Fossil SCM

fossil-scm / src / deltafunc.c
Blame History Raw 530 lines
1
/*
2
** Copyright (c) 2019 D. Richard Hipp
3
**
4
** This program is free software; you can redistribute it and/or
5
** modify it under the terms of the Simplified BSD License (also
6
** known as the "2-Clause License" or "FreeBSD License".)
7
**
8
** This program is distributed in the hope that it will be useful,
9
** but without any warranty; without even the implied warranty of
10
** merchantability or fitness for a particular purpose.
11
**
12
** Author contact information:
13
** [email protected]
14
** http://www.hwaci.com/drh/
15
**
16
*******************************************************************************
17
**
18
** This module implements SQL interfaces to the delta logic. The code
19
** here is adapted from the ext/misc/fossildelta.c extension in SQLite.
20
*/
21
#include "config.h"
22
#include "deltafunc.h"
23
24
/*
25
** SQL functions: delta_create(X,Y)
26
**
27
** Return a delta that will transform X into Y.
28
*/
29
static void deltaCreateFunc(
30
sqlite3_context *context,
31
int argc,
32
sqlite3_value **argv
33
){
34
const char *aOrig; int nOrig; /* old blob */
35
const char *aNew; int nNew; /* new blob */
36
char *aOut; int nOut; /* output delta */
37
38
assert( argc==2 );
39
if( sqlite3_value_type(argv[0])==SQLITE_NULL ) return;
40
if( sqlite3_value_type(argv[1])==SQLITE_NULL ) return;
41
nOrig = sqlite3_value_bytes(argv[0]);
42
aOrig = (const char*)sqlite3_value_blob(argv[0]);
43
nNew = sqlite3_value_bytes(argv[1]);
44
aNew = (const char*)sqlite3_value_blob(argv[1]);
45
aOut = sqlite3_malloc64(nNew+70);
46
if( aOut==0 ){
47
sqlite3_result_error_nomem(context);
48
}else{
49
nOut = delta_create(aOrig, nOrig, aNew, nNew, aOut);
50
if( nOut<0 ){
51
sqlite3_free(aOut);
52
sqlite3_result_error(context, "cannot create fossil delta", -1);
53
}else{
54
sqlite3_result_blob(context, aOut, nOut, sqlite3_free);
55
}
56
}
57
}
58
59
/*
60
** SQL functions: delta_apply(X,D)
61
**
62
** Return the result of applying delta D to input X.
63
*/
64
static void deltaApplyFunc(
65
sqlite3_context *context,
66
int argc,
67
sqlite3_value **argv
68
){
69
const char *aOrig; int nOrig; /* The X input */
70
const char *aDelta; int nDelta; /* The input delta (D) */
71
char *aOut; int nOut, nOut2; /* The output */
72
73
assert( argc==2 );
74
if( sqlite3_value_type(argv[0])==SQLITE_NULL ) return;
75
if( sqlite3_value_type(argv[1])==SQLITE_NULL ) return;
76
nOrig = sqlite3_value_bytes(argv[0]);
77
aOrig = (const char*)sqlite3_value_blob(argv[0]);
78
nDelta = sqlite3_value_bytes(argv[1]);
79
aDelta = (const char*)sqlite3_value_blob(argv[1]);
80
81
/* Figure out the size of the output */
82
nOut = delta_output_size(aDelta, nDelta);
83
if( nOut<0 ){
84
sqlite3_result_error(context, "corrupt fossil delta", -1);
85
return;
86
}
87
aOut = sqlite3_malloc64((sqlite3_int64)nOut+1);
88
if( aOut==0 ){
89
sqlite3_result_error_nomem(context);
90
}else{
91
nOut2 = delta_apply(aOrig, nOrig, aDelta, nDelta, aOut);
92
if( nOut2!=nOut ){
93
sqlite3_free(aOut);
94
sqlite3_result_error(context, "corrupt fossil delta", -1);
95
}else{
96
sqlite3_result_blob(context, aOut, nOut, sqlite3_free);
97
}
98
}
99
}
100
101
102
/*
103
** SQL functions: delta_output_size(D)
104
**
105
** Return the size of the output that results from applying delta D.
106
*/
107
static void deltaOutputSizeFunc(
108
sqlite3_context *context,
109
int argc,
110
sqlite3_value **argv
111
){
112
const char *aDelta; int nDelta; /* The input delta (D) */
113
int nOut; /* Size of output */
114
assert( argc==1 );
115
if( sqlite3_value_type(argv[0])==SQLITE_NULL ) return;
116
nDelta = sqlite3_value_bytes(argv[0]);
117
aDelta = (const char*)sqlite3_value_blob(argv[0]);
118
119
/* Figure out the size of the output */
120
nOut = delta_output_size(aDelta, nDelta);
121
if( nOut<0 ){
122
sqlite3_result_error(context, "corrupt fossil delta", -1);
123
return;
124
}else{
125
sqlite3_result_int(context, nOut);
126
}
127
}
128
129
/*****************************************************************************
130
** Table-valued SQL function: delta_parse(DELTA)
131
**
132
** Schema:
133
**
134
** CREATE TABLE delta_parse(
135
** op TEXT,
136
** a1 INT,
137
** a2 ANY,
138
** delta HIDDEN BLOB
139
** );
140
**
141
** Given an input DELTA, this function parses the delta and returns
142
** rows for each entry in the delta. The op column has one of the
143
** values SIZE, COPY, INSERT, CHECKSUM, ERROR.
144
**
145
** Assuming no errors, the first row has op='SIZE'. a1 is the size of
146
** the output in bytes and a2 is NULL.
147
**
148
** After the initial SIZE row, there are zero or more 'COPY' and/or 'INSERT'
149
** rows. A COPY row means content is copied from the source into the
150
** output. Column a1 is the number of bytes to copy and a2 is the offset
151
** into source from which to begin copying. An INSERT row means to
152
** insert text into the output stream. Column a1 is the number of bytes
153
** to insert and column is a BLOB that contains the text to be inserted.
154
**
155
** The last row of a well-formed delta will have an op value of 'CHECKSUM'.
156
** The a1 column will be the value of the checksum and a2 will be NULL.
157
**
158
** If the input delta is not well-formed, then a row with an op value
159
** of 'ERROR' is returned. The a1 value of the ERROR row is the offset
160
** into the delta where the error was encountered and a2 is NULL.
161
*/
162
typedef struct deltaparsevtab_vtab deltaparsevtab_vtab;
163
typedef struct deltaparsevtab_cursor deltaparsevtab_cursor;
164
struct deltaparsevtab_vtab {
165
sqlite3_vtab base; /* Base class - must be first */
166
/* No additional information needed */
167
};
168
struct deltaparsevtab_cursor {
169
sqlite3_vtab_cursor base; /* Base class - must be first */
170
char *aDelta; /* The delta being parsed */
171
int nDelta; /* Number of bytes in the delta */
172
int iCursor; /* Current cursor location */
173
int eOp; /* Name of current operator */
174
unsigned int a1, a2; /* Arguments to current operator */
175
int iNext; /* Next cursor value */
176
};
177
178
/* Operator names:
179
*/
180
static const char *const azOp[] = {
181
"SIZE", "COPY", "INSERT", "CHECKSUM", "ERROR", "EOF"
182
};
183
#define DELTAPARSE_OP_SIZE 0
184
#define DELTAPARSE_OP_COPY 1
185
#define DELTAPARSE_OP_INSERT 2
186
#define DELTAPARSE_OP_CHECKSUM 3
187
#define DELTAPARSE_OP_ERROR 4
188
#define DELTAPARSE_OP_EOF 5
189
190
/*
191
** Read bytes from *pz and convert them into a positive integer. When
192
** finished, leave *pz pointing to the first character past the end of
193
** the integer. The *pLen parameter holds the length of the string
194
** in *pz and is decremented once for each character in the integer.
195
*/
196
static unsigned int deltaGetInt(const char **pz, int *pLen){
197
static const signed char zValue[] = {
198
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
199
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
200
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
201
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1,
202
-1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
203
25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1, -1, -1, -1, 36,
204
-1, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51,
205
52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, -1, -1, -1, 63, -1,
206
};
207
unsigned int v = 0;
208
int c;
209
unsigned char *z = (unsigned char*)*pz;
210
unsigned char *zStart = z;
211
while( (c = zValue[0x7f&*(z++)])>=0 ){
212
v = (v<<6) + c;
213
}
214
z--;
215
*pLen -= z - zStart;
216
*pz = (char*)z;
217
return v;
218
}
219
220
/*
221
** The deltaparsevtabConnect() method is invoked to create a new
222
** deltaparse virtual table.
223
**
224
** Think of this routine as the constructor for deltaparsevtab_vtab objects.
225
**
226
** All this routine needs to do is:
227
**
228
** (1) Allocate the deltaparsevtab_vtab object and initialize all fields.
229
**
230
** (2) Tell SQLite (via the sqlite3_declare_vtab() interface) what the
231
** result set of queries against the virtual table will look like.
232
*/
233
static int deltaparsevtabConnect(
234
sqlite3 *db,
235
void *pAux,
236
int argc, const char *const*argv,
237
sqlite3_vtab **ppVtab,
238
char **pzErr
239
){
240
deltaparsevtab_vtab *pNew;
241
int rc;
242
243
rc = sqlite3_declare_vtab(db,
244
"CREATE TABLE x(op,a1,a2,delta HIDDEN)"
245
);
246
/* For convenience, define symbolic names for the index to each column. */
247
#define DELTAPARSEVTAB_OP 0
248
#define DELTAPARSEVTAB_A1 1
249
#define DELTAPARSEVTAB_A2 2
250
#define DELTAPARSEVTAB_DELTA 3
251
if( rc==SQLITE_OK ){
252
pNew = sqlite3_malloc64( sizeof(*pNew) );
253
*ppVtab = (sqlite3_vtab*)pNew;
254
if( pNew==0 ) return SQLITE_NOMEM;
255
memset(pNew, 0, sizeof(*pNew));
256
sqlite3_vtab_config(db, SQLITE_VTAB_INNOCUOUS);
257
}
258
return rc;
259
}
260
261
/*
262
** This method is the destructor for deltaparsevtab_vtab objects.
263
*/
264
static int deltaparsevtabDisconnect(sqlite3_vtab *pVtab){
265
deltaparsevtab_vtab *p = (deltaparsevtab_vtab*)pVtab;
266
sqlite3_free(p);
267
return SQLITE_OK;
268
}
269
270
/*
271
** Constructor for a new deltaparsevtab_cursor object.
272
*/
273
static int deltaparsevtabOpen(sqlite3_vtab *p, sqlite3_vtab_cursor **ppCursor){
274
deltaparsevtab_cursor *pCur;
275
pCur = sqlite3_malloc( sizeof(*pCur) );
276
if( pCur==0 ) return SQLITE_NOMEM;
277
memset(pCur, 0, sizeof(*pCur));
278
*ppCursor = &pCur->base;
279
return SQLITE_OK;
280
}
281
282
/*
283
** Destructor for a deltaparsevtab_cursor.
284
*/
285
static int deltaparsevtabClose(sqlite3_vtab_cursor *cur){
286
deltaparsevtab_cursor *pCur = (deltaparsevtab_cursor*)cur;
287
sqlite3_free(pCur->aDelta);
288
sqlite3_free(pCur);
289
return SQLITE_OK;
290
}
291
292
293
/*
294
** Advance a deltaparsevtab_cursor to its next row of output.
295
*/
296
static int deltaparsevtabNext(sqlite3_vtab_cursor *cur){
297
deltaparsevtab_cursor *pCur = (deltaparsevtab_cursor*)cur;
298
const char *z;
299
int i = 0;
300
301
pCur->iCursor = pCur->iNext;
302
if( pCur->iCursor >= pCur->nDelta ){
303
pCur->eOp = DELTAPARSE_OP_ERROR;
304
pCur->iNext = pCur->nDelta;
305
return SQLITE_OK;
306
}
307
z = pCur->aDelta + pCur->iCursor;
308
pCur->a1 = deltaGetInt(&z, &i);
309
switch( z[0] ){
310
case '@': {
311
z++;
312
if( pCur->iNext>=pCur->nDelta ){
313
pCur->eOp = DELTAPARSE_OP_ERROR;
314
pCur->iNext = pCur->nDelta;
315
break;
316
}
317
pCur->a2 = deltaGetInt(&z, &i);
318
pCur->eOp = DELTAPARSE_OP_COPY;
319
pCur->iNext = (int)(&z[1] - pCur->aDelta);
320
break;
321
}
322
case ':': {
323
z++;
324
pCur->a2 = (unsigned int)(z - pCur->aDelta);
325
pCur->eOp = DELTAPARSE_OP_INSERT;
326
pCur->iNext = (int)(&z[pCur->a1] - pCur->aDelta);
327
break;
328
}
329
case ';': {
330
pCur->eOp = DELTAPARSE_OP_CHECKSUM;
331
pCur->iNext = pCur->nDelta;
332
break;
333
}
334
default: {
335
if( pCur->iNext==pCur->nDelta ){
336
pCur->eOp = DELTAPARSE_OP_EOF;
337
}else{
338
pCur->eOp = DELTAPARSE_OP_ERROR;
339
pCur->iNext = pCur->nDelta;
340
}
341
break;
342
}
343
}
344
return SQLITE_OK;
345
}
346
347
/*
348
** Return values of columns for the row at which the deltaparsevtab_cursor
349
** is currently pointing.
350
*/
351
static int deltaparsevtabColumn(
352
sqlite3_vtab_cursor *cur, /* The cursor */
353
sqlite3_context *ctx, /* First argument to sqlite3_result_...() */
354
int i /* Which column to return */
355
){
356
deltaparsevtab_cursor *pCur = (deltaparsevtab_cursor*)cur;
357
switch( i ){
358
case DELTAPARSEVTAB_OP: {
359
sqlite3_result_text(ctx, azOp[pCur->eOp], -1, SQLITE_STATIC);
360
break;
361
}
362
case DELTAPARSEVTAB_A1: {
363
sqlite3_result_int(ctx, pCur->a1);
364
break;
365
}
366
case DELTAPARSEVTAB_A2: {
367
if( pCur->eOp==DELTAPARSE_OP_COPY ){
368
sqlite3_result_int(ctx, pCur->a2);
369
}else if( pCur->eOp==DELTAPARSE_OP_INSERT ){
370
if( pCur->a2 + pCur->a1 > pCur->nDelta ){
371
sqlite3_result_zeroblob(ctx, pCur->a1);
372
}else{
373
sqlite3_result_blob(ctx, pCur->aDelta+pCur->a2, pCur->a1,
374
SQLITE_TRANSIENT);
375
}
376
}
377
break;
378
}
379
case DELTAPARSEVTAB_DELTA: {
380
sqlite3_result_blob(ctx, pCur->aDelta, pCur->nDelta, SQLITE_TRANSIENT);
381
break;
382
}
383
}
384
return SQLITE_OK;
385
}
386
387
/*
388
** Return the rowid for the current row. In this implementation, the
389
** rowid is the same as the output value.
390
*/
391
static int deltaparsevtabRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){
392
deltaparsevtab_cursor *pCur = (deltaparsevtab_cursor*)cur;
393
*pRowid = pCur->iCursor;
394
return SQLITE_OK;
395
}
396
397
/*
398
** Return TRUE if the cursor has been moved off of the last
399
** row of output.
400
*/
401
static int deltaparsevtabEof(sqlite3_vtab_cursor *cur){
402
deltaparsevtab_cursor *pCur = (deltaparsevtab_cursor*)cur;
403
return pCur->eOp==DELTAPARSE_OP_EOF || pCur->iCursor>=pCur->nDelta;
404
}
405
406
/*
407
** This method is called to "rewind" the deltaparsevtab_cursor object back
408
** to the first row of output. This method is always called at least
409
** once prior to any call to deltaparsevtabColumn() or deltaparsevtabRowid() or
410
** deltaparsevtabEof().
411
*/
412
static int deltaparsevtabFilter(
413
sqlite3_vtab_cursor *pVtabCursor,
414
int idxNum, const char *idxStr,
415
int argc, sqlite3_value **argv
416
){
417
deltaparsevtab_cursor *pCur = (deltaparsevtab_cursor *)pVtabCursor;
418
const char *a;
419
int i = 0;
420
pCur->eOp = DELTAPARSE_OP_ERROR;
421
if( idxNum!=1 ){
422
return SQLITE_OK;
423
}
424
pCur->nDelta = sqlite3_value_bytes(argv[0]);
425
a = (const char*)sqlite3_value_blob(argv[0]);
426
if( pCur->nDelta==0 || a==0 ){
427
return SQLITE_OK;
428
}
429
pCur->aDelta = sqlite3_malloc64( pCur->nDelta+1 );
430
if( pCur->aDelta==0 ){
431
pCur->nDelta = 0;
432
return SQLITE_NOMEM;
433
}
434
memcpy(pCur->aDelta, a, pCur->nDelta);
435
pCur->aDelta[pCur->nDelta] = 0;
436
a = pCur->aDelta;
437
pCur->eOp = DELTAPARSE_OP_SIZE;
438
pCur->a1 = deltaGetInt(&a, &i);
439
if( a[0]!='\n' ){
440
pCur->eOp = DELTAPARSE_OP_ERROR;
441
pCur->a1 = pCur->a2 = 0;
442
pCur->iNext = pCur->nDelta;
443
return SQLITE_OK;
444
}
445
a++;
446
pCur->iNext = (unsigned int)(a - pCur->aDelta);
447
return SQLITE_OK;
448
}
449
450
/*
451
** SQLite will invoke this method one or more times while planning a query
452
** that uses the virtual table. This routine needs to create
453
** a query plan for each invocation and compute an estimated cost for that
454
** plan.
455
*/
456
static int deltaparsevtabBestIndex(
457
sqlite3_vtab *tab,
458
sqlite3_index_info *pIdxInfo
459
){
460
int i;
461
for(i=0; i<pIdxInfo->nConstraint; i++){
462
if( pIdxInfo->aConstraint[i].iColumn != DELTAPARSEVTAB_DELTA ) continue;
463
if( pIdxInfo->aConstraint[i].usable==0 ) continue;
464
if( pIdxInfo->aConstraint[i].op!=SQLITE_INDEX_CONSTRAINT_EQ ) continue;
465
pIdxInfo->aConstraintUsage[i].argvIndex = 1;
466
pIdxInfo->aConstraintUsage[i].omit = 1;
467
pIdxInfo->estimatedCost = (double)1;
468
pIdxInfo->estimatedRows = 10;
469
pIdxInfo->idxNum = 1;
470
return SQLITE_OK;
471
}
472
pIdxInfo->idxNum = 0;
473
pIdxInfo->estimatedCost = (double)0x7fffffff;
474
pIdxInfo->estimatedRows = 0x7fffffff;
475
return SQLITE_CONSTRAINT;
476
}
477
478
/*
479
** This following structure defines all the methods for the
480
** virtual table.
481
*/
482
static sqlite3_module deltaparsevtabModule = {
483
/* iVersion */ 0,
484
/* xCreate */ 0,
485
/* xConnect */ deltaparsevtabConnect,
486
/* xBestIndex */ deltaparsevtabBestIndex,
487
/* xDisconnect */ deltaparsevtabDisconnect,
488
/* xDestroy */ 0,
489
/* xOpen */ deltaparsevtabOpen,
490
/* xClose */ deltaparsevtabClose,
491
/* xFilter */ deltaparsevtabFilter,
492
/* xNext */ deltaparsevtabNext,
493
/* xEof */ deltaparsevtabEof,
494
/* xColumn */ deltaparsevtabColumn,
495
/* xRowid */ deltaparsevtabRowid,
496
/* xUpdate */ 0,
497
/* xBegin */ 0,
498
/* xSync */ 0,
499
/* xCommit */ 0,
500
/* xRollback */ 0,
501
/* xFindMethod */ 0,
502
/* xRename */ 0,
503
/* xSavepoint */ 0,
504
/* xRelease */ 0,
505
/* xRollbackTo */ 0,
506
/* xShadowName */ 0,
507
/* xIntegrity */ 0
508
};
509
510
/*
511
** Invoke this routine to register the various delta functions.
512
*/
513
int deltafunc_init(sqlite3 *db){
514
int rc = SQLITE_OK;
515
rc = sqlite3_create_function(db, "delta_create", 2, SQLITE_UTF8, 0,
516
deltaCreateFunc, 0, 0);
517
if( rc==SQLITE_OK ){
518
rc = sqlite3_create_function(db, "delta_apply", 2, SQLITE_UTF8, 0,
519
deltaApplyFunc, 0, 0);
520
}
521
if( rc==SQLITE_OK ){
522
rc = sqlite3_create_function(db, "delta_output_size", 1, SQLITE_UTF8, 0,
523
deltaOutputSizeFunc, 0, 0);
524
}
525
if( rc==SQLITE_OK ){
526
rc = sqlite3_create_module(db, "delta_parse", &deltaparsevtabModule, 0);
527
}
528
return rc;
529
}
530

Keyboard Shortcuts

Open search /
Next entry (timeline) j
Previous entry (timeline) k
Open focused entry Enter
Show this help ?
Toggle theme Top nav button