src/pkg/runtime/alg.goc

// Copyright 2009 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.

package runtime
#include "runtime.h"
#include "type.h"
#include "../../cmd/ld/textflag.h"

#define M0 (sizeof(uintptr)==4 ? 2860486313UL : 33054211828000289ULL)
#define M1 (sizeof(uintptr)==4 ? 3267000013UL : 23344194077549503ULL)

static bool use_aeshash;

/*
 * map and chan helpers for
 * dealing with unknown types
 */
void
runtime·memhash(uintptr *h, uintptr s, void *a)
{
	byte *b;
	uintptr hash;
	if(!NaCl && use_aeshash) {
		runtime·aeshash(h, s, a);
		return;
	}

	b = a;
	hash = M0 ^ *h;
	while(s > 0) {
		hash = (hash ^ *b) * M1;
		b++;
		s--;
	}
	*h = hash;
}

void
runtime·memequal(bool *eq, uintptr s, void *a, void *b)
{
	if(a == b) {
		*eq = 1;
		return;
	}
	*eq = runtime·memeq(a, b, s);
}

void
runtime·memprint(uintptr s, void *a)
{
	uint64 v;

	v = 0xbadb00b;
	switch(s) {
	case 1:
		v = *(uint8*)a;
		break;
	case 2:
		v = *(uint16*)a;
		break;
	case 4:
		v = *(uint32*)a;
		break;
	case 8:
		v = *(uint64*)a;
		break;
	}
	runtime·printint(v);
}

void
runtime·memcopy(uintptr s, void *a, void *b)
{
	if(b == nil) {
		runtime·memclr(a, s);
		return;
	}
	runtime·memmove(a, b, s);
}

void
runtime·memequal0(bool *eq, uintptr s, void *a, void *b)
{
	USED(s);
	USED(a);
	USED(b);
	*eq = true;
}

void
runtime·memcopy0(uintptr s, void *a, void *b)
{
	USED(s);
	USED(a);
	USED(b);
}

void
runtime·memequal8(bool *eq, uintptr s, void *a, void *b)
{
	USED(s);
	*eq = *(uint8*)a == *(uint8*)b;
}

void
runtime·memcopy8(uintptr s, void *a, void *b)
{
	USED(s);
	if(b == nil) {
		*(uint8*)a = 0;
		return;
	}
	*(uint8*)a = *(uint8*)b;
}

void
runtime·memequal16(bool *eq, uintptr s, void *a, void *b)
{
	USED(s);
	*eq = *(uint16*)a == *(uint16*)b;
}

void
runtime·memcopy16(uintptr s, void *a, void *b)
{
	USED(s);
	if(b == nil) {
		*(uint16*)a = 0;
		return;
	}
	*(uint16*)a = *(uint16*)b;
}

void
runtime·memequal32(bool *eq, uintptr s, void *a, void *b)
{
	USED(s);
	*eq = *(uint32*)a == *(uint32*)b;
}

void
runtime·memcopy32(uintptr s, void *a, void *b)
{
	USED(s);
	if(b == nil) {
		*(uint32*)a = 0;
		return;
	}
	*(uint32*)a = *(uint32*)b;
}

void
runtime·memequal64(bool *eq, uintptr s, void *a, void *b)
{
	USED(s);
	*eq = *(uint64*)a == *(uint64*)b;
}

void
runtime·memcopy64(uintptr s, void *a, void *b)
{
	USED(s);
	if(b == nil) {
		*(uint64*)a = 0;
		return;
	}
	*(uint64*)a = *(uint64*)b;
}

void
runtime·memequal128(bool *eq, uintptr s, void *a, void *b)
{
	USED(s);
	*eq = ((uint64*)a)[0] == ((uint64*)b)[0] && ((uint64*)a)[1] == ((uint64*)b)[1];
}

void
runtime·memcopy128(uintptr s, void *a, void *b)
{
	USED(s);
	if(b == nil) {
		((uint64*)a)[0] = 0;
		((uint64*)a)[1] = 0;
		return;
	}
	((uint64*)a)[0] = ((uint64*)b)[0];
	((uint64*)a)[1] = ((uint64*)b)[1];
}

void
runtime·f32equal(bool *eq, uintptr s, void *a, void *b)
{
	USED(s);
	*eq = *(float32*)a == *(float32*)b;
}

void
runtime·f64equal(bool *eq, uintptr s, void *a, void *b)
{
	USED(s);
	*eq = *(float64*)a == *(float64*)b;
}

void
runtime·c64equal(bool *eq, uintptr s, void *a, void *b)
{	
	Complex64 *ca, *cb;
	
	USED(s);
	ca = a;
	cb = b;
	*eq = ca->real == cb->real && ca->imag == cb->imag;
}

void
runtime·c128equal(bool *eq, uintptr s, void *a, void *b)
{	
	Complex128 *ca, *cb;
	
	USED(s);
	ca = a;
	cb = b;
	*eq = ca->real == cb->real && ca->imag == cb->imag;
}

// NOTE: Because NaN != NaN, a map can contain any
// number of (mostly useless) entries keyed with NaNs.
// To avoid long hash chains, we assign a random number
// as the hash value for a NaN.

void
runtime·f32hash(uintptr *h, uintptr s, void *a)
{
	uintptr hash;
	float32 f;

	USED(s);
	f = *(float32*)a;
	if(f == 0)
		hash = 0;  // +0, -0
	else if(f != f)
		hash = runtime·fastrand1();  // any kind of NaN
	else
		hash = *(uint32*)a;
	*h = (*h ^ hash ^ M0) * M1;
}

void
runtime·f64hash(uintptr *h, uintptr s, void *a)
{
	uintptr hash;
	float64 f;
	uint64 u;

	USED(s);
	f = *(float64*)a;
	if(f == 0)
		hash = 0;	// +0, -0
	else if(f != f)
		hash = runtime·fastrand1();  // any kind of NaN
	else {
		u = *(uint64*)a;
		if(sizeof(uintptr) == 4)
			hash = ((uint32)(u>>32) * M1) ^ (uint32)u;
		else
			hash = u;
	}
	*h = (*h ^ hash ^ M0) * M1;
}

void
runtime·c64hash(uintptr *h, uintptr s, void *a)
{
	USED(s);
	runtime·f32hash(h, 0, a);
	runtime·f32hash(h, 0, (float32*)a+1);
}

void
runtime·c128hash(uintptr *h, uintptr s, void *a)
{
	USED(s);
	runtime·f64hash(h, 0, a);
	runtime·f64hash(h, 0, (float64*)a+1);
}

void
runtime·slicecopy(uintptr s, void *a, void *b)
{
	USED(s);
	if(b == nil) {
		((Slice*)a)->array = 0;
		((Slice*)a)->len = 0;
		((Slice*)a)->cap = 0;
		return;
	}
	((Slice*)a)->array = ((Slice*)b)->array;
	((Slice*)a)->len = ((Slice*)b)->len;
	((Slice*)a)->cap = ((Slice*)b)->cap;
}

void
runtime·strhash(uintptr *h, uintptr s, void *a)
{
	USED(s);
	runtime·memhash(h, ((String*)a)->len, ((String*)a)->str);
}

void
runtime·strequal(bool *eq, uintptr s, void *a, void *b)
{
	intgo alen;
	byte *s1, *s2;

	USED(s);
	alen = ((String*)a)->len;
	if(alen != ((String*)b)->len) {
		*eq = false;
		return;
	}
	s1 = ((String*)a)->str;
	s2 = ((String*)b)->str;
	if(s1 == s2) {
		*eq = true;
		return;
	}
	*eq = runtime·memeq(s1, s2, alen);
}

void
runtime·strprint(uintptr s, void *a)
{
	USED(s);
	runtime·printstring(*(String*)a);
}

void
runtime·strcopy(uintptr s, void *a, void *b)
{
	USED(s);
	if(b == nil) {
		((String*)a)->str = 0;
		((String*)a)->len = 0;
		return;
	}
	((String*)a)->str = ((String*)b)->str;
	((String*)a)->len = ((String*)b)->len;
}

