fatfs/
dir.rs

1#[cfg(all(not(feature = "std"), feature = "alloc"))]
2use alloc::vec::Vec;
3use core::{char, cmp, num, str};
4#[cfg(feature = "alloc")]
5use core::{iter, slice};
6use io;
7use io::prelude::*;
8use io::{ErrorKind, SeekFrom};
9
10use dir_entry::{DirEntry, DirEntryData, DirFileEntryData, DirLfnEntryData, FileAttributes, ShortName, DIR_ENTRY_SIZE};
11#[cfg(feature = "alloc")]
12use dir_entry::{LFN_ENTRY_LAST_FLAG, LFN_PART_LEN};
13use file::File;
14use fs::{DiskSlice, FileSystem, FsIoAdapter, ReadWriteSeek};
15
16#[cfg(feature = "alloc")]
17type LfnUtf16 = Vec<u16>;
18#[cfg(not(feature = "alloc"))]
19type LfnUtf16 = ();
20
21const SFN_PADDING: u8 = 0x20;
22
23pub(crate) enum DirRawStream<'a, T: ReadWriteSeek + 'a> {
24    File(File<'a, T>),
25    Root(DiskSlice<FsIoAdapter<'a, T>>),
26}
27
28impl<'a, T: ReadWriteSeek> DirRawStream<'a, T> {
29    fn abs_pos(&self) -> Option<u64> {
30        match self {
31            &DirRawStream::File(ref file) => file.abs_pos(),
32            &DirRawStream::Root(ref slice) => Some(slice.abs_pos()),
33        }
34    }
35
36    fn first_cluster(&self) -> Option<u32> {
37        match self {
38            &DirRawStream::File(ref file) => file.first_cluster(),
39            &DirRawStream::Root(_) => None,
40        }
41    }
42}
43
44// Note: derive cannot be used because of invalid bounds. See: https://github.com/rust-lang/rust/issues/26925
45impl<'a, T: ReadWriteSeek> Clone for DirRawStream<'a, T> {
46    fn clone(&self) -> Self {
47        match self {
48            &DirRawStream::File(ref file) => DirRawStream::File(file.clone()),
49            &DirRawStream::Root(ref raw) => DirRawStream::Root(raw.clone()),
50        }
51    }
52}
53
54impl<'a, T: ReadWriteSeek> Read for DirRawStream<'a, T> {
55    fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
56        match self {
57            &mut DirRawStream::File(ref mut file) => file.read(buf),
58            &mut DirRawStream::Root(ref mut raw) => raw.read(buf),
59        }
60    }
61}
62
63impl<'a, T: ReadWriteSeek> Write for DirRawStream<'a, T> {
64    fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
65        match self {
66            &mut DirRawStream::File(ref mut file) => file.write(buf),
67            &mut DirRawStream::Root(ref mut raw) => raw.write(buf),
68        }
69    }
70    fn flush(&mut self) -> io::Result<()> {
71        match self {
72            &mut DirRawStream::File(ref mut file) => file.flush(),
73            &mut DirRawStream::Root(ref mut raw) => raw.flush(),
74        }
75    }
76}
77
78impl<'a, T: ReadWriteSeek> Seek for DirRawStream<'a, T> {
79    fn seek(&mut self, pos: SeekFrom) -> io::Result<u64> {
80        match self {
81            &mut DirRawStream::File(ref mut file) => file.seek(pos),
82            &mut DirRawStream::Root(ref mut raw) => raw.seek(pos),
83        }
84    }
85}
86
87fn split_path<'c>(path: &'c str) -> (&'c str, Option<&'c str>) {
88    // remove trailing slash and split into 2 components - top-most parent and rest
89    let mut path_split = path.trim_matches('/').splitn(2, '/');
90    let comp = path_split.next().unwrap(); // SAFE: splitn always returns at least one element
91    let rest_opt = path_split.next();
92    (comp, rest_opt)
93}
94
95enum DirEntryOrShortName<'a, T: ReadWriteSeek + 'a> {
96    DirEntry(DirEntry<'a, T>),
97    ShortName([u8; 11]),
98}
99
100/// A FAT filesystem directory.
101///
102/// This struct is created by the `open_dir` or `create_dir` methods on `Dir`.
103/// The root directory is returned by the `root_dir` method on `FileSystem`.
104pub struct Dir<'a, T: ReadWriteSeek + 'a> {
105    stream: DirRawStream<'a, T>,
106    fs: &'a FileSystem<T>,
107}
108
109impl<'a, T: ReadWriteSeek + 'a> Dir<'a, T> {
110    pub(crate) fn new(stream: DirRawStream<'a, T>, fs: &'a FileSystem<T>) -> Self {
111        Dir { stream, fs }
112    }
113
114    /// Creates directory entries iterator.
115    pub fn iter(&self) -> DirIter<'a, T> {
116        DirIter::new(self.stream.clone(), self.fs, true)
117    }
118
119    fn find_entry(
120        &self,
121        name: &str,
122        is_dir: Option<bool>,
123        mut short_name_gen: Option<&mut ShortNameGenerator>,
124    ) -> io::Result<DirEntry<'a, T>> {
125        for r in self.iter() {
126            let e = r?;
127            // compare name ignoring case
128            if e.eq_name(name) {
129                // check if file or directory is expected
130                if is_dir.is_some() && Some(e.is_dir()) != is_dir {
131                    let error_msg = if e.is_dir() { "Is a directory" } else { "Not a directory" };
132                    return Err(io::Error::new(ErrorKind::Other, error_msg));
133                }
134                return Ok(e);
135            }
136            // update short name generator state
137            if let Some(ref mut gen) = short_name_gen {
138                gen.add_existing(e.raw_short_name());
139            }
140        }
141        Err(io::Error::new(ErrorKind::NotFound, "No such file or directory"))
142    }
143
144    pub(crate) fn find_volume_entry(&self) -> io::Result<Option<DirEntry<'a, T>>> {
145        for r in DirIter::new(self.stream.clone(), self.fs, false) {
146            let e = r?;
147            if e.data.is_volume() {
148                return Ok(Some(e));
149            }
150        }
151        Ok(None)
152    }
153
154    fn check_for_existence(&self, name: &str, is_dir: Option<bool>) -> io::Result<DirEntryOrShortName<'a, T>> {
155        let mut short_name_gen = ShortNameGenerator::new(name);
156        loop {
157            let r = self.find_entry(name, is_dir, Some(&mut short_name_gen));
158            match r {
159                Err(ref err) if err.kind() == ErrorKind::NotFound => {},
160                // other error
161                Err(err) => return Err(err),
162                // directory already exists - return it
163                Ok(e) => return Ok(DirEntryOrShortName::DirEntry(e)),
164            };
165            if let Ok(name) = short_name_gen.generate() {
166                return Ok(DirEntryOrShortName::ShortName(name));
167            }
168            short_name_gen.next_iteration();
169        }
170    }
171
172    /// Opens existing subdirectory.
173    ///
174    /// `path` is a '/' separated directory path relative to self directory.
175    pub fn open_dir(&self, path: &str) -> io::Result<Self> {
176        trace!("open_dir {}", path);
177        let (name, rest_opt) = split_path(path);
178        let e = self.find_entry(name, Some(true), None)?;
179        match rest_opt {
180            Some(rest) => e.to_dir().open_dir(rest),
181            None => Ok(e.to_dir()),
182        }
183    }
184
185    /// Opens existing file.
186    ///
187    /// `path` is a '/' separated file path relative to self directory.
188    pub fn open_file(&self, path: &str) -> io::Result<File<'a, T>> {
189        trace!("open_file {}", path);
190        // traverse path
191        let (name, rest_opt) = split_path(path);
192        if let Some(rest) = rest_opt {
193            let e = self.find_entry(name, Some(true), None)?;
194            return e.to_dir().open_file(rest);
195        }
196        // convert entry to a file
197        let e = self.find_entry(name, Some(false), None)?;
198        Ok(e.to_file())
199    }
200
201    /// Creates new or opens existing file=.
202    ///
203    /// `path` is a '/' separated file path relative to self directory.
204    /// File is never truncated when opening. It can be achieved by calling `File::truncate` method after opening.
205    pub fn create_file(&self, path: &str) -> io::Result<File<'a, T>> {
206        trace!("create_file {}", path);
207        // traverse path
208        let (name, rest_opt) = split_path(path);
209        if let Some(rest) = rest_opt {
210            return self.find_entry(name, Some(true), None)?.to_dir().create_file(rest);
211        }
212        // this is final filename in the path
213        let r = self.check_for_existence(name, Some(false))?;
214        match r {
215            // file does not exist - create it
216            DirEntryOrShortName::ShortName(short_name) => {
217                let sfn_entry = self.create_sfn_entry(short_name, FileAttributes::from_bits_truncate(0), None);
218                Ok(self.write_entry(name, sfn_entry)?.to_file())
219            },
220            // file already exists - return it
221            DirEntryOrShortName::DirEntry(e) => Ok(e.to_file()),
222        }
223    }
224
225    /// Creates new directory or opens existing.
226    ///
227    /// `path` is a '/' separated path relative to self directory.
228    pub fn create_dir(&self, path: &str) -> io::Result<Self> {
229        trace!("create_dir {}", path);
230        // traverse path
231        let (name, rest_opt) = split_path(path);
232        if let Some(rest) = rest_opt {
233            return self.find_entry(name, Some(true), None)?.to_dir().create_dir(rest);
234        }
235        // this is final filename in the path
236        let r = self.check_for_existence(name, Some(true))?;
237        match r {
238            // directory does not exist - create it
239            DirEntryOrShortName::ShortName(short_name) => {
240                // alloc cluster for directory data
241                let cluster = self.fs.alloc_cluster(None, true)?;
242                // create entry in parent directory
243                let sfn_entry = self.create_sfn_entry(short_name, FileAttributes::DIRECTORY, Some(cluster));
244                let entry = self.write_entry(name, sfn_entry)?;
245                let dir = entry.to_dir();
246                // create special entries "." and ".."
247                let dot_sfn = ShortNameGenerator::generate_dot();
248                let sfn_entry = self.create_sfn_entry(dot_sfn, FileAttributes::DIRECTORY, entry.first_cluster());
249                dir.write_entry(".", sfn_entry)?;
250                let dotdot_sfn = ShortNameGenerator::generate_dotdot();
251                let sfn_entry =
252                    self.create_sfn_entry(dotdot_sfn, FileAttributes::DIRECTORY, self.stream.first_cluster());
253                dir.write_entry("..", sfn_entry)?;
254                Ok(dir)
255            },
256            // directory already exists - return it
257            DirEntryOrShortName::DirEntry(e) => Ok(e.to_dir()),
258        }
259    }
260
261    fn is_empty(&self) -> io::Result<bool> {
262        trace!("is_empty");
263        // check if directory contains no files
264        for r in self.iter() {
265            let e = r?;
266            let name = e.short_file_name_as_bytes();
267            // ignore special entries "." and ".."
268            if name != b"." && name != b".." {
269                return Ok(false);
270            }
271        }
272        Ok(true)
273    }
274
275    /// Removes existing file or directory.
276    ///
277    /// `path` is a '/' separated file path relative to self directory.
278    /// Make sure there is no reference to this file (no File instance) or filesystem corruption
279    /// can happen.
280    pub fn remove(&self, path: &str) -> io::Result<()> {
281        trace!("remove {}", path);
282        // traverse path
283        let (name, rest_opt) = split_path(path);
284        if let Some(rest) = rest_opt {
285            let e = self.find_entry(name, Some(true), None)?;
286            return e.to_dir().remove(rest);
287        }
288        // in case of directory check if it is empty
289        let e = self.find_entry(name, None, None)?;
290        if e.is_dir() && !e.to_dir().is_empty()? {
291            return Err(io::Error::new(ErrorKind::Other, "Directory not empty"));
292        }
293        // free data
294        if let Some(n) = e.first_cluster() {
295            self.fs.free_cluster_chain(n)?;
296        }
297        // free long and short name entries
298        let mut stream = self.stream.clone();
299        stream.seek(SeekFrom::Start(e.offset_range.0 as u64))?;
300        let num = (e.offset_range.1 - e.offset_range.0) as usize / DIR_ENTRY_SIZE as usize;
301        for _ in 0..num {
302            let mut data = DirEntryData::deserialize(&mut stream)?;
303            trace!("removing dir entry {:?}", data);
304            data.set_deleted();
305            stream.seek(SeekFrom::Current(-(DIR_ENTRY_SIZE as i64)))?;
306            data.serialize(&mut stream)?;
307        }
308        Ok(())
309    }
310
311    /// Renames or moves existing file or directory.
312    ///
313    /// `src_path` is a '/' separated source file path relative to self directory.
314    /// `dst_path` is a '/' separated destination file path relative to `dst_dir`.
315    /// `dst_dir` can be set to self directory if rename operation without moving is needed.
316    /// Make sure there is no reference to this file (no File instance) or filesystem corruption
317    /// can happen.
318    pub fn rename(&self, src_path: &str, dst_dir: &Dir<T>, dst_path: &str) -> io::Result<()> {
319        trace!("rename {} {}", src_path, dst_path);
320        // traverse source path
321        let (name, rest_opt) = split_path(src_path);
322        if let Some(rest) = rest_opt {
323            let e = self.find_entry(name, Some(true), None)?;
324            return e.to_dir().rename(rest, dst_dir, dst_path);
325        }
326        // traverse destination path
327        let (name, rest_opt) = split_path(dst_path);
328        if let Some(rest) = rest_opt {
329            let e = dst_dir.find_entry(name, Some(true), None)?;
330            return self.rename(src_path, &e.to_dir(), rest);
331        }
332        // move/rename file
333        self.rename_internal(src_path, dst_dir, dst_path)
334    }
335
336    fn rename_internal(&self, src_name: &str, dst_dir: &Dir<T>, dst_name: &str) -> io::Result<()> {
337        trace!("rename_internal {} {}", src_name, dst_name);
338        // find existing file
339        let e = self.find_entry(src_name, None, None)?;
340        // check if destionation filename is unused
341        let r = dst_dir.check_for_existence(dst_name, None)?;
342        let short_name = match r {
343            DirEntryOrShortName::DirEntry(ref dst_e) => {
344                // check if source and destination entry is the same
345                if e.is_same_entry(dst_e) {
346                    return Ok(());
347                }
348                return Err(io::Error::new(ErrorKind::AlreadyExists, "Destination file already exists"));
349            },
350            DirEntryOrShortName::ShortName(short_name) => short_name,
351        };
352        // free long and short name entries
353        let mut stream = self.stream.clone();
354        stream.seek(SeekFrom::Start(e.offset_range.0 as u64))?;
355        let num = (e.offset_range.1 - e.offset_range.0) as usize / DIR_ENTRY_SIZE as usize;
356        for _ in 0..num {
357            let mut data = DirEntryData::deserialize(&mut stream)?;
358            trace!("removing LFN entry {:?}", data);
359            data.set_deleted();
360            stream.seek(SeekFrom::Current(-(DIR_ENTRY_SIZE as i64)))?;
361            data.serialize(&mut stream)?;
362        }
363        // save new directory entry
364        let sfn_entry = e.data.renamed(short_name);
365        dst_dir.write_entry(dst_name, sfn_entry)?;
366        Ok(())
367    }
368
369    fn find_free_entries(&self, num_entries: usize) -> io::Result<DirRawStream<'a, T>> {
370        let mut stream = self.stream.clone();
371        let mut first_free = 0;
372        let mut num_free = 0;
373        let mut i = 0;
374        loop {
375            let raw_entry = DirEntryData::deserialize(&mut stream)?;
376            if raw_entry.is_end() {
377                // first unused entry - all remaining space can be used
378                if num_free == 0 {
379                    first_free = i;
380                }
381                stream.seek(io::SeekFrom::Start(first_free as u64 * DIR_ENTRY_SIZE))?;
382                return Ok(stream);
383            } else if raw_entry.is_deleted() {
384                // free entry - calculate number of free entries in a row
385                if num_free == 0 {
386                    first_free = i;
387                }
388                num_free += 1;
389                if num_free == num_entries {
390                    // enough space for new file
391                    stream.seek(io::SeekFrom::Start(first_free as u64 * DIR_ENTRY_SIZE))?;
392                    return Ok(stream);
393                }
394            } else {
395                // used entry - start counting from 0
396                num_free = 0;
397            }
398            i += 1;
399        }
400    }
401
402    fn create_sfn_entry(
403        &self,
404        short_name: [u8; 11],
405        attrs: FileAttributes,
406        first_cluster: Option<u32>,
407    ) -> DirFileEntryData {
408        let mut raw_entry = DirFileEntryData::new(short_name, attrs);
409        raw_entry.set_first_cluster(first_cluster, self.fs.fat_type());
410        let now = self.fs.options.time_provider.get_current_date_time();
411        raw_entry.set_created(now);
412        raw_entry.set_accessed(now.date);
413        raw_entry.set_modified(now);
414        raw_entry
415    }
416
417    #[cfg(feature = "alloc")]
418    fn encode_lfn_utf16(name: &str) -> Vec<u16> {
419        name.encode_utf16().collect::<Vec<u16>>()
420    }
421    #[cfg(not(feature = "alloc"))]
422    fn encode_lfn_utf16(_name: &str) -> () {
423        ()
424    }
425
426    fn alloc_and_write_lfn_entries(
427        &self,
428        lfn_utf16: &LfnUtf16,
429        short_name: &[u8; 11],
430    ) -> io::Result<(DirRawStream<'a, T>, u64)> {
431        // get short name checksum
432        let lfn_chsum = lfn_checksum(short_name);
433        // create LFN entries generator
434        let lfn_iter = LfnEntriesGenerator::new(&lfn_utf16, lfn_chsum);
435        // find space for new entries (multiple LFN entries and 1 SFN entry)
436        let num_entries = lfn_iter.len() + 1;
437        let mut stream = self.find_free_entries(num_entries)?;
438        let start_pos = stream.seek(io::SeekFrom::Current(0))?;
439        // write LFN entries before SFN entry
440        for lfn_entry in lfn_iter {
441            lfn_entry.serialize(&mut stream)?;
442        }
443        Ok((stream, start_pos))
444    }
445
446    fn write_entry(&self, name: &str, raw_entry: DirFileEntryData) -> io::Result<DirEntry<'a, T>> {
447        trace!("write_entry {}", name);
448        // check if name doesn't contain unsupported characters
449        validate_long_name(name)?;
450        // convert long name to UTF-16
451        let lfn_utf16 = Self::encode_lfn_utf16(name);
452        // write LFN entries
453        let (mut stream, start_pos) = self.alloc_and_write_lfn_entries(&lfn_utf16, raw_entry.name())?;
454        // write short name entry
455        raw_entry.serialize(&mut stream)?;
456        let end_pos = stream.seek(io::SeekFrom::Current(0))?;
457        let abs_pos = stream.abs_pos().map(|p| p - DIR_ENTRY_SIZE);
458        // return new logical entry descriptor
459        let short_name = ShortName::new(raw_entry.name());
460        Ok(DirEntry {
461            data: raw_entry,
462            short_name,
463            lfn_utf16,
464            fs: self.fs,
465            entry_pos: abs_pos.unwrap(), // SAFE: abs_pos is absent only for empty file
466            offset_range: (start_pos, end_pos),
467        })
468    }
469}
470
471// Note: derive cannot be used because of invalid bounds. See: https://github.com/rust-lang/rust/issues/26925
472impl<'a, T: ReadWriteSeek> Clone for Dir<'a, T> {
473    fn clone(&self) -> Self {
474        Self { stream: self.stream.clone(), fs: self.fs }
475    }
476}
477
478/// An iterator over the directory entries.
479///
480/// This struct is created by the `iter` method on `Dir`.
481pub struct DirIter<'a, T: ReadWriteSeek + 'a> {
482    stream: DirRawStream<'a, T>,
483    fs: &'a FileSystem<T>,
484    skip_volume: bool,
485    err: bool,
486}
487
488impl<'a, T: ReadWriteSeek> DirIter<'a, T> {
489    fn new(stream: DirRawStream<'a, T>, fs: &'a FileSystem<T>, skip_volume: bool) -> Self {
490        DirIter { stream, fs, skip_volume, err: false }
491    }
492
493    fn should_ship_entry(&self, raw_entry: &DirEntryData) -> bool {
494        if raw_entry.is_deleted() {
495            return true;
496        }
497        match raw_entry {
498            &DirEntryData::File(ref sfn_entry) => self.skip_volume && sfn_entry.is_volume(),
499            _ => false,
500        }
501    }
502
503    fn read_dir_entry(&mut self) -> io::Result<Option<DirEntry<'a, T>>> {
504        trace!("read_dir_entry");
505        let mut lfn_buf = LongNameBuilder::new();
506        let mut offset = self.stream.seek(SeekFrom::Current(0))?;
507        let mut begin_offset = offset;
508        loop {
509            let raw_entry = DirEntryData::deserialize(&mut self.stream)?;
510            offset += DIR_ENTRY_SIZE;
511            // Check if this is end of dir
512            if raw_entry.is_end() {
513                return Ok(None);
514            }
515            // Check if this is deleted or volume ID entry
516            if self.should_ship_entry(&raw_entry) {
517                trace!("skip entry");
518                lfn_buf.clear();
519                begin_offset = offset;
520                continue;
521            }
522            match raw_entry {
523                DirEntryData::File(data) => {
524                    // Get entry position on volume
525                    let abs_pos = self.stream.abs_pos().map(|p| p - DIR_ENTRY_SIZE);
526                    // Check if LFN checksum is valid
527                    lfn_buf.validate_chksum(data.name());
528                    // Return directory entry
529                    let short_name = ShortName::new(data.name());
530                    trace!("file entry {:?}", data.name());
531                    return Ok(Some(DirEntry {
532                        data,
533                        short_name,
534                        lfn_utf16: lfn_buf.into_vec(),
535                        fs: self.fs,
536                        entry_pos: abs_pos.unwrap(), // SAFE: abs_pos is empty only for empty file
537                        offset_range: (begin_offset, offset),
538                    }));
539                },
540                DirEntryData::Lfn(data) => {
541                    // Append to LFN buffer
542                    trace!("lfn entry");
543                    lfn_buf.process(&data);
544                },
545            }
546        }
547    }
548}
549
550// Note: derive cannot be used because of invalid bounds. See: https://github.com/rust-lang/rust/issues/26925
551impl<'a, T: ReadWriteSeek> Clone for DirIter<'a, T> {
552    fn clone(&self) -> Self {
553        Self { stream: self.stream.clone(), fs: self.fs, err: self.err, skip_volume: self.skip_volume }
554    }
555}
556
557impl<'a, T: ReadWriteSeek> Iterator for DirIter<'a, T> {
558    type Item = io::Result<DirEntry<'a, T>>;
559
560    fn next(&mut self) -> Option<Self::Item> {
561        if self.err {
562            return None;
563        }
564        let r = self.read_dir_entry();
565        match r {
566            Ok(Some(e)) => Some(Ok(e)),
567            Ok(None) => None,
568            Err(err) => {
569                self.err = true;
570                Some(Err(err))
571            },
572        }
573    }
574}
575
576fn validate_long_name(name: &str) -> io::Result<()> {
577    // check if length is valid
578    if name.is_empty() {
579        return Err(io::Error::new(ErrorKind::Other, "File name is empty"));
580    }
581    if name.len() > 255 {
582        return Err(io::Error::new(ErrorKind::Other, "File name too long"));
583    }
584    // check if there are only valid characters
585    for c in name.chars() {
586        match c {
587            'a'...'z' | 'A'...'Z' | '0'...'9' => {},
588            '\u{80}'...'\u{FFFF}' => {},
589            '$' | '%' | '\'' | '-' | '_' | '@' | '~' | '`' | '!' | '(' | ')' | '{' | '}' | '.' | ' ' | '+' | ','
590            | ';' | '=' | '[' | ']' | '^' | '#' | '&' => {},
591            _ => return Err(io::Error::new(ErrorKind::Other, "File name contains unsupported characters")),
592        }
593    }
594    Ok(())
595}
596
597fn lfn_checksum(short_name: &[u8; 11]) -> u8 {
598    let mut chksum = num::Wrapping(0u8);
599    for b in short_name {
600        chksum = (chksum << 7) + (chksum >> 1) + num::Wrapping(*b);
601    }
602    chksum.0
603}
604
605#[cfg(feature = "alloc")]
606struct LongNameBuilder {
607    buf: Vec<u16>,
608    chksum: u8,
609    index: u8,
610}
611
612#[cfg(feature = "alloc")]
613impl LongNameBuilder {
614    fn new() -> Self {
615        LongNameBuilder { buf: Vec::<u16>::new(), chksum: 0, index: 0 }
616    }
617
618    fn clear(&mut self) {
619        self.buf.clear();
620        self.index = 0;
621    }
622
623    fn into_vec(mut self) -> Vec<u16> {
624        // Check if last processed entry had index 1
625        if self.index == 1 {
626            self.truncate();
627        } else if !self.is_empty() {
628            warn!("unfinished LFN sequence {}", self.index);
629            self.clear();
630        }
631        self.buf
632    }
633
634    fn truncate(&mut self) {
635        // Truncate 0 and 0xFFFF characters from LFN buffer
636        let mut lfn_len = self.buf.len();
637        while lfn_len > 0 {
638            match self.buf[lfn_len - 1] {
639                0xFFFF | 0 => lfn_len -= 1,
640                _ => break,
641            }
642        }
643        self.buf.truncate(lfn_len);
644    }
645
646    fn is_empty(&self) -> bool {
647        // Check if any LFN entry has been processed
648        // Note: index 0 is not a valid index in LFN and can be seen only after struct initialization
649        self.index == 0
650    }
651
652    fn process(&mut self, data: &DirLfnEntryData) {
653        let is_last = (data.order() & LFN_ENTRY_LAST_FLAG) != 0;
654        let index = data.order() & 0x1F;
655        if index == 0 {
656            // Corrupted entry
657            warn!("currupted lfn entry! {:x}", data.order());
658            self.clear();
659            return;
660        }
661        if is_last {
662            // last entry is actually first entry in stream
663            self.index = index;
664            self.chksum = data.checksum();
665            self.buf.resize(index as usize * LFN_PART_LEN, 0);
666        } else if self.index == 0 || index != self.index - 1 || data.checksum() != self.chksum {
667            // Corrupted entry
668            warn!("currupted lfn entry! {:x} {:x} {:x} {:x}", data.order(), self.index, data.checksum(), self.chksum);
669            self.clear();
670            return;
671        } else {
672            // Decrement LFN index only for non-last entries
673            self.index -= 1;
674        }
675        let pos = LFN_PART_LEN * (index - 1) as usize;
676        // copy name parts into LFN buffer
677        data.copy_name_to_slice(&mut self.buf[pos..pos + 13]);
678    }
679
680    fn validate_chksum(&mut self, short_name: &[u8; 11]) {
681        if self.is_empty() {
682            // Nothing to validate - no LFN entries has been processed
683            return;
684        }
685        let chksum = lfn_checksum(short_name);
686        if chksum != self.chksum {
687            warn!("checksum mismatch {:x} {:x} {:?}", chksum, self.chksum, short_name);
688            self.clear();
689        }
690    }
691}
692
693// Dummy implementation for non-alloc build
694#[cfg(not(feature = "alloc"))]
695struct LongNameBuilder {}
696#[cfg(not(feature = "alloc"))]
697impl LongNameBuilder {
698    fn new() -> Self {
699        LongNameBuilder {}
700    }
701    fn clear(&mut self) {}
702    fn into_vec(self) {}
703    fn truncate(&mut self) {}
704    fn process(&mut self, _data: &DirLfnEntryData) {}
705    fn validate_chksum(&mut self, _short_name: &[u8; 11]) {}
706}
707
708#[cfg(feature = "alloc")]
709struct LfnEntriesGenerator<'a> {
710    name_parts_iter: iter::Rev<slice::Chunks<'a, u16>>,
711    checksum: u8,
712    index: usize,
713    num: usize,
714    ended: bool,
715}
716
717#[cfg(feature = "alloc")]
718impl<'a> LfnEntriesGenerator<'a> {
719    fn new(name_utf16: &'a [u16], checksum: u8) -> Self {
720        let num_entries = (name_utf16.len() + LFN_PART_LEN - 1) / LFN_PART_LEN;
721        // create generator using reverse iterator over chunks - first chunk can be shorter
722        LfnEntriesGenerator {
723            checksum,
724            name_parts_iter: name_utf16.chunks(LFN_PART_LEN).rev(),
725            index: 0,
726            num: num_entries,
727            ended: false,
728        }
729    }
730}
731
732#[cfg(feature = "alloc")]
733impl<'a> Iterator for LfnEntriesGenerator<'a> {
734    type Item = DirLfnEntryData;
735
736    fn next(&mut self) -> Option<Self::Item> {
737        if self.ended {
738            return None;
739        }
740
741        // get next part from reverse iterator
742        match self.name_parts_iter.next() {
743            Some(ref name_part) => {
744                let lfn_index = self.num - self.index;
745                let mut order = lfn_index as u8;
746                if self.index == 0 {
747                    // this is last name part (written as first)
748                    order |= LFN_ENTRY_LAST_FLAG;
749                }
750                debug_assert!(order > 0);
751                // name is padded with ' '
752                let mut lfn_part = [0xFFFFu16; LFN_PART_LEN];
753                lfn_part[..name_part.len()].copy_from_slice(&name_part);
754                if name_part.len() < LFN_PART_LEN {
755                    // name is only zero-terminated if its length is not multiplicity of LFN_PART_LEN
756                    lfn_part[name_part.len()] = 0;
757                }
758                // create and return new LFN entry
759                let mut lfn_entry = DirLfnEntryData::new(order, self.checksum);
760                lfn_entry.copy_name_from_slice(&lfn_part);
761                self.index += 1;
762                Some(lfn_entry)
763            },
764            None => {
765                // end of name
766                self.ended = true;
767                None
768            },
769        }
770    }
771
772    fn size_hint(&self) -> (usize, Option<usize>) {
773        self.name_parts_iter.size_hint()
774    }
775}
776
777// name_parts_iter is ExactSizeIterator so size_hint returns one limit
778#[cfg(feature = "alloc")]
779impl<'a> ExactSizeIterator for LfnEntriesGenerator<'a> {}
780
781// Dummy implementation for non-alloc build
782#[cfg(not(feature = "alloc"))]
783struct LfnEntriesGenerator {}
784#[cfg(not(feature = "alloc"))]
785impl LfnEntriesGenerator {
786    fn new(_name_utf16: &(), _checksum: u8) -> Self {
787        LfnEntriesGenerator {}
788    }
789}
790#[cfg(not(feature = "alloc"))]
791impl Iterator for LfnEntriesGenerator {
792    type Item = DirLfnEntryData;
793
794    fn next(&mut self) -> Option<Self::Item> {
795        None
796    }
797
798    fn size_hint(&self) -> (usize, Option<usize>) {
799        (0, Some(0))
800    }
801}
802#[cfg(not(feature = "alloc"))]
803impl ExactSizeIterator for LfnEntriesGenerator {}
804
805#[derive(Default, Debug, Clone)]
806struct ShortNameGenerator {
807    chksum: u16,
808    long_prefix_bitmap: u16,
809    prefix_chksum_bitmap: u16,
810    name_fits: bool,
811    lossy_conv: bool,
812    exact_match: bool,
813    basename_len: u8,
814    short_name: [u8; 11],
815}
816
817impl ShortNameGenerator {
818    fn new(name: &str) -> Self {
819        // padded by ' '
820        let mut short_name = [SFN_PADDING; 11];
821        // find extension after last dot
822        let (basename_len, name_fits, lossy_conv) = match name.rfind('.') {
823            Some(index) => {
824                // extension found - copy parts before and after dot
825                let (basename_len, basename_fits, basename_lossy) =
826                    Self::copy_short_name_part(&mut short_name[0..8], &name[..index]);
827                let (_, ext_fits, ext_lossy) = Self::copy_short_name_part(&mut short_name[8..11], &name[index + 1..]);
828                (basename_len, basename_fits && ext_fits, basename_lossy || ext_lossy)
829            },
830            None => {
831                // no extension - copy name and leave extension empty
832                let (basename_len, basename_fits, basename_lossy) =
833                    Self::copy_short_name_part(&mut short_name[0..8], &name);
834                (basename_len, basename_fits, basename_lossy)
835            },
836        };
837        let chksum = Self::checksum(name);
838        Self { short_name, chksum, name_fits, lossy_conv, basename_len: basename_len as u8, ..Default::default() }
839    }
840
841    fn generate_dot() -> [u8; 11] {
842        let mut short_name = [SFN_PADDING; 11];
843        short_name[0] = 0x2e;
844        short_name
845    }
846
847    fn generate_dotdot() -> [u8; 11] {
848        let mut short_name = [SFN_PADDING; 11];
849        short_name[0] = 0x2e;
850        short_name[1] = 0x2e;
851        short_name
852    }
853
854    fn copy_short_name_part(dst: &mut [u8], src: &str) -> (usize, bool, bool) {
855        let mut dst_pos = 0;
856        let mut lossy_conv = false;
857        for c in src.chars() {
858            if dst_pos == dst.len() {
859                // result buffer is full
860                return (dst_pos, false, lossy_conv);
861            }
862            // Make sure character is allowed in 8.3 name
863            let fixed_c = match c {
864                // strip spaces and dots
865                ' ' | '.' => {
866                    lossy_conv = true;
867                    continue;
868                },
869                // copy allowed characters
870                'A'...'Z' | 'a'...'z' | '0'...'9' => c,
871                '!' | '#' | '$' | '%' | '&' | '\'' | '(' | ')' | '-' | '@' | '^' | '_' | '`' | '{' | '}' | '~' => c,
872                // replace disallowed characters by underscore
873                _ => '_',
874            };
875            // Update 'lossy conversion' flag
876            lossy_conv = lossy_conv || (fixed_c != c);
877            // short name is always uppercase
878            let upper = fixed_c.to_ascii_uppercase();
879            dst[dst_pos] = upper as u8; // SAFE: upper is in range 0x20-0x7F
880            dst_pos += 1;
881        }
882        (dst_pos, true, lossy_conv)
883    }
884
885    fn add_existing(&mut self, short_name: &[u8; 11]) {
886        // check for exact match collision
887        if short_name == &self.short_name {
888            self.exact_match = true;
889        }
890        // check for long prefix form collision (TEXTFI~1.TXT)
891        let prefix_len = cmp::min(self.basename_len, 6) as usize;
892        let num_suffix =
893            if short_name[prefix_len] == b'~' { (short_name[prefix_len + 1] as char).to_digit(10) } else { None };
894        let ext_matches = short_name[8..] == self.short_name[8..];
895        if short_name[..prefix_len] == self.short_name[..prefix_len] && num_suffix.is_some() && ext_matches {
896            let num = num_suffix.unwrap(); // SAFE
897            self.long_prefix_bitmap |= 1 << num;
898        }
899
900        // check for short prefix + checksum form collision (TE021F~1.TXT)
901        let prefix_len = cmp::min(self.basename_len, 2) as usize;
902        let num_suffix = if short_name[prefix_len + 4] == b'~' {
903            (short_name[prefix_len + 4 + 1] as char).to_digit(10)
904        } else {
905            None
906        };
907        if short_name[..prefix_len] == self.short_name[..prefix_len] && num_suffix.is_some() && ext_matches {
908            let chksum_res =
909                str::from_utf8(&short_name[prefix_len..prefix_len + 4]).map(|s| u16::from_str_radix(s, 16));
910            if chksum_res == Ok(Ok(self.chksum)) {
911                let num = num_suffix.unwrap(); // SAFE
912                self.prefix_chksum_bitmap |= 1 << num;
913            }
914        }
915    }
916
917    fn checksum(name: &str) -> u16 {
918        // BSD checksum algorithm
919        let mut chksum = num::Wrapping(0u16);
920        for c in name.chars() {
921            chksum = (chksum >> 1) + (chksum << 15) + num::Wrapping(c as u16);
922        }
923        chksum.0
924    }
925
926    fn generate(&self) -> io::Result<[u8; 11]> {
927        if !self.lossy_conv && self.name_fits && !self.exact_match {
928            // If there was no lossy conversion and name fits into
929            // 8.3 convention and there is no collision return it as is
930            return Ok(self.short_name);
931        }
932        // Try using long 6-characters prefix
933        for i in 1..5 {
934            if self.long_prefix_bitmap & (1 << i) == 0 {
935                return Ok(self.build_prefixed_name(i, false));
936            }
937        }
938        // Try prefix with checksum
939        for i in 1..10 {
940            if self.prefix_chksum_bitmap & (1 << i) == 0 {
941                return Ok(self.build_prefixed_name(i, true));
942            }
943        }
944        // Too many collisions - fail
945        Err(io::Error::new(ErrorKind::AlreadyExists, "short name already exists"))
946    }
947
948    fn next_iteration(&mut self) {
949        // Try different checksum in next iteration
950        self.chksum = (num::Wrapping(self.chksum) + num::Wrapping(1)).0;
951        // Zero bitmaps
952        self.long_prefix_bitmap = 0;
953        self.prefix_chksum_bitmap = 0;
954    }
955
956    fn build_prefixed_name(&self, num: u32, with_chksum: bool) -> [u8; 11] {
957        let mut buf = [SFN_PADDING; 11];
958        let prefix_len = if with_chksum {
959            let prefix_len = cmp::min(self.basename_len as usize, 2);
960            buf[..prefix_len].copy_from_slice(&self.short_name[..prefix_len]);
961            buf[prefix_len..prefix_len + 4].copy_from_slice(&Self::u16_to_u8_array(self.chksum));
962            prefix_len + 4
963        } else {
964            let prefix_len = cmp::min(self.basename_len as usize, 6);
965            buf[..prefix_len].copy_from_slice(&self.short_name[..prefix_len]);
966            prefix_len
967        };
968        buf[prefix_len] = b'~';
969        buf[prefix_len + 1] = char::from_digit(num, 10).unwrap() as u8; // SAFE
970        buf[8..].copy_from_slice(&self.short_name[8..]);
971        buf
972    }
973
974    fn u16_to_u8_array(x: u16) -> [u8; 4] {
975        let c1 = char::from_digit((x as u32 >> 12) & 0xF, 16).unwrap().to_ascii_uppercase() as u8;
976        let c2 = char::from_digit((x as u32 >> 8) & 0xF, 16).unwrap().to_ascii_uppercase() as u8;
977        let c3 = char::from_digit((x as u32 >> 4) & 0xF, 16).unwrap().to_ascii_uppercase() as u8;
978        let c4 = char::from_digit((x as u32 >> 0) & 0xF, 16).unwrap().to_ascii_uppercase() as u8;
979        [c1, c2, c3, c4]
980    }
981}
982
983#[cfg(test)]
984mod tests {
985    use super::*;
986
987    #[test]
988    fn test_split_path() {
989        assert_eq!(split_path("aaa/bbb/ccc"), ("aaa", Some("bbb/ccc")));
990        assert_eq!(split_path("aaa/bbb"), ("aaa", Some("bbb")));
991        assert_eq!(split_path("aaa"), ("aaa", None));
992    }
993
994    #[test]
995    fn test_generate_short_name() {
996        assert_eq!(&ShortNameGenerator::new("Foo").generate().unwrap(), b"FOO        ");
997        assert_eq!(&ShortNameGenerator::new("Foo.b").generate().unwrap(), b"FOO     B  ");
998        assert_eq!(&ShortNameGenerator::new("Foo.baR").generate().unwrap(), b"FOO     BAR");
999        assert_eq!(&ShortNameGenerator::new("Foo+1.baR").generate().unwrap(), b"FOO_1~1 BAR");
1000        assert_eq!(&ShortNameGenerator::new("ver +1.2.text").generate().unwrap(), b"VER_12~1TEX");
1001        assert_eq!(&ShortNameGenerator::new(".bashrc.swp").generate().unwrap(), b"BASHRC~1SWP");
1002    }
1003
1004    #[test]
1005    fn test_short_name_checksum_overflow() {
1006        ShortNameGenerator::checksum("\u{FF5A}\u{FF5A}\u{FF5A}\u{FF5A}");
1007    }
1008
1009    #[test]
1010    fn test_lfn_checksum_overflow() {
1011        lfn_checksum(&[0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8]);
1012    }
1013
1014    #[test]
1015    fn test_generate_short_name_collisions_long() {
1016        let mut buf: [u8; 11];
1017        let mut gen = ShortNameGenerator::new("TextFile.Mine.txt");
1018        buf = gen.generate().unwrap();
1019        assert_eq!(&buf, b"TEXTFI~1TXT");
1020        gen.add_existing(&buf);
1021        buf = gen.generate().unwrap();
1022        assert_eq!(&buf, b"TEXTFI~2TXT");
1023        gen.add_existing(&buf);
1024        buf = gen.generate().unwrap();
1025        assert_eq!(&buf, b"TEXTFI~3TXT");
1026        gen.add_existing(&buf);
1027        buf = gen.generate().unwrap();
1028        assert_eq!(&buf, b"TEXTFI~4TXT");
1029        gen.add_existing(&buf);
1030        buf = gen.generate().unwrap();
1031        assert_eq!(&buf, b"TE527D~1TXT");
1032        gen.add_existing(&buf);
1033        buf = gen.generate().unwrap();
1034        assert_eq!(&buf, b"TE527D~2TXT");
1035        for i in 3..10 {
1036            gen.add_existing(&buf);
1037            buf = gen.generate().unwrap();
1038            assert_eq!(&buf, format!("TE527D~{}TXT", i).as_bytes());
1039        }
1040        gen.add_existing(&buf);
1041        assert!(gen.generate().is_err());
1042        gen.next_iteration();
1043        for _i in 0..4 {
1044            buf = gen.generate().unwrap();
1045            gen.add_existing(&buf);
1046        }
1047        buf = gen.generate().unwrap();
1048        assert_eq!(&buf, b"TE527E~1TXT");
1049    }
1050
1051    #[test]
1052    fn test_generate_short_name_collisions_short() {
1053        let mut buf: [u8; 11];
1054        let mut gen = ShortNameGenerator::new("x.txt");
1055        buf = gen.generate().unwrap();
1056        assert_eq!(&buf, b"X       TXT");
1057        gen.add_existing(&buf);
1058        buf = gen.generate().unwrap();
1059        assert_eq!(&buf, b"X~1     TXT");
1060        gen.add_existing(&buf);
1061        buf = gen.generate().unwrap();
1062        assert_eq!(&buf, b"X~2     TXT");
1063        gen.add_existing(&buf);
1064        buf = gen.generate().unwrap();
1065        assert_eq!(&buf, b"X~3     TXT");
1066        gen.add_existing(&buf);
1067        buf = gen.generate().unwrap();
1068        assert_eq!(&buf, b"X~4     TXT");
1069        gen.add_existing(&buf);
1070        buf = gen.generate().unwrap();
1071        assert_eq!(&buf, b"X40DA~1 TXT");
1072        gen.add_existing(&buf);
1073        buf = gen.generate().unwrap();
1074        assert_eq!(&buf, b"X40DA~2 TXT");
1075    }
1076}
fatfs/dir.rs

fatfs/
dir.rs
