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 <limits.h>
24 #include <zlib.h>
25 #include <sha1.h>
26 #include <sha2.h>
27 #include <time.h>
28 #include <zlib.h>
29 
30 #include "got_error.h"
31 #include "got_repository.h"
32 #include "got_object.h"
33 #include "got_path.h"
34 
35 #include "got_lib_delta.h"
36 #include "got_lib_inflate.h"
37 #include "got_lib_object.h"
38 
39 #ifndef MIN
40 #define	MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
41 #endif
42 
43 struct got_delta *
44 got_delta_open(off_t offset, size_t tslen, int type, size_t size,
45     off_t data_offset)
46 {
47 	struct got_delta *delta;
48 
49 	delta = malloc(sizeof(*delta));
50 	if (delta == NULL)
51 		return NULL;
52 
53 	delta->type = type;
54 	delta->offset = offset;
55 	delta->tslen = tslen;
56 	delta->size = size;
57 	delta->data_offset = data_offset;
58 	return delta;
59 }
60 
61 const struct got_error *
62 got_delta_chain_get_base_type(int *type, struct got_delta_chain *deltas)
63 {
64 	struct got_delta *delta;
65 
66 	/* The first delta in the chain should represent the base object. */
67 	delta = STAILQ_FIRST(&deltas->entries);
68 	if (delta->type == GOT_OBJ_TYPE_COMMIT ||
69 	    delta->type == GOT_OBJ_TYPE_TREE ||
70 	    delta->type == GOT_OBJ_TYPE_BLOB ||
71 	    delta->type == GOT_OBJ_TYPE_TAG) {
72 		*type = delta->type;
73 		return NULL;
74 	}
75 
76 	return got_error(GOT_ERR_BAD_DELTA_CHAIN);
77 }
78 
79 /* Fetch another (required) byte from the delta stream. */
80 static const struct got_error *
81 next_delta_byte(const uint8_t **p, size_t *remain)
82 {
83 	if (--(*remain) == 0)
84 		return got_error_msg(GOT_ERR_BAD_DELTA,
85 		    "delta data truncated");
86 	(*p)++;
87 	return NULL;
88 }
89 
90 static const struct got_error *
91 parse_size(uint64_t *size, const uint8_t **p, size_t *remain)
92 {
93 	const struct got_error *err = NULL;
94 	int i = 0;
95 
96 	*size = 0;
97 	do {
98 		/* We do not support size values which don't fit in 64 bit. */
99 		if (i > 9)
100 			return got_error(GOT_ERR_NO_SPACE);
101 
102 		if (i == 0)
103 			*size = ((**p) & GOT_DELTA_SIZE_VAL_MASK);
104 		else {
105 			size_t shift = GOT_DELTA_SIZE_SHIFT * i;
106 			*size |= (((**p) & GOT_DELTA_SIZE_VAL_MASK) << shift);
107 		}
108 
109 		if (((**p) & GOT_DELTA_SIZE_MORE) == 0)
110 			break;
111 		i++;
112 		err = next_delta_byte(p, remain);
113 	} while (err == NULL);
114 
115 	return err;
116 }
117 
118 static const struct got_error *
119 parse_opcode(off_t *offset, size_t *len, const uint8_t **p, size_t *remain)
120 {
121 	const struct got_error *err = NULL;
122 	off_t o = 0;
123 	size_t l = 0;
124 	uint8_t opcode = **p;
125 
126 	if (opcode & GOT_DELTA_COPY_OFF1) {
127 		err = next_delta_byte(p, remain);
128 		if (err)
129 			return err;
130 		o = (off_t)(**p);
131 	}
132 	if (opcode & GOT_DELTA_COPY_OFF2) {
133 		err = next_delta_byte(p, remain);
134 		if (err)
135 			return err;
136 		o |= ((off_t)(**p)) << 8;
137 	}
138 	if (opcode & GOT_DELTA_COPY_OFF3) {
139 		err = next_delta_byte(p, remain);
140 		if (err)
141 			return err;
142 		o |= ((off_t)(**p)) << 16;
143 	}
144 	if (opcode & GOT_DELTA_COPY_OFF4) {
145 		err = next_delta_byte(p, remain);
146 		if (err)
147 			return err;
148 		o |= ((off_t)(**p)) << 24;
149 	}
150 
151 	if (opcode & GOT_DELTA_COPY_LEN1) {
152 		err = next_delta_byte(p, remain);
153 		if (err)
154 			return err;
155 		l = (off_t)(**p);
156 	}
157 	if (opcode & GOT_DELTA_COPY_LEN2) {
158 		err = next_delta_byte(p, remain);
159 		if (err)
160 			return err;
161 		l |= ((off_t)(**p)) << 8;
162 	}
163 	if (opcode & GOT_DELTA_COPY_LEN3) {
164 		err = next_delta_byte(p, remain);
165 		if (err)
166 			return err;
167 		l |= ((off_t)(**p)) << 16;
168 	}
169 
170 	if (o == 0)
171 		o = GOT_DELTA_COPY_DEFAULT_OFF;
172 	if (l == 0)
173 		l = GOT_DELTA_COPY_DEFAULT_LEN;
174 
175 	*offset = o;
176 	*len = l;
177 	return NULL;
178 }
179 
180 static const struct got_error *
181 copy_from_base(FILE *base_file, off_t offset, size_t size, FILE *outfile)
182 {
183 	if (fseeko(base_file, offset, SEEK_SET) != 0)
184 		return got_error_from_errno("fseeko");
185 
186 	while (size > 0) {
187 		uint8_t data[2048];
188 		size_t len = MIN(size, sizeof(data));
189 		size_t n;
190 
191 		n = fread(data, len, 1, base_file);
192 		if (n != 1)
193 			return got_ferror(base_file, GOT_ERR_IO);
194 
195 		n = fwrite(data, len, 1, outfile);
196 		if (n != 1)
197 			return got_ferror(outfile, GOT_ERR_IO);
198 
199 		size -= len;
200 	}
201 
202 	return NULL;
203 }
204 
205 static const struct got_error *
206 copy_from_delta(const uint8_t **p, size_t *remain, size_t len, FILE *outfile)
207 {
208 	size_t n;
209 
210 	if (*remain < len)
211 		return got_error_msg(GOT_ERR_BAD_DELTA,
212 		    "copy from beyond end of delta data");
213 
214 	n = fwrite(*p, len, 1, outfile);
215 	if (n != 1)
216 		return got_ferror(outfile, GOT_ERR_IO);
217 
218 	*p += len;
219 	*remain -= len;
220 	return NULL;
221 }
222 
223 static const struct got_error *
224 parse_delta_sizes(uint64_t *base_size, uint64_t *result_size,
225     const uint8_t **p, size_t *remain)
226 {
227 	const struct got_error *err;
228 
229 	/* Read the two size fields at the beginning of the stream. */
230 	err = parse_size(base_size, p, remain);
231 	if (err)
232 		return err;
233 	err = next_delta_byte(p, remain);
234 	if (err)
235 		return err;
236 	err = parse_size(result_size, p, remain);
237 	if (err)
238 		return err;
239 
240 	return NULL;
241 }
242 
243 const struct got_error *
244 got_delta_get_sizes(uint64_t *base_size, uint64_t *result_size,
245     const uint8_t *delta_buf, size_t delta_len)
246 {
247 	size_t remain;
248 	const uint8_t *p;
249 
250 	if (delta_len < GOT_DELTA_STREAM_LENGTH_MIN)
251 		return got_error_msg(GOT_ERR_BAD_DELTA, "delta too small");
252 
253 	p = delta_buf;
254 	remain = delta_len;
255 	return parse_delta_sizes(base_size, result_size, &p, &remain);
256 }
257 
258 const struct got_error *
259 got_delta_apply_in_mem(uint8_t *base_buf, size_t base_bufsz,
260     const uint8_t *delta_buf, size_t delta_len, uint8_t *outbuf,
261     size_t *outsize, size_t maxoutsize)
262 {
263 	const struct got_error *err = NULL;
264 	uint64_t base_size, result_size;
265 	size_t remain;
266 	const uint8_t *p;
267 
268 	*outsize= 0;
269 
270 	if (delta_len < GOT_DELTA_STREAM_LENGTH_MIN)
271 		return got_error_msg(GOT_ERR_BAD_DELTA, "delta too small");
272 
273 	p = delta_buf;
274 	remain = delta_len;
275 	err = parse_delta_sizes(&base_size, &result_size, &p, &remain);
276 	if (err)
277 		return err;
278 
279 	/* Decode and execute copy instructions from the delta stream. */
280 	err = next_delta_byte(&p, &remain);
281 	while (err == NULL && remain > 0) {
282 		if (*p & GOT_DELTA_BASE_COPY) {
283 			off_t offset = 0;
284 			size_t len = 0;
285 			err = parse_opcode(&offset, &len, &p, &remain);
286 			if (err)
287 				break;
288 			if (SIZE_MAX - offset < len || offset + len < 0 ||
289 			    base_bufsz < offset + len ||
290 			    *outsize + len > maxoutsize)
291 				return got_error_msg(GOT_ERR_BAD_DELTA,
292 				    "bad delta copy length");
293 			memcpy(outbuf + *outsize, base_buf + offset, len);
294 			if (err == NULL) {
295 				*outsize += len;
296 				if (remain > 0) {
297 					p++;
298 					remain--;
299 				}
300 			}
301 		} else {
302 			size_t len = (size_t)*p;
303 			if (len == 0) {
304 				err = got_error_msg(GOT_ERR_BAD_DELTA,
305 				    "zero length delta");
306 				break;
307 			}
308 			err = next_delta_byte(&p, &remain);
309 			if (err)
310 				break;
311 			if (remain < len || SIZE_MAX - *outsize < len ||
312 			    *outsize + len > maxoutsize)
313 				return got_error_msg(GOT_ERR_BAD_DELTA,
314 				    "bad delta copy length");
315 			memcpy(outbuf + *outsize, p, len);
316 			p += len;
317 			remain -= len;
318 			*outsize += len;
319 		}
320 	}
321 
322 	if (*outsize != result_size)
323 		err = got_error_msg(GOT_ERR_BAD_DELTA,
324 		    "delta application result size mismatch");
325 	return err;
326 }
327 
328 const struct got_error *
329 got_delta_apply(FILE *base_file, const uint8_t *delta_buf,
330     size_t delta_len, FILE *outfile, size_t *outsize)
331 {
332 	const struct got_error *err = NULL;
333 	uint64_t base_size, result_size;
334 	size_t remain = 0;
335 	const uint8_t *p;
336 	FILE *memstream = NULL;
337 	char *memstream_buf = NULL;
338 	size_t memstream_size = 0;
339 
340 	*outsize = 0;
341 
342 	if (delta_len < GOT_DELTA_STREAM_LENGTH_MIN)
343 		return got_error_msg(GOT_ERR_BAD_DELTA, "delta too small");
344 
345 	p = delta_buf;
346 	remain = delta_len;
347 	err = parse_delta_sizes(&base_size, &result_size, &p, &remain);
348 	if (err)
349 		return err;
350 
351 	if (result_size < GOT_DELTA_RESULT_SIZE_CACHED_MAX)
352 		memstream = open_memstream(&memstream_buf, &memstream_size);
353 
354 	/* Decode and execute copy instructions from the delta stream. */
355 	err = next_delta_byte(&p, &remain);
356 	while (err == NULL && remain > 0) {
357 		if (*p & GOT_DELTA_BASE_COPY) {
358 			off_t offset = 0;
359 			size_t len = 0;
360 			err = parse_opcode(&offset, &len, &p, &remain);
361 			if (err)
362 				break;
363 			err = copy_from_base(base_file, offset, len,
364 			    memstream ? memstream : outfile);
365 			if (err == NULL) {
366 				*outsize += len;
367 				if (remain > 0) {
368 					p++;
369 					remain--;
370 				}
371 			}
372 		} else {
373 			size_t len = (size_t)*p;
374 			if (len == 0) {
375 				err = got_error_msg(GOT_ERR_BAD_DELTA,
376 				    "zero length 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_msg(GOT_ERR_BAD_DELTA,
391 		    "delta application result size mismatch");
392 
393 	if (memstream != NULL) {
394 		if (fclose(memstream) == EOF)
395 			err = got_error_from_errno("fclose");
396 		if (err == NULL) {
397 			size_t n;
398 			n = fwrite(memstream_buf, 1, memstream_size, outfile);
399 			if (n != memstream_size)
400 				err = got_ferror(outfile, GOT_ERR_IO);
401 		}
402 		free(memstream_buf);
403 	}
404 	if (err == NULL)
405 		rewind(outfile);
406 	return err;
407 }