#!/usr/bin/env bash # uuid256.sh — reference implementation of README.md (UUID256, random layout) in Bash 3.2+ / POSIX tools. # # ./uuid256.sh # self-tests + exact duplicate check over 1,000,000 ids # ./uuid256.sh -n 200000 -i 3 # 2e5 ids with 3 planted duplicates (proves detection) # ./uuid256.sh -g [count] # just print one (or count) new ids, nothing else # # source uuid256.sh # library use (functions only, nothing runs): # id=$(uuid256_generate) # §5.1: 32 bytes from /dev/urandom via od, ver=4 / var=10 applied, canonical text # hex=$(uuid256_parse "$id") # §6: strict → prints the 64-hex compact form, exit 0; exit 1..4 on error # hex=$(uuid256_parse "$id" lenient) # §6: lenient (no ver/var check) # uuid256_is_strict "$hex" # exit 0 iff ver == 4 && var == 10 # # Randomness (§5.2): /dev/urandom — the OS CSPRNG. Only od/tr are used per id; the bulk check streams # /dev/urandom through xxd | awk (§4 + hyphens) | sort | uniq -d, i.e. an exact duplicate check with the # ordinary Unix toolbox. Works with macOS's stock bash 3.2 (no associative arrays, no ${x,,}). UUID256_TEXT_LEN=68 UUID256_VERSION=4 UUID256_STRICT_RE='^[0-9a-f]{16}-[0-9a-f]{8}-4[0-9a-f]{7}-[89ab][0-9a-f]{7}-[0-9a-f]{24}$' UUID256_HEX64_RE='^[0-9a-f]{64}$' UUID256_NIL='0000000000000000-00000000-00000000-00000000-000000000000000000000000' # §8 # ---- API ------------------------------------------------------------------ # 64 lowercase hex digits of OS randomness (§5.2). Fails closed: if the CSPRNG cannot be read the # function prints nothing and returns 1, so no caller can ever emit a short or non-random "id". uuid256_random_hex64() { local h h=$(od -An -tx1 -N32 -v /dev/urandom 2>/dev/null | LC_ALL=C tr -d ' \n') case $h in ????????????????????????????????????????????????????????????????) printf '%s\n' "$h";; *) echo 'uuid256: cannot read 32 bytes from /dev/urandom' >&2; return 1;; esac } # §4 on a 64-hex string: digit 24 → '4'; digit 32 → keep its low 2 bits, set the top two to 10 (→ 8..b). uuid256_set_ver_var() { local h=$1 v [[ $h =~ $UUID256_HEX64_RE ]] || { echo "uuid256: expected 64 hex digits" >&2; return 1; } v=$(( (16#${h:32:1} & 3) | 8 )) printf '%s%s%s%x%s\n' "${h:0:24}" "$UUID256_VERSION" "${h:25:7}" "$v" "${h:33:31}" } # §3.1 — 64-hex → canonical 16-8-8-8-24. uuid256_to_canonical() { local h=$1 [[ $h =~ $UUID256_HEX64_RE ]] || { echo "uuid256: expected 64 hex digits" >&2; return 1; } printf '%s-%s-%s-%s-%s\n' "${h:0:16}" "${h:16:8}" "${h:24:8}" "${h:32:8}" "${h:40:24}" } # §5.1 — a new id in canonical text (exit 1, no output, if the OS random source is unavailable). uuid256_generate() { local h h=$(uuid256_random_hex64) || return 1 uuid256_to_canonical "$(uuid256_set_ver_var "$h")" } # §6 — ver == 4 && var == 10 on a 64-hex string. uuid256_is_strict() { local h=$1 [ "${h:24:1}" = "$UUID256_VERSION" ] && case "${h:32:1}" in 8|9|a|b) return 0;; esac return 1 } # §6 — parse canonical (68) or compact (64), any case. Prints 64-hex compact form. # exit: 0 ok · 1 length · 2 hyphen · 3 char · 4 version/variant (only when strict, the default) uuid256_parse() { local s h local LC_ALL=C # byte semantics for ${#s}, ${s:i:1} and the [0-9a-f] classes, whatever the caller's locale s=$(printf '%sx' "$1" | tr 'A-Z' 'a-z'); s=${s%x} # the 'x' keeps $(...) from eating trailing newlines: §6 trims nothing if [ ${#s} -eq $UUID256_TEXT_LEN ]; then [ "${s:16:1}" = '-' ] && [ "${s:25:1}" = '-' ] && [ "${s:34:1}" = '-' ] && [ "${s:43:1}" = '-' ] || return 2 h="${s:0:16}${s:17:8}${s:26:8}${s:35:8}${s:44:24}" elif [ ${#s} -eq 64 ]; then h=$s else return 1 fi [[ $h =~ $UUID256_HEX64_RE ]] || return 3 if [ "${2:-strict}" = strict ]; then uuid256_is_strict "$h" || return 4; fi printf '%s\n' "$h" } # ---- self-tests ----------------------------------------------------------- uuid256_self_test() { local fails=0 i raw expected h txt ok up nil_txt local vec_in=( 000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f fffefdfcfbfaf9f8f7f6f5f4f3f2f1f0efeeedecebeae9e8e7e6e5e4e3e2e1e0 ) local vec_out=( 0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f fffefdfcfbfaf9f8-f7f6f5f4-43f2f1f0-afeeedec-ebeae9e8e7e6e5e4e3e2e1e0 ) for i in 0 1; do raw=${vec_in[$i]}; expected=${vec_out[$i]} h=$(uuid256_set_ver_var "$raw"); txt=$(uuid256_to_canonical "$h") up=$(printf '%s' "$txt" | tr 'a-z' 'A-Z') ok=1 [ "$txt" = "$expected" ] || ok=0 [ "$(uuid256_parse "$txt")" = "$h" ] || ok=0 [ "$(uuid256_parse "$up")" = "$h" ] || ok=0 [ "$(uuid256_parse "$raw" lenient)" = "$raw" ] || ok=0 # raw compact: lenient ok uuid256_parse "$raw" >/dev/null 2>&1; [ $? -eq 4 ] || ok=0 # strict rejects (ver != 4) [[ $txt =~ $UUID256_STRICT_RE ]] || ok=0 [ $ok -eq 1 ] && printf ' spec §11 vector %d: PASS %s\n' $((i+1)) "$txt" || { printf ' spec §11 vector %d: FAIL %s\n' $((i+1)) "$txt"; fails=$((fails+1)); } done ok=1 uuid256_parse '0001020304050607_08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1f' >/dev/null; [ $? -eq 2 ] || ok=0 uuid256_parse '0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1' >/dev/null; [ $? -eq 1 ] || ok=0 uuid256_parse '0001020304050607-08090a0b-4c0d0e0f-90111213-1415161718191a1b1c1d1e1g' >/dev/null; [ $? -eq 3 ] || ok=0 uuid256_parse "$UUID256_NIL" >/dev/null; [ $? -eq 4 ] || ok=0 [ "$(uuid256_parse "$UUID256_NIL" lenient)" = "$(printf '%064d' 0)" ] || ok=0 [ $ok -eq 1 ] && echo ' parser rules (§3.2/§6): PASS' || { echo ' parser rules (§3.2/§6): FAIL'; fails=$((fails+1)); } for i in 1 2 3; do txt=$(uuid256_generate) if [[ $txt =~ $UUID256_STRICT_RE ]] && [ "$(uuid256_to_canonical "$(uuid256_parse "$txt")")" = "$txt" ]; then printf ' uuid256_generate: %s ok\n' "$txt" else printf ' uuid256_generate: %s BAD\n' "$txt"; fails=$((fails+1)) fi done return $fails } # ---- bulk exact duplicate check (Unix pipeline) --------------------------- uuid256_bulk() { local n=$1 planted=$2 t0 t1 t2 out bad dups ndups i printf 'Bulk exact duplicate check: n=%s ids, planted duplicates=%s\n' "$n" "$planted" out=$(mktemp "${TMPDIR:-/tmp}/uuid256.XXXXXX") || return 1 # (mktemp -t PREFIX is BSD-only) # 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). local step=0; [ "$planted" -gt 0 ] && step=$(( (n / 2) / planted )) i=0; while [ "$i" -lt "$planted" ]; do local src=$(( step * i )) dst=$(( n - 1 - step * i )) printf ' planted: id[%s] := id[%s]\n' "$dst" "$src"; i=$((i+1)) done t0=$(date +%s) # /dev/urandom → 64 hex per line → awk: §4 (digit 25 := '4', digit 33 := (low 2 bits)|8), hyphens, planted dups head -c $((n * 32)) /dev/urandom | xxd -p -c 32 | LC_ALL=C awk -v N="$n" -v K="$planted" ' BEGIN { step = K > 0 ? int(int(N / 2) / K) : 0 for (k = 0; k < K; k++) { src = step * k; dst = N - 1 - src; want[src] = 1; plant[dst] = src } } { c = substr($0, 33, 1); v = index("0123456789abcdef", c) - 1 h = substr($0, 1, 24) "4" substr($0, 26, 7) substr("89ab", (v % 4) + 1, 1) substr($0, 34) line = substr(h,1,16) "-" substr(h,17,8) "-" substr(h,25,8) "-" substr(h,33,8) "-" substr(h,41,24) i = NR - 1 if (i in want) keep[i] = line if (i in plant) line = keep[plant[i]] print line }' > "$out" t1=$(date +%s) bad=$(LC_ALL=C grep -c -v -E "$UUID256_STRICT_RE" "$out") dups=$(LC_ALL=C sort "$out" | LC_ALL=C uniq -d) ndups=$(printf '%s' "$dups" | grep -c .) t2=$(date +%s) [ -n "$dups" ] && printf '%s\n' "$dups" | while read -r i; do printf ' DUPLICATE id[%s] %s\n' "$(LC_ALL=C grep -n -F -x "$i" "$out" | cut -d: -f1 | awk '{printf "%s%d", (NR>1?"] == id[":""), $1-1}')" "$i" done echo echo '==== RESULT ====' printf 'ids generated: %s (urandom | xxd | awk in %ss; sort | uniq -d in %ss)\n' "$n" $((t1 - t0)) $((t2 - t1)) printf 'version/variant violations: %s\n' "$bad" printf 'lines total / distinct: %s / %s\n' "$(wc -l < "$out" | tr -d ' ')" "$(LC_ALL=C sort -u "$out" | wc -l | tr -d ' ')" printf 'FULL 256-bit DUPLICATES: %s' "$ndups" [ "$planted" -gt 0 ] && { [ "$ndups" -eq "$planted" ] && printf ' (planted: %s — all detected)' "$planted" || printf ' (planted: %s — COUNT MISMATCH)' "$planted"; } echo [ "$ndups" -eq 0 ] && printf ' → no duplicates among %s ids\n' "$n" rm -f "$out" [ "$ndups" -eq "$planted" ] } # ---- CLI ------------------------------------------------------------------ uuid256_main() { local n=1000000 planted=0 count if [ $# -ge 2 ] && { [ "$1" = -p ] || [ "$1" = -P ]; }; then # parse mode: -p strict, -P lenient local hex rc mode=strict; [ "$1" = -P ] && mode=lenient hex=$(uuid256_parse "$2" $mode); rc=$? case $rc in 0) echo "ok $hex"; return 0;; 1) echo "error length";; 2) echo "error hyphen";; 3) echo "error char";; 4) echo "error version";; esac return 1 fi while [ $# -gt 0 ]; do case $1 in -g) count=1; case ${2:-} in ''|*[!0-9]*) ;; *) count=$2; shift;; esac while [ "$count" -gt 0 ]; do uuid256_generate || return 1; count=$((count-1)); done return 0;; -n) n=$2; shift;; -i) planted=$2; shift;; *) echo 'usage: ./uuid256.sh [-g [count]] [-n count] [-i planted_dups]'; return 2;; esac shift done case $n in ''|*[!0-9]*) echo '-n must be a number'; return 2;; esac case $planted in ''|*[!0-9]*) echo '-i must be a number'; return 2;; esac if [ "$n" -lt 2 ] || [ "$planted" -gt $((n / 2)) ]; then echo '-n must be >= 2 and -i at most n/2'; return 2; fi echo 'UUID256 reference implementation (Bash) — README.md (256-bit random, 16-8-8-8-24 text)' echo echo 'Self-tests:' uuid256_self_test || { echo ' self-test FAILED — aborting'; return 1; } echo uuid256_bulk "$n" "$planted" } # Run only when executed, not when sourced. if [ "${BASH_SOURCE[0]}" = "$0" ]; then uuid256_main "$@" exit $? fi