1 /*
2  * Copyright (C) 2003-2009 JNode.org
3  *               2009,2010 Matthias Treydte <[email protected]>
4  *
5  * This library is free software; you can redistribute it and/or modify it
6  * under the terms of the GNU Lesser General Public License as published
7  * by the Free Software Foundation; either version 2.1 of the License, or
8  * (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful, but
11  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
13  * License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public License
16  * along with this library; If not, write to the Free Software Foundation, Inc.,
17  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18  */
19 
20 package de.waldheinz.fs.fat;
21 
22 import de.waldheinz.fs.BlockDevice;
23 import java.io.IOException;
24 import java.nio.ByteBuffer;
25 import java.util.Arrays;
26 
27 /**
28  *
29  *
30  * @author Ewout Prangsma &lt;epr at jnode.org&gt;
31  * @author Matthias Treydte &lt;waldheinz at gmail.com&gt;
32  */
33 public final class Fat {
34 
35     /**
36      * The first cluster that really holds user data in a FAT.
37      */
38     public final static int FIRST_CLUSTER = 2;
39 
40     private final long[] entries;
41     private final FatType fatType;
42     private final int sectorCount;
43     private final int sectorSize;
44     private final BlockDevice device;
45     private final BootSector bs;
46     private final long offset;
47     private final int lastClusterIndex;
48 
49     private int lastAllocatedCluster;
50 
51     /**
52      * Reads a {@code Fat} as specified by a {@code BootSector}.
53      *
54      * @param bs the boot sector specifying the {@code Fat} layout
55      * @param fatNr the number of the {@code Fat} to read
56      * @return the {@code Fat} that was read
57      * @throws IOException on read error
58      * @throws IllegalArgumentException if {@code fatNr} is greater than
59      *      {@link BootSector#getNrFats()}
60      */
read(BootSector bs, int fatNr)61     public static Fat read(BootSector bs, int fatNr)
62             throws IOException, IllegalArgumentException {
63 
64         if (fatNr > bs.getNrFats()) {
65             throw new IllegalArgumentException(
66                     "boot sector says there are only " + bs.getNrFats() +
67                     " FATs when reading FAT #" + fatNr);
68         }
69 
70         final long fatOffset = FatUtils.getFatOffset(bs, fatNr);
71         final Fat result = new Fat(bs, fatOffset);
72         result.read();
73         return result;
74     }
75 
76     /**
77      * Creates a new {@code Fat} as specified by a {@code BootSector}.
78      *
79      * @param bs the boot sector specifying the {@code Fat} layout
80      * @param fatNr the number of the {@code Fat} to create
81      * @return the {@code Fat} that was created
82      * @throws IOException on write error
83      * @throws IllegalArgumentException if {@code fatNr} is greater than
84      *      {@link BootSector#getNrFats()}
85      */
create(BootSector bs, int fatNr)86     public static Fat create(BootSector bs, int fatNr)
87             throws IOException, IllegalArgumentException {
88 
89         if (fatNr > bs.getNrFats()) {
90             throw new IllegalArgumentException(
91                     "boot sector says there are only " + bs.getNrFats() +
92                     " FATs when creating FAT #" + fatNr);
93         }
94 
95         final long fatOffset = FatUtils.getFatOffset(bs, fatNr);
96         final Fat result = new Fat(bs, fatOffset);
97 
98         if (bs.getDataClusterCount() > result.entries.length)
99             throw new IOException("FAT too small for device");
100 
101         result.init(bs.getMediumDescriptor());
102         result.write();
103         return result;
104     }
105 
Fat(BootSector bs, long offset)106     private Fat(BootSector bs, long offset) throws IOException {
107         this.bs = bs;
108         this.fatType = bs.getFatType();
109         if (bs.getSectorsPerFat() > Integer.MAX_VALUE)
110             throw new IllegalArgumentException("FAT too large");
111 
112         if (bs.getSectorsPerFat() <= 0) throw new IOException(
113                 "boot sector says there are " + bs.getSectorsPerFat() +
114                 " sectors per FAT");
115 
116         if (bs.getBytesPerSector() <= 0) throw new IOException(
117                 "boot sector says there are " + bs.getBytesPerSector() +
118                 " bytes per sector");
119 
120         this.sectorCount = (int) bs.getSectorsPerFat();
121         this.sectorSize = bs.getBytesPerSector();
122         this.device = bs.getDevice();
123         this.offset = offset;
124         this.lastAllocatedCluster = FIRST_CLUSTER;
125 
126         if (bs.getDataClusterCount() > Integer.MAX_VALUE) throw
127                 new IOException("too many data clusters");
128 
129         if (bs.getDataClusterCount() == 0) throw
130                 new IOException("no data clusters");
131 
132         this.lastClusterIndex = (int) bs.getDataClusterCount() + FIRST_CLUSTER;
133 
134         entries = new long[(int) ((sectorCount * sectorSize) /
135                 fatType.getEntrySize())];
136 
137         if (lastClusterIndex > entries.length) throw new IOException(
138             "file system has " + lastClusterIndex +
139             "clusters but only " + entries.length + " FAT entries");
140     }
141 
getFatType()142     public FatType getFatType() {
143         return fatType;
144     }
145 
146     /**
147      * Returns the {@code BootSector} that specifies this {@code Fat}.
148      *
149      * @return this {@code Fat}'s {@code BootSector}
150      */
getBootSector()151     public BootSector getBootSector() {
152         return this.bs;
153     }
154 
155     /**
156      * Returns the {@code BlockDevice} where this {@code Fat} is stored.
157      *
158      * @return the device holding this FAT
159      */
getDevice()160     public BlockDevice getDevice() {
161         return device;
162     }
163 
init(int mediumDescriptor)164     private void init(int mediumDescriptor) {
165         entries[0] =
166                 (mediumDescriptor & 0xFF) |
167                 (0xFFFFF00L & fatType.getBitMask());
168         entries[1] = fatType.getEofMarker();
169     }
170 
171     /**
172      * Read the contents of this FAT from the given device at the given offset.
173      *
174      * @param offset the byte offset where to read the FAT from the device
175      * @throws IOException on read error
176      */
read()177     private void read() throws IOException {
178         final byte[] data = new byte[sectorCount * sectorSize];
179         device.read(offset, ByteBuffer.wrap(data));
180 
181         for (int i = 0; i < entries.length; i++)
182             entries[i] = fatType.readEntry(data, i);
183     }
184 
write()185     public void write() throws IOException {
186         this.writeCopy(offset);
187     }
188 
189     /**
190      * Write the contents of this FAT to the given device at the given offset.
191      *
192      * @param offset the device offset where to write the FAT copy
193      * @throws IOException on write error
194      */
writeCopy(long offset)195     public void writeCopy(long offset) throws IOException {
196         final byte[] data = new byte[sectorCount * sectorSize];
197 
198         for (int index = 0; index < entries.length; index++) {
199             fatType.writeEntry(data, index, entries[index]);
200         }
201 
202         device.write(offset, ByteBuffer.wrap(data));
203     }
204 
205     /**
206      * Gets the medium descriptor byte
207      *
208      * @return int
209      */
getMediumDescriptor()210     public int getMediumDescriptor() {
211         return (int) (entries[0] & 0xFF);
212     }
213 
214     /**
215      * Gets the entry at a given offset
216      *
217      * @param index
218      * @return long
219      */
getEntry(int index)220     public long getEntry(int index) {
221         return entries[index];
222     }
223 
224     /**
225      * Returns the last free cluster that was accessed in this FAT.
226      *
227      * @return the last seen free cluster
228      */
getLastFreeCluster()229     public int getLastFreeCluster() {
230         return this.lastAllocatedCluster;
231     }
232 
getChain(long startCluster)233     public long[] getChain(long startCluster) {
234         testCluster(startCluster);
235         // Count the chain first
236         int count = 1;
237         long cluster = startCluster;
238         while (!isEofCluster(entries[(int) cluster])) {
239             count++;
240             cluster = entries[(int) cluster];
241         }
242         // Now create the chain
243         long[] chain = new long[count];
244         chain[0] = startCluster;
245         cluster = startCluster;
246         int i = 0;
247         while (!isEofCluster(entries[(int) cluster])) {
248             cluster = entries[(int) cluster];
249             chain[++i] = cluster;
250         }
251         return chain;
252     }
253 
254     /**
255      * Gets the cluster after the given cluster
256      *
257      * @param cluster
258      * @return long The next cluster number or -1 which means eof.
259      */
getNextCluster(long cluster)260     public long getNextCluster(long cluster) {
261         testCluster(cluster);
262         long entry = entries[(int) cluster];
263         if (isEofCluster(entry)) {
264             return -1;
265         } else {
266             return entry;
267         }
268     }
269 
270     /**
271      * Allocate a cluster for a new file
272      *
273      * @return long the number of the newly allocated cluster
274      * @throws IOException if there are no free clusters
275      */
allocNew()276     public long allocNew() throws IOException {
277 
278         int i;
279         int entryIndex = -1;
280 
281         for (i = lastAllocatedCluster; i < lastClusterIndex; i++) {
282             if (isFreeCluster(i)) {
283                 entryIndex = i;
284                 break;
285             }
286         }
287 
288         if (entryIndex < 0) {
289             for (i = FIRST_CLUSTER; i < lastAllocatedCluster; i++) {
290                 if (isFreeCluster(i)) {
291                     entryIndex = i;
292                     break;
293                 }
294             }
295         }
296 
297         if (entryIndex < 0) {
298             throw new IOException(
299                     "FAT Full (" + (lastClusterIndex - FIRST_CLUSTER)
300                     + ", " + i + ")"); //NOI18N
301         }
302 
303         entries[entryIndex] = fatType.getEofMarker();
304         lastAllocatedCluster = entryIndex % lastClusterIndex;
305         if (lastAllocatedCluster < FIRST_CLUSTER)
306             lastAllocatedCluster = FIRST_CLUSTER;
307 
308         return entryIndex;
309     }
310 
311     /**
312      * Returns the number of clusters that are currently not in use by this FAT.
313      * This estimate does only account for clusters that are really available in
314      * the data portion of the file system, not for clusters that might only
315      * theoretically be stored in the {@code Fat}.
316      *
317      * @return the free cluster count
318      * @see FsInfoSector#setFreeClusterCount(long)
319      * @see FsInfoSector#getFreeClusterCount()
320      * @see BootSector#getDataClusterCount()
321      */
getFreeClusterCount()322     public int getFreeClusterCount() {
323         int result = 0;
324 
325         for (int i=FIRST_CLUSTER; i < lastClusterIndex; i++) {
326             if (isFreeCluster(i)) result++;
327         }
328 
329         return result;
330     }
331 
332     /**
333      * Returns the cluster number that was last allocated in this fat.
334      *
335      * @return
336      */
getLastAllocatedCluster()337     public int getLastAllocatedCluster() {
338         return this.lastAllocatedCluster;
339     }
340 
341     /**
342      * Allocate a series of clusters for a new file.
343      *
344      * @param nrClusters when number of clusters to allocate
345      * @return long
346      * @throws IOException if there are no free clusters
347      */
allocNew(int nrClusters)348     public long[] allocNew(int nrClusters) throws IOException {
349         final long rc[] = new long[nrClusters];
350 
351         rc[0] = allocNew();
352         for (int i = 1; i < nrClusters; i++) {
353             rc[i] = allocAppend(rc[i - 1]);
354         }
355 
356         return rc;
357     }
358 
359     /**
360      * Allocate a cluster to append to a new file
361      *
362      * @param cluster a cluster from a chain where the new cluster should be
363      *      appended
364      * @return long the newly allocated and appended cluster number
365      * @throws IOException if there are no free clusters
366      */
allocAppend(long cluster)367     public long allocAppend(long cluster)
368             throws IOException {
369 
370         testCluster(cluster);
371 
372         while (!isEofCluster(entries[(int) cluster])) {
373             cluster = entries[(int) cluster];
374         }
375 
376         long newCluster = allocNew();
377         entries[(int) cluster] = newCluster;
378 
379         return newCluster;
380     }
381 
setEof(long cluster)382     public void setEof(long cluster) {
383         testCluster(cluster);
384         entries[(int) cluster] = fatType.getEofMarker();
385     }
386 
setFree(long cluster)387     public void setFree(long cluster) {
388         testCluster(cluster);
389         entries[(int) cluster] = 0;
390     }
391 
392     @Override
equals(Object obj)393     public boolean equals(Object obj) {
394         if (!(obj instanceof Fat)) return false;
395 
396         final Fat other = (Fat) obj;
397         if (this.fatType != other.fatType) return false;
398         if (this.sectorCount != other.sectorCount) return false;
399         if (this.sectorSize != other.sectorSize) return false;
400         if (this.lastClusterIndex != other.lastClusterIndex) return false;
401         if (!Arrays.equals(this.entries, other.entries)) return false;
402         if (this.getMediumDescriptor() != other.getMediumDescriptor())
403             return false;
404 
405         return true;
406     }
407 
408     @Override
hashCode()409     public int hashCode() {
410         int hash = 7;
411         hash = 23 * hash + Arrays.hashCode(this.entries);
412         hash = 23 * hash + this.fatType.hashCode();
413         hash = 23 * hash + this.sectorCount;
414         hash = 23 * hash + this.sectorSize;
415         hash = 23 * hash + this.lastClusterIndex;
416         return hash;
417     }
418 
419     /**
420      * Is the given entry a free cluster?
421      *
422      * @param entry
423      * @return boolean
424      */
isFreeCluster(long entry)425     protected boolean isFreeCluster(long entry) {
426         if (entry > Integer.MAX_VALUE) throw new IllegalArgumentException();
427         return (entries[(int) entry] == 0);
428     }
429 
430     /**
431      * Is the given entry a reserved cluster?
432      *
433      * @param entry
434      * @return boolean
435      */
isReservedCluster(long entry)436     protected boolean isReservedCluster(long entry) {
437         return fatType.isReservedCluster(entry);
438     }
439 
440     /**
441      * Is the given entry an EOF marker
442      *
443      * @param entry
444      * @return boolean
445      */
isEofCluster(long entry)446     protected boolean isEofCluster(long entry) {
447         return fatType.isEofCluster(entry);
448     }
449 
testCluster(long cluster)450     protected void testCluster(long cluster) throws IllegalArgumentException {
451         if ((cluster < FIRST_CLUSTER) || (cluster >= entries.length)) {
452             throw new IllegalArgumentException(
453                     "invalid cluster value " + cluster);
454         }
455     }
456 
457     @Override
toString()458     public String toString() {
459         final StringBuilder sb = new StringBuilder();
460 
461         sb.append(this.getClass().getSimpleName());
462         sb.append("[type=");
463         sb.append(fatType);
464         sb.append(", mediumDescriptor=0x");
465         sb.append(Integer.toHexString(getMediumDescriptor()));
466         sb.append(", sectorCount=");
467         sb.append(sectorCount);
468         sb.append(", sectorSize=");
469         sb.append(sectorSize);
470         sb.append(", freeClusters=");
471         sb.append(getFreeClusterCount());
472         sb.append("]");
473 
474         return sb.toString();
475     }
476 
477 }
478