1 Notes for Z80 by #191256145782898688

1.1 Introduction

The following are notes of Filesystems,specifications and guides of a z80 project. The notes can be read here or be downloaded as textfiles. The textfiles are listed below.

1.2 Text Files

2 The ext2 filesystem


A partition, disk, file, or block device formatted with a Second Extended Filesystem is divided into small groups of sectors called "blocks". These blocks are then grouped into larger units called block groups.

The size of the blocks are usually determined when formatting the disk and will have an impact on performance, maximum file size, and maximum file system size. Block sizes commonly implemented include 1KiB, 2KiB, 4KiB, and 8KiB although provisions in the superblock allow for block sizes as big as 1024*(231)-1.

Depending on the implementation, some architectures may impose limits on which block sizes are supported. For example, a Linux 2.6 implementation on DEC Alpha uses blocks of 8KiB but the same implementation on a Intel 386 processor will support a maximum block size of 4KiB.


Blocks are clustered into block groups in order to reduce fragmentation and minimise the amount of head seeking when reading a large amount of consecutive data. Information about each block group is kept in a descriptor table stored in the block(s) immediately after the superblock. Two blocks near the start of each group are reserved for the block usage bitmap and the inode usage bitmap which show which blocks and inodes are in use. Since each bitmap is limited to a single block, this means that the maximum size of a block group in blocks is 8 times the size of a block.

The block(s) following the bitmaps in each block group are designated as the inode table for that block group and the remainder are the data blocks. The block allocation algorithm attempts to allocate data blocks in the same block group as the inode which contains them.

A directory is a filesystem object and has an inode just like a file. It is a specially formatted file containing records which associate each name with an inode number. Later revisions of the filesystem also encode the type of the object (file, directory, symlink, device, fifo, coket) to avoid the need to check the inode itself for this information.

The inode allocation code should try to assign inodes which are in the same block group as the directory in which they are first created.

The original Ext2 revision used singly-linked lists to store the filenames in the directory; newer revisions are able to use hashes and binary trees.

Also note that as directory grows additional blocks are assigned to store the additional file records. When filenames are removed, some implementations do not free these additional blocks.


The inode (index node) is a fundamental concept in the ext2 filesystem. Each object in the filesystem is represented by an inode. The inode structure contains pointers to the filesystem blocks which contain the data held in the object and all of the metadata about an object includes the permissions, owner, group, flags, size, number of blocks used, access time, change time, modification time, deletion time, number of links, fragments, version (for NFS) and extended attributes (EAs) and/or Access Control Lists (ACLs).

There are some reserved fields which are currently unused in the inode structure and several which are overloaded. One field is reserved for the directory ACL if the inode is a directory and alternately for the top 32 bits of the file size if the inode is a regular file (allowing file sizes larger than 2GB). The translator field is unused under Linux, but is used by the HURD to reference the inode of a program which will be used to interpret this object. Most of the remaining reserved fields have been used up for both Linux and the HURD for larger owner and group fields. The HURD also has a larger mode field so it uses another of the remaining fields to store the extra bits.

There are pointers to the first 12 blocks which contain the file's data in the inode. There is a pointer to an indirect block (which contains pointers to the next set of blocks), a pointer to a doubly-indirect block (which contains pointers to indirect blocks) and a pointer to a trebly-indirect block (which contains pointers to doubly-indirect blocks).

Some filesystem specific behavior flags are also stored and allow for specific filesystem behavior on a per-file basis. There are flags for secure deletion, undeletable, compression, synchronous updates, immutability, append-only, dumpable, no-atime, indexed directories, and data-journaling.

Many of the filesystem specific behavior flags, like journaling, have been implemented in newer filesystems like ext3 and ext4, while some others are still under development.

All the inodes are stored in inode tables, with one inode table per block group.


The superblock contains all the infomation about the configuration of the filesystem. The information in the superblock contains fields such as the total number of inodes and blocks in the filesystem and how many are free, how many inodes and blocks are in each block group, when the filesystem was mounted (and if it was cleanly unmounted), when it was modified, what version of the filesystem it is and which OS created it.

The primary copy of the superblock is stored at an offset of 1024 bytes from the start of the device, and it is essential to mounting the filesystem. Since it is so important, backup copies of the superblock are stored in block groups throughout the filesystem.

The first version of ext2 (revision 0) stores a copy at the start of every block group, along with backups of the group descriptor block(s). Because this can consume a considerable amount of space for large filesystems, later revisions can optionally reduce the number of backup copies by only putting backups in specific groups (this is the sparse superblock feature). The groups chosen are 0, 1 and powers of 3, 5 and 7.

Revision 1 and higher of the filesystem also stores extra fields, such as volume name, a unique identification number, the inode size, and space for optional filesystem features to store configuration info.

All fields in the superblock (as in all other ext2 structures) are stored on the disk in little endian format, so a filesystem is portable between machines without having to know what machine it was created on.


A symbolic link (also symlink or soft link) is a special type of file that contains a reference to another file or directory in the form of an absolute or relative path and that affects pathname resolution.

Symbolic links operate transparently for most operations: programs which read or write to files named by a symbolic link will behave as if operating directly on the target files. However, programs that need to handle symbolic links specially (e.g., backup utilities) may identify and manipulate them directly.

A symbolic link merely contains a text string that is interpreted and followed by the operating system as a path to another file or directory. It is a file on its own and can exist independantly of its target. The symbolic links do not affect and inode link count. If a symbolic link is deleted, its target remains unaffected. If the target is moved, renamed, or deleted, any symbolic link that used to point to it continues to exist but now points to a nonexisting file. Symbolic links pointing to non-existing files are sometimes called "orphaned" or "dangling".

Symbolic links are also filesystem objects with inodes. For all symlink shorter than 60 bytes long, the data is stored within the inode itself; it uses the fields which would normally be used to store the pointers to data blocks. This is a worthwhile optimisation as it avoids allocating a full block for the symlink, and most symlinks are less than 60 characters long.

Symbolic links can also point to files or directories of other partitions and file systems.


An ext2 filesystem starts with a superblock located at byte offset 1024 from the start of the volume. This is block 1 for a 1KiB block formatted volume, or within block 0 for larger block sizes. Note that the size of the superblock is constant regardless of the block size.

