x86/x86map/map.go

// Copyright 2014 The Go Authors.  All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// X86map constructs the x86 opcode map from the instruction set CSV file.
//
// Usage:
//	x86map [-fmt=format] x86.csv
//
// The known output formats are:
//
//  text (default) - print decoding tree in text form
//  decoder - print decoding tables for the x86asm package
//  scanner - print scanning tables for x86scan package
package main

import (
	"bufio"
	"bytes"
	"encoding/csv"
	"flag"
	"fmt"
	"io"
	"log"
	"os"
	"sort"
	"strconv"
	"strings"
)

var format = flag.String("fmt", "text", "output format: text, decoder")

var inputFile string

func usage() {
	fmt.Fprintf(os.Stderr, "usage: x86map [-fmt=format] x86.csv\n")
	os.Exit(2)
}

func main() {
	log.SetFlags(0)
	log.SetPrefix("x86map: ")

	flag.Usage = usage
	flag.Parse()
	if flag.NArg() != 1 {
		usage()
	}

	inputFile = flag.Arg(0)

	var print func(*Prog)
	switch *format {
	default:
		log.Fatalf("unknown output format %q", *format)
	case "text":
		print = printText
	case "decoder":
		print = printDecoder
	case "scanner":
		print = printScanner
	}

	p, err := readCSV(flag.Arg(0))
	if err != nil {
		log.Fatal(err)
	}

	//p = mergeTail(p)

	print(p)
}

// readCSV reads the CSV file and returns the corresponding Prog.
// It may print details about problems to standard error using the log package.
func readCSV(file string) (*Prog, error) {
	// Read input.
	// Skip leading blank and # comment lines.
	f, err := os.Open(file)
	if err != nil {
		return nil, err
	}
	b := bufio.NewReader(f)
	for {
		c, err := b.ReadByte()
		if err != nil {
			break
		}
		if c == '\n' {
			continue
		}
		if c == '#' {
			b.ReadBytes('\n')
			continue
		}
		b.UnreadByte()
		break
	}
	table, err := csv.NewReader(b).ReadAll()
	if err != nil {
		return nil, fmt.Errorf("parsing %s: %v", file, err)
	}
	if len(table) == 0 {
		return nil, fmt.Errorf("empty csv input")
	}
	if len(table[0]) < 6 {
		return nil, fmt.Errorf("csv too narrow: need at least six columns")
	}

	p := &Prog{}
	for _, row := range table {
		add(p, row[0], row[1], row[2], row[3], row[4], row[5])
	}

	check(p)

	return p, nil
}

// A Prog is a single node in the tree representing the instruction format.
// Collectively the tree of nodes form a kind of program for decoding.
// Each Prog has a single action, identifying the kind of node it is,
// and then children to be executed according to the action.
// For example, the Prog with Action="decode" has children named for each
// possible next byte in the input, and those children are the decoding
// tree to execute for the corresponding bytes.
type Prog struct {
	Path   string
	Action string
	Child  map[string]*Prog
	PC     int
	TailID int
}

// keys returns the child keys in sorted order.
func (p *Prog) keys() []string {
	var keys []string
	for key := range p.Child {
		keys = append(keys, key)
	}
	sort.Strings(keys)
	return keys
}

// findChildLeaf finds a leaf node in the subtree rooted at p
// and returns that node's full path. The path is useful in error
// messages as an example of where a particular subtree is headed.
func (p *Prog) findChildLeaf() string {
	for {
		if len(p.Child) == 0 {
			return p.Path
		}
		p = p.Child[p.keys()[0]]
	}
}

// walk advances from p to apply the given action and key.
// If p has no action yet, the action is recorded as p.Action.
// Otherwise the action must match p's action: every node in the
// tree can have at most one action, although possibly with many
// alternative keys.
// If p already has an alternative with the given key, walk returns
// that preexisting subtree. Otherwise walk allocates a new Prog
// representing that subtree and returns that node.
func (p *Prog) walk(action, key, text, opcode string) *Prog {
	if p.Action == "" {
		p.Action = action
	} else if p.Action != action {
		log.Printf("%s; %s: conflicting paths %s and %s|%s %s\n", text, opcode, p.findChildLeaf(), p.Path, action, key)
		return new(Prog)
	}
	q := p.Child[key]
	if q == nil {
		if p.Child == nil {
			p.Child = make(map[string]*Prog)
		}
		q = new(Prog)
		q.Path = fmt.Sprintf("%s|%s %s", p.Path, action, key)
		p.Child[key] = q
	}
	return q
}

