phillips@cs.ubc.ca (George Phillips) (09/07/90)
And here's part 2 ...
#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create the files:
# decoder.c
# newsmap.c
# floydstein.c
# errs.h
# std.h
# mem_image.h
# newsmap.h
# imgfile.h
# This archive created: Thu Sep 6 22:51:24 1990
export PATH; PATH=/bin:$PATH
echo shar: extracting "'decoder.c'" '(11341 characters)'
if test -f 'decoder.c'
then
echo shar: will not over-write existing file "'decoder.c'"
else
sed 's/^X//' << \SHAR_EOF > 'decoder.c'
X/* DECODE.C - An LZW decoder for GIF
X * Copyright (C) 1987, by Steven A. Bennett
X *
X * Permission is given by the author to freely redistribute and include
X * this code in any program as long as this credit is given where due.
X *
X * In accordance with the above, I want to credit Steve Wilhite who wrote
X * the code which this is heavily inspired by...
X *
X * GIF and 'Graphics Interchange Format' are trademarks (tm) of
X * Compuserve, Incorporated, an H&R Block Company.
X *
X * Release Notes: This file contains a decoder routine for GIF images
X * which is similar, structurally, to the original routine by Steve Wilhite.
X * It is, however, somewhat noticably faster in most cases.
X *
X * GWP: I've hacked this around to make a somewhat cleaner interface...
X */
X
X#include <stdio.h>
X
X#include "std.h"
X#include "errs.h"
X
X#include "mem_image.h"
X
XIMPORT TEXT *malloc(); /* Standard C library allocation */
X
X/* IMPORT INT get_byte()
X *
X * - This external (machine specific) function is expected to return
X * either the next byte from the GIF file, or a negative number, as
X * defined in ERRS.H.
X */
XIMPORT INT get_byte();
X
X/* IMPORT INT out_line(pixels, linelen)
X * UBYTE pixels[];
X * INT linelen;
X *
X * - This function takes a full line of pixels (one byte per pixel) and
X * displays them (or does whatever your program wants with them...). It
X * should return zero, or negative if an error or some other event occurs
X * which would require aborting the decode process... Note that the length
X * passed will almost always be equal to the line length passed to the
X * decoder function, with the sole exception occurring when an ending code
X * occurs in an odd place in the GIF file... In any case, linelen will be
X * equal to the number of pixels passed...
X */
Xextern char* out_line();
X
X/* IMPORT INT bad_code_count;
X *
X * This value is the only other global required by the using program, and
X * is incremented each time an out of range code is read by the decoder.
X * When this value is non-zero after a decode, your GIF file is probably
X * corrupt in some way...
X */
XIMPORT INT bad_code_count;
X
X#define MAX_CODES 4095
X
X/* Static variables */
XLOCAL WORD curr_size; /* The current code size */
XLOCAL WORD clear; /* Value for a clear code */
XLOCAL WORD ending; /* Value for a ending code */
XLOCAL WORD newcodes; /* First available code */
XLOCAL WORD top_slot; /* Highest code for current size */
XLOCAL WORD slot; /* Last read code */
X
X/* The following static variables are used
X * for seperating out codes
X */
XLOCAL WORD navail_bytes = 0; /* # bytes left in block */
XLOCAL WORD nbits_left = 0; /* # bits left in current byte */
XLOCAL UTINY b1; /* Current byte */
XLOCAL UTINY byte_buff[257]; /* Current block */
XLOCAL UTINY *pbytes; /* Pointer to next byte in block */
X
XLOCAL LONG code_mask[13] = {
X 0,
X 0x0001, 0x0003,
X 0x0007, 0x000F,
X 0x001F, 0x003F,
X 0x007F, 0x00FF,
X 0x01FF, 0x03FF,
X 0x07FF, 0x0FFF
X };
X
X
X/* This function initializes the decoder for reading a new image.
X */
XLOCAL WORD init_exp(size)
X WORD size;
X {
X curr_size = size + 1;
X top_slot = 1 << curr_size;
X clear = 1 << size;
X ending = clear + 1;
X slot = newcodes = ending + 1;
X navail_bytes = nbits_left = 0;
X return(0);
X }
X
X/* get_next_code()
X * - gets the next code from the GIF file. Returns the code, or else
X * a negative number in case of file errors...
X */
XLOCAL WORD get_next_code(fp)
XFILE* fp;
X {
X WORD i, x;
X ULONG ret;
X
X if (nbits_left == 0)
X {
X if (navail_bytes <= 0)
X {
X
X /* Out of bytes in current block, so read next block
X */
X pbytes = byte_buff;
X if ((navail_bytes = fgetc(fp)) == EOF)
X return(READ_ERROR);
X else if (navail_bytes)
X {
X if (fread(byte_buff, navail_bytes, 1, fp) != 1)
X return(READ_ERROR);
X }
X }
X b1 = *pbytes++;
X nbits_left = 8;
X --navail_bytes;
X }
X
X ret = b1 >> (8 - nbits_left);
X while (curr_size > nbits_left)
X {
X if (navail_bytes <= 0)
X {
X
X /* Out of bytes in current block, so read next block
X */
X pbytes = byte_buff;
X if ((navail_bytes = fgetc(fp)) == EOF)
X return(READ_ERROR);
X else if (navail_bytes)
X {
X if (fread(byte_buff, navail_bytes, 1, fp) != 1)
X return(READ_ERROR);
X }
X }
X b1 = *pbytes++;
X ret |= b1 << nbits_left;
X nbits_left += 8;
X --navail_bytes;
X }
X nbits_left -= curr_size;
X ret &= code_mask[curr_size];
X return((WORD)(ret));
X }
X
X
X/* The reason we have these seperated like this instead of using
X * a structure like the original Wilhite code did, is because this
X * stuff generally produces significantly faster code when compiled...
X * This code is full of similar speedups... (For a good book on writing
X * C for speed or for space optomisation, see Efficient C by Tom Plum,
X * published by Plum-Hall Associates...)
X */
XLOCAL UTINY stack[MAX_CODES + 1]; /* Stack for storing pixels */
XLOCAL UTINY suffix[MAX_CODES + 1]; /* Suffix table */
XLOCAL UWORD prefix[MAX_CODES + 1]; /* Prefix linked list */
X
X/* WORD decoder(linewidth)
X * WORD linewidth; * Pixels per line of image *
X *
X * - This function decodes an LZW image, according to the method used
X * in the GIF spec. Every *linewidth* "characters" (ie. pixels) decoded
X * will generate a call to out_line(), which is a user specific function
X * to display a line of pixels. The function gets it's codes from
X * get_next_code() which is responsible for reading blocks of data and
X * seperating them into the proper size codes. Finally, get_byte() is
X * the global routine to read the next byte from the GIF file.
X *
X * It is generally a good idea to have linewidth correspond to the actual
X * width of a line (as specified in the Image header) to make your own
X * code a bit simpler, but it isn't absolutely necessary.
X *
X * Returns: 0 if successful, else negative. (See ERRS.H)
X *
X */
X
XWORD decoder(fp, img)
XFILE* fp;
Xstruct mem_image* img;
X {
X FAST UTINY *sp, *bufptr;
X FAST WORD code, fc, oc, bufcnt;
X WORD c, size, ret;
X
X /* Initialize for decoding a new image...
X */
X if ((size = fgetc(fp)) == EOF)
X return(READ_ERROR);
X if (size < 2 || 9 < size)
X return(BAD_CODE_SIZE);
X init_exp(size);
X
X /* Initialize in case they forgot to put in a clear code.
X * (This shouldn't happen, but we'll try and decode it anyway...)
X */
X oc = fc = 0;
X
X /* Set up the stack pointer and decode buffer pointer
X */
X sp = stack;
X bufptr = img->data;
X bufcnt = img->width;
X
X /* This is the main loop. For each code we get we pass through the
X * linked list of prefix codes, pushing the corresponding "character" for
X * each code onto the stack. When the list reaches a single "character"
X * we push that on the stack too, and then start unstacking each
X * character for output in the correct order. Special handling is
X * included for the clear code, and the whole thing ends when we get
X * an ending code.
X */
X while ((c = get_next_code(fp)) != ending)
X {
X
X /* If we had a file error, return without completing the decode
X */
X if (c < 0) {
X return(0);
X }
X
X /* If the code is a clear code, reinitialize all necessary items.
X */
X if (c == clear)
X {
X curr_size = size + 1;
X slot = newcodes;
X top_slot = 1 << curr_size;
X
X /* Continue reading codes until we get a non-clear code
X * (Another unlikely, but possible case...)
X */
X while ((c = get_next_code(fp)) == clear)
X ;
X
X /* If we get an ending code immediately after a clear code
X * (Yet another unlikely case), then break out of the loop.
X */
X if (c == ending)
X break;
X
X /* Finally, if the code is beyond the range of already set codes,
X * (This one had better NOT happen... I have no idea what will
X * result from this, but I doubt it will look good...) then set it
X * to color zero.
X */
X if (c >= slot)
X c = 0;
X
X oc = fc = c;
X
X /* And let us not forget to put the char into the buffer... And
X * if, on the off chance, we were exactly one pixel from the end
X * of the line, we have to send the buffer to the out_line()
X * routine...
X */
X *bufptr++ = c;
X if (--bufcnt == 0)
X {
X bufptr = out_line(img);
X bufcnt = img->width;
X }
X }
X else
X {
X
X /* In this case, it's not a clear code or an ending code, so
X * it must be a code code... So we can now decode the code into
X * a stack of character codes. (Clear as mud, right?)
X */
X code = c;
X
X /* Here we go again with one of those off chances... If, on the
X * off chance, the code we got is beyond the range of those already
X * set up (Another thing which had better NOT happen...) we trick
X * the decoder into thinking it actually got the last code read.
X * (Hmmn... I'm not sure why this works... But it does...)
X */
X if (code >= slot)
X {
X if (code > slot)
X ++bad_code_count;
X code = oc;
X *sp++ = fc;
X }
X
X /* Here we scan back along the linked list of prefixes, pushing
X * helpless characters (ie. suffixes) onto the stack as we do so.
X */
X while (code >= newcodes)
X {
X *sp++ = suffix[code];
X code = prefix[code];
X }
X
X /* Push the last character on the stack, and set up the new
X * prefix and suffix, and if the required slot number is greater
X * than that allowed by the current bit size, increase the bit
X * size. (NOTE - If we are all full, we *don't* save the new
X * suffix and prefix... I'm not certain if this is correct...
X * it might be more proper to overwrite the last code...
X */
X *sp++ = code;
X if (slot < top_slot)
X {
X suffix[slot] = fc = code;
X prefix[slot++] = oc;
X oc = c;
X }
X if (slot >= top_slot)
X if (curr_size < 12)
X {
X top_slot <<= 1;
X ++curr_size;
X }
X
X /* Now that we've pushed the decoded string (in reverse order)
X * onto the stack, lets pop it off and put it into our decode
X * buffer... And when the decode buffer is full, write another
X * line...
X */
X while (sp > stack)
X {
X *bufptr++ = *(--sp);
X if (--bufcnt == 0)
X {
X bufptr = out_line(img);
X bufcnt = img->width;
X }
X }
X }
X }
X ret = 0;
X if (bufcnt != img->width)
X out_line(img); /* buf, (linewidth - bufcnt));*/
X return(ret);
X }
X
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'newsmap.c'" '(2217 characters)'
if test -f 'newsmap.c'
then
echo shar: will not over-write existing file "'newsmap.c'"
else
sed 's/^X//' << \SHAR_EOF > 'newsmap.c'
X/*
X * newsmap.c -- convert an RGB triplet into a nearby value from the
X * NeWS 8 plane colourmap.
X *
X * Note: I could hard code the inverse tables, but this is not so
X * inscrutable in case it should be changed. Besides, the true
X * colour mode could use this information in fitting the colour
X * collisions to a next-best choice.
X */
X
X#include "newsmap.h"
X
X#define gray_base (32)
Xshort gray_level[] = {
X 0, 10, 20, 30, 40, 51, 61, 71, 81, 91, 102, 112, 122, 132,
X 142, 153, 163, 173, 183, 193, 204, 214, 224, 234, 244, 255
X};
X#define gray_run (sizeof(gray_level) / sizeof(short))
X#define gray_black (56)
X#define gray_white (255)
X
X#define colourbase (56)
Xshort red_level[] = { 0, 63, 127, 191, 255 };
Xshort green_level[] = { 0, 36, 72, 109, 145, 182, 218, 255 };
Xshort blue_level[] = { 0, 63, 127, 191, 255 };
X
X#define nreds (sizeof(red_level) / sizeof(short))
X#define ngreens (sizeof(green_level) / sizeof(short))
X#define nblues (sizeof(blue_level) / sizeof(short))
X
Xshort gray_inverse[256];
Xshort red_inverse[256];
Xshort green_inverse[256];
Xshort blue_inverse[256];
X
Xstatic void run_ramp();
X
Xvoid init_newsmap()
X{
X int i;
X
X run_ramp(gray_run, gray_level, gray_inverse);
X for (i = 0; i < 256; i++) {
X if (gray_inverse[i] == 0)
X gray_inverse[i] = gray_black;
X else if (gray_inverse[i] == gray_run - 1)
X gray_inverse[i] = gray_white;
X else
X gray_inverse[i] += gray_base - 1;
X }
X
X run_ramp(ngreens, green_level, green_inverse);
X run_ramp(nreds, red_level, red_inverse);
X for (i = 0; i < 256; i++)
X red_inverse[i] *= ngreens;
X
X run_ramp(nblues, blue_level, blue_inverse);
X for (i = 0; i < 256; i++)
X blue_inverse[i] *= ngreens * nreds;
X}
X
Xstatic void run_ramp(n, level, inverse)
Xint n;
Xshort level[];
Xshort inverse[];
X{
X int i;
X int closest = 0;
X
X for (i = 0; i < 256; i++) {
X if (abs(i - level[closest]) > abs(i - level[closest + 1]))
X closest++;
X inverse[i] = closest;
X if (closest == n - 1)
X break;
X }
X for (; i < 256; i++)
X inverse[i] = closest;
X}
X
Xstatic int abs(n)
Xint n;
X{
X if (n < 0)
X return(-n);
X return(n);
X}
X
Xint rgb2newsmap(r, g, b)
Xint r;
Xint g;
Xint b;
X{
X if (r == g && g == b)
X return(gray_inverse[r]);
X
X return(red_inverse[r] + green_inverse[g] + blue_inverse[b] + colourbase);
X}
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'floydstein.c'" '(5035 characters)'
if test -f 'floydstein.c'
then
echo shar: will not over-write existing file "'floydstein.c'"
else
sed 's/^X//' << \SHAR_EOF > 'floydstein.c'
X/*
X * floydstein.c -- perform Floyd-Steinberg dithering on an in-memory image.
X *
X * This is designed around the NeWS colour map and is for colour mapped
X * images. Beware.
X *
X * This code is based on ppmquant from Jef Poskanzer's PBM+ package which is
X *
X * Copyright (C) 1989 by Jef Poskanzer.
X *
X * Permission to use, copy, modify, and distribute this software and its
X * documentation for any purpose and without fee is hereby granted, provided
X * that the above copyright notice appear in all copies and that both that
X * copyright notice and this permission notice appear in supporting
X * documentation. This software is provided "as is" without express or
X * implied warranty.
X*/
X
X#include <stdio.h>
X#include <malloc.h>
X
X#include "mem_image.h"
X#include "newsmap.h"
X
Xlong* long_alloc();
X
Xunsigned char red[256], green[256], blue[256];
Xunsigned short news_red[256];
Xunsigned short news_green[256];
Xunsigned short news_blue[256];
Xlong *thisrerr, *nextrerr, *thisgerr, *nextgerr, *thisberr, *nextberr;
Xint fs_direction;
X
Xvoid init_floydstein(img)
Xstruct mem_image* img;
X{
X register int col;
X#define FS_SCALE 1024
X int i;
X
X /* Build a local colour map for convenience */
X for (i = 0; i < img->maplen; i++) {
X red[i] = img->colourmap[i] & 255;
X green[i] = (img->colourmap[i] >> 8) & 255;
X blue[i] = (img->colourmap[i] >> 16) & 255;
X }
X
X for (i = 0; i < 256; i++)
X getmcolor(i, news_red + i, news_green + i, news_blue + i);
X
X /* Initialize Floyd-Steinberg error vectors. */
X thisrerr = long_alloc(img->width + 2);
X nextrerr = long_alloc(img->width + 2);
X thisgerr = long_alloc(img->width + 2);
X nextgerr = long_alloc(img->width + 2);
X thisberr = long_alloc(img->width + 2);
X nextberr = long_alloc(img->width + 2);
X
X srand((int)time(0));
X
X for (col = 0; col < img->width + 2; col++) {
X thisrerr[col] = rand() % (FS_SCALE * 2) - FS_SCALE;
X thisgerr[col] = rand() % (FS_SCALE * 2) - FS_SCALE;
X thisberr[col] = rand() % (FS_SCALE * 2) - FS_SCALE;
X /* (random errors in [-1 .. 1]) */
X }
X fs_direction = 1;
X}
X
Xvoid floydstein(img, row)
Xstruct mem_image* img;
Xint row;
X{
X register unsigned char* pP;
X int rows, cols;
X register int col, limitcol;
X long* temperr;
X register long sr, sg, sb;
X int r, g, b;
X#define FS_SCALE 1024
X int err;
X int i;
X
X for (col = 0; col < img->width + 2; col++)
X nextrerr[col] = nextgerr[col] = nextberr[col] = 0;
X
X if (fs_direction ) {
X col = 0;
X limitcol = img->width;
X pP = img->data + row * img->width;
X }
X else {
X col = img->width - 1;
X limitcol = -1;
X pP = img->data + row * img->width + img->width - 1;
X }
X
X do {
X /* Use Floyd-Steinberg errors to adjust actual color. */
X sr = red[*pP] * FS_SCALE + thisrerr[col + 1];
X sg = green[*pP] * FS_SCALE + thisgerr[col + 1];
X sb = blue[*pP] * FS_SCALE + thisberr[col + 1];
X r = sr / FS_SCALE; if (r < 0) r = 0; else if (r > 255) r = 255;
X g = sg / FS_SCALE; if (g < 0) g = 0; else if (g > 255) g = 255;
X b = sb / FS_SCALE; if (b < 0) b = 0; else if (b > 255) b = 255;
X /* just for fun, replace the previous 3 lines with these */
X /*r = (sr / FS_SCALE) & 255;
X g = (sg / FS_SCALE) & 255;
X b = (sb / FS_SCALE) & 255;*/
X *pP = rgb2newsmap(r, g, b);
X
X if (fs_direction) {
X err = sr - news_red[*pP] * FS_SCALE;
X thisrerr[col + 2] += ( err * 7 ) / 16;
X nextrerr[col ] += ( err * 3 ) / 16;
X nextrerr[col + 1] += ( err * 5 ) / 16;
X nextrerr[col + 2] += ( err ) / 16;
X err = sg - news_green[*pP] * FS_SCALE;
X thisgerr[col + 2] += ( err * 7 ) / 16;
X nextgerr[col ] += ( err * 3 ) / 16;
X nextgerr[col + 1] += ( err * 5 ) / 16;
X nextgerr[col + 2] += ( err ) / 16;
X err = sb - news_blue[*pP] * FS_SCALE;
X thisberr[col + 2] += ( err * 7 ) / 16;
X nextberr[col ] += ( err * 3 ) / 16;
X nextberr[col + 1] += ( err * 5 ) / 16;
X nextberr[col + 2] += ( err ) / 16;
X }
X else {
X err = sr - news_red[*pP] * FS_SCALE;
X thisrerr[col ] += ( err * 7 ) / 16;
X nextrerr[col + 2] += ( err * 3 ) / 16;
X nextrerr[col + 1] += ( err * 5 ) / 16;
X nextrerr[col ] += ( err ) / 16;
X err = sg - news_green[*pP] * FS_SCALE;
X thisgerr[col ] += ( err * 7 ) / 16;
X nextgerr[col + 2] += ( err * 3 ) / 16;
X nextgerr[col + 1] += ( err * 5 ) / 16;
X nextgerr[col ] += ( err ) / 16;
X err = sb - news_blue[*pP] * FS_SCALE;
X thisberr[col ] += ( err * 7 ) / 16;
X nextberr[col + 2] += ( err * 3 ) / 16;
X nextberr[col + 1] += ( err * 5 ) / 16;
X nextberr[col ] += ( err ) / 16;
X }
X if (fs_direction) {
X col++;
X pP++;
X }
X else {
X col--;
X pP--;
X }
X } while (col != limitcol);
X
X temperr = thisrerr;
X thisrerr = nextrerr;
X nextrerr = temperr;
X temperr = thisgerr;
X thisgerr = nextgerr;
X nextgerr = temperr;
X temperr = thisberr;
X thisberr = nextberr;
X nextberr = temperr;
X fs_direction = !fs_direction;
X}
X
Xclean_floyd()
X{
X free(thisrerr);
X free(nextrerr);
X free(thisgerr);
X free(nextgerr);
X free(thisberr);
X free(nextberr);
X}
X
Xlong* long_alloc(n)
Xint n;
X{
X long* l;
X
X l = (long*)malloc(n * sizeof(long));
X
X if (l == NULL)
X no_mem();
X
X return(l);
X}
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'errs.h'" '(366 characters)'
if test -f 'errs.h'
then
echo shar: will not over-write existing file "'errs.h'"
else
sed 's/^X//' << \SHAR_EOF > 'errs.h'
X/* Various error codes used by decoder
X * and my own routines... It's okay
X * for you to define whatever you want,
X * as long as it's negative... It will be
X * returned intact up the various subroutine
X * levels...
X */
X#define OUT_OF_MEMORY -10
X#define BAD_CODE_SIZE -20
X#define READ_ERROR -1
X#define WRITE_ERROR -2
X#define OPEN_ERROR -3
X#define CREATE_ERROR -4
X
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'std.h'" '(278 characters)'
if test -f 'std.h'
then
echo shar: will not over-write existing file "'std.h'"
else
sed 's/^X//' << \SHAR_EOF > 'std.h'
X/* STD.H - My own standard header file...
X */
X
X#define LOCAL static
X#define IMPORT extern
X
X#define FAST register
X
Xtypedef short WORD;
Xtypedef unsigned short UWORD;
Xtypedef char TEXT;
Xtypedef unsigned char UTINY;
Xtypedef long LONG;
Xtypedef unsigned long ULONG;
Xtypedef int INT;
X
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'mem_image.h'" '(282 characters)'
if test -f 'mem_image.h'
then
echo shar: will not over-write existing file "'mem_image.h'"
else
sed 's/^X//' << \SHAR_EOF > 'mem_image.h'
X/*
X * mem_image.h
X */
X
Xstruct mem_image {
X int* colourmap;
X int* mapmap;
X int maplen;
X char* data;
X int width;
X int height;
X int depth;
X struct imgfile* imf;
X struct mem_image* next;
X
X /* extras */
X int gif_interlaced;
X int x_off;
X int y_off;
X int background;
X int seq;
X};
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'newsmap.h'" '(75 characters)'
if test -f 'newsmap.h'
then
echo shar: will not over-write existing file "'newsmap.h'"
else
sed 's/^X//' << \SHAR_EOF > 'newsmap.h'
X/*
X * newsmap.h
X */
X
Xextern void init_newsmap();
Xextern int rgb2newsmap();
SHAR_EOF
fi # end of overwriting check
echo shar: extracting "'imgfile.h'" '(164 characters)'
if test -f 'imgfile.h'
then
echo shar: will not over-write existing file "'imgfile.h'"
else
sed 's/^X//' << \SHAR_EOF > 'imgfile.h'
X/*
X * imgfile.h
X */
X
Xstruct imgfile {
X char* filename;
X char* name;
X FILE* stream;
X int width;
X int height;
X struct mem_image* imglist;
X struct imgfile* next;
X};
SHAR_EOF
fi # end of overwriting check
# End of shell archive
exit 0