diff options
Diffstat (limited to 'deflate.c')
| -rw-r--r-- | deflate.c | 866 |
1 files changed, 0 insertions, 866 deletions
diff --git a/deflate.c b/deflate.c deleted file mode 100644 index 4b0724b..0000000 --- a/deflate.c +++ /dev/null @@ -1,866 +0,0 @@ -/* -Copyright 2011 Google Inc. All Rights Reserved. - -Licensed under the Apache License, Version 2.0 (the "License"); -you may not use this file except in compliance with the License. -You may obtain a copy of the License at - - http://www.apache.org/licenses/LICENSE-2.0 - -Unless required by applicable law or agreed to in writing, software -distributed under the License is distributed on an "AS IS" BASIS, -WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -See the License for the specific language governing permissions and -limitations under the License. - -Author: lode.vandevenne@gmail.com (Lode Vandevenne) -Author: jyrki.alakuijala@gmail.com (Jyrki Alakuijala) -*/ - -#include "deflate.h" - -#include <assert.h> -#include <stdio.h> -#include <stdlib.h> - -#include "blocksplitter.h" -#include "lz77.h" -#include "squeeze.h" -#include "tree.h" - -/* -bp = bitpointer, always in range [0, 7]. -The outsize is number of necessary bytes to encode the bits. -Given the value of bp and the amount of bytes, the amount of bits represented -is not simply bytesize * 8 + bp because even representing one bit requires a -whole byte. It is: (bp == 0) ? (bytesize * 8) : ((bytesize - 1) * 8 + bp) -*/ -static void AddBit(int bit, - unsigned char* bp, unsigned char** out, size_t* outsize) { - if (*bp == 0) ZOPFLI_APPEND_DATA(0, out, outsize); - (*out)[*outsize - 1] |= bit << *bp; - *bp = (*bp + 1) & 7; -} - -static void AddBits(unsigned symbol, unsigned length, - unsigned char* bp, unsigned char** out, size_t* outsize) { - /* TODO(lode): make more efficient (add more bits at once). */ - unsigned i; - for (i = 0; i < length; i++) { - unsigned bit = (symbol >> i) & 1; - if (*bp == 0) ZOPFLI_APPEND_DATA(0, out, outsize); - (*out)[*outsize - 1] |= bit << *bp; - *bp = (*bp + 1) & 7; - } -} - -/* -Adds bits, like AddBits, but the order is inverted. The deflate specification -uses both orders in one standard. -*/ -static void AddHuffmanBits(unsigned symbol, unsigned length, - unsigned char* bp, unsigned char** out, - size_t* outsize) { - /* TODO(lode): make more efficient (add more bits at once). */ - unsigned i; - for (i = 0; i < length; i++) { - unsigned bit = (symbol >> (length - i - 1)) & 1; - if (*bp == 0) ZOPFLI_APPEND_DATA(0, out, outsize); - (*out)[*outsize - 1] |= bit << *bp; - *bp = (*bp + 1) & 7; - } -} - -/* -Ensures there are at least 2 distance codes to support buggy decoders. -Zlib 1.2.1 and below have a bug where it fails if there isn't at least 1 -distance code (with length > 0), even though it's valid according to the -deflate spec to have 0 distance codes. On top of that, some mobile phones -require at least two distance codes. To support these decoders too (but -potentially at the cost of a few bytes), add dummy code lengths of 1. -References to this bug can be found in the changelog of -Zlib 1.2.2 and here: http://www.jonof.id.au/forum/index.php?topic=515.0. - -d_lengths: the 32 lengths of the distance codes. -*/ -static void PatchDistanceCodesForBuggyDecoders(unsigned* d_lengths) { - int num_dist_codes = 0; /* Amount of non-zero distance codes */ - int i; - for (i = 0; i < 30 /* Ignore the two unused codes from the spec */; i++) { - if (d_lengths[i]) num_dist_codes++; - if (num_dist_codes >= 2) return; /* Two or more codes is fine. */ - } - - if (num_dist_codes == 0) { - d_lengths[0] = d_lengths[1] = 1; - } else if (num_dist_codes == 1) { - d_lengths[d_lengths[0] ? 1 : 0] = 1; - } -} - -/* -Encodes the Huffman tree and returns how many bits its encoding takes. If out -is a null pointer, only returns the size and runs faster. -*/ -static size_t EncodeTree(const unsigned* ll_lengths, - const unsigned* d_lengths, - int use_16, int use_17, int use_18, - unsigned char* bp, - unsigned char** out, size_t* outsize) { - unsigned lld_total; /* Total amount of literal, length, distance codes. */ - /* Runlength encoded version of lengths of litlen and dist trees. */ - unsigned* rle = 0; - unsigned* rle_bits = 0; /* Extra bits for rle values 16, 17 and 18. */ - size_t rle_size = 0; /* Size of rle array. */ - size_t rle_bits_size = 0; /* Should have same value as rle_size. */ - unsigned hlit = 29; /* 286 - 257 */ - unsigned hdist = 29; /* 32 - 1, but gzip does not like hdist > 29.*/ - unsigned hclen; - unsigned hlit2; - size_t i, j; - size_t clcounts[19]; - unsigned clcl[19]; /* Code length code lengths. */ - unsigned clsymbols[19]; - /* The order in which code length code lengths are encoded as per deflate. */ - static const unsigned order[19] = { - 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 - }; - int size_only = !out; - size_t result_size = 0; - - for(i = 0; i < 19; i++) clcounts[i] = 0; - - /* Trim zeros. */ - while (hlit > 0 && ll_lengths[257 + hlit - 1] == 0) hlit--; - while (hdist > 0 && d_lengths[1 + hdist - 1] == 0) hdist--; - hlit2 = hlit + 257; - - lld_total = hlit2 + hdist + 1; - - for (i = 0; i < lld_total; i++) { - /* This is an encoding of a huffman tree, so now the length is a symbol */ - unsigned char symbol = i < hlit2 ? ll_lengths[i] : d_lengths[i - hlit2]; - unsigned count = 1; - if(use_16 || (symbol == 0 && (use_17 || use_18))) { - for (j = i + 1; j < lld_total && symbol == - (j < hlit2 ? ll_lengths[j] : d_lengths[j - hlit2]); j++) { - count++; - } - } - i += count - 1; - - /* Repetitions of zeroes */ - if (symbol == 0 && count >= 3) { - if (use_18) { - while (count >= 11) { - unsigned count2 = count > 138 ? 138 : count; - if (!size_only) { - ZOPFLI_APPEND_DATA(18, &rle, &rle_size); - ZOPFLI_APPEND_DATA(count2 - 11, &rle_bits, &rle_bits_size); - } - clcounts[18]++; - count -= count2; - } - } - if (use_17) { - while (count >= 3) { - unsigned count2 = count > 10 ? 10 : count; - if (!size_only) { - ZOPFLI_APPEND_DATA(17, &rle, &rle_size); - ZOPFLI_APPEND_DATA(count2 - 3, &rle_bits, &rle_bits_size); - } - clcounts[17]++; - count -= count2; - } - } - } - - /* Repetitions of any symbol */ - if (use_16 && count >= 4) { - count--; /* Since the first one is hardcoded. */ - clcounts[symbol]++; - if (!size_only) { - ZOPFLI_APPEND_DATA(symbol, &rle, &rle_size); - ZOPFLI_APPEND_DATA(0, &rle_bits, &rle_bits_size); - } - while (count >= 3) { - unsigned count2 = count > 6 ? 6 : count; - if (!size_only) { - ZOPFLI_APPEND_DATA(16, &rle, &rle_size); - ZOPFLI_APPEND_DATA(count2 - 3, &rle_bits, &rle_bits_size); - } - clcounts[16]++; - count -= count2; - } - } - - /* No or insufficient repetition */ - clcounts[symbol] += count; - while (count > 0) { - if (!size_only) { - ZOPFLI_APPEND_DATA(symbol, &rle, &rle_size); - ZOPFLI_APPEND_DATA(0, &rle_bits, &rle_bits_size); - } - count--; - } - } - - ZopfliCalculateBitLengths(clcounts, 19, 7, clcl); - if (!size_only) ZopfliLengthsToSymbols(clcl, 19, 7, clsymbols); - - hclen = 15; - /* Trim zeros. */ - while (hclen > 0 && clcounts[order[hclen + 4 - 1]] == 0) hclen--; - - if (!size_only) { - AddBits(hlit, 5, bp, out, outsize); - AddBits(hdist, 5, bp, out, outsize); - AddBits(hclen, 4, bp, out, outsize); - - for (i = 0; i < hclen + 4; i++) { - AddBits(clcl[order[i]], 3, bp, out, outsize); - } - - for (i = 0; i < rle_size; i++) { - unsigned symbol = clsymbols[rle[i]]; - AddHuffmanBits(symbol, clcl[rle[i]], bp, out, outsize); - /* Extra bits. */ - if (rle[i] == 16) AddBits(rle_bits[i], 2, bp, out, outsize); - else if (rle[i] == 17) AddBits(rle_bits[i], 3, bp, out, outsize); - else if (rle[i] == 18) AddBits(rle_bits[i], 7, bp, out, outsize); - } - } - - result_size += 14; /* hlit, hdist, hclen bits */ - result_size += (hclen + 4) * 3; /* clcl bits */ - for(i = 0; i < 19; i++) { - result_size += clcl[i] * clcounts[i]; - } - /* Extra bits. */ - result_size += clcounts[16] * 2; - result_size += clcounts[17] * 3; - result_size += clcounts[18] * 7; - - /* Note: in case of "size_only" these are null pointers so no effect. */ - free(rle); - free(rle_bits); - - return result_size; -} - -static void AddDynamicTree(const unsigned* ll_lengths, - const unsigned* d_lengths, - unsigned char* bp, - unsigned char** out, size_t* outsize) { - int i; - int best = 0; - size_t bestsize = 0; - - for(i = 0; i < 8; i++) { - size_t size = EncodeTree(ll_lengths, d_lengths, - i & 1, i & 2, i & 4, - 0, 0, 0); - if (bestsize == 0 || size < bestsize) { - bestsize = size; - best = i; - } - } - - EncodeTree(ll_lengths, d_lengths, - best & 1, best & 2, best & 4, - bp, out, outsize); -} - -/* -Gives the exact size of the tree, in bits, as it will be encoded in DEFLATE. -*/ -static size_t CalculateTreeSize(const unsigned* ll_lengths, - const unsigned* d_lengths) { - size_t result = 0; - int i; - - for(i = 0; i < 8; i++) { - size_t size = EncodeTree(ll_lengths, d_lengths, - i & 1, i & 2, i & 4, - 0, 0, 0); - if (result == 0 || size < result) result = size; - } - - return result; -} - -/* -Adds all lit/len and dist codes from the lists as huffman symbols. Does not add -end code 256. expected_data_size is the uncompressed block size, used for -assert, but you can set it to 0 to not do the assertion. -*/ -static void AddLZ77Data(const unsigned short* litlens, - const unsigned short* dists, - size_t lstart, size_t lend, - size_t expected_data_size, - const unsigned* ll_symbols, const unsigned* ll_lengths, - const unsigned* d_symbols, const unsigned* d_lengths, - unsigned char* bp, - unsigned char** out, size_t* outsize) { - size_t testlength = 0; - size_t i; - - for (i = lstart; i < lend; i++) { - unsigned dist = dists[i]; - unsigned litlen = litlens[i]; - if (dist == 0) { - assert(litlen < 256); - assert(ll_lengths[litlen] > 0); - AddHuffmanBits(ll_symbols[litlen], ll_lengths[litlen], bp, out, outsize); - testlength++; - } else { - unsigned lls = ZopfliGetLengthSymbol(litlen); - unsigned ds = ZopfliGetDistSymbol(dist); - assert(litlen >= 3 && litlen <= 288); - assert(ll_lengths[lls] > 0); - assert(d_lengths[ds] > 0); - AddHuffmanBits(ll_symbols[lls], ll_lengths[lls], bp, out, outsize); - AddBits(ZopfliGetLengthExtraBitsValue(litlen), - ZopfliGetLengthExtraBits(litlen), - bp, out, outsize); - AddHuffmanBits(d_symbols[ds], d_lengths[ds], bp, out, outsize); - AddBits(ZopfliGetDistExtraBitsValue(dist), - ZopfliGetDistExtraBits(dist), - bp, out, outsize); - testlength += litlen; - } - } - assert(expected_data_size == 0 || testlength == expected_data_size); -} - -static void GetFixedTree(unsigned* ll_lengths, unsigned* d_lengths) { - size_t i; - for (i = 0; i < 144; i++) ll_lengths[i] = 8; - for (i = 144; i < 256; i++) ll_lengths[i] = 9; - for (i = 256; i < 280; i++) ll_lengths[i] = 7; - for (i = 280; i < 288; i++) ll_lengths[i] = 8; - for (i = 0; i < 32; i++) d_lengths[i] = 5; -} - -/* -Calculates size of the part after the header and tree of an LZ77 block, in bits. -*/ -static size_t CalculateBlockSymbolSize(const unsigned* ll_lengths, - const unsigned* d_lengths, - const unsigned short* litlens, - const unsigned short* dists, - size_t lstart, size_t lend) { - size_t result = 0; - size_t i; - for (i = lstart; i < lend; i++) { - if (dists[i] == 0) { - result += ll_lengths[litlens[i]]; - } else { - result += ll_lengths[ZopfliGetLengthSymbol(litlens[i])]; - result += d_lengths[ZopfliGetDistSymbol(dists[i])]; - result += ZopfliGetLengthExtraBits(litlens[i]); - result += ZopfliGetDistExtraBits(dists[i]); - } - } - result += ll_lengths[256]; /*end symbol*/ - return result; -} - -static size_t AbsDiff(size_t x, size_t y) { - if (x > y) - return x - y; - else - return y - x; -} - -/* -Change the population counts in a way that the consequent Hufmann tree -compression, especially its rle-part will be more likely to compress this data -more efficiently. length containts the size of the histogram. -*/ -void OptimizeHuffmanForRle(int length, size_t* counts) { - int i, k, stride; - size_t symbol, sum, limit; - int* good_for_rle; - - /* 1) We don't want to touch the trailing zeros. We may break the - rules of the format by adding more data in the distance codes. */ - for (; length >= 0; --length) { - if (length == 0) { - return; - } - if (counts[length - 1] != 0) { - /* Now counts[0..length - 1] does not have trailing zeros. */ - break; - } - } - /* 2) Let's mark all population counts that already can be encoded - with an rle code.*/ - good_for_rle = (int*)malloc(length * sizeof(int)); - for (i = 0; i < length; ++i) good_for_rle[i] = 0; - - /* Let's not spoil any of the existing good rle codes. - Mark any seq of 0's that is longer than 5 as a good_for_rle. - Mark any seq of non-0's that is longer than 7 as a good_for_rle.*/ - symbol = counts[0]; - stride = 0; - for (i = 0; i < length + 1; ++i) { - if (i == length || counts[i] != symbol) { - if ((symbol == 0 && stride >= 5) || (symbol != 0 && stride >= 7)) { - for (k = 0; k < stride; ++k) { - good_for_rle[i - k - 1] = 1; - } - } - stride = 1; - if (i != length) { - symbol = counts[i]; - } - } else { - ++stride; - } - } - - /* 3) Let's replace those population counts that lead to more rle codes. */ - stride = 0; - limit = counts[0]; - sum = 0; - for (i = 0; i < length + 1; ++i) { - if (i == length || good_for_rle[i] - /* Heuristic for selecting the stride ranges to collapse. */ - || AbsDiff(counts[i], limit) >= 4) { - if (stride >= 4 || (stride >= 3 && sum == 0)) { - /* The stride must end, collapse what we have, if we have enough (4). */ - int count = (sum + stride / 2) / stride; - if (count < 1) count = 1; - if (sum == 0) { - /* Don't make an all zeros stride to be upgraded to ones. */ - count = 0; - } - for (k = 0; k < stride; ++k) { - /* We don't want to change value at counts[i], - that is already belonging to the next stride. Thus - 1. */ - counts[i - k - 1] = count; - } - } - stride = 0; - sum = 0; - if (i < length - 3) { - /* All interesting strides have a count of at least 4, - at least when non-zeros. */ - limit = (counts[i] + counts[i + 1] + - counts[i + 2] + counts[i + 3] + 2) / 4; - } else if (i < length) { - limit = counts[i]; - } else { - limit = 0; - } - } - ++stride; - if (i != length) { - sum += counts[i]; - } - } - - free(good_for_rle); -} - -/* -Calculates the bit lengths for the symbols for dynamic blocks. Chooses bit -lengths that give the smallest size of tree encoding + encoding of all the -symbols to have smallest output size. This are not necessarily the ideal Huffman -bit lengths. -*/ -static void GetDynamicLengths(const unsigned short* litlens, - const unsigned short* dists, - size_t lstart, size_t lend, - unsigned* ll_lengths, unsigned* d_lengths) { - size_t ll_counts[288]; - size_t d_counts[32]; - - ZopfliLZ77Counts(litlens, dists, lstart, lend, ll_counts, d_counts); - OptimizeHuffmanForRle(288, ll_counts); - OptimizeHuffmanForRle(32, d_counts); - ZopfliCalculateBitLengths(ll_counts, 288, 15, ll_lengths); - ZopfliCalculateBitLengths(d_counts, 32, 15, d_lengths); - PatchDistanceCodesForBuggyDecoders(d_lengths); -} - -double ZopfliCalculateBlockSize(const unsigned short* litlens, - const unsigned short* dists, - size_t lstart, size_t lend, int btype) { - unsigned ll_lengths[288]; - unsigned d_lengths[32]; - - double result = 3; /* bfinal and btype bits */ - - assert(btype == 1 || btype == 2); /* This is not for uncompressed blocks. */ - - if(btype == 1) { - GetFixedTree(ll_lengths, d_lengths); - } else { - GetDynamicLengths(litlens, dists, lstart, lend, ll_lengths, d_lengths); - result += CalculateTreeSize(ll_lengths, d_lengths); - } - - result += CalculateBlockSymbolSize( - ll_lengths, d_lengths, litlens, dists, lstart, lend); - - return result; -} - -/* -Adds a deflate block with the given LZ77 data to the output. -options: global program options -btype: the block type, must be 1 or 2 -final: whether to set the "final" bit on this block, must be the last block -litlens: literal/length array of the LZ77 data, in the same format as in - ZopfliLZ77Store. -dists: distance array of the LZ77 data, in the same format as in - ZopfliLZ77Store. -lstart: where to start in the LZ77 data -lend: where to end in the LZ77 data (not inclusive) -expected_data_size: the uncompressed block size, used for assert, but you can - set it to 0 to not do the assertion. -bp: output bit pointer -out: dynamic output array to append to -outsize: dynamic output array size -*/ -static void AddLZ77Block(const ZopfliOptions* options, int btype, int final, - const unsigned short* litlens, - const unsigned short* dists, - size_t lstart, size_t lend, - size_t expected_data_size, - unsigned char* bp, - unsigned char** out, size_t* outsize) { - unsigned ll_lengths[288]; - unsigned d_lengths[32]; - unsigned ll_symbols[288]; - unsigned d_symbols[32]; - size_t detect_block_size = *outsize; - size_t compressed_size; - size_t uncompressed_size = 0; - size_t i; - - AddBit(final, bp, out, outsize); - AddBit(btype & 1, bp, out, outsize); - AddBit((btype & 2) >> 1, bp, out, outsize); - - if (btype == 1) { - /* Fixed block. */ - GetFixedTree(ll_lengths, d_lengths); - } else { - /* Dynamic block. */ - unsigned detect_tree_size; - assert(btype == 2); - - GetDynamicLengths(litlens, dists, lstart, lend, ll_lengths, d_lengths); - - detect_tree_size = *outsize; - AddDynamicTree(ll_lengths, d_lengths, bp, out, outsize); - if (options->verbose) { - fprintf(stderr, "treesize: %d\n", (int)(*outsize - detect_tree_size)); - } - } - - ZopfliLengthsToSymbols(ll_lengths, 288, 15, ll_symbols); - ZopfliLengthsToSymbols(d_lengths, 32, 15, d_symbols); - - detect_block_size = *outsize; - AddLZ77Data(litlens, dists, lstart, lend, expected_data_size, - ll_symbols, ll_lengths, d_symbols, d_lengths, - bp, out, outsize); - /* End symbol. */ - AddHuffmanBits(ll_symbols[256], ll_lengths[256], bp, out, outsize); - - for (i = lstart; i < lend; i++) { - uncompressed_size += dists[i] == 0 ? 1 : litlens[i]; - } - compressed_size = *outsize - detect_block_size; - if (options->verbose) { - fprintf(stderr, "compressed block size: %d (%dk) (unc: %d)\n", - (int)compressed_size, (int)(compressed_size / 1024), - (int)(uncompressed_size)); - } -} - -static void DeflateDynamicBlock(const ZopfliOptions* options, int final, - const unsigned char* in, - size_t instart, size_t inend, - unsigned char* bp, - unsigned char** out, size_t* outsize) { - ZopfliBlockState s; - size_t blocksize = inend - instart; - ZopfliLZ77Store store; - int btype = 2; - - ZopfliInitLZ77Store(&store); - - s.options = options; - s.blockstart = instart; - s.blockend = inend; -#ifdef ZOPFLI_LONGEST_MATCH_CACHE - s.lmc = (ZopfliLongestMatchCache*)malloc(sizeof(ZopfliLongestMatchCache)); - ZopfliInitCache(blocksize, s.lmc); -#endif - - ZopfliLZ77Optimal(&s, in, instart, inend, &store); - - /* For small block, encoding with fixed tree can be smaller. For large block, - don't bother doing this expensive test, dynamic tree will be better.*/ - if (store.size < 1000) { - double dyncost, fixedcost; - ZopfliLZ77Store fixedstore; - ZopfliInitLZ77Store(&fixedstore); - ZopfliLZ77OptimalFixed(&s, in, instart, inend, &fixedstore); - dyncost = ZopfliCalculateBlockSize(store.litlens, store.dists, - 0, store.size, 2); - fixedcost = ZopfliCalculateBlockSize(fixedstore.litlens, fixedstore.dists, - 0, fixedstore.size, 1); - if (fixedcost < dyncost) { - btype = 1; - ZopfliCleanLZ77Store(&store); - store = fixedstore; - } else { - ZopfliCleanLZ77Store(&fixedstore); - } - } - - AddLZ77Block(s.options, btype, final, - store.litlens, store.dists, 0, store.size, - blocksize, bp, out, outsize); - -#ifdef ZOPFLI_LONGEST_MATCH_CACHE - ZopfliCleanCache(s.lmc); - free(s.lmc); -#endif - ZopfliCleanLZ77Store(&store); -} - -static void DeflateFixedBlock(const ZopfliOptions* options, int final, - const unsigned char* in, - size_t instart, size_t inend, - unsigned char* bp, - unsigned char** out, size_t* outsize) { - ZopfliBlockState s; - size_t blocksize = inend - instart; - ZopfliLZ77Store store; - - ZopfliInitLZ77Store(&store); - - s.options = options; - s.blockstart = instart; - s.blockend = inend; -#ifdef ZOPFLI_LONGEST_MATCH_CACHE - s.lmc = (ZopfliLongestMatchCache*)malloc(sizeof(ZopfliLongestMatchCache)); - ZopfliInitCache(blocksize, s.lmc); -#endif - - ZopfliLZ77OptimalFixed(&s, in, instart, inend, &store); - - AddLZ77Block(s.options, 1, final, store.litlens, store.dists, 0, store.size, - blocksize, bp, out, outsize); - -#ifdef ZOPFLI_LONGEST_MATCH_CACHE - ZopfliCleanCache(s.lmc); - free(s.lmc); -#endif - ZopfliCleanLZ77Store(&store); -} - -static void DeflateNonCompressedBlock(const ZopfliOptions* options, int final, - const unsigned char* in, size_t instart, - size_t inend, - unsigned char* bp, - unsigned char** out, size_t* outsize) { - size_t i; - size_t blocksize = inend - instart; - unsigned short nlen = ~blocksize; - - (void)options; - assert(blocksize < 65536); /* Non compressed blocks are max this size. */ - - AddBit(final, bp, out, outsize); - /* BTYPE 00 */ - AddBit(0, bp, out, outsize); - AddBit(0, bp, out, outsize); - - /* Any bits of input up to the next byte boundary are ignored. */ - *bp = 0; - - ZOPFLI_APPEND_DATA(blocksize % 256, out, outsize); - ZOPFLI_APPEND_DATA((blocksize / 256) % 256, out, outsize); - ZOPFLI_APPEND_DATA(nlen % 256, out, outsize); - ZOPFLI_APPEND_DATA((nlen / 256) % 256, out, outsize); - - for (i = instart; i < inend; i++) { - ZOPFLI_APPEND_DATA(in[i], out, outsize); - } -} - -static void DeflateBlock(const ZopfliOptions* options, - int btype, int final, - const unsigned char* in, size_t instart, size_t inend, - unsigned char* bp, - unsigned char** out, size_t* outsize) { - if (btype == 0) { - DeflateNonCompressedBlock( - options, final, in, instart, inend, bp, out, outsize); - } else if (btype == 1) { - DeflateFixedBlock(options, final, in, instart, inend, bp, out, outsize); - } else { - assert (btype == 2); - DeflateDynamicBlock(options, final, in, instart, inend, bp, out, outsize); - } -} - -/* -Does squeeze strategy where first block splitting is done, then each block is -squeezed. -Parameters: see description of the ZopfliDeflate function. -*/ -static void DeflateSplittingFirst(const ZopfliOptions* options, - int btype, int final, - const unsigned char* in, - size_t instart, size_t inend, - unsigned char* bp, - unsigned char** out, size_t* outsize) { - size_t i; - size_t* splitpoints = 0; - size_t npoints = 0; - if (btype == 0) { - ZopfliBlockSplitSimple(in, instart, inend, 65535, &splitpoints, &npoints); - } else if (btype == 1) { - /* If all blocks are fixed tree, splitting into separate blocks only - increases the total size. Leave npoints at 0, this represents 1 block. */ - } else { - ZopfliBlockSplit(options, in, instart, inend, - options->blocksplittingmax, &splitpoints, &npoints); - } - - for (i = 0; i <= npoints; i++) { - size_t start = i == 0 ? instart : splitpoints[i - 1]; - size_t end = i == npoints ? inend : splitpoints[i]; - DeflateBlock(options, btype, i == npoints && final, in, start, end, - bp, out, outsize); - } - - free(splitpoints); -} - -/* -Does squeeze strategy where first the best possible lz77 is done, and then based -on that data, block splitting is done. -Parameters: see description of the ZopfliDeflate function. -*/ -static void DeflateSplittingLast(const ZopfliOptions* options, - int btype, int final, - const unsigned char* in, - size_t instart, size_t inend, - unsigned char* bp, - unsigned char** out, size_t* outsize) { - size_t i; - ZopfliBlockState s; - ZopfliLZ77Store store; - size_t* splitpoints = 0; - size_t npoints = 0; - - if (btype == 0) { - /* This function only supports LZ77 compression. DeflateSplittingFirst - supports the special case of noncompressed data. Punt it to that one. */ - DeflateSplittingFirst(options, btype, final, - in, instart, inend, - bp, out, outsize); - } - assert(btype == 1 || btype == 2); - - ZopfliInitLZ77Store(&store); - - s.options = options; - s.blockstart = instart; - s.blockend = inend; -#ifdef ZOPFLI_LONGEST_MATCH_CACHE - s.lmc = (ZopfliLongestMatchCache*)malloc(sizeof(ZopfliLongestMatchCache)); - ZopfliInitCache(inend - instart, s.lmc); -#endif - - if (btype == 2) { - ZopfliLZ77Optimal(&s, in, instart, inend, &store); - } else { - assert (btype == 1); - ZopfliLZ77OptimalFixed(&s, in, instart, inend, &store); - } - - if (btype == 1) { - /* If all blocks are fixed tree, splitting into separate blocks only - increases the total size. Leave npoints at 0, this represents 1 block. */ - } else { - ZopfliBlockSplitLZ77(options, store.litlens, store.dists, store.size, - options->blocksplittingmax, &splitpoints, &npoints); - } - - for (i = 0; i <= npoints; i++) { - size_t start = i == 0 ? 0 : splitpoints[i - 1]; - size_t end = i == npoints ? store.size : splitpoints[i]; - AddLZ77Block(options, btype, i == npoints && final, - store.litlens, store.dists, start, end, 0, - bp, out, outsize); - } - -#ifdef ZOPFLI_LONGEST_MATCH_CACHE - ZopfliCleanCache(s.lmc); - free(s.lmc); -#endif - - ZopfliCleanLZ77Store(&store); - free(splitpoints); -} - -/* -Deflate a part, to allow ZopfliDeflate() to use multiple master blocks if -needed. -It is possible to call this function multiple times in a row, shifting -instart and inend to next bytes of the data. If instart is larger than 0, then -previous bytes are used as the initial dictionary for LZ77. -This function will usually output multiple deflate blocks. If final is 1, then -the final bit will be set on the last block. -*/ -void ZopfliDeflatePart(const ZopfliOptions* options, int btype, int final, - const unsigned char* in, size_t instart, size_t inend, - unsigned char* bp, unsigned char** out, - size_t* outsize) { - if (options->blocksplitting) { - if (options->blocksplittinglast) { - DeflateSplittingLast(options, btype, final, in, instart, inend, - bp, out, outsize); - } else { - DeflateSplittingFirst(options, btype, final, in, instart, inend, - bp, out, outsize); - } - } else { - DeflateBlock(options, btype, final, in, instart, inend, bp, out, outsize); - } -} - -void ZopfliDeflate(const ZopfliOptions* options, int btype, int final, - const unsigned char* in, size_t insize, - unsigned char* bp, unsigned char** out, size_t* outsize) { -#if ZOPFLI_MASTER_BLOCK_SIZE == 0 - ZopfliDeflatePart(options, btype, final, in, 0, insize, bp, out, outsize); -#else - size_t i = 0; - while (i < insize) { - int masterfinal = (i + ZOPFLI_MASTER_BLOCK_SIZE >= insize); - int final2 = final && masterfinal; - size_t size = masterfinal ? insize - i : ZOPFLI_MASTER_BLOCK_SIZE; - ZopfliDeflatePart(options, btype, final2, - in, i, i + size, bp, out, outsize); - i += size; - } -#endif - if (options->verbose) { - fprintf(stderr, - "Original Size: %d, Deflate: %d, Compression: %f%% Removed\n", - (int)insize, (int)*outsize, - 100.0 * (double)(insize - *outsize) / (double)insize); - } -} |