ref: 7d7e8ae31ac01434c7017afce4eb0a033281a757
dir: /sys/src/cmd/venti/srv/whack.c/
#include "stdinc.h"
#include "whack.h"
typedef struct Huff Huff;
int compressblocks = 1;
enum
{
MaxFastLen = 9,
BigLenCode = 0x1f4, /* minimum code for large lenth encoding */
BigLenBits = 9,
BigLenBase = 4, /* starting items to encode for big lens */
MinOffBits = 6,
MaxOffBits = MinOffBits + 8,
MaxLen = 2051 /* max. length encodable in 24 bits */
};
enum
{
StatBytes,
StatOutBytes,
StatLits,
StatMatches,
StatLitBits,
StatOffBits,
StatLenBits,
MaxStat
};
struct Huff
{
short bits; /* length of the code */
ulong encode; /* the code */
};
static Huff lentab[MaxFastLen] =
{
{2, 0x2}, /* 10 */
{3, 0x6}, /* 110 */
{5, 0x1c}, /* 11100 */
{5, 0x1d}, /* 11101 */
{6, 0x3c}, /* 111100 */
{7, 0x7a}, /* 1111010 */
{7, 0x7b}, /* 1111011 */
{8, 0xf8}, /* 11111000 */
{8, 0xf9}, /* 11111001 */
};
static int thwmaxcheck;
void
whackinit(Whack *tw, int level)
{
thwmaxcheck = (1 << level);
thwmaxcheck -= thwmaxcheck >> 2;
if(thwmaxcheck < 2)
thwmaxcheck = 2;
else if(thwmaxcheck > 1024)
thwmaxcheck = 1024;
memset(tw, 0, sizeof *tw);
tw->begin = 2 * WhackMaxOff;
}
/*
* find a string in the dictionary
*/
static int
whackmatch(Whack *b, uchar **ss, uchar *esrc, ulong h, ulong now)
{
ushort then, off, last;
int bestoff, bestlen, check;
uchar *s, *t;
s = *ss;
if(esrc < s + MinMatch)
return -1;
if(s + MaxLen < esrc)
esrc = s + MaxLen;
bestoff = 0;
bestlen = 0;
check = thwmaxcheck;
last = 0;
for(then = b->hash[h]; check-- > 0; then = b->next[then & (WhackMaxOff - 1)]){
off = now - then;
if(off <= last || off > WhackMaxOff)
break;
/*
* don't need to check for the end because
* 1) s too close check above
*/
t = s - off;
if(s[0] == t[0] && s[1] == t[1] && s[2] == t[2]){
if(!bestlen || esrc - s > bestlen && s[bestlen] == t[bestlen]){
t += 3;
for(s += 3; s < esrc; s++){
if(*s != *t)
break;
t++;
}
if(s - *ss > bestlen){
bestlen = s - *ss;
bestoff = off;
if(bestlen > thwmaxcheck)
break;
}
}
}
s = *ss;
last = off;
}
*ss += bestlen;
return bestoff;
}
/*
* knuth vol. 3 multiplicative hashing
* each byte x chosen according to rules
* 1/4 < x < 3/10, 1/3 x < < 3/7, 4/7 < x < 2/3, 7/10 < x < 3/4
* with reasonable spread between the bytes & their complements
*
* the 3 byte value appears to be as almost good as the 4 byte value,
* and might be faster on some machines
*/
/*
#define hashit(c) ((((ulong)(c) * 0x6b43a9) >> (24 - HashLog)) & HashMask)
*/
#define hashit(c) (((((ulong)(c) & 0xffffff) * 0x6b43a9b5) >> (32 - HashLog)) & HashMask)
/*
* lz77 compression with single lookup in a hash table for each block
*/
int
whack(Whack *w, uchar *dst, uchar *src, int n, ulong stats[WhackStats])
{
uchar *s, *ss, *sss, *esrc, *half, *wdst, *wdmax;
ulong cont, code, wbits;
ushort now;
int toff, lithist, h, len, bits, use, wnbits, lits, matches, offbits, lenbits;
if(!compressblocks || n < MinMatch)
return -1;
wdst = dst;
wdmax = dst + n;
now = w->begin;
s = src;
w->data = s;
cont = (s[0] << 16) | (s[1] << 8) | s[2];
esrc = s + n;
half = s + (n >> 1);
wnbits = 0;
wbits = 0;
lits = 0;
matches = 0;
offbits = 0;
lenbits = 0;
lithist = ~0;
while(s < esrc){
h = hashit(cont);
sss = s;
toff = whackmatch(w, &sss, esrc, h, now);
ss = sss;
len = ss - s;
for(; wnbits >= 8; wnbits -= 8){
if(wdst >= wdmax){
w->begin = now;
return -1;
}
*wdst++ = wbits >> (wnbits - 8);
}
if(len < MinMatch){
toff = *s;
lithist = (lithist << 1) | toff < 32 | toff > 127;
if(lithist & 0x1e){
wbits = (wbits << 9) | toff;
wnbits += 9;
}else if(lithist & 1){
toff = (toff + 64) & 0xff;
if(toff < 96){
wbits = (wbits << 10) | toff;
wnbits += 10;
}else{
wbits = (wbits << 11) | toff;
wnbits += 11;
}
}else{
wbits = (wbits << 8) | toff;
wnbits += 8;
}
lits++;
/*
* speed hack
* check for compression progress, bail if none achieved
*/
if(s > half){
if(4 * (s - src) < 5 * lits){
w->begin = now;
return -1;
}
half = esrc;
}
if(s + MinMatch <= esrc){
w->next[now & (WhackMaxOff - 1)] = w->hash[h];
w->hash[h] = now;
if(s + MinMatch < esrc)
cont = (cont << 8) | s[MinMatch];
}
now++;
s++;
continue;
}
matches++;
/*
* length of match
*/
if(len > MaxLen){
len = MaxLen;
ss = s + len;
}
len -= MinMatch;
if(len < MaxFastLen){
bits = lentab[len].bits;
wbits = (wbits << bits) | lentab[len].encode;
wnbits += bits;
lenbits += bits;
}else{
code = BigLenCode;
bits = BigLenBits;
use = BigLenBase;
len -= MaxFastLen;
while(len >= use){
len -= use;
code = (code + use) << 1;
use <<= (bits & 1) ^ 1;
bits++;
}
wbits = (wbits << bits) | (code + len);
wnbits += bits;
lenbits += bits;
for(; wnbits >= 8; wnbits -= 8){
if(wdst >= wdmax){
w->begin = now;
return -1;
}
*wdst++ = wbits >> (wnbits - 8);
}
}
/*
* offset in history
*/
toff--;
for(bits = MinOffBits; toff >= (1 << bits); bits++)
;
if(bits < MaxOffBits-1){
wbits = (wbits << 3) | (bits - MinOffBits);
if(bits != MinOffBits)
bits--;
wnbits += bits + 3;
offbits += bits + 3;
}else{
wbits = (wbits << 4) | 0xe | (bits - (MaxOffBits-1));
bits--;
wnbits += bits + 4;
offbits += bits + 4;
}
wbits = (wbits << bits) | toff & ((1 << bits) - 1);
for(; s != ss; s++){
if(s + MinMatch <= esrc){
h = hashit(cont);
w->next[now & (WhackMaxOff - 1)] = w->hash[h];
w->hash[h] = now;
if(s + MinMatch < esrc)
cont = (cont << 8) | s[MinMatch];
}
now++;
}
}
w->begin = now;
stats[StatBytes] += esrc - src;
stats[StatLits] += lits;
stats[StatMatches] += matches;
stats[StatLitBits] += (wdst - (dst + 2)) * 8 + wnbits - offbits - lenbits;
stats[StatOffBits] += offbits;
stats[StatLenBits] += lenbits;
if(wnbits & 7){
wbits <<= 8 - (wnbits & 7);
wnbits += 8 - (wnbits & 7);
}
for(; wnbits >= 8; wnbits -= 8){
if(wdst >= wdmax)
return -1;
*wdst++ = wbits >> (wnbits - 8);
}
stats[StatOutBytes] += wdst - dst;
return wdst - dst;
}
int
whackblock(uchar *dst, uchar *src, int ssize)
{
Whack w;
ulong stats[MaxStat];
int r;
whackinit(&w, 6);
r = whack(&w, dst, src, ssize, stats);
return r;
}