constants.h (7977B)
1 /* Copyright 2016 Google Inc. All Rights Reserved. 2 3 Distributed under MIT license. 4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT 5 */ 6 7 /** 8 * @file 9 * Common constants used in decoder and encoder API. 10 */ 11 12 #ifndef BROTLI_COMMON_CONSTANTS_H_ 13 #define BROTLI_COMMON_CONSTANTS_H_ 14 15 #include "platform.h" 16 17 /* Specification: 7.3. Encoding of the context map */ 18 #define BROTLI_CONTEXT_MAP_MAX_RLE 16 19 20 /* Specification: 2. Compressed representation overview */ 21 #define BROTLI_MAX_NUMBER_OF_BLOCK_TYPES 256 22 23 /* Specification: 3.3. Alphabet sizes: insert-and-copy length */ 24 #define BROTLI_NUM_LITERAL_SYMBOLS 256 25 #define BROTLI_NUM_COMMAND_SYMBOLS 704 26 #define BROTLI_NUM_BLOCK_LEN_SYMBOLS 26 27 #define BROTLI_MAX_CONTEXT_MAP_SYMBOLS (BROTLI_MAX_NUMBER_OF_BLOCK_TYPES + \ 28 BROTLI_CONTEXT_MAP_MAX_RLE) 29 #define BROTLI_MAX_BLOCK_TYPE_SYMBOLS (BROTLI_MAX_NUMBER_OF_BLOCK_TYPES + 2) 30 31 /* Specification: 3.5. Complex prefix codes */ 32 #define BROTLI_REPEAT_PREVIOUS_CODE_LENGTH 16 33 #define BROTLI_REPEAT_ZERO_CODE_LENGTH 17 34 #define BROTLI_CODE_LENGTH_CODES (BROTLI_REPEAT_ZERO_CODE_LENGTH + 1) 35 /* "code length of 8 is repeated" */ 36 #define BROTLI_INITIAL_REPEATED_CODE_LENGTH 8 37 38 /* "Large Window Brotli" */ 39 40 /** 41 * The theoretical maximum number of distance bits specified for large window 42 * brotli, for 64-bit encoders and decoders. Even when in practice 32-bit 43 * encoders and decoders only support up to 30 max distance bits, the value is 44 * set to 62 because it affects the large window brotli file format. 45 * Specifically, it affects the encoding of simple huffman tree for distances, 46 * see Specification RFC 7932 chapter 3.4. 47 */ 48 #define BROTLI_LARGE_MAX_DISTANCE_BITS 62U 49 #define BROTLI_LARGE_MIN_WBITS 10 50 /** 51 * The maximum supported large brotli window bits by the encoder and decoder. 52 * Large window brotli allows up to 62 bits, however the current encoder and 53 * decoder, designed for 32-bit integers, only support up to 30 bits maximum. 54 */ 55 #define BROTLI_LARGE_MAX_WBITS 30 56 57 /* Specification: 4. Encoding of distances */ 58 #define BROTLI_NUM_DISTANCE_SHORT_CODES 16 59 /** 60 * Maximal number of "postfix" bits. 61 * 62 * Number of "postfix" bits is stored as 2 bits in meta-block header. 63 */ 64 #define BROTLI_MAX_NPOSTFIX 3 65 #define BROTLI_MAX_NDIRECT 120 66 #define BROTLI_MAX_DISTANCE_BITS 24U 67 #define BROTLI_DISTANCE_ALPHABET_SIZE(NPOSTFIX, NDIRECT, MAXNBITS) ( \ 68 BROTLI_NUM_DISTANCE_SHORT_CODES + (NDIRECT) + \ 69 ((MAXNBITS) << ((NPOSTFIX) + 1))) 70 /* BROTLI_NUM_DISTANCE_SYMBOLS == 1128 */ 71 #define BROTLI_NUM_DISTANCE_SYMBOLS \ 72 BROTLI_DISTANCE_ALPHABET_SIZE( \ 73 BROTLI_MAX_NDIRECT, BROTLI_MAX_NPOSTFIX, BROTLI_LARGE_MAX_DISTANCE_BITS) 74 75 /* ((1 << 26) - 4) is the maximal distance that can be expressed in RFC 7932 76 brotli stream using NPOSTFIX = 0 and NDIRECT = 0. With other NPOSTFIX and 77 NDIRECT values distances up to ((1 << 29) + 88) could be expressed. */ 78 #define BROTLI_MAX_DISTANCE 0x3FFFFFC 79 80 /* ((1 << 31) - 4) is the safe distance limit. Using this number as a limit 81 allows safe distance calculation without overflows, given the distance 82 alphabet size is limited to corresponding size 83 (see kLargeWindowDistanceCodeLimits). */ 84 #define BROTLI_MAX_ALLOWED_DISTANCE 0x7FFFFFFC 85 86 87 /* Specification: 4. Encoding of Literal Insertion Lengths and Copy Lengths */ 88 #define BROTLI_NUM_INS_COPY_CODES 24 89 90 /* 7.1. Context modes and context ID lookup for literals */ 91 /* "context IDs for literals are in the range of 0..63" */ 92 #define BROTLI_LITERAL_CONTEXT_BITS 6 93 94 /* 7.2. Context ID for distances */ 95 #define BROTLI_DISTANCE_CONTEXT_BITS 2 96 97 /* 9.1. Format of the Stream Header */ 98 /* Number of slack bytes for window size. Don't confuse 99 with BROTLI_NUM_DISTANCE_SHORT_CODES. */ 100 #define BROTLI_WINDOW_GAP 16 101 #define BROTLI_MAX_BACKWARD_LIMIT(W) (((size_t)1 << (W)) - BROTLI_WINDOW_GAP) 102 103 typedef struct BrotliDistanceCodeLimit { 104 uint32_t max_alphabet_size; 105 uint32_t max_distance; 106 } BrotliDistanceCodeLimit; 107 108 /* This function calculates maximal size of distance alphabet, such that the 109 distances greater than the given values can not be represented. 110 111 This limits are designed to support fast and safe 32-bit decoders. 112 "32-bit" means that signed integer values up to ((1 << 31) - 1) could be 113 safely expressed. 114 115 Brotli distance alphabet symbols do not represent consecutive distance 116 ranges. Each distance alphabet symbol (excluding direct distances and short 117 codes), represent interleaved (for NPOSTFIX > 0) range of distances. 118 A "group" of consecutive (1 << NPOSTFIX) symbols represent non-interleaved 119 range. Two consecutive groups require the same amount of "extra bits". 120 121 It is important that distance alphabet represents complete "groups". 122 To avoid complex logic on encoder side about interleaved ranges 123 it was decided to restrict both sides to complete distance code "groups". 124 */ 125 BROTLI_UNUSED_FUNCTION BrotliDistanceCodeLimit BrotliCalculateDistanceCodeLimit( 126 uint32_t max_distance, uint32_t npostfix, uint32_t ndirect) { 127 BrotliDistanceCodeLimit result; 128 /* Marking this function as unused, because not all files 129 including "constants.h" use it -> compiler warns about that. */ 130 BROTLI_UNUSED(&BrotliCalculateDistanceCodeLimit); 131 if (max_distance <= ndirect) { 132 /* This case never happens / exists only for the sake of completeness. */ 133 result.max_alphabet_size = max_distance + BROTLI_NUM_DISTANCE_SHORT_CODES; 134 result.max_distance = max_distance; 135 return result; 136 } else { 137 /* The first prohibited value. */ 138 uint32_t forbidden_distance = max_distance + 1; 139 /* Subtract "directly" encoded region. */ 140 uint32_t offset = forbidden_distance - ndirect - 1; 141 uint32_t ndistbits = 0; 142 uint32_t tmp; 143 uint32_t half; 144 uint32_t group; 145 /* Postfix for the last dcode in the group. */ 146 uint32_t postfix = (1u << npostfix) - 1; 147 uint32_t extra; 148 uint32_t start; 149 /* Remove postfix and "head-start". */ 150 offset = (offset >> npostfix) + 4; 151 /* Calculate the number of distance bits. */ 152 tmp = offset / 2; 153 /* Poor-man's log2floor, to avoid extra dependencies. */ 154 while (tmp != 0) {ndistbits++; tmp = tmp >> 1;} 155 /* One bit is covered with subrange addressing ("half"). */ 156 ndistbits--; 157 /* Find subrange. */ 158 half = (offset >> ndistbits) & 1; 159 /* Calculate the "group" part of dcode. */ 160 group = ((ndistbits - 1) << 1) | half; 161 /* Calculated "group" covers the prohibited distance value. */ 162 if (group == 0) { 163 /* This case is added for correctness; does not occur for limit > 128. */ 164 result.max_alphabet_size = ndirect + BROTLI_NUM_DISTANCE_SHORT_CODES; 165 result.max_distance = ndirect; 166 return result; 167 } 168 /* Decrement "group", so it is the last permitted "group". */ 169 group--; 170 /* After group was decremented, ndistbits and half must be recalculated. */ 171 ndistbits = (group >> 1) + 1; 172 /* The last available distance in the subrange has all extra bits set. */ 173 extra = (1u << ndistbits) - 1; 174 /* Calculate region start. NB: ndistbits >= 1. */ 175 start = (1u << (ndistbits + 1)) - 4; 176 /* Move to subregion. */ 177 start += (group & 1) << ndistbits; 178 /* Calculate the alphabet size. */ 179 result.max_alphabet_size = ((group << npostfix) | postfix) + ndirect + 180 BROTLI_NUM_DISTANCE_SHORT_CODES + 1; 181 /* Calculate the maximal distance representable by alphabet. */ 182 result.max_distance = ((start + extra) << npostfix) + postfix + ndirect + 1; 183 return result; 184 } 185 } 186 187 /* Represents the range of values belonging to a prefix code: 188 [offset, offset + 2^nbits) */ 189 typedef struct { 190 uint16_t offset; 191 uint8_t nbits; 192 } BrotliPrefixCodeRange; 193 194 /* "Soft-private", it is exported, but not "advertised" as API. */ 195 BROTLI_COMMON_API extern const BROTLI_MODEL("small") 196 BrotliPrefixCodeRange _kBrotliPrefixCodeRanges[BROTLI_NUM_BLOCK_LEN_SYMBOLS]; 197 198 #endif /* BROTLI_COMMON_CONSTANTS_H_ */