/*----------------------------------------------------------------------*/ /* LHarc Encoding/Decoding module */ /* */ /* LZSS Algorithm Haruhiko.Okumura */ /* Adaptic Huffman Encoding 1989.05.27 Haruyasu.Yoshizaki */ /* */ /*----------------------------------------------------------------------*/ #include #include "lhio.h" extern int NotInterruptedCall; extern int ForceReturn; static FILE *infile, *outfile; static long textsize, codesize; static int PutNum; long count; /* number of bytes decoded at present time */ #define SETUP_GETC_CRC(fp) crc_infile = fp #define PUTC_CRC(c) putc_crc(c) #define GETC_CRC() getc_crc() #define END_PUTC_CRC() #define END_GETC_CRC() /*----------------------------------------------------------------------*/ /* */ /* LZSS ENCODING */ /* */ /*----------------------------------------------------------------------*/ #define N 4096 /* buffer size */ #define F 60 /* pre-sence buffer size */ #define THRESHOLD 2 #define NIL N /* term of tree */ static unsigned char text_buf[N + F - 1]; static unsigned int match_position, match_length; static int lson[N + 1], rson[N + 1 + N], dad[N + 1]; static unsigned char same[N + 1]; /*----------------------------------------------------------------------*/ /* */ /* HUFFMAN ENCODING */ /* */ /*----------------------------------------------------------------------*/ #define N_CHAR (256 - THRESHOLD + F) /* {code : 0 .. N_CHAR-1} */ #define T (N_CHAR * 2 - 1) /* size of table */ #define R (T - 1) /* root position */ #define MAX_FREQ 0x8000 /* tree update timing from frequency */ typedef unsigned char uchar; /* TABLE OF DECODE for upper 6bits position information */ /* for decode */ static uchar 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, }; static uchar 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, }; static unsigned freq[T + 1]; /* frequency table */ static int prnt[T + N_CHAR]; /* points to parent node */ /* notes : prnt[T .. T + N_CHAR - 1] used by indicates leaf position that corresponding to code */ static int son[T]; /* points to son node (son[i],son[i+]) */ static unsigned getbuf = 0; static uchar getlen = 0; /* get one bit */ /* returning in Bit 0 */ static int GetBit () { register unsigned int dx = getbuf; register unsigned int c; if (getlen <= 8) { c = getc (infile); if ((int)c < 0) c = 0; dx |= c << (8 - getlen); getlen += 8; } getbuf = dx << 1; getlen--; return (dx & 0x8000) ? 1 : 0; } /* get one byte */ /* returning in Bit7...0 */ static int GetByte () { register unsigned int dx = getbuf; register unsigned c; if (getlen <= 8) { c = getc (infile); if ((int)c < 0) c = 0; dx |= c << (8 - getlen); getlen += 8; } getbuf = dx << 8; getlen -= 8; return (dx >> 8) & 0xff; } /* get N bit */ /* returning in Bit(N-1)...Bit 0 */ static int GetNBits (n) register unsigned int n; { register unsigned int dx = getbuf; register unsigned int c; static int mask[17] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x0fff, 0xffff }; static int shift[17] = { 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }; if (getlen <= 8) { c = getc (infile); if ((int)c < 0) c = 0; dx |= c << (8 - getlen); getlen += 8; } getbuf = dx << n; getlen -= n; return (dx >> shift[n]) & mask[n]; } /* Initialize tree */ static StartHuff () { register 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; getlen = 0; getbuf = 0; } /* reconstruct tree */ static reconst () { register int i, j, k; register unsigned f; /* correct leaf node into of first half, and set these freqency to (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++; } } /* build tree. Link sons first */ 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++; { register unsigned *p, *e; for (p = &freq[j], e = &freq[k]; p > e; p--) p[0] = p[-1]; freq[k] = f; } { register int *p, *e; for (p = &son[j], e = &son[k]; p > e; p--) p[0] = p[-1]; son[k] = i; } } /* link parents */ for (i = 0; i < T; i++) { if ((k = son[i]) >= T) { prnt[k] = i; } else { prnt[k] = prnt[k + 1] = i; } } } /* update given code's frequency, and update tree */ static update (c) unsigned int c; { register unsigned *p; register int i, j, k, l; if (freq[R] == MAX_FREQ) { reconst(); } c = prnt[c + T]; do { k = ++freq[c]; /* swap nodes when become wrong frequency order. */ if (k > freq[l = c + 1]) { for (p = freq+l+1; k > *p++; ) ; l = p - freq - 2; freq[c] = p[-2]; p[-2] = 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); /* loop until reach to root */ } /* static unsigned code, len; */ static int DecodeChar () { register unsigned c; c = son[R]; /* trace from root to leaf, got bit is 0 to small(son[]), 1 to large (son[]+1) son node */ while (c < T) { c += GetBit(); c = son[c]; } c -= T; update(c); return c; } static int DecodePosition () { unsigned i, j, c; /* decode upper 6bit from table */ i = GetByte(); c = (unsigned)d_code[i] << 6; j = d_len[i]; /* get lower 6bit */ j -= 2; return c | (((i << j) | GetNBits (j)) & 0x3f); } static Decode () { static int i, j, k, r, c; if( NotInterruptedCall ) { StartHuff(); for (i = 0; i < N - F; i++) text_buf[i] = ' '; r = N - F; count = 0; } else { NotInterruptedCall = 1; if( PutNum ) { /* Note: cannot use Manx -sf optimization here */ for ( ; k < j; k++) { c = text_buf[(i + k) & (N - 1)]; PUTC_CRC (c); text_buf[r++] = c; r &= (N - 1); count++; if( ForceReturn ) { k++; if( count >= textsize && k >= j ) ForceReturn = 0; PutNum = 1; return; } } } } /* Note: cannot use Manx -sf optimization here */ for ( ; count < textsize; ) { c = DecodeChar(); if (c < 256) { PUTC_CRC (c); text_buf[r++] = c; r &= (N - 1); count++; if( ForceReturn ) { if( count >= textsize ) ForceReturn = 0; PutNum = 0; return; } } else { i = (r - DecodePosition() - 1) & (N - 1); j = c - 255 + THRESHOLD; for (k = 0; k < j; k++) { c = text_buf[(i + k) & (N - 1)]; PUTC_CRC (c); text_buf[r++] = c; r &= (N - 1); count++; if( ForceReturn ) { k++; if( count >= textsize && k >= j ) ForceReturn = 0; PutNum = 1; return; } } } } END_PUTC_CRC (); } /*----------------------------------------------------------------------*/ /* */ /* LARC */ /* */ /*----------------------------------------------------------------------*/ #define F_OLD 18 /* look ahead buffer size for LArc */ /* intialize buffer for LArc type 5 */ static InitBuf () { register unsigned char *p = text_buf; register int i, j; for (i = 0; i < 256; i ++) for (j = 0; j < 13; j ++) *p ++ = i; for (i = 0; i < 256; i ++) *p ++ = i; for (i = 0; i < 256; i ++) *p ++ = 255 - i; for (i = 0; i < 128; i ++) *p ++ = 0; for (i = 0; i < 128; i ++) *p ++ = 0x20; } /* Decode LArc type 5 */ static DecodeOld () { static int si, di; static int dl, dh, al, cx; if( NotInterruptedCall ) { if (textsize == 0) return; InitBuf (); di = N - F_OLD; dl = 0x80; count = 0; } else { NotInterruptedCall = 1; if( PutNum ) { do { text_buf[di] = al = text_buf[si]; PUTC_CRC (al); si = (si + 1) & (N - 1); di = (di + 1) & (N - 1); if( ForceReturn ) { if( count >= textsize && cx == 1 ) ForceReturn = 0; PutNum = 1; return; } } while (--cx != 0) ; } } for ( ; count < textsize; ) { dl = ((dl << 1) | (dl >> 7)) & 0xff; if (dl & 0x01) dh = getc (infile); al = getc (infile); if ((dh & dl) != 0) { PUTC_CRC (al); text_buf[di] = al; di = (di + 1) & (N - 1); count ++; if( ForceReturn ) { if( count >= textsize ) ForceReturn = 0; PutNum = 0; return; } } else { cx = getc (infile); si = (al & 0x00ff) | ((cx << 4) & 0x0f00); cx = (cx & 0x000f) + 3; count += cx; do { text_buf[di] = al = text_buf[si]; PUTC_CRC (al); si = (si + 1) & (N - 1); di = (di + 1) & (N - 1); if( ForceReturn ) { if( count >= textsize && cx == 1 ) ForceReturn = 0; PutNum = 1; return; } } while (--cx != 0) ; } } END_PUTC_CRC (); } int decode_lzhuf (infp, original_size, name) FILE *infp; long original_size; char *name; { if( NotInterruptedCall ) { infile = infp; textsize = original_size; init_crc (); } Decode (); return crc_value; } int decode_larc (infp, original_size, name) FILE *infp; long original_size; char *name; { if( NotInterruptedCall ) { infile = infp; textsize = original_size; init_crc (); } DecodeOld (); return crc_value; }