jdk

1
/*
2
 * reserved comment block
3
 * DO NOT REMOVE OR ALTER!
4
 */
5
/*
6
 * jcphuff.c
7
 *
8
 * Copyright (C) 1995-1997, Thomas G. Lane.
9
 * This file is part of the Independent JPEG Group's software.
10
 * For conditions of distribution and use, see the accompanying README file.
11
 *
12
 * This file contains Huffman entropy encoding routines for progressive JPEG.
13
 *
14
 * We do not support output suspension in this module, since the library
15
 * currently does not allow multiple-scan files to be written with output
16
 * suspension.
17
 */
18

19
#define JPEG_INTERNALS
20
#include "jinclude.h"
21
#include "jpeglib.h"
22
#include "jchuff.h"             /* Declarations shared with jchuff.c */
23

24
#ifdef C_PROGRESSIVE_SUPPORTED
25

26
/* Expanded entropy encoder object for progressive Huffman encoding. */
27

28
typedef struct {
29
  struct jpeg_entropy_encoder pub; /* public fields */
30

31
  /* Mode flag: TRUE for optimization, FALSE for actual data output */
32
  boolean gather_statistics;
33

34
  /* Bit-level coding status.
35
   * next_output_byte/free_in_buffer are local copies of cinfo->dest fields.
36
   */
37
  JOCTET * next_output_byte;    /* => next byte to write in buffer */
38
  size_t free_in_buffer;        /* # of byte spaces remaining in buffer */
39
  INT32 put_buffer;             /* current bit-accumulation buffer */
40
  int put_bits;                 /* # of bits now in it */
41
  j_compress_ptr cinfo;         /* link to cinfo (needed for dump_buffer) */
42

43
  /* Coding status for DC components */
44
  int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
45

46
  /* Coding status for AC components */
47
  int ac_tbl_no;                /* the table number of the single component */
48
  unsigned int EOBRUN;          /* run length of EOBs */
49
  unsigned int BE;              /* # of buffered correction bits before MCU */
50
  char * bit_buffer;            /* buffer for correction bits (1 per char) */
51
  /* packing correction bits tightly would save some space but cost time... */
52

53
  unsigned int restarts_to_go;  /* MCUs left in this restart interval */
54
  int next_restart_num;         /* next restart number to write (0-7) */
55

56
  /* Pointers to derived tables (these workspaces have image lifespan).
57
   * Since any one scan codes only DC or only AC, we only need one set
58
   * of tables, not one for DC and one for AC.
59
   */
60
  c_derived_tbl * derived_tbls[NUM_HUFF_TBLS];
61

62
  /* Statistics tables for optimization; again, one set is enough */
63
  long * count_ptrs[NUM_HUFF_TBLS];
64
} phuff_entropy_encoder;
65

66
typedef phuff_entropy_encoder * phuff_entropy_ptr;
67

68
/* MAX_CORR_BITS is the number of bits the AC refinement correction-bit
69
 * buffer can hold.  Larger sizes may slightly improve compression, but
70
 * 1000 is already well into the realm of overkill.
71
 * The minimum safe size is 64 bits.
72
 */
73

74
#define MAX_CORR_BITS  1000     /* Max # of correction bits I can buffer */
75

76
/* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than INT32.
77
 * We assume that int right shift is unsigned if INT32 right shift is,
78
 * which should be safe.
79
 */
80

81
#ifdef RIGHT_SHIFT_IS_UNSIGNED
82
#define ISHIFT_TEMPS    int ishift_temp;
83
#define IRIGHT_SHIFT(x,shft)  \
84
        ((ishift_temp = (x)) < 0 ? \
85
         (ishift_temp >> (shft)) | ((~0) << (16-(shft))) : \
86
         (ishift_temp >> (shft)))
87
#else
88
#define ISHIFT_TEMPS
89
#define IRIGHT_SHIFT(x,shft)    ((x) >> (shft))
90
#endif
91

92
/* Forward declarations */
93
METHODDEF(boolean) encode_mcu_DC_first JPP((j_compress_ptr cinfo,
94
                                            JBLOCKROW *MCU_data));
