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