workshopsoft/ludic
2
0
Fork 0
Code Issues Pull requests Projects Releases 26 Packages Wiki Activity Actions
ludic/selfhost/backend/stdlib/emit_hash.ludic
Orkuncakilkaya 647dfec334 feat(compiler): list literals, typed compound assignment, file:line diagnostics 
- `[a, b, c]` list literals (E_LIST → emit_list); static_type learns
  slice-element, `new T`, list, string and literal kinds
- `x op= y` lowers through the same path as `x = x op y` (emit_bin_vals):
  fixed `*=`/`/=` use the Q16.16 64-bit paths, string `+=` concatenates,
  int→long widens; unary `-` keeps a fixed operand's type (arith_ty)
- one `unescape()` table for "strings", 'chars' and `interpolation`;
  `'\''`, `'\\'`, `'\"'` no longer read as 0; unterminated char literals
  and unexpected characters are errors instead of silently skipped
- every diagnostic is `file:line: error: msg` (g_parse_file / g_err_file,
  Node.file + Node.line set by node()); tok_desc() in expectation errors;
  duplicate `function` names and unknown `phase` names are reported in
  source terms (phase_id used to default unknown phases to Overlay)
- interpolation holes skip braces inside string literals
- hand-IR preludes move from the user `@fn_` prefix to `@lp_` so a user
  `is_ws` / `str_eq` / `path_join` no longer collides at link time
- `@ClearColor(expr)` accepts any constant expression; `Os.pid()` added
  (docs page + inventory); `str_starts()` in support/str
- main.ludic: `else if` flag ladder, char literals, stale script comments
- examples/lang/operators.ludic covers all of the above; os.ludic covers
  Os.pid; docs pages for Os.pid and the Overlay phase; ten changesets
- reseeded: selfhost/ludicc.seed.ll is the new compiler's own fixpoint

Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com>
2026-09-05 01:12:16 +03:00

195 lines
8.1 KiB
Text
Raw Permalink Blame History