On the next block(s) following the superblock, is the Block Group Descriptor Table; which provides an overview of how the volume is split into block groups and where to find the inode bitmap, the block bitmap, and the inode table for each block group.

In revision 0 of ext2, each block group consists of a copy superblock, a copy of the block group descriptor table, a block bitmap, an inode bitmap, an inode table, and data blocks.

With the introduction of revision 1 and the sparse superblock feature in ext2, only specific block groups contain copies of the superblock and block group descriptor table. All block groups still contain the block bitmap, inode bitmap, inode table, and data blocks. The shadow copies of the superblock can be located in block groups 0, 1 and powers of 3, 5, and 7.

The block bitmap and inode bitmap are limited to 1 block each per block group, so the total blocks per block group is therefore limited. (More information in the Block Size Impact table).

Each data block may also be further divided into 'fragments'. As of Linux 2.6.28, support for fragment was still not implemented in the kernel; it is therefore suggested to ensure the fragment size is equal to the block size so as to maintain compatibility.

Example layout

Block Offset Length Description
Byte 0 512B Boot record (if present)
Byte 512 512B Additional boot record data (if present)
byte 1024 1024B Superblock
Block 2 1 Block Block group descriptor table
Block 3 1 Block Block bitmap
Block 4 1 Block inode bitmap
Block 5 23 Block inode table
Block 28 1412 Bl data blocks

For the curious, block 0 always points to the first sector of the disk or partition and will always contain the boot record if one is present.

The superblock is always located at byte offset 1024 from the start of the disk or partition. In a 1KiB block-size formatted file system, this is block 1, but will always be block 0 (at 1024 bytes within block 0) in larger block size file systems.

The layout on disk is very predictable as long as you know a few basic information; block size, blocks per group, inodes per group. This information is all located in, or can be computed from, the superblock structure.

Nevertheless, unless the image was crafted with controlled parameters, the position of the various structures on disk (except the superblock) should never be assumed. Always load the superblock first.

Notice how block 0 is not part of the block group 0 in 1KiB block size file systems. The reason for this is block group 0 always starts with the block containing the superblock. Hence on 1KiB block systems, block group 0 starts at block 1, but on larger block sizes it starts on block 0. For more information, see the sfirstdatablock superblock entry.


The superblock is always located at byte offset 1024 from the beginning of the file, block device, or partition formatted with ext2 and later variants (ext3, ext4).

Its structure is mostly constant from ext2 to ext3 and ext4 with only some minor changes.

Offset Bytes Description
0x0000 4 s_inodes_count
0x0004 4 s_blocks_count
0x0008 4 s_r_blocks_count
0x000C 4 s_free_blocks_count
0x0010 4 s_free_inodes_count
0x0014 4 s_first_data_block
0x0018 4 s_log_block_size
0x001C 4 s_log_frag_size
0x0020 4 s_blocks_per_group
0x0024 4 s_frags_per_group
0x0028 4 s_inodes_per_group
0x002C 4 s_mtime
0x0030 4 s_wtime
0x0034 2 s_mnt_count
0x0036 2 s_max_mnt_count
0x0038 2 s_magic
0x003A 2 s_state
0x003C 2 s_errors
0x003E 2 s_minor_rev_level
0x0040 4 s_lastcheck
0x0044 4 s_checkinterval
0x0048 4 s_creator_os
0x004C 4 s_rev_level
0x0050 2 s_def_resuid
0x0052 2 s_def_resgid
0x0054 4 s_first_ino
0x0058 2 s_inode_size
0x005A 2 s_block_group_nr
0x005C 4 s_feature_compat
0x0060 4 s_feature_incompat
0x0064 4 s_feature_ro_compat
0x0068 16 s_uuid
0x0078 16 s_volume_name
0x0088 64 s_last_mounted
0x00C8 4 s_algo_bitmap
0x00CC 1 s_prealloc_blocks
0x00CD 1 s_prealloc_dir_blocks
0x00CE 2 (alignment)
0x00D0 16 s_journal_uuid
0x00E0 4 s_journal_inum
0x00E4 4 s_journal_dev
0x00E8 4 s_last_orphan
0x00EC 4x4(16) s_hash_seed
0x00FC 1 s_def_hash_version
0x00FD 3 padding - reserved for future expansion
0x0100 4 s_default_mount_options
0x0104 4 s_first_meta_bg
0x0108 760 Unused - reserved for future expansion


32bit value indicating the total number of inodes, both used and free, in the file system. This value must be lower or equal to (sinodespergroup * number of block groups). It must be equal to the sum of the inodes defined in each block group.


32bit value indicating the total number of blocks in the system including all used, free, and reserved. This value must be lower or equal to (sblockspergroup * number of block groups). It must be equal to the sum of the blocks defined in each block group.


32bit value indicating the total number of blocks reserved for the usage of the super user. This is most useful if for some reason a user, maliciously or not, fill the system to capacity; the super user will have this specified amount of free blocks at his disposal so he can edit and save configuration files.


32bit value indicating the total number of free blocks, including the number of reserved blocks (see srblockscount). This is a sum of all free blocks of all the block groups.


32bit value indicating the total number of free inodes. This is a sum of all free inodes of all the block groups.


32bit value identifying the first data block, in other words the id of the block containing the superblock structure. NOTE: 1 for block size of 1KiB, otherwise 0.


The block size is computated using this 32bit value as the number of bits to shift left the value of 1024. This value may only be positive.


The fragment size is computed using this 32bit value as the number of bits to shift left the value 1024. Negative values will shift the bit right rather than left.


32bit value indicating the total number of blocks per group. This value in combination with sfirstdatablock can be used to determine the block groups boundaries.


32bit value indicating the total number of fragments per group. It is also used to determine the size of the block bitmap of each block group.


32bit value indicating the total number of inodes per group. This is also used to determine the size of the inode bitmap of each block group. Note that you cannot have more than (block size in bytes * 8) inodes per group as the inode bitmap must fit within a single block. This value must be a perfect multiple of inodes that can fit in a block ((1024<<slogblocksize)/sinodesize).

s_mtime Unix time, as defined by POSIX, of the last time the file system was mounted.

s_wtime Unix time, as defined by POSIX, of the last write access to the file system.

s_mnt_count 32bit value indicating how many times the file system was mounted since the last time it was fully verified.

