Bits 'n' Bytes

To understand how DiskPatch works or to understand how the built-in disk editor can be used to examine and repair logical structures, it's good to have some understanding about disk structures. This chapter is meant as a primer and is not an in-depth description of each and every disk structure.

You may already know that a computer works with zeros and ones. It can only discriminate 2 states: something is on or something is off, something is either true or false etc. The entity that describes the two states is called a bit. By grouping several bits together the PC can 'grasp' more complex matters, like characters in our alphabet or decimal numbers. Eight zeros/ones 'grouped' together in one unit are referred to as a byte. The byte is a very important 'unit'; values regarding memory or disk sizes are expressed in Kilo-Bytes, Mega-Bytes etc.

Using 8 bits we can define 256 different combinations of zeros and ones (for example 00001111, 11110000 etc.). Rather than describing a state using a string of 8 zeros and ones, we like to be able to use a more compact notation: the Hexadecimal notation.

Decimal notation we all know; we group numbers in units of 10 and we have 10 characters available for writing down values: 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9. If you understand the following calculations, you understand decimal notations: 

05 + 04 = 09
09 + 01 = 10.

In the Hexadecimal system we have additional characters; A, B, C, D, E, F at our disposal for expressing values. If you understand the following calculations, you understand hexadecimal notations: 

09 + 06 = 0F
0F + 01 = 10.

We've already seen that by using 8 bits we can define 256 different states, so we should be able to express different combinations of zeros and ones in decimal or hexadecimal numbers. We will not explain how you can convert binary number to decimals or hexadecimals, it is only important that you understand that it can be done. If you can understand the following table however, you get the basic idea. If you need to convert binary to hex, hex to decimals etc. use the Windows calculator.

If you do not understand this table, then either don't worry about it, or do some 'Googling' to find more information on the subject.

Note: the most common way to denote a value as Hex is : 0xA1B1, where 0x defines the value A1B1 as being noted in Hex. Another well-known notation is 02h, where h denotes the value as 02 in Hex. Throughout this chapter both notations are used.

Certain standards and agreements exist about what a particular order of bytes represents. For example the ASCII standard allows us to represent characters in our alphabet by a specific sequences of bits. When software reads information from the hard disk, it therefore needs to know if it should interpret a given sequence of bytes as values to be used in calculations, or as ASCII characters (a text string).

In the end, all information on your hard disk can be displayed as an apparent chaos: Your MP3 files, your drawings, in the end it's noting else but a bunch of zeros and ones.

Sectors