// add adds a single instructions to the tree rooted at root.
// The string arguments match the CSV: instruction mnemonic,
// opcode encoding, validity in 32- and 64-bit modes, CPUID
// feature set (ignored), and additional tags.
//
// In effect, add adds a new path through the tree leading to
// the given instruction, but it reuses as much of the existing
// tree structure as possible. For example if there have already
// been instructions added starting with 0F and this instruction
// also starts with 0F, that 0F subtree node is reused instead of
// allocating a parallel one. To maximize the reuse, the check action
// sequence along the path being added is the same for every instruction:
// encoding pieces needed to make a decision, 64-bit mode check,
// rex check, prefix check, address size check, data size check,
// register vs memory argument check. Once all those checks have
// been applied, the assumption is that we have uniquely identified
// an instruction, and at that point it is okay to diverge from the
// uniform pattern to set the opcode and read the specific arguments
// corresponding to the instruction at hand.
//
// The maximimal reuse of the existing tree means that the tree
// resulting from all adds have been done amounts to a decision tree.
// There is one detail that makes it non-deterministic: some checks
// do not matter to some instructions and those are recorded as "any" keys.
// If you are decoding and there is a key for the specific thing you are
// seeing as well as the "any" key, both must be considered. To avoid
// adding complexity to the decoder execution, the 'check' function
// removes this case by merging "any" trees into specific keys when
// present.
func add(root *Prog, text, opcode, valid32, valid64, cpuid, tags string) {
	// These are not real instructions: they are either
	// prefixes for other instructions, composite instructions
	// built from multiple individual instructions, or alternate
	// mnemonics of other encodings.
	// Discard for disassembly, because we want a unique decoding.
	if strings.Contains(tags, "pseudo") {
		return
	}

	// Treat REX.W + opcode as being like having an "operand64" tag.
	// The REX.W flag sets the operand size to 64 bits; in this way it is
	// not much different than the 66 prefix that inverts 32 vs 16 bits.
	if strings.Contains(opcode, "REX.W") {
		if !strings.Contains(tags, "operand64") {
			if tags != "" {
				tags += ","
			}
			tags += "operand64"
		}
	}

	// If there is more than one operand size given, we need to do
	// a separate add for each size, because we need multiple
	// keys to be added in the operand size branch, and the code makes
	// a linear pass through the tree adding just one key to each node.
	// We would need to do the same for any other possible repeated tag
	// (for example, if an instruction could have multiple address sizes)
	// but so far operand size is the only tag we have needed to repeat.
	if strings.Count(tags, "operand") > 1 {
		f := strings.Split(tags, ",")
		var ops []string
		w := 0
		for _, tag := range f {
			if strings.HasPrefix(tag, "operand") {
				ops = append(ops, tag)
			} else {
				if strings.Contains(tag, "operand") {
					log.Fatalf("unknown tag %q", tag)
				}
				f[w] = tag
				w++
			}
		}
		f = f[:w]
		for _, op := range ops {
			add(root, text, opcode, valid32, valid64, cpuid, strings.Join(append(f, op), ","))
		}
		return
	}

	p := root
	walk := func(action, item string) {
		p = p.walk(action, item, text, opcode)
	}

	// Ignore VEX instructions for now.
	if strings.HasPrefix(opcode, "VEX") {
		if !strings.HasPrefix(text, "VMOVNTDQ") &&
			!strings.HasPrefix(text, "VMOVDQA") &&
			!strings.HasPrefix(text, "VMOVDQU") &&
			!strings.HasPrefix(text, "VZEROUPPER") {
			return
		}
		if !strings.HasPrefix(opcode, "VEX.256") && !strings.HasPrefix(text, "VZEROUPPER") {
			return
		}
		if !strings.Contains(tags, "VEXC4") {
			add(root, text, opcode, valid32, valid64, cpuid, tags+",VEXC4")
		}
		encoding := strings.Fields(opcode)
		walk("decode", encoding[1])
		walk("is64", "any")
		if strings.Contains(tags, "VEXC4") {
			walk("prefix", "C4")
		} else {
			walk("prefix", "C5")
		}
		for _, pref := range strings.Split(encoding[0], ".") {
			if isVexEncodablePrefix[pref] {
				walk("prefix", pref)
			}
		}
	}

	var rex, prefix string
	encoding := strings.Fields(opcode)
	if len(encoding) > 0 && strings.HasPrefix(encoding[0], "REX") {
		rex = encoding[0]
		encoding = encoding[1:]
		if len(encoding) > 0 && encoding[0] == "+" {
			encoding = encoding[1:]
		}
	}
	if len(encoding) > 0 && isPrefix[encoding[0]] {
		prefix = encoding[0]
		encoding = encoding[1:]
	}
	if rex == "" && len(encoding) > 0 && strings.HasPrefix(encoding[0], "REX") {
		rex = encoding[0]
		if rex == "REX" {
			log.Printf("REX without REX.W: %s %s", text, opcode)
		}
		encoding = encoding[1:]
		if len(encoding) > 0 && encoding[0] == "+" {
			encoding = encoding[1:]
		}
	}
	if len(encoding) > 0 && isPrefix[encoding[0]] {
		log.Printf("%s %s: too many prefixes", text, opcode)
		return
	}

	var haveModRM, havePlus bool
	var usedReg string
	for len(encoding) > 0 && (isHex(encoding[0]) || isSlashNum(encoding[0])) {
		key := encoding[0]
		if isSlashNum(key) {
			if usedReg != "" {
				log.Printf("%s %s: multiple modrm checks", text, opcode)
			}
			haveModRM = true
			usedReg = key
		}
		if i := strings.Index(key, "+"); i >= 0 {
			key = key[:i+1]
			havePlus = true
		}
		walk("decode", key)
		encoding = encoding[1:]
	}

	if valid32 != "V" {
		walk("is64", "1")
	} else if valid64 != "V" {
		walk("is64", "0")
	} else {
		walk("is64", "any")
	}

	if prefix == "" {
		prefix = "0"
	}
	walk("prefix", prefix)

	if strings.Contains(tags, "address16") {
		walk("addrsize", "16")
	} else if strings.Contains(tags, "address32") {
		walk("addrsize", "32")
	} else if strings.Contains(tags, "address64") {
		walk("addrsize", "64")
	} else {
		walk("addrsize", "any")
	}

	if strings.Contains(tags, "operand16") {
		walk("datasize", "16")
	} else if strings.Contains(tags, "operand32") {
		walk("datasize", "32")
	} else if strings.Contains(tags, "operand64") {
		walk("datasize", "64")
	} else {
		walk("datasize", "any")
	}

	if len(encoding) > 0 && encoding[0] == "/r" {
		haveModRM = true
	}
	if haveModRM {
		if strings.Contains(tags, "modrm_regonly") {
			walk("ismem", "0")
		} else if strings.Contains(tags, "modrm_memonly") {
			walk("ismem", "1")
		} else {
			walk("ismem", "any")
		}
	}

	walk("op", strings.Fields(text)[0])

	if len(encoding) > 0 && strings.HasPrefix(encoding[0], "VEX") {
		for _, field := range encoding[2:] {
			walk("read", field)
		}
	} else {
		for _, field := range encoding {
			walk("read", field)
		}
	}

	var usedRM string
	for _, arg := range strings.Fields(text)[1:] {
		arg = strings.TrimRight(arg, ",")
		if usesReg[arg] && !haveModRM && !havePlus {
			log.Printf("%s %s: no modrm field to use for %s", text, opcode, arg)
			continue
		}
		if usesRM[arg] && !haveModRM {
			log.Printf("%s %s: no modrm field to use for %s", text, opcode, arg)
			continue
		}
		if usesReg[arg] {
			if usedReg != "" {
				log.Printf("%s %s: modrm reg field used by both %s and %s", text, opcode, usedReg, arg)
				continue
			}
			usedReg = arg
		}
		if usesRM[arg] {
			if usedRM != "" {
				log.Printf("%s %s: modrm r/m field used by both %s and %s", text, opcode, usedRM, arg)
				continue
			}
			usedRM = arg
		}
		walk("arg", arg)
	}

	walk("match", "!")
}

