home *** CD-ROM | disk | FTP | other *** search
/ Encyclopedia of Graphics File Formats Companion / GFF_CD.ISO / software / unix / libtiff / lbtif3_3.tar / contrib / fax2ps / faxdecode.c < prev    next >
C/C++ Source or Header  |  1993-08-26  |  22KB  |  766 lines
  1. #ifndef lint
  2. static char rcsid[] = "$Header: /usr/people/sam/tiff/contrib/fax2ps/RCS/faxdecode.c,v 1.16 93/08/26 16:07:40 sam Exp $";
  3. #endif
  4.  
  5. /*
  6.  * Copyright (c) 1991, 1992, 1993 by Sam Leffler.
  7.  * All rights reserved.
  8.  *
  9.  * This file is provided for unrestricted use provided that this
  10.  * legend is included on all tape media and as a part of the
  11.  * software program in whole or part.  Users may copy, modify or
  12.  * distribute this file at will.
  13.  */
  14. #include "defs.h"
  15. #include "t4.h"
  16. #include "g3states.h"
  17.  
  18. Fax3DecodeState fax;
  19.  
  20. static    int decode1DRow(TIFF*, u_char*, int);
  21. static    int decode2DRow(TIFF*, u_char*, int);
  22. static    void fillspan(char*, int, int);
  23. static    void emitcode(TIFF*, int, int, int);
  24. static    int findspan(u_char**, int, int, u_char*);
  25. static    int finddiff(u_char*, int, int);
  26.  
  27. static void
  28. emitcode(TIFF* tif, int dx, int x, int count)
  29. {
  30.     CodeEntry* thisCode;
  31.  
  32.     switch (fax.pass) {
  33.     case 1:    /* count potential code & pair use */
  34.     thisCode = enterCode(x-dx, count);
  35.     thisCode->c.count++;
  36.     if (dopairs) {
  37.         if (fax.lastCode)
  38.         enterPair(fax.lastCode, thisCode)->c.count++;
  39.         fax.lastCode = thisCode;
  40.     }
  41.     break;
  42.     case 2:    /* rescan w/ potential codes */
  43.     thisCode = enterCode(x-dx, count);
  44.     if (fax.lastCode) {
  45.         CodePairEntry* pair = findPair(fax.lastCode, thisCode);
  46.         if (pair) {
  47.         pair->c.count++;
  48.         fax.lastCode = 0;
  49.         } else {
  50.         fax.lastCode->c.count++;
  51.         fax.lastCode = thisCode;
  52.         }
  53.     } else
  54.         fax.lastCode = thisCode;
  55.     break;
  56.     case 3:    /* generate encoded output */
  57.     thisCode = enterCode(x-dx, count);
  58.     if (dopairs) {
  59.         if (fax.lastCode) {
  60.         if (!printPair(tif, fax.lastCode, thisCode)) {
  61.             printCode(tif, fax.lastCode);
  62.             fax.lastCode = thisCode;
  63.         } else
  64.             fax.lastCode = 0;
  65.         } else
  66.         fax.lastCode = thisCode;
  67.     } else
  68.         printCode(tif, thisCode);
  69.     break;
  70.     }
  71. }
  72.  
  73. static u_char bitMask[8] =
  74.     { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
  75. #define    isBitSet(sp)    ((sp)->b.data & bitMask[(sp)->b.bit])
  76.  
  77. #define    is2DEncoding(tif)    (fax.is2d)
  78. #define    fetchByte(tif, sp)    (fax.cc--, *fax.bp++)
  79.  
  80. #define    BITCASE(b)            \
  81.     case b:                \
  82.     code <<= 1;                \
  83.     if (data & (1<<(7-b))) code |= 1;    \
  84.     len++;                \
  85.     if (code > 0) { bit = b+1; break; }
  86.  
  87. /*
  88.  * Skip over input until an EOL code is found.  The
  89.  * value of len is passed as 0 except during error
  90.  * recovery when decoding 2D data.  Note also that
  91.  * we don't use the optimized state tables to locate
  92.  * an EOL because we can't assume much of anything
  93.  * about our state (e.g. bit position).
  94.  */
  95. static void
  96. skiptoeol(TIFF* tif, int len)
  97. {
  98.     Fax3DecodeState *sp = &fax;
  99.     register int bit = sp->b.bit;
  100.     register int data = sp->b.data;
  101.     int code = 0;
  102.  
  103.     /*
  104.      * Our handling of ``bit'' is painful because
  105.      * the rest of the code does not maintain it as
  106.      * exactly the bit offset in the current data
  107.      * byte (bit == 0 means refill the data byte).
  108.      * Thus we have to be careful on entry and
  109.      * exit to insure that we maintain a value that's
  110.      * understandable elsewhere in the decoding logic.
  111.      */
  112.     if (bit == 0)            /* force refill */
  113.         bit = 8;
  114.     for (;;) {
  115.         switch (bit) {
  116. again:  BITCASE(0);
  117.         BITCASE(1);
  118.         BITCASE(2);
  119.         BITCASE(3);
  120.         BITCASE(4);
  121.         BITCASE(5);
  122.         BITCASE(6);
  123.         BITCASE(7);
  124.         default:
  125.             if (fax.cc <= 0)
  126.                 return;
  127.             data = fetchByte(tif, sp);
  128.             goto again;
  129.         }
  130.         if (len >= 12 && code == EOL)
  131.             break;
  132.         code = len = 0;
  133.     }
  134.     sp->b.bit = bit > 7 ? 0 : bit;    /* force refill */
  135.     sp->b.data = data;
  136. }
  137.  
  138. /*
  139.  * Return the next bit in the input stream.  This is
  140.  * used to extract 2D tag values and the color tag
  141.  * at the end of a terminating uncompressed data code.
  142.  */
  143. static int
  144. nextbit(TIFF* tif)
  145. {
  146.     Fax3DecodeState *sp = &fax;
  147.     int bit;
  148.  
  149.     if (sp->b.bit == 0 && fax.cc > 0)
  150.         sp->b.data = fetchByte(tif, sp);
  151.     bit = isBitSet(sp);
  152.     if (++(sp->b.bit) > 7)
  153.         sp->b.bit = 0;
  154.     return (bit);
  155. }
  156.  
  157. /*
  158.  * Setup state for decoding a strip.
  159.  */
  160. int
  161. FaxPreDecode(TIFF* tif)
  162. {
  163.     Fax3DecodeState *sp = &fax;
  164.  
  165.     sp->b.bit = 0;            /* force initial read */
  166.     sp->b.data = 0;
  167.     sp->b.tag = G3_1D;
  168.     if (sp->b.refline)
  169.         memset(sp->b.refline, sp->b.white ? 0xff : 0x00, sp->b.rowbytes);
  170.     /*
  171.      * If image has EOL codes, they precede each line
  172.      * of data.  We skip over the first one here so that
  173.      * when we decode rows, we can use an EOL to signal
  174.      * that less than the expected number of pixels are
  175.      * present for the scanline.
  176.      */
  177.     if ((fax.options & FAX3_NOEOL) == 0) {
  178.         skiptoeol(tif, 0);
  179.         if (is2DEncoding(tif))
  180.             /* tag should always be 1D! */
  181.             sp->b.tag = nextbit(tif) ? G3_1D : G3_2D;
  182.     }
  183.     return (1);
  184. }
  185.  
  186. /*
  187.  * Fill a span with ones.
  188.  */
  189. static void
  190. fillspan(register char* cp, register int x, register int count)
  191. {
  192.     static unsigned char masks[] =
  193.         { 0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff };
  194.  
  195.     if (count <= 0)
  196.         return;
  197.     cp += x>>3;
  198.     if (x &= 7) {            /* align to byte boundary */
  199.         if (count < 8 - x) {
  200.             *cp++ |= masks[count] >> x;
  201.             return;
  202.         }
  203.         *cp++ |= 0xff >> x;
  204.         count -= 8 - x;
  205.     }
  206.     while (count >= 8) {
  207.         *cp++ = 0xff;
  208.         count -= 8;
  209.     }
  210.     *cp |= masks[count];
  211. }
  212.  
  213. /*
  214.  * Decode the requested amount of data.
  215.  */
  216. int
  217. Fax3DecodeRow(TIFF* tif, int npels)
  218. {
  219.     Fax3DecodeState *sp = &fax;
  220.  
  221.     fax.lastCode = 0;
  222.     while (npels > 0) {
  223.     /* decoding only sets non-zero bits */
  224.     memset(sp->scanline, 0, sp->b.rowbytes);
  225.         if (sp->b.tag == G3_1D) {
  226.             if (!decode1DRow(tif, sp->scanline, sp->b.rowpixels) && fax.cc <= 0)
  227.         break;
  228.         } else {
  229.             if (!decode2DRow(tif, sp->scanline, sp->b.rowpixels) && fax.cc <= 0)
  230.         break;
  231.         }
  232.         if (is2DEncoding(tif)) {
  233.             /*
  234.              * Fetch the tag bit that indicates
  235.              * whether the next row is 1d or 2d
  236.              * encoded.  If 2d-encoded, then setup
  237.              * the reference line from the decoded
  238.              * scanline just completed.
  239.              */
  240.             sp->b.tag = nextbit(tif) ? G3_1D : G3_2D;
  241.             if (sp->b.tag == G3_2D)
  242.                 memcpy(sp->b.refline, sp->scanline, sp->b.rowbytes);
  243.         }
  244.         npels -= sp->b.rowpixels;
  245.     fax.row++;
  246.     }
  247.     switch (sp->pass) {
  248.     case 2:
  249.     if (fax.lastCode)
  250.         fax.lastCode->c.count++;
  251.     break;
  252.     case 3:
  253.     if (fax.lastCode)
  254.         printCode(tif, fax.lastCode);
  255.     break;
  256.     }
  257.     return (npels == 0);
  258. }
  259.  
  260. int
  261. Fax4DecodeRow(TIFF* tif, int npels)
  262. {
  263.     Fax3DecodeState *sp = &fax;
  264.  
  265.     fax.lastCode = 0;
  266.     while (npels > 0) {
  267.     /* decoding only sets non-zero bits */
  268.     memset(sp->scanline, 0, sp->b.rowbytes);
  269.     if (!decode2DRow(tif, sp->scanline, sp->b.rowpixels))
  270.         return (0);
  271.     memcpy(sp->b.refline, sp->scanline, sp->b.rowbytes);
  272.     fax.row++;
  273.         npels -= sp->b.rowpixels;
  274.     }
  275.     switch (sp->pass) {
  276.     case 2:
  277.     if (fax.lastCode)
  278.         fax.lastCode->c.count++;
  279.     break;
  280.     case 3:
  281.     if (fax.lastCode)
  282.         printCode(tif, fax.lastCode);
  283.     break;
  284.     }
  285.     return (1);
  286. }
  287.  
  288. /*
  289.  * Decode a run of white.
  290.  */
  291. static int
  292. decode_white_run(TIFF* tif)
  293. {
  294.     Fax3DecodeState *sp = &fax;
  295.     short state = sp->b.bit;
  296.     short action;
  297.     int runlen = 0;
  298.  
  299.     for (;;) {
  300.         if (sp->b.bit == 0) {
  301.     nextbyte:
  302.             if (fax.cc <= 0)
  303.                 return (G3CODE_EOF);
  304.             sp->b.data = fetchByte(tif, sp);
  305.         }
  306.         action = TIFFFax1DAction[state][sp->b.data];
  307.         state = TIFFFax1DNextState[state][sp->b.data];
  308.         if (action == ACT_INCOMP)
  309.             goto nextbyte;
  310.         if (action == ACT_INVALID)
  311.             return (G3CODE_INVALID);
  312.         if (action == ACT_EOL)
  313.             return (G3CODE_EOL);
  314.         sp->b.bit = state;
  315.         action = RUNLENGTH(action - ACT_WRUNT);
  316.         runlen += action;
  317.         if (action < 64)
  318.             return (runlen);
  319.     }
  320.     /*NOTREACHED*/
  321. }
  322.  
  323. /*
  324.  * Decode a run of black.
  325.  */
  326. static int
  327. decode_black_run(TIFF* tif)
  328. {
  329.     Fax3DecodeState *sp = &fax;
  330.     short state = sp->b.bit + 8;
  331.     short action;
  332.     int runlen = 0;
  333.  
  334.     for (;;) {
  335.         if (sp->b.bit == 0) {
  336.     nextbyte:
  337.             if (fax.cc <= 0)
  338.                 return (G3CODE_EOF);
  339.             sp->b.data = fetchByte(tif, sp);
  340.         }
  341.         action = TIFFFax1DAction[state][sp->b.data];
  342.         state = TIFFFax1DNextState[state][sp->b.data];
  343.         if (action == ACT_INCOMP)
  344.             goto nextbyte;
  345.         if (action == ACT_INVALID)
  346.             return (G3CODE_INVALID);
  347.         if (action == ACT_EOL)
  348.             return (G3CODE_EOL);
  349.         sp->b.bit = state;
  350.         action = RUNLENGTH(action - ACT_BRUNT);
  351.         runlen += action;
  352.         if (action < 64)
  353.             return (runlen);
  354.         state += 8;
  355.     }
  356.     /*NOTREACHED*/
  357. }
  358.  
  359. /*
  360.  * Process one row of 1d Huffman-encoded data.
  361.  */
  362. static int
  363. decode1DRow(TIFF* tif, u_char* buf, int npels)
  364. {
  365.     Fax3DecodeState *sp = &fax;
  366.     int x = 0;
  367.     int dx = 0;
  368.     int runlen;
  369.     short action;
  370.     short color = sp->b.white;
  371.     static char module[] = "Fax3Decode1D";
  372.  
  373.     for (;;) {
  374.         if (color == sp->b.white)
  375.             runlen = decode_white_run(tif);
  376.         else
  377.             runlen = decode_black_run(tif);
  378.         switch (runlen) {
  379.         case G3CODE_EOF:
  380.             TIFFError(module,
  381.                 "%s: Premature EOF at scanline %d (x %d)",
  382.                 TIFFFileName(tif), fax.row, x);
  383.             return (0);
  384.         case G3CODE_INVALID:    /* invalid code */
  385.             /*
  386.              * An invalid code was encountered.
  387.              * Flush the remainder of the line
  388.              * and allow the caller to decide whether
  389.              * or not to continue.  Note that this
  390.              * only works if we have a G3 image
  391.              * with EOL markers.
  392.              */
  393.             TIFFError(TIFFFileName(tif),
  394.                "%s: Bad code word at scanline %d (x %d)",
  395.                module, fax.row, x);
  396.             goto done;
  397.         case G3CODE_EOL:    /* premature end-of-line code */
  398.             TIFFWarning(TIFFFileName(tif),
  399.                 "%s: Premature EOL at scanline %d (x %d)",
  400.                 module, fax.row, x);
  401.             return (1);    /* try to resynchronize... */
  402.         }
  403.         if (x+runlen > npels)
  404.             runlen = npels-x;
  405.         if (runlen > 0) {
  406.             if (color)
  407.                 fillspan((char *)buf, x, runlen);
  408.         if (color != sp->b.white) {
  409.         emitcode(tif, dx, x, runlen);
  410.         dx = x+runlen;
  411.         }
  412.             x += runlen;
  413.             if (x >= npels)
  414.                 break;
  415.         }
  416.         color = !color;
  417.     }
  418. done:
  419.     /*
  420.      * Cleanup at the end of the row.  This convoluted
  421.      * logic is merely so that we can reuse the code with
  422.      * two other related compression algorithms (2 & 32771).
  423.      *
  424.      * Note also that our handling of word alignment assumes
  425.      * that the buffer is at least word aligned.  This is
  426.      * the case for most all versions of malloc (typically
  427.      * the buffer is returned longword aligned).
  428.      */
  429.     if ((fax.options & FAX3_NOEOL) == 0)
  430.         skiptoeol(tif, 0);
  431.     if (fax.options & FAX3_BYTEALIGN)
  432.         sp->b.bit = 0;
  433.     if ((fax.options & FAX3_WORDALIGN) && ((long)fax.bp & 1))
  434.         (void) fetchByte(tif, sp);
  435.     return (x == npels);
  436. }
  437.  
  438. /*
  439.  * Group 3 2d Decoding support.
  440.  */
  441.  
  442. /*
  443.  * Return the next uncompressed mode code word.
  444.  */
  445. static int
  446. decode_uncomp_code(TIFF* tif)
  447. {
  448.     Fax3DecodeState *sp = &fax;
  449.     short code;
  450.  
  451.     do {
  452.         if (sp->b.bit == 0 || sp->b.bit > 7) {
  453.             if (fax.cc <= 0)
  454.                 return (UNCOMP_EOF);
  455.             sp->b.data = fetchByte(tif, sp);
  456.         }
  457.         code = TIFFFaxUncompAction[sp->b.bit][sp->b.data];
  458.         sp->b.bit = TIFFFaxUncompNextState[sp->b.bit][sp->b.data];
  459.     } while (code == ACT_INCOMP);
  460.     return (code);
  461. }
  462.  
  463. /*
  464.  * Process one row of 2d encoded data.
  465.  */
  466. static int
  467. decode2DRow(TIFF* tif, u_char* buf, int npels)
  468. {
  469. #define    PIXEL(buf,ix)    ((((buf)[(ix)>>3]) >> (7-((ix)&7))) & 1)
  470.     Fax3DecodeState *sp = &fax;
  471.     int a0 = 0;
  472.     int b1 = 0;
  473.     int b2 = 0;
  474.     int dx = 0;
  475.     int run1, run2;        /* for horizontal mode */
  476.     short mode;
  477.     short color = sp->b.white;
  478.     static char module[] = "Fax3Decode2D";
  479.  
  480.     do {
  481.         if (sp->b.bit == 0 || sp->b.bit > 7) {
  482.             if (fax.cc <= 0) {
  483.                 TIFFError(module,
  484.                 "%s: Premature EOF at scanline %d",
  485.                     TIFFFileName(tif), fax.row);
  486.                 return (0);
  487.             }
  488.             sp->b.data = fetchByte(tif, sp);
  489.         }
  490.         mode = TIFFFax2DMode[sp->b.bit][sp->b.data];
  491.         sp->b.bit = TIFFFax2DNextState[sp->b.bit][sp->b.data];
  492.         switch (mode) {
  493.         case MODE_NULL:
  494.             break;
  495.         case MODE_PASS:
  496.             if (a0 || PIXEL(sp->b.refline, 0) == color) {
  497.                 b1 = finddiff(sp->b.refline, a0, npels);
  498.                 if (color == PIXEL(sp->b.refline, b1))
  499.                     b1 = finddiff(sp->b.refline, b1, npels);
  500.             } else
  501.                 b1 = 0;
  502.             b2 = finddiff(sp->b.refline, b1, npels);
  503.             if (color)
  504.                 fillspan((char *)buf, a0, b2 - a0);
  505.         if (color != sp->b.white) {
  506.         emitcode(tif, dx, a0, b2 - a0);
  507.         dx = b2;
  508.         }
  509.             a0 += b2 - a0;
  510.             break;
  511.         case MODE_HORIZ:
  512.             if (color == sp->b.white) {
  513.                 run1 = decode_white_run(tif);
  514.                 run2 = decode_black_run(tif);
  515.             } else {
  516.                 run1 = decode_black_run(tif);
  517.                 run2 = decode_white_run(tif);
  518.             }
  519.         /*
  520.          * Do the appropriate fill.  Note that we exit
  521.          * this logic with the same color that we enter
  522.          * with since we do 2 fills.  This explains the
  523.          * somewhat obscure logic below.
  524.          */
  525.         if (run1 < 0)
  526.         goto bad;
  527.         if (a0 + run1 > npels)
  528.         run1 = npels - a0;
  529.         if (color)
  530.         fillspan((char *)buf, a0, run1);
  531.         if (color != sp->b.white) {
  532.         emitcode(tif, dx, a0, run1);
  533.         dx = a0 + run1;
  534.         }
  535.         a0 += run1;
  536.         if (run2 < 0)
  537.         goto bad;
  538.         if (a0 + run2 > npels)
  539.         run2 = npels - a0;
  540.         if (!color)
  541.         fillspan((char *)buf, a0, run2);
  542.         if (!color != sp->b.white) {
  543.         emitcode(tif, dx, a0, run2);
  544.         dx = a0 + run2;
  545.         }
  546.         a0 += run2;
  547.             break;
  548.         case MODE_VERT_V0:
  549.         case MODE_VERT_VR1:
  550.         case MODE_VERT_VR2:
  551.         case MODE_VERT_VR3:
  552.         case MODE_VERT_VL1:
  553.         case MODE_VERT_VL2:
  554.         case MODE_VERT_VL3:
  555.             /*
  556.              * Calculate b1 as the "first changing element
  557.              * on the reference line to right of a0 and of
  558.              * opposite color to a0".  In addition, "the
  559.              * first starting picture element a0 of each
  560.              * coding line is imaginarily set at a position
  561.              * just before the first picture element, and
  562.              * is regarded as a white element".  For us,
  563.              * the condition (a0 == 0 && color == sp->b.white)
  564.              * describes this initial condition. 
  565.              */
  566.             if (!(a0 == 0 &&
  567.         color == sp->b.white && PIXEL(sp->b.refline, 0) != sp->b.white)) {
  568.                 b1 = finddiff(sp->b.refline, a0, npels);
  569.                 if (color == PIXEL(sp->b.refline, b1))
  570.                     b1 = finddiff(sp->b.refline, b1, npels);
  571.             } else
  572.                 b1 = 0;
  573.             b1 += mode - MODE_VERT_V0;
  574.             if (color)
  575.                 fillspan((char *)buf, a0, b1 - a0);
  576.         if (color != sp->b.white) {
  577.         emitcode(tif, dx, a0, b1 - a0);
  578.         dx = b1;
  579.         }
  580.             color = !color;
  581.             a0 += b1 - a0;
  582.             break;
  583.     case MODE_UNCOMP:
  584.             /*
  585.              * Uncompressed mode: select from the
  586.              * special set of code words.
  587.              */
  588.             do {
  589.                 mode = decode_uncomp_code(tif);
  590.                 switch (mode) {
  591.                 case UNCOMP_RUN1:
  592.                 case UNCOMP_RUN2:
  593.                 case UNCOMP_RUN3:
  594.                 case UNCOMP_RUN4:
  595.                 case UNCOMP_RUN5:
  596.                     run1 = mode - UNCOMP_RUN0;
  597.                     fillspan((char *)buf, a0+run1-1, 1);
  598.                     a0 += run1;
  599.             if (color != sp->b.white) {
  600.             emitcode(tif, dx, a0-1, 1);
  601.             dx = a0;
  602.             }
  603.                     break;
  604.                 case UNCOMP_RUN6:
  605.                     a0 += 5;
  606.                     break;
  607.                 case UNCOMP_TRUN0:
  608.                 case UNCOMP_TRUN1:
  609.                 case UNCOMP_TRUN2:
  610.                 case UNCOMP_TRUN3:
  611.                 case UNCOMP_TRUN4:
  612.                     run1 = mode - UNCOMP_TRUN0;
  613.                     a0 += run1;
  614.                     color = nextbit(tif) ? !sp->b.white : sp->b.white;
  615.                     break;
  616.                 case UNCOMP_INVALID:
  617.                     TIFFError(module,
  618.                 "%s: Bad uncompressed code word at scanline %d",
  619.                         TIFFFileName(tif), fax.row);
  620.                     goto bad;
  621.                 case UNCOMP_EOF:
  622.                     TIFFError(module,
  623.                         "%s: Premature EOF at scanline %d",
  624.                         TIFFFileName(tif), fax.row);
  625.                     return (0);
  626.                 }
  627.             } while (mode < UNCOMP_EXIT);
  628.             break;
  629.     case MODE_ERROR_1:
  630.             if ((fax.options & FAX3_NOEOL) == 0) {
  631.                 TIFFWarning(TIFFFileName(tif),
  632.                     "%s: Premature EOL at scanline %d (x %d)",
  633.                     module, fax.row, a0);
  634.                 skiptoeol(tif, 7);    /* seen 7 0's already */
  635.                 return (1);        /* try to synchronize */
  636.             }
  637.             /* fall thru... */
  638.     case MODE_ERROR:
  639.             TIFFError(TIFFFileName(tif),
  640.                 "%s: Bad 2D code word at scanline %d",
  641.                 module, fax.row);
  642.             goto bad;
  643.     default:
  644.             TIFFError(TIFFFileName(tif),
  645.                 "%s: Panic, bad decoding state at scanline %d",
  646.                 module, fax.row);
  647.             return (0);
  648.         }
  649.     } while (a0 < npels);
  650. bad:
  651.     /*
  652.      * Cleanup at the end of row.  We check for
  653.      * EOL separately so that this code can be
  654.      * reused by the Group 4 decoding routine.
  655.      */
  656.     if ((fax.options & FAX3_NOEOL) == 0)
  657.         skiptoeol(tif, 0);
  658.     return (a0 >= npels);
  659. #undef    PIXEL
  660. }
  661.  
  662. static u_char zeroruns[256] = {
  663.     8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,    /* 0x00 - 0x0f */
  664.     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,    /* 0x10 - 0x1f */
  665.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0x20 - 0x2f */
  666.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0x30 - 0x3f */
  667.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x40 - 0x4f */
  668.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x50 - 0x5f */
  669.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x60 - 0x6f */
  670.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x70 - 0x7f */
  671.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x80 - 0x8f */
  672.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x90 - 0x9f */
  673.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xa0 - 0xaf */
  674.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xb0 - 0xbf */
  675.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xc0 - 0xcf */
  676.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xd0 - 0xdf */
  677.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xe0 - 0xef */
  678.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xf0 - 0xff */
  679. };
  680. static u_char oneruns[256] = {
  681.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x00 - 0x0f */
  682.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x10 - 0x1f */
  683.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x20 - 0x2f */
  684.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x30 - 0x3f */
  685.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x40 - 0x4f */
  686.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x50 - 0x5f */
  687.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x60 - 0x6f */
  688.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x70 - 0x7f */
  689.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x80 - 0x8f */
  690.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x90 - 0x9f */
  691.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0xa0 - 0xaf */
  692.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0xb0 - 0xbf */
  693.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0xc0 - 0xcf */
  694.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0xd0 - 0xdf */
  695.     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,    /* 0xe0 - 0xef */
  696.     4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7, 8,    /* 0xf0 - 0xff */
  697. };
  698.  
  699. /*
  700.  * Bit handling utilities.
  701.  */
  702.  
  703. /*
  704.  * Find a span of ones or zeros using the supplied
  705.  * table.  The byte-aligned start of the bit string
  706.  * is supplied along with the start+end bit indices.
  707.  * The table gives the number of consecutive ones or
  708.  * zeros starting from the msb and is indexed by byte
  709.  * value.
  710.  */
  711. static int
  712. findspan(u_char** bpp, int bs, int be, u_char* tab)
  713. {
  714.     u_char *bp = *bpp;
  715.     int bits = be - bs;
  716.     int n, span;
  717.  
  718.     /*
  719.      * Check partial byte on lhs.
  720.      */
  721.     if (bits > 0 && (n = (bs & 7))) {
  722.     span = tab[(*bp << n) & 0xff];
  723.     if (span > 8-n)        /* table value too generous */
  724.         span = 8-n;
  725.     if (n+span < 8)        /* doesn't extend to edge of byte */
  726.         goto done;
  727.     bits -= span;
  728.     bp++;
  729.     } else
  730.     span = 0;
  731.     /*
  732.      * Scan full bytes for all 1's or all 0's.
  733.      */
  734.     while (bits >= 8) {
  735.     n = tab[*bp];
  736.     span += n;
  737.     bits -= n;
  738.     if (n < 8)        /* end of run */
  739.         goto done;
  740.     bp++;
  741.     }
  742.     /*
  743.      * Check partial byte on rhs.
  744.      */
  745.     if (bits > 0) {
  746.     n = tab[*bp];
  747.     span += (n > bits ? bits : n);
  748.     }
  749. done:
  750.     *bpp = bp;
  751.     return (span);
  752. }
  753.  
  754. /*
  755.  * Return the offset of the next bit in the range
  756.  * [bs..be] that is different from bs.  The end,
  757.  * be, is returned if no such bit exists.
  758.  */
  759. static int
  760. finddiff(u_char* cp, int bs, int be)
  761. {
  762.     cp += bs >> 3;            /* adjust byte offset */
  763.     return (bs + findspan(&cp, bs, be,
  764.     (*cp & (0x80 >> (bs&7))) ? oneruns : zeroruns));
  765. }
  766.