1  /********************************************************************** <BR>


2  This file is part of Crack dot Com's free source code release of


3  Golgotha. <a href="http://www.crack.com/golgotha_release"> <BR> for


4  information about compiling & licensing issues visit this URL</a>


5  <PRE> If that doesn't help, contact Jonathan Clark at


6  golgotha_source@usa.net (Subject should have "GOLG" in it)


7  ***********************************************************************/


8 


9  /* 

10  * jchuff.c 

11  * 

12  * Copyright (C) 19911996, Thomas G. Lane. 

13  * This file is part of the Independent JPEG Group's software. 

14  * For conditions of distribution and use, see the accompanying README file. 

15  * 

16  * This file contains Huffman entropy encoding routines. 

17  * 

18  * Much of the complexity here has to do with supporting output suspension. 

19  * If the data destination module demands suspension, we want to be able to 

20  * back up to the start of the current MCU. To do this, we copy state 

21  * variables into local working storage, and update them back to the 

22  * permanent JPEG objects only upon successful completion of an MCU. 

23  */ 

24  

25  #define JPEG_INTERNALS 

26  #include "loaders/jpg/jinclude.h" 

27  #include "loaders/jpg/jpeglib.h" 

28  #include "loaders/jpg/jchuff.h" /* Declarations shared with jcphuff.c */ 

29  

30  

31  /* Expanded entropy encoder object for Huffman encoding. 

32  * 

33  * The savable_state subrecord contains fields that change within an MCU, 

34  * but must not be updated permanently until we complete the MCU. 

35  */ 

36  

37  typedef struct { 

38  INT32 put_buffer; /* current bitaccumulation buffer */ 

39  int put_bits; /* # of bits now in it */ 

40  int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */ 

41  } savable_state; 

42  

43  /* This macro is to work around compilers with missing or broken 

44  * structure assignment. You'll need to fix this code if you have 

45  * such a compiler and you change MAX_COMPS_IN_SCAN. 

46  */ 

47  

48  #ifndef NO_STRUCT_ASSIGN 

49  #define ASSIGN_STATE(dest,src) ((dest) = (src)) 

50  #else 

51  #if MAX_COMPS_IN_SCAN == 4 

52  #define ASSIGN_STATE(dest,src) \ 

53  ((dest).put_buffer = (src).put_buffer, \ 

54  (dest).put_bits = (src).put_bits, \ 

55  (dest).last_dc_val[0] = (src).last_dc_val[0], \ 

56  (dest).last_dc_val[1] = (src).last_dc_val[1], \ 

57  (dest).last_dc_val[2] = (src).last_dc_val[2], \ 

58  (dest).last_dc_val[3] = (src).last_dc_val[3]) 

59  #endif 

60  #endif 

61  

62  

63  typedef struct { 

64  struct jpeg_entropy_encoder pub; /* public fields */ 

65  

66  savable_state saved; /* Bit buffer & DC state at start of MCU */ 

67  

68  /* These fields are NOT loaded into local working state. */ 

69  unsigned int restarts_to_go; /* MCUs left in this restart interval */ 

70  int next_restart_num; /* next restart number to write (07) */ 

71  

72  /* Pointers to derived tables (these workspaces have image lifespan) */ 

73  c_derived_tbl * dc_derived_tbls[NUM_HUFF_TBLS]; 

74  c_derived_tbl * ac_derived_tbls[NUM_HUFF_TBLS]; 

75  

76  #ifdef ENTROPY_OPT_SUPPORTED /* Statistics tables for optimization */ 

77  long * dc_count_ptrs[NUM_HUFF_TBLS]; 

78  long * ac_count_ptrs[NUM_HUFF_TBLS]; 

79  #endif 

80  } huff_entropy_encoder; 

81  

82  typedef huff_entropy_encoder * huff_entropy_ptr; 

83  

84  /* Working state while writing an MCU. 

85  * This struct contains all the fields that are needed by subroutines. 

86  */ 

87  

88  typedef struct { 

89  JOCTET * next_output_byte; /* => next byte to write in buffer */ 

90  size_t free_in_buffer; /* # of byte spaces remaining in buffer */ 

91  savable_state cur; /* Current bit buffer & DC state */ 

92  j_compress_ptr cinfo; /* dump_buffer needs access to this */ 

93  } working_state; 

94  

95  

96  /* Forward declarations */ 

97  METHODDEF(boolean) encode_mcu_huff JPP((j_compress_ptr cinfo, 

98  JBLOCKROW *MCU_data)); 

99  METHODDEF(void) finish_pass_huff JPP((j_compress_ptr cinfo)); 

100  #ifdef ENTROPY_OPT_SUPPORTED 

101  METHODDEF(boolean) encode_mcu_gather JPP((j_compress_ptr cinfo, 

102  JBLOCKROW *MCU_data)); 

103  METHODDEF(void) finish_pass_gather JPP((j_compress_ptr cinfo)); 

104  #endif 

105  

106  

107  /* 

108  * Initialize for a Huffmancompressed scan. 

109  * If gather_statistics is TRUE, we do not output anything during the scan, 

110  * just count the Huffman symbols used and generate Huffman code tables. 

111  */ 

112  

113  METHODDEF(void) 

114  start_pass_huff (j_compress_ptr cinfo, boolean gather_statistics) 

115  { 

116  huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo>entropy; 

117  int ci, dctbl, actbl; 

118  jpeg_component_info * compptr; 

119  

120  if (gather_statistics) { 

121  #ifdef ENTROPY_OPT_SUPPORTED 

122  entropy>pub.encode_mcu = encode_mcu_gather; 

123  entropy>pub.finish_pass = finish_pass_gather; 

124  #else 

125  ERREXIT(cinfo, JERR_NOT_COMPILED); 

126  #endif 

127  } else { 

128  entropy>pub.encode_mcu = encode_mcu_huff; 

129  entropy>pub.finish_pass = finish_pass_huff; 

130  } 

131  

132  for (ci = 0; ci < cinfo>comps_in_scan; ci++) { 

133  compptr = cinfo>cur_comp_info[ci]; 

134  dctbl = compptr>dc_tbl_no; 

135  actbl = compptr>ac_tbl_no; 

136  /* Make sure requested tables are present */ 

137  /* (In gather mode, tables need not be allocated yet) */ 

138  if (dctbl < 0  dctbl >= NUM_HUFF_TBLS  

139  (cinfo>dc_huff_tbl_ptrs[dctbl] == NULL && !gather_statistics)) 

140  ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, dctbl); 

141  if (actbl < 0  actbl >= NUM_HUFF_TBLS  

142  (cinfo>ac_huff_tbl_ptrs[actbl] == NULL && !gather_statistics)) 

143  ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, actbl); 

144  if (gather_statistics) { 

145  #ifdef ENTROPY_OPT_SUPPORTED 

146  /* Allocate and zero the statistics tables */ 

147  /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */ 

148  if (entropy>dc_count_ptrs[dctbl] == NULL) 

149  entropy>dc_count_ptrs[dctbl] = (long *) 

150  (*cinfo>mem>alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 

151  257 * SIZEOF(long)); 

152  MEMZERO(entropy>dc_count_ptrs[dctbl], 257 * SIZEOF(long)); 

153  if (entropy>ac_count_ptrs[actbl] == NULL) 

154  entropy>ac_count_ptrs[actbl] = (long *) 

155  (*cinfo>mem>alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 

156  257 * SIZEOF(long)); 

157  MEMZERO(entropy>ac_count_ptrs[actbl], 257 * SIZEOF(long)); 

158  #endif 

159  } else { 

160  /* Compute derived values for Huffman tables */ 

161  /* We may do this more than once for a table, but it's not expensive */ 

162  jpeg_make_c_derived_tbl(cinfo, cinfo>dc_huff_tbl_ptrs[dctbl], 

163  & entropy>dc_derived_tbls[dctbl]); 

164  jpeg_make_c_derived_tbl(cinfo, cinfo>ac_huff_tbl_ptrs[actbl], 

165  & entropy>ac_derived_tbls[actbl]); 

166  } 

167  /* Initialize DC predictions to 0 */ 

168  entropy>saved.last_dc_val[ci] = 0; 

169  } 

170  

171  /* Initialize bit buffer to empty */ 

172  entropy>saved.put_buffer = 0; 

173  entropy>saved.put_bits = 0; 

174  

175  /* Initialize restart stuff */ 

176  entropy>restarts_to_go = cinfo>restart_interval; 

177  entropy>next_restart_num = 0; 

178  } 

179  

180  

