arithmeticmodel.cpp
Go to the documentation of this file.
1 /*
2 ===============================================================================
3 
4  FILE: arithmeticmodel.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 "arithmeticmodel.hpp"
71 
72 #include <stdio.h>
73 #include <stdlib.h>
74 
76 {
77  this->symbols = symbols;
78  this->compress = compress;
79  distribution = 0;
80 }
81 
83 {
84  if (distribution) delete [] distribution;
85 }
86 
88 {
89  if (distribution == 0)
90  {
91  if ( (symbols < 2) || (symbols > (1 << 11)) )
92  {
93  return -1; // invalid number of symbols
94  }
95  last_symbol = symbols - 1;
96  if ((!compress) && (symbols > 16))
97  {
98  U32 table_bits = 3;
99  while (symbols > (1U << (table_bits + 2))) ++table_bits;
100  table_size = 1 << table_bits;
101  table_shift = DM__LengthShift - table_bits;
102  distribution = new U32[2*symbols+table_size+2];
104  }
105  else // small alphabet: no table needed
106  {
107  decoder_table = 0;
108  table_size = table_shift = 0;
109  distribution = new U32[2*symbols];
110  }
111  if (distribution == 0)
112  {
113  return -1; // "cannot allocate model memory");
114  }
116  }
117 
118  total_count = 0;
120  if (table)
121  for (U32 k = 0; k < symbols; k++) symbol_count[k] = table[k];
122  else
123  for (U32 k = 0; k < symbols; k++) symbol_count[k] = 1;
124 
125  update();
127 
128  return 0;
129 }
130 
132 {
133  // halve counts when a threshold is reached
135  {
136  total_count = 0;
137  for (U32 n = 0; n < symbols; n++)
138  {
139  total_count += (symbol_count[n] = (symbol_count[n] + 1) >> 1);
140  }
141  }
142 
143  // compute cumulative distribution, decoder table
144  U32 k, sum = 0, s = 0;
145  U32 scale = 0x80000000U / total_count;
146 
147  if (compress || (table_size == 0))
148  {
149  for (k = 0; k < symbols; k++)
150  {
151  distribution[k] = (scale * sum) >> (31 - DM__LengthShift);
152  sum += symbol_count[k];
153  }
154  }
155  else
156  {
157  for (k = 0; k < symbols; k++)
158  {
159  distribution[k] = (scale * sum) >> (31 - DM__LengthShift);
160  sum += symbol_count[k];
161  U32 w = distribution[k] >> table_shift;
162  while (s < w) decoder_table[++s] = k - 1;
163  }
164  decoder_table[0] = 0;
165  while (s <= table_size) decoder_table[++s] = symbols - 1;
166  }
167 
168  // set frequency of model updates
169  update_cycle = (5 * update_cycle) >> 2;
170  U32 max_cycle = (symbols + 6) << 3;
171  if (update_cycle > max_cycle) update_cycle = max_cycle;
173 }
174 
176 {
177  init();
178 }
179 
181 {
182 }
183 
185 {
186  // initialization to equiprobable model
187  bit_0_count = 1;
188  bit_count = 2;
189  bit_0_prob = 1U << (BM__LengthShift - 1);
190  // start with frequent updates
192 }
193 
195 {
196  // halve counts when a threshold is reached
198  {
199  bit_count = (bit_count + 1) >> 1;
200  bit_0_count = (bit_0_count + 1) >> 1;
201  if (bit_0_count == bit_count) ++bit_count;
202  }
203 
204  // compute scaled bit 0 probability
205  U32 scale = 0x80000000U / bit_count;
206  bit_0_prob = (bit_0_count * scale) >> (31 - BM__LengthShift);
207 
208  // set frequency of model updates
209  update_cycle = (5 * update_cycle) >> 2;
210  if (update_cycle > 64) update_cycle = 64;
212 }
ArithmeticModel::table_size
U32 table_size
Definition: arithmeticmodel.hpp:69
ArithmeticModel::last_symbol
U32 last_symbol
Definition: arithmeticmodel.hpp:69
I32
int I32
Definition: mydefs.hpp:35
ArithmeticModel::ArithmeticModel
ArithmeticModel(U32 symbols, BOOL compress)
Definition: arithmeticmodel.cpp:75
ArithmeticModel::table_shift
U32 table_shift
Definition: arithmeticmodel.hpp:69
ArithmeticModel::decoder_table
U32 * decoder_table
Definition: arithmeticmodel.hpp:67
ArithmeticModel::distribution
U32 * distribution
Definition: arithmeticmodel.hpp:67
ArithmeticBitModel::bit_0_count
U32 bit_0_count
Definition: arithmeticmodel.hpp:86
ArithmeticBitModel::~ArithmeticBitModel
~ArithmeticBitModel()
Definition: arithmeticmodel.cpp:180
ArithmeticBitModel::update_cycle
U32 update_cycle
Definition: arithmeticmodel.hpp:85
ArithmeticBitModel::init
void init()
Definition: arithmeticmodel.cpp:184
BM__LengthShift
const U32 BM__LengthShift
Definition: arithmeticmodel.hpp:50
ArithmeticModel::compress
BOOL compress
Definition: arithmeticmodel.hpp:70
ArithmeticModel::update
void update()
Definition: arithmeticmodel.cpp:131
ArithmeticModel::update_cycle
U32 update_cycle
Definition: arithmeticmodel.hpp:68
ArithmeticModel::~ArithmeticModel
~ArithmeticModel()
Definition: arithmeticmodel.cpp:82
ArithmeticBitModel::bits_until_update
U32 bits_until_update
Definition: arithmeticmodel.hpp:85
ArithmeticModel::symbols_until_update
U32 symbols_until_update
Definition: arithmeticmodel.hpp:68
ArithmeticBitModel::ArithmeticBitModel
ArithmeticBitModel()
Definition: arithmeticmodel.cpp:175
ArithmeticBitModel::update
void update()
Definition: arithmeticmodel.cpp:194
ArithmeticBitModel::bit_count
U32 bit_count
Definition: arithmeticmodel.hpp:86
BOOL
int BOOL
Definition: mydefs.hpp:57
arithmeticmodel.hpp
ArithmeticModel::symbols
U32 symbols
Definition: arithmeticmodel.hpp:69
ArithmeticBitModel::bit_0_prob
U32 bit_0_prob
Definition: arithmeticmodel.hpp:86
BM__MaxCount
const U32 BM__MaxCount
Definition: arithmeticmodel.hpp:51
U32
unsigned int U32
Definition: mydefs.hpp:39
ArithmeticModel::init
I32 init(U32 *table=0)
Definition: arithmeticmodel.cpp:87
ArithmeticModel::total_count
U32 total_count
Definition: arithmeticmodel.hpp:68
DM__LengthShift
const U32 DM__LengthShift
Definition: arithmeticmodel.hpp:54
ArithmeticModel::symbol_count
U32 * symbol_count
Definition: arithmeticmodel.hpp:67
DM__MaxCount
const U32 DM__MaxCount
Definition: arithmeticmodel.hpp:55


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