← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to diff-delta.c

  • Committer: John Arbash Meinel
  • Date: 2009-03-02 18:52:36 UTC
  • mto: (0.17.31 trunk)
  • mto: This revision was merged to the branch mainline in revision 4280.
  • Revision ID: john@arbash-meinel.com-20090302185236-gm5ckgaic13q6vvs
Change the code so that we can pass in multiple sources to match against.
At the moment, we only use a single source, but that will soon change.

Show diffs side-by-side

added added

removed removed

Lines of Context:
diff-delta.c
123
123
};
124
124
 
125
125
struct delta_index {
126
 
        unsigned long memsize;
127
 
        const void *src_buf;
128
 
        unsigned long src_size;
129
 
        unsigned int hash_mask;
 
126
        unsigned long memsize; /* Total bytes pointed to by this index */
 
127
        const void *src_buf; /* Pointer to the beginning of source data */
 
128
        unsigned long src_size; /* Total length of source data */
 
129
        unsigned long agg_src_offset; /* Start of source data as part of the
 
130
                                                                         aggregate source */
 
131
        unsigned int hash_mask; /* val & hash_mask gives the hash index for a given
 
132
                                                           entry */
130
133
        struct index_entry *hash[];
131
134
};
132
135
 
133
 
struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
 
136
struct delta_index * create_delta_index(const void *buf, unsigned long bufsize,
 
137
                                                                                unsigned long agg_src_offset)
