diff options
Diffstat (limited to 'vendor/x11iraf/ximtool/gifio.c')
| -rw-r--r-- | vendor/x11iraf/ximtool/gifio.c | 1325 |
1 files changed, 1325 insertions, 0 deletions
diff --git a/vendor/x11iraf/ximtool/gifio.c b/vendor/x11iraf/ximtool/gifio.c new file mode 100644 index 00000000..de81085b --- /dev/null +++ b/vendor/x11iraf/ximtool/gifio.c @@ -0,0 +1,1325 @@ +/* + * GIFIO.C -- Routines to load and save simple GIF files. + * + * ival = isGIF (fname) + * loadGIF (fname, pixels, pixtype, w,h, r,g,b, ncolors) + * writeGIF (fp, pixels, pixtype, w,h, r,g,b, ncolors, gray) + + * LoadGIF(fname, numcols) - loads a GIF file + * WriteGIF(fp, pic, w, h, rmap, gmap, bmap, numcols) + * + * isGIF -- returns nonzero if the named file is a GIF file. + * loadGIF -- reads a GIF file and returns the decoded pixel array and gray- + * scale 8 bit colormap. The caller is responsible for freeing + * the pixels buffer. + * writeGIF -- performs the converse operation, writing the given pixel array + * and colormap to the output GIF file. + * + * Based on GIFENCOD by David Rowley <mgardi@watdscu.waterloo.edu>.A + * Lempel-Zim compression based on "compress". + */ + +#include <stdio.h> +#include <math.h> + + +/* a code_int must be able to hold 2**GIFBITS values of type int, and also -1 + */ +typedef int code_int; +typedef long int count_int; +typedef unsigned char byte; +#ifndef AIXV3 +#ifndef OSF1 +typedef unsigned char uchar; +#endif +#endif + +#define MAXCOLORS 256 +#define TRUE 1 +#define FALSE 0 + +#define CM_RED 0 +#define CM_GREEN 1 +#define CM_BLUE 2 + +#define GIFBITS 12 + +#define INTERLACE 0x40 +#define LOCALCOLORMAP 0x80 + +#define BitSet(byte, bit) (((byte) & (bit)) == (bit)) +#define ReadOK(file,buffer,len) (fread(buffer, len, 1, file) != 0) +#define LM_to_uint(a,b) (((b)<<8)|(a)) + +static struct { + unsigned int Width; + unsigned int Height; + unsigned int BitPixel; + unsigned int ColorResolution; + unsigned int Background; + unsigned int AspectRatio; +} GifScreen; + +static struct { + int transparent; + int delayTime; + int inputFlag; + int disposal; +} Gif89 = { + -1, -1, -1, 0 }; + + + +/* MONO returns total intensity of r,g,b components */ +#define MONO(rd,gn,bl) (((rd)*11 + (gn)*16 + (bl)*5) >> 5) /*.33R+ .5G+ .17B*/ + + +/* Function prototypes */ +#ifdef __STDC__ + +#include <stddef.h> +#include <stdlib.h> + +static int colorstobpp (int colors); +static int GetPixel (int x, int y); +static void BumpPixel (void); +static int GIFNextPixel (); +static void GIFEncode (FILE* fp, int GWidth, int GHeight, int GInterlace, + int Background, int BitsPerPixel, int Red[], int Green[], int Blue[]); +static void Putword (int w, FILE* fp); +static void compress (int init_bits, FILE* outfile); +static void output (code_int code); +static void cl_block (void); +static void cl_hash (count_int hsize); +static void writeerr (void); +static void char_init (void); +static void char_out (int c); +static void flush_char (void); + +static char *ReadGIF (FILE *fd, int imageNumber, uchar **pix, int *nx, int *ny, + uchar *r, uchar *g, uchar *b, int *ncolors); +static int ReadColorMap (FILE *fd, int number, uchar *r, uchar *g, uchar *b ); +static int DoExtension (FILE *fd, int label ); +static int GetDataBlock (FILE *fd, uchar *buf ); +static int GetCode (FILE *fd, int code_size, int flag ); +static int LWZReadByte (FILE *fd, int flag, int input_code_size ); +static char *ReadImage (FILE *fd, int len, int height, + int interlace, int ignore, uchar **image ); + +#else +static int colorstobpp(), GIFNextPixel(); +static void BumpPixel (), GIFEncode (), Putword (), compress (); +static void output (), cl_block (), cl_hash (), writeerr (), char_init (); +static void char_out (), flush_char (); + +static char *ReadGIF (), *ReadImage (); +static int ReadColorMap (), DoExtension (), GetDataBlock (); +static int GetCode (), LWZReadByte (); +#endif + +static byte *pixels; +static int nrows, ncols; +static char *errstr = NULL; + + +/* ---------------- + * Public routines. + * ----------------*/ + + +/* loadGIF - Load a GIF file. + */ + +char * +loadGIF (fname, pix, nx, ny, r,g,b, ncolors, gray) +char *fname; /* input filename */ +uchar **pix; /* output pixels */ +int *nx, *ny; /* dimensions */ +uchar *r, *g, *b; /* colormap */ +int *ncolors; /* number of colors */ +int gray; /* read as a grayscale? */ +{ + register FILE *fd; + register int i, imageNumber = 1; + + if ((fd = fopen(fname, "rb")) == NULL) + return "Unable to open FITS file"; + + for (i=0; i < 256; i++) + r[i] = g[i] = b[i] = 0; + + errstr = ReadGIF(fd, imageNumber, pix, nx, ny, r, g, b, ncolors); + + /* If we requested grayscale reset the colormap and pixels. */ + if (gray) + for (i=0; i < 256; i++) + r[i] = g[i] = b[i] = MONO(r[i],g[i],b[i]); + + fclose (fd); + return (errstr); +} + + +/* writeGIF -- Write a GIF image. + */ + +int +writeGIF (fp, image, w, h, rmap, gmap, bmap, numcols, gray) +FILE *fp; /* output file descriptor */ +byte *image; /* image pixels */ +int w, h; /* image dimensions */ +byte *rmap, *gmap, *bmap; /* colormap */ +int numcols; /* number of colors */ +int gray; /* save as grayscale? */ +{ + register int i, bpp, npix; + int r[MAXCOLORS], g[MAXCOLORS], b[MAXCOLORS]; + + /* Change type of the colormap. */ + if (gray) + for (i = 0; i < MAXCOLORS; i++) + r[i] = g[i] = b[i] = (int) MONO(rmap[i],gmap[i],bmap[i]); + else + for (i = 0; i < MAXCOLORS; i++) { + r[i] = (int) rmap[i]; + g[i] = (int) gmap[i]; + b[i] = (int) bmap[i]; + } + bpp = colorstobpp (numcols); + + /* Load the pixel buffer */ + npix = w * h; + ncols = w; + nrows = h; + pixels = (byte *) malloc (npix * sizeof(byte)); + for (i = 0; i < npix; i++) + pixels[i] = image[i]; + + /* All set, write it out. */ + GIFEncode (fp, w, h, 0, 0, bpp, r, g, b); + + /* Clean up. */ + free ((byte *)pixels); +} + + +/* IsGIF -- Test a file to see if it is a GIF file. + */ +int +isGIF (fname) +char *fname; /* input filename */ +{ + register FILE *fp; + int value = 0; + char tag[5]; + + if (fp = fopen (fname, "r")) { + fread (tag, sizeof(char), 4, fp); + if (strncmp ("GIF8", tag, 4) == 0) + value = 1; + fclose (fp); + } + return value; +} + + +/* getGIFHdr -- Get some set of header information for the GUI. + */ + +char * +getGIFHdr (fname) +char *fname; +{ + FILE *fp; + char *line; + uchar buf[16], version[4]; + int nx, ny, ncolors; + + + /* Open the image. */ + fp = fopen (fname, "r"); + if (!fp) + return NULL; + + /* Get the version. */ + if (!ReadOK(fp, buf, 6) || strncmp(buf, "GIF", 3) != 0) + return NULL; + strncpy(version, buf + 3, 3); + version[3] = '\0'; + + + /* Read the image header. */ + if (!ReadOK(fp, buf, 7)) + return NULL; + nx = LM_to_uint(buf[0], buf[1]); + ny = LM_to_uint(buf[2], buf[3]); + ncolors = 2 << (buf[4] & 0x07); + + /* Format the description. */ + line = (char *) malloc (80); + sprintf (line, "%-16.16s 8 %5dx%-5d GIF%s Image (%d colors)", + fname, nx, ny, version, ncolors); + + fclose (fp); + return (line); +} + + + +/* ------------------ + * Private Procedures + * ------------------*/ + + +/* COLORSTOBPP -- Convert the numbers of colors we're writing to a + * bits-per-pixel value. + */ +static int +colorstobpp (colors) +int colors; +{ + int bpp; + + if (colors <= 2) + bpp = 1; + else if (colors <= 4) + bpp = 2; + else if (colors <= 8) + bpp = 3; + else if (colors <= 16) + bpp = 4; + else if (colors <= 32) + bpp = 5; + else if (colors <= 64) + bpp = 6; + else if (colors <= 128) + bpp = 7; + else if (colors <= 256) + bpp = 8; + else + perror ("can't happen"); + + return bpp; +} + + + +/*---------------------- + * GIF Input Procedures + *----------------------*/ + + +/* +-------------------------------------------------------------------+ + * | Copyright 1990, David Koblas. | + * | Permission to use, copy, modify, and distribute this software | + * | and its documentation for any purpose and without fee is hereby | + * | granted, provided that the above copyright notice appear in all | + * | copies and that both that copyright notice and this permission | + * | notice appear in supporting documentation. This software is | + * | provided "as is" without express or implied warranty. | + * +-------------------------------------------------------------------+ + */ + + +static char * +ReadGIF(fd, imageNumber, pix, nx, ny, r, g, b, ncolors) +FILE *fd; +int imageNumber; +uchar **pix; +int *nx, *ny; +uchar *r, *g, *b; +int *ncolors; +{ + uchar buf[16]; + uchar c; + int useGlobalColormap; + int bitPixel; + int imageCount = 0; + char version[4]; + + if (!ReadOK(fd, buf, 6)) + return "error reading magic number"; + + if (strncmp(buf, "GIF", 3) != 0) + return "not a GIF file"; + + strncpy(version, buf + 3, 3); + version[3] = '\0'; + + if ((strcmp(version, "87a") != 0) && (strcmp(version, "89a") != 0)) + return "bad version number, not '87a' or '89a'"; + + if (!ReadOK(fd, buf, 7)) + return "failed to read screen descriptor"; + + *nx = GifScreen.Width = LM_to_uint(buf[0], buf[1]); + *ny = GifScreen.Height = LM_to_uint(buf[2], buf[3]); + *ncolors = GifScreen.BitPixel = 2 << (buf[4] & 0x07); + GifScreen.ColorResolution = (((buf[4] & 0x70) >> 3) + 1); + GifScreen.Background = buf[5]; + GifScreen.AspectRatio = buf[6]; + + if (BitSet(buf[4], LOCALCOLORMAP)) { /* Global Colormap */ + if (ReadColorMap(fd, *ncolors, r, g, b)) + return "error reading global colormap"; + } + + if (GifScreen.AspectRatio != 0 && GifScreen.AspectRatio != 49) { + float r; + r = ( (float) GifScreen.AspectRatio + 15.0 ) / 64.0; + } + + for (; ; ) { + if (!ReadOK(fd, &c, 1)) + return "EOF / read error on image data"; + + if (c == ';') { /* GIF terminator */ + if (imageCount < imageNumber) + return "requested image number not found"; + return; + } + + if (c == '!') { /* Extension */ + if (!ReadOK(fd, &c, 1)) + return "OF / read error on extention function code"; + DoExtension(fd, c); + continue; + } + + if (c != ',') /* Not a valid start character */ + continue; + + ++imageCount; + + if (!ReadOK(fd, buf, 9)) + return "couldn't read left/top/width/height"; + + useGlobalColormap = !BitSet(buf[8], LOCALCOLORMAP); + + bitPixel = 1 << ((buf[8] & 0x07) + 1); + + if (!useGlobalColormap) { + if (ReadColorMap(fd, bitPixel, r, g, b)) + return "error reading local colormap"; + return (ReadImage(fd, LM_to_uint(buf[4], buf[5]), + LM_to_uint(buf[6], buf[7]), BitSet(buf[8], INTERLACE), + imageCount != imageNumber, pix )); + } else { + return (ReadImage(fd, LM_to_uint(buf[4], buf[5]), + LM_to_uint(buf[6], buf[7]), BitSet(buf[8], INTERLACE), + imageCount != imageNumber, pix )); + } + + } +} + + +static int +ReadColorMap(fd, number, r, g, b) +FILE *fd; +int number; +uchar *r, *g, *b; +{ + int i; + uchar rgb[3]; + + for (i = 0; i < number; ++i) { + if (!ReadOK(fd, rgb, sizeof(rgb))) + return TRUE; + + r[i] = rgb[0] ; + g[i] = rgb[1] ; + b[i] = rgb[2] ; + } + return FALSE; +} + + +static int +DoExtension(fd, label) +FILE *fd; +int label; +{ + static char buf[256]; + char *str; + + switch (label) { + case 0x01: /* Plain Text Extension */ + str = "Plain Text Extension"; + break; + case 0xff: /* Application Extension */ + str = "Application Extension"; + break; + case 0xfe: /* Comment Extension */ + str = "Comment Extension"; + while (GetDataBlock(fd, (uchar * ) buf) != 0) + ; + return FALSE; + case 0xf9: /* Graphic Control Extension */ + str = "Graphic Control Extension"; + (void) GetDataBlock(fd, (uchar * ) buf); + Gif89.disposal = (buf[0] >> 2) & 0x7; + Gif89.inputFlag = (buf[0] >> 1) & 0x1; + Gif89.delayTime = LM_to_uint(buf[1], buf[2]); + if ((buf[0] & 0x1) != 0) + Gif89.transparent = buf[3]; + + while (GetDataBlock(fd, (uchar * ) buf) != 0) + ; + return FALSE; + default: + str = buf; + sprintf(buf, "UNKNOWN (0x%02x)", label); + break; + } + + while (GetDataBlock(fd, (uchar * ) buf) != 0) ; + + return FALSE; +} + + +static int ZeroDataBlock = FALSE; + +static int +GetDataBlock(fd, buf) +FILE *fd; +uchar *buf; +{ + uchar count; + + if (!ReadOK(fd, &count, 1)) + return - 1; + + ZeroDataBlock = count == 0; + + if ((count != 0) && (!ReadOK(fd, buf, count))) + return - 1; + + return count; +} + + +static int +GetCode(fd, code_size, flag) +FILE *fd; +int code_size; +int flag; +{ + static uchar buf[280]; + static int curbit, lastbit, done, last_byte; + int i, j, ret; + uchar count; + + if (flag) { + curbit = 0; + lastbit = 0; + done = FALSE; + return 0; + } + + if ( (curbit + code_size) >= lastbit) { + if (done) + return - 1; + buf[0] = buf[last_byte-2]; + buf[1] = buf[last_byte-1]; + + if ((count = GetDataBlock(fd, &buf[2])) == 0) + done = TRUE; + + last_byte = 2 + count; + curbit = (curbit - lastbit) + 16; + lastbit = (2 + count) * 8 ; + } + + ret = 0; + for (i = curbit, j = 0; j < code_size; ++i, ++j) + ret |= ((buf[ i / 8 ] & (1 << (i % 8))) != 0) << j; + + curbit += code_size; + + return ret; +} + + +static int +LWZReadByte(fd, flag, input_code_size) +FILE *fd; +int flag; +int input_code_size; +{ + static int fresh = FALSE; + int code, incode; + static int code_size, set_code_size; + static int max_code, max_code_size; + static int firstcode, oldcode; + static int clear_code, end_code; + static int table[2][(1<< GIFBITS)]; + static int stack[(1<<(GIFBITS))*2], *sp; + register int i; + + if (flag) { + set_code_size = input_code_size; + code_size = set_code_size + 1; + clear_code = 1 << set_code_size ; + end_code = clear_code + 1; + max_code_size = 2 * clear_code; + max_code = clear_code + 2; + + GetCode(fd, 0, TRUE); + + fresh = TRUE; + + for (i = 0; i < clear_code; ++i) { + table[0][i] = 0; + table[1][i] = i; + } + for (; i < (1 << GIFBITS); ++i) + table[0][i] = table[1][0] = 0; + + sp = stack; + + return 0; + } else if (fresh) { + fresh = FALSE; + do { + firstcode = oldcode = + GetCode(fd, code_size, FALSE); + } while (firstcode == clear_code); + return firstcode; + } + + if (sp > stack) + return * --sp; + + while ((code = GetCode(fd, code_size, FALSE)) >= 0) { + if (code == clear_code) { + for (i = 0; i < clear_code; ++i) { + table[0][i] = 0; + table[1][i] = i; + } + for (; i < (1 << GIFBITS); ++i) + table[0][i] = table[1][i] = 0; + code_size = set_code_size + 1; + max_code_size = 2 * clear_code; + max_code = clear_code + 2; + sp = stack; + firstcode = oldcode = + GetCode(fd, code_size, FALSE); + return firstcode; + } else if (code == end_code) { + int count; + uchar buf[260]; + + if (ZeroDataBlock) + return - 2; + + while ((count = GetDataBlock(fd, buf)) > 0) + ; + + return - 2; + } + + incode = code; + + if (code >= max_code) { + *sp++ = firstcode; + code = oldcode; + } + + while (code >= clear_code) { + *sp++ = table[1][code]; + code = table[0][code]; + } + + *sp++ = firstcode = table[1][code]; + + if ((code = max_code) < (1 << GIFBITS)) { + table[0][code] = oldcode; + table[1][code] = firstcode; + ++max_code; + if ((max_code >= max_code_size) && + (max_code_size < (1 << GIFBITS))) { + max_code_size *= 2; + ++code_size; + } + } + + oldcode = incode; + + if (sp > stack) + return * --sp; + } + return code; +} + + +static char * +ReadImage(fd, len, height, interlace, ignore, image) +FILE *fd; +int len, height; +int interlace, ignore; +uchar **image; +{ + uchar c; + int v; + int xpos = 0, ypos = 0, pass = 0; + + /* Initialize the Compression routines */ + if (!ReadOK(fd, &c, 1)) + return "EOF / read error on image data"; + + if (LWZReadByte(fd, TRUE, c) < 0) + return "error reading image"; + + /* If this is an "uninteresting picture" ignore it. */ + if (ignore) { + while (LWZReadByte(fd, FALSE, c) >= 0) + ; + return; + } + + if ((*image = (uchar *)malloc(len * height)) == NULL) + return "couldn't alloc space for image"; + + while ((v = LWZReadByte(fd, FALSE, c)) >= 0 ) { + (*image)[ypos * len + xpos] = v; + + ++xpos; + if (xpos == len) { + xpos = 0; + if (interlace) { + switch (pass) { + case 0: + case 1: + ypos += 8; + break; + case 2: + ypos += 4; + break; + case 3: + ypos += 2; + break; + } + + if (ypos >= height) { + ++pass; + switch (pass) { + case 1: + ypos = 4; + break; + case 2: + ypos = 2; + break; + case 3: + ypos = 1; + break; + default: + goto fini; + } + } + } else { + ++ypos; + } + } + if (ypos >= height) + break; + } + +fini: + return NULL; +} + + + +/*----------------------- + * GIF Output Procedures + *-----------------------*/ + +/***************************************************************************** + * + * GIFENCODE.C - GIF Image compression interface + * + * GIFEncode (FName, GHeight, GWidth, GInterlace, Background, + * BitsPerPixel, Red, Green, Blue) + * + *****************************************************************************/ + +#define TRUE 1 +#define FALSE 0 + +static int Width, Height; +static int curx, cury; +static long CountDown; +static int Pass = 0; +static int Interlace; + + + +static void +GIFEncode (fp, GWidth, GHeight, GInterlace, Background, +BitsPerPixel, Red, Green, Blue) + +FILE*fp; +int GWidth, GHeight; +int GInterlace; +int Background; +int BitsPerPixel; +int Red[], Green[], Blue[]; +{ + int B; + int RWidth, RHeight; + int LeftOfs, TopOfs; + int Resolution; + int ColorMapSize; + int InitCodeSize; + int i; + + Interlace = GInterlace; + + ColorMapSize = 1 << BitsPerPixel; + + RWidth = Width = GWidth; + RHeight = Height = GHeight; + LeftOfs = TopOfs = 0; + + Resolution = BitsPerPixel; + + /* Calculate number of bits we are expecting */ + CountDown = (long)Width * (long)Height; + + /* Indicate which pass we are on (if interlace) */ + Pass = 0; + + /* The initial code size */ + if (BitsPerPixel <= 1) + InitCodeSize = 2; + else + InitCodeSize = BitsPerPixel; + + /* Set up the current x and y position */ + curx = cury = 0; + + /* Write the Magic header */ + fwrite ("GIF87a", 1, 6, fp); + + /* Write out the screen width and height */ + Putword (RWidth, fp); + Putword (RHeight, fp); + + /* Indicate that there is a global colour map */ + B = 0x80; /* Yes, there is a color map */ + + /* OR in the resolution */ + B |= (Resolution - 1) << 5; + + /* OR in the Bits per Pixel */ + B |= (BitsPerPixel - 1); + + /* Write it out */ + fputc (B, fp); + + /* Write out the Background colour */ + fputc (Background, fp); + + /* Byte of 0's (future expansion) */ + fputc (0, fp); + + /* Write out the Global Colour Map */ + for (i = 0; i < ColorMapSize; ++i) { + fputc (Red[i], fp); + fputc (Green[i], fp); + fputc (Blue[i], fp); + } + + /* Write an Image separator */ + fputc (',', fp); + + /* Write the Image header */ + Putword (LeftOfs, fp); + Putword (TopOfs, fp); + Putword (Width, fp); + Putword (Height, fp); + + /* Write out whether or not the image is interlaced */ + if (Interlace) + fputc (0x40, fp); + else + fputc (0x00, fp); + + /* Write out the initial code size */ + fputc (InitCodeSize, fp); + + /* Go and actually compress the data */ + compress (InitCodeSize + 1, fp); + + /* Write out a Zero-length packet (to end the series) */ + fputc (0, fp); + + /* Write the GIF file terminator */ + fputc (';', fp); +} + + +/* Bump the 'curx' and 'cury' to point to the next pixel + */ +static void +BumpPixel() +{ + /* Bump the current X position */ + ++curx; + + /* If we are at the end of a scan line, set curx back to the beginning + * If we are interlaced, bump the cury to the appropriate spot, + * otherwise, just increment it. + */ + if (curx == Width) { + curx = 0; + + if (!Interlace) + ++cury; + else { + switch (Pass) { + case 0: + cury += 8; + if (cury >= Height) { + ++Pass; + cury = 4; + } + break; + case 1: + cury += 8; + if (cury >= Height) { + ++Pass; + cury = 2; + } + break; + case 2: + cury += 4; + if (cury >= Height) { + ++Pass; + cury = 1; + } + break; + case 3: + cury += 2; + break; + } + } + } +} + + +/* Return the next pixel from the image + */ +static int +GIFNextPixel () +{ + int r; + + if (CountDown == 0) + return EOF; + + --CountDown; + r = (int) pixels[ cury * ncols + curx ] ; + BumpPixel(); + return r; +} + + +/* Write out a word to the GIF file + */ +static void +Putword (w, fp) +int w; +FILE*fp; +{ + fputc (w & 0xff, fp); + fputc ((w / 256) & 0xff, fp); +} + + +/*************************************************************************** + * + * GIFCOMPR.C - GIF Image compression routines + * + * Lempel-Ziv compression based on 'compress'. GIF modifications by + * David Rowley (mgardi@watdcsu.waterloo.edu) + * + ***************************************************************************/ + +/* + * General DEFINEs + */ + +#define GIFBITS 12 +#define HSIZE 5003 /* 80% occupancy */ + +#ifdef NO_UCHAR +typedef char char_type; +#else /*NO_UCHAR*/ +typedef unsigned char char_type; +#endif /*NO_UCHAR*/ + +/* + * + * GIF Image compression - modified 'compress' + * + * Based on: compress.c - File compression ala IEEE Computer, June 1984. + * + * By Authors: Spencer W. Thomas (decvax!harpo!utah-cs!utah-gr!thomas) + * Jim McKie (decvax!mcvax!jim) + * Steve Davies (decvax!vax135!petsd!peora!srd) + * Ken Turkowski (decvax!decwrl!turtlevax!ken) + * James A. Woods (decvax!ihnp4!ames!jaw) + * Joe Orost (decvax!vax135!petsd!joe) + * + */ +#include <ctype.h> + +#define ARGVAL() (*++(*argv) || (--argc && *++argv)) + +static int n_bits; /* number of bits/code */ +static int maxbits = GIFBITS; /* user settable max # bits/code */ +static code_int maxcode; /* maximum code, given n_bits */ + /* should NEVER generate this code */ +static code_int maxmaxcode = (code_int) 1 << GIFBITS; +#ifdef COMPATIBLE /* But wrong! */ +# define MAXCODE(n_bits) ((code_int) 1 << (n_bits) - 1) +#else /*COMPATIBLE*/ +# define MAXCODE(n_bits) (((code_int) 1 << (n_bits)) - 1) +#endif /*COMPATIBLE*/ + +static count_int htab [HSIZE]; +static unsigned short codetab [HSIZE]; +#define HashTabOf(i) htab[i] +#define CodeTabOf(i) codetab[i] + +/*static*/ code_int hsize = HSIZE; /* for dynamic table sizing */ + +/* To save much memory, we overlay the table used by compress() with those + * used by decompress(). The tab_prefix table is the same size and type + * as the codetab. The tab_suffix table needs 2**GIFBITS characters. We + * get this from the beginning of htab. The output stack uses the rest + * of htab, and contains characters. There is plenty of room for any + * possible stack (stack used to be 8000 characters). + */ + +#define tab_prefixof(i) CodeTabOf(i) +#define tab_suffixof(i) ((char_type*)(htab))[i] +#define de_stack ((char_type*)&tab_suffixof((code_int)1<<GIFBITS)) + +static code_int free_ent = 0; /* first unused entry */ + +/* + * block compression parameters -- after all codes are used up, + * and compression rate changes, start over. + */ +static int clear_flg = 0; + +static int offset; +static long int in_count = 1; /* length of input */ +static long int out_count = 0; /* # of codes output (for debugging) */ + +/* + * compress stdin to stdout + * + * Algorithm: use open addressing double hashing (no chaining) on the + * prefix code / next character combination. We do a variant of Knuth's + * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime + * secondary probe. Here, the modular division first probe is gives way + * to a faster exclusive-or manipulation. Also do block compression with + * an adaptive reset, whereby the code table is cleared when the compression + * ratio decreases, but after the table fills. The variable-length output + * codes are re-sized at this point, and a special CLEAR code is generated + * for the decompressor. Late addition: construct the table according to + * file size for noticeable speed improvement on small files. Please direct + * questions about this implementation to ames!jaw. + */ + +static int g_init_bits; +static FILE *g_outfile; + +static int ClearCode; +static int EOFCode; + +static unsigned long cur_accum = 0; +static int cur_bits = 0; +static unsigned long masks[] = { + 0x0000, 0x0001, 0x0003, 0x0007, 0x000F, + 0x001F, 0x003F, 0x007F, 0x00FF, + 0x01FF, 0x03FF, 0x07FF, 0x0FFF, + 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF }; + +static int a_count; /* Number of characters so far in this 'packet' */ +static char accum[ 256 ]; /* Define the storage for the packet accumulator */ + +static void +compress (init_bits, outfile) +int init_bits; +FILE*outfile; +{ + register long fcode; + register code_int i /* = 0 */; + register int c; + register code_int ent; + register code_int disp; + register code_int hsize_reg; + register int hshift; + + /* + * Set up the globals: g_init_bits - initial number of bits + * g_outfile - pointer to output file + */ + g_init_bits = init_bits; + g_outfile = outfile; + + /* + * Set up the necessary values + */ + offset = 0; + out_count = 0; + clear_flg = 0; + cur_accum = 0; + cur_bits = 0; + in_count = 1; + maxbits = GIFBITS; + maxcode = MAXCODE(n_bits = g_init_bits); + + ClearCode = (1 << (init_bits - 1)); + EOFCode = ClearCode + 1; + free_ent = ClearCode + 2; + + char_init(); + for (i=0; i<HSIZE; i++) { + htab[i] = 0; + codetab[i] = 0; + } + + ent = GIFNextPixel (); + + hshift = 0; + for (fcode = (long) hsize; fcode < 65536L; fcode *= 2L) + ++hshift; + hshift = 8 - hshift; /* set hash code range bound */ + + hsize_reg = hsize; + cl_hash ((count_int) hsize_reg); /* clear hash table */ + + output ((code_int)ClearCode); + + while ((c = GIFNextPixel ()) != EOF) { + + ++in_count; + + fcode = (long) (((long) c << maxbits) + ent); + i = (((code_int)c << hshift) ^ ent); /* xor hashing */ + + if (HashTabOf (i) == fcode) { + ent = CodeTabOf (i); + continue; + } else if ((long)HashTabOf (i) < 0) /* empty slot */ + goto nomatch; + disp = hsize_reg - i; /* secondary hash (after G. Knott) */ + if (i == 0) + disp = 1; +probe: + if ((i -= disp) < 0) + i += hsize_reg; + + if (HashTabOf (i) == fcode) { + ent = CodeTabOf (i); + continue; + } + if ((long)HashTabOf (i) > 0) + goto probe; +nomatch: + output ((code_int) ent); + ++out_count; + ent = c; + if (free_ent < maxmaxcode) { /* } */ + CodeTabOf (i) = free_ent++; /* code -> hashtable */ + HashTabOf (i) = fcode; + } else + cl_block(); + } + + /* + * Put out the final code. + */ + output ((code_int)ent); + ++out_count; + output ((code_int) EOFCode); +} + +/***************************************************************** + * TAG (output) + * + * Output the given code. + * Inputs: + * code: A n_bits-bit integer. If == -1, then EOF. This assumes + * that n_bits =< (long)wordsize - 1. + * Outputs: + * Outputs code to the file. + * Assumptions: + * Chars are 8 bits long. + * Algorithm: + * Maintain a GIFBITS character long buffer (so that 8 codes will + * fit in it exactly). Use the VAX insv instruction to insert each + * code in turn. When the buffer fills up empty it and start over. + */ + + +static void +output (code) +code_int code; +{ + cur_accum &= masks[ cur_bits ]; + + if (cur_bits > 0) + cur_accum |= ((long)code << cur_bits); + else + cur_accum = code; + + cur_bits += n_bits; + + while (cur_bits >= 8) { + char_out ((unsigned int)(cur_accum & 0xff)); + cur_accum >>= 8; + cur_bits -= 8; + } + + /* + * If the next entry is going to be too big for the code size, + * then increase it, if possible. + */ + if (free_ent > maxcode || clear_flg) { + + if (clear_flg) { + maxcode = MAXCODE (n_bits = g_init_bits); + clear_flg = 0; + } else { + ++n_bits; + if (n_bits == maxbits) + maxcode = maxmaxcode; + else + maxcode = MAXCODE(n_bits); + } + } + + if (code == EOFCode) { + /* At EOF, write the rest of the buffer. */ + while (cur_bits > 0) { + char_out ((unsigned int)(cur_accum & 0xff)); + cur_accum >>= 8; + cur_bits -= 8; + } + flush_char(); + fflush (g_outfile); + if (ferror (g_outfile)) + writeerr(); + } +} + + +/* + * Clear out the hash table + */ +static void +cl_block () /* table clear for block compress */ +{ + + cl_hash ((count_int) hsize); + free_ent = ClearCode + 2; + clear_flg = 1; + + output ((code_int)ClearCode); +} + +static void +cl_hash(hsize) /* reset code table */ +register count_int hsize; +{ + + register count_int *htab_p = htab + hsize; + + register long i; + register long m1 = -1; + + i = hsize - 16; + do { /* might use Sys V memset(3) here */ + *(htab_p - 16) = m1; + *(htab_p - 15) = m1; + *(htab_p - 14) = m1; + *(htab_p - 13) = m1; + *(htab_p - 12) = m1; + *(htab_p - 11) = m1; + *(htab_p - 10) = m1; + *(htab_p - 9) = m1; + *(htab_p - 8) = m1; + *(htab_p - 7) = m1; + *(htab_p - 6) = m1; + *(htab_p - 5) = m1; + *(htab_p - 4) = m1; + *(htab_p - 3) = m1; + *(htab_p - 2) = m1; + *(htab_p - 1) = m1; + htab_p -= 16; + } while ((i -= 16) >= 0); + + for (i += 16; i > 0; --i) + *--htab_p = m1; +} + +static void +writeerr() +{ + perror ("error writing output file"); +} + + +/****************************************************************************** + * + * GIF Specific routines + * + ******************************************************************************/ + + +/* Set up the 'byte output' routine + */ +static void +char_init() +{ + register int i; + + a_count = 0; + for (i=0; i<256; i++) + accum[i] = 0; +} + + +/* + * Add a character to the end of the current packet, and if it is 254 + * characters, flush the packet to disk. + */ +static void +char_out (c) +int c; +{ + accum[ a_count++ ] = c; + if (a_count >= 254) + flush_char(); +} + +/* + * Flush the packet to disk, and reset the accumulator + */ +static void +flush_char() +{ + if (a_count > 0) { + fputc (a_count, g_outfile); + fwrite (accum, 1, a_count, g_outfile); + a_count = 0; + } +} |