path: root/sys/plio/PLIO.hlp

.help PLIO Feb88 "Pixel List Package Design"
.ce
\fBThe IRAF Pixel List Package\fR
.ce
and
.ce
\fBIMIO Extensions to Support Image Masks\fR
.ce
Doug Tody
.ce
February, 1988
.ce
(Revised June 1988)


.NH
Introduction

    The pixel list package is a general package for flagging individual pixels
or regions of an image, to mark some subset of the pixels in an image.
This may be done to flag bad pixels, or to identify those regions of an image
to be processed by some applications program.  When the pixel list package is
used to flag the bad pixels in an image we call this a \fBbad pixel mask\fR,
or BPM.  When used to identify the regions of an image to be processed (or
ignored), we call the list a \fBregion mask\fR.

A pixel list may be viewed conceptually as either a list or an image; the list
is merely the compressed form of a virtual \fBmask image\fR.  Storing a mask
image as a list has two major advantages.
.ls
.ls [1]
Storage efficiency.  Simple masks may be stored very compactly, e.g., as small
arrays stored directly in an image header, or in a separate mask file or
database.
.le
.ls [2]
Runtime efficiency.  Storing a mask in list form has the advantage that one
can determine very quickly whether or not a given region of the image (e.g.,
an image line) contains any pixels in the mask.  The alternative, given a
fully populated mask image (or flagging the pixels directly in the data image),
requires that one examine every pixel in the mask image, which is very
inefficient for simple masks.
.le
.le

The pixel list technique for implementing image masks is the most efficient
choice only for simple or moderately complex masks.  As a mask image increases
in complexity there eventually comes a point where it would be simpler and
more efficient to use a conventional raster image to store the mask.
For example, if one wishes to associate a flag value (such as a weight) with
every pixel in an image, and the flag values vary rapidly in value across the
image, a separate image should probably be used (except that other forms of
data compression may be possible; the IRAF \fInoise function package\fR
addresses one aspect of this problem).

The pixel list related software is subdivided into two parts, the pixel list
package itself, and the extensions to IMIO to make use of the pixel list
package.  The pixel list package in itself is independent of IMIO and may be
used separately.

.NH
IMIO Support for Pixel Lists

    Most image applications tend to fall into two classes, the simple pointwise
transformation operators, and the more cpu intensive image analysis operations.
The simple operators usually operate upon the whole image (no mask required)
and may ignore the presence of bad pixels in the image, provided reasonable
artificial values have been provided for the bad pixels so that arithmetic
problems do not occur, and provided we keep track of the locations of the
bad pixels (by propagating the bad pixel lists), so that the bad pixel
information is available to subsequent image analysis programs.

The image analysis operators, on the other hand, must know the locations of
the bad pixels in order to exclude them from the fit.  The analysis is also
often performed only upon specified regions of the image, as indicated by some
sort of image mask.  Most image analysis algorithms are fairly cpu intensive,
hence as long as we can access the bad pixel list and region mask reasonably
efficiently, we would prefer a simple interface, e.g., for every buffer of
input image data read, an associated buffer the same size and dimensionality
as the input image data buffer, containing the bad pixel or region mask flag
values.

In general, if pixel lists are to be used with images, either IMIO must
provide direct support for pixel lists or the pixel list package must duplicate
much of the functionality of IMIO.  This is because the pixel list must
be defined in terms of the physical image, whereas an applications
program accessing an image via IMIO may be operating upon some user specified
section of the image.  To support applications transparent sectioning, boundary
extension, multiple input buffers, and so on, support for pixel lists must
be integrated into IMIO.

.NH 2
Mask Images

    These considerations lead us to make it possible for a pixel list to appear
to an application as a special type of image called a \fImask image\fR, even
though the mask may be stored as a pixel list internally, and accessed or
queried directly as a list if desired.  If whenever we read a block of data
from the data image, we read an equivalent block of data from the mask image,
it is evident that whatever we come up with for reading from the mask image is
going to have to look an awful lot like IMIO.  Given the complexities of image
section transformations, automatic buffer allocation strategies, and so on,
the simplest solution is to just go ahead and use IMIO to access the virtual
mask image.  This leads us to the interface shown in the figure below.
These routines represent an extension to IMIO to support pixel lists.  The
conventional IMIO routines, used to access the mask "pixels", are not shown.

The mask image may be opened by name with \fIim_pmmap\fR, or an already opened
pixel mask, perhaps the result of some computation done by the applications
program, may be opened with \fIim_pmmapo\fR.  Alternatively, if the mask is
stored (or will be stored in the case of a new mask) in a pixel list file
(".pl" extension), the mask may be opened with a conventional \fIimmap\fR call.
This last option is especially powerful, since it allows all image tasks to
access masks as if they were conventional images, e.g., one can DISPLAY or
IMCOPY a stored mask.

.ks
.nf
		  im = im_pmmap (maskname, mode, ref_im|NULL)
		 im = im_pmmapo (pm, ref_im)

		         imseti (im, IM_RLIO, YES|NO)
		         imseti (im, IM_PMDES, pm)
		   pm = imstati (im, IM_PMDES)

	   bool = im_pmlne[123] (im[, lineno[, bandno]])
	   bool = im_pmsne[123] (im, x1, x2[, y1, y2[, z1, z2]])
	       bool = im_pmlnev (im, v)
	       bool = im_pmsnev (im, vs, ve, ndim)
.fi
.ke

The \fImode\fR argument to \fIim_pmmap\fR  specifies both the access mode for
the mask, and any standard transformations to be performed upon the mask before
i/o takes place (if an existing mask is to be read).  NEW_FILE mode is used to
create a new mask; READ_ONLY to read an existing mask, and READ_WRITE to modify
an existing mask.  The mode-transformation flags currently supported are
INVERT_MASK, which performs a PIX_NOT operation on the input mask, and
BOOLEAN_MASK, which converts an integer input mask to boolean.  Any more
complex mask transformations or combinations must be performed explicitly
by the calling program via calls to the PMIO or PLIO routines, mapping the
resultant mask onto an image descriptor with \fIim_pmmapo\fR.

If a reference image \fIref_im\fR is specified at open time,
then the mask image will inherit any image section, boundary extension, etc.
in effect for the reference image.  Inheritance occurs when the first i/o
to the mask image takes place.  The reserved names "BPM" and "EMPTY",
respectively (must be upper case), denote the bad pixel mask
for the reference image, or an empty mask the size of the reference image.
If the reference image does not have a bad pixel mask, BPM and EMPTY are
equivalent.  Note that separate image descriptors are used for the data
(reference) image and any mask images.  Multiple mask images may be associated
with the same reference image.

Normal IMIO calls, e.g., \fIimgs2i\fR, are used to access the mask "pixels".
Since it is common for a mask to be empty over large regions of an image,
a set of boolean functions are provided for testing whether regions of the
mask are nonempty, allowing a program to avoid the expense of image mask i/o
and subseqent testing of the mask pixel values if not needed.
The boolean functions \fIim_pmlne\fR (line not empty) and \fIim_pmsne\fR
(section not empty) and their more general variants \fIim_pmlnev\fR and
\fIim_pmsnev\fR test whether the specified region of the mask image contains
any nonzero mask pixels.  The calling sequences of these routines are patterned
after the corresponding IMIO pixel i/o routines, e.g., \fIim_pmlne2\fR is
intended for use with the \fIimgl2\fR routines, and \fIim_pmlnev\fR is
intended for use with the \fIimgnl\fR routines.

