/src/h2o/deps/brotli/c/enc/block_splitter.c
Line | Count | Source (jump to first uncovered line) |
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 | | /* Block split point selection utilities. */ |
8 | | |
9 | | #include "./block_splitter.h" |
10 | | |
11 | | #include <assert.h> |
12 | | #include <string.h> /* memcpy, memset */ |
13 | | |
14 | | #include "./bit_cost.h" |
15 | | #include "./cluster.h" |
16 | | #include "./command.h" |
17 | | #include "./fast_log.h" |
18 | | #include "./histogram.h" |
19 | | #include "./memory.h" |
20 | | #include "./port.h" |
21 | | #include "./quality.h" |
22 | | |
23 | | #if defined(__cplusplus) || defined(c_plusplus) |
24 | | extern "C" { |
25 | | #endif |
26 | | |
27 | | static const size_t kMaxLiteralHistograms = 100; |
28 | | static const size_t kMaxCommandHistograms = 50; |
29 | | static const double kLiteralBlockSwitchCost = 28.1; |
30 | | static const double kCommandBlockSwitchCost = 13.5; |
31 | | static const double kDistanceBlockSwitchCost = 14.6; |
32 | | static const size_t kLiteralStrideLength = 70; |
33 | | static const size_t kCommandStrideLength = 40; |
34 | | static const size_t kSymbolsPerLiteralHistogram = 544; |
35 | | static const size_t kSymbolsPerCommandHistogram = 530; |
36 | | static const size_t kSymbolsPerDistanceHistogram = 544; |
37 | | static const size_t kMinLengthForBlockSplitting = 128; |
38 | | static const size_t kIterMulForRefining = 2; |
39 | | static const size_t kMinItersForRefining = 100; |
40 | | |
41 | 0 | static size_t CountLiterals(const Command* cmds, const size_t num_commands) { |
42 | | /* Count how many we have. */ |
43 | 0 | size_t total_length = 0; |
44 | 0 | size_t i; |
45 | 0 | for (i = 0; i < num_commands; ++i) { |
46 | 0 | total_length += cmds[i].insert_len_; |
47 | 0 | } |
48 | 0 | return total_length; |
49 | 0 | } |
50 | | |
51 | | static void CopyLiteralsToByteArray(const Command* cmds, |
52 | | const size_t num_commands, |
53 | | const uint8_t* data, |
54 | | const size_t offset, |
55 | | const size_t mask, |
56 | 0 | uint8_t* literals) { |
57 | 0 | size_t pos = 0; |
58 | 0 | size_t from_pos = offset & mask; |
59 | 0 | size_t i; |
60 | 0 | for (i = 0; i < num_commands; ++i) { |
61 | 0 | size_t insert_len = cmds[i].insert_len_; |
62 | 0 | if (from_pos + insert_len > mask) { |
63 | 0 | size_t head_size = mask + 1 - from_pos; |
64 | 0 | memcpy(literals + pos, data + from_pos, head_size); |
65 | 0 | from_pos = 0; |
66 | 0 | pos += head_size; |
67 | 0 | insert_len -= head_size; |
68 | 0 | } |
69 | 0 | if (insert_len > 0) { |
70 | 0 | memcpy(literals + pos, data + from_pos, insert_len); |
71 | 0 | pos += insert_len; |
72 | 0 | } |
73 | 0 | from_pos = (from_pos + insert_len + CommandCopyLen(&cmds[i])) & mask; |
74 | 0 | } |
75 | 0 | } |
76 | | |
77 | 0 | static BROTLI_INLINE uint32_t MyRand(uint32_t* seed) { |
78 | | /* Initial seed should be 7. In this case, loop length is (1 << 29). */ |
79 | 0 | *seed *= 16807U; |
80 | 0 | return *seed; |
81 | 0 | } |
82 | | |
83 | 0 | static BROTLI_INLINE double BitCost(size_t count) { |
84 | 0 | return count == 0 ? -2.0 : FastLog2(count); |
85 | 0 | } |
86 | | |
87 | 0 | #define HISTOGRAMS_PER_BATCH 64 |
88 | 0 | #define CLUSTERS_PER_BATCH 16 |
89 | | |
90 | 0 | #define FN(X) X ## Literal |
91 | | #define DataType uint8_t |
92 | | /* NOLINTNEXTLINE(build/include) */ |
93 | | #include "./block_splitter_inc.h" |
94 | | #undef DataType |
95 | | #undef FN |
96 | | |
97 | 0 | #define FN(X) X ## Command |
98 | | #define DataType uint16_t |
99 | | /* NOLINTNEXTLINE(build/include) */ |
100 | | #include "./block_splitter_inc.h" |
101 | | #undef FN |
102 | | |
103 | 0 | #define FN(X) X ## Distance |
104 | | /* NOLINTNEXTLINE(build/include) */ |
105 | | #include "./block_splitter_inc.h" |
106 | | #undef DataType |
107 | | #undef FN |
108 | | |
109 | 0 | void BrotliInitBlockSplit(BlockSplit* self) { |
110 | 0 | self->num_types = 0; |
111 | 0 | self->num_blocks = 0; |
112 | 0 | self->types = 0; |
113 | 0 | self->lengths = 0; |
114 | 0 | self->types_alloc_size = 0; |
115 | 0 | self->lengths_alloc_size = 0; |
116 | 0 | } |
117 | | |
118 | 0 | void BrotliDestroyBlockSplit(MemoryManager* m, BlockSplit* self) { |
119 | 0 | BROTLI_FREE(m, self->types); |
120 | 0 | BROTLI_FREE(m, self->lengths); |
121 | 0 | } |
122 | | |
123 | | void BrotliSplitBlock(MemoryManager* m, |
124 | | const Command* cmds, |
125 | | const size_t num_commands, |
126 | | const uint8_t* data, |
127 | | const size_t pos, |
128 | | const size_t mask, |
129 | | const BrotliEncoderParams* params, |
130 | | BlockSplit* literal_split, |
131 | | BlockSplit* insert_and_copy_split, |
132 | 0 | BlockSplit* dist_split) { |
133 | 0 | { |
134 | 0 | size_t literals_count = CountLiterals(cmds, num_commands); |
135 | 0 | uint8_t* literals = BROTLI_ALLOC(m, uint8_t, literals_count); |
136 | 0 | if (BROTLI_IS_OOM(m)) return; |
137 | | /* Create a continuous array of literals. */ |
138 | 0 | CopyLiteralsToByteArray(cmds, num_commands, data, pos, mask, literals); |
139 | | /* Create the block split on the array of literals. |
140 | | Literal histograms have alphabet size 256. */ |
141 | 0 | SplitByteVectorLiteral( |
142 | 0 | m, literals, literals_count, |
143 | 0 | kSymbolsPerLiteralHistogram, kMaxLiteralHistograms, |
144 | 0 | kLiteralStrideLength, kLiteralBlockSwitchCost, params, |
145 | 0 | literal_split); |
146 | 0 | if (BROTLI_IS_OOM(m)) return; |
147 | 0 | BROTLI_FREE(m, literals); |
148 | 0 | } |
149 | | |
150 | 0 | { |
151 | | /* Compute prefix codes for commands. */ |
152 | 0 | uint16_t* insert_and_copy_codes = BROTLI_ALLOC(m, uint16_t, num_commands); |
153 | 0 | size_t i; |
154 | 0 | if (BROTLI_IS_OOM(m)) return; |
155 | 0 | for (i = 0; i < num_commands; ++i) { |
156 | 0 | insert_and_copy_codes[i] = cmds[i].cmd_prefix_; |
157 | 0 | } |
158 | | /* Create the block split on the array of command prefixes. */ |
159 | 0 | SplitByteVectorCommand( |
160 | 0 | m, insert_and_copy_codes, num_commands, |
161 | 0 | kSymbolsPerCommandHistogram, kMaxCommandHistograms, |
162 | 0 | kCommandStrideLength, kCommandBlockSwitchCost, params, |
163 | 0 | insert_and_copy_split); |
164 | 0 | if (BROTLI_IS_OOM(m)) return; |
165 | | /* TODO: reuse for distances? */ |
166 | 0 | BROTLI_FREE(m, insert_and_copy_codes); |
167 | 0 | } |
168 | | |
169 | 0 | { |
170 | | /* Create a continuous array of distance prefixes. */ |
171 | 0 | uint16_t* distance_prefixes = BROTLI_ALLOC(m, uint16_t, num_commands); |
172 | 0 | size_t j = 0; |
173 | 0 | size_t i; |
174 | 0 | if (BROTLI_IS_OOM(m)) return; |
175 | 0 | for (i = 0; i < num_commands; ++i) { |
176 | 0 | const Command* cmd = &cmds[i]; |
177 | 0 | if (CommandCopyLen(cmd) && cmd->cmd_prefix_ >= 128) { |
178 | 0 | distance_prefixes[j++] = cmd->dist_prefix_; |
179 | 0 | } |
180 | 0 | } |
181 | | /* Create the block split on the array of distance prefixes. */ |
182 | 0 | SplitByteVectorDistance( |
183 | 0 | m, distance_prefixes, j, |
184 | 0 | kSymbolsPerDistanceHistogram, kMaxCommandHistograms, |
185 | 0 | kCommandStrideLength, kDistanceBlockSwitchCost, params, |
186 | 0 | dist_split); |
187 | 0 | if (BROTLI_IS_OOM(m)) return; |
188 | 0 | BROTLI_FREE(m, distance_prefixes); |
189 | 0 | } |
190 | 0 | } |
191 | | |
192 | | |
193 | | #if defined(__cplusplus) || defined(c_plusplus) |
194 | | } /* extern "C" */ |
195 | | #endif |