void
runtime·interhash(uintptr *h, uintptr s, void *a)
{
	USED(s);
	*h = runtime·ifacehash(*(Iface*)a, *h ^ M0) * M1;
}

void
runtime·interprint(uintptr s, void *a)
{
	USED(s);
	runtime·printiface(*(Iface*)a);
}

void
runtime·interequal(bool *eq, uintptr s, void *a, void *b)
{
	USED(s);
	*eq = runtime·ifaceeq_c(*(Iface*)a, *(Iface*)b);
}

void
runtime·intercopy(uintptr s, void *a, void *b)
{
	USED(s);
	if(b == nil) {
		((Iface*)a)->tab = 0;
		((Iface*)a)->data = 0;
		return;
	}
	((Iface*)a)->tab = ((Iface*)b)->tab;
	((Iface*)a)->data = ((Iface*)b)->data;
}

void
runtime·nilinterhash(uintptr *h, uintptr s, void *a)
{
	USED(s);
	*h = runtime·efacehash(*(Eface*)a, *h ^ M0) * M1;
}

void
runtime·nilinterprint(uintptr s, void *a)
{
	USED(s);
	runtime·printeface(*(Eface*)a);
}

void
runtime·nilinterequal(bool *eq, uintptr s, void *a, void *b)
{
	USED(s);
	*eq = runtime·efaceeq_c(*(Eface*)a, *(Eface*)b);
}

void
runtime·nilintercopy(uintptr s, void *a, void *b)
{
	USED(s);
	if(b == nil) {
		((Eface*)a)->type = 0;
		((Eface*)a)->data = 0;
		return;
	}
	((Eface*)a)->type = ((Eface*)b)->type;
	((Eface*)a)->data = ((Eface*)b)->data;
}

void
runtime·nohash(uintptr *h, uintptr s, void *a)
{
	USED(s);
	USED(a);
	USED(h);
	runtime·panicstring("hash of unhashable type");
}

void
runtime·noequal(bool *eq, uintptr s, void *a, void *b)
{
	USED(s);
	USED(a);
	USED(b);
	USED(eq);
	runtime·panicstring("comparing uncomparable types");
}

Alg
runtime·algarray[] =
{
[AMEM]		{ runtime·memhash, runtime·memequal, runtime·memprint, runtime·memcopy },
[ANOEQ]		{ runtime·nohash, runtime·noequal, runtime·memprint, runtime·memcopy },
[ASTRING]	{ runtime·strhash, runtime·strequal, runtime·strprint, runtime·strcopy },
[AINTER]	{ runtime·interhash, runtime·interequal, runtime·interprint, runtime·intercopy },
[ANILINTER]	{ runtime·nilinterhash, runtime·nilinterequal, runtime·nilinterprint, runtime·nilintercopy },
[ASLICE]	{ runtime·nohash, runtime·noequal, runtime·memprint, runtime·slicecopy },
[AFLOAT32]	{ runtime·f32hash, runtime·f32equal, runtime·memprint, runtime·memcopy },
[AFLOAT64]	{ runtime·f64hash, runtime·f64equal, runtime·memprint, runtime·memcopy },
[ACPLX64]	{ runtime·c64hash, runtime·c64equal, runtime·memprint, runtime·memcopy },
[ACPLX128]	{ runtime·c128hash, runtime·c128equal, runtime·memprint, runtime·memcopy },
[AMEM0]		{ runtime·memhash, runtime·memequal0, runtime·memprint, runtime·memcopy0 },
[AMEM8]		{ runtime·memhash, runtime·memequal8, runtime·memprint, runtime·memcopy8 },
[AMEM16]	{ runtime·memhash, runtime·memequal16, runtime·memprint, runtime·memcopy16 },
[AMEM32]	{ runtime·memhash, runtime·memequal32, runtime·memprint, runtime·memcopy32 },
[AMEM64]	{ runtime·memhash, runtime·memequal64, runtime·memprint, runtime·memcopy64 },
[AMEM128]	{ runtime·memhash, runtime·memequal128, runtime·memprint, runtime·memcopy128 },
[ANOEQ0]	{ runtime·nohash, runtime·noequal, runtime·memprint, runtime·memcopy0 },
[ANOEQ8]	{ runtime·nohash, runtime·noequal, runtime·memprint, runtime·memcopy8 },
[ANOEQ16]	{ runtime·nohash, runtime·noequal, runtime·memprint, runtime·memcopy16 },
[ANOEQ32]	{ runtime·nohash, runtime·noequal, runtime·memprint, runtime·memcopy32 },
[ANOEQ64]	{ runtime·nohash, runtime·noequal, runtime·memprint, runtime·memcopy64 },
[ANOEQ128]	{ runtime·nohash, runtime·noequal, runtime·memprint, runtime·memcopy128 },
};

