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  * view_selector ::= copyfrom_source
  25  *   | copyfrom_target
  26  *   ;
  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;
  34  */
  35
  36 #define INSN_MASK       0xc0
  37 #define INSN_COPYFROM_TARGET    0x40
  38 #define INSN_COPYFROM_DATA      0x80
  39 #define OPERAND_MASK    0x3f
  40
  41 #define VLI_CONTINUE    0x80
  42 #define VLI_DIGIT_MASK  0x7f
  43 #define VLI_BITS_PER_DIGIT 7
  44
  45 struct window {
  46         struct strbuf out;
  47         struct strbuf instructions;
  48         struct strbuf data;
  49 };
  50
  51 #define WINDOW_INIT     { STRBUF_INIT, STRBUF_INIT, STRBUF_INIT }
  52
  53 static void window_release(struct window *ctx)
  54 {
  55         strbuf_release(&ctx->out);
  56         strbuf_release(&ctx->instructions);
  57         strbuf_release(&ctx->data);
  58 }
  59
  60 static int write_strbuf(struct strbuf *sb, FILE *out)
  61 {
  62         if (fwrite(sb->buf, 1, sb->len, out) == sb->len)        /* Success. */
  63                 return 0;
  64         return error("cannot write delta postimage: %s", strerror(errno));
  65 }
  66
  67 static int error_short_read(struct line_buffer *input)
  68 {
  69         if (buffer_ferror(input))
  70                 return error("error reading delta: %s", strerror(errno));
  71         return error("invalid delta: unexpected end of file");
  72 }
  73
  74 static int read_chunk(struct line_buffer *delta, off_t *delta_len,
  75                       struct strbuf *buf, size_t len)
  76 {
  77         strbuf_reset(buf);
  78         if (len > *delta_len ||
  79             buffer_read_binary(delta, buf, len) != len)
  80                 return error_short_read(delta);
  81         *delta_len -= buf->len;
  82         return 0;
  83 }
  84
  85 static int read_magic(struct line_buffer *in, off_t *len)
  86 {
  87         static const char magic[] = {'S', 'V', 'N', '\0'};
  88         struct strbuf sb = STRBUF_INIT;
  89
  90         if (read_chunk(in, len, &sb, sizeof(magic))) {
  91                 strbuf_release(&sb);
  92                 return -1;
  93         }
  94         if (memcmp(sb.buf, magic, sizeof(magic))) {
  95                 strbuf_release(&sb);
  96                 return error("invalid delta: unrecognized file type");
  97         }
  98         strbuf_release(&sb);
  99         return 0;
 100 }
 101
 102 static int read_int(struct line_buffer *in, uintmax_t *result, off_t *len)
 103 {
 104         uintmax_t rv = 0;
 105         off_t sz;
 106         for (sz = *len; sz; sz--) {
 107                 const int ch = buffer_read_char(in);
 108                 if (ch == EOF)
 109                         break;
 110
 111                 rv <<= VLI_BITS_PER_DIGIT;
 112                 rv += (ch & VLI_DIGIT_MASK);
 113                 if (ch & VLI_CONTINUE)
 114                         continue;
 115
 116                 *result = rv;
 117                 *len = sz - 1;
 118                 return 0;
 119         }
 120         return error_short_read(in);
 121 }
 122
 123 static int parse_int(const char **buf, size_t *result, const char *end)
 124 {
 125         size_t rv = 0;
 126         const char *pos;
 127         for (pos = *buf; pos != end; pos++) {
 128                 unsigned char ch = *pos;
 129
 130                 rv <<= VLI_BITS_PER_DIGIT;
 131                 rv += (ch & VLI_DIGIT_MASK);
 132                 if (ch & VLI_CONTINUE)
 133                         continue;
 134
 135                 *result = rv;
 136                 *buf = pos + 1;
 137                 return 0;
 138         }
 139         return error("invalid delta: unexpected end of instructions section");
 140 }
 141
 142 static int read_offset(struct line_buffer *in, off_t *result, off_t *len)
 143 {
 144         uintmax_t val;
 145         if (read_int(in, &val, len))
 146                 return -1;
 147         if (val > maximum_signed_value_of_type(off_t))
 148                 return error("unrepresentable offset in delta: %"PRIuMAX"", val);
 149         *result = val;
 150         return 0;
 151 }
 152
 153 static int read_length(struct line_buffer *in, size_t *result, off_t *len)
 154 {
 155         uintmax_t val;
 156         if (read_int(in, &val, len))
 157                 return -1;
 158         if (val > SIZE_MAX)
 159                 return error("unrepresentable length in delta: %"PRIuMAX"", val);
 160         *result = val;
 161         return 0;
 162 }
 163
 164 static int copyfrom_target(struct window *ctx, const char **instructions,
 165                            size_t nbytes, const char *instructions_end)
 166 {
 167         size_t offset;
 168         if (parse_int(instructions, &offset, instructions_end))
 169                 return -1;
 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++]);
 174         return 0;
 175 }
 176
 177 static int copyfrom_data(struct window *ctx, size_t *data_pos, size_t nbytes)
 178 {
 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);
 184         *data_pos += nbytes;
 185         return 0;
 186 }
 187
 188 static int parse_first_operand(const char **buf, size_t *out, const char *end)
 189 {
 190         size_t result = (unsigned char) *(*buf)++ & OPERAND_MASK;
 191         if (result) {   /* immediate operand */
 192                 *out = result;
 193                 return 0;
 194         }
 195         return parse_int(buf, out, end);
 196 }
 197
 198 static int execute_one_instruction(struct window *ctx,
 199                                 const char **instructions, size_t *data_pos)
 200 {
 201         unsigned int instruction;
 202         const char *insns_end = ctx->instructions.buf + ctx->instructions.len;
 203         size_t nbytes;
 204         assert(ctx);
 205         assert(instructions && *instructions);
 206         assert(data_pos);
 207
 208         instruction = (unsigned char) **instructions;
 209         if (parse_first_operand(instructions, &nbytes, insns_end))
 210                 return -1;
 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);
 216         default:
 217                 return error("Unknown instruction %x", instruction);
 218         }
 219 }
 220
 221 static int apply_window_in_core(struct window *ctx)
 222 {
 223         const char *instructions;
 224         size_t data_pos = 0;
 225
 226         /*
 227          * Fill ctx->out.buf using data from the source, target,
 228          * and inline data views.
 229          */
 230         for (instructions = ctx->instructions.buf;
 231              instructions != ctx->instructions.buf + ctx->instructions.len;
 232              )
 233                 if (execute_one_instruction(ctx, &instructions, &data_pos))
 234                         return -1;
 235         if (data_pos != ctx->data.len)
 236                 return error("invalid delta: does not copy all inline data");
 237         return 0;
 238 }
 239
 240 static int apply_one_window(struct line_buffer *delta, off_t *delta_len,
 241                             FILE *out)
 242 {
 243         struct window ctx = WINDOW_INIT;
 244         size_t out_len;
 245         size_t instructions_len;
 246         size_t data_len;
 247         assert(delta_len);
 248
 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))
 255                 goto error_out;
 256         strbuf_grow(&ctx.out, out_len);
 257         if (apply_window_in_core(&ctx))
 258                 goto error_out;
 259         if (ctx.out.len != out_len) {
 260                 error("invalid delta: incorrect postimage length");
 261                 goto error_out;
 262         }
 263         if (write_strbuf(&ctx.out, out))
 264                 goto error_out;
 265         window_release(&ctx);
 266         return 0;
 267 error_out:
 268         window_release(&ctx);
 269         return -1;
 270 }
 271
 272 int svndiff0_apply(struct line_buffer *delta, off_t delta_len,
 273                         struct sliding_view *preimage, FILE *postimage)
 274 {
 275         assert(delta && preimage && postimage);
 276
 277         if (read_magic(delta, &delta_len))
 278                 return -1;
 279         while (delta_len) {     /* For each window: */
 280                 off_t pre_off;
 281                 size_t pre_len;
 282
 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))
 287                         return -1;
 288         }
 289         return 0;
 290 }