sva_formula/
hash.rs

1// Concern: content-addresses a SpectralSum under the table version, and draws a seed at a step | Non-concern: what a hash keys (sva-engine) | IO: (&SpectralSum) -> Hash
2
3use std::fmt;
4
5use crate::closed_form::{
6    Body, Bound, ClosedForm, Edge, Excitation, Fold, IndexId, ModalBank, Mode, Part, Rational,
7    Series, Unary, Var,
8};
9use crate::complex::{C64, canonical};
10use crate::env::NodeId;
11use crate::lanes::Lanes;
12use crate::run::Mirror;
13use crate::spectral_sum::atom::{Singular, SpectralAtom};
14use crate::spectral_sum::{Lane, SpectralSum};
15use crate::table::TABLE_VERSION;
16
17/// Two independently primed FNV-1a lanes: serving one closed form's samples for another is silent
18/// corruption, so the width is set against birthday collisions rather than speed.
19#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
20pub struct Hash(pub u64, pub u64);
21
22impl fmt::Display for Hash {
23    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
24        write!(f, "{:016x}{:016x}", self.0, self.1)
25    }
26}
27
28pub fn hash_spectral_sum(n: &SpectralSum) -> Hash {
29    hash_spectral_sum_under(n, TABLE_VERSION)
30}
31
32pub fn hash_closed_form(t: &ClosedForm) -> Hash {
33    hash_closed_form_under(t, TABLE_VERSION)
34}
35
36/// The version is the first field after the tag, so a table bump retires every entry keyed
37/// by one of these.
38pub fn hash_spectral_sum_under(n: &SpectralSum, table_version: u64) -> Hash {
39    let mut s = Sink::new(0x01, table_version);
40    s.var(n.var);
41    s.u64(n.lanes.len() as u64);
42    for lane in &n.lanes {
43        s.lane(lane);
44    }
45    s.finish()
46}
47
48pub fn hash_closed_form_under(t: &ClosedForm, table_version: u64) -> Hash {
49    let mut s = Sink::new(0x02, table_version);
50    s.var(t.var);
51    s.formula(&t.body);
52    s.finish()
53}
54
55/// A closed form that reads other nodes, each ref hashed as what `node` names it: the node's
56/// own content, never the number a graph gave it.
57pub fn hash_closed_form_with(t: &ClosedForm, node: &mut dyn FnMut(NodeId) -> Hash) -> Hash {
58    let mut s = Sink::new(0x04, TABLE_VERSION);
59    s.node = Some(node);
60    s.var(t.var);
61    s.formula(&t.body);
62    s.finish()
63}
64
65/// The unit-interval value one seed draws at one whole step, wherever the pair is written.
66pub fn draw(seed: u64, step: i64) -> f64 {
67    mix(mix(seed ^ DRAWN) ^ step as u64) as f64 / u64::MAX as f64
68}
69
70const DRAWN: u64 = 0x9e37_79b9_7f4a_7c15;
71
72/// The draw at the whole step nearest `key`, ties to even; `None` past any `i64` step.
73pub fn draw_nearest(seed: u64, key: f64) -> Option<f64> {
74    let step = key.round_ties_even();
75    let held = step >= i64::MIN as f64 && step < i64::MAX as f64;
76    held.then(|| draw(seed, step as i64))
77}
78
79struct Sink<'a> {
80    lanes: Lanes<0>,
81    node: Option<&'a mut dyn FnMut(NodeId) -> Hash>,
82    /// The series indices bound around the term being hashed, innermost last: an index is
83    /// hashed by which binder it names, never by the number a typing drew for it.
84    bound: Vec<IndexId>,
85}
86
87impl<'a> Sink<'a> {
88    fn new(tag: u8, table_version: u64) -> Sink<'a> {
89        let mut s = Sink {
90            lanes: Lanes::default(),
91            node: None,
92            bound: Vec::new(),
93        };
94        s.byte(tag);
95        s.u64(table_version);
96        s
97    }
98
99    fn byte(&mut self, b: u8) {
100        self.lanes.word(u64::from(b));
101    }
102
103    fn u64(&mut self, v: u64) {
104        for b in v.to_le_bytes() {
105            self.byte(b);
106        }
107    }
108
109    fn i64(&mut self, v: i64) {
110        self.u64(v as u64);
111    }
112
113    fn f64(&mut self, v: f64) {
114        self.u64(canonical(v));
115    }
116
117    fn c64(&mut self, v: C64) {
118        let (re, im) = v.bits();
119        self.u64(re);
120        self.u64(im);
121    }
122
123    fn var(&mut self, v: Var) {
124        self.byte(match v {
125            Var::T => 0,
126            Var::F => 1,
127        });
128    }
129
130    fn edge(&mut self, e: Edge) {
131        match e {
132            Edge::NegInf => self.byte(0),
133            Edge::At(bits) => {
134                self.byte(1);
135                self.u64(bits);
136            }
137            Edge::PosInf => self.byte(2),
138        }
139    }
140
141    fn lane(&mut self, lane: &Lane) {
142        self.u64(lane.atoms.len() as u64);
143        for a in &lane.atoms {
144            self.atom(a);
145        }
146        self.u64(lane.series.len() as u64);
147        for s in &lane.series {
148            self.series(s);
149        }
150        self.u64(lane.modal.len() as u64);
151        for m in &lane.modal {
152            self.modal(m);
153        }
154    }
155
156    /// `Origin` is excluded: two spellings from different files must hash alike.
157    fn atom(&mut self, a: &SpectralAtom) {
158        self.c64(a.c);
159        self.u64(u64::from(a.poly.degree));
160        self.f64(a.poly.at);
161        match a.exp {
162            None => self.byte(0),
163            Some(e) => {
164                self.byte(1);
165                self.f64(e.sigma);
166                self.f64(e.omega);
167            }
168        }
169        match a.gauss {
170            None => self.byte(0),
171            Some(g) => {
172                self.byte(1);
173                self.f64(g.a);
174                self.f64(g.mu);
175            }
176        }
177        match a.ind {
178            None => self.byte(0),
179            Some(i) => {
180                self.byte(1);
181                self.edge(i.l);
182                self.edge(i.r);
183            }
184        }
185        match a.pole {
186            None => self.byte(0),
187            Some(p) => {
188                self.byte(1);
189                self.c64(p.at);
190                self.u64(u64::from(p.order));
191                self.byte(u8::from(p.pv));
192            }
193        }
194        match a.sing {
195            Singular::Regular => self.byte(0),
196            Singular::Delta { at, order } => {
197                self.byte(1);
198                self.f64(at);
199                self.u64(u64::from(order));
200            }
201        }
202    }
203
204    fn series(&mut self, s: &Series) {
205        self.i64(s.lo);
206        match s.hi {
207            Bound::Finite(n) => {
208                self.byte(0);
209                self.i64(n);
210            }
211            Bound::Infinite => self.byte(1),
212        }
213        self.bound.push(s.index);
214        self.formula(&s.term.body);
215        self.bound.pop();
216    }
217
218    fn amps(&mut self, amps: &[C64]) {
219        self.u64(amps.len() as u64);
220        for a in amps {
221            self.c64(*a);
222        }
223    }
224
225    fn modal(&mut self, m: &ModalBank) {
226        self.u64(m.modes.len() as u64);
227        for Mode {
228            omega,
229            tau,
230            amp,
231            phase,
232        } in &m.modes
233        {
234            self.f64(*omega);
235            self.f64(*tau);
236            self.f64(*amp);
237            self.f64(*phase);
238        }
239        match m.excite {
240            Excitation::HammerPulse { f0, t0, contact } => {
241                self.byte(0);
242                self.f64(f0);
243                self.f64(t0);
244                self.f64(contact);
245            }
246            Excitation::Impulse { t0 } => {
247                self.byte(1);
248                self.f64(t0);
249            }
250        }
251    }
252
253    fn parts(&mut self, parts: &[Part]) {
254        self.u64(parts.len() as u64);
255        for p in parts {
256            self.formula(&p.body);
257        }
258    }
259
260    fn rational(&mut self, r: &Rational) {
261        self.u64(r.zeros.len() as u64);
262        for z in &r.zeros {
263            self.c64(*z);
264        }
265        self.u64(r.poles.len() as u64);
266        for p in &r.poles {
267            self.c64(*p);
268        }
269        self.c64(r.gain);
270    }
271
272    fn formula(&mut self, f: &Body) {
273        match f {
274            Body::Const(c) => {
275                self.byte(0x10);
276                self.c64(*c);
277            }
278            Body::Line => self.byte(0x11),
279            Body::Index(i) => {
280                let depth = self.bound.iter().rev().position(|b| b == i);
281                self.byte(0x12);
282                self.u64(depth.expect("an index inside the series binding it") as u64);
283            }
284            Body::Param(p) => {
285                self.byte(0x13);
286                self.u64(u64::from(p.0));
287            }
288            Body::Node(n) => {
289                self.byte(0x14);
290                match self.node.as_mut().map(|named| named(*n)) {
291                    Some(held) => {
292                        self.u64(held.0);
293                        self.u64(held.1);
294                    }
295                    None => self.u64(u64::from(n.0)),
296                }
297            }
298            Body::Add(parts) => {
299                self.byte(0x15);
300                self.parts(parts);
301            }
302            Body::Mul(parts) => {
303                self.byte(0x16);
304                self.parts(parts);
305            }
306            Body::Div(a, b) => {
307                self.byte(0x17);
308                self.formula(&a.body);
309                self.formula(&b.body);
310            }
311            Body::Pow(base, n) => {
312                self.byte(0x18);
313                self.formula(&base.body);
314                self.i64(i64::from(*n));
315            }
316            Body::Apply(op, arg) => {
317                self.byte(0x19);
318                self.byte(unary_tag(*op));
319                self.formula(&arg.body);
320            }
321            Body::Fold(op, args) => {
322                self.byte(0x1a);
323                self.byte(match op {
324                    Fold::Max => 0,
325                    Fold::Min => 1,
326                    Fold::Mod => 2,
327                });
328                self.parts(args);
329            }
330            Body::Delta { at, order } => {
331                self.byte(0x1b);
332                self.formula(&at.body);
333                self.u64(u64::from(*order));
334            }
335            Body::Pv(at) => {
336                self.byte(0x1c);
337                self.formula(&at.body);
338            }
339            Body::Warp { at, of } => {
340                self.byte(0x27);
341                self.formula(&at.body);
342                self.formula(&of.body);
343            }
344            Body::Shift { by, of } => {
345                self.byte(0x1d);
346                self.f64(*by);
347                self.formula(&of.body);
348            }
349            Body::Deriv { order, of } => {
350                self.byte(0x1e);
351                self.u64(u64::from(*order));
352                self.formula(&of.body);
353            }
354            Body::Crop {
355                of,
356                l,
357                r,
358                rise,
359                fall,
360            } => {
361                self.byte(0x1f);
362                self.formula(&of.body);
363                self.edge(*l);
364                self.edge(*r);
365                self.f64(*rise);
366                self.f64(*fall);
367            }
368            Body::Join(parts) => {
369                self.byte(0x21);
370                self.parts(parts);
371            }
372            Body::Channel(of, k) => {
373                self.byte(0x22);
374                self.formula(&of.body);
375                self.byte(*k);
376            }
377            Body::Rational(r) => {
378                self.byte(0x23);
379                self.rational(r);
380            }
381            Body::Series(s) => {
382                self.byte(0x24);
383                self.series(s);
384            }
385            Body::Modal(m) => {
386                self.byte(0x25);
387                self.modal(m);
388            }
389            Body::Run(run) => {
390                self.byte(0x28);
391                self.f64(run.offset);
392                self.f64(run.step);
393                self.i64(run.first);
394                self.amps(&run.amps);
395                match &run.mirror {
396                    Mirror::None => self.byte(0),
397                    Mirror::Conjugate => self.byte(1),
398                    Mirror::Held(amps) => {
399                        self.byte(2);
400                        self.amps(amps);
401                    }
402                }
403            }
404            Body::Keyed { seed, of } => {
405                self.byte(0x26);
406                self.u64(*seed);
407                self.formula(&of.body);
408            }
409        }
410    }
411
412    /// One avalanche past the lanes, so a short input still fills both words.
413    fn finish(&self) -> Hash {
414        let Hash(a, b) = self.lanes.finish();
415        Hash(mix(a), mix(b))
416    }
417}
418
419fn unary_tag(op: Unary) -> u8 {
420    match op {
421        Unary::Sin => 0,
422        Unary::Cos => 1,
423        Unary::Exp => 2,
424        Unary::Tanh => 3,
425        Unary::Sat => 4,
426        Unary::Abs => 5,
427        Unary::Log => 6,
428        Unary::Sqrt => 7,
429        Unary::Step => 8,
430    }
431}
432
433fn mix(mut z: u64) -> u64 {
434    z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
435    z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
436    z ^ (z >> 31)
437}
sva_formula/hash.rs

sva_formula/
hash.rs
