/* DELETE_LINE
#!/bin/sh
#
# GIFBLAST Generic C Version 1.1,
# Copyright (C) 1992 Isaac Dimitrovsky.
#
# INSTRUCTIONS:                                                 DELETE_LINE
#                                                               DELETE_LINE
# You have two options for how to use this file.                DELETE_LINE
# If you just want to compile the code with a                   DELETE_LINE
# minimum of fuss, you can name this whole file                 DELETE_LINE
# gifblast.c and compile the whole file at once to              DELETE_LINE
# produce an executable program. On the PC, you must            DELETE_LINE
# compile with the large model. For systems that do             DELETE_LINE
# not accept ANSI-style function prototypes you must            DELETE_LINE
# compile with the option -DNOPROTOS. If you want to            DELETE_LINE
# look at the source code, you will probably want               DELETE_LINE
# to unpack this file into individual source files.             DELETE_LINE
# This can be done as follows. First, rename this               DELETE_LINE
# file x (for example). Then, edit x using your                 DELETE_LINE
# favorite editor and delete all lines containing               DELETE_LINE
# the string DELETE_LINE. Then, run /bin/sh on x.               DELETE_LINE
# You should obtain the split up source files,                  DELETE_LINE
# along with a makefile. You will have to tweak                 DELETE_LINE
# the makefile to get it to work on your system -               DELETE_LINE
# check it for instructions.                                    DELETE_LINE
#                                                               DELETE_LINE
# This version of the GIFBLAST source is free and               DELETE_LINE
# may be copied, distributed, and uploaded to                   DELETE_LINE
# bulletin boards. If you modify the source code                DELETE_LINE
# significantly, please don't use the GIFBLAST name             DELETE_LINE
# for your program to avoid confusion.                          DELETE_LINE
#                                                               DELETE_LINE
# shell archive - Extract with /bin/sh.
#
 DELETE_LINE */
#include <ctype.h>                              /* DELETE_LINE */
#include <stdio.h>                              /* DELETE_LINE */
#include <string.h>                             /* DELETE_LINE */
#define ARCON_NTYPES 2                          /* DELETE_LINE */
#define ARCON_SMALL_RBSIZE 64                   /* DELETE_LINE */
/* DELETE_LINE
echo extracting makefile
cat <<"END_OF_FILE" >makefile

# makefile for gifblast program

# You need to substitute here the appropriate lines for your system.
# The next four lines are for the MSC 5.1 compiler on the PC.
# The meanings of the options are:
# -AL - use large model
# -Ox - max. optimization
# -c, -D - standard
# For systems that do not accept ANSI-style function prototypes
# you should add -DNOPROTOS to the CC_ONE = ... line.
CC_ONE = cl -AL -Ox -c -DARCON_NTYPES=2 -DARCON_SMALL_RBSIZE=64
CC_LINK = cl -AL
OBJ_SUFFIX = .obj  # object file suffix
EXE_SUFFIX = .exe  # executable file suffix

all: gifblast$(EXE_SUFFIX)

gifblast$(EXE_SUFFIX): gifblast$(OBJ_SUFFIX) ubasic$(OBJ_SUFFIX) \
		uffile$(OBJ_SUFFIX) gifcode$(OBJ_SUFFIX) \
		arith$(OBJ_SUFFIX) arithcon$(OBJ_SUFFIX) gb11code$(OBJ_SUFFIX)
	$(CC_LINK) gifblast$(OBJ_SUFFIX) ubasic$(OBJ_SUFFIX) \
		uffile$(OBJ_SUFFIX) gifcode$(OBJ_SUFFIX) \
		arith$(OBJ_SUFFIX) arithcon$(OBJ_SUFFIX) gb11code$(OBJ_SUFFIX)

ubasic$(OBJ_SUFFIX): ubasic.h ubasic.c
	$(CC_ONE) -DNOFLOAT ubasic.c

uffile$(OBJ_SUFFIX): uffile.h uffile.c
	$(CC_ONE) uffile.c

gifcode$(OBJ_SUFFIX): uffile.h gifcode.h gifcode.c
	$(CC_ONE) gifcode.c

arith$(OBJ_SUFFIX): uffile.h arith.h arith.c
	$(CC_ONE) arith.c

arithcon$(OBJ_SUFFIX): arithcon.h arithcon.c
	$(CC_ONE) arithcon.c

gb11code$(OBJ_SUFFIX): uffile.h arith.h arithcon.h gb11code.h gb11code.c
	$(CC_ONE) gb11code.c

gifblast$(OBJ_SUFFIX): ubasic.h uffile.h gifcode.h \
		arith.h arithcon.h gb11code.h gifblast.c
	$(CC_ONE) gifblast.c
END_OF_FILE
echo extracting ubasic.h
cat <<"END_OF_FILE" >ubasic.h
 DELETE_LINE */

/* ubasic.h - Include file for basic routines, UNIX version. */

#ifndef P_DEFINED
#define P_DEFINED
#ifdef NOPROTOS
#define P(a,b) b
#else
#define P(a,b) a
#endif
#endif

#define FALSE 0
#define TRUE 1

#define BASIC_MAX_PRINTF 1024

typedef enum {
	SWITCHONOPT,SWITCHOFFOPT,STRARGOPT,INTARGOPT,LONGARGOPT
} OPTIONTYPE;

typedef struct {
	char *op_name;
	OPTIONTYPE op_type;
	void *op_pval;
} OPTION;

extern void *(*basic_alloc) P((size_t size),());
extern void (*basic_free) P((void *block),());

#define uhalt(m) (printf m, exit(1))

extern free_fnames P((char **fnames, int count, int freearr),());
extern process_command_line P((int *pargc, char **(*pargv), OPTION *opts),());
extern long divup P((long n, long m),());
extern long multup P((long n, long m),());
/* DELETE_LINE
END_OF_FILE
echo extracting ubasic.c
cat <<"END_OF_FILE" >ubasic.c
 DELETE_LINE */

/* ubasic.c - Some basic routines, UNIX version. */

/* DELETE_LINE
#include <ctype.h>
#include <stdio.h>
#include <string.h>

#include "ubasic.h"

 DELETE_LINE */
extern void *malloc P((size_t size),());
extern void free P((void *block),());

void *(*basic_alloc) P((size_t size),()) = malloc;
void (*basic_free) P((void *block),()) = free;

free_fnames(fnames,count,freearr)
char **fnames; int count; int freearr;
{
	int i;

	if (fnames == NULL)
		return;
	for (i=0; i<count; i++)
		(*basic_free)(fnames[i]);
	if (freearr)
		(*basic_free)(fnames);
}

static int
extract_long(str,l)
unsigned char *str; long *l;
{
	int negative;
	long oldval;

	(*l) = 0;
	negative = (*str=='-');
	if (*str=='+' || *str=='-')
		str++;
	do {
		if (!isdigit(*str))
			return FALSE;
		oldval = (*l);
		(*l) = (*l)*10 + (*str) - '0';
		if ((*l) < oldval)
			return FALSE;
		str++;
	} while (*str != '\0');
	if (negative)
		(*l) = -(*l);
	return TRUE;
}

process_command_line(pargc,pargv,opts)
int *pargc; char **(*pargv); OPTION *opts;
{
	int argno,newargno;
	OPTION *optr;
	char **newargv;
	long larg;

	if ((*pargc) <= 0) {
		(*pargc) = 0;
		(*pargv) = NULL;
		return;
	}
	newargno = 1;
	for (argno=1; argno<(*pargc); argno++) {
		if (opts != NULL) {
			for (optr=opts; optr->op_name!=NULL; optr++)
				if (strcmp((*pargv)[argno],optr->op_name) == 0)
					break;
		}
		if (opts==NULL || optr->op_name==NULL)
			newargno++;
		else if (optr->op_type==STRARGOPT || optr->op_type==INTARGOPT
			|| optr->op_type==LONGARGOPT) {
			if (argno == (*pargc)-1)
				uhalt(("argument required for %s option\n",optr->op_name));
			else
				argno++;
		}
	}
	if ((newargv=(*basic_alloc)((size_t)newargno*sizeof(newargv[0])))==NULL
		|| (newargv[0]=(*basic_alloc)(strlen((*pargv)[0])+1))==NULL)
		uhalt(("out of memory while processing command line\n"));
	strcpy(newargv[0],(*pargv)[0]);
	argno = newargno = 1;
	for (argno=1; argno<(*pargc); argno++) {
		if (opts != NULL) {
			for (optr=opts; optr->op_name!=NULL; optr++)
				if (strcmp((*pargv)[argno],optr->op_name) == 0)
					break;
		}
		if (opts==NULL || optr->op_name==NULL) {
			newargv[newargno] = (*basic_alloc)(strlen((*pargv)[argno])+1);
			if (newargv[newargno] == NULL)
				uhalt(("out of memory while copying file names\n"));
			strcpy(newargv[newargno],(*pargv)[argno]);
			newargno++;
		} else {
			switch (optr->op_type) {
			case SWITCHONOPT:
				(*(int *)optr->op_pval) = TRUE;
				break;
			case SWITCHOFFOPT:
				(*(int *)optr->op_pval) = FALSE;
				break;
			case STRARGOPT: case INTARGOPT: case LONGARGOPT:
				argno++;
				if (optr->op_type == STRARGOPT) {
					(*((char **)optr->op_pval)) =
						(*basic_alloc)(strlen((*pargv)[argno])+1);
					if ((*((char **)optr->op_pval)) == NULL)
						uhalt(("out of memory while copying %s option",
							optr->op_name));
					strcpy((*((char **)optr->op_pval)),(*pargv)[argno]);
				} else if (!extract_long(
						(unsigned char *)((*pargv)[argno]),&larg))
					uhalt(("invalid integer for %s option\n",optr->op_name));
				else if (optr->op_type == LONGARGOPT)
					(*(long *)optr->op_pval) = larg;
				else if (larg != (long)(int)larg)
					uhalt(("integer overflow in %s option\n",optr->op_name));
				else
					(*(int *)optr->op_pval) = (int)larg;
				break;
			default:
				uhalt(("error: unknown option type %d\n",(int)optr->op_type));
				break;
			}
		}
	}
	(*pargc) = newargno;
	(*pargv) = newargv;
}

