vcs-svn/svndiff.c

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