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