s_max_mnt_count 32bit value indicating the maximum number of times that the file system may be mounted before a full check is performed.

s_magic 16bit value identifying the file system as ext2. The value is currently fixed to EXT2SUPERMAGIC of value 0xEF53.


16bit value indicating the file system state. When the file system is mounted, this state is set to EXT2ERRORFS(0x0002). After the file system was cleanly unmounted, this value is set to EXTVALIDFS(0x0001). When mounting the file system, if a value of 0x0002 is encountered it means the file system was not cleanly unmounted and most likely contain errors that will need to be fixed.


16bit value indicating what the file system driver should do when an error is detected. The following values have been defined:

Value Description
0x0001 Continue as if nothing happened
0x0002 Remount as read only
0x0003 Cause a kernel panic


16bit value identifying the minor revision level with its revision level.


Unix time, as defined by POSIX, of the last file system check.


Maximum Unix time interval, as defined by POSIX, allowed between file system checks.


32bit identifier of the OS that created the file system. Defined values are:

Value Description
0x00000000 Linux
0x00000001 GNU HURD
0x00000002 MASIX
0x00000003 FreeBSD
0x00000004 Lites


32bit revision level value. 0 or 1.


16bit value used as the default user id for reserved blocks. (defaults to 0)


16bit value used as the default group id for reserved blocks. (defaults to 0)


32bit value used as index to the first inode usable for standard files. In rev 0, the first non-reserved inode is fixed to 11. In rev 1 and later this value may be set to any value.


16bit value indicating the size of the inode structure. In rev 0, this value is always 128. In rev 1 and later, this value must be a perfect power of 2 and must be smaller or equal to the block size (1<<slogblocksize).


16bit value used to indicate the block group number hosting this superblock structure. This can be used to rebuild the file system from any superblock backup.


32bit bitmask of compatible features. The file system implementation is free to support them or not without risk of damaging the meta-data.

Bit Description
0 Block pre-allocation for new directories
1 Imagic inodes
2 An ext3 journal exists
3 Extended inode attributes are present
4 Non-standard inode size used
5 Directory indexing


32bit bitmask of incompatible features. The file system implementation should refuse to mount the file system if any of the indicated features are unsupported. An implementation not supporting these features would be unable to properly use the file system. For example, if compression is being used and an executable file would be unusable after being read from the disk if the system does not know how to uncompress it.

Bit Description
0 Disk/File compression is used.
1 Filetype
2 Recovery
3 Journal
4 Meta blockgroup


32bit bitmask of 'read-only' features. The file system implementation should mount as read-only if any of the indicated feature is unsupported

Bit Description
0 Sparse superblock
1 Large file support, 64-bit filesize
2 Binary tree sorted directory files


128bit value used as the volume id. This should, as much as possible, be unique for each file system formatted.


16 bytes volume name, mostly unused. A valid volume name would consist only of ISO-Latin-1 characters and be 0 terminated.


64 bytes directory path where the file system was last mounted. While not normally used, it could serve for auto-finding the mountpoint when not indicated on the command line. Again the path should be 0 terminated for compatibility reasons. Valid path is constructed from ISO-Latin-1 characters.


32bit value used by compression algorithms to determine the compression method(s) used.

Bit Description
0 LZV1


8bit value representing the number of blocks the implementation should attempt to pre-allocate when creating a new regular file.


8bit value representing the number of blocks the implementation should attempt to pre-allocate when creating a new directory.


16byte value containing the uuid of the journal superblock.


32bit inode number of the journal file.


32bit device number of the journal file.


32bit inode number, pointing to the first inode in the list of inodes to delete.


An array of 4 32bit values containing the seeds used for the hash algorithm for directory indexing.


An 8bit value containing the default hash version used for directory indexing.


A 32bit value containing the default mount options for this file system.


A 32bit value indicating the block group ID of the first meta block group.


The block group descriptor table is an array of block group descriptors, used to define parameters of all the block groups. It provides the location of the inode bitmap and inode table, block bitmap, number of free blocks and inodes, and some other useful information.

The block group descriptor table starts on the first block following the superblock. This would be the third block on a 1KiB, or second block for other block-sized file systems. Shadow copies of the block descriptor table are also stored with every copy of the superblock.

Depending on how many block groups are defined, this table can require multiple blocks of storage. Always refer to the superblock in case of doubt.

Structure as follows:

Offset Bytes Description
0x00 4 Block ID of the first block of the 'block bitmap' for the group represented.
0x04 4 Block ID of the first block of the 'inode bitmap' for the group represented.
0x08 4 Block ID of the first block of the 'inode table' for the group represented.
0x0C 2 Value indicating the total number of free blocks for the represented group.
0x0E 2 Value indicating the total number of free inodes for the represented group.
0x10 2 Value indicating the total number of inodes allocated to directories for the represented group.
0x12 2 Value used for padding the structure on a 32bit boundary.
0x14 12 Reserved for future revisions.

For each block group in the file system, such a groupdesc is created. Each represent a single block group within the file system and the information within any one of them is pertinent only to the group it is describing. Every block group descriptor table contains all the information about all the block groups.


On small filesystems, the 'block bitmap' is normally located at the first block, or second block if a superblock backup is present, of each block group. Its official location can be determined by reading offset 0x00 of the BGDT.

Each bit represents the current state of a block within that block group, where 1 means 'used' and 0 'free/available'.


The 'Inode Bitmap' works in a similar way to the 'Block Bitmap', difference being in each bit representing an inode in the inode table rather than a block.

There is one inode bitmap per group and its location may be determined by reading offset 0x04 in the BGDT.

When the inode table is created, all reserved inodes are marked as used. In rev 0 this is the first 11 inodes.


The inode table is used to keep track of every directory, regular file, symbolic link, or special file; their location, size, type and access rights are all stored in inodes. There is no filename stored in the inode itself, names are contained in directory files only.

There is one inode table per block group and it can be located by reading offset 0x08 of the BGDT, and number of inodes per table can be determined by reading offset 0x0028 of the superblock.

Each inode contains the information about a single physical file on the system. A file can be a directory, a socket, a buffer, character or block device, symbolic link or a regular file. So an inode can be seen as a block of information related to an entity, describing its location on disk, its size, and its owner. An inode is arranged like this:

