jdlhuff.c

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