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