coding.c

//Huffman coding
//Adam Rachuba
//Coding program
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#define BUFFER_SIZE 128
#define MAX_CODE_BYTE 4

int symbols_number = 0;
int nodes_number = 0;

struct symbol_data
{
    unsigned char symbol;
    int number;
};

struct node
{
    int value;
    int symbol;
    struct node *right;
    struct node *left;
};

struct code_table
{
    int symbol;
    unsigned char code[MAX_CODE_BYTE];
    unsigned char length;
};

char *new_extension(const char file[], const char new_extension[])
{
    int n = strlen(file);
    int i = n - 1;
    while (i >= 0 && file[i] != '.') i--;
    char *new_file = malloc((n + strlen(new_extension) + 2) * sizeof(char));
    if (new_file == NULL)
    {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    if (i > 0) 
    {
        strncpy(new_file, file, i + 1);
        new_file[i + 1] = '\0';
    }
    else if(i==0) strcpy(new_file, file);
    strcat(new_file, new_extension);
    return new_file;
}

int count_bytes(char name_file[]) 
{
    FILE *file = fopen(name_file, "rb");
    if (file == NULL) 
    {
        fprintf(stderr,"Cannot open file %s for writing\n", name_file);
        exit(EXIT_FAILURE);
    }
    fseek(file, 0, SEEK_SET);
    int byte_count = 0;
    char buffer[BUFFER_SIZE];
    size_t bytes_read;
    while ((bytes_read = fread(buffer, 1, sizeof(buffer), file)) > 0) byte_count += bytes_read;
    fclose(file);
    return byte_count;
}

void save(char name_file[], int info)
{
    FILE *file = fopen(name_file, "w");
    if (file == NULL)
    {
        fprintf(stderr, "Cannot open file %s for writing.\n", name_file);
        exit(EXIT_FAILURE);
    }
    fprintf(file, "%d", info);
    fclose(file);
}

//SEKCJA SHANNONA

struct symbol_data* create_Shannon(char name_file[])
{
    struct symbol_data *Shannon_model = malloc(256 * sizeof(struct symbol_data));
    if (Shannon_model == NULL)
    {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    
    FILE *file = fopen(name_file, "rb");
    if (file == NULL)
    {
        printf("Cannot open file %s for writing\n", name_file);
        exit(EXIT_FAILURE);
    }
    int n;
    for (n = 0; n < 256; n++)
    {
        int counter = 0;
        unsigned char buffer[BUFFER_SIZE];
        size_t bytes_read;
        fseek(file, 0, SEEK_SET);
        while ((bytes_read = fread(buffer, 1, sizeof(buffer), file)) > 0)
        {
            int i = 0;
            for (i = 0; i < bytes_read; i++) if (buffer[i] == n) counter++;
        }
        Shannon_model[n].symbol = n;
        Shannon_model[n].number = counter;
        if (counter > 0) symbols_number++;
    }
    fclose(file);
    return Shannon_model;
}

struct symbol_data* create_modelShannon(struct symbol_data Shannon_model[], char name_file[]) 
{
    struct symbol_data *temp = malloc(symbols_number * sizeof(struct symbol_data));
    if (temp == NULL) 
    {
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    int i = 0, j = 0;
    for (i = 0; i < 256; i++) 
    {
        if (Shannon_model[i].number > 0) 
        {
            temp[j].symbol = Shannon_model[i].symbol;
            temp[j].number = Shannon_model[i].number;
            j++;
        }
    }
    
    struct symbol_data *temp_ptr = realloc(Shannon_model, symbols_number * sizeof(struct symbol_data));
    if (temp_ptr == NULL) 
    {
        fprintf(stderr, "Memory reallocation failed\n");
        free(temp);
        exit(EXIT_FAILURE);
    }
    Shannon_model = temp_ptr;
    
    memcpy(Shannon_model, temp, symbols_number * sizeof(struct symbol_data));
    free(temp);

    FILE *file = fopen(name_file, "wb");
    if (file == NULL)
    {
        fprintf(stderr, "Cannot open file %s for writing.\n", name_file);
        exit(EXIT_FAILURE);
    }

    int n=0;
    for (n = 0; n < symbols_number; n++)
    {
        fprintf(file, "%d %d\n", Shannon_model[n].symbol, Shannon_model[n].number);
    }

    fclose(file);
}

void create_sortModelShannon(struct symbol_data Shannon_model[], char name_file[]) 
{
    int i=0, j=0;
    struct symbol_data temp;

    for (i = 0; i < symbols_number - 1; i++) 
    {
        for (j = 0; j < symbols_number - i - 1; j++) 
        {
            if (Shannon_model[j].number < Shannon_model[j + 1].number) 
            {
                temp = Shannon_model[j];
                Shannon_model[j] = Shannon_model[j + 1];
                Shannon_model[j + 1] = temp;
            }
        }
    }

    FILE *file = fopen(name_file, "wb");
    if (file == NULL)
    {
        fprintf(stderr, "Cannot open file %s for writing.\n", name_file);
        exit(EXIT_FAILURE);
    }

    int n=0;
    for (n = 0; n < symbols_number; n++)
    {
        fprintf(file, "%d %d\n", Shannon_model[n].symbol, Shannon_model[n].number);
    }

    fclose(file);
}

//SEKCJA DRZEWA

void travel(FILE *file, struct node* root) 
{
    nodes_number++;
    if (root != NULL) 
    {
    	if(root->symbol<255) return;
        fprintf(file, "%d ", root->symbol);
        if(root->right==NULL) fprintf(file, "%d ", -1);
        else fprintf(file, "%d ", root->right->symbol);
        if(root->left==NULL) fprintf(file, "%d\n", -1);
        else fprintf(file, "%d\n", root->left->symbol);
        travel(file, root->right);
        travel(file, root->left);
    }
}

struct node* binary_tree(struct symbol_data Shannon_model[], char name_file[]) 
{
    struct node **roots = malloc(symbols_number * sizeof(struct node *));
    if (roots == NULL) 
    {
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    int i = 0;
    for (i = 0; i < symbols_number; i++) 
    {
        roots[i] = malloc(sizeof(struct node));
        if (roots[i] == NULL) 
        {
            fprintf(stderr, "Memory allocation failed\n");
            exit(EXIT_FAILURE);
        }
        roots[i]->value = Shannon_model[i].number;
        roots[i]->symbol = Shannon_model[i].symbol;
        roots[i]->right = NULL;
        roots[i]->left = NULL;
    }
    
    int trees_number = symbols_number;
    int node_number = 256;
    
    if (trees_number == 1) 
    {
        struct node *temp_tree = malloc(sizeof(struct node));
        if (temp_tree == NULL) 
        {
            fprintf(stderr, "Memory allocation failed\n");
            exit(EXIT_FAILURE);
        }   
        temp_tree->value = roots[0]->value;
        temp_tree->symbol = node_number++;
        temp_tree->right = roots[0];
        temp_tree->left = NULL;
        roots[0]=temp_tree;
    }
    
    while (trees_number != 1) 
    {
        struct node *temp_tree = malloc(sizeof(struct node));
        if (temp_tree == NULL) 
        {
            fprintf(stderr, "Memory allocation failed\n");
            exit(EXIT_FAILURE);
        }

        int temp_value = roots[trees_number - 1]->value + roots[trees_number - 2]->value;
        temp_tree->value = temp_value;
        temp_tree->symbol = node_number++;
        temp_tree->right = roots[trees_number - 1];
        temp_tree->left = roots[trees_number - 2];
        roots[trees_number - 1] = NULL;
        roots[trees_number - 2] = temp_tree;

        struct node **temp_roots = realloc(roots, (trees_number - 1) * sizeof(struct node *));
        if (temp_roots == NULL) 
        {
            fprintf(stderr, "Memory allocation failed\n");
            exit(EXIT_FAILURE);
        }
        roots = temp_roots;
        int number = 2;
        for (;;) 
        {
            if(trees_number - number==0) break;
            if (roots[trees_number - number]->value < roots[trees_number - number - 1]->value) 
            {
                break;
            } 
            else 
            {
                struct node *temp_node = roots[trees_number - number];
                roots[trees_number - number] = roots[trees_number - number - 1];
                roots[trees_number - number - 1] = temp_node;
                number++;
            }
        }
        trees_number--;
    }
    struct node *root = roots[0];
    free(roots);

    FILE *file = fopen(name_file, "wb");
    if (file == NULL) 
	{
        fprintf(stderr, "Cannot open file %s for writing.\n", name_file);
        exit(EXIT_FAILURE);
    }
    travel(file, root);
    fclose(file);
    return root;
}

// SEKCJA TABLICY KODU

void numbering_tree(struct code_table code_tab[], char *code_prev, struct node *root, int position, int bit) 
{
    if (root == NULL) return;
    
    char *code = malloc(MAX_CODE_BYTE * sizeof(char));
    if (code_prev != NULL) 
    {
        int i;
        for (i = 0; i < MAX_CODE_BYTE; i++) code[i] = code_prev[i];
    }
    
    if (bit == 1) code[position / 8] |= (1 << (7 - (position % 8)));
    
    int i;
    for (i = 0; i < MAX_CODE_BYTE; i++) code_tab[nodes_number].code[i] = code[i];
    code_tab[nodes_number].symbol=root->symbol;
    code_tab[nodes_number].length=position+1;
    nodes_number++; 
    
    numbering_tree(code_tab, code, root->left, position + 1, 0);
    numbering_tree(code_tab, code, root->right, position + 1, 1);
    
    free(code);
}

struct code_table* create_fullCodeTable(struct node *root, char name_file[]) 
{
    if (root == NULL) return NULL;
    
    struct code_table *code_tab = malloc(nodes_number * sizeof(struct code_table));
    if (code_tab == NULL) 
    {
        fprintf(stderr, "Memory allocation failed for code_tab.\n");
        exit(EXIT_FAILURE);
    }
    
    nodes_number = 0;
    char *code = malloc(MAX_CODE_BYTE * sizeof(char));
    if (code == NULL) 
    {
        fprintf(stderr, "Memory allocation failed for code.\n");
        exit(EXIT_FAILURE);
    }
    
    int i;
    for (i = 0; i < MAX_CODE_BYTE; i++) code[i] = 0;
    numbering_tree(code_tab, code, root->left, 0, 0);
    numbering_tree(code_tab, code, root->right, 0, 1);
    
    FILE *file = fopen(name_file, "wb");
    if (file == NULL) 
    {
        fprintf(stderr, "Cannot open file %s for writing.\n", name_file);
        exit(EXIT_FAILURE);
    }

    for (i=0; i<nodes_number; i++)
    {
        fprintf(file,"%d ",code_tab[i].symbol);
        int j;
        for (j=0; j<MAX_CODE_BYTE; j++) fprintf(file,"%d ",code_tab[i].code[j]);
        fprintf(file,"%d\n",code_tab[i].length);
    }
    fclose(file);
    free(code);
    return code_tab;
}

struct code_table* create_codeTable(struct code_table *code_tab, char name_file[]) 
{
    int i,k = 0;
    for (i = 0; i < nodes_number; i++) 
    {
        if (code_tab[i].symbol < 256) 
        {
            int j;
            code_tab[k].symbol = code_tab[i].symbol;
            for (j = 0; j < MAX_CODE_BYTE; j++) code_tab[k].code[j] = code_tab[i].code[j];
            code_tab[k].length = code_tab[i].length;
            k++;
        }
    }

    struct code_table *temp = realloc(code_tab,symbols_number*sizeof(struct code_table));
    if (temp == NULL) 
    {
        fprintf(stderr, "Memory reallocation failed for code_tab.\n");
        exit(EXIT_FAILURE);
    } 
    else code_tab = temp;
    
    FILE *file = fopen(name_file, "wb");
    if (file == NULL) 
    {
        fprintf(stderr, "Cannot open file %s for writing.\n", name_file);
        exit(EXIT_FAILURE);
    }

    for (i = 0; i < symbols_number; i++) 
    {
        fprintf(file, "%d ",code_tab[i].symbol);
        int j;
        for (j = 0; j < MAX_CODE_BYTE; j++) fprintf(file, "%d ", code_tab[i].code[j]);
        fprintf(file, "%d\n", code_tab[i].length);
    }
    fclose(file);
    return code_tab;
}

//SEKCJA PLIKU WYNIKOWEGO

void create_compressedFile(struct code_table code_tab[], char name_fileIn[], char name_fileOut[])
{
    FILE *fileIn = fopen(name_fileIn, "rb");
    if (fileIn == NULL)
    {
        fprintf(stderr, "Cannot open file %s for reading\n", name_fileIn);
        exit(EXIT_FAILURE);
    }

    FILE *fileOut = fopen(name_fileOut, "wb");
    if (fileOut == NULL)
    {
        fprintf(stderr, "Cannot open file %s for writing\n", name_fileOut);
        exit(EXIT_FAILURE);
    }

    unsigned char buffer[BUFFER_SIZE];
    int byteCounterIn = 0;
    int byteCounterOut = 0;
    int bitCounterOut = 0;
    int cursor = 0;
    char byteEncoded = 0;
    int bytesRead;

    while ((bytesRead = fread(buffer, 1, sizeof(buffer), fileIn)) > 0)
    {
        byteCounterIn += bytesRead;

        int i;
        for (i = 0; i < bytesRead; i++)
        {
            int j;
            for (j = 0; j < symbols_number; j++)
            {
                if (code_tab[j].symbol == buffer[i])
                {
                    int k;
                    for (k = 0; k < code_tab[j].length; k++)
                    {
                        byteEncoded |= (code_tab[j].code[k / 8] >> (7 - (k % 8))) & 1;
                        cursor++;
                        bitCounterOut++;
                        if (cursor == 8)
                        {
                            fwrite(&byteEncoded, sizeof(char), 1, fileOut);
                            byteEncoded = 0;
                            cursor = 0;
                            byteCounterOut++;
                        }
                        else
                        {
                            byteEncoded <<= 1;
                        }
                    }
                }
            }
        }
    }

	if (cursor > 0)
	{
	    byteEncoded <<= (8 - cursor);
	    fwrite(&byteEncoded, sizeof(char), 1, fileOut);
	    byteCounterOut++;
	    printf("Last (incomplete) byte of the compression stream\n");
	    printf("Byte number %d, hexdec code of the byte %02X \n", byteCounterOut, byteEncoded & 0xFF);
	}
	else
	{
	    printf("Last (full) byte of the compression stream\n");
	    printf("Byte number %d, hexdec code of the byte %02X \n", byteCounterOut, byteEncoded & 0xFF);    
	}
	
	printf("Number of processed bytes from the input file: %d\n", byteCounterIn);
	printf("Number of encoded bytes in the compressed file: %d \n", byteCounterOut);
	printf("Number of encoded bits in the compressed file: %d \n", bitCounterOut);
	printf("Compression ratio: %5.1f percent\n", (float)(100 * (float)(byteCounterOut) / (float)byteCounterIn));

    fclose(fileIn);
    fclose(fileOut);
}

void set_filenames(char* filenames[], char *argv[])
{
    filenames[0] = strdup(new_extension(argv[1], "bytes"));
    filenames[1] = strdup(new_extension(argv[1], "model"));
    filenames[2] = strdup(new_extension(argv[1], "modelSort"));
    filenames[3] = strdup(new_extension(argv[1], "tree"));
    filenames[4] = strdup(new_extension(argv[1], "codeTableFull"));
    filenames[5] = strdup(new_extension(argv[1], "codeTable"));
    filenames[6] = strdup(new_extension(argv[1], "huffman"));
}

int main(int argc, char *argv[]) 
{
    if (argc != 2)
    {
        printf("Give name of file as parameter!\n");
        exit(EXIT_FAILURE);
    }
    
    char *filenames[7];
    set_filenames(filenames, argv);
    
    int byte_number = count_bytes(argv[1]);
    save(filenames[0],byte_number);
    
    struct symbol_data* Shannon_model=create_Shannon(argv[1]);
    create_modelShannon(Shannon_model,filenames[1]);
    create_sortModelShannon(Shannon_model,filenames[2]);
    
    struct node* root = binary_tree(Shannon_model, filenames[3]);
    struct code_table *code_tab=create_fullCodeTable(root,filenames[4]);
    code_tab=create_codeTable(code_tab,filenames[5]);
    
    create_compressedFile(code_tab,argv[1],filenames[6]);
    
    free(Shannon_model);
    free(code_tab);

    int i;
    for (i = 0; i < 7; i++) free(filenames[i]);
    
    return 0;
}