1 7a4ee46d 2003-11-23 devnull #include "stdinc.h"
2 7a4ee46d 2003-11-23 devnull #include "whack.h"
4 7a4ee46d 2003-11-23 devnull typedef struct Huff Huff;
8 7a4ee46d 2003-11-23 devnull MaxFastLen = 9,
9 7a4ee46d 2003-11-23 devnull BigLenCode = 0x1f4, /* minimum code for large lenth encoding */
10 7a4ee46d 2003-11-23 devnull BigLenBits = 9,
11 7a4ee46d 2003-11-23 devnull BigLenBase = 4, /* starting items to encode for big lens */
13 7a4ee46d 2003-11-23 devnull MinOffBits = 6,
14 7a4ee46d 2003-11-23 devnull MaxOffBits = MinOffBits + 8,
16 7a4ee46d 2003-11-23 devnull MaxLen = 2051 /* max. length encodable in 24 bits */
21 7a4ee46d 2003-11-23 devnull StatBytes,
22 7a4ee46d 2003-11-23 devnull StatOutBytes,
23 7a4ee46d 2003-11-23 devnull StatLits,
24 7a4ee46d 2003-11-23 devnull StatMatches,
25 7a4ee46d 2003-11-23 devnull StatLitBits,
26 7a4ee46d 2003-11-23 devnull StatOffBits,
27 7a4ee46d 2003-11-23 devnull StatLenBits,
32 7a4ee46d 2003-11-23 devnull struct Huff
34 7a4ee46d 2003-11-23 devnull short bits; /* length of the code */
35 7a4ee46d 2003-11-23 devnull ulong encode; /* the code */
38 7a4ee46d 2003-11-23 devnull static Huff lentab[MaxFastLen] =
40 7a4ee46d 2003-11-23 devnull {2, 0x2}, /* 10 */
41 7a4ee46d 2003-11-23 devnull {3, 0x6}, /* 110 */
42 7a4ee46d 2003-11-23 devnull {5, 0x1c}, /* 11100 */
43 7a4ee46d 2003-11-23 devnull {5, 0x1d}, /* 11101 */
44 7a4ee46d 2003-11-23 devnull {6, 0x3c}, /* 111100 */
45 7a4ee46d 2003-11-23 devnull {7, 0x7a}, /* 1111010 */
46 7a4ee46d 2003-11-23 devnull {7, 0x7b}, /* 1111011 */
47 7a4ee46d 2003-11-23 devnull {8, 0xf8}, /* 11111000 */
48 7a4ee46d 2003-11-23 devnull {8, 0xf9}, /* 11111001 */
51 7a4ee46d 2003-11-23 devnull static int thwmaxcheck;
54 7a4ee46d 2003-11-23 devnull whackinit(Whack *tw, int level)
56 7a4ee46d 2003-11-23 devnull thwmaxcheck = (1 << level);
57 7a4ee46d 2003-11-23 devnull thwmaxcheck -= thwmaxcheck >> 2;
58 7a4ee46d 2003-11-23 devnull if(thwmaxcheck < 2)
59 7a4ee46d 2003-11-23 devnull thwmaxcheck = 2;
60 7a4ee46d 2003-11-23 devnull else if(thwmaxcheck > 1024)
61 7a4ee46d 2003-11-23 devnull thwmaxcheck = 1024;
62 7a4ee46d 2003-11-23 devnull memset(tw, 0, sizeof *tw);
63 7a4ee46d 2003-11-23 devnull tw->begin = 2 * WhackMaxOff;
67 7a4ee46d 2003-11-23 devnull * find a string in the dictionary
69 7a4ee46d 2003-11-23 devnull static int
70 7a4ee46d 2003-11-23 devnull whackmatch(Whack *b, uchar **ss, uchar *esrc, ulong h, ulong now)
72 7a4ee46d 2003-11-23 devnull ushort then, off, last;
73 7a4ee46d 2003-11-23 devnull int bestoff, bestlen, check;
74 7a4ee46d 2003-11-23 devnull uchar *s, *t;
77 7a4ee46d 2003-11-23 devnull if(esrc < s + MinMatch)
78 7a4ee46d 2003-11-23 devnull return -1;
79 7a4ee46d 2003-11-23 devnull if(s + MaxLen < esrc)
80 7a4ee46d 2003-11-23 devnull esrc = s + MaxLen;
82 7a4ee46d 2003-11-23 devnull bestoff = 0;
83 7a4ee46d 2003-11-23 devnull bestlen = 0;
84 7a4ee46d 2003-11-23 devnull check = thwmaxcheck;
85 7a4ee46d 2003-11-23 devnull last = 0;
86 7a4ee46d 2003-11-23 devnull for(then = b->hash[h]; check-- > 0; then = b->next[then & (WhackMaxOff - 1)]){
87 7a4ee46d 2003-11-23 devnull off = now - then;
88 7a4ee46d 2003-11-23 devnull if(off <= last || off > WhackMaxOff)
92 7a4ee46d 2003-11-23 devnull * don't need to check for the end because
93 7a4ee46d 2003-11-23 devnull * 1) s too close check above
95 7a4ee46d 2003-11-23 devnull t = s - off;
96 7a4ee46d 2003-11-23 devnull if(s[0] == t[0] && s[1] == t[1] && s[2] == t[2]){
97 7a4ee46d 2003-11-23 devnull if(!bestlen || esrc - s > bestlen && s[bestlen] == t[bestlen]){
99 7a4ee46d 2003-11-23 devnull for(s += 3; s < esrc; s++){
100 7a4ee46d 2003-11-23 devnull if(*s != *t)
104 7a4ee46d 2003-11-23 devnull if(s - *ss > bestlen){
105 7a4ee46d 2003-11-23 devnull bestlen = s - *ss;
106 7a4ee46d 2003-11-23 devnull bestoff = off;
107 7a4ee46d 2003-11-23 devnull if(bestlen > thwmaxcheck)
112 7a4ee46d 2003-11-23 devnull s = *ss;
113 7a4ee46d 2003-11-23 devnull last = off;
115 7a4ee46d 2003-11-23 devnull *ss += bestlen;
116 7a4ee46d 2003-11-23 devnull return bestoff;
120 7a4ee46d 2003-11-23 devnull * knuth vol. 3 multiplicative hashing
121 7a4ee46d 2003-11-23 devnull * each byte x chosen according to rules
122 7a4ee46d 2003-11-23 devnull * 1/4 < x < 3/10, 1/3 x < < 3/7, 4/7 < x < 2/3, 7/10 < x < 3/4
123 7a4ee46d 2003-11-23 devnull * with reasonable spread between the bytes & their complements
125 7a4ee46d 2003-11-23 devnull * the 3 byte value appears to be as almost good as the 4 byte value,
126 7a4ee46d 2003-11-23 devnull * and might be faster on some machines
129 7a4ee46d 2003-11-23 devnull #define hashit(c) ((((ulong)(c) * 0x6b43a9) >> (24 - HashLog)) & HashMask)
131 7a4ee46d 2003-11-23 devnull #define hashit(c) (((((ulong)(c) & 0xffffff) * 0x6b43a9b5) >> (32 - HashLog)) & HashMask)
134 7a4ee46d 2003-11-23 devnull * lz77 compression with single lookup in a hash table for each block
137 7a4ee46d 2003-11-23 devnull whack(Whack *w, uchar *dst, uchar *src, int n, ulong stats[WhackStats])
139 7a4ee46d 2003-11-23 devnull uchar *s, *ss, *sss, *esrc, *half, *wdst, *wdmax;
140 7a4ee46d 2003-11-23 devnull ulong cont, code, wbits;
141 7a4ee46d 2003-11-23 devnull ushort now;
142 7a4ee46d 2003-11-23 devnull int toff, lithist, h, len, bits, use, wnbits, lits, matches, offbits, lenbits;
144 7a4ee46d 2003-11-23 devnull if(n < MinMatch)
145 7a4ee46d 2003-11-23 devnull return -1;
147 7a4ee46d 2003-11-23 devnull wdst = dst;
148 7a4ee46d 2003-11-23 devnull wdmax = dst + n;
150 7a4ee46d 2003-11-23 devnull now = w->begin;
151 7a4ee46d 2003-11-23 devnull s = src;
152 7a4ee46d 2003-11-23 devnull w->data = s;
154 7a4ee46d 2003-11-23 devnull cont = (s[0] << 16) | (s[1] << 8) | s[2];
156 7a4ee46d 2003-11-23 devnull esrc = s + n;
157 7a4ee46d 2003-11-23 devnull half = s + (n >> 1);
158 7a4ee46d 2003-11-23 devnull wnbits = 0;
159 7a4ee46d 2003-11-23 devnull wbits = 0;
160 7a4ee46d 2003-11-23 devnull lits = 0;
161 7a4ee46d 2003-11-23 devnull matches = 0;
162 7a4ee46d 2003-11-23 devnull offbits = 0;
163 7a4ee46d 2003-11-23 devnull lenbits = 0;
164 7a4ee46d 2003-11-23 devnull lithist = ~0;
165 7a4ee46d 2003-11-23 devnull while(s < esrc){
166 7a4ee46d 2003-11-23 devnull h = hashit(cont);
168 7a4ee46d 2003-11-23 devnull sss = s;
169 7a4ee46d 2003-11-23 devnull toff = whackmatch(w, &sss, esrc, h, now);
170 7a4ee46d 2003-11-23 devnull ss = sss;
172 7a4ee46d 2003-11-23 devnull len = ss - s;
173 7a4ee46d 2003-11-23 devnull for(; wnbits >= 8; wnbits -= 8){
174 7a4ee46d 2003-11-23 devnull if(wdst >= wdmax){
175 7a4ee46d 2003-11-23 devnull w->begin = now;
176 7a4ee46d 2003-11-23 devnull return -1;
178 7a4ee46d 2003-11-23 devnull *wdst++ = wbits >> (wnbits - 8);
180 7a4ee46d 2003-11-23 devnull if(len < MinMatch){
181 7a4ee46d 2003-11-23 devnull toff = *s;
182 7a4ee46d 2003-11-23 devnull lithist = (lithist << 1) | toff < 32 | toff > 127;
183 7a4ee46d 2003-11-23 devnull if(lithist & 0x1e){
184 7a4ee46d 2003-11-23 devnull wbits = (wbits << 9) | toff;
185 7a4ee46d 2003-11-23 devnull wnbits += 9;
186 7a4ee46d 2003-11-23 devnull }else if(lithist & 1){
187 7a4ee46d 2003-11-23 devnull toff = (toff + 64) & 0xff;
188 7a4ee46d 2003-11-23 devnull if(toff < 96){
189 7a4ee46d 2003-11-23 devnull wbits = (wbits << 10) | toff;
190 7a4ee46d 2003-11-23 devnull wnbits += 10;
192 7a4ee46d 2003-11-23 devnull wbits = (wbits << 11) | toff;
193 7a4ee46d 2003-11-23 devnull wnbits += 11;
196 7a4ee46d 2003-11-23 devnull wbits = (wbits << 8) | toff;
197 7a4ee46d 2003-11-23 devnull wnbits += 8;
202 7a4ee46d 2003-11-23 devnull * speed hack
203 7a4ee46d 2003-11-23 devnull * check for compression progress, bail if none achieved
205 7a4ee46d 2003-11-23 devnull if(s > half){
206 7a4ee46d 2003-11-23 devnull if(4 * (s - src) < 5 * lits){
207 7a4ee46d 2003-11-23 devnull w->begin = now;
208 7a4ee46d 2003-11-23 devnull return -1;
210 7a4ee46d 2003-11-23 devnull half = esrc;
213 7a4ee46d 2003-11-23 devnull if(s + MinMatch <= esrc){
214 7a4ee46d 2003-11-23 devnull w->next[now & (WhackMaxOff - 1)] = w->hash[h];
215 7a4ee46d 2003-11-23 devnull w->hash[h] = now;
216 7a4ee46d 2003-11-23 devnull if(s + MinMatch < esrc)
217 7a4ee46d 2003-11-23 devnull cont = (cont << 8) | s[MinMatch];
221 7a4ee46d 2003-11-23 devnull continue;
224 7a4ee46d 2003-11-23 devnull matches++;
227 7a4ee46d 2003-11-23 devnull * length of match
229 7a4ee46d 2003-11-23 devnull if(len > MaxLen){
230 7a4ee46d 2003-11-23 devnull len = MaxLen;
231 7a4ee46d 2003-11-23 devnull ss = s + len;
233 7a4ee46d 2003-11-23 devnull len -= MinMatch;
234 7a4ee46d 2003-11-23 devnull if(len < MaxFastLen){
235 7a4ee46d 2003-11-23 devnull bits = lentab[len].bits;
236 7a4ee46d 2003-11-23 devnull wbits = (wbits << bits) | lentab[len].encode;
237 7a4ee46d 2003-11-23 devnull wnbits += bits;
238 7a4ee46d 2003-11-23 devnull lenbits += bits;
240 7a4ee46d 2003-11-23 devnull code = BigLenCode;
241 7a4ee46d 2003-11-23 devnull bits = BigLenBits;
242 7a4ee46d 2003-11-23 devnull use = BigLenBase;
243 7a4ee46d 2003-11-23 devnull len -= MaxFastLen;
244 7a4ee46d 2003-11-23 devnull while(len >= use){
245 7a4ee46d 2003-11-23 devnull len -= use;
246 7a4ee46d 2003-11-23 devnull code = (code + use) << 1;
247 7a4ee46d 2003-11-23 devnull use <<= (bits & 1) ^ 1;
251 7a4ee46d 2003-11-23 devnull wbits = (wbits << bits) | (code + len);
252 7a4ee46d 2003-11-23 devnull wnbits += bits;
253 7a4ee46d 2003-11-23 devnull lenbits += bits;
255 7a4ee46d 2003-11-23 devnull for(; wnbits >= 8; wnbits -= 8){
256 7a4ee46d 2003-11-23 devnull if(wdst >= wdmax){
257 7a4ee46d 2003-11-23 devnull w->begin = now;
258 7a4ee46d 2003-11-23 devnull return -1;
260 7a4ee46d 2003-11-23 devnull *wdst++ = wbits >> (wnbits - 8);
265 7a4ee46d 2003-11-23 devnull * offset in history
268 7a4ee46d 2003-11-23 devnull for(bits = MinOffBits; toff >= (1 << bits); bits++)
270 7a4ee46d 2003-11-23 devnull if(bits < MaxOffBits-1){
271 7a4ee46d 2003-11-23 devnull wbits = (wbits << 3) | (bits - MinOffBits);
272 7a4ee46d 2003-11-23 devnull if(bits != MinOffBits)
274 7a4ee46d 2003-11-23 devnull wnbits += bits + 3;
275 7a4ee46d 2003-11-23 devnull offbits += bits + 3;
277 7a4ee46d 2003-11-23 devnull wbits = (wbits << 4) | 0xe | (bits - (MaxOffBits-1));
279 7a4ee46d 2003-11-23 devnull wnbits += bits + 4;
280 7a4ee46d 2003-11-23 devnull offbits += bits + 4;
282 7a4ee46d 2003-11-23 devnull wbits = (wbits << bits) | toff & ((1 << bits) - 1);
284 7a4ee46d 2003-11-23 devnull for(; s != ss; s++){
285 7a4ee46d 2003-11-23 devnull if(s + MinMatch <= esrc){
286 7a4ee46d 2003-11-23 devnull h = hashit(cont);
287 7a4ee46d 2003-11-23 devnull w->next[now & (WhackMaxOff - 1)] = w->hash[h];
288 7a4ee46d 2003-11-23 devnull w->hash[h] = now;
289 7a4ee46d 2003-11-23 devnull if(s + MinMatch < esrc)
290 7a4ee46d 2003-11-23 devnull cont = (cont << 8) | s[MinMatch];
296 7a4ee46d 2003-11-23 devnull w->begin = now;
298 7a4ee46d 2003-11-23 devnull stats[StatBytes] += esrc - src;
299 7a4ee46d 2003-11-23 devnull stats[StatLits] += lits;
300 7a4ee46d 2003-11-23 devnull stats[StatMatches] += matches;
301 7a4ee46d 2003-11-23 devnull stats[StatLitBits] += (wdst - (dst + 2)) * 8 + wnbits - offbits - lenbits;
302 7a4ee46d 2003-11-23 devnull stats[StatOffBits] += offbits;
303 7a4ee46d 2003-11-23 devnull stats[StatLenBits] += lenbits;
305 7a4ee46d 2003-11-23 devnull if(wnbits & 7){
306 7a4ee46d 2003-11-23 devnull wbits <<= 8 - (wnbits & 7);
307 7a4ee46d 2003-11-23 devnull wnbits += 8 - (wnbits & 7);
309 7a4ee46d 2003-11-23 devnull for(; wnbits >= 8; wnbits -= 8){
310 7a4ee46d 2003-11-23 devnull if(wdst >= wdmax)
311 7a4ee46d 2003-11-23 devnull return -1;
312 7a4ee46d 2003-11-23 devnull *wdst++ = wbits >> (wnbits - 8);
315 7a4ee46d 2003-11-23 devnull stats[StatOutBytes] += wdst - dst;
317 7a4ee46d 2003-11-23 devnull return wdst - dst;
321 7a4ee46d 2003-11-23 devnull whackblock(uchar *dst, uchar *src, int ssize)
323 7a4ee46d 2003-11-23 devnull Whack w;
324 7a4ee46d 2003-11-23 devnull ulong stats[MaxStat];
327 7a4ee46d 2003-11-23 devnull whackinit(&w, 6);
328 7a4ee46d 2003-11-23 devnull r = whack(&w, dst, src, ssize, stats);
329 7a4ee46d 2003-11-23 devnull return r;
