util.h revision 4975aa5e50761cdeb335b3bf029332df469aa472
1/* 2Copyright 2011 Google Inc. All Rights Reserved. 3 4Licensed under the Apache License, Version 2.0 (the "License"); 5you may not use this file except in compliance with the License. 6You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10Unless required by applicable law or agreed to in writing, software 11distributed under the License is distributed on an "AS IS" BASIS, 12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13See the License for the specific language governing permissions and 14limitations under the License. 15 16Author: lode.vandevenne@gmail.com (Lode Vandevenne) 17Author: jyrki.alakuijala@gmail.com (Jyrki Alakuijala) 18*/ 19 20/* 21Several utilities, including: #defines to try different compression results, 22basic deflate specification values and generic program options. 23*/ 24 25#ifndef ZOPFLI_UTIL_H_ 26#define ZOPFLI_UTIL_H_ 27 28#include <string.h> 29#include <stdlib.h> 30 31/* Minimum and maximum length that can be encoded in deflate. */ 32#define ZOPFLI_MAX_MATCH 258 33#define ZOPFLI_MIN_MATCH 3 34 35/* 36The window size for deflate. Must be a power of two. This should be 32768, the 37maximum possible by the deflate spec. Anything less hurts compression more than 38speed. 39*/ 40#define ZOPFLI_WINDOW_SIZE 32768 41 42/* 43The window mask used to wrap indices into the window. This is why the 44window size must be a power of two. 45*/ 46#define ZOPFLI_WINDOW_MASK (ZOPFLI_WINDOW_SIZE - 1) 47 48/* 49A block structure of huge, non-smart, blocks to divide the input into, to allow 50operating on huge files without exceeding memory, such as the 1GB wiki9 corpus. 51The whole compression algorithm, including the smarter block splitting, will 52be executed independently on each huge block. 53Dividing into huge blocks hurts compression, but not much relative to the size. 54Set this to, for example, 20MB (20000000). Set it to 0 to disable master blocks. 55*/ 56#define ZOPFLI_MASTER_BLOCK_SIZE 20000000 57 58/* 59Used to initialize costs for example 60*/ 61#define ZOPFLI_LARGE_FLOAT 1e30 62 63/* 64For longest match cache. max 256. Uses huge amounts of memory but makes it 65faster. Uses this many times three bytes per single byte of the input data. 66This is so because longest match finding has to find the exact distance 67that belongs to each length for the best lz77 strategy. 68Good values: e.g. 5, 8. 69*/ 70#define ZOPFLI_CACHE_LENGTH 8 71 72/* 73limit the max hash chain hits for this hash value. This has an effect only 74on files where the hash value is the same very often. On these files, this 75gives worse compression (the value should ideally be 32768, which is the 76ZOPFLI_WINDOW_SIZE, while zlib uses 4096 even for best level), but makes it 77faster on some specific files. 78Good value: e.g. 8192. 79*/ 80#define ZOPFLI_MAX_CHAIN_HITS 8192 81 82/* 83Whether to use the longest match cache for ZopfliFindLongestMatch. This cache 84consumes a lot of memory but speeds it up. No effect on compression size. 85*/ 86#define ZOPFLI_LONGEST_MATCH_CACHE 87 88/* 89Enable to remember amount of successive identical bytes in the hash chain for 90finding longest match 91required for ZOPFLI_HASH_SAME_HASH and ZOPFLI_SHORTCUT_LONG_REPETITIONS 92This has no effect on the compression result, and enabling it increases speed. 93*/ 94#define ZOPFLI_HASH_SAME 95 96/* 97Switch to a faster hash based on the info from ZOPFLI_HASH_SAME once the 98best length so far is long enough. This is way faster for files with lots of 99identical bytes, on which the compressor is otherwise too slow. Regular files 100are unaffected or maybe a tiny bit slower. 101This has no effect on the compression result, only on speed. 102*/ 103#define ZOPFLI_HASH_SAME_HASH 104 105/* 106Enable this, to avoid slowness for files which are a repetition of the same 107character more than a multiple of ZOPFLI_MAX_MATCH times. This should not affect 108the compression result. 109*/ 110#define ZOPFLI_SHORTCUT_LONG_REPETITIONS 111 112/* 113Whether to use lazy matching in the greedy LZ77 implementation. This gives a 114better result of ZopfliLZ77Greedy, but the effect this has on the optimal LZ77 115varies from file to file. 116*/ 117#define ZOPFLI_LAZY_MATCHING 118 119/* 120Gets the symbol for the given length, cfr. the DEFLATE spec. 121Returns the symbol in the range [257-285] (inclusive) 122*/ 123int ZopfliGetLengthSymbol(int l); 124 125/* Gets the amount of extra bits for the given length, cfr. the DEFLATE spec. */ 126int ZopfliGetLengthExtraBits(int l); 127 128/* Gets value of the extra bits for the given length, cfr. the DEFLATE spec. */ 129int ZopfliGetLengthExtraBitsValue(int l); 130 131/* Gets the symbol for the given dist, cfr. the DEFLATE spec. */ 132int ZopfliGetDistSymbol(int dist); 133 134/* Gets the amount of extra bits for the given dist, cfr. the DEFLATE spec. */ 135int ZopfliGetDistExtraBits(int dist); 136 137/* Gets value of the extra bits for the given dist, cfr. the DEFLATE spec. */ 138int ZopfliGetDistExtraBitsValue(int dist); 139 140/* 141Appends value to dynamically allocated memory, doubling its allocation size 142whenever needed. 143 144value: the value to append, type T 145data: pointer to the dynamic array to append to, type T** 146size: pointer to the size of the array to append to, type size_t*. This is the 147size that you consider the array to be, not the internal allocation size. 148Precondition: allocated size of data is at least a power of two greater than or 149equal than *size. 150*/ 151#ifdef __cplusplus /* C++ cannot assign void* from malloc to *data */ 152#define ZOPFLI_APPEND_DATA(/* T */ value, /* T** */ data, /* size_t* */ size) {\ 153 if (!((*size) & ((*size) - 1))) {\ 154 /*double alloc size if it's a power of two*/\ 155 void** data_void = reinterpret_cast<void**>(data);\ 156 *data_void = (*size) == 0 ? malloc(sizeof(**data))\ 157 : realloc((*data), (*size) * 2 * sizeof(**data));\ 158 }\ 159 (*data)[(*size)] = (value);\ 160 (*size)++;\ 161} 162#else /* C gives problems with strict-aliasing rules for (void**) cast */ 163#define ZOPFLI_APPEND_DATA(/* T */ value, /* T** */ data, /* size_t* */ size) {\ 164 if (!((*size) & ((*size) - 1))) {\ 165 /*double alloc size if it's a power of two*/\ 166 (*data) = (*size) == 0 ? malloc(sizeof(**data))\ 167 : realloc((*data), (*size) * 2 * sizeof(**data));\ 168 }\ 169 (*data)[(*size)] = (value);\ 170 (*size)++;\ 171} 172#endif 173 174 175#endif /* ZOPFLI_UTIL_H_ */ 176