Script started on Tue Mar 11 04:54:15 2003
uhunix2:~/212% cat makefile

huffdcmp: huffdcmp.o nodeTree.o decompress.o
        gcc -g huffdcmp.o nodeTree.o decompress.o -o huffdcmp

huffdcmp.o: huffdcmp.c huffdcmp.h
        gcc -c huffdcmp.c

nodeTree.o: nodeTree.c huffdcmp.h
        gcc -c nodeTree.c

decompress.o: decompress.c huffdcmp.h
        gcc -c decompress.c

uhunix2:~/212% cat huffdcmp.h

#include <stdio.h>  /*used by all */

struct node {  /* definition of tree nodes */
  int content; 
  struct node *left;
  struct node *right;
};
typedef struct node Node;



/* huffdcmp.c */
void usage();
#define TREEINFO 1  //whether to print extra info when run

/* nodeTree.c */
Node* readTree(FILE* fileIn);
Node* makeNode(int content, Node* left, Node* right);
void push(Node* node);
Node* pop();
void printtree(Node* r);
int countLeaves(Node* n);
int largestValue(Node* n);

/* decompress.c */
Node* decompress(FILE* fileIn, Node* tree, FILE* fileOut);
void process(char byte, int bits, Node* tree, FILE* fileOut);
void traverse(char bit, Node* tree, FILE* fileOut);

uhunix2:~/212% cat huffdcmp.c

/* huffdcmp.c */
/* A Huffman decompression program.                           */
/* This main module involves primarily file I/O               */

/* Author: Zach Tomaszewski */
/* Date: 10 Mar 2003        */


#include "huffdcmp.h"


int main(int argc, char* argv[]){

  FILE* huffFile;
  FILE* treeFile;
  FILE* outFile;
  Node* root;

  if (argc == 4) {

    /* make the tree */
    treeFile = fopen(argv[2], "rb");
    if (treeFile == NULL) {
      printf("Unable to open tree file: %s\n", argv[2]);
      return(1); //exit with error
    }
    root = readTree(treeFile);
    close(treeFile);

    /* decompress the .huf file */
    huffFile = fopen(argv[1], "rb");
    if (huffFile == NULL) {
      printf("Unable to open compressed file: %s\n", argv[1]);
      return(1); //exit with error
    }
    outFile = fopen(argv[3], "wb");
    if (outFile == NULL) {
      printf("Unable to open output file: %s\n", argv[3]);
      return(1); //exit with error
    }

    decompress(huffFile, root, outFile);

    close(huffFile);
    close(outFile);

    if (TREEINFO) { //request for tree info
       puts("Decoding tree info:");
       printf(" %d total leaves.  ", countLeaves(root));
       printf("0x%.2x is the largest byte value.\n", largestValue(root));
    }

  }else {
    usage();
  }  
  return 0;
}


/*
 Returns a usage message for this program to the screen
 */
void usage() {
  puts("");
  puts("Usage:");
  puts("\thuffdcmp [compressed file] [tree file] [output file]");
  puts("");
  puts("Example use: huffdcmp myfile.huf myfile.tre myfile.out");
  puts("");
}
uhunix2:~/212% cat nodeTree.c
/* nodeTree.c  */
/* Builds a tree of nodes used in Huffman decompression.   */

/* Author: Zach Tomaszewski */
/* Date: 10 Mar 2002        */


#include "huffdcmp.h"
#include<stdlib.h>

#define MAXSTACK 30
Node* stack[MAXSTACK];
unsigned int stackCount;


/*
 Takes a pointer to an open and readable binary tree file.
 Builds a tree of Node.
 Returns a point to the root node.
*/
Node* readTree(FILE* fileIn){

   int nextChar;
   Node* left;
   Node* right;

   while ( (nextChar = getc(fileIn)) != EOF ){
     if (nextChar != '*') { // a leaf node
        if (nextChar == '\\') { //escaped character
           nextChar = getc(fileIn);
        }
        push(makeNode(nextChar, NULL, NULL));
     }else {  // an internal node
        nextChar = 0; //not used in internal nodes
        right = pop();
        left = pop();
        push(makeNode(nextChar, left, right));
     }
   }
   return pop();
}


