#include <stdio.h>
#include <string.h>
#include <assert.h>

#define FTR "file.txt"
#define FTW "output.txt"
#define NODES 511

int nodesused = 256;

struct htree{
    unsigned freq;
    int left;
    int right;
    int parent;
} array[NODES];

struct low{
    short low1;
    short low2;
} lowsym;

void buildTree(int, int);
int findLow();
void encode(FILE *);
void write_bits(FILE *, int, int);

int main(){
    int i = 0;
    char symbol[1];
    int f1, f2, codeTable[511];
    FILE * input = fopen(FTR, "rb");
    FILE * output = fopen(FTW, "wb");

    memset(array, 0, sizeof(array));
    memset(symbol, 0, sizeof(symbol));

    while(fread(symbol, 1, 1, input))
        array[symbol[0]].freq++;
    fclose(input);

    while(i < 256){
        fwrite(&array[i].freq, 1, sizeof(array[i].freq), output);
        ++i;
    }

    while(findLow() >= 0){
        buildTree(lowsym.low1, lowsym.low2);
    }

    array[lowsym.low1].parent = -1;
    encode(output);
    fclose(output);

    getchar();
    return 0;
}

int findLow(){
    int i, count = 0;
    lowsym.low1 = -1;
    lowsym.low2 = -1;

    for(i = 0; i < NODES; i++)
        if(array[i].freq){
            count++;
            if(lowsym.low1 < 0 || array[i].freq < array[lowsym.low1].freq)
                lowsym.low1 = i;
        }

    if(count > 1)
        for(i = 0; i < NODES; i++)
            if(array[i].freq && i != lowsym.low1)
                if(lowsym.low2 < 0 || array[i].freq < array[lowsym.low2].freq)
                    lowsym.low2 = i;

    return lowsym.low2;
}

void buildTree(int s1, int s2){
    int node = nodesused++;

    array[node].freq = array[s1].freq + array[s2].freq;
    array[node].left = s1;
    array[node].right = s2;
    array[s1].parent = node;
    array[s2].parent = node;

    array[s1].freq = 0;
    array[s2].freq = 0;
}

void encode(FILE * output){
    unsigned i;
    char buff[512], symbol[1], bufp = 0;
    FILE * input = fopen(FTR, "rb");

    memset(buff, 0, sizeof(buff));
    memset(symbol, 0, sizeof(symbol));



    while(fread(symbol, 1, 1, input)){
        i = symbol[0];
        memset(buff, 0, sizeof(buff));

        if(array[array[i].parent].left == i)
            buff [bufp++] = 0 ;
        else if(array[array[i].parent].right == i)
            buff [bufp++] = 1 ;

        while(array[i].parent >= 0){
            i = array[i].parent;
            if(array[array[i].parent].left == i)
                buff [bufp++] = 0 ;
            else if(array[array[i].parent].right == i)
                buff [bufp++] = 1 ;
        }

        while (bufp) {
            write_bits (output,buff [--bufp],0) ;
        }
    }
    write_bits (output,0,1) ;
}

void write_bits(FILE * output, int bit, int flush){
    static count_bits = 0;
    static char buff = 0;

    if(bit)
        buff |= 1 << count_bits;

    if(++count_bits >= 8){
        fwrite(&buff, 1, sizeof(buff), output);
        buff = 0;
        count_bits = 0;
    }

    if(flush && count_bits > 0){
        fwrite(&buff, 1, sizeof(buff), output);
        buff = 0;
        count_bits = 0;
        return;
    }
}