95
METHODDEF(boolean) encode_mcu_AC_first JPP((j_compress_ptr cinfo,
96
                                            JBLOCKROW *MCU_data));
97
METHODDEF(boolean) encode_mcu_DC_refine JPP((j_compress_ptr cinfo,
98
                                             JBLOCKROW *MCU_data));
99
METHODDEF(boolean) encode_mcu_AC_refine JPP((j_compress_ptr cinfo,
100
                                             JBLOCKROW *MCU_data));
101
METHODDEF(void) finish_pass_phuff JPP((j_compress_ptr cinfo));
102
METHODDEF(void) finish_pass_gather_phuff JPP((j_compress_ptr cinfo));
103

104

105
/*
106
 * Initialize for a Huffman-compressed scan using progressive JPEG.
107
 */
108

109
METHODDEF(void)
110
start_pass_phuff (j_compress_ptr cinfo, boolean gather_statistics)
111
{
112
  phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
113
  boolean is_DC_band;
114
  int ci, tbl;
115
  jpeg_component_info * compptr;
116

117
  entropy->cinfo = cinfo;
118
  entropy->gather_statistics = gather_statistics;
119

120
  is_DC_band = (cinfo->Ss == 0);
121

122
  /* We assume jcmaster.c already validated the scan parameters. */
123

124
  /* Select execution routines */
125
  if (cinfo->Ah == 0) {
126
    if (is_DC_band)
127
      entropy->pub.encode_mcu = encode_mcu_DC_first;
128
    else
129
      entropy->pub.encode_mcu = encode_mcu_AC_first;
130
  } else {
131
    if (is_DC_band)
132
      entropy->pub.encode_mcu = encode_mcu_DC_refine;
133
    else {
134
      entropy->pub.encode_mcu = encode_mcu_AC_refine;
135
      /* AC refinement needs a correction bit buffer */
136
      if (entropy->bit_buffer == NULL)
137
        entropy->bit_buffer = (char *)
138
          (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
139
                                      MAX_CORR_BITS * SIZEOF(char));
140
    }
141
  }
142
  if (gather_statistics)
143
    entropy->pub.finish_pass = finish_pass_gather_phuff;
144
  else
145
    entropy->pub.finish_pass = finish_pass_phuff;
146

147
  /* Only DC coefficients may be interleaved, so cinfo->comps_in_scan = 1
148
   * for AC coefficients.
149
   */
150
  for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
151
    compptr = cinfo->cur_comp_info[ci];
152
    /* Initialize DC predictions to 0 */
153
    entropy->last_dc_val[ci] = 0;
154
    /* Get table index */
155
    if (is_DC_band) {
156
      if (cinfo->Ah != 0)       /* DC refinement needs no table */
157
        continue;
158
      tbl = compptr->dc_tbl_no;
159
    } else {
160
      entropy->ac_tbl_no = tbl = compptr->ac_tbl_no;
161
    }
162
    if (gather_statistics) {
163
      /* Check for invalid table index */
164
      /* (make_c_derived_tbl does this in the other path) */
165
      if (tbl < 0 || tbl >= NUM_HUFF_TBLS)
166
        ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tbl);
167
      /* Allocate and zero the statistics tables */
168
      /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */
169
      if (entropy->count_ptrs[tbl] == NULL)
170
        entropy->count_ptrs[tbl] = (long *)
171
          (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
172
                                      257 * SIZEOF(long));
173
      MEMZERO(entropy->count_ptrs[tbl], 257 * SIZEOF(long));
174
    } else {
175
      /* Compute derived values for Huffman table */
176
      /* We may do this more than once for a table, but it's not expensive */
177
      jpeg_make_c_derived_tbl(cinfo, is_DC_band, tbl,
178
                              & entropy->derived_tbls[tbl]);
179
    }
180
  }
181

182
  /* Initialize AC stuff */
183
  entropy->EOBRUN = 0;
184
  entropy->BE = 0;
185

186
  /* Initialize bit buffer to empty */
187
  entropy->put_buffer = 0;