By default, mask image i/o operates on data buffers containing arrays of
pixels, as for a conventional data image.  When i/o takes place, the interface
automatically converts between pixel format and the compressed line list format
in which the mask is stored internally.  An alternative format for the mask
data is \fBrange list\fR format, enabled by setting the \fIIM_RLIO\fR parameter
to YES in an \fIimseti\fR call.  Range list i/o works identically to pixel i/o,
except that the "pixel arrays" returned by IMIO (or input to IMIO) are range
list structures, as defined in \fB<plset.h>\fR and discussed in section 3.3.4.

Range list i/o at the IMIO level is fully general, i.e., the section
transformation, if any, is applied transparently to the calling program,
and the full range of IMIO i/o routines may be used.
If the data buffer is a multidimensional subraster, each line of the subraster
will be a separate range list, and the physical length in pixels of each line
of the subraster will be as for a pixel subraster.
On a read, if the length of the encoded range list exceeds the subraster
line length in pixels, and i/o error will occur.  Such an i/o error cannot
occur when i/o is restricted to lines or line segments (1D buffers),
since IMIO will automatically allocate a data buffer large enough to hold
the worst case (longest) range list.  Range list overflow errors are
unlikely even for subrasters, however, since the range list format is
normally much more compact than the equivalent pixel array (except for
very small subrasters or very complex masks).

.NH 2
Masked Image I/O (MIO)

    The mask image i/o routines discussed in the previous section provide a
fully generalized means for directly accessing a mask as an separate entity,
independent of the associated reference data image.  Two separate image
descriptors are required, and two parallel but separate sets of calls to the
IMIO routines.  In many applications, however, a mask is used only to specify
those regions of the data image to be analyzed or processed.  We want to
access those regions of the image visible through the mask, but are not
otherwise interested in the mask itself.  The \fBmasked image i/o\fR (MIO)
interface is designed for such applications.

The MIO interface is summarized in the figure below.  A named mask may be
opened on a previously opened image with the \fImio_open\fR procedure.
As for \fIim_pmopen\fR, the reserved names "BPM" and "EMPTY", respectively,
denote the bad pixel mask for the image, or an empty mask the size of the
image.  If the image does not have a bad pixel mask, an empty mask will be
opened.

The \fIflags\fR argument, if nonzero, specifies an operation be performed
upon the input mask to generate the mask to be used to access the data image.
The currently supported flags are INVERT_MASK and BOOLEAN_MASK.  For example,
when the mask is a bad pixel mask, INVERT_MASK would cause MIO to access only
that portion of the image which is \fInot\fR covered by the bad pixel mask,
i.e., the "good" region of the image.  BOOLEAN_MASK is used to convert an
integer mask into a boolean mask.  Note that in the case of inversion of an
integer mask, the PIX_NOT operation merely complements the mask pixel values,
hence will not affect the \fIregion\fR covered by the mask.  To invert an
integer mask in the region sense, use INVERT_MASK+BOOLEAN_MASK.

.ks
.nf
		  mp = mio_open (maskname, flags, im)
		 mp = mio_openo (pm, im)
	      value = mio_stati (mp, param)
		       mio_seti (mp, param, value)
		   mio_setrange (mp, vs, ve, ndim)
   n|EOF = mio_[gp]lseg[silrdx] (mp, ptr, mval, v, npix)
		      mio_close (mp)
.fi
.ke

More general mask transformations must be carried out by the user using the
PMIO package to directly compute the desired mask, the mapping the mask onto
an image descriptor with \fImio_openo\fR.  For example, given as input a bad
pixel mask and a region mask, one could compute the mask specifying all pixels
in the region mask but not in the bad pixel mask.  Any general mask may be
computed in this way.

An MIO application will not normally need to access the mask directly, but
if such access is required the mask descriptor may be obtained with a call
to \fImio_stati\fR to fetch the value of the parameter \fIP_PMDES\fR.
Similarly, the image descriptor may be queried as parameter \fIP_IMDES\fR,
and either parameter may be set with the corresponding call to \fImio_seti\fR.

Successive calls to a get or put line segment procedure, e.g.,
\fImio_glsegr\fR (get line segment real), return line segments from the data
image until all the data present in the area outlined by the mask has been
accessed, at which time EOF is returned as the function value.
Each line segment is returned along with a vector \fIv\fR specifying the
line of the image from which the segment is taken and the index of the first
pixel of the current line segment within the line, a count \fInpix\fR of the
number of pixels in the line segment, and the mask value \fImval\fR for the
current line segment (e.g., 1 for a boolean mask).  Each line segment
corresponds to a region of constant nonzero value (\fImval\fR) in the mask.
Line segments are returned sequentially in storage order.

By default, the entire region of the image visible through the mask will be
accessed.  To access only a portion of the image, the \fIimio_setrange\fR
procedure may be called before performing any i/o to specify the starting and
ending vector coordinates \fIvs\fR and \fIve\fR of the region to be accessed.
Multiple calls may be made on the same MIO descriptor to access multiple
regions of the data image, or to "rewind" a given region of the image.

.NH 2
Mask Image Storage

    As we shall see in the discussion of the pixel list package, the pixel
list package is designed to permit a list to be stored anywhere, e.g.,
in a binary file, in a database, as an array in an image header,
or merely as a temporary array in memory.  When the new image structures
become available storing the masks in the image header or in a global database
will probably be the best approach, but in the meantime the simplest solution
is to store each pixel list or mask in a small binary file.  This approach has
the advantage of being independent of the particular image format used (none
of which are currently capable of storing the pixel list directly in any case).

If desired, the name of the mask file may be stored in the image header
as a simple string valued parameter.  Alternatively, the mask name may be
input as a parameter when a task is run.  A single mask may be associated
with several images, or several masks may be used with the same image.
The approach to be followed for a particular program is up to the programmer
or package designer.

The bad pixel mask is a special case, since it has a well defined logical
meaning for an image, unlike the region masks which are application specific.
The most straightforward approach is to use a single boolean mask for the
bad pixel list, using the optional header keyword \fIBPM\fR to store the
mask name, which should normally be the image name plus the pixel list file
extension "\fI.pl\fR".  An integer BPM could also be used, but most applications
would treat it as a boolean mask, treating any pixel with a nonzero value as
a bad pixel.

Any additional information required to describe the bad pixels is application
specific, and may be stored in any of several ways, e.g., as a set of boolean
masks, in an integer mask, using flag bits or reserved values to describe each
pixel or region, in a separate fully populated weight image, or using the noise
function package.  Most IRAF applications will probably use the BPM plus a
noise function, with the noise function being stored either as
a one-dimensional noise model or as a separate uncertainty image, transparently
to the application.  The combination of a one-dimensional noise model plus a
compressed bad pixel list should provide an efficient and flexible solution
to the pixel variance problem for most applications.

.NH 2
Example

    Open a data image and the associated mask image, and sum the pixels within
the area indicated by the mask.

.nf
    include <pmset.h>

    task    sum = t_sum
.fi

