compiler/libjpeg/main/jdshuff.c

   1 /*
   2     $Id$
   3 */
   4
   5 /*
   6  * jdshuff.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 sequential 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 "jlossy.h"             /* Private declarations for lossy codec */
  25 #include "jdhuff.h"             /* Declarations shared with jd*huff.c */
  26
  27
  28 /*
  29  * Private entropy decoder object for Huffman decoding.
  30  *
  31  * The savable_state subrecord contains fields that change within an MCU,
  32  * but must not be updated permanently until we complete the MCU.
  33  */
  34
  35 typedef struct {
  36   int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
  37 } savable_state;
  38
  39 /* This macro is to work around compilers with missing or broken
  40  * structure assignment.  You'll need to fix this code if you have
  41  * such a compiler and you change MAX_COMPS_IN_SCAN.
  42  */
  43
  44 #ifndef NO_STRUCT_ASSIGN
  45 #define ASSIGN_STATE(dest,src)  ((dest) = (src))
  46 #else
  47 #if MAX_COMPS_IN_SCAN == 4
  48 #define ASSIGN_STATE(dest,src)  \
  49         ((dest).last_dc_val[0] = (src).last_dc_val[0], \
  50          (dest).last_dc_val[1] = (src).last_dc_val[1], \
  51          (dest).last_dc_val[2] = (src).last_dc_val[2], \
  52          (dest).last_dc_val[3] = (src).last_dc_val[3])
  53 #endif
  54 #endif
  55
  56
  57 typedef struct {
  58   huffd_common_fields;          /* Fields shared with other entropy decoders */
  59
  60   /* These fields are loaded into local variables at start of each MCU.
  61    * In case of suspension, we exit WITHOUT updating them.
  62    */
  63   savable_state saved;          /* Other state at start of MCU */
  64
  65   /* These fields are NOT loaded into local working state. */
  66   unsigned int restarts_to_go;  /* MCUs left in this restart interval */
  67
  68   /* Pointers to derived tables (these workspaces have image lifespan) */
  69   d_derived_tbl * dc_derived_tbls[NUM_HUFF_TBLS];
  70   d_derived_tbl * ac_derived_tbls[NUM_HUFF_TBLS];
  71
  72   /* Precalculated info set up by start_pass for use in decode_mcu: */
  73
  74   /* Pointers to derived tables to be used for each block within an MCU */
  75   d_derived_tbl * dc_cur_tbls[D_MAX_DATA_UNITS_IN_MCU];
  76   d_derived_tbl * ac_cur_tbls[D_MAX_DATA_UNITS_IN_MCU];
  77   /* Whether we care about the DC and AC coefficient values for each block */
  78   boolean dc_needed[D_MAX_DATA_UNITS_IN_MCU];
  79   boolean ac_needed[D_MAX_DATA_UNITS_IN_MCU];
  80 } shuff_entropy_decoder;
  81
  82 typedef shuff_entropy_decoder * shuff_entropy_ptr;
  83
  84
  85 /*
  86  * Initialize for a Huffman-compressed scan.
  87  */
  88
  89 METHODDEF(void)
  90 start_pass_huff_decoder (j_decompress_ptr cinfo)
  91 {
  92   j_lossy_d_ptr lossyd = (j_lossy_d_ptr) cinfo->codec;
  93   shuff_entropy_ptr entropy = (shuff_entropy_ptr) lossyd->entropy_private;
  94   int ci, blkn, dctbl, actbl;
  95   jpeg_component_info * compptr;
  96
  97   /* Check that the scan parameters Ss, Se, Ah/Al are OK for sequential JPEG.
  98    * This ought to be an error condition, but we make it a warning because
  99    * there are some baseline files out there with all zeroes in these bytes.
 100    */
 101   if (cinfo->Ss != 0 || cinfo->Se != DCTSIZE2-1 ||
 102       cinfo->Ah != 0 || cinfo->Al != 0)
 103     WARNMS(cinfo, JWRN_NOT_SEQUENTIAL);
 104
 105   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
 106     compptr = cinfo->cur_comp_info[ci];
 107     dctbl = compptr->dc_tbl_no;
 108     actbl = compptr->ac_tbl_no;
 109     /* Compute derived values for Huffman tables */
 110     /* We may do this more than once for a table, but it's not expensive */
 111     jpeg_make_d_derived_tbl(cinfo, TRUE, dctbl,
 112                             & entropy->dc_derived_tbls[dctbl]);
 113     jpeg_make_d_derived_tbl(cinfo, FALSE, actbl,
 114                             & entropy->ac_derived_tbls[actbl]);
 115     /* Initialize DC predictions to 0 */
 116     entropy->saved.last_dc_val[ci] = 0;
 117   }
 118
 119   /* Precalculate decoding info for each block in an MCU of this scan */
 120   for (blkn = 0; blkn < cinfo->data_units_in_MCU; blkn++) {
 121     ci = cinfo->MCU_membership[blkn];
 122     compptr = cinfo->cur_comp_info[ci];
 123     /* Precalculate which table to use for each block */
 124     entropy->dc_cur_tbls[blkn] = entropy->dc_derived_tbls[compptr->dc_tbl_no];
 125     entropy->ac_cur_tbls[blkn] = entropy->ac_derived_tbls[compptr->ac_tbl_no];
 126     /* Decide whether we really care about the coefficient values */
 127     if (compptr->component_needed) {
 128       entropy->dc_needed[blkn] = TRUE;
 129       /* we don't need the ACs if producing a 1/8th-size image */
 130       entropy->ac_needed[blkn] = (compptr->codec_data_unit > 1);
 131     } else {
 132       entropy->dc_needed[blkn] = entropy->ac_needed[blkn] = FALSE;
 133     }
 134   }
 135
 136   /* Initialize bitread state variables */
 137   entropy->bitstate.bits_left = 0;
 138   entropy->bitstate.get_buffer = 0; /* unnecessary, but keeps Purify quiet */
 139   entropy->insufficient_data = FALSE;
 140
 141   /* Initialize restart counter */
 142   entropy->restarts_to_go = cinfo->restart_interval;
 143 }
 144
 145
 146 /*
 147  * Figure F.12: extend sign bit.
 148  * On some machines, a shift and add will be faster than a table lookup.
 149  */
 150
 151 #ifdef AVOID_TABLES
 152
 153 #define HUFF_EXTEND(x,s)  ((x) < (1<<((s)-1)) ? (x) + (((-1)<<(s)) + 1) : (x))
 154
 155 #else
 156
 157 #define HUFF_EXTEND(x,s)  ((x) < extend_test[s] ? (x) + extend_offset[s] : (x))
 158
 159 static const int extend_test[16] =   /* entry n is 2**(n-1) */
 160   { 0, 0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080,
 161     0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000 };
 162
 163 static const int extend_offset[16] = /* entry n is (-1 << n) + 1 */
 164   { 0, ((-1)<<1) + 1, ((-1)<<2) + 1, ((-1)<<3) + 1, ((-1)<<4) + 1,
 165     ((-1)<<5) + 1, ((-1)<<6) + 1, ((-1)<<7) + 1, ((-1)<<8) + 1,
 166     ((-1)<<9) + 1, ((-1)<<10) + 1, ((-1)<<11) + 1, ((-1)<<12) + 1,
 167     ((-1)<<13) + 1, ((-1)<<14) + 1, ((-1)<<15) + 1 };
 168
 169 #endif /* AVOID_TABLES */
 170
 171
 172 /*
 173  * Check for a restart marker & resynchronize decoder.
 174  * Returns FALSE if must suspend.
 175  */
 176
 177 LOCAL(boolean)
 178 process_restart (j_decompress_ptr cinfo)
 179 {
 180   j_lossy_d_ptr lossyd = (j_lossy_d_ptr) cinfo->codec;
 181   shuff_entropy_ptr entropy = (shuff_entropy_ptr) lossyd->entropy_private;
 182   int ci;
 183
 184   /* Throw away any unused bits remaining in bit buffer; */
 185   /* include any full bytes in next_marker's count of discarded bytes */
 186   cinfo->marker->discarded_bytes += entropy->bitstate.bits_left / 8;
 187   entropy->bitstate.bits_left = 0;
 188
 189   /* Advance past the RSTn marker */
 190   if (! (*cinfo->marker->read_restart_marker) (cinfo))
 191     return FALSE;
 192
 193   /* Re-initialize DC predictions to 0 */
 194   for (ci = 0; ci < cinfo->comps_in_scan; ci++)
 195     entropy->saved.last_dc_val[ci] = 0;
 196
 197   /* Reset restart counter */
 198   entropy->restarts_to_go = cinfo->restart_interval;
 199
 200   /* Reset out-of-data flag, unless read_restart_marker left us smack up
 201    * against a marker.  In that case we will end up treating the next data
 202    * segment as empty, and we can avoid producing bogus output pixels by
 203    * leaving the flag set.
 204    */
 205   if (cinfo->unread_marker == 0)
 206     entropy->insufficient_data = FALSE;
 207
 208   return TRUE;
 209 }
 210
 211
 212 /*
 213  * Decode and return one MCU's worth of Huffman-compressed coefficients.
 214  * The coefficients are reordered from zigzag order into natural array order,
 215  * but are not dequantized.
 216  *
 217  * The i'th block of the MCU is stored into the block pointed to by
 218  * MCU_data[i].  WE ASSUME THIS AREA HAS BEEN ZEROED BY THE CALLER.
 219  * (Wholesale zeroing is usually a little faster than retail...)
 220  *
 221  * Returns FALSE if data source requested suspension.  In that case no
 222  * changes have been made to permanent state.  (Exception: some output
 223  * coefficients may already have been assigned.  This is harmless for
 224  * this module, since we'll just re-assign them on the next call.)
 225  */
 226
 227 METHODDEF(boolean)
 228 decode_mcu (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
 229 {
 230   j_lossy_d_ptr lossyd = (j_lossy_d_ptr) cinfo->codec;
 231   shuff_entropy_ptr entropy = (shuff_entropy_ptr) lossyd->entropy_private;
 232   int blkn;
 233   BITREAD_STATE_VARS;
 234   savable_state state;
 235
 236   /* Process restart marker if needed; may have to suspend */
 237   if (cinfo->restart_interval) {
 238     if (entropy->restarts_to_go == 0)
 239       if (! process_restart(cinfo))
 240         return FALSE;
 241   }
 242
 243   /* If we've run out of data, just leave the MCU set to zeroes.
 244    * This way, we return uniform gray for the remainder of the segment.
 245    */
 246   if (! entropy->insufficient_data) {
 247
 248     /* Load up working state */
 249     BITREAD_LOAD_STATE(cinfo,entropy->bitstate);
 250     ASSIGN_STATE(state, entropy->saved);
 251
 252     /* Outer loop handles each block in the MCU */
 253
 254     for (blkn = 0; blkn < cinfo->data_units_in_MCU; blkn++) {
 255       JBLOCKROW block = MCU_data[blkn];
 256       d_derived_tbl * dctbl = entropy->dc_cur_tbls[blkn];
 257       d_derived_tbl * actbl = entropy->ac_cur_tbls[blkn];
 258       register int s, k, r;
 259
 260       /* Decode a single block's worth of coefficients */
 261
 262       /* Section F.2.2.1: decode the DC coefficient difference */
 263       HUFF_DECODE(s, br_state, dctbl, return FALSE, label1);
 264       if (s) {
 265         CHECK_BIT_BUFFER(br_state, s, return FALSE);
 266         r = GET_BITS(s);
 267         s = HUFF_EXTEND(r, s);
 268       }
 269
 270       if (entropy->dc_needed[blkn]) {
 271         /* Convert DC difference to actual value, update last_dc_val */
 272         int ci = cinfo->MCU_membership[blkn];
 273         s += state.last_dc_val[ci];
 274         state.last_dc_val[ci] = s;
 275         /* Output the DC coefficient (assumes jpeg_natural_order[0] = 0) */
 276         (*block)[0] = (JCOEF) s;
 277       }
 278
 279       if (entropy->ac_needed[blkn]) {
 280
 281         /* Section F.2.2.2: decode the AC coefficients */
 282         /* Since zeroes are skipped, output area must be cleared beforehand */
 283         for (k = 1; k < DCTSIZE2; k++) {
 284           HUFF_DECODE(s, br_state, actbl, return FALSE, label2);
 285
 286           r = s >> 4;
 287           s &= 15;
 288
 289           if (s) {
 290             k += r;
 291             CHECK_BIT_BUFFER(br_state, s, return FALSE);
 292             r = GET_BITS(s);
 293             s = HUFF_EXTEND(r, s);
 294             /* Output coefficient in natural (dezigzagged) order.
 295              * Note: the extra entries in jpeg_natural_order[] will save us
 296              * if k >= DCTSIZE2, which could happen if the data is corrupted.
 297              */
 298             (*block)[jpeg_natural_order[k]] = (JCOEF) s;
 299           } else {
 300             if (r != 15)
 301               break;
 302             k += 15;
 303           }
 304         }
 305
 306       } else {
 307
 308         /* Section F.2.2.2: decode the AC coefficients */
 309         /* In this path we just discard the values */
 310         for (k = 1; k < DCTSIZE2; k++) {
 311           HUFF_DECODE(s, br_state, actbl, return FALSE, label3);
 312
 313           r = s >> 4;
 314           s &= 15;
 315
 316           if (s) {
 317             k += r;
 318             CHECK_BIT_BUFFER(br_state, s, return FALSE);
 319             DROP_BITS(s);
 320           } else {
 321             if (r != 15)
 322               break;
 323             k += 15;
 324           }
 325         }
 326
 327       }
 328     }
 329
 330     /* Completed MCU, so update state */
 331     BITREAD_SAVE_STATE(cinfo,entropy->bitstate);
 332     ASSIGN_STATE(entropy->saved, state);
 333   }
 334
 335   /* Account for restart interval (no-op if not using restarts) */
 336   entropy->restarts_to_go--;
 337
 338   return TRUE;
 339 }
 340
 341
 342 /*
 343  * Module initialization routine for Huffman entropy decoding.
 344  */
 345
 346 JGLOBAL(void)
 347 jinit_shuff_decoder (j_decompress_ptr cinfo)
 348 {
 349   j_lossy_d_ptr lossyd = (j_lossy_d_ptr) cinfo->codec;
 350   shuff_entropy_ptr entropy;
 351   int i;
 352
 353   entropy = (shuff_entropy_ptr)
 354     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
 355                                 SIZEOF(shuff_entropy_decoder));
 356   lossyd->entropy_private = (void *) entropy;
 357   lossyd->entropy_start_pass = start_pass_huff_decoder;
 358   lossyd->entropy_decode_mcu = decode_mcu;
 359
 360   /* Mark tables unallocated */
 361   for (i = 0; i < NUM_HUFF_TBLS; i++) {
 362     entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL;
 363   }
 364 }