1% Copyright 2003,2005,2007 Alain Knaff. 2 3% This documentation is for Mtools which is a collection of tools to 4% allow Unix systems to manipulate MS-DOS files. 5 6% Permission is granted to copy, distribute and/or modify this document 7% under the terms of the GNU Free Documentation License, Version 1.3 or 8% any later version published by the Free Software Foundation; with no 9% Invariant Sections, with no Front-Cover Texts, and with no Back-Cover 10%Texts. A copy of the license is included in the section entitled 11% ``GNU Free Documentation License''. 12 13\documentclass[a4paper,12pt]{article} 14 15\usepackage[T1]{fontenc} 16\usepackage[latin1]{inputenc} 17\usepackage{pslatex} 18\usepackage[pdfpagemode=None,colorlinks]{hyperref} 19 20\author{Alain Knaff} 21\title{How mformat-3.9.10 and above calculates needed FAT size} 22 23\begin{document} 24 25\maketitle 26 27This small document explains the formula used by {\tt mformat.c} to 28figure out fat size and number of clusters. Due to the way that 29filesystem parameters are stored in the boot sector, we can afford to 30have a FAT that is larger than need to be to accommodate the clusters 31present on disk, but under no circumstances can we have one that is 32too small. 33 34In this discussion, we use the following variable names: 35 36\begin{tabular}{|r|p{12cm}|} 37 38\hline 39 40$fatNybls$& 41Number of nubbles (4 bit unit per FAT). This is 3 for FAT12, 4 for 42FAT16, and 8 for FAT16\\ 43 44\hline 45 46$numClus$& 47Number of clusters on the disk\\ 48 49\hline 50 51$clusSiz$& 52Size of a cluster, expressed in sectors\\ 53 54\hline 55 56$secSiz$& 57Size of a sector, in bytes. Size of a sector in nybbles is $secSiz$ * 2\\ 58 59\hline 60 61$nfats$& 62Number of FAT copies, usually two\\ 63 64\hline 65 66$remSects$& 67``Remaining sectors'', after number of boot sectors and root directory 68have been accounted for\\ 69 70\hline 71 72$fatLen$& 73Length of the FAT, in sectors\\ 74 75\hline 76 77 78\end{tabular} 79 80\ \\ 81 82Taking into account both data and fat, each cluster takes up the 83following number of nybbles (units of 4 bytes): 84 85 86$$clusSiz * (2*secSiz) + nfats * fatNybls$$ 87 88This accounts for the data of the cluster ($clusSiz * secSiz$), 89as well as for the space taken up by its descriptor. 90 91The space taken up by all clusters together, plus the space taken by 92descriptors for clusters 0 and 1 ($2*nfats*fatNybls$) should be less 93than what is available. 94 95Additional sectors may be lost due to slack (you have to use a full 96FAT sector, you also have to use a full cluster in the data 97area). Thus, an {\em upper bound} for the number of clusters is as 98follows: 99 100$$ 101numClus \le {2*remSect*secSiz - 2*nfats*fatNybls \over 1022*clusSiz*secSiz + nfats*fatNybls} 103$$ 104 105 106$$ 107numClus \le {(remSect+2*clusSiz)*2*secSiz \over 1082*clusSiz*secSiz + nfats*fatNybls} - 2 109$$ 110 111 112These will take up at most the following space in one copy of the FAT 113(we have to round up, because even a half-full fat sector must be 114taken in its entirety) 115 116$$ 117fatLen \le \left\lceil { (numClus+2)*fatNybls \over secSiz * 2 } \right\rceil 118$$ 119 120 121$$ 122fatLen \le \left\lceil { 123\left( { 2*(remSect+2*clusSiz)*secSiz \over 1242*clusSiz*secSiz + nfats*fatNybls} \right) * fatNybls \over 1252*secSiz 126} \right\rceil 127$$ 128 129 130$$ 131fatLen \le \left\lceil { 132(remSect+2*clusSiz)* fatNybls \over 1332*clusSiz*secSiz + nfats*fatNybls 134} \right\rceil 135$$ 136 137The space left after FAT sector has been deduced is now {\em less than 138or equal} to what would be needed for the data area of the clusters 139(including fractional clusters), which is good, as we may have under 140no circumstances {\em more} clusters in the data area than in the FAT. 141An important point in this calculation is that we based the needed FAT 142size on a {\em fractional} number of clusters, rather than a rounded 143down amount of clusters. Indeed, using a rounded down number could 144have exposed us to a situation where we had an {\em almost enough} 145space for one more cluster (i.e. not enough space for data + FAT, but 146enough for data alone). This situation, combined with a situation 147where the last FAT sector was flush full could have lead to a 148situation where $numClus$ would become too large for the FAT to 149accommodate. I think this is clearer with an example: 150\begin{itemize} 151\item $remSect=4127$, $clusSiz=1$, $nfats=1$ 152\item (Non rounded down) $numClus={(4127+2)*(1024) \over 1032} - 1532 =4094.992$ 154\item Rounded down: 4094 clusters 155\item These fit into 16 FAT sectors, exactly 156\item ... leaving us 4095 clusters, which is one to many (because 157these 4095 clusters would now need 17 FAT clusters) 158\end{itemize} 159 160Keeping the fractional part (0.992) allows us to round {\em up} the 161needed number of FAT sectors to 17, nicely solving this problem. 162 163The downside of counting the fractional part however is that we quite 164often waste a sector in the really common situation where both $nfats$ 165and $clusSiz$ are even, while $remSect$ is odd. An easy way to address 166this is to subtract one from $remSect$ before application of the 167formula, if this case is detected. Such operation carries no risk, as 168the odd final sector cannot be used to make a full cluster. 169 170There is still a case however, where fatLen must be grown manually 171after application of the formula: If numClus exceeds the maximum 172number of clusters allowable for FAT12 or FAT16), we need to shrink 173$numClus$ after application of the formula, and manually make the FAT 174larger in order to take up any excess space. 175 176Also note that as we used upper bounds, we may waste a certain number 177of sectors, which an exact calculation may not have wasted. However, 178normally, we should not lose more than one sector per FAT copy. 179 180N.B. In its document at \url{http://www.microsoft.com/hwdev/download/hardware/fatgen103.pdf}, 181Microsoft proposes a much simpler formula. However, this formula is 182both wrong (i.e. occasionally it produces a smaller FAT than is 183needed for the clusters on disk), less generic (only works for sector 184sizes equal to 512), and less efficient (in case of FAT32, it may 185waste up to 8 sectors!) 186 187The formula is the following (for FAT16): 188$$ 189fatLen \le \left\lceil { remSect \over 256 * clusSiz + nfats} \right\rceil 190$$ 191 192Note that it doesn't account for the dummy clusters 0 and 1. Thus, if 193we have 258 sectors remaining, with a cluster size of 1, and two FAT 194copies, the Microsoft formula mistakenly assumes fatLen = 1. This 195leaves 258 - 2 = 256 sectors for clusters, which yields 256 clusters. 196However, those clusters do not fit into the FAT, as two clusters are 197lost (0 and 1). However, to Micro\$ofts' credit, this is not actually 198the formula they're using (tested with $remsect=160056$ and 199$clusSize=4$), so this seems to be a documentation issue rather than a 200genuine bug. 201 202In case of FAT32, Microsoft just halves the denominator. This is 203wasteful, as only the $256*clusSiz$ part would need to be halved. 204 205If we assume 16777000, and a cluster size of 8, our formula would give 206us: 207$$fatLen = \left\lceil (16777000 + 16) * 8 \over 2 * 8 * 512 + 16 208\right\rceil = 16352$$ 209This would leave $16777000-2*16352=16744296$ sectors for the clusters, 210i.e. 2093037 clusters. The FAT descriptors for those 2093037 clusters 211do indeed fit into our 16352 fat sectors. 212 213Microsoft, on the other hand, would get: $$fatLen = \left\lceil{ 21416777000 \over (256 * 8 + 2)/2} \right\rceil = 16368$$ This would only 215leave $16777000-2*16368=16744264$, i.e. 2093033 clusters, thus wasting 2164 clusters. The FAT would be 28 sectors too big, i.e. more than the 217mere 8 sectors announced by Microsoft! Unfortunately, I currently 218don't have access to any sufficiently recent Windows to check out 219whether this really happens in the code, or whether it is only a 220documentation issue as well. 221 222Oh, and before somebody points it out: the formula in this document 223occassionnally wastes sectors too, although not as much (Example: With 224$remsect=685$, $clusSiz=1$ and $nfats=2$ our formula gives $fatLen=3$, 225which leaves 679 clusters. However, we could use $fatLen=2$, leaving 226681 clusters. 227 228\end{document} 229