Blame | Last modification | View Log | RSS feed
#include "u.h"
#include "lib.h"
#include "mem.h"
#include "dat.h"
#include "fns.h"
#include "thwack.h"
enum
{
DMaxFastLen = 7,
DBigLenCode = 0x3c, /* minimum code for large lenth encoding */
DBigLenBits = 6,
DBigLenBase = 1 /* starting items to encode for big lens */
};
static uchar lenval[1 << (DBigLenBits - 1)] =
{
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4,
5,
6,
255,
255
};
static uchar lenbits[] =
{
0, 0, 0,
2, 3, 5, 5,
};
static uchar offbits[16] =
{
5, 5, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 12, 13
};
static ushort offbase[16] =
{
0, 0x20,
0x40, 0x60,
0x80, 0xc0,
0x100, 0x180,
0x200, 0x300,
0x400, 0x600,
0x800, 0xc00,
0x1000,
0x2000
};
void
unthwackinit(Unthwack *ut)
{
int i;
memset(ut, 0, sizeof *ut);
for(i = 0; i < DWinBlocks; i++)
ut->blocks[i].data = ut->data[i];
}
ulong
unthwackstate(Unthwack *ut, uchar *mask)
{
ulong bseq, seq;
int slot, m;
seq = ~0UL;
m = 0;
slot = ut->slot;
for(;;){
slot--;
if(slot < 0)
slot += DWinBlocks;
if(slot == ut->slot)
break;
if(ut->blocks[slot].maxoff == 0)
continue;
bseq = ut->blocks[slot].seq;
if(seq == ~0UL)
seq = bseq;
else if(seq - bseq > MaxSeqMask)
break;
else
m |= 1 << (seq - bseq - 1);
}
*mask = m;
return seq;
}
/*
* insert this block in it's correct sequence number order.
* replace the oldest block, which is always pointed to by ut->slot.
* the encoder doesn't use a history at wraparound,
* so don't worry about that case.
*/
static int
unthwackinsert(Unthwack *ut, int len, ulong seq)
{
uchar *d;
int slot, tslot;
tslot = ut->slot;
for(;;){
slot = tslot - 1;
if(slot < 0)
slot += DWinBlocks;
if(ut->blocks[slot].seq <= seq || ut->blocks[slot].maxoff == 0)
break;
d = ut->blocks[tslot].data;
ut->blocks[tslot] = ut->blocks[slot];
ut->blocks[slot].data = d;
tslot = slot;
}
ut->blocks[tslot].seq = seq;
ut->blocks[tslot].maxoff = len;
ut->slot++;
if(ut->slot >= DWinBlocks)
ut->slot = 0;
ut->blocks[ut->slot].seq = ~0UL;
ut->blocks[ut->slot].maxoff = 0;
return tslot;
}
int
unthwack(Unthwack *ut, uchar *dst, int ndst, uchar *src, int nsrc, ulong seq)
{
UnthwBlock blocks[CompBlocks], *b, *eblocks;
uchar *s, *d, *dmax, *smax, lit;
ulong cmask, cseq, bseq, utbits;
int i, off, len, bits, slot, use, code, utnbits, overbits, lithist;
if(nsrc < 4 || nsrc > ThwMaxBlock)
return -1;
slot = ut->slot;
b = blocks;
*b = ut->blocks[slot];
d = b->data;
dmax = d + ndst;
/*
* set up the history blocks
*/
cseq = seq - src[0];
cmask = src[1];
b++;
while(cseq != seq && b < blocks + CompBlocks){
slot--;
if(slot < 0)
slot += DWinBlocks;
if(slot == ut->slot)
break;
bseq = ut->blocks[slot].seq;
if(bseq == cseq){
*b = ut->blocks[slot];
b++;
if(cmask == 0){
cseq = seq;
break;
}
do{
bits = cmask & 1;
cseq--;
cmask >>= 1;
}while(!bits);
}
}
eblocks = b;
if(cseq != seq){
print("unthwack: blocks dropped: seq=%ld cseq=%ld %d cmask=%#lx %#x\n",
seq, cseq, src[0], cmask, src[1]);
return -2;
}
smax = src + nsrc;
src += 2;
utnbits = 0;
utbits = 0;
overbits = 0;
lithist = ~0;
while(src < smax || utnbits - overbits >= MinDecode){
while(utnbits <= 24){
utbits <<= 8;
if(src < smax)
utbits |= *src++;
else
overbits += 8;
utnbits += 8;
}
/*
* literal
*/
len = lenval[(utbits >> (utnbits - 5)) & 0x1f];
if(len == 0){
if(lithist & 0xf){
utnbits -= 9;
lit = (utbits >> utnbits) & 0xff;
lit &= 255;
}else{
utnbits -= 8;
lit = (utbits >> utnbits) & 0x7f;
if(lit < 32){
if(lit < 24){
utnbits -= 2;
lit = (lit << 2) | ((utbits >> utnbits) & 3);
}else{
utnbits -= 3;
lit = (lit << 3) | ((utbits >> utnbits) & 7);
}
lit = (lit - 64) & 0xff;
}
}
if(d >= dmax)
return -1;
*d++ = lit;
lithist = (lithist << 1) | (lit < 32) | (lit > 127);
blocks->maxoff++;
continue;
}
/*
* length
*/
if(len < 255)
utnbits -= lenbits[len];
else{
utnbits -= DBigLenBits;
code = ((utbits >> utnbits) & ((1 << DBigLenBits) - 1)) - DBigLenCode;
len = DMaxFastLen;
use = DBigLenBase;
bits = (DBigLenBits & 1) ^ 1;
while(code >= use){
len += use;
code -= use;
code <<= 1;
utnbits--;
if(utnbits < 0)
return -1;
code |= (utbits >> utnbits) & 1;
use <<= bits;
bits ^= 1;
}
len += code;
while(utnbits <= 24){
utbits <<= 8;
if(src < smax)
utbits |= *src++;
else
overbits += 8;
utnbits += 8;
}
}
/*
* offset
*/
utnbits -= 4;
bits = (utbits >> utnbits) & 0xf;
off = offbase[bits];
bits = offbits[bits];
utnbits -= bits;
off |= (utbits >> utnbits) & ((1 << bits) - 1);
off++;
b = blocks;
while(off > b->maxoff){
off -= b->maxoff;
b++;
if(b >= eblocks)
return -1;
}
if(d + len > dmax
|| b != blocks && len > off)
return -1;
s = b->data + b->maxoff - off;
blocks->maxoff += len;
for(i = 0; i < len; i++)
d[i] = s[i];
d += len;
}
if(utnbits < overbits)
return -1;
len = d - blocks->data;
memmove(dst, blocks->data, len);
unthwackinsert(ut, len, seq);
return len;
}