Differential D9642 Diff 31357 extern/draco/draco/src/draco/compression/entropy/rans_symbol_encoder.h
Changeset View
Changeset View
Standalone View
Standalone View
extern/draco/draco/src/draco/compression/entropy/rans_symbol_encoder.h
- This file was moved from extern/draco/dracoenc/src/draco/compression/entropy/rans_symbol_encoder.h.
| Show First 20 Lines • Show All 85 Lines • ▼ Show 20 Lines | |||||
| template <int unique_symbols_bit_length_t> | template <int unique_symbols_bit_length_t> | ||||
| bool RAnsSymbolEncoder<unique_symbols_bit_length_t>::Create( | bool RAnsSymbolEncoder<unique_symbols_bit_length_t>::Create( | ||||
| const uint64_t *frequencies, int num_symbols, EncoderBuffer *buffer) { | const uint64_t *frequencies, int num_symbols, EncoderBuffer *buffer) { | ||||
| // Compute the total of the input frequencies. | // Compute the total of the input frequencies. | ||||
| uint64_t total_freq = 0; | uint64_t total_freq = 0; | ||||
| int max_valid_symbol = 0; | int max_valid_symbol = 0; | ||||
| for (int i = 0; i < num_symbols; ++i) { | for (int i = 0; i < num_symbols; ++i) { | ||||
| total_freq += frequencies[i]; | total_freq += frequencies[i]; | ||||
| if (frequencies[i] > 0) | if (frequencies[i] > 0) { | ||||
| max_valid_symbol = i; | max_valid_symbol = i; | ||||
| } | } | ||||
| } | |||||
| num_symbols = max_valid_symbol + 1; | num_symbols = max_valid_symbol + 1; | ||||
| num_symbols_ = num_symbols; | num_symbols_ = num_symbols; | ||||
| probability_table_.resize(num_symbols); | probability_table_.resize(num_symbols); | ||||
| const double total_freq_d = static_cast<double>(total_freq); | const double total_freq_d = static_cast<double>(total_freq); | ||||
| const double rans_precision_d = static_cast<double>(rans_precision_); | const double rans_precision_d = static_cast<double>(rans_precision_); | ||||
| // Compute probabilities by rescaling the normalized frequencies into interval | // Compute probabilities by rescaling the normalized frequencies into interval | ||||
| // [1, rans_precision - 1]. The total probability needs to be equal to | // [1, rans_precision - 1]. The total probability needs to be equal to | ||||
| // rans_precision. | // rans_precision. | ||||
| int total_rans_prob = 0; | int total_rans_prob = 0; | ||||
| for (int i = 0; i < num_symbols; ++i) { | for (int i = 0; i < num_symbols; ++i) { | ||||
| const uint64_t freq = frequencies[i]; | const uint64_t freq = frequencies[i]; | ||||
| // Normalized probability. | // Normalized probability. | ||||
| const double prob = static_cast<double>(freq) / total_freq_d; | const double prob = static_cast<double>(freq) / total_freq_d; | ||||
| // RAns probability in range of [1, rans_precision - 1]. | // RAns probability in range of [1, rans_precision - 1]. | ||||
| uint32_t rans_prob = static_cast<uint32_t>(prob * rans_precision_d + 0.5f); | uint32_t rans_prob = static_cast<uint32_t>(prob * rans_precision_d + 0.5f); | ||||
| if (rans_prob == 0 && freq > 0) | if (rans_prob == 0 && freq > 0) { | ||||
| rans_prob = 1; | rans_prob = 1; | ||||
| } | |||||
| probability_table_[i].prob = rans_prob; | probability_table_[i].prob = rans_prob; | ||||
| total_rans_prob += rans_prob; | total_rans_prob += rans_prob; | ||||
| } | } | ||||
| // Because of rounding errors, the total precision may not be exactly accurate | // Because of rounding errors, the total precision may not be exactly accurate | ||||
| // and we may need to adjust the entries a little bit. | // and we may need to adjust the entries a little bit. | ||||
| if (total_rans_prob != rans_precision_) { | if (total_rans_prob != rans_precision_) { | ||||
| std::vector<int> sorted_probabilities(num_symbols); | std::vector<int> sorted_probabilities(num_symbols); | ||||
| for (int i = 0; i < num_symbols; ++i) { | for (int i = 0; i < num_symbols; ++i) { | ||||
| Show All 11 Lines | if (total_rans_prob < rans_precision_) { | ||||
| // Rescale the probabilities of all symbols. | // Rescale the probabilities of all symbols. | ||||
| int32_t error = total_rans_prob - rans_precision_; | int32_t error = total_rans_prob - rans_precision_; | ||||
| while (error > 0) { | while (error > 0) { | ||||
| const double act_total_prob_d = static_cast<double>(total_rans_prob); | const double act_total_prob_d = static_cast<double>(total_rans_prob); | ||||
| const double act_rel_error_d = rans_precision_d / act_total_prob_d; | const double act_rel_error_d = rans_precision_d / act_total_prob_d; | ||||
| for (int j = num_symbols - 1; j > 0; --j) { | for (int j = num_symbols - 1; j > 0; --j) { | ||||
| int symbol_id = sorted_probabilities[j]; | int symbol_id = sorted_probabilities[j]; | ||||
| if (probability_table_[symbol_id].prob <= 1) { | if (probability_table_[symbol_id].prob <= 1) { | ||||
| if (j == num_symbols - 1) | if (j == num_symbols - 1) { | ||||
| return false; // Most frequent symbol would be empty. | return false; // Most frequent symbol would be empty. | ||||
| } | |||||
| break; | break; | ||||
| } | } | ||||
| const int32_t new_prob = static_cast<int32_t>( | const int32_t new_prob = static_cast<int32_t>( | ||||
| floor(act_rel_error_d * | floor(act_rel_error_d * | ||||
| static_cast<double>(probability_table_[symbol_id].prob))); | static_cast<double>(probability_table_[symbol_id].prob))); | ||||
| int32_t fix = probability_table_[symbol_id].prob - new_prob; | int32_t fix = probability_table_[symbol_id].prob - new_prob; | ||||
| if (fix == 0u) | if (fix == 0u) { | ||||
| fix = 1; | fix = 1; | ||||
| if (fix >= static_cast<int32_t>(probability_table_[symbol_id].prob)) | } | ||||
| if (fix >= static_cast<int32_t>(probability_table_[symbol_id].prob)) { | |||||
| fix = probability_table_[symbol_id].prob - 1; | fix = probability_table_[symbol_id].prob - 1; | ||||
| if (fix > error) | } | ||||
| if (fix > error) { | |||||
| fix = error; | fix = error; | ||||
| } | |||||
| probability_table_[symbol_id].prob -= fix; | probability_table_[symbol_id].prob -= fix; | ||||
| total_rans_prob -= fix; | total_rans_prob -= fix; | ||||
| error -= fix; | error -= fix; | ||||
| if (total_rans_prob == rans_precision_) | if (total_rans_prob == rans_precision_) { | ||||
| break; | break; | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| } | |||||
| // Compute the cumulative probability (cdf). | // Compute the cumulative probability (cdf). | ||||
| uint32_t total_prob = 0; | uint32_t total_prob = 0; | ||||
| for (int i = 0; i < num_symbols; ++i) { | for (int i = 0; i < num_symbols; ++i) { | ||||
| probability_table_[i].cum_prob = total_prob; | probability_table_[i].cum_prob = total_prob; | ||||
| total_prob += probability_table_[i].prob; | total_prob += probability_table_[i].prob; | ||||
| } | } | ||||
| if (total_prob != rans_precision_) | if (total_prob != rans_precision_) { | ||||
| return false; | return false; | ||||
| } | |||||
| // Estimate the number of bits needed to encode the input. | // Estimate the number of bits needed to encode the input. | ||||
| // From Shannon entropy the total number of bits N is: | // From Shannon entropy the total number of bits N is: | ||||
| // N = -sum{i : all_symbols}(F(i) * log2(P(i))) | // N = -sum{i : all_symbols}(F(i) * log2(P(i))) | ||||
| // where P(i) is the normalized probability of symbol i and F(i) is the | // where P(i) is the normalized probability of symbol i and F(i) is the | ||||
| // symbol's frequency in the input data. | // symbol's frequency in the input data. | ||||
| double num_bits = 0; | double num_bits = 0; | ||||
| for (int i = 0; i < num_symbols; ++i) { | for (int i = 0; i < num_symbols; ++i) { | ||||
| if (probability_table_[i].prob == 0) | if (probability_table_[i].prob == 0) { | ||||
| continue; | continue; | ||||
| } | |||||
| const double norm_prob = | const double norm_prob = | ||||
| static_cast<double>(probability_table_[i].prob) / rans_precision_d; | static_cast<double>(probability_table_[i].prob) / rans_precision_d; | ||||
| num_bits += static_cast<double>(frequencies[i]) * log2(norm_prob); | num_bits += static_cast<double>(frequencies[i]) * log2(norm_prob); | ||||
| } | } | ||||
| num_expected_bits_ = static_cast<uint64_t>(ceil(-num_bits)); | num_expected_bits_ = static_cast<uint64_t>(ceil(-num_bits)); | ||||
| if (!EncodeTable(buffer)) | if (!EncodeTable(buffer)) { | ||||
| return false; | return false; | ||||
| } | |||||
| return true; | return true; | ||||
| } | } | ||||
| template <int unique_symbols_bit_length_t> | template <int unique_symbols_bit_length_t> | ||||
| bool RAnsSymbolEncoder<unique_symbols_bit_length_t>::EncodeTable( | bool RAnsSymbolEncoder<unique_symbols_bit_length_t>::EncodeTable( | ||||
| EncoderBuffer *buffer) { | EncoderBuffer *buffer) { | ||||
| EncodeVarint(num_symbols_, buffer); | EncodeVarint(num_symbols_, buffer); | ||||
| // Use varint encoding for the probabilities (first two bits represent the | // Use varint encoding for the probabilities (first two bits represent the | ||||
| ▲ Show 20 Lines • Show All 81 Lines • Show Last 20 Lines | |||||