import java.util.ArrayList;
import java.util.Random;


public class ReverseDecoratorHashRefactored {

    public static int countTrailingZeroes(long v) {
        int c;  // output: c will count v's trailing zero bits,
        // so if v is 1101000 (base 2), then c will be 3
        v = (v ^ (v - 1)) >> 1;  // Set v's trailing 0s to 1s and zero rest
        for (c = 0; v !=0; c++)
        {
            v >>>= 1;
        }
        return c;
    }

    public static long modInverse(long x, int mod) { //Fast method for modular inverse mod powers of 2
        long inv = 0;
        long b = 1;
        for (int i = 0; i < mod; i++) {
            if ((b & 1)==1) {
                inv |= 1L << i;
                b = (b - x) >> 1;
            } else {
                b >>= 1;
            }
        }
        return inv;
    }

    public static long getChunkseed(long seed, int x, int z) {
        Random r = new Random(seed);
        long a = r.nextLong()|1;
        long b = r.nextLong()|1;
        return ((x*a + z*b)^seed) & ((1L << 48) - 1);
    }

    private static final long mask16 = 0xffffL;
    private static final long mask32 = 0xffff_ffffL;

    private static final long m1 = 25214903917L; //the next 8 lines are constants for the lcg created by calling java lcg multiple times.
    //    private static final long addend1 = 11;
    private static final long m2 = 205749139540585L;
    private static final long addend2 = 277363943098L;
    //    private static final long m3 = 233752471717045L;
//    private static final long addend3 = 11718085204285L;
    private static final long m4 = 55986898099985L;
    private static final long addend4 = 49720483695876L;
    private static ArrayList<Long> worldseeds;

    public static ArrayList<Long> getSeedFromChunkseed(long chunkseed, int x, int z) {

        worldseeds = new ArrayList<>();

        if (x == 0 && z == 0) {
            worldseeds.add(chunkseed);
            return worldseeds;
        }

        long c; //a is upper 16 bits, b middle 16 bits, c lower 16 bits of worldseed.
        long e = chunkseed & ((1L << 32) - 1); //The algorithm proceeds by solving for worldseed in 16 bit groups
        long f = chunkseed & (((1L << 16) - 1)); //as such, we need the 16 bit groups of chunkseed for later eqns.

        boolean xEven = ((x&1) == 0);
        boolean zEven = ((z&1) == 0);

        long firstMultiplier = (m2*x + m4*z) & mask16;
        int multTrailingZeroes = countTrailingZeroes(firstMultiplier); //TODO currently code blows up if this is 16, but you can use it to get bits of seed anyway if it is non zero
        long firstMultInv = modInverse(firstMultiplier >> multTrailingZeroes,16);


        //TODO We can recover more initial bits when x + z is divisible by a power of 2
        if (xEven ^ zEven) { //bottom bit of x*a + z*b is odd so we xor by 1 to get bottom bit of worldseed.
            c = (chunkseed & 1)^1;
        } else { //bottom bit of x*a + z*b is even so we xor by 0 to get bottom bit of worldseed.
            c = (chunkseed & 1);
        }

        for (; c < (1L << 16); c+=2) { //iterate through all possible lower 16 bits of worldseed.
            long target = (c ^ f) & mask16; //now that we've guessed 16 bits of worldseed we can undo the mask

            //We need to handle the four different cases of the effect the two |1s have on the seed
            long magic = x * ((m2 * ((c ^ m1) & mask16) + addend2) >>> 16) + z * ((m4 * ((c ^ m1) & mask16) + addend4) >>> 16);

            addWorldSeed(target - (magic & mask16), multTrailingZeroes, firstMultInv, c, e, x, z, chunkseed); //case both nextLongs were odd

            addWorldSeed(target - ((magic + x) & mask16), multTrailingZeroes, firstMultInv, c, e, x, z, chunkseed); //case where x nextLong even

            addWorldSeed(target - ((magic + z) & mask16), multTrailingZeroes, firstMultInv, c, e, x, z, chunkseed); //case where z nextLong even

            addWorldSeed(target - ((magic + x + z) & mask16), multTrailingZeroes, firstMultInv, c, e, x, z, chunkseed); //case where both nextLongs even
        }

        return worldseeds;
    }

    public static long makeSecondAddend(int x, long k, int z) {
        return ((((long)x)*(((int)(((m2*((k^m1)& mask32) + addend2) & ((1L<<48)-1)) >>> 16))|1) +
                ((long)z)*(((int)(((m4*((k^m1)& mask32) + addend4) & ((1L<<48)-1)) >>> 16))|1)) >>> 16) & mask16;
    }

    public static void addWorldSeed(long firstAddend, int multTrailingZeroes, long firstMultInv, long c, long e, int x, int z, long chunkseed){
        if (countTrailingZeroes(firstAddend) >= multTrailingZeroes) { //Does there exist a set of 16 bits which work for bits 17-32
            long b = ((((firstMultInv * firstAddend)>>> multTrailingZeroes)^(m1 >> 16)) & ((1L << (16-multTrailingZeroes))-1));
            //System.out.println(Long.toHexString(b));
            for(; b < (1L << 16); b += (1L << (16 - multTrailingZeroes))) { //if the previous multiplier had a power of 2 divisor, we get multiple solutions for b
                long k = (b << 16) + c;
                long target2 = (k ^ e) >> 16; //now that we know b, we can undo more of the mask
                long secondAddend = makeSecondAddend(x, k, z);
                if (countTrailingZeroes(target2 - secondAddend) >= multTrailingZeroes) { //Does there exist a set of 16 bits which work for bits 33-48
                    long a = ((((firstMultInv * (target2 - secondAddend)) >>> multTrailingZeroes)^(m1 >> 32)) & ((1L << (16-multTrailingZeroes))-1));
                    for(; a < (1L << 16); a += (1L << (16 - multTrailingZeroes))) { //if the previous multiplier had a power of 2 divisor, we get multiple solutions for a
                        if (getChunkseed((a << 32) + k, x, z) == chunkseed) { //lazy check if the test has succeeded
                            worldseeds.add((a << 32) + k);
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        long seed;
        int x , z;
        ArrayList<Long> seeds;
        /*long seed = 40820992642153L;
        int x = 2;
        int z = 4;
        ArrayList<Long> seeds = getSeedFromChunkseed(getChunkseed(seed, x, z), x, z);
        System.out.println("start");
        for (long a : seeds) {
            System.out.println(a);
        }
        System.out.println("done");*/
        Random r = new Random();
        int failcount = 0;
        System.out.println("start");
        long start = System.currentTimeMillis();
        for(int i = 0; i < 100000; i++){
            seed = r.nextLong() & ((1L << 48)-1);
            x = r.nextInt(16) - 8;
            z = r.nextInt(16) - 8;
            seeds = getSeedFromChunkseed(getChunkseed(seed,x,z),x,z);
            if (!seeds.contains(seed)) {
                System.out.println(seed);
                System.out.println(x);
                System.out.println(z);
                failcount++;
                System.out.println();
            }
        }
        System.out.println("End: "+((System.currentTimeMillis()-start)/1000.0));
        System.out.println(failcount+" failures.");
    }
}