View difference between Paste ID: D0PLGmGu and Unap8Vbz
SHOW: | | - or go back to the newest paste.
1
// Using FastAC by Amir Said -- http://www.cipr.rpi.edu/research/SPIHT/EW_Code/FastAC.zip
2
#include "arithmetic_codec.h"
3
4
#include <boost/random/mersenne_twister.hpp>
5
#include <boost/random/laplace_distribution.hpp>
6
7
#include <vector>
8
9
std::size_t const N_VAL(1 << 20);
10
11
// ============================================================================
12
// Generate some random data with distribution similar to what's in the question
13
14
std::vector<int32_t> gen_data(std::size_t n)
15
{
16
    boost::random::mt19937 rng;
17
    boost::random::laplace_distribution<> dist(0, 20);
18
19
    std::vector<int32_t> data;
20
    data.reserve(n);
21
22
    for (; data.size() < n;) {
23
        int32_t v = static_cast<int32_t>(std::round(dist(rng)));
24
        if ((v >= -256) && (v <= 255)) {
25
            data.push_back(v);
26
        }
27
    }
28
29
    return data;
30
}
31
32
// ============================================================================
33
// Ziz-Zag Coding
34
//
35
// Maps signed integers into unsigned integers
36
// 0 => 0, -1 => 1, 1 => 2, -2 => 3, 2 => 4 ...
37
38
uint32_t zigzag_encode(int32_t v)
39
{
40
    return static_cast<uint32_t>((v >> 31) ^ (v << 1));
41
}
42
43
std::vector<uint32_t> zigzag_encode(std::vector<int32_t> const& data)
44
{
45
    std::vector<uint32_t> result(data.size());
46
    std::transform(data.begin(), data.end(), result.begin(),
47
        [](int32_t v) -> uint32_t { return zigzag_encode(v); });
48
    return result;
49
}
50
51
int32_t zigzag_decode(uint32_t v)
52
{
53
    return (static_cast<int32_t>(v) >> 1) ^ -(static_cast<int32_t>(v)& 1);
54
}
55
56
std::vector<int32_t> zigzag_decode(std::vector<uint32_t> const& data)
57
{
58
    std::vector<int32_t> result(data.size());
59
    std::transform(data.begin(), data.end(), result.begin(),
60
        [](uint32_t v) -> int32_t { return zigzag_decode(v); });
61
    return result;
62
}
63
64
// ============================================================================
65
// Simple approach with 1 adaptive model for 512 symbols
66
// Processes zig-zag coded 9-bit values
67
68
template<typename ModelT, typename CodecT = Arithmetic_Codec>
69
uint32_t encode(std::vector<uint32_t> const& buffer
70
    , ModelT& model
71
    , CodecT& encoder)
72
{
73
    encoder.start_encoder();
74
    for (uint32_t v : buffer) {
75
        encoder.encode(v, model);
76
    }
77
    return 8 * encoder.stop_encoder();
78
}
79
80
template<typename ModelT, typename CodecT = Arithmetic_Codec>
81
void decode(std::vector<uint32_t>& buffer
82
    , ModelT& model
83
    , CodecT& decoder)
84
{
85
    decoder.start_decoder();
86
    for (uint32_t i(0); i < buffer.size(); ++i) {
87
        buffer[i] = decoder.decode(model);
88
    }
89
    decoder.stop_decoder();
90
}
91
92
void test_simple(std::vector<uint32_t> const& zdata)
93
{
94
    Arithmetic_Codec codec(N_VAL * 2);
95
    Adaptive_Data_Model adaptive_model(512);
96
97
    std::size_t raw_size_bits(N_VAL * 9);
98
    std::size_t packed_size_bits(encode(zdata, adaptive_model, codec));
99
    double ratio(double(packed_size_bits) / raw_size_bits * 100);
100
    std::cout << "Ratio = " << ratio << " %\n";
101
102
    std::vector<uint32_t> dzdata(N_VAL);
103
104
    adaptive_model.reset();
105
106
    decode(dzdata, adaptive_model, codec);
107
108
    std::cout << "Match = " << ((zdata == dzdata) ? "true" : "false") << "\n";
109
}
110
111
// ============================================================================
112
// Split approach with 3 adaptive models (1*2 and 2*256 symbols)
113
// Processes zig-zag coded 9-bit values
114
//
115
// First the MSB is coded using the 2 symbol model_msb
116
// If MSB == 0 then LSB is coded using the 256 symbold model_lsb0
117
// If MSB == 1 then LSB is coded using the 256 symbold model_lsb1
118
119
template<typename ModelT, typename CodecT = Arithmetic_Codec>
120
uint32_t encode(std::vector<uint32_t> const& buffer
121
    , ModelT& model_msb
122
    , ModelT& model_lsb0
123
    , ModelT& model_lsb1
124
    , CodecT& encoder)
125
{
126
    encoder.start_encoder();
127
    for (uint32_t v : buffer) {
128
        uint32_t msb(v >> 8);
129
        uint32_t lsb(v & 0xFF);
130
131
        encoder.encode(msb, model_msb);
132
        if (msb == 0) {
133
            encoder.encode(lsb, model_lsb0);
134
        } else {
135
            encoder.encode(lsb, model_lsb1);
136
        }
137
    }
138
    return 8 * encoder.stop_encoder();
139
}
140
141
template<typename ModelT, typename CodecT = Arithmetic_Codec>
142
void decode(std::vector<uint32_t>& buffer
143
    , ModelT& model_msb
144
    , ModelT& model_lsb0
145
    , ModelT& model_lsb1
146
    , CodecT& decoder)
