block_splitter_inc.h (18879B)
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 12 static 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; 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 32 static 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 46 static void FN(RefineEntropyCodes)(const DataType* data, size_t length, 47 size_t stride, 48 size_t num_histograms, 49 HistogramType* histograms, 50 HistogramType* tmp) { 51 size_t iters = 52 kIterMulForRefining * length / stride + kMinItersForRefining; 53 uint32_t seed = 7; 54 size_t iter; 55 iters = ((iters + num_histograms - 1) / num_histograms) * num_histograms; 56 for (iter = 0; iter < iters; ++iter) { 57 FN(HistogramClear)(tmp); 58 FN(RandomSample)(&seed, data, length, stride, tmp); 59 FN(HistogramAddHistogram)(&histograms[iter % num_histograms], tmp); 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. */ 66 static 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 alphabet_size = FN(HistogramDataSize)(); 75 const size_t bitmap_len = (num_histograms + 7) >> 3; 76 size_t num_blocks = 1; 77 size_t byte_ix; 78 size_t i; 79 size_t j; 80 BROTLI_DCHECK(num_histograms <= 256); 81 82 /* Trivial case: single histogram -> single block type. */ 83 if (num_histograms <= 1) { 84 for (i = 0; i < length; ++i) { 85 block_id[i] = 0; 86 } 87 return 1; 88 } 89 90 /* Fill bitcost for each symbol of all histograms. 91 * Non-existing symbol cost: 2 + log2(total_count). 92 * Regular symbol cost: -log2(symbol_count / total_count). */ 93 memset(insert_cost, 0, 94 sizeof(insert_cost[0]) * alphabet_size * num_histograms); 95 for (i = 0; i < num_histograms; ++i) { 96 insert_cost[i] = FastLog2((uint32_t)histograms[i].total_count_); 97 } 98 for (i = alphabet_size; i != 0;) { 99 /* Reverse order to use the 0-th row as a temporary storage. */ 100 --i; 101 for (j = 0; j < num_histograms; ++j) { 102 insert_cost[i * num_histograms + j] = 103 insert_cost[j] - BitCost(histograms[j].data_[i]); 104 } 105 } 106 107 /* After each iteration of this loop, cost[k] will contain the difference 108 between the minimum cost of arriving at the current byte position using 109 entropy code k, and the minimum cost of arriving at the current byte 110 position. This difference is capped at the block switch cost, and if it 111 reaches block switch cost, it means that when we trace back from the last 112 position, we need to switch here. */ 113 memset(cost, 0, sizeof(cost[0]) * num_histograms); 114 memset(switch_signal, 0, sizeof(switch_signal[0]) * length * bitmap_len); 115 for (byte_ix = 0; byte_ix < length; ++byte_ix) { 116 size_t ix = byte_ix * bitmap_len; 117 size_t symbol = data[byte_ix]; 118 size_t insert_cost_ix = symbol * num_histograms; 119 double min_cost = 1e99; 120 double block_switch_cost = block_switch_bitcost; 121 static const size_t prologue_length = 2000; 122 static const double multiplier = 0.07 / 2000; 123 size_t k; 124 for (k = 0; k < num_histograms; ++k) { 125 /* We are coding the symbol with entropy code k. */ 126 cost[k] += insert_cost[insert_cost_ix + k]; 127 if (cost[k] < min_cost) { 128 min_cost = cost[k]; 129 block_id[byte_ix] = (uint8_t)k; 130 } 131 } 132 /* More blocks for the beginning. */ 133 if (byte_ix < prologue_length) { 134 block_switch_cost *= 0.77 + multiplier * (double)byte_ix; 135 } 136 for (k = 0; k < num_histograms; ++k) { 137 cost[k] -= min_cost; 138 if (cost[k] >= block_switch_cost) { 139 const uint8_t mask = (uint8_t)(1u << (k & 7)); 140 cost[k] = block_switch_cost; 141 BROTLI_DCHECK((k >> 3) < bitmap_len); 142 switch_signal[ix + (k >> 3)] |= mask; 143 } 144 } 145 } 146 147 byte_ix = length - 1; 148 { /* Trace back from the last position and switch at the marked places. */ 149 size_t ix = byte_ix * bitmap_len; 150 uint8_t cur_id = block_id[byte_ix]; 151 while (byte_ix > 0) { 152 const uint8_t mask = (uint8_t)(1u << (cur_id & 7)); 153 BROTLI_DCHECK(((size_t)cur_id >> 3) < bitmap_len); 154 --byte_ix; 155 ix -= bitmap_len; 156 if (switch_signal[ix + (cur_id >> 3)] & mask) { 157 if (cur_id != block_id[byte_ix]) { 158 cur_id = block_id[byte_ix]; 159 ++num_blocks; 160 } 161 } 162 block_id[byte_ix] = cur_id; 163 } 164 } 165 return num_blocks; 166 } 167 168 static size_t FN(RemapBlockIds)(uint8_t* block_ids, const size_t length, 169 uint16_t* new_id, const size_t num_histograms) { 170 static const uint16_t kInvalidId = 256; 171 uint16_t next_id = 0; 172 size_t i; 173 for (i = 0; i < num_histograms; ++i) { 174 new_id[i] = kInvalidId; 175 } 176 for (i = 0; i < length; ++i) { 177 BROTLI_DCHECK(block_ids[i] < num_histograms); 178 if (new_id[block_ids[i]] == kInvalidId) { 179 new_id[block_ids[i]] = next_id++; 180 } 181 } 182 for (i = 0; i < length; ++i) { 183 block_ids[i] = (uint8_t)new_id[block_ids[i]]; 184 BROTLI_DCHECK(block_ids[i] < num_histograms); 185 } 186 BROTLI_DCHECK(next_id <= num_histograms); 187 return next_id; 188 } 189 190 static void FN(BuildBlockHistograms)(const DataType* data, const size_t length, 191 const uint8_t* block_ids, 192 const size_t num_histograms, 193 HistogramType* histograms) { 194 size_t i; 195 FN(ClearHistograms)(histograms, num_histograms); 196 for (i = 0; i < length; ++i) { 197 FN(HistogramAdd)(&histograms[block_ids[i]], data[i]); 198 } 199 } 200 201 /* Given the initial partitioning build partitioning with limited number 202 * of histograms (and block types). */ 203 static void FN(ClusterBlocks)(MemoryManager* m, 204 const DataType* data, const size_t length, 205 const size_t num_blocks, 206 uint8_t* block_ids, 207 BlockSplit* split) { 208 uint32_t* histogram_symbols = BROTLI_ALLOC(m, uint32_t, num_blocks); 209 uint32_t* u32 = 210 BROTLI_ALLOC(m, uint32_t, num_blocks + 4 * HISTOGRAMS_PER_BATCH); 211 const size_t expected_num_clusters = CLUSTERS_PER_BATCH * 212 (num_blocks + HISTOGRAMS_PER_BATCH - 1) / HISTOGRAMS_PER_BATCH; 213 size_t all_histograms_size = 0; 214 size_t all_histograms_capacity = expected_num_clusters; 215 HistogramType* all_histograms = 216 BROTLI_ALLOC(m, HistogramType, all_histograms_capacity); 217 size_t cluster_size_size = 0; 218 size_t cluster_size_capacity = expected_num_clusters; 219 uint32_t* cluster_size = BROTLI_ALLOC(m, uint32_t, cluster_size_capacity); 220 size_t num_clusters = 0; 221 HistogramType* histograms = BROTLI_ALLOC(m, HistogramType, 222 BROTLI_MIN(size_t, num_blocks, HISTOGRAMS_PER_BATCH)); 223 size_t max_num_pairs = 224 HISTOGRAMS_PER_BATCH * HISTOGRAMS_PER_BATCH / 2; 225 size_t pairs_capacity = max_num_pairs + 1; 226 HistogramPair* pairs = BROTLI_ALLOC(m, HistogramPair, pairs_capacity); 227 size_t pos = 0; 228 uint32_t* clusters; 229 size_t num_final_clusters; 230 static const uint32_t kInvalidIndex = BROTLI_UINT32_MAX; 231 uint32_t* new_index; 232 size_t i; 233 uint32_t* BROTLI_RESTRICT const sizes = 234 u32 ? (u32 + 0 * HISTOGRAMS_PER_BATCH) : NULL; 235 uint32_t* BROTLI_RESTRICT const new_clusters = 236 u32 ? (u32 + 1 * HISTOGRAMS_PER_BATCH) : NULL; 237 uint32_t* BROTLI_RESTRICT const symbols = 238 u32 ? (u32 + 2 * HISTOGRAMS_PER_BATCH) : NULL; 239 uint32_t* BROTLI_RESTRICT const remap = 240 u32 ? (u32 + 3 * HISTOGRAMS_PER_BATCH) : NULL; 241 uint32_t* BROTLI_RESTRICT const block_lengths = 242 u32 ? (u32 + 4 * HISTOGRAMS_PER_BATCH) : NULL; 243 /* TODO(eustas): move to arena? */ 244 HistogramType* tmp = BROTLI_ALLOC(m, HistogramType, 2); 245 246 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(histogram_symbols) || 247 BROTLI_IS_NULL(u32) || BROTLI_IS_NULL(all_histograms) || 248 BROTLI_IS_NULL(cluster_size) || BROTLI_IS_NULL(histograms) || 249 BROTLI_IS_NULL(pairs) || BROTLI_IS_NULL(tmp)) { 250 return; 251 } 252 253 memset(u32, 0, (num_blocks + 4 * HISTOGRAMS_PER_BATCH) * sizeof(uint32_t)); 254 255 /* Calculate block lengths (convert repeating values -> series length). */ 256 { 257 size_t block_idx = 0; 258 for (i = 0; i < length; ++i) { 259 BROTLI_DCHECK(block_idx < num_blocks); 260 ++block_lengths[block_idx]; 261 if (i + 1 == length || block_ids[i] != block_ids[i + 1]) { 262 ++block_idx; 263 } 264 } 265 BROTLI_DCHECK(block_idx == num_blocks); 266 } 267 268 /* Pre-cluster blocks (cluster batches). */ 269 for (i = 0; i < num_blocks; i += HISTOGRAMS_PER_BATCH) { 270 const size_t num_to_combine = 271 BROTLI_MIN(size_t, num_blocks - i, HISTOGRAMS_PER_BATCH); 272 size_t num_new_clusters; 273 size_t j; 274 for (j = 0; j < num_to_combine; ++j) { 275 size_t k; 276 size_t block_length = block_lengths[i + j]; 277 FN(HistogramClear)(&histograms[j]); 278 for (k = 0; k < block_length; ++k) { 279 FN(HistogramAdd)(&histograms[j], data[pos++]); 280 } 281 histograms[j].bit_cost_ = FN(BrotliPopulationCost)(&histograms[j]); 282 new_clusters[j] = (uint32_t)j; 283 symbols[j] = (uint32_t)j; 284 sizes[j] = 1; 285 } 286 num_new_clusters = FN(BrotliHistogramCombine)( 287 histograms, tmp, sizes, symbols, new_clusters, pairs, num_to_combine, 288 num_to_combine, HISTOGRAMS_PER_BATCH, max_num_pairs); 289 BROTLI_ENSURE_CAPACITY(m, HistogramType, all_histograms, 290 all_histograms_capacity, all_histograms_size + num_new_clusters); 291 BROTLI_ENSURE_CAPACITY(m, uint32_t, cluster_size, 292 cluster_size_capacity, cluster_size_size + num_new_clusters); 293 if (BROTLI_IS_OOM(m)) return; 294 for (j = 0; j < num_new_clusters; ++j) { 295 all_histograms[all_histograms_size++] = histograms[new_clusters[j]]; 296 cluster_size[cluster_size_size++] = sizes[new_clusters[j]]; 297 remap[new_clusters[j]] = (uint32_t)j; 298 } 299 for (j = 0; j < num_to_combine; ++j) { 300 histogram_symbols[i + j] = (uint32_t)num_clusters + remap[symbols[j]]; 301 } 302 num_clusters += num_new_clusters; 303 BROTLI_DCHECK(num_clusters == cluster_size_size); 304 BROTLI_DCHECK(num_clusters == all_histograms_size); 305 } 306 BROTLI_FREE(m, histograms); 307 308 /* Final clustering. */ 309 max_num_pairs = 310 BROTLI_MIN(size_t, 64 * num_clusters, (num_clusters / 2) * num_clusters); 311 if (pairs_capacity < max_num_pairs + 1) { 312 BROTLI_FREE(m, pairs); 313 pairs = BROTLI_ALLOC(m, HistogramPair, max_num_pairs + 1); 314 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(pairs)) return; 315 } 316 clusters = BROTLI_ALLOC(m, uint32_t, num_clusters); 317 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(clusters)) return; 318 for (i = 0; i < num_clusters; ++i) { 319 clusters[i] = (uint32_t)i; 320 } 321 num_final_clusters = FN(BrotliHistogramCombine)( 322 all_histograms, tmp, cluster_size, histogram_symbols, clusters, pairs, 323 num_clusters, num_blocks, BROTLI_MAX_NUMBER_OF_BLOCK_TYPES, 324 max_num_pairs); 325 BROTLI_FREE(m, pairs); 326 BROTLI_FREE(m, cluster_size); 327 328 /* Assign blocks to final histograms. */ 329 new_index = BROTLI_ALLOC(m, uint32_t, num_clusters); 330 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(new_index)) return; 331 for (i = 0; i < num_clusters; ++i) new_index[i] = kInvalidIndex; 332 pos = 0; 333 { 334 uint32_t next_index = 0; 335 for (i = 0; i < num_blocks; ++i) { 336 size_t j; 337 uint32_t best_out; 338 double best_bits; 339 FN(HistogramClear)(tmp); 340 for (j = 0; j < block_lengths[i]; ++j) { 341 FN(HistogramAdd)(tmp, data[pos++]); 342 } 343 /* Among equally good histograms prefer last used. */ 344 /* TODO(eustas): should we give a block-switch discount here? */ 345 best_out = (i == 0) ? histogram_symbols[0] : histogram_symbols[i - 1]; 346 best_bits = FN(BrotliHistogramBitCostDistance)( 347 tmp, &all_histograms[best_out], tmp + 1); 348 for (j = 0; j < num_final_clusters; ++j) { 349 const double cur_bits = FN(BrotliHistogramBitCostDistance)( 350 tmp, &all_histograms[clusters[j]], tmp + 1); 351 if (cur_bits < best_bits) { 352 best_bits = cur_bits; 353 best_out = clusters[j]; 354 } 355 } 356 histogram_symbols[i] = best_out; 357 if (new_index[best_out] == kInvalidIndex) { 358 new_index[best_out] = next_index++; 359 } 360 } 361 } 362 BROTLI_FREE(m, tmp); 363 BROTLI_FREE(m, clusters); 364 BROTLI_FREE(m, all_histograms); 365 BROTLI_ENSURE_CAPACITY( 366 m, uint8_t, split->types, split->types_alloc_size, num_blocks); 367 BROTLI_ENSURE_CAPACITY( 368 m, uint32_t, split->lengths, split->lengths_alloc_size, num_blocks); 369 if (BROTLI_IS_OOM(m)) return; 370 371 /* Rewrite final assignment to block-split. There might be less blocks 372 * than |num_blocks| due to clustering. */ 373 { 374 uint32_t cur_length = 0; 375 size_t block_idx = 0; 376 uint8_t max_type = 0; 377 for (i = 0; i < num_blocks; ++i) { 378 cur_length += block_lengths[i]; 379 if (i + 1 == num_blocks || 380 histogram_symbols[i] != histogram_symbols[i + 1]) { 381 const uint8_t id = (uint8_t)new_index[histogram_symbols[i]]; 382 split->types[block_idx] = id; 383 split->lengths[block_idx] = cur_length; 384 max_type = BROTLI_MAX(uint8_t, max_type, id); 385 cur_length = 0; 386 ++block_idx; 387 } 388 } 389 split->num_blocks = block_idx; 390 split->num_types = (size_t)max_type + 1; 391 } 392 BROTLI_FREE(m, new_index); 393 BROTLI_FREE(m, u32); 394 BROTLI_FREE(m, histogram_symbols); 395 } 396 397 /* Create BlockSplit (partitioning) given the limits, estimates and "effort" 398 * parameters. 399 * 400 * NB: max_histograms is often less than number of histograms allowed by format; 401 * this is done intentionally, to save some "space" for context-aware 402 * clustering (here entropy is estimated for context-free symbols). */ 403 static void FN(SplitByteVector)(MemoryManager* m, 404 const DataType* data, const size_t length, 405 const size_t symbols_per_histogram, 406 const size_t max_histograms, 407 const size_t sampling_stride_length, 408 const double block_switch_cost, 409 const BrotliEncoderParams* params, 410 BlockSplit* split) { 411 const size_t data_size = FN(HistogramDataSize)(); 412 HistogramType* histograms; 413 HistogramType* tmp; 414 /* Calculate number of histograms; initial estimate is one histogram per 415 * specified amount of symbols; however, this value is capped. */ 416 size_t num_histograms = length / symbols_per_histogram + 1; 417 if (num_histograms > max_histograms) { 418 num_histograms = max_histograms; 419 } 420 421 /* Corner case: no input. */ 422 if (length == 0) { 423 split->num_types = 1; 424 return; 425 } 426 427 if (length < kMinLengthForBlockSplitting) { 428 BROTLI_ENSURE_CAPACITY(m, uint8_t, 429 split->types, split->types_alloc_size, split->num_blocks + 1); 430 BROTLI_ENSURE_CAPACITY(m, uint32_t, 431 split->lengths, split->lengths_alloc_size, split->num_blocks + 1); 432 if (BROTLI_IS_OOM(m)) return; 433 split->num_types = 1; 434 split->types[split->num_blocks] = 0; 435 split->lengths[split->num_blocks] = (uint32_t)length; 436 split->num_blocks++; 437 return; 438 } 439 histograms = BROTLI_ALLOC(m, HistogramType, num_histograms + 1); 440 tmp = histograms + num_histograms; 441 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(histograms)) return; 442 /* Find good entropy codes. */ 443 FN(InitialEntropyCodes)(data, length, 444 sampling_stride_length, 445 num_histograms, histograms); 446 FN(RefineEntropyCodes)(data, length, 447 sampling_stride_length, 448 num_histograms, histograms, tmp); 449 { 450 /* Find a good path through literals with the good entropy codes. */ 451 uint8_t* block_ids = BROTLI_ALLOC(m, uint8_t, length); 452 size_t num_blocks = 0; 453 const size_t bitmaplen = (num_histograms + 7) >> 3; 454 double* insert_cost = BROTLI_ALLOC(m, double, data_size * num_histograms); 455 double* cost = BROTLI_ALLOC(m, double, num_histograms); 456 uint8_t* switch_signal = BROTLI_ALLOC(m, uint8_t, length * bitmaplen); 457 uint16_t* new_id = BROTLI_ALLOC(m, uint16_t, num_histograms); 458 const size_t iters = params->quality < HQ_ZOPFLIFICATION_QUALITY ? 3 : 10; 459 size_t i; 460 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(block_ids) || 461 BROTLI_IS_NULL(insert_cost) || BROTLI_IS_NULL(cost) || 462 BROTLI_IS_NULL(switch_signal) || BROTLI_IS_NULL(new_id)) { 463 return; 464 } 465 for (i = 0; i < iters; ++i) { 466 num_blocks = FN(FindBlocks)(data, length, 467 block_switch_cost, 468 num_histograms, histograms, 469 insert_cost, cost, switch_signal, 470 block_ids); 471 num_histograms = FN(RemapBlockIds)(block_ids, length, 472 new_id, num_histograms); 473 FN(BuildBlockHistograms)(data, length, block_ids, 474 num_histograms, histograms); 475 } 476 BROTLI_FREE(m, insert_cost); 477 BROTLI_FREE(m, cost); 478 BROTLI_FREE(m, switch_signal); 479 BROTLI_FREE(m, new_id); 480 BROTLI_FREE(m, histograms); 481 FN(ClusterBlocks)(m, data, length, num_blocks, block_ids, split); 482 if (BROTLI_IS_OOM(m)) return; 483 BROTLI_FREE(m, block_ids); 484 } 485 } 486 487 #undef HistogramType