home *** CD-ROM | disk | FTP | other *** search
/ rtsi.com / 2014.01.www.rtsi.com.tar / www.rtsi.com / OS9 / OSK / NETWORK / netpbm_src.lzh / NETPBM / LIBTIFF / tif_fax3.c < prev    next >
Text File  |  1996-11-18  |  28KB  |  1,078 lines
  1. #ifndef lint
  2. static char rcsid[] = "$Header: /usr/people/sam/tiff/libtiff/RCS/tif_fax3.c,v 1.75 93/08/26 14:24:43 sam Exp $";
  3. #endif
  4.  
  5. /*
  6.  * Copyright (c) 1990, 1991, 1992 Sam Leffler
  7.  * Copyright (c) 1991, 1992 Silicon Graphics, Inc.
  8.  *
  9.  * Permission to use, copy, modify, distribute, and sell this software and 
  10.  * its documentation for any purpose is hereby granted without fee, provided
  11.  * that (i) the above copyright notices and this permission notice appear in
  12.  * all copies of the software and related documentation, and (ii) the names of
  13.  * Sam Leffler and Silicon Graphics may not be used in any advertising or
  14.  * publicity relating to the software without the specific, prior written
  15.  * permission of Sam Leffler and Silicon Graphics.
  16.  * 
  17.  * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, 
  18.  * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY 
  19.  * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.  
  20.  * 
  21.  * IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR
  22.  * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
  23.  * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  24.  * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF 
  25.  * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE 
  26.  * OF THIS SOFTWARE.
  27.  */
  28.  
  29. /*
  30.  * TIFF Library.
  31.  *
  32.  * CCITT Group 3 and Group 4 Compression Support.
  33.  */
  34. #include "tiffiop.h"
  35. #include "tif_fax3.h"
  36. #define    G3CODES
  37. #include "t4.h"
  38. #define    G3STATES
  39. #include "g3states.h"
  40. #include <assert.h>
  41. #include <stdio.h>
  42.  
  43. typedef struct {
  44.     Fax3BaseState b;
  45. } Fax3DecodeState;
  46.  
  47. typedef struct {
  48.     Fax3BaseState b;
  49.     const u_char *wruns;
  50.     const u_char *bruns;
  51.     short    k;            /* #rows left that can be 2d encoded */
  52.     short    maxk;            /* max #rows that can be 2d encoded */
  53. } Fax3EncodeState;
  54.  
  55. static    int Fax3Decode1DRow(TIFF*, u_char*, int);
  56. static    int Fax3Encode1DRow(TIFF*, u_char*, int);
  57. static    int findspan(u_char**, int, int, const u_char*);
  58. static    int finddiff(u_char*, int, int, int);
  59.  
  60. void
  61. TIFFModeCCITTFax3(TIFF* tif, int isClassF)
  62. {
  63.     if (isClassF)
  64.         tif->tif_options |= FAX3_CLASSF;
  65.     else
  66.         tif->tif_options &= ~FAX3_CLASSF;
  67. }
  68.  
  69. static u_char bitMask[8] =
  70.     { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
  71. #define    isBitSet(sp)    ((sp)->b.data & bitMask[(sp)->b.bit])
  72.  
  73. #define    is2DEncoding(tif) \
  74.     (tif->tif_dir.td_group3options & GROUP3OPT_2DENCODING)
  75. #define    fetchByte(tif, sp) \
  76.     ((tif)->tif_rawcc--, (sp)->b.bitmap[*(u_char *)(tif)->tif_rawcp++])
  77.  
  78. #define    BITCASE(b)            \
  79.     case b:                \
  80.     code <<= 1;            \
  81.     if (data & (1<<(7-b))) code |= 1;\
  82.     len++;                \
  83.     if (code > 0) { bit = b+1; break; }
  84.  
  85. /*
  86.  * Skip over input until an EOL code is found.  The
  87.  * value of len is passed as 0 except during error
  88.  * recovery when decoding 2D data.  Note also that
  89.  * we don't use the optimized state tables to locate
  90.  * an EOL because we can't assume much of anything
  91.  * about our state (e.g. bit position).
  92.  */
  93. static void
  94. skiptoeol(TIFF* tif, int len)
  95. {
  96.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  97.     register int bit = sp->b.bit;
  98.     register int data = sp->b.data;
  99.     int code = 0;
  100.  
  101.     /*
  102.      * Our handling of ``bit'' is painful because
  103.      * the rest of the code does not maintain it as
  104.      * exactly the bit offset in the current data
  105.      * byte (bit == 0 means refill the data byte).
  106.      * Thus we have to be careful on entry and
  107.      * exit to insure that we maintain a value that's
  108.      * understandable elsewhere in the decoding logic.
  109.      */
  110.     if (bit == 0)            /* force refill */
  111.         bit = 8;
  112.     for (;;) {
  113.         switch (bit) {
  114.     again:    BITCASE(0);
  115.         BITCASE(1);
  116.         BITCASE(2);
  117.         BITCASE(3);
  118.         BITCASE(4);
  119.         BITCASE(5);
  120.         BITCASE(6);
  121.         BITCASE(7);
  122.         default:
  123.             if (tif->tif_rawcc <= 0)
  124.                 return;
  125.             data = fetchByte(tif, sp);
  126.             goto again;
  127.         }
  128.         if (len >= 12 && code == EOL)
  129.             break;
  130.         code = len = 0;
  131.     }
  132.     sp->b.bit = bit > 7 ? 0 : bit;    /* force refill */
  133.     sp->b.data = data;
  134. }
  135.  
  136. /*
  137.  * Return the next bit in the input stream.  This is
  138.  * used to extract 2D tag values and the color tag
  139.  * at the end of a terminating uncompressed data code.
  140.  */
  141. static int
  142. nextbit(TIFF* tif)
  143. {
  144.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  145.     int bit;
  146.  
  147.     if (sp->b.bit == 0 && tif->tif_rawcc > 0)
  148.         sp->b.data = fetchByte(tif, sp);
  149.     bit = isBitSet(sp);
  150.     if (++(sp->b.bit) > 7)
  151.         sp->b.bit = 0;
  152.     return (bit);
  153. }
  154.  
  155. /*
  156.  * Setup G3-related compression/decompression
  157.  * state before data is processed.  This routine
  158.  * is called once per image -- it sets up different
  159.  * state based on whether or not 2D encoding is used.
  160.  */
  161. static void *
  162. Fax3SetupState(TIFF* tif, int space)
  163. {
  164.     TIFFDirectory *td = &tif->tif_dir;
  165.     Fax3BaseState *sp;
  166.     int cc = space;
  167.     long rowbytes, rowpixels;
  168.  
  169.     if (td->td_bitspersample != 1) {
  170.         TIFFError(tif->tif_name,
  171.             "Bits/sample must be 1 for Group 3/4 encoding/decoding");
  172.         return (0);
  173.     }
  174.     /*
  175.      * Calculate the scanline/tile widths.
  176.      */
  177.     if (isTiled(tif)) {
  178.         rowbytes = TIFFTileRowSize(tif);
  179.         rowpixels = tif->tif_dir.td_tilewidth;
  180.     } else {
  181.         rowbytes = TIFFScanlineSize(tif);
  182.         rowpixels = tif->tif_dir.td_imagewidth;
  183.     }
  184.     if (is2DEncoding(tif) || td->td_compression == COMPRESSION_CCITTFAX4)
  185.         cc += rowbytes+1;
  186.     tif->tif_data = _TIFFmalloc(cc);
  187.     if (tif->tif_data == NULL) {
  188.         TIFFError("Fax3SetupState",
  189.             "%s: No space for Fax3 state block", tif->tif_name);
  190.         return (0);
  191.     }
  192.     sp = (Fax3BaseState *)tif->tif_data;
  193.     sp->rowbytes = rowbytes;
  194.     sp->rowpixels = rowpixels;
  195.     sp->bitmap = TIFFGetBitRevTable(tif->tif_fillorder != td->td_fillorder);
  196.     sp->white = (td->td_photometric == PHOTOMETRIC_MINISBLACK);
  197.     if (is2DEncoding(tif) || td->td_compression == COMPRESSION_CCITTFAX4) {
  198.         /*
  199.          * 2d encoding/decoding requires a scanline
  200.          * buffer for the ``reference line''; the
  201.          * scanline against which delta encoding
  202.          * is referenced.  The reference line must
  203.          * be initialized to be ``white'' (done elsewhere).
  204.          */
  205.         sp->refline = (u_char *)tif->tif_data + space + 1;
  206.         /*
  207.          * Initialize pixel just to the left of the
  208.          * reference line to white.  This extra pixel
  209.          * simplifies the edge-condition logic.
  210.          */
  211.         sp->refline[-1] = sp->white ? 0xff : 0x00;
  212.     } else
  213.         sp->refline = 0;
  214.     return (sp);
  215. }
  216.  
  217. /*
  218.  * Setup state for decoding a strip.
  219.  */
  220. static
  221. Fax3PreDecode(TIFF* tif)
  222. {
  223.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  224.  
  225.     if (sp == NULL) {
  226.         sp = (Fax3DecodeState *)Fax3SetupState(tif, sizeof (*sp));
  227.         if (!sp)
  228.             return (0);
  229.     }
  230.     sp->b.bit = 0;            /* force initial read */
  231.     sp->b.data = 0;
  232.     sp->b.tag = G3_1D;
  233.     if (sp->b.refline)
  234.         memset(sp->b.refline, sp->b.white ? 0xff:0x00, sp->b.rowbytes);
  235.     /*
  236.      * If image has EOL codes, they precede each line
  237.      * of data.  We skip over the first one here so that
  238.      * when we decode rows, we can use an EOL to signal
  239.      * that less than the expected number of pixels are
  240.      * present for the scanline.
  241.      */
  242.     if ((tif->tif_options & FAX3_NOEOL) == 0) {
  243.         skiptoeol(tif, 0);
  244.         if (is2DEncoding(tif))
  245.             /* tag should always be 1D! */
  246.             sp->b.tag = nextbit(tif) ? G3_1D : G3_2D;
  247.     }
  248.     return (1);
  249. }
  250.  
  251. /*
  252.  * Fill a span with ones.
  253.  */
  254. static void
  255. fillspan(register char* cp, register int x, register int count)
  256. {
  257.     static const unsigned char masks[] =
  258.         { 0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff };
  259.  
  260.     if (count <= 0)
  261.         return;
  262.     cp += x>>3;
  263.     if (x &= 7) {            /* align to byte boundary */
  264.         if (count < 8 - x) {
  265.             *cp++ |= masks[count] >> x;
  266.             return;
  267.         }
  268.         *cp++ |= 0xff >> x;
  269.         count -= 8 - x;
  270.     }
  271.     while (count >= 8) {
  272.         *cp++ = 0xff;
  273.         count -= 8;
  274.     }
  275.     *cp |= masks[count];
  276. }
  277.  
  278. /*
  279.  * Decode the requested amount of data.
  280.  */
  281. static
  282. Fax3Decode(TIFF* tif, tidata_t buf, tsize_t occ, tsample_t s)
  283. {
  284.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  285.     int status;
  286.  
  287.     memset(buf, 0, occ);        /* decoding only sets non-zero bits */
  288.     while ((long)occ > 0) {
  289.         if (sp->b.tag == G3_1D)
  290.             status = Fax3Decode1DRow(tif, buf, sp->b.rowpixels);
  291.         else
  292.             status = Fax3Decode2DRow(tif, buf, sp->b.rowpixels);
  293.         /*
  294.          * For premature EOF, stop decoding and return
  295.          * the buffer with the remainder white-filled.
  296.          */
  297.         if (status < 0)
  298.             return (status == G3CODE_EOF);
  299.         if (is2DEncoding(tif)) {
  300.             /*
  301.              * Fetch the tag bit that indicates
  302.              * whether the next row is 1d or 2d
  303.              * encoded.  If 2d-encoded, then setup
  304.              * the reference line from the decoded
  305.              * scanline just completed.
  306.              */
  307.             sp->b.tag = nextbit(tif) ? G3_1D : G3_2D;
  308.             if (sp->b.tag == G3_2D)
  309.                 memcpy(sp->b.refline, buf, sp->b.rowbytes);
  310.         }
  311.         buf += sp->b.rowbytes;
  312.         occ -= sp->b.rowbytes;
  313.         if (occ != 0)
  314.             tif->tif_row++;
  315.     }
  316.     return (1);
  317. }
  318.  
  319. /*
  320.  * Decode a run of white.
  321.  */
  322. static int
  323. decode_white_run(TIFF* tif)
  324. {
  325.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  326.     short state = sp->b.bit;
  327.     short action;
  328.     int runlen = 0;
  329.  
  330.     for (;;) {
  331.         if (sp->b.bit == 0) {
  332.     nextbyte:
  333.             if (tif->tif_rawcc <= 0)
  334.                 return (G3CODE_EOF);
  335.             sp->b.data = fetchByte(tif, sp);
  336.         }
  337.         action = TIFFFax1DAction[state][sp->b.data];
  338.         state = TIFFFax1DNextState[state][sp->b.data];
  339.         if (action == ACT_INCOMP)
  340.             goto nextbyte;
  341.         if (action == ACT_INVALID)
  342.             return (G3CODE_INVALID);
  343.         if (action == ACT_EOL)
  344.             return (G3CODE_EOL);
  345.         sp->b.bit = state;
  346.         action = RUNLENGTH(action - ACT_WRUNT);
  347.         runlen += action;
  348.         if (action < 64)
  349.             return (runlen);
  350.     }
  351.     /*NOTREACHED*/
  352. }
  353.  
  354. /*
  355.  * Decode a run of black.
  356.  */
  357. static int
  358. decode_black_run(TIFF* tif)
  359. {
  360.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  361.     short state = sp->b.bit + 8;
  362.     short action;
  363.     int runlen = 0;
  364.  
  365.     for (;;) {
  366.         if (sp->b.bit == 0) {
  367.     nextbyte:
  368.             if (tif->tif_rawcc <= 0)
  369.                 return (G3CODE_EOF);
  370.             sp->b.data = fetchByte(tif, sp);
  371.         }
  372.         action = TIFFFax1DAction[state][sp->b.data];
  373.         state = TIFFFax1DNextState[state][sp->b.data];
  374.         if (action == ACT_INCOMP)
  375.             goto nextbyte;
  376.         if (action == ACT_INVALID)
  377.             return (G3CODE_INVALID);
  378.         if (action == ACT_EOL)
  379.             return (G3CODE_EOL);
  380.         sp->b.bit = state;
  381.         action = RUNLENGTH(action - ACT_BRUNT);
  382.         runlen += action;
  383.         if (action < 64)
  384.             return (runlen);
  385.         state += 8;
  386.     }
  387.     /*NOTREACHED*/
  388. }
  389.  
  390. /*
  391.  * Process one row of 1d Huffman-encoded data.
  392.  */
  393. static int
  394. Fax3Decode1DRow(TIFF* tif, u_char* buf, int npels)
  395. {
  396.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  397.     int x = 0;
  398.     int runlen;
  399.     short action;
  400.     short color = sp->b.white;
  401.     static const char module[] = "Fax3Decode1D";
  402.  
  403.     for (;;) {
  404.         if (color == sp->b.white)
  405.             runlen = decode_white_run(tif);
  406.         else
  407.             runlen = decode_black_run(tif);
  408.         switch (runlen) {
  409.         case G3CODE_EOF:
  410.             TIFFWarning(module,
  411.                 "%s: Premature EOF at scanline %d (x %d)",
  412.                 tif->tif_name, tif->tif_row, x);
  413.             return (G3CODE_EOF);
  414.         case G3CODE_INVALID:    /* invalid code */
  415.             /*
  416.              * An invalid code was encountered.
  417.              * Flush the remainder of the line
  418.              * and allow the caller to decide whether
  419.              * or not to continue.  Note that this
  420.              * only works if we have a G3 image
  421.              * with EOL markers.
  422.              */
  423.             TIFFError(module,
  424.                "%s: Bad code word at scanline %d (x %d)",
  425.                tif->tif_name, tif->tif_row, x);
  426.             goto done;
  427.         case G3CODE_EOL:    /* premature end-of-line code */
  428.             TIFFWarning(module,
  429.                 "%s: Premature EOL at scanline %d (x %d)",
  430.                 tif->tif_name, tif->tif_row, x);
  431.             return (1);    /* try to resynchronize... */
  432.         }
  433.         if (x+runlen > npels)
  434.             runlen = npels-x;
  435.         if (runlen > 0) {
  436.             if (color)
  437.                 fillspan((char *)buf, x, runlen);
  438.             x += runlen;
  439.             if (x >= npels)
  440.                 break;
  441.         }
  442.         color = !color;
  443.     }
  444. done:
  445.     /*
  446.      * Cleanup at the end of the row.  This convoluted
  447.      * logic is merely so that we can reuse the code with
  448.      * two other related compression algorithms (2 & 32771).
  449.      *
  450.      * Note also that our handling of word alignment assumes
  451.      * that the buffer is at least word aligned.  This is
  452.      * the case for most all versions of malloc (typically
  453.      * the buffer is returned longword aligned).
  454.      */
  455.     if ((tif->tif_options & FAX3_NOEOL) == 0)
  456.         skiptoeol(tif, 0);
  457.     if (tif->tif_options & FAX3_BYTEALIGN)
  458.         sp->b.bit = 0;
  459.     if ((tif->tif_options & FAX3_WORDALIGN) && ((long)tif->tif_rawcp & 1))
  460.         (void) fetchByte(tif, sp);
  461.     return (x == npels ? 1 : G3CODE_EOL);
  462. }
  463.  
  464. /*
  465.  * Group 3 2d Decoding support.
  466.  */
  467.  
  468. /*
  469.  * Return the next uncompressed mode code word.
  470.  */
  471. static int
  472. decode_uncomp_code(TIFF* tif)
  473. {
  474.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  475.     short code;
  476.  
  477.     do {
  478.         if (sp->b.bit == 0 || sp->b.bit > 7) {
  479.             if (tif->tif_rawcc <= 0)
  480.                 return (UNCOMP_EOF);
  481.             sp->b.data = fetchByte(tif, sp);
  482.         }
  483.         code = TIFFFaxUncompAction[sp->b.bit][sp->b.data];
  484.         sp->b.bit = TIFFFaxUncompNextState[sp->b.bit][sp->b.data];
  485.     } while (code == ACT_INCOMP);
  486.     return (code);
  487. }
  488.  
  489. /*
  490.  * Process one row of 2d encoded data.
  491.  */
  492. int
  493. Fax3Decode2DRow(TIFF* tif, u_char* buf, int npels)
  494. {
  495. #define    PIXEL(buf,ix)    ((((buf)[(ix)>>3]) >> (7-((ix)&7))) & 1)
  496.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  497.     int a0 = -1;
  498.     int b1, b2;
  499.     int run1, run2;        /* for horizontal mode */
  500.     short mode;
  501.     short color = sp->b.white;
  502.     static const char module[] = "Fax3Decode2D";
  503.  
  504.     do {
  505.         if (sp->b.bit == 0 || sp->b.bit > 7) {
  506.             if (tif->tif_rawcc <= 0) {
  507.                 TIFFError(module,
  508.                     "%s: Premature EOF at scanline %d",
  509.                     tif->tif_name, tif->tif_row);
  510.                 return (G3CODE_EOF);
  511.             }
  512.             sp->b.data = fetchByte(tif, sp);
  513.         }
  514.         mode = TIFFFax2DMode[sp->b.bit][sp->b.data];
  515.         sp->b.bit = TIFFFax2DNextState[sp->b.bit][sp->b.data];
  516.         switch (mode) {
  517.         case MODE_NULL:
  518.             break;
  519.         case MODE_PASS:
  520.             b2 = finddiff(sp->b.refline, a0, npels, !color);
  521.             b1 = finddiff(sp->b.refline, b2, npels, color);
  522.             b2 = finddiff(sp->b.refline, b1, npels, !color);
  523.             if (color) {
  524.                 if (a0 < 0)
  525.                     a0 = 0;
  526.                 fillspan((char *)buf, a0, b2 - a0);
  527.             }
  528.             a0 = b2;
  529.             break;
  530.         case MODE_HORIZ:
  531.             if (color == sp->b.white) {
  532.                 run1 = decode_white_run(tif);
  533.                 run2 = decode_black_run(tif);
  534.             } else {
  535.                 run1 = decode_black_run(tif);
  536.                 run2 = decode_white_run(tif);
  537.             }
  538.             if (run1 >= 0 && run2 >= 0) {
  539.                 /*
  540.                  * Do the appropriate fill.  Note that we exit
  541.                  * this logic with the same color that we enter
  542.                  * with since we do 2 fills.  This explains the
  543.                  * somewhat obscure logic below.
  544.                  */
  545.                 if (a0 < 0)
  546.                     a0 = 0;
  547.                 if (a0 + run1 > npels)
  548.                     run1 = npels - a0;
  549.                 if (color)
  550.                     fillspan((char *)buf, a0, run1);
  551.                 a0 += run1;
  552.                 if (a0 + run2 > npels)
  553.                     run2 = npels - a0;
  554.                 if (!color)
  555.                     fillspan((char *)buf, a0, run2);
  556.                 a0 += run2;
  557.             }
  558.             break;
  559.         case MODE_VERT_V0:
  560.         case MODE_VERT_VR1:
  561.         case MODE_VERT_VR2:
  562.         case MODE_VERT_VR3:
  563.         case MODE_VERT_VL1:
  564.         case MODE_VERT_VL2:
  565.         case MODE_VERT_VL3:
  566.             b2 = finddiff(sp->b.refline, a0, npels, !color);
  567.             b1 = finddiff(sp->b.refline, b2, npels, color);
  568.             b1 += mode - MODE_VERT_V0;
  569.             if (color) {
  570.                 if (a0 < 0)
  571.                     a0 = 0;
  572.                 fillspan((char *)buf, a0, b1 - a0);
  573.             }
  574.             color = !color;
  575.             a0 = b1;
  576.             break;
  577.             case MODE_UNCOMP:
  578.             /*
  579.              * Uncompressed mode: select from the
  580.              * special set of code words.
  581.              */
  582.             if (a0 < 0)
  583.                 a0 = 0;
  584.             do {
  585.                 mode = decode_uncomp_code(tif);
  586.                 switch (mode) {
  587.                 case UNCOMP_RUN1:
  588.                 case UNCOMP_RUN2:
  589.                 case UNCOMP_RUN3:
  590.                 case UNCOMP_RUN4:
  591.                 case UNCOMP_RUN5:
  592.                     run1 = mode - UNCOMP_RUN0;
  593.                     fillspan((char *)buf, a0+run1-1, 1);
  594.                     a0 += run1;
  595.                     break;
  596.                 case UNCOMP_RUN6:
  597.                     a0 += 5;
  598.                     break;
  599.                 case UNCOMP_TRUN0:
  600.                 case UNCOMP_TRUN1:
  601.                 case UNCOMP_TRUN2:
  602.                 case UNCOMP_TRUN3:
  603.                 case UNCOMP_TRUN4:
  604.                     run1 = mode - UNCOMP_TRUN0;
  605.                     a0 += run1;
  606.                     color = nextbit(tif) ?
  607.                         !sp->b.white : sp->b.white;
  608.                     break;
  609.                 case UNCOMP_INVALID:
  610.                     TIFFError(module,
  611.                 "%s: Bad uncompressed code word at scanline %d",
  612.                         tif->tif_name, tif->tif_row);
  613.                     goto bad;
  614.                 case UNCOMP_EOF:
  615.                     TIFFError(module,
  616.                         "%s: Premature EOF at scanline %d",
  617.                         tif->tif_name, tif->tif_row);
  618.                     return (G3CODE_EOF);
  619.                 }
  620.             } while (mode < UNCOMP_EXIT);
  621.             break;
  622.             case MODE_ERROR_1:
  623.             if ((tif->tif_options & FAX3_NOEOL) == 0) {
  624.                 TIFFWarning(module,
  625.                     "%s: Premature EOL at scanline %d (x %d)",
  626.                     tif->tif_name, tif->tif_row, a0);
  627.                 skiptoeol(tif, 7);    /* seen 7 0's already */
  628.                 return (1);        /* try to synchronize */
  629.             }
  630.             /* fall thru... */
  631.             case MODE_ERROR:
  632.             TIFFError(module,
  633.                 "%s: Bad 2D code word at scanline %d",
  634.                 tif->tif_name, tif->tif_row);
  635.             goto bad;
  636.             default:
  637.             TIFFError(module,
  638.                 "%s: Panic, bad decoding state at scanline %d",
  639.                 tif->tif_name, tif->tif_row);
  640.             return (0);
  641.         }
  642.     } while (a0 < npels);
  643. bad:
  644.     /*
  645.      * Cleanup at the end of row.  We check for
  646.      * EOL separately so that this code can be
  647.      * reused by the Group 4 decoding routine.
  648.      */
  649.     if ((tif->tif_options & FAX3_NOEOL) == 0)
  650.         skiptoeol(tif, 0);
  651.     return (a0 >= npels ? 1 : G3CODE_EOL);
  652. #undef    PIXEL
  653. }
  654.  
  655. /*
  656.  * CCITT Group 3 FAX Encoding.
  657.  */
  658.  
  659. /*
  660.  * Write a variable-length bit-value to
  661.  * the output stream.  Values are
  662.  * assumed to be at most 16 bits.
  663.  */
  664. void
  665. Fax3PutBits(TIFF* tif, u_int bits, u_int length)
  666. {
  667.     Fax3BaseState *sp = (Fax3BaseState *)tif->tif_data;
  668.     static const int mask[9] =
  669.         { 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff };
  670.  
  671.     while (length > sp->bit) {
  672.         sp->data |= bits >> (length - sp->bit);
  673.         length -= sp->bit;
  674.         Fax3FlushBits(tif, sp);
  675.     }
  676.     sp->data |= (bits & mask[length]) << (sp->bit - length);
  677.     sp->bit -= length;
  678.     if (sp->bit == 0)
  679.         Fax3FlushBits(tif, sp);
  680. }
  681.  
  682. /*
  683.  * Write a code to the output stream.
  684.  */
  685. static void
  686. putcode(TIFF* tif, const tableentry* te)
  687. {
  688.     Fax3PutBits(tif, te->code, te->length);
  689. }
  690.  
  691. /*
  692.  * Write the sequence of codes that describes
  693.  * the specified span of zero's or one's.  The
  694.  * appropriate table that holds the make-up and
  695.  * terminating codes is supplied.
  696.  */
  697. static void
  698. putspan(TIFF* tif, int span, const tableentry* tab)
  699. {
  700.     while (span >= 2624) {
  701.         const tableentry *te = &tab[63 + (2560>>6)];
  702.         putcode(tif, te);
  703.         span -= te->runlen;
  704.     }
  705.     if (span >= 64) {
  706.         const tableentry *te = &tab[63 + (span>>6)];
  707.         assert(te->runlen == 64*(span>>6));
  708.         putcode(tif, te);
  709.         span -= te->runlen;
  710.     }
  711.     putcode(tif, &tab[span]);
  712. }
  713.  
  714. /*
  715.  * Write an EOL code to the output stream.  The zero-fill
  716.  * logic for byte-aligning encoded scanlines is handled
  717.  * here.  We also handle writing the tag bit for the next
  718.  * scanline when doing 2d encoding.
  719.  */
  720. void
  721. Fax3PutEOL(TIFF* tif)
  722. {
  723.     Fax3BaseState *sp = (Fax3BaseState *)tif->tif_data;
  724.  
  725.     if (tif->tif_dir.td_group3options & GROUP3OPT_FILLBITS) {
  726.         /*
  727.          * Force bit alignment so EOL will terminate on
  728.          * a byte boundary.  That is, force the bit alignment
  729.          * to 16-12 = 4 before putting out the EOL code.
  730.          */
  731.         int align = 8 - 4;
  732.         if (align != sp->bit) {
  733.             if (align > sp->bit)
  734.                 align = sp->bit + (8 - align);
  735.             else
  736.                 align = sp->bit - align;
  737.             Fax3PutBits(tif, 0, align);
  738.         }
  739.     }
  740.     Fax3PutBits(tif, EOL, 12);
  741.     if (is2DEncoding(tif))
  742.         Fax3PutBits(tif, sp->tag == G3_1D, 1);
  743. }
  744.  
  745. static const u_char zeroruns[256] = {
  746.     8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,    /* 0x00 - 0x0f */
  747.     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,    /* 0x10 - 0x1f */
  748.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0x20 - 0x2f */
  749.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0x30 - 0x3f */
  750.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x40 - 0x4f */
  751.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x50 - 0x5f */
  752.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x60 - 0x6f */
  753.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x70 - 0x7f */
  754.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x80 - 0x8f */
  755.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x90 - 0x9f */
  756.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xa0 - 0xaf */
  757.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xb0 - 0xbf */
  758.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xc0 - 0xcf */
  759.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xd0 - 0xdf */
  760.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xe0 - 0xef */
  761.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xf0 - 0xff */
  762. };
  763. static const u_char oneruns[256] = {
  764.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x00 - 0x0f */
  765.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x10 - 0x1f */
  766.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x20 - 0x2f */
  767.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x30 - 0x3f */
  768.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x40 - 0x4f */
  769.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x50 - 0x5f */
  770.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x60 - 0x6f */
  771.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x70 - 0x7f */
  772.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x80 - 0x8f */
  773.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x90 - 0x9f */
  774.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0xa0 - 0xaf */
  775.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0xb0 - 0xbf */
  776.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0xc0 - 0xcf */
  777.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0xd0 - 0xdf */
  778.     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,    /* 0xe0 - 0xef */
  779.     4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7, 8,    /* 0xf0 - 0xff */
  780. };
  781.  
  782. /*
  783.  * Reset encoding state at the start of a strip.
  784.  */
  785. static
  786. Fax3PreEncode(TIFF* tif)
  787. {
  788.     Fax3EncodeState *sp = (Fax3EncodeState *)tif->tif_data;
  789.  
  790.     if (sp == NULL) {
  791.         sp = (Fax3EncodeState *)Fax3SetupState(tif, sizeof (*sp));
  792.         if (!sp)
  793.             return (0);
  794.         if (sp->b.white == 0) {
  795.             sp->wruns = zeroruns;
  796.             sp->bruns = oneruns;
  797.         } else {
  798.             sp->wruns = oneruns;
  799.             sp->bruns = zeroruns;
  800.         }
  801.     }
  802.     sp->b.bit = 8;
  803.     sp->b.data = 0;
  804.     sp->b.tag = G3_1D;
  805.     /*
  806.      * This is necessary for Group 4; otherwise it isn't
  807.      * needed because the first scanline of each strip ends
  808.      * up being copied into the refline.
  809.      */
  810.     if (sp->b.refline)
  811.         memset(sp->b.refline, sp->b.white ? 0xff:0x00, sp->b.rowbytes);
  812.     if (is2DEncoding(tif)) {
  813.         float res = tif->tif_dir.td_yresolution;
  814.         /*
  815.          * The CCITT spec says that when doing 2d encoding, you
  816.          * should only do it on K consecutive scanlines, where K
  817.          * depends on the resolution of the image being encoded
  818.          * (2 for <= 200 lpi, 4 for > 200 lpi).  Since the directory
  819.          * code initializes td_yresolution to 0, this code will
  820.          * select a K of 2 unless the YResolution tag is set
  821.          * appropriately.  (Note also that we fudge a little here
  822.          * and use 150 lpi to avoid problems with units conversion.)
  823.          */
  824.         if (tif->tif_dir.td_resolutionunit == RESUNIT_CENTIMETER)
  825.             res = (res * .3937) / 2.54;    /* convert to inches */
  826.         sp->maxk = (res > 150 ? 4 : 2);
  827.         sp->k = sp->maxk-1;
  828.     } else
  829.         sp->k = sp->maxk = 0;
  830.     return (1);
  831. }
  832.  
  833. /*
  834.  * 1d-encode a row of pixels.  The encoding is
  835.  * a sequence of all-white or all-black spans
  836.  * of pixels encoded with Huffman codes.
  837.  */
  838. static int
  839. Fax3Encode1DRow(TIFF* tif, u_char* bp, int bits)
  840. {
  841.     Fax3EncodeState *sp = (Fax3EncodeState *)tif->tif_data;
  842.     int bs = 0, span;
  843.  
  844.     for (;;) {
  845.         span = findspan(&bp, bs, bits, sp->wruns);    /* white span */
  846.         putspan(tif, span, TIFFFaxWhiteCodes);
  847.         bs += span;
  848.         if (bs >= bits)
  849.             break;
  850.         span = findspan(&bp, bs, bits, sp->bruns);    /* black span */
  851.         putspan(tif, span, TIFFFaxBlackCodes);
  852.         bs += span;
  853.         if (bs >= bits)
  854.             break;
  855.     }
  856.     return (1);
  857. }
  858.  
  859. static const tableentry horizcode =
  860.     { 3, 0x1 };        /* 001 */
  861. static const tableentry passcode =
  862.     { 4, 0x1 };        /* 0001 */
  863. static const tableentry vcodes[7] = {
  864.     { 7, 0x03 },    /* 0000 011 */
  865.     { 6, 0x03 },    /* 0000 11 */
  866.     { 3, 0x03 },    /* 011 */
  867.     { 1, 0x1 },        /* 1 */
  868.     { 3, 0x2 },        /* 010 */
  869.     { 6, 0x02 },    /* 0000 10 */
  870.     { 7, 0x02 }        /* 0000 010 */
  871. };
  872.  
  873. /*
  874.  * 2d-encode a row of pixels.  Consult the CCITT
  875.  * documentation for the algorithm.
  876.  */
  877. int
  878. Fax3Encode2DRow(TIFF* tif, u_char* bp, u_char* rp, int bits)
  879. {
  880. #define    PIXEL(buf,ix)    ((((buf)[(ix)>>3]) >> (7-((ix)&7))) & 1)
  881.     short white = ((Fax3BaseState *)tif->tif_data)->white;
  882.     int a0 = 0;
  883.     int a1 = (PIXEL(bp, 0) != white ? 0 : finddiff(bp, 0, bits, white));
  884.     int b1 = (PIXEL(rp, 0) != white ? 0 : finddiff(rp, 0, bits, white));
  885.     int a2, b2;
  886.  
  887.     for (;;) {
  888.         b2 = finddiff(rp, b1, bits, PIXEL(rp,b1));
  889.         if (b2 >= a1) {
  890.             int d = b1 - a1;
  891.             if (!(-3 <= d && d <= 3)) {    /* horizontal mode */
  892.                 a2 = finddiff(bp, a1, bits, PIXEL(bp,a1));
  893.                 putcode(tif, &horizcode);
  894.                 if (a0+a1 == 0 || PIXEL(bp, a0) == white) {
  895.                     putspan(tif, a1-a0, TIFFFaxWhiteCodes);
  896.                     putspan(tif, a2-a1, TIFFFaxBlackCodes);
  897.                 } else {
  898.                     putspan(tif, a1-a0, TIFFFaxBlackCodes);
  899.                     putspan(tif, a2-a1, TIFFFaxWhiteCodes);
  900.                 }
  901.                 a0 = a2;
  902.             } else {            /* vertical mode */
  903.                 putcode(tif, &vcodes[d+3]);
  904.                 a0 = a1;
  905.             }
  906.         } else {                /* pass mode */
  907.             putcode(tif, &passcode);
  908.             a0 = b2;
  909.         }
  910.         if (a0 >= bits)
  911.             break;
  912.         a1 = finddiff(bp, a0, bits, PIXEL(bp,a0));
  913.         b1 = finddiff(rp, a0, bits, !PIXEL(bp,a0));
  914.         b1 = finddiff(rp, b1, bits, PIXEL(bp,a0));
  915.     }
  916.     return (1);
  917. #undef PIXEL
  918. }
  919.  
  920. /*
  921.  * Encode a buffer of pixels.
  922.  */
  923. static int
  924. Fax3Encode(TIFF* tif, tidata_t bp, tsize_t cc, tsample_t s)
  925. {
  926.     Fax3EncodeState *sp = (Fax3EncodeState *)tif->tif_data;
  927.  
  928.     while ((long)cc > 0) {
  929.         Fax3PutEOL(tif);
  930.         if (is2DEncoding(tif)) {
  931.             if (sp->b.tag == G3_1D) {
  932.                 if (!Fax3Encode1DRow(tif, bp, sp->b.rowpixels))
  933.                     return (0);
  934.                 sp->b.tag = G3_2D;
  935.             } else {
  936.                 if (!Fax3Encode2DRow(tif, bp, sp->b.refline, sp->b.rowpixels))
  937.                     return (0);
  938.                 sp->k--;
  939.             }
  940.             if (sp->k == 0) {
  941.                 sp->b.tag = G3_1D;
  942.                 sp->k = sp->maxk-1;
  943.             } else
  944.                 memcpy(sp->b.refline, bp, sp->b.rowbytes);
  945.         } else {
  946.             if (!Fax3Encode1DRow(tif, bp, sp->b.rowpixels))
  947.                 return (0);
  948.         }
  949.         bp += sp->b.rowbytes;
  950.         cc -= sp->b.rowbytes;
  951.         if (cc != 0)
  952.             tif->tif_row++;
  953.     }
  954.     return (1);
  955. }
  956.  
  957. static int
  958. Fax3PostEncode(TIFF* tif)
  959. {
  960.     Fax3BaseState *sp = (Fax3BaseState *)tif->tif_data;
  961.  
  962.     if (sp->bit != 8)
  963.         Fax3FlushBits(tif, sp);
  964.     return (1);
  965. }
  966.  
  967. static void
  968. Fax3Close(TIFF* tif)
  969. {
  970.     if ((tif->tif_options & FAX3_CLASSF) == 0) {    /* append RTC */
  971.         int i;
  972.         for (i = 0; i < 6; i++) {
  973.             Fax3PutBits(tif, EOL, 12);
  974.             if (is2DEncoding(tif))
  975.                 Fax3PutBits(tif, 1, 1);
  976.         }
  977.         (void) Fax3PostEncode(tif);
  978.     }
  979. }
  980.  
  981. static void
  982. Fax3Cleanup(TIFF* tif)
  983. {
  984.     if (tif->tif_data) {
  985.         _TIFFfree(tif->tif_data);
  986.         tif->tif_data = NULL;
  987.     }
  988. }
  989.  
  990. /*
  991.  * Bit handling utilities.
  992.  */
  993.  
  994. /*
  995.  * Find a span of ones or zeros using the supplied
  996.  * table.  The byte-aligned start of the bit string
  997.  * is supplied along with the start+end bit indices.
  998.  * The table gives the number of consecutive ones or
  999.  * zeros starting from the msb and is indexed by byte
  1000.  * value.
  1001.  */
  1002. static int
  1003. findspan(u_char** bpp, int bs, int be, register const u_char* tab)
  1004. {
  1005.     register u_char *bp = *bpp;
  1006.     register int bits = be - bs;
  1007.     register int n, span;
  1008.  
  1009.     /*
  1010.      * Check partial byte on lhs.
  1011.      */
  1012.     if (bits > 0 && (n = (bs & 7))) {
  1013.         span = tab[(*bp << n) & 0xff];
  1014.         if (span > 8-n)        /* table value too generous */
  1015.             span = 8-n;
  1016.         if (span > bits)    /* constrain span to bit range */
  1017.             span = bits;
  1018.         if (n+span < 8)        /* doesn't extend to edge of byte */
  1019.             goto done;
  1020.         bits -= span;
  1021.         bp++;
  1022.     } else
  1023.         span = 0;
  1024.     /*
  1025.      * Scan full bytes for all 1's or all 0's.
  1026.      */
  1027.     while (bits >= 8) {
  1028.         n = tab[*bp];
  1029.         span += n;
  1030.         bits -= n;
  1031.         if (n < 8)        /* end of run */
  1032.             goto done;
  1033.         bp++;
  1034.     }
  1035.     /*
  1036.      * Check partial byte on rhs.
  1037.      */
  1038.     if (bits > 0) {
  1039.         n = tab[*bp];
  1040.         span += (n > bits ? bits : n);
  1041.     }
  1042. done:
  1043.     *bpp = bp;
  1044.     return (span);
  1045. }
  1046.  
  1047. /*
  1048.  * Return the offset of the next bit in the range
  1049.  * [bs..be] that is different from the specified
  1050.  * color.  The end, be, is returned if no such bit
  1051.  * exists.
  1052.  */
  1053. static int
  1054. finddiff(u_char* cp, int bs, int be, int color)
  1055. {
  1056.     cp += bs >> 3;            /* adjust byte offset */
  1057.     return (bs + findspan(&cp, bs, be, color ? oneruns : zeroruns));
  1058. }
  1059.  
  1060. int
  1061. TIFFInitCCITTFax3(TIFF* tif)
  1062. {
  1063.     tif->tif_predecode = Fax3PreDecode;
  1064.     tif->tif_decoderow = Fax3Decode;
  1065.     tif->tif_decodestrip = Fax3Decode;
  1066.     tif->tif_decodetile = Fax3Decode;
  1067.     tif->tif_preencode = Fax3PreEncode;
  1068.     tif->tif_postencode = Fax3PostEncode;
  1069.     tif->tif_encoderow = Fax3Encode;
  1070.     tif->tif_encodestrip = Fax3Encode;
  1071.     tif->tif_encodetile = Fax3Encode;
  1072.     tif->tif_close = Fax3Close;
  1073.     tif->tif_cleanup = Fax3Cleanup;
  1074.     tif->tif_options |= FAX3_CLASSF;    /* default */
  1075.     tif->tif_flags |= TIFF_NOBITREV;    /* we handle bit reversal */
  1076.     return (1);
  1077. }
  1078.