diff options
Diffstat (limited to 'src/pkg/runtime/alg.goc')
| -rw-r--r-- | src/pkg/runtime/alg.goc | 549 |
1 files changed, 549 insertions, 0 deletions
diff --git a/src/pkg/runtime/alg.goc b/src/pkg/runtime/alg.goc new file mode 100644 index 000000000..f1b8d5982 --- /dev/null +++ b/src/pkg/runtime/alg.goc @@ -0,0 +1,549 @@ +// 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; +} |