1/* 2Copyright 2011 Google Inc. All Rights Reserved. 3 4Licensed under the Apache License, Version 2.0 (the "License"); 5you may not use this file except in compliance with the License. 6You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10Unless required by applicable law or agreed to in writing, software 11distributed under the License is distributed on an "AS IS" BASIS, 12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13See the License for the specific language governing permissions and 14limitations under the License. 15 16Author: lode.vandevenne@gmail.com (Lode Vandevenne) 17Author: jyrki.alakuijala@gmail.com (Jyrki Alakuijala) 18*/ 19 20/* 21Modified by madler@alumni.caltech.edu (Mark Adler) 22Moved ZopfliInitOptions() from zopfli_lib.c. 23*/ 24 25#include "deflate.h" 26 27#include <assert.h> 28#include <stdio.h> 29#include <stdlib.h> 30 31#include "blocksplitter.h" 32#include "lz77.h" 33#include "squeeze.h" 34#include "tree.h" 35 36void ZopfliInitOptions(ZopfliOptions* options) { 37 options->verbose = 0; 38 options->numiterations = 15; 39 options->blocksplitting = 1; 40 options->blocksplittinglast = 0; 41 options->blocksplittingmax = 15; 42} 43 44static void AddBit(int bit, 45 unsigned char* bp, unsigned char** out, size_t* outsize) { 46 if (((*bp) & 7) == 0) ZOPFLI_APPEND_DATA(0, out, outsize); 47 (*out)[*outsize - 1] |= bit << ((*bp) & 7); 48 (*bp)++; 49} 50 51static void AddBits(unsigned symbol, unsigned length, 52 unsigned char* bp, unsigned char** out, size_t* outsize) { 53 /* TODO(lode): make more efficient (add more bits at once). */ 54 unsigned i; 55 for (i = 0; i < length; i++) { 56 unsigned bit = (symbol >> i) & 1; 57 if (((*bp) & 7) == 0) ZOPFLI_APPEND_DATA(0, out, outsize); 58 (*out)[*outsize - 1] |= bit << ((*bp) & 7); 59 (*bp)++; 60 } 61} 62 63/* 64Adds bits, like AddBits, but the order is inverted. The deflate specification 65uses both orders in one standard. 66*/ 67static void AddHuffmanBits(unsigned symbol, unsigned length, 68 unsigned char* bp, unsigned char** out, 69 size_t* outsize) { 70 /* TODO(lode): make more efficient (add more bits at once). */ 71 unsigned i; 72 for (i = 0; i < length; i++) { 73 unsigned bit = (symbol >> (length - i - 1)) & 1; 74 if (((*bp) & 7) == 0) ZOPFLI_APPEND_DATA(0, out, outsize); 75 (*out)[*outsize - 1] |= bit << ((*bp) & 7); 76 (*bp)++; 77 } 78} 79 80/* 81Ensures there are at least 2 distance codes to support buggy decoders. 82Zlib 1.2.1 and below have a bug where it fails if there isn't at least 1 83distance code (with length > 0), even though it's valid according to the 84deflate spec to have 0 distance codes. On top of that, some mobile phones 85require at least two distance codes. To support these decoders too (but 86potentially at the cost of a few bytes), add dummy code lengths of 1. 87References to this bug can be found in the changelog of 88Zlib 1.2.2 and here: http://www.jonof.id.au/forum/index.php?topic=515.0. 89 90d_lengths: the 32 lengths of the distance codes. 91*/ 92static void PatchDistanceCodesForBuggyDecoders(unsigned* d_lengths) { 93 int num_dist_codes = 0; /* Amount of non-zero distance codes */ 94 int i; 95 for (i = 0; i < 30 /* Ignore the two unused codes from the spec */; i++) { 96 if (d_lengths[i]) num_dist_codes++; 97 if (num_dist_codes >= 2) return; /* Two or more codes is fine. */ 98 } 99 100 if (num_dist_codes == 0) { 101 d_lengths[0] = d_lengths[1] = 1; 102 } else if (num_dist_codes == 1) { 103 d_lengths[d_lengths[0] ? 1 : 0] = 1; 104 } 105} 106 107static void AddDynamicTree(const unsigned* ll_lengths, 108 const unsigned* d_lengths, 109 unsigned char* bp, 110 unsigned char** out, size_t* outsize) { 111 unsigned* lld_lengths = 0; /* All litlen and dist lengthts with ending zeros 112 trimmed together in one array. */ 113 unsigned lld_total; /* Size of lld_lengths. */ 114 unsigned* rle = 0; /* Runlength encoded version of lengths of litlen and dist 115 trees. */ 116 unsigned* rle_bits = 0; /* Extra bits for rle values 16, 17 and 18. */ 117 size_t rle_size = 0; /* Size of rle array. */ 118 size_t rle_bits_size = 0; /* Should have same value as rle_size. */ 119 unsigned hlit = 29; /* 286 - 257 */ 120 unsigned hdist = 29; /* 32 - 1, but gzip does not like hdist > 29.*/ 121 unsigned hclen; 122 size_t i, j; 123 size_t clcounts[19]; 124 unsigned clcl[19]; /* Code length code lengths. */ 125 unsigned clsymbols[19]; 126 /* The order in which code length code lengths are encoded as per deflate. */ 127 unsigned order[19] = { 128 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 129 }; 130 131 /* Trim zeros. */ 132 while (hlit > 0 && ll_lengths[257 + hlit - 1] == 0) hlit--; 133 while (hdist > 0 && d_lengths[1 + hdist - 1] == 0) hdist--; 134 135 lld_total = hlit + 257 + hdist + 1; 136 lld_lengths = (unsigned*)malloc(sizeof(*lld_lengths) * lld_total); 137 if (!lld_lengths) exit(-1); /* Allocation failed. */ 138 139 for (i = 0; i < lld_total; i++) { 140 lld_lengths[i] = i < 257 + hlit 141 ? ll_lengths[i] : d_lengths[i - 257 - hlit]; 142 assert(lld_lengths[i] < 16); 143 } 144 145 for (i = 0; i < lld_total; i++) { 146 size_t count = 0; 147 for (j = i; j < lld_total && lld_lengths[i] == lld_lengths[j]; j++) { 148 count++; 149 } 150 if (count >= 4 || (count >= 3 && lld_lengths[i] == 0)) { 151 if (lld_lengths[i] == 0) { 152 if (count > 10) { 153 if (count > 138) count = 138; 154 ZOPFLI_APPEND_DATA(18, &rle, &rle_size); 155 ZOPFLI_APPEND_DATA(count - 11, &rle_bits, &rle_bits_size); 156 } else { 157 ZOPFLI_APPEND_DATA(17, &rle, &rle_size); 158 ZOPFLI_APPEND_DATA(count - 3, &rle_bits, &rle_bits_size); 159 } 160 } else { 161 unsigned repeat = count - 1; /* Since the first one is hardcoded. */ 162 ZOPFLI_APPEND_DATA(lld_lengths[i], &rle, &rle_size); 163 ZOPFLI_APPEND_DATA(0, &rle_bits, &rle_bits_size); 164 while (repeat >= 6) { 165 ZOPFLI_APPEND_DATA(16, &rle, &rle_size); 166 ZOPFLI_APPEND_DATA(6 - 3, &rle_bits, &rle_bits_size); 167 repeat -= 6; 168 } 169 if (repeat >= 3) { 170 ZOPFLI_APPEND_DATA(16, &rle, &rle_size); 171 ZOPFLI_APPEND_DATA(3 - 3, &rle_bits, &rle_bits_size); 172 repeat -= 3; 173 } 174 while (repeat != 0) { 175 ZOPFLI_APPEND_DATA(lld_lengths[i], &rle, &rle_size); 176 ZOPFLI_APPEND_DATA(0, &rle_bits, &rle_bits_size); 177 repeat--; 178 } 179 } 180 181 i += count - 1; 182 } else { 183 ZOPFLI_APPEND_DATA(lld_lengths[i], &rle, &rle_size); 184 ZOPFLI_APPEND_DATA(0, &rle_bits, &rle_bits_size); 185 } 186 assert(rle[rle_size - 1] <= 18); 187 } 188 189 for (i = 0; i < 19; i++) { 190 clcounts[i] = 0; 191 } 192 for (i = 0; i < rle_size; i++) { 193 clcounts[rle[i]]++; 194 } 195 196 ZopfliCalculateBitLengths(clcounts, 19, 7, clcl); 197 ZopfliLengthsToSymbols(clcl, 19, 7, clsymbols); 198 199 hclen = 15; 200 /* Trim zeros. */ 201 while (hclen > 0 && clcounts[order[hclen + 4 - 1]] == 0) hclen--; 202 203 AddBits(hlit, 5, bp, out, outsize); 204 AddBits(hdist, 5, bp, out, outsize); 205 AddBits(hclen, 4, bp, out, outsize); 206 207 for (i = 0; i < hclen + 4; i++) { 208 AddBits(clcl[order[i]], 3, bp, out, outsize); 209 } 210 211 for (i = 0; i < rle_size; i++) { 212 unsigned symbol = clsymbols[rle[i]]; 213 AddHuffmanBits(symbol, clcl[rle[i]], bp, out, outsize); 214 /* Extra bits. */ 215 if (rle[i] == 16) AddBits(rle_bits[i], 2, bp, out, outsize); 216 else if (rle[i] == 17) AddBits(rle_bits[i], 3, bp, out, outsize); 217 else if (rle[i] == 18) AddBits(rle_bits[i], 7, bp, out, outsize); 218 } 219 220 free(lld_lengths); 221 free(rle); 222 free(rle_bits); 223} 224 225/* 226Gives the exact size of the tree, in bits, as it will be encoded in DEFLATE. 227*/ 228static size_t CalculateTreeSize(const unsigned* ll_lengths, 229 const unsigned* d_lengths, 230 size_t* ll_counts, size_t* d_counts) { 231 unsigned char* dummy = 0; 232 size_t dummysize = 0; 233 unsigned char bp = 0; 234 235 (void)ll_counts; 236 (void)d_counts; 237 238 AddDynamicTree(ll_lengths, d_lengths, &bp, &dummy, &dummysize); 239 free(dummy); 240 241 return dummysize * 8 + (bp & 7); 242} 243 244/* 245Adds all lit/len and dist codes from the lists as huffman symbols. Does not add 246end code 256. expected_data_size is the uncompressed block size, used for 247assert, but you can set it to 0 to not do the assertion. 248*/ 249static void AddLZ77Data(const unsigned short* litlens, 250 const unsigned short* dists, 251 size_t lstart, size_t lend, 252 size_t expected_data_size, 253 const unsigned* ll_symbols, const unsigned* ll_lengths, 254 const unsigned* d_symbols, const unsigned* d_lengths, 255 unsigned char* bp, 256 unsigned char** out, size_t* outsize) { 257 size_t testlength = 0; 258 size_t i; 259 260 for (i = lstart; i < lend; i++) { 261 unsigned dist = dists[i]; 262 unsigned litlen = litlens[i]; 263 if (dist == 0) { 264 assert(litlen < 256); 265 assert(ll_lengths[litlen] > 0); 266 AddHuffmanBits(ll_symbols[litlen], ll_lengths[litlen], bp, out, outsize); 267 testlength++; 268 } else { 269 unsigned lls = ZopfliGetLengthSymbol(litlen); 270 unsigned ds = ZopfliGetDistSymbol(dist); 271 assert(litlen >= 3 && litlen <= 288); 272 assert(ll_lengths[lls] > 0); 273 assert(d_lengths[ds] > 0); 274 AddHuffmanBits(ll_symbols[lls], ll_lengths[lls], bp, out, outsize); 275 AddBits(ZopfliGetLengthExtraBitsValue(litlen), 276 ZopfliGetLengthExtraBits(litlen), 277 bp, out, outsize); 278 AddHuffmanBits(d_symbols[ds], d_lengths[ds], bp, out, outsize); 279 AddBits(ZopfliGetDistExtraBitsValue(dist), 280 ZopfliGetDistExtraBits(dist), 281 bp, out, outsize); 282 testlength += litlen; 283 } 284 } 285 assert(expected_data_size == 0 || testlength == expected_data_size); 286} 287 288static void GetFixedTree(unsigned* ll_lengths, unsigned* d_lengths) { 289 size_t i; 290 for (i = 0; i < 144; i++) ll_lengths[i] = 8; 291 for (i = 144; i < 256; i++) ll_lengths[i] = 9; 292 for (i = 256; i < 280; i++) ll_lengths[i] = 7; 293 for (i = 280; i < 288; i++) ll_lengths[i] = 8; 294 for (i = 0; i < 32; i++) d_lengths[i] = 5; 295} 296 297/* 298Calculates size of the part after the header and tree of an LZ77 block, in bits. 299*/ 300static size_t CalculateBlockSymbolSize(const unsigned* ll_lengths, 301 const unsigned* d_lengths, 302 const unsigned short* litlens, 303 const unsigned short* dists, 304 size_t lstart, size_t lend) { 305 size_t result = 0; 306 size_t i; 307 for (i = lstart; i < lend; i++) { 308 if (dists[i] == 0) { 309 result += ll_lengths[litlens[i]]; 310 } else { 311 result += ll_lengths[ZopfliGetLengthSymbol(litlens[i])]; 312 result += d_lengths[ZopfliGetDistSymbol(dists[i])]; 313 result += ZopfliGetLengthExtraBits(litlens[i]); 314 result += ZopfliGetDistExtraBits(dists[i]); 315 } 316 } 317 result += ll_lengths[256]; /*end symbol*/ 318 return result; 319} 320 321double ZopfliCalculateBlockSize(const unsigned short* litlens, 322 const unsigned short* dists, 323 size_t lstart, size_t lend, int btype) { 324 size_t ll_counts[288]; 325 size_t d_counts[32]; 326 327 unsigned ll_lengths[288]; 328 unsigned d_lengths[32]; 329 330 double result = 3; /*bfinal and btype bits*/ 331 332 assert(btype == 1 || btype == 2); /* This is not for uncompressed blocks. */ 333 334 if(btype == 1) { 335 GetFixedTree(ll_lengths, d_lengths); 336 } else { 337 ZopfliLZ77Counts(litlens, dists, lstart, lend, ll_counts, d_counts); 338 ZopfliCalculateBitLengths(ll_counts, 288, 15, ll_lengths); 339 ZopfliCalculateBitLengths(d_counts, 32, 15, d_lengths); 340 PatchDistanceCodesForBuggyDecoders(d_lengths); 341 result += CalculateTreeSize(ll_lengths, d_lengths, ll_counts, d_counts); 342 } 343 344 result += CalculateBlockSymbolSize( 345 ll_lengths, d_lengths, litlens, dists, lstart, lend); 346 347 return result; 348} 349 350/* 351Adds a deflate block with the given LZ77 data to the output. 352options: global program options 353btype: the block type, must be 1 or 2 354final: whether to set the "final" bit on this block, must be the last block 355litlens: literal/length array of the LZ77 data, in the same format as in 356 ZopfliLZ77Store. 357dists: distance array of the LZ77 data, in the same format as in 358 ZopfliLZ77Store. 359lstart: where to start in the LZ77 data 360lend: where to end in the LZ77 data (not inclusive) 361expected_data_size: the uncompressed block size, used for assert, but you can 362 set it to 0 to not do the assertion. 363bp: output bit pointer 364out: dynamic output array to append to 365outsize: dynamic output array size 366*/ 367static void AddLZ77Block(const ZopfliOptions* options, int btype, int final, 368 const unsigned short* litlens, 369 const unsigned short* dists, 370 size_t lstart, size_t lend, 371 size_t expected_data_size, 372 unsigned char* bp, unsigned char** out, size_t* outsize) { 373 size_t ll_counts[288]; 374 size_t d_counts[32]; 375 unsigned ll_lengths[288]; 376 unsigned d_lengths[32]; 377 unsigned ll_symbols[288]; 378 unsigned d_symbols[32]; 379 size_t detect_block_size = *outsize; 380 size_t compressed_size; 381 size_t uncompressed_size = 0; 382 size_t i; 383 384 AddBit(final, bp, out, outsize); 385 AddBit(btype & 1, bp, out, outsize); 386 AddBit((btype & 2) >> 1, bp, out, outsize); 387 388 if (btype == 1) { 389 /* Fixed block. */ 390 GetFixedTree(ll_lengths, d_lengths); 391 } else { 392 /* Dynamic block. */ 393 unsigned detect_tree_size; 394 assert(btype == 2); 395 ZopfliLZ77Counts(litlens, dists, lstart, lend, ll_counts, d_counts); 396 ZopfliCalculateBitLengths(ll_counts, 288, 15, ll_lengths); 397 ZopfliCalculateBitLengths(d_counts, 32, 15, d_lengths); 398 PatchDistanceCodesForBuggyDecoders(d_lengths); 399 detect_tree_size = *outsize; 400 AddDynamicTree(ll_lengths, d_lengths, bp, out, outsize); 401 if (options->verbose) { 402 fprintf(stderr, "treesize: %d\n", (int)(*outsize - detect_tree_size)); 403 } 404 405 /* Assert that for every present symbol, the code length is non-zero. */ 406 /* TODO(lode): remove this in release version. */ 407 for (i = 0; i < 288; i++) assert(ll_counts[i] == 0 || ll_lengths[i] > 0); 408 for (i = 0; i < 32; i++) assert(d_counts[i] == 0 || d_lengths[i] > 0); 409 } 410 411 ZopfliLengthsToSymbols(ll_lengths, 288, 15, ll_symbols); 412 ZopfliLengthsToSymbols(d_lengths, 32, 15, d_symbols); 413 414 detect_block_size = *outsize; 415 AddLZ77Data(litlens, dists, lstart, lend, expected_data_size, 416 ll_symbols, ll_lengths, d_symbols, d_lengths, 417 bp, out, outsize); 418 /* End symbol. */ 419 AddHuffmanBits(ll_symbols[256], ll_lengths[256], bp, out, outsize); 420 421 for (i = lstart; i < lend; i++) { 422 uncompressed_size += dists[i] == 0 ? 1 : litlens[i]; 423 } 424 compressed_size = *outsize - detect_block_size; 425 if (options->verbose) { 426 fprintf(stderr, "compressed block size: %d (%dk) (unc: %d)\n", 427 (int)compressed_size, (int)(compressed_size / 1024), 428 (int)(uncompressed_size)); 429 } 430} 431 432static void DeflateDynamicBlock(const ZopfliOptions* options, int final, 433 const unsigned char* in, 434 size_t instart, size_t inend, 435 unsigned char* bp, 436 unsigned char** out, size_t* outsize) { 437 ZopfliBlockState s; 438 size_t blocksize = inend - instart; 439 ZopfliLZ77Store store; 440 int btype = 2; 441 442 ZopfliInitLZ77Store(&store); 443 444 s.options = options; 445 s.blockstart = instart; 446 s.blockend = inend; 447#ifdef ZOPFLI_LONGEST_MATCH_CACHE 448 s.lmc = (ZopfliLongestMatchCache*)malloc(sizeof(ZopfliLongestMatchCache)); 449 ZopfliInitCache(blocksize, s.lmc); 450#endif 451 452 ZopfliLZ77Optimal(&s, in, instart, inend, &store); 453 454 /* For small block, encoding with fixed tree can be smaller. For large block, 455 don't bother doing this expensive test, dynamic tree will be better.*/ 456 if (store.size < 1000) { 457 double dyncost, fixedcost; 458 ZopfliLZ77Store fixedstore; 459 ZopfliInitLZ77Store(&fixedstore); 460 ZopfliLZ77OptimalFixed(&s, in, instart, inend, &fixedstore); 461 dyncost = ZopfliCalculateBlockSize(store.litlens, store.dists, 462 0, store.size, 2); 463 fixedcost = ZopfliCalculateBlockSize(fixedstore.litlens, fixedstore.dists, 464 0, fixedstore.size, 1); 465 if (fixedcost < dyncost) { 466 btype = 1; 467 ZopfliCleanLZ77Store(&store); 468 store = fixedstore; 469 } else { 470 ZopfliCleanLZ77Store(&fixedstore); 471 } 472 } 473 474 AddLZ77Block(s.options, btype, final, 475 store.litlens, store.dists, 0, store.size, 476 blocksize, bp, out, outsize); 477 478#ifdef ZOPFLI_LONGEST_MATCH_CACHE 479 ZopfliCleanCache(s.lmc); 480 free(s.lmc); 481#endif 482 ZopfliCleanLZ77Store(&store); 483} 484 485static void DeflateFixedBlock(const ZopfliOptions* options, int final, 486 const unsigned char* in, 487 size_t instart, size_t inend, 488 unsigned char* bp, 489 unsigned char** out, size_t* outsize) { 490 ZopfliBlockState s; 491 size_t blocksize = inend - instart; 492 ZopfliLZ77Store store; 493 494 ZopfliInitLZ77Store(&store); 495 496 s.options = options; 497 s.blockstart = instart; 498 s.blockend = inend; 499#ifdef ZOPFLI_LONGEST_MATCH_CACHE 500 s.lmc = (ZopfliLongestMatchCache*)malloc(sizeof(ZopfliLongestMatchCache)); 501 ZopfliInitCache(blocksize, s.lmc); 502#endif 503 504 ZopfliLZ77OptimalFixed(&s, in, instart, inend, &store); 505 506 AddLZ77Block(s.options, 1, final, store.litlens, store.dists, 0, store.size, 507 blocksize, bp, out, outsize); 508 509#ifdef ZOPFLI_LONGEST_MATCH_CACHE 510 ZopfliCleanCache(s.lmc); 511 free(s.lmc); 512#endif 513 ZopfliCleanLZ77Store(&store); 514} 515 516static void DeflateNonCompressedBlock(const ZopfliOptions* options, int final, 517 const unsigned char* in, size_t instart, 518 size_t inend, 519 unsigned char* bp, 520 unsigned char** out, size_t* outsize) { 521 size_t i; 522 size_t blocksize = inend - instart; 523 unsigned short nlen = ~blocksize; 524 525 (void)options; 526 assert(blocksize < 65536); /* Non compressed blocks are max this size. */ 527 528 AddBit(final, bp, out, outsize); 529 /* BTYPE 00 */ 530 AddBit(0, bp, out, outsize); 531 AddBit(0, bp, out, outsize); 532 533 /* Any bits of input up to the next byte boundary are ignored. */ 534 *bp = 0; 535 536 ZOPFLI_APPEND_DATA(blocksize % 256, out, outsize); 537 ZOPFLI_APPEND_DATA((blocksize / 256) % 256, out, outsize); 538 ZOPFLI_APPEND_DATA(nlen % 256, out, outsize); 539 ZOPFLI_APPEND_DATA((nlen / 256) % 256, out, outsize); 540 541 for (i = instart; i < inend; i++) { 542 ZOPFLI_APPEND_DATA(in[i], out, outsize); 543 } 544} 545 546static void DeflateBlock(const ZopfliOptions* options, 547 int btype, int final, 548 const unsigned char* in, size_t instart, size_t inend, 549 unsigned char* bp, 550 unsigned char** out, size_t* outsize) { 551 if (btype == 0) { 552 DeflateNonCompressedBlock( 553 options, final, in, instart, inend, bp, out, outsize); 554 } else if (btype == 1) { 555 DeflateFixedBlock(options, final, in, instart, inend, bp, out, outsize); 556 } else { 557 assert (btype == 2); 558 DeflateDynamicBlock(options, final, in, instart, inend, bp, out, outsize); 559 } 560} 561 562/* 563Does squeeze strategy where first block splitting is done, then each block is 564squeezed. 565Parameters: see description of the ZopfliDeflate function. 566*/ 567static void DeflateSplittingFirst(const ZopfliOptions* options, 568 int btype, int final, 569 const unsigned char* in, 570 size_t instart, size_t inend, 571 unsigned char* bp, 572 unsigned char** out, size_t* outsize) { 573 size_t i; 574 size_t* splitpoints = 0; 575 size_t npoints = 0; 576 if (btype == 0) { 577 ZopfliBlockSplitSimple(in, instart, inend, 65535, &splitpoints, &npoints); 578 } else if (btype == 1) { 579 /* If all blocks are fixed tree, splitting into separate blocks only 580 increases the total size. Leave npoints at 0, this represents 1 block. */ 581 } else { 582 ZopfliBlockSplit(options, in, instart, inend, 583 options->blocksplittingmax, &splitpoints, &npoints); 584 } 585 586 for (i = 0; i <= npoints; i++) { 587 size_t start = i == 0 ? instart : splitpoints[i - 1]; 588 size_t end = i == npoints ? inend : splitpoints[i]; 589 DeflateBlock(options, btype, i == npoints && final, in, start, end, 590 bp, out, outsize); 591 } 592 593 free(splitpoints); 594} 595 596/* 597Does squeeze strategy where first the best possible lz77 is done, and then based 598on that data, block splitting is done. 599Parameters: see description of the ZopfliDeflate function. 600*/ 601static void DeflateSplittingLast(const ZopfliOptions* options, 602 int btype, int final, 603 const unsigned char* in, 604 size_t instart, size_t inend, 605 unsigned char* bp, 606 unsigned char** out, size_t* outsize) { 607 size_t i; 608 ZopfliBlockState s; 609 ZopfliLZ77Store store; 610 size_t* splitpoints = 0; 611 size_t npoints = 0; 612 613 if (btype == 0) { 614 /* This function only supports LZ77 compression. DeflateSplittingFirst 615 supports the special case of noncompressed data. Punt it to that one. */ 616 DeflateSplittingFirst(options, btype, final, 617 in, instart, inend, 618 bp, out, outsize); 619 } 620 assert(btype == 1 || btype == 2); 621 622 ZopfliInitLZ77Store(&store); 623 624 s.options = options; 625 s.blockstart = instart; 626 s.blockend = inend; 627#ifdef ZOPFLI_LONGEST_MATCH_CACHE 628 s.lmc = (ZopfliLongestMatchCache*)malloc(sizeof(ZopfliLongestMatchCache)); 629 ZopfliInitCache(inend - instart, s.lmc); 630#endif 631 632 if (btype == 2) { 633 ZopfliLZ77Optimal(&s, in, instart, inend, &store); 634 } else { 635 assert (btype == 1); 636 ZopfliLZ77OptimalFixed(&s, in, instart, inend, &store); 637 } 638 639 if (btype == 1) { 640 /* If all blocks are fixed tree, splitting into separate blocks only 641 increases the total size. Leave npoints at 0, this represents 1 block. */ 642 } else { 643 ZopfliBlockSplitLZ77(options, store.litlens, store.dists, store.size, 644 options->blocksplittingmax, &splitpoints, &npoints); 645 } 646 647 for (i = 0; i <= npoints; i++) { 648 size_t start = i == 0 ? 0 : splitpoints[i - 1]; 649 size_t end = i == npoints ? store.size : splitpoints[i]; 650 AddLZ77Block(options, btype, i == npoints && final, 651 store.litlens, store.dists, start, end, 0, 652 bp, out, outsize); 653 } 654 655#ifdef ZOPFLI_LONGEST_MATCH_CACHE 656 ZopfliCleanCache(s.lmc); 657 free(s.lmc); 658#endif 659 660 ZopfliCleanLZ77Store(&store); 661} 662 663/* 664Deflate a part, to allow ZopfliDeflate() to use multiple master blocks if 665needed. 666It is possible to call this function multiple times in a row, shifting 667instart and inend to next bytes of the data. If instart is larger than 0, then 668previous bytes are used as the initial dictionary for LZ77. 669This function will usually output multiple deflate blocks. If final is 1, then 670the final bit will be set on the last block. 671*/ 672void ZopfliDeflatePart(const ZopfliOptions* options, int btype, int final, 673 const unsigned char* in, size_t instart, size_t inend, 674 unsigned char* bp, unsigned char** out, 675 size_t* outsize) { 676 if (options->blocksplitting) { 677 if (options->blocksplittinglast) { 678 DeflateSplittingLast(options, btype, final, in, instart, inend, 679 bp, out, outsize); 680 } else { 681 DeflateSplittingFirst(options, btype, final, in, instart, inend, 682 bp, out, outsize); 683 } 684 } else { 685 DeflateBlock(options, btype, final, in, instart, inend, bp, out, outsize); 686 } 687} 688 689void ZopfliDeflate(const ZopfliOptions* options, int btype, int final, 690 const unsigned char* in, size_t insize, 691 unsigned char* bp, unsigned char** out, size_t* outsize) { 692#if ZOPFLI_MASTER_BLOCK_SIZE == 0 693 ZopfliDeflatePart(options, btype, final, in, 0, insize, bp, out, outsize); 694#else 695 size_t i = 0; 696 while (i < insize) { 697 int masterfinal = (i + ZOPFLI_MASTER_BLOCK_SIZE >= insize); 698 int final2 = final && masterfinal; 699 size_t size = masterfinal ? insize - i : ZOPFLI_MASTER_BLOCK_SIZE; 700 ZopfliDeflatePart(options, btype, final2, 701 in, i, i + size, bp, out, outsize); 702 i += size; 703 } 704#endif 705} 706