/*
 Builds and returns a pointer to a node with the given contents.
   Returns NULL if memory can not be allocted.
*/
Node* makeNode(int content, Node* left, Node* right){
  Node* newNode;
  newNode = malloc(sizeof(Node));
  if (newNode != NULL) {
    (*newNode).left = left;
    (*newNode).right = right;
    (*newNode).content = content;
  }
  return newNode;
}



/*
 Adds a node to the top of the stack
*/
void push(Node* node){
  if (stackCount >= MAXSTACK) {
    puts("Error: Node stack overflowed while building the tree!");
    exit(1);
  }else {
    stackCount++;  //move up one space
    stack[stackCount - 1] = node;  //but index == count-1.
  }
}

/*
 Removes and returns the top node of the stack.
 Returns NULL if stack is empty.
*/
Node* pop(){
  if (stackCount == 0) {
    return NULL;
  }else {
    return stack[--stackCount]; //index == count- 1
  }
}



/*
  Prints a node tree to the screen.
  (Code by Wes Peterson.) 
*/
void printtree(Node* r)
{
    if(r==NULL) return;
    printf("%08x  ", r);  /* location of node  */
    if(r->left==NULL)  /* leaf node  */
        printf("(%02x)   ", r->content);
    else printf("Int.   ");  /* internal node  */
    printf("left = %08x  right = %08x\n",
        r->left,   r->right); /* The two pointers */
    printtree(r->left);  /* print the left subtree*/
    printtree(r->right); /* print the right subtree*/
}


/*
 Recursive function to return the number of leaves contained
  by a given node.
*/
int countLeaves(Node* n){
  if ((*n).left == NULL && (*n).right==NULL) { //leaf node
    return 1;
  }else {
    return (countLeaves((*n).left) + countLeaves((*n).right));
  }
}


/*
 Recursive function to return the largest byte value in any of the
  nodes within this tree.
*/
int largestValue(Node* n){
  int left = 0;
  int right = 0;
  int largest = (*n).content;
  if ((*n).left != NULL) {
    left = largestValue((*n).left);
  }
  if ((*n).right != NULL) {
    right = largestValue((*n).right);
  }
  largest = (left > largest) ? left : largest;
  largest = (right > largest) ? right : largest;
  return largest;
}

uhunix2:~/212% cat decompress.c
/* decompress.c  */
/* Uses a previously built nodetree to complete Huffman decompression.*/

/* Author: Zach Tomaszewski */
/* Date: 10 Mar 2002        */


#include "huffdcmp.h"


/*
 Takes: a readable compressed .huf file, 
        the root of a node tree for that file,
        and a file to output to.
 Decompresses the input file, printing the results to the output file.
*/

Node* decompress(FILE* fileIn, Node* tree, FILE* fileOut){
  int byte1 = fgetc(fileIn);
  int byte2 = fgetc(fileIn);
  int byte3 = fgetc(fileIn);

  while (byte3 != EOF) {
    process(byte1, 8, tree, fileOut);
    byte1 = byte2;
    byte2 = byte3;
    byte3 = fgetc(fileIn);
  } 
  /*hit end of file, so process last two bytes
    where last byte in file tells the number of bits to process
    of the second-to-last byte*/
  process(byte1, byte2, tree, fileOut);

}


/*
 Takes a byte,
   the number of bits to process in that byte,
   a pointer to a Huffman tree root node,
   and the file to output to.
 Decompresses the given number of bits in the byte, using the tree,
   and outputs to the output file.
*/
void process(char byte, int bits, Node* tree, FILE* fileOut){
  int i;
  char bit;
  for (i=1; i<=bits; i++){
     //shift over and mask to grab the ith bit from the ith
     bit = (byte >> (8 - i)) & 1;
     traverse(bit, tree, fileOut);
  }
}


