source/file_allocation_table.c

   1 /*
   2  file_allocation_table.c
   3  Reading, writing and manipulation of the FAT structure on
   4  a FAT partition
   5
   6  Copyright (c) 2006 Michael "Chishm" Chisholm
   7
   8  Redistribution and use in source and binary forms, with or without modification,
   9  are permitted provided that the following conditions are met:
  10
  11   1. Redistributions of source code must retain the above copyright notice,
  12      this list of conditions and the following disclaimer.
  13   2. Redistributions in binary form must reproduce the above copyright notice,
  14      this list of conditions and the following disclaimer in the documentation and/or
  15      other materials provided with the distribution.
  16   3. The name of the author may not be used to endorse or promote products derived
  17      from this software without specific prior written permission.
  18
  19  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
  20  WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
  21  AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE
  22  LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  23  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  24  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  27  EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28 */
  29
  30
  31 #include "file_allocation_table.h"
  32 #include "partition.h"
  33 #include <string.h>
  34
  35 /*
  36 Gets the cluster linked from input cluster
  37 */
  38 uint32_t _FAT_fat_nextCluster(PARTITION* partition, uint32_t cluster)
  39 {
  40         uint32_t nextCluster = CLUSTER_FREE;
  41         sec_t sector;
  42         int offset;
  43
  44         if (cluster == CLUSTER_FREE) {
  45                 return CLUSTER_FREE;
  46         }
  47
  48         switch (partition->filesysType)
  49         {
  50                 case FS_UNKNOWN:
  51                         return CLUSTER_ERROR;
  52                         break;
  53
  54                 case FS_FAT12:
  55                 {
  56                         u32 nextCluster_h;
  57                         sector = partition->fat.fatStart + (((cluster * 3) / 2) / BYTES_PER_READ);
  58                         offset = ((cluster * 3) / 2) % BYTES_PER_READ;
  59
  60
  61                         _FAT_cache_readLittleEndianValue (partition->cache, &nextCluster, sector, offset, sizeof(u8));
  62
  63                         offset++;
  64
  65                         if (offset >= BYTES_PER_READ) {
  66                                 offset = 0;
  67                                 sector++;
  68                         }
  69                         nextCluster_h = 0;
  70
  71                         _FAT_cache_readLittleEndianValue (partition->cache, &nextCluster_h, sector, offset, sizeof(u8));
  72                         nextCluster |= (nextCluster_h << 8);
  73
  74                         if (cluster & 0x01) {
  75                                 nextCluster = nextCluster >> 4;
  76                         } else  {
  77                                 nextCluster &= 0x0FFF;
  78                         }
  79
  80                         if (nextCluster >= 0x0FF7)
  81                         {
  82                                 nextCluster = CLUSTER_EOF;
  83                         }
  84
  85                         break;
  86                 }
  87                 case FS_FAT16:
  88                         sector = partition->fat.fatStart + ((cluster << 1) / BYTES_PER_READ);
  89                         offset = (cluster % (BYTES_PER_READ >> 1)) << 1;
  90
  91                         _FAT_cache_readLittleEndianValue (partition->cache, &nextCluster, sector, offset, sizeof(u16));
  92
  93                         if (nextCluster >= 0xFFF7) {
  94                                 nextCluster = CLUSTER_EOF;
  95                         }
  96                         break;
  97
  98                 case FS_FAT32:
  99                         sector = partition->fat.fatStart + ((cluster << 2) / BYTES_PER_READ);
 100                         offset = (cluster % (BYTES_PER_READ >> 2)) << 2;
 101
 102                         _FAT_cache_readLittleEndianValue (partition->cache, &nextCluster, sector, offset, sizeof(u32));
 103
 104                         if (nextCluster >= 0x0FFFFFF7) {
 105                                 nextCluster = CLUSTER_EOF;
 106                         }
 107                         break;
 108
 109                 default:
 110                         return CLUSTER_ERROR;
 111                         break;
 112         }
 113
 114         return nextCluster;
 115 }
 116
 117 /*
 118 writes value into the correct offset within a partition's FAT, based
 119 on the cluster number.
 120 */
 121 static bool _FAT_fat_writeFatEntry (PARTITION* partition, uint32_t cluster, uint32_t value) {
 122         sec_t sector;
 123         int offset;
 124         uint32_t oldValue;
 125
 126         if ((cluster < CLUSTER_FIRST) || (cluster > partition->fat.lastCluster /* This will catch CLUSTER_ERROR */))
 127         {
 128                 return false;
 129         }
 130
 131         switch (partition->filesysType)
 132         {
 133                 case FS_UNKNOWN:
 134                         return false;
 135                         break;
 136
 137                 case FS_FAT12:
 138                         sector = partition->fat.fatStart + (((cluster * 3) / 2) / BYTES_PER_READ);
 139                         offset = ((cluster * 3) / 2) % BYTES_PER_READ;
 140
 141                         if (cluster & 0x01) {
 142
 143                                 _FAT_cache_readLittleEndianValue (partition->cache, &oldValue, sector, offset, sizeof(u8));
 144
 145                                 value = (value << 4) | (oldValue & 0x0F);
 146
 147                                 _FAT_cache_writeLittleEndianValue (partition->cache, value & 0xFF, sector, offset, sizeof(u8));
 148
 149                                 offset++;
 150                                 if (offset >= BYTES_PER_READ) {
 151                                         offset = 0;
 152                                         sector++;
 153                                 }
 154
 155                                 _FAT_cache_writeLittleEndianValue (partition->cache, (value >> 8) & 0xFF, sector, offset, sizeof(u8));
 156
 157                         } else {
 158
 159                                 _FAT_cache_writeLittleEndianValue (partition->cache, value, sector, offset, sizeof(u8));
 160
 161                                 offset++;
 162                                 if (offset >= BYTES_PER_READ) {
 163                                         offset = 0;
 164                                         sector++;
 165                                 }
 166
 167                                 _FAT_cache_readLittleEndianValue (partition->cache, &oldValue, sector, offset, sizeof(u8));
 168
 169                                 value = ((value >> 8) & 0x0F) | (oldValue & 0xF0);
 170
 171                                 _FAT_cache_writeLittleEndianValue (partition->cache, value, sector, offset, sizeof(u8));
 172                         }
 173
 174                         break;
 175
 176                 case FS_FAT16:
 177                         sector = partition->fat.fatStart + ((cluster << 1) / BYTES_PER_READ);
 178                         offset = (cluster % (BYTES_PER_READ >> 1)) << 1;
 179
 180                         _FAT_cache_writeLittleEndianValue (partition->cache, value, sector, offset, sizeof(u16));
 181
 182                         break;
 183
 184                 case FS_FAT32:
 185                         sector = partition->fat.fatStart + ((cluster << 2) / BYTES_PER_READ);
 186                         offset = (cluster % (BYTES_PER_READ >> 2)) << 2;
 187
 188                         _FAT_cache_writeLittleEndianValue (partition->cache, value, sector, offset, sizeof(u32));
 189
 190                         break;
 191
 192                 default:
 193                         return false;
 194                         break;
 195         }
 196
 197         return true;
 198 }
 199
 200 /*-----------------------------------------------------------------
 201 gets the first available free cluster, sets it
 202 to end of file, links the input cluster to it then returns the
 203 cluster number
 204 If an error occurs, return CLUSTER_ERROR
 205 -----------------------------------------------------------------*/
 206 uint32_t _FAT_fat_linkFreeCluster(PARTITION* partition, uint32_t cluster) {
 207         uint32_t firstFree;
 208         uint32_t curLink;
 209         uint32_t lastCluster;
 210         bool loopedAroundFAT = false;
 211
 212         lastCluster =  partition->fat.lastCluster;
 213
 214         if (cluster > lastCluster) {
 215                 return CLUSTER_ERROR;
 216         }
 217
 218         // Check if the cluster already has a link, and return it if so
 219         curLink = _FAT_fat_nextCluster(partition, cluster);
 220         if ((curLink >= CLUSTER_FIRST) && (curLink <= lastCluster)) {
 221                 return curLink; // Return the current link - don't allocate a new one
 222         }
 223
 224         // Get a free cluster
 225         firstFree = partition->fat.firstFree;
 226         // Start at first valid cluster
 227         if (firstFree < CLUSTER_FIRST) {
 228                 firstFree = CLUSTER_FIRST;
 229         }
 230
 231         // Search until a free cluster is found
 232         while (_FAT_fat_nextCluster(partition, firstFree) != CLUSTER_FREE) {
 233                 firstFree++;
 234                 if (firstFree > lastCluster) {
 235                         if (loopedAroundFAT) {
 236                                 // If couldn't get a free cluster then return an error
 237                                 partition->fat.firstFree = firstFree;
 238                                 return CLUSTER_ERROR;
 239                         } else {
 240                                 // Try looping back to the beginning of the FAT
 241                                 // This was suggested by loopy
 242                                 firstFree = CLUSTER_FIRST;
 243                                 loopedAroundFAT = true;
 244                         }
 245                 }
 246         }
 247         partition->fat.firstFree = firstFree;
 248
 249         if ((cluster >= CLUSTER_FIRST) && (cluster < lastCluster))
 250         {
 251                 // Update the linked from FAT entry
 252                 _FAT_fat_writeFatEntry (partition, cluster, firstFree);
 253         }
 254         // Create the linked to FAT entry
 255         _FAT_fat_writeFatEntry (partition, firstFree, CLUSTER_EOF);
 256
 257         return firstFree;
 258 }
 259
 260 /*-----------------------------------------------------------------
 261 gets the first available free cluster, sets it
 262 to end of file, links the input cluster to it, clears the new
 263 cluster to 0 valued bytes, then returns the cluster number
 264 If an error occurs, return CLUSTER_ERROR
 265 -----------------------------------------------------------------*/
 266 uint32_t _FAT_fat_linkFreeClusterCleared (PARTITION* partition, uint32_t cluster) {
 267         uint32_t newCluster;
 268         uint32_t i;
 269         uint8_t emptySector[BYTES_PER_READ];
 270
 271         // Link the cluster
 272         newCluster = _FAT_fat_linkFreeCluster(partition, cluster);
 273
 274         if (newCluster == CLUSTER_FREE || newCluster == CLUSTER_ERROR) {
 275                 return CLUSTER_ERROR;
 276         }
 277
 278         // Clear all the sectors within the cluster
 279         memset (emptySector, 0, BYTES_PER_READ);
 280         for (i = 0; i < partition->sectorsPerCluster; i++) {
 281                 _FAT_disc_writeSectors (partition->disc,
 282                         _FAT_fat_clusterToSector (partition, newCluster) + i,
 283                         1, emptySector);
 284         }
 285
 286         return newCluster;
 287 }
 288
 289
 290 /*-----------------------------------------------------------------
 291 _FAT_fat_clearLinks
 292 frees any cluster used by a file
 293 -----------------------------------------------------------------*/
 294 bool _FAT_fat_clearLinks (PARTITION* partition, uint32_t cluster) {
 295         uint32_t nextCluster;
 296
 297         if ((cluster < CLUSTER_FIRST) || (cluster > partition->fat.lastCluster /* This will catch CLUSTER_ERROR */))
 298                 return false;
 299
 300         // If this clears up more space in the FAT before the current free pointer, move it backwards
 301         if (cluster < partition->fat.firstFree) {
 302                 partition->fat.firstFree = cluster;
 303         }
 304
 305         while ((cluster != CLUSTER_EOF) && (cluster != CLUSTER_FREE) && (cluster != CLUSTER_ERROR)) {
 306                 // Store next cluster before erasing the link
 307                 nextCluster = _FAT_fat_nextCluster (partition, cluster);
 308
 309                 // Erase the link
 310                 _FAT_fat_writeFatEntry (partition, cluster, CLUSTER_FREE);
 311
 312                 // Move onto next cluster
 313                 cluster = nextCluster;
 314         }
 315
 316         return true;
 317 }
 318
 319 /*-----------------------------------------------------------------
 320 _FAT_fat_trimChain
 321 Drop all clusters past the chainLength.
 322 If chainLength is 0, all clusters are dropped.
 323 If chainLength is 1, the first cluster is kept and the rest are
 324 dropped, and so on.
 325 Return the last cluster left in the chain.
 326 -----------------------------------------------------------------*/
 327 uint32_t _FAT_fat_trimChain (PARTITION* partition, uint32_t startCluster, unsigned int chainLength) {
 328         uint32_t nextCluster;
 329
 330         if (chainLength == 0) {
 331                 // Drop the entire chain
 332                 _FAT_fat_clearLinks (partition, startCluster);
 333                 return CLUSTER_FREE;
 334         } else {
 335                 // Find the last cluster in the chain, and the one after it
 336                 chainLength--;
 337                 nextCluster = _FAT_fat_nextCluster (partition, startCluster);
 338                 while ((chainLength > 0) && (nextCluster != CLUSTER_FREE) && (nextCluster != CLUSTER_EOF)) {
 339                         chainLength--;
 340                         startCluster = nextCluster;
 341                         nextCluster = _FAT_fat_nextCluster (partition, startCluster);
 342                 }
 343
 344                 // Drop all clusters after the last in the chain
 345                 if (nextCluster != CLUSTER_FREE && nextCluster != CLUSTER_EOF) {
 346                         _FAT_fat_clearLinks (partition, nextCluster);
 347                 }
 348
 349                 // Mark the last cluster in the chain as the end of the file
 350                 _FAT_fat_writeFatEntry (partition, startCluster, CLUSTER_EOF);
 351
 352                 return startCluster;
 353         }
 354 }
 355
 356 /*-----------------------------------------------------------------
 357 _FAT_fat_lastCluster
 358 Trace the cluster links until the last one is found
 359 -----------------------------------------------------------------*/
 360 uint32_t _FAT_fat_lastCluster (PARTITION* partition, uint32_t cluster) {
 361         while ((_FAT_fat_nextCluster(partition, cluster) != CLUSTER_FREE) && (_FAT_fat_nextCluster(partition, cluster) != CLUSTER_EOF)) {
 362                 cluster = _FAT_fat_nextCluster(partition, cluster);
 363         }
 364         return cluster;
 365 }
 366
 367 /*-----------------------------------------------------------------
 368 _FAT_fat_freeClusterCount
 369 Return the number of free clusters available
 370 -----------------------------------------------------------------*/
 371 unsigned int _FAT_fat_freeClusterCount (PARTITION* partition) {
 372         unsigned int count = 0;
 373         uint32_t curCluster;
 374
 375         for (curCluster = CLUSTER_FIRST; curCluster <= partition->fat.lastCluster; curCluster++) {
 376                 if (_FAT_fat_nextCluster(partition, curCluster) == CLUSTER_FREE) {
 377                         count++;
 378                 }
 379         }
 380
 381         return count;
 382 }
 383