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::Knots { at, table } => {
463                self.byte(tag::KNOTS);
464                self.byte(u8::from(table.integral()));
465                self.child(&at.body);
466                self.u64(table.times().len() as u64);
467                for (t, v) in table.times().iter().zip(table.values()) {
468                    self.f64(*t);
469                    self.f64(*v);
470                }
471            }
472            Body::Keyed { seed, of } => {
473                self.byte(tag::KEYED);
474                self.u64(*seed);
475                self.child(&of.body);
476            }
477        }
478    }
479
480    fn finish(self) -> Hash {
481        self.hasher.finish()
482    }
483}
484
485fn unary_tag(op: Unary) -> u8 {
486    match op {
487        Unary::Sin => 0,
488        Unary::Cos => 1,
489        Unary::Exp => 2,
490        Unary::Tanh => 3,
491        Unary::Sat => 4,
492        Unary::Abs => 5,
493        Unary::Log => 6,
494        Unary::Sqrt => 7,
495        Unary::Step => 8,
496    }
497}
498
499fn mix(mut z: u64) -> u64 {
500    z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
501    z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
502    z ^ (z >> 31)
503}
504
505/// The byte each body opens with: one per meaning, so no two bodies share a prefix.
506mod tag {
507    pub const CONST: u8 = 0x10;
508    pub const LINE: u8 = 0x11;
509    pub const BOUND_INDEX: u8 = 0x12;
510    pub const PARAM: u8 = 0x13;
511    pub const NODE: u8 = 0x14;
512    pub const ADD: u8 = 0x15;
513    pub const MUL: u8 = 0x16;
514    pub const DIV: u8 = 0x17;
515    pub const POW: u8 = 0x18;
516    pub const APPLY: u8 = 0x19;
517    pub const FOLD: u8 = 0x1a;
518    pub const DELTA: u8 = 0x1b;
519    pub const PV: u8 = 0x1c;
520    pub const SHIFT: u8 = 0x1d;
521    pub const DERIV: u8 = 0x1e;
522    pub const CROP: u8 = 0x1f;
523    pub const JOIN: u8 = 0x21;
524    pub const CHANNEL: u8 = 0x22;
525    pub const RATIONAL: u8 = 0x23;
526    pub const SERIES: u8 = 0x24;
527    pub const MODAL: u8 = 0x25;
528    pub const KEYED: u8 = 0x26;
529    pub const WARP: u8 = 0x27;
530    pub const RUN: u8 = 0x28;
531    pub const FREE_INDEX: u8 = 0x29;
532    pub const BANDED: u8 = 0x2a;
533    pub const KNOTS: u8 = 0x2b;
534
535    #[cfg(test)]
536    pub const ALL: [u8; 27] = [
537        CONST,
538        LINE,
539        BOUND_INDEX,
540        PARAM,
541        NODE,
542        ADD,
543        MUL,
544        DIV,
545        POW,
546        APPLY,
547        FOLD,
548        DELTA,
549        PV,
550        SHIFT,
551        DERIV,
552        CROP,
553        JOIN,
554        CHANNEL,
555        RATIONAL,
556        SERIES,
557        MODAL,
558        KEYED,
559        WARP,
560        RUN,
561        FREE_INDEX,
562        BANDED,
563        KNOTS,
564    ];
565}
566
567#[cfg(test)]
568mod tests {
569    use super::tag;
570
571    /// A tag two bodies share makes the encoding ambiguous: a free index and a banded series
572    /// once both opened with 0x29.
573    #[test]
574    fn every_body_has_its_own_tag() {
575        let mut tags = tag::ALL.to_vec();
576        tags.sort_unstable();
577        tags.dedup();
578        assert_eq!(tags.len(), tag::ALL.len());
579    }
580}
sva_formula/hash.rs

sva_formula/
hash.rs
