inplace.c

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

#include "code.h"

/*
Adapted by aht to allow a level of indirection.
Tue Sep 16 09:58:43 EST 1997

        The method for calculating codelengths in function
        calculate_minimum_redundancy is described in 

        @inproceedings{mk95:wads,
                author = "A. Moffat and J. Katajainen",
                title = "In-place calculation of minimum-redundancy codes",
                booktitle = "Proc. Workshop on Algorithms and Data Structures",
                address = "Kingston University, Canada",
                publisher = "LNCS 955, Springer-Verlag",
                Month = aug,
                year = 1995,
                editor = "S.G. Akl and F. Dehne and J.-R. Sack",
                pages = "393-402",
        }

        The abstract of that paper may be fetched from 
        http://www.cs.mu.oz.au/~alistair/abstracts/wads95.html
        A revised version is currently being prepared.

        Written by
		Alistair Moffat, [e-mail],
		Jyrki Katajainen, [e-mail]
	November 1996.
*/

/*** Function to calculate in-place a minimum-redundancy code
     Parameters:
        freq[0..M]    array of n symbol frequencies, unsorted
        syms[0..n-1]  array of n pointers into freq[], sorted increasing freq
        n             number of symbols
*/
void
calculate_minimum_redundancy(uint freq[], uint syms[], int n) {
        int root;                  /* next root node to be used */
        int leaf;                  /* next leaf to be used */
        int next;                  /* next value to be assigned */
        int avbl;                  /* number of available nodes */
        int used;                  /* number of internal nodes */
        uint dpth;                  /* current depth of leaves */

        /* check for pathological cases */
        if (n==0) { return; }
        if (n==1) { freq[syms[0]] = 0; return; }

        /* first pass, left to right, setting parent pointers */
        freq[syms[0]] += freq[syms[1]]; root = 0; leaf = 2;
        for (next=1; next < n-1; next++) {
                /* select first item for a pairing */
                if (leaf>=n || freq[syms[root]]<freq[syms[leaf]]) {
                        freq[syms[next]]   = freq[syms[root]]; 
                        freq[syms[root++]] = next;
                } else
                        freq[syms[next]] = freq[syms[leaf++]];

                /* add on the second item */
                if (leaf>=n || (root<next && freq[syms[root]]<freq[syms[leaf]])) {
                        freq[syms[next]] += freq[syms[root]]; 
                        freq[syms[root++]] = next;
                } else
                        freq[syms[next]] += freq[syms[leaf++]];
        }
        
        /* second pass, right to left, setting internal depths */
        freq[syms[n-2]] = 0;
        for (next=n-3; next>=0; next--)
                freq[syms[next]] = freq[syms[freq[syms[next]]]]+1;

        /* third pass, right to left, setting leaf depths */
        avbl = 1; used = dpth = 0; root = n-2; next = n-1;
        while (avbl>0) {
                while (root>=0 && freq[syms[root]]==dpth) {
                        used++; root--;
                }
                while (avbl>used) {
                        freq[syms[next--]] = dpth; avbl--;
                }
                avbl = 2*used; dpth++; used = 0;
        }
}