1 /*
2 * wfalib.c: Library functions both for encoding and decoding
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/07/18 15:57:28 $
12 * $Author: hafner $
13 * $Revision: 5.5 $
14 * $State: Exp $
15 */
16
17 #define _DEFAULT_SOURCE 1 /* New name for SVID & BSD source defines */
18 #define _BSD_SOURCE 1 /* Make sure strdup() is in string.h */
19 #define _XOPEN_SOURCE 500 /* Make sure strdup() is in string.h */
20
21 #include "config.h"
22
23 #include <stdlib.h>
24 #include <string.h>
25
26 #include "pm_c_util.h"
27
28 #include "types.h"
29 #include "macros.h"
30 #include "error.h"
31
32 #include "wfa.h"
33 #include "misc.h"
34 #include "wfalib.h"
35
36 /*****************************************************************************
37
38 prototypes
39
40 *****************************************************************************/
41
42 static unsigned
43 xy_to_address (unsigned x, unsigned y, unsigned level, unsigned n);
44
45 /*****************************************************************************
46
47 public code
48
49 *****************************************************************************/
50
51 wfa_t *
alloc_wfa(bool_t coding)52 alloc_wfa (bool_t coding)
53 /*
54 * WFA constructor:
55 * Initialize the WFA structure 'wfa' and allocate memory.
56 * Flag 'coding' indicates whether WFA is used for coding or decoding.
57 *
58 * Return value:
59 * pointer to the new WFA structure
60 */
61 {
62 wfa_t *wfa = Calloc (1, sizeof (wfa_t));
63
64 /*
65 * Allocate memory
66 */
67 wfa->final_distribution = Calloc (MAXSTATES, sizeof (real_t));
68 wfa->level_of_state = Calloc (MAXSTATES, sizeof (byte_t));
69 wfa->domain_type = Calloc (MAXSTATES, sizeof (byte_t));
70 wfa->delta_state = Calloc (MAXSTATES, sizeof (bool_t));
71 wfa->tree = Calloc (MAXSTATES * MAXLABELS, sizeof (word_t));
72 wfa->x = Calloc (MAXSTATES * MAXLABELS, sizeof (word_t));
73 wfa->y = Calloc (MAXSTATES * MAXLABELS, sizeof (word_t));
74 wfa->mv_tree = Calloc (MAXSTATES * MAXLABELS, sizeof (mv_t));
75 wfa->y_state = Calloc (MAXSTATES * MAXLABELS, sizeof (word_t));
76 wfa->into = Calloc (MAXSTATES * MAXLABELS * (MAXEDGES + 1),
77 sizeof (word_t));
78 wfa->weight = Calloc (MAXSTATES * MAXLABELS * (MAXEDGES + 1),
79 sizeof (real_t));
80 wfa->int_weight = Calloc (MAXSTATES * MAXLABELS * (MAXEDGES + 1),
81 sizeof (word_t));
82 wfa->wfainfo = Calloc (1, sizeof (wfa_info_t));;
83 wfa->prediction = Calloc (MAXSTATES * MAXLABELS, sizeof (byte_t));
84
85 wfa->wfainfo->wfa_name = NULL;
86 wfa->wfainfo->basis_name = NULL;
87 wfa->wfainfo->title = strdup ("");
88 wfa->wfainfo->comment = strdup ("");
89
90 /*
91 * Initialize structure
92 */
93 {
94 unsigned state, label;
95
96 wfa->states = 0;
97 wfa->basis_states = 0;
98 wfa->root_state = 0;
99 for (state = 0; state < MAXSTATES; state++)
100 {
101 wfa->final_distribution [state] = 0;
102 wfa->domain_type [state] = 0;
103 for (label = 0; label < MAXLABELS; label++)
104 {
105 wfa->into [state][label][0] = NO_EDGE;
106 wfa->tree [state][label] = RANGE;
107 wfa->y_state [state][label] = RANGE;
108 }
109 }
110 }
111
112 if (coding) /* initialize additional variables */
113 wfa->y_column = Calloc (MAXSTATES * MAXLABELS, sizeof (byte_t));
114 else
115 wfa->y_column = NULL;
116
117 return wfa;
118 }
119
120 void
free_wfa(wfa_t * wfa)121 free_wfa (wfa_t *wfa)
122 /*
123 * WFA destructor:
124 * Free memory of given 'wfa'.
125 *
126 * No return value.
127 *
128 * Side effects:
129 * 'wfa' struct is discarded.
130 */
131 {
132 if (wfa->wfainfo->wfa_name)
133 Free (wfa->wfainfo->wfa_name);
134 if (wfa->wfainfo->basis_name)
135 Free (wfa->wfainfo->basis_name);
136 if (wfa->wfainfo->title)
137 Free (wfa->wfainfo->title);
138 if (wfa->wfainfo->comment)
139 Free (wfa->wfainfo->comment);
140
141 Free (wfa->final_distribution);
142 Free (wfa->level_of_state);
143 Free (wfa->domain_type);
144 Free (wfa->tree);
145 Free (wfa->x);
146 Free (wfa->y);
147 Free (wfa->mv_tree);
148 Free (wfa->y_state);
149 Free (wfa->into);
150 Free (wfa->weight);
151 Free (wfa->int_weight);
152 Free (wfa->wfainfo);
153 Free (wfa->prediction);
154 Free (wfa->delta_state);
155 if (wfa->y_column)
156 Free (wfa->y_column);
157 Free (wfa);
158 }
159
160 real_t
compute_final_distribution(unsigned state,const wfa_t * wfa)161 compute_final_distribution (unsigned state, const wfa_t *wfa)
162 /*
163 * Compute the final distribution of the given 'state'.
164 * Uses the fact that the generated 'wfa' is average preserving.
165 *
166 * Return value:
167 * final distribution
168 */
169 {
170 unsigned label;
171 real_t final = 0;
172
173 for (label = 0; label < MAXLABELS; label++)
174 {
175 unsigned edge;
176 int domain;
177
178 if (ischild (domain = wfa->tree [state][label]))
179 final += wfa->final_distribution [domain];
180 for (edge = 0; isedge (domain = wfa->into [state][label][edge]); edge++)
181 final += wfa->weight [state][label][edge]
182 * wfa->final_distribution [domain];
183 }
184
185 return final / MAXLABELS;
186 }
187
188 word_t *
compute_hits(unsigned from,unsigned to,unsigned n,const wfa_t * wfa)189 compute_hits (unsigned from, unsigned to, unsigned n, const wfa_t *wfa)
190 /*
191 * Selects the 'n' most popular domain images of the given 'wfa'.
192 * Consider only linear combinations of state images
193 * {i | 'from' <= i <= 'to'}. I.e. domains are in {i | from <= i < 'to'}
194 * Always ensure that state 0 is among selected states even though from
195 * may be > 0.
196 *
197 * Return value:
198 * pointer to array of the most popular state images
199 * sorted by increasing state numbers and terminated by -1
200 */
201 {
202 word_t *domains;
203 unsigned state, label, edge;
204 int domain;
205 pair_t *hits = Calloc (to, sizeof (pair_t));
206
207 for (domain = 0; domain < (int) to; domain++)
208 {
209 hits [domain].value = domain;
210 hits [domain].key = 0;
211 }
212
213 for (state = from; state <= to; state++)
214 for (label = 0; label < MAXLABELS; label++)
215 for (edge = 0; isedge (domain = wfa->into [state][label][edge]);
216 edge++)
217 hits [domain].key++;
218
219 qsort (hits + 1, to - 1, sizeof (pair_t), sort_desc_pair);
220
221 n = MIN(to, n);
222 domains = Calloc (n + 1, sizeof (word_t));
223
224 for (domain = 0; domain < (int) n && (!domain || hits [domain].key);
225 domain++)
226 domains [domain] = hits [domain].value;
227 if (n != domain)
228 debug_message ("Only %d domains have been used in the luminance.",
229 domain);
230 n = domain;
231 qsort (domains, n, sizeof (word_t), sort_asc_word);
232 domains [n] = -1;
233
234 Free (hits);
235
236 return domains;
237 }
238
239 void
append_edge(unsigned from,unsigned into,real_t weight,unsigned label,wfa_t * wfa)240 append_edge (unsigned from, unsigned into, real_t weight,
241 unsigned label, wfa_t *wfa)
242 /*
243 * Append an edge from state 'from' to state 'into' with
244 * the given 'label' and 'weight' to the 'wfa'.
245 *
246 * No return value.
247 *
248 * Side effects:
249 * 'wfa' structure is changed.
250 */
251 {
252 unsigned new; /* position of the new edge */
253 unsigned edge;
254
255 /*
256 * First look where to insert the new edge:
257 * edges are sorted by increasing 'into' values
258 */
259 for (new = 0; (isedge (wfa->into [from][label][new])
260 && wfa->into [from][label][new] < (int) into); new++)
261 ;
262 /*
263 * Move the edges 'n' to position 'n+1', for n = max, ..., 'new'
264 */
265 for (edge = new; isedge (wfa->into [from][label][edge]); edge++)
266 ;
267 for (edge++; edge != new; edge--)
268 {
269 wfa->into [from][label][edge] = wfa->into [from][label][edge - 1];
270 wfa->weight [from][label][edge] = wfa->weight [from][label][edge - 1];
271 wfa->int_weight [from][label][edge]
272 = wfa->int_weight [from][label][edge - 1];
273 }
274 /*
275 * Insert the new edge
276 */
277 wfa->into [from][label][edge] = into;
278 wfa->weight [from][label][edge] = weight;
279 wfa->int_weight [from][label][edge] = weight * 512 + 0.5;
280 }
281
282 void
remove_states(unsigned from,wfa_t * wfa)283 remove_states (unsigned from, wfa_t *wfa)
284 /*
285 * Remove 'wfa' states 'wfa->basis_states',...,'wfa->states' - 1.
286 *
287 * No return value.
288 *
289 * Side effects:
290 * 'wfa' structure is cleared for the given states.
291 */
292 {
293 unsigned state;
294
295 for (state = from; state < wfa->states; state++)
296 {
297 unsigned label;
298
299 for (label = 0; label < MAXLABELS; label++)
300 {
301 wfa->into [state][label][0] = NO_EDGE;
302 wfa->tree [state][label] = RANGE;
303 wfa->prediction [state][label] = FALSE;
304 wfa->y_state [state][label] = RANGE;
305 wfa->mv_tree [state][label].type = NONE;
306 wfa->mv_tree [state][label].fx = 0;
307 wfa->mv_tree [state][label].fy = 0;
308 wfa->mv_tree [state][label].bx = 0;
309 wfa->mv_tree [state][label].by = 0;
310 }
311 wfa->domain_type [state] = 0;
312 wfa->delta_state [state] = FALSE;
313 }
314
315 wfa->states = from;
316 }
317
318 void
copy_wfa(wfa_t * dst,const wfa_t * src)319 copy_wfa (wfa_t *dst, const wfa_t *src)
320 /*
321 * Copy WFA struct 'src' to WFA struct 'dst'.
322 *
323 * No return value.
324 *
325 * Side effects:
326 * 'dst' is filled with same data as 'src'
327 *
328 * NOTE: size of WFA 'dst' must be at least size of WFA 'src'
329 */
330 {
331 unsigned state;
332
333 memset (dst->final_distribution, 0, MAXSTATES * sizeof (real_t));
334 memset (dst->level_of_state, 0, MAXSTATES * sizeof (byte_t));
335 memset (dst->domain_type, 0, MAXSTATES * sizeof (byte_t));
336 memset (dst->mv_tree, 0, MAXSTATES * MAXLABELS * sizeof (mv_t));
337 memset (dst->tree, 0, MAXSTATES * MAXLABELS * sizeof (word_t));
338 memset (dst->x, 0, MAXSTATES * MAXLABELS * sizeof (word_t));
339 memset (dst->y, 0, MAXSTATES * MAXLABELS * sizeof (word_t));
340 memset (dst->y_state, 0, MAXSTATES * MAXLABELS * sizeof (word_t));
341 memset (dst->into, NO_EDGE,
342 MAXSTATES * MAXLABELS * (MAXEDGES + 1) * sizeof (word_t));
343 memset (dst->weight, 0,
344 MAXSTATES * MAXLABELS * (MAXEDGES + 1) * sizeof (real_t));
345 memset (dst->int_weight, 0,
346 MAXSTATES * MAXLABELS * (MAXEDGES + 1) * sizeof (word_t));
347 memset (dst->prediction, 0, MAXSTATES * MAXLABELS * sizeof (byte_t));
348 memset (dst->delta_state, 0, MAXSTATES * sizeof (bool_t));
349 if (dst->y_column)
350 memset (dst->y_column, 0, MAXSTATES * MAXLABELS * sizeof (byte_t));
351
352 for (state = 0; state < MAXSTATES; state++) /* clear WFA struct */
353 {
354 unsigned label;
355
356 for (label = 0; label < MAXLABELS; label++)
357 {
358 dst->into [state][label][0] = NO_EDGE;
359 dst->tree [state][label] = RANGE;
360 dst->mv_tree [state][label].type = NONE;
361 dst->y_state[state][label] = RANGE;
362 }
363 dst->delta_state [state] = NO;
364 dst->domain_type [state] = 0;
365 }
366
367 dst->frame_type = src->frame_type;
368 dst->states = src->states;
369 dst->basis_states = src->basis_states;
370 dst->root_state = src->root_state;
371
372 memcpy (dst->wfainfo, src->wfainfo, sizeof (wfa_info_t));
373
374 if (dst->states == 0) /* nothing to do */
375 return;
376
377 memcpy (dst->final_distribution, src->final_distribution,
378 src->states * sizeof (real_t));
379 memcpy (dst->level_of_state, src->level_of_state,
380 src->states * sizeof (byte_t));
381 memcpy (dst->domain_type, src->domain_type,
382 src->states * sizeof (byte_t));
383 memcpy (dst->delta_state, src->delta_state,
384 src->states * sizeof (bool_t));
385 memcpy (dst->mv_tree, src->mv_tree,
386 src->states * MAXLABELS * sizeof (mv_t));
387 memcpy (dst->tree, src->tree,
388 src->states * MAXLABELS * sizeof (word_t));
389 memcpy (dst->x, src->x,
390 src->states * MAXLABELS * sizeof (word_t));
391 memcpy (dst->y, src->y,
392 src->states * MAXLABELS * sizeof (word_t));
393 memcpy (dst->y_state, src->y_state,
394 src->states * MAXLABELS * sizeof (word_t));
395 memcpy (dst->into, src->into,
396 src->states * MAXLABELS * (MAXEDGES + 1) * sizeof (word_t));
397 memcpy (dst->weight, src->weight,
398 src->states * MAXLABELS * (MAXEDGES + 1) * sizeof (real_t));
399 memcpy (dst->int_weight, src->int_weight,
400 src->states * MAXLABELS * (MAXEDGES + 1) * sizeof (word_t));
401 memcpy (dst->prediction, src->prediction,
402 src->states * MAXLABELS * sizeof (byte_t));
403 if (dst->y_column)
404 memcpy (dst->y_column, src->y_column,
405 src->states * MAXLABELS * sizeof (byte_t));
406 }
407
408 void
locate_subimage(unsigned orig_level,unsigned level,unsigned bintree,unsigned * x,unsigned * y,unsigned * width,unsigned * height)409 locate_subimage (unsigned orig_level, unsigned level, unsigned bintree,
410 unsigned *x, unsigned *y, unsigned *width, unsigned *height)
411 /*
412 * Compute pixel coordinates of the subimage which 'bintree' address is given.
413 * The level of the original image is 'orig_level' and the level of the
414 * subimage is 'level'.
415 *
416 * No return value.
417 *
418 * Side effects:
419 * '*x', '*y' coordinates of the upper left corner
420 * '*width', '*height' size of image
421 */
422 {
423 /*
424 * Compute coordinates of the subimage
425 */
426 *x = *y = 0; /* start at NW corner */
427 *width = width_of_level (level);
428 *height = height_of_level (level);
429
430 if (level > orig_level)
431 {
432 error ("size of tile must be less or equal than image size.");
433 return;
434 }
435 else if (bintree >= (unsigned) (1 << (orig_level - level)))
436 {
437 error ("address out of bounds.");
438 return;
439 }
440 else if (level < orig_level)
441 {
442 unsigned mask; /* mask for bintree -> xy conversion */
443 bool_t hor; /* 1 next subdivision is horizontal
444 0 next subdivision is vertical */
445 unsigned l = orig_level - 1; /* current level */
446
447 hor = orig_level % 2; /* start with vertival subdivision
448 for square image and vice versa */
449
450 for (mask = 1 << (orig_level - level - 1); mask; mask >>= 1, hor = !hor)
451 {
452 if (bintree & mask) /* change coordinates */
453 {
454 if (hor) /* horizontal subdivision */
455 *y += height_of_level (l);
456 else /* vertical subdivision */
457 *x += width_of_level (l);
458 }
459 l--;
460 }
461 }
462 }
463
464 void
compute_spiral(int * vorder,unsigned image_width,unsigned image_height,unsigned tiling_exp,bool_t inc_spiral)465 compute_spiral (int *vorder, unsigned image_width, unsigned image_height,
466 unsigned tiling_exp, bool_t inc_spiral)
467 /*
468 * Compute image tiling with spiral order.
469 * 'inc_spiral' specifies whether the spiral starts in the middle
470 * of the image (TRUE) or at the border (FALSE).
471 * 'image_width'x'image_height' define the size of the image.
472 * The image is split into 'tiling->exp' tiles.
473 *
474 * No return value.
475 *
476 * Side effects:
477 * vorder[] is filled with tiling permutation
478 */
479 {
480 unsigned x, y; /* current position */
481 unsigned xmin, xmax, ymin, ymax; /* boundaries for current line */
482 unsigned width, height; /* offset for each tile */
483 unsigned lx, ly, level; /* level x and y */
484 unsigned tiles; /* total number of tiles */
485 unsigned address; /* bintree address */
486
487 lx = log2 (image_width - 1) + 1;
488 ly = log2 (image_height - 1) + 1;
489 level = MAX(lx, ly) * 2 - ((ly == lx + 1) ? 1 : 0);
490 tiles = 1 << tiling_exp; /* Number of image tiles */
491 width = width_of_level (level - tiling_exp);
492 height = height_of_level (level - tiling_exp);
493 for (address = 0; address < tiles; address++)
494 {
495 unsigned x0, y0, width, height;
496
497 locate_subimage (level, level - tiling_exp, address,
498 &x0, &y0, &width, &height);
499 vorder [address] = (x0 < image_width && y0 < image_height) ? 0 : -1;
500 }
501
502 xmin = 0;
503 xmax = width_of_level (level);
504 ymin = 0;
505 ymax = height_of_level (level);
506 address = 0;
507
508 /*
509 * 1234
510 * CDE5 Traverse image in spiral order
511 * BGF6 starting at the top left corner
512 * A987
513 */
514 while (TRUE)
515 {
516 for (x = xmin, y = ymin; x < xmax; x += width) /* W>E */
517 {
518 while (vorder [address] == -1)
519 address++;
520 if (x < image_width && y < image_height) /* valid range */
521 vorder [address++] = xy_to_address (x, y, level, tiling_exp);
522 while (address < tiles && vorder [address] == -1)
523 address++;
524 }
525 ymin += height;
526
527 if (address >= tiles)
528 break;
529
530 for (x = xmax - width, y = ymin; y < ymax; y += height) /* N>S */
531 {
532 while (vorder [address] == -1)
533 address++;
534 if (x <= image_width && y <= image_height) /* valid range */
535 vorder [address++] = xy_to_address (x, y, level, tiling_exp);
536 while (address < tiles && vorder [address] == -1)
537 address++;
538 }
539 xmax -= width;
540
541 if (address >= tiles)
542 break;
543
544 for (x = xmax - width, y = ymax - width; x >= xmin; x -= width) /* E<W */
545 {
546 while (vorder [address] == -1)
547 address++;
548 if (x <= image_width && y <= image_height) /* valid range */
549 vorder [address++] = xy_to_address (x, y, level, tiling_exp);
550 while (address < tiles && vorder [address] == -1)
551 address++;
552 }
553 ymax -= height;
554
555 if (address >= tiles)
556 break;
557
558 for (x = xmin, y = ymax - height; y >= ymin; y -= height) /* S>N */
559 {
560 while (vorder [address] == -1)
561 address++;
562 if (x <= image_width && y <= image_height) /* valid range */
563 vorder [address++] = xy_to_address (x, y, level, tiling_exp);
564 while (address < tiles && vorder [address] == -1)
565 address++;
566 }
567 xmin += width;
568
569 if (address >= tiles)
570 break;
571 }
572
573 if (inc_spiral)
574 {
575 int i = 0, j = tiles - 1;
576
577 while (i < j)
578 {
579 int tmp;
580
581 while (vorder [i] == -1)
582 i++;
583 while (vorder [j] == -1)
584 j--;
585
586 tmp = vorder [i];
587 vorder [i] = vorder [j];
588 vorder [j] = tmp;
589 i++;
590 j--;
591 }
592 }
593 /*
594 * Print tiling info
595 */
596 {
597 unsigned number;
598
599 for (number = 0, address = 0; address < tiles; address++)
600 if (vorder [address] != -1)
601 debug_message ("number %d: address %d",
602 number++, vorder [address]);
603 }
604 }
605
606 bool_t
find_range(unsigned x,unsigned y,unsigned band,const wfa_t * wfa,unsigned * range_state,unsigned * range_label)607 find_range (unsigned x, unsigned y, unsigned band,
608 const wfa_t *wfa, unsigned *range_state, unsigned *range_label)
609 /*
610 * Find a range ('*range_state', '*range_label') that contains
611 * pixel ('x', 'y') in the iven color 'band'.
612 *
613 * Return value:
614 * TRUE on success, or FALSE if there is no such range
615 *
616 * Side effects:
617 * '*range_state' and '*range_label' are modified on success.
618 */
619 {
620 unsigned state, label;
621 unsigned first_state, last_state;
622 bool_t success = NO;
623
624 first_state = wfa->basis_states;
625 last_state = wfa->states;
626 if (wfa->wfainfo->color)
627 switch (band)
628 {
629 case Y:
630 first_state = wfa->basis_states;
631 last_state = wfa->tree [wfa->tree [wfa->root_state][0]][0];
632 break;
633 case Cb:
634 first_state = wfa->tree [wfa->tree [wfa->root_state][0]][0] + 1;
635 last_state = wfa->tree [wfa->tree [wfa->root_state][0]][1];
636 break;
637 case Cr:
638 first_state = wfa->tree [wfa->tree [wfa->root_state][0]][1] + 1;
639 last_state = wfa->states;
640 break;
641 default:
642 error ("unknown color component.");
643 }
644
645 for (state = first_state; state < last_state; state++)
646 for (label = 0; label < MAXLABELS; label++)
647 if (isrange (wfa->tree [state][label]))
648 if (x >= wfa->x [state][label] && y >= wfa->y [state][label]
649 && x < (unsigned) (wfa->x [state][label]
650 + width_of_level (wfa->level_of_state [state] - 1))
651 && y < (unsigned) (wfa->y [state][label]
652 + height_of_level (wfa->level_of_state [state] - 1)))
653 {
654 success = YES;
655 *range_state = state;
656 *range_label = label;
657
658 return success;
659 }
660
661 return success;
662 }
663
664 void
sort_ranges(unsigned state,unsigned * domain,range_sort_t * rs,const wfa_t * wfa)665 sort_ranges (unsigned state, unsigned *domain,
666 range_sort_t *rs, const wfa_t *wfa)
667 /*
668 * Generate list of ranges in coder order.
669 * 'state' is the current state of the call tree while 'domain' is the
670 * index of the last added WFA state.
671 *
672 * Side effects:
673 * 'domain' is incremented after recursion returns
674 * 'rs' is filled accordingly
675 *
676 * No return value.
677 */
678 {
679 unsigned label;
680
681 for (label = 0; label < MAXLABELS; label++)
682 {
683 if (isrange (wfa->tree [state][label]))
684 rs->range_subdivided [rs->range_no] = NO;
685 else
686 {
687 sort_ranges (wfa->tree [state][label], domain, rs, wfa);
688 rs->range_subdivided [rs->range_no] = YES;
689 }
690
691 rs->range_state [rs->range_no] = state;
692 rs->range_label [rs->range_no] = label;
693 rs->range_max_domain [rs->range_no] = *domain;
694 while (!usedomain (rs->range_max_domain [rs->range_no], wfa))
695 rs->range_max_domain [rs->range_no]--;
696
697 if (label == 1 || !rs->range_subdivided [rs->range_no])
698 rs->range_no++;
699 }
700
701 (*domain)++;
702 }
703
704 bool_t
locate_delta_images(wfa_t * wfa)705 locate_delta_images (wfa_t *wfa)
706 /*
707 * Locate all WFA states that are part of a delta approximation.
708 * I.e., these states are assigned to ranges that have been predicted
709 * via MC or ND.
710 *
711 * Return value:
712 * TRUE at least one state is part of a delta approximation
713 * FALSE no delta approximations in this WFA
714 *
715 * Side effects:
716 * 'wfa->delta [state][label]' is set accordingly.
717 */
718 {
719 unsigned state, label;
720 bool_t delta = NO;
721
722 for (state = wfa->root_state; state >= wfa->basis_states; state--)
723 wfa->delta_state [state] = NO;
724
725 for (state = wfa->root_state; state >= wfa->basis_states; state--)
726 for (label = 0; label < MAXLABELS; label++)
727 if (ischild (wfa->tree [state][label]))
728 if (wfa->mv_tree [state][label].type != NONE
729 || isedge (wfa->into [state][label][0])
730 || wfa->delta_state [state])
731 {
732 delta = YES;
733 wfa->delta_state [wfa->tree [state][label]] = YES;
734 }
735
736 return delta;
737 }
738
739 /*****************************************************************************
740
741 private code
742
743 ******************************************************************************/
744
745 static unsigned
xy_to_address(unsigned x,unsigned y,unsigned level,unsigned n)746 xy_to_address (unsigned x, unsigned y, unsigned level, unsigned n)
747 /*
748 * Compute bintree address of subimage at coordinates ('x', 'y').
749 * Size of original image is determined by 'level'.
750 * 'n' specifies number of iterations.
751 *
752 * Return value:
753 * address of subimage
754 */
755 {
756 unsigned address = 0;
757
758 while (n--)
759 {
760 address <<= 1;
761 if (--level % 2)
762 {
763 if (x & width_of_level (level))
764 address++;
765 }
766 else
767 {
768 if (y & height_of_level (level))
769 address++;
770 }
771 }
772
773 return address;
774 }
775