/**-----------------------------------------------------------------------
  *   Bloque de includes, por fin me ocupan menos de una pagina de
  * impresisn, lo que hay que hacer para tener todos los prototipos..
  *
  **/

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

#define NO_SUB_PRAGMAS
#include <libraries/xpksub.h>

#include "bitio.h"      /* custom includes */

/**-----------------------------------------------------------------------
  *   Bloque de constantes 'NEMOTECNICAS' para una mejor simplicidad
  * de csdigo, lo siento si alguien cree que tengo demasiada tendencia
  * a las palabras de origen sajsn, pero no puedo sufrir versiones 
  * castellanas ni catalanas. Sera la costumbre.
  *
  **/

#define TRUE                  1
#define FALSE                 0
#define NIL                   0
#define UNUSED                0
#define CONTROL               0L    /* Indicador de que control   */
#define END_OF_FILE           0L    /* Indic. fin de fichero      */
#define BITS_CHARS            8     /* 8 order-0 ; 16 order-1 ... */

#define WIND_BITS            14
#define WIND_SIZE             ( 1 << WIND_BITS )
#define WIND_MASK             ( WIND_SIZE - 1 )
#define MOD_WIN( a )          ( ( a ) & WIND_MASK )

#define INIT_BIT_BUMP              8

#define BITS_LOOKAHEAD        4
#define RAW_LOOKAHEAD         ( 1 << BITS_LOOKAHEAD ) 

#define MIN_MATCH             3     /* No lo toques o no funciona */
#define MAX_MATCH             (RAW_LOOKAHEAD + MIN_MATCH -1 )

#define HASH_BITS             15    /* Sugiero mmnimo de 12 pero llega a 10 */
#define HASH_SIZE            (unsigned)(1<<HASH_BITS)
#define HASH_MASK             ( HASH_SIZE - 1)
#define HASH_SHIFT            (( HASH_BITS + MIN_MATCH -1 )/MIN_MATCH) /* 5 */

#define MAX_HASH_COL          128

#define REHASH( h , c )      h = (( (( h )<<HASH_SHIFT) ^ ( c )) & HASH_MASK )


/**-----------------------------------------------------------------------
  *   Aqum se encuentran las variables globales, espero que no quede nada 
  * pues en caso contrario uno no puede hacer residente el codigo
  *
  **/


/**-----------------------------------------------------------------------
  *   Definicisn de tipos a causa de mi vagancia al escribir, tambien
  * simplifica considerablemente el entendimiento de los parametros.
  *
  **/

typedef unsigned char  CHARS;   /* Por si en el futuro amplio a order-1    */
                              /* El 1.8 Speedup , 14% compresion-down( text ) */

/**-----------------------------------------------------------------------
  *   Prototipos para todas estas paridas necesarias para compilar.
  *
  **/


/**-----------------------------------------------------------------------
  *   En un principio utilizaba la funcisn de HASH del COMRESS de GNU en
  * UNIX, pero por motivos de eficiencia he tenido que cambiarla. La forma
  * actual se inspira en el algoritmo de Rabin & Karp ( En el libro :
  *   "Algorithms" de Sedgewick de Addison-Wesley p.252  )
  *
  **/

#define BestMatch( scan , matchpos , bestlen )                      \
  {                                                                 \
  if( (xparinbuf + matchpos) <= scan )                                             \
    {                                                               \
    ioaux    = 0;                                                   \
    bestlen  = MIN_MATCH - 1;                                       \
    scanend  = scan[ bestlen    ];                                  \
    strend   = scan + MAX_MATCH;                                    \
    current  = matchpos;                                            \
    lastmatch= matchpos;                                            \
    while( current != NIL &&  lastmatch >= current )                \
      {                                                             \
      match = xparinbuf + current;                                \
      if( match[ bestlen   ] != scanend  ||                         \
          *match             != *scan    ||                         \
          *++match           != scan[1]     )                       \
        {                                                           \
        lastmatch  = current;                                       \
        current    = prev[ current ];                               \
        ioaux++;                                                    \
        if( ioaux > MAX_HASH_COL )                                  \
          break;                                                    \
        continue;                                                   \
        }                                                           \
      scan+=2;    /*  do not try to put in the if condition    */   \
      match++;                                                      \
      do                                                            \
        {                                                           \
        }while( *++scan == *++match &&  *++scan == *++match &&      \
                *++scan == *++match &&  *++scan == *++match &&      \
                *++scan == *++match &&  *++scan == *++match &&      \
                *++scan == *++match &&  *++scan == *++match &&      \
                scan < strend );    /* Estraqo pero mejor codigo */ \
      conta  = MAX_MATCH - (UBYTE)(strend - scan);  /* len para ahorrar */\
      scan = strend - MAX_MATCH;                                    \
      if( conta > bestlen )                                         \
        {                                                           \
        bestlen  = conta;                                           \
        matchpos = current;                                         \
        if( conta >= MAX_MATCH )                                    \
          break;                                                    \
        scanend   = scan[ bestlen     ];                            \
        }                                                           \
      lastmatch  = current;                                         \
      current    = prev[ current ];                                 \
      }                                                             \
    }                                                               \
  }


