zdeflate_8cpp-source.html

著名的密码库Crypto++的文档 C++语言的杰作。程序员必备。

<a name="l00075"></a>00075         }
<a name="l00076"></a>00076 }
<a name="l00077"></a>00077 
<a name="l00078"></a><a class="code" href="class_low_first_bit_writer.html#ccc5bffe4a9459f6ce0b5b678e4a7e04">00078</a> <span class="keywordtype">void</span> <a class="code" href="class_low_first_bit_writer.html#ccc5bffe4a9459f6ce0b5b678e4a7e04">LowFirstBitWriter::ClearBitBuffer</a>()
<a name="l00079"></a>00079 {
<a name="l00080"></a>00080         <a class="code" href="class_low_first_bit_writer.html#0df2a5478042587afd61c8f2c0c04b59">m_buffer</a> = 0;
<a name="l00081"></a>00081         <a class="code" href="class_low_first_bit_writer.html#75a39e9548b284609320ab615289040d">m_bytesBuffered</a> = 0;
<a name="l00082"></a>00082         <a class="code" href="class_low_first_bit_writer.html#20da2a4de9640ac6f3b785a7fff56c60">m_bitsBuffered</a> = 0;
<a name="l00083"></a>00083 }
<a name="l00084"></a>00084 
<a name="l00085"></a><a class="code" href="class_huffman_encoder.html#f646f8a57a3fae0ff8c2e8ff27d8db87">00085</a> <a class="code" href="class_huffman_encoder.html#f2b441522d45cf1e1935673e27d09b30">HuffmanEncoder::HuffmanEncoder</a>(<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)
<a name="l00086"></a>00086 {
<a name="l00087"></a>00087         <a class="code" href="class_huffman_encoder.html#58cdf24aadeaea994f01164e7dea0a3d">Initialize</a>(codeBits, nCodes);
<a name="l00088"></a>00088 }
<a name="l00089"></a>00089 
<a name="l00090"></a><a class="code" href="struct_huffman_node.html">00090</a> <span class="keyword">struct </span><a class="code" href="struct_huffman_node.html">HuffmanNode</a>
<a name="l00091"></a>00091 {
<a name="l00092"></a><a class="code" href="struct_huffman_node.html#664d7c0ceca2a9280e7be517bfe31b1f">00092</a>         <span class="keywordtype">size_t</span> symbol;
<a name="l00093"></a><a class="code" href="struct_huffman_node.html#33a30bffc12c7e308cc3fffccd521b30">00093</a>         <span class="keyword">union </span>{<span class="keywordtype">size_t</span> parent; <span class="keywordtype">unsigned</span> depth, freq;};
<a name="l00094"></a>00094 };
<a name="l00095"></a>00095 
<a name="l00096"></a><a class="code" href="struct_freq_less_than.html">00096</a> <span class="keyword">struct </span><a class="code" href="struct_freq_less_than.html">FreqLessThan</a>
<a name="l00097"></a>00097 {
<a name="l00098"></a><a class="code" href="struct_freq_less_than.html#a29c084c1e773096aec448bcc385d8dc">00098</a>         <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> <a class="code" href="struct_huffman_node.html">HuffmanNode</a> &amp;rhs) {<span class="keywordflow">return</span> lhs &lt; rhs.<a class="code" href="struct_huffman_node.html#14bca3e99c730c465a7f07b68261e8a1">freq</a>;}
<a name="l00099"></a><a class="code" href="struct_freq_less_than.html#db57e7c40d38998f18310b311f9b5daf">00099</a>         <span class="keyword">inline</span> <span class="keywordtype">bool</span> operator()(<span class="keyword">const</span> <a class="code" href="struct_huffman_node.html">HuffmanNode</a> &amp;lhs, <span class="keyword">const</span> <a class="code" href="struct_huffman_node.html">HuffmanNode</a> &amp;rhs)<span class="keyword"> const </span>{<span class="keywordflow">return</span> lhs.<a class="code" href="struct_huffman_node.html#14bca3e99c730c465a7f07b68261e8a1">freq</a> &lt; rhs.<a class="code" href="struct_huffman_node.html#14bca3e99c730c465a7f07b68261e8a1">freq</a>;}
<a name="l00100"></a>00100         <span class="comment">// needed for MSVC .NET 2005</span>
<a name="l00101"></a><a class="code" href="struct_freq_less_than.html#fcdcacdbdad8410871dbe4e1356fcb15">00101</a>         <span class="keyword">inline</span> <span class="keywordtype">bool</span> operator()(<span class="keyword">const</span> <a class="code" href="struct_huffman_node.html">HuffmanNode</a> &amp;lhs, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> rhs) {<span class="keywordflow">return</span> lhs.<a class="code" href="struct_huffman_node.html#14bca3e99c730c465a7f07b68261e8a1">freq</a> &lt; rhs;}
<a name="l00102"></a>00102 };
<a name="l00103"></a>00103 
<a name="l00104"></a><a class="code" href="class_huffman_encoder.html#3067c6ca4d90a282925ce2f2e15b014d">00104</a> <span class="keywordtype">void</span> <a class="code" href="class_huffman_encoder.html#3067c6ca4d90a282925ce2f2e15b014d">HuffmanEncoder::GenerateCodeLengths</a>(<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">size_t</span> nCodes)
<a name="l00105"></a>00105 {
<a name="l00106"></a>00106         assert(nCodes &gt; 0);
<a name="l00107"></a>00107         assert(nCodes &lt;= ((<span class="keywordtype">size_t</span>)1 &lt;&lt; maxCodeBits));
<a name="l00108"></a>00108 
<a name="l00109"></a>00109         <span class="keywordtype">size_t</span> i;
<a name="l00110"></a>00110         <a class="code" href="class_sec_block_with_hint.html" title="a SecBlock that preallocates size S statically, and uses the heap when this size...">SecBlockWithHint&lt;HuffmanNode, 2*286&gt;</a> tree(nCodes);
<a name="l00111"></a>00111         <span class="keywordflow">for</span> (i=0; i&lt;nCodes; i++)
<a name="l00112"></a>00112         {
<a name="l00113"></a>00113                 tree[i].symbol = i;
<a name="l00114"></a>00114                 tree[i].freq = codeCounts[i];
<a name="l00115"></a>00115         }
<a name="l00116"></a>00116         sort(tree.<a class="code" href="class_sec_block.html#11a05906688172579cd3520816799446">begin</a>(), tree.<a class="code" href="class_sec_block.html#26d88ba73b5da0f5dd4ab87ce6345d8f">end</a>(), <a class="code" href="struct_freq_less_than.html">FreqLessThan</a>());
<a name="l00117"></a>00117         <span class="keywordtype">size_t</span> treeBegin = upper_bound(tree.<a class="code" href="class_sec_block.html#11a05906688172579cd3520816799446">begin</a>(), tree.<a class="code" href="class_sec_block.html#26d88ba73b5da0f5dd4ab87ce6345d8f">end</a>(), 0, <a class="code" href="struct_freq_less_than.html">FreqLessThan</a>()) - tree.<a class="code" href="class_sec_block.html#11a05906688172579cd3520816799446">begin</a>();
<a name="l00118"></a>00118         <span class="keywordflow">if</span> (treeBegin == nCodes)
<a name="l00119"></a>00119         {       <span class="comment">// special case for no codes</span>
<a name="l00120"></a>00120                 fill(codeBits, codeBits+nCodes, 0);
<a name="l00121"></a>00121                 <span class="keywordflow">return</span>;
<a name="l00122"></a>00122         }
<a name="l00123"></a>00123         tree.<a class="code" href="class_sec_block.html#f9e98d3f4a7af1156fcf3e6e68f4ae5a" title="change size and preserve contents">resize</a>(nCodes + nCodes - treeBegin - 1);
<a name="l00124"></a>00124 
<a name="l00125"></a>00125         <span class="keywordtype">size_t</span> leastLeaf = treeBegin, leastInterior = nCodes;
<a name="l00126"></a>00126         <span class="keywordflow">for</span> (i=nCodes; i&lt;tree.<a class="code" href="class_sec_block.html#f5999bffe3193e62719cc0792b0282a7">size</a>(); i++)
<a name="l00127"></a>00127         {
<a name="l00128"></a>00128                 <span class="keywordtype">size_t</span> least;
<a name="l00129"></a>00129                 least = (leastLeaf == nCodes || (leastInterior &lt; i &amp;&amp; tree[leastInterior].freq &lt; tree[leastLeaf].freq)) ? leastInterior++ : leastLeaf++;
<a name="l00130"></a>00130                 tree[i].freq = tree[least].freq;
<a name="l00131"></a>00131                 tree[least].parent = i;
<a name="l00132"></a>00132                 least = (leastLeaf == nCodes || (leastInterior &lt; i &amp;&amp; tree[leastInterior].freq &lt; tree[leastLeaf].freq)) ? leastInterior++ : leastLeaf++;
<a name="l00133"></a>00133                 tree[i].freq += tree[least].freq;
<a name="l00134"></a>00134                 tree[least].parent = i;
<a name="l00135"></a>00135         }
<a name="l00136"></a>00136 
<a name="l00137"></a>00137         tree[tree.<a class="code" href="class_sec_block.html#f5999bffe3193e62719cc0792b0282a7">size</a>()-1].depth = 0;
<a name="l00138"></a>00138         <span class="keywordflow">if</span> (tree.<a class="code" href="class_sec_block.html#f5999bffe3193e62719cc0792b0282a7">size</a>() &gt;= 2)
<a name="l00139"></a>00139                 <span class="keywordflow">for</span> (i=tree.<a class="code" href="class_sec_block.html#f5999bffe3193e62719cc0792b0282a7">size</a>()-2; i&gt;=nCodes; i--)
<a name="l00140"></a>00140                         tree[i].depth = tree[tree[i].parent].depth + 1;
<a name="l00141"></a>00141         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> sum = 0;
<a name="l00142"></a>00142         <a class="code" href="class_sec_block_with_hint.html" title="a SecBlock that preallocates size S statically, and uses the heap when this size...">SecBlockWithHint&lt;unsigned int, 15+1&gt;</a> blCount(maxCodeBits+1);
<a name="l00143"></a>00143         fill(blCount.<a class="code" href="class_sec_block.html#11a05906688172579cd3520816799446">begin</a>(), blCount.<a class="code" href="class_sec_block.html#26d88ba73b5da0f5dd4ab87ce6345d8f">end</a>(), 0);
<a name="l00144"></a>00144         <span class="keywordflow">for</span> (i=treeBegin; i&lt;nCodes; i++)
<a name="l00145"></a>00145         {
<a name="l00146"></a>00146                 <span class="keywordtype">size_t</span> depth = STDMIN(maxCodeBits, tree[tree[i].parent].depth + 1);
<a name="l00147"></a>00147                 blCount[depth]++;
<a name="l00148"></a>00148                 sum += 1 &lt;&lt; (maxCodeBits - depth);
<a name="l00149"></a>00149         }
<a name="l00150"></a>00150 
<a name="l00151"></a>00151         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> overflow = sum &gt; (<span class="keywordtype">unsigned</span> int)(1 &lt;&lt; maxCodeBits) ? sum - (1 &lt;&lt; maxCodeBits) : 0;
<a name="l00152"></a>00152 
<a name="l00153"></a>00153         <span class="keywordflow">while</span> (overflow--)
<a name="l00154"></a>00154         {
<a name="l00155"></a>00155                 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bits = maxCodeBits-1;
<a name="l00156"></a>00156                 <span class="keywordflow">while</span> (blCount[bits] == 0)
<a name="l00157"></a>00157                         bits--;
<a name="l00158"></a>00158                 blCount[bits]--;
<a name="l00159"></a>00159                 blCount[bits+1] += 2;
<a name="l00160"></a>00160                 assert(blCount[maxCodeBits] &gt; 0);
<a name="l00161"></a>00161                 blCount[maxCodeBits]--;
<a name="l00162"></a>00162         }
<a name="l00163"></a>00163 
<a name="l00164"></a>00164         <span class="keywordflow">for</span> (i=0; i&lt;treeBegin; i++)
<a name="l00165"></a>00165                 codeBits[tree[i].symbol] = 0;
<a name="l00166"></a>00166         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bits = maxCodeBits;
<a name="l00167"></a>00167         <span class="keywordflow">for</span> (i=treeBegin; i&lt;nCodes; i++)
<a name="l00168"></a>00168         {
<a name="l00169"></a>00169                 <span class="keywordflow">while</span> (blCount[bits] == 0)