+++ /dev/null
-/* NOLINT(build/header_guard) */\r
-/* Copyright 2013 Google Inc. All Rights Reserved.\r
-\r
- Distributed under MIT license.\r
- See file LICENSE for detail or copy at https://opensource.org/licenses/MIT\r
-*/\r
-\r
-/* template parameters: FN, DataType */\r
-\r
-#define HistogramType FN(Histogram)\r
-\r
-static void FN(InitialEntropyCodes)(const DataType* data, size_t length,\r
- size_t stride,\r
- size_t num_histograms,\r
- HistogramType* histograms) {\r
- uint32_t seed = 7;\r
- size_t block_length = length / num_histograms;\r
- size_t i;\r
- FN(ClearHistograms)(histograms, num_histograms);\r
- for (i = 0; i < num_histograms; ++i) {\r
- size_t pos = length * i / num_histograms;\r
- if (i != 0) {\r
- pos += MyRand(&seed) % block_length;\r
- }\r
- if (pos + stride >= length) {\r
- pos = length - stride - 1;\r
- }\r
- FN(HistogramAddVector)(&histograms[i], data + pos, stride);\r
- }\r
-}\r
-\r
-static void FN(RandomSample)(uint32_t* seed,\r
- const DataType* data,\r
- size_t length,\r
- size_t stride,\r
- HistogramType* sample) {\r
- size_t pos = 0;\r
- if (stride >= length) {\r
- stride = length;\r
- } else {\r
- pos = MyRand(seed) % (length - stride + 1);\r
- }\r
- FN(HistogramAddVector)(sample, data + pos, stride);\r
-}\r
-\r
-static void FN(RefineEntropyCodes)(const DataType* data, size_t length,\r
- size_t stride,\r
- size_t num_histograms,\r
- HistogramType* histograms) {\r
- size_t iters =\r
- kIterMulForRefining * length / stride + kMinItersForRefining;\r
- uint32_t seed = 7;\r
- size_t iter;\r
- iters = ((iters + num_histograms - 1) / num_histograms) * num_histograms;\r
- for (iter = 0; iter < iters; ++iter) {\r
- HistogramType sample;\r
- FN(HistogramClear)(&sample);\r
- FN(RandomSample)(&seed, data, length, stride, &sample);\r
- FN(HistogramAddHistogram)(&histograms[iter % num_histograms], &sample);\r
- }\r
-}\r
-\r
-/* Assigns a block id from the range [0, num_histograms) to each data element\r
- in data[0..length) and fills in block_id[0..length) with the assigned values.\r
- Returns the number of blocks, i.e. one plus the number of block switches. */\r
-static size_t FN(FindBlocks)(const DataType* data, const size_t length,\r
- const double block_switch_bitcost,\r
- const size_t num_histograms,\r
- const HistogramType* histograms,\r
- double* insert_cost,\r
- double* cost,\r
- uint8_t* switch_signal,\r
- uint8_t* block_id) {\r
- const size_t data_size = FN(HistogramDataSize)();\r
- const size_t bitmaplen = (num_histograms + 7) >> 3;\r
- size_t num_blocks = 1;\r
- size_t i;\r
- size_t j;\r
- BROTLI_DCHECK(num_histograms <= 256);\r
- if (num_histograms <= 1) {\r
- for (i = 0; i < length; ++i) {\r
- block_id[i] = 0;\r
- }\r
- return 1;\r
- }\r
- memset(insert_cost, 0, sizeof(insert_cost[0]) * data_size * num_histograms);\r
- for (i = 0; i < num_histograms; ++i) {\r
- insert_cost[i] = FastLog2((uint32_t)histograms[i].total_count_);\r
- }\r
- for (i = data_size; i != 0;) {\r
- --i;\r
- for (j = 0; j < num_histograms; ++j) {\r
- insert_cost[i * num_histograms + j] =\r
- insert_cost[j] - BitCost(histograms[j].data_[i]);\r
- }\r
- }\r
- memset(cost, 0, sizeof(cost[0]) * num_histograms);\r
- memset(switch_signal, 0, sizeof(switch_signal[0]) * length * bitmaplen);\r
- /* After each iteration of this loop, cost[k] will contain the difference\r
- between the minimum cost of arriving at the current byte position using\r
- entropy code k, and the minimum cost of arriving at the current byte\r
- position. This difference is capped at the block switch cost, and if it\r
- reaches block switch cost, it means that when we trace back from the last\r
- position, we need to switch here. */\r
- for (i = 0; i < length; ++i) {\r
- const size_t byte_ix = i;\r
- size_t ix = byte_ix * bitmaplen;\r
- size_t insert_cost_ix = data[byte_ix] * num_histograms;\r
- double min_cost = 1e99;\r
- double block_switch_cost = block_switch_bitcost;\r
- size_t k;\r
- for (k = 0; k < num_histograms; ++k) {\r
- /* We are coding the symbol in data[byte_ix] with entropy code k. */\r
- cost[k] += insert_cost[insert_cost_ix + k];\r
- if (cost[k] < min_cost) {\r
- min_cost = cost[k];\r
- block_id[byte_ix] = (uint8_t)k;\r
- }\r
- }\r
- /* More blocks for the beginning. */\r
- if (byte_ix < 2000) {\r
- block_switch_cost *= 0.77 + 0.07 * (double)byte_ix / 2000;\r
- }\r
- for (k = 0; k < num_histograms; ++k) {\r
- cost[k] -= min_cost;\r
- if (cost[k] >= block_switch_cost) {\r
- const uint8_t mask = (uint8_t)(1u << (k & 7));\r
- cost[k] = block_switch_cost;\r
- BROTLI_DCHECK((k >> 3) < bitmaplen);\r
- switch_signal[ix + (k >> 3)] |= mask;\r
- }\r
- }\r
- }\r
- { /* Trace back from the last position and switch at the marked places. */\r
- size_t byte_ix = length - 1;\r
- size_t ix = byte_ix * bitmaplen;\r
- uint8_t cur_id = block_id[byte_ix];\r
- while (byte_ix > 0) {\r
- const uint8_t mask = (uint8_t)(1u << (cur_id & 7));\r
- BROTLI_DCHECK(((size_t)cur_id >> 3) < bitmaplen);\r
- --byte_ix;\r
- ix -= bitmaplen;\r
- if (switch_signal[ix + (cur_id >> 3)] & mask) {\r
- if (cur_id != block_id[byte_ix]) {\r
- cur_id = block_id[byte_ix];\r
- ++num_blocks;\r
- }\r
- }\r
- block_id[byte_ix] = cur_id;\r
- }\r
- }\r
- return num_blocks;\r
-}\r
-\r
-static size_t FN(RemapBlockIds)(uint8_t* block_ids, const size_t length,\r
- uint16_t* new_id, const size_t num_histograms) {\r
- static const uint16_t kInvalidId = 256;\r
- uint16_t next_id = 0;\r
- size_t i;\r
- for (i = 0; i < num_histograms; ++i) {\r
- new_id[i] = kInvalidId;\r
- }\r
- for (i = 0; i < length; ++i) {\r
- BROTLI_DCHECK(block_ids[i] < num_histograms);\r
- if (new_id[block_ids[i]] == kInvalidId) {\r
- new_id[block_ids[i]] = next_id++;\r
- }\r
- }\r
- for (i = 0; i < length; ++i) {\r
- block_ids[i] = (uint8_t)new_id[block_ids[i]];\r
- BROTLI_DCHECK(block_ids[i] < num_histograms);\r
- }\r
- BROTLI_DCHECK(next_id <= num_histograms);\r
- return next_id;\r
-}\r
-\r
-static void FN(BuildBlockHistograms)(const DataType* data, const size_t length,\r
- const uint8_t* block_ids,\r
- const size_t num_histograms,\r
- HistogramType* histograms) {\r
- size_t i;\r
- FN(ClearHistograms)(histograms, num_histograms);\r
- for (i = 0; i < length; ++i) {\r
- FN(HistogramAdd)(&histograms[block_ids[i]], data[i]);\r
- }\r
-}\r
-\r
-static void FN(ClusterBlocks)(MemoryManager* m,\r
- const DataType* data, const size_t length,\r
- const size_t num_blocks,\r
- uint8_t* block_ids,\r
- BlockSplit* split) {\r
- uint32_t* histogram_symbols = BROTLI_ALLOC(m, uint32_t, num_blocks);\r
- uint32_t* block_lengths = BROTLI_ALLOC(m, uint32_t, num_blocks);\r
- const size_t expected_num_clusters = CLUSTERS_PER_BATCH *\r
- (num_blocks + HISTOGRAMS_PER_BATCH - 1) / HISTOGRAMS_PER_BATCH;\r
- size_t all_histograms_size = 0;\r
- size_t all_histograms_capacity = expected_num_clusters;\r
- HistogramType* all_histograms =\r
- BROTLI_ALLOC(m, HistogramType, all_histograms_capacity);\r
- size_t cluster_size_size = 0;\r
- size_t cluster_size_capacity = expected_num_clusters;\r
- uint32_t* cluster_size = BROTLI_ALLOC(m, uint32_t, cluster_size_capacity);\r
- size_t num_clusters = 0;\r
- HistogramType* histograms = BROTLI_ALLOC(m, HistogramType,\r
- BROTLI_MIN(size_t, num_blocks, HISTOGRAMS_PER_BATCH));\r
- size_t max_num_pairs =\r
- HISTOGRAMS_PER_BATCH * HISTOGRAMS_PER_BATCH / 2;\r
- size_t pairs_capacity = max_num_pairs + 1;\r
- HistogramPair* pairs = BROTLI_ALLOC(m, HistogramPair, pairs_capacity);\r
- size_t pos = 0;\r
- uint32_t* clusters;\r
- size_t num_final_clusters;\r
- static const uint32_t kInvalidIndex = BROTLI_UINT32_MAX;\r
- uint32_t* new_index;\r
- size_t i;\r
- uint32_t sizes[HISTOGRAMS_PER_BATCH] = { 0 };\r
- uint32_t new_clusters[HISTOGRAMS_PER_BATCH] = { 0 };\r
- uint32_t symbols[HISTOGRAMS_PER_BATCH] = { 0 };\r
- uint32_t remap[HISTOGRAMS_PER_BATCH] = { 0 };\r
-\r
- if (BROTLI_IS_OOM(m)) return;\r
-\r
- memset(block_lengths, 0, num_blocks * sizeof(uint32_t));\r
-\r
- {\r
- size_t block_idx = 0;\r
- for (i = 0; i < length; ++i) {\r
- BROTLI_DCHECK(block_idx < num_blocks);\r
- ++block_lengths[block_idx];\r
- if (i + 1 == length || block_ids[i] != block_ids[i + 1]) {\r
- ++block_idx;\r
- }\r
- }\r
- BROTLI_DCHECK(block_idx == num_blocks);\r
- }\r
-\r
- for (i = 0; i < num_blocks; i += HISTOGRAMS_PER_BATCH) {\r
- const size_t num_to_combine =\r
- BROTLI_MIN(size_t, num_blocks - i, HISTOGRAMS_PER_BATCH);\r
- size_t num_new_clusters;\r
- size_t j;\r
- for (j = 0; j < num_to_combine; ++j) {\r
- size_t k;\r
- FN(HistogramClear)(&histograms[j]);\r
- for (k = 0; k < block_lengths[i + j]; ++k) {\r
- FN(HistogramAdd)(&histograms[j], data[pos++]);\r
- }\r
- histograms[j].bit_cost_ = FN(BrotliPopulationCost)(&histograms[j]);\r
- new_clusters[j] = (uint32_t)j;\r
- symbols[j] = (uint32_t)j;\r
- sizes[j] = 1;\r
- }\r
- num_new_clusters = FN(BrotliHistogramCombine)(\r
- histograms, sizes, symbols, new_clusters, pairs, num_to_combine,\r
- num_to_combine, HISTOGRAMS_PER_BATCH, max_num_pairs);\r
- BROTLI_ENSURE_CAPACITY(m, HistogramType, all_histograms,\r
- all_histograms_capacity, all_histograms_size + num_new_clusters);\r
- BROTLI_ENSURE_CAPACITY(m, uint32_t, cluster_size,\r
- cluster_size_capacity, cluster_size_size + num_new_clusters);\r
- if (BROTLI_IS_OOM(m)) return;\r
- for (j = 0; j < num_new_clusters; ++j) {\r
- all_histograms[all_histograms_size++] = histograms[new_clusters[j]];\r
- cluster_size[cluster_size_size++] = sizes[new_clusters[j]];\r
- remap[new_clusters[j]] = (uint32_t)j;\r
- }\r
- for (j = 0; j < num_to_combine; ++j) {\r
- histogram_symbols[i + j] = (uint32_t)num_clusters + remap[symbols[j]];\r
- }\r
- num_clusters += num_new_clusters;\r
- BROTLI_DCHECK(num_clusters == cluster_size_size);\r
- BROTLI_DCHECK(num_clusters == all_histograms_size);\r
- }\r
- BROTLI_FREE(m, histograms);\r
-\r
- max_num_pairs =\r
- BROTLI_MIN(size_t, 64 * num_clusters, (num_clusters / 2) * num_clusters);\r
- if (pairs_capacity < max_num_pairs + 1) {\r
- BROTLI_FREE(m, pairs);\r
- pairs = BROTLI_ALLOC(m, HistogramPair, max_num_pairs + 1);\r
- if (BROTLI_IS_OOM(m)) return;\r
- }\r
-\r
- clusters = BROTLI_ALLOC(m, uint32_t, num_clusters);\r
- if (BROTLI_IS_OOM(m)) return;\r
- for (i = 0; i < num_clusters; ++i) {\r
- clusters[i] = (uint32_t)i;\r
- }\r
- num_final_clusters = FN(BrotliHistogramCombine)(\r
- all_histograms, cluster_size, histogram_symbols, clusters, pairs,\r
- num_clusters, num_blocks, BROTLI_MAX_NUMBER_OF_BLOCK_TYPES,\r
- max_num_pairs);\r
- BROTLI_FREE(m, pairs);\r
- BROTLI_FREE(m, cluster_size);\r
-\r
- new_index = BROTLI_ALLOC(m, uint32_t, num_clusters);\r
- if (BROTLI_IS_OOM(m)) return;\r
- for (i = 0; i < num_clusters; ++i) new_index[i] = kInvalidIndex;\r
- pos = 0;\r
- {\r
- uint32_t next_index = 0;\r
- for (i = 0; i < num_blocks; ++i) {\r
- HistogramType histo;\r
- size_t j;\r
- uint32_t best_out;\r
- double best_bits;\r
- FN(HistogramClear)(&histo);\r
- for (j = 0; j < block_lengths[i]; ++j) {\r
- FN(HistogramAdd)(&histo, data[pos++]);\r
- }\r
- best_out = (i == 0) ? histogram_symbols[0] : histogram_symbols[i - 1];\r
- best_bits =\r
- FN(BrotliHistogramBitCostDistance)(&histo, &all_histograms[best_out]);\r
- for (j = 0; j < num_final_clusters; ++j) {\r
- const double cur_bits = FN(BrotliHistogramBitCostDistance)(\r
- &histo, &all_histograms[clusters[j]]);\r
- if (cur_bits < best_bits) {\r
- best_bits = cur_bits;\r
- best_out = clusters[j];\r
- }\r
- }\r
- histogram_symbols[i] = best_out;\r
- if (new_index[best_out] == kInvalidIndex) {\r
- new_index[best_out] = next_index++;\r
- }\r
- }\r
- }\r
- BROTLI_FREE(m, clusters);\r
- BROTLI_FREE(m, all_histograms);\r
- BROTLI_ENSURE_CAPACITY(\r
- m, uint8_t, split->types, split->types_alloc_size, num_blocks);\r
- BROTLI_ENSURE_CAPACITY(\r
- m, uint32_t, split->lengths, split->lengths_alloc_size, num_blocks);\r
- if (BROTLI_IS_OOM(m)) return;\r
- {\r
- uint32_t cur_length = 0;\r
- size_t block_idx = 0;\r
- uint8_t max_type = 0;\r
- for (i = 0; i < num_blocks; ++i) {\r
- cur_length += block_lengths[i];\r
- if (i + 1 == num_blocks ||\r
- histogram_symbols[i] != histogram_symbols[i + 1]) {\r
- const uint8_t id = (uint8_t)new_index[histogram_symbols[i]];\r
- split->types[block_idx] = id;\r
- split->lengths[block_idx] = cur_length;\r
- max_type = BROTLI_MAX(uint8_t, max_type, id);\r
- cur_length = 0;\r
- ++block_idx;\r
- }\r
- }\r
- split->num_blocks = block_idx;\r
- split->num_types = (size_t)max_type + 1;\r
- }\r
- BROTLI_FREE(m, new_index);\r
- BROTLI_FREE(m, block_lengths);\r
- BROTLI_FREE(m, histogram_symbols);\r
-}\r
-\r
-static void FN(SplitByteVector)(MemoryManager* m,\r
- const DataType* data, const size_t length,\r
- const size_t literals_per_histogram,\r
- const size_t max_histograms,\r
- const size_t sampling_stride_length,\r
- const double block_switch_cost,\r
- const BrotliEncoderParams* params,\r
- BlockSplit* split) {\r
- const size_t data_size = FN(HistogramDataSize)();\r
- size_t num_histograms = length / literals_per_histogram + 1;\r
- HistogramType* histograms;\r
- if (num_histograms > max_histograms) {\r
- num_histograms = max_histograms;\r
- }\r
- if (length == 0) {\r
- split->num_types = 1;\r
- return;\r
- } else if (length < kMinLengthForBlockSplitting) {\r
- BROTLI_ENSURE_CAPACITY(m, uint8_t,\r
- split->types, split->types_alloc_size, split->num_blocks + 1);\r
- BROTLI_ENSURE_CAPACITY(m, uint32_t,\r
- split->lengths, split->lengths_alloc_size, split->num_blocks + 1);\r
- if (BROTLI_IS_OOM(m)) return;\r
- split->num_types = 1;\r
- split->types[split->num_blocks] = 0;\r
- split->lengths[split->num_blocks] = (uint32_t)length;\r
- split->num_blocks++;\r
- return;\r
- }\r
- histograms = BROTLI_ALLOC(m, HistogramType, num_histograms);\r
- if (BROTLI_IS_OOM(m)) return;\r
- /* Find good entropy codes. */\r
- FN(InitialEntropyCodes)(data, length,\r
- sampling_stride_length,\r
- num_histograms, histograms);\r
- FN(RefineEntropyCodes)(data, length,\r
- sampling_stride_length,\r
- num_histograms, histograms);\r
- {\r
- /* Find a good path through literals with the good entropy codes. */\r
- uint8_t* block_ids = BROTLI_ALLOC(m, uint8_t, length);\r
- size_t num_blocks = 0;\r
- const size_t bitmaplen = (num_histograms + 7) >> 3;\r
- double* insert_cost = BROTLI_ALLOC(m, double, data_size * num_histograms);\r
- double* cost = BROTLI_ALLOC(m, double, num_histograms);\r
- uint8_t* switch_signal = BROTLI_ALLOC(m, uint8_t, length * bitmaplen);\r
- uint16_t* new_id = BROTLI_ALLOC(m, uint16_t, num_histograms);\r
- const size_t iters = params->quality < HQ_ZOPFLIFICATION_QUALITY ? 3 : 10;\r
- size_t i;\r
- if (BROTLI_IS_OOM(m)) return;\r
- for (i = 0; i < iters; ++i) {\r
- num_blocks = FN(FindBlocks)(data, length,\r
- block_switch_cost,\r
- num_histograms, histograms,\r
- insert_cost, cost, switch_signal,\r
- block_ids);\r
- num_histograms = FN(RemapBlockIds)(block_ids, length,\r
- new_id, num_histograms);\r
- FN(BuildBlockHistograms)(data, length, block_ids,\r
- num_histograms, histograms);\r
- }\r
- BROTLI_FREE(m, insert_cost);\r
- BROTLI_FREE(m, cost);\r
- BROTLI_FREE(m, switch_signal);\r
- BROTLI_FREE(m, new_id);\r
- BROTLI_FREE(m, histograms);\r
- FN(ClusterBlocks)(m, data, length, num_blocks, block_ids, split);\r
- if (BROTLI_IS_OOM(m)) return;\r
- BROTLI_FREE(m, block_ids);\r
- }\r
-}\r
-\r
-#undef HistogramType\r
projects / mirror_edk2.git / blobdiff