long
divup(n,m)
long n; long m;
{
	return (n+m-1)/m;
}

long
multup(n,m)
long n; long m;
{
	return m*divup(n,m);
}
/* DELETE_LINE
END_OF_FILE
echo extracting uffile.h
cat <<"END_OF_FILE" >uffile.h
 DELETE_LINE */

/* uffile.h - Include file for portable fast file routines, UNIX version. */

#ifndef P_DEFINED
#define P_DEFINED
#ifdef NOPROTOS
#define P(a,b) b
#else
#define P(a,b) a
#endif
#endif

#define FFILEBUFSIZE 16384
#define BITS_IN_CHAR 8

enum {FF_READ,FF_WRITE};
typedef struct {
	FILE *f;
	int mode;
	size_t pos,count;
	long bits,tmpbits;
	char nbits;
	char onebitpos;
	unsigned char buf[FFILEBUFSIZE];
} FFILE;

/* functions/macros used internally only: */
extern int ff___inbuf P((FFILE *ff),());
extern int ff___outbuf P((int c, FFILE *ff),());
extern int ff___in1bit P((FFILE *ff),());
extern int ff___out1bit P((FFILE *ff, int bit),());
#define ff___advance_put1bitpos(ff) ((ff)->onebitpos==BITS_IN_CHAR-1 \
	? ((ff)->onebitpos=0, (ff)->count++) : (ff)->onebitpos++)

/* functions/macros for external use: */

/* The following work similarly to the standard i/o library. */
extern FFILE *ff_open P((char *fpath, int mode),());
/* Opens a new file (mode is FF_READ or FF_WRITE). Returns NULL on failure. */
#define ff_getc(ff) ((ff)->pos==(ff)->count \
	? ff___inbuf(ff) : (ff)->buf[(ff)->pos++])
/* Reads a single character from ff. Returns EOF on end of file. */
extern int ff_ungetc P((int c, FFILE *ff),());
/* Undoes a single character read from ff. The next read on ff will return c.
	At least one character may always be undone. May not be called with EOF
	as argument. Returns c, or EOF on failure. */
extern size_t ff_read P((char *buf, size_t n, FFILE *ff),());
/* Reads n characters from ff and places them into buf. Returns the number
	of characters successfully read. This may be less than n if end of file
	was reached during the read. */
#define ff_putc(c,ff) ((ff)->count==FFILEBUFSIZE \
	? ff___outbuf(c,ff) : ((ff)->buf[(ff)->count++]=(c)))
/* Writes a single character to ff. Returns EOF on failure. */
extern int ff_unputc P((FFILE *ff),());
/* Undoes a single character written to ff. If any characters have been
	written to ff, and ff_seek or ff_flush has not been called in the
	interim, then at least one character may be undone. Returns the last
	character written to ff, or EOF on failure. */
extern size_t ff_write P((char *buf, size_t n, FFILE *ff),());
/* Writes n characters from buf to ff. Returns the number of characters
	successfully written. This may be less than n if a disk write was
	unsuccessful (usually caused by a full disk). */
extern int ff_seek P((FFILE *ff, long offset, int whence),());
/* Seeks to a position in ff. Returns 0 on success, nonzero on failure. */
extern long ff_tell P((FFILE *ff),());
/* Returns the current position in ff, -1L on  failure. */
extern int ff_flush P((FFILE *ff),());
/* If ff is open for reading, discards any buffered input. Otherwise,
	writes all buffered output. Returns 0 on success, EOF on failure. */
extern int ff_close P((FFILE *ff),());
/* Closes ff, flushing buffers and freeing the storage used by ff. Returns 0
	on success, EOF on failure. */

/* The following is an optimized set of 1bitstream functions for the case
	where we only read or write one bit at a time. To begin, ff_start1bit
	must be called. Then, a series of ff_get1bit or ff_put1bit calls may
	be made, accordingly as the fast file structure is open for reading
	or writing. Finally, ff_end1bit must be called to end 1bitstream mode.
	None of the other routines above should be called while in 1bitstream
	mode (between ff_start1bit and ff_end1bit calls). */
extern void ff_start1bit P((FFILE *ff),());
/* Initializes 1bitstream state for ff. */
#define ff_get1bit(ff) ((ff)->pos==(ff)->count ? ff___in1bit(ff) \
	: ((ff)->onebitpos==BITS_IN_CHAR-1 \
		? ((ff)->onebitpos=0, \
			(((ff)->buf[(ff)->pos++]&(1<<(BITS_IN_CHAR-1))) != 0)) \
		: (((ff)->buf[(ff)->pos]&(1<<(ff->onebitpos++))) != 0)))
/* Reads one bit from ff. Returns -1 on failure. */
#define ff_put1bit(ff,b) ((ff)->count==FFILEBUFSIZE ? ff___out1bit(ff,b) \
	: (((ff)->onebitpos==0 && ((ff)->buf[(ff)->count]=0)), \
		(((b)&1)==0 ? (ff___advance_put1bitpos(ff), 0) \
			: ((ff)->buf[(ff)->count]|=(1<<(ff)->onebitpos), \
				ff___advance_put1bitpos(ff), 1))))
/* Writes the low bit of b to ff. Returns the low bit of b, or -1
	on failure. */
extern int ff_end1bit P((FFILE *ff),());
/* Ends 1bitstream state for ff. Returns 0 on success, or -1 on failure. */
/* DELETE_LINE
END_OF_FILE
echo extracting uffile.c
cat <<"END_OF_FILE" >uffile.c
 DELETE_LINE */

/* uffile.c - Portable fast file routines, UNIX version. */

/* DELETE_LINE
#include <stdio.h>
#include <string.h>

#include "ubasic.h"
#include "uffile.h"

 DELETE_LINE */
FFILE *
ff_open(fpath,mode)
char *fpath; int mode;
{
	FFILE *ff;

	if ((ff=(FFILE *)basic_alloc(sizeof(FFILE))) == NULL)
		return NULL;
	if ((ff->f=fopen(fpath,(mode==FF_READ?"rb":"wb"))) == NULL) {
		basic_free(ff);
		return NULL;
	}
	ff->mode = mode;
	ff->pos = ff->count = (mode==FF_READ?1:0);
	return ff;
}

static void
ff___fillbuf(ff)
FFILE *ff;
{
	ff->pos = 0;
	ff->count = fread(ff->buf,1,FFILEBUFSIZE,ff->f);
	if (ff->count == 0)
		ff->pos = ff->count = 1;
}

int
ff___inbuf(ff)
FFILE *ff;
{
	ff___fillbuf(ff);
	return (ff->pos==ff->count ? EOF : ff->buf[ff->pos++]);
}

int
ff_ungetc(c,ff)
int c; FFILE *ff;
{
	return ((c==EOF || ff->pos==0) ? EOF : (ff->buf[--ff->pos]=c));
}

size_t
ff_read(buf,n,ff)
char *buf; size_t n; FFILE *ff;
{
	size_t offset;

	offset = 0;
	while (n-offset > ff->count-ff->pos) {
		if (ff->count-ff->pos > 0)
			memcpy(buf+offset,ff->buf+ff->pos,ff->count-ff->pos);
		offset += (ff->count-ff->pos);
		ff___fillbuf(ff);
		if (ff->pos == ff->count)
			return offset;
	}
	if (n-offset > 0)
		memcpy(buf+offset,ff->buf+ff->pos,n-offset);
	ff->pos += (n-offset);
	return n;
}

static void
ff___flushbuf(ff)
FFILE *ff;
{
	size_t count,i;

	if (ff->count == 0)
		return;
	count = fwrite(ff->buf,1,ff->count,ff->f);
	if (0<count && count<ff->count) {
		for (i=0; i<ff->count-count; i++)
			ff->buf[i] = ff->buf[count+i];
	}
	ff->count -= count;
}

int
ff___outbuf(c,ff)
int c; FFILE *ff;
{
	ff___flushbuf(ff);
	if (ff->count != 0)
		return EOF;
	else
		return (ff->buf[ff->count++] = c);
}

int
ff_unputc(ff)
FFILE *ff;
{
	return (ff->count==0 ? EOF : ff->buf[--ff->count]);
}

