Skip to main content

dima_core/
engine.rs

1//! The streaming k-mer counter (D1).
2//!
3//! One pass over the normalised rows counts, for every position p (1 ≤ p ≤ L − k + 1), each
4//! distinct k-mer starting at p, and — with header metadata — the number of sequences per
5//! (k-mer, header value). Nothing proportional to sequences × positions is ever stored: memory
6//! is Σₚ (distinct k-mers × (k + 25) bytes + metadata cells × ~19 bytes) plus two batches.
7//!
8//! * **Exact interning.** Each window is hashed with a Karp–Rabin rolling hash modulo the
9//!   Mersenne prime 2⁶¹ − 1 (Karp & Rabin 1987), updated in O(1) per position, and looked up in
10//!   a per-position table whose candidates are verified byte by byte, so collisions can never
11//!   merge different k-mers. For k > 32 a transition cache maps (k-mer id at p − 1, next residue)
12//!   to the id at p, which skips the O(k) comparison for repeated transitions.
13//! * **Any k.** 1 ≤ k ≤ L; there is no packing into machine words.
14//! * **Parallelism.** Positions are split into contiguous shards processed in parallel on the
15//!   caller's rayon pool; memory does not grow with the number of threads (each shard owns its
16//!   positions), and results do not depend on the thread count or batch size (k-mer ids are
17//!   internal; outputs are sorted by count and bytes).
18
19use std::hash::{BuildHasherDefault, Hasher};
20use std::sync::atomic::{AtomicBool, Ordering};
21
22use hashbrown::{HashMap, HashTable};
23use rayon::prelude::*;
24
25use crate::error::{DimaError, Result};
26
27/// The Mersenne prime 2⁶¹ − 1.
28const MODULUS: u64 = (1 << 61) - 1;
29/// Fixed hash base (any value in [256, M) works; results never depend on it).
30const BASE: u64 = 0x1F35_A1C0_9E37_79B9 % MODULUS;
31/// Marks "no k-mer" in per-row state.
32const NONE: u32 = u32::MAX;
33/// Above this k, the transition cache is used.
34const TRANSITION_MIN_K: usize = 33;
35
36/// (a · b) mod 2⁶¹ − 1 for a, b < 2⁶¹ − 1.
37#[inline]
38const fn mulmod(a: u64, b: u64) -> u64 {
39    let x = (a as u128) * (b as u128);
40    let r = ((x as u64) & MODULUS) + ((x >> 61) as u64);
41    let r = (r & MODULUS) + (r >> 61);
42    if r >= MODULUS { r - MODULUS } else { r }
43}
44
45#[inline]
46const fn addmod(a: u64, b: u64) -> u64 {
47    let r = a + b;
48    if r >= MODULUS { r - MODULUS } else { r }
49}
50
51#[inline]
52const fn submod(a: u64, b: u64) -> u64 {
53    if a >= b { a - b } else { a + MODULUS - b }
54}
55
56/// MurmurHash3's 64-bit finaliser: spreads entropy to every bit (hash tables use both the high
57/// and the low bits).
58#[inline]
59const fn mix(mut x: u64) -> u64 {
60    x ^= x >> 33;
61    x = x.wrapping_mul(0xff51_afd7_ed55_8ccd);
62    x ^= x >> 33;
63    x = x.wrapping_mul(0xc4ce_b9fe_1a85_ec53);
64    x ^ (x >> 33)
65}
66
67/// Hasher for `u64` keys (metadata cells, transitions).
68#[derive(Clone, Copy, Debug, Default)]
69struct MixHasher(u64);
70
71impl Hasher for MixHasher {
72    fn finish(&self) -> u64 {
73        self.0
74    }
75
76    fn write(&mut self, bytes: &[u8]) {
77        for &b in bytes {
78            self.0 = mix(self.0 ^ u64::from(b));
79        }
80    }
81
82    fn write_u64(&mut self, x: u64) {
83        self.0 = mix(self.0 ^ x);
84    }
85}
86
87type MixMap<V> = HashMap<u64, V, BuildHasherDefault<MixHasher>>;
88
89/// Distinct k-mers (and metadata cells) seen at one position.
90#[derive(Debug)]
91struct PositionState {
92    arena: Vec<u8>,
93    counts: Vec<u64>,
94    hashes: Vec<u64>,
95    table: HashTable<u32>,
96    transitions: Option<MixMap<u32>>,
97    cells: Option<MixMap<u64>>,
98}
99
100impl PositionState {
101    fn new(k: usize, strata: usize) -> Self {
102        Self {
103            arena: Vec::new(),
104            counts: Vec::new(),
105            hashes: Vec::new(),
106            table: HashTable::new(),
107            transitions: (k >= TRANSITION_MIN_K).then(MixMap::default),
108            cells: (strata > 0).then(MixMap::default),
109        }
110    }
111
112    /// The id of `kmer` (with Karp–Rabin hash `kr`), inserting it if new.
113    fn intern(&mut self, kmer: &[u8], kr: u64) -> Result<u32> {
114        let h = mix(kr);
115        let k = kmer.len();
116        let Self {
117            arena,
118            counts,
119            hashes,
120            table,
121            ..
122        } = self;
123        if let Some(&id) = table.find(h, |&id| {
124            let i = id as usize;
125            hashes[i] == h && &arena[i * k..(i + 1) * k] == kmer
126        }) {
127            return Ok(id);
128        }
129        let id = u32::try_from(counts.len())
130            .ok()
131            .filter(|&id| id != NONE)
132            .ok_or(DimaError::Overflow {
133                what: "distinct k-mers at one position",
134            })?;
135        arena.extend_from_slice(kmer);
136        counts.push(0);
137        hashes.push(h);
138        table.insert_unique(h, id, |&id| hashes[id as usize]);
139        Ok(id)
140    }
141}
142
143/// Per-row rolling state of a shard.
144#[derive(Clone, Debug, Default)]
145struct RowState {
146    hash: Vec<u64>,
147    excluded: Vec<u32>,
148    previous: Vec<u32>,
149}
150
151/// A contiguous range of positions owned by one task.
152#[derive(Debug)]
153struct Shard {
154    start: usize,
155    positions: Vec<PositionState>,
156    scratch: RowState,
157}
158
159/// Counts of one position after all input was read.
160#[derive(Debug)]
161pub struct PositionCounts {
162    k: usize,
163    arena: Vec<u8>,
164    counts: Vec<u64>,
165    /// Metadata cells `((id << 32) | value id, count)`, sorted by key.
166    cells: Vec<(u64, u64)>,
167}
168
169impl PositionCounts {
170    /// Support *N*: sequences with a valid k-mer here.
171    #[must_use]
172    pub fn support(&self) -> u64 {
173        self.counts.iter().sum()
174    }
175
176    /// Number of distinct k-mers.
177    #[must_use]
178    pub fn distinct(&self) -> usize {
179        self.counts.len()
180    }
181
182    /// Ids ordered by count (descending), then k-mer bytes (ascending): the output order.
183    #[must_use]
184    pub fn ordered_ids(&self) -> Vec<u32> {
185        let mut ids: Vec<u32> = (0..self.counts.len() as u32).collect();
186        ids.sort_unstable_by(|&a, &b| {
187            self.counts[b as usize]
188                .cmp(&self.counts[a as usize])
189                .then_with(|| self.kmer(a).cmp(self.kmer(b)))
190        });
191        ids
192    }
193
194    /// The k-mer of an id.
195    #[must_use]
196    pub fn kmer(&self, id: u32) -> &[u8] {
197        let i = id as usize;
198        &self.arena[i * self.k..(i + 1) * self.k]
199    }
200
201    /// The count of an id.
202    #[must_use]
203    pub fn count(&self, id: u32) -> u64 {
204        self.counts[id as usize]
205    }
206
207    /// `(value id, count)` metadata cells of a k-mer, ascending by value id.
208    pub fn cells(&self, id: u32) -> impl Iterator<Item = (u32, u64)> + '_ {
209        let lo = u64::from(id) << 32;
210        let start = self.cells.partition_point(|&(key, _)| key < lo);
211        let end = self.cells.partition_point(|&(key, _)| key < lo + (1 << 32));
212        #[allow(clippy::cast_possible_truncation)] // The low 32 bits are the value id.
213        self.cells[start..end]
214            .iter()
215            .map(|&(key, count)| (key as u32, count))
216    }
217}
218
219/// The streaming counter.
220#[derive(Debug)]
221pub struct Engine {
222    k: usize,
223    width: usize,
224    strata: usize,
225    shards: Vec<Shard>,
226}
227
228impl Engine {
229    /// A counter for alignments of `width` columns, k-mers of length `k`, `strata` stratified
230    /// header fields, split into shards for `threads` workers.
231    ///
232    /// # Errors
233    /// A usage error when k is 0 or longer than the alignment.
234    pub fn new(width: usize, k: usize, strata: usize, threads: usize) -> Result<Self> {
235        if k == 0 {
236            return Err(DimaError::usage("k-mer length must be at least 1"));
237        }
238        if k > width {
239            return Err(DimaError::usage(format!(
240                "k-mer length {k} is longer than the alignment ({width} columns)"
241            ))
242            .with_hint(format!("choose a k-mer length between 1 and {width}")));
243        }
244        let positions = width - k + 1;
245        let shard_count = positions.min(4 * threads.max(1)).min(width / k).max(1);
246        let base = positions / shard_count;
247        let extra = positions % shard_count;
248        let mut shards = Vec::with_capacity(shard_count);
249        let mut start = 0;
250        for s in 0..shard_count {
251            let len = base + usize::from(s < extra);
252            shards.push(Shard {
253                start,
254                positions: (0..len).map(|_| PositionState::new(k, strata)).collect(),
255                scratch: RowState::default(),
256            });
257            start += len;
258        }
259        Ok(Self {
260            k,
261            width,
262            strata,
263            shards,
264        })
265    }
266
267    /// Number of positions (L − k + 1).
268    #[must_use]
269    pub fn positions(&self) -> usize {
270        self.width - self.k + 1
271    }
272
273    /// Number of shards (exposed for diagnostics and tests).
274    #[must_use]
275    pub fn shard_count(&self) -> usize {
276        self.shards.len()
277    }
278
279    /// Counts a batch: `rows` holds `records × width` canonical bytes (0 = excluded column);
280    /// `values` holds `records × strata` header value ids (empty without metadata). Runs on the
281    /// current rayon pool.
282    ///
283    /// # Errors
284    /// [`DimaError::Cancelled`] or [`DimaError::Overflow`].
285    pub fn add_batch(
286        &mut self,
287        rows: &[u8],
288        records: usize,
289        values: &[u32],
290        cancel: &AtomicBool,
291    ) -> Result<()> {
292        debug_assert_eq!(rows.len(), records * self.width);
293        debug_assert!(self.strata == 0 || values.len() == records * self.strata);
294        if records == 0 {
295            return Ok(());
296        }
297        let (k, width, strata) = (self.k, self.width, self.strata);
298        self.shards
299            .par_iter_mut()
300            .try_for_each(|shard| shard.count(rows, records, width, k, values, strata, cancel))
301    }
302
303    /// Finishes counting and returns the counts of every position, in position order.
304    #[must_use]
305    pub fn finish(self) -> Vec<PositionCounts> {
306        let k = self.k;
307        self.shards
308            .into_iter()
309            .flat_map(|s| s.positions)
310            .map(|p| {
311                let mut cells: Vec<(u64, u64)> =
312                    p.cells.map(|c| c.into_iter().collect()).unwrap_or_default();
313                cells.sort_unstable_by_key(|&(key, _)| key);
314                PositionCounts {
315                    k,
316                    arena: p.arena,
317                    counts: p.counts,
318                    cells,
319                }
320            })
321            .collect()
322    }
323}
324
325/// B^(k−1) mod M.
326fn base_power(k: usize) -> u64 {
327    let mut p = 1u64;
328    for _ in 1..k {
329        p = mulmod(p, BASE);
330    }
331    p
332}
333
334impl Shard {
335    #[allow(clippy::too_many_arguments)]
336    fn count(
337        &mut self,
338        rows: &[u8],
339        records: usize,
340        width: usize,
341        k: usize,
342        values: &[u32],
343        strata: usize,
344        cancel: &AtomicBool,
345    ) -> Result<()> {
346        if self.positions.is_empty() {
347            return Ok(());
348        }
349        if cancel.load(Ordering::Relaxed) {
350            return Err(DimaError::Cancelled);
351        }
352        let top = base_power(k);
353        let s = self.start;
354        let st = &mut self.scratch;
355        st.hash.clear();
356        st.excluded.clear();
357        st.previous.clear();
358        st.previous.resize(records, NONE);
359        // Initial windows [s, s + k) of every row.
360        for r in 0..records {
361            let w = &rows[r * width + s..r * width + s + k];
362            let mut h = 0u64;
363            let mut ex = 0u32;
364            for &c in w {
365                h = addmod(mulmod(h, BASE), u64::from(c));
366                ex += u32::from(c == 0);
367            }
368            st.hash.push(h);
369            st.excluded.push(ex);
370        }
371        for (offset, pos) in self.positions.iter_mut().enumerate() {
372            let p = s + offset;
373            if offset > 0 && offset % 64 == 0 && cancel.load(Ordering::Relaxed) {
374                return Err(DimaError::Cancelled);
375            }
376            for r in 0..records {
377                let row = &rows[r * width..(r + 1) * width];
378                if offset > 0 {
379                    let out = row[p - 1];
380                    let inn = row[p + k - 1];
381                    st.hash[r] = addmod(
382                        mulmod(submod(st.hash[r], mulmod(u64::from(out), top)), BASE),
383                        u64::from(inn),
384                    );
385                    st.excluded[r] = st.excluded[r] - u32::from(out == 0) + u32::from(inn == 0);
386                }
387                if st.excluded[r] != 0 {
388                    st.previous[r] = NONE;
389                    continue;
390                }
391                let kmer = &row[p..p + k];
392                let prev = st.previous[r];
393                let id = match (&mut pos.transitions, prev) {
394                    (Some(tr), prev) if prev != NONE => {
395                        let key = (u64::from(prev) << 8) | u64::from(kmer[k - 1]);
396                        if let Some(&id) = tr.get(&key) {
397                            id
398                        } else {
399                            let id = pos.intern(kmer, st.hash[r])?;
400                            pos.transitions.as_mut().map(|t| t.insert(key, id));
401                            id
402                        }
403                    }
404                    _ => pos.intern(kmer, st.hash[r])?,
405                };
406                // Transitions at p key on the id at p − 1; record this one for p + 1.
407                st.previous[r] = id;
408                pos.counts[id as usize] += 1;
409                if let Some(cells) = &mut pos.cells {
410                    for &v in &values[r * strata..(r + 1) * strata] {
411                        *cells
412                            .entry((u64::from(id) << 32) | u64::from(v))
413                            .or_insert(0) += 1;
414                    }
415                }
416            }
417        }
418        // Keep transition keys valid across batches: a row's previous id refers to this batch only.
419        Ok(())
420    }
421}
422
423#[cfg(test)]
424mod tests {
425    use super::*;
426    use std::collections::BTreeMap;
427
428    /// Naive reference: per position, a map from k-mer to (count, metadata cells).
429    type Naive = Vec<BTreeMap<Vec<u8>, (u64, BTreeMap<u32, u64>)>>;
430
431    fn naive(rows: &[Vec<u8>], k: usize, values: &[Vec<u32>]) -> Naive {
432        let width = rows[0].len();
433        let mut out: Naive = vec![BTreeMap::new(); width - k + 1];
434        for (r, row) in rows.iter().enumerate() {
435            for p in 0..=width - k {
436                let w = &row[p..p + k];
437                if w.contains(&0) {
438                    continue;
439                }
440                let e = out[p].entry(w.to_vec()).or_default();
441                e.0 += 1;
442                for &v in values.get(r).map(Vec::as_slice).unwrap_or(&[]) {
443                    *e.1.entry(v).or_default() += 1;
444                }
445            }
446        }
447        out
448    }
449
450    fn run(
451        rows: &[Vec<u8>],
452        k: usize,
453        values: &[Vec<u32>],
454        threads: usize,
455        batch: usize,
456    ) -> Vec<PositionCounts> {
457        let width = rows[0].len();
458        let strata = values.first().map_or(0, Vec::len);
459        let mut e = Engine::new(width, k, strata, threads).unwrap();
460        let cancel = AtomicBool::new(false);
461        for (chunk, vals) in rows
462            .chunks(batch)
463            .zip(values_chunks(values, batch, rows.len()))
464        {
465            let flat: Vec<u8> = chunk.concat();
466            let v: Vec<u32> = vals.concat();
467            e.add_batch(&flat, chunk.len(), &v, &cancel).unwrap();
468        }
469        e.finish()
470    }
471
472    fn values_chunks(values: &[Vec<u32>], batch: usize, n: usize) -> Vec<&[Vec<u32>]> {
473        if values.is_empty() {
474            vec![&[][..]; n.div_ceil(batch)]
475        } else {
476            values.chunks(batch).collect()
477        }
478    }
479
480    fn check(rows: &[Vec<u8>], k: usize, values: &[Vec<u32>]) {
481        let want = naive(rows, k, values);
482        for threads in [1, 2, 7] {
483            for batch in [1, 3, rows.len()] {
484                let got = run(rows, k, values, threads, batch);
485                assert_eq!(got.len(), want.len());
486                for (p, (g, w)) in got.iter().zip(&want).enumerate() {
487                    let mut gm: BTreeMap<Vec<u8>, (u64, BTreeMap<u32, u64>)> = BTreeMap::new();
488                    for id in g.ordered_ids() {
489                        let cells = g.cells(id).collect();
490                        gm.insert(g.kmer(id).to_vec(), (g.count(id), cells));
491                    }
492                    assert_eq!(&gm, w, "k={k} threads={threads} batch={batch} position={p}");
493                    assert_eq!(g.support(), w.values().map(|v| v.0).sum::<u64>());
494                }
495            }
496        }
497    }
498
499    fn rows_from(seqs: &[&str]) -> Vec<Vec<u8>> {
500        seqs.iter()
501            .map(|s| s.bytes().map(|b| if b == b'-' { 0 } else { b }).collect())
502            .collect()
503    }
504
505    #[test]
506    fn matches_naive_counter() {
507        let rows = rows_from(&[
508            "ACGTACGTAC",
509            "ACGTTCGTAC",
510            "AC-TACGTAC",
511            "TTTTTTTTTT",
512            "ACGTACGTAC",
513            "-CGTACGTA-",
514        ]);
515        for k in 1..=10 {
516            check(&rows, k, &[]);
517        }
518        let values = vec![
519            vec![0, 2],
520            vec![1, 2],
521            vec![0, 3],
522            vec![1, 3],
523            vec![0, 2],
524            vec![1, 2],
525        ];
526        for k in [1, 3, 10] {
527            check(&rows, k, &values);
528        }
529    }
530
531    #[test]
532    fn long_kmers_use_transitions() {
533        // k > 32 exercises the transition cache, including after an excluded column.
534        let base = "ACGT".repeat(25);
535        let mut v = base.clone().into_bytes();
536        v[50] = b'-';
537        let mut w = base.clone().into_bytes();
538        w[70] = b'T';
539        let seqs = [
540            base.as_str(),
541            std::str::from_utf8(&v).unwrap(),
542            std::str::from_utf8(&w).unwrap(),
543            base.as_str(),
544        ];
545        let rows = rows_from(&seqs);
546        for k in [33, 40, 100] {
547            check(&rows, k, &[]);
548        }
549    }
550
551    #[test]
552    fn ordering_and_cells() {
553        let rows = rows_from(&["AAA", "CCC", "CCC", "AAA", "GGG"]);
554        let values = vec![vec![5], vec![6], vec![6], vec![7], vec![5]];
555        let got = run(&rows, 3, &values, 1, 5);
556        let p = &got[0];
557        let ids = p.ordered_ids();
558        let kmers: Vec<&[u8]> = ids.iter().map(|&i| p.kmer(i)).collect();
559        assert_eq!(kmers, [&b"AAA"[..], b"CCC", b"GGG"], "ties by bytes");
560        assert_eq!(p.cells(ids[0]).collect::<Vec<_>>(), [(5, 1), (7, 1)]);
561        assert_eq!(p.cells(ids[1]).collect::<Vec<_>>(), [(6, 2)]);
562        assert_eq!(p.distinct(), 3);
563    }
564
565    #[test]
566    fn hash_arithmetic() {
567        assert_eq!(mulmod(MODULUS - 1, MODULUS - 1), 1);
568        assert_eq!(submod(0, 1), MODULUS - 1);
569        assert_eq!(addmod(MODULUS - 1, 1), 0);
570        // Rolling equals direct hashing.
571        let s = b"ACGTTGCAAGT";
572        let k = 4;
573        let direct = |w: &[u8]| {
574            w.iter()
575                .fold(0u64, |h, &c| addmod(mulmod(h, BASE), u64::from(c)))
576        };
577        let top = base_power(k);
578        let mut h = direct(&s[..k]);
579        for p in 1..=s.len() - k {
580            h = addmod(
581                mulmod(submod(h, mulmod(u64::from(s[p - 1]), top)), BASE),
582                u64::from(s[p + k - 1]),
583            );
584            assert_eq!(h, direct(&s[p..p + k]));
585        }
586    }
587
588    #[test]
589    fn engine_validation_and_sharding() {
590        assert_eq!(
591            Engine::new(5, 6, 0, 1).unwrap_err().class(),
592            crate::error::ExitClass::Usage
593        );
594        assert_eq!(
595            Engine::new(5, 0, 0, 1).unwrap_err().class(),
596            crate::error::ExitClass::Usage
597        );
598        let e = Engine::new(1353, 9, 0, 8).unwrap();
599        assert_eq!(e.positions(), 1345);
600        assert_eq!(e.shard_count(), 32);
601        let e = Engine::new(10, 9, 0, 8).unwrap();
602        assert_eq!(e.shard_count(), 1, "shards are at least k long");
603        let mut e = Engine::new(4, 2, 0, 1).unwrap();
604        let cancel = AtomicBool::new(true);
605        assert!(matches!(
606            e.add_batch(b"ACGT", 1, &[], &cancel),
607            Err(DimaError::Cancelled)
608        ));
609    }
610}