Loader.c リファクタ 1

# Loader.c 同値変形
# 参考: https://gist.github.com/aycabta/9088471
# 擬似言語

# 再帰の書き換えや不要な変数の削除など

# P(y, x): yの右端に1を付け、0をx個つける。P(y, x) = (y*2+1)*(2**x) > y
# y-~y<<x = y-(-y-1)<<x = 2*y+1<<x
# P(0x10, 2) = 0x10100
P(y, x): Int := (y << 1 | 1) << x

# countTrailingZeros(x): Z(x)。xを2進数で表したときの右端の0の個数を数える。
# countTrailingZeros(5) = countTrailingZeros(0b101) = 0
# countTrailingZeros(8) = countTrailingZeros(0b1000) = 3
countTrailingZeros(x): Int := do
  var zeros := 0
  while (x & 1) == 0
    zeros += 1
    x >>= 1
  return zeros

# L(x): xを右端の0の個数+1右シフトして返す
# つまり、xを2進数で表したとき、最も右にある1のビットから右端までを削除する。L(P(y, x)) = y
# x > L(x)
# L(0b10110000) = 0b101
L(x) := x >> (1 + countTrailingZeros(x))

S(v, y, c, t) := do
  f: Int := L(t) # f < t
  x: Int := (t != 1) ? 1 : 0

  if f > 2
    if f > v
      return t - c
    elif f < v
      return t
    else
      return y
  elif f < 2
    return P(f, P(S(v, y, c, L(x)), S(v + 2, S(4, 0b1101, -4, y), c, countTrailingZeros(x))))
  else
    return A(S(v, y, c, L(x)), S(v, y, c, countTrailingZeros(x))

A(y, x): Int := do
  if L(y) != 1
    return 0b101 << P(y, x)
  else
    return S(4, x, 4, 0)

# aはD(x)によって書き換えられる
var a: Int := 0

D(x): Int := do
  c := 0
  t := 0b111
  u := 0b1110

  loop do
    if x != 0
      D(x - 1)
    if (x>>1 & 1) != 0  # xの2ビット目が1なら
      break
    d := L(L(D(x)))
    f := 0
    x := 0
    if c == (L(D(x)) != 1 ? 1 : 0) and L(u) == 0 and f == 0
      x >>= 1
      if (x & 1) == 1
        u = S(4, d, 4, 1)
        t = A(t, d)
        x >>= 1
        if (x&1) == 1 and (f>>1 & 1) == 1  # xの1ビット目とfの2ビット目が1なら
          c = P(d, c)
          t = S(4, 0b1101, -4, t)
          u = S(4, 0b1101, -4, u)
    if c != 0
      x >>= 1
      if (x & 1) != 0
        x >>= 1
        if (~u & 2 | x & 1) != 0
          u = 1 << P(L(c), u)
          t = P(u, P(L(c), t))
        else
          t = P(0, P(L(c), t))
        c = r
    x >>= 1
    if ((x & 1) == 1 and (u>>1 & 1) == 1
      c = P(t, c)
      u = S(4, 0b1101, -4, t)
      t = 0b1001
  a = P(P(t, P(u, P(x, c))), a)
  return a

main() := D(D(D(D(D(99)))))