181  /* 

182  * Compute the derived values for a Huffman table. 

183  * Note this is also used by jcphuff.c. 

184  */ 

185  

186  GLOBAL(void) 

187  jpeg_make_c_derived_tbl (j_compress_ptr cinfo, JHUFF_TBL * htbl, 

188  c_derived_tbl ** pdtbl) 

189  { 

190  c_derived_tbl *dtbl; 

191  int p, i, l, lastp, si; 

192  char huffsize[257]; 

193  unsigned int huffcode[257]; 

194  unsigned int code; 

195  

196  /* Allocate a workspace if we haven't already done so. */ 

197  if (*pdtbl == NULL) 

198  *pdtbl = (c_derived_tbl *) 

199  (*cinfo>mem>alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 

200  SIZEOF(c_derived_tbl)); 

201  dtbl = *pdtbl; 

202  

203  /* Figure C.1: make table of Huffman code length for each symbol */ 

204  /* Note that this is in codelength order. */ 

205  

206  p = 0; 

207  for (l = 1; l <= 16; l++) { 

208  for (i = 1; i <= (int) htbl>bits[l]; i++) 

209  huffsize[p++] = (char) l; 

210  } 

211  huffsize[p] = 0; 

212  lastp = p; 

213  

214  /* Figure C.2: generate the codes themselves */ 

215  /* Note that this is in codelength order. */ 

216  

217  code = 0; 

218  si = huffsize[0]; 

219  p = 0; 

220  while (huffsize[p]) { 

221  while (((int) huffsize[p]) == si) { 

222  huffcode[p++] = code; 

223  code++; 

224  } 

225  code <<= 1; 

226  si++; 

227  } 

228  

229  /* Figure C.3: generate encoding tables */ 

230  /* These are code and size indexed by symbol value */ 

231  

232  /* Set any codeless symbols to have code length 0; 

233  * this allows emit_bits to detect any attempt to emit such symbols. 

234  */ 

235  MEMZERO(dtbl>ehufsi, SIZEOF(dtbl>ehufsi)); 

236  

237  for (p = 0; p < lastp; p++) { 

238  dtbl>ehufco[htbl>huffval[p]] = huffcode[p]; 

239  dtbl>ehufsi[htbl>huffval[p]] = huffsize[p]; 

240  } 

241  } 

242  

243  

244  /* Outputting bytes to the file */ 

245  

246  /* Emit a byte, taking 'action' if must suspend. */ 

247  #define emit_byte(state,val,action) \ 

248  { *(state)>next_output_byte++ = (JOCTET) (val); \ 

249  if ((state)>free_in_buffer == 0) \ 

250  if (! dump_buffer(state)) \ 

251  { action; } } 

252  

253  

254  LOCAL(boolean) 

255  dump_buffer (working_state * state) 

256  /* Empty the output buffer; return TRUE if successful, FALSE if must suspend */ 

257  { 

258  struct jpeg_destination_mgr * dest = state>cinfo>dest; 

259  

260  if (! (*dest>empty_output_buffer) (state>cinfo)) 

261  return FALSE; 

262  /* After a successful buffer dump, must reset buffer pointers */ 

263  state>next_output_byte = dest>next_output_byte; 

264  state>free_in_buffer = dest>free_in_buffer; 

265  return TRUE; 

266  } 

267  

268  

269  /* Outputting bits to the file */ 

270  

271  /* Only the right 24 bits of put_buffer are used; the valid bits are 

272  * leftjustified in this part. At most 16 bits can be passed to emit_bits 

273  * in one call, and we never retain more than 7 bits in put_buffer 

274  * between calls, so 24 bits are sufficient. 

275  */ 

276  

277  INLINE 

278  LOCAL(boolean) 

279  emit_bits (working_state * state, unsigned int code, int size) 

280  /* Emit some bits; return TRUE if successful, FALSE if must suspend */ 

