diff options
Diffstat (limited to 'lz77.h')
| -rw-r--r-- | lz77.h | 129 |
1 files changed, 0 insertions, 129 deletions
@@ -1,129 +0,0 @@ -/* -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_ */ |