lzrw1-a.c

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

/*                     ====================================                   */
/*  * A compressed file consists of a COPY FLAG followed by a REMAINDER.      */
/*  * The copy flag CF uses up four bytes with the first byte being the       */
/*    least significant.                                                      */
/*  * If CF=1, then the compressed file represents the remainder of the file  */
/*    exactly. Otherwise CF=0 and the remainder of the file consists of zero  */
/*    or more GROUPS, each of which represents one or more bytes.             */
/*  * Each group consists of two bytes of CONTROL information followed by     */
/*    sixteen ITEMs except for the last group which can contain from one      */
/*    to sixteen items.                                                       */
/*  * An item can be either a LITERAL item or a COPY item.                    */
/*  * Each item corresponds to a bit in the control bytes.                    */
/*  * The first control byte corresponds to the first 8 items in the group    */
/*    with bit 0 corresponding to the first item in the group and bit 7 to    */
/*    the eighth item in the group.                                           */
/*  * The second control byte corresponds to the second 8 items in the group  */
/*    with bit 0 corresponding to the ninth item in the group and bit 7 to    */
/*    the sixteenth item in the group.                                        */
/*  * A zero bit in a control word means that the corresponding item is a     */
/*    literal item. A one bit corresponds to a copy item.                     */
/*  * A literal item consists of a single byte which represents itself.       */
/*  * A copy item consists of two bytes that represent from 3 to 18 bytes.    */
/*  * The first byte in a copy item will be denoted C1.                       */
/*  * The second byte in a copy item will be denoted C2.                      */
/*  * Bits will be selected using square brackets.                            */
/*    For example: C1[0..3] is the low nibble of the first control byte.      */
/*    of copy item C1.                                                        */
/*  * The LENGTH of a copy item is defined to be C1[0..3]+3 which is a number */
/*    in the range [3,18].                                                    */
/*  * The OFFSET of a copy item is defined to be C1[4..7]*256+C2[0..8] which  */
/*    is a number in the range [1,4095] (the value 0 is never used).          */
/*  * A copy item represents the sequence of bytes                            */
/*       text[POS-OFFSET..POS-OFFSET+LENGTH-1] where "text" is the entire     */
/*    text of the uncompressed string, and POS is the index in the text of    */
/*    the character following the string represented by all the items         */
/*    preceeding the item being defined.                                      */
/*                                                                            */
/******************************************************************************/

/* The following define defines the length of the copy flag that appears at   */
/* the start of the compressed file. I have decided on four bytes so as to    */
/* make the source and destination longword aligned in the case where a copy  */
/* operation must be performed.                                               */
/* The actual flag data appears in the first byte. The rest are zero.         */
#define FLAG_BYTES    4     /* How many bytes does the flag use up?           */

/* The following defines define the meaning of the values of the copy         */
/* flag at the start of the compressed file.                                  */
#define FLAG_COMPRESS 0     /* Signals that output was result of compression. */
#define FLAG_COPY     1     /* Signals that output was simply copied over.    */

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

LOCAL void compress_compress(p_wrk_mem,p_src_first,src_len,
                             p_dst_first,p_dst_len)
