1 1.1 tls /* 2 1.1 tls Copyright 2011 Google Inc. All Rights Reserved. 3 1.1 tls 4 1.1 tls Licensed under the Apache License, Version 2.0 (the "License"); 5 1.1 tls you may not use this file except in compliance with the License. 6 1.1 tls You may obtain a copy of the License at 7 1.1 tls 8 1.1 tls http://www.apache.org/licenses/LICENSE-2.0 9 1.1 tls 10 1.1 tls Unless required by applicable law or agreed to in writing, software 11 1.1 tls distributed under the License is distributed on an "AS IS" BASIS, 12 1.1 tls WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 1.1 tls See the License for the specific language governing permissions and 14 1.1 tls limitations under the License. 15 1.1 tls 16 1.1 tls Author: lode.vandevenne (at) gmail.com (Lode Vandevenne) 17 1.1 tls Author: jyrki.alakuijala (at) gmail.com (Jyrki Alakuijala) 18 1.1 tls */ 19 1.1 tls 20 1.1 tls /* 21 1.1 tls Functions for basic LZ77 compression and utilities for the "squeeze" LZ77 22 1.1 tls compression. 23 1.1 tls */ 24 1.1 tls 25 1.1 tls #ifndef ZOPFLI_LZ77_H_ 26 1.1 tls #define ZOPFLI_LZ77_H_ 27 1.1 tls 28 1.1 tls #include <stdlib.h> 29 1.1 tls 30 1.1 tls #include "cache.h" 31 1.1 tls #include "hash.h" 32 1.1 tls #include "zopfli.h" 33 1.1 tls 34 1.1 tls /* 35 1.1 tls Stores lit/length and dist pairs for LZ77. 36 1.1 tls litlens: Contains the literal symbols or length values. 37 1.1 tls dists: Indicates the distance, or 0 to indicate that there is no distance and 38 1.1 tls litlens contains a literal instead of a length. 39 1.1 tls litlens and dists both have the same size. 40 1.1 tls */ 41 1.1 tls typedef struct ZopfliLZ77Store { 42 1.1 tls unsigned short* litlens; /* Lit or len. */ 43 1.1 tls unsigned short* dists; /* If 0: indicates literal in corresponding litlens, 44 1.1 tls if > 0: length in corresponding litlens, this is the distance. */ 45 1.1 tls size_t size; 46 1.1 tls } ZopfliLZ77Store; 47 1.1 tls 48 1.1 tls void ZopfliInitLZ77Store(ZopfliLZ77Store* store); 49 1.1 tls void ZopfliCleanLZ77Store(ZopfliLZ77Store* store); 50 1.1 tls void ZopfliCopyLZ77Store(const ZopfliLZ77Store* source, ZopfliLZ77Store* dest); 51 1.1 tls void ZopfliStoreLitLenDist(unsigned short length, unsigned short dist, 52 1.1 tls ZopfliLZ77Store* store); 53 1.1 tls 54 1.1 tls /* 55 1.1 tls Some state information for compressing a block. 56 1.1 tls This is currently a bit under-used (with mainly only the longest match cache), 57 1.1 tls but is kept for easy future expansion. 58 1.1 tls */ 59 1.1 tls typedef struct ZopfliBlockState { 60 1.1 tls const ZopfliOptions* options; 61 1.1 tls 62 1.1 tls #ifdef ZOPFLI_LONGEST_MATCH_CACHE 63 1.1 tls /* Cache for length/distance pairs found so far. */ 64 1.1 tls ZopfliLongestMatchCache* lmc; 65 1.1 tls #endif 66 1.1 tls 67 1.1 tls /* The start (inclusive) and end (not inclusive) of the current block. */ 68 1.1 tls size_t blockstart; 69 1.1 tls size_t blockend; 70 1.1 tls } ZopfliBlockState; 71 1.1 tls 72 1.1 tls /* 73 1.1 tls Finds the longest match (length and corresponding distance) for LZ77 74 1.1 tls compression. 75 1.1 tls Even when not using "sublen", it can be more efficient to provide an array, 76 1.1 tls because only then the caching is used. 77 1.1 tls array: the data 78 1.1 tls pos: position in the data to find the match for 79 1.1 tls size: size of the data 80 1.1 tls limit: limit length to maximum this value (default should be 258). This allows 81 1.1 tls finding a shorter dist for that length (= less extra bits). Must be 82 1.1 tls in the range [ZOPFLI_MIN_MATCH, ZOPFLI_MAX_MATCH]. 83 1.1 tls sublen: output array of 259 elements, or null. Has, for each length, the 84 1.1 tls smallest distance required to reach this length. Only 256 of its 259 values 85 1.1 tls are used, the first 3 are ignored (the shortest length is 3. It is purely 86 1.1 tls for convenience that the array is made 3 longer). 87 1.1 tls */ 88 1.1 tls void ZopfliFindLongestMatch( 89 1.1 tls ZopfliBlockState *s, const ZopfliHash* h, const unsigned char* array, 90 1.1 tls size_t pos, size_t size, size_t limit, 91 1.1 tls unsigned short* sublen, unsigned short* distance, unsigned short* length); 92 1.1 tls 93 1.1 tls /* 94 1.1 tls Verifies if length and dist are indeed valid, only used for assertion. 95 1.1 tls */ 96 1.1 tls void ZopfliVerifyLenDist(const unsigned char* data, size_t datasize, size_t pos, 97 1.1 tls unsigned short dist, unsigned short length); 98 1.1 tls 99 1.1 tls /* 100 1.1 tls Counts the number of literal, length and distance symbols in the given lz77 101 1.1 tls arrays. 102 1.1 tls litlens: lz77 lit/lengths 103 1.1 tls dists: ll77 distances 104 1.1 tls start: where to begin counting in litlens and dists 105 1.1 tls end: where to stop counting in litlens and dists (not inclusive) 106 1.1 tls ll_count: count of each lit/len symbol, must have size 288 (see deflate 107 1.1 tls standard) 108 1.1 tls d_count: count of each dist symbol, must have size 32 (see deflate standard) 109 1.1 tls */ 110 1.1 tls void ZopfliLZ77Counts(const unsigned short* litlens, 111 1.1 tls const unsigned short* dists, 112 1.1 tls size_t start, size_t end, 113 1.1 tls size_t* ll_count, size_t* d_count); 114 1.1 tls 115 1.1 tls /* 116 1.1 tls Does LZ77 using an algorithm similar to gzip, with lazy matching, rather than 117 1.1 tls with the slow but better "squeeze" implementation. 118 1.1 tls The result is placed in the ZopfliLZ77Store. 119 1.1 tls If instart is larger than 0, it uses values before instart as starting 120 1.1 tls dictionary. 121 1.1 tls */ 122 1.1 tls void ZopfliLZ77Greedy(ZopfliBlockState* s, const unsigned char* in, 123 1.1 tls size_t instart, size_t inend, 124 1.1 tls ZopfliLZ77Store* store); 125 1.1 tls 126 1.1 tls #endif /* ZOPFLI_LZ77_H_ */ 127
Indexes created Sat Mar 21 00:23:06 UTC 2026