Andrew's git - gitweb.git/blob

   1/*
   2 * diff-delta.c: generate a delta between two buffers
   3 *
   4 *  Many parts of this file have been lifted from LibXDiff version 0.10.
   5 *  http://www.xmailserver.org/xdiff-lib.html
   6 *
   7 *  LibXDiff was written by Davide Libenzi <davidel@xmailserver.org>
   8 *  Copyright (C) 2003  Davide Libenzi
   9 *
  10 *  Many mods for GIT usage by Nicolas Pitre <nico@cam.org>, (C) 2005.
  11 *
  12 *  This file is free software; you can redistribute it and/or
  13 *  modify it under the terms of the GNU Lesser General Public
  14 *  License as published by the Free Software Foundation; either
  15 *  version 2.1 of the License, or (at your option) any later version.
  16 *
  17 *  Use of this within git automatically means that the LGPL
  18 *  licensing gets turned into GPLv2 within this project.
  19 */
  20
  21#include <stdlib.h>
  22#include <string.h>
  23#include "delta.h"
  24
  25
  26/* maximum hash entry list for the same hash bucket */
  27#define HASH_LIMIT 64
  28
  29#define RABIN_SHIFT 23
  30#define RABIN_WINDOW 16
  31
  32static const unsigned int T[256] = {
  33        0x00000000, 0xab59b4d1, 0x56b369a2, 0xfdeadd73, 0x063f6795, 0xad66d344,
  34        0x508c0e37, 0xfbd5bae6, 0x0c7ecf2a, 0xa7277bfb, 0x5acda688, 0xf1941259,
  35        0x0a41a8bf, 0xa1181c6e, 0x5cf2c11d, 0xf7ab75cc, 0x18fd9e54, 0xb3a42a85,
  36        0x4e4ef7f6, 0xe5174327, 0x1ec2f9c1, 0xb59b4d10, 0x48719063, 0xe32824b2,
  37        0x1483517e, 0xbfdae5af, 0x423038dc, 0xe9698c0d, 0x12bc36eb, 0xb9e5823a,
  38        0x440f5f49, 0xef56eb98, 0x31fb3ca8, 0x9aa28879, 0x6748550a, 0xcc11e1db,
  39        0x37c45b3d, 0x9c9defec, 0x6177329f, 0xca2e864e, 0x3d85f382, 0x96dc4753,
  40        0x6b369a20, 0xc06f2ef1, 0x3bba9417, 0x90e320c6, 0x6d09fdb5, 0xc6504964,
  41        0x2906a2fc, 0x825f162d, 0x7fb5cb5e, 0xd4ec7f8f, 0x2f39c569, 0x846071b8,
  42        0x798aaccb, 0xd2d3181a, 0x25786dd6, 0x8e21d907, 0x73cb0474, 0xd892b0a5,
  43        0x23470a43, 0x881ebe92, 0x75f463e1, 0xdeadd730, 0x63f67950, 0xc8afcd81,
  44        0x354510f2, 0x9e1ca423, 0x65c91ec5, 0xce90aa14, 0x337a7767, 0x9823c3b6,
  45        0x6f88b67a, 0xc4d102ab, 0x393bdfd8, 0x92626b09, 0x69b7d1ef, 0xc2ee653e,
  46        0x3f04b84d, 0x945d0c9c, 0x7b0be704, 0xd05253d5, 0x2db88ea6, 0x86e13a77,
  47        0x7d348091, 0xd66d3440, 0x2b87e933, 0x80de5de2, 0x7775282e, 0xdc2c9cff,
  48        0x21c6418c, 0x8a9ff55d, 0x714a4fbb, 0xda13fb6a, 0x27f92619, 0x8ca092c8,
  49        0x520d45f8, 0xf954f129, 0x04be2c5a, 0xafe7988b, 0x5432226d, 0xff6b96bc,
  50        0x02814bcf, 0xa9d8ff1e, 0x5e738ad2, 0xf52a3e03, 0x08c0e370, 0xa39957a1,
  51        0x584ced47, 0xf3155996, 0x0eff84e5, 0xa5a63034, 0x4af0dbac, 0xe1a96f7d,
  52        0x1c43b20e, 0xb71a06df, 0x4ccfbc39, 0xe79608e8, 0x1a7cd59b, 0xb125614a,
  53        0x468e1486, 0xedd7a057, 0x103d7d24, 0xbb64c9f5, 0x40b17313, 0xebe8c7c2,
  54        0x16021ab1, 0xbd5bae60, 0x6cb54671, 0xc7ecf2a0, 0x3a062fd3, 0x915f9b02,
  55        0x6a8a21e4, 0xc1d39535, 0x3c394846, 0x9760fc97, 0x60cb895b, 0xcb923d8a,
  56        0x3678e0f9, 0x9d215428, 0x66f4eece, 0xcdad5a1f, 0x3047876c, 0x9b1e33bd,
  57        0x7448d825, 0xdf116cf4, 0x22fbb187, 0x89a20556, 0x7277bfb0, 0xd92e0b61,
  58        0x24c4d612, 0x8f9d62c3, 0x7836170f, 0xd36fa3de, 0x2e857ead, 0x85dcca7c,
  59        0x7e09709a, 0xd550c44b, 0x28ba1938, 0x83e3ade9, 0x5d4e7ad9, 0xf617ce08,
  60        0x0bfd137b, 0xa0a4a7aa, 0x5b711d4c, 0xf028a99d, 0x0dc274ee, 0xa69bc03f,
  61        0x5130b5f3, 0xfa690122, 0x0783dc51, 0xacda6880, 0x570fd266, 0xfc5666b7,
  62        0x01bcbbc4, 0xaae50f15, 0x45b3e48d, 0xeeea505c, 0x13008d2f, 0xb85939fe,
  63        0x438c8318, 0xe8d537c9, 0x153feaba, 0xbe665e6b, 0x49cd2ba7, 0xe2949f76,
  64        0x1f7e4205, 0xb427f6d4, 0x4ff24c32, 0xe4abf8e3, 0x19412590, 0xb2189141,
  65        0x0f433f21, 0xa41a8bf0, 0x59f05683, 0xf2a9e252, 0x097c58b4, 0xa225ec65,
  66        0x5fcf3116, 0xf49685c7, 0x033df00b, 0xa86444da, 0x558e99a9, 0xfed72d78,
  67        0x0502979e, 0xae5b234f, 0x53b1fe3c, 0xf8e84aed, 0x17bea175, 0xbce715a4,
  68        0x410dc8d7, 0xea547c06, 0x1181c6e0, 0xbad87231, 0x4732af42, 0xec6b1b93,
  69        0x1bc06e5f, 0xb099da8e, 0x4d7307fd, 0xe62ab32c, 0x1dff09ca, 0xb6a6bd1b,
  70        0x4b4c6068, 0xe015d4b9, 0x3eb80389, 0x95e1b758, 0x680b6a2b, 0xc352defa,
  71        0x3887641c, 0x93ded0cd, 0x6e340dbe, 0xc56db96f, 0x32c6cca3, 0x999f7872,
  72        0x6475a501, 0xcf2c11d0, 0x34f9ab36, 0x9fa01fe7, 0x624ac294, 0xc9137645,
  73        0x26459ddd, 0x8d1c290c, 0x70f6f47f, 0xdbaf40ae, 0x207afa48, 0x8b234e99,
  74        0x76c993ea, 0xdd90273b, 0x2a3b52f7, 0x8162e626, 0x7c883b55, 0xd7d18f84,
  75        0x2c043562, 0x875d81b3, 0x7ab75cc0, 0xd1eee811
  76};
  77
  78static const unsigned int U[256] = {
  79        0x00000000, 0x7eb5200d, 0x5633f4cb, 0x2886d4c6, 0x073e5d47, 0x798b7d4a,
  80        0x510da98c, 0x2fb88981, 0x0e7cba8e, 0x70c99a83, 0x584f4e45, 0x26fa6e48,
  81        0x0942e7c9, 0x77f7c7c4, 0x5f711302, 0x21c4330f, 0x1cf9751c, 0x624c5511,
  82        0x4aca81d7, 0x347fa1da, 0x1bc7285b, 0x65720856, 0x4df4dc90, 0x3341fc9d,
  83        0x1285cf92, 0x6c30ef9f, 0x44b63b59, 0x3a031b54, 0x15bb92d5, 0x6b0eb2d8,
  84        0x4388661e, 0x3d3d4613, 0x39f2ea38, 0x4747ca35, 0x6fc11ef3, 0x11743efe,
  85        0x3eccb77f, 0x40799772, 0x68ff43b4, 0x164a63b9, 0x378e50b6, 0x493b70bb,
  86        0x61bda47d, 0x1f088470, 0x30b00df1, 0x4e052dfc, 0x6683f93a, 0x1836d937,
  87        0x250b9f24, 0x5bbebf29, 0x73386bef, 0x0d8d4be2, 0x2235c263, 0x5c80e26e,
  88        0x740636a8, 0x0ab316a5, 0x2b7725aa, 0x55c205a7, 0x7d44d161, 0x03f1f16c,
  89        0x2c4978ed, 0x52fc58e0, 0x7a7a8c26, 0x04cfac2b, 0x73e5d470, 0x0d50f47d,
  90        0x25d620bb, 0x5b6300b6, 0x74db8937, 0x0a6ea93a, 0x22e87dfc, 0x5c5d5df1,
  91        0x7d996efe, 0x032c4ef3, 0x2baa9a35, 0x551fba38, 0x7aa733b9, 0x041213b4,
  92        0x2c94c772, 0x5221e77f, 0x6f1ca16c, 0x11a98161, 0x392f55a7, 0x479a75aa,
  93        0x6822fc2b, 0x1697dc26, 0x3e1108e0, 0x40a428ed, 0x61601be2, 0x1fd53bef,
  94        0x3753ef29, 0x49e6cf24, 0x665e46a5, 0x18eb66a8, 0x306db26e, 0x4ed89263,
  95        0x4a173e48, 0x34a21e45, 0x1c24ca83, 0x6291ea8e, 0x4d29630f, 0x339c4302,
  96        0x1b1a97c4, 0x65afb7c9, 0x446b84c6, 0x3adea4cb, 0x1258700d, 0x6ced5000,
  97        0x4355d981, 0x3de0f98c, 0x15662d4a, 0x6bd30d47, 0x56ee4b54, 0x285b6b59,
  98        0x00ddbf9f, 0x7e689f92, 0x51d01613, 0x2f65361e, 0x07e3e2d8, 0x7956c2d5,
  99        0x5892f1da, 0x2627d1d7, 0x0ea10511, 0x7014251c, 0x5facac9d, 0x21198c90,
 100        0x099f5856, 0x772a785b, 0x4c921c31, 0x32273c3c, 0x1aa1e8fa, 0x6414c8f7,
 101        0x4bac4176, 0x3519617b, 0x1d9fb5bd, 0x632a95b0, 0x42eea6bf, 0x3c5b86b2,
 102        0x14dd5274, 0x6a687279, 0x45d0fbf8, 0x3b65dbf5, 0x13e30f33, 0x6d562f3e,
 103        0x506b692d, 0x2ede4920, 0x06589de6, 0x78edbdeb, 0x5755346a, 0x29e01467,
 104        0x0166c0a1, 0x7fd3e0ac, 0x5e17d3a3, 0x20a2f3ae, 0x08242768, 0x76910765,
 105        0x59298ee4, 0x279caee9, 0x0f1a7a2f, 0x71af5a22, 0x7560f609, 0x0bd5d604,
 106        0x235302c2, 0x5de622cf, 0x725eab4e, 0x0ceb8b43, 0x246d5f85, 0x5ad87f88,
 107        0x7b1c4c87, 0x05a96c8a, 0x2d2fb84c, 0x539a9841, 0x7c2211c0, 0x029731cd,
 108        0x2a11e50b, 0x54a4c506, 0x69998315, 0x172ca318, 0x3faa77de, 0x411f57d3,
 109        0x6ea7de52, 0x1012fe5f, 0x38942a99, 0x46210a94, 0x67e5399b, 0x19501996,
 110        0x31d6cd50, 0x4f63ed5d, 0x60db64dc, 0x1e6e44d1, 0x36e89017, 0x485db01a,
 111        0x3f77c841, 0x41c2e84c, 0x69443c8a, 0x17f11c87, 0x38499506, 0x46fcb50b,
 112        0x6e7a61cd, 0x10cf41c0, 0x310b72cf, 0x4fbe52c2, 0x67388604, 0x198da609,
 113        0x36352f88, 0x48800f85, 0x6006db43, 0x1eb3fb4e, 0x238ebd5d, 0x5d3b9d50,
 114        0x75bd4996, 0x0b08699b, 0x24b0e01a, 0x5a05c017, 0x728314d1, 0x0c3634dc,
 115        0x2df207d3, 0x534727de, 0x7bc1f318, 0x0574d315, 0x2acc5a94, 0x54797a99,
 116        0x7cffae5f, 0x024a8e52, 0x06852279, 0x78300274, 0x50b6d6b2, 0x2e03f6bf,
 117        0x01bb7f3e, 0x7f0e5f33, 0x57888bf5, 0x293dabf8, 0x08f998f7, 0x764cb8fa,
 118        0x5eca6c3c, 0x207f4c31, 0x0fc7c5b0, 0x7172e5bd, 0x59f4317b, 0x27411176,
 119        0x1a7c5765, 0x64c97768, 0x4c4fa3ae, 0x32fa83a3, 0x1d420a22, 0x63f72a2f,
 120        0x4b71fee9, 0x35c4dee4, 0x1400edeb, 0x6ab5cde6, 0x42331920, 0x3c86392d,
 121        0x133eb0ac, 0x6d8b90a1, 0x450d4467, 0x3bb8646a
 122};
 123
 124struct index_entry {
 125        const unsigned char *ptr;
 126        unsigned int val;
 127        struct index_entry *next;
 128};
 129
 130struct delta_index {
 131        const void *src_buf;
 132        unsigned long src_size;
 133        unsigned int hash_mask;
 134        struct index_entry *hash[0];
 135};
 136
 137struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
 138{
 139        unsigned int i, hsize, hmask, entries, *hash_count;
 140        const unsigned char *data, *buffer = buf;
 141        struct delta_index *index;
 142        struct index_entry *entry, **hash;
 143        void *mem;
 144
 145        if (!buf || !bufsize)
 146                return NULL;
 147
 148        /* Determine index hash size.  Note that indexing skips the
 149           first byte to allow for optimizing the rabin polynomial
 150           initialization in create_delta(). */
 151        entries = (bufsize - 1)  / RABIN_WINDOW;
 152        hsize = entries / 4;
 153        for (i = 4; (1 << i) < hsize && i < 31; i++);
 154        hsize = 1 << i;
 155        hmask = hsize - 1;
 156
 157        /* allocate lookup index */
 158        mem = malloc(sizeof(*index) +
 159                     sizeof(*hash) * hsize +
 160                     sizeof(*entry) * entries);
 161        if (!mem)
 162                return NULL;
 163        index = mem;
 164        mem = index + 1;
 165        hash = mem;
 166        mem = hash + hsize;
 167        entry = mem;
 168
 169        index->src_buf = buf;
 170        index->src_size = bufsize;
 171        index->hash_mask = hmask;
 172        memset(hash, 0, hsize * sizeof(*hash));
 173
 174        /* allocate an array to count hash entries */
 175        hash_count = calloc(hsize, sizeof(*hash_count));
 176        if (!hash_count) {
 177                free(index);
 178                return NULL;
 179        }
 180
 181        /* then populate the index */
 182        data = buffer + entries * RABIN_WINDOW - RABIN_WINDOW;
 183        while (data >= buffer) {
 184                unsigned int val = 0;
 185                for (i = 1; i <= RABIN_WINDOW; i++)
 186                        val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
 187                i = val & hmask;
 188                entry->ptr = data + RABIN_WINDOW;
 189                entry->val = val;
 190                entry->next = hash[i];
 191                hash[i] = entry++;
 192                hash_count[i]++;
 193                data -= RABIN_WINDOW;
 194        }
 195
 196        /*
 197         * Determine a limit on the number of entries in the same hash
 198         * bucket.  This guard us against patological data sets causing
 199         * really bad hash distribution with most entries in the same hash
 200         * bucket that would bring us to O(m*n) computing costs (m and n
 201         * corresponding to reference and target buffer sizes).
 202         *
 203         * Make sure none of the hash buckets has more entries than
 204         * we're willing to test.  Otherwise we cull the entry list
 205         * uniformly to still preserve a good repartition across
 206         * the reference buffer.
 207         */
 208        for (i = 0; i < hsize; i++) {
 209                if (hash_count[i] < HASH_LIMIT)
 210                        continue;
 211                entry = hash[i];
 212                do {
 213                        struct index_entry *keep = entry;
 214                        int skip = hash_count[i] / HASH_LIMIT / 2;
 215                        do {
 216                                entry = entry->next;
 217                        } while(--skip && entry);
 218                        keep->next = entry;
 219                } while(entry);
 220        }
 221        free(hash_count);
 222
 223        return index;
 224}
 225
 226void free_delta_index(struct delta_index *index)
 227{
 228        free(index);
 229}
 230
 231/*
 232 * The maximum size for any opcode sequence, including the initial header
 233 * plus rabin window plus biggest copy.
 234 */
 235#define MAX_OP_SIZE     (5 + 5 + 1 + RABIN_WINDOW + 7)
 236
 237void *
 238create_delta(const struct delta_index *index,
 239             const void *trg_buf, unsigned long trg_size,
 240             unsigned long *delta_size, unsigned long max_size)
 241{
 242        unsigned int i, outpos, outsize, val;
 243        int inscnt;
 244        const unsigned char *ref_data, *ref_top, *data, *top;
 245        unsigned char *out;
 246
 247        if (!trg_buf || !trg_size)
 248                return NULL;
 249
 250        outpos = 0;
 251        outsize = 8192;
 252        if (max_size && outsize >= max_size)
 253                outsize = max_size + MAX_OP_SIZE + 1;
 254        out = malloc(outsize);
 255        if (!out)
 256                return NULL;
 257
 258        /* store reference buffer size */
 259        i = index->src_size;
 260        while (i >= 0x80) {
 261                out[outpos++] = i | 0x80;
 262                i >>= 7;
 263        }
 264        out[outpos++] = i;
 265
 266        /* store target buffer size */
 267        i = trg_size;
 268        while (i >= 0x80) {
 269                out[outpos++] = i | 0x80;
 270                i >>= 7;
 271        }
 272        out[outpos++] = i;
 273
 274        ref_data = index->src_buf;
 275        ref_top = ref_data + index->src_size;
 276        data = trg_buf;
 277        top = trg_buf + trg_size;
 278
 279        outpos++;
 280        val = 0;
 281        for (i = 0; i < RABIN_WINDOW && data < top; i++, data++) {
 282                out[outpos++] = *data;
 283                val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];
 284        }
 285        inscnt = i;
 286
 287        while (data < top) {
 288                unsigned int moff = 0, msize = 0;
 289                struct index_entry *entry;
 290                val ^= U[data[-RABIN_WINDOW]];
 291                val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];
 292                i = val & index->hash_mask;
 293                for (entry = index->hash[i]; entry; entry = entry->next) {
 294                        const unsigned char *ref = entry->ptr;
 295                        const unsigned char *src = data;
 296                        unsigned int ref_size = ref_top - ref;
 297                        if (entry->val != val)
 298                                continue;
 299                        if (ref_size > top - src)
 300                                ref_size = top - src;
 301                        if (ref_size > 0x10000)
 302                                ref_size = 0x10000;
 303                        if (ref_size <= msize)
 304                                break;
 305                        while (ref_size-- && *src++ == *ref)
 306                                ref++;
 307                        if (msize < ref - entry->ptr) {
 308                                /* this is our best match so far */
 309                                msize = ref - entry->ptr;
 310                                moff = entry->ptr - ref_data;
 311                        }
 312                }
 313
 314                if (msize < 4) {
 315                        if (!inscnt)
 316                                outpos++;
 317                        out[outpos++] = *data++;
 318                        inscnt++;
 319                        if (inscnt == 0x7f) {
 320                                out[outpos - inscnt - 1] = inscnt;
 321                                inscnt = 0;
 322                        }
 323                } else {
 324                        unsigned char *op;
 325
 326                        if (msize >= RABIN_WINDOW) {
 327                                const unsigned char *sk;
 328                                sk = data + msize - RABIN_WINDOW;
 329                                val = 0;
 330                                for (i = 0; i < RABIN_WINDOW; i++)
 331                                        val = ((val << 8) | *sk++) ^ T[val >> RABIN_SHIFT];
 332                        } else {
 333                                const unsigned char *sk = data + 1;
 334                                for (i = 1; i < msize; i++) {
 335                                        val ^= U[sk[-RABIN_WINDOW]];
 336                                        val = ((val << 8) | *sk++) ^ T[val >> RABIN_SHIFT];
 337                                }
 338                        }
 339
 340                        if (inscnt) {
 341                                while (moff && ref_data[moff-1] == data[-1]) {
 342                                        if (msize == 0x10000)
 343                                                break;
 344                                        /* we can match one byte back */
 345                                        msize++;
 346                                        moff--;
 347                                        data--;
 348                                        outpos--;
 349                                        if (--inscnt)
 350                                                continue;
 351                                        outpos--;  /* remove count slot */
 352                                        inscnt--;  /* make it -1 */
 353                                        break;
 354                                }
 355                                out[outpos - inscnt - 1] = inscnt;
 356                                inscnt = 0;
 357                        }
 358
 359                        data += msize;
 360                        op = out + outpos++;
 361                        i = 0x80;
 362
 363                        if (moff & 0xff) { out[outpos++] = moff; i |= 0x01; }
 364                        moff >>= 8;
 365                        if (moff & 0xff) { out[outpos++] = moff; i |= 0x02; }
 366                        moff >>= 8;
 367                        if (moff & 0xff) { out[outpos++] = moff; i |= 0x04; }
 368                        moff >>= 8;
 369                        if (moff & 0xff) { out[outpos++] = moff; i |= 0x08; }
 370
 371                        if (msize & 0xff) { out[outpos++] = msize; i |= 0x10; }
 372                        msize >>= 8;
 373                        if (msize & 0xff) { out[outpos++] = msize; i |= 0x20; }
 374
 375                        *op = i;
 376                }
 377
 378                if (outpos >= outsize - MAX_OP_SIZE) {
 379                        void *tmp = out;
 380                        outsize = outsize * 3 / 2;
 381                        if (max_size && outsize >= max_size)
 382                                outsize = max_size + MAX_OP_SIZE + 1;
 383                        if (max_size && outpos > max_size)
 384                                break;
 385                        out = realloc(out, outsize);
 386                        if (!out) {
 387                                free(tmp);
 388                                return NULL;
 389                        }
 390                }
 391        }
 392
 393        if (inscnt)
 394                out[outpos - inscnt - 1] = inscnt;
 395
 396        if (max_size && outpos > max_size) {
 397                free(out);
 398                return NULL;
 399        }
 400
 401        *delta_size = outpos;
 402        return out;
 403}