zdeflate_8cpp-source.html

Crypto++是一个非常强大的密码学库,主要是功能全

00182         SecBlockWithHint<unsigned int, 15+1> blCount(maxCodeBits+1);
00183         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);
00184         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i;
00185         <span class="keywordflow">for</span> (i=0; i&lt;nCodes; i++)
00186                 blCount[codeBits[i]]++;
00187 
00188         code_t code = 0;
00189         SecBlockWithHint&lt;code_t, 15+1&gt; nextCode(maxCodeBits+1);
00190         nextCode[1] = 0;
00191         <span class="keywordflow">for</span> (i=2; i&lt;=maxCodeBits; i++)
00192         {
00193                 code = (code + blCount[i-1]) &lt;&lt; 1;
00194                 nextCode[i] = code;
00195         }
00196         assert(maxCodeBits == 1 || code == (1 &lt;&lt; maxCodeBits) - blCount[maxCodeBits]);
00197 
00198         m_valueToCode.<a class="code" href="class_sec_block.html#_sec_block_with_hinta23">resize</a>(nCodes);
00199         <span class="keywordflow">for</span> (i=0; i&lt;nCodes; i++)
00200         {
00201                 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> len = m_valueToCode[i].len = codeBits[i];
00202                 <span class="keywordflow">if</span> (len != 0)
00203                         m_valueToCode[i].code = BitReverse(nextCode[len]++) &gt;&gt; (8*<span class="keyword">sizeof</span>(code_t)-len);
00204         }
00205 }
00206 
00207 <span class="keyword">inline</span> <span class="keywordtype">void</span> HuffmanEncoder::Encode(<a class="code" href="class_low_first_bit_writer.html">LowFirstBitWriter</a> &amp;writer, value_t value)<span class="keyword"> const</span>
00208 <span class="keyword"></span>{
00209         assert(m_valueToCode[value].len &gt; 0);
00210         writer.<a class="code" href="class_low_first_bit_writer.html#_zlib_compressora9">PutBits</a>(m_valueToCode[value].code, m_valueToCode[value].len);
00211 }
00212 
00213 <a class="code" href="class_deflator.html#_deflatora1">Deflator::Deflator</a>(<a class="code" href="class_buffered_transformation.html">BufferedTransformation</a> *attachment, <span class="keywordtype">int</span> deflateLevel, <span class="keywordtype">int</span> log2WindowSize)
00214         : <a class="code" href="class_low_first_bit_writer.html">LowFirstBitWriter</a>(attachment)
00215 {
00216         InitializeStaticEncoders();
00217         IsolatedInitialize(MakeParameters(<span class="stringliteral">"DeflateLevel"</span>, deflateLevel)(<span class="stringliteral">"Log2WindowSize"</span>, log2WindowSize));
00218 }
00219 
<a name="l00220"></a><a class="code" href="class_deflator.html#_deflatora1">00220</a> <a class="code" href="class_deflator.html#_deflatora1">Deflator::Deflator</a>(<span class="keyword">const</span> <a class="code" href="class_name_value_pairs.html">NameValuePairs</a> &amp;parameters, <a class="code" href="class_buffered_transformation.html">BufferedTransformation</a> *attachment)
00221         : <a class="code" href="class_low_first_bit_writer.html">LowFirstBitWriter</a>(attachment)
00222 {
00223         InitializeStaticEncoders();
00224         IsolatedInitialize(parameters);
00225 }
00226 
00227 <span class="keywordtype">void</span> Deflator::InitializeStaticEncoders()
00228 {
00229         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> codeLengths[288];
00230         fill(codeLengths + 0, codeLengths + 144, 8);
00231         fill(codeLengths + 144, codeLengths + 256, 9);
00232         fill(codeLengths + 256, codeLengths + 280, 7);
00233         fill(codeLengths + 280, codeLengths + 288, 8);
00234         m_staticLiteralEncoder.<a class="code" href="class_huffman_encoder.html#_huffman_encodera2">Initialize</a>(codeLengths, 288);
00235         fill(codeLengths + 0, codeLengths + 32, 5);
00236         m_staticDistanceEncoder.<a class="code" href="class_huffman_encoder.html#_huffman_encodera2">Initialize</a>(codeLengths, 32);
00237 }
00238 
00239 <span class="keywordtype">void</span> Deflator::IsolatedInitialize(<span class="keyword">const</span> <a class="code" href="class_name_value_pairs.html">NameValuePairs</a> &amp;parameters)
00240 {
00241         <span class="keywordtype">int</span> log2WindowSize = parameters.<a class="code" href="class_name_value_pairs.html#_x_t_r___d_ha43">GetIntValueWithDefault</a>(<span class="stringliteral">"Log2WindowSize"</span>, DEFAULT_LOG2_WINDOW_SIZE);
00242 
00243         <span class="keywordflow">if</span> (!(MIN_LOG2_WINDOW_SIZE &lt;= log2WindowSize &amp;&amp; log2WindowSize &lt;= MAX_LOG2_WINDOW_SIZE))
00244                 <span class="keywordflow">throw</span> <a class="code" href="class_invalid_argument.html">InvalidArgument</a>(<span class="stringliteral">"Deflator: "</span> + IntToString(log2WindowSize) + <span class="stringliteral">" is an invalid window size"</span>);
00245 
00246         m_log2WindowSize = log2WindowSize;
00247         DSIZE = 1 &lt;&lt; m_log2WindowSize;
00248         DMASK = DSIZE - 1;
00249         HSIZE = 1 &lt;&lt; m_log2WindowSize;
00250         HMASK = HSIZE - 1;
00251         m_byteBuffer.<a class="code" href="class_sec_block.html#_sec_block_with_hinta19">New</a>(2*DSIZE);
00252         m_head.<a class="code" href="class_sec_block.html#_sec_block_with_hinta19">New</a>(HSIZE);
00253         m_prev.<a class="code" href="class_sec_block.html#_sec_block_with_hinta19">New</a>(DSIZE);
00254         m_matchBuffer.<a class="code" href="class_sec_block.html#_sec_block_with_hinta19">New</a>(DSIZE/2);
00255 
00256         <a class="code" href="class_deflator.html#_zlib_compressora3">SetDeflateLevel</a>(parameters.<a class="code" href="class_name_value_pairs.html#_x_t_r___d_ha43">GetIntValueWithDefault</a>(<span class="stringliteral">"DeflateLevel"</span>, DEFAULT_DEFLATE_LEVEL));
00257         Reset(<span class="keyword">true</span>);
00258 }
00259 
00260 <span class="keywordtype">void</span> Deflator::Reset(<span class="keywordtype">bool</span> forceReset)
00261 {
00262         <span class="keywordflow">if</span> (forceReset)
00263                 ClearBitBuffer();
00264         <span class="keywordflow">else</span>
00265                 assert(m_bitsBuffered == 0);
00266 
00267         m_headerWritten = <span class="keyword">false</span>;
00268         m_matchAvailable = <span class="keyword">false</span>;
00269         m_dictionaryEnd = 0;
00270         m_stringStart = 0;
00271         m_lookahead = 0;
00272         m_minLookahead = MAX_MATCH;
00273         m_previousMatch = 0;
00274         m_previousLength = 0;
00275         m_matchBufferEnd = 0;
00276         m_blockStart = 0;
00277         m_blockLength = 0;
00278 
00279         <span class="comment">// m_prev will be initialized automaticly in InsertString</span>
00280         fill(m_head.<a class="code" href="class_sec_block.html#_sec_block_with_hinta7">begin</a>(), m_head.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">end</a>(), 0);
00281 
00282         fill(m_literalCounts.<a class="code" href="class_sec_block.html#_sec_block_with_hinta7">begin</a>(), m_literalCounts.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">end</a>(), 0);
00283         fill(m_distanceCounts.<a class="code" href="class_sec_block.html#_sec_block_with_hinta7">begin</a>(), m_distanceCounts.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">end</a>(), 0);
00284 }
00285 
<a name="l00286"></a><a class="code" href="class_deflator.html#_zlib_compressora3">00286</a> <span class="keywordtype">void</span> <a class="code" href="class_deflator.html#_zlib_compressora3">Deflator::SetDeflateLevel</a>(<span class="keywordtype">int</span> deflateLevel)
00287 {
00288         <span class="keywordflow">if</span> (!(MIN_DEFLATE_LEVEL &lt;= deflateLevel &amp;&amp; deflateLevel &lt;= MAX_DEFLATE_LEVEL))
00289                 <span class="keywordflow">throw</span> <a class="code" href="class_invalid_argument.html">InvalidArgument</a>(<span class="stringliteral">"Deflator: "</span> + IntToString(deflateLevel) + <span class="stringliteral">" is an invalid deflate level"</span>);
00290 
00291         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> configurationTable[10][4] = {
00292                 <span class="comment">/*      good lazy nice chain */</span>
00293                 <span class="comment">/* 0 */</span> {0,    0,  0,    0},  <span class="comment">/* store only */</span>
00294                 <span class="comment">/* 1 */</span> {4,    3,  8,    4},  <span class="comment">/* maximum speed, no lazy matches */</span>
00295                 <span class="comment">/* 2 */</span> {4,    3, 16,    8},
00296                 <span class="comment">/* 3 */</span> {4,    3, 32,   32},
00297                 <span class="comment">/* 4 */</span> {4,    4, 16,   16},  <span class="comment">/* lazy matches */</span>
00298                 <span class="comment">/* 5 */</span> {8,   16, 32,   32},
00299                 <span class="comment">/* 6 */</span> {8,   16, 128, 128},
00300                 <span class="comment">/* 7 */</span> {8,   32, 128, 256},
00301                 <span class="comment">/* 8 */</span> {32, 128, 258, 1024},
00302                 <span class="comment">/* 9 */</span> {32, 258, 258, 4096}}; <span class="comment">/* maximum compression */</span>
00303 
00304         GOOD_MATCH = configurationTable[deflateLevel][0];
00305         MAX_LAZYLENGTH = configurationTable[deflateLevel][1];
00306         MAX_CHAIN_LENGTH = configurationTable[deflateLevel][3];
00307 
00308         m_deflateLevel = deflateLevel;
00309 }
00310 
00311 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> Deflator::FillWindow(<span class="keyword">const</span> byte *str, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> length)
00312 {
00313         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> accepted = STDMIN(length, 2*DSIZE-(m_stringStart+m_lookahead));
00314 
00315         <span class="keywordflow">if</span> (m_stringStart &gt;= 2*DSIZE - MAX_MATCH)
00316         {
00317                 <span class="keywordflow">if</span> (m_blockStart &lt; DSIZE)
00318                         EndBlock(<span class="keyword">false</span>);
00319 
00320                 memcpy(m_byteBuffer, m_byteBuffer + DSIZE, DSIZE);
00321 
00322                 m_dictionaryEnd = m_dictionaryEnd &lt; DSIZE ? 0 : m_dictionaryEnd-DSIZE;
00323                 assert(m_stringStart &gt;= DSIZE);
00324                 m_stringStart -= DSIZE;
00325                 assert(m_previousMatch &gt;= DSIZE || m_previousLength &lt; MIN_MATCH);
00326                 m_previousMatch -= DSIZE;
00327                 assert(m_blockStart &gt;= DSIZE);
00328                 m_blockStart -= DSIZE;
00329 
00330                 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i;
00331 
00332                 <span class="keywordflow">for</span> (i=0; i&lt;HSIZE; i++)
00333                         m_head[i] = SaturatingSubtract(m_head[i], DSIZE);
00334 
00335                 <span class="keywordflow">for</span> (i=0; i&lt;DSIZE; i++)
00336                         m_prev[i] = SaturatingSubtract(m_prev[i], DSIZE);
00337 
00338                 accepted = STDMIN(accepted + DSIZE, length);
00339         }
00340         assert(accepted &gt; 0);
00341 
00342         memcpy(m_byteBuffer + m_stringStart + m_lookahead, str, accepted);
00343         m_lookahead += accepted;
00344         <span class="keywordflow">return</span> accepted;
00345 }
00346 
00347 <span class="keyword">inline</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> Deflator::ComputeHash(<span class="keyword">const</span> byte *str)<span class="keyword"> const</span>
00348 <span class="keyword"></span>{
00349         assert(str+3 &lt;= m_byteBuffer + m_stringStart + m_lookahead);
00350         <span class="keywordflow">return</span> ((str[0] &lt;&lt; 10) ^ (str[1] &lt;&lt; 5) ^ str[2]) &amp; HMASK;
00351 }
00352 
00353 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> Deflator::LongestMatch(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> &amp;bestMatch)<span class="keyword"> const</span>
00354 <span class="keyword"></span>{
00355         assert(m_previousLength &lt; MAX_MATCH);
00356 
00357         bestMatch = 0;
00358         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bestLength = STDMAX(m_previousLength, (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>)MIN_MATCH-1);
00359         <span class="keywordflow">if</span> (m_lookahead &lt;= bestLength)
00360                 <span class="keywordflow">return</span> 0;
00361 
00362         <span class="keyword">const</span> byte *scan = m_byteBuffer + m_stringStart, *scanEnd = scan + STDMIN((<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>)MAX_MATCH, m_lookahead);
00363         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> limit = m_stringStart &gt; (DSIZE-MAX_MATCH) ? m_stringStart - (DSIZE-MAX_MATCH) : 0;
00364         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> current = m_head[ComputeHash(scan)];
00365 
00366         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> chainLength = MAX_CHAIN_LENGTH;
00367         <span class="keywordflow">if</span> (m_previousLength &gt;= GOOD_MATCH)
00368                 chainLength &gt;&gt;= 2;
00369