hopfli 0.2.1.1 → 0.2.2.1
raw patch · 26 files changed
+1463/−945 lines, 26 filesdep ~QuickCheckdep ~hspecPVP ok
version bump matches the API change (PVP)
Dependency ranges changed: QuickCheck, hspec
API changes (from Hackage documentation)
Files
- CHANGELOG.md +10/−0
- README.md +5/−2
- hopfli.cabal +8/−7
- src/Codec/Compression/Hopfli.hs +34/−14
- src/Codec/Compression/Hopfli/Raw.hsc +31/−22
- src/cbits/blocksplitter.c +41/−53
- src/cbits/blocksplitter.h +2/−6
- src/cbits/cache.c +6/−0
- src/cbits/deflate.c +608/−376
- src/cbits/deflate.h +8/−2
- src/cbits/gzip_container.c +53/−46
- src/cbits/hash.c +18/−10
- src/cbits/hash.h +10/−7
- src/cbits/katajainen.c +73/−62
- src/cbits/katajainen.h +1/−1
- src/cbits/lz77.c +189/−41
- src/cbits/lz77.h +39/−23
- src/cbits/squeeze.c +75/−61
- src/cbits/squeeze.h +1/−0
- src/cbits/symbols.h +239/−0
- src/cbits/util.c +0/−178
- src/cbits/util.h +6/−23
- src/cbits/zlib_container.c +1/−1
- src/cbits/zopfli.h +1/−4
- src/cbits/zopfli_lib.c +1/−3
- test/HopfliSpec.hs +3/−3
+ CHANGELOG.md view
@@ -0,0 +1,10 @@+# Changelog++## 0.2.2.1+* Relaxed Quickcheck upper bound.++## 0.2.2+* Update Zopfli C files++## 0.2.1.1+* Updated dependency bounds
README.md view
@@ -1,16 +1,19 @@ Hopfli - Haskell bindings to the Zopfli library ===-[](http://travis-ci.org/ananthakumaran/hopfli)-[](http://packdeps.haskellers.com/specific?package=hasmin)+[](https://travis-ci.org/ananthakumaran/hopfli.svg?branch=master)+[](http://packdeps.haskellers.com/specific?package=hopfli) [](https://hackage.haskell.org/package/hopfli) [](https://opensource.org/licenses/Apache-2.0) + Hopfli provides a pure interface to compress data using the Zopfli library. *Zopfli is a compression library released by Google in 2013, which can output either a raw DEFLATE stream, or one wrapped into zlib or gzip formats. Under default settings, the output produced by Zopfli is 3.7–8.3% smaller than that of `gzip -9`, though the algorithm is 81 times slower.*++Zopfli is distributed under the Apache 2.0 license. ## Example
hopfli.cabal view
@@ -1,5 +1,5 @@ name: hopfli-version: 0.2.1.1+version: 0.2.2.1 license: Apache-2.0 license-file: LICENSE author: Anantha Kumaran <ananthakumaran@gmail.com>@@ -11,6 +11,7 @@ build-type: Simple cabal-version: >=1.10 extra-source-files: README.md+ CHANGELOG.md description: Hopfli provides a pure interface to compress data using the Zopfli library algorithm.@@ -24,7 +25,7 @@ default-language: Haskell2010 exposed-modules: Codec.Compression.Hopfli other-modules: Codec.Compression.Hopfli.Raw- ghc-options: -Wall -fwarn-tabs -fwarn-unused-do-bind+ ghc-options: -O2 -Wall -fwarn-tabs -fwarn-unused-do-bind build-depends: base >=4 && <5 , bytestring >=0.9 && <0.12 , zlib >=0.5.4 && <0.7@@ -33,12 +34,12 @@ src/cbits/gzip_container.c src/cbits/hash.c src/cbits/katajainen.c src/cbits/lz77.c src/cbits/squeeze.c src/cbits/tree.c src/cbits/util.c src/cbits/zlib_container.c src/cbits/zopfli_lib.c- includes: blocksplitter.h, cache.h, deflate.h, gzip_container.h, hash.h,- katajainen.h, lz77.h, squeeze.h, tree.h, util.h, zlib_container.h,- zopfli.h+ includes: blocksplitter.h, cache.h, deflate.h, gzip_container.h,+ hash.h, katajainen.h, lz77.h, squeeze.h, tree.h, util.h,+ zlib_container.h, zopfli.h, symbols.h install-includes: blocksplitter.h, cache.h, deflate.h, gzip_container.h, hash.h, katajainen.h, lz77.h, squeeze.h, tree.h, util.h,- zlib_container.h, zopfli.h+ zlib_container.h, zopfli.h, symbols.h test-suite test hs-source-dirs: test@@ -51,5 +52,5 @@ , bytestring >=0.9 && <0.12 , hspec >=1.7.2.1 && <2.5 , zlib >=0.5.4 && <0.7- , QuickCheck >=2.6 && <2.10+ , QuickCheck >=2.6 && <2.11 , hopfli
src/Codec/Compression/Hopfli.hs view
@@ -1,42 +1,62 @@ {-# LANGUAGE RecordWildCards #-}-+-----------------------------------------------------------------------------+-- |+-- Module : Hopfli+-- License : Apache 2.0+-- Copyright : (c) 2014 Anantha Kumaran+-- Stability : experimental+-- Portability : unknown+--+----------------------------------------------------------------------------- module Codec.Compression.Hopfli (- Format(..)+ Format(..) , CompressOptions(..) , VerboseLevel(..) , compressWith , Codec.Compression.Hopfli.compress , defaultCompressOptions , defaultFormat-) where+ ) where import Codec.Compression.Hopfli.Raw as Raw import Data.ByteString+import Data.Bool (bool) import Foreign.C.Types (CInt) -data VerboseLevel = NONE | VERBOSE | VERY_VERBOSE deriving (Show, Eq)+data VerboseLevel = NONE+ | VERBOSE+ | VERY_VERBOSE+ deriving (Show, Eq) data CompressOptions = CompressOptions { verbose :: VerboseLevel , numIterations :: Int , blockSplitting :: Bool , blockSplittingLast :: Bool- , blockSplittingMax :: Int }+ , blockSplittingMax :: Int+ } defaultCompressOptions :: CompressOptions-defaultCompressOptions = CompressOptions { verbose = NONE, numIterations = 10, blockSplitting = True, blockSplittingLast = False, blockSplittingMax = 15 }+defaultCompressOptions =+ CompressOptions { verbose = NONE+ , numIterations = 10+ , blockSplitting = True+ , blockSplittingLast = False+ , blockSplittingMax = 15+ } defaultFormat :: Format defaultFormat = ZLIB -boolToInt :: Bool -> CInt-boolToInt True = 1-boolToInt False = 0- toOptions :: CompressOptions -> Options-toOptions (CompressOptions {..})- = Options verbose' verboseMore (fromIntegral numIterations) (boolToInt blockSplitting) (boolToInt blockSplittingLast) (fromIntegral blockSplittingMax)- where verbose' = boolToInt $ VERBOSE == verbose || VERY_VERBOSE == verbose- verboseMore = boolToInt $ VERY_VERBOSE == verbose+toOptions CompressOptions{..} =+ Options verbose' verboseMore numIterations' blockSplitting' blockSplittingLast' blockSplittingMax'+ where verbose' = boolToInt $ VERBOSE == verbose || VERY_VERBOSE == verbose+ verboseMore = boolToInt $ VERY_VERBOSE == verbose+ numIterations' = fromIntegral numIterations+ blockSplitting' = boolToInt blockSplitting+ blockSplittingLast' = boolToInt blockSplittingLast+ blockSplittingMax' = fromIntegral blockSplittingMax+ boolToInt = bool 0 1 :: Bool -> CInt compressWith :: CompressOptions -> Format -> ByteString -> ByteString compressWith options = Raw.compress (toOptions options)
src/Codec/Compression/Hopfli/Raw.hsc view
@@ -1,10 +1,19 @@ {-# LANGUAGE ForeignFunctionInterface, OverloadedStrings, RecordWildCards #-}+-----------------------------------------------------------------------------+-- |+-- Module : Hopfli.Raw+-- License : Apache 2.0+-- Copyright : (c) 2014 Anantha Kumaran+-- Stability : experimental+-- Portability : unknown+--+----------------------------------------------------------------------------- module Codec.Compression.Hopfli.Raw (- Options(Options)+ Options(Options) , Format(..) , compress-) where+ ) where import qualified Codec.Compression.GZip as G import qualified Codec.Compression.Zlib as Z@@ -26,19 +35,19 @@ , numiterations :: CInt , blocksplitting :: CInt , blocksplittinglast :: CInt- , blocksplittingmax :: CInt } deriving (Show)-+ , blocksplittingmax :: CInt+ } deriving (Show) instance Storable Options where sizeOf _ = (#size ZopfliOptions) alignment _ = alignment (undefined :: CInt) peek ptr = do- verbose <- (#peek ZopfliOptions, verbose) ptr- verbose_more <- (#peek ZopfliOptions, verbose_more) ptr- numiterations <- (#peek ZopfliOptions, numiterations) ptr- blocksplitting <- (#peek ZopfliOptions, blocksplitting) ptr+ verbose <- (#peek ZopfliOptions, verbose) ptr+ verbose_more <- (#peek ZopfliOptions, verbose_more) ptr+ numiterations <- (#peek ZopfliOptions, numiterations) ptr+ blocksplitting <- (#peek ZopfliOptions, blocksplitting) ptr blocksplittinglast <- (#peek ZopfliOptions, blocksplittinglast) ptr- blocksplittingmax <- (#peek ZopfliOptions, blocksplittingmax) ptr- return $ Options{..}+ blocksplittingmax <- (#peek ZopfliOptions, blocksplittingmax) ptr+ pure Options{..} poke ptr (Options verbose' verbose_more' numiterations' blocksplitting' blocksplittinglast' blocksplittingmax') = do (#poke ZopfliOptions, verbose) ptr verbose' (#poke ZopfliOptions, verbose_more) ptr verbose_more'@@ -47,26 +56,27 @@ (#poke ZopfliOptions, blocksplittinglast) ptr blocksplittinglast' (#poke ZopfliOptions, blocksplittingmax) ptr blocksplittingmax' -data Format = GZIP | ZLIB | DEFLATE deriving (Show, Eq)+data Format = GZIP+ | ZLIB+ | DEFLATE+ deriving (Eq, Show) newtype ZopfliFormat = ZopfliFormat CInt fromFormat :: Format -> ZopfliFormat-fromFormat GZIP = ZopfliFormat #{const ZOPFLI_FORMAT_GZIP}-fromFormat ZLIB = ZopfliFormat #{const ZOPFLI_FORMAT_ZLIB}+fromFormat GZIP = ZopfliFormat #{const ZOPFLI_FORMAT_GZIP}+fromFormat ZLIB = ZopfliFormat #{const ZOPFLI_FORMAT_ZLIB} fromFormat DEFLATE = ZopfliFormat #{const ZOPFLI_FORMAT_DEFLATE} - foreign import ccall unsafe "zopfli.h ZopfliCompress"- c_zopfli_compress :: Ptr Options -> ZopfliFormat -> Ptr Word8 -> CSize -> Ptr (Ptr Word8) -> Ptr CSize -> IO ()-+ c_zopfli_compress :: Ptr Options -> ZopfliFormat -> Ptr Word8 -> CSize+ -> Ptr (Ptr Word8) -> Ptr CSize -> IO () compress :: Options -> Format -> B.ByteString -> B.ByteString -- zopfli doesn't handle zero length data-compress _ GZIP "" = B.concat . BL.toChunks $ G.compress ""-compress _ ZLIB "" = B.concat . BL.toChunks $ Z.compress ""-compress _ DEFLATE "" = B.concat . BL.toChunks $ ZR.compress ""-+compress _ GZIP "" = mconcat . BL.toChunks $ G.compress ""+compress _ ZLIB "" = mconcat . BL.toChunks $ Z.compress ""+compress _ DEFLATE "" = mconcat . BL.toChunks $ ZR.compress "" compress options format input = unsafePerformIO $ do let (inputFptr, start, length) = toForeignPtr input withForeignPtr inputFptr $ \inputPtr -> do@@ -80,5 +90,4 @@ outSize <- peek outSizePtr resultPtr <- throwIfNull "Zopfli compression failed" (peek outPtrPtr) resultFptr <- newForeignPtr finalizerFree resultPtr- return $ fromForeignPtr resultFptr 0 (fromIntegral outSize)-+ pure $ fromForeignPtr resultFptr 0 (fromIntegral outSize)
src/cbits/blocksplitter.c view
@@ -24,7 +24,6 @@ #include <stdlib.h> #include "deflate.h"-#include "lz77.h" #include "squeeze.h" #include "tree.h" #include "util.h"@@ -39,9 +38,10 @@ /* Finds minimum of function f(i) where is is of type size_t, f(i) is of type double, i is in range start-end (excluding end).+Outputs the minimum value in *smallest and returns the index of this value. */ static size_t FindMinimum(FindMinimumFun f, void* context,- size_t start, size_t end) {+ size_t start, size_t end, double* smallest) { if (end - start < 1024) { double best = ZOPFLI_LARGE_FLOAT; size_t result = start;@@ -53,6 +53,7 @@ result = i; } }+ *smallest = best; return result; } else { /* Try to find minimum faster by recursively checking multiple points. */@@ -88,6 +89,7 @@ pos = p[besti]; lastbest = best; }+ *smallest = lastbest; return pos; #undef NUM }@@ -103,16 +105,13 @@ lstart: start of block lend: end of block (not inclusive) */-static double EstimateCost(const unsigned short* litlens,- const unsigned short* dists,+static double EstimateCost(const ZopfliLZ77Store* lz77, size_t lstart, size_t lend) {- return ZopfliCalculateBlockSize(litlens, dists, lstart, lend, 2);+ return ZopfliCalculateBlockSizeAutoType(lz77, lstart, lend); } typedef struct SplitCostContext {- const unsigned short* litlens;- const unsigned short* dists;- size_t llsize;+ const ZopfliLZ77Store* lz77; size_t start; size_t end; } SplitCostContext;@@ -125,23 +124,20 @@ */ static double SplitCost(size_t i, void* context) { SplitCostContext* c = (SplitCostContext*)context;- return EstimateCost(c->litlens, c->dists, c->start, i) +- EstimateCost(c->litlens, c->dists, i, c->end);+ return EstimateCost(c->lz77, c->start, i) + EstimateCost(c->lz77, i, c->end); } static void AddSorted(size_t value, size_t** out, size_t* outsize) { size_t i; ZOPFLI_APPEND_DATA(value, out, outsize);- if (*outsize > 0) {- for (i = 0; i < *outsize - 1; i++) {- if ((*out)[i] > value) {- size_t j;- for (j = *outsize - 1; j > i; j--) {- (*out)[j] = (*out)[j - 1];- }- (*out)[i] = value;- break;+ for (i = 0; i + 1 < *outsize; i++) {+ if ((*out)[i] > value) {+ size_t j;+ for (j = *outsize - 1; j > i; j--) {+ (*out)[j] = (*out)[j - 1]; }+ (*out)[i] = value;+ break; } } }@@ -149,9 +145,8 @@ /* Prints the block split points as decimal and hex values in the terminal. */-static void PrintBlockSplitPoints(const unsigned short* litlens,- const unsigned short* dists,- size_t llsize, const size_t* lz77splitpoints,+static void PrintBlockSplitPoints(const ZopfliLZ77Store* lz77,+ const size_t* lz77splitpoints, size_t nlz77points) { size_t* splitpoints = 0; size_t npoints = 0;@@ -160,8 +155,8 @@ index values. */ size_t pos = 0; if (nlz77points > 0) {- for (i = 0; i < llsize; i++) {- size_t length = dists[i] == 0 ? 1 : litlens[i];+ for (i = 0; i < lz77->size; i++) {+ size_t length = lz77->dists[i] == 0 ? 1 : lz77->litlens[i]; if (lz77splitpoints[npoints] == i) { ZOPFLI_APPEND_DATA(pos, &splitpoints, &npoints); if (npoints == nlz77points) break;@@ -188,7 +183,7 @@ Finds next block to try to split, the largest of the available ones. The largest is chosen to make sure that if only a limited amount of blocks is requested, their sizes are spread evenly.-llsize: the size of the LL77 data, which is the size of the done array here.+lz77size: the size of the LL77 data, which is the size of the done array here. done: array indicating which blocks starting at that position are no longer splittable (splitting them increases rather than decreases cost). splitpoints: the splitpoints found so far.@@ -198,7 +193,7 @@ returns 1 if a block was found, 0 if no block found (all are done). */ static int FindLargestSplittableBlock(- size_t llsize, const unsigned char* done,+ size_t lz77size, const unsigned char* done, const size_t* splitpoints, size_t npoints, size_t* lstart, size_t* lend) { size_t longest = 0;@@ -206,7 +201,7 @@ size_t i; for (i = 0; i <= npoints; i++) { size_t start = i == 0 ? 0 : splitpoints[i - 1];- size_t end = i == npoints ? llsize - 1 : splitpoints[i];+ size_t end = i == npoints ? lz77size - 1 : splitpoints[i]; if (!done[start] && end - start > longest) { *lstart = start; *lend = end;@@ -218,9 +213,7 @@ } void ZopfliBlockSplitLZ77(const ZopfliOptions* options,- const unsigned short* litlens,- const unsigned short* dists,- size_t llsize, size_t maxblocks,+ const ZopfliLZ77Store* lz77, size_t maxblocks, size_t** splitpoints, size_t* npoints) { size_t lstart, lend; size_t i;@@ -229,14 +222,14 @@ unsigned char* done; double splitcost, origcost; - if (llsize < 10) return; /* This code fails on tiny files. */+ if (lz77->size < 10) return; /* This code fails on tiny files. */ - done = (unsigned char*)malloc(llsize);+ done = (unsigned char*)malloc(lz77->size); if (!done) exit(-1); /* Allocation failed. */- for (i = 0; i < llsize; i++) done[i] = 0;+ for (i = 0; i < lz77->size; i++) done[i] = 0; lstart = 0;- lend = llsize;+ lend = lz77->size; for (;;) { SplitCostContext c; @@ -244,20 +237,16 @@ break; } - c.litlens = litlens;- c.dists = dists;- c.llsize = llsize;+ c.lz77 = lz77; c.start = lstart; c.end = lend; assert(lstart < lend);- llpos = FindMinimum(SplitCost, &c, lstart + 1, lend);+ llpos = FindMinimum(SplitCost, &c, lstart + 1, lend, &splitcost); assert(llpos > lstart); assert(llpos < lend); - splitcost = EstimateCost(litlens, dists, lstart, llpos) +- EstimateCost(litlens, dists, llpos, lend);- origcost = EstimateCost(litlens, dists, lstart, lend);+ origcost = EstimateCost(lz77, lstart, lend); if (splitcost > origcost || llpos == lstart + 1 || llpos == lend) { done[lstart] = 1;@@ -267,7 +256,7 @@ } if (!FindLargestSplittableBlock(- llsize, done, *splitpoints, *npoints, &lstart, &lend)) {+ lz77->size, done, *splitpoints, *npoints, &lstart, &lend)) { break; /* No further split will probably reduce compression. */ } @@ -277,7 +266,7 @@ } if (options->verbose) {- PrintBlockSplitPoints(litlens, dists, llsize, *splitpoints, *npoints);+ PrintBlockSplitPoints(lz77, *splitpoints, *npoints); } free(done);@@ -292,25 +281,22 @@ size_t* lz77splitpoints = 0; size_t nlz77points = 0; ZopfliLZ77Store store;-- ZopfliInitLZ77Store(&store);+ ZopfliHash hash;+ ZopfliHash* h = &hash; - s.options = options;- s.blockstart = instart;- s.blockend = inend;-#ifdef ZOPFLI_LONGEST_MATCH_CACHE- s.lmc = 0;-#endif+ ZopfliInitLZ77Store(in, &store);+ ZopfliInitBlockState(options, instart, inend, 0, &s);+ ZopfliAllocHash(ZOPFLI_WINDOW_SIZE, h); *npoints = 0; *splitpoints = 0; /* Unintuitively, Using a simple LZ77 method here instead of ZopfliLZ77Optimal results in better blocks. */- ZopfliLZ77Greedy(&s, in, instart, inend, &store);+ ZopfliLZ77Greedy(&s, in, instart, inend, &store, h); ZopfliBlockSplitLZ77(options,- store.litlens, store.dists, store.size, maxblocks,+ &store, maxblocks, &lz77splitpoints, &nlz77points); /* Convert LZ77 positions to positions in the uncompressed input. */@@ -328,7 +314,9 @@ assert(*npoints == nlz77points); free(lz77splitpoints);+ ZopfliCleanBlockState(&s); ZopfliCleanLZ77Store(&store);+ ZopfliCleanHash(h); } void ZopfliBlockSplitSimple(const unsigned char* in,
src/cbits/blocksplitter.h view
@@ -30,21 +30,17 @@ #include <stdlib.h> +#include "lz77.h" #include "zopfli.h" /* Does blocksplitting on LZ77 data. The output splitpoints are indices in the LZ77 data.-litlens: lz77 lit/lengths-dists: lz77 distances-llsize: size of litlens and dists maxblocks: set a limit to the amount of blocks. Set to 0 to mean no limit. */ void ZopfliBlockSplitLZ77(const ZopfliOptions* options,- const unsigned short* litlens,- const unsigned short* dists,- size_t llsize, size_t maxblocks,+ const ZopfliLZ77Store* lz77, size_t maxblocks, size_t** splitpoints, size_t* npoints); /*
src/cbits/cache.c view
@@ -31,6 +31,12 @@ lmc->dist = (unsigned short*)malloc(sizeof(unsigned short) * blocksize); /* Rather large amount of memory. */ lmc->sublen = (unsigned char*)malloc(ZOPFLI_CACHE_LENGTH * 3 * blocksize);+ if(lmc->sublen == NULL) {+ fprintf(stderr,+ "Error: Out of memory. Tried allocating %lu bytes of memory.\n",+ ZOPFLI_CACHE_LENGTH * 3 * blocksize);+ exit (EXIT_FAILURE);+ } /* length > 0 and dist 0 is invalid combination, which indicates on purpose that this cache value is not filled in yet. */
src/cbits/deflate.c view
@@ -24,15 +24,22 @@ #include <stdlib.h> #include "blocksplitter.h"-#include "lz77.h" #include "squeeze.h"+#include "symbols.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) & 7) == 0) ZOPFLI_APPEND_DATA(0, out, outsize);- (*out)[*outsize - 1] |= bit << ((*bp) & 7);- (*bp)++;+ 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,@@ -41,9 +48,9 @@ unsigned i; for (i = 0; i < length; i++) { unsigned bit = (symbol >> i) & 1;- if (((*bp) & 7) == 0) ZOPFLI_APPEND_DATA(0, out, outsize);- (*out)[*outsize - 1] |= bit << ((*bp) & 7);- (*bp)++;+ if (*bp == 0) ZOPFLI_APPEND_DATA(0, out, outsize);+ (*out)[*outsize - 1] |= bit << *bp;+ *bp = (*bp + 1) & 7; } } @@ -58,9 +65,9 @@ unsigned i; for (i = 0; i < length; i++) { unsigned bit = (symbol >> (length - i - 1)) & 1;- if (((*bp) & 7) == 0) ZOPFLI_APPEND_DATA(0, out, outsize);- (*out)[*outsize - 1] |= bit << ((*bp) & 7);- (*bp)++;+ if (*bp == 0) ZOPFLI_APPEND_DATA(0, out, outsize);+ (*out)[*outsize - 1] |= bit << *bp;+ *bp = (*bp + 1) & 7; } } @@ -91,141 +98,195 @@ } } -static void AddDynamicTree(const unsigned* ll_lengths,- const unsigned* d_lengths,- unsigned char* bp,- unsigned char** out, size_t* outsize) {- unsigned* lld_lengths = 0; /* All litlen and dist lengthts with ending zeros- trimmed together in one array. */- unsigned lld_total; /* Size of lld_lengths. */- unsigned* rle = 0; /* Runlength encoded version of lengths of litlen and dist- trees. */+/*+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 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. */- unsigned order[19] = {+ 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--;-- lld_total = hlit + 257 + hdist + 1;- lld_lengths = (unsigned*)malloc(sizeof(*lld_lengths) * lld_total);- if (!lld_lengths) exit(-1); /* Allocation failed. */+ hlit2 = hlit + 257; - for (i = 0; i < lld_total; i++) {- lld_lengths[i] = i < 257 + hlit- ? ll_lengths[i] : d_lengths[i - 257 - hlit];- assert(lld_lengths[i] < 16);- }+ lld_total = hlit2 + hdist + 1; for (i = 0; i < lld_total; i++) {- size_t count = 0;- for (j = i; j < lld_total && lld_lengths[i] == lld_lengths[j]; j++) {- count++;+ /* 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++;+ } }- if (count >= 4 || (count >= 3 && lld_lengths[i] == 0)) {- if (lld_lengths[i] == 0) {- if (count > 10) {- if (count > 138) count = 138;- ZOPFLI_APPEND_DATA(18, &rle, &rle_size);- ZOPFLI_APPEND_DATA(count - 11, &rle_bits, &rle_bits_size);- } else {- ZOPFLI_APPEND_DATA(17, &rle, &rle_size);- ZOPFLI_APPEND_DATA(count - 3, &rle_bits, &rle_bits_size);+ 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; }- } else {- unsigned repeat = count - 1; /* Since the first one is hardcoded. */- ZOPFLI_APPEND_DATA(lld_lengths[i], &rle, &rle_size);- ZOPFLI_APPEND_DATA(0, &rle_bits, &rle_bits_size);- while (repeat >= 6) {- ZOPFLI_APPEND_DATA(16, &rle, &rle_size);- ZOPFLI_APPEND_DATA(6 - 3, &rle_bits, &rle_bits_size);- repeat -= 6;+ }+ 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; }- if (repeat >= 3) {+ }+ }++ /* 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(repeat - 3, &rle_bits, &rle_bits_size);- repeat = 0;- }- while (repeat != 0) {- ZOPFLI_APPEND_DATA(lld_lengths[i], &rle, &rle_size);- ZOPFLI_APPEND_DATA(0, &rle_bits, &rle_bits_size);- repeat--;+ ZOPFLI_APPEND_DATA(count2 - 3, &rle_bits, &rle_bits_size); }+ clcounts[16]++;+ count -= count2; }-- i += count - 1;- } else {- ZOPFLI_APPEND_DATA(lld_lengths[i], &rle, &rle_size);- ZOPFLI_APPEND_DATA(0, &rle_bits, &rle_bits_size); }- assert(rle[rle_size - 1] <= 18);- } - for (i = 0; i < 19; i++) {- clcounts[i] = 0;- }- for (i = 0; i < rle_size; i++) {- clcounts[rle[i]]++;+ /* 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);- ZopfliLengthsToSymbols(clcl, 19, 7, clsymbols);+ if (!size_only) ZopfliLengthsToSymbols(clcl, 19, 7, clsymbols); hclen = 15; /* Trim zeros. */ while (hclen > 0 && clcounts[order[hclen + 4 - 1]] == 0) hclen--; - AddBits(hlit, 5, bp, out, outsize);- AddBits(hdist, 5, bp, out, outsize);- AddBits(hclen, 4, bp, out, outsize);+ 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 < 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);+ } } - 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; - free(lld_lengths);+ /* 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* ll_counts, size_t* d_counts) {- unsigned char* dummy = 0;- size_t dummysize = 0;- unsigned char bp = 0;-- (void)ll_counts;- (void)d_counts;+ const unsigned* d_lengths) {+ size_t result = 0;+ int i; - AddDynamicTree(ll_lengths, d_lengths, &bp, &dummy, &dummysize);- free(dummy);+ 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 dummysize * 8 + (bp & 7);+ return result; } /*@@ -233,8 +294,7 @@ 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,+static void AddLZ77Data(const ZopfliLZ77Store* lz77, size_t lstart, size_t lend, size_t expected_data_size, const unsigned* ll_symbols, const unsigned* ll_lengths,@@ -245,8 +305,8 @@ size_t i; for (i = lstart; i < lend; i++) {- unsigned dist = dists[i];- unsigned litlen = litlens[i];+ unsigned dist = lz77->dists[i];+ unsigned litlen = lz77->litlens[i]; if (dist == 0) { assert(litlen < 256); assert(ll_lengths[litlen] > 0);@@ -282,58 +342,326 @@ } /*-Calculates size of the part after the header and tree of an LZ77 block, in bits.+Same as CalculateBlockSymbolSize, but for block size smaller than histogram+size. */-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) {+static size_t CalculateBlockSymbolSizeSmall(const unsigned* ll_lengths,+ const unsigned* d_lengths,+ const ZopfliLZ77Store* lz77,+ 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]];+ assert(i < lz77->size);+ assert(lz77->litlens[i] < 259);+ if (lz77->dists[i] == 0) {+ result += ll_lengths[lz77->litlens[i]]; } else {- result += ll_lengths[ZopfliGetLengthSymbol(litlens[i])];- result += d_lengths[ZopfliGetDistSymbol(dists[i])];- result += ZopfliGetLengthExtraBits(litlens[i]);- result += ZopfliGetDistExtraBits(dists[i]);+ int ll_symbol = ZopfliGetLengthSymbol(lz77->litlens[i]);+ int d_symbol = ZopfliGetDistSymbol(lz77->dists[i]);+ result += ll_lengths[ll_symbol];+ result += d_lengths[d_symbol];+ result += ZopfliGetLengthSymbolExtraBits(ll_symbol);+ result += ZopfliGetDistSymbolExtraBits(d_symbol); } } result += ll_lengths[256]; /*end symbol*/ return result; } -double ZopfliCalculateBlockSize(const unsigned short* litlens,- const unsigned short* dists,- size_t lstart, size_t lend, int btype) {- size_t ll_counts[288];- size_t d_counts[32];+/*+Same as CalculateBlockSymbolSize, but with the histogram provided by the caller.+*/+static size_t CalculateBlockSymbolSizeGivenCounts(const size_t* ll_counts,+ const size_t* d_counts,+ const unsigned* ll_lengths,+ const unsigned* d_lengths,+ const ZopfliLZ77Store* lz77,+ size_t lstart, size_t lend) {+ size_t result = 0;+ size_t i;+ if (lstart + ZOPFLI_NUM_LL * 3 > lend) {+ return CalculateBlockSymbolSizeSmall(+ ll_lengths, d_lengths, lz77, lstart, lend);+ } else {+ for (i = 0; i < 256; i++) {+ result += ll_lengths[i] * ll_counts[i];+ }+ for (i = 257; i < 286; i++) {+ result += ll_lengths[i] * ll_counts[i];+ result += ZopfliGetLengthSymbolExtraBits(i) * ll_counts[i];+ }+ for (i = 0; i < 30; i++) {+ result += d_lengths[i] * d_counts[i];+ result += ZopfliGetDistSymbolExtraBits(i) * d_counts[i];+ }+ result += ll_lengths[256]; /*end symbol*/+ return result;+ }+} - unsigned ll_lengths[288];- unsigned d_lengths[32];+/*+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 ZopfliLZ77Store* lz77,+ size_t lstart, size_t lend) {+ if (lstart + ZOPFLI_NUM_LL * 3 > lend) {+ return CalculateBlockSymbolSizeSmall(+ ll_lengths, d_lengths, lz77, lstart, lend);+ } else {+ size_t ll_counts[ZOPFLI_NUM_LL];+ size_t d_counts[ZOPFLI_NUM_D];+ ZopfliLZ77GetHistogram(lz77, lstart, lend, ll_counts, d_counts);+ return CalculateBlockSymbolSizeGivenCounts(+ ll_counts, d_counts, ll_lengths, d_lengths, lz77, lstart, lend);+ }+} - double result = 3; /*bfinal and btype bits*/+static size_t AbsDiff(size_t x, size_t y) {+ if (x > y)+ return x - y;+ else+ return y - x;+} - assert(btype == 1 || btype == 2); /* This is not for uncompressed blocks. */+/*+Changes the population counts in a way that the consequent Huffman tree+compression, especially its rle-part, will be more likely to compress this data+more efficiently. length contains 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; - if(btype == 1) {+ /* 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);+}++/*+Tries out OptimizeHuffmanForRle for this block, if the result is smaller,+uses it, otherwise keeps the original. Returns size of encoded tree and data in+bits, not including the 3-bit block header.+*/+static double TryOptimizeHuffmanForRle(+ const ZopfliLZ77Store* lz77, size_t lstart, size_t lend,+ const size_t* ll_counts, const size_t* d_counts,+ unsigned* ll_lengths, unsigned* d_lengths) {+ size_t ll_counts2[ZOPFLI_NUM_LL];+ size_t d_counts2[ZOPFLI_NUM_D];+ unsigned ll_lengths2[ZOPFLI_NUM_LL];+ unsigned d_lengths2[ZOPFLI_NUM_D];+ double treesize;+ double datasize;+ double treesize2;+ double datasize2;++ treesize = CalculateTreeSize(ll_lengths, d_lengths);+ datasize = CalculateBlockSymbolSizeGivenCounts(ll_counts, d_counts,+ ll_lengths, d_lengths, lz77, lstart, lend);++ memcpy(ll_counts2, ll_counts, sizeof(ll_counts2));+ memcpy(d_counts2, d_counts, sizeof(d_counts2));+ OptimizeHuffmanForRle(ZOPFLI_NUM_LL, ll_counts2);+ OptimizeHuffmanForRle(ZOPFLI_NUM_D, d_counts2);+ ZopfliCalculateBitLengths(ll_counts2, ZOPFLI_NUM_LL, 15, ll_lengths2);+ ZopfliCalculateBitLengths(d_counts2, ZOPFLI_NUM_D, 15, d_lengths2);+ PatchDistanceCodesForBuggyDecoders(d_lengths2);++ treesize2 = CalculateTreeSize(ll_lengths2, d_lengths2);+ datasize2 = CalculateBlockSymbolSizeGivenCounts(ll_counts, d_counts,+ ll_lengths2, d_lengths2, lz77, lstart, lend);++ if (treesize2 + datasize2 < treesize + datasize) {+ memcpy(ll_lengths, ll_lengths2, sizeof(ll_lengths2));+ memcpy(d_lengths, d_lengths2, sizeof(d_lengths2));+ return treesize2 + datasize2;+ }+ return treesize + datasize;+}++/*+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. Returns size of encoded tree and data in bits, not including the+3-bit block header.+*/+static double GetDynamicLengths(const ZopfliLZ77Store* lz77,+ size_t lstart, size_t lend,+ unsigned* ll_lengths, unsigned* d_lengths) {+ size_t ll_counts[ZOPFLI_NUM_LL];+ size_t d_counts[ZOPFLI_NUM_D];++ ZopfliLZ77GetHistogram(lz77, lstart, lend, ll_counts, d_counts);+ ll_counts[256] = 1; /* End symbol. */+ ZopfliCalculateBitLengths(ll_counts, ZOPFLI_NUM_LL, 15, ll_lengths);+ ZopfliCalculateBitLengths(d_counts, ZOPFLI_NUM_D, 15, d_lengths);+ PatchDistanceCodesForBuggyDecoders(d_lengths);+ return TryOptimizeHuffmanForRle(+ lz77, lstart, lend, ll_counts, d_counts, ll_lengths, d_lengths);+}++double ZopfliCalculateBlockSize(const ZopfliLZ77Store* lz77,+ size_t lstart, size_t lend, int btype) {+ unsigned ll_lengths[ZOPFLI_NUM_LL];+ unsigned d_lengths[ZOPFLI_NUM_D];++ double result = 3; /* bfinal and btype bits */++ if (btype == 0) {+ size_t length = ZopfliLZ77GetByteRange(lz77, lstart, lend);+ size_t rem = length % 65535;+ size_t blocks = length / 65535 + (rem ? 1 : 0);+ /* An uncompressed block must actually be split into multiple blocks if it's+ larger than 65535 bytes long. Eeach block header is 5 bytes: 3 bits,+ padding, LEN and NLEN (potential less padding for first one ignored). */+ return blocks * 5 * 8 + length * 8;+ } if (btype == 1) { GetFixedTree(ll_lengths, d_lengths);+ result += CalculateBlockSymbolSize(+ ll_lengths, d_lengths, lz77, lstart, lend); } else {- ZopfliLZ77Counts(litlens, dists, lstart, lend, ll_counts, d_counts);- ZopfliCalculateBitLengths(ll_counts, 288, 15, ll_lengths);- ZopfliCalculateBitLengths(d_counts, 32, 15, d_lengths);- PatchDistanceCodesForBuggyDecoders(d_lengths);- result += CalculateTreeSize(ll_lengths, d_lengths, ll_counts, d_counts);+ result += GetDynamicLengths(lz77, lstart, lend, ll_lengths, d_lengths); } - result += CalculateBlockSymbolSize(- ll_lengths, d_lengths, litlens, dists, lstart, lend);- return result; } +double ZopfliCalculateBlockSizeAutoType(const ZopfliLZ77Store* lz77,+ size_t lstart, size_t lend) {+ double uncompressedcost = ZopfliCalculateBlockSize(lz77, lstart, lend, 0);+ /* Don't do the expensive fixed cost calculation for larger blocks that are+ unlikely to use it. */+ double fixedcost = (lz77->size > 1000) ?+ uncompressedcost : ZopfliCalculateBlockSize(lz77, lstart, lend, 1);+ double dyncost = ZopfliCalculateBlockSize(lz77, lstart, lend, 2);+ return (uncompressedcost < fixedcost && uncompressedcost < dyncost)+ ? uncompressedcost+ : (fixedcost < dyncost ? fixedcost : dyncost);+}++/* Since an uncompressed block can be max 65535 in size, it actually adds+multible blocks if needed. */+static void AddNonCompressedBlock(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 pos = instart;+ (void)options;+ for (;;) {+ size_t i;+ unsigned short blocksize = 65535;+ unsigned short nlen;+ int currentfinal;++ if (pos + blocksize > inend) blocksize = inend - pos;+ currentfinal = pos + blocksize >= inend;++ nlen = ~blocksize;++ AddBit(final && currentfinal, 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 = 0; i < blocksize; i++) {+ ZOPFLI_APPEND_DATA(in[pos + i], out, outsize);+ }++ if (currentfinal) break;+ pos += blocksize;+ }+}+ /* Adds a deflate block with the given LZ77 data to the output. options: global program options@@ -352,22 +680,27 @@ outsize: dynamic output array size */ static void AddLZ77Block(const ZopfliOptions* options, int btype, int final,- const unsigned short* litlens,- const unsigned short* dists,+ const ZopfliLZ77Store* lz77, size_t lstart, size_t lend, size_t expected_data_size, unsigned char* bp, unsigned char** out, size_t* outsize) {- size_t ll_counts[288];- size_t d_counts[32];- unsigned ll_lengths[288];- unsigned d_lengths[32];- unsigned ll_symbols[288];- unsigned d_symbols[32];+ unsigned ll_lengths[ZOPFLI_NUM_LL];+ unsigned d_lengths[ZOPFLI_NUM_D];+ unsigned ll_symbols[ZOPFLI_NUM_LL];+ unsigned d_symbols[ZOPFLI_NUM_D]; size_t detect_block_size = *outsize; size_t compressed_size; size_t uncompressed_size = 0; size_t i;+ if (btype == 0) {+ size_t length = ZopfliLZ77GetByteRange(lz77, lstart, lend);+ size_t pos = lstart == lend ? 0 : lz77->pos[lstart];+ size_t end = pos + length;+ AddNonCompressedBlock(options, final,+ lz77->data, pos, end, bp, out, outsize);+ return;+ } AddBit(final, bp, out, outsize); AddBit(btype & 1, bp, out, outsize);@@ -380,34 +713,28 @@ /* Dynamic block. */ unsigned detect_tree_size; assert(btype == 2);- ZopfliLZ77Counts(litlens, dists, lstart, lend, ll_counts, d_counts);- ZopfliCalculateBitLengths(ll_counts, 288, 15, ll_lengths);- ZopfliCalculateBitLengths(d_counts, 32, 15, d_lengths);- PatchDistanceCodesForBuggyDecoders(d_lengths);++ GetDynamicLengths(lz77, 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)); }-- /* Assert that for every present symbol, the code length is non-zero. */- /* TODO(lode): remove this in release version. */- for (i = 0; i < 288; i++) assert(ll_counts[i] == 0 || ll_lengths[i] > 0);- for (i = 0; i < 32; i++) assert(d_counts[i] == 0 || d_lengths[i] > 0); } - ZopfliLengthsToSymbols(ll_lengths, 288, 15, ll_symbols);- ZopfliLengthsToSymbols(d_lengths, 32, 15, d_symbols);+ ZopfliLengthsToSymbols(ll_lengths, ZOPFLI_NUM_LL, 15, ll_symbols);+ ZopfliLengthsToSymbols(d_lengths, ZOPFLI_NUM_D, 15, d_symbols); detect_block_size = *outsize;- AddLZ77Data(litlens, dists, lstart, lend, expected_data_size,+ AddLZ77Data(lz77, 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];+ uncompressed_size += lz77->dists[i] == 0 ? 1 : lz77->litlens[i]; } compressed_size = *outsize - detect_block_size; if (options->verbose) {@@ -417,283 +744,188 @@ } } -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+static void AddLZ77BlockAutoType(const ZopfliOptions* options, int final,+ const ZopfliLZ77Store* lz77,+ size_t lstart, size_t lend,+ size_t expected_data_size,+ unsigned char* bp,+ unsigned char** out, size_t* outsize) {+ double uncompressedcost = ZopfliCalculateBlockSize(lz77, lstart, lend, 0);+ double fixedcost = ZopfliCalculateBlockSize(lz77, lstart, lend, 1);+ double dyncost = ZopfliCalculateBlockSize(lz77, lstart, lend, 2); - ZopfliLZ77Optimal(&s, in, instart, inend, &store);+ /* Whether to perform the expensive calculation of creating an optimal block+ with fixed huffman tree to check if smaller. Only do this for small blocks or+ blocks which already are pretty good with fixed huffman tree. */+ int expensivefixed = (lz77->size < 1000) || fixedcost <= dyncost * 1.1; - /* 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);- }+ ZopfliLZ77Store fixedstore;+ if (lstart == lend) {+ /* Smallest empty block is represented by fixed block */+ AddBits(final, 1, bp, out, outsize);+ AddBits(1, 2, bp, out, outsize); /* btype 01 */+ AddBits(0, 7, bp, out, outsize); /* end symbol has code 0000000 */+ return; }-- 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);+ ZopfliInitLZ77Store(lz77->data, &fixedstore);+ if (expensivefixed) {+ /* Recalculate the LZ77 with ZopfliLZ77OptimalFixed */+ size_t instart = lz77->pos[lstart];+ size_t inend = instart + ZopfliLZ77GetByteRange(lz77, lstart, lend); - for (i = instart; i < inend; i++) {- ZOPFLI_APPEND_DATA(in[i], out, outsize);+ ZopfliBlockState s;+ ZopfliInitBlockState(options, instart, inend, 1, &s);+ ZopfliLZ77OptimalFixed(&s, lz77->data, instart, inend, &fixedstore);+ fixedcost = ZopfliCalculateBlockSize(&fixedstore, 0, fixedstore.size, 1);+ ZopfliCleanBlockState(&s); }-} -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);+ if (uncompressedcost < fixedcost && uncompressedcost < dyncost) {+ AddLZ77Block(options, 0, final, lz77, lstart, lend,+ expected_data_size, bp, out, outsize);+ } else if (fixedcost < dyncost) {+ if (expensivefixed) {+ AddLZ77Block(options, 1, final, &fixedstore, 0, fixedstore.size,+ expected_data_size, bp, out, outsize);+ } else {+ AddLZ77Block(options, 1, final, lz77, lstart, lend,+ expected_data_size, bp, out, outsize);+ } } else {- assert (btype == 2);- DeflateDynamicBlock(options, final, in, instart, inend, bp, out, outsize);+ AddLZ77Block(options, 2, final, lz77, lstart, lend,+ expected_data_size, bp, out, outsize); }++ ZopfliCleanLZ77Store(&fixedstore); } /*-Does squeeze strategy where first block splitting is done, then each block is-squeezed.-Parameters: see description of the ZopfliDeflate function.+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. */-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) {+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) { size_t i;- size_t* splitpoints = 0;+ /* byte coordinates rather than lz77 index */+ size_t* splitpoints_uncompressed = 0; size_t npoints = 0;+ size_t* splitpoints = 0;+ double totalcost = 0;+ ZopfliLZ77Store lz77;++ /* If btype=2 is specified, it tries all block types. If a lesser btype is+ given, then however it forces that one. Neither of the lesser types needs+ block splitting as they have no dynamic huffman trees. */ if (btype == 0) {- ZopfliBlockSplitSimple(in, instart, inend, 65535, &splitpoints, &npoints);+ AddNonCompressedBlock(options, final, in, instart, inend, bp, out, outsize);+ return; } 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);- }+ ZopfliLZ77Store store;+ ZopfliBlockState s;+ ZopfliInitLZ77Store(in, &store);+ ZopfliInitBlockState(options, instart, inend, 1, &s); - 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,+ ZopfliLZ77OptimalFixed(&s, in, instart, inend, &store);+ AddLZ77Block(options, btype, final, &store, 0, store.size, 0, bp, out, outsize);++ ZopfliCleanBlockState(&s);+ ZopfliCleanLZ77Store(&store);+ return; } - 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);+ if (options->blocksplitting) {+ ZopfliBlockSplit(options, in, instart, inend,+ options->blocksplittingmax,+ &splitpoints_uncompressed, &npoints);+ splitpoints = (size_t*)malloc(sizeof(*splitpoints) * npoints); }- assert(btype == 1 || btype == 2); - ZopfliInitLZ77Store(&store);+ ZopfliInitLZ77Store(in, &lz77); - 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+ for (i = 0; i <= npoints; i++) {+ size_t start = i == 0 ? instart : splitpoints_uncompressed[i - 1];+ size_t end = i == npoints ? inend : splitpoints_uncompressed[i];+ ZopfliBlockState s;+ ZopfliLZ77Store store;+ ZopfliInitLZ77Store(in, &store);+ ZopfliInitBlockState(options, start, end, 1, &s);+ ZopfliLZ77Optimal(&s, in, start, end, options->numiterations, &store);+ totalcost += ZopfliCalculateBlockSizeAutoType(&store, 0, store.size); - if (btype == 2) {- ZopfliLZ77Optimal(&s, in, instart, inend, &store);- } else {- assert (btype == 1);- ZopfliLZ77OptimalFixed(&s, in, instart, inend, &store);- }+ ZopfliAppendLZ77Store(&store, &lz77);+ if (i < npoints) splitpoints[i] = lz77.size; - 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);+ ZopfliCleanBlockState(&s);+ ZopfliCleanLZ77Store(&store); } - 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);- }+ /* Second block splitting attempt */+ if (options->blocksplitting && npoints > 1) {+ size_t* splitpoints2 = 0;+ size_t npoints2 = 0;+ double totalcost2 = 0; -#ifdef ZOPFLI_LONGEST_MATCH_CACHE- ZopfliCleanCache(s.lmc);- free(s.lmc);-#endif+ ZopfliBlockSplitLZ77(options, &lz77,+ options->blocksplittingmax, &splitpoints2, &npoints2); - ZopfliCleanLZ77Store(&store);-}+ for (i = 0; i <= npoints2; i++) {+ size_t start = i == 0 ? 0 : splitpoints2[i - 1];+ size_t end = i == npoints2 ? lz77.size : splitpoints2[i];+ totalcost2 += ZopfliCalculateBlockSizeAutoType(&lz77, start, end);+ } -/*-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);+ if (totalcost2 < totalcost) {+ free(splitpoints);+ splitpoints = splitpoints2;+ npoints = npoints2; } else {- DeflateSplittingFirst(options, btype, final, in, instart, inend,- bp, out, outsize);+ free(splitpoints2); }- } else {- DeflateBlock(options, btype, final, in, instart, inend, bp, out, outsize); }++ for (i = 0; i <= npoints; i++) {+ size_t start = i == 0 ? 0 : splitpoints[i - 1];+ size_t end = i == npoints ? lz77.size : splitpoints[i];+ AddLZ77BlockAutoType(options, i == npoints && final,+ &lz77, start, end, 0,+ bp, out, outsize);+ }++ ZopfliCleanLZ77Store(&lz77);+ free(splitpoints);+ free(splitpoints_uncompressed); } 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) {+ size_t offset = *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) {+ do { 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;- }+ } while (i < insize); #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);+ "Original Size: %lu, Deflate: %lu, Compression: %f%% Removed\n",+ (unsigned long)insize, (unsigned long)(*outsize - offset),+ 100.0 * (double)(insize - (*outsize - offset)) / (double)insize); } }
src/cbits/deflate.h view
@@ -25,6 +25,7 @@ "squeeze" LZ77 compression backend. */ +#include "lz77.h" #include "zopfli.h" #ifdef __cplusplus@@ -75,9 +76,14 @@ lstart: start of block lend: end of block (not inclusive) */-double ZopfliCalculateBlockSize(const unsigned short* litlens,- const unsigned short* dists,+double ZopfliCalculateBlockSize(const ZopfliLZ77Store* lz77, size_t lstart, size_t lend, int btype);++/*+Calculates block size in bits, automatically using the best btype.+*/+double ZopfliCalculateBlockSizeAutoType(const ZopfliLZ77Store* lz77,+ size_t lstart, size_t lend); #ifdef __cplusplus } // extern "C"
src/cbits/gzip_container.c view
@@ -24,56 +24,63 @@ #include "deflate.h" -/* Table of CRCs of all 8-bit messages. */-static unsigned long crc_table[256];--/* Flag: has the table been computed? Initially false. */-static int crc_table_computed = 0;--/* Makes the table for a fast CRC. */-static void MakeCRCTable() {- unsigned long c;- int n, k;- for (n = 0; n < 256; n++) {- c = (unsigned long) n;- for (k = 0; k < 8; k++) {- if (c & 1) {- c = 0xedb88320L ^ (c >> 1);- } else {- c = c >> 1;- }- }- crc_table[n] = c;- }- crc_table_computed = 1;-}---/*-Updates a running crc with the bytes buf[0..len-1] and returns-the updated crc. The crc should be initialized to zero.-*/-static unsigned long UpdateCRC(unsigned long crc,- const unsigned char *buf, size_t len) {- unsigned long c = crc ^ 0xffffffffL;- unsigned n;+/* CRC polynomial: 0xedb88320 */+static const unsigned long crc32_table[256] = {+ 0u, 1996959894u, 3993919788u, 2567524794u, 124634137u, 1886057615u,+ 3915621685u, 2657392035u, 249268274u, 2044508324u, 3772115230u, 2547177864u,+ 162941995u, 2125561021u, 3887607047u, 2428444049u, 498536548u, 1789927666u,+ 4089016648u, 2227061214u, 450548861u, 1843258603u, 4107580753u, 2211677639u,+ 325883990u, 1684777152u, 4251122042u, 2321926636u, 335633487u, 1661365465u,+ 4195302755u, 2366115317u, 997073096u, 1281953886u, 3579855332u, 2724688242u,+ 1006888145u, 1258607687u, 3524101629u, 2768942443u, 901097722u, 1119000684u,+ 3686517206u, 2898065728u, 853044451u, 1172266101u, 3705015759u, 2882616665u,+ 651767980u, 1373503546u, 3369554304u, 3218104598u, 565507253u, 1454621731u,+ 3485111705u, 3099436303u, 671266974u, 1594198024u, 3322730930u, 2970347812u,+ 795835527u, 1483230225u, 3244367275u, 3060149565u, 1994146192u, 31158534u,+ 2563907772u, 4023717930u, 1907459465u, 112637215u, 2680153253u, 3904427059u,+ 2013776290u, 251722036u, 2517215374u, 3775830040u, 2137656763u, 141376813u,+ 2439277719u, 3865271297u, 1802195444u, 476864866u, 2238001368u, 4066508878u,+ 1812370925u, 453092731u, 2181625025u, 4111451223u, 1706088902u, 314042704u,+ 2344532202u, 4240017532u, 1658658271u, 366619977u, 2362670323u, 4224994405u,+ 1303535960u, 984961486u, 2747007092u, 3569037538u, 1256170817u, 1037604311u,+ 2765210733u, 3554079995u, 1131014506u, 879679996u, 2909243462u, 3663771856u,+ 1141124467u, 855842277u, 2852801631u, 3708648649u, 1342533948u, 654459306u,+ 3188396048u, 3373015174u, 1466479909u, 544179635u, 3110523913u, 3462522015u,+ 1591671054u, 702138776u, 2966460450u, 3352799412u, 1504918807u, 783551873u,+ 3082640443u, 3233442989u, 3988292384u, 2596254646u, 62317068u, 1957810842u,+ 3939845945u, 2647816111u, 81470997u, 1943803523u, 3814918930u, 2489596804u,+ 225274430u, 2053790376u, 3826175755u, 2466906013u, 167816743u, 2097651377u,+ 4027552580u, 2265490386u, 503444072u, 1762050814u, 4150417245u, 2154129355u,+ 426522225u, 1852507879u, 4275313526u, 2312317920u, 282753626u, 1742555852u,+ 4189708143u, 2394877945u, 397917763u, 1622183637u, 3604390888u, 2714866558u,+ 953729732u, 1340076626u, 3518719985u, 2797360999u, 1068828381u, 1219638859u,+ 3624741850u, 2936675148u, 906185462u, 1090812512u, 3747672003u, 2825379669u,+ 829329135u, 1181335161u, 3412177804u, 3160834842u, 628085408u, 1382605366u,+ 3423369109u, 3138078467u, 570562233u, 1426400815u, 3317316542u, 2998733608u,+ 733239954u, 1555261956u, 3268935591u, 3050360625u, 752459403u, 1541320221u,+ 2607071920u, 3965973030u, 1969922972u, 40735498u, 2617837225u, 3943577151u,+ 1913087877u, 83908371u, 2512341634u, 3803740692u, 2075208622u, 213261112u,+ 2463272603u, 3855990285u, 2094854071u, 198958881u, 2262029012u, 4057260610u,+ 1759359992u, 534414190u, 2176718541u, 4139329115u, 1873836001u, 414664567u,+ 2282248934u, 4279200368u, 1711684554u, 285281116u, 2405801727u, 4167216745u,+ 1634467795u, 376229701u, 2685067896u, 3608007406u, 1308918612u, 956543938u,+ 2808555105u, 3495958263u, 1231636301u, 1047427035u, 2932959818u, 3654703836u,+ 1088359270u, 936918000u, 2847714899u, 3736837829u, 1202900863u, 817233897u,+ 3183342108u, 3401237130u, 1404277552u, 615818150u, 3134207493u, 3453421203u,+ 1423857449u, 601450431u, 3009837614u, 3294710456u, 1567103746u, 711928724u,+ 3020668471u, 3272380065u, 1510334235u, 755167117u+}; - if (!crc_table_computed)- MakeCRCTable();- for (n = 0; n < len; n++) {- c = crc_table[(c ^ buf[n]) & 0xff] ^ (c >> 8);+/* Returns the CRC32 */+static unsigned long CRC(const unsigned char* data, size_t size) {+ unsigned long result = 0xffffffffu;+ for (; size > 0; size--) {+ result = crc32_table[(result ^ *(data++)) & 0xff] ^ (result >> 8); }- return c ^ 0xffffffffL;-}--/* Returns the CRC of the bytes buf[0..len-1]. */-static unsigned long CRC(const unsigned char* buf, int len) {- return UpdateCRC(0L, buf, len);+ return result ^ 0xffffffffu; } -/*-Compresses the data according to the gzip specification.-*/+/* Compresses the data according to the gzip specification, RFC 1952. */ void ZopfliGzipCompress(const ZopfliOptions* options, const unsigned char* in, size_t insize, unsigned char** out, size_t* outsize) {
src/cbits/hash.c view
@@ -26,13 +26,26 @@ #define HASH_SHIFT 5 #define HASH_MASK 32767 -void ZopfliInitHash(size_t window_size, ZopfliHash* h) {- size_t i;-- h->val = 0;+void ZopfliAllocHash(size_t window_size, ZopfliHash* h) { h->head = (int*)malloc(sizeof(*h->head) * 65536); h->prev = (unsigned short*)malloc(sizeof(*h->prev) * window_size); h->hashval = (int*)malloc(sizeof(*h->hashval) * window_size);++#ifdef ZOPFLI_HASH_SAME+ h->same = (unsigned short*)malloc(sizeof(*h->same) * window_size);+#endif++#ifdef ZOPFLI_HASH_SAME_HASH+ h->head2 = (int*)malloc(sizeof(*h->head2) * 65536);+ h->prev2 = (unsigned short*)malloc(sizeof(*h->prev2) * window_size);+ h->hashval2 = (int*)malloc(sizeof(*h->hashval2) * window_size);+#endif+}++void ZopfliResetHash(size_t window_size, ZopfliHash* h) {+ size_t i;++ h->val = 0; for (i = 0; i < 65536; i++) { h->head[i] = -1; /* -1 indicates no head so far. */ }@@ -42,7 +55,6 @@ } #ifdef ZOPFLI_HASH_SAME- h->same = (unsigned short*)malloc(sizeof(*h->same) * window_size); for (i = 0; i < window_size; i++) { h->same[i] = 0; }@@ -50,9 +62,6 @@ #ifdef ZOPFLI_HASH_SAME_HASH h->val2 = 0;- h->head2 = (int*)malloc(sizeof(*h->head2) * 65536);- h->prev2 = (unsigned short*)malloc(sizeof(*h->prev2) * window_size);- h->hashval2 = (int*)malloc(sizeof(*h->hashval2) * window_size); for (i = 0; i < 65536; i++) { h->head2[i] = -1; }@@ -129,7 +138,6 @@ void ZopfliWarmupHash(const unsigned char* array, size_t pos, size_t end, ZopfliHash* h) {- (void)end; UpdateHashValue(h, array[pos + 0]);- UpdateHashValue(h, array[pos + 1]);+ if (pos + 1 < end) UpdateHashValue(h, array[pos + 1]); }
src/cbits/hash.h view
@@ -27,16 +27,16 @@ #include "util.h" typedef struct ZopfliHash {- int* head; /* Hash value to index of its most recent occurance. */- unsigned short* prev; /* Index to index of prev. occurance of same hash. */+ int* head; /* Hash value to index of its most recent occurrence. */+ unsigned short* prev; /* Index to index of prev. occurrence of same hash. */ int* hashval; /* Index to hash value at this index. */ int val; /* Current hash value. */ #ifdef ZOPFLI_HASH_SAME_HASH /* Fields with similar purpose as the above hash, but for the second hash with a value that is calculated differently. */- int* head2; /* Hash value to index of its most recent occurance. */- unsigned short* prev2; /* Index to index of prev. occurance of same hash. */+ int* head2; /* Hash value to index of its most recent occurrence. */+ unsigned short* prev2; /* Index to index of prev. occurrence of same hash. */ int* hashval2; /* Index to hash value at this index. */ int val2; /* Current hash value. */ #endif@@ -46,10 +46,13 @@ #endif } ZopfliHash; -/* Allocates and initializes all fields of ZopfliHash. */-void ZopfliInitHash(size_t window_size, ZopfliHash* h);+/* Allocates ZopfliHash memory. */+void ZopfliAllocHash(size_t window_size, ZopfliHash* h); -/* Frees all fields of ZopfliHash. */+/* Resets all fields of ZopfliHash. */+void ZopfliResetHash(size_t window_size, ZopfliHash* h);++/* Frees ZopfliHash memory. */ void ZopfliCleanHash(ZopfliHash* h); /*
src/cbits/katajainen.c view
@@ -26,6 +26,7 @@ #include "katajainen.h" #include <assert.h> #include <stdlib.h>+#include <limits.h> typedef struct Node Node; @@ -36,16 +37,13 @@ size_t weight; /* Total weight (symbol count) of this chain. */ Node* tail; /* Previous node(s) of this chain, or 0 if none. */ int count; /* Leaf symbol index, or number of leaves before this chain. */- char inuse; /* Tracking for garbage collection. */ }; /* Memory pool for nodes. */ typedef struct NodePool {- Node* nodes; /* The pool. */- Node* next; /* Pointer to a possibly free node in the pool. */- int size; /* Size of the memory pool. */+ Node* next; /* Pointer to a free node in the pool. */ } NodePool; /*@@ -55,41 +53,9 @@ node->weight = weight; node->count = count; node->tail = tail;- node->inuse = 1; } /*-Finds a free location in the memory pool. Performs garbage collection if needed.-lists: If given, used to mark in-use nodes during garbage collection.-maxbits: Size of lists.-pool: Memory pool to get free node from.-*/-static Node* GetFreeNode(Node* (*lists)[2], int maxbits, NodePool* pool) {- for (;;) {- if (pool->next >= &pool->nodes[pool->size]) {- /* Garbage collection. */- int i;- for (i = 0; i < pool->size; i++) {- pool->nodes[i].inuse = 0;- }- if (lists) {- for (i = 0; i < maxbits * 2; i++) {- Node* node;- for (node = lists[i / 2][i % 2]; node; node = node->tail) {- node->inuse = 1;- }- }- }- pool->next = &pool->nodes[0];- }- if (!pool->next->inuse) break; /* Found one. */- pool->next++;- }- return pool->next++;-}---/* Performs a Boundary Package-Merge step. Puts a new chain in the given list. The new chain is, depending on the weights, a leaf or a combination of two chains from the previous list.@@ -99,18 +65,16 @@ numsymbols: Number of leaves. pool: the node memory pool. index: The index of the list in which a new chain or leaf is required.-final: Whether this is the last time this function is called. If it is then it- is no more needed to recursively call self. */-static void BoundaryPM(Node* (*lists)[2], int maxbits,- Node* leaves, int numsymbols, NodePool* pool, int index, char final) {+static void BoundaryPM(Node* (*lists)[2], Node* leaves, int numsymbols,+ NodePool* pool, int index) { Node* newchain; Node* oldchain; int lastcount = lists[index][1]->count; /* Count of last chain of list. */ if (index == 0 && lastcount >= numsymbols) return; - newchain = GetFreeNode(lists, maxbits, pool);+ newchain = pool->next++; oldchain = lists[index][1]; /* These are set up before the recursive calls below, so that there is a list@@ -129,15 +93,31 @@ newchain); } else { InitNode(sum, lastcount, lists[index - 1][1], newchain);- if (!final) {- /* Two lookahead chains of previous list used up, create new ones. */- BoundaryPM(lists, maxbits, leaves, numsymbols, pool, index - 1, 0);- BoundaryPM(lists, maxbits, leaves, numsymbols, pool, index - 1, 0);- }+ /* Two lookahead chains of previous list used up, create new ones. */+ BoundaryPM(lists, leaves, numsymbols, pool, index - 1);+ BoundaryPM(lists, leaves, numsymbols, pool, index - 1); } } } +static void BoundaryPMFinal(Node* (*lists)[2],+ Node* leaves, int numsymbols, NodePool* pool, int index) {+ int lastcount = lists[index][1]->count; /* Count of last chain of list. */++ size_t sum = lists[index - 1][0]->weight + lists[index - 1][1]->weight;++ if (lastcount < numsymbols && sum > leaves[lastcount].weight) {+ Node* newchain = pool->next;+ Node* oldchain = lists[index][1]->tail;++ lists[index][1] = newchain;+ newchain->count = lastcount + 1;+ newchain->tail = oldchain;+ } else {+ lists[index][1]->tail = lists[index - 1][1];+ }+}+ /* Initializes each list with as lookahead chains the two leaves with lowest weights.@@ -145,8 +125,8 @@ static void InitLists( NodePool* pool, const Node* leaves, int maxbits, Node* (*lists)[2]) { int i;- Node* node0 = GetFreeNode(0, maxbits, pool);- Node* node1 = GetFreeNode(0, maxbits, pool);+ Node* node0 = pool->next++;+ Node* node1 = pool->next++; InitNode(leaves[0].weight, 1, 0, node0); InitNode(leaves[1].weight, 2, 0, node1); for (i = 0; i < maxbits; i++) {@@ -161,12 +141,24 @@ chain: Chain to extract the bit length from (last chain from last list). */ static void ExtractBitLengths(Node* chain, Node* leaves, unsigned* bitlengths) {+ int counts[16] = {0};+ unsigned end = 16;+ unsigned ptr = 15;+ unsigned value = 1; Node* node;+ int val;+ for (node = chain; node; node = node->tail) {- int i;- for (i = 0; i < node->count; i++) {- bitlengths[leaves[i].count]++;+ counts[--end] = node->count;+ }++ val = counts[15];+ while (ptr >= end) {+ for (; val > counts[ptr - 1]; val--) {+ bitlengths[leaves[val - 1].count] = value; }+ ptr--;+ value++; } } @@ -183,6 +175,7 @@ int i; int numsymbols = 0; /* Amount of symbols with frequency > 0. */ int numBoundaryPMRuns;+ Node* nodes; /* Array of lists of chains. Each list requires only two lookahead chains at a time, so each list is a array of two Node*'s. */@@ -219,33 +212,51 @@ free(leaves); return 0; /* Only one symbol, give it bitlength 1, not 0. OK. */ }+ if (numsymbols == 2) {+ bitlengths[leaves[0].count]++;+ bitlengths[leaves[1].count]++;+ free(leaves);+ return 0;+ } - /* Sort the leaves from lightest to heaviest. */+ /* Sort the leaves from lightest to heaviest. Add count into the same+ variable for stable sorting. */+ for (i = 0; i < numsymbols; i++) {+ if (leaves[i].weight >=+ ((size_t)1 << (sizeof(leaves[0].weight) * CHAR_BIT - 9))) {+ free(leaves);+ return 1; /* Error, we need 9 bits for the count. */+ }+ leaves[i].weight = (leaves[i].weight << 9) | leaves[i].count;+ } qsort(leaves, numsymbols, sizeof(Node), LeafComparator);+ for (i = 0; i < numsymbols; i++) {+ leaves[i].weight >>= 9;+ } - /* Initialize node memory pool. */- pool.size = 2 * maxbits * (maxbits + 1);- pool.nodes = (Node*)malloc(pool.size * sizeof(*pool.nodes));- pool.next = pool.nodes;- for (i = 0; i < pool.size; i++) {- pool.nodes[i].inuse = 0;+ if (numsymbols - 1 < maxbits) {+ maxbits = numsymbols - 1; } + /* Initialize node memory pool. */+ nodes = (Node*)malloc(maxbits * 2 * numsymbols * sizeof(Node));+ pool.next = nodes;+ lists = (Node* (*)[2])malloc(maxbits * sizeof(*lists)); InitLists(&pool, leaves, maxbits, lists); /* In the last list, 2 * numsymbols - 2 active chains need to be created. Two are already created in the initialization. Each BoundaryPM run creates one. */ numBoundaryPMRuns = 2 * numsymbols - 4;- for (i = 0; i < numBoundaryPMRuns; i++) {- char final = i == numBoundaryPMRuns - 1;- BoundaryPM(lists, maxbits, leaves, numsymbols, &pool, maxbits - 1, final);+ for (i = 0; i < numBoundaryPMRuns - 1; i++) {+ BoundaryPM(lists, leaves, numsymbols, &pool, maxbits - 1); }+ BoundaryPMFinal(lists, leaves, numsymbols, &pool, maxbits - 1); ExtractBitLengths(lists[maxbits - 1][1], leaves, bitlengths); free(lists); free(leaves);- free(pool.nodes);+ free(nodes); return 0; /* OK. */ }
src/cbits/katajainen.h view
@@ -30,7 +30,7 @@ of 0, and if only a single symbol occurs at least once, its bitlength will be 1, and not 0 as would theoretically be needed for a single symbol. -frequencies: The amount of occurances of each symbol.+frequencies: The amount of occurrences of each symbol. n: The amount of symbols. maxbits: Maximum bit length, inclusive. bitlengths: Output, the bitlengths for the symbol prefix codes.
src/cbits/lz77.c view
@@ -18,38 +18,77 @@ */ #include "lz77.h"+#include "symbols.h" #include "util.h" #include <assert.h> #include <stdio.h> #include <stdlib.h> -void ZopfliInitLZ77Store(ZopfliLZ77Store* store) {+void ZopfliInitLZ77Store(const unsigned char* data, ZopfliLZ77Store* store) { store->size = 0; store->litlens = 0; store->dists = 0;+ store->pos = 0;+ store->data = data;+ store->ll_symbol = 0;+ store->d_symbol = 0;+ store->ll_counts = 0;+ store->d_counts = 0; } void ZopfliCleanLZ77Store(ZopfliLZ77Store* store) { free(store->litlens); free(store->dists);+ free(store->pos);+ free(store->ll_symbol);+ free(store->d_symbol);+ free(store->ll_counts);+ free(store->d_counts); } +static size_t CeilDiv(size_t a, size_t b) {+ return (a + b - 1) / b;+}+ void ZopfliCopyLZ77Store( const ZopfliLZ77Store* source, ZopfliLZ77Store* dest) { size_t i;+ size_t llsize = ZOPFLI_NUM_LL * CeilDiv(source->size, ZOPFLI_NUM_LL);+ size_t dsize = ZOPFLI_NUM_D * CeilDiv(source->size, ZOPFLI_NUM_D); ZopfliCleanLZ77Store(dest);+ ZopfliInitLZ77Store(source->data, dest); dest->litlens = (unsigned short*)malloc(sizeof(*dest->litlens) * source->size); dest->dists = (unsigned short*)malloc(sizeof(*dest->dists) * source->size);+ dest->pos = (size_t*)malloc(sizeof(*dest->pos) * source->size);+ dest->ll_symbol =+ (unsigned short*)malloc(sizeof(*dest->ll_symbol) * source->size);+ dest->d_symbol =+ (unsigned short*)malloc(sizeof(*dest->d_symbol) * source->size);+ dest->ll_counts = (size_t*)malloc(sizeof(*dest->ll_counts) * llsize);+ dest->d_counts = (size_t*)malloc(sizeof(*dest->d_counts) * dsize); - if (!dest->litlens || !dest->dists) exit(-1); /* Allocation failed. */+ /* Allocation failed. */+ if (!dest->litlens || !dest->dists) exit(-1);+ if (!dest->pos) exit(-1);+ if (!dest->ll_symbol || !dest->d_symbol) exit(-1);+ if (!dest->ll_counts || !dest->d_counts) exit(-1); dest->size = source->size; for (i = 0; i < source->size; i++) { dest->litlens[i] = source->litlens[i]; dest->dists[i] = source->dists[i];+ dest->pos[i] = source->pos[i];+ dest->ll_symbol[i] = source->ll_symbol[i];+ dest->d_symbol[i] = source->d_symbol[i]; }+ for (i = 0; i < llsize; i++) {+ dest->ll_counts[i] = source->ll_counts[i];+ }+ for (i = 0; i < dsize; i++) {+ dest->d_counts[i] = source->d_counts[i];+ } } /*@@ -57,12 +96,151 @@ context must be a ZopfliLZ77Store*. */ void ZopfliStoreLitLenDist(unsigned short length, unsigned short dist,- ZopfliLZ77Store* store) {- size_t size2 = store->size; /* Needed for using ZOPFLI_APPEND_DATA twice. */+ size_t pos, ZopfliLZ77Store* store) {+ size_t i;+ /* Needed for using ZOPFLI_APPEND_DATA multiple times. */+ size_t origsize = store->size;+ size_t llstart = ZOPFLI_NUM_LL * (origsize / ZOPFLI_NUM_LL);+ size_t dstart = ZOPFLI_NUM_D * (origsize / ZOPFLI_NUM_D);++ /* Everytime the index wraps around, a new cumulative histogram is made: we're+ keeping one histogram value per LZ77 symbol rather than a full histogram for+ each to save memory. */+ if (origsize % ZOPFLI_NUM_LL == 0) {+ size_t llsize = origsize;+ for (i = 0; i < ZOPFLI_NUM_LL; i++) {+ ZOPFLI_APPEND_DATA(+ origsize == 0 ? 0 : store->ll_counts[origsize - ZOPFLI_NUM_LL + i],+ &store->ll_counts, &llsize);+ }+ }+ if (origsize % ZOPFLI_NUM_D == 0) {+ size_t dsize = origsize;+ for (i = 0; i < ZOPFLI_NUM_D; i++) {+ ZOPFLI_APPEND_DATA(+ origsize == 0 ? 0 : store->d_counts[origsize - ZOPFLI_NUM_D + i],+ &store->d_counts, &dsize);+ }+ }+ ZOPFLI_APPEND_DATA(length, &store->litlens, &store->size);- ZOPFLI_APPEND_DATA(dist, &store->dists, &size2);+ store->size = origsize;+ ZOPFLI_APPEND_DATA(dist, &store->dists, &store->size);+ store->size = origsize;+ ZOPFLI_APPEND_DATA(pos, &store->pos, &store->size);+ assert(length < 259);++ if (dist == 0) {+ store->size = origsize;+ ZOPFLI_APPEND_DATA(length, &store->ll_symbol, &store->size);+ store->size = origsize;+ ZOPFLI_APPEND_DATA(0, &store->d_symbol, &store->size);+ store->ll_counts[llstart + length]++;+ } else {+ store->size = origsize;+ ZOPFLI_APPEND_DATA(ZopfliGetLengthSymbol(length),+ &store->ll_symbol, &store->size);+ store->size = origsize;+ ZOPFLI_APPEND_DATA(ZopfliGetDistSymbol(dist),+ &store->d_symbol, &store->size);+ store->ll_counts[llstart + ZopfliGetLengthSymbol(length)]++;+ store->d_counts[dstart + ZopfliGetDistSymbol(dist)]++;+ } } +void ZopfliAppendLZ77Store(const ZopfliLZ77Store* store,+ ZopfliLZ77Store* target) {+ size_t i;+ for (i = 0; i < store->size; i++) {+ ZopfliStoreLitLenDist(store->litlens[i], store->dists[i],+ store->pos[i], target);+ }+}++size_t ZopfliLZ77GetByteRange(const ZopfliLZ77Store* lz77,+ size_t lstart, size_t lend) {+ size_t l = lend - 1;+ if (lstart == lend) return 0;+ return lz77->pos[l] + ((lz77->dists[l] == 0) ?+ 1 : lz77->litlens[l]) - lz77->pos[lstart];+}++static void ZopfliLZ77GetHistogramAt(const ZopfliLZ77Store* lz77, size_t lpos,+ size_t* ll_counts, size_t* d_counts) {+ /* The real histogram is created by using the histogram for this chunk, but+ all superfluous values of this chunk subtracted. */+ size_t llpos = ZOPFLI_NUM_LL * (lpos / ZOPFLI_NUM_LL);+ size_t dpos = ZOPFLI_NUM_D * (lpos / ZOPFLI_NUM_D);+ size_t i;+ for (i = 0; i < ZOPFLI_NUM_LL; i++) {+ ll_counts[i] = lz77->ll_counts[llpos + i];+ }+ for (i = lpos + 1; i < llpos + ZOPFLI_NUM_LL && i < lz77->size; i++) {+ ll_counts[lz77->ll_symbol[i]]--;+ }+ for (i = 0; i < ZOPFLI_NUM_D; i++) {+ d_counts[i] = lz77->d_counts[dpos + i];+ }+ for (i = lpos + 1; i < dpos + ZOPFLI_NUM_D && i < lz77->size; i++) {+ if (lz77->dists[i] != 0) d_counts[lz77->d_symbol[i]]--;+ }+}++void ZopfliLZ77GetHistogram(const ZopfliLZ77Store* lz77,+ size_t lstart, size_t lend,+ size_t* ll_counts, size_t* d_counts) {+ size_t i;+ if (lstart + ZOPFLI_NUM_LL * 3 > lend) {+ memset(ll_counts, 0, sizeof(*ll_counts) * ZOPFLI_NUM_LL);+ memset(d_counts, 0, sizeof(*d_counts) * ZOPFLI_NUM_D);+ for (i = lstart; i < lend; i++) {+ ll_counts[lz77->ll_symbol[i]]++;+ if (lz77->dists[i] != 0) d_counts[lz77->d_symbol[i]]++;+ }+ } else {+ /* Subtract the cumulative histograms at the end and the start to get the+ histogram for this range. */+ ZopfliLZ77GetHistogramAt(lz77, lend - 1, ll_counts, d_counts);+ if (lstart > 0) {+ size_t ll_counts2[ZOPFLI_NUM_LL];+ size_t d_counts2[ZOPFLI_NUM_D];+ ZopfliLZ77GetHistogramAt(lz77, lstart - 1, ll_counts2, d_counts2);++ for (i = 0; i < ZOPFLI_NUM_LL; i++) {+ ll_counts[i] -= ll_counts2[i];+ }+ for (i = 0; i < ZOPFLI_NUM_D; i++) {+ d_counts[i] -= d_counts2[i];+ }+ }+ }+}++void ZopfliInitBlockState(const ZopfliOptions* options,+ size_t blockstart, size_t blockend, int add_lmc,+ ZopfliBlockState* s) {+ s->options = options;+ s->blockstart = blockstart;+ s->blockend = blockend;+#ifdef ZOPFLI_LONGEST_MATCH_CACHE+ if (add_lmc) {+ s->lmc = (ZopfliLongestMatchCache*)malloc(sizeof(ZopfliLongestMatchCache));+ ZopfliInitCache(blockend - blockstart, s->lmc);+ } else {+ s->lmc = 0;+ }+#endif+}++void ZopfliCleanBlockState(ZopfliBlockState* s) {+#ifdef ZOPFLI_LONGEST_MATCH_CACHE+ if (s->lmc) {+ ZopfliCleanCache(s->lmc);+ free(s->lmc);+ }+#endif+}+ /* Gets a score of the length given the distance. Typically, the score of the length is the length itself, but if the distance is very long, decrease the@@ -365,7 +543,7 @@ void ZopfliLZ77Greedy(ZopfliBlockState* s, const unsigned char* in, size_t instart, size_t inend,- ZopfliLZ77Store* store) {+ ZopfliLZ77Store* store, ZopfliHash* h) { size_t i = 0, j; unsigned short leng; unsigned short dist;@@ -374,9 +552,6 @@ ? instart - ZOPFLI_WINDOW_SIZE : 0; unsigned short dummysublen[259]; - ZopfliHash hash;- ZopfliHash* h = &hash;- #ifdef ZOPFLI_LAZY_MATCHING /* Lazy matching. */ unsigned prev_length = 0;@@ -387,7 +562,7 @@ if (instart == inend) return; - ZopfliInitHash(ZOPFLI_WINDOW_SIZE, h);+ ZopfliResetHash(ZOPFLI_WINDOW_SIZE, h); ZopfliWarmupHash(in, windowstart, inend, h); for (i = windowstart; i < instart; i++) { ZopfliUpdateHash(in, i, inend, h);@@ -406,7 +581,7 @@ if (match_available) { match_available = 0; if (lengthscore > prevlengthscore + 1) {- ZopfliStoreLitLenDist(in[i - 1], 0, store);+ ZopfliStoreLitLenDist(in[i - 1], 0, i - 1, store); if (lengthscore >= ZOPFLI_MIN_MATCH && leng < ZOPFLI_MAX_MATCH) { match_available = 1; prev_length = leng;@@ -420,7 +595,7 @@ lengthscore = prevlengthscore; /* Add to output. */ ZopfliVerifyLenDist(in, inend, i - 1, dist, leng);- ZopfliStoreLitLenDist(leng, dist, store);+ ZopfliStoreLitLenDist(leng, dist, i - 1, store); for (j = 2; j < leng; j++) { assert(i < inend); i++;@@ -441,10 +616,10 @@ /* Add to output. */ if (lengthscore >= ZOPFLI_MIN_MATCH) { ZopfliVerifyLenDist(in, inend, i, dist, leng);- ZopfliStoreLitLenDist(leng, dist, store);+ ZopfliStoreLitLenDist(leng, dist, i, store); } else { leng = 1;- ZopfliStoreLitLenDist(in[i], 0, store);+ ZopfliStoreLitLenDist(in[i], 0, i, store); } for (j = 1; j < leng; j++) { assert(i < inend);@@ -452,31 +627,4 @@ ZopfliUpdateHash(in, i, inend, h); } }-- ZopfliCleanHash(h);-}--void ZopfliLZ77Counts(const unsigned short* litlens,- const unsigned short* dists,- size_t start, size_t end,- size_t* ll_count, size_t* d_count) {- size_t i;-- for (i = 0; i < 288; i++) {- ll_count[i] = 0;- }- for (i = 0; i < 32; i++) {- d_count[i] = 0;- }-- for (i = start; i < end; i++) {- if (dists[i] == 0) {- ll_count[litlens[i]]++;- } else {- ll_count[ZopfliGetLengthSymbol(litlens[i])]++;- d_count[ZopfliGetDistSymbol(dists[i])]++;- }- }-- ll_count[256] = 1; /* End symbol. */ }
src/cbits/lz77.h view
@@ -33,23 +33,50 @@ /* Stores lit/length and dist pairs for LZ77.-litlens: Contains the literal symbols or length values.-dists: Indicates the distance, or 0 to indicate that there is no distance and-litlens contains a literal instead of a length.-litlens and dists both have the same size.+Parameter litlens: Contains the literal symbols or length values.+Parameter dists: Contains the distances. A value is 0 to indicate that there is+no dist and the corresponding litlens value is a literal instead of a length.+Parameter size: The size of both the litlens and dists arrays.+The memory can best be managed by using ZopfliInitLZ77Store to initialize it,+ZopfliCleanLZ77Store to destroy it, and ZopfliStoreLitLenDist to append values.+ */ typedef struct ZopfliLZ77Store { unsigned short* litlens; /* Lit or len. */ unsigned short* dists; /* If 0: indicates literal in corresponding litlens, if > 0: length in corresponding litlens, this is the distance. */ size_t size;++ const unsigned char* data; /* original data */+ size_t* pos; /* position in data where this LZ77 command begins */++ unsigned short* ll_symbol;+ unsigned short* d_symbol;++ /* Cumulative histograms wrapping around per chunk. Each chunk has the amount+ of distinct symbols as length, so using 1 value per LZ77 symbol, we have a+ precise histogram at every N symbols, and the rest can be calculated by+ looping through the actual symbols of this chunk. */+ size_t* ll_counts;+ size_t* d_counts; } ZopfliLZ77Store; -void ZopfliInitLZ77Store(ZopfliLZ77Store* store);+void ZopfliInitLZ77Store(const unsigned char* data, ZopfliLZ77Store* store); void ZopfliCleanLZ77Store(ZopfliLZ77Store* store); void ZopfliCopyLZ77Store(const ZopfliLZ77Store* source, ZopfliLZ77Store* dest); void ZopfliStoreLitLenDist(unsigned short length, unsigned short dist,- ZopfliLZ77Store* store);+ size_t pos, ZopfliLZ77Store* store);+void ZopfliAppendLZ77Store(const ZopfliLZ77Store* store,+ ZopfliLZ77Store* target);+/* Gets the amount of raw bytes that this range of LZ77 symbols spans. */+size_t ZopfliLZ77GetByteRange(const ZopfliLZ77Store* lz77,+ size_t lstart, size_t lend);+/* Gets the histogram of lit/len and dist symbols in the given range, using the+cumulative histograms, so faster than adding one by one for large range. Does+not add the one end symbol of value 256. */+void ZopfliLZ77GetHistogram(const ZopfliLZ77Store* lz77,+ size_t lstart, size_t lend,+ size_t* ll_counts, size_t* d_counts); /* Some state information for compressing a block.@@ -69,6 +96,11 @@ size_t blockend; } ZopfliBlockState; +void ZopfliInitBlockState(const ZopfliOptions* options,+ size_t blockstart, size_t blockend, int add_lmc,+ ZopfliBlockState* s);+void ZopfliCleanBlockState(ZopfliBlockState* s);+ /* Finds the longest match (length and corresponding distance) for LZ77 compression.@@ -97,22 +129,6 @@ unsigned short dist, unsigned short length); /*-Counts the number of literal, length and distance symbols in the given lz77-arrays.-litlens: lz77 lit/lengths-dists: ll77 distances-start: where to begin counting in litlens and dists-end: where to stop counting in litlens and dists (not inclusive)-ll_count: count of each lit/len symbol, must have size 288 (see deflate- standard)-d_count: count of each dist symbol, must have size 32 (see deflate standard)-*/-void ZopfliLZ77Counts(const unsigned short* litlens,- const unsigned short* dists,- size_t start, size_t end,- size_t* ll_count, size_t* d_count);--/* Does LZ77 using an algorithm similar to gzip, with lazy matching, rather than with the slow but better "squeeze" implementation. The result is placed in the ZopfliLZ77Store.@@ -121,6 +137,6 @@ */ void ZopfliLZ77Greedy(ZopfliBlockState* s, const unsigned char* in, size_t instart, size_t inend,- ZopfliLZ77Store* store);+ ZopfliLZ77Store* store, ZopfliHash* h); #endif /* ZOPFLI_LZ77_H_ */
src/cbits/squeeze.c view
@@ -25,35 +25,40 @@ #include "blocksplitter.h" #include "deflate.h"+#include "symbols.h" #include "tree.h" #include "util.h" typedef struct SymbolStats { /* The literal and length symbols. */- size_t litlens[288];+ size_t litlens[ZOPFLI_NUM_LL]; /* The 32 unique dist symbols, not the 32768 possible dists. */- size_t dists[32];+ size_t dists[ZOPFLI_NUM_D]; - double ll_symbols[288]; /* Length of each lit/len symbol in bits. */- double d_symbols[32]; /* Length of each dist symbol in bits. */+ /* Length of each lit/len symbol in bits. */+ double ll_symbols[ZOPFLI_NUM_LL];+ /* Length of each dist symbol in bits. */+ double d_symbols[ZOPFLI_NUM_D]; } SymbolStats; /* Sets everything to 0. */ static void InitStats(SymbolStats* stats) {- memset(stats->litlens, 0, 288 * sizeof(stats->litlens[0]));- memset(stats->dists, 0, 32 * sizeof(stats->dists[0]));+ memset(stats->litlens, 0, ZOPFLI_NUM_LL * sizeof(stats->litlens[0]));+ memset(stats->dists, 0, ZOPFLI_NUM_D * sizeof(stats->dists[0])); - memset(stats->ll_symbols, 0, 288 * sizeof(stats->ll_symbols[0]));- memset(stats->d_symbols, 0, 32 * sizeof(stats->d_symbols[0]));+ memset(stats->ll_symbols, 0, ZOPFLI_NUM_LL * sizeof(stats->ll_symbols[0]));+ memset(stats->d_symbols, 0, ZOPFLI_NUM_D * sizeof(stats->d_symbols[0])); } static void CopyStats(SymbolStats* source, SymbolStats* dest) {- memcpy(dest->litlens, source->litlens, 288 * sizeof(dest->litlens[0]));- memcpy(dest->dists, source->dists, 32 * sizeof(dest->dists[0]));+ memcpy(dest->litlens, source->litlens,+ ZOPFLI_NUM_LL * sizeof(dest->litlens[0]));+ memcpy(dest->dists, source->dists, ZOPFLI_NUM_D * sizeof(dest->dists[0])); memcpy(dest->ll_symbols, source->ll_symbols,- 288 * sizeof(dest->ll_symbols[0]));- memcpy(dest->d_symbols, source->d_symbols, 32 * sizeof(dest->d_symbols[0]));+ ZOPFLI_NUM_LL * sizeof(dest->ll_symbols[0]));+ memcpy(dest->d_symbols, source->d_symbols,+ ZOPFLI_NUM_D * sizeof(dest->d_symbols[0])); } /* Adds the bit lengths. */@@ -61,11 +66,11 @@ const SymbolStats* stats2, double w2, SymbolStats* result) { size_t i;- for (i = 0; i < 288; i++) {+ for (i = 0; i < ZOPFLI_NUM_LL; i++) { result->litlens[i] = (size_t) (stats1->litlens[i] * w1 + stats2->litlens[i] * w2); }- for (i = 0; i < 32; i++) {+ for (i = 0; i < ZOPFLI_NUM_D; i++) { result->dists[i] = (size_t) (stats1->dists[i] * w1 + stats2->dists[i] * w2); }@@ -96,15 +101,15 @@ } static void RandomizeStatFreqs(RanState* state, SymbolStats* stats) {- RandomizeFreqs(state, stats->litlens, 288);- RandomizeFreqs(state, stats->dists, 32);+ RandomizeFreqs(state, stats->litlens, ZOPFLI_NUM_LL);+ RandomizeFreqs(state, stats->dists, ZOPFLI_NUM_D); stats->litlens[256] = 1; /* End symbol. */ } static void ClearStatFreqs(SymbolStats* stats) { size_t i;- for (i = 0; i < 288; i++) stats->litlens[i] = 0;- for (i = 0; i < 32; i++) stats->dists[i] = 0;+ for (i = 0; i < ZOPFLI_NUM_LL; i++) stats->litlens[i] = 0;+ for (i = 0; i < ZOPFLI_NUM_D; i++) stats->dists[i] = 0; } /*@@ -126,7 +131,7 @@ int dbits = ZopfliGetDistExtraBits(dist); int lbits = ZopfliGetLengthExtraBits(litlen); int lsym = ZopfliGetLengthSymbol(litlen);- double cost = 0;+ int cost = 0; if (lsym <= 279) cost += 7; else cost += 8; cost += 5; /* Every dist symbol has length 5. */@@ -147,7 +152,7 @@ int lbits = ZopfliGetLengthExtraBits(litlen); int dsym = ZopfliGetDistSymbol(dist); int dbits = ZopfliGetDistExtraBits(dist);- return stats->ll_symbols[lsym] + lbits + stats->d_symbols[dsym] + dbits;+ return lbits + dbits + stats->ll_symbols[lsym] + stats->d_symbols[dsym]; } } @@ -192,6 +197,10 @@ return costmodel(bestlength, bestdist, costcontext); } +static size_t zopfli_min(size_t a, size_t b) {+ return a < b ? a : b;+}+ /* Performs the forward pass for "squeeze". Gets the most optimal length to reach every byte from a previous byte, using cost calculations.@@ -209,27 +218,23 @@ const unsigned char* in, size_t instart, size_t inend, CostModelFun* costmodel, void* costcontext,- unsigned short* length_array) {+ unsigned short* length_array,+ ZopfliHash* h, float* costs) { /* Best cost to get here so far. */ size_t blocksize = inend - instart;- float* costs;- size_t i = 0, k;+ size_t i = 0, k, kend; unsigned short leng; unsigned short dist; unsigned short sublen[259]; size_t windowstart = instart > ZOPFLI_WINDOW_SIZE ? instart - ZOPFLI_WINDOW_SIZE : 0;- ZopfliHash hash;- ZopfliHash* h = &hash; double result; double mincost = GetCostModelMinCost(costmodel, costcontext);+ double mincostaddcostj; if (instart == inend) return 0; - costs = (float*)malloc(sizeof(float) * (blocksize + 1));- if (!costs) exit(-1); /* Allocation failed. */-- ZopfliInitHash(ZOPFLI_WINDOW_SIZE, h);+ ZopfliResetHash(ZOPFLI_WINDOW_SIZE, h); ZopfliWarmupHash(in, windowstart, inend, h); for (i = windowstart; i < instart; i++) { ZopfliUpdateHash(in, i, inend, h);@@ -270,7 +275,7 @@ /* Literal. */ if (i + 1 <= inend) {- double newCost = costs[j] + costmodel(in[i], 0, costcontext);+ double newCost = costmodel(in[i], 0, costcontext) + costs[j]; assert(newCost >= 0); if (newCost < costs[j + 1]) { costs[j + 1] = newCost;@@ -278,14 +283,16 @@ } } /* Lengths. */- for (k = 3; k <= leng && i + k <= inend; k++) {+ kend = zopfli_min(leng, inend-i);+ mincostaddcostj = mincost + costs[j];+ for (k = 3; k <= kend; k++) { double newCost; /* Calling the cost model is expensive, avoid this if we are already at the minimum possible cost that it can return. */- if (costs[j + k] - costs[j] <= mincost) continue;+ if (costs[j + k] <= mincostaddcostj) continue; - newCost = costs[j] + costmodel(k, sublen[k], costcontext);+ newCost = costmodel(k, sublen[k], costcontext) + costs[j]; assert(newCost >= 0); if (newCost < costs[j + k]) { assert(k <= ZOPFLI_MAX_MATCH);@@ -298,9 +305,6 @@ assert(costs[blocksize] >= 0); result = costs[blocksize]; - ZopfliCleanHash(h);- free(costs);- return result; } @@ -334,19 +338,16 @@ static void FollowPath(ZopfliBlockState* s, const unsigned char* in, size_t instart, size_t inend, unsigned short* path, size_t pathsize,- ZopfliLZ77Store* store) {+ ZopfliLZ77Store* store, ZopfliHash *h) { size_t i, j, pos = 0; size_t windowstart = instart > ZOPFLI_WINDOW_SIZE ? instart - ZOPFLI_WINDOW_SIZE : 0; size_t total_length_test = 0; - ZopfliHash hash;- ZopfliHash* h = &hash;- if (instart == inend) return; - ZopfliInitHash(ZOPFLI_WINDOW_SIZE, h);+ ZopfliResetHash(ZOPFLI_WINDOW_SIZE, h); ZopfliWarmupHash(in, windowstart, inend, h); for (i = windowstart; i < instart; i++) { ZopfliUpdateHash(in, i, inend, h);@@ -369,11 +370,11 @@ &dist, &dummy_length); assert(!(dummy_length != length && length > 2 && dummy_length > 2)); ZopfliVerifyLenDist(in, inend, pos, dist, length);- ZopfliStoreLitLenDist(length, dist, store);+ ZopfliStoreLitLenDist(length, dist, pos, store); total_length_test += length; } else { length = 1;- ZopfliStoreLitLenDist(in[pos], 0, store);+ ZopfliStoreLitLenDist(in[pos], 0, pos, store); total_length_test++; } @@ -385,14 +386,12 @@ pos += length; }-- ZopfliCleanHash(h); } /* Calculates the entropy of the statistics */ static void CalculateStatistics(SymbolStats* stats) {- ZopfliCalculateEntropy(stats->litlens, 288, stats->ll_symbols);- ZopfliCalculateEntropy(stats->dists, 32, stats->d_symbols);+ ZopfliCalculateEntropy(stats->litlens, ZOPFLI_NUM_LL, stats->ll_symbols);+ ZopfliCalculateEntropy(stats->dists, ZOPFLI_NUM_D, stats->d_symbols); } /* Appends the symbol statistics from the store. */@@ -414,14 +413,13 @@ /* Does a single run for ZopfliLZ77Optimal. For good compression, repeated runs with updated statistics should be performed.- s: the block state in: the input data array instart: where to start inend: where to stop (not inclusive) path: pointer to dynamically allocated memory to store the path pathsize: pointer to the size of the dynamic path array-length_array: array if size (inend - instart) used to store lengths+length_array: array of size (inend - instart) used to store lengths costmodel: function to use as the cost model for this squeeze run costcontext: abstract context for the costmodel function store: place to output the LZ77 data@@ -432,20 +430,22 @@ const unsigned char* in, size_t instart, size_t inend, unsigned short** path, size_t* pathsize, unsigned short* length_array, CostModelFun* costmodel,- void* costcontext, ZopfliLZ77Store* store) {- double cost = GetBestLengths(- s, in, instart, inend, costmodel, costcontext, length_array);+ void* costcontext, ZopfliLZ77Store* store,+ ZopfliHash* h, float* costs) {+ double cost = GetBestLengths(s, in, instart, inend, costmodel,+ costcontext, length_array, h, costs); free(*path); *path = 0; *pathsize = 0; TraceBackwards(inend - instart, length_array, path, pathsize);- FollowPath(s, in, instart, inend, *path, *pathsize, store);+ FollowPath(s, in, instart, inend, *path, *pathsize, store, h); assert(cost < ZOPFLI_LARGE_FLOAT); return cost; } void ZopfliLZ77Optimal(ZopfliBlockState *s, const unsigned char* in, size_t instart, size_t inend,+ int numiterations, ZopfliLZ77Store* store) { /* Dist to get to here with smallest cost. */ size_t blocksize = inend - instart;@@ -454,8 +454,11 @@ unsigned short* path = 0; size_t pathsize = 0; ZopfliLZ77Store currentstore;+ ZopfliHash hash;+ ZopfliHash* h = &hash; SymbolStats stats, beststats, laststats; int i;+ float* costs = (float*)malloc(sizeof(float) * (blocksize + 1)); double cost; double bestcost = ZOPFLI_LARGE_FLOAT; double lastcost = 0;@@ -463,29 +466,30 @@ RanState ran_state; int lastrandomstep = -1; + if (!costs) exit(-1); /* Allocation failed. */ if (!length_array) exit(-1); /* Allocation failed. */ InitRanState(&ran_state); InitStats(&stats);- ZopfliInitLZ77Store(¤tstore);+ ZopfliInitLZ77Store(in, ¤tstore);+ ZopfliAllocHash(ZOPFLI_WINDOW_SIZE, h); /* Do regular deflate, then loop multiple shortest path runs, each time using the statistics of the previous run. */ /* Initial run. */- ZopfliLZ77Greedy(s, in, instart, inend, ¤tstore);+ ZopfliLZ77Greedy(s, in, instart, inend, ¤tstore, h); GetStatistics(¤tstore, &stats); /* Repeat statistics with each time the cost model from the previous stat run. */- for (i = 0; i < s->options->numiterations; i++) {+ for (i = 0; i < numiterations; i++) { ZopfliCleanLZ77Store(¤tstore);- ZopfliInitLZ77Store(¤tstore);+ ZopfliInitLZ77Store(in, ¤tstore); LZ77OptimalRun(s, in, instart, inend, &path, &pathsize, length_array, GetCostStat, (void*)&stats,- ¤tstore);- cost = ZopfliCalculateBlockSize(currentstore.litlens, currentstore.dists,- 0, currentstore.size, 2);+ ¤tstore, h, costs);+ cost = ZopfliCalculateBlockSize(¤tstore, 0, currentstore.size, 2); if (s->options->verbose_more || (s->options->verbose && cost < bestcost)) { fprintf(stderr, "Iteration %d: %d bit\n", i, (int) cost); }@@ -516,7 +520,9 @@ free(length_array); free(path);+ free(costs); ZopfliCleanLZ77Store(¤tstore);+ ZopfliCleanHash(h); } void ZopfliLZ77OptimalFixed(ZopfliBlockState *s,@@ -530,17 +536,25 @@ (unsigned short*)malloc(sizeof(unsigned short) * (blocksize + 1)); unsigned short* path = 0; size_t pathsize = 0;+ ZopfliHash hash;+ ZopfliHash* h = &hash;+ float* costs = (float*)malloc(sizeof(float) * (blocksize + 1)); + if (!costs) exit(-1); /* Allocation failed. */ if (!length_array) exit(-1); /* Allocation failed. */ + ZopfliAllocHash(ZOPFLI_WINDOW_SIZE, h);+ s->blockstart = instart; s->blockend = inend; /* Shortest path for fixed tree This one should give the shortest possible result for fixed tree, no repeated runs are needed since the tree is known. */ LZ77OptimalRun(s, in, instart, inend, &path, &pathsize,- length_array, GetCostFixed, 0, store);+ length_array, GetCostFixed, 0, store, h, costs); free(length_array); free(path);+ free(costs);+ ZopfliCleanHash(h); }
src/cbits/squeeze.h view
@@ -40,6 +40,7 @@ */ void ZopfliLZ77Optimal(ZopfliBlockState *s, const unsigned char* in, size_t instart, size_t inend,+ int numiterations, ZopfliLZ77Store* store); /*
+ src/cbits/symbols.h view
@@ -0,0 +1,239 @@+/*+Copyright 2016 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)+*/++/*+Utilities for using the lz77 symbols of the deflate spec.+*/++#ifndef ZOPFLI_SYMBOLS_H_+#define ZOPFLI_SYMBOLS_H_++/* __has_builtin available in clang */+#ifdef __has_builtin+# if __has_builtin(__builtin_clz)+# define ZOPFLI_HAS_BUILTIN_CLZ+# endif+/* __builtin_clz available beginning with GCC 3.4 */+#elif __GNUC__ * 100 + __GNUC_MINOR__ >= 304+# define ZOPFLI_HAS_BUILTIN_CLZ+#endif++/* Gets the amount of extra bits for the given dist, cfr. the DEFLATE spec. */+static int ZopfliGetDistExtraBits(int dist) {+#ifdef ZOPFLI_HAS_BUILTIN_CLZ+ if (dist < 5) return 0;+ return (31 ^ __builtin_clz(dist - 1)) - 1; /* log2(dist - 1) - 1 */+#else+ if (dist < 5) return 0;+ else if (dist < 9) return 1;+ else if (dist < 17) return 2;+ else if (dist < 33) return 3;+ else if (dist < 65) return 4;+ else if (dist < 129) return 5;+ else if (dist < 257) return 6;+ else if (dist < 513) return 7;+ else if (dist < 1025) return 8;+ else if (dist < 2049) return 9;+ else if (dist < 4097) return 10;+ else if (dist < 8193) return 11;+ else if (dist < 16385) return 12;+ else return 13;+#endif+}++/* Gets value of the extra bits for the given dist, cfr. the DEFLATE spec. */+static int ZopfliGetDistExtraBitsValue(int dist) {+#ifdef ZOPFLI_HAS_BUILTIN_CLZ+ if (dist < 5) {+ return 0;+ } else {+ int l = 31 ^ __builtin_clz(dist - 1); /* log2(dist - 1) */+ return (dist - (1 + (1 << l))) & ((1 << (l - 1)) - 1);+ }+#else+ if (dist < 5) return 0;+ else if (dist < 9) return (dist - 5) & 1;+ else if (dist < 17) return (dist - 9) & 3;+ else if (dist < 33) return (dist - 17) & 7;+ else if (dist < 65) return (dist - 33) & 15;+ else if (dist < 129) return (dist - 65) & 31;+ else if (dist < 257) return (dist - 129) & 63;+ else if (dist < 513) return (dist - 257) & 127;+ else if (dist < 1025) return (dist - 513) & 255;+ else if (dist < 2049) return (dist - 1025) & 511;+ else if (dist < 4097) return (dist - 2049) & 1023;+ else if (dist < 8193) return (dist - 4097) & 2047;+ else if (dist < 16385) return (dist - 8193) & 4095;+ else return (dist - 16385) & 8191;+#endif+}++/* Gets the symbol for the given dist, cfr. the DEFLATE spec. */+static int ZopfliGetDistSymbol(int dist) {+#ifdef ZOPFLI_HAS_BUILTIN_CLZ+ if (dist < 5) {+ return dist - 1;+ } else {+ int l = (31 ^ __builtin_clz(dist - 1)); /* log2(dist - 1) */+ int r = ((dist - 1) >> (l - 1)) & 1;+ return l * 2 + r;+ }+#else+ if (dist < 193) {+ if (dist < 13) { /* dist 0..13. */+ if (dist < 5) return dist - 1;+ else if (dist < 7) return 4;+ else if (dist < 9) return 5;+ else return 6;+ } else { /* dist 13..193. */+ if (dist < 17) return 7;+ else if (dist < 25) return 8;+ else if (dist < 33) return 9;+ else if (dist < 49) return 10;+ else if (dist < 65) return 11;+ else if (dist < 97) return 12;+ else if (dist < 129) return 13;+ else return 14;+ }+ } else {+ if (dist < 2049) { /* dist 193..2049. */+ if (dist < 257) return 15;+ else if (dist < 385) return 16;+ else if (dist < 513) return 17;+ else if (dist < 769) return 18;+ else if (dist < 1025) return 19;+ else if (dist < 1537) return 20;+ else return 21;+ } else { /* dist 2049..32768. */+ if (dist < 3073) return 22;+ else if (dist < 4097) return 23;+ else if (dist < 6145) return 24;+ else if (dist < 8193) return 25;+ else if (dist < 12289) return 26;+ else if (dist < 16385) return 27;+ else if (dist < 24577) return 28;+ else return 29;+ }+ }+#endif+}++/* Gets the amount of extra bits for the given length, cfr. the DEFLATE spec. */+static int ZopfliGetLengthExtraBits(int l) {+ static const int table[259] = {+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,+ 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,+ 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,+ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,+ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,+ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,+ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,+ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,+ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,+ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,+ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,+ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,+ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,+ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,+ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 0+ };+ return table[l];+}++/* Gets value of the extra bits for the given length, cfr. the DEFLATE spec. */+static int ZopfliGetLengthExtraBitsValue(int l) {+ static const int table[259] = {+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 2, 3, 0,+ 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5,+ 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6,+ 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,+ 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2,+ 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,+ 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28,+ 29, 30, 31, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,+ 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 0, 1, 2, 3, 4, 5, 6,+ 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26,+ 27, 28, 29, 30, 31, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,+ 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 0+ };+ return table[l];+}++/*+Gets the symbol for the given length, cfr. the DEFLATE spec.+Returns the symbol in the range [257-285] (inclusive)+*/+static int ZopfliGetLengthSymbol(int l) {+ static const int table[259] = {+ 0, 0, 0, 257, 258, 259, 260, 261, 262, 263, 264,+ 265, 265, 266, 266, 267, 267, 268, 268,+ 269, 269, 269, 269, 270, 270, 270, 270,+ 271, 271, 271, 271, 272, 272, 272, 272,+ 273, 273, 273, 273, 273, 273, 273, 273,+ 274, 274, 274, 274, 274, 274, 274, 274,+ 275, 275, 275, 275, 275, 275, 275, 275,+ 276, 276, 276, 276, 276, 276, 276, 276,+ 277, 277, 277, 277, 277, 277, 277, 277,+ 277, 277, 277, 277, 277, 277, 277, 277,+ 278, 278, 278, 278, 278, 278, 278, 278,+ 278, 278, 278, 278, 278, 278, 278, 278,+ 279, 279, 279, 279, 279, 279, 279, 279,+ 279, 279, 279, 279, 279, 279, 279, 279,+ 280, 280, 280, 280, 280, 280, 280, 280,+ 280, 280, 280, 280, 280, 280, 280, 280,+ 281, 281, 281, 281, 281, 281, 281, 281,+ 281, 281, 281, 281, 281, 281, 281, 281,+ 281, 281, 281, 281, 281, 281, 281, 281,+ 281, 281, 281, 281, 281, 281, 281, 281,+ 282, 282, 282, 282, 282, 282, 282, 282,+ 282, 282, 282, 282, 282, 282, 282, 282,+ 282, 282, 282, 282, 282, 282, 282, 282,+ 282, 282, 282, 282, 282, 282, 282, 282,+ 283, 283, 283, 283, 283, 283, 283, 283,+ 283, 283, 283, 283, 283, 283, 283, 283,+ 283, 283, 283, 283, 283, 283, 283, 283,+ 283, 283, 283, 283, 283, 283, 283, 283,+ 284, 284, 284, 284, 284, 284, 284, 284,+ 284, 284, 284, 284, 284, 284, 284, 284,+ 284, 284, 284, 284, 284, 284, 284, 284,+ 284, 284, 284, 284, 284, 284, 284, 285+ };+ return table[l];+}++/* Gets the amount of extra bits for the given length symbol. */+static int ZopfliGetLengthSymbolExtraBits(int s) {+ static const int table[29] = {+ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,+ 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0+ };+ return table[s - 257];+}++/* Gets the amount of extra bits for the given distance symbol. */+static int ZopfliGetDistSymbolExtraBits(int s) {+ static const int table[30] = {+ 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8,+ 9, 9, 10, 10, 11, 11, 12, 12, 13, 13+ };+ return table[s];+}++#endif /* ZOPFLI_SYMBOLS_H_ */
src/cbits/util.c view
@@ -25,184 +25,6 @@ #include <stdio.h> #include <stdlib.h> -int ZopfliGetDistExtraBits(int dist) {-#ifdef __GNUC__- if (dist < 5) return 0;- return (31 ^ __builtin_clz(dist - 1)) - 1; /* log2(dist - 1) - 1 */-#else- if (dist < 5) return 0;- else if (dist < 9) return 1;- else if (dist < 17) return 2;- else if (dist < 33) return 3;- else if (dist < 65) return 4;- else if (dist < 129) return 5;- else if (dist < 257) return 6;- else if (dist < 513) return 7;- else if (dist < 1025) return 8;- else if (dist < 2049) return 9;- else if (dist < 4097) return 10;- else if (dist < 8193) return 11;- else if (dist < 16385) return 12;- else return 13;-#endif-}--int ZopfliGetDistExtraBitsValue(int dist) {-#ifdef __GNUC__- if (dist < 5) {- return 0;- } else {- int l = 31 ^ __builtin_clz(dist - 1); /* log2(dist - 1) */- return (dist - (1 + (1 << l))) & ((1 << (l - 1)) - 1);- }-#else- if (dist < 5) return 0;- else if (dist < 9) return (dist - 5) & 1;- else if (dist < 17) return (dist - 9) & 3;- else if (dist < 33) return (dist - 17) & 7;- else if (dist < 65) return (dist - 33) & 15;- else if (dist < 129) return (dist - 65) & 31;- else if (dist < 257) return (dist - 129) & 63;- else if (dist < 513) return (dist - 257) & 127;- else if (dist < 1025) return (dist - 513) & 255;- else if (dist < 2049) return (dist - 1025) & 511;- else if (dist < 4097) return (dist - 2049) & 1023;- else if (dist < 8193) return (dist - 4097) & 2047;- else if (dist < 16385) return (dist - 8193) & 4095;- else return (dist - 16385) & 8191;-#endif-}--int ZopfliGetDistSymbol(int dist) {-#ifdef __GNUC__- if (dist < 5) {- return dist - 1;- } else {- int l = (31 ^ __builtin_clz(dist - 1)); /* log2(dist - 1) */- int r = ((dist - 1) >> (l - 1)) & 1;- return l * 2 + r;- }-#else- if (dist < 193) {- if (dist < 13) { /* dist 0..13. */- if (dist < 5) return dist - 1;- else if (dist < 7) return 4;- else if (dist < 9) return 5;- else return 6;- } else { /* dist 13..193. */- if (dist < 17) return 7;- else if (dist < 25) return 8;- else if (dist < 33) return 9;- else if (dist < 49) return 10;- else if (dist < 65) return 11;- else if (dist < 97) return 12;- else if (dist < 129) return 13;- else return 14;- }- } else {- if (dist < 2049) { /* dist 193..2049. */- if (dist < 257) return 15;- else if (dist < 385) return 16;- else if (dist < 513) return 17;- else if (dist < 769) return 18;- else if (dist < 1025) return 19;- else if (dist < 1537) return 20;- else return 21;- } else { /* dist 2049..32768. */- if (dist < 3073) return 22;- else if (dist < 4097) return 23;- else if (dist < 6145) return 24;- else if (dist < 8193) return 25;- else if (dist < 12289) return 26;- else if (dist < 16385) return 27;- else if (dist < 24577) return 28;- else return 29;- }- }-#endif-}--int ZopfliGetLengthExtraBits(int l) {- static const int table[259] = {- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,- 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,- 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,- 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,- 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,- 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,- 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,- 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,- 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,- 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,- 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,- 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,- 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,- 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,- 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,- 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 0- };- return table[l];-}--int ZopfliGetLengthExtraBitsValue(int l) {- static const int table[259] = {- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 2, 3, 0,- 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5,- 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6,- 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,- 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2,- 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,- 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28,- 29, 30, 31, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,- 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 0, 1, 2, 3, 4, 5, 6,- 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26,- 27, 28, 29, 30, 31, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,- 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 0- };- return table[l];-}--/*-Returns symbol in range [257-285] (inclusive).-*/-int ZopfliGetLengthSymbol(int l) {- static const int table[259] = {- 0, 0, 0, 257, 258, 259, 260, 261, 262, 263, 264,- 265, 265, 266, 266, 267, 267, 268, 268,- 269, 269, 269, 269, 270, 270, 270, 270,- 271, 271, 271, 271, 272, 272, 272, 272,- 273, 273, 273, 273, 273, 273, 273, 273,- 274, 274, 274, 274, 274, 274, 274, 274,- 275, 275, 275, 275, 275, 275, 275, 275,- 276, 276, 276, 276, 276, 276, 276, 276,- 277, 277, 277, 277, 277, 277, 277, 277,- 277, 277, 277, 277, 277, 277, 277, 277,- 278, 278, 278, 278, 278, 278, 278, 278,- 278, 278, 278, 278, 278, 278, 278, 278,- 279, 279, 279, 279, 279, 279, 279, 279,- 279, 279, 279, 279, 279, 279, 279, 279,- 280, 280, 280, 280, 280, 280, 280, 280,- 280, 280, 280, 280, 280, 280, 280, 280,- 281, 281, 281, 281, 281, 281, 281, 281,- 281, 281, 281, 281, 281, 281, 281, 281,- 281, 281, 281, 281, 281, 281, 281, 281,- 281, 281, 281, 281, 281, 281, 281, 281,- 282, 282, 282, 282, 282, 282, 282, 282,- 282, 282, 282, 282, 282, 282, 282, 282,- 282, 282, 282, 282, 282, 282, 282, 282,- 282, 282, 282, 282, 282, 282, 282, 282,- 283, 283, 283, 283, 283, 283, 283, 283,- 283, 283, 283, 283, 283, 283, 283, 283,- 283, 283, 283, 283, 283, 283, 283, 283,- 283, 283, 283, 283, 283, 283, 283, 283,- 284, 284, 284, 284, 284, 284, 284, 284,- 284, 284, 284, 284, 284, 284, 284, 284,- 284, 284, 284, 284, 284, 284, 284, 284,- 284, 284, 284, 284, 284, 284, 284, 285- };- return table[l];-}- void ZopfliInitOptions(ZopfliOptions* options) { options->verbose = 0; options->verbose_more = 0;
src/cbits/util.h view
@@ -32,6 +32,10 @@ #define ZOPFLI_MAX_MATCH 258 #define ZOPFLI_MIN_MATCH 3 +/* Number of distinct literal/length and distance symbols in DEFLATE */+#define ZOPFLI_NUM_LL 288+#define ZOPFLI_NUM_D 32+ /* The window size for deflate. Must be a power of two. This should be 32768, the maximum possible by the deflate spec. Anything less hurts compression more than@@ -51,9 +55,9 @@ The whole compression algorithm, including the smarter block splitting, will be executed independently on each huge block. Dividing into huge blocks hurts compression, but not much relative to the size.-Set this to, for example, 20MB (20000000). Set it to 0 to disable master blocks.+Set it to 0 to disable master blocks. */-#define ZOPFLI_MASTER_BLOCK_SIZE 20000000+#define ZOPFLI_MASTER_BLOCK_SIZE 1000000 /* Used to initialize costs for example@@ -115,27 +119,6 @@ varies from file to file. */ #define ZOPFLI_LAZY_MATCHING--/*-Gets the symbol for the given length, cfr. the DEFLATE spec.-Returns the symbol in the range [257-285] (inclusive)-*/-int ZopfliGetLengthSymbol(int l);--/* Gets the amount of extra bits for the given length, cfr. the DEFLATE spec. */-int ZopfliGetLengthExtraBits(int l);--/* Gets value of the extra bits for the given length, cfr. the DEFLATE spec. */-int ZopfliGetLengthExtraBitsValue(int l);--/* Gets the symbol for the given dist, cfr. the DEFLATE spec. */-int ZopfliGetDistSymbol(int dist);--/* Gets the amount of extra bits for the given dist, cfr. the DEFLATE spec. */-int ZopfliGetDistExtraBits(int dist);--/* Gets value of the extra bits for the given dist, cfr. the DEFLATE spec. */-int ZopfliGetDistExtraBitsValue(int dist); /* Appends value to dynamically allocated memory, doubling its allocation size
src/cbits/zlib_container.c view
@@ -53,7 +53,7 @@ unsigned char bitpointer = 0; unsigned checksum = adler32(in, (unsigned)insize); unsigned cmf = 120; /* CM 8, CINFO 7. See zlib spec.*/- unsigned flevel = 0;+ unsigned flevel = 3; unsigned fdict = 0; unsigned cmfflg = 256 * cmf + fdict * 32 + flevel * 64; unsigned fcheck = 31 - cmfflg % 31;
src/cbits/zopfli.h view
@@ -52,10 +52,7 @@ int blocksplitting; /*- If true, chooses the optimal block split points only after doing the iterative- LZ77 compression. If false, chooses the block split points first, then does- iterative LZ77 on each individual block. Depending on the file, either first- or last gives the best compression. Default: false (0).+ No longer used, left for compatibility. */ int blocksplittinglast;
src/cbits/zopfli_lib.c view
@@ -27,9 +27,7 @@ void ZopfliCompress(const ZopfliOptions* options, ZopfliFormat output_type, const unsigned char* in, size_t insize,- unsigned char** out, size_t* outsize)-{-+ unsigned char** out, size_t* outsize) { if (output_type == ZOPFLI_FORMAT_GZIP) { ZopfliGzipCompress(options, in, insize, out, outsize); } else if (output_type == ZOPFLI_FORMAT_ZLIB) {
test/HopfliSpec.hs view
@@ -31,9 +31,9 @@ spec :: Spec spec = describe "compress" $ do- it "should compress in zlib compatible format" $ property $+ it "Compresses in zlib compatible format" . property $ \payload -> (makeStrict Zlib.decompress . compress $ payload) == payload- it "should compress in gzip compatible format" $ property $+ it "Compresses in gzip compatible format" . property $ \payload -> (makeStrict GZip.decompress . compressWith defaultCompressOptions GZIP $ payload) == payload- it "should compress in deflate compatible format" $ property $+ it "Compresses in deflate compatible format" . property $ \payload -> (makeStrict ZRaw.decompress . compressWith defaultCompressOptions DEFLATE $ payload) == payload