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         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
 298 void free_delta_index(struct delta_index *index)
 299 {
 300         free(index);
 301 }
 302
 303 unsigned 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
 317 void *
 318 create_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 }