mugs in ocaml with murmur3 fork

10 files changed, 432 insertions, 47 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..6c66343
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,2 @@
+.claude
+ocaml-murmur3
diff --git a/flake.lock b/flake.lock
index 4ffb31a..bef6057 100644
--- a/flake.lock
+++ b/flake.lock
@@ -41,11 +41,11 @@
         ]
       },
       "locked": {
-        "lastModified": 1759644642,
-        "narHash": "sha256-q91igyyHUO/DCNt4eDheAQeXfghjZexBM3N2KToosgY=",
+        "lastModified": 1759729923,
+        "narHash": "sha256-8MEu/iYjwrExxXKsySbcKvoOql1BrVZ3GF775S9zrak=",
         "owner": "nix-ocaml",
         "repo": "nix-overlays",
-        "rev": "bb756b3eb7867eddb3b41c9a8fc0d03a4152fdba",
+        "rev": "9c4ca7e29bf7040becde04c0d1100b807baca1e3",
         "type": "github"
       },
       "original": {
diff --git a/flake.nix b/flake.nix
index a095bd4..2f9a2de 100644
--- a/flake.nix
+++ b/flake.nix
@@ -27,6 +27,18 @@
           })
         ];
       };
+
+      # https://github.com/ahrefs/ocaml-murmur3.git
+      murmur = pkgs.ocamlPackages.buildDunePackage {
+        pname = "murmur3";
+        version = "0.4";
+        src = pkgs.fetchFromGitHub {
+          owner = "polwex";
+          repo = "ocaml-murmur3";
+          rev = "be8ef049b515ccc1adc7393975e0f4a12a95dcb0";
+          sha256 = "oojBUIo8YIzVxAau4jwToYinemuDKYwaX+2OaZ28mW0=";
+        };
+      };
     in {
       devShells.default = pkgs.mkShell rec {
         buildInputs =
@@ -60,6 +72,7 @@
           domainslib
           # http server
           piaf
+          murmur
         ];
       };
     });
diff --git a/ocaml/lib/dune b/ocaml/lib/dune
index 97961d5..a0cb4b8 100644
--- a/ocaml/lib/dune
+++ b/ocaml/lib/dune
@@ -1,4 +1,4 @@
 (library
  (name nock_lib)
  (modules noun nock bitstream serial eventlog state effects boot runtime domain_pool nock_parallel)
- (libraries zarith eio eio.unix domainslib))
+ (libraries zarith eio eio.unix domainslib murmur3))
diff --git a/ocaml/lib/noun.ml b/ocaml/lib/noun.ml
index 0a666a4..f4c4f87 100644
--- a/ocaml/lib/noun.ml
+++ b/ocaml/lib/noun.ml
@@ -98,9 +98,56 @@ let inc = function
   | Atom { z; _ } -> Atom { z = Z.succ z; mug = 0l }
   | Cell _ -> raise Exit
 
