path: root/sys/qpoe/QPOE.hlp

.help QPOE Jun90 "Quick POE Design"
.ce
\fBQuick-POE (Position Ordered Event File) Interface Design\fR
.ce
Doug Tody
.ce
July, 1988

.NH
Introduction

    The POE (Position Ordered Event file) facility is an interface and file
structure used to store and access the event (photon) lists generated
by event counting detectors.  Each event is described by a unique position,
time, energy, and possibly other parameters (e.g., polarization, position in
other coordinate systems, or instrument related parameters).  In the case of
an imaging event counting detector, the "image" generated consists of this list
of discrete events, rather than the regular matrix produced by a conventional
sampling detector.  Both types of detectors are fundamental to astronomy.

The POE interface is a stand alone interface built upon the standard VOS
interfaces DFIO (in a future release), PLIO, SYMTAB, FIO, and other lower
level interfaces.  The POE interface may be called directly by applications
code to create and access POE datafiles, for event file specific processing.
In addition, an IMIO image kernel is provided so that POE files may be
accessed as (read only) images, allowing existing IRAF image tasks to be
used to access POE files.  The main function of the POE image kernel is to
filter and sample the event list in real time, returning a conventional
sampled grid (image matrix) to the high level applications code.
The parameters controlling the filtering and sampling operations may be
specified by the user when the image (POE file) is accessed, making runtime
filtering of events possible in connection with any general image processing
task.

.NH 2
Important Concepts
    
    The primary object dealt with by this interface is the \fIevent file\fR,
consisting of a free format \fIfile header\fR and the main \fIevent list\fR.
The event list is a collection of \fIevent structures\fR, e.g., photons
hitting an imaging detector during the period of observation recorded by the
event file.  Each event is characterized by a standard set of attributes such
as the position of the event in detector, sky, or other coordinates, the time
at which the event was recorded, the energy of the event, and so on, plus
optionally additional instrument dependent attributes (in general the event
structure cannot be fixed, and the nomenclature may vary depending upon the
science being performed).

The events may appear in the event list in any order, but since most access
to image data tends to be spatial in nature, access will be most efficient if
the event list is position ordered.  This is the convention chosen by QPOE
and hence the name \fIpoe\fRfile, or \fIp\fRosition \fIo\fRrdered \fIe\fRvent
file.  An important alternative ordering is time ordering, which preserves
the order in which the events were originally recorded, but which requires
a complete scan of the event list to accumulate the events in a region of
interest during analysis.  There are cases where time ordering might be
preferable to position ordering, e.g., for time series analysis of a long
observation.

Of fundamental importance to the analysis of data from event counting
detectors is the concept of \fIfiltering\fR.  It is in the nature of event
counting detectors that they are often used to observe very faint objects
for very long periods of integration.  The total amount of data (number of
events) may be limited, so one wants to preserve all events, but since the
quality of the data may vary both with time and with position, it is common
to want to reject a portion of the data.  Conversely, the analysis being
performed may require one to examine only a portion of the data, e.g., only
events with a certain range of energies or arrival times, occurring within a
given region of the image.  Often the analysis will be repeated many times
wtih different filters.

Hence, most analysis of event counting data typically involves both
\fIrejection\fR and \fIregion of interest\fR filtering.  Rejection filtering
depends mostly upon the data itself, hence the rejection filter for an image
is a part of the image and should be in effect by default whenever the image
is accessed, although we would like to physically record all data and be able
to change the rejection filter either temporarily or indefinitely if desired.
Region of interest filtering, on the other hand, depends upon the scientific
analysis being performed rather than upon the data, hence is highly variable
and should be controlled by the user, independently of the data.

.NH 2
Interface Requirements

    Given the description of the problem to be solved presented in the previous
section, we can make the following observations regarding the POE interface:
.ls 4 o
A flexible binary file header supporting both scalar and variable length vector
fields is essential.  Examples of vector fields include the aspect and temporal
records (actually arrays of records, or subtables), the processing history
(probably stored as a single variable length text buffer), and the rejection
and region of interest filters (PLIO external format byte sequences stored as
opaque binary arrays).
.le
.ls o
In the general case the details of the event structure depend upon the
instrument for which data is being stored.  The minimum requirement is that
the event structure consist of a set of standard fields (x, y, time, energy)
followed by a variable length, instrument dependent area (hence the size of
the event structure, while fixed for a given datafile, should be allowed to
vary depending upon the data).  Ideally all fields should be named and
accessible for filtering, the names chosen should be variables rather than
constants, and the set of fields used to describe an event should be allowed
to vary depending upon the data.
.le
.ls o
Runtime access to the event list, including event-attribute and spatial
filtering, should be as efficient as possible since this is likely to be
by far the most time consuming part of the interface.  Header access
efficiency is much less important and is not expected to be a problem.
.le
.ls o
For most efficient access the event list should be stored sorted upon some
primary key, with an index maintained by the interface for that key,
and used for efficient retrieval.  The minimum requirement is that the primary
or sort key be the Y coordinate (corresponding to image lines).  Ideally it
should be possible for the sort key to be any field of the event structure,
or any combination of fields (e.g., Y+X, or T).  Ideally the interface itself
should be responsible for maintaining the event list in sort order; this is
not a requirement since writing to event files is much less common than
reading.  Ideally it should be possible for the event list to be unordered,
and it should be possible to transparently access the event list regardless
of the ordering.
.le
.ls o
Rejection filtering is typically required by the data, yet we wish to retain
all the data and be able to override or replace the default rejection mask.
The rejection filter is logically associated with the data and should be
stored with the data.  The minimum requirement is for the interface to be able
to store all the data plus the rejection mask, and be able to return only
the "good" data at runtime.  The interface is not required to perform rejection
filtering at runtime, although it would be desirable to be able to do so if
the efficiency penalty were not too great.  Alternatively, the event list
could be prefiltered, and the "good" and "bad" events stored in different
places in the datafile, requiring that the entire file be rebuilt to change
the rejection filter.
.le
.ls o
Region of interest filtering is a common operation for event data, and can be
difficult to implement efficiently, hence should be supported directly by the
interface.  At a minimum it should be possible to filter events by defining a
range of acceptable or unacceptable values for each of some subset of the event
attributes (e.g., energy or time).  Ideally it should also be possible to
specify an arbitrarily long list of ranges of acceptable values.  Ideally
spatial filtering should be supported as well; this is required for rejection
filtering, but is at most a desirable option for spatial region of interest
filtering (there is nothing about spatial filtering which is unique to event
data, hence it might be more appropriate to implement it at a higher level,
but on the other hand it might be more efficient to implement it at the event
i/o level since the event list is position ordered and can be very large).
.le
.ls o
It should be possible to specify the various filtering options both
transparently to applications programs (via a symbolic expression passed
into the interface by the user as part of the file specification),
or procedurally, via \fIset\fR-parameter calls issued by the client program.
.le

