1 /*
2 * coeff.c: Matching pursuit coefficients probability model
3 *
4 * Written by: Ullrich Hafner
5 *
6 * This file is part of FIASCO (Fractal Image And Sequence COdec)
7 * Copyright (C) 1994-2000 Ullrich Hafner
8 */
9
10 /*
11 * $Date: 2000/06/14 20:50:51 $
12 * $Author: hafner $
13 * $Revision: 5.1 $
14 * $State: Exp $
15 */
16
17 #include <string.h>
18 #include "config.h"
19
20 #include "types.h"
21 #include "macros.h"
22 #include "error.h"
23
24 #include "rpf.h"
25 #include "misc.h"
26 #include "coeff.h"
27
28 /*
29 * Coefficient model interface:
30 * Implementing the coefficients model interface requires the
31 * following steps:
32 * - Add a constructor that initializes the coeff_t structure
33 * - Allocate new model with default_alloc()
34 * - Fill the c_array_t coeff_models[] array with constructor and name
35 * - Write code for methods bits() and update()
36 * - Either use default functions for remaining methods or override them
37 * The new model is automatically registered at the command line.
38 */
39
40 /*****************************************************************************
41 uniform distribution coefficients model
42 *****************************************************************************/
43
44 static coeff_t *
45 alloc_uniform_coeff_model (rpf_t *rpf, rpf_t *dc_rpf,
46 unsigned min_level, unsigned max_level);
47 static void
48 uniform_update (const real_t *used_coeff, const word_t *used_states,
49 unsigned level, coeff_t *coeff);
50 static real_t
51 uniform_bits (const real_t *used_coeff, const word_t *used_states,
52 unsigned level, const coeff_t *coeff);
53
54 /*****************************************************************************
55 default functions
56 *****************************************************************************/
57
58 static void
59 default_model_free (void *model);
60 static void *
61 default_model_duplicate (const coeff_t *coeff, const void *model);
62 static void
63 default_free (coeff_t *coeff);
64 static coeff_t *
65 default_alloc (rpf_t *rpf, rpf_t *dc_rpf,
66 unsigned min_level, unsigned max_level);
67
68 /*****************************************************************************
69 adaptive arithmetic coding model
70 *****************************************************************************/
71
72 static coeff_t *
73 alloc_aac_coeff_model (rpf_t *rpf, rpf_t *dc_rpf,
74 unsigned min_level, unsigned max_level);
75 static void
76 aac_model_free (void *model);
77 static void *
78 aac_model_alloc (const coeff_t *coeff);
79 static void *
80 aac_model_duplicate (const coeff_t *coeff, const void *model);
81 static void
82 aac_update (const real_t *used_coeff, const word_t *used_states,
83 unsigned level, coeff_t *coeff);
84 static real_t
85 aac_bits (const real_t *used_coeff, const word_t *used_states,
86 unsigned level, const coeff_t *coeff);
87
88 /*****************************************************************************
89
90 public code
91
92 *****************************************************************************/
93
94 typedef struct c_array
95 {
96 const char *identifier;
97 coeff_t *(*function) (rpf_t *rpf, rpf_t *dc_rpf,
98 unsigned min_level, unsigned max_level);
99 } c_array_t;
100
101 c_array_t coeff_models[] = {{"adaptive", alloc_aac_coeff_model},
102 {"uniform", alloc_uniform_coeff_model},
103 {NULL, NULL}};
104
105 coeff_t *
alloc_coeff_model(const char * coeff_model_name,rpf_t * rpf,rpf_t * dc_rpf,unsigned min_level,unsigned max_level)106 alloc_coeff_model (const char *coeff_model_name, rpf_t *rpf, rpf_t *dc_rpf,
107 unsigned min_level, unsigned max_level)
108 /*
109 * Allocate a new coefficients model which is identified by the string
110 * 'coeff_model_name'. 'rpf' and 'dc_rpf' define the reduced
111 * precision formats the should be used to quantize normal and DC
112 * components, respectively. 'min_level' and 'max_level' define the
113 * range of range approximations.
114 *
115 * Return value:
116 * pointer to the allocated coefficients model
117 *
118 * Note:
119 * Refer to 'coeff.h' for a short description of the member functions. */
120 {
121 unsigned n;
122
123 for (n = 0; coeff_models [n].identifier; n++) /* step through all id's */
124 if (strcaseeq (coeff_models [n].identifier, coeff_model_name))
125 return coeff_models [n].function (rpf, dc_rpf, min_level, max_level);
126
127 warning ("Can't initialize coefficients model '%s'. "
128 "Using default value '%s'.",
129 coeff_model_name, coeff_models [0].identifier);
130
131 return coeff_models [0].function (rpf, dc_rpf, min_level, max_level);
132 }
133
134 /*****************************************************************************
135
136 private code
137
138 *****************************************************************************/
139
140 /*****************************************************************************
141 uniform distribution coefficients model
142 *****************************************************************************/
143
144 static coeff_t *
alloc_uniform_coeff_model(rpf_t * rpf,rpf_t * dc_rpf,unsigned min_level,unsigned max_level)145 alloc_uniform_coeff_model (rpf_t *rpf, rpf_t *dc_rpf,
146 unsigned min_level, unsigned max_level)
147 /*
148 * Underlying probability model: uniform distribution.
149 * I.e. each coefficient is written as such with
150 * (1 + exponent_bits + mantissa_bits) bits.
151 */
152 {
153 coeff_t *coeff = default_alloc (rpf, dc_rpf, min_level, max_level);
154
155 coeff->bits = uniform_bits;
156 coeff->update = uniform_update;
157
158 return coeff;
159 }
160
161 static real_t
uniform_bits(const real_t * used_coeff,const word_t * used_states,unsigned level,const coeff_t * coeff)162 uniform_bits (const real_t *used_coeff, const word_t *used_states,
163 unsigned level, const coeff_t *coeff)
164 {
165 unsigned edge;
166 real_t bits = 0; /* #bits to store coefficients */
167
168 for (edge = 0; isedge (used_states [edge]); edge++)
169 {
170 rpf_t *rpf = used_states [edge] ? coeff->rpf : coeff->dc_rpf;
171
172 bits += rpf->mantissa_bits + 1;
173 }
174
175 return bits;
176 }
177
178 static void
uniform_update(const real_t * used_coeff,const word_t * used_states,unsigned level,coeff_t * coeff)179 uniform_update (const real_t *used_coeff, const word_t *used_states,
180 unsigned level, coeff_t *coeff)
181 {
182 return; /* nothing to do */
183 }
184
185 /*****************************************************************************
186 adaptive arithmetic coding model
187 *****************************************************************************/
188
189 typedef struct aac_model
190 {
191 word_t *counts;
192 word_t *totals;
193 } aac_model_t;
194
195 static coeff_t *
alloc_aac_coeff_model(rpf_t * rpf,rpf_t * dc_rpf,unsigned min_level,unsigned max_level)196 alloc_aac_coeff_model (rpf_t *rpf, rpf_t *dc_rpf,
197 unsigned min_level, unsigned max_level)
198 /*
199 * Underlying probability model: adaptive arithmetic coding using
200 * the level of a range as context.
201 */
202 {
203 coeff_t *coeff = default_alloc (rpf, dc_rpf, min_level, max_level);
204
205 coeff->bits = aac_bits;
206 coeff->update = aac_update;
207 coeff->model_free = aac_model_free;
208 coeff->model_duplicate = aac_model_duplicate;
209 coeff->model = aac_model_alloc (coeff);
210
211 return coeff;
212 }
213
214 static real_t
aac_bits(const real_t * used_coeff,const word_t * used_states,unsigned level,const coeff_t * coeff)215 aac_bits (const real_t *used_coeff, const word_t *used_states,
216 unsigned level, const coeff_t *coeff)
217 {
218 real_t bits = 0; /* # bits to store coefficients */
219 unsigned edge;
220 int state;
221 word_t *counts;
222 aac_model_t *model = (aac_model_t *) coeff->model;
223
224 counts = model->counts
225 + (1 << (1 + coeff->dc_rpf->mantissa_bits))
226 + ((level - coeff->min_level)
227 * (1 << (1 + coeff->rpf->mantissa_bits)));
228
229 for (edge = 0; isedge (state = used_states [edge]); edge++)
230 if (state)
231 bits -= log2 (counts [rtob (used_coeff [edge], coeff->rpf)]
232 / (real_t) model->totals [level
233 - coeff->min_level + 1]);
234 else
235 bits -= log2 (model->counts [rtob (used_coeff [edge], coeff->dc_rpf)]
236 / (real_t) model->totals [0]);
237
238 return bits;
239 }
240
241 static void
aac_update(const real_t * used_coeff,const word_t * used_states,unsigned level,coeff_t * coeff)242 aac_update (const real_t *used_coeff, const word_t *used_states,
243 unsigned level, coeff_t *coeff)
244 {
245 unsigned edge;
246 int state;
247 word_t *counts;
248 aac_model_t *model = (aac_model_t *) coeff->model;
249
250 counts = model->counts
251 + (1 << (1 + coeff->dc_rpf->mantissa_bits))
252 + ((level - coeff->min_level)
253 * (1 << (1 + coeff->rpf->mantissa_bits)));
254
255 for (edge = 0; isedge (state = used_states [edge]); edge++)
256 if (state)
257 {
258 counts [rtob (used_coeff [edge], coeff->rpf)]++;
259 model->totals [level - coeff->min_level + 1]++;
260 }
261 else
262 {
263 model->counts [rtob (used_coeff [edge], coeff->dc_rpf)]++;
264 model->totals [0]++;
265 }
266 }
267
268 static void *
aac_model_duplicate(const coeff_t * coeff,const void * model)269 aac_model_duplicate (const coeff_t *coeff, const void *model)
270 {
271 aac_model_t *src = (aac_model_t *) model;
272 aac_model_t *dst = aac_model_alloc (coeff);
273
274 memcpy (dst->counts, src->counts,
275 sizeof (word_t) * ((coeff->max_level - coeff->min_level + 1)
276 * (1 << (1 + coeff->rpf->mantissa_bits))
277 + (1 << (1 + coeff->dc_rpf->mantissa_bits))));
278 memcpy (dst->totals, src->totals,
279 sizeof (word_t) * (coeff->max_level - coeff->min_level + 1 + 1));
280
281 return dst;
282 }
283
284 static void *
aac_model_alloc(const coeff_t * coeff)285 aac_model_alloc (const coeff_t *coeff)
286 {
287 aac_model_t *model;
288 unsigned size = (coeff->max_level - coeff->min_level + 1)
289 * (1 << (1 + coeff->rpf->mantissa_bits))
290 + (1 << (1 + coeff->dc_rpf->mantissa_bits));
291
292 model = Calloc (1, sizeof (aac_model_t));
293 model->counts = Calloc (size, sizeof (word_t));
294 model->totals = Calloc (coeff->max_level - coeff->min_level + 1 + 1,
295 sizeof (word_t));
296 /*
297 * Initialize model
298 */
299 {
300 unsigned n;
301 word_t *ptr = model->counts;
302
303 for (n = size; n; n--)
304 *ptr++ = 1;
305 model->totals [0] = 1 << (1 + coeff->dc_rpf->mantissa_bits);
306 for (n = coeff->min_level; n <= coeff->max_level; n++)
307 model->totals [n - coeff->min_level + 1]
308 = 1 << (1 + coeff->rpf->mantissa_bits);
309 }
310
311 return (void *) model;
312 }
313
314 static void
aac_model_free(void * model)315 aac_model_free (void *model)
316 {
317 aac_model_t *aac_model = (aac_model_t *) model;
318
319 if (aac_model)
320 {
321 Free (aac_model->counts);
322 Free (aac_model->totals);
323 Free (aac_model);
324 }
325 }
326
327 /*****************************************************************************
328 default functions
329 *****************************************************************************/
330
331 static coeff_t *
default_alloc(rpf_t * rpf,rpf_t * dc_rpf,unsigned min_level,unsigned max_level)332 default_alloc (rpf_t *rpf, rpf_t *dc_rpf,
333 unsigned min_level, unsigned max_level)
334 {
335 coeff_t *coeff = Calloc (1, sizeof (coeff_t));
336
337 coeff->rpf = rpf;
338 coeff->dc_rpf = dc_rpf;
339 coeff->min_level = min_level;
340 coeff->max_level = max_level;
341 coeff->model = NULL;
342 coeff->bits = NULL;
343 coeff->update = NULL;
344 coeff->free = default_free;
345 coeff->model_free = default_model_free;
346 coeff->model_duplicate = default_model_duplicate;
347
348 return coeff;
349 }
350
351 static void
default_free(coeff_t * coeff)352 default_free (coeff_t *coeff)
353 {
354 coeff->model_free (coeff->model);
355 Free (coeff);
356 }
357
358 static void *
default_model_duplicate(const coeff_t * coeff,const void * model)359 default_model_duplicate (const coeff_t *coeff, const void *model)
360 {
361 return NULL;
362 }
363
364 static void
default_model_free(void * model)365 default_model_free (void *model)
366 {
367 if (model)
368 Free (model);
369 }
370