Offset Bytes Description
0x00 2 Value used to indicate the format of the described file and access rights. See [ i_mode table ] for possible values.
0x02 2 User ID associated with the file.
0x04 4 Rev 0, signed 32bit value indicating size of file in bytes. Rev 1, lower 32bits of regular file size.
0x08 4 Value representing Unix time of the last time this inode was accessed.
0x0C 4 Value representing unix time of when the inode was created.
0x10 4 Value representing unix time of the last time this inode was modified.
0x14 4 Value representing unix time of when the inode was deleted.
0x18 2 Value of the POSIX group having access to this file.
0x1A 2 Value indicating how many times this particular inode is linked. Typically 1. Each hard link increments count.
0x1C 4 Value representing the total # of 512byte blocks reserved to contain the data of this inode. Block #s in offset 0x34
0x20 4 Flag register indicating how the FS implementation should behave when accessing inode. See [ i_flags table ].
0x24 4 OS dependant value.
0x28 60 Array of 32bit values pointing to blocks containing the data for this inode. See [ i_block behavior ] for more info.
0x64 4 Value used to indicate file version.
0x68 4 Value indicating block number containing extended attributes. Always 0 in rev 0.
0x6C 4 Rev 0, 0. Rev 1, upper 32bits of 64bit file size.
0x70 4 Value indicating the location of the file fragment
0x74 12 OS dependant structure.

Reserved inodes:

Inode# Name Description
1 BAD_INO Bad blocks inode
2 ROOT_INO Root directory inode
3 ACL_IDX_INO ACL index inode (deprecated)
4 ACL_DATA_INO ACL data inode (deprecated)
5 BOOT_LOADER_INO Boot loader inode
6 UNDEL_DIR_INO Undelete directory inode
  • i_mode table: (values can be combined to add mixed-mode behavior)*
Value Description
[file format] [file format]
0xC000 socket
0xA000 symbolic link
0x8000 regular file
0x6000 block device
0x4000 directory
0x2000 character device
0x1000 fifo
[process execution user/group override] [process execution user/group override]
0x0800 Set process User ID
0x0400 Set process Group ID
0x0200 sticky bit
[access rights] [access right]
0x0100 user read
0x0080 user write
0x0040 user execute
0x0020 group read
0x0010 group write
0x0008 group execute
0x0004 others read
0x0002 others write
0x0001 others execute
  • i_flags table:*
Bit Description
0 Secure deletion
1 Record for undelete
2 Compressed file
3 Synchronous updates
4 Immutable file
5 Append only
6 Do not dump/delete file
7 Do not update access time
[reserved for compression usage] res
8 Dirty (modified)
9 Compressed blocks
10 Access raw compressed data
11 Compression error
[end of compression flags] end
12 B-tree format directory
12 Hash indexed directory
13 AFS directory
14 Journal file data
31 Reserved for ext2 library

i_block behavior:

Word Behavior
0-11 Direct blocks
12 First indirect block, address to a block containing data.
13 Doubly-indirect block, points to an array of indirect block pointers.
14 Triply-indirect block, points to an array of doubly-indirect block pointers.
[Any value of 0 indicates end of file]  


Inodes are all numerically ordered. The 'inode number' is an index in the inode table to an inode structure. The size of the inode table is fixed at format time; it is built to hold a maximum number of entries. Due to the large amount of entries created, the table is quite big and thus, it is split equally among all the blog groups.

Offset 0x0028 of the superblock tells us how many inodes are defined per group. Know that inode 1 is the first inode defined in the inode table, one can use the following formulaes:

block group = (inode - 1)/sinodespergroup[offset 0x0028 of SB]

Once the block is identified, the local inode index for the local inode table can be identified using:

local inode index = (inode - 1) % sinodespergroup


Directories are used to heirarchically organize files. Each directory can contain other directories, regular files, and special files.

Directories are stored as data block and referenced by an inode. They can be identified by the file type 0x4000 in the imode field of the inode.

The second entry of the Inode table contains the inode pointing to the data of the root directory; as defined by the ROOTINO constant.

In rev 0 directories could only be stored in a linked list. Rev 1 and later introduced indexed directories. The indexed directory is backward compatible with linked list directory; this is achieved by inserting empty directory entry records to skip over hash indexes.


A directory file is a linked list of directory entry structures. Each structure contains the name of the entry, the inode associated with the data of this entry, and the distance within the directory file to the next entry.

In rev 0, the type of the entry (file, directory, special file, etc) has to be looked up in the inode of the file. In rev 0.5 and later, the file type is also contained in the directory entry structure.

Linked Directory Entry Structure:

Offset Bytes Description
0x000 4 Inode number of the file entry. 0 indicates that the entry is not used.
0x004 2 Unsigned displacement to the next directory entry. See [reclen] for further details.
0x006 1 Unsigned value indicating how many bytes of character data are contained in the name.
0x007 1 Unsigned value used to indicate file type. See [file type table] for further explanation.
  • rec_len *

Unsigned displacement to the next directory entry from the start of the current directory entry. This field must have a value at least equal to the length of the current record.

The directory entries must be aligned on 4byte boundaries and there cannot be any directory entry spanning multiple data blocks. If an entry cannot completely fit in one block, it must be pushed to the next data block and the reclen of the previous entry properly adjusted.

File type table:

Value Description
0 Unknown File Type
1 Regular File
2 Directory File
3 Character Device
4 Block Device
5 Buffer File
6 Socket File
7 Symbolic Link


Example home directory:

  1. .
  2. ..
  3. .bashprofile
  4. .bashrc
  5. mbox
  6. publichtml
  7. tmp

Directory structure and data as stored on disk:

