Skip to main content

pixelator_core/
encoding.rs

1/// Maps a single DNA base (as an ASCII byte) to its 2-bit code, panicking on
2/// non-ACGT input.
3///
4/// Matches the Python LUT from pixelator:
5/// A -> [0, 0], C -> [1, 0], G -> [0, 1], T -> [1, 1]
6fn base_to_2bit(base: u8) -> u64 {
7    match base {
8        b'A' => 0b00u64,
9        b'C' => 0b01u64,
10        b'G' => 0b10u64,
11        b'T' => 0b11u64,
12        _ => panic!("Unsupported DNA base: {}", base as char),
13    }
14}
15
16/// Packs a DNA sequence into a 2-bit-per-base integer in little-endian symbol
17/// order (the first base occupies the lowest bits). Panics on non-ACGT input.
18///
19/// The result is a `u64`, so sequences of up to 32 bases fit; longer sequences
20/// overflow the shift.
21pub fn encode_dna_2bit(dna: &[u8]) -> u64 {
22    dna.iter().enumerate().fold(0u64, |acc, (idx, &base)| {
23        acc | (base_to_2bit(base) << (2 * idx))
24    })
25}
26
27/// Encodes the reverse complement of a DNA sequence directly, without building
28/// an intermediate buffer. Panics on non-ACGT input.
29///
30/// In this scheme, complementing a base is a XOR with `0b11` (A<->T, C<->G),
31/// and reversing places the base at index `idx` at symbol position
32/// `n - 1 - idx`.
33pub fn encode_dna_2bit_rc(dna: &[u8]) -> u64 {
34    let n = dna.len();
35    dna.iter().enumerate().fold(0u64, |acc, (idx, &base)| {
36        acc | ((base_to_2bit(base) ^ 0b11) << (2 * (n - 1 - idx)))
37    })
38}
39
40/// Inverse of [`base_to_2bit`]: maps a 2-bit code back to an ASCII DNA base.
41fn bit_to_base(bits: u8) -> u8 {
42    match bits {
43        0b00 => b'A',
44        0b01 => b'C',
45        0b10 => b'G',
46        0b11 => b'T',
47        _ => unreachable!("2-bit mask yields at most 0b11"),
48    }
49}
50
51/// Unpacks a 2-bit-per-base integer back into `length` DNA bases, the inverse of
52/// [`encode_dna_2bit`]. Bits above `2 * length` are ignored.
53///
54/// Panics if `length` exceeds 32, the most bases a `u64` can hold.
55pub fn decode_dna_2bit(encoded: u64, length: usize) -> Vec<u8> {
56    assert!(length <= 32, "Cannot decode {length} bases from a u64");
57    (0..length)
58        .map(|idx| bit_to_base(((encoded >> (2 * idx)) & 0b11) as u8))
59        .collect()
60}
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn encode_dna_2bit_matches_base_mapping() {
68        assert_eq!(encode_dna_2bit(b"A"), 0);
69        assert_eq!(encode_dna_2bit(b"C"), 1);
70        assert_eq!(encode_dna_2bit(b"G"), 2);
71        assert_eq!(encode_dna_2bit(b"T"), 3);
72    }
73
74    #[test]
75    fn encode_dna_2bit_packs_bases_in_little_endian_symbol_order() {
76        // "ACGT" -> A(00), C(01), G(10), T(11)
77        // packed as: 00 | 01<<2 | 10<<4 | 11<<6 = 0b1110_0100 = 228
78        assert_eq!(encode_dna_2bit(b"ACGT"), 228);
79        // Empty input should encode to 0.
80        assert_eq!(encode_dna_2bit(b""), 0);
81    }
82
83    #[test]
84    #[should_panic(expected = "Unsupported DNA base")]
85    fn encode_dna_2bit_rejects_invalid_bases() {
86        let _ = encode_dna_2bit(b"AN");
87    }
88
89    #[test]
90    fn encode_dna_2bit_rc_matches_encoding_of_reverse_complement() {
91        // RC("ACTTCCTAGG") == "CCTAGGAAGT".
92        assert_eq!(
93            encode_dna_2bit_rc(b"ACTTCCTAGG"),
94            encode_dna_2bit(b"CCTAGGAAGT")
95        );
96        // RC of a single base is its complement.
97        assert_eq!(encode_dna_2bit_rc(b"A"), encode_dna_2bit(b"T"));
98        // Empty input encodes to 0.
99        assert_eq!(encode_dna_2bit_rc(b""), 0);
100    }
101
102    #[test]
103    #[should_panic(expected = "Unsupported DNA base")]
104    fn encode_dna_2bit_rc_rejects_invalid_bases() {
105        let _ = encode_dna_2bit_rc(b"AN");
106    }
107
108    #[test]
109    fn decode_dna_2bit_matches_base_mapping() {
110        assert_eq!(decode_dna_2bit(0, 1), b"A");
111        assert_eq!(decode_dna_2bit(1, 1), b"C");
112        assert_eq!(decode_dna_2bit(2, 1), b"G");
113        assert_eq!(decode_dna_2bit(3, 1), b"T");
114    }
115
116    #[test]
117    fn decode_dna_2bit_unpacks_little_endian_symbol_order() {
118        // 228 = 0b1110_0100 -> A(00), C(01), G(10), T(11)
119        assert_eq!(decode_dna_2bit(228, 4), b"ACGT");
120        assert_eq!(decode_dna_2bit(0, 0), b"");
121    }
122
123    #[test]
124    fn decode_dna_2bit_ignores_bits_above_length() {
125        // Same packed value as "ACGT", but only the first two symbols are kept.
126        assert_eq!(decode_dna_2bit(228, 2), b"AC");
127    }
128
129    #[test]
130    #[should_panic(expected = "Cannot decode 33 bases from a u64")]
131    fn decode_dna_2bit_rejects_lengths_beyond_u64() {
132        let _ = decode_dna_2bit(0, 33);
133    }
134
135    #[test]
136    fn decode_encode_round_trips() {
137        let sequences: [&[u8]; 6] = [
138            b"",
139            b"A",
140            b"ACGT",
141            b"AAAAAAAA",
142            b"TTTTTTTT",
143            b"ACGTACGTACGTACGTACGTACGTACGTACGT", // 32 bases
144        ];
145        for seq in sequences {
146            assert_eq!(decode_dna_2bit(encode_dna_2bit(seq), seq.len()), seq);
147        }
148    }
149
150    #[test]
151    fn encode_decode_round_trips_for_values() {
152        let cases: [(u64, usize); 4] = [(0, 0), (0b11, 1), (228, 4), (0x0123_4567_89AB_CDEF, 32)];
153        for (value, length) in cases {
154            let mask = if length == 0 {
155                0
156            } else {
157                u64::MAX >> (64 - 2 * length)
158            };
159            let masked = value & mask;
160            assert_eq!(encode_dna_2bit(&decode_dna_2bit(masked, length)), masked);
161        }
162    }
163
164    #[test]
165    fn decode_of_rc_encoding_is_reverse_complement() {
166        assert_eq!(
167            decode_dna_2bit(encode_dna_2bit_rc(b"ACTTCCTAGG"), 10),
168            b"CCTAGGAAGT"
169        );
170    }
171}