progpow.go

package ethash

import (
	"encoding/binary"
	"math/bits"
	"github.com/ethereum/go-ethereum/crypto/sha3"
)

const (
	progpowCacheWords = 4 * 1024 // Total size 16*1024 bytes
	progpowLanes      = 32
	progpowRegs       = 16
	progpowCntCache   = 8
	progpowCntMath    = 8
	progpowCntMem     = loopAccesses
	progpowMixBytes   = 2 * mixBytes
)

func progpowLight(size uint64, cache []uint32, hash []byte, nonce uint64,
	blockNumber uint64) ([]byte, []byte) {
	keccak512 := makeHasher(sha3.NewKeccak512())

	lookup := func(index uint32) uint32 {
		rawData := generateDatasetItem(cache, index/16, keccak512)
		data := binary.LittleEndian.Uint32(rawData[(index%16)*4:])
		return data
	}
	return progpow(hash, nonce, size, blockNumber, lookup)
}

func progpowFull(dataset []uint32, hash []byte, nonce uint64,
	blockNumber uint64) ([]byte, []byte) {
	lookup := func(index uint32) uint32 {
		return dataset[index]
	}
	return progpow(hash, nonce, uint64(len(dataset))*4, blockNumber, lookup)
}

func lower32(in uint64) uint32 {
	return uint32(in & uint64(0x00000000FFFFFFFF))
}

func higher32(in uint64) uint32 {
	return uint32(in >> 32)
}

var keccakfRNDC = [24]uint32{
	0x00000001, 0x00008082, 0x0000808a, 0x80008000, 0x0000808b, 0x80000001,
	0x80008081, 0x00008009, 0x0000008a, 0x00000088, 0x80008009, 0x8000000a,
	0x8000808b, 0x0000008b, 0x00008089, 0x00008003, 0x00008002, 0x00000080,
	0x0000800a, 0x8000000a, 0x80008081, 0x00008080, 0x80000001, 0x80008008}

var keccakfROTC = [24]int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 2,
	14, 27, 41, 56, 8, 25, 43, 62, 18, 39, 61,
	20, 44}
var keccakfPILN = [24]uint32{10, 7, 11, 17, 18, 3, 5, 16, 8, 21, 24,
	4, 15, 23, 19, 13, 12, 2, 20, 14, 22, 9,
	6, 1}

var bc [5]uint32
var gst [25]uint32

func keccakF800Round(r int) {
	// Theta
	for i := 0; i < 5; i++ {
		bc[i] = gst[i] ^ gst[i+5] ^ gst[i+10] ^ gst[i+15] ^ gst[i+20]
	}

	for i := 0; i < 5; i++ {
		t := bc[(i+4)%5] ^ bits.RotateLeft32(bc[(i+1)%5], 1)
		for j := 0; j < 25; j += 5 {
			gst[j+i] ^= t
		}
	}

	// Rho Pi
	t := gst[1]
	for i := 0; i < 24; i++ {
		j := keccakfPILN[i]
		bc[0] = gst[j]
		gst[j] = bits.RotateLeft32(t, keccakfROTC[i])
		t = bc[0]
	}

	//  Chi
	for j := 0; j < 25; j += 5 {
		for i := 0; i < 5; i++ {
			bc[i] = gst[j+i]
		}
		for i := 0; i < 5; i++ {
			gst[j+i] ^= (^bc[(i+1)%5]) & bc[(i+2)%5]
		}
	}

	//  Iota
	gst[0] ^= keccakfRNDC[r]
}

func keccakF800Short(headerHash []byte, nonce uint64, result []uint32) uint64 {

	for i := 0; i < 8; i++ {
		gst[i] = (uint32(headerHash[4*i])) +
			(uint32(headerHash[4*i+1]) << 8) +
			(uint32(headerHash[4*i+2]) << 16) +
			(uint32(headerHash[4*i+3]) << 24)
	}

	gst[8] = lower32(nonce)
	gst[9] = higher32(nonce)
	for i := 0; i < 8; i++ {
		gst[10+i] = result[i]
	}
	gst[18] = 0
	gst[19] = 0
	gst[20] = 0
	gst[21] = 0
	gst[22] = 0
	gst[23] = 0
	gst[24] = 0
	for r := 0; r < 21; r++ {
		keccakF800Round(r)
	}
	keccakF800Round(21)
	return (uint64(gst[0]) << 32) | uint64(gst[1])
}

