encode.c

Arithmetic coding source code. A very good software for arithmetic coding.

/*
** Three modes:
**   (A) Read stdin and output frequencies to stdout  freq_count()
**   (B) Read freq file, encode entire file           two_pass_encoding()
**   (C) Code file in blocks of x symbols.            one_pass_encoding()
**
** Format of freqs file:
**      sizeof(ulong)*8 bits is number of symbols (n)
**      n "uints" to go into A[0..n-1]
*/
#include "mytypes.h"
#include "bitio.h"
#include "code.h"
#include "mysort.h"
#include "nqsort.h"
#include "inplace.h"
#include "interp.h"

ulong num_source_syms = 0;
ulong num_source_bits = 0;
ulong num_interp_bits = 0;
ulong num_unary_bits = 0;
ulong num_header_bits = 0;
ulong num_padding_bits = 0;
ulong last_num_source_syms = 0;
ulong last_num_source_bits = 0;
ulong last_num_interp_bits = 0;
ulong last_num_unary_bits = 0;
ulong last_num_header_bits = 0;
ulong last_num_padding_bits = 0;

extern char verbose, very_verbose;

    /* Canonical coding arrays */
ulong min_code[L];
ulong lj_base[L];
ulong  offset[L];

    /* prototypes */
void build_canonical_arrays(uint cw_lens[], uint);
void process_block(uint *block, uint b, uint *freq, uint *syms, FILE *out_file);
uint one_pass_freq_count(uint block[], uint b, uint freq[],uint syms[], uint);
void build_codes(FILE *f, uint *, uint *, uint n);
void generate_mapping(uint [], uint [], uint [], uint, uint);

/*
**
** print a wee little summary of where all the money went...
*/
void
print_summary_stats() {
    fprintf(stderr,"\nMessage symbols       : %10lu\n", num_source_syms);
    fprintf(stderr,"Header bits           : %10lu (%5.2f bps)\n",
	    num_header_bits, (double)num_header_bits/num_source_syms);
    fprintf(stderr,"Subalphabet selection : %10lu (%5.2f bps)\n",
	    num_interp_bits, (double)num_interp_bits/num_source_syms);
    fprintf(stderr,"Codeword lengths      : %10lu (%5.2f bps)\n",
	    num_unary_bits, (double)num_unary_bits/num_source_syms);
    fprintf(stderr,"Message bits          : %10lu (%5.2f bps)\n",
	    num_source_bits, (double)num_source_bits/num_source_syms);
    fprintf(stderr,"Padding bits          : %10lu (%5.2f bps)\n",
	    num_padding_bits, (double)num_padding_bits/num_source_syms);
    fprintf(stderr,"Total bytes           : %10lu (%5.2f bps)\n",
	    (num_interp_bits+num_unary_bits+num_header_bits+num_padding_bits+num_source_bits)/ 8,
	    (double)(num_interp_bits+num_unary_bits+num_header_bits+num_padding_bits+num_source_bits)/ num_source_syms);
} /* print_summary_stats() */


/*
**
** print a wee little summary for each block of where all the money went...
** try and keep the format strings in BLOCK_SUMMARY_HEADINGS and the 
** fprintf of the data the "same"
*/
#define BLOCK_SUMMARY_HEADINGS \
do { \
    fprintf(stderr,"-------------------------------------------------------------------------------\n");\
    fprintf(stderr,"%4s %10s %10s %8s %8s %8s %8s %8s %8s\n", \
        "Num","max","Total","header","alpha","codeword","message","padding","Total"); \
    fprintf(stderr,"%4s %10s %10s %8s %8s %8s %8s %8s %8s\n", \
        "syms","symbol","bytes","","select","lengths","","",""); \
    if (very_verbose == BLOCK_OUTPUT_IN_BYTES) \
        fprintf(stderr,"%4s %10s %10s %8s %8s %8s %8s %8s %8s\n", \
            "","","","(bits)","(bits)","(bits)","(bits)","(bits)","(bits)"); \
    else \
        fprintf(stderr,"%4s %10s %10s %8s %8s %8s %8s %8s %8s\n", \
            "","","","(bps)","(bps)","(bps)","(bps)","(bps)","(bps)"); \
    fprintf(stderr,"-------------------------------------------------------------------------------\n");\
} while(0);

void
print_block_summary(ulong num_distinct, ulong num_syms, ulong max_symbol) {
    double i = (double)(num_interp_bits - last_num_interp_bits);
    double u = (double)(num_unary_bits  - last_num_unary_bits);
    double s = (double)(num_source_bits - last_num_source_bits);
    double h = (double)(num_header_bits - last_num_header_bits);
    double p = (double)(num_padding_bits - last_num_padding_bits);
    double n = (double)num_syms;

    if (very_verbose == BLOCK_OUTPUT_IN_BYTES) 
        fprintf(stderr,"%4lu %10lu %10lu %8lu %8lu %8lu %8lu %8lu %8lu\n",
                    num_distinct, max_symbol, (ulong)(i+u+s+h+p)/8, (ulong)h, (ulong)i, (ulong)u, (ulong)s, (ulong)p, (ulong)(i+u+s+h+p));
    else
        fprintf(stderr,"%4lu %10lu %10lu %8.2f %8.2f %8.2f %8.2f %8.2f %8.2f\n",
                    num_distinct, max_symbol, (ulong)(i+u+s+h+p)/8, h/n, i/n, u/n, s/n, p/n, (i+u+s+h+p)/n);

} /* print_block_summary() */





