1use 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
27const MODULUS: u64 = (1 << 61) - 1;
29const BASE: u64 = 0x1F35_A1C0_9E37_79B9 % MODULUS;
31const NONE: u32 = u32::MAX;
33const TRANSITION_MIN_K: usize = 33;
35
36#[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#[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#[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#[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 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#[derive(Clone, Debug, Default)]
145struct RowState {
146 hash: Vec<u64>,
147 excluded: Vec<u32>,
148 previous: Vec<u32>,
149}
150
151#[derive(Debug)]
153struct Shard {
154 start: usize,
155 positions: Vec<PositionState>,
156 scratch: RowState,
157}
158
159#[derive(Debug)]
161pub struct PositionCounts {
162 k: usize,
163 arena: Vec<u8>,
164 counts: Vec<u64>,
165 cells: Vec<(u64, u64)>,
167}
168
169impl PositionCounts {
170 #[must_use]
172 pub fn support(&self) -> u64 {
173 self.counts.iter().sum()
174 }
175
176 #[must_use]
178 pub fn distinct(&self) -> usize {
179 self.counts.len()
180 }
181
182 #[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 #[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 #[must_use]
203 pub fn count(&self, id: u32) -> u64 {
204 self.counts[id as usize]
205 }
206
207 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)] self.cells[start..end]
214 .iter()
215 .map(|&(key, count)| (key as u32, count))
216 }
217}
218
219#[derive(Debug)]
221pub struct Engine {
222 k: usize,
223 width: usize,
224 strata: usize,
225 shards: Vec<Shard>,
226}
227
228impl Engine {
229 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 #[must_use]
269 pub fn positions(&self) -> usize {
270 self.width - self.k + 1
271 }
272
273 #[must_use]
275 pub fn shard_count(&self) -> usize {
276 self.shards.len()
277 }
278
279 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 #[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
325fn 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 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 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 Ok(())
420 }
421}
422
423#[cfg(test)]
424mod tests {
425 use super::*;
426 use std::collections::BTreeMap;
427
428 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 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 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}