Skip to content

Instantly share code, notes, and snippets.

@mjtb49
Created March 15, 2021 04:26
Show Gist options
  • Save mjtb49/4fc1befca5431c693fe157cfb9b509b4 to your computer and use it in GitHub Desktop.
Save mjtb49/4fc1befca5431c693fe157cfb9b509b4 to your computer and use it in GitHub Desktop.
import java.util.*;
public class AdditionUnderXOR {
static final int SS = 1000000;
enum Ore {
COAL(60005),
IRON(60006),
GOLD(60007),
REDSTONE(60008),
DIAMOND(60009),
LAPIS(60010);
public final int salt;
Ore(int salt) {
this.salt = salt;
}
}
enum Disk {
SWAMP_CLAY(60011),
RIVER_CLAY(60012),
GRAVEL(60013);
public final int salt;
Disk(int salt) {
this.salt = salt;
}
}
static long powMod(long base, int pow) {
long answer = 1;
while (pow != 0) {
if ((pow & 1) == 1)
answer = (base * answer) & 0xffff_ffff_ffffL;
base = (base * base) & 0xffff_ffff_ffffL;
pow >>>= 1;
}
return answer;
}
/*
* Adapted from https://www.geeksforgeeks.org/sorting-a-hashmap-according-to-values/
*/
static HashMap<ArrayList<Long>, Integer> sortByValue(HashMap<ArrayList<Long>, Integer> hm)
{
// Create a list from elements of HashMap
List<Map.Entry<ArrayList<Long>, Integer> > list = new LinkedList<>(hm.entrySet());
// Sort the list
list.sort(Map.Entry.comparingByValue());
// put data from sorted list to hashmap
HashMap<ArrayList<Long>, Integer> temp = new LinkedHashMap<>();
for (Map.Entry<ArrayList<Long>, Integer> aa : list) {
temp.put(aa.getKey(), aa.getValue());
}
return temp;
}
/*
* Adapted from https://www.geeksforgeeks.org/sorting-a-hashmap-according-to-values/
*/
static HashMap<ArrayList<Long>, Integer> sortByValueDescending(HashMap<ArrayList<Long>, Integer> hm)
{
// Create a list from elements of HashMap
List<Map.Entry<ArrayList<Long>, Integer> > list = new LinkedList<>(hm.entrySet());
// Sort the list
list.sort(Map.Entry.comparingByValue());
Collections.reverse(list);
// put data from sorted list to hashmap
HashMap<ArrayList<Long>, Integer> temp = new LinkedHashMap<>();
for (Map.Entry<ArrayList<Long>, Integer> aa : list) {
temp.put(aa.getKey(), aa.getValue());
}
return temp;
}
static HashMap<ArrayList<Long>, Integer> getOffsets(Disk disk, Ore ore) {
return getOffsets(disk, ore, false, 0);
}
static HashMap<ArrayList<Long>, Integer> getOffsets(Disk disk, Ore ore, boolean useResidue, int residue) {
HashMap<ArrayList<Long>, Integer> offsets = new HashMap<>();
Random r = new Random();
long targetSalt = ore.salt;
long[] measuredSalts = {disk.salt}; // intent is eventually to handle multiple decorators
long lmult = 0x5deece66dL;
long mask = 0xffff_ffff_ffffL;
long seed;
for (int i = 0; i < SS; i++) {
if (useResidue)
seed = ((r.nextLong() << 4) + residue) & mask;
else
seed = r.nextLong() & mask;
ArrayList<Long> key = new ArrayList<>(measuredSalts.length);
for (long salt: measuredSalts) {
key.add((((seed + targetSalt) ^ lmult) - ((seed + salt) ^ lmult)) & mask);
}
if (offsets.containsKey(key)) {
int current = offsets.get(key);
offsets.replace(key, current + 1);
} else {
offsets.put(key, 1);
}
}
return offsets;
}
static boolean residueReliable(Disk disk, Ore ore, int residue) {
return getOffsets(disk, ore, true, residue).size() == 1;
}
static void printTableForPublic(Disk disk, Ore ore, int maxLines) {
int total = 0;
for (int i = 0; i < 16; i++) //lmao this is terrible
if (residueReliable(disk,ore,i)) total++;
System.out.println(disk + " " + ore + " will work reliably on " + total / 16.0 * 100 +"% of seeds.");
HashMap<ArrayList<Long>, Integer> offsets = getOffsets(disk, ore);
int i = 0;
for (Map.Entry<ArrayList<Long>, Integer> en : sortByValueDescending(offsets).entrySet()) {
if ( i >= maxLines)
continue;
i++;
ArrayList<Long> vecs = en.getKey();
int precision = 16;
long blockToSeed = (1L << 48) / precision;
long s1 = (vecs.get(0) * 0x5deece66dL) & 0xffff_ffff_ffffL;
long s2 = (s1 * 0x5deece66dL) & 0xffff_ffff_ffffL;
//long s3 = (s2 * lmult) & mask; //these correspond to the size to depth conversion - too complex
//for public
//System.out.print( s1 / blockToSeed + " ");
System.out.print("Z offset " + s2 / blockToSeed + " occurs with probability ");
//System.out.print(s3 / blockToSeed + " ");
System.out.println(en.getValue() / (double) SS);
}
System.out.println();
offsets.clear();
}
static void printTableForMe(Disk disk, Ore ore) {
HashMap<ArrayList<Long>, Integer> offsets = getOffsets(disk, ore);
long lmult = 0x5deece66dL;
long mask = 0xffff_ffff_ffffL;
for (Map.Entry<ArrayList<Long>, Integer> en : sortByValue(offsets).entrySet()) {
ArrayList<Long> vecs = en.getKey();
//for (int call = 0; call < 3; call++) {
for (int i = 0; i < vecs.size(); i++) {
if (i == 0) {
long s1 = (vecs.get(0) * lmult) & mask;
long s2 = (s1 * lmult) & mask;
long s3 = (s2 * lmult) & mask;
System.out.printf("%012X", s1);
System.out.print(" " + String.format("%012X", s2));
System.out.print(" " + String.format("%012X", s3));
System.out.println(" " + en.getValue() / (double) SS);
} else {
long offset = vecs.get(i) - vecs.get(0);
long s1 = (offset * lmult) & mask;
long s2 = (s1 * lmult) & mask;
long s3 = (s2 * lmult) & mask;
System.out.printf("%012X", s1);
System.out.print(" " + String.format("%012X", s2));
System.out.print(" " + String.format("%012X", s3));
System.out.println(" " + en.getValue() / (double) SS);
}
}
}
System.out.println();
offsets.clear();
}
public static void main(String[] args) {
final int MAX_LINES = 5;
for (Disk disk: Disk.values()) {
for (Ore ore : Ore.values()) {
printTableForPublic(disk, ore, MAX_LINES);
}
}
}
}
@ha6000
Copy link

