structure.doc

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

* Colorspace conversion: convert from JPEG color space to output color space,
  and change data layout from separate component planes to pixel-interleaved.
  Works on one pixel row at a time.

* Color quantization: reduce the data to colormapped form, using either an
  externally specified colormap or an internally generated one.  This module
  is not used for full-color output.  Works on one pixel row at a time; may
  require two passes to generate a color map.  Note that the output will
  always be a single component representing colormap indexes.  In the current
  design, the output values are JSAMPLEs, so an 8-bit compilation cannot
  quantize to more than 256 colors.  This is unlikely to be a problem in
  practice.

* Color reduction: this module handles color precision reduction, e.g.,
  generating 15-bit color (5 bits/primary) from JPEG's 24-bit output.
  Not quite clear yet how this should be handled... should we merge it with
  colorspace conversion???

Note that some high-speed operating modes might condense the entire
postprocessing sequence to a single module (upsample, color convert, and
quantize in one step).

In addition to the above objects, the decompression library includes these
objects:

* Master control: determines the number of passes required, controls overall
  and per-pass initialization of the other modules.  This is subdivided into
  input and output control: jdinput.c controls only input-side processing,
  while jdmaster.c handles overall initialization and output-side control.

* Marker reading: decodes JPEG markers (except for RSTn).

* Data source manager: supplies the input JPEG datastream.  The source
  manager supplied with the library knows how to read from a stdio stream;
  for other behaviors, the surrounding application may provide its own source
  manager.

* Memory manager: same as for compression library.

* Error handler: same as for compression library.

* Progress monitor: same as for compression library.

As with compression, the data source manager, error handler, and progress
monitor are candidates for replacement by a surrounding application.


*** Decompression input and output separation ***

To support efficient incremental display of progressive JPEG files, the
decompressor is divided into two sections that can run independently:

1. Data input includes marker parsing, entropy decoding, and input into the
   coefficient controller's DCT coefficient buffer.  Note that this
   processing is relatively cheap and fast.

2. Data output reads from the DCT coefficient buffer and performs the IDCT
   and all postprocessing steps.

For a progressive JPEG file, the data input processing is allowed to get
arbitrarily far ahead of the data output processing.  (This occurs only
if the application calls jpeg_consume_input(); otherwise input and output
run in lockstep, since the input section is called only when the output
section needs more data.)  In this way the application can avoid making
extra display passes when data is arriving faster than the display pass
can run.  Furthermore, it is possible to abort an output pass without
losing anything, since the coefficient buffer is read-only as far as the
output section is concerned.  See libjpeg.doc for more detail.

A full-image coefficient array is only created if the JPEG file has multiple
scans (or if the application specifies buffered-image mode anyway).  When
reading a single-scan file, the coefficient controller normally creates only
a one-MCU buffer, so input and output processing must run in lockstep in this
case.  jpeg_consume_input() is effectively a no-op in this situation.

The main impact of dividing the decompressor in this fashion is that we must
be very careful with shared variables in the cinfo data structure.  Each
variable that can change during the course of decompression must be
classified as belonging to data input or data output, and each section must
look only at its own variables.  For example, the data output section may not
depend on any of the variables that describe the current scan in the JPEG
file, because these may change as the data input section advances into a new
scan.

The progress monitor is (somewhat arbitrarily) defined to treat input of the
file as one pass when buffered-image mode is not used, and to ignore data
input work completely when buffered-image mode is used.  Note that the
library has no reliable way to predict the number of passes when dealing
with a progressive JPEG file, nor can it predict the number of output passes
in buffered-image mode.  So the work estimate is inherently bogus anyway.

No comparable division is currently made in the compression library, because
there isn't any real need for it.


*** Data formats ***

Arrays of pixel sample values use the following data structure:

    typedef something JSAMPLE;		a pixel component value, 0..MAXJSAMPLE
    typedef JSAMPLE *JSAMPROW;		ptr to a row of samples
    typedef JSAMPROW *JSAMPARRAY;	ptr to a list of rows
    typedef JSAMPARRAY *JSAMPIMAGE;	ptr to a list of color-component arrays

The basic element type JSAMPLE will typically be one of unsigned char,
(signed) char, or short.  Short will be used if samples wider than 8 bits are
to be supported (this is a compile-time option).  Otherwise, unsigned char is
used if possible.  If the compiler only supports signed chars, then it is
necessary to mask off the value when reading.  Thus, all reads of JSAMPLE
values must be coded as "GETJSAMPLE(value)", where the macro will be defined
as "((value) & 0xFF)" on signed-char machines and "((int) (value))" elsewhere.

With these conventions, JSAMPLE values can be assumed to be >= 0.  This helps
simplify correct rounding during downsampling, etc.  The JPEG standard's
specification that sample values run from -128..127 is accommodated by
subtracting 128 just as the sample value is copied into the source array for
the DCT step (this will be an array of signed ints).  Similarly, during
decompression the output of the IDCT step will be immediately shifted back to
0..255.  (NB: different values are required when 12-bit samples are in use.
The code is written in terms of MAXJSAMPLE and CENTERJSAMPLE, which will be
defined as 255 and 128 respectively in an 8-bit implementation, and as 4095
and 2048 in a 12-bit implementation.)

We use a pointer per row, rather than a two-dimensional JSAMPLE array.  This
choice costs only a small amount of memory and has several benefits:
* Code using the data structure doesn't need to know the allocated width of
  the rows.  This simplifies edge expansion/compression, since we can work
  in an array that's wider than the logical picture width.
* Indexing doesn't require multiplication; this is a performance win on many
  machines.
* Arrays with more than 64K total elements can be supported even on machines
  where malloc() cannot allocate chunks larger than 64K.
* The rows forming a component array may be allocated at different times
  without extra copying.  This trick allows some speedups in smoothing steps
  that need access to the previous and next rows.

Note that each color component is stored in a separate array; we don't use the
traditional layout in which the components of a pixel are stored together.
This simplifies coding of modules that work on each component independently,
because they don't need to know how many components there are.  Furthermore,
we can read or write each component to a temporary file independently, which
is helpful when dealing with noninterleaved JPEG files.

In general, a specific sample value is accessed by code such as
	GETJSAMPLE(image[colorcomponent][row][col])
where col is measured from the image left edge, but row is measured from the
first sample row currently in memory.  Either of the first two indexings can
be precomputed by copying the relevant pointer.


Since most image-processing applications prefer to work on images in which
the components of a pixel are stored together, the data passed to or from the
surrounding application uses the traditional convention: a single pixel is
represented by N consecutive JSAMPLE values, and an image row is an array of
(# of color components)*(image width) JSAMPLEs.  One or more rows of data can
be represented by a pointer of type JSAMPARRAY in this scheme.  This scheme is
converted to component-wise storage inside the JPEG library.  (Applications
that want to skip JPEG preprocessing or postprocessing will have to contend
with component-wise storage.)


Arrays of DCT-coefficient values use the following data structure:

    typedef short JCOEF;		a 16-bit signed integer
    typedef JCOEF JBLOCK[DCTSIZE2];	an 8x8 block of coefficients
    typedef JBLOCK *JBLOCKROW;		ptr to one horizontal row of 8x8 blocks
    typedef JBLOCKROW *JBLOCKARRAY;	ptr to a list of such rows
    typedef JBLOCKARRAY *JBLOCKIMAGE;	ptr to a list of color component arrays

The underlying type is at least a 16-bit signed integer; while "short" is big
enough on all machines of interest, on some machines it is preferable to use
"int" for speed reasons, despite the storage cost.  Coefficients are grouped
into 8x8 blocks (but we always use #defines DCTSIZE and DCTSIZE2 rather than
"8" and "64").

The contents of a coefficient block may be in either "natural" or zigzagged
order, and may be true values or divided by the quantization coefficients,
depending on where the block is in the processing pipeline.  In the current
library, coefficient blocks are kept in natural order everywhere; the entropy
codecs zigzag or dezigzag the data as it is written or read.  The blocks
contain quantized coefficients everywhere outside the DCT/IDCT subsystems.
(This latter decision may need to be revisited to support variable
quantization a la JPEG Part 3.)

Notice that the allocation unit is now a row of 8x8 blocks, corresponding to
eight rows of samples.  Otherwise the structure is much the same as for
samples, and for the same reasons.

On machines where malloc() can't handle a request bigger than 64Kb, this data
structure limits us to rows of less than 512 JBLOCKs, or a picture width of
4000+ pixels.  This seems an acceptable restriction.


On 80x86 machines, the bottom-level pointer types (JSAMPROW and JBLOCKROW)
must be declared as "far" pointers, but the upper levels can be "near"
(implying that the pointer lists are allocated in the DS segment).
We use a #define symbol FAR, which expands to the "far" keyword when
compiling on 80x86 machines and to nothing elsewhere.


*** Suspendable processing ***

In some applications it is desirable to use the JPEG library as an
incremental, memory-to-memory filter.  In this situation the data source or
destination may be a limited-size buffer, and we can't rely on being able to
empty or refill the buffer at arbitrary times.  Instead the application would
like to have control return from the library at buffer overflow/underrun, and
then resume compression or decompression at a later time.

This scenario is supported for simple cases.  (For anything more complex, we
recommend that the application "bite the bullet" and develop real multitasking
capability.)  The libjpeg.doc file goes into more detail about the usage and
limitations of this capability; here we address the implications for library
structure.

The essence of the problem is that the entropy codec (coder or decoder) must
be prepared to stop at arbitrary times.  In turn, the controllers that call
the entropy codec must be able to stop before having produced or consumed all
the data that they normally would handle in one call.  That part is reasonably
straightforward: we make the controller call interfaces include "progress
counters" which indicate the number of data chunks successfully processed, and
we require callers to test the counter rather than just assume all of the data
was processed.

Rather than trying to restart at an arbitrary point, the current Huffman
codecs are designed to restart at the beginning of the current MCU after a
suspension due to buffer overflow/underrun.  At the start of each call, the
codec's internal state is loaded from permanent storage (in the JPEG object
structures) into local variables.  On successful completion of the MCU, the
permanent state is updated.  (This copying is not very expensive, and may even
lead to *improved* performance if the local variables can be registerized.)
If a suspension occurs, the codec simply returns without updating the state,
thus effectively reverting to the start of the MCU.  Note that this implies
leaving some data unprocessed in the source/destination buffer (ie, the
compressed partial MCU).  The data source/destination module interfaces are
specified so as to make this possible.  This also implies that the data buffer
must be large enough to hold a worst-case compressed MCU; a couple thousand
bytes should be enough.