// allKeys records the list of all possible child keys for actions that support "any".
var allKeys = map[string][]string{
	"is64":     {"0", "1"},
	"ismem":    {"0", "1"},
	"addrsize": {"16", "32", "64"},
	"datasize": {"16", "32", "64"},
}

// check checks that the program tree is well-formed.
// It also merges "any" keys into specific decoding keys in order to
// create an invariant that a particular check node either has a
// single "any" child - making it a no-op - or has no "any" children.
// See the discussion of "any" in the comment for add above.
func check(p *Prog) {
	if p.Child["any"] != nil && len(p.Child) > 1 {
		for _, key := range p.keys() {
			if key != "any" {
				mergeCopy(p.Child[key], p.Child["any"])
			}
		}
		if allKeys[p.Action] == nil {
			log.Printf("%s: unknown key space for %s=any", p.Path, p.Action)
		}
		for _, key := range allKeys[p.Action] {
			if p.Child[key] == nil {
				p.Child[key] = p.Child["any"]
			}
		}
		delete(p.Child, "any")
	}

	for _, q := range p.Child {
		check(q)
	}

	switch p.Action {
	case "op", "read", "arg":
		if len(p.Child) > 1 {
			log.Printf("%s: multiple children for action=%s: %v", p.Path, p.Action, p.keys())
		}
	}
}

// mergeCopy merges a copy of the tree rooted at src into dst.
// It is only used once no more paths will be added to the tree,
// so it is safe to introduce cross-links that make the program
// a dag rather than a tree.
func mergeCopy(dst, src *Prog) {
	//log.Printf("merge %s|%s and %s|%s\n", dst.Path, dst.Action, src.Path, src.Action)
	if dst.Action != src.Action {
		log.Printf("cannot merge %s|%s and %s|%s", dst.Path, dst.Action, src.Path, src.Action)
		return
	}

	for _, key := range src.keys() {
		if dst.Child[key] == nil {
			// Create new subtree by creating cross-link.
			dst.Child[key] = src.Child[key]
		} else {
			// Merge src subtree into existing dst subtree.
			mergeCopy(dst.Child[key], src.Child[key])
		}
	}
}

// set returns a map mapping each of the words in all to true.
func set(all string) map[string]bool {
	m := map[string]bool{}
	for _, f := range strings.Fields(all) {
		m[f] = true
	}
	return m
}

// isPrefix records the x86 opcode prefix bytes.
var isPrefix = set(`
	26
	2E
	36
	3E
	64
	65
	66
	67
	F0
	F2
	F3
`)

// usesReg records the argument codes that use the modrm reg field.
var usesReg = set(`
	r8
	r16
	r32
	r64
`)

// usesRM records the argument codes that use the modrm r/m field.
var usesRM = set(`
	r/m8
	r/m16
	r/m32
	r/m64
`)

var isVexEncodablePrefix = set(`
	0F
	0F38
	0F3A
	66
	F3
	F2
`)

// isHex reports whether the argument is a two digit hex number
// possibly followed by a +foo suffix.
func isHex(s string) bool {
	if i := strings.Index(s, "+"); i >= 0 {
		s = s[:i]
	}
	if len(s) != 2 {
		return false
	}
	for i := 0; i < len(s); i++ {
		c := s[i]
		if '0' <= c && c <= '9' || 'A' <= c && c <= 'F' {
			continue
		}
		return false
	}
	return true
}

// isSlashNum reports whether the argument is /n for some number n in [0,7].
func isSlashNum(s string) bool {
	return len(s) == 2 && s[0] == '/' && '0' <= s[1] && s[1] <= '7'
}

// mergeTail is supposed to merge common subtrees (program tails),
// reducing the size of the final program code.
// It identifies the subtrees using a bottom-up canonicalization.
//
// THIS CODE DOES NOT WORK. IT NEEDS TO BE DEBUGGED.
func mergeTail(p *Prog, emitted map[string]*Prog) *Prog {
	if emitted == nil {
		emitted = make(map[string]*Prog)
	}

	if p.Action == "match" {
		return p
	}

	for _, key := range p.keys() {
		p.Child[key] = mergeTail(p.Child[key], emitted)
	}

	op := ""
	for _, key := range p.keys() {
		q := p.Child[key]
		if q.Action != "op" || len(q.Child) > 1 {
			op = ""
			break
		}
		qop := q.keys()[0]
		if op == "" {
			op = qop
		} else if op != qop {
			op = ""
			break
		}
	}

	if op != "" {
		// Pull 'op x' up above the discriminator.
		p1 := new(Prog)
		*p1 = *p
		for _, key := range p.keys() {
			p1.Child[key] = p.Child[key].Child[op]
		}
		p.Action = "op"
		p.Child = map[string]*Prog{op: p1}
	}

	var buf bytes.Buffer
	fmt.Fprintf(&buf, "%s\n", p.Action)
	for _, key := range p.keys() {
		fmt.Fprintf(&buf, "%s %d\n", key, p.Child[key].TailID)
	}
	key := buf.String()

	if q := emitted[key]; q != nil {
		return q
	}
	emitted[key] = p
	p.TailID = len(emitted)
	return p
}

// printText prints the tree in textual form.
func printText(p *Prog) {
	printTree(os.Stdout, p, 0, false)
}

var tabs = strings.Repeat("    ", 100)

func printTree(w io.Writer, p *Prog, depth int, compact bool) {
	if compact && len(p.Child) == 1 {
		fmt.Fprintf(w, "%.*s%s", 4*depth, tabs, p.Action)
		for len(p.Child) == 1 {
			key := p.keys()[0]
			child := p.Child[key]
			fmt.Fprintf(w, " %s %s", key, child.Action)
			p = child
		}
		fmt.Fprintf(w, "\n")
	} else {
		fmt.Fprintf(w, "%.*s%s\n", 4*depth, tabs, p.Action)
	}
	for _, key := range p.keys() {
		fmt.Fprintf(w, "%.*s%s\n", 4*(depth+1), tabs, key)
		printTree(w, p.Child[key], depth+2, compact)
	}
}

// printDecoder prints a Go array containing the decoder program.
// It runs in two passes, both of which traverse and could generate
// the entire program. The first pass records the PC for each Prog node,
// and the second pass emits the actual program, using the PCs as jump
// targets in the places where the program is a dag rather than a tree.
func printDecoder(p *Prog) {
	opMap := map[string]bool{
		"PAUSE": true,
	}
	printDecoderPass(p, 1, false, opMap)
	fmt.Printf("// DO NOT EDIT\n")
	fmt.Printf("// generated by: x86map -fmt=decoder %s\n", inputFile)
	fmt.Printf("\n")
	fmt.Printf("package x86asm\n\n")
	fmt.Printf("var decoder = [...]uint16{\n\tuint16(xFail),\n")
	printDecoderPass(p, 1, true, opMap)
	fmt.Printf("}\n\n")

	var ops []string
	for op := range opMap {
		ops = append(ops, op)
	}
	sort.Strings(ops)

	fmt.Printf("const (\n")
	fmt.Printf("\t_ Op = iota\n\n")
	last := ""
	for _, op := range ops {
		fmt.Printf("\t%s\n", op)
		last = op
	}
	fmt.Printf(")\n\n")
	fmt.Printf("const maxOp = %s\n\n", last)

	fmt.Printf("var opNames = [...]string{\n")
	for _, op := range ops {
		fmt.Printf("\t%s: \"%s\",\n", op, op)
	}
	fmt.Printf("}\n")
}

