1 /* Copyright 2016 Google Inc. All Rights Reserved.
3 Distributed under MIT license.
4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
7 /* Constants and formulas that affect speed-ratio trade-offs and thus define
10 #ifndef BROTLI_ENC_QUALITY_H_
11 #define BROTLI_ENC_QUALITY_H_
15 #define FAST_ONE_PASS_COMPRESSION_QUALITY 0
16 #define FAST_TWO_PASS_COMPRESSION_QUALITY 1
17 #define ZOPFLIFICATION_QUALITY 10
18 #define HQ_ZOPFLIFICATION_QUALITY 11
20 #define MAX_QUALITY_FOR_STATIC_ENRTOPY_CODES 2
21 #define MIN_QUALITY_FOR_BLOCK_SPLIT 4
22 #define MIN_QUALITY_FOR_OPTIMIZE_HISTOGRAMS 4
23 #define MIN_QUALITY_FOR_EXTENSIVE_REFERENCE_SEARCH 5
24 #define MIN_QUALITY_FOR_CONTEXT_MODELING 5
25 #define MIN_QUALITY_FOR_HQ_CONTEXT_MODELING 7
26 #define MIN_QUALITY_FOR_HQ_BLOCK_SPLITTING 10
27 /* Only for "font" mode. */
28 #define MIN_QUALITY_FOR_RECOMPUTE_DISTANCE_PREFIXES 10
30 /* For quality below MIN_QUALITY_FOR_BLOCK_SPLIT there is no block splitting,
31 so we buffer at most this much literals and commands. */
32 #define MAX_NUM_DELAYED_SYMBOLS 0x2fff
34 /* Encoding parameters */
35 typedef struct BrotliEncoderParams
{
36 BrotliEncoderMode mode
;
40 } BrotliEncoderParams
;
42 /* Returns hashtable size for quality levels 0 and 1. */
43 static BROTLI_INLINE
size_t MaxHashTableSize(int quality
) {
44 return quality
== FAST_ONE_PASS_COMPRESSION_QUALITY
? 1 << 15 : 1 << 17;
47 /* The maximum length for which the zopflification uses distinct distances. */
48 #define MAX_ZOPFLI_LEN_QUALITY_10 150
49 #define MAX_ZOPFLI_LEN_QUALITY_11 325
51 static BROTLI_INLINE
size_t MaxZopfliLen(const BrotliEncoderParams
* params
) {
52 return params
->quality
<= 10 ?
53 MAX_ZOPFLI_LEN_QUALITY_10
:
54 MAX_ZOPFLI_LEN_QUALITY_11
;
57 /* Number of best candidates to evaluate to expand zopfli chain. */
58 static BROTLI_INLINE
size_t MaxZopfliCandidates(
59 const BrotliEncoderParams
* params
) {
60 return params
->quality
<= 10 ? 1 : 5;
63 static BROTLI_INLINE
void SanitizeParams(BrotliEncoderParams
* params
) {
64 params
->quality
= BROTLI_MIN(int, BROTLI_MAX_QUALITY
,
65 BROTLI_MAX(int, BROTLI_MIN_QUALITY
, params
->quality
));
66 if (params
->lgwin
< kBrotliMinWindowBits
) {
67 params
->lgwin
= kBrotliMinWindowBits
;
68 } else if (params
->lgwin
> kBrotliMaxWindowBits
) {
69 params
->lgwin
= kBrotliMaxWindowBits
;
73 /* Returns optimized lg_block value. */
74 static BROTLI_INLINE
int ComputeLgBlock(const BrotliEncoderParams
* params
) {
75 int lgblock
= params
->lgblock
;
76 if (params
->quality
== FAST_ONE_PASS_COMPRESSION_QUALITY
||
77 params
->quality
== FAST_TWO_PASS_COMPRESSION_QUALITY
) {
78 lgblock
= params
->lgwin
;
79 } else if (params
->quality
< MIN_QUALITY_FOR_BLOCK_SPLIT
) {
81 } else if (lgblock
== 0) {
83 if (params
->quality
>= 9 && params
->lgwin
> lgblock
) {
84 lgblock
= BROTLI_MIN(int, 18, params
->lgwin
);
87 lgblock
= BROTLI_MIN(int, kBrotliMaxInputBlockBits
,
88 BROTLI_MAX(int, kBrotliMinInputBlockBits
, lgblock
));
93 /* Returns log2 of the size of main ring buffer area.
94 Allocate at least lgwin + 1 bits for the ring buffer so that the newly
95 added block fits there completely and we still get lgwin bits and at least
96 read_block_size_bits + 1 bits because the copy tail length needs to be
97 smaller than ringbuffer size. */
98 static BROTLI_INLINE
int ComputeRbBits(const BrotliEncoderParams
* params
) {
99 return 1 + BROTLI_MAX(int, params
->lgwin
, params
->lgblock
);
102 static BROTLI_INLINE
size_t MaxMetablockSize(
103 const BrotliEncoderParams
* params
) {
104 int bits
= BROTLI_MIN(int, ComputeRbBits(params
), kBrotliMaxInputBlockBits
);
105 return (size_t)1 << bits
;
108 /* When searching for backward references and have not seen matches for a long
109 time, we can skip some match lookups. Unsuccessful match lookups are very
110 expensive and this kind of a heuristic speeds up compression quite a lot.
111 At first 8 byte strides are taken and every second byte is put to hasher.
112 After 4x more literals stride by 16 bytes, every put 4-th byte to hasher.
113 Applied only to qualities 2 to 9. */
114 static BROTLI_INLINE
size_t LiteralSpreeLengthForSparseSearch(
115 const BrotliEncoderParams
* params
) {
116 return params
->quality
< 9 ? 64 : 512;
119 static BROTLI_INLINE
int ChooseHasher(const BrotliEncoderParams
* params
) {
120 if (params
->quality
> 9) {
122 } else if (params
->quality
< 5) {
123 return params
->quality
;
124 } else if (params
->lgwin
<= 16) {
125 return params
->quality
< 7 ? 40 : params
->quality
< 9 ? 41 : 42;
127 return params
->quality
;
130 #endif /* BROTLI_ENC_QUALITY_H_ */