188
  entropy->put_bits = 0;
189

190
  /* Initialize restart stuff */
191
  entropy->restarts_to_go = cinfo->restart_interval;
192
  entropy->next_restart_num = 0;
193
}
194

195

196
/* Outputting bytes to the file.
197
 * NB: these must be called only when actually outputting,
198
 * that is, entropy->gather_statistics == FALSE.
199
 */
200

201
/* Emit a byte */
202
#define emit_byte(entropy,val)  \
203
        { *(entropy)->next_output_byte++ = (JOCTET) (val);  \
204
          if (--(entropy)->free_in_buffer == 0)  \
205
            dump_buffer(entropy); }
206

207

208
LOCAL(void)
209
dump_buffer (phuff_entropy_ptr entropy)
210
/* Empty the output buffer; we do not support suspension in this module. */
211
{
212
  struct jpeg_destination_mgr * dest = entropy->cinfo->dest;
213

214
  if (! (*dest->empty_output_buffer) (entropy->cinfo))
215
    ERREXIT(entropy->cinfo, JERR_CANT_SUSPEND);
216
  /* After a successful buffer dump, must reset buffer pointers */
217
  entropy->next_output_byte = dest->next_output_byte;
218
  entropy->free_in_buffer = dest->free_in_buffer;
219
}
220

221

222
/* Outputting bits to the file */
223

224
/* Only the right 24 bits of put_buffer are used; the valid bits are
225
 * left-justified in this part.  At most 16 bits can be passed to emit_bits
226
 * in one call, and we never retain more than 7 bits in put_buffer
227
 * between calls, so 24 bits are sufficient.
228
 */
229

230
INLINE
231
LOCAL(void)
232
emit_bits (phuff_entropy_ptr entropy, unsigned int code, int size)
233
/* Emit some bits, unless we are in gather mode */
234
{
235
  /* This routine is heavily used, so it's worth coding tightly. */
236
  register INT32 put_buffer = (INT32) code;
237
  register int put_bits = entropy->put_bits;
238

239
  /* if size is 0, caller used an invalid Huffman table entry */
240
  if (size == 0)
241
    ERREXIT(entropy->cinfo, JERR_HUFF_MISSING_CODE);
242

243
  if (entropy->gather_statistics)
244
    return;                     /* do nothing if we're only getting stats */
245

246
  put_buffer &= (((INT32) 1)<<size) - 1; /* mask off any extra bits in code */
247

248
  put_bits += size;             /* new number of bits in buffer */
249

250
  put_buffer <<= 24 - put_bits; /* align incoming bits */
251

252
  put_buffer |= entropy->put_buffer; /* and merge with old buffer contents */
253

254
  while (put_bits >= 8) {
255
    int c = (int) ((put_buffer >> 16) & 0xFF);
256

257
    emit_byte(entropy, c);
258
    if (c == 0xFF) {            /* need to stuff a zero byte? */
259
      emit_byte(entropy, 0);
260
    }
261
    put_buffer <<= 8;
262
    put_bits -= 8;
263
  }
264

265
  entropy->put_buffer = put_buffer; /* update variables */
266
  entropy->put_bits = put_bits;
267
}
268

269

270
LOCAL(void)
271
flush_bits (phuff_entropy_ptr entropy)
272
{
273
  emit_bits(entropy, 0x7F, 7); /* fill any partial byte with ones */
274
  entropy->put_buffer = 0;     /* and reset bit-buffer to empty */
275
  entropy->put_bits = 0;
276
}
277

278

279
/*
280
 * Emit (or just count) a Huffman symbol.
281
 */
282

283
INLINE
284
LOCAL(void)
285
emit_symbol (phuff_entropy_ptr entropy, int tbl_no, int symbol)
286
{
287
  if (entropy->gather_statistics)
288
    entropy->count_ptrs[tbl_no][symbol]++;
289
  else {
290
    c_derived_tbl * tbl = entropy->derived_tbls[tbl_no];
291
    emit_bits(entropy, tbl->ehufco[symbol], tbl->ehufsi[symbol]);
292
  }
293
}
294

295

