1
2 /*
3 ** 2012-02-08
4 **
5 ** The author disclaims copyright to this source code. In place of
6 ** a legal notice, here is a blessing:
7 **
8 ** May you do good and not evil.
9 ** May you find forgiveness for yourself and forgive others.
10 ** May you share freely, never taking more than you give.
11 **
12 *************************************************************************
13 **
14 ** SQLite4-compatible varint implementation.
15 */
16 #include "lsmInt.h"
17
18 /*************************************************************************
19 ** The following is a copy of the varint.c module from SQLite 4.
20 */
21
22 /*
23 ** Decode the varint in z[]. Write the integer value into *pResult and
24 ** return the number of bytes in the varint.
25 */
lsmSqlite4GetVarint64(const unsigned char * z,u64 * pResult)26 static int lsmSqlite4GetVarint64(const unsigned char *z, u64 *pResult){
27 unsigned int x;
28 if( z[0]<=240 ){
29 *pResult = z[0];
30 return 1;
31 }
32 if( z[0]<=248 ){
33 *pResult = (z[0]-241)*256 + z[1] + 240;
34 return 2;
35 }
36 if( z[0]==249 ){
37 *pResult = 2288 + 256*z[1] + z[2];
38 return 3;
39 }
40 if( z[0]==250 ){
41 *pResult = (z[1]<<16) + (z[2]<<8) + z[3];
42 return 4;
43 }
44 x = (z[1]<<24) + (z[2]<<16) + (z[3]<<8) + z[4];
45 if( z[0]==251 ){
46 *pResult = x;
47 return 5;
48 }
49 if( z[0]==252 ){
50 *pResult = (((u64)x)<<8) + z[5];
51 return 6;
52 }
53 if( z[0]==253 ){
54 *pResult = (((u64)x)<<16) + (z[5]<<8) + z[6];
55 return 7;
56 }
57 if( z[0]==254 ){
58 *pResult = (((u64)x)<<24) + (z[5]<<16) + (z[6]<<8) + z[7];
59 return 8;
60 }
61 *pResult = (((u64)x)<<32) +
62 (0xffffffff & ((z[5]<<24) + (z[6]<<16) + (z[7]<<8) + z[8]));
63 return 9;
64 }
65
66 /*
67 ** Write a 32-bit unsigned integer as 4 big-endian bytes.
68 */
lsmVarintWrite32(unsigned char * z,unsigned int y)69 static void lsmVarintWrite32(unsigned char *z, unsigned int y){
70 z[0] = (unsigned char)(y>>24);
71 z[1] = (unsigned char)(y>>16);
72 z[2] = (unsigned char)(y>>8);
73 z[3] = (unsigned char)(y);
74 }
75
76 /*
77 ** Write a varint into z[]. The buffer z[] must be at least 9 characters
78 ** long to accommodate the largest possible varint. Return the number of
79 ** bytes of z[] used.
80 */
lsmSqlite4PutVarint64(unsigned char * z,u64 x)81 static int lsmSqlite4PutVarint64(unsigned char *z, u64 x){
82 unsigned int w, y;
83 if( x<=240 ){
84 z[0] = (unsigned char)x;
85 return 1;
86 }
87 if( x<=2287 ){
88 y = (unsigned int)(x - 240);
89 z[0] = (unsigned char)(y/256 + 241);
90 z[1] = (unsigned char)(y%256);
91 return 2;
92 }
93 if( x<=67823 ){
94 y = (unsigned int)(x - 2288);
95 z[0] = 249;
96 z[1] = (unsigned char)(y/256);
97 z[2] = (unsigned char)(y%256);
98 return 3;
99 }
100 y = (unsigned int)x;
101 w = (unsigned int)(x>>32);
102 if( w==0 ){
103 if( y<=16777215 ){
104 z[0] = 250;
105 z[1] = (unsigned char)(y>>16);
106 z[2] = (unsigned char)(y>>8);
107 z[3] = (unsigned char)(y);
108 return 4;
109 }
110 z[0] = 251;
111 lsmVarintWrite32(z+1, y);
112 return 5;
113 }
114 if( w<=255 ){
115 z[0] = 252;
116 z[1] = (unsigned char)w;
117 lsmVarintWrite32(z+2, y);
118 return 6;
119 }
120 if( w<=32767 ){
121 z[0] = 253;
122 z[1] = (unsigned char)(w>>8);
123 z[2] = (unsigned char)w;
124 lsmVarintWrite32(z+3, y);
125 return 7;
126 }
127 if( w<=16777215 ){
128 z[0] = 254;
129 z[1] = (unsigned char)(w>>16);
130 z[2] = (unsigned char)(w>>8);
131 z[3] = (unsigned char)w;
132 lsmVarintWrite32(z+4, y);
133 return 8;
134 }
135 z[0] = 255;
136 lsmVarintWrite32(z+1, w);
137 lsmVarintWrite32(z+5, y);
138 return 9;
139 }
140
141 /*
142 ** End of SQLite 4 code.
143 *************************************************************************/
144
lsmVarintPut64(u8 * aData,i64 iVal)145 int lsmVarintPut64(u8 *aData, i64 iVal){
146 return lsmSqlite4PutVarint64(aData, (u64)iVal);
147 }
148
lsmVarintGet64(const u8 * aData,i64 * piVal)149 int lsmVarintGet64(const u8 *aData, i64 *piVal){
150 return lsmSqlite4GetVarint64(aData, (u64 *)piVal);
151 }
152
lsmVarintPut32(u8 * aData,int iVal)153 int lsmVarintPut32(u8 *aData, int iVal){
154 return lsmSqlite4PutVarint64(aData, (u64)iVal);
155 }
156
lsmVarintGet32(u8 * z,int * piVal)157 int lsmVarintGet32(u8 *z, int *piVal){
158 u64 i;
159 int ret;
160
161 if( z[0]<=240 ){
162 *piVal = z[0];
163 return 1;
164 }
165 if( z[0]<=248 ){
166 *piVal = (z[0]-241)*256 + z[1] + 240;
167 return 2;
168 }
169 if( z[0]==249 ){
170 *piVal = 2288 + 256*z[1] + z[2];
171 return 3;
172 }
173 if( z[0]==250 ){
174 *piVal = (z[1]<<16) + (z[2]<<8) + z[3];
175 return 4;
176 }
177
178 ret = lsmSqlite4GetVarint64(z, &i);
179 *piVal = (int)i;
180 return ret;
181 }
182
lsmVarintLen32(int n)183 int lsmVarintLen32(int n){
184 u8 aData[9];
185 return lsmVarintPut32(aData, n);
186 }
187
188 /*
189 ** The argument is the first byte of a varint. This function returns the
190 ** total number of bytes in the entire varint (including the first byte).
191 */
lsmVarintSize(u8 c)192 int lsmVarintSize(u8 c){
193 if( c<241 ) return 1;
194 if( c<249 ) return 2;
195 return (int)(c - 246);
196 }
197