发信人: lofe ()感激生活(), 信区: Algorithm
标 题: LZRW - LZRW1.C
发信站: 哈工大紫丁香 (Sun Sep 3 16:06:00 2000), 转信
#ifndef __HUGE__
#error Use HUGE memory model.
#endif
#define TRUE 1
#define UBYTE unsigned char /* Unsigned byte (1 byte ) */
#define UWORD unsigned int /* Unsigned word (2 bytes) */
#define ULONG unsigned long /* Unsigned longword (4 bytes) */
#define FLAG_BYTES 4 /* Number of bytes used by copy flag. */
#define FLAG_COMPRESS 0 /* Signals that compression occurred. */
#define FLAG_COPY 1 /* Signals that a copyover occurred. */
void fast_copy(p_src,p_dst,len) /* Fast copy routine. */
UBYTE *p_src,*p_dst; {while (len--) *p_dst++=*p_src++;}
/***************************************************************************
***/
void lzrw1_compress(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+256-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;
#define PS *p++!=*s++ /* Body of inner unrolled matching loop. */
#define ITEMMAX 16 /* Maximum number of bytes in an expanded item. */
{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_post-ITEMMAX,*p_src_max16=p_src_post-16*ITEMMAX;
UBYTE *hash[4096],*p_control; UWORD control=0,control_bits=0;
*p_dst=FLAG_COMPRESS; p_dst+=FLAG_BYTES; p_control=p_dst; p_dst+=2;
while (TRUE)
{UBYTE *p,*s; UWORD unroll=16,len,index; 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:
index=((40543*((((p_src[0]<<4)^p_src[1])<<4)^p_src[2]))>>4) & 0xFFF;
p=hash[index]; hash[index]=s=p_src; offset=s-p;
if (offset>4095 || p<p_src_first || offset==0 || PS || PS || PS)
{literal: *p_dst++=*p_src++; control>>=1; control_bits++;}
else
{PS || PS || PS || PS || PS || PS || PS ||
PS || PS || PS || PS || PS || PS || s++; len=s-p_src-1;
*p_dst++=((offset&0xF00)>>4)+(len-1); *p_dst++=offset&0xFF;
p_src+=len; control=(control>>1)|0x8000; control_bits++;}
end_unrolled_loop: if (--unroll) goto begin_unrolled_loop;
if (control_bits==16)
{*p_control=control&0xFF; *(p_control+1)=control>>8;
p_control=p_dst; p_dst+=2; control=control_bits=0;}
}
control>>=16-control_bits;
*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;
}
/***************************************************************************
***/
void lzrw1_decompress(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 eight 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;
{UWORD controlbits=0, control;
UBYTE *p_src=p_src_first+FLAG_BYTES, *p_dst=p_dst_first,
*p_src_post=p_src_first+src_len;
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)
{if (controlbits==0)
{control=*p_src++; control|=(*p_src++)<<8; controlbits=16;}
if (control&1)
{UWORD offset,len; UBYTE *p;
offset=(*p_src&0xF0)<<4; len=1+(*p_src++&0xF);
offset+=*p_src++&0xFF; p=p_dst-offset;
while (len--) *p_dst++=*p++;}
else
*p_dst++=*p_src++;
control>>=1; controlbits--;
}
*p_dst_len=p_dst-p_dst_first;
}
/***************************************************************************
***/
/* End of LZRW1.C
*/
/***************************************************************************
***/
unsigned _stklen = 40000U;
void main (void){
char *str1 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\n
\r";
char str2[100];
long len2;
char str3[100];
long len3;
lzrw1_compress (str1, (long)(strlen(str1)+1), str2, &len2);
lzrw1_decompress (str2, len2, str3, &len3);
printf (str1);
printf (str3);
}
--
████████████████████████
█ █ http://inf.home.chinaren.net
█ ＨＡＰＰＹ ＮＥＷ ＭＩＬＬＥＮＮＩＵＭ！ █ http://jtlab.163.net
█ Yours, █
█ Anya █ inf@chinaren.com
████████████████████████
※ 修改:．haojs 于 Sep 3 16:03:37 修改本文．[FROM: bbs.hit.edu.cn]
--
※ 转寄:．武汉白云黄鹤站 bbs.whnet.edu.cn．[FROM: bbs.hit.edu.cn]
--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: haojs.bbs@bbs.whnet.]
※ 修改:·lofe 於 09月03日16:08:10 修改本文·[FROM: 202.118.226.15]