Coverage Report

Created: 2024-07-27 06:27

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