.tp 6
.nf
    # SUM -- Sum the image pixels lying within the given mask.

    procedure t_sum()

    char    image[SZ_FNAME]              # input data image
    char    mask[SZ_FNAME]               # image mask

    int     npix, mval, totpix, m_flags
    long    v[PM_MAXDIM]
    pointer im, mp, pp
    real    sum

    bool    clgetb()
    real    asumr()
    int     mio_glsegr()
    pointer immap(), mio_open()

    begin
	    call clgstr ("image", image, SZ_FNAME)
	    call clgstr ("mask", mask, SZ_FNAME)
	    m_flags = 0
	    if (clgetb ("invert"))
		m_flags = INVERT_MASK

	    im = immap (image, READ_ONLY, 0)
	    mp = mio_open (mask, m_flags, im)

	    sum = 0;  totpix = 0
	    while (mio_glsegr (mp, pp, mval, v, npix) != EOF) {
		sum = sum + asumr (Memr[pp], npix)
		totpix = totpix + npix
	    }

	    call mio_close (mp)
	    call imunmap (im)

	    call printf ("%d pixels, sum=%g, mean=%g\n")
		call pargi (totpix)
		call pargr (sum)
		if (totpix > 0)
		    call pargr (sum / totpix)
		else
		    call pargr (INDEF)
    end
.fi

A more complex application might use the spatial information provided by
\fIv\fR and \fInpix\fR, or the flag values provided by \fImval\fR (for an
integer mask).  For example, a surface fitting routine would accumulate each
line segment into a least squares matrix, using the coordinate information
provided as well as the pixel values.

.NH 2
The Pixel Mask Package (PMIO)

    We have thus far discussed two quite different interfaces, i.e., the use
of IMIO to do pixel i/o to a mask mapped as a virtual mask image, and the MIO
interface, used to access the portion of a data image visible through a mask.
The next step is to define the interface used to access the mask object
directly as a \fImask\fR, independently of the use of masks for image i/o.

.nf
	    pm = pm_newmask (ref_im, depth)

	       pm = pm_open (bufptr|NULL)
	     pm = pm_create (naxes, axlen, depth)
	    pm = pm_newcopy (pm)
		   pm_close (pm)

		pm_[sg]size (pm, naxes, alxen, depth)
		    pm_seti (pm, param, value)
	   value = pm_stati (pm, param)
		   pm_debug (pm, outfd, maxcol, flags)
	    bool = pm_empty (pm)
		pm_compress (pm)
		   pm_clear (pm)

		    pm_load (pm, bufptr)
	   nwords = pm_save (pm, bufptr, buflen)
		   pm_loadf (pm, fname, title, maxch)
		   pm_savef (pm, fname, title, save_flags)
	   pm_[load|save]im (pm, imname[, save_flags])

	    ptr = pm_access (pm, v)
     bool = pm_linenotempty (pm, v)
     bool = pm_sectnotempty (pm, vs, ve, ndim)
	  pm[gp]l[lrp][sil] (pm, v, buf, b_depth, npix, rop)

	  pm_[set|get]plane (pm, v)
		   pm_point (pm, x, y, rop)
		  pm_circle (pm, x, y, r, rop)
		     pm_box (pm, x1,y1, x2,y2, rop)
		    pm_line (pm, x1,y1, x2,y2, width, rop)
		 pm_polygon (pm, x, y, npts, rop)

		     pm_rop (pm_src, vs, pm_dst, vs, vn, rop)
		 pm_stencil (pm_src, vs, pm_dst, vs, pm_stl, vs, vn, rop)
.fi

There are two variants on this lowest level interface, known as PMIO (pixel
mask i/o) and PLIO (pixel list i/o).  These two interfaces are equivalent
with one difference: PMIO can accept a reference image and inherit the section
transformation of the reference image, allowing the mask to be accessed in
the coordinate system of the reference image, while PLIO is a stand alone
interface, implemented independently of IMIO without any ties to IMIO.
PMIO is implemented as a thin layer upon PLIO, with ties to IMIO to access
the section transformation for the reference image.

The PMIO interface is shown in the figure above.
With the exception of the additional routine \fIpm_newmask\fR, used to create
a new, empty mask the same size as a reference image, the PMIO routines are
identical to the corresponding PLIO routines except for the \fIpm\fR package
prefix, and the implied section transformation.  Indeed, if no reference image
is specified or if the section transformation is unitary (the reference image
was opened without an image section), the two interfaces are identical.
Hence the discussion of PLIO in the next section will serve to document PMIO
as well.

To use PMIO, merely include \fB<pmset.h>\fR rather than \fI<plset.h>\fR,
and set the reference image with a call to \fIpm_seti\fR, e.g.,

	call pm_seti (pm, P_REFIM, ref_im)

This step can be skipped if \fIpm_newmask\fR or \fIpm_newcopy\fR is used to
create a new mask, as the reference image will be inherited by the new mask.

Programs which use PMIO to access a mask may also use the low level line,
range, and pixel list routines discussed in section 3.1 (\fBpl_rangerop\fR etc.)
on lists returned by PMIO, since PMIO will have already transformed the data
into the coordinate system of the reference image.

In general, the PMIO interface should be used in preference to PLIO whenever
the mask to be accessed is logically associated with some data image or images.
The region description and logical region processing capabilities of PLIO are
very powerful in their own right, however, and PLIO should be used directly by
applications which do not consider the mask to be merely an overlay for a data
image.  An example would be any application which operates upon a 2-dimensional
data structure other than an image (e.g., region filtering in the POE image
kernel).

.NH
The Pixel List Package (PLIO)

    A pixel list is a way of representing an N-dimensional image matrix which
is well suited for applications where the represented image is sparse, or
consists of a moderate number of arbitrarily shaped regions.  Routines are
provided for creating new lists, for writing to or reading from lists,
for storing or retrieving lists, and for performing various types of
operations upon entire lists to make new lists.  The full set of routines
in the package are summarized in the figure below.

A pixel list, like an image, has a fixed dimensionality and size which is
determined at list creation time for the lifetime of the list.  New lists
are created with \fIpl_create\fR, which returns a pointer to an empty list.
The \fIdepth\fR parameter specifies the depth of the list in bits, i.e.,
the number of bits per pixel, in the range 1-27.  A boolean list has a depth
of 1 bit.  In the current implementation the boolean mask is handled as a
degenerate case of an integer mask, i.e., an integer mask which happens to
have mask values in the range 0-1.

An existing list is accessed by opening a descriptor with \fIpl_open\fR and
loading the list into the runtime descriptor structure, either by specifying
a non-NULL buffer pointer \fIbufptr\fR, or by calling one of the \fIpl_load\fR
functions after opening a null descriptor.

.ks
.nf
	       pl = pl_open (bufptr|NULL)
	     pl = pl_create (naxes, axlen, depth)
	    pl = pl_newcopy (pl)
		   pl_close (pl)

		pl_[sg]size (pl, naxes, axlen, depth)
		    pl_seti (pl, param, value)
	   value = pl_stati (pl, param)
		   pl_debug (pl, outfd, maxcol, flags)
	    bool = pl_empty (pl)
		pl_compress (pl)
		   pl_clear (pl)

		    pl_load (pl, bufptr)
	   nwords = pl_save (pl, bufptr, buflen)
		   pl_loadf (pl, fname, title, maxch)
		   pl_savef (pl, fname, title, save_flags)
	   pl_[load|save]im (pl, imname[, save_flags])

	    ptr = pl_access (pl, v)
     bool = pl_linenotempty (pl, v)
     bool = pl_sectnotempty (pl, vs, ve, ndim)
	  pl[gp]l[lrp][sil] (pl, v, buf, b_depth, npix, rop)

	  pl_[set|get]plane (pl, v)
		   pl_point (pl, x, y, rop)
		  pl_circle (pl, x, y, r, rop)
		     pl_box (pl, x1,y1, x2,y2, rop)
		    pl_line (pl, x1,y1, x2,y2, width, rop)
		 pl_polygon (pl, x, y, npts, rop)

		     pl_rop (pl_src, vs, pl_dst, vs, vn, rop)
		 pl_stencil (pl_src, vs, pl_dst, vs, pl_stl, vs, vn, rop)
