3

This morning I lost a bunch of files, but because the volume they were one was both internally and externally defragmented, all of the information necessary for a 100% recovery is available; I just need to fill in the FAT where required.

I wrote a program to do this and tested it on a copy of the FAT that I dumped to a file and it works perfectly except that for a few of the files (17 out of 526), the FAT chain is one single cluster too long, and thus cross-linked with the next file.

Fortunately I know exactly what the problem is. I used ceil in my EOF calculation because even a single byte over will require a whole extra cluster:

//Cluster    is the starting cluster of the file
//Size       is the size (in bytes) of the file
//BPC        is the number of bytes per cluster
//NumClust   is the number of clusters in the file
//EOF        is the last cluster of the file’s FAT chain

DWORD NumClust = ceil( (float)(Size / BPC) )
DWORD EOF      = Cluster + NumClust;

This algorithm works fine for everything except files whose size happens to be exactly a multiple of the cluster size, in which case they end up being one cluster too much.

I thought about it for a while but am at a loss as to a way to do this. It seems like it should be simple but somehow it is surprisingly tricky.

What formula would work for files of any size?

Synetech
  • 9,643
  • 9
  • 64
  • 96
  • Why do you cast it to float in the first place??? – Hot Licks Oct 28 '12 at 16:59
  • @HotLicks, because without it, I get the error `ambiguous call to ceil…`. – Synetech Oct 28 '12 at 17:02
  • Why do you feel the need to use `ceil`? In theory, `ceil` of an int should always yield back the same int. – Hot Licks Oct 28 '12 at 17:13
  • @HotLicks, even a single byte over means a whole extra cluster, so it always has to be rounded up; hence `ceil`. I figured it was logically more clear than to experiment and rely on integer division and implied rounding. – Synetech Oct 28 '12 at 17:18
  • Integer division is far more reliable than depending on the random conversions of integer to float. And if you really wanted to use ceil you needed to do float division, or it was basically a no-op. – Hot Licks Oct 28 '12 at 17:46
  • Well, when I got back, I tried the answers below and ended up using Xymostech’s: `EOF = Cluster + ((Size - 1) / BPC)`. (I left off the `+1` because clusters use a 0-based index.) I copied the test FAT to the disk and sure enough, `chkdsk` doesn’t complain anymore and the files were fine (well almost all; one of them is cross-linked with `\Recycled\INFO` because stupid Windows insists on constantly creating and modifying the recycle bin on every volume even when no changes are made to it, and does not provide a way to prevent it—fortunately the file seems undamaged). Thanks a lot everyone! ☺ – Synetech Oct 28 '12 at 19:35
  • (Oops, no, it that one file *is* damaged. There is clearly a 1-sector/512-byte chunk in the middle where `\Recycled\INFO` was copied. ☹ Stupid Windows [forced, optionless Recycle Bin](http://superuser.com/questions/76707).) – Synetech Oct 28 '12 at 20:45

3 Answers3

7

If you want the number of clusters it would be (size + BPC - 1) / BPC, with all integral data types.

Hot Licks
  • 47,103
  • 17
  • 93
  • 151
1

Perhaps ceil( (float)((Size - 1) / BPC) )?

If everything is an integral type, even better would be ((Size - 1) / BPC) + 1.

Xymostech
  • 9,710
  • 3
  • 34
  • 44
  • Hmm, that’s strange. I figured that subtracting one from the size would just end up making a different edge-case error, but I tried it and it worked. ಠ_ಠ I can only assume it’s because I happen to not have any files of a size that fit that particular edge-case. Either way, it worked. Thanks a lot. – Synetech Oct 28 '12 at 19:29
0

ceil( (float)(Size / BPC) ) does integer division, then casts that to float.

You need ceil( (float)Size / BPC ) to do that correctly. But using floats here does seem like a bad idea in the first place... See other answers for integer solution.

hyde
  • 60,639
  • 21
  • 115
  • 176