vcs-svn/svndiff.c

   1 /*
   2  * Licensed under a two-clause BSD-style license.
   3  * See LICENSE for details.
   4  */
   5
   6 #include "cache.h"
   7 #if 0
   8 #include "git-compat-util.h"
   9 #endif
  10 #include "line_buffer.h"
  11
  12 /*
  13  * svndiff0 applier
  14  *
  15  * See http://svn.apache.org/repos/asf/subversion/trunks/notes/svndiff.
  16  *
  17  * svndiff0 ::= 'SVN\0' window window*;
  18  * window ::= int int int int int instructions inline_data;
  19  * instructions ::= instruction*;
  20  * instruction ::= view_selector int int
  21  *   | copyfrom_data int
  22  *   | packed_view_selector int
  23  *   | packed_copyfrom_data
  24  *   ;
  25  * view_selector ::= copyfrom_source
  26  *   | copyfrom_target
  27  *   ;
  28  * copyfrom_source ::= # binary 00 000000;
  29  * copyfrom_target ::= # binary 01 000000;
  30  * copyfrom_data ::= # binary 10 000000;
  31  * packed_view_selector ::= # view_selector OR-ed with 6 bit value;
  32  * packed_copyfrom_data ::= # copyfrom_data OR-ed with 6 bit value;
  33  * int ::= highdigit* lowdigit;
  34  * highdigit ::= # binary 10000000 OR-ed with 7 bit value;
  35  * lowdigit ::= # 7 bit value;
  36  */
  37
  38 #define SVNDIFF_MAGIC "SVN\0"
  39
  40 #define INSN_MASK       0xc0
  41 #define INSN_COPYFROM_SOURCE    0000
  42 #define INSN_COPYFROM_TARGET    0x40
  43 #define INSN_COPYFROM_DATA      0x80
  44 #define OPERAND_MASK    0x3f
  45
  46 #define VLI_CONTINUE    0x80
  47 #define VLI_DIGIT_MASK  0x7f
  48 #define VLI_BITS_PER_DIGIT 7
  49
  50 struct view {
  51         FILE *file;
  52         char *buf;
  53         size_t off;
  54         size_t len;
  55 };
  56
  57 struct window {
  58         char *out;
  59         size_t out_off;
  60         size_t out_len;
  61
  62         const char *preimage;
  63         size_t preimage_off;
  64         size_t preimage_len;
  65         const char *instructions;
  66         size_t instructions_len;
  67         const char *data;
  68         size_t data_len;
  69 };
  70
  71 static size_t fskip(FILE *file, size_t nbytes)
  72 {
  73         static char buf[4096];
  74         size_t done = 0;
  75
  76         /*
  77          * Try to throw away nbytes bytes.
  78          */
  79         while (done < nbytes) {
  80                 size_t n = nbytes - done;
  81                 size_t in;
  82
  83                 if (n > sizeof(buf))
  84                         n = sizeof(buf);
  85                 in = fread(buf, 1, n, file);
  86                 done += in;
  87                 if (in != n)
  88                         break;
  89         }
  90         return done;
  91 }
  92
  93 static int move_window(struct view *view, size_t newoff, size_t newlen)
  94 {
  95         size_t oldoff, oldlen, len;
  96         char *oldbuf, *buf;
  97
  98         if (newoff > SIZE_MAX - newlen)
  99                 return error("Source file is too big: "
 100                         "%"PRIu64" + %"PRIu64" > SIZE_MAX",
 101                         (uint64_t) newoff, (uint64_t) newlen);
 102         assert(view && view->file);
 103
 104         oldoff = view->off;
 105         oldlen = view->len;
 106         oldbuf = view->buf;
 107
 108         assert(oldoff <= SIZE_MAX - oldlen);
 109         assert(!oldlen || oldbuf);
 110         if (newoff < oldoff || newoff + newlen < oldoff + oldlen)
 111                 return error("Corrupt delta? Window slides left.");
 112
 113         view->off = newoff;
 114         view->len = newlen;
 115         view->buf = buf = malloc(newlen);
 116         if (newlen && !buf)
 117                 return error("Address space exhausted; "
 118                                 "no room for source window");
 119         if (newoff < oldoff + oldlen) {
 120                 const size_t overlap = oldoff + oldlen - newoff;
 121                 buf = mempcpy(buf, oldbuf + oldlen - overlap, overlap);
 122                 newlen -= overlap;
 123         }
 124         if (oldoff + oldlen < newoff) {
 125                 const size_t gap = newoff - oldoff - oldlen;
 126                 if (fskip(view->file, gap) != gap)
 127                         return error("error seeking in source: %s",
 128                                                         strerror(errno));
 129         }
 130         len = fread(buf, 1, newlen, view->file);
 131         if (len == newlen)
 132                 return 0;
 133         if (feof(view->file)) {
 134                 warning("Overlarge window specified; adjusting.");
 135                 view->len -= (newlen - len);
 136                 return 0;
 137         }
 138         return error("error reading source: %s", strerror(errno));
 139 }
 140
 141 static int buf_parse_int(size_t *result, const char **buf, size_t *len)
 142 {
 143         const char *p = *buf;
 144         size_t bufsz = *len;
 145         size_t rv = 0;
 146         while (bufsz) {
 147                 int ch = (unsigned char) *p++;
 148                 bufsz--;
 149                 rv <<= VLI_BITS_PER_DIGIT;
 150                 rv += ch & VLI_DIGIT_MASK;
 151                 if (!(ch & VLI_CONTINUE)) {
 152                         *result = rv;
 153                         *buf = p;
 154                         *len = bufsz;
 155                         return 0;
 156                 }
 157         }
 158         return error("Corrupt delta? Argument with leading digits "
 159                         "%"PRIu64" left unterminated.", (uint64_t) rv);
 160 }
 161
 162 static int parse_int(size_t *result, size_t *len)
 163 {
 164         size_t bufsz = *len;
 165         size_t rv = 0;
 166         while (bufsz) {
 167                 int ch = buffer_read_char();
 168                 if (ch == EOF)
 169                         break;
 170                 bufsz--;
 171                 rv <<= VLI_BITS_PER_DIGIT;
 172                 rv += (ch & VLI_DIGIT_MASK);
 173                 if (!(ch & VLI_CONTINUE)) {
 174                         *result = rv;
 175                         *len = bufsz;
 176                         return 0;
 177                 }
 178         }
 179         return error("Corrupt delta? Integer with leading digits "
 180                         "%"PRIu64" left unterminated.", (uint64_t) rv);
 181 }
 182
 183 static int copyfrom_source(char **out_pos, struct window *ctx, size_t nbytes)
 184 {
 185         char *p = *out_pos;
 186         size_t offset;
 187         if (buf_parse_int(&offset, &ctx->instructions,
 188                                         &ctx->instructions_len))
 189                 return -1;
 190         if (offset > SIZE_MAX - nbytes)
 191                 return error("Source data is too long: "
 192                                 "%"PRIu64" + %"PRIu64" > SIZE_MAX",
 193                                 (uint64_t) offset, (uint64_t) nbytes);
 194         if (offset < ctx->preimage_off)
 195                 return error("Corrupt delta? Attempts to write source "
 196                                 "data that has been forgotten already.");
 197         if (ctx->preimage_len < nbytes)
 198                 return error("Corrupt delta? Attempts to write source "
 199                                 "data that has not been read yet.");
 200         if (p + nbytes > ctx->out + ctx->out_len)
 201                 return error("Corrupt delta? Attempts to write "
 202                                 "source data without making room for it.");
 203         p = mempcpy(p, ctx->preimage - ctx->preimage_off + offset, nbytes);
 204         *out_pos = p;
 205         return 0;
 206 }
 207
 208 static int copyfrom_target(char **out_pos, struct window *ctx, size_t nbytes)
 209 {
 210         char *p = *out_pos;
 211         size_t offset;
 212         if (buf_parse_int(&offset, &ctx->instructions,
 213                                         &ctx->instructions_len))
 214                 return -1;
 215         if (offset > SIZE_MAX - nbytes)
 216                 return error("Output data is too long: "
 217                                 "%"PRIu64" + %"PRIu64" > SIZE_MAX",
 218                                 (uint64_t) offset, (uint64_t) nbytes);
 219         if (offset < ctx->out_off)
 220                 return error("Corrupt delta? Attempts to copy target "
 221                                 "data that has been written and forgotten.");
 222         if (p <= ctx->out - ctx->out_off + offset)
 223                 return error("Corrupt delta? Attempts to copy data "
 224                                 "that has not been written yet.");
 225         if (ctx->out_len < nbytes)
 226                 return error("Corrupt delta? Attempts to copy target "
 227                                 "data that has not even been allocated.");
 228         if (p + nbytes > ctx->out + ctx->out_len)
 229                 return error("Corrupt delta? Attempts to copy target "
 230                                 "data without making room for it.");
 231         while (nbytes) {
 232                 *p++ = (ctx->out - ctx->out_off)[offset++];
 233                 nbytes--;
 234         }
 235         *out_pos = p;
 236         return 0;
 237 }
 238
 239 static int copyfrom_data(char **out_pos, struct window *ctx,
 240                                 size_t *data_pos, size_t nbytes)
 241 {
 242         char *p = *out_pos;
 243         size_t offset = *data_pos;
 244         if (offset > SIZE_MAX - nbytes)
 245                 return error("Inline data is too long: "
 246                                 "%"PRIu64" + %"PRIu64" > SIZE_MAX",
 247                                 (uint64_t) offset, (uint64_t) nbytes);
 248         if (ctx->data_len < offset + nbytes)
 249                 return error("Corrupt delta? Attempts to read inline "
 250                                 "data where none exists.");
 251         if (p + nbytes > ctx->out + ctx->out_len)
 252                 return error("Corrupt delta? Attempts to write inline "
 253                                 "data without making room for it.");
 254         *data_pos = offset + nbytes;
 255         p = mempcpy(p, ctx->data + offset, nbytes);
 256         *out_pos = p;
 257         return 0;
 258 }
 259
 260 static int apply_one_instruction(struct window *ctx,
 261                                 char **out, size_t *data_pos)
 262 {
 263         unsigned char instruction;
 264         size_t nbytes;
 265
 266         assert(ctx->instructions_len);
 267         assert(ctx->instructions);
 268
 269         instruction = (unsigned char) *ctx->instructions;
 270         ctx->instructions++;
 271         ctx->instructions_len--;
 272         nbytes = instruction & OPERAND_MASK;
 273         if (!nbytes && buf_parse_int(&nbytes, &ctx->instructions,
 274                                                 &ctx->instructions_len))
 275                 return -1;
 276         switch (instruction & INSN_MASK) {
 277         case INSN_COPYFROM_SOURCE:
 278                 return copyfrom_source(out, ctx, nbytes);
 279         case INSN_COPYFROM_TARGET:
 280                 return copyfrom_target(out, ctx, nbytes);
 281         case INSN_COPYFROM_DATA:
 282                 return copyfrom_data(out, ctx, data_pos, nbytes);
 283         default:
 284                 return error("Delta contains invalid instruction %x",
 285                                         (unsigned int) instruction);
 286         }
 287 }
 288
 289 static int do_instructions(struct window *ctx)
 290 {
 291         char *p = ctx->out;
 292         size_t data_offset = 0;
 293
 294         /*
 295          * Advance p while copying data from the source, target,
 296          * and inline data views.
 297          */
 298         while (ctx->instructions_len)
 299                 if (apply_one_instruction(ctx, &p, &data_offset))
 300                         return -1;
 301         return 0;
 302 }
 303
 304 static int apply_within(const struct view *preimage, size_t *out_offset,
 305                         FILE *outf, size_t *len_remaining,
 306                         size_t *out_remaining)
 307 {
 308         struct window ctx;
 309
 310         ctx.preimage_len = preimage->len;
 311         ctx.preimage_off = preimage->off;
 312         ctx.preimage = preimage->buf;
 313
 314         assert(out_offset);
 315         assert(len_remaining);
 316
 317         /*
 318          * Window header:
 319          *  - "source view" offset and length (already handled);
 320          *  - "target view" length;
 321          *  - "instructions" length;
 322          *  - inline data length.
 323          */
 324
 325         if (parse_int(&ctx.out_len, len_remaining))
 326                 return -1;
 327         ctx.out_off = *out_offset;
 328
 329         if (parse_int(&ctx.instructions_len, len_remaining))
 330                 return -1;
 331         if (parse_int(&ctx.data_len, len_remaining))
 332                 return -1;
 333
 334         if (ctx.instructions_len > SIZE_MAX - ctx.data_len)
 335                 return error("Instructions too long: "
 336                                         "%"PRIu64" + %"PRIu64" > SIZE_MAX",
 337                                         (uint64_t) ctx.instructions_len,
 338                                         (uint64_t) ctx.data_len);
 339         if (ctx.instructions_len > *len_remaining)
 340                 warning("Delta instructions appear to be tructated "
 341                                 "(%"PRIu64" bytes out of %"PRIu64")",
 342                                 (uint64_t) *len_remaining,
 343                                 (uint64_t) ctx.instructions_len);
 344         if (ctx.instructions_len + ctx.data_len > *len_remaining)
 345                 warning("Delta appears to be truncated");
 346
 347         ctx.out = malloc(ctx.out_len);
 348         if (ctx.out_len && !ctx.out)
 349                 return error("Address space exhausted; "
 350                                         "no room for target window");
 351         ctx.out_off = *out_offset;
 352         ctx.instructions = buffer_read_string(
 353                                         ctx.instructions_len + ctx.data_len);
 354         *len_remaining -= ctx.instructions_len + ctx.data_len;
 355         ctx.data = ctx.instructions + ctx.instructions_len;
 356
 357         if (do_instructions(&ctx)) {
 358                 free(ctx.out);
 359                 return -1;
 360         }
 361         if (ctx.out_len > *out_remaining)
 362                 ctx.out_len = *out_remaining;
 363         if (fwrite(ctx.out, 1, ctx.out_len, outf) == ctx.out_len) {
 364                 /* Success. */
 365                 free(ctx.out);
 366                 *out_offset = ctx.out_off;
 367                 *out_remaining -= ctx.out_len;
 368                 return 0;
 369         }
 370         error("Error writing patched file: %s", strerror(errno));
 371         free(ctx.out);
 372         return -1;
 373
 374 }
 375
 376 /*
 377  * Magic bytes ("SVN\0")
 378  */
 379 static int parse_magic(size_t *len)
 380 {
 381         const char *buf;
 382         const size_t magic_len = 4;
 383
 384         if (*len < magic_len)
 385                 return error("Invalid diff stream: no file type header");
 386         buf = buffer_read_string(magic_len);
 387         if (memcmp(buf, SVNDIFF_MAGIC, magic_len))
 388                 return error("Unrecognized file type %s", buf);
 389         *len -= magic_len;
 390         return 0;
 391 }
 392
 393 /*
 394  * Apply a delta from the file named by delta, truncated to len bytes.
 395  */
 396 int svndiff0_apply(const char *delta, size_t len, size_t out, size_t in,
 397                                 FILE *preimage, FILE *postimage)
 398 {
 399         struct view preimage_view = {preimage, NULL, 0, 0};
 400         size_t out_offset = 0;
 401
 402         assert(delta && preimage && postimage);
 403         if (buffer_init(delta))
 404                 return error("cannot open %s: %s\n", delta, strerror(errno));
 405         if (parse_magic(&len))
 406                 return -1;
 407         while (len > 0 && out > 0) {
 408                 /* New window. */
 409                 size_t pre_off, pre_len;
 410                 int ch;
 411                 if (parse_int(&pre_off, &len))
 412                         return -1;
 413                 if (parse_int(&pre_len, &len))
 414                         return -1;
 415                 if (pre_len > in)
 416                         pre_len = in;
 417                 if (move_window(&preimage_view, pre_off, pre_len))
 418                         return -1;
 419                 in -= pre_len;
 420                 if (apply_within(&preimage_view, &out_offset, postimage, &len, &out))
 421                         return -1;
 422                 if (ferror(stdin) || feof(stdin))
 423                         break;
 424         }
 425         return buffer_deinit();
 426 }