/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: Martin Pool
  • Date: 2011-05-20 14:46:02 UTC
  • mto: This revision was merged to the branch mainline in revision 5923.
  • Revision ID: mbp@canonical.com-20110520144602-bqli0t6dj01gl0pv
Various pyflakes import fixes.

Some modules were used for subclassing or at module load time, so there is no
point loading them lazily.

Some were not imported when they should be.

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
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)
853
873
    free(index);
854
874
}
855
875
 
856
 
unsigned long sizeof_delta_index(struct delta_index *index)
 
876
unsigned long
 
877
sizeof_delta_index(struct delta_index *index)
857
878
{
858
879
    if (index)
859
880
        return index->memsize;
867
888
 */
868
889
#define MAX_OP_SIZE (5 + 5 + 1 + RABIN_WINDOW + 7)
869
890
 
870
 
void *
 
891
delta_result
871
892
create_delta(const struct delta_index *index,
872
893
             const void *trg_buf, unsigned long trg_size,
873
 
             unsigned long *delta_size, unsigned long max_size)
 
894
             unsigned long *delta_size, unsigned long max_size,
 
895
             void **delta_data)
874
896
{
875
 
    unsigned int i, outpos, outsize, moff, msize, val;
 
897
    unsigned int i, outpos, outsize, moff, val;
 
898
    int msize;
876
899
    const struct source_info *msource;
877
900
    int inscnt;
878
901
    const unsigned char *ref_data, *ref_top, *data, *top;
880
903
    unsigned long source_size;
881
904
 
882
905
    if (!trg_buf || !trg_size)
883
 
        return NULL;
 
906
        return DELTA_BUFFER_EMPTY;
884
907
    if (index == NULL)
885
 
        return NULL;
 
908
        return DELTA_INDEX_NEEDED;
886
909
 
887
910
    outpos = 0;
888
911
    outsize = 8192;
890
913
        outsize = max_size + MAX_OP_SIZE + 1;
891
914
    out = malloc(outsize);
892
915
    if (!out)
893
 
        return NULL;
 
916
        return DELTA_OUT_OF_MEMORY;
894
917
 
895
918
    source_size = index->last_src->size + index->last_src->agg_offset;
896
919
 
943
966
                 entry++) {
944
967
                const unsigned char *ref;
945
968
                const unsigned char *src;
946
 
                unsigned int ref_size;
 
969
                int ref_size;
947
970
                if (entry->val != val)
948
971
                    continue;
949
972
                ref = entry->ptr;
956
979
                 * match more bytes with this location that we have already
957
980
                 * matched.
958
981
                 */
959
 
                if (ref_size > top - src)
 
982
                if (ref_size > (top - src))
960
983
                    ref_size = top - src;
961
984
                if (ref_size <= msize)
962
985
                    break;
963
986
                /* See how many bytes actually match at this location. */
964
987
                while (ref_size-- && *src++ == *ref)
965
988
                    ref++;
966
 
                if (msize < ref - entry->ptr) {
 
989
                if (msize < (ref - entry->ptr)) {
967
990
                    /* this is our best match so far */
968
991
                    msize = ref - entry->ptr;
969
992
                    msource = entry->src;
1069
1092
            out = realloc(out, outsize);
1070
1093
            if (!out) {
1071
1094
                free(tmp);
1072
 
                return NULL;
 
1095
                return DELTA_OUT_OF_MEMORY;
1073
1096
            }
1074
1097
        }
1075
1098
    }
1079
1102
 
1080
1103
    if (max_size && outpos > max_size) {
1081
1104
        free(out);
1082
 
        return NULL;
 
1105
        return DELTA_SIZE_TOO_BIG;
1083
1106
    }
1084
1107
 
1085
1108
    *delta_size = outpos;
1086
 
    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;
1087
1180
}
1088
1181
 
1089
1182
/* vim: et ts=4 sw=4 sts=4