// printScanner prints the decoding table for a scanner.
// The scanner can identify instruction boundaries but does not do
// full decoding. It is meant to be lighter weight than the x86asm
// decoder tables.
func printScanner(p *Prog) {
	walkScanTree(p, -1)
	var out []uint16
	out = append(out, 0)
	emitScanFunc(p, &out)
	fmt.Printf("var scanProg = []uint16{\n")
	fmt.Printf("\t/*0*/ 0, // dead\n")
	for i := 1; i < len(out); i++ {
		fmt.Printf("\t/*%d*/ ", i)
		switch out[i] {
		default:
			log.Fatalf("malformed program %#x", out[i])
		case scanMatch:
			fmt.Printf("scanMatch,\n")
			continue
		case scanJump:
			fmt.Printf("scanJump, %d,\n", out[i+1])
			i++
			continue
		case scanSwitchByte:
			fmt.Printf("scanSwitchByte,\n")
			for j := 0; j < 256/8; j++ {
				fmt.Printf("\t")
				fmt.Printf("/* %#02x-%#02x */", j*8, j*8+7)
				for k := 0; k < 8; k++ {
					fmt.Printf(" %d,", out[i+1+j*8+k])
				}
				fmt.Printf("\n")
			}
			i += 256
			continue
		case scanSwitchSlash:
			fmt.Printf("scanSwitchSlash, %d,\n", out[i+1])
			n := int(out[i+1])
			for j := 0; j < n; j++ {
				fmt.Printf("\t/* byte */ %#x, %d,\n", out[i+2+2*j], out[i+2+2*j+1])
			}
			for j := 0; j < 8; j++ {
				fmt.Printf("\t/* /%d */ %d,\n", j, out[i+2+2*n+j])
			}
			i += 1 + 2*n + 8
			continue
		case scanSwitchPrefix:
			fmt.Printf("scanSwitchPrefix, %d,\n", out[i+1])
			n := int(out[i+1])
			for j := 0; j < n; j++ {
				fmt.Printf("\t/* prefix */ %#x, %d,\n", out[i+2+2*j], out[i+2+2*j+1])
			}
			i += 1 + 2*n
			continue
		case scanSwitchIs64:
			fmt.Printf("scanSwitchIs64, %d, %d\n", out[i+1], out[i+2])
			i += 2
			continue
		case scanSwitchDatasize:
			fmt.Printf("scanSwitchDatasize, %d, %d, %d\n", out[i+1], out[i+2], out[i+3])
			i += 3
			continue
		case scanSwitchIsMem:
			fmt.Printf("scanSwitchIsMem, %d, %d\n", out[i+1], out[i+2])
			i += 2
			continue
		case scanReadModRM:
			fmt.Printf("scanReadModRM,\n")
			continue
		case scanReadIB:
			fmt.Printf("scanReadIB,\n")
			continue
		case scanReadIW:
			fmt.Printf("scanReadIW,\n")
			continue
		case scanReadIWD:
			fmt.Printf("scanReadIWD,\n")
			continue
		case scanReadIWDO:
			fmt.Printf("scanReadIWDO,\n")
			continue
		case scanReadCWD:
			fmt.Printf("scanReadCWD,\n")
			continue
		case scanReadCB:
			fmt.Printf("scanReadCB,\n")
			continue
		case scanReadCDP:
			fmt.Printf("scanReadCDP,\n")
			continue
		case scanReadCM:
			fmt.Printf("scanReadCM,\n")
			continue
		}
	}
	fmt.Printf("}\n")
}

func walkScanTree(p *Prog, is64 int) {
	keys := p.keys()
	for _, key := range keys {
		if p.Action == "is64" {
			switch key {
			case "0":
				is64 = 0
			case "1":
				is64 = 1
			}
		}
		walkScanTree(p.Child[key], is64)
	}

	switch p.Action {
	case "read", "match":
		// keep
		return
	case "decode":
		if len(keys) >= 8 && keys[0] == "/0" && keys[7] == "/7" && allSame(p, keys) {
			p.Action = "read"
			p.Child = map[string]*Prog{"/r": p.Child[keys[0]]}
			return
		}
	case "op", "arg":
		// drop
		*p = *p.Child[keys[0]]
		return
	case "prefix":
		if len(keys) >= 1 && keys[0] == "0" && allSame(p, keys) {
			*p = *p.Child[keys[0]]
			return
		}
	case "is64", "addrsize", "datasize", "ismem":
		if len(keys) == 1 && keys[0] == "any" {
			*p = *p.Child[keys[0]]
			return
		}
		nkey := len(allKeys[p.Action])
		if p.Action == "addrsize" {
			nkey = 2
		}
		if p.Action == "datasize" && is64 == 0 {
			nkey = 2
		}
		if len(keys) == nkey && allSame(p, keys) {
			*p = *p.Child[keys[0]]
			return
		}
	}

	switch p.Action {
	case "datasize":
		if len(keys) == 2 && is64 == 0 || len(keys) == 3 {
			if treeText(p.Child["16"]) == "read iw match ! \n" && treeText(p.Child["32"]) == "read id match ! \n" && (len(keys) == 2 || treeText(p.Child["64"]) == "read id match ! \n") {
				p.Action = "read"
				p.Child = map[string]*Prog{"iwd/d": p.Child["16"].Child["iw"]}
				return
			}
			if len(keys) == 3 && treeText(p.Child["16"]) == "read iw match ! \n" && treeText(p.Child["32"]) == "read id match ! \n" && treeText(p.Child["64"]) == "read io match ! \n" {
				p.Action = "read"
				p.Child = map[string]*Prog{"iwdo/d": p.Child["16"].Child["iw"]}
				return
			}
			if treeText(p.Child["16"]) == "read /r read iw match ! \n" && treeText(p.Child["32"]) == "read /r read id match ! \n" && (len(keys) == 2 || treeText(p.Child["64"]) == "read /r read id match ! \n") {
				p.Action = "read"
				p.Child = map[string]*Prog{"/r": {Action: "read", Child: map[string]*Prog{"iwd/d": p.Child["16"].Child["/r"].Child["iw"]}}}
				return
			}
			if treeText(p.Child["16"]) == "read cw match ! \n" && treeText(p.Child["32"]) == "read cd match ! \n" && (len(keys) == 2 || treeText(p.Child["64"]) == "read cd match ! \n") {
				p.Action = "read"
				p.Child = map[string]*Prog{"cwd/d": p.Child["16"].Child["cw"]}
				return
			}
			if treeText(p.Child["16"]) == "read cd match ! \n" && treeText(p.Child["32"]) == "read cp match ! \n" && (len(keys) == 2 || treeText(p.Child["64"]) == "read cp match ! \n") {
				p.Action = "read"
				p.Child = map[string]*Prog{"cdp/d": p.Child["16"].Child["cd"]}
				return
			}
			fmt.Printf("!! %q\n", treeText(p.Child["16"]))
		}

	case "is64":
		if len(keys) == 2 && treeText(p.Child["0"]) == "read cwd/d match ! \n" && treeText(p.Child["1"]) == "read cd match ! \n" {
			*p = *p.Child["0"]
			return
		}
		if len(keys) == 2 && treeText(p.Child["0"]) == "read iwd/d match ! \n" && treeText(p.Child["1"]) == "read iwdo/d match ! \n" {
			*p = *p.Child["1"]
			return
		}
	}

	/*
		match := make(map[string][]string)
		for _, key := range keys {
			text := treeText(p.Child[key])
			match[text] = append(match[text], key)
		}
		child := make(map[string]*Prog)
		for _, keys := range match {
			child[strings.Join(keys, ",")] = p.Child[keys[0]]
		}
		p.Child = child
	*/
}

