/*    MPRESS - Compression-Decompression pour Magma
       Dec 96 - Sylvain HUET
*/
// Modification history:
//$ FA(06/06/2001): Includes baselib.h
//
//$LB (27/05/2002) : MGzip and MGunzip functions : compute the size in an unsigned long, instead of int
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "include/vscol.h"
#include "mmemory.h"
#include "mbytec.h"
#include "listlab.h"
#include "baselib.h"


#define CLEARCODE 256
#define EOI 257
#define NBMOTIF 4096

struct Dictcase
{
  int val;
  int pere;
  int fils;
  int frere;
};
typedef struct Dictcase *dictcase;

struct Dict
{
  mmachine m;
  int i;      /* index d'ecriture */
  int imax;
  dictcase tape;
  int im;

  char *buf;

  int IOcodein;  /* code buffer IO in */
  int IObitsin;  /* taille buffer IO in */
  int IOcodeout; /* code buffer IO out */
  int IObitsout; /* taille buffer IO out */
  int tapein;
  int tapeout;
};
typedef struct Dict *dict;


#define MZSZBLOC 1024

int MZaddbloc(mmachine m)
{
  int a,k;

  if (MMpush(m,NIL)) return MERRMEM;
  if (MMpush(m,2*2)) return MERRMEM;
  if (k=MBdeftab(m)) return k;
  // SH000808
  a=MMget(m,1)>>1;
  if (a==NIL) MMset(m,1,MMget(m,0));
  else
  {
	  while(MMfetch(m,a,OFFLNEXT)!=NIL) a=MMfetch(m,a,OFFLNEXT)>>1;
	  MMstore(m,a,OFFLNEXT,MMget(m,0));
  }
  //
  return 0;
}


int Mcharout(dict d,int c)
{
  mmachine m;
  int k,s,sl;

  m=d->m;
  if (d->tapeout>=MZSZBLOC)
    {
      if (k=MZaddbloc(m)) return k;
      d->tapeout=0;
    }
  if (d->tapeout==0)
    {
      sl=(MZSZBLOC+4)>>2;
      s=MMmalloc(m,sl+1,TYPEBUF); if (s==NIL) return MERRMEM;
      MMset(m,0,s+s+1);
    }
  *(MMstartstr(m,MMget(m,0)>>1)+(d->tapeout++))=c;
  MMstore(m,MMget(m,0)>>1,0,d->tapeout);
  return 0;
}

/* envoie nbits bits sur la sortie */
int Mcodeout(dict d, int c)
{
  int nbits,k;

  if (d->i<512) nbits=9;
  else if (d->i<1024) nbits=10;
  else if (d->i<2048) nbits=11;
  else nbits=12;

  d->IOcodeout=(d->IOcodeout<<nbits)+c;
  d->IObitsout+=nbits;
  while(d->IObitsout>=8)
    {
      d->IObitsout-=8;
      if (k=Mcharout(d,(d->IOcodeout>>d->IObitsout)&255)) return k;
    }
  return 0;
}

/* flush le buffer de sortie, en completant avec des 0 */
int Mflushout(dict d)
{
  int k;
  if (d->IObitsout)
    {
      if (k=Mcharout(d,(d->IOcodeout<<(8-d->IObitsout))&255)) return k;
    }
  return MZaddbloc(d->m);
}

int Mcharin(dict d)
{
  mmachine m=d->m;

  if (d->tapein>=MMsizestr(m,MMget(m,2)>>1)) return EOF;
  return (*(MMstartstr(m,MMget(m,2)>>1)+(d->tapein++)))&255;
}

int maskbit[33]=
{0x00000000,0x00000001,0x00000003,0x00000007,
 0x0000000f,0x0000001f,0x0000003f,0x0000007f,
 0x000000ff,0x000001ff,0x000003ff,0x000007ff,
 0x00000fff,0x00001fff,0x00003fff,0x00007fff,
 0x0000ffff,0x0001ffff,0x0003ffff,0x0007ffff,
 0x000fffff,0x001fffff,0x003fffff,0x007fffff,
 0x00ffffff,0x01ffffff,0x03ffffff,0x07ffffff,
 0x0fffffff,0x1fffffff,0x3fffffff,0x7fffffff,
 0xffffffff};

