/* MIGHTY HUFFMAN COMPRESSOR! TOO LARGE FOR WORDS! hunpack.c, (c) MPA 1995 */

#include "harp1.h"

/* {{{ Constants and definitions! */

const dw = 8;
const pw = dw + 1;
const de = 1 << dw;
const maxnodes = (2 << dw);
const tw = 2; /* Node type width */
const probw = 12; /* Probability width */
const nw = pw + pw + probw + tw; /* Complete node width */

#define  TYPE(x)  (((((x) \\ pw) \\ pw) \\ probw) <-  tw)
#define  PROB(x)  ((((x) \\ pw) \\ pw) <- probw)
#define  LEFT(x)  (((x) \\ pw) <- pw)
#define  RIGHT(x) (((x) \\  0) <- pw)
#define  NODE(l, r, p, t) ((t)@(p)@(l)@(r))

#define nodes(x)      general[false @ (x)]          /* 2 ^ pw wide */
#define dict(x)       general[true @ false @ (x)]    /* 2 ^ dw wide */

/* Heap lefts and rights */
#define left(x)  (((x) <- (pw - 1)) @ false)
#define right(x) (((x) <- (pw - 1)) @ true)

const ROOT = 2 : tw;
const LEAF = 1 : tw;

const NULL = 0 : pw;
const MINP = 1 : pw;           /* Pointer to first (minimum) element in heap */
const MAXP = (1 << dw) : pw;   /* Pointer to last element in heap */
const no_pointer     = 0 : pw;
const no_probability = 1 : probw;

const max = 1 << dw;
const half_max = (max div 2) - 1;

const codew = 16;

/* }}} */

