/*
* freeze.c - compress the bootrom image
*
* Copyright (C) 1997-2003 Gero Kuhlmann <gero@gkminix.han.de>
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*
**************************************************************************
*
* Parts of this file have been taken from source code published by
* leo@s514.ipmce.su without any copyright information.
*
* $Id: freeze.c,v 1.4 2003/01/25 23:29:42 gkminix Exp $
*/
#include <common.h>
#include <nblib.h>
#include "makerom.h"
#include "freeze.h"
/*
* Local variables
*/
static int infile; /* Input file handle */
static int outfile; /* Output file handle */
static int inptr = -1, outptr = 0; /* Pointers into I/O buffers */
static int insize = BLKSIZE; /* Number of bytes in input buffer */
static unsigned long outsize = 0; /* Number of bytes written */
static __u8 inbuf[BLKSIZE]; /* Input buffer */
static __u8 outbuf[BLKSIZE]; /* Output buffer */
/*
* Write a character into the output file
*/
static void charout(c)
short c;
{
outbuf[outptr++] = (c & 0xff);
if (outptr >= BLKSIZE) {
outsize += nbwrite(outbuf, BLKSIZE, outfile);
outptr = 0;
}
}
/*
* Read a character from the input file
*/
static short charin()
{
if (inptr < 0 || inptr >= insize) {
if (insize < BLKSIZE)
return(EOF);
if ((insize = nbread(inbuf, BLKSIZE, infile)) <= 0)
return(EOF);
inptr = 0;
}
return(inbuf[inptr++] & 0xff);
}
/*
**************************************************************************
*
* LZSS ENCODING
*
**************************************************************************
*/
/*
* Most of this is actually included within preprocessor macros, which are
* defined in freeze.h. There is just one routine left here besides the
* definition of the encoding tables. Note that with systems which cannot
* access data structures larger than 64kB (like MSDOS or XENIX) we have
* to split the large tables into several parts.
*/
static unsigned char text_buf[BUFSIZE + PRESENSE - 1];
static unsigned short match_position, match_length;
static hash_t prev[BUFSIZE + 1];
#if !defined(__XENIX__) && !defined(MSDOS)
static unsigned short next[array_size];
#else
# if parts == 2
static unsigned short next0[32768], next1[8193];
# else
# if parts == 3
static unsigned short next0[32768], next1[32768], next2[8193];
# else
# if parts == 5
static unsigned short next0[32768], next1[32768], next2[32768], next3[32768],
next4[8193];
# else
static unsigned short next0[32768], next1[32768], next2[32768], next3[32768],
next4[32768], next5[32768], next6[32768], next7[32768],
next8[8193];
# endif
# endif
# endif
static unsigned short *next[parts] = {
next0, next1
# if parts > 2
,next2
# if parts > 3
,next3, next4
# if parts > 5
,next5, next6, next7, next8
# endif
# endif
# endif
};
#endif
/*
* Get next match
*/
static void Get_Next_Match(r)
unsigned short r;
{
register unsigned short p = r;
register int m;
unsigned char *key = text_buf + r;
unsigned char *pattern;
match_length = 0;
do {
do {
if ((p = nextof(p)) == _NIL)
return;
pattern = text_buf + p;
for (m = match_length; m >= 0 && key[m] == pattern[m]; m--) ;
} while (m >= 0);
for (m = match_length; ++m < PRESENSE && key[m] == pattern[m]; ) ;
match_length = m;
match_position = ((r - p) & (BUFSIZE - 1)) - 1;
} while (m < PRESENSE);
nextof(prev[p]) = nextof(p);
prev[nextof(p)] = prev[p];
prev[p] = _NIL; /* Remove p, it is further than r */
}
/*
**************************************************************************
*
* HUFFMAN ENCODING
*
**************************************************************************
*/
/*
* TABLE OF ENCODE for upper 6 bits position information. It has been
* optimized for the bootrom images.
*/
#ifdef USE_ORIG_TABLE
static unsigned char Table[9] = { 0, 0, 1, 1, 1, 4, 10, 27, 18 };
#else
static unsigned char Table[9] = { 0, 0, 1, 1, 2, 3, 11, 16, 28 };
#endif
static unsigned char p_len[64];
static unsigned char code[256];
#define MAX_FREQ (unsigned short)0x8000 /* tree update timing from frequency */
static unsigned short freq[TABSIZE + 1]; /* frequency table */
static short prnt[TABSIZE + _NCHAR]; /* points to parent node */
static short son[TABSIZE]; /* points to son node */
static unsigned short bitbuf = 0;
static unsigned char bitlen = 0;
/*
* Update given code's frequency, and update Huffmann tree
*/
static void update(c)
unsigned short c;
{
register unsigned short *p;
register unsigned short i, j, k, l;
/* Reconstruct tree */
if (freq[ROOTPOS] == MAX_FREQ) {
/*
* Correct leaf node into of first half,
* and set these freqency to (freq+1)/2
*/
j = 0;
for (i = 0; i < TABSIZE; i++) {
if (son[i] >= TABSIZE) {
freq[j] = (freq[i] + 1) / 2;
son[j] = son[i];
j++;
}
}
/* Build tree. Link sons first */
for (i = 0, j = _NCHAR; j < TABSIZE; i += 2, j++) {
k = i + 1;
l = freq[j] = freq[i] + freq[k];
for (k = j - 1; l < freq[k]; k--);
k++;
{
register unsigned short *p, *e;
for (p = &freq[j], e = &freq[k]; p > e; p--)
p[0] = p[-1];
freq[k] = l;
}
{
register short *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 < TABSIZE; i++) {
if ((k = son[i]) >= TABSIZE)
prnt[k] = i;
else
prnt[k] = prnt[k + 1] = i;
}
}
/* Update tree and frequencies */
c = prnt[c + TABSIZE];
do {
k = ++freq[c];
/* Swap nodes when we get a 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 < TABSIZE)
prnt[i + 1] = l;
j = son[l];
son[l] = i;
prnt[j] = c;
if (j < TABSIZE)
prnt[j + 1] = c;
son[c] = j;
c = l;
}
} while ((c = prnt[c]) != 0); /* loop until we reach root */
}
/*
* Output C bits
*/
static void Putcode(l, c)
unsigned short l;
unsigned short c;
{
register unsigned short len = bitlen;
register unsigned short b = bitbuf;
b |= c >> len;
if ((len += l) >= 8) {
charout((short)(b >> 8));
if ((len -= 8) >= 8) {
charout((short)b);
len -= 8;
b = c << (l - len);
} else {
b <<= 8;
}
}
bitbuf = b;
bitlen = len;
}
/*
* Encode character
*/
static void EncodeChar(c)
unsigned short c;
{
register short *p;
unsigned long i;
register unsigned short j, k;
i = 0;
j = 0;
p = prnt;
k = p[c + TABSIZE];
/* trace links from leaf node to root */
do {
i >>= 1;
/* if node index is odd, trace larger of sons */
if (k & 1) i += (unsigned long)0x80000000L;
j++;
} while ((k = p[k]) != ROOTPOS) ;
if (j > 16) {
Putcode(16, (unsigned short)(i >> 16));
Putcode(j - 16, (unsigned short)i);
} else {
Putcode(j, (unsigned short)(i >> 16));
}
update(c);
}
/*
* Encode code position in Huffmann tree
*/
static void EncodePosition(c)
unsigned short c;
{
register unsigned short i;
/* output upper 6bit from table */
i = c >> 7;
Putcode((unsigned short)(p_len[i]), (unsigned short)(code[i]) << 8);
/* output lower 7bit */
Putcode(7, (unsigned short)(c & 0x7f) << 9);
}
/*
* Initialize the Huffmann encoding tree
*/
static void StartHuff()
{
register short i, j, k, num;
num = 0;
for(i = 1, j = 0; i <= 8; i++) {
num += Table[i] << (8 - i);
for(k = Table[i]; k; j++, k--)
p_len[j] = i;
}
num = j;
for(i = j = 0; ; ) {
code[j] = i << (8 - p_len[j]);
i++;
j++;
if(j == num)
break;
i <<= p_len[j] - p_len[j-1];
}
for (i = 0; i < _NCHAR; i++) {
freq[i] = 1;
son[i] = i + TABSIZE;
prnt[i + TABSIZE] = i;
}
i = 0;
j = _NCHAR;
while (j <= ROOTPOS) {
freq[j] = freq[i] + freq[i + 1];
son[j] = i;
prnt[i] = prnt[i + 1] = j;
i += 2;
j++;
}
freq[TABSIZE] = 0xffff;
prnt[ROOTPOS] = 0;
bitlen = 0;
bitbuf = 0;
}
/*
* Main freezing routine
*/
unsigned long freeze(inf, outf)
int inf;
int outf;
{
long l;
register unsigned short i, len, r, s;
register short c;
/* Initialize global variables */
infile = inf;
inptr = -1;
insize = BLKSIZE;
outptr = 0;
outsize = 0;
outfile = outf;
/* Initialize the Huffman encoding tree */
StartHuff();
/* Write freeze compression header */
i = Table[5] & 0x1f; i <<= 4;
i |= Table[4] & 0x0f; i <<= 3;
i |= Table[3] & 0x07; i <<= 2;
i |= Table[2] & 0x03; i <<= 1;
i |= Table[1] & 0x01;
charout((short)(i & 0xff));
charout((short)((i >> 8) & 0x7f));
charout((short)(Table[6] & 0x3f));
/* Setup the LZSS encoding tree */
for (l = BUFSIZE + 1; l < array_size; l++)
nextof(l) = _NIL;
for (l = 0; l < (sizeof(prev) / sizeof(*prev)); l++)
prev[l] = _NIL;
/* Preset the text buffer with data from input stream */
s = 0;
r = BUFSIZE - PRESENSE;
for (i = s; i < r; i++)
text_buf[i] = ' ';
for (len = 0; len < PRESENSE && (c = charin()) != EOF; len++)
text_buf[r + len] = c;
for (i = 0; i <= PRESENSE; i++)
InsertNode(r + i - PRESENSE);
/* Encode the remainder of the input data */
while (len != 0) {
Get_Next_Match(r);
if (match_length > len)
match_length = len;
if (match_length <= THRESHOLD) {
match_length = 1;
EncodeChar(text_buf[r]);
} else {
register unsigned short orig_length, orig_position, oldchar;
oldchar = text_buf[r];
orig_length = match_length;
orig_position = match_position;
DeleteNode(s);
Next_Char();
Get_Next_Match(r);
if (match_length > len)
match_length = len;
if (orig_length > match_length) {
EncodeChar((unsigned short)
(256 - THRESHOLD + orig_length));
EncodePosition((unsigned short)orig_position);
match_length = orig_length - 1;
} else {
EncodeChar(oldchar);
EncodeChar(256 - THRESHOLD + match_length);
EncodePosition(match_position);
}
}
for (i = 0; i < match_length && (c = charin()) != EOF; i++) {
DeleteNode(s);
text_buf[s] = c;
if (s < PRESENSE - 1)
text_buf[s + BUFSIZE] = c;
s = (s + 1) & (BUFSIZE - 1);
r = (r + 1) & (BUFSIZE - 1);
InsertNode(r);
}
while (i++ < match_length) {
DeleteNode(s);
s = (s + 1) & (BUFSIZE - 1);
r = (r + 1) & (BUFSIZE - 1);
if (--len) InsertNode(r);
}
}
EncodeChar((short)ENDOF);
/* Flush the output buffer */
if (bitlen)
charout((short)(bitbuf >> 8));
if (outptr > 0) {
assert(outptr <= BUFSIZE);
outsize += nbwrite(outbuf, (int)outptr, outfile);
}
return(outsize);
}
syntax highlighted by Code2HTML, v. 0.9.1