From 0746108a35256aa72b3938370a53a8d52b731e62 Mon Sep 17 00:00:00 2001 From: giraffedata Date: Wed, 22 Nov 2006 04:29:28 +0000 Subject: Add pamtogif git-svn-id: http://svn.code.sf.net/p/netpbm/code/trunk@141 9d0c8265-081b-0410-96cb-a4ca84ce46f8 --- converter/other/Makefile | 2 +- converter/other/pamtogif.c | 2022 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 2023 insertions(+), 1 deletion(-) create mode 100644 converter/other/pamtogif.c diff --git a/converter/other/Makefile b/converter/other/Makefile index 6cde424d..0273c523 100644 --- a/converter/other/Makefile +++ b/converter/other/Makefile @@ -79,7 +79,7 @@ endif PORTBINARIES = bmptopnm fitstopnm \ gemtopnm giftopnm hdifftopam infotopam \ - pamtodjvurle pamtofits \ + pamtodjvurle pamtofits pamtogif \ pamtohdiff pamtohtmltbl pamtopfm pamtopnm pamtouil \ pamtoxvmini \ pbmtopgm pfmtopam \ diff --git a/converter/other/pamtogif.c b/converter/other/pamtogif.c new file mode 100644 index 00000000..9e19086d --- /dev/null +++ b/converter/other/pamtogif.c @@ -0,0 +1,2022 @@ +/*============================================================================= + pamtogif +=============================================================================== + Convert a Netpbm image to GIF + + History and copyright information is at the end of the file. +=============================================================================*/ + + +/* TODO: merge the LZW and uncompressed subroutines. They are separate + only because they had two different lineages and the code is too + complicated for me quickly to rewrite it. +*/ +#include +#include + +#include "mallocvar.h" +#include "shhopt.h" +#include "nstring.h" +#include "pam.h" +#include "pammap.h" + +#define MAXCMAPSIZE 256 + +static unsigned int const gifMaxval = 255; + +static bool verbose; + +typedef int stringCode; + /* A code to be place in the GIF raster. It represents + a string of one or more pixels. You interpret this in the context + of a current code size. The lower half of the values representable + in the current code size represent singleton strings and the value + is simply the value of the one pixel in the string. The first two + values in the upper half of the range are the clear code and EOF + code, respectively. The rest of the values represent multi-pixel + strings. The mapping between value and the sequence of pixels + changes throughout the image. + + A variable of this type sometimes has the value -1 instead of + a string code due to cheesy programming. + + Ergo, this data structure most be signed and at least BITS bits + wide plus sign bit. + */ + + +struct cmap { + /* This is the information for the GIF colormap (aka palette). */ + + struct pam pam; + /* Gives depth and maxval for colors in color[] */ + tuple color[MAXCMAPSIZE]; + /* Maps a color index, as is found in the raster part of the + GIF, to color. + */ + int perm[MAXCMAPSIZE], permi[MAXCMAPSIZE]; + /* perm[i] is the position in the sorted colormap of the color which + is at position i in the unsorted colormap. permi[] is the inverse + function of perm[]. + + The sort colormap is the one that goes into the GIF. The + unsorted one is the one that is hashed so we can find colors + in it. + */ + unsigned int cmapSize; + /* Number of entries in the GIF colormap. I.e. number of colors + in the image, plus possibly one fake transparency color. + */ + bool haveTransparent; + /* The colormap contains an entry for transparent pixels */ + unsigned int transparent; + /* color index number in GIF palette of the color that is to + be transparent. This is a post-sort index. + + Meaningful only if 'haveTransparent' is true. + */ + tuplehash tuplehash; + /* A hash table to translate color to GIF (presort) colormap index. */ +}; + +struct cmdlineInfo { + /* All the information the user supplied in the command line, + in a form easy for the program to use. + */ + const char *input_filespec; /* Filespec of input file */ + const char *alphacolor; /* -alphacolor option value or default */ + unsigned int interlace; /* -interlace option value */ + unsigned int sort; /* -sort option value */ + const char *mapfile; /* -mapfile option value. NULL if none. */ + const char *transparent; /* -transparent option value. NULL if none. */ + const char *comment; /* -comment option value; NULL if none */ + unsigned int nolzw; /* -nolzw option */ + unsigned int verbose; +}; + + +static unsigned int +nSignificantBits(unsigned int const arg) { + + unsigned int i; + + i = 0; + + while (arg >> i != 0) + ++i; + + return i; +} + + + +static unsigned int +pamAlphaPlane(struct pam * const pamP) { + + unsigned int alphaPlane; + + if (STREQ(pamP->tuple_type, "RGB_ALPHA")) + alphaPlane = 3; + else if (STREQ(pamP->tuple_type, "GRAYSCALE_ALPHA")) + alphaPlane = 2; + else if (STREQ(pamP->tuple_type, "BLACKANDWHITE_ALPHA")) + alphaPlane = 2; + else + alphaPlane = 0; + + if (alphaPlane >= pamP->depth) + pm_error("Tuple type is '%s', but depth (%u) is less than %u", + pamP->tuple_type, pamP->depth, alphaPlane + 1); + + return alphaPlane; +} + + + +static void +handleLatex2htmlHack(void) { +/*---------------------------------------------------------------------------- + This program used to put out a "usage" message when it saw an option + it didn't understand. Latex2html's configure program does a + ppmtogif -h (-h was never a valid option) to elicit that message and + then parses the message to see if it included the strings + "-interlace" and "-transparent". That way it knows if the + 'ppmtogif' program it found has those options or not. I don't think + any 'ppmtogif' you're likely to find today lacks those options, but + latex2html checks anyway, and we don't want it to conclude that we + don't have them. + + So we issue a special error message just to trick latex2html into + deciding that we have -interlace and -transparent options. The function + is not documented in the man page. We would like to see Latex2html + either stop checking or check like configure programs usually do -- + try the option and see if you get success or failure. + + -Bryan 2001.11.14 +-----------------------------------------------------------------------------*/ + pm_error("latex2html, you should just try the -interlace and " + "-transparent options to see if they work instead of " + "expecting a 'usage' message from -h"); +} + + + +static void +parseCommandLine(int argc, char ** argv, + struct cmdlineInfo * const cmdlineP) { +/*---------------------------------------------------------------------------- + Parse the program arguments (given by argc and argv) into a form + the program can deal with more easily -- a cmdline_info structure. + If the syntax is invalid, issue a message and exit the program via + pm_error(). + + Note that the file spec array we return is stored in the storage that + was passed to us as the argv array. +-----------------------------------------------------------------------------*/ + optEntry * option_def; /* malloc'ed */ + optStruct3 opt; /* set by OPTENT3 */ + unsigned int option_def_index; + + unsigned int latex2htmlhack; + + MALLOCARRAY_NOFAIL(option_def, 100); + + option_def_index = 0; /* incremented by OPTENT3 */ + OPTENT3(0, "interlace", OPT_FLAG, + NULL, &cmdlineP->interlace, 0); + OPTENT3(0, "sort", OPT_FLAG, + NULL, &cmdlineP->sort, 0); + OPTENT3(0, "nolzw", OPT_FLAG, + NULL, &cmdlineP->nolzw, 0); + OPTENT3(0, "mapfile", OPT_STRING, + &cmdlineP->mapfile, NULL, 0); + OPTENT3(0, "transparent", OPT_STRING, + &cmdlineP->transparent, NULL, 0); + OPTENT3(0, "comment", OPT_STRING, + &cmdlineP->comment, NULL, 0); + OPTENT3(0, "alphacolor", OPT_STRING, + &cmdlineP->alphacolor, NULL, 0); + OPTENT3(0, "h", OPT_FLAG, + NULL, &latex2htmlhack, 0); + OPTENT3(0, "verbose", OPT_FLAG, + NULL, &cmdlineP->verbose, 0); + + /* Set the defaults */ + cmdlineP->mapfile = NULL; + cmdlineP->transparent = NULL; /* no transparency */ + cmdlineP->comment = NULL; /* no comment */ + cmdlineP->alphacolor = "rgb:0/0/0"; + /* We could say "black" here, but then we depend on the color names + database existing. + */ + + opt.opt_table = option_def; + opt.short_allowed = FALSE; /* We have no short (old-fashioned) options */ + opt.allowNegNum = FALSE; /* We have no parms that are negative numbers */ + + optParseOptions3(&argc, argv, opt, sizeof(opt), 0); + /* Uses and sets argc, argv, and some of *cmdlineP and others. */ + + if (latex2htmlhack) + handleLatex2htmlHack(); + + if (argc-1 == 0) + cmdlineP->input_filespec = "-"; + else if (argc-1 != 1) + pm_error("Program takes zero or one argument (filename). You " + "specified %d", argc-1); + else + cmdlineP->input_filespec = argv[1]; +} + + + +/* + * Write out a word to the GIF file + */ +static void +Putword(int const w, FILE * const fp) { + + fputc( w & 0xff, fp ); + fputc( (w / 256) & 0xff, fp ); +} + + + +static int +closestColor(tuple const color, + struct pam * const pamP, + struct cmap * const cmapP) { +/*---------------------------------------------------------------------------- + Return the pre-sort colormap index of the color in the colormap *cmapP + that is closest to the color 'color', whose format is specified by + *pamP. + + Also add 'color' to the colormap hash, with the colormap index we + are returning. Caller must ensure that the color is not already in + there. +-----------------------------------------------------------------------------*/ + unsigned int const nComp = pamP->depth >= 3 ? 3 : 1; + /* Number of color components (not alpha) in 'color' */ + + unsigned int i; + unsigned int imin, dmin; + bool fits; + + dmin = UINT_MAX; + imin = 0; + for (i = 0; i < cmapP->cmapSize; ++i) { + unsigned int distance; + unsigned int plane; + + for (distance = 0, plane = 0; plane < nComp; ++plane) + // Divide by 4 is to avoid arithmetic overflow + distance += SQR(color[plane] - cmapP->color[i][plane]) / 4; + + if (distance < dmin) { + dmin = distance; + imin = i; + } + } + pnm_addtotuplehash(pamP, cmapP->tuplehash, color, imin, &fits); + + return imin; +} + + + +enum pass {MULT8PLUS0, MULT8PLUS4, MULT4PLUS2, MULT2PLUS1}; + + +typedef struct { + struct pam pam; + /* Description of input file/image. The position of the file + is also part of the state of this rowReader. + */ + pm_filepos rasterPos; + /* Position in file fileP of the start of the raster */ + bool interlace; + /* We're accessing the image in interlace fashion */ + bool eof; + /* The image is at EOF (we have returned all of the rows) */ + unsigned int nextRow; + /* Number of row to which input file is positioned; + meaningless if 'eof'. + */ + enum pass pass; + /* The interlace pass. Undefined if !interlace */ + tuple * discardBuffer; + /* A bitbucket for rows we read in order to advance the file + position. + */ +} rowReader; + + + +static rowReader * +rowReader_create(struct pam * const pamP, + pm_filepos const rasterPos, + bool const interlace) { + + rowReader * rdrP; + + MALLOCVAR_NOFAIL(rdrP); + + rdrP->pam = *pamP; + rdrP->rasterPos = rasterPos; + rdrP->interlace = interlace; + rdrP->eof = FALSE; + rdrP->pass = MULT8PLUS0; + + pm_seek2(rdrP->pam.file, &rasterPos, sizeof(rasterPos)); + rdrP->nextRow = 0; + + rdrP->discardBuffer = pnm_allocpamrow(&rdrP->pam); + + return rdrP; +} + + + +static void +rowReader_destroy(rowReader * const rdrP) { + + pnm_freepamrow(rdrP->discardBuffer); + free(rdrP); +} + + + +static void +rowReaderSkipRows(rowReader * const rdrP, + unsigned int const rowCount, + bool * const eofP) { +/*---------------------------------------------------------------------------- + Skip over the next 'rowCount' rows of the input file. + + Iff there aren't at least 'rowCount' rows left, return *eofP == TRUE. +-----------------------------------------------------------------------------*/ + if (rdrP->nextRow + rowCount >= rdrP->pam.height) + *eofP = TRUE; + else { + /* This could be made faster if need be by adding a libnetpbm + row skip function. Except with the plain formats, that could + just compute the next row position and fseek() to it. + pnm_readpamrow() with NULL for the output pointer would be a + good interface for a row skip function. + */ + unsigned int i; + + *eofP = FALSE; + + for (i = 0; i < rowCount; ++i) + pnm_readpamrow(&rdrP->pam, rdrP->discardBuffer); + + rdrP->nextRow += rowCount; + } +} + + + +static void +rowReaderGotoNextInterlaceRow(rowReader * const rdrP) { +/*---------------------------------------------------------------------------- + Position reader to the next row in the interlace pattern, assuming it + is now positioned immediately after the current row. +-----------------------------------------------------------------------------*/ + bool endOfPass; + + /* There are 4 passes: + MULT8PLUS0: Rows 0, 8, 16, 24, 32, etc. + MULT8PLUS4: Rows 4, 12, 20, 28, etc. + MULT4PLUS2: Rows 2, 6, 10, 14, etc. + MULT2PLUS1: Rows 1, 3, 5, 7, 9, etc. + */ + + switch (rdrP->pass) { + case MULT8PLUS0: + rowReaderSkipRows(rdrP, 7, &endOfPass); + break; + case MULT8PLUS4: + rowReaderSkipRows(rdrP, 7, &endOfPass); + break; + case MULT4PLUS2: + rowReaderSkipRows(rdrP, 3, &endOfPass); + break; + case MULT2PLUS1: + rowReaderSkipRows(rdrP, 1, &endOfPass); + break; + } + + /* Note that if there are more than 4 rows, the sequence of passes + is sequential, but when there are fewer than 4, reading may skip + e.g. from MULT8PLUS0 to MULT4PLUS2. + */ + while (endOfPass && !rdrP->eof) { + pm_seek2(rdrP->pam.file, &rdrP->rasterPos, sizeof(rdrP->rasterPos)); + rdrP->nextRow = 0; + + switch (rdrP->pass) { + case MULT8PLUS0: + rdrP->pass = MULT8PLUS4; + rowReaderSkipRows(rdrP, 4, &endOfPass); + break; + case MULT8PLUS4: + rdrP->pass = MULT4PLUS2; + rowReaderSkipRows(rdrP, 2, &endOfPass); + break; + case MULT4PLUS2: + rdrP->pass = MULT2PLUS1; + rowReaderSkipRows(rdrP, 1, &endOfPass); + break; + case MULT2PLUS1: + rdrP->eof = TRUE; + break; + } + } +} + + + + +static void +rowReaderGotoNextStraightRow(rowReader * const rdrP) { +/*---------------------------------------------------------------------------- + Position reader to the next row in a straight, non-interlace + pattern, assuming the file is now positioned immediately after the + current row. + + This is trivial, since the next row _is_ immediately after the current + row, except in the case that there are no more rows. +-----------------------------------------------------------------------------*/ + if (rdrP->nextRow >= rdrP->pam.height) + rdrP->eof = TRUE; +} + + + +static void +rowReader_read(rowReader * const rdrP, + tuple * const tuplerow) { + + if (rdrP->eof) + pm_error("INTERNAL ERROR: rowReader attempted to read beyond end " + "of image"); + + pnm_readpamrow(&rdrP->pam, tuplerow); + ++rdrP->nextRow; + + if (rdrP->interlace) + rowReaderGotoNextInterlaceRow(rdrP); + else + rowReaderGotoNextStraightRow(rdrP); +} + + + +static unsigned int +gifPixel(struct pam * const pamP, + tuple const tuple, + unsigned int const alphaPlane, + sample const alphaThreshold, + struct cmap * const cmapP) { +/*---------------------------------------------------------------------------- + Return as *colorIndexP the colormap index of the tuple 'tuple', + whose format is described by *pamP, using colormap *cmapP. + + 'alphaThreshold' is the alpha level below which we consider a + pixel transparent for GIF purposes. +-----------------------------------------------------------------------------*/ + unsigned int colorIndex; + + if (alphaPlane && tuple[alphaPlane] < alphaThreshold && + cmapP->haveTransparent) + colorIndex = cmapP->transparent; + else { + int presortColorindex; + int found; + + pnm_lookuptuple(pamP, cmapP->tuplehash, tuple, + &found, &presortColorindex); + + if (!found) + presortColorindex = closestColor(tuple, pamP, cmapP); + + colorIndex = cmapP->perm[presortColorindex]; + } + return colorIndex; +} + + + +static void +writeTransparentColorIndexExtension(FILE * const ofP, + unsigned int const transColorIndex) { +/*---------------------------------------------------------------------------- + Write out extension for transparent color index. +-----------------------------------------------------------------------------*/ + fputc('!', ofP); + fputc(0xf9, ofP); + fputc(4, ofP); + fputc(1, ofP); + fputc(0, ofP); + fputc(0, ofP); + fputc(transColorIndex, ofP); + fputc(0, ofP); +} + + + +static void +writeCommentExtension(FILE * const ofP, + char const comment[]) { +/*---------------------------------------------------------------------------- + Write out extension for a comment +-----------------------------------------------------------------------------*/ + unsigned int const maxSegmentSize = 255; + + const char * segment; + + fputc('!', ofP); /* Identifies an extension */ + fputc(0xfe, ofP); /* Identifies a comment */ + + /* Write it out in segments no longer than 255 characters */ + for (segment = &comment[0]; + segment < comment + strlen(comment); + segment += maxSegmentSize) { + + unsigned int const lengthThisSegment = + MIN(maxSegmentSize, strlen(segment)); + + fputc(lengthThisSegment, ofP); + + fwrite(segment, 1, lengthThisSegment, ofP); + } + + fputc(0, ofP); /* No more comment blocks in this extension */ +} + + + +/*************************************************************************** + * + * GIFCOMPR.C - GIF Image compression routines + * + * Lempel-Ziv compression based on 'compress'. GIF modifications by + * David Rowley (mgardi@watdcsu.waterloo.edu) + * + ***************************************************************************/ + +/* + * General DEFINEs + */ + +#define BITS 12 + +#define HSIZE 5003 /* 80% occupancy */ + +/* + * + * 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) + * + */ + +static stringCode const maxCodeLimit = (stringCode)1 << BITS; + /* One beyond the largest string code that can exist in GIF */ + + +struct hashTableEntry { + long fcode; // -1 means unused slot + unsigned int ent; +}; + + + +/*************************************************************************** +* BYTE OUTPUTTER +***************************************************************************/ + +typedef struct { + FILE * fileP; /* The file to which to output */ + unsigned int count; + /* Number of bytes so far in the current data block */ + unsigned char buffer[256]; + /* The current data block, under construction */ +} byteBuffer; + + + +static byteBuffer * +byteBuffer_create(FILE * const fileP) { + + byteBuffer * byteBufferP; + + MALLOCVAR_NOFAIL(byteBufferP); + + byteBufferP->fileP = fileP; + byteBufferP->count = 0; + + return byteBufferP; +} + + + +static void +byteBuffer_destroy(byteBuffer * const byteBufferP) { + + free(byteBufferP); +} + + + +static void +byteBuffer_flush(byteBuffer * const byteBufferP) { +/*---------------------------------------------------------------------------- + Write the current data block to the output file, then reset the current + data block to empty. +-----------------------------------------------------------------------------*/ + if (byteBufferP->count > 0 ) { + if (verbose) + pm_message("Writing %u byte block", byteBufferP->count); + fputc(byteBufferP->count, byteBufferP->fileP); + fwrite(byteBufferP->buffer, 1, byteBufferP->count, byteBufferP->fileP); + byteBufferP->count = 0; + } +} + + + +static void +byteBuffer_flushFile(byteBuffer * const byteBufferP) { + + fflush(byteBufferP->fileP); + + if (ferror(byteBufferP->fileP)) + pm_error("error writing output file"); +} + + + +static void +byteBuffer_out(byteBuffer * const byteBufferP, + unsigned char const c) { +/*---------------------------------------------------------------------------- + Add a byte to the end of the current data block, and if it is now 254 + characters, flush the data block to the output file. +-----------------------------------------------------------------------------*/ + byteBufferP->buffer[byteBufferP->count++] = c; + if (byteBufferP->count >= 254) + byteBuffer_flush(byteBufferP); +} + + + +/*************************************************************************** +* GIF CODE OUTPUTTER +***************************************************************************/ + +typedef struct { + byteBuffer * byteBufferP; + unsigned int initBits; + unsigned int nBits; + /* Number of bits to put in output for each code */ + stringCode maxCode; /* maximum code, given n_bits */ + unsigned long curAccum; + int curBits; + unsigned int codeCount; + /* Number of codes that have been output to this buffer (doesn't + matter if they have gone out the other side yet or not) since + the last flush (or ever, if no last flush). The main use of this + is debugging -- when something fails, you can see in a debugger + where in the image it was, then set a trap for there. + */ +} codeBuffer; + + + +static codeBuffer * +codeBuffer_create(FILE * const ofP, + unsigned int const initBits) { + + codeBuffer * codeBufferP; + + MALLOCVAR_NOFAIL(codeBufferP); + + codeBufferP->initBits = initBits; + codeBufferP->nBits = codeBufferP->initBits; + codeBufferP->maxCode = (1 << codeBufferP->nBits) - 1; + codeBufferP->byteBufferP = byteBuffer_create(ofP); + codeBufferP->curAccum = 0; + codeBufferP->curBits = 0; + codeBufferP->codeCount = 0; + + return codeBufferP; +} + + + +static void +codeBuffer_destroy(codeBuffer * const codeBufferP) { + + byteBuffer_destroy(codeBufferP->byteBufferP); + + free(codeBufferP); +} + + + +static void +codeBuffer_resetCodeSize(codeBuffer * const codeBufferP) { + + codeBufferP->nBits = codeBufferP->initBits; + + assert(codeBufferP->nBits <= BITS); + + codeBufferP->maxCode = (1 << codeBufferP->nBits) - 1; +} + + + +static void +codeBuffer_increaseCodeSize(codeBuffer * const codeBufferP) { + + ++codeBufferP->nBits; + + assert(codeBufferP->nBits <= BITS); + + codeBufferP->maxCode = (1 << codeBufferP->nBits) - 1; +} + + + +static unsigned long const masks[] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000F, + 0x001F, 0x003F, 0x007F, 0x00FF, + 0x01FF, 0x03FF, 0x07FF, 0x0FFF, + 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF }; + +static void +codeBuffer_output(codeBuffer * const codeBufferP, + stringCode const code) { +/*---------------------------------------------------------------------------- + Output one GIF code to the file, through the code buffer. + + The code is represented as N bits in the file -- the lower + N bits of 'code'. N is a the current code size of *codeBufferP. + + Id 'code' is the maximum possible code for the current code size + for *codeBufferP, increase that code size (unless it's already + maxed out). +-----------------------------------------------------------------------------*/ + assert (code <= codeBufferP->maxCode); + + codeBufferP->curAccum &= masks[codeBufferP->curBits]; + + if (codeBufferP->curBits > 0) + codeBufferP->curAccum |= ((long)code << codeBufferP->curBits); + else + codeBufferP->curAccum = code; + + codeBufferP->curBits += codeBufferP->nBits; + + while (codeBufferP->curBits >= 8) { + byteBuffer_out(codeBufferP->byteBufferP, + codeBufferP->curAccum & 0xff); + codeBufferP->curAccum >>= 8; + codeBufferP->curBits -= 8; + } + + ++codeBufferP->codeCount; +} + + + +static void +codeBuffer_flush(codeBuffer * const codeBufferP) { + + /* Output the possible partial byte in the buffer */ + + if (codeBufferP->curBits > 0) { + byteBuffer_out(codeBufferP->byteBufferP, + codeBufferP->curAccum & 0xff); + codeBufferP->curBits = 0; + } + byteBuffer_flush(codeBufferP->byteBufferP); + + byteBuffer_flushFile(codeBufferP->byteBufferP); + + if (verbose) + pm_message("%u strings of pixels written to file", + codeBufferP->codeCount); + codeBufferP->codeCount = 0; +} + + + +typedef struct { + codeBuffer * codeBufferP; + /* The place to which we write our string codes. + + Constant. + */ + unsigned int hshift; + /* This is how many bits we shift left a string code in forming the + primary hash of the concatenation of that string with another. + Constant. + */ + + /* Codes less than 'clearCode' are singleton pixel codes - each + represents the pixel value equal to it. + + Codes greater than 'eofCode' are multipixel string codes. Each + represents a string of pixels that is defined by the preceding + stream. + */ + stringCode clearCode; + /* The code in an LZW stream that means to clear the string + dictionary and start fresh. + + Constant. + */ + stringCode eofCode; + /* The code in an LZW stream that means there's no more coming + + Constant. + */ + stringCode initCodeLimit; + /* The value of 'codeLimit' at the start of a block. + + Constant. + */ + + stringCode codeLimit; + /* One beyond the maximum code possible with the current code + size. + */ + + struct hashTableEntry * hashTable; + stringCode nextUnusedCode; + /* Numerically next code available to assign to a a multi-pixel + string. Note that codes for multi-pixel strings are in the + upper half of the range of codes, always greater than + 'clearCode'. + */ + + stringCode stringSoFar; + /* The code for the string we have built so far. This code indicates + one or more pixels that we have encoded but not yet output + because we're hoping to match an even longer string. + + Valid only when 'buildingString' is true. + */ + bool buildingString; + /* We are in the middle of building a string; 'stringSoFar' describes + the pixels in it so far. The only time this is false is at the + very beginning of the stream. + */ +} lzwCompressor; + + + +static lzwCompressor * +lzw_create(FILE * const ofP, + unsigned int const initBits) { + + lzwCompressor * lzwP; + + MALLOCVAR_NOFAIL(lzwP); + + MALLOCARRAY(lzwP->hashTable, HSIZE); + + if (lzwP->hashTable == NULL) + pm_error("Couldn't get memory for %u-entry hash table.", HSIZE); + + /* Constants */ + lzwP->hshift = + nSignificantBits(HSIZE-1) - 1 - nSignificantBits(MAXCMAPSIZE-1); + lzwP->clearCode = 1 << (initBits - 1); + lzwP->eofCode = lzwP->clearCode + 1; + lzwP->initCodeLimit = 1 << initBits; + + lzwP->buildingString = FALSE; + + lzwP->codeBufferP = codeBuffer_create(ofP, initBits); + + return lzwP; +} + + + +static void +lzw_destroy(lzwCompressor * const lzwP) { + + codeBuffer_destroy(lzwP->codeBufferP); + + free(lzwP->hashTable); + + free(lzwP); +} + + + +static void +lzwHashClear(lzwCompressor * const lzwP) { + + /* Empty the code table */ + + unsigned int i; + + for (i = 0; i < HSIZE; ++i) + lzwP->hashTable[i].fcode = -1; + + lzwP->nextUnusedCode = lzwP->clearCode + 2; + + +} + + + +static void +lzw_clearBlock(lzwCompressor * const lzwP) { +/*---------------------------------------------------------------------------- + +-----------------------------------------------------------------------------*/ + lzwHashClear(lzwP); + + codeBuffer_output(lzwP->codeBufferP, lzwP->clearCode); + + codeBuffer_resetCodeSize(lzwP->codeBufferP); + + lzwP->codeLimit = lzwP->initCodeLimit; +} + + + +static void +lzwAdjustCodeSize(lzwCompressor * const lzwP, + stringCode const newCode) { +/*---------------------------------------------------------------------------- + Assuming we just defined code 'newCode', increase the code size as + required so that this code fits. + + The decompressor is mimicking our assignment of that code, so knows that + we are making this adjustment, so expects codes of the new size. +-----------------------------------------------------------------------------*/ + assert(newCode <= lzwP->codeLimit); + + if (newCode == lzwP->codeLimit) { + lzwP->codeLimit *= 2; + codeBuffer_increaseCodeSize(lzwP->codeBufferP); + + assert(lzwP->codeLimit <= maxCodeLimit); + } +} + + + +static void +lzwOutputCurrentString(lzwCompressor * const lzwP) { +/*---------------------------------------------------------------------------- + Put a code for the currently built-up string in the output stream. + + Doing this causes a new string code to be defined (code is + lzwP->nextUnusedCode), so Caller must add that to the hash. If + that code is beyond the overall limit, we reset the hash and put a + clear code in the stream to tell the decompressor to do the same. + So Caller must add it to the hash _before_ calling us. + + There's an odd case that always screws up any attempt to make this + code cleaner: At the end of the LZW stream, you have to output the + code for the final string even though you don't have a following + pixel that would make a longer string. So there's nothing to add + to the hash table and no point in allocating a new string code. + But the decompressor doesn't know that we're done, so he allocates + the next string code and may therefore increase his code length. + If we don't do the same, we will write our one last code -- the EOF + code -- in a code length smaller than what the decompressor is + expecting, and he will have a premature end of stream. + + So this subroutine does run for that final code flush and does some + of the motions of defining a new string code, but this subroutine + can't update the hash because in that particular case, there's + nothing to add. +-----------------------------------------------------------------------------*/ + codeBuffer_output(lzwP->codeBufferP, lzwP->stringSoFar); + + if (lzwP->nextUnusedCode < maxCodeLimit) { + /* Allocate the code for the extended string, which Caller + should have already put in the hash so he can use it in the + future. Decompressor knows when it sees the code output + above to define a string on its end too, using the same + string code we do. + */ + stringCode const newCode = lzwP->nextUnusedCode++; + + /* This code may be too big to fit in the current code size, in + which case we have to increase the code size (and decompressor + will do the same). + */ + lzwAdjustCodeSize(lzwP, newCode); + } else { + /* Forget all the strings so far; start building again; tell + decompressor to do the same. + */ + lzw_clearBlock(lzwP); + } +} + + + +static void +lzw_flush(lzwCompressor * const lzwP) { + + /* Put out the code for the final string. */ + + lzwOutputCurrentString(lzwP); + + codeBuffer_output(lzwP->codeBufferP, lzwP->eofCode); + + codeBuffer_flush(lzwP->codeBufferP); +} + + + +static unsigned int +primaryHash(stringCode const baseString, + stringCode const additionalPixel, + unsigned int const hshift) { + + unsigned int hash; + + assert(baseString < maxCodeLimit); + assert(additionalPixel < MAXCMAPSIZE); + + hash = (additionalPixel << hshift) ^ baseString; + + assert(hash < HSIZE); + + return hash; +} + + + +static void +lookupInHash(lzwCompressor * const lzwP, + unsigned int const gifPixel, + long const fcode, + bool * const foundP, + unsigned short * const codeP, + unsigned int * const hashP) { + + int disp; + /* secondary hash stride (after G. Knott) */ + int i; + /* Index into hash table */ + + i = primaryHash(lzwP->stringSoFar, gifPixel, lzwP->hshift); + disp = (i == 0) ? 1 : HSIZE - i; + + while (lzwP->hashTable[i].fcode != fcode && + lzwP->hashTable[i].fcode >= 0) { + i -= disp; + if (i < 0) + i += HSIZE; + } + + if (lzwP->hashTable[i].fcode == fcode) { + /* Found fcode in hash table */ + *foundP = TRUE; + *codeP = lzwP->hashTable[i].ent; + } else { + /* Found where it _should_ be (but it's not) with primary hash */ + *foundP = FALSE; + *hashP = i; + } +} + + + +static void +lzw_encodePixel(lzwCompressor * const lzwP, + struct pam * const pamP, + unsigned int const gifPixel) { + + bool found; + unsigned short code; + unsigned int hash; + /* Index into hash table where the value should go */ + + assert(gifPixel < 256); + + if (!lzwP->buildingString) { + /* Start a new string with just this pixel */ + lzwP->stringSoFar = gifPixel; + lzwP->buildingString = TRUE; + } else { + long const fcode = ((long) gifPixel << BITS) + lzwP->stringSoFar; + /* The encoding of the string we've already recognized plus the + instant pixel, to be looked up in the hash of knows strings. + */ + + lookupInHash(lzwP, gifPixel, fcode, &found, &code, &hash); + + if (found) + /* With this new pixel, it is still a known string; 'code' is + its code + */ + lzwP->stringSoFar = code; + else { + /* It's no longer a known string. Output the code for the + known prefix of the string, thus defining a new string + code for possible later use. Warning: + lzwOutputCurrentString() does more than you think. + */ + + lzwP->hashTable[hash].ent = lzwP->nextUnusedCode; + lzwP->hashTable[hash].fcode = fcode; + + lzwOutputCurrentString(lzwP); + + /* This singleton pixel starts the next string */ + lzwP->stringSoFar = gifPixel; + } + } +} + + + +/* + * 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. + */ + + +struct gifDest { + /* This structure controls output of uncompressed GIF raster */ + + byteBuffer * byteBufferP; /* Where the full bytes go */ + + /* State for packing variable-width codes into a bitstream */ + int n_bits; /* current number of bits/code */ + int maxcode; /* maximum code, given n_bits */ + int cur_accum; /* holds bits not yet output */ + int cur_bits; /* # of bits in cur_accum */ + + /* State for GIF code assignment */ + int ClearCode; /* clear code (doesn't change) */ + int EOFCode; /* EOF code (ditto) */ + int code_counter; /* counts output symbols */ +}; + + + +static void +writeRasterLzw(struct pam * const pamP, + rowReader * const rowReaderP, + unsigned int const alphaPlane, + unsigned int const alphaThreshold, + struct cmap * const cmapP, + unsigned int const initBits, + FILE * const ofP) { +/*---------------------------------------------------------------------------- + Write the raster to file 'ofP'. + + Get the raster to write from 'rowReaderP', which gives tuples whose + format is described by 'pamP'. + + Use the colormap 'cmapP' to generate the raster ('rowReaderP' gives + pixel values as RGB samples; the GIF raster is colormap indices). + + Write the raster using LZW compression. +-----------------------------------------------------------------------------*/ + lzwCompressor * lzwP; + tuple * tuplerow; + unsigned int nRowsDone; + /* Number of rows we have read so far from the the input (the + last of which is the one we're working on now). Note that + in case of interlace, this is not the same thing as the row + number of the current row. + */ + + lzwP = lzw_create(ofP, initBits); + + tuplerow = pnm_allocpamrow(pamP); + + lzw_clearBlock(lzwP); + + nRowsDone = 0; + + while (nRowsDone < pamP->height) { + unsigned int col; + + rowReader_read(rowReaderP, tuplerow); + + for (col = 0; col < pamP->width; ++col) { + unsigned int const colorIndex = + gifPixel(pamP, tuplerow[col], alphaPlane, alphaThreshold, + cmapP); + + /* The value for the pixel in the GIF image. I.e. the colormap + index. + */ + + lzw_encodePixel(lzwP, pamP, colorIndex); + } + ++nRowsDone; + } + /* Gif is no good with no pixels; fortunately, that's impossible: */ + assert(nRowsDone > 0); + + lzw_flush(lzwP); + + pnm_freepamrow(tuplerow); + + lzw_destroy(lzwP); +} + + + +/* Routine to convert variable-width codes into a byte stream */ + +static void +outputUncompressed(struct gifDest * const dinfoP, + int const code) { + + /* Emit a code of n_bits bits */ + /* Uses cur_accum and cur_bits to reblock into 8-bit bytes */ + dinfoP->cur_accum |= ((int) code) << dinfoP->cur_bits; + dinfoP->cur_bits += dinfoP->n_bits; + + while (dinfoP->cur_bits >= 8) { + byteBuffer_out(dinfoP->byteBufferP, dinfoP->cur_accum & 0xFF); + dinfoP->cur_accum >>= 8; + dinfoP->cur_bits -= 8; + } +} + + +static void +writeRasterUncompressedInit(FILE * const ofP, + struct gifDest * const dinfoP, + int const i_bits) { +/*---------------------------------------------------------------------------- + Initialize pseudo-compressor +-----------------------------------------------------------------------------*/ + + /* init all the state variables */ + dinfoP->n_bits = i_bits; + dinfoP->maxcode = (1 << dinfoP->n_bits) - 1; + dinfoP->ClearCode = (1 << (i_bits - 1)); + dinfoP->EOFCode = dinfoP->ClearCode + 1; + dinfoP->code_counter = dinfoP->ClearCode + 2; + /* init output buffering vars */ + dinfoP->byteBufferP = byteBuffer_create(ofP); + dinfoP->cur_accum = 0; + dinfoP->cur_bits = 0; + /* GIF specifies an initial Clear code */ + outputUncompressed(dinfoP, dinfoP->ClearCode); +} + + + +static void +writeRasterUncompressedPixel(struct gifDest * const dinfoP, + unsigned int const colormapIndex) { +/*---------------------------------------------------------------------------- + "Compress" one pixel value and output it as a symbol. + + 'colormapIndex' must be less than dinfoP->n_bits wide. +-----------------------------------------------------------------------------*/ + assert(colormapIndex >> dinfoP->n_bits == 0); + + outputUncompressed(dinfoP, colormapIndex); + /* Issue Clear codes often enough to keep the reader from ratcheting up + * its symbol size. + */ + if (dinfoP->code_counter < dinfoP->maxcode) { + ++dinfoP->code_counter; + } else { + outputUncompressed(dinfoP, dinfoP->ClearCode); + dinfoP->code_counter = dinfoP->ClearCode + 2; /* reset the counter */ + } +} + + + +static void +writeRasterUncompressedTerm(struct gifDest * const dinfoP) { + + outputUncompressed(dinfoP, dinfoP->EOFCode); + + if (dinfoP->cur_bits > 0) + byteBuffer_out(dinfoP->byteBufferP, dinfoP->cur_accum & 0xFF); + + byteBuffer_flush(dinfoP->byteBufferP); + + byteBuffer_destroy(dinfoP->byteBufferP); +} + + + +static void +writeRasterUncompressed(struct pam * const pamP, + rowReader * const rowReaderP, + unsigned int const alphaPlane, + unsigned int const alphaThreshold, + struct cmap * const cmapP, + int const initBits, + FILE * const ofP) { +/*---------------------------------------------------------------------------- + Write the raster to file 'ofP'. + + Same as writeRasterLzw(), except written out one code per + pixel (plus some clear codes), so no compression. And no use + of the LZW patent. +-----------------------------------------------------------------------------*/ + struct gifDest gifDest; + tuple * tuplerow; + unsigned int nRowsDone; + /* Number of rows we have read so far from the the input (the + last of which is the one we're working on now). Note that + in case of interlace, this is not the same thing as the row + number of the current row. + */ + + tuplerow = pnm_allocpamrow(pamP); + + writeRasterUncompressedInit(ofP, &gifDest, initBits); + + nRowsDone = 0; + + while (nRowsDone < pamP->height) { + unsigned int col; + + rowReader_read(rowReaderP, tuplerow); + + for (col = 0; col < pamP->width; ++col) { + unsigned int const colorIndex = + gifPixel(pamP, tuplerow[col], + alphaPlane, alphaThreshold, cmapP); + + /* The value for the pixel in the GIF image. I.e. the colormap + index. + */ + + writeRasterUncompressedPixel(&gifDest, colorIndex); + } + ++nRowsDone; + } + writeRasterUncompressedTerm(&gifDest); + + pnm_freepamrow(tuplerow); +} + + + +static void +writeGlobalColorMap(FILE * const ofP, + const struct cmap * const cmapP, + unsigned int const bitsPerPixel) { +/*---------------------------------------------------------------------------- + Write out the Global Color Map + + Note that the Global Color Map is always a power of two colors + in size, but *cmapP could be smaller than that. So we pad with + black. +-----------------------------------------------------------------------------*/ + unsigned int const colorMapSize = 1 << bitsPerPixel; + + struct pam pam; + unsigned int i; + tuple tupleRgb255; + + if (verbose) + pm_message("Writing %u-entry global colormap for %u colors", + colorMapSize, cmapP->cmapSize); + + pam = cmapP->pam; + pam.size = PAM_STRUCT_SIZE(allocation_depth); + pam.len = pam.size; + pam.allocation_depth = 3; + + tupleRgb255 = pnm_allocpamtuple(&pam); + + for (i = 0; i < colorMapSize; ++i) { + if (i < cmapP->cmapSize) { + tuple const color = cmapP->color[cmapP->permi[i]]; + + assert(cmapP->permi[i] < cmapP->cmapSize); + + pnm_scaletuple(&pam, tupleRgb255, color, 255); + pnm_maketuplergb(&pam, tupleRgb255); + + fputc(tupleRgb255[PAM_RED_PLANE], ofP); + fputc(tupleRgb255[PAM_GRN_PLANE], ofP); + fputc(tupleRgb255[PAM_BLU_PLANE], ofP); + } else { + fputc(0, ofP); + fputc(0, ofP); + fputc(0, ofP); + } + } + pnm_freepamtuple(tupleRgb255); +} + + + +static void +writeGifHeader(FILE * const ofP, + unsigned int const width, + unsigned int const height, + unsigned int const background, + unsigned int const bitsPerPixel, + const struct cmap * const cmapP, + char const comment[]) { + + unsigned int const resolution = bitsPerPixel; + + unsigned char b; + + /* Write the Magic header */ + if (cmapP->haveTransparent || comment) + fwrite("GIF89a", 1, 6, ofP); + else + fwrite("GIF87a", 1, 6, ofP); + + /* Write out the screen width and height */ + Putword(width, ofP); + Putword(height, ofP); + + /* Indicate that there is a global color map */ + b = 0x80; /* Yes, there is a color map */ + + /* OR in the resolution */ + b |= (resolution - 1) << 4; + + /* OR in the Bits per Pixel */ + b |= (bitsPerPixel - 1); + + /* Write it out */ + fputc(b, ofP); + + /* Write out the Background color */ + assert((unsigned char)background == background); + fputc(background, ofP); + + /* Byte of 0's (future expansion) */ + fputc(0x00, ofP); + + writeGlobalColorMap(ofP, cmapP, bitsPerPixel); + + if (cmapP->haveTransparent) + writeTransparentColorIndexExtension(ofP, cmapP->transparent); + + if (comment) + writeCommentExtension(ofP, comment); +} + + + +static void +writeImageHeader(FILE * const ofP, + unsigned int const leftOffset, + unsigned int const topOffset, + unsigned int const gWidth, + unsigned int const gHeight, + bool const gInterlace, + unsigned int const initCodeSize) { + + Putword(leftOffset, ofP); + Putword(topOffset, ofP); + Putword(gWidth, ofP); + Putword(gHeight, ofP); + + /* Write out whether or not the image is interlaced */ + if (gInterlace) + fputc(0x40, ofP); + else + fputc(0x00, ofP); + + /* Write out the initial code size */ + fputc(initCodeSize, ofP); +} + + + +static void +reportImageInfo(bool const interlace, + unsigned int const background, + unsigned int const bitsPerPixel) { + + if (verbose) { + if (interlace) + pm_message("interlaced"); + else + pm_message("not interlaced"); + pm_message("Background color index = %u", background); + pm_message("%u bits per pixel", bitsPerPixel); + } +} + + + +static void +gifEncode(struct pam * const pamP, + FILE * const ofP, + pm_filepos const rasterPos, + bool const gInterlace, + int const background, + unsigned int const bitsPerPixel, + struct cmap * const cmapP, + char const comment[], + bool const nolzw) { + + unsigned int const leftOffset = 0; + unsigned int const topOffset = 0; + + unsigned int const initCodeSize = bitsPerPixel <= 1 ? 2 : bitsPerPixel; + /* The initial code size */ + + sample const alphaThreshold = (pamP->maxval + 1) / 2; + /* Levels below this in the alpha plane indicate transparent + pixels in the output image. + */ + + unsigned int const alphaPlane = pamAlphaPlane(pamP); + + rowReader * rowReaderP; + + reportImageInfo(gInterlace, background, bitsPerPixel); + + writeGifHeader(ofP, pamP->width, pamP->height, background, + bitsPerPixel, cmapP, comment); + + /* Write an Image separator */ + fputc(',', ofP); + + writeImageHeader(ofP, leftOffset, topOffset, pamP->width, pamP->height, + gInterlace, initCodeSize); + + rowReaderP = rowReader_create(pamP, rasterPos, gInterlace); + + /* Write the actual raster */ + if (nolzw) + writeRasterUncompressed(pamP, rowReaderP, alphaPlane, alphaThreshold, + cmapP, initCodeSize + 1, ofP); + else + writeRasterLzw(pamP, rowReaderP, alphaPlane, alphaThreshold, + cmapP, initCodeSize + 1, ofP); + + rowReader_destroy(rowReaderP); + + /* Write out a zero length data block (to end the series) */ + fputc(0, ofP); + + /* Write the GIF file terminator */ + fputc(';', ofP); +} + + + +static void +reportTransparent(struct cmap * const cmapP) { + + if (verbose) { + if (cmapP->haveTransparent) { + tuple const color = cmapP->color[cmapP->permi[cmapP->transparent]]; + pm_message("Color %u (%lu, %lu, %lu) is transparent", + cmapP->transparent, + color[PAM_RED_PLANE], + color[PAM_GRN_PLANE], + color[PAM_BLU_PLANE]); + } else + pm_message("No transparent color"); + } +} + + + +static void +computeTransparent(char const colorarg[], + bool const usingFakeTrans, + unsigned int const fakeTransparent, + struct cmap * const cmapP) { +/*---------------------------------------------------------------------------- + Figure out the color index (index into the colormap) of the color + that is to be transparent in the GIF. + + colorarg[] is the string that specifies the color the user wants to + be transparent (e.g. "red", "#fefefe"). Its maxval is the maxval + of the colormap. 'cmap' is the full colormap except that its + 'transparent' component isn't valid. + + colorarg[] is a standard Netpbm color specification, except that + may have a "=" prefix, which means it specifies a particular exact + color, as opposed to without the "=", which means "the color that + is closest to this and actually in the image." + + colorarg[] null means the color didn't ask for a particular color + to be transparent. + + Establish no transparent color if colorarg[] specifies an exact + color and that color is not in the image. Also issue an + informational message. + + 'usingFakeTrans' means pixels will be transparent because of something + other than their foreground color, and 'fakeTransparent' is the + color map index for transparent colors. +-----------------------------------------------------------------------------*/ + if (colorarg) { + const char * colorspec; + bool exact; + tuple transcolor; + bool found; + int presortColorindex; + + if (colorarg[0] == '=') { + colorspec = &colorarg[1]; + exact = TRUE; + } else { + colorspec = colorarg; + exact = FALSE; + } + + transcolor = pnm_parsecolor(colorspec, cmapP->pam.maxval); + pnm_lookuptuple(&cmapP->pam, cmapP->tuplehash, transcolor, &found, + &presortColorindex); + + if (found) { + cmapP->haveTransparent = TRUE; + cmapP->transparent = cmapP->perm[presortColorindex]; + } else if (!exact) { + cmapP->haveTransparent = TRUE; + cmapP->transparent = + cmapP->perm[closestColor(transcolor, &cmapP->pam, cmapP)]; + } else { + cmapP->haveTransparent = FALSE; + pm_message("Warning: specified transparent color " + "does not occur in image."); + } + } else if (usingFakeTrans) { + cmapP->haveTransparent = TRUE; + cmapP->transparent = fakeTransparent; + } else + cmapP->haveTransparent = FALSE; + + reportTransparent(cmapP); +} + + + +static unsigned int +sortOrder(tuple const tuple, + struct pam * const pamP) { + + if (pamP->depth < 3) + return tuple[0]; + else + return ((tuple[0] * MAXCMAPSIZE) + tuple[1]) * MAXCMAPSIZE + tuple[2]; +} + + + + +static void +sortColormap(bool const sort, + struct cmap * const cmapP) { +/*---------------------------------------------------------------------------- + Sort (in place) the colormap *cmapP. + + Create the perm[] and permi[] mappings for the colormap. + + 'sort' is logical: true means to sort the colormap by red intensity, + then by green intensity, then by blue intensity. False means a null + sort -- leave it in the same order in which we found it. +-----------------------------------------------------------------------------*/ + tuple * const color = cmapP->color; + int * const perm = cmapP->perm; + int * const permi = cmapP->permi; + struct pam * const pamP = &cmapP->pam; + unsigned int const cmapSize = cmapP->cmapSize; + + unsigned int i; + + /* We will sort permi[]. So we first set up permi[] to reflect the + original, unsorted order. + */ + for (i=0; i < cmapSize; i++) + permi[i] = i; + + if (sort) { + pm_message("sorting colormap"); + for (i = 0; i < cmapSize; ++i) { + unsigned int j; + for (j = i+1; j < cmapSize; ++j) { + if (sortOrder(color[permi[i]], pamP) > + sortOrder(color[permi[j]], pamP)) { + + sample tmp; + + tmp = permi[i]; permi[i] = permi[j]; permi[j] = tmp; + } + } + } + } + for (i = 0; i < cmapSize; ++i) + perm[permi[i]] = i; +} + + + +static void +addToColormap(struct cmap * const cmapP, + const char * const colorspec, + unsigned int * const newIndexP) { +/*---------------------------------------------------------------------------- + Add a new entry to the colormap. Make the color that specified by + 'colorspec', and return the index of the new entry as *newIndexP. + + 'colorspec' is a color specification given by the user, e.g. + "red" or "rgb:ff/03/0d". The maxval for this color specification is + that for the colormap *cmapP. +-----------------------------------------------------------------------------*/ + tuple const transcolor = pnm_parsecolor(colorspec, cmapP->pam.maxval); + + unsigned int const colorIndex = cmapP->cmapSize++; + + cmapP->color[colorIndex] = pnm_allocpamtuple(&cmapP->pam); + + if (cmapP->pam.depth < 3) { + if (!pnm_rgbtupleisgray(transcolor)) + pm_error("Image is grayscale, but color '%s' is not gray. " + "It is (%lu, %lu, %lu)", + colorspec, + transcolor[PAM_RED_PLANE], + transcolor[PAM_GRN_PLANE], + transcolor[PAM_BLU_PLANE]); + else + cmapP->color[colorIndex][0] = transcolor[0]; + } else { + pnm_assigntuple(&cmapP->pam, cmapP->color[colorIndex], transcolor); + } + *newIndexP = colorIndex; +} + + + +static void +colormapFromFile(char const filespec[], + unsigned int const maxcolors, + tupletable * const tupletableP, + struct pam * const mapPamP, + unsigned int * const colorCountP) { +/*---------------------------------------------------------------------------- + Read a colormap from the Netpbm file filespec[]. Return a + tupletable of the colors in it (which is practically a colormap) as + *tupletableP and the format of those tuples as *mapPamP. Return + the number of colors as *colorsCountP. +-----------------------------------------------------------------------------*/ + FILE * mapfileP; + tuple ** colors; + unsigned int colorCount; + + mapfileP = pm_openr(filespec); + colors = pnm_readpam(mapfileP, mapPamP, PAM_STRUCT_SIZE(tuple_type)); + pm_close(mapfileP); + + pm_message("computing other colormap ..."); + + pnm_computetuplefreqtable(mapPamP, colors, maxcolors, &colorCount); + + *colorCountP = colorCount; + + pnm_freepamarray(colors, mapPamP); +} + + + +static void +computeColormapFromInput(struct pam * const pamP, + unsigned int const maxcolors, + unsigned int const nInputComp, + struct pam * const mapPamP, + unsigned int * const colorCountP, + tupletable * const tuplefreqP) { + + tupletable tuplefreq; + + pm_message("computing colormap..."); + + tuplefreq = pnm_computetuplefreqtable3( + pamP, NULL, maxcolors, nInputComp, pamP->maxval, colorCountP); + + *mapPamP = *pamP; + mapPamP->depth = nInputComp; + + *tuplefreqP = tuplefreq; +} + + + +static void +computeLibnetpbmColormap(struct pam * const pamP, + bool const haveAlpha, + const char * const mapfile, + tuple * const color, + tuplehash * const tuplehashP, + struct pam * const mapPamP, + unsigned int * const colorCountP) { +/*---------------------------------------------------------------------------- + Compute a colormap, libnetpbm style, for the image described by + 'pamP', which is positioned to the raster. + + If 'mapfile' is non-null, Use the colors in that (Netpbm) file for + the color map instead of the colors in 'pamP'. + + Return the colormap as color[] and *tuplehashP. Return the format + of those tuples as *mapPamP. + + The tuples of the color map have a meaningful depth of 1 (grayscale) or 3 + (color) and *mapPamP reflects that. + + While we're at it, count the colors and validate that there aren't + too many. Return the count as *colorCountP. In determining if there are + too many, allow one slot for a fake transparency color if 'haveAlpha' + is true. If there are too many, issue an error message and abort the + program. +-----------------------------------------------------------------------------*/ + unsigned int const maxcolors = haveAlpha ? MAXCMAPSIZE - 1 : MAXCMAPSIZE; + /* The most colors we can tolerate in the image. If we have + our own made-up entry in the colormap for transparency, it + isn't included in this count. + */ + unsigned int const nInputComp = haveAlpha ? pamP->depth - 1 : pamP->depth; + /* Number of color components (not alpha) in the input image */ + + unsigned int i; + tupletable tuplefreq; + unsigned int colorCount; + + if (mapfile) { + /* Read the colormap from a separate colormap file. */ + colormapFromFile(mapfile, maxcolors, &tuplefreq, mapPamP, + &colorCount); + + if (mapPamP->depth != nInputComp) + pm_error("Depth of map file (%u) does not match number of " + "color components in input file (%u)", + mapPamP->depth, pamP->depth); + if (mapPamP->maxval != pamP->maxval) + pm_error("Maxval of map file (%lu) does not match maxval of " + "input file (%lu)", mapPamP->maxval, pamP->maxval); + } else + computeColormapFromInput(pamP, maxcolors, nInputComp, + mapPamP, &colorCount, &tuplefreq); + + if (tuplefreq == NULL) + pm_error("too many colors - try doing a 'pnmquant %u'", maxcolors); + + pm_message("%u colors found", colorCount); + + for (i = 0; i < colorCount; ++i) { + color[i] = pnm_allocpamtuple(mapPamP); + pnm_assigntuple(mapPamP, color[i], tuplefreq[i]->tuple); + } + + /* And make a hash table for fast lookup. */ + *tuplehashP = + pnm_computetupletablehash(mapPamP, tuplefreq, colorCount); + + *colorCountP = colorCount; + + pnm_freetupletable(mapPamP, tuplefreq); +} + + + +static void +destroyCmap(struct cmap * const cmapP) { + + unsigned int colorIndex; + + for (colorIndex = 0; colorIndex < cmapP->cmapSize; ++colorIndex) + pnm_freepamtuple(cmapP->color[colorIndex]); + + pnm_destroytuplehash(cmapP->tuplehash); +} + + + +int +main(int argc, char *argv[]) { + struct cmdlineInfo cmdline; + FILE * ifP; + struct pam pam; + unsigned int bitsPerPixel; + pm_filepos rasterPos; + + struct cmap cmap; + /* The colormap, with all its accessories */ + unsigned int fakeTransparent; + /* colormap index of the fake transparency color we're using to + implement the alpha mask. Undefined if we're not doing an alpha + mask. + */ + + pnm_init(&argc, argv); + + parseCommandLine(argc, argv, &cmdline); + + verbose = cmdline.verbose; + + ifP = pm_openr_seekable(cmdline.input_filespec); + + pnm_readpaminit(ifP, &pam, PAM_STRUCT_SIZE(tuple_type)); + + pm_tell2(ifP, &rasterPos, sizeof(rasterPos)); + + computeLibnetpbmColormap(&pam, !!pamAlphaPlane(&pam), cmdline.mapfile, + cmap.color, &cmap.tuplehash, + &cmap.pam, &cmap.cmapSize); + + assert(cmap.pam.maxval == pam.maxval); + + if (pamAlphaPlane(&pam)) { + /* Add a fake entry to the end of the colormap for transparency. + Make its color black. + */ + addToColormap(&cmap, cmdline.alphacolor, &fakeTransparent); + } + sortColormap(cmdline.sort, &cmap); + + bitsPerPixel = pm_maxvaltobits(cmap.cmapSize-1); + + computeTransparent(cmdline.transparent, + !!pamAlphaPlane(&pam), fakeTransparent, &cmap); + + /* All set, let's do it. */ + gifEncode(&pam, stdout, rasterPos, + cmdline.interlace, 0, bitsPerPixel, &cmap, cmdline.comment, + cmdline.nolzw); + + destroyCmap(&cmap); + + pm_close(ifP); + pm_close(stdout); + + return 0; +} + + + +/*============================================================================ + Original version, named 'ppmgif' was by Jef Poskanzer in 1989, based + on GIFENCOD by David Rowley .A Lempel-Zim + compression based on "compress". + + Switched to use libnetpbm PAM facilities (ergo process PAM images) + and renamed 'pamtogif' by Bryan Henderson November 2006. + + The non-LZW GIF generation stuff was adapted from the Independent + JPEG Group's djpeg on 2001.09.29. The uncompressed output subroutines + are derived directly from the corresponding subroutines in djpeg's + wrgif.c source file. Its copyright notice say: + + Copyright (C) 1991-1997, Thomas G. Lane. This file is part of the + Independent JPEG Group's software. For conditions of distribution and + use, see the accompanying README file. + + The referenced README file is README.JPEG in the Netpbm package. + + Copyright (C) 1989 by Jef Poskanzer. + + 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. + + The Graphics Interchange Format(c) is the Copyright property of + CompuServe Incorporated. GIF(sm) is a Service Mark property of + CompuServe Incorporated. +============================================================================*/ -- cgit 1.4.1