.fi
.ke

Pixel lists are stored externally as opaque binary byte arrays.
The function \fIpl_save\fR will encode a pixel list as a byte array and store
it in the indicated buffer, resizing the buffer if necessary.
If \fIbufptr\fR is NULL a new buffer will be allocated, overwriting the NULL.
The \fIpl_load\fR function performs the inverse function.
The \fIf\fR suffixed functions are provided for convenience when storing
lists in small binary files.  The \fIim\fR suffixed functions create masks
out of actual data images, and vice versa.  In the most general case, a list
is encoded into an array in memory and then stored away by the applications
wherever they wish, e.g., as an array parameter in an image header when the
new image structures become available.

Pixel list i/o is provided via the \fIpl[gp]l[lrp][sil]\fR family of functions,
which read, write, or edit (via the \fIrop\fR) lines or line segments of masks.
The naming convention is as follows:

.ks
.nf
	 pl		package prefix
	[gp]		get or put
	 l		line segment
	[lrp]		as a line list, range list, or pixel array
	[sil]		in an array of type short, int, or long
.fi
.ke

For example, \fIplglps\fR would get a line from a mask image as a fully
populated array of type short.  For maximum efficiency, since this is a low
level interface, the data is read from or copied into a user allocated buffer,
rather than having the pixel list package control the buffer.

The functions \fIplgll[sil]\fR return the packed line list for the indicated
line or line segment.  This is the copy-out form of access with the least
overhead, but requires that the application have knowledge of the internal
line list format.

Alternatively, if it is only desired to read from a list, accessing the list
in the internal format, the internal list for an image line may be directly
accessed by pointer with the \fIpl_access\fR function.  This is the most
efficient form of access.  The variant \fIpl_linenotempty\fR is similar except
that the NULL pointer is returned if the indicated line of the list is empty,
providing an efficient and convenient way to perform the empty test on mask
image lines.

The functions \fIplglr[sil]\fR are similar to the get line list form of access,
but instead of returning the encoded list-list in the internal format,
it returns a simple array of ranges of absolute pixel indices and associated
mask values.  This is the recommended way of accessing the mask as a list
structured object, since it does not require knowledge of the internal packed
line list format.  For example, to print line \fIv\fR of the mask on descriptor
\fIpl\fR as a series of range lists:

.ks
.nf
	int	buf[3,1024], n, i, plglri()

	n = plglri (pl, v, buf, 0, axlen[1], 0)
	do i = 1, n {
	    call printf ("range at %d, %d pixels, mask value = %o\n")
		call pargi (buf[1,i]);  call pargi (buf[2,i])
		call pargi (buf[3,i])
	}
.fi
.ke

These routines require that the depth in bits of the output line or range
list or pixel array be specified.  This is necessary to avoid generating
numbers the size of the machine integer when inverting a mask (PIX_NOT),
e.g., if the mask depth is 8 bits, the complement of a 0 pixel should be 377,
not 37777777777.  The depth argument may also be used to convert an integer
mask to a boolean mask, or vice versa (using the PIX_VALUE field of the
rasterop discussed in the next section).  If \fIb_value\fR is zero, clipping
of the output values is disabled.  This would be appropriate, for example,
when simply reading from a mask without modifying the pixel values.

New pixel lists may be created by having the application prepare the packed
line lists externally, inserting them directly into the pixel list structure
with a \fIput\fR routine.  This is generally inadvisable, however, because
the packed line list format is considered internal to the PLIO package.
A better alternative is to input the mask data as a populated array or
as a range list, letting the PL package manage the internal line list.

A more convenient approach to creating or modifying masks for most applications
is to define the mask by specifying a series of include and exclude standard
region types (circles, boxes, lines, points, or polygons),
using the block of routines beginning with \fIpl_setplane\fR in the figure.
Note that these are two dimensional
operators; they are provided for convenience even though the pixel list
package can support images of any dimension (if the image has three or more
dimensions \fIpl_setplane\fR may be used to specify the plane to be operated
upon).  The most general routine is \fIpl_polygon\fR, which may be used to
operate upon the pixels in the interior of any general polygon.  All of the
region drawing operators will permit regions to extend beyond the boundary
of the mask, clipping as necessary at the boundary.

.NH 2
Pixel, Line, and Range List Routines

    Most of the N dimensional region or mask oriented PMIO and PLIO routines
eventually result in calls to the low level pixel, line, and range rasterop
routines and format conversion routines shown in the figure below.  These
routines form the functional core of the PLIO package and will often be
responsible for most of the execution time of routines which use PLIO.

There are two main classes of routines.  The \fIpl_pixrop\fR, \fIpl_linerop\fR,
and \fIpl_rangerop\fR routines perform the general raster operation on pixel
arrays, line lists, and range lists.  The \fIpl_linestencil\fR routine performs
the stencil rasterop operation upon line lists; currently only a list list
version is available since this is a rarely used routine.  Lastly, a set of
six routines are provided for converting between any two of the three formats,
e.g., line list to range list or pixel array and vice versa, omitting the
like-to-like conversions.  For example, \fIpl_p2ri\fR would convert a pixel
array to a range list, both of type integer.

.ks
.nf
		 pl_linerop (ll_src, xs, src_maxval,
			     ll_dst, ds, dst_maxval, ll_out, npix, rop)
	     pl_linestencil (ll_src, xs, src_maxval, ll_dst, ds, dst_maxval,
			     ll_stn, xs, ll_out, npix, rop)

	     pl_pixrop[sil] (px_src, xs, src_maxval,
			     px_dst, ds, dst_maxval, npix, rop)
	   pl_rangerop[sil] (rl_src, xs, src_maxval,
			     rl_dst, ds, dst_maxval, rl_out, npix, rop)

    n = pl_[lrp]2[lrp][sil] (op_src, xs, op_dst, npix)
.fi
.ke

Note that these low level routines
specify the mask depth as a maximum pixel value, rather than taking the depth
in bits as the high level PMIO and PLIO routines do, and that there are no
\fI"pm_"\fR versions of these routines - the one set of routines may be used
with both PLIO and PMIO.

.NH 2
Rasterops

    The argument \fIrop\fR in the circle, box, and other routines discussed
in the previous sections is called a \fBrasterop\fR, and specifies the bitwise
operation to be performed to generate the destination operand.  Much of the
generality and conciseness of the pixel list package is due to the rasterop
abstraction, which is patterned after a similar construct used by the Sun
Microsystems \fISunview\fR interface to specify operations upon \fIpixrects\fR,
which are logically similar to PLIO masks.

The rasterop defines the operation to be performed to generate the destination
mask, in terms of bitwise boolean operations performed upon the input source
and destination masks.  Rasterops are constructed via a series of bitwise
\fIand\fR and \fIor\fR operations, using the following macro defines:

.ks
.nf
	PIX_SRC			  specifies the source mask
	PIX_DST			  specifies the destination mask
	PIX_NOT(op)		  inverts the operand mask
	PIX_VALUE(value)	  specifies the bitplanes to be set
.fi
.ke

Examples of some of the possible operations (out of a total of 16 possible
operations) are shown below.  This table is reproduced from the SunView
Pixrect Reference Manual.

.ks
.nf
	     \fIRasterop\fR			     \fIDescription\fR

	PIX_SRC			  copy source to destination
	PIX_DST			  no-op
	PIX_SRC | PIX_DST	  paint (OR source to destination)
	PIX_SRC & PIX_DST	  mask (AND of source and destination)
	PIX_NOT(PIX_SRC)&PIX_DST  erase (AND destination with negation
				    of source)
	PIX_NOT(PIX_DST)	  invert area (negate the existing
				    values)
	PIX_SRC ^ PIX_DST	  inverting paint (XOR of source and
				    destination)
.fi
.ke

Here, the |&^ denote the SPP \fIor\fR, \fIand\fR, and \fIxor\fR intrinsic
functions, which must be used to construct actual rasterop expressions in SPP,
e.g.:

	PIX_NOT(PIX_SRC) | PIX_DST | PIX_VALUE(v)

would actually be written as

	or (PIX_NOT(PIX_SRC), PIX_DST) + PIX_VALUE(v)

The following additional macros are defined to deal with the more common
cases of setting or clearing a region.

.ks
.nf
	PIX_SET			  (PIX_SRC | PIX_NOT(PIX_SRC))
	PIX_CLR			  (PIX_SRC & PIX_NOT(PIX_SRC))
.fi
.ke

As a simple example, consider the case of specifying a region mask as a series
of include and exclude circles and boxes.  This is trivial for a boolean mask:
an include circle or box is specified by the rasterop PIX_SET, and an exclude
by PIX_CLR.  In the equivalent operation upon an integer mask this would cause
any mask values which had already been set to be replaced, hence it might be
desirable to use a PIX_SRC|PIX_DST rasterop instead, to OR the bits of the new
flag values into those of any flag values already set.  Similarly, when using
\fIpl_ltop\fR to unpack a line list into a pixel array, the PIX_SRC|PIX_DST
rasterop might be specified to OR the mask segment into an existing pixel
array.

General bitwise boolean operations upon masks are provided by the \fIpl_rop\fR
and \fIpl_stencil\fR operators, which operate upon entire masks or rectangular
subregions of masks.  The \fIpl_rop\fR operator combines the source and
destination masks to produce a new mask; \fIpl_stencil\fR performs the same
operation, but only in the regions specified by the stencil mask,
which must be a boolean mask.  The input mask may be NULL (depending upon
the rasterop specified), or the source and destination masks may be the same.

The equivalent operators for line lists, range lists, and pixel arrays are
the \fIpl_S2D\fR family of routines, where \fIS=D=[lrp]\fR for a line list,
range list, or pixel array rop.  The routine \fIpl_linestencil\fR implements
the stencil operation for a line list.

As noted above, when operating upon integer masks (\fIdepth\fR > 1), the
PIX_VALUE macro is used to specify the flag value for the indicated region.
For example, the following rasterop would set all the pixels in a region to
the same value:

	PIX_VALUE(value)

to OR in the new value instead of replacing any existing flag values:

	PIX_VALUE(value) | PIX_DST

If a boolean mask is to be written to an integer mask, PIX_VALUE specifies
the flag value to be used for the regions set to 1 in the input boolean mask.
For example, one might wish to combine a set of 8 boolean masks to form a
single 8 bit deep integer mask, with each bit in the integer mask corresponding
to one of the input boolean masks (001 = mask 1, 002 = mask 2, 040 = mask 3,
etc.).  This could be done using the rasterop shown above, incrementing
PIX_VALUE in each operation to specify the bitplane to be set.

.NH 3
Rasterop Expression Evaluation

    As mentioned above, there are sixteen possible ways to combine the source
and destination masks subject to the four possible boolean operations
(\fIand\fR, \fIor\fR, \fIxor\fR, and \fInot\fR).
More precisely, although numerous bitwise expressions can be constructed, many
of these are equivalent, and there are only sixteen fundamental operations.
These are summarized in the following table.

.nf
		Operation			      Opcode

	PIX_CLR 		      			00
	PIX_SET						17

	PIX_SRC						14
	PIX_DST						12

	PIX_NOT(PIX_SRC)				03
	PIX_NOT(PIX_DST)				05

	PIX_SRC & PIX_DST				10
	PIX_SRC | PIX_DST				16
	PIX_SRC ^ PIX_DST				06

	PIX_SRC & PIX_NOT(PIX_DST)			04
	PIX_SRC | PIX_NOT(PIX_DST)			15
	PIX_NOT(PIX_SRC) & PIX_DST			02
	PIX_NOT(PIX_SRC) | PIX_DST			13

	PIX_NOT (PIX_SRC & PIX_DST)			07
	PIX_NOT (PIX_SRC | PIX_DST)			01
	PIX_NOT (PIX_SRC ^ PIX_DST)			11
.fi

As an example of the redundancy of arbitrary rasterop expressions,
compare the following with the equivalent expressions (same opcode)
in the table above.

.ks
.nf
	PIX_NOT(PIX_SRC) & PIX_NOT(PIX_DST)		01
	PIX_NOT(PIX_SRC) ^ PIX_NOT(PIX_DST)		06
	PIX_NOT(PIX_SRC) | PIX_NOT(PIX_DST)		07
	PIX_NOT(PIX_SRC) ^ PIX_DST			11
	PIX_SRC ^ PIX_NOT(PIX_DST)			11
.fi
.ke

Any number of additional logically redundant expressions may be constructed.
The programmer should not worry about simplifying logical expressions,
but should choose instead whatever expression is clearest for their particular
application, letting the interface handle expression optimization internally.

Of the sixteen possible fundamental operations, there are four trivial
operations (\fIclr\fR, \fIset\fR, \fIsrc\fR, \fIdst\fR),
seven composite operations, and four primary operations, namely,
\fIand\fR, \fIor\fR, \fIxor\fR, and \fInot\fR (two cases of the latter).
The composite operations are all implementable as two primary
operations in sequence.  PIX_NOT is implemented by actual inversion of the
list rather than as a mode flag, to avoid complications when the list is read.

.NH 3
Rasterop Encoding

    The rasterop argument specifies the bitwise boolean operation to be
performed, and optionally the pixel value to be used (in the case of an
integer mask).  Both are specified as a single integer value, packed as
shown in the figure below.

.ks
.nf
	+--+-------------+--------+
	|32|31          5|4      1|
	+--+-------------+--------+
	|  | pixel value | opcode |
	+--+----------------------+
.fi
.ke

The following is an example of a typical rasterop (note that since the pixel
value field has a reserved range of bits which is zero prior to expression
evaluation, the "+" operator is equivalent to the \fIor\fR intrinsic function).

	or(PIX_SRC, PIX_NOT(PIX_DST)) + PIX_VALUE(pix_value)

