发信人: lofe ()感激生活(), 信区: Algorithm
标 题: Ash - model.c
发信站: 哈工大紫丁香 (Sun Sep 3 08:26:19 2000), 转信
#include <stdio.h>
#include <mem.h>
#include <alloc.h>
#include <stdlib.h>
#include "comp.h"
#include "arith.h"
#define MAX_CUM_FREQ 0x4000 /* maximum cumulative frequency */
struct model
{
int initial_level;
int match_level;
unsigned base_count;
unsigned sym_freq;
unsigned order_cum_freq [MAX_ORDER + 2];
unsigned order_sym_count [MAX_ORDER + 2];
};
/*
Define circular dictionary large enough to hold complete
set of active input symbols.
Extra entries are included in the dictionary corresponding
to a string of length equal to the maximum order to facilitate
searching across the end of the dictionary. This extra space
is allocated at the front of the dictionary, so that the first
few entries are never referenced directly.
An additional table is allocated consisting of one word entries
used to link equivalent dictionary entries where a hash table is
used to locate the start of each search chain.
The last character of the test string is used locate the
initial hash table entry. The hash table entries are stored
as an extension to the link table.
The link table is accessed through the use of macros to allow
easy access to this table when its size excceds 64K.
*/
#ifndef FAR_TABLES
static unsigned char dict [MAX_DICT];
static unsigned char base_level [MAX_DICT];
static unsigned int next_dict [MAX_DICT + HTBL1_SIZE];
#define DICT_WORD_PTR(i) ((unsigned *) (&dict [i]));
#define NEXT_DICT(i) next_dict [i]
#else
static unsigned char far *dict;
static unsigned char far *base_level;
#define DICT_WORD_PTR(i) ((unsigned far *) (&dict [i]));
#ifdef SPLIT_TABLES
static unsigned int far *next_dict [2];
#define NEXT_DICT(i) next_dict [i & 1] [i >> 1]
#else
static unsigned int far *next_dict;
#define NEXT_DICT(i) next_dict [i]
#endif
#endif
static unsigned int node;
static int new_symbol_count;
static unsigned int last_search_node;
static int max_order;
static int max_pos_size;
/*
Define table of entries for each order giving number of symbols
and total cumulative frequency for each order
*/
static struct model active_state;
static struct model last_state;
/*
Define set of save areas for the state at the potential start any string
The areas are used in rotation until a substring is matched equal to
the minimum string length. Normal symbol compression is performed
during the time that the substring matches the input data.
When the first non matching character is encountered, the lengths of
the string and the compressed symbols are compared. If the string
length is less, the output is repositioned as specified by the
state at the start of the string, and the string selection sequence
overwrites the output.
*/
static struct
{
int i;
struct coder_state cs;
struct model mod;
} save_state [MAX_STR_SAVE];
static int save_state_index;
static unsigned int string_pos;
static int string_len;
static int string_start;
static int skip_count;
/*
States used while testing for text string replacements
*/
static enum
{
STRING_WAIT, STRING_SEARCH, STRING_START, STRING_ACTIVE,
STRING_COMP,
} string_state;
/*
Define combined set of tables giving the order and
frequency count for each symbol encountered during dictionary scan
Also accumulate base frequency values for each order
*/
static unsigned char level [MAX_SYM];
static unsigned int freq [MAX_SYM];
static unsigned int base_freq [MAX_ORDER + 2];
static unsigned int dup_count = 0;
static int dup_char = -1;
/*
Build frequency table for zero and default orders
Used to initialize state tables at start of each dictionary scan
Always contains nonzero count for every symbol
Includes order for each symbol selecting zero or default orders
Initially set to all defaults with symbol frequency one
*/
static unsigned int sym_count_zero;
static unsigned int cum_freq_zero;
static unsigned int freq_zero [MAX_SYM];
static unsigned char order_zero [MAX_SYM];
/*
Prototypes
*/
static void clear_context (void);
static void scan_dict (int);
static void scale_freq_tbl (int, int);
static void calc_symbol_freq (int);
static void select_output_symbol (void);
static int decode_symbol (void);
static void update_model (int);
static void encode_symbol (struct model *);
static void generate_switch_code (struct model *);
static void generate_symbol_code (struct model *);
static void generate_value (unsigned, unsigned);
static int start_decode_string (void);
static int decode_active_state (void);
static int decode_string_char (void);
static unsigned decode_value (unsigned);
static unsigned switch_char_freq (unsigned, unsigned);
static void delete_dict_entry (int);
static void test_string_state (void);
static void clear_text_string (void);
static void check_string_cont (void);
static void test_string_start (unsigned pos, int n);
static void test_string_resume (unsigned pos, int n);
static void replace_text_string (void);
static int log2 (unsigned);
static void scale_binary_value (long, int *, unsigned *);
static void update_bit_len (unsigned, unsigned, int *, unsigned *);
static int find_string_len (void);
/*
Initialize model at start of compression or expansion
Alocate and initialize tables
*/
void InitModel (int n)
{
unsigned i;
InitCoder ();
active_state.initial_level = 1;
node = MAX_ORDER;
max_pos_size = log2 (NDICT - 1) + 1;
max_order = n;
if (max_order == 0) max_order = 1;
sym_count_zero = 0;
cum_freq_zero = 0;
#ifdef FAR_TABLES
dict = farmalloc (MAX_DICT * sizeof (unsigned char));
base_level = farmalloc (MAX_DICT * sizeof (unsigned char));
#ifndef SPLIT_TABLES
next_dict = farmalloc ((MAX_DICT + HTBL1_SIZE) * sizeof (unsigned int));
if (dict == NULL || base_level == NULL || next_dict == NULL)
{
printf ("Memory allocation failure\n");
exit (EXIT_FAILURE);
}
#else
next_dict [0] = farmalloc ((MAX_DICT + HTBL1_SIZE + 1) / 2 * sizeof (unsigned int));
next_dict [1] = farmalloc ((MAX_DICT + HTBL1_SIZE + 1) / 2 * sizeof (unsigned int));
if (dict == NULL || base_level == NULL || next_dict [1] == NULL)
{
printf ("Memory allocation failure\n");
exit (EXIT_FAILURE);
}
#endif /* SPLIT_TABLES */
#endif /* FAR_TABLES */
for (i = 0; i < MAX_SYM; i ++)
{
freq_zero [i] = 1;
order_zero [i] = 0;
}
for (i = 0; i < MAX_DICT + HTBL1_SIZE; i ++)
NEXT_DICT (i) = NIL_DICT_PTR;
for (i = 0; i < MAX_DICT; i ++)
{
dict [i] = 0;
base_level [i] = 0;
}
save_state_index = 0;
string_pos = 0;
string_len = 0;
string_start = 0;
skip_count = MIN_STR;
string_state = STRING_WAIT;
}
/*
Compress next symbol
*/
void CompressSymbol (int ch)
{
int i;
unsigned cfreq;
if (string_state == STRING_ACTIVE) check_string_cont ();
if (dup_count > max_order + 2)
{
++ active_state.order_cum_freq [max_order + 1];
++ freq [dup_char];
if (ch != dup_char)
{
for (i = 0, cfreq = 0; i < ch; i ++)
{
if (level [i] == level [ch]) cfreq += freq [i];
}
base_freq [level [ch]] = cfreq;
}
}
else
{
clear_context ();
for (i = 0; i < max_order + 2; i ++) base_freq [i] = 0;
scan_dict (ch);
}
for (i = 1; i <= active_state.initial_level; i ++)
{
while (active_state.order_cum_freq [i] > MAX_CUM_FREQ)
scale_freq_tbl (i, ch);
}
test_string_state ();
calc_symbol_freq (ch);
select_output_symbol ();
update_model (ch);
}
/*
Expand next symbol from input stream
*/
int ExpandSymbol (void)
{
int ch;
if (dup_count > max_order + 2)
{
++ active_state.order_cum_freq [max_order + 1];
++ freq [dup_char];
}
else
{
clear_context ();
scan_dict (0);
}
ch = string_len == 0 ? decode_symbol () : decode_string_char ();
update_model (ch);
return ch;
}
/*
Update tables used by model for new symbol
Link new symbol into dictionary
Delete oldest symbol in dictionary, if required
Update zero order frequencies if no higher level context found
*/
static void update_model (int ch)
{
int n;
NEXT_DICT (node) = NIL_DICT_PTR;
NEXT_DICT (last_search_node) = node;
last_search_node = node;
if (active_state.match_level < 2)
{
cum_freq_zero ++;
if (order_zero [ch])
freq_zero [ch] ++;
else
{
order_zero [ch] = 1;
sym_count_zero ++;
}
}
dict [node] = ch;
if (ch == dup_char)
dup_count ++;
else
{
dup_char = ch;
dup_count = 0;
}
n = active_state.match_level;
if (n == 0) n = 1;
base_level [node] = n;
delete_dict_entry (node + max_order);
active_state.initial_level = active_state.match_level;
if (active_state.initial_level <= max_order)
active_state.initial_level ++;
if (++ node == MAX_DICT)
{
node = MAX_ORDER;
for (n = 1; n <= max_order; n ++)
dict [MAX_ORDER - n] = dict [MAX_DICT - n];
}
}
/*
Delete oldest symbol from dictionary
Update frequency counts if added for lower order
*/
static void delete_dict_entry (int i)
{
unsigned int n;
int j;
n = i;
if (n >= MAX_DICT) n -= NDICT;
switch (base_level [n])
{
case 0:
break;
case 1:
j = dict [n];
cum_freq_zero --;
if (-- freq_zero [j] == 0)
{
order_zero [j] = 0;
freq_zero [j] = 1;
sym_count_zero --;
}
default:
j = dict [n - 1];
NEXT_DICT (j + MAX_DICT) = NEXT_DICT (n);
break;
}
}
/*
Initialize tables at start of dictionary scan
Establish counts based on low order tables
*/
static void clear_context (void)
{
int i;
for (i = 2; i < max_order + 2; i ++)
{
active_state.order_sym_count [i] = 0;
active_state.order_cum_freq [i] = 0;
}
active_state.order_sym_count [1] = sym_count_zero;
active_state.order_sym_count [0] = MAX_SYM - sym_count_zero;
active_state.order_cum_freq [1] = cum_freq_zero;
active_state.order_cum_freq [0] = MAX_SYM - sym_count_zero;
movmem (freq_zero, freq, sizeof freq);
movmem (order_zero, level, sizeof level);
}
/*
Perform search of dictionary to locate active contexts
Accumulate freqencies for all symbols encounered
Use initial character of input string to select the starting table value
*/
static void scan_dict (int base_char)
{
unsigned int k;
unsigned int jnode;
int ch;
int n;
last_search_node = dict [node - 1] + MAX_DICT;
jnode = NEXT_DICT (last_search_node);
while (jnode != NIL_DICT_PTR)
{
ch = dict [jnode];
for (n = 2; n < max_order + 1; n ++)
{
if (dict [node - n] != dict [jnode - n]) break;
}
switch (string_state)
{
case STRING_SEARCH:
case STRING_START:
test_string_start (jnode, n);
break;
case STRING_COMP:
test_string_resume (jnode, n);
break;
}
if (base_level [jnode] <= n)
{
k = level [ch];
if (k < n)
{
active_state.order_cum_freq [k] -= freq [ch];
active_state.order_sym_count [k] --;
active_state.order_cum_freq [n] ++;
active_state.order_sym_count [n] ++;
if (ch < base_char)
{
base_freq [k] -= freq [ch];
base_freq [n] ++;
}
level [ch] = n;
freq [ch] = 1;
if (n > active_state.initial_level) active_state.initial_level = n;
}
else
if (k == n)
{
active_state.order_cum_freq [n] ++;
freq [ch] ++;
if (ch < base_char) base_freq [n] ++;
}
}
last_search_node = jnode;
jnode = NEXT_DICT (jnode);
}
}
/*
Test for continued text substring
Executed before the start of each dictionary scan during compression
*/
static void check_string_cont (void)
{
int j;
j = string_pos + string_len;
if (j >= MAX_DICT) j -= NDICT;
if (dict [node - 1] == dict [j])
string_len ++;
else
string_state = STRING_COMP;
}
/*
Test for start of potential text substring
Executed during dictionary scan based on string state variable
*/
static void test_string_start (unsigned pos, int n)
{
if (n > MIN_STR)
{
string_pos = pos;
if (string_pos < MIN_STR + MAX_ORDER) string_pos += NDICT;
string_pos -= MIN_STR;
string_len = MIN_STR;
string_state = STRING_START;
}
}
static void test_string_resume (unsigned pos, int n)
{
if (n > string_len + 1)
{
string_state = STRING_ACTIVE;
string_len ++;
string_pos = pos;
if (string_pos < string_len + MAX_ORDER) string_pos += NDICT;
string_pos -= string_len;
}
else
if (n == max_order + 1)
{
unsigned i2, j2, n2;
i2 = node - max_order - 1;
j2 = pos - max_order - 1;
for (n2 = max_order + 1; n2 <= string_len + 1; n2 ++)
{
if (i2 < MAX_ORDER) i2 += NDICT;
if (j2 < MAX_ORDER) j2 += NDICT;
if (dict [i2 --] != dict [j2 --]) break;
}
if (n2 > string_len + 1)
{
string_state = STRING_ACTIVE;
string_len ++;
string_pos = pos;
if (string_pos < string_len + MAX_ORDER) string_pos += NDICT;
string_pos -= string_len;
}
}
}
/*
Test status of text substring match procedure
Performed after each dictionary scan
*/
static void test_string_state (void)
{
switch (string_state)
{
case STRING_WAIT:
save_state [string_start].mod = active_state;
SaveCoderState (&save_state [string_start].cs);
if (++ string_start == MAX_STR_SAVE) string_start = 0;
if (-- skip_count == 0) string_state = STRING_SEARCH;
break;
case STRING_SEARCH:
save_state [string_start].mod = active_state;
SaveCoderState (&save_state [string_start].cs);
if (++ string_start == MAX_STR_SAVE) string_start = 0;
break;
case STRING_ACTIVE:
if (string_len > MAX_STR)
{
string_len --;
clear_text_string ();
}
break;
case STRING_COMP:
clear_text_string ();
break;
}
}
/*
End of text substring
Test for minimum code length of dtring versus coded symbols
Reposition output and write string selection if less
Set up for start of next string
*/
static void clear_text_string (void)
{
int nbits;
int i;
if (string_len >= MIN_STR)
{
nbits = find_string_len ();
if (nbits > 0)
{
replace_text_string ();
i = node;
if (i <= string_len) i += NDICT;
i -= string_len + 1;
}
}
save_state [string_start].mod = last_state;
SaveCoderState (&save_state [string_start].cs);
if (++ string_start == MAX_STR_SAVE) string_start = 0;
encode_symbol (&last_state);
save_state [string_start].mod = active_state;
SaveCoderState (&save_state [string_start].cs);
if (++ string_start == MAX_STR_SAVE) string_start = 0;
skip_count = MIN_STR - 2;
string_len = 0;
string_state = STRING_WAIT;
}
/*
Estimate size of string reference
Returns size relative to actual length used by coded symbols
*/
static int find_string_len (void)
{
int nbits;
unsigned f;
struct model start_context;
unsigned i;
unsigned n;
unsigned j;
int m;
unsigned c1;
nbits = 0;
f = 0;
new_symbol_count = MAX_SYM;
m = save_state [string_start].mod.match_level;
start_context = save_state [string_start].mod;
/*
Accumulate switch characters for default context
Include start of string symbol
*/
do
{
new_symbol_count -= start_context.order_sym_count [m];
c1 = start_context.order_cum_freq [m];
n = switch_char_freq (start_context.order_sym_count [m], c1);
update_bit_len (n, c1 + n, &nbits, &f);
} while (-- m > 0);
c1 = start_context.order_cum_freq [0];
update_bit_len (1, c1, &nbits, &f);
/*
Include string length
*/
nbits += 6;
if (string_len - MIN_STR >= 63) nbits += 8;
/*
Calculate relative location of start of string
Output as bit count and offset
*/
update_bit_len (1, max_pos_size, &nbits, &f);
i = string_pos + string_len;
if (i >= MAX_DICT) i -= NDICT;
j = i < node ? node - i - 1 : node + NDICT - 1 - i;
nbits += log2 (j);
return CodeLength (&save_state [string_start].cs) - nbits;
}
/*
Generate coded symbols for text substring
Used when string length is less length used by actual symbols
*/
static void replace_text_string (void)
{
struct model start_context;
unsigned n;
unsigned i, j;
RestoreCoderState (&save_state [string_start].cs);
new_symbol_count = MAX_SYM;
start_context = save_state [string_start].mod;
/*
Output switch codes for default context and start string symbol
*/
start_context.match_level = 0;
start_context.base_count = start_context.order_cum_freq [0] - 1;
start_context.sym_freq = 1;
encode_symbol (&start_context);
/*
Output string length
*/
n = string_len - MIN_STR;
if (n < MAX_STR_CODE - 1)
generate_value (n, MAX_STR_CODE);
else
{
generate_value (MAX_STR_CODE - 1, MAX_STR_CODE);
generate_value (n + 1 - MAX_STR_CODE, 256);
}
/*
Determine relative location of start of string
*/
i = string_pos + string_len;
if (i >= MAX_DICT) i -= NDICT;
j = i < node ? node - i - 1 : node - i - 1 + NDICT;
n = 2;
if (j < 2)
i = 0;
else
{
for (i = 1; 2 * n <= j && n < 0x8000; i ++, n <<= 1);
j -= n;
}
/*
Output bit length of relative string location
*/
generate_value (i, max_pos_size);
/*
Output string location in 8 bit pices if required
*/
if (i > 8)
{
generate_value (j & 0xFF, 256);
j >>= 8;
n >>= 8;
}
generate_value (j, n);
}
/*
Scale frequency tables if total cumulative frequency exceeds maximum
Also recalculates frequencies for current input symbol
*/
static void scale_freq_tbl (int order, int ch)
{
int i;
unsigned cfreq;
unsigned t;
i = 0;
cfreq = 0;
if (level [ch] == order)
{
for (; i < ch; i ++)
{
if (level [i] == order)
{
t = (freq [i] + 1) >> 1;
freq [i] = t;
cfreq += t;
}
}
base_freq [order] = cfreq;
t = (freq [i] + 1) >> 1;
freq [i] = t;
i ++;
cfreq += t;
}
for (; i < MAX_CHAR_CODE; i ++)
{
if (level [i] == order)
{
t = (freq [i] + 1) >> 1;
freq [i] = t;
cfreq += t;
}
}
active_state.order_cum_freq [order] = cfreq;
}
/*
Determine symbol frequency counts for coder
*/
static void calc_symbol_freq (int ch)
{
int i;
active_state.match_level = level [ active_state.sym_freq = freq [ch];
if (active_state.match_level > 1)
active_state.base_count = base_freq [active_state.match_level];
else
{
active_state.base_count = 0;
for (i = 0; i < ch; i ++)
{
if (level [i] == active_state.match_level)
active_state.base_count += freq [i];
}
}
}
/*
Select state structure containing symbol to be output
Generate coded symbol value if required
Note that there is a one character delay during substring matching
so that the non matching character at end of string is not output
until after string replacement has occurred
*/
static void select_output_symbol (void)
{
switch (string_state)
{
case STRING_START:
last_state = active_state;
string_state = STRING_ACTIVE;
break;
case STRING_ACTIVE:
encode_symbol (&last_state);
last_state = active_state;
break;
default:
encode_symbol (&active_state);
break;
}
}
/*
Generate coded value for symbol defined by input state variable
State includes symbol frequencies and all values used by coder
*/
static void encode_symbol (struct model *cptr)
{
int i;
new_symbol_count = MAX_SYM;
i = cptr -> match_level;
while (i < cptr -> initial_level)
{
new_symbol_count -= cptr -> order_sym_count [cptr -> initial_level];
generate_switch_code (cptr);
cptr -> initial_level --;
}
new_symbol_count -= cptr -> order_sym_count [i];
generate_symbol_code (cptr);
}
/*
Generate code for switch character to select next lower context
Input consists of state variable for symbol
*/
static void generate_switch_code (struct model *cptr)
{
unsigned c1;
unsigned n, m;
n = cptr -> initial_level;
c1 = cptr -> order_cum_freq [n];
m = switch_char_freq (cptr -> order_sym_count [n], c1);
EncodeArith (c1, m, c1 + m);
}
/*
Generate code for symbol defined by input state variable
*/
static void generate_symbol_code (struct model *cptr)
{
unsigned int c1, c2, c3;
int n;
n = cptr -> initial_level;
c1 = cptr -> base_count;
c2 = cptr -> sym_freq;
c3 = cptr -> order_cum_freq [n];
if (n > 0) c3 += switch_char_freq (cptr -> order_sym_count [n], c3);
EncodeArith (c1, c2, c3);
}
/*
Estimate frequency to be allocated to the switch character
Use number of symbols referenced in current context and the
number of unreferenced symbols so far
Value should reflect probability of encountering a symbol
already present in the active context
*/
static unsigned switch_char_freq (unsigned scount, unsigned cmax)
{ unsigned n;
n = (scount + 1) * new_symbol_count / (scount + new_symbol_count);
if (n + cmax > MAX_CUM_FREQ) n = MAX_CUM_FREQ + 1 - cmax;
return n;
}
/*
End of compression procedure
Terminate active substring processing
Close arithmetic coder and flush output
*/
void CloseModel (void)
{
if (string_state == STRING_ACTIVE) clear_text_string ();
CloseCoder ();
}
/*
Decode next input symbol from input stream
Test for context switch and repeat until non switch symbol encountered
*/
static int decode_symbol (void)
{
int ch;
new_symbol_count = MAX_SYM;
active_state.match_level = active_state.initial_level;
new_symbol_count -= active_state.order_sym_count [active_state.match_level];
ch = decode_active_state ();
while (ch == SWITCH_SYM)
{
active_state.match_level --;
new_symbol_count -= active_state.order_sym_count [active_state.match_level];
ch = decode_active_state ();
}
if (ch == START_STRING) ch = start_decode_string ();
return ch;
}
/*
Start of string symbol encountered
Extract string length and position from input stream
Returns first character in string
*/
static int start_decode_string (void)
{
unsigned i, j, k;
unsigned n;
string_len = decode_value (MAX_STR_CODE);
if (string_len == MAX_STR_CODE - 1) string_len += decode_value (256);
string_len += MIN_STR;
i = decode_value (max_pos_size);
if (i == 0)
{
i = 2;
j = decode_value (2);
}
else
if (i > 8)
{
j = decode_value (256);
i -= 8;
n = 1 << i;
k = decode_value (n);
k += n;
k <<= 8;
j += k;
}
else
{
n = 1 << i;
j = decode_value (n);
j += n;
}
string_pos = node < j + MAX_ORDER ? node + NDICT - j : node - j;
return decode_string_char ();
}
/*
Locate next character in text substring
Increment string pointers and decrement length
Set parameters used for updating state variable
*/
static int decode_string_char (void)
{
int ch;
unsigned int j;
ch = dict [string_pos];
active_state.match_level = level [ch];
string_len --;
if (++ string_pos == MAX_DICT) string_pos = MAX_ORDER;
last_search_node = dict [node - 1] + MAX_DICT;
j = NEXT_DICT (last_search_node);
while (j != NIL_DICT_PTR)
{
last_search_node = j;
j = NEXT_DICT (j);
}
return ch;
}
/*
Extract next value from input stream
Search frequency tables to convert to symbol
Update arithmetic decoder using symbol frequencies
*/
static int decode_active_state (void)
{
unsigned c1, c2, c3;
unsigned sym;
unsigned m;
int i;
int n;
n = active_state.match_level;
c2 = active_state.order_cum_freq [n];
while (c2 > MAX_CUM_FREQ)
{
scale_freq_tbl (n, END_OF_FILE);
c2 = active_state.order_cum_freq [n];
}
m = n > 0 ? switch_char_freq (active_state.order_sym_count [n], c2) : 0;
c3 = c2 + m;
sym = DecodeArith (c3);
if (sym < c2)
{
c1 = 0;
for (i = 0; i < MAX_SYM; i ++)
{
if (level [i] == n)
{
m = freq [i];
c1 += m;
if (sym < c1) break;
}
}
c1 -= m;
}
else
{
c1 = c2;
i = SWITCH_SYM;
}
UpdateDecoder (c1, m, c3);
return i;
}
/*
Generate coded output for a constant value within a fixed range
Value is treated as a symbol with frequency one
*/
static void generate_value (unsigned value, unsigned range)
{
EncodeArith (value, 1, range);
}
/*
Extract constant value within fixed range
Each possible value is treated as symbol with frequency one
*/
static unsigned decode_value (unsigned range)
{ unsigned value;
value = DecodeArith (range);
UpdateDecoder (value, 1, range);
return value;
}
/*
Determine integer value of base 2 logarithm of integer value
Use smallest power of two less than input value
*/
static int log2 (unsigned n)
{
int i;
for (i = 0; n > 1; i ++, n >>= 1);
return i;
}
/*
Scale binary value as part of log calulation
Input is a binary fraction (32 bits, 16 binary places)
Extract integer log to base 2
Return fractional part and accumulate integer part
*/
static void scale_binary_value (long x, int *nbits, unsigned *frac)
{
int i;
i = log2 ((unsigned) (x >> 16));
*nbits += i;
*frac = (unsigned) (x >> i);
}
/*
Estimate bit size of arithmetic coded values
Input consists of symbol frequency (p) and cumulative frequency (q)
Actual bit size is log to base 2 of (q / p)
Maintain intermediate values as:
n + log2 (1 + f)
where n is integer and f is the remainder (between 0 and 1.0)
stored as a 16 bit binary fraction.
The pair (nbits, frac) contains the starting value for the bit length
This is updated to include the latest symbol size
*/
static void update_bit_len (unsigned p, unsigned q, int *nbits, unsigned *frac)
{
long x;
unsigned f2;
x = ((long) q << 16) / p;
scale_binary_value (x, nbits, &f2);
x = (long) f2 * (long) *frac;
x >>= 16;
x += f2;
x += *frac;
x += 0x10000L;
scale_binary_value (x, nbits, frac);
}
--
Every problem has a solution.
infosite@263.net
※ 修改:．haojs 于 Sep 3 08:23:48 修改本文．[FROM: bbs.hit.edu.cn]
--
※ 转寄:．武汉白云黄鹤站 bbs.whnet.edu.cn．[FROM: bbs.hit.edu.cn]
--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: haojs.bbs@bbs.whnet.]