ハードウェアシミュレータその１３

ここまででそれとなく動作するCPUぽい何かはできたのだが、機能を追加していくには8bit固定長の命令では幅が足りない。幅を増やして更なる独自命令セットを作るぐらいなら既存の何かにチャレンジすればいいのではないか、など考えてみて、そもそも既存の何かを作るには足りない回路が山ほどあることに気が付いた。っていうか命令5個しかないし、そりゃそーだ。CPUなめんな。
足りないものを少しずつ追加していくにはやっぱり独自アーキテクチャのほうが都合がよいということで、しばらくはオレオレアーキテクチャで進めることにした。
今回のネタはシフタ。

論理シフト

例えば1bit固定でシフトする回路は、入力と出力の線を1本ずらして接続すればよい。簡単である。2bitシフトする場合は2本ずらす。8bitレジスタで指定ビットシフトする命令を作る場合、左右合わせてこの回路を16個ほど作れば解決である。
以下、生成時にシフトビット数を指定するクラス。論理シフトするとあまったところはLで埋められる。

# 指定ビット論理シフトする(-が左、+が右)
class LogicalShifter
  def initialize(bit_width, n)
    @buf = Buffer.new(bit_width)
    @n = n
  end

  def d=(v)
    @buf.d = Array.new(@buf.o.size) do |i|
      if i - @n < 0 or i - @n >= @buf.o.size
        OutputPin.new(L)
      else
        v[i - @n]
      end
    end
  end

  def o
    @buf.o
  end

  def inspect
    o.map{|o|"#{HLHASH[o.get]}"}.join
  end
end

_vcc = Line.new
_gnd = Line.new
vcc = _vcc.o
gnd = _gnd.o

rshifter = LogicalShifter.new(8, 2)
rshifter.d = [vcc, gnd, gnd, vcc, gnd, gnd, gnd, gnd]
lshifter = LogicalShifter.new(8, -2)
lshifter.d = [vcc, gnd, gnd, vcc, gnd, gnd, gnd, gnd]

_vcc.d = H
_gnd.d = L

p rshifter # LLHLLHLL
p lshifter # LHLLLLLL

算術シフト

算術シフトというのは符号を保存したシフトで、例えば-8(2の補数で0xf8)を右シフトすると-4(2の補数で0xfc)になる。符合を保存するというのは、右シフトの場合にあまったビットに最上位のビットがコピーされることを意味する。プラスの場合や左シフトの場合は0で埋められるので、マイナスの値の右シフトの場合でのみ意味がある。
ところで、算術左シフトについて調べてみると、「符号ビットはそのまま」、と書いてあるサイトが結構多い。
世の中のCPUでは右シフトは算術/論理の命令があっても、左シフトは論理シフトしかない、というものが多い。実際のところ、左シフトに関しては符号を残す必要がないので算術でも論理でも同じロジックになる。なぜかというと、マイナスの値の場合、上位から2ビット目が0だったとしたら、2倍したらオーバーフローするからである。符号を残しても結果の値に意味が無い。
などといいつつ算術シフト回路は左右に対応しておく。

# 指定ビット算術シフトする(-が左、+が右)
class ArithmeticShifter
  def initialize(bit_width, n)
    @buf = Buffer.new(bit_width)
    @n = n
  end

  def d=(v)
    @buf.d = Array.new(@buf.o.size) do |i|
      if i - @n < 0 or i - @n >= @buf.o.size
        if @n > 0 # 右シフトの場合
          v[0]
        else
          OutputPin.new(L)
        end
      else
        v[i - @n]
      end
    end
  end

  def o
    @buf.o
  end

  def inspect
    o.map{|o|"#{HLHASH[o.get]}"}.join
  end
end

_vcc = Line.new
_gnd = Line.new
vcc = _vcc.o
gnd = _gnd.o

rshifter = ArithmeticShifter.new(8, 2)
rshifter.d = [vcc, gnd, gnd, vcc, gnd, gnd, gnd, gnd]
lshifter = ArithmeticShifter.new(8, -2)
lshifter.d = [vcc, gnd, gnd, vcc, gnd, gnd, gnd, gnd]

