huffman.cpp
上传用户:cjw5120
上传日期:2022-05-11
资源大小:5032k
文件大小:7k
源码类别:

网络截获/分析

开发平台:

Visual C++

  1. // Huffman1.cpp: implementation of the CHuffman class.
  2. //
  3. //////////////////////////////////////////////////////////////////////
  4. #include "stdafx.h"
  5. #include "Huffman.h"
  6. //#include <alloc.h>
  7. #include <dos.h>
  8. #include <fcntl.h>
  9. #ifdef _DEBUG
  10. #undef THIS_FILE
  11. static char THIS_FILE[]=__FILE__;
  12. #define new DEBUG_NEW
  13. #endif
  14. //////////////////////////////////////////////////////////////////////
  15. // Construction/Destruction
  16. //////////////////////////////////////////////////////////////////////
  17. CHuffman::CHuffman()
  18. {
  19. _maskshuff[0] = &(_mask.chars.c3);
  20. _maskshuff[1] = &(_mask.chars.c2);
  21. _maskshuff[2] = &(_mask.chars.c1);
  22. _maskshuff[3] = &(_mask.chars.c0);
  23. }
  24. CHuffman::~CHuffman()
  25. {
  26. }
  27. void CHuffman::ntXORcode(char *outbuff, char *inbuff, long lSize )
  28. {
  29. for(; lSize > 0; lSize--)
  30. {
  31.      *outbuff ^= *inbuff;
  32.  outbuff++;
  33.  inbuff++;
  34. }
  35. }
  36. int CHuffman::ntDecode(char *outbuff, char *inbuff )
  37. {
  38. int c, i, nchildren;
  39. int inleft;
  40. _eof = &_characters[0];
  41. if (inbuff[0] != US) return( 0 );
  42. if (inbuff[1] != RS) return( 0 );
  43. _inp = &inbuff[2];
  44. _origsize = 0;
  45. for (i=0; i<4; i++)
  46. _origsize = _origsize*256 + ((*_inp++) & 0377);
  47. inleft = _origsize;
  48. _dmaxlev = *_inp++ & 0377;
  49. if (_dmaxlev > 24) return( 0 );
  50. for (i=1; i<=_dmaxlev; i++)
  51. _intnodes[i] = *_inp++ & 0377;
  52. for (i=1; i<=_dmaxlev; i++) {
  53. _tree[i] = _eof;
  54. for (c=_intnodes[i]; c>0; c--) {
  55. if (_eof >= &_characters[255]) return( 0 );
  56. *_eof++ = *_inp++;
  57. }
  58. }
  59. *_eof++ = *_inp++;
  60. _intnodes[_dmaxlev] += 2;
  61. inleft -= _inp - &inbuff[0];
  62. if (inleft < 0) return( 0 );
  63. nchildren = 0;
  64. for (i=_dmaxlev; i>=1; i--) {
  65. c = _intnodes[i];
  66. _intnodes[i] = nchildren /= 2;
  67. nchildren += c;
  68. }
  69. return ( _decode( inleft,outbuff ));
  70. }
  71. int CHuffman::_decode( int inleft, char *outbuff )
  72. {
  73. int bitsleft, c, i;
  74. int j, lev;
  75. char *p;
  76. _outp = &outbuff[0];
  77. lev = 1;
  78. i = 0;
  79. while (1) {
  80. if (--inleft < 0) return( 0 );
  81. c = *_inp++;
  82. bitsleft = 8;
  83. while (--bitsleft >= 0) {
  84. i *= 2;
  85. if (c & 0200)
  86. i++;
  87. c <<= 1;
  88. if ((j = i - _intnodes[lev]) >= 0) {
  89. p = &_tree[lev][j];
  90. if (p == _eof){
  91. c = _outp - &outbuff[0];
  92. _origsize -= c;
  93. if (_origsize != 0) return( 0 );
  94. return (1);
  95. }
  96. *_outp++ = *p;
  97. lev = 1;
  98. i = 0;
  99. }else
  100. lev++;
  101. }
  102. }
  103. }
  104. int CHuffman::ntIsarc(char *inbuff )
  105. {
  106. if( inbuff[0] == US && inbuff[1] == RS )
  107. return( 1 );
  108. else
  109. return( 0 );
  110. }
  111. int CHuffman::ntGetorig(char *inbuff )
  112. {
  113. int i;
  114. char *in;
  115. int size;
  116. in = inbuff+2;
  117. size = 0;
  118. for (i=0; i<4; i++)
  119. size = size*256 + ((*in++) & 0377);
  120. return( size );
  121. }
  122. int CHuffman::ntEncode(char *outbuff, char *inbuff, int buflen )
  123. {
  124.         register int c, i, p;
  125.         long bitsout;
  126. _input( inbuff,buflen );
  127.         _diffbytes = -1;
  128. _count[ END ] = 1;
  129. _insize.lint.lng = 0L;
  130. _n_ = 0;
  131.         for (i=END; i>=0; i--) {
  132.                 _parent[i] = 0;
  133.                 if (_count[i] > 0) {
  134.                         _diffbytes++;
  135.                         _insize.lint.lng += _count[i];
  136.                         _heap[++_n_].count = _count[i];
  137.                         _heap[_n_].node = i;
  138.                 }
  139. }
  140. if (_diffbytes == 1) return( 0 );
  141.         _insize.lint.lng >>= 1;
  142.         for (i=_n_/2; i>=1; i--)
  143. _heapify(i);
  144.         _lastnode = END;
  145.         while (_n_ > 1) {
  146.                 _parent[_heap[1].node] = ++_lastnode;
  147.                 _inc = _heap[1].count;
  148.                 hmove (_heap[_n_], _heap[1]);
  149.                 _n_--;
  150. _heapify(1);
  151.                 _parent[_heap[1].node] = _lastnode;
  152.                 _heap[1].node = _lastnode;
  153.                 _heap[1].count += _inc;
  154. _heapify(1);
  155.         }
  156.         _parent[_lastnode] = 0;
  157.         bitsout = _maxlev = 0;
  158.         for (i=1; i<=24; i++)
  159.                 _levcount[i] = 0;
  160.         for (i=0; i<=END; i++) {
  161.                 c = 0;
  162.                 for (p=_parent[i]; p!=0; p=_parent[p])
  163.                         c++;
  164.                 _levcount[c]++;
  165.                 _length[i] = c;
  166.                 if (c > _maxlev)
  167.                         _maxlev = c;
  168.                 bitsout += c*(_count[i]>>1);
  169.         }
  170.         if (_maxlev > 24) return( 0 );
  171.         _inc = 1L << 24;
  172.         _inc >>= _maxlev;
  173.         _mask.lint.lng = 0;
  174.         for (i=_maxlev; i>0; i--) {
  175.                 for (c=0; c<=END; c++)
  176.                         if (_length[c] == i) {
  177.                                 _bits[c] = _mask.lint.lng;
  178.                                 _mask.lint.lng += _inc;
  179.                         }
  180.                 _mask.lint.lng &= ~_inc;
  181.                 _inc <<= 1;
  182.         }
  183. return( _output( outbuff,inbuff,buflen ));
  184. }
  185. void CHuffman::_input (char *inbuff, int buflen )
  186. {
  187. register int i;
  188.         for (i=0; i<END; i++)
  189.                 _count[i] = 0;
  190. while (buflen > 0)
  191. _count[inbuff[--buflen]&0377] += 2;
  192. }
  193. int CHuffman::_output(char *outbuff,char *inbuff, int buflen )
  194. {
  195. int c, i;
  196.         char *inp;
  197.         register char **q, *outp;
  198.         register int bitsleft;
  199.         long temp;
  200.         outbuff[0] = 037;       /* ascii US */
  201. outbuff[1] = 036;       /* ascii RS */
  202.         temp = _insize.lint.lng;
  203.         for (i=5; i>=2; i--) {
  204.                 outbuff[i] =  (char) (temp & 0377);
  205.                 temp >>= 8;
  206.         }
  207.         outp = outbuff+6;
  208.         *outp++ = _maxlev;
  209.         for (i=1; i<_maxlev; i++)
  210.                 *outp++ = _levcount[i];
  211.         *outp++ = _levcount[_maxlev]-2;
  212.         for (i=1; i<=_maxlev; i++)
  213.                 for (c=0; c<END; c++)
  214.                         if (_length[c] == i)
  215.                                 *outp++ = c;
  216. inp = inbuff;
  217.         bitsleft = 8;
  218.         do {
  219.                 c = (--buflen < 0) ? END : (*inp++ & 0377);
  220.                 _mask.lint.lng = _bits[c]<<bitsleft;
  221.                 q = &_maskshuff[0];
  222.                 if (bitsleft == 8)
  223.                         *outp = **q++;
  224.                 else
  225.                         *outp |= **q++;
  226.                 bitsleft -= _length[c];
  227.                 while (bitsleft < 0) {
  228.                         *++outp = **q++;
  229.                         bitsleft += 8;
  230.                 }
  231.         } while (c != END);
  232.         if (bitsleft < 8)
  233.                 outp++;
  234.         c = outp-outbuff;
  235. return (c);
  236. }
  237. void CHuffman::_heapify(int i )
  238. {
  239.         register int k;
  240.         int lastparent;
  241. struct _heap heapsubi;
  242.         hmove (_heap[i], heapsubi);
  243.         lastparent = _n_/2;
  244.         while (i <= lastparent) {
  245.                 k = 2*i;
  246.                 if (_heap[k].count > _heap[k+1].count && k < _n_)
  247.                         k++;
  248.                 if (heapsubi.count < _heap[k].count)
  249.                         break;
  250.                 hmove (_heap[k], _heap[i]);
  251.                 i = k;
  252.         }
  253.         hmove (heapsubi, _heap[i]);
  254. }