int Mgetcode(dict d)
{
  int i,nbits;

  if (d->i<511) nbits=9;
  else if (d->i<1023) nbits=10;
  else if (d->i<2047) nbits=11;
  else nbits=12;

  while(d->IObitsin<nbits)
    {
      d->IOcodein=(d->IOcodein<<8)+(Mcharin(d)&255);
      d->IObitsin+=8;
    }
  d->IObitsin-=nbits;
  i=(d->IOcodein>>d->IObitsin)&maskbit[nbits];
  return i;
}

int Mbufout(dict d,int i)
{
  int k,size;
  char *p;

  p=&d->buf[d->imax];
  size=0;
  do
	{
	  p--;
	  *p=d->tape[i].val;
	  i=d->tape[i].pere;
	  size++;
	}
  while(i!=-1);

  for(i=0;i<size;i++) if (k=Mcharout(d,*(p++))) return k;
  return 0;
}

/* ajoute un motif : retourne le numero du motif ou -1 si erreur */
int Madddict(dict d, int val, int pere)
{
  if (d->i>=d->imax) return -1;

  d->tape[d->i].val=val;
  d->tape[d->i].pere=pere;
  d->tape[d->i].fils=-1;
  if (pere!=-1)
    {
      d->tape[d->i].frere=d->tape[pere].fils;
      d->tape[pere].fils=d->i;
    }
  else d->tape[d->i].frere=-1;
  d->i++;
  return d->i-1;
}

/* initialise le dictionnaire */
int Minidict(dict d)
{
  int i;
  
/*  MMechostr(MSKDEBUG,"reinitdict\n");*/
  d->i=0;
  d->im=-1;
  for(i=0;i<256;i++) Madddict(d,i,-1);
  Madddict(d,0,-1);  /* CLEARCODE */
  Madddict(d,0,-1);  /* EOI */
  return 0;
}

/* ouvre le dictionnaire, fait les mallocs */
int Mopendict(dict d, int nbcase)
{
  d->imax=nbcase;
  d->tape=(dictcase)malloc(sizeof(struct Dictcase)*nbcase);
  if (d->tape==NULL) return -1;

  d->buf=(char*)malloc(nbcase);
  if (d->buf==NULL)
  {
	  free((void*)d->tape);
	  return -1;
  }
  return 0;
}

/* ferme le dictionnaire, fait les free */
int Mclosedict(dict d)
{
  free((void*)d->tape);
  free((void*)d->buf);
  return 0;
}

/* cherche un motif, retourne son index ou -1 si introuvable */
int Mfindmotif(dict d,int c,int pere)
{
  int i;

  i=d->tape[pere].fils;
  while(i!=-1)
    {
      if (d->tape[i].val==c) return i;
      i=d->tape[i].frere;
    }
  return -1;
}

/* traite un nouveau caractere */
int Maddchar(dict d,int c)
{
  int k;

  if (d->im==-1) k=c&255;
  else k=Mfindmotif(d,c&255,d->im);
  if (k!=-1)
    {
      d->im=k;
      return 0;
    }
  if (Mcodeout(d,d->im)) return -1;
  if (Madddict(d,c&255,d->im)<0)
    {
      d->i++;
      if (Mcodeout(d,CLEARCODE)) return -1;
      d->i--;
      Minidict(d);
    }
  d->im=c&255;
  return 0;
}

/* fin du message */
int Mlastchar(dict d)
{
  if (d->im!=-1)
    {
      if (Mcodeout(d,d->im)) return -1;
      d->i++;
    }
  if (Mcodeout(d,EOI)) return -1;
  return Mflushout(d);
}

int Mbigfather(dict d,int i)
{
	while(d->tape[i].pere!=-1)
		i=d->tape[i].pere;
	return i;
}

/* traite un nouveau code */
int Mxcode(dict d,int c)
{
  if (c==CLEARCODE)
    {
      Minidict(d);
      return 0;
    }
  if (d->im==-1)  /* debut segment */
    {
      if ((c<0)||(c>=d->i)) return -1;
      if (Mbufout(d,c)) return -1;
      d->im=c;
      return 0;
    }

  if ((c>=0)&&(c<d->i))
    {
      if (Mbufout(d,c)) return -1;
      Madddict(d,d->tape[Mbigfather(d,c)].val,d->im);
      d->im=c;
      return 0;
    }
  else if (c!=d->i)
  {
	  return -1;
  }
  if (Madddict(d,d->tape[Mbigfather(d,d->im)].val,d->im)>=0)
    {
      if (Mbufout(d,c)) return -1;
      d->im=c;
    }
  return 0;
}