A hard disk is capable of storing billions of bytes, so to address an individual byte (to know where something is stored), huge numbers would be required. To simplify addressing and finding information on a hard disk, bytes are grouped into units called 'sectors'. A sector is a group of 512 Bytes. We start counting sectors from zero, so in order to read what's in the 513th byte on a disk, we would need to address sector 1. Even if we're only interested in the value of one particular byte, we need to read an entire sector into memory. A sector is the smallest addressable unit on a disk (you can read more than one sector at the time, but you can't read less than one sector).

As mentioned before, a byte may represent a value, or for example an ASCII character. In the DiskPatch disk editor main window three columns are shown. The first column shows the sequencenumber of the bytes in the sector (also known as the offset), the second column displays the values (in hexadecimal notation) of the individual bytes, and in the 3rd column this same information is shown, however now interpreted by using the ASCII table.

All the information on a hard disk is organized in some way, which is defined by one (or more) of hundreds of protocols, specifications, conventions or standards that different organizations or software and operating system manufacturers have come up with over the years. And much of the information isn't defined by any of those and may only have meaning to specific software or operating systems, for example executable code or proprietary file formats.

There is one important convention you need to be aware of when editing raw sectors; Intel Byte ordering (little endian): whenever a value exceeds 255 (and thus more than one byte is required to store the value), bytes are stored in reverse order! So if we would need to store a decimal number > 255, we'd first convert it to hex, and then write the bytes to the disk in reverse order. So the decimal value of 41393, which equals A1B1 in hex is written to the disk as B1A1 (which is how the bytes will appear in a disk editor as well).
Please note that Intel Byte ordering is not used all the time, it is used in some cases, for example in conjunction with partition table data. For instance, some sections of the MBR are written according to Intel Byte order.

Addressing Sectors

A long time ago sectors were addressed using the cylinder-head-sector notation, or 'CHS addressing' for short. Try to visualize a hard disk being several platters on a spindle. Disk read/write heads float above the platter surface, one above and one below each platter. The individual platters are divided into tracks and the tracks are divided into sectors. The outer tracks form one cylinder, all next tracks form the next cylinder etc.. By describing a specific cylinder, head and sector, one specific sector can be addressed.

Modern operating systems and software no longer use CHS addressing. As a result of the limitations of several standards and  specifications (the Int13h and IDE specifications) disks larger than approximately 8 Gb could not be addressed beyond the first 8 Gb. So when using CHS addressing on a 12 Gb hard disk, only the first 8 Gb could be addressed and used. Although CHS addressing is now obsolete, the partition table specification (see below) still reserves room for cylinder/head/sector values and partitions tend to start and end at cylinder boundaries. 

So, how do modern operating systems and other software address a sector? Quite simple, actually: basically they regard a disk as one huge line of sectors starting with the first sector (sector 0) up to the last sector on the disk. This is called Logical Block Addressing, or LBA.

LBA addresses can be converted to CHS addresses and vice versa. In case you ever need to do so you can use the converter that is built into the DiskPatch Disk Editor. Keep in mind that converting LBA to CHS is disk dependant: the CHS geometry of a disk defines where a cylinder stops and the next one starts. So the LBA address 126543 may translate into different CHS values for disks with different geometries.

Interesting fact: DiskPatch does not scan your entire disk when scanning for lost partitions. Partitions that were created using standard disk partitioning software (Fdisk, Windows Disk Management, PartitionMagic etc.) are 'cylinder aligned': they typically start and end on a cylinder boundary. To locate lost partitions, DiskPatch uses this knowledge to reduce the number of sectors that need to be scanned, in order to reduce the time needed. This results in a significantly faster diskscan.

For DiskPatch to be able to calculate the cylinder boundaries, it needs the correct disk geometry (heads per cylinder and sectors per track) information. DiskPatch requires the disk to be configured (in the BIOS) using the same geometry information that was used at the time the disk was partitioned.

If the geometry settings can not be adjusted by using the BIOS you need to make DiskPatch aware of the disk geometry, as it was at the time that the partitions were created.

Specifications

# Partition Table Specification

The partition table is a 64-byte data structure that is used to identify the type and location of partitions on the hard disk drive. The partition table format is not related to any Operating System, it's completely independent. Each partition table entry is 16 bytes long, so there is a maximum of four entries.  Each entry starts at a predetermined offset relative to the start of the sector (we count zero-based, the first byte in a sector is at address 0) :

Entry 1, starts at offset 446 (01BE in Hex)
Entry 2, starts at offset 462 (01CE in Hex)
Entry 3, starts at offset 478 (01DE in Hex)
Entry 4, starts at offset 494 (01EE in Hex)

Note: in Windows 2000/2003/XP only basic disks make use of the partition table. Dynamic disks use the LDM database (located at the end of the disk) for disk configuration information; the partition table is not updated when volumes are deleted or extended after a dynamic disk upgrade, or when new dynamic volumes are created. On a dynamic disk only the first entry of the 'legacy' partition table is used: it describes a type 42 partition occupying the entire disk (the entire disk minus 1 cylinder to be exact).

One Partition Table entry (the first of the four) up close and personal :

The example below is taken from a MBR. The entire underlined area (64 bytes in size) is reserved for defining partitions. Each partition table sector ends with a 55 AA signature! If this signature is missing, the operating system or disk partitioning tools will regard the partition table to be absent.

"80" determines that a partition is the active partition. The red column indicates where '80' can be expected for all partition table entries. However only one partition can be active at a time!

The 'blue' bytes (in the example "0B" and "0F") describe the partition types, in this example a FAT32 partition (0B) and an extended partition (0F). Only one extended partition can be defined in the MBR. An extended partition allocates an area in which logical partitions are located. The first sector of the extended partition contains a partition table that defines the first logical partition (in entry 1) and, if multiple logical partitions are present, a pointer to the next partition table (in entry 2). This first sector of the extended partition is called the EPBR (Extended Partition Boot Record).
The MBR can contain 4 partition table entries. The EPBR can also contain 4 partition table entries, but only the first 2 are used! Entries 3 and 4 are ignored, and thus usually empty.

In the first entry a "0B" type partition is defined. The LBA Relative offset is relative to the partition table it is defined in. The "05" type entry is the pointer to the next partition table, the LBA offset is relative to the start of the extended partition. Like all partition table sectors, the last 2 bytes of the sector contain the 55 AA signature.

Below you can find an example disk layout:

Legend:    = Partition Table sector (the MBR or EPBR) /    = the extended region that contains the logical partitions.
The values that are between parenthesis point to the partition table sector (  ) in which the partition table structures for that partition can be found.

Partition Table Sector  1  describes:

- The primary FAT32 partition 
- The primary NTFS partition
- The Extended partition

The first sector of the extended partition  2  contains a Partition Table Sector. It defines:

- The logical NTFS partition
- The next Partition Table Sector  3 

Partition Table Sector  3  describes:

- the logical FAT32 partition
- and the next Partition Table Sector  4 

Partition Table Sector  4  describes:

- the logical FAT partition

end there the chain ends.

Partition tables form a 'chain'. If the chain is broken at some point, all logical partitions defined later in the chain past the 'breakpoint' can not be accessed.
A Partition Table Sector that points to the next Partition Table Sector should always point forward.

# Boot Sector Specification

The first sector(s) of an individual partition is the boot sector. Although the name boot sector suggests this sector has something to do with booting (which indeed can be the case as the boot sector may contain executable code for booting the operating system), it plays a more important role as the 'mother of the file system structures'. The boot sector contains important information about the partition's size, how it's built up and were the administrative structures are. A damaged boot sector can lead to unexplainable access problems and partitions becoming invisible. A common problem that can be caused by a damaged boot sector is windows asking you 'do you want to format this partition' when you know the partition was in perfect shape during your previous session.
In contrast to the partition table structures, a boot sector IS Operating System dependant: boot sectors for FAT32 partitions are different from boot sectors for NTFS partitions.

The boot sector in the FAT partition

The general layout for a FAT partition is as follows:

The central structure in the FAT file system is the File Allocation Table (FAT). The FAT's position and size can be determined from (are defined by) the boot sector. The data area is divided into clusters. A cluster consists of one or more sectors. For each cluster an entry is kept in the FAT. A cluster can be free, occupied or bad.

The start location of a file or folder is defined in a directory entry. The directory entry for a file/folder contains a filename, attributes (hidden, archive etc.), the start cluster (n) and the size of the file.

To access a file, cluster (n) will be looked up in the FAT. If the file size > 1 cluster, the value in the FAT entry points to the next cluster that was allocated to this file.

Locations of the FAT and the data area are described in the boot sector. Values as they are described in the boot sector are relative to the start of the partition. For example, the position of the first FAT can be derived from the value for 'Reserved Sectors'. Then, once the sectors per FAT and the number of FATs was determined, the start of the Root area follows as: Reserved Sectors + 2*(Sectors Per FAT).

FAT Boot Sector layout:

The data contained in the boot sector after the OEM name string is referred to as the BIOS parameter block or BPB

The Extended BIOS parameter block

The boot sector in the FAT32 partition

The central structure in the FAT32 file system is the File Allocation Table (FAT). The FAT's position and size can be determined from (are defined by) the boot sector. The data area is divided into clusters. A cluster consists of one or more sectors. For each cluster an entry is kept in the FAT. A cluster can be free, occupied or bad. A FAT entry in the FAT32 file system allows for 32 bits (although currently only 28 bits are used).

The start location of a file or folder is defined in a directory entry. The directory entry for a file/folder contains a filename, attributes (hidden, archive etc.), the start cluster (n) and the size of the file.

To access a file, cluster (n) will be looked up in the FAT. If the file size > 1 cluster, the value in the FAT entry points to the next cluster that was allocated to this file.

Locations of the FAT and the data area are described in the boot sector. Values as they are described in the boot sector are relative to the start of the partition. For example, the position of the first FAT can be derived from the value for 'Reserved Sectors'. Then, once the sectors per FAT and the number of FATs was determined, the start of the Data area follows as: Reserved Sectors + 2*(Sectors Per FAT).

FAT32 Boot Sector layout:

The data contained in the boot sector after the OEM name string is referred to as the BIOS parameter block or BPB

The boot sector in the NTFS partition

The central administrative structure in NTFS is the Master File Table (MFT). The NTFS partition is divided into clusters (the entire partition!) and clusters consist of one or more sectors. Cluster sizes can be read from the boot sector. Everything in the NTFS file system is a file, even for example the boot sector ($Boot).

All files are described in the MFT, even the the '$MFT' itself. One or more MFT entries or File record Segments can be assigned to a file. An MFT entry typically describes the filename and the clusters assigned to the file. Assigned clusters are defined in so called 'run-lists': rather than describing each cluster individually, a start cluster value and a number of clusters value is described. For fragmented files multiple run lists are maintained.

NTFS Boot Sector layout: