jcphuff.c

   1 /*
   2  * jcphuff.c
   3  *
   4  * This file was part of the Independent JPEG Group's software:
   5  * Copyright (C) 1995-1997, Thomas G. Lane.
   6  * libjpeg-turbo Modifications:
   7  * Copyright (C) 2011, 2015, 2018, 2021-2022, D. R. Commander.
   8  * Copyright (C) 2016, 2018, Matthieu Darbois.
   9  * Copyright (C) 2020, Arm Limited.
  10  * Copyright (C) 2021, Alex Richardson.
  11  * For conditions of distribution and use, see the accompanying README.ijg
  12  * file.
  13  *
  14  * This file contains Huffman entropy encoding routines for progressive JPEG.
  15  *
  16  * We do not support output suspension in this module, since the library
  17  * currently does not allow multiple-scan files to be written with output
  18  * suspension.
  19  */
  20
  21 #define JPEG_INTERNALS
  22 #include "jinclude.h"
  23 #include "jpeglib.h"
  24 #include "jsimd.h"
  25 #include "jconfigint.h"
  26 #include <limits.h>
  27
  28 #ifdef HAVE_INTRIN_H
  29 #include <intrin.h>
  30 #ifdef _MSC_VER
  31 #ifdef HAVE_BITSCANFORWARD64
  32 #pragma intrinsic(_BitScanForward64)
  33 #endif
  34 #ifdef HAVE_BITSCANFORWARD
  35 #pragma intrinsic(_BitScanForward)
  36 #endif
  37 #endif
  38 #endif
  39
  40 #ifdef C_PROGRESSIVE_SUPPORTED
  41
  42 /*
  43  * NOTE: If USE_CLZ_INTRINSIC is defined, then clz/bsr instructions will be
  44  * used for bit counting rather than the lookup table.  This will reduce the
  45  * memory footprint by 64k, which is important for some mobile applications
  46  * that create many isolated instances of libjpeg-turbo (web browsers, for
  47  * instance.)  This may improve performance on some mobile platforms as well.
  48  * This feature is enabled by default only on Arm processors, because some x86
  49  * chips have a slow implementation of bsr, and the use of clz/bsr cannot be
  50  * shown to have a significant performance impact even on the x86 chips that
  51  * have a fast implementation of it.  When building for Armv6, you can
  52  * explicitly disable the use of clz/bsr by adding -mthumb to the compiler
  53  * flags (this defines __thumb__).
  54  */
  55
  56 /* NOTE: Both GCC and Clang define __GNUC__ */
  57 #if (defined(__GNUC__) && (defined(__arm__) || defined(__aarch64__))) || \
  58     defined(_M_ARM) || defined(_M_ARM64)
  59 #if !defined(__thumb__) || defined(__thumb2__)
  60 #define USE_CLZ_INTRINSIC
  61 #endif
  62 #endif
  63
  64 #ifdef USE_CLZ_INTRINSIC
  65 #if defined(_MSC_VER) && !defined(__clang__)
  66 #define JPEG_NBITS_NONZERO(x)  (32 - _CountLeadingZeros(x))
  67 #else
  68 #define JPEG_NBITS_NONZERO(x)  (32 - __builtin_clz(x))
  69 #endif
  70 #define JPEG_NBITS(x)          (x ? JPEG_NBITS_NONZERO(x) : 0)
  71 #else
  72 #include "jpeg_nbits_table.h"
  73 #define JPEG_NBITS(x)          (jpeg_nbits_table[x])
  74 #define JPEG_NBITS_NONZERO(x)  JPEG_NBITS(x)
  75 #endif
  76
  77
  78 /* Expanded entropy encoder object for progressive Huffman encoding. */
  79
  80 typedef struct {
  81   struct jpeg_entropy_encoder pub; /* public fields */
  82
  83   /* Pointer to routine to prepare data for encode_mcu_AC_first() */
  84   void (*AC_first_prepare) (const JCOEF *block,
  85                             const int *jpeg_natural_order_start, int Sl,
  86                             int Al, JCOEF *values, size_t *zerobits);
  87   /* Pointer to routine to prepare data for encode_mcu_AC_refine() */
  88   int (*AC_refine_prepare) (const JCOEF *block,
  89                             const int *jpeg_natural_order_start, int Sl,
  90                             int Al, JCOEF *absvalues, size_t *bits);
  91
  92   /* Mode flag: TRUE for optimization, FALSE for actual data output */
  93   boolean gather_statistics;
  94
  95   /* Bit-level coding status.
  96    * next_output_byte/free_in_buffer are local copies of cinfo->dest fields.
  97    */
  98   JOCTET *next_output_byte;     /* => next byte to write in buffer */
  99   size_t free_in_buffer;        /* # of byte spaces remaining in buffer */
 100   size_t put_buffer;            /* current bit-accumulation buffer */
 101   int put_bits;                 /* # of bits now in it */
 102   j_compress_ptr cinfo;         /* link to cinfo (needed for dump_buffer) */
 103
 104   /* Coding status for DC components */
 105   int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
 106
 107   /* Coding status for AC components */
 108   int ac_tbl_no;                /* the table number of the single component */
 109   unsigned int EOBRUN;          /* run length of EOBs */
 110   unsigned int BE;              /* # of buffered correction bits before MCU */
 111   char *bit_buffer;             /* buffer for correction bits (1 per char) */
 112   /* packing correction bits tightly would save some space but cost time... */
 113
 114   unsigned int restarts_to_go;  /* MCUs left in this restart interval */
 115   int next_restart_num;         /* next restart number to write (0-7) */
 116
 117   /* Pointers to derived tables (these workspaces have image lifespan).
 118    * Since any one scan codes only DC or only AC, we only need one set
 119    * of tables, not one for DC and one for AC.
 120    */
 121   c_derived_tbl *derived_tbls[NUM_HUFF_TBLS];
 122
 123   /* Statistics tables for optimization; again, one set is enough */
 124   long *count_ptrs[NUM_HUFF_TBLS];
 125 } phuff_entropy_encoder;
 126
 127 typedef phuff_entropy_encoder *phuff_entropy_ptr;
 128
 129 /* MAX_CORR_BITS is the number of bits the AC refinement correction-bit
 130  * buffer can hold.  Larger sizes may slightly improve compression, but
 131  * 1000 is already well into the realm of overkill.
 132  * The minimum safe size is 64 bits.
 133  */
 134
 135 #define MAX_CORR_BITS  1000     /* Max # of correction bits I can buffer */
 136
 137 /* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than JLONG.
 138  * We assume that int right shift is unsigned if JLONG right shift is,
 139  * which should be safe.
 140  */
 141
 142 #ifdef RIGHT_SHIFT_IS_UNSIGNED
 143 #define ISHIFT_TEMPS    int ishift_temp;
 144 #define IRIGHT_SHIFT(x, shft) \
 145   ((ishift_temp = (x)) < 0 ? \
 146    (ishift_temp >> (shft)) | ((~0) << (16 - (shft))) : \
 147    (ishift_temp >> (shft)))
 148 #else
 149 #define ISHIFT_TEMPS
 150 #define IRIGHT_SHIFT(x, shft)   ((x) >> (shft))
 151 #endif
 152
 153 #define PAD(v, p)  ((v + (p) - 1) & (~((p) - 1)))
 154
 155 /* Forward declarations */
 156 METHODDEF(boolean) encode_mcu_DC_first(j_compress_ptr cinfo,
 157                                        JBLOCKROW *MCU_data);
 158 METHODDEF(void) encode_mcu_AC_first_prepare
 159   (const JCOEF *block, const int *jpeg_natural_order_start, int Sl, int Al,
 160    JCOEF *values, size_t *zerobits);
 161 METHODDEF(boolean) encode_mcu_AC_first(j_compress_ptr cinfo,
 162                                        JBLOCKROW *MCU_data);
 163 METHODDEF(boolean) encode_mcu_DC_refine(j_compress_ptr cinfo,
 164                                         JBLOCKROW *MCU_data);
 165 METHODDEF(int) encode_mcu_AC_refine_prepare
 166   (const JCOEF *block, const int *jpeg_natural_order_start, int Sl, int Al,
 167    JCOEF *absvalues, size_t *bits);
 168 METHODDEF(boolean) encode_mcu_AC_refine(j_compress_ptr cinfo,
 169                                         JBLOCKROW *MCU_data);
 170 METHODDEF(void) finish_pass_phuff(j_compress_ptr cinfo);
 171 METHODDEF(void) finish_pass_gather_phuff(j_compress_ptr cinfo);
 172
 173
 174 /* Count bit loop zeroes */
 175 INLINE
 176 METHODDEF(int)
 177 count_zeroes(size_t *x)
 178 {
 179 #if defined(HAVE_BUILTIN_CTZL)
 180   int result;
 181   result = __builtin_ctzl(*x);
 182   *x >>= result;
 183 #elif defined(HAVE_BITSCANFORWARD64)
 184   unsigned long result;
 185   _BitScanForward64(&result, *x);
 186   *x >>= result;
 187 #elif defined(HAVE_BITSCANFORWARD)
 188   unsigned long result;
 189   _BitScanForward(&result, *x);
 190   *x >>= result;
 191 #else
 192   int result = 0;
 193   while ((*x & 1) == 0) {
 194     ++result;
 195     *x >>= 1;
 196   }
 197 #endif
 198   return (int)result;
 199 }
 200
 201
 202 /*
 203  * Initialize for a Huffman-compressed scan using progressive JPEG.
 204  */
 205
 206 METHODDEF(void)
 207 start_pass_phuff(j_compress_ptr cinfo, boolean gather_statistics)
 208 {
 209   phuff_entropy_ptr entropy = (phuff_entropy_ptr)cinfo->entropy;
 210   boolean is_DC_band;
 211   int ci, tbl;
 212   jpeg_component_info *compptr;
 213
 214   entropy->cinfo = cinfo;
 215   entropy->gather_statistics = gather_statistics;
 216
 217   is_DC_band = (cinfo->Ss == 0);
 218
 219   /* We assume jcmaster.c already validated the scan parameters. */
 220
 221   /* Select execution routines */
 222   if (cinfo->Ah == 0) {
 223     if (is_DC_band)
 224       entropy->pub.encode_mcu = encode_mcu_DC_first;
 225     else
 226       entropy->pub.encode_mcu = encode_mcu_AC_first;
 227     if (jsimd_can_encode_mcu_AC_first_prepare())
 228       entropy->AC_first_prepare = jsimd_encode_mcu_AC_first_prepare;
 229     else
 230       entropy->AC_first_prepare = encode_mcu_AC_first_prepare;
 231   } else {
 232     if (is_DC_band)
 233       entropy->pub.encode_mcu = encode_mcu_DC_refine;
 234     else {
 235       entropy->pub.encode_mcu = encode_mcu_AC_refine;
 236       if (jsimd_can_encode_mcu_AC_refine_prepare())
 237         entropy->AC_refine_prepare = jsimd_encode_mcu_AC_refine_prepare;
 238       else
 239         entropy->AC_refine_prepare = encode_mcu_AC_refine_prepare;
 240       /* AC refinement needs a correction bit buffer */
 241       if (entropy->bit_buffer == NULL)
 242         entropy->bit_buffer = (char *)
 243           (*cinfo->mem->alloc_small) ((j_common_ptr)cinfo, JPOOL_IMAGE,
 244                                       MAX_CORR_BITS * sizeof(char));
 245     }
 246   }
 247   if (gather_statistics)
 248     entropy->pub.finish_pass = finish_pass_gather_phuff;
 249   else
 250     entropy->pub.finish_pass = finish_pass_phuff;
 251
 252   /* Only DC coefficients may be interleaved, so cinfo->comps_in_scan = 1
 253    * for AC coefficients.
 254    */
 255   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
 256     compptr = cinfo->cur_comp_info[ci];
 257     /* Initialize DC predictions to 0 */
 258     entropy->last_dc_val[ci] = 0;
 259     /* Get table index */
 260     if (is_DC_band) {
 261       if (cinfo->Ah != 0)       /* DC refinement needs no table */
 262         continue;
 263       tbl = compptr->dc_tbl_no;
 264     } else {
 265       entropy->ac_tbl_no = tbl = compptr->ac_tbl_no;
 266     }
 267     if (gather_statistics) {
 268       /* Check for invalid table index */
 269       /* (make_c_derived_tbl does this in the other path) */
 270       if (tbl < 0 || tbl >= NUM_HUFF_TBLS)
 271         ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tbl);
 272       /* Allocate and zero the statistics tables */
 273       /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */
 274       if (entropy->count_ptrs[tbl] == NULL)
 275         entropy->count_ptrs[tbl] = (long *)
 276           (*cinfo->mem->alloc_small) ((j_common_ptr)cinfo, JPOOL_IMAGE,
 277                                       257 * sizeof(long));
 278       memset(entropy->count_ptrs[tbl], 0, 257 * sizeof(long));
 279     } else {
 280       /* Compute derived values for Huffman table */
 281       /* We may do this more than once for a table, but it's not expensive */
 282       jpeg_make_c_derived_tbl(cinfo, is_DC_band, tbl,
 283                               &entropy->derived_tbls[tbl]);
 284     }
 285   }
 286
 287   /* Initialize AC stuff */
 288   entropy->EOBRUN = 0;
 289   entropy->BE = 0;
 290
 291   /* Initialize bit buffer to empty */
 292   entropy->put_buffer = 0;
 293   entropy->put_bits = 0;
 294
 295   /* Initialize restart stuff */
 296   entropy->restarts_to_go = cinfo->restart_interval;
 297   entropy->next_restart_num = 0;
 298 }
 299
 300
 301 /* Outputting bytes to the file.
 302  * NB: these must be called only when actually outputting,
 303  * that is, entropy->gather_statistics == FALSE.
 304  */
 305
 306 /* Emit a byte */
 307 #define emit_byte(entropy, val) { \
 308   *(entropy)->next_output_byte++ = (JOCTET)(val); \
 309   if (--(entropy)->free_in_buffer == 0) \
 310     dump_buffer(entropy); \
 311 }
 312
 313
 314 LOCAL(void)
 315 dump_buffer(phuff_entropy_ptr entropy)
 316 /* Empty the output buffer; we do not support suspension in this module. */
 317 {
 318   struct jpeg_destination_mgr *dest = entropy->cinfo->dest;
 319
 320   if (!(*dest->empty_output_buffer) (entropy->cinfo))
 321     ERREXIT(entropy->cinfo, JERR_CANT_SUSPEND);
 322   /* After a successful buffer dump, must reset buffer pointers */
 323   entropy->next_output_byte = dest->next_output_byte;
 324   entropy->free_in_buffer = dest->free_in_buffer;
 325 }
 326
 327
 328 /* Outputting bits to the file */
 329
 330 /* Only the right 24 bits of put_buffer are used; the valid bits are
 331  * left-justified in this part.  At most 16 bits can be passed to emit_bits
 332  * in one call, and we never retain more than 7 bits in put_buffer
 333  * between calls, so 24 bits are sufficient.
 334  */
 335
 336 LOCAL(void)
 337 emit_bits(phuff_entropy_ptr entropy, unsigned int code, int size)
 338 /* Emit some bits, unless we are in gather mode */
 339 {
 340   /* This routine is heavily used, so it's worth coding tightly. */
 341   register size_t put_buffer = (size_t)code;
 342   register int put_bits = entropy->put_bits;
 343
 344   /* if size is 0, caller used an invalid Huffman table entry */
 345   if (size == 0)
 346     ERREXIT(entropy->cinfo, JERR_HUFF_MISSING_CODE);
 347
 348   if (entropy->gather_statistics)
 349     return;                     /* do nothing if we're only getting stats */
 350
 351   put_buffer &= (((size_t)1) << size) - 1; /* mask off any extra bits in code */
 352
 353   put_bits += size;             /* new number of bits in buffer */
 354
 355   put_buffer <<= 24 - put_bits; /* align incoming bits */
 356
 357   put_buffer |= entropy->put_buffer; /* and merge with old buffer contents */
 358
 359   while (put_bits >= 8) {
 360     int c = (int)((put_buffer >> 16) & 0xFF);
 361
 362     emit_byte(entropy, c);
 363     if (c == 0xFF) {            /* need to stuff a zero byte? */
 364       emit_byte(entropy, 0);
 365     }
 366     put_buffer <<= 8;
 367     put_bits -= 8;
 368   }
 369
 370   entropy->put_buffer = put_buffer; /* update variables */
 371   entropy->put_bits = put_bits;
 372 }
 373
 374
 375 LOCAL(void)
 376 flush_bits(phuff_entropy_ptr entropy)
 377 {
 378   emit_bits(entropy, 0x7F, 7); /* fill any partial byte with ones */
 379   entropy->put_buffer = 0;     /* and reset bit-buffer to empty */
 380   entropy->put_bits = 0;
 381 }
 382
 383
 384 /*
 385  * Emit (or just count) a Huffman symbol.
 386  */
 387
 388 LOCAL(void)
 389 emit_symbol(phuff_entropy_ptr entropy, int tbl_no, int symbol)
 390 {
 391   if (entropy->gather_statistics)
 392     entropy->count_ptrs[tbl_no][symbol]++;
 393   else {
 394     c_derived_tbl *tbl = entropy->derived_tbls[tbl_no];
 395     emit_bits(entropy, tbl->ehufco[symbol], tbl->ehufsi[symbol]);
 396   }
 397 }
 398
 399
 400 /*
 401  * Emit bits from a correction bit buffer.
 402  */
 403
 404 LOCAL(void)
 405 emit_buffered_bits(phuff_entropy_ptr entropy, char *bufstart,
 406                    unsigned int nbits)
 407 {
 408   if (entropy->gather_statistics)
 409     return;                     /* no real work */
 410
 411   while (nbits > 0) {
 412     emit_bits(entropy, (unsigned int)(*bufstart), 1);
 413     bufstart++;
 414     nbits--;
 415   }
 416 }
 417
 418
 419 /*
 420  * Emit any pending EOBRUN symbol.
 421  */
 422
 423 LOCAL(void)
 424 emit_eobrun(phuff_entropy_ptr entropy)
 425 {
 426   register int temp, nbits;
 427
 428   if (entropy->EOBRUN > 0) {    /* if there is any pending EOBRUN */
 429     temp = entropy->EOBRUN;
 430     nbits = JPEG_NBITS_NONZERO(temp) - 1;
 431     /* safety check: shouldn't happen given limited correction-bit buffer */
 432     if (nbits > 14)
 433       ERREXIT(entropy->cinfo, JERR_HUFF_MISSING_CODE);
 434
 435     emit_symbol(entropy, entropy->ac_tbl_no, nbits << 4);
 436     if (nbits)
 437       emit_bits(entropy, entropy->EOBRUN, nbits);
 438
 439     entropy->EOBRUN = 0;
 440
 441     /* Emit any buffered correction bits */
 442     emit_buffered_bits(entropy, entropy->bit_buffer, entropy->BE);
 443     entropy->BE = 0;
 444   }
 445 }
 446
 447
 448 /*
 449  * Emit a restart marker & resynchronize predictions.
 450  */
 451
 452 LOCAL(void)
 453 emit_restart(phuff_entropy_ptr entropy, int restart_num)
 454 {
 455   int ci;
 456
 457   emit_eobrun(entropy);
 458
 459   if (!entropy->gather_statistics) {
 460     flush_bits(entropy);
 461     emit_byte(entropy, 0xFF);
 462     emit_byte(entropy, JPEG_RST0 + restart_num);
 463   }
 464
 465   if (entropy->cinfo->Ss == 0) {
 466     /* Re-initialize DC predictions to 0 */
 467     for (ci = 0; ci < entropy->cinfo->comps_in_scan; ci++)
 468       entropy->last_dc_val[ci] = 0;
 469   } else {
 470     /* Re-initialize all AC-related fields to 0 */
 471     entropy->EOBRUN = 0;
 472     entropy->BE = 0;
 473   }
 474 }
 475
 476
 477 /*
 478  * MCU encoding for DC initial scan (either spectral selection,
 479  * or first pass of successive approximation).
 480  */
 481
 482 METHODDEF(boolean)
 483 encode_mcu_DC_first(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 484 {
 485   phuff_entropy_ptr entropy = (phuff_entropy_ptr)cinfo->entropy;
 486   register int temp, temp2, temp3;
 487   register int nbits;
 488   int blkn, ci;
 489   int Al = cinfo->Al;
 490   JBLOCKROW block;
 491   jpeg_component_info *compptr;
 492   ISHIFT_TEMPS
 493
 494   entropy->next_output_byte = cinfo->dest->next_output_byte;
 495   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
 496
 497   /* Emit restart marker if needed */
 498   if (cinfo->restart_interval)
 499     if (entropy->restarts_to_go == 0)
 500       emit_restart(entropy, entropy->next_restart_num);
 501
 502   /* Encode the MCU data blocks */
 503   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
 504     block = MCU_data[blkn];
 505     ci = cinfo->MCU_membership[blkn];
 506     compptr = cinfo->cur_comp_info[ci];
 507
 508     /* Compute the DC value after the required point transform by Al.
 509      * This is simply an arithmetic right shift.
 510      */
 511     temp2 = IRIGHT_SHIFT((int)((*block)[0]), Al);
 512
 513     /* DC differences are figured on the point-transformed values. */
 514     temp = temp2 - entropy->last_dc_val[ci];
 515     entropy->last_dc_val[ci] = temp2;
 516
 517     /* Encode the DC coefficient difference per section G.1.2.1 */
 518
 519     /* This is a well-known technique for obtaining the absolute value without
 520      * a branch.  It is derived from an assembly language technique presented
 521      * in "How to Optimize for the Pentium Processors", Copyright (c) 1996,
 522      * 1997 by Agner Fog.
 523      */
 524     temp3 = temp >> (CHAR_BIT * sizeof(int) - 1);
 525     temp ^= temp3;
 526     temp -= temp3;              /* temp is abs value of input */
 527     /* For a negative input, want temp2 = bitwise complement of abs(input) */
 528     temp2 = temp ^ temp3;
 529
 530     /* Find the number of bits needed for the magnitude of the coefficient */
 531     nbits = JPEG_NBITS(temp);
 532     /* Check for out-of-range coefficient values.
 533      * Since we're encoding a difference, the range limit is twice as much.
 534      */
 535     if (nbits > MAX_COEF_BITS + 1)
 536       ERREXIT(cinfo, JERR_BAD_DCT_COEF);
 537
 538     /* Count/emit the Huffman-coded symbol for the number of bits */
 539     emit_symbol(entropy, compptr->dc_tbl_no, nbits);
 540
 541     /* Emit that number of bits of the value, if positive, */
 542     /* or the complement of its magnitude, if negative. */
 543     if (nbits)                  /* emit_bits rejects calls with size 0 */
 544       emit_bits(entropy, (unsigned int)temp2, nbits);
 545   }
 546
 547   cinfo->dest->next_output_byte = entropy->next_output_byte;
 548   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
 549
 550   /* Update restart-interval state too */
 551   if (cinfo->restart_interval) {
 552     if (entropy->restarts_to_go == 0) {
 553       entropy->restarts_to_go = cinfo->restart_interval;
 554       entropy->next_restart_num++;
 555       entropy->next_restart_num &= 7;
 556     }
 557     entropy->restarts_to_go--;
 558   }
 559
 560   return TRUE;
 561 }
 562
 563
 564 /*
 565  * Data preparation for encode_mcu_AC_first().
 566  */
 567
 568 #define COMPUTE_ABSVALUES_AC_FIRST(Sl) { \
 569   for (k = 0; k < Sl; k++) { \
 570     temp = block[jpeg_natural_order_start[k]]; \
 571     if (temp == 0) \
 572       continue; \
 573     /* We must apply the point transform by Al.  For AC coefficients this \
 574      * is an integer division with rounding towards 0.  To do this portably \
 575      * in C, we shift after obtaining the absolute value; so the code is \
 576      * interwoven with finding the abs value (temp) and output bits (temp2). \
 577      */ \
 578     temp2 = temp >> (CHAR_BIT * sizeof(int) - 1); \
 579     temp ^= temp2; \
 580     temp -= temp2;              /* temp is abs value of input */ \
 581     temp >>= Al;                /* apply the point transform */ \
 582     /* Watch out for case that nonzero coef is zero after point transform */ \
 583     if (temp == 0) \
 584       continue; \
 585     /* For a negative coef, want temp2 = bitwise complement of abs(coef) */ \
 586     temp2 ^= temp; \
 587     values[k] = (JCOEF)temp; \
 588     values[k + DCTSIZE2] = (JCOEF)temp2; \
 589     zerobits |= ((size_t)1U) << k; \
 590   } \
 591 }
 592
 593 METHODDEF(void)
 594 encode_mcu_AC_first_prepare(const JCOEF *block,
 595                             const int *jpeg_natural_order_start, int Sl,
 596                             int Al, JCOEF *values, size_t *bits)
 597 {
 598   register int k, temp, temp2;
 599   size_t zerobits = 0U;
 600   int Sl0 = Sl;
 601
 602 #if SIZEOF_SIZE_T == 4
 603   if (Sl0 > 32)
 604     Sl0 = 32;
 605 #endif
 606
 607   COMPUTE_ABSVALUES_AC_FIRST(Sl0);
 608
 609   bits[0] = zerobits;
 610 #if SIZEOF_SIZE_T == 4
 611   zerobits = 0U;
 612
 613   if (Sl > 32) {
 614     Sl -= 32;
 615     jpeg_natural_order_start += 32;
 616     values += 32;
 617
 618     COMPUTE_ABSVALUES_AC_FIRST(Sl);
 619   }
 620   bits[1] = zerobits;
 621 #endif
 622 }
 623
 624 /*
 625  * MCU encoding for AC initial scan (either spectral selection,
 626  * or first pass of successive approximation).
 627  */
 628
 629 #define ENCODE_COEFS_AC_FIRST(label) { \
 630   while (zerobits) { \
 631     r = count_zeroes(&zerobits); \
 632     cvalue += r; \
 633 label \
 634     temp  = cvalue[0]; \
 635     temp2 = cvalue[DCTSIZE2]; \
 636     \
 637     /* if run length > 15, must emit special run-length-16 codes (0xF0) */ \
 638     while (r > 15) { \
 639       emit_symbol(entropy, entropy->ac_tbl_no, 0xF0); \
 640       r -= 16; \
 641     } \
 642     \
 643     /* Find the number of bits needed for the magnitude of the coefficient */ \
 644     nbits = JPEG_NBITS_NONZERO(temp);  /* there must be at least one 1 bit */ \
 645     /* Check for out-of-range coefficient values */ \
 646     if (nbits > MAX_COEF_BITS) \
 647       ERREXIT(cinfo, JERR_BAD_DCT_COEF); \
 648     \
 649     /* Count/emit Huffman symbol for run length / number of bits */ \
 650     emit_symbol(entropy, entropy->ac_tbl_no, (r << 4) + nbits); \
 651     \
 652     /* Emit that number of bits of the value, if positive, */ \
 653     /* or the complement of its magnitude, if negative. */ \
 654     emit_bits(entropy, (unsigned int)temp2, nbits); \
 655     \
 656     cvalue++; \
 657     zerobits >>= 1; \
 658   } \
 659 }
 660
 661 METHODDEF(boolean)
 662 encode_mcu_AC_first(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 663 {
 664   phuff_entropy_ptr entropy = (phuff_entropy_ptr)cinfo->entropy;
 665   register int temp, temp2;
 666   register int nbits, r;
 667   int Sl = cinfo->Se - cinfo->Ss + 1;
 668   int Al = cinfo->Al;
 669   JCOEF values_unaligned[2 * DCTSIZE2 + 15];
 670   JCOEF *values;
 671   const JCOEF *cvalue;
 672   size_t zerobits;
 673   size_t bits[8 / SIZEOF_SIZE_T];
 674
 675   entropy->next_output_byte = cinfo->dest->next_output_byte;
 676   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
 677
 678   /* Emit restart marker if needed */
 679   if (cinfo->restart_interval)
 680     if (entropy->restarts_to_go == 0)
 681       emit_restart(entropy, entropy->next_restart_num);
 682
 683 #ifdef WITH_SIMD
 684   cvalue = values = (JCOEF *)PAD((JUINTPTR)values_unaligned, 16);
 685 #else
 686   /* Not using SIMD, so alignment is not needed */
 687   cvalue = values = values_unaligned;
 688 #endif
 689
 690   /* Prepare data */
 691   entropy->AC_first_prepare(MCU_data[0][0], jpeg_natural_order + cinfo->Ss,
 692                             Sl, Al, values, bits);
 693
 694   zerobits = bits[0];
 695 #if SIZEOF_SIZE_T == 4
 696   zerobits |= bits[1];
 697 #endif
 698
 699   /* Emit any pending EOBRUN */
 700   if (zerobits && (entropy->EOBRUN > 0))
 701     emit_eobrun(entropy);
 702
 703 #if SIZEOF_SIZE_T == 4
 704   zerobits = bits[0];
 705 #endif
 706
 707   /* Encode the AC coefficients per section G.1.2.2, fig. G.3 */
 708
 709   ENCODE_COEFS_AC_FIRST((void)0;);
 710
 711 #if SIZEOF_SIZE_T == 4
 712   zerobits = bits[1];
 713   if (zerobits) {
 714     int diff = ((values + DCTSIZE2 / 2) - cvalue);
 715     r = count_zeroes(&zerobits);
 716     r += diff;
 717     cvalue += r;
 718     goto first_iter_ac_first;
 719   }
 720
 721   ENCODE_COEFS_AC_FIRST(first_iter_ac_first:);
 722 #endif
 723
 724   if (cvalue < (values + Sl)) { /* If there are trailing zeroes, */
 725     entropy->EOBRUN++;          /* count an EOB */
 726     if (entropy->EOBRUN == 0x7FFF)
 727       emit_eobrun(entropy);     /* force it out to avoid overflow */
 728   }
 729
 730   cinfo->dest->next_output_byte = entropy->next_output_byte;
 731   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
 732
 733   /* Update restart-interval state too */
 734   if (cinfo->restart_interval) {
 735     if (entropy->restarts_to_go == 0) {
 736       entropy->restarts_to_go = cinfo->restart_interval;
 737       entropy->next_restart_num++;
 738       entropy->next_restart_num &= 7;
 739     }
 740     entropy->restarts_to_go--;
 741   }
 742
 743   return TRUE;
 744 }
 745
 746
 747 /*
 748  * MCU encoding for DC successive approximation refinement scan.
 749  * Note: we assume such scans can be multi-component, although the spec
 750  * is not very clear on the point.
 751  */
 752
 753 METHODDEF(boolean)
 754 encode_mcu_DC_refine(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 755 {
 756   phuff_entropy_ptr entropy = (phuff_entropy_ptr)cinfo->entropy;
 757   register int temp;
 758   int blkn;
 759   int Al = cinfo->Al;
 760   JBLOCKROW block;
 761
 762   entropy->next_output_byte = cinfo->dest->next_output_byte;
 763   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
 764
 765   /* Emit restart marker if needed */
 766   if (cinfo->restart_interval)
 767     if (entropy->restarts_to_go == 0)
 768       emit_restart(entropy, entropy->next_restart_num);
 769
 770   /* Encode the MCU data blocks */
 771   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
 772     block = MCU_data[blkn];
 773
 774     /* We simply emit the Al'th bit of the DC coefficient value. */
 775     temp = (*block)[0];
 776     emit_bits(entropy, (unsigned int)(temp >> Al), 1);
 777   }
 778
 779   cinfo->dest->next_output_byte = entropy->next_output_byte;
 780   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
 781
 782   /* Update restart-interval state too */
 783   if (cinfo->restart_interval) {
 784     if (entropy->restarts_to_go == 0) {
 785       entropy->restarts_to_go = cinfo->restart_interval;
 786       entropy->next_restart_num++;
 787       entropy->next_restart_num &= 7;
 788     }
 789     entropy->restarts_to_go--;
 790   }
 791
 792   return TRUE;
 793 }
 794
 795
 796 /*
 797  * Data preparation for encode_mcu_AC_refine().
 798  */
 799
 800 #define COMPUTE_ABSVALUES_AC_REFINE(Sl, koffset) { \
 801   /* It is convenient to make a pre-pass to determine the transformed \
 802    * coefficients' absolute values and the EOB position. \
 803    */ \
 804   for (k = 0; k < Sl; k++) { \
 805     temp = block[jpeg_natural_order_start[k]]; \
 806     /* We must apply the point transform by Al.  For AC coefficients this \
 807      * is an integer division with rounding towards 0.  To do this portably \
 808      * in C, we shift after obtaining the absolute value. \
 809      */ \
 810     temp2 = temp >> (CHAR_BIT * sizeof(int) - 1); \
 811     temp ^= temp2; \
 812     temp -= temp2;              /* temp is abs value of input */ \
 813     temp >>= Al;                /* apply the point transform */ \
 814     if (temp != 0) { \
 815       zerobits |= ((size_t)1U) << k; \
 816       signbits |= ((size_t)(temp2 + 1)) << k; \
 817     } \
 818     absvalues[k] = (JCOEF)temp; /* save abs value for main pass */ \
 819     if (temp == 1) \
 820       EOB = k + koffset;        /* EOB = index of last newly-nonzero coef */ \
 821   } \
 822 }
 823
 824 METHODDEF(int)
 825 encode_mcu_AC_refine_prepare(const JCOEF *block,
 826                              const int *jpeg_natural_order_start, int Sl,
 827                              int Al, JCOEF *absvalues, size_t *bits)
 828 {
 829   register int k, temp, temp2;
 830   int EOB = 0;
 831   size_t zerobits = 0U, signbits = 0U;
 832   int Sl0 = Sl;
 833
 834 #if SIZEOF_SIZE_T == 4
 835   if (Sl0 > 32)
 836     Sl0 = 32;
 837 #endif
 838
 839   COMPUTE_ABSVALUES_AC_REFINE(Sl0, 0);
 840
 841   bits[0] = zerobits;
 842 #if SIZEOF_SIZE_T == 8
 843   bits[1] = signbits;
 844 #else
 845   bits[2] = signbits;
 846
 847   zerobits = 0U;
 848   signbits = 0U;
 849
 850   if (Sl > 32) {
 851     Sl -= 32;
 852     jpeg_natural_order_start += 32;
 853     absvalues += 32;
 854
 855     COMPUTE_ABSVALUES_AC_REFINE(Sl, 32);
 856   }
 857
 858   bits[1] = zerobits;
 859   bits[3] = signbits;
 860 #endif
 861
 862   return EOB;
 863 }
 864
 865
 866 /*
 867  * MCU encoding for AC successive approximation refinement scan.
 868  */
 869
 870 #define ENCODE_COEFS_AC_REFINE(label) { \
 871   while (zerobits) { \
 872     idx = count_zeroes(&zerobits); \
 873     r += idx; \
 874     cabsvalue += idx; \
 875     signbits >>= idx; \
 876 label \
 877     /* Emit any required ZRLs, but not if they can be folded into EOB */ \
 878     while (r > 15 && (cabsvalue <= EOBPTR)) { \
 879       /* emit any pending EOBRUN and the BE correction bits */ \
 880       emit_eobrun(entropy); \
 881       /* Emit ZRL */ \
 882       emit_symbol(entropy, entropy->ac_tbl_no, 0xF0); \
 883       r -= 16; \
 884       /* Emit buffered correction bits that must be associated with ZRL */ \
 885       emit_buffered_bits(entropy, BR_buffer, BR); \
 886       BR_buffer = entropy->bit_buffer; /* BE bits are gone now */ \
 887       BR = 0; \
 888     } \
 889     \
 890     temp = *cabsvalue++; \
 891     \
 892     /* If the coef was previously nonzero, it only needs a correction bit. \
 893      * NOTE: a straight translation of the spec's figure G.7 would suggest \
 894      * that we also need to test r > 15.  But if r > 15, we can only get here \
 895      * if k > EOB, which implies that this coefficient is not 1. \
 896      */ \
 897     if (temp > 1) { \
 898       /* The correction bit is the next bit of the absolute value. */ \
 899       BR_buffer[BR++] = (char)(temp & 1); \
 900       signbits >>= 1; \
 901       zerobits >>= 1; \
 902       continue; \
 903     } \
 904     \
 905     /* Emit any pending EOBRUN and the BE correction bits */ \
 906     emit_eobrun(entropy); \
 907     \
 908     /* Count/emit Huffman symbol for run length / number of bits */ \
 909     emit_symbol(entropy, entropy->ac_tbl_no, (r << 4) + 1); \
 910     \
 911     /* Emit output bit for newly-nonzero coef */ \
 912     temp = signbits & 1; /* ((*block)[jpeg_natural_order_start[k]] < 0) ? 0 : 1 */ \
 913     emit_bits(entropy, (unsigned int)temp, 1); \
 914     \
 915     /* Emit buffered correction bits that must be associated with this code */ \
 916     emit_buffered_bits(entropy, BR_buffer, BR); \
 917     BR_buffer = entropy->bit_buffer; /* BE bits are gone now */ \
 918     BR = 0; \
 919     r = 0;                      /* reset zero run length */ \
 920     signbits >>= 1; \
 921     zerobits >>= 1; \
 922   } \
 923 }
 924
 925 METHODDEF(boolean)
 926 encode_mcu_AC_refine(j_compress_ptr cinfo, JBLOCKROW *MCU_data)
 927 {
 928   phuff_entropy_ptr entropy = (phuff_entropy_ptr)cinfo->entropy;
 929   register int temp, r, idx;
 930   char *BR_buffer;
 931   unsigned int BR;
 932   int Sl = cinfo->Se - cinfo->Ss + 1;
 933   int Al = cinfo->Al;
 934   JCOEF absvalues_unaligned[DCTSIZE2 + 15];
 935   JCOEF *absvalues;
 936   const JCOEF *cabsvalue, *EOBPTR;
 937   size_t zerobits, signbits;
 938   size_t bits[16 / SIZEOF_SIZE_T];
 939
 940   entropy->next_output_byte = cinfo->dest->next_output_byte;
 941   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
 942
 943   /* Emit restart marker if needed */
 944   if (cinfo->restart_interval)
 945     if (entropy->restarts_to_go == 0)
 946       emit_restart(entropy, entropy->next_restart_num);
 947
 948 #ifdef WITH_SIMD
 949   cabsvalue = absvalues = (JCOEF *)PAD((JUINTPTR)absvalues_unaligned, 16);
 950 #else
 951   /* Not using SIMD, so alignment is not needed */
 952   cabsvalue = absvalues = absvalues_unaligned;
 953 #endif
 954
 955   /* Prepare data */
 956   EOBPTR = absvalues +
 957     entropy->AC_refine_prepare(MCU_data[0][0], jpeg_natural_order + cinfo->Ss,
 958                                Sl, Al, absvalues, bits);
 959
 960   /* Encode the AC coefficients per section G.1.2.3, fig. G.7 */
 961
 962   r = 0;                        /* r = run length of zeros */
 963   BR = 0;                       /* BR = count of buffered bits added now */
 964   BR_buffer = entropy->bit_buffer + entropy->BE; /* Append bits to buffer */
 965
 966   zerobits = bits[0];
 967 #if SIZEOF_SIZE_T == 8
 968   signbits = bits[1];
 969 #else
 970   signbits = bits[2];
 971 #endif
 972   ENCODE_COEFS_AC_REFINE((void)0;);
 973
 974 #if SIZEOF_SIZE_T == 4
 975   zerobits = bits[1];
 976   signbits = bits[3];
 977
 978   if (zerobits) {
 979     int diff = ((absvalues + DCTSIZE2 / 2) - cabsvalue);
 980     idx = count_zeroes(&zerobits);
 981     signbits >>= idx;
 982     idx += diff;
 983     r += idx;
 984     cabsvalue += idx;
 985     goto first_iter_ac_refine;
 986   }
 987
 988   ENCODE_COEFS_AC_REFINE(first_iter_ac_refine:);
 989 #endif
 990
 991   r |= (int)((absvalues + Sl) - cabsvalue);
 992
 993   if (r > 0 || BR > 0) {        /* If there are trailing zeroes, */
 994     entropy->EOBRUN++;          /* count an EOB */
 995     entropy->BE += BR;          /* concat my correction bits to older ones */
 996     /* We force out the EOB if we risk either:
 997      * 1. overflow of the EOB counter;
 998      * 2. overflow of the correction bit buffer during the next MCU.
 999      */
1000     if (entropy->EOBRUN == 0x7FFF ||
1001         entropy->BE > (MAX_CORR_BITS - DCTSIZE2 + 1))
1002       emit_eobrun(entropy);
1003   }
1004
1005   cinfo->dest->next_output_byte = entropy->next_output_byte;
1006   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
1007
1008   /* Update restart-interval state too */
1009   if (cinfo->restart_interval) {
1010     if (entropy->restarts_to_go == 0) {
1011       entropy->restarts_to_go = cinfo->restart_interval;
1012       entropy->next_restart_num++;
1013       entropy->next_restart_num &= 7;
1014     }
1015     entropy->restarts_to_go--;
1016   }
1017
1018   return TRUE;
1019 }
1020
1021
1022 /*
1023  * Finish up at the end of a Huffman-compressed progressive scan.
1024  */
1025
1026 METHODDEF(void)
1027 finish_pass_phuff(j_compress_ptr cinfo)
1028 {
1029   phuff_entropy_ptr entropy = (phuff_entropy_ptr)cinfo->entropy;
1030
1031   entropy->next_output_byte = cinfo->dest->next_output_byte;
1032   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
1033
1034   /* Flush out any buffered data */
1035   emit_eobrun(entropy);
1036   flush_bits(entropy);
1037
1038   cinfo->dest->next_output_byte = entropy->next_output_byte;
1039   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
1040 }
1041
1042
1043 /*
1044  * Finish up a statistics-gathering pass and create the new Huffman tables.
1045  */
1046
1047 METHODDEF(void)
1048 finish_pass_gather_phuff(j_compress_ptr cinfo)
1049 {
1050   phuff_entropy_ptr entropy = (phuff_entropy_ptr)cinfo->entropy;
1051   boolean is_DC_band;
1052   int ci, tbl;
1053   jpeg_component_info *compptr;
1054   JHUFF_TBL **htblptr;
1055   boolean did[NUM_HUFF_TBLS];
1056
1057   /* Flush out buffered data (all we care about is counting the EOB symbol) */
1058   emit_eobrun(entropy);
1059
1060   is_DC_band = (cinfo->Ss == 0);
1061
1062   /* It's important not to apply jpeg_gen_optimal_table more than once
1063    * per table, because it clobbers the input frequency counts!
1064    */
1065   memset(did, 0, sizeof(did));
1066
1067   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
1068     compptr = cinfo->cur_comp_info[ci];
1069     if (is_DC_band) {
1070       if (cinfo->Ah != 0)       /* DC refinement needs no table */
1071         continue;
1072       tbl = compptr->dc_tbl_no;
1073     } else {
1074       tbl = compptr->ac_tbl_no;
1075     }
1076     if (!did[tbl]) {
1077       if (is_DC_band)
1078         htblptr = &cinfo->dc_huff_tbl_ptrs[tbl];
1079       else
1080         htblptr = &cinfo->ac_huff_tbl_ptrs[tbl];
1081       if (*htblptr == NULL)
1082         *htblptr = jpeg_alloc_huff_table((j_common_ptr)cinfo);
1083       jpeg_gen_optimal_table(cinfo, *htblptr, entropy->count_ptrs[tbl]);
1084       did[tbl] = TRUE;
1085     }
1086   }
1087 }
1088
1089
1090 /*
1091  * Module initialization routine for progressive Huffman entropy encoding.
1092  */
1093
1094 GLOBAL(void)
1095 jinit_phuff_encoder(j_compress_ptr cinfo)
1096 {
1097   phuff_entropy_ptr entropy;
1098   int i;
1099
1100   entropy = (phuff_entropy_ptr)
1101     (*cinfo->mem->alloc_small) ((j_common_ptr)cinfo, JPOOL_IMAGE,
1102                                 sizeof(phuff_entropy_encoder));
1103   cinfo->entropy = (struct jpeg_entropy_encoder *)entropy;
1104   entropy->pub.start_pass = start_pass_phuff;
1105
1106   /* Mark tables unallocated */
1107   for (i = 0; i < NUM_HUFF_TBLS; i++) {
1108     entropy->derived_tbls[i] = NULL;
1109     entropy->count_ptrs[i] = NULL;
1110   }
1111   entropy->bit_buffer = NULL;   /* needed only in AC refinement scan */
1112 }
1113
1114 #endif /* C_PROGRESSIVE_SUPPORTED */