Elementary school multiplication in avo.

README.md

Elementary school multiplication in avo.

asm.go

// +build ignore

package main

import (
	"errors"
	"flag"
	"fmt"
	"log"
	"strconv"
	"strings"

	. "github.com/mmcloughlin/avo/build"
	. "github.com/mmcloughlin/avo/operand"
	. "github.com/mmcloughlin/avo/reg"
)

var (
	sizeslist = flag.String("sizes", "3x2", "sizes to generate (for example \"3x2,2x4\")")
)

type size struct{ m, n int }

func parsesizes(list string) ([]size, error) {
	var sizes []size
	for _, part := range strings.Split(list, ",") {
		pair := strings.Split(part, "x")
		if len(pair) != 2 {
			return nil, errors.New("expected two numbers joined by 'x'")
		}
		m, err := strconv.Atoi(pair[0])
		if err != nil {
			return nil, err
		}
		n, err := strconv.Atoi(pair[1])
		if err != nil {
			return nil, err
		}
		sizes = append(sizes, size{m, n})
	}
	return sizes, nil
}

func main() {
	flag.Parse()
	sizes, err := parsesizes(*sizeslist)
	if err != nil {
		log.Fatal(err)
	}

	for _, s := range sizes {
		buildmul(s.m, s.n)
	}

	Generate()
}

func buildmul(m, n int) {
	name := fmt.Sprintf("Mul%dx%d", 64*m, 64*n)
	sig := fmt.Sprintf("func(x [%d]uint64, y [%d]uint64) [%d]uint64", m, n, m+n)
	TEXT(name, 0, sig)
	Doc(fmt.Sprintf("%s computes x*y for %d-bit x and %d-bit y. ", name, 64*m, 64*n))

	// Load operands.
	var x, y []Register
	for i := 0; i < m; i++ {
		x = append(x, Load(Param("x").Index(i), GP64()))
	}
	for i := 0; i < n; i++ {
		y = append(y, Load(Param("y").Index(i), GP64()))
	}

	// Generate multiplication instructions.
	p := mul(x, y)

	// Store result.
	for i, r := range p {
		Store(r, ReturnIndex(0).Index(i))
	}

	RET()
}

func mul(x, y []Register) []Register {
	m, n := len(x), len(y)

	// Allocate registers for the product.
	p := make([]Register, m+n)
	for i := 0; i < m+n; i++ {
		p[i] = GP64()
	}

	// Initialize product registers to zero.
	for _, r := range p {
		XORQ(r, r)
	}

	for ix, lx := range x {
		for iy, ly := range y {
			MOVQ(lx, RAX)
			MULQ(ly)
			ADDQ(RAX, p[ix+iy])
			ADCQ(RDX, p[ix+iy+1])
			if ix+iy+2 < m+n {
				ADCQ(Imm(0), p[ix+iy+2])
			}
		}
	}

	return p
}

gen.go

package mulavo

//go:generate go run asm.go -sizes=1x1,2x2,3x3 -out=mul.s -stubs=stubs.go

mul.s

// Code generated by command: go run asm.go -sizes=1x1,2x2,3x3 -out=mul.s -stubs=stubs.go. DO NOT EDIT.

// func Mul64x64(x [1]uint64, y [1]uint64) [2]uint64
TEXT ·Mul64x64(SB), $0-32
	MOVQ x_0+0(FP), AX
	MOVQ y_0+8(FP), DX
	XORQ CX, CX
	XORQ BX, BX
	MOVQ AX, AX
	MULQ DX
	ADDQ AX, CX
	ADCQ DX, BX
	MOVQ CX, ret_0+16(FP)
	MOVQ BX, ret_1+24(FP)
	RET

// func Mul128x128(x [2]uint64, y [2]uint64) [4]uint64
TEXT ·Mul128x128(SB), $0-64
	MOVQ x_0+0(FP), CX
	MOVQ x_1+8(FP), BX
	MOVQ y_0+16(FP), BP
	MOVQ y_1+24(FP), SI
	XORQ DI, DI
	XORQ R8, R8
	XORQ R9, R9
	XORQ R10, R10
	MOVQ CX, AX
	MULQ BP
	ADDQ AX, DI
	ADCQ DX, R8
	ADCQ $0x00, R9
	MOVQ CX, AX
	MULQ SI
	ADDQ AX, R8
	ADCQ DX, R9
	ADCQ $0x00, R10
	MOVQ BX, AX
	MULQ BP
	ADDQ AX, R8
	ADCQ DX, R9
	ADCQ $0x00, R10
	MOVQ BX, AX
	MULQ SI
	ADDQ AX, R9
	ADCQ DX, R10
	MOVQ DI, ret_0+32(FP)
	MOVQ R8, ret_1+40(FP)
	MOVQ R9, ret_2+48(FP)
	MOVQ R10, ret_3+56(FP)
	RET

