This file: progressive.txt

This document describes the general guidelines for implementing progressive
object loading in XmHTML.

In particular it focuses on progressive image loading but contains a number
of general ideas as well.

The implementation itself is of a very asynchronous nature, so all routines 
*must* be fully re-entrant.


Table Of Contents
-----------------

0. Terminology

1. Progressive Image Loading

2. User Function Description
	2.1 The get_data() function
	2.2 The end_data() function

3. Progressive Loader Context

4. XmHTML's Image API and Progressive Image Loading

5. Implementing Progressive Image Loading in XmHTML

6. Changes to XmHTML in general

7. Changes to the Decoders

8. Changes to the image composition routines


0. Terminology
--------------
alpha channel: a series of pixel values in an image used to compute partial
  pixel transparency. Used to provide fade in/out effects. An alpha channel
  can be seen as viewing the actual image thru ``foggy'' glasses.

clipmask: a ``window'' thru which the image is seen. A clipmask is used by
  XmHTML to make images appear transparent.

colorspace: a term used to describe how colors in an image are composed.
  In the X window system, a color is composed of three components: red, green
  and blue (RGB). These components can be viewed as a cube where each of the
  principal axis's represent a component of a color (hence the term colorcube).
  A color is thus identified by its spatial position in this colorspace and
  is uniquely defined by its three components. This colorcube is the RGB
  colorspace. The indexed colorspace is a 1D representation of the RGB
  colorspace, in which each RGB triplet is assigned a unique number. As such
  it is actually nothing more than a lookup table. The grayscale colorspace
  is a colorcube in which all principal axis's coincide and thus forming a 1D
  colorspace. This 1D colorspace is not equal to the indexed colorspace since
  the components of a color in this one-dimensional colorspace all have the
  same value and hence the size of this colorspace is three times smaller than
  the indexed colorspace.

histogram: a table representing the color usage in an image. Used to perform
  color reduction.

interlaced: a way to store image data. An interlaced image is made up of a
  number of planes (which can be seen as venetian blinds), where each plane
  contains a portion of the final image. The final image is created by
  laying all planes on top of each other (closing the blinds). Interlacing
  is used to offer a preview of an image while it is being created (fancy
  image viewers can convert each interlaced plane to a full image by expanding
  pixels, giving the look of a blocky image which is refined with each pass.
  Other cool use of interlacing allows the storage of a background image which
  becomes visible on the last pass).

scanline: a single line of image data.

quantization: reduction of the number of colors in an image. Also known as
  dithering.


1. Progressive Image Loading
----------------------------

Progressive Image reading is supported for the following image types and
colorspaces:

- GIF and GZF (all types), all colorspaces;
- JPEG, indexed & grayscale, RGB when using a fixed palette on direct-indexed 
  displays (TrueColor/DirectColor);
- PNG, indexed & grayscale, RGB when using a fixed palette on direct-indexed
  displays (TrueColor/DirectColor).

It is not supported for the body image in a HTML document.

Progressive image loading can only start when the colormap used by the image
has been read *and* if it does not use more colors than allowed.

In all other cases (except PNG images with a histogram chunk), progressive
reading is impossible as in advance we do not know how many colors the image
will be using and thus any attempt to perform color quantization is useless.

The general outline is as follows:

1. Set up a function which is able to transfer a given amount of data from
   the image stream to the progressive loader. This function must return
   DATA_ABORT when it wants to abort progressive reading. It must return
   DATA_SUSPEND when at the time of call newly received data isn't sufficient
   to comply with the requested amount of data while it must return a positive
   number when the requested amount of data can be and is provided;
   (this function will be referred to as get_data())

2. obtain required image information (width, height, no of colors, colormap, 
   type of colorspace);

3. Check colorspace and size of colormap. When we have an RGB colorspace,
   set up a default colormap (with evenly spaced RGB components). If the image
   contains more than the allowed no of colors, switch to default processing
   here. For PNG images with a histogram present, switch libpng into dithering
   mode.
   Obtain the number of passes required if the image is interlaced.
   The number of scanlines equals the height of the image.

