use core::cmp::Ordering;
use super::binary::{HEADER_BYTES, MAGIC, RECORD_BYTES, TAG};
#[derive(Clone, Copy)]
pub(crate) struct PrefixTable {
bytes: &'static [u8],
}
impl PrefixTable {
pub(crate) const fn new(bytes: &'static [u8]) -> Self {
Self { bytes }
}
pub(crate) fn longest_number(self, calling_code: u16, national: &str) -> Option<&'static str> {
if national.len() > 15 || !national.bytes().all(|byte| byte.is_ascii_digit()) {
return None;
}
let mut digits = [0_u8; 15];
let code_length = decimal(calling_code, &mut digits)?;
let end = code_length.checked_add(national.len())?;
digits
.get_mut(code_length..end)?
.copy_from_slice(national.as_bytes());
self.longest_bytes(&digits[..end])
}
fn longest_bytes(self, digits: &[u8]) -> Option<&'static str> {
let count = self.count()?;
let pool = HEADER_BYTES.checked_add(count.checked_mul(RECORD_BYTES)?)?;
let longest = usize::from(self.record(count.checked_sub(1)?)?.length);
for length in (1..=digits.len().min(longest)).rev() {
let key = decimal_prefix(digits.get(..length)?)?;
let encoded_length = u8::try_from(length).ok()?;
let mut lower = 0;
let mut upper = count;
while lower < upper {
let middle = lower + (upper - lower) / 2;
let record = self.record(middle)?;
match (record.length, record.key).cmp(&(encoded_length, key)) {
Ordering::Less => lower = middle + 1,
Ordering::Greater => upper = middle,
Ordering::Equal => return self.value(record, pool),
}
}
}
None
}
fn count(self) -> Option<usize> {
if self.bytes.get(..MAGIC.len())? != MAGIC || *self.bytes.get(MAGIC.len())? != TAG {
return None;
}
let start = MAGIC.len() + 1;
let count = u32::from_le_bytes(self.bytes.get(start..start + 4)?.try_into().ok()?);
let count = usize::try_from(count).ok()?;
let records = count.checked_mul(RECORD_BYTES)?;
(HEADER_BYTES.checked_add(records)? <= self.bytes.len()).then_some(count)
}
fn record(self, index: usize) -> Option<Record> {
let start = HEADER_BYTES.checked_add(index.checked_mul(RECORD_BYTES)?)?;
let bytes = self.bytes.get(start..start + RECORD_BYTES)?;
let record = Record {
key: u64::from_le_bytes(bytes.get(..8)?.try_into().ok()?),
length: *bytes.get(8)?,
value_offset: u32::from_le_bytes(bytes.get(9..13)?.try_into().ok()?),
value_length: u16::from_le_bytes(bytes.get(13..15)?.try_into().ok()?),
};
(record.length > 0 && record.length <= 15).then_some(record)
}
fn value(self, record: Record, pool: usize) -> Option<&'static str> {
let start = pool.checked_add(usize::try_from(record.value_offset).ok()?)?;
let end = start.checked_add(usize::from(record.value_length))?;
std::str::from_utf8(self.bytes.get(start..end)?).ok()
}
}
fn decimal(mut value: u16, output: &mut [u8; 15]) -> Option<usize> {
if value == 0 || value > 999 {
return None;
}
let length = if value >= 100 {
3
} else if value >= 10 {
2
} else {
1
};
for position in (0..length).rev() {
output[position] = b'0' + u8::try_from(value % 10).ok()?;
value /= 10;
}
Some(length)
}
fn decimal_prefix(digits: &[u8]) -> Option<u64> {
digits.iter().try_fold(0_u64, |value, digit| {
let digit = digit.checked_sub(b'0')?;
if digit > 9 {
return None;
}
value.checked_mul(10)?.checked_add(u64::from(digit))
})
}
#[derive(Clone, Copy)]
struct Record {
key: u64,
length: u8,
value_offset: u32,
value_length: u16,
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn longest_prefix_reads_the_static_table_without_decoding_it() {
let mut bytes = MAGIC.to_vec();
bytes.push(TAG);
bytes.extend(2_u32.to_le_bytes());
for (key, length, offset, value_length) in [(1_u64, 1_u8, 0_u32, 5_u16), (1201, 4, 5, 6)] {
bytes.extend(key.to_le_bytes());
bytes.push(length);
bytes.extend(offset.to_le_bytes());
bytes.extend(value_length.to_le_bytes());
}
bytes.extend(b"WorldJersey");
let table = PrefixTable::new(Box::leak(bytes.into_boxed_slice()));
assert_eq!(table.longest_bytes(b"12015550123"), Some("Jersey"));
assert_eq!(table.longest_bytes(b"16502530000"), Some("World"));
assert_eq!(table.longest_number(1, "2015550123"), Some("Jersey"));
assert_eq!(decimal(1000, &mut [0; 15]), None);
assert_eq!(decimal_prefix(b"12:"), None);
}
}