jchuff.c

   1 /*
   2  * jchuff.c
   3  *
   4  * This file was part of the Independent JPEG Group's software:
   5  * Copyright (C) 1991-1997, Thomas G. Lane.
   6  * libjpeg-turbo Modifications:
   7  * Copyright (C) 2009-2011, D. R. Commander.
   8  * For conditions of distribution and use, see the accompanying README file.
   9  *
  10  * This file contains Huffman entropy encoding routines.
  11  *
  12  * Much of the complexity here has to do with supporting output suspension.
  13  * If the data destination module demands suspension, we want to be able to
  14  * back up to the start of the current MCU.  To do this, we copy state
  15  * variables into local working storage, and update them back to the
  16  * permanent JPEG objects only upon successful completion of an MCU.
  17  */
  18
  19 #define JPEG_INTERNALS
  20 #include "jinclude.h"
  21 #include "jpeglib.h"
  22 #include "jchuff.h"             /* Declarations shared with jcphuff.c */
  23 #include <limits.h>
  24
  25 static unsigned char jpeg_nbits_table[65536];
  26 static int jpeg_nbits_table_init = 0;
  27
  28 #ifndef min
  29  #define min(a,b) ((a)<(b)?(a):(b))
  30 #endif
  31
  32
  33 /* Expanded entropy encoder object for Huffman encoding.
  34  *
  35  * The savable_state subrecord contains fields that change within an MCU,
  36  * but must not be updated permanently until we complete the MCU.
  37  */
  38
  39 typedef struct {
  40   size_t put_buffer;            /* current bit-accumulation buffer */
  41   int put_bits;                 /* # of bits now in it */
  42   int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
  43 } savable_state;
  44
  45 /* This macro is to work around compilers with missing or broken
  46  * structure assignment.  You'll need to fix this code if you have
  47  * such a compiler and you change MAX_COMPS_IN_SCAN.
  48  */
  49
  50 #ifndef NO_STRUCT_ASSIGN
  51 #define ASSIGN_STATE(dest,src)  ((dest) = (src))
  52 #else
  53 #if MAX_COMPS_IN_SCAN == 4
  54 #define ASSIGN_STATE(dest,src)  \
  55         ((dest).put_buffer = (src).put_buffer, \
  56          (dest).put_bits = (src).put_bits, \
  57          (dest).last_dc_val[0] = (src).last_dc_val[0], \
  58          (dest).last_dc_val[1] = (src).last_dc_val[1], \
  59          (dest).last_dc_val[2] = (src).last_dc_val[2], \
  60          (dest).last_dc_val[3] = (src).last_dc_val[3])
  61 #endif
  62 #endif
  63
  64
  65 typedef struct {
  66   struct jpeg_entropy_encoder pub; /* public fields */
  67
  68   savable_state saved;          /* Bit buffer & DC state at start of MCU */
  69
  70   /* These fields are NOT loaded into local working state. */
  71   unsigned int restarts_to_go;  /* MCUs left in this restart interval */
  72   int next_restart_num;         /* next restart number to write (0-7) */
  73
  74   /* Pointers to derived tables (these workspaces have image lifespan) */
  75   c_derived_tbl * dc_derived_tbls[NUM_HUFF_TBLS];
  76   c_derived_tbl * ac_derived_tbls[NUM_HUFF_TBLS];
  77
  78 #ifdef ENTROPY_OPT_SUPPORTED    /* Statistics tables for optimization */
  79   long * dc_count_ptrs[NUM_HUFF_TBLS];
  80   long * ac_count_ptrs[NUM_HUFF_TBLS];
  81 #endif
  82 } huff_entropy_encoder;
  83
  84 typedef huff_entropy_encoder * huff_entropy_ptr;
  85
  86 /* Working state while writing an MCU.
  87  * This struct contains all the fields that are needed by subroutines.
  88  */
  89
  90 typedef struct {
  91   JOCTET * next_output_byte;    /* => next byte to write in buffer */
  92   size_t free_in_buffer;        /* # of byte spaces remaining in buffer */
  93   savable_state cur;            /* Current bit buffer & DC state */
  94   j_compress_ptr cinfo;         /* dump_buffer needs access to this */
  95 } working_state;
  96
  97
  98 /* Forward declarations */
  99 METHODDEF(boolean) encode_mcu_huff JPP((j_compress_ptr cinfo,
 100                                         JBLOCKROW *MCU_data));
 101 METHODDEF(void) finish_pass_huff JPP((j_compress_ptr cinfo));
 102 #ifdef ENTROPY_OPT_SUPPORTED
 103 METHODDEF(boolean) encode_mcu_gather JPP((j_compress_ptr cinfo,
 104                                           JBLOCKROW *MCU_data));
 105 METHODDEF(void) finish_pass_gather JPP((j_compress_ptr cinfo));
 106 #endif
 107
 108
 109 /*
 110  * Initialize for a Huffman-compressed scan.
 111  * If gather_statistics is TRUE, we do not output anything during the scan,
 112  * just count the Huffman symbols used and generate Huffman code tables.
 113  */
 114
 115 METHODDEF(void)
 116 start_pass_huff (j_compress_ptr cinfo, boolean gather_statistics)
 117 {
 118   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
 119   int ci, dctbl, actbl;
 120   jpeg_component_info * compptr;
 121
 122   if (gather_statistics) {
 123 #ifdef ENTROPY_OPT_SUPPORTED
 124     entropy->pub.encode_mcu = encode_mcu_gather;
 125     entropy->pub.finish_pass = finish_pass_gather;
 126 #else
 127     ERREXIT(cinfo, JERR_NOT_COMPILED);
 128 #endif
 129   } else {
 130     entropy->pub.encode_mcu = encode_mcu_huff;
 131     entropy->pub.finish_pass = finish_pass_huff;
 132   }
 133
 134   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
 135     compptr = cinfo->cur_comp_info[ci];
 136     dctbl = compptr->dc_tbl_no;
 137     actbl = compptr->ac_tbl_no;
 138     if (gather_statistics) {
 139 #ifdef ENTROPY_OPT_SUPPORTED
 140       /* Check for invalid table indexes */
 141       /* (make_c_derived_tbl does this in the other path) */
 142       if (dctbl < 0 || dctbl >= NUM_HUFF_TBLS)
 143         ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, dctbl);
 144       if (actbl < 0 || actbl >= NUM_HUFF_TBLS)
 145         ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, actbl);
 146       /* Allocate and zero the statistics tables */
 147       /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */
 148       if (entropy->dc_count_ptrs[dctbl] == NULL)
 149         entropy->dc_count_ptrs[dctbl] = (long *)
 150           (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
 151                                       257 * SIZEOF(long));
 152       MEMZERO(entropy->dc_count_ptrs[dctbl], 257 * SIZEOF(long));
 153       if (entropy->ac_count_ptrs[actbl] == NULL)
 154         entropy->ac_count_ptrs[actbl] = (long *)
 155           (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
 156                                       257 * SIZEOF(long));
 157       MEMZERO(entropy->ac_count_ptrs[actbl], 257 * SIZEOF(long));
 158 #endif
 159     } else {
 160       /* Compute derived values for Huffman tables */
 161       /* We may do this more than once for a table, but it's not expensive */
 162       jpeg_make_c_derived_tbl(cinfo, TRUE, dctbl,
 163                               & entropy->dc_derived_tbls[dctbl]);
 164       jpeg_make_c_derived_tbl(cinfo, FALSE, actbl,
 165                               & entropy->ac_derived_tbls[actbl]);
 166     }
 167     /* Initialize DC predictions to 0 */
 168     entropy->saved.last_dc_val[ci] = 0;
 169   }
 170
 171   /* Initialize bit buffer to empty */
 172   entropy->saved.put_buffer = 0;
 173   entropy->saved.put_bits = 0;
 174
 175   /* Initialize restart stuff */
 176   entropy->restarts_to_go = cinfo->restart_interval;
 177   entropy->next_restart_num = 0;
 178 }
 179
 180
 181 /*
 182  * Compute the derived values for a Huffman table.
 183  * This routine also performs some validation checks on the table.
 184  *
 185  * Note this is also used by jcphuff.c.
 186  */
 187
 188 GLOBAL(void)
 189 jpeg_make_c_derived_tbl (j_compress_ptr cinfo, boolean isDC, int tblno,
 190                          c_derived_tbl ** pdtbl)
 191 {
 192   JHUFF_TBL *htbl;
 193   c_derived_tbl *dtbl;
 194   int p, i, l, lastp, si, maxsymbol;
 195   char huffsize[257];
 196   unsigned int huffcode[257];
 197   unsigned int code;
 198
 199   /* Note that huffsize[] and huffcode[] are filled in code-length order,
 200    * paralleling the order of the symbols themselves in htbl->huffval[].
 201    */
 202
 203   /* Find the input Huffman table */
 204   if (tblno < 0 || tblno >= NUM_HUFF_TBLS)
 205     ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
 206   htbl =
 207     isDC ? cinfo->dc_huff_tbl_ptrs[tblno] : cinfo->ac_huff_tbl_ptrs[tblno];
 208   if (htbl == NULL)
 209     ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
 210
 211   /* Allocate a workspace if we haven't already done so. */
 212   if (*pdtbl == NULL)
 213     *pdtbl = (c_derived_tbl *)
 214       (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
 215                                   SIZEOF(c_derived_tbl));
 216   dtbl = *pdtbl;
 217
 218   /* Figure C.1: make table of Huffman code length for each symbol */
 219
 220   p = 0;
 221   for (l = 1; l <= 16; l++) {
 222     i = (int) htbl->bits[l];
 223     if (i < 0 || p + i > 256)   /* protect against table overrun */
 224       ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
 225     while (i--)
 226       huffsize[p++] = (char) l;
 227   }
 228   huffsize[p] = 0;
 229   lastp = p;
 230
 231   /* Figure C.2: generate the codes themselves */
 232   /* We also validate that the counts represent a legal Huffman code tree. */
 233
 234   code = 0;
 235   si = huffsize[0];
 236   p = 0;
 237   while (huffsize[p]) {
 238     while (((int) huffsize[p]) == si) {
 239       huffcode[p++] = code;
 240       code++;
 241     }
 242     /* code is now 1 more than the last code used for codelength si; but
 243      * it must still fit in si bits, since no code is allowed to be all ones.
 244      */
 245     if (((INT32) code) >= (((INT32) 1) << si))
 246       ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
 247     code <<= 1;
 248     si++;
 249   }
 250
 251   /* Figure C.3: generate encoding tables */
 252   /* These are code and size indexed by symbol value */
 253
 254   /* Set all codeless symbols to have code length 0;
 255    * this lets us detect duplicate VAL entries here, and later
 256    * allows emit_bits to detect any attempt to emit such symbols.
 257    */
 258   MEMZERO(dtbl->ehufsi, SIZEOF(dtbl->ehufsi));
 259
 260   /* This is also a convenient place to check for out-of-range
 261    * and duplicated VAL entries.  We allow 0..255 for AC symbols
 262    * but only 0..15 for DC.  (We could constrain them further
 263    * based on data depth and mode, but this seems enough.)
 264    */
 265   maxsymbol = isDC ? 15 : 255;
 266
 267   for (p = 0; p < lastp; p++) {
 268     i = htbl->huffval[p];
 269     if (i < 0 || i > maxsymbol || dtbl->ehufsi[i])
 270       ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
 271     dtbl->ehufco[i] = huffcode[p];
 272     dtbl->ehufsi[i] = huffsize[p];
 273   }
 274
 275   if(!jpeg_nbits_table_init) {
 276     for(i = 0; i < 65536; i++) {
 277       int nbits = 0, temp = i;
 278       while (temp) {temp >>= 1;  nbits++;}
 279       jpeg_nbits_table[i] = nbits;
 280     }
 281     jpeg_nbits_table_init = 1;
 282   }
 283 }
 284
 285
 286 /* Outputting bytes to the file */
 287
 288 /* Emit a byte, taking 'action' if must suspend. */
 289 #define emit_byte(state,val,action)  \
 290         { *(state)->next_output_byte++ = (JOCTET) (val);  \
 291           if (--(state)->free_in_buffer == 0)  \
 292             if (! dump_buffer(state))  \
 293               { action; } }
 294
 295
 296 LOCAL(boolean)
 297 dump_buffer (working_state * state)
 298 /* Empty the output buffer; return TRUE if successful, FALSE if must suspend */
 299 {
 300   struct jpeg_destination_mgr * dest = state->cinfo->dest;
 301
 302   if (! (*dest->empty_output_buffer) (state->cinfo))
 303     return FALSE;
 304   /* After a successful buffer dump, must reset buffer pointers */
 305   state->next_output_byte = dest->next_output_byte;
 306   state->free_in_buffer = dest->free_in_buffer;
 307   return TRUE;
 308 }
 309
 310
 311 /* Outputting bits to the file */
 312
 313 /* These macros perform the same task as the emit_bits() function in the
 314  * original libjpeg code.  In addition to reducing overhead by explicitly
 315  * inlining the code, additional performance is achieved by taking into
 316  * account the size of the bit buffer and waiting until it is almost full
 317  * before emptying it.  This mostly benefits 64-bit platforms, since 6
 318  * bytes can be stored in a 64-bit bit buffer before it has to be emptied.
 319  */
 320
 321 #define EMIT_BYTE() { \
 322   JOCTET c; \
 323   put_bits -= 8; \
 324   c = (JOCTET)GETJOCTET(put_buffer >> put_bits); \
 325   *buffer++ = c; \
 326   if (c == 0xFF)  /* need to stuff a zero byte? */ \
 327     *buffer++ = 0; \
 328  }
 329
 330 #define PUT_BITS(code, size) { \
 331   put_bits += size; \
 332   put_buffer = (put_buffer << size) | code; \
 333 }
 334
 335 #define CHECKBUF15() { \
 336   if (put_bits > 15) { \
 337     EMIT_BYTE() \
 338     EMIT_BYTE() \
 339   } \
 340 }
 341
 342 #define CHECKBUF31() { \
 343   if (put_bits > 31) { \
 344     EMIT_BYTE() \
 345     EMIT_BYTE() \
 346     EMIT_BYTE() \
 347     EMIT_BYTE() \
 348   } \
 349 }
 350
 351 #define CHECKBUF47() { \
 352   if (put_bits > 47) { \
 353     EMIT_BYTE() \
 354     EMIT_BYTE() \
 355     EMIT_BYTE() \
 356     EMIT_BYTE() \
 357     EMIT_BYTE() \
 358     EMIT_BYTE() \
 359   } \
 360 }
 361
 362 #if __WORDSIZE==64 || defined(_WIN64)
 363
 364 #define EMIT_BITS(code, size) { \
 365   CHECKBUF47() \
 366   PUT_BITS(code, size) \
 367 }
 368
 369 #define EMIT_CODE(code, size) { \
 370   temp2 &= (((INT32) 1)<<nbits) - 1; \
 371   CHECKBUF31() \
 372   PUT_BITS(code, size) \
 373   PUT_BITS(temp2, nbits) \
 374  }
 375
 376 #else
 377
 378 #define EMIT_BITS(code, size) { \
 379   PUT_BITS(code, size) \
 380   CHECKBUF15() \
 381 }
 382
 383 #define EMIT_CODE(code, size) { \
 384   temp2 &= (((INT32) 1)<<nbits) - 1; \
 385   PUT_BITS(code, size) \
 386   CHECKBUF15() \
 387   PUT_BITS(temp2, nbits) \
 388   CHECKBUF15() \
 389  }
 390
 391 #endif
 392
 393
 394 #define BUFSIZE (DCTSIZE2 * 2)
 395
 396 #define LOAD_BUFFER() { \
 397   if (state->free_in_buffer < BUFSIZE) { \
 398     localbuf = 1; \
 399     buffer = _buffer; \
 400   } \
 401   else buffer = state->next_output_byte; \
 402  }
 403
 404 #define STORE_BUFFER() { \
 405   if (localbuf) { \
 406     bytes = buffer - _buffer; \
 407     buffer = _buffer; \
 408     while (bytes > 0) { \
 409       bytestocopy = min(bytes, state->free_in_buffer); \
 410       MEMCOPY(state->next_output_byte, buffer, bytestocopy); \
 411       state->next_output_byte += bytestocopy; \
 412       buffer += bytestocopy; \
 413       state->free_in_buffer -= bytestocopy; \
 414       if (state->free_in_buffer == 0) \
 415         if (! dump_buffer(state)) return FALSE; \
 416       bytes -= bytestocopy; \
 417     } \
 418   } \
 419   else { \
 420     state->free_in_buffer -= (buffer - state->next_output_byte); \
 421     state->next_output_byte = buffer; \
 422   } \
 423  }
 424
 425
 426 LOCAL(boolean)
 427 flush_bits (working_state * state)
 428 {
 429   JOCTET _buffer[BUFSIZE], *buffer;
 430   size_t put_buffer;  int put_bits;
 431   size_t bytes, bytestocopy;  int localbuf = 0;
 432
 433   put_buffer = state->cur.put_buffer;
 434   put_bits = state->cur.put_bits;
 435   LOAD_BUFFER()
 436
 437   /* fill any partial byte with ones */
 438   PUT_BITS(0x7F, 7)
 439   while (put_bits >= 8) EMIT_BYTE()
 440
 441   state->cur.put_buffer = 0;    /* and reset bit-buffer to empty */
 442   state->cur.put_bits = 0;
 443   STORE_BUFFER()
 444
 445   return TRUE;
 446 }
 447
 448
 449 /* Encode a single block's worth of coefficients */
 450
 451 LOCAL(boolean)
 452 encode_one_block (working_state * state, JCOEFPTR block, int last_dc_val,
 453                   c_derived_tbl *dctbl, c_derived_tbl *actbl)
 454 {
 455   int temp, temp2, temp3;
 456   int nbits;
 457   int r, code, size;
 458   JOCTET _buffer[BUFSIZE], *buffer;
 459   size_t put_buffer;  int put_bits;
 460   int code_0xf0 = actbl->ehufco[0xf0], size_0xf0 = actbl->ehufsi[0xf0];
 461   size_t bytes, bytestocopy;  int localbuf = 0;
 462
 463   put_buffer = state->cur.put_buffer;
 464   put_bits = state->cur.put_bits;
 465   LOAD_BUFFER()
 466
 467   /* Encode the DC coefficient difference per section F.1.2.1 */
 468
 469   temp = temp2 = block[0] - last_dc_val;
 470
 471  /* This is a well-known technique for obtaining the absolute value without a
 472   * branch.  It is derived from an assembly language technique presented in
 473   * "How to Optimize for the Pentium Processors", Copyright (c) 1996, 1997 by
 474   * Agner Fog.
 475   */
 476   temp3 = temp >> (CHAR_BIT * sizeof(int) - 1);
 477   temp ^= temp3;
 478   temp -= temp3;
 479
 480   /* For a negative input, want temp2 = bitwise complement of abs(input) */
 481   /* This code assumes we are on a two's complement machine */
 482   temp2 += temp3;
 483
 484   /* Find the number of bits needed for the magnitude of the coefficient */
 485   nbits = jpeg_nbits_table[temp];
 486
 487   /* Emit the Huffman-coded symbol for the number of bits */
 488   code = dctbl->ehufco[nbits];
 489   size = dctbl->ehufsi[nbits];
 490   PUT_BITS(code, size)
 491   CHECKBUF15()
 492
 493   /* Mask off any extra bits in code */
 494   temp2 &= (((INT32) 1)<<nbits) - 1;
 495
 496   /* Emit that number of bits of the value, if positive, */
 497   /* or the complement of its magnitude, if negative. */
 498   PUT_BITS(temp2, nbits)
 499   CHECKBUF15()
 500
 501   /* Encode the AC coefficients per section F.1.2.2 */
 502
 503   r = 0;                        /* r = run length of zeros */
 504
 505 /* Manually unroll the k loop to eliminate the counter variable.  This
 506  * improves performance greatly on systems with a limited number of
 507  * registers (such as x86.)
 508  */
 509 #define kloop(jpeg_natural_order_of_k) {  \
 510   if ((temp = block[jpeg_natural_order_of_k]) == 0) { \
 511     r++; \
 512   } else { \
 513     temp2 = temp; \
 514     /* Branch-less absolute value, bitwise complement, etc., same as above */ \
 515     temp3 = temp >> (CHAR_BIT * sizeof(int) - 1); \
 516     temp ^= temp3; \
 517     temp -= temp3; \
 518     temp2 += temp3; \
 519     nbits = jpeg_nbits_table[temp]; \
 520     /* if run length > 15, must emit special run-length-16 codes (0xF0) */ \
 521     while (r > 15) { \
 522       EMIT_BITS(code_0xf0, size_0xf0) \
 523       r -= 16; \
 524     } \
 525     /* Emit Huffman symbol for run length / number of bits */ \
 526     temp3 = (r << 4) + nbits;  \
 527     code = actbl->ehufco[temp3]; \
 528     size = actbl->ehufsi[temp3]; \
 529     EMIT_CODE(code, size) \
 530     r = 0;  \
 531   } \
 532 }
 533
 534   /* One iteration for each value in jpeg_natural_order[] */
 535   kloop(1);   kloop(8);   kloop(16);  kloop(9);   kloop(2);   kloop(3);
 536   kloop(10);  kloop(17);  kloop(24);  kloop(32);  kloop(25);  kloop(18);
 537   kloop(11);  kloop(4);   kloop(5);   kloop(12);  kloop(19);  kloop(26);
 538   kloop(33);  kloop(40);  kloop(48);  kloop(41);  kloop(34);  kloop(27);
 539   kloop(20);  kloop(13);  kloop(6);   kloop(7);   kloop(14);  kloop(21);
 540   kloop(28);  kloop(35);  kloop(42);  kloop(49);  kloop(56);  kloop(57);
 541   kloop(50);  kloop(43);  kloop(36);  kloop(29);  kloop(22);  kloop(15);
 542   kloop(23);  kloop(30);  kloop(37);  kloop(44);  kloop(51);  kloop(58);
 543   kloop(59);  kloop(52);  kloop(45);  kloop(38);  kloop(31);  kloop(39);
 544   kloop(46);  kloop(53);  kloop(60);  kloop(61);  kloop(54);  kloop(47);
 545   kloop(55);  kloop(62);  kloop(63);
 546
 547   /* If the last coef(s) were zero, emit an end-of-block code */
 548   if (r > 0) {
 549     code = actbl->ehufco[0];
 550     size = actbl->ehufsi[0];
 551     EMIT_BITS(code, size)
 552   }
 553
 554   state->cur.put_buffer = put_buffer;
 555   state->cur.put_bits = put_bits;
 556   STORE_BUFFER()
 557
 558   return TRUE;
 559 }
 560
 561
 562 /*
 563  * Emit a restart marker & resynchronize predictions.
 564  */
 565
 566 LOCAL(boolean)
 567 emit_restart (working_state * state, int restart_num)
 568 {
 569   int ci;
 570
 571   if (! flush_bits(state))
 572     return FALSE;
 573
 574   emit_byte(state, 0xFF, return FALSE);
 575   emit_byte(state, JPEG_RST0 + restart_num, return FALSE);
 576
 577   /* Re-initialize DC predictions to 0 */
 578   for (ci = 0; ci < state->cinfo->comps_in_scan; ci++)
 579     state->cur.last_dc_val[ci] = 0;
 580
 581   /* The restart counter is not updated until we successfully write the MCU. */
 582
 583   return TRUE;
 584 }
 585
 586
 587 /*
 588  * Encode and output one MCU's worth of Huffman-compressed coefficients.
 589  */
 590
 591 METHODDEF(boolean)
 592 encode_mcu_huff (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 593 {
 594   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
 595   working_state state;
 596   int blkn, ci;
 597   jpeg_component_info * compptr;
 598
 599   /* Load up working state */
 600   state.next_output_byte = cinfo->dest->next_output_byte;
 601   state.free_in_buffer = cinfo->dest->free_in_buffer;
 602   ASSIGN_STATE(state.cur, entropy->saved);
 603   state.cinfo = cinfo;
 604
 605   /* Emit restart marker if needed */
 606   if (cinfo->restart_interval) {
 607     if (entropy->restarts_to_go == 0)
 608       if (! emit_restart(&state, entropy->next_restart_num))
 609         return FALSE;
 610   }
 611
 612   /* Encode the MCU data blocks */
 613   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
 614     ci = cinfo->MCU_membership[blkn];
 615     compptr = cinfo->cur_comp_info[ci];
 616     if (! encode_one_block(&state,
 617                            MCU_data[blkn][0], state.cur.last_dc_val[ci],
 618                            entropy->dc_derived_tbls[compptr->dc_tbl_no],
 619                            entropy->ac_derived_tbls[compptr->ac_tbl_no]))
 620       return FALSE;
 621     /* Update last_dc_val */
 622     state.cur.last_dc_val[ci] = MCU_data[blkn][0][0];
 623   }
 624
 625   /* Completed MCU, so update state */
 626   cinfo->dest->next_output_byte = state.next_output_byte;
 627   cinfo->dest->free_in_buffer = state.free_in_buffer;
 628   ASSIGN_STATE(entropy->saved, state.cur);
 629
 630   /* Update restart-interval state too */
 631   if (cinfo->restart_interval) {
 632     if (entropy->restarts_to_go == 0) {
 633       entropy->restarts_to_go = cinfo->restart_interval;
 634       entropy->next_restart_num++;
 635       entropy->next_restart_num &= 7;
 636     }
 637     entropy->restarts_to_go--;
 638   }
 639
 640   return TRUE;
 641 }
 642
 643
 644 /*
 645  * Finish up at the end of a Huffman-compressed scan.
 646  */
 647
 648 METHODDEF(void)
 649 finish_pass_huff (j_compress_ptr cinfo)
 650 {
 651   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
 652   working_state state;
 653
 654   /* Load up working state ... flush_bits needs it */
 655   state.next_output_byte = cinfo->dest->next_output_byte;
 656   state.free_in_buffer = cinfo->dest->free_in_buffer;
 657   ASSIGN_STATE(state.cur, entropy->saved);
 658   state.cinfo = cinfo;
 659
 660   /* Flush out the last data */
 661   if (! flush_bits(&state))
 662     ERREXIT(cinfo, JERR_CANT_SUSPEND);
 663
 664   /* Update state */
 665   cinfo->dest->next_output_byte = state.next_output_byte;
 666   cinfo->dest->free_in_buffer = state.free_in_buffer;
 667   ASSIGN_STATE(entropy->saved, state.cur);
 668 }
 669
 670
 671 /*
 672  * Huffman coding optimization.
 673  *
 674  * We first scan the supplied data and count the number of uses of each symbol
 675  * that is to be Huffman-coded. (This process MUST agree with the code above.)
 676  * Then we build a Huffman coding tree for the observed counts.
 677  * Symbols which are not needed at all for the particular image are not
 678  * assigned any code, which saves space in the DHT marker as well as in
 679  * the compressed data.
 680  */
 681
 682 #ifdef ENTROPY_OPT_SUPPORTED
 683
 684
 685 /* Process a single block's worth of coefficients */
 686
 687 LOCAL(void)
 688 htest_one_block (j_compress_ptr cinfo, JCOEFPTR block, int last_dc_val,
 689                  long dc_counts[], long ac_counts[])
 690 {
 691   register int temp;
 692   register int nbits;
 693   register int k, r;
 694
 695   /* Encode the DC coefficient difference per section F.1.2.1 */
 696
 697   temp = block[0] - last_dc_val;
 698   if (temp < 0)
 699     temp = -temp;
 700
 701   /* Find the number of bits needed for the magnitude of the coefficient */
 702   nbits = 0;
 703   while (temp) {
 704     nbits++;
 705     temp >>= 1;
 706   }
 707   /* Check for out-of-range coefficient values.
 708    * Since we're encoding a difference, the range limit is twice as much.
 709    */
 710   if (nbits > MAX_COEF_BITS+1)
 711     ERREXIT(cinfo, JERR_BAD_DCT_COEF);
 712
 713   /* Count the Huffman symbol for the number of bits */
 714   dc_counts[nbits]++;
 715
 716   /* Encode the AC coefficients per section F.1.2.2 */
 717
 718   r = 0;                        /* r = run length of zeros */
 719
 720   for (k = 1; k < DCTSIZE2; k++) {
 721     if ((temp = block[jpeg_natural_order[k]]) == 0) {
 722       r++;
 723     } else {
 724       /* if run length > 15, must emit special run-length-16 codes (0xF0) */
 725       while (r > 15) {
 726         ac_counts[0xF0]++;
 727         r -= 16;
 728       }
 729
 730       /* Find the number of bits needed for the magnitude of the coefficient */
 731       if (temp < 0)
 732         temp = -temp;
 733
 734       /* Find the number of bits needed for the magnitude of the coefficient */
 735       nbits = 1;                /* there must be at least one 1 bit */
 736       while ((temp >>= 1))
 737         nbits++;
 738       /* Check for out-of-range coefficient values */
 739       if (nbits > MAX_COEF_BITS)
 740         ERREXIT(cinfo, JERR_BAD_DCT_COEF);
 741
 742       /* Count Huffman symbol for run length / number of bits */
 743       ac_counts[(r << 4) + nbits]++;
 744
 745       r = 0;
 746     }
 747   }
 748
 749   /* If the last coef(s) were zero, emit an end-of-block code */
 750   if (r > 0)
 751     ac_counts[0]++;
 752 }
 753
 754
 755 /*
 756  * Trial-encode one MCU's worth of Huffman-compressed coefficients.
 757  * No data is actually output, so no suspension return is possible.
 758  */
 759
 760 METHODDEF(boolean)
 761 encode_mcu_gather (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 762 {
 763   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
 764   int blkn, ci;
 765   jpeg_component_info * compptr;
 766
 767   /* Take care of restart intervals if needed */
 768   if (cinfo->restart_interval) {
 769     if (entropy->restarts_to_go == 0) {
 770       /* Re-initialize DC predictions to 0 */
 771       for (ci = 0; ci < cinfo->comps_in_scan; ci++)
 772         entropy->saved.last_dc_val[ci] = 0;
 773       /* Update restart state */
 774       entropy->restarts_to_go = cinfo->restart_interval;
 775     }
 776     entropy->restarts_to_go--;
 777   }
 778
 779   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
 780     ci = cinfo->MCU_membership[blkn];
 781     compptr = cinfo->cur_comp_info[ci];
 782     htest_one_block(cinfo, MCU_data[blkn][0], entropy->saved.last_dc_val[ci],
 783                     entropy->dc_count_ptrs[compptr->dc_tbl_no],
 784                     entropy->ac_count_ptrs[compptr->ac_tbl_no]);
 785     entropy->saved.last_dc_val[ci] = MCU_data[blkn][0][0];
 786   }
 787
 788   return TRUE;
 789 }
 790
 791
 792 /*
 793  * Generate the best Huffman code table for the given counts, fill htbl.
 794  * Note this is also used by jcphuff.c.
 795  *
 796  * The JPEG standard requires that no symbol be assigned a codeword of all
 797  * one bits (so that padding bits added at the end of a compressed segment
 798  * can't look like a valid code).  Because of the canonical ordering of
 799  * codewords, this just means that there must be an unused slot in the
 800  * longest codeword length category.  Section K.2 of the JPEG spec suggests
 801  * reserving such a slot by pretending that symbol 256 is a valid symbol
 802  * with count 1.  In theory that's not optimal; giving it count zero but
 803  * including it in the symbol set anyway should give a better Huffman code.
 804  * But the theoretically better code actually seems to come out worse in
 805  * practice, because it produces more all-ones bytes (which incur stuffed
 806  * zero bytes in the final file).  In any case the difference is tiny.
 807  *
 808  * The JPEG standard requires Huffman codes to be no more than 16 bits long.
 809  * If some symbols have a very small but nonzero probability, the Huffman tree
 810  * must be adjusted to meet the code length restriction.  We currently use
 811  * the adjustment method suggested in JPEG section K.2.  This method is *not*
 812  * optimal; it may not choose the best possible limited-length code.  But
 813  * typically only very-low-frequency symbols will be given less-than-optimal
 814  * lengths, so the code is almost optimal.  Experimental comparisons against
 815  * an optimal limited-length-code algorithm indicate that the difference is
 816  * microscopic --- usually less than a hundredth of a percent of total size.
 817  * So the extra complexity of an optimal algorithm doesn't seem worthwhile.
 818  */
 819
 820 GLOBAL(void)
 821 jpeg_gen_optimal_table (j_compress_ptr cinfo, JHUFF_TBL * htbl, long freq[])
 822 {
 823 #define MAX_CLEN 32             /* assumed maximum initial code length */
 824   UINT8 bits[MAX_CLEN+1];       /* bits[k] = # of symbols with code length k */
 825   int codesize[257];            /* codesize[k] = code length of symbol k */
 826   int others[257];              /* next symbol in current branch of tree */
 827   int c1, c2;
 828   int p, i, j;
 829   long v;
 830
 831   /* This algorithm is explained in section K.2 of the JPEG standard */
 832
 833   MEMZERO(bits, SIZEOF(bits));
 834   MEMZERO(codesize, SIZEOF(codesize));
 835   for (i = 0; i < 257; i++)
 836     others[i] = -1;             /* init links to empty */
 837
 838   freq[256] = 1;                /* make sure 256 has a nonzero count */
 839   /* Including the pseudo-symbol 256 in the Huffman procedure guarantees
 840    * that no real symbol is given code-value of all ones, because 256
 841    * will be placed last in the largest codeword category.
 842    */
 843
 844   /* Huffman's basic algorithm to assign optimal code lengths to symbols */
 845
 846   for (;;) {
 847     /* Find the smallest nonzero frequency, set c1 = its symbol */
 848     /* In case of ties, take the larger symbol number */
 849     c1 = -1;
 850     v = 1000000000L;
 851     for (i = 0; i <= 256; i++) {
 852       if (freq[i] && freq[i] <= v) {
 853         v = freq[i];
 854         c1 = i;
 855       }
 856     }
 857
 858     /* Find the next smallest nonzero frequency, set c2 = its symbol */
 859     /* In case of ties, take the larger symbol number */
 860     c2 = -1;
 861     v = 1000000000L;
 862     for (i = 0; i <= 256; i++) {
 863       if (freq[i] && freq[i] <= v && i != c1) {
 864         v = freq[i];
 865         c2 = i;
 866       }
 867     }
 868
 869     /* Done if we've merged everything into one frequency */
 870     if (c2 < 0)
 871       break;
 872
 873     /* Else merge the two counts/trees */
 874     freq[c1] += freq[c2];
 875     freq[c2] = 0;
 876
 877     /* Increment the codesize of everything in c1's tree branch */
 878     codesize[c1]++;
 879     while (others[c1] >= 0) {
 880       c1 = others[c1];
 881       codesize[c1]++;
 882     }
 883
 884     others[c1] = c2;            /* chain c2 onto c1's tree branch */
 885
 886     /* Increment the codesize of everything in c2's tree branch */
 887     codesize[c2]++;
 888     while (others[c2] >= 0) {
 889       c2 = others[c2];
 890       codesize[c2]++;
 891     }
 892   }
 893
 894   /* Now count the number of symbols of each code length */
 895   for (i = 0; i <= 256; i++) {
 896     if (codesize[i]) {
 897       /* The JPEG standard seems to think that this can't happen, */
 898       /* but I'm paranoid... */
 899       if (codesize[i] > MAX_CLEN)
 900         ERREXIT(cinfo, JERR_HUFF_CLEN_OVERFLOW);
 901
 902       bits[codesize[i]]++;
 903     }
 904   }
 905
 906   /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure
 907    * Huffman procedure assigned any such lengths, we must adjust the coding.
 908    * Here is what the JPEG spec says about how this next bit works:
 909    * Since symbols are paired for the longest Huffman code, the symbols are
 910    * removed from this length category two at a time.  The prefix for the pair
 911    * (which is one bit shorter) is allocated to one of the pair; then,
 912    * skipping the BITS entry for that prefix length, a code word from the next
 913    * shortest nonzero BITS entry is converted into a prefix for two code words
 914    * one bit longer.
 915    */
 916
 917   for (i = MAX_CLEN; i > 16; i--) {
 918     while (bits[i] > 0) {
 919       j = i - 2;                /* find length of new prefix to be used */
 920       while (bits[j] == 0)
 921         j--;
 922
 923       bits[i] -= 2;             /* remove two symbols */
 924       bits[i-1]++;              /* one goes in this length */
 925       bits[j+1] += 2;           /* two new symbols in this length */
 926       bits[j]--;                /* symbol of this length is now a prefix */
 927     }
 928   }
 929
 930   /* Remove the count for the pseudo-symbol 256 from the largest codelength */
 931   while (bits[i] == 0)          /* find largest codelength still in use */
 932     i--;
 933   bits[i]--;
 934
 935   /* Return final symbol counts (only for lengths 0..16) */
 936   MEMCOPY(htbl->bits, bits, SIZEOF(htbl->bits));
 937
 938   /* Return a list of the symbols sorted by code length */
 939   /* It's not real clear to me why we don't need to consider the codelength
 940    * changes made above, but the JPEG spec seems to think this works.
 941    */
 942   p = 0;
 943   for (i = 1; i <= MAX_CLEN; i++) {
 944     for (j = 0; j <= 255; j++) {
 945       if (codesize[j] == i) {
 946         htbl->huffval[p] = (UINT8) j;
 947         p++;
 948       }
 949     }
 950   }
 951
 952   /* Set sent_table FALSE so updated table will be written to JPEG file. */
 953   htbl->sent_table = FALSE;
 954 }
 955
 956
 957 /*
 958  * Finish up a statistics-gathering pass and create the new Huffman tables.
 959  */
 960
 961 METHODDEF(void)
 962 finish_pass_gather (j_compress_ptr cinfo)
 963 {
 964   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
 965   int ci, dctbl, actbl;
 966   jpeg_component_info * compptr;
 967   JHUFF_TBL **htblptr;
 968   boolean did_dc[NUM_HUFF_TBLS];
 969   boolean did_ac[NUM_HUFF_TBLS];
 970
 971   /* It's important not to apply jpeg_gen_optimal_table more than once
 972    * per table, because it clobbers the input frequency counts!
 973    */
 974   MEMZERO(did_dc, SIZEOF(did_dc));
 975   MEMZERO(did_ac, SIZEOF(did_ac));
 976
 977   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
 978     compptr = cinfo->cur_comp_info[ci];
 979     dctbl = compptr->dc_tbl_no;
 980     actbl = compptr->ac_tbl_no;
 981     if (! did_dc[dctbl]) {
 982       htblptr = & cinfo->dc_huff_tbl_ptrs[dctbl];
 983       if (*htblptr == NULL)
 984         *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
 985       jpeg_gen_optimal_table(cinfo, *htblptr, entropy->dc_count_ptrs[dctbl]);
 986       did_dc[dctbl] = TRUE;
 987     }
 988     if (! did_ac[actbl]) {
 989       htblptr = & cinfo->ac_huff_tbl_ptrs[actbl];
 990       if (*htblptr == NULL)
 991         *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
 992       jpeg_gen_optimal_table(cinfo, *htblptr, entropy->ac_count_ptrs[actbl]);
 993       did_ac[actbl] = TRUE;
 994     }
 995   }
 996 }
 997
 998
 999 #endif /* ENTROPY_OPT_SUPPORTED */
1000
1001
1002 /*
1003  * Module initialization routine for Huffman entropy encoding.
1004  */
1005
1006 GLOBAL(void)
1007 jinit_huff_encoder (j_compress_ptr cinfo)
1008 {
1009   huff_entropy_ptr entropy;
1010   int i;
1011
1012   entropy = (huff_entropy_ptr)
1013     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
1014                                 SIZEOF(huff_entropy_encoder));
1015   cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
1016   entropy->pub.start_pass = start_pass_huff;
1017
1018   /* Mark tables unallocated */
1019   for (i = 0; i < NUM_HUFF_TBLS; i++) {
1020     entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL;
1021 #ifdef ENTROPY_OPT_SUPPORTED
1022     entropy->dc_count_ptrs[i] = entropy->ac_count_ptrs[i] = NULL;
1023 #endif
1024   }
1025 }