Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
746 lines (664 sloc) 17.8 KB
// LzHuf.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#pragma hdrstop
#include <io.h>
#include <fcntl.h>
#include <sys\stat.h>
#define MODULE
//typedef unsigned char BYTE;
unsigned textsize = 0, codesize = 0;
char wterr[] = "Can't write.";
/********** LZSS compression **********/
#define N 4096 /* buffer size */
#define F 60 /* lookahead buffer size */
#define THRESHOLD 2
#define NIL N /* leaf of tree */
#define N_CHAR (256 - THRESHOLD + F) /* kinds of characters (character code = 0..N_CHAR-1) */
#define T (N_CHAR * 2 - 1) /* size of table */
#define R (T - 1) /* position of root */
#define MAX_FREQ 0x4000 /* updates tree when the */
u8 text_buf[N + F];
int match_position, match_length, lson[N + 1], rson[N + 257], dad[N + 1];
unsigned code, len;
unsigned tim_size = 0;
unsigned freq[T + 1]; /* frequency table */
int prnt[T + N_CHAR + 1]; /* pointers to parent nodes, except for the */
/* elements [T..T + N_CHAR - 1] which are used to get */
/* the positions of leaves corresponding to the codes. */
int son[T]; /* pointers to child nodes (son[], son[] + 1) */
//************************** Internal FS
//typedef xr_vector<BYTE> vecB;
class LZfs
{
private:
unsigned getbuf;
unsigned getlen;
unsigned putbuf;
unsigned putlen;
u8* in_start;
u8* in_end;
u8* in_iterator;
u8* out_start;
u8* out_end;
u8* out_iterator;
public:
IC int _getb()
{
if (in_iterator == in_end) return EOF;
return *in_iterator++;
}
IC void _putb(int c)
{
if (out_iterator == out_end)
{
u32 out_size = u32(out_end - out_start);
out_start = (u8*)xr_realloc(out_start, out_size + 1024);
out_iterator = out_start + out_size;
out_end = out_iterator + 1024;
}
*out_iterator++ = u8(c & 0xFF);
}
LZfs()
{
in_start = in_end = in_iterator = 0;
out_start = out_end = out_iterator = 0;
}
IC void Init_Input(u8* _start, u8* _end)
{
// input
in_start = _start;
in_end = _end;
in_iterator = in_start;
// bitwise input/output
getbuf = getlen = putbuf = putlen = 0;
}
IC void Init_Output(int _rsize)
{
// output
out_start = (u8*)xr_malloc(_rsize);
out_end = out_start + _rsize;
out_iterator = out_start;
}
IC u32 InputSize()
{
return u32(in_end - in_start);
}
IC u32 OutSize()
{
return u32(out_iterator - out_start);
}
IC u8* OutPointer()
{
return out_start;
}
IC void OutRelease()
{
xr_free(out_start);
out_start = 0;
out_end = 0;
out_iterator = 0;
}
IC int GetBit(void) /* get one bit */
{
unsigned i;
while (getlen <= 8)
{
if ((int)(i = _getb()) < 0) i = 0;
getbuf |= i << (8 - getlen);
getlen += 8;
}
i = getbuf;
getbuf <<= 1;
getlen--;
return (int)((i & 0x8000) >> 15);
}
IC int GetByte(void) /* get one byte */
{
unsigned i;
while (getlen <= 8)
{
if ((int)(i = _getb()) < 0) i = 0;
getbuf |= i << (8 - getlen);
getlen += 8;
}
i = getbuf;
getbuf <<= 8;
getlen -= 8;
return (int)((i & 0xff00) >> 8);
}
IC void PutCode(int l, unsigned c) /* output c bits of code */
{
putbuf |= c >> putlen;
if ((putlen += l) >= 8)
{
_putb(putbuf >> 8);
if ((putlen -= 8) >= 8)
{
_putb(putbuf);
codesize += 2;
putlen -= 8;
putbuf = c << (l - putlen);
}
else
{
putbuf <<= 8;
codesize++;
}
}
}
IC void PutFlush()
{
if (putlen)
{
_putb(putbuf >> 8);
codesize++;
}
}
};
static LZfs fs;
//************************** Internal FS
IC void InitTree(void) /* initialize trees */
{
int i;
for (i = N + 1; i <= N + 256; i++) rson[i] = NIL; /* root */
for (i = 0; i < N; i++) dad[i] = NIL; /* node */
}
void InsertNode(int r) /* insert to tree */
{
int i, p, cmp;
u8* key;
unsigned c;
cmp = 1;
key = &text_buf[r];
p = N + 1 + key[0];
rson[r] = lson[r] = NIL;
match_length = 0;
for (;;)
{
if (cmp >= 0)
{
if (rson[p] != NIL)
p = rson[p];
else
{
rson[p] = r;
dad[r] = p;
return;
}
}
else
{
if (lson[p] != NIL)
p = lson[p];
else
{
lson[p] = r;
dad[r] = p;
return;
}
}
for (i = 1; i < F; i++)
if ((cmp = key[i] - text_buf[p + i]) != 0)
break;
if (i > THRESHOLD)
{
if (i > match_length)
{
match_position = ((r - p) & (N - 1)) - 1;
if ((match_length = i) >= F)
break;
}
if (i == match_length)
{
if ((c = ((r - p) & (N - 1)) - 1) < (unsigned)match_position)
{
match_position = c;
}
}
}
}
dad[r] = dad[p];
lson[r] = lson[p];
rson[r] = rson[p];
dad[lson[p]] = r;
dad[rson[p]] = r;
if (rson[dad[p]] == p)
rson[dad[p]] = r;
else
lson[dad[p]] = r;
dad[p] = NIL; /* remove p */
}
void DeleteNode(int p) /* remove from tree */
{
int q;
if (dad[p] == NIL) return; /* not registered */
if (rson[p] == NIL)
q = lson[p];
else
{
if (lson[p] == NIL)
{
q = rson[p];
}
else
{
q = lson[p];
if (rson[q] != NIL)
{
do { q = rson[q]; } while (rson[q] != NIL);
rson[dad[q]] = lson[q];
dad[lson[q]] = dad[q];
lson[q] = lson[p];
dad[lson[p]] = q;
}
rson[q] = rson[p];
dad[rson[p]] = q;
}
}
dad[q] = dad[p];
if (rson[dad[p]] == p)
rson[dad[p]] = q;
else
lson[dad[p]] = q;
dad[p] = NIL;
}
/* Huffman coding */
/* table for encoding and decoding the upper 6 bits of position */
/* for encoding */
u8 p_len[64] =
{
0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
};
u8 p_code[64] =
{
0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
};
/* for decoding */
u8 d_code[256] =
{
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
};
u8 d_len[256] =
{
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
};
/* initialization of tree */
void StartHuff(void)
{
int i, j;
for (i = 0; i < N_CHAR; i++)
{
freq[i] = 1;
son[i] = i + T;
prnt[i + T] = i;
}
i = 0;
j = N_CHAR;
while (j <= R)
{
freq[j] = freq[i] + freq[i + 1];
son[j] = i;
prnt[i] = prnt[i + 1] = j;
i += 2;
j++;
}
freq[T] = 0xffff;
prnt[R] = 0;
}
/* reconstruction of tree */
void reconst(void)
{
int i, j, k;
unsigned f, l;
/* collect leaf nodes in the first half of the table */
/* and replace the freq by (freq + 1) / 2. */
j = 0;
for (i = 0; i < T; i++)
{
if (son[i] >= T)
{
freq[j] = (freq[i] + 1) / 2;
son[j] = son[i];
j++;
}
}
/* begin constructing tree by connecting sons */
for (i = 0, j = N_CHAR; j < T; i += 2, j++)
{
k = i + 1;
f = freq[j] = freq[i] + freq[k];
for (k = j - 1; f < freq[k]; k--);
k++;
l = (j - k) * sizeof(unsigned);
memmove(&freq[k + 1], &freq[k], l);
freq[k] = f;
memmove(&son[k + 1], &son[k], l);
son[k] = i;
}
/* connect prnt */
for (i = 0; i < T; i++)
{
if ((k = son[i]) >= T)
{
prnt[k] = i;
}
else
{
prnt[k] = prnt[k + 1] = i;
}
}
}
/* increment frequency of given code by one, and update tree */
void update(int c)
{
int i, j, k, l;
if (freq[R] == MAX_FREQ)
{
reconst();
}
c = prnt[c + T];
do
{
k = ++freq[c];
/* if the order is disturbed, exchange nodes */
if ((unsigned)k > freq[l = c + 1])
{
while ((unsigned)k > freq[++l]);
l--;
freq[c] = freq[l];
freq[l] = k;
i = son[c];
prnt[i] = l;
if (i < T) prnt[i + 1] = l;
j = son[l];
son[l] = i;
prnt[j] = c;
if (j < T) prnt[j + 1] = c;
son[c] = j;
c = l;
}
} while ((c = prnt[c]) != 0); /* repeat up to root */
}
void EncodeChar(unsigned c)
{
unsigned i;
int j, k;
i = 0;
j = 0;
k = prnt[c + T];
/* travel from leaf to root */
do
{
i >>= 1;
/* if node's address is odd-numbered, choose bigger brother node */
if (k & 1) i += 0x8000;
j++;
k = prnt[k];
} while (k != R);
fs.PutCode(j, i);
code = i;
len = j;
update(c);
}
void EncodePosition(unsigned c)
{
unsigned i;
/* output upper 6 bits by table lookup */
i = c >> 6;
fs.PutCode(p_len[i], (unsigned)p_code[i] << 8);
/* output lower 6 bits verbatim */
fs.PutCode(6, (c & 0x3f) << 10);
}
int DecodeChar(void)
{
unsigned c;
c = son[R];
/* travel from root to leaf, */
/* choosing the smaller child node (son[]) if the read bit is 0, */
/* the bigger (son[]+1} if 1 */
while (c < T)
{
c += fs.GetBit();
c = son[c];
}
c -= T;
update(c);
return (int)c;
}
int DecodePosition(void)
{
unsigned i, j, c;
/* recover upper 6 bits from table */
i = fs.GetByte();
c = (unsigned)d_code[i] << 6;
j = d_len[i];
/* read lower 6 bits verbatim */
j -= 2;
while (j--)
{
i = (i << 1) + fs.GetBit();
}
return (int)(c | (i & 0x3f));
}
/* compression */
void Encode(void) /* compression */
{
int i, c, len, r, s, last_match_length;
textsize = fs.InputSize();
fs.Init_Output(textsize);
fs._putb((textsize & 0xff));
fs._putb((textsize & 0xff00) >> 8);
fs._putb((textsize & 0xff0000L) >> 16);
fs._putb((textsize & 0xff000000L) >> 24);
if (textsize == 0)
return;
textsize = 0; /* rewind and re-read */
StartHuff();
InitTree();
s = 0;
r = N - F;
for (i = s; i < r; i++)
text_buf[i] = 0x20;
for (len = 0; len < F && (c = fs._getb()) != EOF; len++)
text_buf[r + len] = (unsigned char)c;
textsize = len;
for (i = 1; i <= F; i++)
InsertNode(r - i);
InsertNode(r);
do
{
if (match_length > len)
match_length = len;
if (match_length <= THRESHOLD)
{
match_length = 1;
// textsize==56158 - FATAL :(
EncodeChar(text_buf[r]);
}
else
{
EncodeChar(255 - THRESHOLD + match_length);
EncodePosition(match_position);
}
last_match_length = match_length;
for (i = 0; i < last_match_length &&
(c = fs._getb()) != EOF; i++)
{
DeleteNode(s);
text_buf[s] = (unsigned char)c;
if (s < F - 1)
text_buf[s + N] = (unsigned char)c;
s = (s + 1) & (N - 1);
r = (r + 1) & (N - 1);
InsertNode(r);
}
textsize += i;
while (i++ < last_match_length)
{
DeleteNode(s);
s = (s + 1) & (N - 1);
r = (r + 1) & (N - 1);
if (--len) InsertNode(r);
}
} while (len > 0);
fs.PutFlush();
tim_size = textsize;
}
void Decode(void) /* recover */
{
int i, j, k, r, c;
unsigned int count;
textsize = (fs._getb());
textsize |= (fs._getb() << 8);
textsize |= (fs._getb() << 16);
textsize |= (fs._getb() << 24);
if (textsize == 0) return;
fs.Init_Output(textsize);
StartHuff();
for (i = 0; i < N - F; i++)
text_buf[i] = 0x20;
r = N - F;
for (count = 0; count < textsize;)
{
c = DecodeChar();
if (c < 256)
{
fs._putb(c);
text_buf[r++] = (unsigned char)c;
r &= (N - 1);
count++;
}
else
{
i = (r - DecodePosition() - 1) & (N - 1);
j = c - 255 + THRESHOLD;
for (k = 0; k < j; k++)
{
c = text_buf[(i + k) & (N - 1)];
fs._putb(c);
text_buf[r++] = (unsigned char)c;
r &= (N - 1);
count++;
}
}
}
tim_size = count;
}
unsigned _writeLZ(int hf, void* d, unsigned size)
{
u8* start = (u8*)d;
fs.Init_Input(start, start + size);
// Actual compression
Encode();
// Flush cache
int size_out = fs.OutSize();
if (size_out) _write(hf, fs.OutPointer(), size_out);
fs.OutRelease();
return size_out;
}
void _compressLZ(u8** dest, unsigned* dest_sz, void* src, unsigned src_sz)
{
u8* start = (u8*)src;
fs.Init_Input(start, start + src_sz);
Encode();
*dest = fs.OutPointer();
*dest_sz = fs.OutSize();
}
void _decompressLZ(u8** dest, unsigned* dest_sz, void* src, unsigned src_sz)
{
u8* start = (u8*)src;
fs.Init_Input(start, start + src_sz);
Decode();
*dest = fs.OutPointer();
*dest_sz = fs.OutSize();
}
unsigned _readLZ(int hf, void*& d, unsigned size)
{
// Read file in memory
u8* data = (u8*)xr_malloc(size);
_read(hf, data, size);
fs.Init_Input(data, data + size);
// Actual compression
Decode();
// Flush cache
xr_free(data);
d = fs.OutPointer();
return fs.OutSize();
}
You can’t perform that action at this time.