src/openpower/decoder/isa/fastdctlee.py

   1 #
   2 # Fast discrete cosine transform algorithms (Python)
   3 #
   4 # Copyright (c) 2020 Project Nayuki. (MIT License)
   5 # https://www.nayuki.io/page/fast-discrete-cosine-transform-algorithms
   6 #
   7 # Permission is hereby granted, free of charge, to any person obtaining a copy of
   8 # this software and associated documentation files (the "Software"), to deal in
   9 # the Software without restriction, including without limitation the rights to
  10 # use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
  11 # the Software, and to permit persons to whom the Software is furnished to do so,
  12 # subject to the following conditions:
  13 # - The above copyright notice and this permission notice shall be included in
  14 #   all copies or substantial portions of the Software.
  15 # - The Software is provided "as is", without warranty of any kind, express or
  16 #   implied, including but not limited to the warranties of merchantability,
  17 #   fitness for a particular purpose and noninfringement. In no event shall the
  18 #   authors or copyright holders be liable for any claim, damages or other
  19 #   liability, whether in an action of contract, tort or otherwise, arising from,
  20 #   out of or in connection with the Software or the use or other dealings in the
  21 #   Software.
  22 #
  23
  24 import math
  25
  26
  27 # DCT type II, unscaled. Algorithm by Byeong Gi Lee, 1984.
  28 # See: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.3056&rep=rep1&type=pdf#page=34
  29 def transform(vector):
  30         n = len(vector)
  31         if n == 1:
  32                 return list(vector)
  33         elif n == 0 or n % 2 != 0:
  34                 raise ValueError()
  35         else:
  36                 half = n // 2
  37                 alpha = [(vector[i] + vector[-(i + 1)]) for i in range(half)]
  38                 beta  = [(vector[i] - vector[-(i + 1)]) / (math.cos((i + 0.5) * math.pi / n) * 2.0)
  39                         for i in range(half)]
  40                 alpha = transform(alpha)
  41                 beta  = transform(beta )
  42                 result = []
  43                 for i in range(half - 1):
  44                         result.append(alpha[i])
  45                         result.append(beta[i] + beta[i + 1])
  46                 result.append(alpha[-1])
  47                 result.append(beta [-1])
  48                 return result
  49
  50
  51 # DCT type III, unscaled. Algorithm by Byeong Gi Lee, 1984.
  52 # See: https://www.nayuki.io/res/fast-discrete-cosine-transform-algorithms/lee-new-algo-discrete-cosine-transform.pdf
  53 def inverse_transform(vector, root=True):
  54         if root:
  55                 vector = list(vector)
  56                 vector[0] /= 2
  57         n = len(vector)
  58         if n == 1:
  59                 return vector
  60         elif n == 0 or n % 2 != 0:
  61                 raise ValueError()
  62         else:
  63                 half = n // 2
  64                 alpha = [vector[0]]
  65                 beta  = [vector[1]]
  66                 for i in range(2, n, 2):
  67                         alpha.append(vector[i])
  68                         beta.append(vector[i - 1] + vector[i + 1])
  69                 inverse_transform(alpha, False)
  70                 inverse_transform(beta , False)
  71                 for i in range(half):
  72                         x = alpha[i]
  73                         y = beta[i] / (math.cos((i + 0.5) * math.pi / n) * 2)
  74                         vector[i] = x + y
  75                         vector[-(i + 1)] = x - y
  76                 return vector