filesystem_recovery.cpp

Go to the documentation of this file.

#include "filesystem_recovery.hpp"
#include "i18n.hpp"
#include "ntfs_recovery.hpp"
#include "ext4_recovery.hpp"
#include "btrfs_recovery.hpp"
#include "xfs_recovery.hpp"
#include "hfs_recovery.hpp"
#include "carving.hpp"
#include "text_utils.hpp"
 
#include <algorithm>
#include <array>
#include <cctype>
#include <cstdlib>
#include <filesystem>
#include <fstream>
#include <map>
#include <optional>
#include <set>
#include <sstream>
#include <string>
#include <vector>
 
namespace fs = std::filesystem;
 
namespace {
uint16_t le16(const unsigned char* p) {
    return static_cast<uint16_t>(p[0]) | (static_cast<uint16_t>(p[1]) << 8);
}
 
uint32_t le32(const unsigned char* p) {
    return static_cast<uint32_t>(p[0]) |
           (static_cast<uint32_t>(p[1]) << 8) |
           (static_cast<uint32_t>(p[2]) << 16) |
           (static_cast<uint32_t>(p[3]) << 24);
}
 
uint64_t le64(const unsigned char* p) {
    return static_cast<uint64_t>(p[0]) |
           (static_cast<uint64_t>(p[1]) << 8) |
           (static_cast<uint64_t>(p[2]) << 16) |
           (static_cast<uint64_t>(p[3]) << 24) |
           (static_cast<uint64_t>(p[4]) << 32) |
           (static_cast<uint64_t>(p[5]) << 40) |
           (static_cast<uint64_t>(p[6]) << 48) |
           (static_cast<uint64_t>(p[7]) << 56);
}
 
// Bug #14, #18 fix: previous implementation silently DROPPED illegal characters
// (e.g. "file:test.txt" -> "filetesttxt") instead of replacing them. It also
// mangled accented characters into '_'. Now uses the shared UTF-8 aware helper.
inline std::string sanitize_path_component(const std::string& in) {
    return text_utils::sanitize_component(in);
}
 
bool write_data_to_file(DiskReader& reader,
                        const std::vector<std::pair<uint64_t, uint64_t>>& ranges,
                        const fs::path& out_path,
                        uint64_t expected_size,
                        std::string& error) {
    std::ofstream out(out_path, std::ios::binary);
    if (!out) {
        error = trs("Unable to create output file") + std::string(": ") + out_path.string();
        return false;
    }
 
    std::vector<unsigned char> buffer(1024 * 1024);
    uint64_t written = 0;
    for (const auto& [offset, length] : ranges) {
        uint64_t remaining = length;
        uint64_t cursor = offset;
        while (remaining > 0 && written < expected_size) {
            const uint64_t allowed = std::min<uint64_t>(remaining, expected_size - written);
            const size_t chunk = static_cast<size_t>(std::min<uint64_t>(buffer.size(), allowed));
            if (!reader.read_at(cursor, buffer.data(), chunk)) {
                error = trs("Read error while exporting recovered file");
                return false;
            }
            out.write(reinterpret_cast<const char*>(buffer.data()), static_cast<std::streamsize>(chunk));
            if (!out) {
                error = trs("Write error while exporting recovered file");
                return false;
            }
            remaining -= chunk;
            cursor += chunk;
            written += chunk;
        }
        if (written >= expected_size) break;
    }
    return true;
}
 
class Fat32Recovery {
public:
    explicit Fat32Recovery(DiskReader& reader) : reader_(reader) {}
 
    bool recover(uint64_t volume_offset,
                 const fs::path& out_root,
                 std::vector<RecoveredFileRecord>& recovered,
                 std::vector<std::string>& logs,
                 std::string& error) {
        if (!load_bpb(volume_offset)) return false;
        fs::create_directories(out_root);
        logs.push_back(trs("FAT32 recovery started at offset") + std::string(" ") + std::to_string(volume_offset));
        std::set<uint32_t> dir_guard;
        if (!recover_directory(root_cluster_, out_root, recovered, logs, error, dir_guard, 0)) {
            return false;
        }
        logs.push_back(trs("FAT32 recovery completed."));
        return true;
    }
 
private:
    DiskReader& reader_;
    uint64_t volume_offset_ {0};
    uint16_t bytes_per_sector_ {0};
    uint8_t sectors_per_cluster_ {0};
    uint16_t reserved_sectors_ {0};
    uint8_t fat_count_ {0};
    uint32_t sectors_per_fat_ {0};
    uint32_t root_cluster_ {2};
    uint64_t fat_offset_bytes_ {0};
    uint64_t data_region_offset_ {0};
    uint64_t cluster_size_ {0};
 
    bool load_bpb(uint64_t volume_offset) {
        std::array<unsigned char, 512> b{};
        if (!reader_.read_at(volume_offset, b.data(), b.size())) return false;
        if (std::string(reinterpret_cast<const char*>(b.data() + 82), 8) != "FAT32   ") return false;
        volume_offset_ = volume_offset;
        bytes_per_sector_ = le16(b.data() + 11);
        sectors_per_cluster_ = b[13];
        reserved_sectors_ = le16(b.data() + 14);
        fat_count_ = b[16];
        sectors_per_fat_ = le32(b.data() + 36);
        root_cluster_ = le32(b.data() + 44);
        if (bytes_per_sector_ == 0 || sectors_per_cluster_ == 0 || sectors_per_fat_ == 0 || fat_count_ == 0) return false;
        cluster_size_ = static_cast<uint64_t>(bytes_per_sector_) * sectors_per_cluster_;
        fat_offset_bytes_ = volume_offset_ + static_cast<uint64_t>(reserved_sectors_) * bytes_per_sector_;
        data_region_offset_ = volume_offset_ + static_cast<uint64_t>(reserved_sectors_ + fat_count_ * sectors_per_fat_) * bytes_per_sector_;
        return true;
    }
 
    uint64_t cluster_to_offset(uint32_t cluster) const {
        return data_region_offset_ + static_cast<uint64_t>(cluster - 2) * cluster_size_;
    }
 
    bool read_cluster(uint32_t cluster, std::vector<unsigned char>& out) {
        out.resize(static_cast<size_t>(cluster_size_));
        return reader_.read_at(cluster_to_offset(cluster), out.data(), out.size());
    }
 
    bool next_cluster(uint32_t current, uint32_t& next) {
        const uint64_t fat_entry_offset = fat_offset_bytes_ + static_cast<uint64_t>(current) * 4;
        std::array<unsigned char, 4> entry{};
        if (!reader_.read_at(fat_entry_offset, entry.data(), entry.size())) return false;
        next = le32(entry.data()) & 0x0FFFFFFF;
        return true;
    }
 
    std::vector<uint32_t> cluster_chain(uint32_t start, size_t hard_limit = 1 << 20) {
        std::vector<uint32_t> chain;
        if (start < 2) return chain;
        std::set<uint32_t> seen;
        uint32_t current = start;
        while (current >= 2 && current < 0x0FFFFFF8 && chain.size() < hard_limit && seen.insert(current).second) {
            chain.push_back(current);
            uint32_t next = 0x0FFFFFFF;
            if (!next_cluster(current, next)) break;
            if (next == 0x0FFFFFF7 || next == 0) break;
            current = next;
        }
        return chain;
    }
 
    static std::string decode_lfn_part(const unsigned char* entry) {
        // Bug #14 fix: FAT32 long filenames are UTF-16LE, not ASCII.
        // The previous version replaced any non-ASCII char with '_',
        // mangling all Italian/European/Asian filenames.
        // We extract the 26 bytes of UTF-16LE name fragment from one LFN slot
        // (positions 1, 3, 5, 7, 9 / 14..24 / 28, 30) into a flat buffer,
        // then run it through the shared UTF-8 decoder.
        static const int positions[] = {1,3,5,7,9,14,16,18,20,22,24,28,30};
        std::vector<unsigned char> raw;
        raw.reserve(26);
        for (int pos : positions) {
            const uint16_t ch = le16(entry + pos);
            if (ch == 0x0000 || ch == 0xFFFF) {
                // Append null-terminator-equivalent and stop
                raw.push_back(0);
                raw.push_back(0);
                break;
            }
            raw.push_back(static_cast<unsigned char>(ch & 0xFF));
            raw.push_back(static_cast<unsigned char>((ch >> 8) & 0xFF));
        }
        return text_utils::utf16le_to_utf8(raw.data(), raw.size());
    }
 
    static std::string short_name(const unsigned char* entry) {
        std::string base;
        for (int i = 0; i < 8; ++i) {
            const unsigned char c = entry[i];
            if (c == ' ') break;
            base.push_back(static_cast<char>(c));
        }
        std::string ext;
        for (int i = 8; i < 11; ++i) {
            const unsigned char c = entry[i];
            if (c == ' ') break;
            ext.push_back(static_cast<char>(c));
        }
        if (!ext.empty()) return base + "." + ext;
        return base;
    }
 
    bool export_file(const std::string& name,
                     uint32_t start_cluster,
                     uint32_t size_bytes,
                     const fs::path& out_dir,
                     std::vector<RecoveredFileRecord>& recovered,
                     std::vector<std::string>& logs,
                     std::string& error) {
        if (name.empty() || name == "." || name == "..") return true;
        fs::create_directories(out_dir);
        const auto chain = cluster_chain(start_cluster);
        if (chain.empty() && size_bytes > 0) {
            logs.push_back(trs("Skipped FAT32 file with invalid cluster chain") + std::string(": ") + name);
            return true;
        }
 
        std::vector<std::pair<uint64_t, uint64_t>> ranges;
        for (uint32_t cluster : chain) {
            ranges.push_back({cluster_to_offset(cluster), cluster_size_});
        }
 
        fs::path out_path = out_dir / sanitize_path_component(name);
        std::string unique = out_path.string();
        int suffix = 1;
        while (fs::exists(unique)) {
            unique = (out_dir / (sanitize_path_component(name) + "_" + std::to_string(suffix++))).string();
        }
        out_path = unique;
        if (!write_data_to_file(reader_, ranges, out_path, size_bytes, error)) {
            return false;
        }
        recovered.push_back({out_path.string(), "FAT32", name, size_bytes, "full", "filesystem export"});
        logs.push_back(trs("Recovered FAT32 file:") + std::string(" ") + out_path.string());
        return true;
    }
 
