carving.cpp

Go to the documentation of this file.

// carving.cpp -- magic-signature-based file carving.
 
#include "carving.hpp"
#include "i18n.hpp"
 
#include <algorithm>
#include <array>
#include <cstring>
#include <filesystem>
#include <fstream>
#include <functional>
#include <sstream>
#include <string>
#include <vector>
 
namespace fs = std::filesystem;
 
namespace carving {
 
namespace {
 
// =========================================================================
// Little-endian + big-endian readers
// =========================================================================
 
inline uint16_t le16(const unsigned char* p) {
    return static_cast<uint16_t>(p[0]) |
           (static_cast<uint16_t>(p[1]) << 8);
}
inline 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);
}
inline uint32_t be32(const unsigned char* p) {
    return (static_cast<uint32_t>(p[0]) << 24) |
           (static_cast<uint32_t>(p[1]) << 16) |
           (static_cast<uint32_t>(p[2]) <<  8) |
            static_cast<uint32_t>(p[3]);
}
inline uint64_t be64(const unsigned char* p) {
    return (static_cast<uint64_t>(p[0]) << 56) |
           (static_cast<uint64_t>(p[1]) << 48) |
           (static_cast<uint64_t>(p[2]) << 40) |
           (static_cast<uint64_t>(p[3]) << 32) |
           (static_cast<uint64_t>(p[4]) << 24) |
           (static_cast<uint64_t>(p[5]) << 16) |
           (static_cast<uint64_t>(p[6]) <<  8) |
            static_cast<uint64_t>(p[7]);
}
 
// Find a byte pattern within a buffer; returns offset of first match
// or std::numeric_limits<size_t>::max() if not found.
size_t find_pattern(const unsigned char* buf, size_t buf_len,
                     const unsigned char* pat, size_t pat_len,
                     size_t start = 0) {
    if (pat_len == 0 || pat_len > buf_len) return SIZE_MAX;
    for (size_t i = start; i + pat_len <= buf_len; ++i) {
        if (std::memcmp(buf + i, pat, pat_len) == 0) return i;
    }
    return SIZE_MAX;
}
 
// =========================================================================
// Format detector signature: given a window starting at the magic, and
// a function to read additional bytes from the disk, return:
//   - true if this is a real file (post-validation succeeded)
//   - the size of the file in bytes (size_out)
// =========================================================================
 
// `peek_more` is invoked by the format handler to read MORE bytes from
// the disk past the current window, when the format needs it (e.g.
// to scan for a footer up to N MB ahead). It reads up to `want` bytes
// at the absolute disk offset and writes into `dst`, returning the
// number of bytes actually read (<= want).
using PeekMore = std::function<size_t(uint64_t abs_off, unsigned char* dst,
                                       size_t want)>;
 
struct DetectResult {
    bool ok {false};
    uint64_t size {0};       // file size in bytes
    bool size_is_capped {false};  // true if we hit max_file_size
};
 
struct CarverFormat {
    const char* name;        // e.g. "jpeg"
    const char* extension;   // e.g. "jpg"
    std::vector<unsigned char> magic;
    // The magic does not always appear at offset 0 of the file (e.g.
    // MP4 atoms have 'ftyp' at offset 4). magic_offset_in_file tells
    // us how far back to subtract from the match position to get the
    // actual file start.
    size_t magic_offset_in_file {0};
    // Validator + size finder. window contains at least 64 bytes
    // starting at the file's offset (= match - magic_offset_in_file).
    // The function may call peek_more(disk_offset, buf, want) to read
    // more bytes; disk_offset is the ABSOLUTE disk offset, not relative.
    std::function<DetectResult(const unsigned char* window,
                                size_t window_len,
                                uint64_t file_disk_off,
                                uint64_t max_file_size,
                                PeekMore& peek_more)> detect;
};
 
// =========================================================================
// JPEG: starts with FF D8 FF, ends with FF D9. Most JPEGs have <50 MB
// size. Validation: the third byte must be one of E0..EF (APP marker),
// DB, or another standard JPEG marker -- this filters most random
// 0xFF 0xD8 0xFF byte sequences.
// =========================================================================
 
DetectResult detect_jpeg(const unsigned char* window, size_t window_len,
                          uint64_t file_disk_off,
                          uint64_t max_file_size,
                          PeekMore& peek_more) {
    DetectResult r;
    if (window_len < 4) return r;
    // The 4th byte must be a valid JPEG marker (0xE0..0xEF for APP,
    // or 0xDB for DQT, or 0xC0..0xCF for SOF, or 0xFE for COM).
    const uint8_t b3 = window[3];
    const bool good_marker =
        (b3 >= 0xE0 && b3 <= 0xEF) ||  // APP0..APPF
         b3 == 0xDB ||                  // DQT
        (b3 >= 0xC0 && b3 <= 0xCF) ||  // SOF
         b3 == 0xFE;                    // COM
    if (!good_marker) return r;
 
    // Search for FF D9 footer. Read up to max_file_size in 1 MiB
    // chunks, scanning each for the footer.
    constexpr size_t SCAN_CHUNK = 1024 * 1024;
    constexpr unsigned char footer[2] = { 0xFF, 0xD9 };
 
    // Start by scanning the existing window
    size_t hit = find_pattern(window, window_len, footer, 2, 4);
    if (hit != SIZE_MAX) {
        r.ok = true;
        r.size = hit + 2;
        return r;
    }
 
    // Read more from disk
    std::vector<unsigned char> chunk(SCAN_CHUNK);
    uint64_t cursor = file_disk_off + window_len;
    uint64_t total = window_len;
    // Carry one byte across chunks in case footer straddles boundary
    bool have_carry = (window_len > 0 && window[window_len - 1] == 0xFF);
 
    while (total < max_file_size) {
        size_t got = peek_more(cursor, chunk.data(), SCAN_CHUNK);
        if (got == 0) break;
 
        // Boundary-straddle check
        if (have_carry && got >= 1 && chunk[0] == 0xD9) {
            r.ok = true;
            r.size = total + 1;
            return r;
        }
 
        size_t local = find_pattern(chunk.data(), got, footer, 2);
        if (local != SIZE_MAX) {
            r.ok = true;
            r.size = total + local + 2;
            return r;
        }
        have_carry = (got > 0 && chunk[got - 1] == 0xFF);
        total += got;
        cursor += got;
    }
    // No footer found within max_file_size -- soft-cap at max
    if (total >= max_file_size) {
        r.ok = true;
        r.size = max_file_size;
        r.size_is_capped = true;
        return r;
    }
    return r;
}
 
