lib/delta.c

   1 /*
   2  * Copyright (c) 2018 Stefan Sperling <stsp@openbsd.org>
   3  *
   4  * Permission to use, copy, modify, and distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15  */
  16
  17 #include <sys/queue.h>
  18
  19 #include <stdio.h>
  20 #include <stdlib.h>
  21 #include <stdint.h>
  22 #include <string.h>
  23 #include <limits.h>
  24 #include <zlib.h>
  25 #include <time.h>
  26 #include <zlib.h>
  27
  28 #include "got_error.h"
  29 #include "got_repository.h"
  30 #include "got_object.h"
  31 #include "got_path.h"
  32
  33 #include "got_lib_delta.h"
  34 #include "got_lib_inflate.h"
  35 #include "got_lib_object.h"
  36
  37 #ifndef MIN
  38 #define MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
  39 #endif
  40
  41 struct got_delta *
  42 got_delta_open(off_t offset, size_t tslen, int type, size_t size,
  43     off_t data_offset)
  44 {
  45         struct got_delta *delta;
  46
  47         delta = malloc(sizeof(*delta));
  48         if (delta == NULL)
  49                 return NULL;
  50
  51         delta->type = type;
  52         delta->offset = offset;
  53         delta->tslen = tslen;
  54         delta->size = size;
  55         delta->data_offset = data_offset;
  56         return delta;
  57 }
  58
  59 const struct got_error *
  60 got_delta_chain_get_base_type(int *type, struct got_delta_chain *deltas)
  61 {
  62         struct got_delta *delta;
  63
  64         /* The first delta in the chain should represent the base object. */
  65         delta = STAILQ_FIRST(&deltas->entries);
  66         if (delta->type == GOT_OBJ_TYPE_COMMIT ||
  67             delta->type == GOT_OBJ_TYPE_TREE ||
  68             delta->type == GOT_OBJ_TYPE_BLOB ||
  69             delta->type == GOT_OBJ_TYPE_TAG) {
  70                 *type = delta->type;
  71                 return NULL;
  72         }
  73
  74         return got_error(GOT_ERR_BAD_DELTA_CHAIN);
  75 }
  76
  77 /* Fetch another (required) byte from the delta stream. */
  78 static const struct got_error *
  79 next_delta_byte(const uint8_t **p, size_t *remain)
  80 {
  81         if (--(*remain) == 0)
  82                 return got_error_msg(GOT_ERR_BAD_DELTA,
  83                     "delta data truncated");
  84         (*p)++;
  85         return NULL;
  86 }
  87
  88 static const struct got_error *
  89 parse_size(uint64_t *size, const uint8_t **p, size_t *remain)
  90 {
  91         const struct got_error *err = NULL;
  92         int i = 0;
  93
  94         *size = 0;
  95         do {
  96                 /* We do not support size values which don't fit in 64 bit. */
  97                 if (i > 9)
  98                         return got_error(GOT_ERR_NO_SPACE);
  99
 100                 if (i == 0)
 101                         *size = ((**p) & GOT_DELTA_SIZE_VAL_MASK);
 102                 else {
 103                         size_t shift = GOT_DELTA_SIZE_SHIFT * i;
 104                         *size |= (((**p) & GOT_DELTA_SIZE_VAL_MASK) << shift);
 105                 }
 106
 107                 if (((**p) & GOT_DELTA_SIZE_MORE) == 0)
 108                         break;
 109                 i++;
 110                 err = next_delta_byte(p, remain);
 111         } while (err == NULL);
 112
 113         return err;
 114 }
 115
 116 static const struct got_error *
 117 parse_opcode(off_t *offset, size_t *len, const uint8_t **p, size_t *remain)
 118 {
 119         const struct got_error *err = NULL;
 120         off_t o = 0;
 121         size_t l = 0;
 122         uint8_t opcode = **p;
 123
 124         if (opcode & GOT_DELTA_COPY_OFF1) {
 125                 err = next_delta_byte(p, remain);
 126                 if (err)
 127                         return err;
 128                 o = (off_t)(**p);
 129         }
 130         if (opcode & GOT_DELTA_COPY_OFF2) {
 131                 err = next_delta_byte(p, remain);
 132                 if (err)
 133                         return err;
 134                 o |= ((off_t)(**p)) << 8;
 135         }
 136         if (opcode & GOT_DELTA_COPY_OFF3) {
 137                 err = next_delta_byte(p, remain);
 138                 if (err)
 139                         return err;
 140                 o |= ((off_t)(**p)) << 16;
 141         }
 142         if (opcode & GOT_DELTA_COPY_OFF4) {
 143                 err = next_delta_byte(p, remain);
 144                 if (err)
 145                         return err;
 146                 o |= ((off_t)(**p)) << 24;
 147         }
 148
 149         if (opcode & GOT_DELTA_COPY_LEN1) {
 150                 err = next_delta_byte(p, remain);
 151                 if (err)
 152                         return err;
 153                 l = (off_t)(**p);
 154         }
 155         if (opcode & GOT_DELTA_COPY_LEN2) {
 156                 err = next_delta_byte(p, remain);
 157                 if (err)
 158                         return err;
 159                 l |= ((off_t)(**p)) << 8;
 160         }
 161         if (opcode & GOT_DELTA_COPY_LEN3) {
 162                 err = next_delta_byte(p, remain);
 163                 if (err)
 164                         return err;
 165                 l |= ((off_t)(**p)) << 16;
 166         }
 167
 168         if (o == 0)
 169                 o = GOT_DELTA_COPY_DEFAULT_OFF;
 170         if (l == 0)
 171                 l = GOT_DELTA_COPY_DEFAULT_LEN;
 172
 173         *offset = o;
 174         *len = l;
 175         return NULL;
 176 }
 177
 178 static const struct got_error *
 179 copy_from_base(FILE *base_file, off_t offset, size_t size, FILE *outfile)
 180 {
 181         if (fseeko(base_file, offset, SEEK_SET) != 0)
 182                 return got_error_from_errno("fseeko");
 183
 184         while (size > 0) {
 185                 uint8_t data[2048];
 186                 size_t len = MIN(size, sizeof(data));
 187                 size_t n;
 188
 189                 n = fread(data, len, 1, base_file);
 190                 if (n != 1)
 191                         return got_ferror(base_file, GOT_ERR_IO);
 192
 193                 n = fwrite(data, len, 1, outfile);
 194                 if (n != 1)
 195                         return got_ferror(outfile, GOT_ERR_IO);
 196
 197                 size -= len;
 198         }
 199
 200         return NULL;
 201 }
 202
 203 static const struct got_error *
 204 copy_from_delta(const uint8_t **p, size_t *remain, size_t len, FILE *outfile)
 205 {
 206         size_t n;
 207
 208         if (*remain < len)
 209                 return got_error_msg(GOT_ERR_BAD_DELTA,
 210                     "copy from beyond end of delta data");
 211
 212         n = fwrite(*p, len, 1, outfile);
 213         if (n != 1)
 214                 return got_ferror(outfile, GOT_ERR_IO);
 215
 216         *p += len;
 217         *remain -= len;
 218         return NULL;
 219 }
 220
 221 static const struct got_error *
 222 parse_delta_sizes(uint64_t *base_size, uint64_t *result_size,
 223     const uint8_t **p, size_t *remain)
 224 {
 225         const struct got_error *err;
 226
 227         /* Read the two size fields at the beginning of the stream. */
 228         err = parse_size(base_size, p, remain);
 229         if (err)
 230                 return err;
 231         err = next_delta_byte(p, remain);
 232         if (err)
 233                 return err;
 234         err = parse_size(result_size, p, remain);
 235         if (err)
 236                 return err;
 237
 238         return NULL;
 239 }
 240
 241 const struct got_error *
 242 got_delta_get_sizes(uint64_t *base_size, uint64_t *result_size,
 243     const uint8_t *delta_buf, size_t delta_len)
 244 {
 245         size_t remain;
 246         const uint8_t *p;
 247
 248         if (delta_len < GOT_DELTA_STREAM_LENGTH_MIN)
 249                 return got_error_msg(GOT_ERR_BAD_DELTA, "delta too small");
 250
 251         p = delta_buf;
 252         remain = delta_len;
 253         return parse_delta_sizes(base_size, result_size, &p, &remain);
 254 }
 255
 256 const struct got_error *
 257 got_delta_apply_in_mem(uint8_t *base_buf, size_t base_bufsz,
 258     const uint8_t *delta_buf, size_t delta_len, uint8_t *outbuf,
 259     size_t *outsize, size_t maxoutsize)
 260 {
 261         const struct got_error *err = NULL;
 262         uint64_t base_size, result_size;
 263         size_t remain;
 264         const uint8_t *p;
 265
 266         *outsize= 0;
 267
 268         if (delta_len < GOT_DELTA_STREAM_LENGTH_MIN)
 269                 return got_error_msg(GOT_ERR_BAD_DELTA, "delta too small");
 270
 271         p = delta_buf;
 272         remain = delta_len;
 273         err = parse_delta_sizes(&base_size, &result_size, &p, &remain);
 274         if (err)
 275                 return err;
 276
 277         /* Decode and execute copy instructions from the delta stream. */
 278         err = next_delta_byte(&p, &remain);
 279         while (err == NULL && remain > 0) {
 280                 if (*p & GOT_DELTA_BASE_COPY) {
 281                         off_t offset = 0;
 282                         size_t len = 0;
 283                         err = parse_opcode(&offset, &len, &p, &remain);
 284                         if (err)
 285                                 break;
 286                         if (SIZE_MAX - offset < len || offset + len < 0 ||
 287                             base_bufsz < offset + len ||
 288                             *outsize + len > maxoutsize)
 289                                 return got_error_msg(GOT_ERR_BAD_DELTA,
 290                                     "bad delta copy length");
 291                         memcpy(outbuf + *outsize, base_buf + offset, len);
 292                         if (err == NULL) {
 293                                 *outsize += len;
 294                                 if (remain > 0) {
 295                                         p++;
 296                                         remain--;
 297                                 }
 298                         }
 299                 } else {
 300                         size_t len = (size_t)*p;
 301                         if (len == 0) {
 302                                 err = got_error_msg(GOT_ERR_BAD_DELTA,
 303                                     "zero length delta");
 304                                 break;
 305                         }
 306                         err = next_delta_byte(&p, &remain);
 307                         if (err)
 308                                 break;
 309                         if (remain < len || SIZE_MAX - *outsize < len ||
 310                             *outsize + len > maxoutsize)
 311                                 return got_error_msg(GOT_ERR_BAD_DELTA,
 312                                     "bad delta copy length");
 313                         memcpy(outbuf + *outsize, p, len);
 314                         p += len;
 315                         remain -= len;
 316                         *outsize += len;
 317                 }
 318         }
 319
 320         if (*outsize != result_size)
 321                 err = got_error_msg(GOT_ERR_BAD_DELTA,
 322                     "delta application result size mismatch");
 323         return err;
 324 }
 325
 326 const struct got_error *
 327 got_delta_apply(FILE *base_file, const uint8_t *delta_buf,
 328     size_t delta_len, FILE *outfile, size_t *outsize)
 329 {
 330         const struct got_error *err = NULL;
 331         uint64_t base_size, result_size;
 332         size_t remain = 0;
 333         const uint8_t *p;
 334         FILE *memstream = NULL;
 335         char *memstream_buf = NULL;
 336         size_t memstream_size = 0;
 337
 338         *outsize = 0;
 339
 340         if (delta_len < GOT_DELTA_STREAM_LENGTH_MIN)
 341                 return got_error_msg(GOT_ERR_BAD_DELTA, "delta too small");
 342
 343         p = delta_buf;
 344         remain = delta_len;
 345         err = parse_delta_sizes(&base_size, &result_size, &p, &remain);
 346         if (err)
 347                 return err;
 348
 349         if (result_size < GOT_DELTA_RESULT_SIZE_CACHED_MAX)
 350                 memstream = open_memstream(&memstream_buf, &memstream_size);
 351
 352         /* Decode and execute copy instructions from the delta stream. */
 353         err = next_delta_byte(&p, &remain);
 354         while (err == NULL && remain > 0) {
 355                 if (*p & GOT_DELTA_BASE_COPY) {
 356                         off_t offset = 0;
 357                         size_t len = 0;
 358                         err = parse_opcode(&offset, &len, &p, &remain);
 359                         if (err)
 360                                 break;
 361                         err = copy_from_base(base_file, offset, len,
 362                             memstream ? memstream : outfile);
 363                         if (err == NULL) {
 364                                 *outsize += len;
 365                                 if (remain > 0) {
 366                                         p++;
 367                                         remain--;
 368                                 }
 369                         }
 370                 } else {
 371                         size_t len = (size_t)*p;
 372                         if (len == 0) {
 373                                 err = got_error_msg(GOT_ERR_BAD_DELTA,
 374                                     "zero length delta");
 375                                 break;
 376                         }
 377                         err = next_delta_byte(&p, &remain);
 378                         if (err)
 379                                 break;
 380                         err = copy_from_delta(&p, &remain, len,
 381                             memstream ? memstream : outfile);
 382                         if (err == NULL)
 383                                 *outsize += len;
 384                 }
 385         }
 386
 387         if (*outsize != result_size)
 388                 err = got_error_msg(GOT_ERR_BAD_DELTA,
 389                     "delta application result size mismatch");
 390
 391         if (memstream != NULL) {
 392                 if (fclose(memstream) == EOF)
 393                         err = got_error_from_errno("fclose");
 394                 if (err == NULL) {
 395                         size_t n;
 396                         n = fwrite(memstream_buf, 1, memstream_size, outfile);
 397                         if (n != memstream_size)
 398                                 err = got_ferror(outfile, GOT_ERR_IO);
 399                 }
 400                 free(memstream_buf);
 401         }
 402         if (err == NULL)
 403                 rewind(outfile);
 404         return err;
 405 }