📄 zdeflate_8cpp-source.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"><html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"><title>Crypto++: zdeflate.cpp Source File</title><link href="doxygen.css" rel="stylesheet" type="text/css"></head><body><!-- Generated by Doxygen 1.3.2 --><div class="qindex"><a class="qindex" href="index.html">Main Page</a> | <a class="qindex" href="namespaces.html">Namespace List</a> | <a class="qindex" href="hierarchy.html">Class Hierarchy</a> | <a class="qindex" href="classes.html">Alphabetical List</a> | <a class="qindex" href="annotated.html">Compound List</a> | <a class="qindex" href="files.html">File List</a> | <a class="qindex" href="namespacemembers.html">Namespace Members</a> | <a class="qindex" href="functions.html">Compound Members</a> | <a class="qindex" href="globals.html">File Members</a></div><h1>zdeflate.cpp</h1><div class="fragment"><pre>00001 <span class="comment">// zdeflate.cpp - written and placed in the public domain by Wei Dai</span>00002 00003 <span class="comment">// Many of the algorithms and tables used here came from the deflate implementation</span>00004 <span class="comment">// by Jean-loup Gailly, which was included in Crypto++ 4.0 and earlier. I completely</span>00005 <span class="comment">// rewrote it in order to fix a bug that I could not figure out. This code</span>00006 <span class="comment">// is less clever, but hopefully more understandable and maintainable.</span>00007 00008 <span class="preprocessor">#include "pch.h"</span>00009 <span class="preprocessor">#include "zdeflate.h"</span>00010 <span class="preprocessor">#include <functional></span>00011 00012 NAMESPACE_BEGIN(CryptoPP)00013 00014 <span class="keyword">using</span> <span class="keyword">namespace </span>std;00015 00016 LowFirstBitWriter::LowFirstBitWriter(<a class="code" href="class_buffered_transformation.html">BufferedTransformation</a> *attachment)00017 : <a class="code" href="class_filter.html">Filter</a>(attachment), m_counting(false), m_buffer(0), m_bitsBuffered(0), m_bytesBuffered(0)00018 {00019 }00020 00021 <span class="keywordtype">void</span> LowFirstBitWriter::StartCounting()00022 {00023 assert(!m_counting);00024 m_counting = <span class="keyword">true</span>;00025 m_bitCount = 0;00026 }00027 00028 <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> LowFirstBitWriter::FinishCounting()00029 {00030 assert(m_counting);00031 m_counting = <span class="keyword">false</span>;00032 <span class="keywordflow">return</span> m_bitCount;00033 }00034 00035 <span class="keywordtype">void</span> LowFirstBitWriter::PutBits(<span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> value, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> length)00036 {00037 <span class="keywordflow">if</span> (m_counting)00038 m_bitCount += length;00039 <span class="keywordflow">else</span>00040 {00041 m_buffer |= value << m_bitsBuffered;00042 m_bitsBuffered += length;00043 assert(m_bitsBuffered <= <span class="keyword">sizeof</span>(<span class="keywordtype">unsigned</span> <span class="keywordtype">long</span>)*8);00044 <span class="keywordflow">while</span> (m_bitsBuffered >= 8)00045 {00046 m_outputBuffer[m_bytesBuffered++] = (byte)m_buffer;00047 <span class="keywordflow">if</span> (m_bytesBuffered == m_outputBuffer.<a class="code" href="class_sec_block.html#_sec_block_with_hinta13">size</a>())00048 {00049 <a class="code" href="class_filter.html#_zlib_decompressora8">AttachedTransformation</a>()-><a class="code" href="class_buffered_transformation.html#_zlib_decompressorz1_6">PutModifiable</a>(m_outputBuffer, m_bytesBuffered);00050 m_bytesBuffered = 0;00051 }00052 m_buffer >>= 8;00053 m_bitsBuffered -= 8;00054 }00055 }00056 }00057 00058 <span class="keywordtype">void</span> LowFirstBitWriter::FlushBitBuffer()00059 {00060 <span class="keywordflow">if</span> (m_counting)00061 m_bitCount += 8*(m_bitsBuffered > 0);00062 <span class="keywordflow">else</span>00063 {00064 <span class="keywordflow">if</span> (m_bytesBuffered > 0)00065 {00066 <a class="code" href="class_filter.html#_zlib_decompressora8">AttachedTransformation</a>()-><a class="code" href="class_buffered_transformation.html#_zlib_decompressorz1_6">PutModifiable</a>(m_outputBuffer, m_bytesBuffered);00067 m_bytesBuffered = 0;00068 }00069 <span class="keywordflow">if</span> (m_bitsBuffered > 0)00070 {00071 <a class="code" href="class_filter.html#_zlib_decompressora8">AttachedTransformation</a>()-><a class="code" href="class_buffered_transformation.html#_zlib_decompressorz1_0">Put</a>((byte)m_buffer);00072 m_buffer = 0;00073 m_bitsBuffered = 0;00074 }00075 }00076 }00077 00078 <span class="keywordtype">void</span> LowFirstBitWriter::ClearBitBuffer()00079 {00080 m_buffer = 0;00081 m_bytesBuffered = 0;00082 m_bitsBuffered = 0;00083 }00084 00085 HuffmanEncoder::HuffmanEncoder(<span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> *codeBits, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> nCodes)00086 {00087 Initialize(codeBits, nCodes);00088 }00089 00090 <span class="keyword">struct </span>HuffmanNode00091 {00092 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> symbol;00093 <span class="keyword">union </span>{<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> parent, depth, freq;};00094 };00095 00096 <span class="keyword">struct </span>FreqLessThan00097 {00098 <span class="keyword">inline</span> <span class="keywordtype">bool</span> operator()(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> lhs, <span class="keyword">const</span> HuffmanNode &rhs) {<span class="keywordflow">return</span> lhs < rhs.freq;}00099 <span class="keyword">inline</span> <span class="keywordtype">bool</span> operator()(<span class="keyword">const</span> HuffmanNode &lhs, <span class="keyword">const</span> HuffmanNode &rhs)<span class="keyword"> const </span>{<span class="keywordflow">return</span> lhs.freq < rhs.freq;}00100 };00101 00102 <span class="keywordtype">void</span> HuffmanEncoder::GenerateCodeLengths(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> *codeBits, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> maxCodeBits, <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> *codeCounts, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> nCodes)00103 {00104 assert(nCodes > 0);00105 assert(nCodes <= (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>)(1 << maxCodeBits));00106 00107 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i;00108 SecBlockWithHint<HuffmanNode, 2*286> tree(nCodes);00109 <span class="keywordflow">for</span> (i=0; i<nCodes; i++)00110 {00111 tree[i].symbol = i;00112 tree[i].freq = codeCounts[i];00113 }00114 sort(tree.<a class="code" href="class_sec_block.html#_sec_block_with_hinta7">begin</a>(), tree.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">end</a>(), FreqLessThan());00115 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> treeBegin = upper_bound(tree.<a class="code" href="class_sec_block.html#_sec_block_with_hinta7">begin</a>(), tree.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">end</a>(), 0, FreqLessThan()) - tree.<a class="code" href="class_sec_block.html#_sec_block_with_hinta7">begin</a>();00116 <span class="keywordflow">if</span> (treeBegin == nCodes)00117 { <span class="comment">// special case for no codes</span>00118 fill(codeBits, codeBits+nCodes, 0);00119 <span class="keywordflow">return</span>;00120 }00121 tree.<a class="code" href="class_sec_block.html#_sec_block_with_hinta23">resize</a>(nCodes + nCodes - treeBegin - 1);00122 00123 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> leastLeaf = treeBegin, leastInterior = nCodes;00124 <span class="keywordflow">for</span> (i=nCodes; i<tree.<a class="code" href="class_sec_block.html#_sec_block_with_hinta13">size</a>(); i++)00125 {00126 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> least;00127 least = (leastLeaf == nCodes || (leastInterior < i && tree[leastInterior].freq < tree[leastLeaf].freq)) ? leastInterior++ : leastLeaf++;00128 tree[i].freq = tree[least].freq;00129 tree[least].parent = i;00130 least = (leastLeaf == nCodes || (leastInterior < i && tree[leastInterior].freq < tree[leastLeaf].freq)) ? leastInterior++ : leastLeaf++;00131 tree[i].freq += tree[least].freq;00132 tree[least].parent = i;00133 }00134 00135 tree[tree.<a class="code" href="class_sec_block.html#_sec_block_with_hinta13">size</a>()-1].depth = 0;00136 <span class="keywordflow">if</span> (tree.<a class="code" href="class_sec_block.html#_sec_block_with_hinta13">size</a>() >= 2)00137 <span class="keywordflow">for</span> (i=tree.<a class="code" href="class_sec_block.html#_sec_block_with_hinta13">size</a>()-2; i>=nCodes; i--)00138 tree[i].depth = tree[tree[i].parent].depth + 1;00139 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> sum = 0;00140 SecBlockWithHint<unsigned int, 15+1> blCount(maxCodeBits+1);00141 fill(blCount.<a class="code" href="class_sec_block.html#_sec_block_with_hinta7">begin</a>(), blCount.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">end</a>(), 0);00142 <span class="keywordflow">for</span> (i=treeBegin; i<nCodes; i++)00143 {00144 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> depth = STDMIN(maxCodeBits, tree[tree[i].parent].depth + 1);00145 blCount[depth]++;00146 sum += 1 << (maxCodeBits - depth);00147 }00148 00149 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> overflow = sum > (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>)(1 << maxCodeBits) ? sum - (1 << maxCodeBits) : 0;00150 00151 <span class="keywordflow">while</span> (overflow--)00152 {00153 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bits = maxCodeBits-1;00154 <span class="keywordflow">while</span> (blCount[bits] == 0)00155 bits--;00156 blCount[bits]--;00157 blCount[bits+1] += 2;00158 assert(blCount[maxCodeBits] > 0);00159 blCount[maxCodeBits]--;00160 }00161 00162 <span class="keywordflow">for</span> (i=0; i<treeBegin; i++)00163 codeBits[tree[i].symbol] = 0;00164 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bits = maxCodeBits;00165 <span class="keywordflow">for</span> (i=treeBegin; i<nCodes; i++)00166 {00167 <span class="keywordflow">while</span> (blCount[bits] == 0)00168 bits--;00169 codeBits[tree[i].symbol] = bits;00170 blCount[bits]--;00171 }00172 assert(blCount[bits] == 0);00173 }00174 00175 <span class="keywordtype">void</span> HuffmanEncoder::Initialize(<span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> *codeBits, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> nCodes)00176 {00177 assert(nCodes > 0);00178 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> maxCodeBits = *max_element(codeBits, codeBits+nCodes);00179 <span class="keywordflow">if</span> (maxCodeBits == 0)00180 <span class="keywordflow">return</span>; <span class="comment">// assume this object won't be used</span>00181 ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -