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