← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/diff-delta.c

  • Committer: Tarmac
  • Author(s): Vincent Ladeuil
  • Date: 2017-01-30 14:42:05 UTC
  • mfrom: (6620.1.1 trunk)
  • Revision ID: tarmac-20170130144205-r8fh2xpmiuxyozpv
Merge  2.7 into trunk including fix for bug #1657238 [r=vila]

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@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
 
 * This code is free software; you can redistribute it and/or modify
11
 
 * it under the terms of the GNU General Public License version 2 as
12
 
 * published by the Free Software Foundation.
 
10
 * This program is free software; you can redistribute it and/or modify
 
11
 * it under the terms of the GNU General Public License as published by
 
12
 * the Free Software Foundation; either version 2 of the License, or
 
13
 * (at your option) any later version.
 
14
 *
 
15
 * NB: The version in GIT is 'version 2 of the Licence only', however Nicolas
 
16
 * has granted permission for use under 'version 2 or later' in private email
 
17
 * to Robert Collins and Karl Fogel on the 6th April 2009.
13
18
 */
14
19
 
15
20
#include <stdio.h>
275
280
        if (fit_in_old) {
276
281
            // fprintf(stderr, "Fit all %d entries into old index\n",
277
282
            //                 copied_count);
278
 
            /* No need to allocate a new buffer */
279
 
            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;
280
288
        } else {
281
289
            // fprintf(stderr, "Fit only %d entries into old index,"
282
290
            //                 " reallocating\n", copied_count);
365
373
}
366
374
 
367
375
 
368
 
struct delta_index *
 
376
delta_result
369
377
create_delta_index(const struct source_info *src,
370
 
                   struct delta_index *old)
 
378
                   struct delta_index *old,
 
379
                   struct delta_index **fresh,
 
380
                   int max_bytes_to_index)
371
381
{
372
382
    unsigned int i, hsize, hmask, num_entries, prev_val, *hash_count;
373
 
    unsigned int total_num_entries;
 
383
    unsigned int total_num_entries, stride, max_entries;
374
384
    const unsigned char *data, *buffer;
375
385
    struct delta_index *index;
376
386
    struct unpacked_index_entry *entry, **hash;
378
388
    unsigned long memsize;
379
389
 
380
390
    if (!src->buf || !src->size)
381
 
        return NULL;
 
391
        return DELTA_SOURCE_EMPTY;
382
392
    buffer = src->buf;
383
393
 
384
394
    /* Determine index hash size.  Note that indexing skips the
385
 
       first byte to allow for optimizing the Rabin's polynomial
386
 
       initialization in create_delta(). */
 
395
       first byte so we subtract 1 to get the edge cases right.
 
396
     */
 
397
    stride = RABIN_WINDOW;
387
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
    }
388
409
    if (old != NULL)
389
410
        total_num_entries = num_entries + old->num_entries;
390
411
    else
403
424
          sizeof(*entry) * total_num_entries;
404
425
    mem = malloc(memsize);
405
426
    if (!mem)
406
 
        return NULL;
 
427
        return DELTA_OUT_OF_MEMORY;
407
428
    hash = mem;
408
429
    mem = hash + hsize;
409
430
    entry = mem;
414
435
    hash_count = calloc(hsize, sizeof(*hash_count));
415
436
    if (!hash_count) {
416
437
        free(hash);
417
 
        return NULL;
 
438
        return DELTA_OUT_OF_MEMORY;
418
439
    }
419
440
 
420
441
    /* then populate the index for the new data */
421
442
    prev_val = ~0;
