/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/diff-delta.c

  • Committer: Robert Collins
  • Date: 2010-05-06 23:41:35 UTC
  • mto: This revision was merged to the branch mainline in revision 5223.
  • Revision ID: robertc@robertcollins.net-20100506234135-yivbzczw1sejxnxc
Lock methods on ``Tree``, ``Branch`` and ``Repository`` are now
expected to return an object which can be used to unlock them. This reduces
duplicate code when using cleanups. The previous 'tokens's returned by
``Branch.lock_write`` and ``Repository.lock_write`` are now attributes
on the result of the lock_write. ``repository.RepositoryWriteLockResult``
and ``branch.BranchWriteLockResult`` document this. (Robert Collins)

``log._get_info_for_log_files`` now takes an add_cleanup callable.
(Robert Collins)

Show diffs side-by-side

added added

removed removed

Lines of Context:
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@fluxnic.net>, (C) 2005-2007
 
7
 * Rewritten for GIT by Nicolas Pitre <nico@cam.org>, (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
220
220
    unsigned int i, j, hmask, memsize, fit_in_old, copied_count;
221
221
    struct unpacked_index_entry *entry;
222
222
    struct delta_index *index;
223
 
    struct index_entry *packed_entry, **packed_hash, *old_entry;
 
223
    struct index_entry *packed_entry, **packed_hash, *old_entry, *copy_from;
224
224
    struct index_entry null_entry = {0};
225
225
    void *mem;
226
226
 
280
280
        if (fit_in_old) {
281
281
            // fprintf(stderr, "Fit all %d entries into old index\n",
282
282
            //                 copied_count);
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;
 
283
            /* No need to allocate a new buffer */
 
284
            return NULL;
288
285
        } else {
289
286
            // fprintf(stderr, "Fit only %d entries into old index,"
290
287
            //                 " reallocating\n", copied_count);
334
331
             * old_index->hash_mask? Would it make any real difference?
335
332
             */
336
333
            j = i & old_index->hash_mask;
 
334
            copy_from = old_index->hash[j];
337
335
            for (old_entry = old_index->hash[j];
338
336
                 old_entry < old_index->hash[j + 1] && old_entry->ptr != NULL;
339
337
                 old_entry++) {
372
370
}
373
371
 
374
372
 
375
 
delta_result
 
373
struct delta_index *
376
374
create_delta_index(const struct source_info *src,
377
 
                   struct delta_index *old,
378
 
                   struct delta_index **fresh,
379
 
                   int max_bytes_to_index)
 
375
                   struct delta_index *old)
380
376
{
381
377
    unsigned int i, hsize, hmask, num_entries, prev_val, *hash_count;
382
 
    unsigned int total_num_entries, stride, max_entries;
 
378
    unsigned int total_num_entries;
383
379
    const unsigned char *data, *buffer;
384
380
    struct delta_index *index;
385
381
    struct unpacked_index_entry *entry, **hash;
387
383
    unsigned long memsize;
388
384
 
389
385
    if (!src->buf || !src->size)
390
 
        return DELTA_SOURCE_EMPTY;
 
386
        return NULL;
391
387
    buffer = src->buf;
392
388
 
393
389
    /* Determine index hash size.  Note that indexing skips the
394
 
       first byte so we subtract 1 to get the edge cases right.
395
 
     */
396
 
    stride = RABIN_WINDOW;
 
390
       first byte to allow for optimizing the Rabin's polynomial
 
391
       initialization in create_delta(). */
397
392
    num_entries = (src->size - 1)  / RABIN_WINDOW;
398
 
    if (max_bytes_to_index > 0) {
399
 
        max_entries = (unsigned int) (max_bytes_to_index / RABIN_WINDOW);
400
 
        if (num_entries > max_entries) {
401
 
            /* Limit the max number of matching entries. This reduces the 'best'
402
 
             * possible match, but means we don't consume all of ram.
403
 
             */
404
 
            num_entries = max_entries;
405
 
            stride = (src->size - 1) / num_entries;
406
 
        }
407
 
    }
408
393
    if (old != NULL)
409
394
        total_num_entries = num_entries + old->num_entries;
410
395
    else
423
408
          sizeof(*entry) * total_num_entries;
424
409
    mem = malloc(memsize);
425
410
    if (!mem)
426
 
        return DELTA_OUT_OF_MEMORY;
 
411
        return NULL;
427
412
    hash = mem;
428
413
    mem = hash + hsize;
429
414
    entry = mem;
434
419
    hash_count = calloc(hsize, sizeof(*hash_count));
435
420
    if (!hash_count) {
436
421
        free(hash);
437
 
        return DELTA_OUT_OF_MEMORY;
 
422
        return NULL;
438
423
    }
439
424
 
440
425
    /* then populate the index for the new data */
441
426
    prev_val = ~0;
442
 
    for (data = buffer + num_entries * stride - RABIN_WINDOW;
 
427
    for (data = buffer + num_entries * RABIN_WINDOW - RABIN_WINDOW;
443
428
         data >= buffer;
444
 
         data -= stride) {
 
429
         data -= RABIN_WINDOW) {
445
430
        unsigned int val = 0;
446
431
        for (i = 1; i <= RABIN_WINDOW; i++)
447
432
            val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
465
450
    total_num_entries = limit_hash_buckets(hash, hash_count, hsize,
466
451
                                           total_num_entries);
467
452
    free(hash_count);
 
453
    if (old) {
 
454
        old->last_src = src;
 
455
    }
468
456
    index = pack_delta_index(hash, hsize, total_num_entries, old);
469
457
    free(hash);
470
 
    /* pack_delta_index only returns NULL on malloc failure */
471
458
    if (!index) {
472
 
        return DELTA_OUT_OF_MEMORY;
 
459
        return NULL;
473
460
    }
474
461
    index->last_src = src;
475
 
    *fresh = index;
476
 
    return DELTA_OK;
 
462
    return index;
477
463
}
478
464
 
479
465
/* Take some entries, and put them into a custom hash.
487
473
                       unsigned int hsize)
488
474
{
489
475
    unsigned int hash_offset, hmask, memsize;
490
 
    struct index_entry *entry;
 
476
    struct index_entry *entry, *last_entry;
491
477
    struct index_entry_linked_list *out_entry, **hash;
492
478
    void *mem;
493
479
 
507
493
    /* We know that entries are in the order we want in the output, but they
508
494
     * aren't "grouped" by hash bucket yet.
509
495
     */
 
496
    last_entry = entries + num_entries;
510
497
    for (entry = entries + num_entries - 1; entry >= entries; --entry) {
511
498
        hash_offset = entry->val & hmask;
512
499
        out_entry->p_entry = entry;
531
518
    unsigned int i, j, hsize, hmask, total_num_entries;
532
519
    struct delta_index *index;
533
520
    struct index_entry *entry, *packed_entry, **packed_hash;
534
 
    struct index_entry null_entry = {0};
 
521
    struct index_entry *last_entry, null_entry = {0};
535
522
    void *mem;
536
523
    unsigned long memsize;
537
524
    struct index_entry_linked_list *unpacked_entry, **mini_hash;
582
569
        free(index);
583
570
        return NULL;
584
571
    }
 
572
    last_entry = entries + num_entries;
585
573
    for (i = 0; i < hsize; i++) {
586
574
        /*
587
575
         * Coalesce all entries belonging in one hash bucket
691
679
    }
692
680
}
693
681
 
694
 
delta_result
 
682
struct delta_index *
695
683
create_delta_index_from_delta(const struct source_info *src,
696
 
                              struct delta_index *old_index,
697
 
                              struct delta_index **fresh)
 
684
                              struct delta_index *old_index)
698
685
{
699
686
    unsigned int i, num_entries, max_num_entries, prev_val, num_inserted;
700
687
    unsigned int hash_offset;
703
690
    struct delta_index *new_index;
704
691
    struct index_entry *entry, *entries;
705
692
 
706
 
    if (!old_index)
707
 
        return DELTA_INDEX_NEEDED;
708
693
    if (!src->buf || !src->size)
709
 
        return DELTA_SOURCE_EMPTY;
 
694
        return NULL;
710
695
    buffer = src->buf;
711
696
    top = buffer + src->size;
712
697
 
719
704
 
720
705
    max_num_entries = (src->size - 1)  / RABIN_WINDOW;
721
706
 
722
 
    if (!max_num_entries) {
723
 
        *fresh = old_index;
724
 
        return DELTA_OK;
725
 
    }
726
 
 
727
707
    /* allocate an array to hold whatever entries we find */
728
708
    entries = malloc(sizeof(*entry) * max_num_entries);
729
709
    if (!entries) /* malloc failure */
730
 
        return DELTA_OUT_OF_MEMORY;
 
710
        return NULL;
731
711
 
732
712
    /* then populate the index for the new data */
733
713
    prev_val = ~0;
794
774
        }
795
775
    }
796
776
    if (data != top) {
797
 
        /* The source_info data passed was corrupted or otherwise invalid */
 
777
        /* Something was wrong with this delta */
798
778
        free(entries);
799
 
        return DELTA_SOURCE_BAD;
 
779
        return NULL;
800
780
    }
801
781
    if (num_entries == 0) {
802
782
        /** Nothing to index **/
803
783
        free(entries);
804
 
        *fresh = old_index;
805
 
        return DELTA_OK;
 
784
        return NULL;
806
785
    }
 
786
    assert(old_index != NULL);
807
787
    old_index->last_src = src;
808
788
    /* See if we can fill in these values into the holes in the array */
809
789
    entry = entries;
861
841
        new_index = create_index_from_old_and_new_entries(old_index,
862
842
            entry, num_entries);
863
843
    } else {
864
 
        new_index = old_index;
 
844
        new_index = NULL;
865
845
        // fprintf(stderr, "inserted %d without resizing\n", num_inserted);
866
846
    }
867
847
    free(entries);
868
 
    /* create_index_from_old_and_new_entries returns NULL on malloc failure */
869
 
    if (!new_index)
870
 
        return DELTA_OUT_OF_MEMORY;
871
 
    *fresh = new_index;
872
 
    return DELTA_OK;
 
848
    return new_index;
873
849
}
874
850
 
