SHARE
TWEET

Untitled

a guest May 25th, 2019 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*hdecode.c by Evan Fukumoto
  2.  * decodes a huffman encoded file*/
  3.  
  4. #include "huff.h"
  5. #define SIZE 100
  6. #define ASCII 256
  7.  
  8. int main(int argc, char *argv[]){
  9.     /*argument checks*/
  10.     int in, out, i, *chars, *counts, pqSize;
  11.     int mask;
  12.     char buff, toPrint;
  13.     uint32_t numChars, currCount;
  14.     uint8_t  currChar;
  15.     Node *head, *curr;
  16.     pqSize = 0;
  17.     mask = 12;
  18.  
  19.     /*check infile*
  20.      * default to stdin if can't open or file can't be opened*/
  21.     if(argc > 1){
  22.         if(strcmp(argv[1],"-") == 0){
  23.             in = 0;
  24.         }else if((in = open(argv[1], O_RDONLY)) < 1){
  25.             printf("usage: hdecode [(infile|-) [ outfile ]]"
  26.                    "\nIn file can't be opened \n");
  27.             return -1;
  28.         }
  29.     }else{
  30.         in = 0;
  31.     }
  32.     printf("%d\n", in);
  33.     /*check out file
  34.      * default to stdout if can't open or no file provided*/
  35.     if(argc > 2){
  36.         if((out = open(argv[2], O_WRONLY | O_CREAT | O_TRUNC, 0666)) < 1){
  37.             out = 1;
  38.         }
  39.     }else{
  40.         out = 1;
  41.     }
  42.     /*read the number of chars used*/
  43.     lseek(in, 0,SEEK_SET );
  44.     buff = 0;
  45.  
  46.     printf("%d",read(in, &buff, 1));
  47.     for(i = 0; i < 3; i++){
  48.         numChars = buff << 4;
  49.         printf("%d",read(in, &buff, 1));
  50.  
  51.     }
  52.  
  53.     if(numChars == 0){
  54.         return -1;
  55.     }
  56.  
  57.  
  58.     chars = (int *)malloc(numChars* sizeof(int));
  59.     counts = (int *)malloc(numChars* sizeof(int));
  60.     /*build a PQ w the chars*/
  61.     for(i = 0; i < numChars; i++){
  62.         read(in, &currChar, 1);
  63.         read(in, &currCount, 4);
  64.         if(head == NULL){
  65.             head = newNode(currChar,currCount);
  66.             pqSize++;
  67.         }else{
  68.             push(&head, currChar, currCount);
  69.             pqSize++;
  70.         }
  71.         chars[i] = (int) currChar;
  72.         counts[i] = (int) currCount;
  73.     }
  74.     head = makeTreeDecode(pqSize, &head);
  75.     /*read in sequence byte by byte
  76.      * traverse tree by byte, if a leaf, write char and*/
  77.     curr = head;
  78.     while(read(in, &buff, 1)){
  79.         for(i = 0; i < 4; i++){
  80.             if(mask & buff){
  81.                 /*is a 1*/
  82.                 curr = curr->right;
  83.             }else{
  84.                 /*is a 0*/
  85.                 curr = curr->left;
  86.             }
  87.             /*check for leaf node*/
  88.             if(curr->left == NULL && curr->right == NULL){
  89.                 /*write out the character
  90.                  * and reset curr to head*/
  91.                 toPrint = (char)curr->data;
  92.                 write(out, &toPrint, 1);
  93.                 curr = head;
  94.             }
  95.             buff = buff << 1;
  96.         }
  97.     }
  98.     /*free chars and counts*/
  99.     free(chars);
  100.     free(counts);
  101.     return 0;
  102. }
  103.  
  104. Node *makeTreeDecode(int pqSize, Node **head){
  105.     Node *temp1, *temp2;
  106.     while(pqSize > 1){
  107.         temp1 = pop(head);
  108.         temp2 = pop(head);
  109.         pushTree(head, temp1, temp2);
  110.         pqSize--;
  111.     }
  112.     return (*head);
  113. }
  114.  
  115. Node* newNode(int d, int p){
  116.     Node* temp = (Node*)malloc(sizeof(Node));
  117.     temp->data = d;
  118.     temp->priority = p;
  119.     temp->next = NULL;
  120.     temp->left = NULL;
  121.     temp->right = NULL;
  122.     return temp;
  123. }
  124.  
  125.  
  126. /*Removes the element with the
  127.  highest priority form the list*/
  128. Node *pop(Node** head)
  129. {
  130.     Node* temp = *head;
  131.     (*head) = (*head)->next;
  132.     return temp;
  133. }
  134.  
  135. /*Function to push according to priority*/
  136. void push(Node** head, int d, int p)
  137. {
  138.     Node* start = (*head);
  139.     /*Create new Node*/
  140.     Node* temp = newNode(d, p);
  141.     /*Special Case: The head of list has lesser*/
  142.     /*priority than new node. So insert new
  143.     node before head node and change head node.*/
  144.     if ((*head)->priority > p) {
  145.         /*Insert New Node before head*/
  146.         temp->next = *head;
  147.         (*head) = temp;
  148.     }
  149.     else {
  150.         /*Traverse the list and find a
  151.         position to insert new node*/
  152.         while (start->next != NULL &&
  153.                start->next->priority < p) {
  154.             start = start->next;
  155.         }
  156.         /*Either at the ends of the list
  157.         or at required position*/
  158.         temp->next = start->next;
  159.         start->next = temp;
  160.     }
  161. }
  162.  
  163. void pushTree(Node** head, Node *temp1, Node* temp2)
  164. {
  165.     Node *start, *temp;
  166.     int p;
  167.     p = temp1->priority+ temp2->priority;
  168.     start = (*head);
  169.     /*Create new Node*/
  170.     temp = newNode(-1, p);
  171.     temp->left = temp1;
  172.     temp->right = temp2;
  173.     /*Special Case: The head of list has lesser*/
  174.     /*priority than new node. So insert new
  175.     node before head node and change head node.*/
  176.     if(*head != NULL){
  177.         if ((*head)->priority <= p){
  178.             /*Insert New Node before head*/
  179.             temp->next = *head;
  180.             (*head) = temp;
  181.         }
  182.         else {
  183.             /*Traverse the list and find a
  184.             position to insert new node*/
  185.             while (start->next != NULL &&
  186.                    start->next->priority >= p) {
  187.                 start = start->next;
  188.             }
  189.             /*Either at the ends of the list
  190.             or at required position*/
  191.             temp->next = start->next;
  192.             start->next = temp;
  193.         }
  194.     }else{
  195.         temp->next = NULL;
  196.         *head = temp;
  197.     }
  198.  
  199. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top