diff options
Diffstat (limited to 'converter/other/fiasco/input/nd.c')
| -rw-r--r-- | converter/other/fiasco/input/nd.c | 237 |
1 files changed, 237 insertions, 0 deletions
diff --git a/converter/other/fiasco/input/nd.c b/converter/other/fiasco/input/nd.c new file mode 100644 index 00000000..1a68bfbf --- /dev/null +++ b/converter/other/fiasco/input/nd.c @@ -0,0 +1,237 @@ +/* + * nd.c: Input of prediction tree + * + * Written by: Ullrich Hafner + * + * This file is part of FIASCO («F»ractal «I»mage «A»nd «S»equence «CO»dec) + * Copyright (C) 1994-2000 Ullrich Hafner <hafner@bigfoot.de> + */ + +/* + * $Date: 2000/06/14 20:50:13 $ + * $Author: hafner $ + * $Revision: 5.1 $ + * $State: Exp $ + */ + +#include "config.h" + +#include "types.h" +#include "macros.h" +#include "error.h" + +#include "bit-io.h" +#include "arith.h" +#include "misc.h" +#include "list.h" +#include "wfalib.h" + +#include "nd.h" + +/***************************************************************************** + + prototypes + +*****************************************************************************/ + +static void +decode_nd_coefficients (unsigned total, wfa_t *wfa, bitfile_t *input); +static unsigned +decode_nd_tree (wfa_t *wfa, bitfile_t *input); + +/***************************************************************************** + + public code + +*****************************************************************************/ + +void +read_nd (wfa_t *wfa, bitfile_t *input) +/* + * Read transitions of the nondetermistic 'wfa' part from 'input' stream. + * ND is used only at levels {'wfa->p_min_level', ... , 'wfa->p_max_level'}. + * + * Side effects: + * 'wfa->into' and 'wfa->weights' are filled with the decoded values + */ +{ + unsigned total = decode_nd_tree (wfa, input); + + if (total > 0) + decode_nd_coefficients (total, wfa, input); +} + +/***************************************************************************** + + private code + +*****************************************************************************/ + +static unsigned +decode_nd_tree (wfa_t *wfa, bitfile_t *input) +/* + * Read 'wfa' prediction tree of given 'input' stream. + * + * No return value. + * + * Side effects: + * 'wfa->into' is filled with the decoded values + */ +{ + lqueue_t *queue; /* queue of states */ + int next, state; /* state and its current child */ + unsigned total = 0; /* total number of predicted states */ + u_word_t sum0, sum1; /* Probability model */ + u_word_t code; /* The present input code value */ + u_word_t low; /* Start of the current code range */ + u_word_t high; /* End of the current code range */ + + /* + * Initialize arithmetic decoder + */ + code = get_bits (input, 16); + low = 0; + high = 0xffff; + sum0 = 1; + sum1 = 11; + + queue = alloc_queue (sizeof (int)); + state = wfa->root_state; + queue_append (queue, &state); + + /* + * Traverse the WFA tree in breadth first order (using a queue). + */ + while (queue_remove (queue, &next)) + { + unsigned label; + + if (wfa->level_of_state [next] > wfa->wfainfo->p_max_level + 1) + { + /* + * Nondetermismn is not allowed at levels larger than + * 'wfa->wfainfo->p_max_level'. + */ + for (label = 0; label < MAXLABELS; label++) + if (ischild (state = wfa->tree [next][label])) + queue_append (queue, &state); /* continue with childs */ + } + else if (wfa->level_of_state [next] > wfa->wfainfo->p_min_level) + { + for (label = 0; label < MAXLABELS; label++) + if (ischild (state = wfa->tree [next][label])) + { + unsigned count; /* Current interval count */ + unsigned range; /* Current interval range */ + + count = (((code - low) + 1) * sum1 - 1) / ((high - low) + 1); + if (count < sum0) + { + /* + * Decode a '0' symbol + * First, the range is expanded to account for the + * symbol removal. + */ + range = (high - low) + 1; + high = low + (u_word_t) ((range * sum0) / sum1 - 1 ); + RESCALE_INPUT_INTERVAL; + /* + * Update the frequency counts + */ + sum0++; + sum1++; + if (sum1 > 50) /* scale the symbol frequencies */ + { + sum0 >>= 1; + sum1 >>= 1; + if (!sum0) + sum0 = 1; + if (sum0 >= sum1) + sum1 = sum0 + 1; + } + if (wfa->level_of_state [state] > wfa->wfainfo->p_min_level) + queue_append (queue, &state); + } + else + { + /* + * Decode a '1' symbol + * First, the range is expanded to account for the + * symbol removal. + */ + range = (high - low) + 1; + high = low + (u_word_t) ((range * sum1) / sum1 - 1); + low = low + (u_word_t) ((range * sum0) / sum1); + RESCALE_INPUT_INTERVAL; + /* + * Update the frequency counts + */ + sum1++; + if (sum1 > 50) /* scale the symbol frequencies */ + { + sum0 >>= 1; + sum1 >>= 1; + if (!sum0) + sum0 = 1; + if (sum0 >= sum1) + sum1 = sum0 + 1; + } + append_edge (next, 0, -1, label, wfa); + total++; + } + } + } + } + free_queue (queue); + + INPUT_BYTE_ALIGN (input); + + return total; +} + +static void +decode_nd_coefficients (unsigned total, wfa_t *wfa, bitfile_t *input) +/* + * Read #'total' weights of nondeterministic part of 'wfa' + * of given 'input' stream. + * 'frame' gives the current frame number. + * + * No return value. + * + * Side effects: + * 'wfa->weights' is filled with the decoded values. + */ +{ + unsigned *coefficients; /* array of factors to encode */ + unsigned *ptr; /* pointer to current factor */ + + /* + * Decode array of coefficients stored with arithmetic coding + */ + { + const int scaling = 50; /* scaling factor of prob. model */ + unsigned c_symbols = 1 << (wfa->wfainfo->dc_rpf->mantissa_bits + 1); + + ptr = coefficients = decode_array (input, NULL, &c_symbols, 1, + total, scaling); + } + + /* + * Fill 'wfa->weights' with decoded coefficients + */ + { + unsigned state, label; + + for (state = wfa->basis_states; state < wfa->states; state++) + for (label = 0; label < MAXLABELS; label++) + if (ischild (wfa->tree [state][label]) + && isedge (wfa->into [state][label][0])) + { + wfa->weight [state][label][0] = btor (*ptr++, + wfa->wfainfo->dc_rpf); + wfa->int_weight [state][label][0] + = wfa->weight [state][label][0] * 512 + 0.5; + } + } + Free (coefficients); +} |