4. allocate destination memory and allocate all colors used by the image.
   Allocate an XImage which will receive the data while the image is being
   read. Allocate a destination drawable which is to receive the processed
   data. This destination drawable (useally a Pixmap for the X Window System)
   is initially initialized to reflect the current background setting.

   When the image is transparent, allocate a fully opaque clipmask.
   When the image contains an alpha channel, obtain the background color or
   the colormap used by the background image.

   Note on color allocation: for transparent images, all colors can be
   allocated before step 5 begins. For alpha channel images, colors can only
   be allocated when requested as proper alpha channel processing involves
   color manipulation at the component level.

5. Start progressive reading. In general this will be done by code along
   the following lines:

	Boolean done = False;
	while(pass < passes_required && !done)
		while(scanline < image_scanlines && !done)
		{
			switch(read_scanline(&data))
			{
				case DATA_ABORT:
					done = True;
					break;
				case DATA_END:
				case DATA_SUSPEND:
					[set a status flag according to the return value of the
					 read_scanline() function so XmHTML will known what to do
					 when the scanline is to be read]
					break;
				default:
					transfer_scanline(data);
					[update status flag];
					break;
			}
		}
		done;
	done;
   
   The read_scanline() function is an image-specific function which needs
   to be able to read both regular and interlaced images. For interlaced
   images, it must translate each scanline read to a scanline covering the
   entire width of the image (which possibly includes combining a previous
   scanline with the current scanline). When the image being processed is an
   RGB image and a fixed palette is present, it must also perform a mapping
   from RGB colorspace to indexed colorspace.
   When this function requires more data, it will call the get_data()
   function mentioned in step 1.

   The transfer_scanline() function transfers each scanline to the frame
   buffer. For all images, it must save each scanline for reuse when the image
   has been read. For transparent images, it must update the clipmask to
   reflect the transparent pixels in the scanline being processed. When the
   image contains an alpha channel, it must combine the background RGB values
   with the RGB values corresponding to each pixel in the scanline.
   When this has been performed, the corresponding pixel value is stored in
   the XImage. When the scanline has been processed, this routine transfers
   the updated portion of the XImage to the destination drawable.

   When the read_scanline() function returns DATA_ABORT, progressive reading
   is terminated and the image is possibly replaced with the "delayed image"
   icon (a boomerang).

   The actual implementation will be slightly more complicated as each
   loop will be performed by different functions which allow a breakdown of
   progressive image loading into different chunks at a time. This will become
   clear in the Progressive Loader Context description below.

6. Terminate progressive reading. The accumulated, decoded, image data stored
   by the transfer_scanline() function is promoted to the final image data.
   This final image data will then be available for reuse when the image needs
   to be recreated. Any allocated intermediate storage and structures are
   to be destroyed.
   During this step a user-installed function can also be called to signal
   the caller that the image has been processed (this function will be
   referred to as end_data()). It is advisable for the user to install
   such a function as this is the only way by which a user will be informed
   about the removal of this PLC, regardless of the current state of this PLC.


2. User Function Description
----------------------------

2.1 The get_data() function

   This is a user-installed function used by a progressive loader to obtain
   an amount of data from a data stream.

   Proposed prototype:
	typedef int (*XmHTMLGetDataProc)(XmHTMLPLCStream, XtPointer);

   Where:
	XmHTMLPLCStream *stream:
		a structure containing data about the data stream from which data
		is requested.
		This structure should include at least the following information:
		- a user_data field so the user can identify this stream;
		- a count of the number of bytes received so far. This number should
		  be used to compute the proper offset in the real data stream. It
		  can be used for backtracking purposes as well
		- a minimum request size;
		- a maximum request size;

	XtPointer buffer:
		a pre-allocated destination buffer. Data requested by this function
		is to be placed in this buffer. The number of bytes copied into
		this buffer *must* lie between the minimum and maximum request size;

   Possible return values:
		STREAM_ABORT
			indicates progressive reading is to be aborted. Data copied into
			buffer is ignored. Depending on the amount of data received so far,
			the portion of the received image is either displayed or replaced
			by a "delayed image" icon.
		STREAM_SUSPEND
			indicates progressive reading should be suspended for the given
			context. Data copied into the buffer is ignored. When this value
			is returned, the progressive loader will call this function again
			at a later time.
		STREAM_END
			indicates no more data is available. This is *not* the same
			as returning STREAM_ABORT as in this case the progressive loader
			will consider the object loaded and act accordingly.
		<any positive number>
			the amount of bytes actually copied into buffer. This indicates
			that the requested amount of data was available and has been
			copied into the buffer. For obvious reasons, this value may
			*never* be larger than the maximum request size. Also it may
			not be smaller than the minimum request size.

   Please note that returning 0 is equivalent to returning STREAM_END.

   Proposed Resource:
	XmNprogressiveReadProc

   Note1:
	For performance reasons, the amount of bytes copied by this function should
	not differ too much from the requested amount of data. XmHTML will
	calculate an optimal length as to reduce the number of function calls
	(and data backtracking as well). This length is very likely to be the
	size of one or more scanlines at a time (how do we do this when the image
	data is compressed???).

   Note2:
	Although the term image is used frequently, this function will also be
	used by XmHTML for progressive loading of other data streams (such as
	a HTML document itself, which is the next logical step...).
	Therefore it's implementation should be independent on the type of object
	that is to being loaded. 

