lib/deltify.c

   1 /*
   2  * Copyright (c) 2020 Ori Bernstein
   3  * Copyright (c) 2021 Stefan Sperling <stsp@openbsd.org>
   4  *
   5  * Permission to use, copy, modify, and distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  11  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  15  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 #include <sys/types.h>
  19
  20 #include <assert.h>
  21 #include <errno.h>
  22 #include <limits.h>
  23 #include <stdint.h>
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27
  28 #include "got_error.h"
  29
  30 #include "got_lib_deltify.h"
  31 #include "murmurhash2.h"
  32
  33 #ifndef MIN
  34 #define MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
  35 #endif
  36
  37 /*
  38  * The algorihm used here is FastCDC (Fast Content-Defined Chunking)
  39  * https://www.usenix.org/conference/atc16/technical-sessions/presentation/xia
  40  */
  41
  42 static uint32_t geartab[256] = {
  43     0x67ed26b7, 0x32da500c, 0x53d0fee0, 0xce387dc7, 0xcd406d90, 0x2e83a4d4,
  44     0x9fc9a38d, 0xb67259dc, 0xca6b1722, 0x6d2ea08c, 0x235cea2e, 0x3149bb5f,
  45     0x1beda787, 0x2a6b77d5, 0x2f22d9ac, 0x91fc0544, 0xe413acfa, 0x5a30ff7a,
  46     0xad6fdde0, 0x444fd0f5, 0x7ad87864, 0x58c5ff05, 0x8d2ec336, 0x2371f853,
  47     0x550f8572, 0x6aa448dd, 0x7c9ddbcf, 0x95221e14, 0x2a82ec33, 0xcbec5a78,
  48     0xc6795a0d, 0x243995b7, 0x1c909a2f, 0x4fded51c, 0x635d334b, 0x0e2b9999,
  49     0x2702968d, 0x856de1d5, 0x3325d60e, 0xeb6a7502, 0xec2a9844, 0x0905835a,
  50     0xa1820375, 0xa4be5cab, 0x96a6c058, 0x2c2ccd70, 0xba40fce3, 0xd794c46b,
  51     0x8fbae83e, 0xc3aa7899, 0x3d3ff8ed, 0xa0d42b5b, 0x571c0c97, 0xd2811516,
  52     0xf7e7b96c, 0x4fd2fcbd, 0xe2fdec94, 0x282cc436, 0x78e8e95c, 0x80a3b613,
  53     0xcfbee20c, 0xd4a32d1c, 0x2a12ff13, 0x6af82936, 0xe5630258, 0x8efa6a98,
  54     0x294fb2d1, 0xdeb57086, 0x5f0fddb3, 0xeceda7ce, 0x4c87305f, 0x3a6d3307,
  55     0xe22d2942, 0x9d060217, 0x1e42ed02, 0xb6f63b52, 0x4367f39f, 0x055cf262,
  56     0x03a461b2, 0x5ef9e382, 0x386bc03a, 0x2a1e79c7, 0xf1a0058b, 0xd4d2dea9,
  57     0x56baf37d, 0x5daff6cc, 0xf03a951d, 0xaef7de45, 0xa8f4581e, 0x3960b555,
  58     0xffbfff6d, 0xbe702a23, 0x8f5b6d6f, 0x061739fb, 0x98696f47, 0x3fd596d4,
  59     0x151eac6b, 0xa9fcc4f5, 0x69181a12, 0x3ac5a107, 0xb5198fe7, 0x96bcb1da,
  60     0x1b5ddf8e, 0xc757d650, 0x65865c3a, 0x8fc0a41a, 0x87435536, 0x99eda6f2,
  61     0x41874794, 0x29cff4e8, 0xb70efd9a, 0x3103f6e7, 0x84d2453b, 0x15a450bd,
  62     0x74f49af1, 0x60f664b1, 0xa1c86935, 0xfdafbce1, 0xe36353e3, 0x5d9ba739,
  63     0xbc0559ba, 0x708b0054, 0xd41d808c, 0xb2f31723, 0x9027c41f, 0xf136d165,
  64     0xb5374b12, 0x9420a6ac, 0x273958b6, 0xe6c2fad0, 0xebdc1f21, 0xfb33af8b,
  65     0xc71c25cd, 0xe9a2d8e5, 0xbeb38a50, 0xbceb7cc2, 0x4e4e73f0, 0xcd6c251d,
  66     0xde4c032c, 0x4b04ac30, 0x725b8b21, 0x4eb8c33b, 0x20d07b75, 0x0567aa63,
  67     0xb56b2bb7, 0xc1f5fd3a, 0xcafd35ca, 0x470dd4da, 0xfe4f94cd, 0xfb8de424,
  68     0xe8dbcf40, 0xfe50a37a, 0x62db5b5d, 0xf32f4ab6, 0x2c4a8a51, 0x18473dc0,
  69     0xfe0cbb6e, 0xfe399efd, 0xdf34ecc9, 0x6ccd5055, 0x46097073, 0x139135c2,
  70     0x721c76f6, 0x1c6a94b4, 0x6eee014d, 0x8a508e02, 0x3da538f5, 0x280d394f,
  71     0x5248a0c4, 0x3ce94c6c, 0x9a71ad3a, 0x8493dd05, 0xe43f0ab6, 0x18e4ed42,
  72     0x6c5c0e09, 0x42b06ec9, 0x8d330343, 0xa45b6f59, 0x2a573c0c, 0xd7fd3de6,
  73     0xeedeab68, 0x5c84dafc, 0xbbd1b1a8, 0xa3ce1ad1, 0x85b70bed, 0xb6add07f,
  74     0xa531309c, 0x8f8ab852, 0x564de332, 0xeac9ed0c, 0x73da402c, 0x3ec52761,
  75     0x43af2f4d, 0xd6ff45c8, 0x4c367462, 0xd553bd6a, 0x44724855, 0x3b2aa728,
  76     0x56e5eb65, 0xeaf16173, 0x33fa42ff, 0xd714bb5d, 0xfbd0a3b9, 0xaf517134,
  77     0x9416c8cd, 0x534cf94f, 0x548947c2, 0x34193569, 0x32f4389a, 0xfe7028bc,
  78     0xed73b1ed, 0x9db95770, 0x468e3922, 0x0440c3cd, 0x60059a62, 0x33504562,
  79     0x2b229fbd, 0x5174dca5, 0xf7028752, 0xd63c6aa8, 0x31276f38, 0x0646721c,
  80     0xb0191da8, 0xe00e6de0, 0x9eac1a6e, 0x9f7628a5, 0xed6c06ea, 0x0bb8af15,
  81     0xf119fb12, 0x38693c1c, 0x732bc0fe, 0x84953275, 0xb82ec888, 0x33a4f1b3,
  82     0x3099835e, 0x028a8782, 0x5fdd51d7, 0xc6c717b3, 0xb06caf71, 0x17c8c111,
  83     0x61bad754, 0x9fd03061, 0xe09df1af, 0x3bc9eb73, 0x85878413, 0x9889aaf2,
  84     0x3f5a9e46, 0x42c9f01f, 0x9984a4f4, 0xd5de43cc, 0xd294daed, 0xbecba2d2,
  85     0xf1f6e72c, 0x5551128a, 0x83af87e2, 0x6f0342ba,
  86 };
  87
  88 static uint32_t
  89 hashblk(const unsigned char *p, off_t n)
  90 {
  91         return murmurhash2(p, n, 0x1d7c5ac3);
  92 }
  93
  94 static const struct got_error *
  95 addblk(struct got_delta_table *dt, FILE *f, off_t file_offset0, off_t len,
  96     off_t offset, uint64_t h)
  97 {
  98         const struct got_error *err = NULL;
  99         int i;
 100         uint8_t buf[GOT_DELTIFY_MAXCHUNK];
 101         uint8_t buf2[GOT_DELTIFY_MAXCHUNK];
 102         size_t r = 0;
 103
 104         if (len == 0)
 105                 return NULL;
 106
 107         i = h % dt->nalloc;
 108         while (dt->blocks[i].len != 0) {
 109                 /*
 110                  * Avoid adding duplicate blocks.
 111                  * NB: A matching hash is insufficient for detecting equality.
 112                  * The hash can only detect inequality.
 113                  */
 114                 if (len == dt->blocks[i].len && h == dt->blocks[i].hash) {
 115                         if (r == 0) {
 116                                 if (fseeko(f, file_offset0 + offset, SEEK_SET) == -1)
 117                                         return got_error_from_errno("fseeko");
 118                                 r = fread(buf, 1, len, f);
 119                                 if (r != len) {
 120                                         if (!ferror(f))
 121                                                 return NULL;
 122                                         return got_ferror(f, GOT_ERR_IO);
 123                                 }
 124                         }
 125                         if (fseeko(f, file_offset0 + dt->blocks[i].offset,
 126                             SEEK_SET) == -1)
 127                                 return got_error_from_errno("fseeko");
 128                         if (fread(buf2, 1, len, f) != len)
 129                                 return got_ferror(f, GOT_ERR_IO);
 130                         if (memcmp(buf, buf2, len) == 0)
 131                                 return NULL;
 132                 }
 133
 134                 i = (i + 1) % dt->nalloc;
 135         }
 136         assert(dt->blocks[i].len == 0);
 137         dt->blocks[i].len = len;
 138         dt->blocks[i].offset = offset;
 139         dt->blocks[i].hash = h;
 140         dt->nblocks++;
 141         if (dt->nalloc < dt->nblocks + 64) {
 142                 struct got_delta_block *db;
 143                 size_t old_size = dt->nalloc;
 144                 db = dt->blocks;
 145                 dt->blocks = calloc(dt->nalloc + 64,
 146                     sizeof(struct got_delta_block));
 147                 if (dt->blocks == NULL) {
 148                         err = got_error_from_errno("calloc");
 149                         dt->blocks = db;
 150                         return err;
 151                 }
 152                 dt->nalloc += 64;
 153                 /*
 154                  * Recompute all block positions. Hash-based indices of blocks
 155                  * in the array depend on the allocated length of the array.
 156                  */
 157                 dt->nblocks = 0;
 158                 for (i = 0; i < old_size; i++) {
 159                         if (db[i].len == 0)
 160                                 continue;
 161                         err = addblk(dt, f, file_offset0, db[i].len,
 162                             db[i].offset, db[i].hash);
 163                         if (err)
 164                                 break;
 165                 }
 166                 free(db);
 167         }
 168
 169         return err;
 170 }
 171
 172 static const struct got_error *
 173 addblk_mem(struct got_delta_table *dt, uint8_t *data, off_t file_offset0,
 174     off_t len, off_t offset, uint64_t h)
 175 {
 176         const struct got_error *err = NULL;
 177         int i;
 178         uint8_t *block1;
 179         uint8_t *block2;
 180
 181         if (len == 0)
 182                 return NULL;
 183
 184         i = h % dt->nalloc;
 185         while (dt->blocks[i].len != 0) {
 186                 /*
 187                  * Avoid adding duplicate blocks.
 188                  * NB: A matching hash is insufficient for detecting equality.
 189                  * The hash can only detect inequality.
 190                  */
 191                 if (len == dt->blocks[i].len && h == dt->blocks[i].hash) {
 192                         block1 = data + file_offset0 + dt->blocks[i].offset;
 193                         block2 = data + file_offset0 + offset;
 194                         if (memcmp(block1, block2, len) == 0)
 195                                 return NULL;
 196                 }
 197
 198                 i = (i + 1) % dt->nalloc;
 199         }
 200         assert(dt->blocks[i].len == 0);
 201         dt->blocks[i].len = len;
 202         dt->blocks[i].offset = offset;
 203         dt->blocks[i].hash = h;
 204         dt->nblocks++;
 205         if (dt->nalloc < dt->nblocks + 64) {
 206                 struct got_delta_block *db;
 207                 size_t old_size = dt->nalloc;
 208                 db = dt->blocks;
 209                 dt->blocks = calloc(dt->nalloc + 64,
 210                     sizeof(struct got_delta_block));
 211                 if (dt->blocks == NULL) {
 212                         err = got_error_from_errno("calloc");
 213                         dt->blocks = db;
 214                         return err;
 215                 }
 216                 dt->nalloc += 64;
 217                 /*
 218                  * Recompute all block positions. Hash-based indices of blocks
 219                  * in the array depend on the allocated length of the array.
 220                  */
 221                 dt->nblocks = 0;
 222                 for (i = 0; i < old_size; i++) {
 223                         if (db[i].len == 0)
 224                                 continue;
 225                         err = addblk_mem(dt, data, file_offset0, db[i].len,
 226                             db[i].offset, db[i].hash);
 227                         if (err)
 228                                 break;
 229                 }
 230                 free(db);
 231         }
 232
 233         return err;
 234 }
 235
 236 static const struct got_error *
 237 lookupblk(struct got_delta_block **block, struct got_delta_table *dt,
 238     unsigned char *p, off_t len, FILE *basefile, off_t basefile_offset0)
 239 {
 240         int i;
 241         uint32_t h;
 242         uint8_t buf[GOT_DELTIFY_MAXCHUNK];
 243         size_t r;
 244
 245         *block = NULL;
 246
 247         h = hashblk(p, len);
 248         for (i = h % dt->nalloc; dt->blocks[i].len != 0;
 249              i = (i + 1) % dt->nalloc) {
 250                 if (dt->blocks[i].hash != h ||
 251                     dt->blocks[i].len != len)
 252                         continue;
 253                 if (fseeko(basefile, basefile_offset0 + dt->blocks[i].offset,
 254                     SEEK_SET) == -1)
 255                         return got_error_from_errno("fseeko");
 256                 r = fread(buf, 1, len, basefile);
 257                 if (r != len)
 258                         return got_ferror(basefile, GOT_ERR_IO);
 259                 if (memcmp(p, buf, len) == 0) {
 260                         *block = &dt->blocks[i];
 261                         break;
 262                 }
 263         }
 264         return NULL;
 265 }
 266
 267 static const struct got_error *
 268 lookupblk_mem(struct got_delta_block **block, struct got_delta_table *dt,
 269     unsigned char *p, off_t len, uint8_t *basedata, off_t basefile_offset0)
 270 {
 271         int i;
 272         uint32_t h;
 273         uint8_t *b;
 274
 275         *block = NULL;
 276
 277         h = hashblk(p, len);
 278         for (i = h % dt->nalloc; dt->blocks[i].len != 0;
 279              i = (i + 1) % dt->nalloc) {
 280                 if (dt->blocks[i].hash != h ||
 281                     dt->blocks[i].len != len)
 282                         continue;
 283                 b = basedata + basefile_offset0 + dt->blocks[i].offset;
 284                 if (memcmp(p, b, len) == 0) {
 285                         *block = &dt->blocks[i];
 286                         break;
 287                 }
 288         }
 289         return NULL;
 290 }
 291
 292 static const struct got_error *
 293 nextblk(uint8_t *buf, off_t *blocklen, FILE *f)
 294 {
 295         uint32_t gh;
 296         const unsigned char *p;
 297         size_t r;
 298         off_t pos = ftello(f);
 299
 300         *blocklen = 0;
 301
 302         r = fread(buf, 1, GOT_DELTIFY_MAXCHUNK, f);
 303         if (r == 0 && ferror(f))
 304                 return got_ferror(f, GOT_ERR_IO);
 305         if (r < GOT_DELTIFY_MINCHUNK)
 306                 return NULL; /* no more delta-worthy blocks left */
 307
 308         /* Got a deltifiable block. Find the split-point where it ends. */
 309         p = buf + GOT_DELTIFY_MINCHUNK;
 310         gh = 0;
 311         while (p != buf + r) {
 312                 gh = (gh << 1) + geartab[*p++];
 313                 if ((gh & GOT_DELTIFY_SPLITMASK) == 0)
 314                         break;
 315         }
 316
 317         *blocklen = (p - buf);
 318         if (fseeko(f, pos + *blocklen, SEEK_SET) == -1)
 319                 return got_error_from_errno("fseeko");
 320
 321         return NULL;
 322 }
 323
 324 static const struct got_error *
 325 nextblk_mem(off_t *blocklen, uint8_t *data, off_t fileoffset, off_t filesize)
 326 {
 327         uint32_t gh;
 328         const unsigned char *p;
 329
 330         *blocklen = 0;
 331
 332         if (fileoffset >= filesize ||
 333             filesize - fileoffset < GOT_DELTIFY_MINCHUNK)
 334                 return NULL; /* no more delta-worthy blocks left */
 335
 336         /* Got a deltifiable block. Find the split-point where it ends. */
 337         p = data + fileoffset + GOT_DELTIFY_MINCHUNK;
 338         gh = 0;
 339         while (p != data + MIN(fileoffset + GOT_DELTIFY_MAXCHUNK, filesize)) {
 340                 gh = (gh << 1) + geartab[*p++];
 341                 if ((gh & GOT_DELTIFY_SPLITMASK) == 0)
 342                         break;
 343         }
 344
 345         *blocklen = (p - (data + fileoffset));
 346         return NULL;
 347 }
 348
 349 const struct got_error *
 350 got_deltify_init(struct got_delta_table **dt, FILE *f, off_t fileoffset,
 351     off_t filesize)
 352 {
 353         const struct got_error *err = NULL;
 354         uint32_t h;
 355         const off_t offset0 = fileoffset;
 356
 357         *dt = calloc(1, sizeof(**dt));
 358         if (*dt == NULL)
 359                 return got_error_from_errno("calloc");
 360
 361         (*dt)->nblocks = 0;
 362         (*dt)->nalloc = 128;
 363         (*dt)->blocks = calloc((*dt)->nalloc, sizeof(struct got_delta_block));
 364         if ((*dt)->blocks == NULL) {
 365                 err = got_error_from_errno("calloc");
 366                 goto done;
 367         }
 368
 369         if (fseeko(f, fileoffset, SEEK_SET) == -1)
 370                 return got_error_from_errno("fseeko");
 371
 372         while (fileoffset < filesize) {
 373                 uint8_t buf[GOT_DELTIFY_MAXCHUNK];
 374                 off_t blocklen;
 375                 err = nextblk(buf, &blocklen, f);
 376                 if (err)
 377                         goto done;
 378                 if (blocklen == 0)
 379                         break;
 380                 h = hashblk(buf, blocklen);
 381                 err = addblk(*dt, f, offset0, blocklen,
 382                     fileoffset - offset0, h);
 383                 if (err)
 384                         goto done;
 385                 fileoffset += blocklen;
 386                 if (fseeko(f, fileoffset, SEEK_SET) == -1)
 387                         return got_error_from_errno("fseeko");
 388         }
 389 done:
 390         if (err) {
 391                 free((*dt)->blocks);
 392                 free(*dt);
 393                 *dt = NULL;
 394         }
 395
 396         return err;
 397 }
 398
 399 const struct got_error *
 400 got_deltify_init_mem(struct got_delta_table **dt, uint8_t *data,
 401     off_t fileoffset, off_t filesize)
 402 {
 403         const struct got_error *err = NULL;
 404         uint64_t h;
 405         const off_t offset0 = fileoffset;
 406
 407         *dt = calloc(1, sizeof(**dt));
 408         if (*dt == NULL)
 409                 return got_error_from_errno("calloc");
 410
 411         (*dt)->nblocks = 0;
 412         (*dt)->nalloc = 128;
 413         (*dt)->blocks = calloc((*dt)->nalloc, sizeof(struct got_delta_block));
 414         if ((*dt)->blocks == NULL) {
 415                 err = got_error_from_errno("calloc");
 416                 goto done;
 417         }
 418
 419         while (fileoffset < filesize) {
 420                 off_t blocklen;
 421                 err = nextblk_mem(&blocklen, data, fileoffset, filesize);
 422                 if (err)
 423                         goto done;
 424                 if (blocklen == 0)
 425                         break;
 426                 h = hashblk(data + fileoffset, blocklen);
 427                 err = addblk_mem(*dt, data, offset0, blocklen,
 428                     fileoffset - offset0, h);
 429                 if (err)
 430                         goto done;
 431                 fileoffset += blocklen;
 432         }
 433 done:
 434         if (err) {
 435                 free((*dt)->blocks);
 436                 free(*dt);
 437                 *dt = NULL;
 438         }
 439
 440         return err;
 441 }
 442
 443 void
 444 got_deltify_free(struct got_delta_table *dt)
 445 {
 446         if (dt == NULL)
 447                 return;
 448         free(dt->blocks);
 449         free(dt);
 450 }
 451
 452 static const struct got_error *
 453 emitdelta(struct got_delta_instruction **deltas, size_t *nalloc, int *ndeltas,
 454     const size_t alloc_chunk_size, int copy, off_t offset, off_t len)
 455 {
 456         struct got_delta_instruction *d, *p;
 457
 458         if (*nalloc < *ndeltas + alloc_chunk_size) {
 459                 p = reallocarray(*deltas, *nalloc + alloc_chunk_size,
 460                     sizeof(struct got_delta_instruction));
 461                 if (p == NULL)
 462                         return got_error_from_errno("reallocarray");
 463                 *deltas = p;
 464                 *nalloc += alloc_chunk_size;
 465         }
 466         *ndeltas += 1;
 467         d = &(*deltas)[*ndeltas - 1];
 468         d->copy = copy;
 469         d->offset = offset;
 470         d->len = len;
 471         return NULL;
 472 }
 473
 474 static const struct got_error *
 475 stretchblk(FILE *basefile, off_t base_offset0, struct got_delta_block *block,
 476     FILE *f, off_t filesize, off_t *blocklen)
 477 {
 478         uint8_t basebuf[GOT_DELTIFY_MAXCHUNK], buf[GOT_DELTIFY_MAXCHUNK];
 479         size_t base_r, r, i;
 480         int buf_equal = 1;
 481
 482         if (fseeko(basefile, base_offset0 + block->offset + *blocklen,
 483             SEEK_SET) == -1)
 484                 return got_error_from_errno("fseeko");
 485
 486         while (buf_equal && *blocklen < (1 << 24) - 1) {
 487                 base_r = fread(basebuf, 1, sizeof(basebuf), basefile);
 488                 if (base_r == 0) {
 489                         if (ferror(basefile))
 490                                 return got_ferror(basefile, GOT_ERR_IO);
 491                         break;
 492                 }
 493                 r = fread(buf, 1, sizeof(buf), f);
 494                 if (r == 0) {
 495                         if (ferror(f))
 496                                 return got_ferror(f, GOT_ERR_IO);
 497                         break;
 498                 }
 499                 for (i = 0; i < MIN(base_r, r); i++) {
 500                         if (buf[i] != basebuf[i]) {
 501                                 buf_equal = 0;
 502                                 break;
 503                         }
 504                         (*blocklen)++;
 505                 }
 506         }
 507
 508         return NULL;
 509 }
 510
 511 static const struct got_error *
 512 stretchblk_file_mem(uint8_t *basedata, off_t base_offset0, off_t basefile_size,
 513      struct got_delta_block *block, FILE *f, off_t filesize, off_t *blocklen)
 514 {
 515         uint8_t buf[GOT_DELTIFY_MAXCHUNK];
 516         size_t r, i;
 517         int buf_equal = 1;
 518         off_t base_offset = base_offset0 + block->offset + *blocklen;
 519
 520         if (base_offset > basefile_size) {
 521                 return got_error_fmt(GOT_ERR_RANGE,
 522                     "read beyond the size of delta base at offset %llu",
 523                     base_offset);
 524         }
 525
 526         while (buf_equal && *blocklen < (1 << 24) - 1) {
 527                 if (base_offset + *blocklen >= basefile_size)
 528                         break;
 529                 r = fread(buf, 1, sizeof(buf), f);
 530                 if (r == 0) {
 531                         if (ferror(f))
 532                                 return got_ferror(f, GOT_ERR_IO);
 533                         break;
 534                 }
 535                 for (i = 0; i < MIN(basefile_size - base_offset, r); i++) {
 536                         if (buf[i] != *(basedata + base_offset + i)) {
 537                                 buf_equal = 0;
 538                                 break;
 539                         }
 540                         (*blocklen)++;
 541                 }
 542         }
 543
 544         return NULL;
 545 }
 546
 547 static const struct got_error *
 548 stretchblk_mem_file(FILE *basefile, off_t base_offset0,
 549     struct got_delta_block *block, uint8_t *data, off_t fileoffset,
 550     off_t filesize, off_t *blocklen)
 551 {
 552         uint8_t basebuf[GOT_DELTIFY_MAXCHUNK];
 553         size_t base_r, i;
 554         int buf_equal = 1;
 555
 556         if (fileoffset > filesize) {
 557                 return got_error_fmt(GOT_ERR_RANGE,
 558                     "read beyond the size of deltify file at offset %llu",
 559                     fileoffset);
 560         }
 561
 562         if (fseeko(basefile, base_offset0 + block->offset + *blocklen,
 563             SEEK_SET) == -1)
 564                 return got_error_from_errno("fseeko");
 565
 566         while (buf_equal && *blocklen < (1 << 24) - 1) {
 567                 if (fileoffset + *blocklen >= filesize)
 568                         break;
 569                 base_r = fread(basebuf, 1, sizeof(basebuf), basefile);
 570                 if (base_r == 0) {
 571                         if (ferror(basefile))
 572                                 return got_ferror(basefile, GOT_ERR_IO);
 573                         break;
 574                 }
 575                 for (i = 0; i < MIN(base_r, filesize - fileoffset); i++) {
 576                         if (*(data + fileoffset + i) != basebuf[i]) {
 577                                 buf_equal = 0;
 578                                 break;
 579                         }
 580                         (*blocklen)++;
 581                 }
 582         }
 583
 584         return NULL;
 585 }
 586
 587 static const struct got_error *
 588 stretchblk_mem_mem(uint8_t *basedata, off_t base_offset0, off_t basefile_size,
 589     struct got_delta_block *block, uint8_t *data, off_t fileoffset,
 590     off_t filesize, off_t *blocklen)
 591 {
 592         off_t i, maxlen;
 593         off_t base_offset = base_offset0 + block->offset + *blocklen;
 594         uint8_t *p, *q;
 595
 596         if (base_offset > basefile_size) {
 597                 return got_error_fmt(GOT_ERR_RANGE,
 598                     "read beyond the size of delta base at offset %llu",
 599                     base_offset);
 600         }
 601
 602         if (fileoffset > filesize) {
 603                 return got_error_fmt(GOT_ERR_RANGE,
 604                     "read beyond the size of deltify file at offset %llu",
 605                     fileoffset);
 606         }
 607
 608         p = data + fileoffset;
 609         q = basedata + base_offset;
 610         maxlen = MIN(basefile_size - base_offset, filesize - fileoffset);
 611         for (i = 0; i < maxlen && *blocklen < (1 << 24) - 1; i++) {
 612                 if (p[i] != q[i])
 613                         break;
 614                 (*blocklen)++;
 615         }
 616
 617         return NULL;
 618 }
 619
 620 const struct got_error *
 621 got_deltify(struct got_delta_instruction **deltas, int *ndeltas,
 622     FILE *f, off_t fileoffset, off_t filesize,
 623     struct got_delta_table *dt, FILE *basefile,
 624     off_t basefile_offset0, off_t basefile_size)
 625 {
 626         const struct got_error *err = NULL;
 627         const off_t offset0 = fileoffset;
 628         size_t nalloc = 0;
 629         const size_t alloc_chunk_size = 64;
 630
 631         *deltas = NULL;
 632         *ndeltas = 0;
 633
 634         /*
 635          * offset0 indicates where data to be deltified begins.
 636          * For example, we want to avoid deltifying a Git object header at
 637          * the beginning of the file.
 638          */
 639         if (fseeko(f, offset0, SEEK_SET) == -1)
 640                 return got_error_from_errno("fseeko");
 641
 642         *deltas = reallocarray(NULL, alloc_chunk_size,
 643             sizeof(struct got_delta_instruction));
 644         if (*deltas == NULL)
 645                 return got_error_from_errno("reallocarray");
 646         nalloc = alloc_chunk_size;
 647
 648         while (fileoffset < filesize) {
 649                 uint8_t buf[GOT_DELTIFY_MAXCHUNK];
 650                 off_t blocklen;
 651                 struct got_delta_block *block;
 652                 err = nextblk(buf, &blocklen, f);
 653                 if (err)
 654                         break;
 655                 if (blocklen == 0) {
 656                         /* Source remainder from the file itself. */
 657                         if (fileoffset < filesize) {
 658                                 err = emitdelta(deltas, &nalloc, ndeltas,
 659                                     alloc_chunk_size, 0, fileoffset - offset0,
 660                                     filesize - fileoffset);
 661                         }
 662                         break;
 663                 }
 664                 err = lookupblk(&block, dt, buf, blocklen, basefile,
 665                     basefile_offset0);
 666                 if (err)
 667                         break;
 668                 if (block != NULL) {
 669                         /*
 670                          * We have found a matching block in the delta base.
 671                          * Attempt to stretch the block as far as possible and
 672                          * generate a copy instruction.
 673                          */
 674                         err = stretchblk(basefile, basefile_offset0, block,
 675                             f, filesize, &blocklen);
 676                         if (err)
 677                                 break;
 678                         err = emitdelta(deltas, &nalloc, ndeltas,
 679                             alloc_chunk_size, 1, block->offset, blocklen);
 680                         if (err)
 681                                 break;
 682                 } else {
 683                         /*
 684                          * No match.
 685                          * This block needs to be sourced from the file itself.
 686                          */
 687                         err = emitdelta(deltas, &nalloc, ndeltas,
 688                             alloc_chunk_size, 0, fileoffset - offset0, blocklen);
 689                         if (err)
 690                                 break;
 691                 }
 692                 fileoffset += blocklen;
 693                 if (fseeko(f, fileoffset, SEEK_SET) == -1) {
 694                         err = got_error_from_errno("fseeko");
 695                         break;
 696                 }
 697         }
 698
 699         if (err) {
 700                 free(*deltas);
 701                 *deltas = NULL;
 702                 *ndeltas = 0;
 703         }
 704         return err;
 705 }
 706
 707 const struct got_error *
 708 got_deltify_file_mem(struct got_delta_instruction **deltas, int *ndeltas,
 709     FILE *f, off_t fileoffset, off_t filesize,
 710     struct got_delta_table *dt, uint8_t *basedata,
 711     off_t basefile_offset0, off_t basefile_size)
 712 {
 713         const struct got_error *err = NULL;
 714         const off_t offset0 = fileoffset;
 715         size_t nalloc = 0;
 716         const size_t alloc_chunk_size = 64;
 717
 718         *deltas = NULL;
 719         *ndeltas = 0;
 720
 721         /*
 722          * offset0 indicates where data to be deltified begins.
 723          * For example, we want to avoid deltifying a Git object header at
 724          * the beginning of the file.
 725          */
 726         if (fseeko(f, offset0, SEEK_SET) == -1)
 727                 return got_error_from_errno("fseeko");
 728
 729         *deltas = reallocarray(NULL, alloc_chunk_size,
 730             sizeof(struct got_delta_instruction));
 731         if (*deltas == NULL)
 732                 return got_error_from_errno("reallocarray");
 733         nalloc = alloc_chunk_size;
 734
 735         while (fileoffset < filesize) {
 736                 uint8_t buf[GOT_DELTIFY_MAXCHUNK];
 737                 off_t blocklen;
 738                 struct got_delta_block *block;
 739                 err = nextblk(buf, &blocklen, f);
 740                 if (err)
 741                         break;
 742                 if (blocklen == 0) {
 743                         /* Source remainder from the file itself. */
 744                         if (fileoffset < filesize) {
 745                                 err = emitdelta(deltas, &nalloc, ndeltas,
 746                                     alloc_chunk_size, 0, fileoffset - offset0,
 747                                     filesize - fileoffset);
 748                         }
 749                         break;
 750                 }
 751                 err = lookupblk_mem(&block, dt, buf, blocklen, basedata,
 752                     basefile_offset0);
 753                 if (err)
 754                         break;
 755                 if (block != NULL) {
 756                         /*
 757                          * We have found a matching block in the delta base.
 758                          * Attempt to stretch the block as far as possible and
 759                          * generate a copy instruction.
 760                          */
 761                         err = stretchblk_file_mem(basedata, basefile_offset0,
 762                             basefile_size, block, f, filesize, &blocklen);
 763                         if (err)
 764                                 break;
 765                         err = emitdelta(deltas, &nalloc, ndeltas,
 766                             alloc_chunk_size, 1, block->offset, blocklen);
 767                         if (err)
 768                                 break;
 769                 } else {
 770                         /*
 771                          * No match.
 772                          * This block needs to be sourced from the file itself.
 773                          */
 774                         err = emitdelta(deltas, &nalloc, ndeltas,
 775                             alloc_chunk_size, 0, fileoffset - offset0, blocklen);
 776                         if (err)
 777                                 break;
 778                 }
 779                 fileoffset += blocklen;
 780                 if (fseeko(f, fileoffset, SEEK_SET) == -1) {
 781                         err = got_error_from_errno("fseeko");
 782                         break;
 783                 }
 784         }
 785
 786         if (err) {
 787                 free(*deltas);
 788                 *deltas = NULL;
 789                 *ndeltas = 0;
 790         }
 791         return err;
 792 }
 793
 794 const struct got_error *
 795 got_deltify_mem_file(struct got_delta_instruction **deltas, int *ndeltas,
 796     uint8_t *data, off_t fileoffset, off_t filesize,
 797     struct got_delta_table *dt, FILE *basefile,
 798     off_t basefile_offset0, off_t basefile_size)
 799 {
 800         const struct got_error *err = NULL;
 801         const off_t offset0 = fileoffset;
 802         size_t nalloc = 0;
 803         const size_t alloc_chunk_size = 64;
 804
 805         *deltas = NULL;
 806         *ndeltas = 0;
 807
 808         *deltas = reallocarray(NULL, alloc_chunk_size,
 809             sizeof(struct got_delta_instruction));
 810         if (*deltas == NULL)
 811                 return got_error_from_errno("reallocarray");
 812         nalloc = alloc_chunk_size;
 813
 814         while (fileoffset < filesize) {
 815                 off_t blocklen;
 816                 struct got_delta_block *block;
 817                 err = nextblk_mem(&blocklen, data, fileoffset, filesize);
 818                 if (err)
 819                         break;
 820                 if (blocklen == 0) {
 821                         /* Source remainder from the file itself. */
 822                         if (fileoffset < filesize) {
 823                                 err = emitdelta(deltas, &nalloc, ndeltas,
 824                                     alloc_chunk_size, 0, fileoffset - offset0,
 825                                     filesize - fileoffset);
 826                         }
 827                         break;
 828                 }
 829                 err = lookupblk(&block, dt, data + fileoffset, blocklen,
 830                     basefile, basefile_offset0);
 831                 if (err)
 832                         break;
 833                 if (block != NULL) {
 834                         /*
 835                          * We have found a matching block in the delta base.
 836                          * Attempt to stretch the block as far as possible and
 837                          * generate a copy instruction.
 838                          */
 839                         err = stretchblk_mem_file(basefile, basefile_offset0,
 840                             block, data, fileoffset + blocklen, filesize,
 841                             &blocklen);
 842                         if (err)
 843                                 break;
 844                         err = emitdelta(deltas, &nalloc, ndeltas,
 845                             alloc_chunk_size, 1, block->offset, blocklen);
 846                         if (err)
 847                                 break;
 848                 } else {
 849                         /*
 850                          * No match.
 851                          * This block needs to be sourced from the file itself.
 852                          */
 853                         err = emitdelta(deltas, &nalloc, ndeltas,
 854                             alloc_chunk_size, 0, fileoffset - offset0, blocklen);
 855                         if (err)
 856                                 break;
 857                 }
 858                 fileoffset += blocklen;
 859         }
 860
 861         if (err) {
 862                 free(*deltas);
 863                 *deltas = NULL;
 864                 *ndeltas = 0;
 865         }
 866         return err;
 867 }
 868
 869 const struct got_error *
 870 got_deltify_mem_mem(struct got_delta_instruction **deltas, int *ndeltas,
 871     uint8_t *data, off_t fileoffset, off_t filesize,
 872     struct got_delta_table *dt, uint8_t *basedata,
 873     off_t basefile_offset0, off_t basefile_size)
 874 {
 875         const struct got_error *err = NULL;
 876         const off_t offset0 = fileoffset;
 877         size_t nalloc = 0;
 878         const size_t alloc_chunk_size = 64;
 879
 880         *deltas = NULL;
 881         *ndeltas = 0;
 882
 883         *deltas = reallocarray(NULL, alloc_chunk_size,
 884             sizeof(struct got_delta_instruction));
 885         if (*deltas == NULL)
 886                 return got_error_from_errno("reallocarray");
 887         nalloc = alloc_chunk_size;
 888
 889         while (fileoffset < filesize) {
 890                 off_t blocklen;
 891                 struct got_delta_block *block;
 892                 err = nextblk_mem(&blocklen, data, fileoffset, filesize);
 893                 if (err)
 894                         break;
 895                 if (blocklen == 0) {
 896                         /* Source remainder from the file itself. */
 897                         if (fileoffset < filesize) {
 898                                 err = emitdelta(deltas, &nalloc, ndeltas,
 899                                     alloc_chunk_size, 0, fileoffset - offset0,
 900                                     filesize - fileoffset);
 901                         }
 902                         break;
 903                 }
 904                 err = lookupblk_mem(&block, dt, data + fileoffset, blocklen,
 905                     basedata, basefile_offset0);
 906                 if (err)
 907                         break;
 908                 if (block != NULL) {
 909                         /*
 910                          * We have found a matching block in the delta base.
 911                          * Attempt to stretch the block as far as possible and
 912                          * generate a copy instruction.
 913                          */
 914                         err = stretchblk_mem_mem(basedata, basefile_offset0,
 915                             basefile_size, block, data, fileoffset + blocklen,
 916                             filesize, &blocklen);
 917                         if (err)
 918                                 break;
 919                         err = emitdelta(deltas, &nalloc, ndeltas,
 920                             alloc_chunk_size, 1, block->offset, blocklen);
 921                         if (err)
 922                                 break;
 923                 } else {
 924                         /*
 925                          * No match.
 926                          * This block needs to be sourced from the file itself.
 927                          */
 928                         err = emitdelta(deltas, &nalloc, ndeltas,
 929                             alloc_chunk_size, 0, fileoffset - offset0, blocklen);
 930                         if (err)
 931                                 break;
 932                 }
 933                 fileoffset += blocklen;
 934         }
 935
 936         if (err) {
 937                 free(*deltas);
 938                 *deltas = NULL;
 939                 *ndeltas = 0;
 940         }
 941         return err;
 942 }