func treeText(p *Prog) string {
	var buf bytes.Buffer
	printTree(&buf, p, 0, true)
	return buf.String()
}

func allSame(p *Prog, keys []string) bool {
	var tree string
	for i, key := range keys {
		if i == 0 {
			tree = treeText(p.Child[key])
			continue
		}
		if treeText(p.Child[key]) != tree {
			return false
		}
	}
	return true
}

var scanCache = map[string]uint16{}

const (
	_ uint16 = iota
	scanMatch
	scanJump
	scanSwitchByte
	scanSwitchSlash
	scanSwitchIs64
	scanSwitchDatasize
	scanSwitchIsMem
	scanSwitchPrefix
	scanReadModRM
	scanReadIB
	scanReadIW
	scanReadIWD
	scanReadIWDO
	scanReadCWD
	scanReadCB
	scanReadCDP
	scanReadCM
)

func decodeKeyPlus(key string) (val, n int) {
	n = 1
	if strings.HasSuffix(key, "+") {
		n = 8
		key = key[:len(key)-1]
	}
	v, err := strconv.ParseUint(key, 16, 8)
	if err != nil {
		log.Fatalf("unexpected decode key %q", key)
	}
	return int(v), n
}

func decodeKey(key string) int {
	val, n := decodeKeyPlus(key)
	if n != 1 {
		log.Panicf("unexpected decode key+ %q", key)
	}
	return val
}

func emitScanFunc(p *Prog, out *[]uint16) uint16 {
	keys := p.keys()
	text := treeText(p)
	if off, ok := scanCache[text]; ok {
		return off
	}
	start := uint16(len(*out))
	scanCache[text] = start
	switch p.Action {
	case "decode":
		if keys[0][0] != '/' {
			*out = append(*out, scanSwitchByte)
			off := len(*out)
			for i := 0; i < 256; i++ {
				*out = append(*out, 0)
			}
			for _, key := range keys {
				val, n := decodeKeyPlus(key)
				dst := emitScanFunc(p.Child[key], out)
				for j := 0; j < n; j++ {
					(*out)[off+val+j] = dst
				}
			}
			return start
		}

		n := len(keys)
		for n > 0 && keys[n-1][0] != '/' {
			n--
		}
		total := 0
		for i := n; i < len(keys); i++ {
			key := keys[i]
			_, n := decodeKeyPlus(key)
			total += n
		}
		*out = append(*out, scanSwitchSlash, uint16(total))
		off := len(*out)
		for i := 0; i < total; i++ {
			*out = append(*out, 0, 0)
		}
		for i := 0; i < 8; i++ {
			*out = append(*out, 0)
		}
		for i := n; i < len(keys); i++ {
			key := keys[i]
			val, valn := decodeKeyPlus(key)
			targ := emitScanFunc(p.Child[key], out)
			for j := 0; j < valn; j++ {
				(*out)[off] = uint16(val + j)
				off++
				(*out)[off] = targ
				off++
			}
		}
		for i := 0; i < n; i++ {
			key := keys[i]
			if len(key) != 2 || key[0] != '/' || key[1] < '0' || '8' <= key[1] {
				log.Fatalf("unexpected decode key %q", key)
			}
			(*out)[off+int(key[1]-'0')] = emitScanFunc(p.Child[key], out)
		}
		return start

	case "read":
		switch keys[0] {
		default:
			log.Fatalf("unexpected read %q", keys[0])
		case "/r":
			*out = append(*out, scanReadModRM)
		case "ib":
			*out = append(*out, scanReadIB)
		case "iw":
			*out = append(*out, scanReadIW)
		case "cb":
			*out = append(*out, scanReadCB)
		case "cm":
			*out = append(*out, scanReadCM)
		case "iwd/d":
			*out = append(*out, scanReadIWD)
		case "iwdo/d":
			*out = append(*out, scanReadIWDO)
		case "cwd/d":
			*out = append(*out, scanReadCWD)
		case "cdp/d":
			*out = append(*out, scanReadCDP)
		}
		next := p.Child[keys[0]]
		if next.Action == "match" {
			*out = append(*out, scanMatch)
		} else {
			*out = append(*out, scanJump, 0)
			off := len(*out)
			(*out)[off-1] = emitScanFunc(next, out)
		}
		return start

	case "match":
		*out = append(*out, scanMatch)
		return start

	case "is64":
		*out = append(*out, scanSwitchIs64, 0, 0)
		if next := p.Child["0"]; next != nil {
			(*out)[start+1] = emitScanFunc(next, out)
		}
		if next := p.Child["1"]; next != nil {
			(*out)[start+2] = emitScanFunc(next, out)
		}
		return start

	case "ismem":
		*out = append(*out, scanSwitchIsMem, 0, 0)
		if next := p.Child["0"]; next != nil {
			(*out)[start+1] = emitScanFunc(next, out)
		}
		if next := p.Child["1"]; next != nil {
			(*out)[start+2] = emitScanFunc(next, out)
		}
		return start

	case "datasize":
		*out = append(*out, scanSwitchDatasize, 0, 0, 0)
		if next := p.Child["16"]; next != nil {
			(*out)[start+1] = emitScanFunc(next, out)
		}
		if next := p.Child["32"]; next != nil {
			(*out)[start+2] = emitScanFunc(next, out)
		}
		if next := p.Child["64"]; next != nil {
			(*out)[start+3] = emitScanFunc(next, out)
		}
		return start
	case "prefix":
		*out = append(*out, scanSwitchPrefix, uint16(len(keys)))
		n := len(keys)
		for i := 0; i < n; i++ {
			*out = append(*out, uint16(decodeKey(keys[i])), 0)
		}
		for i := 0; i < n; i++ {
			(*out)[int(start)+2+2*i+1] = emitScanFunc(p.Child[keys[i]], out)
		}
		return start

	}

	log.Fatalf("unexpected action %q", p.Action)
	return start
}

