← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/diff-delta.c

  • Committer: Ian Clatworthy
  • Date: 2009-09-09 15:30:59 UTC
  • mto: (4634.37.2 prepare-2.0)
  • mto: This revision was merged to the branch mainline in revision 4689.
  • Revision ID: ian.clatworthy@canonical.com-20090909153059-sb038agvd38ci2q8
more link fixes in the User Guide

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
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);
373
370
}
374
371
 
375
372
 
376
 
delta_result
 
373
struct delta_index *
377
374
create_delta_index(const struct source_info *src,
378
 
                   struct delta_index *old,
379
 
                   struct delta_index **fresh,
380
 
                   int max_bytes_to_index)
 
375
                   struct delta_index *old)
381
376
{
382
377
    unsigned int i, hsize, hmask, num_entries, prev_val, *hash_count;
383
 
    unsigned int total_num_entries, stride, max_entries;
 
378
    unsigned int total_num_entries;
384
379
    const unsigned char *data, *buffer;
385
380
    struct delta_index *index;
386
381
    struct unpacked_index_entry *entry, **hash;
388
383
    unsigned long memsize;
389
384
 
390
385
    if (!src->buf || !src->size)
391
 
        return DELTA_SOURCE_EMPTY;
 
386
        return NULL;
392
387
    buffer = src->buf;
393
388
 
394
389
    /* Determine index hash size.  Note that indexing skips the
395
 
       first byte so we subtract 1 to get the edge cases right.
396
 
     */
397
 
    stride = RABIN_WINDOW;
 
390
       first byte to allow for optimizing the Rabin's polynomial
 
391
       initialization in create_delta(). */
398
392
    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
 
    }
409
393
    if (old != NULL)
410
394
        total_num_entries = num_entries + old->num_entries;
411
395
    else
424
408
          sizeof(*entry) * total_num_entries;
425
409
    mem = malloc(memsize);
426
410
    if (!mem)
427
 
        return DELTA_OUT_OF_MEMORY;
 
411
        return NULL;
428
412
    hash = mem;
429
413
    mem = hash + hsize;
430
414
    entry = mem;
435
419
    hash_count = calloc(hsize, sizeof(*hash_count));
436
420
    if (!hash_count) {
437
421
        free(hash);
438
 
        return DELTA_OUT_OF_MEMORY;
 
422
        return NULL;
439
423
    }
440
424
 
441
425
    /* then populate the index for the new data */
442
426
    prev_val = ~0;
