sva_formula/
hash.rs

1// Concern: content-addresses a written closed form and a read's time, and draws a seed at a step | Non-concern: what a hash keys (sva-engine) | IO: (&ClosedForm, a namer) -> 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::content_hash::{ContentHasher, HashDomain};
11use crate::env::NodeId;
12use crate::fourier_dual::FOURIER_DUAL_RULES_VERSION;
13use crate::run::Mirror;
14use crate::spectral_sum::Lane;
15use crate::spectral_sum::atom::{Singular, SpectralAtom};
16
17/// Serving one closed form's samples for another is silent corruption, so the width is set
18/// 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
28/// Two operands of a sum or product, which IEEE commutes bit for bit; three never associate so.
29pub fn either_order(operands: &mut [Hash]) {
30    if let [a, b] = operands
31        && b < a
32    {
33        std::mem::swap(a, b);
34    }
35}
36
37/// A closed form as written, each subterm by its own hash and each ref as `node` names it, so a
38/// node named by its form's hash reads alike by ref or written in place.
39pub fn hash_written_with(t: &ClosedForm, node: &mut dyn FnMut(NodeId) -> Hash) -> Hash {
40    let mut s = Sink {
41        hasher: ContentHasher::new(HashDomain::WrittenClosedForm),
42        node: Some(node),
43        bound: Vec::new(),
44        free: true,
45        merkle: true,
46    };
47    let held = s.part(&t.body);
48    match t.var {
49        Var::T => held,
50        Var::F => {
51            let mut f = ContentHasher::new(HashDomain::ClosedFormInFrequency);
52            f.hash(held);
53            f.finish()
54        }
55    }
56}
57
58/// A time a ref is read at, as a reading of that ref is kept under: an index it holds is one
59/// series' own, named by its number.
60pub fn hash_time(at: &Body) -> Hash {
61    let mut s = Sink {
62        hasher: ContentHasher::new(HashDomain::ReadTime),
63        node: None,
64        bound: Vec::new(),
65        free: true,
66        merkle: false,
67    };
68    s.u64(FOURIER_DUAL_RULES_VERSION);
69    s.formula(at);
70    s.finish()
71}
72
73/// The unit-interval value one seed draws at one whole step, wherever the pair is written.
74pub fn draw(seed: u64, step: i64) -> f64 {
75    mix(mix(seed ^ DRAWN) ^ step as u64) as f64 / u64::MAX as f64
76}
77
78const DRAWN: u64 = 0x9e37_79b9_7f4a_7c15;
79
80/// The draw at the whole step nearest `key`, ties to even; `None` past any `i64` step.
81pub fn draw_nearest(seed: u64, key: f64) -> Option<f64> {
82    let step = key.round_ties_even();
83    let held = step >= i64::MIN as f64 && step < i64::MAX as f64;
84    held.then(|| draw(seed, step as i64))
85}
86
87struct Sink<'a> {
88    hasher: ContentHasher,
89    node: Option<&'a mut dyn FnMut(NodeId) -> Hash>,
90    /// The series indices bound around the term being hashed, innermost last: an index is
91    /// hashed by which binder it names, never by the number a typing drew for it.
92    bound: Vec<IndexId>,
93    /// Whether an index no binder here names is named by its own number.
94    free: bool,
95    /// Each subterm named by its own hash, as a ref is by its node's.
96    merkle: bool,
97}
98
99impl<'a> Sink<'a> {
100    fn byte(&mut self, b: u8) {
101        self.hasher.word(u64::from(b));
102    }
103
104    fn u64(&mut self, v: u64) {
105        self.hasher.word(v);
106    }
107
108    fn i64(&mut self, v: i64) {
109        self.u64(v as u64);
110    }
111
112    fn f64(&mut self, v: f64) {
113        self.u64(canonical(v));
114    }
115
116    fn c64(&mut self, v: C64) {
117        let (re, im) = v.bits();
118        self.u64(re);
119        self.u64(im);
120    }
121
122    fn edge(&mut self, e: Edge) {
123        match e {
124            Edge::NegInf => self.byte(0),
125            Edge::At(bits) => {
126                self.byte(1);
127                self.u64(bits);
128            }
129            Edge::PosInf => self.byte(2),
130        }
131    }
132
133    fn lane(&mut self, lane: &Lane) {
134        self.u64(lane.atoms.len() as u64);
135        for a in &lane.atoms {
136            self.atom(a);
137        }
138        self.u64(lane.series.len() as u64);
139        for s in &lane.series {
140            self.series(s);
141        }
142        self.u64(lane.modal.len() as u64);
143        for m in &lane.modal {
144            self.modal(m);
145        }
146    }
147
148    /// `Origin` is excluded: two spellings from different files must hash alike.
149    fn atom(&mut self, a: &SpectralAtom) {
150        self.c64(a.c);
151        self.u64(u64::from(a.poly.degree));
152        self.f64(a.poly.at);
153        match a.exp {
154            None => self.byte(0),
155            Some(e) => {
156                self.byte(1);
157                self.f64(e.sigma);
158                self.f64(e.omega);
159            }
160        }
161        match a.gauss {
162            None => self.byte(0),
163            Some(g) => {
164                self.byte(1);
165                self.f64(g.a);
166                self.f64(g.mu);
167            }
168        }
169        match a.ind {
170            None => self.byte(0),
171            Some(i) => {
172                self.byte(1);
173                self.edge(i.l);
174                self.edge(i.r);
175            }
176        }
177        match a.pole {
178            None => self.byte(0),
179            Some(p) => {
180                self.byte(1);
181                self.c64(p.at);
182                self.u64(u64::from(p.order));
183                self.byte(u8::from(p.pv));
184            }
185        }
186        match a.sing {
187            Singular::Regular => self.byte(0),
188            Singular::Delta { at, order } => {
189                self.byte(1);
190                self.f64(at);
191                self.u64(u64::from(order));
192            }
193        }
194    }
195
196    fn series(&mut self, s: &Series) {
197        self.i64(s.lo);
198        match s.hi {
199            Bound::Finite(n) => {
200                self.byte(0);
201                self.i64(n);
202            }
203            Bound::Infinite => self.byte(1),
204        }
205        self.bound.push(s.index);
206        self.formula(&s.term.body);
207        self.bound.pop();
208    }
209
210    fn amps(&mut self, amps: &[C64]) {
211        self.u64(amps.len() as u64);
212        for a in amps {
213            self.c64(*a);
214        }
215    }
216
217    fn modal(&mut self, m: &ModalBank) {
218        self.u64(m.modes.len() as u64);
219        for Mode {
220            omega,
221            tau,
222            amp,
223            phase,
224        } in &m.modes
225        {
226            self.f64(*omega);
227            self.f64(*tau);
228            self.f64(*amp);
229            self.f64(*phase);
230        }
231        match m.excite {
232            Excitation::HammerPulse { f0, t0, contact } => {
233                self.byte(0);
234                self.f64(f0);
235                self.f64(t0);
236                self.f64(contact);
237            }
238            Excitation::Impulse { t0 } => {
239                self.byte(1);
240                self.f64(t0);
241            }
242        }
243    }
244
245    fn parts(&mut self, parts: &[Part]) {
246        self.u64(parts.len() as u64);
247        for p in parts {
248            self.child(&p.body);
249        }
250    }
251
252    fn commuting(&mut self, parts: &[Part]) {
253        let [a, b] = parts else {
254            return self.parts(parts);
255        };
256        if !self.merkle {
257            return self.parts(parts);
258        }
259        let mut held = [self.part(&a.body), self.part(&b.body)];
260        either_order(&mut held);
261        self.u64(2);
262        for Hash(x, y) in held {
263            self.u64(x);
264            self.u64(y);
265        }
266    }
267
268    fn child(&mut self, f: &Body) {
269        match self.merkle {
270            true => {
271                let Hash(x, y) = self.part(f);
272                self.u64(x);
273                self.u64(y);
274            }
275            false => self.formula(f),
276        }
277    }
278
279    fn part(&mut self, f: &Body) -> Hash {
280        if let Body::Node(n) = f
281            && let Some(named) = self.node.as_mut()
282        {
283            return named(*n);
284        }
285        let mut sub = Sink {
286            hasher: ContentHasher::new(HashDomain::WrittenClosedForm),
287            node: self.node.take(),
288            bound: std::mem::take(&mut self.bound),
289            free: self.free,
290            merkle: true,
291        };
292        sub.formula(f);
293        self.node = sub.node.take();
294        self.bound = std::mem::take(&mut sub.bound);
295        sub.finish()
296    }
297
298    fn rational(&mut self, r: &Rational) {
299        self.u64(r.zeros.len() as u64);
300        for z in &r.zeros {
301            self.c64(*z);
302        }
303        self.u64(r.poles.len() as u64);
304        for p in &r.poles {
305            self.c64(*p);
306        }
307        self.c64(r.gain);
308    }
309
310    fn formula(&mut self, f: &Body) {
311        match f {
312            Body::Const(c) => {
313                self.byte(tag::CONST);
314                self.c64(*c);
315            }
316            Body::Line => self.byte(tag::LINE),
317            Body::Index(i) => match self.bound.iter().rev().position(|b| b == i) {
318                Some(depth) => {
319                    self.byte(tag::BOUND_INDEX);
320                    self.u64(depth as u64);
321                }
322                None => {
323                    assert!(self.free, "an index inside the series binding it");
324                    self.byte(tag::FREE_INDEX);
325                    self.u64(u64::from(i.0));
326                }
327            },
328            Body::Param(p) => {
329                self.byte(tag::PARAM);
330                self.u64(u64::from(p.0));
331            }
332            Body::Node(n) => {
333                self.byte(tag::NODE);
334                match self.node.as_mut().map(|named| named(*n)) {
335                    Some(held) => {
336                        self.u64(held.0);
337                        self.u64(held.1);
338                    }
339                    None => self.u64(u64::from(n.0)),
340                }
341            }
342            Body::Add(parts) => {
343                self.byte(tag::ADD);
344                self.commuting(parts);
345            }
346            Body::Mul(parts) => {
347                self.byte(tag::MUL);
348                self.commuting(parts);
349            }
350            Body::Div(a, b) => {
351                self.byte(tag::DIV);
352                self.child(&a.body);
353                self.child(&b.body);
354            }
355            Body::Pow(base, n) => {
356                self.byte(tag::POW);
357                self.child(&base.body);
358                self.i64(i64::from(*n));
359            }
360            Body::Apply(op, arg) => {
361                self.byte(tag::APPLY);
362                self.byte(unary_tag(*op));
363                self.child(&arg.body);
364            }
365            Body::Fold(op, args) => {
366                self.byte(tag::FOLD);
367                self.byte(match op {
368                    Fold::Max => 0,
369                    Fold::Min => 1,
370                    Fold::Mod => 2,
371                });
372                self.parts(args);
373            }
374            Body::Delta { at, order } => {
375                self.byte(tag::DELTA);
376                self.child(&at.body);
377                self.u64(u64::from(*order));
378            }
379            Body::Pv(at) => {
380                self.byte(tag::PV);
381                self.child(&at.body);
382            }
383            Body::Warp { at, of } => {
384                self.byte(tag::WARP);
385                self.child(&at.body);
386                self.child(&of.body);
387            }
388            Body::Shift { by, of } => {
389                self.byte(tag::SHIFT);
390                self.f64(*by);
391                self.child(&of.body);
392            }
393            Body::Deriv { order, of } => {
394                self.byte(tag::DERIV);
395                self.u64(u64::from(*order));
396                self.child(&of.body);
397            }
398            Body::Crop {
399                of,
400                l,
401                r,
402                rise,
403                fall,
404            } => {
405                self.byte(tag::CROP);
406                self.child(&of.body);
407                self.edge(*l);
408                self.edge(*r);
409                self.f64(*rise);
410                self.f64(*fall);
411            }
412            Body::Join(parts) => {
413                self.byte(tag::JOIN);
414                self.parts(parts);
415            }
416            Body::Channel(of, k) => {
417                self.byte(tag::CHANNEL);
418                self.child(&of.body);
419                self.byte(*k);
420            }
421            Body::Rational(r) => {
422                self.byte(tag::RATIONAL);
423                self.rational(r);
424            }
425            Body::Series(s) => {
426                self.byte(tag::SERIES);
427                self.series(s);
428            }
429            Body::Modal(m) => {
430                self.byte(tag::MODAL);
431                self.modal(m);
432            }
433            Body::Run(run) => {
434                self.byte(tag::RUN);
435                self.f64(run.offset);
436                self.f64(run.step);
437                self.i64(run.first);
438                self.amps(&run.amps);
439                match &run.mirror {
440                    Mirror::None => self.byte(0),
441                    Mirror::Conjugate => self.byte(1),
442                    Mirror::Held(amps) => {
443                        self.byte(2);
444                        self.amps(amps);
445                    }
446                }
447            }
448            Body::Banded(b) => {
449                self.byte(tag::BANDED);
450                self.series(&b.series);
451                for sum in [&b.slope, &b.offset] {
452                    self.u64(sum.lanes.len() as u64);
453                    sum.lanes.iter().for_each(|lane| self.lane(lane));
454                }
455                for x in [b.omega, b.reach, b.dropped_db] {
456                    self.f64(x);
457                }
458                self.i64(b.most);
459                self.i64(b.widest);
460            }
461            Body::Keyed { seed, of } => {
462                self.byte(tag::KEYED);
463                self.u64(*seed);
464                self.child(&of.body);
465            }
466        }
467    }
468
469    fn finish(self) -> Hash {
470        self.hasher.finish()
471    }
472}
473
474fn unary_tag(op: Unary) -> u8 {
475    match op {
476        Unary::Sin => 0,
477        Unary::Cos => 1,
478        Unary::Exp => 2,
479        Unary::Tanh => 3,
480        Unary::Sat => 4,
481        Unary::Abs => 5,
482        Unary::Log => 6,
483        Unary::Sqrt => 7,
484        Unary::Step => 8,
485    }
486}
487
488fn mix(mut z: u64) -> u64 {
489    z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
490    z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
491    z ^ (z >> 31)
492}
493
494/// The byte each body opens with: one per meaning, so no two bodies share a prefix.
495mod tag {
496    pub const CONST: u8 = 0x10;
497    pub const LINE: u8 = 0x11;
498    pub const BOUND_INDEX: u8 = 0x12;
499    pub const PARAM: u8 = 0x13;
500    pub const NODE: u8 = 0x14;
501    pub const ADD: u8 = 0x15;
502    pub const MUL: u8 = 0x16;
503    pub const DIV: u8 = 0x17;
504    pub const POW: u8 = 0x18;
505    pub const APPLY: u8 = 0x19;
506    pub const FOLD: u8 = 0x1a;
507    pub const DELTA: u8 = 0x1b;
508    pub const PV: u8 = 0x1c;
509    pub const SHIFT: u8 = 0x1d;
510    pub const DERIV: u8 = 0x1e;
511    pub const CROP: u8 = 0x1f;
512    pub const JOIN: u8 = 0x21;
513    pub const CHANNEL: u8 = 0x22;
514    pub const RATIONAL: u8 = 0x23;
515    pub const SERIES: u8 = 0x24;
516    pub const MODAL: u8 = 0x25;
517    pub const KEYED: u8 = 0x26;
518    pub const WARP: u8 = 0x27;
519    pub const RUN: u8 = 0x28;
520    pub const FREE_INDEX: u8 = 0x29;
521    pub const BANDED: u8 = 0x2a;
522
523    #[cfg(test)]
524    pub const ALL: [u8; 26] = [
525        CONST,
526        LINE,
527        BOUND_INDEX,
528        PARAM,
529        NODE,
530        ADD,
531        MUL,
532        DIV,
533        POW,
534        APPLY,
535        FOLD,
536        DELTA,
537        PV,
538        SHIFT,
539        DERIV,
540        CROP,
541        JOIN,
542        CHANNEL,
543        RATIONAL,
544        SERIES,
545        MODAL,
546        KEYED,
547        WARP,
548        RUN,
549        FREE_INDEX,
550        BANDED,
551    ];
552}
553
554#[cfg(test)]
555mod tests {
556    use super::tag;
557
558    /// A tag two bodies share makes the encoding ambiguous: a free index and a banded series
559    /// once both opened with 0x29.
560    #[test]
561    fn every_body_has_its_own_tag() {
562        let mut tags = tag::ALL.to_vec();
563        tags.sort_unstable();
564        tags.dedup();
565        assert_eq!(tags.len(), tag::ALL.len());
566    }
567}
sva_formula/hash.rs

sva_formula/
hash.rs