Offset Value Description
[Directory Entry 0]    
0x0000 0x000BF402 Inode number: 783362
0x0004 0x000C Record length: 12
0x0006 0x01 Name length: 1
0x0007 0x02 File type: Directory
0x0008 '.' Name: .
0x0009 0x00000 Padding
[Directory Entry 1]    
0x000C 0x0010EF01 Inode number: 1109761
0x0010 0x000C Record length: 12
0x0012 0x02 Name length: 2
0x0013 0x02 File type: Directory
0x0014 '..' Name: ..
0x0016 0x0000 Padding
[Directory Entry 2]    
0x0018 0x000BF404 Inode number: 783364
0x001C 0x0018 Record length: 24
0x001E 0x0D Name length: 13
0x001F 0x01 File type: Regular File
0x0020 '.bashprofile' Name: .bashprofile
0x002D 0x000000 Padding
[Directory Entry 3]    
0x0030 0x000BF403 Inode number: 783363
0x0034 0x0010 Record length: 16
0x0036 0x07 Name length: 7
0x0037 0x01 File type: Regular File
0x0038 '.bashrc' Name: .bashrc
0x003F 0x00 Padding
[Directory Entry 4]    
0x0040 0x000BF411 Inode number: 783377
0x0044 0x000C Record length: 12
0x0046 0x04 Name length: 4
0x0047 0x01 File type: Regular File
0x0048 'mbox' Name: mbox
[Directory Entry 5]    
0x004C 0x000BF4B9 Inode number: 783545
0x0050 0x0014 Record length: 20
0x0052 0x0B Name length: 11
0x0053 0x02 File type: Directory
0x0054 'publichtml' Name: publichtml
0x005F 0x00 Padding
[Directory Entry 6]    
0x0060 0x000A36AA Inode number: 669354
0x0064 0x000C Record length: 12
0x0066 0x03 Name length: 3
0x0067 0x02 File type: Directory
0x0068 'tmp' Name: tmp
0x006B 0x00 Padding
[Directory Entry 7]    
0x006C 0x00000000 Inode number: 0
0x0070 0x0F94 record length: 3988
0x0072 0x00 Name length: 0
0x0073 0x00 File type: Unknown
0x0074 0x00 Name: <null> + 3980B Padding

3 FAT32 Fragmentations

3.1 Fragmentation

The FAT file system does not contain built-in mechanisms which prevent newly written files from becoming scattered across the partition. On volumes where files are created and deleted frequently or their lengths often changed, the medium will become increasingly fragmented over time.

While the design of the FAT file system does not cause any organizational overhead in disk structures or reduce the amount of free storage space with increased amounts of fragmentation, as it occurs with external fragmentation, the time required to read and write fragmented files will increase as the operating system will have to follow the cluster chains in the FAT (with parts having to be loaded into memory first in particular on large volumes) and read the corresponding data physically scattered over the whole medium reducing chances for the low-level vlock device driver to perform multi-sector disk I/O or initiate larger DMA transfers, thereby effectively increasing I/O protocol overhead as well as arm movement and head settle times inside the disk drive. Also, file operations will become slower with growing fragmentation as it takes increasingly longer for the operating system to find files or free clusters.

Other file systems such as HPFS or exFAT, use free space bitmaps that indicate used and available clusters, which could then be quickly looked up in order to find free contiguous areas. Another solutions is the linkage of all free clusters into one or more lists (as is done in Unix systems). Instead, the FAT has to be scanned as an array to find free clusters, which can lead to performance penalties with large disks.

In fact, seeking for files in large subdirectories or computing the free disk space on FAT volumes is one of the most resource intensive operations, as it requires reading the directory tables or even the entire FAT linearly. Since the total amount of clusters and the size of their entries in the FAT was still small on FAT12/16 volumes, this could be tolerated most of the time, considering that the introduction of more sophisticated disk structures would have also increased the complexity and memory footprint of real-mode operating systems with their minimum total memory requirements of 128KiB or less (such as with DOS) for which FAT has been designed and optimized originally.

With the introduction of FAT32, long seek and scan times became more apparent, particularly on very large volumes. A possible justification for limiting the maximum size of FAT32 partitions was the time required to perform a 'DIR' operation, which always displays the free disk space as the last line. Displaying this line took longer and longer as the number of clusters increased. FAT32 therefore introduced a special file system information sector where the previously computed amount of free space is preserved over power cycles, so that the free space counter needs to be recalculated only when a removable FAT32 formatted medium gets ejected without first unmounting it or if the system is switched off without properly shutting down the operating system, a problem mostly visible with pre-ATX style PCs, on plain DOS systems and some battery-powered consumer products.

Huge cluster sizes can cause internal fragmentation, since files are rarely exact multiples of cluster size. This problem is worse with a large number of small files.

Various optimizations and tweaks to the implementation of FAT file system drivers, block device drivers, and disk tools have been devised to overcome most of the performance bottlenecks in the file system's inherent design without having to change the layout of the on-disk structures. They can be divided into on-line and off-line methods and work by trying to avoid fragmentation in the file system in the first place, deploying methods to better cope with existing fragmentation, and by reordering and optimizing the on-disk structures. With optimiziations in place, the performance on FAT volumes can often reach that of more sophisticated file systems in practical scenarios, while at the same time retaining the advantage of being accessible even on very small or old systems.

DOS 3.0 and higher will not immediately reuse disk space of deleted files for new allocations but instead seek for previously unused space before starting to use disk space of previously deleted files as well. This not only helps to maintain the integrity of deleted files for as long as possible but also speeds up file allocations and avoids fragmentation, since never before allocated disk space is always unfragmented. DOS accomplishes this by keeping a pointer to the last allocated cluster on each mounted volume in memory and starts searching for free space from this location upwards instead of at the beginning of the FAT, as it was still done by DOS 2.x. If the end of the FAT is reached, it would wrap around to continue the search at the beginning of the FAT until either free space has been found or the original position has been reached again without having found free space. These pointers are initialized to point to the start of the FATs after bootup, but on FAT32 volumes, DOS 7.1 and higher will attempt to retreive the last position from the FS Information Sector. This mechanism is defeated, however, if an application often deletes and recreates temporary files as the operating system would then try to maintain the integrity of void data effectively causing more fragmentation in the end. In some DOS versions, the usage of a special API function to create temporary files can be used to avoid this problem.

Additionally, directory entries of deleted files will be marked 0xE5 since DOS 3.0. DOS 5.0 and higher will start to reuse these entries only when previously unused directory entries have been used up in the table and the system would otherwise have to expand the table itself.

Since DOS 3.3 the OS provides the means to improve performance of file operations with FASTOPEN by keeping track of the position of recently opened files or directories in various forms of lists (MS-DOS/PC DOS) or hash tables (DR-DOS), which can reduce file seek and open times significantly. Before DOS 5.0 special care must be taken when using such mechanisms in conjunction with disk defragmentation software bypassing the file system or disk drivers.