The above issues need to be adequately addressed in order to have a useful
interface.  In the longer term there are many other considerations, e.g.,
it is also desirable for the data format to be machine independent, and the
data format should be flexible, to accommodate the inevitable evolutionary
revisions as well as to accommodate data from a variety of instruments or
projects.  The event files can be very large, hence efficiency is a major
consideration for event i/o and filtering.

.NH 
The QPOE Interface
.NH 2
Implementation Strategy

    A two step operation is planned for implementing the POE interface within
IRAF.  The first step is the so called quick-POE interface.  The objective of
quick-POE is to provide the necessary functionality so that applications
development can proceed immediately, without waiting for the general interface
to be developed.  Once quick-POE is in place development of the fully general
POE interface can proceed at a more leisurely pace consistent with the plan to
provide most of the functionality of the generalized POE interface with other
standard IRAF facilities currently under development, most notably the datafile
i/o interface (DFIO), a general purpose binary file record manager to be used
in the new images structures project and elsewhere in IRAF.

The main facilities provided by POE are for access to general header fields,
access to the variable length aspect and temporal records, event list i/o,
and event filtering.  The POE header is a type of record, and the aspect and
temporal "records" are arrays of records (tables), as is the event list itself.
Any record access problem involving large records commonly involves the
related problems of indexing and selection based on a user supplied predicate
(boolean expression or filter in our case).

In the general case, we would like the POE interface to be able to support
data from a variety of detectors or instruments, not only those used in high
energy astrophysics but those used in optical and radio observatories as well,
hence the details of the data structures must be allowed to vary without
affecting the interface itself.  Ideally the POE files should be maintained
in a machine independent format, and the applications programs using POE
should not be affected by changes to the data format, and indeed should be
usable directly with any of several similar data formats, or with data formats
that evolve over time.

All these observations lead us to conclude that a general implementation of
the POE interface has much in common with the general record access problem,
hence the association of POE with DFIO.  Quick-POE will provide much the same
functionality at the applications level but will be less general, i.e., the
binary record structures as seen by applications will be mapped directly onto
external storage (the main contribution of DFIO is data independence and
flexibility).  This means that initially the applications will be tied to
a specific format datafile, changes to applications structures will require
reformatting the data, and the datafiles will probably be machine dependent.

This approach would be unacceptable in the long run, as the need arises to
support a variety of instruments, but is viable for initial applications
development provided a DFIO based implementation eventually replaces the
initial interface.  There should be little difference in terms of functionality
and efficiency between QPOE and POE; in fact QPOE may have the edge over POE
in terms of efficiency, since it will be less general.  It is likely that
applications developed for QPOE will be usable with POE with few if any
changes, e.g., by reimplementing QPOE as a layer on top of the more general
POE interface.  The main motivation for implementing a DFIO based POE will be
to provide increased data independence, a machine independent binary data
format, and the ability to support a variety of instruments with a single
interface.

Although some throw away code will have to be written to implement the QPOE
interface, most of the complexity of the interface lies in the event filtering
code, which should be reusable in the final interface.  Low level, custom
(non-DFIO) selection code is required for POE due to the unusual requirements
for region and temporal filtering, and the potentially extremely high data
volume (>10**6 event records).  This implies that DFIO itself will have to be
a layered interface, supporting low level access to the packed data records
for applications with unusual efficiency requirements (it will be).  Finally,
it is already evident that the low level file manager required by QPOE has
much in common with the access method code planned for DFIO, hence can serve
as a prototype for the DFIO file manager.

The remainder of this document will deal only with the details of the
QPOE interface.  The DFIO interface has already been specified,
including a sketch of a data definition for a POE file.  See \fIThe IRAF
Datafile I/O Interface\fR, February 1988.  The region filtering
code in POE will make use of the Pixel List I/O (PLIO) interface, described
in \fIThe IRAF Pixel List Package\fR, February 1988.  The latter interface
has already been implemented, as have all other interfaces (e.g., SYMTAB)
required by QPOE.

.NH 2
Architecture

    The architecture of IRAF as it pertains to the QPOE (and POE) interface
is summarized in the figure below.

.ks
.nf
        IMIO
                IKI
                        IK-POE
                                POE
                                        PLIO
                                        [DFIO]
                                        SYMTAB
                                        FIO
.fi
.ke

As indicated in the figure, QPOE depends most heavily on the VOS interfaces
PLIO (pixel list i/o), used for spatial filtering, SYMTAB (the general symbol
table package), used to manage the file header and aspect and temporal records,
and FIO (file i/o), used to access the binary file in
which the QPOE data is stored (low level, unbuffered asynchronous i/o is
used by the QPOE file manager).  The QPOE interface is accessed both directly
by applications code, and by the IMIO interface via an image kernel, shown
as IK-POE in the figure.  IK-POE and QPOE comprise the code to be written to
implement the QPOE interface.

The QPOE interface consists of the POE file itself, a binary data structure
[largely] private to the QPOE interface, and a set of procedures for creating,
writing into, and reading from POE files.  The procedures fall into several
categories, i.e.,
.ls 4
.ls o
General QPOE file management procedures.  These include routines for creating,
deleting, renaming, opening, and closing POE files, plus set/stat routines
for setting and querying the file parameters and interface options.
.le
.ls o
General header access procedures.  These include a conventional set of keyword
driven typed scalar get/put routines, plus get/put routines for accessing
variable length typed and opaque binary arrays (e.g., history records and the
aspect and temporal records).
.le
.ls o
Event i/o procedures.  These are routines for initially preparing and
subsequently reading (sequentially with seek) the main event list, e.g.,
the raw "get next photon" routine.
.le
.ls o
The selection subpackage.  Included are routines for opening and incrementally
compiling a user supplied selection predicate (filter) input as a formatted
text string, and for testing individual event records to see whether they
satisfy the given expression.
.le
.le

