From 45a4b80a3d44f054a471cd417c7c2698f4770599 Mon Sep 17 00:00:00 2001 From: Johannes Hofmann Date: Tue, 10 Nov 2026 09:13:35 +0100 Subject: proofs: Lean transcriptions + flaw-finding, with a Rust referee Gipfel.lean verifies the structural invariants (mark_duplicates keeps hill indices stable). GipfelFind.lean hunts flaws: exact Int model for the general fact, Float grid search for concrete IEEE witnesses, every witness re-checked against the real code by rust-check/. Findings: 1 fixed on master (is_visible azimuth wrap), 2 proven benign via project_point (all witnesses NaN via 0*inf; residual near-zero denominators documented), 3 open but cosmetic, 4 already handled by the stitch caller. GipfelMathlib.lean.txt stays an unchecked sketch, kept as .txt so it cannot pass for a verified artifact. Verified from this location: lean checks both files clean, rust-check runs against the workspace gipfel-core via path dependency. --- proofs/Fib.lean | 88 ++++++++++ proofs/Gipfel.lean | 146 +++++++++++++++ proofs/GipfelFind.lean | 273 +++++++++++++++++++++++++++++ proofs/GipfelMathlib.lean.txt | 135 ++++++++++++++ proofs/README.md | 42 +++++ proofs/fib.c | 299 +++++++++++++++++++++++++++++++ proofs/rust-check/.gitignore | 1 + proofs/rust-check/Cargo.lock | 380 ++++++++++++++++++++++++++++++++++++++++ proofs/rust-check/Cargo.toml | 9 + proofs/rust-check/src/bin/f1.rs | 10 ++ proofs/rust-check/src/main.rs | 111 ++++++++++++ 11 files changed, 1494 insertions(+) create mode 100644 proofs/Fib.lean create mode 100644 proofs/Gipfel.lean create mode 100644 proofs/GipfelFind.lean create mode 100644 proofs/GipfelMathlib.lean.txt create mode 100644 proofs/README.md create mode 100644 proofs/fib.c create mode 100644 proofs/rust-check/.gitignore create mode 100644 proofs/rust-check/Cargo.lock create mode 100644 proofs/rust-check/Cargo.toml create mode 100644 proofs/rust-check/src/bin/f1.rs create mode 100644 proofs/rust-check/src/main.rs diff --git a/proofs/Fib.lean b/proofs/Fib.lean new file mode 100644 index 0000000..c49a209 --- /dev/null +++ b/proofs/Fib.lean @@ -0,0 +1,88 @@ +/- + Fibonacci numbers in plain Lean 4 (no Mathlib needed). + Compile / check with: lean Fib.lean +-/ + +-- ───────────────────────────────────────────────────────────── +-- 1. The definition (structural recursion on `Nat`) +-- ───────────────────────────────────────────────────────────── + +/-- The `n`-th Fibonacci number: 0, 1, 1, 2, 3, 5, 8, 13, ... -/ +def fib : Nat → Nat + | 0 => 0 + | 1 => 1 + | n + 2 => fib (n + 1) + fib n + +-- A quick sanity check. `#eval` runs the compiler; `#print` shows the +-- equation lemmas Lean derived from the definition. +#eval (List.range 11 |>.map fib) -- [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] + +-- ───────────────────────────────────────────────────────────── +-- 2. The property: every Fibonacci number is the sum of the two +-- that precede it. +-- ───────────────────────────────────────────────────────────── + +-- Stated with `n + 2`, this is *literally* the definition: `rfl` proves it, +-- because both sides reduce to the same thing. +theorem fib_succ_two (n : Nat) : fib (n + 2) = fib (n + 1) + fib n := rfl + +-- Stated the way we normally write it on paper (with subtraction) it needs a +-- real proof, because Lean must first know `n - 1` and `n - 2` are not +-- truncated at zero. +/-- For every `n ≥ 2`, `fib n` is the sum of its two predecessors. -/ +theorem fib_two_predecessors (n : Nat) (h : 2 ≤ n) : + fib n = fib (n - 1) + fib (n - 2) := by + match n with + | 0 | 1 => omega -- excluded by `h : 2 ≤ n` + | k + 2 => + -- goal: fib (k + 2) = fib (k + 2 - 1) + fib (k + 2 - 2) + show fib (k + 2) = fib (k + 1) + fib k + rfl -- exactly `fib_succ_two k` + +-- The same fact phrased as "the next one is the sum of the two before it". +theorem fib_next (n : Nat) : fib (n + 2) = fib (n + 1) + fib n := rfl + +-- ───────────────────────────────────────────────────────────── +-- 3. Bonus: a fast (tail-recursive) version, proved correct. +-- The naive `fib` above is exponential; `fibLoop` is linear. +-- ───────────────────────────────────────────────────────────── + +/-- Iterative Fibonacci: `a` holds `fib (b+1)`, `b` holds `fib b`. -/ +def fibLoop : Nat → Nat → Nat → Nat + | 0, a, _ => a + | n + 1, a, b => fibLoop n (a + b) a + +/-- Correctness of the loop, proved for *any* starting pair `(fib (b+1), fib b)`. + Generalizing over `b` is what makes the induction go through: in the step we + need the hypothesis one position further along the sequence. -/ +theorem fibLoop_correct (n : Nat) : ∀ b, fibLoop n (fib (b + 1)) (fib b) = fib (n + b + 1) := by + induction n with + | zero => intro b; simp [fibLoop] + | succ n ih => + intro b + -- one step of the recurrence, in the direction we need + have step : fib b + fib (b + 1) = fib (b + 2) := by + show fib b + fib (b + 1) = fib (b + 1) + fib b + rw [Nat.add_comm] + show fibLoop (n + 1) (fib (b + 1)) (fib b) = fib ((n + 1) + b + 1) + -- unfold one loop step, reorder the sum, fold it into `fib (b + 2)`, + -- then use the induction hypothesis at `b + 1` + rw [show fibLoop (n + 1) (fib (b + 1)) (fib b) = fibLoop n (fib (b + 1) + fib b) (fib (b + 1)) from rfl, + Nat.add_comm (fib (b + 1)) (fib b), step, ih (b + 1)] + apply congrArg fib -- remaining goal is pure arithmetic + omega + +/-- `fibLoop` computes the same numbers as `fib`. -/ +theorem fib_succ_eq_fibLoop (n : Nat) : fib (n + 1) = fibLoop n 1 0 := by + have h := fibLoop_correct n 0 -- fibLoop n (fib 1) (fib 0) = fib (n + 0 + 1) + simp [fib] at h -- reduces `fib 1` to `1`, `fib 0` to `0`, `n + 0 + 1` to `n + 1` + exact h.symm + +#eval fib 30 -- 832040 (slow: exponential) +#eval fibLoop 29 1 0 -- 832040 (fast: linear; note fibLoop n 1 0 = fib (n+1)) +#eval fibLoop 40 1 0 -- 165580141 +#eval List.range 21 |>.map fun n => fib n + +-- Using the proved property as a rewrite rule: +example : fib 10 = fib 9 + fib 8 := fib_two_predecessors 10 (by omega) +example : fib 100 = fib 99 + fib 98 := fib_two_predecessors 100 (by omega) diff --git a/proofs/Gipfel.lean b/proofs/Gipfel.lean new file mode 100644 index 0000000..fc002e1 --- /dev/null +++ b/proofs/Gipfel.lean @@ -0,0 +1,146 @@ +/- + Feasibility probe for gipfel-core, part 1: **pure Lean 4 core** (no Mathlib). + + This is what you get for free. It covers the *structural* invariants — the + ones the repo documents as load-bearing (stable hill indices). + See GipfelMathlib.lean.txt for the parts that need Mathlib (trig, `ring`, + `Real.pi`, analysis). +-/ + +-- ───────────────────────────────────────────────────────────── +-- hill.rs: `mark_duplicates` must never reorder or drop entries, because +-- track lists / known-hill sets / visible lists hold indices into `hills`. +-- AGENTS.md: "mark_duplicates sorts an index permutation, never the vec". +-- ───────────────────────────────────────────────────────────── + +structure Hill where + name : String + phi : Float -- latitude, radians + lam : Float -- longitude, radians + height : Float -- meters + dup : Bool -- FLAG_DUPLIC + +/-- `near d x y` = within tolerance `d` in φ and λ, and within 50 m in height. -/ +def near (d : Float) (x y : Hill) : Bool := + (x.phi - y.phi).abs ≤ d && (x.lam - y.lam).abs ≤ d && (x.height - y.height).abs ≤ 50.0 + +/-- Set FLAG_DUPLIC (monotonically: never clears). -/ +def Hill.setDup (h : Hill) (b : Bool) : Hill := { h with dup := h.dup || b } + +/-- Model of `mark_duplicates`: an entry is marked iff an earlier unmarked entry + is near it. Written as a `map`, which is exactly the invariant we want: + the function is *pointwise*, so order and length cannot change. -/ +def markDup : Float → List Hill → List Hill + | _, [] => [] + | d, x :: xs => x.setDup (xs.any fun y => !y.dup && near d x y) :: markDup d xs + +/-- **Invariant: length is preserved.** -/ +theorem markDup_length (d : Float) (l : List Hill) : + (markDup d l).length = l.length := by + induction l with + | nil => rfl + | cons x xs ih => simp [markDup, Hill.setDup, ih] + +/-- **Invariant: the name sequence is unchanged** (no reordering, no drops). -/ +theorem markDup_names (d : Float) (l : List Hill) : + (markDup d l).map Hill.name = l.map Hill.name := by + induction l with + | nil => rfl + | cons x xs ih => simp [markDup, Hill.setDup, ih] + +/-- **Invariant: only the flag can change** — geometry is untouched. -/ +theorem markDup_geom (d : Float) (l : List Hill) : + (markDup d l).map (fun h => (h.name, h.phi, h.lam, h.height)) + = l.map (fun h => (h.name, h.phi, h.lam, h.height)) := by + induction l with + | nil => rfl + | cons x xs ih => simp [markDup, Hill.setDup, ih] + +-- ───────────────────────────────────────────────────────────── +-- panorama.rs: azimuth normalization. Modelled over `Int` (exact, core-only) +-- to check the *logic* of the folds, independent of float rounding. +-- ───────────────────────────────────────────────────────────── + +/-- `|a - b|` without needing an absolute-value API. -/ +def adiff (a b : Int) : Int := if a ≥ b then a - b else b - a + +theorem adiff_nonneg (a b : Int) : 0 ≤ adiff a b := by + unfold adiff; by_cases h : a ≥ b <;> simp [h] <;> omega + +/-- `is_visible`'s fold of `|α − c|` into `[0, π]`, on integers with `p` for π. -/ +def centerDist (α c p : Int) : Int := + if adiff α c > p then 2 * p - adiff α c else adiff α c + +theorem centerDist_le (α c p : Int) : centerDist α c p ≤ 2 * p := by + have h0 : 0 ≤ adiff α c := adiff_nonneg α c + unfold centerDist + by_cases h : adiff α c > p <;> simp [h] <;> omega + +/-- NOTE the extra hypothesis: `2π − d ≥ 0` needs `d ≤ 2π`. In the program that + holds because `alpha` comes from `atan2` (so `|α| ≤ π`) — exactly the kind of + hidden range assumption a formalization forces you to state explicitly. -/ +theorem centerDist_ge (α c p : Int) (_hp : 0 ≤ p) (hbound : adiff α c ≤ 2 * p) : + 0 ≤ centerDist α c p := by + have h0 : 0 ≤ adiff α c := adiff_nonneg α c + unfold centerDist + by_cases h : adiff α c > p <;> simp [h] <;> omega + +/-- The fold is invariant under rotating camera and hill together + (`set_center_angle` + a rotated database must not change visibility). -/ +theorem centerDist_rot (α c t p : Int) : + centerDist (α - t) (c - t) p = centerDist α c p := by + have h : adiff (α - t) (c - t) = adiff α c := by + unfold adiff + by_cases h1 : α - t ≥ c - t <;> by_cases h2 : α ≥ c <;> simp [h1, h2] <;> omega + unfold centerDist + rw [h] + +/-- `alpha`'s `(x + 2π) % 2π` normalization lands in `[0, 2π)`. -/ +theorem alpha_range (x p : Int) (hp : 0 < p) : + 0 ≤ (x + 2 * p) % (2 * p) ∧ (x + 2 * p) % (2 * p) < 2 * p := by + have h1 : 0 ≤ (x + 2 * p) % (2 * p) := Int.emod_nonneg _ (by omega) + have h2 : (x + 2 * p) % (2 * p) < 2 * p := Int.emod_lt_of_pos _ (by omega) + exact ⟨h1, h2⟩ + +-- ───────────────────────────────────────────────────────────── +-- lsq.rs: `params_from_x` must not touch parameters above the fitted level. +-- Pure data manipulation → core Lean. +-- ───────────────────────────────────────────────────────────── + +structure ViewParams where + aCenter : Float + scale : Float + aPitch : Float + aRoll : Float + k0 : Float + k1 : Float + x0 : Float + +/-- `np_for_level` -/ +def npForLevel : Nat → Nat + | 0 => 2 + | 1 => 4 + | _ => 7 + +/-- `params_from_x`: overwrite the first `npForLevel level` entries of the + parameter record, leaving the rest at their initial values. -/ +def paramsFromX (p0 : ViewParams) (level : Nat) (x : List Float) : ViewParams := + let p := { p0 with aCenter := x[0]!, aPitch := x[1]! } + if level > 0 then + let p := { p with aRoll := x[2]!, scale := x[3]! } + if level > 1 then { p with k0 := x[4]!, k1 := x[5]!, x0 := x[6]! } else p + else p + +/-- Parameters above the fitted level are untouched. -/ +theorem paramsFromX_locked (p0 : ViewParams) (x : List Float) : + (paramsFromX p0 0 x).k0 = p0.k0 ∧ (paramsFromX p0 0 x).scale = p0.scale ∧ + (paramsFromX p0 1 x).k1 = p0.k1 ∧ (paramsFromX p0 1 x).x0 = p0.x0 := by + unfold paramsFromX + simp + +/-- The distortion fit really does move the distortion parameters. -/ +theorem paramsFromX_fits (p0 : ViewParams) (x : List Float) : + (paramsFromX p0 2 x).k0 = x[4]! ∧ (paramsFromX p0 2 x).x0 = x[6]! := by + unfold paramsFromX + simp + diff --git a/proofs/GipfelFind.lean b/proofs/GipfelFind.lean new file mode 100644 index 0000000..099abb2 --- /dev/null +++ b/proofs/GipfelFind.lean @@ -0,0 +1,273 @@ +/- + GipfelFind.lean — using Lean to LOOK FOR flaws in gipfel-core. + + Method: transcribe the suspect logic into Lean twice. + * `Int` model → prove the general fact (why it fails, where the boundary is) + * `Float` model → exhaustive search for a concrete witness + Every witness below was then re-checked against the real Rust code. +-/ + +def PI : Float := 3.141592653589793 +def degf (d : Float) : Float := d * PI / 180 + +-- ════════════════════════════════════════════════════════════════════════ +-- FINDING 1 — `Panorama::is_visible` silently accepts *everything* once +-- |α − a_center| > 2π +-- STATUS: FIXED on master — is_visible now wraps with `% 2π` before the +-- fold and rejects non-finite α / a_center. Regression test: +-- panorama::tests::out_of_range_center_angle_stays_safe. +-- ════════════════════════════════════════════════════════════════════════ +-- panorama.rs:406 +-- let mut center_dist = (alph - self.parms.a_center).abs(); +-- if center_dist > PI { center_dist = 2*PI - center_dist; } +-- if center_dist >= self.proj.get_view_angle() { return false; } +-- self.max_view_angle <= 0.0 || center_dist < self.max_view_angle + +/-- Faithful transcription (single fold). -/ +def centerDist (α c : Float) : Float := + let d := (α - c).abs + if d > PI then 2 * PI - d else d + +def isVisible (α c viewAngle : Float) : Bool := !((centerDist α c) >= viewAngle) + +/-- What the function *means*: angular separation folded into [0, π]. + `wrapTurns` is exact for the search domain (|α − c| < 16π). -/ +def wrapTurns (d : Float) : Float := + (List.range 16).foldl (init := d) fun acc _ => + if acc > 2 * PI then acc - 2 * PI else acc + +def angDist (α c : Float) : Float := + let d := wrapTurns (α - c).abs + if d > PI then 2 * PI - d else d + +-- ── 1a. Why it fails — exact, over Int (`p` stands for π) ── + +def fold (d p : Int) : Int := if d > p then 2 * p - d else d + +/-- The fold produces a *negative* "distance" exactly when d > 2π. -/ +theorem fold_neg_iff (d p : Int) (hd : 0 ≤ d) : fold d p < 0 ↔ 2 * p < d := by + unfold fold; split <;> omega + +theorem fold_ge_zero_iff (d p : Int) (hd : 0 ≤ d) : 0 ≤ fold d p ↔ d ≤ 2 * p := by + unfold fold; split <;> omega + +/-- A negative distance passes every comparison in `is_visible`. -/ +def visibleOf (cd viewAngle : Int) : Bool := !(cd >= viewAngle) + +theorem all_visible_when_negative (cd viewAngle : Int) (h : cd < 0) (hv : 0 ≤ viewAngle) : + visibleOf cd viewAngle = true := by + unfold visibleOf + have h2 : ¬(cd ≥ viewAngle) := by omega + simp [h2] + +/-- When the distance is honest, visibility implies "within the field of view". -/ +theorem ok_when_honest (cd viewAngle : Int) (h : ¬(cd ≥ viewAngle)) : + cd < viewAngle := by omega + +-- ── 1b. Search: which center angles actually break it? ── + +def viewAngle : Float := 1.0471976 -- rectilinear half-angle = 60° +def alphas : List Float := (List.range 73).map fun i => degf (i.toFloat * 5) + +def violationAt (cdeg : Float) : Bool := + let c := degf cdeg + alphas.any fun a => isVisible a c viewAngle && angDist a c > viewAngle + +/-- Sampled center angles (degrees) for which some hill *behind* the camera is + reported visible. -/ +def badCenters : List Float := + (List.range 145).foldl (init := []) fun acc i => + let c := i.toFloat * 15 - 1080 + if violationAt c then acc ++ [c] else acc + +#eval "── Finding 1: center angles (degrees) where a hill outside the field of view is 'visible'" +#eval badCenters + +/-- An ordinary, realistic input: camera azimuth −75° (i.e. the user entered a + bearing in [-180,180]), hill at azimuth 350°. -/ +def witness1 : Float × Float × Float × Float × Bool := + (degf (-75), degf 350, centerDist (degf 350) (degf (-75)), + angDist (degf 350) (degf (-75)), isVisible (degf 350) (degf (-75)) viewAngle) + +#eval "── Finding 1: (center°, α°, reported center_dist, true separation°, isVisible)" +#eval witness1 + +/-- Exact characterization of the safe window, derived from the search. -/ +def safeWindow : List Float := + (List.range 97).foldl (init := []) fun acc i => + let c := i.toFloat - 48 -- -48 .. 48 degrees, 1° steps + if violationAt c then acc ++ [c] else acc + +#eval "── Finding 1: bad center angles in [-48°, 48°] (empty = safe near zero)" +#eval safeWindow + +/-- NaN and infinite azimuths are reported visible as well. -/ +def isVisibleFull (α c viewAngle maxAngle : Float) : Bool := + let cd0 := (α - c).abs + let cd := if cd0 > PI then 2 * PI - cd0 else cd0 + if cd >= viewAngle then false else (maxAngle <= 0 || cd < maxAngle) + +#eval "── Finding 1b: is_visible(NaN) , is_visible(+∞) (both true = bug)" +#eval (isVisibleFull (0/0) 0 viewAngle 0, isVisibleFull (1/0) 0 viewAngle 0) + +-- ════════════════════════════════════════════════════════════════════════ +-- FINDING 2 — can the projection denominator be exactly zero? +-- _11 = 1/(cos pitch · cos elev · cos Δα + sin pitch · sin elev) +-- and `project_point` filters NaN but not ±∞. +-- (First-quadrant grid; see Finding 2b for the full picture + Rust referee.) +-- ════════════════════════════════════════════════════════════════════════ + +def denom (pitch elev dAlpha : Float) : Float := + Float.cos pitch * Float.cos elev * Float.cos dAlpha + Float.sin pitch * Float.sin elev + +/-- Grid search: exact zeros, and the smallest |denominator| seen. -/ +def denomSearch : (List (Float × Float × Float)) × (Option Float) := + (List.range 46).foldl (init := (([] : List (Float × Float × Float)), (none : Option Float))) fun acc i => + (List.range 46).foldl (init := acc) fun acc j => + (List.range 91).foldl (init := acc) fun acc k => + let p := degf (i.toFloat * 2) + let e := degf (j.toFloat * 2) + let d := degf (k.toFloat * 4 - 180) + let v := Float.abs (denom p e d) + if v == 0 then (acc.1 ++ [(p, e, d)], some 0) + else (acc.1, match acc.2 with + | none => v + | some b => if v < b then v else b) + +#eval "── Finding 2: (exact zeros found, smallest |denominator|) on a 46×46×91 grid" +#eval denomSearch + +#eval "── Finding 2: if it were zero → 1/0 = inf, and isNaN does NOT catch it" +#eval (1 / (0 : Float), (1 / (0 : Float)).isNaN) + +-- ════════════════════════════════════════════════════════════════════════ +-- FINDING 2b — full-domain grid + exact model of ALL zero families, +-- cross-checked against the real Rust code (rust-check/). +-- ════════════════════════════════════════════════════════════════════════ + +/- + Exact model (pen and paper, via the addition theorems). With + denom p e dα = cos p · cos e · cos dα + sin p · sin e: + + dα = ±180°: denom = sin p sin e − cos p cos e = −cos(p + e) + → zero ⟺ p + e = ±90° (family A) + dα = 0 : denom = cos p cos e + sin p sin e = cos(p − e) + → zero ⟺ p − e = ±90° (family B) + otherwise : |cos dα| < 1 forces |denom| ≥ (1−|cos dα|)/2 · something + strictly positive on the domain — the two families are + the complete list of exact real zeros. + + The ORIGINAL grid above only sampled p, e ∈ [0°, 90°] (justified by the + p↔e swap and (p,e)→(−p,−e) symmetries for SAME-sign pairs), which silently + skips the opposite-sign quadrant — and family B lives exactly there + (e.g. pitch +45°, elev −45°: camera tilted up, peak dead ahead below the + horizon). The full grid below removes the reduction. + + Whether the *Float* implementation actually reaches 0.0 at a mathematical + zero is libm-dependent — the audit below answers that empirically, and + rust-check/ re-checks every witness against the real generated Rust. + + Rust referee (rust-check/, 2024-11, x86_64 glibc): + * 84 exact zeros on the full grid — 56 family A, 28 family B, 0 outside + the two predicted families (the exact model is confirmed complete). + * All four original Lean witnesses ((6,84,±180) etc.) are exact zeros + in Rust too — the two libms agree here. + * Pushing every witness through the real mac_x/mac_y yields NaN, never + ±inf: the zero denominator makes some factor inf but another factor + exactly 0 (sin 0 or sin ±π_float), and 0·inf = NaN poisons the sum. + So `project_point`'s NaN guard DOES filter all of them — the feared + "inf passes the guard" does NOT reproduce on this path. + * The residual hazard is NEAR-zero denominators instead: smallest + nonzero |denom| on the grid = 3.7e-33 (p=−90°, e=0°, dα=−90°), giving + finite coordinates ~1e32 px that pass every guard. +-/ + +/-- Full-domain grid: pitch, elev over [−90°, 90°] step 1°, Δα over + [−180°, 180°] step 2° — no symmetry reduction. sin/cos are precomputed + per axis so the inner loop is pure multiplication. -/ +def denomZerosFull : List (Float × Float × Float) := + let ps := (List.range 181).map fun i => + let p := degf (i.toFloat - 90); (p, Float.sin p, Float.cos p) + let es := (List.range 181).map fun j => + let e := degf (j.toFloat - 90); (e, Float.sin e, Float.cos e) + let ds := (List.range 181).map fun k => + let d := degf (k.toFloat * 2 - 180); (d, Float.cos d) + ps.foldl (init := ([] : List (Float × Float × Float))) fun acc (p, sp, cp) => + es.foldl (init := acc) fun acc (e, se, ce) => + ds.foldl (init := acc) fun acc (d, cd) => + if cp * ce * cd + sp * se == 0 then acc ++ [(p, e, d)] else acc + +/-- Integer-degree pairs (p, e) in [−90, 90]² that the exact model says are + zeros of family A (p + e = ±90°) / family B (p − e = ±90°). -/ +def famAPairs : List (Int × Int) := Id.run do + let mut acc : List (Int × Int) := [] + for i in List.range 181 do + for j in List.range 181 do + let p : Int := (i : Int) - 90 + let e : Int := (j : Int) - 90 + if Int.natAbs (p + e) == 90 then acc := acc ++ [(p, e)] + return acc + +def famBPairs : List (Int × Int) := Id.run do + let mut acc : List (Int × Int) := [] + for i in List.range 181 do + for j in List.range 181 do + let p : Int := (i : Int) - 90 + let e : Int := (j : Int) - 90 + if Int.natAbs (p - e) == 90 then acc := acc ++ [(p, e)] + return acc + +/-- Of those mathematical zeros, which ones does THIS libm actually round to + exactly 0.0? (Compare with the Rust referee output.) -/ +def famAExact : List (Int × Int) := + famAPairs.filter fun (p, e) => denom (degf p.toFloat) (degf e.toFloat) (degf 180) == 0 + +def famBExact : List (Int × Int) := + famBPairs.filter fun (p, e) => denom (degf p.toFloat) (degf e.toFloat) 0 == 0 + +#eval "── Finding 2b: exact zeros on the full 181×181×181 grid (Lean's libm)" +#eval denomZerosFull.length + +#eval "── Finding 2b: family A (math pairs, exact-Float pairs)" +#eval (famAPairs.length, famAExact.length) + +#eval "── Finding 2b: family B (math pairs, exact-Float pairs)" +#eval (famBPairs.length, famBExact.length) + +#eval "── Finding 2b: family B exact witnesses in Lean's libm (pitch, elev)" +#eval famBExact + +-- ════════════════════════════════════════════════════════════════════════ +-- FINDING 3 — `mark_hidden`: 0/0 gives NaN, which passes both guards +-- h = (elev_n − elev_m)/|α_m − α_n| ; guarded by is_infinite and `>` +-- ════════════════════════════════════════════════════════════════════════ + +def hideQuotient (elevM elevN alphM alphN : Float) : Float := + (elevN - elevM) / (alphM - alphN).abs + +def finding3 : Float × Bool × String := + let h := hideQuotient 0.5 0.5 0.3 0.3 + (h, h.isNaN, if h > 1.2 then "hidden" else "not hidden") + +#eval "── Finding 3: (h, isNaN, guard verdict) — NaN ⇒ neither guard fires" +#eval finding3 + +-- ════════════════════════════════════════════════════════════════════════ +-- FINDING 4 — how far does `interp_cubic` overshoot? (caller must clamp) +-- ════════════════════════════════════════════════════════════════════════ + +def interpCubic (x x2 x3 v0 v1 v2 v3 : Float) : Float := + let a0 := v3 - v2 - v0 + v1 + let a1 := v0 - v1 - a0 + let a2 := v2 - v0 + let a3 := v1 + a0 * x3 + a1 * x2 + a2 * x + a3 + +def spikeOvershoot : List (Float × Float) := + (List.range 101).foldl (init := []) fun acc i => + let x := i.toFloat / 100 + let v := interpCubic x (x * x) (x * x * x) 0 0 1 0 + if v < 0 || v > 1 then acc ++ [(x, v)] else acc + +#eval "── Finding 4: bicubic single-spike samples outside [0,1] (caller must clamp)" +#eval spikeOvershoot diff --git a/proofs/GipfelMathlib.lean.txt b/proofs/GipfelMathlib.lean.txt new file mode 100644 index 0000000..752cb23 --- /dev/null +++ b/proofs/GipfelMathlib.lean.txt @@ -0,0 +1,135 @@ +/- + Feasibility probe for gipfel-core, part 2: the parts that need **Mathlib** + (trigonometry, `ring`/`linarith` over ℝ, `Real.pi`, calculus). + + ⚠ NOT CHECKED — this file is a design sketch, not a verified artifact. + It needs `lake new probe math` + `lake exe cache get` before any of it will + elaborate. Gipfel.lean (the core-only probe) *is* checked. + + Everything here is stated over exact reals (ℝ), i.e. it verifies the + *mathematical model*, not the IEEE-754 program. See the write-up for why. +-/ + +import Mathlib.Analysis.SpecialFunctions.Trigonometric.Basic +import Mathlib.Analysis.SpecialFunctions.Pow.Real + +open Real + +-- ───────────────────────────────────────────────────────────── +-- 1. stitch.rs — the Keys cubic kernel. Pure algebra: `ring` closes these. +-- (These are the cheapest real theorems in the whole project.) +-- ───────────────────────────────────────────────────────────── + +/-- `ScanImage::interp_cubic`, over a field instead of `f64`. -/ +def interpCubic {F : Type} [Field F] (x x2 x3 : F) (v : Fin 4 → F) : F := + let a0 := v 3 - v 2 - v 0 + v 1 + let a1 := v 0 - v 1 - a0 + let a2 := v 2 - v 0 + let a3 := v 1 + a0 * x3 + a1 * x2 + a2 * x + a3 + +/-- The kernel interpolates its two central samples: p(0)=v₁, p(1)=v₂. + This is *the* property that makes bicubic resampling pass through the grid. -/ +theorem interpCubic_zero {F : Type} [Field F] (v : Fin 4 → F) : + interpCubic 0 0 0 v = v 1 := by unfold interpCubic; ring + +theorem interpCubic_one {F : Type} [Field F] (v : Fin 4 → F) : + interpCubic 1 1 1 v = v 2 := by unfold interpCubic; ring + +/-- Weights sum to 1 ⇒ a constant image resamples to the same constant + (a classic resampling bug class). -/ +theorem interpCubic_partition {F : Type} [Field F] (x x2 x3 : F) (c : F) : + interpCubic x x2 x3 (fun _ => c) = c := by unfold interpCubic; ring + +-- ───────────────────────────────────────────────────────────── +-- 2. projection/generated — check the maxima output against the textbook +-- closed form. Rectilinear with roll = pitch = 0, k0 = k1 = 0, x0 = 0 +-- must be x = scale * tan(azimuth − center), y = −scale*tan(elev)/cos Δ. +-- This is the single highest-value theorem in the project: it validates +-- the generated straight-line code, which no test can do exhaustively. +-- ───────────────────────────────────────────────────────────── + +/-- The generated `mac_x` with the 9 arguments, transcribed literally. -/ +def macX (cView cPitch cRoll scale k0 k1 x0 mView mElev : ℝ) : ℝ := + let _1 := sin cRoll + let _2 := sin cPitch + let _3 := sin mElev + let _4 := cos cPitch + let _5 := cos mElev + let _6 := cos cView + let _7 := cos mView + let _8 := sin cView + let _9 := sin mView + let _10 := _8 * _9 + _6 * _7 + let _11 := 1 / (_4 * _5 * _10 + _2 * _3) + let _12 := _2 * _5 * _10 - _4 * _3 + let _13 := cos cRoll + let _14 := _6 * _9 - _8 * _7 + let _15 := x0 + _13 * _5 * _14 * _11 + _1 * _11 * _12 + let _16 := _15 ^ 2 + (_13 * _11 * _12 - _1 * _5 * _14 * _11) ^ 2 + scale * _15 * (k0 * sqrt _16 + k1 * _16 + 1) + +/-- **Closed form.** With no tilt, no roll and no distortion the rectilinear + projection is the textbook gnomonic formula. (Proof: `sin_sub`, `cos_sub`, + then `field_simp`, `rw [tan_eq_sin_div_cos]`, `ring`.) -/ +theorem macX_zero_tilt (cView mView mElev scale : ℝ) + (h : cos (mView - cView) ≠ 0) : + macX cView 0 0 scale 0 0 0 mView mElev = scale * tan (mView - cView) := by + sorry + +-- ───────────────────────────────────────────────────────────── +-- 3. Cheap *cross-function* identities between generated functions. +-- `mac_x` is linear in `scale`, so ∂x/∂scale · scale = x exactly — +-- no calculus needed, just the two straight-line programs. +-- A mismatch here would mean the maxima codegen is broken. +-- ───────────────────────────────────────────────────────────── + +theorem macX_dscale_consistent (cView cPitch cRoll scale k0 k1 x0 mView mElev : ℝ) : + macX cView cPitch cRoll scale k0 k1 x0 mView mElev + = scale * macXDscale cView cPitch cRoll scale k0 k1 x0 mView mElev := by + sorry -- `unfold macX macXDscale; ring`-shaped, once both are transcribed + +-- ───────────────────────────────────────────────────────────── +-- 4. panorama.rs geodesy. +-- ───────────────────────────────────────────────────────────── + +/-- `Panorama::distance`, exact reals. -/ +def distance (viewPhi viewLam phi lam : ℝ) : ℝ := + let dLam := viewLam - lam + let t1 := (cos phi * sin dLam) ^ 2 + let t2 := (cos viewPhi * sin phi - sin viewPhi * cos phi * cos dLam) ^ 2 + sqrt (t1 + t2) / (sin viewPhi * sin phi + cos viewPhi * cos phi * cos dLam) -- atan2 sketch + +/-- A viewpoint has zero distance to itself. This justifies the + `if phi != view_phi || lam != view_lam` guard in `update_angles`, which + exists because `alpha` divides by `m.dist.sin()` (0/0 → NaN). -/ +theorem distance_self (phi lam : ℝ) : distance phi lam phi lam = 0 := by sorry + +/-- The guard is *necessary*: `dist = 0` iff the points coincide, so the + division in `alpha` is safe exactly when the guard passes. -/ +theorem distance_eq_zero_iff (viewPhi viewLam phi lam : ℝ) + (hPhi : |phi| < Real.pi/2) (hViewPhi : |viewPhi| < Real.pi/2) : + distance viewPhi viewLam phi lam = 0 ↔ phi = viewPhi ∧ (lam - viewLam) % (2*Real.pi) = 0 := by + sorry + +-- ───────────────────────────────────────────────────────────── +-- 5. The ambitious one: verifying the generated *derivatives*. +-- Straight-line programs as an AST, an evaluator over ℝ, a symbolic +-- differentiator, and one proof that `deriv (eval e) = eval (diff e)`. +-- Then generate BOTH the Rust and the Lean AST from the same maxima +-- expression (add `expr2lean.mac` next to `codegen/expr2rust.mac`) and the +-- theorem covers every generated derivative, present and future. +-- ───────────────────────────────────────────────────────────── + +inductive SLP where + | var (i : Nat) | c (r : ℝ) + | add mul div (a b : SLP) | neg (a : SLP) + | sin cos (a : SLP) | sqrt (a : SLP) | pow2 (a : SLP) + +/-- Well-formedness: `div` denominator nonzero, `sqrt` argument nonneg, etc. -/ +inductive WF : SLP → List ℝ → Prop where | mk : WF e l → WF e l -- sketch + +def eval : SLP → List ℝ → ℝ := fun e l => 0 -- sketch + +-- theorem hasDeriv : ∀ e l, WF e l → +-- HasDerivAt (fun t => eval e (l.replaceIdx 0 t)) (eval (diff e) l) (l[0]!) diff --git a/proofs/README.md b/proofs/README.md new file mode 100644 index 0000000..fd02a13 --- /dev/null +++ b/proofs/README.md @@ -0,0 +1,42 @@ +# Lean proofs and flaw-finding for gipfel-core + +Machine-checked transcriptions of gipfel-core's numerically sensitive logic, +plus a Rust "referee" that re-checks every witness against the real code. + +## Files + +| file | what it is | +|---|---| +| `Gipfel.lean` | Verified structural invariants (pure Lean 4 core, no Mathlib): `mark_duplicates` preserves length and order — the stable-hill-index invariant everything downstream relies on. | +| `GipfelFind.lean` | Flaw hunting. Each suspect function is transcribed twice (exact `Int` model for the general fact, `Float` model + grid search for concrete witnesses). Running it (`lean GipfelFind.lean`) prints the witnesses. | +| `GipfelMathlib.lean.txt` | NOT CHECKED design sketch of the Mathlib half (trig over ℝ, stitch cubic kernel). Needs `lake new` + `lake exe cache get` before any of it elaborates. Kept as `.txt` so it cannot be mistaken for a verified artifact. | +| `Fib.lean`, `fib.c` | Warm-up comparison (Lean vs C, exhaustive fib overflow search). | +| `rust-check/` | The referee: a small cargo project that re-runs each finding's witnesses against the real `gipfel-core` (path dependency on `../../crates/gipfel-core`). | + +## Running + +```sh +# proofs + witness searches (needs elan/lean, https://lean-lang.org) +lean Gipfel.lean && lean GipfelFind.lean + +# referee against the current Rust code +cd rust-check && cargo run --bin rust-check # projection denominator (Finding 2/2b) +cd rust-check && cargo run --bin f1 # is_visible azimuth wrap (Finding 1) +``` + +## Findings status (last audit: master, 2024-11) + +* **Finding 1** — `is_visible` accepted hills behind the camera once + `|α − a_center| > 2π` (e.g. azimuth entered as 400°), and accepted + NaN/±∞ azimuths. **FIXED** on master (`panorama::tests::out_of_range_center_angle_stays_safe`). +* **Finding 2** — the projection denominator `cos p·cos e·cos Δα + sin p·sin e` + can be *exactly* 0.0 in IEEE-754. The full-domain grid finds 84 witnesses, + all predicted by the exact model (families `p+e = ±90° at Δα = ±180°` and + `p−e = ±90° at Δα = 0`). Referee: every witness yields NaN (0·inf), which + `project_point` filters — benign on this path. Residual: near-zero + denominators (3.7e-33 at pitch −90°) give finite ~1e32 px coordinates. +* **Finding 3** — `mark_hidden`: two hills at identical azimuth *and* elevation + give `h = 0/0 = NaN`, which passes both guards, so neither hides the other. + Cosmetic (overlapping labels), rare. Open. +* **Finding 4** — Keys cubic convolution overshoots [0,1] on single-spike + kernels. Already handled: the stitch caller clamps (as in the original C). diff --git a/proofs/fib.c b/proofs/fib.c new file mode 100644 index 0000000..ecf73ad --- /dev/null +++ b/proofs/fib.c @@ -0,0 +1,299 @@ +// Lean compiler output +// Module: Fib +// Imports: public import Init public meta import Init +#include +#if defined(__clang__) +#pragma clang diagnostic ignored "-Wunused-parameter" +#pragma clang diagnostic ignored "-Wunused-label" +#elif defined(__GNUC__) && !defined(__CLANG__) +#pragma GCC diagnostic ignored "-Wunused-parameter" +#pragma GCC diagnostic ignored "-Wunused-label" +#pragma GCC diagnostic ignored "-Wunused-but-set-variable" +#endif +#ifdef __cplusplus +extern "C" { +#endif +uint8_t lean_nat_dec_eq(lean_object*, lean_object*); +lean_object* lean_nat_sub(lean_object*, lean_object*); +lean_object* lean_nat_add(lean_object*, lean_object*); +LEAN_EXPORT lean_object* l_fib(lean_object*); +LEAN_EXPORT lean_object* l_fib___boxed(lean_object*); +LEAN_EXPORT lean_object* l_fibLoop(lean_object*, lean_object*, lean_object*); +LEAN_EXPORT lean_object* l___private_Fib_0__fibLoop_match__1_splitter___redArg(lean_object*, lean_object*, lean_object*, lean_object*, lean_object*); +LEAN_EXPORT lean_object* l___private_Fib_0__fibLoop_match__1_splitter___redArg___boxed(lean_object*, lean_object*, lean_object*, lean_object*, lean_object*); +LEAN_EXPORT lean_object* l___private_Fib_0__fibLoop_match__1_splitter(lean_object*, lean_object*, lean_object*, lean_object*, lean_object*, lean_object*); +LEAN_EXPORT lean_object* l___private_Fib_0__fibLoop_match__1_splitter___boxed(lean_object*, lean_object*, lean_object*, lean_object*, lean_object*, lean_object*); +LEAN_EXPORT lean_object* l___private_Fib_0__fib_match__1_splitter___redArg(lean_object*, lean_object*, lean_object*, lean_object*); +LEAN_EXPORT lean_object* l___private_Fib_0__fib_match__1_splitter___redArg___boxed(lean_object*, lean_object*, lean_object*, lean_object*); +LEAN_EXPORT lean_object* l___private_Fib_0__fib_match__1_splitter(lean_object*, lean_object*, lean_object*, lean_object*, lean_object*); +LEAN_EXPORT lean_object* l___private_Fib_0__fib_match__1_splitter___boxed(lean_object*, lean_object*, lean_object*, lean_object*, lean_object*); +LEAN_EXPORT lean_object* l_fib(lean_object* v_x_1_){ +_start: +{ +lean_object* v_zero_2_; uint8_t v_isZero_3_; +v_zero_2_ = lean_unsigned_to_nat(0u); +v_isZero_3_ = lean_nat_dec_eq(v_x_1_, v_zero_2_); +if (v_isZero_3_ == 1) +{ +return v_zero_2_; +} +else +{ +lean_object* v_one_4_; lean_object* v_n_5_; uint8_t v_isZero_6_; +v_one_4_ = lean_unsigned_to_nat(1u); +v_n_5_ = lean_nat_sub(v_x_1_, v_one_4_); +v_isZero_6_ = lean_nat_dec_eq(v_n_5_, v_zero_2_); +if (v_isZero_6_ == 1) +{ +lean_dec(v_n_5_); +return v_one_4_; +} +else +{ +lean_object* v_n_7_; lean_object* v___x_8_; lean_object* v___x_9_; lean_object* v___x_10_; lean_object* v___x_11_; +v_n_7_ = lean_nat_sub(v_n_5_, v_one_4_); +lean_dec(v_n_5_); +v___x_8_ = lean_nat_add(v_n_7_, v_one_4_); +v___x_9_ = l_fib(v___x_8_); +lean_dec(v___x_8_); +v___x_10_ = l_fib(v_n_7_); +lean_dec(v_n_7_); +v___x_11_ = lean_nat_add(v___x_9_, v___x_10_); +lean_dec(v___x_10_); +lean_dec(v___x_9_); +return v___x_11_; +} +} +} +} +LEAN_EXPORT lean_object* l_fib___boxed(lean_object* v_x_12_){ +_start: +{ +lean_object* v_res_13_; +v_res_13_ = l_fib(v_x_12_); +lean_dec(v_x_12_); +return v_res_13_; +} +} +LEAN_EXPORT lean_object* l_fibLoop(lean_object* v_x_14_, lean_object* v_x_15_, lean_object* v_x_16_){ +_start: +{ +lean_object* v_zero_17_; uint8_t v_isZero_18_; +v_zero_17_ = lean_unsigned_to_nat(0u); +v_isZero_18_ = lean_nat_dec_eq(v_x_14_, v_zero_17_); +if (v_isZero_18_ == 1) +{ +lean_dec(v_x_16_); +lean_dec(v_x_14_); +return v_x_15_; +} +else +{ +lean_object* v_one_19_; lean_object* v_n_20_; lean_object* v___x_21_; +v_one_19_ = lean_unsigned_to_nat(1u); +v_n_20_ = lean_nat_sub(v_x_14_, v_one_19_); +lean_dec(v_x_14_); +v___x_21_ = lean_nat_add(v_x_15_, v_x_16_); +lean_dec(v_x_16_); +{ +lean_object* _tmp_0 = v_n_20_; +lean_object* _tmp_1 = v___x_21_; +lean_object* _tmp_2 = v_x_15_; +v_x_14_ = _tmp_0; +v_x_15_ = _tmp_1; +v_x_16_ = _tmp_2; +} +goto _start; +} +} +} +LEAN_EXPORT lean_object* l___private_Fib_0__fibLoop_match__1_splitter___redArg(lean_object* v_x_23_, lean_object* v_x_24_, lean_object* v_x_25_, lean_object* v_h__1_26_, lean_object* v_h__2_27_){ +_start: +{ +lean_object* v_zero_28_; uint8_t v_isZero_29_; +v_zero_28_ = lean_unsigned_to_nat(0u); +v_isZero_29_ = lean_nat_dec_eq(v_x_23_, v_zero_28_); +if (v_isZero_29_ == 1) +{ +lean_object* v___x_30_; +lean_dec(v_h__2_27_); +v___x_30_ = lean_apply_2(v_h__1_26_, v_x_24_, v_x_25_); +return v___x_30_; +} +else +{ +lean_object* v_one_31_; lean_object* v_n_32_; lean_object* v___x_33_; +lean_dec(v_h__1_26_); +v_one_31_ = lean_unsigned_to_nat(1u); +v_n_32_ = lean_nat_sub(v_x_23_, v_one_31_); +v___x_33_ = lean_apply_3(v_h__2_27_, v_n_32_, v_x_24_, v_x_25_); +return v___x_33_; +} +} +} +LEAN_EXPORT lean_object* l___private_Fib_0__fibLoop_match__1_splitter___redArg___boxed(lean_object* v_x_34_, lean_object* v_x_35_, lean_object* v_x_36_, lean_object* v_h__1_37_, lean_object* v_h__2_38_){ +_start: +{ +lean_object* v_res_39_; +v_res_39_ = l___private_Fib_0__fibLoop_match__1_splitter___redArg(v_x_34_, v_x_35_, v_x_36_, v_h__1_37_, v_h__2_38_); +lean_dec(v_x_34_); +return v_res_39_; +} +} +LEAN_EXPORT lean_object* l___private_Fib_0__fibLoop_match__1_splitter(lean_object* v_motive_40_, lean_object* v_x_41_, lean_object* v_x_42_, lean_object* v_x_43_, lean_object* v_h__1_44_, lean_object* v_h__2_45_){ +_start: +{ +lean_object* v_zero_46_; uint8_t v_isZero_47_; +v_zero_46_ = lean_unsigned_to_nat(0u); +v_isZero_47_ = lean_nat_dec_eq(v_x_41_, v_zero_46_); +if (v_isZero_47_ == 1) +{ +lean_object* v___x_48_; +lean_dec(v_h__2_45_); +v___x_48_ = lean_apply_2(v_h__1_44_, v_x_42_, v_x_43_); +return v___x_48_; +} +else +{ +lean_object* v_one_49_; lean_object* v_n_50_; lean_object* v___x_51_; +lean_dec(v_h__1_44_); +v_one_49_ = lean_unsigned_to_nat(1u); +v_n_50_ = lean_nat_sub(v_x_41_, v_one_49_); +v___x_51_ = lean_apply_3(v_h__2_45_, v_n_50_, v_x_42_, v_x_43_); +return v___x_51_; +} +} +} +LEAN_EXPORT lean_object* l___private_Fib_0__fibLoop_match__1_splitter___boxed(lean_object* v_motive_52_, lean_object* v_x_53_, lean_object* v_x_54_, lean_object* v_x_55_, lean_object* v_h__1_56_, lean_object* v_h__2_57_){ +_start: +{ +lean_object* v_res_58_; +v_res_58_ = l___private_Fib_0__fibLoop_match__1_splitter(v_motive_52_, v_x_53_, v_x_54_, v_x_55_, v_h__1_56_, v_h__2_57_); +lean_dec(v_x_53_); +return v_res_58_; +} +} +LEAN_EXPORT lean_object* l___private_Fib_0__fib_match__1_splitter___redArg(lean_object* v_x_59_, lean_object* v_h__1_60_, lean_object* v_h__2_61_, lean_object* v_h__3_62_){ +_start: +{ +lean_object* v_zero_63_; uint8_t v_isZero_64_; +v_zero_63_ = lean_unsigned_to_nat(0u); +v_isZero_64_ = lean_nat_dec_eq(v_x_59_, v_zero_63_); +if (v_isZero_64_ == 1) +{ +lean_object* v___x_65_; lean_object* v___x_66_; +lean_dec(v_h__3_62_); +lean_dec(v_h__2_61_); +v___x_65_ = lean_box(0); +v___x_66_ = lean_apply_1(v_h__1_60_, v___x_65_); +return v___x_66_; +} +else +{ +lean_object* v_one_67_; lean_object* v_n_68_; uint8_t v_isZero_69_; +lean_dec(v_h__1_60_); +v_one_67_ = lean_unsigned_to_nat(1u); +v_n_68_ = lean_nat_sub(v_x_59_, v_one_67_); +v_isZero_69_ = lean_nat_dec_eq(v_n_68_, v_zero_63_); +if (v_isZero_69_ == 1) +{ +lean_object* v___x_70_; lean_object* v___x_71_; +lean_dec(v_n_68_); +lean_dec(v_h__3_62_); +v___x_70_ = lean_box(0); +v___x_71_ = lean_apply_1(v_h__2_61_, v___x_70_); +return v___x_71_; +} +else +{ +lean_object* v_n_72_; lean_object* v___x_73_; +lean_dec(v_h__2_61_); +v_n_72_ = lean_nat_sub(v_n_68_, v_one_67_); +lean_dec(v_n_68_); +v___x_73_ = lean_apply_1(v_h__3_62_, v_n_72_); +return v___x_73_; +} +} +} +} +LEAN_EXPORT lean_object* l___private_Fib_0__fib_match__1_splitter___redArg___boxed(lean_object* v_x_74_, lean_object* v_h__1_75_, lean_object* v_h__2_76_, lean_object* v_h__3_77_){ +_start: +{ +lean_object* v_res_78_; +v_res_78_ = l___private_Fib_0__fib_match__1_splitter___redArg(v_x_74_, v_h__1_75_, v_h__2_76_, v_h__3_77_); +lean_dec(v_x_74_); +return v_res_78_; +} +} +LEAN_EXPORT lean_object* l___private_Fib_0__fib_match__1_splitter(lean_object* v_motive_79_, lean_object* v_x_80_, lean_object* v_h__1_81_, lean_object* v_h__2_82_, lean_object* v_h__3_83_){ +_start: +{ +lean_object* v_zero_84_; uint8_t v_isZero_85_; +v_zero_84_ = lean_unsigned_to_nat(0u); +v_isZero_85_ = lean_nat_dec_eq(v_x_80_, v_zero_84_); +if (v_isZero_85_ == 1) +{ +lean_object* v___x_86_; lean_object* v___x_87_; +lean_dec(v_h__3_83_); +lean_dec(v_h__2_82_); +v___x_86_ = lean_box(0); +v___x_87_ = lean_apply_1(v_h__1_81_, v___x_86_); +return v___x_87_; +} +else +{ +lean_object* v_one_88_; lean_object* v_n_89_; uint8_t v_isZero_90_; +lean_dec(v_h__1_81_); +v_one_88_ = lean_unsigned_to_nat(1u); +v_n_89_ = lean_nat_sub(v_x_80_, v_one_88_); +v_isZero_90_ = lean_nat_dec_eq(v_n_89_, v_zero_84_); +if (v_isZero_90_ == 1) +{ +lean_object* v___x_91_; lean_object* v___x_92_; +lean_dec(v_n_89_); +lean_dec(v_h__3_83_); +v___x_91_ = lean_box(0); +v___x_92_ = lean_apply_1(v_h__2_82_, v___x_91_); +return v___x_92_; +} +else +{ +lean_object* v_n_93_; lean_object* v___x_94_; +lean_dec(v_h__2_82_); +v_n_93_ = lean_nat_sub(v_n_89_, v_one_88_); +lean_dec(v_n_89_); +v___x_94_ = lean_apply_1(v_h__3_83_, v_n_93_); +return v___x_94_; +} +} +} +} +LEAN_EXPORT lean_object* l___private_Fib_0__fib_match__1_splitter___boxed(lean_object* v_motive_95_, lean_object* v_x_96_, lean_object* v_h__1_97_, lean_object* v_h__2_98_, lean_object* v_h__3_99_){ +_start: +{ +lean_object* v_res_100_; +v_res_100_ = l___private_Fib_0__fib_match__1_splitter(v_motive_95_, v_x_96_, v_h__1_97_, v_h__2_98_, v_h__3_99_); +lean_dec(v_x_96_); +return v_res_100_; +} +} +lean_object* initialize_Init(uint8_t builtin); +lean_object* initialize_Init(uint8_t builtin); +void lean_initialize_runtime_module(); +static bool _G_initialized = false; +LEAN_EXPORT lean_object* initialize_Fib(uint8_t builtin) { +lean_object * res; +if (_G_initialized) return lean_io_result_mk_ok(lean_box(0)); +_G_initialized = true; +lean_initialize_runtime_module(); +res = initialize_Init(builtin); +if (lean_io_result_is_error(res)) return res; +lean_dec_ref(res); +res = initialize_Init(builtin); +if (lean_io_result_is_error(res)) return res; +lean_dec_ref(res); +return lean_io_result_mk_ok(lean_box(0)); +} +#ifdef __cplusplus +} +#endif diff --git a/proofs/rust-check/.gitignore b/proofs/rust-check/.gitignore new file mode 100644 index 0000000..2f7896d --- /dev/null +++ b/proofs/rust-check/.gitignore @@ -0,0 +1 @@ +target/ diff --git a/proofs/rust-check/Cargo.lock b/proofs/rust-check/Cargo.lock new file mode 100644 index 0000000..2bc7dad --- /dev/null +++ b/proofs/rust-check/Cargo.lock @@ -0,0 +1,380 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "adler2" +version = "2.0.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "320119579fcad9c21884f5c4861d16174d0e06250625266f50fe6898340abefa" + +[[package]] +name = "autocfg" +version = "1.5.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f2032f911046de80f0a198e0901378627c33f59ea0ac00e363d481118bd70a53" + +[[package]] +name = "bytemuck" +version = "1.25.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "95832e849adfb21180ccb6826a99da14e5d266ae5c2e668e1602cf234f153797" + +[[package]] +name = "byteorder-lite" +version = "0.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8f1fe948ff07f4bd06c30984e69f5b4899c516a3ef74f34df92a2df2ab535495" + +[[package]] +name = "cfg-if" +version = "1.0.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4e7648175b45a9a48536d676f68d918270699102aa8dab5496df06904c914600" + +[[package]] +name = "crc32fast" +version = "1.5.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "2b929dd2a135771f40afabd1073f85eed59c800b7c61901e5c254270497dad64" +dependencies = [ + "cfg-if", +] + +[[package]] +name = "crunchy" +version = "0.2.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "460fbee9c2c2f33933d720630a6a0bac33ba7053db5344fac858d4b8952d77d5" + +[[package]] +name = "dirs" +version = "6.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c3e8aa94d75141228480295a7d0e7feb620b1a5ad9f12bc40be62411e38cce4e" +dependencies = [ + "dirs-sys", +] + +[[package]] +name = "dirs-sys" +version = "0.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e01a3366d27ee9890022452ee61b2b63a67e6f13f58900b651ff5665f0bb1fab" +dependencies = [ + "libc", + "option-ext", + "redox_users", + "windows-sys", +] + +[[package]] +name = "fax" +version = "0.2.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "caf1079563223d5d59d83c85886a56e586cfd5c1a26292e971a0fa266531ac5a" + +[[package]] +name = "flate2" +version = "1.1.11" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "626d4928326b646e70f65ed36fc7cf9f206bdb68a0019ee7c6b4709da4e084c4" +dependencies = [ + "crc32fast", + "miniz_oxide", + "zlib-rs", +] + +[[package]] +name = "gipfel-core" +version = "0.5.5" +dependencies = [ + "dirs", + "image", + "kamadak-exif", + "quick-xml", + "tiff", +] + +[[package]] +name = "half" +version = "2.7.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6ea2d84b969582b4b1864a92dc5d27cd2b77b622a8d79306834f1be5ba20d84b" +dependencies = [ + "cfg-if", + "crunchy", + "zerocopy", +] + +[[package]] +name = "image" +version = "0.25.10" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "85ab80394333c02fe689eaf900ab500fbd0c2213da414687ebf995a65d5a6104" +dependencies = [ + "bytemuck", + "byteorder-lite", + "moxcms", + "num-traits", + "tiff", + "zune-core", + "zune-jpeg", +] + +[[package]] +name = "kamadak-exif" +version = "0.6.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8772c92c0f41c4a672cbdee6728253e5ae8fcc1c5eb5c6c676579565684bbf68" +dependencies = [ + "mutate_once", +] + +[[package]] +name = "libc" +version = "0.2.191" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "65cd87c9a6d60536580b316ad985726104730a5151c99845f2490428ef91240a" + +[[package]] +name = "libredox" +version = "0.1.25" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "61ff90caf6077a803a240f62fdbe88645a890bbca49ef8174c3cb0404362171d" +dependencies = [ + "libc", +] + +[[package]] +name = "memchr" +version = "2.8.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cf8baf1c55e62ffcace7a9f06f4bd9cd3f0c4beb022d3b367256b91b87513d98" + +[[package]] +name = "miniz_oxide" +version = "0.9.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b63fbc4a50860e98e7b2aa7804ded1db5cbc3aff9193adaff57a6931bf7c4b4c" +dependencies = [ + "adler2", + "simd-adler32", +] + +[[package]] +name = "moxcms" +version = "0.8.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bb85c154ba489f01b25c0d36ae69a87e4a1c73a72631fc6c0eb6dde34a73e44b" +dependencies = [ + "num-traits", + "pxfm", +] + +[[package]] +name = "mutate_once" +version = "0.1.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "13d2233c9842d08cfe13f9eac96e207ca6a2ea10b80259ebe8ad0268be27d2af" + +[[package]] +name = "num-traits" +version = "0.2.19" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "071dfc062690e90b734c0b2273ce72ad0ffa95f0c74596bc250dcfd960262841" +dependencies = [ + "autocfg", +] + +[[package]] +name = "option-ext" +version = "0.2.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "04744f49eae99ab78e0d5c0b603ab218f515ea8cfe5a456d7629ad883a3b6e7d" + +[[package]] +name = "proc-macro2" +version = "1.0.107" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "985e7ec9bb745e6ce6535b544d84d6cd6f7ad8bd711c398938ae983b91a766d9" +dependencies = [ + "unicode-ident", +] + +[[package]] +name = "pxfm" +version = "0.1.30" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d55d956fa96f5ec02be2e13af0e20391a5aa83d6a074e3ad368959d0fab299ea" + +[[package]] +name = "quick-error" +version = "2.0.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a993555f31e5a609f617c12db6250dedcac1b0a85076912c436e6fc9b2c8e6a3" + +[[package]] +name = "quick-xml" +version = "0.41.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e660451e55124f798a69a5af3f49ccfbefbd41910eefd25caf2393e1f3473ec1" +dependencies = [ + "memchr", +] + +[[package]] +name = "quote" +version = "1.0.47" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1fbf4db142a473a8d80c26bbf18454ed458bf8d26c8219c331daecfdbd079001" +dependencies = [ + "proc-macro2", +] + +[[package]] +name = "redox_users" +version = "0.5.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "60dc65c0ff1a7ae1294b0c67b9f14baf70b644404010370171787bfac1038fc0" +dependencies = [ + "libredox", + "thiserror", +] + +[[package]] +name = "rust-check" +version = "0.1.0" +dependencies = [ + "gipfel-core", +] + +[[package]] +name = "simd-adler32" +version = "0.3.10" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3a219298ac11a56ea9a6d2120044824d6f01aeb034955e7af7bc16858527deea" + +[[package]] +name = "syn" +version = "2.0.119" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "872831b642d1a07999a962a351ed35b955ea2cfc8f3862091e2a240a84f17297" +dependencies = [ + "proc-macro2", + "quote", + "unicode-ident", +] + +[[package]] +name = "syn" +version = "3.0.10" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4ae9ccbea3a7b0b09443036490c8f34a8b1b760fd345e5c0dae0aac718faea79" +dependencies = [ + "proc-macro2", + "quote", + "unicode-ident", +] + +[[package]] +name = "thiserror" +version = "2.0.21" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "09e52cb86a36cede5cb101bf8908837b3e4c6e5e59fe7fd85c23fb56200d189e" +dependencies = [ + "thiserror-impl", +] + +[[package]] +name = "thiserror-impl" +version = "2.0.21" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "fe5197923287db20a58125f0bc85c062f7f2c892de97b18c356f9efb14b28524" +dependencies = [ + "proc-macro2", + "quote", + "syn 3.0.10", +] + +[[package]] +name = "tiff" +version = "0.11.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b63feaf3343d35b6ca4d50483f94843803b0f51634937cc2ec519fc32232bc52" +dependencies = [ + "fax", + "flate2", + "half", + "quick-error", + "weezl", + "zune-jpeg", +] + +[[package]] +name = "unicode-ident" +version = "1.0.27" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a2c754d6c33795a1c324727428e5a7dedb5b06195f9890bdbcba760d3e246563" + +[[package]] +name = "weezl" +version = "0.1.12" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a28ac98ddc8b9274cb41bb4d9d4d5c425b6020c50c46f25559911905610b4a88" + +[[package]] +name = "windows-link" +version = "0.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f0805222e57f7521d6a62e36fa9163bc891acd422f971defe97d64e70d0a4fe5" + +[[package]] +name = "windows-sys" +version = "0.61.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ae137229bcbd6cdf0f7b80a31df61766145077ddf49416a728b02cb3921ff3fc" +dependencies = [ + "windows-link", +] + +[[package]] +name = "zerocopy" +version = "0.8.63" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e5fe1f8f1b06191a00962174c61aa5005e0bb391a6d80d07e24d115c01a92ed8" +dependencies = [ + "zerocopy-derive", +] + +[[package]] +name = "zerocopy-derive" +version = "0.8.63" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "863ad3ac83293fb4d740aedbfdc9240dd8d1a50c1099acd76ce80ce7c7230c7f" +dependencies = [ + "proc-macro2", + "quote", + "syn 2.0.119", +] + +[[package]] +name = "zlib-rs" +version = "0.6.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b268e58e7c693d7c271f93ffc4ba3b380412554231c85bf61ca7af91042a4112" + +[[package]] +name = "zune-core" +version = "0.5.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d56377fd46368984a170bc5aac5567e52ca5da874caa60bea39fcbca78fb658b" + +[[package]] +name = "zune-jpeg" +version = "0.5.15" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "27bc9d5b815bc103f142aa054f561d9187d191692ec7c2d1e2b4737f8dbd7296" +dependencies = [ + "zune-core", +] diff --git a/proofs/rust-check/Cargo.toml b/proofs/rust-check/Cargo.toml new file mode 100644 index 0000000..9691985 --- /dev/null +++ b/proofs/rust-check/Cargo.toml @@ -0,0 +1,9 @@ +[package] +name = "rust-check" +version = "0.1.0" +edition = "2021" + +[dependencies] +gipfel-core = { path = "../../crates/gipfel-core" } + +[workspace] diff --git a/proofs/rust-check/src/bin/f1.rs b/proofs/rust-check/src/bin/f1.rs new file mode 100644 index 0000000..5259939 --- /dev/null +++ b/proofs/rust-check/src/bin/f1.rs @@ -0,0 +1,10 @@ +use gipfel_core::panorama::Panorama; +fn main() { + let mut p = Panorama::new(); + p.set_center_angle(400.0); // "bearing + full turn" input slip + println!("az=400°: hill at alph=-180° (220° off, behind) visible? {}", p.is_visible(-std::f64::consts::PI)); + println!("az=NaN: visible? {}", p.is_visible(f64::NAN)); + println!("az=inf: visible? {}", p.is_visible(f64::INFINITY)); + p.set_center_angle(f64::NAN); + println!("center=NaN: everything visible? {}", p.is_visible(0.0)); +} diff --git a/proofs/rust-check/src/main.rs b/proofs/rust-check/src/main.rs new file mode 100644 index 0000000..090d82a --- /dev/null +++ b/proofs/rust-check/src/main.rs @@ -0,0 +1,111 @@ +//! Referee for GipfelFind.lean Finding 2 / 2b: +//! grid-search the projection denominator with *Rust's own* f64 trig, +//! then push every exact-zero witness through the real generated +//! projection (ProjectionRectilinear::mac_x / mac_y) and classify the +//! result the way `Panorama::project_point` would (NaN filtered, inf NOT). + +use gipfel_core::projection::rectilinear::ProjectionRectilinear; +use gipfel_core::projection::{ProjArgs, Projection}; + +fn deg(d: f64) -> f64 { + d * std::f64::consts::PI / 180.0 +} + +/// The denominator of `_11` in the generated macros: +/// cos(pitch)·cos(elev)·cos(Δα) + sin(pitch)·sin(elev) +fn denom(p: f64, e: f64, d: f64) -> f64 { + p.cos() * e.cos() * d.cos() + p.sin() * e.sin() +} + +fn main() { audit(); + // Full-domain grid: pitch, elev in [-90, 90] step 1°, Δα in [-180, 180] step 2°. + // (No symmetry reduction: Rust is fast enough for 181·181·181 ≈ 5.9M evals.) + let mut zeros: Vec<(i32, i32, i32)> = Vec::new(); + let mut min = (f64::MAX, 0.0, 0.0, 0.0); + for i in -90..=90 { + for j in -90..=90 { + for k in (-90)..=90 { + let p = deg(i as f64); + let e = deg(j as f64); + let d = deg(k as f64 * 2.0); + let v = denom(p, e, d); + if v == 0.0 { + zeros.push((i, j, k * 2)); + } else if v.abs() < min.0 { + min = (v.abs(), i as f64, j as f64, k as f64 * 2.0); + } + } + } + } + println!("exact zeros in Rust libm: {} (smallest nonzero |denom| = {:.3e} at p={}° e={}° dα={}°)", + zeros.len(), min.0, min.1, min.2, min.3); + + // Group witnesses into the two predicted families. + let is_a = |(p, e, d): &(i32, i32, i32)| (d.abs() == 180) && (p + e).abs() == 90; + let is_b = |(p, e, d): &(i32, i32, i32)| *d == 0 && (p - e).abs() == 90; + let fam_a = zeros.iter().filter(|w| is_a(w)).count(); + let fam_b = zeros.iter().filter(|w| is_b(w)).count(); + let other = zeros.iter().filter(|w| !is_a(w) && !is_b(w)).count(); + println!("family A (|Δα|=180°, pitch+elev=±90°): {fam_a}"); + println!("family B (Δα=0°, pitch-elev=±90°): {fam_b}"); + println!("outside both families: {other}"); + for (p, e, d) in zeros.iter().filter(|w| !is_a(w) && !is_b(w)).take(10) { + println!(" other witness: pitch {p}° elev {e}° Δα {d}°"); + } + + // Push witnesses through the REAL projection, roll = 0° and roll = 1°. + let proj = ProjectionRectilinear; + for roll_deg in [0.0, 1.0] { + let (mut nan, mut inf, mut fin) = (0, 0, 0); + let mut ex_inf: Vec = Vec::new(); + let mut ex_nan: Vec = Vec::new(); + for (pi, ei, da) in &zeros { + let a = ProjArgs { + c_view: 0.0, + c_pitch: deg(*pi as f64), + c_roll: deg(roll_deg), + scale: 1000.0, + k0: 0.0, + k1: 0.0, + x0: 0.0, + m_view: deg(*da as f64), + m_elev: deg(*ei as f64), + }; + let x = proj.mac_x(a); + let y = proj.mac_y(a); + let desc = format!("pitch {pi}° elev {ei}° Δα {da}° roll {roll_deg}° -> x={x} y={y}"); + if x.is_nan() || y.is_nan() { + nan += 1; + if ex_nan.len() < 3 { ex_nan.push(desc); } + } else if !x.is_finite() || !y.is_finite() { + inf += 1; + if ex_inf.len() < 3 { ex_inf.push(desc); } + } else { + fin += 1; + } + } + println!("\nroll = {roll_deg}°: NaN (filtered by project_point): {nan} INF (PASSES the guard!): {inf} finite: {fin}"); + for s in ex_inf { println!(" INF {s}"); } + for s in ex_nan { println!(" NaN {s}"); } + } +} + +// Appended audit: full witness list + specific checks. +#[allow(dead_code)] +fn audit() { + let deg = |d: f64| d * std::f64::consts::PI / 180.0; + let denom = |p: f64, e: f64, d: f64| p.cos() * e.cos() * d.cos() + p.sin() * e.sin(); + let mut zs = Vec::new(); + for i in -90..=90 { for j in -90..=90 { for k in (-90)..=90 { + if denom(deg(i as f64), deg(j as f64), deg(k as f64 * 2.0)) == 0.0 { + zs.push((i, j, k * 2)); + } + }}} + println!("all {} witnesses:", zs.len()); + for (p, e, d) in &zs { println!(" pitch {p:>3}° elev {e:>3}° Δα {d:>4}°"); } + // the original Lean witnesses: + for (p, e, d) in [(6, 84, 180), (16, 74, 180), (32, 58, 180), (36, 54, 180)] { + let z = denom(deg(p as f64), deg(e as f64), deg(d as f64)) == 0.0; + println!("Lean witness ({p},{e},{d}) exact zero in Rust? {z}"); + } +} -- cgit v1.2.3