~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/diff-delta.c

• browse files at revision 5050.73.11
• compare with another revision
• download diff
• download tarball
• view history from revision 5050.73.11

Show diffs side-by-side

added

removed

bzrlib/diff-delta.c

4

4

 * This code was greatly inspired by parts of LibXDiff from Davide Libenzi

5

5

 * http://www.xmailserver.org/xdiff-lib.html

6

6

 *

7

 

 * Rewritten for GIT by Nicolas Pitre <nico@cam.org>, (C) 2005-2007

 

7

 * Rewritten for GIT by Nicolas Pitre <nico@fluxnic.net>, (C) 2005-2007

8

8

 * Adapted for Bazaar by John Arbash Meinel <john@arbash-meinel.com> (C) 2009

9

9

 *

10

10

 * This program is free software; you can redistribute it and/or modify

280

280

        if (fit_in_old) {

281

281

            // fprintf(stderr, "Fit all %d entries into old index\n",

282

282

            //                 copied_count);

283

 

            /* No need to allocate a new buffer */

284

 

            return NULL;

 

283

            /*

 

284

             * No need to allocate a new buffer, but return old_index ptr so

 

285

             * callers can distinguish this from an OOM failure.

 

286

             */

 

287

            return old_index;

285

288

        } else {

286

289

            // fprintf(stderr, "Fit only %d entries into old index,"

287

290

            //                 " reallocating\n", copied_count);

370

373

}

371

374

 

372

375

 

373

 

struct delta_index *

 

376

delta_result

374

377

create_delta_index(const struct source_info *src,

375

 

                   struct delta_index *old)

 

378

                   struct delta_index *old,

 

379

                   struct delta_index **fresh,

 

380

                   int max_bytes_to_index)

376

381

