/*
 * freeze.c  -  compress the bootrom image
 *
 * Copyright (C) 1997,1998 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.
 */

#include "common.h"
#include "nblib.h"
#include "makerom.h"
#include "freeze.h"



/*
 * Local variables
 */
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 unsigned char inbuf[BLKSIZE];	/* Input buffer */
static unsigned char outbuf[BLKSIZE];	/* Output buffer */
static int infile;
static int outfile;



/*
 * Write a character into the output file
 */
static void charout(c)
unsigned char c;
{
  outbuf[outptr++] = c;
  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++]);
}



/*
 **************************************************************************
 *
 *		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((int)(b >> 8));
	if ((len -= 8) >= 8) {
		charout((int)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((unsigned char)(i & 0xff));
  charout((unsigned char)((i >> 8) & 0x7f));
  charout((unsigned char)(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((int)(bitbuf >> 8));
  if (outptr > 0)
	outsize += nbwrite(outbuf, (unsigned int)outptr, outfile);
  return(outsize);
}