neo/renderer/jpeg-6/jcphuff.c

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