875
851
void free_delta_index(struct delta_index *index)
877
853
    free(index);
878
854
}
879
855
 
880
 
unsigned long
881
 
sizeof_delta_index(struct delta_index *index)
 
856
unsigned long sizeof_delta_index(struct delta_index *index)
882
857
{
883
858
    if (index)
884
859
        return index->memsize;
892
867
 */
893
868
#define MAX_OP_SIZE (5 + 5 + 1 + RABIN_WINDOW + 7)
894
869
 
895
 
delta_result
 
870
void *
896
871
create_delta(const struct delta_index *index,
897
872
             const void *trg_buf, unsigned long trg_size,
898
 
             unsigned long *delta_size, unsigned long max_size,
899
 
             void **delta_data)
 
873
             unsigned long *delta_size, unsigned long max_size)
900
874
{
901
 
    unsigned int i, outpos, outsize, moff, val;
902
 
    int msize;
 
875
    unsigned int i, outpos, outsize, moff, msize, val;
903
876
    const struct source_info *msource;
904
877
    int inscnt;
905
878
    const unsigned char *ref_data, *ref_top, *data, *top;
906
879
    unsigned char *out;
 
880
    unsigned long source_size;
907
881
 
908
882
    if (!trg_buf || !trg_size)
909
 
        return DELTA_BUFFER_EMPTY;
 
883
        return NULL;
910
884
    if (index == NULL)
911
 
        return DELTA_INDEX_NEEDED;
 
885
        return NULL;
912
886
 
913
887
    outpos = 0;
914
888
    outsize = 8192;
916
890
        outsize = max_size + MAX_OP_SIZE + 1;
917
891
    out = malloc(outsize);
918
892
    if (!out)
919
 
        return DELTA_OUT_OF_MEMORY;
 
893
        return NULL;
 
894
 
 
895
    source_size = index->last_src->size + index->last_src->agg_offset;
920
896
 
921
897
    /* store target buffer size */
922
898
    i = trg_size;
967
943
                 entry++) {
968
944
                const unsigned char *ref;
969
945
                const unsigned char *src;
970
 
                int ref_size;
 
946
                unsigned int ref_size;
971
947
                if (entry->val != val)
972
948
                    continue;
973
949
                ref = entry->ptr;
980
956
                 * match more bytes with this location that we have already
981
957
                 * matched.
982
958
                 */
983
 
                if (ref_size > (top - src))
 
959
                if (ref_size > top - src)
984
960
                    ref_size = top - src;
985
961
                if (ref_size <= msize)
986
962
                    break;
987
963
                /* See how many bytes actually match at this location. */
988
964
                while (ref_size-- && *src++ == *ref)
989
965
                    ref++;
990
 
                if (msize < (ref - entry->ptr)) {
 
966
                if (msize < ref - entry->ptr) {
991
967
                    /* this is our best match so far */
992
968
                    msize = ref - entry->ptr;
993
969
                    msource = entry->src;
1049
1025
             */
1050
1026
            assert(moff < msource->size);
1051
1027
            moff += msource->agg_offset;
1052
 
            assert(moff + msize
1053
 
                <= index->last_src->size + index->last_src->agg_offset);
 
1028
            assert(moff + msize <= source_size);
1054
1029
            if (moff & 0x000000ff)
1055
1030
                out[outpos++] = moff >> 0,  i |= 0x01;
1056
1031
            if (moff & 0x0000ff00)
1094
1069
            out = realloc(out, outsize);
1095
1070
            if (!out) {
1096
1071
                free(tmp);
1097
 
                return DELTA_OUT_OF_MEMORY;
 
1072
                return NULL;
1098
1073
            }
1099
1074
        }
1100
1075
    }
1104
1079
 
1105
1080
    if (max_size && outpos > max_size) {
1106
1081
        free(out);
1107
 
        return DELTA_SIZE_TOO_BIG;
 
1082
        return NULL;
1108
1083
    }
1109
1084
 
1110
1085
    *delta_size = outpos;
1111
 
    *delta_data = out;
1112
 
    return DELTA_OK;
1113
 
}
1114
 
 
1115
 
 
1116
 
