1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
// Copyright (c) the JPEG XL Project Authors. All rights reserved.
//
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
#ifndef LIB_JXL_ENC_ANS_H_
#define LIB_JXL_ENC_ANS_H_
// Library to encode the ANS population counts to the bit-stream and encode
// symbols based on the respective distributions.
#include <cstddef>
#include <cstdint>
#include <vector>
#include "lib/jxl/ans_params.h"
#include "lib/jxl/dec_ans.h"
#include "lib/jxl/enc_ans_params.h"
#include "lib/jxl/enc_bit_writer.h"
namespace jxl {
struct AuxOut;
#define USE_MULT_BY_RECIPROCAL
// precision must be equal to: #bits(state_) + #bits(freq)
#define RECIPROCAL_PRECISION (32 + ANS_LOG_TAB_SIZE)
// Data structure representing one element of the encoding table built
// from a distribution.
// TODO(veluca): split this up, or use an union.
struct ANSEncSymbolInfo {
// ANS
uint16_t freq_;
std::vector<uint16_t> reverse_map_;
#ifdef USE_MULT_BY_RECIPROCAL
uint64_t ifreq_;
#endif
// Prefix coding.
uint8_t depth;
uint16_t bits;
};
class ANSCoder {
public:
ANSCoder() : state_(ANS_SIGNATURE << 16) {}
uint32_t PutSymbol(const ANSEncSymbolInfo& t, uint8_t* nbits) {
uint32_t bits = 0;
*nbits = 0;
if ((state_ >> (32 - ANS_LOG_TAB_SIZE)) >= t.freq_) {
bits = state_ & 0xffff;
state_ >>= 16;
*nbits = 16;
}
#ifdef USE_MULT_BY_RECIPROCAL
// We use mult-by-reciprocal trick, but that requires 64b calc.
const uint32_t v = (state_ * t.ifreq_) >> RECIPROCAL_PRECISION;
const uint32_t offset = t.reverse_map_[state_ - v * t.freq_];
state_ = (v << ANS_LOG_TAB_SIZE) + offset;
#else
state_ = ((state_ / t.freq_) << ANS_LOG_TAB_SIZE) +
t.reverse_map_[state_ % t.freq_];
#endif
return bits;
}
uint32_t GetState() const { return state_; }
private:
uint32_t state_;
};
static const int kNumFixedHistograms = 1;
struct EntropyEncodingData {
std::vector<std::vector<ANSEncSymbolInfo>> encoding_info;
bool use_prefix_code;
std::vector<HybridUintConfig> uint_config;
LZ77Params lz77;
std::vector<BitWriter> encoded_histograms;
};
// Integer to be encoded by an entropy coder, either ANS or Huffman.
struct Token {
Token() {}
Token(uint32_t c, uint32_t value)
: is_lz77_length(false), context(c), value(value) {}
uint32_t is_lz77_length : 1;
uint32_t context : 31;
uint32_t value;
};
// Returns an estimate of the number of bits required to encode the given
// histogram (header bits plus data bits).
float ANSPopulationCost(const ANSHistBin* data, size_t alphabet_size);
// Writes the context map to the bitstream and concatenates the individual
// histogram bistreams in codes.encoded_histograms. Used in streaming mode.
void EncodeHistograms(const std::vector<uint8_t>& context_map,
const EntropyEncodingData& codes, BitWriter* writer,
size_t layer, AuxOut* aux_out);
// Apply context clustering, compute histograms and encode them. Returns an
// estimate of the total bits used for encoding the stream. If `writer` ==
// nullptr, the bit estimate will not take into account the context map (which
// does not get written if `num_contexts` == 1).
size_t BuildAndEncodeHistograms(const HistogramParams& params,
size_t num_contexts,
std::vector<std::vector<Token>>& tokens,
EntropyEncodingData* codes,
std::vector<uint8_t>* context_map,
BitWriter* writer, size_t layer,
AuxOut* aux_out);
// Write the tokens to a string.
void WriteTokens(const std::vector<Token>& tokens,
const EntropyEncodingData& codes,
const std::vector<uint8_t>& context_map, size_t context_offset,
BitWriter* writer, size_t layer, AuxOut* aux_out);
// Same as above, but assumes allotment created by caller.
size_t WriteTokens(const std::vector<Token>& tokens,
const EntropyEncodingData& codes,
const std::vector<uint8_t>& context_map,
size_t context_offset, BitWriter* writer);
// Exposed for tests; to be used with Writer=BitWriter only.
template <typename Writer>
void EncodeUintConfigs(const std::vector<HybridUintConfig>& uint_config,
Writer* writer, size_t log_alpha_size);
extern template void EncodeUintConfigs(const std::vector<HybridUintConfig>&,
BitWriter*, size_t);
// Globally set the option to create fuzzer-friendly ANS streams. Negatively
// impacts compression. Not thread-safe.
void SetANSFuzzerFriendly(bool ans_fuzzer_friendly);
} // namespace jxl
#endif // LIB_JXL_ENC_ANS_H_
|