_vcc.d = H
_gnd.d = L

p rshifter # HHHLLHLL
p lshifter # LHLLLLLL

論理算術共有シフト

16個作るとしても、論理シフトと算術シフトを分けて作ると倍になる。右シフトの場合に左端に埋める値を入力線で渡してもらうようにすると、実行時に論理と算術を指定することができるようになる。論理シフトの場合にL固定、算術シフトの場合は最上位ビットを入力することになる。命令によって接続する線をマルチプレクサで選択してやれば、論理と算術シフト回路は共有できる。これで生成する回路は半分になる。

# 指定ビットシフトする(論理、算術共有)(-が左、+が右)
class Shifter
  def initialize(bit_width, n)
    @buf = Buffer.new(bit_width)
    @n = n
    @sign = Buffer1.new
  end

  def d=(v)
    @buf.d = Array.new(@buf.o.size) do |i|
      if i - @n < 0 
        @sign.o
      elsif i - @n >= @buf.o.size
        OutputPin.new(L)
      else
        v[i - @n]
      end
    end
  end

  # 右シフトの場合、ここに最上位ビットの出力ピンを接続すると算術シフト、L固定にすると論理シフト。
  # 左シフトの場合は使われないのでどっちでもいい。
  def sign=(v)
    @sign.d = v
  end

  def o
    @buf.o
  end

  def inspect
    o.map{|o|"#{HLHASH[o.get]}"}.join
  end
end

_vcc = Line.new
_gnd = Line.new
vcc = _vcc.o
gnd = _gnd.o

rshifter1 = Shifter.new(8, 2)
rshifter1.d = [vcc, gnd, gnd, vcc, gnd, gnd, gnd, gnd]
rshifter1.sign = vcc
rshifter2 = Shifter.new(8, 2)
rshifter2.d = [vcc, gnd, gnd, vcc, gnd, gnd, gnd, gnd]
rshifter2.sign = gnd
lshifter = Shifter.new(8, -2)
lshifter.d = [vcc, gnd, gnd, vcc, gnd, gnd, gnd, gnd]
lshifter.sign = vcc

_vcc.d = H
_gnd.d = L

p rshifter1 # HHHLLHLL
p rshifter2 # LLHLLHLL
p lshifter # LHLLLLLL

テストでは最上位ビットを入力するのが面倒だったので直接指定しちゃってるけども。

バレルシフタ

それでも16個生成するといかにも多い。無駄っぽい。そこで、バレルシフタという回路を構成する。賢い人がいたもんだ。検索するといろいろ出てくるが、ここの資料(pdf)がわかりやすかった。
シフト量も回路に入力して、シフト量のbitの数だけシフタ(シフト量は2の累乗)を構成し、1になってるビットのシフタを通す、というものである。

# バレルシフタ(右シフト限定)
class BarrelShifterRight
  def initialize(shift_bit_width, data_bit_width)
    @shifter = Array.new(shift_bit_width){|i| Shifter.new(data_bit_width, 2**i)}
    @mux = Array.new(shift_bit_width){Mux1_n.new(data_bit_width)}
    @buf = Buffer.new(shift_bit_width)

    # 接続
    shift_bit_width.times do |i|
      @mux[i].s = @buf.o[i]
      if i > 0
        @shifter[i].d = @mux[i-1].o
        @mux[i].d = [@shifter[i].o, @mux[i-1].o]
      end
    end
  end

  def d=(v)
    @shifter[0].d = v
    @mux[0].d = [@shifter[0].o, v]
  end

  def shift=(v)
    @buf.d = v.reverse
  end

  def sign=(v)
    @shifter.each do |s|
      s.sign = v
    end
  end

  def o
    @mux.last.o
  end

  def inspect
    o.map{|o|"#{HLHASH[o.get]}"}.join
  end
end

