This file: README for gzf

Contents
--------

1.  Introduction
2.  Why an alternative GIF format?
3.  GZF Compressed Raster Data
4.  GIF -> GZF conversion
5.  GIF LZW -> compress LZW Translation
6.  Decoding GIF LZW raster data using the LZWStream package
7.  Programming Example
8.  Using the LZWStream package in your own applications
9.  Using gif2gzf to convert gif images to gzf images
10. Reading GZF Images
11. License
12. Author, contact information and where to get it

1. Introduction
---------------
GZF is a graphics format very similar to CompuServe's GIF graphics format.

The Gif graphics format has been around since 1987, when CompuServe published
the Graphics Interchange Format definition (also known as GIF87a). It defines
an open standard for exchanging graphics, in which the image data is stored in
a compressed raster format. The problem with the GIF specification lies in the
compression method that is used to compress and decompress the image data. The
Lempel-Ziv-Welch algorithm used for both compression *and* decompression is
patented by Unisys under US patent no. 4,558,302. 

Unisys claims to only have found out of the use of LZW in the gif specification 
in 1993 (although there are strong indications they have known since 1989) and 
since then they are denying the use of LZW without a license in all types of
both freeware and commercial software. Their point of view regarding the use of
LZW in freeware is a totally outrageous one: it requires writers of freeware to
obtain a license (at the price of 1,000$ in 1997) and to give Unisys $0.10 for
every copy of their software that is used. The situation for commercial
software doesn't differ much and is in some aspects even worse. If you are
writing a commercial software library, you must obtain a 1,000$ license from
Unisys before you can even begin to think about selling your product. And even
if you have a license, you can *only* sell your product to other users when
they have also obtained a license from Unisys at the same price...

Clearly, Unisys doesn't know what it is doing. If they pursue this policy it
will mean the end of GIF.

The GZF format described in this document does not suffer from this decrepancy
in the GIF specification, while keeping the required changes to the GIF format
to a minimum. In fact, the only difference between GZF and GIF is the format of
the compressed data. The GZF format stores the compressed raster data in the
deflate format (as described in RFC 1951). This format is used in various
public domain compression packages such as zlib, gzip and Info-Zip.

We have chosen to use zlib as a way to achieve compression and decompression of
the raster data, since zlib is the only library with the most open license. The
zlib license allows usage of zlib in both freeware and commercial software
without requiring any license or licensing fees. Both the gzip and Info-Zip
license allow use of their algorithms in freeware without a license but
restrict the use for commercial purposes.

2. Why an alternative GIF format?
---------------------------------

Since the GIF controversy first surfaced, there have been several attempts to
define a new GIF format, but all have been abandoned in favor of the PNG
graphics format. This PNG format is superior to the GIF format, but it is not
a replacement for the GIF format. Therefore a number of features of the GIF
format are not supported by the PNG format. One of the most eye-catching
features of the GIF specification which is not present in the current PNG
specification is that a GIF image can contain multiple images in a single file.
When these images are displayed sequentially, an animation results.

Since Netscape introduced support for these GIF animations, they have come to
become a widely used element on the World Wide Web, where they are used to
flourish otherwise static HTML documents.

While Netscape made a strong marketing move by adding animated GIF support to 
their browser, it has also prevented a rapid replacement of the GIF image
format with the PNG image format. Netscape is probably a company which can
afford a LZW license, but many software developers can not. The only way in
which many software developers can still support GIF images while not required
a LZW license is an alternative GIF format. The GZF format described in this
document provides this alternative.

The routines contained with the GZF code allow developers to create and read
GZF images, and, more important, it also provides a way to read GIF images
without requiring a LZW license.

3. GZF Compressed Raster Data
-----------------------------

The raster data in the GZF image format is compressed into the ``deflate'' data
format. This format is described in rfc1951.txt, of which the Abstract is shown
below:

   This specification defines a lossless compressed data format that is
   compatible with the widely used GZIP utility.  The format includes a
   cyclic redundancy check value for detecting data corruption.  The
   format presently uses the DEFLATE method of compression but can be
   easily extended to use other compression methods.  The format can be
   implemented readily in a manner not covered by patents.

Especially the last sentence is of importance, it means that any software
developer can write a deflate compressor/decompressor without having to fear
a lawsuit.

To remain compliant with the Gif specification, the compressed raster data is
stored in blocks of 0 to 255 bytes preceeded with a character count. A block
with a zero byte count terminates the raster data stream.

4. GIF -> GZF conversion
------------------------

To convert existing gif images to gzf images, the following conversion method
is proposed:

1. Compare the first six bytes of the file to either GIF87a or GIF89a. Gif
   images are always identified by one of these magic numbers. If the file
   is a gif file, proceed and else terminate;