func keccakF800Long(headerHash []byte, nonce uint64, result []uint32, ret []byte) {
	for i := 0; i < 8; i++ {
		gst[i] = (uint32(headerHash[4*i])) +
			(uint32(headerHash[4*i+1]) << 8) +
			(uint32(headerHash[4*i+2]) << 16) +
			(uint32(headerHash[4*i+3]) << 24)
	}

	gst[8] = lower32(nonce)
	gst[9] = higher32(nonce)
	for i := 0; i < 8; i++ {
		gst[10+i] = result[i]
	}
	gst[18] = 0
	gst[19] = 0
	gst[20] = 0
	gst[21] = 0
	gst[22] = 0
	gst[23] = 0
	gst[24] = 0
	for r := 0; r < 21; r++ {
		keccakF800Round(r)
	}
	keccakF800Round(21)
	for i := 0; i < 8; i++ {
		binary.LittleEndian.PutUint32(ret[i*4:], gst[i])
	}
}

func fnv1a(h *uint32, d uint32) uint32 {
	*h = (*h ^ d) * uint32(0x1000193)
	return *h
}

type kiss99State struct {
	z     uint32
	w     uint32
	jsr   uint32
	jcong uint32
}

func kiss99(st *kiss99State) uint32 {
	var MWC uint32
	st.z = 36969*(st.z&65535) + (st.z >> 16)
	st.w = 18000*(st.w&65535) + (st.w >> 16)
	MWC = ((st.z << 16) + st.w)
	st.jsr ^= (st.jsr << 17)
	st.jsr ^= (st.jsr >> 13)
	st.jsr ^= (st.jsr << 5)
	st.jcong = 69069*st.jcong + 1234567
	return ((MWC ^ st.jcong) + st.jsr)
}

func fillMix(seed uint64, laneId uint32, mix *[progpowRegs]uint32)  {
	var st kiss99State

	fnvHash := uint32(0x811c9dc5)

	st.z = fnv1a(&fnvHash, lower32(seed))
	st.w = fnv1a(&fnvHash, higher32(seed))
	st.jsr = fnv1a(&fnvHash, laneId)
	st.jcong = fnv1a(&fnvHash, laneId)

	for i := 0; i < progpowRegs; i++ {
		mix[i] = kiss99(&st)
	}
}

// Merge new data from b into the value in a
// Assuming A has high entropy only do ops that retain entropy
// even if B is low entropy
// (IE don't do A&B)
func merge(a *uint32, b uint32, r uint32) {
	switch r % 4 {
	case 0:
		*a = (*a * 33) + b
	case 1:
		*a = (*a ^ b) * 33
	case 2:
		*a = bits.RotateLeft32(*a, int((r>>16)&31)) ^ b
	case 3:
		*a = bits.RotateLeft32(*a, -int((r>>16)&31)) ^ b
	}
}

func progpowInit(seed uint64, randState *kiss99State, mixSeq *[progpowRegs]uint32) {
	fnvHash := uint32(0x811c9dc5)

	randState.z = fnv1a(&fnvHash, lower32(seed))
	randState.w = fnv1a(&fnvHash, higher32(seed))
	randState.jsr = fnv1a(&fnvHash, lower32(seed))
	randState.jcong = fnv1a(&fnvHash, higher32(seed))

	// Create a random sequence of mix destinations for merge()
	// guaranteeing every location is touched once
	// Uses Fisher CYates shuffle
	for i := uint32(0); i < progpowRegs; i++ {
		mixSeq[i] = i
	}
	for i := uint32(progpowRegs - 1); i > 0; i-- {
		j := kiss99(randState) % (i + 1)
		temp := mixSeq[i]
		mixSeq[i] = mixSeq[j]
		mixSeq[j] = temp
	}
}

// Random math between two input values
func progpowMath(a uint32, b uint32, r uint32) uint32 {
	switch r % 11 {
	case 0:
		return a + b
	case 1:
		return a * b
	case 2:
		return higher32(uint64(a) * uint64(b))
	case 3:
		if a < b {
			return a
		}
		return b
	case 4:
		return bits.RotateLeft32(a, int(b&31))
	case 5:
		return bits.RotateLeft32(a, -int(b&31))
	case 6:
		return a & b
	case 7:
		return a | b
	case 8:
		return a ^ b
	case 9:
		return uint32(bits.LeadingZeros32(a) + bits.LeadingZeros32(b))
	case 10:
		return uint32(bits.OnesCount64(uint64(a) | (uint64(b)<<32)))
	default:
		return 0
	}
	return 0
}

