home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-387-Vol-3of3.iso / g / gs252src.zip / GS252 / SCFD.C < prev    next >
C/C++ Source or Header  |  1992-09-17  |  16KB  |  569 lines
  1. /* Copyright (C) 1992 Aladdin Enterprises.  All rights reserved.
  2.    Distributed by Free Software Foundation, Inc.
  3.  
  4. This file is part of Ghostscript.
  5.  
  6. Ghostscript is distributed in the hope that it will be useful, but
  7. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  8. to anyone for the consequences of using it or for whether it serves any
  9. particular purpose or works at all, unless he says so in writing.  Refer
  10. to the Ghostscript General Public License for full details.
  11.  
  12. Everyone is granted permission to copy, modify and redistribute
  13. Ghostscript, but only under the conditions described in the Ghostscript
  14. General Public License.  A copy of this license is supposed to have been
  15. given to you along with Ghostscript so you can know your rights and
  16. responsibilities.  It should be in a file named COPYING.  Among other
  17. things, the copyright notice and this notice must be preserved on all
  18. copies.  */
  19.  
  20. /* scfd.c */
  21. /* CCITTFax decoding filter */
  22. #include "stdio_.h"    /* includes std.h */
  23. #include "memory_.h"
  24. #include "gdebug.h"
  25. #include "scf.h"
  26. #include "stream.h"
  27.  
  28. /* Initialize CCITTFaxDecode filter */
  29. void
  30. s_CFD_init(register stream *s, CCITTFax_state *pcfs)
  31. {    int raster = pcfs->raster;    /* s->cfs isn't set yet! */
  32.     s->cfs = *pcfs;
  33.     if ( s->cfs.K != 0 )
  34.     {    /* Clear the initial reference line for 2-D encoding. */
  35.         s->cptr = s->endptr = s->cbuf + raster * 3 - 1;
  36.         s->cfs.prev_pos = raster * 2;
  37.         memset(s->cbuf + raster * 2, (s->cfs.BlackIs1 ? 0 : 0xff),
  38.                raster);
  39.     }
  40.     s->cfs.k_left = min(s->cfs.K, 0);
  41.     s->cfs.cbit = 0;
  42.     s->cfs.bits = 0;
  43.     s->cfs.bits_left = 0;
  44.     s->cfs.uncomp_run = 0;
  45. }
  46.  
  47. /* Declare the variables that hold the state of the input. */
  48. #define cfd_declare_stream_state\
  49.     stream *strm = s->strm;\
  50.     register byte *inptr;\
  51.     byte *inend
  52. #define cfd_declare_state\
  53.     cfd_declare_stream_state;\
  54.     register byte *p;\
  55.     int pbit;\
  56.     uint bits;\
  57.     int bits_left
  58. /* Load the input state from the stream. */
  59. #define cfd_load_stream_state()\
  60.     inptr = sbufptr(strm), inend = sbufend(strm)
  61. #define cfd_load_state()\
  62.     cfd_load_stream_state(),\
  63.     p = s->cptr, pbit = s->cfs.cbit,\
  64.     bits = s->cfs.bits, bits_left = s->cfs.bits_left
  65. /* Store the input state back in the stream. */
  66. #define cfd_store_stream_state()\
  67.     ssetbufptr(strm, inptr)
  68. #define cfd_store_state()\
  69.     cfd_store_stream_state(),\
  70.     s->cptr = p, s->cfs.cbit = pbit,\
  71.     s->cfs.bits = bits, s->cfs.bits_left = bits_left
  72.  
  73. /* Macros to get blocks of bits from the input stream. */
  74. /* Invariants: 0 <= bits_left <= bits_size; */
  75. /* bits [bits_left-1..0] contain valid data. */
  76. #define bits_size (arch_sizeof_int * 8) /* avoid sizeof so is constant */
  77. /* n must not be greater than 8. */
  78. #define ensure_bits(n)\
  79.   if ( bits_left < n ) more_bits()
  80. #define more_bits_1()\
  81.   { int c;\
  82.     if ( inptr < inend ) c = *inptr++;\
  83.     else { cfd_store_stream_state(); c = sgetc(strm); cfd_load_stream_state(); }\
  84.     if ( c < 0 ) { s->end_status = c; goto out; }\
  85.     bits = (bits << 8) + c, bits_left += 8;\
  86.   }
  87. #if bits_size == 16
  88. #  define more_bits() more_bits_1()
  89. #else                /* bits_size >= 32 */
  90. #  define more_bits()\
  91.   { if ( inend - inptr < 3 ) more_bits_1()\
  92.     else\
  93.     { bits = (bits << 24) + ((uint)inptr[0] << 16) + ((uint)inptr[1] << 8) + inptr[2];\
  94.       bits_left += 24, inptr += 3;\
  95.     }\
  96.   }
  97. #endif
  98. #define peek_bits(n) ((bits >> (bits_left - (n))) & ((1 << (n)) - 1))
  99. #define peek_var_bits(n) ((bits >> (bits_left - (n))) & peek_masks[n])
  100. static const byte peek_masks[9] = { 0, 1, 3, 7, 0xf, 0x1f, 0x3f, 0x7f, 0xff };
  101. #define skip_bits(n) bits_left -= (n)
  102.  
  103. /* Get a run from the stream. */
  104. #define get_run(decode, initial_bits, runlen, str)\
  105. {    const cfd_node _ds *np;\
  106.     int clen;\
  107.     ensure_bits(initial_bits);\
  108.     np = &decode[peek_bits(initial_bits)];\
  109.     if ( (clen = np->code_length) > initial_bits )\
  110.     {    do_debug(uint init_bits = peek_bits(initial_bits));\
  111.         clen -= initial_bits;\
  112.         skip_bits(initial_bits);\
  113.         ensure_bits(clen);\
  114.         np = &decode[np->run_length + peek_var_bits(clen)];\
  115.         if_debug4('W', "%s clen=%d xcode=0x%x rlen=%d\n", str,\
  116.               initial_bits + np->code_length,\
  117.               (init_bits << np->code_length) +\
  118.                   peek_var_bits(np->code_length),\
  119.               np->run_length);\
  120.         skip_bits(np->code_length);\
  121.     }\
  122.     else\
  123.     {    if_debug4('W', "%s clen=%d code=0x%x rlen=%d\n", str,\
  124.               clen, peek_var_bits(clen), np->run_length);\
  125.         skip_bits(clen);\
  126.     }\
  127.     runlen = np->run_length;\
  128. }
  129.  
  130. /* Skip data bits for a white run. */
  131. /* rlen is either less than 64, or a multiple of 64. */
  132. #define skip_data(rlen, makeup_label)\
  133.     if ( (pbit -= rlen) < 0 )\
  134.     {    p -= pbit >> 3, pbit &= 7;\
  135.         if ( rlen >= 64 ) goto makeup_label;\
  136.     }
  137.  
  138. /* Invert data bits for a black run. */
  139. /* If rlen >= 64, execute makeup_action: this is to handle */
  140. /* makeup codes efficiently, since these are always a multiple of 64. */
  141. #define invert_data(rlen, black_byte, makeup_action, d)\
  142.     if ( rlen > pbit )\
  143.     {    *p++ ^= (1 << pbit) - 1;\
  144.         rlen -= pbit;\
  145.         switch ( rlen >> 3 )\
  146.         {\
  147.         default:    /* original rlen >= 64 */\
  148. d:            memset(p, black_byte, rlen >> 3);\
  149.             p += rlen >> 3;\
  150.             rlen &= 7;\
  151.             if ( !rlen ) pbit = 0, p--;\
  152.             else pbit = 8 - rlen, *p ^= 0xff << pbit;\
  153.             makeup_action;\
  154.             break;\
  155.         case 7:        /* original rlen possibly >= 64 */\
  156.             if ( rlen + pbit >= 64 ) goto d;\
  157.             *p++ = black_byte;\
  158.         case 6: *p++ = black_byte;\
  159.         case 5: *p++ = black_byte;\
  160.         case 4: *p++ = black_byte;\
  161.         case 3: *p++ = black_byte;\
  162.         case 2: *p++ = black_byte;\
  163.         case 1: *p = black_byte;\
  164.             rlen &= 7;\
  165.             if ( !rlen ) { pbit = 0; break; }\
  166.             p++;\
  167.         case 0:            /* know rlen != 0 */\
  168.             pbit = 8 - rlen;\
  169.             *p ^= 0xff << pbit;\
  170.         }\
  171.     }\
  172.     else\
  173.         pbit -= rlen,\
  174.         *p ^= ((1 << rlen) - 1) << pbit
  175.  
  176. /* Buffer refill for CCITTFaxDecode filter */
  177. private int cf_decode_1d(P1(stream *));
  178. private int cf_decode_2d(P2(stream *, byte *));
  179. private int cf_decode_uncompressed(P1(stream *));
  180. private int
  181. s_CFD_read_buf(register stream *s)
  182. {    cfd_declare_stream_state;
  183.     int raster = s->cfs.raster;
  184.     register byte *p = s->cbuf - 1;
  185.     byte *prev = p + s->cfs.prev_pos;
  186.     byte *limit = p + s->bsize;
  187.     int k_left = s->cfs.k_left;
  188.     cfd_load_stream_state();
  189.     /* Do complete scan lines. */
  190.     while ( limit - p >= raster )
  191.     {    uint bits = s->cfs.bits;
  192.         int bits_left = s->cfs.bits_left;
  193.         int code;
  194.         if ( s->cfs.EncodedByteAlign )
  195.             bits_left &= ~7;
  196.         /* Check for an initial EOL code. */
  197.         /* In 16-bit environments, we can't look at */
  198.         /* the entire EOL code simultaneously; */
  199.         /* having two separate algorithms isn't worth the trouble. */
  200.         ensure_bits(8);
  201.         /* Read an extra byte, and put it back if needed. */
  202.         if ( peek_bits(8) != 0 ) goto ne;
  203.         skip_bits(8);
  204.         more_bits_1();
  205.         if ( peek_bits(run_eol_code_length-9) != 0 )
  206.         {    /* Undo the more_bits_1() */
  207.             bits >>= 8;
  208.             bits_left -= 8;
  209.             inptr--;    /*sputback(strm)*/
  210.             goto ne;
  211.         }
  212.         /* Skip over padding and EOL. */
  213.         while ( 1 )
  214.         {    ensure_bits(1);
  215.             if ( peek_bits(1) ) break;
  216.             skip_bits(1);
  217.         }
  218.         skip_bits(1);
  219.         /* If we are in a Group 3 mixed regime, */
  220.         /* check the next bit for 1- vs. 2-D. */
  221.         if ( s->cfs.K > 0 )
  222.         {    ensure_bits(1);
  223.             k_left = (peek_bits(1) ? 0 : 1);
  224.             skip_bits(1);
  225.         }
  226.         goto rd;
  227. ne:        if ( s->cfs.EndOfLine )
  228.         {    /* EOL is required, but none is present. */
  229.             s->end_status = ERRC;
  230.             break;
  231.         }
  232. rd:        s->cptr = p;
  233.         s->cfs.cbit = 0;        /* for now */
  234.         s->cfs.bits = bits;
  235.         s->cfs.bits_left = bits_left;
  236.         cfd_store_stream_state();
  237.         if ( k_left < 0 )
  238.         {    if_debug0('w', "[w2]new row\n");
  239.             code = cf_decode_2d(s, prev);
  240.         }
  241.         else if ( k_left == 0 )
  242.         {    if_debug0('w', "[w1]new row\n");
  243.             code = cf_decode_1d(s);
  244.             k_left = s->cfs.K;
  245.         }
  246.         else
  247.         {    if_debug1('w', "[w1]new 2-D row, %d left\n", k_left);
  248.             code = cf_decode_2d(s, prev);
  249.             k_left--;
  250.         }
  251.         cfd_load_stream_state();
  252.         if ( code < 0 )
  253.         {    s->end_status = ERRC;
  254.             break;
  255.         }
  256.         prev = p;
  257.         p += raster;
  258.     }
  259. out:    cfd_store_stream_state();
  260.     s->cptr = s->cbuf - 1;
  261.     s->endptr = p;
  262.     s->cfs.k_left = k_left;
  263.     s->cfs.prev_pos = prev - s->cptr;
  264.     return 0;
  265. }
  266. /* Decode a 1-D scan line. */
  267. private int
  268. cf_decode_1d(stream *s)
  269. {    cfd_declare_state;
  270.     byte black_byte = (s->cfs.BlackIs1 ? 0xff : 0);
  271.     int end_bit = -s->cfs.Columns & 7;
  272.     int raster = s->cfs.raster;
  273.     byte *stop;
  274.     cfd_load_state();
  275.     stop = p + raster;
  276. #define p_at_stop() (p >= stop && (pbit <= end_bit || p > stop))
  277.     memset(p + 1, ~black_byte, raster);
  278.     while ( !p_at_stop() )
  279.     {    int bcnt;
  280. dw:        /* Decode a white run. */
  281.         get_run(cf_white_decode, cfd_white_initial_bits, bcnt, "[w1]white");
  282.         if ( bcnt < 0 )
  283.                 /* exceptional situation */
  284.           switch ( bcnt )
  285.         {
  286.         case run_uncompressed:    /* Uncompressed data. */
  287.             cfd_store_state();
  288.             bcnt = cf_decode_uncompressed(s);
  289.             if ( bcnt < 0 )
  290.             {    s->end_status = bcnt;
  291.                 goto out;
  292.             }
  293.             cfd_load_state();
  294.             if ( bcnt ) goto db;
  295.             else goto dw;
  296.         /*case run_error:*/
  297.         /*case run_zeros:*/    /* Premature end-of-line. */
  298.         default:
  299.             s->end_status = ERRC;
  300.             goto out;
  301.         }
  302.         skip_data(bcnt, dw);
  303.         if ( p_at_stop() ) break;
  304. db:        /* Decode a black run. */
  305.         get_run(cf_black_decode, cfd_black_initial_bits, bcnt, "[w1]black");
  306.         if ( bcnt < 0 )
  307.         {    /* All exceptional codes are invalid here. */
  308.             /****** WRONG, uncompressed IS ALLOWED ******/
  309.             s->end_status = ERRC;
  310.             goto out;
  311.         }
  312.         /* Invert bits designated by black run. */
  313.         invert_data(bcnt, black_byte, goto db, idb);
  314.     }
  315.     if ( p > stop || pbit < end_bit )
  316.     {    s->end_status = ERRC;
  317.         goto out;
  318.     }
  319. out:    cfd_store_state();
  320.     return s->end_status;
  321. }
  322. /* Decode a 2-D scan line. */
  323. private int
  324. cf_decode_2d(stream *s, byte *prev_p)
  325. {    cfd_declare_state;
  326.     int dist;
  327.     byte invert = (s->cfs.BlackIs1 ? 0 : 0xff);
  328.     byte black_byte = ~invert;
  329.     byte invert_white = invert;
  330.     register int count;
  331.     int end_count = -s->cfs.Columns & 7;
  332.     uint raster = s->cfs.raster;
  333.     byte *endptr;
  334.     int init_count = raster << 3;
  335.     int rlen;
  336.     cfd_load_state();
  337.     endptr = p + raster;
  338.     memset(p + 1, invert, raster);
  339.     endptr[1] = 0xa0;    /* a byte with some 0s and some 1s, */
  340.                 /* to ensure run scan will stop */
  341.     dist = prev_p - p;
  342.     for ( count = init_count; count > end_count; )
  343.     {    /* If invert == invert_white, white and black have their */
  344.         /* correct meanings; if invert == ~invert_white, */
  345.         /* black and white are interchanged. */
  346.         if_debug1('W', "[w2]%4d:\n", count);
  347. #ifdef DEBUG
  348.         /* Check the invariant between p, pbit, and count. */
  349.         {    int pcount = (endptr - p) * 8 + pbit;
  350.             if ( pcount != count )
  351.                 dprintf2("[w2]Error: count=%d pcount=%d\n",
  352.                      count, pcount);
  353.         }
  354. #endif
  355.         /* We could just use get_run here, but we can do better: */
  356.         ensure_bits(3);
  357.         switch( peek_bits(3) )
  358.         {
  359.         default/*4..7*/:            /* vertical(0) */
  360.             skip_bits(1);
  361.             rlen = countof(cf2_run_vertical) / 2;
  362.             break;
  363.         case 2:                    /* vertical(+1) */
  364.             skip_bits(3);
  365.             rlen = countof(cf2_run_vertical) / 2 + 1;
  366.             break;
  367.         case 3:                    /* vertical(-1) */
  368.             skip_bits(3);
  369.             rlen = countof(cf2_run_vertical) / 2 - 1;
  370.             break;
  371.         case 1:                    /* horizontal */
  372.             skip_bits(3);
  373.             if ( invert == invert_white )
  374.             {    /* White, then black. */
  375.                 int olen;
  376. hww:                get_run(cf_white_decode,
  377.                     cfd_white_initial_bits, rlen,
  378.                     " white");
  379.                 if ( (count -= rlen) < end_count )
  380.                 {    s->end_status = ERRC;
  381.                     goto out;
  382.                 }
  383.                 skip_data(rlen, hww);
  384. hwb:                get_run(cf_black_decode,
  385.                     cfd_black_initial_bits, olen,
  386.                     " black");
  387.                 if ( (count -= olen) < end_count )
  388.                 {    s->end_status = ERRC;
  389.                     goto out;
  390.                 }
  391.                 invert_data(olen, black_byte, goto hwb, ihwb);
  392.             }
  393.             else
  394.             {    /* Black, then white. */
  395.                 int olen;
  396. hbb:                get_run(cf_black_decode,
  397.                     cfd_black_initial_bits, rlen,
  398.                     " black");
  399.                 if ( (count -= rlen) < end_count )
  400.                 {    s->end_status = ERRC;
  401.                     goto out;
  402.                 }
  403.                 invert_data(rlen, black_byte, goto hbb, ihbb);
  404. hbw:                get_run(cf_white_decode,
  405.                     cfd_white_initial_bits, olen,
  406.                     " white");
  407.                 if ( (count -= olen) < end_count )
  408.                 {    s->end_status = ERRC;
  409.                     goto out;
  410.                 }
  411.                 skip_data(olen, hbw);
  412.             }
  413.             continue;
  414.         case 0:                /* everything else */
  415.             get_run(cf_2d_decode, cfd_2d_initial_bits, rlen,
  416.                 "[w2]");
  417.             /* rlen may be run2_pass, run_uncompressed, or */
  418.             /* 0..countof(cf2_run_vertical)-1. */
  419.             if ( rlen < 0 )
  420.               switch ( rlen )
  421.             {
  422.             case run2_pass:
  423.                 break;
  424.             case run_uncompressed:
  425.             {    int which;
  426.                 cfd_store_state();
  427.                 which = cf_decode_uncompressed(s);
  428.                 if ( which < 0 )
  429.                 {    s->end_status = which;
  430.                     goto out;
  431.                 }
  432.                 cfd_load_state();
  433.                 /****** ADJUST count ******/
  434.                 invert = (which ? ~invert_white : invert_white);
  435.             }    continue;
  436.             default:    /* run_error, run_zeros */
  437.                 s->end_status = ERRC;
  438.                 goto out;
  439.             }
  440.         }
  441.         /* Interpreting the run requires scanning the */
  442.         /* previous ('reference') line. */
  443.         {    int prev_count = count;
  444.             byte prev_data;
  445.             int dlen;
  446.             static const byte count_bit[8] =
  447.                 { 0x80, 1, 2, 4, 8, 0x10, 0x20, 0x40 };
  448.             prev_p = p + dist + 1;
  449.             if ( !(count & 7) )
  450.                 prev_p++;    /* because of skip macros */
  451.             prev_data = prev_p[-1] ^ invert;
  452.             /* Find the b1 transition. */
  453.             if ( (prev_data & count_bit[prev_count & 7]) &&
  454.                  prev_count < init_count
  455.                )
  456.             {    /* Look for changing white first. */
  457.                 skip_black_pixels(prev_data, prev_p,
  458.                           prev_count, invert,
  459.                           b01, b11);
  460.                 if ( prev_count < end_count ) /* overshot */
  461.                     prev_count = end_count;
  462.                 if_debug1('W', " b1 other=%d", prev_count);
  463.             }
  464.             if ( prev_count != end_count )
  465.             {    skip_white_pixels(prev_data, prev_p,
  466.                           prev_count, invert, w01);
  467.                 if ( prev_count < end_count ) /* overshot */
  468.                     prev_count = end_count;
  469.                 if_debug1('W', " b1 same=%d", prev_count);
  470.             }
  471.             /* b1 = prev_count; */
  472.             if ( rlen == run2_pass )
  473.             {    /* Pass mode.  Find b2. */
  474.                 if ( prev_count != end_count )
  475.                 {    skip_black_pixels(prev_data, prev_p,
  476.                               prev_count, invert,
  477.                               b02, b12);
  478.                     if ( prev_count < end_count ) /* overshot */
  479.                         prev_count = end_count;
  480.                 }
  481.                 /* b2 = prev_count; */
  482.                 if_debug2('W', " b2=%d, pass %d\n",
  483.                       prev_count, count - prev_count);
  484.             }
  485.             else
  486.             {    /* Vertical coding. */
  487.                 /* Remember that count counts *down*. */
  488.                 prev_count += rlen - 3;    /* a1 */
  489.                 if_debug2('W', " vertical %d -> %d\n",
  490.                       3 - rlen, prev_count);
  491.             }
  492.             /* Now either invert or skip from count */
  493.             /* to prev_count, and reset count. */
  494.             if ( !invert )
  495.             {    /* Skip data bits. */
  496.                 p = endptr - (prev_count >> 3);
  497.                 pbit = prev_count & 7;
  498.             }
  499.             else
  500.             {    /* Invert data bits. */
  501.                 dlen = count - prev_count;
  502.                 invert_data(dlen, black_byte, 0, idd);
  503.             }
  504.             count = prev_count;
  505.             if ( rlen >= 0 )    /* vertical mode */
  506.                 invert = ~invert;    /* polarity changes */
  507.         }
  508.     }
  509.     if ( count < end_count )    /* overrun! */
  510.         s->end_status = ERRC;
  511. out:    cfd_store_state();
  512.     return s->end_status;
  513. }
  514. /* Decode uncompressed data. */
  515. /* (Not tested: no sample data available!) */
  516. /****** DOESN'T CHECK FOR OVERFLOWING SCAN LINE ******/
  517. private int
  518. cf_decode_uncompressed(stream *s)
  519. {    cfd_declare_state;
  520.     const cfd_node _ds *np;
  521.     int clen, rlen;
  522.     cfd_load_state();
  523.     while ( 1 )
  524.     {    ensure_bits(cfd_uncompressed_initial_bits);
  525.         np = &cf_uncompressed_decode[peek_bits(cfd_uncompressed_initial_bits)];
  526.         clen = np->code_length;
  527.         rlen = np->run_length;
  528.         if ( clen > cfd_uncompressed_initial_bits )
  529.         {    /* Must be an exit code. */
  530.             break;
  531.         }
  532.         if ( rlen == cfd_uncompressed_initial_bits )
  533.         {    /* Longest representable white run */
  534.             if_debug1('W', "[wu]%d\n", rlen);
  535.             if ( (pbit -= cfd_uncompressed_initial_bits) < 0 )
  536.                 pbit += 8, p++;
  537.         }
  538.         else
  539.         {    if_debug1('W', "[wu]%d+1\n", rlen);
  540.             if ( pbit -= rlen < 0 )
  541.                 pbit += 8, p++;
  542.             *p ^= 1 << pbit;
  543.         }
  544.         skip_bits(clen);
  545.     }
  546.     clen -= cfd_uncompressed_initial_bits;
  547.     skip_bits(cfd_uncompressed_initial_bits);
  548.     ensure_bits(clen);
  549.     np = &cf_uncompressed_decode[rlen + peek_var_bits(clen)];
  550.     rlen = np->run_length;
  551.     skip_bits(np->code_length);
  552.     if_debug1('w', "[wu]exit %d\n", rlen);
  553.     if ( rlen >= 0 )
  554.     {    /* Valid exit code, rlen = 2 * run length + next polarity */
  555.         if ( (pbit -= rlen >> 1) < 0 )
  556.             pbit += 8, p++;
  557.         rlen &= 1;
  558.     }
  559. out:        /******* WRONG ******/
  560.     cfd_store_state();
  561.     return rlen;
  562. }
  563.  
  564. /* Stream procedures */
  565. const stream_procs s_CFD_procs =
  566.    {    s_std_noavailable, NULL, s_std_read_flush, s_std_close,
  567.     s_CFD_read_buf, NULL
  568.    };
  569.