To extend the solution found in Linalg Fixed Seeds to the 2-3 guaranteed IV cases, we need to consider a few things:
With this in mind we know that if we could account for the variable amount of calls that happen, as well as determine which IVs are natural, we could easily build a form of the matrix detailed before.
Consider the 3 guaranteed IV case where all natural IVs are non 31. Because there are no natural 31s, the value and order of the natural IVs are obvious and can be used to calculate the fixed seed. The only issue in this case is the variable amount of "advances" that happen prior to the natural IVs being generated. The amount of advances could theoretically span the discrete interval
Though there may not be a set limit, here we can abuse the fact that there are a finite amount of seeds and therefore is a concrete limit determined by the seed with the most advances. Testing via brute-forcing, we find that in this case the interval is restricted to
In the event where there is a natural 31 IV, it is not possible to easily discern which IV is actually natural. To take another simple approach, we will just look at every possible scenario that would produce those IVs. For example, the IVs
With this in mind searching all guaranteed IV values can be broken down into the following process
from itertools import combinations advance_ranges = (None, None, (2 + 2, 2 + 26), (2 + 3, 2 + 36)) target_iv_values = np.array([...], np.uint8) (perfect_ivs,) = np.where(target_iv_values == 31) for guaranteed_ivs in (0, 2, 3): if guaranteed_ivs == 0: advances = 2 natural_iv_values = target_iv_values[:3] ... # default to the original algorithm else: for non_natural_ivs in combinations(perfect_ivs, guaranteed_ivs): natural_ivs = tuple(set(range(6)) ^ set(non_natural_ivs))[:3] natural_iv_values = target_iv_values[natural_ivs] for advances in range(*advance_ranges[guaranteed_ivs]): ... # find seeds based on advances and natural iv values
import sys from itertools import product, combinations # pyodide support if sys.platform == "emscripten": import micropip await micropip.install("numpy") import numpy as np class Xoroshiro128PlusGF: """Xoroshiro128+ Generator used in GameFreak games""" XOROSHIRO_CONST = np.uint64(0x82A2B175229D6A5B) def __init__( self, seed_0: np.uint64, seed_1: np.uint64 = XOROSHIRO_CONST ) -> None: self.state = np.empty(2, np.uint64) self.state[:] = seed_0, seed_1 @staticmethod def rotl(integer: np.uint64, shift: np.uint64) -> np.uint64: """Rotate the bits of a 64-bit unsigned integer left by a specified shift""" return ( (np.uint64(integer) << np.uint64(shift)) | (np.uint64(integer) >> np.uint64(64 - shift)) ) @staticmethod def bit_mask(integer: np.uint32) -> np.uint32: """Generate a bitmask for a 32-bit integer""" return np.uint32((1 << (int(integer).bit_length())) - 1) def next_full(self) -> np.uint64: """Generate the next 64-bit random number""" seed_0, seed_1 = self.state result = seed_0 + seed_1 seed_1 ^= seed_0 self.state[:] = ( self.rotl(seed_0, 24) ^ seed_1 ^ (seed_1 << np.uint64(16)), self.rotl(seed_1, 37) ) return result def next(self) -> np.uint32: """Generate the next 32-bit random number""" return np.uint32(self.next_full()) def rand_max(self, maximum: np.uint32) -> np.uint32: """Generate the next random number < maximum""" maximum = np.uint32(maximum) mask = self.bit_mask(maximum - 1) result = self.next() & mask while result >= maximum: result = self.next() & mask return result def generate_ivs(fixed_seed: int, guaranteeed_ivs: int) -> list[int]: """Generate ivs from a fixed seed""" rng = Xoroshiro128PlusGF(fixed_seed) rng.next_full() rng.next_full() ivs = [None, None, None, None, None, None] for _ in range(guaranteed_ivs): iv_index = rng.rand_max(6) while ivs[iv_index] is not None: iv_index = rng.rand_max(6) ivs[iv_index] = 31 for iv_index in range(6): if ivs[iv_index] is None: ivs[iv_index] = rng.rand_max(32) return ivs def int_to_bit_vector(integer: int, bit_length: int) -> np.ndarray: """Convert an integer to its bit vector representation""" bit_vec = np.empty(bit_length, np.uint8) bit_vec[:] = list(((int(integer) >> i) & 1 for i in range(bit_length))) return bit_vec def bit_vector_to_int(bit_vector: np.ndarray) -> int: """Convert a bit vector to its integer representation""" integer = 0 for i, bit in enumerate(bit_vector): integer |= int(bit) << i return integer def shift_matrix(matrix: np.ndarray, k: int) -> np.ndarray: """Build the k-th shifted matrix of matrix""" shifted_matrix = np.roll(matrix, -k, axis = 0) shifted_matrix[:, :k] = 0 return shifted_matrix def rotate_matrix(matrix: np.ndarray, k: int) -> np.ndarray: """Build the k-th rotated matrix of matrix""" return np.roll(matrix, -k, axis = 0) def xoroshiro128plus_mat() -> np.ndarray: """Build the 128x128 Xoroshiro128+ state transition matrix""" s0_mat = np.zeros((128, 64), np.uint8) s1_mat = np.zeros((128, 64), np.uint8) s0_mat[0:64] = np.identity(64, np.uint8) s1_mat[64:128] = np.identity(64, np.uint8) s1_mat ^= s0_mat s0_mat = (s0_mat @ rotate_matrix(np.identity(64, np.uint8), 24)) % 2 s0_mat ^= s1_mat s0_mat ^= (s1_mat @ shift_matrix(np.identity(64, np.uint8), 16)) % 2 s1_mat = (s1_mat @ rotate_matrix(np.identity(64, np.uint8), 37)) % 2 return np.hstack((s0_mat, s1_mat)) def build_map_mats(advances: int) -> tuple[np.ndarray, np.ndarray]: """Build the 32x30 and 64x30 matrices that map from fixed_seed -> ivs and xoroshiro constant -> ivs respectively""" X = xoroshiro128plus_mat() L = np.empty((32, 0), np.uint8) C = np.empty((64, 0), np.uint8) for k in range(advances, advances + 3): X_k = np.identity(128, np.uint8) for _ in range(k): X_k = (X_k @ X) % 2 for col in (1, 2, 3, 4, 5, 65, 66, 67, 68, 69): L = np.hstack((L, X_k[:32, col - 1].reshape(-1, 1))) C = np.hstack((C, X_k[64:, col - 1].reshape(-1, 1))) return L, C def resize(matrix: np.ndarray, new_shape: tuple) -> np.ndarray: """Resize a matrix, truncating and filling with zeros""" mat_rows, mat_cols = matrix.shape new_rows, new_cols = new_shape new_mat = np.zeros(new_shape, np.uint8) new_mat[: min(mat_rows, new_rows), : min(mat_cols, new_cols)] = matrix[ : min(mat_rows, new_rows), : min(mat_cols, new_cols) ] return new_mat def reduced_row_echelon_form( matrix: np.ndarray ) -> tuple[np.ndarray, np.ndarray, int, list[int]]: """Convert a matrix to reduced row echelon form""" rows, columns = matrix.shape reduced_form = np.copy(matrix) inverse_form = np.identity(rows, np.uint8) rank = 0 pivots = [] for j in range(columns): for i in range(rank, rows): if reduced_form[i, j]: for k in range(rows): if (k != i) and reduced_form[k, j]: reduced_form[k] ^= reduced_form[i] inverse_form[k] ^= inverse_form[i] reduced_form[[i, rank]] = reduced_form[[rank, i]] inverse_form[[i, rank]] = inverse_form[[rank, i]] pivots.append(j) rank += 1 break return reduced_form, inverse_form, rank, pivots def generalized_inverse(matrix: np.ndarray) -> np.ndarray: """Compute the generalized inverse of a matrix""" _, inverse_form, rank, pivots = reduced_row_echelon_form(matrix) inverse_form = resize(inverse_form, (matrix.shape[1], matrix.shape[0])) for i in range(rank - 1, -1, -1): column_index = pivots[i] inverse_form[[i, column_index]] = inverse_form[[column_index, i]] return inverse_form def co_kernel_basis(matrix: np.ndarray) -> np.ndarray: """Compute the basis for the cokernel of a matrix""" matrix_inverse = generalized_inverse(matrix) basis = (matrix @ matrix_inverse) % 2 basis = (basis + np.identity(basis.shape[0], np.uint8)) % 2 basis, _, rank, _ = reduced_row_echelon_form(basis) return basis[:rank] def co_kernel(matrix: np.ndarray) -> np.ndarray: """Compute the cokernel of a matrix""" basis = co_kernel_basis(matrix) space = np.zeros((2 ** basis.shape[0], basis.shape[1]), np.uint8) for k in range(space.shape[0]): vector = np.zeros(basis.shape[1], np.uint8) for i in range(basis.shape[0]): if (k >> i) & 1: vector ^= basis[i] space[k] = vector return space def find_seeds(advances, guaranteed_ivs, natural_iv_values, target_ivs): L, C = build_map_mats(advances) L_plus = generalized_inverse(L) c = ( int_to_bit_vector(Xoroshiro128PlusGF.XOROSHIRO_CONST, 64) @ C ) % 2 L_co_kernel = co_kernel(L) fixed_seeds = [] for seed_1_values in product(range(32), range(32), range(32)): observable_bits = [] for iv_index, seed_1_value in enumerate(seed_1_values): seed_0_value = (natural_iv_values[iv_index] - seed_1_value) & 31 # bits 1,2,3,4,5 observable_bits.extend( (seed_0_value >> bit_index) & 1 for bit_index in range(5) ) # bits 65,66,67,68,69 observable_bits.extend( (seed_1_value >> bit_index) & 1 for bit_index in range(5) ) # account for the xoroshiro constant observable_bit_vector = (np.array(observable_bits, np.uint8) - c) % 2 # if the vector does not produce a valid solution, skip it if any( ((observable_bit_vector @ L_plus @ L) % 2) != observable_bit_vector ): continue principal_solution = (observable_bit_vector @ L_plus) % 2 for co_kernel_vector in L_co_kernel: solution = (principal_solution + co_kernel_vector) % 2 solution = bit_vector_to_int(solution) solution_ivs = generate_ivs(solution, guaranteed_ivs) if solution_ivs == target_ivs: print(f"Valid Fixed Seed: {fixed_seed:08X}") fixed_seeds.append(solution) advance_ranges = (None, None, (2 + 2, 2 + 26), (2 + 3, 2 + 36)) target_iv_values = np.array([0, 0, 0, 0, 0, 0], np.uint8) (perfect_ivs,) = np.where(target_iv_values == 0) for guaranteed_ivs in (0, 2, 3): if guaranteed_ivs == 0: advances = 2 natural_iv_values = target_iv_values[:3] find_seeds(advances, guaranteed_ivs, natural_iv_values, target_ivs) else: for non_natural_ivs in combinations(perfect_ivs, guaranteed_ivs): natural_ivs = tuple(set(range(6)) ^ set(non_natural_ivs))[:3] natural_iv_values = target_iv_values[natural_ivs] for advances in range(*advance_ranges[guaranteed_ivs]): find_seeds(advances, guaranteed_ivs, natural_iv_values, target_ivs)