src/gdcmjpeg/jcphuff.c

   1 /*
   2  * jcphuff.c
   3  *
   4  * Copyright (C) 1995-1998, 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 "jlossy.h"    /* Private declarations for lossy codec */
  19 #include "jchuff.h"    /* Declarations shared with jc*huff.c */
  20
  21 #ifdef C_PROGRESSIVE_SUPPORTED
  22
  23 /* Expanded entropy encoder object for progressive Huffman encoding. */
  24
  25 typedef struct {
  26   /* Mode flag: TRUE for optimization, FALSE for actual data output */
  27   boolean gather_statistics;
  28
  29   /* Bit-level coding status.
  30    * next_output_byte/free_in_buffer are local copies of cinfo->dest fields.
  31    */
  32   JOCTET * next_output_byte;  /* => next byte to write in buffer */
  33   size_t free_in_buffer;  /* # of byte spaces remaining in buffer */
  34   INT32 put_buffer;    /* current bit-accumulation buffer */
  35   int put_bits;      /* # of bits now in it */
  36   j_compress_ptr cinfo;    /* link to cinfo (needed for dump_buffer) */
  37
  38   /* Coding status for DC components */
  39   int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
  40
  41   /* Coding status for AC components */
  42   int ac_tbl_no;    /* the table number of the single component */
  43   unsigned int EOBRUN;    /* run length of EOBs */
  44   unsigned int BE;    /* # of buffered correction bits before MCU */
  45   char * bit_buffer;    /* buffer for correction bits (1 per char) */
  46   /* packing correction bits tightly would save some space but cost time... */
  47
  48   unsigned int restarts_to_go;  /* MCUs left in this restart interval */
  49   int next_restart_num;    /* next restart number to write (0-7) */
  50
  51   /* Pointers to derived tables (these workspaces have image lifespan).
  52    * Since any one scan codes only DC or only AC, we only need one set
  53    * of tables, not one for DC and one for AC.
  54    */
  55   c_derived_tbl * derived_tbls[NUM_HUFF_TBLS];
  56
  57   /* Statistics tables for optimization; again, one set is enough */
  58   long * count_ptrs[NUM_HUFF_TBLS];
  59 } phuff_entropy_encoder;
  60
  61 typedef phuff_entropy_encoder * phuff_entropy_ptr;
  62
  63 /* MAX_CORR_BITS is the number of bits the AC refinement correction-bit
  64  * buffer can hold.  Larger sizes may slightly improve compression, but
  65  * 1000 is already well into the realm of overkill.
  66  * The minimum safe size is 64 bits.
  67  */
  68
  69 #define MAX_CORR_BITS  1000  /* Max # of correction bits I can buffer */
  70
  71 /* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than INT32.
  72  * We assume that int right shift is unsigned if INT32 right shift is,
  73  * which should be safe.
  74  */
  75
  76 #ifdef RIGHT_SHIFT_IS_UNSIGNED
  77 #define ISHIFT_TEMPS  int ishift_temp;
  78 #define IRIGHT_SHIFT(x,shft)  \
  79   ((ishift_temp = (x)) < 0 ? \
  80    (ishift_temp >> (shft)) | ((~0) << (16-(shft))) : \
  81    (ishift_temp >> (shft)))
  82 #else
  83 #define ISHIFT_TEMPS
  84 #define IRIGHT_SHIFT(x,shft)  ((x) >> (shft))
  85 #endif
  86
  87 /* Forward declarations */
  88 METHODDEF(boolean) encode_mcu_DC_first JPP((j_compress_ptr cinfo,
  89               JBLOCKROW *MCU_data));
  90 METHODDEF(boolean) encode_mcu_AC_first JPP((j_compress_ptr cinfo,
  91               JBLOCKROW *MCU_data));
  92 METHODDEF(boolean) encode_mcu_DC_refine JPP((j_compress_ptr cinfo,
  93                JBLOCKROW *MCU_data));
  94 METHODDEF(boolean) encode_mcu_AC_refine JPP((j_compress_ptr cinfo,
  95                JBLOCKROW *MCU_data));
  96 METHODDEF(void) finish_pass_phuff JPP((j_compress_ptr cinfo));
  97 METHODDEF(void) finish_pass_gather_phuff JPP((j_compress_ptr cinfo));
  98
  99
 100 /*
 101  * Initialize for a Huffman-compressed scan using progressive JPEG.
 102  */
 103
 104 METHODDEF(void)
 105 start_pass_phuff (j_compress_ptr cinfo, boolean gather_statistics)
 106 {
 107   j_lossy_c_ptr lossyc = (j_lossy_c_ptr) cinfo->codec;
 108   phuff_entropy_ptr entropy = (phuff_entropy_ptr) lossyc->entropy_private;
 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       lossyc->entropy_encode_mcu = encode_mcu_DC_first;
 124     else
 125       lossyc->entropy_encode_mcu = encode_mcu_AC_first;
 126   } else {
 127     if (is_DC_band)
 128       lossyc->entropy_encode_mcu = encode_mcu_DC_refine;
 129     else {
 130       lossyc->entropy_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     lossyc->pub.entropy_finish_pass = finish_pass_gather_phuff;
 140   else
 141     lossyc->pub.entropy_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   j_lossy_c_ptr lossyc = (j_lossy_c_ptr) cinfo->codec;
 380   phuff_entropy_ptr entropy = (phuff_entropy_ptr) lossyc->entropy_private;
 381   register int temp, temp2;
 382   register int nbits;
 383   int blkn, ci;
 384   int Al = cinfo->Al;
 385   JBLOCKROW block;
 386   jpeg_component_info * compptr;
 387   ISHIFT_TEMPS
 388
 389   entropy->next_output_byte = cinfo->dest->next_output_byte;
 390   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
 391
 392   /* Emit restart marker if needed */
 393   if (cinfo->restart_interval)
 394     if (entropy->restarts_to_go == 0)
 395       emit_restart(entropy, entropy->next_restart_num);
 396
 397   /* Encode the MCU data blocks */
 398   for (blkn = 0; blkn < cinfo->data_units_in_MCU; blkn++) {
 399     block = MCU_data[blkn];
 400     ci = cinfo->MCU_membership[blkn];
 401     compptr = cinfo->cur_comp_info[ci];
 402
 403     /* Compute the DC value after the required point transform by Al.
 404      * This is simply an arithmetic right shift.
 405      */
 406     temp2 = IRIGHT_SHIFT((int) ((*block)[0]), Al);
 407
 408     /* DC differences are figured on the point-transformed values. */
 409     temp = temp2 - entropy->last_dc_val[ci];
 410     entropy->last_dc_val[ci] = temp2;
 411
 412     /* Encode the DC coefficient difference per section G.1.2.1 */
 413     temp2 = temp;
 414     if (temp < 0) {
 415       temp = -temp;    /* temp is abs value of input */
 416       /* For a negative input, want temp2 = bitwise complement of abs(input) */
 417       /* This code assumes we are on a two's complement machine */
 418       temp2--;
 419     }
 420
 421     /* Find the number of bits needed for the magnitude of the coefficient */
 422     nbits = 0;
 423     while (temp) {
 424       nbits++;
 425       temp >>= 1;
 426     }
 427     /* Check for out-of-range coefficient values.
 428      * Since we're encoding a difference, the range limit is twice as much.
 429      */
 430     if (nbits > MAX_COEF_BITS+1)
 431       ERREXIT(cinfo, JERR_BAD_DCT_COEF);
 432
 433     /* Count/emit the Huffman-coded symbol for the number of bits */
 434     emit_symbol(entropy, compptr->dc_tbl_no, nbits);
 435
 436     /* Emit that number of bits of the value, if positive, */
 437     /* or the complement of its magnitude, if negative. */
 438     if (nbits)      /* emit_bits rejects calls with size 0 */
 439       emit_bits(entropy, (unsigned int) temp2, nbits);
 440   }
 441
 442   cinfo->dest->next_output_byte = entropy->next_output_byte;
 443   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
 444
 445   /* Update restart-interval state too */
 446   if (cinfo->restart_interval) {
 447     if (entropy->restarts_to_go == 0) {
 448       entropy->restarts_to_go = cinfo->restart_interval;
 449       entropy->next_restart_num++;
 450       entropy->next_restart_num &= 7;
 451     }
 452     entropy->restarts_to_go--;
 453   }
 454
 455   return TRUE;
 456 }
 457
 458
 459 /*
 460  * MCU encoding for AC initial scan (either spectral selection,
 461  * or first pass of successive approximation).
 462  */
 463
 464 METHODDEF(boolean)
 465 encode_mcu_AC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 466 {
 467   j_lossy_c_ptr lossyc = (j_lossy_c_ptr) cinfo->codec;
 468   phuff_entropy_ptr entropy = (phuff_entropy_ptr) lossyc->entropy_private;
 469   register int temp, temp2;
 470   register int nbits;
 471   register int r, k;
 472   int Se = cinfo->Se;
 473   int Al = cinfo->Al;
 474   JBLOCKROW block;
 475
 476   entropy->next_output_byte = cinfo->dest->next_output_byte;
 477   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
 478
 479   /* Emit restart marker if needed */
 480   if (cinfo->restart_interval)
 481     if (entropy->restarts_to_go == 0)
 482       emit_restart(entropy, entropy->next_restart_num);
 483
 484   /* Encode the MCU data block */
 485   block = MCU_data[0];
 486
 487   /* Encode the AC coefficients per section G.1.2.2, fig. G.3 */
 488
 489   r = 0;      /* r = run length of zeros */
 490
 491   for (k = cinfo->Ss; k <= Se; k++) {
 492     if ((temp = (*block)[jpeg_natural_order[k]]) == 0) {
 493       r++;
 494       continue;
 495     }
 496     /* We must apply the point transform by Al.  For AC coefficients this
 497      * is an integer division with rounding towards 0.  To do this portably
 498      * in C, we shift after obtaining the absolute value; so the code is
 499      * interwoven with finding the abs value (temp) and output bits (temp2).
 500      */
 501     if (temp < 0) {
 502       temp = -temp;    /* temp is abs value of input */
 503       temp >>= Al;    /* apply the point transform */
 504       /* For a negative coef, want temp2 = bitwise complement of abs(coef) */
 505       temp2 = ~temp;
 506     } else {
 507       temp >>= Al;    /* apply the point transform */
 508       temp2 = temp;
 509     }
 510     /* Watch out for case that nonzero coef is zero after point transform */
 511     if (temp == 0) {
 512       r++;
 513       continue;
 514     }
 515
 516     /* Emit any pending EOBRUN */
 517     if (entropy->EOBRUN > 0)
 518       emit_eobrun(entropy);
 519     /* if run length > 15, must emit special run-length-16 codes (0xF0) */
 520     while (r > 15) {
 521       emit_symbol(entropy, entropy->ac_tbl_no, 0xF0);
 522       r -= 16;
 523     }
 524
 525     /* Find the number of bits needed for the magnitude of the coefficient */
 526     nbits = 1;      /* there must be at least one 1 bit */
 527     while ((temp >>= 1))
 528       nbits++;
 529     /* Check for out-of-range coefficient values */
 530     if (nbits > MAX_COEF_BITS)
 531       ERREXIT(cinfo, JERR_BAD_DCT_COEF);
 532
 533     /* Count/emit Huffman symbol for run length / number of bits */
 534     emit_symbol(entropy, entropy->ac_tbl_no, (r << 4) + nbits);
 535
 536     /* Emit that number of bits of the value, if positive, */
 537     /* or the complement of its magnitude, if negative. */
 538     emit_bits(entropy, (unsigned int) temp2, nbits);
 539
 540     r = 0;      /* reset zero run length */
 541   }
 542
 543   if (r > 0) {      /* If there are trailing zeroes, */
 544     entropy->EOBRUN++;    /* count an EOB */
 545     if (entropy->EOBRUN == 0x7FFF)
 546       emit_eobrun(entropy);  /* force it out to avoid overflow */
 547   }
 548
 549   cinfo->dest->next_output_byte = entropy->next_output_byte;
 550   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
 551
 552   /* Update restart-interval state too */
 553   if (cinfo->restart_interval) {
 554     if (entropy->restarts_to_go == 0) {
 555       entropy->restarts_to_go = cinfo->restart_interval;
 556       entropy->next_restart_num++;
 557       entropy->next_restart_num &= 7;
 558     }
 559     entropy->restarts_to_go--;
 560   }
 561
 562   return TRUE;
 563 }
 564
 565
 566 /*
 567  * MCU encoding for DC successive approximation refinement scan.
 568  * Note: we assume such scans can be multi-component, although the spec
 569  * is not very clear on the point.
 570  */
 571
 572 METHODDEF(boolean)
 573 encode_mcu_DC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 574 {
 575   j_lossy_c_ptr lossyc = (j_lossy_c_ptr) cinfo->codec;
 576   phuff_entropy_ptr entropy = (phuff_entropy_ptr) lossyc->entropy_private;
 577   register int temp;
 578   int blkn;
 579   int Al = cinfo->Al;
 580   JBLOCKROW block;
 581
 582   entropy->next_output_byte = cinfo->dest->next_output_byte;
 583   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
 584
 585   /* Emit restart marker if needed */
 586   if (cinfo->restart_interval)
 587     if (entropy->restarts_to_go == 0)
 588       emit_restart(entropy, entropy->next_restart_num);
 589
 590   /* Encode the MCU data blocks */
 591   for (blkn = 0; blkn < cinfo->data_units_in_MCU; blkn++) {
 592     block = MCU_data[blkn];
 593
 594     /* We simply emit the Al'th bit of the DC coefficient value. */
 595     temp = (*block)[0];
 596     emit_bits(entropy, (unsigned int) (temp >> Al), 1);
 597   }
 598
 599   cinfo->dest->next_output_byte = entropy->next_output_byte;
 600   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
 601
 602   /* Update restart-interval state too */
 603   if (cinfo->restart_interval) {
 604     if (entropy->restarts_to_go == 0) {
 605       entropy->restarts_to_go = cinfo->restart_interval;
 606       entropy->next_restart_num++;
 607       entropy->next_restart_num &= 7;
 608     }
 609     entropy->restarts_to_go--;
 610   }
 611
 612   return TRUE;
 613 }
 614
 615
 616 /*
 617  * MCU encoding for AC successive approximation refinement scan.
 618  */
 619
 620 METHODDEF(boolean)
 621 encode_mcu_AC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 622 {
 623   j_lossy_c_ptr lossyc = (j_lossy_c_ptr) cinfo->codec;
 624   phuff_entropy_ptr entropy = (phuff_entropy_ptr) lossyc->entropy_private;
 625   register int temp;
 626   register int r, k;
 627   int EOB;
 628   char *BR_buffer;
 629   unsigned int BR;
 630   int Se = cinfo->Se;
 631   int Al = cinfo->Al;
 632   JBLOCKROW block;
 633   int absvalues[DCTSIZE2];
 634
 635   entropy->next_output_byte = cinfo->dest->next_output_byte;
 636   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
 637
 638   /* Emit restart marker if needed */
 639   if (cinfo->restart_interval)
 640     if (entropy->restarts_to_go == 0)
 641       emit_restart(entropy, entropy->next_restart_num);
 642
 643   /* Encode the MCU data block */
 644   block = MCU_data[0];
 645
 646   /* It is convenient to make a pre-pass to determine the transformed
 647    * coefficients' absolute values and the EOB position.
 648    */
 649   EOB = 0;
 650   for (k = cinfo->Ss; k <= Se; k++) {
 651     temp = (*block)[jpeg_natural_order[k]];
 652     /* We must apply the point transform by Al.  For AC coefficients this
 653      * is an integer division with rounding towards 0.  To do this portably
 654      * in C, we shift after obtaining the absolute value.
 655      */
 656     if (temp < 0)
 657       temp = -temp;    /* temp is abs value of input */
 658     temp >>= Al;    /* apply the point transform */
 659     absvalues[k] = temp;  /* save abs value for main pass */
 660     if (temp == 1)
 661       EOB = k;      /* EOB = index of last newly-nonzero coef */
 662   }
 663
 664   /* Encode the AC coefficients per section G.1.2.3, fig. G.7 */
 665
 666   r = 0;      /* r = run length of zeros */
 667   BR = 0;      /* BR = count of buffered bits added now */
 668   BR_buffer = entropy->bit_buffer + entropy->BE; /* Append bits to buffer */
 669
 670   for (k = cinfo->Ss; k <= Se; k++) {
 671     if ((temp = absvalues[k]) == 0) {
 672       r++;
 673       continue;
 674     }
 675
 676     /* Emit any required ZRLs, but not if they can be folded into EOB */
 677     while (r > 15 && k <= EOB) {
 678       /* emit any pending EOBRUN and the BE correction bits */
 679       emit_eobrun(entropy);
 680       /* Emit ZRL */
 681       emit_symbol(entropy, entropy->ac_tbl_no, 0xF0);
 682       r -= 16;
 683       /* Emit buffered correction bits that must be associated with ZRL */
 684       emit_buffered_bits(entropy, BR_buffer, BR);
 685       BR_buffer = entropy->bit_buffer; /* BE bits are gone now */
 686       BR = 0;
 687     }
 688
 689     /* If the coef was previously nonzero, it only needs a correction bit.
 690      * NOTE: a straight translation of the spec's figure G.7 would suggest
 691      * that we also need to test r > 15.  But if r > 15, we can only get here
 692      * if k > EOB, which implies that this coefficient is not 1.
 693      */
 694     if (temp > 1) {
 695       /* The correction bit is the next bit of the absolute value. */
 696       BR_buffer[BR++] = (char) (temp & 1);
 697       continue;
 698     }
 699
 700     /* Emit any pending EOBRUN and the BE correction bits */
 701     emit_eobrun(entropy);
 702
 703     /* Count/emit Huffman symbol for run length / number of bits */
 704     emit_symbol(entropy, entropy->ac_tbl_no, (r << 4) + 1);
 705
 706     /* Emit output bit for newly-nonzero coef */
 707     temp = ((*block)[jpeg_natural_order[k]] < 0) ? 0 : 1;
 708     emit_bits(entropy, (unsigned int) temp, 1);
 709
 710     /* Emit buffered correction bits that must be associated with this code */
 711     emit_buffered_bits(entropy, BR_buffer, BR);
 712     BR_buffer = entropy->bit_buffer; /* BE bits are gone now */
 713     BR = 0;
 714     r = 0;      /* reset zero run length */
 715   }
 716
 717   if (r > 0 || BR > 0) {  /* If there are trailing zeroes, */
 718     entropy->EOBRUN++;    /* count an EOB */
 719     entropy->BE += BR;    /* concat my correction bits to older ones */
 720     /* We force out the EOB if we risk either:
 721      * 1. overflow of the EOB counter;
 722      * 2. overflow of the correction bit buffer during the next MCU.
 723      */
 724     if (entropy->EOBRUN == 0x7FFF || entropy->BE > (MAX_CORR_BITS-DCTSIZE2+1))
 725       emit_eobrun(entropy);
 726   }
 727
 728   cinfo->dest->next_output_byte = entropy->next_output_byte;
 729   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
 730
 731   /* Update restart-interval state too */
 732   if (cinfo->restart_interval) {
 733     if (entropy->restarts_to_go == 0) {
 734       entropy->restarts_to_go = cinfo->restart_interval;
 735       entropy->next_restart_num++;
 736       entropy->next_restart_num &= 7;
 737     }
 738     entropy->restarts_to_go--;
 739   }
 740
 741   return TRUE;
 742 }
 743
 744
 745 /*
 746  * Finish up at the end of a Huffman-compressed progressive scan.
 747  */
 748
 749 METHODDEF(void)
 750 finish_pass_phuff (j_compress_ptr cinfo)
 751 {
 752   j_lossy_c_ptr lossyc = (j_lossy_c_ptr) cinfo->codec;
 753   phuff_entropy_ptr entropy = (phuff_entropy_ptr) lossyc->entropy_private;
 754
 755   entropy->next_output_byte = cinfo->dest->next_output_byte;
 756   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
 757
 758   /* Flush out any buffered data */
 759   emit_eobrun(entropy);
 760   flush_bits(entropy);
 761
 762   cinfo->dest->next_output_byte = entropy->next_output_byte;
 763   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
 764 }
 765
 766
 767 /*
 768  * Finish up a statistics-gathering pass and create the new Huffman tables.
 769  */
 770
 771 METHODDEF(void)
 772 finish_pass_gather_phuff (j_compress_ptr cinfo)
 773 {
 774   j_lossy_c_ptr lossyc = (j_lossy_c_ptr) cinfo->codec;
 775   phuff_entropy_ptr entropy = (phuff_entropy_ptr) lossyc->entropy_private;
 776   boolean is_DC_band;
 777   int ci, tbl;
 778   jpeg_component_info * compptr;
 779   JHUFF_TBL **htblptr;
 780   boolean did[NUM_HUFF_TBLS];
 781
 782   /* Flush out buffered data (all we care about is counting the EOB symbol) */
 783   emit_eobrun(entropy);
 784
 785   is_DC_band = (cinfo->Ss == 0);
 786
 787   /* It's important not to apply jpeg_gen_optimal_table more than once
 788    * per table, because it clobbers the input frequency counts!
 789    */
 790   MEMZERO(did, SIZEOF(did));
 791
 792   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
 793     compptr = cinfo->cur_comp_info[ci];
 794     if (is_DC_band) {
 795       if (cinfo->Ah != 0)  /* DC refinement needs no table */
 796   continue;
 797       tbl = compptr->dc_tbl_no;
 798     } else {
 799       tbl = compptr->ac_tbl_no;
 800     }
 801     if (! did[tbl]) {
 802       if (is_DC_band)
 803         htblptr = & cinfo->dc_huff_tbl_ptrs[tbl];
 804       else
 805         htblptr = & cinfo->ac_huff_tbl_ptrs[tbl];
 806       if (*htblptr == NULL)
 807         *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
 808       jpeg_gen_optimal_table(cinfo, *htblptr, entropy->count_ptrs[tbl]);
 809       did[tbl] = TRUE;
 810     }
 811   }
 812 }
 813
 814
 815 METHODDEF(boolean)
 816 need_optimization_pass (j_compress_ptr cinfo)
 817 {
 818   return (cinfo->Ss != 0 || cinfo->Ah == 0);
 819 }
 820
 821
 822 /*
 823  * Module initialization routine for progressive Huffman entropy encoding.
 824  */
 825
 826 GLOBAL(void)
 827 jinit_phuff_encoder (j_compress_ptr cinfo)
 828 {
 829   j_lossy_c_ptr lossyc = (j_lossy_c_ptr) cinfo->codec;
 830   phuff_entropy_ptr entropy;
 831   int i;
 832
 833   entropy = (phuff_entropy_ptr)
 834     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
 835         SIZEOF(phuff_entropy_encoder));
 836   lossyc->entropy_private = (struct jpeg_entropy_encoder *) entropy;
 837   lossyc->pub.entropy_start_pass = start_pass_phuff;
 838   lossyc->pub.need_optimization_pass = need_optimization_pass;
 839
 840   /* Mark tables unallocated */
 841   for (i = 0; i < NUM_HUFF_TBLS; i++) {
 842     entropy->derived_tbls[i] = NULL;
 843     entropy->count_ptrs[i] = NULL;
 844   }
 845   entropy->bit_buffer = NULL;  /* needed only in AC refinement scan */
 846 }
 847
 848 #endif /* C_PROGRESSIVE_SUPPORTED */