var randStateStart kiss99State
var mixSeqStart [progpowRegs]uint32

func progpowLoop(seed uint64, loop uint32,
	mix *[progpowLanes][progpowRegs]uint32,
	lookup func(index uint32) uint32,
	cDag []uint32, datasetSize uint32) {
	// All lanes share a base address for the global load
	// Global offset uses mix[0] to guarantee it depends on the load result
	gOffset := mix[loop%progpowLanes][0] % datasetSize
	gOffset = gOffset * progpowLanes
	iMax := uint32(0)
	// Lanes can execute in parallel and will be convergent
	progpowInit(seed, &randStateStart, &mixSeqStart)

	for l := uint32(0); l < progpowLanes; l++ {
		mixSeqCnt := uint32(0)

		// global load to sequential locations
		data64 := uint64(lookup(2*(gOffset+l)+1))<<32 |
			uint64(lookup(2*(gOffset+l)))

		// initialize the seed and mix destination sequence
		randState, mixSeq := randStateStart, mixSeqStart

		if progpowCntCache > progpowCntMath {
			iMax = progpowCntCache
		} else {
			iMax = progpowCntMath
		}

		for i := uint32(0); i < iMax; i++ {
			if i < progpowCntCache {
				// Cached memory access
				// lanes access random location
				src1 := kiss99(&randState) % progpowRegs
				offset := mix[l][src1] % progpowCacheWords
				data32 := cDag[offset]
				dest := mixSeq[mixSeqCnt%progpowRegs]
				mixSeqCnt++
				r := kiss99(&randState)
				merge(&mix[l][dest], data32, r)
			}

			if i < progpowCntMath {
				// Random Math
				src11 := kiss99(&randState)
				src1 := src11 % progpowRegs
				src2 := kiss99(&randState) % progpowRegs
				r1 := kiss99(&randState)
				r2 := kiss99(&randState)
				dest := mixSeq[mixSeqCnt%progpowRegs]
				mixSeqCnt++
				data32 := progpowMath(mix[l][src1], mix[l][src2], r1)
				merge(&mix[l][dest], data32, r2)
			}
		}

		r1 := kiss99(&randState)
		r2 := kiss99(&randState)

		merge(&mix[l][0], lower32(data64), r1)
		dest := mixSeq[mixSeqCnt%progpowRegs]
		mixSeqCnt++
		merge(&mix[l][dest], higher32(data64), r2)
	}
}

func progpow(hash []byte, nonce uint64, size uint64, blockNumber uint64,
	lookup func(index uint32) uint32) ([]byte, []byte) {
	var mix [progpowLanes][progpowRegs]uint32
	var laneResults [progpowLanes]uint32

	var cDag [progpowCacheWords]uint32
	var result [8]uint32

	// initialize cDag
	for i := uint32(0); i < progpowCacheWords; i += 2 {
		cDag[i] = lookup(2 * i)
		cDag[i+1] = lookup(2*i + 1)
	}

	seed := keccakF800Short(hash, nonce, result[:])
	for lane := uint32(0); lane < progpowLanes; lane++ {
		fillMix(seed, lane, &mix[lane])
	}

	blockNumberRounded := (blockNumber / epochLength) * epochLength
	for l := uint32(0); l < progpowCntMem; l++ {
		progpowLoop(blockNumberRounded, l, &mix, lookup, cDag[:],
			uint32(size/progpowMixBytes))
	}

	// Reduce mix data to a single per-lane result
	for lane := uint32(0); lane < progpowLanes; lane++ {
		laneResults[lane] = 0x811c9dc5
		for i := uint32(0); i < progpowRegs; i++ {
			fnv1a(&laneResults[lane], mix[lane][i])
		}
	}

	for i := uint32(0); i < 8; i++ {
		result[i] = 0x811c9dc5
	}
	for lane := uint32(0); lane < progpowLanes; lane++ {
		fnv1a(&result[lane%8], laneResults[lane])
	}

	var digest [32]byte
	keccakF800Long(hash, seed, result[:], digest[:])

	resultBytes := make([]byte, 8*4)
	for i := 0; i < 8; i++ {
		binary.LittleEndian.PutUint32(resultBytes[i*4:], result[i])
	}

	return digest[:], resultBytes[:]
}