pub const RUNA: u16 = 0;
pub const RUNB: u16 = 1;
pub fn encode(mtf_data: &[u8], symbols: &mut [u16], n_in_use: usize) -> usize {
let eob = (n_in_use + 1) as u16;
let mut out_pos = 0;
let mut i = 0;
while i < mtf_data.len() {
if mtf_data[i] == 0 {
let mut run_len = 0u32;
while i < mtf_data.len() && mtf_data[i] == 0 {
run_len += 1;
i += 1;
}
encode_run(run_len, symbols, &mut out_pos);
} else {
symbols[out_pos] = mtf_data[i] as u16 + 1;
out_pos += 1;
i += 1;
}
}
symbols[out_pos] = eob;
out_pos += 1;
out_pos
}
fn encode_run(mut run_len: u32, symbols: &mut [u16], pos: &mut usize) {
while run_len > 0 {
run_len -= 1; if run_len & 1 == 0 {
symbols[*pos] = RUNA;
} else {
symbols[*pos] = RUNB;
}
*pos += 1;
run_len >>= 1;
}
}
pub fn decode(symbols: &[u16], mtf_data: &mut [u8], n_in_use: usize) -> usize {
let eob = (n_in_use + 1) as u16;
let mut out_pos = 0;
let mut i = 0;
while i < symbols.len() {
let sym = symbols[i];
if sym == eob {
break;
}
if sym == RUNA || sym == RUNB {
let mut run_len = 0u32;
let mut power = 1u32;
while i < symbols.len() && (symbols[i] == RUNA || symbols[i] == RUNB) {
if symbols[i] == RUNA {
run_len += power;
} else {
run_len += 2 * power;
}
power <<= 1;
i += 1;
}
for _ in 0..run_len {
mtf_data[out_pos] = 0;
out_pos += 1;
}
} else {
mtf_data[out_pos] = (sym - 1) as u8;
out_pos += 1;
i += 1;
}
}
out_pos
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn encode_no_zeros() {
let mtf = [1u8, 2, 3];
let mut symbols = [0u16; 16];
let n = encode(&mtf, &mut symbols, 4);
assert_eq!(n, 4);
assert_eq!(symbols[0], 2);
assert_eq!(symbols[1], 3);
assert_eq!(symbols[2], 4);
assert_eq!(symbols[3], 5); }
#[test]
fn encode_zeros() {
let mtf = [0u8, 0, 0, 1];
let mut symbols = [0u16; 16];
let n = encode(&mtf, &mut symbols, 4);
let mut decoded = [0u8; 16];
let dn = decode(&symbols[..n], &mut decoded, 4);
assert_eq!(dn, 4);
assert_eq!(&decoded[..4], &[0, 0, 0, 1]);
}
#[test]
fn roundtrip_mixed() {
let mtf = [0u8, 0, 0, 0, 0, 1, 0, 0, 2, 0];
let n_in_use = 4;
let mut symbols = [0u16; 64];
let sym_len = encode(&mtf, &mut symbols, n_in_use);
let mut decoded = [0u8; 64];
let dec_len = decode(&symbols[..sym_len], &mut decoded, n_in_use);
assert_eq!(dec_len, mtf.len());
assert_eq!(&decoded[..dec_len], &mtf[..]);
}
#[test]
fn single_zero() {
let mtf = [0u8];
let mut symbols = [0u16; 16];
let sym_len = encode(&mtf, &mut symbols, 2);
let mut decoded = [0u8; 16];
let dec_len = decode(&symbols[..sym_len], &mut decoded, 2);
assert_eq!(dec_len, 1);
assert_eq!(decoded[0], 0);
}
}