lzrw2.c

一个基于lZW压缩算法的高效实现

       *p_hte=next;
       phrase[next++]=p_src;

       /* Having looked up the candidate position, we are in a position to    */
       /* attempt a match. The match loop has been unrolled using the PS      */
       /* macro so that failure within the first three bytes automatically    */
       /* results in the literal branch being taken. The coding is simple.    */
       /* p_ziv saves p_src so we can let p_src wander.                       */
       #define PS *p++!=*p_src++
       p_ziv=p_src;
       if (PS || PS || PS)
         {p_src=p_ziv; literal:*p_dst++=*p_src++; control&=0xFFFEFFFF;}
       else
         {
          PS || PS || PS || PS || PS || PS || PS || PS ||
          PS || PS || PS || PS || PS || PS || PS || p_src++;
          *p_dst++=((phrase_num&0xF00)>>4)|(--p_src-p_ziv-3);
          *p_dst++=phrase_num&0xFF;
         }
       control>>=1;
                
       /* This loop is all set up for a decrement and jump instruction! */
    end_unrolled_loop: if (--unroll) goto begin_unrolled_loop;

    /* At this point it will nearly always be the end of a group in which     */
    /* case, we have to do some control-word processing. However, near the    */
    /* end of the input block, the inner unrolled loop is only executed once. */
    /* This necessitates the 'if' test.                                       */
    if ((control&TOPWORD)==0)
      {
       /* Write the control word to the place we saved for it in the output. */
       *p_control++=  control     &0xFF;
       *p_control  = (control>>8) &0xFF;

       /* Reserve the next word in the output block for the control word */
       /* for the group about to be processed.                           */
       p_control=p_dst; p_dst+=2;
       
       /* Reset the control bits buffer. */
       control=TOPWORD;
       
       /* The following statement makes sure that the 'next' phrase table     */
       /* index cycles when it comes to the end of the phrase table. This     */
       /* can be included here within the control word processing because the */
       /* control word processing happens once every 16 items processed and   */
       /* 4096 (the num of entries in the phrase table) is a multiple of 16.  */
       next&=0xFFF;
      }
          
   } /* End main processing loop. */
   
 /* After the main processing loop has executed, all the input bytes have     */
 /* been processed. However, the control word has still to be written to the  */
 /* word reserved for it in the output at the start of the most recent group. */
 /* Before writing, the control word has to be shifted so that all the bits   */
 /* are in the right place. The "empty" bit positions are filled with 1s      */
 /* which partially fill the top word.                                        */
 while(control&TOPWORD) control>>=1;
 *p_control++= control     &0xFF;
 *p_control++=(control>>8) &0xFF;
 
 /* If the last group contained no items, delete the control word too.        */
 if (p_control==p_dst) p_dst-=2;
 
 /* Write the length of the output block to the dst_len parameter and return. */
 *p_dst_len=p_dst-p_dst_first;                           
 return;
 
 /* Jump here as soon as an overrun is detected. An overrun is defined to     */
 /* have occurred if p_dst>p_dst_first+src_len. That is, the moment the       */
 /* length of the output written so far exceeds the length of the input block.*/
 /* The algorithm checks for overruns at least at the end of each group       */
 /* which means that the maximum overrun is MAX_CMP_GROUP bytes.              */
 /* Once an overrun occurs, the only thing to do is to set the copy flag and  */
 /* copy the input over.                                                      */
 overrun:
 *p_dst_first=FLAG_COPY;
 fast_copy(p_src_first,p_dst_first+FLAG_BYTES,src_len);
 *p_dst_len=src_len+FLAG_BYTES;
}

/******************************************************************************/

LOCAL void compress_decompress
           (p_wrk_mem,p_src_first,src_len,p_dst_first,p_dst_len)
