rand-solver.go

// rand-solver.go - GPL - Ported of a rust version by @bjrnove 

// Discovers the seed value for the first rand() value by bruting all possible seed values for perls 
// srand() in under a second

// $ go build rand-solver.go
// $ ./rand-solver $(perl -E 'my $r = rand(); warn "Got rand() output: $r\n"; say $r * 2**48')

package main

import (
	"fmt"
	"math"
	"os"
	"runtime"
	"strconv"
	"sync"
	"time"
)

type Rand struct {
	state uint64
}

func Seeded(v uint32) Rand {
	return Rand{(uint64(v) << 16) | 0x330e}
}

func (r *Rand) NextRaw() uint64 {
	r.state = (r.state*0x5deece66d + 0xb) & ((1 << 48) - 1)
	return r.state
}

func (r *Rand) NextNormal() float64 {
	return float64(r.NextRaw()) * math.Pow(2, -48)
}

func main() {
	if len(os.Args) < 2 {
		fmt.Fprintln(os.Stderr, "Expected the first rand() value as the argument")
		os.Exit(1)
	}

	firstValue, err := strconv.ParseUint(os.Args[1], 10, 64)
	if err != nil {
		fmt.Fprintln(os.Stderr, "The argument should be an unsigned integer")
		os.Exit(1)
	}

	start := time.Now()

	numCores := runtime.NumCPU()
	runtime.GOMAXPROCS(numCores)

	seedsToTry := uint64(0x1_0000_0000) // 2^32
	chunkSize := seedsToTry / uint64(numCores)

	firstValueAsF64 := float64(firstValue) / float64(uint64(1)<<48)
	wantValue := uint64(firstValueAsF64 * math.Pow(2, 48))

	fmt.Printf("Using %d cores\n", numCores)
	fmt.Printf("First value as float: %.15f\n", firstValueAsF64)
	fmt.Printf("First value re-calculated: %.15f\n", firstValueAsF64)
	fmt.Printf("Converted first value: %.15f\n", firstValueAsF64*float64(uint64(1)<<48))

	type pair struct{ a, b uint64 }
	var ranges []pair
	for s := uint64(0); s < seedsToTry; s += chunkSize {
		ranges = append(ranges, pair{s, s + chunkSize})
	}
	if len(ranges) > 0 {
		ranges[len(ranges)-1].b = 0xffff_ffff // exclusive; mirrors Rust
	}

	var wg sync.WaitGroup
	wg.Add(len(ranges))

	for id, r := range ranges {
		id := id
		r := r
		go func() {
			defer wg.Done()
			fmt.Printf("Thread %d: %08x..%08x\n", id, r.a, r.b)
			for seed := r.a; seed < r.b; seed++ {
				rng := Seeded(uint32(seed))
				if wantValue == rng.NextRaw() {
					fmt.Printf("Thread %d got seed: %d\n", id, uint32(seed))
				}
			}
		}()
	}

	wg.Wait()
	fmt.Printf("Tried all possible seeds in %.6f seconds\n", time.Since(start).Seconds())
}