ondas 2.1.0

Read-only, format-independent waveform analysis library
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
//! A bounded index of validated VCD record positions.
//!
//! The index keeps only source positions of records that opening already
//! validated. It stores no values, no source bytes and no query state. A
//! representation that does not fit the private budgets is dropped and the
//! chronological paths answer instead.

use std::mem::size_of;

pub(super) const ENTRY_BYTES: usize = size_of::<Entry>();
pub(super) const LIST_BYTES: usize = size_of::<Vec<Entry>>();
const TICK_BYTES: usize = size_of::<(u32, u64)>();
const BLOCK_BYTES: usize = size_of::<(u64, u64)>();
const RECORD_BYTES: usize = size_of::<u32>() + size_of::<u64>();

/// The validated time and source offset of one record token.
#[derive(Clone, Copy)]
pub(super) struct Entry {
    pub(super) time: u64,
    pub(super) offset: u64,
}

/// Transient records of one opening walk, in source order.
///
/// A record keeps its signal and offset; the tick table turns consecutive
/// records with equal time into one `(first record, time)` pair. A record costs
/// 12 bytes and a recorded tick or dump block costs 16 bytes. The budget covers
/// the actual capacities, not the current lengths, so an input with a new tick
/// on every record or with many blocks cannot overrun it.
#[derive(Default)]
pub(super) struct Builder {
    signals: Vec<u32>,
    offsets: Vec<u64>,
    ticks: Vec<(u32, u64)>,
    blocks: Vec<(u64, u64)>,
    /// Largest raw payload plus identifier token seen in the opening walk.
    max_token: u64,
    time: u64,
    allocated: usize,
    limit: usize,
    overflow: bool,
}

impl Builder {
    pub(super) fn new(_signals: usize, limit: usize) -> Self {
        Self {
            limit,
            ..Self::default()
        }
    }

    pub(super) fn record(&mut self, signal: usize, time: u64, offset: u64, token: (u64, u64)) {
        if self.overflow {
            return;
        }
        let Ok(signal) = u32::try_from(signal) else {
            self.abandon();
            return;
        };
        self.max_token = self
            .max_token
            .max(token.0.saturating_add(token.1).saturating_add(2));
        if self.time != time || self.signals.is_empty() {
            let Ok(next) = u32::try_from(self.offsets.len()) else {
                self.abandon();
                return;
            };
            if !self.grow_ticks() {
                return;
            }
            self.ticks.push((next, time));
            self.time = time;
        }
        if !self.grow_records() {
            return;
        }
        self.signals.push(signal);
        self.offsets.push(offset);
    }

    /// Records one dump block, whose records are snapshots rather than occurrences.
    pub(super) fn block(&mut self, start: u64, end: u64) {
        if self.overflow {
            return;
        }
        if self.blocks.len() == self.blocks.capacity() {
            let capacity = self.blocks.capacity().max(16).saturating_mul(2);
            let bytes = (capacity - self.blocks.capacity()).saturating_mul(BLOCK_BYTES);
            if self.exceeds(bytes)
                || self
                    .blocks
                    .try_reserve_exact(capacity - self.blocks.len())
                    .is_err()
            {
                self.abandon();
                return;
            }
            self.allocated += bytes;
        }
        self.blocks.push((start, end));
    }

    fn grow_records(&mut self) -> bool {
        if self.signals.len() < self.signals.capacity() {
            return true;
        }
        let capacity = self.signals.capacity().max(1024).saturating_mul(2);
        let extra = capacity - self.signals.len();
        let bytes = extra.saturating_mul(RECORD_BYTES);
        if self.exceeds(bytes)
            || self.signals.try_reserve_exact(extra).is_err()
            || self.offsets.try_reserve_exact(extra).is_err()
        {
            self.abandon();
            return false;
        }
        self.allocated += bytes;
        true
    }

    fn grow_ticks(&mut self) -> bool {
        if self.ticks.len() < self.ticks.capacity() {
            return true;
        }
        let capacity = self.ticks.capacity().max(64).saturating_mul(2);
        let extra = capacity - self.ticks.len();
        let bytes = extra.saturating_mul(TICK_BYTES);
        if self.exceeds(bytes) || self.ticks.try_reserve_exact(extra).is_err() {
            self.abandon();
            return false;
        }
        self.allocated += bytes;
        true
    }

    fn exceeds(&self, bytes: usize) -> bool {
        self.allocated.saturating_add(bytes) > self.limit
    }

    fn abandon(&mut self) {
        self.overflow = true;
        self.signals = Vec::new();
        self.offsets = Vec::new();
        self.ticks = Vec::new();
        self.blocks = Vec::new();
        self.allocated = 0;
    }

    fn into_parts(self) -> Option<Part> {
        if self.overflow {
            return None;
        }
        Some(Part {
            signals: self.signals,
            offsets: self.offsets,
            ticks: self.ticks,
            blocks: self.blocks,
            max_token: self.max_token,
        })
    }
}