296
/*
297
 * Emit bits from a correction bit buffer.
298
 */
299

300
LOCAL(void)
301
emit_buffered_bits (phuff_entropy_ptr entropy, char * bufstart,
302
                    unsigned int nbits)
303
{
304
  if (entropy->gather_statistics)
305
    return;                     /* no real work */
306

307
  while (nbits > 0) {
308
    emit_bits(entropy, (unsigned int) (*bufstart), 1);
309
    bufstart++;
310
    nbits--;
311
  }
312
}
313

314

315
/*
316
 * Emit any pending EOBRUN symbol.
317
 */
318

319
LOCAL(void)
320
emit_eobrun (phuff_entropy_ptr entropy)
321
{
322
  register int temp, nbits;
323

324
  if (entropy->EOBRUN > 0) {    /* if there is any pending EOBRUN */
325
    temp = entropy->EOBRUN;
326
    nbits = 0;
327
    while ((temp >>= 1))
328
      nbits++;
329
    /* safety check: shouldn't happen given limited correction-bit buffer */
330
    if (nbits > 14)
331
      ERREXIT(entropy->cinfo, JERR_HUFF_MISSING_CODE);
332

333
    emit_symbol(entropy, entropy->ac_tbl_no, nbits << 4);
334
    if (nbits)
335
      emit_bits(entropy, entropy->EOBRUN, nbits);
336

337
    entropy->EOBRUN = 0;
338

339
    /* Emit any buffered correction bits */
340
    emit_buffered_bits(entropy, entropy->bit_buffer, entropy->BE);
341
    entropy->BE = 0;
342
  }
343
}
344

345

346
/*
347
 * Emit a restart marker & resynchronize predictions.
348
 */
349

350
LOCAL(void)
351
emit_restart (phuff_entropy_ptr entropy, int restart_num)
352
{
353
  int ci;
354

355
  emit_eobrun(entropy);
356

357
  if (! entropy->gather_statistics) {
358
    flush_bits(entropy);
359
    emit_byte(entropy, 0xFF);
360
    emit_byte(entropy, JPEG_RST0 + restart_num);
361
  }
362

363
  if (entropy->cinfo->Ss == 0) {
364
    /* Re-initialize DC predictions to 0 */
365
    for (ci = 0; ci < entropy->cinfo->comps_in_scan; ci++)
366
      entropy->last_dc_val[ci] = 0;
367
  } else {
368
    /* Re-initialize all AC-related fields to 0 */
369
    entropy->EOBRUN = 0;
370
    entropy->BE = 0;
371
  }
372
}
373

374

375
/*
376
 * MCU encoding for DC initial scan (either spectral selection,
377
 * or first pass of successive approximation).
378
 */
379

380
METHODDEF(boolean)
381
encode_mcu_DC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
382
{
383
  phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
384
  register int temp, temp2;
385
  register int nbits;
386
  int blkn, ci;
387
  int Al = cinfo->Al;
388
  JBLOCKROW block;
389
  jpeg_component_info * compptr;
390
  ISHIFT_TEMPS
391

392
  entropy->next_output_byte = cinfo->dest->next_output_byte;
393
  entropy->free_in_buffer = cinfo->dest->free_in_buffer;
394

395
  /* Emit restart marker if needed */
396
  if (cinfo->restart_interval)
397
    if (entropy->restarts_to_go == 0)
398
      emit_restart(entropy, entropy->next_restart_num);
399

400
  /* Encode the MCU data blocks */
401
  for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
402
    block = MCU_data[blkn];
403
    ci = cinfo->MCU_membership[blkn];
404
    compptr = cinfo->cur_comp_info[ci];
405

406
    /* Compute the DC value after the required point transform by Al.
407
     * This is simply an arithmetic right shift.
408
     */
409
    temp2 = IRIGHT_SHIFT((int) ((*block)[0]), Al);
410

411
    /* DC differences are figured on the point-transformed values. */
412
    temp = temp2 - entropy->last_dc_val[ci];
413
    entropy->last_dc_val[ci] = temp2;
414

415
    /* Encode the DC coefficient difference per section G.1.2.1 */
416
    temp2 = temp;
417
    if (temp < 0) {
418
      temp = -temp;             /* temp is abs value of input */
419
      /* For a negative input, want temp2 = bitwise complement of abs(input) */
420
      /* This code assumes we are on a two's complement machine */
421
      temp2--;
422
    }
423

424
    /* Find the number of bits needed for the magnitude of the coefficient */
425
    nbits = 0;
426
    while (temp) {
427
      nbits++;
428
      temp >>= 1;
429
    }
430
    /* Check for out-of-range coefficient values.
431
     * Since we're encoding a difference, the range limit is twice as much.
432
     */
433
    if (nbits > MAX_COEF_BITS+1)
434
      ERREXIT(cinfo, JERR_BAD_DCT_COEF);
435

436
    /* Count/emit the Huffman-coded symbol for the number of bits */
437
    emit_symbol(entropy, compptr->dc_tbl_no, nbits);
438

439
    /* Emit that number of bits of the value, if positive, */
440
    /* or the complement of its magnitude, if negative. */
441
    if (nbits)                  /* emit_bits rejects calls with size 0 */
442
      emit_bits(entropy, (unsigned int) temp2, nbits);
443
  }
