use crate::constants::ALPHABET_SIZE;
use crate::error::Error;
pub fn forward(block: &[u8], output: &mut [u8], indices: &mut [u32]) -> Result<u32, Error> {
let n = block.len();
if n == 0 {
return Ok(0);
}
if indices.len() < n || output.len() < n {
return Err(Error::OutputOverflow);
}
for i in 0..n {
indices[i] = i as u32;
}
shellsort_rotations(block, &mut indices[..n]);
let mut primary_index = 0u32;
for i in 0..n {
let idx = indices[i] as usize;
if idx == 0 {
primary_index = i as u32;
}
output[i] = block[(idx + n - 1) % n];
}
Ok(primary_index)
}
fn shellsort_rotations(block: &[u8], indices: &mut [u32]) {
let n = indices.len();
if n <= 1 {
return;
}
const GAPS: [usize; 16] = [
510_097, 227_011, 100_894, 44_842, 19_930, 8_858,
3_937, 1_750, 701, 301, 132, 57, 23, 10, 4, 1,
];
for &gap in &GAPS {
if gap >= n {
continue;
}
for i in gap..n {
let tmp = indices[i];
let mut j = i;
while j >= gap && compare_rotations(block, indices[j - gap], tmp) > 0 {
indices[j] = indices[j - gap];
j -= gap;
}
indices[j] = tmp;
}
}
}
#[inline]
fn compare_rotations(block: &[u8], a: u32, b: u32) -> i32 {
if a == b {
return 0;
}
let n = block.len();
let mut ai = a as usize;
let mut bi = b as usize;
for _ in 0..n {
let ca = block[ai];
let cb = block[bi];
if ca != cb {
return (ca as i32) - (cb as i32);
}
ai += 1;
if ai >= n {
ai = 0;
}
bi += 1;
if bi >= n {
bi = 0;
}
}
0
}
pub fn inverse(
bwt_data: &[u8],
primary_index: u32,
output: &mut [u8],
t_vec: &mut [u32],
) -> Result<(), Error> {
let n = bwt_data.len();
if primary_index as usize >= n {
return Err(Error::BadBwtIndex);
}
if output.len() < n || t_vec.len() < n {
return Err(Error::OutputOverflow);
}
let mut freq = [0u32; ALPHABET_SIZE];
for &b in &bwt_data[..n] {
freq[b as usize] += 1;
}
let mut cumul = [0u32; ALPHABET_SIZE];
let mut sum = 0u32;
for i in 0..ALPHABET_SIZE {
cumul[i] = sum;
sum += freq[i];
}
let mut count = [0u32; ALPHABET_SIZE];
for i in 0..n {
let ch = bwt_data[i] as usize;
t_vec[i] = cumul[ch] + count[ch];
count[ch] += 1;
}
let mut idx = primary_index as usize;
for i in (0..n).rev() {
output[i] = bwt_data[idx];
idx = t_vec[idx] as usize;
}
Ok(())
}
pub fn inverse_small(
bwt_data: &[u8],
primary_index: u32,
output: &mut [u8],
) -> Result<(), Error> {
let n = bwt_data.len();
if n == 0 {
return Ok(());
}
if primary_index as usize >= n {
return Err(Error::BadBwtIndex);
}
if output.len() < n {
return Err(Error::OutputOverflow);
}
let mut freq = [0u32; ALPHABET_SIZE];
for &b in &bwt_data[..n] {
freq[b as usize] += 1;
}
let mut cumul = [0u32; ALPHABET_SIZE + 1];
let mut sum = 0u32;
for i in 0..ALPHABET_SIZE {
cumul[i] = sum;
sum += freq[i];
}
cumul[ALPHABET_SIZE] = sum;
let mut idx = primary_index as usize;
for i in (0..n).rev() {
let ch = bwt_data[idx];
output[i] = ch;
let mut rank = 0u32;
for j in 0..idx {
if bwt_data[j] == ch {
rank += 1;
}
}
idx = cumul[ch as usize] as usize + rank as usize;
}
Ok(())
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn roundtrip_simple() {
let input = b"banana";
let n = input.len();
let _output = [0u8; 16];
let mut indices = [0u32; 16];
let mut bwt_out = [0u8; 16];
let primary = forward(input, &mut bwt_out, &mut indices).unwrap();
let mut restored = [0u8; 16];
let mut t_vec = [0u32; 16];
inverse(&bwt_out[..n], primary, &mut restored, &mut t_vec).unwrap();
assert_eq!(&restored[..n], b"banana");
}
#[test]
fn roundtrip_small_inverse() {
let input = b"abracadabra";
let n = input.len();
let mut bwt_out = [0u8; 16];
let mut indices = [0u32; 16];
let primary = forward(input, &mut bwt_out, &mut indices).unwrap();
let mut restored = [0u8; 16];
inverse_small(&bwt_out[..n], primary, &mut restored).unwrap();
assert_eq!(&restored[..n], b"abracadabra");
}
#[test]
fn roundtrip_repeated() {
let input = b"AAAAAAA";
let n = input.len();
let mut bwt_out = [0u8; 16];
let mut indices = [0u32; 16];
let primary = forward(input, &mut bwt_out, &mut indices).unwrap();
let mut restored = [0u8; 16];
let mut t_vec = [0u32; 16];
inverse(&bwt_out[..n], primary, &mut restored, &mut t_vec).unwrap();
assert_eq!(&restored[..n], b"AAAAAAA");
}
#[test]
fn roundtrip_single_byte() {
let input = b"X";
let mut bwt_out = [0u8; 1];
let mut indices = [0u32; 1];
let primary = forward(input, &mut bwt_out, &mut indices).unwrap();
assert_eq!(primary, 0);
assert_eq!(bwt_out[0], b'X');
let mut restored = [0u8; 1];
let mut t_vec = [0u32; 1];
inverse(&bwt_out, primary, &mut restored, &mut t_vec).unwrap();
assert_eq!(restored[0], b'X');
}
}