2 * Licensed under a two-clause BSD-style license.
3 * See LICENSE for details.
6 #include "git-compat-util.h"
7 #include "sliding_window.h"
8 #include "line_buffer.h"
14 * See http://svn.apache.org/repos/asf/subversion/trunk/notes/svndiff.
16 * svndiff0 ::= 'SVN\0' window*
17 * window ::= int int int int int instructions inline_data;
18 * instructions ::= instruction*;
19 * instruction ::= view_selector int int
21 * | packed_view_selector int
22 * | packed_copyfrom_data
24 * view_selector ::= copyfrom_source
27 * copyfrom_target ::= # binary 01 000000;
28 * copyfrom_data ::= # binary 10 000000;
29 * packed_view_selector ::= # view_selector OR-ed with 6 bit value;
30 * packed_copyfrom_data ::= # copyfrom_data OR-ed with 6 bit value;
31 * int ::= highdigit* lowdigit;
32 * highdigit ::= # binary 1000 0000 OR-ed with 7 bit value;
33 * lowdigit ::= # 7 bit value;
36 #define INSN_MASK 0xc0
37 #define INSN_COPYFROM_TARGET 0x40
38 #define INSN_COPYFROM_DATA 0x80
39 #define OPERAND_MASK 0x3f
41 #define VLI_CONTINUE 0x80
42 #define VLI_DIGIT_MASK 0x7f
43 #define VLI_BITS_PER_DIGIT 7
47 struct strbuf instructions
;
51 #define WINDOW_INIT { STRBUF_INIT, STRBUF_INIT, STRBUF_INIT }
53 static void window_release(struct window
*ctx
)
55 strbuf_release(&ctx
->out
);
56 strbuf_release(&ctx
->instructions
);
57 strbuf_release(&ctx
->data
);
60 static int write_strbuf(struct strbuf
*sb
, FILE *out
)
62 if (fwrite(sb
->buf
, 1, sb
->len
, out
) == sb
->len
) /* Success. */
64 return error("cannot write delta postimage: %s", strerror(errno
));
67 static int error_short_read(struct line_buffer
*input
)
69 if (buffer_ferror(input
))
70 return error("error reading delta: %s", strerror(errno
));
71 return error("invalid delta: unexpected end of file");
74 static int read_chunk(struct line_buffer
*delta
, off_t
*delta_len
,
75 struct strbuf
*buf
, size_t len
)
78 if (len
> *delta_len
||
79 buffer_read_binary(delta
, buf
, len
) != len
)
80 return error_short_read(delta
);
81 *delta_len
-= buf
->len
;
85 static int read_magic(struct line_buffer
*in
, off_t
*len
)
87 static const char magic
[] = {'S', 'V', 'N', '\0'};
88 struct strbuf sb
= STRBUF_INIT
;
90 if (read_chunk(in
, len
, &sb
, sizeof(magic
))) {
94 if (memcmp(sb
.buf
, magic
, sizeof(magic
))) {
96 return error("invalid delta: unrecognized file type");
102 static int read_int(struct line_buffer
*in
, uintmax_t *result
, off_t
*len
)
106 for (sz
= *len
; sz
; sz
--) {
107 const int ch
= buffer_read_char(in
);
111 rv
<<= VLI_BITS_PER_DIGIT
;
112 rv
+= (ch
& VLI_DIGIT_MASK
);
113 if (ch
& VLI_CONTINUE
)
120 return error_short_read(in
);
123 static int parse_int(const char **buf
, size_t *result
, const char *end
)
127 for (pos
= *buf
; pos
!= end
; pos
++) {
128 unsigned char ch
= *pos
;
130 rv
<<= VLI_BITS_PER_DIGIT
;
131 rv
+= (ch
& VLI_DIGIT_MASK
);
132 if (ch
& VLI_CONTINUE
)
139 return error("invalid delta: unexpected end of instructions section");
142 static int read_offset(struct line_buffer
*in
, off_t
*result
, off_t
*len
)
145 if (read_int(in
, &val
, len
))
147 if (val
> maximum_signed_value_of_type(off_t
))
148 return error("unrepresentable offset in delta: %"PRIuMAX
"", val
);
153 static int read_length(struct line_buffer
*in
, size_t *result
, off_t
*len
)
156 if (read_int(in
, &val
, len
))
159 return error("unrepresentable length in delta: %"PRIuMAX
"", val
);
164 static int copyfrom_target(struct window
*ctx
, const char **instructions
,
165 size_t nbytes
, const char *instructions_end
)
168 if (parse_int(instructions
, &offset
, instructions_end
))
170 if (offset
>= ctx
->out
.len
)
171 return error("invalid delta: copies from the future");
172 for (; nbytes
> 0; nbytes
--)
173 strbuf_addch(&ctx
->out
, ctx
->out
.buf
[offset
++]);
177 static int copyfrom_data(struct window
*ctx
, size_t *data_pos
, size_t nbytes
)
179 const size_t pos
= *data_pos
;
180 if (unsigned_add_overflows(pos
, nbytes
) ||
181 pos
+ nbytes
> ctx
->data
.len
)
182 return error("invalid delta: copies unavailable inline data");
183 strbuf_add(&ctx
->out
, ctx
->data
.buf
+ pos
, nbytes
);
188 static int parse_first_operand(const char **buf
, size_t *out
, const char *end
)
190 size_t result
= (unsigned char) *(*buf
)++ & OPERAND_MASK
;
191 if (result
) { /* immediate operand */
195 return parse_int(buf
, out
, end
);
198 static int execute_one_instruction(struct window
*ctx
,
199 const char **instructions
, size_t *data_pos
)
201 unsigned int instruction
;
202 const char *insns_end
= ctx
->instructions
.buf
+ ctx
->instructions
.len
;
205 assert(instructions
&& *instructions
);
208 instruction
= (unsigned char) **instructions
;
209 if (parse_first_operand(instructions
, &nbytes
, insns_end
))
211 switch (instruction
& INSN_MASK
) {
212 case INSN_COPYFROM_TARGET
:
213 return copyfrom_target(ctx
, instructions
, nbytes
, insns_end
);
214 case INSN_COPYFROM_DATA
:
215 return copyfrom_data(ctx
, data_pos
, nbytes
);
217 return error("Unknown instruction %x", instruction
);
221 static int apply_window_in_core(struct window
*ctx
)
223 const char *instructions
;
227 * Fill ctx->out.buf using data from the source, target,
228 * and inline data views.
230 for (instructions
= ctx
->instructions
.buf
;
231 instructions
!= ctx
->instructions
.buf
+ ctx
->instructions
.len
;
233 if (execute_one_instruction(ctx
, &instructions
, &data_pos
))
235 if (data_pos
!= ctx
->data
.len
)
236 return error("invalid delta: does not copy all inline data");
240 static int apply_one_window(struct line_buffer
*delta
, off_t
*delta_len
,
243 struct window ctx
= WINDOW_INIT
;
245 size_t instructions_len
;
249 /* "source view" offset and length already handled; */
250 if (read_length(delta
, &out_len
, delta_len
) ||
251 read_length(delta
, &instructions_len
, delta_len
) ||
252 read_length(delta
, &data_len
, delta_len
) ||
253 read_chunk(delta
, delta_len
, &ctx
.instructions
, instructions_len
) ||
254 read_chunk(delta
, delta_len
, &ctx
.data
, data_len
))
256 strbuf_grow(&ctx
.out
, out_len
);
257 if (apply_window_in_core(&ctx
))
259 if (ctx
.out
.len
!= out_len
) {
260 error("invalid delta: incorrect postimage length");
263 if (write_strbuf(&ctx
.out
, out
))
265 window_release(&ctx
);
268 window_release(&ctx
);
272 int svndiff0_apply(struct line_buffer
*delta
, off_t delta_len
,
273 struct sliding_view
*preimage
, FILE *postimage
)
275 assert(delta
&& preimage
&& postimage
);
277 if (read_magic(delta
, &delta_len
))
279 while (delta_len
) { /* For each window: */
283 if (read_offset(delta
, &pre_off
, &delta_len
) ||
284 read_length(delta
, &pre_len
, &delta_len
) ||
285 move_window(preimage
, pre_off
, pre_len
) ||
286 apply_one_window(delta
, &delta_len
, postimage
))