// =========================================================================
// PNG: 8-byte magic 89 50 4E 47 0D 0A 1A 0A. Structure is a sequence of
// chunks: __be32 length + 4-byte type + length data + __be32 CRC.
// Last chunk has type 'IEND'. We walk the chunk chain (using length
// from each chunk's header) to compute the exact file size.
// =========================================================================
 
DetectResult detect_png(const unsigned char* window, size_t window_len,
                         uint64_t file_disk_off,
                         uint64_t max_file_size,
                         PeekMore& peek_more) {
    DetectResult r;
    constexpr size_t HDR = 8;
    if (window_len < HDR + 8) return r;
 
    // First chunk MUST be IHDR (length 13, type 'IHDR')
    const uint32_t first_len = be32(window + HDR + 0);
    if (first_len != 13) return r;
    if (std::memcmp(window + HDR + 4, "IHDR", 4) != 0) return r;
 
    // Walk chunks. Each chunk is:
    //   __be32 length     (length of DATA, not including these 12 hdr bytes)
    //   4 bytes type
    //   <length> bytes data
    //   __be32 CRC
    // Total chunk size = 12 + length.
    constexpr size_t SCAN_CHUNK = 256 * 1024;
    std::vector<unsigned char> chunk_buf(SCAN_CHUNK);
 
    auto read_at = [&](uint64_t off, unsigned char* dst, size_t want) -> size_t {
        // First try to satisfy from `window` if in range
        if (off >= file_disk_off &&
            off + want <= file_disk_off + window_len) {
            std::memcpy(dst, window + (off - file_disk_off), want);
            return want;
        }
        return peek_more(off, dst, want);
    };
 
    uint64_t pos = HDR;  // file-relative offset of next chunk header
    constexpr int MAX_CHUNKS = 100000;  // sanity cap
    for (int n = 0; n < MAX_CHUNKS; ++n) {
        if (pos + 12 > max_file_size) {
            r.ok = true;
            r.size = max_file_size;
            r.size_is_capped = true;
            return r;
        }
        unsigned char hdr[12];
        if (read_at(file_disk_off + pos, hdr, 12) != 12) return r;
        const uint32_t clen = be32(hdr);
        if (clen > 0x10000000u) return r;  // implausible
        const bool is_iend = std::memcmp(hdr + 4, "IEND", 4) == 0;
        // Chunk total size = 12 (hdr+CRC) + clen
        pos += 12 + clen;
        if (is_iend) {
            r.ok = true;
            r.size = pos;
            return r;
        }
        if (pos > max_file_size) {
            r.ok = true;
            r.size = max_file_size;
            r.size_is_capped = true;
            return r;
        }
    }
    return r;
}
 
// =========================================================================
// GIF: 6-byte magic GIF87a or GIF89a. Trailer = 0x3B. We scan for 0x3B
// followed by reasonable end (i.e. NOT followed by a continuation byte).
// Simplification: scan to first 0x3B that is preceded by typical block
// terminator (0x00). False-positive rate higher than for PNG; we keep
// it but tag as "carved-gif".
// =========================================================================
 
DetectResult detect_gif(const unsigned char* window, size_t window_len,
                         uint64_t file_disk_off,
                         uint64_t max_file_size,
                         PeekMore& peek_more) {
    DetectResult r;
    // Validate the logical screen descriptor immediately follows the magic
    if (window_len < 13) return r;
    // The byte at offset 10 is the packed field; bit 7 = global color
    // table flag, bits 0-2 = color resolution (must be 0..7). We don't
    // strictly validate; just sanity-check that bytes 10..12 are not
    // all the same (a degenerate value is suspicious).
    if (window[10] == window[11] && window[11] == window[12]
        && (window[10] == 0x00 || window[10] == 0xFF)) return r;
 
    // Scan for trailer 0x3B
    constexpr size_t SCAN_CHUNK = 256 * 1024;
    std::vector<unsigned char> chunk(SCAN_CHUNK);
    constexpr unsigned char trailer = 0x3B;
 
    // Existing window first
    for (size_t i = 13; i < window_len; ++i) {
        if (window[i] == trailer && i > 0 && window[i - 1] == 0x00) {
            r.ok = true;
            r.size = i + 1;
            return r;
        }
    }
    uint64_t total = window_len;
    uint64_t cursor = file_disk_off + window_len;
    unsigned char prev_last = window_len > 0 ? window[window_len - 1] : 0;
    while (total < max_file_size) {
        size_t got = peek_more(cursor, chunk.data(), SCAN_CHUNK);
        if (got == 0) break;
        for (size_t i = 0; i < got; ++i) {
            const unsigned char prev = (i == 0) ? prev_last : chunk[i - 1];
            if (chunk[i] == trailer && prev == 0x00) {
                r.ok = true;
                r.size = total + i + 1;
                return r;
            }
        }
        prev_last = chunk[got - 1];
        total += got;
        cursor += got;
    }
    return r;
}
 