/*
** Canonical encode.  cwlens[] contains codeword lens, mapping[] contains 
** ordinal symbol mapping.
*/
inline 
uint output(FILE *f, uint i, uint mapping[], uint cwlens[]) {

    uint sym_num = mapping[i];            // ordinal symbol number

    uint len = cwlens[i];

    ulong cw = min_code[len-1] + (sym_num - offset[len-1]);
//fprintf(stderr, "currlen %4u symbol %6u -> %6u (cw = %8lx)\n",len, i,sym_num,cw);
//fflush(stderr);
    OUTPUT_ULONG(f, cw, len);
    num_source_bits += len;
	num_source_syms += 1;

    return len;
} /* output() */

/*
**
*/
void
two_pass_encoding(FILE *in_file, FILE *freq_file, FILE *out_file) {
    uint n, max_symbol, i, b;
    uint *block, *up;           /* buffer for input symbols */ 

    uint *syms;                 /* working array for mapping */
    uint *freq;                 /* working array for freq */

    SHOW_MEM(L, ulong) /* min_code */
    SHOW_MEM(L, ulong) /* lj_base */
    SHOW_MEM(L, ulong) /* offset */
    allocate(block, uint, BUFF_SIZE);

    fread(&max_symbol,sizeof(uint),1, freq_file);

    allocate(syms, uint, max_symbol+2);
    allocate(freq, uint, max_symbol+2);
    SHOW_MEM(max_symbol+2, uint)
    SHOW_MEM(max_symbol+2, uint)

    fread(freq+1, sizeof(uint), max_symbol, freq_file);
    freq[EOF_SYMBOL] = 1;
    n = 0;
    for(i = 0 ; i <= max_symbol ; i++)
        if (freq[i] > 0)
            syms[n++] = i;

    START_OUTPUT(out_file);

	OUTPUT_ULONG(out_file, MAGIC, sizeof(ulong)*8);
	num_header_bits += sizeof(ulong)*8;

    build_codes(out_file, syms, freq, n);

    while ((b=fread(block,sizeof(uint),BUFF_SIZE, in_file)) > 0)
        for(up = block ; up < block + b ; up++) {
            CHECK_SYMBOL_RANGE(*up+1);
            (void)output(out_file, *up+1, syms, freq);
        }

    uint temp = output(out_file, EOF_SYMBOL, syms, freq);

    OUTPUT_ULONG(out_file, 0, sizeof(ulong)*8 - temp);    // pad last codeword
    num_padding_bits += sizeof(ulong)*8 - temp;

    OUTPUT_ULONG(out_file, 0, LOG2_MAX_SYMBOL);           // last block n = 0
    num_header_bits += LOG2_MAX_SYMBOL;

    FINISH_OUTPUT(out_file);

    free(block);
    free(syms);
    free(freq);
    
    if (verbose) print_summary_stats();
} /* two_pass_encoding() */


/*
** count the freqs, build the codes, write the codes, "...and I am spent."
*/
inline void
process_block(uint *block, uint b, uint *freq, uint *syms, FILE *out_file) {
    uint *up, n;
    uint max_symbol, temp;

    if (very_verbose > 0) {      // assuming 1 cmp is faster than 6 assignments
        last_num_source_syms  = num_source_syms  ;  
        last_num_source_bits  = num_source_bits  ;
        last_num_interp_bits  = num_interp_bits  ;
        last_num_unary_bits   = num_unary_bits   ;
        last_num_header_bits  = num_header_bits  ;
        last_num_padding_bits = num_padding_bits ;
    }

        /* add 1 to handle zero symbols , and set max_symbol */
    max_symbol = 0;
    for(up = block ; up < block + b ; up++) {
        *up = *up + 1;
        if (*up > max_symbol) 
           max_symbol = *up;
        CHECK_SYMBOL_RANGE(*up);
    }

    n = one_pass_freq_count(block, b, freq, syms, max_symbol);
    
	build_codes(out_file, syms, freq, n);
    
	for(up = block ; up < block + b ; up++)
	    (void)output(out_file, *up, syms, freq);
    
	temp = output(out_file, EOF_SYMBOL, syms, freq);
    
	OUTPUT_ULONG(out_file, 0, sizeof(ulong)*8 - temp); // pad last codeword
    num_padding_bits += sizeof(ulong)*8 - temp;

    if (very_verbose > 0 )
        print_block_summary(n, b+1, max_symbol);  // b+1 for EOB symbol
}/* process_block() */

/*
** A block_size == 0 indicates that an input symbol of 0 marks EOB.
*/
void
one_pass_encoding(FILE *in_file, FILE *out_file, int block_size) {
    uint *block, *up; /* buffer for input symbols */ 
    uint b;
    uint *syms;                 /* working array for mapping */
    uint *freq;                 /* working array for freq */
    uint num_blocks=0;
    
    uint current_array_size;

    if (block_size == 0)
        current_array_size = INITIAL_BLOCK_SIZE;
    else
        current_array_size = block_size;
    
    allocate(block, uint, current_array_size+1);

    SHOW_MEM(current_array_size+1,uint)
    SHOW_MEM(L, ulong) /* min_code */
    SHOW_MEM(L, ulong) /* lj_base */