diff options
Diffstat (limited to 'converter/other/fiasco/lib/arith.c')
| -rw-r--r-- | converter/other/fiasco/lib/arith.c | 440 |
1 files changed, 220 insertions, 220 deletions
diff --git a/converter/other/fiasco/lib/arith.c b/converter/other/fiasco/lib/arith.c index e61e753e..7fac0c6d 100644 --- a/converter/other/fiasco/lib/arith.c +++ b/converter/other/fiasco/lib/arith.c @@ -1,7 +1,7 @@ /* - * arith.c: Adaptive arithmetic coding and decoding + * arith.c: Adaptive arithmetic coding and decoding * - * Written by: Ullrich Hafner + * Written by: Ullrich Hafner * * This file is part of FIASCO (Fractal Image And Sequence COdec) * Copyright (C) 1994-2000 Ullrich Hafner @@ -26,7 +26,7 @@ /****************************************************************************** - public code + public code ******************************************************************************/ @@ -37,7 +37,7 @@ alloc_encoder (bitfile_t *output) * Initialize the arithmetic coder. * * Return value: - * A pointer to the new coder structure + * A pointer to the new coder structure */ { arith_t *arith = Calloc (1, sizeof (arith_t)); @@ -47,7 +47,7 @@ alloc_encoder (bitfile_t *output) arith->low = LOW; arith->high = HIGH; arith->underflow = 0; - arith->file = output; + arith->file = output; return arith; } @@ -62,9 +62,9 @@ free_encoder (arith_t *arith) * No return value. */ { - u_word_t low; /* start of the current code range */ - u_word_t high; /* end of the current code range */ - u_word_t underflow; /* number of underflow bits pending */ + u_word_t low; /* start of the current code range */ + u_word_t high; /* end of the current code range */ + u_word_t underflow; /* number of underflow bits pending */ bitfile_t *output; assert (arith); @@ -94,22 +94,22 @@ encode_symbol (unsigned symbol, arith_t *arith, model_t *model) * symbol counts are rescaled). * * Return value: - * information content of the encoded symbol. + * information content of the encoded symbol. * * Side effects: - * 'model' is updated (probability distribution) - * 'arith' is updated (coder state) + * 'model' is updated (probability distribution) + * 'arith' is updated (coder state) */ { - u_word_t low_count; /* lower bound of 'symbol' interval */ - u_word_t high_count; /* upper bound of 'symbol' interval */ - u_word_t scale; /* range of all 'm' symbol intervals */ - unsigned range; /* range of current interval */ - unsigned index; /* index of probability model */ - u_word_t low; /* start of the current code range */ - u_word_t high; /* end of the current code range */ - u_word_t underflow; /* number of underflow bits pending */ - bitfile_t *output; /* output file */ + u_word_t low_count; /* lower bound of 'symbol' interval */ + u_word_t high_count; /* upper bound of 'symbol' interval */ + u_word_t scale; /* range of all 'm' symbol intervals */ + unsigned range; /* range of current interval */ + unsigned index; /* index of probability model */ + u_word_t low; /* start of the current code range */ + u_word_t high; /* end of the current code range */ + u_word_t underflow; /* number of underflow bits pending */ + bitfile_t *output; /* output file */ assert (model && arith); @@ -123,28 +123,28 @@ encode_symbol (unsigned symbol, arith_t *arith, model_t *model) assert (high > low); - if (model->order > 0) /* order-'n' model*/ + if (model->order > 0) /* order-'n' model*/ { - unsigned power; /* multiplicator */ + unsigned power; /* multiplicator */ unsigned i; /* * Compute index of the probability model to use. * See init_model() for more details. */ - power = 1; /* multiplicator */ - index = 0; /* address of prob. model */ + power = 1; /* multiplicator */ + index = 0; /* address of prob. model */ for (i = 0; i < model->order; i++) /* generate a M-nary number */ { - index += model->context [i] * power; - power *= model->symbols; + index += model->context [i] * power; + power *= model->symbols; } - index *= model->symbols + 1; /* we need space for M + 1 elements */ + index *= model->symbols + 1; /* we need space for M + 1 elements */ for (i = 0; i < model->order - 1; i++) - model->context [i] = model->context [i + 1]; + model->context [i] = model->context [i + 1]; model->context [i] = symbol; } else @@ -163,7 +163,7 @@ encode_symbol (unsigned symbol, arith_t *arith, model_t *model) RESCALE_OUTPUT_INTERVAL; - if (model->scale > 0) /* adaptive model */ + if (model->scale > 0) /* adaptive model */ { unsigned i; @@ -171,23 +171,23 @@ encode_symbol (unsigned symbol, arith_t *arith, model_t *model) * Update probability model */ for (i = symbol + 1; i <= model->symbols; i++) - model->totals [index + i]++; + model->totals [index + i]++; if (model->totals [index + model->symbols] > model->scale) /* scaling */ { - for (i = 1; i <= model->symbols; i++) - { - model->totals [index + i] >>= 1; - if (model->totals [index + i] <= model->totals [index + i - 1]) - model->totals [index + i] = model->totals [index + i - 1] + 1; - } + for (i = 1; i <= model->symbols; i++) + { + model->totals [index + i] >>= 1; + if (model->totals [index + i] <= model->totals [index + i - 1]) + model->totals [index + i] = model->totals [index + i - 1] + 1; + } } } /* * Store interval values */ - arith->low = low; - arith->high = high; + arith->low = low; + arith->high = high; arith->underflow = underflow; return - log2 ((high_count - low_count) / (real_t) scale); @@ -195,8 +195,8 @@ encode_symbol (unsigned symbol, arith_t *arith, model_t *model) void encode_array (bitfile_t *output, const unsigned *data, const unsigned *context, - const unsigned *c_symbols, unsigned n_context, unsigned n_data, - unsigned scaling) + const unsigned *c_symbols, unsigned n_context, unsigned n_data, + unsigned scaling) /* * Arithmetic coding of #'n_data' symbols given in the array 'data'. * If 'n_context' > 1 then a number (context [n]) is assigned to every @@ -207,10 +207,10 @@ encode_array (bitfile_t *output, const unsigned *data, const unsigned *context, * No return value. */ { - u_word_t **totals; /* probability model */ + u_word_t **totals; /* probability model */ if (!n_context) - n_context = 1; /* always use one context */ + n_context = 1; /* always use one context */ assert (output && c_symbols && data); assert (n_context == 1 || context); @@ -224,13 +224,13 @@ encode_array (bitfile_t *output, const unsigned *data, const unsigned *context, for (c = 0; c < n_context; c++) { - unsigned i; + unsigned i; - totals [c] = Calloc (c_symbols [c] + 1, sizeof (u_word_t)); - totals [c][0] = 0; + totals [c] = Calloc (c_symbols [c] + 1, sizeof (u_word_t)); + totals [c][0] = 0; - for (i = 0; i < c_symbols [c]; i++) - totals [c][i + 1] = totals [c][i] + 1; + for (i = 0; i < c_symbols [c]; i++) + totals [c][i + 1] = totals [c][i] + 1; } } @@ -238,52 +238,52 @@ encode_array (bitfile_t *output, const unsigned *data, const unsigned *context, * Encode array elements */ { - u_word_t low = 0; /* Start of the current code range */ - u_word_t high = 0xffff; /* End of the current code range */ - u_word_t underflow = 0; /* Number of underflow bits pending */ + u_word_t low = 0; /* Start of the current code range */ + u_word_t high = 0xffff; /* End of the current code range */ + u_word_t underflow = 0; /* Number of underflow bits pending */ unsigned n; for (n = 0; n < n_data; n++) { - u_word_t low_count; /* lower bound of 'symbol' interval */ - u_word_t high_count; /* upper bound of 'symbol' interval */ - u_word_t scale; /* range of all 'm' symbol intervals */ - unsigned range; /* current range */ - int d; /* current data symbol */ - int c; /* context of current data symbol */ - - d = data [n]; - c = n_context > 1 ? context [n] : 0; - - scale = totals [c][c_symbols [c]]; - low_count = totals [c][d]; - high_count = totals [c][d + 1]; - - /* - * Rescale high and low for the new symbol. - */ - range = (high - low) + 1; - high = low + (u_word_t) ((range * high_count) / scale - 1); - low = low + (u_word_t) ((range * low_count) / scale); - RESCALE_OUTPUT_INTERVAL; - - /* - * Update probability models - */ - { - unsigned i; - - for (i = d + 1; i < c_symbols [c] + 1; i++) - totals [c][i]++; - - if (totals [c][c_symbols [c]] > scaling) /* scaling */ - for (i = 1; i < c_symbols [c] + 1; i++) - { - totals [c][i] >>= 1; - if (totals [c][i] <= totals [c][i - 1]) - totals [c][i] = totals [c][i - 1] + 1; - } - } + u_word_t low_count; /* lower bound of 'symbol' interval */ + u_word_t high_count; /* upper bound of 'symbol' interval */ + u_word_t scale; /* range of all 'm' symbol intervals */ + unsigned range; /* current range */ + int d; /* current data symbol */ + int c; /* context of current data symbol */ + + d = data [n]; + c = n_context > 1 ? context [n] : 0; + + scale = totals [c][c_symbols [c]]; + low_count = totals [c][d]; + high_count = totals [c][d + 1]; + + /* + * Rescale high and low for the new symbol. + */ + range = (high - low) + 1; + high = low + (u_word_t) ((range * high_count) / scale - 1); + low = low + (u_word_t) ((range * low_count) / scale); + RESCALE_OUTPUT_INTERVAL; + + /* + * Update probability models + */ + { + unsigned i; + + for (i = d + 1; i < c_symbols [c] + 1; i++) + totals [c][i]++; + + if (totals [c][c_symbols [c]] > scaling) /* scaling */ + for (i = 1; i < c_symbols [c] + 1; i++) + { + totals [c][i] >>= 1; + if (totals [c][i] <= totals [c][i - 1]) + totals [c][i] = totals [c][i - 1] + 1; + } + } } /* * Flush arithmetic encoder @@ -299,7 +299,7 @@ encode_array (bitfile_t *output, const unsigned *data, const unsigned *context, { unsigned c; for (c = 0; c < n_context; c++) - Free (totals [c]); + Free (totals [c]); Free (totals); } } @@ -312,7 +312,7 @@ alloc_decoder (bitfile_t *input) * 16 input bits from the stream 'input'. * * Return value: - * A pointer to the new decoder structure + * A pointer to the new decoder structure */ { @@ -338,7 +338,7 @@ free_decoder (arith_t *arith) * No return value. * * Side effects: - * structure 'arith' is discarded. + * structure 'arith' is discarded. */ { assert (arith); @@ -357,22 +357,22 @@ decode_symbol (arith_t *arith, model_t *model) * decoding the symbol (if necessary also rescale the symbol counts). * * Return value: - * decoded symbol + * decoded symbol * * Side effects: - * 'model' is updated (probability distribution) - * 'arith' is updated (decoder state) + * 'model' is updated (probability distribution) + * 'arith' is updated (decoder state) */ { - unsigned range; /* range of current interval */ - unsigned count; /* value in the current interval */ - unsigned index; /* index of probability model */ - unsigned symbol; /* decoded symbol */ - u_word_t scale; /* range of all 'm' symbol intervals */ - u_word_t low; /* start of the current code range */ - u_word_t high; /* end of the current code range */ - u_word_t code; /* the present input code value */ - bitfile_t *input; /* input file */ + unsigned range; /* range of current interval */ + unsigned count; /* value in the current interval */ + unsigned index; /* index of probability model */ + unsigned symbol; /* decoded symbol */ + u_word_t scale; /* range of all 'm' symbol intervals */ + u_word_t low; /* start of the current code range */ + u_word_t high; /* end of the current code range */ + u_word_t code; /* the present input code value */ + bitfile_t *input; /* input file */ assert (arith && model); @@ -386,25 +386,25 @@ decode_symbol (arith_t *arith, model_t *model) assert (high > low); - if (model->order > 0) /* order-'n' model */ + if (model->order > 0) /* order-'n' model */ { - unsigned power; /* multiplicator */ + unsigned power; /* multiplicator */ unsigned i; /* * Compute index of the probability model to use. * See init_model() for more details. */ - power = 1; /* multiplicator */ - index = 0; /* address of prob. model */ + power = 1; /* multiplicator */ + index = 0; /* address of prob. model */ for (i = 0; i < model->order; i++) /* generate a m-nary number */ { - index += model->context[i] * power; - power *= model->symbols; + index += model->context[i] * power; + power *= model->symbols; } - index *= model->symbols + 1; /* we need space for m + 1 elements */ + index *= model->symbols + 1; /* we need space for m + 1 elements */ } else index = 0; @@ -414,15 +414,15 @@ decode_symbol (arith_t *arith, model_t *model) count = ((code - low + 1) * scale - 1) / range; for (symbol = model->symbols; count < model->totals [index + symbol]; - symbol--) + symbol--) ; - if (model->order > 0) /* order-'n' model */ + if (model->order > 0) /* order-'n' model */ { unsigned i; for (i = 0; i < model->order - 1; i++) - model->context [i] = model->context [i + 1]; + model->context [i] = model->context [i + 1]; model->context [i] = symbol; } @@ -430,8 +430,8 @@ decode_symbol (arith_t *arith, model_t *model) * Compute interval boundaries */ { - u_word_t low_count; /* lower bound of 'symbol' interval */ - u_word_t high_count; /* upper bound of 'symbol' interval */ + u_word_t low_count; /* lower bound of 'symbol' interval */ + u_word_t high_count; /* upper bound of 'symbol' interval */ low_count = model->totals [index + symbol]; high_count = model->totals [index + symbol + 1]; @@ -441,7 +441,7 @@ decode_symbol (arith_t *arith, model_t *model) RESCALE_INPUT_INTERVAL; - if (model->scale > 0) /* adaptive model */ + if (model->scale > 0) /* adaptive model */ { unsigned i; @@ -449,15 +449,15 @@ decode_symbol (arith_t *arith, model_t *model) * Update probability model */ for (i = symbol + 1; i <= model->symbols; i++) - model->totals [index + i]++; + model->totals [index + i]++; if (model->totals [index + model->symbols] > model->scale) /* scaling */ { - for (i = 1; i <= model->symbols; i++) - { - model->totals [index + i] >>= 1; - if (model->totals [index + i] <= model->totals [index + i - 1]) - model->totals [index + i] = model->totals [index + i - 1] + 1; - } + for (i = 1; i <= model->symbols; i++) + { + model->totals [index + i] >>= 1; + if (model->totals [index + i] <= model->totals [index + i - 1]) + model->totals [index + i] = model->totals [index + i - 1] + 1; + } } } @@ -473,8 +473,8 @@ decode_symbol (arith_t *arith, model_t *model) unsigned * decode_array (bitfile_t *input, const unsigned *context, - const unsigned *c_symbols, unsigned n_context, - unsigned n_data, unsigned scaling) + const unsigned *c_symbols, unsigned n_context, + unsigned n_data, unsigned scaling) /* * Arithmetic decoding of #'n_data' symbols. * If 'n_context' > 1 then a number (context [n]) is assigned to every @@ -483,14 +483,14 @@ decode_array (bitfile_t *input, const unsigned *context, * Rescale probability models if range > 'scaling'. * * Return value: - * pointer to array containing the decoded symbols + * pointer to array containing the decoded symbols */ { - unsigned *data; /* array to store decoded symbols */ - u_word_t **totals; /* probability model */ + unsigned *data; /* array to store decoded symbols */ + u_word_t **totals; /* probability model */ if (n_context < 1) - n_context = 1; /* always use one context */ + n_context = 1; /* always use one context */ assert (input && c_symbols); assert (n_context == 1 || context); @@ -505,13 +505,13 @@ decode_array (bitfile_t *input, const unsigned *context, for (c = 0; c < n_context; c++) { - unsigned i; + unsigned i; - totals [c] = Calloc (c_symbols [c] + 1, sizeof (u_word_t)); - totals [c][0] = 0; + totals [c] = Calloc (c_symbols [c] + 1, sizeof (u_word_t)); + totals [c][0] = 0; - for (i = 0; i < c_symbols [c]; i++) - totals [c][i + 1] = totals [c][i] + 1; + for (i = 0; i < c_symbols [c]; i++) + totals [c][i + 1] = totals [c][i] + 1; } } @@ -520,54 +520,54 @@ decode_array (bitfile_t *input, const unsigned *context, */ { u_word_t code = get_bits (input, 16); /* The present input code value */ - u_word_t low = 0; /* Start of the current code range */ - u_word_t high = 0xffff; /* End of the current code range */ + u_word_t low = 0; /* Start of the current code range */ + u_word_t high = 0xffff; /* End of the current code range */ unsigned n; for (n = 0; n < n_data; n++) { - u_word_t scale; /* range of all 'm' symbol intervals */ - u_word_t low_count; /* lower bound of 'symbol' interval */ - u_word_t high_count; /* upper bound of 'symbol' interval */ - unsigned count; /* value in the current interval */ - unsigned range; /* current interval range */ - unsigned d; /* current data symbol */ - unsigned c; /* context of current data symbol */ - - c = n_context > 1 ? context [n] : 0; - - assert (high > low); - scale = totals [c][c_symbols [c]]; - range = (high - low) + 1; - count = (((code - low) + 1 ) * scale - 1) / range; - - for (d = c_symbols [c]; count < totals [c][d]; d--) /* next symbol */ - ; - low_count = totals [c][d]; - high_count = totals [c][d + 1]; - - high = low + (u_word_t) ((range * high_count) / scale - 1 ); - low = low + (u_word_t) ((range * low_count) / scale ); - RESCALE_INPUT_INTERVAL; - - /* - * Updata probability models - */ - { - unsigned i; - - for (i = d + 1; i < c_symbols [c] + 1; i++) - totals [c][i]++; - - if (totals [c][c_symbols [c]] > scaling) /* scaling */ - for (i = 1; i < c_symbols [c] + 1; i++) - { - totals [c][i] >>= 1; - if (totals [c][i] <= totals [c][i - 1]) - totals [c][i] = totals [c][i - 1] + 1; - } - } - data [n] = d; + u_word_t scale; /* range of all 'm' symbol intervals */ + u_word_t low_count; /* lower bound of 'symbol' interval */ + u_word_t high_count; /* upper bound of 'symbol' interval */ + unsigned count; /* value in the current interval */ + unsigned range; /* current interval range */ + unsigned d; /* current data symbol */ + unsigned c; /* context of current data symbol */ + + c = n_context > 1 ? context [n] : 0; + + assert (high > low); + scale = totals [c][c_symbols [c]]; + range = (high - low) + 1; + count = (((code - low) + 1 ) * scale - 1) / range; + + for (d = c_symbols [c]; count < totals [c][d]; d--) /* next symbol */ + ; + low_count = totals [c][d]; + high_count = totals [c][d + 1]; + + high = low + (u_word_t) ((range * high_count) / scale - 1 ); + low = low + (u_word_t) ((range * low_count) / scale ); + RESCALE_INPUT_INTERVAL; + + /* + * Updata probability models + */ + { + unsigned i; + + for (i = d + 1; i < c_symbols [c] + 1; i++) + totals [c][i]++; + + if (totals [c][c_symbols [c]] > scaling) /* scaling */ + for (i = 1; i < c_symbols [c] + 1; i++) + { + totals [c][i] >>= 1; + if (totals [c][i] <= totals [c][i - 1]) + totals [c][i] = totals [c][i - 1] + 1; + } + } + data [n] = d; } INPUT_BYTE_ALIGN (input); } @@ -579,7 +579,7 @@ decode_array (bitfile_t *input, const unsigned *context, unsigned c; for (c = 0; c < n_context; c++) - Free (totals [c]); + Free (totals [c]); Free (totals); } @@ -599,17 +599,17 @@ alloc_model (unsigned m, unsigned scale, unsigned n, unsigned *totals) * the initial counts. * * Return value: - * a pointer to the new probability model structure. + * a pointer to the new probability model structure. * * Note: We recommend a small size of the alphabet because no escape codes * are used to encode/decode previously unseen symbols. * */ { - model_t *model; /* new probability model */ - unsigned num; /* number of contexts to allocate */ - bool_t cont; /* continue flag */ - bool_t dec; /* next order flag */ + model_t *model; /* new probability model */ + unsigned num; /* number of contexts to allocate */ + bool_t cont; /* continue flag */ + bool_t dec; /* next order flag */ unsigned i; /* @@ -630,56 +630,56 @@ alloc_model (unsigned m, unsigned scale, unsigned n, unsigned *totals) model->totals = Calloc (num * (model->symbols + 1), sizeof (unsigned)); for (i = 0; i < model->order; i++) - model->context[i] = 0; /* start with context 0,0, .. ,0 */ + model->context[i] = 0; /* start with context 0,0, .. ,0 */ cont = YES; - while (cont) /* repeat while context != M ... M */ + while (cont) /* repeat while context != M ... M */ { - int power; /* multiplicator */ - int index; /* index of probability model */ + int power; /* multiplicator */ + int index; /* index of probability model */ /* * There are m^n different contexts: * Let "context_1 context_2 ... context_n symbol" be the current input * stream then the index of the probability model is given by: * index = context_1 * M^0 + context_2 * M^1 + ... + context_n * M^(n-1) */ - power = 1; /* multiplicator */ - index = 0; /* address of prob. model */ + power = 1; /* multiplicator */ + index = 0; /* address of prob. model */ - for (i = 0; i < model->order; i++) /* generate a m-nary number */ + for (i = 0; i < model->order; i++) /* generate a m-nary number */ { - index += model->context[i] * power; - power *= model->symbols; + index += model->context[i] * power; + power *= model->symbols; } - index *= model->symbols + 1; /* size of each model is m + 1 */ + index *= model->symbols + 1; /* size of each model is m + 1 */ - model->totals [index + 0] = 0; /* always zero */ + model->totals [index + 0] = 0; /* always zero */ for (i = 1; i <= model->symbols; i++) /* prob of each symbol is 1/m or - as given in totals */ - model->totals[index + i] = model->totals [index + i - 1] - + (totals ? totals [i - 1] : 1); - - if (model->order == 0) /* order-0 model */ - cont = NO; - else /* try next context */ - for (i = model->order - 1, dec = YES; dec; i--) - { - dec = NO; - model->context[i]++; - if (model->context[i] >= model->symbols) - { - /* change previous context */ - model->context[i] = 0; - if (i > 0) /* there's still a context remaining */ - dec = YES; - else - cont = NO; /* all context models initialized */ - } - } + as given in totals */ + model->totals[index + i] = model->totals [index + i - 1] + + (totals ? totals [i - 1] : 1); + + if (model->order == 0) /* order-0 model */ + cont = NO; + else /* try next context */ + for (i = model->order - 1, dec = YES; dec; i--) + { + dec = NO; + model->context[i]++; + if (model->context[i] >= model->symbols) + { + /* change previous context */ + model->context[i] = 0; + if (i > 0) /* there's still a context remaining */ + dec = YES; + else + cont = NO; /* all context models initialized */ + } + } } for (i = 0; i < model->order; i++) - model->context[i] = 0; /* start with context 0,0, .. ,0 */ + model->context[i] = 0; /* start with context 0,0, .. ,0 */ return model; } @@ -693,13 +693,13 @@ free_model (model_t *model) * No return value. * * Side effects: - * struct 'model' is discarded + * struct 'model' is discarded */ { if (model != NULL) { if (model->context != NULL) - Free (model->context); + Free (model->context); Free (model->totals); Free (model); } |