/* Input  : Specify input block using p_src_first and src_len.          */
/* Input  : Point p_dst_first to the start of the output zone (OZ).     */
/* Input  : Point p_dst_len to a ULONG to receive the output length.    */
/* Input  : Input block and output zone must not overlap.               */
/* 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 : May write in OZ=Mem[p_dst_first..p_dst_first+src_len+288-1].*/
/* Output : Upon completion guaranteed *p_dst_len<=src_len+FLAG_BYTES.  */
UBYTE *p_src_first,*p_dst_first; ULONG src_len,*p_dst_len; UBYTE *p_wrk_mem;
#define PS *p++!=*p_src++  /* Body of inner unrolled matching loop.     */
#define ITEMMAX 18         /* Max number of bytes in an expanded item.  */
#define TOPWORD 0xFFFF0000
{register UBYTE *p_src=p_src_first,*p_dst=p_dst_first;
 UBYTE *p_src_post=p_src_first+src_len,*p_dst_post=p_dst_first+src_len;
 UBYTE *p_src_max1,*p_src_max16;
 /* The following longword aligns the hash table in the working memory. */
 register UBYTE **hash= (UBYTE **) (( ((ULONG) p_wrk_mem) +3) & 0xFFFFFFFC);
 UBYTE *p_control; register ULONG control=TOPWORD;
 p_src_max1=p_src_post-ITEMMAX; p_src_max16=p_src_post-16*ITEMMAX;
 *p_dst=FLAG_COMPRESS; {UWORD i; for (i=1;i<FLAG_BYTES;i++) p_dst[i]=0;}
 p_dst+=FLAG_BYTES; p_control=p_dst; p_dst+=2;
 while (TRUE)
   {register UBYTE *p,**p_entry; register UWORD unroll=16;
    register ULONG offset;
    if (p_dst>p_dst_post) goto overrun;
    if (p_src>p_src_max16)
      {unroll=1;
       if (p_src>p_src_max1)
         {if (p_src==p_src_post) break; goto literal;}}
    begin_unrolled_loop:
       p_entry=&hash
          [((40543*((((p_src[0]<<4)^p_src[1])<<4)^p_src[2]))>>4) & 0xFFF];
       p=*p_entry; *p_entry=p_src; offset=p_src-p;
       if (offset>4095 || p<p_src_first || offset==0 || PS || PS || PS)
         {p_src=*p_entry; 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++=((offset&0xF00)>>4)|(--p_src-*p_entry-3);
          *p_dst++=offset&0xFF;}
       control>>=1;
    end_unrolled_loop: if (--unroll) goto begin_unrolled_loop;
    if ((control&TOPWORD) == 0)
      {*p_control=control&0xFF; *(p_control+1)=(control>>8)&0xFF;
       p_control=p_dst; p_dst+=2; control=TOPWORD;}
   }
 while (control&TOPWORD) control>>=1;
 *p_control++=control&0xFF; *p_control++=control>>8;
 if (p_control==p_dst) p_dst-=2;
 *p_dst_len=p_dst-p_dst_first;
 return;
 overrun: fast_copy(p_src_first,p_dst_first+FLAG_BYTES,src_len);
          *p_dst_first=FLAG_COPY; *p_dst_len=src_len+FLAG_BYTES;
}

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

LOCAL void compress_decompress(wrk_mem,p_src_first,src_len,p_dst_first,p_dst_len)
/* 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_src_first, *p_dst_first; ULONG src_len, *p_dst_len; UBYTE *wrk_mem;
{register UBYTE *p_src=p_src_first+FLAG_BYTES, *p_dst=p_dst_first;
 UBYTE *p_src_post=p_src_first+src_len;
 UBYTE *p_src_max16=p_src_first+src_len-(16*2);
 register ULONG control=1;
 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;}
 while (p_src!=p_src_post)
   {register UWORD unroll;
    if (control==1) {control=0x10000|*p_src++; control|=(*p_src++)<<8;}
    unroll= p_src<=p_src_max16 ? 16 : 1;
    while (unroll--)
      {if (control&1)
         {register UWORD lenmt; register UBYTE *p;
          lenmt=*p_src++; p=p_dst-(((lenmt&0xF0)<<4)|*p_src++);
          *p_dst++=*p++; *p_dst++=*p++; *p_dst++=*p++;
          lenmt&=0xF; while (lenmt--) *p_dst++=*p++;}
       else
          *p_dst++=*p_src++;
       control>>=1;
      }
   }
 *p_dst_len=p_dst-p_dst_first;
}

/******************************************************************************/
/*                             End of LZRNW1-A.C                              */
/******************************************************************************/