misc idea: Mini-LZ

well, this idea was mentioned some recently.
namely, my ability to actually code stuff, recently, is somewhat reduced by having resumed classes, and thus having less time for coding.

however, a recent idea that I have spec'ed out is something I am calling 'Mini-LZ'.
point, well, is that of being much more readily usable in a copy-paste manner than deflate.

for example, my inflater and deflater together take about 1.6 kloc, and have a reasonable number of functions.
one can copy the files (for example, I can readily copy them between projects), however, for finer grained usages (and where deflate is overkill), this is not optimal.


nevermind that some people object to a copy-paste coding style, but nevermind this...
I will argue that there are cases (especially within large modular C-based projects) where this may be the best style...


several schemes were considered (I wrote up the designs, and then template encoders and decoders to see about how the code would look...).

the most recent idea (MiniLZ2), being a more or less LZSS style algo.
though adding to complexity, multiple run styles are supported.

a simpler algo would only have a single run type. say, a flat 3-byte run with an 8 bit length and a 16 bit offset (infact this is what my deflater does internally), however, multiple run types are supported both for range, and because I expect certain occurances (say, short nearby runs) to be particularly common.


the scheme supports 2 2-byte run types, 1 3-byte type, and 4 and 5 byte types.

2 byte: run 3..18, dist 0..1023; run 0..1023, 0..16.
3 byte: run 3..258, dist 0..16383.
4 byte: run 0..1023, dist 0..262143
5 byte: run 0..4095, dist 0..16777215

this limits circular buffer decoders some, but for now I will assume single flat buffers to be the norm (this is what I was often doing with deflate as well).

or such...


example from my 'idea spec', note that the code fragments are untested, mostly just serving to organize my thoughts...
in truth, the encoder may not work at all, or may be slow (certain lookup optimizations employed in my deflater were omited for brevity). actually, an encoder could also attempt optimal-parsing, at the cost of code complexity.

----
0: literal byte
1: LZ run

1 byte, with 2 high bits giving a type:
0: short run (2 bytes)
mid 2 bits are 2 high bits of distance.
low 4 bits are length (3..18).
next byte is the low 8 bits of distance (0..1023).
1: medium run (3 bytes)
low 6 bits are length(+2 of next), are a length, 3..258.
next 2 bytes form a distance (high-low, 0..16383)
2: shallow run (2 bytes)
short run with length and distance reversed, RLE
length=0..1023, dist=0..15
3 (possible): 2 more tag bits
0: 24 bit word follows (4 bytes)
10 bit length, 18 bist distance.
1: full 32 bit word follows (5 bytes)
uses low 4 bits and byte for a 12 bit length.
24 bit distance.

a shallow run with both a length and distance of 0 will indicate a stream end.

int MiniLZ2_Decode(byte *ibuf, byte *obuf)
{
byte *cs, *ct, *cs1;
int mrk;
int i, j, k;

cs=ibuf; ct=obuf;
mrk=0;
while(1)
{
if(!(mrk&256))mrk=(*cs++)|0xFF00;

if(mrk&1)
{
i=*cs++;
if((i&0xC0)==0x00)
{ j=(*cs++)|((i<<4)&0x300); i=(i&15)+3; }
else if((i&0xC0)==0x40) {
j=(cs[0]<<8)+cs[1]; cs+=2;
i=(((i<<2)|(j>>14))&255)+3;
j&=16383;
}else if((i&0xC0)==0x80)
{ k=i; i=(*cs++)|((k<<4)&0x300); j=i&15; }
else if((i&0xF0)==0xC0) {
k=(i<<24)|(cs[0]<<16)|(cs[1]<<8)|cs[2]; cs+=3;
i=(k>>18)&1023; j=k&262143; }
else if((i&0xF0)==0xD0) {
i=((i&15)<<8)|(*cs++);
j=(cs[0]<<16)+(cs[1]<<8)+cs[2]; cs+=3;
}
if(!i)break;

cs1=ct-j; while(i--)*ct++=*cs1++;
mrk>>=1;
continue;
}

*ct++=*cs++;
mrk>>=1;
}
}

int MiniLZ2_Encode(byte *ibuf, byte *obuf, int sz)
{
static byte *chain[65536], *hash[4096];
byte *cs, *ct, *cse, *s0, *s1, *mps;
int chi, mp;
int i, j, k, bj, bk;

for(i=0; i<65536; i++)chain[i]=NULL;
for(i=0; i<4096; i++)hash[i]=NULL;

cs=ibuf; cse=ibuf+sz ct=obuf;
mps=ct++; *mps=0; mp=0;

while(cs<cse)
{
i=((cs[0]*251+cs[1])*251+cs[2])&0xFFF;
s0=hash[i]; k=cs-s0; bj=0; bk=0; chi=cs-ibuf;
while(s0 && (k<65536))
{
s1=cs; s1e=cs+1023; if(cse<s1e)s1e=cse;
while((s1<s1e) && (*s0==*s1)) { *s0++; *s1++; }

j=s1-cs;
if((j>bj) || (!bj)) { bj=j; bk=k; }
s0=chain[(chi-k)&65535];
}

if((bj>=3) && ((bk<16384) || (bj>=8)))
{
if((bj<=18) && (bk<1024))
{ *ct++=(bj-3)|((bk>>4)&0x30); *ct++=bk&0xFF; }
else if(bk<16)
{ *ct++=0x80|bk|((bj>>4)&0x30); *ct++=bj&0xFF; }
else if((bj<=258) && (bk<16384))
{
j=bj-3;
*ct++=0x40 | ((j>>2)&63);
*ct++=((bk>>8)&0x3F)|(j<<6)&0xC0;
*ct++=bk&0xFF;
}else
{
*ct++=0xC0 | ((bj>>6)&15);
*ct++=((bk>>16)&0x3)|(bj<<2)&0xFC;
*ct++=(bk>>8)&0xFF;
*ct++=bk&0xFF;
}

j=bj;
while(j--)
{
i=((cs[0]*251+cs[1])*251+cs[2])&0xFFF;
chain[(chi++)&65535]=hash[i];
hash[i]=cs++;
}

*mps|=1<<(mp++);
if(mp>=8) { mps=ct++; *mps=0; mp=0; }
continue;
}

chain[chi&65535]=hash[i]; hash[i]=cs;
*ct++=*cs++;
mp++; if(mp>=8) { mps=ct++; *mps=0; mp=0; }
}
*ct++=0x80; *ct++=0x00;
*mps|=1<<(mp++);
return(ct-obuf);
}


.

Relevant Pages

  • Re: A Lighting Model
    ... a good point of the inverse square law is that it's ... your distance calculations. ... slowdist(int x, int y) ...
    (rec.games.roguelike.development)
  • Re: Constructor problem
    ... all the values are int values. ... ie, if I input Distance a I'd like to be able to ... int measure (void) const; ...
    (comp.lang.cpp)
  • Re: String compare
    ... my project is about mutation clustering... ... data in the form of 1's and 0's(data= 101010000011000001, could be int ... link and there was this algo of hamming distance... ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: String compare
    ... data in the form of 1's and 0's(data= 101010000011000001, could be int ... link and there was this algo of hamming distance... ... so I suspect it is homework. ...
    (microsoft.public.dotnet.languages.csharp)