use ferrosys_ucd::{ASSIGNED, CASE_FOLDING, COMBINING_CLASS, DECOMPOSITION};
pub(crate) const HASH_MASK: u32 = 0x3F_FFFF;
const S_BASE: u32 = 0xAC00;
const L_BASE: u32 = 0x1100;
const V_BASE: u32 = 0x1161;
const T_BASE: u32 = 0x11A7;
const V_COUNT: u32 = 21;
const T_COUNT: u32 = 28;
const N_COUNT: u32 = V_COUNT * T_COUNT;
const S_COUNT: u32 = 19 * N_COUNT;
pub(crate) fn key(name: &[u8], fold: bool) -> Option<Vec<u32>> {
let text = std::str::from_utf8(name).ok()?;
let decomposed = decompose(text.chars().map(u32::from));
if !fold {
return Some(decomposed);
}
let folded = decomposed.into_iter().flat_map(|cp| {
CASE_FOLDING
.binary_search_by_key(&cp, |(c, _)| *c)
.map_or_else(|_| vec![cp], |i| CASE_FOLDING[i].1.to_vec())
});
Some(decompose(folded))
}
pub(crate) fn hash(form: &[u32]) -> u32 {
let bytes: Vec<u8> = form.iter().flat_map(|cp| cp.to_le_bytes()).collect();
crate::crc32c::crc32c(!0, &bytes) & HASH_MASK
}
pub(crate) const MAX_NAME_UNITS: usize = 255;
pub(crate) type UnicodeVersion = (u8, u8);
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(crate) enum NameFault {
NotUtf8,
TooLong(usize),
Unassigned(u32),
Noncharacter(u32),
}
pub(crate) fn check(name: &[u8], version: UnicodeVersion) -> Result<(), NameFault> {
let text = std::str::from_utf8(name).map_err(|_| NameFault::NotUtf8)?;
let units: usize = text.chars().map(char::len_utf16).sum();
if units > MAX_NAME_UNITS {
return Err(NameFault::TooLong(units));
}
for cp in text.chars().map(u32::from) {
if is_noncharacter(cp) {
return Err(NameFault::Noncharacter(cp));
}
if !assigned_in(cp, version) {
return Err(NameFault::Unassigned(cp));
}
}
Ok(())
}
const fn is_noncharacter(cp: u32) -> bool {
(cp >= 0xFDD0 && cp <= 0xFDEF) || cp & 0xFFFE == 0xFFFE
}
fn assigned_in(cp: u32, version: UnicodeVersion) -> bool {
let at = ASSIGNED.partition_point(|(_, last, _, _)| *last < cp);
ASSIGNED
.get(at)
.is_some_and(|&(first, _, major, minor)| first <= cp && (major, minor) <= version)
}
fn decompose(code_points: impl Iterator<Item = u32>) -> Vec<u32> {
let mut out = Vec::new();
for cp in code_points {
if (S_BASE..S_BASE + S_COUNT).contains(&cp) {
let s = cp - S_BASE;
out.push(L_BASE + s / N_COUNT);
out.push(V_BASE + (s % N_COUNT) / T_COUNT);
if !s.is_multiple_of(T_COUNT) {
out.push(T_BASE + s % T_COUNT);
}
} else if let Ok(i) = DECOMPOSITION.binary_search_by_key(&cp, |(c, _)| *c) {
out.extend_from_slice(DECOMPOSITION[i].1);
} else {
out.push(cp);
}
}
let mut i = 0;
while i < out.len() {
if class(out[i]) == 0 {
i += 1;
continue;
}
let start = i;
while i < out.len() && class(out[i]) != 0 {
i += 1;
}
out[start..i].sort_by_key(|cp| class(*cp));
}
out
}
fn class(cp: u32) -> u8 {
COMBINING_CLASS
.binary_search_by_key(&cp, |(c, _)| *c)
.map_or(0, |i| COMBINING_CLASS[i].1)
}
#[cfg(test)]
mod tests {
use super::*;
fn same(a: &str, b: &str, fold: bool) -> bool {
key(a.as_bytes(), fold) == key(b.as_bytes(), fold)
}
#[test]
fn composed_and_decomposed_spellings_are_one_name_on_either_kind_of_volume() {
for fold in [false, true] {
assert!(same("caf\u{E9}", "cafe\u{301}", fold));
assert!(same("\u{212A}", "K", fold));
assert!(same("\u{212B}", "\u{C5}", fold));
assert!(same("\u{2126}", "\u{3A9}", fold));
assert!(same("\u{D55C}", "\u{1112}\u{1161}\u{11AB}", fold));
assert!(same("a\u{301}\u{316}", "a\u{316}\u{301}", fold));
assert_eq!(
key("a\u{301}\u{316}".as_bytes(), fold),
Some(vec![u32::from('a'), 0x316, 0x301])
);
}
assert!(!same("Readme", "README", false));
}
#[test]
fn a_volume_that_folds_case_folds_it_fully_and_not_as_turkish() {
assert!(same("Readme", "README", true));
assert!(same("STRASSE", "stra\u{DF}e", true));
assert!(same("\u{FB01}", "fi", true));
assert!(same("\u{130}", "i\u{307}", true));
assert!(!same("I", "\u{131}", true));
assert!(
same("\u{3C2}", "\u{3C3}", true),
"final sigma folds to sigma"
);
}
#[test]
fn the_hash_is_the_complemented_crc_of_the_form_in_22_bits() {
let form = key(b"hello", false).expect("UTF-8");
let words: Vec<u8> = b"hello"
.iter()
.flat_map(|b| u32::from(*b).to_le_bytes())
.collect();
assert_eq!(hash(&form), crate::crc32c::crc32c(!0, &words) & HASH_MASK);
assert!(hash(&form) <= HASH_MASK);
}
#[test]
fn a_name_hashes_to_what_a_volume_macos_wrote_stores_it_under() {
let observed: [(&str, u32, u32); 8] = [
("names", 0x09_3833, 0x09_3833),
("MixedCase", 0x05_183B, 0x37_08E3),
("\u{E9}cole", 0x2D_A0E8, 0x2D_A0E8),
("\u{130}", 0x3E_E29A, 0x3E_8703),
("\u{AC00}", 0x2A_953B, 0x2A_953B),
("stra\u{DF}e", 0x14_6C83, 0x3F_993D),
("\u{3A3}\u{3B1}", 0x1D_E450, 0x1D_4AFB),
("\u{FB01}", 0x30_19CF, 0x06_9132),
];
for (name, folding, keeping) in observed {
for (fold, stored) in [(true, folding), (false, keeping)] {
let form = key(name.as_bytes(), fold).expect("UTF-8");
assert_eq!(hash(&form), stored, "{name:?}, folding case: {fold}");
}
}
}
#[test]
fn a_name_that_is_not_utf8_has_no_form() {
assert_eq!(key(b"\xff\xfe", true), None);
}
#[test]
fn a_name_is_held_to_the_code_points_its_version_assigns_and_255_utf16_units() {
const V16: UnicodeVersion = (16, 0);
const V17: UnicodeVersion = (17, 0);
for cp in [0x378, 0xE0080] {
let name = char::from_u32(cp).unwrap().to_string();
assert_eq!(check(name.as_bytes(), V17), Err(NameFault::Unassigned(cp)));
}
for cp in [0xFDD0, 0xFDEF, 0xFFFE, 0xFFFF, 0x1FFFE, 0x10FFFF] {
let name = char::from_u32(cp).unwrap().to_string();
assert_eq!(
check(name.as_bytes(), V17),
Err(NameFault::Noncharacter(cp))
);
}
for name in ["\u{E000}", "\u{E0041}", "\u{1F600}", "a\u{200D}b", "a:b"] {
assert_eq!(check(name.as_bytes(), V17), Ok(()), "{name:?}");
}
assert_eq!(check("\u{10D50}".as_bytes(), V16), Ok(()));
assert_eq!(check("\u{1E5D0}".as_bytes(), V16), Ok(()));
assert_eq!(
check("\u{10EC5}".as_bytes(), V16),
Err(NameFault::Unassigned(0x10EC5))
);
assert_eq!(check("\u{10EC5}".as_bytes(), V17), Ok(()));
assert_eq!(check("\u{20AC}".repeat(255).as_bytes(), V17), Ok(()));
assert_eq!(
check("\u{20AC}".repeat(256).as_bytes(), V17),
Err(NameFault::TooLong(256))
);
assert_eq!(
check("\u{1F600}".repeat(128).as_bytes(), V17),
Err(NameFault::TooLong(256))
);
assert_eq!(check(b"x\xed\xa0\x80", V17), Err(NameFault::NotUtf8));
}
}