/*** 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...*/voidprint_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);voidprint_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() *//****/voidtwo_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 voidprocess_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.*/voidone_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 */