diff-delta.c

   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
  23 static 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
  69 static 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
 115 struct index_entry {
 116         const unsigned char *ptr;
 117         unsigned int val;
 118 };
 119
 120 struct unpacked_index_entry {
 121         struct index_entry entry;
 122         struct unpacked_index_entry *next;
 123 };
 124
 125 struct 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
 133 struct 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         hsize = entries / 4;
 151         for (i = 4; (1u << i) < hsize && i < 31; i++);
 152         hsize = 1 << i;
 153         hmask = hsize - 1;
 154
 155         /* allocate lookup index */
 156         memsize = sizeof(*hash) * hsize +
 157                   sizeof(*entry) * entries;
 158         mem = malloc(memsize);
 159         if (!mem)
 160                 return NULL;
 161         hash = mem;
 162         mem = hash + hsize;
 163         entry = mem;
 164
 165         memset(hash, 0, hsize * sizeof(*hash));
 166
 167         /* allocate an array to count hash entries */
 168         hash_count = calloc(hsize, sizeof(*hash_count));
 169         if (!hash_count) {
 170                 free(hash);
 171                 return NULL;
 172         }
 173
 174         /* then populate the index */
 175         prev_val = ~0;
 176         for (data = buffer + entries * RABIN_WINDOW - RABIN_WINDOW;
 177              data >= buffer;
 178              data -= RABIN_WINDOW) {
 179                 unsigned int val = 0;
 180                 for (i = 1; i <= RABIN_WINDOW; i++)
 181                         val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
 182                 if (val == prev_val) {
 183                         /* keep the lowest of consecutive identical blocks */
 184                         entry[-1].entry.ptr = data + RABIN_WINDOW;
 185                         --entries;
 186                 } else {
 187                         prev_val = val;
 188                         i = val & hmask;
 189                         entry->entry.ptr = data + RABIN_WINDOW;
 190                         entry->entry.val = val;
 191                         entry->next = hash[i];
 192                         hash[i] = entry++;
 193                         hash_count[i]++;
 194                 }
 195         }
 196
 197         /*
 198          * Determine a limit on the number of entries in the same hash
 199          * bucket.  This guards us against pathological data sets causing
 200          * really bad hash distribution with most entries in the same hash
 201          * bucket that would bring us to O(m*n) computing costs (m and n
 202          * corresponding to reference and target buffer sizes).
 203          *
 204          * Make sure none of the hash buckets has more entries than
 205          * we're willing to test.  Otherwise we cull the entry list
 206          * uniformly to still preserve a good repartition across
 207          * the reference buffer.
 208          */
 209         for (i = 0; i < hsize; i++) {
 210                 int acc;
 211
 212                 if (hash_count[i] <= HASH_LIMIT)
 213                         continue;
 214
 215                 /* We leave exactly HASH_LIMIT entries in the bucket */
 216                 entries -= hash_count[i] - HASH_LIMIT;
 217
 218                 entry = hash[i];
 219                 acc = 0;
 220
 221                 /*
 222                  * Assume that this loop is gone through exactly
 223                  * HASH_LIMIT times and is entered and left with
 224                  * acc==0.  So the first statement in the loop
 225                  * contributes (hash_count[i]-HASH_LIMIT)*HASH_LIMIT
 226                  * to the accumulator, and the inner loop consequently
 227                  * is run (hash_count[i]-HASH_LIMIT) times, removing
 228                  * one element from the list each time.  Since acc
 229                  * balances out to 0 at the final run, the inner loop
 230                  * body can't be left with entry==NULL.  So we indeed
 231                  * encounter entry==NULL in the outer loop only.
 232                  */
 233                 do {
 234                         acc += hash_count[i] - HASH_LIMIT;
 235                         if (acc > 0) {
 236                                 struct unpacked_index_entry *keep = entry;
 237                                 do {
 238                                         entry = entry->next;
 239                                         acc -= HASH_LIMIT;
 240                                 } while (acc > 0);
 241                                 keep->next = entry->next;
 242                         }
 243                         entry = entry->next;
 244                 } while (entry);
 245         }
 246         free(hash_count);
 247
 248         /*
 249          * Now create the packed index in array form
 250          * rather than linked lists.
 251          */
 252         memsize = sizeof(*index)
 253                 + sizeof(*packed_hash) * (hsize+1)
 254                 + sizeof(*packed_entry) * entries;
 255         mem = malloc(memsize);
 256         if (!mem) {
 257                 free(hash);
 258                 return NULL;
 259         }
 260
 261         index = mem;
 262         index->memsize = memsize;
 263         index->src_buf = buf;
 264         index->src_size = bufsize;
 265         index->hash_mask = hmask;
 266
 267         mem = index->hash;
 268         packed_hash = mem;
 269         mem = packed_hash + (hsize+1);
 270         packed_entry = mem;
 271
 272         for (i = 0; i < hsize; i++) {
 273                 /*
 274                  * Coalesce all entries belonging to one linked list
 275                  * into consecutive array entries.
 276                  */
 277                 packed_hash[i] = packed_entry;
 278                 for (entry = hash[i]; entry; entry = entry->next)
 279                         *packed_entry++ = entry->entry;
 280         }
 281
 282         /* Sentinel value to indicate the length of the last hash bucket */
 283         packed_hash[hsize] = packed_entry;
 284
 285         assert(packed_entry - (struct index_entry *)mem == entries);
 286         free(hash);
 287
 288         return index;
 289 }
 290
 291 void free_delta_index(struct delta_index *index)
 292 {
 293         free(index);
 294 }
 295
 296 unsigned long sizeof_delta_index(struct delta_index *index)
 297 {
 298         if (index)
 299                 return index->memsize;
 300         else
 301                 return 0;
 302 }
 303
 304 /*
 305  * The maximum size for any opcode sequence, including the initial header
 306  * plus Rabin window plus biggest copy.
 307  */
 308 #define MAX_OP_SIZE     (5 + 5 + 1 + RABIN_WINDOW + 7)
 309
 310 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)
 314 {
 315         unsigned int i, outpos, outsize, moff, msize, val;
 316         int inscnt;
 317         const unsigned char *ref_data, *ref_top, *data, *top;
 318         unsigned char *out;
 319
 320         if (!trg_buf || !trg_size)
 321                 return NULL;
 322
 323         outpos = 0;
 324         outsize = 8192;
 325         if (max_size && outsize >= max_size)
 326                 outsize = max_size + MAX_OP_SIZE + 1;
 327         out = malloc(outsize);
 328         if (!out)
 329                 return NULL;
 330
 331         /* store reference buffer size */
 332         i = index->src_size;
 333         while (i >= 0x80) {
 334                 out[outpos++] = i | 0x80;
 335                 i >>= 7;
 336         }
 337         out[outpos++] = i;
 338
 339         /* store target buffer size */
 340         i = trg_size;
 341         while (i >= 0x80) {
 342                 out[outpos++] = i | 0x80;
 343                 i >>= 7;
 344         }
 345         out[outpos++] = i;
 346
 347         ref_data = index->src_buf;
 348         ref_top = ref_data + index->src_size;
 349         data = trg_buf;
 350         top = (const unsigned char *) trg_buf + trg_size;
 351
 352         outpos++;
 353         val = 0;
 354         for (i = 0; i < RABIN_WINDOW && data < top; i++, data++) {
 355                 out[outpos++] = *data;
 356                 val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];
 357         }
 358         inscnt = i;
 359
 360         moff = 0;
 361         msize = 0;
 362         while (data < top) {
 363                 if (msize < 4096) {
 364                         struct index_entry *entry;
 365                         val ^= U[data[-RABIN_WINDOW]];
 366                         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 */
 385                                                 break;
 386                                 }
 387                         }
 388                 }
 389
 390                 if (msize < 4) {
 391                         if (!inscnt)
 392                                 outpos++;
 393                         out[outpos++] = *data++;
 394                         inscnt++;
 395                         if (inscnt == 0x7f) {
 396                                 out[outpos - inscnt - 1] = inscnt;
 397                                 inscnt = 0;
 398                         }
 399                         msize = 0;
 400                 } else {
 401                         unsigned int left;
 402                         unsigned char *op;
 403
 404                         if (inscnt) {
 405                                 while (moff && ref_data[moff-1] == data[-1]) {
 406                                         /* we can match one byte back */
 407                                         msize++;
 408                                         moff--;
 409                                         data--;
 410                                         outpos--;
 411                                         if (--inscnt)
 412                                                 continue;
 413                                         outpos--;  /* remove count slot */
 414                                         inscnt--;  /* make it -1 */
 415                                         break;
 416                                 }
 417                                 out[outpos - inscnt - 1] = inscnt;
 418                                 inscnt = 0;
 419                         }
 420
 421                         /* A copy op is currently limited to 64KB (pack v2) */
 422                         left = (msize < 0x10000) ? 0 : (msize - 0x10000);
 423                         msize -= left;
 424
 425                         op = out + outpos++;
 426                         i = 0x80;
 427
 428                         if (moff & 0x000000ff)
 429                                 out[outpos++] = moff >> 0,  i |= 0x01;
 430                         if (moff & 0x0000ff00)
 431                                 out[outpos++] = moff >> 8,  i |= 0x02;
 432                         if (moff & 0x00ff0000)
 433                                 out[outpos++] = moff >> 16, i |= 0x04;
 434                         if (moff & 0xff000000)
 435                                 out[outpos++] = moff >> 24, i |= 0x08;
 436
 437                         if (msize & 0x00ff)
 438                                 out[outpos++] = msize >> 0, i |= 0x10;
 439                         if (msize & 0xff00)
 440                                 out[outpos++] = msize >> 8, i |= 0x20;
 441
 442                         *op = i;
 443
 444                         data += msize;
 445                         moff += msize;
 446                         msize = left;
 447
 448                         if (msize < 4096) {
 449                                 int j;
 450                                 val = 0;
 451                                 for (j = -RABIN_WINDOW; j < 0; j++)
 452                                         val = ((val << 8) | data[j])
 453                                               ^ T[val >> RABIN_SHIFT];
 454                         }
 455                 }
 456
 457                 if (outpos >= outsize - MAX_OP_SIZE) {
 458                         void *tmp = out;
 459                         outsize = outsize * 3 / 2;
 460                         if (max_size && outsize >= max_size)
 461                                 outsize = max_size + MAX_OP_SIZE + 1;
 462                         if (max_size && outpos > max_size)
 463                                 break;
 464                         out = realloc(out, outsize);
 465                         if (!out) {
 466                                 free(tmp);
 467                                 return NULL;
 468                         }
 469                 }
 470         }
 471
 472         if (inscnt)
 473                 out[outpos - inscnt - 1] = inscnt;
 474
 475         if (max_size && outpos > max_size) {
 476                 free(out);
 477                 return NULL;
 478         }
 479
 480         *delta_size = outpos;
 481         return out;
 482 }