{

377

382

    unsigned int i, hsize, hmask, num_entries, prev_val, *hash_count;

378

 

    unsigned int total_num_entries;

 

383

    unsigned int total_num_entries, stride, max_entries;

379

384

    const unsigned char *data, *buffer;

380

385

    struct delta_index *index;

381

386

    struct unpacked_index_entry *entry, **hash;

383

388

    unsigned long memsize;

384

389

 

385

390

    if (!src->buf || !src->size)

386

 

        return NULL;

 

391

        return DELTA_SOURCE_EMPTY;

387

392

    buffer = src->buf;

388

393

 

389

394

    /* Determine index hash size.  Note that indexing skips the

390

 

       first byte to allow for optimizing the Rabin's polynomial

391

 

       initialization in create_delta(). */

 

395

       first byte so we subtract 1 to get the edge cases right.

 

396

     */

 

397

    stride = RABIN_WINDOW;

392

398

    num_entries = (src->size - 1)  / RABIN_WINDOW;

 

399

    if (max_bytes_to_index > 0) {

 

400

        max_entries = (unsigned int) (max_bytes_to_index / RABIN_WINDOW);

 

401

        if (num_entries > max_entries) {

 

402

            /* Limit the max number of matching entries. This reduces the 'best'

 

403

             * possible match, but means we don't consume all of ram.

 

404

             */

 

405

            num_entries = max_entries;

 

406

            stride = (src->size - 1) / num_entries;

 

407

        }

 

408

    }

393

409

    if (old != NULL)

394

410

        total_num_entries = num_entries + old->num_entries;

395

411

    else

408

424

          sizeof(*entry) * total_num_entries;

409

425

    mem = malloc(memsize);

410

426

    if (!mem)

411

 

        return NULL;

 

427

        return DELTA_OUT_OF_MEMORY;

412

428

    hash = mem;

413

429

    mem = hash + hsize;

414

430

    entry = mem;

419

435

    hash_count = calloc(hsize, sizeof(*hash_count));

420

436

    if (!hash_count) {

421

437

        free(hash);

422

 

        return NULL;

 

438

        return DELTA_OUT_OF_MEMORY;

423

439

    }

424

440

 

425

441

    /* then populate the index for the new data */

426

442

    prev_val = ~0;

427

 

    for (data = buffer + num_entries * RABIN_WINDOW - RABIN_WINDOW;

 

443

    for (data = buffer + num_entries * stride - RABIN_WINDOW;

428

444

         data >= buffer;

429

 

         data -= RABIN_WINDOW) {

 

445

         data -= stride) {

430

446

        unsigned int val = 0;

431

447

        for (i = 1; i <= RABIN_WINDOW; i++)

432

448

            val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];

450

466

    total_num_entries = limit_hash_buckets(hash, hash_count, hsize,

451

467

                                           total_num_entries);

452

468

    free(hash_count);

453

 

    if (old) {

454

 

        old->last_src = src;

455

 

    }

456

469

    index = pack_delta_index(hash, hsize, total_num_entries, old);

457

470

    free(hash);

 

471

    /* pack_delta_index only returns NULL on malloc failure */

458

472

    if (!index) {

459

 

        return NULL;

 

473

        return DELTA_OUT_OF_MEMORY;

460

474

    }

461

475

    index->last_src = src;

462

 

    return index;

 

476

    *fresh = index;

 

477

    return DELTA_OK;

463

478

}

464

479

 

465

480

/* Take some entries, and put them into a custom hash.

473

488

                       unsigned int hsize)

474

489

{

475

490

    unsigned int hash_offset, hmask, memsize;

476

 

    struct index_entry *entry, *last_entry;

 

491

    struct index_entry *entry;

477

492

    struct index_entry_linked_list *out_entry, **hash;

478

493

    void *mem;

479

494

 

493

508

    /* We know that entries are in the order we want in the output, but they

494

509

     * aren't "grouped" by hash bucket yet.

495

510

     */

496

 

    last_entry = entries + num_entries;

497

511

    for (entry = entries + num_entries - 1; entry >= entries; --entry) {

498

512

        hash_offset = entry->val & hmask;

499

513

        out_entry->p_entry = entry;

518

532

    unsigned int i, j, hsize, hmask, total_num_entries;

519

533

    struct delta_index *index;

520

534

    struct index_entry *entry, *packed_entry, **packed_hash;

521

 

    struct index_entry *last_entry, null_entry = {0};

 

535

    struct index_entry null_entry = {0};

522

536

    void *mem;

523

537

    unsigned long memsize;

524

538

    struct index_entry_linked_list *unpacked_entry, **mini_hash;

569

583

        free(index);

570

584

        return NULL;

571

585

    }

572

 

    last_entry = entries + num_entries;

573

586

    for (i = 0; i < hsize; i++) {

574

587

        /*

575

588

         * Coalesce all entries belonging in one hash bucket

679

692

    }

680

693

}

681

694

 

682

 

struct delta_index *

 

695

delta_result

683

696

create_delta_index_from_delta(const struct source_info *src,

684

 

                              struct delta_index *old_index)

 

697

                              struct delta_index *old_index,

 

698

                              struct delta_index **fresh)

685

699

{

686

700

    unsigned int i, num_entries, max_num_entries, prev_val, num_inserted;

687

701

    unsigned int hash_offset;

690

704

    struct delta_index *new_index;

691

705

    struct index_entry *entry, *entries;

692

706

 

 

707

    if (!old_index)

 

708

        return DELTA_INDEX_NEEDED;

693

709

    if (!src->buf || !src->size)

694

 

        return NULL;

 

710

        return DELTA_SOURCE_EMPTY;

695

711

    buffer = src->buf;

696

712

    top = buffer + src->size;

697

713

 

707

723

    /* allocate an array to hold whatever entries we find */

708

724

    entries = malloc(sizeof(*entry) * max_num_entries);

709

725

    if (!entries) /* malloc failure */

710

 

        return NULL;

 

726

        return DELTA_OUT_OF_MEMORY;

711

727

 

712

728

    /* then populate the index for the new data */

713

729

    prev_val = ~0;

774

790

        }

775

791

    }

776

792

    if (data != top) {

777

 

        /* Something was wrong with this delta */

 

793

        /* The source_info data passed was corrupted or otherwise invalid */

778

794

        free(entries);

779

 

        return NULL;

 

795

        return DELTA_SOURCE_BAD;

780

796

    }

781

797

    if (num_entries == 0) {

782

798

        /** Nothing to index **/

783

799

        free(entries);

784

 

        return NULL;

 

800

        *fresh = old_index;

 

801

        return DELTA_OK;

785

802

    }

786

 

    assert(old_index != NULL);

787

803

    old_index->last_src = src;

788

804

    /* See if we can fill in these values into the holes in the array */

789

805

    entry = entries;

841

857

        new_index = create_index_from_old_and_new_entries(old_index,

842

858

            entry, num_entries);

843

859

    } else {

844

 

        new_index = NULL;

 

860

        new_index = old_index;

845

861

        // fprintf(stderr, "inserted %d without resizing\n", num_inserted);

846

862

    }

847

863

    free(entries);

848

 

    return new_index;

 

864

    /* create_index_from_old_and_new_entries returns NULL on malloc failure */

 

865

    if (!new_index)

 

866

        return DELTA_OUT_OF_MEMORY;

 

867

    *fresh = new_index;

 

868

    return DELTA_OK;

849

869

}

850

870

 

851

871

void free_delta_index(struct delta_index *index)

868

888

 */

869

889

#define MAX_OP_SIZE (5 + 5 + 1 + RABIN_WINDOW + 7)