// =========================================================================
// PDF: starts with "%PDF-". Ends with "%%EOF" (often followed by some
// whitespace / EOL). Some PDFs are LINEARIZED with a different layout
// but %%EOF still appears at the end. We scan for the LAST %%EOF
// within max_file_size.
// =========================================================================
 
DetectResult detect_pdf(const unsigned char* window, size_t window_len,
                         uint64_t file_disk_off,
                         uint64_t max_file_size,
                         PeekMore& peek_more) {
    DetectResult r;
    // Sanity: byte at offset 5 must be a digit (PDF version "%PDF-1.x")
    if (window_len < 8) return r;
    if (window[5] != '1' && window[5] != '2') return r;
    if (window[6] != '.') return r;
 
    constexpr size_t SCAN_CHUNK = 1024 * 1024;
    std::vector<unsigned char> chunk(SCAN_CHUNK);
    constexpr unsigned char eof[5] = {'%', '%', 'E', 'O', 'F'};
 
    // Last-occurrence scan: keep updating last_eof_at as we read more.
    uint64_t last_eof_end = 0;  // byte offset within file (1-past)
 
    // Scan window first
    for (size_t i = 0; i + 5 <= window_len; ++i) {
        if (std::memcmp(window + i, eof, 5) == 0) {
            last_eof_end = i + 5;
        }
    }
    uint64_t total = window_len;
    uint64_t cursor = file_disk_off + window_len;
    // Carry the last 4 bytes across chunks for boundary handling
    unsigned char carry[4] = {0, 0, 0, 0};
    size_t carry_len = std::min<size_t>(4, window_len);
    if (window_len > 0) {
        std::memcpy(carry, window + window_len - carry_len, carry_len);
    }
 
    while (total < max_file_size) {
        size_t got = peek_more(cursor, chunk.data(), SCAN_CHUNK);
        if (got == 0) break;
        // Build a small temp buffer (carry + first 4 bytes of chunk) for
        // boundary scan
        std::vector<unsigned char> bnd(carry_len + std::min<size_t>(got, 4));
        std::memcpy(bnd.data(), carry, carry_len);
        std::memcpy(bnd.data() + carry_len, chunk.data(),
                    std::min<size_t>(got, 4));
        for (size_t i = 0; i + 5 <= bnd.size(); ++i) {
            if (std::memcmp(bnd.data() + i, eof, 5) == 0) {
                // Translate position to file offset
                last_eof_end = total - carry_len + i + 5;
            }
        }
        // Scan main chunk
        for (size_t i = 0; i + 5 <= got; ++i) {
            if (std::memcmp(chunk.data() + i, eof, 5) == 0) {
                last_eof_end = total + i + 5;
            }
        }
        carry_len = std::min<size_t>(4, got);
        std::memcpy(carry, chunk.data() + got - carry_len, carry_len);
        total += got;
        cursor += got;
    }
 
    if (last_eof_end > 0) {
        // Round up to next newline if any (PDFs commonly have %%EOF\n)
        r.ok = true;
        r.size = last_eof_end;
        // Try to include trailing CR/LF (up to 2 bytes)
        unsigned char tail[2];
        if (peek_more(file_disk_off + last_eof_end, tail, 2) > 0) {
            int extra = 0;
            if (tail[0] == '\r' || tail[0] == '\n') ++extra;
            if (extra == 1 && (tail[1] == '\r' || tail[1] == '\n')) ++extra;
            r.size += extra;
        }
        if (r.size > max_file_size) { r.size = max_file_size; r.size_is_capped = true; }
        return r;
    }
    return r;
}
 
// =========================================================================
// ZIP family (also DOCX, XLSX, PPTX, JAR, APK, ODT): "PK\x03\x04" at
// start. End-of-central-directory (EOCD) record starts with "PK\x05\x06"
// near the end of the file. EOCD has a fixed prefix of 22 bytes plus a
// variable-length comment.
// =========================================================================
 
