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