Home | History | Annotate | Download | only in zopfli 
      1 /*
      2 Copyright 2011 Google Inc. All Rights Reserved.
      3 
      4 Licensed under the Apache License, Version 2.0 (the "License");
      5 you may not use this file except in compliance with the License.
      6 You may obtain a copy of the License at
      7 
      8     http://www.apache.org/licenses/LICENSE-2.0
      9 
     10 Unless required by applicable law or agreed to in writing, software
     11 distributed under the License is distributed on an "AS IS" BASIS,
     12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13 See the License for the specific language governing permissions and
     14 limitations under the License.
     15 
     16 Author: lode.vandevenne (at) gmail.com (Lode Vandevenne)
     17 Author: jyrki.alakuijala (at) gmail.com (Jyrki Alakuijala)
     18 */
     19 
     20 /*
     21 Functions for basic LZ77 compression and utilities for the "squeeze" LZ77
     22 compression.
     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 /*
     35 Stores lit/length and dist pairs for LZ77.
     36 Parameter litlens: Contains the literal symbols or length values.
     37 Parameter dists: Contains the distances. A value is 0 to indicate that there is
     38 no dist and the corresponding litlens value is a literal instead of a length.
     39 Parameter size: The size of both the litlens and dists arrays.
     40 The memory can best be managed by using ZopfliInitLZ77Store to initialize it,
     41 ZopfliCleanLZ77Store to destroy it, and ZopfliStoreLitLenDist to append values.
     42 
     43 */
     44 typedef 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 
     51 void ZopfliInitLZ77Store(ZopfliLZ77Store* store);
     52 void ZopfliCleanLZ77Store(ZopfliLZ77Store* store);
     53 void ZopfliCopyLZ77Store(const ZopfliLZ77Store* source, ZopfliLZ77Store* dest);
     54 void ZopfliStoreLitLenDist(unsigned short length, unsigned short dist,
     55                            ZopfliLZ77Store* store);
     56 
     57 /*
     58 Some state information for compressing a block.
     59 This is currently a bit under-used (with mainly only the longest match cache),
     60 but is kept for easy future expansion.
     61 */
     62 typedef 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 /*
     76 Finds the longest match (length and corresponding distance) for LZ77
     77 compression.
     78 Even when not using "sublen", it can be more efficient to provide an array,
     79 because only then the caching is used.
     80 array: the data
     81 pos: position in the data to find the match for
     82 size: size of the data
     83 limit: 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].
     86 sublen: 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 */
     91 void 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 /*
     97 Verifies if length and dist are indeed valid, only used for assertion.
     98 */
     99 void ZopfliVerifyLenDist(const unsigned char* data, size_t datasize, size_t pos,
    100                          unsigned short dist, unsigned short length);
    101 
    102 /*
    103 Counts the number of literal, length and distance symbols in the given lz77
    104 arrays.
    105 litlens: lz77 lit/lengths
    106 dists: ll77 distances
    107 start: where to begin counting in litlens and dists
    108 end: where to stop counting in litlens and dists (not inclusive)
    109 ll_count: count of each lit/len symbol, must have size 288 (see deflate
    110     standard)
    111 d_count: count of each dist symbol, must have size 32 (see deflate standard)
    112 */
    113 void 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 /*
    119 Does LZ77 using an algorithm similar to gzip, with lazy matching, rather than
    120 with the slow but better "squeeze" implementation.
    121 The result is placed in the ZopfliLZ77Store.
    122 If instart is larger than 0, it uses values before instart as starting
    123 dictionary.
    124 */
    125 void ZopfliLZ77Greedy(ZopfliBlockState* s, const unsigned char* in,
    126                       size_t instart, size_t inend,
    127                       ZopfliLZ77Store* store);
    128 
    129 #endif  /* ZOPFLI_LZ77_H_ */
    130