1 /*
2 Copyright 2011 Google Inc. All Rights Reserved.
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15
16 Author: lode.vandevenne@gmail.com (Lode Vandevenne)
17 Author: jyrki.alakuijala@gmail.com (Jyrki Alakuijala)
18 */
19
20 #include "lz77.h"
21 #include "symbols.h"
22 #include "util.h"
23
24 #include <assert.h>
25 #include <stdio.h>
26 #include <stdlib.h>
27
ZopfliInitLZ77Store(const unsigned char * data,ZopfliLZ77Store * store)28 void ZopfliInitLZ77Store(const unsigned char* data, ZopfliLZ77Store* store) {
29 store->size = 0;
30 store->litlens = 0;
31 store->dists = 0;
32 store->pos = 0;
33 store->data = data;
34 store->ll_symbol = 0;
35 store->d_symbol = 0;
36 store->ll_counts = 0;
37 store->d_counts = 0;
38 }
39
ZopfliCleanLZ77Store(ZopfliLZ77Store * store)40 void ZopfliCleanLZ77Store(ZopfliLZ77Store* store) {
41 free(store->litlens);
42 free(store->dists);
43 free(store->pos);
44 free(store->ll_symbol);
45 free(store->d_symbol);
46 free(store->ll_counts);
47 free(store->d_counts);
48 }
49
CeilDiv(size_t a,size_t b)50 static size_t CeilDiv(size_t a, size_t b) {
51 return (a + b - 1) / b;
52 }
53
ZopfliCopyLZ77Store(const ZopfliLZ77Store * source,ZopfliLZ77Store * dest)54 void ZopfliCopyLZ77Store(
55 const ZopfliLZ77Store* source, ZopfliLZ77Store* dest) {
56 size_t i;
57 size_t llsize = ZOPFLI_NUM_LL * CeilDiv(source->size, ZOPFLI_NUM_LL);
58 size_t dsize = ZOPFLI_NUM_D * CeilDiv(source->size, ZOPFLI_NUM_D);
59 ZopfliCleanLZ77Store(dest);
60 ZopfliInitLZ77Store(source->data, dest);
61 dest->litlens =
62 (unsigned short*)malloc(sizeof(*dest->litlens) * source->size);
63 dest->dists = (unsigned short*)malloc(sizeof(*dest->dists) * source->size);
64 dest->pos = (size_t*)malloc(sizeof(*dest->pos) * source->size);
65 dest->ll_symbol =
66 (unsigned short*)malloc(sizeof(*dest->ll_symbol) * source->size);
67 dest->d_symbol =
68 (unsigned short*)malloc(sizeof(*dest->d_symbol) * source->size);
69 dest->ll_counts = (size_t*)malloc(sizeof(*dest->ll_counts) * llsize);
70 dest->d_counts = (size_t*)malloc(sizeof(*dest->d_counts) * dsize);
71
72 /* Allocation failed. */
73 if (!dest->litlens || !dest->dists) exit(-1);
74 if (!dest->pos) exit(-1);
75 if (!dest->ll_symbol || !dest->d_symbol) exit(-1);
76 if (!dest->ll_counts || !dest->d_counts) exit(-1);
77
78 dest->size = source->size;
79 for (i = 0; i < source->size; i++) {
80 dest->litlens[i] = source->litlens[i];
81 dest->dists[i] = source->dists[i];
82 dest->pos[i] = source->pos[i];
83 dest->ll_symbol[i] = source->ll_symbol[i];
84 dest->d_symbol[i] = source->d_symbol[i];
85 }
86 for (i = 0; i < llsize; i++) {
87 dest->ll_counts[i] = source->ll_counts[i];
88 }
89 for (i = 0; i < dsize; i++) {
90 dest->d_counts[i] = source->d_counts[i];
91 }
92 }
93
94 /*
95 Appends the length and distance to the LZ77 arrays of the ZopfliLZ77Store.
96 context must be a ZopfliLZ77Store*.
97 */
ZopfliStoreLitLenDist(unsigned short length,unsigned short dist,size_t pos,ZopfliLZ77Store * store)98 void ZopfliStoreLitLenDist(unsigned short length, unsigned short dist,
99 size_t pos, ZopfliLZ77Store* store) {
100 size_t i;
101 /* Needed for using ZOPFLI_APPEND_DATA multiple times. */
102 size_t origsize = store->size;
103 size_t llstart = ZOPFLI_NUM_LL * (origsize / ZOPFLI_NUM_LL);
104 size_t dstart = ZOPFLI_NUM_D * (origsize / ZOPFLI_NUM_D);
105
106 /* Everytime the index wraps around, a new cumulative histogram is made: we're
107 keeping one histogram value per LZ77 symbol rather than a full histogram for
108 each to save memory. */
109 if (origsize % ZOPFLI_NUM_LL == 0) {
110 size_t llsize = origsize;
111 for (i = 0; i < ZOPFLI_NUM_LL; i++) {
112 ZOPFLI_APPEND_DATA(
113 origsize == 0 ? 0 : store->ll_counts[origsize - ZOPFLI_NUM_LL + i],
114 &store->ll_counts, &llsize);
115 }
116 }
117 if (origsize % ZOPFLI_NUM_D == 0) {
118 size_t dsize = origsize;
119 for (i = 0; i < ZOPFLI_NUM_D; i++) {
120 ZOPFLI_APPEND_DATA(
121 origsize == 0 ? 0 : store->d_counts[origsize - ZOPFLI_NUM_D + i],
122 &store->d_counts, &dsize);
123 }
124 }
125
126 ZOPFLI_APPEND_DATA(length, &store->litlens, &store->size);
127 store->size = origsize;
128 ZOPFLI_APPEND_DATA(dist, &store->dists, &store->size);
129 store->size = origsize;
130 ZOPFLI_APPEND_DATA(pos, &store->pos, &store->size);
131 assert(length < 259);
132
133 if (dist == 0) {
134 store->size = origsize;
135 ZOPFLI_APPEND_DATA(length, &store->ll_symbol, &store->size);
136 store->size = origsize;
137 ZOPFLI_APPEND_DATA(0, &store->d_symbol, &store->size);
138 store->ll_counts[llstart + length]++;
139 } else {
140 store->size = origsize;
141 ZOPFLI_APPEND_DATA(ZopfliGetLengthSymbol(length),
142 &store->ll_symbol, &store->size);
143 store->size = origsize;
144 ZOPFLI_APPEND_DATA(ZopfliGetDistSymbol(dist),
145 &store->d_symbol, &store->size);
146 store->ll_counts[llstart + ZopfliGetLengthSymbol(length)]++;
147 store->d_counts[dstart + ZopfliGetDistSymbol(dist)]++;
148 }
149 }
150
ZopfliAppendLZ77Store(const ZopfliLZ77Store * store,ZopfliLZ77Store * target)151 void ZopfliAppendLZ77Store(const ZopfliLZ77Store* store,
152 ZopfliLZ77Store* target) {
153 size_t i;
154 for (i = 0; i < store->size; i++) {
155 ZopfliStoreLitLenDist(store->litlens[i], store->dists[i],
156 store->pos[i], target);
157 }
158 }
159
ZopfliLZ77GetByteRange(const ZopfliLZ77Store * lz77,size_t lstart,size_t lend)160 size_t ZopfliLZ77GetByteRange(const ZopfliLZ77Store* lz77,
161 size_t lstart, size_t lend) {
162 size_t l = lend - 1;
163 if (lstart == lend) return 0;
164 return lz77->pos[l] + ((lz77->dists[l] == 0) ?
165 1 : lz77->litlens[l]) - lz77->pos[lstart];
166 }
167
ZopfliLZ77GetHistogramAt(const ZopfliLZ77Store * lz77,size_t lpos,size_t * ll_counts,size_t * d_counts)168 static void ZopfliLZ77GetHistogramAt(const ZopfliLZ77Store* lz77, size_t lpos,
169 size_t* ll_counts, size_t* d_counts) {
170 /* The real histogram is created by using the histogram for this chunk, but
171 all superfluous values of this chunk subtracted. */
172 size_t llpos = ZOPFLI_NUM_LL * (lpos / ZOPFLI_NUM_LL);
173 size_t dpos = ZOPFLI_NUM_D * (lpos / ZOPFLI_NUM_D);
174 size_t i;
175 for (i = 0; i < ZOPFLI_NUM_LL; i++) {
176 ll_counts[i] = lz77->ll_counts[llpos + i];
177 }
178 for (i = lpos + 1; i < llpos + ZOPFLI_NUM_LL && i < lz77->size; i++) {
179 ll_counts[lz77->ll_symbol[i]]--;
180 }
181 for (i = 0; i < ZOPFLI_NUM_D; i++) {
182 d_counts[i] = lz77->d_counts[dpos + i];
183 }
184 for (i = lpos + 1; i < dpos + ZOPFLI_NUM_D && i < lz77->size; i++) {
185 if (lz77->dists[i] != 0) d_counts[lz77->d_symbol[i]]--;
186 }
187 }
188
ZopfliLZ77GetHistogram(const ZopfliLZ77Store * lz77,size_t lstart,size_t lend,size_t * ll_counts,size_t * d_counts)189 void ZopfliLZ77GetHistogram(const ZopfliLZ77Store* lz77,
190 size_t lstart, size_t lend,
191 size_t* ll_counts, size_t* d_counts) {
192 size_t i;
193 if (lstart + ZOPFLI_NUM_LL * 3 > lend) {
194 memset(ll_counts, 0, sizeof(*ll_counts) * ZOPFLI_NUM_LL);
195 memset(d_counts, 0, sizeof(*d_counts) * ZOPFLI_NUM_D);
196 for (i = lstart; i < lend; i++) {
197 ll_counts[lz77->ll_symbol[i]]++;
198 if (lz77->dists[i] != 0) d_counts[lz77->d_symbol[i]]++;
199 }
200 } else {
201 /* Subtract the cumulative histograms at the end and the start to get the
202 histogram for this range. */
203 ZopfliLZ77GetHistogramAt(lz77, lend - 1, ll_counts, d_counts);
204 if (lstart > 0) {
205 size_t ll_counts2[ZOPFLI_NUM_LL];
206 size_t d_counts2[ZOPFLI_NUM_D];
207 ZopfliLZ77GetHistogramAt(lz77, lstart - 1, ll_counts2, d_counts2);
208
209 for (i = 0; i < ZOPFLI_NUM_LL; i++) {
210 ll_counts[i] -= ll_counts2[i];
211 }
212 for (i = 0; i < ZOPFLI_NUM_D; i++) {
213 d_counts[i] -= d_counts2[i];
214 }
215 }
216 }
217 }
218
ZopfliInitBlockState(const ZopfliOptions * options,size_t blockstart,size_t blockend,int add_lmc,ZopfliBlockState * s)219 void ZopfliInitBlockState(const ZopfliOptions* options,
220 size_t blockstart, size_t blockend, int add_lmc,
221 ZopfliBlockState* s) {
222 s->options = options;
223 s->blockstart = blockstart;
224 s->blockend = blockend;
225 #ifdef ZOPFLI_LONGEST_MATCH_CACHE
226 if (add_lmc) {
227 s->lmc = (ZopfliLongestMatchCache*)malloc(sizeof(ZopfliLongestMatchCache));
228 ZopfliInitCache(blockend - blockstart, s->lmc);
229 } else {
230 s->lmc = 0;
231 }
232 #endif
233 }
234
ZopfliCleanBlockState(ZopfliBlockState * s)235 void ZopfliCleanBlockState(ZopfliBlockState* s) {
236 #ifdef ZOPFLI_LONGEST_MATCH_CACHE
237 if (s->lmc) {
238 ZopfliCleanCache(s->lmc);
239 free(s->lmc);
240 }
241 #endif
242 }
243
244 /*
245 Gets a score of the length given the distance. Typically, the score of the
246 length is the length itself, but if the distance is very long, decrease the
247 score of the length a bit to make up for the fact that long distances use large
248 amounts of extra bits.
249
250 This is not an accurate score, it is a heuristic only for the greedy LZ77
251 implementation. More accurate cost models are employed later. Making this
252 heuristic more accurate may hurt rather than improve compression.
253
254 The two direct uses of this heuristic are:
255 -avoid using a length of 3 in combination with a long distance. This only has
256 an effect if length == 3.
257 -make a slightly better choice between the two options of the lazy matching.
258
259 Indirectly, this affects:
260 -the block split points if the default of block splitting first is used, in a
261 rather unpredictable way
262 -the first zopfli run, so it affects the chance of the first run being closer
263 to the optimal output
264 */
GetLengthScore(int length,int distance)265 static int GetLengthScore(int length, int distance) {
266 /*
267 At 1024, the distance uses 9+ extra bits and this seems to be the sweet spot
268 on tested files.
269 */
270 return distance > 1024 ? length - 1 : length;
271 }
272
ZopfliVerifyLenDist(const unsigned char * data,size_t datasize,size_t pos,unsigned short dist,unsigned short length)273 void ZopfliVerifyLenDist(const unsigned char* data, size_t datasize, size_t pos,
274 unsigned short dist, unsigned short length) {
275
276 /* TODO(lode): make this only run in a debug compile, it's for assert only. */
277 size_t i;
278
279 assert(pos + length <= datasize);
280 for (i = 0; i < length; i++) {
281 if (data[pos - dist + i] != data[pos + i]) {
282 assert(data[pos - dist + i] == data[pos + i]);
283 break;
284 }
285 }
286 }
287
288 /*
289 Finds how long the match of scan and match is. Can be used to find how many
290 bytes starting from scan, and from match, are equal. Returns the last byte
291 after scan, which is still equal to the correspondinb byte after match.
292 scan is the position to compare
293 match is the earlier position to compare.
294 end is the last possible byte, beyond which to stop looking.
295 safe_end is a few (8) bytes before end, for comparing multiple bytes at once.
296 */
GetMatch(const unsigned char * scan,const unsigned char * match,const unsigned char * end,const unsigned char * safe_end)297 static const unsigned char* GetMatch(const unsigned char* scan,
298 const unsigned char* match,
299 const unsigned char* end,
300 const unsigned char* safe_end) {
301
302 if (sizeof(size_t) == 8) {
303 /* 8 checks at once per array bounds check (size_t is 64-bit). */
304 while (scan < safe_end && *((size_t*)scan) == *((size_t*)match)) {
305 scan += 8;
306 match += 8;
307 }
308 } else if (sizeof(unsigned int) == 4) {
309 /* 4 checks at once per array bounds check (unsigned int is 32-bit). */
310 while (scan < safe_end
311 && *((unsigned int*)scan) == *((unsigned int*)match)) {
312 scan += 4;
313 match += 4;
314 }
315 } else {
316 /* do 8 checks at once per array bounds check. */
317 while (scan < safe_end && *scan == *match && *++scan == *++match
318 && *++scan == *++match && *++scan == *++match
319 && *++scan == *++match && *++scan == *++match
320 && *++scan == *++match && *++scan == *++match) {
321 scan++; match++;
322 }
323 }
324
325 /* The remaining few bytes. */
326 while (scan != end && *scan == *match) {
327 scan++; match++;
328 }
329
330 return scan;
331 }
332
333 #ifdef ZOPFLI_LONGEST_MATCH_CACHE
334 /*
335 Gets distance, length and sublen values from the cache if possible.
336 Returns 1 if it got the values from the cache, 0 if not.
337 Updates the limit value to a smaller one if possible with more limited
338 information from the cache.
339 */
TryGetFromLongestMatchCache(ZopfliBlockState * s,size_t pos,size_t * limit,unsigned short * sublen,unsigned short * distance,unsigned short * length)340 static int TryGetFromLongestMatchCache(ZopfliBlockState* s,
341 size_t pos, size_t* limit,
342 unsigned short* sublen, unsigned short* distance, unsigned short* length) {
343 /* The LMC cache starts at the beginning of the block rather than the
344 beginning of the whole array. */
345 size_t lmcpos = pos - s->blockstart;
346
347 /* Length > 0 and dist 0 is invalid combination, which indicates on purpose
348 that this cache value is not filled in yet. */
349 unsigned char cache_available = s->lmc && (s->lmc->length[lmcpos] == 0 ||
350 s->lmc->dist[lmcpos] != 0);
351 unsigned char limit_ok_for_cache = cache_available &&
352 (*limit == ZOPFLI_MAX_MATCH || s->lmc->length[lmcpos] <= *limit ||
353 (sublen && ZopfliMaxCachedSublen(s->lmc,
354 lmcpos, s->lmc->length[lmcpos]) >= *limit));
355
356 if (s->lmc && limit_ok_for_cache && cache_available) {
357 if (!sublen || s->lmc->length[lmcpos]
358 <= ZopfliMaxCachedSublen(s->lmc, lmcpos, s->lmc->length[lmcpos])) {
359 *length = s->lmc->length[lmcpos];
360 if (*length > *limit) *length = *limit;
361 if (sublen) {
362 ZopfliCacheToSublen(s->lmc, lmcpos, *length, sublen);
363 *distance = sublen[*length];
364 if (*limit == ZOPFLI_MAX_MATCH && *length >= ZOPFLI_MIN_MATCH) {
365 assert(sublen[*length] == s->lmc->dist[lmcpos]);
366 }
367 } else {
368 *distance = s->lmc->dist[lmcpos];
369 }
370 return 1;
371 }
372 /* Can't use much of the cache, since the "sublens" need to be calculated,
373 but at least we already know when to stop. */
374 *limit = s->lmc->length[lmcpos];
375 }
376
377 return 0;
378 }
379
380 /*
381 Stores the found sublen, distance and length in the longest match cache, if
382 possible.
383 */
StoreInLongestMatchCache(ZopfliBlockState * s,size_t pos,size_t limit,const unsigned short * sublen,unsigned short distance,unsigned short length)384 static void StoreInLongestMatchCache(ZopfliBlockState* s,
385 size_t pos, size_t limit,
386 const unsigned short* sublen,
387 unsigned short distance, unsigned short length) {
388 /* The LMC cache starts at the beginning of the block rather than the
389 beginning of the whole array. */
390 size_t lmcpos = pos - s->blockstart;
391
392 /* Length > 0 and dist 0 is invalid combination, which indicates on purpose
393 that this cache value is not filled in yet. */
394 unsigned char cache_available = s->lmc && (s->lmc->length[lmcpos] == 0 ||
395 s->lmc->dist[lmcpos] != 0);
396
397 if (s->lmc && limit == ZOPFLI_MAX_MATCH && sublen && !cache_available) {
398 assert(s->lmc->length[lmcpos] == 1 && s->lmc->dist[lmcpos] == 0);
399 s->lmc->dist[lmcpos] = length < ZOPFLI_MIN_MATCH ? 0 : distance;
400 s->lmc->length[lmcpos] = length < ZOPFLI_MIN_MATCH ? 0 : length;
401 assert(!(s->lmc->length[lmcpos] == 1 && s->lmc->dist[lmcpos] == 0));
402 ZopfliSublenToCache(sublen, lmcpos, length, s->lmc);
403 }
404 }
405 #endif
406
ZopfliFindLongestMatch(ZopfliBlockState * s,const ZopfliHash * h,const unsigned char * array,size_t pos,size_t size,size_t limit,unsigned short * sublen,unsigned short * distance,unsigned short * length)407 void ZopfliFindLongestMatch(ZopfliBlockState* s, const ZopfliHash* h,
408 const unsigned char* array,
409 size_t pos, size_t size, size_t limit,
410 unsigned short* sublen, unsigned short* distance, unsigned short* length) {
411 unsigned short hpos = pos & ZOPFLI_WINDOW_MASK, p, pp;
412 unsigned short bestdist = 0;
413 unsigned short bestlength = 1;
414 const unsigned char* scan;
415 const unsigned char* match;
416 const unsigned char* arrayend;
417 const unsigned char* arrayend_safe;
418 #if ZOPFLI_MAX_CHAIN_HITS < ZOPFLI_WINDOW_SIZE
419 int chain_counter = ZOPFLI_MAX_CHAIN_HITS; /* For quitting early. */
420 #endif
421
422 unsigned dist = 0; /* Not unsigned short on purpose. */
423
424 int* hhead = h->head;
425 unsigned short* hprev = h->prev;
426 int* hhashval = h->hashval;
427 int hval = h->val;
428
429 #ifdef ZOPFLI_LONGEST_MATCH_CACHE
430 if (TryGetFromLongestMatchCache(s, pos, &limit, sublen, distance, length)) {
431 assert(pos + *length <= size);
432 return;
433 }
434 #endif
435
436 assert(limit <= ZOPFLI_MAX_MATCH);
437 assert(limit >= ZOPFLI_MIN_MATCH);
438 assert(pos < size);
439
440 if (size - pos < ZOPFLI_MIN_MATCH) {
441 /* The rest of the code assumes there are at least ZOPFLI_MIN_MATCH bytes to
442 try. */
443 *length = 0;
444 *distance = 0;
445 return;
446 }
447
448 if (pos + limit > size) {
449 limit = size - pos;
450 }
451 arrayend = &array[pos] + limit;
452 arrayend_safe = arrayend - 8;
453
454 assert(hval < 65536);
455
456 pp = hhead[hval]; /* During the whole loop, p == hprev[pp]. */
457 p = hprev[pp];
458
459 assert(pp == hpos);
460
461 dist = p < pp ? pp - p : ((ZOPFLI_WINDOW_SIZE - p) + pp);
462
463 /* Go through all distances. */
464 while (dist < ZOPFLI_WINDOW_SIZE) {
465 unsigned short currentlength = 0;
466
467 assert(p < ZOPFLI_WINDOW_SIZE);
468 assert(p == hprev[pp]);
469 assert(hhashval[p] == hval);
470
471 if (dist > 0) {
472 assert(pos < size);
473 assert(dist <= pos);
474 scan = &array[pos];
475 match = &array[pos - dist];
476
477 /* Testing the byte at position bestlength first, goes slightly faster. */
478 if (pos + bestlength >= size
479 || *(scan + bestlength) == *(match + bestlength)) {
480
481 #ifdef ZOPFLI_HASH_SAME
482 unsigned short same0 = h->same[pos & ZOPFLI_WINDOW_MASK];
483 if (same0 > 2 && *scan == *match) {
484 unsigned short same1 = h->same[(pos - dist) & ZOPFLI_WINDOW_MASK];
485 unsigned short same = same0 < same1 ? same0 : same1;
486 if (same > limit) same = limit;
487 scan += same;
488 match += same;
489 }
490 #endif
491 scan = GetMatch(scan, match, arrayend, arrayend_safe);
492 currentlength = scan - &array[pos]; /* The found length. */
493 }
494
495 if (currentlength > bestlength) {
496 if (sublen) {
497 unsigned short j;
498 for (j = bestlength + 1; j <= currentlength; j++) {
499 sublen[j] = dist;
500 }
501 }
502 bestdist = dist;
503 bestlength = currentlength;
504 if (currentlength >= limit) break;
505 }
506 }
507
508
509 #ifdef ZOPFLI_HASH_SAME_HASH
510 /* Switch to the other hash once this will be more efficient. */
511 if (hhead != h->head2 && bestlength >= h->same[hpos] &&
512 h->val2 == h->hashval2[p]) {
513 /* Now use the hash that encodes the length and first byte. */
514 hhead = h->head2;
515 hprev = h->prev2;
516 hhashval = h->hashval2;
517 hval = h->val2;
518 }
519 #endif
520
521 pp = p;
522 p = hprev[p];
523 if (p == pp) break; /* Uninited prev value. */
524
525 dist += p < pp ? pp - p : ((ZOPFLI_WINDOW_SIZE - p) + pp);
526
527 #if ZOPFLI_MAX_CHAIN_HITS < ZOPFLI_WINDOW_SIZE
528 chain_counter--;
529 if (chain_counter <= 0) break;
530 #endif
531 }
532
533 #ifdef ZOPFLI_LONGEST_MATCH_CACHE
534 StoreInLongestMatchCache(s, pos, limit, sublen, bestdist, bestlength);
535 #endif
536
537 assert(bestlength <= limit);
538
539 *distance = bestdist;
540 *length = bestlength;
541 assert(pos + *length <= size);
542 }
543
ZopfliLZ77Greedy(ZopfliBlockState * s,const unsigned char * in,size_t instart,size_t inend,ZopfliLZ77Store * store,ZopfliHash * h)544 void ZopfliLZ77Greedy(ZopfliBlockState* s, const unsigned char* in,
545 size_t instart, size_t inend,
546 ZopfliLZ77Store* store, ZopfliHash* h) {
547 size_t i = 0, j;
548 unsigned short leng;
549 unsigned short dist;
550 int lengthscore;
551 size_t windowstart = instart > ZOPFLI_WINDOW_SIZE
552 ? instart - ZOPFLI_WINDOW_SIZE : 0;
553 unsigned short dummysublen[259];
554
555 #ifdef ZOPFLI_LAZY_MATCHING
556 /* Lazy matching. */
557 unsigned prev_length = 0;
558 unsigned prev_match = 0;
559 int prevlengthscore;
560 int match_available = 0;
561 #endif
562
563 if (instart == inend) return;
564
565 ZopfliResetHash(ZOPFLI_WINDOW_SIZE, h);
566 ZopfliWarmupHash(in, windowstart, inend, h);
567 for (i = windowstart; i < instart; i++) {
568 ZopfliUpdateHash(in, i, inend, h);
569 }
570
571 for (i = instart; i < inend; i++) {
572 ZopfliUpdateHash(in, i, inend, h);
573
574 ZopfliFindLongestMatch(s, h, in, i, inend, ZOPFLI_MAX_MATCH, dummysublen,
575 &dist, &leng);
576 lengthscore = GetLengthScore(leng, dist);
577
578 #ifdef ZOPFLI_LAZY_MATCHING
579 /* Lazy matching. */
580 prevlengthscore = GetLengthScore(prev_length, prev_match);
581 if (match_available) {
582 match_available = 0;
583 if (lengthscore > prevlengthscore + 1) {
584 ZopfliStoreLitLenDist(in[i - 1], 0, i - 1, store);
585 if (lengthscore >= ZOPFLI_MIN_MATCH && leng < ZOPFLI_MAX_MATCH) {
586 match_available = 1;
587 prev_length = leng;
588 prev_match = dist;
589 continue;
590 }
591 } else {
592 /* Add previous to output. */
593 leng = prev_length;
594 dist = prev_match;
595 lengthscore = prevlengthscore;
596 /* Add to output. */
597 ZopfliVerifyLenDist(in, inend, i - 1, dist, leng);
598 ZopfliStoreLitLenDist(leng, dist, i - 1, store);
599 for (j = 2; j < leng; j++) {
600 assert(i < inend);
601 i++;
602 ZopfliUpdateHash(in, i, inend, h);
603 }
604 continue;
605 }
606 }
607 else if (lengthscore >= ZOPFLI_MIN_MATCH && leng < ZOPFLI_MAX_MATCH) {
608 match_available = 1;
609 prev_length = leng;
610 prev_match = dist;
611 continue;
612 }
613 /* End of lazy matching. */
614 #endif
615
616 /* Add to output. */
617 if (lengthscore >= ZOPFLI_MIN_MATCH) {
618 ZopfliVerifyLenDist(in, inend, i, dist, leng);
619 ZopfliStoreLitLenDist(leng, dist, i, store);
620 } else {
621 leng = 1;
622 ZopfliStoreLitLenDist(in[i], 0, i, store);
623 }
624 for (j = 1; j < leng; j++) {
625 assert(i < inend);
626 i++;
627 ZopfliUpdateHash(in, i, inend, h);
628 }
629 }
630 }
631