_vcc = Line.new
_gnd = Line.new
vcc = _vcc.o
gnd = _gnd.o
s0 = Line.new
s1 = Line.new
s2 = Line.new
shift = [s2.o, s1.o, s0.o]

rshifter = BarrelShifterRight.new(shift.size, 8)
rshifter.d = [vcc, gnd, gnd, vcc, gnd, gnd, gnd, gnd]
rshifter.sign = vcc
rshifter.shift = shift

_vcc.d = H
_gnd.d = L

# 4bit右シフト
s0.d = L
s1.d = L
s2.d = H

p rshifter # HHHHHLLH

これならシフタの数はシフト量のビットの数ぶんだけになるので、8bitレジスタの場合は3個で済む。左右あわせても6個だ。すばらしい。さっきのコードは右シフトのみだが、これを2つ突っ込んで、方向ビットも入力して、マルチプレクサで選択してやるようにするとRuby上のオブジェクトは1個になる。

# バレルシフタ
class BarrelShifter
  def initialize(shift_bit_width, data_bit_width)
    # 左シフタ
    @lshifter = Array.new(shift_bit_width){|i| Shifter.new(data_bit_width, -(2**i))}
    @lmux = Array.new(shift_bit_width){Mux1_n.new(data_bit_width)}
    @lbuf = Buffer.new(shift_bit_width)

    # 右シフタ
    @rshifter = Array.new(shift_bit_width){|i| Shifter.new(data_bit_width, 2**i)}
    @rmux = Array.new(shift_bit_width){Mux1_n.new(data_bit_width)}
    @rbuf = Buffer.new(shift_bit_width)

    # 接続
    shift_bit_width.times do |i|
      @lmux[i].s = @lbuf.o[i]
      @rmux[i].s = @rbuf.o[i]
      if i > 0
        @lshifter[i].d = @lmux[i-1].o
        @lmux[i].d = [@lshifter[i].o, @lmux[i-1].o]
        @rshifter[i].d = @rmux[i-1].o
        @rmux[i].d = [@rshifter[i].o, @rmux[i-1].o]
      end
    end

    # 左右選択マルチプレクサ
    @mux = Mux1_n.new(data_bit_width)
    @mux.d = [@rmux.last.o, @lmux.last.o]
  end

  # データ入力
  def d=(v)
    @lshifter[0].d = @rshifter[0].d = v
    @lmux[0].d     = @rmux[0].d     = [@rshifter[0].o, v]
  end

  # シフトビット数
  def shift=(v)
    @lbuf.d = @rbuf.d = v.reverse
  end

  # 算術シフトの場合に最上位に埋められる符号ビット
  def sign=(v)
    @lshifter.each do |s|
      s.sign = v
    end
    @rshifter.each do |s|
      s.sign = v
    end
  end

  # Lが左、Hが右
  def direction=(v)
    @mux.s = v
  end

  def o
    @mux.o
  end

  def inspect
    o.map{|o|"#{HLHASH[o.get]}"}.join
  end
end

_vcc = Line.new
_gnd = Line.new
vcc = _vcc.o
gnd = _gnd.o
s0 = Line.new
s1 = Line.new
s2 = Line.new
shift = [s2.o, s1.o, s0.o]
d0 = Line.new
direction = d0.o

shifter = BarrelShifter.new(shift.size, 8)
shifter.d = [vcc, gnd, gnd, vcc, gnd, gnd, gnd, gnd]
shifter.sign = vcc
shifter.shift = shift
shifter.direction = direction

_vcc.d = H
_gnd.d = L

# 4bit右シフト
s0.d = L
s1.d = L
s2.d = H
d0.d = H
p shifter # HHHHHLLH

# 2bit左シフト
s0.d = L
s1.d = H
s2.d = L
d0.d = L
p shifter # LHLLLLLL

できた。
これで論理シフトと算術シフトの命令を追加してやればシフト命令は完成である。
そういえばバレルシフタを調べるとローテイトさせる回路も出てくるのだが、シフトとローテイトを共有するやり方はよくわからない。よくわからないのでローテイト命令を作る場合はバレルローテイタでも作るか。