Bug Summary

File:out/../deps/brotli/c/enc/./block_splitter_inc.h
Warning:line 17, column 32
Division by zero

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name block_splitter.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=all -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/home/maurizio/node-v18.6.0/out -resource-dir /usr/local/lib/clang/16.0.0 -D V8_DEPRECATION_WARNINGS -D V8_IMMINENT_DEPRECATION_WARNINGS -D _GLIBCXX_USE_CXX11_ABI=1 -D NODE_OPENSSL_CONF_NAME=nodejs_conf -D NODE_OPENSSL_HAS_QUIC -D __STDC_FORMAT_MACROS -D OPENSSL_NO_PINSHARED -D OPENSSL_THREADS -D OS_LINUX -I ../deps/brotli/c/include -internal-isystem /usr/local/lib/clang/16.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../x86_64-redhat-linux/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O3 -Wno-unused-parameter -fdebug-compilation-dir=/home/maurizio/node-v18.6.0/out -ferror-limit 19 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-08-22-142216-507842-1 -x c ../deps/brotli/c/enc/block_splitter.c

../deps/brotli/c/enc/block_splitter.c

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

../deps/brotli/c/enc/./block_splitter_inc.h

1/* NOLINT(build/header_guard) */
2/* Copyright 2013 Google Inc. All Rights Reserved.
3
4 Distributed under MIT license.
5 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
6*/
7
8/* template parameters: FN, DataType */
9
10#define HistogramType FN(Histogram)
11
12static void FN(InitialEntropyCodes)(const DataType* data, size_t length,
13 size_t stride,
14 size_t num_histograms,
15 HistogramType* histograms) {
16 uint32_t seed = 7;
17 size_t block_length = length / num_histograms;
16
←
Division by zero
18 size_t i;
19 FN(ClearHistograms)(histograms, num_histograms);
20 for (i = 0; i < num_histograms; ++i) {
21 size_t pos = length * i / num_histograms;
22 if (i != 0) {
23 pos += MyRand(&seed) % block_length;
24 }
25 if (pos + stride >= length) {
26 pos = length - stride - 1;
27 }
28 FN(HistogramAddVector)(&histograms[i], data + pos, stride);
29 }
30}
31
32static void FN(RandomSample)(uint32_t* seed,
33 const DataType* data,
34 size_t length,
35 size_t stride,
36 HistogramType* sample) {
37 size_t pos = 0;
38 if (stride >= length) {
39 stride = length;
40 } else {
41 pos = MyRand(seed) % (length - stride + 1);
42 }
43 FN(HistogramAddVector)(sample, data + pos, stride);
44}
45
46static void FN(RefineEntropyCodes)(const DataType* data, size_t length,
47 size_t stride,
48 size_t num_histograms,
49 HistogramType* histograms) {
50 size_t iters =
51 kIterMulForRefining * length / stride + kMinItersForRefining;
52 uint32_t seed = 7;
53 size_t iter;
54 iters = ((iters + num_histograms - 1) / num_histograms) * num_histograms;
55 for (iter = 0; iter < iters; ++iter) {
56 HistogramType sample;
57 FN(HistogramClear)(&sample);
58 FN(RandomSample)(&seed, data, length, stride, &sample);
59 FN(HistogramAddHistogram)(&histograms[iter % num_histograms], &sample);
60 }
61}
62
63/* Assigns a block id from the range [0, num_histograms) to each data element
64 in data[0..length) and fills in block_id[0..length) with the assigned values.
65 Returns the number of blocks, i.e. one plus the number of block switches. */
66static size_t FN(FindBlocks)(const DataType* data, const size_t length,
67 const double block_switch_bitcost,
68 const size_t num_histograms,
69 const HistogramType* histograms,
70 double* insert_cost,
71 double* cost,
72 uint8_t* switch_signal,
73 uint8_t* block_id) {
74 const size_t data_size = FN(HistogramDataSize)();
75 const size_t bitmaplen = (num_histograms + 7) >> 3;
76 size_t num_blocks = 1;
77 size_t i;
78 size_t j;
79 BROTLI_DCHECK(num_histograms <= 256);
80 if (num_histograms <= 1) {
81 for (i = 0; i < length; ++i) {
82 block_id[i] = 0;
83 }
84 return 1;
85 }
86 memset(insert_cost, 0, sizeof(insert_cost[0]) * data_size * num_histograms);
87 for (i = 0; i < num_histograms; ++i) {
88 insert_cost[i] = FastLog2((uint32_t)histograms[i].total_count_);
89 }
90 for (i = data_size; i != 0;) {
91 --i;
92 for (j = 0; j < num_histograms; ++j) {
93 insert_cost[i * num_histograms + j] =
94 insert_cost[j] - BitCost(histograms[j].data_[i]);
95 }
96 }
97 memset(cost, 0, sizeof(cost[0]) * num_histograms);
98 memset(switch_signal, 0, sizeof(switch_signal[0]) * length * bitmaplen);
99 /* After each iteration of this loop, cost[k] will contain the difference
100 between the minimum cost of arriving at the current byte position using
101 entropy code k, and the minimum cost of arriving at the current byte
102 position. This difference is capped at the block switch cost, and if it
103 reaches block switch cost, it means that when we trace back from the last
104 position, we need to switch here. */
105 for (i = 0; i < length; ++i) {
106 const size_t byte_ix = i;
107 size_t ix = byte_ix * bitmaplen;
108 size_t insert_cost_ix = data[byte_ix] * num_histograms;
109 double min_cost = 1e99;
110 double block_switch_cost = block_switch_bitcost;
111 size_t k;
112 for (k = 0; k < num_histograms; ++k) {
113 /* We are coding the symbol in data[byte_ix] with entropy code k. */
114 cost[k] += insert_cost[insert_cost_ix + k];
115 if (cost[k] < min_cost) {
116 min_cost = cost[k];
117 block_id[byte_ix] = (uint8_t)k;
118 }
119 }
120 /* More blocks for the beginning. */
121 if (byte_ix < 2000) {
122 block_switch_cost *= 0.77 + 0.07 * (double)byte_ix / 2000;
123 }
124 for (k = 0; k < num_histograms; ++k) {
125 cost[k] -= min_cost;
126 if (cost[k] >= block_switch_cost) {
127 const uint8_t mask = (uint8_t)(1u << (k & 7));
128 cost[k] = block_switch_cost;
129 BROTLI_DCHECK((k >> 3) < bitmaplen);
130 switch_signal[ix + (k >> 3)] |= mask;
131 }
132 }
133 }
134 { /* Trace back from the last position and switch at the marked places. */
135 size_t byte_ix = length - 1;
136 size_t ix = byte_ix * bitmaplen;
137 uint8_t cur_id = block_id[byte_ix];
138 while (byte_ix > 0) {
139 const uint8_t mask = (uint8_t)(1u << (cur_id & 7));
140 BROTLI_DCHECK(((size_t)cur_id >> 3) < bitmaplen);
141 --byte_ix;
142 ix -= bitmaplen;
143 if (switch_signal[ix + (cur_id >> 3)] & mask) {
144 if (cur_id != block_id[byte_ix]) {
145 cur_id = block_id[byte_ix];
146 ++num_blocks;
147 }
148 }
149 block_id[byte_ix] = cur_id;
150 }
151 }
152 return num_blocks;
153}
154
155static size_t FN(RemapBlockIds)(uint8_t* block_ids, const size_t length,
156 uint16_t* new_id, const size_t num_histograms) {
157 static const uint16_t kInvalidId = 256;
158 uint16_t next_id = 0;
159 size_t i;
160 for (i = 0; i < num_histograms; ++i) {
161 new_id[i] = kInvalidId;
162 }
163 for (i = 0; i < length; ++i) {
164 BROTLI_DCHECK(block_ids[i] < num_histograms);
165 if (new_id[block_ids[i]] == kInvalidId) {
166 new_id[block_ids[i]] = next_id++;
167 }
168 }
169 for (i = 0; i < length; ++i) {
170 block_ids[i] = (uint8_t)new_id[block_ids[i]];
171 BROTLI_DCHECK(block_ids[i] < num_histograms);
172 }
173 BROTLI_DCHECK(next_id <= num_histograms);
174 return next_id;
175}
176
177static void FN(BuildBlockHistograms)(const DataType* data, const size_t length,
178 const uint8_t* block_ids,
179 const size_t num_histograms,
180 HistogramType* histograms) {
181 size_t i;
182 FN(ClearHistograms)(histograms, num_histograms);
183 for (i = 0; i < length; ++i) {
184 FN(HistogramAdd)(&histograms[block_ids[i]], data[i]);
185 }
186}
187
188static void FN(ClusterBlocks)(MemoryManager* m,
189 const DataType* data, const size_t length,
190 const size_t num_blocks,
191 uint8_t* block_ids,
192 BlockSplit* split) {
193 uint32_t* histogram_symbols = BROTLI_ALLOC(m, uint32_t, num_blocks)((num_blocks) > 0 ? ((uint32_t*)BrotliAllocate((m), (num_blocks
) * sizeof(uint32_t))) : ((void*)0));
194 uint32_t* block_lengths = BROTLI_ALLOC(m, uint32_t, num_blocks)((num_blocks) > 0 ? ((uint32_t*)BrotliAllocate((m), (num_blocks
) * sizeof(uint32_t))) : ((void*)0));
195 const size_t expected_num_clusters = CLUSTERS_PER_BATCH16 *
196 (num_blocks + HISTOGRAMS_PER_BATCH64 - 1) / HISTOGRAMS_PER_BATCH64;
197 size_t all_histograms_size = 0;
198 size_t all_histograms_capacity = expected_num_clusters;
199 HistogramType* all_histograms =
200 BROTLI_ALLOC(m, HistogramType, all_histograms_capacity)((all_histograms_capacity) > 0 ? ((HistogramType*)BrotliAllocate
((m), (all_histograms_capacity) * sizeof(HistogramType))) : (
(void*)0));
201 size_t cluster_size_size = 0;
202 size_t cluster_size_capacity = expected_num_clusters;
203 uint32_t* cluster_size = BROTLI_ALLOC(m, uint32_t, cluster_size_capacity)((cluster_size_capacity) > 0 ? ((uint32_t*)BrotliAllocate(
(m), (cluster_size_capacity) * sizeof(uint32_t))) : ((void*)0
));
204 size_t num_clusters = 0;
205 HistogramType* histograms = BROTLI_ALLOC(m, HistogramType,(((brotli_min_size_t((num_blocks), (64)))) > 0 ? ((HistogramType
*)BrotliAllocate((m), ((brotli_min_size_t((num_blocks), (64))
)) * sizeof(HistogramType))) : ((void*)0))
206 BROTLI_MIN(size_t, num_blocks, HISTOGRAMS_PER_BATCH))(((brotli_min_size_t((num_blocks), (64)))) > 0 ? ((HistogramType
*)BrotliAllocate((m), ((brotli_min_size_t((num_blocks), (64))
)) * sizeof(HistogramType))) : ((void*)0));
207 size_t max_num_pairs =
208 HISTOGRAMS_PER_BATCH64 * HISTOGRAMS_PER_BATCH64 / 2;
209 size_t pairs_capacity = max_num_pairs + 1;
210 HistogramPair* pairs = BROTLI_ALLOC(m, HistogramPair, pairs_capacity)((pairs_capacity) > 0 ? ((HistogramPair*)BrotliAllocate((m
), (pairs_capacity) * sizeof(HistogramPair))) : ((void*)0));
211 size_t pos = 0;
212 uint32_t* clusters;
213 size_t num_final_clusters;
214 static const uint32_t kInvalidIndex = BROTLI_UINT32_MAX(~((uint32_t)0));
215 uint32_t* new_index;
216 size_t i;
217 uint32_t sizes[HISTOGRAMS_PER_BATCH64] = { 0 };
218 uint32_t new_clusters[HISTOGRAMS_PER_BATCH64] = { 0 };
219 uint32_t symbols[HISTOGRAMS_PER_BATCH64] = { 0 };
220 uint32_t remap[HISTOGRAMS_PER_BATCH64] = { 0 };
221
222 if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(histogram_symbols)(!!0) ||
223 BROTLI_IS_NULL(block_lengths)(!!0) || BROTLI_IS_NULL(all_histograms)(!!0) ||
224 BROTLI_IS_NULL(cluster_size)(!!0) || BROTLI_IS_NULL(histograms)(!!0) ||
225 BROTLI_IS_NULL(pairs)(!!0)) {
226 return;
227 }
228
229 memset(block_lengths, 0, num_blocks * sizeof(uint32_t));
230
231 {
232 size_t block_idx = 0;
233 for (i = 0; i < length; ++i) {
234 BROTLI_DCHECK(block_idx < num_blocks);
235 ++block_lengths[block_idx];
236 if (i + 1 == length || block_ids[i] != block_ids[i + 1]) {
237 ++block_idx;
238 }
239 }
240 BROTLI_DCHECK(block_idx == num_blocks);
241 }
242
243 for (i = 0; i < num_blocks; i += HISTOGRAMS_PER_BATCH64) {
244 const size_t num_to_combine =
245 BROTLI_MIN(size_t, num_blocks - i, HISTOGRAMS_PER_BATCH)(brotli_min_size_t((num_blocks - i), (64)));
246 size_t num_new_clusters;
247 size_t j;
248 for (j = 0; j < num_to_combine; ++j) {
249 size_t k;
250 FN(HistogramClear)(&histograms[j]);
251 for (k = 0; k < block_lengths[i + j]; ++k) {
252 FN(HistogramAdd)(&histograms[j], data[pos++]);
253 }
254 histograms[j].bit_cost_ = FN(BrotliPopulationCost)(&histograms[j]);
255 new_clusters[j] = (uint32_t)j;
256 symbols[j] = (uint32_t)j;
257 sizes[j] = 1;
258 }
259 num_new_clusters = FN(BrotliHistogramCombine)(
260 histograms, sizes, symbols, new_clusters, pairs, num_to_combine,
261 num_to_combine, HISTOGRAMS_PER_BATCH64, max_num_pairs);
262 BROTLI_ENSURE_CAPACITY(m, HistogramType, all_histograms,{ if (all_histograms_capacity < (all_histograms_size + num_new_clusters
)) { size_t _new_size = (all_histograms_capacity == 0) ? (all_histograms_size
+ num_new_clusters) : all_histograms_capacity; HistogramType
* new_array; while (_new_size < (all_histograms_size + num_new_clusters
)) _new_size *= 2; new_array = ((_new_size) > 0 ? ((HistogramType
*)BrotliAllocate(((m)), (_new_size) * sizeof(HistogramType)))
: ((void*)0)); if (!(!!0) && !(!!0) && all_histograms_capacity
!= 0) memcpy(new_array, all_histograms, all_histograms_capacity
* sizeof(HistogramType)); { BrotliFree(((m)), (all_histograms
)); all_histograms = ((void*)0); }; all_histograms = new_array
; all_histograms_capacity = _new_size; } }
263 all_histograms_capacity, all_histograms_size + num_new_clusters){ if (all_histograms_capacity < (all_histograms_size + num_new_clusters
)) { size_t _new_size = (all_histograms_capacity == 0) ? (all_histograms_size
+ num_new_clusters) : all_histograms_capacity; HistogramType
* new_array; while (_new_size < (all_histograms_size + num_new_clusters
)) _new_size *= 2; new_array = ((_new_size) > 0 ? ((HistogramType
*)BrotliAllocate(((m)), (_new_size) * sizeof(HistogramType)))
: ((void*)0)); if (!(!!0) && !(!!0) && all_histograms_capacity
!= 0) memcpy(new_array, all_histograms, all_histograms_capacity
* sizeof(HistogramType)); { BrotliFree(((m)), (all_histograms
)); all_histograms = ((void*)0); }; all_histograms = new_array
; all_histograms_capacity = _new_size; } };
264 BROTLI_ENSURE_CAPACITY(m, uint32_t, cluster_size,{ if (cluster_size_capacity < (cluster_size_size + num_new_clusters
)) { size_t _new_size = (cluster_size_capacity == 0) ? (cluster_size_size
+ num_new_clusters) : cluster_size_capacity; uint32_t* new_array
; while (_new_size < (cluster_size_size + num_new_clusters
)) _new_size *= 2; new_array = ((_new_size) > 0 ? ((uint32_t
*)BrotliAllocate(((m)), (_new_size) * sizeof(uint32_t))) : ((
void*)0)); if (!(!!0) && !(!!0) && cluster_size_capacity
!= 0) memcpy(new_array, cluster_size, cluster_size_capacity *
sizeof(uint32_t)); { BrotliFree(((m)), (cluster_size)); cluster_size
= ((void*)0); }; cluster_size = new_array; cluster_size_capacity
= _new_size; } }
265 cluster_size_capacity, cluster_size_size + num_new_clusters){ if (cluster_size_capacity < (cluster_size_size + num_new_clusters
)) { size_t _new_size = (cluster_size_capacity == 0) ? (cluster_size_size
+ num_new_clusters) : cluster_size_capacity; uint32_t* new_array
; while (_new_size < (cluster_size_size + num_new_clusters
)) _new_size *= 2; new_array = ((_new_size) > 0 ? ((uint32_t
*)BrotliAllocate(((m)), (_new_size) * sizeof(uint32_t))) : ((
void*)0)); if (!(!!0) && !(!!0) && cluster_size_capacity
!= 0) memcpy(new_array, cluster_size, cluster_size_capacity *
sizeof(uint32_t)); { BrotliFree(((m)), (cluster_size)); cluster_size
= ((void*)0); }; cluster_size = new_array; cluster_size_capacity
= _new_size; } };
266 if (BROTLI_IS_OOM(m)(!!0)) return;
267 for (j = 0; j < num_new_clusters; ++j) {
268 all_histograms[all_histograms_size++] = histograms[new_clusters[j]];
269 cluster_size[cluster_size_size++] = sizes[new_clusters[j]];
270 remap[new_clusters[j]] = (uint32_t)j;
271 }
272 for (j = 0; j < num_to_combine; ++j) {
273 histogram_symbols[i + j] = (uint32_t)num_clusters + remap[symbols[j]];
274 }
275 num_clusters += num_new_clusters;
276 BROTLI_DCHECK(num_clusters == cluster_size_size);
277 BROTLI_DCHECK(num_clusters == all_histograms_size);
278 }
279 BROTLI_FREE(m, histograms){ BrotliFree((m), (histograms)); histograms = ((void*)0); };
280
281 max_num_pairs =
282 BROTLI_MIN(size_t, 64 * num_clusters, (num_clusters / 2) * num_clusters)(brotli_min_size_t((64 * num_clusters), ((num_clusters / 2) *
num_clusters)));
283 if (pairs_capacity < max_num_pairs + 1) {
284 BROTLI_FREE(m, pairs){ BrotliFree((m), (pairs)); pairs = ((void*)0); };
285 pairs = BROTLI_ALLOC(m, HistogramPair, max_num_pairs + 1)((max_num_pairs + 1) > 0 ? ((HistogramPair*)BrotliAllocate
((m), (max_num_pairs + 1) * sizeof(HistogramPair))) : ((void*
)0));
286 if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(pairs)(!!0)) return;
287 }
288
289 clusters = BROTLI_ALLOC(m, uint32_t, num_clusters)((num_clusters) > 0 ? ((uint32_t*)BrotliAllocate((m), (num_clusters
) * sizeof(uint32_t))) : ((void*)0));
290 if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(clusters)(!!0)) return;
291 for (i = 0; i < num_clusters; ++i) {
292 clusters[i] = (uint32_t)i;
293 }
294 num_final_clusters = FN(BrotliHistogramCombine)(
295 all_histograms, cluster_size, histogram_symbols, clusters, pairs,
296 num_clusters, num_blocks, BROTLI_MAX_NUMBER_OF_BLOCK_TYPES256,
297 max_num_pairs);
298 BROTLI_FREE(m, pairs){ BrotliFree((m), (pairs)); pairs = ((void*)0); };
299 BROTLI_FREE(m, cluster_size){ BrotliFree((m), (cluster_size)); cluster_size = ((void*)0);
};
300
301 new_index = BROTLI_ALLOC(m, uint32_t, num_clusters)((num_clusters) > 0 ? ((uint32_t*)BrotliAllocate((m), (num_clusters
) * sizeof(uint32_t))) : ((void*)0));
302 if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(new_index)(!!0)) return;
303 for (i = 0; i < num_clusters; ++i) new_index[i] = kInvalidIndex;
304 pos = 0;
305 {
306 uint32_t next_index = 0;
307 for (i = 0; i < num_blocks; ++i) {
308 HistogramType histo;
309 size_t j;
310 uint32_t best_out;
311 double best_bits;
312 FN(HistogramClear)(&histo);
313 for (j = 0; j < block_lengths[i]; ++j) {
314 FN(HistogramAdd)(&histo, data[pos++]);
315 }
316 best_out = (i == 0) ? histogram_symbols[0] : histogram_symbols[i - 1];
317 best_bits =
318 FN(BrotliHistogramBitCostDistance)(&histo, &all_histograms[best_out]);
319 for (j = 0; j < num_final_clusters; ++j) {
320 const double cur_bits = FN(BrotliHistogramBitCostDistance)(
321 &histo, &all_histograms[clusters[j]]);
322 if (cur_bits < best_bits) {
323 best_bits = cur_bits;
324 best_out = clusters[j];
325 }
326 }
327 histogram_symbols[i] = best_out;
328 if (new_index[best_out] == kInvalidIndex) {
329 new_index[best_out] = next_index++;
330 }
331 }
332 }
333 BROTLI_FREE(m, clusters){ BrotliFree((m), (clusters)); clusters = ((void*)0); };
334 BROTLI_FREE(m, all_histograms){ BrotliFree((m), (all_histograms)); all_histograms = ((void*
)0); };
335 BROTLI_ENSURE_CAPACITY({ if (split->types_alloc_size < (num_blocks)) { size_t _new_size
= (split->types_alloc_size == 0) ? (num_blocks) : split->
types_alloc_size; uint8_t* new_array; while (_new_size < (
num_blocks)) _new_size *= 2; new_array = ((_new_size) > 0 ?
((uint8_t*)BrotliAllocate(((m)), (_new_size) * sizeof(uint8_t
))) : ((void*)0)); if (!(!!0) && !(!!0) && split
->types_alloc_size != 0) memcpy(new_array, split->types
, split->types_alloc_size * sizeof(uint8_t)); { BrotliFree
(((m)), (split->types)); split->types = ((void*)0); }; split
->types = new_array; split->types_alloc_size = _new_size
; } }
336 m, uint8_t, split->types, split->types_alloc_size, num_blocks){ if (split->types_alloc_size < (num_blocks)) { size_t _new_size
= (split->types_alloc_size == 0) ? (num_blocks) : split->
types_alloc_size; uint8_t* new_array; while (_new_size < (
num_blocks)) _new_size *= 2; new_array = ((_new_size) > 0 ?
((uint8_t*)BrotliAllocate(((m)), (_new_size) * sizeof(uint8_t
))) : ((void*)0)); if (!(!!0) && !(!!0) && split
->types_alloc_size != 0) memcpy(new_array, split->types
, split->types_alloc_size * sizeof(uint8_t)); { BrotliFree
(((m)), (split->types)); split->types = ((void*)0); }; split
->types = new_array; split->types_alloc_size = _new_size
; } };
337 BROTLI_ENSURE_CAPACITY({ if (split->lengths_alloc_size < (num_blocks)) { size_t
_new_size = (split->lengths_alloc_size == 0) ? (num_blocks
) : split->lengths_alloc_size; uint32_t* new_array; while (
_new_size < (num_blocks)) _new_size *= 2; new_array = ((_new_size
) > 0 ? ((uint32_t*)BrotliAllocate(((m)), (_new_size) * sizeof
(uint32_t))) : ((void*)0)); if (!(!!0) && !(!!0) &&
split->lengths_alloc_size != 0) memcpy(new_array, split->
lengths, split->lengths_alloc_size * sizeof(uint32_t)); { BrotliFree
(((m)), (split->lengths)); split->lengths = ((void*)0);
}; split->lengths = new_array; split->lengths_alloc_size
= _new_size; } }
338 m, uint32_t, split->lengths, split->lengths_alloc_size, num_blocks){ if (split->lengths_alloc_size < (num_blocks)) { size_t
_new_size = (split->lengths_alloc_size == 0) ? (num_blocks
) : split->lengths_alloc_size; uint32_t* new_array; while (
_new_size < (num_blocks)) _new_size *= 2; new_array = ((_new_size
) > 0 ? ((uint32_t*)BrotliAllocate(((m)), (_new_size) * sizeof
(uint32_t))) : ((void*)0)); if (!(!!0) && !(!!0) &&
split->lengths_alloc_size != 0) memcpy(new_array, split->
lengths, split->lengths_alloc_size * sizeof(uint32_t)); { BrotliFree
(((m)), (split->lengths)); split->lengths = ((void*)0);
}; split->lengths = new_array; split->lengths_alloc_size
= _new_size; } };
339 if (BROTLI_IS_OOM(m)(!!0)) return;
340 {
341 uint32_t cur_length = 0;
342 size_t block_idx = 0;
343 uint8_t max_type = 0;
344 for (i = 0; i < num_blocks; ++i) {
345 cur_length += block_lengths[i];
346 if (i + 1 == num_blocks ||
347 histogram_symbols[i] != histogram_symbols[i + 1]) {
348 const uint8_t id = (uint8_t)new_index[histogram_symbols[i]];
349 split->types[block_idx] = id;
350 split->lengths[block_idx] = cur_length;
351 max_type = BROTLI_MAX(uint8_t, max_type, id)(brotli_max_uint8_t((max_type), (id)));
352 cur_length = 0;
353 ++block_idx;
354 }
355 }
356 split->num_blocks = block_idx;
357 split->num_types = (size_t)max_type + 1;
358 }
359 BROTLI_FREE(m, new_index){ BrotliFree((m), (new_index)); new_index = ((void*)0); };
360 BROTLI_FREE(m, block_lengths){ BrotliFree((m), (block_lengths)); block_lengths = ((void*)0
); };
361 BROTLI_FREE(m, histogram_symbols){ BrotliFree((m), (histogram_symbols)); histogram_symbols = (
(void*)0); };
362}
363
364static void FN(SplitByteVector)(MemoryManager* m,
365 const DataType* data, const size_t length,
366 const size_t literals_per_histogram,
367 const size_t max_histograms,
368 const size_t sampling_stride_length,
369 const double block_switch_cost,
370 const BrotliEncoderParams* params,
371 BlockSplit* split) {
372 const size_t data_size = FN(HistogramDataSize)();
373 size_t num_histograms = length / literals_per_histogram + 1;
5
←
'num_histograms' initialized here
→
374 HistogramType* histograms;
375 if (num_histograms > max_histograms) {
6
←
Assuming 'num_histograms' is <= 'max_histograms'
→
7
←
Taking false branch
→
376 num_histograms = max_histograms;
377 }
378 if (length
7.1
'length' is not equal to 0
7.1
'length' is not equal to 0
 == 0) {
8
←
Taking false branch
→
379 split->num_types = 1;
380 return;
381 } else if (length < kMinLengthForBlockSplitting) {
9
←
Assuming 'length' is >= 'kMinLengthForBlockSplitting'
→
382 BROTLI_ENSURE_CAPACITY(m, uint8_t,{ if (split->types_alloc_size < (split->num_blocks +
1)) { size_t _new_size = (split->types_alloc_size == 0) ?
(split->num_blocks + 1) : split->types_alloc_size; uint8_t
* new_array; while (_new_size < (split->num_blocks + 1)
) _new_size *= 2; new_array = ((_new_size) > 0 ? ((uint8_t
*)BrotliAllocate(((m)), (_new_size) * sizeof(uint8_t))) : ((void
*)0)); if (!(!!0) && !(!!0) && split->types_alloc_size
!= 0) memcpy(new_array, split->types, split->types_alloc_size
* sizeof(uint8_t)); { BrotliFree(((m)), (split->types)); split
->types = ((void*)0); }; split->types = new_array; split
->types_alloc_size = _new_size; } }
383 split->types, split->types_alloc_size, split->num_blocks + 1){ if (split->types_alloc_size < (split->num_blocks +
1)) { size_t _new_size = (split->types_alloc_size == 0) ?
(split->num_blocks + 1) : split->types_alloc_size; uint8_t
* new_array; while (_new_size < (split->num_blocks + 1)
) _new_size *= 2; new_array = ((_new_size) > 0 ? ((uint8_t
*)BrotliAllocate(((m)), (_new_size) * sizeof(uint8_t))) : ((void
*)0)); if (!(!!0) && !(!!0) && split->types_alloc_size
!= 0) memcpy(new_array, split->types, split->types_alloc_size
* sizeof(uint8_t)); { BrotliFree(((m)), (split->types)); split
->types = ((void*)0); }; split->types = new_array; split
->types_alloc_size = _new_size; } };
384 BROTLI_ENSURE_CAPACITY(m, uint32_t,{ if (split->lengths_alloc_size < (split->num_blocks
+ 1)) { size_t _new_size = (split->lengths_alloc_size == 0
) ? (split->num_blocks + 1) : split->lengths_alloc_size
; uint32_t* new_array; while (_new_size < (split->num_blocks
+ 1)) _new_size *= 2; new_array = ((_new_size) > 0 ? ((uint32_t
*)BrotliAllocate(((m)), (_new_size) * sizeof(uint32_t))) : ((
void*)0)); if (!(!!0) && !(!!0) && split->
lengths_alloc_size != 0) memcpy(new_array, split->lengths,
split->lengths_alloc_size * sizeof(uint32_t)); { BrotliFree
(((m)), (split->lengths)); split->lengths = ((void*)0);
}; split->lengths = new_array; split->lengths_alloc_size
= _new_size; } }
385 split->lengths, split->lengths_alloc_size, split->num_blocks + 1){ if (split->lengths_alloc_size < (split->num_blocks
+ 1)) { size_t _new_size = (split->lengths_alloc_size == 0
) ? (split->num_blocks + 1) : split->lengths_alloc_size
; uint32_t* new_array; while (_new_size < (split->num_blocks
+ 1)) _new_size *= 2; new_array = ((_new_size) > 0 ? ((uint32_t
*)BrotliAllocate(((m)), (_new_size) * sizeof(uint32_t))) : ((
void*)0)); if (!(!!0) && !(!!0) && split->
lengths_alloc_size != 0) memcpy(new_array, split->lengths,
split->lengths_alloc_size * sizeof(uint32_t)); { BrotliFree
(((m)), (split->lengths)); split->lengths = ((void*)0);
}; split->lengths = new_array; split->lengths_alloc_size
= _new_size; } };
386 if (BROTLI_IS_OOM(m)(!!0)) return;
387 split->num_types = 1;
388 split->types[split->num_blocks] = 0;
389 split->lengths[split->num_blocks] = (uint32_t)length;
390 split->num_blocks++;
391 return;
392 }
393 histograms = BROTLI_ALLOC(m, HistogramType, num_histograms)((num_histograms) > 0 ? ((HistogramType*)BrotliAllocate((m
), (num_histograms) * sizeof(HistogramType))) : ((void*)0));
10
←
Taking false branch
→
11
←
Assuming 'num_histograms' is <= 0
→
12
←
'?' condition is false
→
394 if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(histograms)(!!0)) return;
13
←
Taking false branch
→
395 /* Find good entropy codes. */
396 FN(InitialEntropyCodes)(data, length,
15
←
Calling 'InitialEntropyCodesLiteral'
→
397 sampling_stride_length,
398 num_histograms, histograms);
14
←
Passing value via 4th parameter 'num_histograms'
→
399 FN(RefineEntropyCodes)(data, length,
400 sampling_stride_length,
401 num_histograms, histograms);
402 {
403 /* Find a good path through literals with the good entropy codes. */
404 uint8_t* block_ids = BROTLI_ALLOC(m, uint8_t, length)((length) > 0 ? ((uint8_t*)BrotliAllocate((m), (length) * sizeof
(uint8_t))) : ((void*)0));
405 size_t num_blocks = 0;
406 const size_t bitmaplen = (num_histograms + 7) >> 3;
407 double* insert_cost = BROTLI_ALLOC(m, double, data_size * num_histograms)((data_size * num_histograms) > 0 ? ((double*)BrotliAllocate
((m), (data_size * num_histograms) * sizeof(double))) : ((void
*)0));
408 double* cost = BROTLI_ALLOC(m, double, num_histograms)((num_histograms) > 0 ? ((double*)BrotliAllocate((m), (num_histograms
) * sizeof(double))) : ((void*)0));
409 uint8_t* switch_signal = BROTLI_ALLOC(m, uint8_t, length * bitmaplen)((length * bitmaplen) > 0 ? ((uint8_t*)BrotliAllocate((m),
(length * bitmaplen) * sizeof(uint8_t))) : ((void*)0));
410 uint16_t* new_id = BROTLI_ALLOC(m, uint16_t, num_histograms)((num_histograms) > 0 ? ((uint16_t*)BrotliAllocate((m), (num_histograms
) * sizeof(uint16_t))) : ((void*)0));
411 const size_t iters = params->quality < HQ_ZOPFLIFICATION_QUALITY11 ? 3 : 10;
412 size_t i;
413 if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(block_ids)(!!0) ||
414 BROTLI_IS_NULL(insert_cost)(!!0) || BROTLI_IS_NULL(cost)(!!0) ||
415 BROTLI_IS_NULL(switch_signal)(!!0) || BROTLI_IS_NULL(new_id)(!!0)) {
416 return;
417 }
418 for (i = 0; i < iters; ++i) {
419 num_blocks = FN(FindBlocks)(data, length,
420 block_switch_cost,
421 num_histograms, histograms,
422 insert_cost, cost, switch_signal,
423 block_ids);
424 num_histograms = FN(RemapBlockIds)(block_ids, length,
425 new_id, num_histograms);
426 FN(BuildBlockHistograms)(data, length, block_ids,
427 num_histograms, histograms);
428 }
429 BROTLI_FREE(m, insert_cost){ BrotliFree((m), (insert_cost)); insert_cost = ((void*)0); };
430 BROTLI_FREE(m, cost){ BrotliFree((m), (cost)); cost = ((void*)0); };
431 BROTLI_FREE(m, switch_signal){ BrotliFree((m), (switch_signal)); switch_signal = ((void*)0
); };
432 BROTLI_FREE(m, new_id){ BrotliFree((m), (new_id)); new_id = ((void*)0); };
433 BROTLI_FREE(m, histograms){ BrotliFree((m), (histograms)); histograms = ((void*)0); };
434 FN(ClusterBlocks)(m, data, length, num_blocks, block_ids, split);
435 if (BROTLI_IS_OOM(m)(!!0)) return;
436 BROTLI_FREE(m, block_ids){ BrotliFree((m), (block_ids)); block_ids = ((void*)0); };
437 }
438}
439
440#undef HistogramType