arithmetic_encode.c

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

/* ARITHMETIC ENCODING 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 buffered for output                 */
static int S_bits_to_go;	/* Number of bits free in buffer            */


/* INITIALIZE FOR BIT OUTPUT. */

start_outputing_bits()
{   S_buffer = 0;				/* Buffer is empty to start */
    S_bits_to_go= 8;				/* with.                    */
}


/* OUTPUT A BIT. */

#define output_bit(bit) do \
{   buffer >>= 1; if (bit) buffer |= 0x80; \
    bits_to_go -= 1; \
    if (bits_to_go==0) { \
        putc(buffer,stdout); \
        bits_to_go = 8; \
    } \
} while (0)


/* FLUSH OUT THE LAST BITS. */

done_outputing_bits()
{   putc(S_buffer>>S_bits_to_go,stdout);
}


/* OUTPUT BITS PLUS FOLLOWING OPPOSITE BITS. */

#define bit_plus_follow(bit) do \
{   output_bit(bit); \
    while (bits_to_follow>0) { \
        output_bit(!bit); \
        bits_to_follow -= 1; \
    } \
} while(0)


/* CURRENT STATE OF THE ENCODING. */

static code_value S_low, S_high;/* Ends of the current code region          */
static long S_bits_to_follow;	/* Number of opposite bits to output after  */
				/* the next bit.                            */


/* START ENCODING A STREAM OF SYMBOLS. */

start_encoding()
{   S_low = 0;					/* Full code range.         */
    S_high = Top_value;
    S_bits_to_follow = 0;			/* No bits to follow next.  */
}


/* ENCODE A SYMBOL. */

encode_symbol(symbol,P_cum_freq)
    int symbol;			/* Symbol to encode                         */
    int P_cum_freq[];		/* Cumulative symbol frequencies            */
{   register code_value low, high;
    {   register long range;
        register int *cum_freq;
        cum_freq = P_cum_freq;
        range = (long)(S_high-S_low)+1;
        high = S_low +				/* Narrow the code region   */
          (range*cum_freq[symbol-1])/cum_freq[0]-1;/* to that allotted to   */
        low = S_low + 				/* this symbol.             */
        (range*cum_freq[symbol])/cum_freq[0];
    }
    {   register int H;
        register long bits_to_follow;
        register int buffer, bits_to_go;
        H = Half;
        bits_to_follow = S_bits_to_follow;
        buffer = S_buffer; bits_to_go = S_bits_to_go;
        for (;;) {				/* Loop to output bits.     */
            if (high<H) {
                bit_plus_follow(0);		/* Output 0 if in low half. */
            } 
            else if (low>=H) {			/* Output 1 if in high half.*/
                bit_plus_follow(1);
                low -= H;
                high -= H;			/* Subtract offset to top.  */
            }
            else if (low>=First_qtr		/* Output an opposite bit   */
                  && high<Third_qtr) {		/* later if in middle half. */
                bits_to_follow += 1;
                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.     */
        }
        S_bits_to_follow = bits_to_follow;
        S_buffer = buffer; S_bits_to_go = bits_to_go;
    }
    S_low = low; S_high = high; 
}


/* FINISH ENCODING THE STREAM. */

done_encoding()
{   register code_value low, high;
    register long bits_to_follow;
    register int buffer, bits_to_go;
    low = S_low; high = S_high; 
    bits_to_follow = S_bits_to_follow;
    buffer = S_buffer; bits_to_go = S_bits_to_go;
    bits_to_follow += 1;			/* Output two bits that     */
    if (S_low<First_qtr) bit_plus_follow(0);	/* select the quarter that  */
    else bit_plus_follow(1);			/* the current code range   */
    S_low = low; S_high = high; 		/* contains.                */
    S_bits_to_follow = bits_to_follow;
    S_buffer = buffer; S_bits_to_go = bits_to_go;
}