ha6000 commented Mar 16, 2021

wow! what exciting code!!

@MarcinK50
Copy link

good job 👍

@arskiy
Copy link

arskiy commented Mar 25, 2021

awesome research! keep up the great work

@YHDiamond
Copy link

how

@BrainStone
Copy link

Would be super cool if you added code to spit out the numbers for a known seed!

@BrainStone
Copy link

Btw the residue function can be simplified to this:

    static boolean residueOrSeedReliable(Disk disk, Ore ore, long residueOrSeed) {
        return ((disk.salt + residueOrSeed) & 0x10) == ((ore.salt + residueOrSeed) & 0x10);
    }

Updated snippet can be seen here: https://gist.github.com/BrainStone/8f4a453b05189645a4d077d0ace72fcc

You are free to merge these changes back into this main function here.

@MrAn0nym
Copy link

MrAn0nym commented Apr 18, 2021

Would be super cool if you added code to spit out the numbers for a known seed!

Set SS to 1, remove this:
if (useResidue) seed = ((r.nextLong() << 4) + residue) & mask; else seed = r.nextLong() & mask;
and change the initialization of seed to long seed = <your seed>;
(If I'm not wrong)

@MrAn0nym
Copy link

Would be super cool if you added code to spit out the numbers for a known seed!

Set SS to 1, remove this:
if (useResidue) seed = ((r.nextLong() << 4) + residue) & mask; else seed = r.nextLong() & mask;
and change the initialization of seed to long seed = ;
(If I'm not wrong)

*You have to make sure that you indicate your seed as long by adding L to the end of your seed ^^

@BrainStone
Copy link

Would be super cool if you added code to spit out the numbers for a known seed!

Set SS to 1, remove this:
if (useResidue) seed = ((r.nextLong() << 4) + residue) & mask; else seed = r.nextLong() & mask;
and change the initialization of seed to long seed = ;
(If I'm not wrong)

Thanks for the comment. But I forked the project already and modified it, so it's all good ^^

@nfitzen
Copy link

nfitzen commented Aug 2, 2021

Would it be possible to release this under a free software license?

You could just put something like the following text at the top:

// Copyright (C) 2021 mjtb49 <https://github.com/mjtb49>
// 
// SPDX-License-Identifier: Apache-2.0

(Obviously, this text is for Apache-2.0. Replace it with whatever SPDX license expression under which you want to license the program, such as CC0-1.0 or MIT.)

This way, people can (legally) modify and run the code. One person already made a fork, but it's of questionable legality because it doesn't have a license. (Edit: while the idea-expression divide could apply here, I doubt many people who want to use this code are lawyers.)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment