home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 11 Util / 11-Util.zip / xloadimg.zip / xloadimage.4.1 / jpeg / architecture < prev    next >
Text File  |  1992-12-02  |  67KB  |  1,196 lines

  1.  
  2.     JPEG SYSTEM ARCHITECTURE        1-DEC-92
  3.  
  4.  
  5. This file provides an overview of the "architecture" of the portable JPEG
  6. software; that is, the functions of the various modules in the system and the
  7. interfaces between modules.  For more precise details about any data structure
  8. or calling convention, see the header files.
  9.  
  10. Important note: when I say "module" I don't mean "a C function", which is what
  11. some people seem to think the term means.  A separate C source file is closer
  12. to the mark.  Also, it is frequently the case that several different modules
  13. present a common interface to callers; the term "object" or "method" refers to
  14. this common interface (see "Poor man's object-oriented programming", below).
  15.  
  16. JPEG-specific terminology follows the JPEG standard:
  17.   A "component" means a color channel, e.g., Red or Luminance.
  18.   A "sample" is a pixel component value (i.e., one number in the image data).
  19.   A "coefficient" is a frequency coefficient (a DCT transform output number).
  20.   The term "block" refers to an 8x8 group of samples or coefficients.
  21.   "MCU" (minimum coded unit) is the same as "MDU" of the R8 draft; i.e., an
  22.     interleaved set of blocks of size determined by the sampling factors,
  23.     or a single block in a noninterleaved scan.
  24.  
  25.  
  26. *** System requirements ***
  27.  
  28. We must support compression and decompression of both Huffman and
  29. arithmetic-coded JPEG files.  Any set of compression parameters allowed by the
  30. JPEG spec should be readable for decompression.  (We can be more restrictive
  31. about what formats we can generate.)  (Note: for legal reasons no arithmetic
  32. coding implementation is currently included in the publicly available sources.
  33. However, the architecture still supports it.)
  34.  
  35. We need to be able to handle both raw JPEG files (more specifically, the JFIF
  36. format) and JPEG-in-TIFF (C-cubed's format, and perhaps Kodak's).  Even if we
  37. don't implement TIFF ourselves, other people will want to use our code for
  38. that.  This means that generation and scanning of the file header has to be
  39. separated out.
  40.  
  41. Perhaps we should be prepared to support the JPEG lossless mode (also referred
  42. to in the spec as spatial DPCM coding).  A lot of people seem to believe they
  43. need this... whether they really do is debatable, but the customer is always
  44. right.  On the other hand, there will not be much sharable code between the
  45. lossless and lossy modes!  At best, a lossless program could be derived from
  46. parts of the lossy version.  For now we will only worry about the lossy mode.
  47.  
  48. I see no real value in supporting the JPEG progressive modes (note that
  49. spectral selection and successive approximation are two different progressive
  50. modes).  These are only of interest when painting the decompressed image in
  51. real-time, which nobody is going to do with a pure software implementation.
  52.  
  53. There is some value in supporting the hierarchical mode, which allows for
  54. successive frames of higher resolution.  This could be of use for including
  55. "thumbnail" representations.  However, this appears to add a lot more
  56. complexity than it is worth.
  57.  
  58. A variety of uncompressed image file formats and user interfaces must be
  59. supported.  These aspects therefore have to be kept separate from the rest of
  60. the system.  A particularly important issue is whether color quantization of
  61. the output is needed (i.e., whether a colormap is used).  We should be able to
  62. support both adaptive quantization (which requires two or more passes over the
  63. image) and nonadaptive (quantization to a prespecified colormap, which can be
  64. done in one pass).
  65.  
  66. Memory usage is an important concern, since we will port this code to 80x86
  67. and other limited-memory machines.  For large intermediate structures, we
  68. should be able to use either virtual memory or temporary files.
  69.  
  70. It should be possible to build programs that handle compression only,
  71. decompression only, or both, without much duplicate or unused code in any
  72. version.  (In particular, a decompression-only version should have no extra
  73. baggage.)
  74.  
  75.  
  76. *** Compression overview ***
  77.  
  78. The *logical* steps needed in (non-lossless) JPEG compression are:
  79.  
  80. 1. Conversion from incoming image format to a standardized internal form
  81.    (either RGB or grayscale).
  82.  
  83. 2. Color space conversion (e.g., RGB to YCbCr).  This is a null step for
  84.    grayscale (unless we support mapping color inputs to grayscale, which
  85.    would most easily be done here).  Gamma adjustment may also be needed here.
  86.  
  87. 3. Downsampling (reduction of number of samples in some color components).
  88.    This step operates independently on each color component.
  89.  
  90. 4. MCU extraction (creation of a single sequence of 8x8 sample blocks).
  91.    This step and the following ones are performed once for each scan
  92.    in the output JPEG file, i.e., once if making an interleaved file and more
  93.    than once for a noninterleaved file.
  94.    Note: both this step and the previous one must deal with edge conditions
  95.    for pictures that aren't a multiple of the MCU dimensions.  Alternately,
  96.    we could expand the picture to a multiple of an MCU before doing these
  97.    two steps.  (The latter seems better and has been adopted below.)
  98.  
  99. 5. DCT transformation of each 8x8 block.
  100.  
  101. 6. Quantization scaling and zigzag reordering of the elements in each 8x8
  102.    block.
  103.  
  104. 7. Huffman or arithmetic encoding of the transformed block sequence.
  105.  
  106. 8. Output of the JPEG file with whatever headers/markers are wanted.
  107.  
  108. Of course, the actual implementation will combine some of these logical steps
  109. for efficiency.  The trick is to keep these logical functions as separate as
  110. possible without losing too much performance.
  111.  
  112. In addition to these logical pipeline steps, we need various modules that
  113. aren't part of the data pipeline.  These are:
  114.  
  115. A. Overall control (sequencing of other steps & management of data passing).
  116.  
  117. B. User interface; this will determine the input and output files, and supply
  118.    values for some compression parameters.  Note that this module is highly
  119.    platform-dependent.
  120.  
  121. C. Compression parameter selection: some parameters should be chosen
  122.    automatically rather than requiring the user to find a good value.
  123.    The prototype only does this for the back-end (Huffman or arithmetic)
  124.    parameters, but further in the future, more might be done.  A
  125.    straightforward approach to selection is to try several values; this
  126.    requires being able to repeatedly apply some portion of the pipeline and
  127.    inspect the results (without actually outputting them).  Probably only
  128.    entropy encoding parameters can reasonably be done this way; optimizing
  129.    earlier steps would require too much data to be reprocessed (not to mention
  130.    the problem of interactions between parameters for different steps).
  131.    What other facilities do we need to support automatic parameter selection?
  132.  
  133. D. A memory management module to deal with small-memory machines.  This must
  134.    create the illusion of virtual memory for certain large data structures
  135.    (e.g., the downsampled image or the transformed coefficients).
  136.    The interface to this must be defined to minimize the overhead incurred,
  137.    especially on virtual-memory machines where the module won't do much.
  138.  
  139. In many cases we can arrange things so that a data stream is produced in
  140. segments by one module and consumed by another without the need to hold it all
  141. in (virtual) memory.  This is obviously not possible for any data that must be
  142. scanned more than once, so it won't work everywhere.
  143.  
  144. The major variable at this level of detail is whether the JPEG file is to be
  145. interleaved or not; that affects the order of processing so fundamentally that
  146. the central control module must know about it.  Some of the other modules may
  147. need to know it too.  It would simplify life if we didn't need to support
  148. noninterleaved images, but that is not reasonable.
  149.  
  150. Many of these steps operate independently on each color component; the
  151. knowledge of how many components there are, and how they are interleaved,
  152. ought to be confined to the central control module.  (Color space conversion
  153. and MCU extraction probably have to know it too.)
  154.  
  155.  
  156. *** Decompression overview ***
  157.  
  158. Decompression is roughly the inverse process from compression, but there are
  159. some additional steps needed to produce a good output image.
  160.  
  161. The *logical* steps needed in (non-lossless) JPEG decompression are:
  162.  
  163. 1. Scanning of the JPEG file, decoding of headers/markers etc.
  164.  
  165. 2. Huffman or arithmetic decoding of the coefficient sequence.
  166.  
  167. 3. Quantization descaling and zigzag reordering of the elements in each 8x8
  168.    block.
  169.  
  170. 4. MCU disassembly (conversion of a possibly interleaved sequence of 8x8
  171.    blocks back to separate components in pixel map order).
  172.  
  173. 5. (Optional)  Cross-block smoothing per JPEG section K.8 or a similar
  174.    algorithm.  (Steps 5-8 operate independently on each component.)
  175.  
  176. 6. Inverse DCT transformation of each 8x8 block.
  177.  
  178. 7. Upsampling.  At this point a pixel image of the original dimensions
  179.    has been recreated.
  180.  
  181. 8. Post-upsampling smoothing.  This can be combined with upsampling,
  182.    by using a convolution-like calculation to generate each output pixel
  183.    directly from one or more input pixels.
  184.  
  185. 9. Cropping to the original pixel dimensions (throwing away duplicated
  186.    pixels at the edges).  It is most convenient to do this now, as the
  187.    preceding steps are simplified by not having to worry about odd picture
  188.    sizes.
  189.  
  190. 10. Color space reconversion (e.g., YCbCr to RGB).  This is a null step for
  191.     grayscale.  (Note that mapping a color JPEG to grayscale output is most
  192.     easily done in this step.)  Gamma adjustment may also be needed here.
  193.  
  194. 11. Color quantization (only if a colormapped output format is requested).
  195.     NOTE: it is probably preferable to perform quantization in the internal
  196.     (JPEG) colorspace rather than the output colorspace.  Doing it that way,
  197.     color conversion need only be applied to the colormap entries, not to
  198.     every pixel; and quantization gets to operate in a non-gamma-corrected
  199.     space.  But the internal space may not be suitable for some algorithms.
  200.     The system design is such that only the color quantizer module knows
  201.     whether color conversion happens before or after quantization.
  202.  
  203. 12. Writing of the desired image format.
  204.  
  205. As before, some of these will be combined into single steps.  When dealing
  206. with a noninterleaved JPEG file, steps 2-9 will be performed once for each
  207. scan; the resulting data will need to be buffered up so that steps 10-12 can
  208. process all the color components together.
  209.  
  210. The same auxiliary modules are needed as before, except for compression
  211. parameter selection.  Note that rerunning a pipeline stage should never be
  212. needed during decompression.  This may allow a simpler control module.  The
  213. user interface might also be simpler since it need not supply any compression
  214. parameters.
  215.  
  216. As before, not all of these steps require the whole image to be stored.
  217. Actually, two-pass color quantization is the only step that logically requires
  218. this; everything else could be done a few raster lines at a time (at least for
  219. interleaved images).  We might want to make color quantization be a separate
  220. program because of this fact.
  221.  
  222. Again, many of the steps should be able to work on one color component in
  223. ignorance of the other components.
  224.  
  225.  
  226. *** Implications of noninterleaved formats ***
  227.  
  228. Much of the work can be done in a single pass if an interleaved JPEG file
  229. format is used.  With a noninterleaved JPEG file, separating or recombining
  230. the components will force use of virtual memory (on a small-memory machine,
  231. we probably would want one temp file per color component).
  232.  
  233. If any of the image formats we read or write are noninterleaved, the opposite
  234. condition might apply: processing a noninterleaved JPEG file would be more
  235. efficient.  Offhand, though, I can't think of any popular image formats that
  236. work that way; besides the win would only come if the same color space were
  237. used in JPEG and non-JPEG files.  It's not worth the complexity to make the
  238. system design accommodate that case efficiently.
  239.  
  240. An argument against interleaving is that it makes the decompressor need more
  241. memory for cross-block smoothing (since the minimum processable chunk of the
  242. image gets bigger).  With images more than 1000 pixels across, 80x86 machines
  243. are likely to have difficulty in handling this feature.
  244.  
  245. Another argument against interleaving is that the noninterleaved format allows
  246. a wider range of sampling factors, since the limit of ten blocks per MCU no
  247. longer applies.  We could get around this by blithely ignoring the spec's
  248. limit of ten blocks, but that seems like a bad idea (especially since it makes
  249. the above problem worse).
  250.  
  251. The upshot is that we need to support both interleaved and noninterleaved JPEG
  252. formats, since for any given machine and picture size one may be much more
  253. efficient than the other.  However, the non-JPEG format we convert to or from
  254. will be assumed to be an interleaved format (i.e., it produces or stores all
  255. the components of a pixel together).
  256.  
  257. I do not think it is necessary for the compressor to be able to output
  258. partially-interleaved formats (multiple scans, some of which interleave a
  259. subset of the components).  However, the decompressor must be able to read
  260. such files to conform to the spec.
  261.  
  262.  
  263. *** Data formats ***
  264.  
  265. Pipeline steps that work on pixel sample values will use the following data
  266. structure:
  267.  
  268.     typedef something JSAMPLE;        a pixel component value, 0..MAXJSAMPLE
  269.     typedef JSAMPLE *JSAMPROW;        ptr to a row of samples
  270.     typedef JSAMPROW *JSAMPARRAY;    ptr to a list of rows
  271.     typedef JSAMPARRAY *JSAMPIMAGE;    ptr to a list of color-component arrays
  272.  
  273. The basic element type JSAMPLE will be one of unsigned char, (signed) char, or
  274. unsigned short.  Unsigned short will be used if samples wider than 8 bits are
  275. to be supported (this is a compile-time option).  Otherwise, unsigned char is
  276. used if possible.  If the compiler only supports signed chars, then it is
  277. necessary to mask off the value when reading.  Thus, all reads of sample
  278. values should be coded as "GETJSAMPLE(value)", where the macro will be defined
  279. as "((value)&0xFF)" on signed-char machines and "(value)" elsewhere.
  280.  
  281. With these conventions, JSAMPLE values can be assumed to be >= 0.  This should
  282. simplify correct rounding during downsampling, etc.  The JPEG draft's
  283. specification that sample values run from -128..127 will be accommodated by
  284. subtracting 128 just as the sample value is copied into the source array for
  285. the DCT step (this will be an array of signed shorts or longs).  Similarly,
  286. during decompression the output of the IDCT step will be immediately shifted
  287. back to 0..255.  (NB: different values are required when 12-bit samples are in
  288. use.  The code should be written in terms of MAXJSAMPLE and CENTERJSAMPLE,
  289. which will be #defined as 255 and 128 respectively in an 8-bit implementation,
  290. and as 4095 and 2048 in a 12-bit implementation.)
  291.  
  292. On compilers that don't support "unsigned short", signed short can be used for
  293. a 12-bit implementation.  To support lossless coding (which allows up to
  294. 16-bit data precision) masking with 0xFFFF in GETJSAMPLE might be necessary.
  295. (But if "int" is 16 bits then using "unsigned int" is the best solution.)
  296.  
  297. Notice that we use a pointer per row, rather than a two-dimensional JSAMPLE
  298. array.  This choice costs only a small amount of memory and has several
  299. benefits:
  300.  
  301. * Code using the data structure doesn't need to know the allocated width of
  302. the rows.  This will simplify edge expansion/compression, since we can work
  303. in an array that's wider than the logical picture width.
  304.  
  305. * The rows forming a component array may be allocated at different times
  306. without extra copying.  This will simplify working a few scanlines at a time,
  307. especially in smoothing steps that need access to the previous and next rows.
  308.  
  309. * Indexing doesn't require multiplication; this is a performance win on many
  310. machines.
  311.  
  312. Note that each color component is stored in a separate array; we don't use the
  313. traditional structure in which the components of a pixel are stored together.
  314. This simplifies coding of steps that work on each component independently,
  315. because they don't need to know how many components there are.  Furthermore,
  316. we can read or write each component to a temp file independently, which is
  317. helpful when dealing with noninterleaved JPEG files.
  318.  
  319. A specific sample value will be accessed by code such as
  320.     GETJSAMPLE(image[colorcomponent][row][col])
  321. where col is measured from the image left edge, but row is measured from the
  322. first sample row currently in memory.  Either of the first two indexings can
  323. be precomputed by copying the relevant pointer.
  324.  
  325.  
  326. Pipeline steps that work on frequency-coefficient values will use the
  327. following data structure:
  328.  
  329.     typedef short JCOEF;        a 16-bit signed integer
  330.     typedef JCOEF JBLOCK[64];        an 8x8 block of coefficients
  331.     typedef JBLOCK *JBLOCKROW;        ptr to one horizontal row of 8x8 blocks
  332.     typedef JBLOCKROW *JBLOCKARRAY;    ptr to a list of such rows
  333.     typedef JBLOCKARRAY *JBLOCKIMAGE;    ptr to a list of color component arrays
  334.  
  335. The underlying type is always a 16-bit signed integer (this is "short" on all
  336. machines of interest, but let's use the typedef name anyway).  These are
  337. grouped into 8x8 blocks (we should use #defines DCTSIZE and DCTSIZE2 rather
  338. than "8" and "64").  The contents of a block may be either in "natural" or
  339. zigzagged order, and may be true values or divided by the quantization
  340. coefficients, depending on where the block is in the pipeline.
  341.  
  342. Notice that the allocation unit is now a row of 8x8 blocks, corresponding to
  343. eight rows of samples.  Otherwise the structure is much the same as for
  344. samples, and for the same reasons.
  345.  
  346. On machines where malloc() can't handle a request bigger than 64Kb, this data
  347. structure limits us to rows of less than 512 JBLOCKs, which would be a picture
  348. width of 4000 pixels.  This seems an acceptable restriction.
  349.  
  350.  
  351. On 80x86 machines, the bottom-level pointer types (JSAMPROW and JBLOCKROW)
  352. must be declared as "far" pointers, but the upper levels can be "near"
  353. (implying that the pointer lists are allocated in the DS segment).
  354. To simplify sharing code, we'll have a #define symbol FAR, which expands to
  355. the "far" keyword when compiling on 80x86 machines and to nothing elsewhere.
  356.  
  357.  
  358. The data arrays used as input and output of the DCT transform subroutine will
  359. be declared using a separate typedef; they could be arrays of "short", "int"
  360. or "long" independently of the above choices.  This would depend on what is
  361. needed to make the compiler generate correct and efficient multiply/add code
  362. in the DCT inner loops.  No significant speed or memory penalty will be paid
  363. to have a different representation than is used in the main image storage
  364. arrays, since some additional value-by-value processing is done at the time of
  365. creation or extraction of the DCT data anyway (e.g., add/subtract 128).
  366.  
  367.  
  368. *** Poor man's object-oriented programming ***
  369.  
  370. It should be pretty clear by now that we have a lot of quasi-independent
  371. steps, many of which have several possible behaviors.  To avoid cluttering the
  372. code with lots of switch statements, we'll use a simple form of object-style
  373. programming to separate out the different possibilities.
  374.  
  375. For example, Huffman and arithmetic coding will be implemented as two separate
  376. modules that present the same external interface; at runtime, the calling code
  377. will access the proper module indirectly through an "object".
  378.  
  379. We can get the limited features we need while staying within portable C.  The
  380. basic tool is a function pointer.  An "object" is just a struct containing one
  381. or more function pointer fields, each of which corresponds to a method name in
  382. real object-oriented languages.  During initialization we fill in the function
  383. pointers with references to whichever module we have determined we need to use
  384. in this run.  Then invocation of the module is done by indirecting through a
  385. function pointer; on most architectures this is no more expensive (and
  386. possibly cheaper) than a switch, which would be the only other way of making
  387. the required run-time choice.  The really significant benefit, of course, is
  388. keeping the source code clean and well structured.
  389.  
  390. For example, the interface for entropy decoding (Huffman or arithmetic
  391. decoding) might look like this:
  392.  
  393.     struct function_ptr_struct {
  394.         ...
  395.         /* Entropy decoding methods */
  396.         void (*prepare_for_scan) ();
  397.         void (*get_next_mcu) ();
  398.         ...
  399.         };
  400.  
  401.     typedef struct function_ptr_struct * function_ptrs;
  402.  
  403. The struct pointer is what will actually be passed around.  A call site might
  404. look like this:
  405.  
  406.     some_function (function_ptrs fptrs)
  407.         {
  408.         ...
  409.         (*fptrs->get_next_mcu) (...);
  410.         ...
  411.         }
  412.  
  413. (It might be worth inventing some specialized macros to hide the rather ugly
  414. syntax for method definition and call.)  Note that the caller doesn't know how
  415. many different get_next_mcu procedures there are, what their real names are,
  416. nor how to choose which one to call.
  417.  
  418. An important benefit of this scheme is that it is easy to provide multiple
  419. versions of any method, each tuned to a particular case.  While a lot of
  420. precalculation might be done to select an optimal implementation of a method,
  421. the cost per invocation is constant.  For example, the MCU extraction step
  422. might have a "generic" method, plus one or more "hardwired" methods for the
  423. most popular sampling factors; the hardwired methods would be faster because
  424. they'd use straight-line code instead of for-loops.  The cost to determine
  425. which method to use is paid only once, at startup, and the selection criteria
  426. are hidden from the callers of the method.
  427.  
  428. This plan differs a little bit from usual object-oriented structures, in that
  429. only one instance of each object class will exist during execution.  The
  430. reason for having the class structure is that on different runs we may create
  431. different instances (choose to execute different modules).
  432.  
  433. To minimize the number of object pointers that have to be passed around, it
  434. will be easiest to have just a few big structs containing all the method
  435. pointers.  We'll actually use two such structs, one for "system-dependent"
  436. methods (memory allocation and error handling) and one for everything else.
  437.  
  438. Because of this choice, it's best not to think of an "object" as a specific
  439. data structure.  Rather, an "object" is just a group of related methods.
  440. There would typically be one or more C modules (source files) providing
  441. concrete implementations of those methods.  You can think of the term
  442. "method" as denoting the common interface presented by some set of functions,
  443. and "object" as denoting a group of common method interfaces, or the total
  444. shared interface behavior of a group of modules.
  445.  
  446.  
  447. *** Data chunk sizes ***
  448.  
  449. To make the cost of this object-oriented style really minimal, we should make
  450. sure that each method call does a fair amount of computation.  To do that we
  451. should pass large chunks of data around; for example, the colorspace
  452. conversion method should process much more than one pixel per call.
  453.  
  454. For many steps, the most natural unit of data seems to be an "MCU row".
  455. This consists of one complete horizontal strip of the image, as high as an
  456. MCU.  In a noninterleaved scan, an MCU row is always eight samples high (when
  457. looking at samples) or one 8x8 block high (when looking at coefficients).  In
  458. an interleaved scan, an MCU row consists of all the data for one horizontal
  459. row of MCUs; this may be from one to four blocks high (eight to thirty-two
  460. samples) depending on the sampling factors.  The height and width of an MCU
  461. row may be different in each component.  (Note that the height and width of an
  462. MCU row changes at the downsampling and upsampling steps.  An unsubsampled
  463. image has the same size in each component.  The preceding statements apply to
  464. the downsampled dimensions.)
  465.  
  466. For example, consider a 1024-pixel-wide image using (2h:2v)(1h:1v)(1h:1v)
  467. subsampling.  In the noninterleaved case, an MCU row of Y would contain 8x1024
  468. samples or the same number of frequency coefficients, so it would occupy
  469. 8K bytes (samples) or 16K bytes (coefficients).  An MCU row of Cb or Cr would
  470. contain 8x512 samples and occupy half as much space.  In the interleaved case,
  471. an MCU row would contain 16x1024 Y samples, 8x512 Cb and 8x512 Cr samples, so
  472. a total of 24K (samples) or 48K (coefficients) would be needed.  This is a
  473. reasonable amount of data to expect to retain in memory at one time.  (Bear in
  474. mind that we'll usually need to have several MCU rows resident in memory at
  475. once, at the inputs and outputs to various pipeline steps.)
  476.  
  477. The worst case is probably (2h:4v)(1h:1v)(1h:1v) interleaving (this uses 10
  478. blocks per MCU, which is the maximum allowed by the spec).  An MCU will then
  479. contain 32 sample rows worth of Y, so it would occupy 40K or 80K bytes for a
  480. 1024-pixel-wide image.  The most memory-intensive step is probably cross-block
  481. smoothing, for which we'd need 3 MCU rows of coefficients as input and another
  482. one as output; that would be 320K of working storage.  Anything much larger
  483. would not fit in an 80x86 machine.  (To decompress wider pictures on an 80x86,
  484. we'll have to skip cross-block smoothing or else use temporary files.)
  485.  
  486. This unit is thus a reasonable-sized chunk for passing through the pipeline.
  487. Of course, its major advantage is that it is a natural chunk size for the MCU
  488. assembly and disassembly steps to work with.
  489.  
  490. For the entropy (Huffman or arithmetic) encoding/decoding steps, the most
  491. convenient chunk is a single MCU: one 8x8 block if not interleaved, three to
  492. ten such blocks if interleaved.  The advantage of this is that when handling
  493. interleaved data, the blocks have the same sequence of component membership on
  494. each call.  (For example, Y,Y,Y,Y,Cb,Cr when using (2h:2v)(1h:1v)(1h:1v)
  495. subsampling.)  The code needs to know component membership so that it can
  496. apply the right set of compression coefficients to each block.  A prebuilt
  497. array describing this membership can be used during each call.  This chunk
  498. size also makes it easy to handle restart intervals: just count off one MCU
  499. per call and reinitialize when the count reaches zero (restart intervals are
  500. specified in numbers of MCU).
  501.  
  502. For similar reasons, one MCU is also the best chunk size for the frequency
  503. coefficient quantization and dequantization steps.
  504.  
  505. For downsampling and upsampling, the best chunk size is to have each call
  506. transform Vk sample rows from or to Vmax sample rows (Vk = this component's
  507. vertical sampling factor, Vmax = largest vertical sampling factor).  There are
  508. eight such chunks in each MCU row.  Using a whole MCU row as the chunk size
  509. would reduce function call overhead a fraction, but would imply more buffering
  510. to provide context for cross-pixel smoothing.
  511.  
  512.  
  513. *** Compression object structure ***
  514.  
  515. I propose the following set of objects for the compressor.  Here an "object"
  516. is the common interface for one or more modules having comparable functions.
  517.  
  518. Most of these objects can be justified as information-hiding modules.
  519. I've indicated what information is private to each object/module.
  520.  
  521. Note that in all cases, the caller of a method is expected to have allocated
  522. any storage needed for it to return its result.  (Typically this storage can
  523. be re-used in successive calls, so malloc'ing and free'ing once per call is
  524. not reasonable.)  Also, much of the context required (compression parameters,
  525. image size, etc) will be passed around in large common data structures, which
  526. aren't described here; see the header files.  Notice that any object that
  527. might need to allocate working storage receives an "init" and a "term" call;
  528. "term" should be careful to free all allocated storage so that the JPEG system
  529. can be used multiple times during a program run.  (For the same reason,
  530. depending on static initialization of variables is a no-no.  The only
  531. exception to the free-all-allocated-storage rule is that storage allocated for
  532. the entire processing of an image need not be explicitly freed, since the
  533. memory manager's free_all cleanup will free it.)
  534.  
  535. 1. Input file conversion to standardized form.  This provides these methods:
  536.     input_init: read the file header, report image size & component count.
  537.     get_input_row: read one pixel row, return it in our standard format.
  538.     input_term: finish up at the end.
  539.    In implementations that support multiple input formats, input_init could
  540.    set up an appropriate get_input_row method depending on the format it
  541.    finds.  Note that in most applications, the selection and opening of the
  542.    input file will be under the control of the user interface module; and
  543.    indeed the user interface may have already read the input header, so that
  544.    all that input_init may have to do is return previously saved values.  The
  545.    behind-the-scenes interaction between this object and the user interface is
  546.    not specified by this architecture.
  547.    (Hides format of input image and mechanism used to read it.  This code is
  548.    likely to vary considerably from one implementation to another.  Note that
  549.    the color space and number of color components of the source are not hidden;
  550.    but they are used only by the next object.)
  551.  
  552. 2. Gamma and color space conversion.  This provides three methods:
  553.     colorin_init: initialization.
  554.     get_sample_rows: read, convert, and return a specified number of pixel
  555.              rows (not more than remain in the picture).
  556.     colorin_term: finish up at the end.
  557.    The most efficient approach seems to be for this object to call
  558.    get_input_row directly, rather than being passed the input data; that way,
  559.    any intermediate storage required can be local to this object.
  560.    (get_sample_rows might tell get_input_row to read directly into its own
  561.    output area and then convert in place; or it may do something different.
  562.    For example, conversion in place wouldn't work if it is changing the number
  563.    of color components.)  The output of this step is in the standardized
  564.    sample array format shown previously.
  565.    (Hides all knowledge of color space semantics and conversion.  Remaining
  566.    modules only need to know the number of JPEG components.)
  567.  
  568. 3. Edge expansion: needs only a single method.
  569.     edge_expand: Given an NxM sample array, expand to a desired size (a
  570.              multiple of the MCU dimensions) by duplicating the last
  571.              row or column.  Repeat for each component.
  572.    Expansion will occur in place, so the caller must have pre-allocated enough
  573.    storage.  (I'm assuming that it is easier and faster to do this expansion
  574.    than it is to worry about boundary conditions in the next two steps.
  575.    Notice that vertical expansion will occur only once, at the bottom of the
  576.    picture, so only horizontal expansion by a few pixels is speed-critical.)
  577.    (This doesn't really hide any information, so maybe it could be a simple
  578.    subroutine instead of a method.  Depends on whether we want to be able to
  579.    use alternative, optimized methods.)
  580.  
  581. 4. Downsampling: this will be applied to one component at a time.
  582.     downsample_init: initialize (precalculate convolution factors, for
  583.              example).  This will be called once per scan.
  584.     downsample: Given a sample array, reduce it to a smaller number of
  585.             samples using specified sampling factors.
  586.     downsample_term: clean up at the end of a scan.
  587.    If the current component has vertical sampling factor Vk and the largest
  588.    sampling factor is Vmax, then the input is always Vmax sample rows (whose
  589.    width is a multiple of Hmax) and the output is always Vk sample rows.
  590.    Vmax additional rows above and below the nominal input rows are also passed
  591.    for use by partial-pixel-averaging sampling methods.  (Is this necessary?)
  592.    At the top and bottom of the image, these extra rows are copies of the
  593.    first or last actual input row.
  594.    (This hides whether and how cross-pixel averaging occurs.)
  595.  
  596. 5. MCU extraction (creation of a single sequence of 8x8 sample blocks).
  597.     extract_init: initialize as needed.  This will be called once per scan.
  598.     extract_MCUs: convert a sample array to a sequence of MCUs.
  599.     extract_term: clean up at the end of a scan.
  600.    Given one or more MCU rows worth of image data, extract sample blocks in the
  601.    appropriate order; pass these off to subsequent steps one MCU at a time.
  602.    The input must be a multiple of the MCU dimensions.  It will probably be
  603.    most convenient for the DCT transform, frequency quantization, and zigzag
  604.    reordering of each block to be done as simple subroutines of this step.
  605.    Once a transformed MCU has been completed, it'll be passed off to a
  606.    method call, which will be passed as a parameter to extract_MCUs.
  607.    That routine might either encode and output the MCU immediately, or buffer
  608.    it up for later output if we want to do global optimization of the entropy
  609.    encoding coefficients.  Note: when outputting a noninterleaved file this
  610.    object will be called separately for each component.  Direct output could
  611.    be done for the first component, but the others would have to be buffered.
  612.    (Again, an object mainly on the grounds that multiple instantiations might
  613.    be useful.)
  614.  
  615. 6. DCT transformation of each 8x8 block.  This probably doesn't have to be a
  616.    full-fledged method, but just a plain subroutine that will be called by MCU
  617.    extraction.  One 8x8 block will be processed per call.
  618.  
  619. 7. Quantization scaling and zigzag reordering of the elements in each 8x8
  620.    block.  (This can probably be a plain subroutine called once per block by
  621.    MCU extraction; hard to see a need for multiple instantiations here.)
  622.  
  623. 8. Entropy encoding (Huffman or arithmetic).
  624.     entropy_encode_init: prepare for one scan.
  625.     entropy_encode: accepts an MCU's worth of quantized coefficients,
  626.             encodes and outputs them.
  627.     entropy_encode_term: finish up at end of a scan (dump any buffered
  628.                  bytes, for example).
  629.    The data output by this module will be sent to the entropy_output method
  630.    provided by the pipeline controller.  (It will probably be worth using
  631.    buffering to pass multiple bytes per call of the output method.)  The
  632.    output method could be just write_jpeg_data, but might also be a dummy
  633.    routine that counts output bytes (for use during cut-and-try coefficient
  634.    optimization).
  635.    (This hides which entropy encoding method is in use.)
  636.  
  637. 9. JPEG file header construction.  This will provide these methods:
  638.     write_file_header: output the initial header.
  639.     write_scan_header: output scan header (called once per component
  640.                if noninterleaved mode).
  641.     write_jpeg_data: the actual data output method for the preceding step.
  642.     write_scan_trailer: finish up after one scan.
  643.     write_file_trailer: finish up at end of file.
  644.    Note that compressed data is passed to the write_jpeg_data method, in case
  645.    a simple fwrite isn't appropriate for some reason.
  646.    (This hides which variant JPEG file format is being written.  Also, the
  647.    actual mechanism for writing the file is private to this object and the
  648.    user interface.)
  649.  
  650. 10. Pipeline control.  This object will provide the "main loop" that invokes
  651.     all the pipeline objects.  Note that we will need several different main
  652.     loops depending on the situation (interleaved output or not, global
  653.     optimization of encoding parameters or not, etc).  This object will do
  654.     most of the memory allocation, since it will provide the working buffers
  655.     that are the inputs and outputs of the pipeline steps.
  656.     (An object mostly to support multiple instantiations; however, overall
  657.     memory management and sequencing of operations are known only here.)
  658.  
  659. 11. Overall control.  This module will provide at least two routines:
  660.     jpeg_compress: the main entry point to the compressor.
  661.     per_scan_method_selection: called by pipeline controllers for
  662.                    secondary method selection passes.
  663.     jpeg_compress is invoked from the user interface after the UI has selected
  664.     the input and output files and obtained values for all compression
  665.     parameters that aren't dynamically determined.  jpeg_compress performs
  666.     basic initialization (e.g., calculating the size of MCUs), does the
  667.     "global" method selection pass, and finally calls the selected pipeline
  668.     control object.  (Per-scan method selections will be invoked by the
  669.     pipeline controller.)
  670.     Note that jpeg_compress can't be a method since it is invoked prior to
  671.     method selection.
  672.  
  673. 12. User interface; this is the architecture's term for "the rest of the
  674.     application program", i.e., that which invokes the JPEG compressor.  In a
  675.     standalone JPEG compression program the UI need be little more than a C
  676.     main() routine and argument parsing code; but we can expect that the JPEG
  677.     compressor may be incorporated into complex graphics applications, wherein
  678.     the UI is much more complex.  Much of the UI will need to be written
  679.     afresh for each non-Unix-like platform the compressor is ported to.
  680.     The UI is expected to supply input and output files and values for all
  681.     non-automatically-chosen compression parameters.  (Hence defaults are
  682.     determined by the UI; we should provide helpful routines to fill in
  683.     the recommended defaults.)  The UI must also supply error handling
  684.     routines and some mechanism for trace messages.
  685.     (This module hides the user interface provided --- command line,
  686.     interactive, etc.  Except for error/message handling, the UI calls the
  687.     portable JPEG code, not the other way around.)
  688.  
  689. 13. (Optional) Compression parameter selection control.
  690.     entropy_optimize: given an array of MCUs ready to be fed to entropy
  691.               encoding, find optimal encoding parameters.
  692.     The actual optimization algorithm ought to be separated out as an object,
  693.     even though a special pipeline control method will be needed.  (The
  694.     pipeline controller only has to understand that the output of extract_MCUs
  695.     must be built up as a virtual array rather than fed directly to entropy
  696.     encoding and output.  This pipeline behavior may also be useful for future
  697.     implementation of hierarchical modes, etc.)
  698.     To minimize the amount of control logic in the optimization module, the
  699.     pipeline control doesn't actually hand over big-array pointers, but rather
  700.     an "iterator": a function which knows how to scan the stored image.
  701.     (This hides the details of the parameter optimization algorithm.)
  702.  
  703.     The present design doesn't allow for multiple passes at earlier points
  704.     in the pipeline, but allowing that would only require providing some
  705.     new pipeline control methods; nothing else need change.
  706.  
  707. 14. A memory management object.  This will provide methods to allocate "small"
  708.     things and "big" things.  Small things have to fit in memory and you get
  709.     back direct pointers (this could be handled by direct calls to malloc, but
  710.     it's cleaner not to assume malloc is the right routine).  "Big" things
  711.     mean buffered images for multiple passes, noninterleaved output, etc.
  712.     In this case the memory management object will give you room for a few MCU
  713.     rows and you have to ask for access to the next few; dumping and reloading
  714.     in a temporary file will go on behind the scenes.  (All big objects are
  715.     image arrays containing either samples or coefficients, and will be
  716.     scanned top-to-bottom some number of times, so we can apply this access
  717.     model easily.)  On a platform with virtual memory, the memory manager can
  718.     treat small and big things alike: just malloc up enough virtual memory for
  719.     the whole image, and let the operating system worry about swapping the
  720.     image to disk.
  721.  
  722.     Most of the actual calls on the memory manager will be made from pipeline
  723.     control objects; changing any data item from "small" to "big" status would
  724.     require a new pipeline control object, since it will contain the logic to
  725.     ask for a new chunk of a big thing.  Thus, one way in which pipeline
  726.     controllers will vary is in which structures they treat as big.
  727.  
  728.     The memory manager will need to be told roughly how much space is going to
  729.     be requested overall, so that it can figure out how big a buffer is safe
  730.     to allocate for a "big" object.  (If it happens that you are dealing with
  731.     a small image, you'd like to decide to keep it all in memory!)  The most
  732.     flexible way of doing this is to divide allocation of "big" objects into
  733.     two steps.  First, there will be one or more "request" calls that indicate
  734.     the desired object sizes; then an "instantiate" call causes the memory
  735.     manager to actually construct the objects.  The instantiation must occur
  736.     before the contents of any big object can be accessed.
  737.  
  738.     For 80x86 CPUs, we would like the code to be compilable under small or
  739.     medium model, meaning that pointers are 16 bits unless explicitly declared
  740.     FAR.  Hence space allocated by the "small" allocator must fit into the
  741.     64Kb default data segment, along with stack space and global/static data.
  742.     For normal JPEG operations we seem to need only about 32Kb of such space,
  743.     so we are within the target (and have a reasonable slop for the needs of
  744.     a surrounding application program).  However, some color quantization
  745.     algorithms need 64Kb or more of all-in-memory space in order to create
  746.     color histograms.  For this purpose, we will also support "medium" size
  747.     things.  These are semantically the same as "small" things but are
  748.     referenced through FAR pointers.
  749.  
  750.     The following methods will be needed:
  751.     alloc_small:    allocate an object of given size; use for any random
  752.             data that's not an image array.
  753.     free_small:    release same.
  754.     alloc_medium:    like alloc_small, but returns a FAR pointer.  Use for
  755.             any object bigger than a couple kilobytes.
  756.     free_medium:    release same.
  757.     alloc_small_sarray: construct an all-in-memory image sample array.
  758.     free_small_sarray:  release same.
  759.     alloc_small_barray,
  760.     free_small_barray:  ditto for block (coefficient) arrays.
  761.     request_big_sarray:  request a virtual image sample array.  The size
  762.                  of the in-memory buffer will be determined by the
  763.                  memory manager, but it will always be a multiple
  764.                  of the passed-in MCU height.
  765.     request_big_barray:  ditto for block (coefficient) arrays.
  766.     alloc_big_arrays:  instantiate all the big arrays previously requested.
  767.                This call will also pass some info about future
  768.                memory demands, so that the memory manager can
  769.                figure out how much space to leave unallocated.
  770.     access_big_sarray: obtain access to a specified portion of a virtual
  771.                image sample array.
  772.     free_big_sarray:   release a virtual sample array.
  773.     access_big_barray,
  774.     free_big_barray:   ditto for block (coefficient) arrays.
  775.     free_all:       release any remaining storage.  This is called
  776.                before normal or error termination; the main reason
  777.                why it must exist is to ensure that any temporary
  778.                files will be deleted upon error termination.
  779.  
  780.     alloc_big_arrays will be called by the pipeline controller, which does
  781.     most of the memory allocation anyway.  The only reason for having separate
  782.     request calls is to allow some of the other modules to get big arrays.
  783.     The pipeline controller is required to give an upper bound on total future
  784.     small-array requests, so that this space can be discounted.  (A fairly
  785.     conservative estimate will be adequate.)  Future small-object requests
  786.     aren't counted; the memory manager has to use a slop factor for those.
  787.     10K or so seems to be sufficient.  (In an 80x86, small objects aren't an
  788.     issue anyway, since they don't compete for far-heap space.  "Medium"-size
  789.     objects will have to be counted separately.)
  790.  
  791.     The distinction between sample and coefficient array routines is annoying,
  792.     but it has to be maintained for machines in which "char *" is represented
  793.     differently from "int *".  On byte-addressable machines some of these
  794.     methods could perhaps point to the same code.
  795.  
  796.     The array routines will operate on only 2-D arrays (one component at a
  797.     time), since different components may require different-size arrays.
  798.  
  799.     (This object hides the knowledge of whether virtual memory is available,
  800.     as well as the actual interface to OS and library support routines.)
  801.  
  802. Note that any given implementation will presumably contain only one
  803. instantiation of input file header reading, overall control, user interface,
  804. and memory management.  Thus these could be called as simple subroutines,
  805. without bothering with an object indirection.  This is essential for overall
  806. control (which has to initialize the object structure); for consistency we
  807. will impose objectness on the other three.
  808.  
  809.  
  810. *** Decompression object structure ***
  811.  
  812. I propose the following set of objects for decompression.  The general
  813. comments at the top of the compression object section also apply here.
  814.  
  815. 1. JPEG file scanning.  This will provide these methods:
  816.     read_file_header: read the file header, determine which variant
  817.               JPEG format is in use, read everything through SOF.
  818.     read_scan_header: read scan header (up through SOS).  This is called
  819.               after read_file_header and again after each scan;
  820.               it returns TRUE if it finds SOS, FALSE if EOI.
  821.     read_jpeg_data: fetch data for entropy decoder.
  822.     resync_to_restart: try to recover from bogus data (see below).
  823.     read_scan_trailer: finish up after one scan, prepare for another call
  824.                of read_scan_header (may be a no-op).
  825.     read_file_trailer: finish up at end of file (probably a no-op).
  826.    The entropy decoder must deal with restart markers, but all other JPEG
  827.    marker types will be handled in this object; useful data from the markers
  828.    will be extracted into data structures available to subsequent routines.
  829.    Note that on exit from read_file_header, only the SOF-marker data should be
  830.    assumed valid (image size, component IDs, sampling factors); other data
  831.    such as Huffman tables may not appear until after the SOF.  The overall
  832.    image size and colorspace can be determined after read_file_header, but not
  833.    whether or how the data is interleaved.  (This hides which variant JPEG
  834.    file format is being read.  In particular, for JPEG-in-TIFF the read_header
  835.    routines might not be scanning standard JPEG markers at all; they could
  836.    extract the data from TIFF tags.  The user interface will already have
  837.    opened the input file and possibly read part of the header before
  838.    read_file_header is called.)
  839.  
  840.    When reading a file with a nonzero restart interval, the entropy decoder
  841.    expects to see a correct sequence of restart markers.  In some cases, these
  842.    markers may be synthesized by the file-format module (a TIFF reader might
  843.    do so, for example, using tile boundary pointers to determine where the
  844.    restart intervals fall).  If the incoming data is corrupted, the entropy
  845.    decoder will read as far as the next JPEG marker, which may or may not be
  846.    the expected next restart marker.  If it isn't, resync_to_restart is called
  847.    to try to locate a good place to resume reading.  We make this heuristic a
  848.    file-format-dependent operation since some file formats may have special
  849.    info that's not available to the entropy decoder (again, TIFF is an
  850.    example).  Note that resync_to_restart is NOT called at the end of a scan;
  851.    it is read_scan_trailer's responsibility to resync there.
  852.  
  853.    NOTE: for JFIF/raw-JPEG file format, the read_jpeg_data routine is actually
  854.    supplied by the user interface; the jrdjfif module uses read_jpeg_data
  855.    internally to scan the input stream.  This makes it possible for the user
  856.    interface module to single-handedly implement special applications like
  857.    reading from a non-stdio source.  For JPEG-in-TIFF format, the need for
  858.    random access will make it impossible for this to work; hence the TIFF
  859.    header module will override the UI-supplied read_jpeg_data routine.
  860.    Non-stdio input from a TIFF file will require extensive surgery to the TIFF
  861.    header module, if indeed it is practical at all.
  862.  
  863. 2. Entropy (Huffman or arithmetic) decoding of the coefficient sequence.
  864.     entropy_decode_init: prepare for one scan.
  865.     entropy_decode: decodes and returns an MCU's worth of quantized
  866.             coefficients per call.
  867.     entropy_decode_term: finish up after a scan (may be a no-op).
  868.    This will read raw data by calling the read_jpeg_data method (I don't see
  869.    any reason to provide a further level of indirection).
  870.    (This hides which entropy encoding method is in use.)
  871.  
  872. 3. Quantization descaling and zigzag reordering of the elements in each 8x8
  873.    block.  This will be folded into entropy_decode for efficiency reasons:
  874.    many of the coefficients are zeroes, and this can be exploited most easily
  875.    within entropy_decode since the encoding explicitly skips zeroes.
  876.  
  877. 4. MCU disassembly (conversion of a possibly interleaved sequence of 8x8
  878.    blocks back to separate components in pixel map order).
  879.     disassemble_init: initialize.  This will be called once per scan.
  880.     disassemble_MCU:  Given an MCU's worth of dequantized blocks,
  881.               distribute them into the proper locations in a
  882.               coefficient image array.
  883.     disassemble_term: clean up at the end of a scan.
  884.    Probably this should be called once per MCU row and should call the
  885.    entropy decoder repeatedly to obtain the row's data.  The output is
  886.    always a multiple of an MCU's dimensions.
  887.    (An object on the grounds that multiple instantiations might be useful.)
  888.  
  889. 5. Cross-block smoothing per JPEG section K.8 or a similar algorithm.
  890.     smooth_coefficients: Given three block rows' worth of a single
  891.                  component, emit a smoothed equivalent of the
  892.                  middle row.  The "above" and "below" pointers
  893.                  may be NULL if at top/bottom of image.
  894.    The pipeline controller will do the necessary buffering to provide the
  895.    above/below context.  Smoothing will be optional since a good deal of
  896.    extra memory is needed to buffer the additional block rows.
  897.    (This object hides the details of the smoothing algorithm.)
  898.  
  899. 6. Inverse DCT transformation of each 8x8 block.
  900.     reverse_DCT: given an MCU row's worth of blocks, perform inverse
  901.              DCT on each block and output the results into an array
  902.              of samples.
  903.    We put this method into the jdmcu module for symmetry with the division of
  904.    labor in compression.  Note that the actual IDCT code is a separate source
  905.    file.
  906.  
  907. 7. Upsampling and smoothing: this will be applied to one component at a
  908.    time.  Note that cross-pixel smoothing, which was a separate step in the
  909.    prototype code, will now be performed simultaneously with expansion.
  910.     upsample_init: initialize (precalculate convolution factors, for
  911.                example).  This will be called once per scan.
  912.     upsample: Given a sample array, enlarge it by specified sampling
  913.           factors.
  914.     upsample_term: clean up at the end of a scan.
  915.    If the current component has vertical sampling factor Vk and the largest
  916.    sampling factor is Vmax, then the input is always Vk sample rows (whose
  917.    width is a multiple of Hk) and the output is always Vmax sample rows.
  918.    Vk additional rows above and below the nominal input rows are also passed
  919.    for use in cross-pixel smoothing.  At the top and bottom of the image,
  920.    these extra rows are copies of the first or last actual input row.
  921.    (This hides whether and how cross-pixel smoothing occurs.)
  922.  
  923. 8. Cropping to the original pixel dimensions (throwing away duplicated
  924.    pixels at the edges).  This won't be a separate object, just an
  925.    adjustment of the nominal image size in the pipeline controller.
  926.  
  927. 9. Color space reconversion and gamma adjustment.
  928.     colorout_init: initialization.  This will be passed the component
  929.                data from read_file_header, and will determine the
  930.                number of output components.
  931.     color_convert: convert a specified number of pixel rows.  Input and
  932.                output are image arrays of same size but possibly
  933.                different numbers of components.
  934.     colorout_term: cleanup (probably a no-op except for memory dealloc).
  935.    In practice will usually be given an MCU row's worth of pixel rows, except
  936.    at the bottom where a smaller number of rows may be left over.  Note that
  937.    this object works on all the components at once.
  938.    When quantizing colors, color_convert may be applied to the colormap
  939.    instead of actual pixel data.  color_convert is called by the color
  940.    quantizer in this case; the pipeline controller calls color_convert
  941.    directly only when not quantizing.
  942.    (Hides all knowledge of color space semantics and conversion.  Remaining
  943.    modules only need to know the number of JPEG and output components.)
  944.  
  945. 10. Color quantization (used only if a colormapped output format is requested).
  946.     We use two different strategies depending on whether one-pass (on-the-fly)
  947.     or two-pass quantization is requested.  Note that the two-pass interface
  948.     is actually designed to let the quantizer make any number of passes.
  949.     color_quant_init: initialization, allocate working memory.  In 1-pass
  950.               quantization, should call put_color_map.
  951.     color_quantize: convert a specified number of pixel rows.  Input
  952.             and output are image arrays of same size, but input
  953.             is N coefficients and output is only one.  (Used only
  954.             in 1-pass quantization.)
  955.     color_quant_prescan: prescan a specified number of pixel rows in
  956.                  2-pass quantization.
  957.     color_quant_doit: perform multi-pass color quantization.  Input is a
  958.               "big" sample image, output is via put_color_map and
  959.               put_pixel_rows.  (Used only in 2-pass quantization.)
  960.     color_quant_term: cleanup (probably a no-op except for memory dealloc).
  961.     The input to the color quantizer is always in the unconverted colorspace;
  962.     its output colormap must be in the converted colorspace.  The quantizer
  963.     has the choice of which space to work in internally.  It must call
  964.     color_convert either on its input data or on the colormap it sends to the
  965.     output module.
  966.     For one-pass quantization the image is simply processed by color_quantize,
  967.     a few rows at a time.  For two-pass quantization, the pipeline controller
  968.     accumulates the output of steps 1-8 into a "big" sample image.  The
  969.     color_quant_prescan method is invoked during this process so that the
  970.     quantizer can accumulate statistics.  (If the input file has multiple
  971.     scans, the prescan may be done during the final scan or as a separate
  972.     pass.)  At the end of the image, color_quant_doit is called; it must
  973.     create and output a colormap, then rescan the "big" image and pass mapped
  974.     data to the output module.  Additional scans of the image could be made
  975.     before the output pass is done (in fact, prescan could be a no-op).
  976.     As with entropy parameter optimization, the pipeline controller actually
  977.     passes an iterator function rather than direct access to the big image.
  978.     (Hides color quantization algorithm.)
  979.  
  980. 11. Writing of the desired image format.
  981.     output_init: produce the file header given data from read_file_header.
  982.     put_color_map: output colormap, if any (called by color quantizer).
  983.                If used, must be called before any pixel data is output.
  984.     put_pixel_rows: output image data in desired format.
  985.     output_term: finish up at the end.
  986.     The actual timing of I/O may differ from that suggested by the routine
  987.     names; for instance, writing of the file header may be delayed until
  988.     put_color_map time if the actual number of colors is needed in the header.
  989.     Also, the colormap is available to put_pixel_rows and output_term as well
  990.     as put_color_map.
  991.     Note that whether colormapping is needed will be determined by the user
  992.     interface object prior to method selection.  In implementations that
  993.     support multiple output formats, the actual output format will also be
  994.     determined by the user interface.
  995.     (Hides format of output image and mechanism used to write it.  Note that
  996.     several other objects know the color model used by the output format.
  997.     The actual mechanism for writing the file is private to this object and
  998.     the user interface.)
  999.  
  1000. 12. Pipeline control.  This object will provide the "main loop" that invokes
  1001.     all the pipeline objects.  Note that we will need several different main
  1002.     loops depending on the situation (interleaved input or not, whether to
  1003.     apply cross-block smoothing or not, etc).  We may want to divvy up the
  1004.     pipeline controllers into two levels, one that retains control over the
  1005.     whole file and one that is invoked per scan.
  1006.     This object will do most of the memory allocation, since it will provide
  1007.     the working buffers that are the inputs and outputs of the pipeline steps.
  1008.     (An object mostly to support multiple instantiations; however, overall
  1009.     memory management and sequencing of operations are known only here.)
  1010.  
  1011. 13. Overall control.  This module will provide at least two routines:
  1012.     jpeg_decompress: the main entry point to the decompressor.
  1013.     per_scan_method_selection: called by pipeline controllers for
  1014.                    secondary method selection passes.
  1015.     jpeg_decompress is invoked from the user interface after the UI has
  1016.     selected the input and output files and obtained values for all
  1017.     user-specified options (e.g., output file format, whether to do block
  1018.     smoothing).  jpeg_decompress calls read_file_header, performs basic
  1019.     initialization (e.g., calculating the size of MCUs), does the "global"
  1020.     method selection pass, and finally calls the selected pipeline control
  1021.     object.  (Per-scan method selections will be invoked by the pipeline
  1022.     controller.)
  1023.     Note that jpeg_decompress can't be a method since it is invoked prior to
  1024.     method selection.
  1025.  
  1026. 14. User interface; this is the architecture's term for "the rest of the
  1027.     application program", i.e., that which invokes the JPEG decompressor.
  1028.     The UI is expected to supply input and output files and values for all
  1029.     operational parameters.  The UI must also supply error handling routines.
  1030.     (This module hides the user interface provided --- command line,
  1031.     interactive, etc.  Except for error handling, the UI calls the portable
  1032.     JPEG code, not the other way around.)
  1033.  
  1034. 15. A memory management object.  This will be identical to the memory
  1035.     management for compression (and will be the same code, in combined
  1036.     programs).  See above for details.
  1037.  
  1038.  
  1039. *** Initial method selection ***
  1040.  
  1041. The main ugliness in this design is the portion of startup that will select
  1042. which of several instantiations should be used for each of the objects.  (For
  1043. example, Huffman or arithmetic for entropy encoding; one of several pipeline
  1044. controllers depending on interleaving, the size of the image, etc.)  It's not
  1045. really desirable to have a single chunk of code that knows the names of all
  1046. the possible instantiations and the conditions under which to select each one.
  1047.  
  1048. The best approach seems to be to provide a selector function for each object
  1049. (group of related method calls).  This function knows about each possible
  1050. instantiation of its object and how to choose the right one; but it doesn't
  1051. know about any other objects.
  1052.  
  1053. Note that there will be several rounds of method selection: at initial startup,
  1054. after overall compression parameters are determined (after the file header is
  1055. read, if decompressing), and one in preparation for each scan (this occurs
  1056. more than once if the file is noninterleaved).  Each object method will need
  1057. to be clearly identified as to which round sets it up.
  1058.  
  1059.  
  1060. *** Implications of DNL marker ***
  1061.  
  1062. Some JPEG files may use a DNL marker to postpone definition of the image
  1063. height (this would be useful for a fax-like scanner's output, for instance).
  1064. In these files the SOF marker claims the image height is 0, and you only
  1065. find out the true image height at the end of the first scan.
  1066.  
  1067. We could handle these files as follows:
  1068. 1. Upon seeing zero image height, replace it by 65535 (the maximum allowed).
  1069. 2. When the DNL is found, update the image height in the global image
  1070.    descriptor.
  1071. This implies that pipeline control objects must avoid making copies of the
  1072. image height, and must re-test for termination after each MCU row.  This is
  1073. no big deal.
  1074.  
  1075. In situations where image-size data structures are allocated, this approach
  1076. will result in very inefficient use of virtual memory or
  1077. much-larger-than-necessary temporary files.  This seems acceptable for
  1078. something that probably won't be a mainstream usage.  People might have to
  1079. forgo use of memory-hogging options (such as two-pass color quantization or
  1080. noninterleaved JPEG files) if they want efficient conversion of such files.
  1081. (One could improve efficiency by demanding a user-supplied upper bound for the
  1082. height, less than 65536; in most cases it could be much less.)
  1083.  
  1084. Alternately, we could insist that DNL-using files be preprocessed by a
  1085. separate program that reads ahead to the DNL, then goes back and fixes the SOF
  1086. marker.  This is a much simpler solution and is probably far more efficient.
  1087. Even if one wants piped input, buffering the first scan of the JPEG file
  1088. needs a lot smaller temp file than is implied by the maximum-height method.
  1089. For this approach we'd simply treat DNL as a no-op in the decompressor (at
  1090. most, check that it matches the SOF image height).
  1091.  
  1092. We will not worry about making the compressor capable of outputting DNL.
  1093. Something similar to the first scheme above could be applied if anyone ever
  1094. wants to make that work.
  1095.  
  1096.  
  1097. *** Memory manager internal structure ***
  1098.  
  1099. The memory manager contains the most potential for system dependencies.
  1100. To isolate system dependencies as much as possible, we have broken the
  1101. memory manager into two parts.  There is a reasonably system-independent
  1102. "front end" (jmemmgr.c) and a "back end" that contains only the code
  1103. likely to change across systems.  All of the memory management methods
  1104. outlined above are implemented by the front end.  The back end provides
  1105. the following routines for use by the front end (none of these routines
  1106. are known to the rest of the JPEG code):
  1107.  
  1108. jmem_init, jmem_term    system-dependent initialization/shutdown
  1109.  
  1110. jget_small, jfree_small    interface to malloc and free library routines
  1111.  
  1112. jget_large, jfree_large    interface to FAR malloc/free in MS-DOS machines;
  1113.             otherwise same as jget_small/jfree_small
  1114.  
  1115. jmem_available        estimate available memory
  1116.  
  1117. jopen_backing_store    create a backing-store object
  1118.  
  1119. read_backing_store,    manipulate a backing store object
  1120. write_backing_store,
  1121. close_backing_store
  1122.  
  1123. On some systems there will be more than one type of backing-store object
  1124. (specifically, in MS-DOS a backing store file might be an area of extended
  1125. memory as well as a disk file).  jopen_backing_store is responsible for
  1126. choosing how to implement a given object.  The read/write/close routines
  1127. are method pointers in the structure that describes a given object; this
  1128. lets them be different for different object types.
  1129.  
  1130. It may be necessary to ensure that backing store objects are explicitly
  1131. released upon abnormal program termination.  (For example, MS-DOS won't free
  1132. extended memory by itself.)  To support this, we will expect the main program
  1133. or surrounding application to arrange to call the free_all method upon
  1134. abnormal termination; this may require a SIGINT signal handler, for instance.
  1135. (We don't want to have the system-dependent module install its own signal
  1136. handler, because that would pre-empt the surrounding application's ability
  1137. to control signal handling.)
  1138.  
  1139.  
  1140. *** Notes for MS-DOS implementors ***
  1141.  
  1142. The standalone cjpeg and djpeg applications can be compiled in "small" memory
  1143. model, at least at the moment; as the code grows we may be forced to switch to
  1144. "medium" model.  (Small = both code and data pointers are near by default;
  1145. medium = far code pointers, near data pointers.)  Medium model will slow down
  1146. calls through method pointers, but I don't think this will amount to any
  1147. significant speed penalty.
  1148.  
  1149. When integrating the JPEG code into a larger application, it's a good idea to
  1150. stay with a small-data-space model if possible.  An 8K stack is much more than
  1151. sufficient for the JPEG code, and its static data requirements are less than
  1152. 1K.  When executed, it will typically malloc about 10K-20K worth of near heap
  1153. space (and lots of far heap, but that doesn't count in this calculation).
  1154. This figure will vary depending on image size and other factors, but figuring
  1155. 30K should be more than sufficient.  Thus you have about 25K available for
  1156. other modules' static data and near heap requirements before you need to go to
  1157. a larger memory model.  The C library's static data will account for several K
  1158. of this, but that still leaves a good deal for your needs.  (If you are tight
  1159. on space, you could reduce JPEG_BUF_SIZE from 4K to 1K to save 3K of near heap
  1160. space.)
  1161.  
  1162. As the code is improved, we will endeavor to hold the near data requirements
  1163. to the range given above.  This does imply that certain data structures will
  1164. be allocated as FAR although they would fit in near space if we assumed the
  1165. JPEG code is stand-alone.  (The LZW tables in jrdgif/jwrgif are examples.)
  1166. To make an optimal implementation, you might want to move these structures
  1167. back to near heap if you know there is sufficient space.
  1168.  
  1169. FAR data space may also be a tight resource when you are dealing with large
  1170. images.  The most memory-intensive case is decompression with two-pass color
  1171. quantization.  This requires a 128Kb color histogram plus strip buffers
  1172. amounting to about 150 bytes per column for typical sampling ratios (eg, about
  1173. 96000 bytes for a 640-pixel-wide image).  You may not be able to process wide
  1174. images if you have large data structures of your own.
  1175.  
  1176.  
  1177. *** Potential optimizations ***
  1178.  
  1179. For colormapped input formats it might be worthwhile to merge the input file
  1180. reading and the colorspace conversion steps; in other words, do the colorspace
  1181. conversion by hacking up the colormap before inputting the image body, rather
  1182. than doing the conversion on each pixel independently.  Not clear if this is
  1183. worth the uglification involved.  In the above design for the compressor, only
  1184. the colorspace conversion step ever sees the output of get_input_row, so this
  1185. sort of thing could be done via private agreement between those two modules.
  1186.  
  1187. Level shift from 0..255 to -128..127 may be done either during colorspace
  1188. conversion, or at the moment of converting an 8x8 sample block into the format
  1189. used by the DCT step (which will be signed short or long int).  This could be
  1190. selectable by a compile-time flag, so that the intermediate steps can work on
  1191. either signed or unsigned chars as samples, whichever is most easily handled
  1192. by the platform.  However, making sure that rounding is done right will be a
  1193. lot easier if we can assume positive values.  At the moment I think that
  1194. benefit is worth the overhead of "& 0xFF" when reading out sample values on
  1195. signed-char-only machines.
  1196.