1 /* Copyright 2013 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 /* Function to find backward reference copies. */
8
9 #include "backward_references.h"
10
11 #include "../common/constants.h"
12 #include "../common/dictionary.h"
13 #include "../common/platform.h"
14 #include <brotli/types.h>
15 #include "command.h"
16 #include "compound_dictionary.h"
17 #include "dictionary_hash.h"
18 #include "encoder_dict.h"
19 #include "memory.h"
20 #include "quality.h"
21
22 #if defined(__cplusplus) || defined(c_plusplus)
23 extern "C" {
24 #endif
25
ComputeDistanceCode(size_t distance,size_t max_distance,const int * dist_cache)26 static BROTLI_INLINE size_t ComputeDistanceCode(size_t distance,
27 size_t max_distance,
28 const int* dist_cache) {
29 if (distance <= max_distance) {
30 size_t distance_plus_3 = distance + 3;
31 size_t offset0 = distance_plus_3 - (size_t)dist_cache[0];
32 size_t offset1 = distance_plus_3 - (size_t)dist_cache[1];
33 if (distance == (size_t)dist_cache[0]) {
34 return 0;
35 } else if (distance == (size_t)dist_cache[1]) {
36 return 1;
37 } else if (offset0 < 7) {
38 return (0x9750468 >> (4 * offset0)) & 0xF;
39 } else if (offset1 < 7) {
40 return (0xFDB1ACE >> (4 * offset1)) & 0xF;
41 } else if (distance == (size_t)dist_cache[2]) {
42 return 2;
43 } else if (distance == (size_t)dist_cache[3]) {
44 return 3;
45 }
46 }
47 return distance + BROTLI_NUM_DISTANCE_SHORT_CODES - 1;
48 }
49
50 #define EXPAND_CAT(a, b) CAT(a, b)
51 #define CAT(a, b) a ## b
52 #define FN(X) EXPAND_CAT(X, HASHER())
53 #define EXPORT_FN(X) EXPAND_CAT(X, EXPAND_CAT(PREFIX(), HASHER()))
54
55 #define PREFIX() N
56 #define ENABLE_COMPOUND_DICTIONARY 0
57
58 #define HASHER() H2
59 /* NOLINTNEXTLINE(build/include) */
60 #include "backward_references_inc.h"
61 #undef HASHER
62
63 #define HASHER() H3
64 /* NOLINTNEXTLINE(build/include) */
65 #include "backward_references_inc.h"
66 #undef HASHER
67
68 #define HASHER() H4
69 /* NOLINTNEXTLINE(build/include) */
70 #include "backward_references_inc.h"
71 #undef HASHER
72
73 #define HASHER() H5
74 /* NOLINTNEXTLINE(build/include) */
75 #include "backward_references_inc.h"
76 #undef HASHER
77
78 #define HASHER() H6
79 /* NOLINTNEXTLINE(build/include) */
80 #include "backward_references_inc.h"
81 #undef HASHER
82
83 #define HASHER() H40
84 /* NOLINTNEXTLINE(build/include) */
85 #include "backward_references_inc.h"
86 #undef HASHER
87
88 #define HASHER() H41
89 /* NOLINTNEXTLINE(build/include) */
90 #include "backward_references_inc.h"
91 #undef HASHER
92
93 #define HASHER() H42
94 /* NOLINTNEXTLINE(build/include) */
95 #include "backward_references_inc.h"
96 #undef HASHER
97
98 #define HASHER() H54
99 /* NOLINTNEXTLINE(build/include) */
100 #include "backward_references_inc.h"
101 #undef HASHER
102
103 #define HASHER() H35
104 /* NOLINTNEXTLINE(build/include) */
105 #include "backward_references_inc.h"
106 #undef HASHER
107
108 #define HASHER() H55
109 /* NOLINTNEXTLINE(build/include) */
110 #include "backward_references_inc.h"
111 #undef HASHER
112
113 #define HASHER() H65
114 /* NOLINTNEXTLINE(build/include) */
115 #include "backward_references_inc.h"
116 #undef HASHER
117
118 #undef ENABLE_COMPOUND_DICTIONARY
119 #undef PREFIX
120 #define PREFIX() D
121 #define ENABLE_COMPOUND_DICTIONARY 1
122
123 #define HASHER() H5
124 /* NOLINTNEXTLINE(build/include) */
125 #include "backward_references_inc.h"
126 #undef HASHER
127 #define HASHER() H6
128 /* NOLINTNEXTLINE(build/include) */
129 #include "backward_references_inc.h"
130 #undef HASHER
131 #define HASHER() H40
132 /* NOLINTNEXTLINE(build/include) */
133 #include "backward_references_inc.h"
134 #undef HASHER
135 #define HASHER() H41
136 /* NOLINTNEXTLINE(build/include) */
137 #include "backward_references_inc.h"
138 #undef HASHER
139 #define HASHER() H42
140 /* NOLINTNEXTLINE(build/include) */
141 #include "backward_references_inc.h"
142 #undef HASHER
143 #define HASHER() H55
144 /* NOLINTNEXTLINE(build/include) */
145 #include "backward_references_inc.h"
146 #undef HASHER
147 #define HASHER() H65
148 /* NOLINTNEXTLINE(build/include) */
149 #include "backward_references_inc.h"
150 #undef HASHER
151
152 #undef ENABLE_COMPOUND_DICTIONARY
153 #undef PREFIX
154
155 #undef EXPORT_FN
156 #undef FN
157 #undef CAT
158 #undef EXPAND_CAT
159
BrotliCreateBackwardReferences(size_t num_bytes,size_t position,const uint8_t * ringbuffer,size_t ringbuffer_mask,ContextLut literal_context_lut,const BrotliEncoderParams * params,Hasher * hasher,int * dist_cache,size_t * last_insert_len,Command * commands,size_t * num_commands,size_t * num_literals)160 void BrotliCreateBackwardReferences(size_t num_bytes,
161 size_t position, const uint8_t* ringbuffer, size_t ringbuffer_mask,
162 ContextLut literal_context_lut, const BrotliEncoderParams* params,
163 Hasher* hasher, int* dist_cache, size_t* last_insert_len,
164 Command* commands, size_t* num_commands, size_t* num_literals) {
165 if (params->dictionary.compound.num_chunks != 0) {
166 switch (params->hasher.type) {
167 #define CASE_(N) \
168 case N: \
169 CreateBackwardReferencesDH ## N(num_bytes, \
170 position, ringbuffer, ringbuffer_mask, \
171 literal_context_lut, params, hasher, dist_cache, \
172 last_insert_len, commands, num_commands, num_literals); \
173 return;
174 CASE_(5)
175 CASE_(6)
176 CASE_(40)
177 CASE_(41)
178 CASE_(42)
179 CASE_(55)
180 CASE_(65)
181 #undef CASE_
182 default:
183 break;
184 }
185 }
186
187 switch (params->hasher.type) {
188 #define CASE_(N) \
189 case N: \
190 CreateBackwardReferencesNH ## N(num_bytes, \
191 position, ringbuffer, ringbuffer_mask, \
192 literal_context_lut, params, hasher, dist_cache, \
193 last_insert_len, commands, num_commands, num_literals); \
194 return;
195 FOR_GENERIC_HASHERS(CASE_)
196 #undef CASE_
197 default:
198 break;
199 }
200 }
201
202 #if defined(__cplusplus) || defined(c_plusplus)
203 } /* extern "C" */
204 #endif
205