#include <iostream>
#include <math.h>
#include "gzip.h"
#include <unistd.h>
#include "huffman.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
FILE* gzFile;

long getOrigFileSize(FILE * gzFile);
int isDynamicHuffman(unsigned char rb);
void bits2String(char *strBits, unsigned char byte);
int getNumberOfCodes(int necessaryBits, int exp);
int bitsAddicionaisHDIST(int index);
void lengthLengthAlfa();
void getHuffmanCodes(int lengths [], int n_codes, HuffmanTree * tree);
unsigned int_to_int(unsigned k);

unsigned char byte;  //varavel temporaria para armazenar um byte lido directamente do ficheiro
unsigned int rb = 0;  //ultimo byte lido (podera ter mais que 8 bits, se tiverem sobrado alguns de leituras anteriores)
char availBits = 0;
int hLit, hDist, hcLen;
int *hLit_lengths;
int *hDist_lengths;
unsigned char * output_stream;
void checkaNaArvore(int * lengths, int size);

// raizes das 3 arvores
HuffmanTree* HCLen_tree = createHFTree();
HuffmanTree* hDist_tree = createHFTree();
HuffmanTree* hLit_tree = createHFTree();

int main() {
    char oneChar;
    long fileSize;
    long origFileSize;
    int numBlocks = 0;
    char needBits = 0;
    gzipHeader gzh;


    gzFile = fopen("FAQ.txt.gz", "rb");
    if (!gzFile) {
        perror("FAQ.txt.gz"); exit(EXIT_FAILURE);
    }

    fseek(gzFile, 0L, SEEK_END);
    fileSize = ftell(gzFile);
    fseek(gzFile, 0L, SEEK_SET);

    //ler tamanho do ficheiro original (acrescentar: e definir Vector com s�mbolos
    origFileSize = getOrigFileSize(gzFile);

    //--- ler cabe�alho
    int erro = getHeader(gzFile, &gzh);
    if (erro != 0)
    {
        printf ("Formato inválido!!!");
        return -1;
    }

    //--- Para todos os blocos encontrados
    char BFINAL;

    do
    {
        //--- ler o block header: primeiro byte depois do cabecalho do ficheiro
        needBits = 3;
        if (availBits < needBits)
        {
            fread(&byte, 1, 1, gzFile);
            rb = (byte << availBits) | rb;
            availBits += 8;
        }

        //obter BFINAL
        //ver se � o �ltimo bloco
        BFINAL = rb & 0x01; //primeiro bit e o menos significativo
        rb = rb >> 1; //descartar o bit correspondente ao BFINAL
        availBits -=1;

        //analisar block header e ver se � huffman din�mico
        if (!isDynamicHuffman(rb))  //ignorar bloco se n�o for Huffman din�mico
            continue;
        rb = rb >> 2; //descartar os 2 bits correspondentes ao BTYPE
        availBits -= 2;
        printf("BITS-> %d\n",availBits);

        //--- Se chegou aqui --> compactado com Huffman din�mico --> descompactar

        hLit = getNumberOfCodes(5,0x1F);
        hDist = getNumberOfCodes(5,0x1F);
        hcLen = getNumberOfCodes(4,0x0F);
        printf("\nValores dos codigos:\n____________________________________\n| HLIT: %d | HDIST: %d | HCLEN: %d |\n|__________|___________|___________|\n\n\n", hLit, hDist, hcLen);

        // alfabeto de comprimentos de codigos
        lengthLengthAlfa();

        //hLit_lengths = comprimentos dos códigos do alfabeto de literais e comprimentos
        hLit_lengths = (int*)malloc(sizeof(int) * (hLit+257));
        checkaNaArvore(hLit_lengths, hLit+257);

        printf("Comprimentos dos códigos do alfabeto de literais e comprimentos:\n");
        for (int i=0; i<hLit+257; i++) {
            printf("hLit_lengths[%d] -> %d\n", i, hLit_lengths[i]);
        }
        printf("_________________________________________\n");
        printf("Criar árvore para hLit:\n");
        getHuffmanCodes(hLit_lengths, hLit+257, hLit_tree);
        printf("_________________________________________\n");

        //hDist_lengths = comprimentos dos códigos do alfabeto de distancias
        hDist_lengths = (int*)malloc(sizeof(int) * (hDist+1));
        checkaNaArvore(hDist_lengths, hDist + 1);


        printf("Comprimentos dos códigos do alfabeto de distâncias:\n");
        for (int i=0; i<hDist+1; i++) {
            printf("hDist_lengths[%d] -> %d\n", i, hDist_lengths[i]);
        }
        printf("_________________________________________\n");
        printf("Criar árvore para hDist:\n");
        getHuffmanCodes(hDist_lengths, hDist+1, hDist_tree);
        printf("_________________________________________\n");


        // ______________________ decoding the actual data bytes ___________________________________________________________
        char *aux;
        HuffmanTree value;
        int index,indexDist;
        char *symbol = (char*)malloc(sizeof(char)*18);
        int k = 0;
        int i=0;
        // availBits = 0;
        printf("BITS-> %d\n",availBits);
        int needBits = 1;


        printf("-------------->>.. DECODING .. <<------------\n");
        int auxi=0;
        char* to_copy = (char*)malloc(sizeof(char)*50);
        //char *final[99999];
        char *strr[20];
        strr[0]='\0';

        int recua=0;
        int bitsAddi=0;
        int bitLido=0;
        do{
           // usleep(200000);
            //printf("iteração: %d\n", i);
            // procurar proxima folha na arvore de literais/comprimentos
            // lê 1 bit da input stream
            if (availBits < needBits) {
                //printf("A ler um byte...\n");
                fread(&byte, 1, 1, gzFile);
                availBits = 8;
            }

            rb = byte & 0x01; // guarda apenas o bit maissignificativo (o da direita) -------------------------------------------------->>> ATENÇÃO !!!! Aqui também é para ler da direita para a esquerda? Vamos descobrir

            byte = byte >> 1; // discarda um bit já lido

            //printf("symbol int: %d\n", rb);

            symbol[k] = rb+ '0'; // vai guardando todos os bits lidos
            printf("symbol[%d] = %c\n", k, symbol[k]);
            i++;
            k++;
            availBits--;
            // anda um bit para a frente a partir da root da árvore hLit
            //index = nextNode(hLit_tree, rb);
            //printf("andou um nó para a frente. teste = %d\n", index);
            ///TESTE

            index=findNode(hLit_tree,symbol,0);

            ////
            //strr
            /*
             TODO------------------------------------------------------==============================================================<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
             -Fazer uma string acumuladora para fazer o findNode v
             -ao encontrar uma folha -> igualar string a \0  v
             -MEter as condições quando encontra cod de distancia e ir a arvore de dist ta mesma maneira (ATENÇÃO BITS ADICIONAIS)
             -Tratar do seg fault da leitura do ficheiro X
             ------------------------------------------------------==============================================================<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<


             */

            //index=findNode(hLit_tree,"111110100",0);






            //printf("andou um nó para a frente. teste = %d\n", index);
            if (index >= 0) {
                // é uma folha!

                printf("(LEAF = %d)encontrei folha!\n",index);

                printf("> %d\n",index);
                printf("STRING : %s\n",symbol);
                //symbol[k]='\0';

                //copiar para output stream


                memset(symbol, ' ', (sizeof(char))*18); //limpa o array
                k=0;
                //final[i]=static_cast<char>(index);
                bitsAddi=0;
                recua=0;
                if(index>=257 && index<=264){
                    recua=index-254;

                    //// LER CODIGO DA ARVORE HDIST


                   do{
                    if (availBits < needBits) {
                        //printf("A ler um byte...\n");
                        fread(&byte, 1, 1, gzFile);
                        availBits = 8;
                    }

                    rb = byte & 0x01; // guarda apenas o bit maissignificativo (o da direita) -------------------------------------------------->>> ATENÇÃO !!!! Aqui também é para ler da direita para a esquerda? Vamos descobrir

                    byte = byte >> 1; // discarda um bit já lido

                    //printf("symbol int: %d\n", rb);

                    symbol[k] = rb+ '0'; // vai guardando todos os bits lidos
                    printf("symbol[%d] = %c\n", k, symbol[k]);
                    i++;
                    k++;
                    availBits--;
                    // anda um bit para a frente a partir da root da árvore hLit
                    //index = nextNode(hLit_tree, rb);
                    //printf("andou um nó para a frente. teste = %d\n", index);
                    ///TESTE

                    indexDist=findNode(hDist_tree,symbol,0);
                       printf("<<Index de entrada %d\n",indexDist);
                       indexDist=bitsAddicionaisHDIST(indexDist);
                    printf("*******************************************INDEX HDIST->  %d\n",indexDist);

                   } while(indexDist<=0);








                }else if(index>=265 && index<=268){
                     recua=index-254+(index-265);
                     /// LER 1 BIT ADICIONAL
                    printf("=====RECUA %d + 1 bit adicional\n",recua);
                    if(availBits < 1) {
                        fread(&byte, 1, 1, gzFile);
                        rb = byte << availBits | rb;
                        availBits += 8;
                    }
                    for(int i=0; i<1; i++){
                        bitLido=(rb & 0x01);
                        rb = rb >> 1;
                        availBits -=1;
                       printf("Bit extra-> %d\n",bitLido);
                        if(bitLido==1) {

                            recua += pow(2.0, i);
                        }

                    }
                    //// LER CODIGO DA ARVORE HDIST



                    do{
                        if (availBits < needBits) {
                            //printf("A ler um byte...\n");
                            fread(&byte, 1, 1, gzFile);
                            availBits = 8;
                        }

                        rb = byte & 0x01; // guarda apenas o bit maissignificativo (o da direita) -------------------------------------------------->>> ATENÇÃO !!!! Aqui também é para ler da direita para a esquerda? Vamos descobrir

                        byte = byte >> 1; // discarda um bit já lido

                        //printf("symbol int: %d\n", rb);

                        symbol[k] = rb+ '0'; // vai guardando todos os bits lidos
                        printf("symbol[%d] = %c\n", k, symbol[k]);
                        i++;
                        k++;
                        availBits--;
                        // anda um bit para a frente a partir da root da árvore hLit
                        //index = nextNode(hLit_tree, rb);
                        //printf("andou um nó para a frente. teste = %d\n", index);
                        ///TESTE

                        indexDist=findNode(hDist_tree,symbol,0);
                        printf("<<Index de entrada %d\n",indexDist);
                        indexDist=bitsAddicionaisHDIST(indexDist);
                       printf("*******************************************=======INDEX HDIST->  %d\n",indexDist);

                    } while(indexDist<=0);


                }else if(index>=269 && index<=272){
                    recua=index-250+(index-269)*3;
                    //LER 2 BITS ADICIONAIS
                    printf("=====RECUA %d + 2 bits adicional\n",recua);
                    if(availBits < 1) {
                        fread(&byte, 1, 1, gzFile);
                        rb = byte << availBits | rb;
                        availBits += 8;
                    }
                    for(int i=0; i<2; i++){
                        bitLido=(rb & 0x01);
                        rb = rb >> 1;
                        availBits -=1;
                        printf("Bit extra-> %d\n",bitLido);
                        if(bitLido==1) {
                            //ca = '1';
                            recua += pow(2.0, i);
                        }
                    }
                    //// LER CODIGO DA ARVORE HDIST





                    do{
                        if (availBits < needBits) {
                            //printf("A ler um byte...\n");
                            fread(&byte, 1, 1, gzFile);
                            availBits = 8;
                        }

                        rb = byte & 0x01; // guarda apenas o bit maissignificativo (o da direita) -------------------------------------------------->>> ATENÇÃO !!!! Aqui também é para ler da direita para a esquerda? Vamos descobrir

                        byte = byte >> 1; // discarda um bit já lido

                        //printf("symbol int: %d\n", rb);

                        symbol[k] = rb+ '0'; // vai guardando todos os bits lidos
                        printf("symbol[%d] = %c\n", k, symbol[k]);
                        i++;
                        k++;
                        availBits--;
                        // anda um bit para a frente a partir da root da árvore hLit
                        //index = nextNode(hLit_tree, rb);
                        //printf("andou um nó para a frente. teste = %d\n", index);
                        ///TESTE

                       indexDist=findNode(hDist_tree,symbol,1);
                        printf("<<Index de entrada %d\n",indexDist);
                        indexDist=bitsAddicionaisHDIST(indexDist);
                        printf("*******************************************=======INDEX HDIST->  %d\n",indexDist);

                    } while(indexDist<0);





                } else if(index>=273 && index<=276){
                    recua=index-238+(index-273)*7;
                    //LER 3 BITS ADICIONAIS
                    printf("=====RECUA %d + 3 bits adicional\n",recua);
                    if(availBits < 3) {
                        fread(&byte, 1, 1, gzFile);
                        rb = byte << availBits | rb;
                        availBits += 8;
                    }
                    for(int i=0; i<3; i++){
                        bitLido=(rb & 0x01);
                        rb = rb >> 1;
                        availBits -=1;
                       printf("Bit extra-> %d\n",bitLido);
                        if(bitLido==1) {
                           // ca = '1';
                            recua += pow(2.0, i);
                        }

                    }
                    //// LER CODIGO DA ARVORE HDIST



                   do{
                        if (availBits < needBits) {
                            //printf("A ler um byte...\n");
                            fread(&byte, 1, 1, gzFile);
                            availBits = 8;
                        }

                        rb = byte & 0x01; // guarda apenas o bit maissignificativo (o da direita) -------------------------------------------------->>> ATENÇÃO !!!! Aqui também é para ler da direita para a esquerda? Vamos descobrir

                        byte = byte >> 1; // discarda um bit já lido

                        //printf("symbol int: %d\n", rb);

                        symbol[k] = rb+ '0'; // vai guardando todos os bits lidos
                        printf("symbol[%d] = %c\n", k, symbol[k]);
                        i++;
                        k++;
                        availBits--;
                        // anda um bit para a frente a partir da root da árvore hLit
                        //index = nextNode(hLit_tree, rb);
                        //printf("andou um nó para a frente. teste = %d\n", index);
                        ///TESTE

                        indexDist=findNode(hDist_tree,symbol,1);
                       printf("<<Index de entrada %d\n",indexDist);
                       indexDist=bitsAddicionaisHDIST(indexDist);
                        printf("*******************************************=======INDEX HDIST->  %d\n",indexDist);

                   } while(indexDist<0);

                }else if(index>=277 && index<=280){
                    recua=index-210+(index-277)*15;
                    //LER 4 BITS ADICIONAIS
                    printf("=====RECUA %d + 4 bits adicional\n",recua);
                    if(availBits < 1) {
                        fread(&byte, 1, 1, gzFile);
                        rb = byte << availBits | rb;
                        availBits += 8;
                    }
                    for(int i=0; i<4; i++){
                        bitLido=(rb & 0x01);
                        rb = rb >> 1;
                        availBits -=1;
                        printf("Bit extra-> %d\n",bitLido);
                        if(bitLido==1) {
                           // ca = '1';
                            recua += pow(2.0, i);
                        }


                    }
                    //// LER CODIGO DA ARVORE HDIST


                    do{
                        if (availBits < needBits) {
                            //printf("A ler um byte...\n");
                            fread(&byte, 1, 1, gzFile);
                            availBits = 8;
                        }

                        rb = byte & 0x01; // guarda apenas o bit maissignificativo (o da direita) -------------------------------------------------->>> ATENÇÃO !!!! Aqui também é para ler da direita para a esquerda? Vamos descobrir

                        byte = byte >> 1; // discarda um bit já lido

                        //printf("symbol int: %d\n", rb);

                        symbol[k] = rb+ '0'; // vai guardando todos os bits lidos
                        printf("symbol[%d] = %c\n", k, symbol[k]);
                        i++;
                        k++;
                        availBits--;
                        // anda um bit para a frente a partir da root da árvore hLit
                        //index = nextNode(hLit_tree, rb);
                        //printf("andou um nó para a frente. teste = %d\n", index);
                        ///TESTE

                        indexDist=findNode(hDist_tree,symbol,1);
                        printf("<<Index de entrada %d\n",indexDist);
                        indexDist=bitsAddicionaisHDIST(indexDist);
                        printf("*******************************************=======INDEX HDIST->  %d\n",indexDist);

                    } while(indexDist<0);


                }else if(index>=281 && index<=284){
                    recua=index-150+(index-281)*31;
                    //LER 5 BITS ADICIONAIS
                    printf("=====RECUA %d + 5 bits adicional\n",recua);
                    if(availBits < 1) {
                        fread(&byte, 1, 1, gzFile);
                        rb = byte << availBits | rb;
                        availBits += 8;
                    }
                    for(int i=0; i<5; i++){
                        bitLido=(rb & 0x01);
                        rb = rb >> 1;
                        availBits -=1;
                        printf("Bit extra-> %d\n",bitLido);
                        if(bitLido==1) {
                           // ca = '1';
                            recua += pow(2.0, i);
                        }


                    }
                    //// LER CODIGO DA ARVORE HDIST




                    do{
                        if (availBits < needBits) {
                            //printf("A ler um byte...\n");
                            fread(&byte, 1, 1, gzFile);
                            availBits = 8;
                        }

                        rb = byte & 0x01; // guarda apenas o bit maissignificativo (o da direita) -------------------------------------------------->>> ATENÇÃO !!!! Aqui também é para ler da direita para a esquerda? Vamos descobrir

                        byte = byte >> 1; // discarda um bit já lido

                        //printf("symbol int: %d\n", rb);

                        symbol[k] = rb+ '0'; // vai guardando todos os bits lidos
                        printf("symbol[%d] = %c\n", k, symbol[k]);
                        i++;
                        k++;
                        availBits--;
                        // anda um bit para a frente a partir da root da árvore hLit
                        //index = nextNode(hLit_tree, rb);
                        //printf("andou um nó para a frente. teste = %d\n", index);
                        ///TESTE

                        indexDist=findNode(hDist_tree,symbol,1);
                        printf("<<Index de entrada %d\n",indexDist);
                        indexDist=bitsAddicionaisHDIST(indexDist);
                       printf("*******************************************=======INDEX HDIST->  %d\n",indexDist);





                    } while(indexDist<0);


                }
                else if(index==285){
                    recua=258;
                    printf("=====RECUA %d + 0 bits adicional\n",recua);
                    //// LER CODIGO DA ARVORE HDIST


                    do{
                        if (availBits < needBits) {
                            //printf("A ler um byte...\n");
                            fread(&byte, 1, 1, gzFile);
                            availBits = 8;
                        }

                        rb = byte & 0x01; // guarda apenas o bit maissignificativo (o da direita) -------------------------------------------------->>> ATENÇÃO !!!! Aqui também é para ler da direita para a esquerda? Vamos descobrir

                        byte = byte >> 1; // discarda um bit já lido

                        //printf("symbol int: %d\n", rb);

                        symbol[k] = rb+ '0'; // vai guardando todos os bits lidos
                        printf("symbol[%d] = %c\n", k, symbol[k]);
                        i++;
                        k++;
                        availBits--;
                        // anda um bit para a frente a partir da root da árvore hLit
                        //index = nextNode(hLit_tree, rb);
                        //printf("andou um nó para a frente. teste = %d\n", index);
                        ///TESTE

                        indexDist=findNode(hDist_tree,symbol,1);
                        printf("<<Index de entrada %d\n",indexDist);
                        indexDist=bitsAddicionaisHDIST(indexDist);
                       printf("*******************************************=======INDEX HDIST->  %d\n",indexDist);


                    } while(indexDist<0);


                }

                    printf("=====>>>>>>>>>>>>RECUA FINAL %d \n",recua);







            }

            else if (index == -1) {
                printf("Este nó não existe\n");
                printf("STRING : %s",symbol);
                break;
            }

            else { //index == -2
                printf("(NODE)Continues searching \n");
                printf("STRING : %s\n",symbol);
                continue; // ainda nao se encontrou uma folha!
            }



        }while(index!=256);




        //actualizar numero de blocos analisados
        numBlocks++;
    } while(BFINAL == 0);

    //terminações
    fclose(gzFile);
    printf("End: %d bloco(s) analisado(s).\n", numBlocks);


    //teste da função bits2String: RETIRAR antes de criar o executável final
    char str[9];
    bits2String(str, 0x03);
    printf("%s\n", str);


    //RETIRAR antes de criar o executável final-
    system("PAUSE");
    return EXIT_SUCCESS;
} // ________________________________________________________________________________________________
int bitsAddicionaisHDIST(int index){
    int num=index;
    int bitLido;
    if(index>=0 && index<=3){
        num=index+1;


    }else if(index>=4 && index<=5){
        num=index+1+(index-4);
        // LER 1 BITS ADICIONAIS
        if(availBits < 1) {
            fread(&byte, 1, 1, gzFile);
            rb = byte << availBits | rb;
            availBits += 8;
        }
        for(int i=0; i<1; i++){
            bitLido=(rb & 0x01);
            rb = rb >> 1;
            availBits -=1;
            printf("<<Bit extra-> %d\n",bitLido);
            if(bitLido==1) {
                // ca = '1';
                num += pow(2.0, i);
            }


        }

    }else if(index>=6 && index<=7){
        num=index+3+(index-6)*3;
        // LER 2 BITS ADICIONAIS
        if(availBits < 1) {
            fread(&byte, 1, 1, gzFile);
            rb = byte << availBits | rb;
            availBits += 8;
        }
        for(int i=0; i<2; i++){
            bitLido=(rb & 0x01);
            rb = rb >> 1;
            availBits -=1;
            printf("<<Bit extra-> %d\n",bitLido);
            if(bitLido==1) {
                // ca = '1';
                num += pow(2.0, i);
            }


        }

    }else if(index>=8 && index<=9){
        num=index+9+(index-8)*7;
        // LER 3 BITS ADICIONAIS
        if(availBits < 1) {
            fread(&byte, 1, 1, gzFile);
            rb = byte << availBits | rb;
            availBits += 8;
        }
        for(int i=0; i<3; i++){
            bitLido=(rb & 0x01);
            rb = rb >> 1;
            availBits -=1;
            printf("<<Bit extra-> %d\n",bitLido);
            if(bitLido==1) {
                // ca = '1';
                num += pow(2.0, i);
            }


        }

    }else if(index>=10 && index<=11){
        num=index+23+(index-10)*15;
        // LER 4 BITS ADICIONAIS
        if(availBits < 1) {
            fread(&byte, 1, 1, gzFile);
            rb = byte << availBits | rb;
            availBits += 8;
        }
        for(int i=0; i<4; i++){
            bitLido=(rb & 0x01);
            rb = rb >> 1;
            availBits -=1;
            printf("<<Bit extra-> %d\n",bitLido);
            if(bitLido==1) {
                // ca = '1';
                num += pow(2.0, i);
            }


        }

    }else if(index>=12 && index<=13){
        num=index+53+(index-12)*31;
        // LER 5 BITS ADICIONAIS
        if(availBits < 1) {
            fread(&byte, 1, 1, gzFile);
            rb = byte << availBits | rb;
            availBits += 8;
        }
        for(int i=0; i<5; i++){
            bitLido=(rb & 0x01);
            rb = rb >> 1;
            availBits -=1;
            printf("<<Bit extra-> %d\n",bitLido);
            if(bitLido==1) {
                // ca = '1';
                num += pow(2.0, i);
            }


        }

    }else if(index>=14 && index<=15){
        num=index+115+(index-14)*62;
        // LER 6 BITS ADICIONAIS
        if(availBits < 1) {
            fread(&byte, 1, 1, gzFile);
            rb = byte << availBits | rb;
            availBits += 8;
        }
        for(int i=0; i<6; i++){
            bitLido=(rb & 0x01);
            rb = rb >> 1;
            availBits -=1;
            printf("<<Bit extra-> %d\n",bitLido);
            if(bitLido==1) {
                // ca = '1';
                num += pow(2.0, i);
            }


        }
    }else if(index>=16 && index<=17){
        num=index+241+(index-16)*127;
        // LER 7 BITS ADICIONAIS
        if(availBits < 1) {
            fread(&byte, 1, 1, gzFile);
            rb = byte << availBits | rb;
            availBits += 8;
        }
        for(int i=0; i<7; i++){
            bitLido=(rb & 0x01);
            rb = rb >> 1;
            availBits -=1;
            printf("<<Bit extra-> %d\n",bitLido);
            if(bitLido==1) {
                // ca = '1';
                num += pow(2.0, i);
            }


        }

    }else if(index>=18 && index<=19){
        num=index+495+(index-18)*255;
        // LER 8 BITS ADICIONAIS
        if(availBits < 1) {
            fread(&byte, 1, 1, gzFile);
            rb = byte << availBits | rb;
            availBits += 8;
        }
        for(int i=0; i<8; i++){
            bitLido=(rb & 0x01);
            rb = rb >> 1;
            availBits -=1;
            printf("<<Bit extra-> %d\n",bitLido);
            if(bitLido==1) {
                // ca = '1';
                num += pow(2.0, i);
            }


        }

    }else if(index>=20 && index<=21){
        num=index+1005+(index-20)*511;
        // LER 9 BITS ADICIONAIS
        if(availBits < 1) {
            fread(&byte, 1, 1, gzFile);
            rb = byte << availBits | rb;
            availBits += 8;
        }
        for(int i=0; i<9; i++){
            bitLido=(rb & 0x01);
            rb = rb >> 1;
            availBits -=1;
            printf("<<Bit extra-> %d\n",bitLido);
            if(bitLido==1) {
                // ca = '1';
                num += pow(2.0, i);
            }


        }

    }else if(index>=22 && index<=23){
        num=index+2027+(index-22)*1023;
        // LER 10 BITS ADICIONAIS
        if(availBits < 1) {
            fread(&byte, 1, 1, gzFile);
            rb = byte << availBits | rb;
            availBits += 8;
        }
        for(int i=0; i<10; i++){
            bitLido=(rb & 0x01);
            rb = rb >> 1;
            availBits -=1;
            printf("<<Bit extra-> %d\n",bitLido);
            if(bitLido==1) {
                // ca = '1';
                num += pow(2.0, i);
            }


        }

    }else if(index>=24 && index<=25){
        num=index+4073+(index-24)*2047;
        // LER 11 BITS ADICIONAIS
        if(availBits < 1) {
            fread(&byte, 1, 1, gzFile);
            rb = byte << availBits | rb;
            availBits += 8;
        }
        for(int i=0; i<11; i++){
            bitLido=(rb & 0x01);
            rb = rb >> 1;
            availBits -=1;
            printf("<<Bit extra-> %d\n",bitLido);
            if(bitLido==1) {
                // ca = '1';
                num += pow(2.0, i);
            }


        }

    }else if(index>=26 && index<=27){
        num=index+8167+(index-26)*4095;
        // LER 12 BITS ADICIONAIS
        if(availBits < 1) {
            fread(&byte, 1, 1, gzFile);
            rb = byte << availBits | rb;
            availBits += 8;
        }
        for(int i=0; i<12; i++){
            bitLido=(rb & 0x01);
            rb = rb >> 1;
            availBits -=1;
            printf("<<Bit extra-> %d\n",bitLido);
            if(bitLido==1) {
                // ca = '1';
                num += pow(2.0, i);
            }


        }

    }else if(index>=28 && index<=29){
        num=index+16357+(index-28)*8191;
        // LER 12 BITS ADICIONAIS
        if(availBits < 1) {
            fread(&byte, 1, 1, gzFile);
            rb = byte << availBits | rb;
            availBits += 8;
        }
        for(int i=0; i<12; i++){
            bitLido=(rb & 0x01);
            rb = rb >> 1;
            availBits -=1;
            printf("<<Bit extra-> %d\n",bitLido);
            if(bitLido==1) {
                // ca = '1';
                num += pow(2.0, i);
            }


        }

    }
    return num;
}

