易码技术论坛

 找回密码
 加入易码
搜索
查看: 2120|回复: 6

[演示] lava版lzw压缩算法

[复制链接]
发表于 2008-2-2 12:59:14 | 显示全部楼层 |阅读模式
平台:lava20k或24k
  1. #define TABLESIZE 2048//2^MAXBITS字典大小
  2. #define INITBITS 9 //初始位
  3. #define MAXBITS 11//in theory it can be 16 but limited by NC3000 ram最大位
  4. #define HASHSHIFT MAXBITS-8 //用于compress中的hash函数
  5. #define CLEARCODE 256 //清除字典标志
  6. #define TERMINATOR 257 //结束标志
  7. #define FIRSTCODE 258 //第一个代码
  8. #define ESC_KEY 27
  9. #define DECODESIZE 1000 //解压字串缓存大小
  10. //字典树,前后缀都是为了在压缩时防止hash函数冲突用的
  11. struct TABLE
  12. {
  13. int value; //存放CODE
  14. int prefix; //前缀
  15. char append; //后缀
  16. };
  17. struct TABLE table[TABLESIZE];

  18. long buffer; //input和output的缓存
  19. char bitscounter; //buffer中的位数
  20. int index; //索引
  21. long maxcode; //最大的code
  22. char bitsnum; //当前code的位数
  23. int nextcode; //当前code
  24. int bytesin; //已读取的字节数
  25. char decode[DECODESIZE]; //解压字串缓存
  26. int decounter; //解压字串计数器

  27. char infilename[60],outfilename[60];//filepath
  28. char infile,outfile;//filehandle

  29. //返回maxcode
  30. int maxval(char n)
  31. {
  32. return((1<<n)-1);
  33. }

  34. //清空字典
  35. void cleartable()
  36. {
  37. int i;
  38. bitsnum=INITBITS;
  39. nextcode=FIRSTCODE;
  40. maxcode=maxval(bitsnum);
  41. for(i=0;i<TABLESIZE;i++)
  42. table[i].value=-1;
  43. }

  44. //初始化
  45. void init()
  46. {
  47. infile=outfile=buffer=bitscounter=0;
  48. bytesin=0;
  49. memset(infilename,0,60);
  50. memset(outfilename,0,60);
  51. }


  52. //get the length of a file
  53. long fsize(char fp)
  54. {
  55. long a,b;
  56. a=ftell(fp);
  57. b=fseek(fp,0,2);
  58. fseek(fp,a,0);
  59. return b;
  60. }

  61. //to find a word from the end of a string,return the position in the string
  62. char findword(char &string[],char word)
  63. {
  64. int i;
  65. for(i=strlen(string);i>0;i--)
  66. {
  67. if(string[i-1]==word)break;
  68. }
  69. return (i-1);
  70. }

  71. //if choose a file return 1 else return 0
  72. char choose()
  73. {
  74. char path[15];
  75. char i;
  76. memset(path,0,15);
  77. ChDir("/");
  78. for(;;)
  79. {
  80. if(!FileList(path)||!strcmp(path,".."))
  81.   {
  82.   if(infilename[0]==0)return 0;
  83.   ChDir("..");
  84.   infilename[findword(infilename,'/')]=0;
  85.   continue;
  86.   }
  87. strcat(infilename,"/");
  88. strcat(infilename,path);
  89. if(!ChDir(path))break;
  90. }
  91. return 1;
  92. }

  93. //find node in the tree
  94. int findnode(int prefix,char word)
  95. {
  96. int offset;
  97. int pointer;
  98. //通过一个hash函数进行定位
  99. pointer=(word<<HASHSHIFT)^prefix;
  100. //以后的都是为了解决冲突
  101. while(pointer>=TABLESIZE)
  102. pointer=pointer-(TABLESIZE>>1);
  103. if(pointer)
  104. offset=TABLESIZE-pointer;
  105. else
  106. offset=1;
  107. for(;;)
  108. {
  109. if(table[pointer].value==-1)
  110.   return(pointer);
  111. if(table[pointer].prefix==prefix&&table[pointer].append==word)
  112.   return(pointer);
  113. //if has a colesion
  114. pointer=pointer-(offset--);
  115. if(!offset)
  116.   offset=TABLESIZE>>1;
  117. if(pointer<0)
  118.   pointer=pointer+TABLESIZE;
  119. }
  120. }

  121. //动态输出
  122. void outputc(char fp,int code)
  123. {
  124. buffer=buffer|code<<(32-bitsnum-bitscounter);
  125. bitscounter=bitscounter+bitsnum;
  126. while(bitscounter>=8)
  127. {
  128. putc(buffer>>24,outfile);
  129. bitscounter=bitscounter-8;
  130. buffer=buffer<<8;
  131. }
  132. }

  133. //由于压缩时是动态输出,解压时也要动态输入
  134. int input(char fp)
  135. {
  136. int value;
  137. while(bitscounter<=24)
  138. {
  139. buffer=buffer|getc(fp)<<(24-bitscounter);
  140. bitscounter=bitscounter+8;
  141. }
  142. value=buffer>>(32-bitsnum);
  143. bitscounter=bitscounter-bitsnum;
  144. buffer=buffer<<bitsnum;
  145. return(value);
  146. }

  147. //解压字串的函数
  148. void decodestring(char &data[],int code)
  149. {
  150. int i=0;
  151. while(code>255)
  152. {
  153. data[decounter++]=table[code].append;
  154. code=table[code].prefix;
  155. if(++i>=DECODESIZE)
  156.   {
  157.   SetScreen(1);
  158.   fclose(infile);
  159.   fclose(outfile);
  160.   printf("out of the decode area");
  161.   getchar();
  162.   exit(1);
  163.   }
  164. }
  165. data[decounter]=code;
  166. }

  167. //解压
  168. void expand()
  169. {
  170. int character,stringcode; //后缀和前缀
  171. char flag=1; //是否遇到CLEARCODE的标志,置一以后连序读两个字节
  172. long len=0; //原始文件大小,用于检验文件是否正确压缩
  173. char name[15]; //原文件名
  174. memset(name,0,15);
  175. infile=fopen(infilename,"rb");
  176. if(!infile)
  177. {
  178. SetScreen(1);
  179. printf("open file error!\n");
  180. getchar();
  181. return;
  182. }
  183. if(getc(infile)!='l'||getc(infile)!='z'||getc(infile)!='w')
  184. {
  185. SetScreen(1);
  186. printf("This is not a lzw file!");
  187. fclose(infile);
  188. getchar();
  189. return;
  190. }
  191. fread(&len,1,4,infile);//get the length of file
  192. character=getc(infile); //get the name of file
  193. fread(name,1,character,infile);
  194. strcpy(outfilename,infilename);
  195. //change outfile name
  196. strcpy(outfilename+1+findword(outfilename,'/'),name);
  197. outfile=fopen(outfilename,"w");
  198. if(!outfile)
  199. {
  200. fclose(infile);
  201. SetScreen(1);
  202. printf("Create file error!");
  203. getchar();
  204. return;
  205. }
  206. SetScreen(1);
  207. printf("expanding...\n");
  208. nextcode=FIRSTCODE;
  209. bitsnum=INITBITS;
  210. maxcode=maxval(bitsnum);
  211. decounter=0;
  212. while((index=input(infile))!=TERMINATOR) //遇到结束标志就停止
  213. {
  214. if(Inkey()==ESC_KEY)
  215.   {
  216.   fclose(infile);
  217.   fclose(outfile);
  218.   DeleteFile(outfilename);
  219.   SetScreen(1);
  220.   printf("ESC KEY HAS BEEN PUSHED!");
  221.   getchar();
  222.   return;
  223.   }
  224. if(++bytesin==1000) //统计进度
  225.   {
  226.   putchar('.');
  227.   bytesin=0;
  228.   }
  229. if(index==CLEARCODE) //如果遇到清除标志的处理
  230.   {
  231.   flag=1;
  232.   nextcode=FIRSTCODE;
  233.   bitsnum=INITBITS;
  234.   maxcode=maxval(bitsnum);
  235.   putchar('C');
  236.   continue;
  237.   }
  238. if(flag) //如果上一个是清除标志,就再读一个字节
  239.   {
  240.   flag=0;
  241.   stringcode=character=index;
  242.   putc(character,outfile);
  243.   continue;
  244.   }
  245. if(index>=nextcode) //读到字典中还没有的数
  246.   {
  247.   decode[0]=character;
  248.   decounter=1;
  249.   decodestring(decode,stringcode);
  250.   }
  251. else //读到字典中已有的数
  252.   {
  253.   decounter=0;
  254.   decodestring(decode,index);
  255.   }
  256. character=decode[decounter]; //解压后的最后一个字节是后缀
  257. while(decounter>=0) //输出字串
  258.   putc(decode[decounter--],outfile);
  259. //nextcode+1
  260. //因为压缩的关系,nextcode一定是小于字典大小
  261. if(nextcode<=maxcode)
  262.   {
  263.   table[nextcode].prefix=stringcode;
  264.   table[nextcode++].append=character;
  265.   if(nextcode==maxcode&&bitsnum<MAXBITS)
  266.    {
  267.    putchar('+');
  268.    maxcode=maxval(++bitsnum);
  269.    }
  270.   }
  271. stringcode=index;
  272. }//while

  273. //判断是否成功解压
  274. if(len!=ftell(outfile))
  275. {
  276. fclose(infile);
  277. fclose(outfile);
  278. SetScreen(1);
  279. printf("Did not expand exactly,please check your programme!");
  280. getchar();
  281. return;
  282. }
  283. fclose(infile);
  284. fclose(outfile);
  285. SetScreen(1);
  286. printf("in:%s\nout:%s\nOK",infilename,outfilename);
  287. getchar();
  288. }

  289. //procedure compress
  290. void compress()
  291. {
  292. int stringcode,i; //stringcode前缀
  293. char character,flag=0;  //character后缀
  294. long inlen,outlen; //输入输出文件大小
  295. char name[15];
  296. infile=fopen(infilename,"rb");
  297. if(!infile)
  298. {
  299. SetScreen(1);
  300. printf("open file error!\n");
  301. getchar();
  302. return;
  303. }
  304. strcpy(outfilename,infilename);
  305. strcpy(name,infilename+1+findword(infilename,'/'));//get name of infile
  306. for(i=strlen(outfilename);i>0;i--)
  307. {
  308. if(outfilename[i-1]=='/')break;
  309. if(outfilename[i-1]=='.')
  310.   {
  311.   outfilename[i-1]=0;
  312.   break;
  313.   }
  314. }
  315. strcat(outfilename,".lzw");
  316. outfile=fopen(outfilename,"w");
  317. if(!outfile)
  318. {
  319. fclose(infile);
  320. SetScreen(1);
  321. printf("Create file error!");
  322. getchar();
  323. return;
  324. }
  325. inlen=fsize(infile);
  326. fwrite("lzw",1,3,outfile);
  327. fwrite(&inlen,1,4,outfile);
  328. inlen=strlen(name);
  329. fwrite(&inlen,1,1,outfile);
  330. fwrite(name,1,inlen,outfile);
  331. SetScreen(1);
  332. printf("Compressing...\n");
  333. cleartable();
  334. stringcode=getc(infile);
  335. while(!feof(infile))
  336. {
  337. if(Inkey()==ESC_KEY)
  338.   {
  339.   fclose(infile);
  340.   fclose(outfile);
  341.   DeleteFile(outfilename);
  342.   SetScreen(1);
  343.   printf("ESC KEY HAS BEEN PUSHED!");
  344.   getchar();
  345.   }
  346. character=getc(infile);
  347. //压缩进度
  348. if(++bytesin==1000)
  349.   {
  350.   putchar('.');
  351.   bytesin=0;
  352.   }
  353. index=findnode(stringcode,character); //通过hash函数查找节点
  354. /* table[index].value already exist */
  355. if(table[index].value!=-1) //如过节点值存在,前缀等于节点值
  356.   stringcode=table[index].value;
  357. /* table[index].value not exist */
  358. else //如果节点值不存在
  359.   {
  360.   if(nextcode<=maxcode) //如果没达到上限,就添加进字典
  361.    {
  362.    table[index].value=nextcode++;
  363.    table[index].prefix=stringcode;
  364.    table[index].append=character;
  365.    }
  366.   outputc(outfile,stringcode); //输出前缀
  367.   stringcode=character; //前缀等于后缀
  368.   if(nextcode>maxcode) //超过上限
  369.    {
  370.    if(bitsnum<MAXBITS)
  371.     {
  372.     putchar('+');
  373.     maxcode=maxval(++bitsnum);
  374.     }
  375.    else  //bitsnum==MAXBITS
  376.     {
  377.     outputc(outfile,CLEARCODE);
  378.     putchar('C');
  379.     cleartable();
  380.     }
  381.    }
  382.   } //else table[index].value==-1
  383. } //while
  384. outputc(outfile,stringcode);
  385. outputc(outfile,TERMINATOR);
  386. outputc(outfile,0); //这两步不能省,用于把buffer中的数据都输出
  387. outputc(outfile,0);
  388. //compression end
  389. inlen=fsize(infile);
  390. outlen=ftell(outfile);
  391. fclose(infile);
  392. fclose(outfile);
  393. SetScreen(1);
  394. printf("in:%s %d Bytes\nout:%s %d Bytes\nOK",infilename,inlen,outfilename,outlen);
  395. getchar();
  396. }

  397. void main()
  398. {
  399. char key;
  400. for(;;)
  401. {
  402. SetScreen(1);
  403. init();
  404. printf("LZW Compression programme\na.compress\nb.expand\nc.exit");
  405. key=getchar();
  406. if(key=='a')
  407.   {
  408.   if(!choose())continue;//if not choose a file
  409.   compress();
  410.   }
  411. else if(key=='b')
  412.   {
  413.   if(!choose())continue;//if not choose a file
  414.   expand();
  415.   }
  416. else if(key==ESC_KEY||key=='c')break;
  417. }
  418. }
复制代码

lzw.rar

4.65 KB, 下载次数: 462

源码和编译好的文件

发表于 2008-2-2 13:36:31 | 显示全部楼层
很实用啊 爽爽爽爽  希望能够开发个BBK解释器 就行了
发表于 2009-5-13 18:38:07 | 显示全部楼层
非常强大,我以前怎么就没发现呢?
发表于 2009-5-14 14:47:13 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
发表于 2009-5-15 12:53:04 | 显示全部楼层
不是……也就是2008年的东西。
只是……我用了一下,速度太慢了。还是Eastsun那个bin的实用。
可惜没有NC2600版的啊,什么时候移植一下
发表于 2009-5-15 23:14:29 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
发表于 2009-5-16 18:39:45 | 显示全部楼层
哎,移植问题很大啊。我捣鼓了半天只能显示个界面来
您需要登录后才可以回帖 登录 | 加入易码

本版积分规则

Archiver|手机版|小黑屋|EMAX Studio

GMT+8, 2024-3-29 18:14 , Processed in 0.016425 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表