struct Part {
    signals: Vec<u32>,
    offsets: Vec<u64>,
    ticks: Vec<(u32, u64)>,
    blocks: Vec<(u64, u64)>,
    max_token: u64,
}

impl Part {
    fn held(&self) -> usize {
        self.signals.capacity() * size_of::<u32>()
            + self.offsets.capacity() * size_of::<u64>()
            + self.ticks.capacity() * TICK_BYTES
            + self.blocks.capacity() * BLOCK_BYTES
    }
}

/// A complete, immutable position index for one opened source.
pub(super) struct Index {
    signals: Vec<Vec<Entry>>,
    blocks: Vec<(u64, u64)>,
    max_token: u64,
}

impl Index {
    /// Merges per-chunk records in source order.
    ///
    /// The representation is dropped when any chunk overflowed its share, when
    /// a count or the retained size does not fit, when the peak of the merge
    /// would exceed the combined budget, or when an allocation fails. Every
    /// retaining allocation is fallible.
    pub(super) fn build(
        parts: impl IntoIterator<Item = Builder>,
        signals: usize,
        limit: usize,
        peak: usize,
    ) -> Option<Self> {
        let parts = parts
            .into_iter()
            .map(Builder::into_parts)
            .collect::<Option<Vec<_>>>()?;
        // Check the bounds that do not need records before touching one counter
        // per declaration. An impossible list table or peak refuses here.
        let list_floor = signals.checked_mul(LIST_BYTES)?;
        let counts_bytes = signals.checked_mul(size_of::<u32>())?;
        let mut held = 0_usize;
        for part in &parts {
            held = held.checked_add(part.held())?;
        }
        if list_floor > limit || held.checked_add(counts_bytes)? > peak {
            return None;
        }
        let mut counts = Vec::new();
        counts.try_reserve_exact(signals).ok()?;
        counts.resize(signals, 0_u32);
        let mut max_token = 0_u64;
        let mut blocks_len = 0_usize;
        for part in &parts {
            blocks_len = blocks_len.checked_add(part.blocks.len())?;
            max_token = max_token.max(part.max_token);
            for &signal in &part.signals {
                let count = counts.get_mut(signal as usize)?;
                *count = count.checked_add(1)?;
            }
        }
        let entries = counts
            .iter()
            .try_fold(0_usize, |total, &count| total.checked_add(count as usize))?;
        let retained = entries
            .checked_mul(ENTRY_BYTES)?
            .checked_add(list_floor)?
            .checked_add(blocks_len.checked_mul(BLOCK_BYTES)?)?;
        if retained > limit || held.checked_add(retained)?.checked_add(counts_bytes)? > peak {
            return None;
        }
        let mut lists = Vec::new();
        lists.try_reserve_exact(signals).ok()?;
        for &count in &counts {
            let mut list = Vec::new();
            list.try_reserve_exact(count as usize).ok()?;
            lists.push(list);
        }
        let mut blocks = Vec::new();
        blocks.try_reserve_exact(blocks_len).ok()?;
        for part in parts {
            let mut tick = 0_usize;
            for (record, (&signal, &offset)) in part.signals.iter().zip(&part.offsets).enumerate() {
                while tick + 1 < part.ticks.len() && part.ticks[tick + 1].0 as usize <= record {
                    tick += 1;
                }
                lists[signal as usize].push(Entry {
                    time: part.ticks[tick].1,
                    offset,
                });
            }
            blocks.extend(part.blocks);
        }
        Some(Self {
            signals: lists,
            blocks,
            max_token,
        })
    }

    pub(super) fn entries(&self, signal: usize) -> &[Entry] {
        &self.signals[signal]
    }

    /// Largest raw payload plus identifier token seen during opening validation.
    ///
    /// This is the payload token plus the identifier; leading whitespace is
    /// skipped without retention and is not part of the bound. The value is
    /// global to the source, so one large record makes the traversal estimate
    /// conservative for every selection.
    pub(super) fn max_token(&self) -> u64 {
        self.max_token
    }

    /// Returns the index of the last recorded entry at or before `time`.
    pub(super) fn last_at_or_before(&self, signal: usize, time: u64) -> Option<usize> {
        self.entries(signal)
            .partition_point(|entry| entry.time <= time)
            .checked_sub(1)
    }

    /// Returns the index of the first recorded entry after `time`.
    pub(super) fn first_after(&self, signal: usize, time: u64) -> usize {
        self.entries(signal)
            .partition_point(|entry| entry.time <= time)
    }