// printDecoderPass prints the decoding table program for p,
// assuming that we are emitting code at the given program counter.
// It returns the new current program counter, that is, the program
// counter after the printed instructions.
// If printing==false, printDecoderPass does not print the actual
// code words but still does the PC computation.
func printDecoderPass(p *Prog, pc int, printing bool, ops map[string]bool) int {
	// Record PC on first pass.
	if p.PC == 0 {
		p.PC = pc
	}

	// If PC doesn't match, we've already printed this code
	// because it was reached some other way. Jump to that copy.
	if p.PC != pc {
		if printing {
			fmt.Printf("/*%d*/\tuint16(xJump), %d,\n", pc, p.PC)
		}
		return pc + 2
	}

	// Otherwise, emit the code for the given action.

	// At the bottom, if next is non-nil, emit code for next.
	// Then emit the code for the children named by the keys.
	keys := p.keys()
	var next *Prog

	switch p.Action {
	default:
		log.Printf("printDecoderPass: unknown action %q: %s", p.Action, p.Path)

	case "decode":
		// Decode hex bytes or /n modrm op checks.
		// Hex bytes take priority, so do them first.
		// Hex bytes of the form "40+" indicate an
		// 8 entry-wide swath of codes: 40, 41, ..., 47.
		hex := 0
		slash := 0
		for _, key := range keys {
			if isHex(key) {
				if strings.Contains(key, "+") {
					hex += 8
				} else {
					hex++
				}
			}
			if isSlashNum(key) {
				slash++
			}
		}
		if hex > 0 {
			// TODO(rsc): Introduce an xCondByte256 that has 256 child entries
			// and no explicit keys. That will cut the size in half for large
			// tables.
			if printing {
				fmt.Printf("/*%d*/\tuint16(xCondByte), %d,\n", pc, hex)
				for _, key := range keys {
					if !isHex(key) {
						continue
					}
					if i := strings.Index(key, "+"); i >= 0 {
						nextPC := p.Child[key].PC
						n, _ := strconv.ParseUint(key[:i], 16, 0)
						for j := 0; j < 8; j++ {
							fmt.Printf("\t%#02x, %d,\n", int(n)+j, nextPC)
						}
						continue
					}
					fmt.Printf("\t0x%s, %d,\n", key, p.Child[key].PC)
				}
			}
			pc += 2 + 2*hex

			// All other condition checks fail the decoding if nothing is found,
			// but this one falls through so that we can then do /n checks.
			// If there are no upcoming /n checks, insert an explicit failure.
			if slash == 0 {
				if printing {
					fmt.Printf("\tuint16(xFail),\n")
				}
				pc++
			}
		}
		if slash > 0 {
			if printing {
				fmt.Printf("/*%d*/\tuint16(xCondSlashR),\n", pc)
				for i := 0; i < 8; i++ {
					fmt.Printf("\t%d, // %d\n", p.childPC(fmt.Sprintf("/%d", i)), i)
				}
			}
			pc += 1 + 8
		}

	case "is64":
		// Decode based on processor mode: 64-bit or not.
		if len(keys) == 1 && keys[0] == "any" {
			next = p.Child["any"]
			break
		}
		if p.Child["any"] != nil {
			log.Printf("%s: mixed is64 keys: %v", p.Path, keys)
		}

		if printing {
			fmt.Printf("/*%d*/\tuint16(xCondIs64), %d, %d,\n", pc, p.childPC("0"), p.childPC("1"))
		}
		pc += 3

	case "prefix":
		// Decode based on presence of prefix.
		// The "0" prefix means "none of the above", so if there's
		// nothing else, it's the same as "any".
		if len(keys) == 1 && (keys[0] == "any" || keys[0] == "0") {
			next = p.Child["any"]
			break
		}
		if p.Child["any"] != nil {
			log.Printf("%s: mixed prefix keys: %v", p.Path, keys)
		}

		// Emit the prefixes in reverse sorted order, so that F3 and F2 are
		// considered before 66, and the fallback 0 is considered last.
		if printing {
			fmt.Printf("/*%d*/\tuint16(xCondPrefix), %d,\n", pc, len(keys))
			for i := len(keys) - 1; i >= 0; i-- {
				key := keys[i]
				nextPC := p.Child[key].PC
				fmt.Printf("\t0x%s, %d,\n", key, nextPC)
			}
		}
		pc += 2 + 2*len(keys)

	case "addrsize":
		// Decode based on address size attribute.
		if len(keys) == 1 && keys[0] == "any" {
			next = p.Child["any"]
			break
		}
		if p.Child["any"] != nil {
			log.Printf("%s: mixed addrsize keys: %v", p.Path, keys)
		}

		if printing {
			fmt.Printf("/*%d*/\tuint16(xCondAddrSize), %d, %d, %d,\n", pc, p.childPC("16"), p.childPC("32"), p.childPC("64"))
		}
		pc += 4

	case "datasize":
		// Decode based on operand size attribute.
		if len(keys) == 1 && keys[0] == "any" {
			next = p.Child["any"]
			break
		}
		if p.Child["any"] != nil {
			log.Printf("%s: mixed datasize keys: %v", p.Path, keys)
		}

		if printing {
			fmt.Printf("/*%d*/\tuint16(xCondDataSize), %d, %d, %d,\n", pc, p.childPC("16"), p.childPC("32"), p.childPC("64"))
		}
		pc += 4

	case "ismem":
		// Decode based on modrm form: memory or register reference.
		if len(keys) == 1 && keys[0] == "any" {
			next = p.Child["any"]
			break
		}
		if p.Child["any"] != nil {
			log.Printf("%s: mixed ismem keys: %v", p.Path, keys)
		}

		if printing {
			fmt.Printf("/*%d*/\tuint16(xCondIsMem), %d, %d,\n", pc, p.childPC("0"), p.childPC("1"))
		}
		pc += 3

	case "op":
		// Set opcode.
		ops[keys[0]] = true
		if printing {
			fmt.Printf("/*%d*/\tuint16(xSetOp), uint16(%s),\n", pc, keys[0])
		}
		next = p.Child[keys[0]]
		pc += 2

	case "read":
		// Read argument bytes.
		if printing {
			fmt.Printf("/*%d*/\tuint16(xRead%s),\n", pc, xOp(keys[0]))
		}
		next = p.Child[keys[0]]
		pc++

	case "arg":
		// Record instruction argument (interpret bytes loaded with read).
		if printing {
			fmt.Printf("/*%d*/\tuint16(xArg%s),\n", pc, xOp(keys[0]))
		}
		next = p.Child[keys[0]]
		pc++

	case "match":
		// Finish match.
		if printing {
			fmt.Printf("/*%d*/\tuint16(xMatch),\n", pc)
		}
		pc++
		return pc
	}

	if next != nil {
		pc = printDecoderPass(next, pc, printing, ops)
	}

	for _, key := range keys {
		q := p.Child[key]
		if q.PC == 0 || q.PC == pc {
			pc = printDecoderPass(q, pc, printing, ops)
		}
	}

	return pc
}