size_t
ff_write(buf,n,ff)
char *buf; size_t n; FFILE *ff;
{
	size_t offset;

	offset = 0;
	while (n-offset > FFILEBUFSIZE-ff->count) {
		if (FFILEBUFSIZE-ff->count > 0)
			memcpy(ff->buf+ff->count,buf+offset,FFILEBUFSIZE-ff->count);
		offset += (FFILEBUFSIZE-ff->count);
		ff->count = FFILEBUFSIZE;
		ff___flushbuf(ff);
		if (ff->count != 0)
			return offset;
	}
	if (n-offset > 0)
		memcpy(ff->buf+ff->count,buf+offset,n-offset);
	ff->count += (n-offset);
	return n;
}

int
ff_seek(ff,offset,whence)
FFILE *ff; long offset; int whence;
{
	if (ff->mode == FF_READ)
		ff->pos = ff->count = 1;
	else {
		ff___flushbuf(ff);
		if (ff->count != 0)
			return -1;
	}
	return fseek(ff->f,offset,whence);
}

long
ff_tell(ff)
FFILE *ff;
{
	long fpos;

	fpos = ftell(ff->f);
	if (fpos == -1L)
		return fpos;
	else if (ff->mode == FF_READ)
		return fpos-(ff->count-ff->pos);
	else
		return fpos+ff->count;
}

int
ff_flush(ff)
FFILE *ff;
{
	if (ff->mode == FF_READ)
		ff->pos = ff->count = 1;
	else {
		ff___flushbuf(ff);
		if (ff->count != 0)
			return EOF;
	}
	return fflush(ff->f);
}

int
ff_close(ff)
FFILE *ff;
{
	int res;
	FILE *f;

	if (ff->mode == FF_READ)
		res = 0;
	else {
		ff___flushbuf(ff);
		res = (ff->count!=0 ? EOF : 0);
	}
	f = ff->f;
	basic_free(ff);
	if (fclose(f) == EOF)
		return EOF;
	else
		return res;
}

void
ff_start1bit(ff)
FFILE *ff;
{
	ff->onebitpos = 0;
}

int
ff___in1bit(ff)
FFILE *ff;
{
	ff___fillbuf(ff);
	if (ff->pos == ff->count)
		return -1;
	ff->onebitpos++;
	return (ff->buf[ff->pos]&1);
}

int
ff___out1bit(ff,bit)
FFILE *ff; int bit;
{
	ff___flushbuf(ff);
	if (ff->count != 0)
		return -1;
	ff->onebitpos++;
	return (ff->buf[ff->count] = (bit&1));
}

int
ff_end1bit(ff)
FFILE *ff;
{
	if (ff->onebitpos > 0) {
		if (ff->mode == FF_READ)
			ff->pos++;
		else
			ff->count++;
		ff->onebitpos = 0;
	}
	return 0;
}
/* DELETE_LINE
END_OF_FILE
echo extracting arith.h
cat <<"END_OF_FILE" >arith.h
 DELETE_LINE */

/* arith.h - Include file for arithmetic coding routines. */

#ifndef P_DEFINED
#define P_DEFINED
#ifdef NOPROTOS
#define P(a,b) b
#else
#define P(a,b) a
#endif
#endif

typedef struct {
	FFILE *ff;
	long low,high;
	union {
		struct {
			long bits_to_follow;
		} e;
		struct {
			long value;
		} d;
	} u;
} ARITH_CODER;

extern int arith_start_encoding P((ARITH_CODER *ac, FFILE *ff),());
/* Prepares to do arithmetic encoding to ff. Returns 0 on success,
	or -1 on failure. */
extern int arith_encode P((ARITH_CODER *ac, int rstart, int rend, int rtot),());
/* Encodes a fraction rstart..rend of the interval 0..rtot-1. Returns 0
	on success, or -1 on failure. */
extern int arith_end_encoding P((ARITH_CODER *ac),());
/* Ends encoding. Returns 0 on success, or -1 on failure. */
extern int arith_start_decoding P((ARITH_CODER *ac, FFILE *ff),());
/* Prepares to do arithmetic decoding from ff. Returns 0 on success,
	or -1 on failure. */
extern int arith_decode_getrpos P((ARITH_CODER *ac, int rtot),());
/* Gets the decoder's current position within 0..rtot-1. */
extern int arith_decode_advance P((ARITH_CODER *ac,
	int rstart, int rend, int rtot),());
/* Advances the decoder to account for a fraction rstart..rend of the
	interval 0..rtot-1. If rpos was the position returned by
	arith_decode_advance, then rstart..rend should be the interval
	within the appropriate context such that rstart<=rpos<rend.
	Returns 0 on success, or -1 on failure. */
extern int arith_end_decoding P((ARITH_CODER *ac),());
/* Ends decoding. Returns 0 on success, or -1 on failure. */
/* DELETE_LINE
END_OF_FILE
echo extracting arith.c
cat <<"END_OF_FILE" >arith.c
 DELETE_LINE */

/* arith.c - Arithmetic coding routines. */

/* DELETE_LINE
#include <stdio.h>
#include <string.h>

#include "uffile.h"
#include "arith.h"

 DELETE_LINE */
#define CODE_VALUE_BITS 16
#define FIRST_QUARTER (1L << (CODE_VALUE_BITS-2))
#define HALF (2*FIRST_QUARTER)
#define THIRD_QUARTER (3*FIRST_QUARTER)
#define TOP_VALUE ((1L<<CODE_VALUE_BITS) - 1)

int
arith_start_encoding(ac,ff)
ARITH_CODER *ac; FFILE *ff;
{
	if (ff == NULL)
		return -1;
	ac->ff = ff;
	ff_start1bit(ac->ff);
	ac->low = 0L;
	ac->high = TOP_VALUE;
	ac->u.e.bits_to_follow = 0L;
	return 0;
}

static int
f_bit_plus_follow(ac,bit)
ARITH_CODER *ac; int bit;
{
	if (ff_put1bit(ac->ff,bit) < 0)
		return -1;
	bit = !bit;
	for (; ac->u.e.bits_to_follow>0; ac->u.e.bits_to_follow--)
		if (ff_put1bit(ac->ff,bit) < 0)
			return -1;
	return 0;
}

#define bit_plus_follow(ac,bit) ((ac)->u.e.bits_to_follow==0 \
	? ff_put1bit((ac)->ff,(bit)) : f_bit_plus_follow(ac,bit))

int
arith_encode(ac,rstart,rend,rtot)
ARITH_CODER *ac; int rstart; int rend; int rtot;
{
	long iwidth;
	register unsigned int high,low;

	iwidth = ac->high+1-ac->low;
	high = (unsigned int)(ac->low + (iwidth*rend)/rtot - 1);
	low = (unsigned int)(ac->low + (iwidth*rstart)/rtot);
	for (;;) {
		if (high < HALF) {
			if (bit_plus_follow(ac,0) < 0)
				return -1;
		} else if (HALF <= low) {
			if (bit_plus_follow(ac,1) < 0)
				return -1;
			low -= HALF;
			high -= HALF;
		} else if (FIRST_QUARTER<=low && high<THIRD_QUARTER) {
			ac->u.e.bits_to_follow++;
			low -= FIRST_QUARTER;
			high -= FIRST_QUARTER;
		} else {
			ac->high = high;
			ac->low = low;
			return 0;
		}
		low <<= 1;
		high <<= 1;
		high++;
	}
}

int
arith_end_encoding(ac)
ARITH_CODER *ac;
{
	int bit,i;

	ac->u.e.bits_to_follow++;
	bit = (ac->low >= FIRST_QUARTER);
	if (bit_plus_follow(ac,bit) < 0)
		return -1;
	for (i=0; i<CODE_VALUE_BITS-2; i++)
		if (ff_put1bit(ac->ff,0) < 0)
			return -1;
	return ff_end1bit(ac->ff);
}

int
arith_start_decoding(ac,ff)
ARITH_CODER *ac; FFILE *ff;
{
	int i,bit;

	if (ff == NULL)
		return -1;
	ac->ff = ff;
	ff_start1bit(ac->ff);
	ac->low = 0L;
	ac->high = TOP_VALUE;
	ac->u.d.value = 0L;
	for (i=0; i<CODE_VALUE_BITS; i++) {
		if ((bit=ff_get1bit(ac->ff)) < 0)
			return -1;
		ac->u.d.value <<= 1;
		ac->u.d.value |= bit;
	}
	return 0;
}

int
arith_decode_getrpos(ac,rtot)
ARITH_CODER *ac; int rtot;
{
	return ((ac->u.d.value+1-ac->low)*rtot - 1) / (ac->high+1-ac->low);
}

int
arith_decode_advance(ac,rstart,rend,rtot)
ARITH_CODER *ac; int rstart; int rend; int rtot;
{
	long iwidth;
	int bit;
	register unsigned int high,low,value;

	iwidth = ac->high+1-ac->low;
	high = (unsigned int)(ac->low + (iwidth*rend)/rtot - 1);
	low = (unsigned int)(ac->low + (iwidth*rstart)/rtot);
	value = (unsigned int)ac->u.d.value;
	for (;;) {
		if (high < HALF)
			/* NOTHING */;
		else if (HALF <= low) {
			value -= HALF;
			low -= HALF;
			high -= HALF;
		} else if (FIRST_QUARTER<=low && high<THIRD_QUARTER) {
			value -= FIRST_QUARTER;
			low -= FIRST_QUARTER;
			high -= FIRST_QUARTER;
		} else {
			ac->high = high;
			ac->low = low;
			ac->u.d.value = value;
			return 0;
		}
		low <<= 1;
		high <<= 1;
		high++;
		value <<= 1;
		if ((bit=ff_get1bit(ac->ff)) < 0)
			return -1;
		value |= bit;
	}
}