// func Mul192x192(x [3]uint64, y [3]uint64) [6]uint64
TEXT ·Mul192x192(SB), $0-96
	MOVQ x_0+0(FP), CX
	MOVQ x_1+8(FP), BX
	MOVQ x_2+16(FP), BP
	MOVQ y_0+24(FP), SI
	MOVQ y_1+32(FP), DI
	MOVQ y_2+40(FP), R8
	XORQ R9, R9
	XORQ R10, R10
	XORQ R11, R11
	XORQ R12, R12
	XORQ R13, R13
	XORQ R14, R14
	MOVQ CX, AX
	MULQ SI
	ADDQ AX, R9
	ADCQ DX, R10
	ADCQ $0x00, R11
	MOVQ CX, AX
	MULQ DI
	ADDQ AX, R10
	ADCQ DX, R11
	ADCQ $0x00, R12
	MOVQ CX, AX
	MULQ R8
	ADDQ AX, R11
	ADCQ DX, R12
	ADCQ $0x00, R13
	MOVQ BX, AX
	MULQ SI
	ADDQ AX, R10
	ADCQ DX, R11
	ADCQ $0x00, R12
	MOVQ BX, AX
	MULQ DI
	ADDQ AX, R11
	ADCQ DX, R12
	ADCQ $0x00, R13
	MOVQ BX, AX
	MULQ R8
	ADDQ AX, R12
	ADCQ DX, R13
	ADCQ $0x00, R14
	MOVQ BP, AX
	MULQ SI
	ADDQ AX, R11
	ADCQ DX, R12
	ADCQ $0x00, R13
	MOVQ BP, AX
	MULQ DI
	ADDQ AX, R12
	ADCQ DX, R13
	ADCQ $0x00, R14
	MOVQ BP, AX
	MULQ R8
	ADDQ AX, R13
	ADCQ DX, R14
	MOVQ R9, ret_0+48(FP)
	MOVQ R10, ret_1+56(FP)
	MOVQ R11, ret_2+64(FP)
	MOVQ R12, ret_3+72(FP)
	MOVQ R13, ret_4+80(FP)
	MOVQ R14, ret_5+88(FP)
	RET

mul_test.go

package mulavo

import (
	"encoding/binary"
	"math/big"
	"math/bits"
	"testing"
	"testing/quick"
)

func TestMul64x64(t *testing.T) {
	expect := func(x, y [1]uint64) [2]uint64 {
		hi, lo := bits.Mul64(x[0], y[0])
		return [2]uint64{lo, hi}
	}
	if err := quick.CheckEqual(Mul64x64, expect, nil); err != nil {
		t.Fatal(err)
	}
}

func TestMul128x128(t *testing.T) {
	expect := func(x, y [2]uint64) (product [4]uint64) {
		p := MulReference(x[:], y[:])
		copy(product[:], p)
		return
	}
	if err := quick.CheckEqual(Mul128x128, expect, nil); err != nil {
		t.Fatal(err)
	}
}

func TestMul192x192(t *testing.T) {
	expect := func(x, y [3]uint64) (product [6]uint64) {
		p := MulReference(x[:], y[:])
		copy(product[:], p)
		return
	}
	if err := quick.CheckEqual(Mul192x192, expect, nil); err != nil {
		t.Fatal(err)
	}
}

func MulReference(x, y []uint64) []uint64 {
	bx, by := tobig(x), tobig(y)
	bp := new(big.Int)
	bp.Mul(bx, by)
	return frombig(bp)
}

func tobig(x []uint64) *big.Int {
	bigx := big.NewInt(0)
	bigx.SetBytes(tobytes(x))
	return bigx
}

func frombig(x *big.Int) []uint64 {
	return frombytes(x.Bytes())
}

func tobytes(x []uint64) []byte {
	n := len(x)
	b := make([]byte, 8*n)
	for i := 0; i < n; i++ {
		binary.BigEndian.PutUint64(b[8*i:], x[n-1-i])
	}
	return b
}

func frombytes(b []byte) []uint64 {
	n := (len(b) + 7) / 8
	x := make([]uint64, n)
	for i := 0; i < len(b); i++ {
		d := b[len(b)-1-i]
		x[i/8] |= uint64(d) << uint(8*(i%8))
	}
	return x
}

stubs.go

// Code generated by command: go run asm.go -sizes=1x1,2x2,3x3 -out=mul.s -stubs=stubs.go. DO NOT EDIT.

package mulavo

// Mul64x64 computes x*y for 64-bit x and 64-bit y. 
func Mul64x64(x [1]uint64, y [1]uint64) [2]uint64

// Mul128x128 computes x*y for 128-bit x and 128-bit y. 
func Mul128x128(x [2]uint64, y [2]uint64) [4]uint64

// Mul192x192 computes x*y for 192-bit x and 192-bit y. 
func Mul192x192(x [3]uint64, y [3]uint64) [6]uint64