2. read and write the screen descriptor;
3. read and write a possibly global colormap;
4. read and write all extension blocks up to the first compressed raster data
5. read a compressed raster data block
6. convert the compressed raster data to a format understood by the standard
   Unix "compress" utility;
7. uncompress the converted, but still compressed, raster data by feeding it
   to the "compress" utility;
8. compress the uncompressed raster data using the zlib function compress and
   store the returned, compressed raster data in a temporary buffer;
9. repeat steps 4 till 8 until a block with a zero byte count is encountered;
10.write the temporary buffer in blocks of 256 bytes;
11.write the gif terminator character and terminate conversion.

The "compress" utility mentioned in steps 6 and 7 uses a slightly modified
version of the LZW algorithm, which is also patented. By converting the
compressed data rather than uncompressing it using a LZW algorithm introduces
a performance penalty, but it *ensures* that your application does not have to
use the dreaded LZW algorithm but can instead rely on the presence of the
"compress" utility. You are almost guarenteed of the presence of this utility
since it is a standard tool on *every* Unix distribution.  If for some reason,
compress should not be present on your system, the public domain compress and
gzip compression tools can mimic uncompress. See the Translation section below
for more details.

The gif2gzf source code implements the above method.

5. GIF LZW -> compress LZW Translation
--------------------------------------

The translation process takes care of some minor differences between the GIF
compressed data and the compress compressed data.

The GIF LZW format uses dynamic clear code and end-of-data code whereas
compress uses a static clear code and doesn't have an end-of-data code.

The dynamic stream codes in GIF are determined by the value of the "code size".
This code size is a value indicating the minimum number of bits required
to represent the set of actual pixel values. The value of clear code is given
by <code size>^2, and the end-of-data code is defined as <clear code>+1.
The first available compression code value is <clear code>+2.

The main difference however concerns the minimum code size specification in
compressed data. This number controls the generation of the LZW codes in the
compressed data. While GIF images use anything between 3 to 12 bits, compress
only works between 8 and 16 (maximum codeSize for compress, the minimum-maximum
is 12). This means that the conversion process must make a distinction between
the code size: anything below 8 and 8 or above.

The latter case is quite easy: the gif LZW codes are simply copied to compress
output with possible adjustment of the aforementioned codes. The first case
involves a lot more work as the 2 to 7 bits LZW codes need to be transformed
to 8 bit codes. This conversion process actually comes pretty close to
violating the LZW patent, but since only the LZW codes are read, adjusted and
packed again the gzf gif decoder is patent-safe.


6. Decoding GIF LZW raster data using the LZWStream package
-----------------------------------------------------------

The gzf source code comes with a package that uncompresses the LZW compressed
raster data in gif images by using the "compress" utility. Proper use of this
package requires you to understand the GIF format (the Gif87a and Gif89a
specification can be found in the docs directory).

The LZWStream package only decodes gif raster data and does not provide a
way to read an entire gif image.

An LZWStream is created by using the LZWStreamCreate function:

LZWStream *LZWStreamCreate(ib, zCmd)
	ImageBuffer *ib;
	char *zCmd;

ImageBuffer is a memory object which is used to mimic file access but in
memory, which can provide a substantial speedup. An ImageBuffer is created
by using the ImageFileToBuffer(char *file) function, where "file" represents
the file that is to be loaded.

zCmd is the name of the "uncompress" program that is to be used. If NULL is
specified, the LZWStream package will default to "uncompress". This argument
can be used to specify an alternative LZW decoder, such as gzip.

When LZWStreamCreate returns successfully, you need to set two read functions:
readOK and getData.

The proto's for these functions are:

size_t (*readOK)(ImageBuffer*, unsigned char*, int);
size_t (*getData)(ImageBuffer*, unsigned char*);

The code in buffer.c offers two default functions:

size_t ReadOK(ib, buf, len)
	ImageBuffer *ib;
	unsigned char *buf;
	int len;

This function copies len characters from ib to buf and returns the number of
characters copied. It returns 0 when the end of the current ImageBuffer is
reached.

size_t GifGetDataBlock(ib, buf)
	ImageBuffer *ib;
	unsigned char *buf;

This function retrieves an the contents of an entire block of data found in
a gif image. Gif data blocks consist of a single byte with a character count,
followed by the specified number of bytes. The above function reads the
character count and copies the requested number of bytes in the given
destination buffer. An ImageBuffer is destroyed by using the
FreeImageBuffer() macro.

Feel free to replace these default functions with your own readers.

When you have reached the point were you want to obtain the decompressed
raster data, you *must* call the following function:

int LZWStreamInit(lzw)
	LZWStream *lzw;

lzw is the LZWStream returned by LZWStreamCreate. This function returns
1 when the stream was successfully initialized or something else when an
error occurs.

