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            // 0 is retired: a value stored under it rang only while the felt pressed.
233            Excitation::HammerPulse { f0, t0, contact } => {
234                self.byte(2);
235                self.f64(f0);
236                self.f64(t0);
237                self.f64(contact);
238            }
239            Excitation::Impulse { t0 } => {
240                self.byte(1);
241                self.f64(t0);
242            }
243        }
244    }
245
246    fn parts(&mut self, parts: &[Part]) {
247        self.u64(parts.len() as u64);
248        for p in parts {
249            self.child(&p.body);
250        }
251    }
252
253    fn commuting(&mut self, parts: &[Part]) {
254        let [a, b] = parts else {
255            return self.parts(parts);
256        };
257        if !self.merkle {
258            return self.parts(parts);
259        }
260        let mut held = [self.part(&a.body), self.part(&b.body)];
261        either_order(&mut held);
262        self.u64(2);
263        for Hash(x, y) in held {
264            self.u64(x);
265            self.u64(y);
266        }
267    }
268
269    fn child(&mut self, f: &Body) {
270        match self.merkle {
271            true => {
272                let Hash(x, y) = self.part(f);
273                self.u64(x);
274                self.u64(y);
275            }
276            false => self.formula(f),
277        }
278    }
279
280    fn part(&mut self, f: &Body) -> Hash {
281        if let Body::Node(n) = f
282            && let Some(named) = self.node.as_mut()
283        {
284            return named(*n);
285        }
286        let mut sub = Sink {
287            hasher: ContentHasher::new(HashDomain::WrittenClosedForm),
288            node: self.node.take(),
289            bound: std::mem::take(&mut self.bound),
290            free: self.free,
291            merkle: true,
292        };
293        sub.formula(f);
294        self.node = sub.node.take();
295        self.bound = std::mem::take(&mut sub.bound);
296        sub.finish()
297    }
298
299    fn rational(&mut self, r: &Rational) {
300        self.u64(r.zeros.len() as u64);
301        for z in &r.zeros {
302            self.c64(*z);
303        }
304        self.u64(r.poles.len() as u64);
305        for p in &r.poles {
306            self.c64(*p);
307        }
308        self.c64(r.gain);
309    }
310
311    fn formula(&mut self, f: &Body) {
312        match f {
313            Body::Const(c) => {
314                self.byte(tag::CONST);
315                self.c64(*c);
316            }
317            Body::Line => self.byte(tag::LINE),
318            Body::Index(i) => match self.bound.iter().rev().position(|b| b == i) {
319                Some(depth) => {
320                    self.byte(tag::BOUND_INDEX);
321                    self.u64(depth as u64);
322                }
323                None => {
324                    assert!(self.free, "an index inside the series binding it");
325                    self.byte(tag::FREE_INDEX);
326                    self.u64(u64::from(i.0));
327                }
328            },
329            Body::Param(p) => {
330                self.byte(tag::PARAM);
331                self.u64(u64::from(p.0));
332            }
333            Body::Node(n) => {
334                self.byte(tag::NODE);
335                match self.node.as_mut().map(|named| named(*n)) {
336                    Some(held) => {
337                        self.u64(held.0);
338                        self.u64(held.1);
339                    }
340                    None => self.u64(u64::from(n.0)),
341                }
342            }
343            Body::Add(parts) => {
344                self.byte(tag::ADD);
345                self.commuting(parts);
346            }
347            Body::Mul(parts) => {
348                self.byte(tag::MUL);
349                self.commuting(parts);
350            }
351            Body::Div(a, b) => {
352                self.byte(tag::DIV);
353                self.child(&a.body);
354                self.child(&b.body);
355            }
356            Body::Pow(base, n) => {
357                self.byte(tag::POW);
358                self.child(&base.body);
359                self.i64(i64::from(*n));
360            }
361            Body::Apply(op, arg) => {
362                self.byte(tag::APPLY);
363                self.byte(unary_tag(*op));
364                self.child(&arg.body);
365            }
366            Body::Fold(op, args) => {
367                self.byte(tag::FOLD);
368                self.byte(match op {
369                    Fold::Max => 0,
370                    Fold::Min => 1,
371                    Fold::Mod => 2,
372                });
373                self.parts(args);
374            }
375            Body::Delta { at, order } => {
376                self.byte(tag::DELTA);
377                self.child(&at.body);
378                self.u64(u64::from(*order));
379            }
380            Body::Pv(at) => {
381                self.byte(tag::PV);
382                self.child(&at.body);
383            }
384            Body::Warp { at, of } => {
385                self.byte(tag::WARP);
386                self.child(&at.body);
387                self.child(&of.body);
388            }
389            Body::Shift { by, of } => {
390                self.byte(tag::SHIFT);
391                self.f64(*by);
392                self.child(&of.body);
393            }
394            Body::Deriv { order, of } => {
395                self.byte(tag::DERIV);
396                self.u64(u64::from(*order));
397                self.child(&of.body);
398            }
399            Body::Crop {
400                of,
401                l,
402                r,
403                rise,
404                fall,
405            } => {
406                self.byte(tag::CROP);
407                self.child(&of.body);
408                self.edge(*l);
409                self.edge(*r);
410                self.f64(*rise);
411                self.f64(*fall);
412            }
413            Body::Join(parts) => {
414                self.byte(tag::JOIN);
415                self.parts(parts);
416            }
417            Body::Channel(of, k) => {
418                self.byte(tag::CHANNEL);
419                self.child(&of.body);
420                self.byte(*k);
421            }
422            Body::Rational(r) => {
423                self.byte(tag::RATIONAL);
424                self.rational(r);
425            }
426            Body::Series(s) => {
427                self.byte(tag::SERIES);
428                self.series(s);
429            }
430            Body::Modal(m) => {
431                self.byte(tag::MODAL);
432                self.modal(m);
433            }
434            Body::Run(run) => {
435                self.byte(tag::RUN);
436                self.f64(run.offset);
437                self.f64(run.step);
438                self.i64(run.first);
439                self.amps(&run.amps);
440                match &run.mirror {
441                    Mirror::None => self.byte(0),
442                    Mirror::Conjugate => self.byte(1),
443                    Mirror::Held(amps) => {
444                        self.byte(2);
445                        self.amps(amps);
446                    }
447                }
448            }
449            Body::Banded(b) => {
450                self.byte(tag::BANDED);
451                self.series(&b.series);
452                for sum in [&b.slope, &b.offset] {
453                    self.u64(sum.lanes.len() as u64);
454                    sum.lanes.iter().for_each(|lane| self.lane(lane));
455                }
456                for x in [b.omega, b.reach, b.dropped_db] {
457                    self.f64(x);
458                }
459                self.i64(b.most);
460                self.i64(b.widest);
461            }
462            Body::Keyed { seed, of } => {
463                self.byte(tag::KEYED);
464                self.u64(*seed);
465                self.child(&of.body);
466            }
467        }
468    }
469
470    fn finish(self) -> Hash {
471        self.hasher.finish()
472    }
473}
474
475fn unary_tag(op: Unary) -> u8 {
476    match op {
477        Unary::Sin => 0,
478        Unary::Cos => 1,
479        Unary::Exp => 2,
480        Unary::Tanh => 3,
481        Unary::Sat => 4,
482        Unary::Abs => 5,
483        Unary::Log => 6,
484        Unary::Sqrt => 7,
485        Unary::Step => 8,
486    }
487}
488
489fn mix(mut z: u64) -> u64 {
490    z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
491    z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
492    z ^ (z >> 31)
493}
494
495/// The byte each body opens with: one per meaning, so no two bodies share a prefix.
496mod tag {
497    pub const CONST: u8 = 0x10;
498    pub const LINE: u8 = 0x11;
499    pub const BOUND_INDEX: u8 = 0x12;
500    pub const PARAM: u8 = 0x13;
501    pub const NODE: u8 = 0x14;
502    pub const ADD: u8 = 0x15;
503    pub const MUL: u8 = 0x16;
504    pub const DIV: u8 = 0x17;
505    pub const POW: u8 = 0x18;
506    pub const APPLY: u8 = 0x19;
507    pub const FOLD: u8 = 0x1a;
508    pub const DELTA: u8 = 0x1b;
509    pub const PV: u8 = 0x1c;
510    pub const SHIFT: u8 = 0x1d;
511    pub const DERIV: u8 = 0x1e;
512    pub const CROP: u8 = 0x1f;
513    pub const JOIN: u8 = 0x21;
514    pub const CHANNEL: u8 = 0x22;
515    pub const RATIONAL: u8 = 0x23;
516    pub const SERIES: u8 = 0x24;
517    pub const MODAL: u8 = 0x25;
518    pub const KEYED: u8 = 0x26;
519    pub const WARP: u8 = 0x27;
520    pub const RUN: u8 = 0x28;
521    pub const FREE_INDEX: u8 = 0x29;
522    pub const BANDED: u8 = 0x2a;
523
524    #[cfg(test)]
525    pub const ALL: [u8; 26] = [
526        CONST,
527        LINE,
528        BOUND_INDEX,
529        PARAM,
530        NODE,
531        ADD,
532        MUL,
533        DIV,
534        POW,
535        APPLY,
536        FOLD,
537        DELTA,
538        PV,
539        SHIFT,
540        DERIV,
541        CROP,
542        JOIN,
543        CHANNEL,
544        RATIONAL,
545        SERIES,
546        MODAL,
547        KEYED,
548        WARP,
549        RUN,
550        FREE_INDEX,
551        BANDED,
552    ];
553}
554
555#[cfg(test)]
556mod tests {
557    use super::tag;
558
559    /// A tag two bodies share makes the encoding ambiguous: a free index and a banded series
560    /// once both opened with 0x29.
561    #[test]
562    fn every_body_has_its_own_tag() {
563        let mut tags = tag::ALL.to_vec();
564        tags.sort_unstable();
565        tags.dedup();
566        assert_eq!(tags.len(), tag::ALL.len());
567    }
568}
sva_formula/hash.rs

sva_formula/
hash.rs
