Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 1 | IJG JPEG LIBRARY: SYSTEM ARCHITECTURE |
| 2 | |
Guido Vollbeding | 5829cb2 | 2012-01-15 00:00:00 +0000 | [diff] [blame] | 3 | Copyright (C) 1991-2012, Thomas G. Lane, Guido Vollbeding. |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 4 | This file is part of the Independent JPEG Group's software. |
| 5 | For conditions of distribution and use, see the accompanying README file. |
| 6 | |
| 7 | |
| 8 | This file provides an overview of the architecture of the IJG JPEG software; |
| 9 | that is, the functions of the various modules in the system and the interfaces |
| 10 | between modules. For more precise details about any data structure or calling |
| 11 | convention, see the include files and comments in the source code. |
| 12 | |
| 13 | We assume that the reader is already somewhat familiar with the JPEG standard. |
| 14 | The README file includes references for learning about JPEG. The file |
Guido Vollbeding | 5996a25 | 2009-06-27 00:00:00 +0000 | [diff] [blame] | 15 | libjpeg.txt describes the library from the viewpoint of an application |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 16 | programmer using the library; it's best to read that file before this one. |
Guido Vollbeding | 5996a25 | 2009-06-27 00:00:00 +0000 | [diff] [blame] | 17 | Also, the file coderules.txt describes the coding style conventions we use. |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 18 | |
| 19 | In this document, JPEG-specific terminology follows the JPEG standard: |
| 20 | A "component" means a color channel, e.g., Red or Luminance. |
| 21 | A "sample" is a single component value (i.e., one number in the image data). |
| 22 | A "coefficient" is a frequency coefficient (a DCT transform output number). |
| 23 | A "block" is an 8x8 group of samples or coefficients. |
| 24 | An "MCU" (minimum coded unit) is an interleaved set of blocks of size |
| 25 | determined by the sampling factors, or a single block in a |
| 26 | noninterleaved scan. |
| 27 | We do not use the terms "pixel" and "sample" interchangeably. When we say |
| 28 | pixel, we mean an element of the full-size image, while a sample is an element |
| 29 | of the downsampled image. Thus the number of samples may vary across |
| 30 | components while the number of pixels does not. (This terminology is not used |
| 31 | rigorously throughout the code, but it is used in places where confusion would |
| 32 | otherwise result.) |
| 33 | |
| 34 | |
| 35 | *** System features *** |
| 36 | |
| 37 | The IJG distribution contains two parts: |
| 38 | * A subroutine library for JPEG compression and decompression. |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 39 | * cjpeg/djpeg, two sample applications that use the library to transform |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 40 | JFIF JPEG files to and from several other image formats. |
| 41 | cjpeg/djpeg are of no great intellectual complexity: they merely add a simple |
| 42 | command-line user interface and I/O routines for several uncompressed image |
| 43 | formats. This document concentrates on the library itself. |
| 44 | |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 45 | We desire the library to be capable of supporting all JPEG baseline, extended |
| 46 | sequential, and progressive DCT processes. Hierarchical processes are not |
| 47 | supported. |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 48 | |
| 49 | The library does not support the lossless (spatial) JPEG process. Lossless |
| 50 | JPEG shares little or no code with lossy JPEG, and would normally be used |
| 51 | without the extensive pre- and post-processing provided by this library. |
| 52 | We feel that lossless JPEG is better handled by a separate library. |
| 53 | |
| 54 | Within these limits, any set of compression parameters allowed by the JPEG |
| 55 | spec should be readable for decompression. (We can be more restrictive about |
| 56 | what formats we can generate.) Although the system design allows for all |
| 57 | parameter values, some uncommon settings are not yet implemented and may |
| 58 | never be; nonintegral sampling ratios are the prime example. Furthermore, |
| 59 | we treat 8-bit vs. 12-bit data precision as a compile-time switch, not a |
| 60 | run-time option, because most machines can store 8-bit pixels much more |
| 61 | compactly than 12-bit. |
| 62 | |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 63 | By itself, the library handles only interchange JPEG datastreams --- in |
| 64 | particular the widely used JFIF file format. The library can be used by |
| 65 | surrounding code to process interchange or abbreviated JPEG datastreams that |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 66 | are embedded in more complex file formats. (For example, libtiff uses this |
| 67 | library to implement JPEG compression within the TIFF file format.) |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 68 | |
| 69 | The library includes a substantial amount of code that is not covered by the |
| 70 | JPEG standard but is necessary for typical applications of JPEG. These |
| 71 | functions preprocess the image before JPEG compression or postprocess it after |
| 72 | decompression. They include colorspace conversion, downsampling/upsampling, |
| 73 | and color quantization. This code can be omitted if not needed. |
| 74 | |
| 75 | A wide range of quality vs. speed tradeoffs are possible in JPEG processing, |
| 76 | and even more so in decompression postprocessing. The decompression library |
| 77 | provides multiple implementations that cover most of the useful tradeoffs, |
| 78 | ranging from very-high-quality down to fast-preview operation. On the |
| 79 | compression side we have generally not provided low-quality choices, since |
| 80 | compression is normally less time-critical. It should be understood that the |
| 81 | low-quality modes may not meet the JPEG standard's accuracy requirements; |
| 82 | nonetheless, they are useful for viewers. |
| 83 | |
| 84 | |
| 85 | *** Portability issues *** |
| 86 | |
| 87 | Portability is an essential requirement for the library. The key portability |
| 88 | issues that show up at the level of system architecture are: |
| 89 | |
| 90 | 1. Memory usage. We want the code to be able to run on PC-class machines |
| 91 | with limited memory. Images should therefore be processed sequentially (in |
| 92 | strips), to avoid holding the whole image in memory at once. Where a |
| 93 | full-image buffer is necessary, we should be able to use either virtual memory |
| 94 | or temporary files. |
| 95 | |
| 96 | 2. Near/far pointer distinction. To run efficiently on 80x86 machines, the |
| 97 | code should distinguish "small" objects (kept in near data space) from |
| 98 | "large" ones (kept in far data space). This is an annoying restriction, but |
| 99 | fortunately it does not impact code quality for less brain-damaged machines, |
| 100 | and the source code clutter turns out to be minimal with sufficient use of |
| 101 | pointer typedefs. |
| 102 | |
| 103 | 3. Data precision. We assume that "char" is at least 8 bits, "short" and |
| 104 | "int" at least 16, "long" at least 32. The code will work fine with larger |
| 105 | data sizes, although memory may be used inefficiently in some cases. However, |
| 106 | the JPEG compressed datastream must ultimately appear on external storage as a |
| 107 | sequence of 8-bit bytes if it is to conform to the standard. This may pose a |
| 108 | problem on machines where char is wider than 8 bits. The library represents |
| 109 | compressed data as an array of values of typedef JOCTET. If no data type |
| 110 | exactly 8 bits wide is available, custom data source and data destination |
| 111 | modules must be written to unpack and pack the chosen JOCTET datatype into |
| 112 | 8-bit external representation. |
| 113 | |
| 114 | |
| 115 | *** System overview *** |
| 116 | |
| 117 | The compressor and decompressor are each divided into two main sections: |
| 118 | the JPEG compressor or decompressor proper, and the preprocessing or |
| 119 | postprocessing functions. The interface between these two sections is the |
| 120 | image data that the official JPEG spec regards as its input or output: this |
| 121 | data is in the colorspace to be used for compression, and it is downsampled |
| 122 | to the sampling factors to be used. The preprocessing and postprocessing |
| 123 | steps are responsible for converting a normal image representation to or from |
| 124 | this form. (Those few applications that want to deal with YCbCr downsampled |
| 125 | data can skip the preprocessing or postprocessing step.) |
| 126 | |
| 127 | Looking more closely, the compressor library contains the following main |
| 128 | elements: |
| 129 | |
| 130 | Preprocessing: |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 131 | * Color space conversion (e.g., RGB to YCbCr). |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 132 | * Edge expansion and downsampling. Optionally, this step can do simple |
| 133 | smoothing --- this is often helpful for low-quality source data. |
| 134 | JPEG proper: |
| 135 | * MCU assembly, DCT, quantization. |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 136 | * Entropy coding (sequential or progressive, Huffman or arithmetic). |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 137 | |
| 138 | In addition to these modules we need overall control, marker generation, |
| 139 | and support code (memory management & error handling). There is also a |
| 140 | module responsible for physically writing the output data --- typically |
| 141 | this is just an interface to fwrite(), but some applications may need to |
| 142 | do something else with the data. |
| 143 | |
| 144 | The decompressor library contains the following main elements: |
| 145 | |
| 146 | JPEG proper: |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 147 | * Entropy decoding (sequential or progressive, Huffman or arithmetic). |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 148 | * Dequantization, inverse DCT, MCU disassembly. |
| 149 | Postprocessing: |
| 150 | * Upsampling. Optionally, this step may be able to do more general |
| 151 | rescaling of the image. |
| 152 | * Color space conversion (e.g., YCbCr to RGB). This step may also |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 153 | provide gamma adjustment [ currently it does not ]. |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 154 | * Optional color quantization (e.g., reduction to 256 colors). |
| 155 | * Optional color precision reduction (e.g., 24-bit to 15-bit color). |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 156 | [This feature is not currently implemented.] |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 157 | |
| 158 | We also need overall control, marker parsing, and a data source module. |
| 159 | The support code (memory management & error handling) can be shared with |
| 160 | the compression half of the library. |
| 161 | |
| 162 | There may be several implementations of each of these elements, particularly |
| 163 | in the decompressor, where a wide range of speed/quality tradeoffs is very |
| 164 | useful. It must be understood that some of the best speedups involve |
| 165 | merging adjacent steps in the pipeline. For example, upsampling, color space |
| 166 | conversion, and color quantization might all be done at once when using a |
| 167 | low-quality ordered-dither technique. The system architecture is designed to |
| 168 | allow such merging where appropriate. |
| 169 | |
| 170 | |
| 171 | Note: it is convenient to regard edge expansion (padding to block boundaries) |
| 172 | as a preprocessing/postprocessing function, even though the JPEG spec includes |
| 173 | it in compression/decompression. We do this because downsampling/upsampling |
| 174 | can be simplified a little if they work on padded data: it's not necessary to |
| 175 | have special cases at the right and bottom edges. Therefore the interface |
| 176 | buffer is always an integral number of blocks wide and high, and we expect |
| 177 | compression preprocessing to pad the source data properly. Padding will occur |
| 178 | only to the next block (8-sample) boundary. In an interleaved-scan situation, |
| 179 | additional dummy blocks may be used to fill out MCUs, but the MCU assembly and |
| 180 | disassembly logic will create or discard these blocks internally. (This is |
| 181 | advantageous for speed reasons, since we avoid DCTing the dummy blocks. |
| 182 | It also permits a small reduction in file size, because the compressor can |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 183 | choose dummy block contents so as to minimize their size in compressed form. |
| 184 | Finally, it makes the interface buffer specification independent of whether |
| 185 | the file is actually interleaved or not.) Applications that wish to deal |
| 186 | directly with the downsampled data must provide similar buffering and padding |
| 187 | for odd-sized images. |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 188 | |
| 189 | |
| 190 | *** Poor man's object-oriented programming *** |
| 191 | |
| 192 | It should be clear by now that we have a lot of quasi-independent processing |
| 193 | steps, many of which have several possible behaviors. To avoid cluttering the |
| 194 | code with lots of switch statements, we use a simple form of object-style |
| 195 | programming to separate out the different possibilities. |
| 196 | |
| 197 | For example, two different color quantization algorithms could be implemented |
| 198 | as two separate modules that present the same external interface; at runtime, |
| 199 | the calling code will access the proper module indirectly through an "object". |
| 200 | |
| 201 | We can get the limited features we need while staying within portable C. |
| 202 | The basic tool is a function pointer. An "object" is just a struct |
| 203 | containing one or more function pointer fields, each of which corresponds to |
| 204 | a method name in real object-oriented languages. During initialization we |
| 205 | fill in the function pointers with references to whichever module we have |
| 206 | determined we need to use in this run. Then invocation of the module is done |
| 207 | by indirecting through a function pointer; on most machines this is no more |
| 208 | expensive than a switch statement, which would be the only other way of |
| 209 | making the required run-time choice. The really significant benefit, of |
| 210 | course, is keeping the source code clean and well structured. |
| 211 | |
| 212 | We can also arrange to have private storage that varies between different |
| 213 | implementations of the same kind of object. We do this by making all the |
| 214 | module-specific object structs be separately allocated entities, which will |
| 215 | be accessed via pointers in the master compression or decompression struct. |
| 216 | The "public" fields or methods for a given kind of object are specified by |
| 217 | a commonly known struct. But a module's initialization code can allocate |
| 218 | a larger struct that contains the common struct as its first member, plus |
| 219 | additional private fields. With appropriate pointer casting, the module's |
| 220 | internal functions can access these private fields. (For a simple example, |
| 221 | see jdatadst.c, which implements the external interface specified by struct |
| 222 | jpeg_destination_mgr, but adds extra fields.) |
| 223 | |
| 224 | (Of course this would all be a lot easier if we were using C++, but we are |
| 225 | not yet prepared to assume that everyone has a C++ compiler.) |
| 226 | |
| 227 | An important benefit of this scheme is that it is easy to provide multiple |
| 228 | versions of any method, each tuned to a particular case. While a lot of |
| 229 | precalculation might be done to select an optimal implementation of a method, |
| 230 | the cost per invocation is constant. For example, the upsampling step might |
| 231 | have a "generic" method, plus one or more "hardwired" methods for the most |
| 232 | popular sampling factors; the hardwired methods would be faster because they'd |
| 233 | use straight-line code instead of for-loops. The cost to determine which |
| 234 | method to use is paid only once, at startup, and the selection criteria are |
| 235 | hidden from the callers of the method. |
| 236 | |
| 237 | This plan differs a little bit from usual object-oriented structures, in that |
| 238 | only one instance of each object class will exist during execution. The |
| 239 | reason for having the class structure is that on different runs we may create |
| 240 | different instances (choose to execute different modules). You can think of |
| 241 | the term "method" as denoting the common interface presented by a particular |
| 242 | set of interchangeable functions, and "object" as denoting a group of related |
| 243 | methods, or the total shared interface behavior of a group of modules. |
| 244 | |
| 245 | |
| 246 | *** Overall control structure *** |
| 247 | |
| 248 | We previously mentioned the need for overall control logic in the compression |
| 249 | and decompression libraries. In IJG implementations prior to v5, overall |
| 250 | control was mostly provided by "pipeline control" modules, which proved to be |
| 251 | large, unwieldy, and hard to understand. To improve the situation, the |
| 252 | control logic has been subdivided into multiple modules. The control modules |
| 253 | consist of: |
| 254 | |
| 255 | 1. Master control for module selection and initialization. This has two |
| 256 | responsibilities: |
| 257 | |
| 258 | 1A. Startup initialization at the beginning of image processing. |
| 259 | The individual processing modules to be used in this run are selected |
| 260 | and given initialization calls. |
| 261 | |
| 262 | 1B. Per-pass control. This determines how many passes will be performed |
| 263 | and calls each active processing module to configure itself |
| 264 | appropriately at the beginning of each pass. End-of-pass processing, |
| 265 | where necessary, is also invoked from the master control module. |
| 266 | |
| 267 | Method selection is partially distributed, in that a particular processing |
| 268 | module may contain several possible implementations of a particular method, |
| 269 | which it will select among when given its initialization call. The master |
| 270 | control code need only be concerned with decisions that affect more than |
| 271 | one module. |
| 272 | |
| 273 | 2. Data buffering control. A separate control module exists for each |
| 274 | inter-processing-step data buffer. This module is responsible for |
| 275 | invoking the processing steps that write or read that data buffer. |
| 276 | |
| 277 | Each buffer controller sees the world as follows: |
| 278 | |
| 279 | input data => processing step A => buffer => processing step B => output data |
| 280 | | | | |
| 281 | ------------------ controller ------------------ |
| 282 | |
| 283 | The controller knows the dataflow requirements of steps A and B: how much data |
| 284 | they want to accept in one chunk and how much they output in one chunk. Its |
| 285 | function is to manage its buffer and call A and B at the proper times. |
| 286 | |
| 287 | A data buffer control module may itself be viewed as a processing step by a |
| 288 | higher-level control module; thus the control modules form a binary tree with |
| 289 | elementary processing steps at the leaves of the tree. |
| 290 | |
| 291 | The control modules are objects. A considerable amount of flexibility can |
| 292 | be had by replacing implementations of a control module. For example: |
| 293 | * Merging of adjacent steps in the pipeline is done by replacing a control |
| 294 | module and its pair of processing-step modules with a single processing- |
| 295 | step module. (Hence the possible merges are determined by the tree of |
| 296 | control modules.) |
| 297 | * In some processing modes, a given interstep buffer need only be a "strip" |
| 298 | buffer large enough to accommodate the desired data chunk sizes. In other |
| 299 | modes, a full-image buffer is needed and several passes are required. |
| 300 | The control module determines which kind of buffer is used and manipulates |
| 301 | virtual array buffers as needed. One or both processing steps may be |
| 302 | unaware of the multi-pass behavior. |
| 303 | |
| 304 | In theory, we might be able to make all of the data buffer controllers |
| 305 | interchangeable and provide just one set of implementations for all. In |
| 306 | practice, each one contains considerable special-case processing for its |
| 307 | particular job. The buffer controller concept should be regarded as an |
| 308 | overall system structuring principle, not as a complete description of the |
| 309 | task performed by any one controller. |
| 310 | |
| 311 | |
| 312 | *** Compression object structure *** |
| 313 | |
| 314 | Here is a sketch of the logical structure of the JPEG compression library: |
| 315 | |
| 316 | |-- Colorspace conversion |
| 317 | |-- Preprocessing controller --| |
| 318 | | |-- Downsampling |
| 319 | Main controller --| |
| 320 | | |-- Forward DCT, quantize |
| 321 | |-- Coefficient controller --| |
| 322 | |-- Entropy encoding |
| 323 | |
| 324 | This sketch also describes the flow of control (subroutine calls) during |
| 325 | typical image data processing. Each of the components shown in the diagram is |
| 326 | an "object" which may have several different implementations available. One |
| 327 | or more source code files contain the actual implementation(s) of each object. |
| 328 | |
| 329 | The objects shown above are: |
| 330 | |
| 331 | * Main controller: buffer controller for the subsampled-data buffer, which |
| 332 | holds the preprocessed input data. This controller invokes preprocessing to |
| 333 | fill the subsampled-data buffer, and JPEG compression to empty it. There is |
| 334 | usually no need for a full-image buffer here; a strip buffer is adequate. |
| 335 | |
| 336 | * Preprocessing controller: buffer controller for the downsampling input data |
| 337 | buffer, which lies between colorspace conversion and downsampling. Note |
| 338 | that a unified conversion/downsampling module would probably replace this |
| 339 | controller entirely. |
| 340 | |
| 341 | * Colorspace conversion: converts application image data into the desired |
| 342 | JPEG color space; also changes the data from pixel-interleaved layout to |
| 343 | separate component planes. Processes one pixel row at a time. |
| 344 | |
| 345 | * Downsampling: performs reduction of chroma components as required. |
| 346 | Optionally may perform pixel-level smoothing as well. Processes a "row |
| 347 | group" at a time, where a row group is defined as Vmax pixel rows of each |
| 348 | component before downsampling, and Vk sample rows afterwards (remember Vk |
| 349 | differs across components). Some downsampling or smoothing algorithms may |
| 350 | require context rows above and below the current row group; the |
| 351 | preprocessing controller is responsible for supplying these rows via proper |
| 352 | buffering. The downsampler is responsible for edge expansion at the right |
| 353 | edge (i.e., extending each sample row to a multiple of 8 samples); but the |
| 354 | preprocessing controller is responsible for vertical edge expansion (i.e., |
| 355 | duplicating the bottom sample row as needed to make a multiple of 8 rows). |
| 356 | |
| 357 | * Coefficient controller: buffer controller for the DCT-coefficient data. |
| 358 | This controller handles MCU assembly, including insertion of dummy DCT |
| 359 | blocks when needed at the right or bottom edge. When performing |
| 360 | Huffman-code optimization or emitting a multiscan JPEG file, this |
Thomas G. Lane | a8b67c4 | 1995-03-15 00:00:00 +0000 | [diff] [blame] | 361 | controller is responsible for buffering the full image. The equivalent of |
| 362 | one fully interleaved MCU row of subsampled data is processed per call, |
| 363 | even when the JPEG file is noninterleaved. |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 364 | |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 365 | * Forward DCT and quantization: Perform DCT, quantize, and emit coefficients. |
| 366 | Works on one or more DCT blocks at a time. (Note: the coefficients are now |
| 367 | emitted in normal array order, which the entropy encoder is expected to |
| 368 | convert to zigzag order as necessary. Prior versions of the IJG code did |
| 369 | the conversion to zigzag order within the quantization step.) |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 370 | |
| 371 | * Entropy encoding: Perform Huffman or arithmetic entropy coding and emit the |
| 372 | coded data to the data destination module. Works on one MCU per call. |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 373 | For progressive JPEG, the same DCT blocks are fed to the entropy coder |
| 374 | during each pass, and the coder must emit the appropriate subset of |
| 375 | coefficients. |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 376 | |
| 377 | In addition to the above objects, the compression library includes these |
| 378 | objects: |
| 379 | |
| 380 | * Master control: determines the number of passes required, controls overall |
| 381 | and per-pass initialization of the other modules. |
| 382 | |
| 383 | * Marker writing: generates JPEG markers (except for RSTn, which is emitted |
| 384 | by the entropy encoder when needed). |
| 385 | |
| 386 | * Data destination manager: writes the output JPEG datastream to its final |
| 387 | destination (e.g., a file). The destination manager supplied with the |
Guido Vollbeding | 5829cb2 | 2012-01-15 00:00:00 +0000 | [diff] [blame] | 388 | library knows how to write to a stdio stream or to a memory buffer; |
| 389 | for other behaviors, the surrounding application may provide its own |
| 390 | destination manager. |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 391 | |
| 392 | * Memory manager: allocates and releases memory, controls virtual arrays |
| 393 | (with backing store management, where required). |
| 394 | |
| 395 | * Error handler: performs formatting and output of error and trace messages; |
| 396 | determines handling of nonfatal errors. The surrounding application may |
| 397 | override some or all of this object's methods to change error handling. |
| 398 | |
| 399 | * Progress monitor: supports output of "percent-done" progress reports. |
| 400 | This object represents an optional callback to the surrounding application: |
| 401 | if wanted, it must be supplied by the application. |
| 402 | |
| 403 | The error handler, destination manager, and progress monitor objects are |
| 404 | defined as separate objects in order to simplify application-specific |
| 405 | customization of the JPEG library. A surrounding application may override |
| 406 | individual methods or supply its own all-new implementation of one of these |
| 407 | objects. The object interfaces for these objects are therefore treated as |
| 408 | part of the application interface of the library, whereas the other objects |
| 409 | are internal to the library. |
| 410 | |
| 411 | The error handler and memory manager are shared by JPEG compression and |
| 412 | decompression; the progress monitor, if used, may be shared as well. |
| 413 | |
| 414 | |
| 415 | *** Decompression object structure *** |
| 416 | |
| 417 | Here is a sketch of the logical structure of the JPEG decompression library: |
| 418 | |
| 419 | |-- Entropy decoding |
| 420 | |-- Coefficient controller --| |
| 421 | | |-- Dequantize, Inverse DCT |
| 422 | Main controller --| |
| 423 | | |-- Upsampling |
| 424 | |-- Postprocessing controller --| |-- Colorspace conversion |
| 425 | |-- Color quantization |
| 426 | |-- Color precision reduction |
| 427 | |
| 428 | As before, this diagram also represents typical control flow. The objects |
| 429 | shown are: |
| 430 | |
| 431 | * Main controller: buffer controller for the subsampled-data buffer, which |
| 432 | holds the output of JPEG decompression proper. This controller's primary |
| 433 | task is to feed the postprocessing procedure. Some upsampling algorithms |
| 434 | may require context rows above and below the current row group; when this |
| 435 | is true, the main controller is responsible for managing its buffer so as |
| 436 | to make context rows available. In the current design, the main buffer is |
| 437 | always a strip buffer; a full-image buffer is never required. |
| 438 | |
| 439 | * Coefficient controller: buffer controller for the DCT-coefficient data. |
| 440 | This controller handles MCU disassembly, including deletion of any dummy |
| 441 | DCT blocks at the right or bottom edge. When reading a multiscan JPEG |
| 442 | file, this controller is responsible for buffering the full image. |
| 443 | (Buffering DCT coefficients, rather than samples, is necessary to support |
| 444 | progressive JPEG.) The equivalent of one fully interleaved MCU row of |
| 445 | subsampled data is processed per call, even when the source JPEG file is |
| 446 | noninterleaved. |
| 447 | |
| 448 | * Entropy decoding: Read coded data from the data source module and perform |
| 449 | Huffman or arithmetic entropy decoding. Works on one MCU per call. |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 450 | For progressive JPEG decoding, the coefficient controller supplies the prior |
| 451 | coefficients of each MCU (initially all zeroes), which the entropy decoder |
| 452 | modifies in each scan. |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 453 | |
| 454 | * Dequantization and inverse DCT: like it says. Note that the coefficients |
| 455 | buffered by the coefficient controller have NOT been dequantized; we |
| 456 | merge dequantization and inverse DCT into a single step for speed reasons. |
| 457 | When scaled-down output is asked for, simplified DCT algorithms may be used |
| 458 | that emit only 1x1, 2x2, or 4x4 samples per DCT block, not the full 8x8. |
| 459 | Works on one DCT block at a time. |
| 460 | |
| 461 | * Postprocessing controller: buffer controller for the color quantization |
| 462 | input buffer, when quantization is in use. (Without quantization, this |
| 463 | controller just calls the upsampler.) For two-pass quantization, this |
| 464 | controller is responsible for buffering the full-image data. |
| 465 | |
| 466 | * Upsampling: restores chroma components to full size. (May support more |
| 467 | general output rescaling, too. Note that if undersized DCT outputs have |
| 468 | been emitted by the DCT module, this module must adjust so that properly |
| 469 | sized outputs are created.) Works on one row group at a time. This module |
| 470 | also calls the color conversion module, so its top level is effectively a |
| 471 | buffer controller for the upsampling->color conversion buffer. However, in |
| 472 | all but the highest-quality operating modes, upsampling and color |
| 473 | conversion are likely to be merged into a single step. |
| 474 | |
| 475 | * Colorspace conversion: convert from JPEG color space to output color space, |
| 476 | and change data layout from separate component planes to pixel-interleaved. |
| 477 | Works on one pixel row at a time. |
| 478 | |
| 479 | * Color quantization: reduce the data to colormapped form, using either an |
| 480 | externally specified colormap or an internally generated one. This module |
| 481 | is not used for full-color output. Works on one pixel row at a time; may |
| 482 | require two passes to generate a color map. Note that the output will |
| 483 | always be a single component representing colormap indexes. In the current |
| 484 | design, the output values are JSAMPLEs, so an 8-bit compilation cannot |
| 485 | quantize to more than 256 colors. This is unlikely to be a problem in |
| 486 | practice. |
| 487 | |
| 488 | * Color reduction: this module handles color precision reduction, e.g., |
| 489 | generating 15-bit color (5 bits/primary) from JPEG's 24-bit output. |
| 490 | Not quite clear yet how this should be handled... should we merge it with |
| 491 | colorspace conversion??? |
| 492 | |
| 493 | Note that some high-speed operating modes might condense the entire |
| 494 | postprocessing sequence to a single module (upsample, color convert, and |
| 495 | quantize in one step). |
| 496 | |
| 497 | In addition to the above objects, the decompression library includes these |
| 498 | objects: |
| 499 | |
| 500 | * Master control: determines the number of passes required, controls overall |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 501 | and per-pass initialization of the other modules. This is subdivided into |
| 502 | input and output control: jdinput.c controls only input-side processing, |
| 503 | while jdmaster.c handles overall initialization and output-side control. |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 504 | |
| 505 | * Marker reading: decodes JPEG markers (except for RSTn). |
| 506 | |
| 507 | * Data source manager: supplies the input JPEG datastream. The source |
Guido Vollbeding | 5829cb2 | 2012-01-15 00:00:00 +0000 | [diff] [blame] | 508 | manager supplied with the library knows how to read from a stdio stream |
| 509 | or from a memory buffer; for other behaviors, the surrounding application |
| 510 | may provide its own source manager. |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 511 | |
| 512 | * Memory manager: same as for compression library. |
| 513 | |
| 514 | * Error handler: same as for compression library. |
| 515 | |
| 516 | * Progress monitor: same as for compression library. |
| 517 | |
| 518 | As with compression, the data source manager, error handler, and progress |
| 519 | monitor are candidates for replacement by a surrounding application. |
| 520 | |
| 521 | |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 522 | *** Decompression input and output separation *** |
| 523 | |
| 524 | To support efficient incremental display of progressive JPEG files, the |
| 525 | decompressor is divided into two sections that can run independently: |
| 526 | |
| 527 | 1. Data input includes marker parsing, entropy decoding, and input into the |
| 528 | coefficient controller's DCT coefficient buffer. Note that this |
| 529 | processing is relatively cheap and fast. |
| 530 | |
| 531 | 2. Data output reads from the DCT coefficient buffer and performs the IDCT |
| 532 | and all postprocessing steps. |
| 533 | |
| 534 | For a progressive JPEG file, the data input processing is allowed to get |
| 535 | arbitrarily far ahead of the data output processing. (This occurs only |
| 536 | if the application calls jpeg_consume_input(); otherwise input and output |
| 537 | run in lockstep, since the input section is called only when the output |
| 538 | section needs more data.) In this way the application can avoid making |
| 539 | extra display passes when data is arriving faster than the display pass |
| 540 | can run. Furthermore, it is possible to abort an output pass without |
| 541 | losing anything, since the coefficient buffer is read-only as far as the |
Guido Vollbeding | 5996a25 | 2009-06-27 00:00:00 +0000 | [diff] [blame] | 542 | output section is concerned. See libjpeg.txt for more detail. |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 543 | |
| 544 | A full-image coefficient array is only created if the JPEG file has multiple |
| 545 | scans (or if the application specifies buffered-image mode anyway). When |
| 546 | reading a single-scan file, the coefficient controller normally creates only |
| 547 | a one-MCU buffer, so input and output processing must run in lockstep in this |
| 548 | case. jpeg_consume_input() is effectively a no-op in this situation. |
| 549 | |
| 550 | The main impact of dividing the decompressor in this fashion is that we must |
| 551 | be very careful with shared variables in the cinfo data structure. Each |
| 552 | variable that can change during the course of decompression must be |
| 553 | classified as belonging to data input or data output, and each section must |
| 554 | look only at its own variables. For example, the data output section may not |
| 555 | depend on any of the variables that describe the current scan in the JPEG |
| 556 | file, because these may change as the data input section advances into a new |
| 557 | scan. |
| 558 | |
| 559 | The progress monitor is (somewhat arbitrarily) defined to treat input of the |
| 560 | file as one pass when buffered-image mode is not used, and to ignore data |
| 561 | input work completely when buffered-image mode is used. Note that the |
| 562 | library has no reliable way to predict the number of passes when dealing |
| 563 | with a progressive JPEG file, nor can it predict the number of output passes |
| 564 | in buffered-image mode. So the work estimate is inherently bogus anyway. |
| 565 | |
| 566 | No comparable division is currently made in the compression library, because |
| 567 | there isn't any real need for it. |
| 568 | |
| 569 | |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 570 | *** Data formats *** |
| 571 | |
| 572 | Arrays of pixel sample values use the following data structure: |
| 573 | |
| 574 | typedef something JSAMPLE; a pixel component value, 0..MAXJSAMPLE |
| 575 | typedef JSAMPLE *JSAMPROW; ptr to a row of samples |
| 576 | typedef JSAMPROW *JSAMPARRAY; ptr to a list of rows |
| 577 | typedef JSAMPARRAY *JSAMPIMAGE; ptr to a list of color-component arrays |
| 578 | |
| 579 | The basic element type JSAMPLE will typically be one of unsigned char, |
| 580 | (signed) char, or short. Short will be used if samples wider than 8 bits are |
| 581 | to be supported (this is a compile-time option). Otherwise, unsigned char is |
| 582 | used if possible. If the compiler only supports signed chars, then it is |
| 583 | necessary to mask off the value when reading. Thus, all reads of JSAMPLE |
| 584 | values must be coded as "GETJSAMPLE(value)", where the macro will be defined |
| 585 | as "((value) & 0xFF)" on signed-char machines and "((int) (value))" elsewhere. |
| 586 | |
| 587 | With these conventions, JSAMPLE values can be assumed to be >= 0. This helps |
| 588 | simplify correct rounding during downsampling, etc. The JPEG standard's |
| 589 | specification that sample values run from -128..127 is accommodated by |
Guido Vollbeding | 5996a25 | 2009-06-27 00:00:00 +0000 | [diff] [blame] | 590 | subtracting 128 from the sample value in the DCT step. Similarly, during |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 591 | decompression the output of the IDCT step will be immediately shifted back to |
| 592 | 0..255. (NB: different values are required when 12-bit samples are in use. |
| 593 | The code is written in terms of MAXJSAMPLE and CENTERJSAMPLE, which will be |
| 594 | defined as 255 and 128 respectively in an 8-bit implementation, and as 4095 |
| 595 | and 2048 in a 12-bit implementation.) |
| 596 | |
| 597 | We use a pointer per row, rather than a two-dimensional JSAMPLE array. This |
| 598 | choice costs only a small amount of memory and has several benefits: |
| 599 | * Code using the data structure doesn't need to know the allocated width of |
| 600 | the rows. This simplifies edge expansion/compression, since we can work |
| 601 | in an array that's wider than the logical picture width. |
| 602 | * Indexing doesn't require multiplication; this is a performance win on many |
| 603 | machines. |
| 604 | * Arrays with more than 64K total elements can be supported even on machines |
| 605 | where malloc() cannot allocate chunks larger than 64K. |
| 606 | * The rows forming a component array may be allocated at different times |
| 607 | without extra copying. This trick allows some speedups in smoothing steps |
| 608 | that need access to the previous and next rows. |
| 609 | |
| 610 | Note that each color component is stored in a separate array; we don't use the |
| 611 | traditional layout in which the components of a pixel are stored together. |
| 612 | This simplifies coding of modules that work on each component independently, |
| 613 | because they don't need to know how many components there are. Furthermore, |
| 614 | we can read or write each component to a temporary file independently, which |
| 615 | is helpful when dealing with noninterleaved JPEG files. |
| 616 | |
| 617 | In general, a specific sample value is accessed by code such as |
| 618 | GETJSAMPLE(image[colorcomponent][row][col]) |
| 619 | where col is measured from the image left edge, but row is measured from the |
| 620 | first sample row currently in memory. Either of the first two indexings can |
| 621 | be precomputed by copying the relevant pointer. |
| 622 | |
| 623 | |
| 624 | Since most image-processing applications prefer to work on images in which |
| 625 | the components of a pixel are stored together, the data passed to or from the |
| 626 | surrounding application uses the traditional convention: a single pixel is |
| 627 | represented by N consecutive JSAMPLE values, and an image row is an array of |
| 628 | (# of color components)*(image width) JSAMPLEs. One or more rows of data can |
| 629 | be represented by a pointer of type JSAMPARRAY in this scheme. This scheme is |
| 630 | converted to component-wise storage inside the JPEG library. (Applications |
| 631 | that want to skip JPEG preprocessing or postprocessing will have to contend |
| 632 | with component-wise storage.) |
| 633 | |
| 634 | |
| 635 | Arrays of DCT-coefficient values use the following data structure: |
| 636 | |
| 637 | typedef short JCOEF; a 16-bit signed integer |
| 638 | typedef JCOEF JBLOCK[DCTSIZE2]; an 8x8 block of coefficients |
| 639 | typedef JBLOCK *JBLOCKROW; ptr to one horizontal row of 8x8 blocks |
| 640 | typedef JBLOCKROW *JBLOCKARRAY; ptr to a list of such rows |
| 641 | typedef JBLOCKARRAY *JBLOCKIMAGE; ptr to a list of color component arrays |
| 642 | |
| 643 | The underlying type is at least a 16-bit signed integer; while "short" is big |
| 644 | enough on all machines of interest, on some machines it is preferable to use |
| 645 | "int" for speed reasons, despite the storage cost. Coefficients are grouped |
| 646 | into 8x8 blocks (but we always use #defines DCTSIZE and DCTSIZE2 rather than |
Thomas G. Lane | 489583f | 1996-02-07 00:00:00 +0000 | [diff] [blame] | 647 | "8" and "64"). |
| 648 | |
| 649 | The contents of a coefficient block may be in either "natural" or zigzagged |
| 650 | order, and may be true values or divided by the quantization coefficients, |
| 651 | depending on where the block is in the processing pipeline. In the current |
| 652 | library, coefficient blocks are kept in natural order everywhere; the entropy |
| 653 | codecs zigzag or dezigzag the data as it is written or read. The blocks |
| 654 | contain quantized coefficients everywhere outside the DCT/IDCT subsystems. |
| 655 | (This latter decision may need to be revisited to support variable |
| 656 | quantization a la JPEG Part 3.) |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 657 | |
| 658 | Notice that the allocation unit is now a row of 8x8 blocks, corresponding to |
| 659 | eight rows of samples. Otherwise the structure is much the same as for |
| 660 | samples, and for the same reasons. |
| 661 | |
| 662 | On machines where malloc() can't handle a request bigger than 64Kb, this data |
| 663 | structure limits us to rows of less than 512 JBLOCKs, or a picture width of |
| 664 | 4000+ pixels. This seems an acceptable restriction. |
| 665 | |
| 666 | |
| 667 | On 80x86 machines, the bottom-level pointer types (JSAMPROW and JBLOCKROW) |
| 668 | must be declared as "far" pointers, but the upper levels can be "near" |
| 669 | (implying that the pointer lists are allocated in the DS segment). |
| 670 | We use a #define symbol FAR, which expands to the "far" keyword when |
| 671 | compiling on 80x86 machines and to nothing elsewhere. |
| 672 | |
| 673 | |
| 674 | *** Suspendable processing *** |
| 675 | |
| 676 | In some applications it is desirable to use the JPEG library as an |
| 677 | incremental, memory-to-memory filter. In this situation the data source or |
| 678 | destination may be a limited-size buffer, and we can't rely on being able to |
| 679 | empty or refill the buffer at arbitrary times. Instead the application would |
| 680 | like to have control return from the library at buffer overflow/underrun, and |
| 681 | then resume compression or decompression at a later time. |
| 682 | |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 683 | This scenario is supported for simple cases. (For anything more complex, we |
| 684 | recommend that the application "bite the bullet" and develop real multitasking |
Guido Vollbeding | 5996a25 | 2009-06-27 00:00:00 +0000 | [diff] [blame] | 685 | capability.) The libjpeg.txt file goes into more detail about the usage and |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 686 | limitations of this capability; here we address the implications for library |
| 687 | structure. |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 688 | |
| 689 | The essence of the problem is that the entropy codec (coder or decoder) must |
| 690 | be prepared to stop at arbitrary times. In turn, the controllers that call |
| 691 | the entropy codec must be able to stop before having produced or consumed all |
| 692 | the data that they normally would handle in one call. That part is reasonably |
| 693 | straightforward: we make the controller call interfaces include "progress |
| 694 | counters" which indicate the number of data chunks successfully processed, and |
| 695 | we require callers to test the counter rather than just assume all of the data |
| 696 | was processed. |
| 697 | |
| 698 | Rather than trying to restart at an arbitrary point, the current Huffman |
| 699 | codecs are designed to restart at the beginning of the current MCU after a |
| 700 | suspension due to buffer overflow/underrun. At the start of each call, the |
| 701 | codec's internal state is loaded from permanent storage (in the JPEG object |
| 702 | structures) into local variables. On successful completion of the MCU, the |
| 703 | permanent state is updated. (This copying is not very expensive, and may even |
| 704 | lead to *improved* performance if the local variables can be registerized.) |
| 705 | If a suspension occurs, the codec simply returns without updating the state, |
| 706 | thus effectively reverting to the start of the MCU. Note that this implies |
| 707 | leaving some data unprocessed in the source/destination buffer (ie, the |
| 708 | compressed partial MCU). The data source/destination module interfaces are |
| 709 | specified so as to make this possible. This also implies that the data buffer |
| 710 | must be large enough to hold a worst-case compressed MCU; a couple thousand |
| 711 | bytes should be enough. |
| 712 | |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 713 | In a successive-approximation AC refinement scan, the progressive Huffman |
| 714 | decoder has to be able to undo assignments of newly nonzero coefficients if it |
| 715 | suspends before the MCU is complete, since decoding requires distinguishing |
| 716 | previously-zero and previously-nonzero coefficients. This is a bit tedious |
| 717 | but probably won't have much effect on performance. Other variants of Huffman |
| 718 | decoding need not worry about this, since they will just store the same values |
| 719 | again if forced to repeat the MCU. |
| 720 | |
| 721 | This approach would probably not work for an arithmetic codec, since its |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 722 | modifiable state is quite large and couldn't be copied cheaply. Instead it |
| 723 | would have to suspend and resume exactly at the point of the buffer end. |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 724 | |
| 725 | The JPEG marker reader is designed to cope with suspension at an arbitrary |
| 726 | point. It does so by backing up to the start of the marker parameter segment, |
| 727 | so the data buffer must be big enough to hold the largest marker of interest. |
| 728 | Again, a couple KB should be adequate. (A special "skip" convention is used |
| 729 | to bypass COM and APPn markers, so these can be larger than the buffer size |
| 730 | without causing problems; otherwise a 64K buffer would be needed in the worst |
| 731 | case.) |
| 732 | |
Guido Vollbeding | 5996a25 | 2009-06-27 00:00:00 +0000 | [diff] [blame] | 733 | The JPEG marker writer currently does *not* cope with suspension. |
| 734 | We feel that this is not necessary; it is much easier simply to require |
| 735 | the application to ensure there is enough buffer space before starting. (An |
| 736 | empty 2K buffer is more than sufficient for the header markers; and ensuring |
| 737 | there are a dozen or two bytes available before calling jpeg_finish_compress() |
| 738 | will suffice for the trailer.) This would not work for writing multi-scan |
| 739 | JPEG files, but we simply do not intend to support that capability with |
| 740 | suspension. |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 741 | |
| 742 | |
| 743 | *** Memory manager services *** |
| 744 | |
| 745 | The JPEG library's memory manager controls allocation and deallocation of |
| 746 | memory, and it manages large "virtual" data arrays on machines where the |
| 747 | operating system does not provide virtual memory. Note that the same |
| 748 | memory manager serves both compression and decompression operations. |
| 749 | |
| 750 | In all cases, allocated objects are tied to a particular compression or |
| 751 | decompression master record, and they will be released when that master |
| 752 | record is destroyed. |
| 753 | |
| 754 | The memory manager does not provide explicit deallocation of objects. |
| 755 | Instead, objects are created in "pools" of free storage, and a whole pool |
| 756 | can be freed at once. This approach helps prevent storage-leak bugs, and |
| 757 | it speeds up operations whenever malloc/free are slow (as they often are). |
| 758 | The pools can be regarded as lifetime identifiers for objects. Two |
| 759 | pools/lifetimes are defined: |
| 760 | * JPOOL_PERMANENT lasts until master record is destroyed |
| 761 | * JPOOL_IMAGE lasts until done with image (JPEG datastream) |
| 762 | Permanent lifetime is used for parameters and tables that should be carried |
| 763 | across from one datastream to another; this includes all application-visible |
| 764 | parameters. Image lifetime is used for everything else. (A third lifetime, |
| 765 | JPOOL_PASS = one processing pass, was originally planned. However it was |
| 766 | dropped as not being worthwhile. The actual usage patterns are such that the |
| 767 | peak memory usage would be about the same anyway; and having per-pass storage |
| 768 | substantially complicates the virtual memory allocation rules --- see below.) |
| 769 | |
| 770 | The memory manager deals with three kinds of object: |
| 771 | 1. "Small" objects. Typically these require no more than 10K-20K total. |
| 772 | 2. "Large" objects. These may require tens to hundreds of K depending on |
| 773 | image size. Semantically they behave the same as small objects, but we |
| 774 | distinguish them for two reasons: |
| 775 | * On MS-DOS machines, large objects are referenced by FAR pointers, |
| 776 | small objects by NEAR pointers. |
| 777 | * Pool allocation heuristics may differ for large and small objects. |
| 778 | Note that individual "large" objects cannot exceed the size allowed by |
| 779 | type size_t, which may be 64K or less on some machines. |
| 780 | 3. "Virtual" objects. These are large 2-D arrays of JSAMPLEs or JBLOCKs |
| 781 | (typically large enough for the entire image being processed). The |
| 782 | memory manager provides stripwise access to these arrays. On machines |
| 783 | without virtual memory, the rest of the array may be swapped out to a |
| 784 | temporary file. |
| 785 | |
| 786 | (Note: JSAMPARRAY and JBLOCKARRAY data structures are a combination of large |
| 787 | objects for the data proper and small objects for the row pointers. For |
| 788 | convenience and speed, the memory manager provides single routines to create |
| 789 | these structures. Similarly, virtual arrays include a small control block |
| 790 | and a JSAMPARRAY or JBLOCKARRAY working buffer, all created with one call.) |
| 791 | |
| 792 | In the present implementation, virtual arrays are only permitted to have image |
| 793 | lifespan. (Permanent lifespan would not be reasonable, and pass lifespan is |
| 794 | not very useful since a virtual array's raison d'etre is to store data for |
| 795 | multiple passes through the image.) We also expect that only "small" objects |
| 796 | will be given permanent lifespan, though this restriction is not required by |
| 797 | the memory manager. |
| 798 | |
| 799 | In a non-virtual-memory machine, some performance benefit can be gained by |
| 800 | making the in-memory buffers for virtual arrays be as large as possible. |
| 801 | (For small images, the buffers might fit entirely in memory, so blind |
| 802 | swapping would be very wasteful.) The memory manager will adjust the height |
| 803 | of the buffers to fit within a prespecified maximum memory usage. In order |
| 804 | to do this in a reasonably optimal fashion, the manager needs to allocate all |
| 805 | of the virtual arrays at once. Therefore, there isn't a one-step allocation |
| 806 | routine for virtual arrays; instead, there is a "request" routine that simply |
| 807 | allocates the control block, and a "realize" routine (called just once) that |
| 808 | determines space allocation and creates all of the actual buffers. The |
| 809 | realize routine must allow for space occupied by non-virtual large objects. |
| 810 | (We don't bother to factor in the space needed for small objects, on the |
| 811 | grounds that it isn't worth the trouble.) |
| 812 | |
| 813 | To support all this, we establish the following protocol for doing business |
| 814 | with the memory manager: |
| 815 | 1. Modules must request virtual arrays (which may have only image lifespan) |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 816 | during the initial setup phase, i.e., in their jinit_xxx routines. |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 817 | 2. All "large" objects (including JSAMPARRAYs and JBLOCKARRAYs) must also be |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 818 | allocated during initial setup. |
| 819 | 3. realize_virt_arrays will be called at the completion of initial setup. |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 820 | The above conventions ensure that sufficient information is available |
| 821 | for it to choose a good size for virtual array buffers. |
| 822 | Small objects of any lifespan may be allocated at any time. We expect that |
| 823 | the total space used for small objects will be small enough to be negligible |
| 824 | in the realize_virt_arrays computation. |
| 825 | |
| 826 | In a virtual-memory machine, we simply pretend that the available space is |
| 827 | infinite, thus causing realize_virt_arrays to decide that it can allocate all |
| 828 | the virtual arrays as full-size in-memory buffers. The overhead of the |
| 829 | virtual-array access protocol is very small when no swapping occurs. |
| 830 | |
Thomas G. Lane | bc79e06 | 1995-08-02 00:00:00 +0000 | [diff] [blame] | 831 | A virtual array can be specified to be "pre-zeroed"; when this flag is set, |
| 832 | never-yet-written sections of the array are set to zero before being made |
| 833 | available to the caller. If this flag is not set, never-written sections |
| 834 | of the array contain garbage. (This feature exists primarily because the |
| 835 | equivalent logic would otherwise be needed in jdcoefct.c for progressive |
| 836 | JPEG mode; we may as well make it available for possible other uses.) |
| 837 | |
| 838 | The first write pass on a virtual array is required to occur in top-to-bottom |
| 839 | order; read passes, as well as any write passes after the first one, may |
| 840 | access the array in any order. This restriction exists partly to simplify |
| 841 | the virtual array control logic, and partly because some file systems may not |
| 842 | support seeking beyond the current end-of-file in a temporary file. The main |
| 843 | implication of this restriction is that rearrangement of rows (such as |
| 844 | converting top-to-bottom data order to bottom-to-top) must be handled while |
| 845 | reading data out of the virtual array, not while putting it in. |
| 846 | |
Thomas G. Lane | 36a4ccc | 1994-09-24 00:00:00 +0000 | [diff] [blame] | 847 | |
| 848 | *** Memory manager internal structure *** |
| 849 | |
| 850 | To isolate system dependencies as much as possible, we have broken the |
| 851 | memory manager into two parts. There is a reasonably system-independent |
| 852 | "front end" (jmemmgr.c) and a "back end" that contains only the code |
| 853 | likely to change across systems. All of the memory management methods |
| 854 | outlined above are implemented by the front end. The back end provides |
| 855 | the following routines for use by the front end (none of these routines |
| 856 | are known to the rest of the JPEG code): |
| 857 | |
| 858 | jpeg_mem_init, jpeg_mem_term system-dependent initialization/shutdown |
| 859 | |
| 860 | jpeg_get_small, jpeg_free_small interface to malloc and free library routines |
| 861 | (or their equivalents) |
| 862 | |
| 863 | jpeg_get_large, jpeg_free_large interface to FAR malloc/free in MSDOS machines; |
| 864 | else usually the same as |
| 865 | jpeg_get_small/jpeg_free_small |
| 866 | |
| 867 | jpeg_mem_available estimate available memory |
| 868 | |
| 869 | jpeg_open_backing_store create a backing-store object |
| 870 | |
| 871 | read_backing_store, manipulate a backing-store object |
| 872 | write_backing_store, |
| 873 | close_backing_store |
| 874 | |
| 875 | On some systems there will be more than one type of backing-store object |
| 876 | (specifically, in MS-DOS a backing store file might be an area of extended |
| 877 | memory as well as a disk file). jpeg_open_backing_store is responsible for |
| 878 | choosing how to implement a given object. The read/write/close routines |
| 879 | are method pointers in the structure that describes a given object; this |
| 880 | lets them be different for different object types. |
| 881 | |
| 882 | It may be necessary to ensure that backing store objects are explicitly |
| 883 | released upon abnormal program termination. For example, MS-DOS won't free |
| 884 | extended memory by itself. To support this, we will expect the main program |
| 885 | or surrounding application to arrange to call self_destruct (typically via |
| 886 | jpeg_destroy) upon abnormal termination. This may require a SIGINT signal |
| 887 | handler or equivalent. We don't want to have the back end module install its |
| 888 | own signal handler, because that would pre-empt the surrounding application's |
| 889 | ability to control signal handling. |
| 890 | |
| 891 | The IJG distribution includes several memory manager back end implementations. |
| 892 | Usually the same back end should be suitable for all applications on a given |
| 893 | system, but it is possible for an application to supply its own back end at |
| 894 | need. |
| 895 | |
| 896 | |
| 897 | *** Implications of DNL marker *** |
| 898 | |
| 899 | Some JPEG files may use a DNL marker to postpone definition of the image |
| 900 | height (this would be useful for a fax-like scanner's output, for instance). |
| 901 | In these files the SOF marker claims the image height is 0, and you only |
| 902 | find out the true image height at the end of the first scan. |
| 903 | |
| 904 | We could read these files as follows: |
| 905 | 1. Upon seeing zero image height, replace it by 65535 (the maximum allowed). |
| 906 | 2. When the DNL is found, update the image height in the global image |
| 907 | descriptor. |
| 908 | This implies that control modules must avoid making copies of the image |
| 909 | height, and must re-test for termination after each MCU row. This would |
| 910 | be easy enough to do. |
| 911 | |
| 912 | In cases where image-size data structures are allocated, this approach will |
| 913 | result in very inefficient use of virtual memory or much-larger-than-necessary |
| 914 | temporary files. This seems acceptable for something that probably won't be a |
| 915 | mainstream usage. People might have to forgo use of memory-hogging options |
| 916 | (such as two-pass color quantization or noninterleaved JPEG files) if they |
| 917 | want efficient conversion of such files. (One could improve efficiency by |
| 918 | demanding a user-supplied upper bound for the height, less than 65536; in most |
| 919 | cases it could be much less.) |
| 920 | |
| 921 | The standard also permits the SOF marker to overestimate the image height, |
| 922 | with a DNL to give the true, smaller height at the end of the first scan. |
| 923 | This would solve the space problems if the overestimate wasn't too great. |
| 924 | However, it implies that you don't even know whether DNL will be used. |
| 925 | |
| 926 | This leads to a couple of very serious objections: |
| 927 | 1. Testing for a DNL marker must occur in the inner loop of the decompressor's |
| 928 | Huffman decoder; this implies a speed penalty whether the feature is used |
| 929 | or not. |
| 930 | 2. There is no way to hide the last-minute change in image height from an |
| 931 | application using the decoder. Thus *every* application using the IJG |
| 932 | library would suffer a complexity penalty whether it cared about DNL or |
| 933 | not. |
| 934 | We currently do not support DNL because of these problems. |
| 935 | |
| 936 | A different approach is to insist that DNL-using files be preprocessed by a |
| 937 | separate program that reads ahead to the DNL, then goes back and fixes the SOF |
| 938 | marker. This is a much simpler solution and is probably far more efficient. |
| 939 | Even if one wants piped input, buffering the first scan of the JPEG file needs |
| 940 | a lot smaller temp file than is implied by the maximum-height method. For |
| 941 | this approach we'd simply treat DNL as a no-op in the decompressor (at most, |
| 942 | check that it matches the SOF image height). |
| 943 | |
| 944 | We will not worry about making the compressor capable of outputting DNL. |
| 945 | Something similar to the first scheme above could be applied if anyone ever |
| 946 | wants to make that work. |