/*
|
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_ */
|
