Advertisement
Guest User

Untitled

a guest
May 30th, 2012
354
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdafx.h>
  2. #include "lzss.h"
  3. #ifndef _AFX
  4. #include "debug_new.h"
  5. #endif
  6. #include "memstream.h"
  7.  
  8. #ifdef _DEBUG
  9. #undef THIS_FILE
  10. static char THIS_FILE[]=__FILE__;
  11. #endif
  12.  
  13. static u32 textsize = 0,    /* text size counter */
  14.     codesize = 0;   /* code size counter */
  15. static int  match_position, match_length,  /* of longest match.  These are
  16.             set by the InsertNode() procedure. */
  17.     lson[N + 1], rson[N + 257], dad[N + 1];  /* left & right children &
  18.             parents -- These constitute binary search trees. */
  19.  
  20. static void InitTree(void)
  21. {
  22.     int  i;
  23.  
  24.     for (i = N + 1; i <= N + 256; i++) rson[i] = NIL;
  25.     for (i = 0; i < N; i++) dad[i] = NIL;
  26. }
  27.  
  28. static void InsertNode(int r, u8 *text_buf)
  29. {
  30.     int  i, p, cmp;
  31.     unsigned char  *key;
  32.  
  33.     cmp = 1;  key = &text_buf[r];  p = N + 1 + key[0];
  34.     rson[r] = lson[r] = NIL;  match_length = 0;
  35.     for(;;)
  36.     {
  37.         if (cmp >= 0)
  38.         {
  39.             if(rson[p]!=NIL) p=rson[p];
  40.             else {rson[p]=r; dad[r]=p; return;}
  41.         }
  42.         else
  43.         {
  44.             if(lson[p]!=NIL) p=lson[p];
  45.             else {lson[p]=r; dad[r]=p; return;}
  46.         }
  47.         for (i = 1; i < F; i++) if ((cmp = key[i] - text_buf[p + i]) != 0)  break;
  48.         if(i>match_length)
  49.         {
  50.             match_position=p;
  51.             if((match_length=i)>=F) break;
  52.         }
  53.     }
  54.     dad[r] = dad[p];  lson[r] = lson[p];  rson[r] = rson[p];
  55.     dad[lson[p]] = r;  dad[rson[p]] = r;
  56.     if (rson[dad[p]] == p) rson[dad[p]] = r;
  57.     else                   lson[dad[p]] = r;
  58.     dad[p] = NIL;  /* remove p */
  59. }
  60.  
  61. void DeleteNode(int p)
  62. {
  63.     int  q;
  64.    
  65.     if (dad[p] == NIL) return;  /* not in tree */
  66.     if (rson[p] == NIL) q = lson[p];
  67.     else if (lson[p] == NIL) q = rson[p];
  68.     else
  69.     {
  70.         q = lson[p];
  71.         if (rson[q] != NIL)
  72.         {
  73.             do {  q = rson[q];  } while (rson[q] != NIL);
  74.             rson[dad[q]] = lson[q];  dad[lson[q]] = dad[q];
  75.             lson[q] = lson[p];  dad[lson[p]] = q;
  76.         }
  77.         rson[q] = rson[p];  dad[rson[p]] = q;
  78.     }
  79.     dad[q] = dad[p];
  80.     if (rson[dad[p]] == p) rson[dad[p]] = q;  else lson[dad[p]] = q;
  81.     dad[p] = NIL;
  82. }
  83.  
  84. int LzssEncode(u8* &dest, u8* src, int src_size)
  85. {
  86.     int dest_seek=4, src_seek=0;
  87.     int  i, c, len, r, s, last_match_length, code_buf_ptr;
  88.     u8 code_buf[17], mask;
  89.     static u8   text_buf[N + F - 1];    /* ring buffer of size N,
  90.             with extra F-1 bytes to facilitate string comparison */
  91.  
  92.     dest=new u8[src_size*2];
  93.     InitTree();
  94.     code_buf[0]=0;
  95.     code_buf_ptr=mask=1;
  96.     s=0;
  97.     r=N-F;
  98.     // clear the buffer with any character that will appear often
  99.     memset(&text_buf[s],0,r);
  100.     // read F bytes into the last F bytes of the buffer
  101.     for(len=0; len<F && len<src_size; len++) text_buf[r+len]=src[src_seek++];
  102.     // text of size zero
  103.     if((textsize=len)==0) return 0;
  104.     for(i=1; i<=F; i++) InsertNode(r-i,text_buf);
  105.     InsertNode(r,text_buf);
  106.    
  107.     for(; len>0; )
  108.     {
  109.         if(match_length>len) match_length=len;
  110.  
  111.         if(match_length<=THRESHOLD)
  112.         {
  113.             match_length=1;  /* Not long enough match.  Send one byte. */
  114.             code_buf[0]|=mask;  /* 'send one byte' flag */
  115.             code_buf[code_buf_ptr++]=text_buf[r];  /* Send uncoded. */
  116.         }
  117.         else
  118.         {
  119.             code_buf[code_buf_ptr++]=match_position;
  120.             code_buf[code_buf_ptr++]=((match_position >> 4) & 0xf0)|(match_length-(THRESHOLD+1));
  121.         }
  122.         // shift mask left one bit
  123.         if((mask<<=1)==0)
  124.         {
  125.             for(i=0; i<code_buf_ptr; i++) dest[dest_seek++]=code_buf[i];
  126.             codesize+=code_buf_ptr;
  127.             code_buf[0]=0;
  128.             code_buf_ptr=mask=1;
  129.         }
  130.         last_match_length=match_length;
  131.         for(i=0; i<last_match_length; i++)
  132.         {
  133.             if(src_seek>=src_size) break;
  134.             c=src[src_seek++];
  135.             DeleteNode(s);      // delete old strings
  136.             text_buf[s]=c;      // read new bytes
  137.             if(s<F-1) text_buf[s+N]=c;
  138.             s=(s+1)%N;
  139.             r=(r+1)%N;
  140.             InsertNode(r,text_buf);
  141.         }
  142.         while(i++<last_match_length)
  143.         {
  144.             DeleteNode(s);                  // no need to read, but
  145.             s=(s+1)%N;
  146.             r=(r+1)%N;
  147.             if(--len) InsertNode(r,text_buf);       // buffer may not be empty
  148.         }
  149.     }
  150.  
  151.     // Send remaining code. */
  152.     if(code_buf_ptr>1)
  153.     {
  154.         for(i=0; i<code_buf_ptr; i++) dest[dest_seek++]=code_buf[i];
  155.         codesize+=code_buf_ptr;
  156.     }
  157.  
  158.     *((u32*)&dest[0])=dest_seek-4;
  159.     return dest_seek;
  160. }
  161.  
  162. int LzssDecode(u8* &dest, u8* src, int src_size)
  163. {
  164.     int r, fpos;
  165.     int dest_seek, src_seek;
  166.     u8 flags, c;
  167.     static u8   text_buf[N + F - 1];    /* ring buffer of size N,
  168.             with extra F-1 bytes to facilitate string comparison */
  169.  
  170.     //dest=new u8[src_size*10];
  171.     MEM_STREAM str;
  172.     MemStreamCreate(&str);
  173.     ZeroMemory(text_buf,N-F);
  174.  
  175.     for(fpos=0, r=N-F, flags=0, dest_seek=0, src_seek=4; src_seek-4<src_size; flags>>=1, fpos++)
  176.     {
  177.         // read flag
  178.         if((fpos%=8)==0) flags=src[src_seek++];
  179.  
  180.         if(flags&1)
  181.         {
  182.             c=src[src_seek++];
  183.             //dest[dest_seek++]=c;
  184.             MemStreamWriteByte(&str,c);
  185.             text_buf[r++]=c;
  186.             r%=N;
  187.         }
  188.         else
  189.         {
  190.             int i=src[src_seek++];
  191.             int j=src[src_seek++];
  192.  
  193.             i|=((j&0xf0)<<4);
  194.             j=(j&0x0f)+THRESHOLD;
  195.             // decompress string
  196.             for(int k=0; k<=j; k++)
  197.             {
  198.                 c=text_buf[(i+k)%N];
  199.                 //dest[dest_seek++]=c;
  200.                 MemStreamWriteByte(&str,c);
  201.                 text_buf[r++]=c;
  202.                 r%=N;
  203.             }
  204.         }
  205.     }
  206.     //return dest_seek;
  207.  
  208.     dest=str.data;
  209.     return str.pos;
  210. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement