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)]) /
  39                  (math.cos((i + 0.5) * math.pi / n) * 2.0)
  40                     for i in range(half)]
  41         alpha = transform(alpha)
  42         beta  = transform(beta )
  43         result = []
  44         for i in range(half - 1):
  45             result.append(alpha[i])
  46             result.append(beta[i] + beta[i + 1])
  47         result.append(alpha[-1])
  48         result.append(beta [-1])
  49         return result
  50
  51
  52 def transform2(vector):
  53     n = len(vector)
  54     if n == 1:
  55         return list(vector)
  56     elif n == 0 or n % 2 != 0:
  57         raise ValueError()
  58     else:
  59         half = n // 2
  60         alpha = [0] * half
  61         beta = [0] * half
  62         for i in range(half):
  63             t1, t2 = vector[i], vector[n-i-1]
  64             k = (math.cos((i + 0.5) * math.pi / n) * 2.0)
  65             alpha[i] = t1 + t2
  66             beta[i] = (t1 - t2) * (1/k)
  67         alpha = transform2(alpha)
  68         beta  = transform2(beta )
  69         result = [0] * n
  70         for i in range(half):
  71             result[i*2] = alpha[i]
  72             result[i*2+1] = beta[i]
  73         for i in range(half - 1):
  74             result[i*2+1] += result[i*2+3]
  75         return result
  76
  77
  78 # DCT type III, unscaled. Algorithm by Byeong Gi Lee, 1984.
  79 # See: https://www.nayuki.io/res/fast-discrete-cosine-transform-algorithms/lee-new-algo-discrete-cosine-transform.pdf
  80 def inverse_transform(vector, root=True, indent=0):
  81     idt = "   " * indent
  82     if root:
  83         vector = list(vector)
  84         vector[0] /= 2
  85     n = len(vector)
  86     if n == 1:
  87         return vector, [0]
  88     elif n == 0 or n % 2 != 0:
  89         raise ValueError()
  90     else:
  91         half = n // 2
  92         alpha = [vector[0]]
  93         beta  = [vector[1]]
  94         for i in range(2, n, 2):
  95             alpha.append(vector[i])
  96             beta.append(vector[i - 1] + vector[i + 1])
  97         print (idt, "n", n, "alpha 0", end=" ")
  98         for i in range(2, n, 2):
  99             print (i, end=" ")
 100         print ("beta 1", end=" ")
 101         for i in range(2, n, 2):
 102             print ("%d+%d" % (i-1, i+1), end=" ")
 103         print()
 104         inverse_transform(alpha, False, indent+1)
 105         inverse_transform(beta , False, indent+1)
 106         for i in range(half):
 107             x = alpha[i]
 108             y = beta[i] / (math.cos((i + 0.5) * math.pi / n) * 2)
 109             vector[i] = x + y
 110             vector[-(i + 1)] = x - y
 111             print (idt, " v[%d] = alpha[%d]+beta[%d]" % (i, i, i))
 112             print (idt, " v[%d] = alpha[%d]-beta[%d]" % (n-i-1, i, i))
 113         return vector
 114
 115
 116 def inverse_transform2(vector, root=True):
 117     n = len(vector)
 118     if root:
 119         vector = list(vector)
 120     if n == 1:
 121         return vector
 122     elif n == 0 or n % 2 != 0:
 123         raise ValueError()
 124     else:
 125         half = n // 2
 126         alpha = [0]
 127         beta  = [1]
 128         for i in range(2, n, 2):
 129             alpha.append(i)
 130             beta.append(("add", i - 1, i + 1))
 131         inverse_transform2(alpha, False)
 132         inverse_transform2(beta , False)
 133         for i in range(half):
 134             x = alpha[i]
 135             y = ("cos", beta[i], i)
 136             vector[i] = ("add", x, y)
 137             vector[-(i + 1)] = ("sub", x, y)
 138         return vector
 139
 140
 141 if __name__ == '__main__':
 142     vector = range(8)
 143     ops = inverse_transform(vector)
 144     print (ops)