home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Magazyn Amiga Shareware Floppies
/
ma54.dms
/
ma54.adf
/
xpkILZR
/
source
/
ILZR.C
< prev
next >
Wrap
C/C++ Source or Header
|
1994-01-20
|
11KB
|
287 lines
/**-----------------------------------------------------------------------
* 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 *************************/