+(** MurmurHash3 using external library *)
+
+(* Use the murmur3 library's hash function with seed parameter *)
+external murmur3_hash32_seed : string -> int32 -> int32 = "caml_murmur3_hash32_seed"
+
+(* u3r_mug_bytes: matches C implementation *)
+let mug_bytes_with_seed data seed =
+  let rec try_hash seed attempts =
+    if attempts >= 8 then 0x7fffl  (* Fallback after 8 attempts *)
+    else begin
+      let hash = murmur3_hash32_seed data seed in
+      let mug = Int32.logxor (Int32.shift_right_logical hash 31)
+                             (Int32.logand hash 0x7fffffffl) in
+      if mug = 0l then
+        try_hash (Int32.succ seed) (attempts + 1)
+      else
+        mug
+    end
+  in
+  try_hash seed 0
+
+(* c3_bits_word: count number of bits in a 32-bit word *)
+let c3_bits_word n =
+  let rec loop n bits =
+    if n = 0l then bits
+    else loop (Int32.shift_right_logical n 1) (bits + 1)
+  in
+  loop n 0
+
+(* u3r_mug_both: mix two mugs for cells *)
+let mug_both lef_mug rit_mug =
+  (* Calculate length based on bit width of rit_mug, matching C's c3_bits_word *)
+  let bits = c3_bits_word rit_mug in
+  let len = 4 + ((bits + 7) / 8) in
+  let buf = Bytes.create len in
+  (* Always write lef_mug (4 bytes) *)
+  Bytes.set buf 0 (Char.chr (Int32.to_int (Int32.logand lef_mug 0xffl)));
+  Bytes.set buf 1 (Char.chr (Int32.to_int (Int32.logand (Int32.shift_right_logical lef_mug 8) 0xffl)));
+  Bytes.set buf 2 (Char.chr (Int32.to_int (Int32.logand (Int32.shift_right_logical lef_mug 16) 0xffl)));
+  Bytes.set buf 3 (Char.chr (Int32.to_int (Int32.logand (Int32.shift_right_logical lef_mug 24) 0xffl)));
+  (* Write rit_mug bytes only if len > 4 *)
+  if len > 4 then Bytes.set buf 4 (Char.chr (Int32.to_int (Int32.logand rit_mug 0xffl)));
+  if len > 5 then Bytes.set buf 5 (Char.chr (Int32.to_int (Int32.logand (Int32.shift_right_logical rit_mug 8) 0xffl)));
+  if len > 6 then Bytes.set buf 6 (Char.chr (Int32.to_int (Int32.logand (Int32.shift_right_logical rit_mug 16) 0xffl)));
+  if len > 7 then Bytes.set buf 7 (Char.chr (Int32.to_int (Int32.logand (Int32.shift_right_logical rit_mug 24) 0xffl)));
+  mug_bytes_with_seed (Bytes.to_string buf) 0xdeadbeefl
+
 (** Compute mug (31-bit hash) of a noun with inline caching
 
-    This implements Urbit's mug hash function using FNV-1a.
+    This implements Urbit's mug hash function using MurmurHash3.
     Mugs are stored inline in the noun structure (like C's u3 system).
 
     The mug field is 0l when not yet computed, and computed lazily on first access.
@@ -126,7 +173,7 @@ let rec mug noun =
       else begin
         let h_mug = mug h in
         let t_mug = mug t in
-        let computed = mix_mugs h_mug t_mug in
+        let computed = mug_both h_mug t_mug in
         (* Update inline cache *)
         (match noun with
          | Cell r -> r.mug <- computed
@@ -135,31 +182,9 @@ let rec mug noun =
       end
 
 and compute_mug_atom z =
-  (* FNV-1a constants - using hex to avoid signed int32 overflow *)
-  let fnv_prime = 16777619l in
-  let fnv_basis = 0x811c9dc5l in  (* 2166136261 in decimal *)
-
-  (* Mask to 31 bits (Urbit uses 31-bit mugs) *)
-  let mask31 x = Int32.logand x 0x7fffffffl in
-
-  (* Convert atom to bytes and hash using FNV-1a *)
+  (* Convert to bytes (little-endian, strip trailing zeros) *)
   let bytes = Z.to_bits z in
-  let len = String.length bytes in
-  let rec loop i hash =
-    if i >= len then hash
-    else
-      let byte = Int32.of_int (Char.code bytes.[i]) in
-      let hash' = Int32.mul (Int32.logxor hash byte) fnv_prime in
-      loop (i + 1) hash'
-  in
-  mask31 (loop 0 fnv_basis)
-
-and mix_mugs a_mug b_mug =
-  (* Mix two mugs together (for cells) *)
-  let fnv_prime = 16777619l in
-  let mask31 x = Int32.logand x 0x7fffffffl in
-  let mixed = Int32.mul (Int32.logxor a_mug b_mug) fnv_prime in
-  mask31 mixed
+  mug_bytes_with_seed bytes 0xcafebabel
 
 (** Pretty-print a noun *)
 let rec pp_noun fmt = function
diff --git a/ocaml/test/dune b/ocaml/test/dune
index 8087a38..330f064 100644
--- a/ocaml/test/dune
+++ b/ocaml/test/dune
@@ -272,6 +272,11 @@
  (modules test_two_stage_boot)
  (libraries nock_lib eio_main unix))
 
+(executable
+ (name test_mug)
+ (modules test_mug)
+ (libraries nock_lib))
+
 ; (executable
 ;  (name test_life_formula)
 ;  (modules test_life_formula)
diff --git a/ocaml/test/test_mug.ml b/ocaml/test/test_mug.ml
new file mode 100644
index 0000000..0f5df7c
--- /dev/null
+++ b/ocaml/test/test_mug.ml
@@ -0,0 +1,161 @@
+(* Mug Test - Compare OCaml vs C mug computation *)
+
+open Nock_lib
+
+let () = Printf.printf "\n═══════════════════════════════════════\n";
+         Printf.printf " Mug Computation Test\n";
+         Printf.printf "═══════════════════════════════════════\n\n"
+
+(* Helper to print mug with description *)
+let test_mug desc noun =
+  let m = Noun.mug noun in
+  Printf.printf "%-40s 0x%08lx\n" desc m
+
+(* Helper to build a noun from string for readability *)
+let atom = Noun.atom
+let cell = Noun.cell
+
+let () =
+  Printf.printf "ATOMS - Small values:\n";
+  Printf.printf "─────────────────────────────────────\n";
+  test_mug "0" (atom 0);
+  test_mug "1" (atom 1);
+  test_mug "2" (atom 2);
+  test_mug "3" (atom 3);
+  test_mug "10" (atom 10);
+  test_mug "42" (atom 42);
+  test_mug "100" (atom 100);
+  test_mug "255" (atom 255);
+  test_mug "256" (atom 256);
+  test_mug "1000" (atom 1000);
+  Printf.printf "\n";
+
+  Printf.printf "ATOMS - Powers of 2:\n";
+  Printf.printf "─────────────────────────────────────\n";
+  test_mug "2^8 (256)" (atom 256);
+  test_mug "2^16 (65536)" (atom 65536);
+  test_mug "2^20 (1048576)" (atom 1048576);
+  test_mug "2^24 (16777216)" (atom 16777216);
+  test_mug "2^31 - 1 (max signed 32-bit)" (atom 2147483647);
+  Printf.printf "\n";
+
+  Printf.printf "ATOMS - Large values:\n";
+  Printf.printf "─────────────────────────────────────\n";
+  test_mug "2^32" (Noun.Atom { z = Z.shift_left Z.one 32; mug = 0l });
+  test_mug "2^64" (Noun.Atom { z = Z.shift_left Z.one 64; mug = 0l });
+  test_mug "2^128" (Noun.Atom { z = Z.shift_left Z.one 128; mug = 0l });
+  test_mug "0xdeadbeef" (Noun.Atom { z = Z.of_string "0xdeadbeef"; mug = 0l });
+  test_mug "0xcafebabe" (Noun.Atom { z = Z.of_string "0xcafebabe"; mug = 0l });
+  Printf.printf "\n";
+
+  Printf.printf "CELLS - Simple pairs:\n";
+  Printf.printf "─────────────────────────────────────\n";
+  test_mug "[0 0]" (cell (atom 0) (atom 0));
+  test_mug "[0 1]" (cell (atom 0) (atom 1));
+  test_mug "[1 0]" (cell (atom 1) (atom 0));
+  test_mug "[1 1]" (cell (atom 1) (atom 1));
+  test_mug "[1 2]" (cell (atom 1) (atom 2));
+  test_mug "[2 1]" (cell (atom 2) (atom 1));
+  test_mug "[42 0]" (cell (atom 42) (atom 0));
+  test_mug "[0 42]" (cell (atom 0) (atom 42));
+  test_mug "[42 42]" (cell (atom 42) (atom 42));
+  test_mug "[100 200]" (cell (atom 100) (atom 200));
+  Printf.printf "\n";
+
+  Printf.printf "CELLS - Nested structures:\n";
+  Printf.printf "─────────────────────────────────────\n";
+  test_mug "[[0 0] 0]" (cell (cell (atom 0) (atom 0)) (atom 0));
+  test_mug "[0 [0 0]]" (cell (atom 0) (cell (atom 0) (atom 0)));
+  test_mug "[[1 2] 3]" (cell (cell (atom 1) (atom 2)) (atom 3));
+  test_mug "[1 [2 3]]" (cell (atom 1) (cell (atom 2) (atom 3)));
+  test_mug "[[1 2] [3 4]]" (cell (cell (atom 1) (atom 2))
+                                 (cell (atom 3) (atom 4)));
+  test_mug "[[[0 1] 2] 3]" (cell (cell (cell (atom 0) (atom 1)) (atom 2)) (atom 3));
+  test_mug "[0 [1 [2 3]]]" (cell (atom 0) (cell (atom 1) (cell (atom 2) (atom 3))));
+  Printf.printf "\n";
+
+  Printf.printf "CELLS - Binary trees:\n";
+  Printf.printf "─────────────────────────────────────\n";
+  (* Balanced binary tree depth 2 *)
+  let tree2 = cell (cell (atom 1) (atom 2)) (cell (atom 3) (atom 4)) in
+  test_mug "Balanced tree depth 2" tree2;
+
+  (* Balanced binary tree depth 3 *)
+  let tree3 = cell
+    (cell (cell (atom 1) (atom 2)) (cell (atom 3) (atom 4)))
+    (cell (cell (atom 5) (atom 6)) (cell (atom 7) (atom 8))) in
+  test_mug "Balanced tree depth 3" tree3;
+
+  (* Left-heavy tree *)
+  let left_heavy = cell (cell (cell (atom 1) (atom 2)) (atom 3)) (atom 4) in
+  test_mug "Left-heavy tree" left_heavy;
+
+  (* Right-heavy tree *)
+  let right_heavy = cell (atom 1) (cell (atom 2) (cell (atom 3) (atom 4))) in
+  test_mug "Right-heavy tree" right_heavy;
+  Printf.printf "\n";
+
+  Printf.printf "LISTS - Null-terminated lists:\n";
+  Printf.printf "─────────────────────────────────────\n";
+  (* [1 2 3 ~] = [1 [2 [3 0]]] *)
+  let list_123 = cell (atom 1) (cell (atom 2) (cell (atom 3) (atom 0))) in
+  test_mug "[1 2 3 ~]" list_123;
+
+  (* [0 ~] = [0 0] *)
+  test_mug "[0 ~]" (cell (atom 0) (atom 0));
+
+  (* [42 ~] = [42 0] *)
+  test_mug "[42 ~]" (cell (atom 42) (atom 0));
+
+  (* Empty list: ~ = 0 *)
+  test_mug "~ (null/empty list)" (atom 0);
+
+  (* Longer list [1 2 3 4 5 ~] *)
+  let list_12345 = cell (atom 1)
+    (cell (atom 2)
+      (cell (atom 3)
+        (cell (atom 4)
+          (cell (atom 5) (atom 0))))) in
+  test_mug "[1 2 3 4 5 ~]" list_12345;
+  Printf.printf "\n";
+
+  Printf.printf "SPECIAL - Urbit constants:\n";
+  Printf.printf "─────────────────────────────────────\n";
+  (* YES and NO in Urbit *)
+  test_mug "YES (0)" (atom 0);
+  test_mug "NO (1)" (atom 1);
+
+  (* Common Urbit atoms *)
+  test_mug "~zod (0)" (atom 0);
+  test_mug "~nec (1)" (atom 1);
+  test_mug "~bud (2)" (atom 2);
+
+  (* Cord atoms (text) *)
+  let cord_atom s =
+    let rec loop i acc =
+      if i < 0 then acc
+      else loop (i - 1) (Z.add (Z.mul acc (Z.of_int 256)) (Z.of_int (Char.code s.[i])))
+    in
+    Noun.Atom { z = loop (String.length s - 1) Z.zero; mug = 0l }
+  in
+  test_mug "'hello'" (cord_atom "hello");
+  test_mug "'world'" (cord_atom "world");
+  test_mug "'urbit'" (cord_atom "urbit");
+  test_mug "'nock'" (cord_atom "nock");
+  Printf.printf "\n";
+
+  Printf.printf "EDGE CASES - Repeated values:\n";
+  Printf.printf "─────────────────────────────────────\n";
+  (* Same cell computed multiple times should have same mug *)
+  let pair = cell (atom 123) (atom 456) in
+  test_mug "[123 456] - first computation" pair;
+  test_mug "[123 456] - second computation" (cell (atom 123) (atom 456));
+
+  (* Nested identical cells *)
+  let nested = cell pair pair in
+  test_mug "[[123 456] [123 456]]" nested;
+  Printf.printf "\n";
+
+  Printf.printf "═══════════════════════════════════════\n";
+  Printf.printf "Test complete! Compare with C output.\n";
+  Printf.printf "═══════════════════════════════════════\n\n"
diff --git a/ocaml/test/test_two_stage_boot.ml b/ocaml/test/test_two_stage_boot.ml
index 62d262d..17c72a8 100644
--- a/ocaml/test/test_two_stage_boot.ml
+++ b/ocaml/test/test_two_stage_boot.ml
@@ -24,21 +24,27 @@ let stage1_ivory_boot env =
   let start = Unix.gettimeofday () in
   let pill = Serial.cue pill_bytes in
   let elapsed = Unix.gettimeofday () -. start in
-  Printf.printf "    ✓ Cued in %.2fs\n\n%!" elapsed;
+  Printf.printf "    ✓ Cued in %.2fs\n%!" elapsed;
+
+  let pill_mug = Noun.mug pill in
+  Printf.printf "    Pill mug: 0x%08lx\n\n%!" pill_mug;
 
   (* Check ivory structure: ["ivory" core] *)
   Printf.printf "[3] Parsing ivory pill structure...\n%!";
   match pill with
-  | Noun.Cell (tag, core) ->
+  | Noun.Cell { h = tag; t = core; _ } ->
       (* Check tag *)
       let tag_str = match tag with
-        | Noun.Atom z ->
+        | Noun.Atom { z; _ } ->
             let bytes = Z.to_bits z in
             if String.length bytes <= 10 then bytes else "too-long"
         | _ -> "not-atom"
       in
-      Printf.printf "    Tag: '%s'\n" tag_str;
-      Printf.printf "    Core: %s\n\n" (if Noun.is_cell core then "cell" else "atom");
+      let tag_mug = Noun.mug tag in
+      let core_mug = Noun.mug core in
+      Printf.printf "    Tag: '%s' (mug: 0x%08lx)\n" tag_str tag_mug;
+      Printf.printf "    Core: %s (mug: 0x%08lx)\n\n"
+        (if Noun.is_cell core then "cell" else "atom") core_mug;
 
       (* KEY DISCOVERY: The ivory pill tail IS the Arvo core! *)
       Printf.printf "[4] Using ivory pill tail (Arvo core) for bootstrap...\n%!";
@@ -47,14 +53,16 @@ let stage1_ivory_boot env =
 
       Printf.printf "[5] Running u3v_life() on Arvo core...\n%!";
       Printf.printf "    Formula: [2 [0 3] [0 2]]\n";
-      Printf.printf "    Subject: Arvo core (cell)\n%!";
+      Printf.printf "    Subject: Arvo core (cell, mug: 0x%08lx)\n%!" core_mug;
 
       begin try
         let start = Unix.gettimeofday () in
         let kernel = Boot.life core in
         let elapsed = Unix.gettimeofday () -. start in
 
-        Printf.printf "    ✓ SUCCESS! Kernel built in %.4fs\n\n" elapsed;
+        let kernel_mug = Noun.mug kernel in
+        Printf.printf "    ✓ SUCCESS! Kernel built in %.4fs\n" elapsed;
+        Printf.printf "    Kernel mug: 0x%08lx\n\n%!" kernel_mug;
 
         (* Verify kernel has poke at slot 23 *)
         Printf.printf "[6] Verifying kernel structure...\n%!";
@@ -86,14 +94,14 @@ let stage1_ivory_boot env =
               (if Noun.is_cell poke_battery then "cell ✓" else "atom ✗")
           end;
 
-          (* Compute mugs of small sub-structures for verification *)
+          (* Compute mugs of sub-structures for verification *)
           Printf.printf "    Computing mugs of sub-structures:\n";
           let slot2_mug = Noun.mug slot2 in
           let slot3_mug = Noun.mug slot3 in
           let poke_mug = Noun.mug poke in
-          Printf.printf "      Slot 2 mug: 0x%lx\n" slot2_mug;
-          Printf.printf "      Slot 3 mug: 0x%lx\n" slot3_mug;
-          Printf.printf "      Poke mug: 0x%lx\n" poke_mug;
+          Printf.printf "      Slot 2 (battery) mug: 0x%08lx\n" slot2_mug;
+          Printf.printf "      Slot 3 (payload) mug: 0x%08lx\n" slot3_mug;
+          Printf.printf "      Slot 23 (poke) mug:   0x%08lx\n" poke_mug;
 
           Printf.printf "\n";
           Printf.printf "╔═══════════════════════════════════════╗\n";
@@ -101,10 +109,8 @@ let stage1_ivory_boot env =
           Printf.printf "╚═══════════════════════════════════════╝\n\n";
 
           Printf.printf "⚠️  To verify correctness, compare these mugs with C:\n";
-          Printf.printf "    Run the C test and check if mugs match!\n\n";
-
-          (* Print cache stats *)
-          Noun.MugCache.stats ();
+          Printf.printf "    Run: vere/zig-out/bin/ivory_boot_test\n";
+          Printf.printf "    Check if mugs match!\n\n";
 
           Some kernel
 
@@ -122,8 +128,8 @@ let stage1_ivory_boot env =
           None
       end
 
-  | Noun.Atom _ ->
-      Printf.printf "    ✗ Pill is atom (expected cell)\n\n";
+  | Noun.Atom { z; _ } ->
+      Printf.printf "    ✗ Pill is atom (expected cell): %s\n\n" (Z.to_string z);
       None
 
 (* Stage 2: Boot solid pill events *)
diff --git a/vere/build.zig b/vere/build.zig
index 72baf8e..e2a7590 100644
--- a/vere/build.zig
+++ b/vere/build.zig
@@ -643,6 +643,11 @@ fn buildBinary(
                 .deps = vere_test_deps,
             },
             .{
+                .name = "mug-test",
+                .file = "pkg/vere/mug_test.c",
+                .deps = vere_test_deps,
+            },
+            .{
                 .name = "newt-test",
                 .file = "pkg/vere/newt_tests.c",
                 .deps = vere_test_deps,
diff --git a/vere/pkg/vere/mug_test.c b/vere/pkg/vere/mug_test.c
new file mode 100644
index 0000000..19bad89
--- /dev/null
+++ b/vere/pkg/vere/mug_test.c
@@ -0,0 +1,168 @@
+/* Mug Test - Compare C vs OCaml mug computation */
+
+#include "noun.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+
+/* Helper to print mug with description */
+static void
+test_mug(const char* desc, u3_noun noun)
+{
+  c3_w mug = u3r_mug(noun);
+  printf("%-40s 0x%08x\n", desc, mug);
+}
+
+/* Helper to build cord from string */
+static u3_atom
+_cord(const char* str)
+{
+  return u3i_string(str);
+}
+
+int
+main(int argc, char* argv[])
+{
+  /* Initialize u3 with lite boot (no jets, just memory) */
+  u3C.wag_w |= u3o_hashless;
+  u3m_boot_lite(1 << 28);  // 256MB loom
+
+  printf("\n═══════════════════════════════════════\n");
+  printf(" Mug Computation Test (C)\n");
+  printf("═══════════════════════════════════════\n\n");
+
+  printf("ATOMS - Small values:\n");
+  printf("─────────────────────────────────────\n");
+  test_mug("0", 0);
+  test_mug("1", 1);
+  test_mug("2", 2);
+  test_mug("3", 3);
+  test_mug("10", 10);
+  test_mug("42", 42);
+  test_mug("100", 100);
+  test_mug("255", 255);
+  test_mug("256", 256);
+  test_mug("1000", 1000);
+  printf("\n");
+
+  printf("ATOMS - Powers of 2:\n");
+  printf("─────────────────────────────────────\n");
+  test_mug("2^8 (256)", 256);
+  test_mug("2^16 (65536)", 65536);
+  test_mug("2^20 (1048576)", 1048576);
+  test_mug("2^24 (16777216)", 16777216);
+  test_mug("2^31 - 1 (max signed 32-bit)", 2147483647);
+  printf("\n");
+
+  printf("ATOMS - Large values:\n");
+  printf("─────────────────────────────────────\n");
+  test_mug("2^32", u3i_chub(1ULL << 32));
+  test_mug("2^64", u3i_chubs(1, (c3_d[]){0}));  // 2^64 would overflow, use 2^63
+  test_mug("2^128", u3i_chubs(2, (c3_d[]){0, 1}));
+  test_mug("0xdeadbeef", u3i_word(0xdeadbeef));
+  test_mug("0xcafebabe", u3i_word(0xcafebabe));
+  printf("\n");
+
+  printf("CELLS - Simple pairs:\n");
+  printf("─────────────────────────────────────\n");
+  test_mug("[0 0]", u3nc(0, 0));
+  test_mug("[0 1]", u3nc(0, 1));
+  test_mug("[1 0]", u3nc(1, 0));
+  test_mug("[1 1]", u3nc(1, 1));
+  test_mug("[1 2]", u3nc(1, 2));
+  test_mug("[2 1]", u3nc(2, 1));
+  test_mug("[42 0]", u3nc(42, 0));
+  test_mug("[0 42]", u3nc(0, 42));
+  test_mug("[42 42]", u3nc(42, 42));
+  test_mug("[100 200]", u3nc(100, 200));
+  printf("\n");
+
+  printf("CELLS - Nested structures:\n");
+  printf("─────────────────────────────────────\n");
+  test_mug("[[0 0] 0]", u3nc(u3nc(0, 0), 0));
+  test_mug("[0 [0 0]]", u3nc(0, u3nc(0, 0)));
+  test_mug("[[1 2] 3]", u3nc(u3nc(1, 2), 3));
+  test_mug("[1 [2 3]]", u3nc(1, u3nc(2, 3)));
+  test_mug("[[1 2] [3 4]]", u3nc(u3nc(1, 2), u3nc(3, 4)));
+  test_mug("[[[0 1] 2] 3]", u3nc(u3nc(u3nc(0, 1), 2), 3));
+  test_mug("[0 [1 [2 3]]]", u3nc(0, u3nc(1, u3nc(2, 3))));
+  printf("\n");
+
+  printf("CELLS - Binary trees:\n");
+  printf("─────────────────────────────────────\n");
+  /* Balanced binary tree depth 2 */
+  u3_noun tree2 = u3nc(u3nc(1, 2), u3nc(3, 4));
+  test_mug("Balanced tree depth 2", tree2);
+
+  /* Balanced binary tree depth 3 */
+  u3_noun tree3 = u3nc(
+    u3nc(u3nc(1, 2), u3nc(3, 4)),
+    u3nc(u3nc(5, 6), u3nc(7, 8))
+  );
+  test_mug("Balanced tree depth 3", tree3);
+
+  /* Left-heavy tree */
+  u3_noun left_heavy = u3nc(u3nc(u3nc(1, 2), 3), 4);
+  test_mug("Left-heavy tree", left_heavy);
+
+  /* Right-heavy tree */
+  u3_noun right_heavy = u3nc(1, u3nc(2, u3nc(3, 4)));
+  test_mug("Right-heavy tree", right_heavy);
+  printf("\n");
+
+  printf("LISTS - Null-terminated lists:\n");
+  printf("─────────────────────────────────────\n");
+  /* [1 2 3 ~] = [1 [2 [3 0]]] */
+  u3_noun list_123 = u3nc(1, u3nc(2, u3nc(3, 0)));
+  test_mug("[1 2 3 ~]", list_123);
+
+  /* [0 ~] = [0 0] */
+  test_mug("[0 ~]", u3nc(0, 0));
+
+  /* [42 ~] = [42 0] */
+  test_mug("[42 ~]", u3nc(42, 0));
+
+  /* Empty list: ~ = 0 */
+  test_mug("~ (null/empty list)", 0);
+
+  /* Longer list [1 2 3 4 5 ~] */
+  u3_noun list_12345 = u3nc(1, u3nc(2, u3nc(3, u3nc(4, u3nc(5, 0)))));
+  test_mug("[1 2 3 4 5 ~]", list_12345);
+  printf("\n");
+
+  printf("SPECIAL - Urbit constants:\n");
+  printf("─────────────────────────────────────\n");
+  /* YES and NO in Urbit */
+  test_mug("YES (0)", 0);
+  test_mug("NO (1)", 1);
+
+  /* Common Urbit atoms */
+  test_mug("~zod (0)", 0);
+  test_mug("~nec (1)", 1);
+  test_mug("~bud (2)", 2);
+
+  /* Cord atoms (text) */
+  test_mug("'hello'", _cord("hello"));
+  test_mug("'world'", _cord("world"));
+  test_mug("'urbit'", _cord("urbit"));
+  test_mug("'nock'", _cord("nock"));
+  printf("\n");
+
+  printf("EDGE CASES - Repeated values:\n");
+  printf("─────────────────────────────────────\n");
+  /* Same cell computed multiple times should have same mug */
+  u3_noun pair = u3nc(123, 456);
+  test_mug("[123 456] - first computation", pair);
+  test_mug("[123 456] - second computation", u3nc(123, 456));
+
+  /* Nested identical cells */
+  u3_noun nested = u3nc(pair, pair);
+  test_mug("[[123 456] [123 456]]", nested);
+  printf("\n");
+
+  printf("═══════════════════════════════════════\n");
+  printf("Test complete! Compare with OCaml.\n");
+  printf("═══════════════════════════════════════\n\n");
+
+  return 0;
+}