📄 zinflate_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++: zinflate.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>zinflate.cpp</h1><div class="fragment"><pre>00001 <span class="comment">// zinflate.cpp - written and placed in the public domain by Wei Dai</span>00002 00003 <span class="comment">// This is a complete reimplementation of the DEFLATE decompression algorithm.</span>00004 <span class="comment">// It should not be affected by any security vulnerabilities in the zlib </span>00005 <span class="comment">// compression library. In particular it is not affected by the double free bug</span>00006 <span class="comment">// (http://www.kb.cert.org/vuls/id/368819).</span>00007 00008 <span class="preprocessor">#include "pch.h"</span>00009 <span class="preprocessor">#include "zinflate.h"</span>00010 00011 NAMESPACE_BEGIN(CryptoPP)00012 00013 <span class="keyword">struct </span>CodeLessThan00014 {00015 <span class="keyword">inline</span> <span class="keywordtype">bool</span> operator()(<span class="keyword">const</span> CryptoPP::HuffmanDecoder::code_t lhs, <span class="keyword">const</span> CryptoPP::HuffmanDecoder::CodeInfo &rhs)00016 {<span class="keywordflow">return</span> lhs < rhs.code;}00017 };00018 00019 <span class="keyword">inline</span> <span class="keywordtype">bool</span> LowFirstBitReader::FillBuffer(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> length)00020 {00021 <span class="keywordflow">while</span> (m_bitsBuffered < length)00022 {00023 byte b;00024 <span class="keywordflow">if</span> (!m_store.<a class="code" href="class_buffered_transformation.html#_zlib_decompressorz7_2">Get</a>(b))00025 <span class="keywordflow">return</span> <span class="keyword">false</span>;00026 m_buffer |= (<span class="keywordtype">unsigned</span> <span class="keywordtype">long</span>)b << m_bitsBuffered;00027 m_bitsBuffered += 8;00028 }00029 assert(m_bitsBuffered <= <span class="keyword">sizeof</span>(<span class="keywordtype">unsigned</span> <span class="keywordtype">long</span>)*8);00030 <span class="keywordflow">return</span> <span class="keyword">true</span>;00031 }00032 00033 <span class="keyword">inline</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> LowFirstBitReader::PeekBits(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> length)00034 {00035 <span class="keywordtype">bool</span> result = FillBuffer(length);00036 assert(result);00037 <span class="keywordflow">return</span> m_buffer & (((<span class="keywordtype">unsigned</span> <span class="keywordtype">long</span>)1 << length) - 1);00038 }00039 00040 <span class="keyword">inline</span> <span class="keywordtype">void</span> LowFirstBitReader::SkipBits(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> length)00041 {00042 assert(m_bitsBuffered >= length);00043 m_buffer >>= length;00044 m_bitsBuffered -= length;00045 }00046 00047 <span class="keyword">inline</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> LowFirstBitReader::GetBits(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> length)00048 {00049 <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> result = PeekBits(length);00050 SkipBits(length);00051 <span class="keywordflow">return</span> result;00052 }00053 00054 <span class="keyword">inline</span> HuffmanDecoder::code_t HuffmanDecoder::NormalizeCode(HuffmanDecoder::code_t code, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> codeBits)00055 {00056 <span class="keywordflow">return</span> code << (MAX_CODE_BITS - codeBits);00057 }00058 00059 <span class="keywordtype">void</span> HuffmanDecoder::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)00060 {00061 <span class="comment">// the Huffman codes are represented in 3 ways in this code:</span>00062 <span class="comment">//</span>00063 <span class="comment">// 1. most significant code bit (i.e. top of code tree) in the least significant bit position</span>00064 <span class="comment">// 2. most significant code bit (i.e. top of code tree) in the most significant bit position</span>00065 <span class="comment">// 3. most significant code bit (i.e. top of code tree) in n-th least significant bit position,</span>00066 <span class="comment">// where n is the maximum code length for this code tree</span>00067 <span class="comment">//</span>00068 <span class="comment">// (1) is the way the codes come in from the deflate stream</span>00069 <span class="comment">// (2) is used to sort codes so they can be binary searched</span>00070 <span class="comment">// (3) is used in this function to compute codes from code lengths</span>00071 <span class="comment">//</span>00072 <span class="comment">// a code in representation (2) is called "normalized" here</span>00073 <span class="comment">// The BitReverse() function is used to convert between (1) and (2)</span>00074 <span class="comment">// The NormalizeCode() function is used to convert from (3) to (2)</span>00075 00076 <span class="keywordflow">if</span> (nCodes == 0)00077 <span class="keywordflow">throw</span> Err(<span class="stringliteral">"null code"</span>);00078 00079 m_maxCodeBits = *std::max_element(codeBits, codeBits+nCodes);00080 00081 <span class="keywordflow">if</span> (m_maxCodeBits > MAX_CODE_BITS)00082 <span class="keywordflow">throw</span> Err(<span class="stringliteral">"code length exceeds maximum"</span>);00083 00084 <span class="keywordflow">if</span> (m_maxCodeBits == 0)00085 <span class="keywordflow">throw</span> Err(<span class="stringliteral">"null code"</span>);00086 00087 <span class="comment">// count number of codes of each length</span>00088 SecBlockWithHint<unsigned int, 15+1> blCount(m_maxCodeBits+1);00089 std::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);00090 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i;00091 <span class="keywordflow">for</span> (i=0; i<nCodes; i++)00092 blCount[codeBits[i]]++;00093 00094 <span class="comment">// compute the starting code of each length</span>00095 code_t code = 0;00096 SecBlockWithHint<code_t, 15+1> nextCode(m_maxCodeBits+1);00097 nextCode[1] = 0;00098 <span class="keywordflow">for</span> (i=2; i<=m_maxCodeBits; i++)00099 {00100 <span class="comment">// compute this while checking for overflow: code = (code + blCount[i-1]) << 1</span>00101 <span class="keywordflow">if</span> (code > code + blCount[i-1])00102 <span class="keywordflow">throw</span> Err(<span class="stringliteral">"codes oversubscribed"</span>);00103 code += blCount[i-1];00104 <span class="keywordflow">if</span> (code > (code << 1))00105 <span class="keywordflow">throw</span> Err(<span class="stringliteral">"codes oversubscribed"</span>);00106 code <<= 1;00107 nextCode[i] = code;00108 }00109 00110 <span class="keywordflow">if</span> (code > (1 << m_maxCodeBits) - blCount[m_maxCodeBits])00111 <span class="keywordflow">throw</span> Err(<span class="stringliteral">"codes oversubscribed"</span>);00112 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (m_maxCodeBits != 1 && code < (1 << m_maxCodeBits) - blCount[m_maxCodeBits])00113 <span class="keywordflow">throw</span> Err(<span class="stringliteral">"codes incomplete"</span>);00114 00115 <span class="comment">// compute a vector of <code, length, value> triples sorted by code</span>00116 m_codeToValue.resize(nCodes - blCount[0]);00117 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> j=0;00118 <span class="keywordflow">for</span> (i=0; i<nCodes; i++) 00119 {00120 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> len = codeBits[i];00121 <span class="keywordflow">if</span> (len != 0)00122 {00123 code = NormalizeCode(nextCode[len]++, len);00124 m_codeToValue[j].code = code;00125 m_codeToValue[j].len = len;00126 m_codeToValue[j].value = i;00127 j++;00128 }00129 }00130 std::sort(m_codeToValue.begin(), m_codeToValue.end());00131 00132 <span class="comment">// initialize the decoding cache</span>00133 m_cacheBits = STDMIN(9U, m_maxCodeBits);00134 m_cacheMask = (1 << m_cacheBits) - 1;00135 m_normalizedCacheMask = NormalizeCode(m_cacheMask, m_cacheBits);00136 assert(m_normalizedCacheMask == BitReverse(m_cacheMask));00137 00138 <span class="keywordflow">if</span> (m_cache.size() != 1 << m_cacheBits)00139 m_cache.resize(1 << m_cacheBits);00140 00141 <span class="keywordflow">for</span> (i=0; i<m_cache.size(); i++)00142 m_cache[i].type = 0;⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -