spawnmason / randar-explanation Goto Github PK

This lookup table works with no collisions because each mansion seed has a unique lower 32 bits, somehow. I don't understand why that's true, it's fascinating. You'd think it wouldn't work. But I think the coefficients 341873128712 and 132897987541 may have been specially chosen to make this work? Like, if you have 2.2 billion marbles, and 4.3 billion buckets, and you independently put each marble in a random bucket, what are the odds that each marble gets its own bucket? Essentially zero. Nearing the end, each new marble has a more than 50% chance of hitting a bucket that's already filled. Yet, clearly, these are not independently random, so somehow it works. Unironically if you're reading this and understand how this works or why those two specific coefficients make this work, please let me know.

To shine some light on the topic. The woodland seed function is a perfect hash of the cords (x,z) in the limited range. It is from the family of linear hash functions. Usual construction would require that parameters are co-prime to modulus and each-other but due to limited range of x and z the function is still injective despite one of the parameters not being co-prime with the modulus.

In case of only one input, if the parameter is co-prime to the modulus, it will create an additive group of size N, meaning it it will create a perfect hash for all values [0, N).
(I can write more on it latter).

I've been looking at this magnificent exploit closely since this paper is public and after a little bit of research in MC sources a question started to haunt me, how can we know item exact coordinates before protocol version 106 (release 1.9-pre4) since the server send 3 integers for x, y and z using floor_double method thus destroying the information of the exact position for the client since the client precision is down to a 1/32 of a block. I assume randar cannot run using block drop coordinates below 1.9 and it's necessary to find a pseudo random event with an output that the client can know with absolute precision, I am right ?

A key part of your algorithm is decoding the seed to find an x and z coordinate for a woodland region.

In other words, we have the equation:

seed = x * 341873128712 + z * 132897987541 - 4172144997891902323 mod 2^48

and we need to find x and z (both between -23440 and 23440).

You do this with a very large lookup table of size 2^32. A lookup table of that size is strictly not necessary and we can actually just use a HashMap with 46,881 entries, a reduction of about 5 orders of magnitude. This should also improve your speed quite tremendously, as you can do everything within cache (either CPU or GPU cache).

First, let us make x and z strictly positive by adding an offset of 23440 to each.

seed = (x - 23440) * 341873128712 + (z - 23440) * 132897987541 - 4172144997891902323 mod 2^48

If you simplify this out you get

seed = x * 341873128712 + z * 132897987541 + 7471016896829 mod 2^48

Important point: x and z are now always less than 16 bits

We can now do a bit more simplification, using the fact that 132897987541 is invertible mod 2^48

First, we subtract from both sides

(seed - 7471016896829 ) = x * 341873128712 + z * 132897987541 mod 2^48

Then, we multiply each side by 211541297333629

(seed - 7471016896829 ) * 211541297333629 = x * 341873128712 * 211541297333629 + z mod 2 ^ 48

Finally, we simplify

(seed - 7471016896829 ) * 211541297333629 = x * 1063476645096 + z mod 2 ^ 48

For the sake of simplicity, let seed* = (seed - 7471016896829 ) * 211541297333629 mod 2 ^ 48

seed* = x * 1063476645096 + z mod 2 ^ 48

Now we can make a key insight. z is at most 16 bits, so the upper bits of x * 1063476645096 should be mostly preserved.

Let >> be the bitwise shift operator.

(seed* >> 16) = (x * 1063476645096 >> 16) or (seed* >> 16) = (x * 1063476645096 >> 16) + 1

The key is to think about addition in terms of binary representation. There are two possibilities: the lower 16 bits of x * 1063476645096 and z sum to a number greater than 2^16 (aka there is a carry bit) or they sum to a number less than 2^16 (aka there is no carry bit).

All we have to do is create a lookup table that maps (x * 1063476645096 >> 16) mod 2 ^ 32 to x for all possible x values (which is from 0 to 46880). This table will only have 46881 entries. It turns out that (x * 1063476645096 >> 16) mod 2 ^ 32 => x is a unique mapping, so you can deterministically find the x given (x * 1063476645096 >> 16) mod 2 ^ 32. Note that the overall approach will still work even if it's not a unique mapping, it will just be more inefficient as you will have more values of x to check.

Now you can find x by simply looking at the table entries for (seed* >> 16) mod 2^ 32 and (seed* >> 16) - 1 mod 2^32.

That will get you two possible x values. You can then find two possible z values using the below formula:

z = x * 1063476645096 - seed* mod 2 ^ 48

Check both possible z's and you have your solution.