← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/diff-delta.c

  • Committer: Jonathan Riddell
  • Date: 2011-05-16 10:05:25 UTC
  • mto: This revision was merged to the branch mainline in revision 5869.
  • Revision ID: jriddell@canonical.com-20110516100525-7q23m5opdnl4qg41
start adding licences

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)
376
380
{
377
381
    unsigned int i, hsize, hmask, num_entries, prev_val, *hash_count;
378
382
    unsigned int total_num_entries;
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
408
412
          sizeof(*entry) * total_num_entries;
409
413
    mem = malloc(memsize);
410
414
    if (!mem)
411
 
        return NULL;
 
415
        return DELTA_OUT_OF_MEMORY;
412
416
    hash = mem;
413
417
    mem = hash + hsize;
414
418
    entry = mem;
419
423
    hash_count = calloc(hsize, sizeof(*hash_count));
420
424
    if (!hash_count) {
421
425
        free(hash);
422
 
        return NULL;
 
426
        return DELTA_OUT_OF_MEMORY;
423
427
    }
424
428
 
425
429
    /* then populate the index for the new data */
450
454
    total_num_entries = limit_hash_buckets(hash, hash_count, hsize,
451
455
                                           total_num_entries);
452
456
    free(hash_count);
453
 
    if (old) {
454
 
        old->last_src = src;
455
 
    }
456
457
    index = pack_delta_index(hash, hsize, total_num_entries, old);
457
458
    free(hash);
 
459
    /* pack_delta_index only returns NULL on malloc failure */
458
460
    if (!index) {
459
 
        return NULL;
 
461
        return DELTA_OUT_OF_MEMORY;
460
462
    }
461
463
    index->last_src = src;
462
 
    return index;
 
464
    *fresh = index;
 
465
    return DELTA_OK;
463
466
}
464
467
 
465
468
/* Take some entries, and put them into a custom hash.
679
682
    }
680
683
}
681
684
 
682
 
struct delta_index *
 
685
delta_result
683
686
create_delta_index_from_delta(const struct source_info *src,
684
 
                              struct delta_index *old_index)
 
687
                              struct delta_index *old_index,
 
688
                              struct delta_index **fresh)
685
689
{
686
690
    unsigned int i, num_entries, max_num_entries, prev_val, num_inserted;
687
691
    unsigned int hash_offset;
690
694
    struct delta_index *new_index;
691
695
    struct index_entry *entry, *entries;
692
696
 
 
697
    if (!old_index)
 
698
        return DELTA_INDEX_NEEDED;
693
699
    if (!src->buf || !src->size)
694
 
        return NULL;
 
700
        return DELTA_SOURCE_EMPTY;
695
701
    buffer = src->buf;
696
702
    top = buffer + src->size;
697
703
 
707
713
    /* allocate an array to hold whatever entries we find */
708
714
    entries = malloc(sizeof(*entry) * max_num_entries);
709
715
    if (!entries) /* malloc failure */
710
 
        return NULL;
 
716
        return DELTA_OUT_OF_MEMORY;
711
717
 
712
718
    /* then populate the index for the new data */
713
719
    prev_val = ~0;
774
780
        }
775
781
    }
776
782
    if (data != top) {
777
 
        /* Something was wrong with this delta */
 
783
        /* The source_info data passed was corrupted or otherwise invalid */
778
784
        free(entries);
779
 
        return NULL;
 
785
        return DELTA_SOURCE_BAD;
780
786
    }
781
787
    if (num_entries == 0) {
782
788
        /** Nothing to index **/
783
789
        free(entries);
784
 
        return NULL;
 
790
        *fresh = old_index;
 
791
        return DELTA_OK;
785
792
    }
786
 
    assert(old_index != NULL);
787
793
    old_index->last_src = src;
788
794
    /* See if we can fill in these values into the holes in the array */
789
795
    entry = entries;
841
847
        new_index = create_index_from_old_and_new_entries(old_index,
842
848
            entry, num_entries);
