structure.doc

game engine, which is useful for everyone who is interested in it. I hope you can enjoy it.

In a successive-approximation AC refinement scan, the progressive Huffman
decoder has to be able to undo assignments of newly nonzero coefficients if it
suspends before the MCU is complete, since decoding requires distinguishing
previously-zero and previously-nonzero coefficients.  This is a bit tedious
but probably won't have much effect on performance.  Other variants of Huffman
decoding need not worry about this, since they will just store the same values
again if forced to repeat the MCU.

This approach would probably not work for an arithmetic codec, since its
modifiable state is quite large and couldn't be copied cheaply.  Instead it
would have to suspend and resume exactly at the point of the buffer end.

The JPEG marker reader is designed to cope with suspension at an arbitrary
point.  It does so by backing up to the start of the marker parameter segment,
so the data buffer must be big enough to hold the largest marker of interest.
Again, a couple KB should be adequate.  (A special "skip" convention is used
to bypass COM and APPn markers, so these can be larger than the buffer size
without causing problems; otherwise a 64K buffer would be needed in the worst
case.)

The JPEG marker writer currently does *not* cope with suspension.  I feel that
this is not necessary; it is much easier simply to require the application to
ensure there is enough buffer space before starting.  (An empty 2K buffer is
more than sufficient for the header markers; and ensuring there are a dozen or
two bytes available before calling jpeg_finish_compress() will suffice for the
trailer.)  This would not work for writing multi-scan JPEG files, but
we simply do not intend to support that capability with suspension.


*** Memory manager services ***

The JPEG library's memory manager controls allocation and deallocation of
memory, and it manages large "virtual" data arrays on machines where the
operating system does not provide virtual memory.  Note that the same
memory manager serves both compression and decompression operations.

In all cases, allocated objects are tied to a particular compression or
decompression master record, and they will be released when that master
record is destroyed.

The memory manager does not provide explicit deallocation of objects.
Instead, objects are created in "pools" of free storage, and a whole pool
can be freed at once.  This approach helps prevent storage-leak bugs, and
it speeds up operations whenever malloc/free are slow (as they often are).
The pools can be regarded as lifetime identifiers for objects.  Two
pools/lifetimes are defined:
  * JPOOL_PERMANENT	lasts until master record is destroyed
  * JPOOL_IMAGE		lasts until done with image (JPEG datastream)
Permanent lifetime is used for parameters and tables that should be carried
across from one datastream to another; this includes all application-visible
parameters.  Image lifetime is used for everything else.  (A third lifetime,
JPOOL_PASS = one processing pass, was originally planned.  However it was
dropped as not being worthwhile.  The actual usage patterns are such that the
peak memory usage would be about the same anyway; and having per-pass storage
substantially complicates the virtual memory allocation rules --- see below.)

The memory manager deals with three kinds of object:
1. "Small" objects.  Typically these require no more than 10K-20K total.
2. "Large" objects.  These may require tens to hundreds of K depending on
   image size.  Semantically they behave the same as small objects, but we
   distinguish them for two reasons:
     * On MS-DOS machines, large objects are referenced by FAR pointers,
       small objects by NEAR pointers.
     * Pool allocation heuristics may differ for large and small objects.
   Note that individual "large" objects cannot exceed the size allowed by
   type size_t, which may be 64K or less on some machines.
3. "Virtual" objects.  These are large 2-D arrays of JSAMPLEs or JBLOCKs
   (typically large enough for the entire image being processed).  The
   memory manager provides stripwise access to these arrays.  On machines
   without virtual memory, the rest of the array may be swapped out to a
   temporary file.

(Note: JSAMPARRAY and JBLOCKARRAY data structures are a combination of large
objects for the data proper and small objects for the row pointers.  For
convenience and speed, the memory manager provides single routines to create
these structures.  Similarly, virtual arrays include a small control block
and a JSAMPARRAY or JBLOCKARRAY working buffer, all created with one call.)

In the present implementation, virtual arrays are only permitted to have image
lifespan.  (Permanent lifespan would not be reasonable, and pass lifespan is
not very useful since a virtual array's raison d'etre is to store data for
multiple passes through the image.)  We also expect that only "small" objects
will be given permanent lifespan, though this restriction is not required by
the memory manager.

