IJG JPEG LIBRARY:  SYSTEM ARCHITECTURECopyright (C) 1991-1995, Thomas G. Lane.This file is part of the Independent JPEG Group's software.For conditions of distribution and use, see the accompanying README file.This file provides an overview of the architecture of the IJG JPEG software;that is, the functions of the various modules in the system and the interfacesbetween modules.  For more precise details about any data structure or callingconvention, see the include files and comments in the source code.We assume that the reader is already somewhat familiar with the JPEG standard.The README file includes references for learning about JPEG.  The filelibjpeg.doc describes the library from the viewpoint of an applicationprogrammer using the library; it's best to read that file before this one.Also, the file coderules.doc describes the coding style conventions we use.In this document, JPEG-specific terminology follows the JPEG standard:  A "component" means a color channel, e.g., Red or Luminance.  A "sample" is a single component value (i.e., one number in the image data).  A "coefficient" is a frequency coefficient (a DCT transform output number).  A "block" is an 8x8 group of samples or coefficients.  An "MCU" (minimum coded unit) is an interleaved set of blocks of size	determined by the sampling factors, or a single block in a	noninterleaved scan.We do not use the terms "pixel" and "sample" interchangeably.  When we saypixel, we mean an element of the full-size image, while a sample is an elementof the downsampled image.  Thus the number of samples may vary acrosscomponents while the number of pixels does not.  (This terminology is not usedrigorously throughout the code, but it is used in places where confusion wouldotherwise result.)*** System features ***The IJG distribution contains two parts:  * A subroutine library for JPEG compression and decompression.  * cjpeg/djpeg, two sample applications that use the library to transform    JFIF JPEG files to and from several other image formats.cjpeg/djpeg are of no great intellectual complexity: they merely add a simplecommand-line user interface and I/O routines for several uncompressed imageformats.  This document concentrates on the library itself.We desire the library to be capable of supporting all JPEG baseline, extendedsequential, and progressive DCT processes.  Hierarchical processes are notsupported.The library does not support the lossless (spatial) JPEG process.  LosslessJPEG shares little or no code with lossy JPEG, and would normally be usedwithout the extensive pre- and post-processing provided by this library.We feel that lossless JPEG is better handled by a separate library.Within these limits, any set of compression parameters allowed by the JPEGspec should be readable for decompression.  (We can be more restrictive aboutwhat formats we can generate.)  Although the system design allows for allparameter values, some uncommon settings are not yet implemented and maynever be; nonintegral sampling ratios are the prime example.  Furthermore,we treat 8-bit vs. 12-bit data precision as a compile-time switch, not arun-time option, because most machines can store 8-bit pixels much morecompactly than 12-bit.For legal reasons, JPEG arithmetic coding is not currently supported, butextending the library to include it would be straightforward.By itself, the library handles only interchange JPEG datastreams --- inparticular the widely used JFIF file format.  The library can be used bysurrounding code to process interchange or abbreviated JPEG datastreams thatare embedded in more complex file formats.  (For example, libtiff uses thislibrary to implement JPEG compression within the TIFF file format.)The library includes a substantial amount of code that is not covered by theJPEG standard but is necessary for typical applications of JPEG.  Thesefunctions preprocess the image before JPEG compression or postprocess it afterdecompression.  They include colorspace conversion, downsampling/upsampling,and color quantization.  This code can be omitted if not needed.A wide range of quality vs. speed tradeoffs are possible in JPEG processing,and even more so in decompression postprocessing.  The decompression libraryprovides multiple implementations that cover most of the useful tradeoffs,ranging from very-high-quality down to fast-preview operation.  On thecompression side we have generally not provided low-quality choices, sincecompression is normally less time-critical.  It should be understood that thelow-quality modes may not meet the JPEG standard's accuracy requirements;nonetheless, they are useful for viewers.*** Portability issues ***Portability is an essential requirement for the library.  The key portabilityissues that show up at the level of system architecture are:1.  Memory usage.  We want the code to be able to run on PC-class machineswith limited memory.  Images should therefore be processed sequentially (instrips), to avoid holding the whole image in memory at once.  Where afull-image buffer is necessary, we should be able to use either virtual memoryor temporary files.2.  Near/far pointer distinction.  To run efficiently on 80x86 machines, thecode should distinguish "small" objects (kept in near data space) from"large" ones (kept in far data space).  This is an annoying restriction, butfortunately it does not impact code quality for less brain-damaged machines,and the source code clutter turns out to be minimal with sufficient use ofpointer typedefs.3. Data precision.  We assume that "char" is at least 8 bits, "short" and"int" at least 16, "long" at least 32.  The code will work fine with largerdata sizes, although memory may be used inefficiently in some cases.  However,the JPEG compressed datastream must ultimately appear on external storage as asequence of 8-bit bytes if it is to conform to the standard.  This may pose aproblem on machines where char is wider than 8 bits.  The library representscompressed data as an array of values of typedef JOCTET.  If no data typeexactly 8 bits wide is available, custom data source and data destinationmodules must be written to unpack and pack the chosen JOCTET datatype into8-bit external representation.*** System overview ***The compressor and decompressor are each divided into two main sections:the JPEG compressor or decompressor proper, and the preprocessing orpostprocessing functions.  The interface between these two sections is theimage data that the official JPEG spec regards as its input or output: thisdata is in the colorspace to be used for compression, and it is downsampledto the sampling factors to be used.  The preprocessing and postprocessingsteps are responsible for converting a normal image representation to or fromthis form.  (Those few applications that want to deal with YCbCr downsampleddata can skip the preprocessing or postprocessing step.)Looking more closely, the compressor library contains the following mainelements:  Preprocessing:    * Color space conversion (e.g., RGB to YCbCr).    * Edge expansion and downsampling.  Optionally, this step can do simple      smoothing --- this is often helpful for low-quality source data.  JPEG proper:    * MCU assembly, DCT, quantization.    * Entropy coding (sequential or progressive, Huffman or arithmetic).In addition to these modules we need overall control, marker generation,and support code (memory management & error handling).  There is also amodule responsible for physically writing the output data --- typicallythis is just an interface to fwrite(), but some applications may need todo something else with the data.The decompressor library contains the following main elements:  JPEG proper:    * Entropy decoding (sequential or progressive, Huffman or arithmetic).    * Dequantization, inverse DCT, MCU disassembly.  Postprocessing:    * Upsampling.  Optionally, this step may be able to do more general      rescaling of the image.    * Color space conversion (e.g., YCbCr to RGB).  This step may also      provide gamma adjustment [ currently it does not ].    * Optional color quantization (e.g., reduction to 256 colors).    * Optional color precision reduction (e.g., 24-bit to 15-bit color).      [This feature is not currently implemented.]We also need overall control, marker parsing, and a data source module.The support code (memory management & error handling) can be shared withthe compression half of the library.There may be several implementations of each of these elements, particularlyin the decompressor, where a wide range of speed/quality tradeoffs is veryuseful.  It must be understood that some of the best speedups involvemerging adjacent steps in the pipeline.  For example, upsampling, color spaceconversion, and color quantization might all be done at once when using alow-quality ordered-dither technique.  The system architecture is designed toallow such merging where appropriate.Note: it is convenient to regard edge expansion (padding to block boundaries)as a preprocessing/postprocessing function, even though the JPEG spec includesit in compression/decompression.  We do this because downsampling/upsamplingcan be simplified a little if they work on padded data: it's not necessary tohave special cases at the right and bottom edges.  Therefore the interfacebuffer is always an integral number of blocks wide and high, and we expectcompression preprocessing to pad the source data properly.  Padding will occuronly to the next block (8-sample) boundary.  In an interleaved-scan situation,additional dummy blocks may be used to fill out MCUs, but the MCU assembly anddisassembly logic will create or discard these blocks internally.  (This isadvantageous for speed reasons, since we avoid DCTing the dummy blocks.It also permits a small reduction in file size, because the compressor canchoose dummy block contents so as to minimize their size in compressed form.Finally, it makes the interface buffer specification independent of whetherthe file is actually interleaved or not.)  Applications that wish to dealdirectly with the downsampled data must provide similar buffering and paddingfor odd-sized images.*** Poor man's object-oriented programming ***It should be clear by now that we have a lot of quasi-independent processingsteps, many of which have several possible behaviors.  To avoid cluttering thecode with lots of switch statements, we use a simple form of object-styleprogramming to separate out the different possibilities.For example, two different color quantization algorithms could be implementedas two separate modules that present the same external interface; at runtime,the calling code will access the proper module indirectly through an "object".We can get the limited features we need while staying within portable C.The basic tool is a function pointer.  An "object" is just a structcontaining one or more function pointer fields, each of which corresponds toa method name in real object-oriented languages.  During initialization wefill in the function pointers with references to whichever module we havedetermined we need to use in this run.  Then invocation of the module is doneby indirecting through a function pointer; on most machines this is no moreexpensive than a switch statement, which would be the only other way ofmaking the required run-time choice.  The really significant benefit, ofcourse, is keeping the source code clean and well structured.We can also arrange to have private storage that varies between differentimplementations of the same kind of object.  We do this by making all themodule-specific object structs be separately allocated entities, which willbe accessed via pointers in the master compression or decompression struct.The "public" fields or methods for a given kind of object are specified bya commonly known struct.  But a module's initialization code can allocatea larger struct that contains the common struct as its first member, plusadditional private fields.  With appropriate pointer casting, the module'sinternal functions can access these private fields.  (For a simple example,see jdatadst.c, which implements the external interface specified by structjpeg_destination_mgr, but adds extra fields.)(Of course this would all be a lot easier if we were using C++, but we arenot yet prepared to assume that everyone has a C++ compiler.)An important benefit of this scheme is that it is easy to provide multipleversions of any method, each tuned to a particular case.  While a lot ofprecalculation might be done to select an optimal implementation of a method,the cost per invocation is constant.  For example, the upsampling step mighthave a "generic" method, plus one or more "hardwired" methods for the mostpopular sampling factors; the hardwired methods would be faster because they'duse straight-line code instead of for-loops.  The cost to determine whichmethod to use is paid only once, at startup, and the selection criteria arehidden from the callers of the method.