compiler/libjpeg/main/jdlhuff.c

   1 /*
   2     $Id$
   3 */
   4
   5 /*
   6  * jdlhuff.c
   7  *
   8  * Copyright (C) 1991-1998, Thomas G. Lane.
   9  * This file is part of the Independent JPEG Group's software.
  10  * For conditions of distribution and use, see the accompanying README file.
  11  *
  12  * This file contains Huffman entropy decoding routines for lossless JPEG.
  13  *
  14  * Much of the complexity here has to do with supporting input suspension.
  15  * If the data source module demands suspension, we want to be able to back
  16  * up to the start of the current MCU.  To do this, we copy state variables
  17  * into local working storage, and update them back to the permanent
  18  * storage only upon successful completion of an MCU.
  19  */
  20
  21 #define JPEG_INTERNALS
  22 #include "jinclude.h"
  23 #include "jpeglib.h"
  24 #include "jlossls.h"            /* Private declarations for lossless codec */
  25 #include "jdhuff.h"             /* Declarations shared with jd*huff.c */
  26
  27
  28 #ifdef D_LOSSLESS_SUPPORTED
  29
  30 typedef struct {
  31   int ci, yoffset, MCU_width;
  32 } lhd_output_ptr_info;
  33
  34 /*
  35  * Private entropy decoder object for lossless Huffman decoding.
  36  */
  37
  38 typedef struct {
  39   huffd_common_fields;          /* Fields shared with other entropy decoders */
  40
  41   /* Pointers to derived tables (these workspaces have image lifespan) */
  42   d_derived_tbl * derived_tbls[NUM_HUFF_TBLS];
  43
  44   /* Precalculated info set up by start_pass for use in decode_mcus: */
  45
  46   /* Pointers to derived tables to be used for each data unit within an MCU */
  47   d_derived_tbl * cur_tbls[D_MAX_DATA_UNITS_IN_MCU];
  48
  49   /* Pointers to the proper output difference row for each group of data units
  50    * within an MCU.  For each component, there are Vi groups of Hi data units.
  51    */
  52   JDIFFROW output_ptr[D_MAX_DATA_UNITS_IN_MCU];
  53
  54   /* Number of output pointers in use for the current MCU.  This is the sum
  55    * of all Vi in the MCU.
  56    */
  57   int num_output_ptrs;
  58
  59   /* Information used for positioning the output pointers within the output
  60    * difference rows.
  61    */
  62   lhd_output_ptr_info output_ptr_info[D_MAX_DATA_UNITS_IN_MCU];
  63
  64   /* Index of the proper output pointer for each data unit within an MCU */
  65   int output_ptr_index[D_MAX_DATA_UNITS_IN_MCU];
  66
  67 } lhuff_entropy_decoder;
  68
  69 typedef lhuff_entropy_decoder * lhuff_entropy_ptr;
  70
  71
  72 /*
  73  * Initialize for a Huffman-compressed scan.
  74  */
  75
  76 METHODDEF(void)
  77 start_pass_lhuff_decoder (j_decompress_ptr cinfo)
  78 {
  79   j_lossless_d_ptr losslsd = (j_lossless_d_ptr) cinfo->codec;
  80   lhuff_entropy_ptr entropy = (lhuff_entropy_ptr) losslsd->entropy_private;
  81   int ci, dctbl, sampn, ptrn, yoffset, xoffset;
  82   jpeg_component_info * compptr;
  83
  84   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
  85     compptr = cinfo->cur_comp_info[ci];
  86     dctbl = compptr->dc_tbl_no;
  87     /* Make sure requested tables are present */
  88     if (dctbl < 0 || dctbl >= NUM_HUFF_TBLS ||
  89         cinfo->dc_huff_tbl_ptrs[dctbl] == NULL)
  90       ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, dctbl);
  91     /* Compute derived values for Huffman tables */
  92     /* We may do this more than once for a table, but it's not expensive */
  93     jpeg_make_d_derived_tbl(cinfo, TRUE, dctbl,
  94                             & entropy->derived_tbls[dctbl]);
  95   }
  96
  97   /* Precalculate decoding info for each sample in an MCU of this scan */
  98   for (sampn = 0, ptrn = 0; sampn < cinfo->data_units_in_MCU;) {
  99     compptr = cinfo->cur_comp_info[cinfo->MCU_membership[sampn]];
 100     ci = compptr->component_index;
 101     for (yoffset = 0; yoffset < compptr->MCU_height; yoffset++, ptrn++) {
 102       /* Precalculate the setup info for each output pointer */
 103       entropy->output_ptr_info[ptrn].ci = ci;
 104       entropy->output_ptr_info[ptrn].yoffset = yoffset;
 105       entropy->output_ptr_info[ptrn].MCU_width = compptr->MCU_width;
 106       for (xoffset = 0; xoffset < compptr->MCU_width; xoffset++, sampn++) {
 107         /* Precalculate the output pointer index for each sample */
 108         entropy->output_ptr_index[sampn] = ptrn;
 109         /* Precalculate which table to use for each sample */
 110         entropy->cur_tbls[sampn] = entropy->derived_tbls[compptr->dc_tbl_no];
 111       }
 112     }
 113   }
 114   entropy->num_output_ptrs = ptrn;
 115
 116   /* Initialize bitread state variables */
 117   entropy->bitstate.bits_left = 0;
 118   entropy->bitstate.get_buffer = 0; /* unnecessary, but keeps Purify quiet */
 119   entropy->insufficient_data = FALSE;
 120 }
 121
 122
 123 /*
 124  * Figure F.12: extend sign bit.
 125  * On some machines, a shift and add will be faster than a table lookup.
 126  */
 127
 128 #ifdef AVOID_TABLES
 129
 130 #define HUFF_EXTEND(x,s)  ((x) < (1<<((s)-1)) ? (x) + (((-1)<<(s)) + 1) : (x))
 131
 132 #else
 133
 134 #define HUFF_EXTEND(x,s)  ((x) < extend_test[s] ? (x) + extend_offset[s] : (x))
 135
 136 static const int extend_test[16] =   /* entry n is 2**(n-1) */
 137   { 0, 0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080,
 138     0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000 };
 139
 140 static const int extend_offset[16] = /* entry n is (-1 << n) + 1 */
 141   { 0, ((-1)<<1) + 1, ((-1)<<2) + 1, ((-1)<<3) + 1, ((-1)<<4) + 1,
 142     ((-1)<<5) + 1, ((-1)<<6) + 1, ((-1)<<7) + 1, ((-1)<<8) + 1,
 143     ((-1)<<9) + 1, ((-1)<<10) + 1, ((-1)<<11) + 1, ((-1)<<12) + 1,
 144     ((-1)<<13) + 1, ((-1)<<14) + 1, ((-1)<<15) + 1 };
 145
 146 #endif /* AVOID_TABLES */
 147
 148
 149 /*
 150  * Check for a restart marker & resynchronize decoder.
 151  * Returns FALSE if must suspend.
 152  */
 153
 154 METHODDEF(boolean)
 155 process_restart (j_decompress_ptr cinfo)
 156 {
 157   j_lossless_d_ptr losslsd = (j_lossless_d_ptr) cinfo->codec;
 158   lhuff_entropy_ptr entropy = (lhuff_entropy_ptr) losslsd->entropy_private;
 159   int ci;
 160
 161   /* Throw away any unused bits remaining in bit buffer; */
 162   /* include any full bytes in next_marker's count of discarded bytes */
 163   cinfo->marker->discarded_bytes += entropy->bitstate.bits_left / 8;
 164   entropy->bitstate.bits_left = 0;
 165
 166   /* Advance past the RSTn marker */
 167   if (! (*cinfo->marker->read_restart_marker) (cinfo))
 168     return FALSE;
 169
 170   /* Reset out-of-data flag, unless read_restart_marker left us smack up
 171    * against a marker.  In that case we will end up treating the next data
 172    * segment as empty, and we can avoid producing bogus output pixels by
 173    * leaving the flag set.
 174    */
 175   if (cinfo->unread_marker == 0)
 176     entropy->insufficient_data = FALSE;
 177
 178   return TRUE;
 179 }
 180
 181
 182 /*
 183  * Decode and return nMCU's worth of Huffman-compressed differences.
 184  * Each MCU is also disassembled and placed accordingly in diff_buf.
 185  *
 186  * MCU_col_num specifies the column of the first MCU being requested within
 187  * the MCU-row.  This tells us where to position the output row pointers in
 188  * diff_buf.
 189  *
 190  * Returns the number of MCUs decoded.  This may be less than nMCU if data
 191  * source requested suspension.  In that case no changes have been made to
 192  * permanent state.  (Exception: some output differences may already have
 193  * been assigned.  This is harmless for this module, since we'll just
 194  * re-assign them on the next call.)
 195  */
 196
 197 METHODDEF(JDIMENSION)
 198 decode_mcus (j_decompress_ptr cinfo, JDIFFIMAGE diff_buf,
 199              JDIMENSION MCU_row_num, JDIMENSION MCU_col_num, JDIMENSION nMCU)
 200 {
 201   j_lossless_d_ptr losslsd = (j_lossless_d_ptr) cinfo->codec;
 202   lhuff_entropy_ptr entropy = (lhuff_entropy_ptr) losslsd->entropy_private;
 203   int mcu_num, sampn, ci, yoffset, MCU_width, ptrn;
 204   BITREAD_STATE_VARS;
 205
 206   /* Set output pointer locations based on MCU_col_num */
 207   for (ptrn = 0; ptrn < entropy->num_output_ptrs; ptrn++) {
 208     ci = entropy->output_ptr_info[ptrn].ci;
 209     yoffset = entropy->output_ptr_info[ptrn].yoffset;
 210     MCU_width = entropy->output_ptr_info[ptrn].MCU_width;
 211     entropy->output_ptr[ptrn] =
 212       diff_buf[ci][MCU_row_num + yoffset] + (MCU_col_num * MCU_width);
 213   }
 214
 215   /*
 216    * If we've run out of data, zero out the buffers and return.
 217    * By resetting the undifferencer, the output samples will be CENTERJSAMPLE.
 218    *
 219    * NB: We should find a way to do this without interacting with the
 220    * undifferencer module directly.
 221    */
 222   if (entropy->insufficient_data) {
 223     for (ptrn = 0; ptrn < entropy->num_output_ptrs; ptrn++)
 224       jzero_far((void FAR *) entropy->output_ptr[ptrn],
 225                 nMCU * entropy->output_ptr_info[ptrn].MCU_width * SIZEOF(JDIFF));
 226
 227     (*losslsd->predict_process_restart) (cinfo);
 228   }
 229
 230   else {
 231
 232     /* Load up working state */
 233     BITREAD_LOAD_STATE(cinfo,entropy->bitstate);
 234
 235     /* Outer loop handles the number of MCU requested */
 236
 237     for (mcu_num = 0; mcu_num < nMCU; mcu_num++) {
 238
 239       /* Inner loop handles the samples in the MCU */
 240       for (sampn = 0; sampn < cinfo->data_units_in_MCU; sampn++) {
 241         d_derived_tbl * dctbl = entropy->cur_tbls[sampn];
 242         register int s, r;
 243
 244         /* Section H.2.2: decode the sample difference */
 245         HUFF_DECODE(s, br_state, dctbl, return mcu_num, label1);
 246         if (s) {
 247           if (s == 16)  /* special case: always output 32768 */
 248             s = 32768;
 249           else {        /* normal case: fetch subsequent bits */
 250             CHECK_BIT_BUFFER(br_state, s, return mcu_num);
 251             r = GET_BITS(s);
 252             s = HUFF_EXTEND(r, s);
 253           }
 254         }
 255
 256         /* Output the sample difference */
 257         *entropy->output_ptr[entropy->output_ptr_index[sampn]]++ = (JDIFF) s;
 258       }
 259
 260       /* Completed MCU, so update state */
 261       BITREAD_SAVE_STATE(cinfo,entropy->bitstate);
 262     }
 263   }
 264
 265  return nMCU;
 266 }
 267
 268
 269 /*
 270  * Module initialization routine for lossless Huffman entropy decoding.
 271  */
 272
 273 JGLOBAL(void)
 274 jinit_lhuff_decoder (j_decompress_ptr cinfo)
 275 {
 276   j_lossless_d_ptr losslsd = (j_lossless_d_ptr) cinfo->codec;
 277   lhuff_entropy_ptr entropy;
 278   int i;
 279
 280   entropy = (lhuff_entropy_ptr)
 281     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
 282                                 SIZEOF(lhuff_entropy_decoder));
 283   losslsd->entropy_private = (void *) entropy;
 284   losslsd->entropy_start_pass = start_pass_lhuff_decoder;
 285   losslsd->entropy_process_restart = process_restart;
 286   losslsd->entropy_decode_mcus = decode_mcus;
 287
 288   /* Mark tables unallocated */
 289   for (i = 0; i < NUM_HUFF_TBLS; i++) {
 290     entropy->derived_tbls[i] = NULL;
 291   }
 292 }
 293
 294 #endif /* D_LOSSLESS_SUPPORTED */