1// zdeflate.cpp - written and placed in the public domain by Wei Dai 2 3// Many of the algorithms and tables used here came from the deflate implementation 4// by Jean-loup Gailly, which was included in Crypto++ 4.0 and earlier. I completely 5// rewrote it in order to fix a bug that I could not figure out. This code 6// is less clever, but hopefully more understandable and maintainable. 7 8#include "pch.h" 9#include "zdeflate.h" 10#include <functional> 11 12NAMESPACE_BEGIN(CryptoPP) 13 14using namespace std; 15 16LowFirstBitWriter::LowFirstBitWriter(BufferedTransformation *attachment) 17 : Filter(attachment), m_counting(false), m_buffer(0), m_bitsBuffered(0), m_bytesBuffered(0) 18{ 19} 20 21void LowFirstBitWriter::StartCounting() 22{ 23 assert(!m_counting); 24 m_counting = true; 25 m_bitCount = 0; 26} 27 28unsigned long LowFirstBitWriter::FinishCounting() 29{ 30 assert(m_counting); 31 m_counting = false; 32 return m_bitCount; 33} 34 35void LowFirstBitWriter::PutBits(unsigned long value, unsigned int length) 36{ 37 if (m_counting) 38 m_bitCount += length; 39 else 40 { 41 m_buffer |= value << m_bitsBuffered; 42 m_bitsBuffered += length; 43 assert(m_bitsBuffered <= sizeof(unsigned long)*8); 44 while (m_bitsBuffered >= 8) 45 { 46 m_outputBuffer[m_bytesBuffered++] = (byte)m_buffer; 47 if (m_bytesBuffered == m_outputBuffer.size()) 48 { 49 AttachedTransformation()->PutModifiable(m_outputBuffer, m_bytesBuffered); 50 m_bytesBuffered = 0; 51 } 52 m_buffer >>= 8; 53 m_bitsBuffered -= 8; 54 } 55 } 56} 57 58void LowFirstBitWriter::FlushBitBuffer() 59{ 60 if (m_counting) 61 m_bitCount += 8*(m_bitsBuffered > 0); 62 else 63 { 64 if (m_bytesBuffered > 0) 65 { 66 AttachedTransformation()->PutModifiable(m_outputBuffer, m_bytesBuffered); 67 m_bytesBuffered = 0; 68 } 69 if (m_bitsBuffered > 0) 70 { 71 AttachedTransformation()->Put((byte)m_buffer); 72 m_buffer = 0; 73 m_bitsBuffered = 0; 74 } 75 } 76} 77 78void LowFirstBitWriter::ClearBitBuffer() 79{ 80 m_buffer = 0; 81 m_bytesBuffered = 0; 82 m_bitsBuffered = 0; 83} 84 85HuffmanEncoder::HuffmanEncoder(const unsigned int *codeBits, unsigned int nCodes) 86{ 87 Initialize(codeBits, nCodes); 88} 89 90struct HuffmanNode 91{ 92 size_t symbol; 93 union {size_t parent; unsigned depth, freq;}; 94}; 95 96struct FreqLessThan 97{ 98 inline bool operator()(unsigned int lhs, const HuffmanNode &rhs) {return lhs < rhs.freq;} 99 inline bool operator()(const HuffmanNode &lhs, const HuffmanNode &rhs) const {return lhs.freq < rhs.freq;} 100 // needed for MSVC .NET 2005 101 inline bool operator()(const HuffmanNode &lhs, unsigned int rhs) {return lhs.freq < rhs;} 102}; 103 104void HuffmanEncoder::GenerateCodeLengths(unsigned int *codeBits, unsigned int maxCodeBits, const unsigned int *codeCounts, size_t nCodes) 105{ 106 assert(nCodes > 0); 107 assert(nCodes <= ((size_t)1 << maxCodeBits)); 108 109 size_t i; 110 SecBlockWithHint<HuffmanNode, 2*286> tree(nCodes); 111 for (i=0; i<nCodes; i++) 112 { 113 tree[i].symbol = i; 114 tree[i].freq = codeCounts[i]; 115 } 116 sort(tree.begin(), tree.end(), FreqLessThan()); 117 size_t treeBegin = upper_bound(tree.begin(), tree.end(), 0, FreqLessThan()) - tree.begin(); 118 if (treeBegin == nCodes) 119 { // special case for no codes 120 fill(codeBits, codeBits+nCodes, 0); 121 return; 122 } 123 tree.resize(nCodes + nCodes - treeBegin - 1); 124 125 size_t leastLeaf = treeBegin, leastInterior = nCodes; 126 for (i=nCodes; i<tree.size(); i++) 127 { 128 size_t least; 129 least = (leastLeaf == nCodes || (leastInterior < i && tree[leastInterior].freq < tree[leastLeaf].freq)) ? leastInterior++ : leastLeaf++; 130 tree[i].freq = tree[least].freq; 131 tree[least].parent = i; 132 least = (leastLeaf == nCodes || (leastInterior < i && tree[leastInterior].freq < tree[leastLeaf].freq)) ? leastInterior++ : leastLeaf++; 133 tree[i].freq += tree[least].freq; 134 tree[least].parent = i; 135 } 136 137 tree[tree.size()-1].depth = 0; 138 if (tree.size() >= 2) 139 for (i=tree.size()-2; i>=nCodes; i--) 140 tree[i].depth = tree[tree[i].parent].depth + 1; 141 unsigned int sum = 0; 142 SecBlockWithHint<unsigned int, 15+1> blCount(maxCodeBits+1); 143 fill(blCount.begin(), blCount.end(), 0); 144 for (i=treeBegin; i<nCodes; i++) 145 { 146 size_t depth = STDMIN(maxCodeBits, tree[tree[i].parent].depth + 1); 147 blCount[depth]++; 148 sum += 1 << (maxCodeBits - depth); 149 } 150 151 unsigned int overflow = sum > (unsigned int)(1 << maxCodeBits) ? sum - (1 << maxCodeBits) : 0; 152 153 while (overflow--) 154 { 155 unsigned int bits = maxCodeBits-1; 156 while (blCount[bits] == 0) 157 bits--; 158 blCount[bits]--; 159 blCount[bits+1] += 2; 160 assert(blCount[maxCodeBits] > 0); 161 blCount[maxCodeBits]--; 162 } 163 164 for (i=0; i<treeBegin; i++) 165 codeBits[tree[i].symbol] = 0; 166 unsigned int bits = maxCodeBits; 167 for (i=treeBegin; i<nCodes; i++) 168 { 169 while (blCount[bits] == 0) 170 bits--; 171 codeBits[tree[i].symbol] = bits; 172 blCount[bits]--; 173 } 174 assert(blCount[bits] == 0); 175} 176 177void HuffmanEncoder::Initialize(const unsigned int *codeBits, unsigned int nCodes) 178{ 179 assert(nCodes > 0); 180 unsigned int maxCodeBits = *max_element(codeBits, codeBits+nCodes); 181 if (maxCodeBits == 0) 182 return; // assume this object won't be used 183 184 SecBlockWithHint<unsigned int, 15+1> blCount(maxCodeBits+1); 185 fill(blCount.begin(), blCount.end(), 0); 186 unsigned int i; 187 for (i=0; i<nCodes; i++) 188 blCount[codeBits[i]]++; 189 190 code_t code = 0; 191 SecBlockWithHint<code_t, 15+1> nextCode(maxCodeBits+1); 192 nextCode[1] = 0; 193 for (i=2; i<=maxCodeBits; i++) 194 { 195 code = (code + blCount[i-1]) << 1; 196 nextCode[i] = code; 197 } 198 assert(maxCodeBits == 1 || code == (1 << maxCodeBits) - blCount[maxCodeBits]); 199 200 m_valueToCode.resize(nCodes); 201 for (i=0; i<nCodes; i++) 202 { 203 unsigned int len = m_valueToCode[i].len = codeBits[i]; 204 if (len != 0) 205 m_valueToCode[i].code = BitReverse(nextCode[len]++) >> (8*sizeof(code_t)-len); 206 } 207} 208 209inline void HuffmanEncoder::Encode(LowFirstBitWriter &writer, value_t value) const 210{ 211 assert(m_valueToCode[value].len > 0); 212 writer.PutBits(m_valueToCode[value].code, m_valueToCode[value].len); 213} 214 215Deflator::Deflator(BufferedTransformation *attachment, int deflateLevel, int log2WindowSize, bool detectUncompressible) 216 : LowFirstBitWriter(attachment) 217 , m_deflateLevel(-1) 218{ 219 InitializeStaticEncoders(); 220 IsolatedInitialize(MakeParameters("DeflateLevel", deflateLevel)("Log2WindowSize", log2WindowSize)("DetectUncompressible", detectUncompressible)); 221} 222 223Deflator::Deflator(const NameValuePairs ¶meters, BufferedTransformation *attachment) 224 : LowFirstBitWriter(attachment) 225 , m_deflateLevel(-1) 226{ 227 InitializeStaticEncoders(); 228 IsolatedInitialize(parameters); 229} 230 231void Deflator::InitializeStaticEncoders() 232{ 233 unsigned int codeLengths[288]; 234 fill(codeLengths + 0, codeLengths + 144, 8); 235 fill(codeLengths + 144, codeLengths + 256, 9); 236 fill(codeLengths + 256, codeLengths + 280, 7); 237 fill(codeLengths + 280, codeLengths + 288, 8); 238 m_staticLiteralEncoder.Initialize(codeLengths, 288); 239 fill(codeLengths + 0, codeLengths + 32, 5); 240 m_staticDistanceEncoder.Initialize(codeLengths, 32); 241} 242 243void Deflator::IsolatedInitialize(const NameValuePairs ¶meters) 244{ 245 int log2WindowSize = parameters.GetIntValueWithDefault("Log2WindowSize", DEFAULT_LOG2_WINDOW_SIZE); 246 if (!(MIN_LOG2_WINDOW_SIZE <= log2WindowSize && log2WindowSize <= MAX_LOG2_WINDOW_SIZE)) 247 throw InvalidArgument("Deflator: " + IntToString(log2WindowSize) + " is an invalid window size"); 248 249 m_log2WindowSize = log2WindowSize; 250 DSIZE = 1 << m_log2WindowSize; 251 DMASK = DSIZE - 1; 252 HSIZE = 1 << m_log2WindowSize; 253 HMASK = HSIZE - 1; 254 m_byteBuffer.New(2*DSIZE); 255 m_head.New(HSIZE); 256 m_prev.New(DSIZE); 257 m_matchBuffer.New(DSIZE/2); 258 Reset(true); 259 260 SetDeflateLevel(parameters.GetIntValueWithDefault("DeflateLevel", DEFAULT_DEFLATE_LEVEL)); 261 bool detectUncompressible = parameters.GetValueWithDefault("DetectUncompressible", true); 262 m_compressibleDeflateLevel = detectUncompressible ? m_deflateLevel : 0; 263} 264 265void Deflator::Reset(bool forceReset) 266{ 267 if (forceReset) 268 ClearBitBuffer(); 269 else 270 assert(m_bitsBuffered == 0); 271 272 m_headerWritten = false; 273 m_matchAvailable = false; 274 m_dictionaryEnd = 0; 275 m_stringStart = 0; 276 m_lookahead = 0; 277 m_minLookahead = MAX_MATCH; 278 m_matchBufferEnd = 0; 279 m_blockStart = 0; 280 m_blockLength = 0; 281 282 m_detectCount = 1; 283 m_detectSkip = 0; 284 285 // m_prev will be initialized automaticly in InsertString 286 fill(m_head.begin(), m_head.end(), 0); 287 288 fill(m_literalCounts.begin(), m_literalCounts.end(), 0); 289 fill(m_distanceCounts.begin(), m_distanceCounts.end(), 0); 290} 291 292void Deflator::SetDeflateLevel(int deflateLevel) 293{ 294 if (!(MIN_DEFLATE_LEVEL <= deflateLevel && deflateLevel <= MAX_DEFLATE_LEVEL)) 295 throw InvalidArgument("Deflator: " + IntToString(deflateLevel) + " is an invalid deflate level"); 296 297 if (deflateLevel == m_deflateLevel) 298 return; 299 300 EndBlock(false); 301 302 static const unsigned int configurationTable[10][4] = { 303 /* good lazy nice chain */ 304 /* 0 */ {0, 0, 0, 0}, /* store only */ 305 /* 1 */ {4, 3, 8, 4}, /* maximum speed, no lazy matches */ 306 /* 2 */ {4, 3, 16, 8}, 307 /* 3 */ {4, 3, 32, 32}, 308 /* 4 */ {4, 4, 16, 16}, /* lazy matches */ 309 /* 5 */ {8, 16, 32, 32}, 310 /* 6 */ {8, 16, 128, 128}, 311 /* 7 */ {8, 32, 128, 256}, 312 /* 8 */ {32, 128, 258, 1024}, 313 /* 9 */ {32, 258, 258, 4096}}; /* maximum compression */ 314 315 GOOD_MATCH = configurationTable[deflateLevel][0]; 316 MAX_LAZYLENGTH = configurationTable[deflateLevel][1]; 317 MAX_CHAIN_LENGTH = configurationTable[deflateLevel][3]; 318 319 m_deflateLevel = deflateLevel; 320} 321 322unsigned int Deflator::FillWindow(const byte *str, size_t length) 323{ 324 unsigned int maxBlockSize = (unsigned int)STDMIN(2UL*DSIZE, 0xffffUL); 325 326 if (m_stringStart >= maxBlockSize - MAX_MATCH) 327 { 328 if (m_blockStart < DSIZE) 329 EndBlock(false); 330 331 memcpy(m_byteBuffer, m_byteBuffer + DSIZE, DSIZE); 332 333 m_dictionaryEnd = m_dictionaryEnd < DSIZE ? 0 : m_dictionaryEnd-DSIZE; 334 assert(m_stringStart >= DSIZE); 335 m_stringStart -= DSIZE; 336 assert(!m_matchAvailable || m_previousMatch >= DSIZE); 337 m_previousMatch -= DSIZE; 338 assert(m_blockStart >= DSIZE); 339 m_blockStart -= DSIZE; 340 341 unsigned int i; 342 343 for (i=0; i<HSIZE; i++) 344 m_head[i] = SaturatingSubtract(m_head[i], DSIZE); 345 346 for (i=0; i<DSIZE; i++) 347 m_prev[i] = SaturatingSubtract(m_prev[i], DSIZE); 348 } 349 350 assert(maxBlockSize > m_stringStart+m_lookahead); 351 unsigned int accepted = UnsignedMin(maxBlockSize-(m_stringStart+m_lookahead), length); 352 assert(accepted > 0); 353 memcpy(m_byteBuffer + m_stringStart + m_lookahead, str, accepted); 354 m_lookahead += accepted; 355 return accepted; 356} 357 358inline unsigned int Deflator::ComputeHash(const byte *str) const 359{ 360 assert(str+3 <= m_byteBuffer + m_stringStart + m_lookahead); 361 return ((str[0] << 10) ^ (str[1] << 5) ^ str[2]) & HMASK; 362} 363 364unsigned int Deflator::LongestMatch(unsigned int &bestMatch) const 365{ 366 assert(m_previousLength < MAX_MATCH); 367 368 bestMatch = 0; 369 unsigned int bestLength = STDMAX(m_previousLength, (unsigned int)MIN_MATCH-1); 370 if (m_lookahead <= bestLength) 371 return 0; 372 373 const byte *scan = m_byteBuffer + m_stringStart, *scanEnd = scan + STDMIN((unsigned int)MAX_MATCH, m_lookahead); 374 unsigned int limit = m_stringStart > (DSIZE-MAX_MATCH) ? m_stringStart - (DSIZE-MAX_MATCH) : 0; 375 unsigned int current = m_head[ComputeHash(scan)]; 376 377 unsigned int chainLength = MAX_CHAIN_LENGTH; 378 if (m_previousLength >= GOOD_MATCH) 379 chainLength >>= 2; 380 381 while (current > limit && --chainLength > 0) 382 { 383 const byte *match = m_byteBuffer + current; 384 assert(scan + bestLength < m_byteBuffer + m_stringStart + m_lookahead); 385 if (scan[bestLength-1] == match[bestLength-1] && scan[bestLength] == match[bestLength] && scan[0] == match[0] && scan[1] == match[1]) 386 { 387 assert(scan[2] == match[2]); 388 unsigned int len = (unsigned int)( 389#if defined(_STDEXT_BEGIN) && !(defined(_MSC_VER) && _MSC_VER < 1400) && !defined(_STLPORT_VERSION) 390 stdext::unchecked_mismatch 391#else 392 std::mismatch 393#endif 394 (scan+3, scanEnd, match+3).first - scan); 395 assert(len != bestLength); 396 if (len > bestLength) 397 { 398 bestLength = len; 399 bestMatch = current; 400 if (len == (scanEnd - scan)) 401 break; 402 } 403 } 404 current = m_prev[current & DMASK]; 405 } 406 return (bestMatch > 0) ? bestLength : 0; 407} 408 409inline void Deflator::InsertString(unsigned int start) 410{ 411 unsigned int hash = ComputeHash(m_byteBuffer + start); 412 m_prev[start & DMASK] = m_head[hash]; 413 m_head[hash] = start; 414} 415 416void Deflator::ProcessBuffer() 417{ 418 if (!m_headerWritten) 419 { 420 WritePrestreamHeader(); 421 m_headerWritten = true; 422 } 423 424 if (m_deflateLevel == 0) 425 { 426 m_stringStart += m_lookahead; 427 m_lookahead = 0; 428 m_blockLength = m_stringStart - m_blockStart; 429 m_matchAvailable = false; 430 return; 431 } 432 433 while (m_lookahead > m_minLookahead) 434 { 435 while (m_dictionaryEnd < m_stringStart && m_dictionaryEnd+3 <= m_stringStart+m_lookahead) 436 InsertString(m_dictionaryEnd++); 437 438 if (m_matchAvailable) 439 { 440 unsigned int matchPosition, matchLength; 441 bool usePreviousMatch; 442 if (m_previousLength >= MAX_LAZYLENGTH) 443 usePreviousMatch = true; 444 else 445 { 446 matchLength = LongestMatch(matchPosition); 447 usePreviousMatch = (matchLength == 0); 448 } 449 if (usePreviousMatch) 450 { 451 MatchFound(m_stringStart-1-m_previousMatch, m_previousLength); 452 m_stringStart += m_previousLength-1; 453 m_lookahead -= m_previousLength-1; 454 m_matchAvailable = false; 455 } 456 else 457 { 458 m_previousLength = matchLength; 459 m_previousMatch = matchPosition; 460 LiteralByte(m_byteBuffer[m_stringStart-1]); 461 m_stringStart++; 462 m_lookahead--; 463 } 464 } 465 else 466 { 467 m_previousLength = 0; 468 m_previousLength = LongestMatch(m_previousMatch); 469 if (m_previousLength) 470 m_matchAvailable = true; 471 else 472 LiteralByte(m_byteBuffer[m_stringStart]); 473 m_stringStart++; 474 m_lookahead--; 475 } 476 477 assert(m_stringStart - (m_blockStart+m_blockLength) == (unsigned int)m_matchAvailable); 478 } 479 480 if (m_minLookahead == 0 && m_matchAvailable) 481 { 482 LiteralByte(m_byteBuffer[m_stringStart-1]); 483 m_matchAvailable = false; 484 } 485} 486 487size_t Deflator::Put2(const byte *str, size_t length, int messageEnd, bool blocking) 488{ 489 if (!blocking) 490 throw BlockingInputOnly("Deflator"); 491 492 size_t accepted = 0; 493 while (accepted < length) 494 { 495 unsigned int newAccepted = FillWindow(str+accepted, length-accepted); 496 ProcessBuffer(); 497 // call ProcessUncompressedData() after WritePrestreamHeader() 498 ProcessUncompressedData(str+accepted, newAccepted); 499 accepted += newAccepted; 500 } 501 assert(accepted == length); 502 503 if (messageEnd) 504 { 505 m_minLookahead = 0; 506 ProcessBuffer(); 507 EndBlock(true); 508 FlushBitBuffer(); 509 WritePoststreamTail(); 510 Reset(); 511 } 512 513 Output(0, NULL, 0, messageEnd, blocking); 514 return 0; 515} 516 517bool Deflator::IsolatedFlush(bool hardFlush, bool blocking) 518{ 519 if (!blocking) 520 throw BlockingInputOnly("Deflator"); 521 522 m_minLookahead = 0; 523 ProcessBuffer(); 524 m_minLookahead = MAX_MATCH; 525 EndBlock(false); 526 if (hardFlush) 527 EncodeBlock(false, STORED); 528 return false; 529} 530 531void Deflator::LiteralByte(byte b) 532{ 533 if (m_matchBufferEnd == m_matchBuffer.size()) 534 EndBlock(false); 535 536 m_matchBuffer[m_matchBufferEnd++].literalCode = b; 537 m_literalCounts[b]++; 538 m_blockLength++; 539} 540 541void Deflator::MatchFound(unsigned int distance, unsigned int length) 542{ 543 if (m_matchBufferEnd == m_matchBuffer.size()) 544 EndBlock(false); 545 546 static const unsigned int lengthCodes[] = { 547 257, 258, 259, 260, 261, 262, 263, 264, 265, 265, 266, 266, 267, 267, 268, 268, 548 269, 269, 269, 269, 270, 270, 270, 270, 271, 271, 271, 271, 272, 272, 272, 272, 549 273, 273, 273, 273, 273, 273, 273, 273, 274, 274, 274, 274, 274, 274, 274, 274, 550 275, 275, 275, 275, 275, 275, 275, 275, 276, 276, 276, 276, 276, 276, 276, 276, 551 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 277, 552 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 278, 553 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 279, 554 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 280, 555 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 556 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 281, 557 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 558 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 282, 559 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 560 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 561 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 562 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 284, 285}; 563 static const unsigned int lengthBases[] = {3,4,5,6,7,8,9,10,11,13,15,17,19,23,27,31,35,43,51,59,67,83,99,115,131,163,195,227,258}; 564 static const unsigned int distanceBases[30] = 565 {1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193,257,385,513,769,1025,1537,2049,3073,4097,6145,8193,12289,16385,24577}; 566 567 EncodedMatch &m = m_matchBuffer[m_matchBufferEnd++]; 568 assert(length >= 3); 569 unsigned int lengthCode = lengthCodes[length-3]; 570 m.literalCode = lengthCode; 571 m.literalExtra = length - lengthBases[lengthCode-257]; 572 unsigned int distanceCode = (unsigned int)(upper_bound(distanceBases, distanceBases+30, distance) - distanceBases - 1); 573 m.distanceCode = distanceCode; 574 m.distanceExtra = distance - distanceBases[distanceCode]; 575 576 m_literalCounts[lengthCode]++; 577 m_distanceCounts[distanceCode]++; 578 m_blockLength += length; 579} 580 581inline unsigned int CodeLengthEncode(const unsigned int *begin, 582 const unsigned int *end, 583 const unsigned int *& p, 584 unsigned int &extraBits, 585 unsigned int &extraBitsLength) 586{ 587 unsigned int v = *p; 588 if ((end-p) >= 3) 589 { 590 const unsigned int *oldp = p; 591 if (v==0 && p[1]==0 && p[2]==0) 592 { 593 for (p=p+3; p!=end && *p==0 && p!=oldp+138; p++) {} 594 unsigned int repeat = (unsigned int)(p - oldp); 595 if (repeat <= 10) 596 { 597 extraBits = repeat-3; 598 extraBitsLength = 3; 599 return 17; 600 } 601 else 602 { 603 extraBits = repeat-11; 604 extraBitsLength = 7; 605 return 18; 606 } 607 } 608 else if (p!=begin && v==p[-1] && v==p[1] && v==p[2]) 609 { 610 for (p=p+3; p!=end && *p==v && p!=oldp+6; p++) {} 611 unsigned int repeat = (unsigned int)(p - oldp); 612 extraBits = repeat-3; 613 extraBitsLength = 2; 614 return 16; 615 } 616 } 617 p++; 618 extraBits = 0; 619 extraBitsLength = 0; 620 return v; 621} 622 623void Deflator::EncodeBlock(bool eof, unsigned int blockType) 624{ 625 PutBits(eof, 1); 626 PutBits(blockType, 2); 627 628 if (blockType == STORED) 629 { 630 assert(m_blockStart + m_blockLength <= m_byteBuffer.size()); 631 assert(m_blockLength <= 0xffff); 632 FlushBitBuffer(); 633 AttachedTransformation()->PutWord16(m_blockLength, LITTLE_ENDIAN_ORDER); 634 AttachedTransformation()->PutWord16(~m_blockLength, LITTLE_ENDIAN_ORDER); 635 AttachedTransformation()->Put(m_byteBuffer + m_blockStart, m_blockLength); 636 } 637 else 638 { 639 if (blockType == DYNAMIC) 640 { 641#if defined(_MSC_VER) && !defined(__MWERKS__) && (_MSC_VER <= 1300) 642 // VC60 and VC7 workaround: built-in reverse_iterator has two template parameters, Dinkumware only has one 643 typedef reverse_bidirectional_iterator<unsigned int *, unsigned int> RevIt; 644#elif defined(_RWSTD_NO_CLASS_PARTIAL_SPEC) 645 typedef reverse_iterator<unsigned int *, random_access_iterator_tag, unsigned int> RevIt; 646#else 647 typedef reverse_iterator<unsigned int *> RevIt; 648#endif 649 650 FixedSizeSecBlock<unsigned int, 286> literalCodeLengths; 651 FixedSizeSecBlock<unsigned int, 30> distanceCodeLengths; 652 653 m_literalCounts[256] = 1; 654 HuffmanEncoder::GenerateCodeLengths(literalCodeLengths, 15, m_literalCounts, 286); 655 m_dynamicLiteralEncoder.Initialize(literalCodeLengths, 286); 656 unsigned int hlit = (unsigned int)(find_if(RevIt(literalCodeLengths.end()), RevIt(literalCodeLengths.begin()+257), bind2nd(not_equal_to<unsigned int>(), 0)).base() - (literalCodeLengths.begin()+257)); 657 658 HuffmanEncoder::GenerateCodeLengths(distanceCodeLengths, 15, m_distanceCounts, 30); 659 m_dynamicDistanceEncoder.Initialize(distanceCodeLengths, 30); 660 unsigned int hdist = (unsigned int)(find_if(RevIt(distanceCodeLengths.end()), RevIt(distanceCodeLengths.begin()+1), bind2nd(not_equal_to<unsigned int>(), 0)).base() - (distanceCodeLengths.begin()+1)); 661 662 SecBlockWithHint<unsigned int, 286+30> combinedLengths(hlit+257+hdist+1); 663 memcpy(combinedLengths, literalCodeLengths, (hlit+257)*sizeof(unsigned int)); 664 memcpy(combinedLengths+hlit+257, distanceCodeLengths, (hdist+1)*sizeof(unsigned int)); 665 666 FixedSizeSecBlock<unsigned int, 19> codeLengthCodeCounts, codeLengthCodeLengths; 667 fill(codeLengthCodeCounts.begin(), codeLengthCodeCounts.end(), 0); 668 const unsigned int *p = combinedLengths.begin(), *begin = combinedLengths.begin(), *end = combinedLengths.end(); 669 while (p != end) 670 { 671 unsigned int code, extraBits, extraBitsLength; 672 code = CodeLengthEncode(begin, end, p, extraBits, extraBitsLength); 673 codeLengthCodeCounts[code]++; 674 } 675 HuffmanEncoder::GenerateCodeLengths(codeLengthCodeLengths, 7, codeLengthCodeCounts, 19); 676 HuffmanEncoder codeLengthEncoder(codeLengthCodeLengths, 19); 677 static const unsigned int border[] = { // Order of the bit length code lengths 678 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 679 unsigned int hclen = 19; 680 while (hclen > 4 && codeLengthCodeLengths[border[hclen-1]] == 0) 681 hclen--; 682 hclen -= 4; 683 684 PutBits(hlit, 5); 685 PutBits(hdist, 5); 686 PutBits(hclen, 4); 687 688 for (unsigned int i=0; i<hclen+4; i++) 689 PutBits(codeLengthCodeLengths[border[i]], 3); 690 691 p = combinedLengths.begin(); 692 while (p != end) 693 { 694 unsigned int code, extraBits, extraBitsLength; 695 code = CodeLengthEncode(begin, end, p, extraBits, extraBitsLength); 696 codeLengthEncoder.Encode(*this, code); 697 PutBits(extraBits, extraBitsLength); 698 } 699 } 700 701 static const unsigned int lengthExtraBits[] = { 702 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 703 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0}; 704 static const unsigned int distanceExtraBits[] = { 705 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 706 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 707 12, 12, 13, 13}; 708 709 const HuffmanEncoder &literalEncoder = (blockType == STATIC) ? m_staticLiteralEncoder : m_dynamicLiteralEncoder; 710 const HuffmanEncoder &distanceEncoder = (blockType == STATIC) ? m_staticDistanceEncoder : m_dynamicDistanceEncoder; 711 712 for (unsigned int i=0; i<m_matchBufferEnd; i++) 713 { 714 unsigned int literalCode = m_matchBuffer[i].literalCode; 715 literalEncoder.Encode(*this, literalCode); 716 if (literalCode >= 257) 717 { 718 assert(literalCode <= 285); 719 PutBits(m_matchBuffer[i].literalExtra, lengthExtraBits[literalCode-257]); 720 unsigned int distanceCode = m_matchBuffer[i].distanceCode; 721 distanceEncoder.Encode(*this, distanceCode); 722 PutBits(m_matchBuffer[i].distanceExtra, distanceExtraBits[distanceCode]); 723 } 724 } 725 literalEncoder.Encode(*this, 256); // end of block 726 } 727} 728 729void Deflator::EndBlock(bool eof) 730{ 731 if (m_blockLength == 0 && !eof) 732 return; 733 734 if (m_deflateLevel == 0) 735 { 736 EncodeBlock(eof, STORED); 737 738 if (m_compressibleDeflateLevel > 0 && ++m_detectCount == m_detectSkip) 739 { 740 m_deflateLevel = m_compressibleDeflateLevel; 741 m_detectCount = 1; 742 } 743 } 744 else 745 { 746 unsigned long storedLen = 8*((unsigned long)m_blockLength+4) + RoundUpToMultipleOf(m_bitsBuffered+3, 8U)-m_bitsBuffered; 747 748 StartCounting(); 749 EncodeBlock(eof, STATIC); 750 unsigned long staticLen = FinishCounting(); 751 752 unsigned long dynamicLen; 753 if (m_blockLength < 128 && m_deflateLevel < 8) 754 dynamicLen = ULONG_MAX; 755 else 756 { 757 StartCounting(); 758 EncodeBlock(eof, DYNAMIC); 759 dynamicLen = FinishCounting(); 760 } 761 762 if (storedLen <= staticLen && storedLen <= dynamicLen) 763 { 764 EncodeBlock(eof, STORED); 765 766 if (m_compressibleDeflateLevel > 0) 767 { 768 if (m_detectSkip) 769 m_deflateLevel = 0; 770 m_detectSkip = m_detectSkip ? STDMIN(2*m_detectSkip, 128U) : 1; 771 } 772 } 773 else 774 { 775 if (staticLen <= dynamicLen) 776 EncodeBlock(eof, STATIC); 777 else 778 EncodeBlock(eof, DYNAMIC); 779 780 if (m_compressibleDeflateLevel > 0) 781 m_detectSkip = 0; 782 } 783 } 784 785 m_matchBufferEnd = 0; 786 m_blockStart += m_blockLength; 787 m_blockLength = 0; 788 fill(m_literalCounts.begin(), m_literalCounts.end(), 0); 789 fill(m_distanceCounts.begin(), m_distanceCounts.end(), 0); 790} 791 792NAMESPACE_END 793