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 "lz77.h" 218c218eff39749e738c92bf34155099ad280c16f7Lode Vandevenne#include "util.h" 22b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 23b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#include <assert.h> 24b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#include <stdio.h> 25b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#include <stdlib.h> 26b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 27981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennevoid ZopfliInitLZ77Store(ZopfliLZ77Store* store) { 28b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne store->size = 0; 29b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne store->litlens = 0; 30b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne store->dists = 0; 31b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 32b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 33981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennevoid ZopfliCleanLZ77Store(ZopfliLZ77Store* store) { 34b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne free(store->litlens); 35b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne free(store->dists); 36b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 37b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 38981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennevoid ZopfliCopyLZ77Store( 39981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne const ZopfliLZ77Store* source, ZopfliLZ77Store* dest) { 40b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t i; 41981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliCleanLZ77Store(dest); 42b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne dest->litlens = 43b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne (unsigned short*)malloc(sizeof(*dest->litlens) * source->size); 44b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne dest->dists = (unsigned short*)malloc(sizeof(*dest->dists) * source->size); 45b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 46b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (!dest->litlens || !dest->dists) exit(-1); /* Allocation failed. */ 47b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 48b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne dest->size = source->size; 49b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < source->size; i++) { 50b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne dest->litlens[i] = source->litlens[i]; 51b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne dest->dists[i] = source->dists[i]; 52b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 53b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 54b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 55b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 56981df0fe897c94382b9b963eb72bc36cbc2e729cLode VandevenneAppends the length and distance to the LZ77 arrays of the ZopfliLZ77Store. 57981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennecontext must be a ZopfliLZ77Store*. 58b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 59981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennevoid ZopfliStoreLitLenDist(unsigned short length, unsigned short dist, 60981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliLZ77Store* store) { 61981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne size_t size2 = store->size; /* Needed for using ZOPFLI_APPEND_DATA twice. */ 62981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZOPFLI_APPEND_DATA(length, &store->litlens, &store->size); 63981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZOPFLI_APPEND_DATA(dist, &store->dists, &size2); 64b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 65b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 66b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 67806be49c750347eb78f4d94bb21ad37aa9121f93Lode VandevenneGets a score of the length given the distance. Typically, the score of the 68806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevennelength is the length itself, but if the distance is very long, decrease the 69806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevennescore of the length a bit to make up for the fact that long distances use large 70806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenneamounts of extra bits. 71806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne 72806be49c750347eb78f4d94bb21ad37aa9121f93Lode VandevenneThis is not an accurate score, it is a heuristic only for the greedy LZ77 73806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenneimplementation. More accurate cost models are employed later. Making this 74806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenneheuristic more accurate may hurt rather than improve compression. 75806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne 76806be49c750347eb78f4d94bb21ad37aa9121f93Lode VandevenneThe two direct uses of this heuristic are: 77806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne-avoid using a length of 3 in combination with a long distance. This only has 78806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne an effect if length == 3. 79806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne-make a slightly better choice between the two options of the lazy matching. 80806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne 81806be49c750347eb78f4d94bb21ad37aa9121f93Lode VandevenneIndirectly, this affects: 82806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne-the block split points if the default of block splitting first is used, in a 83806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne rather unpredictable way 84806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne-the first zopfli run, so it affects the chance of the first run being closer 85806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne to the optimal output 86b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 87806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevennestatic int GetLengthScore(int length, int distance) { 88b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* 89806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne At 1024, the distance uses 9+ extra bits and this seems to be the sweet spot 90806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne on tested files. 91b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne */ 92b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne return distance > 1024 ? length - 1 : length; 93b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 94b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 95981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennevoid ZopfliVerifyLenDist(const unsigned char* data, size_t datasize, size_t pos, 96981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne unsigned short dist, unsigned short length) { 97b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 98b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* TODO(lode): make this only run in a debug compile, it's for assert only. */ 99b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t i; 100b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 101b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(pos + length <= datasize); 102b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < length; i++) { 103b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (data[pos - dist + i] != data[pos + i]) { 104b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(data[pos - dist + i] == data[pos + i]); 105b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne break; 106b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 107b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 108b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 109b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 110b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 111b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneFinds how long the match of scan and match is. Can be used to find how many 112b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennebytes starting from scan, and from match, are equal. Returns the last byte 113b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenneafter scan, which is still equal to the correspondinb byte after match. 114b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennescan is the position to compare 115b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennematch is the earlier position to compare. 116b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenneend is the last possible byte, beyond which to stop looking. 117b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennesafe_end is a few (8) bytes before end, for comparing multiple bytes at once. 118b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 119b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennestatic const unsigned char* GetMatch(const unsigned char* scan, 120b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne const unsigned char* match, 121b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne const unsigned char* end, 122b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne const unsigned char* safe_end) { 123b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 124b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (sizeof(size_t) == 8) { 125b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* 8 checks at once per array bounds check (size_t is 64-bit). */ 126b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne while (scan < safe_end && *((size_t*)scan) == *((size_t*)match)) { 127b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne scan += 8; 128b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne match += 8; 129b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 130b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } else if (sizeof(unsigned int) == 4) { 131b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* 4 checks at once per array bounds check (unsigned int is 32-bit). */ 132b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne while (scan < safe_end 133b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne && *((unsigned int*)scan) == *((unsigned int*)match)) { 134b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne scan += 4; 135b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne match += 4; 136b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 137b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } else { 138b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* do 8 checks at once per array bounds check. */ 139b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne while (scan < safe_end && *scan == *match && *++scan == *++match 140b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne && *++scan == *++match && *++scan == *++match 141b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne && *++scan == *++match && *++scan == *++match 142b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne && *++scan == *++match && *++scan == *++match) { 143b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne scan++; match++; 144b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 145b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 146b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 147b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* The remaining few bytes. */ 148b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne while (scan != end && *scan == *match) { 149b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne scan++; match++; 150b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 151b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 152b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne return scan; 153b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 154b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 155981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne#ifdef ZOPFLI_LONGEST_MATCH_CACHE 156b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 157b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneGets distance, length and sublen values from the cache if possible. 158b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneReturns 1 if it got the values from the cache, 0 if not. 159b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneUpdates the limit value to a smaller one if possible with more limited 160b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenneinformation from the cache. 161b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 162981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennestatic int TryGetFromLongestMatchCache(ZopfliBlockState* s, 163981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne size_t pos, size_t* limit, 164b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne unsigned short* sublen, unsigned short* distance, unsigned short* length) { 165b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* The LMC cache starts at the beginning of the block rather than the 166b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne beginning of the whole array. */ 167b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t lmcpos = pos - s->blockstart; 168b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 169b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Length > 0 and dist 0 is invalid combination, which indicates on purpose 170b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne that this cache value is not filled in yet. */ 171b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne unsigned char cache_available = s->lmc && (s->lmc->length[lmcpos] == 0 || 172b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne s->lmc->dist[lmcpos] != 0); 173981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne unsigned char limit_ok_for_cache = cache_available && 174981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne (*limit == ZOPFLI_MAX_MATCH || s->lmc->length[lmcpos] <= *limit || 175981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne (sublen && ZopfliMaxCachedSublen(s->lmc, 176b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne lmcpos, s->lmc->length[lmcpos]) >= *limit)); 177b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 178b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (s->lmc && limit_ok_for_cache && cache_available) { 179b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (!sublen || s->lmc->length[lmcpos] 180981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne <= ZopfliMaxCachedSublen(s->lmc, lmcpos, s->lmc->length[lmcpos])) { 181b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne *length = s->lmc->length[lmcpos]; 182b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (*length > *limit) *length = *limit; 183b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (sublen) { 184981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliCacheToSublen(s->lmc, lmcpos, *length, sublen); 185b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne *distance = sublen[*length]; 186981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne if (*limit == ZOPFLI_MAX_MATCH && *length >= ZOPFLI_MIN_MATCH) { 187b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(sublen[*length] == s->lmc->dist[lmcpos]); 188b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 189b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } else { 190b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne *distance = s->lmc->dist[lmcpos]; 191b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 192b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne return 1; 193b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 194b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Can't use much of the cache, since the "sublens" need to be calculated, 195b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne but at least we already know when to stop. */ 196b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne *limit = s->lmc->length[lmcpos]; 197b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 198b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 199b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne return 0; 200b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 201b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 202b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 203b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneStores the found sublen, distance and length in the longest match cache, if 204b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennepossible. 205b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 206981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennestatic void StoreInLongestMatchCache(ZopfliBlockState* s, 207981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne size_t pos, size_t limit, 208b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne const unsigned short* sublen, 209b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne unsigned short distance, unsigned short length) { 210b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* The LMC cache starts at the beginning of the block rather than the 211b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne beginning of the whole array. */ 212b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t lmcpos = pos - s->blockstart; 213b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 214b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Length > 0 and dist 0 is invalid combination, which indicates on purpose 215b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne that this cache value is not filled in yet. */ 216b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne unsigned char cache_available = s->lmc && (s->lmc->length[lmcpos] == 0 || 217b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne s->lmc->dist[lmcpos] != 0); 218b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 219981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne if (s->lmc && limit == ZOPFLI_MAX_MATCH && sublen && !cache_available) { 220b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(s->lmc->length[lmcpos] == 1 && s->lmc->dist[lmcpos] == 0); 221981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne s->lmc->dist[lmcpos] = length < ZOPFLI_MIN_MATCH ? 0 : distance; 222981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne s->lmc->length[lmcpos] = length < ZOPFLI_MIN_MATCH ? 0 : length; 223b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(!(s->lmc->length[lmcpos] == 1 && s->lmc->dist[lmcpos] == 0)); 224981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliSublenToCache(sublen, lmcpos, length, s->lmc); 225b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 226b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 227b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#endif 228b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 229981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennevoid ZopfliFindLongestMatch(ZopfliBlockState* s, const ZopfliHash* h, 230981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne const unsigned char* array, 231b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t pos, size_t size, size_t limit, 232b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne unsigned short* sublen, unsigned short* distance, unsigned short* length) { 233981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne unsigned short hpos = pos & ZOPFLI_WINDOW_MASK, p, pp; 234b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne unsigned short bestdist = 0; 235b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne unsigned short bestlength = 1; 236b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne const unsigned char* scan; 237b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne const unsigned char* match; 238b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne const unsigned char* arrayend; 239b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne const unsigned char* arrayend_safe; 240981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne#if ZOPFLI_MAX_CHAIN_HITS < ZOPFLI_WINDOW_SIZE 241981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne int chain_counter = ZOPFLI_MAX_CHAIN_HITS; /* For quitting early. */ 242b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#endif 243b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 244b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne unsigned dist = 0; /* Not unsigned short on purpose. */ 245b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 246b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne int* hhead = h->head; 247b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne unsigned short* hprev = h->prev; 248b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne int* hhashval = h->hashval; 249b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne int hval = h->val; 250b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 251981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne#ifdef ZOPFLI_LONGEST_MATCH_CACHE 252b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (TryGetFromLongestMatchCache(s, pos, &limit, sublen, distance, length)) { 253b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(pos + *length <= size); 254b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne return; 255b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 256b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#endif 257b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 258981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne assert(limit <= ZOPFLI_MAX_MATCH); 259981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne assert(limit >= ZOPFLI_MIN_MATCH); 260b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(pos < size); 261b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 262981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne if (size - pos < ZOPFLI_MIN_MATCH) { 263981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne /* The rest of the code assumes there are at least ZOPFLI_MIN_MATCH bytes to 264b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne try. */ 265b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne *length = 0; 266b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne *distance = 0; 267b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne return; 268b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 269b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 270b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (pos + limit > size) { 271b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne limit = size - pos; 272b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 273b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne arrayend = &array[pos] + limit; 274b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne arrayend_safe = arrayend - 8; 275b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 276b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(hval < 65536); 277b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 278b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne pp = hhead[hval]; /* During the whole loop, p == hprev[pp]. */ 279b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne p = hprev[pp]; 280b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 281b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(pp == hpos); 282b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 283981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne dist = p < pp ? pp - p : ((ZOPFLI_WINDOW_SIZE - p) + pp); 284b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 285b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Go through all distances. */ 286981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne while (dist < ZOPFLI_WINDOW_SIZE) { 287b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne unsigned short currentlength = 0; 288b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 289981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne assert(p < ZOPFLI_WINDOW_SIZE); 290b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(p == hprev[pp]); 291b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(hhashval[p] == hval); 292b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 293b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (dist > 0) { 294b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(pos < size); 295b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(dist <= pos); 296b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne scan = &array[pos]; 297b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne match = &array[pos - dist]; 298b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 299b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Testing the byte at position bestlength first, goes slightly faster. */ 300b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (pos + bestlength >= size 301b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne || *(scan + bestlength) == *(match + bestlength)) { 302b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 303981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne#ifdef ZOPFLI_HASH_SAME 304981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne unsigned short same0 = h->same[pos & ZOPFLI_WINDOW_MASK]; 305b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (same0 > 2 && *scan == *match) { 306981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne unsigned short same1 = h->same[(pos - dist) & ZOPFLI_WINDOW_MASK]; 307b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne unsigned short same = same0 < same1 ? same0 : same1; 308b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (same > limit) same = limit; 309b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne scan += same; 310b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne match += same; 311b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 312b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#endif 313b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne scan = GetMatch(scan, match, arrayend, arrayend_safe); 314b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne currentlength = scan - &array[pos]; /* The found length. */ 315b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 316b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 317b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (currentlength > bestlength) { 318b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (sublen) { 319b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne unsigned short j; 320b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (j = bestlength + 1; j <= currentlength; j++) { 321b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne sublen[j] = dist; 322b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 323b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 324b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne bestdist = dist; 325b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne bestlength = currentlength; 326b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (currentlength >= limit) break; 327b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 328b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 329b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 330b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 331981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne#ifdef ZOPFLI_HASH_SAME_HASH 332b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Switch to the other hash once this will be more efficient. */ 333b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (hhead != h->head2 && bestlength >= h->same[hpos] && 334b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->val2 == h->hashval2[p]) { 335b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Now use the hash that encodes the length and first byte. */ 336b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne hhead = h->head2; 337b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne hprev = h->prev2; 338b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne hhashval = h->hashval2; 339b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne hval = h->val2; 340b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 341b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#endif 342b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 343b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne pp = p; 344b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne p = hprev[p]; 345b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (p == pp) break; /* Uninited prev value. */ 346b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 347981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne dist += p < pp ? pp - p : ((ZOPFLI_WINDOW_SIZE - p) + pp); 348b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 349981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne#if ZOPFLI_MAX_CHAIN_HITS < ZOPFLI_WINDOW_SIZE 350b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne chain_counter--; 351b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (chain_counter <= 0) break; 352b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#endif 353b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 354b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 355981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne#ifdef ZOPFLI_LONGEST_MATCH_CACHE 356b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne StoreInLongestMatchCache(s, pos, limit, sublen, bestdist, bestlength); 357b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#endif 358b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 359b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(bestlength <= limit); 360b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 361b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne *distance = bestdist; 362b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne *length = bestlength; 363b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(pos + *length <= size); 364b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 365b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 366981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennevoid ZopfliLZ77Greedy(ZopfliBlockState* s, const unsigned char* in, 367981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne size_t instart, size_t inend, 368981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliLZ77Store* store) { 369b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t i = 0, j; 370b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne unsigned short leng; 371b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne unsigned short dist; 372806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne int lengthscore; 373981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne size_t windowstart = instart > ZOPFLI_WINDOW_SIZE 374981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ? instart - ZOPFLI_WINDOW_SIZE : 0; 375b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne unsigned short dummysublen[259]; 376b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 377981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliHash hash; 378981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliHash* h = &hash; 379b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 380981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne#ifdef ZOPFLI_LAZY_MATCHING 381b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Lazy matching. */ 382b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne unsigned prev_length = 0; 383b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne unsigned prev_match = 0; 384806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne int prevlengthscore; 385b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne int match_available = 0; 386b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#endif 387b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 388b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (instart == inend) return; 389b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 390981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliInitHash(ZOPFLI_WINDOW_SIZE, h); 391981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliWarmupHash(in, windowstart, inend, h); 392b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = windowstart; i < instart; i++) { 393981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliUpdateHash(in, i, inend, h); 394b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 395b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 396b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = instart; i < inend; i++) { 397981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliUpdateHash(in, i, inend, h); 398b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 399981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliFindLongestMatch(s, h, in, i, inend, ZOPFLI_MAX_MATCH, dummysublen, 400981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne &dist, &leng); 401806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne lengthscore = GetLengthScore(leng, dist); 402b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 403981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne#ifdef ZOPFLI_LAZY_MATCHING 404b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Lazy matching. */ 405806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne prevlengthscore = GetLengthScore(prev_length, prev_match); 406b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (match_available) { 407b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne match_available = 0; 408806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne if (lengthscore > prevlengthscore + 1) { 409981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliStoreLitLenDist(in[i - 1], 0, store); 410806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne if (lengthscore >= ZOPFLI_MIN_MATCH && leng < ZOPFLI_MAX_MATCH) { 411b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne match_available = 1; 412b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne prev_length = leng; 413b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne prev_match = dist; 414b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne continue; 415b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 416b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } else { 417b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Add previous to output. */ 418b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne leng = prev_length; 419b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne dist = prev_match; 420806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne lengthscore = prevlengthscore; 421b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Add to output. */ 422981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliVerifyLenDist(in, inend, i - 1, dist, leng); 423981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliStoreLitLenDist(leng, dist, store); 424b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (j = 2; j < leng; j++) { 425b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(i < inend); 426b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne i++; 427981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliUpdateHash(in, i, inend, h); 428b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 429b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne continue; 430b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 431b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 432806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne else if (lengthscore >= ZOPFLI_MIN_MATCH && leng < ZOPFLI_MAX_MATCH) { 433b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne match_available = 1; 434b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne prev_length = leng; 435b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne prev_match = dist; 436b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne continue; 437b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 438b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* End of lazy matching. */ 439b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#endif 440b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 441b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Add to output. */ 442806be49c750347eb78f4d94bb21ad37aa9121f93Lode Vandevenne if (lengthscore >= ZOPFLI_MIN_MATCH) { 443981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliVerifyLenDist(in, inend, i, dist, leng); 444981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliStoreLitLenDist(leng, dist, store); 445b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } else { 446b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne leng = 1; 447981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliStoreLitLenDist(in[i], 0, store); 448b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 449b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (j = 1; j < leng; j++) { 450b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne assert(i < inend); 451b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne i++; 452981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliUpdateHash(in, i, inend, h); 453b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 454b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 455b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 456981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliCleanHash(h); 457b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 458b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 459981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennevoid ZopfliLZ77Counts(const unsigned short* litlens, 460981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne const unsigned short* dists, 461981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne size_t start, size_t end, 462981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne size_t* ll_count, size_t* d_count) { 463b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t i; 464b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 465b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < 288; i++) { 466b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne ll_count[i] = 0; 467b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 468b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < 32; i++) { 469b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne d_count[i] = 0; 470b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 471b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 472b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = start; i < end; i++) { 473b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (dists[i] == 0) { 474b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne ll_count[litlens[i]]++; 475b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } else { 476981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ll_count[ZopfliGetLengthSymbol(litlens[i])]++; 477981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne d_count[ZopfliGetDistSymbol(dists[i])]++; 478b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 479b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 480b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 481b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne ll_count[256] = 1; /* End symbol. */ 482b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 483