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