#include <stdio.h>
#include <math.h>
#include <memory.h>
#include <stdlib.h>

#define BASE    "website/sv8/"


const char*  MemberOf   = "";
const char*  ReturnLink = "";
FILE*        fp_c;
FILE*        fp_html;


typedef struct _Code_t {
    long double      Probability;
    unsigned long    CodeWord;
    unsigned long    Power;
    unsigned short   CodeNumber;
    unsigned char    Bits;
    struct _Code_t*  l1;
    struct _Code_t*  l2;
} Code_t;


static int
cmpfn_1 ( const void* p1, const void* p2 )
{
    if ( ((const Code_t*)p1)->Probability < ((const Code_t*)p2)->Probability )
        return +1;
    if ( ((const Code_t*)p1)->Probability > ((const Code_t*)p2)->Probability )
        return -1;
    return 0;
}


static int
cmpfn_2 ( const void* p1, const void* p2 )
{
    if ( ((const Code_t*)p1)->Bits < ((const Code_t*)p2)->Bits )
        return -1;
    if ( ((const Code_t*)p1)->Bits > ((const Code_t*)p2)->Bits )
        return +1;
    if ( ((const Code_t*)p1)->CodeNumber < ((const Code_t*)p2)->CodeNumber )
        return -1;
    if ( ((const Code_t*)p1)->CodeNumber > ((const Code_t*)p2)->CodeNumber )
        return +1;
    return 0;
}


static int
cmpfn_3 ( const void* p1, const void* p2 )
{
    if ( ((const Code_t*)p1)->CodeNumber < ((const Code_t*)p2)->CodeNumber )
        return -1;
    if ( ((const Code_t*)p1)->CodeNumber > ((const Code_t*)p2)->CodeNumber )
        return +1;
    return 0;
}


static Code_t  Codes  [729 * 729 * 2];


static void
CountBits ( Code_t* p, int no )
{
    if ( p -> l1  &&  p -> l2 ) {
        CountBits ( p -> l1, no+1 );
        CountBits ( p -> l2, no+1 );
    }
    else if ( p -> l1  ||  p -> l2 ) {
        fprintf ( stderr, "Error in Huffman Tree\n" );
    }
    else {
        p -> Bits = no;
    }
}


const char*
Graph ( unsigned long x, int n )
{
    static char  buff [128];
    char*        p = buff;
    int          i;

    for ( i = 0; i < n; i++ ) {
        if ( (i & 7) == 7 )
            *p++ = '<', *p++ = 'b', *p++ = '>';
        *p++ = x & (0x80000000 >> i) ? '#' : '.';
        if ( (i & 7) == 7 )
            *p++ = '<', *p++ = '/', *p++ = 'b', *p++ = '>';
    }
    *p = '\0';
    return buff;
}


