jfdctint.cpp 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283
  1. /*
  2. * jfdctint.c
  3. *
  4. * Copyright (C) 1991-1994, Thomas G. Lane.
  5. * This file is part of the Independent JPEG Group's software.
  6. * For conditions of distribution and use, see the accompanying README file.
  7. *
  8. * This file contains a slow-but-accurate integer implementation of the
  9. * forward DCT (Discrete Cosine Transform).
  10. *
  11. * A 2-D DCT can be done by 1-D DCT on each row followed by 1-D DCT
  12. * on each column. Direct algorithms are also available, but they are
  13. * much more complex and seem not to be any faster when reduced to code.
  14. *
  15. * This implementation is based on an algorithm described in
  16. * C. Loeffler, A. Ligtenberg and G. Moschytz, "Practical Fast 1-D DCT
  17. * Algorithms with 11 Multiplications", Proc. Int'l. Conf. on Acoustics,
  18. * Speech, and Signal Processing 1989 (ICASSP '89), pp. 988-991.
  19. * The primary algorithm described there uses 11 multiplies and 29 adds.
  20. * We use their alternate method with 12 multiplies and 32 adds.
  21. * The advantage of this method is that no data path contains more than one
  22. * multiplication; this allows a very simple and accurate implementation in
  23. * scaled fixed-point arithmetic, with a minimal number of shifts.
  24. */
  25. #define JPEG_INTERNALS
  26. #include "jinclude.h"
  27. #include "jpeglib.h"
  28. #include "jdct.h" /* Private declarations for DCT subsystem */
  29. #ifdef DCT_ISLOW_SUPPORTED
  30. /*
  31. * This module is specialized to the case DCTSIZE = 8.
  32. */
  33. #if DCTSIZE != 8
  34. Sorry, this code only copes with 8 x8 DCTs. /* deliberate syntax err */
  35. #endif
  36. /*
  37. * The poop on this scaling stuff is as follows:
  38. *
  39. * Each 1-D DCT step produces outputs which are a factor of sqrt(N)
  40. * larger than the true DCT outputs. The final outputs are therefore
  41. * a factor of N larger than desired; since N=8 this can be cured by
  42. * a simple right shift at the end of the algorithm. The advantage of
  43. * this arrangement is that we save two multiplications per 1-D DCT,
  44. * because the y0 and y4 outputs need not be divided by sqrt(N).
  45. * In the IJG code, this factor of 8 is removed by the quantization step
  46. * (in jcdctmgr.c), NOT in this module.
  47. *
  48. * We have to do addition and subtraction of the integer inputs, which
  49. * is no problem, and multiplication by fractional constants, which is
  50. * a problem to do in integer arithmetic. We multiply all the constants
  51. * by CONST_SCALE and convert them to integer constants (thus retaining
  52. * CONST_BITS bits of precision in the constants). After doing a
  53. * multiplication we have to divide the product by CONST_SCALE, with proper
  54. * rounding, to produce the correct output. This division can be done
  55. * cheaply as a right shift of CONST_BITS bits. We postpone shifting
  56. * as long as possible so that partial sums can be added together with
  57. * full fractional precision.
  58. *
  59. * The outputs of the first pass are scaled up by PASS1_BITS bits so that
  60. * they are represented to better-than-integral precision. These outputs
  61. * require BITS_IN_JSAMPLE + PASS1_BITS + 3 bits; this fits in a 16-bit word
  62. * with the recommended scaling. (For 12-bit sample data, the intermediate
  63. * array is INT32 anyway.)
  64. *
  65. * To avoid overflow of the 32-bit intermediate results in pass 2, we must
  66. * have BITS_IN_JSAMPLE + CONST_BITS + PASS1_BITS <= 26. Error analysis
  67. * shows that the values given below are the most effective.
  68. */
  69. #if BITS_IN_JSAMPLE == 8
  70. #define CONST_BITS 13
  71. #define PASS1_BITS 2
  72. #else
  73. #define CONST_BITS 13
  74. #define PASS1_BITS 1 /* lose a little precision to avoid overflow */
  75. #endif
  76. /* Some C compilers fail to reduce "FIX(constant)" at compile time, thus
  77. * causing a lot of useless floating-point operations at run time.
  78. * To get around this we use the following pre-calculated constants.
  79. * If you change CONST_BITS you may want to add appropriate values.
  80. * (With a reasonable C compiler, you can just rely on the FIX() macro...)
  81. */
  82. #if CONST_BITS == 13
  83. #define FIX_0_298631336 ( (INT32) 2446 ) /* FIX(0.298631336) */
  84. #define FIX_0_390180644 ( (INT32) 3196 ) /* FIX(0.390180644) */
  85. #define FIX_0_541196100 ( (INT32) 4433 ) /* FIX(0.541196100) */
  86. #define FIX_0_765366865 ( (INT32) 6270 ) /* FIX(0.765366865) */
  87. #define FIX_0_899976223 ( (INT32) 7373 ) /* FIX(0.899976223) */
  88. #define FIX_1_175875602 ( (INT32) 9633 ) /* FIX(1.175875602) */
  89. #define FIX_1_501321110 ( (INT32) 12299 ) /* FIX(1.501321110) */
  90. #define FIX_1_847759065 ( (INT32) 15137 ) /* FIX(1.847759065) */
  91. #define FIX_1_961570560 ( (INT32) 16069 ) /* FIX(1.961570560) */
  92. #define FIX_2_053119869 ( (INT32) 16819 ) /* FIX(2.053119869) */
  93. #define FIX_2_562915447 ( (INT32) 20995 ) /* FIX(2.562915447) */
  94. #define FIX_3_072711026 ( (INT32) 25172 ) /* FIX(3.072711026) */
  95. #else
  96. #define FIX_0_298631336 FIX( 0.298631336 )
  97. #define FIX_0_390180644 FIX( 0.390180644 )
  98. #define FIX_0_541196100 FIX( 0.541196100 )
  99. #define FIX_0_765366865 FIX( 0.765366865 )
  100. #define FIX_0_899976223 FIX( 0.899976223 )
  101. #define FIX_1_175875602 FIX( 1.175875602 )
  102. #define FIX_1_501321110 FIX( 1.501321110 )
  103. #define FIX_1_847759065 FIX( 1.847759065 )
  104. #define FIX_1_961570560 FIX( 1.961570560 )
  105. #define FIX_2_053119869 FIX( 2.053119869 )
  106. #define FIX_2_562915447 FIX( 2.562915447 )
  107. #define FIX_3_072711026 FIX( 3.072711026 )
  108. #endif
  109. /* Multiply an INT32 variable by an INT32 constant to yield an INT32 result.
  110. * For 8-bit samples with the recommended scaling, all the variable
  111. * and constant values involved are no more than 16 bits wide, so a
  112. * 16x16->32 bit multiply can be used instead of a full 32x32 multiply.
  113. * For 12-bit samples, a full 32-bit multiplication will be needed.
  114. */
  115. #if BITS_IN_JSAMPLE == 8
  116. #define MULTIPLY( var, const ) MULTIPLY16C16( var, const )
  117. #else
  118. #define MULTIPLY( var, const ) ( ( var ) * ( const ) )
  119. #endif
  120. /*
  121. * Perform the forward DCT on one block of samples.
  122. */
  123. GLOBAL void
  124. jpeg_fdct_islow( DCTELEM * data ) {
  125. INT32 tmp0, tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7;
  126. INT32 tmp10, tmp11, tmp12, tmp13;
  127. INT32 z1, z2, z3, z4, z5;
  128. DCTELEM * dataptr;
  129. int ctr;
  130. SHIFT_TEMPS
  131. /* Pass 1: process rows. */
  132. /* Note results are scaled up by sqrt(8) compared to a true DCT; */
  133. /* furthermore, we scale the results by 2**PASS1_BITS. */
  134. dataptr = data;
  135. for ( ctr = DCTSIZE - 1; ctr >= 0; ctr-- ) {
  136. tmp0 = dataptr[0] + dataptr[7];
  137. tmp7 = dataptr[0] - dataptr[7];
  138. tmp1 = dataptr[1] + dataptr[6];
  139. tmp6 = dataptr[1] - dataptr[6];
  140. tmp2 = dataptr[2] + dataptr[5];
  141. tmp5 = dataptr[2] - dataptr[5];
  142. tmp3 = dataptr[3] + dataptr[4];
  143. tmp4 = dataptr[3] - dataptr[4];
  144. /* Even part per LL&M figure 1 --- note that published figure is faulty;
  145. * rotator "sqrt(2)*c1" should be "sqrt(2)*c6".
  146. */
  147. tmp10 = tmp0 + tmp3;
  148. tmp13 = tmp0 - tmp3;
  149. tmp11 = tmp1 + tmp2;
  150. tmp12 = tmp1 - tmp2;
  151. dataptr[0] = (DCTELEM) ( ( tmp10 + tmp11 ) << PASS1_BITS );
  152. dataptr[4] = (DCTELEM) ( ( tmp10 - tmp11 ) << PASS1_BITS );
  153. z1 = MULTIPLY( tmp12 + tmp13, FIX_0_541196100 );
  154. dataptr[2] = (DCTELEM) DESCALE( z1 + MULTIPLY( tmp13, FIX_0_765366865 ),
  155. CONST_BITS - PASS1_BITS );
  156. dataptr[6] = (DCTELEM) DESCALE( z1 + MULTIPLY( tmp12, -FIX_1_847759065 ),
  157. CONST_BITS - PASS1_BITS );
  158. /* Odd part per figure 8 --- note paper omits factor of sqrt(2).
  159. * cK represents cos(K*pi/16).
  160. * i0..i3 in the paper are tmp4..tmp7 here.
  161. */
  162. z1 = tmp4 + tmp7;
  163. z2 = tmp5 + tmp6;
  164. z3 = tmp4 + tmp6;
  165. z4 = tmp5 + tmp7;
  166. z5 = MULTIPLY( z3 + z4, FIX_1_175875602 );/* sqrt(2) * c3 */
  167. tmp4 = MULTIPLY( tmp4, FIX_0_298631336 );/* sqrt(2) * (-c1+c3+c5-c7) */
  168. tmp5 = MULTIPLY( tmp5, FIX_2_053119869 );/* sqrt(2) * ( c1+c3-c5+c7) */
  169. tmp6 = MULTIPLY( tmp6, FIX_3_072711026 );/* sqrt(2) * ( c1+c3+c5-c7) */
  170. tmp7 = MULTIPLY( tmp7, FIX_1_501321110 );/* sqrt(2) * ( c1+c3-c5-c7) */
  171. z1 = MULTIPLY( z1, -FIX_0_899976223 );/* sqrt(2) * (c7-c3) */
  172. z2 = MULTIPLY( z2, -FIX_2_562915447 );/* sqrt(2) * (-c1-c3) */
  173. z3 = MULTIPLY( z3, -FIX_1_961570560 );/* sqrt(2) * (-c3-c5) */
  174. z4 = MULTIPLY( z4, -FIX_0_390180644 );/* sqrt(2) * (c5-c3) */
  175. z3 += z5;
  176. z4 += z5;
  177. dataptr[7] = (DCTELEM) DESCALE( tmp4 + z1 + z3, CONST_BITS - PASS1_BITS );
  178. dataptr[5] = (DCTELEM) DESCALE( tmp5 + z2 + z4, CONST_BITS - PASS1_BITS );
  179. dataptr[3] = (DCTELEM) DESCALE( tmp6 + z2 + z3, CONST_BITS - PASS1_BITS );
  180. dataptr[1] = (DCTELEM) DESCALE( tmp7 + z1 + z4, CONST_BITS - PASS1_BITS );
  181. dataptr += DCTSIZE; /* advance pointer to next row */
  182. }
  183. /* Pass 2: process columns.
  184. * We remove the PASS1_BITS scaling, but leave the results scaled up
  185. * by an overall factor of 8.
  186. */
  187. dataptr = data;
  188. for ( ctr = DCTSIZE - 1; ctr >= 0; ctr-- ) {
  189. tmp0 = dataptr[DCTSIZE * 0] + dataptr[DCTSIZE * 7];
  190. tmp7 = dataptr[DCTSIZE * 0] - dataptr[DCTSIZE * 7];
  191. tmp1 = dataptr[DCTSIZE * 1] + dataptr[DCTSIZE * 6];
  192. tmp6 = dataptr[DCTSIZE * 1] - dataptr[DCTSIZE * 6];
  193. tmp2 = dataptr[DCTSIZE * 2] + dataptr[DCTSIZE * 5];
  194. tmp5 = dataptr[DCTSIZE * 2] - dataptr[DCTSIZE * 5];
  195. tmp3 = dataptr[DCTSIZE * 3] + dataptr[DCTSIZE * 4];
  196. tmp4 = dataptr[DCTSIZE * 3] - dataptr[DCTSIZE * 4];
  197. /* Even part per LL&M figure 1 --- note that published figure is faulty;
  198. * rotator "sqrt(2)*c1" should be "sqrt(2)*c6".
  199. */
  200. tmp10 = tmp0 + tmp3;
  201. tmp13 = tmp0 - tmp3;
  202. tmp11 = tmp1 + tmp2;
  203. tmp12 = tmp1 - tmp2;
  204. dataptr[DCTSIZE * 0] = (DCTELEM) DESCALE( tmp10 + tmp11, PASS1_BITS );
  205. dataptr[DCTSIZE * 4] = (DCTELEM) DESCALE( tmp10 - tmp11, PASS1_BITS );
  206. z1 = MULTIPLY( tmp12 + tmp13, FIX_0_541196100 );
  207. dataptr[DCTSIZE * 2] = (DCTELEM) DESCALE( z1 + MULTIPLY( tmp13, FIX_0_765366865 ),
  208. CONST_BITS + PASS1_BITS );
  209. dataptr[DCTSIZE * 6] = (DCTELEM) DESCALE( z1 + MULTIPLY( tmp12, -FIX_1_847759065 ),
  210. CONST_BITS + PASS1_BITS );
  211. /* Odd part per figure 8 --- note paper omits factor of sqrt(2).
  212. * cK represents cos(K*pi/16).
  213. * i0..i3 in the paper are tmp4..tmp7 here.
  214. */
  215. z1 = tmp4 + tmp7;
  216. z2 = tmp5 + tmp6;
  217. z3 = tmp4 + tmp6;
  218. z4 = tmp5 + tmp7;
  219. z5 = MULTIPLY( z3 + z4, FIX_1_175875602 );/* sqrt(2) * c3 */
  220. tmp4 = MULTIPLY( tmp4, FIX_0_298631336 );/* sqrt(2) * (-c1+c3+c5-c7) */
  221. tmp5 = MULTIPLY( tmp5, FIX_2_053119869 );/* sqrt(2) * ( c1+c3-c5+c7) */
  222. tmp6 = MULTIPLY( tmp6, FIX_3_072711026 );/* sqrt(2) * ( c1+c3+c5-c7) */
  223. tmp7 = MULTIPLY( tmp7, FIX_1_501321110 );/* sqrt(2) * ( c1+c3-c5-c7) */
  224. z1 = MULTIPLY( z1, -FIX_0_899976223 );/* sqrt(2) * (c7-c3) */
  225. z2 = MULTIPLY( z2, -FIX_2_562915447 );/* sqrt(2) * (-c1-c3) */
  226. z3 = MULTIPLY( z3, -FIX_1_961570560 );/* sqrt(2) * (-c3-c5) */
  227. z4 = MULTIPLY( z4, -FIX_0_390180644 );/* sqrt(2) * (c5-c3) */
  228. z3 += z5;
  229. z4 += z5;
  230. dataptr[DCTSIZE * 7] = (DCTELEM) DESCALE( tmp4 + z1 + z3,
  231. CONST_BITS + PASS1_BITS );
  232. dataptr[DCTSIZE * 5] = (DCTELEM) DESCALE( tmp5 + z2 + z4,
  233. CONST_BITS + PASS1_BITS );
  234. dataptr[DCTSIZE * 3] = (DCTELEM) DESCALE( tmp6 + z2 + z3,
  235. CONST_BITS + PASS1_BITS );
  236. dataptr[DCTSIZE * 1] = (DCTELEM) DESCALE( tmp7 + z1 + z4,
  237. CONST_BITS + PASS1_BITS );
  238. dataptr++; /* advance pointer to next column */
  239. }
  240. }
  241. #endif /* DCT_ISLOW_SUPPORTED */