All binary data structures other than simple scalar variables, e.g., the
aspect and temporal records and the event structure, are described in QPOE
by compile time bound SPP binary data structure definitions, provided in a
standard interface include file (\fI<qpset.h>\fR) referenced by both QPOE and
selected applications.  When the interface is layered upon DFIO these
structures could continue to be used, since DFIO will have the ability to
define runtime mappings of conventional application defined structures onto
the physical data datafile (POE file) structures.

.NH 2
Interface Specification

    The quick-POE interface (QPOE, package prefix `qp') is a set of procedures
for accessing \fIpoefiles\fR, or position ordered event files.  Each poefile
consists of a \fBheader\fR of arbitrary size and content containing zero or
more named scalar or variable length (opaque, typeless) fields, plus an
\fBevent list\fR consisting of zero or more event structures.
The event structure is fixed at compile time via a conventional SPP structure
declaration in the include file \fB<qpset.h>\fR.

.NH 3
Interface Procedures

    The QPOE procedures fall into three main categories, the primary user
interface procedures (general datafile management, header access, and filtered
event i/o), the low level or raw event i/o procedures, and the low level
selection expression compile and evaluate procedures.

.NH 4
Header Access Procedures

    The routines described in this section are used to create, open, or
otherwise manipulate poefiles, to define new header parameters or query the
existing parameter set, and to read and write the values of both scalar and
vector parameters of various standard and poefile-specific datatypes.
These operators are summarized in the figure below.

The function of most of these procedures should be obvious.
The \fIqp_access\fR, \fIqp_delete\fR, \fIqp_rename\fR, and \fIqp_copy\fR
operators perform the implied operation on the named poefile.
The poefile may be rebuilt with \fIqp_rebuild\fR, recovering any unused
space and rendering storage for the internal data structures (logically)
contiguous in the process (a rebuild is just a copy/rename/delete).

The \fIqp_open\fR procedure must be called to open or create a poefile,
before it can be accessed.  The NEW_FILE and NEW_COPY modes are supported
for creating new files.  If NEW_COPY mode is specified, a reference file
may be specified (via the descriptor \fIo_qp\fR) from which the new file
is to inherit the header but no data (no event list).
The \fIqp_seti\fR and \fIqp_stati\fR procedures are used to set and stat
any parameters affecting QPOE i/o, and \fIqp_sync\fR updates an opened
poefile on disk.

The \fIqp_get\fR and \fIqp_put\fR scalar functions behave as for the other
VOS interfaces, e.g., they will abort if the named parameter does not exist,
or if the implied datatype conversion is illegal.  The \fIqp_add\fR 
procedures are equivalent to the \fIqp_put\fR procedures except that they
will create the named parameter if it does not already exist (see also
\fIqp_addf\fR, discussed below).

.nf
         yes|no = qp_access (poefile, mode)
                    qp_copy (poefile, newfile)
                  qp_rename (poefile, newfile)
                 qp_rebuild (poefile)
                  qp_delete (poefile)

               qp = qp_open (poefile, mode, o_qp)
                    qp_seti (qp, param, ival)
            ival = qp_stati (qp, param)
                    qp_sync (qp)
                   qp_close (qp)
           
     val = qp_get[bcsilrdx] (qp, param)
                    qp_gstr (qp, param, outstr, maxch)
           qp_put[bcsilrdx] (qp, param, val)
                    qp_pstr (qp, param, strval)
           qp_add[bcsilrdx] (qp, param, defval, comment)
                    qp_astr (qp, param, strval, comment)

              fd = qp_popen (qp, param, mode, type)
            nelem = qp_read (qp, param, buf, nelem, first, dtype)
                   qp_write (qp, param, buf, nelem, first, dtype)

        yes|no = qp_accessf (qp, param)
                 qp_deletef (qp, param)
                 qp_renamef (qp, param, newname)
                    qp_addf (qp, param, dtype, maxelem, comment, flags)
	  nelem = qp_queryf (qp, param, dtype, maxelem, comment, flags)

         list = qp_ofnl[su] (qp, template)
          nch|EOF = qp_gnfn (list, outstr, maxch)
                    qp_cfnl (list)
.fi

Array valued parameters may be randomly read with \fIqp_read\fR and
written with \fIqp_write\fR; arrays may be any length, and will be
automatically extended in a write.  The only way to shorten an array
parameter is to copy it and delete the old parameter.  The typed read and
write functions allow automatic type conversions, and external storage of
the data in a machine independent form (should the interface choose to do so).
In addition to the standard SPP types, QPOE supports the special types
TY_EVENT, TY_ASPECT, and TY_TEMPORAL.  Finally, the type TY_OPAQUE denotes
an array of element size SZ_CHAR, which will be copied to and from external
storage without the data being modified in any way (note that opaque data
is machine independent only if the application encodes it that way).

Alternatively, an array valued parameter may be opened as a random access
\fIfile\fR with \fIqp_popen\fR, and then read or written with conventional
FIO calls.  The value of the \fItype\fR parameter must be TEXT_FILE or
BINARY_FILE, as for a conventional file.  If the type is TEXT_FILE then
only text data may be stored in the file, and text data will be byte packed
on disk.  The BINARY_FILE type is equivalent to the QPOE type TY_OPAQUE.
File i/o to a QPOE parameter is equivalent to file i/o to a conventional
binary file in terms of both efficiency and semantics, i.e., the data is not
modified in any way, and the "files" may be any size (the main semantic
difference is that deleting the parameter does not immediately free the space).
A parameter opened as a file with \fIqp_popen\fR is closed with the FIO
\fIclose\fR routine.

Although new parameters may be defined when first written to by calling one of
the typed \fIqp_add\fR functions, the most general procedure for adding new
parameters is \fIqp_addf\fR, which allows the datatype and vector length of
the parameter to be explicitly specified, along with a comment describing the
new parameter.  The procedure \fIqp_accessf\fR tests if the named parameter
exists, and \fIqp_deletef\fR and \fIqp_renamef\fR make it possible to delete
and rename parameters, e.g., for implementing array copy procedures.
The \fIqp_queryf\fR procedure returns the datatype, allocated vector length,
current vector length, and comment field of the named parameter.

The field name list procedures (\fIqp_ofnl[su]\fR etc.) are used to obtain
the names of all header parameters matching the given template; a null or "*"
template returns the names of all header parameters.  This is the only way by
which an application without apriori knowledge of the field names can determine
what is in the header, e.g., to list or copy the header.

.NH 4
Filtered Event I/O Procedures

    The \fBevent i/o\fR subpacke provides sequential i/o facilities for the
main event list of the poefile.  These procedures, known as the QPIO (QPOE
event i/o) package, provide read or write (append) access to the event list,
optionally filtered when reading to select events spatially or by event
attribute.

Under QPOE, an event list is stored as a variable length array (i.e., as a
named header parameter) of type \fIevent\fR.  The QPIO package takes this
basic object and adds additional structure for more efficient i/o, e.g., events
are blocked into large, fixed size \fIbuckets\fR of N events, the first two
events of each bucket containing the minimum and maximum event values for that
bucket.  If the event list is sorted an \fIindex\fR may be maintained for the
list; this index, plus the min/max event values maintained for a bucket, are
used to optimize basic event i/o and filtering.  During event i/o the raw
event list may be filtered spatially or by event attribute.  All this is
transparent to the application, which merely opens the event list parameter
and begins reading (or writing) blocks of events.

Before i/o can take place the named event list parameter is opened with
\fIqpio_open\fR.  The selection filter to be used by QPIO may be specified
via a selection expression passed in by the user at poefile open time (as
part of the poefile name), at QPIO open time (as part of the parameter name),
or in subsequent calls to \fIqp_addfilter\fR (each call incrementally modifies
the current filter) or to \fIqp_setfilter\fR (each call replaces the affected
portion of the current filter).  A region mask may also be specified with
\fIqp_setmask\fR; if no mask is specified, the default rejection mask is used
(or more precisely, its inverse).

.nf
           qpio = qpio_open (qp, param, mode)
               qpio_mkindex (qpio, key, nelem)
              qpio_setrange (qpio, vs, ve, ndim)
       qpio_[add|set]filter (qpio, selexpr)
    nchars = qpio_getfilter (qpio, outstr, maxch)
               qpio_setmask (qpio, pl)
          pl = qpio_getmask (qpio)
   nev|EOF = qpio_getevents (qpio, ev, maskval, maxevents)
             qpio_putevents (qpio, ev, nevents)
               qpio_readpix (qpio, obuf, vs, ve, dxim, xblock, yblock)
                 qpio_close (qpio)
.fi

Events are read sequentially with \fIqp_getevents\fR, which fills in the
pointer array \fIev[maxevents]\fR with one or more pointers to event structs,
returning the number of events read as the function value, or EOF when the
event list is exhausted.  Events are returned in the order in which they are
stored in the main event list.  If a region mask is used for spatial
filtering, the mask value associated with the output events is returned in 
\fImaskval\fR.  Filtering and subranges are supported only for reading;
\fIqp_putevents\fR may only be used to append to the output poefile.
At present, poefiles are not randomly updatable, as this would require
runtime editing of the compressed event lists and it is not clear how useful
such a feature would be.

If less then the entire image is to be accessed then \fIqp_setrange\fR
may be called to specify the region of the poe image from which events are
to be read (the vector coordinates \fIvs\fR and \fIve\fR are specified
relative to the predefined primary event coordinate system, i.e., the PO
coordinates).  Repeated calls to \fIqp_setrange\fR may be made to access
multiple regions of the image, or to rewind the i/o pointer for a region.

An alternative to event i/o is provided by \fIqp_readpix\fR, which samples
the event list using the current filters and blocking factor,
generating \fInpix\fR pixels beginning with the pixel at the image coordinates
specified by the vector \fIv\fR.  This is the routine used by the POE IMIO
image kernel to read from a poefile.  Only integer pixels are supported.
On output, each pixel value is a count of the number of filtered events
mapping into that pixel.  A region mask may be used to filter the event list,
but the ability to discriminate between different regions by the mask value
is lost.

A poefile may contain any number of event list parameters, although most
files are expected to store only the main event list.
As an alternative to QPIO, event-array parameters may be accessed directly
via the normal header access parameters, e.g., \fIqp_read\fR, but i/o may be
somewhat less efficient (due to the copyout), the bucket structure will be
visible, and no filtering is possible.  In short, the raw event list will
be accessed as an array, returning the min/max events in each bucket along
with the data events.

In the current implementation, the event structure is a fixed, predefined
binary structure, and all event i/o is expressed in terms of pointers to event
structures.  The event structure is defined in the include file
\fB<qpset.h>\fR, discussed in the appendix.

.NH 4
Selection Subsystem Procedures

    The \fBselection subsystem\fR is a facility used to perform runtime
filtering of the event list, returning to the calling program only those
events satisfying some user defined selection criteria.  The selection
subsystem is driven by a selection expression provided by the user as a
formatted string, normally at image (poefile) open time.  The selection
expression syntax itself is independent of the procedural interface and is
described separately in section 2.3.2.  The selection procedures are
summarized in the figure below.

.nf
	     ex = qpex_open (qp, expr)
    ok|err = qpex_modfilter (ex, exprlist)
    nchars = qpex_getfilter (ex, outstr, maxch)
	nev = qpex_evaluate (ex, i_ev, o_ev, nev)
		 qpex_close (ex)
.fi

A selection expression, input as the string \fIexpr\fR, is compiled with
\fIqpex_open\fR, which returns a pointer to the runtime descriptor (filter)
for the given compiled selection expression.  If \fIexpr\fR is the null
string the filter returned will pass all events.

An active filter may be modified with \fIqpex_modfilter\fR, which combines
the expression \fIexpr\fR into the current filter, allowing complex
filters to be built up in several calls, or allowing an application to modify
a base filter without knowledge of the base filter.  The expression consists
of a list of comma delimited "attribute = exprlist" terms.  If the assignment
is specified as "=" the term for the given attribute is replaced; if the
assignment is "+=" the term for the given attribute is further qualified.
A text representation for the current filter may be obtained at any time with
\fIqpex_getfilter\fR.  The boolean function \fIqpex_evaluate\fR is called to
test whether a specific event meets the selection criteria, i.e., to test
whether or not \fIexpr\fR is true for the given event.

Selection is normally performed transparently to the application by the QPIO
interface, which calls the routines described in this section to create and
apply event-attribute filters.

.NH 3
Spatial and Event Attribute Filtering
.NH 4
Selection Syntax

    Selection expressions are used to construct \fIfilters\fR to specify the
rejection mask and region of interest filters before reading the event list
via QPIO.  Due to the complexity of event attribute selection, selection
predicates are specified syntactically, i.e., as an expression input as a
text string.  These filters may be input by the user as part of the image
or poefile specification (object name), transparently to applications code,
or they may be constructed by the application via calls to the QPIO or
selection routines.  Complex or frequently referenced filters may be stored
in text files and referenced by filename if desired.  It does not matter
whether a filter is input all at once, or compiled incrementally.

An event attribute filter consists of a set of filters for each event
attribute.  By default, i.e., if no filter is specified, all attribute values
are passed.  If a filter is specified for an attribute, the filter specifies
either a bitwise mask value, or a list of acceptable values or ranges of values
for the attribute.  An event is passed if and only if all event attribute
filters pass the event.  If a list of acceptable values are specified, the
list may be any length, with little impact on filtering efficiency.

The basic event attribute filter syntax consists of a list of attribute
filters, e.g.:

        attribute = values [, attribute = values ...]

where \fIattribute\fR is the attribute name, e.g., a position attribute,
time, energy, and so on, and \fIvalues\fR is a mask or list of values.
Mask values are integers prefixed by `%', e.g.,

        attribute = %1003B

Note that the mask may be specified in decimal (the default), octal (`b' or
`B' suffix), or hex (`x' or `X' suffix), in accord with the usual IRAF
conventions.  The meta-characters used in selection expressions have been
selected to avoid or at least minimize the need to quote such expressions
in CL commands.

A specific value or list of values may be specified as a
simple integer constant, or comma delimited list of constants, e.g.:

.nf
        attribute = 3
or
        attribute = 3, 5, 20X
.fi

Ranges are specified using the `:' notation, e.g.,

        attribute = 3, 5, 8:11

A `!' may be prepended to indicate the opposite, i.e., "everything but":

.nf
        attribute = !%14B
or
        attribute = 3, !1:10
.fi

Open ended ranges may be used to indicate that the range includes all values
less than or equal to or greater than or equal to the given value, e.g.,

        attribute = :100

denotes all values less than or equal to 100.

File inclusion or \fImacro expansion\fR is denoted by a C-like function call
notation, e.g.,

.nf
        macro()
or
        macro(a,b)
.fi

Any arguments are expanded via string substitution when the text of the macro
or include file is expanded.  Include files should have the extension ".qpm".
Macros are permitted only if the variable \fBqpinit\fR is defined in the user's
environment, the string value consisting if the filename of the user's QPOE
macro file.  In a reference to a macro \fImacro\fR, QPOE will look first in
the macro definitions file pointed to by \fIqpinit\fR for the named macro,
then it will look for the file "\fImacro\fR.qpm" in the current directory.

Parenthesis are optional and may be included to, for example, make attribute
value lists more easily identifiable.  If a line ends in a comma or backslash
continuation is assumed; blank lines and comment lines are ignored.
The syntax for attributes with floating point values is identical to that
for integers except that mask values are not allowed.

.NH 4
Region Specification

    QPOE does not itself contain any syntax-level support for specifying
region masks, e.g., via a list of include and exclude circles and other
shapes.  The reason for this is that it is too difficult to come up with
a sufficiently general scheme at the level of an interface like QPOE;
there are too many ways to specify regions, hence in general such region
specification must be done at the applications level.  QPOE does however
include very general and efficient support for region analysis provided the
region mask is input already encoded into a PLIO binary mask.  Since PLIO
includes high level primitives for defining masks in terms of include and
exclude circles, boxes, lines, polygons, etc., it is easy to extend QPOE at
the applications level to include support for a region specification language
tailored to the specific application.

While QPOE cannot itself process a user defined region description to create
new region masks, it is possible to \fIselect\fR from any number of region
masks if these are prepared in advance using other systems facilities or
applications programs.  PLIO region masks may be stored in the QPOE header
as named parameters of type opaque binary array, or they may be stored in
external binary files.  The region mask to be used may be specified by
including an assignment of the form

        mask=[\fIparam\fR|\fIfile\fR.pl]

in the selection expression.  Unless otherwise specified, this region mask 
will be combined with the default rejection mask for the poefile (the final
mask will be the region mask \fIand\fR-ed with the \fInot\fR of the rejection
mask).

.NH 4
Predefined Selection Keywords

    While the syntax of a selection expression is an inherent part of the
QPOE interface, the names of the event attributes used in selection
expressions are logically part of the event structure, and ideally should
be stored with the data and used by the interface only to determine the
attribute datatypes and offsets into the event structure when the selection
expression is compiled at runtime.  We should not really be documenting the
specifics of the POE external data structures here, but in QPOE these data
structures are wired into the interface, so it is appropriate to do so.

The following \fIstandard event attributes\fR are defined.  Minimum match
abbreviations are of course permitted.  The keyword \fIpi\fR is an acceptable
alias for \fIenergy\fR (\fIpi\fR and \fIpha\fR are examples of discipline
dependent terminology which should be associated with the data and not the
interface).

.nf
        X               short           range in X (PO coords)
        Y               short           range in Y (PO coords)
        TIME            real            time event was recorded
        ENERGY,PI       int             energy of event
        PHA             int             pulse height
.fi

The event attributes may also be referred to using the generic notation
[\fIsir\fR]\fIN\fR, which refers to each attribute by its datatype and
struct offset (byte units, zero indexed) rather than by name.  For example,
if the event attributes shown above are assumed to be shown in the order
in which the fields are stored in the event struct, the \fItime\fR field
could also be referred to as \fIR4\fR, and \fIpha\fR as \fII10\fR.  This
crude but effective technique may be used to reference any private
(nonstandard) fields of the event struct in selection expressions.

The following additional, non-event keywords are defined:

.nf
        BLOCK           int             \fIqp_readpix\fR blocking factor
        MASK            string          region mask to be used
        FILTER          string          region filter to be used
        REJMASK         string          rejection mask to be used
        REJFILTER       string          rejection filter to be used
.fi

The default values for these parameters are taken from datafile header
parameters of the same name, if such are found.  Masks are specified either
by the name of a header parameter of type opaque binary array (containing
an encoded PLIO mask), or by the name of a PLIO mask file, extension ".pl".
Named filters are specified by the name of a header parameter of type char
array, or by the name of a text file (extension ".qpf"), where in either
case the named object contains the selection expression text.

.NH 3
Interface Set/Stat Parameters

    The internal parameters for the QPOE interface, and all user accessible
data structures, e.g., the event and other structures, are defined in the
global system include file \fB<qpset.h>\fR.  This file should be referred to
for up to date documentation on these definitions and structures; the
discussion which follows may not be kept up to date.

The following interface parameters may be accessed via the \fIqp_seti\fR and
\fIqp_stati\fR procedures:

.nf
        QP_XRESOLUTION          resolution of an event x-coordinate
        QP_YRESOLUTION          resolution of an event y-coordinate
        QP_LENEVENT             length of an event structure
        QP_LENINDEX             resolution of the event list index
        QP_BUCKETSIZE           event list bucket size, nevents
        QP_PAGESIZE             datafile page size, bytes
        QP_CACHESIZE            number of buffers in data buffer cache
        QP_MAXFILES             max lfiles in datafile (fixed)
        QP_NFILES               query number of lfiles in datafile
        QP_NPAGES               query number of pages in datafile
        QP_FREEPAGES            query number of free pages in datafile
.fi

The parameters shown above may be set only at datafile creation time.
The X and Y resolution parameters define the range of event x,y coordinates.
The resolution of the event list index is set by QP_LENINDEX, and may be less
than the full resolution of the event pixel Y-coordinate.
The remaining parameters control how storage is physically allocated in the
datafile and in any event lists.

.NH 2
Detailed Design
.NH 3
Event Attribute Filtering

    The point of event-attribute filtering is to test an event to see if it
satisfies a user defined event selection expression.  A selection expression
may be decomposed into a list of simple, independent expressions for the
individual event attributes; the event satisfies the full expression only
if the value of each event attribute satisfies the associated attribute
expression.  Currently, attribute expressions are limited to bitmasks, lists
of acceptable values, or lists of ranges (inclusive) of acceptable values.

        attr1=expr, attr2=expr, ...

The highly constrained nature of event-attribute expressions makes expression
evaluation straightforward and fast.  Expression evaluation is implemented
by logically negating each attribute expression and testing each in turn;
expression evaluation ends either when an attribute test fails, in which case
the event is rejected, or when the end of the attribute expression list is
reached, in which case the event is passed.

The obvious way to implement such an expression evaluator is with a simple
interpreter.  The expression is parsed and compiled to produce a simple
interpreter program, using the instructions shown in the figure below.

.ks
.nf
        \fIinstruction     arguments\fR

        MSK[sir]        offset  maskval         bitwise mask test
        EQL[sir]        offset  value           equality test
        LEQ[sir]        offset  value           less than or equal
        GEQ[sir]        offset  value           greater than or equal
        RNG[sir]        offset  lowval highval  range test (inclusive)
        LUT[sir]        offset  lut             lookup table
        NOT                                     invert test
        RET                                     return, pass event
.fi
.ke

An interpreter program consists of a series of these instructions.  The
\fIoffset\fR argument gives the offset of the event attribute (field) to
be tested; the datatype of this field must match that of the instruction
and of the data argument or arguments, if any.  Only event attributes for
which restricted values were specified are tested, hence the cost of the
evaluator depends only upon the complexity of the expression to be evaluated.
An interpreter of this type can be coded very efficiently as a switch-case
statement (jump table) within an optimized DO-loop.

Simple attribute value tests are most efficiently coded as several \fIMSK\fR,
\fIEQL\fR, etc., instructions.  The only case of any complexity is where the
attribute has a long list of acceptable values or ranges of values.  This is
most efficiently coded using a lookup table, using the \fILUT\fR instruction
shown in the figure.  A lookup table test may be preceded by a range test to
limit the size of the lookup table required.  For an integer or short integer
attribute, the lookup table will be a \fIboolean\fR table containing one entry
for each possible value of the attribute in the range spanned by the table.

Use of a lookup table for floating point attributes is more difficult since
an enormous lookup table might be required to preserve the resolution of
the floating point numbers used to define ranges.  The solution is to employ
an \fIinteger\fR (rather than boolean) lookup table of \fIreduced resolution\fR.
The floating point value of the attribute to be tested is mapped into a bin of
the lookup table.  The integer value of the table entry has one of the
following values:

.ks
.nf
        0               Reject all FP numbers mapping to this bin.
        1               Accept all FP numbers mapping to this bin.

        N               Some of the FP numbers mapping to this bin are
                        legal, and some are not.  The value N is the
                        address of a segment of interpreter code to be
                        executed to test a FP value mapped to this bin.
.fi
.ke

The performance of this algorithm for floating point table lookup depends
upon the frequency with which 0 or 1 is encountered as the table value during
lookup; if 0 or 1 is encountered most of the time, then a floating point LUT
test is comparable in expense to an integer LUT test.  But since we already
have to map a floating point number into an integer space of reduced
resolution, we can easily vary the resolution of the lookup table,
increasing the resolution of the table until the desired level of efficiency
is reached (the interpreter execution time for case N is pretty fast in any
case, so this is not critical).

In summary, the expense of event-attribute filtering is directly proportional
to the number of attribute tests to be performed.  An arbitrary number of
values or ranges of values may be specified for an attribute with little if
any affect on performance, even for floating point attributes (e.g., for
time-tagged quality filtering).

.NH 3
Region Filtering

    Region filtering is implemented in QPOE by the PLIO interface, which is
documented elsewhere.  PLIO permits regions of arbitrary complexity to be
described and used for event filtering, with little overhead beyond that
already present for i/o on a large event list with no region filtering.
This assumes only that the event list is position ordered, and that the
region mask is specified in the PO (position ordered) coordinate system.
This makes it possible for QPIO to use the mask to reduce the number of
events to be examined; event attribute filtering is performed only on those
events read through the region mask (this is similar to masked image i/o,
i.e., the MIO package).

If the event structure supports multiple coordinate systems and the region
mask refers to a non-PO coordinate system, then the only approach is to first
perform event-attribute filtering on the non-positional event attributes,
then for each event passing the event-attribute filter, fetch the mask value
corresponding to the x,y coordinates of the event.  This is still an efficient
technique since only mask pixel lookup is required (no complicated region
list traversal is involved), but it will be significantly less efficient than
PO region filtering since we cannot take advantage of position ordering to
reduce the number of events to be examined, and the overhead of accessing
the region mask will be greater.

.NH 3
Datafile Layout and Access
.NH 4
File Structure

    The QPOE file structure is private to the QPOE interface and is discussed
here only for the purpose of detailing (and documenting) the design of the
interface.  The QPOE file is a random access, dynamically extendable, binary
file.  Under QPOE these files will be partially, but not completely, machine
independent, hence file sharing by machines of different architectures will
not be provided initially.  This will be rectified when management of the
datafile is later turned over to DFIO.

To provide a reasonable degree of flexibility, QPOE contains many
variable length data structures, e.g., there may be any number of header
parameters, including array valued parameters of arbitrary size.  New header
parameters may be added at any time, and new data may be appended to array
parameters at any time.  This flexibility places certain demands upon the
low level file manager used to maintain these data structures in the datafile.

All access to the physical datafile is via a low level binary
\fIfile manager\fR.  The purpose of the file manager is to implement a
restricted implementation of the binary file abstraction upon a single host
level binary file.  This provides the "lightweight" binary file mechanism we
need for QPOE.  Since the file manager is a low level facility, it is
implemented using only the low level asynchronous i/o facilities provided
by FIO to read and write file pages, once the file has been opened.

The file manager provides routines for creating new datafiles, and for
creating, deleting, etc., \fIlightweight files\fR (lfiles) within a datafile.
Storage for lfiles is allocated in units of datafile \fIpages\fR.  For each
data page in the datafile there is an entry in the datafile \fIpage table\fR.
The page table itself is stored as an lfile (\fIlfile zero\fR) in the data
pages.  Files at the file manager level are known only by their file number;
association of these file numbers with file names is left up to the higher
level code, and in the case of QPOE is done with the symbol table (which is
also stored as an lfile).

.ks
.nf
         +-----------------+
           datafile header              fixed size
         +-----------------+
              file table                fixed size
         +-----------------+
                  |
              data pages                data and page table pages
                  |                        (arbitrarily large)
                  v
.fi
.ke

The page table is a vector mapping datafile pages by file offset onto lfile
file numbers; the value of each page table entry is the file number of the
lfile to which the page is assigned.  When the file manager opens an lfile
it scans the page table, extracting the page numbers of the pages assigned
to the lfile, to form a vector mapping lfile page offsets directly onto
datafile page offsets.  New pages are always allocated at the end of the
datafile, and new lfiles are always allocated at the end of the file table,
hence lfile deletion will leave "holes" (unused storage) in both the datafile
pages and file table.  A \fIrebuild\fR operation is required to reclaim the
space occupied by these holes.  Deleted files are recoverable by merely
revalidating their file table entries.

Every variable size object managed by QPOE is stored in the datafile as a
distinct lfile.  Since storage for lfiles is allocated in units of file pages,
the minimum amount of storage used by a variable length object is 0 or 1 page.
Examples of variable size objects are the SYMTAB symbol table
used to describe the contents of the datafile header (and any other symbols
used by QPOE), the static data storage area (used to store the values of
scalar and static array valued header parameters), and individual variable
length arrays.  Note that each variable length array is stored in the datafile
as a separate lfile; if the maximum size of an array is less then the page
size, it will be more efficient to store it as a static array.

The most important example of a variable length array is the main event list
of the poefile.  To improve i/o efficiency and speed selection, the event
structs stored in an event list are grouped together into \fIbuckets\fR,
as discussed earlier in section 2.3.1.2.  Each bucket will always occupy an
integral number of file pages.  Storage for buckets is allocated contiguously
in the datafile, and buckets are always read and written to disk in a single
i/o transfer.

The most important physical datafile parameters are hence the page size and
the bucket size.  A larger page size can improve i/o efficiency and reduce the
size of the page table, but can lead to significant wasted space if there are
many variable length arrays.  Since the i/o system will move entire large
blocks of pages to and from disk whenever possible, use of a small page is
normally preferred.  A large bucket size improves i/o efficiency for event
lists, but if the bucket size is too large then bucket searching takes longer,
and selection efficiency may decrease.

.NH 4
File Manager

    The function of the file manager is to map a set of lfiles onto a single
random access host binary file.  The file manager must keep track of the size
and type of each file, and whether or not it has been deleted.
In addition, the file manager must maintain a page table for the entire
datafile, noting the lfile to which each page is assigned.  While an lfile
is open the file manager must maintain the page vector for that lfile so that
lfile offsets may be mapped directly onto datafile offsets.

The number of lfiles is fixed at datafile creation time, and lfiles are
referred to by file number.  File number zero is the datafile page table;
the first user lfile is number one.  A datafile with a max file count of one
would actually contain two lfiles, counting the page table.

The file manager interface is summarized in the figure below.  A new datafile
may be created or an existing datafile opened with \fIfm_open\fR.
If a new datafile is being created the page size and max file count may be
changed from their default values with calls to \fIfm_seti\fR, and the values
of these and other parameters may be queried at any time with \fIfm_stati\fR.  
An opened datafile may be copied with \fIfm_copyo\fR, omitting deleted lfiles
and rendering file segments contiguous.  The page size and max file count
may be changed in a copy operation if desired.

The \fIfm_access\fR, \fIfm_rename\fR, and \fIfm_delete\fR routines perform
the indicated operation upon the named datafile.  The \fIfm_rebuild\fR
routine rebuilds a datafile, discarding deleted structures and coalescing
storage for objects.  This routine, as well as \fIfm_copy\fR, are built upon
on the lower level routine \fIfm_copyo\fR,  which does the real work, and
which allows the structural attributes of the new datafile to be specified
in \fIfm_seti\fR cals.

All i/o to lfiles is via the six routines beginning with \fIfm_lfopen\fR in
the figure below.  These routines constitute a FIO binary file driver for
lfiles, and may be called directly, or passed to the FIO routine \fIfopnbf\fR
to open an lfile as a binary file (\fIfm_lfname\fR should be called first
to construct a pseudo-filename for the lfile so that \fIfm_lfopen\fR can
reconstruct the file manager descriptor, lfile number, and lfile type).
Note that the lfile driver routines are unbuffered and (potentially)
asynchronous, and that i/o must be in units of datafile pages.
(See the buffer cache routines described in the next section for a higher
level facility for i/o to lfiles).

.nf
        yes|no = fm_access (datafile, mode)
                  fm_rename (datafile, newname)
                    fm_copy (datafile, newname)
                  fm_delete (datafile)
                 fm_rebuild (datafile)

               fm = fm_open (datafile, mode)
                    fm_seti (fm, param, ival)
            ival = fm_stati (fm, param)
		   fm_debug (fm, out, what)
                   fm_copyo (fm, fm_to)
                    fm_sync (fm)
                   fm_close (fm)

       lfile = fm_nextlfile (fm)
                  fm_lfname (fm, lfile, type, lfname, maxch)

                  fm_lfopen (lfname, mode, lf)
                 fm_lfstati (lf, param, ival)
                 fm_lfaread (lf, buf, nbytes, offset, status)
                fm_lfawrite (lf, buf, nbytes, offset, status)
                 fm_lfawait (lf, status)
                 fm_lfclose (lf, status)

                  fm_lfstat (fm, lfile, statbuf)
                fm_lfdelete (fm, lfile)
              fm_lfundelete (fm, lfile)
.fi

In a sense, all lfiles exist as zero length files when the datafile is
created, since the lfile descriptors are preallocated and the files are
known only by number.  Lfiles become interesting when they are opened as
files with \fIfm_lfopen\fR, and data is written into the file.  An lfile
may be deleted with \fIfm_lfstat\fR.  All this does is set the delete bit
in the lfile descriptor, hence a deleted lfile may later be undeleted with
\fIfm_lfundelete\fR.  The data in a deleted lfile is not lost until the lfile
is again opened and written into, or the datafile is rebuilt.  Information
on a specific lfile (size, type, etc.) may be obtained with \fIfm_lfstat\fR.

There is nothing about the file manager which is specific to QPOE, so it is
implemented as a separate, standalone facility, and may be used in applications
other than QPOE.

.NH 4
Buffer Cache

    For reasons of efficiency, QPOE maintains portions of the datafile in
memory buffers while a datafile is open.  The main QPOE descriptor, symbol
table, and file manager descriptor and page table are maintained in special
runtime data structures internal to the respective interfaces.  All other
data is stored in lfiles and accessed only upon demand.  In particular,
storage for all static (non variable length) QPOE header parameters is
maintained in a single lfile, and storage for each variable length parameter
is allocated in a separate lfile.

Since most access to QPOE header parameters is via simple gets and puts to
named parameters, lfile access is handled by QPOE transparently to the client
applications program.  To avoid excessive disk i/o when randomly accessing
the datafile, it is desirable for QPOE to maintain a cache of several lfile
data buffers, e.g., so that accesses to a series of static parameters or
repeated accesses to read or write different parts of an array parameter
should incur minimal disk accesses.  This buffer cache is implemented in
QPOE by simply opening each lfile as a file under FIO, leaving it up to FIO to
manage the file buffer, and maintaining a LRU cache of open lfiles in QPOE.
The number of buffers (open lfiles) is controlled by the QP_CACHESIZE
parameter.  Since the lfile buffer cache is a general datafile related
facility, it is implemented by the file manager.

.ks
.nf
              fd = fm_getfd (fm, lfile, mode, type)
                   fm_retfd (fm, lfile)
                 fm_lockout (fm, lfile)
                 fm_debugfd (fm, out)
.fi
.ke

The \fIfm_getfd\fR routine maps an lfile onto a file descriptor.  A file
descriptor is opened on the lfile only when necessary.  Once opened, an lfile
remains in the cache until forced out by the LRU replacement algorithm,
or the datafile is closed.  Removal of an lfile from the cache (closing the
associated file descriptor) is permitted only after a call to \fIfm_retfd\fR;
calling this routine does not immediately close the file, it only permits it
to be closed.  Most calls to \fIfm_getfd\fR should return a file descriptor
immediately, with very little overhead, with an already active file buffer,
hence repeated calls to the cache manager and FIO may be made without
incurring any disk accesses.

Note that lfiles may be opened on file descriptors via direct calls to the
file manager, regardless of whether these lfiles are already open in the
buffer cache.  This allows two or more independent file buffers to be
simultaneously active on the same lfile, but opens the possibility of loss
of data if the buffers overlap.  If this is a problem, the routine
\fIfm_lockoutfd\fR may be called to prevent inadvertent use of an lfile by
the cache.  This should be followed by a call to \fIfm_retfd\fR to clear the
lockout bit once the reason for the lockout (usually a noncached lfile open)
is gone.  The routine \fIfm_debugfd\fR will print information on \fIout\fR
describing the contents of the buffer cache.

.tp 24
.NH 3
Interface Structure
.NH 4 1
Header Access Package (QP Routines)

    The structure of the general QPOE routines (mostly header access) is
illustrated in the figure below.

.ks
.nf
                                +--------+
                                |   QP   |
                                +--------+
                                 /      \
                                /        \
                        +--------+      +--------+
                        | SYMTAB |      | BCACHE |
                        +--------+      +--------+
                                             |
                                      +--------------+
                                      | FILE MANAGER |  
                                      +--------------+

              Figure 1.  Structure of the Header Access Routines
.fi
.ke

To fulfill a get or put header access, QPOE will access the symbol table
(SYMTAB) to lookup the symbol name and determine the symbol datatype, nelem,
lfile number, and lfile file offset where the value is stored.  The buffer
cache (BCACHE) and FIO are then called to access the value of the parameter
in the datafile.

.NH 4
Filtered Event I/O Package (QPIO)

    The structure of the filtered event i/o package (QPIO) is illustrated in
the figure below.

.ks
.nf
                                +--------+
                                |  QPIO  |
                                +--------+
                                 /   |  \       
                      __________/    |   \__________
                     /               |              \
                +--------+      +--------+      +--------+
                |  PLIO  |      |  QPEX  |      | BCACHE |
                +--------+      +--------+      +--------+
                                     |               |
                                +--------+    +--------------+
                                | SYMTAB |    | FILE MANAGER |  
                                +--------+    +--------------+

                     Figure 2.  Structure of QPIO Routines
.fi
.ke

In the typical \fIgetevents\fR call, QPIO will call PLIO to determine the
next region of the stored image (event list) to access, then if the event
data is not already in a data buffer, FIO is called to read the data (bucket),
using the event list index, an integer array valued parameter, to determine
what bucket to read.  The events in the bucket are then examined and optionally
filtered via calls to QPEX, returning pointers to the passed events in an
output argument.  This process terminates when either the mask value changes
or at least one event has been returned and a new bucket is required to 
continue reading.