1 /*
2  * Copyright (c) 2018 Stefan Sperling <stsp@openbsd.org>
3  *
4  * Permission to use, copy, modify, and distribute this software for any
5  * purpose with or without fee is hereby granted, provided that the above
6  * copyright notice and this permission notice appear in all copies.
7  *
8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15  */
16 
17 #include <sys/queue.h>
18 
19 #include <stdio.h>
20 #include <stdlib.h>
21 #include <stdint.h>
22 #include <string.h>
23 #include <zlib.h>
24 #include <sha1.h>
25 #include <time.h>
26 #include <zlib.h>
27 
28 #include "got_error.h"
29 #include "got_repository.h"
30 #include "got_object.h"
31 #include "got_path.h"
32 
33 #include "got_lib_delta.h"
34 #include "got_lib_inflate.h"
35 #include "got_lib_object.h"
36 
37 #ifndef MIN
38 #define	MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
39 #endif
40 
41 struct got_delta *
42 got_delta_open(off_t offset, size_t tslen, int type, size_t size,
43     off_t data_offset, uint8_t *delta_buf, size_t delta_len)
44 {
45 	struct got_delta *delta;
46 
47 	delta = malloc(sizeof(*delta));
48 	if (delta == NULL)
49 		return NULL;
50 
51 	delta->type = type;
52 	delta->offset = offset;
53 	delta->tslen = tslen;
54 	delta->size = size;
55 	delta->data_offset = data_offset;
56 	delta->delta_buf = delta_buf;
57 	delta->delta_len = delta_len;
58 	return delta;
59 }
60 
61 void
62 got_delta_close(struct got_delta *delta)
63 {
64 	free(delta->delta_buf);
65 	free(delta);
66 }
67 
68 const struct got_error *
69 got_delta_chain_get_base_type(int *type, struct got_delta_chain *deltas)
70 {
71 	struct got_delta *delta;
72 
73 	/* The first delta in the chain should represent the base object. */
74 	delta = SIMPLEQ_FIRST(&deltas->entries);
75 	if (delta->type == GOT_OBJ_TYPE_COMMIT ||
76 	    delta->type == GOT_OBJ_TYPE_TREE ||
77 	    delta->type == GOT_OBJ_TYPE_BLOB ||
78 	    delta->type == GOT_OBJ_TYPE_TAG) {
79 		*type = delta->type;
80 		return NULL;
81 	}
82 
83 	return got_error(GOT_ERR_BAD_DELTA_CHAIN);
84 }
85 
86 /* Fetch another (required) byte from the delta stream. */
87 static const struct got_error *
88 next_delta_byte(const uint8_t **p, size_t *remain)
89 {
90 	if (--(*remain) == 0)
91 		return got_error(GOT_ERR_BAD_DELTA);
92 	(*p)++;
93 	return NULL;
94 }
95 
96 static const struct got_error *
97 parse_size(uint64_t *size, const uint8_t **p, size_t *remain)
98 {
99 	const struct got_error *err = NULL;
100 	int i = 0;
101 
102 	*size = 0;
103 	do {
104 		/* We do not support size values which don't fit in 64 bit. */
105 		if (i > 9)
106 			return got_error(GOT_ERR_NO_SPACE);
107 
108 		if (i == 0)
109 			*size = ((**p) & GOT_DELTA_SIZE_VAL_MASK);
110 		else {
111 			size_t shift = GOT_DELTA_SIZE_SHIFT * i;
112 			*size |= (((**p) & GOT_DELTA_SIZE_VAL_MASK) << shift);
113 		}
114 
115 		if (((**p) & GOT_DELTA_SIZE_MORE) == 0)
116 			break;
117 		i++;
118 		err = next_delta_byte(p, remain);
119 	} while (err == NULL);
120 
121 	return err;
122 }
123 
124 static const struct got_error *
125 parse_opcode(off_t *offset, size_t *len, const uint8_t **p, size_t *remain)
126 {
127 	const struct got_error *err = NULL;
128 	off_t o = 0;
129 	size_t l = 0;
130 	uint8_t opcode = **p;
131 
132 	if (opcode & GOT_DELTA_COPY_OFF1) {
133 		err = next_delta_byte(p, remain);
134 		if (err)
135 			return err;
136 		o = (off_t)(**p);
137 	}
138 	if (opcode & GOT_DELTA_COPY_OFF2) {
139 		err = next_delta_byte(p, remain);
140 		if (err)
141 			return err;
142 		o |= ((off_t)(**p)) << 8;
143 	}
144 	if (opcode & GOT_DELTA_COPY_OFF3) {
145 		err = next_delta_byte(p, remain);
146 		if (err)
147 			return err;
148 		o |= ((off_t)(**p)) << 16;
149 	}
150 	if (opcode & GOT_DELTA_COPY_OFF4) {
151 		err = next_delta_byte(p, remain);
152 		if (err)
153 			return err;
154 		o |= ((off_t)(**p)) << 24;
155 	}
156 
157 	if (opcode & GOT_DELTA_COPY_LEN1) {
158 		err = next_delta_byte(p, remain);
159 		if (err)
160 			return err;
161 		l = (off_t)(**p);
162 	}
163 	if (opcode & GOT_DELTA_COPY_LEN2) {
164 		err = next_delta_byte(p, remain);
165 		if (err)
166 			return err;
167 		l |= ((off_t)(**p)) << 8;
168 	}
169 	if (opcode & GOT_DELTA_COPY_LEN3) {
170 		err = next_delta_byte(p, remain);
171 		if (err)
172 			return err;
173 		l |= ((off_t)(**p)) << 16;
174 	}
175 
176 	if (o == 0)
177 		o = GOT_DELTA_COPY_DEFAULT_OFF;
178 	if (l == 0)
179 		l = GOT_DELTA_COPY_DEFAULT_LEN;
180 
181 	*offset = o;
182 	*len = l;
183 	return NULL;
184 }
185 
186 static const struct got_error *
187 copy_from_base(FILE *base_file, off_t offset, size_t size, FILE *outfile)
188 {
189 	if (fseeko(base_file, offset, SEEK_SET) != 0)
190 		return got_error_from_errno("fseeko");
191 
192 	while (size > 0) {
193 		uint8_t data[2048];
194 		size_t len = MIN(size, sizeof(data));
195 		size_t n;
196 
197 		n = fread(data, len, 1, base_file);
198 		if (n != 1)
199 			return got_ferror(base_file, GOT_ERR_IO);
200 
201 		n = fwrite(data, len, 1, outfile);
202 		if (n != 1)
203 			return got_ferror(outfile, GOT_ERR_IO);
204 
205 		size -= len;
206 	}
207 
208 	return NULL;
209 }
210 
211 static const struct got_error *
212 copy_from_delta(const uint8_t **p, size_t *remain, size_t len, FILE *outfile)
213 {
214 	size_t n;
215 
216 	if (*remain < len)
217 		return got_error(GOT_ERR_BAD_DELTA);
218 
219 	n = fwrite(*p, len, 1, outfile);
220 	if (n != 1)
221 		return got_ferror(outfile, GOT_ERR_IO);
222 
223 	*p += len;
224 	*remain -= len;
225 	return NULL;
226 }
227 
228 static const struct got_error *
229 parse_delta_sizes(uint64_t *base_size, uint64_t *result_size,
230     const uint8_t **p, size_t *remain)
231 {
232 	const struct got_error *err;
233 
234 	/* Read the two size fields at the beginning of the stream. */
235 	err = parse_size(base_size, p, remain);
236 	if (err)
237 		return err;
238 	err = next_delta_byte(p, remain);
239 	if (err)
240 		return err;
241 	err = parse_size(result_size, p, remain);
242 	if (err)
243 		return err;
244 
245 	return NULL;
246 }
247 
248 const struct got_error *
249 got_delta_get_sizes(uint64_t *base_size, uint64_t *result_size,
250     const uint8_t *delta_buf, size_t delta_len)
251 {
252 	size_t remain;
253 	const uint8_t *p;
254 
255 	if (delta_len < GOT_DELTA_STREAM_LENGTH_MIN)
256 		return got_error(GOT_ERR_BAD_DELTA);
257 
258 	p = delta_buf;
259 	remain = delta_len;
260 	return parse_delta_sizes(base_size, result_size, &p, &remain);
261 }
262 
263 const struct got_error *
264 got_delta_apply_in_mem(uint8_t *base_buf, size_t base_bufsz,
265     const uint8_t *delta_buf, size_t delta_len, uint8_t *outbuf,
266     size_t *outsize, size_t maxoutsize)
267 {
268 	const struct got_error *err = NULL;
269 	uint64_t base_size, result_size;
270 	size_t remain;
271 	const uint8_t *p;
272 
273 	*outsize= 0;
274 
275 	if (delta_len < GOT_DELTA_STREAM_LENGTH_MIN)
276 		return got_error(GOT_ERR_BAD_DELTA);
277 
278 	p = delta_buf;
279 	remain = delta_len;
280 	err = parse_delta_sizes(&base_size, &result_size, &p, &remain);
281 	if (err)
282 		return err;
283 
284 	/* Decode and execute copy instructions from the delta stream. */
285 	err = next_delta_byte(&p, &remain);
286 	while (err == NULL && remain > 0) {
287 		if (*p & GOT_DELTA_BASE_COPY) {
288 			off_t offset = 0;
289 			size_t len = 0;
290 			err = parse_opcode(&offset, &len, &p, &remain);
291 			if (err)
292 				break;
293 			if (SIZE_MAX - offset < len || offset + len < 0 ||
294 			    base_bufsz < offset + len ||
295 			    *outsize + len > maxoutsize)
296 				return got_error(GOT_ERR_BAD_DELTA);
297 			memcpy(outbuf + *outsize, base_buf + offset, len);
298 			if (err == NULL) {
299 				*outsize += len;
300 				if (remain > 0) {
301 					p++;
302 					remain--;
303 				}
304 			}
305 		} else {
306 			size_t len = (size_t)*p;
307 			if (len == 0) {
308 				err = got_error(GOT_ERR_BAD_DELTA);
309 				break;
310 			}
311 			err = next_delta_byte(&p, &remain);
312 			if (err)
313 				break;
314 			if (remain < len || SIZE_MAX - *outsize < len ||
315 			    *outsize + len > maxoutsize)
316 				return got_error(GOT_ERR_BAD_DELTA);
317 			memcpy(outbuf + *outsize, p, len);
318 			p += len;
319 			remain -= len;
320 			*outsize += len;
321 		}
322 	}
323 
324 	if (*outsize != result_size)
325 		err = got_error(GOT_ERR_BAD_DELTA);
326 	return err;
327 }
328 
329 const struct got_error *
330 got_delta_apply(FILE *base_file, const uint8_t *delta_buf,
331     size_t delta_len, FILE *outfile, size_t *outsize)
332 {
333 	const struct got_error *err = NULL;
334 	uint64_t base_size, result_size;
335 	size_t remain = 0;
336 	const uint8_t *p;
337 	FILE *memstream = NULL;
338 	char *memstream_buf = NULL;
339 	size_t memstream_size = 0;
340 
341 	*outsize = 0;
342 
343 	if (delta_len < GOT_DELTA_STREAM_LENGTH_MIN)
344 		return got_error(GOT_ERR_BAD_DELTA);
345 
346 	p = delta_buf;
347 	remain = delta_len;
348 	err = parse_delta_sizes(&base_size, &result_size, &p, &remain);
349 	if (err)
350 		return err;
351 
352 	if (result_size < GOT_DELTA_RESULT_SIZE_CACHED_MAX)
353 		memstream = open_memstream(&memstream_buf, &memstream_size);
354 
355 	/* Decode and execute copy instructions from the delta stream. */
356 	err = next_delta_byte(&p, &remain);
357 	while (err == NULL && remain > 0) {
358 		if (*p & GOT_DELTA_BASE_COPY) {
359 			off_t offset = 0;
360 			size_t len = 0;
361 			err = parse_opcode(&offset, &len, &p, &remain);
362 			if (err)
363 				break;
364 			err = copy_from_base(base_file, offset, len,
365 			    memstream ? memstream : outfile);
366 			if (err == NULL) {
367 				*outsize += len;
368 				if (remain > 0) {
369 					p++;
370 					remain--;
371 				}
372 			}
373 		} else {
374 			size_t len = (size_t)*p;
375 			if (len == 0) {
376 				err = got_error(GOT_ERR_BAD_DELTA);
377 				break;
378 			}
379 			err = next_delta_byte(&p, &remain);
380 			if (err)
381 				break;
382 			err = copy_from_delta(&p, &remain, len,
383 			    memstream ? memstream : outfile);
384 			if (err == NULL)
385 				*outsize += len;
386 		}
387 	}
388 
389 	if (*outsize != result_size)
390 		err = got_error(GOT_ERR_BAD_DELTA);
391 
392 	if (memstream != NULL) {
393 		if (fclose(memstream) != 0)
394 			err = got_error_from_errno("fclose");
395 		if (err == NULL) {
396 			size_t n;
397 			n = fwrite(memstream_buf, 1, memstream_size, outfile);
398 			if (n != memstream_size)
399 				err = got_ferror(outfile, GOT_ERR_IO);
400 		}
401 		free(memstream_buf);
402 	}
403 	if (err == NULL)
404 		rewind(outfile);
405 	return err;
406 }