Windows NT will allocated disk space to files on FAT in advance, selecting large contiguous areas, but in case of a failure, files which were being appended appear larger than they were ever written into, with a lot of random data at the end.

Other high-level mechanisms may read in and process larger parts or the complete FAT on startup or on demand when needed and dynamically build up in-memory tree representations of the volume's file structures different from the on-disk structures. This may, on volumes with many free clusters, occupy even less memory than an image of the FAT itself. In particular on highly fragmented or filled volumes, seeks become much faster than with linear scans over the actual FAT, even if an image of the FAT would be stored in memory. Also, operating on the logically high level of files and cluster- chains instead of on sector or track level, it becomes possible to avoid some degree of file fragmentation in the first place or to carry out local file defragmentation and reordering of directory entries based on their names or access patterns in the background.

Some of the perceived problems with fragmentation of FAT file systems also result from performance limitations of the underlying block device drivers, which becomes more visible the lesser memory is available for sector buffering and track blocking/deblocking:

While the single-tasking DOS had provisions for multi-sector reads and track blocking/deblocking, the OS and the traditional PC hard disk architecture (only one outstanding I/O request at a time and no DMA transfers) originally did not contain mechanisms which could alleviate fragmentation by asynchronously prefetching next data while the application was processing the previous chunks. Such features became available later. Later DOS versions also provided built-in support for look-ahead sector buffering and came with dynamically loadable disk caching programs working on physical or logical sector level, often utilizing EMS or XMS memory and sometimes providing adaptive caching strategies or even run in protected mode through DPMS or Cloaking to increase performance by gaining direct access to the cached data in linear memory rather than through conventional DOS APIs.

Write-behind caching was often not enabled by default with Microsoft software (if present) given the problem of data loss in case of a power failure or crash, made easier by the lack of hardware protection between applications and the system.

4 Fixed Point

Add and subtract use a simple 32-bit integer and subtract.

Multiply and divide are a bit more involved.

First allow an extra set of bytes for each operand to be shifted left into, also supplying a single shift counter for both operands.

Shift each number left until there are no 1s right of the 'decimal point', and for each shift increment the shift counter.

Perform normal integer multiplication or division as normal.

Afterwards shift the result right, decrementing the shift counter each time until it reaches zero.

4.1 BCD fixed point

1/n Decimal
2 0.5
4 0.25
8 0.125
16 0.0625
32 0.03125
64 0.015625
128 0.0078125
256 0.00390625

4.1.1 Convert integer to BCD

Shift left, if nibble is five or greater, add three, 8 times.

Test case 1111 1111 (FFh)

1111 1111 0000 0000 0000 (000) start
1111 1110 0000 0000 0001 (001) shift left
1111 1100 0000 0000 0011 (003) shift left
1111 1000 0000 0000 0111 (007) shift left
1111 1000 0000 0000 1010 (00A) add 3
1111 0000 0000 0001 0101 (015) shift left
1111 0000 0000 0001 1000 (018) add 3
1110 0000 0000 0011 0001 (031) shift left
1100 0000 0000 0110 0011 (063) shift left
1100 0000 0000 1001 0011 (093) add 3
1000 0000 0001 0010 0111 (127) shift left
1000 0000 0001 0010 1010 (12A) add 3
0000 0000 0010 0101 0101 (255) shift left

Test case 1010 1010 (AAh)

1010 1010 0000 0000 0000 (000) start
0101 0100 0000 0000 0001 (001) shift left
1010 1000 0000 0000 0010 (002) shift left
0101 0000 0000 0000 0101 (005) shift left
0101 0000 0000 0000 1000 (008) add 3
1010 0000 0000 0001 0000 (010) shift left
0100 0000 0000 0010 0001 (021) shift left
1000 0000 0000 0100 0010 (042) shift left
0000 0000 0000 1000 0101 (085) shift left
0000 0000 0000 1011 1000 (0B8) add 3
0000 0000 0001 0111 0000 (170) shift left

4.1.2 Convert fixed-point fractional to BCD


  1. Test case 0.1111b
    • .1111 * 1010 = 1001.0110 = 9.6h (0.9xxx)
    • (integer portion placed in 'converted' output)
    • .0110 * 1010 = 0011.1100 = 3.Ch (0.93xx)
    • .1100 * 1010 = 0111.1000 = 7.8h (0.937x)
    • .1000 * 1010 = 0101.0000 = 5.0h (0.9375)
  2. Test case 0.00000001b
    • .00000001 * 1010 = 0000.00001010 = 0.0Ah (0.0xxxxxxx)
    • .00001010 * 1010 = 0000.01100100 = 0.64h (0.00xxxxxx)
    • .01100100 * 1010 = 0011.11101000 = 3.E8h (0.003xxxxx)
    • .11101000 * 1010 = 1001.00010000 = 9.10h (0.0039xxxx)
    • .00010000 * 1010 = 0000.10100000 = 0.A0h (0.00390xxx)
    • .10100000 * 1010 = 0110.01000000 = 6.40h (0.003906xx)
    • .01000000 * 1010 = 0010.10000000 = 2.80h (0.0039062x)
    • .10000000 * 1010 = 0101.00000000 = 5.00h (0.00390625)
  3. Test case 0.11111111b
    • .11111111 * 1010 = 1001.11110110 = 9.F6h (0.9xxxxxxx)
    • .11110110 * 1010 = 1001.10011100 = 9.9Ch (0.99xxxxxx)
    • .10011100 * 1010 = 0110.00011000 = 6.18h (0.996xxxxx)
    • .00011000 * 1010 = 0000.11110000 = 0.F0h (0.9960xxxx)
    • .11110000 * 1010 = 1001.01100000 = 9.60h (0.99609xxx)
    • .01100000 * 1010 = 0011.11000000 = 3.C0h (0.996093xx)
    • .11000000 * 1010 = 0111.10000000 = 7.80h (0.9960937x)
    • .10000000 * 1010 = 0101.00000000 = 5.00h (0.99609375)

4.1.3 BCD to bin


  1. Test case 255 (0010 0101 0101)
    • 0010 0101 0101 -> 0001 0010 1010 ; 1000 0000 (80h) ; Shift right, low nibble over seven
    • 0001 0010 1010 -> 0001 0010 0111 ; 1000 0000 (80h) ; Subtract 3
    • 0001 0010 0111 -> 0000 1001 0011 ; 1100 0000 (C0h) ; Shift right, middle nibble over seven
    • 0000 1001 0011 -> 0000 0110 0011 ; 1100 0000 (C0h) ; Subtract 3
    • 0000 0110 0011 -> 0000 0011 0001 ; 1110 0000 (E0h) ; Shift right, no nibble over seven
    • 0000 0011 0001 -> 0000 0001 1000 ; 1111 0000 (F0h) ; Shift right, low nibble over seven
    • 0000 0001 1000 -> 0000 0001 0101 ; 1111 0000 (F0h) ; Subtract 3
    • 0000 0001 0101 -> 0000 0000 1010 ; 1111 1000 (F8h) ; Shift right, low nibble over seven
    • 0000 0000 1010 -> 0000 0000 0111 ; 1111 1000 (F8h) ; Subtract 3
    • 0000 0000 0111 -> 0000 0000 0011 ; 1111 1100 (FCh) ; Shift right, no nibble over seven
    • 0000 0000 0011 -> 0000 0000 0001 ; 1111 1110 (FEh) ; Shift right
    • 0000 0000 0001 -> 0000 0000 0000 ; 1111 1111 (FFh) ; Shift right
  2. Test case 063 (0000 0110 0011)
    • 0000 0110 0011 -> 0000 0011 0001 ; 1000 0000 (80h) ; Shift right
    • 0000 0011 0001 -> 0000 0001 1000 ; 1100 0000 (C0h) ; Shift right, low nibble over seven
    • 0000 0001 1000 -> 0000 0001 0101 ; 1100 0000 (C0h) ; Subtract 3
    • 0000 0001 0101 -> 0000 0000 1010 ; 1110 0000 (E0H) ; Shift right, low nibble over seven
    • 0000 0000 1010 -> 0000 0000 0111 ; 1110 0000 (E0h) ; Subtract 3
    • 0000 0000 0111 -> 0000 0000 0011 ; 1111 0000 (F0h) ; Shift right
    • 0000 0000 0011 -> 0000 0000 0001 ; 1111 1000 (F8h) ; Shift right
    • 0000 0000 0001 -> 0000 0000 0000 ; 1111 1100 (FCh) ; Shift right
    • 0000 0000 0000 -> 0000 0000 0000 ; 0111 1110 (7Eh) ; Shift right
    • 0000 0000 0000 -> 0000 0000 0000 ; 0011 1111 (3Fh) ; Shift right
  3. Test case 170 (0001 0111 0000)
    • 0001 0111 0000 -> 0000 1011 1000 ; 0000 0000 (00h) ; Shift right, low and middle nibbles over seven
    • 0000 1011 1000 -> 0000 1000 0101 ; 0000 0000 (00h) ; subtract 3
    • 0000 1000 0101 -> 0000 0100 0010 ; 1000 0000 (80h) ; Shift right
    • 0000 0100 0010 -> 0000 0010 0001 ; 0100 0000 (40h) ; Shift right
    • 0000 0010 0001 -> 0000 0001 0000 ; 1010 0000 (A0h) ; Shift right
    • 0000 0001 0000 -> 0000 0000 1000 ; 0101 0000 (50h) ; Shift right, low nibble over seven
    • 0000 0000 1000 -> 0000 0000 0101 ; 0101 0000 (50h) ; Subtract 3
    • 0000 0000 0101 -> 0000 0000 0010 ; 1010 1000 (A8h) ; Shift right
    • 0000 0000 0010 -> 0000 0000 0001 ; 0101 0100 (54h) ; Shift right
    • 0000 0000 0001 -> 0000 0000 0000 ; 1010 1010 (AAh) ; Shift right

4.1.4 BCD Fractional to Fixed Point fractional

Left shift BCD fractional, add 6 to nibbles preceding 'overshifted' nibble, correct for out of bounds in upward cascade.

  1. Test Case: 0.123 (0000.0001 0010 0011)
    • 0000.0001 0010 0011 > 0000.0010 0100 0110 (0.246) ; 0.0xxx xxxx ;shift, no issues detected, take 0 from output
    • 0000.0010 0100 0110 > 0000.0100 1000 1100 (0.48C) ; 0.0xxx xxxx ;shift, low nibble out of bounds
    • 0000.0100 1000 1100 > 0000.0100 1001 0010 (0.492) ; 0.00xx xxxx ;correct out of bounds, take 0
    • 0000.0100 1001 0010 > 0000.1001 0010 0100 (0.924) ; 0.00xx xxxx ;'overshift' detected
    • 0000.1001 0010 0100 > 0000.1001 1000 0100 (0.984) ; 0.000x xxxx ;correct for overshift, take 0
    • 0000.1001 1000 0100 > 0001.0011 0000 1000 (1.308) ; 0.000x xxxx ;multiple 'overshift' events
    • 0001.0011 0000 1000 > 0000.1001 0110 1000 (0.968) ; 0.0001 xxxx ;add 6 to preceding nibbles and take off 1 from output.
    • 0000.1001 0110 1000 > 0001.0010 1101 0000 (1.2D0) ; 0.0001 xxxx ;multiple overshift events and an out of bounds
    • 0001.0010 1101 0000 > 0001.1000 1101 0110 (1.8D6) ; 0.0001 xxxx ;corrected for overshift
    • 0001.1000 1101 0110 > 0000.1001 0011 0110 (0.936) ; 0.0001 1xxx ;corrected out of bounds, take off 1 from output
    • 0000.1001 0011 0110 > 0001.0010 0110 1100 (1.26C) ; 0.0001 1xxx ;Overshift and out of bounds detected
    • 0001.0010 0110 1100 > 0001.1000 0110 1100 (1.86C) ; 0.0001 1xxx ;corrected for overshift
    • 0001.1000 0110 1100 > 0000.1000 0111 0010 (0.872) ; 0.0001 11xx ;corrected for out of bounds, take off 1 from output
    • 0000.1000 0111 0010 > 0001.0000 1110 0100 (1.0E4) ; 0.0001 11xx ;overshift and out of bounds detected
    • 0001.0000 1110 0100 > 0001.0110 1110 0100 (1.6E4) ; 0.0001 11xx ;Correct for overshift
    • 0001.0110 1110 0100 > 0000.0111 0100 0100 (0.744) ; 0.0001 111x ;correct for out of bounds, take 1 from output
    • 0000.0111 0100 0100 > 0000.1110 1000 1000 (0.E88) ; 0.0001 111x ;out of bounds detected
    • 0000.1110 1000 1000 > 0000.0100 1000 1000 (0.488) ; 0.0001 1111 ;out of bounds corrected, take 1 from output
  2. Test Case 0.5 (0000.0101)
    • 0000.0101 > 0000.1010 ; 0.x ;out of bounds detected
    • 0000.1010 > 0000.0000 ; 0.1 ;corrected for out of bounds, take 1 from output