int
arith_end_decoding(ac)
ARITH_CODER *ac;
{
	return ff_end1bit(ac->ff);
}
/* DELETE_LINE
END_OF_FILE
echo extracting arithcon.h
cat <<"END_OF_FILE" >arithcon.h
 DELETE_LINE */

/* arithcon.h - Include file for arithmetic coding context routines. */

#ifndef P_DEFINED
#define P_DEFINED
#ifdef NOPROTOS
#define P(a,b) b
#else
#define P(a,b) a
#endif
#endif

#define ARCON_NCODES 256 /* must be power of two */
typedef unsigned char ARCON_CODETYPE;
/* must be able to contain 0 .. ARCON_NCODES-1 */

#define ARCON_BIG_RBSIZE 1792
typedef struct {
	ARCON_CODETYPE rb[ARCON_BIG_RBSIZE];
	int count,tail;
	int freqs[2*ARCON_NCODES-1];
} ARCON_BIG_CONTEXT;

#ifndef ARCON_SMALL_RBSIZE
#define ARCON_SMALL_RBSIZE 20
#endif
typedef struct {
	ARCON_CODETYPE rb[ARCON_SMALL_RBSIZE];
	char count,tail;
	ARCON_CODETYPE hits[ARCON_SMALL_RBSIZE];
	char hitfreqs[ARCON_SMALL_RBSIZE];
	char nhits;
} ARCON_SMALL_CONTEXT;

#ifndef ARCON_NTYPES
#define ARCON_NTYPES 5
#endif
#define ARCON_MAXTYPEFREQ 512
typedef struct {
	int freqs[ARCON_NTYPES];
	int totfreq;
} ARCON_TYPE_CONTEXT;

/* Routines to keep track of large contexts: */
extern void arcon_big_init P((ARCON_BIG_CONTEXT *ac),());
/* Initializes a large context. */
extern int arcon_big_add P((ARCON_BIG_CONTEXT *ac, int c),());
/* Adds c to ac. Returns 0 on success, or -1 on failure. */
#define arcon_big_rtot(ac) ((ac)->freqs[2*ARCON_NCODES-2])
/* Returns the current total frequency of ac. */
extern int arcon_big_find_range P((ARCON_BIG_CONTEXT *ac,
	int c, int *prstart, int *prend),());
/* Sets *prstart..*prend to the current range for c in ac. Returns the
	size of this range, 0 if not found. */
extern int arcon_big_find_c P((ARCON_BIG_CONTEXT *ac,
	int rpos, int *prstart, int *prend),());
/* Sets *prstart..*prend to the current range that contains rpos in ac.
	Returns the character that corresponds to this range, -1 if not found. */

/* Routines to keep track of small contexts: */
extern void arcon_small_init P((ARCON_SMALL_CONTEXT *ac),());
/* Initializes a small context. */
extern int arcon_small_add P((ARCON_SMALL_CONTEXT *ac, int c),());
/* Adds c to ac. Returns 0 on success, or -1 on failure. */
#define arcon_small_rtot(ac) ((ac)->count)
/* Returns the current total frequency of ac. */
extern int arcon_small_find_range P((ARCON_SMALL_CONTEXT *ac,
	int c, int *prstart, int *prend),());
/* Sets *prstart..*prend to the current range for c in ac. Returns the
	size of this range, 0 if not found. */
extern int arcon_small_find_c P((ARCON_SMALL_CONTEXT *ac,
	int rpos, int *prstart, int *prend),());
/* Sets *prstart..*prend to the current range that contains rpos in ac.
	Returns the character that corresponds to this range, -1 if not found. */

/* Routines to keep track of type contexts: */
extern void arcon_type_init P((ARCON_TYPE_CONTEXT *ac),());
/* Initializes a type context. */
extern int arcon_type_add P((ARCON_TYPE_CONTEXT *ac, int c),());
/* Adds c to ac. Returns 0 on success, or -1 on failure. */
extern int arcon_type_rtot P((ARCON_TYPE_CONTEXT *ac, int t),());
/* Returns the current total frequency of ac up to and including type t. */
extern int arcon_type_find_range P((ARCON_TYPE_CONTEXT *ac,
	int c, int *prstart, int *prend),());
/* Sets *prstart..*prend to the current range for c in ac. Returns the
	size of this range, 0 if not found. */
extern int arcon_type_find_c P((ARCON_TYPE_CONTEXT *ac,
	int rpos, int *prstart, int *prend),());
/* Sets *prstart..*prend to the current range that contains rpos in ac.
	Returns the character that corresponds to this range, -1 if not found. */
/* DELETE_LINE
END_OF_FILE
echo extracting arithcon.c
cat <<"END_OF_FILE" >arithcon.c
 DELETE_LINE */

/* arithcon.c - Arithmetic coding context routines. */

/* DELETE_LINE
#include <stdio.h>
#include <string.h>

#include "arithcon.h"

 DELETE_LINE */
static void
join_big_freqs(freqs)
int *freqs;
{
	int n,i;

	n = ARCON_NCODES;
	do {
		for (i=0; i<n/2; i++)
			freqs[n+i] = freqs[2*i]+freqs[2*i+1];
		freqs += n;
		n /= 2;
	} while (n > 1);
}

static void
add_to_big_freqs(c,freqs)
int c; int *freqs;
{
	int n;

	n = ARCON_NCODES;
	do {
		(freqs[c])++;
		freqs += n;
		n /= 2;
		c /= 2;
	} while (n > 0);
}

static void
del_from_big_freqs(c,freqs)
int c; int *freqs;
{
	int n;

	n = ARCON_NCODES;
	do {
		(freqs[c])--;
		freqs += n;
		n /= 2;
		c /= 2;
	} while (n > 0);
}

static int
find_code_in_big_freqs(c,freqs)
int c; int *freqs;
{
	int start,n;

	start = 0;
	n = ARCON_NCODES;
	do {
		if ((c&1) != 0)
			start += freqs[(c&~1)];
		freqs += n;
		n /= 2;
		c /= 2;
	} while (c != 0);
	return start;
}

static int
find_freq_in_big_freqs(f,freqs,prstart)
int f; int *freqs; int *prstart;
{
	int c,n,pos;

	(*prstart) = 0;
	c = 0;
	n = 2;
	pos = 2*ARCON_NCODES-4;
	do {
		c <<= 1;
		if (freqs[pos+c] <= f) {
			(*prstart) += freqs[pos+c];
			f -= freqs[pos+c];
			c++;
		}
		n <<= 1;
		pos -= n;
	} while (pos >= 0);
	return c;
}

void
arcon_big_init(ac)
ARCON_BIG_CONTEXT *ac;
{
	int i;

	ac->count = ac->tail = 0;
	for (i=0; i<ARCON_NCODES; i++)
		ac->freqs[i] = 1;
	join_big_freqs(ac->freqs);
}

int
arcon_big_add(ac,c)
ARCON_BIG_CONTEXT *ac; int c;
{
	if (c<0 || ARCON_NCODES<=c)
		return -1;
	if (ac->count == ARCON_BIG_RBSIZE)
		del_from_big_freqs(ac->rb[ac->tail],ac->freqs);
	else
		ac->count++;
	ac->rb[ac->tail] = c;
	ac->tail = ((ac->tail+1)%ARCON_BIG_RBSIZE);
	add_to_big_freqs(c,ac->freqs);
	return 0;
}

int
arcon_big_find_range(ac,c,prstart,prend)
ARCON_BIG_CONTEXT *ac; int c; int *prstart; int *prend;
{
	int f;

	if (c<0 || ARCON_NCODES<=c)
		return 0;
	if ((f=ac->freqs[c]) > 0) {
		(*prstart) = find_code_in_big_freqs(c,ac->freqs);
		(*prend) = (*prstart) + f;
	}
	return f;
}

int
arcon_big_find_c(ac,rpos,prstart,prend)
ARCON_BIG_CONTEXT *ac;  int rpos; int *prstart; int *prend;
{
	int c;

	if (rpos<0 || arcon_big_rtot(ac)<=rpos)
		return -1;
	c = find_freq_in_big_freqs(rpos,ac->freqs,prstart);
	(*prend) = (*prstart) + ac->freqs[c];
	return c;
}

void
arcon_small_init(ac)
ARCON_SMALL_CONTEXT *ac;
{
	ac->count = ac->tail = 0;
	ac->nhits = 0;
}