    /// Returns whether a source offset lies inside a dump block.
    pub(super) fn in_block(&self, offset: u64) -> bool {
        let after = self.blocks.partition_point(|&(start, _)| start <= offset);
        after
            .checked_sub(1)
            .is_some_and(|index| offset < self.blocks[index].1)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn part(signals: usize, records: &[(u32, u64, u64)], blocks: &[(u64, u64)]) -> Builder {
        let mut builder = Builder::new(signals, usize::MAX / 2);
        for &(signal, time, offset) in records {
            builder.record(signal as usize, time, offset, (8, 2));
        }
        for &(start, end) in blocks {
            builder.block(start, end);
        }
        builder
    }

    #[test]
    fn merge_keeps_source_order_per_signal_and_tick_context() {
        let first = part(2, &[(1, 2, 10), (0, 2, 11), (1, 5, 30)], &[(4, 8)]);
        let second = part(2, &[(1, 5, 31), (0, 9, 50)], &[]);
        let index = Index::build([first, second], 2, usize::MAX, usize::MAX).unwrap();
        let one = index.entries(1);
        assert_eq!(
            one.iter()
                .map(|entry| (entry.time, entry.offset))
                .collect::<Vec<_>>(),
            [(2, 10), (5, 30), (5, 31)]
        );
        assert_eq!(index.last_at_or_before(1, 4), Some(0));
        assert_eq!(index.last_at_or_before(1, 5), Some(2));
        assert_eq!(index.first_after(1, 5), 3);
        assert!(index.in_block(5));
        assert!(!index.in_block(8));
        assert_eq!(index.max_token(), 8 + 2 + 2);
    }

    #[test]
    fn record_budget_counts_actual_capacities() {
        let mut builder = Builder::new(1, 4 * RECORD_BYTES);
        for offset in 0..1024 {
            builder.record(0, 0, offset, (8, 2));
        }
        assert!(Index::build([builder], 1, usize::MAX, usize::MAX).is_none());
        let exact = part(1, &[(0, 1, 4)], &[]);
        assert!(Index::build([exact], 1, 0, usize::MAX).is_none());
        // Retained entries fit, while the transient minimum capacities only
        // count against the peak.
        assert!(Index::build([part(1, &[(0, 1, 4)], &[])], 1, 1024, usize::MAX).is_some());
    }

    #[test]
    fn tick_and_block_budgets_are_bounded() {
        // The same 1024 records in one tick fit the records and one tick entry.
        let mut same_tick = Builder::new(1, 32 * 1024);
        for offset in 0..1024 {
            same_tick.record(0, 7, offset, (8, 2));
        }
        assert!(!same_tick.overflow);
        assert_eq!(same_tick.signals.len(), 1024);
        assert_eq!(same_tick.ticks.len(), 1);
        assert!(Index::build([same_tick], 1, usize::MAX, usize::MAX).is_some());
        // One tick per record keeps the same record capacities but must exhaust
        // the tick budget, which an implementation that ignored ticks would not.
        let mut ticks = Builder::new(1, 32 * 1024);
        for tick in 0..1024 {
            ticks.record(0, tick, tick, (8, 2));
        }
        assert!(ticks.overflow);
        assert!(Index::build([ticks], 1, usize::MAX, usize::MAX).is_none());
        // An empty block on every tick is also retained state.
        let mut blocks = Builder::new(1, 8 * BLOCK_BYTES);
        for tick in 0..1024 {
            blocks.block(tick, tick + 1);
        }
        assert!(Index::build([blocks], 1, usize::MAX, usize::MAX).is_none());
        // Retained state stays available inside a budget that covers it.
        let mut small = Builder::new(1, 64 * 1024);
        for tick in 0..4 {
            small.record(0, tick, tick, (8, 2));
            small.block(tick, tick + 1);
        }
        assert!(Index::build([small], 1, 4096, usize::MAX).is_some());
    }

    #[test]
    fn impossible_lower_bounds_refuse_before_counting() {
        // The per-signal list table alone exceeds the retained limit.
        let builder = part(1024, &[], &[]);
        assert!(Index::build([builder], 1024, 1024 * LIST_BYTES - 1, usize::MAX).is_none());
        // The transient parts plus the counters exceed the merge peak.
        let builder = part(1024, &[(0, 1, 4)], &[]);
        let held = builder.into_parts().unwrap().held();
        assert!(
            Index::build(
                [part(1024, &[(0, 1, 4)], &[])],
                1024,
                usize::MAX,
                held + 1024 * 4 - 1
            )
            .is_none()
        );
    }

    #[test]
    fn build_peak_covers_parts_counts_and_retained_lists() {
        let builder = part(3, &[(0, 1, 4), (1, 1, 5), (0, 2, 6)], &[]);
        let index = Index::build([builder], 3, usize::MAX, usize::MAX).unwrap();
        assert_eq!(index.entries(0).len(), 2);
        assert_eq!(index.entries(1).len(), 1);
        assert!(index.entries(2).is_empty());
        let builder = part(3, &[(0, 1, 4), (1, 1, 5), (0, 2, 6)], &[]);
        assert!(Index::build([builder], 3, usize::MAX, 1).is_none());
    }
}