void
compute_type1 ( long double* p, int min, int max, int coupling, int maxcodes )
{
    int            i;
    int            i0, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11;
    int            cnt;
    long double    Sum;
    long double    ProbabilityS;
    long double    ProbabilityH;
    long double    Huffman;
    long double    Shannon;
    long double    Power;
    unsigned long  Code;

    for ( i = 0; i < sizeof(Codes)/sizeof(*Codes); i++ ) {
        Codes [i].CodeNumber  = i;
        Codes [i].Probability = 0.;
        Codes [i].Bits        = 255;
        Codes [i].CodeWord    = 0x00000000;
        Codes [i].l1          = NULL;
        Codes [i].l2          = NULL;
    }

    cnt = 0;
    switch ( coupling ) {
    case 12:
        for ( i0 = min; i0 <= max; i0++ )
            for ( i1 = min; i1 <= max; i1++ )
                for ( i2 = min; i2 <= max; i2++ )
                    for ( i3 = min; i3 <= max; i3++ )
                        for ( i4 = min; i4 <= max; i4++ )
                            for ( i5 = min; i5 <= max; i5++ )
                                for ( i6 = min; i6 <= max; i6++ )
                                    for ( i7 = min; i7 <= max; i7++ )
                                        for ( i8 = min; i8 <= max; i8++ )
                                            for ( i9 = min; i9 <= max; i9++ )
                                                for ( i10 = min; i10 <= max; i10++ )
                                                    for ( i11 = min; i11 <= max; i11++ ) {
                                                    Codes [cnt].Probability = p[i0] * p[i1] * p[i2] * p[i3] * p[i4] * p[i5] * p[i6] * p[i7] * p[i8] * p[i9] * p [i10] * p[i11];
                                                    Codes [cnt].Power       = i0*i0 + i1*i1 + i2*i2 + i3*i3 + i4*i4 + i5*i5 + i6*i6 + i7*i7 + i8*i8 + i9*i9 + i10*i10 + i11*i11;
                                                    cnt++;
                                                }
        break;

    case 11:
        for ( i0 = min; i0 <= max; i0++ )
            for ( i1 = min; i1 <= max; i1++ )
                for ( i2 = min; i2 <= max; i2++ )
                    for ( i3 = min; i3 <= max; i3++ )
                        for ( i4 = min; i4 <= max; i4++ )
                            for ( i5 = min; i5 <= max; i5++ )
                                for ( i6 = min; i6 <= max; i6++ )
                                    for ( i7 = min; i7 <= max; i7++ )
                                        for ( i8 = min; i8 <= max; i8++ )
                                            for ( i9 = min; i9 <= max; i9++ )
                                                for ( i10 = min; i10 <= max; i10++ ) {
                                                    Codes [cnt].Probability = p[i0] * p[i1] * p[i2] * p[i3] * p[i4] * p[i5] * p[i6] * p[i7] * p[i8] * p[i9] * p [i10];
                                                    Codes [cnt].Power       = i0*i0 + i1*i1 + i2*i2 + i3*i3 + i4*i4 + i5*i5 + i6*i6 + i7*i7 + i8*i8 + i9*i9 + i10*i10;
                                                    cnt++;
                                                }
        break;

    case 10:
        for ( i0 = min; i0 <= max; i0++ )
            for ( i1 = min; i1 <= max; i1++ )
                for ( i2 = min; i2 <= max; i2++ )
                    for ( i3 = min; i3 <= max; i3++ )
                        for ( i4 = min; i4 <= max; i4++ )
                            for ( i5 = min; i5 <= max; i5++ )
                                for ( i6 = min; i6 <= max; i6++ )
                                    for ( i7 = min; i7 <= max; i7++ )
                                        for ( i8 = min; i8 <= max; i8++ )
                                            for ( i9 = min; i9 <= max; i9++ ) {
                                                Codes [cnt].Probability = p[i0] * p[i1] * p[i2] * p[i3] * p[i4] * p[i5] * p[i6] * p[i7] * p[i8] * p[i9];
                                                Codes [cnt].Power       = i0*i0 + i1*i1 + i2*i2 + i3*i3 + i4*i4 + i5*i5 + i6*i6 + i7*i7 + i8*i8 + i9*i9;
                                                cnt++;
                                            }
        break;

    case 9:
        for ( i0 = min; i0 <= max; i0++ )
            for ( i1 = min; i1 <= max; i1++ )
                for ( i2 = min; i2 <= max; i2++ )
                    for ( i3 = min; i3 <= max; i3++ )
                        for ( i4 = min; i4 <= max; i4++ )
                            for ( i5 = min; i5 <= max; i5++ )
                                for ( i6 = min; i6 <= max; i6++ )
                                    for ( i7 = min; i7 <= max; i7++ )
                                        for ( i8 = min; i8 <= max; i8++ ) {
                                            Codes [cnt].Probability = p[i0] * p[i1] * p[i2] * p[i3] * p[i4] * p[i5] * p[i6] * p[i7] * p[i8];
                                            Codes [cnt].Power       = i0*i0 + i1*i1 + i2*i2 + i3*i3 + i4*i4 + i5*i5 + i6*i6 + i7*i7 + i8*i8;
                                            cnt++;
                                        }
        break;

    case 8:
        for ( i0 = min; i0 <= max; i0++ )
            for ( i1 = min; i1 <= max; i1++ )
                for ( i2 = min; i2 <= max; i2++ )
                    for ( i3 = min; i3 <= max; i3++ )
                        for ( i4 = min; i4 <= max; i4++ )
                            for ( i5 = min; i5 <= max; i5++ )
                                for ( i6 = min; i6 <= max; i6++ )
                                    for ( i7 = min; i7 <= max; i7++ ) {
                                        Codes [cnt].Probability = p[i0] * p[i1] * p[i2] * p[i3] * p[i4] * p[i5] * p[i6] * p[i7];
                                        Codes [cnt].Power       = i0*i0 + i1*i1 + i2*i2 + i3*i3 + i4*i4 + i5*i5 + i6*i6 + i7*i7;
                                        cnt++;
                                    }
        break;

    case 7:
        for ( i0 = min; i0 <= max; i0++ )
            for ( i1 = min; i1 <= max; i1++ )
                for ( i2 = min; i2 <= max; i2++ )
                    for ( i3 = min; i3 <= max; i3++ )
                        for ( i4 = min; i4 <= max; i4++ )
                            for ( i5 = min; i5 <= max; i5++ )
                                for ( i6 = min; i6 <= max; i6++ ) {
                                    Codes [cnt].Probability = p[i0] * p[i1] * p[i2] * p[i3] * p[i4] * p[i5] * p[i6];
                                    Codes [cnt].Power       = i0*i0 + i1*i1 + i2*i2 + i3*i3 + i4*i4 + i5*i5 + i6*i6;
                                    cnt++;
                                }
        break;

    case 6:
        for ( i0 = min; i0 <= max; i0++ )
            for ( i1 = min; i1 <= max; i1++ )
                for ( i2 = min; i2 <= max; i2++ )
                    for ( i3 = min; i3 <= max; i3++ )
                        for ( i4 = min; i4 <= max; i4++ )
                            for ( i5 = min; i5 <= max; i5++ ) {
                                Codes [cnt].Probability = p[i0] * p[i1] * p[i2] * p[i3] * p[i4] * p[i5];
                                Codes [cnt].Power       = i0*i0 + i1*i1 + i2*i2 + i3*i3 + i4*i4 + i5*i5;
                                cnt++;
                            }
        break;

    case 5:
        for ( i0 = min; i0 <= max; i0++ )
            for ( i1 = min; i1 <= max; i1++ )
                for ( i2 = min; i2 <= max; i2++ )
                    for ( i3 = min; i3 <= max; i3++ )
                        for ( i4 = min; i4 <= max; i4++ ) {
                            Codes [cnt].Probability = p[i0] * p[i1] * p[i2] * p[i3] * p[i4];
                            Codes [cnt].Power       = i0*i0 + i1*i1 + i2*i2 + i3*i3 + i4*i4;
                            cnt++;
                        }
        break;

    case 4:
        for ( i0 = min; i0 <= max; i0++ )
            for ( i1 = min; i1 <= max; i1++ )
                for ( i2 = min; i2 <= max; i2++ )
                    for ( i3 = min; i3 <= max; i3++ ) {
                        Codes [cnt].Probability = p[i0] * p[i1] * p[i2] * p[i3];
                        Codes [cnt].Power       = i0*i0 + i1*i1 + i2*i2 + i3*i3;
                        cnt++;
                    }
        break;

    case 3:
        for ( i0 = min; i0 <= max; i0++ )
            for ( i1 = min; i1 <= max; i1++ )
                for ( i2 = min; i2 <= max; i2++ ) {
                    Codes [cnt].Probability = p[i0] * p[i1] * p[i2];
                    Codes [cnt].Power       = i0*i0 + i1*i1 + i2*i2;
                    cnt++;
                }
        break;

    case 2:
        for ( i0 = min; i0 <= max; i0++ )
            for ( i1 = min; i1 <= max; i1++ ) {
                Codes [cnt].Probability = p[i0] * p[i1];
                Codes [cnt].Power       = i0*i0 + i1*i1;
                cnt++;
            }
        break;

    case 1:
        for ( i0 = min; i0 <= max; i0++ ) {
            Codes [cnt].Probability = p[i0];
            Codes [cnt].Power       = i0*i0;
            cnt++;
        }
        break;
    }

    qsort ( Codes, cnt, sizeof(*Codes), cmpfn_1 );

    if ( cnt < maxcodes )
        fprintf ( stderr, "Error: Too less codes generated: max possible: %u, requested: %u\n", cnt, maxcodes );

    for ( Sum = 0., i = maxcodes; --i >= 0; )
        Sum += Codes [i].Probability;

    for ( i = maxcodes; --i >= 0; )
        Codes [i].Probability /= Sum;

    for ( Sum = 0., i = maxcodes; --i >= 1; )
        Sum += Codes [i].Probability;

    Codes [0].Probability = 1. - Sum;

    for ( i = maxcodes-2; i >= 0; i-- ) {
        //fprintf ( stderr, "Merge %3u and %3u -> %3u (%7.3f%% + %7.3f%% = %7.3f%%)\n", i+0, i+1, i+0, 100 * Codes [i+0].Probability, 100 * Codes [i+1].Probability, 100 * Codes [i+0].Probability + 100 * Codes [i+1].Probability );
        Codes [i+i+2]            = Codes   [i+0];
        Codes [i+i+3]            = Codes   [i+1];
        Codes [i+0].Probability += Codes   [i+1].Probability;
        Codes [i+0].l1           = Codes + (i+i+2);
        Codes [i+0].l2           = Codes + (i+i+3);
        qsort ( Codes, i+1, sizeof(*Codes), cmpfn_1 );
    }
    CountBits ( Codes, 0 );

    qsort ( Codes, 2*maxcodes, sizeof(*Codes), cmpfn_2 );

    ProbabilityS = 0.;
    ProbabilityH = 0.;
    Huffman      = 0.;
    Shannon      = 0.;
    Power        = 0.;
    for ( i = 0; i < maxcodes; i++ ) {
        double  ps = Codes [i].Probability;
        double  ph = 1. / ( 1LU << Codes [i].Bits );

        ProbabilityS += ps;
        Shannon      -= ps * log (ps) / log (2.);
        Power        += Codes [i].Power * ps;
        ProbabilityH += ph;
        Huffman      -= ps * log (ph) / log (2.);
    }
    fprintf ( fp_c, "    //\n" );
    fprintf ( fp_c, "    // Probability = %9.5f%% (Huffman), %9.5f%% (Shannon)\n", (double)(100 * ProbabilityH), (double)(100 * ProbabilityS) );
    fprintf ( fp_c, "    // Huffman     = %9.5f bit/sample\n", (double)(Huffman/coupling)  );
    fprintf ( fp_c, "    // Shannon     = %9.5f bit/sample\n", (double)(Shannon/coupling)  );
    fprintf ( fp_c, "    // Huffman Loss= %9.5f bit/sample\n", (double)((Huffman-Shannon)/coupling)  );
    fprintf ( fp_c, "    // Effective V = %9.5f\n",            sqrt (Power/coupling)  );
    fprintf ( fp_c, "    //\n" );

    fprintf ( stderr, "Huffman %9.5f  ", (double)(Huffman/coupling)  );
    fprintf ( stderr, "Shannon %9.5f  ", (double)(Shannon/coupling)  );
    fprintf ( stderr, "Loss %10.3f  ",   (double)(1000*(Huffman-Shannon)/coupling)  );
    fprintf ( stderr, "Eff %9.5f  ",     (double)(sqrt (Power/coupling))  );

    Code = 0;
    for ( i = 0; i < maxcodes; i++ ) {
        Codes [i].CodeWord = Code;
        Code              += 0x80000000 >> (Codes [i].Bits - 1);
    }

    qsort ( Codes, maxcodes, sizeof(*Codes), cmpfn_3 );

    for ( i = 0; i < maxcodes; i++ ) {
        fprintf ( fp_c, "    { 0x%08lX, %2u },\t// Code %3u, %2u bits, %8.5f%%\n", Codes[i].CodeWord, Codes [i].Bits, Codes [i].CodeNumber, Codes [i].Bits, (double)(100 * Codes [i].Probability) );
        fprintf ( fp_html, "    <tr> <td align=\"right\"> %3d&nbsp;</td> <td align=\"right\"> <tt><b> %08lX&nbsp;</b></tt> </td> <td align=\"right\"> %2u&nbsp;</td> <td align=\"right\"> %5.2f%%&nbsp;</td> <td><font color=\"#DDDDDD\">&nbsp;<tt>%s</tt>&nbsp;</font></td> </tr>\n",
                  Codes [i].CodeNumber, Codes[i].CodeWord, Codes [i].Bits, (double)(100 * Codes [i].Probability), Graph (Codes[i].CodeWord, Codes [i].Bits) );
    }
}


