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