jcphuff.c 33 KB

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