# emit_hash.ludic — the Hash.* namespace: fast, non-cryptographic hashing for
# map keys, content IDs, deterministic seeds and checksums. Everything is plain
# 32-bit integer IR with defined constants and byte order, so a given input
# hashes to the same value on every platform and every run — which is what makes
# it safe for procedural generation and lockstep networking. NOT for passwords
# or tamper-proofing; point users at the Crypto library for that.
#
# Hash.of(s) fast default string hash (currently FNV-1a 32)
# Hash.fnv1a(s) FNV-1a 32-bit, named explicitly
# Hash.crc32(s) CRC-32 (IEEE 802.3) checksum, for corruption detection
# Hash.mix(x) fmix32 avalanche of a single int (turn a counter into a seed)
# Hash.combine(...) fold several ints into one (e.g. world_seed, cx, cy)
function is_hash_ns(meth: pointer) -> bool {
if (meth == "of") or (meth == "fnv1a") or (meth == "crc32") { return true }
if (meth == "mix") or (meth == "combine") { return true }
if (meth == "of64") or (meth == "fnv1a_64") or (meth == "mix64") { return true }
return false
}
# fmix32 (MurmurHash3 finalizer) of a single i32 -> code of an i32. A strong
# avalanche: flips ~half the output bits for any one input bit. Used on its own
# (Hash.mix) and nowhere else — combine has its own mixing step.
function hash_mix_code(x: pointer) -> pointer {
let a = emit_bind(`lshr i32 {x}, 16`)
let b = emit_bind(`xor i32 {x}, {a}`)
let c = emit_bind(`mul i32 {b}, -2048144789`) # * 0x85ebca6b
let d = emit_bind(`lshr i32 {c}, 13`)
let e = emit_bind(`xor i32 {c}, {d}`)
let f = emit_bind(`mul i32 {e}, -1028477387`) # * 0xc2b2ae35
let g = emit_bind(`lshr i32 {f}, 16`)
return emit_bind(`xor i32 {f}, {g}`)
}
# fmix64 (MurmurHash3 64-bit finalizer) of a single i64 -> code of an i64. The
# 64-bit twin of hash_mix_code: shift by 33 and multiply by the two 64-bit
# constants. Backs Hash.mix64.
function hash_mix64_code(x: pointer) -> pointer {
let a = emit_bind(`lshr i64 {x}, 33`)
let b = emit_bind(`xor i64 {x}, {a}`)
let c = emit_bind(`mul i64 {b}, -49064778989728563`) # * 0xff51afd7ed558ccd
let d = emit_bind(`lshr i64 {c}, 33`)
let e = emit_bind(`xor i64 {c}, {d}`)
let f = emit_bind(`mul i64 {e}, -4265267296055464877`) # * 0xc4ceb9fe1a85ec53
let g = emit_bind(`lshr i64 {f}, 33`)
return emit_bind(`xor i64 {f}, {g}`)
}
function emit_hash_ns(meth: pointer, e: Node) -> Val {
if (meth == "of") or (meth == "fnv1a") { # FNV-1a 32-bit over the bytes
g_uses_hashrt = true
let s = emit_expr(e.kids[0])
return val(emit_bind(`call i32 @lp_hash_fnv1a(ptr {s.code})`), "int")
}
if (meth == "of64") or (meth == "fnv1a_64") { # FNV-1a 64-bit -> a `long`
g_uses_hashrt = true
let s = emit_expr(e.kids[0])
return val(emit_bind(`call i64 @lp_hash_fnv1a_64(ptr {s.code})`), "long")
}
if (meth == "mix64") { # fmix64 avalanche of one long
let x = emit_expr(e.kids[0])
return val(hash_mix64_code(to_long(x)), "long")
}
if (meth == "crc32") { # CRC-32 (IEEE) checksum
g_uses_hashrt = true
let s = emit_expr(e.kids[0])
return val(emit_bind(`call i32 @lp_hash_crc32(ptr {s.code})`), "int")
}
if (meth == "mix") { # fmix32 avalanche of one int
let x = emit_expr(e.kids[0])
return val(hash_mix_code(x.code), "int")
}
# combine(a, b, ...) -> fold the boost hash_combine step over every argument:
# seed = seed ^ (v + 0x9e3779b9 + (seed << 6) + (seed >> 2))
# order-sensitive and deterministic; seed starts at 0 so a single argument is
# still well-mixed with the golden-ratio constant.
var seed: pointer = "0"
var i = 0
while i < len(e.kids) {
let v = emit_expr(e.kids[i])
let g = emit_bind(`add i32 {v.code}, -1640531527`) # + 0x9e3779b9
let sl = emit_bind(`shl i32 {seed}, 6`)
let sr = emit_bind(`lshr i32 {seed}, 2`)
let t1 = emit_bind(`add i32 {g}, {sl}`)
let t2 = emit_bind(`add i32 {t1}, {sr}`)
seed = emit_bind(`xor i32 {seed}, {t2}`)
i += 1
}
return val(seed, "int")
}
# emit_hash_prelude — the byte-stream hashers, emitted once per program that uses
# Hash.of/fnv1a/crc32 (g_uses_hashrt). Both walk a null-terminated string a byte
# at a time with pure integer IR: FNV-1a with the standard 32-bit offset basis /
# prime, and a bitwise CRC-32 with the reflected poly 0xEDB88320. No libc, no
# allocation, bit-identical on every target.
function emit_hash_prelude() -> void {
emith("define i32 @lp_hash_fnv1a(ptr %s) {\n")
emith("entry:\n")
emith(" %hp = alloca i32\n")
emith(" store i32 -2128831035, ptr %hp\n") # 0x811c9dc5 offset basis
emith(" %ip = alloca i64\n")
emith(" store i64 0, ptr %ip\n")
emith(" br label %cond\n")
emith("cond:\n")
emith(" %i = load i64, ptr %ip\n")
emith(" %p = getelementptr i8, ptr %s, i64 %i\n")
emith(" %c = load i8, ptr %p\n")
emith(" %z = icmp eq i8 %c, 0\n")
emith(" br i1 %z, label %done, label %body\n")
emith("body:\n")
emith(" %ce = zext i8 %c to i32\n")
emith(" %h = load i32, ptr %hp\n")
emith(" %x = xor i32 %h, %ce\n")
emith(" %m = mul i32 %x, 16777619\n") # * 0x01000193 prime
emith(" store i32 %m, ptr %hp\n")
emith(" %i1 = add i64 %i, 1\n")
emith(" store i64 %i1, ptr %ip\n")
emith(" br label %cond\n")
emith("done:\n")
emith(" %hr = load i32, ptr %hp\n")
emith(" ret i32 %hr\n")
emith("}\n")
emith("define i64 @lp_hash_fnv1a_64(ptr %s) {\n") # 64-bit FNV-1a, same shape, i64
emith("entry:\n")
emith(" %hp = alloca i64\n")
emith(" store i64 -3750763034362895579, ptr %hp\n") # 0xcbf29ce484222325 offset basis
emith(" %ip = alloca i64\n")
emith(" store i64 0, ptr %ip\n")
emith(" br label %cond\n")
emith("cond:\n")
emith(" %i = load i64, ptr %ip\n")
emith(" %p = getelementptr i8, ptr %s, i64 %i\n")
emith(" %c = load i8, ptr %p\n")
emith(" %z = icmp eq i8 %c, 0\n")
emith(" br i1 %z, label %done, label %body\n")
emith("body:\n")
emith(" %ce = zext i8 %c to i64\n")
emith(" %h = load i64, ptr %hp\n")
emith(" %x = xor i64 %h, %ce\n")
emith(" %m = mul i64 %x, 1099511628211\n") # * 0x100000001b3 prime
emith(" store i64 %m, ptr %hp\n")
emith(" %i1 = add i64 %i, 1\n")
emith(" store i64 %i1, ptr %ip\n")
emith(" br label %cond\n")
emith("done:\n")
emith(" %hr = load i64, ptr %hp\n")
emith(" ret i64 %hr\n")
emith("}\n")
emith("define i32 @lp_hash_crc32(ptr %s) {\n")
emith("entry:\n")
emith(" %cp = alloca i32\n")
emith(" store i32 -1, ptr %cp\n") # init 0xFFFFFFFF
emith(" %ip = alloca i64\n")
emith(" store i64 0, ptr %ip\n")
emith(" %kp = alloca i32\n")
emith(" br label %cond\n")
emith("cond:\n")
emith(" %i = load i64, ptr %ip\n")
emith(" %p = getelementptr i8, ptr %s, i64 %i\n")
emith(" %ch = load i8, ptr %p\n")
emith(" %z = icmp eq i8 %ch, 0\n")
emith(" br i1 %z, label %done, label %body\n")
emith("body:\n")
emith(" %ce = zext i8 %ch to i32\n")
emith(" %c0 = load i32, ptr %cp\n")
emith(" %cx = xor i32 %c0, %ce\n") # fold byte into low 8 bits
emith(" store i32 %cx, ptr %cp\n")
emith(" store i32 0, ptr %kp\n")
emith(" br label %bit\n")
emith("bit:\n")
emith(" %k = load i32, ptr %kp\n")
emith(" %kd = icmp slt i32 %k, 8\n")
emith(" br i1 %kd, label %bitbody, label %bitdone\n")
emith("bitbody:\n")
emith(" %c1 = load i32, ptr %cp\n")
emith(" %lb = and i32 %c1, 1\n")
emith(" %ls = lshr i32 %c1, 1\n")
emith(" %ism = icmp eq i32 %lb, 1\n")
emith(" %px = select i1 %ism, i32 -306674912, i32 0\n") # ^ 0xEDB88320 when LSB set
emith(" %c2 = xor i32 %ls, %px\n")
emith(" store i32 %c2, ptr %cp\n")
emith(" %k1 = add i32 %k, 1\n")
emith(" store i32 %k1, ptr %kp\n")
emith(" br label %bit\n")
emith("bitdone:\n")
emith(" %i1 = add i64 %i, 1\n")
emith(" store i64 %i1, ptr %ip\n")
emith(" br label %cond\n")
emith("done:\n")
emith(" %cf = load i32, ptr %cp\n")
emith(" %r = xor i32 %cf, -1\n") # final XOR 0xFFFFFFFF
emith(" ret i32 %r\n")
emith("}\n")
}
Reference in a new issue View git blame Copy permalink