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/*
21Functions for basic LZ77 compression and utilities for the "squeeze" LZ77
22compression.
23*/
24
25#ifndef ZOPFLI_LZ77_H_
26#define ZOPFLI_LZ77_H_
27
28#include <stdlib.h>
29
30#include "cache.h"
31#include "hash.h"
32#include "zopfli.h"
33
34/*
35Stores lit/length and dist pairs for LZ77.
36Parameter litlens: Contains the literal symbols or length values.
37Parameter dists: Contains the distances. A value is 0 to indicate that there is
38no dist and the corresponding litlens value is a literal instead of a length.
39Parameter size: The size of both the litlens and dists arrays.
40The memory can best be managed by using ZopfliInitLZ77Store to initialize it,
41ZopfliCleanLZ77Store to destroy it, and ZopfliStoreLitLenDist to append values.
42
43*/
44typedef struct ZopfliLZ77Store {
45  unsigned short* litlens;  /* Lit or len. */
46  unsigned short* dists;  /* If 0: indicates literal in corresponding litlens,
47      if > 0: length in corresponding litlens, this is the distance. */
48  size_t size;
49} ZopfliLZ77Store;
50
51void ZopfliInitLZ77Store(ZopfliLZ77Store* store);
52void ZopfliCleanLZ77Store(ZopfliLZ77Store* store);
53void ZopfliCopyLZ77Store(const ZopfliLZ77Store* source, ZopfliLZ77Store* dest);
54void ZopfliStoreLitLenDist(unsigned short length, unsigned short dist,
55                           ZopfliLZ77Store* store);
56
57/*
58Some state information for compressing a block.
59This is currently a bit under-used (with mainly only the longest match cache),
60but is kept for easy future expansion.
61*/
62typedef struct ZopfliBlockState {
63  const ZopfliOptions* options;
64
65#ifdef ZOPFLI_LONGEST_MATCH_CACHE
66  /* Cache for length/distance pairs found so far. */
67  ZopfliLongestMatchCache* lmc;
68#endif
69
70  /* The start (inclusive) and end (not inclusive) of the current block. */
71  size_t blockstart;
72  size_t blockend;
73} ZopfliBlockState;
74
75/*
76Finds the longest match (length and corresponding distance) for LZ77
77compression.
78Even when not using "sublen", it can be more efficient to provide an array,
79because only then the caching is used.
80array: the data
81pos: position in the data to find the match for
82size: size of the data
83limit: limit length to maximum this value (default should be 258). This allows
84    finding a shorter dist for that length (= less extra bits). Must be
85    in the range [ZOPFLI_MIN_MATCH, ZOPFLI_MAX_MATCH].
86sublen: output array of 259 elements, or null. Has, for each length, the
87    smallest distance required to reach this length. Only 256 of its 259 values
88    are used, the first 3 are ignored (the shortest length is 3. It is purely
89    for convenience that the array is made 3 longer).
90*/
91void ZopfliFindLongestMatch(
92    ZopfliBlockState *s, const ZopfliHash* h, const unsigned char* array,
93    size_t pos, size_t size, size_t limit,
94    unsigned short* sublen, unsigned short* distance, unsigned short* length);
95
96/*
97Verifies if length and dist are indeed valid, only used for assertion.
98*/
99void ZopfliVerifyLenDist(const unsigned char* data, size_t datasize, size_t pos,
100                         unsigned short dist, unsigned short length);
101
102/*
103Counts the number of literal, length and distance symbols in the given lz77
104arrays.
105litlens: lz77 lit/lengths
106dists: ll77 distances
107start: where to begin counting in litlens and dists
108end: where to stop counting in litlens and dists (not inclusive)
109ll_count: count of each lit/len symbol, must have size 288 (see deflate
110    standard)
111d_count: count of each dist symbol, must have size 32 (see deflate standard)
112*/
113void ZopfliLZ77Counts(const unsigned short* litlens,
114                      const unsigned short* dists,
115                      size_t start, size_t end,
116                      size_t* ll_count, size_t* d_count);
117
118/*
119Does LZ77 using an algorithm similar to gzip, with lazy matching, rather than
120with the slow but better "squeeze" implementation.
121The result is placed in the ZopfliLZ77Store.
122If instart is larger than 0, it uses values before instart as starting
123dictionary.
124*/
125void ZopfliLZ77Greedy(ZopfliBlockState* s, const unsigned char* in,
126                      size_t instart, size_t inend,
127                      ZopfliLZ77Store* store);
128
129#endif  /* ZOPFLI_LZ77_H_ */
130