134
138
{
135
139
        unsigned int i, hsize, hmask, entries, prev_val, *hash_count;
136
140
        const unsigned char *data, *buffer = buf;
174
178
        /* then populate the index */
175
179
        prev_val = ~0;
176
180
        for (data = buffer + entries * RABIN_WINDOW - RABIN_WINDOW;
177
 
             data >= buffer;
178
 
             data -= RABIN_WINDOW) {
 
181
                 data >= buffer;
 
182
                 data -= RABIN_WINDOW) {
179
183
                unsigned int val = 0;
180
184
                for (i = 1; i <= RABIN_WINDOW; i++)
181
185
                        val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
196
200
 
197
201
        /*
198
202
         * Determine a limit on the number of entries in the same hash
199
 
         * bucket.  This guards us against pathological data sets causing
 
203
         * bucket.      This guards us against pathological data sets causing
200
204
         * really bad hash distribution with most entries in the same hash
201
205
         * bucket that would bring us to O(m*n) computing costs (m and n
202
206
         * corresponding to reference and target buffer sizes).
221
225
                /*
222
226
                 * Assume that this loop is gone through exactly
223
227
                 * HASH_LIMIT times and is entered and left with
224
 
                 * acc==0.  So the first statement in the loop
 
228
                 * acc==0.      So the first statement in the loop
225
229
                 * contributes (hash_count[i]-HASH_LIMIT)*HASH_LIMIT
226
230
                 * to the accumulator, and the inner loop consequently
227
231
                 * is run (hash_count[i]-HASH_LIMIT) times, removing
262
266
        index->memsize = memsize;
263
267
        index->src_buf = buf;
264
268
        index->src_size = bufsize;
 
269
        index->agg_src_offset = agg_src_offset;
265
270
        index->hash_mask = hmask;
266
271
 
267
272
        mem = index->hash;
308
313
#define MAX_OP_SIZE     (5 + 5 + 1 + RABIN_WINDOW + 7)
309
314
 
310
315
void *
311
 
create_delta(const struct delta_index *index,
312
 
             const void *trg_buf, unsigned long trg_size,
313
 
             unsigned long *delta_size, unsigned long max_size)
 
316
create_delta(struct delta_index **indexes,
 
317
                         unsigned int num_indexes,
 
318
                         const void *trg_buf, unsigned long trg_size,
 
319
                         unsigned long *delta_size, unsigned long max_size)
314
320
{
315
 
        unsigned int i, outpos, outsize, moff, msize, val;
 
321
        unsigned int i, j, outpos, outsize, moff, msize, val;
 
322
        const struct delta_index *index, *mindex;
316
323
        int inscnt;
317
324
        const unsigned char *ref_data, *ref_top, *data, *top;
318
325
        unsigned char *out;
329
336
                return NULL;
330
337
 
331
338
        /* store reference buffer size */
332
 
        i = index->src_size;
 
339
        i = 0;
 
340
        for (j = 0; j < num_indexes; ++j) {
 
341
                index = indexes[j];
 
342
                i += index->src_size;
 
343
        }
333
344
        while (i >= 0x80) {
334
345
                out[outpos++] = i | 0x80;
335
346
                i >>= 7;
344
355
        }
345
356
        out[outpos++] = i;
346
357
 
347
 
        ref_data = index->src_buf;
348
 
        ref_top = ref_data + index->src_size;
349
358
        data = trg_buf;
350
359
        top = (const unsigned char *) trg_buf + trg_size;
351
360
 
352
 
        outpos++;
 
361
        /* Start the matching by filling out with a simple 'insert' instruction, of
 
362
         * the first RABIN_WINDOW bytes of the input.
 
363
         */
 
364
        outpos++; /* leave a byte for the insert command */
353
365
        val = 0;
354
366
        for (i = 0; i < RABIN_WINDOW && data < top; i++, data++) {
355
367
                out[outpos++] = *data;
356
368
                val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];
357
369
        }
 
370
        /* we are now setup with an insert of 'i' bytes and val contains the RABIN
 
371
         * hash for those bytes, and data points to the RABIN_WINDOW+1 byte of
 
372
         * input.
 
373
         */
358
374
        inscnt = i;
359
375
 
360
376
        moff = 0;
361
377
        msize = 0;
 
378
        mindex = NULL;
362
379
        while (data < top) {
363
380
                if (msize < 4096) {
 
381
                        /* we don't have a 'worthy enough' match yet, so let's look for
 
382
                         * one.
 
383
                         */
364
384
                        struct index_entry *entry;
 
385
                        /* Shift the window by one byte. */
365
386
                        val ^= U[data[-RABIN_WINDOW]];
366
387
                        val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];
367
 
                        i = val & index->hash_mask;
368
 
                        for (entry = index->hash[i]; entry < index->hash[i+1]; entry++) {
369
 
                                const unsigned char *ref = entry->ptr;
370
 
                                const unsigned char *src = data;
371
 
                                unsigned int ref_size = ref_top - ref;
372
 
                                if (entry->val != val)
373
 
                                        continue;
374
 
                                if (ref_size > top - src)
375
 
                                        ref_size = top - src;
376
 
                                if (ref_size <= msize)
377
 
                                        break;
378
 
                                while (ref_size-- && *src++ == *ref)
379
 
                                        ref++;
380
 
                                if (msize < ref - entry->ptr) {
381
 
                                        /* this is our best match so far */
382
 
                                        msize = ref - entry->ptr;
383
 
                                        moff = entry->ptr - ref_data;
384
 
                                        if (msize >= 4096) /* good enough */
 
388
                        for (j = 0; j < num_indexes; ++j) {
 
389
                                index = indexes[j];
 
390
                                i = val & index->hash_mask;
 
391
                                ref_top = index->src_buf + index->src_size;
 
392
                                ref_data = index->src_buf;
 
393
                                for (entry = index->hash[i]; entry < index->hash[i+1];
 
394
                                         entry++) {
 
395
                                        const unsigned char *ref = entry->ptr;
 
396
                                        const unsigned char *src = data;
 
397
                                        unsigned int ref_size = ref_top - ref;
 
398
                                        if (entry->val != val)
 
399
                                                continue;
 
400
                                        /* ref_size is the longest possible match that we could make
 
401
                                         * here. If ref_size <= msize, then we know that we cannot
 
402
                                         * match more bytes with this location that we have already
 
403
                                         * matched.
 
404
                                         */
 
405
                                        if (ref_size > top - src)
 
406
                                                ref_size = top - src;
 
407
                                        if (ref_size <= msize)
385
408
                                                break;
 
409
                                        /* See how many bytes actually match at this location. */
 
410
                                        while (ref_size-- && *src++ == *ref)
 
411
                                                ref++;
 
412
                                        if (msize < ref - entry->ptr) {
 
413
                                                /* this is our best match so far */
 
414
                                                msize = ref - entry->ptr;
 
415
                                                moff = entry->ptr - ref_data;
 
416
                                                mindex = index;
 
417
                                                if (msize >= 4096) /* good enough */
 
418
                                                        break;
 
419
                                        }
386
420
                                }
387
421
                        }
388
422
                }
389
423
 
390
424
                if (msize < 4) {
 
425
                        /* The best match right now is less than 4 bytes long. So just add
 
426
                         * the current byte to the insert instruction. Increment the insert
 
427
                         * counter, and copy the byte of data into the output buffer.
 
428
                         */
391
429
                        if (!inscnt)
392
430
                                outpos++;
393
431
                        out[outpos++] = *data++;
394
432
                        inscnt++;
395
433
                        if (inscnt == 0x7f) {
 
434
                                /* We have a max length insert instruction, finalize it in the
 
435
                                 * output.
 
436
                                 */
396
437
                                out[outpos - inscnt - 1] = inscnt;
397
438
                                inscnt = 0;
398
439
                        }
402
443
                        unsigned char *op;
403
444
 
404
445
                        if (inscnt) {
 
446
                                ref_data = mindex->src_buf;
405
447
                                while (moff && ref_data[moff-1] == data[-1]) {
406
448
                                        /* we can match one byte back */
407
449
                                        msize++;
425
467
                        op = out + outpos++;
426
468
                        i = 0x80;
427
469
 
 
470
                        /* so far, moff has been the offset in a single source, however,
 
471
                         * now we encode it as the offset in the aggregate source
 
472
                         */
 
473
                        moff = moff + mindex->agg_src_offset;
428
474
                        if (moff & 0x000000ff)
429
475
                                out[outpos++] = moff >> 0,  i |= 0x01;
430
476
                        if (moff & 0x0000ff00)
450
496
                                val = 0;
451
497
                                for (j = -RABIN_WINDOW; j < 0; j++)
452
498
                                        val = ((val << 8) | data[j])
453
 
                                              ^ T[val >> RABIN_SHIFT];
 
499
                                                  ^ T[val >> RABIN_SHIFT];
454
500
                        }
455
501
                }
456
502
 
480
526
        *delta_size = outpos;
481
527
        return out;
482
528
}
 
529
 
 
530
/* vim: noet ts=4 sw=4 sts=4 */