Little program to check the equality of a stupid and a clever implementation of the BIGMIN function.

bigmintest.go

//
// bigmintest.go
// --------------
//
// Little program to check the equality of a stupid and
// a clever implementation of the BIGMIN function.
//
// (c) 2012 by Sascha L. Teichmann
//
package main

import (
	"fmt"
	"math/rand"
)

const (
	TRIES   = 5
	BITS    = uint32(20)
	MSB     = 3*BITS - 1
	ZERO32  = uint32(0)
	ONE32   = uint32(1)
	ZERO64  = uint64(0)
	ONE64   = uint64(1)
	HI_MASK = ONE32 << (BITS + ONE32)
	_000_   = 0
	_001_   = 1
	_010_   = 1 << 1
	_011_   = (1 << 1) | 1
	_100_   = 1 << 2
	_101_   = (1 << 2) | 1
	// MASK = hex(int(''.join(['1' if (i%3) == 0 else '0' for i in range(60)]),2))
	MASK uint64 = 0x924924924924924
	// FULL = hex(int('1'*60,2))
	FULL uint64 = 0xfffffffffffffff
)

func ZEncode(x, y, z uint32) uint64 {
	code, p := ZERO64, ONE64
	for mask := ONE32; mask != HI_MASK; mask <<= 1 {
		if (x & mask) != 0 {
			code |= p
		}
		p <<= 1
		if (y & mask) != 0 {
			code |= p
		}
		p <<= 1
		if (z & mask) != 0 {
			code |= p
		}
		p <<= 1
	}
	return code
}

func ZDecode(code uint64) (x, y, z uint32) {
	p := ONE64
	x, y, z = ZERO32, ZERO32, ZERO32
	for mask := ONE32; mask != HI_MASK; mask <<= 1 {
		if (code & p) != 0 {
			x |= mask
		}
		p <<= 1
		if (code & p) != 0 {
			y |= mask
		}
		p <<= 1
		if (code & p) != 0 {
			z |= mask
		}
		p <<= 1
	}
	return
}

func setbits(p uint32, v uint64) uint64 {
	mask := (MASK >> (MSB - p)) & (^(FULL << p) & FULL)
	return (v | mask) & ^(1 << p) & FULL
}

func unsetbits(p uint32, v uint64) uint64 {
	mask := ^(MASK >> (MSB - p)) & FULL
	return (v & mask) | (1 << p)
}

func BigMin(minz, maxz, zcode uint64) uint64 {
	bigmin := maxz
	pos := MSB
	for mask := ONE64 << MSB; mask != 0; mask >>= 1 {
		var v int
		if (zcode & mask) != 0 {
			v = _100_
		} else {
			v = _000_
		}
		if (minz & mask) != 0 {
			v |= _010_
		}
		if (maxz & mask) != 0 {
			v |= _001_
		}

		switch v {
		case _001_:
			bigmin = unsetbits(pos, minz)
			maxz = setbits(pos, maxz)
		case _011_:
			return minz
		case _100_:
			return bigmin
		case _101_:
			minz = unsetbits(pos, minz)
		}
		pos--
	}
	return bigmin
}

func StupidBigMin(zmin, zmax, zcode uint64) uint64 {
	cand := zmax
	x1, y1, z1 := ZDecode(zmin)
	x2, y2, z2 := ZDecode(zmax)
	for x := x1; x <= x2; x++ {
		for y := y1; y <= y2; y++ {
			for z := z1; z <= z2; z++ {
				code := ZEncode(x, y, z)
				if code > zcode && code < cand {
					cand = code
				}
			}
		}
	}
	return cand
}

func main() {

	success, errors := 0, 0

	for i := 0; i < TRIES; i++ {
		x1 := uint32(rand.Intn(1000))
		y1 := uint32(rand.Intn(1000))
		z1 := uint32(rand.Intn(1000))
		w := uint32(rand.Intn(10) + 1)
		h := uint32(rand.Intn(10) + 1)
		d := uint32(rand.Intn(10) + 1)
		x2 := x1 + w
		y2 := y1 + h
		z2 := z1 + d

		zmin := ZEncode(x1, y1, z1)
		zmax := ZEncode(x2, y2, z2)

		for zcode := zmin + 1; zcode < zmax; zcode++ {
			x, y, z := ZDecode(zcode)

			// ignore points inside query cube
			if x >= x1 && x <= x2 &&
				y >= y1 && y <= y2 &&
				z >= z1 && z <= z2 {
				continue
			}

			sbm := StupidBigMin(zmin, zmax, zcode)
			cbm := BigMin(zmin, zmax, zcode)

			if sbm != cbm {
				errors++
				/*
				   sx, sy, sz := ZDecode(sbm)
				   cx, cy, cz := ZDecode(cbm)
				   fmt.Printf("(%d, %d, %d) != (%d, %d, %d)\n",
				       sx, sy, sz, cx, cy, cz)
				*/
			} else {
				success++
			}
		}
	}
	fmt.Printf("errors: %d\n", errors)
	fmt.Printf("success: %d\n", success)
}