use std::collections::HashSet;
use crate::path::is_reserved_name_char;
use super::ondisk::{
LFN_CHARS_PER_ENTRY, LFN_LAST_ENTRY, LFN_PADDING, LfnEntry, NAME_DELETED, NAME_LEADING_E5,
lfn_checksum, unpadded,
};
pub(crate) const SHORT_NAME_LEN: usize = 11;
const BASE_LEN: usize = 8;
const EXT_LEN: usize = 3;
pub const MAX_NAME_UNITS: usize = 255;
const MAX_TAIL: u32 = 999_999;
const SHORT_NAME_ALSO_FORBIDDEN: &[u8] = b"+,.;=[]";
pub(crate) fn is_reserved_short_byte(byte: u8) -> bool {
byte == 0x7F
|| SHORT_NAME_ALSO_FORBIDDEN.contains(&byte)
|| is_reserved_name_char(char::from(byte))
}
pub(crate) fn is_reserved_short_byte_at(byte: u8, position: usize) -> bool {
match (position, byte) {
(0, NAME_LEADING_E5) => false,
(0, b' ') => true,
_ => is_reserved_short_byte(byte),
}
}
const SUBSTITUTE: u8 = b'_';
#[derive(Clone, PartialEq, Eq, Debug, thiserror::Error)]
#[non_exhaustive]
pub enum NameError {
#[error("the name is not valid UTF-8, so it has no UTF-16 form a long name entry holds")]
NotUtf8,
#[error("the name is empty")]
Empty,
#[error("a name of {units} UTF-16 code units exceeds the {limit} the format holds")]
#[non_exhaustive]
TooLong {
units: usize,
limit: usize,
},
#[error("{ch:?} is not a character a FAT name may contain")]
#[non_exhaustive]
ForbiddenCharacter {
ch: char,
},
#[error("a name ending in a dot or a space is not one a driver reads back unchanged")]
TrailingDotOrSpace,
#[error(
"no short name is left for this name: all {limit} numeric tails on the stem {} are \
taken",
crate::escape::printable(.stem)
)]
#[non_exhaustive]
TailsExhausted {
stem: Vec<u8>,
limit: u32,
},
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub(crate) struct PlacedName {
pub short: [u8; SHORT_NAME_LEN],
pub long: Option<Vec<u16>>,
}
impl PlacedName {
pub fn slots(&self) -> usize {
1 + self.lfn_count()
}
fn lfn_count(&self) -> usize {
match &self.long {
Some(units) => units.len().div_ceil(LFN_CHARS_PER_ENTRY),
None => 0,
}
}
pub fn lfn_entries(&self) -> Vec<LfnEntry> {
let Some(units) = &self.long else {
return Vec::new();
};
let checksum = lfn_checksum(&self.short);
let chunks: Vec<&[u16]> = units.chunks(LFN_CHARS_PER_ENTRY).collect();
let last = chunks.len() - 1;
chunks
.iter()
.enumerate()
.rev()
.map(|(i, chunk)| {
let mut name = [LFN_PADDING; LFN_CHARS_PER_ENTRY];
name[..chunk.len()].copy_from_slice(chunk);
if chunk.len() < LFN_CHARS_PER_ENTRY {
name[chunk.len()] = 0;
}
LfnEntry {
order: (i as u8 + 1) | if i == last { LFN_LAST_ENTRY } else { 0 },
name,
checksum,
}
})
.collect()
}
}
#[derive(Default, Debug)]
pub(crate) struct DirNames {
used: HashSet<[u8; SHORT_NAME_LEN]>,
}
impl DirNames {
pub fn new() -> Self {
Self::default()
}
pub fn place(&mut self, name: &[u8]) -> Result<PlacedName, NameError> {
let units = long_name_units(name)?;
let text = core::str::from_utf8(name).map_err(|_| NameError::NotUtf8)?;
let (base, ext) = stem(text);
let plain = assemble(&base, &ext);
let short = if self.used.insert(plain) {
plain
} else {
self.with_tail(&base, &ext)?
};
let long = (render(&short) != text).then_some(units);
Ok(PlacedName { short, long })
}
fn with_tail(&mut self, base: &[u8], ext: &[u8]) -> Result<[u8; SHORT_NAME_LEN], NameError> {
for n in 1..=MAX_TAIL {
let mut tail = [0u8; BASE_LEN];
let mut at = 0;
tail[at] = b'~';
at += 1;
for digit in n.to_string().bytes() {
tail[at] = digit;
at += 1;
}
let tail = &tail[..at];
let keep = base.len().min(BASE_LEN - tail.len());
let mut tailed = Vec::with_capacity(BASE_LEN);
tailed.extend_from_slice(&base[..keep]);
tailed.extend_from_slice(tail);
let candidate = assemble(&tailed, ext);
if self.used.insert(candidate) {
return Ok(candidate);
}
}
Err(NameError::TailsExhausted {
stem: base.to_vec(),
limit: MAX_TAIL,
})
}
}
fn long_name_units(name: &[u8]) -> Result<Vec<u16>, NameError> {
let text = core::str::from_utf8(name).map_err(|_| NameError::NotUtf8)?;
if text.is_empty() {
return Err(NameError::Empty);
}
for ch in text.chars() {
if is_reserved_name_char(ch) || u32::from(ch) == u32::from(LFN_PADDING) {
return Err(NameError::ForbiddenCharacter { ch });
}
}
if text.ends_with('.') || text.ends_with(' ') {
return Err(NameError::TrailingDotOrSpace);
}
let units: Vec<u16> = text.encode_utf16().collect();
if units.len() > MAX_NAME_UNITS {
return Err(NameError::TooLong {
units: units.len(),
limit: MAX_NAME_UNITS,
});
}
Ok(units)
}
fn stem(name: &str) -> (Vec<u8>, Vec<u8>) {
let trimmed = name.trim_start_matches(['.', ' ']);
let (base_src, ext_src) = match trimmed.rfind('.') {
Some(dot) => (&trimmed[..dot], &trimmed[dot + 1..]),
None => (trimmed, ""),
};
let mut base = shorten(base_src, BASE_LEN);
let ext = shorten(ext_src, EXT_LEN);
debug_assert!(
!base.is_empty(),
"a legal name shortened to nothing: {name:?}"
);
if base.is_empty() {
base.push(SUBSTITUTE);
}
(base, ext)
}
fn shorten(part: &str, limit: usize) -> Vec<u8> {
let mut out = Vec::with_capacity(limit);
for ch in part.chars() {
if out.len() == limit {
break;
}
if ch == '.' || ch == ' ' {
continue;
}
let byte = if !ch.is_ascii() {
SUBSTITUTE
} else {
let byte = (ch as u8).to_ascii_uppercase();
if is_reserved_short_byte(byte) {
SUBSTITUTE
} else {
byte
}
};
out.push(byte);
}
out
}
fn assemble(base: &[u8], ext: &[u8]) -> [u8; SHORT_NAME_LEN] {
let mut name = [b' '; SHORT_NAME_LEN];
name[..base.len()].copy_from_slice(base);
name[BASE_LEN..BASE_LEN + ext.len()].copy_from_slice(ext);
if name[0] == NAME_DELETED {
name[0] = NAME_LEADING_E5;
}
name
}
pub(crate) fn render(short: &[u8; SHORT_NAME_LEN]) -> String {
let base = unpadded(&short[..BASE_LEN]);
let ext = unpadded(&short[BASE_LEN..]);
let mut out = String::with_capacity(SHORT_NAME_LEN + 1);
out.push_str(&crate::escape::printable(base));
if !ext.is_empty() {
out.push('.');
out.push_str(&crate::escape::printable(ext));
}
out
}
pub(crate) fn folded(name: &[u8]) -> Option<String> {
core::str::from_utf8(name).ok().map(str::to_lowercase)
}
#[cfg(test)]
mod tests {
use super::*;
fn short_of(name: &str) -> String {
String::from_utf8(
DirNames::new()
.place(name.as_bytes())
.expect("a name the format holds")
.short
.to_vec(),
)
.expect("the derivation emits ASCII")
}
fn needs_lfn(name: &str) -> bool {
DirNames::new()
.place(name.as_bytes())
.expect("a name the format holds")
.long
.is_some()
}
#[test]
fn a_character_a_short_name_reserves_becomes_an_underscore_there() {
for (name, short) in [
("a+b.txt", "A_B TXT"),
("a[b].txt", "A_B_ TXT"),
("a\u{7f}b.txt", "A_B TXT"),
] {
assert_eq!(short_of(name), short, "{name:?}");
assert!(
needs_lfn(name),
"{name:?} keeps its own spelling in the long name"
);
}
}
#[test]
fn a_long_name_holding_the_unit_the_format_pads_with_is_refused() {
assert!(matches!(
long_name_units("a\u{ffff}b".as_bytes()),
Err(NameError::ForbiddenCharacter { ch: '\u{ffff}' })
));
}
#[test]
fn the_reserved_short_name_bytes_are_the_documented_set_and_0x7f() {
let reserved: Vec<u8> = (0u8..=0x7f)
.filter(|&b| is_reserved_short_byte(b))
.collect();
let mut want: Vec<u8> = (0..0x20).collect();
want.extend_from_slice(b"\"*+,./:;<=>?[\\]|\x7f");
want.sort_unstable();
assert_eq!(reserved, want);
assert!(!(0x80..=0xff).any(is_reserved_short_byte));
assert!(!is_reserved_short_byte_at(NAME_LEADING_E5, 0));
assert!(is_reserved_short_byte_at(NAME_LEADING_E5, 1));
assert!(is_reserved_short_byte_at(b' ', 0));
assert!(!is_reserved_short_byte_at(b' ', 7), "padding");
}
#[test]
fn a_name_that_is_already_a_short_name_is_stored_as_one() {
for name in ["BOOTX64.EFI", "MAKEFILE", "A", "README.TXT", "X.Y"] {
assert!(
!needs_lfn(name),
"{name} was given a long name it does not need"
);
assert_eq!(render(&assemble_of(name)), name);
}
}
fn assemble_of(name: &str) -> [u8; SHORT_NAME_LEN] {
DirNames::new().place(name.as_bytes()).expect("place").short
}
#[test]
fn the_derivation_folds_strips_substitutes_and_truncates() {
assert_eq!(short_of("readme.txt"), "README TXT");
assert_eq!(short_of("Makefile"), "MAKEFILE ");
assert_eq!(short_of("configuration.yaml"), "CONFIGURYAM");
assert_eq!(short_of("archive.tar.gz"), "ARCHIVETGZ ");
assert_eq!(short_of("my file.txt"), "MYFILE TXT");
assert_eq!(short_of("a+b,c;d.txt"), "A_B_C_D TXT");
assert_eq!(short_of(".config"), "CONFIG ");
assert_eq!(short_of(".gitignore"), "GITIGNOR ");
assert_eq!(short_of("é.txt"), "_ TXT");
assert_eq!(short_of("日本語.txt"), "___ TXT");
assert_eq!(short_of(". .txt"), "TXT ");
for name in [
"readme.txt",
"Makefile",
"configuration.yaml",
"archive.tar.gz",
"my file.txt",
".config",
"é.txt",
] {
assert!(needs_lfn(name), "{name} lost its name to the short form");
}
}
#[test]
fn a_collision_takes_the_next_numeric_tail_in_the_order_it_is_offered() {
let mut dir = DirNames::new();
let names = [
"A Long File Name.txt",
"A Long File Name Also.txt",
"A Long File Number Three.txt",
];
let shorts: Vec<String> = names
.iter()
.map(|n| {
String::from_utf8(dir.place(n.as_bytes()).expect("place").short.to_vec())
.expect("ASCII")
})
.collect();
assert_eq!(shorts, ["ALONGFILTXT", "ALONGF~1TXT", "ALONGF~2TXT"]);
let mut reversed = DirNames::new();
assert_eq!(
&reversed.place(names[2].as_bytes()).expect("place").short,
b"ALONGFILTXT"
);
assert_eq!(
&reversed.place(names[0].as_bytes()).expect("place").short,
b"ALONGF~1TXT"
);
}
#[test]
fn a_literal_short_name_takes_the_slot_a_tail_would_have_used() {
let mut dir = DirNames::new();
assert_eq!(
&dir.place(b"ALONGF~1.TXT").expect("place").short,
b"ALONGF~1TXT"
);
let placed = dir.place(b"A Long File Name.txt").expect("place");
assert_eq!(&placed.short, b"ALONGFILTXT");
let next = dir.place(b"A Long File Name Also.txt").expect("place");
assert_eq!(
&next.short, b"ALONGF~2TXT",
"the taken tail was not skipped"
);
}
#[test]
fn the_tail_shortens_the_base_rather_than_overflowing_the_field() {
let mut dir = DirNames::new();
dir.place(b"document.txt").expect("place");
for expected in [b"DOCUME~1TXT", b"DOCUME~2TXT"] {
let short = dir.place(b"document.txt").expect("place").short;
assert_eq!(&short, expected);
assert_eq!(short.len(), SHORT_NAME_LEN);
}
let mut short_base = DirNames::new();
short_base.place(b"ab").expect("place");
assert_eq!(
&short_base.place(b"ab").expect("place").short,
b"AB~1 "
);
}
#[test]
fn a_name_the_format_cannot_represent_is_refused_rather_than_substituted() {
let mut dir = DirNames::new();
for (name, want) in [
(&b"a/b"[..], NameError::ForbiddenCharacter { ch: '/' }),
(b"a:b", NameError::ForbiddenCharacter { ch: ':' }),
(b"a*b", NameError::ForbiddenCharacter { ch: '*' }),
(b"a?b", NameError::ForbiddenCharacter { ch: '?' }),
(b"a\\b", NameError::ForbiddenCharacter { ch: '\\' }),
(b"a|b", NameError::ForbiddenCharacter { ch: '|' }),
(b"a\"b", NameError::ForbiddenCharacter { ch: '"' }),
(b"a<b", NameError::ForbiddenCharacter { ch: '<' }),
(b"a>b", NameError::ForbiddenCharacter { ch: '>' }),
(b"a\tb", NameError::ForbiddenCharacter { ch: '\t' }),
(b"", NameError::Empty),
(b"trailing.", NameError::TrailingDotOrSpace),
(b"trailing ", NameError::TrailingDotOrSpace),
] {
assert_eq!(
dir.place(name),
Err(want),
"{} was accepted",
String::from_utf8_lossy(name)
);
}
assert_eq!(dir.place(&[0xFF, 0xFE]), Err(NameError::NotUtf8));
let long = "x".repeat(MAX_NAME_UNITS + 1);
assert_eq!(
dir.place(long.as_bytes()),
Err(NameError::TooLong {
units: MAX_NAME_UNITS + 1,
limit: MAX_NAME_UNITS
})
);
assert!(dir.place("x".repeat(MAX_NAME_UNITS).as_bytes()).is_ok());
assert!(dir.place(b"a+b=c[d].txt").is_ok());
}
#[test]
fn a_long_name_is_chunked_backwards_and_every_chunk_carries_the_checksum() {
let placed = DirNames::new()
.place("A Long File Name.txt".as_bytes())
.expect("place");
let entries = placed.lfn_entries();
assert_eq!(entries.len(), 2, "twenty characters spans two entries");
assert_eq!(entries[0].order, 2 | LFN_LAST_ENTRY);
assert_eq!(entries[1].order, 1);
let checksum = lfn_checksum(&placed.short);
assert!(entries.iter().all(|e| e.checksum == checksum));
let mut units: Vec<u16> = Vec::new();
for entry in entries.iter().rev() {
units.extend(
entry
.name
.iter()
.take_while(|&&u| u != 0 && u != LFN_PADDING),
);
}
assert_eq!(
String::from_utf16(&units).expect("utf16"),
"A Long File Name.txt"
);
}
#[test]
fn a_name_that_fills_its_last_entry_gets_no_terminator() {
let placed = DirNames::new().place(b"abcdefghijklm").expect("place");
let entries = placed.lfn_entries();
assert_eq!(entries.len(), 1);
assert!(entries[0].name.iter().all(|&u| u != 0 && u != LFN_PADDING));
let placed = DirNames::new().place(b"abcdefghijkl").expect("place");
let entry = placed.lfn_entries()[0];
assert_eq!(entry.name[12], 0);
let placed = DirNames::new().place(b"abcdefghijk").expect("place");
let entry = placed.lfn_entries()[0];
assert_eq!(entry.name[11], 0);
assert_eq!(entry.name[12], LFN_PADDING);
}
#[test]
fn a_name_spans_the_entries_its_length_needs_and_the_slots_say_so() {
for (units, entries) in [
(1usize, 1usize),
(13, 1),
(14, 2),
(26, 2),
(27, 3),
(255, 20),
] {
let placed = DirNames::new()
.place("x".repeat(units).as_bytes())
.expect("place");
assert_eq!(placed.lfn_entries().len(), entries, "{units} characters");
assert_eq!(placed.slots(), entries + 1);
}
let placed = DirNames::new().place(b"BOOTX64.EFI").expect("place");
assert!(placed.lfn_entries().is_empty());
assert_eq!(placed.slots(), 1);
}
#[test]
fn a_character_outside_the_basic_plane_survives_as_its_surrogate_pair() {
let placed = DirNames::new().place("🦀.rs".as_bytes()).expect("place");
let units = placed.long.expect("a long name");
assert_eq!(units.len(), 5, "one surrogate pair, a dot, and two letters");
assert_eq!(String::from_utf16(&units).expect("utf16"), "🦀.rs");
assert_eq!(&placed.short, b"_ RS ");
}
#[test]
fn two_names_a_driver_cannot_tell_apart_fold_to_one() {
assert_eq!(folded(b"readme.txt"), folded(b"README.TXT"));
assert_eq!(folded(b"MixedCase"), folded(b"mIXEDcASE"));
assert_ne!(folded(b"readme.txt"), folded(b"readme.md"));
assert_eq!(folded("Ä.txt".as_bytes()), folded("ä.txt".as_bytes()));
assert_eq!(folded(&[0xFF]), None);
}
}