lzrw5.txt

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

    /* Insert a new phrase into the tree. */
    if (node[current].len_phrase==MAX_PHRASE_LENGTH)
       node[next].len_phrase=0;
    else
      {
       /* Create a new leaf node with the string in it. */
       struct node_t *pn=&node[next];
       pn->p_phrase=p_ziv;
       pn->len_phrase=node[bestnode].len_phrase+1;  /* Opt: Use a wrap for this later! */
       pn->left=0;
       pn->right=0;
       /* Connect it up to the append node. */
       if (cmp==-1)
          node[current].left=next;
       else
          node[current].right=next;
      }

    if (++next == MAX_NODES)
       {printf("Ran out of nodes.\n");exit(1);}

   } /* End main processing loop. */

 /* At this point there are 256 or less bytes to go. These are most easily */
 /* coded as one byte strings. */
 while (p_src!=p_src_post)
   {
    *p_dst++=0;
    *p_dst++=*p_src++;
   }

 /* 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;
{
 UCARD execute_c_code = FALSE;

 /* Byte pointers p_src and p_dst scan through the input and output blocks.   */
 /* FOLLOWING TWO WERE REGISTER FOR C CODE. */
 UBYTE *p_src = p_src_first+FLAG_BYTES;
 UBYTE *p_dst = p_dst_first;

 /* The following variable is never modified and are used to control          */
 /* the main loop.                                                            */
 UBYTE *p_src_post = p_src_first+src_len;

 UBYTE **pointer;
 UBYTE *length;
 UBYTE *alphabet;
 UBYTE **p_pointer,**p_post_pointer;
 UBYTE *p_length;

 /* 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;
   }

 pointer  = (UBYTE **) ULONG_ALIGN_UP(p_wrk_mem);
 alphabet = (UBYTE *)  &pointer[MAX_NODES];
 length   = (UBYTE *)  &alphabet[ALPHABET_SIZE];

 ass( ((p_src_post-p_src)&1)==0,
      "lzrw5_decompress: Input block is of odd length.");
 ass( (((ULONG)p_src)&1)==0,
      "lzrw5_decompress: Input block is odd aligned.");

 printf("DECOMPRESSOR CALLED\n");

 {
  UCARD i;
  UBYTE **p_init_pointer  = pointer;
  UBYTE  *p_init_alphabet = alphabet;
  UBYTE  *p_init_length   = length;
  UBYTE length_init_value = execute_c_code ? 0 : 255;
  for (i=0;i<ALPHABET_SIZE;i++)
    {
     *p_init_pointer ++ = p_init_alphabet;
     *p_init_alphabet++ = i;
     *p_init_length  ++ = length_init_value;
    }
 }

 p_pointer = p_post_pointer = &pointer[MAX_NODES];

 while (p_src!=p_src_post)
   {
    ULONG items_to_go   = (p_src_post-p_src)>>1;
    ULONG entries_to_go = p_post_pointer-p_pointer;
    ULONG unroll;  /* WAS REGISTER FOR C CODE. */

    if (entries_to_go==0)
       {
        p_pointer=&pointer[ALPHABET_SIZE];
        p_length =&length [ALPHABET_SIZE];
        entries_to_go=p_post_pointer-p_pointer;
       }

    unroll= (items_to_go<entries_to_go) ? items_to_go : entries_to_go;

    ass(unroll>0,"unroll==0.");

    if (execute_c_code)
       while (unroll--)
         {
          register UBYTE *p;
          register UCARD len;
          register UWORD phrase;

          phrase =*p_src++<<8;
          phrase|=*p_src++;
          p=pointer[phrase];
          len=length[phrase];
          *p_pointer++=p_dst;
          *p_length++=len+1;
          do
                {*p_dst++=*p++;}
              while (len--);
         }
    else
    asm 68000
      {
       ;------------------------------------------------------------------------
                                   ;REGISTER MAP
                                   ;============
       #define A_SRC         a0    ;Points to the next input  byte.
       #define A_DST         a1    ;Points to the next output byte.
       #define A_POINTER     a2    ;Points to the start of the pointer array.
       #define A_LENGTH      a3    ;Points to the start of the length array.
       #define A_PPOINTER    a4    ;Points to next pointer to be overwritten.
       #define A_PLENGTH     a5    ;Points to next length  to be overwritten.
       #define A_P           a6    ;Runs through source phrase during copy.
       #define A_LINKAGE     a6 ;<--a6 is also the linkage register. Careful!!!
       #define A_STACK       a7    ;Stack pointer. Don't touch!

       #define D_UNROLL      d0    ;Counts down the unrolled loop
       #define D_LEN         d1    ;Holds the length of the copy.
       #define D_PHRASE      d2    ;Number of phrase chosen by sender.
       #define D_D3          d3    ;Unused.
       #define D_D4          d4    ;Unused
       #define D_D5          d5    ;Unused.
       #define D_D6          d6    ;Unused.
       #define D_D7          d7    ;Unused.

       ;Lightspeed C doesn't mind us using a0-a1 and d0-d2, but I'm being
       ;careful here (if only to ease porting to other compilers).
       #define REGISTERS_TO_SAVE a0-a6/d0-d7

       ;------------------------------------------------------------------------
       movem.l REGISTERS_TO_SAVE,-(A_STACK)

       move.l  p_src,    A_SRC        ;These need to be saved at the end.
       move.l  p_dst,    A_DST
       move.l  p_pointer,A_PPOINTER
       move.l  p_length, A_PLENGTH

       move.l  pointer,  A_POINTER    ;These ones don't need to be saved
       move.l  length,   A_LENGTH     ;at the end.
       move.l  unroll,   D_UNROLL

       move.l  A_LINKAGE,-(A_STACK)


       ;Note: The clr.l D_PHRASE instruction can be moved out of the loop
       ;      if MAX_NODES is not more than 2^15.
       ;Note: The clr.l D_LEN could be moved out of the loop if we
       ;      were to store the length array as an array of longwords.
       #define DECOMPRESS_PHRASE(LABEL)                                  \
          clr.l   D_PHRASE                   ;Clear out top bytes.       \
          clr.l   D_LEN                      ;Clear byte 1               \
          move.w  (A_SRC)+,D_PHRASE          ;phrase =*p_src++<<8;       \
                                             ;phrase|=*p_src++;          \
          move.b  (0,A_LENGTH,D_PHRASE.L),D_LEN;len=length[phrase];      \
          lsl.l   #2,D_PHRASE                ;p=pointer[phrase];         \
          move.l  (0,A_POINTER,D_PHRASE.L),A_P                           \
          move.l  A_DST,(A_PPOINTER)+        ;*p_pointer++=p_dst;        \
          add.b   #1,    D_LEN               ;*p_length++=len+1;         \
          move.b  D_LEN,(A_PLENGTH)+                                     \
          LABEL:                             ;do                         \
             move.b (A_P)+,(A_DST)+          ;  {*p_dst++=*p++;}         \
          dbra D_LEN, LABEL                  ;while (len--);     LAST LINE

       @unrolled_phrase_loop:
          sub.l #16,  D_UNROLL
          bmi   @end_unrolled_phrase_loop

          DECOMPRESS_PHRASE(@copy_01)
          DECOMPRESS_PHRASE(@copy_02)
          DECOMPRESS_PHRASE(@copy_03)
          DECOMPRESS_PHRASE(@copy_04)
          DECOMPRESS_PHRASE(@copy_05)
          DECOMPRESS_PHRASE(@copy_06)
          DECOMPRESS_PHRASE(@copy_07)
          DECOMPRESS_PHRASE(@copy_08)
          DECOMPRESS_PHRASE(@copy_09)
          DECOMPRESS_PHRASE(@copy_10)
          DECOMPRESS_PHRASE(@copy_11)
          DECOMPRESS_PHRASE(@copy_12)
          DECOMPRESS_PHRASE(@copy_13)
          DECOMPRESS_PHRASE(@copy_14)
          DECOMPRESS_PHRASE(@copy_15)
          DECOMPRESS_PHRASE(@copy_16)
       bra @unrolled_phrase_loop

       @end_unrolled_phrase_loop
       add.l #16, D_UNROLL
       @rolled_phrase_loop:
          sub.l #1,  D_UNROLL
          bmi   @end_rolled_phrase_loop
          DECOMPRESS_PHRASE(@just_the_one)
       bra @rolled_phrase_loop
       @end_rolled_phrase_loop:

       move.l  (A_STACK)+, A_LINKAGE

       move.l  A_SRC,      p_src
       move.l  A_DST,      p_dst
       move.l  A_PPOINTER, p_pointer
       move.l  A_PLENGTH,  p_length

       movem.l (A_STACK)+,REGISTERS_TO_SAVE
       ;------------------------------------------------------------------------
      } /* End asm 68000 */

   } /* End outer while loop. */

 /* Write the length of the decompressed data before returning. */
 *p_dst_len=p_dst-p_dst_first;

 printf("EXITING DECOMPRESSOR.\n");
}

/******************************************************************************/
/*                                End of LZRW5.C                              */
/******************************************************************************/



--<End of LZRW5 paper>--