In a non-virtual-memory machine, some performance benefit can be gained by
making the in-memory buffers for virtual arrays be as large as possible.
(For small images, the buffers might fit entirely in memory, so blind
swapping would be very wasteful.)  The memory manager will adjust the height
of the buffers to fit within a prespecified maximum memory usage.  In order
to do this in a reasonably optimal fashion, the manager needs to allocate all
of the virtual arrays at once.  Therefore, there isn't a one-step allocation
routine for virtual arrays; instead, there is a "request" routine that simply
allocates the control block, and a "realize" routine (called just once) that
determines space allocation and creates all of the actual buffers.  The
realize routine must allow for space occupied by non-virtual large objects.
(We don't bother to factor in the space needed for small objects, on the
grounds that it isn't worth the trouble.)

To support all this, we establish the following protocol for doing business
with the memory manager:
  1. Modules must request virtual arrays (which may have only image lifespan)
     during the initial setup phase, i.e., in their jinit_xxx routines.
  2. All "large" objects (including JSAMPARRAYs and JBLOCKARRAYs) must also be
     allocated during initial setup.
  3. realize_virt_arrays will be called at the completion of initial setup.
     The above conventions ensure that sufficient information is available
     for it to choose a good size for virtual array buffers.
Small objects of any lifespan may be allocated at any time.  We expect that
the total space used for small objects will be small enough to be negligible
in the realize_virt_arrays computation.

In a virtual-memory machine, we simply pretend that the available space is
infinite, thus causing realize_virt_arrays to decide that it can allocate all
the virtual arrays as full-size in-memory buffers.  The overhead of the
virtual-array access protocol is very small when no swapping occurs.

A virtual array can be specified to be "pre-zeroed"; when this flag is set,
never-yet-written sections of the array are set to zero before being made
available to the caller.  If this flag is not set, never-written sections
of the array contain garbage.  (This feature exists primarily because the
equivalent logic would otherwise be needed in jdcoefct.c for progressive
JPEG mode; we may as well make it available for possible other uses.)

The first write pass on a virtual array is required to occur in top-to-bottom
order; read passes, as well as any write passes after the first one, may
access the array in any order.  This restriction exists partly to simplify
the virtual array control logic, and partly because some file systems may not
support seeking beyond the current end-of-file in a temporary file.  The main
implication of this restriction is that rearrangement of rows (such as
converting top-to-bottom data order to bottom-to-top) must be handled while
reading data out of the virtual array, not while putting it in.


*** Memory manager internal structure ***

To isolate system dependencies as much as possible, we have broken the
memory manager into two parts.  There is a reasonably system-independent
"front end" (jmemmgr.c) and a "back end" that contains only the code
likely to change across systems.  All of the memory management methods
outlined above are implemented by the front end.  The back end provides
the following routines for use by the front end (none of these routines
are known to the rest of the JPEG code):

jpeg_mem_init, jpeg_mem_term	system-dependent initialization/shutdown

jpeg_get_small, jpeg_free_small	interface to malloc and free library routines
				(or their equivalents)

jpeg_get_large, jpeg_free_large	interface to FAR malloc/free in MSDOS machines;
				else usually the same as
				jpeg_get_small/jpeg_free_small

jpeg_mem_available		estimate available memory

jpeg_open_backing_store		create a backing-store object

read_backing_store,		manipulate a backing-store object
write_backing_store,
close_backing_store

On some systems there will be more than one type of backing-store object
(specifically, in MS-DOS a backing store file might be an area of extended
memory as well as a disk file).  jpeg_open_backing_store is responsible for
choosing how to implement a given object.  The read/write/close routines
are method pointers in the structure that describes a given object; this
lets them be different for different object types.

It may be necessary to ensure that backing store objects are explicitly
released upon abnormal program termination.  For example, MS-DOS won't free
extended memory by itself.  To support this, we will expect the main program
or surrounding application to arrange to call self_destruct (typically via
jpeg_destroy) upon abnormal termination.  This may require a SIGINT signal
handler or equivalent.  We don't want to have the back end module install its
own signal handler, because that would pre-empt the surrounding application's
ability to control signal handling.

The IJG distribution includes several memory manager back end implementations.
Usually the same back end should be suitable for all applications on a given
system, but it is possible for an application to supply its own back end at
need.


*** Implications of DNL marker ***

Some JPEG files may use a DNL marker to postpone definition of the image
height (this would be useful for a fax-like scanner's output, for instance).
In these files the SOF marker claims the image height is 0, and you only
find out the true image height at the end of the first scan.

We could read these files as follows:
1. Upon seeing zero image height, replace it by 65535 (the maximum allowed).
2. When the DNL is found, update the image height in the global image
   descriptor.
This implies that control modules must avoid making copies of the image
height, and must re-test for termination after each MCU row.  This would
be easy enough to do.

In cases where image-size data structures are allocated, this approach will
result in very inefficient use of virtual memory or much-larger-than-necessary
temporary files.  This seems acceptable for something that probably won't be a
mainstream usage.  People might have to forgo use of memory-hogging options
(such as two-pass color quantization or noninterleaved JPEG files) if they
want efficient conversion of such files.  (One could improve efficiency by
demanding a user-supplied upper bound for the height, less than 65536; in most
cases it could be much less.)

The standard also permits the SOF marker to overestimate the image height,
with a DNL to give the true, smaller height at the end of the first scan.
This would solve the space problems if the overestimate wasn't too great.
However, it implies that you don't even know whether DNL will be used.

This leads to a couple of very serious objections:
1. Testing for a DNL marker must occur in the inner loop of the decompressor's
   Huffman decoder; this implies a speed penalty whether the feature is used
   or not.
2. There is no way to hide the last-minute change in image height from an
   application using the decoder.  Thus *every* application using the IJG
   library would suffer a complexity penalty whether it cared about DNL or
   not.
We currently do not support DNL because of these problems.

A different approach is to insist that DNL-using files be preprocessed by a
separate program that reads ahead to the DNL, then goes back and fixes the SOF
marker.  This is a much simpler solution and is probably far more efficient.
Even if one wants piped input, buffering the first scan of the JPEG file needs
a lot smaller temp file than is implied by the maximum-height method.  For
this approach we'd simply treat DNL as a no-op in the decompressor (at most,
check that it matches the SOF image height).

We will not worry about making the compressor capable of outputting DNL.
Something similar to the first scheme above could be applied if anyone ever
wants to make that work.