444

445
  cinfo->dest->next_output_byte = entropy->next_output_byte;
446
  cinfo->dest->free_in_buffer = entropy->free_in_buffer;
447

448
  /* Update restart-interval state too */
449
  if (cinfo->restart_interval) {
450
    if (entropy->restarts_to_go == 0) {
451
      entropy->restarts_to_go = cinfo->restart_interval;
452
      entropy->next_restart_num++;
453
      entropy->next_restart_num &= 7;
454
    }
455
    entropy->restarts_to_go--;
456
  }
457

458
  return TRUE;
459
}
460

461

462
/*
463
 * MCU encoding for AC initial scan (either spectral selection,
464
 * or first pass of successive approximation).
465
 */
466

467
METHODDEF(boolean)
468
encode_mcu_AC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
469
{
470
  phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
471
  register int temp, temp2;
472
  register int nbits;
473
  register int r, k;
474
  int Se = cinfo->Se;
475
  int Al = cinfo->Al;
476
  JBLOCKROW block;
477

478
  entropy->next_output_byte = cinfo->dest->next_output_byte;
479
  entropy->free_in_buffer = cinfo->dest->free_in_buffer;
480

481
  /* Emit restart marker if needed */
482
  if (cinfo->restart_interval)
483
    if (entropy->restarts_to_go == 0)
484
      emit_restart(entropy, entropy->next_restart_num);
485

486
  /* Encode the MCU data block */
487
  block = MCU_data[0];
488

489
  /* Encode the AC coefficients per section G.1.2.2, fig. G.3 */
490

491
  r = 0;                        /* r = run length of zeros */
492

493
  for (k = cinfo->Ss; k <= Se; k++) {
494
    if ((temp = (*block)[jpeg_natural_order[k]]) == 0) {
495
      r++;
496
      continue;
497
    }
498
    /* We must apply the point transform by Al.  For AC coefficients this
499
     * is an integer division with rounding towards 0.  To do this portably
500
     * in C, we shift after obtaining the absolute value; so the code is
501
     * interwoven with finding the abs value (temp) and output bits (temp2).
502
     */
503
    if (temp < 0) {
504
      temp = -temp;             /* temp is abs value of input */
505
      temp >>= Al;              /* apply the point transform */
506
      /* For a negative coef, want temp2 = bitwise complement of abs(coef) */
507
      temp2 = ~temp;
508
    } else {
509
      temp >>= Al;              /* apply the point transform */
510
      temp2 = temp;
511
    }
512
    /* Watch out for case that nonzero coef is zero after point transform */
513
    if (temp == 0) {
514
      r++;
515
      continue;
516
    }
517

518
    /* Emit any pending EOBRUN */
519
    if (entropy->EOBRUN > 0)
520
      emit_eobrun(entropy);
521
    /* if run length > 15, must emit special run-length-16 codes (0xF0) */
522
    while (r > 15) {
523
      emit_symbol(entropy, entropy->ac_tbl_no, 0xF0);
524
      r -= 16;
525
    }
526

527
    /* Find the number of bits needed for the magnitude of the coefficient */
528
    nbits = 1;                  /* there must be at least one 1 bit */
529
    while ((temp >>= 1))
530
      nbits++;
531
    /* Check for out-of-range coefficient values */
532
    if (nbits > MAX_COEF_BITS)
533
      ERREXIT(cinfo, JERR_BAD_DCT_COEF);
534

535
    /* Count/emit Huffman symbol for run length / number of bits */
536
    emit_symbol(entropy, entropy->ac_tbl_no, (r << 4) + nbits);
537

538
    /* Emit that number of bits of the value, if positive, */
539
    /* or the complement of its magnitude, if negative. */
540
    emit_bits(entropy, (unsigned int) temp2, nbits);
541

542
    r = 0;                      /* reset zero run length */
543
  }
544

545
  if (r > 0) {                  /* If there are trailing zeroes, */
546
    entropy->EOBRUN++;          /* count an EOB */
547
    if (entropy->EOBRUN == 0x7FFF)
548
      emit_eobrun(entropy);     /* force it out to avoid overflow */
549
  }
550

551
  cinfo->dest->next_output_byte = entropy->next_output_byte;
552
  cinfo->dest->free_in_buffer = entropy->free_in_buffer;
553

554
  /* Update restart-interval state too */
555
  if (cinfo->restart_interval) {
556
    if (entropy->restarts_to_go == 0) {
557
      entropy->restarts_to_go = cinfo->restart_interval;
558
      entropy->next_restart_num++;
559
      entropy->next_restart_num &= 7;
560
    }
561
    entropy->restarts_to_go--;
562
  }
563

564
  return TRUE;
565
}
566

