Huffman.cpp
上传用户:deer201011
上传日期:2022-06-24
资源大小:10k
文件大小:6k
源码类别:

压缩解压

开发平台:

Visual C++

  1. // Huffman.cpp
  2. #include "CompressedFile.h"
  3. #define END_OF_STREAM 256
  4. BOOL CHuffmanFile::Open( const char *pszFileName, unsigned int nOpenFlags, CFileException *pError )
  5. {
  6. m_nCompressionType = HUFF;
  7. InitializeTree();
  8. return( CCompressedFile::Open( pszFileName, nOpenFlags, pError ) );
  9. }
  10. void CHuffmanFile::Close( void )
  11. {
  12. if( m_nFlags != CFile::modeRead ) EncodeSymbol( END_OF_STREAM );
  13. CCompressedFile::Close();
  14. if( m_nFlags == ( CFile::modeCreate | CFile::modeWrite ) || m_nFlags == CFile::modeWrite ){
  15. CFile cf;
  16. cf.Open( m_szFilename, CFile::modeWrite );
  17. cf.Seek( m_dwSeekTo, CFile::begin );
  18. cf.Write( &m_dwUncompressedSize, sizeof( DWORD ) );
  19. cf.Write( &m_dwCompressedSize, sizeof( DWORD ) );
  20. cf.Close();
  21. }
  22. }
  23. unsigned int CHuffmanFile::Read( void far *lpBuf, unsigned int nCount )
  24. {
  25. unsigned char *pTransfer;
  26. int nSymbol;
  27. unsigned int nBytesRead = 0;
  28. pTransfer = (unsigned char *) lpBuf;
  29. for( unsigned int i=0; i<nCount; i++ ){
  30. nSymbol = DecodeSymbol();
  31. if( nSymbol == END_OF_STREAM ) i = nCount;
  32. else{
  33. pTransfer[i] = (unsigned char) nSymbol;
  34. nBytesRead++;
  35. UpdateModel( nSymbol );
  36. }
  37. }
  38. return( nBytesRead );
  39. }
  40. void CHuffmanFile::Write( void *lpBuf, unsigned int nCount )
  41. {
  42. unsigned char *pTransfer;
  43. pTransfer = (unsigned char *) lpBuf;
  44. for( unsigned int i=0; i<nCount; i++ ){
  45. EncodeSymbol( (int) pTransfer[i] );
  46. UpdateModel( (int) pTransfer[i] );
  47. }
  48. m_dwUncompressedSize += (DWORD) nCount;
  49. }
  50. void CHuffmanFile::InitializeTree( void )
  51. {
  52. memset( &Tree, 0, sizeof( TREE ) );
  53. Tree.nodes[ROOT_NODE].nChild = ROOT_NODE + 1;
  54. Tree.nodes[ROOT_NODE].nChildIsLeaf = FALSE;
  55. Tree.nodes[ROOT_NODE].nWeight = 2;
  56. Tree.nodes[ROOT_NODE].nParent = -1;
  57. Tree.nodes[ROOT_NODE+1].nChild = END_OF_STREAM;
  58. Tree.nodes[ROOT_NODE+1].nChildIsLeaf = TRUE;
  59. Tree.nodes[ROOT_NODE+1].nWeight = 1;
  60. Tree.nodes[ROOT_NODE+1].nParent = ROOT_NODE;
  61. Tree.nLeaf[END_OF_STREAM] = ROOT_NODE + 1;
  62. Tree.nodes[ROOT_NODE+2].nChild = ESCAPE;
  63. Tree.nodes[ROOT_NODE+2].nChildIsLeaf = TRUE;
  64. Tree.nodes[ROOT_NODE+2].nWeight = 1;
  65. Tree.nodes[ROOT_NODE+2].nParent = ROOT_NODE;
  66. Tree.nLeaf[ESCAPE] = ROOT_NODE + 2;
  67. Tree.nNextFreeNode = ROOT_NODE + 3;
  68. for( int i=0; i<END_OF_STREAM; i++ ) Tree.nLeaf[i] = -1;
  69. }
  70. void CHuffmanFile::UpdateModel( int nSymbol )
  71. {
  72. int nCurrentNode;
  73. int nNewNode;
  74. if( Tree.nodes[ROOT_NODE].nWeight == MAX_WEIGHT ) RebuildTree();
  75. nCurrentNode = Tree.nLeaf[nSymbol];
  76. while( nCurrentNode != -1 ){
  77. Tree.nodes[nCurrentNode].nWeight++;
  78. for( nNewNode=nCurrentNode; nNewNode>ROOT_NODE; nNewNode-- )
  79. if( Tree.nodes[nNewNode-1].nWeight >= Tree.nodes[nCurrentNode].nWeight) break;
  80. if( nCurrentNode != nNewNode ){
  81. SwapNodes( nCurrentNode, nNewNode );
  82. nCurrentNode = nNewNode;
  83. }
  84. nCurrentNode = Tree.nodes[nCurrentNode].nParent;
  85. }
  86. }
  87. void CHuffmanFile::EncodeSymbol( unsigned int nSymbol )
  88. {
  89. DWORD dwCode = 0;
  90. DWORD dwCurrentBit = 1;
  91. int nCodeSize = 0;
  92. int nCurrentNode = Tree.nLeaf[nSymbol];
  93. if( nCurrentNode == -1 ) nCurrentNode = Tree.nLeaf[ESCAPE];
  94. while( nCurrentNode != ROOT_NODE ){
  95. if( !( nCurrentNode & 1 ) ) dwCode |= dwCurrentBit;
  96. dwCurrentBit <<= 1;
  97. nCodeSize++;
  98. nCurrentNode = Tree.nodes[nCurrentNode].nParent;
  99. };
  100. OutputBits( dwCode, nCodeSize );
  101. if( Tree.nLeaf[nSymbol] == -1 ){
  102. OutputBits( (DWORD) nSymbol, 8 );
  103. AddNewNode( nSymbol );
  104. }
  105. }
  106. void CHuffmanFile::AddNewNode( int nSymbol )
  107. {
  108. int nLightestNode = Tree.nNextFreeNode - 1;
  109. int nNewNode = Tree.nNextFreeNode;
  110. int nZeroWeightNode = Tree.nNextFreeNode + 1;
  111. Tree.nNextFreeNode += 2;
  112. Tree.nodes[nNewNode] = Tree.nodes[nLightestNode];
  113. Tree.nodes[nNewNode].nParent = nLightestNode;
  114. Tree.nLeaf[Tree.nodes[nNewNode].nChild] = nNewNode;
  115. Tree.nodes[nLightestNode].nChild = nNewNode;
  116. Tree.nodes[nLightestNode].nChildIsLeaf = FALSE;
  117. Tree.nodes[nZeroWeightNode].nChild = nSymbol;
  118. Tree.nodes[nZeroWeightNode].nChildIsLeaf = TRUE;
  119. Tree.nodes[nZeroWeightNode].nWeight = 0;
  120. Tree.nodes[nZeroWeightNode].nParent = nLightestNode;
  121. Tree.nLeaf[nSymbol] = nZeroWeightNode;
  122. }
  123. int CHuffmanFile::DecodeSymbol( void )
  124. {
  125. int nCurrentNode;
  126. int nSymbol;
  127. nCurrentNode = ROOT_NODE;
  128. while( !Tree.nodes[nCurrentNode].nChildIsLeaf ){
  129. nCurrentNode = Tree.nodes[nCurrentNode].nChild;
  130. nCurrentNode += (int) InputBit();
  131. }
  132. nSymbol = Tree.nodes[nCurrentNode].nChild;
  133. if( nSymbol == ESCAPE ){
  134. nSymbol = (int) InputBits( 8 );
  135. AddNewNode( nSymbol );
  136. }
  137. return( nSymbol );
  138. }
  139. void CHuffmanFile::RebuildTree( void )
  140. {
  141. int i, j, k;
  142. unsigned int nWeight;
  143. j = Tree.nNextFreeNode - 1;
  144. for( i=j; i>=ROOT_NODE; i-- ){
  145. if( Tree.nodes[i].nChildIsLeaf ){
  146. Tree.nodes[j] = Tree.nodes[i];
  147. Tree.nodes[j].nWeight = ( Tree.nodes[j].nWeight + 1 ) >> 1;
  148. j--;
  149. }
  150. }
  151. for( i=Tree.nNextFreeNode-2; j>=ROOT_NODE; i-=2, j-- ){
  152. k = i + 1;
  153. Tree.nodes[j].nWeight = Tree.nodes[i].nWeight + Tree.nodes[k].nWeight;
  154. nWeight = Tree.nodes[j].nWeight;
  155. Tree.nodes[j].nChildIsLeaf = FALSE;
  156. for( k=j+1; nWeight<Tree.nodes[k].nWeight; k++ );
  157. k--;
  158. memmove( &Tree.nodes[j], &Tree.nodes[j+1], ( k - j ) * sizeof( struct node ) );
  159. Tree.nodes[k].nWeight = nWeight;
  160. Tree.nodes[k].nChild = i;
  161. Tree.nodes[k].nChildIsLeaf = FALSE;
  162. }
  163. for( i=Tree.nNextFreeNode-1; i>=ROOT_NODE; i-- ){
  164. if( Tree.nodes[i].nChildIsLeaf ){
  165. k = Tree.nodes[i].nChild;
  166. Tree.nLeaf[k] = i;
  167. }
  168. else{
  169. k = Tree.nodes[i].nChild;
  170. Tree.nodes[k].nParent = Tree.nodes[k+1].nParent = i;
  171. }
  172. }
  173. }
  174. void CHuffmanFile::SwapNodes( int i, int j )
  175. {
  176. struct node temp;
  177. if( Tree.nodes[i].nChildIsLeaf ) Tree.nLeaf[Tree.nodes[i].nChild] = j;
  178. else{
  179. Tree.nodes[Tree.nodes[i].nChild].nParent = j;
  180. Tree.nodes[Tree.nodes[i].nChild+1].nParent = j;
  181. }
  182. if( Tree.nodes[j].nChildIsLeaf ) Tree.nLeaf[Tree.nodes[j].nChild] = i;
  183. else{
  184. Tree.nodes[Tree.nodes[j].nChild].nParent = i;
  185. Tree.nodes[Tree.nodes[j].nChild+1].nParent = i;
  186. }
  187. temp = Tree.nodes[i];
  188. Tree.nodes[i] = Tree.nodes[j];
  189. Tree.nodes[i].nParent = temp.nParent;
  190. temp.nParent = Tree.nodes[j].nParent;
  191. Tree.nodes[j] = temp;
  192. }