Last active
August 29, 2015 14:07
-
-
Save oupo/6271febe004f9fe7e036 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
#include <stdio.h> | |
#include <stdint.h> | |
#include <inttypes.h> | |
#include <assert.h> | |
#include <vector> | |
#include <map> | |
typedef uint32_t u32; | |
typedef uint64_t u64; | |
const u64 M = UINT64_C(1) << 32; | |
std::vector<u32> seen(M/32); | |
std::vector<u32> seen2(M/32); | |
std::map<u32, int> seed_to_loop_id; | |
std::vector<int> loops; | |
const u64 A = UINT64_C(0x5d583d6d6c078979); | |
const u64 B = UINT64_C(0x26a693); | |
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); | |
} | |
void store_loop_id(u32 first_s, int id) | |
{ | |
u32 s = first_s; | |
while (true) { | |
s = f(s); | |
seed_to_loop_id[s] = id; | |
if (s == first_s) break; | |
} | |
} | |
int find_loop_id(u32 first_s) | |
{ | |
u32 s = first_s; | |
int i = 0; | |
while (true) { | |
auto it = seed_to_loop_id.find(s); | |
if (it != seed_to_loop_id.end()) { | |
return it->second; | |
} | |
s = f(s); | |
i ++; | |
if (s == first_s) { | |
int id = loops.size(); | |
printf("*** new loop!! %d %u %.8x\n", id, i, s); | |
loops.push_back(i); | |
store_loop_id(s, id); | |
return id; | |
} | |
} | |
} | |
void search(u32 start) | |
{ | |
u32 s = start; | |
u32 end; | |
while (true) { | |
if (bit_at(seen, s)) { | |
end = s; | |
break; | |
} | |
if (bit_at(seen2, s)) { | |
end = s; | |
int loop_id = find_loop_id(s); | |
break; | |
} | |
bit_set(seen2, s); | |
s = f(s); | |
} | |
// copy to seen from seen2 | |
s = start; | |
while (s != end) { | |
bit_set(seen, s); | |
s = f(s); | |
} | |
} | |
int main(int argc, char** argv) | |
{ | |
for (u32 i = 1; i != 0; i++) { | |
if ((i & 0xffff) == 0) printf("%.8x\r", i); | |
search(i); | |
} | |
printf("finish\n"); | |
getchar(); | |
return 0; | |
} | |
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
*** new loop!! 0 83458 79f18008 | |
*** new loop!! 1 123305 2134bc83 | |
*** new loop!! 2 31719 86e648d5 | |
*** new loop!! 3 2598 12719a8c | |
*** new loop!! 4 2466 6cf5a895 | |
*** new loop!! 5 773 0e50bafa | |
*** new loop!! 6 6 6a3db7e0 | |
*** new loop!! 7 25 04cbaf9f | |
*** new loop!! 8 15 1c905da4 | |
*** new loop!! 9 1 00000000 | |
*** new loop!! 10 1 eae02079 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment