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