configurator: HAVE_SECTION_START_STOP
[ccan] / 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 }