void main(chan(in)  STDIN             : dw,
	  chan(out) STDOUT            : codew,
	  eram general[2 << pw] = harp1wram : nw)
{
    int data          : dw;
    int input_counter : pw;

    int a, b, x, y, z : nw;
    int i, n, objs, swsc_i, swsc_j : pw;
    bool did_swap;

    int code : codew;
    bool flag;

    chan bool bitstream;
    bool b0, b1, b2, b3;
    bool b4, b5, b6, b7;

    /* {{{ swap_with_smaller_child */

    void swap_with_smaller_child() {

	x, did_swap = nodes(swsc_i), 0;
	swsc_j, y = left(swsc_i), nodes(left(swsc_i));

	if (left(swsc_i) .<=. n) {

	    if (right(swsc_i) .<=. n) {

		z = nodes(right(swsc_i));
		if (PROB(z) .<. PROB(y))
		    swsc_j, y = right(swsc_i), nodes(right(swsc_i));

	    }

	    if (PROB(y) .<. PROB(x)) { 
		nodes(swsc_i) = y;       
		par {
		    nodes(swsc_j) = x;
		    did_swap = 1;
		}
	    }

	}

    }

    /* }}} */
    /* {{{ bubble_down */

    void bubble_down() {
	do {
	    swap_with_smaller_child();  
	    swsc_i = swsc_j;
	} while (did_swap & (~((swsc_i \\ (pw - 2)) <- 1)));
    }

    /* }}} */
    /* {{{ build_heap */

    void build_heap() {
	i, n = half_max, max;       
	do {                       
	    swsc_i, i = i, i - 1;   
	    bubble_down();
	} while (i != 0);
    }

    /* }}} */
    /* {{{ build_histogram */

/* Build histogram from 256 pieces of input */

    void build_histogram() {
	input_counter = 0;
	do {
	    par {
		STDIN ? data;
		x = nodes(false @ STDIN);
	    }
	    par {
		nodes(false @ data) = NODE(false @ data, no_pointer,
					   PROB(x) + 1, ROOT | LEAF);
		input_counter = input_counter + 1;
	    }
	} while (input_counter != 0);
    }

    /* }}} */
    /* {{{ fix_heap */

    void fix_heap() {
	/* Fixity to make the heap heap-shaped */
	x = nodes(NULL);
	nodes(MAXP) = x;
	build_heap();
    }

    /* }}} */
    /* {{{ huffman */

    void huffman() {

	objs, n = max, max;

	do {

	    /* take the minimum one */
	    a = nodes(MINP);

	    /* restore heap ordering with minimum one outside the heap */
	    y = nodes(n);
	    nodes(n) = NODE(LEFT(a), RIGHT(a),
			    no_probability, TYPE(a) & LEAF);
	    nodes(MINP), n, swsc_i = y, n - 1, 1;   
	    bubble_down();                   

	    /* take the next minimum one */
	    b = nodes(MINP);

	    /* place it right outside the heap, no longer root */
	    objs = objs + 1;
	    nodes(objs) = NODE(LEFT(b), RIGHT(b),
			       no_probability, TYPE(b) & LEAF);

	    /* and put a new one in its place                   */
	    /* pointing to the left at a, and to the right at b */
	    nodes(MINP) = NODE(n + 1, objs, PROB(a) + PROB(b), ROOT);

	    /* restore heap ordering */
	    swsc_i = 1;
	    bubble_down();                   

	} while (n != 1);

    }

    /* }}} */
    /* {{{ unravel_tree */

    void unravel_tree() {
	
	code, i, flag = 1, 1, 0;

	while (~flag) {
	    a = nodes(i);
	    if (code \\ (codew - 1)) {
		code, i, nodes(i) = 1, 1, NODE(NULL, NULL,
					       no_probability, ROOT);
	    } else if ((TYPE(a) & LEAF) != 0) {
		dict(LEFT(a) <- dw) = 0 @ code;
		code, i, nodes(i) = 1, 1, NODE(NULL, NULL,
					       no_probability, ROOT);
	    } else {
		x = nodes(LEFT(a));
		y = nodes(RIGHT(a));
		if ((TYPE(x) & ROOT) == 0) {
		    code, i = (code <- (codew - 1)) @ false, LEFT(a);
		} else if ((TYPE(y) & ROOT) == 0) {
		    code, i = (code <- (codew - 1)) @ true, RIGHT(a);
		} else if (i != 1) {
		    code, i, nodes(i) = 1, 1, NODE(NULL, NULL,
						   no_probability, ROOT);
		} else flag = 1;
	    }

	}
    }

    /* }}} */
    /* {{{ output_dictionary */

    void output_dictionary() {

	i = 0;
	do par {
	    STDOUT ! (dict(i <- dw) <- codew);
	    i = i + 1;
	} while (i != max);

    }

    /* }}} */
    /* {{{ compress */

    void compress() {
	
    par {
	    while (1) {
 		bitstream ? b0;
 		bitstream ? b1;
 		bitstream ? b2;
 		bitstream ? b3;
 		bitstream ? b4;
 		bitstream ? b5;
 		bitstream ? b6;
 		bitstream ? b7;
		STDOUT ! 0 @ b0 @ b1 @ b2 @ b3 @ b4 @ b5 @ b6 @ b7;
	    }

	    while (1) {
		par {
		    {
			STDIN ? data;
			flag = 0;
		    }
		    {
			flag = 1;
			delay;
			if (flag) stop;
		    }
		}
		code = dict(data) <- codew;
		if (flag | ((code \\ 8)  <- 1)) par {
		    bitstream ! (code \\ 7)  <- 1;
		    flag = 1;
		}
		if (flag | ((code \\ 7)  <- 1)) par {
		    bitstream ! (code \\ 6)  <- 1;
		    flag = 1;
		}
		if (flag | ((code \\ 6)  <- 1)) par {
		    bitstream ! (code \\ 5)  <- 1;
		    flag = 1;
		}
		if (flag | ((code \\ 5)  <- 1)) par {
		    bitstream ! (code \\ 4)  <- 1;
		    flag = 1;
		}
		if (flag | ((code \\ 4)  <- 1)) par {
		    bitstream ! (code \\ 3)  <- 1;
		    flag = 1;
		}
		if (flag | ((code \\ 3)  <- 1)) par {
		    bitstream ! (code \\ 2)  <- 1;
		    flag = 1;
		}
		if (flag | ((code \\ 2)  <- 1)) par {
		    bitstream ! (code \\ 1)  <- 1;
		    flag = 1;
		}
		if (flag | ((code \\ 1)  <- 1)) par {
		    bitstream ! (code \\ 0)  <- 1;
		    flag = 1;
		} else
		    stop;
	    }
	}
    }

    /* }}} */

    build_histogram();
    fix_heap();
    huffman();
    unravel_tree();
    output_dictionary();
    compress();

}

/* Starts building the huffman tree before the 2000 cycle
   Finishes and starts unravelling the tree at ~10800 cycle.
*/