DetectResult detect_zip(const unsigned char* window, size_t window_len,
                         uint64_t file_disk_off,
                         uint64_t max_file_size,
                         PeekMore& peek_more) {
    DetectResult r;
    if (window_len < 30) return r;
    // Local file header: PK\x03\x04 + version (2) + flags (2) + method (2) +
    // mod_time (2) + mod_date (2) + crc (4) + comp_size (4) + uncomp_size (4)
    // + name_length (2) + extra_length (2). Sanity: method must be 0..15
    // (most commonly 0, 8). Higher values are rare and suspicious.
    const uint16_t method = le16(window + 8);
    if (method > 99) return r;  // implausible
 
    // Scan for EOCD: "PK\x05\x06"
    constexpr unsigned char eocd[4] = {0x50, 0x4B, 0x05, 0x06};
    constexpr size_t SCAN_CHUNK = 1024 * 1024;
    std::vector<unsigned char> chunk(SCAN_CHUNK);
 
    uint64_t last_eocd_off = 0;  // file-relative
    bool found = false;
 
    for (size_t i = 0; i + 4 <= window_len; ++i) {
        if (std::memcmp(window + i, eocd, 4) == 0) {
            last_eocd_off = i;
            found = true;
        }
    }
    uint64_t total = window_len;
    uint64_t cursor = file_disk_off + window_len;
    unsigned char carry[3] = {0, 0, 0};
    size_t carry_len = std::min<size_t>(3, window_len);
    if (window_len > 0) {
        std::memcpy(carry, window + window_len - carry_len, carry_len);
    }
    while (total < max_file_size) {
        size_t got = peek_more(cursor, chunk.data(), SCAN_CHUNK);
        if (got == 0) break;
        std::vector<unsigned char> bnd(carry_len + std::min<size_t>(got, 3));
        std::memcpy(bnd.data(), carry, carry_len);
        std::memcpy(bnd.data() + carry_len, chunk.data(),
                    std::min<size_t>(got, 3));
        for (size_t i = 0; i + 4 <= bnd.size(); ++i) {
            if (std::memcmp(bnd.data() + i, eocd, 4) == 0) {
                last_eocd_off = total - carry_len + i;
                found = true;
            }
        }
        for (size_t i = 0; i + 4 <= got; ++i) {
            if (std::memcmp(chunk.data() + i, eocd, 4) == 0) {
                last_eocd_off = total + i;
                found = true;
            }
        }
        carry_len = std::min<size_t>(3, got);
        std::memcpy(carry, chunk.data() + got - carry_len, carry_len);
        total += got;
        cursor += got;
    }
 
    if (!found) return r;
 
    // Read the EOCD to determine the comment length, then file size.
    // EOCD layout:
    //   0  PK\x05\x06
    //   4  __le16 disk_num
    //   6  __le16 disk_with_cd
    //   8  __le16 entries_on_this_disk
    //  10  __le16 entries_total
    //  12  __le32 cd_size
    //  16  __le32 cd_offset
    //  20  __le16 comment_length
    //  22  comment[comment_length]
    unsigned char eocd_hdr[22];
    if (peek_more(file_disk_off + last_eocd_off, eocd_hdr, 22) != 22) return r;
    const uint16_t comment_len = le16(eocd_hdr + 20);
    const uint64_t total_size = last_eocd_off + 22 + comment_len;
    if (total_size > max_file_size) {
        r.ok = true;
        r.size = max_file_size;
        r.size_is_capped = true;
        return r;
    }
    r.ok = true;
    r.size = total_size;
    return r;
}
 
// =========================================================================
// BMP: 2-byte magic "BM". Bytes 2..6 (little-endian uint32) hold the
// file size IN THE HEADER.
// =========================================================================
 
DetectResult detect_bmp(const unsigned char* window, size_t window_len,
                         uint64_t /*file_disk_off*/,
                         uint64_t max_file_size,
                         PeekMore& /*peek_more*/) {
    DetectResult r;
    if (window_len < 14) return r;
    const uint32_t fsz = le32(window + 2);
    // DIB header size at offset 14 must be one of the standard values
    // (12, 40, 52, 56, 64, 108, 124).
    if (window_len < 18) return r;
    const uint32_t dib_size = le32(window + 14);
    static const uint32_t valid_dib[] = {12, 40, 52, 56, 64, 108, 124};
    bool dib_ok = false;
    for (uint32_t v : valid_dib) if (dib_size == v) { dib_ok = true; break; }
    if (!dib_ok) return r;
    if (fsz < 26 || fsz > max_file_size) {
        if (fsz > max_file_size) {
            r.ok = true;
            r.size = max_file_size;
            r.size_is_capped = true;
            return r;
        }
        return r;
    }
    r.ok = true;
    r.size = fsz;
    return r;
}
 
// =========================================================================
// MP4 / MOV: each "atom" is __be32 size + 4-byte type. The first atom
// is usually 'ftyp' at offset 0 (size 16..32 bytes typically). We walk
// atoms summing their sizes to find the real file end.
// Magic match: "ftyp" at offset 4; we re-base file_disk_off to the
// preceding 4 bytes (the size field).
// =========================================================================
 
