ref: d3512f60df5d7a2ea5c4cad3cdef797f1f95a182
dir: /sys/src/9/port/thwack.c/
#include "u.h"
#include "lib.h"
#include "mem.h"
#include "dat.h"
#include "fns.h"
#include "thwack.h"
typedef struct Huff Huff;
enum
{
MaxFastLen = 9,
BigLenCode = 0x1f4, /* minimum code for large lenth encoding */
BigLenBits = 9,
BigLenBase = 4 /* starting items to encode for big lens */
};
enum
{
StatBytes,
StatOutBytes,
StatLits,
StatMatches,
StatOffBits,
StatLenBits,
StatDelay,
StatHist,
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 */
};
void
thwackinit(Thwack *tw)
{
int i;
memset(tw, 0, sizeof *tw);
for(i = 0; i < EWinBlocks; i++){
tw->blocks[i].data = tw->data[i];
tw->blocks[i].edata = tw->blocks[i].data;
tw->blocks[i].hash = tw->hash[i];
tw->blocks[i].acked = 0;
}
}
/*
* acknowledgement for block seq & nearby preds
*/
void
thwackack(Thwack *tw, ulong seq, ulong mask)
{
int slot, b;
slot = tw->slot;
for(;;){
slot--;
if(slot < 0)
slot += EWinBlocks;
if(slot == tw->slot)
break;
if(tw->blocks[slot].seq != seq)
continue;
tw->blocks[slot].acked = 1;
if(mask == 0)
break;
do{
b = mask & 1;
seq--;
mask >>= 1;
}while(!b);
}
}
/*
* find a string in the dictionary
*/
static int
thwmatch(ThwBlock *b, ThwBlock *eblocks, uchar **ss, uchar *esrc, ulong h)
{
int then, toff, w, ok;
uchar *s, *t;
s = *ss;
if(esrc < s + MinMatch)
return 0;
toff = 0;
for(; b < eblocks; b++){
then = b->hash[(h ^ b->seq) & HashMask];
toff += b->maxoff;
w = (ushort)(then - b->begin);
if(w >= b->maxoff)
continue;
/*
* don't need to check for the end because
* 1) s too close check above
* 2) entries too close not added to hash tables
*/
t = w + b->data;
if(s[0] != t[0] || s[1] != t[1] || s[2] != t[2])
continue;
ok = b->edata - t;
if(esrc - s > ok)
esrc = s + ok;
t += 3;
for(s += 3; s < esrc; s++){
if(*s != *t)
break;
t++;
}
*ss = s;
return toff - w;
}
return 0;
}
/*
* 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))
*/
#define hashit(c) ((((ulong)(c) & 0xffffff) * 0x6b43a9b5) >> (32 - HashLog))
/*
* lz77 compression with single lookup in a hash table for each block
*/
int
thwack(Thwack *tw, uchar *dst, uchar *src, int n, ulong seq, ulong stats[ThwStats])
{
ThwBlock *eblocks, *b, blocks[CompBlocks];
uchar *s, *ss, *sss, *esrc, *half, *twdst, *twdmax;
ulong cont, cseq, bseq, cmask, code, twbits;
int now, toff, lithist, h, len, slot, bits, use, twnbits, lits, matches, offbits, lenbits, nhist;
if(n > ThwMaxBlock || n < MinMatch)
return -1;
twdst = dst;
twdmax = dst + n;
/*
* add source to the coding window
* there is always enough space
*/
slot = tw->slot;
b = &tw->blocks[slot];
b->seq = seq;
b->acked = 0;
now = b->begin + b->maxoff;
s = b->data;
memmove(s, src, n);
b->edata = s + n;
b->begin = now;
b->maxoff = n;
/*
* set up the history blocks
*/
cseq = seq;
cmask = 0;
*blocks = *b;
b = blocks;
b->maxoff = 0;
b++;
nhist = 0;
while(b < blocks + CompBlocks){
slot--;
if(slot < 0)
slot += EWinBlocks;
if(slot == tw->slot)
break;
if(!tw->blocks[slot].acked)
continue;
bseq = tw->blocks[slot].seq;
if(cseq == seq){
if(seq - bseq >= MaxSeqStart)
break;
cseq = bseq;
}else if(cseq - bseq > MaxSeqMask)
break;
else
cmask |= 1 << (cseq - bseq - 1);
*b = tw->blocks[slot];
nhist += b->maxoff;
b++;
}
eblocks = b;
*twdst++ = seq - cseq;
*twdst++ = cmask;
cont = (s[0] << 16) | (s[1] << 8) | s[2];
esrc = s + n;
half = s + (n >> 1);
twnbits = 0;
twbits = 0;
lits = 0;
matches = 0;
offbits = 0;
lenbits = 0;
lithist = ~0;
while(s < esrc){
h = hashit(cont);
sss = s;
toff = thwmatch(blocks, eblocks, &sss, esrc, h);
ss = sss;
len = ss - s;
for(; twnbits >= 8; twnbits -= 8){
if(twdst >= twdmax)
return -1;
*twdst++ = twbits >> (twnbits - 8);
}
if(len < MinMatch){
toff = *s;
lithist = (lithist << 1) | (toff < 32) | (toff > 127);
if(lithist & 0x1e){
twbits = (twbits << 9) | toff;
twnbits += 9;
}else if(lithist & 1){
toff = (toff + 64) & 0xff;
if(toff < 96){
twbits = (twbits << 10) | toff;
twnbits += 10;
}else{
twbits = (twbits << 11) | toff;
twnbits += 11;
}
}else{
twbits = (twbits << 8) | toff;
twnbits += 8;
}
lits++;
blocks->maxoff++;
/*
* speed hack
* check for compression progress, bail if none achieved
*/
if(s > half){
if(4 * blocks->maxoff < 5 * lits)
return -1;
half = esrc;
}
if(s + MinMatch <= esrc){
blocks->hash[(h ^ blocks->seq) & HashMask] = now;
if(s + MinMatch < esrc)
cont = (cont << 8) | s[MinMatch];
}
now++;
s++;
continue;
}
blocks->maxoff += len;
matches++;
/*
* length of match
*/
len -= MinMatch;
if(len < MaxFastLen){
bits = lentab[len].bits;
twbits = (twbits << bits) | lentab[len].encode;
twnbits += 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++;
}
twbits = (twbits << bits) | (code + len);
twnbits += bits;
lenbits += bits;
for(; twnbits >= 8; twnbits -= 8){
if(twdst >= twdmax)
return -1;
*twdst++ = twbits >> (twnbits - 8);
}
}
/*
* offset in history
*/
toff--;
for(bits = OffBase; toff >= (1 << bits); bits++)
;
if(bits < MaxOff+OffBase-1){
twbits = (twbits << 3) | (bits - OffBase);
if(bits != OffBase)
bits--;
twnbits += bits + 3;
offbits += bits + 3;
}else{
twbits = (twbits << 4) | 0xe | (bits - (MaxOff+OffBase-1));
bits--;
twnbits += bits + 4;
offbits += bits + 4;
}
twbits = (twbits << bits) | toff & ((1 << bits) - 1);
for(; s != ss; s++){
if(s + MinMatch <= esrc){
h = hashit(cont);
blocks->hash[(h ^ blocks->seq) & HashMask] = now;
if(s + MinMatch < esrc)
cont = (cont << 8) | s[MinMatch];
}
now++;
}
}
if(twnbits & 7){
twbits <<= 8 - (twnbits & 7);
twnbits += 8 - (twnbits & 7);
}
for(; twnbits >= 8; twnbits -= 8){
if(twdst >= twdmax)
return -1;
*twdst++ = twbits >> (twnbits - 8);
}
tw->slot++;
if(tw->slot >= EWinBlocks)
tw->slot = 0;
stats[StatBytes] += blocks->maxoff;
stats[StatLits] += lits;
stats[StatMatches] += matches;
stats[StatOffBits] += offbits;
stats[StatLenBits] += lenbits;
stats[StatDelay] = stats[StatDelay]*7/8 + dst[0];
stats[StatHist] = stats[StatHist]*7/8 + nhist;
stats[StatOutBytes] += twdst - dst;
return twdst - dst;
}