int
arcon_small_add(ac,c)
ARCON_SMALL_CONTEXT *ac; int c;
{
	ARCON_CODETYPE *p;
	char *q;

	if (c<0 || ARCON_NCODES<=c)
		return -1;
	if (ac->count == ARCON_SMALL_RBSIZE) {
		p = (ARCON_CODETYPE *)memchr(ac->hits,ac->rb[ac->tail],ac->nhits);
		q = ac->hitfreqs + (p-ac->hits);
		if ((*q) > 1)
			(*q)--;
		else {
			(*p) = ac->hits[--(ac->nhits)];
			(*q) = ac->hitfreqs[ac->nhits];
		}
	} else
		ac->count++;
	ac->rb[ac->tail] = c;
	ac->tail = ((ac->tail+1)%ARCON_SMALL_RBSIZE);
	p = (ARCON_CODETYPE *)memchr(ac->hits,c,ac->nhits);
	if (p == NULL) {
		ac->hits[ac->nhits] = c;
		ac->hitfreqs[ac->nhits++] = 1;
	} else
		ac->hitfreqs[(p-ac->hits)]++;
	return 0;
}

int
arcon_small_find_range(ac,c,prstart,prend)
ARCON_SMALL_CONTEXT *ac; int c; int *prstart; int *prend;
{
	ARCON_CODETYPE *p;
	char *q;
	int f;

	if (c<0 || ARCON_NCODES<=c || ac->nhits==0
		|| (p=(ARCON_CODETYPE *)memchr(ac->hits,c,ac->nhits))==NULL)
		return 0;
	q = ac->hitfreqs + (p-ac->hits);
	(*prstart) = 0;
	f = *q;
	while (q != ac->hitfreqs)
		(*prstart) += *--q;
	(*prend) = (*prstart) + f;
	return f;
}

int
arcon_small_find_c(ac,rpos,prstart,prend)
ARCON_SMALL_CONTEXT *ac; int rpos; int *prstart; int *prend;
{
	char *q;

	if (rpos<0 || ac->count<=rpos)
		return -1;
	(*prstart) = 0;
	q = ac->hitfreqs;
	while ((*prstart)+(*q) <= rpos)
		(*prstart) += (*(q++));
	(*prend) = (*prstart)+(*q);
	return ac->hits[(q-ac->hitfreqs)];
}

void
arcon_type_init(ac)
ARCON_TYPE_CONTEXT *ac;
{
	int i;

	for (i=0; i<ARCON_NTYPES; i++)
		ac->freqs[i] = 1;
	ac->totfreq = ARCON_NTYPES;
}

int
arcon_type_add(ac,c)
ARCON_TYPE_CONTEXT *ac; int c;
{
	int i;

	if (c<0 || ARCON_NTYPES<=c)
		return -1;
	(ac->freqs[c])++;
	ac->totfreq++;
	if (ac->totfreq > ARCON_MAXTYPEFREQ) {
		for (i=0; i<ARCON_NTYPES; i++)
			ac->freqs[i] = (ac->freqs[i]+1)/2;
		ac->totfreq = 0;
		for (i=0; i<ARCON_NTYPES; i++)
			ac->totfreq += ac->freqs[i];
	}
	return 0;
}

int
arcon_type_rtot(ac,t)
ARCON_TYPE_CONTEXT *ac; int t;
{
	int i,res;

	res = 0;
	for (i=0; i<=t; i++)
		res += ac->freqs[i];
	return res;
}

int
arcon_type_find_range(ac,c,prstart,prend)
ARCON_TYPE_CONTEXT *ac; int c; int *prstart; int *prend;
{
	int i;

	if (c<0 || ARCON_NTYPES<=c)
		return 0;
	(*prstart) = 0;
	for (i=0; i<c; i++)
		(*prstart) += ac->freqs[i];
	(*prend) = (*prstart)+ac->freqs[c];
	return ac->freqs[c];
}

int
arcon_type_find_c(ac,rpos,prstart,prend)
ARCON_TYPE_CONTEXT *ac; int rpos; int *prstart; int *prend;
{
	int i;

	if (rpos<0 || ac->totfreq<=rpos)
		return -1;
	(*prstart) = i = 0;
	while ((*prstart)+ac->freqs[i] <= rpos)
		(*prstart) += ac->freqs[i++];
	(*prend) = (*prstart)+ac->freqs[i];
	return i;
}
/* DELETE_LINE
END_OF_FILE
echo extracting gifcode.h
cat <<"END_OF_FILE" >gifcode.h
 DELETE_LINE */

/* gifcode.h - Include file for GIF encoder/decoder routines. */

#ifndef P_DEFINED
#define P_DEFINED
#ifdef NOPROTOS
#define P(a,b) b
#else
#define P(a,b) a
#endif
#endif

#define GIF_MAXCODES 4096
typedef struct {
	FFILE *ff;
	unsigned char curblock[256];
	int curblocksize,curblockpos;
	int nbits;
	long bits;
	int datasize;
	int clear,eoi;
	int prefix[GIF_MAXCODES];
	unsigned char suffix[GIF_MAXCODES];
	int codesize,codemask;
	int avail;
	union {
		struct {
			int sl_ptr[GIF_MAXCODES];
			int sl_index;
			unsigned char sl_suffix[GIF_MAXCODES];
			int sl_newprefix[GIF_MAXCODES];
			int sl_next[GIF_MAXCODES];
			int curprefix;
		} e;
		struct {
			int prevc;
			unsigned char first[GIF_MAXCODES];
			unsigned char cstack[GIF_MAXCODES];
			int csttop;
		} d;
	} u;
} GIF_CODER;

/* functions/macros used internally only: */
extern int gif___f_decode_c P((GIF_CODER *gc),());

/* functions/macros for external use: */
extern void gif_start_encoding P((GIF_CODER *gc, FFILE *ff, int datasize),());
/* Prepares to encode an image to ff. Normally datasize will be the bits per
	pixel for the image, except for binary images where datasize = 2. */
extern int gif_encode_c P((int c, GIF_CODER *gc),());
/* Encodes a single pixel. Returns 0 on success, or -1 on failure. */
extern int gif_end_encoding P((GIF_CODER *gc),());
/* Ends encoding. Returns 0 on success, or -1 on failure. */
extern void gif_start_decoding P((GIF_CODER *gc, FFILE *ff, int datasize),());
/* Prepares to decode an image from ff. Normally datasize will be the bits per
	pixel for the image, except for binary images where datasize = 2. */
#define gif_decode_c(gc) ((gc)->u.d.csttop>0 \
	? (gc)->u.d.cstack[--((gc)->u.d.csttop)] : gif___f_decode_c(gc))
/* Decodes a single pixel. Returns a pixel value on success, or -1
	on failure. */
int gif_end_decoding P((GIF_CODER *gc),());
/* Ends decoding. Returns 0 on success, or -1 on failure. */
/* DELETE_LINE
END_OF_FILE
echo extracting gifcode.c
cat <<"END_OF_FILE" >gifcode.c
 DELETE_LINE */

/* gifcode.c - GIF encoder/decoder routines. */

/* DELETE_LINE
#include <stdio.h>
#include <string.h>

#include "uffile.h"
#include "gifcode.h"

 DELETE_LINE */
static void
init_coder(gc,ff,datasize)
GIF_CODER *gc; FFILE *ff; int datasize;
{
	int c;

	gc->ff = ff;
	gc->curblocksize = gc->curblockpos = 0;
	gc->nbits = 0;
	gc->bits = 0L;
	gc->datasize = datasize;
	gc->clear = (1<<datasize);
	gc->eoi = gc->clear+1;
	for (c=0; c<gc->clear; c++) {
		gc->prefix[c] = -1;
		gc->suffix[c] = c;
	}
}

static void
reset_codesize(gc)
GIF_CODER *gc;
{
	gc->codesize = gc->datasize+1;
	gc->codemask = (1<<gc->codesize)-1;
	gc->avail = gc->eoi+1;
}

static void
inc_codesize(gc)
GIF_CODER *gc;
{
	gc->codesize++;
	gc->codemask = (1<<gc->codesize)-1;
}

static void
clear_encoder(gc)
GIF_CODER *gc;
{
	reset_codesize(gc);
	memset(gc->u.e.sl_ptr,0,GIF_MAXCODES*sizeof(int));
	gc->u.e.sl_index = 1;
}

static void
clear_decoder(gc)
GIF_CODER *gc;
{
	reset_codesize(gc);
	gc->u.d.prevc = -1;
}

void
gif_start_encoding(gc,ff,datasize)
GIF_CODER *gc; FFILE *ff; int datasize;
{
	init_coder(gc,ff,datasize);
	clear_encoder(gc);
	gc->u.e.curprefix = -1;
}

static int
putcurblock(gc)
GIF_CODER *gc;
{
	if (ff_putc(gc->curblocksize,gc->ff)==EOF
		|| ff_write(gc->curblock,gc->curblocksize,gc->ff)!=gc->curblocksize)
		return -1;
	gc->curblocksize = 0;
	return 0;
}

static int
putcode(c,gc)
int c; GIF_CODER *gc;
{
	gc->bits |= (((long)(c&gc->codemask))<<gc->nbits);
	gc->nbits += gc->codesize;
	while (gc->nbits >= 8) {
		gc->curblock[gc->curblocksize++] = (gc->bits&0xFF);
		gc->bits >>= 8;
		gc->nbits -= 8;
		if (gc->curblocksize==254 && putcurblock(gc)<0)
			return -1;
	}
	return 0;
}

static int
end_putcode(gc)
GIF_CODER *gc;
{
	if (putcode(gc->eoi,gc) < 0)
		return -1;
	if (gc->nbits > 0)
		gc->curblock[gc->curblocksize++] = (gc->bits&0xFF);
	if (gc->curblocksize>0 && putcurblock(gc)<0)
		return -1;
	if (ff_putc(0,gc->ff) == EOF)
		return -1;
	return 0;
}

