arithmetic_decode.c

学过数据压缩的朋友都知道, arithmetic encode是为了弥补哈夫曼编码对浮点数压缩的问题而提出的, 希望对大家有帮助

/* ARITHMETIC DECODING ALGORITHM. */

/* (C) Copyright 1987, Radford Neal. 

   Permission is granted to use this program for research purposes. Please
   note that this code was written to provide performance figures. I am
   well aware that it is not documented to the standards of production
   code. You're on your own. */


#include "arithmetic_coding.h"
#include <stdio.h>


/* THE BIT BUFFER. */

static int S_buffer;		/* Bits waiting to be input                 */
static int S_bits_to_go;	/* Number of bits still in buffer           */


/* INITIALIZE BIT INPUT. */

start_inputing_bits()
{   S_bits_to_go = 0;				/* Buffer starts out with   */
}						/* no bits in it.           */


/* INPUT A BIT. */

#define add_input_bit(v) do \
{   bits_to_go -= 1; \
    if (bits_to_go<0) { \
        buffer = getc(stdin); \
        bits_to_go = 7; \
    } \
    v += buffer&1; \
    buffer >>= 1; \
} while (0)


/* CURRENT STATE OF THE DECODING. */

static code_value S_value;	/* Currently-seen code value                */
static code_value S_low, S_high;/* Ends of current code region              */


/* START DECODING A STREAM OF SYMBOLS. */

start_decoding()
{   register int i;
    register int buffer, bits_to_go;
    buffer = S_buffer; bits_to_go = S_bits_to_go;
    S_value = 0;				/* Input bits to fill the   */
    for (i = 1; i<=Code_value_bits; i++) {	/* code value.              */
        S_value += S_value; add_input_bit(S_value);
    }
    S_low = 0;					/* Full code range.         */
    S_high = Top_value;
    S_buffer = buffer; S_bits_to_go = bits_to_go;
}


/* DECODE THE NEXT SYMBOL. */

int decode_symbol(P_cum_freq)
    int P_cum_freq[];		/* Cumulative symbol frequencies            */
{   int symbol;	
    register code_value low, high, value;
    low = S_low; high = S_high; value = S_value;
    {   register int *cum_freq;
        register int cum;
        register int *p;			
        long range;
        cum_freq = P_cum_freq;
        range = (long)(high-low)+1;
        cum = 					/* Find cum freq for value. */
          (((long)(value-low)+1)*cum_freq[0]-1)/range;
        p = &cum_freq[1];			/* Then find symbol.        */
        while (*p++>cum) ;
        symbol = p-&cum_freq[1];
        high = low +				/* Narrow the code region   */
          (range*cum_freq[symbol-1])/cum_freq[0]-1;/* to that allotted to   */
        low = low + 				/* tis symbol.              */
          (range*cum_freq[symbol])/cum_freq[0];
    }
    {   register int H;
        register int buffer, bits_to_go;
        buffer = S_buffer; bits_to_go = S_bits_to_go;
        H = Half;
        for (;;) {				/* Loop to get rid of bits. */
            if (high<H) {
                /* nothing */			/* Expand low half.         */
            } 
            else if (low>=H) {			/* Expand high half.        */
                value -= H;
                low -= H;			/* Subtract offset to top.  */
                high -= H;
            }
            else if (low>=First_qtr		/* Expand middle half.      */
                  && high<Third_qtr) {
                value -= First_qtr;
                low -= First_qtr;		/* Subtract offset to middle*/
                high -= First_qtr;
            }
            else break;				/* Otherwise exit loop.     */
            low += low;
            high += high; high += 1;		/* Scale up code range.     */
            value += value;			/* Move in next input bit.  */
            add_input_bit(value);
        }
        S_buffer = buffer; S_bits_to_go = bits_to_go;
    }
    S_low = low; S_high = high; S_value = value;
    return symbol;
}