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/types.h"
13 #include "../common/port.h"
14 #include "./fast_log.h"
17 #if defined(__cplusplus) || defined(c_plusplus)
21 static uint32_t kInsBase
[] = { 0, 1, 2, 3, 4, 5, 6, 8, 10, 14, 18, 26, 34, 50,
22 66, 98, 130, 194, 322, 578, 1090, 2114, 6210, 22594 };
23 static uint32_t kInsExtra
[] = { 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4,
24 5, 5, 6, 7, 8, 9, 10, 12, 14, 24 };
25 static uint32_t kCopyBase
[] = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 18, 22, 30,
26 38, 54, 70, 102, 134, 198, 326, 582, 1094, 2118 };
27 static uint32_t kCopyExtra
[] = { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3,
28 4, 4, 5, 5, 6, 7, 8, 9, 10, 24 };
30 static BROTLI_INLINE
uint16_t GetInsertLengthCode(size_t insertlen
) {
32 return (uint16_t)insertlen
;
33 } else if (insertlen
< 130) {
34 uint32_t nbits
= Log2FloorNonZero(insertlen
- 2) - 1u;
35 return (uint16_t)((nbits
<< 1) + ((insertlen
- 2) >> nbits
) + 2);
36 } else if (insertlen
< 2114) {
37 return (uint16_t)(Log2FloorNonZero(insertlen
- 66) + 10);
38 } else if (insertlen
< 6210) {
40 } else if (insertlen
< 22594) {
47 static BROTLI_INLINE
uint16_t GetCopyLengthCode(size_t copylen
) {
49 return (uint16_t)(copylen
- 2);
50 } else if (copylen
< 134) {
51 uint32_t nbits
= Log2FloorNonZero(copylen
- 6) - 1u;
52 return (uint16_t)((nbits
<< 1) + ((copylen
- 6) >> nbits
) + 4);
53 } else if (copylen
< 2118) {
54 return (uint16_t)(Log2FloorNonZero(copylen
- 70) + 12);
60 static BROTLI_INLINE
uint16_t CombineLengthCodes(
61 uint16_t inscode
, uint16_t copycode
, BROTLI_BOOL use_last_distance
) {
63 (uint16_t)((copycode
& 0x7u
) | ((inscode
& 0x7u
) << 3));
64 if (use_last_distance
&& inscode
< 8 && copycode
< 16) {
65 return (copycode
< 8) ? bits64
: (bits64
| 64);
67 /* "To convert an insert-and-copy length code to an insert length code and
68 a copy length code, the following table can be used" */
69 static const uint16_t cells
[9] = { 128u, 192u, 384u, 256u, 320u, 512u,
71 return cells
[(copycode
>> 3) + 3 * (inscode
>> 3)] | bits64
;
75 static BROTLI_INLINE
void GetLengthCode(size_t insertlen
, size_t copylen
,
76 BROTLI_BOOL use_last_distance
,
78 uint16_t inscode
= GetInsertLengthCode(insertlen
);
79 uint16_t copycode
= GetCopyLengthCode(copylen
);
80 *code
= CombineLengthCodes(inscode
, copycode
, use_last_distance
);
83 static BROTLI_INLINE
uint32_t GetInsertBase(uint16_t inscode
) {
84 return kInsBase
[inscode
];
87 static BROTLI_INLINE
uint32_t GetInsertExtra(uint16_t inscode
) {
88 return kInsExtra
[inscode
];
91 static BROTLI_INLINE
uint32_t GetCopyBase(uint16_t copycode
) {
92 return kCopyBase
[copycode
];
95 static BROTLI_INLINE
uint32_t GetCopyExtra(uint16_t copycode
) {
96 return kCopyExtra
[copycode
];
99 typedef struct Command
{
100 uint32_t insert_len_
;
101 /* Stores copy_len in low 24 bits and copy_len XOR copy_code in high 8 bit. */
103 uint32_t dist_extra_
;
104 uint16_t cmd_prefix_
;
105 uint16_t dist_prefix_
;
108 /* distance_code is e.g. 0 for same-as-last short code, or 16 for offset 1. */
109 static BROTLI_INLINE
void InitCommand(Command
* self
, size_t insertlen
,
110 size_t copylen
, size_t copylen_code
, size_t distance_code
) {
111 self
->insert_len_
= (uint32_t)insertlen
;
112 self
->copy_len_
= (uint32_t)(copylen
| ((copylen_code
^ copylen
) << 24));
113 /* The distance prefix and extra bits are stored in this Command as if
114 npostfix and ndirect were 0, they are only recomputed later after the
115 clustering if needed. */
116 PrefixEncodeCopyDistance(
117 distance_code
, 0, 0, &self
->dist_prefix_
, &self
->dist_extra_
);
119 insertlen
, copylen_code
, TO_BROTLI_BOOL(self
->dist_prefix_
== 0),
123 static BROTLI_INLINE
void InitInsertCommand(Command
* self
, size_t insertlen
) {
124 self
->insert_len_
= (uint32_t)insertlen
;
125 self
->copy_len_
= 4 << 24;
126 self
->dist_extra_
= 0;
127 self
->dist_prefix_
= 16;
128 GetLengthCode(insertlen
, 4, BROTLI_FALSE
, &self
->cmd_prefix_
);
131 static BROTLI_INLINE
uint32_t CommandDistanceCode(const Command
* self
) {
132 if (self
->dist_prefix_
< 16) {
133 return self
->dist_prefix_
;
135 uint32_t nbits
= self
->dist_extra_
>> 24;
136 uint32_t extra
= self
->dist_extra_
& 0xffffff;
137 uint32_t prefix
= self
->dist_prefix_
- 12u - 2u * nbits
;
138 return (prefix
<< nbits
) + extra
+ 12;
142 static BROTLI_INLINE
uint32_t CommandDistanceContext(const Command
* self
) {
143 uint32_t r
= self
->cmd_prefix_
>> 6;
144 uint32_t c
= self
->cmd_prefix_
& 7;
145 if ((r
== 0 || r
== 2 || r
== 4 || r
== 7) && (c
<= 2)) {
151 static BROTLI_INLINE
uint32_t CommandCopyLen(const Command
* self
) {
152 return self
->copy_len_
& 0xFFFFFF;
155 static BROTLI_INLINE
uint32_t CommandCopyLenCode(const Command
* self
) {
156 return (self
->copy_len_
& 0xFFFFFF) ^ (self
->copy_len_
>> 24);
159 #if defined(__cplusplus) || defined(c_plusplus)
163 #endif /* BROTLI_ENC_COMMAND_H_ */