Note that the width of the pixel value field in the rasterop constrains the
effective mask depth to be 27 bits or less, if full generality is desired in
rasterop operations.  Masks of up to 31 bits (the minimum unsigned precision
of a \fIlong\fR) can be stored and accessed, but rasterops using PIX_VALUE
are limited to 27 bits.

.NH 2
Pixel List Data Structures

    A pixel list consists of an array of pointers to the \fIline lists\fR
forming the mask.  There is one pointer for each image line; if the pointer
is NULL, no mask values are set on the associated image line.  N-dimensional
images are easily handled by an N-1 dimensional array of line pointers.

Each line list consists of a series of offsets and mask pixel values
(the pixel values are normally omitted for a boolean mask).
The offsets specify the number of pixels for which the mask has the same value.
This line list format has the following two significant advantages over the
alternative technique of specifying a list of ranges using absolute pixel
coordinates:
.ls
.ls [1]
A higher degree of data compression is possible.  If absolute pixel
coordinates are used in the list, the list must be an array of 32 bit
integer values in order to avoid a builtin limit on the size of the image
which can be represented.  By using offsets, list elements as small as
one byte are possible.
.le
.ls [2]
A list composed of offsets is invariant with respect to translation.
For example, when extracting a subraster of an image, one can extract the
corresponding segment of each line list and perhaps edit the first element,
and the remainder of the list may be used without change.
.le
.le

When describing regular regions such as boxes it will often be the case that
successive lines of the mask are equivalent, in which case multiple line list
pointers may point to the same line list.  Hence, the line lists will provide
good compression of regular objects in any two dimensional plane of the mask.
This technique can be extended to higher dimensions if desirable, without
affecting the line list data structures visible to an application.

.NH 3
Line List Encoding

    A good compromise between storage efficiency and efficiency of runtime
access, while keeping things simple, is achieved if we maintain the compressed
line lists as variable length arrays of type short integer (16 bits per list
element), regardless of the mask depth.  A line list consists of a series of
simple \fIinstructions\fR which are executed in sequence to reconstruct a line
of the mask.  Each 16 bit instruction consists of the sign bit (not used at
present), a three bit \fIopcode\fR, and twelve bits of data, i.e.:

.ks
.nf
	+--+-----------+-----------------------------+
	|16|15       13|12                          1|
	+--+-----------+-----------------------------+
	|  |   opcode  |            data             |
	+--+-----------------------------------------+
.fi
.ke

The significance of the data depends upon the instruction.  The instructions
currently implemented are summarized in the table below.

.ks
.nf
     Instruction     Opcode           Description

        ZN            00 	Output N zeros
        HN            04 	Output N high values
        PN            05 	Output N-1 zeros plus one high value
	SH	      01	Set high value, absolute
        IH,DH         02,03	Increment or decrement high value
        IS,DS         06,07	Like IH-DH, plus output one high value
.fi
.ke

In order to reconstruct a mask line, the application executing these
instructions is required to keep track of two values,
the \fIcurrent high value\fR and the \fIcurrent position\fR in the output line.
The detailed operation of each instruction is as follows:
.ls 4
.ls 8 ZN
Zero the next N (=\fIdata\fR) output pixels.
.le
.ls HN
Set the next N output pixels to the current high value.
.le
.ls PN
Zero the next N-1 output pixels, and set pixel N to the current high value.
.le
.ls SH
Set the high value (absolute rather than incremental), taking the high 15 bits
from the next word in the instruction stream, and the low 12 bits from the
current data value.
.le
.ls IH,DH
Increment (IH) or decrement (DH) the current high value by the \fIdata\fR
value.  The current position is not affected.
.le
.ls IS,DS
Increment (IS) or decrement (DS) the current high value by the \fIdata\fR
value, and \fIstep\fR, i.e., output one high value.
.le
.le

The high value is assumed to be set to 1 at the beginning of a line, hence
the IH,DH and IS,DS instructions are not normally needed for boolean masks.
If the length of a line segment of constant value or the difference between
two successive high values exceeds 4096 (12 bits), then multiple instructions
are required to describe the segment or intensity change.

The performance of this encoding is very good for typical masks consisting
of isolated high or low values or extended regions at the same level.
The worst case performance occurs when successive pixels have different values.
Even in this case the encoding will only require one word (16 bits) per mask
pixel, provided either the delta intensity change between pixels is usually
less than 12 bits, or the mask represents a zero floored step function of
constant height.  The worst case cannot exceed npix*2 words provided the mask
depth is 24 bits or less.

.NH 3
Example: Line List Encoding

    As a simple example, consider the following line of a boolean mask.
The set pixels are 1, 4, 8 through 11, and so on, shown as \fIindex list\fR
in the figure.  The corresponding \fIoffset list\fR (line list encoding)
is also shown.  Note that both encodings require the same amount of space,
assuming 16 bits per list element in both cases; the index list would require
twice as much space if 32 bit list elements were used.

.ks
.nf
	Index list:	1, 4, 8-11, 15, 23-39		7 words
	Offset list:	P1 P3 Z3 H4 P4 Z7 H17		7 words

	Inverted I-L:	2-3, 5-7, 12-14, 16-22		8 words
	Inverted O-L:	Z1 H2 Z1 H3 Z4 H3 Z1 H7		8 words
.fi
.ke

The bottom half of the figure shows the encodings for the inverted lists,
i.e., the lists which would be produced by a PIX_NOT rasterop operation.
Since both encodings reflect only the points in a line where level changes
occur, the information content and list size of the normal and inverted
lists are comparable.  The encoding for an integer mask would be equivalent
except for the addition of occasional SH or SL instructions to set the high
value.

.NH 3
Line List Structure

    The full line list structure consists of a header describing the line
list entry in the PLIO descriptor, plus the LL encoding of the line, as
illustrated below.  This information is internal to the PLIO package and
should not be used in applications code.  [The LL header was generalized
in Aug2000 to permit larger masks; see plio.h]

.ks
.nf
	define	LL_START	4
	struct linelist {
		short	nref		# number of lines pointing here
		short	blen		# length of buffer containing list
		short	len		# encoded linelist length, words
		short	ll[]		# encoded pixel data
	}
.fi
.ke

The linelist encoding includes any trailing zeros, i.e., executing of the
encoded instructions will regenerate the entire mask line.

.NH 3
Range List Structure

    The range list structure provides applications programs with a list
representation of a mask, for cases where it would be inefficient or
inconvenient to access the mask as a pixel array.  Range lists are not
used to store masks in external storage, hence data compression is not an
issue, nor is machine independence.

.ks
.nf
	rtype = short|int|long
	struct rangelist {
		rtype	x		# x coordinate of first pixel
		rtype	n		# number of pixels in range
		rtype	v		# pixel value
	}

	int	rl[3,ARB]		# typical range list array decl
.fi
.ke

The range list structure is defined in <plset.h>, e.g. (refer to the actual
file for more reliable documentation for these definitions):

.ks
.nf
	RL_FIRST	# first data range entry in list
	RL_LENELEM	# size of each element of list (i.e., 3)
	RL_MAXLEN	# maximum range list length (arg=pl)

	RL_LEN		# physical length of range list	(RL_LEN(rl))
	RL_AXLEN	# length of mask image line (RL_AXLEN(rl))
	RLI_LEN		# RL_LEN for rl = ptr to int
	RLI_AXLEN	# RL_AXLEN  "     "     "
	RLS_LEN		# RL_LEN for rl = ptr to int
	RLS_AXLEN	# RL_AXLEN  "     "     "

	RL_X		# use as RL_X(rl,i), rl = range list array
	RL_N		# Npix field of range list array element
	RL_V		# Value field of range list array element

	RL_XOFF		# offset of xstart field 
	RL_NOFF		# offset of npix field
	RL_VOFF		# offset of value field