int MZcompress2(mmachine m)
{
  int c,k,a,b;
  struct Dict d;

  if (MMget(m,0)==NIL) return 0;

  if (MMpush(m,NIL)) return MERRMEM;
  if (MMpush(m,NIL)) return MERRMEM;

  d.IObitsin=0;
  d.IObitsout=0;
  d.tapein=0;
  d.tapeout=0;
  d.m=m;
  if (k=Mopendict(&d,NBMOTIF)) return k;
  Minidict(&d);
  while((c=Mcharin(&d))!=EOF)
    {
      if (k=Maddchar(&d,c))
        {
          Mclosedict(&d);
          return k;
        }
    }
  if (k=Mlastchar(&d))
    {
      Mclosedict(&d);
      return k;
    }
  Mclosedict(&d);
  MMpull(m);
  if (k=MBstrcatn(m)) return k;
  a=MMsizestr(m,MMget(m,0)>>1);
  b=MMsizestr(m,MMget(m,1)>>1);
  MMechostr(MSKDEBUG,"crunching result :%d/%d\n",a,b);
  if (b>=a)
    {
	  if (k=Mpushstrbloc(m,"Mzip")) return k;
	  MMset(m,2,MMget(m,0));
	  MMpull(m);
	  return MBstrcat(m);
    }
  MMset(m,0,MMget(m,1));
  if (k=Mpushstrbloc(m,"mzip")) return k;
  MMset(m,2,MMget(m,0));
  MMpull(m);
  return MBstrcat(m);
}

int MZcompress(mmachine m)
{
  int pp;

  pp=MMgetPP(m);
  if (MZcompress2(m))
    {
	  MMechostr(MSKDEBUG,"error on crunching\n");
	  MMsetPP(m,pp);
	  MMset(m,0,NIL);
	  return 0;
    }
  return 0;
}

int MZuncompress2(mmachine m)
{
  int c,k;
  struct Dict d;

  if (MMget(m,0)==NIL) return 0;

  if (MMpush(m,NIL)) return MERRMEM;
  if (MMpush(m,NIL)) return MERRMEM;

  d.IObitsin=0;
  d.IObitsout=0;
  d.tapein=0;
  d.tapeout=0;
  d.m=m;
  c=Mcharin(&d);
  if ((c!='M')&&(c!='m')) return MERRTYP;
  if (Mcharin(&d)!='z') return MERRTYP;
  if (Mcharin(&d)!='i') return MERRTYP;
  if (Mcharin(&d)!='p') return MERRTYP;

  if (c=='M')
    {
	  if (k=Mopendict(&d,NBMOTIF)) return k;
      Minidict(&d);
      do
        {
          c=Mgetcode(&d);
          if ((c!=EOI)&&(k=Mxcode(&d,c)))
            {
              Mclosedict(&d);
              return k;
            }
        }
      while(c!=EOI);
      Mclosedict(&d);
    }
  else
	while((c=Mcharin(&d))!=EOF) Mcharout(&d,c);

  if (k=MZaddbloc(m)) return k;
  MMset(m,2,MMget(m,1));
  MMpull(m); MMpull(m);
  return MBstrcatn(m);
}

int MZuncompress(mmachine m)
{
  int pp;

  pp=MMgetPP(m);
  if (MZuncompress2(m))
    {
	  MMechostr(MSKDEBUG,"error on decrunching\n");
	  MMsetPP(m,pp);
	  MMset(m,0,NIL);
	  return 0;
    }
  return 0;
}

#ifdef VERSION_X11
  #include <zlib.h>   /* Linux-X11 */
#else
  #include "zlib/zlib.h"   /* Win32, Linux/SunOS-noX */
#endif



