"Fossies" - the Fresh Open Source Software Archive 
Member "pigz-2.8/zopfli/src/zopfli/lz77.c" (29 Mar 2019, 20631 Bytes) of package /linux/privat/pigz-2.8.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "lz77.c" see the
Fossies "Dox" file reference documentation and the last
Fossies "Diffs" side-by-side code changes report:
2.4_vs_2.5.
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
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
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
50 static size_t CeilDiv(size_t a, size_t b) {
51 return (a + b - 1) / b;
52 }
53
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 */
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
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
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
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
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
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
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 */
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
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 */
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 const*)scan) ==
305 *((size_t const*)match)) {
306 scan += 8;
307 match += 8;
308 }
309 } else if (sizeof(unsigned int) == 4) {
310 /* 4 checks at once per array bounds check (unsigned int is 32-bit). */
311 while (scan < safe_end
312 && *((unsigned int const*)scan) == *((unsigned int const*)match)) {
313 scan += 4;
314 match += 4;
315 }
316 } else {
317 /* do 8 checks at once per array bounds check. */
318 while (scan < safe_end && *scan == *match && *++scan == *++match
319 && *++scan == *++match && *++scan == *++match
320 && *++scan == *++match && *++scan == *++match
321 && *++scan == *++match && *++scan == *++match) {
322 scan++; match++;
323 }
324 }
325
326 /* The remaining few bytes. */
327 while (scan != end && *scan == *match) {
328 scan++; match++;
329 }
330
331 return scan;
332 }
333
334 #ifdef ZOPFLI_LONGEST_MATCH_CACHE
335 /*
336 Gets distance, length and sublen values from the cache if possible.
337 Returns 1 if it got the values from the cache, 0 if not.
338 Updates the limit value to a smaller one if possible with more limited
339 information from the cache.
340 */
341 static int TryGetFromLongestMatchCache(ZopfliBlockState* s,
342 size_t pos, size_t* limit,
343 unsigned short* sublen, unsigned short* distance, unsigned short* length) {
344 /* The LMC cache starts at the beginning of the block rather than the
345 beginning of the whole array. */
346 size_t lmcpos = pos - s->blockstart;
347
348 /* Length > 0 and dist 0 is invalid combination, which indicates on purpose
349 that this cache value is not filled in yet. */
350 unsigned char cache_available = s->lmc && (s->lmc->length[lmcpos] == 0 ||
351 s->lmc->dist[lmcpos] != 0);
352 unsigned char limit_ok_for_cache = cache_available &&
353 (*limit == ZOPFLI_MAX_MATCH || s->lmc->length[lmcpos] <= *limit ||
354 (sublen && ZopfliMaxCachedSublen(s->lmc,
355 lmcpos, s->lmc->length[lmcpos]) >= *limit));
356
357 if (s->lmc && limit_ok_for_cache && cache_available) {
358 if (!sublen || s->lmc->length[lmcpos]
359 <= ZopfliMaxCachedSublen(s->lmc, lmcpos, s->lmc->length[lmcpos])) {
360 *length = s->lmc->length[lmcpos];
361 if (*length > *limit) *length = *limit;
362 if (sublen) {
363 ZopfliCacheToSublen(s->lmc, lmcpos, *length, sublen);
364 *distance = sublen[*length];
365 if (*limit == ZOPFLI_MAX_MATCH && *length >= ZOPFLI_MIN_MATCH) {
366 assert(sublen[*length] == s->lmc->dist[lmcpos]);
367 }
368 } else {
369 *distance = s->lmc->dist[lmcpos];
370 }
371 return 1;
372 }
373 /* Can't use much of the cache, since the "sublens" need to be calculated,
374 but at least we already know when to stop. */
375 *limit = s->lmc->length[lmcpos];
376 }
377
378 return 0;
379 }
380
381 /*
382 Stores the found sublen, distance and length in the longest match cache, if
383 possible.
384 */
385 static void StoreInLongestMatchCache(ZopfliBlockState* s,
386 size_t pos, size_t limit,
387 const unsigned short* sublen,
388 unsigned short distance, unsigned short length) {
389 /* The LMC cache starts at the beginning of the block rather than the
390 beginning of the whole array. */
391 size_t lmcpos = pos - s->blockstart;
392
393 /* Length > 0 and dist 0 is invalid combination, which indicates on purpose
394 that this cache value is not filled in yet. */
395 unsigned char cache_available = s->lmc && (s->lmc->length[lmcpos] == 0 ||
396 s->lmc->dist[lmcpos] != 0);
397
398 if (s->lmc && limit == ZOPFLI_MAX_MATCH && sublen && !cache_available) {
399 assert(s->lmc->length[lmcpos] == 1 && s->lmc->dist[lmcpos] == 0);
400 s->lmc->dist[lmcpos] = length < ZOPFLI_MIN_MATCH ? 0 : distance;
401 s->lmc->length[lmcpos] = length < ZOPFLI_MIN_MATCH ? 0 : length;
402 assert(!(s->lmc->length[lmcpos] == 1 && s->lmc->dist[lmcpos] == 0));
403 ZopfliSublenToCache(sublen, lmcpos, length, s->lmc);
404 }
405 }
406 #endif
407
408 void ZopfliFindLongestMatch(ZopfliBlockState* s, const ZopfliHash* h,
409 const unsigned char* array,
410 size_t pos, size_t size, size_t limit,
411 unsigned short* sublen, unsigned short* distance, unsigned short* length) {
412 unsigned short hpos = pos & ZOPFLI_WINDOW_MASK, p, pp;
413 unsigned short bestdist = 0;
414 unsigned short bestlength = 1;
415 const unsigned char* scan;
416 const unsigned char* match;
417 const unsigned char* arrayend;
418 const unsigned char* arrayend_safe;
419 #if ZOPFLI_MAX_CHAIN_HITS < ZOPFLI_WINDOW_SIZE
420 int chain_counter = ZOPFLI_MAX_CHAIN_HITS; /* For quitting early. */
421 #endif
422
423 unsigned dist = 0; /* Not unsigned short on purpose. */
424
425 int* hhead = h->head;
426 unsigned short* hprev = h->prev;
427 int* hhashval = h->hashval;
428 int hval = h->val;
429
430 #ifdef ZOPFLI_LONGEST_MATCH_CACHE
431 if (TryGetFromLongestMatchCache(s, pos, &limit, sublen, distance, length)) {
432 assert(pos + *length <= size);
433 return;
434 }
435 #endif
436
437 assert(limit <= ZOPFLI_MAX_MATCH);
438 assert(limit >= ZOPFLI_MIN_MATCH);
439 assert(pos < size);
440
441 if (size - pos < ZOPFLI_MIN_MATCH) {
442 /* The rest of the code assumes there are at least ZOPFLI_MIN_MATCH bytes to
443 try. */
444 *length = 0;
445 *distance = 0;
446 return;
447 }
448
449 if (pos + limit > size) {
450 limit = size - pos;
451 }
452 arrayend = &array[pos] + limit;
453 arrayend_safe = arrayend - 8;
454
455 assert(hval < 65536);
456
457 pp = hhead[hval]; /* During the whole loop, p == hprev[pp]. */
458 p = hprev[pp];
459
460 assert(pp == hpos);
461
462 dist = p < pp ? pp - p : ((ZOPFLI_WINDOW_SIZE - p) + pp);
463
464 /* Go through all distances. */
465 while (dist < ZOPFLI_WINDOW_SIZE) {
466 unsigned short currentlength = 0;
467
468 assert(p < ZOPFLI_WINDOW_SIZE);
469 assert(p == hprev[pp]);
470 assert(hhashval[p] == hval);
471
472 if (dist > 0) {
473 assert(pos < size);
474 assert(dist <= pos);
475 scan = &array[pos];
476 match = &array[pos - dist];
477
478 /* Testing the byte at position bestlength first, goes slightly faster. */
479 if (pos + bestlength >= size
480 || *(scan + bestlength) == *(match + bestlength)) {
481
482 #ifdef ZOPFLI_HASH_SAME
483 unsigned short same0 = h->same[pos & ZOPFLI_WINDOW_MASK];
484 if (same0 > 2 && *scan == *match) {
485 unsigned short same1 = h->same[(pos - dist) & ZOPFLI_WINDOW_MASK];
486 unsigned short same = same0 < same1 ? same0 : same1;
487 if (same > limit) same = limit;
488 scan += same;
489 match += same;
490 }
491 #endif
492 scan = GetMatch(scan, match, arrayend, arrayend_safe);
493 currentlength = scan - &array[pos]; /* The found length. */
494 }
495
496 if (currentlength > bestlength) {
497 if (sublen) {
498 unsigned short j;
499 for (j = bestlength + 1; j <= currentlength; j++) {
500 sublen[j] = dist;
501 }
502 }
503 bestdist = dist;
504 bestlength = currentlength;
505 if (currentlength >= limit) break;
506 }
507 }
508
509
510 #ifdef ZOPFLI_HASH_SAME_HASH
511 /* Switch to the other hash once this will be more efficient. */
512 if (hhead != h->head2 && bestlength >= h->same[hpos] &&
513 h->val2 == h->hashval2[p]) {
514 /* Now use the hash that encodes the length and first byte. */
515 hhead = h->head2;
516 hprev = h->prev2;
517 hhashval = h->hashval2;
518 hval = h->val2;
519 }
520 #endif
521
522 pp = p;
523 p = hprev[p];
524 if (p == pp) break; /* Uninited prev value. */
525
526 dist += p < pp ? pp - p : ((ZOPFLI_WINDOW_SIZE - p) + pp);
527
528 #if ZOPFLI_MAX_CHAIN_HITS < ZOPFLI_WINDOW_SIZE
529 chain_counter--;
530 if (chain_counter <= 0) break;
531 #endif
532 }
533
534 #ifdef ZOPFLI_LONGEST_MATCH_CACHE
535 StoreInLongestMatchCache(s, pos, limit, sublen, bestdist, bestlength);
536 #endif
537
538 assert(bestlength <= limit);
539
540 *distance = bestdist;
541 *length = bestlength;
542 assert(pos + *length <= size);
543 }
544
545 void ZopfliLZ77Greedy(ZopfliBlockState* s, const unsigned char* in,
546 size_t instart, size_t inend,
547 ZopfliLZ77Store* store, ZopfliHash* h) {
548 size_t i = 0, j;
549 unsigned short leng;
550 unsigned short dist;
551 int lengthscore;
552 size_t windowstart = instart > ZOPFLI_WINDOW_SIZE
553 ? instart - ZOPFLI_WINDOW_SIZE : 0;
554 unsigned short dummysublen[259];
555
556 #ifdef ZOPFLI_LAZY_MATCHING
557 /* Lazy matching. */
558 unsigned prev_length = 0;
559 unsigned prev_match = 0;
560 int prevlengthscore;
561 int match_available = 0;
562 #endif
563
564 if (instart == inend) return;
565
566 ZopfliResetHash(ZOPFLI_WINDOW_SIZE, h);
567 ZopfliWarmupHash(in, windowstart, inend, h);
568 for (i = windowstart; i < instart; i++) {
569 ZopfliUpdateHash(in, i, inend, h);
570 }
571
572 for (i = instart; i < inend; i++) {
573 ZopfliUpdateHash(in, i, inend, h);
574
575 ZopfliFindLongestMatch(s, h, in, i, inend, ZOPFLI_MAX_MATCH, dummysublen,
576 &dist, &leng);
577 lengthscore = GetLengthScore(leng, dist);
578
579 #ifdef ZOPFLI_LAZY_MATCHING
580 /* Lazy matching. */
581 prevlengthscore = GetLengthScore(prev_length, prev_match);
582 if (match_available) {
583 match_available = 0;
584 if (lengthscore > prevlengthscore + 1) {
585 ZopfliStoreLitLenDist(in[i - 1], 0, i - 1, store);
586 if (lengthscore >= ZOPFLI_MIN_MATCH && leng < ZOPFLI_MAX_MATCH) {
587 match_available = 1;
588 prev_length = leng;
589 prev_match = dist;
590 continue;
591 }
592 } else {
593 /* Add previous to output. */
594 leng = prev_length;
595 dist = prev_match;
596 lengthscore = prevlengthscore;
597 /* Add to output. */
598 ZopfliVerifyLenDist(in, inend, i - 1, dist, leng);
599 ZopfliStoreLitLenDist(leng, dist, i - 1, store);
600 for (j = 2; j < leng; j++) {
601 assert(i < inend);
602 i++;
603 ZopfliUpdateHash(in, i, inend, h);
604 }
605 continue;
606 }
607 }
608 else if (lengthscore >= ZOPFLI_MIN_MATCH && leng < ZOPFLI_MAX_MATCH) {
609 match_available = 1;
610 prev_length = leng;
611 prev_match = dist;
612 continue;
613 }
614 /* End of lazy matching. */
615 #endif
616
617 /* Add to output. */
618 if (lengthscore >= ZOPFLI_MIN_MATCH) {
619 ZopfliVerifyLenDist(in, inend, i, dist, leng);
620 ZopfliStoreLitLenDist(leng, dist, i, store);
621 } else {
622 leng = 1;
623 ZopfliStoreLitLenDist(in[i], 0, i, store);
624 }
625 for (j = 1; j < leng; j++) {
626 assert(i < inend);
627 i++;
628 ZopfliUpdateHash(in, i, inend, h);
629 }
630 }
631 }