Engineering · 9 min read
Where a deleted file ends: format-aware carving in Revive
How Revive rebuilds deleted files from raw disk data by walking each format’s structure, and how it rejects bytes that only look like a file.
Published · By Kumar, QuantumPlug Technologies LLP

When a file is deleted, the file system forgets where it was, but its bytes often stay on the disk until something overwrites them. Deep Scan in Revive, the macOS recovery app we build, reads a disk image from start to finish and looks for files in the raw data. This is called carving. Finding where a file starts is the easy part, because most formats begin with a fixed signature. The hard questions are where the file ends, and whether the bytes in between are really its own. This article explains how Revive’s recovery engine answers both questions using each file’s internal structure, and how the same checks reject false positives. Everything described here comes from the shipping Swift code and its test suite.
Why header-and-footer carving falls short
The classic method is to find a header, search forward for a footer and cut the file there. For JPEG, that means everything from FF D8 to FF D9. It fails on ordinary files. A phone photo usually carries an EXIF thumbnail, which is a complete JPEG with its own FF D9, a few kilobytes in, so a footer search returns a file the size of the thumbnail. A PDF that was edited and saved incrementally has several %%EOF markers. A ZIP stored inside another ZIP has its own end record. And on a disk where files were stored in pieces, the bytes between a header and a footer may belong to a different file entirely.
So Revive never trusts a footer on its own. Each of the 17 parsers in FormatParsers.all walks its format’s structure from the header, segment by segment, chunk by chunk or box by box. It returns a CarvedFile with an exact length and a health rating. For a damaged file, it also returns a verifiedLength: how many leading bytes were actually checked against the structure.
One pass that skips most offsets cheaply
A Deep Scan reads its source once, through a SourceReader that serves every parser from the same cache. Data is read in 1 MiB blocks, and the 16 most recently used are kept in memory. As the scan moves forward, a background queue reads the next eight blocks, so disk reads and the decompression of compressed disk images happen while parsing goes on. Pattern searches are memoised, so many candidates searching the same region, such as fragmented ZIP or PDF headers, don’t read it again.
Running 17 parsers at every offset would be far too slow, so each parser declares trigger bytes. Before the scan, the carver builds two flat tables of 65,536 Booleans. One is indexed by the two bytes at the candidate offset. The other is indexed by the two bytes four bytes later, which is where MP4, MOV and HEIC files carry their ftyp box type. The inner loop walks an UnsafeBufferPointer and does two table lookups per offset. Only when a pair is marked does it build a 32-byte Head, run the cheap matches check of the relevant parsers, and then call the full parse.
By default, candidates are checked at every 512-byte boundary, because file systems start files on sector boundaries. Thorough search checks every byte to find unaligned or embedded data. One test places a PNG three bytes after a boundary: the 512-byte scan misses it, and the thorough scan finds it. Every parser runs whatever file types the user selected. That is deliberate: recognising a video or an archive is what stops the photos inside it being reported as separate files. The type filter is applied to the output.
Walking the structure, format by format
The JPEG parser walks segment markers. Any segment with a length field is skipped by its declared length, so the thumbnail inside the EXIF segment is jumped over in one step. After the start of a scan, the parser searches the compressed image data for the next real marker. It handles FF 00 byte stuffing and fill bytes, and requires a frame header and a scan before the end marker. Restart markers must cycle from RST0 to RST7 in order. If they arrive out of sequence, data from elsewhere has been spliced in, and the photo is rated Partial even when its end marker is present.
Where a format carries checksums, we verify them. A PNG’s IHDR CRC must match or the candidate is rejected outright. After that, every chunk’s CRC is checked, and the walk stops at the first one that fails. Ogg pages are checksummed too, but with a different CRC-32: polynomial 0x04C11DB7, not reflected, computed with the checksum field read as zero. We compute it with our own table, because zlib’s crc32 implements the reflected variant that PNG uses. 7-Zip archives are checked against both their start-header CRC and the CRC of the index at the end of the archive.
Containers that declare their own sizes are checked against themselves. For MP4, MOV, M4A, HEIC, AVIF and CR3, the parser walks top-level boxes from an allow-list, and the child boxes of the moov or meta index must fill it exactly. A box of size zero, which means ‘to the end of the file’, ends the walk, because the parser must never consume the rest of a disk. A ZIP’s end-of-central-directory record must point back to its own archive: the directory it describes has to end exactly where the record begins. Up to 24 local headers, sampled across the directory, must also sit where the directory says they are. This check is why a ZIP nested inside another ZIP doesn’t end the outer archive early.
A PDF is followed through its %%EOF markers as long as what comes next is an xref table or an object header. Then the final startxref offset must point at cross-reference data inside the file. If it doesn’t, the middle of the file has been replaced. The page count in a SQLite header is trusted only when the version-valid-for number matches the change counter, which is the rule SQLite’s file format sets. After that, the first bytes of every page must look like a b-tree, overflow, freelist or pointer-map page. A page that doesn’t means the database was stored in pieces.
- TIFF and camera RAW (CR2, NEF, ARW, DNG, ORF, RW2, PEF): every IFD, SubIFD and EXIF IFD is followed to the furthest strip, tile or preview
- Legacy Office documents and Outlook messages: the length comes from the last sector the allocation table marks as used
- Matroska and WebM: an element walk that also handles live recordings whose segment size is unknown
- MP3: consecutive frames must share version, layer and sample rate, and the count is checked against a Xing, Info or VBRI frame count when present
Rejecting things that only look like files
Random data, such as compressed video or encrypted blocks, will sometimes contain a sequence that matches a signature. The matches step filters most of these with tests that random bytes rarely pass. A PNG signature must be followed by an IHDR chunk of length 13. A BMP needs zeroed reserved bytes and a known header size. An MP4 ftyp box must be 16 to 4,096 bytes long, a multiple of four, with a printable brand. In the first directory of a TIFF file, every entry must have a valid field type, and tags must be in ascending order. The candidate is rejected if any type is invalid or more than a quarter of the tags are out of order.
When a parser finds a plausible start but no structure behind it, it returns nothing rather than offering a file that won’t open. A JPEG with no frame header or no scan is dropped. MP3 and AAC need at least five consistent frames, and an Ogg stream that never finishes needs at least four valid pages. The tests make this concrete. FF D8 FF 09 08 FF D9 followed by noise must produce no results, and so must a PNG with one byte flipped in its header.
Claiming bytes, and handling fragments
When a parser returns a structurally complete file, the carver moves its next free offset past the end of that file. The file claims its byte range, and the scan continues after it. That is what keeps an EXIF thumbnail, a JPEG inside a ZIP or the cover art inside an audio file from appearing twice.
Partial files are harder. A photo whose end was overwritten can run on into another file’s data. So a partial file claims only its verifiedLength, which for a JPEG means the headers up to the start of the compressed image data. The scanner keeps looking inside the unverified tail. If another file starts there, the partial file is cut short at that offset, because the tail was really the other file. One test builds a JPEG with its end marker removed, fills the space after it, and places a valid PNG at offset 2,048. The test expects a Partial JPEG covering exactly bytes 0 to 2,048, followed by a Good PNG.
These ratings reach the interface unchanged. Good means the structure checks out from start to end. Partial means only part of the file was found intact, so it may open with parts missing, or not at all. Partial results start unticked, so a bulk recovery doesn’t fill the destination with files that won’t open.
Reading through compressed disk images
The Mac App Store edition runs in the App Sandbox and can’t ask for the administrator rights needed to read a drive sector by sector, so Deep Scan there works on disk images. Disk Utility saves compressed images by default, and carving the compressed file directly would find nothing. UDIFByteSource reads the image’s trailer and its XML block table, then maps every read to the right chunk. Uncompressed chunks are read in place. zlib (UDZO) and LZFSE (ULFO) chunks are decompressed on demand with Apple’s Compression framework, and the last four decoded chunks are kept in memory. Gaps between tables read as zeros, like unallocated sectors.
An encrypted image, or one compressed with bzip2, LZMA or ADC, produces an error that tells the user how to convert it in Disk Utility. The tests don’t rely on hand-built DMGs alone. They call hdiutil to create real UDZO, ULFO and UDRW images containing a photo, carve each one, recover the photo and check that the recovered bytes are identical to the original.
Treating values from the disk as hostile input
Every length, offset and count a parser reads comes from the disk, often from a file that is corrupt or truncated. So none of them is trusted. Sums use addingReportingOverflow or are checked against a maximum size for each format: 256 MiB for JPEG, 4 GiB for ZIP, 64 GiB for MP4 and Matroska. Walks are bounded, too. A TIFF parse visits at most 64 directories, and the search for a ZIP end record stops after 4,096 attempts. A file that runs past the end of the source is cut to what is there and marked Partial. Long walks check for cancellation, so stopping a scan takes effect promptly.
MalformedInputTests fuzzes this. It takes valid fixtures for eight formats, applies one to eight random byte mutations, and appends up to 300 random bytes. By default it runs 800 iterations, with a SplitMix64 generator and a fixed seed so any failure can be reproduced, and FUZZ_ITER and FUZZ_SEED override both. For every result it asserts that the byte range is non-empty, matches the reported size and stays inside the source. Hand-written cases cover specific traps: TIFF 64-bit offsets at the maximum value, a ZIP64 directory offset that would wrap around, a PDF startxref of 18446744073709551615 and a DMG block table with out-of-range sector addresses.
Reading gets the same care. A block that fails to read is re-read in 64 KiB pieces, then 4 KiB pieces. What still fails is filled with zeros and counted, and the scan reports it at the end rather than stopping. A stopped scan returns everything found so far, with an offset it can resume from.
Carving is a parsing problem more than a search problem. Revive gets files back whole because each parser asks the format where it ends and checks whatever evidence the format provides: checksums, directories, indexes and counters. Files that pass are claimed so nothing is listed twice, and files that fail are either dropped or marked Partial with only their verified bytes claimed. Because the input is hostile by definition, the tests concentrate on what happens when the structure lies. That’s the work behind a file that opens properly after recovery.
Common questions
Does Revive change the disk or image it scans?
No. Revive opens scan sources for reading only, through an interface with no write operation. Recovered files are written only to a folder you choose, and Revive refuses a destination inside the source it scanned.
What do the Good and Partial ratings mean?
Good means the file’s internal structure checked out from start to end, so it should open normally. Partial means only part of the file was found intact, often because it was stored in pieces or partly overwritten. Partial files start unticked.
Why does Deep Scan in the Mac App Store version need a disk image?
Reading a whole drive sector by sector needs administrator rights, which sandboxed Mac App Store apps can’t request. You make an image of the drive or card in Disk Utility, and Revive shows you how, then scan the image. You also stop working on the damaged media, which protects what is left on it.