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