/*
 Takes a bit (0 or 1),
   a pointer to Huffman tree root node,
   and a file to print to.
 Goes either left (0) or right (1) from the current position
 in the tree.  If doing so ends in a leaf node, prints the value
 of that node to the file and returns to the root position.  
 The function remembers the  current location in the tree; 
 it will reset to the root if given a different tree.
 reset to root if given a different tree.
*/
void traverse(char bit, Node* tree, FILE* fileOut) {
  static Node* root;
  static Node* current;

  if (root != tree) { //new tree
    root = tree;
    current = root;
  }

  if (bit == 0) { //go left
    current = (*current).left;
  }else { //go right
    current = (*current).right;
  }

  if ( (*current).left == NULL) { //leaf node, so print and reset
    fputc((*current).content, fileOut);
    current = root;
  }
}
uhunix2:~/212% make
gcc -c huffdcmp.c
gcc -c nodeTree.c
gcc -c decompress.c
gcc -g huffdcmp.o nodeTree.o decompress.o -o huffdcmp
uhunix2:~/212% huffdcmp poly.huf poly.tre poly.out
Decoding tree info:
 10 total leaves.  0x39 is the largest byte value.
uhunix2:~/212% huffdcmp se.huf se.tre se.out
Decoding tree info:
 23 total leaves.  0x78 is the largest byte value.
uhunix2:~/212% huffdcmp declares.huf declares.se declares.out
Unable to open tree file: declares.se
uhunix2:~/212% huffdcmp declares.huf declares.tre declares.out 
Decoding tree info:
 39 total leaves.  0x7a is the largest byte value.
uhunix2:~/212% huffdcmp msdev.huf msdev.tre msdev.out
Decoding tree info:
 252 total leaves.  0xff is the largest byte value.
uhunix2:~/212% sha1 poly.out 
File: poly.out  Size = 760 bits, or 95 bytes
SHA1 HASH: 9a5a404a: 2b1bced3: 296bc34b: 0406a04f: b507b738

uhunix2:~/212% sha1 poly.txt
File: poly.txt  Size = 760 bits, or 95 bytes
SHA1 HASH: 9a5a404a: 2b1bced3: 296bc34b: 0406a04f: b507b738

uhunix2:~/212% sha1 se.out
File: se.out  Size = 648 bits, or 81 bytes
SHA1 HASH: e2632519: c8ab80ba: dba6203d: 5230db75: 916fbf22

uhunix2:~/212% sha1 se.txt
File: se.txt  Size = 648 bits, or 81 bytes
SHA1 HASH: e2632519: c8ab80ba: dba6203d: 5230db75: 916fbf22

uhunix2:~/212% sha1 declares.out
File: declares.out  Size = 66336 bits, or 8292 bytes
SHA1 HASH: 4fcb5b03: bc2fb710: ad74e7a3: e62ebf77: 516ec786

uhunix2:~/212% sha1 declares.txt
File: declares.txt  Size = 66336 bits, or 8292 bytes
SHA1 HASH: 4fcb5b03: bc2fb710: ad74e7a3: e62ebf77: 516ec786

uhunix2:~/212% sha1 msdev.out
File: msdev.out  Size = 2163248 bits, or 270406 bytes
SHA1 HASH: 792a4f77: d2521648: 2b2f397d: 716ba0dc: 5ce1aedb

uhunix2:~/212% sha1 msdev.exe
File: msdev.exe  Size = 2163248 bits, or 270406 bytes
SHA1 HASH: 792a4f77: d2521648: 2b2f397d: 716ba0dc: 5ce1aedb

uhunix2:~/212% exit
uhunix2% 
script done on Tue Mar 11 04:57:57 2003