281  { 

282  /* This routine is heavily used, so it's worth coding tightly. */ 

283  register INT32 put_buffer = (INT32) code; 

284  register int put_bits = state>cur.put_bits; 

285  

286  /* if size is 0, caller used an invalid Huffman table entry */ 

287  if (size == 0) 

288  ERREXIT(state>cinfo, JERR_HUFF_MISSING_CODE); 

289  

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

291  

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

293  

294  put_buffer <<= 24  put_bits; /* align incoming bits */ 

295  

296  put_buffer = state>cur.put_buffer; /* and merge with old buffer contents */ 

297  

298  while (put_bits >= 8) { 

299  int c = (int) ((put_buffer >> 16) & 0xFF); 

300  

301  emit_byte(state, c, return FALSE); 

302  if (c == 0xFF) { /* need to stuff a zero byte? */ 

303  emit_byte(state, 0, return FALSE); 

304  } 

305  put_buffer <<= 8; 

306  put_bits = 8; 

307  } 

308  

309  state>cur.put_buffer = put_buffer; /* update state variables */ 

310  state>cur.put_bits = put_bits; 

311  

312  return TRUE; 

313  } 

314  

315  

316  LOCAL(boolean) 

317  flush_bits (working_state * state) 

318  { 

319  if (! emit_bits(state, 0x7F, 7)) /* fill any partial byte with ones */ 

320  return FALSE; 

321  state>cur.put_buffer = 0; /* and reset bitbuffer to empty */ 

322  state>cur.put_bits = 0; 

323  return TRUE; 

324  } 

325  

326  

327  /* Encode a single block's worth of coefficients */ 

328  

329  LOCAL(boolean) 

330  encode_one_block (working_state * state, JCOEFPTR block, int last_dc_val, 

331  c_derived_tbl *dctbl, c_derived_tbl *actbl) 

332  { 

333  register int temp, temp2; 

334  register int nbits; 

335  register int k, r, i; 

336  

337  /* Encode the DC coefficient difference per section F.1.2.1 */ 

338  

339  temp = temp2 = block[0]  last_dc_val; 

340  

341  if (temp < 0) { 

342  temp = temp; /* temp is abs value of input */ 

343  /* For a negative input, want temp2 = bitwise complement of abs(input) */ 

344  /* This code assumes we are on a two's complement machine */ 

345  temp2; 

346  } 

347  

348  /* Find the number of bits needed for the magnitude of the coefficient */ 

349  nbits = 0; 

350  while (temp) { 

351  nbits++; 

352  temp >>= 1; 

353  } 

354  

355  /* Emit the Huffmancoded symbol for the number of bits */ 

356  if (! emit_bits(state, dctbl>ehufco[nbits], dctbl>ehufsi[nbits])) 

357  return FALSE; 

358  

359  /* Emit that number of bits of the value, if positive, */ 

360  /* or the complement of its magnitude, if negative. */ 

361  if (nbits) /* emit_bits rejects calls with size 0 */ 

362  if (! emit_bits(state, (unsigned int) temp2, nbits)) 

363  return FALSE; 

364  

365  /* Encode the AC coefficients per section F.1.2.2 */ 

366  

367  r = 0; /* r = run length of zeros */ 

368  

369  for (k = 1; k < DCTSIZE2; k++) { 

370  if ((temp = block[jpeg_natural_order[k]]) == 0) { 

371  r++; 

372  } else { 

373  /* if run length > 15, must emit special runlength16 codes (0xF0) */ 

374  while (r > 15) { 

375  if (! emit_bits(state, actbl>ehufco[0xF0], actbl>ehufsi[0xF0])) 

376  return FALSE; 

377  r = 16; 

378  } 

379  

380  temp2 = temp; 

381  if (temp < 0) { 

382  temp = temp; /* temp is abs value of input */ 

383  /* This code assumes we are on a two's complement machine */ 

384  temp2; 

385  } 

386  

387  /* Find the number of bits needed for the magnitude of the coefficient */ 

388  nbits = 1; /* there must be at least one 1 bit */ 

389  while ((temp >>= 1)) 

390  nbits++; 

391  

392  /* Emit Huffman symbol for run length / number of bits */ 

393  i = (r << 4) + nbits; 

394  if (! emit_bits(state, actbl>ehufco[i], actbl>ehufsi[i])) 

395  return FALSE; 

396  

397  /* Emit that number of bits of the value, if positive, */ 

398  /* or the complement of its magnitude, if negative. */ 

399  if (! emit_bits(state, (unsigned int) temp2, nbits)) 

400  return FALSE; 

401  

402  r = 0; 

403  } 

404  } 

405  

406  /* If the last coef(s) were zero, emit an endofblock code */ 

407  if (r > 0) 

408  if (! emit_bits(state, actbl>ehufco[0], actbl>ehufsi[0])) 

409  return FALSE; 

410  

411  return TRUE; 

412  } 

