huf.c

huffman compresssion source code,it would be useful for sb.

        avg_bits_per_symbol += ((double)bits_per_char) * frac;

    }
#ifdef VERBOSE
    printf("\n\nTotal........ %%%6.3f\n", check_total);
    printf("Average bits per symbol = %6.3f\n",avg_bits_per_symbol);
    printf("Total compressed file length w/o decode table = %f\n",
        avg_bits_per_symbol * (double)total / ((double) 8)
    );
#endif

}

/*********************
 * called by qsort() *
 *********************/

int compare(const void *arg1, const void *arg2)
{

    long result = (
                    (
                       *(struct chardata **)arg1

                    )->total
                  )

                  -

                  (
                    (
                        *(struct chardata **)arg2
                    )->total
                  );

    /* return codes reveresed from normal for descending order */

    if (result > 0L) return -1;  /* first > second */
    if (result < 0L) return +1;  /* first < second */
    return 0;                    /* first = second */
}


/***************************************************************************
 * floating point, backwards trees, dynamic memory allocation,             *
 * and now recursion -- this program has it all!                           *
 *                                                                         *
 * func builds bit sequences at stuffs associated sequence and length into *
 * corresponding leaf node                                                 *
 *                                                                         *
 * Pretty obvious code, if you know recursion.                             *
 *                                                                         *
 ***************************************************************************/


short seq_len=0;


void gen_bit_sequences(struct chardata *node)
{
    unsigned short asctobin(char *bit_seq);

    static char bit_sequence[16];    /* where to build the huffman bit sequence */
    double frac;

    if (node->left != NULL)
    {
        bit_sequence[seq_len++]='1';
        gen_bit_sequences(node->left);
        seq_len--;
    }

    if (node->right != NULL)
    {
        bit_sequence[seq_len++]='0';
        gen_bit_sequences(node->right);
        seq_len--;
    }

    if (node->right != NULL)    /* we are at an interior node going back up */
        return;

    bit_sequence[seq_len] = 0;

    node->seq_length = (long)seq_len;
    node->bit_sequence = asctobin(bit_sequence);

#ifdef VERBOSE
    printf("%3d == %16s == %4x %3d\n", node->charnum, bit_sequence, node->bit_sequence, seq_len);
#endif

    frac = (((double)huftable[node->charnum]->total))/(double)total;
    avg_bits_per_symbol += ((double)seq_len) * frac;
    real_bits_total += (long)seq_len;

    
}

/*********************************************
 * turn an ASCII representation of a binary  *
 * number into an unsigned short.            *
 *********************************************/

unsigned short asctobin(char *bit_seq)
{
    register short i;
    register unsigned short binary_value=0;

    for (i = 0; (i < 16) && (bit_seq[i]); i++)
    {
        binary_value <<= 1;
        binary_value |= (bit_seq[i]=='1') ? 1 : 0;
    }

    return binary_value;
}

/************************************************************
 * build a decode table (an array) from the big fat hairy   *
 * tree structure we created earlier.  the decode table is  *
 * parsed just like the tree, only instead of pointers to   *
 * other nodes, there are left and right array indecies.    *
 * This was done because the destination system for my      *
 * application had no dynamic memory allocation.  Also      *
 * I didn't want to try writing a tree to disk, ick.        *
 ************************************************************/

short create_decode_table(void)
{
    void assign_index(struct chardata *node);
    void fill_array(struct chardata *node);

    assign_index(root);     /* assign index nums to each node in tree -- use member 'total' for */
                            /* this purpose, since it isn't needed anymore.                     */

    /* allocate space for array dynamically, since we don't know */
    /* how big it is going to be.  (will be small if there are   */
    /* only a few different characters that are used repeatedly  */
    /* in the file to be encoded.                                */

    decode_table = (struct decode_table_element *) calloc(array_max_index + 1,
        sizeof(struct decode_table_element));

    if (decode_table == NULL)
        return FALSE;

    fill_array(root);   /* fill up the table */
    return TRUE;
}

/***************************************************************************
 * assign all nodes index numbers.  uses preorder traversal to ensure that *
 * the root is assigned 0, which will be the 'root' of the array --        *
 * where the searching starts when decoding.                               *
 * sets value of global, "array_max_index"                                 *
 ***************************************************************************/

void assign_index(struct chardata *node)
{
    if (node != NULL)
    {
         node->total = (long)array_max_index++;
         assign_index(node->left);
         assign_index(node->right);
    }
}


/*************************************************
 * fill up the decode table                      *
 * use preorder traversal (see above for reason) *
 *************************************************/

short temp_index = 0;

void fill_array(struct chardata *node)
{
    if (node != NULL)
    {
        if (node->left == NULL)     /* we found a leaf */
        {
            decode_table[temp_index].letter = node->charnum;
            decode_table[temp_index].left   = 0;
            decode_table[temp_index].right  = 0;
        }
        else    /* we are at an interior node */
        {
            decode_table[temp_index].letter = '@';  /* if you get a lot of '@' in your decoded */
                                                    /* file you are looking at interior nodes, */
                                                    /* not leaves.                             */

            decode_table[temp_index].left   = (short) node->left->total;
            decode_table[temp_index].right  = (short) node->right->total;
        }

        temp_index++;

        fill_array(node->left);
        fill_array(node->right);
    }
}

/***********************
 * perform compression *
 ***********************/