/* Input  : Hand over the required amount of working memory in p_wrk_mem.     */
/* Input  : Specify input block using p_src_first and src_len.                */
/* Input  : Point p_dst_first to the start of the output zone.                */
/* Input  : Point p_dst_len to a ULONG to receive the output length.          */
/* Input  : Input block and output zone must not overlap. User knows          */
/* Input  : upperbound on output block length from earlier compression.       */
/* Input  : In any case, maximum expansion possible is nine times.            */
/* Output : Length of output block written to *p_dst_len.                     */
/* Output : Output block in Mem[p_dst_first..p_dst_first+*p_dst_len-1].       */
/* Output : Writes only  in Mem[p_dst_first..p_dst_first+*p_dst_len-1].       */
UBYTE *p_wrk_mem;
UBYTE *p_src_first;
ULONG  src_len;
UBYTE *p_dst_first;
ULONG *p_dst_len;
{
 /* Byte pointers p_src and p_dst scan through the input and output blocks.   */
 register UBYTE *p_src = p_src_first+FLAG_BYTES;
 register UBYTE *p_dst = p_dst_first;

 /* The following two variables are never modified and are used to control    */
 /* the main loop.                                                            */
 UBYTE *p_src_post  = p_src_first+src_len;
 UBYTE *p_src_max16 = p_src_first+src_len-(MAX_CMP_GROUP-2);
 
 /* The variable 'control' is used to buffer the control bits which appear in */
 /* groups of 16 bits (control words) at the start of each compressed group.  */
 /* When each group is read, bit 16 of the register is set to one. Whenever   */
 /* a new bit is needed, the register is shifted right. When the value of the */
 /* register becomes 1, we know that we have reached the end of a group.      */
 /* Initializing the register to 1 thus instructs the code to follow that it  */
 /* should read a new control word immediately.                               */
 register ULONG control=1;
 
 /* The phrase table is the same as in the compressor. The decompressor does  */
 /* not need to maintain a hash table, only a phrase table.                   */
 /* The phrase table is the only occupant of the working memory.              */
 UBYTE **phrase = (UBYTE **) ULONG_ALIGN_UP(p_wrk_mem);
 
 /* The next variable cycles through the phrase table always containing the   */
 /* index of the next phrase pointer to be overwritten in the phrase table.   */
 /* Optimization note: I tried using a pointer to cycle through the table but */
 /* this went more slowly than using an explicit index.                       */
 register UWORD next=0;
      
 /* Check the leading copy flag to see if the compressor chose to use a copy  */
 /* operation instead of a compression operation. If a copy operation was     */
 /* used, then all we need to do is copy the data over, set the output length */
 /* and return.                                                               */
 if (*p_src_first==FLAG_COPY)
   {
    fast_copy(p_src_first+FLAG_BYTES,p_dst_first,src_len-FLAG_BYTES);
    *p_dst_len=src_len-FLAG_BYTES;
    return;
   }
   
 /* Whereas the compressor needs to maintain a hash table and a phrase table  */
 /* the decompressor needs to maintain only the phrase table. Only the first  */
 /* entry of the phrase table needs initializing as, apart from this entry,   */
 /* the compressor guarantees not to refer to a table entry until the entry   */
 /* has been written.                                                         */
 phrase[0]=(UBYTE *) START_STRING_18;
    
 /* The outer loop processes either 1 or 16 items per iteration depending on  */
 /* how close p_src is to the end of the input block.                         */
 while (p_src!=p_src_post)
   {/* Start of outer loop */
   
    register UWORD unroll;   /* Counts unrolled loop executions.              */
    
    /* When 'control' has the value 1, it means that the 16 buffered control  */
    /* bits that were read in at the start of the current group have all been */
    /* shifted out and that all that is left is the 1 bit that was injected   */
    /* into bit 16 at the start of the current group. When we reach the end   */
    /* of a group, we have to load a new control word and inject a new 1 bit. */
    if (control==1)
      {
       control=0x10000|*p_src++;
       control|=(*p_src++)<<8;
      
       /* Because 4096 (the number of entries in the phrase table) is a       */
       /* multiple of 16 (the loop unrolling), and 'unroll' has the value 1   */
       /* or 16 and never increases its initial value, this wraparound check  */
       /* need only be done once per main loop. In fact it can even reside    */
       /* within this 'if'.                                                   */
       next&=0xFFF;
      }

    /* If it is possible that we are within 16 groups from the end of the     */
    /* input, execute the unrolled loop only once, else process a whole group */
    /* of 16 items by looping 16 times.                                       */
    unroll= p_src<=p_src_max16 ? 16 : 1;

    /* This inner loop processes one phrase (item) per iteration. */
    while (unroll--)
      { /* Begin unrolled inner loop. */
      
       /* Process a literal or copy item depending on the next control bit. */
       if (control&1)
         { /* Copy item. */
          register UWORD lenmt; /* Length of copy item minus three.           */
          register UBYTE *p;    /* Points to history posn from which to copy. */
          
          /* Read and dismantle the copy word. Work out from where to copy.   */
          lenmt=*p_src++;
          p=phrase[((lenmt&0xF0)<<4)|*p_src++];
          lenmt&=0xF;

          /* Update the phrase table. Don't do this before p=phrase[...]. */
          phrase[next++]=p_dst;
          
          /* Now perform the copy using a half unrolled loop. */
          *p_dst++=*p++;
          *p_dst++=*p++;
          *p_dst++=*p++;
          while (lenmt--)
             *p_dst++=*p++;
         }
       else
         { /* Literal item. */
          phrase[next++]=p_dst;  /* Update the phrase table.    */
          *p_dst++=*p_src++;     /* Copy over the literal byte. */
          }
          
       /* Shift the control buffer so the next control bit is in bit 0. */
       control>>=1;
       
      } /* End unrolled inner loop. */
               
   } /* End of outer loop */
   
 /* Write the length of the decompressed data before returning. */
 *p_dst_len=p_dst-p_dst_first;
}

/******************************************************************************/
/*                               End of LZRW2.C                               */
/******************************************************************************/