home *** CD-ROM | disk | FTP | other *** search
/ Chip 2002 June / Chip_2002-06_cd1.bin / ctenari / Krutak / univiewi_jbig.exe / plugins / JBIG / jbig_lib / jbig.c < prev    next >
C/C++ Source or Header  |  2002-03-22  |  86KB  |  2,912 lines
  1. /*
  2.  *  Portable Free JBIG image compression library
  3.  *
  4.  *  Markus Kuhn -- mkuhn@acm.org
  5.  *
  6.  *  $Id: jbig.c,v 1.14 2002-03-23 01:36:08+00 mgk25 Exp $
  7.  *
  8.  *  This module implements a portable standard C encoder and decoder
  9.  *  using the JBIG lossless bi-level image compression algorithm as
  10.  *  specified in International Standard ISO 11544:1993 or equivalently
  11.  *  as specified in ITU-T Recommendation T.82. See the file jbig.doc
  12.  *  for usage instructions and application examples.
  13.  *
  14.  *  This program is free software; you can redistribute it and/or modify
  15.  *  it under the terms of the GNU General Public License as published by
  16.  *  the Free Software Foundation; either version 2 of the License, or
  17.  *  (at your option) any later version.
  18.  *
  19.  *  This program is distributed in the hope that it will be useful,
  20.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  21.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22.  *  GNU General Public License for more details.
  23.  *
  24.  *  You should have received a copy of the GNU General Public License
  25.  *  along with this program; if not, write to the Free Software
  26.  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  27.  * 
  28.  *  If you want to use this program under different license conditions,
  29.  *  then contact the author for an arrangement.
  30.  *
  31.  *  It is possible that certain products which can be built using this
  32.  *  software module might form inventions protected by patent rights in
  33.  *  some countries (e.g., by patents about arithmetic coding algorithms
  34.  *  owned by IBM and AT&T in the USA). Provision of this software by the
  35.  *  author does NOT include any licences for any patents. In those
  36.  *  countries where a patent licence is required for certain applications
  37.  *  of this software module, you will have to obtain such a licence
  38.  *  yourself.
  39.  */
  40.  
  41. #ifdef DEBUG
  42. #include <stdio.h>
  43. #else
  44. #define NDEBUG
  45. #endif
  46.  
  47. #include <stdlib.h>
  48. #include <assert.h>
  49.  
  50. #include "jbig.h"
  51.  
  52.  
  53. /* optional export of arithmetic coder functions for test purposes */
  54. #ifdef TEST_CODEC
  55. #define ARITH
  56. #define ARITH_INL
  57. #else
  58. #define ARITH      static
  59. #ifdef __GNUC__
  60. #define ARITH_INL  static __inline__
  61. #else
  62. #define ARITH_INL  static
  63. #endif
  64. #endif
  65.  
  66. #define MX_MAX  23     /* maximal supported mx offset for
  67.             * adaptive template in the encoder */
  68.  
  69. #define TPB2CX  0x195  /* contexts for TP special pixels */
  70. #define TPB3CX  0x0e5
  71. #define TPDCX   0xc3f
  72.  
  73. /* marker codes */
  74. #define MARKER_STUFF    0x00
  75. #define MARKER_RESERVE  0x01
  76. #define MARKER_SDNORM   0x02
  77. #define MARKER_SDRST    0x03
  78. #define MARKER_ABORT    0x04
  79. #define MARKER_NEWLEN   0x05
  80. #define MARKER_ATMOVE   0x06
  81. #define MARKER_COMMENT  0x07
  82. #define MARKER_ESC      0xff
  83.  
  84. /* loop array indices */
  85. #define STRIPE  0
  86. #define LAYER   1
  87. #define PLANE   2
  88.  
  89. /* special jbg_buf pointers (instead of NULL) */
  90. #define SDE_DONE ((struct jbg_buf *) -1)
  91. #define SDE_TODO ((struct jbg_buf *) 0)
  92.  
  93. /* object code version id */
  94.  
  95. const char jbg_version[] = 
  96. " JBIG-KIT " JBG_VERSION " -- Markus Kuhn -- "
  97. "$Id: jbig.c,v 1.14 2002-03-23 01:36:08+00 mgk25 Exp $ ";
  98.  
  99. /*
  100.  * the following array specifies for each combination of the 3
  101.  * ordering bits, which ii[] variable represents which dimension
  102.  * of s->sde.
  103.  */
  104. static const int index[8][3] = {
  105.   { 2, 1, 0 },    /* no ordering bit set */
  106.   { -1, -1, -1},  /* SMID -> illegal combination */
  107.   { 2, 0, 1 },    /* ILEAVE */
  108.   { 1, 0, 2 },    /* SMID + ILEAVE */
  109.   { 0, 2, 1 },    /* SEQ */
  110.   { 1, 2, 0 },    /* SEQ + SMID */
  111.   { 0, 1, 2 },    /* SEQ + ILEAVE */
  112.   { -1, -1, -1 }  /* SEQ + SMID + ILEAVE -> illegal combination */
  113. };
  114.  
  115.  
  116. /*
  117.  * Array [language][message] with text string error messages that correspond
  118.  * to return values from public functions in this library.
  119.  */
  120. #define NEMSG         9  /* number of error codes */
  121. #define NEMSG_LANG    3  /* number of supported languages */
  122. static const char *errmsg[NEMSG_LANG][NEMSG] = {
  123.   /* English (JBG_EN) */
  124.   {
  125.     "Everything is ok",                                     /* JBG_EOK */
  126.     "Reached specified maximum size",                       /* JBG_EOK_INTR */
  127.     "Unexpected end of data",                               /* JBG_EAGAIN */
  128.     "Not enough memory available",                          /* JBG_ENOMEM */
  129.     "ABORT marker found",                                   /* JBG_EABORT */
  130.     "Unknown marker segment encountered",                   /* JBG_EMARKER */
  131.     "Incremental BIE does not fit to previous one",         /* JBG_ENOCONT */
  132.     "Invalid data encountered",                             /* JBG_EINVAL */
  133.     "Unimplemented features used"                           /* JBG_EIMPL */
  134.   },
  135.   /* German (JBG_DE_8859_1) */
  136.   {
  137.     "Kein Problem aufgetreten",                             /* JBG_EOK */
  138.     "Angegebene maximale Bildgr\366\337e erreicht",         /* JBG_EOK_INTR */
  139.     "Unerwartetes Ende der Daten",                          /* JBG_EAGAIN */
  140.     "Nicht gen\374gend Speicher vorhanden",                 /* JBG_ENOMEM */
  141.     "Es wurde eine Abbruch-Sequenz gefunden",               /* JBG_EABORT */
  142.     "Eine unbekannte Markierungssequenz wurde gefunden",    /* JBG_EMARKER */
  143.     "Neue Daten passen nicht zu vorangegangenen Daten",     /* JBG_ENOCONT */
  144.     "Es wurden ung\374ltige Daten gefunden",                /* JBG_EINVAL */
  145.     "Noch nicht implementierte Optionen wurden benutzt"     /* JBG_EIMPL */
  146.   },
  147.   /* German (JBG_DE_UTF_8) */
  148.   {
  149.     "Kein Problem aufgetreten",                             /* JBG_EOK */
  150.     "Angegebene maximale Bildgr\303\266\303\237e erreicht", /* JBG_EOK_INTR */
  151.     "Unerwartetes Ende der Daten",                          /* JBG_EAGAIN */
  152.     "Nicht gen\303\274gend Speicher vorhanden",             /* JBG_ENOMEM */
  153.     "Es wurde eine Abbruch-Sequenz gefunden",               /* JBG_EABORT */
  154.     "Eine unbekannte Markierungssequenz wurde gefunden",    /* JBG_EMARKER */
  155.     "Neue Daten passen nicht zu vorangegangenen Daten",     /* JBG_ENOCONT */
  156.     "Es wurden ung\303\274ltige Daten gefunden",            /* JBG_EINVAL */
  157.     "Noch nicht implementierte Optionen wurden benutzt"     /* JBG_EIMPL */
  158.   }
  159. };
  160.  
  161.  
  162.  
  163. /*
  164.  * The following three functions are the only places in this code, were
  165.  * C library memory management functions are called. The whole JBIG
  166.  * library has been designed in order to allow multi-threaded
  167.  * execution. no static or global variables are used, so all fuctions
  168.  * are fully reentrant. However if you want to use this multi-thread
  169.  * capability and your malloc, realloc and free are not reentrant,
  170.  * then simply add the necessary semaphores or mutex primitives below.
  171.  */
  172.  
  173. static void *checked_malloc(size_t size)
  174. {
  175.   void *p;
  176.   
  177.   p = malloc(size);
  178.   /* Full manual exception handling is ugly here for performance
  179.    * reasons. If an adequate handling of lack of memory is required,
  180.    * then use C++ and throw a C++ exception here. */
  181.   if (!p)
  182.     abort();
  183.  
  184. #if 0
  185.   fprintf(stderr, "%p = malloc(%ld)\n", p, (long) size);
  186. #endif
  187.  
  188.   return p;
  189. }
  190.  
  191.  
  192. static void *checked_realloc(void *ptr, size_t size)
  193. {
  194.   void *p;
  195.  
  196.   p = realloc(ptr, size);
  197.   /* Full manual exception handling is ugly here for performance
  198.    * reasons. If an adequate handling of lack of memory is required,
  199.    * then use C++ and throw a C++ exception here. */
  200.   if (!p)
  201.     abort();
  202.  
  203. #if 0
  204.   fprintf(stderr, "%p = realloc(%p, %ld)\n", p, ptr, (long) size);
  205. #endif
  206.  
  207.   return p;
  208. }
  209.  
  210.  
  211. static void checked_free(void *ptr)
  212. {
  213.   free(ptr);
  214.  
  215. #if 0
  216.   fprintf(stderr, "free(%p)\n", ptr);
  217. #endif
  218.  
  219. }
  220.  
  221.  
  222.  
  223. /*
  224.  * The next functions implement the arithmedic encoder and decoder
  225.  * required for JBIG. The same algorithm is also used in the arithmetic
  226.  * variant of JPEG.
  227.  */
  228.  
  229. #ifdef DEBUG
  230. static long encoded_pixels = 0;
  231. #endif
  232.  
  233. ARITH void arith_encode_init(struct jbg_arenc_state *s, int reuse_st)
  234. {
  235.   int i;
  236.   
  237.   if (!reuse_st)
  238.     for (i = 0; i < 4096; s->st[i++] = 0);
  239.   s->c = 0;
  240.   s->a = 0x10000L;
  241.   s->sc = 0;
  242.   s->ct = 11;
  243.   s->buffer = -1;    /* empty */
  244.   
  245.   return;
  246. }
  247.  
  248.  
  249. ARITH void arith_encode_flush(struct jbg_arenc_state *s)
  250. {
  251.   unsigned long temp;
  252.  
  253. #ifdef DEBUG
  254.   fprintf(stderr, "  encoded pixels = %ld, a = %05lx, c = %08lx\n",
  255.       encoded_pixels, s->a, s->c);
  256. #endif
  257.  
  258.   /* find the s->c in the coding interval with the largest
  259.    * number of trailing zero bits */
  260.   if ((temp = (s->a - 1 + s->c) & 0xffff0000L) < s->c)
  261.     s->c = temp + 0x8000;
  262.   else
  263.     s->c = temp;
  264.   /* send remaining bytes to output */
  265.   s->c <<= s->ct;
  266.   if (s->c & 0xf8000000L) {
  267.     /* one final overflow has to be handled */
  268.     if (s->buffer >= 0) {
  269.       s->byte_out(s->buffer + 1, s->file);
  270.       if (s->buffer + 1 == MARKER_ESC)
  271.     s->byte_out(MARKER_STUFF, s->file);
  272.     }
  273.     /* output 0x00 bytes only when more non-0x00 will follow */
  274.     if (s->c & 0x7fff800L)
  275.       for (; s->sc; --s->sc)
  276.     s->byte_out(0x00, s->file);
  277.   } else {
  278.     if (s->buffer >= 0)
  279.       s->byte_out(s->buffer, s->file); 
  280.     /* T.82 figure 30 says buffer+1 for the above line! Typo? */
  281.     for (; s->sc; --s->sc) {
  282.       s->byte_out(0xff, s->file);
  283.       s->byte_out(MARKER_STUFF, s->file);
  284.     }
  285.   }
  286.   /* output final bytes only if they are not 0x00 */
  287.   if (s->c & 0x7fff800L) {
  288.     s->byte_out((s->c >> 19) & 0xff, s->file);
  289.     if (((s->c >> 19) & 0xff) == MARKER_ESC)
  290.       s->byte_out(MARKER_STUFF, s->file);
  291.     if (s->c & 0x7f800L) {
  292.       s->byte_out((s->c >> 11) & 0xff, s->file);
  293.       if (((s->c >> 11) & 0xff) == MARKER_ESC)
  294.     s->byte_out(MARKER_STUFF, s->file);
  295.     }
  296.   }
  297.  
  298.   return;
  299. }
  300.  
  301.  
  302. ARITH_INL void arith_encode(struct jbg_arenc_state *s, int cx, int pix) 
  303. {
  304.   extern short jbg_lsz[];
  305.   extern unsigned char jbg_nmps[], jbg_nlps[];
  306.   register unsigned lsz, ss;
  307.   register unsigned char *st;
  308.   long temp;
  309.  
  310. #ifdef DEBUG
  311.   ++encoded_pixels;
  312. #endif
  313.  
  314.   assert(cx >= 0 && cx < 4096);
  315.   st = s->st + cx;
  316.   ss = *st & 0x7f;
  317.   assert(ss < 113);
  318.   lsz = jbg_lsz[ss];
  319.  
  320. #if 0
  321.   fprintf(stderr, "pix = %d, cx = %d, mps = %d, st = %3d, lsz = 0x%04x, "
  322.       "a = 0x%05lx, c = 0x%08lx, ct = %2d, buf = 0x%02x\n",
  323.       pix, cx, !!(s->st[cx] & 0x80), ss, lsz, s->a, s->c, s->ct,
  324.       s->buffer);
  325. #endif
  326.  
  327.   if (((pix << 7) ^ s->st[cx]) & 0x80) {
  328.     /* encode the less probable symbol */
  329.     if ((s->a -= lsz) >= lsz) {
  330.       /* If the interval size (lsz) for the less probable symbol (LPS)
  331.        * is larger than the interval size for the MPS, then exchange
  332.        * the two symbols for coding efficiency, otherwise code the LPS
  333.        * as usual: */
  334.       s->c += s->a;
  335.       s->a = lsz;
  336.     }
  337.     /* Check whether MPS/LPS exchange is necessary
  338.      * and chose next probability estimator status */
  339.     *st &= 0x80;
  340.     *st ^= jbg_nlps[ss];
  341.   } else {
  342.     /* encode the more probable symbol */
  343.     if ((s->a -= lsz) & 0xffff8000L)
  344.       return;   /* A >= 0x8000 -> ready, no renormalization required */
  345.     if (s->a < lsz) {
  346.       /* If the interval size (lsz) for the less probable symbol (LPS)
  347.        * is larger than the interval size for the MPS, then exchange
  348.        * the two symbols for coding efficiency: */
  349.       s->c += s->a;
  350.       s->a = lsz;
  351.     }
  352.     /* chose next probability estimator status */
  353.     *st &= 0x80;
  354.     *st |= jbg_nmps[ss];
  355.   }
  356.  
  357.   /* renormalization of coding interval */
  358.   do {
  359.     s->a <<= 1;
  360.     s->c <<= 1;
  361.     --s->ct;
  362.     if (s->ct == 0) {
  363.       /* another byte is ready for output */
  364.       temp = s->c >> 19;
  365.       if (temp & 0xffffff00L) {
  366.     /* handle overflow over all buffered 0xff bytes */
  367.     if (s->buffer >= 0) {
  368.       ++s->buffer;
  369.       s->byte_out(s->buffer, s->file);
  370.       if (s->buffer == MARKER_ESC)
  371.         s->byte_out(MARKER_STUFF, s->file);
  372.     }
  373.     for (; s->sc; --s->sc)
  374.       s->byte_out(0x00, s->file);
  375.     s->buffer = temp & 0xff;  /* new output byte, might overflow later */
  376.     assert(s->buffer != 0xff);
  377.     /* can s->buffer really never become 0xff here? */
  378.       } else if (temp == 0xff) {
  379.     /* buffer 0xff byte (which might overflow later) */
  380.     ++s->sc;
  381.       } else {
  382.     /* output all buffered 0xff bytes, they will not overflow any more */
  383.     if (s->buffer >= 0)
  384.       s->byte_out(s->buffer, s->file);
  385.     for (; s->sc; --s->sc) {
  386.       s->byte_out(0xff, s->file);
  387.       s->byte_out(MARKER_STUFF, s->file);
  388.     }
  389.     s->buffer = temp;   /* buffer new output byte (can still overflow) */
  390.       }
  391.       s->c &= 0x7ffffL;
  392.       s->ct = 8;
  393.     }
  394.   } while (s->a < 0x8000);
  395.  
  396.   return;
  397. }
  398.  
  399.  
  400. ARITH void arith_decode_init(struct jbg_ardec_state *s, int reuse_st)
  401. {
  402.   int i;
  403.   
  404.   if (!reuse_st)
  405.     for (i = 0; i < 4096; s->st[i++] = 0);
  406.   s->c = 0;
  407.   s->a = 1;
  408.   s->ct = 0;
  409.   s->result = JBG_OK;
  410.   s->startup = 1;
  411.   return;
  412. }
  413.  
  414.  
  415. ARITH_INL int arith_decode(struct jbg_ardec_state *s, int cx)
  416. {
  417.   extern short jbg_lsz[];
  418.   extern unsigned char jbg_nmps[], jbg_nlps[];
  419.   register unsigned lsz, ss;
  420.   register unsigned char *st;
  421.   int pix;
  422.  
  423.   /* renormalization */
  424.   while (s->a < 0x8000 || s->startup) {
  425.     if (s->ct < 1 && s->result != JBG_READY) {
  426.       /* first we have to move a new byte into s->c */
  427.       if (s->pscd_ptr >= s->pscd_end) {
  428.     s->result = JBG_MORE;
  429.     return -1;
  430.       }
  431.       if (*s->pscd_ptr == 0xff) 
  432.     if (s->pscd_ptr + 1 >= s->pscd_end) {
  433.       s->result = JBG_MARKER;
  434.       return -1;
  435.     } else {
  436.       if (*(s->pscd_ptr + 1) == MARKER_STUFF) {
  437.         s->c |= 0xffL << (8 - s->ct);
  438.         s->ct += 8;
  439.         s->pscd_ptr += 2;
  440.         s->result = JBG_OK;
  441.       } else
  442.         s->result = JBG_READY;
  443.     }
  444.       else {
  445.     s->c |= (long)*(s->pscd_ptr++) << (8 - s->ct);
  446.     s->ct += 8;
  447.     s->result = JBG_OK;
  448.       }
  449.     }
  450.     s->c <<= 1;
  451.     s->a <<= 1;
  452.     --s->ct;
  453.     if (s->a == 0x10000L)
  454.       s->startup = 0;
  455.   }
  456.  
  457.   st = s->st + cx;
  458.   ss = *st & 0x7f;
  459.   assert(ss < 113);
  460.   lsz = jbg_lsz[ss];
  461.  
  462. #if 0
  463.   fprintf(stderr, "cx = %d, mps = %d, st = %3d, lsz = 0x%04x, a = 0x%05lx, "
  464.       "c = 0x%08lx, ct = %2d\n",
  465.       cx, !!(s->st[cx] & 0x80), ss, lsz, s->a, s->c, s->ct);
  466. #endif
  467.  
  468.   if ((s->c >> 16) < (s->a -= lsz))
  469.     if (s->a & 0xffff8000L)
  470.       return *st >> 7;
  471.     else {
  472.       /* MPS_EXCHANGE */
  473.       if (s->a < lsz) {
  474.     pix = 1 - (*st >> 7);
  475.     /* Check whether MPS/LPS exchange is necessary
  476.      * and chose next probability estimator status */
  477.     *st &= 0x80;
  478.     *st ^= jbg_nlps[ss];
  479.       } else {
  480.     pix = *st >> 7;
  481.     *st &= 0x80;
  482.     *st |= jbg_nmps[ss];
  483.       }
  484.     }
  485.   else {
  486.     /* LPS_EXCHANGE */
  487.     if (s->a < lsz) {
  488.       s->c -= s->a << 16;
  489.       s->a = lsz;
  490.       pix = *st >> 7;
  491.       *st &= 0x80;
  492.       *st |= jbg_nmps[ss];
  493.     } else {
  494.       s->c -= s->a << 16;
  495.       s->a = lsz;
  496.       pix = 1 - (*st >> 7);
  497.       /* Check whether MPS/LPS exchange is necessary
  498.        * and chose next probability estimator status */
  499.       *st &= 0x80;
  500.       *st ^= jbg_nlps[ss];
  501.     }
  502.   }
  503.  
  504.   return pix;
  505. }
  506.  
  507.  
  508.  
  509. /*
  510.  * Memory management for buffers which are used for temporarily
  511.  * storing SDEs by the encoder.
  512.  *
  513.  * The following functions manage a set of struct jbg_buf storage
  514.  * containers were each can keep JBG_BUFSIZE bytes. The jbg_buf
  515.  * containers can be linked to form linear double-chained lists for
  516.  * which a number of operations are provided. Blocks which are
  517.  * tempoarily not used any more are returned to a freelist which each
  518.  * encoder keeps. Only the destructor of the encoder actually returns
  519.  * the block via checked_free() to the stdlib memory management.
  520.  */
  521.  
  522.  
  523. /*
  524.  * Allocate a new buffer block and initialize it. Try to get it from
  525.  * the free_list, and if it is empty, call checked_malloc().
  526.  */
  527. static struct jbg_buf *jbg_buf_init(struct jbg_buf **free_list)
  528. {
  529.   struct jbg_buf *new_block;
  530.   
  531.   /* Test whether a block from the free list is available */
  532.   if (*free_list) {
  533.     new_block = *free_list;
  534.     *free_list = new_block->next;
  535.   } else {
  536.     /* request a new memory block */
  537.     new_block = (struct jbg_buf *) checked_malloc(sizeof(struct jbg_buf));
  538.   }
  539.   new_block->len = 0;
  540.   new_block->next = NULL;
  541.   new_block->previous = NULL;
  542.   new_block->last = new_block;
  543.   new_block->free_list = free_list;
  544.  
  545.   return new_block;
  546. }
  547.  
  548.  
  549. /*
  550.  * Return an entire free_list to the memory management of stdlib.
  551.  * This is only done by jbg_enc_free().
  552.  */
  553. static void jbg_buf_free(struct jbg_buf **free_list)
  554. {
  555.   struct jbg_buf *tmp;
  556.   
  557.   while (*free_list) {
  558.     tmp = (*free_list)->next;
  559.     checked_free(*free_list);
  560.     *free_list = tmp;
  561.   }
  562.   
  563.   return;
  564. }
  565.  
  566.  
  567. /*
  568.  * Append a single byte to a single list that starts with the block
  569.  * *(struct jbg_buf *) head. The type of *head is void here in order to
  570.  * keep the interface of the arithmetic encoder gereric, which uses this
  571.  * function as a call-back function in order to deliver single bytes
  572.  * for a PSCD.
  573.  */
  574. static void jbg_buf_write(int b, void *head)
  575. {
  576.   struct jbg_buf *now;
  577.  
  578.   now = ((struct jbg_buf *) head)->last;
  579.   if (now->len < JBG_BUFSIZE - 1) {
  580.     now->d[now->len++] = b;
  581.     return;
  582.   }
  583.   now->next = jbg_buf_init(((struct jbg_buf *) head)->free_list);
  584.   now->next->previous = now;
  585.   now->next->d[now->next->len++] = b;
  586.   ((struct jbg_buf *) head)->last = now->next;
  587.  
  588.   return;
  589. }
  590.  
  591.  
  592. /*
  593.  * Remove any trailing zero bytes from the end of a linked jbg_buf list,
  594.  * however make sure that no zero byte is removed which directly
  595.  * follows a 0xff byte (i.e., keep MARKER_ESC MARKER_STUFF sequences
  596.  * intact). This function is used to remove any redundant final zero
  597.  * bytes from a PSCD.
  598.  */
  599. static void jbg_buf_remove_zeros(struct jbg_buf *head)
  600. {
  601.   struct jbg_buf *last;
  602.  
  603.   while (1) {
  604.     /* remove trailing 0x00 in last block of list until this block is empty */
  605.     last = head->last;
  606.     while (last->len && last->d[last->len - 1] == 0)
  607.       last->len--;
  608.     /* if block became really empty, remove it in case it is not the
  609.      * only remaining block and then loop to next block */
  610.     if (last->previous && !last->len) {
  611.       head->last->next = *head->free_list;
  612.       *head->free_list = head->last;
  613.       head->last = last->previous;
  614.       head->last->next = NULL;
  615.     } else
  616.       break;
  617.   }
  618.  
  619.   /*
  620.    * If the final non-zero byte is 0xff (MARKER_ESC), then we just have
  621.    * removed a MARKER_STUFF and we will append it again now in order
  622.    * to preserve PSCD status of byte stream.
  623.    */
  624.   if (head->last->len && head->last->d[head->last->len - 1] == MARKER_ESC)
  625.     jbg_buf_write(MARKER_STUFF, head);
  626.  
  627.   return;
  628. }
  629.  
  630.  
  631. /*
  632.  * The jbg_buf list which starts with block *new_prefix is concatenated
  633.  * with the list which starts with block **start and *start will then point
  634.  * to the first block of the new list.
  635.  */
  636. static void jbg_buf_prefix(struct jbg_buf *new_prefix, struct jbg_buf **start)
  637. {
  638.   new_prefix->last->next = *start;
  639.   new_prefix->last->next->previous = new_prefix->last;
  640.   new_prefix->last = new_prefix->last->next->last;
  641.   *start = new_prefix;
  642.   
  643.   return;
  644. }
  645.  
  646.  
  647. /*
  648.  * Send the contents of a jbg_buf list that starts with block **head to
  649.  * the call back function data_out and return the blocks of the jbg_buf
  650.  * list to the freelist from which these jbg_buf blocks have been taken.
  651.  * After the call, *head == NULL.
  652.  */
  653. static void jbg_buf_output(struct jbg_buf **head,
  654.             void (*data_out)(unsigned char *start,
  655.                      size_t len, void *file),
  656.             void *file)
  657. {
  658.   struct jbg_buf *tmp;
  659.   
  660.   while (*head) {
  661.     data_out((*head)->d, (*head)->len, file);
  662.     tmp = (*head)->next;
  663.     (*head)->next = *(*head)->free_list;
  664.     *(*head)->free_list = *head;
  665.     *head = tmp;
  666.   }
  667.   
  668.   return;
  669. }
  670.  
  671.  
  672. /*
  673.  * Calculate y = ceil(x/2) applied n times. This function is used to
  674.  * determine the number of pixels per row or column after n resolution
  675.  * reductions. E.g. X[d-1] = jbg_ceil_half(X[d], 1) and X[0] =
  676.  * jbg_ceil_half(X[d], d) as defined in clause 6.2.3 of T.82.
  677.  */
  678. unsigned long jbg_ceil_half(unsigned long x, int n)
  679. {
  680.   unsigned long mask;
  681.   
  682.   mask = (1UL << n) - 1;     /* the lowest n bits are 1 here */
  683.   return (x >> n) + ((mask & x) != 0);
  684. }
  685.  
  686.  
  687. /*
  688.  * Initialize the status struct for the encoder.
  689.  */
  690. void jbg_enc_init(struct jbg_enc_state *s, unsigned long x, unsigned long y,
  691.                   int planes, unsigned char **p,
  692.                   void (*data_out)(unsigned char *start, size_t len,
  693.                    void *file),
  694.           void *file)
  695. {
  696.   unsigned long l, lx;
  697.   int i;
  698.   size_t bufsize;
  699.  
  700.   extern char jbg_resred[], jbg_dptable[];
  701.  
  702.   s->xd = x;
  703.   s->yd = y;
  704.   s->planes = planes;
  705.   s->data_out = data_out;
  706.   s->file = file;
  707.  
  708.   s->d = 0;
  709.   s->dl = 0;
  710.   s->dh = s->d;
  711.   s->l0 = jbg_ceil_half(s->yd, s->d) / 35;   /* 35 stripes/image */
  712.   while ((s->l0 << s->d) > 128)              /* but <= 128 lines/stripe */
  713.     --s->l0;
  714.   if (s->l0 < 2) s->l0 = 2;
  715.   s->mx = 8;
  716.   s->my = 0;
  717.   s->order = JBG_ILEAVE | JBG_SMID;
  718.   s->options = JBG_TPBON | JBG_TPDON | JBG_DPON;
  719.   s->dppriv = jbg_dptable;
  720.   s->res_tab = jbg_resred;
  721.   
  722.   s->highres = checked_malloc(planes * sizeof(int));
  723.   s->lhp[0] = p;
  724.   s->lhp[1] = checked_malloc(planes * sizeof(unsigned char *));
  725.   bufsize = ((jbg_ceil_half(x, 1) + 7) / 8) * jbg_ceil_half(y, 1);
  726.   for (i = 0; i < planes; i++) {
  727.     s->highres[i] = 0;
  728.     s->lhp[1][i] = checked_malloc(sizeof(unsigned char) * bufsize);
  729.   }
  730.   
  731.   s->free_list = NULL;
  732.   s->s = (struct jbg_arenc_state *) 
  733.     checked_malloc(s->planes * sizeof(struct jbg_arenc_state));
  734.   s->tx = (int *) checked_malloc(s->planes * sizeof(int));
  735.   lx = jbg_ceil_half(x, 1);
  736.   s->tp = (char *) checked_malloc(lx * sizeof(char));
  737.   for (l = 0; l < lx; s->tp[l++] = 2);
  738.   s->sde = NULL;
  739.  
  740.   return;
  741. }
  742.  
  743.  
  744. /*
  745.  * This function selects the number of differential layers based on
  746.  * the maximum size requested for the lowest resolution layer. If
  747.  * possible, a number of differential layers is selected, which will
  748.  * keep the size of the lowest resolution layer below or equal to the
  749.  * given width x and height y. However not more than 6 differential
  750.  * resolution layers will be used. In addition, a reasonable value for
  751.  * l0 (height of one stripe in the lowest resolution layer) is
  752.  * selected, which obeys the recommended limitations for l0 in annex A
  753.  * and C of the JBIG standard. The selected number of resolution layers
  754.  * is returned. 
  755.  */
  756. int jbg_enc_lrlmax(struct jbg_enc_state *s, unsigned long x, 
  757.            unsigned long y)
  758. {
  759.   for (s->d = 0; s->d < 6; s->d++)
  760.     if (jbg_ceil_half(s->xd, s->d) <= x && jbg_ceil_half(s->yd, s->d) <= y)
  761.       break;
  762.   s->dl = 0;
  763.   s->dh = s->d;
  764.  
  765.   s->l0 = jbg_ceil_half(s->yd, s->d) / 35;  /* 35 stripes/image */
  766.   while ((s->l0 << s->d) > 128)             /* but <= 128 lines/stripe */
  767.     --s->l0;
  768.   if (s->l0 < 2) s->l0 = 2;
  769.  
  770.   return s->d;
  771. }
  772.  
  773.  
  774. /*
  775.  * As an alternative to jbg_enc_lrlmax(), the following function allows
  776.  * to specify the number of layers directly. The stripe height and layer
  777.  * range is also adjusted automatically here.
  778.  */
  779. void jbg_enc_layers(struct jbg_enc_state *s, int d)
  780. {
  781.   if (d < 0 || d > 255)
  782.     return;
  783.   s->d  = d;
  784.   s->dl = 0;
  785.   s->dh = s->d;
  786.  
  787.   s->l0 = jbg_ceil_half(s->yd, s->d) / 35;  /* 35 stripes/image */
  788.   while ((s->l0 << s->d) > 128)             /* but <= 128 lines/stripe */
  789.     --s->l0;
  790.   if (s->l0 < 2) s->l0 = 2;
  791.  
  792.   return;
  793. }
  794.  
  795.  
  796. /*
  797.  * Specify the highest and lowest resolution layers which will be
  798.  * written to the output file. Call this function not before
  799.  * jbg_enc_layers() or jbg_enc_lrlmax(), because these two functions
  800.  * reset the lowest and highest resolution layer to default values.
  801.  * Negative values are ignored. The total number of layers is returned.
  802.  */
  803. int jbg_enc_lrange(struct jbg_enc_state *s, int dl, int dh)
  804. {
  805.   if (dl >= 0     && dl <= s->d) s->dl = dl;
  806.   if (dh >= s->dl && dh <= s->d) s->dh = dh;
  807.  
  808.   return s->d;
  809. }
  810.  
  811.  
  812. /*
  813.  * The following function allows to specify the bits describing the
  814.  * options of the format as well as the maximum AT movement window and
  815.  * the number of layer 0 lines per stripes.
  816.  */
  817. void jbg_enc_options(struct jbg_enc_state *s, int order, int options,
  818.              long l0, int mx, int my)
  819. {
  820.   if (order >= 0 && order <= 0x0f) s->order = order;
  821.   if (options >= 0) s->options = options;
  822.   if (l0 >= 0) s->l0 = l0;
  823.   if (mx >= 0 && my < 128) s->mx = mx;
  824.   if (my >= 0 && my < 256) s->my = my;
  825.  
  826.   return;
  827. }
  828.  
  829.  
  830. /*
  831.  * This function actually does all the tricky work involved in producing
  832.  * a SDE, which is stored in the appropriate s->sde[][][] element
  833.  * for later output in the correct order.
  834.  */
  835. static void encode_sde(struct jbg_enc_state *s,
  836.                long stripe, int layer, int plane)
  837. {
  838.   unsigned char *hp, *lp1, *lp2, *p0, *p1, *q1, *q2;
  839.   unsigned long hl, ll, hx, hy, lx, ly, hbpl, lbpl;
  840.   unsigned long line_h0 = 0, line_h1 = 0;
  841.   unsigned long line_h2, line_h3, line_l1, line_l2, line_l3;
  842.   struct jbg_arenc_state *se;
  843.   unsigned long i, j, y;
  844.   unsigned t;
  845.   int ltp, ltp_old, cx;
  846.   unsigned long c_all, c[MX_MAX + 1], cmin, cmax, clmin, clmax;
  847.   int tmax, at_determined;
  848.   int new_tx;
  849.   long new_tx_line = -1;
  850.   struct jbg_buf *new_jbg_buf;
  851.  
  852. #ifdef DEBUG
  853.   static long tp_lines, tp_exceptions, tp_pixels, dp_pixels;
  854.   static long encoded_pixels;
  855. #endif
  856.  
  857.   /* return immediately if this stripe has already been encoded */
  858.   if (s->sde[stripe][layer][plane] != SDE_TODO)
  859.     return;
  860.  
  861. #ifdef DEBUG
  862.   if (stripe == 0)
  863.     tp_lines = tp_exceptions = tp_pixels = dp_pixels = encoded_pixels = 0;
  864.   fprintf(stderr, "encode_sde: s/d/p = %2ld/%2d/%2d\n",
  865.       stripe, layer, plane);
  866. #endif
  867.  
  868.   /* number of lines per stripe in highres image */
  869.   hl = s->l0 << layer;
  870.   /* number of lines per stripe in lowres image */
  871.   ll = hl >> 1;
  872.   /* current line number in highres image */
  873.   y = stripe * hl;
  874.   /* number of pixels in highres image */
  875.   hx = jbg_ceil_half(s->xd, s->d - layer);
  876.   hy = jbg_ceil_half(s->yd, s->d - layer);
  877.   /* number of pixels in lowres image */
  878.   lx = jbg_ceil_half(hx, 1);
  879.   ly = jbg_ceil_half(hy, 1);
  880.   /* bytes per line in highres and lowres image */
  881.   hbpl = (hx + 7) / 8;
  882.   lbpl = (lx + 7) / 8;
  883.   /* pointer to first image byte of highres stripe */
  884.   hp = s->lhp[s->highres[plane]][plane] + stripe * hl * hbpl;
  885.   lp2 = s->lhp[1 - s->highres[plane]][plane] + stripe * ll * lbpl;
  886.   lp1 = lp2 + lbpl;
  887.   
  888.   /* initialize arithmetic encoder */
  889.   se = s->s + plane;
  890.   arith_encode_init(se, stripe != 0);
  891.   s->sde[stripe][layer][plane] = jbg_buf_init(&s->free_list);
  892.   se->byte_out = jbg_buf_write;
  893.   se->file = s->sde[stripe][layer][plane];
  894.  
  895.   /* initialize adaptive template movement algorithm */
  896.   c_all = 0;
  897.   for (t = 0; t <= s->mx; t++)
  898.     c[t] = 0;
  899.   if (stripe == 0)
  900.     s->tx[plane] = 0;
  901.   new_tx = -1;
  902.   at_determined = 0;  /* we haven't yet decided the template move */
  903.   if (s->mx == 0)
  904.     at_determined = 1;
  905.  
  906.   /* initialize typical prediction */
  907.   ltp = 0;
  908.   if (stripe == 0)
  909.     ltp_old = 0;
  910.   else {
  911.     ltp_old = 1;
  912.     p1 = hp - hbpl;
  913.     if (y > 1) {
  914.       q1 = p1 - hbpl;
  915.       while (p1 < hp && (ltp_old = (*p1++ == *q1++)) != 0);
  916.     } else
  917.       while (p1 < hp && (ltp_old = (*p1++ == 0)) != 0);
  918.   }
  919.  
  920.   if (layer == 0) {
  921.  
  922.     /*
  923.      *  Encode lowest resolution layer
  924.      */
  925.  
  926.     for (i = 0; i < hl && y < hy; i++, y++) {
  927.  
  928.       /* check whether it is worth to perform an ATMOVE */
  929.       if (!at_determined && c_all > 2048) {
  930.     cmin = clmin = 0xffffffffL;
  931.     cmax = clmax = 0;
  932.     tmax = 0;
  933.     for (t = (s->options & JBG_LRLTWO) ? 5 : 3; t <= s->mx; t++) {
  934.       if (c[t] > cmax) cmax = c[t];
  935.       if (c[t] < cmin) cmin = c[t];
  936.       if (c[t] > c[tmax]) tmax = t;
  937.     }
  938.     clmin = (c[0] < cmin) ? c[0] : cmin;
  939.     clmax = (c[0] > cmax) ? c[0] : cmax;
  940.     if (c_all - cmax < (c_all >> 3) &&
  941.         cmax - c[s->tx[plane]] > c_all - cmax &&
  942.         cmax - c[s->tx[plane]] > (c_all >> 4) &&
  943.         /*                     ^ T.82 says here < !!! Typo ? */
  944.         cmax - (c_all - c[s->tx[plane]]) > c_all - cmax &&
  945.         cmax - (c_all - c[s->tx[plane]]) > (c_all >> 4) &&
  946.         cmax - cmin > (c_all >> 2) &&
  947.         (s->tx[plane] || clmax - clmin > (c_all >> 3))) {
  948.       /* we have decided to perform an ATMOVE */
  949.       new_tx = tmax;
  950.       if (!(s->options & JBG_DELAY_AT)) {
  951.         new_tx_line = i;
  952.         s->tx[plane] = new_tx;
  953.       }
  954.     }
  955.     at_determined = 1;
  956.       }
  957.       
  958.       /* typical prediction */
  959.       if (s->options & JBG_TPBON) {
  960.     ltp = 1;
  961.     p1 = hp;
  962.     if (y > 0) {
  963.       q1 = hp - hbpl;
  964.       while (q1 < hp && (ltp = (*p1++ == *q1++)) != 0);
  965.     } else
  966.       while (p1 < hp + hbpl && (ltp = (*p1++ == 0)) != 0);
  967.     arith_encode(se, (s->options & JBG_LRLTWO) ? TPB2CX : TPB3CX,
  968.              ltp == ltp_old);
  969. #ifdef DEBUG
  970.     tp_lines += ltp;
  971. #endif
  972.     ltp_old = ltp;
  973.     if (ltp) {
  974.       /* skip next line */
  975.       hp += hbpl;
  976.       continue;
  977.     }
  978.       }
  979.  
  980.       /*
  981.        * Layout of the variables line_h1, line_h2, line_h3, which contain
  982.        * as bits the neighbour pixels of the currently coded pixel X:
  983.        *
  984.        *          76543210765432107654321076543210     line_h3
  985.        *          76543210765432107654321076543210     line_h2
  986.        *  76543210765432107654321X76543210             line_h1
  987.        */
  988.       
  989.       line_h1 = line_h2 = line_h3 = 0;
  990.       if (y > 0) line_h2 = (long)*(hp - hbpl) << 8;
  991.       if (y > 1) line_h3 = (long)*(hp - hbpl - hbpl) << 8;
  992.       
  993.       /* encode line */
  994.       for (j = 0; j < hx; hp++) {
  995.     line_h1 |= *hp;
  996.     if (j < hbpl * 8 - 8 && y > 0) {
  997.       line_h2 |= *(hp - hbpl + 1);
  998.       if (y > 1)
  999.         line_h3 |= *(hp - hbpl - hbpl + 1);
  1000.     }
  1001.     if (s->options & JBG_LRLTWO) {
  1002.       /* two line template */
  1003.       do {
  1004.         line_h1 <<= 1;  line_h2 <<= 1;  line_h3 <<= 1;
  1005.         if (s->tx[plane])
  1006.           arith_encode(se, (((line_h2 >> 10) & 0x3e0) |
  1007.                 ((line_h1 >> (4 + s->tx[plane])) & 0x010) |
  1008.                 ((line_h1 >>  9) & 0x00f)),
  1009.                (line_h1 >> 8) & 1);
  1010.         else
  1011.           arith_encode(se, (((line_h2 >> 10) & 0x3f0) |
  1012.                 ((line_h1 >>  9) & 0x00f)),
  1013.                (line_h1 >> 8) & 1);
  1014. #ifdef DEBUG
  1015.         encoded_pixels++;
  1016. #endif
  1017.         /* statistics for adaptive template changes */
  1018.         if (!at_determined && j >= s->mx && j < hx-2) {
  1019.           c[0] += !(((line_h2 >> 6) ^ line_h1) & 0x100);
  1020.           for (t = 5; t <= s->mx; t++)
  1021.         c[t] += !(((line_h1 >> t) ^ line_h1) & 0x100);
  1022.           ++c_all;
  1023.         }
  1024.       } while (++j & 7 && j < hx);
  1025.     } else {
  1026.       /* three line template */
  1027.       do {
  1028.         line_h1 <<= 1;  line_h2 <<= 1;  line_h3 <<= 1;
  1029.         if (s->tx[plane]) 
  1030.           arith_encode(se, (((line_h3 >>  8) & 0x380) |
  1031.                 ((line_h2 >> 12) & 0x078) |
  1032.                 ((line_h1 >> (6 + s->tx[plane])) & 0x004) |
  1033.                 ((line_h1 >>  9) & 0x003)),
  1034.                (line_h1 >> 8) & 1);
  1035.         else
  1036.           arith_encode(se, (((line_h3 >>  8) & 0x380) |
  1037.                 ((line_h2 >> 12) & 0x07c) |
  1038.                 ((line_h1 >>  9) & 0x003)),
  1039.                (line_h1 >> 8) & 1);
  1040. #ifdef DEBUG
  1041.         encoded_pixels++;
  1042. #endif
  1043.         /* statistics for adaptive template changes */
  1044.         if (!at_determined && j >= s->mx && j < hx-2) {
  1045.           c[0] += !(((line_h2 >> 6) ^ line_h1) & 0x100);
  1046.           for (t = 3; t <= s->mx; t++)
  1047.         c[t] += !(((line_h1 >> t) ^ line_h1) & 0x100);
  1048.           ++c_all;
  1049.         }
  1050.       } while (++j & 7 && j < hx);
  1051.     } /* if (s->options & JBG_LRLTWO) */
  1052.       } /* for (j = ...) */
  1053.     } /* for (i = ...) */
  1054.  
  1055.   } else {
  1056.  
  1057.     /*
  1058.      *  Encode differential layer
  1059.      */
  1060.     
  1061.     for (i = 0; i < hl && y < hy; i++, y++) {
  1062.  
  1063.       /* check whether it is worth to perform an ATMOVE */
  1064.       if (!at_determined && c_all > 2048) {
  1065.     cmin = clmin = 0xffffffffL;
  1066.     cmax = clmax = 0;
  1067.     tmax = 0;
  1068.     for (t = 3; t <= s->mx; t++) {
  1069.       if (c[t] > cmax) cmax = c[t];
  1070.       if (c[t] < cmin) cmin = c[t];
  1071.       if (c[t] > c[tmax]) tmax = t;
  1072.     }
  1073.     clmin = (c[0] < cmin) ? c[0] : cmin;
  1074.     clmax = (c[0] > cmax) ? c[0] : cmax;
  1075.     if (c_all - cmax < (c_all >> 3) &&
  1076.         cmax - c[s->tx[plane]] > c_all - cmax &&
  1077.         cmax - c[s->tx[plane]] > (c_all >> 4) &&
  1078.         /*                     ^ T.82 says here < !!! Typo ? */
  1079.         cmax - (c_all - c[s->tx[plane]]) > c_all - cmax &&
  1080.         cmax - (c_all - c[s->tx[plane]]) > (c_all >> 4) &&
  1081.         cmax - cmin > (c_all >> 2) &&
  1082.         (s->tx[plane] || clmax - clmin > (c_all >> 3))) {
  1083.       /* we have decided to perform an ATMOVE */
  1084.       new_tx = tmax;
  1085.       if (!(s->options & JBG_DELAY_AT)) {
  1086.         new_tx_line = i;
  1087.         s->tx[plane] = new_tx;
  1088.       }
  1089. #ifdef DEBUG
  1090.       fprintf(stderr, "ATMOVE: line=%ld, tx=%d, c_all=%ld\n",
  1091.           i, new_tx, c_all);
  1092. #endif
  1093.     }
  1094.     at_determined = 1;
  1095.       }
  1096.       
  1097.       if ((i >> 1) >= ll - 1 || (y >> 1) >= ly - 1)
  1098.     lp1 = lp2;
  1099.  
  1100.       /* typical prediction */
  1101.       if (s->options & JBG_TPDON && (i & 1) == 0) {
  1102.     q1 = lp1; q2 = lp2;
  1103.     p0 = p1 = hp;
  1104.     if (i < hl - 1 && y < hy - 1)
  1105.       p0 = hp + hbpl;
  1106.     if (y > 1)
  1107.       line_l3 = (long)*(q2 - lbpl) << 8;
  1108.     else
  1109.       line_l3 = 0;
  1110.     line_l2 = (long)*q2 << 8;
  1111.     line_l1 = (long)*q1 << 8;
  1112.     ltp = 1;
  1113.     for (j = 0; j < lx && ltp; q1++, q2++) {
  1114.       if (j < lbpl * 8 - 8) {
  1115.         if (y > 1)
  1116.           line_l3 |= *(q2 - lbpl + 1);
  1117.         line_l2 |= *(q2 + 1);
  1118.         line_l1 |= *(q1 + 1);
  1119.       }
  1120.       do {
  1121.         if ((j >> 2) < hbpl) {
  1122.           line_h1 = *(p1++);
  1123.           line_h0 = *(p0++);
  1124.         }
  1125.         do {
  1126.           line_l3 <<= 1;
  1127.           line_l2 <<= 1;
  1128.           line_l1 <<= 1;
  1129.           line_h1 <<= 2;
  1130.           line_h0 <<= 2;
  1131.           cx = (((line_l3 >> 15) & 0x007) |
  1132.             ((line_l2 >> 12) & 0x038) |
  1133.             ((line_l1 >> 9)  & 0x1c0));
  1134.           if (cx == 0x000)
  1135.         if ((line_h1 & 0x300) == 0 && (line_h0 & 0x300) == 0)
  1136.           s->tp[j] = 0;
  1137.         else {
  1138.           ltp = 0;
  1139. #ifdef DEBUG
  1140.           tp_exceptions++;
  1141. #endif
  1142.         }
  1143.           else if (cx == 0x1ff)
  1144.         if ((line_h1 & 0x300) == 0x300 && (line_h0 & 0x300) == 0x300)
  1145.           s->tp[j] = 1;
  1146.         else {
  1147.           ltp = 0;
  1148. #ifdef DEBUG
  1149.           tp_exceptions++;
  1150. #endif
  1151.         }
  1152.           else
  1153.         s->tp[j] = 2;
  1154.         } while (++j & 3 && j < lx);
  1155.       } while (j & 7 && j < lx);
  1156.     } /* for (j = ...) */
  1157.     arith_encode(se, TPDCX, !ltp);
  1158. #ifdef DEBUG
  1159.     tp_lines += ltp;
  1160. #endif
  1161.       }
  1162.  
  1163.  
  1164.       /*
  1165.        * Layout of the variables line_h1, line_h2, line_h3, which contain
  1166.        * as bits the high resolution neighbour pixels of the currently coded
  1167.        * highres pixel X:
  1168.        *
  1169.        *            76543210 76543210 76543210 76543210     line_h3
  1170.        *            76543210 76543210 76543210 76543210     line_h2
  1171.        *   76543210 76543210 7654321X 76543210              line_h1
  1172.        *
  1173.        * Layout of the variables line_l1, line_l2, line_l3, which contain
  1174.        * the low resolution pixels near the currently coded pixel as bits.
  1175.        * The lowres pixel in which the currently coded highres pixel is
  1176.        * located is marked as Y:
  1177.        *
  1178.        *            76543210 76543210 76543210 76543210     line_l3
  1179.        *            76543210 7654321Y 76543210 76543210     line_l2
  1180.        *            76543210 76543210 76543210 76543210     line_l1
  1181.        */
  1182.       
  1183.  
  1184.       line_h1 = line_h2 = line_h3 = line_l1 = line_l2 = line_l3 = 0;
  1185.       if (y > 0) line_h2 = (long)*(hp - hbpl) << 8;
  1186.       if (y > 1) {
  1187.     line_h3 = (long)*(hp - hbpl - hbpl) << 8;
  1188.     line_l3 = (long)*(lp2 - lbpl) << 8;
  1189.       }
  1190.       line_l2 = (long)*lp2 << 8;
  1191.       line_l1 = (long)*lp1 << 8;
  1192.       
  1193.       /* encode line */
  1194.       for (j = 0; j < hx; lp1++, lp2++) {
  1195.     if ((j >> 1) < lbpl * 8 - 8) {
  1196.       if (y > 1)
  1197.         line_l3 |= *(lp2 - lbpl + 1);
  1198.       line_l2 |= *(lp2 + 1);
  1199.       line_l1 |= *(lp1 + 1);
  1200.     }
  1201.     do {
  1202.  
  1203.       assert(hp - (s->lhp[s->highres[plane]][plane] +
  1204.                (stripe * hl + i) * hbpl)
  1205.          == (ptrdiff_t) j >> 3);
  1206.  
  1207.       assert(lp2 - (s->lhp[1-s->highres[plane]][plane] +
  1208.             (stripe * ll + (i>>1)) * lbpl)
  1209.          == (ptrdiff_t) j >> 4);
  1210.  
  1211.       line_h1 |= *(hp++);
  1212.       if (j < hbpl * 8 - 8) {
  1213.         if (y > 0) {
  1214.           line_h2 |= *(hp - hbpl);
  1215.           if (y > 1)
  1216.         line_h3 |= *(hp - hbpl - hbpl);
  1217.         }
  1218.       }
  1219.       do {
  1220.         line_l1 <<= 1;  line_l2 <<= 1;  line_l3 <<= 1;
  1221.         if (ltp && s->tp[j >> 1] < 2) {
  1222.           /* pixel are typical and have not to be encoded */
  1223.           line_h1 <<= 2;  line_h2 <<= 2;  line_h3 <<= 2;
  1224. #ifdef DEBUG
  1225.           do {
  1226.         ++tp_pixels;
  1227.           } while (++j & 1 && j < hx);
  1228. #else
  1229.           j += 2;
  1230. #endif
  1231.         } else
  1232.           do {
  1233.         line_h1 <<= 1;  line_h2 <<= 1;  line_h3 <<= 1;
  1234.  
  1235.         /* deterministic prediction */
  1236.         if (s->options & JBG_DPON) {
  1237.           if ((y & 1) == 0) {
  1238.             if ((j & 1) == 0) {
  1239.               /* phase 0 */
  1240.               if (s->dppriv[((line_l3 >> 16) & 0x003) |
  1241.                     ((line_l2 >> 14) & 0x00c) |
  1242.                     ((line_h1 >> 5)  & 0x010) |
  1243.                     ((line_h2 >> 10) & 0x0e0)] < 2) {
  1244. #ifdef DEBUG
  1245.             ++dp_pixels;
  1246. #endif
  1247.             continue;
  1248.               }
  1249.             } else {
  1250.               /* phase 1 */
  1251.               if (s->dppriv[(((line_l3 >> 16) & 0x003) |
  1252.                      ((line_l2 >> 14) & 0x00c) |
  1253.                      ((line_h1 >> 5)  & 0x030) |
  1254.                      ((line_h2 >> 10) & 0x1c0)) + 256] < 2) {
  1255. #ifdef DEBUG
  1256.             ++dp_pixels;
  1257. #endif
  1258.             continue;
  1259.               }
  1260.             }
  1261.           } else {
  1262.             if ((j & 1) == 0) {
  1263.               /* phase 2 */
  1264.               if (s->dppriv[(((line_l3 >> 16) & 0x003) |
  1265.                      ((line_l2 >> 14) & 0x00c) |
  1266.                      ((line_h1 >> 5)  & 0x010) |
  1267.                      ((line_h2 >> 10) & 0x0e0) |
  1268.                      ((line_h3 >> 7) & 0x700)) + 768] < 2) {
  1269. #ifdef DEBUG
  1270.             ++dp_pixels;
  1271. #endif
  1272.             continue;
  1273.               }
  1274.             } else {
  1275.               /* phase 3 */
  1276.               if (s->dppriv[(((line_l3 >> 16) & 0x003) |
  1277.                      ((line_l2 >> 14) & 0x00c) |
  1278.                      ((line_h1 >> 5)  & 0x030) |
  1279.                      ((line_h2 >> 10) & 0x1c0) |
  1280.                      ((line_h3 >> 7)  & 0xe00)) + 2816] < 2) {
  1281. #ifdef DEBUG
  1282.             ++dp_pixels;
  1283. #endif
  1284.             continue;
  1285.               }
  1286.             }    
  1287.           }    
  1288.         }
  1289.  
  1290.         /* determine context */
  1291.         if (s->tx[plane])
  1292.           cx = (((line_h1 >> 9)  & 0x003) |
  1293.             ((line_h1 >> (4 + s->tx[plane])) & 0x010) |
  1294.             ((line_h2 >> 13) & 0x00c) |
  1295.             ((line_h3 >> 11) & 0x020));
  1296.         else
  1297.           cx = (((line_h1 >> 9)  & 0x003) |
  1298.             ((line_h2 >> 13) & 0x01c) |
  1299.             ((line_h3 >> 11) & 0x020));
  1300.         if (j & 1)
  1301.           cx |= (((line_l2 >> 9)  & 0x0c0) |
  1302.              ((line_l1 >> 7)  & 0x300)) | (1UL << 10);
  1303.         else
  1304.           cx |= (((line_l2 >> 10) & 0x0c0) |
  1305.              ((line_l1 >> 8)  & 0x300));
  1306.         cx |= (y & 1) << 11;
  1307.  
  1308.         arith_encode(se, cx, (line_h1 >> 8) & 1);
  1309. #ifdef DEBUG
  1310.         encoded_pixels++;
  1311. #endif
  1312.         
  1313.         /* statistics for adaptive template changes */
  1314.         if (!at_determined && j >= s->mx) {
  1315.           c[0] += !(((line_h2 >> 6) ^ line_h1) & 0x100);
  1316.           for (t = 3; t <= s->mx; t++)
  1317.             c[t] += !(((line_h1 >> t) ^ line_h1) & 0x100);
  1318.           ++c_all;
  1319.         }
  1320.         
  1321.           } while (++j & 1 && j < hx);
  1322.       } while (j & 7 && j < hx);
  1323.     } while (j & 15 && j < hx);
  1324.       } /* for (j = ...) */
  1325.  
  1326.       /* low resolution pixels are used twice */
  1327.       if ((i & 1) == 0) {
  1328.     lp1 -= lbpl;
  1329.     lp2 -= lbpl;
  1330.       }
  1331.       
  1332.     } /* for (i = ...) */
  1333.   }
  1334.   
  1335.   arith_encode_flush(se);
  1336.   jbg_buf_remove_zeros(s->sde[stripe][layer][plane]);
  1337.   jbg_buf_write(MARKER_ESC, s->sde[stripe][layer][plane]);
  1338.   jbg_buf_write(MARKER_SDNORM, s->sde[stripe][layer][plane]);
  1339.  
  1340.   /* add ATMOVE */
  1341.   if (new_tx != -1) {
  1342.     if (s->options & JBG_DELAY_AT) {
  1343.       /* ATMOVE will become active at the first line of the next stripe */
  1344.       s->tx[plane] = new_tx;
  1345.       jbg_buf_write(MARKER_ESC, s->sde[stripe][layer][plane]);
  1346.       jbg_buf_write(MARKER_ATMOVE, s->sde[stripe][layer][plane]);
  1347.       jbg_buf_write(0, s->sde[stripe][layer][plane]);
  1348.       jbg_buf_write(0, s->sde[stripe][layer][plane]);
  1349.       jbg_buf_write(0, s->sde[stripe][layer][plane]);
  1350.       jbg_buf_write(0, s->sde[stripe][layer][plane]);
  1351.       jbg_buf_write(s->tx[plane], s->sde[stripe][layer][plane]);
  1352.       jbg_buf_write(0, s->sde[stripe][layer][plane]);
  1353.     } else {
  1354.       /* ATMOVE has already become active during this stripe
  1355.        * => we have to prefix the SDE data with an ATMOVE marker */
  1356.       new_jbg_buf = jbg_buf_init(&s->free_list);
  1357.       jbg_buf_write(MARKER_ESC, new_jbg_buf);
  1358.       jbg_buf_write(MARKER_ATMOVE, new_jbg_buf);
  1359.       jbg_buf_write((new_tx_line >> 24) & 0xff, new_jbg_buf);
  1360.       jbg_buf_write((new_tx_line >> 16) & 0xff, new_jbg_buf);
  1361.       jbg_buf_write((new_tx_line >> 8) & 0xff, new_jbg_buf);
  1362.       jbg_buf_write(new_tx_line & 0xff, new_jbg_buf);
  1363.       jbg_buf_write(new_tx, new_jbg_buf);
  1364.       jbg_buf_write(0, new_jbg_buf);
  1365.       jbg_buf_prefix(new_jbg_buf, &s->sde[stripe][layer][plane]);
  1366.     }
  1367.   }
  1368.  
  1369. #if 0
  1370.   if (stripe == s->stripes - 1)
  1371.     fprintf(stderr, "tp_lines = %ld, tp_exceptions = %ld, tp_pixels = %ld, "
  1372.         "dp_pixels = %ld, encoded_pixels = %ld\n",
  1373.         tp_lines, tp_exceptions, tp_pixels, dp_pixels, encoded_pixels);
  1374. #endif
  1375.  
  1376.   return;
  1377. }
  1378.  
  1379.  
  1380. /*
  1381.  * Create the next lower resolution version of an image
  1382.  */
  1383. static void resolution_reduction(struct jbg_enc_state *s, int plane,
  1384.                  int higher_layer)
  1385. {
  1386.   unsigned long hx, hy, lx, ly, hbpl, lbpl;
  1387.   unsigned char *hp1, *hp2, *hp3, *lp;
  1388.   unsigned long line_h1, line_h2, line_h3, line_l2;
  1389.   unsigned long i, j;
  1390.   int pix, k, l;
  1391.  
  1392.   /* number of pixels in highres image */
  1393.   hx = jbg_ceil_half(s->xd, s->d - higher_layer);
  1394.   hy = jbg_ceil_half(s->yd, s->d - higher_layer);
  1395.   /* number of pixels in lowres image */
  1396.   lx = jbg_ceil_half(hx, 1);
  1397.   ly = jbg_ceil_half(hy, 1);
  1398.   /* bytes per line in highres and lowres image */
  1399.   hbpl = (hx + 7) / 8;
  1400.   lbpl = (lx + 7) / 8;
  1401.   /* pointers to first image bytes */
  1402.   hp2 = s->lhp[s->highres[plane]][plane];
  1403.   hp1 = hp2 + hbpl;
  1404.   hp3 = hp2 - hbpl;
  1405.   lp = s->lhp[1 - s->highres[plane]][plane];
  1406.   
  1407. #ifdef DEBUG
  1408.   fprintf(stderr, "resolution_reduction: plane = %d, higher_layer = %d\n",
  1409.       plane, higher_layer);
  1410. #endif
  1411.  
  1412.   /*
  1413.    * Layout of the variables line_h1, line_h2, line_h3, which contain
  1414.    * as bits the high resolution neighbour pixels of the currently coded
  1415.    * lowres pixel /\:
  1416.    *              \/
  1417.    *
  1418.    *   76543210 76543210 76543210 76543210     line_h3
  1419.    *   76543210 76543210 765432/\ 76543210     line_h2
  1420.    *   76543210 76543210 765432\/ 76543210     line_h1
  1421.    *
  1422.    * Layout of the variable line_l2, which contains the low resolution
  1423.    * pixels near the currently coded pixel as bits. The lowres pixel
  1424.    * which is currently coded is marked as X:
  1425.    *
  1426.    *   76543210 76543210 76543210 76543210     line_l2
  1427.    *                            X
  1428.    */
  1429.       
  1430.   for (i = 0; i < ly; i++) {
  1431.     if (2*i + 1 >= hy)
  1432.       hp1 = hp2;
  1433.     pix = 0;
  1434.     line_h1 = line_h2 = line_h3 = line_l2 = 0;
  1435.     for (j = 0; j < lbpl * 8; j += 8) {
  1436.       *lp = 0;
  1437.       line_l2 |= i ? lp[-lbpl] : 0;
  1438.       for (k = 0; k < 8 && j + k < lx; k += 4) {
  1439.     if (((j + k) >> 2) < hbpl) {
  1440.       line_h3 |= i ? *hp3 : 0;
  1441.       ++hp3;
  1442.       line_h2 |= *(hp2++);
  1443.       line_h1 |= *(hp1++);
  1444.     }
  1445.     for (l = 0; l < 4 && j + k + l < lx; l++) {
  1446.       line_h3 <<= 2;
  1447.       line_h2 <<= 2;
  1448.       line_h1 <<= 2;
  1449.       line_l2 <<= 1;
  1450.       pix = s->res_tab[((line_h1 >> 8) & 0x007) |
  1451.                ((line_h2 >> 5) & 0x038) |
  1452.                ((line_h3 >> 2) & 0x1c0) |
  1453.                (pix << 9) | ((line_l2 << 2) & 0xc00)];
  1454.       *lp = (*lp << 1) | pix;
  1455.     }
  1456.       }
  1457.       ++lp;
  1458.     }
  1459.     *(lp - 1) <<= lbpl * 8 - lx;
  1460.     hp1 += hbpl;
  1461.     hp2 += hbpl;
  1462.     hp3 += hbpl;
  1463.   }
  1464.  
  1465. #ifdef DEBUG
  1466.   {
  1467.     FILE *f;
  1468.     char fn[50];
  1469.     
  1470.     sprintf(fn, "dbg_d=%02d.pbm", higher_layer - 1);
  1471.     f = fopen(fn, "wb");
  1472.     fprintf(f, "P4\n%lu %lu\n", lx, ly);
  1473.     fwrite(s->lhp[1 - s->highres[plane]][plane], 1, lbpl * ly, f);
  1474.     fclose(f);
  1475.   }
  1476. #endif
  1477.  
  1478.   return;
  1479. }
  1480.  
  1481.  
  1482. /* 
  1483.  * This function is called inside the three loops of jbg_enc_out() in
  1484.  * order to write the next SDE. It has first to generate the required
  1485.  * SDE and all SDEs which have to be encoded before this SDE can be
  1486.  * created. The problem here is that if we want to output a lower
  1487.  * resolution layer, we have to allpy the resolution reduction
  1488.  * algorithm in order to get it. As we try to safe as much memory as
  1489.  * possible, the resolution reduction will overwrite previous higher
  1490.  * resolution bitmaps. Consequently, we have to encode and buffer SDEs
  1491.  * which depend on higher resolution layers before we can start the
  1492.  * resolution reduction. All this logic about which SDE has to be
  1493.  * encoded before resolution reduction is allowed is handled here.
  1494.  * This approach might be a little bit more complex than alternative
  1495.  * ways to do it, but it allows us to do the encoding with the minimal
  1496.  * possible amount of temporary memory.
  1497.  */
  1498. static void output_sde(struct jbg_enc_state *s,
  1499.                unsigned long stripe, int layer, int plane)
  1500. {
  1501.   int lfcl;     /* lowest fully coded layer */
  1502.   long i;
  1503.   unsigned long u;
  1504.   
  1505.   assert(s->sde[stripe][layer][plane] != SDE_DONE);
  1506.  
  1507.   if (s->sde[stripe][layer][plane] != SDE_TODO) {
  1508. #ifdef DEBUG
  1509.     fprintf(stderr, "writing SDE: s/d/p = %2lu/%2d/%2d\n",
  1510.         stripe, layer, plane);
  1511. #endif
  1512.     jbg_buf_output(&s->sde[stripe][layer][plane], s->data_out, s->file);
  1513.     s->sde[stripe][layer][plane] = SDE_DONE;
  1514.     return;
  1515.   }
  1516.  
  1517.   /* Determine the smallest resolution layer in this plane for which
  1518.    * not yet all stripes have been encoded into SDEs. This layer will
  1519.    * have to be completely coded, before we can apply the next
  1520.    * resolution reduction step. */
  1521.   lfcl = 0;
  1522.   for (i = s->d; i >= 0; i--)
  1523.     if (s->sde[s->stripes - 1][i][plane] == SDE_TODO) {
  1524.       lfcl = i + 1;
  1525.       break;
  1526.     }
  1527.   if (lfcl > s->d && s->d > 0 && stripe == 0) {
  1528.     /* perform the first resolution reduction */
  1529.     resolution_reduction(s, plane, s->d);
  1530.   }
  1531.   /* In case HITOLO is not used, we have to encode and store the higher
  1532.    * resolution layers first, although we do not need them right now. */
  1533.   while (lfcl - 1 > layer) {
  1534.     for (u = 0; u < s->stripes; u++)
  1535.       encode_sde(s, u, lfcl - 1, plane);
  1536.     --lfcl;
  1537.     s->highres[plane] ^= 1;
  1538.     if (lfcl > 1)
  1539.       resolution_reduction(s, plane, lfcl - 1);
  1540.   }
  1541.   
  1542.   encode_sde(s, stripe, layer, plane);
  1543.  
  1544. #ifdef DEBUG
  1545.   fprintf(stderr, "writing SDE: s/d/p = %2lu/%2d/%2d\n", stripe, layer, plane);
  1546. #endif
  1547.   jbg_buf_output(&s->sde[stripe][layer][plane], s->data_out, s->file);
  1548.   s->sde[stripe][layer][plane] = SDE_DONE;
  1549.   
  1550.   if (stripe == s->stripes - 1 && layer > 0 &&
  1551.       s->sde[0][layer-1][plane] == SDE_TODO) {
  1552.     s->highres[plane] ^= 1;
  1553.     if (layer > 1)
  1554.       resolution_reduction(s, plane, layer - 1);
  1555.   }
  1556.   
  1557.   return;
  1558. }
  1559.  
  1560.  
  1561. /*
  1562.  * Convert the table which controls the deterministic prediction
  1563.  * process from the internal format into the representation required
  1564.  * for the 1728 byte long DPTABLE element of a BIH.
  1565.  *
  1566.  * The bit order of the DPTABLE format (see also ITU-T T.82 figure 13) is
  1567.  *
  1568.  * high res:   4  5  6     low res:  0  1
  1569.  *             7  8  9               2  3
  1570.  *            10 11 12
  1571.  *
  1572.  * were 4 table entries are packed into one byte, while we here use
  1573.  * internally an unpacked 6912 byte long table indexed by the following
  1574.  * bit order:
  1575.  *
  1576.  * high res:   7  6  5     high res:   8  7  6     low res:  1  0
  1577.  * (phase 0)   4  .  .     (phase 1)   5  4  .               3  2
  1578.  *             .  .  .                 .  .  .
  1579.  *
  1580.  * high res:  10  9  8     high res:  11 10  9
  1581.  * (phase 2)   7  6  5     (phase 3)   8  7  6
  1582.  *             4  .  .                 5  4  .
  1583.  */
  1584. void jbg_int2dppriv(unsigned char *dptable, const char *internal)
  1585. {
  1586.   int i, j, k;
  1587.   int trans0[ 8] = { 1, 0, 3, 2, 7, 6, 5, 4 };
  1588.   int trans1[ 9] = { 1, 0, 3, 2, 8, 7, 6, 5, 4 };
  1589.   int trans2[11] = { 1, 0, 3, 2, 10, 9, 8, 7, 6, 5, 4 };
  1590.   int trans3[12] = { 1, 0, 3, 2, 11, 10, 9, 8, 7, 6, 5, 4 };
  1591.   
  1592.   for (i = 0; i < 1728; dptable[i++] = 0);
  1593.  
  1594. #define FILL_TABLE1(offset, len, trans) \
  1595.   for (i = 0; i < len; i++) { \
  1596.     k = 0; \
  1597.     for (j = 0; j < 8; j++) \
  1598.       k |= ((i >> j) & 1) << trans[j]; \
  1599.     dptable[(i + offset) >> 2] |= \
  1600.       (internal[k + offset] & 3) << ((3 - (i&3)) << 1); \
  1601.   }
  1602.  
  1603.   FILL_TABLE1(   0,  256, trans0);
  1604.   FILL_TABLE1( 256,  512, trans1);
  1605.   FILL_TABLE1( 768, 2048, trans2);
  1606.   FILL_TABLE1(2816, 4096, trans3);
  1607.  
  1608.   return;
  1609. }
  1610.  
  1611.  
  1612. /*
  1613.  * Convert the table which controls the deterministic prediction
  1614.  * process from the 1728 byte long DPTABLE format into the 6912 byte long
  1615.  * internal format.
  1616.  */
  1617. void jbg_dppriv2int(char *internal, const unsigned char *dptable)
  1618. {
  1619.   int i, j, k;
  1620.   int trans0[ 8] = { 1, 0, 3, 2, 7, 6, 5, 4 };
  1621.   int trans1[ 9] = { 1, 0, 3, 2, 8, 7, 6, 5, 4 };
  1622.   int trans2[11] = { 1, 0, 3, 2, 10, 9, 8, 7, 6, 5, 4 };
  1623.   int trans3[12] = { 1, 0, 3, 2, 11, 10, 9, 8, 7, 6, 5, 4 };
  1624.   
  1625. #define FILL_TABLE2(offset, len, trans) \
  1626.   for (i = 0; i < len; i++) { \
  1627.     k = 0; \
  1628.     for (j = 0; j < 8; j++) \
  1629.       k |= ((i >> j) & 1) << trans[j]; \
  1630.     internal[k + offset] = \
  1631.       (dptable[(i + offset) >> 2] >> ((3 - (i & 3)) << 1)) & 3; \
  1632.   }
  1633.  
  1634.   FILL_TABLE2(   0,  256, trans0);
  1635.   FILL_TABLE2( 256,  512, trans1);
  1636.   FILL_TABLE2( 768, 2048, trans2);
  1637.   FILL_TABLE2(2816, 4096, trans3);
  1638.  
  1639.   return;
  1640. }
  1641.  
  1642.  
  1643. /*
  1644.  * Encode one full BIE and pass the generated data to the specified
  1645.  * call-back function
  1646.  */
  1647. void jbg_enc_out(struct jbg_enc_state *s)
  1648. {
  1649.   long bpl;
  1650.   unsigned char bih[20];
  1651.   unsigned long xd, yd, y;
  1652.   long ii[3], is[3], ie[3];    /* generic variables for the 3 nested loops */ 
  1653.   unsigned long stripe;
  1654.   int layer, plane;
  1655.   int order;
  1656.   unsigned char dpbuf[1728];
  1657.   extern char jbg_dptable[];
  1658.  
  1659.   /* some sanity checks */
  1660.   s->order &= JBG_HITOLO | JBG_SEQ | JBG_ILEAVE | JBG_SMID;
  1661.   order = s->order & (JBG_SEQ | JBG_ILEAVE | JBG_SMID);
  1662.   if (index[order][0] < 0)
  1663.     s->order = order = JBG_SMID | JBG_ILEAVE;
  1664.   if (s->options & JBG_DPON && s->dppriv != jbg_dptable)
  1665.     s->options |= JBG_DPPRIV;
  1666.   if (s->mx > MX_MAX)
  1667.     s->mx = MX_MAX;
  1668.   s->my = 0;
  1669.   if (s->mx && s->mx < ((s->options & JBG_LRLTWO) ? 5U : 3U))
  1670.     s->mx = 0;
  1671.   if (s->d > 255 || s->d < 0 || s->dh > s->d || s->dh < 0 ||
  1672.       s->dl < 0 || s->dl > s->dh || s->planes < 0 || s->planes > 255)
  1673.     return;
  1674.  
  1675.   /* ensure correct zero padding of bitmap at the final byte of each line */
  1676.   if (s->xd & 7) {
  1677.     bpl = (s->xd + 7) / 8;     /* bytes per line */
  1678.     for (plane = 0; plane < s->planes; plane++)
  1679.       for (y = 0; y < s->yd; y++)
  1680.     s->lhp[0][plane][y * bpl + bpl - 1] &= ~((1 << (8 - (s->xd & 7))) - 1);
  1681.   }
  1682.  
  1683.   /* calculate number of stripes that will be required */
  1684.   s->stripes = ((s->yd >> s->d) + 
  1685.         ((((1UL << s->d) - 1) & s->xd) != 0) + s->l0 - 1) / s->l0;
  1686.  
  1687.   /* allocate buffers for SDE pointers */
  1688.   if (s->sde == NULL) {
  1689.     s->sde = (struct jbg_buf ****)
  1690.       checked_malloc(s->stripes * sizeof(struct jbg_buf ***));
  1691.     for (stripe = 0; stripe < s->stripes; stripe++) {
  1692.       s->sde[stripe] = (struct jbg_buf ***)
  1693.     checked_malloc((s->d + 1) * sizeof(struct jbg_buf **));
  1694.       for (layer = 0; layer < s->d + 1; layer++) {
  1695.     s->sde[stripe][layer] = (struct jbg_buf **)
  1696.       checked_malloc(s->planes * sizeof(struct jbg_buf *));
  1697.     for (plane = 0; plane < s->planes; plane++)
  1698.       s->sde[stripe][layer][plane] = SDE_TODO;
  1699.       }
  1700.     }
  1701.   }
  1702.  
  1703.   /* output BIH */
  1704.   bih[0] = s->dl;
  1705.   bih[1] = s->dh;
  1706.   bih[2] = s->planes;
  1707.   bih[3] = 0;
  1708.   xd = jbg_ceil_half(s->xd, s->d - s->dh);
  1709.   yd = jbg_ceil_half(s->yd, s->d - s->dh);
  1710.   bih[4] = xd >> 24;
  1711.   bih[5] = (xd >> 16) & 0xff;
  1712.   bih[6] = (xd >> 8) & 0xff;
  1713.   bih[7] = xd & 0xff;
  1714.   bih[8] = yd >> 24;
  1715.   bih[9] = (yd >> 16) & 0xff;
  1716.   bih[10] = (yd >> 8) & 0xff;
  1717.   bih[11] = yd & 0xff;
  1718.   bih[12] = s->l0 >> 24;
  1719.   bih[13] = (s->l0 >> 16) & 0xff;
  1720.   bih[14] = (s->l0 >> 8) & 0xff;
  1721.   bih[15] = s->l0 & 0xff;
  1722.   bih[16] = s->mx;
  1723.   bih[17] = s->my;
  1724.   bih[18] = s->order;
  1725.   bih[19] = s->options & 0x7f;
  1726.   s->data_out(bih, 20, s->file);
  1727.   if ((s->options & (JBG_DPON | JBG_DPPRIV | JBG_DPLAST)) ==
  1728.       (JBG_DPON | JBG_DPPRIV)) {
  1729.     /* write private table */
  1730.     jbg_int2dppriv(dpbuf, s->dppriv);
  1731.     s->data_out(dpbuf, 1728, s->file);
  1732.   }
  1733.  
  1734. #if 0
  1735.   /*
  1736.    * Encode everything first. This is a simple-minded alternative to
  1737.    * all the tricky on-demand encoding logic in output_sde() for
  1738.    * debugging purposes.
  1739.    */
  1740.   for (layer = s->dh; layer >= s->dl; layer--) {
  1741.     for (plane = 0; plane < s->planes; plane++) {
  1742.       if (layer > 0)
  1743.     resolution_reduction(s, plane, layer);
  1744.       for (stripe = 0; stripe < s->stripes; stripe++)
  1745.     encode_sde(s, stripe, layer, plane);
  1746.       s->highres[plane] ^= 1;
  1747.     }
  1748.   }
  1749. #endif
  1750.  
  1751.   /*
  1752.    * Generic loops over all SDEs. Which loop represents layer, plane and
  1753.    * stripe depends on the option flags.
  1754.    */
  1755.  
  1756.   /* start and end value vor each loop */
  1757.   is[index[order][STRIPE]] = 0;
  1758.   ie[index[order][STRIPE]] = s->stripes - 1;
  1759.   is[index[order][LAYER]] = s->dl;
  1760.   ie[index[order][LAYER]] = s->dh;
  1761.   is[index[order][PLANE]] = 0;
  1762.   ie[index[order][PLANE]] = s->planes - 1;
  1763.  
  1764.   for (ii[0] = is[0]; ii[0] <= ie[0]; ii[0]++)
  1765.     for (ii[1] = is[1]; ii[1] <= ie[1]; ii[1]++)
  1766.       for (ii[2] = is[2]; ii[2] <= ie[2]; ii[2]++) {
  1767.     
  1768.     stripe = ii[index[order][STRIPE]];
  1769.     if (s->order & JBG_HITOLO)
  1770.       layer = s->dh - (ii[index[order][LAYER]] - s->dl);
  1771.     else
  1772.       layer = ii[index[order][LAYER]];
  1773.     plane = ii[index[order][PLANE]];
  1774.  
  1775.     output_sde(s, stripe, layer, plane);
  1776.  
  1777.       }
  1778.  
  1779.   return;
  1780. }
  1781.  
  1782.  
  1783. void jbg_enc_free(struct jbg_enc_state *s)
  1784. {
  1785.   unsigned long stripe;
  1786.   int layer, plane;
  1787.  
  1788. #ifdef DEBUG
  1789.   fprintf(stderr, "jbg_enc_free(%p)\n", (void *) s);
  1790. #endif
  1791.  
  1792.   /* clear buffers for SDEs */
  1793.   if (s->sde) {
  1794.     for (stripe = 0; stripe < s->stripes; stripe++) {
  1795.       for (layer = 0; layer < s->d + 1; layer++) {
  1796.     for (plane = 0; plane < s->planes; plane++)
  1797.       if (s->sde[stripe][layer][plane] != SDE_DONE &&
  1798.           s->sde[stripe][layer][plane] != SDE_TODO)
  1799.         jbg_buf_free(&s->sde[stripe][layer][plane]);
  1800.     checked_free(s->sde[stripe][layer]);
  1801.       }
  1802.       checked_free(s->sde[stripe]);
  1803.     }
  1804.     checked_free(s->sde);
  1805.   }
  1806.  
  1807.   /* clear free_list */
  1808.   jbg_buf_free(&s->free_list);
  1809.  
  1810.   /* clear memory for arithmetic encoder states */
  1811.   checked_free(s->s);
  1812.  
  1813.   /* clear memory for differential-layer typical prediction buffer */
  1814.   checked_free(s->tp);
  1815.  
  1816.   /* clear memory for adaptive template pixel offsets */
  1817.   checked_free(s->tx);
  1818.  
  1819.   /* clear lowres image buffers */
  1820.   if (s->lhp[1]) {
  1821.     for (plane = 0; plane < s->planes; plane++)
  1822.       checked_free(s->lhp[1][plane]);
  1823.     checked_free(s->lhp[1]);
  1824.   }
  1825.  
  1826.   return;
  1827. }
  1828.  
  1829.  
  1830. /*
  1831.  * Convert the error codes used by jbg_dec_in() into a string
  1832.  * written in the selected language and character set.
  1833.  */
  1834. const char *jbg_strerror(int errnum, int language)
  1835. {
  1836.   if (errnum < 0 || errnum >= NEMSG)
  1837.     return "Unknown error code passed to jbg_strerror()";
  1838.   if (language < 0 || language >= NEMSG_LANG)
  1839.     return "Unknown language code passed to jbg_strerror()";
  1840.  
  1841.   return errmsg[language][errnum];
  1842. }
  1843.  
  1844.  
  1845. /*
  1846.  * The constructor for a decoder 
  1847.  */
  1848. void jbg_dec_init(struct jbg_dec_state *s)
  1849. {
  1850.   s->order = 0;
  1851.   s->d = -1;
  1852.   s->bie_len = 0;
  1853.   s->buf_len = 0;
  1854.   s->dppriv = NULL;
  1855.   s->xmax = 4294967295UL;
  1856.   s->ymax = 4294967295UL;
  1857.   s->dmax = 256;
  1858.   s->s = NULL;
  1859.  
  1860.   return;
  1861. }
  1862.  
  1863.  
  1864. /*
  1865.  * Specify a maximum image size for the decoder. If the JBIG file has
  1866.  * the order bit ILEAVE, but not the bit SEQ set, then the decoder
  1867.  * will abort to decode after the image has reached the maximal
  1868.  * resolution layer which is still not wider than xmax or higher than
  1869.  * ymax.
  1870.  */
  1871. void jbg_dec_maxsize(struct jbg_dec_state *s, unsigned long xmax,
  1872.              unsigned long ymax)
  1873. {
  1874.   if (xmax > 0) s->xmax = xmax;
  1875.   if (ymax > 0) s->ymax = ymax;
  1876.  
  1877.   return;
  1878. }
  1879.  
  1880.  
  1881. /*
  1882.  * Decode the new len PSDC bytes to which data points and add them to
  1883.  * the current stripe. Return the number of bytes which have actually
  1884.  * been read (this will be less than len if a marker segment was 
  1885.  * part of the data or if the final byte was 0xff were this code
  1886.  * can not determine, whether we have a marker segment.
  1887.  */
  1888. static size_t decode_pscd(struct jbg_dec_state *s, unsigned char *data,
  1889.               size_t len)
  1890. {
  1891.   unsigned long stripe;
  1892.   unsigned int layer, plane;
  1893.   unsigned long hl, ll, y, hx, hy, lx, ly, hbpl, lbpl;
  1894.   unsigned char *hp, *lp1, *lp2, *p1, *q1;
  1895.   register unsigned long line_h1, line_h2, line_h3;
  1896.   register unsigned long line_l1, line_l2, line_l3;
  1897.   struct jbg_ardec_state *se;
  1898.   unsigned long x;
  1899.   int n;
  1900.   int pix, cx = 0, slntp, shift, tx;
  1901.  
  1902.   /* SDE loop variables */
  1903.   stripe = s->ii[index[s->order & 7][STRIPE]];
  1904.   layer = s->ii[index[s->order & 7][LAYER]];
  1905.   plane = s->ii[index[s->order & 7][PLANE]];
  1906.  
  1907.   /* forward data to arithmetic decoder */
  1908.   se = s->s[plane] + layer - s->dl;
  1909.   se->pscd_ptr = data;
  1910.   se->pscd_end = data + len;
  1911.   
  1912.   /* number of lines per stripe in highres image */
  1913.   hl = s->l0 << layer;
  1914.   /* number of lines per stripe in lowres image */
  1915.   ll = hl >> 1;
  1916.   /* current line number in highres image */
  1917.   y = stripe * hl + s->i;
  1918.   /* number of pixels in highres image */
  1919.   hx = jbg_ceil_half(s->xd, s->d - layer);
  1920.   hy = jbg_ceil_half(s->yd, s->d - layer);
  1921.   /* number of pixels in lowres image */
  1922.   lx = jbg_ceil_half(hx, 1);
  1923.   ly = jbg_ceil_half(hy, 1);
  1924.   /* bytes per line in highres and lowres image */
  1925.   hbpl = (hx + 7) / 8;
  1926.   lbpl = (lx + 7) / 8;
  1927.   /* pointer to highres and lowres image bytes */
  1928.   hp  = s->lhp[ layer    & 1][plane] + (stripe * hl + s->i) * hbpl +
  1929.     (s->x >> 3);
  1930.   lp2 = s->lhp[(layer-1) & 1][plane] + (stripe * ll + (s->i >> 1)) * lbpl +
  1931.     (s->x >> 4);
  1932.   lp1 = lp2 + lbpl;
  1933.  
  1934.   /* restore a few local variables */
  1935.   line_h1 = s->line_h1;
  1936.   line_h2 = s->line_h2;
  1937.   line_h3 = s->line_h3;
  1938.   line_l1 = s->line_l1;
  1939.   line_l2 = s->line_l2;
  1940.   line_l3 = s->line_l3;
  1941.   x = s->x;
  1942.  
  1943.   if (s->x == 0 && s->i == 0 &&
  1944.       (stripe == 0 || s->reset[plane][layer - s->dl])) {
  1945.     s->tx[plane][layer - s->dl] = s->ty[plane][layer - s->dl] = 0;
  1946.     if (s->pseudo)
  1947.       s->lntp[plane][layer - s->dl] = 1;
  1948.   }
  1949.  
  1950. #ifdef DEBUG
  1951.   if (s->x == 0 && s->i == 0 && s->pseudo)
  1952.     fprintf(stderr, "decode_pscd(%p, %p, %ld): s/d/p = %2lu/%2u/%2u\n",
  1953.         (void *) s, (void *) data, (long) len, stripe, layer, plane);
  1954. #endif
  1955.  
  1956.   if (layer == 0) {
  1957.  
  1958.     /*
  1959.      *  Decode lowest resolution layer
  1960.      */
  1961.  
  1962.     for (; s->i < hl && y < hy; s->i++, y++) {
  1963.  
  1964.       /* adaptive template changes */
  1965.       if (x == 0)
  1966.     for (n = 0; n < s->at_moves; n++)
  1967.       if (s->at_line[n] == s->i) {
  1968.         s->tx[plane][layer - s->dl] = s->at_tx[n];
  1969.         s->ty[plane][layer - s->dl] = s->at_ty[n];
  1970. #ifdef DEBUG
  1971.         fprintf(stderr, "ATMOVE: line=%lu, tx=%d, ty=%d.\n", s->i,
  1972.             s->tx[plane][layer - s->dl], s->ty[plane][layer - s->dl]);
  1973. #endif
  1974.       }
  1975.       tx = s->tx[plane][layer - s->dl];
  1976.       shift =  tx - ((s->options & JBG_LRLTWO) ? 5 : 3);
  1977.  
  1978.       /* typical prediction */
  1979.       if (s->options & JBG_TPBON && s->pseudo) {
  1980.     slntp = arith_decode(se, (s->options & JBG_LRLTWO) ? TPB2CX : TPB3CX);
  1981.     if (se->result == JBG_MORE || se->result == JBG_MARKER)
  1982.       goto leave;
  1983.     s->lntp[plane][layer - s->dl] =
  1984.       !(slntp ^ s->lntp[plane][layer - s->dl]);
  1985.     if (s->lntp[plane][layer - s->dl]) {
  1986.       /* this line is 'not typical' and has to be coded completely */
  1987.       s->pseudo = 0;
  1988.     } else {
  1989.       /* this line is 'typical' (i.e. identical to the previous one) */
  1990.       p1 = hp;
  1991.       if (s->i == 0 && (stripe == 0 || s->reset[plane][layer - s->dl]))
  1992.         while (p1 < hp + hbpl) *p1++ = 0;
  1993.       else {
  1994.         q1 = hp - hbpl;
  1995.         while (q1 < hp) *p1++ = *q1++;
  1996.       }
  1997.       hp += hbpl;
  1998.       continue;
  1999.     }
  2000.       }
  2001.       
  2002.       /*
  2003.        * Layout of the variables line_h1, line_h2, line_h3, which contain
  2004.        * as bits the neighbour pixels of the currently decoded pixel X:
  2005.        *
  2006.        *                     76543210 76543210 76543210 76543210     line_h3
  2007.        *                     76543210 76543210 76543210 76543210     line_h2
  2008.        *   76543210 76543210 76543210 76543210 X                     line_h1
  2009.        */
  2010.       
  2011.       if (x == 0) {
  2012.     line_h1 = line_h2 = line_h3 = 0;
  2013.     if (s->i > 0 || (y > 0 && !s->reset[plane][layer - s->dl]))
  2014.       line_h2 = (long)*(hp - hbpl) << 8;
  2015.     if (s->i > 1 || (y > 1 && !s->reset[plane][layer - s->dl]))
  2016.       line_h3 = (long)*(hp - hbpl - hbpl) << 8;
  2017.       }
  2018.       
  2019.       /*
  2020.        * Another tiny JBIG standard bug:
  2021.        *
  2022.        * While implementing the line_h3 handling here, I discovered
  2023.        * another problem with the ITU-T T.82(1993 E) specification.
  2024.        * This might be a somewhat pathological case, however. The
  2025.        * standard is unclear about how a decoder should behave in the
  2026.        * following situation:
  2027.        *
  2028.        * Assume we are in layer 0 and all stripes are single lines
  2029.        * (L0=1 allowed by table 9). We are now decoding the first (and
  2030.        * only) line of the third stripe. Assume, the first stripe was
  2031.        * terminated by SDRST and the second stripe was terminated by
  2032.        * SDNORM. While decoding the only line of the third stripe with
  2033.        * the three-line template, we need access to pixels from the
  2034.        * previous two stripes. We know that the previous stripe
  2035.        * terminated with SDNROM, so we access the pixel from the
  2036.        * second stripe. But do we have to replace the pixels from the
  2037.        * first stripe by background pixels, because this stripe ended
  2038.        * with SDRST? The standard, especially clause 6.2.5 does never
  2039.        * mention this case, so the behaviour is undefined here. My
  2040.        * current implementation remembers only the marker used to
  2041.        * terminate the previous stripe. In the above example, the
  2042.        * pixels of the first stripe are accessed despite the fact that
  2043.        * this stripe ended with SDRST. An alternative (only slightly
  2044.        * more complicated) implementation would be to remember the end
  2045.        * marker (SDNORM or SDRST) of the previous two stripes in a
  2046.        * plane/layer and to act accordingly when accessing the two
  2047.        * previous lines. What am I supposed to do here?
  2048.        *
  2049.        * As the standard is unclear about the correct behaviour in the
  2050.        * situation of the above example, I strongly suggest to avoid
  2051.        * the following situation while encoding data with JBIG:
  2052.        *
  2053.        *   LRLTWO = 0, L0=1 and both SDNORM and SDRST appear in layer 0.
  2054.        *
  2055.        * I guess that only a very few if any encoders will switch
  2056.        * between SDNORM and SDRST, so let us hope that this ambiguity
  2057.        * in the standard will never cause any interoperability
  2058.        * problems.
  2059.        *
  2060.        * Markus Kuhn -- 1995-04-30
  2061.        */
  2062.  
  2063.       /* decode line */
  2064.       while (x < hx) {
  2065.     if ((x & 7) == 0) {
  2066.       if (x < hbpl * 8 - 8 &&
  2067.           (s->i > 0 || (y > 0 && !s->reset[plane][layer - s->dl]))) {
  2068.         line_h2 |= *(hp - hbpl + 1);
  2069.         if (s->i > 1 || (y > 1 && !s->reset[plane][layer - s->dl]))
  2070.           line_h3 |= *(hp - hbpl - hbpl + 1);
  2071.       }
  2072.     }
  2073.     if (s->options & JBG_LRLTWO) {
  2074.       /* two line template */
  2075.       do {
  2076.         if (tx)
  2077.           pix = arith_decode(se, (((line_h2 >> 9) & 0x3e0) |
  2078.                       ((line_h1 >> shift) & 0x010) |
  2079.                       (line_h1 & 0x00f)));
  2080.         else
  2081.           pix = arith_decode(se, (((line_h2 >> 9) & 0x3f0) |
  2082.                       (line_h1 & 0x00f)));
  2083.         if (se->result == JBG_MORE || se->result == JBG_MARKER)
  2084.           goto leave;
  2085.         line_h1 = (line_h1 << 1) | pix;
  2086.         line_h2 <<= 1;
  2087.       } while ((++x & 7) && x < hx);
  2088.     } else {
  2089.       /* three line template */
  2090.       do {
  2091.         if (tx) 
  2092.           pix = arith_decode(se, (((line_h3 >>  7) & 0x380) |
  2093.                       ((line_h2 >> 11) & 0x078) |
  2094.                       ((line_h1 >> shift) & 0x004) |
  2095.                       (line_h1 & 0x003)));
  2096.         else
  2097.           pix = arith_decode(se, (((line_h3 >>  7) & 0x380) |
  2098.                       ((line_h2 >> 11) & 0x07c) |
  2099.                       (line_h1 & 0x003)));
  2100.         if (se->result == JBG_MORE || se->result == JBG_MARKER)
  2101.           goto leave;
  2102.         
  2103.         line_h1 = (line_h1 << 1) | pix;
  2104.         line_h2 <<= 1;
  2105.         line_h3 <<= 1;
  2106.       } while ((++x & 7) && x < hx);
  2107.     } /* if (s->options & JBG_LRLTWO) */
  2108.     *hp++ = line_h1;
  2109.       } /* while */
  2110.       *(hp - 1) <<= hbpl * 8 - hx;
  2111.       x = 0;
  2112.       s->pseudo = 1;
  2113.     } /* for (i = ...) */
  2114.     
  2115.   } else {
  2116.  
  2117.     /*
  2118.      *  Decode differential layer
  2119.      */
  2120.  
  2121.     for (; s->i < hl && y < hy; s->i++, y++) {
  2122.  
  2123.       /* adaptive template changes */
  2124.       if (x == 0)
  2125.     for (n = 0; n < s->at_moves; n++)
  2126.       if (s->at_line[n] == s->i) {
  2127.         s->tx[plane][layer - s->dl] = s->at_tx[n];
  2128.         s->ty[plane][layer - s->dl] = s->at_ty[n];
  2129. #ifdef DEBUG
  2130.         fprintf(stderr, "ATMOVE: line=%lu, tx=%d, ty=%d.\n", s->i,
  2131.             s->tx[plane][layer - s->dl], s->ty[plane][layer - s->dl]);
  2132. #endif
  2133.       }
  2134.       tx = s->tx[plane][layer - s->dl];
  2135.       shift = tx - 3;
  2136.  
  2137.       /* handle lower border of low-resolution image */
  2138.       if ((s->i >> 1) >= ll - 1 || (y >> 1) >= ly - 1)
  2139.     lp1 = lp2;
  2140.  
  2141.       /* typical prediction */
  2142.       if (s->options & JBG_TPDON && s->pseudo) {
  2143.     s->lntp[plane][layer - s->dl] = arith_decode(se, TPDCX);
  2144.     if (se->result == JBG_MORE || se->result == JBG_MARKER)
  2145.       goto leave;
  2146.     s->pseudo = 0;
  2147.       }
  2148.  
  2149.  
  2150.       /*
  2151.        * Layout of the variables line_h1, line_h2, line_h3, which contain
  2152.        * as bits the high resolution neighbour pixels of the currently
  2153.        * decoded highres pixel X:
  2154.        *
  2155.        *                     76543210 76543210 76543210 76543210     line_h3
  2156.        *                     76543210 76543210 76543210 76543210     line_h2
  2157.        *   76543210 76543210 76543210 76543210 X                     line_h1
  2158.        *
  2159.        * Layout of the variables line_l1, line_l2, line_l3, which contain
  2160.        * the low resolution pixels near the currently decoded pixel as bits.
  2161.        * The lowres pixel in which the currently coded highres pixel is
  2162.        * located is marked as Y:
  2163.        *
  2164.        *                     76543210 76543210 76543210 76543210     line_l3
  2165.        *                     76543210 76543210 Y6543210 76543210     line_l2
  2166.        *                     76543210 76543210 76543210 76543210     line_l1
  2167.        */
  2168.       
  2169.  
  2170.       if (x == 0) {
  2171.     line_h1 = line_h2 = line_h3 = line_l1 = line_l2 = line_l3 = 0;
  2172.     if (s->i > 0 || (y > 0 && !s->reset[plane][layer - s->dl])) {
  2173.       line_h2 = (long)*(hp - hbpl) << 8;
  2174.       if (s->i > 1 || (y > 1 && !s->reset[plane][layer - s->dl]))
  2175.         line_h3 = (long)*(hp - hbpl - hbpl) << 8;
  2176.     }
  2177.     if (s->i > 1 || (y > 1 && !s->reset[plane][layer-s->dl]))
  2178.       line_l3 = (long)*(lp2 - lbpl) << 8;
  2179.     line_l2 = (long)*lp2 << 8;
  2180.     line_l1 = (long)*lp1 << 8;
  2181.       }
  2182.       
  2183.       /* decode line */
  2184.       while (x < hx) {
  2185.     if ((x & 15) == 0)
  2186.       if ((x >> 1) < lbpl * 8 - 8) {
  2187.         line_l1 |= *(lp1 + 1);
  2188.         line_l2 |= *(lp2 + 1);
  2189.         if (s->i > 1 || 
  2190.         (y > 1 && !s->reset[plane][layer - s->dl]))
  2191.           line_l3 |= *(lp2 - lbpl + 1);
  2192.       }
  2193.     do {
  2194.  
  2195.       assert(hp  - (s->lhp[ layer     &1][plane] + (stripe * hl + s->i)
  2196.             * hbpl) == (ptrdiff_t) x >> 3);
  2197.       assert(lp2 - (s->lhp[(layer-1) &1][plane] + (stripe * ll + (s->i>>1))
  2198.             * lbpl) == (ptrdiff_t) x >> 4);
  2199.  
  2200.       if ((x & 7) == 0)
  2201.         if (x < hbpl * 8 - 8) {
  2202.           if (s->i > 0 || (y > 0 && !s->reset[plane][layer - s->dl])) {
  2203.         line_h2 |= *(hp + 1 - hbpl);
  2204.         if (s->i > 1 || (y > 1 && !s->reset[plane][layer - s->dl]))
  2205.           line_h3 |= *(hp + 1 - hbpl - hbpl);
  2206.           }
  2207.         }
  2208.       do {
  2209.         if (!s->lntp[plane][layer - s->dl])
  2210.               cx = (((line_l3 >> 14) & 0x007) |
  2211.                     ((line_l2 >> 11) & 0x038) |
  2212.                     ((line_l1 >> 8)  & 0x1c0));
  2213.         if (!s->lntp[plane][layer - s->dl] &&
  2214.         (cx == 0x000 || cx == 0x1ff)) {
  2215.           /* pixels are typical and have not to be decoded */
  2216.           do {
  2217.         line_h1 = (line_h1 << 1) | (cx & 1);
  2218.           } while ((++x & 1) && x < hx);
  2219.           line_h2 <<= 2;  line_h3 <<= 2;
  2220.         } else 
  2221.           do {
  2222.         
  2223.         /* deterministic prediction */
  2224.         if (s->options & JBG_DPON)
  2225.           if ((y & 1) == 0)
  2226.             if ((x & 1) == 0) 
  2227.               /* phase 0 */
  2228.               pix = s->dppriv[((line_l3 >> 15) & 0x003) |
  2229.                       ((line_l2 >> 13) & 0x00c) |
  2230.                       ((line_h1 <<  4) & 0x010) |
  2231.                       ((line_h2 >>  9) & 0x0e0)];
  2232.             else
  2233.               /* phase 1 */
  2234.               pix = s->dppriv[(((line_l3 >> 15) & 0x003) |
  2235.                        ((line_l2 >> 13) & 0x00c) |
  2236.                        ((line_h1 <<  4) & 0x030) |
  2237.                        ((line_h2 >>  9) & 0x1c0)) + 256];
  2238.           else
  2239.             if ((x & 1) == 0)
  2240.               /* phase 2 */
  2241.               pix = s->dppriv[(((line_l3 >> 15) & 0x003) |
  2242.                        ((line_l2 >> 13) & 0x00c) |
  2243.                        ((line_h1 <<  4) & 0x010) |
  2244.                        ((line_h2 >>  9) & 0x0e0) |
  2245.                        ((line_h3 >>  6) & 0x700)) + 768];
  2246.             else
  2247.               /* phase 3 */
  2248.               pix = s->dppriv[(((line_l3 >> 15) & 0x003) |
  2249.                        ((line_l2 >> 13) & 0x00c) |
  2250.                        ((line_h1 <<  4) & 0x030) |
  2251.                        ((line_h2 >>  9) & 0x1c0) |
  2252.                        ((line_h3 >>  6) & 0xe00)) + 2816];
  2253.         else
  2254.           pix = 2;
  2255.  
  2256.         if (pix & 2) {
  2257.           if (tx)
  2258.             cx = ((line_h1         & 0x003) |
  2259.               (((line_h1 << 2) >> shift) & 0x010) |
  2260.               ((line_h2 >> 12) & 0x00c) |
  2261.               ((line_h3 >> 10) & 0x020));
  2262.           else
  2263.             cx = ((line_h1         & 0x003) |
  2264.               ((line_h2 >> 12) & 0x01c) |
  2265.               ((line_h3 >> 10) & 0x020));
  2266.           if (x & 1)
  2267.             cx |= (((line_l2 >> 8) & 0x0c0) |
  2268.                ((line_l1 >> 6) & 0x300)) | (1UL << 10);
  2269.           else
  2270.             cx |= (((line_l2 >> 9) & 0x0c0) |
  2271.                ((line_l1 >> 7) & 0x300));
  2272.           cx |= (y & 1) << 11;
  2273.  
  2274.           pix = arith_decode(se, cx);
  2275.           if (se->result == JBG_MORE || se->result == JBG_MARKER)
  2276.             goto leave;
  2277.         }
  2278.  
  2279.         line_h1 = (line_h1 << 1) | pix;
  2280.         line_h2 <<= 1;
  2281.         line_h3 <<= 1;
  2282.         
  2283.           } while ((++x & 1) && x < hx);
  2284.         line_l1 <<= 1; line_l2 <<= 1;  line_l3 <<= 1;
  2285.       } while ((x & 7) && x < hx);
  2286.       *hp++ = line_h1;
  2287.     } while ((x & 15) && x < hx);
  2288.     ++lp1;
  2289.     ++lp2;
  2290.       } /* while */
  2291.       x = 0;
  2292.       
  2293.       *(hp - 1) <<= hbpl * 8 - hx;
  2294.       if ((s->i & 1) == 0) {
  2295.     /* low resolution pixels are used twice */
  2296.     lp1 -= lbpl;
  2297.     lp2 -= lbpl;
  2298.       } else
  2299.     s->pseudo = 1;
  2300.       
  2301.     } /* for (i = ...) */
  2302.     
  2303.   }
  2304.  
  2305.  leave:
  2306.  
  2307.   /* save a few local variables */
  2308.   s->line_h1 = line_h1;
  2309.   s->line_h2 = line_h2;
  2310.   s->line_h3 = line_h3;
  2311.   s->line_l1 = line_l1;
  2312.   s->line_l2 = line_l2;
  2313.   s->line_l3 = line_l3;
  2314.   s->x = x;
  2315.  
  2316.   return se->pscd_ptr - data;
  2317. }
  2318.  
  2319.  
  2320. /*
  2321.  * Provide a new BIE fragment to the decoder.
  2322.  *
  2323.  * If cnt is not NULL, then *cnt will contain after the call the
  2324.  * number of actually read bytes. If the data was not complete, then
  2325.  * the return value will be JBG_EAGAIN and *cnt == len. In case this
  2326.  * function has returned with JBG_EOK, then it has reached the end of
  2327.  * a BIE but it can be called again with data from the next BIE if
  2328.  * there exists one in order to get to a higher resolution layer. In
  2329.  * case the return value was JBG_EOK_INTR then this function can be
  2330.  * called again with the rest of the BIE, because parsing the BIE has
  2331.  * been interrupted by a jbg_dec_maxsize() specification. In both
  2332.  * cases the remaining len - *cnt bytes of the previous block will
  2333.  * have to passed to this function again (if len > *cnt). In case of
  2334.  * any other return value than JBG_EOK, JBG_EOK_INTR or JBG_EAGAIN, a
  2335.  * serious problem has occured and the only function you should call
  2336.  * is jbg_dec_free() in order to remove the mess (and probably
  2337.  * jbg_strerror() in order to find out what to tell the user).
  2338.  */
  2339. int jbg_dec_in(struct jbg_dec_state *s, unsigned char *data, size_t len,
  2340.            size_t *cnt)
  2341. {
  2342.   int i, j, required_length;
  2343.   unsigned long x, y;
  2344.   unsigned long is[3], ie[3];
  2345.   long hsize, lsize;
  2346.   extern char jbg_dptable[];
  2347.   size_t dummy_cnt;
  2348.  
  2349.   if (!cnt) cnt = &dummy_cnt;
  2350.   *cnt = 0;
  2351.   if (len < 1) return JBG_EAGAIN;
  2352.  
  2353.   /* read in 20-byte BIH */
  2354.   if (s->bie_len < 20) {
  2355.     while (s->bie_len < 20 && *cnt < len)
  2356.       s->buffer[s->bie_len++] = data[(*cnt)++];
  2357.     if (s->bie_len < 20) 
  2358.       return JBG_EAGAIN;
  2359.     if (s->buffer[1] < s->buffer[0])
  2360.       return JBG_EINVAL;
  2361.     /* test whether this looks like a valid JBIG header at all */
  2362.     if (s->buffer[3] != 0 || (s->buffer[18] & 0xf0) != 0 ||
  2363.     (s->buffer[19] & 0x80) != 0)
  2364.       return JBG_EINVAL;
  2365.     if (s->buffer[0] != s->d + 1)
  2366.       return JBG_ENOCONT;
  2367.     s->dl = s->buffer[0];
  2368.     s->d = s->buffer[1];
  2369.     if (s->dl == 0)
  2370.       s->planes = s->buffer[2];
  2371.     else
  2372.       if (s->planes != s->buffer[2])
  2373.     return JBG_ENOCONT;
  2374.     x = (((long) s->buffer[ 4] << 24) | ((long) s->buffer[ 5] << 16) |
  2375.      ((long) s->buffer[ 6] <<  8) | (long) s->buffer[ 7]);
  2376.     y = (((long) s->buffer[ 8] << 24) | ((long) s->buffer[ 9] << 16) |
  2377.      ((long) s->buffer[10] <<  8) | (long) s->buffer[11]);
  2378.     if (s->dl != 0 && ((s->xd << (s->d - s->dl + 1)) != x &&
  2379.                (s->yd << (s->d - s->dl + 1)) != y))
  2380.       return JBG_ENOCONT;
  2381.     s->xd = x;
  2382.     s->yd = y;
  2383.     s->l0 = (((long) s->buffer[12] << 24) | ((long) s->buffer[13] << 16) |
  2384.          ((long) s->buffer[14] <<  8) | (long) s->buffer[15]);
  2385.     /* ITU-T T.85 trick currently not yet supported */
  2386.     if (s->yd == 0xffffffff)
  2387.       return JBG_EIMPL;
  2388.     if (!s->planes || !s->xd || !s->yd || !s->l0)
  2389.       return JBG_EINVAL;
  2390.     s->mx = s->buffer[16];
  2391.     if (s->mx > 127)
  2392.       return JBG_EINVAL;
  2393.     s->my = s->buffer[17];
  2394.     if (s->mx > 32 || s->my > 0) 
  2395.       return JBG_EIMPL;
  2396.     s->order = s->buffer[18];
  2397.     if (index[s->order & 7][0] < 0)
  2398.       return JBG_EINVAL;
  2399.     /* HITOLO and SEQ currently not yet implemented */
  2400.     if (s->dl != s->d && (s->order & JBG_HITOLO || s->order & JBG_SEQ))
  2401.       return JBG_EIMPL;
  2402.     s->options = s->buffer[19];
  2403.  
  2404.     /* calculate number of stripes that will be required */
  2405.     s->stripes = ((s->yd >> s->d) +
  2406.           ((((1UL << s->d) - 1) & s->xd) != 0) + s->l0 - 1) / s->l0;
  2407.  
  2408.     /* some initialization */
  2409.     s->ii[index[s->order & 7][STRIPE]] = 0;
  2410.     s->ii[index[s->order & 7][LAYER]] = s->dl;
  2411.     s->ii[index[s->order & 7][PLANE]] = 0;
  2412.     /* bytes required for resolution layer D and D-1 */
  2413.     hsize = ((s->xd + 7) / 8) * s->yd;
  2414.     lsize = ((jbg_ceil_half(s->xd, 1) + 7) / 8) *
  2415.       jbg_ceil_half(s->yd, 1);
  2416.     if (s->dl == 0) {
  2417.       s->s = checked_malloc(s->planes * sizeof(struct jbg_ardec_state *));
  2418.       s->tx = checked_malloc(s->planes * sizeof(int *));
  2419.       s->ty = checked_malloc(s->planes * sizeof(int *));
  2420.       s->reset = checked_malloc(s->planes * sizeof(int *));
  2421.       s->lntp = checked_malloc(s->planes * sizeof(int *));
  2422.       s->lhp[0] = checked_malloc(s->planes * sizeof(unsigned char *));
  2423.       s->lhp[1] = checked_malloc(s->planes * sizeof(unsigned char *));
  2424.       for (i = 0; i < s->planes; i++) {
  2425.     s->s[i] = checked_malloc((s->d - s->dl + 1) *
  2426.                  sizeof(struct jbg_ardec_state));
  2427.     s->tx[i] = checked_malloc((s->d - s->dl + 1) * sizeof(int));
  2428.     s->ty[i] = checked_malloc((s->d - s->dl + 1) * sizeof(int));
  2429.     s->reset[i] = checked_malloc((s->d - s->dl + 1) * sizeof(int));
  2430.     s->lntp[i] = checked_malloc((s->d - s->dl + 1) * sizeof(int));
  2431.     s->lhp[s->d    &1][i] = checked_malloc(sizeof(unsigned char) * hsize);
  2432.     s->lhp[(s->d-1)&1][i] = checked_malloc(sizeof(unsigned char) * lsize);
  2433.       }
  2434.     } else {
  2435.       for (i = 0; i < s->planes; i++) {
  2436.     s->s[i] = checked_realloc(s->s[i], (s->d - s->dl + 1) *
  2437.                   sizeof(struct jbg_ardec_state));
  2438.     s->tx[i] = checked_realloc(s->tx[i], (s->d - s->dl + 1) * sizeof(int));
  2439.     s->ty[i] = checked_realloc(s->ty[i], (s->d - s->dl + 1) * sizeof(int));
  2440.     s->reset[i] = checked_realloc(s->reset[i],
  2441.                       (s->d - s->dl +1) * sizeof(int));
  2442.     s->lntp[i] = checked_realloc(s->lntp[i],
  2443.                      (s->d - s->dl +1) * sizeof(int));
  2444.     s->lhp[s->d    &1][i] = checked_realloc(s->lhp[s->d    & 1][i],
  2445.                         sizeof(unsigned char) * hsize);
  2446.     s->lhp[(s->d-1)&1][i] = checked_realloc(s->lhp[(s->d-1)&1][i],
  2447.                         sizeof(unsigned char) * lsize);
  2448.       }
  2449.     }
  2450.     for (i = 0; i < s->planes; i++)
  2451.       for (j = 0; j <= s->d - s->dl; j++)
  2452.     arith_decode_init(s->s[i] + j, 0);
  2453.     if (s->dl == 0 || (s->options & JBG_DPON && !(s->options & JBG_DPPRIV)))
  2454.       s->dppriv = jbg_dptable;
  2455.     s->comment_skip = 0;
  2456.     s->buf_len = 0;
  2457.     s->x = 0;
  2458.     s->i = 0;
  2459.     s->pseudo = 1;
  2460.     s->at_moves = 0;
  2461.   }
  2462.  
  2463.   /* read in DPTABLE */
  2464.   if (s->bie_len < 20 + 1728 && 
  2465.       (s->options & (JBG_DPON | JBG_DPPRIV | JBG_DPLAST)) ==
  2466.       (JBG_DPON | JBG_DPPRIV)) {
  2467.     assert(s->bie_len >= 20);
  2468.     while (s->bie_len < 20 + 1728 && *cnt < len)
  2469.       s->buffer[s->bie_len++ - 20] = data[(*cnt)++];
  2470.     if (s->bie_len < 20 + 1728) 
  2471.       return JBG_EAGAIN;
  2472.     if (!s->dppriv || s->dppriv == jbg_dptable)
  2473.       s->dppriv = checked_malloc(sizeof(char) * 1728);
  2474.     jbg_dppriv2int(s->dppriv, s->buffer);
  2475.   }
  2476.  
  2477.   /*
  2478.    * BID processing loop
  2479.    */
  2480.   
  2481.   while (*cnt < len) {
  2482.  
  2483.     /* process floating marker segments */
  2484.  
  2485.     /* skip COMMENT contents */
  2486.     if (s->comment_skip) {
  2487.       if (s->comment_skip <= len - *cnt) {
  2488.     *cnt += s->comment_skip;
  2489.     s->comment_skip = 0;
  2490.       } else {
  2491.     s->comment_skip -= len - *cnt;
  2492.     *cnt = len;
  2493.       }
  2494.       continue;
  2495.     }
  2496.  
  2497.     /* load complete marker segments into s->buffer for processing */
  2498.     if (s->buf_len > 0) {
  2499.       assert(s->buffer[0] == MARKER_ESC);
  2500.       while (s->buf_len < 2 && *cnt < len)
  2501.     s->buffer[s->buf_len++] = data[(*cnt)++];
  2502.       if (s->buf_len < 2) continue;
  2503.       switch (s->buffer[1]) {
  2504.       case MARKER_COMMENT: required_length = 6; break;
  2505.       case MARKER_ATMOVE:  required_length = 8; break;
  2506.       case MARKER_NEWLEN:  required_length = 6; break;
  2507.       case MARKER_ABORT:
  2508.       case MARKER_SDNORM:
  2509.       case MARKER_SDRST:   required_length = 2; break;
  2510.       case MARKER_STUFF:
  2511.     /* forward stuffed 0xff to arithmetic decoder */
  2512.     s->buf_len = 0;
  2513.     decode_pscd(s, s->buffer, 2);
  2514.     continue;
  2515.       default:
  2516.     return JBG_EMARKER;
  2517.       }
  2518.       while (s->buf_len < required_length && *cnt < len)
  2519.     s->buffer[s->buf_len++] = data[(*cnt)++];
  2520.       if (s->buf_len < required_length) continue;
  2521.       /* now the buffer is filled with exactly one marker segment */
  2522.       switch (s->buffer[1]) {
  2523.       case MARKER_COMMENT:
  2524.     s->comment_skip = 
  2525.       (((long) s->buffer[2] << 24) | ((long) s->buffer[3] << 16) |
  2526.        ((long) s->buffer[4] <<  8) | (long) s->buffer[5]);
  2527.     break;
  2528.       case MARKER_ATMOVE:
  2529.     if (s->at_moves < JBG_ATMOVES_MAX) {
  2530.       s->at_line[s->at_moves] =
  2531.         (((long) s->buffer[2] << 24) | ((long) s->buffer[3] << 16) |
  2532.          ((long) s->buffer[4] <<  8) | (long) s->buffer[5]);
  2533.       s->at_tx[s->at_moves] = (signed char) s->buffer[6];
  2534.       s->at_ty[s->at_moves] = s->buffer[7];
  2535.       if (s->at_tx[s->at_moves] < - (int) s->mx ||
  2536.           s->at_tx[s->at_moves] >   (int) s->mx ||
  2537.           s->at_ty[s->at_moves] >   (int) s->my ||
  2538.           (s->at_ty[s->at_moves] == 0 && s->at_tx[s->at_moves] < 0))
  2539.         return JBG_EINVAL;
  2540.       s->at_moves++;
  2541.     } else
  2542.       return JBG_EINVAL;
  2543.     break;
  2544.       case MARKER_NEWLEN:
  2545.     y = (((long) s->buffer[2] << 24) | ((long) s->buffer[3] << 16) |
  2546.          ((long) s->buffer[4] <<  8) | (long) s->buffer[5]);
  2547.     if (y > s->yd || !(s->options & JBG_VLENGTH))
  2548.       return JBG_EINVAL;
  2549.     s->yd = y;
  2550.     /* calculate again number of stripes that will be required */
  2551.     s->stripes = 
  2552.       ((s->yd >> s->d) +
  2553.        ((((1UL << s->d) - 1) & s->xd) != 0) + s->l0 - 1) / s->l0;
  2554.     break;
  2555.       case MARKER_ABORT:
  2556.     return JBG_EABORT;
  2557.     
  2558.       case MARKER_SDNORM:
  2559.       case MARKER_SDRST:
  2560.     /* decode final pixels based on trailing zero bytes */
  2561.     decode_pscd(s, s->buffer, 2);
  2562.  
  2563.     arith_decode_init(s->s[s->ii[index[s->order & 7][PLANE]]] + 
  2564.               s->ii[index[s->order & 7][LAYER]] - s->dl,
  2565.               s->ii[index[s->order & 7][STRIPE]] != s->stripes - 1
  2566.               && s->buffer[1] != MARKER_SDRST);
  2567.     
  2568.     s->reset[s->ii[index[s->order & 7][PLANE]]]
  2569.       [s->ii[index[s->order & 7][LAYER]] - s->dl] =
  2570.         (s->buffer[1] == MARKER_SDRST);
  2571.     
  2572.     /* prepare for next SDE */
  2573.     s->x = 0;
  2574.     s->i = 0;
  2575.     s->pseudo = 1;
  2576.     s->at_moves = 0;
  2577.     
  2578.     /* increment layer/stripe/plane loop variables */
  2579.     /* start and end value for each loop: */
  2580.     is[index[s->order & 7][STRIPE]] = 0;
  2581.     ie[index[s->order & 7][STRIPE]] = s->stripes - 1;
  2582.     is[index[s->order & 7][LAYER]] = s->dl;
  2583.     ie[index[s->order & 7][LAYER]] = s->d;
  2584.     is[index[s->order & 7][PLANE]] = 0;
  2585.     ie[index[s->order & 7][PLANE]] = s->planes - 1;
  2586.     i = 2;  /* index to innermost loop */
  2587.     do {
  2588.       j = 0;  /* carry flag */
  2589.       if (++s->ii[i] > ie[i]) {
  2590.         /* handling overflow of loop variable */
  2591.         j = 1;
  2592.         if (i > 0)
  2593.           s->ii[i] = is[i];
  2594.       }
  2595.     } while (--i >= 0 && j);
  2596.  
  2597.     s->buf_len = 0;
  2598.     
  2599.     /* check whether this have been all SDEs */
  2600.     if (j) {
  2601.       s->bie_len = 0;
  2602.       return JBG_EOK;
  2603.     }
  2604.  
  2605.     /* check whether we have to abort because of xmax/ymax */
  2606.     if (index[s->order & 7][LAYER] == 0 && i < 0) {
  2607.       /* LAYER is the outermost loop and we have just gone to next layer */
  2608.       if (jbg_ceil_half(s->xd, s->d - s->ii[0]) > s->xmax ||
  2609.           jbg_ceil_half(s->yd, s->d - s->ii[0]) > s->ymax) {
  2610.         s->xmax = 4294967295UL;
  2611.         s->ymax = 4294967295UL;
  2612.         return JBG_EOK_INTR;
  2613.       }
  2614.       if (s->ii[0] > (unsigned long) s->dmax) {
  2615.         s->dmax = 256;
  2616.         return JBG_EOK_INTR;
  2617.       }
  2618.     }
  2619.  
  2620.     break;
  2621.       }
  2622.       s->buf_len = 0;
  2623.  
  2624.     } else if (data[*cnt] == MARKER_ESC)
  2625.       s->buffer[s->buf_len++] = data[(*cnt)++];
  2626.  
  2627.     else {
  2628.  
  2629.       /* we have found PSCD bytes */
  2630.       *cnt += decode_pscd(s, data + *cnt, len - *cnt);
  2631.       if (*cnt < len && data[*cnt] != 0xff) {
  2632. #ifdef DEBUG
  2633.     fprintf(stderr, "PSCD was longer than expected, unread bytes "
  2634.         "%02x %02x %02x %02x ...\n", data[*cnt], data[*cnt+1],
  2635.         data[*cnt+2], data[*cnt+3]);
  2636. #endif
  2637.     return JBG_EINVAL;
  2638.       }
  2639.       
  2640.     }
  2641.   }  /* of BID processing loop 'while (*cnt < len) ...' */
  2642.  
  2643.   return JBG_EAGAIN;
  2644. }
  2645.  
  2646.  
  2647. /*
  2648.  * After jbg_dec_in() returned JBG_EOK or JBG_EOK_INTR, you can call this
  2649.  * function in order to find out the width of the image.
  2650.  */
  2651. long jbg_dec_getwidth(const struct jbg_dec_state *s)
  2652. {
  2653.   if (s->d < 0)
  2654.     return -1;
  2655.   if (index[s->order & 7][LAYER] == 0) {
  2656.     if (s->ii[0] < 1)
  2657.       return -1;
  2658.     else
  2659.       return jbg_ceil_half(s->xd, s->d - (s->ii[0] - 1));
  2660.   }
  2661.  
  2662.   return s->xd;
  2663. }
  2664.  
  2665.  
  2666. /*
  2667.  * After jbg_dec_in() returned JBG_EOK or JBG_EOK_INTR, you can call this
  2668.  * function in order to find out the height of the image.
  2669.  */
  2670. long jbg_dec_getheight(const struct jbg_dec_state *s)
  2671. {
  2672.   if (s->d < 0)
  2673.     return -1;
  2674.   if (index[s->order & 7][LAYER] == 0) {
  2675.     if (s->ii[0] < 1)
  2676.       return -1;
  2677.     else
  2678.       return jbg_ceil_half(s->yd, s->d - (s->ii[0] - 1));
  2679.   }
  2680.   
  2681.   return s->yd;
  2682. }
  2683.  
  2684.  
  2685. /*
  2686.  * After jbg_dec_in() returned JBG_EOK or JBG_EOK_INTR, you can call this
  2687.  * function in order to get a pointer to the image.
  2688.  */
  2689. unsigned char *jbg_dec_getimage(const struct jbg_dec_state *s, int plane)
  2690. {
  2691.   if (s->d < 0)
  2692.     return NULL;
  2693.   if (index[s->order & 7][LAYER] == 0) {
  2694.     if (s->ii[0] < 1)
  2695.       return NULL;
  2696.     else
  2697.       return s->lhp[(s->ii[0] - 1) & 1][plane];
  2698.   }
  2699.   
  2700.   return s->lhp[s->d & 1][plane];
  2701. }
  2702.  
  2703.  
  2704. /*
  2705.  * After jbg_dec_in() returned JBG_EOK or JBG_EOK_INTR, you can call
  2706.  * this function in order to find out the size in bytes of one
  2707.  * bitplane of the image.
  2708.  */
  2709. long jbg_dec_getsize(const struct jbg_dec_state *s)
  2710. {
  2711.   if (s->d < 0)
  2712.     return -1;
  2713.   if (index[s->order & 7][LAYER] == 0) {
  2714.     if (s->ii[0] < 1)
  2715.       return -1;
  2716.     else
  2717.       return 
  2718.     ((jbg_ceil_half(s->xd, s->d - (s->ii[0] - 1)) + 7) / 8) *
  2719.     jbg_ceil_half(s->yd, s->d - (s->ii[0] - 1));
  2720.   }
  2721.   
  2722.   return ((s->xd + 7) / 8) * s->yd;
  2723. }
  2724.  
  2725.  
  2726. /*
  2727.  * After jbg_dec_in() returned JBG_EOK or JBG_EOK_INTR, you can call
  2728.  * this function in order to find out the size of the image that you
  2729.  * can retrieve with jbg_merge_planes().
  2730.  */
  2731. long jbg_dec_getsize_merged(const struct jbg_dec_state *s)
  2732. {
  2733.   if (s->d < 0)
  2734.     return -1;
  2735.   if (index[s->order & 7][LAYER] == 0) {
  2736.     if (s->ii[0] < 1)
  2737.       return -1;
  2738.     else
  2739.       return 
  2740.     jbg_ceil_half(s->xd, s->d - (s->ii[0] - 1)) *
  2741.     jbg_ceil_half(s->yd, s->d - (s->ii[0] - 1)) *
  2742.     ((s->planes + 7) / 8);
  2743.   }
  2744.   
  2745.   return s->xd * s->yd * ((s->planes + 7) / 8);
  2746. }
  2747.  
  2748.  
  2749. /* 
  2750.  * The destructor function which releases any resources obtained by the
  2751.  * other decoder functions.
  2752.  */
  2753. void jbg_dec_free(struct jbg_dec_state *s)
  2754. {
  2755.   int i;
  2756.  
  2757.   if (s->d < 0 || s->s == NULL)
  2758.     return;
  2759.   s->d = -2;
  2760.  
  2761.   for (i = 0; i < s->planes; i++) {
  2762.     checked_free(s->s[i]);
  2763.     checked_free(s->tx[i]);
  2764.     checked_free(s->ty[i]);
  2765.     checked_free(s->reset[i]);
  2766.     checked_free(s->lntp[i]);
  2767.     checked_free(s->lhp[0][i]);
  2768.     checked_free(s->lhp[1][i]);
  2769.   }
  2770.   
  2771.   checked_free(s->s);
  2772.   checked_free(s->tx);
  2773.   checked_free(s->ty);
  2774.   checked_free(s->reset);
  2775.   checked_free(s->lntp);
  2776.   checked_free(s->lhp[0]);
  2777.   checked_free(s->lhp[1]);
  2778.  
  2779.   s->s = NULL;
  2780.  
  2781.   return;
  2782. }
  2783.  
  2784.  
  2785. /*
  2786.  * Split bigendian integer pixel field into separate bit planes. In the
  2787.  * src array, every pixel is represented by a ((has_planes + 7) / 8) byte
  2788.  * long word, most significant byte first. While has_planes describes
  2789.  * the number of used bits per pixel in the source image, encode_plane
  2790.  * is the number of most significant bits among those that we
  2791.  * actually transfer to dest.
  2792.  */
  2793. void jbg_split_planes(unsigned long x, unsigned long y, int has_planes,
  2794.               int encode_planes,
  2795.               const unsigned char *src, unsigned char **dest,
  2796.               int use_graycode)
  2797. {
  2798.   unsigned bpl = (x + 7) / 8;           /* bytes per line in dest plane */
  2799.   unsigned i, k = 8;
  2800.   int p;
  2801.   unsigned long line;
  2802.   extern void *memset(void *s, int c, size_t n);
  2803.   unsigned prev;     /* previous *src byte shifted by 8 bit to the left */
  2804.   register int bits, msb = has_planes - 1;
  2805.   int bitno;
  2806.  
  2807.   /* sanity checks */
  2808.   if (encode_planes > has_planes)
  2809.     encode_planes = has_planes;
  2810.   use_graycode = use_graycode != 0 && encode_planes > 1;
  2811.   
  2812.   for (p = 0; p < encode_planes; p++)
  2813.     memset(dest[p], 0, bpl * y);
  2814.   
  2815.   for (line = 0; line < y; line++) {                 /* lines loop */
  2816.     for (i = 0; i * 8 < x; i++) {                    /* dest bytes loop */
  2817.       for (k = 0; k < 8 && i * 8 + k < x; k++) {     /* pixel loop */
  2818.     prev = 0;
  2819.     for (p = 0; p < encode_planes; p++) {        /* bit planes loop */
  2820.       /* calculate which bit in *src do we want */
  2821.       bitno = (msb - p) & 7;
  2822.       /* put this bit with its left neighbor right adjusted into bits */
  2823.       bits = (prev | *src) >> bitno;
  2824.       /* go to next *src byte, but keep old */
  2825.       if (bitno == 0)
  2826.         prev = *src++ << 8;
  2827.       /* make space for inserting new bit */
  2828.       dest[p][bpl * line + i] <<= 1;
  2829.       /* insert bit, if requested apply Gray encoding */
  2830.       dest[p][bpl * line + i] |= (bits ^ (use_graycode & (bits>>1))) & 1;
  2831.       /*
  2832.        * Theorem: Let b(n),...,b(1),b(0) be the digits of a
  2833.        * binary word and let g(n),...,g(1),g(0) be the digits of the
  2834.        * corresponding Gray code word, then g(i) = b(i) xor b(i+1).
  2835.        */
  2836.     }
  2837.     /* skip unused *src bytes */
  2838.     for (;p < has_planes; p++)
  2839.       if (((msb - p) & 7) == 0)
  2840.         src++;
  2841.       }
  2842.     }
  2843.     for (p = 0; p < encode_planes; p++)              /* right padding loop */
  2844.       dest[p][bpl * (line + 1) - 1] <<= 8 - k;
  2845.   }
  2846.   
  2847.   return;
  2848. }
  2849.  
  2850. /* 
  2851.  * Merge the separate bit planes decoded by the JBIG decoder into an
  2852.  * integer pixel field. This is essentially the counterpart to
  2853.  * jbg_split_planes(). */
  2854. void jbg_dec_merge_planes(const struct jbg_dec_state *s, int use_graycode,
  2855.               void (*data_out)(unsigned char *start, size_t len,
  2856.                        void *file), void *file)
  2857. {
  2858. #define BUFLEN 4096
  2859.   int bpp, bpl;
  2860.   unsigned long line;
  2861.   unsigned i, k = 8;
  2862.   int p;
  2863.   unsigned char buf[BUFLEN];
  2864.   unsigned char *bp = buf;
  2865.   unsigned char **src;
  2866.   unsigned long x, y;
  2867.   unsigned v;
  2868.  
  2869.   /* sanity check */
  2870.   use_graycode = use_graycode != 0;
  2871.   
  2872.   x = jbg_dec_getwidth(s);
  2873.   y = jbg_dec_getheight(s);
  2874.   if (x <= 0 || y <= 0)
  2875.     return;
  2876.   bpp = (s->planes + 7) / 8;   /* bytes per pixel in dest image */
  2877.   bpl = (x + 7) / 8;           /* bytes per line in src plane */
  2878.  
  2879.   if (index[s->order & 7][LAYER] == 0)
  2880.     if (s->ii[0] < 1)
  2881.       return;
  2882.     else
  2883.       src = s->lhp[(s->ii[0] - 1) & 1];
  2884.   else
  2885.     src = s->lhp[s->d & 1];
  2886.   
  2887.   for (line = 0; line < y; line++) {                    /* lines loop */
  2888.     for (i = 0; i * 8 < x; i++) {                       /* src bytes loop */
  2889.       for (k = 0; k < 8 && i * 8 + k < x; k++) {        /* pixel loop */
  2890.     v = 0;
  2891.     for (p = 0; p < s->planes;) {                   /* dest bytes loop */
  2892.       do {
  2893.         v = (v << 1) |
  2894.           (((src[p][bpl * line + i] >> (7 - k)) & 1) ^
  2895.            (use_graycode & v));
  2896.       } while ((s->planes - ++p) & 7);
  2897.       *bp++ = v;
  2898.       if (bp - buf == BUFLEN) {
  2899.         data_out(buf, BUFLEN, file);
  2900.         bp = buf;
  2901.       }
  2902.     }
  2903.       }
  2904.     }
  2905.   }
  2906.   
  2907.   if (bp - buf > 0)
  2908.     data_out(buf, bp - buf, file);
  2909.   
  2910.   return;
  2911. }
  2912.