ZephyrZ80
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
2.1 BLOCKS
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.
2.2 BLOCK GROUPS
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.
2.3 INODES
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.
2.4 SUPERBLOCKS
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.
2.5 SYMBOLIC LINKS
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.
2.6 DISK ORGANIZATION
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.
2.7 SUPERBLOCK
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 |
s_inodes_count
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.
s_blocks_count
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.
s_r_blocks_count
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.
s_free_blocks_count
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.
s_free_inodes_count
32bit value indicating the total number of free inodes. This is a sum of all free inodes of all the block groups.
s_first_data_block
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.
s_log_block_size
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.
s_log_frag_size
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.
s_blocks_per_group
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.
s_frags_per_group
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.
s_inodes_per_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.
s_state
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.
s_errors
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 |
s_minor_rev_level
16bit value identifying the minor revision level with its revision level.
s_lastcheck
Unix time, as defined by POSIX, of the last file system check.
s_checkinterval
Maximum Unix time interval, as defined by POSIX, allowed between file system checks.
s_creator_os
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 |
s_rev_level
32bit revision level value. 0 or 1.
s_def_resuid
16bit value used as the default user id for reserved blocks. (defaults to 0)
s_def_resgid
16bit value used as the default group id for reserved blocks. (defaults to 0)
s_first_ino
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.
s_inode_size
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).
s_block_group_nr
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.
s_feature_compat
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 |
s_feature_incompat
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 |
s_feature_ro_compat
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 |
s_uuid
128bit value used as the volume id. This should, as much as possible, be unique for each file system formatted.
s_volume_name
16 bytes volume name, mostly unused. A valid volume name would consist only of ISO-Latin-1 characters and be 0 terminated.
s_last_mounted
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.
s_algo_bitmap
32bit value used by compression algorithms to determine the compression method(s) used.
Bit | Description |
---|---|
0 | LZV1 |
1 | LZRW3A |
2 | GZIP |
3 | BZIP2 |
4 | LZO |
s_prealloc_blocks
8bit value representing the number of blocks the implementation should attempt to pre-allocate when creating a new regular file.
s_prealloc_dir_blocks
8bit value representing the number of blocks the implementation should attempt to pre-allocate when creating a new directory.
s_journal_uuid
16byte value containing the uuid of the journal superblock.
s_journal_inum
32bit inode number of the journal file.
s_journal_dev
32bit device number of the journal file.
s_last_orphan
32bit inode number, pointing to the first inode in the list of inodes to delete.
s_hash_seed
An array of 4 32bit values containing the seeds used for the hash algorithm for directory indexing.
s_def_hash_version
An 8bit value containing the default hash version used for directory indexing.
s_default_mount_options
A 32bit value containing the default mount options for this file system.
s_first_meta_bg
A 32bit value indicating the block group ID of the first meta block group.
2.8 BLOCK GROUP DESCRIPTOR TABLE
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.
2.9 BLOCK BITMAP
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'.
2.10 INODE BITMAP
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.
2.11 INODE TABLE
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] |
2.12 LOCATING AN INODE
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
2.13 DIRECTORY STRUCTURE
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.
2.14 LINKED LIST DIRECTORY
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 |
2.15 SAMPLE DIRECTORY
Example home directory:
- .
- ..
- .bashprofile
- .bashrc
- mbox
- publichtml
- 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
MULTIPLY by 10, CONVERT, REPEAT UNTIL FRACTIONAL GONE
- 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)
- 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)
- 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
SHIFT RIGHT 1, IF NIBBLE > 7; SUBTRACT 3, BIT SHIFTED OUT SHIFTED INTO RESULT, 8 times
- 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
- 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
- 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.
- 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
- 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
Format: SEEE EEEE EMMM MMMM MMMM MMMM MMMM MMMM
- 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. | |
0 | ||||
1 | ||||
1 | ||||
0 | ||||
0 | ||||
1 | ||||
1 | ||||
0 | ||||
0 | ||||
1 | ||||
1 |
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:
-0.75
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
Format:
SEEEEEEEEEEEMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM ; 1 sign bit, 11 exponent bits, 52 mantissa bits
Exponent has bias of 1,023. Rest of process is exactly the same.
Practice: Convert Pi to single precision floating point
3.1415926535897932384…
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