0

[About a month ago I asked a similar question, requesting a specific CLI software tool that would perform the required task ; it was quickly blocked on the ground that asking for specific software tools is forbidden here, based on the justifications that “they become outdated quickly and attract opinion-based answers” — which frankly is absurd, since everything becomes outdated eventually and everything can attract opinion-based answers, and besides, sometimes opinion-based answers are welcome. But someone had the time to post a reply suggesting that this could most likely be done with PowerShell. So now, about a month later, I'm asking how I could use PowerShell to perform that task which was stalled in the mean time.]


I am looking for a PowerShell method to compare the binary contents of two files, starting from different offsets, stop at the first identified difference and report the corresponding offsets. For instance, file A has a size of 500MB, file B has a size of 100MB, it could be determined that the beginning of file B matches file A at offset 104857600, but that (based on a checksum comparison between file B and a 100MB block of file A starting from 104857600) file B is not entirely contained within file A. So now I need to come up with a script that will perform a byte-by-byte comparison between file A starting from offset 104857600 and file B starting from offset 0, then report the offset values of the first mismatched byte.

Windows native CLI tools comp and fc do not allow to set start offsets for the comparison (comp doesn't even allow to compare files with different sizes). Based on this thread I tested diffutils, which doesn't seem to suit those requirements either. It could be done with a hexadecimal editor like WinHex, or dedicated compare / merge GUI utilities like WinMerge, but here a command line utility is required to process hundreds of files at once with a script. The cmp tool described here would seem to do exactly what I need, but it doesn't seem to be available as a standalone Windows executable.

I have very little experience with PowerShell, so I don't know where to begin.


Goal : I made a complete data recovery from a 4TB HDD, both in filesystem analysis mode and in so-called “raw file carving” mode (through file signature search, with Photorec and R-Studio) ; most of the files recovered through the second method are actually duplicates or fragments from files which could be fully recovered through the first method. Full duplicates are easy to identify, there are many dedicated tools for that purpose. I had a harder time identifying file fragments which were entirely contained within another file ; I managed to do that with 1) a PowerShell script to extract a short string from each unidentified file into a plain text list, 2) WinHex to run a “simultaneous search” based on the list of strings, and 3) a PowerShell script to calculate checksums based on the search hits from WinHex. Now I'm left with files for which a match could be found, but which are not perfect matches, meaning that they contain parts of different original files (most likely because the source drive was fragmented). At the end should only remain file fragments which do not have any counterpart within the main recovery directory.


[EDIT 20210401]