//$LB (27/05/2002) : compute the size in an unsigned long, instead of int
int MGzip(mmachine m)
{
	int p,s,err,k;
	unsigned long l, nl, effl;
	char *z;

	p=MMget(m,0)>>1;;
	if (p==NIL) return 0;
	l=MMsizestr(m,p);
	nl=20+(102*l)/100;
	s=MMmalloc(m,(nl>>2)+2,TYPEBUF); if (s==NIL) return MERRMEM;
	p=MMget(m,0)>>1;;
	z=MMstartstr(m,s);
	z[0]='_';z[1]='Z';z[2]='I';z[3]='P';
	effl=nl-8;
	err=compress(z+8,&effl,MMstartstr(m,p),l);
	if (err != Z_OK)
	{
		MMset(m,0,NIL);
		MMechostr(MSKDEBUG,"zip error %d\n",err);
		return 0;
	}
	k=l&255; z[4]=k;
	k=(l>>8)&255; z[5]=k;
	k=(l>>16)&255; z[6]=k;
	k=(l>>24)&255; z[7]=k;
	MMsetsizestr(m,s,effl+8);
	MMechostr(MSKDEBUG,"zip %d/%d\n",effl+8,l);
	MMset(m,0,s+s+1);
	return MBstrdup(m);
}
 
int MGunzip(mmachine m)
{
	int p,s,err,k;
	unsigned long effl, l;
	char *z;

	p=MMget(m,0)>>1;;
	if (p==NIL) return 0;
	if (MMsizestr(m,p)<8)
	{
		MMset(m,0,NIL);
		return 0;
	}
	z=MMstartstr(m,p);
	if ((z[0]!='_')||(z[1]!='Z')||(z[2]!='I')||(z[3]!='P'))
	{
		MMset(m,0,NIL);
		MMechostr(MSKDEBUG,"not a zip file\n");
		return 0;
	}

	k=z[4]&255; l=k;
	k=z[5]&255; l+=(k<<8);
	k=z[6]&255; l+=(k<<16);
	k=z[7]&255; l+=(k<<24);

	s=MMmalloc(m,(l>>2)+2,TYPEBUF); if (s==NIL) return MERRMEM;

	p=MMget(m,0)>>1;;
	z=MMstartstr(m,p);
	effl=l;
	err=  uncompress(MMstartstr(m,s),&effl,z+8,MMsizestr(m,p)-8);
	if (err != Z_OK)
	{
		MMset(m,0,NIL);
		MMechostr(MSKDEBUG,"unzip error %d\n",err);
		return 0;
	}
	MMsetsizestr(m,s,effl);
	MMechostr(MSKDEBUG,"unzip %d/%d\n",effl,MMsizestr(m,p));
	MMset(m,0,s+s+1);
	return 0;
}


//$BLG
//Huffman part from http://bcl.sourceforge.net/
//Complete sourcecode, doc & license included in sub directory

/*************************************************************************
* Types used for Huffman coding
*************************************************************************/

typedef struct {
    unsigned int Symbol;
    unsigned int Count;
    unsigned int Code;
    unsigned int Bits;
} huff_sym_t;

typedef struct {
    unsigned char *BytePtr;
    unsigned int  BitPos;
} huff_bitstream_t;



/*************************************************************************
*                           INTERNAL FUNCTIONS                           *
*************************************************************************/


/*************************************************************************
* _Huffman_InitBitstream() - Initialize a bitstream.
*************************************************************************/

static void _Huffman_InitBitstream( huff_bitstream_t *stream,
    unsigned char *buf )
{
    stream->BytePtr  = buf;
    stream->BitPos   = 0;
}


/*************************************************************************
* _Huffman_ReadBits() - Read bits from a bitstream.
*************************************************************************/

static unsigned int _Huffman_ReadBits( huff_bitstream_t *stream,
    unsigned int bits )
{
    unsigned int  x, bit, count;
    unsigned char *buf;

    /* Get current stream state */
    buf = stream->BytePtr;
    bit = stream->BitPos;

    /* Extract bits */
    x = 0;
    for( count = 0; count < bits; ++ count )
    {
        x = (x<<1) + (*buf & (1<<(7-bit)) ? 1 : 0);
        bit = (bit+1) & 7;
        if( !bit )
        {
            ++ buf;
        }
    }

    /* Store new stream state */
    stream->BytePtr = buf;
    stream->BitPos  = bit;

    return x;
}


/*************************************************************************
* _Huffman_WriteBits() - Write bits to a bitstream.
*************************************************************************/