// childPC returns the PC for the given child key.
// If the key is not present, it returns PC 0,
// which is known to be an xFail instruction.
func (p *Prog) childPC(key string) int {
	q := p.Child[key]
	if q == nil {
		return 0
	}
	return q.PC
}

// isLower reports whether c is an ASCII lower case letter.
func isLower(c byte) bool {
	return 'a' <= c && c <= 'z'
}

// isLetterDigit reports whether c is an ASCII letter or digit.
func isLetterDigit(c byte) bool {
	return 'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z' || '0' <= c && c <= '9'
}

// xOp converts arg, an Intel manual shorthand, into a decoder opcode suffix.
// The standard form is LeadingUpperLetter with a few punctuation symbols
// turned into purely lower case words: M16and32, M16colon32, CR0dashCR7.
func xOp(arg string) string {
	var buf []byte
	for i := 0; i < len(arg); i++ {
		c := arg[i]
		if isLower(c) && (i == 0 || !isLetterDigit(arg[i-1])) {
			c -= 'a' - 'A'
		}
		buf = append(buf, c)
	}
	return argFix.Replace(string(buf))
}

var argFix = strings.NewReplacer(
	"/R", "SlashR",
	"/", "",
	"<", "",
	">", "",
	"+", "plus",
	"-", "dash",
	":", "colon",
	"&", "and",
	"ST(0)", "ST",
	"ST(I)", "STi",
	"ST(I)+Op", "STi",
)