The next step is to convert the gif LZW compressed raster data to the
LZW format used by "compress". This is done by the following function:

void LZWStreamConvert(lzw)
	LZWStream *lzw;


When this function returns, the data has been converted but not yet
uncompressed. The LZWStream package offers two functions to do this:

unsigned char *LZWStreamUncompress(lzw, len)
	LZWStream *lzw;
	int *len;

int LZWStreamFillBuffer(lzw, data, size)
	LZWStream *lzw;
	unsigned char *data;
	int size;

The first function decompress the converted data and returns it in an
allocated buffer. "len" is the size of the uncompressed data.

The second function also decompresses the converted data but allows you to
read it in seperate chunks. "size" is the number of bytes that should be read
and "data" is the destination buffer. You should make sure that the specified
destination buffer is large enough to hold "size" bytes. This function returns
the number of bytes copied into "data".

The final step is to destroy the LZWStream:

void LZWStreamDestroy(lzw)
	LZWStream *lzw;

This function removes any temporary files that were created and cleans up
the memory used by the given stream. It does not destroy the ImageBuffer
contained in it. When this function returns, "lzw" is no longer valid.

As a final note: the LZWStream structure contains a field called err_msg.
This field contains an error message whenever an error occured. You can
choose to display this message or ignore it. You may *not* free this
message, it points to a static data space.

7. Programming Example
----------------------

The following example demonstrates a possible use of the ImageBuffer and 
LZWStream objects.

#include "ImBuffer.h"		/* ImageBuffer structure & functions */
#include "LZWStream.h"		/* LZWStream functions */

unsigned char*
readGifImage(char *file)
{
	ImageBuffer *ib;
	LZWStream *lzw;
	unsigned char c, buf[280];

	ib = ImageFileToBuffer(file);

	/* read and check gif magic */
	ReadOK(ib, &buf, 6);
	{
		[ verify gif magic ]
	}

	/* read logical screen descriptor */
	ReadOK(ib, buf, 7);

	[ pull out necessary image attributes ]

	[ read the global colormap using the current ImageBuffer ]

	while(1)
	{
		/* read block identifier */
		ReadOK(ib, &c, 1);

		/* gif terminator */
		if(c == ';')
			break;

		/* a gif extension block */
		if(c == '!')
		{
			/* get extension type */
			ReadOK(ib, &c, 1);

			[ deal with it ]

			continue;	
		}
		if(c != ',')
			continue;	/* not a valid start character */

		/* read image descriptor */
		ReadOK(ib, buf, 9);

		[ pull out necessary information ]

		[ read a possible local colormap, again using the ImageBuffer ]

		/* create a new stream object */
		lzw = LZWStreamCreate(ib, NULL);

		/* initialize uncompression */
		LZWStreamInit(lzw);

		/* set read functions */
		lzw->readOK = readOK;
		lzw->getData = GifGetDataBlock;

		/* convert data */
		LZWStreamConvert(lzw);

		/* get uncompressed data */
		data = LZWStreamUncompress(lzw, &len);

		/* destroy stream */
		LZWStreamDestroy(lzw);

		/* we have our image */
		break;
	}
	/* free the ImageBuffer */
	FreeImageBuffer(ib);

	/* and return the image data */
	return(data);

}

The above is a very simple example which doesn't care about errors and
interlaced images. Obvious enhancements would be to add error checking on
every ReadOK call, dealing with multiple images and comparing the size of
the uncompressed raster data with the dimensions of this image. See
gif2gzf.c for a much more extensive example.

8. Using the LZWStream package in your own applications
-------------------------------------------------------
To use the LZWStream package in your own application, you need the following
files:

	- LZWStream.h: required typedefs and function prototypes
	- LZWStream.c: the LZW decompressor
	- ImBuffer.h : ImageBuffer typedefs and function prototypes
	- ImBuffer.c : ImageBuffer routines.

Compile LZWStream.c with -DNO_XMHTML defined.
Just add these files to your Makefile and you're done.

9. Using gif2gzf to convert gif images to gzf images
----------------------------------------------------
The gif2gzf utility converts a gif image to a gzf image. This tool is capable
of converting GIF87a, GIF89a, multi-image GIF87a, multi-image GIF89a and
multi-image GIF89a with the NETSCAPE2.0 loop extension.

The syntax to gif2gzf is as follows:

gif2gzf <giffile> <gzffile> [-v -p]

Where:
	giffile: name of giffile to convert
	gzffile: name of destination file

	-v: verify deflate compression by inflating the deflate compressed data
	-p: show progress count. Can be usefull when converting animated gifs.

gif2gzf is not capable of doing batch conversion, but you can write a simple
script that does just this.