int
1117
 
get_entry_summary(const struct delta_index *index, int pos,
1118
 
                  unsigned int *text_offset, unsigned int *hash_val)
1119
 
{
1120
 
    int hsize;
1121
 
    const struct index_entry *entry;
1122
 
    const struct index_entry *start_of_entries;
1123
 
    unsigned int offset;
1124
 
    if (pos < 0 || text_offset == NULL || hash_val == NULL
1125
 
        || index == NULL)
1126
 
    {
1127
 
        return 0;
1128
 
    }
1129
 
    hsize = index->hash_mask + 1;
1130
 
    start_of_entries = (struct index_entry *)(((struct index_entry **)index->hash) + (hsize + 1));
1131
 
    entry = start_of_entries + pos;
1132
 
    if (entry > index->last_entry) {
1133
 
        return 0;
1134
 
    }
1135
 
    if (entry->ptr == NULL) {
1136
 
        *text_offset = 0;
1137
 
        *hash_val = 0;
1138
 
    } else {
1139
 
        offset = entry->src->agg_offset;
1140
 
        offset += (entry->ptr - ((unsigned char *)entry->src->buf));
1141
 
        *text_offset = offset;
1142
 
        *hash_val = entry->val;
1143
 
    }
1144
 
    return 1;
1145
 
}
1146
 
 
1147
 
 
1148
 
