Skip to content

Instantly share code, notes, and snippets.

@oupo
Last active August 29, 2015 14:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save oupo/6271febe004f9fe7e036 to your computer and use it in GitHub Desktop.
Save oupo/6271febe004f9fe7e036 to your computer and use it in GitHub Desktop.
#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;
}
*** 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