Debian Codegraph @

ext/misc/fossildelta.c

raw
1 /*
2 ** 2019-02-19
3 **
4 ** The author disclaims copyright to this source code. In place of
5 ** a legal notice, here is a blessing:
6 **
7 ** May you do good and not evil.
8 ** May you find forgiveness for yourself and forgive others.
9 ** May you share freely, never taking more than you give.
10 **
11 ******************************************************************************
12 **
13 ** This SQLite extension implements the delta functions used by the RBU
14 ** extension. Three scalar functions and one table-valued function are
15 ** implemented here:
16 **
17 ** delta_apply(X,D) -- apply delta D to file X and return the result
18 ** delta_create(X,Y) -- compute and return a delta that carries X into Y
19 ** delta_output_size(D) -- blob size in bytes output from applying delta D
20 ** delta_parse(D) -- returns rows describing delta D
21 **
22 ** The delta format is the Fossil delta format, described in a comment
23 ** on the delete_create() function implementation below, and also at
24 **
25 ** https://fossil-scm.org/fossil/doc/trunk/www/delta_format.wiki
26 **
27 ** This delta format is used by the RBU extension, which is the main
28 ** reason that these routines are included in the extension library.
29 ** RBU does not use this extension directly. Rather, this extension is
30 ** provided as a convenience to developers who want to analyze RBU files
31 ** that contain deltas.
32 */
33 #include <string.h>
34 #include <assert.h>
35 #include <stdlib.h>
36 #include "sqlite3ext.h"
37 SQLITE_EXTENSION_INIT1
38
39 #ifndef SQLITE_AMALGAMATION
40 /*
41 ** The "u32" type must be an unsigned 32-bit integer. "u64" is
42 ** an unsigned 64-bit integer.
43 */
44 typedef unsigned int u32;
45 typedef sqlite3_uint64 u64;
46
47 /*
48 ** Must be a 16-bit value
49 */
50 typedef short int s16;
51 typedef unsigned short int u16;
52
53 #endif /* SQLITE_AMALGAMATION */
54
55
56 /*
57 ** The width of a hash window in bytes. The algorithm only works if this
58 ** is a power of 2.
59 */
60 #define NHASH 16
61
62 /*
63 ** The current state of the rolling hash.
64 **
65 ** z[] holds the values that have been hashed. z[] is a circular buffer.
66 ** z[i] is the first entry and z[(i+NHASH-1)%NHASH] is the last entry of
67 ** the window.
68 **
69 ** Hash.a is the sum of all elements of hash.z[]. Hash.b is a weighted
70 ** sum. Hash.b is z[i]*NHASH + z[i+1]*(NHASH-1) + ... + z[i+NHASH-1]*1.
71 ** (Each index for z[] should be module NHASH, of course. The %NHASH operator
72 ** is omitted in the prior expression for brevity.)
73 */
74 typedef struct hash hash;
75 struct hash {
76 u16 a, b; /* Hash values */
77 u16 i; /* Start of the hash window */
78 char z[NHASH]; /* The values that have been hashed */
79 };
80
81 /*
82 ** Initialize the rolling hash using the first NHASH characters of z[]
83 */
84 static void hash_init(hash *pHash, const char *z){
85 u16 a, b, i;
86 a = b = z[0];
87 for(i=1; i<NHASH; i++){
88 a += z[i];
89 b += a;
90 }
91 memcpy(pHash->z, z, NHASH);
92 pHash->a = a & 0xffff;
93 pHash->b = b & 0xffff;
94 pHash->i = 0;
95 }
96
97 /*
98 ** Advance the rolling hash by a single character "c"
99 */
100 static void hash_next(hash *pHash, int c){
101 u16 old = pHash->z[pHash->i];
102 pHash->z[pHash->i] = c;
103 pHash->i = (pHash->i+1)&(NHASH-1);
104 pHash->a = pHash->a - old + c;
105 pHash->b = pHash->b - NHASH*old + pHash->a;
106 }
107
108 /*
109 ** Return a 32-bit hash value
110 */
111 static u32 hash_32bit(hash *pHash){
112 return (pHash->a & 0xffff) | (((u32)(pHash->b & 0xffff))<<16);
113 }
114
115 /*
116 ** Compute a hash on NHASH bytes.
117 **
118 ** This routine is intended to be equivalent to:
119 ** hash h;
120 ** hash_init(&h, zInput);
121 ** return hash_32bit(&h);
122 */
123 static u32 hash_once(const char *z){
124 u16 a, b, i;
125 a = b = z[0];
126 for(i=1; i<NHASH; i++){
127 a += z[i];
128 b += a;
129 }
130 return a | (((u32)b)<<16);
131 }
132
133 /*
134 ** Write an base-64 integer into the given buffer.
135 */
136 static void putInt(unsigned int v, char **pz){
137 static const char zDigits[] =
138 "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz~";
139 /* 123456789 123456789 123456789 123456789 123456789 123456789 123 */
140 int i, j;
141 char zBuf[20];
142 if( v==0 ){
143 *(*pz)++ = '0';
144 return;
145 }
146 for(i=0; v>0; i++, v>>=6){
147 zBuf[i] = zDigits[v&0x3f];
148 }
149 for(j=i-1; j>=0; j--){
150 *(*pz)++ = zBuf[j];
151 }
152 }
153
154 /*
155 ** Read bytes from *pz and convert them into a positive integer. When
156 ** finished, leave *pz pointing to the first character past the end of
157 ** the integer. The *pLen parameter holds the length of the string
158 ** in *pz and is decremented once for each character in the integer.
159 */
160 static unsigned int deltaGetInt(const char **pz, int *pLen){
161 static const signed char zValue[] = {
162 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
163 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
164 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
165 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1,
166 -1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
167 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1, -1, -1, -1, 36,
168 -1, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51,
169 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, -1, -1, -1, 63, -1,
170 };
171 unsigned int v = 0;
172 int c;
173 unsigned char *z = (unsigned char*)*pz;
174 unsigned char *zStart = z;
175 while( (c = zValue[0x7f&*(z++)])>=0 ){
176 v = (v<<6) + c;
177 }
178 z--;
179 *pLen -= z - zStart;
180 *pz = (char*)z;
181 return v;
182 }
183
184 /*
185 ** Return the number digits in the base-64 representation of a positive integer
186 */
187 static int digit_count(int v){
188 unsigned int i, x;
189 for(i=1, x=64; v>=x; i++, x <<= 6){}
190 return i;
191 }
192
193 #ifdef __GNUC__
194 # define GCC_VERSION (__GNUC__*1000000+__GNUC_MINOR__*1000+__GNUC_PATCHLEVEL__)
195 #else
196 # define GCC_VERSION 0
197 #endif
198
199 /*
200 ** Compute a 32-bit big-endian checksum on the N-byte buffer. If the
201 ** buffer is not a multiple of 4 bytes length, compute the sum that would
202 ** have occurred if the buffer was padded with zeros to the next multiple
203 ** of four bytes.
204 */
205 static unsigned int checksum(const char *zIn, size_t N){
206 static const int byteOrderTest = 1;
207 const unsigned char *z = (const unsigned char *)zIn;
208 const unsigned char *zEnd = (const unsigned char*)&zIn[N&~3];
209 unsigned sum = 0;
210 assert( (z - (const unsigned char*)0)%4==0 ); /* Four-byte alignment */
211 if( 0==*(char*)&byteOrderTest ){
212 /* This is a big-endian machine */
213 while( z<zEnd ){
214 sum += *(unsigned*)z;
215 z += 4;
216 }
217 }else{
218 /* A little-endian machine */
219 #if GCC_VERSION>=4003000
220 while( z<zEnd ){
221 sum += __builtin_bswap32(*(unsigned*)z);
222 z += 4;
223 }
224 #elif defined(_MSC_VER) && _MSC_VER>=1300
225 while( z<zEnd ){
226 sum += _byteswap_ulong(*(unsigned*)z);
227 z += 4;
228 }
229 #else
230 unsigned sum0 = 0;
231 unsigned sum1 = 0;
232 unsigned sum2 = 0;
233 while(N >= 16){
234 sum0 += ((unsigned)z[0] + z[4] + z[8] + z[12]);
235 sum1 += ((unsigned)z[1] + z[5] + z[9] + z[13]);
236 sum2 += ((unsigned)z[2] + z[6] + z[10]+ z[14]);
237 sum += ((unsigned)z[3] + z[7] + z[11]+ z[15]);
238 z += 16;
239 N -= 16;
240 }
241 while(N >= 4){
242 sum0 += z[0];
243 sum1 += z[1];
244 sum2 += z[2];
245 sum += z[3];
246 z += 4;
247 N -= 4;
248 }
249 sum += (sum2 << 8) + (sum1 << 16) + (sum0 << 24);
250 #endif
251 }
252 switch(N&3){
253 case 3: sum += (z[2] << 8);
254 case 2: sum += (z[1] << 16);
255 case 1: sum += (z[0] << 24);
256 default: ;
257 }
258 return sum;
259 }
260
261 /*
262 ** Create a new delta.
263 **
264 ** The delta is written into a preallocated buffer, zDelta, which
265 ** should be at least 60 bytes longer than the target file, zOut.
266 ** The delta string will be NUL-terminated, but it might also contain
267 ** embedded NUL characters if either the zSrc or zOut files are
268 ** binary. This function returns the length of the delta string
269 ** in bytes, excluding the final NUL terminator character.
270 **
271 ** Output Format:
272 **
273 ** The delta begins with a base64 number followed by a newline. This
274 ** number is the number of bytes in the TARGET file. Thus, given a
275 ** delta file z, a program can compute the size of the output file
276 ** simply by reading the first line and decoding the base-64 number
277 ** found there. The delta_output_size() routine does exactly this.
278 **
279 ** After the initial size number, the delta consists of a series of
280 ** literal text segments and commands to copy from the SOURCE file.
281 ** A copy command looks like this:
282 **
283 ** NNN@MMM,
284 **
285 ** where NNN is the number of bytes to be copied and MMM is the offset
286 ** into the source file of the first byte (both base-64). If NNN is 0
287 ** it means copy the rest of the input file. Literal text is like this:
288 **
289 ** NNN:TTTTT
290 **
291 ** where NNN is the number of bytes of text (base-64) and TTTTT is the text.
292 **
293 ** The last term is of the form
294 **
295 ** NNN;
296 **
297 ** In this case, NNN is a 32-bit bigendian checksum of the output file
298 ** that can be used to verify that the delta applied correctly. All
299 ** numbers are in base-64.
300 **
301 ** Pure text files generate a pure text delta. Binary files generate a
302 ** delta that may contain some binary data.
303 **
304 ** Algorithm:
305 **
306 ** The encoder first builds a hash table to help it find matching
307 ** patterns in the source file. 16-byte chunks of the source file
308 ** sampled at evenly spaced intervals are used to populate the hash
309 ** table.
310 **
311 ** Next we begin scanning the target file using a sliding 16-byte
312 ** window. The hash of the 16-byte window in the target is used to
313 ** search for a matching section in the source file. When a match
314 ** is found, a copy command is added to the delta. An effort is
315 ** made to extend the matching section to regions that come before
316 ** and after the 16-byte hash window. A copy command is only issued
317 ** if the result would use less space that just quoting the text
318 ** literally. Literal text is added to the delta for sections that
319 ** do not match or which can not be encoded efficiently using copy
320 ** commands.
321 */
322 static int delta_create(
323 const char *zSrc, /* The source or pattern file */
324 unsigned int lenSrc, /* Length of the source file */
325 const char *zOut, /* The target file */
326 unsigned int lenOut, /* Length of the target file */
327 char *zDelta /* Write the delta into this buffer */
328 ){
329 int i, base;
330 char *zOrigDelta = zDelta;
331 hash h;
332 int nHash; /* Number of hash table entries */
333 int *landmark; /* Primary hash table */
334 int *collide; /* Collision chain */
335 int lastRead = -1; /* Last byte of zSrc read by a COPY command */
336
337 /* Add the target file size to the beginning of the delta
338 */
339 putInt(lenOut, &zDelta);
340 *(zDelta++) = '\n';
341
342 /* If the source file is very small, it means that we have no
343 ** chance of ever doing a copy command. Just output a single
344 ** literal segment for the entire target and exit.
345 */
346 if( lenSrc<=NHASH ){
347 putInt(lenOut, &zDelta);
348 *(zDelta++) = ':';
349 memcpy(zDelta, zOut, lenOut);
350 zDelta += lenOut;
351 putInt(checksum(zOut, lenOut), &zDelta);
352 *(zDelta++) = ';';
353 return zDelta - zOrigDelta;
354 }
355
356 /* Compute the hash table used to locate matching sections in the
357 ** source file.
358 */
359 nHash = lenSrc/NHASH;
360 collide = sqlite3_malloc64( (sqlite3_int64)nHash*2*sizeof(int) );
361 memset(collide, -1, nHash*2*sizeof(int));
362 landmark = &collide[nHash];
363 for(i=0; i<lenSrc-NHASH; i+=NHASH){
364 int hv = hash_once(&zSrc[i]) % nHash;
365 collide[i/NHASH] = landmark[hv];
366 landmark[hv] = i/NHASH;
367 }
368
369 /* Begin scanning the target file and generating copy commands and
370 ** literal sections of the delta.
371 */
372 base = 0; /* We have already generated everything before zOut[base] */
373 while( base+NHASH<lenOut ){
374 int iSrc, iBlock;
375 unsigned int bestCnt, bestOfst=0, bestLitsz=0;
376 hash_init(&h, &zOut[base]);
377 i = 0; /* Trying to match a landmark against zOut[base+i] */
378 bestCnt = 0;
379 while( 1 ){
380 int hv;
381 int limit = 250;
382
383 hv = hash_32bit(&h) % nHash;
384 iBlock = landmark[hv];
385 while( iBlock>=0 && (limit--)>0 ){
386 /*
387 ** The hash window has identified a potential match against
388 ** landmark block iBlock. But we need to investigate further.
389 **
390 ** Look for a region in zOut that matches zSrc. Anchor the search
391 ** at zSrc[iSrc] and zOut[base+i]. Do not include anything prior to
392 ** zOut[base] or after zOut[outLen] nor anything after zSrc[srcLen].
393 **
394 ** Set cnt equal to the length of the match and set ofst so that
395 ** zSrc[ofst] is the first element of the match. litsz is the number
396 ** of characters between zOut[base] and the beginning of the match.
397 ** sz will be the overhead (in bytes) needed to encode the copy
398 ** command. Only generate copy command if the overhead of the
399 ** copy command is less than the amount of literal text to be copied.
400 */
401 int cnt, ofst, litsz;
402 int j, k, x, y;
403 int sz;
404 int limitX;
405
406 /* Beginning at iSrc, match forwards as far as we can. j counts
407 ** the number of characters that match */
408 iSrc = iBlock*NHASH;
409 y = base+i;
410 limitX = ( lenSrc-iSrc <= lenOut-y ) ? lenSrc : iSrc + lenOut - y;
411 for(x=iSrc; x<limitX; x++, y++){
412 if( zSrc[x]!=zOut[y] ) break;
413 }
414 j = x - iSrc - 1;
415
416 /* Beginning at iSrc-1, match backwards as far as we can. k counts
417 ** the number of characters that match */
418 for(k=1; k<iSrc && k<=i; k++){
419 if( zSrc[iSrc-k]!=zOut[base+i-k] ) break;
420 }
421 k--;
422
423 /* Compute the offset and size of the matching region */
424 ofst = iSrc-k;
425 cnt = j+k+1;
426 litsz = i-k; /* Number of bytes of literal text before the copy */
427 /* sz will hold the number of bytes needed to encode the "insert"
428 ** command and the copy command, not counting the "insert" text */
429 sz = digit_count(i-k)+digit_count(cnt)+digit_count(ofst)+3;
430 if( cnt>=sz && cnt>bestCnt ){
431 /* Remember this match only if it is the best so far and it
432 ** does not increase the file size */
433 bestCnt = cnt;
434 bestOfst = iSrc-k;
435 bestLitsz = litsz;
436 }
437
438 /* Check the next matching block */
439 iBlock = collide[iBlock];
440 }
441
442 /* We have a copy command that does not cause the delta to be larger
443 ** than a literal insert. So add the copy command to the delta.
444 */
445 if( bestCnt>0 ){
446 if( bestLitsz>0 ){
447 /* Add an insert command before the copy */
448 putInt(bestLitsz,&zDelta);
449 *(zDelta++) = ':';
450 memcpy(zDelta, &zOut[base], bestLitsz);
451 zDelta += bestLitsz;
452 base += bestLitsz;
453 }
454 base += bestCnt;
455 putInt(bestCnt, &zDelta);
456 *(zDelta++) = '@';
457 putInt(bestOfst, &zDelta);
458 *(zDelta++) = ',';
459 if( bestOfst + bestCnt -1 > lastRead ){
460 lastRead = bestOfst + bestCnt - 1;
461 }
462 bestCnt = 0;
463 break;
464 }
465
466 /* If we reach this point, it means no match is found so far */
467 if( base+i+NHASH>=lenOut ){
468 /* We have reached the end of the file and have not found any
469 ** matches. Do an "insert" for everything that does not match */
470 putInt(lenOut-base, &zDelta);
471 *(zDelta++) = ':';
472 memcpy(zDelta, &zOut[base], lenOut-base);
473 zDelta += lenOut-base;
474 base = lenOut;
475 break;
476 }
477
478 /* Advance the hash by one character. Keep looking for a match */
479 hash_next(&h, zOut[base+i+NHASH]);
480 i++;
481 }
482 }
483 /* Output a final "insert" record to get all the text at the end of
484 ** the file that does not match anything in the source file.
485 */
486 if( base<lenOut ){
487 putInt(lenOut-base, &zDelta);
488 *(zDelta++) = ':';
489 memcpy(zDelta, &zOut[base], lenOut-base);
490 zDelta += lenOut-base;
491 }
492 /* Output the final checksum record. */
493 putInt(checksum(zOut, lenOut), &zDelta);
494 *(zDelta++) = ';';
495 sqlite3_free(collide);
496 return zDelta - zOrigDelta;
497 }
498
499 /*
500 ** Return the size (in bytes) of the output from applying
501 ** a delta.
502 **
503 ** This routine is provided so that an procedure that is able
504 ** to call delta_apply() can learn how much space is required
505 ** for the output and hence allocate nor more space that is really
506 ** needed.
507 */
508 static int delta_output_size(const char *zDelta, int lenDelta){
509 int size;
510 size = deltaGetInt(&zDelta, &lenDelta);
511 if( *zDelta!='\n' ){
512 /* ERROR: size integer not terminated by "\n" */
513 return -1;
514 }
515 return size;
516 }
517
518
519 /*
520 ** Apply a delta.
521 **
522 ** The output buffer should be big enough to hold the whole output
523 ** file and a NUL terminator at the end. The delta_output_size()
524 ** routine will determine this size for you.
525 **
526 ** The delta string should be null-terminated. But the delta string
527 ** may contain embedded NUL characters (if the input and output are
528 ** binary files) so we also have to pass in the length of the delta in
529 ** the lenDelta parameter.
530 **
531 ** This function returns the size of the output file in bytes (excluding
532 ** the final NUL terminator character). Except, if the delta string is
533 ** malformed or intended for use with a source file other than zSrc,
534 ** then this routine returns -1.
535 **
536 ** Refer to the delta_create() documentation above for a description
537 ** of the delta file format.
538 */
539 static int delta_apply(
540 const char *zSrc, /* The source or pattern file */
541 int lenSrc, /* Length of the source file */
542 const char *zDelta, /* Delta to apply to the pattern */
543 int lenDelta, /* Length of the delta */
544 char *zOut /* Write the output into this preallocated buffer */
545 ){
546 sqlite3_uint64 limit;
547 sqlite3_uint64 total = 0;
548 #ifdef FOSSIL_ENABLE_DELTA_CKSUM_TEST
549 char *zOrigOut = zOut;
550 #endif
551
552 limit = deltaGetInt(&zDelta, &lenDelta);
553 if( *zDelta!='\n' ){
554 /* ERROR: size integer not terminated by "\n" */
555 return -1;
556 }
557 zDelta++; lenDelta--;
558 while( *zDelta && lenDelta>0 ){
559 unsigned int cnt, ofst;
560 cnt = deltaGetInt(&zDelta, &lenDelta);
561 switch( zDelta[0] ){
562 case '@': {
563 zDelta++; lenDelta--;
564 ofst = deltaGetInt(&zDelta, &lenDelta);
565 if( lenDelta>0 && zDelta[0]!=',' ){
566 /* ERROR: copy command not terminated by ',' */
567 return -1;
568 }
569 zDelta++; lenDelta--;
570 total += cnt;
571 if( total>limit ){
572 /* ERROR: copy exceeds output file size */
573 return -1;
574 }
575 if( (u64)ofst+(u64)cnt > (u64)lenSrc ){
576 /* ERROR: copy extends past end of input */
577 return -1;
578 }
579 memcpy(zOut, &zSrc[ofst], cnt);
580 zOut += cnt;
581 break;
582 }
583 case ':': {
584 zDelta++; lenDelta--;
585 total += cnt;
586 if( total>limit ){
587 /* ERROR: insert command gives an output larger than predicted */
588 return -1;
589 }
590 if( cnt>lenDelta ){
591 /* ERROR: insert count exceeds size of delta */
592 return -1;
593 }
594 memcpy(zOut, zDelta, cnt);
595 zOut += cnt;
596 zDelta += cnt;
597 lenDelta -= cnt;
598 break;
599 }
600 case ';': {
601 zDelta++; lenDelta--;
602 zOut[0] = 0;
603 #ifdef FOSSIL_ENABLE_DELTA_CKSUM_TEST
604 if( cnt!=checksum(zOrigOut, total) ){
605 /* ERROR: bad checksum */
606 return -1;
607 }
608 #endif
609 if( total!=limit ){
610 /* ERROR: generated size does not match predicted size */
611 return -1;
612 }
613 return total;
614 }
615 default: {
616 /* ERROR: unknown delta operator */
617 return -1;
618 }
619 }
620 }
621 /* ERROR: unterminated delta */
622 return -1;
623 }
624
625 /*
626 ** SQL functions: delta_create(X,Y)
627 **
628 ** Return a delta for carrying X into Y.
629 */
630 static void deltaCreateFunc(
631 sqlite3_context *context,
632 int argc,
633 sqlite3_value **argv
634 ){
635 const char *aOrig; int nOrig; /* old blob */
636 const char *aNew; int nNew; /* new blob */
637 char *aOut; int nOut; /* output delta */
638
639 assert( argc==2 );
640 if( sqlite3_value_type(argv[0])==SQLITE_NULL ) return;
641 if( sqlite3_value_type(argv[1])==SQLITE_NULL ) return;
642 nOrig = sqlite3_value_bytes(argv[0]);
643 aOrig = (const char*)sqlite3_value_blob(argv[0]);
644 nNew = sqlite3_value_bytes(argv[1]);
645 aNew = (const char*)sqlite3_value_blob(argv[1]);
646 aOut = sqlite3_malloc64(nNew+70);
647 if( aOut==0 ){
648 sqlite3_result_error_nomem(context);
649 }else{
650 nOut = delta_create(aOrig, nOrig, aNew, nNew, aOut);
651 if( nOut<0 ){
652 sqlite3_free(aOut);
653 sqlite3_result_error(context, "cannot create fossil delta", -1);
654 }else{
655 sqlite3_result_blob(context, aOut, nOut, sqlite3_free);
656 }
657 }
658 }
659
660 /*
661 ** SQL functions: delta_apply(X,D)
662 **
663 ** Return the result of applying delta D to input X.
664 */
665 static void deltaApplyFunc(
666 sqlite3_context *context,
667 int argc,
668 sqlite3_value **argv
669 ){
670 const char *aOrig; int nOrig; /* The X input */
671 const char *aDelta; int nDelta; /* The input delta (D) */
672 char *aOut; int nOut, nOut2; /* The output */
673
674 assert( argc==2 );
675 if( sqlite3_value_type(argv[0])==SQLITE_NULL ) return;
676 if( sqlite3_value_type(argv[1])==SQLITE_NULL ) return;
677 nOrig = sqlite3_value_bytes(argv[0]);
678 aOrig = (const char*)sqlite3_value_blob(argv[0]);
679 nDelta = sqlite3_value_bytes(argv[1]);
680 aDelta = (const char*)sqlite3_value_blob(argv[1]);
681
682 /* Figure out the size of the output */
683 nOut = delta_output_size(aDelta, nDelta);
684 if( nOut<0 ){
685 sqlite3_result_error(context, "corrupt fossil delta", -1);
686 return;
687 }
688 aOut = sqlite3_malloc64((sqlite3_int64)nOut+1);
689 if( aOut==0 ){
690 sqlite3_result_error_nomem(context);
691 }else{
692 nOut2 = delta_apply(aOrig, nOrig, aDelta, nDelta, aOut);
693 if( nOut2!=nOut ){
694 sqlite3_free(aOut);
695 sqlite3_result_error(context, "corrupt fossil delta", -1);
696 }else{
697 sqlite3_result_blob(context, aOut, nOut, sqlite3_free);
698 }
699 }
700 }
701
702
703 /*
704 ** SQL functions: delta_output_size(D)
705 **
706 ** Return the size of the output that results from applying delta D.
707 */
708 static void deltaOutputSizeFunc(
709 sqlite3_context *context,
710 int argc,
711 sqlite3_value **argv
712 ){
713 const char *aDelta; int nDelta; /* The input delta (D) */
714 int nOut; /* Size of output */
715 assert( argc==1 );
716 if( sqlite3_value_type(argv[0])==SQLITE_NULL ) return;
717 nDelta = sqlite3_value_bytes(argv[0]);
718 aDelta = (const char*)sqlite3_value_blob(argv[0]);
719
720 /* Figure out the size of the output */
721 nOut = delta_output_size(aDelta, nDelta);
722 if( nOut<0 ){
723 sqlite3_result_error(context, "corrupt fossil delta", -1);
724 return;
725 }else{
726 sqlite3_result_int(context, nOut);
727 }
728 }
729
730 /*****************************************************************************
731 ** Table-valued SQL function: delta_parse(DELTA)
732 **
733 ** Schema:
734 **
735 ** CREATE TABLE delta_parse(
736 ** op TEXT,
737 ** a1 INT,
738 ** a2 ANY,
739 ** delta HIDDEN BLOB
740 ** );
741 **
742 ** Given an input DELTA, this function parses the delta and returns
743 ** rows for each entry in the delta. The op column has one of the
744 ** values SIZE, COPY, INSERT, CHECKSUM, ERROR.
745 **
746 ** Assuming no errors, the first row has op='SIZE'. a1 is the size of
747 ** the output in bytes and a2 is NULL.
748 **
749 ** After the initial SIZE row, there are zero or more 'COPY' and/or 'INSERT'
750 ** rows. A COPY row means content is copied from the source into the
751 ** output. Column a1 is the number of bytes to copy and a2 is the offset
752 ** into source from which to begin copying. An INSERT row means to
753 ** insert text into the output stream. Column a1 is the number of bytes
754 ** to insert and column is a BLOB that contains the text to be inserted.
755 **
756 ** The last row of a well-formed delta will have an op value of 'CHECKSUM'.
757 ** The a1 column will be the value of the checksum and a2 will be NULL.
758 **
759 ** If the input delta is not well-formed, then a row with an op value
760 ** of 'ERROR' is returned. The a1 value of the ERROR row is the offset
761 ** into the delta where the error was encountered and a2 is NULL.
762 */
763 typedef struct deltaparsevtab_vtab deltaparsevtab_vtab;
764 typedef struct deltaparsevtab_cursor deltaparsevtab_cursor;
765 struct deltaparsevtab_vtab {
766 sqlite3_vtab base; /* Base class - must be first */
767 /* No additional information needed */
768 };
769 struct deltaparsevtab_cursor {
770 sqlite3_vtab_cursor base; /* Base class - must be first */
771 char *aDelta; /* The delta being parsed */
772 int nDelta; /* Number of bytes in the delta */
773 int iCursor; /* Current cursor location */
774 int eOp; /* Name of current operator */
775 unsigned int a1, a2; /* Arguments to current operator */
776 int iNext; /* Next cursor value */
777 };
778
779 /* Operator names:
780 */
781 static const char *azOp[] = {
782 "SIZE", "COPY", "INSERT", "CHECKSUM", "ERROR", "EOF"
783 };
784 #define DELTAPARSE_OP_SIZE 0
785 #define DELTAPARSE_OP_COPY 1
786 #define DELTAPARSE_OP_INSERT 2
787 #define DELTAPARSE_OP_CHECKSUM 3
788 #define DELTAPARSE_OP_ERROR 4
789 #define DELTAPARSE_OP_EOF 5
790
791 /*
792 ** The deltaparsevtabConnect() method is invoked to create a new
793 ** deltaparse virtual table.
794 **
795 ** Think of this routine as the constructor for deltaparsevtab_vtab objects.
796 **
797 ** All this routine needs to do is:
798 **
799 ** (1) Allocate the deltaparsevtab_vtab object and initialize all fields.
800 **
801 ** (2) Tell SQLite (via the sqlite3_declare_vtab() interface) what the
802 ** result set of queries against the virtual table will look like.
803 */
804 static int deltaparsevtabConnect(
805 sqlite3 *db,
806 void *pAux,
807 int argc, const char *const*argv,
808 sqlite3_vtab **ppVtab,
809 char **pzErr
810 ){
811 deltaparsevtab_vtab *pNew;
812 int rc;
813
814 rc = sqlite3_declare_vtab(db,
815 "CREATE TABLE x(op,a1,a2,delta HIDDEN)"
816 );
817 /* For convenience, define symbolic names for the index to each column. */
818 #define DELTAPARSEVTAB_OP 0
819 #define DELTAPARSEVTAB_A1 1
820 #define DELTAPARSEVTAB_A2 2
821 #define DELTAPARSEVTAB_DELTA 3
822 if( rc==SQLITE_OK ){
823 pNew = sqlite3_malloc64( sizeof(*pNew) );
824 *ppVtab = (sqlite3_vtab*)pNew;
825 if( pNew==0 ) return SQLITE_NOMEM;
826 memset(pNew, 0, sizeof(*pNew));
827 sqlite3_vtab_config(db, SQLITE_VTAB_INNOCUOUS);
828 }
829 return rc;
830 }
831
832 /*
833 ** This method is the destructor for deltaparsevtab_vtab objects.
834 */
835 static int deltaparsevtabDisconnect(sqlite3_vtab *pVtab){
836 deltaparsevtab_vtab *p = (deltaparsevtab_vtab*)pVtab;
837 sqlite3_free(p);
838 return SQLITE_OK;
839 }
840
841 /*
842 ** Constructor for a new deltaparsevtab_cursor object.
843 */
844 static int deltaparsevtabOpen(sqlite3_vtab *p, sqlite3_vtab_cursor **ppCursor){
845 deltaparsevtab_cursor *pCur;
846 pCur = sqlite3_malloc64( sizeof(*pCur) );
847 if( pCur==0 ) return SQLITE_NOMEM;
848 memset(pCur, 0, sizeof(*pCur));
849 *ppCursor = &pCur->base;
850 return SQLITE_OK;
851 }
852
853 /*
854 ** Destructor for a deltaparsevtab_cursor.
855 */
856 static int deltaparsevtabClose(sqlite3_vtab_cursor *cur){
857 deltaparsevtab_cursor *pCur = (deltaparsevtab_cursor*)cur;
858 sqlite3_free(pCur->aDelta);
859 sqlite3_free(pCur);
860 return SQLITE_OK;
861 }
862
863
864 /*
865 ** Advance a deltaparsevtab_cursor to its next row of output.
866 */
867 static int deltaparsevtabNext(sqlite3_vtab_cursor *cur){
868 deltaparsevtab_cursor *pCur = (deltaparsevtab_cursor*)cur;
869 const char *z;
870 int i = 0;
871
872 pCur->iCursor = pCur->iNext;
873 if( pCur->iCursor >= pCur->nDelta ){
874 pCur->eOp = DELTAPARSE_OP_ERROR;
875 pCur->iNext = pCur->nDelta;
876 return SQLITE_OK;
877 }
878 z = pCur->aDelta + pCur->iCursor;
879 pCur->a1 = deltaGetInt(&z, &i);
880 switch( z[0] ){
881 case '@': {
882 z++;
883 if( pCur->iNext>=pCur->nDelta ){
884 pCur->eOp = DELTAPARSE_OP_ERROR;
885 pCur->iNext = pCur->nDelta;
886 break;
887 }
888 pCur->a2 = deltaGetInt(&z, &i);
889 pCur->eOp = DELTAPARSE_OP_COPY;
890 pCur->iNext = (int)(&z[1] - pCur->aDelta);
891 break;
892 }
893 case ':': {
894 z++;
895 pCur->a2 = (unsigned int)(z - pCur->aDelta);
896 pCur->eOp = DELTAPARSE_OP_INSERT;
897 pCur->iNext = (int)(&z[pCur->a1] - pCur->aDelta);
898 break;
899 }
900 case ';': {
901 pCur->eOp = DELTAPARSE_OP_CHECKSUM;
902 pCur->iNext = pCur->nDelta;
903 break;
904 }
905 default: {
906 if( pCur->iNext==pCur->nDelta ){
907 pCur->eOp = DELTAPARSE_OP_EOF;
908 }else{
909 pCur->eOp = DELTAPARSE_OP_ERROR;
910 pCur->iNext = pCur->nDelta;
911 }
912 break;
913 }
914 }
915 return SQLITE_OK;
916 }
917
918 /*
919 ** Return values of columns for the row at which the deltaparsevtab_cursor
920 ** is currently pointing.
921 */
922 static int deltaparsevtabColumn(
923 sqlite3_vtab_cursor *cur, /* The cursor */
924 sqlite3_context *ctx, /* First argument to sqlite3_result_...() */
925 int i /* Which column to return */
926 ){
927 deltaparsevtab_cursor *pCur = (deltaparsevtab_cursor*)cur;
928 switch( i ){
929 case DELTAPARSEVTAB_OP: {
930 sqlite3_result_text(ctx, azOp[pCur->eOp], -1, SQLITE_STATIC);
931 break;
932 }
933 case DELTAPARSEVTAB_A1: {
934 sqlite3_result_int(ctx, pCur->a1);
935 break;
936 }
937 case DELTAPARSEVTAB_A2: {
938 if( pCur->eOp==DELTAPARSE_OP_COPY ){
939 sqlite3_result_int(ctx, pCur->a2);
940 }else if( pCur->eOp==DELTAPARSE_OP_INSERT ){
941 if( pCur->a2 + pCur->a1 > pCur->nDelta ){
942 sqlite3_result_zeroblob(ctx, pCur->a1);
943 }else{
944 sqlite3_result_blob(ctx, pCur->aDelta+pCur->a2, pCur->a1,
945 SQLITE_TRANSIENT);
946 }
947 }
948 break;
949 }
950 case DELTAPARSEVTAB_DELTA: {
951 sqlite3_result_blob(ctx, pCur->aDelta, pCur->nDelta, SQLITE_TRANSIENT);
952 break;
953 }
954 }
955 return SQLITE_OK;
956 }
957
958 /*
959 ** Return the rowid for the current row. In this implementation, the
960 ** rowid is the same as the output value.
961 */
962 static int deltaparsevtabRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
963 deltaparsevtab_cursor *pCur = (deltaparsevtab_cursor*)cur;
964 *pRowid = pCur->iCursor;
965 return SQLITE_OK;
966 }
967
968 /*
969 ** Return TRUE if the cursor has been moved off of the last
970 ** row of output.
971 */
972 static int deltaparsevtabEof(sqlite3_vtab_cursor *cur){
973 deltaparsevtab_cursor *pCur = (deltaparsevtab_cursor*)cur;
974 return pCur->eOp==DELTAPARSE_OP_EOF || pCur->iCursor>=pCur->nDelta;
975 }
976
977 /*
978 ** This method is called to "rewind" the deltaparsevtab_cursor object back
979 ** to the first row of output. This method is always called at least
980 ** once prior to any call to deltaparsevtabColumn() or deltaparsevtabRowid() or
981 ** deltaparsevtabEof().
982 */
983 static int deltaparsevtabFilter(
984 sqlite3_vtab_cursor *pVtabCursor,
985 int idxNum, const char *idxStr,
986 int argc, sqlite3_value **argv
987 ){
988 deltaparsevtab_cursor *pCur = (deltaparsevtab_cursor *)pVtabCursor;
989 const char *a;
990 int i = 0;
991 pCur->eOp = DELTAPARSE_OP_ERROR;
992 if( idxNum!=1 ){
993 return SQLITE_OK;
994 }
995 pCur->nDelta = sqlite3_value_bytes(argv[0]);
996 a = (const char*)sqlite3_value_blob(argv[0]);
997 if( pCur->nDelta==0 || a==0 ){
998 return SQLITE_OK;
999 }
1000 pCur->aDelta = sqlite3_malloc64( pCur->nDelta+1 );
1001 if( pCur->aDelta==0 ){
1002 pCur->nDelta = 0;
1003 return SQLITE_NOMEM;
1004 }
1005 memcpy(pCur->aDelta, a, pCur->nDelta);
1006 pCur->aDelta[pCur->nDelta] = 0;
1007 a = pCur->aDelta;
1008 pCur->eOp = DELTAPARSE_OP_SIZE;
1009 pCur->a1 = deltaGetInt(&a, &i);
1010 if( a[0]!='\n' ){
1011 pCur->eOp = DELTAPARSE_OP_ERROR;
1012 pCur->a1 = pCur->a2 = 0;
1013 pCur->iNext = pCur->nDelta;
1014 return SQLITE_OK;
1015 }
1016 a++;
1017 pCur->iNext = (unsigned int)(a - pCur->aDelta);
1018 return SQLITE_OK;
1019 }
1020
1021 /*
1022 ** SQLite will invoke this method one or more times while planning a query
1023 ** that uses the virtual table. This routine needs to create
1024 ** a query plan for each invocation and compute an estimated cost for that
1025 ** plan.
1026 */
1027 static int deltaparsevtabBestIndex(
1028 sqlite3_vtab *tab,
1029 sqlite3_index_info *pIdxInfo
1030 ){
1031 int i;
1032 for(i=0; i<pIdxInfo->nConstraint; i++){
1033 if( pIdxInfo->aConstraint[i].iColumn != DELTAPARSEVTAB_DELTA ) continue;
1034 if( pIdxInfo->aConstraint[i].usable==0 ) continue;
1035 if( pIdxInfo->aConstraint[i].op!=SQLITE_INDEX_CONSTRAINT_EQ ) continue;
1036 pIdxInfo->aConstraintUsage[i].argvIndex = 1;
1037 pIdxInfo->aConstraintUsage[i].omit = 1;
1038 pIdxInfo->estimatedCost = (double)1;
1039 pIdxInfo->estimatedRows = 10;
1040 pIdxInfo->idxNum = 1;
1041 return SQLITE_OK;
1042 }
1043 pIdxInfo->idxNum = 0;
1044 pIdxInfo->estimatedCost = (double)0x7fffffff;
1045 pIdxInfo->estimatedRows = 0x7fffffff;
1046 return SQLITE_CONSTRAINT;
1047 }
1048
1049 /*
1050 ** This following structure defines all the methods for the
1051 ** virtual table.
1052 */
1053 static sqlite3_module deltaparsevtabModule = {
1054 /* iVersion */ 0,
1055 /* xCreate */ 0,
1056 /* xConnect */ deltaparsevtabConnect,
1057 /* xBestIndex */ deltaparsevtabBestIndex,
1058 /* xDisconnect */ deltaparsevtabDisconnect,
1059 /* xDestroy */ 0,
1060 /* xOpen */ deltaparsevtabOpen,
1061 /* xClose */ deltaparsevtabClose,
1062 /* xFilter */ deltaparsevtabFilter,
1063 /* xNext */ deltaparsevtabNext,
1064 /* xEof */ deltaparsevtabEof,
1065 /* xColumn */ deltaparsevtabColumn,
1066 /* xRowid */ deltaparsevtabRowid,
1067 /* xUpdate */ 0,
1068 /* xBegin */ 0,
1069 /* xSync */ 0,
1070 /* xCommit */ 0,
1071 /* xRollback */ 0,
1072 /* xFindMethod */ 0,
1073 /* xRename */ 0,
1074 /* xSavepoint */ 0,
1075 /* xRelease */ 0,
1076 /* xRollbackTo */ 0,
1077 /* xShadowName */ 0,
1078 /* xIntegrity */ 0
1079 };
1080
1081
1082
1083 #ifdef _WIN32
1084 __declspec(dllexport)
1085 #endif
1086 int sqlite3_fossildelta_init(
1087 sqlite3 *db,
1088 char **pzErrMsg,
1089 const sqlite3_api_routines *pApi
1090 ){
1091 static const int enc = SQLITE_UTF8|SQLITE_INNOCUOUS;
1092 int rc = SQLITE_OK;
1093 SQLITE_EXTENSION_INIT2(pApi);
1094 (void)pzErrMsg; /* Unused parameter */
1095 rc = sqlite3_create_function(db, "delta_create", 2, enc, 0,
1096 deltaCreateFunc, 0, 0);
1097 if( rc==SQLITE_OK ){
1098 rc = sqlite3_create_function(db, "delta_apply", 2, enc, 0,
1099 deltaApplyFunc, 0, 0);
1100 }
1101 if( rc==SQLITE_OK ){
1102 rc = sqlite3_create_function(db, "delta_output_size", 1, enc, 0,
1103 deltaOutputSizeFunc, 0, 0);
1104 }
1105 if( rc==SQLITE_OK ){
1106 rc = sqlite3_create_module(db, "delta_parse", &deltaparsevtabModule, 0);
1107 }
1108 return rc;
1109 }