--- /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
+ unsigned int 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)(unsigned int* 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
+ pos = 0;\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
+ unsigned int 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, vec.size()) 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
+ assert(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
+ assert((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
+ assert(((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
+ assert(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
+ assert(block_ids[i] < num_histograms);\r
+ }\r
+ assert(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
+ uint8_t max_type = 0;\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
+ assert(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
+ assert(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
+ assert(num_clusters == cluster_size_size);\r
+ assert(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
+ 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;\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