git.ozlabs.org Git - ccan/blob - ccan/bdelta/bdelta.c

   1 /*
   2  * Copyright (C) 2011 Joseph Adams <joeyadams3.14159@gmail.com>
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a copy
   5  * of this software and associated documentation files (the "Software"), to deal
   6  * in the Software without restriction, including without limitation the rights
   7  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8  * copies of the Software, and to permit persons to whom the Software is
   9  * furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be included in
  12  * all copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  20  * THE SOFTWARE.
  21  */
  22
  23 #include "bdelta.h"
  24
  25 #include <assert.h>
  26 #include <limits.h>
  27 #include <stdint.h>
  28 #include <stdio.h>
  29 #include <stdlib.h>
  30 #include <string.h>
  31
  32 typedef struct
  33 {
  34         unsigned char *cur;    /* End of string; insertion point for new bytes */
  35         unsigned char *end;    /* End of buffer */
  36         unsigned char *start;  /* Beginning of string */
  37 } SB;
  38
  39 /* sb is evaluated multiple times in these macros. */
  40 #define sb_size(sb)  ((size_t)((sb)->cur - (sb)->start))
  41 #define sb_avail(sb) ((size_t)((sb)->end - (sb)->cur))
  42
  43 /* sb and need may be evaluated multiple times. */
  44 #define sb_need(sb, need) do {           \
  45                 if (sb_avail(sb) < (need))       \
  46                         if (sb_grow(sb, need) != 0)  \
  47                                 goto out_of_memory;      \
  48         } while (0)
  49
  50 static int sb_init(SB *sb)
  51 {
  52         sb->start = malloc(17);
  53         if (sb->start == NULL)
  54                 return -1;
  55         sb->cur = sb->start;
  56         sb->end = sb->start + 16;
  57         return 0;
  58 }
  59
  60 static int sb_grow(SB *sb, size_t need)
  61 {
  62         size_t length = sb->cur - sb->start;
  63         size_t alloc = sb->end - sb->start;
  64         unsigned char *tmp;
  65
  66         do {
  67                 alloc *= 2;
  68         } while (alloc < length + need);
  69
  70         tmp = realloc(sb->start, alloc + 1);
  71         if (tmp == NULL)
  72                 return -1;
  73         sb->start = tmp;
  74         sb->cur = tmp + length;
  75         sb->end = tmp + alloc;
  76         return 0;
  77 }
  78
  79 static int sb_putc(SB *sb, unsigned char c)
  80 {
  81         sb_need(sb, 1);
  82         *sb->cur++ = c;
  83         return 0;
  84
  85 out_of_memory:
  86         return -1;
  87 }
  88
  89 static int sb_write(SB *sb, const void *data, size_t size)
  90 {
  91         sb_need(sb, size);
  92         memcpy(sb->cur, data, size);
  93         sb->cur += size;
  94         return 0;
  95
  96 out_of_memory:
  97         return -1;
  98 }
  99
 100 static void sb_return(SB *sb, void **data_out, size_t *length_out)
 101 {
 102         *sb->cur = 0;
 103         if (data_out)
 104                 *data_out = sb->start;
 105         else
 106                 free(sb->start);
 107         if (length_out)
 108                 *length_out = sb->cur - sb->start;
 109 }
 110
 111 static void sb_discard(SB *sb, void **data_out, size_t *length_out)
 112 {
 113         free(sb->start);
 114         if (data_out)
 115                 *data_out = NULL;
 116         if (length_out)
 117                 *length_out = 0;
 118 }
 119
 120 /*
 121  * The first byte in a patch is the "patch type", which indicates how the
 122  * patch is formatted.  This keeps the patch format flexible while retaining
 123  * backward compatibility.  Patches produced with an older version of
 124  * the library can be applied with a newer version.
 125  *
 126  * PT_LITERAL
 127  *     Contains nothing more than the content of the new text.
 128  *
 129  * PT_CSI32
 130  *     A string of copy, skip, and insert instructions for generating the new
 131  *     string from the old.
 132  *
 133  *         copy(size):   Copy @size bytes from old to new.
 134  *         skip(size):   Skip @size bytes of old.
 135  *         insert(text): Insert @text into new.
 136  *
 137  *     The syntax is as follows:
 138  *
 139  *         copy:   instruction_byte(1) size
 140  *         skip:   instruction_byte(2) size
 141  *         insert: instruction_byte(3) size $size*OCTET
 142  *
 143  *         0 <= size_param_length <= 4
 144  *         instruction_byte(op) = op | size_param_length << 2
 145  *         size: $size_param_length*OCTET
 146  *               -- size is an unsigned integer encoded in big endian.
 147  *               -- However, if size_param_length is 0, the operation size is 1.
 148  *
 149  *     Simply put, an instruction starts with an opcode and operation size.
 150  *     An insert instruction is followed by the bytes to be inserted.
 151  */
 152 #define PT_LITERAL   10
 153 #define PT_CSI32     11
 154
 155 #define OP_COPY      1
 156 #define OP_SKIP      2
 157 #define OP_INSERT    3
 158
 159 static unsigned int bytes_needed_for_size(uint32_t size)
 160 {
 161         if (size == 1)
 162                 return 0;
 163         else if (size <= 0xFF)
 164                 return 1;
 165         else if (size <= 0xFFFF)
 166                 return 2;
 167         else if (size <= 0xFFFFFF)
 168                 return 3;
 169         else
 170                 return 4;
 171 }
 172
 173 /*
 174  * Return values:
 175  *
 176  *  BDELTA_OK:      Success
 177  *  BDELTA_MEMORY:  Memory allocation failed
 178  */
 179 static BDELTAcode csi32_emit_op(SB *patch_out, int op, uint32_t size, const char **new_)
 180 {
 181         unsigned int i;
 182         unsigned int size_param_length;
 183         size_t need;
 184         uint32_t tmp;
 185
 186         assert(op >= 1 && op <= 3);
 187
 188         if (size == 0)
 189                 return BDELTA_OK;
 190         size_param_length = bytes_needed_for_size(size);
 191
 192         need = 1 + size_param_length;
 193         if (op == OP_INSERT)
 194                 need += size;
 195         sb_need(patch_out, need);
 196
 197         *patch_out->cur++ = (unsigned int)op | size_param_length << 2;
 198         for (i = size_param_length, tmp = size; i-- > 0; tmp >>= 8)
 199                 patch_out->cur[i] = tmp & 0xFF;
 200         patch_out->cur += size_param_length;
 201
 202         switch (op) {
 203                 case OP_COPY:
 204                         *new_ += size;
 205                         break;
 206                 case OP_SKIP:
 207                         break;
 208                 case OP_INSERT:
 209                         memcpy(patch_out->cur, *new_, size);
 210                         patch_out->cur += size;
 211                         *new_ += size;
 212                         break;
 213                 default:
 214                         assert(0);
 215         }
 216
 217         return BDELTA_OK;
 218
 219 out_of_memory:
 220         return BDELTA_MEMORY;
 221 }
 222
 223 /*
 224  * On success, returns 1, advances *sp past the parsed text, and sets *op_out and *size_out.
 225  * On error or EOF, returns 0.
 226  */
 227 static int csi32_parse_op(
 228         const unsigned char **sp, const unsigned char *e,
 229         int *op_out, uint32_t *size_out)
 230 {
 231         const unsigned char *s = *sp;
 232         int op;
 233         unsigned int i;
 234         unsigned int size_param_length;
 235         uint32_t size;
 236
 237         if (s >= e)
 238                 return 0;
 239         op = *s & 3;
 240         size_param_length = *s >> 2;
 241         s++;
 242         if (op == 0 || size_param_length > 4)
 243                 return 0;
 244
 245         if (size_param_length == 0) {
 246                 size = 1;
 247         } else {
 248                 if ((size_t)(e - s) < size_param_length)
 249                         return 0;
 250                 size = 0;
 251                 for (i = 0; i < size_param_length; i++) {
 252                         size <<= 8;
 253                         size |= *s++ & 0xFF;
 254                 }
 255         }
 256
 257         /* Make sure insert data fits in the patch, but don't consume it. */
 258         if (op == OP_INSERT && (size_t)(e - s) < size)
 259                 return 0;
 260
 261         *op_out = op;
 262         *size_out = size;
 263         *sp = s;
 264         return 1;
 265 }
 266
 267 /*
 268  * bdelta uses the algorithm described in:
 269  *
 270  *     Myers, E. (1986). An O(ND) Difference Algorithm and Its Variations.
 271  *     Retrieved from http://www.xmailserver.org/diff2.pdf
 272  *
 273  * The pseudocode in Myers' paper (Figure 2) uses an array called V,
 274  * where (V[k], V[k] - k) is the endpoint of the furthest-reaching
 275  * D-path ending on diagonal k.
 276  *
 277  * The structure below holds the V array for every iteration of the outer loop.
 278  * Because each iteration produces D+1 values, a triangle is formed:
 279  *
 280  *                      k
 281  *        -5 -4 -3 -2 -1  0  1  2  3  4  5
 282  *      ----------------------------------
 283  *    0 |                 0                (copy 0)
 284  *      |                   \              skip 1
 285  *    1 |              0     1
 286  *      |                      \           skip 1, then copy 1
 287  *    2 |           2     2     3
 288  *  D   |                      /           insert 1, then copy 2
 289  *    3 |        3     4     5     5
 290  *      |                     \            skip 1, then copy 1
 291  *    4 |     3     4     5     7     7
 292  *      |                      /           insert 1
 293  *    5 |  3     4     5     7     -     -
 294  *
 295  * @data will literally contain: 0 0 1 2 2 3 3 4 5 5 3 4 5 7 7 3 4 5 7
 296  *
 297  * To convert this to an edit script, we first climb back to the top,
 298  * using the same procedure as was used when the triangle was generated:
 299  *
 300  *     If k = -D, climb right (the only way we can go).
 301  *     If k = +D, climb left  (the only way we can go).
 302  *     Otherwise, favor the greater number.
 303  *     If the numbers are the same, climb left.
 304  *
 305  * Finally, we convert the descent to the solution to a patch script:
 306  *
 307  *     The top number n corresponds to:
 308  *         copy   n
 309  *
 310  *     A descent left from a to b corresponds to:
 311  *         insert 1
 312  *         copy   b-a
 313  *
 314  *     A descent right from a to b corresponds to:
 315  *         skip   1
 316  *         copy   b-a-1
 317  */
 318 typedef struct
 319 {
 320         uint32_t *data;
 321         int solution_d;
 322         int solution_k;
 323         uint32_t *solution_ptr;
 324 } Triangle;
 325
 326 /*
 327  * Return values:
 328  *
 329  *  BDELTA_OK:                      Success
 330  *  BDELTA_MEMORY:                  Memory allocation failed
 331  *  BDELTA_INTERNAL_DMAX_EXCEEDED:  d_max exceeded (strings are too different)
 332  */
 333 static BDELTAcode build_triangle(
 334         const char *old,  uint32_t old_size,
 335         const char *new_, uint32_t new_size,
 336         int d_max,
 337         Triangle *triangle_out)
 338 {
 339         int d, k;
 340         uint32_t x, y;
 341         uint32_t *data;
 342         uint32_t *vprev; /* position within previous row */
 343         uint32_t *v;     /* position within current row */
 344         uint32_t *vcur;  /* beginning of current row */
 345         size_t data_alloc = 16;
 346
 347         memset(triangle_out, 0, sizeof(*triangle_out));
 348
 349         data = malloc(data_alloc * sizeof(*data));
 350         if (data == NULL)
 351                 return BDELTA_MEMORY;
 352
 353         /* Allow dmax < 0 to mean "no limit". */
 354         if (d_max < 0)
 355                 d_max = old_size + new_size;
 356
 357         /*
 358          * Compute the farthest-reaching 0-path so the loop after this
 359          * will have a "previous" row to start with.
 360          */
 361         for (x = 0; x < old_size && x < new_size && old[x] == new_[x]; )
 362                 x++;
 363         *data = x;
 364         if (x >= old_size && x >= new_size) {
 365                 /* Strings are equal, so return a triangle with one row (a dot). */
 366                 assert(x == old_size && x == new_size);
 367                 triangle_out->data = data;
 368                 triangle_out->solution_d = 0;
 369                 triangle_out->solution_k = 0;
 370                 triangle_out->solution_ptr = data;
 371                 return BDELTA_OK;
 372         }
 373         vprev = data;
 374         vcur = v = data + 1;
 375
 376         /*
 377          * Here is the core of the Myers diff algorithm.
 378          *
 379          * This is a direct translation of the pseudocode in Myers' paper,
 380          * with implementation-specific adaptations:
 381          *
 382          *  * Every V array is preserved per iteration of the outer loop.
 383          *    This is necessary so we can determine the actual patch, not just
 384          *    the length of the shortest edit string.  See the coment above
 385          *    the definition of Triangle for an in-depth explanation.
 386          *
 387          *  * Array items are stored consecutively so as to not waste space.
 388          *
 389          *  * The buffer holding the V arrays is expanded dynamically.
 390          */
 391         for (d = 1; d <= d_max; d++, vprev = vcur, vcur = v) {
 392                 /* Ensure that the buffer has enough room for this row. */
 393                 if ((size_t)(v - data + d + 1) > data_alloc) {
 394                         size_t vprev_idx = vprev - data;
 395                         size_t v_idx     = v     - data;
 396                         size_t vcur_idx  = vcur  - data;
 397                         uint32_t *tmp;
 398
 399                         do {
 400                                 data_alloc *= 2;
 401                         } while ((size_t)(v - data + d + 1) > data_alloc);
 402
 403                         tmp = realloc(data, data_alloc * sizeof(*data));
 404                         if (tmp == NULL) {
 405                                 free(data);
 406                                 return BDELTA_MEMORY;
 407                         }
 408                         data = tmp;
 409
 410                         /* Relocate pointers to the buffer we just expanded. */
 411                         vprev = data + vprev_idx;
 412                         v     = data + v_idx;
 413                         vcur  = data + vcur_idx;
 414                 }
 415
 416                 for (k = -d; k <= d; k += 2, vprev++) {
 417                         if (k == -d || (k != d && vprev[-1] < vprev[0]))
 418                                 x = vprev[0];
 419                         else
 420                                 x = vprev[-1] + 1;
 421                         y = x - k;
 422                         while (x < old_size && y < new_size && old[x] == new_[y])
 423                                 x++, y++;
 424                         *v++ = x;
 425                         if (x >= old_size && y >= new_size) {
 426                                 /* Shortest edit string found. */
 427                                 assert(x == old_size && y == new_size);
 428                                 triangle_out->data = data;
 429                                 triangle_out->solution_d = d;
 430                                 triangle_out->solution_k = k;
 431                                 triangle_out->solution_ptr = v - 1;
 432                                 return BDELTA_OK;
 433                         }
 434                 }
 435         }
 436
 437         free(data);
 438         return BDELTA_INTERNAL_DMAX_EXCEEDED;
 439 }
 440
 441 /*
 442  * Trace a solution back to the top, returning a string of instructions
 443  * for descending from the top to the solution.
 444  *
 445  * An instruction is one of the following:
 446  *
 447  *  -1: Descend left.
 448  *  +1: Descend right.
 449  *   0: Finished.  You should be at the solution now.
 450  *
 451  * If memory allocation fails, this function will return NULL.
 452  */
 453 static signed char *climb_triangle(const Triangle *triangle)
 454 {
 455         signed char *descent;
 456         int d, k;
 457         uint32_t *p;
 458
 459         assert(triangle->solution_d >= 0);
 460
 461         descent = malloc(triangle->solution_d + 1);
 462         if (descent == NULL)
 463                 return NULL;
 464         d = triangle->solution_d;
 465         k = triangle->solution_k;
 466         p = triangle->solution_ptr;
 467         descent[d] = 0;
 468
 469         while (d > 0) {
 470                 if (k == -d || (k != d && *(p-d-1) < *(p-d))) {
 471                         /* Climb right */
 472                         k++;
 473                         p = p - d;
 474                         descent[--d] = -1;
 475                 } else {
 476                         /* Climb left */
 477                         k--;
 478                         p = p - d - 1;
 479                         descent[--d] = 1;
 480                 }
 481         }
 482
 483         return descent;
 484 }
 485
 486 /*
 487  * Generate the actual patch, given data produced by build_triangle and
 488  * climb_triangle.  new_ is needed for the content of the insertions.
 489  *
 490  * See the comment above the definition of Triangle.  It concisely documents
 491  * how a descent down the triangle corresponds to a patch script.
 492  *
 493  * The resulting patch, including the patch type byte, is appended to patch_out.
 494  *
 495  * Return values:
 496  *
 497  *  BDELTA_OK:      Success
 498  *  BDELTA_MEMORY:  Memory allocation failed
 499  */
 500 static BDELTAcode descent_to_patch(
 501         const signed char *descent,
 502         const Triangle *triangle,
 503         const char *new_, uint32_t new_size,
 504         SB *patch_out)
 505 {
 506         const char *new_end = new_ + new_size;
 507         uint32_t *p = triangle->data;
 508         uint32_t *p2;
 509         int d = 0;
 510         int k = 0;
 511         int pending_op = 0;
 512         int current_op;
 513         uint32_t pending_length = 0;
 514         uint32_t copy_length;
 515
 516         if (sb_putc(patch_out, PT_CSI32) != 0)
 517                 return BDELTA_MEMORY;
 518
 519         if (*p > 0) {
 520                 if (csi32_emit_op(patch_out, OP_COPY, *p, &new_) != BDELTA_OK)
 521                         return BDELTA_MEMORY;
 522         }
 523
 524         for (; *descent != 0; descent++, p = p2) {
 525                 if (*descent < 0) {
 526                         /* Descend left. */
 527                         d++;
 528                         k--;
 529                         p2 = p + d;
 530                         current_op = OP_INSERT;
 531                         assert(*p2 >= *p);
 532                         copy_length = *p2 - *p;
 533                 } else {
 534                         /* Descend right. */
 535                         d++;
 536                         k++;
 537                         p2 = p + d + 1;
 538                         current_op = OP_SKIP;
 539                         assert(*p2 > *p);
 540                         copy_length = *p2 - *p - 1;
 541                 }
 542
 543                 if (pending_op == current_op) {
 544                         pending_length++;
 545                 } else {
 546                         if (pending_op != 0) {
 547                                 if (csi32_emit_op(patch_out, pending_op, pending_length, &new_) != BDELTA_OK)
 548                                         return BDELTA_MEMORY;
 549                         }
 550                         pending_op = current_op;
 551                         pending_length = 1;
 552                 }
 553
 554                 if (copy_length > 0) {
 555                         if (csi32_emit_op(patch_out, pending_op, pending_length, &new_) != BDELTA_OK)
 556                                 return BDELTA_MEMORY;
 557                         pending_op = 0;
 558                         if (csi32_emit_op(patch_out, OP_COPY, copy_length, &new_) != BDELTA_OK)
 559                                 return BDELTA_MEMORY;
 560                 }
 561         }
 562         assert(d == triangle->solution_d);
 563         assert(k == triangle->solution_k);
 564         assert(p == triangle->solution_ptr);
 565
 566         /* Emit the last pending op, unless it's a skip. */
 567         if (pending_op != 0 && pending_op != OP_SKIP) {
 568                 if (csi32_emit_op(patch_out, pending_op, pending_length, &new_) != BDELTA_OK)
 569                         return BDELTA_MEMORY;
 570         }
 571
 572         assert(new_ == new_end);
 573         return BDELTA_OK;
 574 }
 575
 576 /*
 577  * Generate a patch using Myers' O(ND) algorithm.
 578  *
 579  * The patch is appended to @patch_out, which must be initialized before calling.
 580  *
 581  * Return values:
 582  *
 583  *  BDELTA_OK:                         Success
 584  *  BDELTA_MEMORY:                     Memory allocation failed
 585  *  BDELTA_INTERNAL_INPUTS_TOO_LARGE:  Input sizes are too large
 586  *  BDELTA_INTERNAL_DMAX_EXCEEDED:     d_max exceeded (strings are too different)
 587  */
 588 static BDELTAcode diff_myers(
 589         const char *old,  size_t old_size,
 590         const char *new_, size_t new_size,
 591         SB *patch_out)
 592 {
 593         Triangle triangle;
 594         signed char *descent;
 595         BDELTAcode rc;
 596
 597         /* Make sure old_size + new_size does not overflow int or uint32_t. */
 598         if (old_size >= UINT32_MAX ||
 599             new_size >= UINT32_MAX - old_size ||
 600             old_size >= (unsigned int)INT_MAX ||
 601             new_size >= (unsigned int)INT_MAX - old_size)
 602                 return BDELTA_INTERNAL_INPUTS_TOO_LARGE;
 603
 604         rc = build_triangle(old, old_size, new_, new_size, 1000, &triangle);
 605         if (rc != BDELTA_OK)
 606                 return rc;
 607
 608         descent = climb_triangle(&triangle);
 609         if (descent == NULL)
 610                 goto oom1;
 611
 612         if (descent_to_patch(descent, &triangle, new_, new_size, patch_out) != BDELTA_OK)
 613                 goto oom2;
 614
 615         free(descent);
 616         free(triangle.data);
 617         return BDELTA_OK;
 618
 619 oom2:
 620         free(descent);
 621 oom1:
 622         free(triangle.data);
 623         return BDELTA_MEMORY;
 624 }
 625
 626 BDELTAcode bdelta_diff(
 627         const void  *old,       size_t  old_size,
 628         const void  *new_,      size_t  new_size,
 629         void       **patch_out, size_t *patch_size_out)
 630 {
 631         SB patch;
 632
 633         if (sb_init(&patch) != 0)
 634                 goto out_of_memory;
 635
 636         if (new_size == 0)
 637                 goto emit_new_literally;
 638
 639         if (diff_myers(old, old_size, new_, new_size, &patch) != BDELTA_OK)
 640                 goto emit_new_literally;
 641
 642         if (sb_size(&patch) > new_size) {
 643                 /*
 644                  * A literal copy of new is no longer than this patch.
 645                  * All that for nothing.
 646                  */
 647                 goto emit_new_literally;
 648         }
 649
 650         /*
 651          * Verify that patch, when applied to old, produces the correct text.
 652          * If it doesn't, it's a bug, but fall back to a simple emit
 653          * to avert data corruption.
 654          */
 655         {
 656                 void *result;
 657                 size_t result_size;
 658                 BDELTAcode rc;
 659                 int correct;
 660
 661                 rc = bdelta_patch(
 662                         old, old_size,
 663                         patch.start, patch.cur - patch.start,
 664                         &result, &result_size
 665                 );
 666
 667                 switch (rc) {
 668                         case BDELTA_OK:
 669                                 correct = (result_size == new_size &&
 670                                            memcmp(result, new_, new_size) == 0);
 671                                 free(result);
 672                                 break;
 673
 674                         case BDELTA_MEMORY:
 675                                 goto out_of_memory;
 676
 677                         default:
 678                                 correct = 0;
 679                                 break;
 680                 }
 681
 682                 if (!correct) {
 683                         assert(0);
 684                         goto emit_new_literally;
 685                 }
 686         }
 687
 688         sb_return(&patch, patch_out, patch_size_out);
 689         return BDELTA_OK;
 690
 691 emit_new_literally:
 692         if (patch.cur != patch.start) {
 693                 free(patch.start);
 694                 if (sb_init(&patch) != 0)
 695                         goto out_of_memory;
 696         }
 697         if (sb_putc(&patch, PT_LITERAL) != 0 || sb_write(&patch, new_, new_size) != 0)
 698                 goto out_of_memory;
 699         sb_return(&patch, patch_out, patch_size_out);
 700         return BDELTA_OK;
 701
 702 out_of_memory:
 703         sb_discard(&patch, patch_out, patch_size_out);
 704         return BDELTA_MEMORY;
 705 }
 706
 707 /*
 708  * Return values:
 709  *
 710  *  BDELTA_OK:              Success
 711  *  BDELTA_PATCH_INVALID:   Patch is malformed
 712  *  BDELTA_PATCH_MISMATCH:  Old string is too small
 713  *  BDELTA_MEMORY:          Memory allocation failed
 714  */
 715 static BDELTAcode patch_csi32(
 716         const unsigned char *o, const unsigned char *oe,
 717         const unsigned char *p, const unsigned char *pe,
 718         SB *new_out)
 719 {
 720         int op;
 721         uint32_t size;
 722
 723         while (csi32_parse_op(&p, pe, &op, &size)) {
 724                 if ((op == OP_COPY || op == OP_SKIP) && (size_t)(oe - o) < size) {
 725                         /* Copy or skip instruction exceeds length of old string. */
 726                         return BDELTA_PATCH_MISMATCH;
 727                 }
 728                 if (op == OP_COPY || op == OP_INSERT)
 729                         sb_need(new_out, size);
 730
 731                 switch (op) {
 732                         case OP_COPY:  /* Copy @size bytes from old string. */
 733                                 memcpy(new_out->cur, o, size);
 734                                 new_out->cur += size;
 735                                 o += size;
 736                                 break;
 737
 738                         case OP_SKIP:  /* Skip @size bytes of old string. */
 739                                 o += size;
 740                                 break;
 741
 742                         case OP_INSERT:  /* Insert @size new bytes (from the patch script). */
 743                                 memcpy(new_out->cur, p, size);
 744                                 new_out->cur += size;
 745                                 p += size;
 746                                 break;
 747
 748                         default:
 749                                 assert(0);
 750                 }
 751         }
 752         if (p != pe)
 753                 return BDELTA_PATCH_INVALID;
 754
 755         return BDELTA_OK;
 756
 757 out_of_memory:
 758         return BDELTA_MEMORY;
 759 }
 760
 761 BDELTAcode bdelta_patch(
 762         const void  *old,     size_t  old_size,
 763         const void  *patch,   size_t  patch_size,
 764         void       **new_out, size_t *new_size_out)
 765 {
 766         const unsigned char *o = old;
 767         const unsigned char *oe = o + old_size;
 768         const unsigned char *p = patch;
 769         const unsigned char *pe = p + patch_size;
 770         SB result;
 771         BDELTAcode rc;
 772
 773         if (sb_init(&result) != 0) {
 774                 rc = BDELTA_MEMORY;
 775                 goto discard;
 776         }
 777
 778         if (p >= pe) {
 779                 rc = BDELTA_PATCH_INVALID;
 780                 goto discard;
 781         }
 782
 783         switch (*p++) {
 784                 case PT_LITERAL:
 785                         if (sb_write(&result, p, pe - p) != 0) {
 786                                 rc = BDELTA_MEMORY;
 787                                 goto discard;
 788                         }
 789                         break;
 790
 791                 case PT_CSI32:
 792                         rc = patch_csi32(o, oe, p, pe, &result);
 793                         if (rc != BDELTA_OK)
 794                                 goto discard;
 795                         break;
 796
 797                 default:
 798                         rc = BDELTA_PATCH_INVALID;
 799                         goto discard;
 800         }
 801
 802         sb_return(&result, new_out, new_size_out);
 803         return BDELTA_OK;
 804
 805 discard:
 806         sb_discard(&result, new_out, new_size_out);
 807         return rc;
 808 }
 809
 810 const char *bdelta_strerror(BDELTAcode code)
 811 {
 812         switch (code) {
 813                 case BDELTA_OK:
 814                         return "Success";
 815                 case BDELTA_MEMORY:
 816                         return "Could not allocate memory";
 817                 case BDELTA_PATCH_INVALID:
 818                         return "Patch is invalid";
 819                 case BDELTA_PATCH_MISMATCH:
 820                         return "Patch applied to wrong data";
 821
 822                 case BDELTA_INTERNAL_DMAX_EXCEEDED:
 823                         return "Difference threshold exceeded (internal error)";
 824                 case BDELTA_INTERNAL_INPUTS_TOO_LARGE:
 825                         return "Inputs are too large (internal error)";
 826
 827                 default:
 828                         return "Invalid error code";
 829         }
 830 }
 831
 832 void bdelta_perror(const char *s, BDELTAcode code)
 833 {
 834         if (s != NULL && *s != '\0')
 835                 fprintf(stderr, "%s: %s\n", s, bdelta_strerror(code));
 836         else
 837                 fprintf(stderr, "%s\n", bdelta_strerror(code));
 838 }