1 /*
2 * nd.c: Output of prediction tree
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:31 $
12 * $Author: hafner $
13 * $Revision: 5.1 $
14 * $State: Exp $
15 */
16
17 #include "config.h"
18
19 #include "types.h"
20 #include "macros.h"
21 #include "error.h"
22
23 #include "wfa.h"
24 #include "arith.h"
25 #include "misc.h"
26 #include "bit-io.h"
27 #include "rpf.h"
28 #include "list.h"
29
30 #include "nd.h"
31
32 /*****************************************************************************
33
34 prototypes
35
36 *****************************************************************************/
37
38 static unsigned
39 encode_nd_tree (const wfa_t *wfa, bitfile_t *output);
40 static void
41 encode_nd_coefficients (unsigned total, const wfa_t *wfa, bitfile_t *output);
42
43 /*****************************************************************************
44
45 public code
46
47 *****************************************************************************/
48
49 void
write_nd(const wfa_t * wfa,bitfile_t * output)50 write_nd (const wfa_t *wfa, bitfile_t *output)
51 /*
52 * Write prediction information of 'wfa' to given stream 'output'.
53 * Coefficients are quantized with model 'p_rpf'.
54 *
55 * No return value.
56 */
57 {
58 unsigned total = encode_nd_tree (wfa, output);
59
60 if (total > 0)
61 encode_nd_coefficients (total, wfa, output);
62 }
63
64 /*****************************************************************************
65
66 private code
67
68 *****************************************************************************/
69
70 static unsigned
encode_nd_tree(const wfa_t * wfa,bitfile_t * output)71 encode_nd_tree (const wfa_t *wfa, bitfile_t *output)
72 /*
73 * Write prediction tree of 'wfa' to given stream 'output'.
74 *
75 * No return value.
76 */
77 {
78 lqueue_t *queue; /* queue of states */
79 int state, next; /* state and its current child */
80 unsigned used, not_used; /* counter ND used/not used */
81 u_word_t low; /* Start of the current code range */
82 u_word_t high; /* End of the current code range */
83 u_word_t underflow; /* Number of underflow bits pending */
84 u_word_t sum0, sum1; /* Probability model */
85 unsigned bits = bits_processed (output);
86
87 used = not_used = 0;
88
89 /*
90 * Initialize arithmetic coder
91 */
92 low = 0;
93 high = 0xffff;
94 underflow = 0;
95 sum0 = 1;
96 sum1 = 11;
97
98 queue = alloc_queue (sizeof (int));
99 state = wfa->root_state;
100 queue_append (queue, &state);
101
102 /*
103 * Traverse the WFA tree in breadth first order (using a queue).
104 */
105 while (queue_remove (queue, &next))
106 {
107 unsigned label;
108
109 if (wfa->level_of_state [next] > wfa->wfainfo->p_max_level + 1)
110 {
111 /*
112 * Nondetermismn is not allowed at levels larger than
113 * 'wfa->wfainfo->p_max_level'.
114 */
115 for (label = 0; label < MAXLABELS; label++)
116 if (ischild (state = wfa->tree [next][label]))
117 queue_append (queue, &state); /* continue with children */
118 }
119 else if (wfa->level_of_state [next] > wfa->wfainfo->p_min_level)
120 {
121 for (label = 0; label < MAXLABELS; label++)
122 if (ischild (state = wfa->tree [next][label]))
123 {
124 unsigned range; /* Current interval range */
125
126 if (isedge (wfa->into [next][label][0])) /* prediction used */
127 {
128 used++;
129
130 /*
131 * Encode a '1' symbol
132 */
133 range = (high - low) + 1;
134 low = low + (u_word_t) ((range * sum0) / sum1);
135 RESCALE_OUTPUT_INTERVAL;
136 }
137 else /* no predict., continue with children */
138 {
139 not_used++;
140 if (wfa->level_of_state [state] > wfa->wfainfo->p_min_level)
141 queue_append (queue, &state);
142
143 /*
144 * Encode a '0' symbol
145 */
146 range = (high - low) + 1;
147 high = low + (u_word_t) ((range * sum0) / sum1 - 1);
148 RESCALE_OUTPUT_INTERVAL;
149 sum0++;
150 }
151 /*
152 * Update the frequency counts
153 */
154 sum1++;
155 if (sum1 > 50) /* Scale the symbol frequencies */
156 {
157 sum0 >>= 1;
158 sum1 >>= 1;
159 if (!sum0)
160 sum0 = 1;
161 if (sum0 >= sum1)
162 sum1 = sum0 + 1;
163 }
164 }
165
166 }
167 }
168 free_queue (queue);
169
170 /*
171 * Flush the quasi-arithmetic encoder
172 */
173 low = high;
174 RESCALE_OUTPUT_INTERVAL;
175 OUTPUT_BYTE_ALIGN (output);
176
177 debug_message ("%d nd fields: %d used nd, %d used not nd", used + not_used,
178 used, not_used);
179 {
180 unsigned total = used + not_used;
181
182 debug_message ("nd-tree: %5d bits. (%5d symbols => %5.2f bps)",
183 bits_processed (output) - bits, total,
184 total > 0 ? ((bits_processed (output) - bits) /
185 (double) total) : 0);
186 }
187
188 return used;
189 }
190
191 static void
encode_nd_coefficients(unsigned total,const wfa_t * wfa,bitfile_t * output)192 encode_nd_coefficients (unsigned total, const wfa_t *wfa, bitfile_t *output)
193 /*
194 * Write #'total' weights of nondeterministic part of 'wfa' to given 'output'
195 * stream. Coefficients are stored with arithmetic coding (the model is
196 * given by 'p_rpf').
197 *
198 * No return value.
199 */
200 {
201 unsigned bits = bits_processed (output);
202
203 {
204 unsigned *coefficients; /* array of factors to encode */
205 unsigned *ptr; /* pointer to current factor */
206 unsigned state, label, edge;
207 word_t domain;
208
209 ptr = coefficients = Calloc (total, sizeof (unsigned));
210
211 for (state = wfa->basis_states; state < wfa->states; state++)
212 for (label = 0; label < MAXLABELS; label++)
213 if (ischild (wfa->tree [state][label])
214 && isedge (wfa->into [state][label][0]))
215 for (edge = 0; isedge (domain = wfa->into [state][label][edge]);
216 edge++)
217 {
218 if (ptr - coefficients >= (int) total)
219 error ("Can't write more than %d coefficients.", total);
220
221 *ptr++ = rtob (wfa->weight [state][label][edge],
222 wfa->wfainfo->dc_rpf);
223 }
224
225 /*
226 * Encode array of coefficients with arithmetic coding
227 */
228 {
229 const int scaling = 50; /* scaling factor of prob. model */
230 unsigned c_symbols = 1 << (wfa->wfainfo->dc_rpf->mantissa_bits + 1);
231
232 encode_array (output, coefficients, NULL, &c_symbols, 1,
233 total, scaling);
234 }
235
236 debug_message ("nd-factors: %5d bits. (%5d symbols => %5.2f bps)",
237 bits_processed (output) - bits, total,
238 total ? ((bits_processed (output) - bits)
239 / (double) total) : 0);
240 Free (coefficients);
241 }
242 }
243
244
245