void
generate_type1 ( const char* basename, int min, int max, double deviation, double exponent, double offset, int coupling, int maxcodes )
{
    long double    table [513];
    char           FileName [128];
    int            i;

    sprintf ( FileName, BASE "%s.html", basename );
    fp_html = fopen ( FileName, "wb" );

    memset ( table, 0, sizeof table );
    for ( i = min; i <= max; i++ ) {
        long double  tmp = i ? pow (fabs ((i+offset)/deviation), exponent) : 0.;
        table [i + 256] = tmp <= 200. ? exp (-tmp) : 0.;
        fprintf ( stderr, "%5.2f ", (double)(99.99*table [i + 256]) );
    }
    fprintf ( stderr, "\n");
    fprintf (fp_c, "const HuffmanCode_t  %s [%3u] = {\n", basename, maxcodes );
    fprintf (stderr, "%-10.10s: ", basename );

    fprintf (fp_html,
        "<!doctype html public \"-//w3c//dtd html 4.0 transitional//en\">\n"
        "<html>\n"
        "<head>\n"
        "    <meta http-equiv=\"Content-Type\" content=\"text/html; charset=iso-8859-1\">\n"
        "    <meta name=\"Author\" content=\"Frank Klemm\">\n"
        "    <title>Huffman Code table: %s</title>\n"
        "</head>\n"
        "<body text=\"#FFFFFF\" bgcolor=\"#254E31\" link=\"#33CCFF\" vlink=\"#33CCFF\" alink=\"#FF0000\" background=\"../img/back-2.gif\">\n"
        "\n"
        "<br>\n", basename );

    fprintf (fp_html,
        "<font size=\"+1\" color=\"#FFD486\"><b>Huffman Code table: &nbsp; %s</b></font><br>\n"
        "\n"
        "<p><p>Member of <a href=\"%s.html\">%s</a>\n"
        "\n"
        "<p>\n"
        "\n"
        "<hr align=\"left\" width=\"512\"> <!------------------------------------------------------------->\n"
        "\n", basename, ReturnLink, MemberOf );

    fprintf (fp_html, "<p><table border=\"3\" bgcolor=\"20442B\">\n" );

    fprintf (fp_html, "    <tr> <td> &nbsp; Code &nbsp; </td> <td> &nbsp; Huffman code &nbsp; </td> <td> &nbsp; Bits &nbsp; </td> <td> &nbsp; Probability &nbsp; </td> <td> &nbsp; Encoded bits &nbsp; </td> </tr>\n" );
    fprintf (fp_html, "    <tr> </tr>\n" );


    compute_type1 ( table+256, min, max, coupling, maxcodes );

    fprintf (fp_html, "</table>" );

    fprintf (fp_html,
        "<p>\n"
        "\n"
        "<hr align=\"left\" width=\"512\"> <!------------------------------------------------------------->\n"
        "\n"
        "<a href=\"mailto:pfk@uni-jena.de\"><img alt=\"[eMail]\" SRC=\"../img/E-Mail.gif\" BORDER=0 height=60 width=55 align=CENTER></a>&nbsp;<a href=\"mailto:pfk@uni-jena.de\">Frank.Klemm@uni-jena.de</a>\n"
        "\n"
        "</body>\n"
        "</html>\n" );

    fprintf (stderr, "\n" );
    fprintf (fp_c, "};\n\n" );
    fflush (fp_c);

    fclose (fp_html);
}