2.2 The end_data() function

   This is a user-installed function, called when the entire object has been
   processed or when the get_data() function returns DATA_ABORT.

   Proposed prototype:
	typedef void (*XmHTMLEndDataProc)(XmHTMLPLCStream, XtPointer, int, Boolean)

   Where:
	XmHTMLPLCStream *stream:
		same structure as above;
	XtPointer object_data:
		information about the loaded object. This argument can be NULL.
	int object_type:
		a number identifying the type of object_data. Currently this can only
		be XmIMAGE, although other values are very well possible in the
		future.
		When this argument has the value XmIMAGE, the object_data argument
		represents a pointer to a structure of type XmImageInfo. This is a
		read-only structure and can be used by the caller for caching purposes.
	Boolean success:
		This argument indicates whether or not progressive loading has
		successfully completed. When it is False, progressive loading has
		been aborted by an internal error or it was aborted explicitly.
		If there are any outstanding PLCStreams when a new document is set
		into the widget, this function will be called for each of the
		remaining PLCStreams with success == False. It is the callers
		responsibility to remove all resources that were allocated to this
		PLCStream.

   Proposed Resource:
	XmNprogressiveEndProc

   Note:
	This function may not return a value.

A convenience function for aborting progressive image loading should also
be provided:

	XmHTMLImageAbortProgressiveLoading(Widget html);

This function should terminate and remove any outstanding PLCStreams.

Similar functions should be added for each PLC type supported, e.i., for
progressive loading of documents, the following convenience function should
be added:

	XmHTMLTextAbortProgressiveLoading(Widget html);

3. Progressive Loader Context
-----------------------------
In order for progressive loading to work properly, the progressive loader
must maintain information about the object that is being loaded. This
information is grouped in a special structure, referred to as the Progressive
Loader Context (or PLC for short).

XmHTML needs to maintain a list of PLC's internally and activate each one
in turn. The frequency with which XmHTML will check this list should be a
user-adjustable time in milliseconds.

A PLC is divided in two sections: object-specific data and PLC status
information.

For progressively loaded images, the object-specific data should be a pointer
to a structure containing at least the following information:

- an object identifier. This should be the first member for all object-specific
  structures stored in a PLC.
- an identifier for the image being loaded (name or location);
- the type of the image being loaded;
- the type of colorspace for this image (COLOR_SPACE_INDEXED,
  COLOR_SPACE_GRAYSCALE, COLOR_SPACE_RGB);
- transparency/alpha channel identified: TRANSPARENCY_NONE,
  TRANSPARENCY_BACKGROUND, TRANSPARENCY_ALPHA.
- colormap used by this image and the number of colors in this image;
- information on the current background setting;
- width and height of this image;
- depth of this image;
- a buffer to contain all decoded image data (useally of size width*height);
- a buffer to contain all image information mentioned in step 2;
- for interlaced images, total number of passes required;
- number of scanlines required on each pass;
- an XImage;
- a destination drawable;
- if applicable, clipmask storage and drawable;
- a field for containing gamma information;
- for interlaced images, number of passes processed so far;
- number of scanlines processed so far;
- a to be defined number of fields specific for the image that is being loaded
  (used by the image-specific decoders).

