← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/diff-delta.c

  • Committer: Richard Wilbur
  • Date: 2016-02-04 19:07:28 UTC
  • mto: This revision was merged to the branch mainline in revision 6618.
  • Revision ID: richard.wilbur@gmail.com-20160204190728-p0zvfii6zase0fw7
Update COPYING.txt from the original http://www.gnu.org/licenses/gpl-2.0.txt  (Only differences were in whitespace.)  Thanks to Petr Stodulka for pointing out the discrepancy.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/diff-delta.c
376
376
delta_result
377
377
create_delta_index(const struct source_info *src,
378
378
                   struct delta_index *old,
379
 
                   struct delta_index **fresh)
 
379
                   struct delta_index **fresh,
 
380
                   int max_bytes_to_index)
380
381
{
381
382
    unsigned int i, hsize, hmask, num_entries, prev_val, *hash_count;
382
 
    unsigned int total_num_entries;
 
383
    unsigned int total_num_entries, stride, max_entries;
383
384
    const unsigned char *data, *buffer;
384
385
    struct delta_index *index;
385
386
    struct unpacked_index_entry *entry, **hash;
391
392
    buffer = src->buf;
392
393
 
393
394
    /* Determine index hash size.  Note that indexing skips the
394
 
       first byte to allow for optimizing the Rabin's polynomial
395
 
       initialization in create_delta(). */
 
395
       first byte so we subtract 1 to get the edge cases right.
 
396
     */
 
397
    stride = RABIN_WINDOW;
396
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
    }
397
409
    if (old != NULL)
398
410
        total_num_entries = num_entries + old->num_entries;
399
411
    else
428
440
 
429
441
    /* then populate the index for the new data */
430
442
    prev_val = ~0;
431
 
    for (data = buffer + num_entries * RABIN_WINDOW - RABIN_WINDOW;
 
443
    for (data = buffer + num_entries * stride - RABIN_WINDOW;
432
444
         data >= buffer;
433
 
         data -= RABIN_WINDOW) {
 
445
         data -= stride) {
434
446
        unsigned int val = 0;
435
447
        for (i = 1; i <= RABIN_WINDOW; i++)
436
448
            val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
476
488
                       unsigned int hsize)
477
489
{
478
490
    unsigned int hash_offset, hmask, memsize;
479
 
    struct index_entry *entry, *last_entry;
 
491
    struct index_entry *entry;
480
492
    struct index_entry_linked_list *out_entry, **hash;
481
493
    void *mem;
482
494
 
496
508
    /* We know that entries are in the order we want in the output, but they
497
509
     * aren't "grouped" by hash bucket yet.
498
510
     */
499
 
    last_entry = entries + num_entries;
500
511
    for (entry = entries + num_entries - 1; entry >= entries; --entry) {
501
512
        hash_offset = entry->val & hmask;
502
513
        out_entry->p_entry = entry;
521
532
    unsigned int i, j, hsize, hmask, total_num_entries;
522
533
    struct delta_index *index;
523
534
    struct index_entry *entry, *packed_entry, **packed_hash;
524
 
    struct index_entry *last_entry, null_entry = {0};
 
535
    struct index_entry null_entry = {0};
525
536
    void *mem;
526
537
    unsigned long memsize;
527
538
    struct index_entry_linked_list *unpacked_entry, **mini_hash;
572
583
        free(index);
573
584
        return NULL;
574
585
    }
575
 
    last_entry = entries + num_entries;
576
586
    for (i = 0; i < hsize; i++) {
577
587
        /*
578
588
         * Coalesce all entries belonging in one hash bucket
710
720
 
711
721
    max_num_entries = (src->size - 1)  / RABIN_WINDOW;
712
722
 
 
723
    if (!max_num_entries) {
 
724
        *fresh = old_index;
 
725
        return DELTA_OK;
 
726
    }
 
727
 
713
728
    /* allocate an array to hold whatever entries we find */
714
729
    entries = malloc(sizeof(*entry) * max_num_entries);
715
730
    if (!entries) /* malloc failure */
1100
1115
    return DELTA_OK;
1101
1116
}
1102
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;
 
1185
}
 
1186
 
1103
1187
/* vim: et ts=4 sw=4 sts=4
1104
1188
 */