Last active
August 29, 2015 14:07
-
-
Save oupo/f4fb9a6a27fdda6d4510 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 日替わり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"); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
実行結果です。
