Index: third_party/brotli/enc/block_splitter_inc.h |
diff --git a/third_party/brotli/enc/block_splitter.cc b/third_party/brotli/enc/block_splitter_inc.h |
similarity index 15% |
rename from third_party/brotli/enc/block_splitter.cc |
rename to third_party/brotli/enc/block_splitter_inc.h |
index db8d9c606d6fab28641f815e0cffdf2aa67612b2..8574fb9a63300d4601c4ad0a34008d06aaa6031e 100644 |
--- a/third_party/brotli/enc/block_splitter.cc |
+++ b/third_party/brotli/enc/block_splitter_inc.h |
@@ -1,98 +1,23 @@ |
+/* NOLINT(build/header_guard) */ |
/* Copyright 2013 Google Inc. All Rights Reserved. |
Distributed under MIT license. |
See file LICENSE for detail or copy at https://opensource.org/licenses/MIT |
*/ |
-// Block split point selection utilities. |
+/* template parameters: FN, DataType */ |
-#include "./block_splitter.h" |
+#define HistogramType FN(Histogram) |
-#include <assert.h> |
-#include <math.h> |
- |
-#include <algorithm> |
-#include <cstring> |
-#include <vector> |
- |
-#include "./cluster.h" |
-#include "./command.h" |
-#include "./fast_log.h" |
-#include "./histogram.h" |
- |
-namespace brotli { |
- |
-static const size_t kMaxLiteralHistograms = 100; |
-static const size_t kMaxCommandHistograms = 50; |
-static const double kLiteralBlockSwitchCost = 28.1; |
-static const double kCommandBlockSwitchCost = 13.5; |
-static const double kDistanceBlockSwitchCost = 14.6; |
-static const size_t kLiteralStrideLength = 70; |
-static const size_t kCommandStrideLength = 40; |
-static const size_t kSymbolsPerLiteralHistogram = 544; |
-static const size_t kSymbolsPerCommandHistogram = 530; |
-static const size_t kSymbolsPerDistanceHistogram = 544; |
-static const size_t kMinLengthForBlockSplitting = 128; |
-static const size_t kIterMulForRefining = 2; |
-static const size_t kMinItersForRefining = 100; |
- |
-void CopyLiteralsToByteArray(const Command* cmds, |
- const size_t num_commands, |
- const uint8_t* data, |
- const size_t offset, |
- const size_t mask, |
- std::vector<uint8_t>* literals) { |
- // Count how many we have. |
- size_t total_length = 0; |
- for (size_t i = 0; i < num_commands; ++i) { |
- total_length += cmds[i].insert_len_; |
- } |
- if (total_length == 0) { |
- return; |
- } |
- |
- // Allocate. |
- literals->resize(total_length); |
- |
- // Loop again, and copy this time. |
- size_t pos = 0; |
- size_t from_pos = offset & mask; |
- for (size_t i = 0; i < num_commands && pos < total_length; ++i) { |
- size_t insert_len = cmds[i].insert_len_; |
- if (from_pos + insert_len > mask) { |
- size_t head_size = mask + 1 - from_pos; |
- memcpy(&(*literals)[pos], data + from_pos, head_size); |
- from_pos = 0; |
- pos += head_size; |
- insert_len -= head_size; |
- } |
- if (insert_len > 0) { |
- memcpy(&(*literals)[pos], data + from_pos, insert_len); |
- pos += insert_len; |
- } |
- from_pos = (from_pos + insert_len + cmds[i].copy_len()) & mask; |
- } |
-} |
- |
-inline static unsigned int MyRand(unsigned int* seed) { |
- *seed *= 16807U; |
- if (*seed == 0) { |
- *seed = 1; |
- } |
- return *seed; |
-} |
- |
-template<typename HistogramType, typename DataType> |
-void InitialEntropyCodes(const DataType* data, size_t length, |
- size_t stride, |
- size_t num_histograms, |
- HistogramType* histograms) { |
- for (size_t i = 0; i < num_histograms; ++i) { |
- histograms[i].Clear(); |
- } |
+static void FN(InitialEntropyCodes)(const DataType* data, size_t length, |
+ size_t stride, |
+ size_t num_histograms, |
+ HistogramType* histograms) { |
unsigned int seed = 7; |
size_t block_length = length / num_histograms; |
- for (size_t i = 0; i < num_histograms; ++i) { |
+ size_t i; |
+ FN(ClearHistograms)(histograms, num_histograms); |
+ for (i = 0; i < num_histograms; ++i) { |
size_t pos = length * i / num_histograms; |
if (i != 0) { |
pos += MyRand(&seed) % block_length; |
@@ -100,16 +25,15 @@ void InitialEntropyCodes(const DataType* data, size_t length, |
if (pos + stride >= length) { |
pos = length - stride - 1; |
} |
- histograms[i].Add(data + pos, stride); |
+ FN(HistogramAddVector)(&histograms[i], data + pos, stride); |
} |
} |
-template<typename HistogramType, typename DataType> |
-void RandomSample(unsigned int* seed, |
- const DataType* data, |
- size_t length, |
- size_t stride, |
- HistogramType* sample) { |
+static void FN(RandomSample)(unsigned int* seed, |
+ const DataType* data, |
+ size_t length, |
+ size_t stride, |
+ HistogramType* sample) { |
size_t pos = 0; |
if (stride >= length) { |
pos = 0; |
@@ -117,389 +41,392 @@ void RandomSample(unsigned int* seed, |
} else { |
pos = MyRand(seed) % (length - stride + 1); |
} |
- sample->Add(data + pos, stride); |
+ FN(HistogramAddVector)(sample, data + pos, stride); |
} |
-template<typename HistogramType, typename DataType> |
-void RefineEntropyCodes(const DataType* data, size_t length, |
- size_t stride, |
- size_t num_histograms, |
- HistogramType* histograms) { |
+static void FN(RefineEntropyCodes)(const DataType* data, size_t length, |
+ size_t stride, |
+ size_t num_histograms, |
+ HistogramType* histograms) { |
size_t iters = |
kIterMulForRefining * length / stride + kMinItersForRefining; |
unsigned int seed = 7; |
+ size_t iter; |
iters = ((iters + num_histograms - 1) / num_histograms) * num_histograms; |
- for (size_t iter = 0; iter < iters; ++iter) { |
+ for (iter = 0; iter < iters; ++iter) { |
HistogramType sample; |
- RandomSample(&seed, data, length, stride, &sample); |
- size_t ix = iter % num_histograms; |
- histograms[ix].AddHistogram(sample); |
+ FN(HistogramClear)(&sample); |
+ FN(RandomSample)(&seed, data, length, stride, &sample); |
+ FN(HistogramAddHistogram)(&histograms[iter % num_histograms], &sample); |
} |
} |
-inline static double BitCost(size_t count) { |
- return count == 0 ? -2.0 : FastLog2(count); |
-} |
- |
-// Assigns a block id from the range [0, vec.size()) to each data element |
-// in data[0..length) and fills in block_id[0..length) with the assigned values. |
-// Returns the number of blocks, i.e. one plus the number of block switches. |
-template<typename DataType, int kSize> |
-size_t FindBlocks(const DataType* data, const size_t length, |
- const double block_switch_bitcost, |
- const size_t num_histograms, |
- const Histogram<kSize>* histograms, |
- double* insert_cost, |
- double* cost, |
- uint8_t* switch_signal, |
- uint8_t *block_id) { |
+/* Assigns a block id from the range [0, num_histograms) to each data element |
+ in data[0..length) and fills in block_id[0..length) with the assigned values. |
+ Returns the number of blocks, i.e. one plus the number of block switches. */ |
+static size_t FN(FindBlocks)(const DataType* data, const size_t length, |
+ const double block_switch_bitcost, |
+ const size_t num_histograms, |
+ const HistogramType* histograms, |
+ double* insert_cost, |
+ double* cost, |
+ uint8_t* switch_signal, |
+ uint8_t *block_id) { |
+ const size_t data_size = FN(HistogramDataSize)(); |
+ const size_t bitmaplen = (num_histograms + 7) >> 3; |
+ size_t num_blocks = 1; |
+ size_t i; |
+ size_t j; |
+ assert(num_histograms <= 256); |
if (num_histograms <= 1) { |
- for (size_t i = 0; i < length; ++i) { |
+ for (i = 0; i < length; ++i) { |
block_id[i] = 0; |
} |
return 1; |
} |
- const size_t bitmaplen = (num_histograms + 7) >> 3; |
- assert(num_histograms <= 256); |
- memset(insert_cost, 0, sizeof(insert_cost[0]) * kSize * num_histograms); |
- for (size_t j = 0; j < num_histograms; ++j) { |
- insert_cost[j] = FastLog2(static_cast<uint32_t>( |
- histograms[j].total_count_)); |
+ memset(insert_cost, 0, sizeof(insert_cost[0]) * data_size * num_histograms); |
+ for (i = 0; i < num_histograms; ++i) { |
+ insert_cost[i] = FastLog2((uint32_t)histograms[i].total_count_); |
} |
- for (size_t i = kSize; i != 0;) { |
+ for (i = data_size; i != 0;) { |
--i; |
- for (size_t j = 0; j < num_histograms; ++j) { |
+ for (j = 0; j < num_histograms; ++j) { |
insert_cost[i * num_histograms + j] = |
insert_cost[j] - BitCost(histograms[j].data_[i]); |
} |
} |
memset(cost, 0, sizeof(cost[0]) * num_histograms); |
memset(switch_signal, 0, sizeof(switch_signal[0]) * length * bitmaplen); |
- // After each iteration of this loop, cost[k] will contain the difference |
- // between the minimum cost of arriving at the current byte position using |
- // entropy code k, and the minimum cost of arriving at the current byte |
- // position. This difference is capped at the block switch cost, and if it |
- // reaches block switch cost, it means that when we trace back from the last |
- // position, we need to switch here. |
- for (size_t byte_ix = 0; byte_ix < length; ++byte_ix) { |
+ /* After each iteration of this loop, cost[k] will contain the difference |
+ between the minimum cost of arriving at the current byte position using |
+ entropy code k, and the minimum cost of arriving at the current byte |
+ position. This difference is capped at the block switch cost, and if it |
+ reaches block switch cost, it means that when we trace back from the last |
+ position, we need to switch here. */ |
+ for (i = 0; i < length; ++i) { |
+ const size_t byte_ix = i; |
size_t ix = byte_ix * bitmaplen; |
size_t insert_cost_ix = data[byte_ix] * num_histograms; |
double min_cost = 1e99; |
- for (size_t k = 0; k < num_histograms; ++k) { |
- // We are coding the symbol in data[byte_ix] with entropy code k. |
+ double block_switch_cost = block_switch_bitcost; |
+ size_t k; |
+ for (k = 0; k < num_histograms; ++k) { |
+ /* We are coding the symbol in data[byte_ix] with entropy code k. */ |
cost[k] += insert_cost[insert_cost_ix + k]; |
if (cost[k] < min_cost) { |
min_cost = cost[k]; |
- block_id[byte_ix] = static_cast<uint8_t>(k); |
+ block_id[byte_ix] = (uint8_t)k; |
} |
} |
- double block_switch_cost = block_switch_bitcost; |
- // More blocks for the beginning. |
+ /* More blocks for the beginning. */ |
if (byte_ix < 2000) { |
- block_switch_cost *= 0.77 + 0.07 * static_cast<double>(byte_ix) / 2000; |
+ block_switch_cost *= 0.77 + 0.07 * (double)byte_ix / 2000; |
} |
- for (size_t k = 0; k < num_histograms; ++k) { |
+ for (k = 0; k < num_histograms; ++k) { |
cost[k] -= min_cost; |
if (cost[k] >= block_switch_cost) { |
+ const uint8_t mask = (uint8_t)(1u << (k & 7)); |
cost[k] = block_switch_cost; |
- const uint8_t mask = static_cast<uint8_t>(1u << (k & 7)); |
assert((k >> 3) < bitmaplen); |
switch_signal[ix + (k >> 3)] |= mask; |
} |
} |
} |
- // Now trace back from the last position and switch at the marked places. |
- size_t byte_ix = length - 1; |
- size_t ix = byte_ix * bitmaplen; |
- uint8_t cur_id = block_id[byte_ix]; |
- size_t num_blocks = 1; |
- while (byte_ix > 0) { |
- --byte_ix; |
- ix -= bitmaplen; |
- const uint8_t mask = static_cast<uint8_t>(1u << (cur_id & 7)); |
- assert((static_cast<size_t>(cur_id) >> 3) < bitmaplen); |
- if (switch_signal[ix + (cur_id >> 3)] & mask) { |
- if (cur_id != block_id[byte_ix]) { |
- cur_id = block_id[byte_ix]; |
- ++num_blocks; |
+ { /* Trace back from the last position and switch at the marked places. */ |
+ size_t byte_ix = length - 1; |
+ size_t ix = byte_ix * bitmaplen; |
+ uint8_t cur_id = block_id[byte_ix]; |
+ while (byte_ix > 0) { |
+ const uint8_t mask = (uint8_t)(1u << (cur_id & 7)); |
+ assert(((size_t)cur_id >> 3) < bitmaplen); |
+ --byte_ix; |
+ ix -= bitmaplen; |
+ if (switch_signal[ix + (cur_id >> 3)] & mask) { |
+ if (cur_id != block_id[byte_ix]) { |
+ cur_id = block_id[byte_ix]; |
+ ++num_blocks; |
+ } |
} |
+ block_id[byte_ix] = cur_id; |
} |
- block_id[byte_ix] = cur_id; |
} |
return num_blocks; |
} |
-static size_t RemapBlockIds(uint8_t* block_ids, const size_t length, |
- uint16_t* new_id, const size_t num_histograms) { |
+static size_t FN(RemapBlockIds)(uint8_t* block_ids, const size_t length, |
+ uint16_t* new_id, const size_t num_histograms) { |
static const uint16_t kInvalidId = 256; |
- for (size_t i = 0; i < num_histograms; ++i) { |
+ uint16_t next_id = 0; |
+ size_t i; |
+ for (i = 0; i < num_histograms; ++i) { |
new_id[i] = kInvalidId; |
} |
- uint16_t next_id = 0; |
- for (size_t i = 0; i < length; ++i) { |
+ for (i = 0; i < length; ++i) { |
assert(block_ids[i] < num_histograms); |
if (new_id[block_ids[i]] == kInvalidId) { |
new_id[block_ids[i]] = next_id++; |
} |
} |
- for (size_t i = 0; i < length; ++i) { |
- block_ids[i] = static_cast<uint8_t>(new_id[block_ids[i]]); |
+ for (i = 0; i < length; ++i) { |
+ block_ids[i] = (uint8_t)new_id[block_ids[i]]; |
assert(block_ids[i] < num_histograms); |
} |
assert(next_id <= num_histograms); |
return next_id; |
} |
-template<typename HistogramType, typename DataType> |
-void BuildBlockHistograms(const DataType* data, const size_t length, |
- const uint8_t* block_ids, |
- const size_t num_histograms, |
- HistogramType* histograms) { |
- for (size_t i = 0; i < num_histograms; ++i) { |
- histograms[i].Clear(); |
- } |
- for (size_t i = 0; i < length; ++i) { |
- histograms[block_ids[i]].Add(data[i]); |
+static void FN(BuildBlockHistograms)(const DataType* data, const size_t length, |
+ const uint8_t* block_ids, |
+ const size_t num_histograms, |
+ HistogramType* histograms) { |
+ size_t i; |
+ FN(ClearHistograms)(histograms, num_histograms); |
+ for (i = 0; i < length; ++i) { |
+ FN(HistogramAdd)(&histograms[block_ids[i]], data[i]); |
} |
} |
-template<typename HistogramType, typename DataType> |
-void ClusterBlocks(const DataType* data, const size_t length, |
- const size_t num_blocks, |
- uint8_t* block_ids, |
- BlockSplit* split) { |
- static const size_t kMaxNumberOfBlockTypes = 256; |
- static const size_t kHistogramsPerBatch = 64; |
- static const size_t kClustersPerBatch = 16; |
- std::vector<uint32_t> histogram_symbols(num_blocks); |
- std::vector<uint32_t> block_lengths(num_blocks); |
+static void FN(ClusterBlocks)(MemoryManager* m, |
+ const DataType* data, const size_t length, |
+ const size_t num_blocks, |
+ uint8_t* block_ids, |
+ BlockSplit* split) { |
+ uint32_t* histogram_symbols = BROTLI_ALLOC(m, uint32_t, num_blocks); |
+ uint32_t* block_lengths = BROTLI_ALLOC(m, uint32_t, num_blocks); |
+ const size_t expected_num_clusters = CLUSTERS_PER_BATCH * |
+ (num_blocks + HISTOGRAMS_PER_BATCH - 1) / HISTOGRAMS_PER_BATCH; |
+ size_t all_histograms_size = 0; |
+ size_t all_histograms_capacity = expected_num_clusters; |
+ HistogramType* all_histograms = |
+ BROTLI_ALLOC(m, HistogramType, all_histograms_capacity); |
+ size_t cluster_size_size = 0; |
+ size_t cluster_size_capacity = expected_num_clusters; |
+ uint32_t* cluster_size = BROTLI_ALLOC(m, uint32_t, cluster_size_capacity); |
+ size_t num_clusters = 0; |
+ HistogramType* histograms = BROTLI_ALLOC(m, HistogramType, |
+ BROTLI_MIN(size_t, num_blocks, HISTOGRAMS_PER_BATCH)); |
+ size_t max_num_pairs = |
+ HISTOGRAMS_PER_BATCH * HISTOGRAMS_PER_BATCH / 2; |
+ size_t pairs_capacity = max_num_pairs + 1; |
+ HistogramPair* pairs = BROTLI_ALLOC(m, HistogramPair, pairs_capacity); |
+ size_t pos = 0; |
+ uint32_t* clusters; |
+ size_t num_final_clusters; |
+ static const uint32_t kInvalidIndex = BROTLI_UINT32_MAX; |
+ uint32_t* new_index; |
+ uint8_t max_type = 0; |
+ size_t i; |
+ uint32_t sizes[HISTOGRAMS_PER_BATCH] = { 0 }; |
+ uint32_t new_clusters[HISTOGRAMS_PER_BATCH] = { 0 }; |
+ uint32_t symbols[HISTOGRAMS_PER_BATCH] = { 0 }; |
+ uint32_t remap[HISTOGRAMS_PER_BATCH] = { 0 }; |
+ |
+ if (BROTLI_IS_OOM(m)) return; |
- size_t block_idx = 0; |
- for (size_t i = 0; i < length; ++i) { |
- assert(block_idx < num_blocks); |
- ++block_lengths[block_idx]; |
- if (i + 1 == length || block_ids[i] != block_ids[i + 1]) { |
- ++block_idx; |
+ memset(block_lengths, 0, num_blocks * sizeof(uint32_t)); |
+ |
+ { |
+ size_t block_idx = 0; |
+ for (i = 0; i < length; ++i) { |
+ assert(block_idx < num_blocks); |
+ ++block_lengths[block_idx]; |
+ if (i + 1 == length || block_ids[i] != block_ids[i + 1]) { |
+ ++block_idx; |
+ } |
} |
+ assert(block_idx == num_blocks); |
} |
- assert(block_idx == num_blocks); |
- const size_t expected_num_clusters = |
- kClustersPerBatch * |
- (num_blocks + kHistogramsPerBatch - 1) / kHistogramsPerBatch; |
- std::vector<HistogramType> all_histograms; |
- std::vector<uint32_t> cluster_size; |
- all_histograms.reserve(expected_num_clusters); |
- cluster_size.reserve(expected_num_clusters); |
- size_t num_clusters = 0; |
- std::vector<HistogramType> histograms( |
- std::min(num_blocks, kHistogramsPerBatch)); |
- size_t max_num_pairs = kHistogramsPerBatch * kHistogramsPerBatch / 2; |
- std::vector<HistogramPair> pairs(max_num_pairs + 1); |
- size_t pos = 0; |
- for (size_t i = 0; i < num_blocks; i += kHistogramsPerBatch) { |
- const size_t num_to_combine = std::min(num_blocks - i, kHistogramsPerBatch); |
- uint32_t sizes[kHistogramsPerBatch]; |
- uint32_t clusters[kHistogramsPerBatch]; |
- uint32_t symbols[kHistogramsPerBatch]; |
- uint32_t remap[kHistogramsPerBatch]; |
- for (size_t j = 0; j < num_to_combine; ++j) { |
- histograms[j].Clear(); |
- for (size_t k = 0; k < block_lengths[i + j]; ++k) { |
- histograms[j].Add(data[pos++]); |
+ for (i = 0; i < num_blocks; i += HISTOGRAMS_PER_BATCH) { |
+ const size_t num_to_combine = |
+ BROTLI_MIN(size_t, num_blocks - i, HISTOGRAMS_PER_BATCH); |
+ size_t num_new_clusters; |
+ size_t j; |
+ for (j = 0; j < num_to_combine; ++j) { |
+ size_t k; |
+ FN(HistogramClear)(&histograms[j]); |
+ for (k = 0; k < block_lengths[i + j]; ++k) { |
+ FN(HistogramAdd)(&histograms[j], data[pos++]); |
} |
- histograms[j].bit_cost_ = PopulationCost(histograms[j]); |
- symbols[j] = clusters[j] = static_cast<uint32_t>(j); |
+ histograms[j].bit_cost_ = FN(BrotliPopulationCost)(&histograms[j]); |
+ new_clusters[j] = (uint32_t)j; |
+ symbols[j] = (uint32_t)j; |
sizes[j] = 1; |
} |
- size_t num_new_clusters = HistogramCombine( |
- &histograms[0], sizes, symbols, clusters, &pairs[0], num_to_combine, |
- num_to_combine, kHistogramsPerBatch, max_num_pairs); |
- for (size_t j = 0; j < num_new_clusters; ++j) { |
- all_histograms.push_back(histograms[clusters[j]]); |
- cluster_size.push_back(sizes[clusters[j]]); |
- remap[clusters[j]] = static_cast<uint32_t>(j); |
+ num_new_clusters = FN(BrotliHistogramCombine)( |
+ histograms, sizes, symbols, new_clusters, pairs, num_to_combine, |
+ num_to_combine, HISTOGRAMS_PER_BATCH, max_num_pairs); |
+ BROTLI_ENSURE_CAPACITY(m, HistogramType, all_histograms, |
+ all_histograms_capacity, all_histograms_size + num_new_clusters); |
+ BROTLI_ENSURE_CAPACITY(m, uint32_t, cluster_size, |
+ cluster_size_capacity, cluster_size_size + num_new_clusters); |
+ if (BROTLI_IS_OOM(m)) return; |
+ for (j = 0; j < num_new_clusters; ++j) { |
+ all_histograms[all_histograms_size++] = histograms[new_clusters[j]]; |
+ cluster_size[cluster_size_size++] = sizes[new_clusters[j]]; |
+ remap[new_clusters[j]] = (uint32_t)j; |
} |
- for (size_t j = 0; j < num_to_combine; ++j) { |
- histogram_symbols[i + j] = |
- static_cast<uint32_t>(num_clusters) + remap[symbols[j]]; |
+ for (j = 0; j < num_to_combine; ++j) { |
+ histogram_symbols[i + j] = (uint32_t)num_clusters + remap[symbols[j]]; |
} |
num_clusters += num_new_clusters; |
- assert(num_clusters == cluster_size.size()); |
- assert(num_clusters == all_histograms.size()); |
+ assert(num_clusters == cluster_size_size); |
+ assert(num_clusters == all_histograms_size); |
} |
+ BROTLI_FREE(m, histograms); |
max_num_pairs = |
- std::min(64 * num_clusters, (num_clusters / 2) * num_clusters); |
- pairs.resize(max_num_pairs + 1); |
+ BROTLI_MIN(size_t, 64 * num_clusters, (num_clusters / 2) * num_clusters); |
+ if (pairs_capacity < max_num_pairs + 1) { |
+ BROTLI_FREE(m, pairs); |
+ pairs = BROTLI_ALLOC(m, HistogramPair, max_num_pairs + 1); |
+ if (BROTLI_IS_OOM(m)) return; |
+ } |
- std::vector<uint32_t> clusters(num_clusters); |
- for (size_t i = 0; i < num_clusters; ++i) { |
- clusters[i] = static_cast<uint32_t>(i); |
+ clusters = BROTLI_ALLOC(m, uint32_t, num_clusters); |
+ if (BROTLI_IS_OOM(m)) return; |
+ for (i = 0; i < num_clusters; ++i) { |
+ clusters[i] = (uint32_t)i; |
} |
- size_t num_final_clusters = |
- HistogramCombine(&all_histograms[0], &cluster_size[0], |
- &histogram_symbols[0], |
- &clusters[0], &pairs[0], num_clusters, |
- num_blocks, kMaxNumberOfBlockTypes, max_num_pairs); |
+ num_final_clusters = FN(BrotliHistogramCombine)( |
+ all_histograms, cluster_size, histogram_symbols, clusters, pairs, |
+ num_clusters, num_blocks, BROTLI_MAX_NUMBER_OF_BLOCK_TYPES, |
+ max_num_pairs); |
+ BROTLI_FREE(m, pairs); |
+ BROTLI_FREE(m, cluster_size); |
- static const uint32_t kInvalidIndex = std::numeric_limits<uint32_t>::max(); |
- std::vector<uint32_t> new_index(num_clusters, kInvalidIndex); |
- uint32_t next_index = 0; |
+ new_index = BROTLI_ALLOC(m, uint32_t, num_clusters); |
+ if (BROTLI_IS_OOM(m)) return; |
+ for (i = 0; i < num_clusters; ++i) new_index[i] = kInvalidIndex; |
pos = 0; |
- for (size_t i = 0; i < num_blocks; ++i) { |
- HistogramType histo; |
- for (size_t j = 0; j < block_lengths[i]; ++j) { |
- histo.Add(data[pos++]); |
- } |
- uint32_t best_out = |
- i == 0 ? histogram_symbols[0] : histogram_symbols[i - 1]; |
- double best_bits = HistogramBitCostDistance( |
- histo, all_histograms[best_out]); |
- for (size_t j = 0; j < num_final_clusters; ++j) { |
- const double cur_bits = HistogramBitCostDistance( |
- histo, all_histograms[clusters[j]]); |
- if (cur_bits < best_bits) { |
- best_bits = cur_bits; |
- best_out = clusters[j]; |
+ { |
+ uint32_t next_index = 0; |
+ for (i = 0; i < num_blocks; ++i) { |
+ HistogramType histo; |
+ size_t j; |
+ uint32_t best_out; |
+ double best_bits; |
+ FN(HistogramClear)(&histo); |
+ for (j = 0; j < block_lengths[i]; ++j) { |
+ FN(HistogramAdd)(&histo, data[pos++]); |
+ } |
+ best_out = (i == 0) ? histogram_symbols[0] : histogram_symbols[i - 1]; |
+ best_bits = |
+ FN(BrotliHistogramBitCostDistance)(&histo, &all_histograms[best_out]); |
+ for (j = 0; j < num_final_clusters; ++j) { |
+ const double cur_bits = FN(BrotliHistogramBitCostDistance)( |
+ &histo, &all_histograms[clusters[j]]); |
+ if (cur_bits < best_bits) { |
+ best_bits = cur_bits; |
+ best_out = clusters[j]; |
+ } |
+ } |
+ histogram_symbols[i] = best_out; |
+ if (new_index[best_out] == kInvalidIndex) { |
+ new_index[best_out] = next_index++; |
} |
- } |
- histogram_symbols[i] = best_out; |
- if (new_index[best_out] == kInvalidIndex) { |
- new_index[best_out] = next_index++; |
} |
} |
- uint8_t max_type = 0; |
- uint32_t cur_length = 0; |
- block_idx = 0; |
- split->types.resize(num_blocks); |
- split->lengths.resize(num_blocks); |
- for (size_t i = 0; i < num_blocks; ++i) { |
- cur_length += block_lengths[i]; |
- if (i + 1 == num_blocks || |
- histogram_symbols[i] != histogram_symbols[i + 1]) { |
- const uint8_t id = static_cast<uint8_t>(new_index[histogram_symbols[i]]); |
- split->types[block_idx] = id; |
- split->lengths[block_idx] = cur_length; |
- max_type = std::max(max_type, id); |
- cur_length = 0; |
- ++block_idx; |
+ BROTLI_FREE(m, clusters); |
+ BROTLI_FREE(m, all_histograms); |
+ BROTLI_ENSURE_CAPACITY( |
+ m, uint8_t, split->types, split->types_alloc_size, num_blocks); |
+ BROTLI_ENSURE_CAPACITY( |
+ m, uint32_t, split->lengths, split->lengths_alloc_size, num_blocks); |
+ if (BROTLI_IS_OOM(m)) return; |
+ { |
+ uint32_t cur_length = 0; |
+ size_t block_idx = 0; |
+ for (i = 0; i < num_blocks; ++i) { |
+ cur_length += block_lengths[i]; |
+ if (i + 1 == num_blocks || |
+ histogram_symbols[i] != histogram_symbols[i + 1]) { |
+ const uint8_t id = (uint8_t)new_index[histogram_symbols[i]]; |
+ split->types[block_idx] = id; |
+ split->lengths[block_idx] = cur_length; |
+ max_type = BROTLI_MAX(uint8_t, max_type, id); |
+ cur_length = 0; |
+ ++block_idx; |
+ } |
} |
+ split->num_blocks = block_idx; |
+ split->num_types = (size_t)max_type + 1; |
} |
- split->types.resize(block_idx); |
- split->lengths.resize(block_idx); |
- split->num_types = static_cast<size_t>(max_type) + 1; |
+ BROTLI_FREE(m, new_index); |
+ BROTLI_FREE(m, block_lengths); |
+ BROTLI_FREE(m, histogram_symbols); |
} |
-template<int kSize, typename DataType> |
-void SplitByteVector(const std::vector<DataType>& data, |
- const size_t literals_per_histogram, |
- const size_t max_histograms, |
- const size_t sampling_stride_length, |
- const double block_switch_cost, |
- BlockSplit* split) { |
- if (data.empty()) { |
+static void FN(SplitByteVector)(MemoryManager* m, |
+ const DataType* data, const size_t length, |
+ const size_t literals_per_histogram, |
+ const size_t max_histograms, |
+ const size_t sampling_stride_length, |
+ const double block_switch_cost, |
+ const BrotliEncoderParams* params, |
+ BlockSplit* split) { |
+ const size_t data_size = FN(HistogramDataSize)(); |
+ size_t num_histograms = length / literals_per_histogram + 1; |
+ HistogramType* histograms; |
+ if (num_histograms > max_histograms) { |
+ num_histograms = max_histograms; |
+ } |
+ if (length == 0) { |
split->num_types = 1; |
return; |
- } else if (data.size() < kMinLengthForBlockSplitting) { |
+ } else if (length < kMinLengthForBlockSplitting) { |
+ BROTLI_ENSURE_CAPACITY(m, uint8_t, |
+ split->types, split->types_alloc_size, split->num_blocks + 1); |
+ BROTLI_ENSURE_CAPACITY(m, uint32_t, |
+ split->lengths, split->lengths_alloc_size, split->num_blocks + 1); |
+ if (BROTLI_IS_OOM(m)) return; |
split->num_types = 1; |
- split->types.push_back(0); |
- split->lengths.push_back(static_cast<uint32_t>(data.size())); |
+ split->types[split->num_blocks] = 0; |
+ split->lengths[split->num_blocks] = (uint32_t)length; |
+ split->num_blocks++; |
return; |
} |
- size_t num_histograms = data.size() / literals_per_histogram + 1; |
- if (num_histograms > max_histograms) { |
- num_histograms = max_histograms; |
- } |
- Histogram<kSize>* histograms = new Histogram<kSize>[num_histograms]; |
- // Find good entropy codes. |
- InitialEntropyCodes(&data[0], data.size(), |
- sampling_stride_length, |
- num_histograms, histograms); |
- RefineEntropyCodes(&data[0], data.size(), |
- sampling_stride_length, |
- num_histograms, histograms); |
- // Find a good path through literals with the good entropy codes. |
- std::vector<uint8_t> block_ids(data.size()); |
- size_t num_blocks; |
- const size_t bitmaplen = (num_histograms + 7) >> 3; |
- double* insert_cost = new double[kSize * num_histograms]; |
- double *cost = new double[num_histograms]; |
- uint8_t* switch_signal = new uint8_t[data.size() * bitmaplen]; |
- uint16_t* new_id = new uint16_t[num_histograms]; |
- for (size_t i = 0; i < 10; ++i) { |
- num_blocks = FindBlocks(&data[0], data.size(), |
- block_switch_cost, |
- num_histograms, histograms, |
- insert_cost, cost, switch_signal, |
- &block_ids[0]); |
- num_histograms = RemapBlockIds(&block_ids[0], data.size(), |
- new_id, num_histograms); |
- BuildBlockHistograms(&data[0], data.size(), &block_ids[0], |
+ histograms = BROTLI_ALLOC(m, HistogramType, num_histograms); |
+ if (BROTLI_IS_OOM(m)) return; |
+ /* Find good entropy codes. */ |
+ FN(InitialEntropyCodes)(data, length, |
+ sampling_stride_length, |
+ num_histograms, histograms); |
+ FN(RefineEntropyCodes)(data, length, |
+ sampling_stride_length, |
num_histograms, histograms); |
- } |
- delete[] insert_cost; |
- delete[] cost; |
- delete[] switch_signal; |
- delete[] new_id; |
- delete[] histograms; |
- ClusterBlocks<Histogram<kSize> >(&data[0], data.size(), num_blocks, |
- &block_ids[0], split); |
-} |
- |
-void SplitBlock(const Command* cmds, |
- const size_t num_commands, |
- const uint8_t* data, |
- const size_t pos, |
- const size_t mask, |
- BlockSplit* literal_split, |
- BlockSplit* insert_and_copy_split, |
- BlockSplit* dist_split) { |
{ |
- // Create a continuous array of literals. |
- std::vector<uint8_t> literals; |
- CopyLiteralsToByteArray(cmds, num_commands, data, pos, mask, &literals); |
- // Create the block split on the array of literals. |
- // Literal histograms have alphabet size 256. |
- SplitByteVector<256>( |
- literals, |
- kSymbolsPerLiteralHistogram, kMaxLiteralHistograms, |
- kLiteralStrideLength, kLiteralBlockSwitchCost, |
- literal_split); |
- } |
- |
- { |
- // Compute prefix codes for commands. |
- std::vector<uint16_t> insert_and_copy_codes(num_commands); |
- for (size_t i = 0; i < num_commands; ++i) { |
- insert_and_copy_codes[i] = cmds[i].cmd_prefix_; |
- } |
- // Create the block split on the array of command prefixes. |
- SplitByteVector<kNumCommandPrefixes>( |
- insert_and_copy_codes, |
- kSymbolsPerCommandHistogram, kMaxCommandHistograms, |
- kCommandStrideLength, kCommandBlockSwitchCost, |
- insert_and_copy_split); |
- } |
- |
- { |
- // Create a continuous array of distance prefixes. |
- std::vector<uint16_t> distance_prefixes(num_commands); |
- size_t pos = 0; |
- for (size_t i = 0; i < num_commands; ++i) { |
- const Command& cmd = cmds[i]; |
- if (cmd.copy_len() && cmd.cmd_prefix_ >= 128) { |
- distance_prefixes[pos++] = cmd.dist_prefix_; |
- } |
+ /* Find a good path through literals with the good entropy codes. */ |
+ uint8_t* block_ids = BROTLI_ALLOC(m, uint8_t, length); |
+ size_t num_blocks = 0; |
+ const size_t bitmaplen = (num_histograms + 7) >> 3; |
+ double* insert_cost = BROTLI_ALLOC(m, double, data_size * num_histograms); |
+ double* cost = BROTLI_ALLOC(m, double, num_histograms); |
+ uint8_t* switch_signal = BROTLI_ALLOC(m, uint8_t, length * bitmaplen); |
+ uint16_t* new_id = BROTLI_ALLOC(m, uint16_t, num_histograms); |
+ const size_t iters = params->quality < HQ_ZOPFLIFICATION_QUALITY ? 3 : 10; |
+ size_t i; |
+ if (BROTLI_IS_OOM(m)) return; |
+ for (i = 0; i < iters; ++i) { |
+ num_blocks = FN(FindBlocks)(data, length, |
+ block_switch_cost, |
+ num_histograms, histograms, |
+ insert_cost, cost, switch_signal, |
+ block_ids); |
+ num_histograms = FN(RemapBlockIds)(block_ids, length, |
+ new_id, num_histograms); |
+ FN(BuildBlockHistograms)(data, length, block_ids, |
+ num_histograms, histograms); |
} |
- distance_prefixes.resize(pos); |
- // Create the block split on the array of distance prefixes. |
- SplitByteVector<kNumDistancePrefixes>( |
- distance_prefixes, |
- kSymbolsPerDistanceHistogram, kMaxCommandHistograms, |
- kCommandStrideLength, kDistanceBlockSwitchCost, |
- dist_split); |
+ BROTLI_FREE(m, insert_cost); |
+ BROTLI_FREE(m, cost); |
+ BROTLI_FREE(m, switch_signal); |
+ BROTLI_FREE(m, new_id); |
+ BROTLI_FREE(m, histograms); |
+ FN(ClusterBlocks)(m, data, length, num_blocks, block_ids, split); |
+ if (BROTLI_IS_OOM(m)) return; |
+ BROTLI_FREE(m, block_ids); |
} |
} |
-} // namespace brotli |
+#undef HistogramType |