The second section should include at least the following information:
- two pre-allocated buffers for use with the get_data() function:
  one is to be used for backtracking/row combining purposes while the other
  will be the destination buffer to the get_data() function;
- number of bytes received so far;
- number of bytes required;
- information about the current status of this PLC: ACTIVE, SUSPENDED, ABORTED,
  COMPLETED;
- a pointer to the user-installed get_data() function (provided by the new
  XmNprogressiveReadFunc resource);
- last returned value of the get_data() function;
- a pointer to the user-installed end_data() function (provided by the new
  XmNprogressiveEndFunc resource);
- a field for storing user_data;

The second section should also contain three pointers to image-specific
functions. They are:
- a pointer to a function for obtaining the image information mentioned in
  step 2 above;
- a pointer for reading scanlines from an image;
- a pointer to terminate/abort progressive image loading.

It should also contain a pointer to the function that does the actual XImage
composition.

Finally it should also contain an identifier for the lastly activated function
so XmHTML will known which function to call the next time a PLC is activated.


Meaning of the status information flags:
  ACTIVE:
	indicates the PLC is active and that it should make a request for
	new data from the image stream the next time this PLC is activated;
	When the get_data() function is other than 0 or a positive number
	(reflecting the number of bytes copied into the buffer), the status of
	the PLC is changed to reflect the return value from this function (e.i.,
	SUSPENDED when DATA_SUSPEND is received and ABORTED when DATA_ABORT
	is received).
  SUSPENDED:
	indicates the PLC has been suspended and that it should make the *same*
	request for new data from the image stream next time this PLC is activated;
	When the get_data() function returns DATA_OK, the status of the PLC is
	promoted to ACTIVE.
  ABORTED:
	indicates the PLC has been aborted and that it should either save the
	amount of data received so far or replace it with a "delayed image" icon.
	Calls the end_data() function.
  COMPLETED:
	indicates the PLC has received the entire image and that it should be
	terminated the next time this PLC is activated. When this happens, the
	image data stored in the PLC is transferred to corresponding internal
	XmHTML structures and the end_data() function is called. The last action
	performed by a PLC is to remove itself.


4. XmHTML's Image API and Progressive Image Loading
---------------------------------------------------

To keep XmHTML's image API simple, progressive image loading can be achieved
by adding one additional flag to the XmIMAGE option flags: XmIMAGE_PROGRESSIVE.
A user_data field should also be added to the XmImageInfo structure.

This allows a user to easily extend the function installed for the XmNimageProc
resource to deal with both images already present locally and images that are
being transferred from a remote site.

An example implementation could be along the following lines:

XmImageInfo *loadImage(Widget w, String image)
{
	if(image in cache)
		return(cached image);

	if(image locally)
		return(XmHTMLImageDefaultProc(html, image, NULL, 0));

	if(image remotely)
	{
		XmImageInfo *p_image;

		[set up a connection with the remote site and save its handle]

		p_image = (XmImageInfo*)calloc(1,sizeof(XmImageInfo));
		p_image->url = strdup(image);
		p_image->options = XmIMAGE_PROGRESSIVE;
		p_image->user_data = (XtPointer)connection_handle;
		return(p_image);
	}
	
	[if we get here, the image is neither locally nor remotely, return
     either NULL or switch to delayed image loading if the connection is
     extremely slow].
}

A corresponding get_data() function could be the following:

int get_data(XmHTMLPLCStream *stream, XtPointer buffer)
{
	int min_out, max_out, buf_pos;
	int length, bytes_avail;

	[obtain connection_handle from the context (user_data field). Probably
	 involves getting a handle to the buffer used by the connection to store
	 incoming data] 

	if(connection broken)
	{
		[close connection and do other cleanup]
		return(XmPLC_STREAM_ABORT);
	}

	bytes_avail = [number of bytes received from connection so far]

	if(all data received from connection)
	{
		[close connection and do other cleanup]
		return(XmPLC_STREAM_END);
	}

	min_out = stream->min_out;	/* minimum request size */
	max_out = stream->max_out;	/* maximum request size */
	buf_pos = stream->total_in;	/* bytes copied so far */

	/* compute no of bytes to copy */
	length = bytes_avail - buf_pos;

	/* more than min_size bytes available */
	if(length > min_out)
	{
		/* check that we do not copy more than max_size bytes */
		if(length > max_out)
			length = max_out;

		/* copy data from connection buffer to outgoing buffer */
		memcpy(buffer, [connection buffer] + buf_pos, length);
		
		[possibly update the connection buffer to reflect the number of
		 bytes copied as well]

		return(length);
	}
	else /* not enough data available yet */
		return(XmPLC_STREAM_SUSPEND);
}