static int
getcode(gc)
GIF_CODER *gc;
{
	int size,c;

	while (gc->nbits < gc->codesize) {
		if (gc->curblockpos < gc->curblocksize) {
			gc->bits |= (((long)gc->curblock[gc->curblockpos++])<<gc->nbits);
			gc->nbits += 8;
		} else if ((size=ff_getc(gc->ff))==EOF || size==0
			|| ff_read(gc->curblock,size,gc->ff)!=size)
			return -1;
		else {
			gc->curblocksize = size;
			gc->curblockpos = 0;
		}
	}
	c = (int)(gc->bits&gc->codemask);
	gc->bits >>= gc->codesize;
	gc->nbits -= gc->codesize;
	return c;
}

static int
end_getcode(gc)
GIF_CODER *gc;
{
	int size;

	if (gc->curblockpos == gc->curblocksize) {
		if ((size=ff_getc(gc->ff)) == 0)
			return 0;
		else if (size==EOF || ff_read(gc->curblock,size,gc->ff)!=size)
			return -1;
		else {
			gc->curblocksize = size;
			gc->curblockpos = 0;
		}
	}
	if (getcode(gc) != gc->eoi)
		return -1;
	if (ff_getc(gc->ff) == 0)
		return 0;
	else
		return -1;
}

static int
check_codetable(gc,c)
GIF_CODER *gc; int c;
{
	int ind;

	ind = gc->u.e.sl_ptr[gc->u.e.curprefix];
	while (ind != 0)
		if (c == gc->u.e.sl_suffix[ind])
			return gc->u.e.sl_newprefix[ind];
		else
			ind = gc->u.e.sl_next[ind];
	return -1;
}

static void
add_to_codetable(gc,newc)
GIF_CODER *gc; int newc;
{
	int ind;

	ind = gc->u.e.sl_index++;
	gc->u.e.sl_next[ind] = gc->u.e.sl_ptr[gc->prefix[newc]];
	gc->u.e.sl_ptr[gc->prefix[newc]] = ind;
	gc->u.e.sl_suffix[ind] = gc->suffix[newc];
	gc->u.e.sl_newprefix[ind] = newc;
}

int
gif_encode_c(c,gc)
int c; GIF_CODER *gc;
{
 	int newpref,newc;

	if (gc->u.e.curprefix < 0) {
		gc->u.e.curprefix = c;
		return putcode(gc->clear,gc);
	} else if ((newpref=check_codetable(gc,c)) >= 0) {
		gc->u.e.curprefix = newpref;
		return 0;
	}
	newc = gc->avail++;
	gc->prefix[newc] = gc->u.e.curprefix;
	gc->suffix[newc] = c;
	add_to_codetable(gc,newc);
	if (putcode(gc->u.e.curprefix,gc) < 0)
		return -1;
	gc->u.e.curprefix = c;
	if (gc->avail == GIF_MAXCODES) {
		if (putcode(gc->clear,gc) < 0)
			return -1;
		clear_encoder(gc);
	} else if (gc->codemask < newc)
		inc_codesize(gc);
	return 0;
}

int
gif_end_encoding(gc)
GIF_CODER *gc;
{
	if ((gc->u.e.curprefix>=0 && putcode(gc->u.e.curprefix,gc)<0)
		|| end_putcode(gc)<0)
		return -1;
	else
		return 0;
}

void
gif_start_decoding(gc,ff,datasize)
GIF_CODER *gc; FFILE *ff; int datasize;
{
	int c;

	init_coder(gc,ff,datasize);
	clear_decoder(gc);
	for (c=0; c<gc->clear; c++)
		gc->u.d.first[c] = c;
	gc->u.d.csttop = 0;
}

int
gif___f_decode_c(gc)
GIF_CODER *gc;
{
	int c,newc;

	for (;;) {
		if (gc->u.d.csttop > 0)
			return gc->u.d.cstack[--gc->u.d.csttop];
		else if ((c=getcode(gc))<0 || c==gc->eoi || gc->avail<c)
			return -1;
		else if (c == gc->clear)
			clear_decoder(gc);
		else {
			if (gc->u.d.prevc>=0 && gc->avail<GIF_MAXCODES) {
				newc = gc->avail++;
				gc->prefix[newc] = gc->u.d.prevc;
				gc->u.d.first[newc] = gc->u.d.first[gc->u.d.prevc];
				gc->suffix[newc] = gc->u.d.first[c];
				if (gc->codemask<gc->avail && gc->avail<GIF_MAXCODES)
					inc_codesize(gc);
			}
			if (c == gc->avail)
				return -1;
			gc->u.d.prevc = c;
			do {
				gc->u.d.cstack[gc->u.d.csttop++] = gc->suffix[c];
				c = gc->prefix[c];
			} while (c >= 0);
		}
	}
}

int
gif_end_decoding(gc)
GIF_CODER *gc;
{
	if (end_getcode(gc) < 0)
		return -1;
	else
		return 0;
}
/* DELETE_LINE
END_OF_FILE
echo extracting gb11code.h
cat <<"END_OF_FILE" >gb11code.h
 DELETE_LINE */

/* gb11code.h - Include file for special purpose GIF compressor routines
	(version 1.1). */

#ifndef P_DEFINED
#define P_DEFINED
#ifdef NOPROTOS
#define P(a,b) b
#else
#define P(a,b) a
#endif
#endif

typedef struct {
	ARCON_BIG_CONTEXT ac_order_0_con;
	ARCON_SMALL_CONTEXT ac_order_1_cons[ARCON_NCODES];
	ARCON_TYPE_CONTEXT ac_type_con;
	int prev;
	ARITH_CODER ac_struct;
} GB11_CODER;

extern int copy_if_larger;

extern int gb11_start_encoding P((GB11_CODER *gb11, FFILE *ff),());
extern int gb11_encode_c P((int c, GB11_CODER *gb11),());
extern int gb11_end_encoding P((GB11_CODER *gb11),());
extern int gb11_start_decoding P((GB11_CODER *gb11, FFILE *ff),());
extern int gb11_decode_c P((GB11_CODER *gb11),());
extern int gb11_end_decoding P((GB11_CODER *gb11),());
/* DELETE_LINE
END_OF_FILE
echo extracting gb11code.c
cat <<"END_OF_FILE" >gb11code.c
 DELETE_LINE */

/* gb11code.c - Special purpose GIF compressor routines (version 1.1). */

/* DELETE_LINE
#include <stdio.h>
#include <string.h>

#include "uffile.h"
#include "arith.h"
#include "arithcon.h"
#include "gb11code.h"

 DELETE_LINE */
int copy_if_larger=1;

static void
gb11_init(gb11)
GB11_CODER *gb11;
{
	int i;

	arcon_big_init(&gb11->ac_order_0_con);
	for (i=0; i<ARCON_NCODES; i++)
		arcon_small_init(&(gb11->ac_order_1_cons[i]));
	arcon_type_init(&gb11->ac_type_con);
	gb11->prev = 0;
}

int
gb11_start_encoding(gb11,ff)
GB11_CODER *gb11; FFILE *ff;
{
	gb11_init(gb11);
	return arith_start_encoding(&gb11->ac_struct,ff);
}

int
gb11_encode_c(c,gb11)
int c; GB11_CODER *gb11;
{
	int rstart,rend,rtot,t,trstart,trend,trtot;
	ARCON_BIG_CONTEXT *big_con;
	ARCON_SMALL_CONTEXT *small_con;
	ARCON_TYPE_CONTEXT *type_con;

	big_con = &gb11->ac_order_0_con;
	small_con = &(gb11->ac_order_1_cons[gb11->prev]);
	type_con = &gb11->ac_type_con;
	if (arcon_small_find_range(small_con,c,&rstart,&rend)) {
		t = 1;
		rtot = arcon_small_rtot(small_con);
	} else if (arcon_big_find_range(big_con,c,&rstart,&rend)) {
		t = 0;
		rtot = arcon_big_rtot(big_con);
	} else
		return -1;
	if (arcon_type_find_range(type_con,t,&trstart,&trend))
		trtot = arcon_type_rtot(type_con,1);
	else
		return -1;
	if (arith_encode(&gb11->ac_struct,trstart,trend,trtot)<0
		|| arith_encode(&gb11->ac_struct,rstart,rend,rtot)<0
		|| arcon_type_add(type_con,t)<0
		|| arcon_small_add(small_con,c)<0
		|| (t==0 && arcon_big_add(big_con,c)<0))
		return -1;
	gb11->prev = c;
	return 0;
}

int
gb11_end_encoding(gb11)
GB11_CODER *gb11;
{
	return arith_end_encoding(&gb11->ac_struct);
}

int
gb11_start_decoding(gb11,ff)
GB11_CODER *gb11; FFILE *ff;
{
	gb11_init(gb11);
	return arith_start_decoding(&gb11->ac_struct,ff);
}

