From 7bd4d6d96453229b436cbdfb78b877563a1e12df Mon Sep 17 00:00:00 2001 From: bartimaeusnek <33183715+bartimaeusnek@users.noreply.github.com> Date: Sat, 12 Jan 2019 21:09:19 +0100 Subject: Reworked Coords class +use the MurmurHash3 and optimised equals to run in a Hashset +added credits +added URL Signed-off-by: bartimaeusnek <33183715+bartimaeusnek@users.noreply.github.com> --- .../bartimaeusnek/bartworks/util/Coords.java | 28 +- .../bartimaeusnek/bartworks/util/MurmurHash3.java | 303 +++++++++++++++++++++ src/main/resources/mcmod.info | 4 +- 3 files changed, 328 insertions(+), 7 deletions(-) create mode 100644 src/main/java/com/github/bartimaeusnek/bartworks/util/MurmurHash3.java diff --git a/src/main/java/com/github/bartimaeusnek/bartworks/util/Coords.java b/src/main/java/com/github/bartimaeusnek/bartworks/util/Coords.java index 7d9f60015b..756f6ed7dc 100644 --- a/src/main/java/com/github/bartimaeusnek/bartworks/util/Coords.java +++ b/src/main/java/com/github/bartimaeusnek/bartworks/util/Coords.java @@ -26,7 +26,8 @@ import java.util.Objects; public class Coords { - public int x, y, z, wID; + public int x, z, wID; + public short y; public Coords(int x, int y, int z, int wID) { this(x, y, z); @@ -35,15 +36,17 @@ public class Coords { public Coords(int x, int y, int z) { this.x = x; - this.y = y; + this.y = (short) y; this.z = z; this.wID = 0; } @Override public boolean equals(Object o) { - if (this == o) return true; - if (o == null || this.getClass() != o.getClass()) return false; +// if (this == o) +// return true; +// if (o == null || this.getClass() != o.getClass()) +// return false; Coords coords = (Coords) o; return this.x == coords.x && this.y == coords.y && @@ -53,7 +56,22 @@ public class Coords { @Override public int hashCode() { - return Objects.hash(this.x, this.y, this.z, this.wID); + byte[] data = new byte[14]; + data[0]= (byte) (this.x & 0b1111); + data[1]= (byte) (this.x >> 4 & 0b1111); + data[2]= (byte) (this.x >> 8 & 0b1111); + data[3]= (byte) (this.x >> 12 & 0b1111); + data[4]= (byte) (this.y & 0b1111); + data[5]= (byte) (this.y >> 4 & 0b1111); + data[6]= (byte) (this.z & 0b1111); + data[7]= (byte) (this.z >> 4 & 0b1111); + data[8]= (byte) (this.z >> 8 & 0b1111); + data[9]= (byte) (this.z >> 12 & 0b1111); + data[10]= (byte) (this.wID & 0b1111); + data[11]= (byte) (this.wID >> 4 & 0b1111); + data[12]= (byte) (this.wID >> 8 & 0b1111); + data[13]= (byte) (this.wID >> 12 & 0b1111); + return MurmurHash3.murmurhash3_x86_32(data,0,14,31); } @Override diff --git a/src/main/java/com/github/bartimaeusnek/bartworks/util/MurmurHash3.java b/src/main/java/com/github/bartimaeusnek/bartworks/util/MurmurHash3.java new file mode 100644 index 0000000000..d0433145c7 --- /dev/null +++ b/src/main/java/com/github/bartimaeusnek/bartworks/util/MurmurHash3.java @@ -0,0 +1,303 @@ +/* + * The MurmurHash3 algorithm was created by Austin Appleby and placed in the public domain. + * This java port was authored by Yonik Seeley and also placed into the public domain. + * The author hereby disclaims copyright to this source code. + *

+ * This produces exactly the same hash values as the final C++ + * version of MurmurHash3 and is thus suitable for producing the same hash values across + * platforms. + *

+ * The 32 bit x86 version of this hash should be the fastest variant for relatively short keys like ids. + * murmurhash3_x64_128 is a good choice for longer strings or if you need more than 32 bits of hash. + *

+ * Note - The x86 and x64 versions do _not_ produce the same results, as the + * algorithms are optimized for their respective platforms. + *

+ * See http://github.com/yonik/java_util for future updates to this file. + * + * + * Special Thanks to Austin Appleby and Yonik Seeley for placing this in the public domain and therefore allowing me to use it! + */ +package com.github.bartimaeusnek.bartworks.util; + + +public final class MurmurHash3 { + + /** 128 bits of state */ + public static final class LongPair { + public long val1; + public long val2; + } + + public static final int fmix32(int h) { + h ^= h >>> 16; + h *= 0x85ebca6b; + h ^= h >>> 13; + h *= 0xc2b2ae35; + h ^= h >>> 16; + return h; + } + + public static final long fmix64(long k) { + k ^= k >>> 33; + k *= 0xff51afd7ed558ccdL; + k ^= k >>> 33; + k *= 0xc4ceb9fe1a85ec53L; + k ^= k >>> 33; + return k; + } + + /** Gets a long from a byte buffer in little endian byte order. */ + public static final long getLongLittleEndian(byte[] buf, int offset) { + return ((long)buf[offset+7] << 56) // no mask needed + | ((buf[offset+6] & 0xffL) << 48) + | ((buf[offset+5] & 0xffL) << 40) + | ((buf[offset+4] & 0xffL) << 32) + | ((buf[offset+3] & 0xffL) << 24) + | ((buf[offset+2] & 0xffL) << 16) + | ((buf[offset+1] & 0xffL) << 8) + | ((buf[offset ] & 0xffL)); // no shift needed + } + + + /** Returns the MurmurHash3_x86_32 hash. */ + public static int murmurhash3_x86_32(byte[] data, int offset, int len, int seed) { + + final int c1 = 0xcc9e2d51; + final int c2 = 0x1b873593; + + int h1 = seed; + int roundedEnd = offset + (len & 0xfffffffc); // round down to 4 byte block + + for (int i=offset; i>> 17); // ROTL32(k1,15); + k1 *= c2; + + h1 ^= k1; + h1 = (h1 << 13) | (h1 >>> 19); // ROTL32(h1,13); + h1 = h1*5+0xe6546b64; + } + + // tail + int k1 = 0; + + switch(len & 0x03) { + case 3: + k1 = (data[roundedEnd + 2] & 0xff) << 16; + // fallthrough + case 2: + k1 |= (data[roundedEnd + 1] & 0xff) << 8; + // fallthrough + case 1: + k1 |= (data[roundedEnd] & 0xff); + k1 *= c1; + k1 = (k1 << 15) | (k1 >>> 17); // ROTL32(k1,15); + k1 *= c2; + h1 ^= k1; + } + + // finalization + h1 ^= len; + + // fmix(h1); + h1 ^= h1 >>> 16; + h1 *= 0x85ebca6b; + h1 ^= h1 >>> 13; + h1 *= 0xc2b2ae35; + h1 ^= h1 >>> 16; + + return h1; + } + + + /** Returns the MurmurHash3_x86_32 hash of the UTF-8 bytes of the String without actually encoding + * the string to a temporary buffer. This is more than 2x faster than hashing the result + * of String.getBytes(). + */ + public static int murmurhash3_x86_32(CharSequence data, int offset, int len, int seed) { + + final int c1 = 0xcc9e2d51; + final int c2 = 0x1b873593; + + int h1 = seed; + + int pos = offset; + int end = offset + len; + int k1 = 0; + int k2 = 0; + int shift = 0; + int bits = 0; + int nBytes = 0; // length in UTF8 bytes + + + while (pos < end) { + int code = data.charAt(pos++); + if (code < 0x80) { + k2 = code; + bits = 8; + + /*** + // optimized ascii implementation (currently slower!!! code size?) + if (shift == 24) { + k1 = k1 | (code << 24); + + k1 *= c1; + k1 = (k1 << 15) | (k1 >>> 17); // ROTL32(k1,15); + k1 *= c2; + + h1 ^= k1; + h1 = (h1 << 13) | (h1 >>> 19); // ROTL32(h1,13); + h1 = h1*5+0xe6546b64; + + shift = 0; + nBytes += 4; + k1 = 0; + } else { + k1 |= code << shift; + shift += 8; + } + continue; + ***/ + + } + else if (code < 0x800) { + k2 = (0xC0 | (code >> 6)) + | ((0x80 | (code & 0x3F)) << 8); + bits = 16; + } + else if (code < 0xD800 || code > 0xDFFF || pos>=end) { + // we check for pos>=end to encode an unpaired surrogate as 3 bytes. + k2 = (0xE0 | (code >> 12)) + | ((0x80 | ((code >> 6) & 0x3F)) << 8) + | ((0x80 | (code & 0x3F)) << 16); + bits = 24; + } else { + // surrogate pair + // int utf32 = pos < end ? (int) data.charAt(pos++) : 0; + int utf32 = (int) data.charAt(pos++); + utf32 = ((code - 0xD7C0) << 10) + (utf32 & 0x3FF); + k2 = (0xff & (0xF0 | (utf32 >> 18))) + | ((0x80 | ((utf32 >> 12) & 0x3F))) << 8 + | ((0x80 | ((utf32 >> 6) & 0x3F))) << 16 + | (0x80 | (utf32 & 0x3F)) << 24; + bits = 32; + } + + + k1 |= k2 << shift; + + // int used_bits = 32 - shift; // how many bits of k2 were used in k1. + // int unused_bits = bits - used_bits; // (bits-(32-shift)) == bits+shift-32 == bits-newshift + + shift += bits; + if (shift >= 32) { + // mix after we have a complete word + + k1 *= c1; + k1 = (k1 << 15) | (k1 >>> 17); // ROTL32(k1,15); + k1 *= c2; + + h1 ^= k1; + h1 = (h1 << 13) | (h1 >>> 19); // ROTL32(h1,13); + h1 = h1*5+0xe6546b64; + + shift -= 32; + // unfortunately, java won't let you shift 32 bits off, so we need to check for 0 + if (shift != 0) { + k1 = k2 >>> (bits-shift); // bits used == bits - newshift + } else { + k1 = 0; + } + nBytes += 4; + } + + } // inner + + // handle tail + if (shift > 0) { + nBytes += shift >> 3; + k1 *= c1; + k1 = (k1 << 15) | (k1 >>> 17); // ROTL32(k1,15); + k1 *= c2; + h1 ^= k1; + } + + // finalization + h1 ^= nBytes; + + // fmix(h1); + h1 ^= h1 >>> 16; + h1 *= 0x85ebca6b; + h1 ^= h1 >>> 13; + h1 *= 0xc2b2ae35; + h1 ^= h1 >>> 16; + + return h1; + } + + + /** Returns the MurmurHash3_x64_128 hash, placing the result in "out". */ + public static void murmurhash3_x64_128(byte[] key, int offset, int len, int seed, LongPair out) { + // The original algorithm does have a 32 bit unsigned seed. + // We have to mask to match the behavior of the unsigned types and prevent sign extension. + long h1 = seed & 0x00000000FFFFFFFFL; + long h2 = seed & 0x00000000FFFFFFFFL; + + final long c1 = 0x87c37b91114253d5L; + final long c2 = 0x4cf5ad432745937fL; + + int roundedEnd = offset + (len & 0xFFFFFFF0); // round down to 16 byte block + for (int i=offset; i