libgo/go/image/jpeg/idct.go

   1 // Copyright 2009 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 // This is a Go translation of idct.c from
   6 //
   7 // http://standards.iso.org/ittf/PubliclyAvailableStandards/ISO_IEC_13818-4_2004_Conformance_Testing/Video/verifier/mpeg2decode_960109.tar.gz
   8 //
   9 // which carries the following notice:
  10
  11 /* Copyright (C) 1996, MPEG Software Simulation Group. All Rights Reserved. */
  12
  13 /*
  14  * Disclaimer of Warranty
  15  *
  16  * These software programs are available to the user without any license fee or
  17  * royalty on an "as is" basis.  The MPEG Software Simulation Group disclaims
  18  * any and all warranties, whether express, implied, or statuary, including any
  19  * implied warranties or merchantability or of fitness for a particular
  20  * purpose.  In no event shall the copyright-holder be liable for any
  21  * incidental, punitive, or consequential damages of any kind whatsoever
  22  * arising from the use of these programs.
  23  *
  24  * This disclaimer of warranty extends to the user of these programs and user's
  25  * customers, employees, agents, transferees, successors, and assigns.
  26  *
  27  * The MPEG Software Simulation Group does not represent or warrant that the
  28  * programs furnished hereunder are free of infringement of any third-party
  29  * patents.
  30  *
  31  * Commercial implementations of MPEG-1 and MPEG-2 video, including shareware,
  32  * are subject to royalty fees to patent holders.  Many of these patents are
  33  * general enough such that they are unavoidable regardless of implementation
  34  * design.
  35  *
  36  */
  37
  38 package jpeg
  39
  40 const (
  41         w1 = 2841 // 2048*sqrt(2)*cos(1*pi/16)
  42         w2 = 2676 // 2048*sqrt(2)*cos(2*pi/16)
  43         w3 = 2408 // 2048*sqrt(2)*cos(3*pi/16)
  44         w5 = 1609 // 2048*sqrt(2)*cos(5*pi/16)
  45         w6 = 1108 // 2048*sqrt(2)*cos(6*pi/16)
  46         w7 = 565  // 2048*sqrt(2)*cos(7*pi/16)
  47
  48         w1pw7 = w1 + w7
  49         w1mw7 = w1 - w7
  50         w2pw6 = w2 + w6
  51         w2mw6 = w2 - w6
  52         w3pw5 = w3 + w5
  53         w3mw5 = w3 - w5
  54
  55         r2 = 181 // 256/sqrt(2)
  56 )
  57
  58 // 2-D Inverse Discrete Cosine Transformation, followed by a +128 level shift.
  59 //
  60 // The input coefficients should already have been multiplied by the appropriate quantization table.
  61 // We use fixed-point computation, with the number of bits for the fractional component varying over the
  62 // intermediate stages. The final values are expected to range within [0, 255], after a +128 level shift.
  63 //
  64 // For more on the actual algorithm, see Z. Wang, "Fast algorithms for the discrete W transform and
  65 // for the discrete Fourier transform", IEEE Trans. on ASSP, Vol. ASSP- 32, pp. 803-816, Aug. 1984.
  66 func idct(b *block) {
  67         // Horizontal 1-D IDCT.
  68         for y := 0; y < 8; y++ {
  69                 // If all the AC components are zero, then the IDCT is trivial.
  70                 if b[y*8+1] == 0 && b[y*8+2] == 0 && b[y*8+3] == 0 &&
  71                         b[y*8+4] == 0 && b[y*8+5] == 0 && b[y*8+6] == 0 && b[y*8+7] == 0 {
  72                         dc := b[y*8+0] << 3
  73                         b[y*8+0] = dc
  74                         b[y*8+1] = dc
  75                         b[y*8+2] = dc
  76                         b[y*8+3] = dc
  77                         b[y*8+4] = dc
  78                         b[y*8+5] = dc
  79                         b[y*8+6] = dc
  80                         b[y*8+7] = dc
  81                         continue
  82                 }
  83
  84                 // Prescale.
  85                 x0 := (b[y*8+0] << 11) + 128
  86                 x1 := b[y*8+4] << 11
  87                 x2 := b[y*8+6]
  88                 x3 := b[y*8+2]
  89                 x4 := b[y*8+1]
  90                 x5 := b[y*8+7]
  91                 x6 := b[y*8+5]
  92                 x7 := b[y*8+3]
  93
  94                 // Stage 1.
  95                 x8 := w7 * (x4 + x5)
  96                 x4 = x8 + w1mw7*x4
  97                 x5 = x8 - w1pw7*x5
  98                 x8 = w3 * (x6 + x7)
  99                 x6 = x8 - w3mw5*x6
 100                 x7 = x8 - w3pw5*x7
 101
 102                 // Stage 2.
 103                 x8 = x0 + x1
 104                 x0 -= x1
 105                 x1 = w6 * (x3 + x2)
 106                 x2 = x1 - w2pw6*x2
 107                 x3 = x1 + w2mw6*x3
 108                 x1 = x4 + x6
 109                 x4 -= x6
 110                 x6 = x5 + x7
 111                 x5 -= x7
 112
 113                 // Stage 3.
 114                 x7 = x8 + x3
 115                 x8 -= x3
 116                 x3 = x0 + x2
 117                 x0 -= x2
 118                 x2 = (r2*(x4+x5) + 128) >> 8
 119                 x4 = (r2*(x4-x5) + 128) >> 8
 120
 121                 // Stage 4.
 122                 b[8*y+0] = (x7 + x1) >> 8
 123                 b[8*y+1] = (x3 + x2) >> 8
 124                 b[8*y+2] = (x0 + x4) >> 8
 125                 b[8*y+3] = (x8 + x6) >> 8
 126                 b[8*y+4] = (x8 - x6) >> 8
 127                 b[8*y+5] = (x0 - x4) >> 8
 128                 b[8*y+6] = (x3 - x2) >> 8
 129                 b[8*y+7] = (x7 - x1) >> 8
 130         }
 131
 132         // Vertical 1-D IDCT.
 133         for x := 0; x < 8; x++ {
 134                 // Similar to the horizontal 1-D IDCT case, if all the AC components are zero, then the IDCT is trivial.
 135                 // However, after performing the horizontal 1-D IDCT, there are typically non-zero AC components, so
 136                 // we do not bother to check for the all-zero case.
 137
 138                 // Prescale.
 139                 y0 := (b[8*0+x] << 8) + 8192
 140                 y1 := b[8*4+x] << 8
 141                 y2 := b[8*6+x]
 142                 y3 := b[8*2+x]
 143                 y4 := b[8*1+x]
 144                 y5 := b[8*7+x]
 145                 y6 := b[8*5+x]
 146                 y7 := b[8*3+x]
 147
 148                 // Stage 1.
 149                 y8 := w7*(y4+y5) + 4
 150                 y4 = (y8 + w1mw7*y4) >> 3
 151                 y5 = (y8 - w1pw7*y5) >> 3
 152                 y8 = w3*(y6+y7) + 4
 153                 y6 = (y8 - w3mw5*y6) >> 3
 154                 y7 = (y8 - w3pw5*y7) >> 3
 155
 156                 // Stage 2.
 157                 y8 = y0 + y1
 158                 y0 -= y1
 159                 y1 = w6*(y3+y2) + 4
 160                 y2 = (y1 - w2pw6*y2) >> 3
 161                 y3 = (y1 + w2mw6*y3) >> 3
 162                 y1 = y4 + y6
 163                 y4 -= y6
 164                 y6 = y5 + y7
 165                 y5 -= y7
 166
 167                 // Stage 3.
 168                 y7 = y8 + y3
 169                 y8 -= y3
 170                 y3 = y0 + y2
 171                 y0 -= y2
 172                 y2 = (r2*(y4+y5) + 128) >> 8
 173                 y4 = (r2*(y4-y5) + 128) >> 8
 174
 175                 // Stage 4.
 176                 b[8*0+x] = (y7 + y1) >> 14
 177                 b[8*1+x] = (y3 + y2) >> 14
 178                 b[8*2+x] = (y0 + y4) >> 14
 179                 b[8*3+x] = (y8 + y6) >> 14
 180                 b[8*4+x] = (y8 - y6) >> 14
 181                 b[8*5+x] = (y0 - y4) >> 14
 182                 b[8*6+x] = (y3 - y2) >> 14
 183                 b[8*7+x] = (y7 - y1) >> 14
 184         }
 185
 186         // Level shift.
 187         for i := range *b {
 188                 b[i] += 128
 189         }
 190 }