/* * freeze.c - compress the bootrom image * * Copyright (C) 1997-2003 Gero Kuhlmann * * 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 #include #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); }