arithmeticencoder.cpp
Go to the documentation of this file.
1 /*
2 ===============================================================================
3 
4  FILE: arithmeticencoder.cpp
5 
6  CONTENTS:
7 
8  A modular C++ wrapper for an adapted version of Amir Said's FastAC Code.
9  see: http://www.cipr.rpi.edu/~said/FastAC.html
10 
11  PROGRAMMERS:
12 
13  martin.isenburg@gmail.com
14 
15  COPYRIGHT:
16 
17  (c) 2011, Martin Isenburg, LASSO - tools to catch reality
18 
19  This is free software; you can redistribute and/or modify it under the
20  terms of the GNU Lesser General Licence as published by the Free Software
21  Foundation. See the COPYING file for more information.
22 
23  This software is distributed WITHOUT ANY WARRANTY and without even the
24  implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
25 
26  CHANGE HISTORY:
27 
28  see header file
29 
30 ===============================================================================
31 */
32 
33 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
34 // -
35 // Fast arithmetic coding implementation -
36 // -> 32-bit variables, 32-bit product, periodic updates, table decoding -
37 // -
38 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
39 // -
40 // Version 1.00 - April 25, 2004 -
41 // -
42 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
43 // -
44 // WARNING -
45 // ========= -
46 // -
47 // The only purpose of this program is to demonstrate the basic principles -
48 // of arithmetic coding. It is provided as is, without any express or -
49 // implied warranty, without even the warranty of fitness for any particular -
50 // purpose, or that the implementations are correct. -
51 // -
52 // Permission to copy and redistribute this code is hereby granted, provided -
53 // that this warning and copyright notices are not removed or altered. -
54 // -
55 // Copyright (c) 2004 by Amir Said (said@ieee.org) & -
56 // William A. Pearlman (pearlw@ecse.rpi.edu) -
57 // -
58 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
59 // -
60 // A description of the arithmetic coding method used here is available in -
61 // -
62 // Lossless Compression Handbook, ed. K. Sayood -
63 // Chapter 5: Arithmetic Coding (A. Said), pp. 101-152, Academic Press, 2003 -
64 // -
65 // A. Said, Introduction to Arithetic Coding Theory and Practice -
66 // HP Labs report HPL-2004-76 - http://www.hpl.hp.com/techreports/ -
67 // -
68 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
69 
70 #include "arithmeticencoder.hpp"
71 
72 #include <string.h>
73 #include <assert.h>
74 
75 #include <stdio.h>
76 
77 FILE* file = 0;
78 
79 #include "arithmeticmodel.hpp"
80 
82 {
83  outstream = 0;
84 
85  outbuffer = (U8*)malloc(sizeof(U8)*2*AC_BUFFER_SIZE);
87 }
88 
90 {
91  free(outbuffer);
92 }
93 
95 {
96  if (outstream == 0) return FALSE;
97  this->outstream = outstream;
98  base = 0;
100  outbyte = outbuffer;
101  endbyte = endbuffer;
102  return TRUE;
103 }
104 
106 {
107  U32 init_base = base; // done encoding: set final data bytes
108  BOOL another_byte = TRUE;
109 
110  if (length > 2 * AC__MinLength) {
111  base += AC__MinLength; // base offset
112  length = AC__MinLength >> 1; // set new length for 1 more byte
113  }
114  else {
115  base += AC__MinLength >> 1; // base offset
116  length = AC__MinLength >> 9; // set new length for 2 more bytes
117  another_byte = FALSE;
118  }
119 
120  if (init_base > base) propagate_carry(); // overflow = carry
121  renorm_enc_interval(); // renormalization = output last bytes
122 
123  if (endbyte != endbuffer)
124  {
125  assert(outbyte < outbuffer + AC_BUFFER_SIZE);
127  }
128  U32 buffer_size = outbyte - outbuffer;
129  if (buffer_size) outstream->putBytes(outbuffer, buffer_size);
130 
131  // write two or three zero bytes to be in sync with the decoder's byte reads
132  outstream->putByte(0);
133  outstream->putByte(0);
134  if (another_byte) outstream->putByte(0);
135 
136  outstream = 0;
137 }
138 
140 {
142  return (EntropyModel*)m;
143 }
144 
145 void ArithmeticEncoder::initBitModel(EntropyModel* model)
146 {
148  m->init();
149 }
150 
151 void ArithmeticEncoder::destroyBitModel(EntropyModel* model)
152 {
154  delete m;
155 }
156 
158 {
159  ArithmeticModel* m = new ArithmeticModel(n, true);
160  return (EntropyModel*)m;
161 }
162 
163 void ArithmeticEncoder::initSymbolModel(EntropyModel* model, U32* table)
164 {
165  ArithmeticModel* m = (ArithmeticModel*)model;
166  m->init(table);
167 }
168 
169 void ArithmeticEncoder::destroySymbolModel(EntropyModel* model)
170 {
171  ArithmeticModel* m = (ArithmeticModel*)model;
172  delete m;
173 }
174 
175 void ArithmeticEncoder::encodeBit(EntropyModel* model, U32 sym)
176 {
177  assert(model && (sym <= 1));
178 
180  U32 x = m->bit_0_prob * (length >> BM__LengthShift); // product l x p0
181  // update interval
182  if (sym == 0) {
183  length = x;
184  ++m->bit_0_count;
185  }
186  else {
187  U32 init_base = base;
188  base += x;
189  length -= x;
190  if (init_base > base) propagate_carry(); // overflow = carry
191  }
192 
193  if (length < AC__MinLength) renorm_enc_interval(); // renormalization
194  if (--m->bits_until_update == 0) m->update(); // periodic model update
195 }
196 
197 void ArithmeticEncoder::encodeSymbol(EntropyModel* model, U32 sym)
198 {
199  assert(model);
200  ArithmeticModel* m = (ArithmeticModel*)model;
201  assert(sym <= m->last_symbol);
202  U32 x, init_base = base;
203  // compute products
204  if (sym == m->last_symbol) {
205  x = m->distribution[sym] * (length >> DM__LengthShift);
206  base += x; // update interval
207  length -= x; // no product needed
208  }
209  else {
210  x = m->distribution[sym] * (length >>= DM__LengthShift);
211  base += x; // update interval
212  length = m->distribution[sym+1] * length - x;
213  }
214 
215  if (init_base > base) propagate_carry(); // overflow = carry
216  if (length < AC__MinLength) renorm_enc_interval(); // renormalization
217 
218  ++m->symbol_count[sym];
219  if (--m->symbols_until_update == 0) m->update(); // periodic model update
220 }
221 
223 {
224  assert(sym < 2);
225 
226  U32 init_base = base;
227  base += sym * (length >>= 1); // new interval base and length
228 
229  if (init_base > base) propagate_carry(); // overflow = carry
230  if (length < AC__MinLength) renorm_enc_interval(); // renormalization
231 }
232 
234 {
235  assert(bits && (bits <= 32) && (sym < (1u<<bits)));
236 
237  if (bits > 19)
238  {
239  writeShort(sym&U16_MAX);
240  sym = sym >> 16;
241  bits = bits - 16;
242  }
243 
244  U32 init_base = base;
245  base += sym * (length >>= bits); // new interval base and length
246 
247  if (init_base > base) propagate_carry(); // overflow = carry
248  if (length < AC__MinLength) renorm_enc_interval(); // renormalization
249 }
250 
252 {
253  U32 init_base = base;
254  base += (U32)(sym) * (length >>= 8); // new interval base and length
255 
256  if (init_base > base) propagate_carry(); // overflow = carry
257  if (length < AC__MinLength) renorm_enc_interval(); // renormalization
258 }
259 
261 {
262  U32 init_base = base;
263  base += (U32)(sym) * (length >>= 16); // new interval base and length
264 
265  if (init_base > base) propagate_carry(); // overflow = carry
266  if (length < AC__MinLength) renorm_enc_interval(); // renormalization
267 }
268 
270 {
271  writeShort((U16)(sym & 0xFFFF)); // lower 16 bits
272  writeShort((U16)(sym >> 16)); // UPPER 16 bits
273 }
274 
275 inline void ArithmeticEncoder::writeFloat(F32 sym) /* danger in float reinterpretation */
276 {
277  U32I32F32 u32i32f32;
278  u32i32f32.f32 = sym;
279  writeInt(u32i32f32.u32);
280 }
281 
283 {
284  writeInt((U32)(sym & 0xFFFFFFFF)); // lower 32 bits
285  writeInt((U32)(sym >> 32)); // UPPER 32 bits
286 }
287 
288 inline void ArithmeticEncoder::writeDouble(F64 sym) /* danger in float reinterpretation */
289 {
290  U64I64F64 u64i64f64;
291  u64i64f64.f64 = sym;
292  writeInt64(u64i64f64.u64);
293 }
294 
296 {
297  U8 * p;
298  if (outbyte == outbuffer)
299  p = endbuffer - 1;
300  else
301  p = outbyte - 1;
302  while (*p == 0xFFU)
303  {
304  *p = 0;
305  if (p == outbuffer)
306  p = endbuffer - 1;
307  else
308  p--;
309  assert(outbuffer <= p);
310  assert(p < endbuffer);
311  assert(outbyte < endbuffer);
312  }
313  ++*p;
314 }
315 
317 {
318  do { // output and discard top byte
319  assert(outbuffer <= outbyte);
320  assert(outbyte < endbuffer);
321  assert(outbyte < endbyte);
322  *outbyte++ = (U8)(base >> 24);
323  if (outbyte == endbyte) manage_outbuffer();
324  base <<= 8;
325  } while ((length <<= 8) < AC__MinLength); // length multiplied by 256
326 }
327 
329 {
333  assert(endbyte > outbyte);
334  assert(outbyte < endbuffer);
335 }
ArithmeticEncoder::writeInt
void writeInt(U32 sym)
Definition: arithmeticencoder.cpp:269
AC_BUFFER_SIZE
#define AC_BUFFER_SIZE
Definition: arithmeticmodel.hpp:44
ArithmeticBitModel
Definition: arithmeticmodel.hpp:75
ArithmeticEncoder::endbyte
U8 * endbyte
Definition: arithmeticencoder.hpp:101
ArithmeticModel
Definition: arithmeticmodel.hpp:57
ArithmeticEncoder::init
BOOL init(ByteStreamOut *outstream)
Definition: arithmeticencoder.cpp:94
ArithmeticEncoder::base
U32 base
Definition: arithmeticencoder.hpp:102
F64
double F64
Definition: mydefs.hpp:52
ArithmeticModel::last_symbol
U32 last_symbol
Definition: arithmeticmodel.hpp:69
U64I64F64::u64
U64 u64
Definition: mydefs.hpp:61
ArithmeticEncoder::length
U32 length
Definition: arithmeticencoder.hpp:102
ArithmeticEncoder::initBitModel
void initBitModel(EntropyModel *model)
Definition: arithmeticencoder.cpp:145
TRUE
#define TRUE
Definition: mydefs.hpp:137
ArithmeticEncoder::encodeSymbol
void encodeSymbol(EntropyModel *model, U32 sym)
Definition: arithmeticencoder.cpp:197
ArithmeticEncoder::writeByte
void writeByte(U8 sym)
Definition: arithmeticencoder.cpp:251
ArithmeticEncoder::writeBits
void writeBits(U32 bits, U32 sym)
Definition: arithmeticencoder.cpp:233
p
SharedPointer p
Definition: ConvertShared.hpp:42
ArithmeticEncoder::createSymbolModel
EntropyModel * createSymbolModel(U32 n)
Definition: arithmeticencoder.cpp:157
ArithmeticEncoder::~ArithmeticEncoder
~ArithmeticEncoder()
Definition: arithmeticencoder.cpp:89
arithmeticencoder.hpp
ArithmeticEncoder::done
void done()
Definition: arithmeticencoder.cpp:105
ArithmeticModel::distribution
U32 * distribution
Definition: arithmeticmodel.hpp:67
ByteStreamOut::putByte
virtual BOOL putByte(U8 byte)=0
ArithmeticBitModel::bit_0_count
U32 bit_0_count
Definition: arithmeticmodel.hpp:86
ArithmeticEncoder::endbuffer
U8 * endbuffer
Definition: arithmeticencoder.hpp:99
ArithmeticEncoder::destroySymbolModel
void destroySymbolModel(EntropyModel *model)
Definition: arithmeticencoder.cpp:169
ArithmeticBitModel::init
void init()
Definition: arithmeticmodel.cpp:184
BM__LengthShift
const U32 BM__LengthShift
Definition: arithmeticmodel.hpp:50
ByteStreamOut
Definition: bytestreamout.hpp:36
ArithmeticEncoder::destroyBitModel
void destroyBitModel(EntropyModel *model)
Definition: arithmeticencoder.cpp:151
ArithmeticModel::update
void update()
Definition: arithmeticmodel.cpp:131
ArithmeticEncoder::ArithmeticEncoder
ArithmeticEncoder()
Definition: arithmeticencoder.cpp:81
ArithmeticBitModel::bits_until_update
U32 bits_until_update
Definition: arithmeticmodel.hpp:85
U16_MAX
#define U16_MAX
Definition: mydefs.hpp:71
ArithmeticEncoder::writeShort
void writeShort(U16 sym)
Definition: arithmeticencoder.cpp:260
ArithmeticEncoder::renorm_enc_interval
void renorm_enc_interval()
Definition: arithmeticencoder.cpp:316
ArithmeticModel::symbols_until_update
U32 symbols_until_update
Definition: arithmeticmodel.hpp:68
ArithmeticEncoder::initSymbolModel
void initSymbolModel(EntropyModel *model, U32 *table=0)
Definition: arithmeticencoder.cpp:163
ArithmeticEncoder::propagate_carry
void propagate_carry()
Definition: arithmeticencoder.cpp:295
ArithmeticBitModel::update
void update()
Definition: arithmeticmodel.cpp:194
U16
unsigned short U16
Definition: mydefs.hpp:40
ArithmeticEncoder::outstream
ByteStreamOut * outstream
Definition: arithmeticencoder.hpp:93
ArithmeticEncoder::writeBit
void writeBit(U32 sym)
Definition: arithmeticencoder.cpp:222
ArithmeticEncoder::manage_outbuffer
void manage_outbuffer()
Definition: arithmeticencoder.cpp:328
ArithmeticEncoder::writeFloat
void writeFloat(F32 sym)
Definition: arithmeticencoder.cpp:275
U8
unsigned char U8
Definition: mydefs.hpp:41
BOOL
int BOOL
Definition: mydefs.hpp:57
U64
unsigned long long U64
Definition: mydefs.hpp:47
U64I64F64
Definition: mydefs.hpp:61
AC__MinLength
const U32 AC__MinLength
Definition: arithmeticmodel.hpp:46
ArithmeticEncoder::writeInt64
void writeInt64(U64 sym)
Definition: arithmeticencoder.cpp:282
FALSE
#define FALSE
Definition: mydefs.hpp:133
file
FILE * file
Definition: arithmeticencoder.cpp:77
F32
float F32
Definition: mydefs.hpp:51
ArithmeticEncoder::encodeBit
void encodeBit(EntropyModel *model, U32 sym)
Definition: arithmeticencoder.cpp:175
arithmeticmodel.hpp
U64I64F64::f64
F64 f64
Definition: mydefs.hpp:61
AC__MaxLength
const U32 AC__MaxLength
Definition: arithmeticmodel.hpp:47
ArithmeticEncoder::outbuffer
U8 * outbuffer
Definition: arithmeticencoder.hpp:98
ArithmeticBitModel::bit_0_prob
U32 bit_0_prob
Definition: arithmeticmodel.hpp:86
ArithmeticEncoder::outbyte
U8 * outbyte
Definition: arithmeticencoder.hpp:100
U32I32F32::u32
U32 u32
Definition: mydefs.hpp:60
U32
unsigned int U32
Definition: mydefs.hpp:39
ArithmeticModel::init
I32 init(U32 *table=0)
Definition: arithmeticmodel.cpp:87
DM__LengthShift
const U32 DM__LengthShift
Definition: arithmeticmodel.hpp:54
U32I32F32
Definition: mydefs.hpp:60
ArithmeticModel::symbol_count
U32 * symbol_count
Definition: arithmeticmodel.hpp:67
ArithmeticEncoder::createBitModel
EntropyModel * createBitModel()
Definition: arithmeticencoder.cpp:139
U32I32F32::f32
F32 f32
Definition: mydefs.hpp:60
ArithmeticEncoder::writeDouble
void writeDouble(F64 sym)
Definition: arithmeticencoder.cpp:288
ByteStreamOut::putBytes
virtual BOOL putBytes(const U8 *bytes, U32 num_bytes)=0


lvr2
Author(s): Thomas Wiemann , Sebastian Pütz , Alexander Mock , Lars Kiesow , Lukas Kalbertodt , Tristan Igelbrink , Johan M. von Behren , Dominik Feldschnieders , Alexander Löhr
autogenerated on Wed Mar 2 2022 00:37:22