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 /*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 #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