    bool recover_directory(uint32_t dir_cluster,
                           const fs::path& out_dir,
                           std::vector<RecoveredFileRecord>& recovered,
                           std::vector<std::string>& logs,
                           std::string& error,
                           std::set<uint32_t>& dir_guard,
                           int depth) {
        if (depth > 32) return true;
        if (!dir_guard.insert(dir_cluster).second) return true;
 
        const auto chain = cluster_chain(dir_cluster, 4096);
        std::vector<unsigned char> cluster_buf;
        std::vector<std::string> lfn_parts;
        // Track LFN slots for deleted entries too. The LFN parts of a
        // deleted file have their first byte set to 0xE5 too -- but we
        // want to RECOVER the original characters when possible.
        std::vector<std::string> deleted_lfn_parts;
 
        for (uint32_t cluster : chain) {
            if (!read_cluster(cluster, cluster_buf)) continue;
            for (size_t off = 0; off + 32 <= cluster_buf.size(); off += 32) {
                const unsigned char* e = cluster_buf.data() + off;
                if (e[0] == 0x00) return true;
 
                const unsigned char attr = e[11];
 
                // ---- DELETED entry (first byte = 0xE5) ----
                //
                // A 0xE5 first-byte marks the dirent as freed. The rest
                // of the bytes (cluster pointers, size, LFN parts) are
                // intact unless the slot has been reused.
                //
                // Note that the FIRST char of the short name was
                // overwritten by 0xE5, so we can't recover it from the
                // 8.3 alone. If we have LFN parts, those are intact.
                if (e[0] == 0xE5) {
                    if (attr == 0x0F) {
                        // Deleted LFN slot -- save the chars; the first
                        // byte (sequence number) was the one overwritten
                        // with 0xE5, the unicode chars are intact.
                        deleted_lfn_parts.push_back(decode_lfn_part(e));
                        continue;
                    }
                    if ((attr & 0x08) != 0) { deleted_lfn_parts.clear(); continue; }
                    // Skip directory entries that were deleted (rare,
                    // and recovering them recursively is risky on a
                    // possibly-corrupted slot).
                    if ((attr & 0x10) != 0) {
                        deleted_lfn_parts.clear();
                        continue;
                    }
 
                    // Build name from deleted LFN parts if available,
                    // otherwise reconstruct best-effort short name.
                    std::string del_name;
                    if (!deleted_lfn_parts.empty()) {
                        for (auto it = deleted_lfn_parts.rbegin();
                             it != deleted_lfn_parts.rend(); ++it) del_name += *it;
                    } else {
                        // First byte was overwritten by 0xE5. Use '_'
                        // as placeholder for the lost first character.
                        std::string sn = short_name(e);
                        if (!sn.empty() && static_cast<unsigned char>(sn[0]) == 0xE5) {
                            sn[0] = '_';
                        }
                        del_name = sn;
                    }
                    deleted_lfn_parts.clear();
                    del_name = sanitize_path_component(del_name);
                    if (del_name.empty()) del_name = "deleted_unnamed";
 
                    const uint32_t dh = le16(e + 20);
                    const uint32_t dl = le16(e + 26);
                    const uint32_t del_cluster = (dh << 16) | dl;
                    const uint32_t del_size = le32(e + 28);
 
                    // Heuristic: skip clearly-bogus entries
                    if (del_size == 0) {
                        // Empty deleted file -- still create it
                        const fs::path deleted_dir = out_dir / "deleted";
                        std::error_code ec;
                        fs::create_directories(deleted_dir, ec);
                        const fs::path out_path = deleted_dir / del_name;
                        std::ofstream(out_path, std::ios::binary);
                        recovered.push_back({out_path.string(), "FAT32",
                            ("deleted/" + del_name), 0, "partial",
                            "deleted-empty"});
                        continue;
                    }
                    if (del_cluster < 2 || del_cluster >= 0x0FFFFFF7) continue;
 
                    // Try to recover by following the FAT chain. The
                    // chain may have been re-used (= the file's data is
                    // gone). We do best-effort: if the chain reads back
                    // and decodes to size_bytes worth of data, save it.
                    const fs::path deleted_dir = out_dir / "deleted";
                    std::error_code ec;
                    fs::create_directories(deleted_dir, ec);
                    std::string ex_err;
                    if (export_file_to_dir(del_name, del_cluster, del_size,
                                            deleted_dir, recovered, logs, ex_err,
                                            /*is_deleted=*/true)) {
                        // recorded inside export_file_to_dir
                    }
                    continue;
                }
 
                if (attr == 0x0F) {
                    lfn_parts.push_back(decode_lfn_part(e));
                    continue;
                }
                if ((attr & 0x08) != 0) { lfn_parts.clear(); continue; }
 
                std::string name;
                if (!lfn_parts.empty()) {
                    for (auto it = lfn_parts.rbegin(); it != lfn_parts.rend(); ++it) name += *it;
                } else {
                    name = short_name(e);
                }
                lfn_parts.clear();
                name = sanitize_path_component(name);
                if (name.empty()) name = "unnamed";
 
                const uint32_t high = le16(e + 20);
                const uint32_t low = le16(e + 26);
                const uint32_t start_cluster = (high << 16) | low;
                const uint32_t size_bytes = le32(e + 28);
                const bool is_dir = (attr & 0x10) != 0;
 
                if (is_dir) {
                    if (name != "." && name != ".." && start_cluster >= 2) {
                        const fs::path subdir = out_dir / name;
                        fs::create_directories(subdir);
                        if (!recover_directory(start_cluster, subdir, recovered, logs, error, dir_guard, depth + 1)) {
                            return false;
                        }
                    }
                } else {
                    if (!export_file(name, start_cluster, size_bytes, out_dir, recovered, logs, error)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
 
    // Helper used by the deleted-entry path. Same as export_file but
    // tags the resulting record with "deleted-recovered" + integrity
    // "partial" because the cluster chain may have been reused.
    bool export_file_to_dir(const std::string& name,
                             uint32_t start_cluster,
                             uint32_t size_bytes,
                             const fs::path& out_dir,
                             std::vector<RecoveredFileRecord>& recovered,
                             std::vector<std::string>& logs,
                             std::string& /*error*/,
                             bool is_deleted) {
        if (start_cluster < 2 || size_bytes == 0) return false;
        // Compute how many clusters we need
        const uint32_t cluster_bytes = static_cast<uint32_t>(cluster_size_);
        if (cluster_bytes == 0) return false;
        const uint64_t need_clusters = (size_bytes + cluster_bytes - 1) / cluster_bytes;
 
        // For deleted files we don't have a reliable FAT chain (it may
        // point into reused clusters). Heuristic: assume the file was
        // CONTIGUOUS starting at start_cluster -- this is true for ~80%
        // of FAT files in practice (defragmented).
        std::vector<uint32_t> chain;
        if (is_deleted) {
            chain.reserve(static_cast<size_t>(need_clusters));
            for (uint64_t i = 0; i < need_clusters; ++i) {
                chain.push_back(static_cast<uint32_t>(start_cluster + i));
            }
        } else {
            chain = cluster_chain(start_cluster);
        }
        if (chain.empty()) return false;
 
        const fs::path out_path = out_dir / sanitize_path_component(name);
        std::ofstream out(out_path, std::ios::binary | std::ios::trunc);
        if (!out) return false;
        uint64_t written = 0;
        std::vector<unsigned char> cb;
        for (uint32_t cl : chain) {
            if (written >= size_bytes) break;
            if (!read_cluster(cl, cb)) break;
            const uint64_t want = std::min<uint64_t>(cluster_bytes, size_bytes - written);
            out.write(reinterpret_cast<const char*>(cb.data()),
                      static_cast<std::streamsize>(want));
            written += want;
        }
        const std::string note = is_deleted
            ? "deleted-contiguous-guess"
            : "filesystem export";
        const std::string integ = is_deleted ? "partial" : "full";
        recovered.push_back({out_path.string(), "FAT32",
            (is_deleted ? "deleted/" : "") + name,
            written, integ, note});
        if (is_deleted) {
            logs.push_back(trs("Recovered FAT32 deleted file (best-effort, "
                               "assumes contiguous):") +
                           std::string(" ") + out_path.string());
        }
        return true;
    }
};
 
class ExfatRecovery {
public:
    explicit ExfatRecovery(DiskReader& reader) : reader_(reader) {}
 
    bool recover(uint64_t volume_offset,
                 const fs::path& out_root,
                 std::vector<RecoveredFileRecord>& recovered,
                 std::vector<std::string>& logs,
                 std::string& error) {
        if (!load_vbr(volume_offset)) return false;
        fs::create_directories(out_root);
        logs.push_back(trs("exFAT recovery started at offset") + std::string(" ") + std::to_string(volume_offset));
        if (load_allocation_bitmap()) {
            logs.push_back(trs("exFAT allocation bitmap loaded") + std::string(": ") + std::to_string(allocation_bitmap_length_) + " bytes");
        }
        std::set<uint32_t> dir_guard;
        if (!recover_directory(root_dir_cluster_, out_root, recovered, logs, error, dir_guard, 0)) {
            return false;
        }
        logs.push_back(trs("exFAT recovery completed."));
        return true;
    }
 
private:
    struct StreamInfo {
        bool valid {false};
        bool no_fat_chain {false};
        uint32_t first_cluster {0};
        uint64_t data_length {0};
        std::string name;
        bool is_directory {false};
        bool is_deleted {false};
    };
 
    DiskReader& reader_;
    uint64_t volume_offset_ {0};
    uint64_t partition_offset_sectors_ {0};
    uint64_t volume_length_sectors_ {0};
    uint32_t fat_offset_sectors_ {0};
    uint32_t fat_length_sectors_ {0};
    uint32_t cluster_heap_offset_sectors_ {0};
    uint32_t cluster_count_ {0};
    uint32_t root_dir_cluster_ {2};
    uint32_t serial_number_ {0};
    uint8_t bytes_per_sector_shift_ {0};
    uint8_t sectors_per_cluster_shift_ {0};
    uint64_t bytes_per_sector_ {0};
    uint64_t sectors_per_cluster_ {0};
    uint64_t cluster_size_ {0};
    uint64_t fat_offset_bytes_ {0};
    uint64_t cluster_heap_offset_bytes_ {0};
    uint32_t allocation_bitmap_cluster_ {0};
    uint64_t allocation_bitmap_length_ {0};
    std::vector<unsigned char> allocation_bitmap_;
 
    bool load_vbr(uint64_t volume_offset) {
        std::array<unsigned char, 512> b{};
        if (!reader_.read_at(volume_offset, b.data(), b.size())) return false;
        if (std::string(reinterpret_cast<const char*>(b.data() + 3), 8) != "EXFAT   ") return false;
        volume_offset_ = volume_offset;
        partition_offset_sectors_ = le64(b.data() + 64);
        volume_length_sectors_ = le64(b.data() + 72);
        fat_offset_sectors_ = le32(b.data() + 80);
        fat_length_sectors_ = le32(b.data() + 84);
        cluster_heap_offset_sectors_ = le32(b.data() + 88);
        cluster_count_ = le32(b.data() + 92);
        root_dir_cluster_ = le32(b.data() + 96);
        serial_number_ = le32(b.data() + 100);
        bytes_per_sector_shift_ = b[108];
        sectors_per_cluster_shift_ = b[109];
        bytes_per_sector_ = 1ull << bytes_per_sector_shift_;
        sectors_per_cluster_ = 1ull << sectors_per_cluster_shift_;
        cluster_size_ = bytes_per_sector_ * sectors_per_cluster_;
        fat_offset_bytes_ = volume_offset_ + static_cast<uint64_t>(fat_offset_sectors_) * bytes_per_sector_;
        cluster_heap_offset_bytes_ = volume_offset_ + static_cast<uint64_t>(cluster_heap_offset_sectors_) * bytes_per_sector_;
        allocation_bitmap_cluster_ = 0;
        allocation_bitmap_length_ = 0;
        allocation_bitmap_.clear();
        return bytes_per_sector_ >= 512 && cluster_size_ > 0 && cluster_count_ > 0;
    }
 
    bool cluster_allocated(uint32_t cluster) const {
        if (cluster < 2 || cluster >= cluster_count_ + 2) return false;
        if (allocation_bitmap_.empty()) return true;
        const uint64_t idx = static_cast<uint64_t>(cluster - 2);
        const uint64_t byte_index = idx / 8;
        const uint8_t bit = static_cast<uint8_t>(idx % 8);
        if (byte_index >= allocation_bitmap_.size()) return false;
        return (allocation_bitmap_[static_cast<size_t>(byte_index)] & (1u << bit)) != 0;
    }
 
    bool load_allocation_bitmap() {
        if (root_dir_cluster_ < 2) return false;
        const auto chain = cluster_chain(root_dir_cluster_, true, cluster_size_ * 64, 4096);
        std::vector<unsigned char> cluster_buf;
        for (uint32_t cluster : chain) {
            if (!read_cluster(cluster, cluster_buf)) continue;
            for (size_t off = 0; off + 32 <= cluster_buf.size(); off += 32) {
                const unsigned char* e = cluster_buf.data() + off;
                const uint8_t type = e[0];
                if (type == 0x00) break;
                if (type == 0x81) {
                    allocation_bitmap_cluster_ = le32(e + 20);
                    allocation_bitmap_length_ = le64(e + 24);
                    break;
                }
            }
            if (allocation_bitmap_cluster_ != 0) break;
        }
        if (allocation_bitmap_cluster_ < 2 || allocation_bitmap_length_ == 0) return false;
        const auto bitmap_chain = cluster_chain(allocation_bitmap_cluster_, true, allocation_bitmap_length_, 4096);
        if (bitmap_chain.empty()) return false;
        std::vector<std::pair<uint64_t, uint64_t>> ranges;
        for (uint32_t cluster : bitmap_chain) ranges.push_back({cluster_to_offset(cluster), cluster_size_});
        fs::path tmp = fs::temp_directory_path() / ("exfat_bitmap_" + std::to_string(serial_number_) + ".bin");
        std::string local_error;
        if (!write_data_to_file(reader_, ranges, tmp, allocation_bitmap_length_, local_error)) return false;
        std::ifstream in(tmp, std::ios::binary);
        allocation_bitmap_.assign(std::istreambuf_iterator<char>(in), std::istreambuf_iterator<char>());
        std::error_code ec;
        fs::remove(tmp, ec);
        return !allocation_bitmap_.empty();
    }
 
    uint64_t cluster_to_offset(uint32_t cluster) const {
        return cluster_heap_offset_bytes_ + static_cast<uint64_t>(cluster - 2) * cluster_size_;
    }
 
    bool next_cluster(uint32_t current, uint32_t& next) {
        const uint64_t fat_entry_offset = fat_offset_bytes_ + static_cast<uint64_t>(current) * 4;
        std::array<unsigned char, 4> entry{};
        if (!reader_.read_at(fat_entry_offset, entry.data(), entry.size())) return false;
        next = le32(entry.data()) & 0x0FFFFFFF;
        return true;
    }
 
    std::vector<uint32_t> cluster_chain(uint32_t start, bool no_fat_chain, uint64_t data_length, size_t hard_limit = 1 << 20) {
        std::vector<uint32_t> chain;
        if (start < 2) return chain;
        if (no_fat_chain) {
            const uint64_t clusters_needed = data_length == 0 ? 1 : (data_length + cluster_size_ - 1) / cluster_size_;
            for (uint64_t i = 0; i < clusters_needed; ++i) {
                const uint32_t cluster = start + static_cast<uint32_t>(i);
                if (cluster < 2 || cluster >= cluster_count_ + 2) break;
                if (!cluster_allocated(cluster)) {
                    chain.clear();
                    break;
                }
                chain.push_back(cluster);
            }
            return chain;
        }
        std::set<uint32_t> seen;
        uint32_t current = start;
        while (current >= 2 && current < 0x0FFFFFF8 && chain.size() < hard_limit && seen.insert(current).second) {
            chain.push_back(current);
            uint32_t next = 0x0FFFFFFF;
            if (!next_cluster(current, next)) break;
            if (next == 0x0FFFFFF7 || next == 0) break;
            current = next;
        }
        return chain;
    }
 
    bool read_cluster(uint32_t cluster, std::vector<unsigned char>& out) {
        out.resize(static_cast<size_t>(cluster_size_));
        return reader_.read_at(cluster_to_offset(cluster), out.data(), out.size());
    }
 
    static std::string decode_utf16_name(const std::vector<unsigned char>& bytes) {
        // Bug #14 fix: exFAT filenames are UTF-16LE; decode as proper UTF-8
        // instead of replacing non-ASCII with '_'.
        return text_utils::utf16le_to_utf8(bytes.data(), bytes.size());
    }
 
    bool export_stream(const StreamInfo& info,
                       const fs::path& out_dir,
                       std::vector<RecoveredFileRecord>& recovered,
                       std::vector<std::string>& logs,
                       std::string& error) {
        if (!info.valid || info.is_directory) return true;
        fs::create_directories(out_dir);
        const auto chain = cluster_chain(info.first_cluster, info.no_fat_chain, info.data_length);
        if (chain.empty() && info.data_length > 0) {
            logs.push_back(trs("Skipped exFAT file with invalid cluster chain") + std::string(": ") + info.name);
            return true;
        }
        std::vector<std::pair<uint64_t, uint64_t>> ranges;
        for (uint32_t cluster : chain) {
            ranges.push_back({cluster_to_offset(cluster), cluster_size_});
        }
        fs::path out_path = out_dir / sanitize_path_component(info.name);
        std::string unique = out_path.string();
        int suffix = 1;
        while (fs::exists(unique)) {
            unique = (out_dir / (sanitize_path_component(info.name) + "_" + std::to_string(suffix++))).string();
        }
        out_path = unique;
        if (!write_data_to_file(reader_, ranges, out_path, info.data_length, error)) return false;
        recovered.push_back({out_path.string(), "exFAT", info.name, info.data_length, "full", info.no_fat_chain ? "bitmap-validated contiguous export" : "filesystem export"});
        logs.push_back(trs("Recovered exFAT file:") + std::string(" ") + out_path.string());
        return true;
    }
 
    // Deleted-file export. Same as export_stream but:
    //   - never trusts the FAT chain (it may have been re-allocated)
    //   - always assumes a CONTIGUOUS layout starting at first_cluster
    //     (= true for ~80% of exFAT files; many file systems
    //     allocate contiguously when they can)
    //   - tags the result as "partial" with note "deleted-contiguous-guess"
    //   - never recurses into deleted directories
    bool export_stream_deleted(const StreamInfo& info,
                                const fs::path& out_dir,
                                std::vector<RecoveredFileRecord>& recovered,
                                std::vector<std::string>& logs,
                                std::string& error) {
        if (!info.valid || info.is_directory) return true;
        if (info.first_cluster < 2 || info.data_length == 0) {
            // Empty file -- still create a placeholder
            const fs::path out_path = out_dir / sanitize_path_component(info.name);
            std::ofstream(out_path, std::ios::binary);
            recovered.push_back({out_path.string(), "exFAT",
                ("deleted/" + info.name), 0, "partial",
                "deleted-empty"});
            return true;
        }
        // Build a contiguous "guess" range
        const uint64_t need_clusters =
            (info.data_length + cluster_size_ - 1) / cluster_size_;
        std::vector<std::pair<uint64_t, uint64_t>> ranges;
        ranges.reserve(static_cast<size_t>(need_clusters));
        for (uint64_t i = 0; i < need_clusters; ++i) {
            const uint32_t cl = info.first_cluster + static_cast<uint32_t>(i);
            // Bound check
            if (cl < 2 || cl >= cluster_count_ + 2) break;
            ranges.push_back({cluster_to_offset(cl), cluster_size_});
        }
        if (ranges.empty()) return true;
 
        fs::path out_path = out_dir / sanitize_path_component(info.name);
        std::string unique = out_path.string();
        int suffix = 1;
        while (fs::exists(unique)) {
            unique = (out_dir / (sanitize_path_component(info.name) + "_"
                                  + std::to_string(suffix++))).string();
        }
        out_path = unique;
        if (!write_data_to_file(reader_, ranges, out_path,
                                 info.data_length, error)) return false;
        recovered.push_back({out_path.string(), "exFAT",
            ("deleted/" + info.name), info.data_length, "partial",
            "deleted-contiguous-guess"});
        logs.push_back(trs("Recovered exFAT deleted file (best-effort, "
                           "assumes contiguous):") +
                       std::string(" ") + out_path.string());
        return true;
    }
 
    bool recover_directory(uint32_t start_cluster,
                           const fs::path& out_dir,
                           std::vector<RecoveredFileRecord>& recovered,
                           std::vector<std::string>& logs,
                           std::string& error,
                           std::set<uint32_t>& dir_guard,
                           int depth) {
        if (depth > 32) return true;
        if (!dir_guard.insert(start_cluster).second) return true;
 
        const auto chain = cluster_chain(start_cluster, true, cluster_size_ * 16, 4096);
        std::vector<unsigned char> cluster_buf;
        StreamInfo current;
        int remaining_secondary = 0;
        std::vector<unsigned char> name_bytes;
 
        auto finalize = [&](bool force_dir_recurse) -> bool {
            if (!current.valid) return true;
            current.name = sanitize_path_component(current.name.empty() ? "unnamed" : current.name);
            // Deleted entries: route to "deleted/" subdir, never recurse
            // into them (the directory's children entries are likely
            // already overwritten or pointing into reused clusters).
            if (current.is_deleted) {
                if (current.is_directory) return true;  // skip deleted dirs
                const fs::path deleted_dir = out_dir / "deleted";
                std::error_code ec;
                fs::create_directories(deleted_dir, ec);
                return export_stream_deleted(current, deleted_dir, recovered, logs, error);
            }
            if (current.is_directory) {
                if (current.first_cluster >= 2) {
                    const fs::path subdir = out_dir / current.name;
                    fs::create_directories(subdir);
                    return recover_directory(current.first_cluster, subdir, recovered, logs, error, dir_guard, depth + 1);
                }
            } else {
                return export_stream(current, out_dir, recovered, logs, error);
            }
            (void)force_dir_recurse;
            return true;
        };
 
        for (uint32_t cluster : chain) {
            if (!read_cluster(cluster, cluster_buf)) continue;
            for (size_t off = 0; off + 32 <= cluster_buf.size(); off += 32) {
                const unsigned char* e = cluster_buf.data() + off;
                const uint8_t type = e[0];
                if (type == 0x00) {
                    return finalize(false);
                }
                // ---- exFAT entry types ----
                //
                // Bit 7 of the type byte = "InUse". When clear, the
                // entry is DELETED but otherwise intact. The 3 entry
                // types we care about have these (in-use, deleted)
                // pairs:
                //   File Directory Entry:  0x85  /  0x05
                //   Stream Extension:      0xC0  /  0x40
                //   Filename:              0xC1  /  0x41
                //
                // We accept BOTH variants. We track is_deleted on the
                // current pseudo-entry so finalize() can route the
                // file to a "deleted/" subdirectory.
                const bool is_file_de   = (type == 0x85 || type == 0x05);
                const bool is_stream_de = (type == 0xC0 || type == 0x40);
                const bool is_name_de   = (type == 0xC1 || type == 0x41);
                const bool entry_deleted = (type == 0x05 || type == 0x40 ||
                                            type == 0x41);
 
                if (is_file_de) {
                    if (!finalize(false)) return false;
                    current = {};
                    current.valid = true;
                    current.is_directory = (e[4] & 0x10) != 0;
                    current.is_deleted = entry_deleted;
                    remaining_secondary = e[1];
                    name_bytes.clear();
                } else if (current.valid && is_stream_de) {
                    current.no_fat_chain = (e[1] & 0x02) != 0;
                    current.name = std::string();
                    const uint8_t name_len = e[3];
                    current.first_cluster = le32(e + 20);
                    current.data_length = le64(e + 24);
                    name_bytes.reserve(static_cast<size_t>(name_len) * 2);
                    if (entry_deleted) current.is_deleted = true;
                    --remaining_secondary;
                } else if (current.valid && is_name_de) {
                    name_bytes.insert(name_bytes.end(), e + 2, e + 32);
                    current.name = decode_utf16_name(name_bytes);
                    if (entry_deleted) current.is_deleted = true;
                    --remaining_secondary;
                    if (remaining_secondary <= 0) {
                        if (!finalize(true)) return false;
                        current = {};
                    }
                } else if (current.valid && remaining_secondary > 0) {
                    --remaining_secondary;
                    if (remaining_secondary <= 0) {
                        if (!finalize(false)) return false;
                        current = {};
                    }
                } else {
                    if (!finalize(false)) return false;
                    current = {};
                }
            }
        }
        return finalize(false);
    }
};
 
}
 
bool FilesystemRecovery::recover_supported_filesystems(DiskReader& reader,
                                                       const ScanReport& report,
                                                       const std::string& output_dir,
                                                       std::vector<RecoveredFileRecord>& recovered,
                                                       std::vector<std::string>& logs,
                                                       std::string& error) {
    std::set<uint64_t> ntfs_offsets;
    std::set<uint64_t> fat32_offsets;
    std::set<uint64_t> exfat_offsets;
    std::set<uint64_t> ext4_offsets;
    std::set<uint64_t> btrfs_offsets;
    std::set<uint64_t> xfs_offsets;
    std::set<uint64_t> hfs_offsets;
    for (const auto& r : report.results) {
        if (r.type == "NTFS volume" || r.type == "Lost NTFS partition candidate" || r.type == "NTFS candidate") ntfs_offsets.insert(r.offset_bytes);
        if (r.type == "FAT32 volume" || r.type == "Lost FAT32 partition candidate") fat32_offsets.insert(r.offset_bytes);
        if (r.type == "exFAT volume" || r.type == "Lost exFAT partition candidate") exfat_offsets.insert(r.offset_bytes);
        if (r.type == "ext4 volume" || r.type == "Lost ext4 partition candidate" || r.type == "ext4 candidate") ext4_offsets.insert(r.offset_bytes);
        if (r.type == "Btrfs volume" || r.type == "Lost Btrfs partition candidate" || r.type == "Btrfs candidate") btrfs_offsets.insert(r.offset_bytes);
        if (r.type == "XFS volume"   || r.type == "Lost XFS partition candidate")   xfs_offsets.insert(r.offset_bytes);
        if (r.type == "HFS+ volume"  || r.type == "HFSX volume" || r.type == "Lost HFS+ partition candidate") hfs_offsets.insert(r.offset_bytes);
    }
 
    try {
        fs::create_directories(fs::path(output_dir) / "filesystem_recovered" / "ntfs");
        fs::create_directories(fs::path(output_dir) / "filesystem_recovered" / "fat32");
        fs::create_directories(fs::path(output_dir) / "filesystem_recovered" / "exfat");
        fs::create_directories(fs::path(output_dir) / "filesystem_recovered" / "ext4");
        fs::create_directories(fs::path(output_dir) / "filesystem_recovered" / "btrfs");
        fs::create_directories(fs::path(output_dir) / "filesystem_recovered" / "xfs");
        fs::create_directories(fs::path(output_dir) / "filesystem_recovered" / "hfs");
    } catch (const std::exception& ex) {
        error = ex.what();
        return false;
    }
 
 
    for (uint64_t offset : ntfs_offsets) {
        NtfsRecovery ntfs(reader);
        std::string local_error;
        if (!ntfs.recover(offset, output_dir, recovered, logs, local_error)) {
            logs.push_back(trs("NTFS recovery skipped or failed at offset") + std::string(" ") + std::to_string(offset) + ": " + local_error);
        }
    }
 
    for (uint64_t offset : fat32_offsets) {
        Fat32Recovery fat32(reader);
        const fs::path out_root = fs::path(output_dir) / "filesystem_recovered" / "fat32" / ("offset_" + std::to_string(offset));
        std::string local_error;
        if (!fat32.recover(offset, out_root, recovered, logs, local_error)) {
            logs.push_back(trs("FAT32 recovery skipped or failed at offset") + std::string(" ") + std::to_string(offset) + ": " + local_error);
        }
    }
 
    for (uint64_t offset : exfat_offsets) {
        ExfatRecovery exfat(reader);
        const fs::path out_root = fs::path(output_dir) / "filesystem_recovered" / "exfat" / ("offset_" + std::to_string(offset));
        std::string local_error;
        if (!exfat.recover(offset, out_root, recovered, logs, local_error)) {
            logs.push_back(trs("exFAT recovery skipped or failed at offset") + std::string(" ") + std::to_string(offset) + ": " + local_error);
        }
    }
 
    for (uint64_t offset : ext4_offsets) {
        Ext4Recovery ext4(reader);
        std::string local_error;
        if (!ext4.recover(offset, output_dir, recovered, logs, local_error)) {
            logs.push_back(trs("ext4 recovery skipped or failed at offset") + std::string(" ") + std::to_string(offset) + ": " + local_error);
        }
    }
 
    for (uint64_t offset : btrfs_offsets) {
        BtrfsRecovery btrfs(reader);
        std::string local_error;
        if (!btrfs.recover(offset, output_dir, recovered, logs, local_error)) {
            logs.push_back(trs("Btrfs recovery skipped or failed at offset") + std::string(" ") + std::to_string(offset) + ": " + local_error);
        }
    }
 
    for (uint64_t offset : xfs_offsets) {
        XfsRecovery xfs(reader);
        std::string local_error;
        if (!xfs.recover(offset, output_dir, recovered, logs, local_error)) {
            logs.push_back(trs("XFS recovery skipped or failed at offset") + std::string(" ") + std::to_string(offset) + ": " + local_error);
        }
    }
 
    for (uint64_t offset : hfs_offsets) {
        HfsRecovery hfs(reader);
        std::string local_error;
        if (!hfs.recover(offset, output_dir, recovered, logs, local_error)) {
            logs.push_back(trs("HFS+ recovery skipped or failed at offset") + std::string(" ") + std::to_string(offset) + ": " + local_error);
        }
    }
 
    // ---- Optional file carving pass ----
    //
    // Carving is opt-in via environment variable BASTIONGUARD_CARVING=1.
    // It runs AFTER all filesystem-specific recovery has been tried,
    // so it complements (not replaces) the per-FS results. The carving
    // pass is filesystem-agnostic: it recognises file content directly
    // by magic-byte signatures and is the right tool for cases where
    // filesystem metadata (MFT/inode table/catalog) is destroyed but
    // content blocks remain intact. It also recovers files with any
    // FS where deletion zeros the metadata but not the data.
    //
    // We make it opt-in (rather than always-on) because:
    //   * On a healthy disk, every file is also recovered by FS-aware
    //     recovery -- carving would produce duplicates.
    //   * Carving has a non-zero false-positive rate.
    //   * Carving is slow on big disks (full sequential scan).
    {
        const char* env = std::getenv("BASTIONGUARD_CARVING");
        if (env != nullptr && env[0] == '1') {
            carving::CarvingOptions opts;
            // Defaults are reasonable (16 GiB scan limit, 500 MiB per
            // file). The user can override these by editing the source
            // for now; a CLI flag is a future addition.
            std::string carve_err;
            const size_t before = recovered.size();
            carving::run_carving(reader, output_dir, opts, recovered,
                                  logs, carve_err);
            const size_t carved = recovered.size() - before;
            if (!carve_err.empty()) {
                logs.push_back(trs("Carving error: ") + carve_err);
            }
            logs.push_back(trs("Carving pass added ") +
                           std::to_string(carved) + trs(" file(s)"));
        }
    }
 
    return true;
}