1 /*
2  * Copyright (c) 2020 Ori Bernstein
3  * Copyright (c) 2021 Stefan Sperling <stsp@openbsd.org>
4  *
5  * Permission to use, copy, modify, and distribute this software for any
6  * purpose with or without fee is hereby granted, provided that the above
7  * copyright notice and this permission notice appear in all copies.
8  *
9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16  */
17 
18 #include "got_compat.h"
19 
20 #include <sys/types.h>
21 #include <sys/queue.h>
22 
23 #include <assert.h>
24 #include <errno.h>
25 #include <limits.h>
26 #include <stdint.h>
27 #include <stdio.h>
28 #include <stdlib.h>
29 #include <string.h>
30 
31 #include "got_error.h"
32 
33 #include "got_lib_deltify.h"
34 #include "murmurhash2.h"
35 
36 #ifndef MIN
37 #define	MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
38 #endif
39 
40 /*
41  * The algorihm used here is FastCDC (Fast Content-Defined Chunking)
42  * https://www.usenix.org/conference/atc16/technical-sessions/presentation/xia
43  */
44 
45 static const uint32_t geartab[256] = {
46     0x67ed26b7, 0x32da500c, 0x53d0fee0, 0xce387dc7, 0xcd406d90, 0x2e83a4d4,
47     0x9fc9a38d, 0xb67259dc, 0xca6b1722, 0x6d2ea08c, 0x235cea2e, 0x3149bb5f,
48     0x1beda787, 0x2a6b77d5, 0x2f22d9ac, 0x91fc0544, 0xe413acfa, 0x5a30ff7a,
49     0xad6fdde0, 0x444fd0f5, 0x7ad87864, 0x58c5ff05, 0x8d2ec336, 0x2371f853,
50     0x550f8572, 0x6aa448dd, 0x7c9ddbcf, 0x95221e14, 0x2a82ec33, 0xcbec5a78,
51     0xc6795a0d, 0x243995b7, 0x1c909a2f, 0x4fded51c, 0x635d334b, 0x0e2b9999,
52     0x2702968d, 0x856de1d5, 0x3325d60e, 0xeb6a7502, 0xec2a9844, 0x0905835a,
53     0xa1820375, 0xa4be5cab, 0x96a6c058, 0x2c2ccd70, 0xba40fce3, 0xd794c46b,
54     0x8fbae83e, 0xc3aa7899, 0x3d3ff8ed, 0xa0d42b5b, 0x571c0c97, 0xd2811516,
55     0xf7e7b96c, 0x4fd2fcbd, 0xe2fdec94, 0x282cc436, 0x78e8e95c, 0x80a3b613,
56     0xcfbee20c, 0xd4a32d1c, 0x2a12ff13, 0x6af82936, 0xe5630258, 0x8efa6a98,
57     0x294fb2d1, 0xdeb57086, 0x5f0fddb3, 0xeceda7ce, 0x4c87305f, 0x3a6d3307,
58     0xe22d2942, 0x9d060217, 0x1e42ed02, 0xb6f63b52, 0x4367f39f, 0x055cf262,
59     0x03a461b2, 0x5ef9e382, 0x386bc03a, 0x2a1e79c7, 0xf1a0058b, 0xd4d2dea9,
60     0x56baf37d, 0x5daff6cc, 0xf03a951d, 0xaef7de45, 0xa8f4581e, 0x3960b555,
61     0xffbfff6d, 0xbe702a23, 0x8f5b6d6f, 0x061739fb, 0x98696f47, 0x3fd596d4,
62     0x151eac6b, 0xa9fcc4f5, 0x69181a12, 0x3ac5a107, 0xb5198fe7, 0x96bcb1da,
63     0x1b5ddf8e, 0xc757d650, 0x65865c3a, 0x8fc0a41a, 0x87435536, 0x99eda6f2,
64     0x41874794, 0x29cff4e8, 0xb70efd9a, 0x3103f6e7, 0x84d2453b, 0x15a450bd,
65     0x74f49af1, 0x60f664b1, 0xa1c86935, 0xfdafbce1, 0xe36353e3, 0x5d9ba739,
66     0xbc0559ba, 0x708b0054, 0xd41d808c, 0xb2f31723, 0x9027c41f, 0xf136d165,
67     0xb5374b12, 0x9420a6ac, 0x273958b6, 0xe6c2fad0, 0xebdc1f21, 0xfb33af8b,
68     0xc71c25cd, 0xe9a2d8e5, 0xbeb38a50, 0xbceb7cc2, 0x4e4e73f0, 0xcd6c251d,
69     0xde4c032c, 0x4b04ac30, 0x725b8b21, 0x4eb8c33b, 0x20d07b75, 0x0567aa63,
70     0xb56b2bb7, 0xc1f5fd3a, 0xcafd35ca, 0x470dd4da, 0xfe4f94cd, 0xfb8de424,
71     0xe8dbcf40, 0xfe50a37a, 0x62db5b5d, 0xf32f4ab6, 0x2c4a8a51, 0x18473dc0,
72     0xfe0cbb6e, 0xfe399efd, 0xdf34ecc9, 0x6ccd5055, 0x46097073, 0x139135c2,
73     0x721c76f6, 0x1c6a94b4, 0x6eee014d, 0x8a508e02, 0x3da538f5, 0x280d394f,
74     0x5248a0c4, 0x3ce94c6c, 0x9a71ad3a, 0x8493dd05, 0xe43f0ab6, 0x18e4ed42,
75     0x6c5c0e09, 0x42b06ec9, 0x8d330343, 0xa45b6f59, 0x2a573c0c, 0xd7fd3de6,
76     0xeedeab68, 0x5c84dafc, 0xbbd1b1a8, 0xa3ce1ad1, 0x85b70bed, 0xb6add07f,
77     0xa531309c, 0x8f8ab852, 0x564de332, 0xeac9ed0c, 0x73da402c, 0x3ec52761,
78     0x43af2f4d, 0xd6ff45c8, 0x4c367462, 0xd553bd6a, 0x44724855, 0x3b2aa728,
79     0x56e5eb65, 0xeaf16173, 0x33fa42ff, 0xd714bb5d, 0xfbd0a3b9, 0xaf517134,
80     0x9416c8cd, 0x534cf94f, 0x548947c2, 0x34193569, 0x32f4389a, 0xfe7028bc,
81     0xed73b1ed, 0x9db95770, 0x468e3922, 0x0440c3cd, 0x60059a62, 0x33504562,
82     0x2b229fbd, 0x5174dca5, 0xf7028752, 0xd63c6aa8, 0x31276f38, 0x0646721c,
83     0xb0191da8, 0xe00e6de0, 0x9eac1a6e, 0x9f7628a5, 0xed6c06ea, 0x0bb8af15,
84     0xf119fb12, 0x38693c1c, 0x732bc0fe, 0x84953275, 0xb82ec888, 0x33a4f1b3,
85     0x3099835e, 0x028a8782, 0x5fdd51d7, 0xc6c717b3, 0xb06caf71, 0x17c8c111,
86     0x61bad754, 0x9fd03061, 0xe09df1af, 0x3bc9eb73, 0x85878413, 0x9889aaf2,
87     0x3f5a9e46, 0x42c9f01f, 0x9984a4f4, 0xd5de43cc, 0xd294daed, 0xbecba2d2,
88     0xf1f6e72c, 0x5551128a, 0x83af87e2, 0x6f0342ba,
89 };
90 
91 static const struct got_error *addblk(struct got_delta_table *, FILE *,
92     uint8_t *, off_t, off_t, off_t, uint32_t);
93 
94 static uint32_t
95 hashblk(const unsigned char *p, off_t n, uint32_t seed)
96 {
97 	return murmurhash2(p, n, seed);
98 }
99 
100 static const struct got_error *
101 lookup(int *n, struct got_delta_table *dt, FILE *f, off_t file_offset0,
102     off_t len, off_t offset, uint32_t h)
103 {
104 	struct got_delta_block *block;
105 	uint8_t buf[GOT_DELTIFY_MAXCHUNK];
106 	uint8_t buf2[GOT_DELTIFY_MAXCHUNK];
107 	size_t r = 0;
108 	int i;
109 
110 	for (i = h % dt->size; dt->offs[i] != 0; i = (i + 1) % dt->size) {
111 		block = &dt->blocks[dt->offs[i] - 1];
112 		if (block->len != len || block->hash != h)
113 			continue;
114 
115 		if (r == 0) {
116 			if (fseeko(f, file_offset0 + offset, SEEK_SET) == -1)
117 				return got_error_from_errno("fseeko");
118 			r = fread(buf, 1, len, f);
119 			if (r != len) {
120 				if (!ferror(f))
121 					break;		/* why? */
122 				return got_ferror(f, GOT_ERR_IO);
123 			}
124 		}
125 
126 		if (fseeko(f, file_offset0 + block->offset, SEEK_SET) == -1)
127 			return got_error_from_errno("fseeko");
128 		if (fread(buf2, 1, len, f) != len)
129 			return got_ferror(f, GOT_ERR_IO);
130 		if (memcmp(buf, buf2, len) == 0)
131 			break;
132 	}
133 
134 	*n = i;
135 	return NULL;
136 }
137 
138 static const struct got_error *
139 lookup_mem(int *n, struct got_delta_table *dt, uint8_t *basedata,
140     off_t basefile_offset0, uint8_t *p, off_t len, uint32_t h)
141 {
142 	struct got_delta_block *block;
143 	uint8_t *d;
144 	int i;
145 
146 	for (i = h % dt->size; dt->offs[i] != 0; i = (i + 1) % dt->size) {
147 		block = &dt->blocks[dt->offs[i] - 1];
148 		if (len == block->len && h == block->hash) {
149 			d = basedata + basefile_offset0 + block->offset;
150 			if (memcmp(d, p, len) == 0)
151 				break;
152 		}
153 	}
154 
155 	*n = i;
156 	return NULL;
157 }
158 
159 static const struct got_error *
160 resizeht(struct got_delta_table *dt, FILE *f, off_t offset0, uint8_t *data,
161     off_t len)
162 {
163 	const struct got_error *err;
164 	struct got_delta_block *b;
165 	size_t newsize, oldsize;
166 	int i, n;
167 
168 	if (dt->nblocks == dt->nalloc) {
169 		newsize = dt->nalloc + 256;
170 		b = reallocarray(dt->blocks, newsize, sizeof(*dt->blocks));
171 		if (b == NULL)
172 			return got_error_from_errno("reallocarray");
173 		dt->blocks = b;
174 		dt->nalloc = newsize;
175 	}
176 
177 	if (dt->blocks == NULL || dt->len * 100 / dt->size > 70) {
178 		oldsize = dt->size;
179 		dt->size *= 2;
180 		free(dt->offs);
181 		dt->offs = calloc(dt->size, sizeof(*dt->offs));
182 		if (dt->offs == NULL) {
183 			dt->size = oldsize;
184 			return got_error_from_errno("calloc");
185 		}
186 
187 		for (i = 0; i < dt->nblocks; ++i) {
188 			b = &dt->blocks[i];
189 			if (f)
190 				err = lookup(&n, dt, f, offset0, b->len,
191 				    b->offset, b->hash);
192 			else
193 				err = lookup_mem(&n, dt, data, offset0,
194 				    data + b->offset, b->len, b->hash);
195 			if (err) {
196 				free(dt->offs);
197 				dt->offs = NULL;
198 				dt->size = oldsize;
199 				return err;
200 			}
201 			assert(dt->offs[n] == 0);
202 			dt->offs[n] = i + 1;
203 		}
204 	}
205 
206 	return NULL;
207 }
208 
209 static const struct got_error *
210 addblk(struct got_delta_table *dt, FILE *f, uint8_t *data, off_t file_offset0,
211     off_t len, off_t offset, uint32_t h)
212 {
213 	const struct got_error *err;
214 	struct got_delta_block *block;
215 	int i;
216 
217 	if (len == 0)
218 		return NULL;
219 
220 	err = resizeht(dt, f, file_offset0, data, len);
221 	if (err)
222 		return err;
223 
224 	if (f)
225 		err = lookup(&i, dt, f, file_offset0, len, offset, h);
226 	else
227 		err = lookup_mem(&i, dt, data, file_offset0, data + offset,
228 		    len, h);
229 	if (err)
230 		return err;
231 
232 	if (dt->offs[i] != 0)
233 		return NULL;	/* found */
234 
235 	dt->offs[i] = dt->nblocks + 1;
236 	block = &dt->blocks[dt->nblocks];
237 	block->len = len;
238 	block->offset = offset;
239 	block->hash = h;
240 
241 	dt->nblocks++;
242 	dt->len++;
243 
244 	return NULL;
245 }
246 
247 static const struct got_error *
248 lookupblk(struct got_delta_block **block, struct got_delta_table *dt,
249     unsigned char *p, off_t len, uint32_t seed, FILE *basefile,
250     off_t basefile_offset0)
251 {
252 	int i;
253 	uint32_t h;
254 	uint8_t buf[GOT_DELTIFY_MAXCHUNK];
255 	struct got_delta_block *b;
256 	size_t r;
257 
258 	*block = NULL;
259 
260 	h = hashblk(p, len, seed);
261 	
262 	for (i = h % dt->size; dt->offs[i] != 0; i = (i + 1) % dt->size) {
263 		b = &dt->blocks[dt->offs[i] - 1];
264 		if (b->hash != h || b->len != len)
265 			continue;
266 		if (fseeko(basefile, basefile_offset0 + b->offset,
267 		    SEEK_SET) == -1)
268 			return got_error_from_errno("fseeko");
269 		r = fread(buf, 1, len, basefile);
270 		if (r != len)
271 			return got_ferror(basefile, GOT_ERR_IO);
272 		if (memcmp(p, buf, len) == 0) {
273 			*block = b;
274 			break;
275 		}
276 	}
277 	return NULL;
278 }
279 
280 static const struct got_error *
281 lookupblk_mem(struct got_delta_block **block, struct got_delta_table *dt,
282     unsigned char *p, off_t len, uint32_t seed, uint8_t *basedata,
283     off_t basefile_offset0)
284 {
285 	const struct got_error *err;
286 	int n;
287 	uint32_t h;
288 
289 	*block = NULL;
290 	h = hashblk(p, len, seed);
291 	err = lookup_mem(&n, dt, basedata, basefile_offset0, p, len, h);
292 	if (err)
293 		return err;
294 	if (dt->offs[n] != 0)
295 		*block = &dt->blocks[dt->offs[n] - 1];
296 	return NULL;
297 }
298 
299 static const struct got_error *
300 nextblk(uint8_t *buf, off_t *blocklen, FILE *f)
301 {
302 	uint32_t gh;
303 	const unsigned char *p;
304 	size_t r;
305 	off_t pos = ftello(f);
306 
307 	*blocklen = 0;
308 
309 	r = fread(buf, 1, GOT_DELTIFY_MAXCHUNK, f);
310 	if (r == 0 && ferror(f))
311 		return got_ferror(f, GOT_ERR_IO);
312 	if (r < GOT_DELTIFY_MINCHUNK)
313 		return NULL; /* no more delta-worthy blocks left */
314 
315 	/* Got a deltifiable block. Find the split-point where it ends. */
316 	p = buf + GOT_DELTIFY_MINCHUNK;
317 	gh = 0;
318 	while (p != buf + r) {
319 		gh = (gh << 1) + geartab[*p++];
320 		if ((gh & GOT_DELTIFY_SPLITMASK) == 0)
321 			break;
322 	}
323 
324 	*blocklen = (p - buf);
325 	if (fseeko(f, pos + *blocklen, SEEK_SET) == -1)
326 		return got_error_from_errno("fseeko");
327 
328 	return NULL;
329 }
330 
331 static const struct got_error *
332 nextblk_mem(off_t *blocklen, uint8_t *data, off_t fileoffset, off_t filesize)
333 {
334 	uint32_t gh;
335 	const unsigned char *p;
336 
337 	*blocklen = 0;
338 
339 	if (fileoffset >= filesize ||
340 	    filesize - fileoffset < GOT_DELTIFY_MINCHUNK)
341 		return NULL; /* no more delta-worthy blocks left */
342 
343 	/* Got a deltifiable block. Find the split-point where it ends. */
344 	p = data + fileoffset + GOT_DELTIFY_MINCHUNK;
345 	gh = 0;
346 	while (p != data + MIN(fileoffset + GOT_DELTIFY_MAXCHUNK, filesize)) {
347 		gh = (gh << 1) + geartab[*p++];
348 		if ((gh & GOT_DELTIFY_SPLITMASK) == 0)
349 			break;
350 	}
351 
352 	*blocklen = (p - (data + fileoffset));
353 	return NULL;
354 }
355 
356 const struct got_error *
357 got_deltify_init(struct got_delta_table **dt, FILE *f, off_t fileoffset,
358     off_t filesize, uint32_t seed)
359 {
360 	const struct got_error *err = NULL;
361 	uint32_t h;
362 	const off_t offset0 = fileoffset;
363 
364 	*dt = calloc(1, sizeof(**dt));
365 	if (*dt == NULL)
366 		return got_error_from_errno("calloc");
367 
368 	(*dt)->nblocks = 0;
369 	(*dt)->nalloc = 128;
370 	(*dt)->blocks = calloc((*dt)->nalloc, sizeof(struct got_delta_block));
371 	if ((*dt)->blocks == NULL) {
372 		err = got_error_from_errno("calloc");
373 		goto done;
374 	}
375 
376 	(*dt)->size = 128;
377 	(*dt)->offs = calloc((*dt)->size, sizeof(*(*dt)->offs));
378 	if ((*dt)->offs == NULL) {
379 		err = got_error_from_errno("calloc");
380 		goto done;
381 	}
382 
383 	if (fseeko(f, fileoffset, SEEK_SET) == -1)
384 		return got_error_from_errno("fseeko");
385 
386 	while (fileoffset < filesize) {
387 		uint8_t buf[GOT_DELTIFY_MAXCHUNK];
388 		off_t blocklen;
389 		err = nextblk(buf, &blocklen, f);
390 		if (err)
391 			goto done;
392 		if (blocklen == 0)
393 			break;
394 		h = hashblk(buf, blocklen, seed);
395 		err = addblk(*dt, f, NULL, offset0, blocklen,
396 		    fileoffset - offset0, h);
397 		if (err)
398 			goto done;
399 		fileoffset += blocklen;
400 		if (fseeko(f, fileoffset, SEEK_SET) == -1)
401 			return got_error_from_errno("fseeko");
402 	}
403 done:
404 	if (err) {
405 		free((*dt)->blocks);
406 		free(*dt);
407 		*dt = NULL;
408 	}
409 
410 	return err;
411 }
412 
413 const struct got_error *
414 got_deltify_init_mem(struct got_delta_table **dt, uint8_t *data,
415     off_t fileoffset, off_t filesize, uint32_t seed)
416 {
417 	const struct got_error *err = NULL;
418 	uint32_t h;
419 	const off_t offset0 = fileoffset;
420 
421 	*dt = calloc(1, sizeof(**dt));
422 	if (*dt == NULL)
423 		return got_error_from_errno("calloc");
424 
425 	(*dt)->nblocks = 0;
426 	(*dt)->nalloc = 128;
427 	(*dt)->blocks = calloc((*dt)->nalloc, sizeof(struct got_delta_block));
428 	if ((*dt)->blocks == NULL) {
429 		err = got_error_from_errno("calloc");
430 		goto done;
431 	}
432 
433 	(*dt)->size = 128;
434 	(*dt)->offs = calloc((*dt)->size, sizeof(*(*dt)->offs));
435 	if ((*dt)->offs == NULL) {
436 		err = got_error_from_errno("calloc");
437 		goto done;
438 	}
439 
440 	while (fileoffset < filesize) {
441 		off_t blocklen;
442 		err = nextblk_mem(&blocklen, data, fileoffset, filesize);
443 		if (err)
444 			goto done;
445 		if (blocklen == 0)
446 			break;
447 		h = hashblk(data + fileoffset, blocklen, seed);
448 		err = addblk(*dt, NULL, data, offset0, blocklen,
449 		    fileoffset - offset0, h);
450 		if (err)
451 			goto done;
452 		fileoffset += blocklen;
453 	}
454 done:
455 	if (err) {
456 		free((*dt)->blocks);
457 		free(*dt);
458 		*dt = NULL;
459 	}
460 
461 	return err;
462 }
463 
464 void
465 got_deltify_free(struct got_delta_table *dt)
466 {
467 	if (dt == NULL)
468 		return;
469 	free(dt->blocks);
470 	free(dt->offs);
471 	free(dt);
472 }
473 
474 static const struct got_error *
475 emitdelta(struct got_delta_instruction **deltas, size_t *nalloc, int *ndeltas,
476     const size_t alloc_chunk_size, int copy, off_t offset, off_t len)
477 {
478 	struct got_delta_instruction *d, *p;
479 
480 	if (*nalloc < *ndeltas + alloc_chunk_size) {
481 		p = reallocarray(*deltas, *nalloc + alloc_chunk_size,
482 		    sizeof(struct got_delta_instruction));
483 		if (p == NULL)
484 			return got_error_from_errno("reallocarray");
485 		*deltas = p;
486 		*nalloc += alloc_chunk_size;
487 	}
488 	*ndeltas += 1;
489 	d = &(*deltas)[*ndeltas - 1];
490 	d->copy = copy;
491 	d->offset = offset;
492 	d->len = len;
493 	return NULL;
494 }
495 
496 static const struct got_error *
497 stretchblk(FILE *basefile, off_t base_offset0, struct got_delta_block *block,
498     FILE *f, off_t filesize, off_t *blocklen)
499 {
500 	uint8_t basebuf[GOT_DELTIFY_MAXCHUNK], buf[GOT_DELTIFY_MAXCHUNK];
501 	size_t base_r, r, i;
502 	int buf_equal = 1;
503 
504 	if (fseeko(basefile, base_offset0 + block->offset + *blocklen,
505 	    SEEK_SET) == -1)
506 		return got_error_from_errno("fseeko");
507 
508 	while (buf_equal && *blocklen < (1 << 24) - 1) {
509 		base_r = fread(basebuf, 1, sizeof(basebuf), basefile);
510 		if (base_r == 0) {
511 			if (ferror(basefile))
512 				return got_ferror(basefile, GOT_ERR_IO);
513 			break;
514 		}
515 		r = fread(buf, 1, sizeof(buf), f);
516 		if (r == 0) {
517 			if (ferror(f))
518 				return got_ferror(f, GOT_ERR_IO);
519 			break;
520 		}
521 		for (i = 0; i < MIN(base_r, r); i++) {
522 			if (buf[i] != basebuf[i]) {
523 				buf_equal = 0;
524 				break;
525 			}
526 			(*blocklen)++;
527 		}
528 	}
529 
530 	return NULL;
531 }
532 
533 static const struct got_error *
534 stretchblk_file_mem(uint8_t *basedata, off_t base_offset0, off_t basefile_size,
535      struct got_delta_block *block, FILE *f, off_t filesize, off_t *blocklen)
536 {
537 	uint8_t buf[GOT_DELTIFY_MAXCHUNK];
538 	size_t r, i;
539 	int buf_equal = 1;
540 	off_t base_offset = base_offset0 + block->offset + *blocklen;
541 
542 	if (base_offset > basefile_size) {
543 		return got_error_fmt(GOT_ERR_RANGE,
544 		    "read beyond the size of delta base at offset %lld",
545 		    (long long)base_offset);
546 	}
547 
548 	while (buf_equal && *blocklen < (1 << 24) - 1) {
549 		if (base_offset + *blocklen >= basefile_size)
550 			break;
551 		r = fread(buf, 1, sizeof(buf), f);
552 		if (r == 0) {
553 			if (ferror(f))
554 				return got_ferror(f, GOT_ERR_IO);
555 			break;
556 		}
557 		for (i = 0; i < MIN(basefile_size - base_offset, r); i++) {
558 			if (buf[i] != *(basedata + base_offset + i)) {
559 				buf_equal = 0;
560 				break;
561 			}
562 			(*blocklen)++;
563 		}
564 	}
565 
566 	return NULL;
567 }
568 
569 static const struct got_error *
570 stretchblk_mem_file(FILE *basefile, off_t base_offset0,
571     struct got_delta_block *block, uint8_t *data, off_t fileoffset,
572     off_t filesize, off_t *blocklen)
573 {
574 	uint8_t basebuf[GOT_DELTIFY_MAXCHUNK];
575 	size_t base_r, i;
576 	int buf_equal = 1;
577 
578 	if (fileoffset > filesize) {
579 		return got_error_fmt(GOT_ERR_RANGE,
580 		    "read beyond the size of deltify file at offset %lld",
581 		    (long long)fileoffset);
582 	}
583 
584 	if (fseeko(basefile, base_offset0 + block->offset + *blocklen,
585 	    SEEK_SET) == -1)
586 		return got_error_from_errno("fseeko");
587 
588 	while (buf_equal && *blocklen < (1 << 24) - 1) {
589 		if (fileoffset + *blocklen >= filesize)
590 			break;
591 		base_r = fread(basebuf, 1, sizeof(basebuf), basefile);
592 		if (base_r == 0) {
593 			if (ferror(basefile))
594 				return got_ferror(basefile, GOT_ERR_IO);
595 			break;
596 		}
597 		for (i = 0; i < MIN(base_r, filesize - fileoffset); i++) {
598 			if (*(data + fileoffset + i) != basebuf[i]) {
599 				buf_equal = 0;
600 				break;
601 			}
602 			(*blocklen)++;
603 		}
604 	}
605 
606 	return NULL;
607 }
608 
609 static const struct got_error *
610 stretchblk_mem_mem(uint8_t *basedata, off_t base_offset0, off_t basefile_size,
611     struct got_delta_block *block, uint8_t *data, off_t fileoffset,
612     off_t filesize, off_t *blocklen)
613 {
614 	off_t i, maxlen;
615 	off_t base_offset = base_offset0 + block->offset + *blocklen;
616 	uint8_t *p, *q;
617 
618 	if (base_offset > basefile_size) {
619 		return got_error_fmt(GOT_ERR_RANGE,
620 		    "read beyond the size of delta base at offset %lld",
621 		    (long long)base_offset);
622 	}
623 
624 	if (fileoffset > filesize) {
625 		return got_error_fmt(GOT_ERR_RANGE,
626 		    "read beyond the size of deltify file at offset %lld",
627 		    (long long)fileoffset);
628 	}
629 
630 	p = data + fileoffset;
631 	q = basedata + base_offset;
632 	maxlen = MIN(basefile_size - base_offset, filesize - fileoffset);
633 	for (i = 0; i < maxlen && *blocklen < (1 << 24) - 1; i++) {
634 		if (p[i] != q[i])
635 			break;
636 		(*blocklen)++;
637 	}
638 
639 	return NULL;
640 }
641 
642 const struct got_error *
643 got_deltify(struct got_delta_instruction **deltas, int *ndeltas,
644     FILE *f, off_t fileoffset, off_t filesize, uint32_t seed,
645     struct got_delta_table *dt, FILE *basefile,
646     off_t basefile_offset0, off_t basefile_size)
647 {
648 	const struct got_error *err = NULL;
649 	const off_t offset0 = fileoffset;
650 	size_t nalloc = 0;
651 	const size_t alloc_chunk_size = 64;
652 
653 	*deltas = NULL;
654 	*ndeltas = 0;
655 
656 	/*
657 	 * offset0 indicates where data to be deltified begins.
658 	 * For example, we want to avoid deltifying a Git object header at
659 	 * the beginning of the file.
660 	 */
661 	if (fseeko(f, offset0, SEEK_SET) == -1)
662 		return got_error_from_errno("fseeko");
663 
664 	*deltas = reallocarray(NULL, alloc_chunk_size,
665 	    sizeof(struct got_delta_instruction));
666 	if (*deltas == NULL)
667 		return got_error_from_errno("reallocarray");
668 	nalloc = alloc_chunk_size;
669 
670 	while (fileoffset < filesize) {
671 		uint8_t buf[GOT_DELTIFY_MAXCHUNK];
672 		off_t blocklen;
673 		struct got_delta_block *block;
674 		err = nextblk(buf, &blocklen, f);
675 		if (err)
676 			break;
677 		if (blocklen == 0) {
678 			/* Source remainder from the file itself. */
679 			if (fileoffset < filesize) {
680 				err = emitdelta(deltas, &nalloc, ndeltas,
681 				    alloc_chunk_size, 0, fileoffset - offset0,
682 				    filesize - fileoffset);
683 			}
684 			break;
685 		}
686 		err = lookupblk(&block, dt, buf, blocklen, seed, basefile,
687 		    basefile_offset0);
688 		if (err)
689 			break;
690 		if (block != NULL) {
691 			/*
692 			 * We have found a matching block in the delta base.
693 			 * Attempt to stretch the block as far as possible and
694 			 * generate a copy instruction.
695 			 */
696 			err = stretchblk(basefile, basefile_offset0, block,
697 			    f, filesize, &blocklen);
698 			if (err)
699 				break;
700 			err = emitdelta(deltas, &nalloc, ndeltas,
701 			    alloc_chunk_size, 1, block->offset, blocklen);
702 			if (err)
703 				break;
704 		} else {
705 			/*
706 			 * No match.
707 			 * This block needs to be sourced from the file itself.
708 			 */
709 			err = emitdelta(deltas, &nalloc, ndeltas,
710 			    alloc_chunk_size, 0, fileoffset - offset0, blocklen);
711 			if (err)
712 				break;
713 		}
714 		fileoffset += blocklen;
715 		if (fseeko(f, fileoffset, SEEK_SET) == -1) {
716 			err = got_error_from_errno("fseeko");
717 			break;
718 		}
719 	}
720 
721 	if (err) {
722 		free(*deltas);
723 		*deltas = NULL;
724 		*ndeltas = 0;
725 	}
726 	return err;
727 }
728 
729 const struct got_error *
730 got_deltify_file_mem(struct got_delta_instruction **deltas, int *ndeltas,
731     FILE *f, off_t fileoffset, off_t filesize, uint32_t seed,
732     struct got_delta_table *dt, uint8_t *basedata,
733     off_t basefile_offset0, off_t basefile_size)
734 {
735 	const struct got_error *err = NULL;
736 	const off_t offset0 = fileoffset;
737 	size_t nalloc = 0;
738 	const size_t alloc_chunk_size = 64;
739 
740 	*deltas = NULL;
741 	*ndeltas = 0;
742 
743 	/*
744 	 * offset0 indicates where data to be deltified begins.
745 	 * For example, we want to avoid deltifying a Git object header at
746 	 * the beginning of the file.
747 	 */
748 	if (fseeko(f, offset0, SEEK_SET) == -1)
749 		return got_error_from_errno("fseeko");
750 
751 	*deltas = reallocarray(NULL, alloc_chunk_size,
752 	    sizeof(struct got_delta_instruction));
753 	if (*deltas == NULL)
754 		return got_error_from_errno("reallocarray");
755 	nalloc = alloc_chunk_size;
756 
757 	while (fileoffset < filesize) {
758 		uint8_t buf[GOT_DELTIFY_MAXCHUNK];
759 		off_t blocklen;
760 		struct got_delta_block *block;
761 		err = nextblk(buf, &blocklen, f);
762 		if (err)
763 			break;
764 		if (blocklen == 0) {
765 			/* Source remainder from the file itself. */
766 			if (fileoffset < filesize) {
767 				err = emitdelta(deltas, &nalloc, ndeltas,
768 				    alloc_chunk_size, 0, fileoffset - offset0,
769 				    filesize - fileoffset);
770 			}
771 			break;
772 		}
773 		err = lookupblk_mem(&block, dt, buf, blocklen, seed, basedata,
774 		    basefile_offset0);
775 		if (err)
776 			break;
777 		if (block != NULL) {
778 			/*
779 			 * We have found a matching block in the delta base.
780 			 * Attempt to stretch the block as far as possible and
781 			 * generate a copy instruction.
782 			 */
783 			err = stretchblk_file_mem(basedata, basefile_offset0,
784 			    basefile_size, block, f, filesize, &blocklen);
785 			if (err)
786 				break;
787 			err = emitdelta(deltas, &nalloc, ndeltas,
788 			    alloc_chunk_size, 1, block->offset, blocklen);
789 			if (err)
790 				break;
791 		} else {
792 			/*
793 			 * No match.
794 			 * This block needs to be sourced from the file itself.
795 			 */
796 			err = emitdelta(deltas, &nalloc, ndeltas,
797 			    alloc_chunk_size, 0, fileoffset - offset0, blocklen);
798 			if (err)
799 				break;
800 		}
801 		fileoffset += blocklen;
802 		if (fseeko(f, fileoffset, SEEK_SET) == -1) {
803 			err = got_error_from_errno("fseeko");
804 			break;
805 		}
806 	}
807 
808 	if (err) {
809 		free(*deltas);
810 		*deltas = NULL;
811 		*ndeltas = 0;
812 	}
813 	return err;
814 }
815 
816 const struct got_error *
817 got_deltify_mem_file(struct got_delta_instruction **deltas, int *ndeltas,
818     uint8_t *data, off_t fileoffset, off_t filesize, uint32_t seed,
819     struct got_delta_table *dt, FILE *basefile,
820     off_t basefile_offset0, off_t basefile_size)
821 {
822 	const struct got_error *err = NULL;
823 	const off_t offset0 = fileoffset;
824 	size_t nalloc = 0;
825 	const size_t alloc_chunk_size = 64;
826 
827 	*deltas = NULL;
828 	*ndeltas = 0;
829 
830 	*deltas = reallocarray(NULL, alloc_chunk_size,
831 	    sizeof(struct got_delta_instruction));
832 	if (*deltas == NULL)
833 		return got_error_from_errno("reallocarray");
834 	nalloc = alloc_chunk_size;
835 
836 	while (fileoffset < filesize) {
837 		off_t blocklen;
838 		struct got_delta_block *block;
839 		err = nextblk_mem(&blocklen, data, fileoffset, filesize);
840 		if (err)
841 			break;
842 		if (blocklen == 0) {
843 			/* Source remainder from the file itself. */
844 			if (fileoffset < filesize) {
845 				err = emitdelta(deltas, &nalloc, ndeltas,
846 				    alloc_chunk_size, 0, fileoffset - offset0,
847 				    filesize - fileoffset);
848 			}
849 			break;
850 		}
851 		err = lookupblk(&block, dt, data + fileoffset, blocklen, seed,
852 		    basefile, basefile_offset0);
853 		if (err)
854 			break;
855 		if (block != NULL) {
856 			/*
857 			 * We have found a matching block in the delta base.
858 			 * Attempt to stretch the block as far as possible and
859 			 * generate a copy instruction.
860 			 */
861 			err = stretchblk_mem_file(basefile, basefile_offset0,
862 			    block, data, fileoffset + blocklen, filesize,
863 			    &blocklen);
864 			if (err)
865 				break;
866 			err = emitdelta(deltas, &nalloc, ndeltas,
867 			    alloc_chunk_size, 1, block->offset, blocklen);
868 			if (err)
869 				break;
870 		} else {
871 			/*
872 			 * No match.
873 			 * This block needs to be sourced from the file itself.
874 			 */
875 			err = emitdelta(deltas, &nalloc, ndeltas,
876 			    alloc_chunk_size, 0, fileoffset - offset0, blocklen);
877 			if (err)
878 				break;
879 		}
880 		fileoffset += blocklen;
881 	}
882 
883 	if (err) {
884 		free(*deltas);
885 		*deltas = NULL;
886 		*ndeltas = 0;
887 	}
888 	return err;
889 }
890 
891 const struct got_error *
892 got_deltify_mem_mem(struct got_delta_instruction **deltas, int *ndeltas,
893     uint8_t *data, off_t fileoffset, off_t filesize, uint32_t seed,
894     struct got_delta_table *dt, uint8_t *basedata,
895     off_t basefile_offset0, off_t basefile_size)
896 {
897 	const struct got_error *err = NULL;
898 	const off_t offset0 = fileoffset;
899 	size_t nalloc = 0;
900 	const size_t alloc_chunk_size = 64;
901 
902 	*deltas = NULL;
903 	*ndeltas = 0;
904 
905 	*deltas = reallocarray(NULL, alloc_chunk_size,
906 	    sizeof(struct got_delta_instruction));
907 	if (*deltas == NULL)
908 		return got_error_from_errno("reallocarray");
909 	nalloc = alloc_chunk_size;
910 
911 	while (fileoffset < filesize) {
912 		off_t blocklen;
913 		struct got_delta_block *block;
914 		err = nextblk_mem(&blocklen, data, fileoffset, filesize);
915 		if (err)
916 			break;
917 		if (blocklen == 0) {
918 			/* Source remainder from the file itself. */
919 			if (fileoffset < filesize) {
920 				err = emitdelta(deltas, &nalloc, ndeltas,
921 				    alloc_chunk_size, 0, fileoffset - offset0,
922 				    filesize - fileoffset);
923 			}
924 			break;
925 		}
926 		err = lookupblk_mem(&block, dt, data + fileoffset, blocklen,
927 		    seed, basedata, basefile_offset0);
928 		if (err)
929 			break;
930 		if (block != NULL) {
931 			/*
932 			 * We have found a matching block in the delta base.
933 			 * Attempt to stretch the block as far as possible and
934 			 * generate a copy instruction.
935 			 */
936 			err = stretchblk_mem_mem(basedata, basefile_offset0,
937 			    basefile_size, block, data, fileoffset + blocklen,
938 			    filesize, &blocklen);
939 			if (err)
940 				break;
941 			err = emitdelta(deltas, &nalloc, ndeltas,
942 			    alloc_chunk_size, 1, block->offset, blocklen);
943 			if (err)
944 				break;
945 		} else {
946 			/*
947 			 * No match.
948 			 * This block needs to be sourced from the file itself.
949 			 */
950 			err = emitdelta(deltas, &nalloc, ndeltas,
951 			    alloc_chunk_size, 0, fileoffset - offset0, blocklen);
952 			if (err)
953 				break;
954 		}
955 		fileoffset += blocklen;
956 	}
957 
958 	if (err) {
959 		free(*deltas);
960 		*deltas = NULL;
961 		*ndeltas = 0;
962 	}
963 	return err;
964 }