567

568
/*
569
 * MCU encoding for DC successive approximation refinement scan.
570
 * Note: we assume such scans can be multi-component, although the spec
571
 * is not very clear on the point.
572
 */
573

574
METHODDEF(boolean)
575
encode_mcu_DC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
576
{
577
  phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
578
  register int temp;
579
  int blkn;
580
  int Al = cinfo->Al;
581
  JBLOCKROW block;
582

583
  entropy->next_output_byte = cinfo->dest->next_output_byte;
584
  entropy->free_in_buffer = cinfo->dest->free_in_buffer;
585

586
  /* Emit restart marker if needed */
587
  if (cinfo->restart_interval)
588
    if (entropy->restarts_to_go == 0)
589
      emit_restart(entropy, entropy->next_restart_num);
590

591
  /* Encode the MCU data blocks */
592
  for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
593
    block = MCU_data[blkn];
594

595
    /* We simply emit the Al'th bit of the DC coefficient value. */
596
    temp = (*block)[0];
597
    emit_bits(entropy, (unsigned int) (temp >> Al), 1);
598
  }
599

600
  cinfo->dest->next_output_byte = entropy->next_output_byte;
601
  cinfo->dest->free_in_buffer = entropy->free_in_buffer;
602

603
  /* Update restart-interval state too */
604
  if (cinfo->restart_interval) {
605
    if (entropy->restarts_to_go == 0) {
606
      entropy->restarts_to_go = cinfo->restart_interval;
607
      entropy->next_restart_num++;
608
      entropy->next_restart_num &= 7;
609
    }
610
    entropy->restarts_to_go--;
611
  }
612

613
  return TRUE;
614
}
615

616

617
/*
618
 * MCU encoding for AC successive approximation refinement scan.
619
 */
620

