SHARE
TWEET

Untitled

a guest May 30th, 2012 204 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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top