/**-----------------------------------------------------------------------
  *   En pocas lineas se adentrara al nucleo de todo el sistema de
  * compresisn de datos, aunque parezca mentira intentare que el 
  * sistema mantenga el coste ideal mmnimo, coste LINEAL??.
  *   Esto son las mejores intenciones, ya veremos en que se nos queda.
  *
  **/

long __saveds __asm XpksPackChunk( REG __a0 XPARAMS *xpar )
{
    /*  variables para input - output   */
register   UBYTE  inpmask;
           UBYTE  outmask;
register   CHARS *inpb;
           CHARS *endinp;
register   CHARS *outb;
           CHARS *endout;
           ULONG  ioaux;          /* tambien se usa en BestMach           */

  /*  varialbles utilizadas en BestMach   */
           CHARS  scanend;
           CHARS *strend;
           CHARS *match;
           UWORD  current;
           UWORD  lastmatch;

    /*  bloque general de compres       */
           UBYTE  lookahead;      /* siempre RAW_LOOKAHEAD < 255          */
           UBYTE  matchlen;       /* siempre RAW_LOOKAHEAD < 255          */
           UBYTE  replace;        /* cuanto se ha de ampliar "lookahead"  */
           UBYTE  conta;          /* tambien se usa en BestMach           */
           
           long   bitcount;       /* es un LONG para compatibilidad       */
           CHARS *bumpcode;
           
           CHARS *xparinbuf;      /* todo el mundo la utiliza             */
           UWORD  hash_key;       /* actual hash value                    */
           UWORD  matchpos;       /* position of matchlen                 */
register   CHARS *actp;           /* posicion  en wwindow fich            */
register   UWORD *head;           /* dictionary                           */
register   UWORD *prev;           /* previous in the hash line            */

/**
  * Bloque de inicializacsn + reserva de memoria para las tablas
  *
  **/

  if( !xpar->Sub[0] )
    {
    if( !(head = malloc( sizeof( UWORD ) * HASH_SIZE )) )
      return( XPKERR_NOMEM );

    if( !(prev = malloc( sizeof( UWORD ) * (WIND_SIZE+MAX_MATCH) ) ) )
      {
      free( head );
      return( XPKERR_NOMEM );
      }
    memset( head , NIL , HASH_SIZE*sizeof( UWORD ) ); /* head */
    xpar->Sub[0]=(long)prev;
    xpar->Sub[1]=(long)head;
    }

                 /* previous y wwindow se autoinilizalizan */

  InitOutput();
  InitInput();

  xparinbuf = xpar->InBuf;
  bitcount  = INIT_BIT_BUMP;
  bumpcode  = xparinbuf+(1<<INIT_BIT_BUMP);

  matchpos  = 0;     /* No hace falta pero evita un WARNING */
  matchlen  = 0;
  actp      = xparinbuf;
  hash_key  = 0;

/**
  * Bloque de la precarga necesaria para poder empezar el bucle
  *
  **/

  for( conta = 1 ; conta <= MAX_MATCH && EndOfFile() ; conta++ )
    InputByte( );
  
  lookahead = conta-2;

 if( conta > 3 )
    {
    REHASH( hash_key , actp[1] );
    REHASH( hash_key , actp[2] );
    }

/**
  *   Comienzo del bucle principal para la compresisn de datos
  *
  **/

  while( lookahead > 0 )
    {
    if( matchlen > lookahead )
      matchlen = lookahead;
    
    if( matchlen < MIN_MATCH )   /* Sale a cuenta 2 bloque ? */
      {
      replace=1;
      OutputBit( 1 );
      OutputBits( (long )*actp , BITS_CHARS );
      }
    else
      {
      replace=matchlen;
      if( actp > bumpcode )
        {
        bitcount++;
        bumpcode  = xparinbuf + (1<<bitcount);
        }
      OutputBit( 0 );
      OutputBits( (long)matchpos , bitcount );
      OutputBits( (long)( matchlen - MIN_MATCH  ) , BITS_LOOKAHEAD );
      }

    for( conta = 0 ; conta < replace ; conta++ )
      {
      if( EndOfFile() )
        lookahead--;
      else
        InputByte( );

      actp++;

      REHASH( hash_key , actp[  MIN_MATCH -1 ] ); 

      prev[ actp - xparinbuf ] = matchpos = head [ hash_key ];
      head[ hash_key ] = actp - xparinbuf;
      }

    BestMatch( actp , matchpos , matchlen );    /* potente macro eh !! */
  }

/**
  *   No hace falta indicador de final de fichero pues se siempre
  * la longitud,  tampoco libero los recursos, de esto se encarga
  *                     XpkPackFree
  *
  **/
  return( 0 );
}

/************************** End of ILZR.C *************************/