870

890

 

871

 

void *

 

891

delta_result

872

892

create_delta(const struct delta_index *index,

873

893

             const void *trg_buf, unsigned long trg_size,

874

 

             unsigned long *delta_size, unsigned long max_size)

 

894

             unsigned long *delta_size, unsigned long max_size,

 

895

             void **delta_data)

875

896

{

876

897

    unsigned int i, outpos, outsize, moff, val;

877

898

    int msize;

882

903

    unsigned long source_size;

883

904

 

884

905

    if (!trg_buf || !trg_size)

885

 

        return NULL;

 

906

        return DELTA_BUFFER_EMPTY;

886

907

    if (index == NULL)

887

 

        return NULL;

 

908

        return DELTA_INDEX_NEEDED;

888

909

 

889

910

    outpos = 0;

890

911

    outsize = 8192;

892

913

        outsize = max_size + MAX_OP_SIZE + 1;

893

914

    out = malloc(outsize);

894

915

    if (!out)

895

 

        return NULL;

 

916

        return DELTA_OUT_OF_MEMORY;

896

917

 

897

918

    source_size = index->last_src->size + index->last_src->agg_offset;

898

919

 

1071

1092

            out = realloc(out, outsize);

1072

1093

            if (!out) {

1073

1094

                free(tmp);

1074

 

                return NULL;

 

1095

                return DELTA_OUT_OF_MEMORY;

1075

1096

            }

1076

1097

        }

1077

1098

    }

1081

1102

 

1082

1103

    if (max_size && outpos > max_size) {

1083

1104

        free(out);

1084

 

        return NULL;

 

1105

        return DELTA_SIZE_TOO_BIG;

1085

1106

    }

1086

1107

 

1087

1108

    *delta_size = outpos;

1088

 

    return out;

 

1109

    *delta_data = out;

 

1110

    return DELTA_OK;

 

1111

}

 

1112

 

 

1113

 

 

1114

int

 

1115

get_entry_summary(const struct delta_index *index, int pos,

 

1116

                  unsigned int *text_offset, unsigned int *hash_val)

 

1117

{

 

1118

    int hsize;

 

1119

    const struct index_entry *entry;

 

1120

    const struct index_entry *start_of_entries;

 

1121

    unsigned int offset;

 

1122

    if (pos < 0 || text_offset == NULL || hash_val == NULL

 

1123

        || index == NULL)

 

1124

    {

 

1125

        return 0;

 

1126

    }

 

1127

    hsize = index->hash_mask + 1;

 

1128

    start_of_entries = (struct index_entry *)(((struct index_entry **)index->hash) + (hsize + 1));

 

1129

    entry = start_of_entries + pos;

 

1130

    if (entry > index->last_entry) {

 

1131

        return 0;

 

1132

    }

 

1133

    if (entry->ptr == NULL) {

 

1134

        *text_offset = 0;

 

1135

        *hash_val = 0;

 

1136

    } else {

 

1137

        offset = entry->src->agg_offset;

 

1138

        offset += (entry->ptr - ((unsigned char *)entry->src->buf));

 

1139

        *text_offset = offset;

 

1140

        *hash_val = entry->val;

 

1141

    }

 

1142

    return 1;

 

1143

}

 

1144

 

 

1145

 

 

1146

int

 

1147

get_hash_offset(const struct delta_index *index, int pos,

 

1148

                unsigned int *entry_offset)

 

1149

{

 

1150

    int hsize;

 

1151

    const struct index_entry *entry;

 

1152

    const struct index_entry *start_of_entries;

 

1153

    if (pos < 0 || index == NULL || entry_offset == NULL)

 

1154

    {

 

1155

        return 0;

 

1156

    }

 

1157

    hsize = index->hash_mask + 1;

 

1158

    start_of_entries = (struct index_entry *)(((struct index_entry **)index->hash) + (hsize + 1));

 

1159

    if (pos >= hsize) {

 

1160

        return 0;

 

1161

    }

 

1162

    entry = index->hash[pos];

 

1163

    if (entry == NULL) {

 

1164

        *entry_offset = -1;

 

1165

    } else {

 

1166

        *entry_offset = (entry - start_of_entries);

 

1167

    }

 

1168

    return 1;

 

1169

}

 

1170

 

 

1171

 

 

1172

unsigned int

 

1173

rabin_hash(const unsigned char *data)

 

1174

{

 

1175

    int i;

 

1176

    unsigned int val = 0;

 

1177

    for (i = 0; i < RABIN_WINDOW; i++)

 

1178

        val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];

 

1179

    return val;

1089

1180

}

1090

1181

 

1091

1182

/* vim: et ts=4 sw=4 sts=4

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.1