/* compile.c - Don Yang (uguu.org)

   Generate binary from bytecode.

   10/19/01
                                                                           */

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

#define BYTECODE_NAME   "hhenc.h"
#define LISTING_NAME    "hhenc.lst"
#define OFFSET          ';'

enum
{
   add = 1024, sub, shl, shr, and, or, cmp,
   inc, mget, mput, rget, rput, fget, fput, fsek,
   sget, pop, call, ret,
   whilecond, ifcond, begin, otherwise, end,

   label_break, label_assignid, label_heappush, label_writebits, output,
   end_bytecode
};
enum
{
   Tree = 0, x, y, LeftPtr, RightPtr, NextPtr, buffer, Dictionary, f
};
enum
{
   i = 0, j, bit, byte, size, a, b, c, Heap, HeapPoolIndex,
   branch, NodeCount, FileSize, tmp
};
static char *OpcodeString[] =
{
   "add", "sub", "shl", "shr", "and", "or", "cmp",
   "inc", "mget", "mput", "rget", "rput", "fget", "fput", "fsek",
   "sget", "pop", "call", "ret",
   "whilecond", "ifcond", "begin", "otherwise", "end",

   "label_break", "label_assignid", "label_heappush", "label_writebits",
   "output", "end_bytecode"
};

/************************************************************** Bytecode[] */
static int Bytecode[] =
{
   /* main() */
   /*105*/  0, size, rput, fsek,
   /*106*/  whilecond,
               ifcond, size, rget, 256,256,add, cmp,
               begin,
   /*107*/        fget, buffer, size, rget, mput, 1, add, tmp, rput, pop,
               otherwise, 0, tmp, rput, pop,
               end,
               tmp, rget,
   /*108*/  begin,
   /*109*/     size, inc, pop,
   /*110*/  end,
   /*111*/  ifcond, size, rget,
   /*112*/  begin,
   /*113*/     buffer, 0, i, rput, FileSize, rput, mget, NodeCount, rput, pop,
   /*114*/     NodeCount, rget, 3, add, 2, shr, HeapPoolIndex, rput,
   /*115*/     NodeCount, rget, 1, shl, add, Heap, rput, pop,
   /*116*/     ifcond, Heap, rget, 4, add, size, rget, cmp,
   /*117*/     begin,
   /*118*/        whilecond, i, rget, NodeCount, rget, cmp,
   /*119*/        begin,
   /*120*/           0, j, rput, pop,
   /*121*/           whilecond, j, rget, 4, cmp,
   /*122*/           begin,
   /*123*/              buffer, i, rget, 2, shr, 1, add, mget,
                        j, rget, 1, shl, shr, 3, and,
                        f, i, rget, j, inc, add, mput, pop,
   /*125*/           end,
   /*126*/           i, rget, 4, add, i, rput, pop,
   /*127*/        end,

   /*129*/        HeapPoolIndex, rget, 1, add, j, rput, pop,
   /*130*/        0, i, rput, pop,
   /*131*/        whilecond, i, rget, NodeCount, rget, cmp,
   /*132*/        begin,
   /*133*/           0, c, rput, pop,
   /*134*/           whilecond, c, rget, 2, cmp,
   /*135*/           begin,
   /*136*/              c, rget, 8, shl, i, rget, add, a, rput, pop,
   /*137*/              buffer, j, inc, mget, b, rput, pop,
   /*138*/              ifcond, f, i, rget, mget, c, rget, 1, add, and,
   /*139*/              begin,
   /*140*/                 0, b, rget, sub, Tree, a, rget, mput, pop,
   /*142*/              otherwise,
   /*144*/                 b, rget, Tree, a, rget, mput, pop,
   /*145*/                 ifcond, Tree, a, rget, mget,
                              i, rget, 1, add, cmp,
   /*146*/                    NodeCount, rget,
                              Tree, a, rget, mget, 1, add, cmp, or,
   /*147*/                 begin,
   /*148*/                    pop, pop, pop, pop, pop, pop, pop, pop,
                              call, label_break,
   /*149*/                 end,
   /*150*/              end,
   /*151*/              c, inc, pop,
   /*152*/           end,
   /*153*/           i, inc, pop,
   /*154*/        end,
   /*155*/        label_break,
   /*156*/        ifcond, i, rget, NodeCount, rget, sub,
   /*157*/        begin,
   /*159*/        otherwise,
   /*161*/           0, i, rput, FileSize, rput, pop,
   /*162*/           whilecond, i, rget, 8,2,shl, cmp,
   /*163*/           begin,
   /*164*/              buffer, j, inc, mget, i, rget, shl,
                        FileSize, rget, or, FileSize, rput, pop,
   /*165*/              i, rget, 8, add, i, rput, pop,
   /*166*/           end,
   /*167*/        end,
   /*168*/     end,
   /*169*/     ifcond, 0, FileSize, rget, cmp,
   /*170*/     begin,
   /*171*/        Heap, rget, 5, add, fsek,
   /*172*/        0, j, rput, i, rput, byte, rput, pop,
   /*173*/        8, bit, rput, pop,
   /*174*/        whilecond, i, rget, FileSize, rget, cmp,
   /*175*/        begin,
   /*176*/           ifcond, 7, bit, rget, cmp,
   /*177*/           begin,
   /*178*/              fget, byte, rput, pop,
   /*179*/              0, bit, rput, pop,
   /*180*/           end,

   /*182*/           ifcond, byte, rget, 1, bit, rget, shl, and,
                     begin,
                        256, tmp, rput, pop,
                     otherwise,
                        0, tmp, rput, pop,
                     end,
                     tmp, rget, j, rget, add, 5,5,add, rput, pop,
   /*183*/           ifcond, Tree, 5,5,add, rget, mget, 1, cmp,
   /*184*/           begin,
   /*185*/              0, j, rput, Tree, 5,5,add, rget, mget, sub, fput,
   /*187*/              i, inc, pop,
   /*189*/           otherwise,
   /*191*/              Tree, 5,5,add, rget, mget, j, rput, pop,
   /*192*/           end,
   /*193*/           bit, inc, pop,
   /*194*/        end,
   /*195*/        0/*"Decoded"*/, output,
   /*197*/     otherwise,

   /*199*/        0, i, rput, FileSize, rput, fsek,
   /*200*/        whilecond, i, rget, 256, cmp,
   /*201*/        begin,
   /*202*/           0, f, i, inc, mput, pop,
   /*203*/        end,

   /*205*/        whilecond, fget, i, rput, 1, add,
   /*206*/        begin,
   /*207*/           f, i, rget, mget, 1, add, f, i, rget, mput, pop,
   /*208*/           FileSize, inc, pop,
   /*209*/        end,

   /*211*/        0, i, rput, b, rput, a, rput, HeapPoolIndex, rput,
                  1, sub, Heap, rput, pop,
   /*213*/        whilecond, i, rget, 256, cmp,
   /*214*/        begin,
   /*215*/           ifcond, f, i, rget, mget,
   /*216*/           begin,
   /*217*/              call, label_heappush,
   /*218*/           end,
   /*219*/           i, inc, pop,
   /*220*/        end,
   /*221*/        ifcond, NextPtr, Heap, rget, mget, 0,1,sub, sub,
   /*222*/        begin, otherwise,
   /*223*/           0, i, rput, pop,
   /*224*/           whilecond, 0, f, i, rget, mget, cmp,
   /*225*/           begin,
   /*226*/              i, inc, pop,
   /*227*/           end,
   /*228*/           call, label_heappush,
   /*229*/        end,

   /*231*/        256, i, rput, pop,
   /*232*/        whilecond, NextPtr, Heap, rget, mget, 1, add,
   /*233*/        begin,
   /*234*/           NextPtr,
                        NextPtr,
                           Heap, rget, a, rput,
                        mget,
                        b, rput,
                     mget,
                     Heap, rput, pop,
   /*236*/           x, a, rget, mget, x, b, rget, mget, add,
                     f, i, rget, mput, pop,
   /*237*/           call, label_heappush,
   /*238*/        end,

   /*240*/        0, NodeCount, rput, pop,
   /*241*/        Heap, rget, 0, 1, sub, call, label_assignid, pop, pop,

   /*243*/        NodeCount, rget, i, rput, pop,
   /*244*/        whilecond, i, rget, 256, cmp,
   /*245*/        begin,
   /*246*/           256, Tree, 256, i, rget, add, mput,
   /*247*/           Tree, i, inc, mput, pop,
   /*248*/        end,

   /*250*/        NodeCount, rget, fput,

   /*251*/        0, i, rput, pop,
   /*252*/        whilecond, i, rget, NodeCount, rget, cmp,
   /*253*/        begin,
   /*254*/           0, j, rput, byte, rput, pop,
   /*255*/           whilecond, j, rget, 4, cmp,
   /*256*/           begin,
   /*257*/              1, j, rget, 1, shl, shl, c, rput, pop,
   /*258*/              ifcond, Tree, i, rget, j, rget, add, mget, 1, cmp,
   /*259*/              begin,
   /*260*/                 byte, rget, c, rget, or, byte, rput, pop,
   /*261*/              end,
   /*262*/              ifcond, Tree,
                           i, rget, j, rget, 256, add, add, mget, 1, cmp,
   /*263*/              begin,
   /*264*/                 byte, rget, c, rget, 1, shl, or, byte, rput, pop,
   /*265*/              end,
   /*266*/              j, inc, pop,
   /*267*/           end,
   /*268*/           byte, rget, fput,
   /*269*/           i, rget, 4, add, i, rput, pop,
   /*270*/        end,

   /*272*/        0, i, rput, pop,
   /*273*/        whilecond, i, rget, NodeCount, rget, cmp,
   /*274*/        begin,
   /*275*/           Tree, i, rget, mget, fput,
   /*276*/           Tree, i, inc, 256, add, mget, fput,
   /*278*/        end,

   /*280*/        0, i, rput, pop,
   /*281*/        whilecond, i, rget, 4, cmp,
   /*282*/        begin,
   /*283*/           FileSize, rget, i, inc, 3, shl, shr, 256,1,sub, and, fput,
   /*285*/        end,

   /*287*/        0, byte, rput, bit, rput, i, rput, fsek,
   /*288*/        whilecond, i, rget, FileSize, rget, cmp,
   /*289*/        begin,
   /*290*/           Dictionary, fget, j, rput, mget,
   /*291*/           call, label_writebits, pop,
   /*292*/           i, inc, pop,
   /*293*/        end,

   /*295*/        ifcond, 0, bit, rget, cmp,
   /*296*/        begin,
   /*297*/           byte, rget, fput,
   /*298*/        end,

   /*300*/        1/*"Encoded"*/, output,
   /*301*/     end,
   /*303*/  otherwise,
   /*305*/     2/*"Empty file"*/, output,
   /*306*/  end,

   /* AssignID() */
   /* 25*/  label_assignid,
   /* 29*/  LeftPtr, -3, sget, mget,
   /* 30*/  RightPtr, -3, sget, mget,
   /* 31*/  -2, sget, NextPtr, -3, sget, mput, pop,
   /* 32*/  ifcond, y, -3, sget, mget, 256, sub,
   /* 33*/  begin,
   /* 34*/     -3, sget, Dictionary, y, -3, sget, mget, mput, pop,
   /* 36*/  otherwise,
   /* 38*/     NodeCount, inc, x, -3, sget, mput, pop,
   /* 39*/     +1, sget, -3, sget, call, label_assignid, pop, pop,
   /* 40*/     +2, sget, -3, sget, call, label_assignid, pop, pop,

   /* 43*/     ifcond, y, +1, sget, mget, 256, sub,
               begin,
   /* 44*/        0, y, +1, sget, mget, sub, tmp, rput, pop,
               otherwise,
   /* 45*/        x, +1, sget, mget, tmp, rput, pop,
               end,
   /* 42*/     tmp, rget, Tree, x, -3, sget, mget, mput, pop,
   /* 47*/     ifcond, y, +2, sget, mget, 256, sub,
               begin,
   /* 48*/        0, y, +2, sget, mget, sub, tmp, rput, pop,
               otherwise,
   /* 49*/        x, +2, sget, mget, tmp, rput, pop,
               end,
   /* 46*/     tmp, rget, Tree, 256, x, -3, sget, mget, add, mput, pop,
   /* 50*/  end,
   /* 51*/  pop, pop, ret,

   /* HeapPush() */
   /* 53*/  label_heappush,
   /* 55*/  HeapPoolIndex, inc, c, rput, pop,
   /* 56*/  f, i, rget, y, c, rget, mput, mget, x, c, rget, mput, pop,
   /* 57*/  a, rget, LeftPtr, c, rget, mput, pop,
   /* 58*/  b, rget, RightPtr, c, rget, mput, pop,
   /* 60*/  ifcond,
               ifcond, Heap, rget, 0, cmp,
   /* 61*/     begin,
                  1, tmp, rput, pop,
               otherwise,
                  x, c, rget, mget, x, Heap, rget, mget, cmp, tmp, rput, pop,
               end,
               tmp, rget,
   /* 62*/  begin,
   /* 63*/     Heap, rget, NextPtr, c, rget, mput, pop,
   /* 64*/     c, rget, Heap, rput, pop,
   /* 66*/  otherwise,
   /* 68*/     NextPtr, Heap, rget, a, rput, mget, b, rput, pop,
   /* 69*/     whilecond,
                  ifcond, b, rget, 1, add,
                  begin,
   /* 70*/           x, b, rget, mget, x, c, rget, mget, cmp, tmp, rput, pop,
                  otherwise,
                     0, tmp, rput, pop,
                  end,
                  tmp, rget,
   /* 71*/     begin,
   /* 72*/        NextPtr, b, rget, a, rput, mget, b, rput, pop,
   /* 73*/     end,
   /* 74*/     b, rget, NextPtr, c, rget, NextPtr, a, rget, mput, mput, pop,
   /* 75*/  end,
   /* 76*/  ret,

   /* WriteBits() */
   /* 78*/  label_writebits,
   /* 80*/  ifcond, NextPtr, -2, sget, mget, 1, add,
   /* 81*/  begin,
   /* 82*/     NextPtr, -2, sget, mget, call, label_writebits, pop,
   /* 83*/     ifcond,
                  RightPtr, NextPtr, -2, sget, mget, mget,
                  -2, sget, sub,
               begin,
                  0, tmp, rput, pop,
               otherwise,
                  1, tmp, rput, pop,
               end,
               tmp, rget, bit, inc, shl,
               byte, rget, or, byte, rput, pop,
   /* 84*/     ifcond, 7, bit, rget, cmp,
   /* 85*/     begin,
   /* 86*/        byte, rget, fput,
   /* 87*/        0, byte, rput, bit, rput, pop,
   /* 88*/     end,
   /* 89*/  end,
   /* 90*/  ret,

   end_bytecode

}; /* Bytecode[] */

