1 files changed, 129 insertions, 0 deletions
diff --git a/zopfli/lz77.h b/zopfli/lz77.h
new file mode 100644
index 0000000..55186a7
--- /dev/null
+++ b/zopfli/lz77.h
@@ -0,0 +1,129 @@
+/*
+Copyright 2011 Google Inc. All Rights Reserved.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+
+Author: lode.vandevenne@gmail.com (Lode Vandevenne)
+Author: jyrki.alakuijala@gmail.com (Jyrki Alakuijala)
+*/
+
+/*
+Functions for basic LZ77 compression and utilities for the "squeeze" LZ77
+compression.
+*/
+
+#ifndef ZOPFLI_LZ77_H_
+#define ZOPFLI_LZ77_H_
+
+#include <stdlib.h>
+
+#include "cache.h"
+#include "hash.h"
+#include "zopfli.h"
+
+/*
+Stores lit/length and dist pairs for LZ77.
+Parameter litlens: Contains the literal symbols or length values.
+Parameter dists: Contains the distances. A value is 0 to indicate that there is
+no dist and the corresponding litlens value is a literal instead of a length.
+Parameter size: The size of both the litlens and dists arrays.
+The memory can best be managed by using ZopfliInitLZ77Store to initialize it,
+ZopfliCleanLZ77Store to destroy it, and ZopfliStoreLitLenDist to append values.
+
+*/
+typedef struct ZopfliLZ77Store {
+  unsigned short* litlens;  /* Lit or len. */
+  unsigned short* dists;  /* If 0: indicates literal in corresponding litlens,
+      if > 0: length in corresponding litlens, this is the distance. */
+  size_t size;
+} ZopfliLZ77Store;
+
+void ZopfliInitLZ77Store(ZopfliLZ77Store* store);
+void ZopfliCleanLZ77Store(ZopfliLZ77Store* store);
+void ZopfliCopyLZ77Store(const ZopfliLZ77Store* source, ZopfliLZ77Store* dest);
+void ZopfliStoreLitLenDist(unsigned short length, unsigned short dist,
+                           ZopfliLZ77Store* store);
+
+/*
+Some state information for compressing a block.
+This is currently a bit under-used (with mainly only the longest match cache),
+but is kept for easy future expansion.
+*/
+typedef struct ZopfliBlockState {
+  const ZopfliOptions* options;
+
+#ifdef ZOPFLI_LONGEST_MATCH_CACHE
+  /* Cache for length/distance pairs found so far. */
+  ZopfliLongestMatchCache* lmc;
+#endif
+
+  /* The start (inclusive) and end (not inclusive) of the current block. */
+  size_t blockstart;
+  size_t blockend;
+} ZopfliBlockState;
+
+/*
+Finds the longest match (length and corresponding distance) for LZ77
+compression.
+Even when not using "sublen", it can be more efficient to provide an array,
+because only then the caching is used.
+array: the data
+pos: position in the data to find the match for
+size: size of the data
+limit: limit length to maximum this value (default should be 258). This allows
+    finding a shorter dist for that length (= less extra bits). Must be
+    in the range [ZOPFLI_MIN_MATCH, ZOPFLI_MAX_MATCH].
+sublen: output array of 259 elements, or null. Has, for each length, the
+    smallest distance required to reach this length. Only 256 of its 259 values
+    are used, the first 3 are ignored (the shortest length is 3. It is purely
+    for convenience that the array is made 3 longer).
+*/
+void 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);
+
+/*
+Verifies if length and dist are indeed valid, only used for assertion.
+*/
+void ZopfliVerifyLenDist(const unsigned char* data, size_t datasize, size_t pos,
+                         unsigned short dist, unsigned short length);
+
+/*
+Counts the number of literal, length and distance symbols in the given lz77
+arrays.
+litlens: lz77 lit/lengths
+dists: ll77 distances
+start: where to begin counting in litlens and dists
+end: where to stop counting in litlens and dists (not inclusive)
+ll_count: count of each lit/len symbol, must have size 288 (see deflate
+    standard)
+d_count: count of each dist symbol, must have size 32 (see deflate standard)
+*/
+void ZopfliLZ77Counts(const unsigned short* litlens,
+                      const unsigned short* dists,
+                      size_t start, size_t end,
+                      size_t* ll_count, size_t* d_count);
+
+/*
+Does LZ77 using an algorithm similar to gzip, with lazy matching, rather than
+with the slow but better "squeeze" implementation.
+The result is placed in the ZopfliLZ77Store.
+If instart is larger than 0, it uses values before instart as starting
+dictionary.
+*/
+void ZopfliLZ77Greedy(ZopfliBlockState* s, const unsigned char* in,
+                      size_t instart, size_t inend,
+                      ZopfliLZ77Store* store);
+
+#endif  /* ZOPFLI_LZ77_H_ */