DetectResult detect_mp4(const unsigned char* window, size_t window_len,
                         uint64_t file_disk_off,
                         uint64_t max_file_size,
                         PeekMore& peek_more) {
    DetectResult r;
    if (window_len < 16) return r;
    // First atom: size (4 BE) + 'ftyp' (4)
    const uint32_t atom1_size = be32(window);
    if (atom1_size < 8 || atom1_size > 1024) return r;
    if (std::memcmp(window + 4, "ftyp", 4) != 0) return r;
 
    // The major brand at offset 8..12 should be ASCII alphanumeric
    // (e.g. "isom", "mp42", "qt  ", "M4A ", "M4V ", "iso2"). Filter
    // junk.
    bool brand_ok = true;
    for (int i = 0; i < 4; ++i) {
        const unsigned char c = window[8 + i];
        if (!(c == ' ' || (c >= '0' && c <= '9') ||
              (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'))) {
            brand_ok = false;
            break;
        }
    }
    if (!brand_ok) return r;
 
    // Walk atoms
    constexpr int MAX_ATOMS = 10000;
    uint64_t pos = 0;
    for (int n = 0; n < MAX_ATOMS; ++n) {
        if (pos + 8 > max_file_size) {
            r.ok = true;
            r.size = max_file_size;
            r.size_is_capped = true;
            return r;
        }
        unsigned char hdr[16];
        // Read atom header
        size_t got = 0;
        if (pos + 8 <= window_len) {
            std::memcpy(hdr, window + pos, 8);
            got = 8;
        } else {
            got = peek_more(file_disk_off + pos, hdr, 16);
        }
        if (got < 8) return r;
        uint64_t atom_size = be32(hdr);
        if (atom_size == 1) {
            // Extended 64-bit size at offset 8..16
            if (got < 16) {
                got += peek_more(file_disk_off + pos + 8, hdr + 8, 8);
            }
            if (got < 16) return r;
            atom_size = be64(hdr + 8);
        } else if (atom_size == 0) {
            // 0 means "to end of file" -- not useful for carving
            r.ok = true;
            r.size = std::min<uint64_t>(max_file_size, pos + 8);
            return r;
        }
        if (atom_size < 8 || atom_size > max_file_size) return r;
        pos += atom_size;
        if (pos > max_file_size) {
            r.ok = true;
            r.size = max_file_size;
            r.size_is_capped = true;
            return r;
        }
    }
    return r;
}
 
// =========================================================================
// MP3 (MPEG audio): two possible starts:
//   - "ID3" (3 bytes) if there's an ID3v2 tag prefix
//   - 0xFF 0xFx (frame sync) if there's no tag
// We handle BOTH magics. The handler walks MPEG frames to determine
// the file size by summing frame lengths until we hit non-MP3 bytes.
// =========================================================================
 
DetectResult detect_mp3_id3(const unsigned char* window, size_t window_len,
                             uint64_t /*file_disk_off*/,
                             uint64_t max_file_size,
                             PeekMore& /*peek_more*/) {
    DetectResult r;
    if (window_len < 10) return r;
    // ID3v2 header layout (10 bytes):
    //   "ID3" (3)
    //   version (2)
    //   flags (1)
    //   size (4 bytes, syncsafe: each byte uses 7 bits)
    if (window[3] == 0xFF || window[4] == 0xFF) return r;  // implausible version
    // Syncsafe size decoding
    const uint32_t s0 = window[6] & 0x7F;
    const uint32_t s1 = window[7] & 0x7F;
    const uint32_t s2 = window[8] & 0x7F;
    const uint32_t s3 = window[9] & 0x7F;
    const uint32_t tag_size = (s0 << 21) | (s1 << 14) | (s2 << 7) | s3;
    // Total ID3v2 prefix = 10 + tag_size. After that should come MP3
    // frames. We don't try to walk frames -- we assume the whole file
    // is one MP3 stream and use a heuristic cap.
    const uint64_t prefix = 10 + tag_size;
    // Most MP3 files are 1-15 MB; cap at 30 MB for safety.
    constexpr uint64_t MP3_HARD_CAP = 30ull * 1024 * 1024;
    const uint64_t cap = std::min<uint64_t>(MP3_HARD_CAP, max_file_size);
    if (prefix > cap) return r;
    r.ok = true;
    r.size = cap;
    r.size_is_capped = true;
    return r;
}
 
DetectResult detect_mp3_frame(const unsigned char* window, size_t window_len,
                                uint64_t /*file_disk_off*/,
                                uint64_t max_file_size,
                                PeekMore& /*peek_more*/) {
    DetectResult r;
    if (window_len < 4) return r;
    // 11-bit frame sync (0xFFE..0xFFF) followed by version (2 bits, must
    // be 00 or 11 -- 01 reserved), layer (2 bits, 01..11 -- 00 reserved),
    // protection bit. We accept only V1/V2/V2.5 + Layer III commonly.
    const uint8_t b1 = window[1];
    const uint8_t b2 = window[2];
    if ((b1 & 0xE0) != 0xE0) return r;
    const uint8_t version = (b1 >> 3) & 0x03;
    const uint8_t layer = (b1 >> 1) & 0x03;
    if (version == 0x01) return r;  // reserved
    if (layer == 0x00) return r;     // reserved
    const uint8_t bitrate_idx = (b2 >> 4) & 0x0F;
    const uint8_t sample_idx = (b2 >> 2) & 0x03;
    if (bitrate_idx == 0x0F || sample_idx == 0x03) return r;  // bad
    // We don't walk frames. Use a heuristic file-size cap.
    constexpr uint64_t MP3_HARD_CAP = 30ull * 1024 * 1024;
    r.ok = true;
    r.size = std::min<uint64_t>(MP3_HARD_CAP, max_file_size);
    r.size_is_capped = true;
    return r;
}
 
// =========================================================================
// OGG: pages start with "OggS" + 1 byte version + 1 byte header_type +
// 8 bytes granule + 4 bytes serial + 4 bytes seq + 4 bytes CRC + 1 byte
// segments + segments[]. We walk pages summing their sizes until we
// stop seeing OggS or hit a stop condition (header_type bit 2 = end).
// =========================================================================
 
DetectResult detect_ogg(const unsigned char* window, size_t window_len,
                         uint64_t file_disk_off,
                         uint64_t max_file_size,
                         PeekMore& peek_more) {
    DetectResult r;
    if (window_len < 27) return r;
    // Stream structure version must be 0
    if (window[4] != 0x00) return r;
 
    auto read_at = [&](uint64_t off, unsigned char* dst, size_t want) -> size_t {
        if (off >= file_disk_off &&
            off + want <= file_disk_off + window_len) {
            std::memcpy(dst, window + (off - file_disk_off), want);
            return want;
        }
        return peek_more(off, dst, want);
    };
 
    uint64_t pos = 0;
    constexpr int MAX_PAGES = 100000;
    for (int n = 0; n < MAX_PAGES; ++n) {
        if (pos + 27 > max_file_size) {
            r.ok = true;
            r.size = max_file_size;
            r.size_is_capped = true;
            return r;
        }
        unsigned char hdr[27];
        if (read_at(file_disk_off + pos, hdr, 27) != 27) {
            // EOF -- accept what we have
            if (pos > 0) {
                r.ok = true;
                r.size = pos;
                return r;
            }
            return r;
        }
        if (std::memcmp(hdr, "OggS", 4) != 0) {
            // No more pages
            if (pos > 0) {
                r.ok = true;
                r.size = pos;
                return r;
            }
            return r;
        }
        const uint8_t header_type = hdr[5];
        const uint8_t segment_count = hdr[26];
        // Read segment_table
        std::vector<unsigned char> seg_table(segment_count);
        if (segment_count > 0 &&
            read_at(file_disk_off + pos + 27, seg_table.data(),
                     segment_count) != segment_count) return r;
        uint32_t body_size = 0;
        for (uint8_t i = 0; i < segment_count; ++i) body_size += seg_table[i];
        const uint64_t page_size = 27 + segment_count + body_size;
        pos += page_size;
        // header_type bit 2 = "last page of bitstream"
        if (header_type & 0x04) {
            r.ok = true;
            r.size = pos;
            return r;
        }
    }
    return r;
}
 
// =========================================================================
// TIFF: starts with "II*\x00" (little-endian) or "MM\x00*" (big-endian).
// We DO NOT walk the IFD chain (would be ~200 lines and risk false
// positives on corrupted IFDs). Instead we use a heuristic size cap of
// 50 MB which fits virtually all photographic TIFFs.
// =========================================================================
 
DetectResult detect_tiff(const unsigned char* window, size_t window_len,
                          uint64_t /*file_disk_off*/,
                          uint64_t max_file_size,
                          PeekMore& /*peek_more*/) {
    DetectResult r;
    if (window_len < 8) return r;
    // The 4-byte IFD offset must be plausible (>= 8 for a real TIFF)
    const bool little_endian = (window[0] == 'I');
    const uint32_t ifd_off = little_endian
                              ? le32(window + 4)
                              : be32(window + 4);
    if (ifd_off < 8 || ifd_off > 100ull * 1024 * 1024) return r;
    constexpr uint64_t TIFF_HARD_CAP = 50ull * 1024 * 1024;
    r.ok = true;
    r.size = std::min<uint64_t>(TIFF_HARD_CAP, max_file_size);
    r.size_is_capped = true;
    return r;
}
 
// =========================================================================
// OLE Compound File (DOC/XLS/PPT old format, MSI installer files):
// magic D0 CF 11 E0 A1 B1 1A E1. The header has sector size (= 1<<sec_shift)
// and we use that to estimate the file size. Compound files are
// allocated in sectors with a Sector Allocation Table; without parsing
// the SAT we use a heuristic cap.
// =========================================================================
 
DetectResult detect_ole(const unsigned char* window, size_t window_len,
                         uint64_t /*file_disk_off*/,
                         uint64_t max_file_size,
                         PeekMore& /*peek_more*/) {
    DetectResult r;
    if (window_len < 76) return r;
    // Sector shift at offset 30 (LE16): typically 9 (=512-byte sectors)
    // or 12 (=4096-byte sectors). Other values are bogus.
    const uint16_t sec_shift = le16(window + 30);
    if (sec_shift != 9 && sec_shift != 12) return r;
    // Number of sectors in directory-stream FAT chain at offset 40:
    // a sanity bound.
    const uint32_t num_dir_sectors = le32(window + 40);
    if (num_dir_sectors > 100000) return r;
    // Heuristic: 100 MB cap. Real Office files are usually <50 MB.
    constexpr uint64_t OLE_HARD_CAP = 100ull * 1024 * 1024;
    r.ok = true;
    r.size = std::min<uint64_t>(OLE_HARD_CAP, max_file_size);
    r.size_is_capped = true;
    return r;
}
 
// =========================================================================
// RIFF (WAV/AVI/WEBP): "RIFF" + le32 size + 4-byte form type. We
// dispatch on the form type to avoid duplicate magic detection.
// =========================================================================
 
DetectResult detect_riff(const unsigned char* window, size_t window_len,
                          uint64_t /*file_disk_off*/,
                          uint64_t max_file_size,
                          PeekMore& /*peek_more*/) {
    DetectResult r;
    if (window_len < 12) return r;
    // Check the form type at offset 8: WAVE, AVI , WEBP are accepted.
    const bool is_wav = std::memcmp(window + 8, "WAVE", 4) == 0;
    const bool is_avi = std::memcmp(window + 8, "AVI ", 4) == 0;
    const bool is_webp = std::memcmp(window + 8, "WEBP", 4) == 0;
    if (!is_wav && !is_avi && !is_webp) return r;
    const uint32_t riff_size = le32(window + 4);
    if (riff_size < 4) return r;
    const uint64_t total = static_cast<uint64_t>(riff_size) + 8;
    if (total > max_file_size) {
        r.ok = true;
        r.size = max_file_size;
        r.size_is_capped = true;
        return r;
    }
    r.ok = true;
    r.size = total;
    return r;
}
 
// =========================================================================
// MP3 frame: 11-bit sync followed by version + layer + protection bits.
// (kept for reference; replaced by the unified detect_riff for WAV/AVI)
// =========================================================================
 
// =========================================================================
// MKV / WebM (Matroska / EBML): magic 1A 45 DF A3 (EBML header).
// The EBML format is variable-length-integer-based -- a full walk is
// hundreds of lines. We use a heuristic cap: 4 GB max (these are big).
// =========================================================================
 
DetectResult detect_mkv(const unsigned char* window, size_t window_len,
                         uint64_t /*file_disk_off*/,
                         uint64_t max_file_size,
                         PeekMore& /*peek_more*/) {
    DetectResult r;
    if (window_len < 16) return r;
    // After the 4-byte EBML header magic, the next byte starts the
    // EBML header VINT. The first byte should have at least one set
    // bit indicating length; common is 0x9F for a small EBML header.
    // Filter out clearly-bogus follow-ups.
    if (window[4] == 0x00) return r;
    constexpr uint64_t MKV_HARD_CAP = 4ull * 1024 * 1024 * 1024;  // 4 GB
    r.ok = true;
    r.size = std::min<uint64_t>(MKV_HARD_CAP, max_file_size);
    r.size_is_capped = true;
    return r;
}
 
// =========================================================================
// SQLite database: magic "SQLite format 3\x00" (16 bytes). The header
// has page size at offset 16 (BE16) and total page count at offset 28
// (BE32). File size = page_size * page_count (exact).
// =========================================================================
 
DetectResult detect_sqlite(const unsigned char* window, size_t window_len,
                            uint64_t /*file_disk_off*/,
                            uint64_t max_file_size,
                            PeekMore& /*peek_more*/) {
    DetectResult r;
    if (window_len < 100) return r;
    // Page size at offset 16: BE16. Either a power of 2 in [512, 32768]
    // or 1 (= 65536, special encoding).
    const uint16_t ps_field = (static_cast<uint16_t>(window[16]) << 8) | window[17];
    uint32_t page_size = 0;
    if (ps_field == 1) {
        page_size = 65536;
    } else {
        page_size = ps_field;
        if (page_size < 512 || page_size > 32768) return r;
        if ((page_size & (page_size - 1)) != 0) return r;  // not pow2
    }
    // Page count at offset 28 (BE32)
    const uint32_t page_count =
        (static_cast<uint32_t>(window[28]) << 24) |
        (static_cast<uint32_t>(window[29]) << 16) |
        (static_cast<uint32_t>(window[30]) <<  8) |
         static_cast<uint32_t>(window[31]);
    if (page_count == 0) return r;
    const uint64_t total = static_cast<uint64_t>(page_size) * page_count;
    if (total > max_file_size) {
        r.ok = true;
        r.size = max_file_size;
        r.size_is_capped = true;
        return r;
    }
    r.ok = true;
    r.size = total;
    return r;
}
 
// =========================================================================
// Build the format table.
// =========================================================================
 
std::vector<CarverFormat> build_formats() {
    std::vector<CarverFormat> v;
    v.push_back({"jpeg", "jpg",
                  {0xFF, 0xD8, 0xFF}, 0, &detect_jpeg});
    v.push_back({"png",  "png",
                  {0x89, 0x50, 0x4E, 0x47, 0x0D, 0x0A, 0x1A, 0x0A}, 0,
                  &detect_png});
    v.push_back({"gif",  "gif",
                  {'G','I','F','8','9','a'}, 0, &detect_gif});
    v.push_back({"gif87","gif",
                  {'G','I','F','8','7','a'}, 0, &detect_gif});
    v.push_back({"pdf",  "pdf",
                  {'%','P','D','F','-'}, 0, &detect_pdf});
    v.push_back({"zip",  "zip",
                  {'P','K',0x03,0x04}, 0, &detect_zip});
    v.push_back({"bmp",  "bmp",
                  {'B','M'}, 0, &detect_bmp});
    // RIFF unified (WAV / AVI / WEBP). Extension is set generically;
    // in a future version we could inspect the form type to pick a
    // better extension (.wav vs .avi vs .webp).
    v.push_back({"riff", "riff",
                  {'R','I','F','F'}, 0, &detect_riff});
    v.push_back({"mp4",  "mp4",
                  {'f','t','y','p'}, 4, &detect_mp4});
    // ---- New formats added in this package ----
    v.push_back({"mp3-id3", "mp3",
                  {'I','D','3'}, 0, &detect_mp3_id3});
    // MP3 frame-sync pairs: try the most common (MPEG-1 Layer III) only,
    // 0xFF 0xFB.  Other variants exist but the false-positive rate
    // gets too high if we accept all of 0xFF 0xFx.
    v.push_back({"mp3-frame", "mp3",
                  {0xFF, 0xFB}, 0, &detect_mp3_frame});
    v.push_back({"mp3-frame-mpeg2", "mp3",
                  {0xFF, 0xF3}, 0, &detect_mp3_frame});
    v.push_back({"ogg",  "ogg",
                  {'O','g','g','S'}, 0, &detect_ogg});
    v.push_back({"tiff-le", "tif",
                  {'I','I',0x2A,0x00}, 0, &detect_tiff});
    v.push_back({"tiff-be", "tif",
                  {'M','M',0x00,0x2A}, 0, &detect_tiff});
    // OLE Compound File (DOC, XLS, PPT old, MSI)
    v.push_back({"ole-cf", "ole",
                  {0xD0,0xCF,0x11,0xE0,0xA1,0xB1,0x1A,0xE1}, 0,
                  &detect_ole});
    // Note: AVI is handled by the unified detect_riff above
    v.push_back({"mkv",  "mkv",
                  {0x1A,0x45,0xDF,0xA3}, 0, &detect_mkv});
    v.push_back({"sqlite", "sqlite",
                  {'S','Q','L','i','t','e',' ','f','o','r','m','a','t',
                   ' ','3',0x00}, 0, &detect_sqlite});
    return v;
}
 
} // anonymous namespace
 
bool run_carving(DiskReader& reader,
                 const std::string& output_dir,
                 const CarvingOptions& opts,
                 std::vector<RecoveredFileRecord>& recovered,
                 std::vector<std::string>& logs,
                 std::string& error) {
    const uint64_t disk_size = reader.size();
    if (disk_size == 0) {
        error = "Carving: disk size is zero";
        return false;
    }
    const uint64_t scan_limit = opts.max_bytes_to_scan == 0
                                 ? disk_size
                                 : std::min<uint64_t>(disk_size,
                                                      opts.max_bytes_to_scan);
 
    fs::path out_root = fs::path(output_dir) / "carved";
    {
        std::error_code ec;
        fs::create_directories(out_root, ec);
    }
 
    auto formats = build_formats();
    // Compute the longest magic to determine sliding overlap
    size_t longest_magic = 0;
    for (const auto& f : formats) {
        const size_t needed = f.magic.size() + f.magic_offset_in_file;
        if (needed > longest_magic) longest_magic = needed;
    }
    // Window size: 16 MiB main + overlap of `longest_magic` for boundary
    constexpr size_t MAIN_WINDOW = 16 * 1024 * 1024;
    const size_t overlap = longest_magic;
    std::vector<unsigned char> window(MAIN_WINDOW + overlap);
 
    size_t carved_count = 0;
    uint64_t pos = 0;
    int ident_counter = 0;
 
    auto peek_more = [&](uint64_t abs_off, unsigned char* dst,
                          size_t want) -> size_t {
        if (abs_off >= disk_size) return 0;
        const size_t can = static_cast<size_t>(
            std::min<uint64_t>(want, disk_size - abs_off));
        return reader.read_at(abs_off, dst, can) ? can : 0;
    };
 
    logs.push_back(trs("Carving: starting scan up to ") +
                   std::to_string(scan_limit / (1024 * 1024)) + " MiB");
 
    while (pos < scan_limit) {
        const size_t want = static_cast<size_t>(
            std::min<uint64_t>(window.size(), scan_limit - pos));
        if (!reader.read_at(pos, window.data(), want)) {
            logs.push_back(trs("Carving: read failure at offset ") +
                           std::to_string(pos) + trs(", skipping ahead"));
            pos += MAIN_WINDOW;
            continue;
        }
        // Scan only the main portion; the overlap will be re-scanned
        // at the start of the next window.
        const size_t scan_end = (want > overlap) ? (want - overlap) : want;
        // For the final window (we cannot read more) scan everything
        const bool last = (pos + want >= scan_limit);
        const size_t actual_end = last ? want : scan_end;
 
        for (size_t i = 0; i < actual_end; ++i) {
            for (const auto& f : formats) {
                const size_t mlen = f.magic.size();
                if (i + mlen > want) continue;
                if (std::memcmp(window.data() + i, f.magic.data(), mlen) != 0)
                    continue;
                // Magic found. Compute the file's start position.
                if (i < f.magic_offset_in_file) continue;
                const size_t file_local_start = i - f.magic_offset_in_file;
                const uint64_t file_disk_off = pos + file_local_start;
 
                // Pass the rest of the window to the detector
                const size_t window_remaining = want - file_local_start;
 
                DetectResult dr = f.detect(
                    window.data() + file_local_start,
                    window_remaining, file_disk_off,
                    opts.max_file_size,
                    const_cast<PeekMore&>(static_cast<const PeekMore&>(peek_more))
                );
 
                if (!dr.ok) continue;
                if (dr.size == 0 || dr.size > opts.max_file_size + 1) continue;
 
                // Write the carved file
                fs::path out_dir = out_root / f.name;
                {
                    std::error_code ec;
                    fs::create_directories(out_dir, ec);
                }
                std::ostringstream nm;
                nm << std::hex << file_disk_off << "_" << ident_counter
                   << "." << f.extension;
                ++ident_counter;
                fs::path out_path = out_dir / nm.str();
 
                std::ofstream out(out_path, std::ios::binary | std::ios::trunc);
                if (!out) continue;
                // Write in chunks
                constexpr size_t WBUF = 1024 * 1024;
                std::vector<unsigned char> wbuf(WBUF);
                uint64_t written = 0;
                while (written < dr.size) {
                    const size_t step = static_cast<size_t>(
                        std::min<uint64_t>(WBUF, dr.size - written));
                    if (!reader.read_at(file_disk_off + written,
                                         wbuf.data(), step)) break;
                    out.write(reinterpret_cast<const char*>(wbuf.data()),
                              static_cast<std::streamsize>(step));
                    written += step;
                }
                out.close();
 
                if (written > 0) {
                    std::string note = "carved-";
                    note += f.name;
                    if (dr.size_is_capped) note += "-capped";
                    recovered.push_back({
                        out_path.string(), "carving",
                        ("carved/" + std::string(f.name) + "/" + nm.str()),
                        written,
                        dr.size_is_capped ? "partial" : "full",
                        note});
                    ++carved_count;
                }
                // After a successful carve, advance i past the file's
                // payload (best-effort; if the user has overlapping
                // content we may miss some files but this is much faster
                // than re-scanning every byte).
                const uint64_t skip_until = file_disk_off + dr.size;
                if (skip_until > pos + i) {
                    const uint64_t skip = skip_until - (pos + i);
                    if (skip > 0 && skip < want - i) {
                        i += static_cast<size_t>(skip - 1);  // -1 because the for-loop ++
                    }
                }
                break;  // do not match this offset against more formats
            }
        }
        pos += MAIN_WINDOW;
    }
 
    {
        std::ostringstream m;
        m << trs("Carving: completed. Files recovered: ") << carved_count;
        logs.push_back(m.str());
    }
    return carved_count > 0;
}
 
} // namespace carving