11 // This is just the sample program. All the meat is in rans_byte.h.
13 static void panic(const char *fmt, ...)
18 fputs("Error: ", stderr);
19 vfprintf(stderr, fmt, arg);
26 static uint8_t* read_file(char const* filename, size_t* out_size)
28 FILE* f = fopen(filename, "rb");
30 panic("file not found: %s\n", filename);
32 fseek(f, 0, SEEK_END);
33 size_t size = ftell(f);
34 fseek(f, 0, SEEK_SET);
36 uint8_t* buf = new uint8_t[size];
37 if (fread(buf, size, 1, f) != 1)
38 panic("read failed\n");
52 uint32_t cum_freqs[257];
54 void count_freqs(uint8_t const* in, size_t nbytes);
55 void calc_cum_freqs();
56 void normalize_freqs(uint32_t target_total);
59 void SymbolStats::count_freqs(uint8_t const* in, size_t nbytes)
61 for (int i=0; i < 256; i++)
64 for (size_t i=0; i < nbytes; i++)
68 void SymbolStats::calc_cum_freqs()
71 for (int i=0; i < 256; i++)
72 cum_freqs[i+1] = cum_freqs[i] + freqs[i];
75 void SymbolStats::normalize_freqs(uint32_t target_total)
77 assert(target_total >= 256);
80 uint32_t cur_total = cum_freqs[256];
82 // resample distribution based on cumulative freqs
83 for (int i = 1; i <= 256; i++)
84 cum_freqs[i] = ((uint64_t)target_total * cum_freqs[i])/cur_total;
86 // if we nuked any non-0 frequency symbol to 0, we need to steal
87 // the range to make the frequency nonzero from elsewhere.
89 // this is not at all optimal, i'm just doing the first thing that comes to mind.
90 for (int i=0; i < 256; i++) {
91 if (freqs[i] && cum_freqs[i+1] == cum_freqs[i]) {
92 // symbol i was set to zero freq
94 // find best symbol to steal frequency from (try to steal from low-freq ones)
95 uint32_t best_freq = ~0u;
97 for (int j=0; j < 256; j++) {
98 uint32_t freq = cum_freqs[j+1] - cum_freqs[j];
99 if (freq > 1 && freq < best_freq) {
104 assert(best_steal != -1);
106 // and steal from it!
107 if (best_steal < i) {
108 for (int j = best_steal + 1; j <= i; j++)
111 assert(best_steal > i);
112 for (int j = i + 1; j <= best_steal; j++)
118 // calculate updated freqs and make sure we didn't screw anything up
119 assert(cum_freqs[0] == 0 && cum_freqs[256] == target_total);
120 for (int i=0; i < 256; i++) {
122 assert(cum_freqs[i+1] == cum_freqs[i]);
124 assert(cum_freqs[i+1] > cum_freqs[i]);
127 freqs[i] = cum_freqs[i+1] - cum_freqs[i];
134 uint8_t* in_bytes = read_file("book1", &in_size);
136 static const uint32_t prob_bits = 14;
137 static const uint32_t prob_scale = 1 << prob_bits;
140 stats.count_freqs(in_bytes, in_size);
141 stats.normalize_freqs(prob_scale);
143 // cumlative->symbol table
144 // this is super brute force
145 uint8_t cum2sym[prob_scale];
146 for (int s=0; s < 256; s++)
147 for (uint32_t i=stats.cum_freqs[s]; i < stats.cum_freqs[s+1]; i++)
150 static size_t out_max_size = 32<<20; // 32MB
151 static size_t out_max_elems = out_max_size / sizeof(uint32_t);
152 uint32_t* out_buf = new uint32_t[out_max_elems];
153 uint32_t* out_end = out_buf + out_max_elems;
154 uint8_t* dec_bytes = new uint8_t[in_size];
157 uint32_t *rans_begin;
158 Rans64EncSymbol esyms[256];
159 Rans64DecSymbol dsyms[256];
161 for (int i=0; i < 256; i++) {
162 Rans64EncSymbolInit(&esyms[i], stats.cum_freqs[i], stats.freqs[i], prob_bits);
163 Rans64DecSymbolInit(&dsyms[i], stats.cum_freqs[i], stats.freqs[i]);
166 // ---- regular rANS encode/decode. Typical usage.
168 memset(dec_bytes, 0xcc, in_size);
170 printf("rANS encode:\n");
171 for (int run=0; run < 5; run++) {
172 double start_time = timer();
173 uint64_t enc_start_time = __rdtsc();
176 Rans64EncInit(&rans);
178 uint32_t* ptr = out_end; // *end* of output buffer
179 for (size_t i=in_size; i > 0; i--) { // NB: working in reverse!
180 int s = in_bytes[i-1];
181 Rans64EncPutSymbol(&rans, &ptr, &esyms[s], prob_bits);
183 Rans64EncFlush(&rans, &ptr);
186 uint64_t enc_clocks = __rdtsc() - enc_start_time;
187 double enc_time = timer() - start_time;
188 printf("%"PRIu64" clocks, %.1f clocks/symbol (%5.1fMiB/s)\n", enc_clocks, 1.0 * enc_clocks / in_size, 1.0 * in_size / (enc_time * 1048576.0));
190 printf("rANS: %d bytes\n", (int) ((out_end - rans_begin) * sizeof(uint32_t)));
193 for (int run=0; run < 5; run++) {
194 double start_time = timer();
195 uint64_t dec_start_time = __rdtsc();
198 uint32_t* ptr = rans_begin;
199 Rans64DecInit(&rans, &ptr);
201 for (size_t i=0; i < in_size; i++) {
202 uint32_t s = cum2sym[Rans64DecGet(&rans, prob_bits)];
203 dec_bytes[i] = (uint8_t) s;
204 Rans64DecAdvanceSymbol(&rans, &ptr, &dsyms[s], prob_bits);
207 uint64_t dec_clocks = __rdtsc() - dec_start_time;
208 double dec_time = timer() - start_time;
209 printf("%"PRIu64" clocks, %.1f clocks/symbol (%5.1fMiB/s)\n", dec_clocks, 1.0 * dec_clocks / in_size, 1.0 * in_size / (dec_time * 1048576.0));
212 // check decode results
213 if (memcmp(in_bytes, dec_bytes, in_size) == 0)
214 printf("decode ok!\n");
216 printf("ERROR: bad decoder!\n");
218 // ---- interleaved rANS encode/decode. This is the kind of thing you might do to optimize critical paths.
220 memset(dec_bytes, 0xcc, in_size);
222 // try interleaved rANS encode
223 printf("\ninterleaved rANS encode:\n");
224 for (int run=0; run < 5; run++) {
225 double start_time = timer();
226 uint64_t enc_start_time = __rdtsc();
228 Rans64State rans0, rans1;
229 Rans64EncInit(&rans0);
230 Rans64EncInit(&rans1);
232 uint32_t* ptr = out_end;
234 // odd number of bytes?
236 int s = in_bytes[in_size - 1];
237 Rans64EncPutSymbol(&rans0, &ptr, &esyms[s], prob_bits);
240 for (size_t i=(in_size & ~1); i > 0; i -= 2) { // NB: working in reverse!
241 int s1 = in_bytes[i-1];
242 int s0 = in_bytes[i-2];
243 Rans64EncPutSymbol(&rans1, &ptr, &esyms[s1], prob_bits);
244 Rans64EncPutSymbol(&rans0, &ptr, &esyms[s0], prob_bits);
246 Rans64EncFlush(&rans1, &ptr);
247 Rans64EncFlush(&rans0, &ptr);
250 uint64_t enc_clocks = __rdtsc() - enc_start_time;
251 double enc_time = timer() - start_time;
252 printf("%"PRIu64" clocks, %.1f clocks/symbol (%5.1fMiB/s)\n", enc_clocks, 1.0 * enc_clocks / in_size, 1.0 * in_size / (enc_time * 1048576.0));
254 printf("interleaved rANS: %d bytes\n", (int) ((out_end - rans_begin) * sizeof(uint32_t)));
256 // try interleaved rANS decode
257 for (int run=0; run < 5; run++) {
258 double start_time = timer();
259 uint64_t dec_start_time = __rdtsc();
261 Rans64State rans0, rans1;
262 uint32_t* ptr = rans_begin;
263 Rans64DecInit(&rans0, &ptr);
264 Rans64DecInit(&rans1, &ptr);
266 for (size_t i=0; i < (in_size & ~1); i += 2) {
267 uint32_t s0 = cum2sym[Rans64DecGet(&rans0, prob_bits)];
268 uint32_t s1 = cum2sym[Rans64DecGet(&rans1, prob_bits)];
269 dec_bytes[i+0] = (uint8_t) s0;
270 dec_bytes[i+1] = (uint8_t) s1;
271 Rans64DecAdvanceSymbolStep(&rans0, &dsyms[s0], prob_bits);
272 Rans64DecAdvanceSymbolStep(&rans1, &dsyms[s1], prob_bits);
273 Rans64DecRenorm(&rans0, &ptr);
274 Rans64DecRenorm(&rans1, &ptr);
277 // last byte, if number of bytes was odd
279 uint32_t s0 = cum2sym[Rans64DecGet(&rans0, prob_bits)];
280 dec_bytes[in_size - 1] = (uint8_t) s0;
281 Rans64DecAdvanceSymbol(&rans0, &ptr, &dsyms[s0], prob_bits);
284 uint64_t dec_clocks = __rdtsc() - dec_start_time;
285 double dec_time = timer() - start_time;
286 printf("%"PRIu64" clocks, %.1f clocks/symbol (%5.1fMB/s)\n", dec_clocks, 1.0 * dec_clocks / in_size, 1.0 * in_size / (dec_time * 1048576.0));
289 // check decode results
290 if (memcmp(in_bytes, dec_bytes, in_size) == 0)
291 printf("decode ok!\n");
293 printf("ERROR: bad decoder!\n");