#include "zl77.h" #include "stdio.h" #include "stdlib.h" #include "string.h" #include "../huffman/huffman_.h" // zl77 算法的实现 #define DBG_WARN printf #define DBG_LOG printf // 定义数据缓冲区步长 #define LZ77_BUFF_STEP_SIZE 10 typedef struct _buff_item{ uint8_t data[LZ77_BUFF_STEP_SIZE]; struct _buff_item *next; struct _buff_item *prev; }buff_item; typedef struct _buff_def{ buff_item *current; buff_item *head; int used; int all; int current_index; int bit_used; }buff_def; typedef struct _zl77_def { int dict_len;// 字典长度 int tran_len;// 转换区长度 int index;// 窗口位置 buff_def buff_chars;//字符编码区 buff_def buff_pos;//标号编码区 buff_def buff_bits;//编码类型标识区(1,字符;0,标号) const uint8_t *in; int in_len; uint8_t cmp_pos;// 匹配到的pos距离 uint8_t cmp_len;// 匹配到的长度 uint8_t cmp_skip;// 窗口移动的距离 }zl77_def; uint8_t zl77_buff_get_byte(buff_def *buff,int index); void zl77_buff_set_byte(buff_def *buff,int index,uint8_t d); void zl77_buff_append_bit(buff_def *buff,int bit); void zl77_buff_append_byte(buff_def *buff, const uint8_t d); int zl77_buff_get_bit(buff_def *buff, int index); zl77_def *zl77_creat(void) { zl77_def *z=calloc(1,sizeof(zl77_def)); z->dict_len=5; z->tran_len=3; } // 删除缓存 void zl77_del_buff(buff_def *buff) { buff_item *t=buff->head; buff_item *o; while(t){ o=t; t=t->next; free(o); } } // 添加一个字节 void zl77_buff_append_byte(buff_def *buff, const uint8_t d) { if(buff->used>=buff->all){ buff_item *t=buff->head; buff_item *t_old=0; while (t) { t_old=t; t=t->next; } t=calloc(1,sizeof(buff_item)); if(t_old){ t_old->next=t; t->prev=t_old; }else{ buff->head=t; } buff->all+=LZ77_BUFF_STEP_SIZE; buff->current=t; buff->current_index=buff->used; } while((buff->used/LZ77_BUFF_STEP_SIZE)>(buff->current_index/LZ77_BUFF_STEP_SIZE)){ buff->current=buff->current->next; buff->current_index+=LZ77_BUFF_STEP_SIZE; } buff->current->data[buff->used%LZ77_BUFF_STEP_SIZE]=d; buff->used++; } // 添加一个位 void zl77_buff_append_bit(buff_def *buff,int bit) { if(buff->bit_used/8>=buff->used){ zl77_buff_append_byte(buff,0); } uint8_t d=zl77_buff_get_byte(buff,buff->bit_used/8); d|=bit<<(buff->bit_used%8); zl77_buff_set_byte(buff,-1,d); buff->bit_used++; } // 调整最近使用的缓冲区 static void zl77_buff_adjust_current(buff_def *buff,int index){ while((index/LZ77_BUFF_STEP_SIZE)>(buff->current_index/LZ77_BUFF_STEP_SIZE)){ buff->current=buff->current->next; buff->current_index+=LZ77_BUFF_STEP_SIZE; } while((index/LZ77_BUFF_STEP_SIZE)<(buff->current_index/LZ77_BUFF_STEP_SIZE)){ buff->current=buff->current->prev; buff->current_index-=LZ77_BUFF_STEP_SIZE; } } // 获取指定字节 uint8_t zl77_buff_get_byte(buff_def *buff,int index){ if(index<0) index=buff->used+index; if(index>=buff->used||index<0) return 0; zl77_buff_adjust_current(buff,index); return buff->current->data[index%LZ77_BUFF_STEP_SIZE]; } // 设置指定字节 void zl77_buff_set_byte(buff_def *buff,int index,uint8_t d){ if(index<0) index=buff->used+index; if(index>=buff->used||index<0) return ; zl77_buff_adjust_current(buff,index); buff->current->data[index%LZ77_BUFF_STEP_SIZE]=d; } // 获取指定位 int zl77_buff_get_bit(buff_def *buff, int index){ uint8_t d=zl77_buff_get_byte(buff,index/8); return (d&(1<<(index%8)))?1:0; } void zl77_buff_print(buff_def *buff) { DBG_LOG("buff:["); for(int i=0;iused;i++){ DBG_LOG("%02x ",zl77_buff_get_byte(buff,i)); } DBG_LOG("]\n"); } static uint8_t zl77_get_char(zl77_def *z,int index) { // DBG_LOG("get_char:[%d]\n",index); if(index<0||index>=z->in_len) return 0; return z->in[index]; } // 比对,找到了返回0没找到返回1 // 0记录标号,1记录原始数据 static int zl77_cmp(zl77_def *z,int index){ uint8_t pos=0; uint8_t len=0; // DBG_LOG("index=%d\n",index); for(int i=z->dict_len;i>0;i--){ if(zl77_get_char(z,index-i)==zl77_get_char(z,index)){ pos=i; len=0; for(int j=0;jz->cmp_len){ z->cmp_len=len; z->cmp_pos=pos; } }else{ len=0; break; } } } } if((pos|len)==0){ z->cmp_skip=1; return 1; } else{ // for(int i=0;icmp_len;i++){ // DBG_LOG("%02x|%02x ",zl77_get_char(z,index-z->cmp_pos+i),zl77_get_char(z,index+i)); // } z->cmp_skip=z->cmp_len; return 0; } } static inline void zl77_append_u32(uint8_t *data,int *index,uint32_t value){ data[(*index)++]=value&0xff; data[(*index)++]=(value>>8)&0xff; data[(*index)++]=(value>>16)&0xff; data[(*index)++]=(value>>24)&0xff; } static inline uint32_t zl77_get_u32(const uint8_t *data,int index){ uint32_t ret=0; for(int i=0;i<4;i++){ ret|=data[index+i]<<(8*i); } return ret; } int zl77_encode(const uint8_t *in,const int in_len,uint8_t **out,int *out_len) { int ret; zl77_def *z=zl77_creat(); z->in=in; z->in_len=in_len; for(int i=0;iin_len;){ z->cmp_pos=0; z->cmp_len=0; ret=zl77_cmp(z,i); if(ret){ zl77_buff_append_byte(&z->buff_chars,zl77_get_char(z,i)); // DBG_LOG("char(%c);",zl77_get_char(z,i)); }else{ zl77_buff_append_byte(&z->buff_pos,((z->cmp_pos&0xf)<<4)|(z->cmp_len&0xf)); // DBG_LOG("pos(%d,%d);",z->cmp_pos,z->cmp_len); if((z->cmp_pos|z->cmp_len)==0){ exit(1); } } zl77_buff_append_bit(&z->buff_bits,ret); i+=z->cmp_skip; } // DBG_LOG("\n"); // zl77_buff_print(&z->buff_chars); // zl77_buff_print(&z->buff_pos); // zl77_buff_print(&z->buff_bits); uint32_t size_chars=z->buff_chars.used; uint32_t size_pos=z->buff_pos.used; uint32_t size_bits=z->buff_bits.used; uint32_t size_unpack=z->in_len; int index=0; (*out_len)=16+size_chars+size_pos+size_bits; (*out)=calloc(*out_len,sizeof(uint8_t)); zl77_append_u32(*out,&index,size_chars); zl77_append_u32(*out,&index,size_pos); zl77_append_u32(*out,&index,size_bits); zl77_append_u32(*out,&index,size_unpack); for(int i=0;ibuff_chars,i); } for(int i=0;ibuff_pos,i); } for(int i=0;ibuff_bits,i); } zl77_del_buff(&z->buff_chars); zl77_del_buff(&z->buff_pos); zl77_del_buff(&z->buff_bits); free(z); DBG_LOG("in_len=%d,out_len=%d\n",in_len,*out_len); return 0; } static inline int zl77_get_bit(const uint8_t *data,int index){ uint8_t c=data[index/8]; return c&(1<<(index%8))?1:0; } int zl77_decode(const uint8_t* in, const int in_len, uint8_t** out, int* out_len) { int ret; int index_chars=0; int index_pos=0; int index_bits=0; uint8_t cmp_pos,cmp_len,ch; zl77_def *z=zl77_creat(); uint32_t size_chars=zl77_get_u32(in,0); uint32_t size_pos=zl77_get_u32(in,4); uint32_t size_bits=zl77_get_u32(in,8); uint32_t size_unpack=zl77_get_u32(in,12); const uint8_t *chars=in+16; const uint8_t *pos=in+16+size_chars; const uint8_t *bits=in+16+size_chars+size_pos; (*out)=calloc(size_unpack+1,sizeof(uint8_t)); for(int i=0;i>4; cmp_len=pos[index_pos]&0xf;index_pos++; // DBG_LOG("pos(%d,%d)",cmp_pos,cmp_len); memcpy(&(*out)[i],&(*out)[i-cmp_pos],cmp_len); i+=cmp_len; } } // DBG_LOG("\n"); free(z); return 0; } void main(int argc,const char *argv[]) { uint8_t *encode_data=0; int encode_len=0; uint8_t *decode_data=0; int decode_len=0; hm_encode(argv[1],strlen(argv[1]),&encode_data,&encode_len); // for(int i=0;i