int
main ( void )
{
    fp_c = fopen ( BASE "huffman_codes.c", "wb" );

    MemberOf   = "Quantized Subband Samples";
    ReturnLink = "subbandsample";

    fprintf ( fp_c, "\n#include \"huffman_codes.h\"\n\n\n" );

    generate_type1 ( "table_0X",  -1,  +1, 0.5600, 2.0, 0.0, 9, 163 );
    generate_type1 ( "table_03",  -1,  +1, 0.6024, 2.0, 0.0, 6,  73 );
    generate_type1 ( "table_04",  -1,  +1, 0.7650, 2.0, 0.0, 4,  81 );
    generate_type1 ( "table_05",  -1,  +1, 0.9200, 1.5, 0.0, 3,  27 );
    generate_type1 ( "table_06",  -2,  +2, 1.0000, 2.0, 0.0, 3, 125 );
    generate_type1 ( "table_07",  -2,  +2, 1.0000, 1.5, 0.0, 2,  25 );
    generate_type1 ( "table_08",  -3,  +3, 1.8700, 2.9, 0.0, 2,  49 );
    generate_type1 ( "table_09",  -4,  +4, 2.6100, 3.0, 0.0, 2,  81 );
    generate_type1 ( "table_10",  -5,  +5, 3.8000, 3.0, 0.0, 2, 121 );
    generate_type1 ( "table_01", -16, +15, 5.2000, 3.0, 0.5, 1,  32 );
    generate_type1 ( "table_02", -16, +15, 6.4000, 2.0, 0.5, 1,  32 );
    generate_type1 ( "table_11",  -6,  +6, 2.6700, 2.8, 0.0, 1,  13 );

    MemberOf   = "Allocation";
    ReturnLink = "allocation";
    generate_type1 ( "table_20", -16, +16, 1.4800, 1.0, 0.0, 1,  33 );

    fprintf (fp_c, "/* end of huffman_codes.c */\n" );
    fclose (fp_c);

    return 0;
}