413  

414  

415  /* 

416  * Emit a restart marker & resynchronize predictions. 

417  */ 

418  

419  LOCAL(boolean) 

420  emit_restart (working_state * state, int restart_num) 

421  { 

422  int ci; 

423  

424  if (! flush_bits(state)) 

425  return FALSE; 

426  

427  emit_byte(state, 0xFF, return FALSE); 

428  emit_byte(state, JPEG_RST0 + restart_num, return FALSE); 

429  

430  /* Reinitialize DC predictions to 0 */ 

431  for (ci = 0; ci < state>cinfo>comps_in_scan; ci++) 

432  state>cur.last_dc_val[ci] = 0; 

433  

434  /* The restart counter is not updated until we successfully write the MCU. */ 

435  

436  return TRUE; 

437  } 

438  

439  

440  /* 

441  * Encode and output one MCU's worth of Huffmancompressed coefficients. 

442  */ 

443  

444  METHODDEF(boolean) 

445  encode_mcu_huff (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 

446  { 

447  huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo>entropy; 

448  working_state state; 

449  int blkn, ci; 

450  jpeg_component_info * compptr; 

451  

452  /* Load up working state */ 

453  state.next_output_byte = cinfo>dest>next_output_byte; 

454  state.free_in_buffer = cinfo>dest>free_in_buffer; 

455  ASSIGN_STATE(state.cur, entropy>saved); 

456  state.cinfo = cinfo; 

457  

458  /* Emit restart marker if needed */ 

459  if (cinfo>restart_interval) { 

460  if (entropy>restarts_to_go == 0) 

461  if (! emit_restart(&state, entropy>next_restart_num)) 

462  return FALSE; 

463  } 

464  

465  /* Encode the MCU data blocks */ 

466  for (blkn = 0; blkn < cinfo>blocks_in_MCU; blkn++) { 

467  ci = cinfo>MCU_membership[blkn]; 

468  compptr = cinfo>cur_comp_info[ci]; 

469  if (! encode_one_block(&state, 

470  MCU_data[blkn][0], state.cur.last_dc_val[ci], 

471  entropy>dc_derived_tbls[compptr>dc_tbl_no], 

472  entropy>ac_derived_tbls[compptr>ac_tbl_no])) 

473  return FALSE; 

474  /* Update last_dc_val */ 

475  state.cur.last_dc_val[ci] = MCU_data[blkn][0][0]; 

476  } 

477  

478  /* Completed MCU, so update state */ 

479  cinfo>dest>next_output_byte = state.next_output_byte; 

480  cinfo>dest>free_in_buffer = state.free_in_buffer; 

481  ASSIGN_STATE(entropy>saved, state.cur); 

482  

483  /* Update restartinterval state too */ 

484  if (cinfo>restart_interval) { 

485  if (entropy>restarts_to_go == 0) { 

486  entropy>restarts_to_go = cinfo>restart_interval; 

487  entropy>next_restart_num++; 

488  entropy>next_restart_num &= 7; 

489  } 

490  entropy>restarts_to_go; 

491  } 

492  

493  return TRUE; 

494  } 

495  

496  

497  /* 

498  * Finish up at the end of a Huffmancompressed scan. 

499  */ 

500  

501  METHODDEF(void) 

502  finish_pass_huff (j_compress_ptr cinfo) 

503  { 

504  huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo>entropy; 

505  working_state state; 

506  

507  /* Load up working state ... flush_bits needs it */ 

508  state.next_output_byte = cinfo>dest>next_output_byte; 

509  state.free_in_buffer = cinfo>dest>free_in_buffer; 

510  ASSIGN_STATE(state.cur, entropy>saved); 

511  state.cinfo = cinfo; 

512  

513  /* Flush out the last data */ 

514  if (! flush_bits(&state)) 

515  ERREXIT(cinfo, JERR_CANT_SUSPEND); 

516  

517  /* Update state */ 

518  cinfo>dest>next_output_byte = state.next_output_byte; 

519  cinfo>dest>free_in_buffer = state.free_in_buffer; 

520  ASSIGN_STATE(entropy>saved, state.cur); 

521  } 

522  

523  

524  /* 

525  * Huffman coding optimization. 

526  * 

527  * This actually is optimization, in the sense that we find the best possible 

528  * Huffman table(s) for the given data. We first scan the supplied data and 

529  * count the number of uses of each symbol that is to be Huffmancoded. 

530  * (This process must agree with the code above.) Then we build an 

531  * optimal Huffman coding tree for the observed counts. 

532  * 

533  * The JPEG standard requires Huffman codes to be no more than 16 bits long. 

534  * If some symbols have a very small but nonzero probability, the Huffman tree 

535  * must be adjusted to meet the code length restriction. We currently use 

536  * the adjustment method suggested in the JPEG spec. This method is *not* 

537  * optimal; it may not choose the best possible limitedlength code. But 

538  * since the symbols involved are infrequently used, it's not clear that 

539  * going to extra trouble is worthwhile. 

540  */ 

541  

542  #ifdef ENTROPY_OPT_SUPPORTED 

543  

544  

545  /* Process a single block's worth of coefficients */ 

546  

547  LOCAL(void) 

548  htest_one_block (JCOEFPTR block, int last_dc_val, 

549  long dc_counts[], long ac_counts[]) 

550  { 

551  register int temp; 

552  register int nbits; 

553  register int k, r; 

554  

555  /* Encode the DC coefficient difference per section F.1.2.1 */ 

556  

557  temp = block[0]  last_dc_val; 

558  if (temp < 0) 

559  temp = temp; 

560  

561  /* Find the number of bits needed for the magnitude of the coefficient */ 

562  nbits = 0; 

563  while (temp) { 

564  nbits++; 

565  temp >>= 1; 

566  } 

567  

568  /* Count the Huffman symbol for the number of bits */ 

569  dc_counts[nbits]++; 

570  

571  /* Encode the AC coefficients per section F.1.2.2 */ 

572  

573  r = 0; /* r = run length of zeros */ 

574  

575  for (k = 1; k < DCTSIZE2; k++) { 

576  if ((temp = block[jpeg_natural_order[k]]) == 0) { 

577  r++; 

578  } else { 

579  /* if run length > 15, must emit special runlength16 codes (0xF0) */ 

580  while (r > 15) { 

581  ac_counts[0xF0]++; 

582  r = 16; 

583  } 

584  

585  /* Find the number of bits needed for the magnitude of the coefficient */ 

586  if (temp < 0) 

587  temp = temp; 

588  

589  /* Find the number of bits needed for the magnitude of the coefficient */ 

590  nbits = 1; /* there must be at least one 1 bit */ 

591  while ((temp >>= 1)) 

592  nbits++; 

593  

594  /* Count Huffman symbol for run length / number of bits */ 

595  ac_counts[(r << 4) + nbits]++; 

596  

597  r = 0; 

598  } 

599  } 

600  

601  /* If the last coef(s) were zero, emit an endofblock code */ 

602  if (r > 0) 

603  ac_counts[0]++; 

604  } 

605  

606  

607  /* 

608  * Trialencode one MCU's worth of Huffmancompressed coefficients. 

609  * No data is actually output, so no suspension return is possible. 

610  */ 

611  

612  METHODDEF(boolean) 

613  encode_mcu_gather (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 

614  { 

615  huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo>entropy; 

616  int blkn, ci; 

617  jpeg_component_info * compptr; 

618  

619  /* Take care of restart intervals if needed */ 

620  if (cinfo>restart_interval) { 

621  if (entropy>restarts_to_go == 0) { 

622  /* Reinitialize DC predictions to 0 */ 

623  for (ci = 0; ci < cinfo>comps_in_scan; ci++) 

624  entropy>saved.last_dc_val[ci] = 0; 

625  /* Update restart state */ 

626  entropy>restarts_to_go = cinfo>restart_interval; 

627  } 

628  entropy>restarts_to_go; 

629  } 

630  

631  for (blkn = 0; blkn < cinfo>blocks_in_MCU; blkn++) { 

632  ci = cinfo>MCU_membership[blkn]; 

633  compptr = cinfo>cur_comp_info[ci]; 

634  htest_one_block(MCU_data[blkn][0], entropy>saved.last_dc_val[ci], 

635  entropy>dc_count_ptrs[compptr>dc_tbl_no], 

636  entropy>ac_count_ptrs[compptr>ac_tbl_no]); 

637  entropy>saved.last_dc_val[ci] = MCU_data[blkn][0][0]; 

638  } 

639  

640  return TRUE; 

641  } 

642  

643  

644  /* 

645  * Generate the optimal coding for the given counts, fill htbl. 

646  * Note this is also used by jcphuff.c. 

647  */ 

648  

649  GLOBAL(void) 

650  jpeg_gen_optimal_table (j_compress_ptr cinfo, JHUFF_TBL * htbl, long freq[]) 

651  { 

652  #define MAX_CLEN 32 /* assumed maximum initial code length */ 

653  UINT8 bits[MAX_CLEN+1]; /* bits[k] = # of symbols with code length k */ 

654  int codesize[257]; /* codesize[k] = code length of symbol k */ 

655  int others[257]; /* next symbol in current branch of tree */ 

656  int c1, c2; 

657  int p, i, j; 

658  long v; 

659  

660  /* This algorithm is explained in section K.2 of the JPEG standard */ 

661  

662  MEMZERO(bits, SIZEOF(bits)); 

663  MEMZERO(codesize, SIZEOF(codesize)); 

664  for (i = 0; i < 257; i++) 

665  others[i] = 1; /* init links to empty */ 

666  

667  freq[256] = 1; /* make sure there is a nonzero count */ 

668  /* Including the pseudosymbol 256 in the Huffman procedure guarantees 

669  * that no real symbol is given codevalue of all ones, because 256 

670  * will be placed in the largest codeword category. 

671  */ 

672  

673  /* Huffman's basic algorithm to assign optimal code lengths to symbols */ 

674  

675  for (;;) { 

676  /* Find the smallest nonzero frequency, set c1 = its symbol */ 

677  /* In case of ties, take the larger symbol number */ 

678  c1 = 1; 

679  v = 1000000000L; 

680  for (i = 0; i <= 256; i++) { 

681  if (freq[i] && freq[i] <= v) { 

682  v = freq[i]; 

683  c1 = i; 

684  } 

685  } 

686  

687  /* Find the next smallest nonzero frequency, set c2 = its symbol */ 

688  /* In case of ties, take the larger symbol number */ 

689  c2 = 1; 

690  v = 1000000000L; 

691  for (i = 0; i <= 256; i++) { 

692  if (freq[i] && freq[i] <= v && i != c1) { 

693  v = freq[i]; 

694  c2 = i; 

695  } 

696  } 

697  

698  /* Done if we've merged everything into one frequency */ 

699  if (c2 < 0) 

700  break; 

701  

702  /* Else merge the two counts/trees */ 

703  freq[c1] += freq[c2]; 

704  freq[c2] = 0; 

705  

706  /* Increment the codesize of everything in c1's tree branch */ 

707  codesize[c1]++; 

708  while (others[c1] >= 0) { 

709  c1 = others[c1]; 

710  codesize[c1]++; 

711  } 

712  

713  others[c1] = c2; /* chain c2 onto c1's tree branch */ 

714  

715  /* Increment the codesize of everything in c2's tree branch */ 

716  codesize[c2]++; 

717  while (others[c2] >= 0) { 

718  c2 = others[c2]; 

719  codesize[c2]++; 

720  } 

721  } 

722  

723  /* Now count the number of symbols of each code length */ 

724  for (i = 0; i <= 256; i++) { 

725  if (codesize[i]) { 

726  /* The JPEG standard seems to think that this can't happen, */ 

727  /* but I'm paranoid... */ 

728  if (codesize[i] > MAX_CLEN) 

729  ERREXIT(cinfo, JERR_HUFF_CLEN_OVERFLOW); 

730  

731  bits[codesize[i]]++; 

732  } 

733  } 

734  

735  /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure 

736  * Huffman procedure assigned any such lengths, we must adjust the coding. 

737  * Here is what the JPEG spec says about how this next bit works: 

738  * Since symbols are paired for the longest Huffman code, the symbols are 

739  * removed from this length category two at a time. The prefix for the pair 

740  * (which is one bit shorter) is allocated to one of the pair; then, 

741  * skipping the BITS entry for that prefix length, a code word from the next 

742  * shortest nonzero BITS entry is converted into a prefix for two code words 

743  * one bit longer. 

744  */ 

745  

746  for (i = MAX_CLEN; i > 16; i) { 

747  while (bits[i] > 0) { 

748  j = i  2; /* find length of new prefix to be used */ 

749  while (bits[j] == 0) 

750  j; 

751  

752  bits[i] = 2; /* remove two symbols */ 

753  bits[i1]++; /* one goes in this length */ 

754  bits[j+1] += 2; /* two new symbols in this length */ 

755  bits[j]; /* symbol of this length is now a prefix */ 

756  } 

757  } 

758  

759  /* Remove the count for the pseudosymbol 256 from the largest codelength */ 

760  while (bits[i] == 0) /* find largest codelength still in use */ 

761  i; 

762  bits[i]; 

763  

764  /* Return final symbol counts (only for lengths 0..16) */ 

765  MEMCOPY(htbl>bits, bits, SIZEOF(htbl>bits)); 

766  

767  /* Return a list of the symbols sorted by code length */ 

768  /* It's not real clear to me why we don't need to consider the codelength 

769  * changes made above, but the JPEG spec seems to think this works. 

770  */ 

771  p = 0; 

772  for (i = 1; i <= MAX_CLEN; i++) { 

773  for (j = 0; j <= 255; j++) { 

774  if (codesize[j] == i) { 

775  htbl>huffval[p] = (UINT8) j; 

776  p++; 

777  } 

778  } 

779  } 

780  

781  /* Set sent_table FALSE so updated table will be written to JPEG file. */ 

782  htbl>sent_table = FALSE; 

783  } 

784  

785  

786  /* 

787  * Finish up a statisticsgathering pass and create the new Huffman tables. 

788  */ 

789  

790  METHODDEF(void) 

791  finish_pass_gather (j_compress_ptr cinfo) 

792  { 

793  huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo>entropy; 

794  int ci, dctbl, actbl; 

795  jpeg_component_info * compptr; 

796  JHUFF_TBL **htblptr; 

797  boolean did_dc[NUM_HUFF_TBLS]; 

798  boolean did_ac[NUM_HUFF_TBLS]; 

799  

800  /* It's important not to apply jpeg_gen_optimal_table more than once 

801  * per table, because it clobbers the input frequency counts! 

802  */ 

803  MEMZERO(did_dc, SIZEOF(did_dc)); 

804  MEMZERO(did_ac, SIZEOF(did_ac)); 

805  

806  for (ci = 0; ci < cinfo>comps_in_scan; ci++) { 

807  compptr = cinfo>cur_comp_info[ci]; 

808  dctbl = compptr>dc_tbl_no; 

809  actbl = compptr>ac_tbl_no; 

810  if (! did_dc[dctbl]) { 

811  htblptr = & cinfo>dc_huff_tbl_ptrs[dctbl]; 

812  if (*htblptr == NULL) 

813  *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo); 

814  jpeg_gen_optimal_table(cinfo, *htblptr, entropy>dc_count_ptrs[dctbl]); 

815  did_dc[dctbl] = TRUE; 

816  } 

817  if (! did_ac[actbl]) { 

818  htblptr = & cinfo>ac_huff_tbl_ptrs[actbl]; 

819  if (*htblptr == NULL) 

820  *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo); 

821  jpeg_gen_optimal_table(cinfo, *htblptr, entropy>ac_count_ptrs[actbl]); 

822  did_ac[actbl] = TRUE; 

823  } 

824  } 

825  } 

826  

827  

828  #endif /* ENTROPY_OPT_SUPPORTED */ 

829  

830  

831  /* 

832  * Module initialization routine for Huffman entropy encoding. 

833  */ 

834  

835  GLOBAL(void) 

836  jinit_huff_encoder (j_compress_ptr cinfo) 

837  { 

838  huff_entropy_ptr entropy; 

839  int i; 

840  

841  entropy = (huff_entropy_ptr) 

842  (*cinfo>mem>alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 

843  SIZEOF(huff_entropy_encoder)); 

844  cinfo>entropy = (struct jpeg_entropy_encoder *) entropy; 

845  entropy>pub.start_pass = start_pass_huff; 

846  

847  /* Mark tables unallocated */ 

848  for (i = 0; i < NUM_HUFF_TBLS; i++) { 

849  entropy>dc_derived_tbls[i] = entropy>ac_derived_tbls[i] = NULL; 

850  #ifdef ENTROPY_OPT_SUPPORTED 

851  entropy>dc_count_ptrs[i] = entropy>ac_count_ptrs[i] = NULL; 

852  #endif 

853  } 

854  } 
