asm-calc/x64/simulate.go

package x64

import (
	"errors"
	"fmt"
)

// Errors the simulator can report. They mirror what the real CPU would do:
// division by zero raises #DE, and overflowing the quotient also raises #DE.
var (
	ErrDivideByZero = errors.New("x64: divide error (division by zero)")
	ErrOverflow     = errors.New("x64: divide error (quotient overflow)")
	ErrStack        = errors.New("x64: stack underflow")
)

// Machine is a simulated x86-64 with the subset of state the calculator
// uses.
type Machine struct {
	regs  map[Register]int64
	stack []int64
	// memory is addressed by (base register, offset), which is enough for
	// the frame-relative accesses the compiler emits.
	memory map[string]int64
	// MaxSteps bounds execution so a malformed program cannot hang.
	MaxSteps int
}

// NewMachine returns a machine with zeroed registers.
func NewMachine() *Machine {
	m := &Machine{
		regs:     map[Register]int64{},
		memory:   map[string]int64{},
		MaxSteps: 1 << 20,
	}
	for _, r := range []Register{RAX, RBX, RCX, RDX, RSI, RDI, RBP, RSP, R8, R9, R10, R11} {
		m.regs[r] = 0
	}
	return m
}

// Get reads a register.
func (m *Machine) Get(r Register) int64 { return m.regs[r] }

// Set writes a register.
func (m *Machine) Set(r Register, v int64) { m.regs[r] = v }

// SetMem writes a memory location.
func (m *Machine) SetMem(base Register, offset int, v int64) {
	m.memory[memKey(base, offset)] = v
}

// GetMem reads a memory location.
func (m *Machine) GetMem(base Register, offset int) int64 {
	return m.memory[memKey(base, offset)]
}

func memKey(base Register, offset int) string {
	return fmt.Sprintf("%s%+d", base, offset)
}

// Run executes the program, returning the value left in RAX — the standard
// return register, and where the calculator leaves its result.
func (m *Machine) Run(p Program) (int64, error) {
	steps := 0
	for _, ins := range p {
		steps++
		if steps > m.MaxSteps {
			return 0, fmt.Errorf("x64: exceeded %d instructions", m.MaxSteps)
		}
		if err := m.exec(ins); err != nil {
			return 0, err
		}
	}
	return m.regs[RAX], nil
}

func (m *Machine) exec(ins Instruction) error {
	switch ins.Op {
	case MOV:
		if err := m.wantOperands(ins, 2); err != nil {
			return err
		}
		return m.store(ins.Operands[0], m.load(ins.Operands[1]))

	case ADD:
		if err := m.wantOperands(ins, 2); err != nil {
			return err
		}
		return m.store(ins.Operands[0], m.load(ins.Operands[0])+m.load(ins.Operands[1]))

	case SUB:
		if err := m.wantOperands(ins, 2); err != nil {
			return err
		}
		return m.store(ins.Operands[0], m.load(ins.Operands[0])-m.load(ins.Operands[1]))

	case IMUL:
		if err := m.wantOperands(ins, 2); err != nil {
			return err
		}
		return m.store(ins.Operands[0], m.load(ins.Operands[0])*m.load(ins.Operands[1]))

	case NEG:
		if err := m.wantOperands(ins, 1); err != nil {
			return err
		}
		return m.store(ins.Operands[0], -m.load(ins.Operands[0]))

	case CQO:
		// Sign-extend RAX into RDX:RAX. idiv divides the 128-bit RDX:RAX
		// pair, so without this a negative dividend is divided against a
		// garbage high half and the result is wrong.
		if m.regs[RAX] < 0 {
			m.regs[RDX] = -1
		} else {
			m.regs[RDX] = 0
		}
		return nil

	case IDIV:
		if err := m.wantOperands(ins, 1); err != nil {
			return err
		}
		divisor := m.load(ins.Operands[0])
		if divisor == 0 {
			return ErrDivideByZero
		}
		dividend := m.regs[RAX]
		// The one case where the quotient does not fit: the most negative
		// value divided by -1. A real CPU raises #DE here rather than
		// wrapping, and Go would panic.
		if dividend == -1<<63 && divisor == -1 {
			return ErrOverflow
		}
		quotient := dividend / divisor
		remainder := dividend % divisor
		m.regs[RAX] = quotient
		m.regs[RDX] = remainder
		return nil

	case PUSH:
		if err := m.wantOperands(ins, 1); err != nil {
			return err
		}
		m.stack = append(m.stack, m.load(ins.Operands[0]))
		return nil

	case POP:
		if err := m.wantOperands(ins, 1); err != nil {
			return err
		}
		if len(m.stack) == 0 {
			return ErrStack
		}
		v := m.stack[len(m.stack)-1]
		m.stack = m.stack[:len(m.stack)-1]
		return m.store(ins.Operands[0], v)

	case XCHG:
		if err := m.wantOperands(ins, 2); err != nil {
			return err
		}
		a, b := m.load(ins.Operands[0]), m.load(ins.Operands[1])
		if err := m.store(ins.Operands[0], b); err != nil {
			return err
		}
		return m.store(ins.Operands[1], a)

	case RET:
		return nil

	default:
		return fmt.Errorf("x64: unsupported instruction %q", ins.Op)
	}
}

func (m *Machine) wantOperands(ins Instruction, n int) error {
	if len(ins.Operands) != n {
		return fmt.Errorf("x64: %s takes %d operand(s), got %d", ins.Op, n, len(ins.Operands))
	}
	return nil
}

func (m *Machine) load(o Operand) int64 {
	switch {
	case o.IsImm:
		return o.Imm
	case o.IsMem:
		return m.GetMem(o.Base, o.Offset)
	default:
		return m.regs[o.Reg]
	}
}

func (m *Machine) store(o Operand, v int64) error {
	switch {
	case o.IsImm:
		return fmt.Errorf("x64: cannot write to an immediate")
	case o.IsMem:
		m.SetMem(o.Base, o.Offset, v)
		return nil
	default:
		if _, ok := m.regs[o.Reg]; !ok {
			return fmt.Errorf("x64: unknown register %q", o.Reg)
		}
		m.regs[o.Reg] = v
		return nil
	}
}

// StackDepth reports how many values are on the simulated stack. A
// well-formed program balances its pushes and pops, so this should be zero
// at the end.
func (m *Machine) StackDepth() int { return len(m.stack) }