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