static void _Huffman_WriteBits( huff_bitstream_t *stream, unsigned int x,
    unsigned int bits )
{
    unsigned int  bit, count;
    unsigned char *buf;
    unsigned int  mask;

    /* Get current stream state */
    buf = stream->BytePtr;
    bit = stream->BitPos;

    /* Append bits */
    mask = 1 << (bits-1);
    for( count = 0; count < bits; ++ count )
    {
        *buf = (*buf & (0xff^(1<<(7-bit)))) +
               ((x & mask ? 1 : 0) << (7-bit));
        x <<= 1;
        bit = (bit+1) & 7;
        if( !bit )
        {
            ++ buf;
        }
    }

    /* Store new stream state */
    stream->BytePtr = buf;
    stream->BitPos  = bit;
}


/*************************************************************************
* _Huffman_Hist() - Calculate (sorted) histogram for a block of data.
*************************************************************************/

static void _Huffman_Hist( unsigned char *in, huff_sym_t *sym,
    unsigned int size )
{
    int k, swaps;
    huff_sym_t tmp;

    /* Clear/init histogram */
    for( k = 0; k < 256; ++ k )
    {
        sym[k].Symbol = k;
        sym[k].Count  = 0;
        sym[k].Code   = 0;
        sym[k].Bits   = 0;
    }

    /* Build histogram */
    for( k = size; k; -- k )
    {
        sym[ *in ++ ].Count ++;
    }

    /* Sort histogram - most frequent symbol first (bubble sort) */
    do
    {
        swaps = 0;
        for( k = 0; k < 255; ++ k )
        {
            if( sym[k].Count < sym[k+1].Count )
            {
                tmp      = sym[k];
                sym[k]   = sym[k+1];
                sym[k+1] = tmp;
                swaps    = 1;
            }
        }
    }
    while( swaps );
}


/*************************************************************************
* _Huffman_MakeTree() - Generate a Huffman tree.
*************************************************************************/

static void _Huffman_MakeTree( huff_sym_t *sym, huff_bitstream_t *stream,
    unsigned int code, unsigned int bits, unsigned int first,
    unsigned int last )
{
    unsigned int k, size, size_a, size_b, last_a, first_b;

    /* Is this a leaf node? */
    if( first == last )
    {
        /* Append symbol to tree description */
        _Huffman_WriteBits( stream, 1, 1 );
        _Huffman_WriteBits( stream, sym[first].Symbol, 8 );

        /* Store code info in symbol array */
        sym[first].Code = code;
        sym[first].Bits = bits;
        return;
    }
    else
    {
        /* This was not a leaf node */
        _Huffman_WriteBits( stream, 0, 1 );
    }

    /* Total size of interval */
    size = 0;
    for( k = first; k <= last; ++ k )
    {
        size += sym[k].Count;
    }

    /* Find size of branch a */
    size_a = 0;
    for( k = first; size_a < ((size+1)>>1) && k < last; ++ k )
    {
        size_a += sym[k].Count;
    }

    /* Non-empty branch? */
    if( size_a > 0 )
    {
        /* Continue branching */
        _Huffman_WriteBits( stream, 1, 1 );

        /* Branch a cut in histogram */
        last_a  = k-1;

        /* Create branch a */
        _Huffman_MakeTree( sym, stream, (code<<1)+0, bits+1,
                               first, last_a );
    }
    else
    {
        /* This was an empty branch */
        _Huffman_WriteBits( stream, 0, 1 );
    }

    /* Size of branch b */
    size_b = size - size_a;

    /* Non-empty branch? */
    if( size_b > 0 )
    {
        /* Continue branching */
        _Huffman_WriteBits( stream, 1, 1 );

        /* Branch b cut in histogram */
        first_b = k;

        /* Create branch b */
        _Huffman_MakeTree( sym, stream, (code<<1)+1, bits+1,
                               first_b, last );
    }
    else
    {
        /* This was an empty branch */
        _Huffman_WriteBits( stream, 0, 1 );
    }
}


/*************************************************************************
* _Huffman_RecoverTree() - Recover a Huffman tree from a bitstream.
*************************************************************************/