MD5 comparison : As mentioned above, I have little experience with PowerShell, so, to do MD5 checksum comparisons I relied on a third-party CLI tool called dsfo (from dsfok), which worked well and probably made the script less convoluted (but I'd be interested to know how the same can be done with PowerShell alone, and if it might be more efficient or more reliable). This tool is primarily meant to extract data, but can be used to calculate MD5 with the syntax : dsfo [source path] [offset] [size] $ (“null size is interpreted as max possible output”). I also used dsfi from the same tool kit, which is meant to overwrite a part of a file with data from another file, with the syntax : dsfi [destination path] [offset] [size] [source path] (here I used it to wipe the contents of fully identified files except the first cluster and the last cluster + 4KB ; I couldn't find a way to directly write null bytes so I created an empty 2GB “Dummy” file with fsutil file createnew and used that as source ; again, I'd be interested to know how the same can be achieved with PowerShell alone).

So for instance I got this result from the WinHex “simultaneous search” :

861627456       *¢M$4M9ˆ  ÿ_ Ì{)    R:\HGST 4To\Root\...\...\...\...\...\...\...\VIDEO_TS\VTS_01_3.VOB  1073739776  1       22  22
40000       *¢M$4M9ˆ  ÿ_ Ì{)    R:\TestDisk 7.1 WIP\MPG\f6821785796.mpg 36079616    1       1   1

A string extracted (with another PowerShell script) at offset 40000 from file fragment f6821785796.mpg (size 36079616) was found at offset 861627456 within file VTS_01_3.VOB (size 1073739776). (The other values on the right side are irrelevant ; they indicate the “link count”, “hit count”, “term count”.) Then, I edited this result with TED Notepad to create the following script :

$offset = 861627456 - 40000
echo "dsfo R:\HGST 4To\Root\...\...\...\...\...\...\...\VIDEO_TS\VTS_01_3.VOB $offset 36079616 $" >> "G:\HGST 4To MPG.txt"
$dsfoA = dsfo "R:\HGST 4To\Root\...\...\...\...\...\...\...\VIDEO_TS\VTS_01_3.VOB" $offset 36079616 $
$MD5A = $dsfoA[-1] -split "= " | select -last 1
echo $MD5A >> "G:\HGST 4To MPG.txt"
echo "dsfo R:\TestDisk 7.1 WIP\MPG\f6821785796.mpg 0 0 $" >> "G:\HGST 4To MPG.txt"
$dsfoB = dsfo "R:\TestDisk 7.1 WIP\MPG\f6821785796.mpg" 0 0 $
$MD5B = $dsfoB[-1] -split "= " | select -last 1
echo $MD5B >> "G:\HGST 4To MPG.txt"
$lengthdsfi = 36079616 - (36079616 % 4096) - 8192
If (($MD5A -eq $MD5B) -and ($lengthdsfi -gt 16384)) {
    echo "dsfi R:\TestDisk 7.1 WIP\MPG\f6821785796.mpg 4096 $lengthdsfi G:\Dummy" >> "G:\HGST 4To MPG.txt"
    dsfi "R:\TestDisk 7.1 WIP\MPG\f6821785796.mpg" 4096 $lengthdsfi G:\Dummy >> "G:\HGST 4To MPG.txt"
    compact /C "R:\TestDisk 7.1 WIP\MPG\f6821785796.mpg" >> "G:\HGST 4To MPG.txt"
} ElseIf (($MD5A -eq $MD5B) -and ($lengthdsfi -lt 16384)) {
    echo "length < 16384" >> "G:\HGST 4To MPG.txt"
} ElseIf ($MD5A -ne $MD5B) {
    echo "MD5 #" >> "G:\HGST 4To MPG.txt"
}
echo ------ >> "G:\HGST 4To MPG.txt"

For 1431 comparisons, the MD5 matched, and the fragment could be wiped / compressed / discarded, but for 1706 others, like the above example, I got this :

dsfo R:\HGST 4To\Root\...\...\...\...\...\...\...\VIDEO_TS\VTS_01_3.VOB 861587456 36079616 $
e365b41f311ff2d111d2324510668331
dsfo R:\TestDisk 7.1 WIP\MPG\f6821785796.mpg 0 0 $
ebfa8a48ea3670b3618089699d66a986
MD5 #

So now the idea is to take all those comparisons which resulted in a MD5 mismatch, and perform a byte-by-byte comparison, in order to obtain the offsets at which files are no longer matching. Actually, it would be preferred to get the offset of the beginning of the corresponding cluster. If I compare those two files above in WinHex, I can see that they are matching up until offsets 897581061 / 35993605 (so 99.7% of the fragment f6821785796.mpg is included within the larger file VTS_01_3.VOB), but I can also see that offsets 897581056 / 35993600, corresponding to an exact multiple of 4096, correspond to the beginning of a new MPG segment (typical 00 00 01 BA signature), so this should be the result of the comparison. (Otherwise it can be calculated with 897581061 - (897581061 % 4096).)


Another possible approach : Another method to find total or partial matches between file fragments and larger files would be to 1) get the MD5 checksum of the first cluster of each file fragment in group B, 2) then calculate the MD5 checksum for each cluster of each file in group A, until a matching MD5 is found, 3) then get the MD5 from the whole file fragment in group B, and the partial MD5 from the file in group A, starting from the beginning of the known identical cluster, with a length equal to the size of the file in group B => if MD5 checksums match then file B is entirely included within file A, 4) if not, then either perform a byte-by-byte comparison, or calculate checksums from each following cluster, until a mismatch is found, and report the offsets of the matching segments.
This would circumvent a major caveat of the former approach, which is that a short string of data extracted from a binary file at a fixed offset is not necessarily specific enough (it can be a segment full of “00” or “FF” bytes, or a more complex but very redundant string that will yield hundreds of irrelevant hits), requiring to start all over again with different offset values until all files could be processed.
WinHex itself has a “block-wise hashing and matching” feature, which I tried, but it relies on a database of sector-level hashes which has to be build first so it's very cumbersome (each 512 bytes sector requires 32 bytes of storage for the corresponding MD5 hash, I had to stop because it was taking way too much space), and then the result is barely useful as it is (it reports a match between a hash from the database and a physical offset, not a logical offset relative to the beginning of a specific file, as with the “simultaneous search” features which can be performed in “Logical” mode).