.fi
.ke

The range list is represented as a simple two dimensional integer or
short integer array.  The first line of the two dimensional array is
used as the \fBrange list header\fR, and is used to store the \fIlen\fR
and \fIaxlen\fR parameters describing the encoded mask line.  Each
subsequent entry defines a range \fInpix\fR of mask image pixels,
starting at pixel \fIx\fR (absolute pixel coordinates), all of which
have the value \fIvalue\fR.  Only nonzero ranges are stored.
Note that the \fIlen\fR field defines the entire length of the structure,
including the header range and data ranges.

.NH 3
Example: A Small Mask

    A complete example of a small mask (75 columns by 40 lines) is shown below.
This mask and the sample output were prepared by the PLIO debug interpreter,
file \fIzzdebug.x\fR in the PLIO source directory.

.nf
40 .1111111..............................................................22222
39 .1111111..............................................................22222
38 .1111111...............................................................2222
37 .1111111...............................................................2222
36 .1111111............................................................4......
35 .1111111.....................11111111111111111111111111...........4444.....
34 .1111111.....................11111111111111111111111111........44444444....
33 .1111111......................1111111111111111111111111......44444444......
32 .1111111......................1111111111111111111111111...44444444.........
31 .1111111......................1111111111111111111111111.44444444...........
30 .1111111...........4..........1111111111111111111111115444444..............
29 .1111111...........4..........11111111111111111111155554444................
28 .1111111...........4..........111111111111111111155555544..................
27 .1111111...........4..........1111111111111111555555551....................
26 .1111111.....................11111111111111155555555111....................
25 .1111111.....................11111111111115555555111111....................
24 ............................1111111111155444444.1111111....................
23 ...........................111111111155544444....111111....................
22 ..............1...........1111111155555444........11111....................
21 ........................1111111155555554..........11111....................
20 ........................111111555555511...........11111....................
19 ........................111555555551111...........11111....................
18 ........................155555555111111...........11111....................
17 ......................445555551111111111.........111111....................
16 ....................444455551111111111111.......1111111....................
15 ..................4444445111111111111111111111111111111....................
14 ...............44444444.1111111111111111111111111111111....................
13 .............44444444......................................................
12 ..........44444444.........................................................
11 ........44444444...........................................................
10 .........4444........................22222.................................
 9 ..........4.........................2222222..............22222.............
 8 ....................................2222222.............2222222............
 7 ....................................2222222.............2222222............
 6 .....................................22222..............2222222............
 5 11111111111111111111.....................................22222.............
 4 11111111111111111111.......................................................
 3 11111111111111111111.......................................................
 2 11111111111111111111.......................................................
 1 11111111111111111111.......................................................
   123456789012345678901234567890123456789012345678901234567890123456789012345
            1         2         3         4         5         6         7     
.fi

This first figure shows the mask itself, output graphically as a character
matrix.  This is an integer mask wherein the integer value of each pixel is
the ASCII value of the character shown.  The mask was created by \fIor\fR-in
a number of regions together, using a different mask value for each region.
The result in areas where the regions intersect is a new mask pixel value.

The figure below shows the internal data structures used to represent the
previous mask.  Both the line list and range list representations of the
mask are shown.  The size of the packed line list is 582 words, 189 of which
are free (no longer used due to updates), hence the packed line list size
would be 393 words following a call to \fIpl_compress\fR to compress the mask.

.nf
    Mask 1EECD naxes=2 [75,40] maxval=177 plane=[75,40]
    max buffered line size 1024, max actual line size 16
    40 lines total, 40 are nonempty, mask is nonempty
    llbp=42AF5, len=1190, op=583, free=189, nupdates=35

    Index at 1EFF1 containing 40 lines:
	 4     4     4     4    17    26    35    35   166   177   187
       194   201   208   218   228   241   254   266   554   292   568
       319   333   347   360   492   507   523   539   423   435   447
       459   471   483   148   148   157   157

    Line list containing 40 lines:
    [1:4]      IH48(49) H20 Z55 (75,49)
    [5]        IH48(49) H20 IH1(50) Z37 H5 Z13 (75,50)
    [6]        IH49(50) Z37 H5 Z14 H7 Z12 (75,50)
    [7:8]      IH49(50) Z36 H7 Z13 H7 Z12 (75,50)
    [9]        IH51(52) P11 DH2(50) Z25 H7 Z14 H5 Z13 (75,50)
    [10]       IH51(52) Z9 H4 DH2(50) Z24 H5 Z33 (75,50)
    [11]       IH51(52) Z8 H8 Z59 (75,52)
    [12]       IH51(52) Z10 H8 Z57 (75,52)
    [13]       IH51(52) Z13 H8 Z54 (75,52)
    [14]       IH51(52) Z15 H8 DH3(49) Z1 H31 Z20 (75,49)
    [15]       IH51(52) Z18 H6 IS1(53) DH4(49) H30 Z20 (75,49)
    [16]       IH51(52) Z20 H4 IH1(53) H4 DH4(49) H13 Z7 H7 Z20 (75,49)
    [17]       IH51(52) Z22 H2 IH1(53) H6 DH4(49) H10 Z9 H6 Z20 (75,49)
    [18]       IH48(49) P25 IH4(53) H8 DH4(49) H6 Z11 H5 Z20 (75,49)
    [19]       IH48(49) Z24 H3 IH4(53) H8 DH4(49) H4 Z11 H5 Z20 (75,49)
    [20]       IH48(49) Z24 H6 IH4(53) H7 DH4(49) H2 Z11 H5 Z20 (75,49)
    [21]       IH48(49) Z24 H8 IH4(53) H7 DS1(52) DH3(49) Z10 H5 Z20
	       (75,49)
    [22]       IH48(49) P15 Z11 H8 IH4(53) H5 DH1(52) H3 DH3(49) Z8 H5
	       Z20 (75,49)
    [23]       IH48(49) Z27 H10 IH4(53) H3 DH1(52) H5 DH3(49) Z4 H6 Z20
	       (75,49)
    [24]       IH48(49) Z28 H11 IH4(53) H2 DH1(52) H6 DH3(49) Z1 H7 Z20
	       (75,49)
    [25]       IH48(49) Z1 H7 Z21 H13 IH4(53) H7 DH4(49) H6 Z20 (75,49)
    [26]       IH48(49) Z1 H7 Z21 H15 IH4(53) H8 DH4(49) H3 Z20 (75,49)
    [27]       IH48(49) Z1 H7 IH3(52) P12 DH3(49) Z10 H16 IH4(53) H8
	       DS4(49) Z20 (75,49)
    [28]       IH48(49) Z1 H7 IH3(52) P12 DH3(49) Z10 H19 IH4(53) H6
	       DH1(52) H2 Z18 (75,52)
    [29]       IH48(49) Z1 H7 IH3(52) P12 DH3(49) Z10 H21 IH4(53) H4
	       DH1(52) H4 Z16 (75,52)
    [30]       IH48(49) Z1 H7 IH3(52) P12 DH3(49) Z10 H24 IS4(53)
	       DH1(52) H6 Z14 (75,52)
    [31]       IH48(49) Z1 H7 Z22 H25 IH3(52) Z1 H8 Z11 (75,52)
    [32]       IH48(49) Z1 H7 Z22 H25 IH3(52) Z3 H8 Z9 (75,52)
    [33]       IH48(49) Z1 H7 Z22 H25 IH3(52) Z6 H8 Z6 (75,52)
    [34]       IH48(49) Z1 H7 Z21 H26 IH3(52) Z8 H8 Z4 (75,52)
    [35]       IH48(49) Z1 H7 Z21 H26 IH3(52) Z11 H4 Z5 (75,52)
    [36]       IH48(49) Z1 H7 IH3(52) P61 Z6 (75,52)
    [37:38]    IH48(49) Z1 H7 IH1(50) Z63 H4 (75,50)
    [39:40]    IH48(49) Z1 H7 IH1(50) Z62 H5 (75,50)

    Line list containing 40 lines:
    [1:4]      1-20(49)
    [5]        1-20(49) 58-62(50)
    [6]        38-42(50) 57-63(50)
    [7:8]      37-43(50) 57-63(50)
    [9]        11(52) 37-43(50) 58-62(50)
    [10]       10-13(52) 38-42(50)
    [11]       9-16(52)
    [12]       11-18(52)
    [13]       14-21(52)
    [14]       16-23(52) 25-55(49)
    [15]       19-24(52) 25(53) 26-55(49)
    [16]       21-24(52) 25-28(53) 29-41(49) 49-55(49)
    [17]       23-24(52) 25-30(53) 31-40(49) 50-55(49)
    [18]       25(49) 26-33(53) 34-39(49) 51-55(49)
    [19]       25-27(49) 28-35(53) 36-39(49) 51-55(49)
    [20]       25-30(49) 31-37(53) 38-39(49) 51-55(49)
    [21]       25-32(49) 33-39(53) 40(52) 51-55(49)
    [22]       15(49) 27-34(49) 35-39(53) 40-42(52) 51-55(49)
    [23]       28-37(49) 38-40(53) 41-45(52) 50-55(49)
    [24]       29-39(49) 40-41(53) 42-47(52) 49-55(49)
    [25]       2-8(49) 30-42(49) 43-49(53) 50-55(49)
    [26]       2-8(49) 30-44(49) 45-52(53) 53-55(49)
    [27]       2-8(49) 20(52) 31-46(49) 47-54(53) 55(49)
    [28]       2-8(49) 20(52) 31-49(49) 50-55(53) 56-57(52)
    [29]       2-8(49) 20(52) 31-51(49) 52-55(53) 56-59(52)
    [30]       2-8(49) 20(52) 31-54(49) 55(53) 56-61(52)
    [31]       2-8(49) 31-55(49) 57-64(52)
    [32]       2-8(49) 31-55(49) 59-66(52)
    [33]       2-8(49) 31-55(49) 62-69(52)
    [34]       2-8(49) 30-55(49) 64-71(52)
    [35]       2-8(49) 30-55(49) 67-70(52)
    [36]       2-8(49) 69(52)
    [37:38]    2-8(49) 72-75(50)
    [39:40]    2-8(49) 71-75(50)
