E format maps

A disc has a section of information, called a map, which controls the allocation of the disc to the files and directories.

An E format disc is divided into a number of zones. A zone is a contiguous section of the disc whose allocation is controled by one sector in the map. If there are nzones zones on a disc, then the map is located at the beginning of zone <nzones/2 rounded down>. The map is nzones sectors long. The first sector controls the lowest numbered sectors on the disc, the second the next sectors and so on. The zones are numbered 0 upwards, so the zone numbers are 0, 1, ..., nzones-2 and nzones-1. Hence, the map will sit at the beginning of the middle zone for discs with an odd number of zones, and the zone higher than the middle for discs with an even number of zones (examples: nzones=7, map is at the start of zone 3, which has 3 zones before it and after it; nzones = 8, map is at the start of zone 4, which has 4 zones before it and 3 after it).

The general format of a zone map block is as follows: <header>
<allocation bytes>
<unused>
The header is different for zone 0 and subsequent zones. The details of these headers will be given later.

The allocation bytes are the section of the map block which controls the allocation of the disc. These bytes are treated as an array of bits with the lsb of a byte comming before the msb of a byte in the array. One bit in the array corresponds with one allocation unit on the disc. The allocation unit is not necessarily one sector, it may be smaller or larger, but it is a power of two bytes. The allocation unit, called bytes_per_map_bit defines the limit of accuracy that the map can define allocation of the disc. The disc can not be split on a boundary which isn't a multiple of the bytes per map bit. The allocation bit array is divided into sections, called fragments, which are the units allocated to various objects (files/directories etc). The allocation unit is stored in the disc record as a log2 value, log2_bytes_per_map_bit.

To translate an allocation bit in the map to a disc address, take the allocation bit's bit offset from the beginning of the bit array (the map with all parts of it which aren't allocation bits removed) and multiply this offset by the bytes per map bit (this multiplication is equivalent to shifting the offset left by log2_bytes_per_map_bit which is why the log2 value is stored). This result is the byte offset across the disc of the beginning of the section of the disc which corresponds to the given map bit. This quantity can be passed to <FS>_DiscOps directly.