443
 
    for (data = buffer + num_entries * stride - RABIN_WINDOW;
 
427
    for (data = buffer + num_entries * RABIN_WINDOW - RABIN_WINDOW;
444
428
         data >= buffer;
445
 
         data -= stride) {
 
429
         data -= RABIN_WINDOW) {
446
430
        unsigned int val = 0;
447
431
        for (i = 1; i <= RABIN_WINDOW; i++)
448
432
            val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
466
450
    total_num_entries = limit_hash_buckets(hash, hash_count, hsize,
467
451
                                           total_num_entries);
468
452
    free(hash_count);
 
453
    if (old) {
 
454
        old->last_src = src;
 
455
    }
469
456
    index = pack_delta_index(hash, hsize, total_num_entries, old);
470
457
    free(hash);
471
 
    /* pack_delta_index only returns NULL on malloc failure */
472
458
    if (!index) {
473
 
        return DELTA_OUT_OF_MEMORY;
 
459
        return NULL;
474
460
    }
475
461
    index->last_src = src;
476
 
    *fresh = index;
477
 
    return DELTA_OK;
 
462
    return index;
478
463
}
479
464
 
480
465
/* Take some entries, and put them into a custom hash.
488
473
                       unsigned int hsize)
489
474
{
490
475
    unsigned int hash_offset, hmask, memsize;
491
 
    struct index_entry *entry;
 
476
    struct index_entry *entry, *last_entry;
492
477
    struct index_entry_linked_list *out_entry, **hash;
493
478
    void *mem;
494
479
 
508
493
    /* We know that entries are in the order we want in the output, but they
509
494
     * aren't "grouped" by hash bucket yet.
510
495
     */
 
496
    last_entry = entries + num_entries;
511
497
    for (entry = entries + num_entries - 1; entry >= entries; --entry) {
512
498
        hash_offset = entry->val & hmask;
513
499
        out_entry->p_entry = entry;
532
518
    unsigned int i, j, hsize, hmask, total_num_entries;
533
519
    struct delta_index *index;
534
520
    struct index_entry *entry, *packed_entry, **packed_hash;
535
 
    struct index_entry null_entry = {0};
 
521
    struct index_entry *last_entry, null_entry = {0};
536
522
    void *mem;
537
523
    unsigned long memsize;
538
524
    struct index_entry_linked_list *unpacked_entry, **mini_hash;
583
569
        free(index);
584
570
        return NULL;
585
571
    }
 
572
    last_entry = entries + num_entries;
586
573
    for (i = 0; i < hsize; i++) {
587
574
        /*
588
575
         * Coalesce all entries belonging in one hash bucket
692
679
    }
693
680
}
694
681
 
695
 
delta_result
 
682
struct delta_index *
696
683
create_delta_index_from_delta(const struct source_info *src,
697
 
                              struct delta_index *old_index,
698
 
                              struct delta_index **fresh)
 
684
                              struct delta_index *old_index)
699
685
{
700
686
    unsigned int i, num_entries, max_num_entries, prev_val, num_inserted;
701
687
    unsigned int hash_offset;
702
688
    const unsigned char *data, *buffer, *top;
703
689
    unsigned char cmd;
704
690
    struct delta_index *new_index;
705
 
    struct index_entry *entry, *entries;
 
691
    struct index_entry *entry, *entries, *old_entry;
706
692
 
707
 
    if (!old_index)
708
 
        return DELTA_INDEX_NEEDED;
709
693
    if (!src->buf || !src->size)
710
 
        return DELTA_SOURCE_EMPTY;
 
694
        return NULL;
711
695
    buffer = src->buf;
712
696
    top = buffer + src->size;
713
697
 
720
704
 
721
705
    max_num_entries = (src->size - 1)  / RABIN_WINDOW;
722
706
 
723
 
    if (!max_num_entries) {
724
 
        *fresh = old_index;
725
 
        return DELTA_OK;
726
 
    }
727
 
 
728
707
    /* allocate an array to hold whatever entries we find */
729
708
    entries = malloc(sizeof(*entry) * max_num_entries);
730
709
    if (!entries) /* malloc failure */
731
 
        return DELTA_OUT_OF_MEMORY;
 
710
        return NULL;
732
711
 
733
712
    /* then populate the index for the new data */
734
713
    prev_val = ~0;
795
774
        }
796
775
    }
797
776
    if (data != top) {
798
 
        /* The source_info data passed was corrupted or otherwise invalid */
 
777
        /* Something was wrong with this delta */
799
778
        free(entries);
800
 
        return DELTA_SOURCE_BAD;
 
779
        return NULL;
801
780
    }
802
781
    if (num_entries == 0) {
803
782
        /** Nothing to index **/
804
783
        free(entries);
805
 
        *fresh = old_index;
806
 
        return DELTA_OK;
 
784
        return NULL;
807
785
    }
 
786
    assert(old_index != NULL);
808
787
    old_index->last_src = src;
809
788
    /* See if we can fill in these values into the holes in the array */
810
789
    entry = entries;
811
790
    num_inserted = 0;
812
791
    for (; num_entries > 0; --num_entries, ++entry) {
813
 
        struct index_entry *next_bucket_entry, *cur_entry, *bucket_first_entry;
814
792
        hash_offset = (entry->val & old_index->hash_mask);
815
793
        /* The basic structure is a hash => packed_entries that fit in that
816
794
         * hash bucket. Things are structured such that the hash-pointers are
819
797
         * forward. If there are no NULL targets, then we know because
820
798
         * entry->ptr will not be NULL.
821
799
         */
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--;
 
800
        old_entry = old_index->hash[hash_offset + 1];
 
801
        old_entry--;
 
802
        while (old_entry->ptr == NULL
 
803
               && old_entry >= old_index->hash[hash_offset]) {
 
804
            old_entry--;
830
805
        }
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) {
 
806
        old_entry++;
 
807
        if (old_entry->ptr != NULL
 
808
            || old_entry >= old_index->hash[hash_offset + 1]) {
835
809
            /* There is no room for this entry, we have to resize */
836
810
            // char buff[128];
837
811
            // get_text(buff, entry->ptr);
848
822
            break;
849
823
        }
850
824
        num_inserted++;
851
 
        *cur_entry = *entry;
 
825
        *old_entry = *entry;
852
826
        /* For entries which we *do* manage to insert into old_index, we don't
853
827
         * want them double copied into the final output.
854
828
         */
862
836
        new_index = create_index_from_old_and_new_entries(old_index,
863
837
            entry, num_entries);
864
838
    } else {
865
 
        new_index = old_index;
 
839
        new_index = NULL;
866
840
        // fprintf(stderr, "inserted %d without resizing\n", num_inserted);
867
841
    }
