diff-delta.con commit khash: rename oid helper functions (e465e7c)
   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        if (!trg_buf || !trg_size)
 330                return NULL;
 331
 332        outpos = 0;
 333        outsize = 8192;
 334        if (max_size && outsize >= max_size)
 335                outsize = max_size + MAX_OP_SIZE + 1;
 336        out = malloc(outsize);
 337        if (!out)
 338                return NULL;
 339
 340        /* store reference buffer size */
 341        l = index->src_size;
 342        while (l >= 0x80) {
 343                out[outpos++] = l | 0x80;
 344                l >>= 7;
 345        }
 346        out[outpos++] = l;
 347
 348        /* store target buffer size */
 349        l = trg_size;
 350        while (l >= 0x80) {
 351                out[outpos++] = l | 0x80;
 352                l >>= 7;
 353        }
 354        out[outpos++] = l;
 355
 356        ref_data = index->src_buf;
 357        ref_top = ref_data + index->src_size;
 358        data = trg_buf;
 359        top = (const unsigned char *) trg_buf + trg_size;
 360
 361        outpos++;
 362        val = 0;
 363        for (i = 0; i < RABIN_WINDOW && data < top; i++, data++) {
 364                out[outpos++] = *data;
 365                val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];
 366        }
 367        inscnt = i;
 368
 369        moff = 0;
 370        msize = 0;
 371        while (data < top) {
 372                if (msize < 4096) {
 373                        struct index_entry *entry;
 374                        val ^= U[data[-RABIN_WINDOW]];
 375                        val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];
 376                        i = val & index->hash_mask;
 377                        for (entry = index->hash[i]; entry < index->hash[i+1]; entry++) {
 378                                const unsigned char *ref = entry->ptr;
 379                                const unsigned char *src = data;
 380                                unsigned int ref_size = ref_top - ref;
 381                                if (entry->val != val)
 382                                        continue;
 383                                if (ref_size > top - src)
 384                                        ref_size = top - src;
 385                                if (ref_size <= msize)
 386                                        break;
 387                                while (ref_size-- && *src++ == *ref)
 388                                        ref++;
 389                                if (msize < ref - entry->ptr) {
 390                                        /* this is our best match so far */
 391                                        msize = ref - entry->ptr;
 392                                        moff = entry->ptr - ref_data;
 393                                        if (msize >= 4096) /* good enough */
 394                                                break;
 395                                }
 396                        }
 397                }
 398
 399                if (msize < 4) {
 400                        if (!inscnt)
 401                                outpos++;
 402                        out[outpos++] = *data++;
 403                        inscnt++;
 404                        if (inscnt == 0x7f) {
 405                                out[outpos - inscnt - 1] = inscnt;
 406                                inscnt = 0;
 407                        }
 408                        msize = 0;
 409                } else {
 410                        unsigned int left;
 411                        unsigned char *op;
 412
 413                        if (inscnt) {
 414                                while (moff && ref_data[moff-1] == data[-1]) {
 415                                        /* we can match one byte back */
 416                                        msize++;
 417                                        moff--;
 418                                        data--;
 419                                        outpos--;
 420                                        if (--inscnt)
 421                                                continue;
 422                                        outpos--;  /* remove count slot */
 423                                        inscnt--;  /* make it -1 */
 424                                        break;
 425                                }
 426                                out[outpos - inscnt - 1] = inscnt;
 427                                inscnt = 0;
 428                        }
 429
 430                        /* A copy op is currently limited to 64KB (pack v2) */
 431                        left = (msize < 0x10000) ? 0 : (msize - 0x10000);
 432                        msize -= left;
 433
 434                        op = out + outpos++;
 435                        i = 0x80;
 436
 437                        if (moff & 0x000000ff)
 438                                out[outpos++] = moff >> 0,  i |= 0x01;
 439                        if (moff & 0x0000ff00)
 440                                out[outpos++] = moff >> 8,  i |= 0x02;
 441                        if (moff & 0x00ff0000)
 442                                out[outpos++] = moff >> 16, i |= 0x04;
 443                        if (moff & 0xff000000)
 444                                out[outpos++] = moff >> 24, i |= 0x08;
 445
 446                        if (msize & 0x00ff)
 447                                out[outpos++] = msize >> 0, i |= 0x10;
 448                        if (msize & 0xff00)
 449                                out[outpos++] = msize >> 8, i |= 0x20;
 450
 451                        *op = i;
 452
 453                        data += msize;
 454                        moff += msize;
 455                        msize = left;
 456
 457                        if (moff > 0xffffffff)
 458                                msize = 0;
 459
 460                        if (msize < 4096) {
 461                                int j;
 462                                val = 0;
 463                                for (j = -RABIN_WINDOW; j < 0; j++)
 464                                        val = ((val << 8) | data[j])
 465                                              ^ T[val >> RABIN_SHIFT];
 466                        }
 467                }
 468
 469                if (outpos >= outsize - MAX_OP_SIZE) {
 470                        void *tmp = out;
 471                        outsize = outsize * 3 / 2;
 472                        if (max_size && outsize >= max_size)
 473                                outsize = max_size + MAX_OP_SIZE + 1;
 474                        if (max_size && outpos > max_size)
 475                                break;
 476                        out = realloc(out, outsize);
 477                        if (!out) {
 478                                free(tmp);
 479                                return NULL;
 480                        }
 481                }
 482        }
 483
 484        if (inscnt)
 485                out[outpos - inscnt - 1] = inscnt;
 486
 487        if (max_size && outpos > max_size) {
 488                free(out);
 489                return NULL;
 490        }
 491
 492        *delta_size = outpos;
 493        return out;
 494}