Line Flow Count Block(s) Source
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 1172 2 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 1172 2-8 GIT_ERROR_CHECK_ALLOC_MULTIPLY(&entries_len, entries, sizeof(struct index_entry));
128 1172 9-15 GIT_ERROR_CHECK_ALLOC_MULTIPLY(&hash_len, hash_count, sizeof(struct index_entry *));
129 -
130 1172 16-22 GIT_ERROR_CHECK_ALLOC_ADD(&index_len, sizeof(struct git_delta_index), entries_len);
131 1172 23-29 GIT_ERROR_CHECK_ALLOC_ADD(&index_len, index_len, hash_len);
132 -
133 1172 30,31 if (!git__is_ulong(index_len)) {
134 ##### 32 git_error_set(GIT_ERROR_NOMEMORY, "overly large delta");
135 ##### 33 return -1;
136 - }
137 -
138 1172 34 *out = git__malloc(index_len);
139 1172 35,36 GIT_ERROR_CHECK_ALLOC(*out);
140 -
141 1172 37 *out_len = (unsigned long)index_len;
142 1172 37 return 0;
143 - }
144 -
145 1172 2 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 1172 2 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 1172 2 *out = NULL;
156 -
157 1172 2,3 if (!buf || !bufsize)
158 ##### 4 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 1172 5 entries = (unsigned int)(bufsize - 1) / RABIN_WINDOW;
164 1172 5 if (bufsize >= 0xffffffffUL) {
165 - /*
166 - * Current delta format can't encode offsets into
167 - * reference buffer with more than 32 bits.
168 - */
169 ##### 6 entries = 0xfffffffeU / RABIN_WINDOW;
170 - }
171 1172 7 hsize = entries / 4;
172 1180 7-10 for (i = 4; i < 31 && (1u << i) < hsize; i++);
173 1172 11 hsize = 1 << i;
174 1172 11 hmask = hsize - 1;
175 -
176 1172 11,12 if (lookup_index_alloc(&mem, &memsize, entries, hsize) < 0)
177 ##### 13 return -1;
178 -
179 1172 14 index = mem;
180 1172 14 mem = index->hash;
181 1172 14 hash = mem;
182 1172 14 mem = hash + hsize;
183 1172 14 entry = mem;
184 -
185 1172 14 index->memsize = memsize;
186 1172 14 index->src_buf = buf;
187 1172 14 index->src_size = bufsize;
188 1172 14 index->hash_mask = hmask;
189 1172 14 memset(hash, 0, hsize * sizeof(*hash));
190 -
191 - /* allocate an array to count hash entries */
192 1172 14 hash_count = git__calloc(hsize, sizeof(*hash_count));
193 1172 15 if (!hash_count) {
194 ##### 16 git__free(index);
195 ##### 17 return -1;
196 - }
197 -
198 - /* then populate the index */
199 1172 18 prev_val = ~0;
200 13908 18,26 for (data = buffer + entries * RABIN_WINDOW - RABIN_WINDOW;
201 - data >= buffer;
202 12736 25 data -= RABIN_WINDOW) {
203 12736 19 unsigned int val = 0;
204 216512 19-21 for (i = 1; i <= RABIN_WINDOW; i++)
205 203776 20 val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
206 12736 22 if (val == prev_val) {
207 - /* keep the lowest of consecutive identical blocks */
208 ##### 23 entry[-1].ptr = data + RABIN_WINDOW;
209 - } else {
210 12736 24 prev_val = val;
211 12736 24 i = val & hmask;
212 12736 24 entry->ptr = data + RABIN_WINDOW;
213 12736 24 entry->val = val;
214 12736 24 entry->next = hash[i];
215 12736 24 hash[i] = entry++;
216 12736 24 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 20116 27,35,36 for (i = 0; i < hsize; i++) {
233 18944 28 if (hash_count[i] < HASH_LIMIT)
234 18944 29 continue;
235 -
236 ##### 30 entry = hash[i];
237 - do {
238 ##### 31 struct index_entry *keep = entry;
239 ##### 31 int skip = hash_count[i] / HASH_LIMIT / 2;
240 - do {
241 ##### 32 entry = entry->next;
242 ##### 32,33 } while(--skip && entry);
243 ##### 34 keep->next = entry;
244 ##### 34 } while (entry);
245 - }
246 1172 37 git__free(hash_count);
247 -
248 1172 38 *out = index;
249 1172 38 return 0;
250 - }
251 -
252 677 2 void git_delta_index_free(git_delta_index *index)
253 - {
254 677 2 git__free(index);
255 677 3 }
256 -
257 1797 2 size_t git_delta_index_size(git_delta_index *index)
258 - {
259 1797 2,3 assert(index);
260 -
261 1797 4 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 6322 2 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 6322 2 *out = NULL;
284 6322 2 *out_len = 0;
285 -
286 6322 2,3 if (!trg_buf || !trg_size)
287 ##### 4 return 0;
288 -
289 6322 5,6 if (index->src_size > UINT_MAX ||
290 6322 7 trg_size > UINT_MAX ||
291 - max_size > (UINT_MAX - MAX_OP_SIZE - 1)) {
292 ##### 8 git_error_set(GIT_ERROR_INVALID, "buffer sizes too large for delta processing");
293 ##### 9 return -1;
294 - }
295 -
296 6322 10 bufpos = 0;
297 6322 10 bufsize = 8192;
298 6322 10,11 if (max_size && bufsize >= max_size)
299 6322 12 bufsize = (unsigned int)(max_size + MAX_OP_SIZE + 1);
300 6322 13 buf = git__malloc(bufsize);
301 6322 14,15 GIT_ERROR_CHECK_ALLOC(buf);
302 -
303 - /* store reference buffer size */
304 6322 16 i = (unsigned int)index->src_size;
305 10796 16,18 while (i >= 0x80) {
306 4474 17 buf[bufpos++] = i | 0x80;
307 4474 17 i >>= 7;
308 - }
309 6322 19 buf[bufpos++] = i;
310 -
311 - /* store target buffer size */
312 6322 19 i = (unsigned int)trg_size;
313 10359 19,21 while (i >= 0x80) {
314 4037 20 buf[bufpos++] = i | 0x80;
315 4037 20 i >>= 7;
316 - }
317 6322 22 buf[bufpos++] = i;
318 -
319 6322 22 ref_data = index->src_buf;
320 6322 22 ref_top = ref_data + index->src_size;
321 6322 22 data = trg_buf;
322 6322 22 top = (const unsigned char *) trg_buf + trg_size;
323 -
324 6322 22 bufpos++;
325 6322 22 val = 0;
326 107402 22-25 for (i = 0; i < RABIN_WINDOW && data < top; i++, data++) {
327 101080 23 buf[bufpos++] = *data;
328 101080 23 val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];
329 - }
330 6322 26 inscnt = i;
331 -
332 6322 26 moff = 0;
333 6322 26 msize = 0;
334 270431 26,88 while (data < top) {
335 270276 27 if (msize < 4096) {
336 - struct index_entry *entry;
337 270276 28 val ^= U[data[-RABIN_WINDOW]];
338 270276 28 val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];
339 270276 28 i = val & index->hash_mask;
340 502274 28,42,43 for (entry = index->hash[i]; entry; entry = entry->next) {
341 231998 29 const unsigned char *ref = entry->ptr;
342 231998 29 const unsigned char *src = data;
343 231998 29 unsigned int ref_size = (unsigned int)(ref_top - ref);
344 231998 29 if (entry->val != val)
345 230726 30 continue;
346 1272 31 if (ref_size > (unsigned int)(top - src))
347 725 32 ref_size = (unsigned int)(top - src);
348 1272 33 if (ref_size <= msize)
349 ##### 34 break;
350 55231 35,37,38 while (ref_size-- && *src++ == *ref)
351 53959 36 ref++;
352 1272 39 if (msize < (unsigned int)(ref - entry->ptr)) {
353 - /* this is our best match so far */
354 1272 40 msize = (unsigned int)(ref - entry->ptr);
355 1272 40 moff = (unsigned int)(entry->ptr - ref_data);
356 1272 40 if (msize >= 4096) /* good enough */
357 ##### 41 break;
358 - }
359 - }
360 - }
361 -
362 270276 44 if (msize < 4) {
363 269077 45 if (!inscnt)
364 1144 46 bufpos++;
365 269077 47 buf[bufpos++] = *data++;
366 269077 47 inscnt++;
367 269077 47 if (inscnt == 0x7f) {
368 ##### 48 buf[bufpos - inscnt - 1] = inscnt;
369 ##### 48 inscnt = 0;
370 - }
371 269077 49 msize = 0;
372 - } else {
373 - unsigned int left;
374 - unsigned char *op;
375 -
376 1199 50 if (inscnt) {
377 21327 51,55,56 while (moff && ref_data[moff-1] == data[-1]) {
378 - /* we can match one byte back */
379 20793 52 msize++;
380 20793 52 moff--;
381 20793 52 data--;
382 20793 52 bufpos--;
383 20793 52 if (--inscnt)
384 20128 53 continue;
385 665 54 bufpos--; /* remove count slot */
386 665 54 inscnt--; /* make it -1 */
387 665 54 break;
388 - }
389 1199 57 buf[bufpos - inscnt - 1] = inscnt;
390 1199 57 inscnt = 0;
391 - }
392 -
393 - /* A copy op is currently limited to 64KB (pack v2) */
394 1199 58-60 left = (msize < 0x10000) ? 0 : (msize - 0x10000);
395 1199 61 msize -= left;
396 -
397 1199 61 op = buf + bufpos++;
398 1199 61 i = 0x80;
399 -
400 1199 61 if (moff & 0x000000ff)
401 686 62 buf[bufpos++] = moff >> 0, i |= 0x01;
402 1199 63 if (moff & 0x0000ff00)
403 52 64 buf[bufpos++] = moff >> 8, i |= 0x02;
404 1199 65 if (moff & 0x00ff0000)
405 ##### 66 buf[bufpos++] = moff >> 16, i |= 0x04;
406 1199 67 if (moff & 0xff000000)
407 ##### 68 buf[bufpos++] = moff >> 24, i |= 0x08;
408 -
409 1199 69 if (msize & 0x00ff)
410 1199 70 buf[bufpos++] = msize >> 0, i |= 0x10;
411 1199 71 if (msize & 0xff00)
412 26 72 buf[bufpos++] = msize >> 8, i |= 0x20;
413 -
414 1199 73 *op = i;
415 -
416 1199 73 data += msize;
417 1199 73 moff += msize;
418 1199 73 msize = left;
419 -
420 1199 73 if (msize < 4096) {
421 - int j;
422 1199 74 val = 0;
423 20383 74-76 for (j = -RABIN_WINDOW; j < 0; j++)
424 19184 75,75 val = ((val << 8) | data[j])
425 19184 75 ^ T[val >> RABIN_SHIFT];
426 - }
427 - }
428 -
429 270276 77 if (bufpos >= bufsize - MAX_OP_SIZE) {
430 6167 78 void *tmp = buf;
431 6167 78 bufsize = bufsize * 3 / 2;
432 6167 78,79 if (max_size && bufsize >= max_size)
433 6167 80 bufsize = (unsigned int)(max_size + MAX_OP_SIZE + 1);
434 6167 81,82 if (max_size && bufpos > max_size)
435 6167 83 break;
436 ##### 84 buf = git__realloc(buf, bufsize);
437 ##### 85 if (!buf) {
438 ##### 86 git__free(tmp);
439 ##### 87 return -1;
440 - }
441 - }
442 - }
443 -
444 6322 89 if (inscnt)
445 6267 90 buf[bufpos - inscnt - 1] = inscnt;
446 -
447 6322 91,92 if (max_size && bufpos > max_size) {
448 6167 93 git_error_set(GIT_ERROR_NOMEMORY, "delta would be larger than maximum size");
449 6167 94 git__free(buf);
450 6167 95 return GIT_EBUFS;
451 - }
452 -
453 155 96 *out_len = bufpos;
454 155 96 *out = buf;
455 155 96 return 0;
456 - }
457 -
458 - /*
459 - * Delta application was heavily cribbed from BinaryDelta.java in JGit, which
460 - * itself was heavily cribbed from <code>patch-delta.c</code> in the
461 - * GIT project. The original delta patching code was written by
462 - * Nicolas Pitre <nico@cam.org>.
463 - */
464 -
465 25229 2 static int hdr_sz(
466 - size_t *size,
467 - const unsigned char **delta,
468 - const unsigned char *end)
469 - {
470 25229 2 const unsigned char *d = *delta;
471 25229 2 size_t r = 0;
472 25229 2 unsigned int c, shift = 0;
473 -
474 - do {
475 50775 3 if (d == end) {
476 ##### 4 git_error_set(GIT_ERROR_INVALID, "truncated delta");
477 ##### 5 return -1;
478 - }
479 -
480 50775 6 c = *d++;
481 50775 6 r |= (c & 0x7f) << shift;
482 50775 6 shift += 7;
483 50775 6 } while (c & 0x80);
484 25229 7 *delta = d;
485 25229 7 *size = r;
486 25229 7 return 0;
487 - }
488 -
489 ##### 2 int git_delta_read_header(
490 - size_t *base_out,
491 - size_t *result_out,
492 - const unsigned char *delta,
493 - size_t delta_len)
494 - {
495 ##### 2 const unsigned char *delta_end = delta + delta_len;
496 ##### 2,3,5 if ((hdr_sz(base_out, &delta, delta_end) < 0) ||
497 ##### 4 (hdr_sz(result_out, &delta, delta_end) < 0))
498 ##### 6 return -1;
499 ##### 7 return 0;
500 - }
501 -
502 - #define DELTA_HEADER_BUFFER_LEN 16
503 474 2 int git_delta_read_header_fromstream(
504 - size_t *base_sz, size_t *res_sz, git_packfile_stream *stream)
505 - {
506 - static const size_t buffer_len = DELTA_HEADER_BUFFER_LEN;
507 - unsigned char buffer[DELTA_HEADER_BUFFER_LEN];
508 - const unsigned char *delta, *delta_end;
509 - size_t len;
510 - ssize_t read;
511 -
512 474 2 len = read = 0;
513 948 2,9 while (len < buffer_len) {
514 549 3 read = git_packfile_stream_read(stream, &buffer[len], buffer_len - len);
515 -
516 549 4 if (read == 0)
517 75 5 break;
518 -
519 474 6 if (read == GIT_EBUFS)
520 ##### 7 continue;
521 -
522 474 8 len += read;
523 - }
524 -
525 474 10 delta = buffer;
526 474 10 delta_end = delta + len;
527 474 10,11,13 if ((hdr_sz(base_sz, &delta, delta_end) < 0) ||
528 474 12 (hdr_sz(res_sz, &delta, delta_end) < 0))
529 ##### 14 return -1;
530 -
531 474 15 return 0;
532 - }
533 -
534 12141 2 int git_delta_apply(
535 - void **out,
536 - size_t *out_len,
537 - const unsigned char *base,
538 - size_t base_len,
539 - const unsigned char *delta,
540 - size_t delta_len)
541 - {
542 12141 2 const unsigned char *delta_end = delta + delta_len;
543 - size_t base_sz, res_sz, alloc_sz;
544 - unsigned char *res_dp;
545 -
546 12141 2 *out = NULL;
547 12141 2 *out_len = 0;
548 -
549 - /*
550 - * Check that the base size matches the data we were given;
551 - * if not we would underflow while accessing data from the
552 - * base object, resulting in data corruption or segfault.
553 - */
554 12141 2-4 if ((hdr_sz(&base_sz, &delta, delta_end) < 0) || (base_sz != base_len)) {
555 1 5 git_error_set(GIT_ERROR_INVALID, "failed to apply delta: base size does not match given data");
556 1 6 return -1;
557 - }
558 -
559 12140 7,8 if (hdr_sz(&res_sz, &delta, delta_end) < 0) {
560 ##### 9 git_error_set(GIT_ERROR_INVALID, "failed to apply delta: base size does not match given data");
561 ##### 10 return -1;
562 - }
563 -
564 12140 11-17 GIT_ERROR_CHECK_ALLOC_ADD(&alloc_sz, res_sz, 1);
565 12140 18 res_dp = git__malloc(alloc_sz);
566 12140 19,20 GIT_ERROR_CHECK_ALLOC(res_dp);
567 -
568 12140 21 res_dp[res_sz] = '\0';
569 12140 21 *out = res_dp;
570 12140 21 *out_len = res_sz;
571 -
572 110195 21,65 while (delta < delta_end) {
573 98057 22 unsigned char cmd = *delta++;
574 98057 22 if (cmd & 0x80) {
575 - /* cmd is a copy instruction; copy from the base. */
576 56215 23 size_t off = 0, len = 0, end;
577 -
578 - #define ADD_DELTA(o, shift) { if (delta < delta_end) (o) |= ((unsigned) *delta++ << shift); else goto fail; }
579 56215 23-26,59 if (cmd & 0x01) ADD_DELTA(off, 0UL);
580 56214 27-30 if (cmd & 0x02) ADD_DELTA(off, 8UL);
581 56214 31-34 if (cmd & 0x04) ADD_DELTA(off, 16UL);
582 56214 35-38 if (cmd & 0x08) ADD_DELTA(off, 24UL);
583 -
584 56214 39-42 if (cmd & 0x10) ADD_DELTA(len, 0UL);
585 56214 43-46 if (cmd & 0x20) ADD_DELTA(len, 8UL);
586 56214 47-50 if (cmd & 0x40) ADD_DELTA(len, 16UL);
587 56214 51,52 if (!len) len = 0x10000;
588 - #undef ADD_DELTA
589 -
590 56214 53-56 if (GIT_ADD_SIZET_OVERFLOW(&end, off, len) ||
591 56214 56,57 base_len < end || res_sz < len)
592 - goto fail;
593 -
594 56213 58 memcpy(res_dp, base + off, len);
595 56213 58 res_dp += len;
596 56213 58 res_sz -= len;
597 -
598 41842 60 } else if (cmd) {
599 - /*
600 - * cmd is a literal insert instruction; copy from
601 - * the delta stream itself.
602 - */
603 41842 61,62 if (delta_end - delta < cmd || res_sz < cmd)
604 - goto fail;
605 41842 63 memcpy(res_dp, delta, cmd);
606 41842 63 delta += cmd;
607 41842 63 res_dp += cmd;
608 41842 63 res_sz -= cmd;
609 -
610 - } else {
611 - /* cmd == 0 is reserved for future encodings. */
612 ##### 64 goto fail;
613 - }
614 - }
615 -
616 12138 66,67 if (delta != delta_end || res_sz)
617 - goto fail;
618 12138 68 return 0;
619 -
620 - fail:
621 2 69 git__free(*out);
622 -
623 2 70 *out = NULL;
624 2 70 *out_len = 0;
625 -
626 2 70 git_error_set(GIT_ERROR_INVALID, "failed to apply delta");
627 2 71 return -1;
628 - }