843
849
    } else {
844
 
        new_index = NULL;
 
850
        new_index = old_index;
845
851
        // fprintf(stderr, "inserted %d without resizing\n", num_inserted);
846
852
    }
847
853
    free(entries);
848
 
    return new_index;
 
854
    /* create_index_from_old_and_new_entries returns NULL on malloc failure */
 
855
    if (!new_index)
 
856
        return DELTA_OUT_OF_MEMORY;
 
857
    *fresh = new_index;
 
858
    return DELTA_OK;
849
859
}
850
860
 
851
861
void free_delta_index(struct delta_index *index)
853
863
    free(index);
854
864
}
855
865
 
856
 
unsigned long sizeof_delta_index(struct delta_index *index)
 
866
unsigned long
 
867
sizeof_delta_index(struct delta_index *index)
857
868
{
858
869
    if (index)
859
870
        return index->memsize;
867
878
 */
868
879
#define MAX_OP_SIZE (5 + 5 + 1 + RABIN_WINDOW + 7)
869
880
 
870
 
void *
 
881
delta_result
871
882
create_delta(const struct delta_index *index,
872
883
             const void *trg_buf, unsigned long trg_size,
873
 
             unsigned long *delta_size, unsigned long max_size)
 
884
             unsigned long *delta_size, unsigned long max_size,
 
885
             void **delta_data)
874
886
{
875
 
    unsigned int i, outpos, outsize, moff, msize, val;
 
887
    unsigned int i, outpos, outsize, moff, val;
 
888
    int msize;
876
889
    const struct source_info *msource;
877
890
    int inscnt;
878
891
    const unsigned char *ref_data, *ref_top, *data, *top;
880
893
    unsigned long source_size;
881
894
 
882
895
    if (!trg_buf || !trg_size)
883
 
        return NULL;
 
896
        return DELTA_BUFFER_EMPTY;
884
897
    if (index == NULL)
885
 
        return NULL;
 
898
        return DELTA_INDEX_NEEDED;
886
899
 
887
900
    outpos = 0;
888
901
    outsize = 8192;
890
903
        outsize = max_size + MAX_OP_SIZE + 1;
891
904
    out = malloc(outsize);
892
905
    if (!out)
893
 
        return NULL;
 
906
        return DELTA_OUT_OF_MEMORY;
894
907
 
895
908
    source_size = index->last_src->size + index->last_src->agg_offset;
896
909
 
943
956
                 entry++) {
944
957
                const unsigned char *ref;
945
958
                const unsigned char *src;
946
 
                unsigned int ref_size;
 
959
                int ref_size;
947
960
                if (entry->val != val)
948
961
                    continue;
949
962
                ref = entry->ptr;
956
969
                 * match more bytes with this location that we have already
957
970
                 * matched.
958
971
                 */
959
 
                if (ref_size > top - src)
 
972
                if (ref_size > (top - src))
960
973
                    ref_size = top - src;
961
974
                if (ref_size <= msize)
962
975
                    break;
963
976
                /* See how many bytes actually match at this location. */
964
977
                while (ref_size-- && *src++ == *ref)
965
978
                    ref++;
966
 
                if (msize < ref - entry->ptr) {
 
979
                if (msize < (ref - entry->ptr)) {
967
980
                    /* this is our best match so far */
968
981
                    msize = ref - entry->ptr;
969
982
                    msource = entry->src;
1069
1082
            out = realloc(out, outsize);
1070
1083
            if (!out) {
1071
1084
                free(tmp);
1072
 
                return NULL;
 
1085
                return DELTA_OUT_OF_MEMORY;
1073
1086
            }
1074
1087
        }
1075
1088
    }
1079
1092
 
1080
1093
    if (max_size && outpos > max_size) {
1081
1094
        free(out);
1082
 
        return NULL;
 
1095
        return DELTA_SIZE_TOO_BIG;
1083
1096
    }
1084
1097
 
1085
1098
    *delta_size = outpos;
1086
 
    return out;
 
1099
    *delta_data = out;
 
1100
    return DELTA_OK;
1087
1101
}
1088
1102
 
1089
1103
/* vim: et ts=4 sw=4 sts=4