/*********************************************************** HuffmanCode[] */
static char *HuffmanCode[] =
{
   /*add             */ "110101",
   /*sub             */ "110110",
   /*shl             */ "1000001",
   /*shr             */ "1000010",
   /*and             */ "1000011",
   /*or              */ "1000000",
   /*cmp             */ "110100",
   /*inc             */ "110111",
   /*mget            */ "11000",
   /*mput            */ "110010",
   /*rget            */ "1111",
   /*rput            */ "1010",
   /*fget            */ "10010010",
   /*fput            */ "1001000",
   /*fsek            */ "10010011",
   /*sget            */ "110011",
   /*pop             */ "1110",
   /*call            */ "1001010",
   /*ret             */ "100101111",
   /*whilecond       */ "100110",
   /*ifcond          */ "100111",
   /*begin           */ "10110",
   /*otherwise       */ "100011",
   /*end             */ "10111",
   /*label_break     */ "10001000",
   /*label_assignid  */ "10001010",
   /*label_heappush  */ "10001011",
   /*label_writebits */ "10001001",
   /*output          */ "10010110",
   /*end_bytecode    */ "100101110"

}; /* HuffmanCode[] */

static int Constant[] =
{
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, -2, -3, 256, 0xdeadbeef
};

static int BufferByte, BufferBit;