621
METHODDEF(boolean)
622
encode_mcu_AC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
623
{
624
  phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
625
  register int temp;
626
  register int r, k;
627
  int EOB;
628
  char *BR_buffer;
629
  unsigned int BR;
630
  int Se = cinfo->Se;
631
  int Al = cinfo->Al;
632
  JBLOCKROW block;
633
  int absvalues[DCTSIZE2];
634

635
  entropy->next_output_byte = cinfo->dest->next_output_byte;
636
  entropy->free_in_buffer = cinfo->dest->free_in_buffer;
637

638
  /* Emit restart marker if needed */
639
  if (cinfo->restart_interval)
640
    if (entropy->restarts_to_go == 0)
641
      emit_restart(entropy, entropy->next_restart_num);
642

643
  /* Encode the MCU data block */
644
  block = MCU_data[0];
645

646
  /* It is convenient to make a pre-pass to determine the transformed
647
   * coefficients' absolute values and the EOB position.
648
   */
649
  EOB = 0;
650
  for (k = cinfo->Ss; k <= Se; k++) {
651
    temp = (*block)[jpeg_natural_order[k]];
652
    /* We must apply the point transform by Al.  For AC coefficients this
653
     * is an integer division with rounding towards 0.  To do this portably
654
     * in C, we shift after obtaining the absolute value.
655
     */
656
    if (temp < 0)
657
      temp = -temp;             /* temp is abs value of input */
658
    temp >>= Al;                /* apply the point transform */
659
    absvalues[k] = temp;        /* save abs value for main pass */
660
    if (temp == 1)
661
      EOB = k;                  /* EOB = index of last newly-nonzero coef */
662
  }
663

664
  /* Encode the AC coefficients per section G.1.2.3, fig. G.7 */
665

666
  r = 0;                        /* r = run length of zeros */
667
  BR = 0;                       /* BR = count of buffered bits added now */
668
  BR_buffer = entropy->bit_buffer + entropy->BE; /* Append bits to buffer */
669

670
  for (k = cinfo->Ss; k <= Se; k++) {
671
    if ((temp = absvalues[k]) == 0) {
672
      r++;
673
      continue;
674
    }
675

676
    /* Emit any required ZRLs, but not if they can be folded into EOB */
677
    while (r > 15 && k <= EOB) {
678
      /* emit any pending EOBRUN and the BE correction bits */
679
      emit_eobrun(entropy);
680
      /* Emit ZRL */
681
      emit_symbol(entropy, entropy->ac_tbl_no, 0xF0);
682
      r -= 16;
683
      /* Emit buffered correction bits that must be associated with ZRL */
684
      emit_buffered_bits(entropy, BR_buffer, BR);
685
      BR_buffer = entropy->bit_buffer; /* BE bits are gone now */
686
      BR = 0;
687
    }
688

689
    /* If the coef was previously nonzero, it only needs a correction bit.
690
     * NOTE: a straight translation of the spec's figure G.7 would suggest
691
     * that we also need to test r > 15.  But if r > 15, we can only get here
692
     * if k > EOB, which implies that this coefficient is not 1.
693
     */
694
    if (temp > 1) {
695
      /* The correction bit is the next bit of the absolute value. */
696
      BR_buffer[BR++] = (char) (temp & 1);
697
      continue;
698
    }
699

700
    /* Emit any pending EOBRUN and the BE correction bits */
701
    emit_eobrun(entropy);
702

703
    /* Count/emit Huffman symbol for run length / number of bits */
704
    emit_symbol(entropy, entropy->ac_tbl_no, (r << 4) + 1);
705

706
    /* Emit output bit for newly-nonzero coef */
707
    temp = ((*block)[jpeg_natural_order[k]] < 0) ? 0 : 1;
708
    emit_bits(entropy, (unsigned int) temp, 1);
709

710
    /* Emit buffered correction bits that must be associated with this code */
711
    emit_buffered_bits(entropy, BR_buffer, BR);
712
    BR_buffer = entropy->bit_buffer; /* BE bits are gone now */
713
    BR = 0;
714
    r = 0;                      /* reset zero run length */
715
  }
716

717
  if (r > 0 || BR > 0) {        /* If there are trailing zeroes, */
718
    entropy->EOBRUN++;          /* count an EOB */
719
    entropy->BE += BR;          /* concat my correction bits to older ones */
720
    /* We force out the EOB if we risk either:
721
     * 1. overflow of the EOB counter;
722
     * 2. overflow of the correction bit buffer during the next MCU.
723
     */
724
    if (entropy->EOBRUN == 0x7FFF || entropy->BE > (MAX_CORR_BITS-DCTSIZE2+1))
725
      emit_eobrun(entropy);
726
  }
727

728
  cinfo->dest->next_output_byte = entropy->next_output_byte;
729
  cinfo->dest->free_in_buffer = entropy->free_in_buffer;
730

731
  /* Update restart-interval state too */
732
  if (cinfo->restart_interval) {
733
    if (entropy->restarts_to_go == 0) {
734
      entropy->restarts_to_go = cinfo->restart_interval;
735
      entropy->next_restart_num++;
736
      entropy->next_restart_num &= 7;
737
    }
738
    entropy->restarts_to_go--;
739
  }
740

741
  return TRUE;
742
}
743

