Update changelog
[joel/debian/python-sqlite.git] / encode.c
1 /*
2 ** 2002 April 25
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 ** This file contains helper routines used to translate binary data into
13 ** a null-terminated string (suitable for use in SQLite) and back again.
14 ** These are convenience routines for use by people who want to store binary
15 ** data in an SQLite database.  The code in this file is not used by any other
16 ** part of the SQLite library.
17 **
18 ** $Id: encode.c,v 1.2 2004/07/03 22:51:18 ghaering Exp $
19 */
20 #include <string.h>
21
22 /*
23 ** How This Encoder Works
24 **
25 ** The output is allowed to contain any character except 0x27 (') and
26 ** 0x00.  This is accomplished by using an escape character to encode
27 ** 0x27 and 0x00 as a two-byte sequence.  The escape character is always
28 ** 0x01.  An 0x00 is encoded as the two byte sequence 0x01 0x01.  The
29 ** 0x27 character is encoded as the two byte sequence 0x01 0x03.  Finally,
30 ** the escape character itself is encoded as the two-character sequence
31 ** 0x01 0x02.
32 **
33 ** To summarize, the encoder works by using an escape sequences as follows:
34 **
35 **       0x00  ->  0x01 0x01
36 **       0x01  ->  0x01 0x02
37 **       0x27  ->  0x01 0x03
38 **
39 ** If that were all the encoder did, it would work, but in certain cases
40 ** it could double the size of the encoded string.  For example, to
41 ** encode a string of 100 0x27 characters would require 100 instances of
42 ** the 0x01 0x03 escape sequence resulting in a 200-character output.
43 ** We would prefer to keep the size of the encoded string smaller than
44 ** this.
45 **
46 ** To minimize the encoding size, we first add a fixed offset value to each 
47 ** byte in the sequence.  The addition is modulo 256.  (That is to say, if
48 ** the sum of the original character value and the offset exceeds 256, then
49 ** the higher order bits are truncated.)  The offset is chosen to minimize
50 ** the number of characters in the string that need to be escaped.  For
51 ** example, in the case above where the string was composed of 100 0x27
52 ** characters, the offset might be 0x01.  Each of the 0x27 characters would
53 ** then be converted into an 0x28 character which would not need to be
54 ** escaped at all and so the 100 character input string would be converted
55 ** into just 100 characters of output.  Actually 101 characters of output - 
56 ** we have to record the offset used as the first byte in the sequence so
57 ** that the string can be decoded.  Since the offset value is stored as
58 ** part of the output string and the output string is not allowed to contain
59 ** characters 0x00 or 0x27, the offset cannot be 0x00 or 0x27.
60 **
61 ** Here, then, are the encoding steps:
62 **
63 **     (1)   Choose an offset value and make it the first character of
64 **           output.
65 **
66 **     (2)   Copy each input character into the output buffer, one by
67 **           one, adding the offset value as you copy.
68 **
69 **     (3)   If the value of an input character plus offset is 0x00, replace
70 **           that one character by the two-character sequence 0x01 0x01.
71 **           If the sum is 0x01, replace it with 0x01 0x02.  If the sum
72 **           is 0x27, replace it with 0x01 0x03.
73 **
74 **     (4)   Put a 0x00 terminator at the end of the output.
75 **
76 ** Decoding is obvious:
77 **
78 **     (5)   Copy encoded characters except the first into the decode 
79 **           buffer.  Set the first encoded character aside for use as
80 **           the offset in step 7 below.
81 **
82 **     (6)   Convert each 0x01 0x01 sequence into a single character 0x00.
83 **           Convert 0x01 0x02 into 0x01.  Convert 0x01 0x03 into 0x27.
84 **
85 **     (7)   Subtract the offset value that was the first character of
86 **           the encoded buffer from all characters in the output buffer.
87 **
88 ** The only tricky part is step (1) - how to compute an offset value to
89 ** minimize the size of the output buffer.  This is accomplished by testing
90 ** all offset values and picking the one that results in the fewest number
91 ** of escapes.  To do that, we first scan the entire input and count the
92 ** number of occurances of each character value in the input.  Suppose
93 ** the number of 0x00 characters is N(0), the number of occurances of 0x01
94 ** is N(1), and so forth up to the number of occurances of 0xff is N(255).
95 ** An offset of 0 is not allowed so we don't have to test it.  The number
96 ** of escapes required for an offset of 1 is N(1)+N(2)+N(40).  The number
97 ** of escapes required for an offset of 2 is N(2)+N(3)+N(41).  And so forth.
98 ** In this way we find the offset that gives the minimum number of escapes,
99 ** and thus minimizes the length of the output string.
100 */
101
102 /*
103 ** Encode a binary buffer "in" of size n bytes so that it contains
104 ** no instances of characters '\'' or '\000'.  The output is 
105 ** null-terminated and can be used as a string value in an INSERT
106 ** or UPDATE statement.  Use sqlite_decode_binary() to convert the
107 ** string back into its original binary.
108 **
109 ** The result is written into a preallocated output buffer "out".
110 ** "out" must be able to hold at least 2 +(257*n)/254 bytes.
111 ** In other words, the output will be expanded by as much as 3
112 ** bytes for every 254 bytes of input plus 2 bytes of fixed overhead.
113 ** (This is approximately 2 + 1.0118*n or about a 1.2% size increase.)
114 **
115 ** The return value is the number of characters in the encoded
116 ** string, excluding the "\000" terminator.
117 */
118 int sqlite_encode_binary(const unsigned char *in, int n, unsigned char *out){
119   int i, j, e = 0, m;
120   int cnt[256];
121   if( n<=0 ){
122     out[0] = 'x';
123     out[1] = 0;
124     return 1;
125   }
126   memset(cnt, 0, sizeof(cnt));
127   for(i=n-1; i>=0; i--){ cnt[in[i]]++; }
128   m = n;
129   for(i=1; i<256; i++){
130     int sum;
131     if( i=='\'' ) continue;
132     sum = cnt[i] + cnt[(i+1)&0xff] + cnt[(i+'\'')&0xff];
133     if( sum<m ){
134       m = sum;
135       e = i;
136       if( m==0 ) break;
137     }
138   }
139   out[0] = e;
140   j = 1;
141   for(i=0; i<n; i++){
142     int c = (in[i] - e)&0xff;
143     if( c==0 ){
144       out[j++] = 1;
145       out[j++] = 1;
146     }else if( c==1 ){
147       out[j++] = 1;
148       out[j++] = 2;
149     }else if( c=='\'' ){
150       out[j++] = 1;
151       out[j++] = 3;
152     }else{
153       out[j++] = c;
154     }
155   }
156   out[j] = 0;
157   return j;
158 }
159
160 /*
161 ** Decode the string "in" into binary data and write it into "out".
162 ** This routine reverses the encoding created by sqlite_encode_binary().
163 ** The output will always be a few bytes less than the input.  The number
164 ** of bytes of output is returned.  If the input is not a well-formed
165 ** encoding, -1 is returned.
166 **
167 ** The "in" and "out" parameters may point to the same buffer in order
168 ** to decode a string in place.
169 */
170 int sqlite_decode_binary(const unsigned char *in, unsigned char *out){
171   int i, c, e;
172   e = *(in++);
173   i = 0;
174   while( (c = *(in++))!=0 ){
175     if( c==1 ){
176       c = *(in++);
177       if( c==1 ){
178         c = 0;
179       }else if( c==2 ){
180         c = 1;
181       }else if( c==3 ){
182         c = '\'';
183       }else{
184         return -1;
185       }
186     }
187     out[i++] = (c + e)&0xff;
188   }
189   return i;
190 }
191
192 #ifdef ENCODER_TEST
193 /*
194 ** The subroutines above are not tested by the usual test suite.  To test
195 ** these routines, compile just this one file with a -DENCODER_TEST=1 option
196 ** and run the result.
197 */
198 int main(int argc, char **argv){
199   int i, j, n, m, nOut;
200   unsigned char in[30000];
201   unsigned char out[33000];
202
203   for(i=0; i<sizeof(in); i++){
204     printf("Test %d: ", i+1);
205     n = rand() % (i+1);
206     if( i%100==0 ){
207       int k;
208       for(j=k=0; j<n; j++){
209         /* if( k==0 || k=='\'' ) k++; */
210         in[j] = k;
211         k = (k+1)&0xff;
212       }
213     }else{
214       for(j=0; j<n; j++) in[j] = rand() & 0xff;
215     }
216     nOut = sqlite_encode_binary(in, n, out);
217     if( nOut!=strlen(out) ){
218       printf(" ERROR return value is %d instead of %d\n", nOut, strlen(out));
219       exit(1);
220     }
221     m = (256*n + 1262)/253;
222     printf("size %d->%d (max %d)", n, strlen(out)+1, m);
223     if( strlen(out)+1>m ){
224       printf(" ERROR output too big\n");
225       exit(1);
226     }
227     for(j=0; out[j]; j++){
228       if( out[j]=='\'' ){
229         printf(" ERROR contains (')\n");
230         exit(1);
231       }
232     }
233     j = sqlite_decode_binary(out, out);
234     if( j!=n ){
235       printf(" ERROR decode size %d\n", j);
236       exit(1);
237     }
238     if( memcmp(in, out, n)!=0 ){
239       printf(" ERROR decode mismatch\n");
240       exit(1);
241     }
242     printf(" OK\n");
243   }
244 }
245 #endif /* ENCODER_TEST */