static void _Huffman_RecoverTree( huff_sym_t *sym,
    huff_bitstream_t *stream, unsigned int code, unsigned int bits,
    unsigned int *symnum )
{
    unsigned int symbol;

    /* Is this a leaf node? */
    if( _Huffman_ReadBits( stream, 1 ) )
    {
        /* Get symbol from tree description */
        symbol = _Huffman_ReadBits( stream, 8 );

        /* Store code info in symbol array */
        sym[*symnum].Symbol = symbol;
        sym[*symnum].Code   = code;
        sym[*symnum].Bits   = bits;

        /* Increase symbol counter */
        *symnum = *symnum + 1;

        return;
    }

    /* Non-empty branch? */
    if( _Huffman_ReadBits( stream, 1 ) )
    {
        /* Create branch a */
        _Huffman_RecoverTree( sym, stream, (code<<1)+0, bits+1,
                              symnum );
    }

    /* Non-empty branch? */
    if( _Huffman_ReadBits( stream, 1 ) )
    {
        /* Create branch b */
        _Huffman_RecoverTree( sym, stream, (code<<1)+1, bits+1,
                              symnum );
    }
}




/*************************************************************************
*                            PUBLIC FUNCTIONS                            *
*************************************************************************/


/*************************************************************************
* Huffman_Compress() - Compress a block of data using a Huffman coder.
*  in     - Input (uncompressed) buffer.
*  out    - Output (compressed) buffer. This buffer must be 384 bytes
*           larger than the input buffer.
*  insize - Number of input bytes.
* The function returns the size of the compressed data.
*************************************************************************/

int Huffman_Compress( unsigned char *in, unsigned char *out,
    unsigned int insize )
{
    huff_sym_t       sym[ 256 ], tmp;
    huff_bitstream_t stream;
    unsigned int     k, total_bytes, swaps, symbol, last_symbol;

    /* Do we have anything to compress? */
    if( insize < 1 ) return 0;

    /* Initialize bitstream */
    _Huffman_InitBitstream( &stream, out );

    /* Calculate and sort histogram for input data */
    _Huffman_Hist( in, sym, insize );

    /* Find number of used symbols */
    for( last_symbol = 255; sym[last_symbol].Count == 0; -- last_symbol );

    /* Special case: In order to build a correct tree, we need at least
       two symbols (otherwise we get zero-bit representations). */
    if( last_symbol == 0 ) ++ last_symbol;

    /* Build Huffman tree */
    _Huffman_MakeTree( sym, &stream, 0, 0, 0, last_symbol );

    /* Was any code > 32 bits? (we do not handle that at present) */
    for( k = 0; k < 255; ++ k )
    {
        if( sym[k].Bits > 32 )
        {
            return 0;
        }
    }

    /* Sort histogram - first symbol first (bubble sort) */
    do
    {
        swaps = 0;
        for( k = 0; k < 255; ++ k )
        {
            if( sym[k].Symbol > sym[k+1].Symbol )
            {
                tmp      = sym[k];
                sym[k]   = sym[k+1];
                sym[k+1] = tmp;
                swaps    = 1;
            }
        }
    }
    while( swaps );

    /* Encode input stream */
    for( k = 0; k < insize; ++ k )
    {
        symbol = in[ k ];
        _Huffman_WriteBits( &stream, sym[symbol].Code,
                            sym[symbol].Bits );
    }

    /* Calculate size of output data */
    total_bytes = (int)(stream.BytePtr - out);
    if( stream.BitPos > 0 )
    {
        ++ total_bytes;
    }

    return total_bytes;
}


/*************************************************************************
* Huffman_Uncompress() - Uncompress a block of data using a Huffman
* decoder.
*  in      - Input (compressed) buffer.
*  out     - Output (uncompressed) buffer. This buffer must be large
*            enough to hold the uncompressed data.
*  insize  - Number of input bytes.
*  outsize - Number of output bytes.
*************************************************************************/

