// File HUFF.C  

// Debugging lab example

// *****There is a bug placed in PutBit() in BitFifo.c on purpose**

// Example: Huffman encoding and decoding

// Last modified 12/15/02 by Jonathan W. Valvano

 

// Copyright 2003 by Jonathan W. Valvano, valvano@uts.cc.utexas.edu 

//    You may use, edit, run or distribute this file 

//    as long as the above copyright notice remains 

#include "HC12.H"

#include "SCI12.H"

#include "BITFIFO.H"



// const will place this structure in EEPROM

const struct Node{

  char Letter0;     // ASCII code if binary 0

  char Letter1;     // ASCII code if binary 1

// Letter1 is NULL(0) if Link is pointer to another node

  const struct Node *Link;};  // binary tree pointer 

typedef const struct Node NodeType;

typedef NodeType * NodePtr;

// Huffman tree

NodeType Twentysixth= {'Q','Z',0};

NodeType Twentyfifth= {'X',0,&Twentysixth}; 

NodeType Twentyfourth={'G',0,&Twentyfifth}; 

NodeType Twentythird= {'J',0,&Twentyfourth}; 

NodeType Twentysecond={'W',0,&Twentythird}; 

NodeType Twentyfirst= {'V',0,&Twentysecond}; 

NodeType Twentyth=    {'H',0,&Twentyfirst}; 

NodeType Ninteenth=   {'F',0,&Twentyth}; 

NodeType Eighteenth=  {'B',0,&Ninteenth}; 

NodeType Seventeenth= {'K',0,&Eighteenth}; 

NodeType Sixteenth=   {'D',0,&Seventeenth}; 

NodeType Fifteenth=   {'P',0,&Sixteenth}; 

NodeType Fourteenth=  {'M',0,&Fifteenth}; 

NodeType Thirteenth=  {'Y',0,&Fourteenth}; 

NodeType Twelfth=     {'L',0,&Thirteenth}; 

NodeType Eleventh=    {'U',0,&Twelfth}; 

NodeType Tenth=       {'R',0,&Eleventh}; 

NodeType Ninth=       {'C',0,&Tenth}; 

NodeType Eighth=      {'O',0,&Ninth}; 

NodeType Seventh=     {' ',0,&Eighth}; 

NodeType Sixth=       {'N',0,&Seventh}; 

NodeType Fifth=       {'I',0,&Sixth}; 

NodeType Fourth=      {'S',0,&Fifth}; 

NodeType Third=       {'T',0,&Fourth}; 

NodeType Second=      {'A',0,&Third}; 

NodeType Root=        {'E',0,&Second};





//******** encode *************** 

// convert ASCII string to Huffman bit sequence

// returns bit count if OK

// returns 0         if BitFifo Full

// returns -1        if illegal character

int encode(char *sPt){  // null-terminated ASCII string

  int notFound; 

  char data;

  int bitCount=0;        // number of bits created

  NodePtr hpt;           // pointer into Huffman tree

  while(data=(*sPt)){

    sPt++;              // next character

    hpt = &Root;        // start search at Root

    notFound = 1;       // changes to 0 when found

    while(notFound){

      if((hpt->Letter0)==data){

        if(!BitFifo_Put(0)){ 

          return(0);    // data structure full

        }

        bitCount++;

        notFound = 0;

      }

      else{

        if(!BitFifo_Put(1)){ 

          return(0);   // data structure full

        }

        bitCount++;

        if((hpt->Letter1)==data){        

          notFound=0;

        }

        else{       // doesn't match either Letter0 or Letter1

          hpt = hpt->Link;

          if(hpt==0){ 

            return(-1);   // illegal error, end of tree??

          }

        }

      }

    }

  }

  return bitCount;        

}



//******** decode *************** 

// convert Huffman bit sequence to ASCII

// will remove from the BitFifo until it is empty

// returns character count

int decode(char *sPt){  // null-terminated ASCII string

  int charCount=0;      // number of ASCII characters created

  unsigned int data;

  NodePtr hpt;           // pointer into Huffman tree

  hpt = &Root;           // start search at Root

  while(BitFifo_Get(&data)){     

    if(data==0){

      (*sPt) = (hpt->Letter0);

      sPt++;

      charCount++;

      hpt = &Root;      // start over and search at Root

    }

    else{  // data is 1

      if((hpt->Link)==0){ 

        (*sPt) = (hpt->Letter1);

        sPt++;

        charCount++;

        hpt = &Root;  // start over and search at Root

      }

      else{           // doesn't match either Letter0 or Letter1

        hpt = hpt->Link;

      }

    }

  }

  (*sPt) = 0;  // null terminated

  return charCount;        

}



//******** InitTimer *************** 

// Initialize Timer, COP

void InitTimer(void){

  COPCTL = 0x00;    // disable COP 

  DDRT |= 0x40;     // PortT bit 6 is output to LED

  TSCR = 0x80;      // TEN(enable)

}



void main(void){  

  char string[40];

  int size;

  SCI_Init(13);

  InitTimer();    // disable COP, enable timer 

  BitFifo_Init();

  SCI_OutString("\nExample with Huffman code 12/15/02 -JWV");

  while(1){

    SCI_OutString("\nEnter a string to encode "); 

    SCI_InString(string,39);

    SCI_OutString("\nEncoding "); SCI_OutString(string); SCI_OutChar(CR);

    size=encode(string);

    if(size==0){

      SCI_OutString("\nToo long, BitFifo full");

      BitFifo_Init();

    }

    else{

      if(size==-1){

        SCI_OutString("\nIllegal character");

        BitFifo_Init();

      }

      else{

        SCI_OutString("\nnumber of bits = "); SCI_OutSDec(size);

        size = decode(string);

        SCI_OutChar(CR);

        SCI_OutString(string); 

        SCI_OutString("\nnumber of characters = "); SCI_OutSDec(size);

      }

    }

  }

}

#include "BITFIFO.C"

#include "SCI12.C"

extern void _start();	

#pragma abs_address:0xfffe

void (*reset_vector[])() = { _start };

#pragma end_abs_address