4 typedef struct Huff Huff;
9 BigLenCode = 0x1f4, /* minimum code for large lenth encoding */
11 BigLenBase = 4, /* starting items to encode for big lens */
14 MaxOffBits = MinOffBits + 8,
16 MaxLen = 2051 /* max. length encodable in 24 bits */
34 short bits; /* length of the code */
35 ulong encode; /* the code */
38 static Huff lentab[MaxFastLen] =
42 {5, 0x1c}, /* 11100 */
43 {5, 0x1d}, /* 11101 */
44 {6, 0x3c}, /* 111100 */
45 {7, 0x7a}, /* 1111010 */
46 {7, 0x7b}, /* 1111011 */
47 {8, 0xf8}, /* 11111000 */
48 {8, 0xf9}, /* 11111001 */
51 static int thwmaxcheck;
54 whackinit(Whack *tw, int level)
56 thwmaxcheck = (1 << level);
57 thwmaxcheck -= thwmaxcheck >> 2;
60 else if(thwmaxcheck > 1024)
62 memset(tw, 0, sizeof *tw);
63 tw->begin = 2 * WhackMaxOff;
67 * find a string in the dictionary
70 whackmatch(Whack *b, uchar **ss, uchar *esrc, ulong h, ulong now)
72 ushort then, off, last;
73 int bestoff, bestlen, check;
77 if(esrc < s + MinMatch)
86 for(then = b->hash[h]; check-- > 0; then = b->next[then & (WhackMaxOff - 1)]){
88 if(off <= last || off > WhackMaxOff)
92 * don't need to check for the end because
93 * 1) s too close check above
96 if(s[0] == t[0] && s[1] == t[1] && s[2] == t[2]){
97 if(!bestlen || esrc - s > bestlen && s[bestlen] == t[bestlen]){
99 for(s += 3; s < esrc; s++){
104 if(s - *ss > bestlen){
107 if(bestlen > thwmaxcheck)
120 * knuth vol. 3 multiplicative hashing
121 * each byte x chosen according to rules
122 * 1/4 < x < 3/10, 1/3 x < < 3/7, 4/7 < x < 2/3, 7/10 < x < 3/4
123 * with reasonable spread between the bytes & their complements
125 * the 3 byte value appears to be as almost good as the 4 byte value,
126 * and might be faster on some machines
129 #define hashit(c) ((((ulong)(c) * 0x6b43a9) >> (24 - HashLog)) & HashMask)
131 #define hashit(c) (((((ulong)(c) & 0xffffff) * 0x6b43a9b5) >> (32 - HashLog)) & HashMask)
134 * lz77 compression with single lookup in a hash table for each block
137 whack(Whack *w, uchar *dst, uchar *src, int n, ulong stats[WhackStats])
139 uchar *s, *ss, *sss, *esrc, *half, *wdst, *wdmax;
140 ulong cont, code, wbits;
142 int toff, lithist, h, len, bits, use, wnbits, lits, matches, offbits, lenbits;
154 cont = (s[0] << 16) | (s[1] << 8) | s[2];
169 toff = whackmatch(w, &sss, esrc, h, now);
173 for(; wnbits >= 8; wnbits -= 8){
178 *wdst++ = wbits >> (wnbits - 8);
182 lithist = (lithist << 1) | toff < 32 | toff > 127;
184 wbits = (wbits << 9) | toff;
186 }else if(lithist & 1){
187 toff = (toff + 64) & 0xff;
189 wbits = (wbits << 10) | toff;
192 wbits = (wbits << 11) | toff;
196 wbits = (wbits << 8) | toff;
203 * check for compression progress, bail if none achieved
206 if(4 * (s - src) < 5 * lits){
213 if(s + MinMatch <= esrc){
214 w->next[now & (WhackMaxOff - 1)] = w->hash[h];
216 if(s + MinMatch < esrc)
217 cont = (cont << 8) | s[MinMatch];
234 if(len < MaxFastLen){
235 bits = lentab[len].bits;
236 wbits = (wbits << bits) | lentab[len].encode;
246 code = (code + use) << 1;
247 use <<= (bits & 1) ^ 1;
251 wbits = (wbits << bits) | (code + len);
255 for(; wnbits >= 8; wnbits -= 8){
260 *wdst++ = wbits >> (wnbits - 8);
268 for(bits = MinOffBits; toff >= (1 << bits); bits++)
270 if(bits < MaxOffBits-1){
271 wbits = (wbits << 3) | (bits - MinOffBits);
272 if(bits != MinOffBits)
277 wbits = (wbits << 4) | 0xe | (bits - (MaxOffBits-1));
282 wbits = (wbits << bits) | toff & ((1 << bits) - 1);
285 if(s + MinMatch <= esrc){
287 w->next[now & (WhackMaxOff - 1)] = w->hash[h];
289 if(s + MinMatch < esrc)
290 cont = (cont << 8) | s[MinMatch];
298 stats[StatBytes] += esrc - src;
299 stats[StatLits] += lits;
300 stats[StatMatches] += matches;
301 stats[StatLitBits] += (wdst - (dst + 2)) * 8 + wnbits - offbits - lenbits;
302 stats[StatOffBits] += offbits;
303 stats[StatLenBits] += lenbits;
306 wbits <<= 8 - (wnbits & 7);
307 wnbits += 8 - (wnbits & 7);
309 for(; wnbits >= 8; wnbits -= 8){
312 *wdst++ = wbits >> (wnbits - 8);
315 stats[StatOutBytes] += wdst - dst;
321 whackblock(uchar *dst, uchar *src, int ssize)
324 ulong stats[MaxStat];
328 r = whack(&w, dst, src, ssize, stats);