raffle-seed-search2.cpp

// 日替わりseedで0x00000000に至るグラフを生成します

// see also raffle-seed-search.cpp
// https://gist.github.com/oupo/6271febe004f9fe7e036

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <assert.h>
#include <vector>
#include <set>

typedef uint32_t u32;
typedef uint64_t u64;

const u64 M = UINT64_C(1) << 32;
const u64 A = UINT64_C(0x5d583d6d6c078979);
const u64 B = UINT64_C(0x26a693);

std::set<u32> graph;

u32 f(u32 s) {
	return (A * s + B) >> 32;
}

bool bit_at(std::vector<u32> &seen, u32 s) {
	return (seen[s / 32] >> (s % 32)) & 1;
}

void bit_set(std::vector<u32> &seen, u32 s) {
	seen[s/32] |= 1u << (s%32);
}

#define ARRAY_SIZE(x) (sizeof(x)/sizeof(*(x)))

const u32 LOOP_STARTS[] = {0x79f18008, 0x2134bc83, 0x86e648d5, 0x12719a8c, 0x6cf5a895, 0x0e50bafa, 0x6a3db7e0, 0x04cbaf9f, 0x1c905da4, 0xeae02079};

static std::vector<u32> seen(M/32);

void fill_seen(u32 start, u32 end) {
	u32 s = start;
	while (true) {
		bit_set(seen, s);
		if (s == end) break;
		s = f(s);
	};
}

void fill_loops() {
	for (int i = 0; i < ARRAY_SIZE(LOOP_STARTS); i++) {
		u32 first = LOOP_STARTS[i];
		fill_seen(first, first);
	}
}

void add_graphs(u32 start) {
	u32 s = start;
	while (!bit_at(seen, s)) {
		graph.insert(s);
		printf("%.8x -> %.8x\n", s, f(s));
		bit_set(seen, s);
		s = f(s);
	}
}

void search(u32 start)
{
	u32 s = start;
	u32 end;
	
	while (true) {
		if (graph.find(f(s)) != graph.end()) {
			add_graphs(start);
			return;
		}
		if (bit_at(seen, s)) {
			end = s;
			fill_seen(start, end);
			return;
		}
		s = f(s);
	}
}

int main() {
	fill_loops();
	graph.insert(0);
	bit_set(seen, 0);
	for (u32 i = 1; i != 0; i++) {
		if ((i & 0xfffff) == 0) {
			printf("%.8x\r", i);
		}
		search(i);
	}
	printf("main\n");
}

~dot.rb

require "set"
dot = 'C:\Users\user\Downloads\graphviz-2.38\release\bin\dot'
nodes = Set[]
edges = []
STDIN.each_line do |x|
  m = x.match(/^([0-9a-f]+) -> ([0-9a-f]+)/)
  nodes << m[1] << m[2]
  edges << [m[1], m[2]]
end

open("t.dot", "wb") do |f|
  f.puts "digraph G {"
  nodes.each do |x|
    f.puts "_#{x} [label=\"0x#{x}\"];"
  end

  edges.each do |n1, n2|
    f.puts "_#{n1} -> _#{n2};"
  end
  f.puts "}"
end

system "#{dot} -Tgif t.dot -o t.gif"

実行結果です。