Page 1 of 2
Understanding the FAT32 allocation table
Posted: Fri Mar 06, 2009 5:45 pm
by mangaluve
Im playing with the idea of implementering FAT32. I dont really understand the code on the wiki, given a cluster number, how to obtain the next in the list. The code on the wiki is:
Code: Select all
unsigned char FAT_table[cluster_size];
unsigned int fat_offset = active_cluster * 4;
unsigned int fat_sector = first_fat_sector + (fat_offset / cluster_size);
unsigned int ent_offset = fat_offset % cluster_size;
//at this point you need to read from sector "fat_sector" on the disk into "FAT_table".
//remember to ignore the high 4 bits.
unsigned int table_value = *(unsigned int*)&FAT_table[ent_offset] & 0x0FFFFFFF;
What is cluster_size? Perhaps I've missunderstood something, but here's what I thought:
Except for the boot sector and the fat-table, the disk is partitioned into clusters (one clusters represents part of a file). The fat-table contains a 4 byte entry for every cluster (each fat-table-entry corresponds to a cluster in the data area). I don't really see how the code above works.
Re: Understanding the FAT32 allocation table
Posted: Sat Mar 07, 2009 1:19 am
by Firestryke31
The FAT is a large table of clusters. When you get a cluster, it's actually an index into the table. At that index is the next cluster index. If the next cluster is a certain value, then the current cluster is the last one. These cluster indexes also happen to coincide with locations on the disk. A cluster can have one or more sectors (a "cluster" of sectors).
The first two clusters in the FAT are ignored. The first one is used for the disk type and the second (IIRC) is for the EoF marker for that disk. I personally just compare the cluster to 0x0FFFFFF0 and if it's >= to it then that's the last cluster.
I don't exactly know what they mean by 'cluster_size' but in my code (which is very similar, but in ASM) I just use sector_size which should be easy to figure out.
Re: Understanding the FAT32 allocation table
Posted: Sat Mar 07, 2009 4:17 am
by mangaluve
Thanks!
Yeah I also thought that cluster_size should be replaced by sector_size, then the code makes much more sense. Is a cluster an entry in the fat-table, or a chunk in the data area? (terminology question). Is this correct?:
The FAT-table is a table of 4-bytes entries. Each entry points to a new entry (or it could be marked as free / EOF and so on). After the FAT table comes the data area, which is divided into clusters? Each entry in the fat-table corresponds to one of these data-chunks?
And why does this limit the file size to 4 GB? The FAT-table entries are 28 bits, so I can have 2^28 of them. Each of them corresponds to a chunk of, say, 512 bytes in the data area. That would give me, if the entire disk is used for one large file, to 2^(28+37) bytes and not 4 GB?
Re: Understanding the FAT32 allocation table
Posted: Sat Mar 07, 2009 5:32 am
by ru2aqare
mangaluve wrote:Thanks!
Yeah I also thought that cluster_size should be replaced by sector_size, then the code makes much more sense. Is a cluster an entry in the fat-table, or a chunk in the data area? (terminology question). Is this correct?:
The FAT-table is a table of 4-bytes entries. Each entry points to a new entry (or it could be marked as free / EOF and so on). After the FAT table comes the data area, which is divided into clusters? Each entry in the fat-table corresponds to one of these data-chunks?
A cluster is a run of continuous sectors in the data area. Each entry in the FAT table corresponds to one cluster in the data area (hence, entries in the FAT table are sometimes also called clusters). After the FAT comes the root directory, and after the root directory comes the data area. The first sector of the data area corresponds to sector zero of cluster two.
mangaluve wrote:
And why does this limit the file size to 4 GB? The FAT-table entries are 28 bits, so I can have 2^28 of them. Each of them corresponds to a chunk of, say, 512 bytes in the data area. That would give me, if the entire disk is used for one large file, to 2^(28+37) bytes and not 4 GB?
The four gigabyte limitation comes from the file size field of the directory entry, which is thirty-two bits, and thus cannot store a value larger than 2^32-1. This field stores the length of the file measures in bytes, not in clusters. Think about it: if the file length was measured in clusters, how would you store how many bytes are there in a partially-filled last cluster?
Re: Understanding the FAT32 allocation table
Posted: Sat Mar 07, 2009 5:44 am
by mangaluve
So the 4 GB limit is just because only 4 bytes in a directory is used to specify the file size?
What about the first two clusters being ignored? Are we talking about the first two entries in the FAT or the two first clusters in the data area?
Are there any good tools for creating / manipulating fat32-images? So I could create a fat-32 partition as a file and put some files on it, to test my code.
Re: Understanding the FAT32 allocation table
Posted: Sat Mar 07, 2009 5:51 am
by ru2aqare
mangaluve wrote:So the 4 GB limit is just because only 4 bytes in a directory is used to specify the file size?
Correct.
mangaluve wrote:
What about the first two clusters being ignored? Are we talking about the first two entries in the FAT or the two first clusters in the data area?
The first two entries in the FAT table are/were used for the Media Descriptor byte. These entries have no clusters associated with them in the data area. Hence, the first sector of the data area is the first sector of cluster two.
mangaluve wrote:
Are there any good tools for creating / manipulating fat32-images? So I could create a fat-32 partition as a file and put some files on it, to test my code.
Don't know about FAT-32, but for FAT-12 I use the Virtual Floppy Disk extension for Total Commander. This is the only VFD clone I found that can be installed on Windows XP x64. If you use Windows x86, there are lots of Virtual Disk type utilities. If you use *nix, I have no idea.
Re: Understanding the FAT32 allocation table
Posted: Sat Mar 07, 2009 5:55 am
by mangaluve
Thanks! So the layout is something like:
Boot Sector | 2 unused bytes | FAT | data area
where the first entry in FAT corresponds to the first cluster in the data area?
Re: Understanding the FAT32 allocation table
Posted: Sat Mar 07, 2009 6:07 am
by ru2aqare
mangaluve wrote:Thanks! So the layout is something like:
Boot Sector | 2 unused bytes | FAT | data area
where the first entry in FAT corresponds to the first cluster in the data area?
More like
Boot Sector | Reserved sectors (may be zero of them) | FAT which includes the two unused entries (not bytes) at its start | Second FAT which is the copy of the first | Root directory | Data area
Re: Understanding the FAT32 allocation table
Posted: Sat Mar 07, 2009 6:25 am
by mangaluve
Thanks (I mean 8 bytes).
When you say the root directory, is this for fat32 aswell? So the first FAT entry (and the first cluster) do always belong to the root?
Re: Understanding the FAT32 allocation table
Posted: Sat Mar 07, 2009 6:32 am
by ru2aqare
mangaluve wrote:Thanks (I mean 8 bytes).
When you say the root directory, is this for fat32 aswell? So the first FAT entry (and the first cluster) do always belong to the root?
All FAT-xx filesystems use this layout. I don't know where you got that the first FAT entry (the first cluster) would "belong" to the root directory... The first two clusters simply don't exist. They have their entries in the FAT, but those entries are reserved/used for other purposes, and the data area starts with the third cluster.
Re: Understanding the FAT32 allocation table
Posted: Sat Mar 07, 2009 6:42 am
by mangaluve
Well I've read (for instance on Wiki) that the root-directory part is only used in fat12/16, and in fat32 it could be placed anywhere... (if that's true, how do I know where?)
Re: Understanding the FAT32 allocation table
Posted: Sat Mar 07, 2009 8:23 am
by ru2aqare
mangaluve wrote:Well I've read (for instance on Wiki) that the root-directory part is only used in fat12/16, and in fat32 it could be placed anywhere... (if that's true, how do I know where?)
Well I can't say anything to that... My FAT driver only works with FAT12/FAT16 at the moment.
Re: Understanding the FAT32 allocation table
Posted: Sat Mar 07, 2009 8:35 am
by neon
mangaluve wrote:Well I've read (for instance on Wiki) that the root-directory part is only used in fat12/16, and in fat32 it could be placed anywhere?
That is correct. Unlike Fat12/Fat16, the Fat32 root directory is not located at a fixed address.
Re: Understanding the FAT32 allocation table
Posted: Sat Mar 07, 2009 11:05 am
by Firestryke31
In the FAT32 info block there's a field called something along the lines of "RootCluster" that's the first cluster index of the root directory. This makes it so that the root directory isn't a fixed size (far less wasted space) and can be treated like a normal file.
FAT12/FAT16 do have a fixed root, which is slightly annoying because then you have to have special code for it.
Re: Understanding the FAT32 allocation table
Posted: Sat Mar 07, 2009 6:56 pm
by mangaluve
Thanks a lot for the replies, I'll get into it tomorrow
Still no knowledge of any program that can create/manipulate a fat32 disk image?