744

745
/*
746
 * Finish up at the end of a Huffman-compressed progressive scan.
747
 */
748

749
METHODDEF(void)
750
finish_pass_phuff (j_compress_ptr cinfo)
751
{
752
  phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
753

754
  entropy->next_output_byte = cinfo->dest->next_output_byte;
755
  entropy->free_in_buffer = cinfo->dest->free_in_buffer;
756

757
  /* Flush out any buffered data */
758
  emit_eobrun(entropy);
759
  flush_bits(entropy);
760

761
  cinfo->dest->next_output_byte = entropy->next_output_byte;
762
  cinfo->dest->free_in_buffer = entropy->free_in_buffer;
763
}
764

765

766
/*
767
 * Finish up a statistics-gathering pass and create the new Huffman tables.
768
 */
769

770
METHODDEF(void)
771
finish_pass_gather_phuff (j_compress_ptr cinfo)
772
{
773
  phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
774
  boolean is_DC_band;
775
  int ci, tbl;
776
  jpeg_component_info * compptr;
777
  JHUFF_TBL **htblptr;
778
  boolean did[NUM_HUFF_TBLS];
779

780
  /* Flush out buffered data (all we care about is counting the EOB symbol) */
781
  emit_eobrun(entropy);
782

783
  is_DC_band = (cinfo->Ss == 0);
784

785
  /* It's important not to apply jpeg_gen_optimal_table more than once
786
   * per table, because it clobbers the input frequency counts!
787
   */
788
  MEMZERO(did, SIZEOF(did));
789

790
  for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
791
    compptr = cinfo->cur_comp_info[ci];
792
    if (is_DC_band) {
793
      if (cinfo->Ah != 0)       /* DC refinement needs no table */
794
        continue;
795
      tbl = compptr->dc_tbl_no;
796
    } else {
797
      tbl = compptr->ac_tbl_no;
798
    }
799
    if (! did[tbl]) {
800
      if (is_DC_band)
801
        htblptr = & cinfo->dc_huff_tbl_ptrs[tbl];
802
      else
803
        htblptr = & cinfo->ac_huff_tbl_ptrs[tbl];
804
      if (*htblptr == NULL)
805
        *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
806
      jpeg_gen_optimal_table(cinfo, *htblptr, entropy->count_ptrs[tbl]);
807
      did[tbl] = TRUE;
808
    }
809
  }
810
}
811

812

813
/*
814
 * Module initialization routine for progressive Huffman entropy encoding.
815
 */
816

817
GLOBAL(void)
818
jinit_phuff_encoder (j_compress_ptr cinfo)
819
{
820
  phuff_entropy_ptr entropy;
821
  int i;
822

823
  entropy = (phuff_entropy_ptr)
824
    (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
825
                                SIZEOF(phuff_entropy_encoder));
826
  cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
827
  entropy->pub.start_pass = start_pass_phuff;
828

829
  /* Mark tables unallocated */
830
  for (i = 0; i < NUM_HUFF_TBLS; i++) {
831
    entropy->derived_tbls[i] = NULL;
832
    entropy->count_ptrs[i] = NULL;
833
  }
834
  entropy->bit_buffer = NULL;   /* needed only in AC refinement scan */
835
}
836

837
#endif /* C_PROGRESSIVE_SUPPORTED */
838