IJG JPEG LIBRARY: SYSTEM ARCHITECTURE Copyright (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. This plan differs a little bit from usual object-oriented structures, in thatonly one instance of each object class will exist during execution. Thereason for having the class structure is that on different runs we may createdifferent instances (choose to execute different modules). You can think ofthe term "method" as denoting the common interface presented by a particularset of interchangeable functions, and "object" as denoting a group of relatedmethods, or the total shared interface behavior of a group of modules. *** Overall control structure *** We previously mentioned the need for overall control logic in the compressionand decompression libraries. In IJG implementations prior to v5, overallcontrol was mostly provided by "pipeline control" modules, which proved to belarge, unwieldy, and hard to understand. To improve the situation, thecontrol logic has been subdivided into multiple modules. The control modulesconsist of: 1. Master control for module selection and initialization. This has tworesponsibilities: 1A. Startup initialization at the beginning of image processing. The individual processing modules to be used in this run are selected and given initialization calls. 1B. Per-pass control. This determines how many passes will be performed and calls each active processing module to configure itself appropriately at the beginning of each pass. End-of-pass processing, where necessary, is also invoked from the master control module. Method selection is partially distributed, in that a particular processing module may contain several possible implementations of a particular method, which it will select among when given its initialization call. The master control code need only be concerned with decisions that affect more than one module. 2. Data buffering control. A separate control module exists for each inter-processing-step data buffer. This module is responsible for invoking the processing steps that write or read that data buffer. Each buffer controller sees the world as follows: input data => processing step A => buffer => processing step B => output data | | | ------------------ controller ------------------ The controller knows the dataflow requirements of steps A and B: how much datathey want to accept in one chunk and how much they output in one chunk. Itsfunction is to manage its buffer and call A and B at the proper times. A data buffer control module may itself be viewed as a processing step by ahigher-level control module; thus the control modules form a binary tree withelementary processing steps at the leaves of the tree. The control modules are objects. A considerable amount of flexibility canbe had by replacing implementations of a control module. For example:* Merging of adjacent steps in the pipeline is done by replacing a control module and its pair of processing-step modules with a single processing- step module. (Hence the possible merges are determined by the tree of control modules.)* In some processing modes, a given interstep buffer need only be a "strip" buffer large enough to accommodate the desired data chunk sizes. In other modes, a full-image buffer is needed and several passes are required. The control module determines which kind of buffer is used and manipulates virtual array buffers as needed. One or both processing steps may be unaware of the multi-pass behavior. In theory, we might be able to make all of the data buffer controllersinterchangeable and provide just one set of implementations for all. Inpractice, each one contains considerable special-case processing for itsparticular job. The buffer controller concept should be regarded as anoverall system structuring principle, not as a complete description of thetask performed by any one controller. *** Compression object structure *** Here is a sketch of the logical structure of the JPEG compression library: |-- Colorspace conversion |-- Preprocessing controller --| | |-- DownsamplingMain controller --| | |-- Forward DCT, quantize |-- Coefficient controller --| |-- Entropy encoding This sketch also describes the flow of control (subroutine calls) duringtypical image data processing. Each of the components shown in the diagram isan "object" which may have several different implementations available. Oneor more source code files contain the actual implementation(s) of each object. The objects shown above are: * Main controller: buffer controller for the subsampled-data buffer, which holds the preprocessed input data. This controller invokes preprocessing to fill the subsampled-data buffer, and JPEG compression to empty it. There is usually no need for a full-image buffer here; a strip buffer is adequate. * Preprocessing controller: buffer controller for the downsampling input data buffer, which lies between colorspace conversion and downsampling. Note that a unified conversion/downsampling module would probably replace this controller entirely. * Colorspace conversion: converts application image data into the desired JPEG color space; also changes the data from pixel-interleaved layout to separate component planes. Processes one pixel row at a time. * Downsampling: performs reduction of chroma components as required. Optionally may perform pixel-level smoothing as well. Processes a "row group" at a time, where a row group is defined as Vmax pixel rows of each component before downsampling, and Vk sample rows afterwards (remember Vk differs across components). Some downsampling or smoothing algorithms may require context rows above and below the current row group; the preprocessing controller is responsible for supplying these rows via proper buffering. The downsampler is responsible for edge expansion at the right edge (i.e., extending each sample row to a multiple of 8 samples); but the preprocessing controller is responsible for vertical edge expansion (i.e., duplicating the bottom sample row as needed to make a multiple of 8 rows). * Coefficient controller: buffer controller for the DCT-coefficient data. This controller handles MCU assembly, including insertion of dummy DCT blocks when needed at the right or bottom edge. When performing Huffman-code optimization or emitting a multiscan JPEG file, this controller is responsible for buffering the full image. The equivalent of one fully interleaved MCU row of subsampled data is processed per call, even when the JPEG file is noninterleaved. * Forward DCT and quantization: Perform DCT, quantize, and emit coefficients. Works on one or more DCT blocks at a time. (Note: the coefficients are now emitted in normal array order, which the entropy encoder is expected to convert to zigzag order as necessary. Prior versions of the IJG code did the conversion to zigzag order within the quantization step.) * Entropy encoding: Perform Huffman or arithmetic entropy coding and emit the coded data to the data destination module. Works on one MCU per call. For progressive JPEG, the same DCT blocks are fed to the entropy coder during each pass, and the coder must emit the appropriate subset of coefficients. In addition to the above objects, the compression library includes theseobjects: * Master control: determines the number of passes required, controls overall and per-pass initialization of the other modules. * Marker writing: generates JPEG markers (except for RSTn, which is emitted by the entropy encoder when needed). * Data destination manager: writes the output JPEG datastream to its final destination (e.g., a file). The destination manager supplied with the library knows how to write to a stdio stream; for other behaviors, the surrounding application may provide its own destination manager. * Memory manager: allocates and releases memory, controls virtual arrays (with backing store management, where required). * Error handler: performs formatting and output of error and trace messages; determines handling of nonfatal errors. The surrounding application may override some or all of this object's methods to change error handling. * Progress monitor: supports output of "percent-done" progress reports. This object represents an optional callback to the surrounding application: if wanted, it must be supplied by the application. The error handler, destination manager, and progress monitor objects aredefined as separate objects in order to simplify application-specificcustomization of the JPEG library. A surrounding application may overrideindividual methods or supply its own all-new implementation of one of theseobjects. The object interfaces for these objects are therefore treated aspart of the application interface of the library, whereas the other objectsare internal to the library. The error handler and memory manager are shared by JPEG compression anddecompression; the progress monitor, if used, may be shared as well. *** Decompression object structure *** Here is a sketch of the logical structure of the JPEG decompression library: |-- Entropy decoding |-- Coefficient controller --| | |-- Dequantize, Inverse DCTMain controller --| | |-- Upsampling |-- Postprocessing controller --| |-- Colorspace conversion |-- Color quantization |-- Color precision reduction As before, this diagram also represents typical control flow. The objectsshown are: * Main controller: buffer controller for the subsampled-data buffer, which holds the output of JPEG decompression proper. This controller's primary task is to feed the postprocessing procedure. Some upsampling algorithms may require context rows above and below the current row group; when this is true, the main controller is responsible for managing its buffer so as to make context rows available. In the current design, the main buffer is always a strip buffer; a full-image buffer is never required. * Coefficient controller: buffer controller for the DCT-coefficient data. This controller handles MCU disassembly, including deletion of any dummy DCT blocks at the right or bottom edge. When reading a multiscan JPEG file, this controller is responsible for buffering the full image. (Buffering DCT coefficients, rather than samples, is necessary to support progressive JPEG.) The equivalent of one fully interleaved MCU row of subsampled data is processed per call, even when the source JPEG file is noninterleaved. * Entropy decoding: Read coded data from the data source module and perform Huffman or arithmetic entropy decoding. Works on one MCU per call. For progressive JPEG decoding, the coefficient controller supplies the prior coefficients of each MCU (initially all zeroes), which the entropy decoder modifies in each scan. * Dequantization and inverse DCT: like it says. Note that the coefficients buffered by the coefficient controller have NOT been dequantized; we merge dequantization and inverse DCT into a single step for speed reasons. When scaled-down output is asked for, simplified DCT algorithms may be used that emit only 1x1, 2x2, or 4x4 samples per DCT block, not the full 8x8. Works on one DCT block at a time. * Postprocessing controller: buffer controller for the color quantization input buffer, when quantization is in use. (Without quantization, this controller just calls the upsampler.) For two-pass quantization, this controller is responsible for buffering the full-image data. * Upsampling: restores chroma components to full size. (May support more general output rescaling, too. Note that if undersized DCT outputs have been emitted by the DCT module, this module must adjust so that properly sized outputs are created.) Works on one row group at a time. This module also calls the color conversion module, so its top level is effectively a buffer controller for the upsampling->color conversion buffer. However, in all but the highest-quality operating modes, upsampling and color conversion are likely to be merged into a single step. * 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 entirepostprocessing sequence to a single module (upsample, color convert, andquantize in one step). In addition to the above objects, the decompression library includes theseobjects:Lines 1–500 of 948. Load more
IJG JPEG LIBRARY: SYSTEM ARCHITECTURE Copyright (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 interfaces between modules. For more precise details about any data structure or calling convention, 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 file libjpeg.doc describes the library from the viewpoint of an application programmer 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 say pixel, we mean an element of the full-size image, while a sample is an element of the downsampled image. Thus the number of samples may vary across components while the number of pixels does not. (This terminology is not used rigorously throughout the code, but it is used in places where confusion would otherwise 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 simple command-line user interface and I/O routines for several uncompressed image formats. This document concentrates on the library itself. We desire the library to be capable of supporting all JPEG baseline, extended sequential, and progressive DCT processes. Hierarchical processes are not supported. The library does not support the lossless (spatial) JPEG process. Lossless JPEG shares little or no code with lossy JPEG, and would normally be used without 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 JPEG spec should be readable for decompression. (We can be more restrictive about what formats we can generate.) Although the system design allows for all parameter values, some uncommon settings are not yet implemented and may never be; nonintegral sampling ratios are the prime example. Furthermore, we treat 8-bit vs. 12-bit data precision as a compile-time switch, not a run-time option, because most machines can store 8-bit pixels much more compactly than 12-bit. For legal reasons, JPEG arithmetic coding is not currently supported, but extending the library to include it would be straightforward. By itself, the library handles only interchange JPEG datastreams --- in particular the widely used JFIF file format. The library can be used by surrounding code to process interchange or abbreviated JPEG datastreams that are embedded in more complex file formats. (For example, libtiff uses this library to implement JPEG compression within the TIFF file format.) The library includes a substantial amount of code that is not covered by the JPEG standard but is necessary for typical applications of JPEG. These functions preprocess the image before JPEG compression or postprocess it after decompression. 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 library provides multiple implementations that cover most of the useful tradeoffs, ranging from very-high-quality down to fast-preview operation. On the compression side we have generally not provided low-quality choices, since compression is normally less time-critical. It should be understood that the low-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 portability issues 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 machines with limited memory. Images should therefore be processed sequentially (in strips), to avoid holding the whole image in memory at once. Where a full-image buffer is necessary, we should be able to use either virtual memory or temporary files. 2. Near/far pointer distinction. To run efficiently on 80x86 machines, the code should distinguish "small" objects (kept in near data space) from "large" ones (kept in far data space). This is an annoying restriction, but fortunately it does not impact code quality for less brain-damaged machines, and the source code clutter turns out to be minimal with sufficient use of pointer 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 larger data sizes, although memory may be used inefficiently in some cases. However, the JPEG compressed datastream must ultimately appear on external storage as a sequence of 8-bit bytes if it is to conform to the standard. This may pose a problem on machines where char is wider than 8 bits. The library represents compressed data as an array of values of typedef JOCTET. If no data type exactly 8 bits wide is available, custom data source and data destination modules must be written to unpack and pack the chosen JOCTET datatype into 8-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 or postprocessing functions. The interface between these two sections is the image data that the official JPEG spec regards as its input or output: this data is in the colorspace to be used for compression, and it is downsampled to the sampling factors to be used. The preprocessing and postprocessing steps are responsible for converting a normal image representation to or from this form. (Those few applications that want to deal with YCbCr downsampled data can skip the preprocessing or postprocessing step.) Looking more closely, the compressor library contains the following main elements: 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 a module responsible for physically writing the output data --- typically this is just an interface to fwrite(), but some applications may need to do 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 with the compression half of the library. There may be several implementations of each of these elements, particularly in the decompressor, where a wide range of speed/quality tradeoffs is very useful. It must be understood that some of the best speedups involve merging adjacent steps in the pipeline. For example, upsampling, color space conversion, and color quantization might all be done at once when using a low-quality ordered-dither technique. The system architecture is designed to allow 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 includes it in compression/decompression. We do this because downsampling/upsampling can be simplified a little if they work on padded data: it's not necessary to have special cases at the right and bottom edges. Therefore the interface buffer is always an integral number of blocks wide and high, and we expect compression preprocessing to pad the source data properly. Padding will occur only 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 and disassembly logic will create or discard these blocks internally. (This is advantageous for speed reasons, since we avoid DCTing the dummy blocks. It also permits a small reduction in file size, because the compressor can choose dummy block contents so as to minimize their size in compressed form. Finally, it makes the interface buffer specification independent of whether the file is actually interleaved or not.) Applications that wish to deal directly with the downsampled data must provide similar buffering and padding for odd-sized images. *** Poor man's object-oriented programming *** It should be clear by now that we have a lot of quasi-independent processing steps, many of which have several possible behaviors. To avoid cluttering the code with lots of switch statements, we use a simple form of object-style programming to separate out the different possibilities. For example, two different color quantization algorithms could be implemented as 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 struct containing one or more function pointer fields, each of which corresponds to a method name in real object-oriented languages. During initialization we fill in the function pointers with references to whichever module we have determined we need to use in this run. Then invocation of the module is done by indirecting through a function pointer; on most machines this is no more expensive than a switch statement, which would be the only other way of making the required run-time choice. The really significant benefit, of course, is keeping the source code clean and well structured. We can also arrange to have private storage that varies between different implementations of the same kind of object. We do this by making all the module-specific object structs be separately allocated entities, which will be accessed via pointers in the master compression or decompression struct. The "public" fields or methods for a given kind of object are specified by a commonly known struct. But a module's initialization code can allocate a larger struct that contains the common struct as its first member, plus additional private fields. With appropriate pointer casting, the module's internal functions can access these private fields. (For a simple example, see jdatadst.c, which implements the external interface specified by struct jpeg_destination_mgr, but adds extra fields.) (Of course this would all be a lot easier if we were using C++, but we are not yet prepared to assume that everyone has a C++ compiler.) An important benefit of this scheme is that it is easy to provide multiple versions of any method, each tuned to a particular case. While a lot of precalculation might be done to select an optimal implementation of a method, the cost per invocation is constant. For example, the upsampling step might have a "generic" method, plus one or more "hardwired" methods for the most popular sampling factors; the hardwired methods would be faster because they'd use straight-line code instead of for-loops. The cost to determine which method to use is paid only once, at startup, and the selection criteria are hidden from the callers of the method. This plan differs a little bit from usual object-oriented structures, in that only one instance of each object class will exist during execution. The reason for having the class structure is that on different runs we may create different instances (choose to execute different modules). You can think of the term "method" as denoting the common interface presented by a particular set of interchangeable functions, and "object" as denoting a group of related methods, or the total shared interface behavior of a group of modules. *** Overall control structure *** We previously mentioned the need for overall control logic in the compression and decompression libraries. In IJG implementations prior to v5, overall control was mostly provided by "pipeline control" modules, which proved to be large, unwieldy, and hard to understand. To improve the situation, the control logic has been subdivided into multiple modules. The control modules consist of: 1. Master control for module selection and initialization. This has two responsibilities: 1A. Startup initialization at the beginning of image processing. The individual processing modules to be used in this run are selected and given initialization calls. 1B. Per-pass control. This determines how many passes will be performed and calls each active processing module to configure itself appropriately at the beginning of each pass. End-of-pass processing, where necessary, is also invoked from the master control module. Method selection is partially distributed, in that a particular processing module may contain several possible implementations of a particular method, which it will select among when given its initialization call. The master control code need only be concerned with decisions that affect more than one module. 2. Data buffering control. A separate control module exists for each inter-processing-step data buffer. This module is responsible for invoking the processing steps that write or read that data buffer. Each buffer controller sees the world as follows: input data => processing step A => buffer => processing step B => output data | | | ------------------ controller ------------------ The controller knows the dataflow requirements of steps A and B: how much data they want to accept in one chunk and how much they output in one chunk. Its function is to manage its buffer and call A and B at the proper times. A data buffer control module may itself be viewed as a processing step by a higher-level control module; thus the control modules form a binary tree with elementary processing steps at the leaves of the tree. The control modules are objects. A considerable amount of flexibility can be had by replacing implementations of a control module. For example: * Merging of adjacent steps in the pipeline is done by replacing a control module and its pair of processing-step modules with a single processing- step module. (Hence the possible merges are determined by the tree of control modules.) * In some processing modes, a given interstep buffer need only be a "strip" buffer large enough to accommodate the desired data chunk sizes. In other modes, a full-image buffer is needed and several passes are required. The control module determines which kind of buffer is used and manipulates virtual array buffers as needed. One or both processing steps may be unaware of the multi-pass behavior. In theory, we might be able to make all of the data buffer controllers interchangeable and provide just one set of implementations for all. In practice, each one contains considerable special-case processing for its particular job. The buffer controller concept should be regarded as an overall system structuring principle, not as a complete description of the task performed by any one controller. *** Compression object structure *** Here is a sketch of the logical structure of the JPEG compression library: |-- Colorspace conversion |-- Preprocessing controller --| | |-- Downsampling Main controller --| | |-- Forward DCT, quantize |-- Coefficient controller --| |-- Entropy encoding This sketch also describes the flow of control (subroutine calls) during typical image data processing. Each of the components shown in the diagram is an "object" which may have several different implementations available. One or more source code files contain the actual implementation(s) of each object. The objects shown above are: * Main controller: buffer controller for the subsampled-data buffer, which holds the preprocessed input data. This controller invokes preprocessing to fill the subsampled-data buffer, and JPEG compression to empty it. There is usually no need for a full-image buffer here; a strip buffer is adequate. * Preprocessing controller: buffer controller for the downsampling input data buffer, which lies between colorspace conversion and downsampling. Note that a unified conversion/downsampling module would probably replace this controller entirely. * Colorspace conversion: converts application image data into the desired JPEG color space; also changes the data from pixel-interleaved layout to separate component planes. Processes one pixel row at a time. * Downsampling: performs reduction of chroma components as required. Optionally may perform pixel-level smoothing as well. Processes a "row group" at a time, where a row group is defined as Vmax pixel rows of each component before downsampling, and Vk sample rows afterwards (remember Vk differs across components). Some downsampling or smoothing algorithms may require context rows above and below the current row group; the preprocessing controller is responsible for supplying these rows via proper buffering. The downsampler is responsible for edge expansion at the right edge (i.e., extending each sample row to a multiple of 8 samples); but the preprocessing controller is responsible for vertical edge expansion (i.e., duplicating the bottom sample row as needed to make a multiple of 8 rows). * Coefficient controller: buffer controller for the DCT-coefficient data. This controller handles MCU assembly, including insertion of dummy DCT blocks when needed at the right or bottom edge. When performing Huffman-code optimization or emitting a multiscan JPEG file, this controller is responsible for buffering the full image. The equivalent of one fully interleaved MCU row of subsampled data is processed per call, even when the JPEG file is noninterleaved. * Forward DCT and quantization: Perform DCT, quantize, and emit coefficients. Works on one or more DCT blocks at a time. (Note: the coefficients are now emitted in normal array order, which the entropy encoder is expected to convert to zigzag order as necessary. Prior versions of the IJG code did the conversion to zigzag order within the quantization step.) * Entropy encoding: Perform Huffman or arithmetic entropy coding and emit the coded data to the data destination module. Works on one MCU per call. For progressive JPEG, the same DCT blocks are fed to the entropy coder during each pass, and the coder must emit the appropriate subset of coefficients. In addition to the above objects, the compression library includes these objects: * Master control: determines the number of passes required, controls overall and per-pass initialization of the other modules. * Marker writing: generates JPEG markers (except for RSTn, which is emitted by the entropy encoder when needed). * Data destination manager: writes the output JPEG datastream to its final destination (e.g., a file). The destination manager supplied with the library knows how to write to a stdio stream; for other behaviors, the surrounding application may provide its own destination manager. * Memory manager: allocates and releases memory, controls virtual arrays (with backing store management, where required). * Error handler: performs formatting and output of error and trace messages; determines handling of nonfatal errors. The surrounding application may override some or all of this object's methods to change error handling. * Progress monitor: supports output of "percent-done" progress reports. This object represents an optional callback to the surrounding application: if wanted, it must be supplied by the application. The error handler, destination manager, and progress monitor objects are defined as separate objects in order to simplify application-specific customization of the JPEG library. A surrounding application may override individual methods or supply its own all-new implementation of one of these objects. The object interfaces for these objects are therefore treated as part of the application interface of the library, whereas the other objects are internal to the library. The error handler and memory manager are shared by JPEG compression and decompression; the progress monitor, if used, may be shared as well. *** Decompression object structure *** Here is a sketch of the logical structure of the JPEG decompression library: |-- Entropy decoding |-- Coefficient controller --| | |-- Dequantize, Inverse DCT Main controller --| | |-- Upsampling |-- Postprocessing controller --| |-- Colorspace conversion |-- Color quantization |-- Color precision reduction As before, this diagram also represents typical control flow. The objects shown are: * Main controller: buffer controller for the subsampled-data buffer, which holds the output of JPEG decompression proper. This controller's primary task is to feed the postprocessing procedure. Some upsampling algorithms may require context rows above and below the current row group; when this is true, the main controller is responsible for managing its buffer so as to make context rows available. In the current design, the main buffer is always a strip buffer; a full-image buffer is never required. * Coefficient controller: buffer controller for the DCT-coefficient data. This controller handles MCU disassembly, including deletion of any dummy DCT blocks at the right or bottom edge. When reading a multiscan JPEG file, this controller is responsible for buffering the full image. (Buffering DCT coefficients, rather than samples, is necessary to support progressive JPEG.) The equivalent of one fully interleaved MCU row of subsampled data is processed per call, even when the source JPEG file is noninterleaved. * Entropy decoding: Read coded data from the data source module and perform Huffman or arithmetic entropy decoding. Works on one MCU per call. For progressive JPEG decoding, the coefficient controller supplies the prior coefficients of each MCU (initially all zeroes), which the entropy decoder modifies in each scan. * Dequantization and inverse DCT: like it says. Note that the coefficients buffered by the coefficient controller have NOT been dequantized; we merge dequantization and inverse DCT into a single step for speed reasons. When scaled-down output is asked for, simplified DCT algorithms may be used that emit only 1x1, 2x2, or 4x4 samples per DCT block, not the full 8x8. Works on one DCT block at a time. * Postprocessing controller: buffer controller for the color quantization input buffer, when quantization is in use. (Without quantization, this controller just calls the upsampler.) For two-pass quantization, this controller is responsible for buffering the full-image data. * Upsampling: restores chroma components to full size. (May support more general output rescaling, too. Note that if undersized DCT outputs have been emitted by the DCT module, this module must adjust so that properly sized outputs are created.) Works on one row group at a time. This module also calls the color conversion module, so its top level is effectively a buffer controller for the upsampling->color conversion buffer. However, in all but the highest-quality operating modes, upsampling and color conversion are likely to be merged into a single step. * 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: