/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 breezy/bzr/diff-delta.c

  • Committer: Jelmer Vernooij
  • Date: 2019-03-04 07:14:58 UTC
  • mto: (7290.1.13 work)
  • mto: This revision was merged to the branch mainline in revision 7295.
  • Revision ID: jelmer@jelmer.uk-20190304071458-2zp29edsanbi1560
Fix tests on Python 3.

Show diffs side-by-side

added added

removed removed

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