001package squidpony.squidmath; 002 003/** 004 * A group of similar methods for getting hashes of points based on int coordinates in 2, 3, 4, or 6 dimensions and 005 * an int for state; the code is similar to {@link HastyPointHash} but will be much faster on GWT. This 006 * implementation has high enough quality to be useful as a source of random numbers based on positions, but would 007 * likely not be a good option in a hash table (or at least not as good as the tailored implementation of 008 * {@link Coord#hashCode()}; it is still better than {@link java.util.Objects#hash(Object...)}). Even on a desktop 009 * JVM, this class is faster than {@link PointHash} or {@link HastyPointHash}. The technique used here 010 * owes credit to Pelle Evensen for finding the significant quality increase from using multiple bitwise rotations XORed 011 * together, and Martin Roberts for discovering the connection between higher dimensional ranks and the appropriate 012 * numbers to gain similar qualities to adding the golden ratio mod 1 in 1D, using what had already been named 013 * "harmonious numbers." The only case where this can return different results on GWT than on a desktop or mobile 014 * JVM is when the inputs are GWT-specific out-of-range JS Numbers appearing to be ints, and that's a problem with 015 * the input rather than the algorithm. 016 * <br> 017 * Getting the bottom 24 bits of {@link #hashAll(int, int, int)}, dividing to get a float from 0 to 1, and graphing 018 * it produces <a href="https://i.imgur.com/vYWzVAR.png">this white-noise-like image</a>. The frequency magnitude of 019 * that image is <a href="https://i.imgur.com/6N39FPQ.png">this diagram</a>, which looks almost exactly like 020 * <a href="https://i.imgur.com/RSdUnSY.png">a diagram of the frequency magnitude of white noise</a>. This shows 021 * there are effectively no significant structural artifacts in the noise when interpreted as a float. 022 */ 023public final class IntPointHash extends IPointHash.IntImpl { 024 025 @Override 026 public int hashWithState(int x, int y, int state) { 027 return hashAll(x, y, state); 028 } 029 030 @Override 031 public int hashWithState(int x, int y, int z, int state) { 032 return hashAll(x, y, z, state); 033 } 034 035 @Override 036 public int hashWithState(int x, int y, int z, int w, int state) { 037 return hashAll(x, y, z, w, state); 038 } 039 040 @Override 041 public int hashWithState(int x, int y, int z, int w, int u, int v, int state) { 042 return hashAll(x, y, z, w, u, v, state); 043 } 044 045 /** 046 * A 32-bit point hash that smashes x and y into s using XOR and multiplications by harmonious numbers, 047 * then runs a simple unary hash on s and returns it. Has better performance than HastyPointHash, especially for 048 * ints, and has slightly fewer collisions in a hash table of points. GWT-optimized. Inspired by Pelle Evensen's 049 * rrxmrrxmsx_0 unary hash, though this doesn't use its code or its full algorithm. The unary hash used here has 050 * been stripped down heavily, both for speed and because unless points are selected specifically to target 051 * flaws in the hash, it doesn't need the intense resistance to bad inputs that rrxmrrxmsx_0 has. 052 * @param x x position, as an int 053 * @param y y position, as an int 054 * @param s any int, a seed to be able to produce many hashes for a given point 055 * @return 32-bit hash of the x,y point with the given state s 056 */ 057 public static int hashAll(int x, int y, int s) { 058 s ^= x * 0x1827F5 ^ y * 0x123C21; 059 return (s = (s ^ (s << 19 | s >>> 13) ^ (s << 5 | s >>> 27) ^ 0xD1B54A35) * 0x125493) ^ s >>> 11; 060 } 061 /** 062 * A 32-bit point hash that smashes x, y, and z into s using XOR and multiplications by harmonious numbers, 063 * then runs a simple unary hash on s and returns it. Has better performance than HastyPointHash, especially for 064 * ints, and has slightly fewer collisions in a hash table of points. GWT-optimized. Inspired by Pelle Evensen's 065 * rrxmrrxmsx_0 unary hash, though this doesn't use its code or its full algorithm. The unary hash used here has 066 * been stripped down heavily, both for speed and because unless points are selected specifically to target 067 flaws in the hash, it doesn't need the intense resistance to bad inputs that rrxmrrxmsx_0 has. 068 * @param x x position, as an int 069 * @param y y position, as an int 070 * @param z z position, as an int 071 * @param s any int, a seed to be able to produce many hashes for a given point 072 * @return 32-bit hash of the x,y,z point with the given state s 073 */ 074 public static int hashAll(int x, int y, int z, int s) { 075 s ^= x * 0x1A36A9 ^ y * 0x157931 ^ z * 0x119725; 076 return (s = (s ^ (s << 19 | s >>> 13) ^ (s << 5 | s >>> 27) ^ 0xD1B54A35) * 0x125493) ^ s >>> 11; 077 } 078 079 /** 080 * A 32-bit point hash that smashes x, y, z, and w into s using XOR and multiplications by harmonious numbers, 081 * then runs a simple unary hash on s and returns it. Has better performance than HastyPointHash, especially for 082 * ints, and has slightly fewer collisions in a hash table of points. GWT-optimized. Inspired by Pelle Evensen's 083 * rrxmrrxmsx_0 unary hash, though this doesn't use its code or its full algorithm. The unary hash used here has 084 * been stripped down heavily, both for speed and because unless points are selected specifically to target 085 * flaws in the hash, it doesn't need the intense resistance to bad inputs that rrxmrrxmsx_0 has. 086 * @param x x position, as an int 087 * @param y y position, as an int 088 * @param z z position, as an int 089 * @param w w position, as an int 090 * @param s any int, a seed to be able to produce many hashes for a given point 091 * @return 32-bit hash of the x,y,z,w point with the given state s 092 */ 093 public static int hashAll(int x, int y, int z, int w, int s) { 094 s ^= x * 0x1B69E1 ^ y * 0x177C0B ^ z * 0x141E5D ^ w * 0x113C31; 095 return (s = (s ^ (s << 19 | s >>> 13) ^ (s << 5 | s >>> 27) ^ 0xD1B54A35) * 0x125493) ^ s >>> 11; 096 } 097 098 /** 099 * A 32-bit point hash that smashes x, y, z, w, u, and v into s using XOR and multiplications by harmonious 100 * numbers, then runs a simple unary hash on s and returns it. Has better performance than HastyPointHash, 101 * especially for ints, and has slightly fewer collisions in a hash table of points. GWT-optimized. Inspired by 102 * Pelle Evensen's rrxmrrxmsx_0 unary hash, though this doesn't use its code or its full algorithm. The unary 103 * hash used here has been stripped down heavily, both for speed and because unless points are selected 104 * specifically to target flaws in the hash, it doesn't need the intense resistance to bad inputs that 105 * rrxmrrxmsx_0 has. 106 * @param x x position, as an int 107 * @param y y position, as an int 108 * @param z z position, as an int 109 * @param w w position, as an int 110 * @param u u position, as an int 111 * @param v v position, as an int 112 * @param s any int, a seed to be able to produce many hashes for a given point 113 * @return 32-bit hash of the x,y,z,w,u,v point with the given state s 114 */ 115 public static int hashAll(int x, int y, int z, int w, int u, int v, int s) { 116 s ^= x * 0x1CC1C5 ^ y * 0x19D7AF ^ z * 0x173935 ^ w * 0x14DEAF ^ u * 0x12C139 ^ v * 0x10DAA3; 117 return (s = (s ^ (s << 19 | s >>> 13) ^ (s << 5 | s >>> 27) ^ 0xD1B54A35) * 0x125493) ^ s >>> 11; 118 } 119 120 /** 121 * A 8-bit point hash that smashes x and y into s using XOR and multiplications by harmonious numbers, 122 * then runs a simple unary hash on s and returns it. Has better performance than HastyPointHash, especially for 123 * ints, and has slightly fewer collisions in a hash table of points. GWT-optimized. Inspired by Pelle Evensen's 124 * rrxmrrxmsx_0 unary hash, though this doesn't use its code or its full algorithm. The unary hash used here has 125 * been stripped down heavily, both for speed and because unless points are selected specifically to target 126 * flaws in the hash, it doesn't need the intense resistance to bad inputs that rrxmrrxmsx_0 has. 127 * @param x x position, as an int 128 * @param y y position, as an int 129 * @param s any int, a seed to be able to produce many hashes for a given point 130 * @return 8-bit hash of the x,y point with the given state s 131 */ 132 public static int hash256(int x, int y, int s) { 133 s ^= x * 0x1827F5 ^ y * 0x123C21; 134 return (s ^ (s << 19 | s >>> 13) ^ (s << 5 | s >>> 27) ^ 0xD1B54A35) * 0x125493 >>> 24; 135 } 136 /** 137 * A 8-bit point hash that smashes x, y, and z into s using XOR and multiplications by harmonious numbers, 138 * then runs a simple unary hash on s and returns it. Has better performance than HastyPointHash, especially for 139 * ints, and has slightly fewer collisions in a hash table of points. GWT-optimized. Inspired by Pelle Evensen's 140 * rrxmrrxmsx_0 unary hash, though this doesn't use its code or its full algorithm. The unary hash used here has 141 * been stripped down heavily, both for speed and because unless points are selected specifically to target 142 flaws in the hash, it doesn't need the intense resistance to bad inputs that rrxmrrxmsx_0 has. 143 * @param x x position, as an int 144 * @param y y position, as an int 145 * @param z z position, as an int 146 * @param s any int, a seed to be able to produce many hashes for a given point 147 * @return 8-bit hash of the x,y,z point with the given state s 148 */ 149 public static int hash256(int x, int y, int z, int s) { 150 s ^= x * 0x1A36A9 ^ y * 0x157931 ^ z * 0x119725; 151 return (s ^ (s << 19 | s >>> 13) ^ (s << 5 | s >>> 27) ^ 0xD1B54A35) * 0x125493 >>> 24; 152 } 153 154 /** 155 * A 8-bit point hash that smashes x, y, z, and w into s using XOR and multiplications by harmonious numbers, 156 * then runs a simple unary hash on s and returns it. Has better performance than HastyPointHash, especially for 157 * ints, and has slightly fewer collisions in a hash table of points. GWT-optimized. Inspired by Pelle Evensen's 158 * rrxmrrxmsx_0 unary hash, though this doesn't use its code or its full algorithm. The unary hash used here has 159 * been stripped down heavily, both for speed and because unless points are selected specifically to target 160 * flaws in the hash, it doesn't need the intense resistance to bad inputs that rrxmrrxmsx_0 has. 161 * @param x x position, as an int 162 * @param y y position, as an int 163 * @param z z position, as an int 164 * @param w w position, as an int 165 * @param s any int, a seed to be able to produce many hashes for a given point 166 * @return 8-bit hash of the x,y,z,w point with the given state s 167 */ 168 public static int hash256(int x, int y, int z, int w, int s) { 169 s ^= x * 0x1B69E1 ^ y * 0x177C0B ^ z * 0x141E5D ^ w * 0x113C31; 170 return (s ^ (s << 19 | s >>> 13) ^ (s << 5 | s >>> 27) ^ 0xD1B54A35) * 0x125493 >>> 24; 171 } 172 173 /** 174 * A 8-bit point hash that smashes x, y, z, w, u, and v into s using XOR and multiplications by harmonious 175 * numbers, then runs a simple unary hash on s and returns it. Has better performance than HastyPointHash, 176 * especially for ints, and has slightly fewer collisions in a hash table of points. GWT-optimized. Inspired by 177 * Pelle Evensen's rrxmrrxmsx_0 unary hash, though this doesn't use its code or its full algorithm. The unary 178 * hash used here has been stripped down heavily, both for speed and because unless points are selected 179 * specifically to target flaws in the hash, it doesn't need the intense resistance to bad inputs that 180 * rrxmrrxmsx_0 has. 181 * @param x x position, as an int 182 * @param y y position, as an int 183 * @param z z position, as an int 184 * @param w w position, as an int 185 * @param u u position, as an int 186 * @param v v position, as an int 187 * @param s any int, a seed to be able to produce many hashes for a given point 188 * @return 8-bit hash of the x,y,z,w,u,v point with the given state s 189 */ 190 public static int hash256(int x, int y, int z, int w, int u, int v, int s) { 191 s ^= x * 0x1CC1C5 ^ y * 0x19D7AF ^ z * 0x173935 ^ w * 0x14DEAF ^ u * 0x12C139 ^ v * 0x10DAA3; 192 return (s ^ (s << 19 | s >>> 13) ^ (s << 5 | s >>> 27) ^ 0xD1B54A35) * 0x125493 >>> 24; 193 } 194 195 /** 196 * A 6-bit point hash that smashes x and y into s using XOR and multiplications by harmonious numbers, 197 * then runs a simple unary hash on s and returns it. Has better performance than HastyPointHash, especially for 198 * ints, and has slightly fewer collisions in a hash table of points. GWT-optimized. Inspired by Pelle Evensen's 199 * rrxmrrxmsx_0 unary hash, though this doesn't use its code or its full algorithm. The unary hash used here has 200 * been stripped down heavily, both for speed and because unless points are selected specifically to target 201 * flaws in the hash, it doesn't need the intense resistance to bad inputs that rrxmrrxmsx_0 has. 202 * @param x x position, as an int 203 * @param y y position, as an int 204 * @param s any int, a seed to be able to produce many hashes for a given point 205 * @return 6-bit hash of the x,y point with the given state s 206 */ 207 public static int hash64(int x, int y, int s) { 208 s ^= x * 0x1827F5 ^ y * 0x123C21; 209 return (s ^ (s << 19 | s >>> 13) ^ (s << 5 | s >>> 27) ^ 0xD1B54A35) * 0x125493 >>> 26; 210 } 211 /** 212 * A 6-bit point hash that smashes x, y, and z into s using XOR and multiplications by harmonious numbers, 213 * then runs a simple unary hash on s and returns it. Has better performance than HastyPointHash, especially for 214 * ints, and has slightly fewer collisions in a hash table of points. GWT-optimized. Inspired by Pelle Evensen's 215 * rrxmrrxmsx_0 unary hash, though this doesn't use its code or its full algorithm. The unary hash used here has 216 * been stripped down heavily, both for speed and because unless points are selected specifically to target 217 flaws in the hash, it doesn't need the intense resistance to bad inputs that rrxmrrxmsx_0 has. 218 * @param x x position, as an int 219 * @param y y position, as an int 220 * @param z z position, as an int 221 * @param s any int, a seed to be able to produce many hashes for a given point 222 * @return 6-bit hash of the x,y,z point with the given state s 223 */ 224 public static int hash64(int x, int y, int z, int s) { 225 s ^= x * 0x1A36A9 ^ y * 0x157931 ^ z * 0x119725; 226 return (s ^ (s << 19 | s >>> 13) ^ (s << 5 | s >>> 27) ^ 0xD1B54A35) * 0x125493 >>> 26; 227 } 228 229 /** 230 * A 6-bit point hash that smashes x, y, z, and w into s using XOR and multiplications by harmonious numbers, 231 * then runs a simple unary hash on s and returns it. Has better performance than HastyPointHash, especially for 232 * ints, and has slightly fewer collisions in a hash table of points. GWT-optimized. Inspired by Pelle Evensen's 233 * rrxmrrxmsx_0 unary hash, though this doesn't use its code or its full algorithm. The unary hash used here has 234 * been stripped down heavily, both for speed and because unless points are selected specifically to target 235 * flaws in the hash, it doesn't need the intense resistance to bad inputs that rrxmrrxmsx_0 has. 236 * @param x x position, as an int 237 * @param y y position, as an int 238 * @param z z position, as an int 239 * @param w w position, as an int 240 * @param s any int, a seed to be able to produce many hashes for a given point 241 * @return 6-bit hash of the x,y,z,w point with the given state s 242 */ 243 public static int hash64(int x, int y, int z, int w, int s) { 244 s ^= x * 0x1B69E1 ^ y * 0x177C0B ^ z * 0x141E5D ^ w * 0x113C31; 245 return (s ^ (s << 19 | s >>> 13) ^ (s << 5 | s >>> 27) ^ 0xD1B54A35) * 0x125493 >>> 26; 246 } 247 248 /** 249 * A 6-bit point hash that smashes x, y, z, w, u, and v into s using XOR and multiplications by harmonious 250 * numbers, then runs a simple unary hash on s and returns it. Has better performance than HastyPointHash, 251 * especially for ints, and has slightly fewer collisions in a hash table of points. GWT-optimized. Inspired by 252 * Pelle Evensen's rrxmrrxmsx_0 unary hash, though this doesn't use its code or its full algorithm. The unary 253 * hash used here has been stripped down heavily, both for speed and because unless points are selected 254 * specifically to target flaws in the hash, it doesn't need the intense resistance to bad inputs that 255 * rrxmrrxmsx_0 has. 256 * @param x x position, as an int 257 * @param y y position, as an int 258 * @param z z position, as an int 259 * @param w w position, as an int 260 * @param u u position, as an int 261 * @param v v position, as an int 262 * @param s any int, a seed to be able to produce many hashes for a given point 263 * @return 6-bit hash of the x,y,z,w,u,v point with the given state s 264 */ 265 public static int hash64(int x, int y, int z, int w, int u, int v, int s) { 266 s ^= x * 0x1CC1C5 ^ y * 0x19D7AF ^ z * 0x173935 ^ w * 0x14DEAF ^ u * 0x12C139 ^ v * 0x10DAA3; 267 return (s ^ (s << 19 | s >>> 13) ^ (s << 5 | s >>> 27) ^ 0xD1B54A35) * 0x125493 >>> 26; 268 } 269 /** 270 * A 5-bit point hash that smashes x and y into s using XOR and multiplications by harmonious numbers, 271 * then runs a simple unary hash on s and returns it. Has better performance than HastyPointHash, especially for 272 * ints, and has slightly fewer collisions in a hash table of points. GWT-optimized. Inspired by Pelle Evensen's 273 * rrxmrrxmsx_0 unary hash, though this doesn't use its code or its full algorithm. The unary hash used here has 274 * been stripped down heavily, both for speed and because unless points are selected specifically to target 275 * flaws in the hash, it doesn't need the intense resistance to bad inputs that rrxmrrxmsx_0 has. 276 * @param x x position, as an int 277 * @param y y position, as an int 278 * @param s any int, a seed to be able to produce many hashes for a given point 279 * @return 5-bit hash of the x,y point with the given state s 280 */ 281 public static int hash32(int x, int y, int s) { 282 s ^= x * 0x1827F5 ^ y * 0x123C21; 283 return (s ^ (s << 19 | s >>> 13) ^ (s << 5 | s >>> 27) ^ 0xD1B54A35) * 0x125493 >>> 27; 284 } 285 /** 286 * A 5-bit point hash that smashes x, y, and z into s using XOR and multiplications by harmonious numbers, 287 * then runs a simple unary hash on s and returns it. Has better performance than HastyPointHash, especially for 288 * ints, and has slightly fewer collisions in a hash table of points. GWT-optimized. Inspired by Pelle Evensen's 289 * rrxmrrxmsx_0 unary hash, though this doesn't use its code or its full algorithm. The unary hash used here has 290 * been stripped down heavily, both for speed and because unless points are selected specifically to target 291 flaws in the hash, it doesn't need the intense resistance to bad inputs that rrxmrrxmsx_0 has. 292 * @param x x position, as an int 293 * @param y y position, as an int 294 * @param z z position, as an int 295 * @param s any int, a seed to be able to produce many hashes for a given point 296 * @return 5-bit hash of the x,y,z point with the given state s 297 */ 298 public static int hash32(int x, int y, int z, int s) { 299 s ^= x * 0x1A36A9 ^ y * 0x157931 ^ z * 0x119725; 300 return (s ^ (s << 19 | s >>> 13) ^ (s << 5 | s >>> 27) ^ 0xD1B54A35) * 0x125493 >>> 27; 301 } 302 303 /** 304 * A 5-bit point hash that smashes x, y, z, and w into s using XOR and multiplications by harmonious numbers, 305 * then runs a simple unary hash on s and returns it. Has better performance than HastyPointHash, especially for 306 * ints, and has slightly fewer collisions in a hash table of points. GWT-optimized. Inspired by Pelle Evensen's 307 * rrxmrrxmsx_0 unary hash, though this doesn't use its code or its full algorithm. The unary hash used here has 308 * been stripped down heavily, both for speed and because unless points are selected specifically to target 309 * flaws in the hash, it doesn't need the intense resistance to bad inputs that rrxmrrxmsx_0 has. 310 * @param x x position, as an int 311 * @param y y position, as an int 312 * @param z z position, as an int 313 * @param w w position, as an int 314 * @param s any int, a seed to be able to produce many hashes for a given point 315 * @return 5-bit hash of the x,y,z,w point with the given state s 316 */ 317 public static int hash32(int x, int y, int z, int w, int s) { 318 s ^= x * 0x1B69E1 ^ y * 0x177C0B ^ z * 0x141E5D ^ w * 0x113C31; 319 return (s ^ (s << 19 | s >>> 13) ^ (s << 5 | s >>> 27) ^ 0xD1B54A35) * 0x125493 >>> 27; 320 } 321 322 /** 323 * A 5-bit point hash that smashes x, y, z, w, u, and v into s using XOR and multiplications by harmonious 324 * numbers, then runs a simple unary hash on s and returns it. Has better performance than HastyPointHash, 325 * especially for ints, and has slightly fewer collisions in a hash table of points. GWT-optimized. Inspired by 326 * Pelle Evensen's rrxmrrxmsx_0 unary hash, though this doesn't use its code or its full algorithm. The unary 327 * hash used here has been stripped down heavily, both for speed and because unless points are selected 328 * specifically to target flaws in the hash, it doesn't need the intense resistance to bad inputs that 329 * rrxmrrxmsx_0 has. 330 * @param x x position, as an int 331 * @param y y position, as an int 332 * @param z z position, as an int 333 * @param w w position, as an int 334 * @param u u position, as an int 335 * @param v v position, as an int 336 * @param s any int, a seed to be able to produce many hashes for a given point 337 * @return 5-bit hash of the x,y,z,w,u,v point with the given state s 338 */ 339 public static int hash32(int x, int y, int z, int w, int u, int v, int s) { 340 s ^= x * 0x1CC1C5 ^ y * 0x19D7AF ^ z * 0x173935 ^ w * 0x14DEAF ^ u * 0x12C139 ^ v * 0x10DAA3; 341 return (s ^ (s << 19 | s >>> 13) ^ (s << 5 | s >>> 27) ^ 0xD1B54A35) * 0x125493 >>> 27; 342 } 343 344 345}