SHARE
TWEET

Untitled

a guest May 25th, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "huff.h"
  2. #define SIZE 100
  3. #define ASCII 256
  4.  
  5.  
  6.  
  7. int main(int argc, char *argv[]){
  8.     /*args check*/
  9.     int  in, out, freqs[ASCII], *freqs2, i,j, chars,
  10.     pqSize, *val, codelen, toAddSize, carrySize, carryChar;
  11.     int codes[ASCII], codelens[ASCII];
  12.     uint8_t toPack;
  13.     char buff[SIZE];
  14.     Node *head, *temp1, *temp2;
  15.     head = NULL;
  16.     temp1 = NULL;
  17.     temp2 = NULL;
  18.     codelen = 0;
  19.     out = 1;
  20.     chars = 0;
  21.     carryChar = 0;
  22.     toAddSize = 0;
  23.     pqSize = 0;
  24.     j = 0;
  25.     carrySize = 0;
  26.     codelen = 0;
  27.     for(i = 0; i< 256; i++){
  28.         codelens[i] = 0;
  29.     }
  30.  
  31.  
  32.     /*check in file*/
  33.     if(argc > 3 || argc < 2){
  34.         printf("usage: hencode infile [ outfile ]\n");
  35.         return -1;
  36.     }
  37.     if( (in = open(argv[1], O_RDONLY)) < 1){
  38.         printf("usage: hencode infile [ outfile ]\n");
  39.         return -1;
  40.     }
  41.  
  42.     /*check outfile*/
  43.     if(argc == 3 &&
  44.        (out = open(argv[2], O_WRONLY | O_CREAT | O_TRUNC, 0666)) < 0){
  45.         exit(-1);
  46.     }
  47.  
  48.     /*init the freq table*/
  49.     for(i = 0; i < ASCII; i++){
  50.         freqs[i] = 0;
  51.     }
  52.     /*zero out the buff*/
  53.     for(i = 0; i < SIZE; i++ ){
  54.         buff[i] = (char) 0;
  55.     }
  56.     while(read(in, buff, SIZE) > 0){
  57.         i = 0;
  58.         while(buff[i] != 0){
  59.             freqs[(int)buff[i]]++;
  60.             buff[i] = (char)0;
  61.             i++;
  62.         }
  63.     }
  64.  
  65.  
  66.     /*create PQ and count used chars*/
  67.     initPQ(freqs, i, &chars, &pqSize, &head);
  68.     if(chars != 0){
  69.  
  70.  
  71.         /*make tree*/
  72.         head = makeTree(pqSize, &head, temp1, temp2);
  73.  
  74.         /*create huffcodes*/
  75.         makecode(head,0,codes, codelen, codelens);
  76.     }
  77.  
  78.  
  79.     /*make out file header */
  80.     /*write numchars*/
  81.     val = (int *)malloc(chars*sizeof(int));
  82.     freqs2 = (int *)malloc(chars* sizeof(int));
  83.  
  84.     if(chars != 0){
  85.         for(i = 0, j = 0; i < ASCII; i++){
  86.             if(freqs[i]!= 0){
  87.                 freqs2[j] = freqs[i];
  88.                 val[j]  = i;
  89.                 j++;
  90.             }
  91.         }
  92.     }
  93.  
  94.     /*initialize these guys*/
  95.     toAddSize = 0;
  96.     carrySize = 0;
  97.     carryChar = -1;
  98.     writeHeaderOut(out, i, &chars, freqs2, val);
  99.     if(chars !=0 ){
  100.         writeBodyOut(in, out, i, codelens,
  101.                      toAddSize, &toPack, carrySize, carryChar, codes, buff, j);
  102.     }
  103.     /*free tree*/
  104.     freeTree(head);
  105.     /*free val and freqs2*/
  106.     free(val);
  107.     free(freqs2);
  108.  
  109.  
  110.     return 0;
  111. }
  112. void freeTree(Node *node){
  113.     if(node != NULL){
  114.         /*call on right and left*/
  115.         freeTree(node->right);
  116.         freeTree(node->left);
  117.         free(node);
  118.     }
  119. }
  120.  
  121. void writeBodyOut(int in, int out, int i, const int *codelens,
  122.         int toAddSize, uint8_t *toPack, int carrySize, int carryChar,
  123.                   const int *codes, char *buff, int j) {
  124.     /*write encoded document*/
  125.     /*reset to begining of document*/
  126.     lseek(in,0,SEEK_SET);
  127.     for(i =0; i < 100; i++){
  128.         buff[i] = 0;
  129.     }
  130.     /*start write*/
  131.     while(read(in,(void *) buff, SIZE) > 0){
  132.         i = 0;
  133.         j = 0;
  134.  
  135.         while(buff[i] != 0 && i < SIZE){
  136.             /*until you read the whole line
  137.             * reset packing int, size*/
  138.             (*toPack) = 0;
  139.             toAddSize = 0;
  140.             if(carrySize >8){
  141.                 /*if can't be written in one carry*/
  142.                 while(carrySize >= 8){
  143.                     (*toPack) |= (codes[(int)buff[i]] << (8 - carrySize));
  144.                     write(out, toPack, 1);
  145.                     carrySize = 8 - carrySize;
  146.                 }
  147.             }
  148.             if(carrySize > 0 && carrySize < 8){
  149.                 /*if theres a left over, pack
  150.                  * the rest of it but needs more packed*/
  151.                 (*toPack) |= (codes[carryChar] << (8 - carrySize));
  152.             }
  153.             /*reset carries*/
  154.             carryChar = 0;
  155.             carrySize = 0;
  156.             while(toAddSize < 8 && i < 100 && buff[i] != 0){
  157.                 /*find out how many chars we can write*/
  158.                 toAddSize += codelens[(int)buff[i]];
  159.                 (*toPack) |= (codes[(int)buff[i]] << (8 - toAddSize));
  160.                 i++;
  161.                 j++;
  162.             }
  163.             if(toAddSize > 8){
  164.                 /*if there is leftover, save the char
  165.                 * and the amount that didn't get written*/
  166.                 carryChar = buff[i];
  167.                 carrySize = toAddSize - 8;
  168.             }
  169.             write(out, toPack, 1);
  170.  
  171.         }
  172.         for(i =0; i < 100; i++){
  173.             buff[i] = (char)0;
  174.         }
  175.     }
  176. }
  177.  
  178. void initPQ(const int *freqs, int i, int *chars, int *pqSize, Node **head) {
  179.     (*chars) = 0;
  180.     (*pqSize) = 0;
  181.     /*create PQ and count used chars*/
  182.     for(i = 0; i < ASCII; i++){
  183.         if(freqs[i] != 0){
  184.             if((*head) == NULL){
  185.                 (*head) = newNode(i, freqs[i]);
  186.                 (*pqSize)++;
  187.             }else{
  188.                 push(head, i, freqs[i]);
  189.                 (*pqSize)++;
  190.             }
  191.             (*chars)++;
  192.         }
  193.     }
  194. }
  195.  
  196. Node *makeTree(int pqSize, Node **head, Node *temp1, Node *temp2) {
  197.     while(pqSize > 1){
  198.         temp1 = pop(head);
  199.         temp2 = pop(head);
  200.         pushTree(head, temp1, temp2);
  201.         pqSize--;
  202.     }
  203.     return (*head);
  204. }
  205.  
  206. void writeHeaderOut(int out, int i, int *chars, const int *freqs2,
  207.                     const int *val) {
  208.     /*write header files, start w amount of codes*/
  209.  
  210.     uint8_t buff1;
  211.     uint32_t buff2;
  212.     buff2 = *chars;
  213.     write(out, &buff2, 4);
  214.     for(i = 0; i < (*chars) ; i++){
  215.         buff1 = (uint8_t) val[i];
  216.         buff2 = (uint32_t) freqs2[i];
  217.         write(out, &buff1, 1);
  218.         write(out, &buff2, 4);
  219.     }
  220.  
  221. }
  222.  
  223.  
  224. /* Function to Create A New Node*/
  225. Node* newNode(int d, int p)
  226. {
  227.     Node* temp = (Node*)malloc(sizeof(Node));
  228.     temp->data = d;
  229.     temp->priority = p;
  230.     temp->next = NULL;
  231.     temp->left = NULL;
  232.     temp->right = NULL;
  233.     return temp;
  234. }
  235.  
  236.  
  237. /*Removes the element with the
  238.  highest priority form the list*/
  239. Node *pop(Node** head)
  240. {
  241.     Node* temp = *head;
  242.     (*head) = (*head)->next;
  243.     return temp;
  244. }
  245.  
  246. /*Function to push according to priority*/
  247. void push(Node** head, int d, int p)
  248. {
  249.     Node* start = (*head);
  250.     /*Create new Node*/
  251.     Node* temp = newNode(d, p);
  252.     /*Special Case: The head of list has lesser*/
  253.     /*priority than new node. So insert new
  254.     node before head node and change head node.*/
  255.     if ((*head)->priority > p) {
  256.         /*Insert New Node before head*/
  257.         temp->next = *head;
  258.         (*head) = temp;
  259.     }
  260.     else {
  261.         /*Traverse the list and find a
  262.         position to insert new node*/
  263.         while (start->next != NULL &&
  264.                start->next->priority < p) {
  265.             start = start->next;
  266.         }
  267.         /*Either at the ends of the list
  268.         or at required position*/
  269.         temp->next = start->next;
  270.         start->next = temp;
  271.     }
  272. }
  273.  
  274. void pushTree(Node** head, Node *temp1, Node* temp2)
  275. {
  276.     Node *start, *temp;
  277.     int p;
  278.     p = temp1->priority+ temp2->priority;
  279.     start = (*head);
  280.     temp1->next = NULL;
  281.     temp2->next = NULL;
  282.     /*Create new Node*/
  283.     temp = newNode(-1, p);
  284.     temp->left = temp1;
  285.     temp->right = temp2;
  286.     /*Special Case: The head of list has lesser*/
  287.     /*priority than new node. So insert new
  288.     node before head node and change head node.*/
  289.     if(*head != NULL){
  290.         if ((*head)->priority >= p) {
  291.             /*Insert New Node before head*/
  292.             temp->next = *head;
  293.             (*head) = temp;
  294.         }
  295.         else {
  296.             /*Traverse the list and find a
  297.             position to insert new node*/
  298.             while (start->next != NULL &&
  299.                    start->next->priority <= p) {
  300.                 start = start->next;
  301.             }
  302.             /*Either at the ends of the list
  303.             or at required position*/
  304.             temp->next = start->next;
  305.             start->next = temp;
  306.         }
  307.     }else{
  308.         temp->next = NULL;
  309.         *head = temp;
  310.     }
  311.  
  312. }
  313.  
  314. void makecode(Node *curr, int code,int *codes, int codelen, int *codelens){
  315.     /*is a leaf node*/
  316.     codelen++;
  317.     if(curr->left == NULL && curr->right == NULL){
  318.         codes[curr->data] = code;
  319.         codelens[curr->data] = codelen;
  320.     }
  321.     if(curr->left){
  322.         code = code << 1;
  323.  
  324.         makecode(curr->left,code,codes,codelen, codelens);
  325.     }
  326.     if(curr->right){
  327.         /*code = code << 1;*/
  328.         code++;
  329.         /*codelen++;*/
  330.         makecode(curr->right,code,codes,codelen, codelens);
  331.     }
  332. }
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