jfdctint.c 11 KB

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