func memUninitializedReads(insn bpf.Instruction, initialized memStatus) memStatus {
	return memReads(insn).merge(initialized, func(read, init bool) bool {
		return read && !init
	})
}
memUninitializedReads returns the memory read by insn that has not yet been initialized according to initialized.
package cbpfc
import (
	"fmt"
	"sort"
	"github.com/pkg/errors"
	"golang.org/x/net/bpf"
)
var condToInverse = map[bpf.JumpTest]bpf.JumpTest{
	bpf.JumpEqual:          bpf.JumpNotEqual,
	bpf.JumpNotEqual:       bpf.JumpEqual,
	bpf.JumpGreaterThan:    bpf.JumpLessOrEqual,
	bpf.JumpLessThan:       bpf.JumpGreaterOrEqual,
	bpf.JumpGreaterOrEqual: bpf.JumpLessThan,
	bpf.JumpLessOrEqual:    bpf.JumpGreaterThan,
	bpf.JumpBitsSet:        bpf.JumpBitsNotSet,
	bpf.JumpBitsNotSet:     bpf.JumpBitsSet,
}
type pos uint
type skip uint
type instruction struct {
	bpf.Instruction
	id pos
}
func (i instruction) String() string {
	return fmt.Sprintf("%d: %v", i.id, i.Instruction)
}
type block struct {
	insns []instruction
	jumps map[pos]*block
	id pos
}
func newBlock(insns []instruction) *block {
	return &block{
		insns: insns,
		jumps: make(map[pos]*block),
		id:    insns[0].id,
	}
}
func (b *block) Label() string {
	return fmt.Sprintf("block_%d", b.id)
}
func (b *block) skipToPos(s skip) pos {
	return b.last().id + 1 + pos(s)
}
func (b *block) skipToBlock(s skip) *block {
	return b.jumps[b.skipToPos(s)]
}
func (b *block) last() instruction {
	return b.insns[len(b.insns)-1]
}
type packetGuard uint32
type packetGuardAbsolute struct {
	guard packetGuard
}
func (p packetGuardAbsolute) Assemble() (bpf.RawInstruction, error) {
	return bpf.RawInstruction{}, errors.Errorf("unsupported")
}
type packetGuardIndirect struct {
	guard packetGuard
}
func (p packetGuardIndirect) Assemble() (bpf.RawInstruction, error) {
	return bpf.RawInstruction{}, errors.Errorf("unsupported")
}
type checkXNotZero struct {
}
func (c checkXNotZero) Assemble() (bpf.RawInstruction, error) {
	return bpf.RawInstruction{}, errors.Errorf("unsupported")
}
func compile(insns []bpf.Instruction) ([]*block, error) {
	err := validateInstructions(insns)
	if err != nil {
		return nil, err
	}
	instructions := toInstructions(insns)
	normalizeJumps(instructions)
	blocks, err := splitBlocks(instructions)
	if err != nil {
		return nil, errors.Wrapf(err, "unable to compute blocks")
	}
	err = initializeMemory(blocks)
	if err != nil {
		return nil, err
	}
	err = addDivideByZeroGuards(blocks)
	if err != nil {
		return nil, err
	}
	addAbsolutePacketGuards(blocks)
	addIndirectPacketGuards(blocks)
	return blocks, nil
}
func validateInstructions(insns []bpf.Instruction) error {
	if len(insns) == 0 {
		return errors.New("can't compile 0 instructions")
	}
	for pc, insn := range insns {
		_, err := insn.Assemble()
		if err != nil {
			return errors.Errorf("can't assemble instruction %d: %v", pc, insn)
		}
		switch i := insn.(type) {
		case bpf.RawInstruction:
			return errors.Errorf("unsupported instruction %d: %v", pc, insn)
		case bpf.LoadExtension:
			switch i.Num {
			case bpf.ExtLen:
				break
			default:
				return errors.Errorf("unsupported BPF extension %d: %v", pc, insn)
			}
		}
	}
	return nil
}
func toInstructions(insns []bpf.Instruction) []instruction {
	instructions := make([]instruction, len(insns))
	for pc, insn := range insns {
		instructions[pc] = instruction{
			Instruction: insn,
			id:          pos(pc),
		}
	}
	return instructions
}
func normalizeJumps(insns []instruction) {
	for pc := range insns {
		switch i := insns[pc].Instruction.(type) {
		case bpf.JumpIf:
			if !shouldInvert(i.SkipTrue, i.SkipFalse) {
				continue
			}
			insns[pc].Instruction = bpf.JumpIf{Cond: condToInverse[i.Cond], Val: i.Val, SkipTrue: i.SkipFalse, SkipFalse: i.SkipTrue}
		case bpf.JumpIfX:
			if !shouldInvert(i.SkipTrue, i.SkipFalse) {
				continue
			}
			insns[pc].Instruction = bpf.JumpIfX{Cond: condToInverse[i.Cond], SkipTrue: i.SkipFalse, SkipFalse: i.SkipTrue}
		}
	}
}
func shouldInvert(skipTrue, skipFalse uint8) bool {
	return skipTrue == 0 && skipFalse != 0
}
func visitBlock(insns []instruction, target pos) (*block, []skip) {
	for pc, insn := range insns {
		var skips []skip
		switch i := insn.Instruction.(type) {
		case bpf.Jump:
			skips = []skip{skip(i.Skip)}
		case bpf.JumpIf:
			skips = []skip{skip(i.SkipTrue), skip(i.SkipFalse)}
		case bpf.JumpIfX:
			skips = []skip{skip(i.SkipTrue), skip(i.SkipFalse)}
		case bpf.RetA, bpf.RetConstant:
		default:
			continue
		}
		return newBlock(insns[:pc+1]), skips
	}
	return newBlock(insns), []skip{0}
}
func splitBlocks(instructions []instruction) ([]*block, error) {
	blocks := []*block{}
	targets := map[pos][]*block{
		0: nil,
	}
	for len(targets) > 0 {
		sortedTargets := sortTargets(targets)
		target := sortedTargets[0]
		end := len(instructions)
		if len(sortedTargets) > 1 {
			end = int(sortedTargets[1])
		}
		next, nextSkips := visitBlock(instructions[target:end], target)
		for _, s := range nextSkips {
			t := next.skipToPos(s)
			if t >= pos(len(instructions)) {
				return nil, errors.Errorf("instruction %v flows past last instruction", next.last())
			}
			targets[t] = append(targets[t], next)
		}
		jmpBlocks := targets[target]
		for _, jmpBlock := range jmpBlocks {
			jmpBlock.jumps[target] = next
		}
		blocks = append(blocks, next)
		delete(targets, target)
	}
	return blocks, nil
}
func sortTargets(targets map[pos][]*block) []pos {
	keys := make([]pos, len(targets))
	i := 0
	for k := range targets {
		keys[i] = k
		i++
	}
	sort.Slice(keys, func(i, j int) bool {
		return keys[i] < keys[j]
	})
	return keys
}
func addDivideByZeroGuards(blocks []*block) error {
	isDivision := func(op bpf.ALUOp) bool {
		return op == bpf.ALUOpDiv || op == bpf.ALUOpMod
	}
	xNotZero := make(map[*block]bool)
	for _, block := range blocks {
		notZero := xNotZero[block]
		newInsns := []instruction{}
		for _, insn := range block.insns {
			switch i := insn.Instruction.(type) {
			case bpf.ALUOpConstant:
				if isDivision(i.Op) && i.Val == 0 {
					return errors.Errorf("instruction %v divides by 0", insn)
				}
			case bpf.ALUOpX:
				if isDivision(i.Op) && !notZero {
					newInsns = append(newInsns, instruction{Instruction: checkXNotZero{}})
					notZero = true
				}
			}
			newInsns = append(newInsns, insn)
			if memWrites(insn.Instruction).regs[bpf.RegX] {
				notZero = false
			}
		}
		block.insns = newInsns
		for _, target := range block.jumps {
			targetNotZero, ok := xNotZero[target]
			if !ok {
				xNotZero[target] = notZero
				continue
			}
			xNotZero[target] = targetNotZero && notZero
		}
	}
	return nil
}
func addAbsolutePacketGuards(blocks []*block) {
	addPacketGuards(blocks, packetGuardOpts{
		requiredGuard: func(insns []instruction) requiredGuard {
			var biggestGuard packetGuard
			for _, insn := range insns {
				switch i := insn.Instruction.(type) {
				case bpf.LoadAbsolute:
					if a := packetGuard(i.Off + uint32(i.Size)); a > biggestGuard {
						biggestGuard = a
					}
				case bpf.LoadMemShift:
					if a := packetGuard(i.Off + 1); a > biggestGuard {
						biggestGuard = a
					}
				}
			}
			return requiredGuard{
				guard:       biggestGuard,
				alwaysValid: true,
			}
		},
		createInsn: func(guard packetGuard) bpf.Instruction {
			return packetGuardAbsolute{guard: guard}
		},
	})
}
func addIndirectPacketGuards(blocks []*block) {
	addPacketGuards(blocks, packetGuardOpts{
		requiredGuard: func(insns []instruction) requiredGuard {
			var (
				insnCount    int
				biggestGuard packetGuard
			)
			for _, insn := range insns {
				insnCount++
				switch i := insn.Instruction.(type) {
				case bpf.LoadIndirect:
					if a := packetGuard(i.Off + uint32(i.Size)); a > biggestGuard {
						biggestGuard = a
					}
				}
				if memWrites(insn.Instruction).regs[bpf.RegX] {
					return requiredGuard{
						guard:         biggestGuard,
						validForInsns: insnCount,
					}
				}
			}
			return requiredGuard{
				guard:       biggestGuard,
				alwaysValid: true,
			}
		},
		createInsn: func(guard packetGuard) bpf.Instruction {
			return packetGuardIndirect{guard: guard}
		},
	})
}
type packetGuardOpts struct {
	requiredGuard func(insns []instruction) requiredGuard
	createInsn func(guard packetGuard) bpf.Instruction
}
type requiredGuard struct {
	guard packetGuard
	alwaysValid bool
	validForInsns int
}
func addPacketGuards(blocks []*block, opts packetGuardOpts) {
	guards := make(map[*block][]packetGuard)
	for _, block := range blocks {
		blockGuard := addBlockGuards(block, leastGuard(guards[block]), opts)
		for _, target := range block.jumps {
			guards[target] = append(guards[target], blockGuard)
		}
	}
}
func addBlockGuards(block *block, currentGuard packetGuard, opts packetGuardOpts) packetGuard {
	insns := block.insns
	block.insns = nil
	for len(insns) != 0 {
		required := opts.requiredGuard(insns)
		if required.guard != 0 && required.guard > currentGuard {
			currentGuard = required.guard
			if required.alwaysValid {
				if guaranteed := guaranteedGuard(block.jumps, opts); guaranteed > required.guard {
					currentGuard = guaranteed
				}
			}
			block.insns = append(block.insns, instruction{Instruction: opts.createInsn(currentGuard)})
		}
		if required.alwaysValid {
			block.insns = append(block.insns, insns...)
			return currentGuard
		}
		currentGuard = 0
		block.insns = append(block.insns, insns[:required.validForInsns]...)
		insns = insns[required.validForInsns:]
	}
	return currentGuard
}
func guaranteedGuard(targets map[pos]*block, opts packetGuardOpts) packetGuard {
	return guaranteedGuardCached(targets, opts, make(map[*block]packetGuard))
}
func guaranteedGuardCached(targets map[pos]*block, opts packetGuardOpts, cache map[*block]packetGuard) packetGuard {
	targetGuards := []packetGuard{}
	for _, target := range targets {
		if blockNeverMatches(target) {
			continue
		}
		if guard, ok := cache[target]; ok {
			targetGuards = append(targetGuards, guard)
			continue
		}
		required := opts.requiredGuard(target.insns)
		if !required.alwaysValid {
			targetGuards = append(targetGuards, required.guard)
			continue
		}
		guard := required.guard
		if guaranteed := guaranteedGuardCached(target.jumps, opts, cache); guaranteed > required.guard {
			guard = guaranteed
		}
		cache[target] = guard
		targetGuards = append(targetGuards, guard)
	}
	return leastGuard(targetGuards)
}
func leastGuard(guards []packetGuard) packetGuard {
	var least packetGuard
	for i, guard := range guards {
		if i == 0 || guard < least {
			least = guard
		}
	}
	return least
}
func blockNeverMatches(block *block) bool {
	for _, insn := range block.insns {
		switch i := insn.Instruction.(type) {
		case bpf.RetConstant:
			if i.Val == 0 {
				return true
			}
		}
	}
	return false
}
type memStatus struct {
	regs    [2]bool
	scratch [16]bool
}
func (r memStatus) merge(other memStatus, policy func(this, other bool) bool) memStatus {
	newStatus := memStatus{}
	for i := range newStatus.regs {
		newStatus.regs[i] = policy(r.regs[i], other.regs[i])
	}
	for i := range newStatus.scratch {
		newStatus.scratch[i] = policy(r.scratch[i], other.scratch[i])
	}
	return newStatus
}
func (r memStatus) and(other memStatus) memStatus {
	return r.merge(other, func(this, other bool) bool {
		return this && other
	})
}
func (r memStatus) or(other memStatus) memStatus {
	return r.merge(other, func(this, other bool) bool {
		return this || other
	})
}
func initializeMemory(blocks []*block) error {
	statuses := make(map[*block]memStatus)
	uninitialized := memStatus{}
	for _, block := range blocks {
		status := statuses[block]
		for _, insn := range block.insns {
			insnUninitialized := memUninitializedReads(insn.Instruction, status)
			for scratch, uninit := range insnUninitialized.scratch {
				if uninit {
					return errors.Errorf("instruction %v reads potentially uninitialized scratch register M[%d]", insn, scratch)
				}
			}
			uninitialized = uninitialized.or(insnUninitialized)
			status = status.or(memWrites(insn.Instruction))
		}
		for _, target := range block.jumps {
			targetStatus, ok := statuses[target]
			if !ok {
				statuses[target] = status
				continue
			}
			statuses[target] = targetStatus.and(status)
		}
	}
	initInsns := []instruction{}
	for reg, uninit := range uninitialized.regs {
		if !uninit {
			continue
		}
		initInsns = append(initInsns, instruction{
			Instruction: bpf.LoadConstant{
				Dst: bpf.Register(reg),
				Val: 0,
			},
		})
	}
	blocks[0].insns = append(initInsns, blocks[0].insns...)
	return nil
}