src/delta.c

   1 /*
   2  * Copyright (C) the libgit2 contributors. All rights reserved.
   3  *
   4  * This file is part of libgit2, distributed under the GNU GPL v2 with
   5  * a Linking Exception. For full terms see the included COPYING file.
   6  */
   7
   8 #include "delta.h"
   9
  10 /* maximum hash entry list for the same hash bucket */
  11 #define HASH_LIMIT 64
  12
  13 #define RABIN_SHIFT 23
  14 #define RABIN_WINDOW 16
  15
  16 static const unsigned int T[256] = {
  17         0x00000000, 0xab59b4d1, 0x56b369a2, 0xfdeadd73, 0x063f6795, 0xad66d344,
  18         0x508c0e37, 0xfbd5bae6, 0x0c7ecf2a, 0xa7277bfb, 0x5acda688, 0xf1941259,
  19         0x0a41a8bf, 0xa1181c6e, 0x5cf2c11d, 0xf7ab75cc, 0x18fd9e54, 0xb3a42a85,
  20         0x4e4ef7f6, 0xe5174327, 0x1ec2f9c1, 0xb59b4d10, 0x48719063, 0xe32824b2,
  21         0x1483517e, 0xbfdae5af, 0x423038dc, 0xe9698c0d, 0x12bc36eb, 0xb9e5823a,
  22         0x440f5f49, 0xef56eb98, 0x31fb3ca8, 0x9aa28879, 0x6748550a, 0xcc11e1db,
  23         0x37c45b3d, 0x9c9defec, 0x6177329f, 0xca2e864e, 0x3d85f382, 0x96dc4753,
  24         0x6b369a20, 0xc06f2ef1, 0x3bba9417, 0x90e320c6, 0x6d09fdb5, 0xc6504964,
  25         0x2906a2fc, 0x825f162d, 0x7fb5cb5e, 0xd4ec7f8f, 0x2f39c569, 0x846071b8,
  26         0x798aaccb, 0xd2d3181a, 0x25786dd6, 0x8e21d907, 0x73cb0474, 0xd892b0a5,
  27         0x23470a43, 0x881ebe92, 0x75f463e1, 0xdeadd730, 0x63f67950, 0xc8afcd81,
  28         0x354510f2, 0x9e1ca423, 0x65c91ec5, 0xce90aa14, 0x337a7767, 0x9823c3b6,
  29         0x6f88b67a, 0xc4d102ab, 0x393bdfd8, 0x92626b09, 0x69b7d1ef, 0xc2ee653e,
  30         0x3f04b84d, 0x945d0c9c, 0x7b0be704, 0xd05253d5, 0x2db88ea6, 0x86e13a77,
  31         0x7d348091, 0xd66d3440, 0x2b87e933, 0x80de5de2, 0x7775282e, 0xdc2c9cff,
  32         0x21c6418c, 0x8a9ff55d, 0x714a4fbb, 0xda13fb6a, 0x27f92619, 0x8ca092c8,
  33         0x520d45f8, 0xf954f129, 0x04be2c5a, 0xafe7988b, 0x5432226d, 0xff6b96bc,
  34         0x02814bcf, 0xa9d8ff1e, 0x5e738ad2, 0xf52a3e03, 0x08c0e370, 0xa39957a1,
  35         0x584ced47, 0xf3155996, 0x0eff84e5, 0xa5a63034, 0x4af0dbac, 0xe1a96f7d,
  36         0x1c43b20e, 0xb71a06df, 0x4ccfbc39, 0xe79608e8, 0x1a7cd59b, 0xb125614a,
  37         0x468e1486, 0xedd7a057, 0x103d7d24, 0xbb64c9f5, 0x40b17313, 0xebe8c7c2,
  38         0x16021ab1, 0xbd5bae60, 0x6cb54671, 0xc7ecf2a0, 0x3a062fd3, 0x915f9b02,
  39         0x6a8a21e4, 0xc1d39535, 0x3c394846, 0x9760fc97, 0x60cb895b, 0xcb923d8a,
  40         0x3678e0f9, 0x9d215428, 0x66f4eece, 0xcdad5a1f, 0x3047876c, 0x9b1e33bd,
  41         0x7448d825, 0xdf116cf4, 0x22fbb187, 0x89a20556, 0x7277bfb0, 0xd92e0b61,
  42         0x24c4d612, 0x8f9d62c3, 0x7836170f, 0xd36fa3de, 0x2e857ead, 0x85dcca7c,
  43         0x7e09709a, 0xd550c44b, 0x28ba1938, 0x83e3ade9, 0x5d4e7ad9, 0xf617ce08,
  44         0x0bfd137b, 0xa0a4a7aa, 0x5b711d4c, 0xf028a99d, 0x0dc274ee, 0xa69bc03f,
  45         0x5130b5f3, 0xfa690122, 0x0783dc51, 0xacda6880, 0x570fd266, 0xfc5666b7,
  46         0x01bcbbc4, 0xaae50f15, 0x45b3e48d, 0xeeea505c, 0x13008d2f, 0xb85939fe,
  47         0x438c8318, 0xe8d537c9, 0x153feaba, 0xbe665e6b, 0x49cd2ba7, 0xe2949f76,
  48         0x1f7e4205, 0xb427f6d4, 0x4ff24c32, 0xe4abf8e3, 0x19412590, 0xb2189141,
  49         0x0f433f21, 0xa41a8bf0, 0x59f05683, 0xf2a9e252, 0x097c58b4, 0xa225ec65,
  50         0x5fcf3116, 0xf49685c7, 0x033df00b, 0xa86444da, 0x558e99a9, 0xfed72d78,
  51         0x0502979e, 0xae5b234f, 0x53b1fe3c, 0xf8e84aed, 0x17bea175, 0xbce715a4,
  52         0x410dc8d7, 0xea547c06, 0x1181c6e0, 0xbad87231, 0x4732af42, 0xec6b1b93,
  53         0x1bc06e5f, 0xb099da8e, 0x4d7307fd, 0xe62ab32c, 0x1dff09ca, 0xb6a6bd1b,
  54         0x4b4c6068, 0xe015d4b9, 0x3eb80389, 0x95e1b758, 0x680b6a2b, 0xc352defa,
  55         0x3887641c, 0x93ded0cd, 0x6e340dbe, 0xc56db96f, 0x32c6cca3, 0x999f7872,
  56         0x6475a501, 0xcf2c11d0, 0x34f9ab36, 0x9fa01fe7, 0x624ac294, 0xc9137645,
  57         0x26459ddd, 0x8d1c290c, 0x70f6f47f, 0xdbaf40ae, 0x207afa48, 0x8b234e99,
  58         0x76c993ea, 0xdd90273b, 0x2a3b52f7, 0x8162e626, 0x7c883b55, 0xd7d18f84,
  59         0x2c043562, 0x875d81b3, 0x7ab75cc0, 0xd1eee811
  60 };
  61
  62 static const unsigned int U[256] = {
  63         0x00000000, 0x7eb5200d, 0x5633f4cb, 0x2886d4c6, 0x073e5d47, 0x798b7d4a,
  64         0x510da98c, 0x2fb88981, 0x0e7cba8e, 0x70c99a83, 0x584f4e45, 0x26fa6e48,
  65         0x0942e7c9, 0x77f7c7c4, 0x5f711302, 0x21c4330f, 0x1cf9751c, 0x624c5511,
  66         0x4aca81d7, 0x347fa1da, 0x1bc7285b, 0x65720856, 0x4df4dc90, 0x3341fc9d,
  67         0x1285cf92, 0x6c30ef9f, 0x44b63b59, 0x3a031b54, 0x15bb92d5, 0x6b0eb2d8,
  68         0x4388661e, 0x3d3d4613, 0x39f2ea38, 0x4747ca35, 0x6fc11ef3, 0x11743efe,
  69         0x3eccb77f, 0x40799772, 0x68ff43b4, 0x164a63b9, 0x378e50b6, 0x493b70bb,
  70         0x61bda47d, 0x1f088470, 0x30b00df1, 0x4e052dfc, 0x6683f93a, 0x1836d937,
  71         0x250b9f24, 0x5bbebf29, 0x73386bef, 0x0d8d4be2, 0x2235c263, 0x5c80e26e,
  72         0x740636a8, 0x0ab316a5, 0x2b7725aa, 0x55c205a7, 0x7d44d161, 0x03f1f16c,
  73         0x2c4978ed, 0x52fc58e0, 0x7a7a8c26, 0x04cfac2b, 0x73e5d470, 0x0d50f47d,
  74         0x25d620bb, 0x5b6300b6, 0x74db8937, 0x0a6ea93a, 0x22e87dfc, 0x5c5d5df1,
  75         0x7d996efe, 0x032c4ef3, 0x2baa9a35, 0x551fba38, 0x7aa733b9, 0x041213b4,
  76         0x2c94c772, 0x5221e77f, 0x6f1ca16c, 0x11a98161, 0x392f55a7, 0x479a75aa,
  77         0x6822fc2b, 0x1697dc26, 0x3e1108e0, 0x40a428ed, 0x61601be2, 0x1fd53bef,
  78         0x3753ef29, 0x49e6cf24, 0x665e46a5, 0x18eb66a8, 0x306db26e, 0x4ed89263,
  79         0x4a173e48, 0x34a21e45, 0x1c24ca83, 0x6291ea8e, 0x4d29630f, 0x339c4302,
  80         0x1b1a97c4, 0x65afb7c9, 0x446b84c6, 0x3adea4cb, 0x1258700d, 0x6ced5000,
  81         0x4355d981, 0x3de0f98c, 0x15662d4a, 0x6bd30d47, 0x56ee4b54, 0x285b6b59,
  82         0x00ddbf9f, 0x7e689f92, 0x51d01613, 0x2f65361e, 0x07e3e2d8, 0x7956c2d5,
  83         0x5892f1da, 0x2627d1d7, 0x0ea10511, 0x7014251c, 0x5facac9d, 0x21198c90,
  84         0x099f5856, 0x772a785b, 0x4c921c31, 0x32273c3c, 0x1aa1e8fa, 0x6414c8f7,
  85         0x4bac4176, 0x3519617b, 0x1d9fb5bd, 0x632a95b0, 0x42eea6bf, 0x3c5b86b2,
  86         0x14dd5274, 0x6a687279, 0x45d0fbf8, 0x3b65dbf5, 0x13e30f33, 0x6d562f3e,
  87         0x506b692d, 0x2ede4920, 0x06589de6, 0x78edbdeb, 0x5755346a, 0x29e01467,
  88         0x0166c0a1, 0x7fd3e0ac, 0x5e17d3a3, 0x20a2f3ae, 0x08242768, 0x76910765,
  89         0x59298ee4, 0x279caee9, 0x0f1a7a2f, 0x71af5a22, 0x7560f609, 0x0bd5d604,
  90         0x235302c2, 0x5de622cf, 0x725eab4e, 0x0ceb8b43, 0x246d5f85, 0x5ad87f88,
  91         0x7b1c4c87, 0x05a96c8a, 0x2d2fb84c, 0x539a9841, 0x7c2211c0, 0x029731cd,
  92         0x2a11e50b, 0x54a4c506, 0x69998315, 0x172ca318, 0x3faa77de, 0x411f57d3,
  93         0x6ea7de52, 0x1012fe5f, 0x38942a99, 0x46210a94, 0x67e5399b, 0x19501996,
  94         0x31d6cd50, 0x4f63ed5d, 0x60db64dc, 0x1e6e44d1, 0x36e89017, 0x485db01a,
  95         0x3f77c841, 0x41c2e84c, 0x69443c8a, 0x17f11c87, 0x38499506, 0x46fcb50b,
  96         0x6e7a61cd, 0x10cf41c0, 0x310b72cf, 0x4fbe52c2, 0x67388604, 0x198da609,
  97         0x36352f88, 0x48800f85, 0x6006db43, 0x1eb3fb4e, 0x238ebd5d, 0x5d3b9d50,
  98         0x75bd4996, 0x0b08699b, 0x24b0e01a, 0x5a05c017, 0x728314d1, 0x0c3634dc,
  99         0x2df207d3, 0x534727de, 0x7bc1f318, 0x0574d315, 0x2acc5a94, 0x54797a99,
 100         0x7cffae5f, 0x024a8e52, 0x06852279, 0x78300274, 0x50b6d6b2, 0x2e03f6bf,
 101         0x01bb7f3e, 0x7f0e5f33, 0x57888bf5, 0x293dabf8, 0x08f998f7, 0x764cb8fa,
 102         0x5eca6c3c, 0x207f4c31, 0x0fc7c5b0, 0x7172e5bd, 0x59f4317b, 0x27411176,
 103         0x1a7c5765, 0x64c97768, 0x4c4fa3ae, 0x32fa83a3, 0x1d420a22, 0x63f72a2f,
 104         0x4b71fee9, 0x35c4dee4, 0x1400edeb, 0x6ab5cde6, 0x42331920, 0x3c86392d,
 105         0x133eb0ac, 0x6d8b90a1, 0x450d4467, 0x3bb8646a
 106 };
 107
 108 struct index_entry {
 109         const unsigned char *ptr;
 110         unsigned int val;
 111         struct index_entry *next;
 112 };
 113
 114 struct git_delta_index {
 115         unsigned long memsize;
 116         const void *src_buf;
 117         size_t src_size;
 118         unsigned int hash_mask;
 119         struct index_entry *hash[GIT_FLEX_ARRAY];
 120 };
 121
 122 static int lookup_index_alloc(
 123         void **out, unsigned long *out_len, size_t entries, size_t hash_count)
 124 {
 125         size_t entries_len, hash_len, index_len;
 126
 127         GITERR_CHECK_ALLOC_MULTIPLY(&entries_len, entries, sizeof(struct index_entry));
 128         GITERR_CHECK_ALLOC_MULTIPLY(&hash_len, hash_count, sizeof(struct index_entry *));
 129
 130         GITERR_CHECK_ALLOC_ADD(&index_len, sizeof(struct git_delta_index), entries_len);
 131         GITERR_CHECK_ALLOC_ADD(&index_len, index_len, hash_len);
 132
 133         if (!git__is_ulong(index_len)) {
 134                 giterr_set(GITERR_NOMEMORY, "overly large delta");
 135                 return -1;
 136         }
 137
 138         *out = git__malloc(index_len);
 139         GITERR_CHECK_ALLOC(*out);
 140
 141         *out_len = index_len;
 142         return 0;
 143 }
 144
 145 int git_delta_index_init(
 146         git_delta_index **out, const void *buf, size_t bufsize)
 147 {
 148         unsigned int i, hsize, hmask, entries, prev_val, *hash_count;
 149         const unsigned char *data, *buffer = buf;
 150         struct git_delta_index *index;
 151         struct index_entry *entry, **hash;
 152         void *mem;
 153         unsigned long memsize;
 154
 155         *out = NULL;
 156
 157         if (!buf || !bufsize)
 158                 return 0;
 159
 160         /* Determine index hash size.  Note that indexing skips the
 161            first byte to allow for optimizing the rabin polynomial
 162            initialization in create_delta(). */
 163         entries = (unsigned int)(bufsize - 1) / RABIN_WINDOW;
 164         if (bufsize >= 0xffffffffUL) {
 165                 /*
 166                  * Current delta format can't encode offsets into
 167                  * reference buffer with more than 32 bits.
 168                  */
 169                 entries = 0xfffffffeU / RABIN_WINDOW;
 170         }
 171         hsize = entries / 4;
 172         for (i = 4; i < 31 && (1u << i) < hsize; i++);
 173         hsize = 1 << i;
 174         hmask = hsize - 1;
 175
 176         if (lookup_index_alloc(&mem, &memsize, entries, hsize) < 0)
 177                 return -1;
 178
 179         index = mem;
 180         mem = index->hash;
 181         hash = mem;
 182         mem = hash + hsize;
 183         entry = mem;
 184
 185         index->memsize = memsize;
 186         index->src_buf = buf;
 187         index->src_size = bufsize;
 188         index->hash_mask = hmask;
 189         memset(hash, 0, hsize * sizeof(*hash));
 190
 191         /* allocate an array to count hash entries */
 192         hash_count = git__calloc(hsize, sizeof(*hash_count));
 193         if (!hash_count) {
 194                 git__free(index);
 195                 return -1;
 196         }
 197
 198         /* then populate the index */
 199         prev_val = ~0;
 200         for (data = buffer + entries * RABIN_WINDOW - RABIN_WINDOW;
 201              data >= buffer;
 202              data -= RABIN_WINDOW) {
 203                 unsigned int val = 0;
 204                 for (i = 1; i <= RABIN_WINDOW; i++)
 205                         val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
 206                 if (val == prev_val) {
 207                         /* keep the lowest of consecutive identical blocks */
 208                         entry[-1].ptr = data + RABIN_WINDOW;
 209                 } else {
 210                         prev_val = val;
 211                         i = val & hmask;
 212                         entry->ptr = data + RABIN_WINDOW;
 213                         entry->val = val;
 214                         entry->next = hash[i];
 215                         hash[i] = entry++;
 216                         hash_count[i]++;
 217                 }
 218         }
 219
 220         /*
 221          * Determine a limit on the number of entries in the same hash
 222          * bucket.  This guard us against patological data sets causing
 223          * really bad hash distribution with most entries in the same hash
 224          * bucket that would bring us to O(m*n) computing costs (m and n
 225          * corresponding to reference and target buffer sizes).
 226          *
 227          * Make sure none of the hash buckets has more entries than
 228          * we're willing to test.  Otherwise we cull the entry list
 229          * uniformly to still preserve a good repartition across
 230          * the reference buffer.
 231          */
 232         for (i = 0; i < hsize; i++) {
 233                 if (hash_count[i] < HASH_LIMIT)
 234                         continue;
 235
 236                 entry = hash[i];
 237                 do {
 238                         struct index_entry *keep = entry;
 239                         int skip = hash_count[i] / HASH_LIMIT / 2;
 240                         do {
 241                                 entry = entry->next;
 242                         } while(--skip && entry);
 243                         keep->next = entry;
 244                 } while (entry);
 245         }
 246         git__free(hash_count);
 247
 248         *out = index;
 249         return 0;
 250 }
 251
 252 void git_delta_index_free(git_delta_index *index)
 253 {
 254         git__free(index);
 255 }
 256
 257 size_t git_delta_index_size(git_delta_index *index)
 258 {
 259         assert(index);
 260
 261         return index->memsize;
 262 }
 263
 264 /*
 265  * The maximum size for any opcode sequence, including the initial header
 266  * plus rabin window plus biggest copy.
 267  */
 268 #define MAX_OP_SIZE     (5 + 5 + 1 + RABIN_WINDOW + 7)
 269
 270 int git_delta_create_from_index(
 271         void **out,
 272         size_t *out_len,
 273         const struct git_delta_index *index,
 274         const void *trg_buf,
 275         size_t trg_size,
 276         size_t max_size)
 277 {
 278         unsigned int i, bufpos, bufsize, moff, msize, val;
 279         int inscnt;
 280         const unsigned char *ref_data, *ref_top, *data, *top;
 281         unsigned char *buf;
 282
 283         *out = NULL;
 284         *out_len = 0;
 285
 286         if (!trg_buf || !trg_size)
 287                 return 0;
 288
 289         bufpos = 0;
 290         bufsize = 8192;
 291         if (max_size && bufsize >= max_size)
 292                 bufsize = (unsigned int)(max_size + MAX_OP_SIZE + 1);
 293         buf = git__malloc(bufsize);
 294         GITERR_CHECK_ALLOC(buf);
 295
 296         /* store reference buffer size */
 297         i = index->src_size;
 298         while (i >= 0x80) {
 299                 buf[bufpos++] = i | 0x80;
 300                 i >>= 7;
 301         }
 302         buf[bufpos++] = i;
 303
 304         /* store target buffer size */
 305         i = trg_size;
 306         while (i >= 0x80) {
 307                 buf[bufpos++] = i | 0x80;
 308                 i >>= 7;
 309         }
 310         buf[bufpos++] = i;
 311
 312         ref_data = index->src_buf;
 313         ref_top = ref_data + index->src_size;
 314         data = trg_buf;
 315         top = (const unsigned char *) trg_buf + trg_size;
 316
 317         bufpos++;
 318         val = 0;
 319         for (i = 0; i < RABIN_WINDOW && data < top; i++, data++) {
 320                 buf[bufpos++] = *data;
 321                 val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];
 322         }
 323         inscnt = i;
 324
 325         moff = 0;
 326         msize = 0;
 327         while (data < top) {
 328                 if (msize < 4096) {
 329                         struct index_entry *entry;
 330                         val ^= U[data[-RABIN_WINDOW]];
 331                         val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];
 332                         i = val & index->hash_mask;
 333                         for (entry = index->hash[i]; entry; entry = entry->next) {
 334                                 const unsigned char *ref = entry->ptr;
 335                                 const unsigned char *src = data;
 336                                 unsigned int ref_size = (unsigned int)(ref_top - ref);
 337                                 if (entry->val != val)
 338                                         continue;
 339                                 if (ref_size > (unsigned int)(top - src))
 340                                         ref_size = (unsigned int)(top - src);
 341                                 if (ref_size <= msize)
 342                                         break;
 343                                 while (ref_size-- && *src++ == *ref)
 344                                         ref++;
 345                                 if (msize < (unsigned int)(ref - entry->ptr)) {
 346                                         /* this is our best match so far */
 347                                         msize = (unsigned int)(ref - entry->ptr);
 348                                         moff = (unsigned int)(entry->ptr - ref_data);
 349                                         if (msize >= 4096) /* good enough */
 350                                                 break;
 351                                 }
 352                         }
 353                 }
 354
 355                 if (msize < 4) {
 356                         if (!inscnt)
 357                                 bufpos++;
 358                         buf[bufpos++] = *data++;
 359                         inscnt++;
 360                         if (inscnt == 0x7f) {
 361                                 buf[bufpos - inscnt - 1] = inscnt;
 362                                 inscnt = 0;
 363                         }
 364                         msize = 0;
 365                 } else {
 366                         unsigned int left;
 367                         unsigned char *op;
 368
 369                         if (inscnt) {
 370                                 while (moff && ref_data[moff-1] == data[-1]) {
 371                                         /* we can match one byte back */
 372                                         msize++;
 373                                         moff--;
 374                                         data--;
 375                                         bufpos--;
 376                                         if (--inscnt)
 377                                                 continue;
 378                                         bufpos--;  /* remove count slot */
 379                                         inscnt--;  /* make it -1 */
 380                                         break;
 381                                 }
 382                                 buf[bufpos - inscnt - 1] = inscnt;
 383                                 inscnt = 0;
 384                         }
 385
 386                         /* A copy op is currently limited to 64KB (pack v2) */
 387                         left = (msize < 0x10000) ? 0 : (msize - 0x10000);
 388                         msize -= left;
 389
 390                         op = buf + bufpos++;
 391                         i = 0x80;
 392
 393                         if (moff & 0x000000ff)
 394                                 buf[bufpos++] = moff >> 0,  i |= 0x01;
 395                         if (moff & 0x0000ff00)
 396                                 buf[bufpos++] = moff >> 8,  i |= 0x02;
 397                         if (moff & 0x00ff0000)
 398                                 buf[bufpos++] = moff >> 16, i |= 0x04;
 399                         if (moff & 0xff000000)
 400                                 buf[bufpos++] = moff >> 24, i |= 0x08;
 401
 402                         if (msize & 0x00ff)
 403                                 buf[bufpos++] = msize >> 0, i |= 0x10;
 404                         if (msize & 0xff00)
 405                                 buf[bufpos++] = msize >> 8, i |= 0x20;
 406
 407                         *op = i;
 408
 409                         data += msize;
 410                         moff += msize;
 411                         msize = left;
 412
 413                         if (msize < 4096) {
 414                                 int j;
 415                                 val = 0;
 416                                 for (j = -RABIN_WINDOW; j < 0; j++)
 417                                         val = ((val << 8) | data[j])
 418                                               ^ T[val >> RABIN_SHIFT];
 419                         }
 420                 }
 421
 422                 if (bufpos >= bufsize - MAX_OP_SIZE) {
 423                         void *tmp = buf;
 424                         bufsize = bufsize * 3 / 2;
 425                         if (max_size && bufsize >= max_size)
 426                                 bufsize = max_size + MAX_OP_SIZE + 1;
 427                         if (max_size && bufpos > max_size)
 428                                 break;
 429                         buf = git__realloc(buf, bufsize);
 430                         if (!buf) {
 431                                 git__free(tmp);
 432                                 return -1;
 433                         }
 434                 }
 435         }
 436
 437         if (inscnt)
 438                 buf[bufpos - inscnt - 1] = inscnt;
 439
 440         if (max_size && bufpos > max_size) {
 441                 giterr_set(GITERR_NOMEMORY, "delta would be larger than maximum size");
 442                 git__free(buf);
 443                 return GIT_EBUFS;
 444         }
 445
 446         *out_len = bufpos;
 447         *out = buf;
 448         return 0;
 449 }
 450
 451 /*
 452 * Delta application was heavily cribbed from BinaryDelta.java in JGit, which
 453 * itself was heavily cribbed from <code>patch-delta.c</code> in the
 454 * GIT project.  The original delta patching code was written by
 455 * Nicolas Pitre <nico@cam.org>.
 456 */
 457
 458 static int hdr_sz(
 459         size_t *size,
 460         const unsigned char **delta,
 461         const unsigned char *end)
 462 {
 463         const unsigned char *d = *delta;
 464         size_t r = 0;
 465         unsigned int c, shift = 0;
 466
 467         do {
 468                 if (d == end) {
 469                         giterr_set(GITERR_INVALID, "truncated delta");
 470                         return -1;
 471                 }
 472
 473                 c = *d++;
 474                 r |= (c & 0x7f) << shift;
 475                 shift += 7;
 476         } while (c & 0x80);
 477         *delta = d;
 478         *size = r;
 479         return 0;
 480 }
 481
 482 int git_delta_read_header(
 483         size_t *base_out,
 484         size_t *result_out,
 485         const unsigned char *delta,
 486         size_t delta_len)
 487 {
 488         const unsigned char *delta_end = delta + delta_len;
 489         if ((hdr_sz(base_out, &delta, delta_end) < 0) ||
 490                 (hdr_sz(result_out, &delta, delta_end) < 0))
 491                 return -1;
 492         return 0;
 493 }
 494
 495 #define DELTA_HEADER_BUFFER_LEN 16
 496 int git_delta_read_header_fromstream(
 497         size_t *base_sz, size_t *res_sz, git_packfile_stream *stream)
 498 {
 499         static const size_t buffer_len = DELTA_HEADER_BUFFER_LEN;
 500         unsigned char buffer[DELTA_HEADER_BUFFER_LEN];
 501         const unsigned char *delta, *delta_end;
 502         size_t len;
 503         ssize_t read;
 504
 505         len = read = 0;
 506         while (len < buffer_len) {
 507                 read = git_packfile_stream_read(stream, &buffer[len], buffer_len - len);
 508
 509                 if (read == 0)
 510                         break;
 511
 512                 if (read == GIT_EBUFS)
 513                         continue;
 514
 515                 len += read;
 516         }
 517
 518         delta = buffer;
 519         delta_end = delta + len;
 520         if ((hdr_sz(base_sz, &delta, delta_end) < 0) ||
 521                 (hdr_sz(res_sz, &delta, delta_end) < 0))
 522                 return -1;
 523
 524         return 0;
 525 }
 526
 527 int git_delta_apply(
 528         void **out,
 529         size_t *out_len,
 530         const unsigned char *base,
 531         size_t base_len,
 532         const unsigned char *delta,
 533         size_t delta_len)
 534 {
 535         const unsigned char *delta_end = delta + delta_len;
 536         size_t base_sz, res_sz, alloc_sz;
 537         unsigned char *res_dp;
 538
 539         *out = NULL;
 540         *out_len = 0;
 541
 542         /*
 543          * Check that the base size matches the data we were given;
 544          * if not we would underflow while accessing data from the
 545          * base object, resulting in data corruption or segfault.
 546          */
 547         if ((hdr_sz(&base_sz, &delta, delta_end) < 0) || (base_sz != base_len)) {
 548                 giterr_set(GITERR_INVALID, "failed to apply delta: base size does not match given data");
 549                 return -1;
 550         }
 551
 552         if (hdr_sz(&res_sz, &delta, delta_end) < 0) {
 553                 giterr_set(GITERR_INVALID, "failed to apply delta: base size does not match given data");
 554                 return -1;
 555         }
 556
 557         GITERR_CHECK_ALLOC_ADD(&alloc_sz, res_sz, 1);
 558         res_dp = git__malloc(alloc_sz);
 559         GITERR_CHECK_ALLOC(res_dp);
 560
 561         res_dp[res_sz] = '\0';
 562         *out = res_dp;
 563         *out_len = res_sz;
 564
 565         while (delta < delta_end) {
 566                 unsigned char cmd = *delta++;
 567                 if (cmd & 0x80) {
 568                         /* cmd is a copy instruction; copy from the base. */
 569                         size_t off = 0, len = 0, end;
 570
 571 #define ADD_DELTA(o, shift) { if (delta < delta_end) (o) |= ((unsigned) *delta++ << shift); else goto fail; }
 572                         if (cmd & 0x01) ADD_DELTA(off, 0UL);
 573                         if (cmd & 0x02) ADD_DELTA(off, 8UL);
 574                         if (cmd & 0x04) ADD_DELTA(off, 16UL);
 575                         if (cmd & 0x08) ADD_DELTA(off, 24UL);
 576
 577                         if (cmd & 0x10) ADD_DELTA(len, 0UL);
 578                         if (cmd & 0x20) ADD_DELTA(len, 8UL);
 579                         if (cmd & 0x40) ADD_DELTA(len, 16UL);
 580                         if (!len)       len = 0x10000;
 581 #undef ADD_DELTA
 582
 583                         if (GIT_ADD_SIZET_OVERFLOW(&end, off, len) ||
 584                             base_len < end || res_sz < len)
 585                                 goto fail;
 586
 587                         memcpy(res_dp, base + off, len);
 588                         res_dp += len;
 589                         res_sz -= len;
 590
 591                 } else if (cmd) {
 592                         /*
 593                          * cmd is a literal insert instruction; copy from
 594                          * the delta stream itself.
 595                          */
 596                         if (delta_end - delta < cmd || res_sz < cmd)
 597                                 goto fail;
 598                         memcpy(res_dp, delta, cmd);
 599                         delta += cmd;
 600                         res_dp += cmd;
 601                         res_sz -= cmd;
 602
 603                 } else {
 604                         /* cmd == 0 is reserved for future encodings. */
 605                         goto fail;
 606                 }
 607         }
 608
 609         if (delta != delta_end || res_sz)
 610                 goto fail;
 611         return 0;
 612
 613 fail:
 614         git__free(*out);
 615
 616         *out = NULL;
 617         *out_len = 0;
 618
 619         giterr_set(GITERR_INVALID, "failed to apply delta");
 620         return -1;
 621 }