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 <epr at jnode.org> 31 * @author Matthias Treydte <waldheinz at gmail.com> 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