int getNumberOfCodes(int necessaryBits, int exp){
    int code = 0;
    while (availBits < necessaryBits){
        fread(&byte, 1, 1, gzFile);
        rb = byte << availBits | rb;
        availBits += 8;
    }


    code = rb & exp; //retirar últimos len(exp) bits
    rb = rb >> necessaryBits;
    availBits -= necessaryBits;

    return code;
}


// armazena num array os comprimentos dos codigos do "alfabeto de comprimentos de codigos"
void lengthLengthAlfa(){

    int sequence [] = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
    int length = 0;
    int codeLength []={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

    hcLen+=4;

    printf("Comprimento dos codigos do 'alfabeto de comprimentos de codigos':\n\n");

    for(int i = 0 ;i < hcLen ; i++){
        length = getNumberOfCodes(3,0x07); //0x07- 3 bits menos significativos
        codeLength[sequence[i]] = length;
        printf("index: %d -> comprimento: %d\n",sequence[i], codeLength[sequence[i]]);
    }

    int n_codes = sizeof(codeLength) / sizeof(int);

    // gets the codes for the alphabet of code lengths
    getHuffmanCodes(codeLength, n_codes, HCLen_tree);
}


// gets the codes for each symbol
// lengths is an array with the lenghts for each symbol in the tree
// n_codes is the size of lengths
void getHuffmanCodes(int lengths [], int n_codes, HuffmanTree* tree) {

    int *codes = (int*)malloc(sizeof(int)*n_codes);

    // initializes all array values to 0
    for (int i=0; i<n_codes; i++) {
        codes[i] = 0;
    }

    int maxBits=0;

    for (int i=0; i<n_codes; i++){
        if(maxBits<=lengths[i]){
            printf("        LENGHTS-> %d\n",lengths[i]);
            maxBits=lengths[i];}
    }
    printf("MaxBits= %d\n", maxBits);

    char bl_count[maxBits+1];

    // gets the number of codes of each code length
    for (int i=1; i<=maxBits; i++) {
        int count=0;

        for (int j=0; j<n_codes; j++) {
            if (lengths[j] == i)
                count++;
        }

        bl_count[i] = count;
        printf("bl_count[%d] = %d\n", i, bl_count[i]);
    }

    int code = 0;

    bl_count[0] = 0; // bl_count[maxBits+1]

    int firstCode[maxBits];

    // calculates the first code for each code length
    for (int bits=1; bits<=maxBits; bits++) {
        code = (code + bl_count[bits-1]) << 1; //aplicar a formula
        firstCode[bits] = code; // primeiro codigo de cada comprimento
        printf("firstCode[%d] = %d\n", bits, firstCode[bits]);
    }


    // gets the codes for each symbol starting from the firstCode
    for (int i=1; i<=maxBits; i++) {
        int n = firstCode[i];
        for (int j = 0; j < n_codes; j++) {
            if(lengths[j]==i){
                codes[j] = n;
                n++;
            }
        }
    }

    for(int i=0; i<n_codes; i++)
        printf("codes[%d]= %d\n", i, codes[i]);

    char binario [n_codes];

    for (int i=0; i<n_codes; i++){
        if(lengths[i]>0){
            printf("LENGHTS-> %d\n",lengths[i]);
            char s [lengths[i]];
            int temp=codes[i];
            int bin;
            printf("%d -> codigo %d: ",i, codes[i]);
            for(int j=0; j<lengths[i];j++) {
                bin = temp % 2;
                temp = temp / 2;

                if (bin == 1) {
                    s[lengths[i]-1 - j] = '1';

                }
                else {
                    s[lengths[i]-1 - j] = '0';
                }
            }
            s[lengths[i]]='\0';
            printf("%s\n", s);
            addNode(tree,s,i,1);

        }

    }
}


//gets the lengths of the codes
void checkaNaArvore(int *lengths, int size){

    int unsigned bitLido;
    int resultado;
    int resultado_ant;
    int index=0;

    while(true) {
        if (index >= size){
            break;
        }
        if(availBits < 1) {
            fread(&byte, 1, 1, gzFile);

            rb = byte << availBits | rb;
            availBits += 8;
        }

        bitLido=(rb & 0x01);
        //printf("\nbitlido=%d",bitLido);
        rb = rb >> 1;
        availBits -=1;
        //printf("BITS-> %d\n",availBits);
        char ca;
        if(bitLido==1)
            ca='1';
        else
            ca='0';

        resultado=nextNode(HCLen_tree, ca);

        if(resultado==-2){
            continue;
        }

        else if(resultado==-1){
            printf("deu bosta");
            break;
        }

        else{
            int acum;
            if(resultado!=16)
                resultado_ant=resultado;
            //printf("\nresultado=%d",resultado);
            if(resultado==16){
                acum=3;
                //printf("\nresultado anterior: %d",resultado_ant);
                if(availBits < 2) {
                    fread(&byte, 1, 1, gzFile);
                    rb = byte << availBits | rb;
                    availBits += 8;
                }
                for(int i=0; i<2; i++){
                    bitLido=(rb & 0x01);
                    rb = rb >> 1;
                    availBits -=1;
                    if(bitLido==1) {
                        ca = '1';
                        acum+=pow(2.0,i);//
                    }
                    else
                        ca='0';
                    //printf("\ndepois do 16: %c",ca);
                }
                //printf("\nRepete o 16 %d vezes",acum);
                for(int i=0; i<acum; i++){
                    //printf("\n%d",index);
                    lengths[index]=resultado_ant;
                    index++;

                }
            }
            else if(resultado==17){
                acum=3;
                if(availBits < 3) {
                    fread(&byte, 1, 1, gzFile);
                    rb = byte << availBits | rb;
                    availBits += 8;
                }
                for(int i=0; i<3; i++){
                    bitLido=(rb & 0x01);
                    rb = rb >> 1;
                    availBits -=1;
                    printf("BITS-> %d\n",availBits);
                    if(bitLido==1) {
                        ca = '1';
                        acum += pow(2.0, i);
                    }
                    else
                        ca='0';
                    //printf("\ndepois do 17: %c",ca);
                }
                //printf("\nRepete o 17 %d vezes",acum);
                for(int i=0; i<acum; i++){
                    //printf("\n%d",index);
                    lengths[index]=0;
                    index++;

                }
            }
            else if(resultado==18){
                acum=11;
                if(availBits < 7) {
                    fread(&byte, 1, 1, gzFile);
                    rb = byte << availBits | rb;
                    availBits += 8;
                }
                for(int i=0; i<7; i++){
                    bitLido=(rb & 0x01);
                    rb = rb >> 1;
                    availBits -=1;
                    printf("BITS-> %d\n",availBits);
                    if(bitLido==1) {
                        ca = '1';
                        acum += pow(2.0, i);
                    }
                    else
                        ca='0';
                    //printf("\ndepois do 18: %c",ca);
                }
                //printf("\nRepete o 18 %d vezes",acum);
                for(int i=0; i<acum; i++){
                    //printf("\n%d",index);
                    lengths[index]=0;
                    index++;

                }
            }
            else {
                //printf("\n%d",index);
                lengths[index] = resultado;
                index++;
            }
        }
    }
}



int isDynamicHuffman(unsigned char rb)
{
    unsigned char BTYPE = rb & 0x03;

    if (BTYPE == 0) //--> sem compress�o
    {
        printf("Ignorando bloco: sem compactacao!!!\n");
        return 0;
    }
    else if (BTYPE == 1)
    {
        printf("Ignorando bloco: compactado com Huffman fixo!!!\n");
        return 0;
    }
    else if (BTYPE == 3)
    {
        printf("Ignorando bloco: BTYPE = reservado!!!\n");
        return 0;
    }
    else
        return 1;
}

//Le o cabecalho do ficheiro gzip: devolve erro (-1) se o formato for inválido, ou devolve 0 se ok
int getHeader(FILE *gzFile, gzipHeader *gzh) //obtem cabecalho
{
    unsigned char byte;

    //Identificacao 1 e 2: valores fixos
    fread(&byte, 1, 1, gzFile);
    (*gzh).ID1 = byte;
    if ((*gzh).ID1 != 0x1f) return -1; //erro no cabecalho

    fread(&byte, 1, 1, gzFile);
    (*gzh).ID2 = byte;
    if ((*gzh).ID2 != 0x8b) return -1; //erro no cabe�alho

    //Método de compress�o (deve ser 8 para denotar o deflate)
    fread(&byte, 1, 1, gzFile);
    (*gzh).CM = byte;
    if ((*gzh).CM != 0x08) return -1; //erro no cabe�alho

    //Flags
    fread(&byte, 1, 1, gzFile);
    unsigned char FLG = byte;

    //MTIME
    char lenMTIME = 4;
    fread(&byte, 1, 1, gzFile);
    (*gzh).MTIME = byte;
    for (int i = 1; i <= lenMTIME - 1; i++)
    {
        fread(&byte, 1, 1, gzFile);
        (*gzh).MTIME = (byte << 8) + (*gzh).MTIME;
    }

    //XFL (not processed...)
    fread(&byte, 1, 1, gzFile);
    (*gzh).XFL = byte;

    //OS (not processed...)
    fread(&byte, 1, 1, gzFile);
    (*gzh).OS = byte;

    //--- Check Flags
    (*gzh).FLG_FTEXT = (char)(FLG & 0x01);
    (*gzh).FLG_FHCRC = (char)((FLG & 0x02) >> 1);
    (*gzh).FLG_FEXTRA = (char)((FLG & 0x04) >> 2);
    (*gzh).FLG_FNAME = (char)((FLG & 0x08) >> 3);
    (*gzh).FLG_FCOMMENT = (char)((FLG & 0x10) >> 4);

    //FLG_EXTRA
    if ((*gzh).FLG_FEXTRA == 1)
    {
        //ler 2 bytes XLEN + XLEN bytes de extra field
        //1� byte: LSB, 2�: MSB
        char lenXLEN = 2;

        fread(&byte, 1, 1, gzFile);
        (*gzh).xlen = byte;
        fread(&byte, 1, 1, gzFile);
        (*gzh).xlen = (byte << 8) + (*gzh).xlen;

        (*gzh).extraField = new unsigned char[(*gzh).xlen];

        //ler extra field (deixado como est�, i.e., n�o processado...)
        for (int i = 0; i <= (*gzh).xlen - 1; i++)
        {
            fread(&byte, 1, 1, gzFile);
            (*gzh).extraField[i] = byte;
        }
    }
    else
    {
        (*gzh).xlen = 0;
        (*gzh).extraField = 0;
    }

    //FLG_FNAME: ler nome original
    if ((*gzh).FLG_FNAME == 1)
    {
        (*gzh).fName = new char[1024];
        unsigned int i = 0;
        do
        {
            fread(&byte, 1, 1, gzFile);
            if (i <= 1023)  //guarda no m�ximo 1024 caracteres no array
                (*gzh).fName[i] = byte;
            i++;
        }while(byte != 0);
        if (i > 1023)
            (*gzh).fName[1023] = 0;  //apesar de nome incompleto, garantir que o array termina em 0
    }
    else
        (*gzh).fName = 0;

    //FLG_FCOMMENT: ler coment�rio
    if ((*gzh).FLG_FCOMMENT == 1)
    {
        (*gzh).fComment = new char[1024];
        unsigned int i = 0;
        do
        {
            fread(&byte, 1, 1, gzFile);
            if (i <= 1023)  //guarda no m�ximo 1024 caracteres no array
                (*gzh).fComment[i] = byte;
            i++;
        }while(byte != 0);
        if (i > 1023)
            (*gzh).fComment[1023] = 0;  //apesar de coment�rio incompleto, garantir que o array termina em 0
    }
    else
        (*gzh).fComment = 0;


    //FLG_FHCRC (not processed...)
    if ((*gzh).FLG_FHCRC == 1)
    {
        (*gzh).HCRC = new unsigned char[2];
        fread(&byte, 1, 1, gzFile);
        (*gzh).HCRC[0] = byte;
        fread(&byte, 1, 1, gzFile);
        (*gzh).HCRC[1] = byte;
    }
    else
        (*gzh).HCRC = 0;

    return 0;
}

long getOrigFileSize(FILE * gzFile)
{
    //salvaguarda posi��o actual do ficheiro
    long fp = ftell(gzFile);

    //�ltimos 4 bytes = ISIZE;
    fseek(gzFile, -4, SEEK_END);

    //determina ISIZE (s� correcto se cabe em 32 bits)
    unsigned long sz = 0;
    unsigned char byte;
    fread(&byte, 1, 1, gzFile);
    sz = byte;
    for (int i = 0; i <= 2; i++)
    {
        fread(&byte, 1, 1, gzFile);
        sz = (byte << 8*(i+1)) + sz;
    }


    //restaura file pointer
    fseek(gzFile, fp, SEEK_SET);

    return sz;
}
void bits2String(char *strBits, unsigned char byte)
{
    char mask = 0x01;  //get LSbit

    strBits[8] = 0;
    for (char bit, i = 7; i >= 0; i--)
    {
        bit = byte & mask;
        strBits[i] = bit +48; //converter valor numérico para o caracter alfanumérico correspondente
        byte = byte >> 1;
    }
}


unsigned int_to_int(unsigned k) {
    if (k == 0) return 0;
    if (k == 1) return 1;                       /* optional */
    return (k % 2) + 10 * int_to_int(k / 2);
}