int
gb11_decode_c(gb11)
GB11_CODER *gb11;
{
	int trstart,trend,trtot,trpos,t,rstart,rend,rtot,rpos,c;
	ARCON_BIG_CONTEXT *big_con;
	ARCON_SMALL_CONTEXT *small_con;
	ARCON_TYPE_CONTEXT *type_con;

	big_con = &gb11->ac_order_0_con;
	small_con = &(gb11->ac_order_1_cons[gb11->prev]);
	type_con = &gb11->ac_type_con;
	trtot = arcon_type_rtot(type_con,1);
	trpos = arith_decode_getrpos(&gb11->ac_struct,trtot);
	if ((t=arcon_type_find_c(type_con,trpos,&trstart,&trend))<0
		|| arith_decode_advance(&gb11->ac_struct,trstart,trend,trtot)<0
		|| arcon_type_add(type_con,t)<0)
		return -1;
	if (t == 0) {
		rtot = arcon_big_rtot(big_con);
		rpos = arith_decode_getrpos(&gb11->ac_struct,rtot);
		if ((c=arcon_big_find_c(big_con,rpos,&rstart,&rend))<0
			|| arith_decode_advance(&gb11->ac_struct,rstart,rend,rtot)<0
			|| arcon_big_add(big_con,c)<0
			|| arcon_small_add(small_con,c)<0)
			return -1;
	} else {
		rtot = arcon_small_rtot(small_con);
		rpos = arith_decode_getrpos(&gb11->ac_struct,rtot);
		if ((c=arcon_small_find_c(small_con,rpos,&rstart,&rend))<0
			|| arith_decode_advance(&gb11->ac_struct,rstart,rend,rtot)<0
			|| arcon_small_add(small_con,c)<0)
			return -1;
	}
	gb11->prev = c;
	return c;
}

int
gb11_end_decoding(gb11)
GB11_CODER *gb11;
{
	return arith_end_decoding(&gb11->ac_struct);
}
/* DELETE_LINE
END_OF_FILE
echo extracting gifblast.c
cat <<"END_OF_FILE" >gifblast.c
 DELETE_LINE */

/* gifblast.c - Special purpose GIF compressor, main program. */

/* DELETE_LINE
#include <ctype.h>
#include <stdio.h>
#include <string.h>

#include "ubasic.h"
#include "uffile.h"
#include "gifcode.h"
#include "arith.h"
#include "arithcon.h"
#include "gb11code.h"

 DELETE_LINE */
#define MAX_IM_WIDTH 3072
#define MAX_IM_HEIGHT 3072

static char *usage_message1[] = {
	"\n",
	"/| I s a a c |/\n",
	"/|Dimitrovsky|/ Presents GIFBLAST, a lossless GIF file compressor.\n",
	"/|  L a b s  |/ Generic C Version 1.1, Copyright (C) 1992 Isaac Dimitrovsky.\n",
	"GIFBLAST is a compressor designed especially for GIF files. The usual file\n",
	"compressors (PKZIP, ARJ, ZOO, etc.) do not work on GIF files; GIFBLAST does.\n",
	"When you run GIFBLAST X.GIF, you get a compressed file X.GFB that is usually\n",
	"20-25% smaller. In order to view this file you have to run GIFBLAST -D X.GFB\n",
	"to decompress X.GFB and get back the original X.GIF file. For convenience\n",
	"you can omit the .GIF and .GFB suffixes and give several files.\n",
	"\n",
	"GIFBLAST is recommended for applications such as storing GIF files on BBS's\n",
	"and posting GIF files to usenet. Because GIFBLAST perfectly preserves all\n",
	"images and other information in GIF files, the user need not be concerned\n",
	"with harming the images or introducing compression artifacts.\n",
	"\n",
	"This version of the GIFBLAST source is free and may be copied, distributed,\n",
	"and uploaded to bulletin boards. If you modify the source code significantly,\n",
	"please don't use the GIFBLAST name for your program to avoid confusion.\n",
	"Version 2.0 of GIFBLAST will be available on October 30, 1992.\n",
	"It will work faster and compress better than the current version.\n",
	"To order, make a $20 check payable to Isaac Dimitrovsky Labs and send it to:\n",
	"\tIsaac Dimitrovsky Labs, 147 Second Ave #484, New York NY 10003\n",
	"Be sure to include a full return address, and specify 3.5 or 5 inch disks.\n",
	"You will receive PC executable and generic C source on a PC-format disk.\n",
	NULL
};
static char *more_message =
	"                        (press return for more)"
;
static char *usage_message2[] = {
	"\n",
	"Legal Matters:\n",
	"\n",
	"This software is provided \"as is\" without any warranty express or implied,\n",
	"including but not limited to implied warranties of merchantability and\n",
	"fitness for a particular purpose.\n",
	"\n",
	"The Graphics Interchange Format(c) is the Copyright property of CompuServe\n",
	"Incorporated. GIF(sm) is a Service Mark property of CompuServe Incorporated.\n",
	NULL
};
static char *header_message[] = {
	"GIFBLAST Generic C Version 1.1, Copyright (C) 1992 Isaac Dimitrovsky.\n",
	"Type GIFBLAST -H for instructions.\n",
	NULL
};
static int usage=FALSE;
static int compress_opt=TRUE;
static OPTION opts[] = {
	{"-usage",SWITCHONOPT,&usage},
	{"-help",SWITCHONOPT,&usage},
	{"/help",SWITCHONOPT,&usage},
	{"-HELP",SWITCHONOPT,&usage},
	{"/HELP",SWITCHONOPT,&usage},
	{"-h",SWITCHONOPT,&usage},
	{"/h",SWITCHONOPT,&usage},
	{"-H",SWITCHONOPT,&usage},
	{"/H",SWITCHONOPT,&usage},
	{"-?",SWITCHONOPT,&usage},
	{"/?",SWITCHONOPT,&usage},
	{"-d",SWITCHOFFOPT,&compress_opt},
	{"/d",SWITCHOFFOPT,&compress_opt},
	{"-D",SWITCHOFFOPT,&compress_opt},
	{"/D",SWITCHOFFOPT,&compress_opt},
	{NULL}
};

static unsigned char buf[MAX_IM_WIDTH];
static int in_image;
static GIF_CODER *gc;
static GB11_CODER *gb11;

static int
has_suff(str,ploc)
char *str; int *ploc;
{
	int res,i;

	res = FALSE;
	for (i=strlen(str)-1; i>=0; i--) {
		res = (str[i] == '.');
		if (res || str[i]=='\\' || str[i]==':')
			break;
	}
	(*ploc) = i;
	return res;
}

static int
is_lowercase_fname(fname)
char *fname;
{
	for (; *fname!='\0'; fname++) {
		if (isascii(*fname) && islower(*fname))
			return TRUE;
	}
	return FALSE;
}

static void
add_suffs(argc,argv)
int argc; char **argv;
{
	int i,j;
	char *newarg;

	for (i=1; i<argc; i++) {
		if ((newarg=basic_alloc(strlen(argv[i])+5)) == NULL)
			uhalt(("out of memory while parsing command line arguments"));
		strcpy(newarg,argv[i]);
		basic_free(argv[i]);
		argv[i] = newarg;
		if (!has_suff(newarg,&j))
			strcat(newarg,(compress_opt
				? (is_lowercase_fname(newarg) ? ".gif" : ".GIF")
				: (is_lowercase_fname(newarg) ? ".gfb" : ".GFB")));
	}
}

static char *
change_to_out_suff(arg)
char *arg;
{
	int i;
	char *newarg;

	if (!has_suff(arg,&i))
		uhalt(("impossible command line argument %s",arg));
	if ((newarg=basic_alloc(strlen(arg)+5)) == NULL)
		return NULL;
	strcpy(newarg,arg);
	strcpy(newarg+i,(compress_opt
		? (is_lowercase_fname(newarg) ? ".gfb" : ".GFB")
		: (is_lowercase_fname(newarg) ? ".gif" : ".GIF")));
	return newarg;
}

static int
init_files(inff,outff)
FFILE *inff; FFILE *outff;
{
	in_image = FALSE;
	if (compress_opt)
		return gb11_start_encoding(gb11,outff);
	else
		return gb11_start_decoding(gb11,inff);
}

static int
end_files()
{
	if (compress_opt)
		return gb11_end_encoding(gb11);
	else
		return gb11_end_decoding(gb11);
}

static void
init_image(inff,outff,datasize)
FFILE *inff; FFILE *outff; int datasize;
{
	in_image = TRUE;
	if (compress_opt)
		gif_start_decoding(gc,inff,datasize);
	else
		gif_start_encoding(gc,outff,datasize);
}

static int
end_image()
{
	in_image = FALSE;
	if (compress_opt)
		return gif_end_decoding(gc);
	else
		return gif_end_encoding(gc);
}

static int
inff_getc(inff)
FFILE *inff;
{
	if (compress_opt && in_image)
		return gif_decode_c(gc);
	else if (compress_opt)
		return ff_getc(inff);
	else
		return gb11_decode_c(gb11);
}

static size_t
inff_read(buf,nbytes,inff)
unsigned char *buf; size_t nbytes; FFILE *inff;
{
	register size_t i;
	int c;

	if (compress_opt && in_image) {
		for (i=0; i<nbytes; i++) {
			if ((c=gif_decode_c(gc)) < 0)
				break;
			buf[i] = c;
		}
	} else if (compress_opt)
		i = ff_read(buf,nbytes,inff);
	else {
		for (i=0; i<nbytes; i++) {
			if ((c=gb11_decode_c(gb11)) < 0)
				break;
			buf[i] = c;
		}
	}
	return i;
}