868
842
    free(entries);
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;
 
843
    return new_index;
874
844
}
875
845
 
876
846
void free_delta_index(struct delta_index *index)
878
848
    free(index);
879
849
}
880
850
 
881
 
unsigned long
882
 
sizeof_delta_index(struct delta_index *index)
 
851
unsigned long sizeof_delta_index(struct delta_index *index)
883
852
{
884
853
    if (index)
885
854
        return index->memsize;
893
862
 */
894
863
#define MAX_OP_SIZE (5 + 5 + 1 + RABIN_WINDOW + 7)
895
864
 
896
 
delta_result
 
865
void *
897
866
create_delta(const struct delta_index *index,
898
867
             const void *trg_buf, unsigned long trg_size,
899
 
             unsigned long *delta_size, unsigned long max_size,
900
 
             void **delta_data)
 
868
             unsigned long *delta_size, unsigned long max_size)
901
869
{
902
 
    unsigned int i, outpos, outsize, moff, val;
903
 
    int msize;
 
870
    unsigned int i, outpos, outsize, moff, msize, val;
904
871
    const struct source_info *msource;
905
872
    int inscnt;
906
873
    const unsigned char *ref_data, *ref_top, *data, *top;
908
875
    unsigned long source_size;
909
876
 
910
877
    if (!trg_buf || !trg_size)
911
 
        return DELTA_BUFFER_EMPTY;
 
878
        return NULL;
912
879
    if (index == NULL)
913
 
        return DELTA_INDEX_NEEDED;
 
880
        return NULL;
914
881
 
915
882
    outpos = 0;
916
883
    outsize = 8192;
918
885
        outsize = max_size + MAX_OP_SIZE + 1;
919
886
    out = malloc(outsize);
920
887
    if (!out)
921
 
        return DELTA_OUT_OF_MEMORY;
 
888
        return NULL;
922
889
 
923
890
    source_size = index->last_src->size + index->last_src->agg_offset;
924
891
 
971
938
                 entry++) {
972
939
                const unsigned char *ref;
973
940
                const unsigned char *src;
974
 
                int ref_size;
 
941
                unsigned int ref_size;
975
942
                if (entry->val != val)
976
943
                    continue;
977
944
                ref = entry->ptr;
984
951
                 * match more bytes with this location that we have already
985
952
                 * matched.
986
953
                 */
987
 
                if (ref_size > (top - src))
 
954
                if (ref_size > top - src)
988
955
                    ref_size = top - src;
989
956
                if (ref_size <= msize)
990
957
                    break;
991
958
                /* See how many bytes actually match at this location. */
992
959
                while (ref_size-- && *src++ == *ref)
993
960
                    ref++;
994
 
                if (msize < (ref - entry->ptr)) {
 
961
                if (msize < ref - entry->ptr) {
995
962
                    /* this is our best match so far */
996
963
                    msize = ref - entry->ptr;
997
964
                    msource = entry->src;
1097
1064
            out = realloc(out, outsize);
1098
1065
            if (!out) {
1099
1066
                free(tmp);
1100
 
                return DELTA_OUT_OF_MEMORY;
 
1067
                return NULL;
1101
1068
            }
1102
1069
        }
1103
1070
    }
1107
1074
 
1108
1075
    if (max_size && outpos > max_size) {
1109
1076
        free(out);
1110
 
        return DELTA_SIZE_TOO_BIG;
 
1077
        return NULL;
1111
1078
    }
1112
1079
 
1113
1080
    *delta_size = outpos;
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;
 
1081
    return out;
1185
1082
}
1186
1083
 
1187
1084
/* vim: et ts=4 sw=4 sts=4