If you are using a shell which knows the ``foreach'' command, you can do batch
conversion on the command line using the following sequence of commands:

hobbes [87][13:10] [/home/newt/src/libs/gzf/pics] >foreach file ( gif/*gif )
foreach? ../gif2gzf $file $file:r.gzf
foreach? end
gif/emailed.gif -> gif/emailed.gzf
Converted frame:       53
Size reduction: 29.72%
gif/techsup.gif -> gif/techsup.gzf
Converted frame:        0
Size reduction:  4.21%
....
hobbes [88][13:10] [/home/newt/src/libs/gzf/pics] >

That's about it.

10. Reading GZF Images
----------------------
Reading a GZF image is very similar to reading a GIF image. As was mentioned
in the introduction, the only difference between these formats is the way
in which the raster data is stored.

The following piece of code is based on giftoppm and shows how to decompress
and convert the GZF raster data to the actual image data.

static unsigned char *
ReadGZFImage(ImageBuffer *ib, int len, int height, int interlace)
{
	int xpos = 0, ypos = 0, nread, foo;
	static unsigned char *image, *data;
	register unsigned char *dp, *dPtr;

	/* uncompress GZF image data */
	data = UncompressGZFData(ib, len*height, &nread);

	/* sanity check */
	if(data == NULL || nread == 0)
		return(NULL);

	dPtr = data;

	/*
	* interlaced image. Need to alternate uncompressed data to create the
	* actual image.
	*/
	if(interlace)
	{
		int pass = 0, step = 8;
		int pass = 0, step = 8;
		register int i;

		/* allocate image storage */
		image = (unsigned char *)calloc(len * height, sizeof(char));

		for(i = 0; i < height; i++)
		{
			if(ypos < height)
			{
				dp = &image[len * ypos];
				for(xpos = 0; xpos < len; xpos++)
					*dp++ = *dPtr++;
			}
			if((ypos += step) >= height)
			{
				if (pass++ > 0)
					step /= 2;
				ypos = step / 2;
			}
		}
		/* no longer needed */
		free(data);
		return(image);
	}
	/* uncompressed data is same as image data */
	return(data);
}

The following routine does the actual decompression:

/*
* dsize is the size of the decompressed image data and nread will be
* updated to reflect the actual no of bytes uncompressed.
*/
static unsigned char*
UncompressData(ImageBuffer *ib, int dsize, int *nread)
{
	static unsigned char *output_buf;
	unsigned char buf[256], c;
	z_stream stream;
	int err;

	*nread = 0;

	/* Skip code size, it's never used */
	(void)ReadOK(ib, &c, 1);

	/* allocate output buffer */
	output_buf = (unsigned char*)calloc(dsize+1, sizeof(char));

	/* initialize inflate stuff */
	stream.zalloc = Z_NULL;
	stream.zfree  = Z_NULL;

	if((err = inflateInit(&stream)) != Z_OK)
	{
		fprintf(stderr, "inflateInit failed: %s\n", stream.msg);
		free(output_buf);
		return(NULL);
	}

	/* keep uncompressing until we reach the end of the compressed stream */
	while(True)
	{
		/* next compressed block of data */
		stream.avail_in = GifGetDataBlock(ib, buf);
		stream.next_in  = buf;
		/* update output buffer */
		stream.next_out = output_buf + stream.total_out;
		stream.avail_out = dsize - stream.total_out;

		/* uncompress it */
		err = inflate(&stream, Z_PARTIAL_FLUSH);

		/* check return value */
		if(err != Z_OK && err != Z_STREAM_END)
		{
			fprintf(stderr, "inflate failed: %s\n", stream.msg);
			free(output_buf);
			return(NULL);
		}
		/* and break if inflate has finished uncompressing our data. */
		if(err == Z_STREAM_END)
			break;
	}
	/*
	* Skip remaining data. The deflate format signals the end of compressed
	* data itself, so we never reach the zero-data block in the above loop.
	*/
	while((GifGetDataBlock(ib, buf)) > 0);

	*nread = stream.total_out;

	/* successfull uncompress, return uncompressed image data */
	return(output_buf);
}

11. License
-----------

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.

Copyright (C) 1994-1997 by Ripley Software Development 
All Rights Reserved

12. Author, contact information and where to get it.
----------------------------------------------------
The LZWStream package is written and maintained by Koen D'Hondt and is 
originally part of the XmHTML Widget, a LGPL'd Motif widget capable of
displaying HTML 3.2 documents. This widget has built-in support for various
types of images including gif and animated gif images.

If you have any comments, encounter problems, suggestions or just want to tell 
us how great this package is ;-) feel free to contact me. ripley@xs4all.nl

Koen D'Hondt
Ripley Software Development.

email: ripley@xs4all.nl
URL  : http://www.xs4all.nl/~ripley