.fi

The line list and range list tables shown consist of two columns, the first
listing the range of mask lines pointing to the line or range list shown to
the right (a sequence of identical mask lines will point to the same encoded
line list).  Each instruction which changes the mask pixel value is followed
by the new current mask value in parenthesis.  Zero ranges are omitted in
the range list format.  The "pl_circle" regions appear as ellipses since
a printed character does not have a unit aspect ratio.

.NH 3
Pixel List Descriptor

    For runtime access to a mask we require, for an N dimensional mask, an
N-1 dimensional array of line list pointers, plus the line lists themselves.
Multiple line list pointers may point to the same encoded line list.
All line pointers are valid at all times, i.e., NULL pointers are not
permitted, even for empty mask lines.  Initially, all line pointers will
point to the same entry, the encoded line list representation of an empty
line, i.e., a line of zeros (i.e., the single instruction ZN where N=axlen[1]).

.ks
.nf
	struct pldes {
		int	pl_magic	# magic / version no.
		int	pl_private1	# used by PMIO (ref_im)
		int	pl_private2	# used by PMIO (mapxy flag)
		int	pl_maxline	# max encoded line lentgh
		int	pl_maxval	# mask depth as max pixel value
		int	pl_naxes	# number of axes
		int	pl_axlen[7]	# axis lengths
		int	pl_plane[7]	# current plane for pl_setplane
		int	pl_llbp		# line list bufptr
		int	pl_llop		# next location in llbuf
		int	pl_lllen	# current llbuf length
		int	pl_llfree	# amount of free space in list
		int	pl_llnupdates	# line list has been modified
		int	pl_llinc	# llbuf increment on overflow
		int	pl_nlp		# number of line pointers
		int	pl_lp[]		# array of line pointers
	}
.fi
.ke

The main descriptor, which is a dynamically allocated data structure, is a
fixed size descriptor, the size of which depends upon the dimensionality and
size of the mask.  A single additional dynamically allocated buffer of type
\fIshort\fR is used to store the encoded line lists.  The size of this buffer
may vary at runtime as the mask is edited.  New line lists, or edited line
lists which increase in size, are inserted at the end of the buffer.
As existing line lists are freed a count of the amount of free space is
kept in \fIpl_llfree\fR.  If the percent of free space reaches a predetermined
level garbage collection is possible by copying the list, otherwise the line
list buffer is reallocated to increase its size.  The line pointers \fIpl_lp\fR
are actually offsets into \fIllbuf\fR, rather than true pointers.

.NH 3
External Storage Format

    A mask is stored externally as a variable length array of 32 bit MII
integers (the stored mask header) followed by two variable length arrays of
16 bit MII integers, packed in the following format:

.ks
.nf
	struct pl_extern {
		int	ple_magic	# magic / version no.
		int	ple_naxes	# mask dimensionality
		int	ple_axlen[7]	# length of each axis
		int	ple_llop	# output pointer into llbuf
		int	ple_lllen	# llbuf length, words
		int	ple_nlp		# number of line pointers (lines)
		int	ple_nlpx	# length of compressed index
		int	ple_exlen	# length of full pl_extern struct
		int	ple_flags	# flag bits
		int	ple_maxline	# saved pl_maxline
		int	ple_maxval	# saved pl_maxval
		short	ple_pkindex[]	# packed line list index array
		short	ple_llbuf[]	# line list buffer
	}
.fi
.ke

The \fIpl_compress\fR function is applied before a mask is encoded
into the external storage format, to eliminate the unused space in the line
list buffer which occurs during dynamic updates to the runtime list structure.
The line list index, containing one integer entry for each line in the mask
in the runtime format, is compressed using \fIpl_p2li\fR, storing in the
external representation the compressed array encoded as a line list in
\fIple_pkindex\fR.  This is especially important for large masks, as otherwise
the index array could be by far the biggest contributor to the size of the
mask when encoded into its external format.

No format conversions are required other than decoding the compressed line list
index and possibly byte swapping, hence accessing a stored list is very fast.
Further data compression is possible when packing the list for storage, but it
is not clear if this is justified.