1 /* Copyright 2013 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 /* This class models a sequence of literals and a backward reference copy. */
9 #ifndef BROTLI_ENC_COMMAND_H_
10 #define BROTLI_ENC_COMMAND_H_
12 #include "../common/constants.h"
13 #include "../common/platform.h"
14 #include <brotli/types.h>
15 #include "./fast_log.h"
19 #if defined(__cplusplus) || defined(c_plusplus)
23 static uint32_t kInsBase
[] = { 0, 1, 2, 3, 4, 5, 6, 8, 10, 14, 18, 26, 34, 50,
24 66, 98, 130, 194, 322, 578, 1090, 2114, 6210, 22594 };
25 static uint32_t kInsExtra
[] = { 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4,
26 5, 5, 6, 7, 8, 9, 10, 12, 14, 24 };
27 static uint32_t kCopyBase
[] = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 18, 22, 30,
28 38, 54, 70, 102, 134, 198, 326, 582, 1094, 2118 };
29 static uint32_t kCopyExtra
[] = { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3,
30 4, 4, 5, 5, 6, 7, 8, 9, 10, 24 };
32 static BROTLI_INLINE
uint16_t GetInsertLengthCode(size_t insertlen
) {
34 return (uint16_t)insertlen
;
35 } else if (insertlen
< 130) {
36 uint32_t nbits
= Log2FloorNonZero(insertlen
- 2) - 1u;
37 return (uint16_t)((nbits
<< 1) + ((insertlen
- 2) >> nbits
) + 2);
38 } else if (insertlen
< 2114) {
39 return (uint16_t)(Log2FloorNonZero(insertlen
- 66) + 10);
40 } else if (insertlen
< 6210) {
42 } else if (insertlen
< 22594) {
49 static BROTLI_INLINE
uint16_t GetCopyLengthCode(size_t copylen
) {
51 return (uint16_t)(copylen
- 2);
52 } else if (copylen
< 134) {
53 uint32_t nbits
= Log2FloorNonZero(copylen
- 6) - 1u;
54 return (uint16_t)((nbits
<< 1) + ((copylen
- 6) >> nbits
) + 4);
55 } else if (copylen
< 2118) {
56 return (uint16_t)(Log2FloorNonZero(copylen
- 70) + 12);
62 static BROTLI_INLINE
uint16_t CombineLengthCodes(
63 uint16_t inscode
, uint16_t copycode
, BROTLI_BOOL use_last_distance
) {
65 (uint16_t)((copycode
& 0x7u
) | ((inscode
& 0x7u
) << 3u));
66 if (use_last_distance
&& inscode
< 8u && copycode
< 16u) {
67 return (copycode
< 8u) ? bits64
: (bits64
| 64u);
69 /* Specification: 5 Encoding of ... (last table) */
70 /* offset = 2 * index, where index is in range [0..8] */
71 uint32_t offset
= 2u * ((copycode
>> 3u) + 3u * (inscode
>> 3u));
72 /* All values in specification are K * 64,
73 where K = [2, 3, 6, 4, 5, 8, 7, 9, 10],
74 i + 1 = [1, 2, 3, 4, 5, 6, 7, 8, 9],
75 K - i - 1 = [1, 1, 3, 0, 0, 2, 0, 1, 2] = D.
76 All values in D require only 2 bits to encode.
77 Magic constant is shifted 6 bits left, to avoid final multiplication. */
78 offset
= (offset
<< 5u) + 0x40u
+ ((0x520D40u
>> offset
) & 0xC0u
);
79 return (uint16_t)(offset
| bits64
);
83 static BROTLI_INLINE
void GetLengthCode(size_t insertlen
, size_t copylen
,
84 BROTLI_BOOL use_last_distance
,
86 uint16_t inscode
= GetInsertLengthCode(insertlen
);
87 uint16_t copycode
= GetCopyLengthCode(copylen
);
88 *code
= CombineLengthCodes(inscode
, copycode
, use_last_distance
);
91 static BROTLI_INLINE
uint32_t GetInsertBase(uint16_t inscode
) {
92 return kInsBase
[inscode
];
95 static BROTLI_INLINE
uint32_t GetInsertExtra(uint16_t inscode
) {
96 return kInsExtra
[inscode
];
99 static BROTLI_INLINE
uint32_t GetCopyBase(uint16_t copycode
) {
100 return kCopyBase
[copycode
];
103 static BROTLI_INLINE
uint32_t GetCopyExtra(uint16_t copycode
) {
104 return kCopyExtra
[copycode
];
107 typedef struct Command
{
108 uint32_t insert_len_
;
109 /* Stores copy_len in low 25 bits and copy_code - copy_len in high 7 bit. */
111 /* Stores distance extra bits. */
112 uint32_t dist_extra_
;
113 uint16_t cmd_prefix_
;
114 /* Stores distance code in low 10 bits
115 and number of extra bits in high 6 bits. */
116 uint16_t dist_prefix_
;
119 /* distance_code is e.g. 0 for same-as-last short code, or 16 for offset 1. */
120 static BROTLI_INLINE
void InitCommand(Command
* self
,
121 const BrotliDistanceParams
* dist
, size_t insertlen
,
122 size_t copylen
, int copylen_code_delta
, size_t distance_code
) {
123 /* Don't rely on signed int representation, use honest casts. */
124 uint32_t delta
= (uint8_t)((int8_t)copylen_code_delta
);
125 self
->insert_len_
= (uint32_t)insertlen
;
126 self
->copy_len_
= (uint32_t)(copylen
| (delta
<< 25));
127 /* The distance prefix and extra bits are stored in this Command as if
128 npostfix and ndirect were 0, they are only recomputed later after the
129 clustering if needed. */
130 PrefixEncodeCopyDistance(
131 distance_code
, dist
->num_direct_distance_codes
,
132 dist
->distance_postfix_bits
, &self
->dist_prefix_
, &self
->dist_extra_
);
134 insertlen
, (size_t)((int)copylen
+ copylen_code_delta
),
135 TO_BROTLI_BOOL((self
->dist_prefix_
& 0x3FF) == 0), &self
->cmd_prefix_
);
138 static BROTLI_INLINE
void InitInsertCommand(Command
* self
, size_t insertlen
) {
139 self
->insert_len_
= (uint32_t)insertlen
;
140 self
->copy_len_
= 4 << 25;
141 self
->dist_extra_
= 0;
142 self
->dist_prefix_
= BROTLI_NUM_DISTANCE_SHORT_CODES
;
143 GetLengthCode(insertlen
, 4, BROTLI_FALSE
, &self
->cmd_prefix_
);
146 static BROTLI_INLINE
uint32_t CommandRestoreDistanceCode(
147 const Command
* self
, const BrotliDistanceParams
* dist
) {
148 if ((self
->dist_prefix_
& 0x3FFu
) <
149 BROTLI_NUM_DISTANCE_SHORT_CODES
+ dist
->num_direct_distance_codes
) {
150 return self
->dist_prefix_
& 0x3FFu
;
152 uint32_t dcode
= self
->dist_prefix_
& 0x3FFu
;
153 uint32_t nbits
= self
->dist_prefix_
>> 10;
154 uint32_t extra
= self
->dist_extra_
;
155 uint32_t postfix_mask
= (1U << dist
->distance_postfix_bits
) - 1U;
156 uint32_t hcode
= (dcode
- dist
->num_direct_distance_codes
-
157 BROTLI_NUM_DISTANCE_SHORT_CODES
) >>
158 dist
->distance_postfix_bits
;
159 uint32_t lcode
= (dcode
- dist
->num_direct_distance_codes
-
160 BROTLI_NUM_DISTANCE_SHORT_CODES
) & postfix_mask
;
161 uint32_t offset
= ((2U + (hcode
& 1U)) << nbits
) - 4U;
162 return ((offset
+ extra
) << dist
->distance_postfix_bits
) + lcode
+
163 dist
->num_direct_distance_codes
+ BROTLI_NUM_DISTANCE_SHORT_CODES
;
167 static BROTLI_INLINE
uint32_t CommandDistanceContext(const Command
* self
) {
168 uint32_t r
= self
->cmd_prefix_
>> 6;
169 uint32_t c
= self
->cmd_prefix_
& 7;
170 if ((r
== 0 || r
== 2 || r
== 4 || r
== 7) && (c
<= 2)) {
176 static BROTLI_INLINE
uint32_t CommandCopyLen(const Command
* self
) {
177 return self
->copy_len_
& 0x1FFFFFF;
180 static BROTLI_INLINE
uint32_t CommandCopyLenCode(const Command
* self
) {
181 uint32_t modifier
= self
->copy_len_
>> 25;
182 int32_t delta
= (int8_t)((uint8_t)(modifier
| ((modifier
& 0x40) << 1)));
183 return (uint32_t)((int32_t)(self
->copy_len_
& 0x1FFFFFF) + delta
);
186 #if defined(__cplusplus) || defined(c_plusplus)
190 #endif /* BROTLI_ENC_COMMAND_H_ */