2 56e7a15f 2021-03-10 stsp * Copyright (c) 2020 Ori Bernstein
3 69aa0e90 2021-03-10 stsp * Copyright (c) 2021 Stefan Sperling <stsp@openbsd.org>
5 2a0e67f7 2021-03-10 stsp * Permission to use, copy, modify, and distribute this software for any
6 2a0e67f7 2021-03-10 stsp * purpose with or without fee is hereby granted, provided that the above
7 2a0e67f7 2021-03-10 stsp * copyright notice and this permission notice appear in all copies.
9 2a0e67f7 2021-03-10 stsp * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 2a0e67f7 2021-03-10 stsp * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 2a0e67f7 2021-03-10 stsp * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 2a0e67f7 2021-03-10 stsp * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 2a0e67f7 2021-03-10 stsp * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 2a0e67f7 2021-03-10 stsp * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 2a0e67f7 2021-03-10 stsp * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18 f364801d 2021-03-10 stsp #include <sys/types.h>
19 f364801d 2021-03-10 stsp #include <sys/queue.h>
21 f364801d 2021-03-10 stsp #include <assert.h>
22 22403ab7 2021-03-22 naddy #include <endian.h>
23 69aa0e90 2021-03-10 stsp #include <errno.h>
24 f364801d 2021-03-10 stsp #include <limits.h>
25 f364801d 2021-03-10 stsp #include <stdint.h>
26 f364801d 2021-03-10 stsp #include <stdio.h>
27 f364801d 2021-03-10 stsp #include <stdlib.h>
28 f364801d 2021-03-10 stsp #include <string.h>
30 f364801d 2021-03-10 stsp #include "got_error.h"
32 69aa0e90 2021-03-10 stsp #include "got_lib_deltify.h"
33 2b474c25 2022-02-11 stsp #include "murmurhash2.h"
36 69aa0e90 2021-03-10 stsp #define MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
40 f736d93a 2021-10-07 stsp * The algorihm used here is FastCDC (Fast Content-Defined Chunking)
41 f736d93a 2021-10-07 stsp * https://www.usenix.org/conference/atc16/technical-sessions/presentation/xia
44 d58ddaf3 2022-03-17 naddy static const uint32_t geartab[256] = {
45 69aa0e90 2021-03-10 stsp 0x67ed26b7, 0x32da500c, 0x53d0fee0, 0xce387dc7, 0xcd406d90, 0x2e83a4d4,
46 69aa0e90 2021-03-10 stsp 0x9fc9a38d, 0xb67259dc, 0xca6b1722, 0x6d2ea08c, 0x235cea2e, 0x3149bb5f,
47 69aa0e90 2021-03-10 stsp 0x1beda787, 0x2a6b77d5, 0x2f22d9ac, 0x91fc0544, 0xe413acfa, 0x5a30ff7a,
48 69aa0e90 2021-03-10 stsp 0xad6fdde0, 0x444fd0f5, 0x7ad87864, 0x58c5ff05, 0x8d2ec336, 0x2371f853,
49 69aa0e90 2021-03-10 stsp 0x550f8572, 0x6aa448dd, 0x7c9ddbcf, 0x95221e14, 0x2a82ec33, 0xcbec5a78,
50 69aa0e90 2021-03-10 stsp 0xc6795a0d, 0x243995b7, 0x1c909a2f, 0x4fded51c, 0x635d334b, 0x0e2b9999,
51 69aa0e90 2021-03-10 stsp 0x2702968d, 0x856de1d5, 0x3325d60e, 0xeb6a7502, 0xec2a9844, 0x0905835a,
52 69aa0e90 2021-03-10 stsp 0xa1820375, 0xa4be5cab, 0x96a6c058, 0x2c2ccd70, 0xba40fce3, 0xd794c46b,
53 69aa0e90 2021-03-10 stsp 0x8fbae83e, 0xc3aa7899, 0x3d3ff8ed, 0xa0d42b5b, 0x571c0c97, 0xd2811516,
54 69aa0e90 2021-03-10 stsp 0xf7e7b96c, 0x4fd2fcbd, 0xe2fdec94, 0x282cc436, 0x78e8e95c, 0x80a3b613,
55 69aa0e90 2021-03-10 stsp 0xcfbee20c, 0xd4a32d1c, 0x2a12ff13, 0x6af82936, 0xe5630258, 0x8efa6a98,
56 69aa0e90 2021-03-10 stsp 0x294fb2d1, 0xdeb57086, 0x5f0fddb3, 0xeceda7ce, 0x4c87305f, 0x3a6d3307,
57 69aa0e90 2021-03-10 stsp 0xe22d2942, 0x9d060217, 0x1e42ed02, 0xb6f63b52, 0x4367f39f, 0x055cf262,
58 69aa0e90 2021-03-10 stsp 0x03a461b2, 0x5ef9e382, 0x386bc03a, 0x2a1e79c7, 0xf1a0058b, 0xd4d2dea9,
59 69aa0e90 2021-03-10 stsp 0x56baf37d, 0x5daff6cc, 0xf03a951d, 0xaef7de45, 0xa8f4581e, 0x3960b555,
60 69aa0e90 2021-03-10 stsp 0xffbfff6d, 0xbe702a23, 0x8f5b6d6f, 0x061739fb, 0x98696f47, 0x3fd596d4,
61 69aa0e90 2021-03-10 stsp 0x151eac6b, 0xa9fcc4f5, 0x69181a12, 0x3ac5a107, 0xb5198fe7, 0x96bcb1da,
62 69aa0e90 2021-03-10 stsp 0x1b5ddf8e, 0xc757d650, 0x65865c3a, 0x8fc0a41a, 0x87435536, 0x99eda6f2,
63 69aa0e90 2021-03-10 stsp 0x41874794, 0x29cff4e8, 0xb70efd9a, 0x3103f6e7, 0x84d2453b, 0x15a450bd,
64 69aa0e90 2021-03-10 stsp 0x74f49af1, 0x60f664b1, 0xa1c86935, 0xfdafbce1, 0xe36353e3, 0x5d9ba739,
65 69aa0e90 2021-03-10 stsp 0xbc0559ba, 0x708b0054, 0xd41d808c, 0xb2f31723, 0x9027c41f, 0xf136d165,
66 69aa0e90 2021-03-10 stsp 0xb5374b12, 0x9420a6ac, 0x273958b6, 0xe6c2fad0, 0xebdc1f21, 0xfb33af8b,
67 69aa0e90 2021-03-10 stsp 0xc71c25cd, 0xe9a2d8e5, 0xbeb38a50, 0xbceb7cc2, 0x4e4e73f0, 0xcd6c251d,
68 69aa0e90 2021-03-10 stsp 0xde4c032c, 0x4b04ac30, 0x725b8b21, 0x4eb8c33b, 0x20d07b75, 0x0567aa63,
69 69aa0e90 2021-03-10 stsp 0xb56b2bb7, 0xc1f5fd3a, 0xcafd35ca, 0x470dd4da, 0xfe4f94cd, 0xfb8de424,
70 69aa0e90 2021-03-10 stsp 0xe8dbcf40, 0xfe50a37a, 0x62db5b5d, 0xf32f4ab6, 0x2c4a8a51, 0x18473dc0,
71 69aa0e90 2021-03-10 stsp 0xfe0cbb6e, 0xfe399efd, 0xdf34ecc9, 0x6ccd5055, 0x46097073, 0x139135c2,
72 69aa0e90 2021-03-10 stsp 0x721c76f6, 0x1c6a94b4, 0x6eee014d, 0x8a508e02, 0x3da538f5, 0x280d394f,
73 69aa0e90 2021-03-10 stsp 0x5248a0c4, 0x3ce94c6c, 0x9a71ad3a, 0x8493dd05, 0xe43f0ab6, 0x18e4ed42,
74 69aa0e90 2021-03-10 stsp 0x6c5c0e09, 0x42b06ec9, 0x8d330343, 0xa45b6f59, 0x2a573c0c, 0xd7fd3de6,
75 69aa0e90 2021-03-10 stsp 0xeedeab68, 0x5c84dafc, 0xbbd1b1a8, 0xa3ce1ad1, 0x85b70bed, 0xb6add07f,
76 69aa0e90 2021-03-10 stsp 0xa531309c, 0x8f8ab852, 0x564de332, 0xeac9ed0c, 0x73da402c, 0x3ec52761,
77 69aa0e90 2021-03-10 stsp 0x43af2f4d, 0xd6ff45c8, 0x4c367462, 0xd553bd6a, 0x44724855, 0x3b2aa728,
78 69aa0e90 2021-03-10 stsp 0x56e5eb65, 0xeaf16173, 0x33fa42ff, 0xd714bb5d, 0xfbd0a3b9, 0xaf517134,
79 69aa0e90 2021-03-10 stsp 0x9416c8cd, 0x534cf94f, 0x548947c2, 0x34193569, 0x32f4389a, 0xfe7028bc,
80 69aa0e90 2021-03-10 stsp 0xed73b1ed, 0x9db95770, 0x468e3922, 0x0440c3cd, 0x60059a62, 0x33504562,
81 69aa0e90 2021-03-10 stsp 0x2b229fbd, 0x5174dca5, 0xf7028752, 0xd63c6aa8, 0x31276f38, 0x0646721c,
82 69aa0e90 2021-03-10 stsp 0xb0191da8, 0xe00e6de0, 0x9eac1a6e, 0x9f7628a5, 0xed6c06ea, 0x0bb8af15,
83 69aa0e90 2021-03-10 stsp 0xf119fb12, 0x38693c1c, 0x732bc0fe, 0x84953275, 0xb82ec888, 0x33a4f1b3,
84 69aa0e90 2021-03-10 stsp 0x3099835e, 0x028a8782, 0x5fdd51d7, 0xc6c717b3, 0xb06caf71, 0x17c8c111,
85 69aa0e90 2021-03-10 stsp 0x61bad754, 0x9fd03061, 0xe09df1af, 0x3bc9eb73, 0x85878413, 0x9889aaf2,
86 69aa0e90 2021-03-10 stsp 0x3f5a9e46, 0x42c9f01f, 0x9984a4f4, 0xd5de43cc, 0xd294daed, 0xbecba2d2,
87 69aa0e90 2021-03-10 stsp 0xf1f6e72c, 0x5551128a, 0x83af87e2, 0x6f0342ba,
90 fcece718 2024-02-26 op static const struct got_error *addblk(struct got_delta_table *, FILE *,
91 fcece718 2024-02-26 op uint8_t *, off_t, off_t, off_t, uint32_t);
93 2b474c25 2022-02-11 stsp static uint32_t
94 d6a28ffe 2022-05-20 op hashblk(const unsigned char *p, off_t n, uint32_t seed)
96 d6a28ffe 2022-05-20 op return murmurhash2(p, n, seed);
99 f364801d 2021-03-10 stsp static const struct got_error *
100 fcece718 2024-02-26 op lookup(int *n, struct got_delta_table *dt, FILE *f, off_t file_offset0,
101 fcece718 2024-02-26 op off_t len, off_t offset, uint32_t h)
103 fcece718 2024-02-26 op struct got_delta_block *block;
104 69aa0e90 2021-03-10 stsp uint8_t buf[GOT_DELTIFY_MAXCHUNK];
105 0d15f6dc 2021-06-13 stsp uint8_t buf2[GOT_DELTIFY_MAXCHUNK];
106 69aa0e90 2021-03-10 stsp size_t r = 0;
109 fcece718 2024-02-26 op for (i = h % dt->size; dt->offs[i] != 0; i = (i + 1) % dt->size) {
110 fcece718 2024-02-26 op block = &dt->blocks[dt->offs[i] - 1];
111 fcece718 2024-02-26 op if (block->len != len || block->hash != h)
114 fcece718 2024-02-26 op if (r == 0) {
115 fcece718 2024-02-26 op if (fseeko(f, file_offset0 + offset, SEEK_SET) == -1)
116 69aa0e90 2021-03-10 stsp return got_error_from_errno("fseeko");
117 fcece718 2024-02-26 op r = fread(buf, 1, len, f);
118 fcece718 2024-02-26 op if (r != len) {
119 fcece718 2024-02-26 op if (!ferror(f))
120 fcece718 2024-02-26 op break; /* why? */
121 69aa0e90 2021-03-10 stsp return got_ferror(f, GOT_ERR_IO);
125 fcece718 2024-02-26 op if (fseeko(f, file_offset0 + block->offset, SEEK_SET) == -1)
126 fcece718 2024-02-26 op return got_error_from_errno("fseeko");
127 fcece718 2024-02-26 op if (fread(buf2, 1, len, f) != len)
128 fcece718 2024-02-26 op return got_ferror(f, GOT_ERR_IO);
129 fcece718 2024-02-26 op if (memcmp(buf, buf2, len) == 0)
137 fcece718 2024-02-26 op static const struct got_error *
138 fcece718 2024-02-26 op lookup_mem(int *n, struct got_delta_table *dt, uint8_t *basedata,
139 fcece718 2024-02-26 op off_t basefile_offset0, uint8_t *p, off_t len, uint32_t h)
141 fcece718 2024-02-26 op struct got_delta_block *block;
145 fcece718 2024-02-26 op for (i = h % dt->size; dt->offs[i] != 0; i = (i + 1) % dt->size) {
146 fcece718 2024-02-26 op block = &dt->blocks[dt->offs[i] - 1];
147 fcece718 2024-02-26 op if (len == block->len && h == block->hash) {
148 fcece718 2024-02-26 op d = basedata + basefile_offset0 + block->offset;
149 fcece718 2024-02-26 op if (memcmp(d, p, len) == 0)
158 64a8571e 2022-01-07 stsp static const struct got_error *
159 fcece718 2024-02-26 op resizeht(struct got_delta_table *dt, FILE *f, off_t offset0, uint8_t *data,
162 fcece718 2024-02-26 op const struct got_error *err;
163 fcece718 2024-02-26 op struct got_delta_block *b;
164 fcece718 2024-02-26 op size_t newsize, oldsize;
167 fcece718 2024-02-26 op if (dt->nblocks == dt->nalloc) {
168 fcece718 2024-02-26 op newsize = dt->nalloc + 256;
169 fcece718 2024-02-26 op b = reallocarray(dt->blocks, newsize, sizeof(*dt->blocks));
170 fcece718 2024-02-26 op if (b == NULL)
171 fcece718 2024-02-26 op return got_error_from_errno("reallocarray");
172 fcece718 2024-02-26 op dt->blocks = b;
173 fcece718 2024-02-26 op dt->nalloc = newsize;
176 fcece718 2024-02-26 op if (dt->blocks == NULL || dt->len * 100 / dt->size > 70) {
177 fcece718 2024-02-26 op oldsize = dt->size;
178 fcece718 2024-02-26 op dt->size *= 2;
179 fcece718 2024-02-26 op free(dt->offs);
180 fcece718 2024-02-26 op dt->offs = calloc(dt->size, sizeof(*dt->offs));
181 fcece718 2024-02-26 op if (dt->offs == NULL) {
182 fcece718 2024-02-26 op dt->size = oldsize;
183 fcece718 2024-02-26 op return got_error_from_errno("calloc");
186 fcece718 2024-02-26 op for (i = 0; i < dt->nblocks; ++i) {
187 fcece718 2024-02-26 op b = &dt->blocks[i];
189 fcece718 2024-02-26 op err = lookup(&n, dt, f, offset0, b->len,
190 fcece718 2024-02-26 op b->offset, b->hash);
192 fcece718 2024-02-26 op err = lookup_mem(&n, dt, data, offset0,
193 fcece718 2024-02-26 op data + b->offset, b->len, b->hash);
195 fcece718 2024-02-26 op free(dt->offs);
196 fcece718 2024-02-26 op dt->offs = NULL;
197 fcece718 2024-02-26 op dt->size = oldsize;
200 fcece718 2024-02-26 op assert(dt->offs[n] == 0);
201 fcece718 2024-02-26 op dt->offs[n] = i + 1;
208 69aa0e90 2021-03-10 stsp static const struct got_error *
209 fcece718 2024-02-26 op addblk(struct got_delta_table *dt, FILE *f, uint8_t *data, off_t file_offset0,
210 fcece718 2024-02-26 op off_t len, off_t offset, uint32_t h)
212 fcece718 2024-02-26 op const struct got_error *err;
213 fcece718 2024-02-26 op struct got_delta_block *block;
216 fcece718 2024-02-26 op if (len == 0)
219 fcece718 2024-02-26 op err = resizeht(dt, f, file_offset0, data, len);
224 fcece718 2024-02-26 op err = lookup(&i, dt, f, file_offset0, len, offset, h);
226 fcece718 2024-02-26 op err = lookup_mem(&i, dt, data, file_offset0, data + offset,
231 fcece718 2024-02-26 op if (dt->offs[i] != 0)
232 fcece718 2024-02-26 op return NULL; /* found */
234 fcece718 2024-02-26 op dt->offs[i] = dt->nblocks + 1;
235 fcece718 2024-02-26 op block = &dt->blocks[dt->nblocks];
236 fcece718 2024-02-26 op block->len = len;
237 fcece718 2024-02-26 op block->offset = offset;
238 fcece718 2024-02-26 op block->hash = h;
240 fcece718 2024-02-26 op dt->nblocks++;
246 fcece718 2024-02-26 op static const struct got_error *
247 69aa0e90 2021-03-10 stsp lookupblk(struct got_delta_block **block, struct got_delta_table *dt,
248 d6a28ffe 2022-05-20 op unsigned char *p, off_t len, uint32_t seed, FILE *basefile,
249 d6a28ffe 2022-05-20 op off_t basefile_offset0)
252 2b474c25 2022-02-11 stsp uint32_t h;
253 69aa0e90 2021-03-10 stsp uint8_t buf[GOT_DELTIFY_MAXCHUNK];
254 fcece718 2024-02-26 op struct got_delta_block *b;
257 69aa0e90 2021-03-10 stsp *block = NULL;
259 d6a28ffe 2022-05-20 op h = hashblk(p, len, seed);
261 fcece718 2024-02-26 op for (i = h % dt->size; dt->offs[i] != 0; i = (i + 1) % dt->size) {
262 fcece718 2024-02-26 op b = &dt->blocks[dt->offs[i] - 1];
263 fcece718 2024-02-26 op if (b->hash != h || b->len != len)
265 fcece718 2024-02-26 op if (fseeko(basefile, basefile_offset0 + b->offset,
266 740bba1c 2021-06-18 stsp SEEK_SET) == -1)
267 69aa0e90 2021-03-10 stsp return got_error_from_errno("fseeko");
268 69aa0e90 2021-03-10 stsp r = fread(buf, 1, len, basefile);
269 69aa0e90 2021-03-10 stsp if (r != len)
270 69aa0e90 2021-03-10 stsp return got_ferror(basefile, GOT_ERR_IO);
271 69aa0e90 2021-03-10 stsp if (memcmp(p, buf, len) == 0) {
276 f364801d 2021-03-10 stsp return NULL;
279 69aa0e90 2021-03-10 stsp static const struct got_error *
280 64a8571e 2022-01-07 stsp lookupblk_mem(struct got_delta_block **block, struct got_delta_table *dt,
281 d6a28ffe 2022-05-20 op unsigned char *p, off_t len, uint32_t seed, uint8_t *basedata,
282 d6a28ffe 2022-05-20 op off_t basefile_offset0)
284 fcece718 2024-02-26 op const struct got_error *err;
286 2b474c25 2022-02-11 stsp uint32_t h;
288 64a8571e 2022-01-07 stsp *block = NULL;
289 d6a28ffe 2022-05-20 op h = hashblk(p, len, seed);
290 fcece718 2024-02-26 op err = lookup_mem(&n, dt, basedata, basefile_offset0, p, len, h);
293 fcece718 2024-02-26 op if (dt->offs[n] != 0)
294 fcece718 2024-02-26 op *block = &dt->blocks[dt->offs[n] - 1];
295 64a8571e 2022-01-07 stsp return NULL;
298 64a8571e 2022-01-07 stsp static const struct got_error *
299 69aa0e90 2021-03-10 stsp nextblk(uint8_t *buf, off_t *blocklen, FILE *f)
301 f364801d 2021-03-10 stsp uint32_t gh;
302 69aa0e90 2021-03-10 stsp const unsigned char *p;
304 69aa0e90 2021-03-10 stsp off_t pos = ftello(f);
306 69aa0e90 2021-03-10 stsp *blocklen = 0;
308 69aa0e90 2021-03-10 stsp r = fread(buf, 1, GOT_DELTIFY_MAXCHUNK, f);
309 69aa0e90 2021-03-10 stsp if (r == 0 && ferror(f))
310 69aa0e90 2021-03-10 stsp return got_ferror(f, GOT_ERR_IO);
311 69aa0e90 2021-03-10 stsp if (r < GOT_DELTIFY_MINCHUNK)
312 69aa0e90 2021-03-10 stsp return NULL; /* no more delta-worthy blocks left */
314 69aa0e90 2021-03-10 stsp /* Got a deltifiable block. Find the split-point where it ends. */
315 69aa0e90 2021-03-10 stsp p = buf + GOT_DELTIFY_MINCHUNK;
317 69aa0e90 2021-03-10 stsp while (p != buf + r) {
318 f364801d 2021-03-10 stsp gh = (gh << 1) + geartab[*p++];
319 69aa0e90 2021-03-10 stsp if ((gh & GOT_DELTIFY_SPLITMASK) == 0)
323 69aa0e90 2021-03-10 stsp *blocklen = (p - buf);
324 69aa0e90 2021-03-10 stsp if (fseeko(f, pos + *blocklen, SEEK_SET) == -1)
325 69aa0e90 2021-03-10 stsp return got_error_from_errno("fseeko");
327 69aa0e90 2021-03-10 stsp return NULL;
330 64a8571e 2022-01-07 stsp static const struct got_error *
331 64a8571e 2022-01-07 stsp nextblk_mem(off_t *blocklen, uint8_t *data, off_t fileoffset, off_t filesize)
333 64a8571e 2022-01-07 stsp uint32_t gh;
334 64a8571e 2022-01-07 stsp const unsigned char *p;
336 64a8571e 2022-01-07 stsp *blocklen = 0;
338 64a8571e 2022-01-07 stsp if (fileoffset >= filesize ||
339 64a8571e 2022-01-07 stsp filesize - fileoffset < GOT_DELTIFY_MINCHUNK)
340 64a8571e 2022-01-07 stsp return NULL; /* no more delta-worthy blocks left */
342 64a8571e 2022-01-07 stsp /* Got a deltifiable block. Find the split-point where it ends. */
343 64a8571e 2022-01-07 stsp p = data + fileoffset + GOT_DELTIFY_MINCHUNK;
345 64a8571e 2022-01-07 stsp while (p != data + MIN(fileoffset + GOT_DELTIFY_MAXCHUNK, filesize)) {
346 64a8571e 2022-01-07 stsp gh = (gh << 1) + geartab[*p++];
347 64a8571e 2022-01-07 stsp if ((gh & GOT_DELTIFY_SPLITMASK) == 0)
351 64a8571e 2022-01-07 stsp *blocklen = (p - (data + fileoffset));
352 64a8571e 2022-01-07 stsp return NULL;
355 f364801d 2021-03-10 stsp const struct got_error *
356 69aa0e90 2021-03-10 stsp got_deltify_init(struct got_delta_table **dt, FILE *f, off_t fileoffset,
357 d6a28ffe 2022-05-20 op off_t filesize, uint32_t seed)
359 69aa0e90 2021-03-10 stsp const struct got_error *err = NULL;
360 2b474c25 2022-02-11 stsp uint32_t h;
361 740bba1c 2021-06-18 stsp const off_t offset0 = fileoffset;
363 69aa0e90 2021-03-10 stsp *dt = calloc(1, sizeof(**dt));
364 69aa0e90 2021-03-10 stsp if (*dt == NULL)
365 f364801d 2021-03-10 stsp return got_error_from_errno("calloc");
367 69aa0e90 2021-03-10 stsp (*dt)->nblocks = 0;
368 69aa0e90 2021-03-10 stsp (*dt)->nalloc = 128;
369 69aa0e90 2021-03-10 stsp (*dt)->blocks = calloc((*dt)->nalloc, sizeof(struct got_delta_block));
370 69aa0e90 2021-03-10 stsp if ((*dt)->blocks == NULL) {
371 69aa0e90 2021-03-10 stsp err = got_error_from_errno("calloc");
375 fcece718 2024-02-26 op (*dt)->size = 128;
376 fcece718 2024-02-26 op (*dt)->offs = calloc((*dt)->size, sizeof(*(*dt)->offs));
377 fcece718 2024-02-26 op if ((*dt)->offs == NULL) {
378 fcece718 2024-02-26 op err = got_error_from_errno("calloc");
382 69aa0e90 2021-03-10 stsp if (fseeko(f, fileoffset, SEEK_SET) == -1)
383 69aa0e90 2021-03-10 stsp return got_error_from_errno("fseeko");
385 69aa0e90 2021-03-10 stsp while (fileoffset < filesize) {
386 69aa0e90 2021-03-10 stsp uint8_t buf[GOT_DELTIFY_MAXCHUNK];
387 69aa0e90 2021-03-10 stsp off_t blocklen;
388 69aa0e90 2021-03-10 stsp err = nextblk(buf, &blocklen, f);
391 69aa0e90 2021-03-10 stsp if (blocklen == 0)
393 d6a28ffe 2022-05-20 op h = hashblk(buf, blocklen, seed);
394 fcece718 2024-02-26 op err = addblk(*dt, f, NULL, offset0, blocklen,
395 740bba1c 2021-06-18 stsp fileoffset - offset0, h);
398 69aa0e90 2021-03-10 stsp fileoffset += blocklen;
399 68bdcdc2 2021-06-11 stsp if (fseeko(f, fileoffset, SEEK_SET) == -1)
400 68bdcdc2 2021-06-11 stsp return got_error_from_errno("fseeko");
404 64a8571e 2022-01-07 stsp free((*dt)->blocks);
406 64a8571e 2022-01-07 stsp *dt = NULL;
409 64a8571e 2022-01-07 stsp return err;
412 64a8571e 2022-01-07 stsp const struct got_error *
413 64a8571e 2022-01-07 stsp got_deltify_init_mem(struct got_delta_table **dt, uint8_t *data,
414 d6a28ffe 2022-05-20 op off_t fileoffset, off_t filesize, uint32_t seed)
416 64a8571e 2022-01-07 stsp const struct got_error *err = NULL;
417 f6027426 2022-02-12 naddy uint32_t h;
418 64a8571e 2022-01-07 stsp const off_t offset0 = fileoffset;
420 64a8571e 2022-01-07 stsp *dt = calloc(1, sizeof(**dt));
421 64a8571e 2022-01-07 stsp if (*dt == NULL)
422 64a8571e 2022-01-07 stsp return got_error_from_errno("calloc");
424 64a8571e 2022-01-07 stsp (*dt)->nblocks = 0;
425 64a8571e 2022-01-07 stsp (*dt)->nalloc = 128;
426 64a8571e 2022-01-07 stsp (*dt)->blocks = calloc((*dt)->nalloc, sizeof(struct got_delta_block));
427 64a8571e 2022-01-07 stsp if ((*dt)->blocks == NULL) {
428 fcece718 2024-02-26 op err = got_error_from_errno("calloc");
432 fcece718 2024-02-26 op (*dt)->size = 128;
433 fcece718 2024-02-26 op (*dt)->offs = calloc((*dt)->size, sizeof(*(*dt)->offs));
434 fcece718 2024-02-26 op if ((*dt)->offs == NULL) {
435 64a8571e 2022-01-07 stsp err = got_error_from_errno("calloc");
439 64a8571e 2022-01-07 stsp while (fileoffset < filesize) {
440 64a8571e 2022-01-07 stsp off_t blocklen;
441 64a8571e 2022-01-07 stsp err = nextblk_mem(&blocklen, data, fileoffset, filesize);
444 64a8571e 2022-01-07 stsp if (blocklen == 0)
446 d6a28ffe 2022-05-20 op h = hashblk(data + fileoffset, blocklen, seed);
447 fcece718 2024-02-26 op err = addblk(*dt, NULL, data, offset0, blocklen,
448 64a8571e 2022-01-07 stsp fileoffset - offset0, h);
451 64a8571e 2022-01-07 stsp fileoffset += blocklen;
455 69aa0e90 2021-03-10 stsp free((*dt)->blocks);
457 69aa0e90 2021-03-10 stsp *dt = NULL;
460 69aa0e90 2021-03-10 stsp return err;
464 69aa0e90 2021-03-10 stsp got_deltify_free(struct got_delta_table *dt)
466 dbbf4a5f 2021-05-20 stsp if (dt == NULL)
468 69aa0e90 2021-03-10 stsp free(dt->blocks);
469 fcece718 2024-02-26 op free(dt->offs);
473 f364801d 2021-03-10 stsp static const struct got_error *
474 dd29967c 2021-08-22 stsp emitdelta(struct got_delta_instruction **deltas, size_t *nalloc, int *ndeltas,
475 dd29967c 2021-08-22 stsp const size_t alloc_chunk_size, int copy, off_t offset, off_t len)
477 69aa0e90 2021-03-10 stsp struct got_delta_instruction *d, *p;
479 dd29967c 2021-08-22 stsp if (*nalloc < *ndeltas + alloc_chunk_size) {
480 dd29967c 2021-08-22 stsp p = reallocarray(*deltas, *nalloc + alloc_chunk_size,
481 dd29967c 2021-08-22 stsp sizeof(struct got_delta_instruction));
482 dd29967c 2021-08-22 stsp if (p == NULL)
483 2d467c6d 2021-10-13 stsp return got_error_from_errno("reallocarray");
484 dd29967c 2021-08-22 stsp *deltas = p;
485 dd29967c 2021-08-22 stsp *nalloc += alloc_chunk_size;
487 69aa0e90 2021-03-10 stsp *ndeltas += 1;
488 69aa0e90 2021-03-10 stsp d = &(*deltas)[*ndeltas - 1];
489 69aa0e90 2021-03-10 stsp d->copy = copy;
490 69aa0e90 2021-03-10 stsp d->offset = offset;
491 56e7a15f 2021-03-10 stsp d->len = len;
492 f364801d 2021-03-10 stsp return NULL;
495 69aa0e90 2021-03-10 stsp static const struct got_error *
496 740bba1c 2021-06-18 stsp stretchblk(FILE *basefile, off_t base_offset0, struct got_delta_block *block,
497 740bba1c 2021-06-18 stsp FILE *f, off_t filesize, off_t *blocklen)
499 69aa0e90 2021-03-10 stsp uint8_t basebuf[GOT_DELTIFY_MAXCHUNK], buf[GOT_DELTIFY_MAXCHUNK];
500 69aa0e90 2021-03-10 stsp size_t base_r, r, i;
501 69aa0e90 2021-03-10 stsp int buf_equal = 1;
503 5de743f8 2021-08-29 stsp if (fseeko(basefile, base_offset0 + block->offset + *blocklen,
504 5de743f8 2021-08-29 stsp SEEK_SET) == -1)
505 69aa0e90 2021-03-10 stsp return got_error_from_errno("fseeko");
507 69aa0e90 2021-03-10 stsp while (buf_equal && *blocklen < (1 << 24) - 1) {
508 69aa0e90 2021-03-10 stsp base_r = fread(basebuf, 1, sizeof(basebuf), basefile);
509 69aa0e90 2021-03-10 stsp if (base_r == 0) {
510 69aa0e90 2021-03-10 stsp if (ferror(basefile))
511 69aa0e90 2021-03-10 stsp return got_ferror(basefile, GOT_ERR_IO);
514 69aa0e90 2021-03-10 stsp r = fread(buf, 1, sizeof(buf), f);
515 69aa0e90 2021-03-10 stsp if (r == 0) {
516 69aa0e90 2021-03-10 stsp if (ferror(f))
517 69aa0e90 2021-03-10 stsp return got_ferror(f, GOT_ERR_IO);
520 69aa0e90 2021-03-10 stsp for (i = 0; i < MIN(base_r, r); i++) {
521 69aa0e90 2021-03-10 stsp if (buf[i] != basebuf[i]) {
522 69aa0e90 2021-03-10 stsp buf_equal = 0;
525 69aa0e90 2021-03-10 stsp (*blocklen)++;
529 64a8571e 2022-01-07 stsp return NULL;
532 64a8571e 2022-01-07 stsp static const struct got_error *
533 64a8571e 2022-01-07 stsp stretchblk_file_mem(uint8_t *basedata, off_t base_offset0, off_t basefile_size,
534 64a8571e 2022-01-07 stsp struct got_delta_block *block, FILE *f, off_t filesize, off_t *blocklen)
536 64a8571e 2022-01-07 stsp uint8_t buf[GOT_DELTIFY_MAXCHUNK];
537 64a8571e 2022-01-07 stsp size_t r, i;
538 64a8571e 2022-01-07 stsp int buf_equal = 1;
539 64a8571e 2022-01-07 stsp off_t base_offset = base_offset0 + block->offset + *blocklen;
541 64a8571e 2022-01-07 stsp if (base_offset > basefile_size) {
542 64a8571e 2022-01-07 stsp return got_error_fmt(GOT_ERR_RANGE,
543 04aed155 2022-07-24 naddy "read beyond the size of delta base at offset %lld",
544 04aed155 2022-07-24 naddy (long long)base_offset);
547 64a8571e 2022-01-07 stsp while (buf_equal && *blocklen < (1 << 24) - 1) {
548 64a8571e 2022-01-07 stsp if (base_offset + *blocklen >= basefile_size)
550 64a8571e 2022-01-07 stsp r = fread(buf, 1, sizeof(buf), f);
551 64a8571e 2022-01-07 stsp if (r == 0) {
552 64a8571e 2022-01-07 stsp if (ferror(f))
553 64a8571e 2022-01-07 stsp return got_ferror(f, GOT_ERR_IO);
556 64a8571e 2022-01-07 stsp for (i = 0; i < MIN(basefile_size - base_offset, r); i++) {
557 64a8571e 2022-01-07 stsp if (buf[i] != *(basedata + base_offset + i)) {
558 64a8571e 2022-01-07 stsp buf_equal = 0;
561 64a8571e 2022-01-07 stsp (*blocklen)++;
565 64a8571e 2022-01-07 stsp return NULL;
568 64a8571e 2022-01-07 stsp static const struct got_error *
569 64a8571e 2022-01-07 stsp stretchblk_mem_file(FILE *basefile, off_t base_offset0,
570 64a8571e 2022-01-07 stsp struct got_delta_block *block, uint8_t *data, off_t fileoffset,
571 64a8571e 2022-01-07 stsp off_t filesize, off_t *blocklen)
573 64a8571e 2022-01-07 stsp uint8_t basebuf[GOT_DELTIFY_MAXCHUNK];
574 64a8571e 2022-01-07 stsp size_t base_r, i;
575 64a8571e 2022-01-07 stsp int buf_equal = 1;
577 64a8571e 2022-01-07 stsp if (fileoffset > filesize) {
578 64a8571e 2022-01-07 stsp return got_error_fmt(GOT_ERR_RANGE,
579 04aed155 2022-07-24 naddy "read beyond the size of deltify file at offset %lld",
580 04aed155 2022-07-24 naddy (long long)fileoffset);
583 64a8571e 2022-01-07 stsp if (fseeko(basefile, base_offset0 + block->offset + *blocklen,
584 64a8571e 2022-01-07 stsp SEEK_SET) == -1)
585 64a8571e 2022-01-07 stsp return got_error_from_errno("fseeko");
587 64a8571e 2022-01-07 stsp while (buf_equal && *blocklen < (1 << 24) - 1) {
588 64a8571e 2022-01-07 stsp if (fileoffset + *blocklen >= filesize)
590 64a8571e 2022-01-07 stsp base_r = fread(basebuf, 1, sizeof(basebuf), basefile);
591 64a8571e 2022-01-07 stsp if (base_r == 0) {
592 64a8571e 2022-01-07 stsp if (ferror(basefile))
593 64a8571e 2022-01-07 stsp return got_ferror(basefile, GOT_ERR_IO);
596 64a8571e 2022-01-07 stsp for (i = 0; i < MIN(base_r, filesize - fileoffset); i++) {
597 64a8571e 2022-01-07 stsp if (*(data + fileoffset + i) != basebuf[i]) {
598 64a8571e 2022-01-07 stsp buf_equal = 0;
601 64a8571e 2022-01-07 stsp (*blocklen)++;
605 64a8571e 2022-01-07 stsp return NULL;
608 64a8571e 2022-01-07 stsp static const struct got_error *
609 64a8571e 2022-01-07 stsp stretchblk_mem_mem(uint8_t *basedata, off_t base_offset0, off_t basefile_size,
610 64a8571e 2022-01-07 stsp struct got_delta_block *block, uint8_t *data, off_t fileoffset,
611 64a8571e 2022-01-07 stsp off_t filesize, off_t *blocklen)
613 64a8571e 2022-01-07 stsp off_t i, maxlen;
614 64a8571e 2022-01-07 stsp off_t base_offset = base_offset0 + block->offset + *blocklen;
615 64a8571e 2022-01-07 stsp uint8_t *p, *q;
617 64a8571e 2022-01-07 stsp if (base_offset > basefile_size) {
618 64a8571e 2022-01-07 stsp return got_error_fmt(GOT_ERR_RANGE,
619 04aed155 2022-07-24 naddy "read beyond the size of delta base at offset %lld",
620 04aed155 2022-07-24 naddy (long long)base_offset);
623 64a8571e 2022-01-07 stsp if (fileoffset > filesize) {
624 64a8571e 2022-01-07 stsp return got_error_fmt(GOT_ERR_RANGE,
625 04aed155 2022-07-24 naddy "read beyond the size of deltify file at offset %lld",
626 04aed155 2022-07-24 naddy (long long)fileoffset);
629 64a8571e 2022-01-07 stsp p = data + fileoffset;
630 64a8571e 2022-01-07 stsp q = basedata + base_offset;
631 64a8571e 2022-01-07 stsp maxlen = MIN(basefile_size - base_offset, filesize - fileoffset);
632 64a8571e 2022-01-07 stsp for (i = 0; i < maxlen && *blocklen < (1 << 24) - 1; i++) {
633 64a8571e 2022-01-07 stsp if (p[i] != q[i])
635 64a8571e 2022-01-07 stsp (*blocklen)++;
638 69aa0e90 2021-03-10 stsp return NULL;
641 69aa0e90 2021-03-10 stsp const struct got_error *
642 69aa0e90 2021-03-10 stsp got_deltify(struct got_delta_instruction **deltas, int *ndeltas,
643 d6a28ffe 2022-05-20 op FILE *f, off_t fileoffset, off_t filesize, uint32_t seed,
644 69aa0e90 2021-03-10 stsp struct got_delta_table *dt, FILE *basefile,
645 f34b169e 2021-06-18 stsp off_t basefile_offset0, off_t basefile_size)
647 69aa0e90 2021-03-10 stsp const struct got_error *err = NULL;
648 69aa0e90 2021-03-10 stsp const off_t offset0 = fileoffset;
649 dd29967c 2021-08-22 stsp size_t nalloc = 0;
650 dd29967c 2021-08-22 stsp const size_t alloc_chunk_size = 64;
652 69aa0e90 2021-03-10 stsp *deltas = NULL;
653 69aa0e90 2021-03-10 stsp *ndeltas = 0;
656 69aa0e90 2021-03-10 stsp * offset0 indicates where data to be deltified begins.
657 69aa0e90 2021-03-10 stsp * For example, we want to avoid deltifying a Git object header at
658 69aa0e90 2021-03-10 stsp * the beginning of the file.
660 69aa0e90 2021-03-10 stsp if (fseeko(f, offset0, SEEK_SET) == -1)
661 69aa0e90 2021-03-10 stsp return got_error_from_errno("fseeko");
663 dd29967c 2021-08-22 stsp *deltas = reallocarray(NULL, alloc_chunk_size,
664 dd29967c 2021-08-22 stsp sizeof(struct got_delta_instruction));
665 dd29967c 2021-08-22 stsp if (*deltas == NULL)
666 dd29967c 2021-08-22 stsp return got_error_from_errno("reallocarray");
667 dd29967c 2021-08-22 stsp nalloc = alloc_chunk_size;
669 69aa0e90 2021-03-10 stsp while (fileoffset < filesize) {
670 69aa0e90 2021-03-10 stsp uint8_t buf[GOT_DELTIFY_MAXCHUNK];
671 69aa0e90 2021-03-10 stsp off_t blocklen;
672 69aa0e90 2021-03-10 stsp struct got_delta_block *block;
673 69aa0e90 2021-03-10 stsp err = nextblk(buf, &blocklen, f);
676 9a8dc2b3 2021-06-18 stsp if (blocklen == 0) {
677 9a8dc2b3 2021-06-18 stsp /* Source remainder from the file itself. */
678 9a8dc2b3 2021-06-18 stsp if (fileoffset < filesize) {
679 dd29967c 2021-08-22 stsp err = emitdelta(deltas, &nalloc, ndeltas,
680 dd29967c 2021-08-22 stsp alloc_chunk_size, 0, fileoffset - offset0,
681 9a8dc2b3 2021-06-18 stsp filesize - fileoffset);
685 d6a28ffe 2022-05-20 op err = lookupblk(&block, dt, buf, blocklen, seed, basefile,
686 740bba1c 2021-06-18 stsp basefile_offset0);
689 69aa0e90 2021-03-10 stsp if (block != NULL) {
691 69aa0e90 2021-03-10 stsp * We have found a matching block in the delta base.
692 69aa0e90 2021-03-10 stsp * Attempt to stretch the block as far as possible and
693 69aa0e90 2021-03-10 stsp * generate a copy instruction.
695 740bba1c 2021-06-18 stsp err = stretchblk(basefile, basefile_offset0, block,
696 740bba1c 2021-06-18 stsp f, filesize, &blocklen);
699 dd29967c 2021-08-22 stsp err = emitdelta(deltas, &nalloc, ndeltas,
700 dd29967c 2021-08-22 stsp alloc_chunk_size, 1, block->offset, blocklen);
705 69aa0e90 2021-03-10 stsp * No match.
706 69aa0e90 2021-03-10 stsp * This block needs to be sourced from the file itself.
708 dd29967c 2021-08-22 stsp err = emitdelta(deltas, &nalloc, ndeltas,
709 dd29967c 2021-08-22 stsp alloc_chunk_size, 0, fileoffset - offset0, blocklen);
713 69aa0e90 2021-03-10 stsp fileoffset += blocklen;
714 0af64e86 2021-08-22 stsp if (fseeko(f, fileoffset, SEEK_SET) == -1) {
715 0af64e86 2021-08-22 stsp err = got_error_from_errno("fseeko");
721 69aa0e90 2021-03-10 stsp free(*deltas);
722 69aa0e90 2021-03-10 stsp *deltas = NULL;
723 69aa0e90 2021-03-10 stsp *ndeltas = 0;
725 69aa0e90 2021-03-10 stsp return err;
728 64a8571e 2022-01-07 stsp const struct got_error *
729 64a8571e 2022-01-07 stsp got_deltify_file_mem(struct got_delta_instruction **deltas, int *ndeltas,
730 d6a28ffe 2022-05-20 op FILE *f, off_t fileoffset, off_t filesize, uint32_t seed,
731 64a8571e 2022-01-07 stsp struct got_delta_table *dt, uint8_t *basedata,
732 64a8571e 2022-01-07 stsp off_t basefile_offset0, off_t basefile_size)
734 64a8571e 2022-01-07 stsp const struct got_error *err = NULL;
735 64a8571e 2022-01-07 stsp const off_t offset0 = fileoffset;
736 64a8571e 2022-01-07 stsp size_t nalloc = 0;
737 64a8571e 2022-01-07 stsp const size_t alloc_chunk_size = 64;
739 64a8571e 2022-01-07 stsp *deltas = NULL;
740 64a8571e 2022-01-07 stsp *ndeltas = 0;
743 64a8571e 2022-01-07 stsp * offset0 indicates where data to be deltified begins.
744 64a8571e 2022-01-07 stsp * For example, we want to avoid deltifying a Git object header at
745 64a8571e 2022-01-07 stsp * the beginning of the file.
747 64a8571e 2022-01-07 stsp if (fseeko(f, offset0, SEEK_SET) == -1)
748 64a8571e 2022-01-07 stsp return got_error_from_errno("fseeko");
750 64a8571e 2022-01-07 stsp *deltas = reallocarray(NULL, alloc_chunk_size,
751 64a8571e 2022-01-07 stsp sizeof(struct got_delta_instruction));
752 64a8571e 2022-01-07 stsp if (*deltas == NULL)
753 64a8571e 2022-01-07 stsp return got_error_from_errno("reallocarray");
754 64a8571e 2022-01-07 stsp nalloc = alloc_chunk_size;
756 64a8571e 2022-01-07 stsp while (fileoffset < filesize) {
757 64a8571e 2022-01-07 stsp uint8_t buf[GOT_DELTIFY_MAXCHUNK];
758 64a8571e 2022-01-07 stsp off_t blocklen;
759 64a8571e 2022-01-07 stsp struct got_delta_block *block;
760 64a8571e 2022-01-07 stsp err = nextblk(buf, &blocklen, f);
763 64a8571e 2022-01-07 stsp if (blocklen == 0) {
764 64a8571e 2022-01-07 stsp /* Source remainder from the file itself. */
765 64a8571e 2022-01-07 stsp if (fileoffset < filesize) {
766 64a8571e 2022-01-07 stsp err = emitdelta(deltas, &nalloc, ndeltas,
767 64a8571e 2022-01-07 stsp alloc_chunk_size, 0, fileoffset - offset0,
768 64a8571e 2022-01-07 stsp filesize - fileoffset);
772 d6a28ffe 2022-05-20 op err = lookupblk_mem(&block, dt, buf, blocklen, seed, basedata,
773 64a8571e 2022-01-07 stsp basefile_offset0);
776 64a8571e 2022-01-07 stsp if (block != NULL) {
778 64a8571e 2022-01-07 stsp * We have found a matching block in the delta base.
779 64a8571e 2022-01-07 stsp * Attempt to stretch the block as far as possible and
780 64a8571e 2022-01-07 stsp * generate a copy instruction.
782 64a8571e 2022-01-07 stsp err = stretchblk_file_mem(basedata, basefile_offset0,
783 64a8571e 2022-01-07 stsp basefile_size, block, f, filesize, &blocklen);
786 64a8571e 2022-01-07 stsp err = emitdelta(deltas, &nalloc, ndeltas,
787 64a8571e 2022-01-07 stsp alloc_chunk_size, 1, block->offset, blocklen);
792 64a8571e 2022-01-07 stsp * No match.
793 64a8571e 2022-01-07 stsp * This block needs to be sourced from the file itself.
795 64a8571e 2022-01-07 stsp err = emitdelta(deltas, &nalloc, ndeltas,
796 64a8571e 2022-01-07 stsp alloc_chunk_size, 0, fileoffset - offset0, blocklen);
800 64a8571e 2022-01-07 stsp fileoffset += blocklen;
801 64a8571e 2022-01-07 stsp if (fseeko(f, fileoffset, SEEK_SET) == -1) {
802 64a8571e 2022-01-07 stsp err = got_error_from_errno("fseeko");
808 64a8571e 2022-01-07 stsp free(*deltas);
809 64a8571e 2022-01-07 stsp *deltas = NULL;
810 64a8571e 2022-01-07 stsp *ndeltas = 0;
812 64a8571e 2022-01-07 stsp return err;
815 64a8571e 2022-01-07 stsp const struct got_error *
816 64a8571e 2022-01-07 stsp got_deltify_mem_file(struct got_delta_instruction **deltas, int *ndeltas,
817 d6a28ffe 2022-05-20 op uint8_t *data, off_t fileoffset, off_t filesize, uint32_t seed,
818 64a8571e 2022-01-07 stsp struct got_delta_table *dt, FILE *basefile,
819 64a8571e 2022-01-07 stsp off_t basefile_offset0, off_t basefile_size)
821 64a8571e 2022-01-07 stsp const struct got_error *err = NULL;
822 64a8571e 2022-01-07 stsp const off_t offset0 = fileoffset;
823 64a8571e 2022-01-07 stsp size_t nalloc = 0;
824 64a8571e 2022-01-07 stsp const size_t alloc_chunk_size = 64;
826 64a8571e 2022-01-07 stsp *deltas = NULL;
827 64a8571e 2022-01-07 stsp *ndeltas = 0;
829 64a8571e 2022-01-07 stsp *deltas = reallocarray(NULL, alloc_chunk_size,
830 64a8571e 2022-01-07 stsp sizeof(struct got_delta_instruction));
831 64a8571e 2022-01-07 stsp if (*deltas == NULL)
832 64a8571e 2022-01-07 stsp return got_error_from_errno("reallocarray");
833 64a8571e 2022-01-07 stsp nalloc = alloc_chunk_size;
835 64a8571e 2022-01-07 stsp while (fileoffset < filesize) {
836 64a8571e 2022-01-07 stsp off_t blocklen;
837 64a8571e 2022-01-07 stsp struct got_delta_block *block;
838 64a8571e 2022-01-07 stsp err = nextblk_mem(&blocklen, data, fileoffset, filesize);
841 64a8571e 2022-01-07 stsp if (blocklen == 0) {
842 64a8571e 2022-01-07 stsp /* Source remainder from the file itself. */
843 64a8571e 2022-01-07 stsp if (fileoffset < filesize) {
844 64a8571e 2022-01-07 stsp err = emitdelta(deltas, &nalloc, ndeltas,
845 64a8571e 2022-01-07 stsp alloc_chunk_size, 0, fileoffset - offset0,
846 64a8571e 2022-01-07 stsp filesize - fileoffset);
850 d6a28ffe 2022-05-20 op err = lookupblk(&block, dt, data + fileoffset, blocklen, seed,
851 64a8571e 2022-01-07 stsp basefile, basefile_offset0);
854 64a8571e 2022-01-07 stsp if (block != NULL) {
856 64a8571e 2022-01-07 stsp * We have found a matching block in the delta base.
857 64a8571e 2022-01-07 stsp * Attempt to stretch the block as far as possible and
858 64a8571e 2022-01-07 stsp * generate a copy instruction.
860 64a8571e 2022-01-07 stsp err = stretchblk_mem_file(basefile, basefile_offset0,
861 64a8571e 2022-01-07 stsp block, data, fileoffset + blocklen, filesize,
862 64a8571e 2022-01-07 stsp &blocklen);
865 64a8571e 2022-01-07 stsp err = emitdelta(deltas, &nalloc, ndeltas,
866 64a8571e 2022-01-07 stsp alloc_chunk_size, 1, block->offset, blocklen);
871 64a8571e 2022-01-07 stsp * No match.
872 64a8571e 2022-01-07 stsp * This block needs to be sourced from the file itself.
874 64a8571e 2022-01-07 stsp err = emitdelta(deltas, &nalloc, ndeltas,
875 64a8571e 2022-01-07 stsp alloc_chunk_size, 0, fileoffset - offset0, blocklen);
879 64a8571e 2022-01-07 stsp fileoffset += blocklen;
883 64a8571e 2022-01-07 stsp free(*deltas);
884 64a8571e 2022-01-07 stsp *deltas = NULL;
885 64a8571e 2022-01-07 stsp *ndeltas = 0;
887 64a8571e 2022-01-07 stsp return err;
890 64a8571e 2022-01-07 stsp const struct got_error *
891 64a8571e 2022-01-07 stsp got_deltify_mem_mem(struct got_delta_instruction **deltas, int *ndeltas,
892 d6a28ffe 2022-05-20 op uint8_t *data, off_t fileoffset, off_t filesize, uint32_t seed,
893 64a8571e 2022-01-07 stsp struct got_delta_table *dt, uint8_t *basedata,
894 64a8571e 2022-01-07 stsp off_t basefile_offset0, off_t basefile_size)
896 64a8571e 2022-01-07 stsp const struct got_error *err = NULL;
897 64a8571e 2022-01-07 stsp const off_t offset0 = fileoffset;
898 64a8571e 2022-01-07 stsp size_t nalloc = 0;
899 64a8571e 2022-01-07 stsp const size_t alloc_chunk_size = 64;
901 64a8571e 2022-01-07 stsp *deltas = NULL;
902 64a8571e 2022-01-07 stsp *ndeltas = 0;
904 64a8571e 2022-01-07 stsp *deltas = reallocarray(NULL, alloc_chunk_size,
905 64a8571e 2022-01-07 stsp sizeof(struct got_delta_instruction));
906 64a8571e 2022-01-07 stsp if (*deltas == NULL)
907 64a8571e 2022-01-07 stsp return got_error_from_errno("reallocarray");
908 64a8571e 2022-01-07 stsp nalloc = alloc_chunk_size;
910 64a8571e 2022-01-07 stsp while (fileoffset < filesize) {
911 64a8571e 2022-01-07 stsp off_t blocklen;
912 64a8571e 2022-01-07 stsp struct got_delta_block *block;
913 64a8571e 2022-01-07 stsp err = nextblk_mem(&blocklen, data, fileoffset, filesize);
916 64a8571e 2022-01-07 stsp if (blocklen == 0) {
917 64a8571e 2022-01-07 stsp /* Source remainder from the file itself. */
918 64a8571e 2022-01-07 stsp if (fileoffset < filesize) {
919 64a8571e 2022-01-07 stsp err = emitdelta(deltas, &nalloc, ndeltas,
920 64a8571e 2022-01-07 stsp alloc_chunk_size, 0, fileoffset - offset0,
921 64a8571e 2022-01-07 stsp filesize - fileoffset);
925 64a8571e 2022-01-07 stsp err = lookupblk_mem(&block, dt, data + fileoffset, blocklen,
926 d6a28ffe 2022-05-20 op seed, basedata, basefile_offset0);
929 64a8571e 2022-01-07 stsp if (block != NULL) {
931 64a8571e 2022-01-07 stsp * We have found a matching block in the delta base.
932 64a8571e 2022-01-07 stsp * Attempt to stretch the block as far as possible and
933 64a8571e 2022-01-07 stsp * generate a copy instruction.
935 64a8571e 2022-01-07 stsp err = stretchblk_mem_mem(basedata, basefile_offset0,
936 64a8571e 2022-01-07 stsp basefile_size, block, data, fileoffset + blocklen,
937 64a8571e 2022-01-07 stsp filesize, &blocklen);
940 64a8571e 2022-01-07 stsp err = emitdelta(deltas, &nalloc, ndeltas,
941 64a8571e 2022-01-07 stsp alloc_chunk_size, 1, block->offset, blocklen);
946 64a8571e 2022-01-07 stsp * No match.
947 64a8571e 2022-01-07 stsp * This block needs to be sourced from the file itself.
949 64a8571e 2022-01-07 stsp err = emitdelta(deltas, &nalloc, ndeltas,
950 64a8571e 2022-01-07 stsp alloc_chunk_size, 0, fileoffset - offset0, blocklen);
954 64a8571e 2022-01-07 stsp fileoffset += blocklen;
958 64a8571e 2022-01-07 stsp free(*deltas);
959 64a8571e 2022-01-07 stsp *deltas = NULL;
960 64a8571e 2022-01-07 stsp *ndeltas = 0;
962 64a8571e 2022-01-07 stsp return err;