The allocation unit may be smaller or larger than a sector size. If it is smaller than a sector size, then only multiples of whole sectors will be allocated. If the allocation unit is larger than one sector, then only multiples of whole allocation units will be allocated. This means that with a sector size of 1024 bytes and a bytes_per_map_bit of 128 bytes, then the smallest increment of disc allocated will be 1024 bytes (a sector), which will still correspond to 8 map bits even though only multiples of 1024 bytes are allocated. If the bytes per map bit is 512 bytes and the sector size 256 bytes, then the smallest increment of disc allocated will be 512 bytes (one map bit's worth of disc space) even though a sector is less than this in size. This smallest quantity actually allocated is called a cluster. A cluster is always a power of two multiple of the allocation unit.

A fragment has the following format in the allocation bytes: <fragment id>
<stream of 0 bits>
<a 1 bit>
The fragment id is a fixed length, in bits, on a disc. This length is called idlen. The use of a fragment determines what the fragment id means. For fragments which are the free space on a disc the fragment id is the offset, in bits, from the beginning of this fragment to the beginning of the next free fragment in the zone. When this is the last free fragment in this zone the offset is 0. Free fragments are chained in this way from the beginning of the zone to the end, never chaining backwards. Hence, the offset is always a positive one, indicating the next free fragment is later in the zone than this one. When a fragment isn't a free fragment, then the fragment id indicates which object this fragment belongs to. Object id 1 is the object which contains all bad blocks and the spare piece of map which hangs over the real end of the disc. Object id 2 is the object which contains the zone map and the root directory. Other object ids indicate files or directories. The following deductions can be made: A fragment can not be shorter than idlen+1 bits, which means that the smallest allocatable unit on a disc is (idlen+1) * (allocation unit), which is the large file allocation unit for that disc; idlen can not be less than log2_sector_size+3, otherwise the link to the next free block would not be guaranteed to reach.

How are free/allocated fragments distinguished? This is easy - if a fragment is in the free chain (as started by the field in the zone map's header), then it's free, otherwise it's allocated.

Given the method of disc allocation, it becomes clear that there is a maximum number of object ids available on a given disc. The maximum number of ids which can be fitted into a given zone is (allocation_bits)/(minimum fragment length, in bits) rounded down. Choosing the zone with the largest number of allocation_bits (ie any zone other than zone 0) gives the quantity ids_per_zone. An object may have a number of fragments allocated to it in several zones. These fragments must be logical joined together in some way to make the object appear as a contiguous sequence of bytes. The naive approach would be to have the first fragment of the disc be the first fragment of the object. ADFS E format discs do not do this. The first fragment in an object is the first fragment on the disc searching from zone (object_id/ids_per_zone) upwards, then starting the search at the start of the disc. The fragments are then joined in this order. Here is an example:

This table numbers the fragments which make up a given object in the order in which they occur in the object. The object's id is 690, the log2_sector_size is 8 (256 byte sectors), and the idlen is 11 (large file allocation unit is 12*bytes_per_map_bit). This means that id_per_zone is 168 (= (256*8 - 4*8)/12 = (sector_size*bits_per_byte - header_size*bits_per_byte)/(idlen+1)). This means that the starting zone for object 690 is zone 4 (= 690/168 = object_id/ids_per_zone).

Zone    Fragments in zone       Position of fragments in object
0       3                       3
                                4
                                5

1       0

2       1                       6

3       1                       7

4       2                       0
                                1

5       0

6       1                       2

7       0

This object has 8 fragments, identified as belonging to this object by having a fragment id of 690. The are ordered in the object as follows:

Position of fragment in object Zone the fragment's in

0                               4
1                               4
2                               6
3                               0
4                               0
5                               0
6                               2
7                               3

Object 2, being the object which carries the map with it, is special. It is always at the beginning of the middle zone, as opposed to being at the beginning of zone 0.

A standard map block header is as follows:

Offset  Name            Meaning
0       ZoneCheck       Check byte for this zone map block
1       FreeLink        Link to first free fragment in this zone
3-3     CrossCheck      Cross check byte for complete map

ZoneCheck is used to check that this zone is valid. CrossChecks are combined to check that the whole map is self-consistent.

The zone 0 map header is structured as follows:

Offset  Name            Meaning
0       ZoneCheck       Check byte for this zone map block
1       FreeLink        Link to first free fragment in this zone
3       CrossCheck      Cross check byte for complete map
4       DiscRec         Copy of disc record for this disc

This means that the total header part of zone 0's map is 64 bytes long.

The FreeLink is treated as a standard fragment, and so, the maximum idlen is 15 bits. This places limits on the large file allocation unit - the large file allocation unit can not be larger than 16*bytes per map bit, and the large file allocation unit can not be so small as to require more than 15 bits to represent all the object ids possible (ids_per_zone*nzones).

The unused section of a map block is determined by zone_spare. The given zone ends at zone_spare bits before the 1st allocation bit in the next zone. In other words, zone_spare gives the size of the hole, in bits, between the last allocation in a map block and the first allocation bit in the next map block. For the purposes of calculating ids_per_zone the maximum number of allocation bits in a zone is
end bit of zone - start bit of zone
or
((sector_size + standard_header_size)*8 - zone_spare) - standard_header_size*8 which reduces to
sector_size*8 - zone_spare

Various values are refered to in the description above. These come from the disc record, which is outlined in the PRM, and labeled here:

Offset  Name            Meaning
0       log2secsize     log base 2 of the sector size of this disc.
1       secspertrack    Number of sectors per track
2       heads           Number of disc heads (1 for old directories)
3       density         0-hard disc, 1-256 bytes per sector, 2-512 bytes per sector, 3-1024 bytes per sector
4       idlen           Length of id field of a map fragment
5       log2bpmb        Log base 2 of the number of bytes per map bit
6       skew            track to track sector skew for random access file allocation
7       bootoption      boot option
8       reserved
9       nzones          Number of zones in the map
10      zone_spare      Number of non-allocation bits between zones
12      root            Disc address of root directory
16      disc_size       Disc size in bytes
20      disc_id         Disc cycle id
22      disc_name       Disc name

Calculating CrossCheck:
These bytes provide a means to check that the set of zones match each other. To check the set matches, these bytes are exclusive-ored (EOR) with each other and the answer must be &FF (0xff). They are modified whenever more than one zone map is modified (the algorithm is not important, just so long as the bytes of the changed maps change and that the EOR of all these bytes remains at &FF).

Calculating ZoneCheck:
This, as described previously, is a check byte on a given zone sector. It's calculation is best described in assembler, but I have also coded one up in C. Here are both those code fragments:

unsigned char map_zone_valid_byte
(

        void const * const map,
        disc_record const * const discrec,
        unsigned int zone

        unsigned char const * const map_base = map;
        unsigned int sum_vector0;
        unsigned int sum_vector1;
        unsigned int sum_vector2;
        unsigned int sum_vector3;
        unsigned int zone_start;
        unsigned int rover;

        sum_vector0 = 0;
        sum_vector1 = 0;
        sum_vector2 = 0;
        sum_vector3 = 0;

        zone_start = zone<<discrec->log2_sector_size;
        for ( rover = ((zone+1)<<discrec->log2_sector_size)-4; rover > zone_start; rover-=4 )
        {
                sum_vector0 += map_base[rover+0] + (sum_vector3>>8);
                sum_vector3 &= 0xff;
                sum_vector1 += map_base[rover+1] + (sum_vector0>>8);
                sum_vector0 &= 0xff;
                sum_vector2 += map_base[rover+2] + (sum_vector1>>8);
                sum_vector1 &= 0xff;
                sum_vector3 += map_base[rover+3] + (sum_vector2>>8);
                sum_vector2 &= 0xff;
        }

        /*
                Don't add the check byte when calculating its value
        */
        sum_vector0 +=                     (sum_vector3>>8);
        sum_vector1 += map_base[rover+1] + (sum_vector0>>8);
        sum_vector2 += map_base[rover+2] + (sum_vector1>>8);
        sum_vector3 += map_base[rover+3] + (sum_vector2>>8);

        return (unsigned char)((sum_vector0^sum_vector1^sum_vector2^sum_vector3) & 0xff);

; ========
; NewCheck
; ========

;entry
; R0 -> start
; R1 length ( must be multiple of 32 )

;exit
; LR check byte, Z=0 <=> good

NewCheck ROUT
Push "R1-R9,LR"
MOV LR, #0

 ADDS   R1, R1, R0              ;C=0
05                              ;loop optimised as winnies may have many zones

 TEQS   R1, R0          ;preserves C