ext
laslib
src
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
75
ArithmeticModel::ArithmeticModel
(
U32
symbols,
BOOL
compress)
76
{
77
this->symbols =
symbols
;
78
this->compress =
compress
;
79
distribution
= 0;
80
}
81
82
ArithmeticModel::~ArithmeticModel
()
83
{
84
if
(
distribution
)
delete
[]
distribution
;
85
}
86
87
I32
ArithmeticModel::init
(
U32
* table)
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];
103
decoder_table
=
distribution
+ 2 *
symbols
;
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
}
115
symbol_count
=
distribution
+
symbols
;
116
}
117
118
total_count
= 0;
119
update_cycle
=
symbols
;
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
();
126
symbols_until_update
=
update_cycle
= (
symbols
+ 6) >> 1;
127
128
return
0;
129
}
130
131
void
ArithmeticModel::update
()
132
{
133
// halve counts when a threshold is reached
134
if
((
total_count
+=
update_cycle
) >
DM__MaxCount
)
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;
172
symbols_until_update
=
update_cycle
;
173
}
174
175
ArithmeticBitModel::ArithmeticBitModel
()
176
{
177
init
();
178
}
179
180
ArithmeticBitModel::~ArithmeticBitModel
()
181
{
182
}
183
184
void
ArithmeticBitModel::init
()
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
191
update_cycle
=
bits_until_update
= 4;
192
}
193
194
void
ArithmeticBitModel::update
()
195
{
196
// halve counts when a threshold is reached
197
if
((
bit_count
+=
update_cycle
) >
BM__MaxCount
)
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;
211
bits_until_update
=
update_cycle
;
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