short compress(void)
{
    short output_bits(short bit_seq, short seq_len); /* prototype */
    short find_match(int c);                         /* prototype */

    register unsigned long i;        /* index variable         */
    register short array_index;      /* index to info for char */
    int c;                           /* a character            */

    char orig_name[MAXFILE+MAXEXT],  /* original filename      */
         drive[MAXDRIVE],            /* needed for fnsplit()   */
         dir[MAXDIR],                /* needed for fnsplit()   */
         filename[MAXFILE],          /* 8 chars, orig name     */
         ext[MAXEXT];                /* 3 chars, orig ext      */

    if ((infile=fopen(infile_name, "rb")) == NULL)
    {
        printf("Unable to open %s\n", infile_name);
        return 1;
    }

    if ((outfile=fopen(outfile_name, "wb")) == NULL)
    {
        printf("Unable to open %s\n", outfile_name);
        return 1;
    }

    fnsplit(infile_name, drive, dir, filename, ext);    /* get filename               */
    strcpy(orig_name, filename);
    strcat(orig_name, ext);
    for (i=0; i<13; i++)                                /* write orig filename        */
        fputc(orig_name[i], outfile);                   /* to file one char at a time */

                                                        /* write # of array elems     */
    if (
         fwrite((void*)&array_max_index, sizeof(short), 1, outfile)
         < 1
       )
    {
        printf("Unable to write to %s -- out of disk space?", outfile_name);
        fclose(outfile);
        return 1;
    }
                                                        /* write original length      */
    if (
         fwrite((void*)&total, sizeof(unsigned long), 1, outfile)
         < 1
       )
    {
        printf("Unable to write to %s -- out of disk space?", outfile_name);
        fclose(outfile);
        return 1;
    }
                                                        /* write decode table         */
    if (
         fwrite((void*)decode_table, sizeof(struct decode_table_element), array_max_index + 1, outfile)
         < array_max_index
       )
    {
        printf("Unable to write to %s -- out of disk space?", outfile_name);
        fclose(outfile);
        return 1;
    }


    printf("Encoding %ld bytes.\n",total);

    for (i=0; i< total; i++)            /* for all bytes                       */
    {
        c = fgetc(infile);              /* get a new byte                      */
        if (c == EOF)
        {
            printf("\nReached unexpected end of input file at position %ld.\n",i);
            return 1;
        }
        array_index = find_match(c);    /* find it in the decode table         */

        if (                            /* write out the bit sequence          */
             output_bits(huftable[array_index]->bit_sequence, (short)huftable[array_index]->seq_length)
             != 0
           )
        {
            printf("Unable to write to %s -- out of disk space?", outfile_name);
            return 1;
        }
    }

    output_bits(255,7);                 /* flush last partial char from buffer */

    printf("%ld bytes encoded.\n", i);

    fclose(outfile);


    return 0;
}

/***************************************
 * return array index that corresponds *
 * to a particular character           *
 ***************************************/

short find_match(int c)
{
    register short i=0;

    while (c != huftable[i]->charnum)
        ++i;

    return i;
}

/************************************
 * write out a bit sequence to disk *
 ************************************/

short output_bits(short bit_seq, short seq_len)
{
    static unsigned char buffer = 0;
    static unsigned short bits_used   = 0;
    short i;

    bit_seq <<= (16 - seq_len);         /* bring 1st real bit to leftmost position */

    for (i = 0; i < seq_len; i++)
    {
        buffer <<= 1;                        /* make space for next bit in buffer                      */
        buffer |= ((bit_seq & 0x8000) != 0); /* set rightmost bit of buffer to lefmost bit in sequence */
        bit_seq <<= 1;                       /* throw away used bit from sequence                      */
        bits_used++;                         /* increment bit count                                    */
        if (bits_used == 8)                  /* if we have a whole byte, write it.                     */
        {
            if (fputc((int)buffer, outfile)==EOF)
            {
                fclose(outfile);
                return 1;
            }

            bits_used = 0;  /* start fresh for new byte                       */
            buffer    = 0;  /* may not be necessary except on final bits/byte */
        }
    }

    return 0;
}


#ifdef VERBOSE

void show_encode_info(void)
{
    register short i;

    for (i=0; i<256; i++)
        printf("%3d.  charnum =%3d  index == %ld  seq_len =%d, bit_seq = %x\n", i, huftable[i]->charnum,
            huftable[i]->total, huftable[i]->seq_length, huftable[i]->bit_sequence);
}

/******

 Datafile:  All 16/32 bit quantities in Intel format


 13 bytes    : original filename (8.3 + "\0")
 16 bits     : number of array elements needed, N (N == 511 means 512 array
               elements -> 0..511)
 32 bits     : size of uncompressed original data in bytes
 N * 6 bytes : Array elements in order 0 .. N
               struct decode_table_element {
                    char letter;      8 bits
                    char spare;       8 bits
                    short left;      16 bits
                    short right;     16 bits
                }
<?>           : compressed data, effectively a bit stream

 ******/

void show_encoded_file_size(void)
{
    register unsigned short i;
    double bit_total=0;

    for (i = 0; i < 256; i++)
        bit_total += (double)huftable[i]->total
                    *(double)huftable[i]->seq_length;

    printf("Best guess at encoded file size is %f bytes.\n", bit_total / (double) 8);


}

void show_decode_table(void)
{
    register unsigned short i;

    for (i=0; i<array_max_index+1; i++)
        printf("[%3d]  %3x  L: %3d  R: %3d\n", i, (int)decode_table[i].letter,
            decode_table[i].left, decode_table[i].right);
}
#endif