/* * uuid256.c — reference implementation of README.md (UUID256, random layout) * plus an exact duplicate-detection harness for very large runs. * * Build: cc -O3 -pthread -o uuid256 uuid256.c * Run: ./uuid256 # 1,000,000,000 ids, print duplicates * ./uuid256 -n 1000000 -i 3 # 1e6 ids with 3 planted duplicates (self-test) * ./uuid256 -h * * Spec implementation (the part you would ship): * uuid256_generate() §5 32 bytes from the OS CSPRNG, then set ver=4 / var=10 * uuid256_to_canonical() §3 16-8-8-8-24 lowercase hex, 68 chars * uuid256_parse() §6 canonical or compact form, strict/lenient * uuid256_is_strict() §6 ver == 4 && var == 10 * * Duplicate-detection harness: * 1e9 ids × 32 B = 32 GB, too much to hold, so the run is made *replayable*: * a ChaCha20 DRBG (RFC 8439 block function, computed 4 blocks at a time with * SIMD; -R 12/8 for fewer rounds) is keyed ONCE from the OS CSPRNG * (arc4random_buf / getrandom) — the same construction the OS RNGs use * internally, so every id still satisfies §5.2 — and id #i is defined as * keystream bytes [32i, 32i+32) with §4 version/variant applied. Because the * stream is seekable, we can: * (a) make S passes over all N ids keeping only the shard whose top bits * match, storing ONE 8-byte entry per id (40-bit index + the 24 prefix * bits after the shard/region bits) straight into one of 4096 regions * chosen by 12 more prefix bits, * (b) radix-sort each region by key and take equal-key pairs as candidates, * (c) regenerate every candidate pair by index and compare all 32 bytes. * A full duplicate always has an equal prefix, so (a)+(b) has no false * negatives, and (c) removes the false positives. Peak memory ≈ 8.3 B × N/S. * -i K plants K known duplicates to prove the detector fires. */ #define _GNU_SOURCE #include #include #include #include #include #include #include #include #include #include #include #include #if defined(__APPLE__) || defined(__FreeBSD__) || defined(__OpenBSD__) || defined(__NetBSD__) # include /* arc4random_buf */ # define HAVE_ARC4RANDOM 1 #elif defined(__linux__) # include /* getrandom */ # define HAVE_GETRANDOM 1 #endif /* ========================================================================== */ /* Spec §3–§6: the UUID256 API */ /* ========================================================================== */ #define UUID256_BYTES 32 #define UUID256_TEXT_LEN 68 /* 64 hex + 4 hyphens */ #define UUID256_VERSION 0x4 static const char HEX[] = "0123456789abcdef"; /* §5.2 — OS cryptographically secure random source. */ static void os_random(void *buf, size_t n) { #if defined(HAVE_ARC4RANDOM) arc4random_buf(buf, n); #elif defined(HAVE_GETRANDOM) uint8_t *p = buf; while (n) { ssize_t r = getrandom(p, n, 0); if (r < 0) { if (errno == EINTR) continue; perror("getrandom"); exit(1); } p += r; n -= (size_t)r; } #else FILE *f = fopen("/dev/urandom", "rb"); if (!f || fread(buf, 1, n, f) != n) { perror("/dev/urandom"); exit(1); } fclose(f); #endif } /* §4 — force version nibble (byte 12) and variant bits (byte 16). */ static inline void uuid256_set_ver_var(uint8_t b[UUID256_BYTES]) { b[12] = (uint8_t)((b[12] & 0x0F) | (UUID256_VERSION << 4)); /* hex digit 24 = '4' */ b[16] = (uint8_t)((b[16] & 0x3F) | 0x80); /* hex digit 32 in [89ab] */ } /* §5.1 — generate one id straight from the OS CSPRNG. */ static void uuid256_generate(uint8_t out[UUID256_BYTES]) { os_random(out, UUID256_BYTES); uuid256_set_ver_var(out); } /* §6 — strict version/variant check. */ static inline bool uuid256_is_strict(const uint8_t b[UUID256_BYTES]) { return (b[12] >> 4) == UUID256_VERSION && (b[16] >> 6) == 0x2; } /* §3.1 — canonical text: 16-8-8-8-24, lowercase, NUL-terminated (69 bytes). */ static void uuid256_to_canonical(const uint8_t b[UUID256_BYTES], char out[UUID256_TEXT_LEN + 1]) { static const int group_end_bytes[5] = { 8, 12, 16, 20, 32 }; /* 16,8,8,8,24 hex digits */ int g = 0, o = 0; for (int i = 0; i < UUID256_BYTES; i++) { out[o++] = HEX[b[i] >> 4]; out[o++] = HEX[b[i] & 0x0F]; if (i + 1 == group_end_bytes[g] && g < 4) { out[o++] = '-'; g++; } } out[o] = '\0'; } /* §6 — parse canonical (68) or compact (64) form. Returns 0 on success; `out` is written only on success. */ enum { UUID256_OK = 0, UUID256_ERR_LENGTH, UUID256_ERR_HYPHEN, UUID256_ERR_CHAR, UUID256_ERR_VERSION }; static int hexval(int c) { if (c >= '0' && c <= '9') return c - '0'; if (c >= 'a' && c <= 'f') return c - 'a' + 10; if (c >= 'A' && c <= 'F') return c - 'A' + 10; return -1; } static int uuid256_parse(const char *s, uint8_t out[UUID256_BYTES], bool strict) { if (!s) return UUID256_ERR_LENGTH; size_t len = strlen(s); bool hyphenated; if (len == UUID256_TEXT_LEN) { if (s[16] != '-' || s[25] != '-' || s[34] != '-' || s[43] != '-') return UUID256_ERR_HYPHEN; hyphenated = true; } else if (len == 64) { hyphenated = false; } else return UUID256_ERR_LENGTH; uint8_t tmp[UUID256_BYTES]; /* decode into a scratch buffer so a rejected */ int nib = 0; uint8_t cur = 0; int bi = 0; /* string never leaves partial bytes in `out` */ for (size_t i = 0; i < len; i++) { if (hyphenated && (i == 16 || i == 25 || i == 34 || i == 43)) continue; int v = hexval((unsigned char)s[i]); if (v < 0) return UUID256_ERR_CHAR; cur = (uint8_t)((cur << 4) | v); if (++nib == 2) { tmp[bi++] = cur; nib = 0; cur = 0; } } if (strict && !uuid256_is_strict(tmp)) return UUID256_ERR_VERSION; memcpy(out, tmp, UUID256_BYTES); return UUID256_OK; } /* ========================================================================== */ /* ChaCha DRBG (RFC 8439 block function, 64-bit block counter in words 12..13) */ /* ========================================================================== */ #define ROTL32(v, n) (((v) << (n)) | ((v) >> (32 - (n)))) #define QR(a, b, c, d) \ a += b; d ^= a; d = ROTL32(d, 16); \ c += d; b ^= c; b = ROTL32(b, 12); \ a += b; d ^= a; d = ROTL32(d, 8); \ c += d; b ^= c; b = ROTL32(b, 7); typedef struct { uint32_t st[16]; int rounds; } chacha_ctx; /* words 12,13 = counter lo/hi; 14,15 = nonce */ static uint32_t load_le32(const uint8_t *p) { return (uint32_t)p[0] | ((uint32_t)p[1] << 8) | ((uint32_t)p[2] << 16) | ((uint32_t)p[3] << 24); } static void chacha_init(chacha_ctx *c, const uint8_t key[32], const uint8_t nonce[8], int rounds) { c->st[0] = 0x61707865; c->st[1] = 0x3320646e; c->st[2] = 0x79622d32; c->st[3] = 0x6b206574; for (int i = 0; i < 8; i++) c->st[4 + i] = load_le32(key + 4 * i); c->st[12] = c->st[13] = 0; c->st[14] = load_le32(nonce); c->st[15] = load_le32(nonce + 4); c->rounds = rounds; } /* One 64-byte block. */ static void chacha_block(const chacha_ctx *c, uint64_t counter, uint8_t out[64]) { uint32_t in[16], x[16]; memcpy(in, c->st, sizeof in); in[12] = (uint32_t)counter; in[13] = (uint32_t)(counter >> 32); memcpy(x, in, sizeof x); for (int i = 0; i < c->rounds; i += 2) { QR(x[0], x[4], x[8], x[12]) QR(x[1], x[5], x[9], x[13]) QR(x[2], x[6], x[10], x[14]) QR(x[3], x[7], x[11], x[15]) QR(x[0], x[5], x[10], x[15]) QR(x[1], x[6], x[11], x[12]) QR(x[2], x[7], x[8], x[13]) QR(x[3], x[4], x[9], x[14]) } for (int i = 0; i < 16; i++) { uint32_t v = x[i] + in[i]; out[4*i] = (uint8_t)v; out[4*i+1] = (uint8_t)(v >> 8); out[4*i+2] = (uint8_t)(v >> 16); out[4*i+3] = (uint8_t)(v >> 24); } } /* Four consecutive blocks (counter .. counter+3) at once, one block per SIMD lane. Written with the GCC/clang vector extension so the same source becomes NEON on arm64 and SSE/AVX on x86; the output is bit-identical to four calls of chacha_block() (checked in the self-tests). */ #if defined(__GNUC__) || defined(__clang__) typedef uint32_t v4u32 __attribute__((vector_size(16))); #define ROTL4(v, n) (((v) << (n)) | ((v) >> (32 - (n)))) #define QR4(a, b, c, d) \ a += b; d ^= a; d = ROTL4(d, 16); \ c += d; b ^= c; b = ROTL4(b, 12); \ a += b; d ^= a; d = ROTL4(d, 8); \ c += d; b ^= c; b = ROTL4(b, 7); static void chacha_block4(const chacha_ctx *c, uint64_t counter, uint8_t out[256]) { v4u32 in[16], x[16]; for (int i = 0; i < 16; i++) { uint32_t w = c->st[i]; in[i] = (v4u32){ w, w, w, w }; } for (int l = 0; l < 4; l++) { uint64_t ctr = counter + (uint64_t)l; in[12][l] = (uint32_t)ctr; in[13][l] = (uint32_t)(ctr >> 32); } for (int i = 0; i < 16; i++) x[i] = in[i]; for (int i = 0; i < c->rounds; i += 2) { QR4(x[0], x[4], x[8], x[12]) QR4(x[1], x[5], x[9], x[13]) QR4(x[2], x[6], x[10], x[14]) QR4(x[3], x[7], x[11], x[15]) QR4(x[0], x[5], x[10], x[15]) QR4(x[1], x[6], x[11], x[12]) QR4(x[2], x[7], x[8], x[13]) QR4(x[3], x[4], x[9], x[14]) } for (int i = 0; i < 16; i++) { v4u32 v = x[i] + in[i]; for (int l = 0; l < 4; l++) { uint32_t w = v[l]; uint8_t *o = out + 64 * l + 4 * i; o[0] = (uint8_t)w; o[1] = (uint8_t)(w >> 8); o[2] = (uint8_t)(w >> 16); o[3] = (uint8_t)(w >> 24); } } } #else static void chacha_block4(const chacha_ctx *c, uint64_t counter, uint8_t out[256]) { for (int l = 0; l < 4; l++) chacha_block(c, counter + (uint64_t)l, out + 64 * l); } #endif /* ========================================================================== */ /* Harness state */ /* ========================================================================== */ typedef struct { uint64_t src, dst; } inject_t; /* id[dst] := id[src] (planted duplicate) */ static chacha_ctx G_ctx; static uint64_t G_N; static int G_shard_bits, G_threads; static inject_t *G_inj; static int G_ninj; /* Per shard, every kept id becomes ONE 8-byte entry: its 40-bit index plus the KEY_BITS prefix bits that follow the shard bits and the REGION_BITS region bits. Entries are written straight into the region their prefix selects, so an entry pins down shard_bits + REGION_BITS + KEY_BITS = 36+s bits of the id; equal-key pairs inside a region are candidates and every candidate is verified by regenerating both ids from their indices. Full duplicates always share the prefix, so there are no false negatives; regeneration removes the false positives. */ #define REGION_BITS 12 #define NREGIONS (1u << REGION_BITS) #define KEY_BITS 24 #define CHUNK 64u /* slots a thread claims from a region at a time */ typedef uint64_t entry_t; /* [KEY_BITS key][40-bit index] */ #define IDX_MASK ((1ULL << 40) - 1) #define ENTRY_KEY(e) ((uint32_t)((e) >> 40)) #define ENTRY_IDX(e) ((e) & IDX_MASK) #define SENTINEL (~0ULL) /* unused slot (index 2^40-1 is never real) */ static inline uint64_t load_be64(const uint8_t *p) { uint64_t v = 0; for (int i = 0; i < 8; i++) v = (v << 8) | p[i]; return v; } static inline uint32_t region_of(uint64_t k0) { return (uint32_t)((k0 >> (64 - G_shard_bits - REGION_BITS)) & (NREGIONS - 1)); } static inline uint32_t key_of(uint64_t k0) { return (uint32_t)((k0 >> (64 - G_shard_bits - REGION_BITS - KEY_BITS)) & ((1u << KEY_BITS) - 1)); } static inline int prefix_bits(void) { return G_shard_bits + REGION_BITS + KEY_BITS; } /* id #idx of the run: keystream slice with ver/var applied, honouring planted duplicates. */ static void gen_id(uint64_t idx, uint8_t out[32]) { for (int k = 0; k < G_ninj; k++) if (G_inj[k].dst == idx) { idx = G_inj[k].src; break; } uint8_t blk[64]; chacha_block(&G_ctx, idx >> 1, blk); memcpy(out, blk + ((idx & 1) << 5), 32); uuid256_set_ver_var(out); } /* The arena: NREGIONS regions of `cap` entries each (cap % CHUNK == 0). Threads claim CHUNK-slot pieces of a region with one atomic add and then fill them privately. */ static entry_t *G_arr; static uint64_t G_cap; static _Atomic uint32_t *G_fill; /* per region: slots handed out so far */ typedef struct { uint32_t region; entry_t e; } ovf_t; /* entry whose region was full (6-sigma rare) */ typedef struct { int tid; uint64_t lo, hi; int shard; uint32_t *cur, *end; /* per region: this thread's current chunk [cur,end) */ ovf_t *ovf; size_t novf, ovfcap; uint64_t kept, bad_ver, roundtrip_fail, roundtrip_ok; } genjob_t; static inline void push_entry(genjob_t *j, uint32_t r, entry_t e) { if (j->cur[r] == j->end[r]) { if (j->end[r] != UINT32_MAX) { /* claim a new chunk in region r */ uint32_t pos = atomic_fetch_add_explicit(&G_fill[r], CHUNK, memory_order_relaxed); if (pos < G_cap) { j->cur[r] = pos; j->end[r] = pos + CHUNK; goto store; } j->cur[r] = j->end[r] = UINT32_MAX; /* region full for this thread from now on */ } if (j->novf == j->ovfcap) { j->ovfcap = j->ovfcap ? 2 * j->ovfcap : 64; j->ovf = realloc(j->ovf, j->ovfcap * sizeof(ovf_t)); if (!j->ovf) { fprintf(stderr, "out of memory\n"); exit(1); } } j->ovf[j->novf].region = r; j->ovf[j->novf].e = e; j->novf++; return; } store: G_arr[(uint64_t)r * G_cap + j->cur[r]++] = e; } static void *gen_worker(void *arg) { genjob_t *j = arg; uint8_t blk[256], tmp[32]; /* 4 ChaCha blocks = 8 consecutive ids */ const int shard_shift = 16 - G_shard_bits; /* shard = top bits of the first two (random) bytes */ j->cur = calloc(NREGIONS, sizeof(uint32_t)); j->end = calloc(NREGIONS, sizeof(uint32_t)); if (!j->cur || !j->end) { fprintf(stderr, "out of memory\n"); exit(1); } for (uint64_t idx = j->lo; idx < j->hi; idx++) { if ((idx & 7) == 0 || idx == j->lo) { /* ids [idx&~7, +8) = blocks 4*(idx>>3) .. +3 */ chacha_block4(&G_ctx, (idx >> 3) << 2, blk); for (int q = 0; q < 8; q++) uuid256_set_ver_var(blk + 32 * q); } const uint8_t *id = blk + ((idx & 7) << 5); if (G_ninj) { /* planted duplicate? */ for (int k = 0; k < G_ninj; k++) if (G_inj[k].dst == idx) { gen_id(idx, tmp); id = tmp; break; } } if (!uuid256_is_strict(id)) j->bad_ver++; if (j->shard == 0 && (idx & 0xFFFFF) == 0) { /* exercise text codec on a sample */ char txt[UUID256_TEXT_LEN + 1]; uint8_t back[32]; uuid256_to_canonical(id, txt); if (uuid256_parse(txt, back, true) == UUID256_OK && memcmp(back, id, 32) == 0) j->roundtrip_ok++; else j->roundtrip_fail++; } if ((((unsigned)id[0] << 8 | id[1]) >> shard_shift) == (unsigned)j->shard) { uint64_t k0 = load_be64(id); push_entry(j, region_of(k0), ((uint64_t)key_of(k0) << 40) | idx); j->kept++; } } for (uint32_t r = 0; r < NREGIONS; r++) /* mark the unused tail of each current chunk */ if (j->end[r] != UINT32_MAX) for (uint32_t i = j->cur[r]; i < j->end[r]; i++) G_arr[(uint64_t)r * G_cap + i] = SENTINEL; free(j->cur); free(j->end); return NULL; } typedef struct { uint64_t i, j; uint8_t id[32]; } dup_t; typedef struct { uint32_t r_lo, r_hi; const ovf_t *ovf; size_t novf; /* all overflow entries, sorted by region */ entry_t *t1, *t2; /* scratch, cap + novf entries each */ dup_t *dups; size_t ndups, dcap; uint64_t cand, prefix_only; } sortjob_t; static int ovf_cmp(const void *a, const void *b) { uint32_t ra = ((const ovf_t *)a)->region, rb = ((const ovf_t *)b)->region; return ra < rb ? -1 : ra > rb; } /* LSD radix sort of n entries by their 24-bit key (3 passes of 8 bits): src -> t1 -> t2 -> t1. */ static entry_t *radix_by_key(const entry_t *src, entry_t *t1, entry_t *t2, uint64_t n) { const entry_t *from = src; entry_t *to = t1; for (int shift = 40; shift < 64; shift += 8) { uint32_t cnt[256] = {0}; for (uint64_t i = 0; i < n; i++) cnt[(from[i] >> shift) & 0xFF]++; uint32_t sum = 0; for (int b = 0; b < 256; b++) { uint32_t c = cnt[b]; cnt[b] = sum; sum += c; } for (uint64_t i = 0; i < n; i++) to[cnt[(from[i] >> shift) & 0xFF]++] = from[i]; from = to; to = (to == t1) ? t2 : t1; } return (entry_t *)from; /* == t1 after three passes */ } /* One regenerated candidate: index + full id. */ typedef struct { uint64_t idx; uint8_t id[32]; } cand_t; static int cand_cmp(const void *a, const void *b) { const cand_t *x = a, *y = b; int c = memcmp(x->id, y->id, 32); if (c) return c; return x->idx < y->idx ? -1 : x->idx > y->idx; } /* Verify one run of r >= 2 entries that share a key: regenerate every id in the run, sort the run by full value and report each adjacent equal pair. Comparing only slot-adjacent entries would miss a real duplicate whenever a prefix-only collider happens to sit between the two copies, so the whole run is covered. Runs are tiny (1 + n/2^(36+s) on average), so the extra work is negligible. */ static void verify_run(sortjob_t *s, const entry_t *run, uint64_t r) { cand_t small[8], *c = small; if (r > 8) { c = malloc(r * sizeof(cand_t)); if (!c) { fprintf(stderr, "out of memory\n"); exit(1); } } for (uint64_t i = 0; i < r; i++) { c[i].idx = ENTRY_IDX(run[i]); gen_id(c[i].idx, c[i].id); } qsort(c, r, sizeof(cand_t), cand_cmp); s->cand += r - 1; for (uint64_t i = 1; i < r; i++) { if (memcmp(c[i - 1].id, c[i].id, 32) == 0) { if (s->ndups == s->dcap) { s->dcap = s->dcap ? 2 * s->dcap : 16; s->dups = realloc(s->dups, s->dcap * sizeof(dup_t)); if (!s->dups) { fprintf(stderr, "out of memory\n"); exit(1); } } dup_t *d = &s->dups[s->ndups++]; d->i = c[i - 1].idx; d->j = c[i].idx; memcpy(d->id, c[i].id, 32); /* sorted by (id, idx): i < j */ } else s->prefix_only++; } if (c != small) free(c); } static void *sort_worker(void *arg) { sortjob_t *s = arg; size_t o = 0; /* cursor into the region-sorted overflow list */ for (uint32_t r = s->r_lo; r < s->r_hi; r++) { uint32_t used = atomic_load_explicit(&G_fill[r], memory_order_relaxed); if (used > G_cap) used = (uint32_t)G_cap; const entry_t *src = G_arr + (uint64_t)r * G_cap; uint64_t n = used; while (o < s->novf && s->ovf[o].region < r) o++; if (o < s->novf && s->ovf[o].region == r) { /* fold this region's overflow entries in */ memcpy(s->t2, src, n * sizeof(entry_t)); while (o < s->novf && s->ovf[o].region == r) s->t2[n++] = s->ovf[o++].e; src = s->t2; } if (n < 2) continue; entry_t *a = radix_by_key(src, s->t1, s->t2, n); uint64_t m = 0; /* drop sentinels (unused slots) */ for (uint64_t i = 0; i < n; i++) if (ENTRY_IDX(a[i]) != IDX_MASK) a[m++] = a[i]; for (uint64_t i = 0; i < m; ) { /* walk the runs of equal keys */ uint64_t j = i + 1; while (j < m && ENTRY_KEY(a[j]) == ENTRY_KEY(a[i])) j++; if (j - i >= 2) verify_run(s, a + i, j - i); i = j; } } return NULL; } static int dup_cmp(const void *a, const void *b) { const dup_t *x = a, *y = b; if (x->i != y->i) return x->i < y->i ? -1 : 1; return x->j < y->j ? -1 : x->j > y->j; } /* ========================================================================== */ /* Helpers */ /* ========================================================================== */ static double now_s(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec + t.tv_nsec / 1e9; } static const char *commas(uint64_t v) { static char bufs[8][32]; static int r = 0; char *b = bufs[r++ & 7]; char tmp[32]; int n = snprintf(tmp, sizeof tmp, "%llu", (unsigned long long)v); int o = 0; for (int i = 0; i < n; i++) { if (i && (n - i) % 3 == 0) b[o++] = ','; b[o++] = tmp[i]; } b[o] = 0; return b; } static void hexdump(const uint8_t *p, size_t n, char *out) { for (size_t i = 0; i < n; i++) { out[2*i] = HEX[p[i] >> 4]; out[2*i+1] = HEX[p[i] & 15]; } out[2*n] = 0; } static bool parse_hex(const char *s, uint8_t *out, size_t n) { if (strlen(s) != 2 * n) return false; for (size_t i = 0; i < n; i++) { int a = hexval(s[2*i]), b = hexval(s[2*i+1]); if (a < 0 || b < 0) return false; out[i] = (uint8_t)(a << 4 | b); } return true; } /* ---- self-tests: spec §11 vectors, RFC 8439 block vector, 4-lane block, codec ---------- */ static int self_test(void) { int fails = 0; struct { const char *in, *out; } vec[2] = { { "000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f", "0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f" }, { "fffefdfcfbfaf9f8f7f6f5f4f3f2f1f0efeeedecebeae9e8e7e6e5e4e3e2e1e0", "fffefdfcfbfaf9f8-f7f6f5f4-43f2f1f0-afeeedec-ebeae9e8e7e6e5e4e3e2e1e0" }, }; for (int i = 0; i < 2; i++) { uint8_t b[32], back[32]; char txt[69]; parse_hex(vec[i].in, b, 32); uuid256_set_ver_var(b); uuid256_to_canonical(b, txt); bool ok = strcmp(txt, vec[i].out) == 0 && uuid256_parse(txt, back, true) == UUID256_OK && memcmp(back, b, 32) == 0 && uuid256_parse(vec[i].in, back, false) == UUID256_OK /* compact, lenient (raw has wrong ver) */ && uuid256_parse(vec[i].in, back, true) == UUID256_ERR_VERSION; /* compact, strict rejects raw ver */ printf(" spec §11 vector %d: %s %s\n", i + 1, ok ? "PASS" : "FAIL", txt); fails += !ok; } { /* uppercase accepted, garbage rejected, nil fails strict but passes lenient */ uint8_t b[32]; const char *up = "0001020304050607-08090A0B-4C0D0E0F-90111213-1415161718191A1B1C1D1E1F"; const char *nil = "0000000000000000-00000000-00000000-00000000-000000000000000000000000"; bool ok = uuid256_parse(up, b, true) == UUID256_OK && uuid256_parse("0001020304050607_08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f", b, true) == UUID256_ERR_HYPHEN && uuid256_parse("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1", b, true) == UUID256_ERR_LENGTH && uuid256_parse("0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1g", b, true) == UUID256_ERR_CHAR && uuid256_parse(nil, b, true) == UUID256_ERR_VERSION && uuid256_parse(nil, b, false) == UUID256_OK; printf(" parser rules (§3.2/§6): %s\n", ok ? "PASS" : "FAIL"); fails += !ok; } { /* RFC 8439 §2.3.2 block-function test vector */ uint8_t key[32], nonce[8] = {0}, out[64]; for (int i = 0; i < 32; i++) key[i] = (uint8_t)i; chacha_ctx c; chacha_init(&c, key, nonce, 20); /* RFC layout: word12 = counter(1), words13..15 = nonce 00:00:00:09 | 00:00:00:4a | 00:00:00:00. Our DRBG uses a 64-bit counter in words 12..13, so word13 (0x09000000) is passed via counter-high. */ c.st[14] = 0x4a000000; c.st[15] = 0; chacha_block(&c, 1ULL | ((uint64_t)0x09000000 << 32), out); static const uint8_t exp[16] = {0x10,0xf1,0xe7,0xe4,0xd1,0x3b,0x59,0x15,0x50,0x0f,0xdd,0x1f,0xa3,0x20,0x71,0xc4}; bool ok = memcmp(out, exp, 16) == 0; printf(" RFC 8439 ChaCha20 vector: %s\n", ok ? "PASS" : "FAIL"); fails += !ok; } { /* 4-lane block function must equal four scalar blocks, for every supported round count */ uint8_t key[32], nonce[8], out4[256], out1[64]; bool ok = true; for (int i = 0; i < 32; i++) key[i] = (uint8_t)(i * 7 + 3); for (int i = 0; i < 8; i++) nonce[i] = (uint8_t)(0xA0 + i); static const int rounds[3] = { 8, 12, 20 }; for (int ri = 0; ri < 3; ri++) { chacha_ctx c; chacha_init(&c, key, nonce, rounds[ri]); static const uint64_t ctrs[3] = { 0, 0xFFFFFFFEULL, 0x123456789ABULL }; /* incl. a 32-bit carry */ for (int ci = 0; ci < 3; ci++) { chacha_block4(&c, ctrs[ci], out4); for (int l = 0; l < 4; l++) { chacha_block(&c, ctrs[ci] + (uint64_t)l, out1); ok = ok && memcmp(out1, out4 + 64 * l, 64) == 0; } } } printf(" ChaCha 4-lane == scalar: %s\n", ok ? "PASS" : "FAIL"); fails += !ok; } { /* live ids straight from the OS CSPRNG (§5.1) */ for (int i = 0; i < 3; i++) { uint8_t b[32]; char t[69]; uuid256_generate(b); uuid256_to_canonical(b, t); bool ok = uuid256_is_strict(b); printf(" uuid256_generate(): %s %s\n", t, ok ? "ok" : "BAD"); fails += !ok; } } return fails; } /* Checked decimal parsing for command-line arguments (atoi/strtoull silently accept junk and overflow). */ static bool parse_u64(const char *s, uint64_t *out) { if (!s || !*s || *s == '-' || *s == '+') return false; char *end; errno = 0; unsigned long long v = strtoull(s, &end, 10); if (errno || *end) return false; *out = v; return true; } static bool parse_int(const char *s, int lo, int hi, int *out) { uint64_t v; if (!parse_u64(s, &v) || v < (uint64_t)lo || v > (uint64_t)hi) return false; *out = (int)v; return true; } #define MAX_THREADS 4096 static void usage(const char *p) { fprintf(stderr, "usage: %s [-n count] [-s shards] [-r first:count] [-t threads] [-i planted_dups] [-k seedhex80] [-R rounds] [-q]\n" " %s -g [count] just print one (or count) new ids\n" " %s -p|-P parse (strict|lenient): prints 'ok ' or 'error '\n" " -n ids to generate (default 1000000000, max 2^40-1)\n" " -s shards, power of two 1..65536 (default 4; peak RAM ~ 8.3 B * n / s)\n" " -r only process shards [first, first+count) — partial coverage (default: all)\n" " -t threads, 1..4096 (default: online CPUs)\n" " -i plant K duplicates to prove detection works (default 0, K <= n/2)\n" " -k reuse a printed seed (32-byte key + 8-byte nonce as 80 hex chars)\n" " -R ChaCha rounds for the DRBG: 20 (default, = the OS RNGs' construction), 12 or 8 (faster)\n" " -q skip self-tests\n", p, p, p); exit(2); } int main(int argc, char **argv) { G_N = 1000000000ULL; int shards = 4; long ncpu = sysconf(_SC_NPROCESSORS_ONLN); G_threads = ncpu < 1 ? 1 : ncpu > MAX_THREADS ? MAX_THREADS : (int)ncpu; int planted = 0; bool quiet = false; uint8_t seed[40]; bool have_seed = false; int rounds = 20; int r_first = 0, r_count = -1; if (argc >= 2 && strcmp(argv[1], "-g") == 0) { /* just print ids: -g [count] */ long count = 1; if (argc >= 3) { uint64_t v; if (parse_u64(argv[2], &v)) count = (long)v; } /* -g N: exactly N (0 allowed); junk → 1 */ for (long i = 0; i < count; i++) { uint8_t b[32]; char t[69]; uuid256_generate(b); uuid256_to_canonical(b, t); puts(t); } return 0; } if (argc >= 3 && (strcmp(argv[1], "-p") == 0 || strcmp(argv[1], "-P") == 0)) { /* parse mode: -p strict, -P lenient */ uint8_t pb[32]; char hx[65]; int rc = uuid256_parse(argv[2], pb, argv[1][1] == 'p'); if (rc == UUID256_OK) { for (int i = 0; i < 32; i++) sprintf(hx + 2 * i, "%02x", pb[i]); printf("ok %s\n", hx); return 0; } static const char *kinds[] = { "ok", "length", "hyphen", "char", "version" }; printf("error %s\n", kinds[rc]); return 1; } int opt; while ((opt = getopt(argc, argv, "n:s:r:t:i:k:R:qh")) != -1) { switch (opt) { case 'n': if (!parse_u64(optarg, &G_N)) usage(argv[0]); break; case 's': if (!parse_int(optarg, 1, 65536, &shards)) usage(argv[0]); break; case 'r': { char *colon = strchr(optarg, ':'); if (!colon) usage(argv[0]); *colon = '\0'; if (!parse_int(optarg, 0, 65536, &r_first) || !parse_int(colon + 1, 1, 65536, &r_count)) usage(argv[0]); break; } case 't': if (!parse_int(optarg, 1, MAX_THREADS, &G_threads)) usage(argv[0]); break; case 'i': if (!parse_int(optarg, 0, INT_MAX, &planted)) usage(argv[0]); break; case 'k': if (!parse_hex(optarg, seed, 40)) usage(argv[0]); have_seed = true; break; case 'R': if (!parse_int(optarg, 8, 20, &rounds)) usage(argv[0]); break; case 'q': quiet = true; break; default: usage(argv[0]); } } if (G_N < 2 || G_N > IDX_MASK || shards < 1 || shards > 65536 || (shards & (shards - 1)) || G_threads < 1 || planted < 0) usage(argv[0]); if (rounds != 8 && rounds != 12 && rounds != 20) usage(argv[0]); if ((uint64_t)planted > G_N / 2) { fprintf(stderr, "-i %d: at most n/2 duplicates can be planted\n", planted); return 2; } if (r_count < 0) { r_first = 0; r_count = shards; } if (r_first < 0 || r_count < 1 || r_first + r_count > shards) usage(argv[0]); G_shard_bits = 0; while ((1 << G_shard_bits) < shards) G_shard_bits++; printf("UUID256 reference implementation — README.md (256-bit random, 16-8-8-8-24 text)\n\n"); if (!quiet) { printf("Self-tests:\n"); int f = self_test(); if (f) { printf(" %d self-test(s) FAILED — aborting\n", f); return 1; } printf("\n"); } if (!have_seed) os_random(seed, sizeof seed); chacha_init(&G_ctx, seed, seed + 32, rounds); char seedhex[81]; hexdump(seed, 40, seedhex); /* planted duplicates: id[dst] := id[src] — sources evenly spaced over the lower half, each mirrored into the upper half, so all 2K positions are distinct and no source is itself a target (K <= N/2). */ G_ninj = planted; G_inj = calloc((size_t)planted + 1, sizeof(inject_t)); if (!G_inj) { fprintf(stderr, "out of memory\n"); return 1; } uint64_t step = planted ? (G_N / 2) / (uint64_t)planted : 0; for (int k = 0; k < planted; k++) { G_inj[k].src = step * (uint64_t)k; G_inj[k].dst = G_N - 1 - G_inj[k].src; } /* region capacity: expected fill + 6 sigma + one partial chunk per thread, rounded up to whole chunks */ double expect = (double)G_N / shards / NREGIONS; uint64_t cap = (uint64_t)(expect + 6.0 * sqrt(expect) + 6.0) + (uint64_t)G_threads * CHUNK + CHUNK; cap = (cap + CHUNK - 1) / CHUNK * CHUNK; if (cap > (uint64_t)UINT32_MAX - CHUNK) { fprintf(stderr, "region capacity %llu exceeds the 32-bit slot counters; use more shards\n", (unsigned long long)cap); return 1; } G_cap = cap; double mem_gb = (double)NREGIONS * cap * sizeof(entry_t) / 1e9; printf("Run: n=%s ids, shards=%d%s, threads=%d, planted duplicates=%d, ChaCha%d DRBG, arena %s regions x %s entries x 8 B = %.1f GB\n", commas(G_N), shards, r_count == shards ? "" : " (PARTIAL: subset of shards)", G_threads, planted, rounds, commas(NREGIONS), commas(cap), mem_gb); if (r_count != shards) printf("Coverage: shards %d..%d of %d → a duplicate pair is detected with probability %d/%d = %.4f%%\n", r_first, r_first + r_count - 1, shards, r_count, shards, 100.0 * r_count / shards); printf("DRBG seed (ChaCha%d key||nonce, replay with -k%s): %s\n\n", rounds, rounds == 20 ? "" : " and the same -R", seedhex); for (int k = 0; k < planted; k++) printf(" planted: id[%s] := id[%s]\n", commas(G_inj[k].dst), commas(G_inj[k].src)); if (planted) printf("\n"); G_arr = malloc((size_t)NREGIONS * cap * sizeof(entry_t)); G_fill = calloc(NREGIONS, sizeof(_Atomic uint32_t)); genjob_t *jobs = calloc((size_t)G_threads, sizeof(genjob_t)); sortjob_t *so = calloc((size_t)G_threads, sizeof(sortjob_t)); pthread_t *th = calloc((size_t)G_threads, sizeof(pthread_t)); if (!G_arr || !G_fill || !jobs || !so || !th) { fprintf(stderr, "out of memory (arena %.1f GB)\n", mem_gb); return 1; } double t_start = now_s(); uint64_t total_kept = 0, total_bad = 0, rt_ok = 0, rt_fail = 0, prefix_only = 0, dups = 0, total_ovf = 0; for (int shard = r_first; shard < r_first + r_count; shard++) { double t0 = now_s(); /* --- pass A: generate all N ids, write this shard's entries straight into their regions --- */ for (uint32_t r = 0; r < NREGIONS; r++) atomic_store_explicit(&G_fill[r], 0, memory_order_relaxed); for (int t = 0; t < G_threads; t++) { jobs[t] = (genjob_t){0}; jobs[t].tid = t; jobs[t].shard = shard; jobs[t].lo = G_N * (uint64_t)t / G_threads; jobs[t].hi = G_N * (uint64_t)(t + 1) / G_threads; if (pthread_create(&th[t], NULL, gen_worker, &jobs[t])) { perror("pthread_create"); return 1; } } uint64_t kept = 0; size_t novf = 0; for (int t = 0; t < G_threads; t++) { pthread_join(th[t], NULL); kept += jobs[t].kept; total_bad += jobs[t].bad_ver; rt_ok += jobs[t].roundtrip_ok; rt_fail += jobs[t].roundtrip_fail; novf += jobs[t].novf; } ovf_t *ovf = NULL; if (novf) { /* gather + sort the (rare) overflow entries by region */ ovf = malloc(novf * sizeof(ovf_t)); size_t o = 0; if (!ovf) { fprintf(stderr, "out of memory\n"); return 1; } for (int t = 0; t < G_threads; t++) { memcpy(ovf + o, jobs[t].ovf, jobs[t].novf * sizeof(ovf_t)); o += jobs[t].novf; } qsort(ovf, novf, sizeof(ovf_t), ovf_cmp); } for (int t = 0; t < G_threads; t++) free(jobs[t].ovf); double t1 = now_s(); /* --- pass B: per region, radix-sort by key and verify equal-key pairs by regeneration --- */ for (int t = 0; t < G_threads; t++) { so[t] = (sortjob_t){0}; so[t].r_lo = (uint32_t)((uint64_t)NREGIONS * t / G_threads); so[t].r_hi = (uint32_t)((uint64_t)NREGIONS * (t + 1) / G_threads); so[t].ovf = ovf; so[t].novf = novf; so[t].t1 = malloc((cap + novf) * sizeof(entry_t)); so[t].t2 = malloc((cap + novf) * sizeof(entry_t)); if (!so[t].t1 || !so[t].t2) { fprintf(stderr, "out of memory\n"); return 1; } if (pthread_create(&th[t], NULL, sort_worker, &so[t])) { perror("pthread_create"); return 1; } } uint64_t ncand = 0, shard_dups = 0; size_t nd = 0; for (int t = 0; t < G_threads; t++) { pthread_join(th[t], NULL); ncand += so[t].cand; prefix_only += so[t].prefix_only; nd += so[t].ndups; free(so[t].t1); free(so[t].t2); } if (nd) { /* print duplicates in (i, j) order, whatever the thread timing */ dup_t *all = malloc(nd * sizeof(dup_t)); size_t o = 0; if (!all) { fprintf(stderr, "out of memory\n"); return 1; } for (int t = 0; t < G_threads; t++) { memcpy(all + o, so[t].dups, so[t].ndups * sizeof(dup_t)); o += so[t].ndups; } qsort(all, nd, sizeof(dup_t), dup_cmp); for (size_t d = 0; d < nd; d++) { char ta[69]; uuid256_to_canonical(all[d].id, ta); printf(" DUPLICATE id[%s] == id[%s] %s\n", commas(all[d].i), commas(all[d].j), ta); } free(all); shard_dups = nd; } for (int t = 0; t < G_threads; t++) free(so[t].dups); free(ovf); double t2 = now_s(); dups += shard_dups; total_kept += kept; total_ovf += novf; printf("shard %2d/%d: gen %6.1fs sort+verify %5.1fs kept %s candidates %s duplicates %llu%s\n", shard + 1, shards, t1 - t0, t2 - t1, commas(kept), commas(ncand), (unsigned long long)shard_dups, novf ? " (overflow entries folded in)" : ""); fflush(stdout); } double elapsed = now_s() - t_start; free(G_arr); free((void *)G_fill); free(jobs); free(so); free(th); printf("\n==== RESULT ====\n"); printf("ids generated (per pass): %s (%d passes, %s id-generations total)\n", commas(G_N), r_count, commas(G_N * (uint64_t)r_count)); if (r_count == shards) printf("ids examined across all shards: %s %s\n", commas(total_kept), total_kept == G_N ? "(every id covered exactly once)" : "(MISMATCH!)"); else printf("ids examined (partial): %s of %s (%.4f%% of shard space; exact within those shards)\n", commas(total_kept), commas(G_N), 100.0 * r_count / shards); printf("version/variant violations: %s\n", commas(total_bad)); printf("text round-trips (sampled): %s ok, %s failed\n", commas(rt_ok), commas(rt_fail)); printf("%d-bit-prefix-only collisions: %s (expected ≈ n²/(2^%d·S) = %s; all resolved by regenerating both ids)\n", prefix_bits(), commas(prefix_only), REGION_BITS + KEY_BITS + 1, commas((uint64_t)((double)G_N * (double)G_N / pow(2.0, REGION_BITS + KEY_BITS + 1) / shards * r_count / shards))); if (total_ovf) printf("region-overflow entries: %s (kept in a side list, still checked)\n", commas(total_ovf)); printf("FULL 256-bit DUPLICATES: %s\n", commas(dups)); if (planted) printf(" (planted: %d — %s)\n", planted, dups == (uint64_t)planted ? "all detected" : "COUNT MISMATCH"); if (!dups) printf(" → no duplicates among %s ids%s\n", commas(G_N), r_count == shards ? "" : " (within the examined shards)"); /* expected collision probability from spec §5.3: n^2 / 2^251 */ double log2p = 2 * log2((double)G_N) - 251.0; printf("expected P(any collision) §5.3: n²/2²⁵¹ ≈ 2^%.1f ≈ %.1e\n", log2p, pow(2.0, log2p)); printf("elapsed: %.1f s (%.1f M ids/s effective, %.1f M ids/s raw generation)\n", elapsed, G_N / elapsed / 1e6, G_N * (double)r_count / elapsed / 1e6); free(G_inj); return (r_count == shards && dups != (uint64_t)planted) ? 1 : 0; }