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. 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