422
 
    for (data = buffer + num_entries * RABIN_WINDOW - RABIN_WINDOW;
 
443
    for (data = buffer + num_entries * stride - RABIN_WINDOW;
423
444
         data >= buffer;
424
 
         data -= RABIN_WINDOW) {
 
445
         data -= stride) {
425
446
        unsigned int val = 0;
426
447
        for (i = 1; i <= RABIN_WINDOW; i++)
427
448
            val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
445
466
    total_num_entries = limit_hash_buckets(hash, hash_count, hsize,
446
467
                                           total_num_entries);
447
468
    free(hash_count);
448
 
    if (old) {
449
 
        old->last_src = src;
450
 
    }
451
469
    index = pack_delta_index(hash, hsize, total_num_entries, old);
452
470
    free(hash);
 
471
    /* pack_delta_index only returns NULL on malloc failure */
453
472
    if (!index) {
454
 
        return NULL;
 
473
        return DELTA_OUT_OF_MEMORY;
455
474
    }
456
475
    index->last_src = src;
457
 
    return index;
 
476
    *fresh = index;
 
477
    return DELTA_OK;
458
478
}
459
479
 
460
480
/* Take some entries, and put them into a custom hash.
468
488
                       unsigned int hsize)
469
489
{
470
490
    unsigned int hash_offset, hmask, memsize;
471
 
    struct index_entry *entry, *last_entry;
 
491
    struct index_entry *entry;
472
492
    struct index_entry_linked_list *out_entry, **hash;
473
493
    void *mem;
474
494
 
488
508
    /* We know that entries are in the order we want in the output, but they
489
509
     * aren't "grouped" by hash bucket yet.
490
510
     */
491
 
    last_entry = entries + num_entries;
492
511
    for (entry = entries + num_entries - 1; entry >= entries; --entry) {
493
512
        hash_offset = entry->val & hmask;
494
513
        out_entry->p_entry = entry;
513
532
    unsigned int i, j, hsize, hmask, total_num_entries;
514
533
    struct delta_index *index;
515
534
    struct index_entry *entry, *packed_entry, **packed_hash;
516
 
    struct index_entry *last_entry, null_entry = {0};
 
535
    struct index_entry null_entry = {0};
517
536
    void *mem;
518
537
    unsigned long memsize;
519
538
    struct index_entry_linked_list *unpacked_entry, **mini_hash;
564
583
        free(index);
565
584
        return NULL;
566
585
    }
567
 
    last_entry = entries + num_entries;
568
586
    for (i = 0; i < hsize; i++) {
569
587
        /*
570
588
         * Coalesce all entries belonging in one hash bucket
674
692
    }
675
693
}
676
694
 
677
 
struct delta_index *
 
695
delta_result
678
696
create_delta_index_from_delta(const struct source_info *src,
679
 
                              struct delta_index *old_index)
 
697
                              struct delta_index *old_index,
 
698
                              struct delta_index **fresh)
680
699
{
681
700
    unsigned int i, num_entries, max_num_entries, prev_val, num_inserted;
682
701
    unsigned int hash_offset;
683
702
    const unsigned char *data, *buffer, *top;
684
703
    unsigned char cmd;
685
704
    struct delta_index *new_index;
686
 
    struct index_entry *entry, *entries, *old_entry;
 
705
    struct index_entry *entry, *entries;
687
706
 
 
707
    if (!old_index)
 
708
        return DELTA_INDEX_NEEDED;
688
709
    if (!src->buf || !src->size)
689
 
        return NULL;
 
710
        return DELTA_SOURCE_EMPTY;
690
711
    buffer = src->buf;
691
712
    top = buffer + src->size;
692
713
 
699
720
 
700
721
    max_num_entries = (src->size - 1)  / RABIN_WINDOW;
701
722
 
 
723
    if (!max_num_entries) {
 
724
        *fresh = old_index;
 
725
        return DELTA_OK;
 
726
    }
 
727
 
702
728
    /* allocate an array to hold whatever entries we find */
703
729
    entries = malloc(sizeof(*entry) * max_num_entries);
704
730
    if (!entries) /* malloc failure */
705
 
        return NULL;
 
731
        return DELTA_OUT_OF_MEMORY;
706
732
 
707
733
    /* then populate the index for the new data */
708
734
    prev_val = ~0;
709
735
    data = buffer;
710
736
    /* target size */
711
 
    get_delta_hdr_size(&data, top);
 
737
    /* get_delta_hdr_size doesn't mutate the content, just moves the
 
738
     * start-of-data pointer, so it is safe to do the cast.
 
739
     */
 
740
    get_delta_hdr_size((unsigned char**)&data, top);
712
741
    entry = entries; /* start at the first slot */
713
742
    num_entries = 0; /* calculate the real number of entries */
714
743
    while (data < top) {
766
795
        }
767
796
    }
768
797
    if (data != top) {
769
 
        /* Something was wrong with this delta */
 
798
        /* The source_info data passed was corrupted or otherwise invalid */
770
799
        free(entries);
771
 
        return NULL;
 
800
        return DELTA_SOURCE_BAD;
772
801
    }
773
802
    if (num_entries == 0) {
774
803
        /** Nothing to index **/
775
804
        free(entries);
776
 
        return NULL;
 
805
        *fresh = old_index;
 
806
        return DELTA_OK;
777
807
    }
778
 
    assert(old_index != NULL);
779
808
    old_index->last_src = src;
780
809
    /* See if we can fill in these values into the holes in the array */
781
810
    entry = entries;
782
811
    num_inserted = 0;
783
812
    for (; num_entries > 0; --num_entries, ++entry) {
 
813
        struct index_entry *next_bucket_entry, *cur_entry, *bucket_first_entry;
784
814
        hash_offset = (entry->val & old_index->hash_mask);
785
815
        /* The basic structure is a hash => packed_entries that fit in that
786
816
         * hash bucket. Things are structured such that the hash-pointers are
789
819
         * forward. If there are no NULL targets, then we know because
790
820
         * entry->ptr will not be NULL.
791
821
         */
792
 
        old_entry = old_index->hash[hash_offset + 1];
793
 
        old_entry--;
794
 
        while (old_entry->ptr == NULL
795
 
               && old_entry >= old_index->hash[hash_offset]) {
796
 
            old_entry--;
 
822
        // The start of the next bucket, this may point past the end of the
 
823
        // entry table if hash_offset is the last bucket.
 
824
        next_bucket_entry = old_index->hash[hash_offset + 1];
 
825
        // First entry in this bucket
 
826
        bucket_first_entry = old_index->hash[hash_offset];
 
827
        cur_entry = next_bucket_entry - 1;
 
828
        while (cur_entry->ptr == NULL && cur_entry >= bucket_first_entry) {
 
829
            cur_entry--;
797
830
        }
798
 
        old_entry++;
799
 
        if (old_entry->ptr != NULL
800
 
            || old_entry >= old_index->hash[hash_offset + 1]) {
 
831
        // cur_entry now either points at the first NULL, or it points to
 
832
        // next_bucket_entry if there were no blank spots.
 
833
        cur_entry++;
 
834
        if (cur_entry >= next_bucket_entry || cur_entry->ptr != NULL) {
801
835
            /* There is no room for this entry, we have to resize */
802
836
            // char buff[128];
803
837
            // get_text(buff, entry->ptr);
814
848
            break;
815
849
        }
816
850
        num_inserted++;
817
 
        *old_entry = *entry;
 
851
        *cur_entry = *entry;
818
852
        /* For entries which we *do* manage to insert into old_index, we don't
819
853
         * want them double copied into the final output.
820
854
         */
828
862
        new_index = create_index_from_old_and_new_entries(old_index,
829
863
            entry, num_entries);
830
864
    } else {
831
 
        new_index = NULL;
 
865
        new_index = old_index;
832
866
        // fprintf(stderr, "inserted %d without resizing\n", num_inserted);
833
867
    }
834
868
    free(entries);
835
 
    return new_index;
 
869
    /* create_index_from_old_and_new_entries returns NULL on malloc failure */
 
870
    if (!new_index)
 
871
        return DELTA_OUT_OF_MEMORY;
 
872
    *fresh = new_index;
 
873
    return DELTA_OK;
836
874
}
837
875
 
838
876
void free_delta_index(struct delta_index *index)
840
878
    free(index);
841
879
}
842
880
 
843
 
unsigned long sizeof_delta_index(struct delta_index *index)
 
881
unsigned long
 
882
sizeof_delta_index(struct delta_index *index)
844
883
{
845
884
    if (index)
846
885
        return index->memsize;
854
893
 */
855
894
#define MAX_OP_SIZE (5 + 5 + 1 + RABIN_WINDOW + 7)
856
895
 
857
 
void *
 
896
delta_result
858
897
create_delta(const struct delta_index *index,
859
898
             const void *trg_buf, unsigned long trg_size,
860
 
             unsigned long *delta_size, unsigned long max_size)
 
899
             unsigned long *delta_size, unsigned long max_size,
 
900
             void **delta_data)
861
901
{
862
 
    unsigned int i, outpos, outsize, moff, msize, val;
 
902
    unsigned int i, outpos, outsize, moff, val;
 
903
    int msize;
863
904
    const struct source_info *msource;
864
905
    int inscnt;
865
906
    const unsigned char *ref_data, *ref_top, *data, *top;
867
908
    unsigned long source_size;
868
909
 
869
910
    if (!trg_buf || !trg_size)
870
 
        return NULL;
 
911
        return DELTA_BUFFER_EMPTY;
871
912
    if (index == NULL)
872
 
        return NULL;
 
913
        return DELTA_INDEX_NEEDED;
873
914
 
874
915
    outpos = 0;
875
916
    outsize = 8192;
877
918
        outsize = max_size + MAX_OP_SIZE + 1;
878
919
    out = malloc(outsize);
879
920
    if (!out)
880
 
        return NULL;
 
921
        return DELTA_OUT_OF_MEMORY;
881
922
 
882
923
    source_size = index->last_src->size + index->last_src->agg_offset;
883
924
 
930
971
                 entry++) {
931
972
                const unsigned char *ref;
932
973
                const unsigned char *src;
933
 
                unsigned int ref_size;
 
974
                int ref_size;
934
975
                if (entry->val != val)
935
976
                    continue;
936
977
                ref = entry->ptr;
943
984
                 * match more bytes with this location that we have already
944
985
                 * matched.
945
986
                 */
946
 
                if (ref_size > top - src)
 
987
                if (ref_size > (top - src))
947
988
                    ref_size = top - src;
948
989
                if (ref_size <= msize)
949
990
                    break;
950
991
                /* See how many bytes actually match at this location. */
951
992
                while (ref_size-- && *src++ == *ref)
952
993
                    ref++;
953
 
                if (msize < ref - entry->ptr) {
 
994
                if (msize < (ref - entry->ptr)) {
954
995
                    /* this is our best match so far */
955
996
                    msize = ref - entry->ptr;
956
997
                    msource = entry->src;
1056
1097
            out = realloc(out, outsize);
1057
1098
            if (!out) {
1058
1099
                free(tmp);
1059
 
                return NULL;
 
1100
                return DELTA_OUT_OF_MEMORY;
1060
1101
            }
1061
1102
        }
1062
1103
    }
1066
1107
 
1067
1108
    if (max_size && outpos > max_size) {
1068
1109
        free(out);
1069
 
        return NULL;
 
1110
        return DELTA_SIZE_TOO_BIG;
1070
1111
    }
1071
1112
 
1072
1113
    *delta_size = outpos;
1073
 
    return out;
 
1114
    *delta_data = out;
 
1115
    return DELTA_OK;
 
1116
}
 
1117
 
 
1118
 
 
1119
int
 
1120
get_entry_summary(const struct delta_index *index, int pos,
 
1121
                  unsigned int *text_offset, unsigned int *hash_val)
 
1122
{
 
1123
    int hsize;
 
1124
    const struct index_entry *entry;
 
1125
    const struct index_entry *start_of_entries;
 
1126
    unsigned int offset;
 
1127
    if (pos < 0 || text_offset == NULL || hash_val == NULL
 
1128
        || index == NULL)
 
1129
    {
 
1130
        return 0;
 
1131
    }
 
1132
    hsize = index->hash_mask + 1;
 
1133
    start_of_entries = (struct index_entry *)(((struct index_entry **)index->hash) + (hsize + 1));
 
1134
    entry = start_of_entries + pos;
 
1135
    if (entry > index->last_entry) {
 
1136
        return 0;
 
1137
    }
 
1138
    if (entry->ptr == NULL) {
 
1139
        *text_offset = 0;
 
1140
        *hash_val = 0;
 
1141
    } else {
 
1142
        offset = entry->src->agg_offset;
 
1143
        offset += (entry->ptr - ((unsigned char *)entry->src->buf));
 
1144
        *text_offset = offset;
 
1145
        *hash_val = entry->val;
 
1146
    }
 
1147
    return 1;
 
1148
}
 
1149
 
 
1150
 
 
1151
int
 
1152
get_hash_offset(const struct delta_index *index, int pos,
 
1153
                unsigned int *entry_offset)
 
1154
{
 
1155
    int hsize;
 
1156
    const struct index_entry *entry;
 
1157
    const struct index_entry *start_of_entries;
 
1158
    if (pos < 0 || index == NULL || entry_offset == NULL)
 
1159
    {
 
1160
        return 0;
 
1161
    }
 
1162
    hsize = index->hash_mask + 1;
 
1163
    start_of_entries = (struct index_entry *)(((struct index_entry **)index->hash) + (hsize + 1));
 
1164
    if (pos >= hsize) {
 
1165
        return 0;
 
1166
    }
 
1167
    entry = index->hash[pos];
 
1168
    if (entry == NULL) {
 
1169
        *entry_offset = -1;
 
1170
    } else {
 
1171
        *entry_offset = (entry - start_of_entries);
 
1172
    }
 
1173
    return 1;
 
1174
}
 
1175
 
 
1176
 
 
1177
unsigned int
 
1178
rabin_hash(const unsigned char *data)
 
1179
{
 
1180
    int i;
 
1181
    unsigned int val = 0;
 
1182
    for (i = 0; i < RABIN_WINDOW; i++)
 
1183
        val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
 
1184
    return val;
1074
1185
}
1075
1186
 
1076
1187
/* vim: et ts=4 sw=4 sts=4