From a9ca8afef510724416d6f3cdab327024ef1f4b48 Mon Sep 17 00:00:00 2001 From: dan Date: Fri, 31 Jul 2015 19:52:03 +0000 Subject: [PATCH] Add support for "fossil deltas" to RBU and "sqldiff --rbu". FossilOrigin-Name: e26ef165fe2f7524684af0d269d38475ea8b9489 --- ext/rbu/rbudiff.test | 25 ++- ext/rbu/sqlite3rbu.c | 262 ++++++++++++++++++++++- ext/rbu/sqlite3rbu.h | 8 + manifest | 20 +- manifest.uuid | 2 +- tool/sqldiff.c | 479 ++++++++++++++++++++++++++++++++++++++++++- 6 files changed, 773 insertions(+), 23 deletions(-) diff --git a/ext/rbu/rbudiff.test b/ext/rbu/rbudiff.test index a24c1f5ce9..10be9e0d53 100644 --- a/ext/rbu/rbudiff.test +++ b/ext/rbu/rbudiff.test @@ -57,8 +57,10 @@ proc rbudiff_cksum {db1} { sqlite3 dbtmp $db1 foreach tbl [dbtmp eval {SELECT name FROM sqlite_master WHERE type='table'}] { + set cols [list] + dbtmp eval "PRAGMA table_info = $tbl" { lappend cols "quote( $name )" } append txt [dbtmp eval \ - "SELECT a || '.' || b || '.' || c FROM $tbl ORDER BY 1" + "SELECT [join $cols {||'.'||}] FROM $tbl ORDER BY 1" ] } dbtmp close @@ -94,8 +96,27 @@ foreach {tn init mod} { INSERT INTO t1 VALUES('a', 'b', 'c'); } + 3 { + CREATE TABLE t1(i INTEGER PRIMARY KEY, x); + INSERT INTO t1 VALUES(1, + X'0000000000000000111111111111111122222222222222223333333333333333' + ); + CREATE TABLE t2(y INTEGER PRIMARY KEY, x); + INSERT INTO t2 VALUES(1, + X'0000000000000000111111111111111122222222222222223333333333333333' + ); + } { + DELETE FROM t1; + INSERT INTO t1 VALUES(1, + X'0000000000000000111111111111111122222555555552223333333333333333' + ); + DELETE FROM t2; + INSERT INTO t2 VALUES(1, + X'0000000000000000111111111111111122222222222222223333333FFF333333' + ); + } + } { - catch { db close } forcedelete test.db test.db2 diff --git a/ext/rbu/sqlite3rbu.c b/ext/rbu/sqlite3rbu.c index 1598ed315e..42f7857744 100644 --- a/ext/rbu/sqlite3rbu.c +++ b/ext/rbu/sqlite3rbu.c @@ -361,6 +361,252 @@ struct rbu_file { }; +/************************************************************************* +** The following three functions, found below: +** +** rbuDeltaGetInt() +** rbuDeltaChecksum() +** rbuDeltaApply() +** +** are lifted from the fossil source code (http://fossil-scm.org). They +** are used to implement the scalar SQL function rbu_fossil_delta(). +*/ + +/* +** Read bytes from *pz and convert them into a positive integer. When +** finished, leave *pz pointing to the first character past the end of +** the integer. The *pLen parameter holds the length of the string +** in *pz and is decremented once for each character in the integer. +*/ +static unsigned int rbuDeltaGetInt(const char **pz, int *pLen){ + static const signed char zValue[] = { + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, + 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, + -1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, + 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1, -1, -1, -1, 36, + -1, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, + 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, -1, -1, -1, 63, -1, + }; + unsigned int v = 0; + int c; + unsigned char *z = (unsigned char*)*pz; + unsigned char *zStart = z; + while( (c = zValue[0x7f&*(z++)])>=0 ){ + v = (v<<6) + c; + } + z--; + *pLen -= z - zStart; + *pz = (char*)z; + return v; +} + +/* +** Compute a 32-bit checksum on the N-byte buffer. Return the result. +*/ +static unsigned int rbuDeltaChecksum(const char *zIn, size_t N){ + const unsigned char *z = (const unsigned char *)zIn; + unsigned sum0 = 0; + unsigned sum1 = 0; + unsigned sum2 = 0; + unsigned sum3 = 0; + while(N >= 16){ + sum0 += ((unsigned)z[0] + z[4] + z[8] + z[12]); + sum1 += ((unsigned)z[1] + z[5] + z[9] + z[13]); + sum2 += ((unsigned)z[2] + z[6] + z[10]+ z[14]); + sum3 += ((unsigned)z[3] + z[7] + z[11]+ z[15]); + z += 16; + N -= 16; + } + while(N >= 4){ + sum0 += z[0]; + sum1 += z[1]; + sum2 += z[2]; + sum3 += z[3]; + z += 4; + N -= 4; + } + sum3 += (sum2 << 8) + (sum1 << 16) + (sum0 << 24); + switch(N){ + case 3: sum3 += (z[2] << 8); + case 2: sum3 += (z[1] << 16); + case 1: sum3 += (z[0] << 24); + default: ; + } + return sum3; +} + +/* +** Apply a delta. +** +** The output buffer should be big enough to hold the whole output +** file and a NUL terminator at the end. The delta_output_size() +** routine will determine this size for you. +** +** The delta string should be null-terminated. But the delta string +** may contain embedded NUL characters (if the input and output are +** binary files) so we also have to pass in the length of the delta in +** the lenDelta parameter. +** +** This function returns the size of the output file in bytes (excluding +** the final NUL terminator character). Except, if the delta string is +** malformed or intended for use with a source file other than zSrc, +** then this routine returns -1. +** +** Refer to the delta_create() documentation above for a description +** of the delta file format. +*/ +static int rbuDeltaApply( + const char *zSrc, /* The source or pattern file */ + int lenSrc, /* Length of the source file */ + const char *zDelta, /* Delta to apply to the pattern */ + int lenDelta, /* Length of the delta */ + char *zOut /* Write the output into this preallocated buffer */ +){ + unsigned int limit; + unsigned int total = 0; +#ifndef FOSSIL_OMIT_DELTA_CKSUM_TEST + char *zOrigOut = zOut; +#endif + + limit = rbuDeltaGetInt(&zDelta, &lenDelta); + if( *zDelta!='\n' ){ + /* ERROR: size integer not terminated by "\n" */ + return -1; + } + zDelta++; lenDelta--; + while( *zDelta && lenDelta>0 ){ + unsigned int cnt, ofst; + cnt = rbuDeltaGetInt(&zDelta, &lenDelta); + switch( zDelta[0] ){ + case '@': { + zDelta++; lenDelta--; + ofst = rbuDeltaGetInt(&zDelta, &lenDelta); + if( lenDelta>0 && zDelta[0]!=',' ){ + /* ERROR: copy command not terminated by ',' */ + return -1; + } + zDelta++; lenDelta--; + total += cnt; + if( total>limit ){ + /* ERROR: copy exceeds output file size */ + return -1; + } + if( ofst+cnt > lenSrc ){ + /* ERROR: copy extends past end of input */ + return -1; + } + memcpy(zOut, &zSrc[ofst], cnt); + zOut += cnt; + break; + } + case ':': { + zDelta++; lenDelta--; + total += cnt; + if( total>limit ){ + /* ERROR: insert command gives an output larger than predicted */ + return -1; + } + if( cnt>lenDelta ){ + /* ERROR: insert count exceeds size of delta */ + return -1; + } + memcpy(zOut, zDelta, cnt); + zOut += cnt; + zDelta += cnt; + lenDelta -= cnt; + break; + } + case ';': { + zDelta++; lenDelta--; + zOut[0] = 0; +#ifndef FOSSIL_OMIT_DELTA_CKSUM_TEST + if( cnt!=rbuDeltaChecksum(zOrigOut, total) ){ + /* ERROR: bad checksum */ + return -1; + } +#endif + if( total!=limit ){ + /* ERROR: generated size does not match predicted size */ + return -1; + } + return total; + } + default: { + /* ERROR: unknown delta operator */ + return -1; + } + } + } + /* ERROR: unterminated delta */ + return -1; +} + +static int rbuDeltaOutputSize(const char *zDelta, int lenDelta){ + int size; + size = rbuDeltaGetInt(&zDelta, &lenDelta); + if( *zDelta!='\n' ){ + /* ERROR: size integer not terminated by "\n" */ + return -1; + } + return size; +} + +/* +** End of code taken from fossil. +*************************************************************************/ + +/* +** Implementation of SQL scalar function rbu_fossil_delta(). +** +** This function applies a fossil delta patch to a blob. Exactly two +** arguments must be passed to this function. The first is the blob to +** patch and the second the patch to apply. If no error occurs, this +** function returns the patched blob. +*/ +static void rbuFossilDeltaFunc( + sqlite3_context *context, + int argc, + sqlite3_value **argv +){ + const char *aDelta; + int nDelta; + const char *aOrig; + int nOrig; + + int nOut; + int nOut2; + char *aOut; + + assert( argc==2 ); + + nOrig = sqlite3_value_bytes(argv[0]); + aOrig = (const char*)sqlite3_value_blob(argv[0]); + nDelta = sqlite3_value_bytes(argv[1]); + aDelta = (const char*)sqlite3_value_blob(argv[1]); + + /* Figure out the size of the output */ + nOut = rbuDeltaOutputSize(aDelta, nDelta); + if( nOut<0 ){ + sqlite3_result_error(context, "corrupt fossil delta", -1); + return; + } + + aOut = sqlite3_malloc(nOut+1); + if( aOut==0 ){ + sqlite3_result_error_nomem(context); + }else{ + int nOut2 = rbuDeltaApply(aOrig, nOrig, aDelta, nDelta, aOut); + if( nOut2!=nOut ){ + sqlite3_result_error(context, "corrupt fossil delta", -1); + }else{ + sqlite3_result_blob(context, aOut, nOut, sqlite3_free); + } + } +} + + /* ** Prepare the SQL statement in buffer zSql against database handle db. ** If successful, set *ppStmt to point to the new statement and return @@ -1300,12 +1546,18 @@ static char *rbuObjIterGetSetlist( ); zSep = ", "; } - if( c=='d' ){ + else if( c=='d' ){ zList = rbuMPrintf(p, "%z%s\"%w\"=rbu_delta(\"%w\", ?%d)", zList, zSep, pIter->azTblCol[i], pIter->azTblCol[i], i+1 ); zSep = ", "; } + else if( c=='f' ){ + zList = rbuMPrintf(p, "%z%s\"%w\"=rbu_fossil_delta(\"%w\", ?%d)", + zList, zSep, pIter->azTblCol[i], pIter->azTblCol[i], i+1 + ); + zSep = ", "; + } } } } @@ -1900,6 +2152,12 @@ static void rbuOpenDatabase(sqlite3rbu *p){ ); } + if( p->rc==SQLITE_OK ){ + p->rc = sqlite3_create_function(p->dbMain, + "rbu_fossil_delta", 2, SQLITE_UTF8, 0, rbuFossilDeltaFunc, 0, 0 + ); + } + if( p->rc==SQLITE_OK ){ p->rc = sqlite3_create_function(p->dbRbu, "rbu_target_name", 1, SQLITE_UTF8, (void*)p, rbuTargetNameFunc, 0, 0 @@ -2335,7 +2593,7 @@ static int rbuStep(sqlite3rbu *p){ for(i=0; p->rc==SQLITE_OK && inCol; i++){ char c = zMask[pIter->aiSrcOrder[i]]; pVal = sqlite3_column_value(pIter->pSelect, i); - if( pIter->abTblPk[i] || c=='x' || c=='d' ){ + if( pIter->abTblPk[i] || c!='.' ){ p->rc = sqlite3_bind_value(pUpdate, i+1, pVal); } } diff --git a/ext/rbu/sqlite3rbu.h b/ext/rbu/sqlite3rbu.h index d80e182424..ca4b03dd4c 100644 --- a/ext/rbu/sqlite3rbu.h +++ b/ext/rbu/sqlite3rbu.h @@ -189,6 +189,14 @@ ** ** UPDATE t1 SET c = rbu_delta(c, 'usa') WHERE a = 4; ** +** Finally, if an 'f' character appears in place of a 'd' or 's' in an +** ota_control string, the contents of the data_xxx table column is assumed +** to be a "fossil delta" - a patch to be applied to a blob value in the +** format used by the fossil source-code management system. In this case +** the existing value within the target database table must be of type BLOB. +** It is replaced by the result of applying the specified fossil delta to +** itself. +** ** If the target database table is a virtual table or a table with no PRIMARY ** KEY, the rbu_control value should not include a character corresponding ** to the rbu_rowid value. For example, this: diff --git a/manifest b/manifest index 7232275000..4f0f96bfa7 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Fix\sthe\ssqlite3_stmt_busy()\sinterface\sso\sthat\sit\salways\sreturns\sFALSE\safter\nthe\sstatement\shas\sreturned\sSQLITE_DONE,\seven\sfor\sROLLBACK\sstatements.\nClarify\sthe\sdocumentation. -D 2015-07-31T18:59:56.800 +C Add\ssupport\sfor\s"fossil\sdeltas"\sto\sRBU\sand\s"sqldiff\s--rbu". +D 2015-07-31T19:52:03.959 F Makefile.arm-wince-mingw32ce-gcc d6df77f1f48d690bd73162294bbba7f59507c72f F Makefile.in 4de3ef40c8b3b75c0c55ff4242a43c8ce1ad90ee F Makefile.linux-gcc 91d710bdc4998cb015f39edf3cb314ec4f4d7e23 @@ -215,12 +215,12 @@ F ext/rbu/rbu8.test 3bbf2c35d71a843c463efe93946f14ad10c3ede0 F ext/rbu/rbu9.test 0806d1772c9f4981774ff028de6656e4183082af F ext/rbu/rbuA.test c1a7b3e2d926b8f8448bb3b4ae787e314ee4b2b3 F ext/rbu/rbucrash.test 8d2ed5d4b05fef6c00c2a6b5f7ead71fa172a695 -F ext/rbu/rbudiff.test fbc3aa567927ac0141d4fe2d92c182e39a7b761f +F ext/rbu/rbudiff.test 6cc806dc36389292f2a8f5842d0103721df4a07d F ext/rbu/rbufault.test cc0be8d5d392d98b0c2d6a51be377ea989250a89 F ext/rbu/rbufault2.test 9a7f19edd6ea35c4c9f807d8a3db0a03a5670c06 F ext/rbu/rbufts.test 17db7d968b3d073788bcba044c498d09e830726b -F ext/rbu/sqlite3rbu.c 75409b33f20ef6acd3689206a707de79e17a8628 -F ext/rbu/sqlite3rbu.h 67977687c3acf995295f5f461809cac030098afd +F ext/rbu/sqlite3rbu.c ffabbb80a1ea796965036e5f7c4a46fbbc86e4b2 +F ext/rbu/sqlite3rbu.h f0754a19fcc155f6d39d72b38bdbeb1d7623f02e F ext/rbu/test_rbu.c f99698956cc9158d6bf865e461e2d15876538ac1 F ext/rtree/README 6315c0d73ebf0ec40dedb5aa0e942bc8b54e3761 F ext/rtree/rtree.c 0f9b595bd0debcbedf1d7a63d0e0678d619e6c9c @@ -1357,7 +1357,7 @@ F tool/speedtest2.tcl ee2149167303ba8e95af97873c575c3e0fab58ff F tool/speedtest8.c 2902c46588c40b55661e471d7a86e4dd71a18224 F tool/speedtest8inst1.c 293327bc76823f473684d589a8160bde1f52c14e F tool/split-sqlite3c.tcl d9be87f1c340285a3e081eb19b4a247981ed290c -F tool/sqldiff.c 664fbb0e99c0feea42512aaab544b635892b1813 +F tool/sqldiff.c 4fe09e784cf2ec8b8e6ff7357b17f890ff9c78b4 F tool/stack_usage.tcl f8e71b92cdb099a147dad572375595eae55eca43 F tool/symbols-mingw.sh 4dbcea7e74768305384c9fd2ed2b41bbf9f0414d F tool/symbols.sh fec58532668296d7c7dc48be9c87f75ccdb5814f @@ -1368,7 +1368,7 @@ F tool/vdbe_profile.tcl 67746953071a9f8f2f668b73fe899074e2c6d8c1 F tool/warnings-clang.sh f6aa929dc20ef1f856af04a730772f59283631d4 F tool/warnings.sh 48bd54594752d5be3337f12c72f28d2080cb630b F tool/win/sqlite.vsix deb315d026cc8400325c5863eef847784a219a2f -P 54a771fe2c2b3c1cc2914a527a825934fe114c49 -R 719f0e876f6a610cf71ea7669afc9986 -U drh -Z a0214b099853a2b8f63fc04fdc3cf017 +P 047d3475e93d08cf172ad02404a690d5b0c1b833 +R 8e736740576f94e272a9082f5b3119dd +U dan +Z c6901fce7acc44dfc5ada7c5b1068696 diff --git a/manifest.uuid b/manifest.uuid index a679b8a3f7..47baf93de8 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -047d3475e93d08cf172ad02404a690d5b0c1b833 \ No newline at end of file +e26ef165fe2f7524684af0d269d38475ea8b9489 \ No newline at end of file diff --git a/tool/sqldiff.c b/tool/sqldiff.c index f5edd60143..82ef4ad150 100644 --- a/tool/sqldiff.c +++ b/tool/sqldiff.c @@ -23,6 +23,7 @@ #include #include #include +#include #include "sqlite3.h" /* @@ -754,6 +755,411 @@ static void checkSchemasMatch(const char *zTab){ sqlite3_finalize(pStmt); } +/************************************************************************** +** The following code is copied from fossil. It is used to generate the +** fossil delta blobs sometimes used in RBU update records. +*/ + +typedef unsigned short u16; +typedef unsigned int u32; +typedef unsigned char u8; + +/* +** The width of a hash window in bytes. The algorithm only works if this +** is a power of 2. +*/ +#define NHASH 16 + +/* +** The current state of the rolling hash. +** +** z[] holds the values that have been hashed. z[] is a circular buffer. +** z[i] is the first entry and z[(i+NHASH-1)%NHASH] is the last entry of +** the window. +** +** Hash.a is the sum of all elements of hash.z[]. Hash.b is a weighted +** sum. Hash.b is z[i]*NHASH + z[i+1]*(NHASH-1) + ... + z[i+NHASH-1]*1. +** (Each index for z[] should be module NHASH, of course. The %NHASH operator +** is omitted in the prior expression for brevity.) +*/ +typedef struct hash hash; +struct hash { + u16 a, b; /* Hash values */ + u16 i; /* Start of the hash window */ + char z[NHASH]; /* The values that have been hashed */ +}; + +/* +** Initialize the rolling hash using the first NHASH characters of z[] +*/ +static void hash_init(hash *pHash, const char *z){ + u16 a, b, i; + a = b = 0; + for(i=0; iz[i] = z[i]; + } + pHash->a = a & 0xffff; + pHash->b = b & 0xffff; + pHash->i = 0; +} + +/* +** Advance the rolling hash by a single character "c" +*/ +static void hash_next(hash *pHash, int c){ + u16 old = pHash->z[pHash->i]; + pHash->z[pHash->i] = c; + pHash->i = (pHash->i+1)&(NHASH-1); + pHash->a = pHash->a - old + c; + pHash->b = pHash->b - NHASH*old + pHash->a; +} + +/* +** Return a 32-bit hash value +*/ +static u32 hash_32bit(hash *pHash){ + return (pHash->a & 0xffff) | (((u32)(pHash->b & 0xffff))<<16); +} + +/* +** Write an base-64 integer into the given buffer. +*/ +static void putInt(unsigned int v, char **pz){ + static const char zDigits[] = + "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz~"; + /* 123456789 123456789 123456789 123456789 123456789 123456789 123 */ + int i, j; + char zBuf[20]; + if( v==0 ){ + *(*pz)++ = '0'; + return; + } + for(i=0; v>0; i++, v>>=6){ + zBuf[i] = zDigits[v&0x3f]; + } + for(j=i-1; j>=0; j--){ + *(*pz)++ = zBuf[j]; + } +} + +/* +** Read bytes from *pz and convert them into a positive integer. When +** finished, leave *pz pointing to the first character past the end of +** the integer. The *pLen parameter holds the length of the string +** in *pz and is decremented once for each character in the integer. +*/ +static unsigned int getInt(const char **pz, int *pLen){ + static const signed char zValue[] = { + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, + 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, + -1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, + 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1, -1, -1, -1, 36, + -1, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, + 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, -1, -1, -1, 63, -1, + }; + unsigned int v = 0; + int c; + unsigned char *z = (unsigned char*)*pz; + unsigned char *zStart = z; + while( (c = zValue[0x7f&*(z++)])>=0 ){ + v = (v<<6) + c; + } + z--; + *pLen -= z - zStart; + *pz = (char*)z; + return v; +} + +/* +** Return the number digits in the base-64 representation of a positive integer +*/ +static int digit_count(int v){ + unsigned int i, x; + for(i=1, x=64; v>=x; i++, x <<= 6){} + return i; +} + +/* +** Compute a 32-bit checksum on the N-byte buffer. Return the result. +*/ +static unsigned int checksum(const char *zIn, size_t N){ + const unsigned char *z = (const unsigned char *)zIn; + unsigned sum0 = 0; + unsigned sum1 = 0; + unsigned sum2 = 0; + unsigned sum3 = 0; + while(N >= 16){ + sum0 += ((unsigned)z[0] + z[4] + z[8] + z[12]); + sum1 += ((unsigned)z[1] + z[5] + z[9] + z[13]); + sum2 += ((unsigned)z[2] + z[6] + z[10]+ z[14]); + sum3 += ((unsigned)z[3] + z[7] + z[11]+ z[15]); + z += 16; + N -= 16; + } + while(N >= 4){ + sum0 += z[0]; + sum1 += z[1]; + sum2 += z[2]; + sum3 += z[3]; + z += 4; + N -= 4; + } + sum3 += (sum2 << 8) + (sum1 << 16) + (sum0 << 24); + switch(N){ + case 3: sum3 += (z[2] << 8); + case 2: sum3 += (z[1] << 16); + case 1: sum3 += (z[0] << 24); + default: ; + } + return sum3; +} + +/* +** Create a new delta. +** +** The delta is written into a preallocated buffer, zDelta, which +** should be at least 60 bytes longer than the target file, zOut. +** The delta string will be NUL-terminated, but it might also contain +** embedded NUL characters if either the zSrc or zOut files are +** binary. This function returns the length of the delta string +** in bytes, excluding the final NUL terminator character. +** +** Output Format: +** +** The delta begins with a base64 number followed by a newline. This +** number is the number of bytes in the TARGET file. Thus, given a +** delta file z, a program can compute the size of the output file +** simply by reading the first line and decoding the base-64 number +** found there. The delta_output_size() routine does exactly this. +** +** After the initial size number, the delta consists of a series of +** literal text segments and commands to copy from the SOURCE file. +** A copy command looks like this: +** +** NNN@MMM, +** +** where NNN is the number of bytes to be copied and MMM is the offset +** into the source file of the first byte (both base-64). If NNN is 0 +** it means copy the rest of the input file. Literal text is like this: +** +** NNN:TTTTT +** +** where NNN is the number of bytes of text (base-64) and TTTTT is the text. +** +** The last term is of the form +** +** NNN; +** +** In this case, NNN is a 32-bit bigendian checksum of the output file +** that can be used to verify that the delta applied correctly. All +** numbers are in base-64. +** +** Pure text files generate a pure text delta. Binary files generate a +** delta that may contain some binary data. +** +** Algorithm: +** +** The encoder first builds a hash table to help it find matching +** patterns in the source file. 16-byte chunks of the source file +** sampled at evenly spaced intervals are used to populate the hash +** table. +** +** Next we begin scanning the target file using a sliding 16-byte +** window. The hash of the 16-byte window in the target is used to +** search for a matching section in the source file. When a match +** is found, a copy command is added to the delta. An effort is +** made to extend the matching section to regions that come before +** and after the 16-byte hash window. A copy command is only issued +** if the result would use less space that just quoting the text +** literally. Literal text is added to the delta for sections that +** do not match or which can not be encoded efficiently using copy +** commands. +*/ +static int rbuDeltaCreate( + const char *zSrc, /* The source or pattern file */ + unsigned int lenSrc, /* Length of the source file */ + const char *zOut, /* The target file */ + unsigned int lenOut, /* Length of the target file */ + char *zDelta /* Write the delta into this buffer */ +){ + int i, base; + char *zOrigDelta = zDelta; + hash h; + int nHash; /* Number of hash table entries */ + int *landmark; /* Primary hash table */ + int *collide; /* Collision chain */ + int lastRead = -1; /* Last byte of zSrc read by a COPY command */ + + /* Add the target file size to the beginning of the delta + */ + putInt(lenOut, &zDelta); + *(zDelta++) = '\n'; + + /* If the source file is very small, it means that we have no + ** chance of ever doing a copy command. Just output a single + ** literal segment for the entire target and exit. + */ + if( lenSrc<=NHASH ){ + putInt(lenOut, &zDelta); + *(zDelta++) = ':'; + memcpy(zDelta, zOut, lenOut); + zDelta += lenOut; + putInt(checksum(zOut, lenOut), &zDelta); + *(zDelta++) = ';'; + return zDelta - zOrigDelta; + } + + /* Compute the hash table used to locate matching sections in the + ** source file. + */ + nHash = lenSrc/NHASH; + collide = sqlite3_malloc( nHash*2*sizeof(int) ); + landmark = &collide[nHash]; + memset(landmark, -1, nHash*sizeof(int)); + memset(collide, -1, nHash*sizeof(int)); + for(i=0; i=0 && (limit--)>0 ){ + /* + ** The hash window has identified a potential match against + ** landmark block iBlock. But we need to investigate further. + ** + ** Look for a region in zOut that matches zSrc. Anchor the search + ** at zSrc[iSrc] and zOut[base+i]. Do not include anything prior to + ** zOut[base] or after zOut[outLen] nor anything after zSrc[srcLen]. + ** + ** Set cnt equal to the length of the match and set ofst so that + ** zSrc[ofst] is the first element of the match. litsz is the number + ** of characters between zOut[base] and the beginning of the match. + ** sz will be the overhead (in bytes) needed to encode the copy + ** command. Only generate copy command if the overhead of the + ** copy command is less than the amount of literal text to be copied. + */ + int cnt, ofst, litsz; + int j, k, x, y; + int sz; + + /* Beginning at iSrc, match forwards as far as we can. j counts + ** the number of characters that match */ + iSrc = iBlock*NHASH; + for(j=0, x=iSrc, y=base+i; x=sz && cnt>bestCnt ){ + /* Remember this match only if it is the best so far and it + ** does not increase the file size */ + bestCnt = cnt; + bestOfst = iSrc-k; + bestLitsz = litsz; + } + + /* Check the next matching block */ + iBlock = collide[iBlock]; + } + + /* We have a copy command that does not cause the delta to be larger + ** than a literal insert. So add the copy command to the delta. + */ + if( bestCnt>0 ){ + if( bestLitsz>0 ){ + /* Add an insert command before the copy */ + putInt(bestLitsz,&zDelta); + *(zDelta++) = ':'; + memcpy(zDelta, &zOut[base], bestLitsz); + zDelta += bestLitsz; + base += bestLitsz; + } + base += bestCnt; + putInt(bestCnt, &zDelta); + *(zDelta++) = '@'; + putInt(bestOfst, &zDelta); + *(zDelta++) = ','; + if( bestOfst + bestCnt -1 > lastRead ){ + lastRead = bestOfst + bestCnt - 1; + } + bestCnt = 0; + break; + } + + /* If we reach this point, it means no match is found so far */ + if( base+i+NHASH>=lenOut ){ + /* We have reached the end of the file and have not found any + ** matches. Do an "insert" for everything that does not match */ + putInt(lenOut-base, &zDelta); + *(zDelta++) = ':'; + memcpy(zDelta, &zOut[base], lenOut-base); + zDelta += lenOut-base; + base = lenOut; + break; + } + + /* Advance the hash by one character. Keep looking for a match */ + hash_next(&h, zOut[base+i+NHASH]); + i++; + } + } + /* Output a final "insert" record to get all the text at the end of + ** the file that does not match anything in the source file. + */ + if( base0 ) fprintf(out, ", "); - printQuoted(out, sqlite3_column_value(pStmt, i)); + + if( sqlite3_column_type(pStmt, nCol)==SQLITE_INTEGER ){ + for(i=0; i<=nCol; i++){ + if( i>0 ) fprintf(out, ", "); + printQuoted(out, sqlite3_column_value(pStmt, i)); + } + }else{ + char *zOtaControl; + int nOtaControl = sqlite3_column_bytes(pStmt, nCol); + + zOtaControl = (char*)sqlite3_malloc(nOtaControl); + memcpy(zOtaControl, sqlite3_column_text(pStmt, nCol), nOtaControl+1); + + for(i=0; i=nPK + && sqlite3_column_type(pStmt, i)==SQLITE_BLOB + && sqlite3_column_type(pStmt, nCol+1+i)==SQLITE_BLOB + ){ + const char *aSrc = sqlite3_column_blob(pStmt, nCol+1+i); + int nSrc = sqlite3_column_bytes(pStmt, nCol+1+i); + const char *aFinal = sqlite3_column_blob(pStmt, i); + int nFinal = sqlite3_column_bytes(pStmt, i); + char *aDelta; + int nDelta; + + aDelta = sqlite3_malloc(nFinal + 60); + nDelta = rbuDeltaCreate(aSrc, nSrc, aFinal, nFinal, aDelta); + if( nDelta