5 Floating Point Binary Z80

Floating Point Math

5.1 Single precision

32-bit floating point value


  • S=sign
  • E=exponent
  • M=mantissa

Sign bit is 0 for positive, 1 for negative.

Exponent is biased by 127:

Power Bit pattern Decimal value
0 01111111 127
+1 10000000 128
-1 01111110 126
+127 11111110 254
-126 00000001 1

Special conditons:

Sign Exponent Mantissa Meaning
0 All 0's All 0's +0
1 All 0's All 0's -0
0 All 0's Nonzero +Denormal
1 All 0's nonzero -Denormal
0 All 1's All 0's +Infinity
1 All 1's All 0's -Infinity
0 All 1's nonzero NaN
1 All 1's nonzero NaN

Implied Mantissa bit:

The Mantissa is 23 bits long with an implied bit left of the radix. The implied bit is 1 for almost all circumstances. The implied bit is 0 only if the number is denormal.

5.1.1 Convert from decimal to binary floating point:

173.7 = b?

Sign = 0 (positive)

To get Exponent, repeatedly divide/multiply by two, while counting how many iterations, until there's there's only 1 to the left of the decimal point. Final result will be a normalised number. The number of iterations will be our exponent (positive for division, negative for multiplication).

\begin{align*} 173.7/2 &= 86.85 && 2^1\\ 86.85/2 &= 43.425 && 2^2\\ 43.425/2 &= 21.7125 && 2^3\\ 21.7125/2 &= 10.85625 && 2^4\\ 10.85625/2 &= 5.428125 && 2^5\\ 5.428125/2 &= 2.7140625 && 2^6\\ 2.7140625/2 &= 1.35703125 && 2^7 \text{Finished, power is 7.}\\ \end{align*}

Power is 7. Our binary exponent is: 7+127=134=b1000 _ 0110.

To get our binary Mantissa (for normals), we multiply the fractional part of our normalised number by two and allocate a 1 if the result is greater than 1, and 0 otherwise. When we get a 1, we subtract 1 from the number.

Normalised number into Mantissa:

Number X2 Result Binary result Comment  
0.35703125 0.7140625 0 Since we didn't get a 1, we only copy the number from the x2 Result column to the Number  
0.7140625 1.428125 1 Since we got a 1 here, when we copy the number over from the x2 Result column to the Number  
0.428125 0.85625 0 column of the next row, we subtract 1.  
0.85625 1.7125 1    
0.7125 1.425 1    
0.425 0.85 0    
0.85 1.7 1    
0.7 1.4 1    
0.4 0.8 0    
0.8 1.6 1    
0.6 1.2 1    
0.2 0.4 0 We've just got a number that we got before, meaning a recursive sequence. We can take a shortcut and copy this sequence until we fill up the mantissa.  

We now have our full floating point number: 0,100_0011_0,010_1101_1011_0011_0011_0011 =0x432DB333 ;commas separate bit fields

Now try a negative number:


Sign = 1

We can, from this point, act as if it's a positive number.

Normalise number:

0.75*2=1.5 2-1

Get exponent: 127-1 = 126 = 01111110

Normalised number, so implied bit is 1.

Get Mantissa bit pattern:

0.5*2 = 1 ;Nothing left, so fill in rest of mantissa with 0.

Our final floating point binary number is: 1,011_1111_0,100_0000_0000_0000_0000_0000 = 0xBF400000

5.2 Double Precision

64-bit floating point value



Exponent has bias of 1,023. Rest of process is exactly the same.

Practice: Convert Pi to single precision floating point


Sign is 0, since it's positive.

Normalize and acquire power

'' / 2 = 1.5707963267948966192313216916398 x 21 ;done

Get bit pattern of exponent

127+1=128=10000000 ;done

Get Mantissa pattern

Number x2 Bit comment
0.5707963267948966192313216916398 1.1415926535897932384626433832795 1  
0.1415926535897932384626433832795 0.283185307179586476925286766559 0  
0.283185307179586476925286766559 0.566370614359172953850573533118 0  
0.566370614359172953850573533118 1.132741228718345907701147066236 1  
0.132741228718345907701147066236 0.265482457436691815402294132472 0  
0.265482457436691815402294132472 0.530964914873383630804588264944 0  
0.530964914873383630804588264944 1.061929829746767261609176529888 1  
0.061929829746767261609176529888 0.123859659493534523218353059776 0  
0.123859659493534523218353059776 0.247719318987069046436706119552 0  
0.247719318987069046436706119552 0.495438637974138092873412239104 0  
0.495438637974138092873412239104 0.990877275948276185746824478208 0  
0.990877275948276185746824478208 1.981754551896552371493648956416 1  
0.981754551896552371493648956416 1.963509103793104742987297912832 1  
0.963509103793104742987297912832 1.927018207586209485974595825664 1  
0.927018207586209485974595825664 1.854036415172418971949191651328 1  
0.854036415172418971949191651328 1.708072830344837943898383302656 1  
0.708072830344837943898383302656 1.416145660689675887796766605312 1  
0.416145660689675887796766605312 0.832291321379351775593533210624 0  
0.832291321379351775593533210624 1.664582642758703551187066421248 1  
0.664582642758703551187066421248 1.329165285517407102374132842496 1  
0.329165285517407102374132842496 0.658330571034814204748265684992 0  
0.658330571034814204748265684992 1.316661142069628409496531369984 1  
0.316661142069628409496531369984 0.633322284139256818993062739968 1 ;Final bit, next bit would be a 1, so we round up

We now have our mantissa pattern: 10010010000111111011011

Concatenate them all together: 0,100_0000_0,100_1001_0000_1111_1101_1011 =0x40490FDB

Compare with Pi value from Propeller manual Pg. 93: 0x40490FDB