home *** CD-ROM | disk | FTP | other *** search
/ Amiga MA Magazine 1998 #6 / amigamamagazinepolishissue1998.iso / packery / xpkilzr / source / cilzr.c < prev    next >
C/C++ Source or Header  |  1977-12-31  |  9KB  |  252 lines
  1.  
  2.  
  3. /**-----------------------------------------------------------------------
  4.   *   Bloque de includes, por fin me ocupan menos de una pagina de
  5.   * impresisn, lo que hay que hacer para tener todos los prototipos..
  6.   *
  7.   **/
  8.  
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11. #include <string.h>
  12. #include <ctype.h>
  13. #include <fcntl.h>
  14.  
  15. #define NO_SUB_PRAGMAS
  16. #include <libraries/xpksub.h>
  17.  
  18. #include "cbitio.h"      /* custom includes */
  19. #include "ilzr.h"
  20.  
  21. /**-----------------------------------------------------------------------
  22.   *   Prototipos para todas estas paridas necesarias para compilar.
  23.   *
  24.   **/
  25.  
  26.  
  27. /**-----------------------------------------------------------------------
  28.   *   En un principio utilizaba la funcisn de HASH del COMRESS de GNU en
  29.   * UNIX, pero por motivos de eficiencia he tenido que cambiarla. La forma
  30.   * actual se inspira en el algoritmo de Rabin & Karp ( En el libro :
  31.   *   "Algorithms" de Sedgewick de Addison-Wesley p.252  )
  32.   *
  33.   **/
  34.  
  35. #define BestMatch( scan , matchpos , bestlen )                      \
  36.   {                                                                 \
  37.   if( (xparinbuf + matchpos) <= scan )                                             \
  38.     {                                                               \
  39.     ioaux    = 0;                                                   \
  40.     bestlen  = MIN_MATCH - 1;                                       \
  41.     scanend  = scan[ bestlen    ];                                  \
  42.     strend   = scan + MAX_MATCH;                                    \
  43.     current  = matchpos;                                            \
  44.     lastmatch= matchpos;                                            \
  45.     while( current != NIL &&  lastmatch >= current )                \
  46.       {                                                             \
  47.       match = xparinbuf + current;                                  \
  48.       if( match[ bestlen   ] != scanend  ||                         \
  49.           *match             != *scan    ||                         \
  50.           *++match           != scan[1]     )                       \
  51.         {                                                           \
  52.         lastmatch  = current;                                       \
  53.         current    = prev[ current ];                               \
  54.         ioaux++;                                                    \
  55.         if( ioaux > MAX_HASH_COL )                                  \
  56.           break;                                                    \
  57.         continue;                                                   \
  58.         }                                                           \
  59.       scan+=2;    /*  do not try to put in the if condition    */   \
  60.       match++;                                                      \
  61.       do                                                            \
  62.         {                                                           \
  63.         }while( *++scan == *++match &&  *++scan == *++match &&      \
  64.                 *++scan == *++match &&  *++scan == *++match &&      \
  65.                 *++scan == *++match &&  *++scan == *++match &&      \
  66.                 *++scan == *++match &&  *++scan == *++match &&      \
  67.                 scan < strend );    /* Estraqo pero mejor codigo */ \
  68.       conta = MAX_MATCH - (UBYTE)(strend - scan);  /* len para ahorrar */\
  69.       scan  = strend - MAX_MATCH;                                   \
  70.       if( conta > bestlen )                                         \
  71.         {                                                           \
  72.         bestlen  = conta;                                           \
  73.         matchpos = current;                                         \
  74.         if( conta >= MAX_MATCH )                                    \
  75.           break;                                                    \
  76.         scanend   = scan[ bestlen     ];                            \
  77.         }                                                           \
  78.       lastmatch  = current;                                         \
  79.       current    = prev[ current ];                                 \
  80.       }                                                             \
  81.     }                                                               \
  82.   }
  83.  
  84.  
  85. /**-----------------------------------------------------------------------
  86.   *   En pocas lineas se adentrara al nucleo de todo el sistema de
  87.   * compresisn de datos, aunque parezca mentira intentare que el 
  88.   * sistema mantenga el coste ideal mmnimo, coste LINEAL??.
  89.   *   Esto son las mejores intenciones, ya veremos en que se nos queda.
  90.   *
  91.   **/
  92.  
  93. long __saveds __asm XpksPackChunk( REG __a0 XPARAMS *xpar )
  94. {
  95.     /*  variables para input - output   */
  96. register   UBYTE  outmask;
  97. register   CHARS *inpb;
  98.            CHARS *endinp;
  99. register   CHARS *outb;
  100.            CHARS *endout;
  101.            ULONG  ioaux;          /* tambien se usa en BestMach           */
  102.            UBYTE  endoffile;
  103.  
  104.   /*  varialbles utilizadas en BestMach   */
  105.            CHARS  scanend;
  106.            CHARS *strend;
  107. register   CHARS *match;
  108.            UWORD  current;
  109.            UWORD  lastmatch;
  110.  
  111.     /*  bloque general de compres       */
  112.            UBYTE  lookahead;      /* siempre RAW_LOOKAHEAD < 255          */
  113.            UBYTE  matchlen;       /* siempre RAW_LOOKAHEAD < 255          */
  114.            UBYTE  replace;        /* cuanto se ha de ampliar "lookahead"  */
  115.            UBYTE  conta;          /* tambien se usa en BestMach           */
  116.            
  117.            long   bitcount;       /* es un LONG para compatibilidad       */
  118.            CHARS *bumpcode;
  119.            
  120.            long   temp;
  121.  
  122.            CHARS *xparinbuf;      /* todo el mundo la utiliza             */
  123.            UWORD  hash_key;       /* actual hash value                    */
  124.            UWORD  matchpos;       /* position of matchlen                 */
  125. register   CHARS *actp;           /* posicion  en wwindow fich            */
  126. register   UWORD *head;           /* dictionary                           */
  127. register   UWORD *prev;           /* previous in the hash line            */
  128.  
  129. /**
  130.   * Bloque de inicializacsn + reserva de memoria para las tablas
  131.   *
  132.   **/
  133.  
  134.   if( !xpar->Sub[0] )
  135.     {
  136.     if( !(head = malloc( sizeof( UWORD ) * HASH_SIZE )) )
  137.       return( XPKERR_NOMEM );
  138.  
  139.     if( !(prev = malloc( sizeof( UWORD ) * (WIND_SIZE+MAX_MATCH) ) ) )
  140.       {
  141.       free( head );
  142.       return( XPKERR_NOMEM );
  143.       }
  144.     xpar->Sub[0]=(long)prev;
  145.     xpar->Sub[1]=(long)head;
  146.     }
  147.   else
  148.     {
  149.     prev= (UWORD *)xpar->Sub[0];
  150.     head= (UWORD *)xpar->Sub[1];
  151.     }
  152.  
  153.                  /* previous y wwindow se autoinilizalizan */
  154.  
  155.   memset( head , NIL , HASH_SIZE*sizeof( UWORD ) ); /* head */
  156.  
  157.   InitOutput();
  158.   InitInput();
  159.   endoffile = 0;
  160.  
  161.   temp = xpar->InLen;
  162.   OutputBits( temp , 16 );    /* NEED store the long of this block */
  163.   
  164.   xparinbuf = xpar->InBuf;
  165.   bitcount  = INIT_BIT_BUMP;
  166.   bumpcode  = xparinbuf+(1<<INIT_BIT_BUMP);
  167.  
  168.   matchpos  = 0;     /* No hace falta pero evita un WARNING */
  169.   matchlen  = 0;
  170.   actp      = xparinbuf;
  171.   hash_key  = 0;
  172.  
  173. /**
  174.   * Bloque de la precarga necesaria para poder empezar el bucle
  175.   *
  176.   **/
  177.  
  178.   for( conta = 1 ; conta <= MAX_MATCH && !EndOfFile() ; conta++ )
  179.     InputByte( );
  180.   
  181.   lookahead = conta-2;
  182.  
  183.   if( conta > 3 )
  184.     {
  185.     REHASH( hash_key , actp[1] );
  186.     REHASH( hash_key , actp[2] );
  187.     }
  188.  
  189. /**
  190.   *   Comienzo del bucle principal para la compresisn de datos
  191.   *
  192.   **/
  193.  
  194.   while( lookahead > 0 )
  195.     {
  196.     if( matchlen > lookahead )
  197.       matchlen = lookahead;
  198.     
  199.     if( matchlen < MIN_MATCH )   /* Sale a cuenta 2 bloque ? */
  200.       {
  201.       replace=1;
  202.       OutputBit( 1 );
  203.       temp=(long)*actp;
  204.       OutputBits( temp , BITS_CHARS );
  205.       }
  206.     else
  207.       {
  208.       replace=matchlen;
  209.       if( actp > bumpcode )
  210.         {
  211.         bitcount++;
  212.         bumpcode  = xparinbuf + (1<<bitcount);
  213.         }
  214.       OutputBit( 0 );
  215.       temp = (long)matchpos;
  216.       OutputBits( temp , bitcount );
  217.       temp= (long)(matchlen - MIN_MATCH );
  218.       OutputBits( temp , BITS_LOOKAHEAD );
  219.       }
  220.  
  221.     for( conta = 0 ; conta < replace ; conta++ )
  222.       {
  223.       if( EndOfFile() )
  224.         lookahead--;
  225.       else
  226.         InputByte( );
  227.  
  228.       actp++;
  229.  
  230.       REHASH( hash_key , actp[  MIN_MATCH -1 ] ); 
  231.       
  232.       temp = (long)(actp - xparinbuf);
  233.       prev[ temp ] = matchpos = head [ hash_key ];
  234.       head[ hash_key ] = ( UWORD )temp;
  235.       }
  236.  
  237.     BestMatch( actp , matchpos , matchlen );    /* potente macro eh !! */
  238.   }
  239.  
  240. /**
  241.   *   No hace falta indicador de final de fichero pues se siempre
  242.   * la longitud,  tampoco libero los recursos, de esto se encarga
  243.   *                     XpkPackFree
  244.   *
  245.   **/
  246.   xpar->OutLen = (long)outb - (long)xpar->OutBuf + 1; /* CUrIosO  */
  247.   
  248.   return( 0 );
  249. }
  250.  
  251. /************************** End of ILZR.C *************************/
  252.