4 typedef struct Huff Huff;
5 int compressblocks = 1;
10 BigLenCode = 0x1f4, /* minimum code for large lenth encoding */
12 BigLenBase = 4, /* starting items to encode for big lens */
15 MaxOffBits = MinOffBits + 8,
17 MaxLen = 2051 /* max. length encodable in 24 bits */
35 short bits; /* length of the code */
36 ulong encode; /* the code */
39 static Huff lentab[MaxFastLen] =
43 {5, 0x1c}, /* 11100 */
44 {5, 0x1d}, /* 11101 */
45 {6, 0x3c}, /* 111100 */
46 {7, 0x7a}, /* 1111010 */
47 {7, 0x7b}, /* 1111011 */
48 {8, 0xf8}, /* 11111000 */
49 {8, 0xf9}, /* 11111001 */
52 static int thwmaxcheck;
55 whackinit(Whack *tw, int level)
57 thwmaxcheck = (1 << level);
58 thwmaxcheck -= thwmaxcheck >> 2;
61 else if(thwmaxcheck > 1024)
63 memset(tw, 0, sizeof *tw);
64 tw->begin = 2 * WhackMaxOff;
68 * find a string in the dictionary
71 whackmatch(Whack *b, uchar **ss, uchar *esrc, ulong h, ulong now)
73 ushort then, off, last;
74 int bestoff, bestlen, check;
78 if(esrc < s + MinMatch)
87 for(then = b->hash[h]; check-- > 0; then = b->next[then & (WhackMaxOff - 1)]){
89 if(off <= last || off > WhackMaxOff)
93 * don't need to check for the end because
94 * 1) s too close check above
97 if(s[0] == t[0] && s[1] == t[1] && s[2] == t[2]){
98 if(!bestlen || esrc - s > bestlen && s[bestlen] == t[bestlen]){
100 for(s += 3; s < esrc; s++){
105 if(s - *ss > bestlen){
108 if(bestlen > thwmaxcheck)
121 * knuth vol. 3 multiplicative hashing
122 * each byte x chosen according to rules
123 * 1/4 < x < 3/10, 1/3 x < < 3/7, 4/7 < x < 2/3, 7/10 < x < 3/4
124 * with reasonable spread between the bytes & their complements
126 * the 3 byte value appears to be as almost good as the 4 byte value,
127 * and might be faster on some machines
130 #define hashit(c) ((((ulong)(c) * 0x6b43a9) >> (24 - HashLog)) & HashMask)
132 #define hashit(c) (((((ulong)(c) & 0xffffff) * 0x6b43a9b5) >> (32 - HashLog)) & HashMask)
135 * lz77 compression with single lookup in a hash table for each block
138 whack(Whack *w, uchar *dst, uchar *src, int n, ulong stats[WhackStats])
140 uchar *s, *ss, *sss, *esrc, *half, *wdst, *wdmax;
141 ulong cont, code, wbits;
143 int toff, lithist, h, len, bits, use, wnbits, lits, matches, offbits, lenbits;
145 if(!compressblocks || n < MinMatch)
155 cont = (s[0] << 16) | (s[1] << 8) | s[2];
170 toff = whackmatch(w, &sss, esrc, h, now);
174 for(; wnbits >= 8; wnbits -= 8){
179 *wdst++ = wbits >> (wnbits - 8);
183 lithist = (lithist << 1) | toff < 32 | toff > 127;
185 wbits = (wbits << 9) | toff;
187 }else if(lithist & 1){
188 toff = (toff + 64) & 0xff;
190 wbits = (wbits << 10) | toff;
193 wbits = (wbits << 11) | toff;
197 wbits = (wbits << 8) | toff;
204 * check for compression progress, bail if none achieved
207 if(4 * (s - src) < 5 * lits){
214 if(s + MinMatch <= esrc){
215 w->next[now & (WhackMaxOff - 1)] = w->hash[h];
217 if(s + MinMatch < esrc)
218 cont = (cont << 8) | s[MinMatch];
235 if(len < MaxFastLen){
236 bits = lentab[len].bits;
237 wbits = (wbits << bits) | lentab[len].encode;
247 code = (code + use) << 1;
248 use <<= (bits & 1) ^ 1;
252 wbits = (wbits << bits) | (code + len);
256 for(; wnbits >= 8; wnbits -= 8){
261 *wdst++ = wbits >> (wnbits - 8);
269 for(bits = MinOffBits; toff >= (1 << bits); bits++)
271 if(bits < MaxOffBits-1){
272 wbits = (wbits << 3) | (bits - MinOffBits);
273 if(bits != MinOffBits)
278 wbits = (wbits << 4) | 0xe | (bits - (MaxOffBits-1));
283 wbits = (wbits << bits) | toff & ((1 << bits) - 1);
286 if(s + MinMatch <= esrc){
288 w->next[now & (WhackMaxOff - 1)] = w->hash[h];
290 if(s + MinMatch < esrc)
291 cont = (cont << 8) | s[MinMatch];
299 stats[StatBytes] += esrc - src;
300 stats[StatLits] += lits;
301 stats[StatMatches] += matches;
302 stats[StatLitBits] += (wdst - (dst + 2)) * 8 + wnbits - offbits - lenbits;
303 stats[StatOffBits] += offbits;
304 stats[StatLenBits] += lenbits;
307 wbits <<= 8 - (wnbits & 7);
308 wnbits += 8 - (wnbits & 7);
310 for(; wnbits >= 8; wnbits -= 8){
313 *wdst++ = wbits >> (wnbits - 8);
316 stats[StatOutBytes] += wdst - dst;
322 whackblock(uchar *dst, uchar *src, int ssize)
325 ulong stats[MaxStat];
329 r = whack(&w, dst, src, ssize, stats);