jpeg/jcphuff.c

   1 /*
   2  * jcphuff.c
   3  *
   4  * Copyright (C) 1995-1997, Thomas G. Lane.
   5  * This file is part of the Independent JPEG Group's software.
   6  * For conditions of distribution and use, see the accompanying README file.
   7  *
   8  * This file contains Huffman entropy encoding routines for progressive JPEG.
   9  *
  10  * We do not support output suspension in this module, since the library
  11  * currently does not allow multiple-scan files to be written with output
  12  * suspension.
  13  */
  14
  15 #define JPEG_INTERNALS
  16 #include "jinclude.h"
  17 #include "jpeglib.h"
  18 #include "jchuff.h"             /* Declarations shared with jchuff.c */
  19
  20 #ifdef C_PROGRESSIVE_SUPPORTED
  21
  22 /* Expanded entropy encoder object for progressive Huffman encoding. */
  23
  24 typedef struct {
  25   struct jpeg_entropy_encoder pub; /* public fields */
  26
  27   /* Mode flag: TRUE for optimization, FALSE for actual data output */
  28   boolean gather_statistics;
  29
  30   /* Bit-level coding status.
  31    * next_output_byte/free_in_buffer are local copies of cinfo->dest fields.
  32    */
  33   JOCTET * next_output_byte;    /* => next byte to write in buffer */
  34   size_t free_in_buffer;        /* # of byte spaces remaining in buffer */
  35   INT32 put_buffer;             /* current bit-accumulation buffer */
  36   int put_bits;                 /* # of bits now in it */
  37   j_compress_ptr cinfo;         /* link to cinfo (needed for dump_buffer) */
  38
  39   /* Coding status for DC components */
  40   int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
  41
  42   /* Coding status for AC components */
  43   int ac_tbl_no;                /* the table number of the single component */
  44   unsigned int EOBRUN;          /* run length of EOBs */
  45   unsigned int BE;              /* # of buffered correction bits before MCU */
  46   char * bit_buffer;            /* buffer for correction bits (1 per char) */
  47   /* packing correction bits tightly would save some space but cost time... */
  48
  49   unsigned int restarts_to_go;  /* MCUs left in this restart interval */
  50   int next_restart_num;         /* next restart number to write (0-7) */
  51
  52   /* Pointers to derived tables (these workspaces have image lifespan).
  53    * Since any one scan codes only DC or only AC, we only need one set
  54    * of tables, not one for DC and one for AC.
  55    */
  56   c_derived_tbl * derived_tbls[NUM_HUFF_TBLS];
  57
  58   /* Statistics tables for optimization; again, one set is enough */
  59   long * count_ptrs[NUM_HUFF_TBLS];
  60 } phuff_entropy_encoder;
  61
  62 typedef phuff_entropy_encoder * phuff_entropy_ptr;
  63
  64 /* MAX_CORR_BITS is the number of bits the AC refinement correction-bit
  65  * buffer can hold.  Larger sizes may slightly improve compression, but
  66  * 1000 is already well into the realm of overkill.
  67  * The minimum safe size is 64 bits.
  68  */
  69
  70 #define MAX_CORR_BITS  1000     /* Max # of correction bits I can buffer */
  71
  72 /* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than INT32.
  73  * We assume that int right shift is unsigned if INT32 right shift is,
  74  * which should be safe.
  75  */
  76
  77 #ifdef RIGHT_SHIFT_IS_UNSIGNED
  78 #define ISHIFT_TEMPS    int ishift_temp;
  79 #define IRIGHT_SHIFT(x,shft)  \
  80         ((ishift_temp = (x)) < 0 ? \
  81          (ishift_temp >> (shft)) | ((~0) << (16-(shft))) : \
  82          (ishift_temp >> (shft)))
  83 #else
  84 #define ISHIFT_TEMPS
  85 #define IRIGHT_SHIFT(x,shft)    ((x) >> (shft))
  86 #endif
  87
  88 /* Forward declarations */
  89 METHODDEF(boolean) encode_mcu_DC_first JPP((j_compress_ptr cinfo,
  90                                             JBLOCKROW *MCU_data));
  91 METHODDEF(boolean) encode_mcu_AC_first JPP((j_compress_ptr cinfo,
  92                                             JBLOCKROW *MCU_data));
  93 METHODDEF(boolean) encode_mcu_DC_refine JPP((j_compress_ptr cinfo,
  94                                              JBLOCKROW *MCU_data));
  95 METHODDEF(boolean) encode_mcu_AC_refine JPP((j_compress_ptr cinfo,
  96                                              JBLOCKROW *MCU_data));
  97 METHODDEF(void) finish_pass_phuff JPP((j_compress_ptr cinfo));
  98 METHODDEF(void) finish_pass_gather_phuff JPP((j_compress_ptr cinfo));
  99
 100
 101 /*
 102  * Initialize for a Huffman-compressed scan using progressive JPEG.
 103  */
 104
 105 METHODDEF(void)
 106 start_pass_phuff (j_compress_ptr cinfo, boolean gather_statistics)
 107 {
 108   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
 109   boolean is_DC_band;
 110   int ci, tbl;
 111   jpeg_component_info * compptr;
 112
 113   entropy->cinfo = cinfo;
 114   entropy->gather_statistics = gather_statistics;
 115
 116   is_DC_band = (cinfo->Ss == 0);
 117
 118   /* We assume jcmaster.c already validated the scan parameters. */
 119
 120   /* Select execution routines */
 121   if (cinfo->Ah == 0) {
 122     if (is_DC_band)
 123       entropy->pub.encode_mcu = encode_mcu_DC_first;
 124     else
 125       entropy->pub.encode_mcu = encode_mcu_AC_first;
 126   } else {
 127     if (is_DC_band)
 128       entropy->pub.encode_mcu = encode_mcu_DC_refine;
 129     else {
 130       entropy->pub.encode_mcu = encode_mcu_AC_refine;
 131       /* AC refinement needs a correction bit buffer */
 132       if (entropy->bit_buffer == NULL)
 133         entropy->bit_buffer = (char *)
 134           (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
 135                                       MAX_CORR_BITS * SIZEOF(char));
 136     }
 137   }
 138   if (gather_statistics)
 139     entropy->pub.finish_pass = finish_pass_gather_phuff;
 140   else
 141     entropy->pub.finish_pass = finish_pass_phuff;
 142
 143   /* Only DC coefficients may be interleaved, so cinfo->comps_in_scan = 1
 144    * for AC coefficients.
 145    */
 146   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
 147     compptr = cinfo->cur_comp_info[ci];
 148     /* Initialize DC predictions to 0 */
 149     entropy->last_dc_val[ci] = 0;
 150     /* Get table index */
 151     if (is_DC_band) {
 152       if (cinfo->Ah != 0)       /* DC refinement needs no table */
 153         continue;
 154       tbl = compptr->dc_tbl_no;
 155     } else {
 156       entropy->ac_tbl_no = tbl = compptr->ac_tbl_no;
 157     }
 158     if (gather_statistics) {
 159       /* Check for invalid table index */
 160       /* (make_c_derived_tbl does this in the other path) */
 161       if (tbl < 0 || tbl >= NUM_HUFF_TBLS)
 162         ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tbl);
 163       /* Allocate and zero the statistics tables */
 164       /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */
 165       if (entropy->count_ptrs[tbl] == NULL)
 166         entropy->count_ptrs[tbl] = (long *)
 167           (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
 168                                       257 * SIZEOF(long));
 169       MEMZERO(entropy->count_ptrs[tbl], 257 * SIZEOF(long));
 170     } else {
 171       /* Compute derived values for Huffman table */
 172       /* We may do this more than once for a table, but it's not expensive */
 173       jpeg_make_c_derived_tbl(cinfo, is_DC_band, tbl,
 174                               & entropy->derived_tbls[tbl]);
 175     }
 176   }
 177
 178   /* Initialize AC stuff */
 179   entropy->EOBRUN = 0;
 180   entropy->BE = 0;
 181
 182   /* Initialize bit buffer to empty */
 183   entropy->put_buffer = 0;
 184   entropy->put_bits = 0;
 185
 186   /* Initialize restart stuff */
 187   entropy->restarts_to_go = cinfo->restart_interval;
 188   entropy->next_restart_num = 0;
 189 }
 190
 191
 192 /* Outputting bytes to the file.
 193  * NB: these must be called only when actually outputting,
 194  * that is, entropy->gather_statistics == FALSE.
 195  */
 196
 197 /* Emit a byte */
 198 #define emit_byte(entropy,val)  \
 199         { *(entropy)->next_output_byte++ = (JOCTET) (val);  \
 200           if (--(entropy)->free_in_buffer == 0)  \
 201             dump_buffer(entropy); }
 202
 203
 204 LOCAL(void)
 205 dump_buffer (phuff_entropy_ptr entropy)
 206 /* Empty the output buffer; we do not support suspension in this module. */
 207 {
 208   struct jpeg_destination_mgr * dest = entropy->cinfo->dest;
 209
 210   if (! (*dest->empty_output_buffer) (entropy->cinfo))
 211     ERREXIT(entropy->cinfo, JERR_CANT_SUSPEND);
 212   /* After a successful buffer dump, must reset buffer pointers */
 213   entropy->next_output_byte = dest->next_output_byte;
 214   entropy->free_in_buffer = dest->free_in_buffer;
 215 }
 216
 217
 218 /* Outputting bits to the file */
 219
 220 /* Only the right 24 bits of put_buffer are used; the valid bits are
 221  * left-justified in this part.  At most 16 bits can be passed to emit_bits
 222  * in one call, and we never retain more than 7 bits in put_buffer
 223  * between calls, so 24 bits are sufficient.
 224  */
 225
 226 INLINE
 227 LOCAL(void)
 228 emit_bits (phuff_entropy_ptr entropy, unsigned int code, int size)
 229 /* Emit some bits, unless we are in gather mode */
 230 {
 231   /* This routine is heavily used, so it's worth coding tightly. */
 232   register INT32 put_buffer = (INT32) code;
 233   register int put_bits = entropy->put_bits;
 234
 235   /* if size is 0, caller used an invalid Huffman table entry */
 236   if (size == 0)
 237     ERREXIT(entropy->cinfo, JERR_HUFF_MISSING_CODE);
 238
 239   if (entropy->gather_statistics)
 240     return;                     /* do nothing if we're only getting stats */
 241
 242   put_buffer &= (((INT32) 1)<<size) - 1; /* mask off any extra bits in code */
 243
 244   put_bits += size;             /* new number of bits in buffer */
 245
 246   put_buffer <<= 24 - put_bits; /* align incoming bits */
 247
 248   put_buffer |= entropy->put_buffer; /* and merge with old buffer contents */
 249
 250   while (put_bits >= 8) {
 251     int c = (int) ((put_buffer >> 16) & 0xFF);
 252
 253     emit_byte(entropy, c);
 254     if (c == 0xFF) {            /* need to stuff a zero byte? */
 255       emit_byte(entropy, 0);
 256     }
 257     put_buffer <<= 8;
 258     put_bits -= 8;
 259   }
 260
 261   entropy->put_buffer = put_buffer; /* update variables */
 262   entropy->put_bits = put_bits;
 263 }
 264
 265
 266 LOCAL(void)
 267 flush_bits (phuff_entropy_ptr entropy)
 268 {
 269   emit_bits(entropy, 0x7F, 7); /* fill any partial byte with ones */
 270   entropy->put_buffer = 0;     /* and reset bit-buffer to empty */
 271   entropy->put_bits = 0;
 272 }
 273
 274
 275 /*
 276  * Emit (or just count) a Huffman symbol.
 277  */
 278
 279 INLINE
 280 LOCAL(void)
 281 emit_symbol (phuff_entropy_ptr entropy, int tbl_no, int symbol)
 282 {
 283   if (entropy->gather_statistics)
 284     entropy->count_ptrs[tbl_no][symbol]++;
 285   else {
 286     c_derived_tbl * tbl = entropy->derived_tbls[tbl_no];
 287     emit_bits(entropy, tbl->ehufco[symbol], tbl->ehufsi[symbol]);
 288   }
 289 }
 290
 291
 292 /*
 293  * Emit bits from a correction bit buffer.
 294  */
 295
 296 LOCAL(void)
 297 emit_buffered_bits (phuff_entropy_ptr entropy, char * bufstart,
 298                     unsigned int nbits)
 299 {
 300   if (entropy->gather_statistics)
 301     return;                     /* no real work */
 302
 303   while (nbits > 0) {
 304     emit_bits(entropy, (unsigned int) (*bufstart), 1);
 305     bufstart++;
 306     nbits--;
 307   }
 308 }
 309
 310
 311 /*
 312  * Emit any pending EOBRUN symbol.
 313  */
 314
 315 LOCAL(void)
 316 emit_eobrun (phuff_entropy_ptr entropy)
 317 {
 318   register int temp, nbits;
 319
 320   if (entropy->EOBRUN > 0) {    /* if there is any pending EOBRUN */
 321     temp = entropy->EOBRUN;
 322     nbits = 0;
 323     while ((temp >>= 1))
 324       nbits++;
 325     /* safety check: shouldn't happen given limited correction-bit buffer */
 326     if (nbits > 14)
 327       ERREXIT(entropy->cinfo, JERR_HUFF_MISSING_CODE);
 328
 329     emit_symbol(entropy, entropy->ac_tbl_no, nbits << 4);
 330     if (nbits)
 331       emit_bits(entropy, entropy->EOBRUN, nbits);
 332
 333     entropy->EOBRUN = 0;
 334
 335     /* Emit any buffered correction bits */
 336     emit_buffered_bits(entropy, entropy->bit_buffer, entropy->BE);
 337     entropy->BE = 0;
 338   }
 339 }
 340
 341
 342 /*
 343  * Emit a restart marker & resynchronize predictions.
 344  */
 345
 346 LOCAL(void)
 347 emit_restart (phuff_entropy_ptr entropy, int restart_num)
 348 {
 349   int ci;
 350
 351   emit_eobrun(entropy);
 352
 353   if (! entropy->gather_statistics) {
 354     flush_bits(entropy);
 355     emit_byte(entropy, 0xFF);
 356     emit_byte(entropy, JPEG_RST0 + restart_num);
 357   }
 358
 359   if (entropy->cinfo->Ss == 0) {
 360     /* Re-initialize DC predictions to 0 */
 361     for (ci = 0; ci < entropy->cinfo->comps_in_scan; ci++)
 362       entropy->last_dc_val[ci] = 0;
 363   } else {
 364     /* Re-initialize all AC-related fields to 0 */
 365     entropy->EOBRUN = 0;
 366     entropy->BE = 0;
 367   }
 368 }
 369
 370
 371 /*
 372  * MCU encoding for DC initial scan (either spectral selection,
 373  * or first pass of successive approximation).
 374  */
 375
 376 METHODDEF(boolean)
 377 encode_mcu_DC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 378 {
 379   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
 380   register int temp, temp2;
 381   register int nbits;
 382   int blkn, ci;
 383   int Al = cinfo->Al;
 384   JBLOCKROW block;
 385   jpeg_component_info * compptr;
 386   ISHIFT_TEMPS
 387
 388   entropy->next_output_byte = cinfo->dest->next_output_byte;
 389   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
 390
 391   /* Emit restart marker if needed */
 392   if (cinfo->restart_interval)
 393     if (entropy->restarts_to_go == 0)
 394       emit_restart(entropy, entropy->next_restart_num);
 395
 396   /* Encode the MCU data blocks */
 397   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
 398     block = MCU_data[blkn];
 399     ci = cinfo->MCU_membership[blkn];
 400     compptr = cinfo->cur_comp_info[ci];
 401
 402     /* Compute the DC value after the required point transform by Al.
 403      * This is simply an arithmetic right shift.
 404      */
 405     temp2 = IRIGHT_SHIFT((int) ((*block)[0]), Al);
 406
 407     /* DC differences are figured on the point-transformed values. */
 408     temp = temp2 - entropy->last_dc_val[ci];
 409     entropy->last_dc_val[ci] = temp2;
 410
 411     /* Encode the DC coefficient difference per section G.1.2.1 */
 412     temp2 = temp;
 413     if (temp < 0) {
 414       temp = -temp;             /* temp is abs value of input */
 415       /* For a negative input, want temp2 = bitwise complement of abs(input) */
 416       /* This code assumes we are on a two's complement machine */
 417       temp2--;
 418     }
 419
 420     /* Find the number of bits needed for the magnitude of the coefficient */
 421     nbits = 0;
 422     while (temp) {
 423       nbits++;
 424       temp >>= 1;
 425     }
 426     /* Check for out-of-range coefficient values.
 427      * Since we're encoding a difference, the range limit is twice as much.
 428      */
 429     if (nbits > MAX_COEF_BITS+1)
 430       ERREXIT(cinfo, JERR_BAD_DCT_COEF);
 431
 432     /* Count/emit the Huffman-coded symbol for the number of bits */
 433     emit_symbol(entropy, compptr->dc_tbl_no, nbits);
 434
 435     /* Emit that number of bits of the value, if positive, */
 436     /* or the complement of its magnitude, if negative. */
 437     if (nbits)                  /* emit_bits rejects calls with size 0 */
 438       emit_bits(entropy, (unsigned int) temp2, nbits);
 439   }
 440
 441   cinfo->dest->next_output_byte = entropy->next_output_byte;
 442   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
 443
 444   /* Update restart-interval state too */
 445   if (cinfo->restart_interval) {
 446     if (entropy->restarts_to_go == 0) {
 447       entropy->restarts_to_go = cinfo->restart_interval;
 448       entropy->next_restart_num++;
 449       entropy->next_restart_num &= 7;
 450     }
 451     entropy->restarts_to_go--;
 452   }
 453
 454   return TRUE;
 455 }
 456
 457
 458 /*
 459  * MCU encoding for AC initial scan (either spectral selection,
 460  * or first pass of successive approximation).
 461  */
 462
 463 METHODDEF(boolean)
 464 encode_mcu_AC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 465 {
 466   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
 467   register int temp, temp2;
 468   register int nbits;
 469   register int r, k;
 470   int Se = cinfo->Se;
 471   int Al = cinfo->Al;
 472   JBLOCKROW block;
 473
 474   entropy->next_output_byte = cinfo->dest->next_output_byte;
 475   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
 476
 477   /* Emit restart marker if needed */
 478   if (cinfo->restart_interval)
 479     if (entropy->restarts_to_go == 0)
 480       emit_restart(entropy, entropy->next_restart_num);
 481
 482   /* Encode the MCU data block */
 483   block = MCU_data[0];
 484
 485   /* Encode the AC coefficients per section G.1.2.2, fig. G.3 */
 486
 487   r = 0;                        /* r = run length of zeros */
 488
 489   for (k = cinfo->Ss; k <= Se; k++) {
 490     if ((temp = (*block)[jpeg_natural_order[k]]) == 0) {
 491       r++;
 492       continue;
 493     }
 494     /* We must apply the point transform by Al.  For AC coefficients this
 495      * is an integer division with rounding towards 0.  To do this portably
 496      * in C, we shift after obtaining the absolute value; so the code is
 497      * interwoven with finding the abs value (temp) and output bits (temp2).
 498      */
 499     if (temp < 0) {
 500       temp = -temp;             /* temp is abs value of input */
 501       temp >>= Al;              /* apply the point transform */
 502       /* For a negative coef, want temp2 = bitwise complement of abs(coef) */
 503       temp2 = ~temp;
 504     } else {
 505       temp >>= Al;              /* apply the point transform */
 506       temp2 = temp;
 507     }
 508     /* Watch out for case that nonzero coef is zero after point transform */
 509     if (temp == 0) {
 510       r++;
 511       continue;
 512     }
 513
 514     /* Emit any pending EOBRUN */
 515     if (entropy->EOBRUN > 0)
 516       emit_eobrun(entropy);
 517     /* if run length > 15, must emit special run-length-16 codes (0xF0) */
 518     while (r > 15) {
 519       emit_symbol(entropy, entropy->ac_tbl_no, 0xF0);
 520       r -= 16;
 521     }
 522
 523     /* Find the number of bits needed for the magnitude of the coefficient */
 524     nbits = 1;                  /* there must be at least one 1 bit */
 525     while ((temp >>= 1))
 526       nbits++;
 527     /* Check for out-of-range coefficient values */
 528     if (nbits > MAX_COEF_BITS)
 529       ERREXIT(cinfo, JERR_BAD_DCT_COEF);
 530
 531     /* Count/emit Huffman symbol for run length / number of bits */
 532     emit_symbol(entropy, entropy->ac_tbl_no, (r << 4) + nbits);
 533
 534     /* Emit that number of bits of the value, if positive, */
 535     /* or the complement of its magnitude, if negative. */
 536     emit_bits(entropy, (unsigned int) temp2, nbits);
 537
 538     r = 0;                      /* reset zero run length */
 539   }
 540
 541   if (r > 0) {                  /* If there are trailing zeroes, */
 542     entropy->EOBRUN++;          /* count an EOB */
 543     if (entropy->EOBRUN == 0x7FFF)
 544       emit_eobrun(entropy);     /* force it out to avoid overflow */
 545   }
 546
 547   cinfo->dest->next_output_byte = entropy->next_output_byte;
 548   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
 549
 550   /* Update restart-interval state too */
 551   if (cinfo->restart_interval) {
 552     if (entropy->restarts_to_go == 0) {
 553       entropy->restarts_to_go = cinfo->restart_interval;
 554       entropy->next_restart_num++;
 555       entropy->next_restart_num &= 7;
 556     }
 557     entropy->restarts_to_go--;
 558   }
 559
 560   return TRUE;
 561 }
 562
 563
 564 /*
 565  * MCU encoding for DC successive approximation refinement scan.
 566  * Note: we assume such scans can be multi-component, although the spec
 567  * is not very clear on the point.
 568  */
 569
 570 METHODDEF(boolean)
 571 encode_mcu_DC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 572 {
 573   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
 574   register int temp;
 575   int blkn;
 576   int Al = cinfo->Al;
 577   JBLOCKROW block;
 578
 579   entropy->next_output_byte = cinfo->dest->next_output_byte;
 580   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
 581
 582   /* Emit restart marker if needed */
 583   if (cinfo->restart_interval)
 584     if (entropy->restarts_to_go == 0)
 585       emit_restart(entropy, entropy->next_restart_num);
 586
 587   /* Encode the MCU data blocks */
 588   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
 589     block = MCU_data[blkn];
 590
 591     /* We simply emit the Al'th bit of the DC coefficient value. */
 592     temp = (*block)[0];
 593     emit_bits(entropy, (unsigned int) (temp >> Al), 1);
 594   }
 595
 596   cinfo->dest->next_output_byte = entropy->next_output_byte;
 597   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
 598
 599   /* Update restart-interval state too */
 600   if (cinfo->restart_interval) {
 601     if (entropy->restarts_to_go == 0) {
 602       entropy->restarts_to_go = cinfo->restart_interval;
 603       entropy->next_restart_num++;
 604       entropy->next_restart_num &= 7;
 605     }
 606     entropy->restarts_to_go--;
 607   }
 608
 609   return TRUE;
 610 }
 611
 612
 613 /*
 614  * MCU encoding for AC successive approximation refinement scan.
 615  */
 616
 617 METHODDEF(boolean)
 618 encode_mcu_AC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 619 {
 620   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
 621   register int temp;
 622   register int r, k;
 623   int EOB;
 624   char *BR_buffer;
 625   unsigned int BR;
 626   int Se = cinfo->Se;
 627   int Al = cinfo->Al;
 628   JBLOCKROW block;
 629   int absvalues[DCTSIZE2];
 630
 631   entropy->next_output_byte = cinfo->dest->next_output_byte;
 632   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
 633
 634   /* Emit restart marker if needed */
 635   if (cinfo->restart_interval)
 636     if (entropy->restarts_to_go == 0)
 637       emit_restart(entropy, entropy->next_restart_num);
 638
 639   /* Encode the MCU data block */
 640   block = MCU_data[0];
 641
 642   /* It is convenient to make a pre-pass to determine the transformed
 643    * coefficients' absolute values and the EOB position.
 644    */
 645   EOB = 0;
 646   for (k = cinfo->Ss; k <= Se; k++) {
 647     temp = (*block)[jpeg_natural_order[k]];
 648     /* We must apply the point transform by Al.  For AC coefficients this
 649      * is an integer division with rounding towards 0.  To do this portably
 650      * in C, we shift after obtaining the absolute value.
 651      */
 652     if (temp < 0)
 653       temp = -temp;             /* temp is abs value of input */
 654     temp >>= Al;                /* apply the point transform */
 655     absvalues[k] = temp;        /* save abs value for main pass */
 656     if (temp == 1)
 657       EOB = k;                  /* EOB = index of last newly-nonzero coef */
 658   }
 659
 660   /* Encode the AC coefficients per section G.1.2.3, fig. G.7 */
 661
 662   r = 0;                        /* r = run length of zeros */
 663   BR = 0;                       /* BR = count of buffered bits added now */
 664   BR_buffer = entropy->bit_buffer + entropy->BE; /* Append bits to buffer */
 665
 666   for (k = cinfo->Ss; k <= Se; k++) {
 667     if ((temp = absvalues[k]) == 0) {
 668       r++;
 669       continue;
 670     }
 671
 672     /* Emit any required ZRLs, but not if they can be folded into EOB */
 673     while (r > 15 && k <= EOB) {
 674       /* emit any pending EOBRUN and the BE correction bits */
 675       emit_eobrun(entropy);
 676       /* Emit ZRL */
 677       emit_symbol(entropy, entropy->ac_tbl_no, 0xF0);
 678       r -= 16;
 679       /* Emit buffered correction bits that must be associated with ZRL */
 680       emit_buffered_bits(entropy, BR_buffer, BR);
 681       BR_buffer = entropy->bit_buffer; /* BE bits are gone now */
 682       BR = 0;
 683     }
 684
 685     /* If the coef was previously nonzero, it only needs a correction bit.
 686      * NOTE: a straight translation of the spec's figure G.7 would suggest
 687      * that we also need to test r > 15.  But if r > 15, we can only get here
 688      * if k > EOB, which implies that this coefficient is not 1.
 689      */
 690     if (temp > 1) {
 691       /* The correction bit is the next bit of the absolute value. */
 692       BR_buffer[BR++] = (char) (temp & 1);
 693       continue;
 694     }
 695
 696     /* Emit any pending EOBRUN and the BE correction bits */
 697     emit_eobrun(entropy);
 698
 699     /* Count/emit Huffman symbol for run length / number of bits */
 700     emit_symbol(entropy, entropy->ac_tbl_no, (r << 4) + 1);
 701
 702     /* Emit output bit for newly-nonzero coef */
 703     temp = ((*block)[jpeg_natural_order[k]] < 0) ? 0 : 1;
 704     emit_bits(entropy, (unsigned int) temp, 1);
 705
 706     /* Emit buffered correction bits that must be associated with this code */
 707     emit_buffered_bits(entropy, BR_buffer, BR);
 708     BR_buffer = entropy->bit_buffer; /* BE bits are gone now */
 709     BR = 0;
 710     r = 0;                      /* reset zero run length */
 711   }
 712
 713   if (r > 0 || BR > 0) {        /* If there are trailing zeroes, */
 714     entropy->EOBRUN++;          /* count an EOB */
 715     entropy->BE += BR;          /* concat my correction bits to older ones */
 716     /* We force out the EOB if we risk either:
 717      * 1. overflow of the EOB counter;
 718      * 2. overflow of the correction bit buffer during the next MCU.
 719      */
 720     if (entropy->EOBRUN == 0x7FFF || entropy->BE > (MAX_CORR_BITS-DCTSIZE2+1))
 721       emit_eobrun(entropy);
 722   }
 723
 724   cinfo->dest->next_output_byte = entropy->next_output_byte;
 725   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
 726
 727   /* Update restart-interval state too */
 728   if (cinfo->restart_interval) {
 729     if (entropy->restarts_to_go == 0) {
 730       entropy->restarts_to_go = cinfo->restart_interval;
 731       entropy->next_restart_num++;
 732       entropy->next_restart_num &= 7;
 733     }
 734     entropy->restarts_to_go--;
 735   }
 736
 737   return TRUE;
 738 }
 739
 740
 741 /*
 742  * Finish up at the end of a Huffman-compressed progressive scan.
 743  */
 744
 745 METHODDEF(void)
 746 finish_pass_phuff (j_compress_ptr cinfo)
 747 {
 748   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
 749
 750   entropy->next_output_byte = cinfo->dest->next_output_byte;
 751   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
 752
 753   /* Flush out any buffered data */
 754   emit_eobrun(entropy);
 755   flush_bits(entropy);
 756
 757   cinfo->dest->next_output_byte = entropy->next_output_byte;
 758   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
 759 }
 760
 761
 762 /*
 763  * Finish up a statistics-gathering pass and create the new Huffman tables.
 764  */
 765
 766 METHODDEF(void)
 767 finish_pass_gather_phuff (j_compress_ptr cinfo)
 768 {
 769   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
 770   boolean is_DC_band;
 771   int ci, tbl;
 772   jpeg_component_info * compptr;
 773   JHUFF_TBL **htblptr;
 774   boolean did[NUM_HUFF_TBLS];
 775
 776   /* Flush out buffered data (all we care about is counting the EOB symbol) */
 777   emit_eobrun(entropy);
 778
 779   is_DC_band = (cinfo->Ss == 0);
 780
 781   /* It's important not to apply jpeg_gen_optimal_table more than once
 782    * per table, because it clobbers the input frequency counts!
 783    */
 784   MEMZERO(did, SIZEOF(did));
 785
 786   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
 787     compptr = cinfo->cur_comp_info[ci];
 788     if (is_DC_band) {
 789       if (cinfo->Ah != 0)       /* DC refinement needs no table */
 790         continue;
 791       tbl = compptr->dc_tbl_no;
 792     } else {
 793       tbl = compptr->ac_tbl_no;
 794     }
 795     if (! did[tbl]) {
 796       if (is_DC_band)
 797         htblptr = & cinfo->dc_huff_tbl_ptrs[tbl];
 798       else
 799         htblptr = & cinfo->ac_huff_tbl_ptrs[tbl];
 800       if (*htblptr == NULL)
 801         *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
 802       jpeg_gen_optimal_table(cinfo, *htblptr, entropy->count_ptrs[tbl]);
 803       did[tbl] = TRUE;
 804     }
 805   }
 806 }
 807
 808
 809 /*
 810  * Module initialization routine for progressive Huffman entropy encoding.
 811  */
 812
 813 GLOBAL(void)
 814 jinit_phuff_encoder (j_compress_ptr cinfo)
 815 {
 816   phuff_entropy_ptr entropy;
 817   int i;
 818
 819   entropy = (phuff_entropy_ptr)
 820     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
 821                                 SIZEOF(phuff_entropy_encoder));
 822   cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
 823   entropy->pub.start_pass = start_pass_phuff;
 824
 825   /* Mark tables unallocated */
 826   for (i = 0; i < NUM_HUFF_TBLS; i++) {
 827     entropy->derived_tbls[i] = NULL;
 828     entropy->count_ptrs[i] = NULL;
 829   }
 830   entropy->bit_buffer = NULL;   /* needed only in AC refinement scan */
 831 }
 832
 833 #endif /* C_PROGRESSIVE_SUPPORTED */