/********************************************************** WriteBitString */
static void WriteBitString(FILE *code, FILE *list, char *bits, int ip,
                           char *label)
{
   char *p;

   for(p = bits; *p; p++)
   {
      BufferByte |= (*p - '0') << (BufferBit++);
      if( BufferBit > 5 )
      {
         fputc(BufferByte + OFFSET, code);
         if( (BufferByte + OFFSET) == '\\' )
            fputc('\\', code);
         BufferBit = BufferByte = 0;
      }
   }

   fprintf(list, "%4d: %-13s%s\n", ip, bits, label);

} /* WriteBitString() */

/*************************************************************** WriteData */
static void WriteData(FILE *code, FILE *list, int ip)
{
   char data[16], label[64];
   int p, q;

   data[0] = '0';
   for(p = 0; Constant[p] != Bytecode[ip] && Constant[p] != 0xdeadbeef; p++);
   for(q = 0; q < 4; q++)
   {
      if( (p & (1 << q)) == 0 )
         data[q + 1] = '0';
      else
         data[q + 1] = '1';
   }
   data[q + 1] = 0;
   sprintf(label, "data = %d", Bytecode[ip]);
   WriteBitString(code, list, data, ip, label);

} /* WriteData() */

/******************************************************** WriteInstruction */
static void WriteInstruction(FILE *code, FILE *list, int ip)
{
   WriteBitString(code, list, HuffmanCode[Bytecode[ip] - add], ip,
      OpcodeString[Bytecode[ip] - add]);

} /* WriteInstruction() */

/******************************************************************** main */
int main(void)
{
   FILE *code, *list;
   int ip;

   if( (code = fopen(BYTECODE_NAME, "wt+")) == NULL )
   {
      puts("Can not create " BYTECODE_NAME);
      return 1;
   }
   if( (list = fopen(LISTING_NAME, "wt+")) == NULL )
   {
      fclose(code);
      puts("Can not create " LISTING_NAME);
      return 1;
   }

   fputs("static char *bytecode = \"", code);
   for(ip = BufferByte = BufferBit = 0; Bytecode[ip] != end_bytecode; ip++)
   {
      if( Bytecode[ip] >= add && Bytecode[ip] < end_bytecode )
         WriteInstruction(code, list, ip);
      else
         WriteData(code, list, ip);
   }
   WriteInstruction(code, list, ip);
   if( BufferBit > 0 )
   {
      fputc(BufferByte + OFFSET, code);
      if( (BufferByte + OFFSET) == '\\' )
         fputc('\\', code);
   }
   fputs("\";\n", code);

   fclose(code);
   fclose(list);
   puts("Wrote " BYTECODE_NAME " and " LISTING_NAME);
   return 0;

} /* main() */