void Huffman_Uncompress( unsigned char *in, unsigned char *out,
    unsigned int insize, unsigned int outsize )
{
    huff_sym_t       sym[ 256 ], tmp;
    huff_bitstream_t stream;
    unsigned int     k, m, symbol_count, swaps;
    unsigned char    *buf;
    unsigned int     bits, delta_bits, new_bits, code;

    /* Do we have anything to decompress? */
    if( insize < 1 ) return;

    /* Initialize bitstream */
    _Huffman_InitBitstream( &stream, in );

    /* Clear tree/histogram */
    for( k = 0; k < 256; ++ k )
    {
        sym[k].Bits = 0x7fffffff;
    }

    /* Recover Huffman tree */
    symbol_count = 0;
    _Huffman_RecoverTree( sym, &stream, 0, 0, &symbol_count );

    /* Sort histogram - shortest code first (bubble sort) */
    do
    {
        swaps = 0;
        for( k = 0; k < symbol_count-1; ++ k )
        {
            if( sym[k].Bits > sym[k+1].Bits )
            {
                tmp      = sym[k];
                sym[k]   = sym[k+1];
                sym[k+1] = tmp;
                swaps    = 1;
            }
        }
    }
    while( swaps );

    /* Decode input stream */
    buf = out;
    for( k = 0; k < outsize; ++ k )
    {
        /* Search tree for matching code */
        bits = 0;
        code = 0;
        for( m = 0; m < symbol_count; ++ m )
        {
            delta_bits = sym[m].Bits - bits;
            if( delta_bits )
            {
                new_bits = _Huffman_ReadBits( &stream, delta_bits );
                code = code | (new_bits << (32-bits-delta_bits));
                bits = sym[m].Bits;
            }
            if( code == (sym[m].Code << (32-sym[m].Bits)) )
            {
                *buf ++ = (unsigned char) sym[m].Symbol;
                break;
            }
        }
    }
}



int MHzip(mmachine m)
{
	int p,s,err,k;
	unsigned long l, nl, effl;
	char *z;

	//Retrieving S param
	p=MMget(m,0)>>1;;
	if (p==NIL) return 0;
	l=MMsizestr(m,p);
	//Output buffer creation, zippped data header
	//nl=20+(102*l)/100;
	nl = 8 + (l*104+50)/100 + 384;
	s=MMmalloc(m,(nl>>2)+2,TYPEBUF); 
	if (s==NIL) return MERRMEM;
	p=MMget(m,0)>>1;;
	z=MMstartstr(m,s);
	z[0]='_';z[1]='H';z[2]='Z';z[3]='P';
	/*
	effl=nl-8;
	err=compress(z+8,&effl,MMstartstr(m,p),l);
	if (err != Z_OK)
	{
		MMset(m,0,NIL);
		MMechostr(MSKDEBUG,"zip error %d\n",err);
		return 0;
	}
	*/
	//Compress and add original size info
	effl = 8 + Huffman_Compress( MMstartstr(m,p), z+8, l );
	k=l&255; z[4]=k;
	k=(l>>8)&255; z[5]=k;
	k=(l>>16)&255; z[6]=k;
	k=(l>>24)&255; z[7]=k;
	//Return zipped S
	MMsetsizestr(m,s,effl);
	MMechostr(MSKDEBUG,"zip %d/%d\n",effl,l);
	MMset(m,0,s+s+1);
	return MBstrdup(m);
}

int MHunzip(mmachine m)
{
	int p,s,err,k;
	unsigned long effl, l;
	char *z;

	//Retrieving S param and checking zipped status
	p=MMget(m,0)>>1;;
	if (p==NIL) return 0;
	if (MMsizestr(m,p)<8)
	{
		MMset(m,0,NIL);
		return 0;
	}
	z=MMstartstr(m,p);
	if ((z[0]!='_')||(z[1]!='H')||(z[2]!='Z')||(z[3]!='P'))
	{
		MMset(m,0,NIL);
		MMechostr(MSKDEBUG,"not a zip file\n");
		return 0;
	}

  // Retrieving original S size and allocating buffer
	k=z[4]&255; l=k;
	k=z[5]&255; l+=(k<<8);
	k=z[6]&255; l+=(k<<16);
	k=z[7]&255; l+=(k<<24);
	s=MMmalloc(m,(l>>2)+2,TYPEBUF); 
	if (s==NIL) return MERRMEM;

	p=MMget(m,0)>>1;;
	z=MMstartstr(m,p);
	effl=l;
	/*
	err=  uncompress(MMstartstr(m,s),&effl,z+8,MMsizestr(m,p)-8);
	if (err != Z_OK)
	{
		MMset(m,0,NIL);
		MMechostr(MSKDEBUG,"unzip error %d\n",err);
		return 0;
	}
	*/
	//Uncompress data
	Huffman_Uncompress( z+8, MMstartstr(m,s), MMsizestr(m,p)-8, effl );
	//Return unzipped S
	MMsetsizestr(m,s,effl);
	MMechostr(MSKDEBUG,"unzip %d/%d\n",effl,MMsizestr(m,p));
	MMset(m,0,s+s+1);
	return 0;
}