Member Avatar for BlitzX

I'm writing a program that searches for particular sequences of bytes in a USB stick. The problem is that I don't know how to search effectively. ReadFile() allows me to buffer 512 bytes each time. If my sequence is fully present in that block, then there is no problem. But what if the first byte of my sequence starts at the end of that block, and the rest in the next block?

Visualization:

target="GIF"

block1
000000000000000000
000000000000000000
000000000000000000
00000000000000000G

block2
IF0000000000000000
000000000000000000
000000000000000000
000000000000000000

Edited by BlitzX
  • 3 Contributors
  • 4 Replies
  • 133 Views
  • 4 Hours Discussion Span
  • Latest Post Latest Post by BlitzX

Dani AI

Generated

The core problem is a stream-boundary one: your data is continuous but you read it in blocks. 's overlap idea is a practical fix, but for a cleaner and more scalable approach treat the device as a stream and use a streaming pattern matcher that keeps match state between reads. Knuth-Morris-Pratt (KMP) maintains a failure table so you can feed each new block and resume a partial match without copying trailing bytes; for many patterns use Aho-Corasick; Rabin-Karp is an alternative when you want a rolling-hash approach. See KMP, Aho-Corasick and Rabin-Karp for algorithms and tradeoffs (Knuth-Morris-Pratt, Aho-Corasick, Rabin-Karp).

I/O notes that matter in practice: use much larger reads (tens or hundreds of KB, even MB) to reduce syscall overhead and increase throughput. If you opt into unbuffered I/O on Windows, buffers and sizes must be sector/cluster aligned; consult the Windows file buffering docs before using no-buffering flags (file buffering). Also open the raw device with appropriate sharing and hints (sequential scan) so you do not interfere with the host OS.

If the goal is deleted-file recovery, signature scanning (“carving”) has limits: it finds contiguous files but will fail on fragmentation or when metadata is erased. For reliable recovery parse the filesystem metadata (MFT on NTFS, directory entries on FAT) or use a forensic library/tool that understands those structures. File carving and filesystem-aware parsing are different techniques; tools like The Sleuth Kit implement both and are worth studying (File carving, The Sleuth Kit, ).

Practical quick plan: 1) switch to larger block reads for speed; 2) implement a streaming matcher (KMP or Aho-Corasick) that retains match state across reads; 3) if you need robust recovery, either image the device first or use filesystem parsing libraries rather than pure signature scans. ’s ifstream idea works fine on images, but for raw devices use a streaming match plus the I/O cautions above.

Recommended Answers

All 4 Replies

Member Avatar for DeeperShade

Is it vital that you use ReadFile()?

Would it be easier for you if you used ifstream's .read()?

Member Avatar for BlitzX

I'm reading directly from the disk, so I guess I have to use ReadFile();
I know that I can make an image of the file and use ifstream on it, but I'd like to know how it's done directly.

Member Avatar for WaltP

I'm reading directly from the disk, so I guess I have to use ReadFile();

Why? What does ReadFile() do that any other read technique doesn't do?

To alleviate your real problem, make your buffer larger than 512 -- say 16 more.
Always read into the last 512 of that buffer, leaving the first 16 bytes alone.
Just before reading the next 512 bytes, move the last 16 bytes into the first 16 bytes. You search on the entire 528 bytes.

char buf[528];

read into &buf[16];
compare
move buf[512-527] into buf[0 - 15]
read into &buf[16];
continue...
Member Avatar for BlitzX

I never actually thought of doing that, WaltP. Thanks.
I think I used a bad choice of words. What I meant is that I'm reading raw bytes from the USB device, not individual files. If ifstreams are capable of doing that, then forgive my ignorance. I'll try to fix it by allocating more for the buffer.
Here's a section from my code to shed some light on my problem:

int main()
{


    DISK_GEOMETRY dg;




    LONG size;
     HANDLE hDrive = CreateFile(L"\\\\.\\F:", GENERIC_READ, FILE_SHARE_READ| FILE_SHARE_WRITE, NULL, OPEN_EXISTING, NULL, NULL);


      if (!DeviceIoControl(hDrive, IOCTL_DISK_GET_DRIVE_GEOMETRY, NULL, 0, &dg, sizeof(dg), &buf, (LPOVERLAPPED)NULL))
          MessageBox(NULL,L"Failed",NULL,MB_OK);



      size=dg.SectorsPerTrack*dg.TracksPerCylinder*dg.Cylinders.QuadPart;


    char *lbuffer;
    lbuffer=new char[512];

    DWORD dwBytesRead=0;

        //Beginning and end of GIF files.
    char GIF[]="GIF";
    char END[2];
    END[0]=(0x00);
    END[1]=(0x3b);

    for(int ii=0;ii<size;ii++)
    {
        if(!ReadFile(hDrive, lbuffer,512, &dwBytesRead, NULL))
                    ErrorExit(TEXT("ReadFile1"));



                        //STUCK HERE

    }
}

What I actually want to do is retrieve recently deleted files, but without having to create an image of the disk.

Edited by BlitzX
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.