2 718b3ab0 2018-03-17 stsp * Copyright (c) 2018 Stefan Sperling <stsp@openbsd.org>
4 718b3ab0 2018-03-17 stsp * Permission to use, copy, modify, and distribute this software for any
5 718b3ab0 2018-03-17 stsp * purpose with or without fee is hereby granted, provided that the above
6 718b3ab0 2018-03-17 stsp * copyright notice and this permission notice appear in all copies.
8 718b3ab0 2018-03-17 stsp * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 718b3ab0 2018-03-17 stsp * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 718b3ab0 2018-03-17 stsp * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 718b3ab0 2018-03-17 stsp * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 718b3ab0 2018-03-17 stsp * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 718b3ab0 2018-03-17 stsp * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 718b3ab0 2018-03-17 stsp * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 718b3ab0 2018-03-17 stsp struct got_delta {
18 718b3ab0 2018-03-17 stsp SIMPLEQ_ENTRY(got_delta) entry;
19 718b3ab0 2018-03-17 stsp off_t offset;
20 718b3ab0 2018-03-17 stsp size_t tslen;
22 718b3ab0 2018-03-17 stsp size_t size;
23 718b3ab0 2018-03-17 stsp off_t data_offset;
24 718b3ab0 2018-03-17 stsp uint8_t *delta_buf;
25 718b3ab0 2018-03-17 stsp size_t delta_len;
28 718b3ab0 2018-03-17 stsp struct got_delta_chain {
29 718b3ab0 2018-03-17 stsp int nentries;
30 718b3ab0 2018-03-17 stsp SIMPLEQ_HEAD(, got_delta) entries;
33 7918459e 2018-04-24 stsp #define GOT_DELTA_CHAIN_RECURSION_MAX 500
35 c336f889 2018-07-23 stsp struct got_delta *got_delta_open(off_t, size_t, int, size_t, off_t,
36 c336f889 2018-07-23 stsp uint8_t *, size_t);
37 718b3ab0 2018-03-17 stsp const struct got_error *got_delta_chain_get_base_type(int *,
38 718b3ab0 2018-03-17 stsp struct got_delta_chain *);
39 718b3ab0 2018-03-17 stsp const struct got_error *got_delta_get_sizes(uint64_t *, uint64_t *,
40 718b3ab0 2018-03-17 stsp const uint8_t *, size_t);
41 34fca9c3 2018-11-11 stsp const struct got_error *got_delta_apply_in_mem(uint8_t *, size_t,
42 34fca9c3 2018-11-11 stsp const uint8_t *, size_t, uint8_t *, size_t *, size_t);
43 718b3ab0 2018-03-17 stsp const struct got_error *got_delta_apply(FILE *, const uint8_t *, size_t,
44 718b3ab0 2018-03-17 stsp FILE *, size_t *);
47 718b3ab0 2018-03-17 stsp * The amount of result data we may keep in RAM while applying deltas.
48 718b3ab0 2018-03-17 stsp * Data larger than this is written to disk during delta application (slow).
50 718b3ab0 2018-03-17 stsp #define GOT_DELTA_RESULT_SIZE_CACHED_MAX (4 * 1024 * 1024) /* bytes */
53 718b3ab0 2018-03-17 stsp * Definitions for delta data streams.
56 718b3ab0 2018-03-17 stsp #define GOT_DELTA_STREAM_LENGTH_MIN 4 /* bytes */
59 718b3ab0 2018-03-17 stsp * A delta stream begins with two size fields. The first specifies the
60 718b3ab0 2018-03-17 stsp * size of the delta base, and the second describes the expected size of
61 718b3ab0 2018-03-17 stsp * the data which results from applying the delta to the delta base.
63 718b3ab0 2018-03-17 stsp * Each size field uses a variable length encoding:
64 718b3ab0 2018-03-17 stsp * size0...sizeN form a 7+7+7+...+7 bit integer, where size0 is the
65 718b3ab0 2018-03-17 stsp * least significant part and sizeN is the most significant part.
66 718b3ab0 2018-03-17 stsp * If the MSB of a size byte is set, an additional size byte follows.
68 718b3ab0 2018-03-17 stsp #define GOT_DELTA_SIZE_VAL_MASK 0x7f
69 718b3ab0 2018-03-17 stsp #define GOT_DELTA_SIZE_SHIFT 7
70 718b3ab0 2018-03-17 stsp #define GOT_DELTA_SIZE_MORE 0x80
73 718b3ab0 2018-03-17 stsp * The rest of the delta stream contains copy instructions.
75 718b3ab0 2018-03-17 stsp * A base copy instruction copies N bytes starting at offset X from the delta
76 718b3ab0 2018-03-17 stsp * base to the output. Base copy instructions begin with a byte which has its
77 718b3ab0 2018-03-17 stsp * MSB set. The remaining bits of this byte describe how many offset and
78 718b3ab0 2018-03-17 stsp * length value bytes follow.
79 718b3ab0 2018-03-17 stsp * The offset X is encoded in 1 to 4 bytes, and the length N is encoded in
80 718b3ab0 2018-03-17 stsp * 1 to 3 bytes. For both values, the first byte contributes the least
81 718b3ab0 2018-03-17 stsp * significant part and the last byte which is present contributes the
82 718b3ab0 2018-03-17 stsp * most significant part.
83 718b3ab0 2018-03-17 stsp * If the offset value is omitted, an offset of zero is implied.
84 718b3ab0 2018-03-17 stsp * If the length value is omitted, a default length of 65536 bytes is implied.
86 718b3ab0 2018-03-17 stsp * An inline copy instruction copies data from the delta stream to the output.
87 718b3ab0 2018-03-17 stsp * Such instructions begin with one byte which does not have the MSB set
88 718b3ab0 2018-03-17 stsp * and which specifies the length of the inline data which follows (i.e.
89 718b3ab0 2018-03-17 stsp * at most 127 bytes). A length value of zero is invalid.
92 718b3ab0 2018-03-17 stsp #define GOT_DELTA_BASE_COPY 0x80
94 718b3ab0 2018-03-17 stsp #define GOT_DELTA_COPY_OFF1 0x01 /* byte 1 of offset is present */
95 718b3ab0 2018-03-17 stsp #define GOT_DELTA_COPY_OFF2 0x02 /* byte 2 of offset is present */
96 718b3ab0 2018-03-17 stsp #define GOT_DELTA_COPY_OFF3 0x04 /* byte 3 of offset is present */
97 718b3ab0 2018-03-17 stsp #define GOT_DELTA_COPY_OFF4 0x08 /* byte 4 of offset is present */
99 718b3ab0 2018-03-17 stsp #define GOT_DELTA_COPY_LEN1 0x10 /* byte 1 of length is present */
100 718b3ab0 2018-03-17 stsp #define GOT_DELTA_COPY_LEN2 0x20 /* byte 2 of length is present */
101 718b3ab0 2018-03-17 stsp #define GOT_DELTA_COPY_LEN3 0x40 /* byte 3 of length is present */
103 718b3ab0 2018-03-17 stsp #define GOT_DELTA_COPY_DEFAULT_OFF 0x0 /* default offset if omitted */
104 718b3ab0 2018-03-17 stsp #define GOT_DELTA_COPY_DEFAULT_LEN 0x10000 /* default length if omitted */
