1b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 2b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneCopyright 2011 Google Inc. All Rights Reserved. 3b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 4b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneLicensed under the Apache License, Version 2.0 (the "License"); 5b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenneyou may not use this file except in compliance with the License. 6b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneYou may obtain a copy of the License at 7b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 8b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne http://www.apache.org/licenses/LICENSE-2.0 9b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 10b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneUnless required by applicable law or agreed to in writing, software 11b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennedistributed under the License is distributed on an "AS IS" BASIS, 12b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneWITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneSee the License for the specific language governing permissions and 14b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennelimitations under the License. 15b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 16b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneAuthor: lode.vandevenne@gmail.com (Lode Vandevenne) 17b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneAuthor: jyrki.alakuijala@gmail.com (Jyrki Alakuijala) 18b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 19b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 20b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#include "blocksplitter.h" 21b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 22b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#include <assert.h> 23b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#include <stdio.h> 24b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#include <stdlib.h> 25b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 26b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#include "deflate.h" 27b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#include "lz77.h" 28b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#include "squeeze.h" 29b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#include "tree.h" 308c218eff39749e738c92bf34155099ad280c16f7Lode Vandevenne#include "util.h" 31b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 32b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 33b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneThe "f" for the FindMinimum function below. 34b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennei: the current parameter of f(i) 35b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennecontext: for your implementation 36b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 37b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennetypedef double FindMinimumFun(size_t i, void* context); 38b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 39b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 40b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneFinds minimum of function f(i) where is is of type size_t, f(i) is of type 41b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennedouble, i is in range start-end (excluding end). 42b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 43b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennestatic size_t FindMinimum(FindMinimumFun f, void* context, 44b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t start, size_t end) { 45b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (end - start < 1024) { 46981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne double best = ZOPFLI_LARGE_FLOAT; 47b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t result = start; 48b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t i; 49b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = start; i < end; i++) { 50b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne double v = f(i, context); 51b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (v < best) { 52b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne best = v; 53b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne result = i; 54b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 55b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 56b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne return result; 57b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } else { 58b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Try to find minimum faster by recursively checking multiple points. */ 59b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#define NUM 9 /* Good value: 9. */ 60b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t i; 61b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t p[NUM]; 62b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne double vp[NUM]; 63b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t besti; 64b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne double best; 65981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne double lastbest = ZOPFLI_LARGE_FLOAT; 66b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t pos = start; 67b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 68b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (;;) { 69b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (end - start <= NUM) break; 70b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 71b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < NUM; i++) { 72b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne p[i] = start + (i + 1) * ((end - start) / (NUM + 1)); 73b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne vp[i] = f(p[i], context); 74b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 75b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne besti = 0; 76b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne best = vp[0]; 77b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 1; i < NUM; i++) { 78b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (vp[i] < best) { 79b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne best = vp[i]; 80b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne besti = i; 81b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 82b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 83b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (best > lastbest) break; 84b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 85b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne start = besti == 0 ? start : p[besti - 1]; 86b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne end = besti == NUM - 1 ? end : p[besti + 1]; 87b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 88b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne pos = p[besti]; 89b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne lastbest = best; 90b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 91b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne return pos; 92b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#undef NUM 93b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 94b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 95b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 96b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 97b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneReturns estimated cost of a block in bits. It includes the size to encode the 98b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennetree and the size to encode all literal, length and distance symbols and their 99b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenneextra bits. 100b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 101b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennelitlens: lz77 lit/lengths 102b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennedists: ll77 distances 103b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennelstart: start of block 104b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennelend: end of block (not inclusive) 105b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 106981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennestatic double EstimateCost(const unsigned short* litlens, 107981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne const unsigned short* dists, 108981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne size_t lstart, size_t lend) { 109981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne return ZopfliCalculateBlockSize(litlens, dists, lstart, lend, 2); 110b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 111b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 112b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennetypedef struct SplitCostContext { 113b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne const unsigned short* litlens; 114b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne const unsigned short* dists; 115b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t llsize; 116b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t start; 117b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t end; 118b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} SplitCostContext; 119b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 120b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 121b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 122b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneGets the cost which is the sum of the cost of the left and the right section 123b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenneof the data. 124b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennetype: FindMinimumFun 125b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 126b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennestatic double SplitCost(size_t i, void* context) { 127b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne SplitCostContext* c = (SplitCostContext*)context; 128b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne return EstimateCost(c->litlens, c->dists, c->start, i) + 129b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne EstimateCost(c->litlens, c->dists, i, c->end); 130b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 131b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 132b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennestatic void AddSorted(size_t value, size_t** out, size_t* outsize) { 133b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t i; 134981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZOPFLI_APPEND_DATA(value, out, outsize); 135ae16c9e727664ec78d8ceb8916dbc9c9ec7c71c0Lode Vandevenne for (i = 0; i + 1 < *outsize; i++) { 136ae16c9e727664ec78d8ceb8916dbc9c9ec7c71c0Lode Vandevenne if ((*out)[i] > value) { 137ae16c9e727664ec78d8ceb8916dbc9c9ec7c71c0Lode Vandevenne size_t j; 138ae16c9e727664ec78d8ceb8916dbc9c9ec7c71c0Lode Vandevenne for (j = *outsize - 1; j > i; j--) { 139ae16c9e727664ec78d8ceb8916dbc9c9ec7c71c0Lode Vandevenne (*out)[j] = (*out)[j - 1]; 140b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 141ae16c9e727664ec78d8ceb8916dbc9c9ec7c71c0Lode Vandevenne (*out)[i] = value; 142ae16c9e727664ec78d8ceb8916dbc9c9ec7c71c0Lode Vandevenne break; 143b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 144b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 145b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 146b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 147b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 148b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevennePrints the block split points as decimal and hex values in the terminal. 149b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 150b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennestatic void PrintBlockSplitPoints(const unsigned short* litlens, 151b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne const unsigned short* dists, 152b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t llsize, const size_t* lz77splitpoints, 153b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t nlz77points) { 154b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t* splitpoints = 0; 155b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t npoints = 0; 156b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t i; 157b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* The input is given as lz77 indices, but we want to see the uncompressed 158b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne index values. */ 159b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t pos = 0; 160b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (nlz77points > 0) { 161b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < llsize; i++) { 162b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t length = dists[i] == 0 ? 1 : litlens[i]; 163b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (lz77splitpoints[npoints] == i) { 164981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZOPFLI_APPEND_DATA(pos, &splitpoints, &npoints); 165b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (npoints == nlz77points) break; 166b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 167b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne pos += length; 168b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 169b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 170b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(npoints == nlz77points); 171b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 172b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne fprintf(stderr, "block split points: "); 173b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < npoints; i++) { 174b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne fprintf(stderr, "%d ", (int)splitpoints[i]); 175b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 176b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne fprintf(stderr, "(hex:"); 177b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < npoints; i++) { 178b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne fprintf(stderr, " %x", (int)splitpoints[i]); 179b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 180b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne fprintf(stderr, ")\n"); 181b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 182b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne free(splitpoints); 183b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 184b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 185b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 186b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneFinds next block to try to split, the largest of the available ones. 187b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneThe largest is chosen to make sure that if only a limited amount of blocks is 188b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennerequested, their sizes are spread evenly. 189b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennellsize: the size of the LL77 data, which is the size of the done array here. 190b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennedone: array indicating which blocks starting at that position are no longer 191b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne splittable (splitting them increases rather than decreases cost). 192b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennesplitpoints: the splitpoints found so far. 193b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennenpoints: the amount of splitpoints found so far. 194b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennelstart: output variable, giving start of block. 195b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennelend: output variable, giving end of block. 196b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennereturns 1 if a block was found, 0 if no block found (all are done). 197b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 198b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennestatic int FindLargestSplittableBlock( 199b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t llsize, const unsigned char* done, 200b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne const size_t* splitpoints, size_t npoints, 201b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t* lstart, size_t* lend) { 202b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t longest = 0; 203b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne int found = 0; 204b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t i; 205b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i <= npoints; i++) { 206b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t start = i == 0 ? 0 : splitpoints[i - 1]; 207b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t end = i == npoints ? llsize - 1 : splitpoints[i]; 208b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (!done[start] && end - start > longest) { 209b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne *lstart = start; 210b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne *lend = end; 211b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne found = 1; 212b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne longest = end - start; 213b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 214b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 215b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne return found; 216b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 217b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 218981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennevoid ZopfliBlockSplitLZ77(const ZopfliOptions* options, 219981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne const unsigned short* litlens, 220981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne const unsigned short* dists, 221981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne size_t llsize, size_t maxblocks, 222981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne size_t** splitpoints, size_t* npoints) { 223b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t lstart, lend; 224b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t i; 225b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t llpos = 0; 226b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t numblocks = 1; 227d5eb5f507386e9933f2d8248d311ceca41fe1df1Lode Vandevenne unsigned char* done; 228b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne double splitcost, origcost; 229b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 230b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (llsize < 10) return; /* This code fails on tiny files. */ 231b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 232d5eb5f507386e9933f2d8248d311ceca41fe1df1Lode Vandevenne done = (unsigned char*)malloc(llsize); 233d5eb5f507386e9933f2d8248d311ceca41fe1df1Lode Vandevenne if (!done) exit(-1); /* Allocation failed. */ 234b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < llsize; i++) done[i] = 0; 235b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 236b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne lstart = 0; 237b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne lend = llsize; 238b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (;;) { 239b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne SplitCostContext c; 240b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 241b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (maxblocks > 0 && numblocks >= maxblocks) { 242b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne break; 243b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 244b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 245b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne c.litlens = litlens; 246b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne c.dists = dists; 247b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne c.llsize = llsize; 248b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne c.start = lstart; 249b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne c.end = lend; 250b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(lstart < lend); 251b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne llpos = FindMinimum(SplitCost, &c, lstart + 1, lend); 252b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 253b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(llpos > lstart); 254b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(llpos < lend); 255b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 256b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne splitcost = EstimateCost(litlens, dists, lstart, llpos) + 257b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne EstimateCost(litlens, dists, llpos, lend); 258b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne origcost = EstimateCost(litlens, dists, lstart, lend); 259b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 260b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (splitcost > origcost || llpos == lstart + 1 || llpos == lend) { 261b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne done[lstart] = 1; 262b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } else { 263b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne AddSorted(llpos, splitpoints, npoints); 264b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne numblocks++; 265b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 266b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 267b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (!FindLargestSplittableBlock( 268b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne llsize, done, *splitpoints, *npoints, &lstart, &lend)) { 269b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne break; /* No further split will probably reduce compression. */ 270b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 271b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 272b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (lend - lstart < 10) { 273b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne break; 274b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 275b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 276b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 277b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (options->verbose) { 278b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne PrintBlockSplitPoints(litlens, dists, llsize, *splitpoints, *npoints); 279b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 280b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 281b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne free(done); 282b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 283b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 284981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennevoid ZopfliBlockSplit(const ZopfliOptions* options, 285981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne const unsigned char* in, size_t instart, size_t inend, 286981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne size_t maxblocks, size_t** splitpoints, size_t* npoints) { 287b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t pos = 0; 288b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t i; 289981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliBlockState s; 290b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t* lz77splitpoints = 0; 291b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t nlz77points = 0; 292981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliLZ77Store store; 293b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 294981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliInitLZ77Store(&store); 295b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 296b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne s.options = options; 297b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne s.blockstart = instart; 298b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne s.blockend = inend; 299981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne#ifdef ZOPFLI_LONGEST_MATCH_CACHE 300b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne s.lmc = 0; 301b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#endif 302b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 303b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne *npoints = 0; 304b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne *splitpoints = 0; 305b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 306981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne /* Unintuitively, Using a simple LZ77 method here instead of ZopfliLZ77Optimal 307b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne results in better blocks. */ 308981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliLZ77Greedy(&s, in, instart, inend, &store); 309b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 310981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliBlockSplitLZ77(options, 311981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne store.litlens, store.dists, store.size, maxblocks, 312981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne &lz77splitpoints, &nlz77points); 313b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 314b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Convert LZ77 positions to positions in the uncompressed input. */ 315b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne pos = instart; 316b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (nlz77points > 0) { 317b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < store.size; i++) { 318b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t length = store.dists[i] == 0 ? 1 : store.litlens[i]; 319b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (lz77splitpoints[*npoints] == i) { 320981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZOPFLI_APPEND_DATA(pos, splitpoints, npoints); 321b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (*npoints == nlz77points) break; 322b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 323b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne pos += length; 324b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 325b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 326b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(*npoints == nlz77points); 327b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 328b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne free(lz77splitpoints); 329981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliCleanLZ77Store(&store); 330b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 331b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 332981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennevoid ZopfliBlockSplitSimple(const unsigned char* in, 333981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne size_t instart, size_t inend, 334981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne size_t blocksize, 335981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne size_t** splitpoints, size_t* npoints) { 336b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t i = instart; 337b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne while (i < inend) { 338981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZOPFLI_APPEND_DATA(i, splitpoints, npoints); 339b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne i += blocksize; 340b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 341b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne (void)in; 342b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 343