0

Here's a decent starting point from this great answer for a similar question. This function will determine if fileA is contained within fileB, and return the offset of fileA within fileB.

I've added the functionality for it to return the Offset of when it stops matching. You may have to play with the MinimumMatch setting if the beginning of your files is fairly similar:

Function Find-BytesUntilMismatch([byte[]]$Bytes, [byte[]]$Search, [int]$Start, [Switch]$All, [int]$MinimumMatch=200) {

    # Starting from offset $start, iterate through each byte
    For ($Index = $Start; $Index -le $Bytes.Length; $Index++) {

        # Check if byte matches, iterate through each following byte until 
        # bytes don't match or all bytes of $search are found:
        For ($i = 0; $i -lt $Search.Length -and $Bytes[$Index + $i] -eq $Search[$i]; $i++) {}

        # Search has exited, so check for complete file or return offset
        If ($i -lt $Search.Length -and $i -gt $MinimumMatch) { 
            Write-Output "file stopped matching at offset:$($index + $i); Total bytes matched:$($i)" 
            break 
        }
        If ($i -ge $Search.Length) { 
            Write-Output "full match completed at offset: $($Index + $i); Total bytes matched:$($i)" 

            # Check for additional matches if $All is set
            If (!$All) { Return } 
        } 
    }
    Write-Output "Search Complete"
}

If you know the start of FileA is contained within FileB at offset 10000, then run the following:

# Import byte strings from files:
$FileA = [System.IO.File]::ReadAllBytes("C:\path\to\FileA.dat")
$FileB = [System.IO.File]::ReadAllBytes("C:\path\to\FileB.bin")

# Run function:
Find-BytesUntilMismatch -Search $FileA -Bytes $FileB -Start 91855 -MinimumMatch 100

Outputs:

file stopped matching at offset:1629233; Total bytes matched: 1537377
Search Complete

Note:

  • the Start offset is 0-based, so you may need to feed this command your offset bytes -1.
  • the arrays are 32-bit, so the maximum file size this can handle is probably 2 GB
7
  • Thanks for this, but that would seem like an alternate way to do what I already did, find file fragments which are entirely contained within another file. And doing it like this is not efficient there are hundreds of GB to parse for possible hits. What I did was : first get a list of short strings extracted at a given offset (problem is, it's not always specific enough), then search all strings at once with WinHex ("Simultaneous search"), which gave offsets of search hits in fragments as well as identified files. (TBC)
    – GabrielB
    Apr 1 at 0:00
  • Then I wrote a PS script to calculate MD5 checksums (relying on a 3rd party tool called dsfo as it worked well and made the script more streamlined) : if the MD5 of the fragment A matched the MD5 of the corresponding segment within file B, then A could be discarded. What's left is to deal with fragments that have only a partial match : I already know that the beginning of A is found within B at offset 104857600, but at which offset do they start to diverge ?
    – GabrielB
    Apr 1 at 0:14
  • Then I'm not so sure what you mean by adding examples of small byte strings : those are binary files (MPG / MTS videos) so it can be any seemingly random sequence of bytes, and it's not actually relevant what they look like. I'll try to add something about the desired output, but I see that I already got a "-1" vote, it's not very encouraging... Apparently here you have to already know everything there is to know to ask only very clever questions which will elicit only very clever replies (which you don't actually need since you already know everything there is to know in the first place !).
    – GabrielB
    Apr 1 at 0:20
  • @GabrielB, I think I understand, but to clarify: You expect fileA to be fragmented within fileB also, or do you want to find complete matches where fileB continues past fileA's contents? For complete matches, you only need the length of fileA, and feed the offset you have to Find-Bytes above to check for the full binary. For partial matches, you can edit the function to dump ($index + $i) once the For loop is done (if $i is less than fileA's length).
    – Cpt.Whale
    Apr 1 at 15:53
  • Not sure what you mean here. FileA ("raw" recovery) contains a block of fileB (valid file), beyond that it can contain either a block of another valid file, or a fragment of a deleted file (which won't match with anything else). See the "cmp" / ibm.com link ? That is exactly what I need. I don't know how to explain it better than I already did, it is already way too convoluted as it is, yet what I want to do is quite simple. I don't quite understand how the above function works (don't even know where it should be put to actually work), so I wouldn't know how to modify it.
    – GabrielB
    Apr 2 at 5:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.