To prevent problems later on, none of the XmHTMLPLC context members may
be used by the current PLC when this function returns. The only purpose of
the XmHTMLPLCStream object is to keep the interface simple and to allow
easy extension of the get_data() function without having the need to modify
the get_data prototype.

And a corresponding end_data() function could be:

void end_data(XmHTMLPLCStream *stream, XtPointer object, int object_type,
	Boolean success)
{
	[obtain connection_handle from the context, close this connection and
     do other cleanup]

	if(success == False)
	{
		[Progressive loading was aborted for whatever reason. Depending on
		 the value of the stream->total_in value you can decide whether
		 or not you want to keep the object data.]
	}

	if(object_type == XmIMAGE)
	{
		[either store object (which will be of type XmImageInfo) in a local
         cache or ignore it.]
	}

	[unknown/unsupported object_type, ignore]	
}

As can be seen from the above example implementations it is very easy for
a user to implement progressive image loading (apart from the connection
routines involved).

5. Implementing Progressive Image Loading in XmHTML
---------------------------------------------------

The implementation of progressive image loading in XmHTML requires a number
of changes to the GIF, PNG and JPEG decoders and the image composition
routines. Changes to the painter will not be required as a drawable will be
present from the moment an image is to be loaded progressively.

6. Changes to XmHTML in general
-------------------------------
Define the exact contents for a PLC and it's object data. Add routines to
create, walk and destroy them. Walk the list of PLC's using a timer (with a
user-adjustable interval?).

All PLC's will be placed in a ringbuffer where the PLC walking routine calls
the various functions in a PLC as they are necessary.

7. Changes to the Decoders
--------------------------
These will be rather minimal: the GIF, GZF, PNG and JPEG decoders can already
deal with interlaced images and already read their data a scanline at a time.
they also contain seperate sections for obtaining the image information
described in step 2 in the general outline.

According to the PLC, the changes required are:

- place the sections that are responsible for obtaining the image information
  in a seperate routine (if not already done). Determine if it is feasible to
  use these routines for both normal and progressive image loading.

- place the scanline reading sections in seperate routines as well. Also
  determine the feasibility of using these routines for both normal and
  progressive image loading.

- add routines that perform cleanup when progressive image loading is aborted
  or has ended.

How this will work with the GIF workaround is a mystery at this moment. One
way is to decode the GIF data using my workaround when a clearCode is received,
but this will lead to a *considerable* delay when doing progressive image
loading on fast connections. On slow connections it will not make that much
difference.

8. Changes to the image composition routines
--------------------------------------------
These will be rather large: actual image composition has to be split into
seperate routines for several display depths (this is preferable for 
performance reasons?).

- color allocation, XImage and drawable (and possibly clipmask as well)
  creation must be moved to the top instead of being one of the final stages;
- set up routines to convert the image data to the format understood by an
  XImage.
- vertical image scaling poses a problem. Horizontal is no problem as we
  are dealing with scanlines. Maybe vertical scaling should be used to compute
  an interval when performing the outerloop in step 5 of the general outline?
- set up routines that copy the updated portion of the XImage to the
  destination drawable. It might be very wise to use the MIT-SHM extension if
  it's present. Also add code to update the screen directly (maybe use
  XPutImage directly on the display instead of XCopyArea from drawable to
  display?)
- add a routine to perform cleanup when progressive image loading has been
  aborted.
- add a routine to transform the data contained in a PLC to an XmHTMLImage
  structure and to update the information in the XmImageInfo structure
  representing the progressively loaded image.


--- End of Document ---
Author       : Koen
Date         : Tue Jun 10 04:51:23 GMT+0100 1997
Revision     : 1.1
Revision Date: Sat Jun 14 18:47:19 GMT+0100 1997