compgif.c File Reference

#include "rle_config.h"
#include <stdio.h>
#include "rletogif.h"

Include dependency graph for compgif.c:

Go to the source code of this file.

Data Structures
struct	str_table_entry
struct	str_table_node

Macros
#define	MAXIMUMCODE   4095 /* 2**maximum_code_size */
#define	BLOCKSIZE   256 /* max block byte count + 1 */
#define	NULLPREFIX   -1

Typedefs
typedef struct str_table_entry	strTableEntry
typedef struct str_table_node	strTableNode
typedef struct str_table_node *	strTableNodePtr
typedef struct str_table_node **	strTable

Functions
int	pack_bits ()
int	compgif (int code_size, FILE *os, ifunptr infun)
int	pack_bits (int compress_size, int prefix, FILE *os)

Macro Definition Documentation

#define BLOCKSIZE   256 /* max block byte count + 1 */

Definition at line 40 of file compgif.c.

#define MAXIMUMCODE   4095 /* 2**maximum_code_size */

Definition at line 39 of file compgif.c.

#define NULLPREFIX   -1

Definition at line 41 of file compgif.c.

Typedef Documentation

typedef struct str_table_node ** strTable

typedef struct str_table_entry strTableEntry

typedef struct str_table_node strTableNode

typedef struct str_table_node * strTableNodePtr

Function Documentation

int compgif	(	int	code_size,
		FILE*	os,
		ifunptr	infun
	)

Definition at line 70 of file compgif.c.

{
    strTable heap; /* our very own memory manager */
    int heap_index;
    int clear_code, end_code, cur_code;
    int i, found, num_colors, prefix, compress_size;
    int cur_char, end_of_data, bits_per_pix;
    strTableNodePtr cur_node;
    strTable root;    /* root of string table for LZW compression */
                                 /* is an array of 2**bits_per_pix pointers
                    to atomic nodes */
    heap_index = 0;
    heap = (strTable)malloc(sizeof(strTableNodePtr)*MAXIMUMCODE);
    if (heap == NULL) error("can't allocate heap");
    for (i=0; i < MAXIMUMCODE; i++) {
    heap[i] = (strTableNodePtr)malloc(sizeof(strTableNode));
        if (heap[i] == NULL) error("can't allocate heap");
    }
    bits_per_pix = code_size - 1;
    compress_size = code_size;
    num_colors = 1<<(bits_per_pix);
    clear_code = num_colors;
    end_code = clear_code + 1;
    cur_code = end_code + 1;
    prefix = NULLPREFIX;
    root = (strTable)malloc(sizeof(strTableNodePtr)*num_colors);
    if (!root) error("memory allocation failure (root)");
    for(i=0; i<num_colors; i++) {
    root[i] = heap[heap_index++];
        root[i]->entry.code = i;
        root[i]->entry.prefix = NULLPREFIX;
        root[i]->entry.suffix = i;
    root[i]->left = NULL;
    root[i]->right = NULL;
        root[i]->children = NULL;
    }
    /* initialize  output block */
    pack_bits(compress_size, -1, os);
    pack_bits(compress_size, clear_code, os);
    end_of_data = 0;
    if((cur_char = GIFNextPixel(infun)) == EOF) error("premature end of data");
    while (!end_of_data) {
        prefix = cur_char;
        cur_node = root[prefix];
        found = 1;
        if((cur_char = GIFNextPixel(infun)) == EOF) {
            end_of_data = 1; break;
        }
        while(cur_node->children && found) {
            cur_node = cur_node->children;
            while(cur_node->entry.suffix != cur_char) {
                if (cur_char < cur_node->entry.suffix) {
                    if (cur_node->left) cur_node = cur_node->left;
                    else {
                        cur_node->left = heap[heap_index++];
                        cur_node = cur_node->left;
                        found = 0; break;
                    }
                }
                else {
                    if (cur_node->right) cur_node = cur_node->right;
                    else {
                        cur_node->right = heap[heap_index++];
                        cur_node = cur_node->right;
                        found = 0; break;
                    }
                }
            }
            if (found) {
                prefix = cur_node->entry.code;
                if((cur_char = GIFNextPixel(infun)) == EOF) {
                    end_of_data = 1; break;
                }
            }
        }
        if (end_of_data) break;
        if (found) {
            cur_node->children = heap[heap_index++];
            cur_node = cur_node->children;
        }
        cur_node->children = NULL;
        cur_node->left = NULL;
        cur_node->right = NULL;
        cur_node->entry.code = cur_code;
        cur_node->entry.prefix = prefix;
        cur_node->entry.suffix = cur_char;
        pack_bits(compress_size, prefix, os);
        if (cur_code > ((1<<(compress_size))-1))
            compress_size++;
        if (cur_code < MAXIMUMCODE) {
            cur_code++;
        }
        else {
            heap_index = num_colors;  /* reinitialize string table */
            for (i=0; i < num_colors; i++ ) root[i]->children = NULL;
            pack_bits(compress_size, clear_code, os);
            compress_size = bits_per_pix + 1;
            cur_code = end_code + 1;
        }
    }
    pack_bits(compress_size, prefix, os);
    pack_bits(compress_size, end_code, os);
    pack_bits(compress_size, -1, os);
    for (i=0; i < MAXIMUMCODE; i++) free(heap[i]);
    free(heap);
    free(root);
    return (1);
}

int pack_bits

(

)

int pack_bits	(	int	compress_size,
		int	prefix,
		FILE*	os
	)

Definition at line 192 of file compgif.c.

{
    static int cur_bit = 8;
    static unsigned char block[BLOCKSIZE] = { 0 };
    int i, left_over_bits;

    /* if we are about to excede the bounds of block or if the flush
       code (code_bis < 0) we output the block */
    if((cur_bit + compress_size > (BLOCKSIZE-1)*8) || (prefix < 0)) {
        /* handle case of data overlapping blocks */
        if ((left_over_bits = (((cur_bit>>3) +
                ((cur_bit & 7) != 0))<<3) - cur_bit) != 0) {
            for (i=0; i < left_over_bits; i++) {
                if(prefix & (1<<i)) block[cur_bit>>3] |= (char)(1<<(cur_bit & 7));
                /* note n>>3 == n/8 and n & 7 == n % 8 */
                cur_bit++;
            }
        }
        compress_size -= left_over_bits;
        prefix = prefix>>left_over_bits;
        block[0] =  (unsigned char)((cur_bit>>3) - 1);
        if (block[0]) fwrite(block,1,block[0]+1,os);
        for(i=0; i < BLOCKSIZE; i++) block[i] = 0;
        cur_bit = 8;
    }
    if (prefix >= 0) {
        for (i=0; i < compress_size; i++) {
        if(prefix & (1<<i)) block[cur_bit>>3] |=
        (unsigned char)(1<<(cur_bit & 7));
            /* note n>>3 == n/8 and n & 7 == n % 8 */
            cur_bit++;
        }
    }
    return (1);
}