GIF Encoding Source Code
256-level grayscale (non-interlaced)
The following (C) source code translates a pixelated 256-level grayscale image
into a GIF image file. For information about GIF format or LZW compression,
look here.
The format of the pixel source file is (in ASCII):
- number of rows
- number of columns
- space-delineated pixels in 1st row (here "space" means space or tab)
- space-delineated pixels in 2nd row
- ...
- space-delineated pixels in last row
The string table is stored in a "b-tree on steroids," or more specifically,
a 256-tree. Each (non-NULL) node contains the string table index (or code)
and 256 pointers to other nodes. For example, the index associated with
the string 0-3-173-25 would be stored in:
first->node[0]->node[3]->node[173]->node[25]->code
Michael A. Mayer /
mayer@aol.com
#include <stdio.h>
#define BLOKLEN 255
#define BUFLEN 1000
typedef struct _tn {
int code;
struct _tn **node;
} TreeNode,*TreePtr;
char *AddCodeToBuffer(int code,short n,char *buf);
TreePtr InitIndices(TreePtr first,int cc);
TreePtr AddNode(int,int);
int SearchTreeForCode(TreePtr,int *,int,int,int,int);
void ClearTree(TreePtr,int);
main(int argc,char **argv)
{
int i,j,rows,cols,depth=8;
int *pixels;
TreePtr first = NULL;
int len,*str,*end,*target;
int cc,eoi,code,next;
short nBits;
char *pos,*buffer;
char cmd[100],filename[100];
FILE *src,*dst;
buffer = (char *)malloc((BUFLEN+1)*sizeof(char))+1;
if(argc!=2) {
printf("\nUsage:: %s pixelfile\n\n",argv[0]);
exit(1);
}
src = fopen(argv[1],"r");
if(!src) {
printf("\nError:: Couldn't open %s\n",argv[1]);
exit(1);
}
strcpy(filename,argv[1]);
strcat(filename,".gif");
dst = fopen(filename,"r");
if(dst) {
fclose(dst);
printf("\nSorry:: %s will not overwrite %s\n\n",argv[0],filename);
exit(1);
}
dst = fopen(filename,"w");
if(fscanf(src,"%d %d",&rows,&cols)!=2) {
fclose(dst);fclose(src);
printf("\nError:: %s is apparently not a pixel file\n\n",argv[1]);
sprintf(cmd,"rm %s",filename);
system(cmd);
exit(1);
}
pixels = (int *)malloc(rows*cols*sizeof(int));
for(i=0;i<rows;i++) {
for(j=0;j<cols;j++) {
if(fscanf(src,"%d",pixels+cols*i+j)!=1) {
fclose(dst);fclose(src);
printf("\nError:: %s is apparently not a pixel file\n\n",argv[1]);
sprintf(cmd,"rm %s",filename);
system(cmd);
exit(1);
}
}
}
fclose(src);
pos = buffer;
*pos++ = 'G';
*pos++ = 'I';
*pos++ = 'F';
*pos++ = '8';
*pos++ = '7';
*pos++ = 'a';
*pos++ = 0xff & cols;
*pos++ = (0xff00 & cols)/0x100;
*pos++ = 0xff & rows;
*pos++ = (0xff00 & rows)/0x100;
*pos++ = 0xf0 | (0x7&(depth-1));
*pos++ = 0xff;
*pos++ = 0x0;
for(i=0;i<256;i++) {
*pos++ = 0xff & i;
*pos++ = 0xff & i;
*pos++ = 0xff & i;
}
*pos++ = 0x2c;
*pos++ = 0x00;
*pos++ = 0x00;
*pos++ = 0x00;
*pos++ = 0x00;
*pos++ = 0xff & cols;
*pos++ = (0xff00 & cols)/0x100;
*pos++ = 0xff & rows;
*pos++ = (0xff00 & rows)/0x100;
*pos++ = 0x7&(depth-1);
*pos++ = (depth==1)?2:depth;
fwrite(buffer,pos-buffer,1,dst);
pos = buffer;
buffer[0]=0x0;
cc = (depth==1)?0x4:1<<depth;
eoi = cc+1;
next = cc+2;
nBits = (depth==1)?3:depth+1;
first = InitIndices(first,cc);
pos = AddCodeToBuffer(cc,nBits,pos);
len=1; str=pixels; end = pixels+rows*cols;
target = str+rows*cols/10;
while(str+len<end) {
if(str+len>target) {
printf("(%3d,%3d): %3x\n",(str-pixels)/cols,(str-pixels)%cols,next);
target += rows*cols/10;
}
code = SearchTreeForCode(first,str,len,next,cc,0);
if(code!=-1) {
pos = AddCodeToBuffer(code,nBits,pos);
if(pos-buffer>BLOKLEN) {
buffer[-1] = BLOKLEN;
fwrite(buffer-1,BLOKLEN+1,1,dst);
buffer[0]=buffer[BLOKLEN];
buffer[1]=buffer[BLOKLEN+1];
buffer[2]=buffer[BLOKLEN+2];
buffer[3]=buffer[BLOKLEN+3];
pos -= BLOKLEN;
}
str += len-1;
len = 0;
if(next==(1<<nBits)) nBits++;
next++;
if(next==0xfff) {
first = InitIndices(first,cc);
pos = AddCodeToBuffer(cc,nBits,pos);
if(pos-buffer>BLOKLEN) {
buffer[-1] = BLOKLEN;
fwrite(buffer-1,BLOKLEN+1,1,dst);
buffer[0]=buffer[BLOKLEN];
buffer[1]=buffer[BLOKLEN+1];
buffer[2]=buffer[BLOKLEN+2];
buffer[3]=buffer[BLOKLEN+3];
pos -= BLOKLEN;
}
next = cc+2;
nBits = (depth==1)?3:depth+1;
}
}
len++;
}
code = SearchTreeForCode(first,str,len,next,cc,1);
pos = AddCodeToBuffer(code,nBits,pos);
pos = AddCodeToBuffer(eoi,nBits,pos);
pos = AddCodeToBuffer(0x0,-1,pos);
buffer[-1] = pos-buffer;
pos = AddCodeToBuffer(0x0,8,pos);
pos = AddCodeToBuffer(0x3b,8,pos);
fwrite(buffer-1,pos-buffer+1,1,dst);
fclose(dst);
}
TreePtr InitIndices(TreePtr first,int cc)
{
int i;
ClearTree(first,cc);
first = AddNode(-1,cc);
for(i=0;i<cc;i++) first->node[i] = AddNode(i,cc);
return first;
}
TreePtr AddNode(int code,int n)
{
TreePtr node;
node = (TreePtr)malloc(sizeof(TreeNode));
node->code = code;
node->node = (TreePtr *)malloc(n*sizeof(TreePtr));
do {
node->node[--n] = NULL;
} while (n);
return node;
}
void ClearTree(TreePtr node,int n)
{
int i;
if(node==NULL) return;
for(i=0;i<n;i++) ClearTree(node->node[i],n);
free(node->node);
free(node);
}
char *AddCodeToBuffer(int code,short n,char *buf)
{
static short need = 8;
int mask;
if(n<0) {
if(need<8) {
buf++;
*buf = 0x0;
}
need = 8;
return buf;
}
while(n>=need) {
mask = (1<<need)-1;
*buf += (mask&code)<<(8-need);
buf++;
*buf = 0x0;
code = code>>need;
n -= need;
need = 8;
}
if(n) {
mask = (1<<n)-1;
*buf += (mask&code)<<(8-need);
need -= n;
}
return buf;
}
int SearchTreeForCode(TreePtr node,int *str,int len,int next,int n,int done)
{
if(len==0) {
if(done) return node->code;
return -1;
}
if(node->node[str[0]])
return SearchTreeForCode(node->node[str[0]],str+1,len-1,next,n,done);
else {
node->node[str[0]] = AddNode(next,n);
return node->code;
}
}