]>
Commit | Line | Data |
---|---|---|
ddcc8c5b JN |
1 | /* |
2 | * Licensed under a two-clause BSD-style license. | |
3 | * See LICENSE for details. | |
4 | */ | |
5 | ||
6 | #include "git-compat-util.h" | |
bcd25462 | 7 | #include "sliding_window.h" |
ddcc8c5b JN |
8 | #include "line_buffer.h" |
9 | #include "svndiff.h" | |
10 | ||
11 | /* | |
12 | * svndiff0 applier | |
13 | * | |
14 | * See http://svn.apache.org/repos/asf/subversion/trunk/notes/svndiff. | |
15 | * | |
16 | * svndiff0 ::= 'SVN\0' window* | |
25271211 | 17 | * window ::= int int int int int instructions inline_data; |
ec71aa2e JN |
18 | * instructions ::= instruction*; |
19 | * instruction ::= view_selector int int | |
20 | * | copyfrom_data int | |
21 | * | packed_view_selector int | |
22 | * | packed_copyfrom_data | |
23 | * ; | |
d3f131b5 JN |
24 | * view_selector ::= copyfrom_source |
25 | * | copyfrom_target | |
26 | * ; | |
c846e410 | 27 | * copyfrom_source ::= # binary 00 000000; |
d3f131b5 | 28 | * copyfrom_target ::= # binary 01 000000; |
ec71aa2e | 29 | * copyfrom_data ::= # binary 10 000000; |
d3f131b5 | 30 | * packed_view_selector ::= # view_selector OR-ed with 6 bit value; |
ec71aa2e | 31 | * packed_copyfrom_data ::= # copyfrom_data OR-ed with 6 bit value; |
25271211 JN |
32 | * int ::= highdigit* lowdigit; |
33 | * highdigit ::= # binary 1000 0000 OR-ed with 7 bit value; | |
34 | * lowdigit ::= # 7 bit value; | |
ddcc8c5b JN |
35 | */ |
36 | ||
ec71aa2e | 37 | #define INSN_MASK 0xc0 |
c846e410 | 38 | #define INSN_COPYFROM_SOURCE 0x00 |
d3f131b5 | 39 | #define INSN_COPYFROM_TARGET 0x40 |
ec71aa2e JN |
40 | #define INSN_COPYFROM_DATA 0x80 |
41 | #define OPERAND_MASK 0x3f | |
42 | ||
25271211 JN |
43 | #define VLI_CONTINUE 0x80 |
44 | #define VLI_DIGIT_MASK 0x7f | |
45 | #define VLI_BITS_PER_DIGIT 7 | |
46 | ||
fc4ae43b | 47 | struct window { |
c846e410 | 48 | struct sliding_view *in; |
ec71aa2e | 49 | struct strbuf out; |
ef2ac77e | 50 | struct strbuf instructions; |
fc4ae43b JN |
51 | struct strbuf data; |
52 | }; | |
53 | ||
c846e410 | 54 | #define WINDOW_INIT(w) { (w), STRBUF_INIT, STRBUF_INIT, STRBUF_INIT } |
fc4ae43b JN |
55 | |
56 | static void window_release(struct window *ctx) | |
57 | { | |
ec71aa2e | 58 | strbuf_release(&ctx->out); |
ef2ac77e | 59 | strbuf_release(&ctx->instructions); |
fc4ae43b JN |
60 | strbuf_release(&ctx->data); |
61 | } | |
62 | ||
ec71aa2e JN |
63 | static int write_strbuf(struct strbuf *sb, FILE *out) |
64 | { | |
65 | if (fwrite(sb->buf, 1, sb->len, out) == sb->len) /* Success. */ | |
66 | return 0; | |
1c8ead97 | 67 | return error_errno("cannot write delta postimage"); |
ec71aa2e JN |
68 | } |
69 | ||
ddcc8c5b JN |
70 | static int error_short_read(struct line_buffer *input) |
71 | { | |
72 | if (buffer_ferror(input)) | |
1c8ead97 | 73 | return error_errno("error reading delta"); |
ddcc8c5b JN |
74 | return error("invalid delta: unexpected end of file"); |
75 | } | |
76 | ||
fc4ae43b JN |
77 | static int read_chunk(struct line_buffer *delta, off_t *delta_len, |
78 | struct strbuf *buf, size_t len) | |
79 | { | |
96a60a87 | 80 | assert(*delta_len >= 0); |
fc4ae43b | 81 | strbuf_reset(buf); |
96a60a87 | 82 | if (len > (uintmax_t) *delta_len || |
fc4ae43b JN |
83 | buffer_read_binary(delta, buf, len) != len) |
84 | return error_short_read(delta); | |
85 | *delta_len -= buf->len; | |
86 | return 0; | |
87 | } | |
88 | ||
ddcc8c5b JN |
89 | static int read_magic(struct line_buffer *in, off_t *len) |
90 | { | |
91 | static const char magic[] = {'S', 'V', 'N', '\0'}; | |
92 | struct strbuf sb = STRBUF_INIT; | |
93 | ||
fc4ae43b | 94 | if (read_chunk(in, len, &sb, sizeof(magic))) { |
25271211 JN |
95 | strbuf_release(&sb); |
96 | return -1; | |
97 | } | |
25271211 JN |
98 | if (memcmp(sb.buf, magic, sizeof(magic))) { |
99 | strbuf_release(&sb); | |
ddcc8c5b | 100 | return error("invalid delta: unrecognized file type"); |
25271211 | 101 | } |
ddcc8c5b JN |
102 | strbuf_release(&sb); |
103 | return 0; | |
104 | } | |
105 | ||
25271211 JN |
106 | static int read_int(struct line_buffer *in, uintmax_t *result, off_t *len) |
107 | { | |
108 | uintmax_t rv = 0; | |
109 | off_t sz; | |
110 | for (sz = *len; sz; sz--) { | |
111 | const int ch = buffer_read_char(in); | |
112 | if (ch == EOF) | |
113 | break; | |
114 | ||
115 | rv <<= VLI_BITS_PER_DIGIT; | |
116 | rv += (ch & VLI_DIGIT_MASK); | |
117 | if (ch & VLI_CONTINUE) | |
118 | continue; | |
119 | ||
120 | *result = rv; | |
121 | *len = sz - 1; | |
122 | return 0; | |
123 | } | |
124 | return error_short_read(in); | |
125 | } | |
126 | ||
ec71aa2e JN |
127 | static int parse_int(const char **buf, size_t *result, const char *end) |
128 | { | |
129 | size_t rv = 0; | |
130 | const char *pos; | |
131 | for (pos = *buf; pos != end; pos++) { | |
132 | unsigned char ch = *pos; | |
133 | ||
134 | rv <<= VLI_BITS_PER_DIGIT; | |
135 | rv += (ch & VLI_DIGIT_MASK); | |
136 | if (ch & VLI_CONTINUE) | |
137 | continue; | |
138 | ||
139 | *result = rv; | |
140 | *buf = pos + 1; | |
141 | return 0; | |
142 | } | |
143 | return error("invalid delta: unexpected end of instructions section"); | |
144 | } | |
145 | ||
25271211 JN |
146 | static int read_offset(struct line_buffer *in, off_t *result, off_t *len) |
147 | { | |
148 | uintmax_t val; | |
149 | if (read_int(in, &val, len)) | |
150 | return -1; | |
151 | if (val > maximum_signed_value_of_type(off_t)) | |
152 | return error("unrepresentable offset in delta: %"PRIuMAX"", val); | |
153 | *result = val; | |
154 | return 0; | |
155 | } | |
156 | ||
157 | static int read_length(struct line_buffer *in, size_t *result, off_t *len) | |
158 | { | |
159 | uintmax_t val; | |
160 | if (read_int(in, &val, len)) | |
161 | return -1; | |
162 | if (val > SIZE_MAX) | |
163 | return error("unrepresentable length in delta: %"PRIuMAX"", val); | |
164 | *result = val; | |
165 | return 0; | |
166 | } | |
167 | ||
c846e410 JN |
168 | static int copyfrom_source(struct window *ctx, const char **instructions, |
169 | size_t nbytes, const char *insns_end) | |
170 | { | |
171 | size_t offset; | |
172 | if (parse_int(instructions, &offset, insns_end)) | |
173 | return -1; | |
174 | if (unsigned_add_overflows(offset, nbytes) || | |
175 | offset + nbytes > ctx->in->width) | |
176 | return error("invalid delta: copies source data outside view"); | |
177 | strbuf_add(&ctx->out, ctx->in->buf.buf + offset, nbytes); | |
178 | return 0; | |
179 | } | |
180 | ||
d3f131b5 JN |
181 | static int copyfrom_target(struct window *ctx, const char **instructions, |
182 | size_t nbytes, const char *instructions_end) | |
183 | { | |
184 | size_t offset; | |
185 | if (parse_int(instructions, &offset, instructions_end)) | |
186 | return -1; | |
187 | if (offset >= ctx->out.len) | |
188 | return error("invalid delta: copies from the future"); | |
189 | for (; nbytes > 0; nbytes--) | |
190 | strbuf_addch(&ctx->out, ctx->out.buf[offset++]); | |
191 | return 0; | |
192 | } | |
193 | ||
ec71aa2e JN |
194 | static int copyfrom_data(struct window *ctx, size_t *data_pos, size_t nbytes) |
195 | { | |
196 | const size_t pos = *data_pos; | |
197 | if (unsigned_add_overflows(pos, nbytes) || | |
198 | pos + nbytes > ctx->data.len) | |
199 | return error("invalid delta: copies unavailable inline data"); | |
200 | strbuf_add(&ctx->out, ctx->data.buf + pos, nbytes); | |
201 | *data_pos += nbytes; | |
202 | return 0; | |
203 | } | |
204 | ||
205 | static int parse_first_operand(const char **buf, size_t *out, const char *end) | |
206 | { | |
207 | size_t result = (unsigned char) *(*buf)++ & OPERAND_MASK; | |
208 | if (result) { /* immediate operand */ | |
209 | *out = result; | |
210 | return 0; | |
211 | } | |
212 | return parse_int(buf, out, end); | |
213 | } | |
214 | ||
215 | static int execute_one_instruction(struct window *ctx, | |
216 | const char **instructions, size_t *data_pos) | |
217 | { | |
218 | unsigned int instruction; | |
219 | const char *insns_end = ctx->instructions.buf + ctx->instructions.len; | |
220 | size_t nbytes; | |
221 | assert(ctx); | |
222 | assert(instructions && *instructions); | |
223 | assert(data_pos); | |
224 | ||
225 | instruction = (unsigned char) **instructions; | |
226 | if (parse_first_operand(instructions, &nbytes, insns_end)) | |
227 | return -1; | |
d3f131b5 | 228 | switch (instruction & INSN_MASK) { |
c846e410 JN |
229 | case INSN_COPYFROM_SOURCE: |
230 | return copyfrom_source(ctx, instructions, nbytes, insns_end); | |
d3f131b5 JN |
231 | case INSN_COPYFROM_TARGET: |
232 | return copyfrom_target(ctx, instructions, nbytes, insns_end); | |
233 | case INSN_COPYFROM_DATA: | |
234 | return copyfrom_data(ctx, data_pos, nbytes); | |
235 | default: | |
c846e410 | 236 | return error("invalid delta: unrecognized instruction"); |
d3f131b5 | 237 | } |
ec71aa2e JN |
238 | } |
239 | ||
240 | static int apply_window_in_core(struct window *ctx) | |
241 | { | |
242 | const char *instructions; | |
243 | size_t data_pos = 0; | |
244 | ||
245 | /* | |
246 | * Fill ctx->out.buf using data from the source, target, | |
247 | * and inline data views. | |
248 | */ | |
249 | for (instructions = ctx->instructions.buf; | |
250 | instructions != ctx->instructions.buf + ctx->instructions.len; | |
251 | ) | |
252 | if (execute_one_instruction(ctx, &instructions, &data_pos)) | |
253 | return -1; | |
4c9b93ed JN |
254 | if (data_pos != ctx->data.len) |
255 | return error("invalid delta: does not copy all inline data"); | |
ec71aa2e JN |
256 | return 0; |
257 | } | |
258 | ||
259 | static int apply_one_window(struct line_buffer *delta, off_t *delta_len, | |
c846e410 | 260 | struct sliding_view *preimage, FILE *out) |
25271211 | 261 | { |
4a161319 | 262 | int rv = -1; |
c846e410 | 263 | struct window ctx = WINDOW_INIT(preimage); |
25271211 JN |
264 | size_t out_len; |
265 | size_t instructions_len; | |
266 | size_t data_len; | |
267 | assert(delta_len); | |
268 | ||
269 | /* "source view" offset and length already handled; */ | |
270 | if (read_length(delta, &out_len, delta_len) || | |
271 | read_length(delta, &instructions_len, delta_len) || | |
ef2ac77e | 272 | read_length(delta, &data_len, delta_len) || |
ec71aa2e JN |
273 | read_chunk(delta, delta_len, &ctx.instructions, instructions_len) || |
274 | read_chunk(delta, delta_len, &ctx.data, data_len)) | |
275 | goto error_out; | |
276 | strbuf_grow(&ctx.out, out_len); | |
277 | if (apply_window_in_core(&ctx)) | |
fc4ae43b | 278 | goto error_out; |
ec71aa2e | 279 | if (ctx.out.len != out_len) { |
4a161319 | 280 | rv = error("invalid delta: incorrect postimage length"); |
fc4ae43b JN |
281 | goto error_out; |
282 | } | |
ec71aa2e | 283 | if (write_strbuf(&ctx.out, out)) |
fc4ae43b | 284 | goto error_out; |
4a161319 | 285 | rv = 0; |
fc4ae43b JN |
286 | error_out: |
287 | window_release(&ctx); | |
4a161319 | 288 | return rv; |
25271211 JN |
289 | } |
290 | ||
ddcc8c5b JN |
291 | int svndiff0_apply(struct line_buffer *delta, off_t delta_len, |
292 | struct sliding_view *preimage, FILE *postimage) | |
293 | { | |
96a60a87 | 294 | assert(delta && preimage && postimage && delta_len >= 0); |
ddcc8c5b JN |
295 | |
296 | if (read_magic(delta, &delta_len)) | |
297 | return -1; | |
25271211 | 298 | while (delta_len) { /* For each window: */ |
4a5de8dd | 299 | off_t pre_off = -1; |
25271211 JN |
300 | size_t pre_len; |
301 | ||
302 | if (read_offset(delta, &pre_off, &delta_len) || | |
303 | read_length(delta, &pre_len, &delta_len) || | |
bcd25462 | 304 | move_window(preimage, pre_off, pre_len) || |
c846e410 | 305 | apply_one_window(delta, &delta_len, preimage, postimage)) |
25271211 JN |
306 | return -1; |
307 | } | |
ddcc8c5b JN |
308 | return 0; |
309 | } |