147
{
148
    decoder.start_decoder();
149
    for (uint32_t i(0); i < buffer.size(); ++i) {
150
        uint32_t msb(decoder.decode(model_msb));
151
        uint32_t lsb;
152
        if (msb == 0) {
153
            lsb = decoder.decode(model_lsb0);
154
        } else {
155
            lsb = decoder.decode(model_lsb1);
156
        }
157
        buffer[i] = (msb << 8) | lsb;
158
    }
159
    decoder.stop_decoder();
160
}
161
162
void test_split(std::vector<uint32_t> const& zdata)
163
{
164
165
    Arithmetic_Codec codec(N_VAL * 2);
166
    Adaptive_Data_Model adaptive_model_msb(2);
167
    Adaptive_Data_Model adaptive_model_lsb0(256);
168
    Adaptive_Data_Model adaptive_model_lsb1(256);
169
170
    std::size_t raw_size_bits(N_VAL * 9);
171
    std::size_t packed_size_bits(encode(zdata, adaptive_model_msb
172
        , adaptive_model_lsb0, adaptive_model_lsb1, codec));
173
    double ratio(double(packed_size_bits) / raw_size_bits * 100);
174
    std::cout << "Ratio = " << ratio << " %\n";
175
176
    std::vector<uint32_t> dzdata(N_VAL);
177
178
    adaptive_model_msb.reset();
179
    adaptive_model_lsb0.reset();
180
    adaptive_model_lsb1.reset();
181
182
    decode(dzdata, adaptive_model_msb
183
        , adaptive_model_lsb0, adaptive_model_lsb1, codec);
184
185
    std::cout << "Match = " << ((zdata == dzdata) ? "true" : "false") << "\n";
186
}
187
188
// ============================================================================
189
// PN approach with 3 adaptive models (1*2 and 2*256 symbols)
190
// Processes signed 9-bit values
191
//
192
// First the sign is coded using the 2 symbol model_sign
193
// If sign positive then abs value is coded using the 256 symbol model_valuep
194
// If sign negative then abs value - 1 is coded using the 256 symbol model_valuen
195
196
template<typename ModelT, typename CodecT = Arithmetic_Codec>
197
uint32_t encode(std::vector<int32_t> const& buffer
198
    , ModelT& model_sign
199
    , ModelT& model_valuep
200
    , ModelT& model_valuen
201
    , CodecT& encoder)
202
{
203
    encoder.start_encoder();
204
    for (int32_t v : buffer) {
205
        uint32_t sign, value;
206
        if (v >= 0) {
207
            sign = 0;
208
            value = v;
209
        } else {
210
            sign = 1;
211
            value = std::abs(v) - 1;
212
        }
213
214
        encoder.encode(sign, model_sign);
215
        if (sign == 0) {
216
            encoder.encode(value, model_valuep);
217
        } else {
218
            encoder.encode(value, model_valuen);
219
        }
220
    }
221
    return 8 * encoder.stop_encoder();
222
}
223
224
template<typename ModelT, typename CodecT = Arithmetic_Codec>
225
void decode(std::vector<int32_t>& buffer
226
    , ModelT& model_sign
227
    , ModelT& model_valuep
228
    , ModelT& model_valuen
229
    , CodecT& decoder)
230
{
231
    decoder.start_decoder();
232
    for (uint32_t i(0); i < buffer.size(); ++i) {
233
        uint32_t sign(decoder.decode(model_sign));
234
        int32_t value;
235
        if (sign == 0) {
236
            value = decoder.decode(model_valuep);
237
            buffer[i] = value;
238
        } else {
239
            value = decoder.decode(model_valuen);
240
            buffer[i] = -(value + 1);
241
        }
242
    }
243
    decoder.stop_decoder();
244
}
245
246
void test_split_pn(std::vector<int32_t> const& data)
247
{
248
249
    Arithmetic_Codec codec(N_VAL * 2);
250
    Adaptive_Data_Model adaptive_model_sign(2);
251
    Adaptive_Data_Model adaptive_model_valuep(256);
252
    Adaptive_Data_Model adaptive_model_valuen(256);
253
254
    std::size_t raw_size_bits(N_VAL * 9);
255
    std::size_t packed_size_bits(encode(data, adaptive_model_sign
256
        , adaptive_model_valuep, adaptive_model_valuen, codec));
257
    double ratio(double(packed_size_bits) / raw_size_bits * 100);
258
    std::cout << "Ratio = " << ratio << " %\n";
259
260
    std::vector<int32_t> ddata(N_VAL);
261
262
    adaptive_model_sign.reset();
263
    adaptive_model_valuep.reset();
264
    adaptive_model_valuen.reset();
265
266
    decode(ddata, adaptive_model_sign
267
        , adaptive_model_valuep, adaptive_model_valuen, codec);
268
269
    std::cout << "Match = " << ((data == ddata) ? "true" : "false") << "\n";
270
}
271
272
// ============================================================================
273
274
int main()
275
{
276
    std::vector<int32_t> data(gen_data(N_VAL));
277
    std::vector<uint32_t> zdata(zigzag_encode(data));
278
279
    test_simple(zdata);
280
    test_split(zdata);
281
    test_split_pn(data);
282
283
    return 0;
284
}
285
286
// ============================================================================