// Runtime helpers.

// used in asm_{386,amd64}.s
#pragma dataflag NOPTR
byte runtime·aeskeysched[HashRandomBytes];

void
runtime·hashinit(void)
{
        if(NaCl)
                return;

	// Install aes hash algorithm if we have the instructions we need
	if((runtime·cpuid_ecx & (1 << 25)) != 0 &&  // aes (aesenc)
	   (runtime·cpuid_ecx & (1 << 9)) != 0 &&   // sse3 (pshufb)
	   (runtime·cpuid_ecx & (1 << 19)) != 0) {  // sse4.1 (pinsr{d,q})
		byte *rnd;
		int32 n;
		use_aeshash = true;
		runtime·algarray[AMEM].hash = runtime·aeshash;
		runtime·algarray[AMEM8].hash = runtime·aeshash;
		runtime·algarray[AMEM16].hash = runtime·aeshash;
		runtime·algarray[AMEM32].hash = runtime·aeshash32;
		runtime·algarray[AMEM64].hash = runtime·aeshash64;
		runtime·algarray[AMEM128].hash = runtime·aeshash;
		runtime·algarray[ASTRING].hash = runtime·aeshashstr;

		// Initialize with random data so hash collisions will be hard to engineer.
		runtime·get_random_data(&rnd, &n);
		if(n > HashRandomBytes)
			n = HashRandomBytes;
		runtime·memmove(runtime·aeskeysched, rnd, n);
		if(n < HashRandomBytes) {
			// Not very random, but better than nothing.
			int64 t = runtime·nanotime();
			while (n < HashRandomBytes) {
				runtime·aeskeysched[n++] = (int8)(t >> (8 * (n % 8)));
			}
		}
	}
}

// func equal(t *Type, x T, y T) (ret bool)
#pragma textflag NOSPLIT
void
runtime·equal(Type *t, ...)
{
	byte *x, *y;
	bool *ret;
	
	x = (byte*)ROUND((uintptr)(&t+1), t->align);
	y = x + t->size;
	ret = (bool*)ROUND((uintptr)(y+t->size), Structrnd);
	t->alg->equal(ret, t->size, x, y);
}

// Testing adapter for memclr
func memclrBytes(s Slice) {
	runtime·memclr(s.array, s.len);
}

// Testing adapters for hash quality tests (see hash_test.go)
func haveGoodHash() (res bool) {
	res = use_aeshash;
}

func stringHash(s String, seed uintptr) (res uintptr) {
	runtime·algarray[ASTRING].hash(&seed, sizeof(String), &s);
	res = seed;
}

func bytesHash(s Slice, seed uintptr) (res uintptr) {
	runtime·algarray[AMEM].hash(&seed, s.len, s.array);
	res = seed;
}

func int32Hash(i uint32, seed uintptr) (res uintptr) {
	runtime·algarray[AMEM32].hash(&seed, sizeof(uint32), &i);
	res = seed;
}

func int64Hash(i uint64, seed uintptr) (res uintptr) {
	runtime·algarray[AMEM64].hash(&seed, sizeof(uint64), &i);
	res = seed;
}