SHARE
TWEET

Loader.c リファクタ 1

Haraken Feb 17th, 2020 (edited) 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # Loader.c 同値変形
  2. # 参考: https://gist.github.com/aycabta/9088471
  3. # 擬似言語
  4.  
  5. # 再帰の書き換えや不要な変数の削除など
  6.  
  7. # P(y, x): yの右端に1を付け、0をx個つける。P(y, x) = (y*2+1)*(2**x) > y
  8. # y-~y<<x = y-(-y-1)<<x = 2*y+1<<x
  9. # P(0x10, 2) = 0x10100
  10. P(y, x): Int := (y << 1 | 1) << x
  11.  
  12. # countTrailingZeros(x): Z(x)。xを2進数で表したときの右端の0の個数を数える。
  13. # countTrailingZeros(5) = countTrailingZeros(0b101) = 0
  14. # countTrailingZeros(8) = countTrailingZeros(0b1000) = 3
  15. countTrailingZeros(x): Int := do
  16.   var zeros := 0
  17.   while (x & 1) == 0
  18.     zeros += 1
  19.     x >>= 1
  20.   return zeros
  21.  
  22. # L(x): xを右端の0の個数+1右シフトして返す
  23. # つまり、xを2進数で表したとき、最も右にある1のビットから右端までを削除する。L(P(y, x)) = y
  24. # x > L(x)
  25. # L(0b10110000) = 0b101
  26. L(x) := x >> (1 + countTrailingZeros(x))
  27.  
  28. S(v, y, c, t) := do
  29.   f: Int := L(t) # f < t
  30.   x: Int := (t != 1) ? 1 : 0
  31.  
  32.   if f > 2
  33.     if f > v
  34.       return t - c
  35.     elif f < v
  36.       return t
  37.     else
  38.       return y
  39.   elif f < 2
  40.     return P(f, P(S(v, y, c, L(x)), S(v + 2, S(4, 0b1101, -4, y), c, countTrailingZeros(x))))
  41.   else
  42.     return A(S(v, y, c, L(x)), S(v, y, c, countTrailingZeros(x))
  43.  
  44. A(y, x): Int := do
  45.   if L(y) != 1
  46.     return 0b101 << P(y, x)
  47.   else
  48.     return S(4, x, 4, 0)
  49.  
  50. # aはD(x)によって書き換えられる
  51. var a: Int := 0
  52.  
  53. D(x): Int := do
  54.   c := 0
  55.   t := 0b111
  56.   u := 0b1110
  57.  
  58.   loop do
  59.     if x != 0
  60.       D(x - 1)
  61.     if (x>>1 & 1) != 0  # xの2ビット目が1なら
  62.       break
  63.     d := L(L(D(x)))
  64.     f := 0
  65.     x := 0
  66.     if c == (L(D(x)) != 1 ? 1 : 0) and L(u) == 0 and f == 0
  67.       x >>= 1
  68.       if (x & 1) == 1
  69.         u = S(4, d, 4, 1)
  70.         t = A(t, d)
  71.         x >>= 1
  72.         if (x&1) == 1 and (f>>1 & 1) == 1  # xの1ビット目とfの2ビット目が1なら
  73.           c = P(d, c)
  74.           t = S(4, 0b1101, -4, t)
  75.           u = S(4, 0b1101, -4, u)
  76.     if c != 0
  77.       x >>= 1
  78.       if (x & 1) != 0
  79.         x >>= 1
  80.         if (~u & 2 | x & 1) != 0
  81.           u = 1 << P(L(c), u)
  82.           t = P(u, P(L(c), t))
  83.         else
  84.           t = P(0, P(L(c), t))
  85.         c = r
  86.     x >>= 1
  87.     if ((x & 1) == 1 and (u>>1 & 1) == 1
  88.       c = P(t, c)
  89.       u = S(4, 0b1101, -4, t)
  90.       t = 0b1001
  91.   a = P(P(t, P(u, P(x, c))), a)
  92.   return a
  93.  
  94. main() := D(D(D(D(D(99)))))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top