Andrew's git - gitweb.git/blob

   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
  39struct 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
  47static void window_release(struct window *ctx)
  48{
  49        strbuf_release(&ctx->out);
  50        strbuf_release(&ctx->instructions);
  51        strbuf_release(&ctx->data);
  52}
  53
  54static 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
  61static 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
  68static 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
  79static 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
  96static 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
 117static 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
 136static 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
 147static 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
 158static 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
 169static 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
 179static 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
 197static 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        if (data_pos != ctx->data.len)
 212                return error("invalid delta: does not copy all inline data");
 213        return 0;
 214}
 215
 216static int apply_one_window(struct line_buffer *delta, off_t *delta_len,
 217                            FILE *out)
 218{
 219        struct window ctx = WINDOW_INIT;
 220        size_t out_len;
 221        size_t instructions_len;
 222        size_t data_len;
 223        assert(delta_len);
 224
 225        /* "source view" offset and length already handled; */
 226        if (read_length(delta, &out_len, delta_len) ||
 227            read_length(delta, &instructions_len, delta_len) ||
 228            read_length(delta, &data_len, delta_len) ||
 229            read_chunk(delta, delta_len, &ctx.instructions, instructions_len) ||
 230            read_chunk(delta, delta_len, &ctx.data, data_len))
 231                goto error_out;
 232        strbuf_grow(&ctx.out, out_len);
 233        if (apply_window_in_core(&ctx))
 234                goto error_out;
 235        if (ctx.out.len != out_len) {
 236                error("invalid delta: incorrect postimage length");
 237                goto error_out;
 238        }
 239        if (write_strbuf(&ctx.out, out))
 240                goto error_out;
 241        window_release(&ctx);
 242        return 0;
 243error_out:
 244        window_release(&ctx);
 245        return -1;
 246}
 247
 248int svndiff0_apply(struct line_buffer *delta, off_t delta_len,
 249                        struct sliding_view *preimage, FILE *postimage)
 250{
 251        assert(delta && preimage && postimage);
 252
 253        if (read_magic(delta, &delta_len))
 254                return -1;
 255        while (delta_len) {     /* For each window: */
 256                off_t pre_off;
 257                size_t pre_len;
 258
 259                if (read_offset(delta, &pre_off, &delta_len) ||
 260                    read_length(delta, &pre_len, &delta_len) ||
 261                    move_window(preimage, pre_off, pre_len) ||
 262                    apply_one_window(delta, &delta_len, postimage))
 263                        return -1;
 264        }
 265        return 0;
 266}