int
1149
 
get_hash_offset(const struct delta_index *index, int pos,
1150
 
                unsigned int *entry_offset)
1151
 
{
1152
 
    int hsize;
1153
 
    const struct index_entry *entry;
1154
 
    const struct index_entry *start_of_entries;
1155
 
    if (pos < 0 || index == NULL || entry_offset == NULL)
1156
 
    {
1157
 
        return 0;
1158
 
    }
1159
 
    hsize = index->hash_mask + 1;
1160
 
    start_of_entries = (struct index_entry *)(((struct index_entry **)index->hash) + (hsize + 1));
1161
 
    if (pos >= hsize) {
1162
 
        return 0;
1163
 
    }
1164
 
    entry = index->hash[pos];
1165
 
    if (entry == NULL) {
1166
 
        *entry_offset = -1;
1167
 
    } else {
1168
 
        *entry_offset = (entry - start_of_entries);
1169
 
    }
1170
 
    return 1;
1171
 
}
1172
 
 
1173
 
 
1174
 
unsigned int
1175
 
rabin_hash(const unsigned char *data)
1176
 
{
1177
 
    int i;
1178
 
    unsigned int val = 0;
1179
 
    for (i = 0; i < RABIN_WINDOW; i++)
1180
 
        val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
1181
 
    return val;
 
1086
    return out;
1182
1087
}
1183
1088
 
1184
1089
/* vim: et ts=4 sw=4 sts=4