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