static int
outff_putc(c,outff)
int c; FFILE *outff;
{
	if (compress_opt)
		return gb11_encode_c(c,gb11);
	else if (in_image)
		return gif_encode_c(c,gc);
	else
		return ff_putc(c,outff);
}

static size_t
outff_write(buf,nbytes,outff)
unsigned char *buf; size_t nbytes; FFILE *outff;
{
	register size_t i;

	if (compress_opt) {
		for (i=0; i<nbytes; i++)
			if (gb11_encode_c(buf[i],gb11) < 0)
				break;
	} else if (in_image) {
		for (i=0; i<nbytes; i++)
			if (gif_encode_c(buf[i],gc) < 0)
				break;
	} else
		i = ff_write(buf,nbytes,outff);
	return i;
}

static int
copyfile(inff,outff)
FFILE *inff; FFILE *outff;
{
	int c;

	while ((c=ff_getc(inff)) != EOF)
		if (ff_putc(c,outff) == EOF)
			return FALSE;
	return TRUE;
}

static void
gifblast(infname)
char *infname;
{
#define fail(args) {printf args ; failed=TRUE; goto endlabel;}
	FFILE *inff,*testf,*outff;
	char *outfname;
	int g_bpp,g_colmapsize,im_no,im_width,im_height,im_bpp;
	int im_colmapsize,im_datasize,im_v,c,extcode,size,pct_done,failed;
	long im_totbytes;

	printf("file %s:\n",infname);
	failed = FALSE;
	outfname = NULL;
	outff = NULL;
	if ((inff=ff_open(infname,FF_READ)) == NULL)
		fail(("\tunable to open file\n"));
	if ((outfname=change_to_out_suff(infname)) == NULL)
		fail(("\tout of memory while copying filename\n"));
	if ((testf=ff_open(outfname,FF_READ)) != NULL) {
		ff_close(testf);
		fail(("\twill not overwrite existing output file %s\n",outfname));
	}
	if ((outff=ff_open(outfname,FF_WRITE)) == NULL)
		fail(("\tunable to open output file %s\n",outfname));
	if (ff_read(buf,6,inff) != 6)
		fail(("\tincomplete header\n"));
	if ((!compress_opt) && strncmp(buf,"GIF",3)==0) {
		if (ff_write(buf,6,outff) != 6)
			fail(("\tunable to write header\n"));
		if (!copyfile(inff,outff))
			fail(("\tunable to write output file\n"));
		goto endlabel;
	}
	if (compress_opt ? strncmp(buf,"GIF",3)!=0 : strncmp(buf,"GB",2)!=0)
		fail(("\tinvalid header\n"));
	if (compress_opt) {
		buf[1] = 'B';
		buf[2] = 0x11;
	} else if (buf[2] != 0x11) {
		fail(("\tunable to decompress this code version (%d.%d)\n",
			buf[2]>>4,buf[2]&0xF));
	} else {
		buf[1] = 'I';
		buf[2] = 'F';
	}
	if (ff_write(buf,6,outff) != 6)
		fail(("\tunable to write header\n"));
	if (init_files(inff,outff) < 0)
		fail(("\tunable to initialize coder\n"));
	if (inff_read(buf,7,inff) != 7)
		fail(("\tunable to read screen descriptor\n"));
	if (outff_write(buf,7,outff) != 7)
		fail(("\tunable to write screen descriptor\n"));
	g_bpp = (buf[4]&0x7)+1;
	if ((buf[4]&0x80) != 0) {
		g_colmapsize = 3*(1<<g_bpp);
		if (inff_read(buf,g_colmapsize,inff) != g_colmapsize)
			fail(("\tunable to read global color map\n"));
		if (outff_write(buf,g_colmapsize,outff) != g_colmapsize)
			fail(("\tunable to write global color map\n"));
	}
	im_no = 0;
	do {
		if ((c=inff_getc(inff)) < 0)
			fail(("\tunexpected end of file\n"));
		if (outff_putc(c,outff) < 0)
			fail(("\tunable to write file\n"));
		switch (c) {
		case ',':
			if (inff_read(buf,9,inff) != 9)
				fail(("\tunable to read image descriptor\n"));
			im_width = ((((int)buf[4])&0xFF) | ((((int)buf[5])&0xFF)<<8));
			im_height = ((((int)buf[6])&0xFF) | ((((int)buf[7])&0xFF)<<8));
			if (im_width<=0 || MAX_IM_WIDTH<im_width
				|| im_height<=0 || MAX_IM_HEIGHT<im_height)
				fail(("\timage size out of range (%dx%d)\n",
					im_width,im_height));
			if ((buf[8]&0x80) != 0) {
				im_bpp = (buf[8]&0x7)+1;
				im_colmapsize = 3*(1<<im_bpp);
			} else {
				im_bpp = g_bpp;
				im_colmapsize = 0;
			}
			printf("\tprocessing image %d, %dx%d, %d bpp: ",
				++im_no,im_width,im_height,im_bpp);
			if (im_colmapsize>0
				&& inff_read(buf+9,im_colmapsize,inff)!=im_colmapsize)
				fail(("\n\t\tunable to read image color map\n"));
			if (outff_write(buf,im_colmapsize+9,outff) != im_colmapsize+9)
				fail(("\n\t\tunable to write image descriptor\n"));
			im_datasize = inff_getc(inff);
			if (im_datasize != (im_bpp==1 ? 2 : im_bpp))
				fail(("\n\t\tinvalid number of data bits in image (%d)\n",
					im_datasize));
			if (outff_putc(im_datasize,outff) < 0)
				fail(("\n\t\tunable to write image data bits\n"));
			init_image(inff,outff,im_datasize);
			im_totbytes = 0L;
			printf("     ");
			for (im_v=0; im_v<im_height; im_v++) {
				if (inff_read(buf,im_width,inff) != im_width)
					fail(("\n\t\terror detected reading image pixels\n"));
				if (outff_write(buf,im_width,outff) != im_width)
					fail(("\n\t\tunable to write image pixels\n"));
				im_totbytes += im_width;
				if (im_v<im_height-1 && (im_v%4)!=0)
					continue;
				pct_done =
					(int)((im_totbytes*100L)/(im_height*(long)im_width));
				printf("\b\b\b\b\b%c%c%c%% ",(pct_done==100?'1':' '),
					'0'+((pct_done/10)%10),'0'+(pct_done%10));
				fflush(stdout);
			}
			putchar('\n');
			if (end_image() < 0)
				fail(("\terror detected at end of image pixels\n"));
			break;
		case ';':
			break;
		case '!':
			if ((extcode=inff_getc(inff)) < 0)
				fail(("\tunexpected end of file\n"));
			if (outff_putc(extcode,outff) < 0)
				fail(("\tunable to write file\n"));
			do {
				if ((size=inff_getc(inff)) < 0)
					fail(("\tunexpected end of file\n"));
				buf[0] = size;
				if (size>0 && inff_read(buf+1,size,inff)!=size)
					fail(("\tunable to read extension block\n"));
				if (outff_write(buf,size+1,outff) != size+1)
					fail(("\tunable to write extension block\n"));
			} while (size > 0);
			break;
		default:
			fail(("\tunexpected character\n"));
		}
	} while (c != ';');
	if (end_files() < 0)
		fail(("\terror detected at end of file\n"));
	if (copy_if_larger && compress_opt && ff_tell(outff)>ff_tell(inff)) {
		ff_close(outff);
		if ((outff=ff_open(outfname,FF_WRITE)) == NULL)
			fail(("\tunable to reset output file\n"));
		ff_close(inff);
		if ((inff=ff_open(infname,FF_READ)) == NULL)
			fail(("\tunable to reset input file\n"));
		if (!copyfile(inff,outff))
			fail(("\tunable to rewrite output file\n"));
	}
	if (compress_opt)
		printf("done (%d%% savings)\n",
			(int)(((ff_tell(inff)-ff_tell(outff))*100L)/ff_tell(inff)));
endlabel:
	if (inff != NULL)
		ff_close(inff);
	if (outff != NULL) {
		ff_close(outff);
		if (failed)
			unlink(outfname);
	}
	if (outfname != NULL)
		basic_free(outfname);
}

main(argc,argv)
int argc; char **argv;
{
	int c,i;

	process_command_line(&argc,&argv,opts);
	if (usage || argc<=1) {
		for (i=0; usage_message1[i]!=NULL; i++)
			fprintf(stderr,"%s",usage_message1[i]);
		fprintf(stderr,"%s",more_message);
		do {
			c = getchar();
		} while (c != '\n');
		for (i=0; usage_message2[i]!=NULL; i++)
			fprintf(stderr,"%s",usage_message2[i]);
		uhalt((""));
	}
	for (i=0; header_message[i]!=NULL; i++)
		fprintf(stderr,"%s",header_message[i]);
	add_suffs(argc,argv);
	if ((gc=basic_alloc(sizeof(GIF_CODER)))==NULL
		|| (gb11=basic_alloc(sizeof(GB11_CODER)))==NULL)
		uhalt(("unable to allocate enough memory to start up"));
	for (i=1; i<argc; i++)
		gifblast(argv[i]);
}
/* DELETE_LINE
END_OF_FILE
 DELETE_LINE */