*** Disk File Layout (D64, D71, D81) *** Document revision: 1.3 *** Last updated: March 11, 2004 *** Compiler/Editor: Peter Schepers *** Source: Joe Forster/STA (internal rev 0.10) Introduction ------------ This document describes how Commodore drives lay out files when saving them onto the disk. It does not describe how the Commodore disk or the BAM is laid out or how you can manage it, you can read that in another document. The description also covers GEOS, which uses its own layout scheme for saving files onto disks. Note that Commodore 1541, 1571 and 1581 drives all use the same scheme, but with different parameters. The Pascal source below was verified against real disks written by real drives and proved to lay out files exactly the same way as Commodore drives and GEOS do. It has been translated into C, as well. These algorithms may be too complicated for your particular needs because they take so many parameters into account. Feel free to strip off whatever you don't need. Please, note that, while the algorithms simulate the real behavior exactly, the reason for this behavior is not always fully known. As you will find below, sometimes we can only assume the reason. If you think these assumptions are incorrect then, please, tell us. We'll be more than happy to discuss and, possibly, include it. Finding the first block ----------------------- Commodore drives, as most floppy drives, have a relatively slow head movement. To speed up data access, it's certainly a good idea to put the directory into the center of the disk so that, when moving the head from the directory area to the actual file data and back, head movement is minimized. On Commodore disks, the directory is on the central track: this is track 18 on 1541 disks, track 18 and track 53 (the flip side of track 18) on double-sided 1571 disks, and track 40 on 1581 disks. When trying to find a free sector for the first block of the file, the drive first searches on the track just "below" the directory track, then the track just "above" the directory track, then 2 below, 2 above, etc., moving away from the directory track. This assures that the first block of the file will be as close to the directory track as possible. Again, this minimizes head movement. When a track is found, that contains one or more free sectors, then the drive simply grabs the first free sector on that track, starting with sector zero and going upwards, and allocates it for the first block of the file. If there are no free sectors left then you get the '72,DISK FULL,00,00' error message. If a track is found, whose "number of free sectors" counter in the BAM is not zero, but the sector allocation bitmap shows no free sectors then the BAM is damaged. It is highly recommended that you check the BAM prior to saving files onto the disk, and refuse to do anything if you find such inconsistensies. The BAM should be repaired, for example with a validate, first. Finding the next block ---------------------- There's another algorithm for finding successive sectors for the file. It is executed each time whenever a new sector is needed to hold file data. The algorithm makes use of an interesting parameter, the "interleave". Because transferring data to the host machine is so slow, the drive shouldn't lay out data of the same file sequentially onto sectors of the same track. If it wrote the first block of data onto sector zero and then second block onto sector one etc. then, while it is sending data read from sector zero to the host machine, the disk would keep spinning and sector one would leave the read/write head. As soon as the data transmission ends, the drive would try to read sector one, to get the next block of data, and it would find that it has to wait about half a revolution for sector one to appear again under the read/write head. Therefore, data shouldn't be laid out sequentially but, rather, there should be "holes" between successive blocks of the same file. Of course, this doesn't mean holes with no data inside. It only means that data is laid out e.g. onto each even sector: sector zero, then sector two, four etc. Then the drive will have time, while sector one, three and five is under the read/write head, to send the contents of sector zero, two and four to the host machine. When the end of the track is reached, you start again with odd sectors - after all, a track is an endless circle - and fill in the holes you made by using every second sector only. The distance of successive blocks is what we call "interleave". On some disks, physical sectors are laid out in a non-sequential manner, that's a "hard" interleave. Commodore drives do lay out physical sectors in a sequential manner but they put data onto them in a non-sequential order, that's a "soft" interleave. In the example above, we were using a soft interleave of two, that is, the distance between two successive blocks of the same file was two sectors. The optimal interleave for a disk highly depends on how fast data can be transmitted to the host machine. For a high transmission rate, the interleave can be smaller because not much time is needed to transfer the contents of the current sector, therefore successive sectors may be closer to each other. For a low transmission rate, such as the default of Commodore drives, a higher interleave is needed. In particular, 1541 drives are using an interleave of 10 sectors, 1571 drives use 6 sectors and 1581 drives use 1 sector, by default. The reason for the latter is that 1581 drives contain a track cache, they can read in a whole track of data and then transmit data right from the memory to the host machine, without having to actually access the disk. In this case, there's no real need for an interleave, sectors may be laid out in a sequential manner - which corresponds with an interleave value of one - without any possible performance penalty. So, when the drive finished writing the current block of a file and there still are free sectors left on the current track, it tries to continue with the sector that is an "interleave" number of sectors away from the current one. It adds the interleave to the current sector number. If it runs off the current track - the sector number becomes invalid - then it subtracts the number of sectors on the track, which will correct the result. If the corrected result is not sector zero then it subtracts one more. This is, most probably, some kind of an empirical optimization, because the gap between the last and first sector on a track is always a bit longer than the other gaps. If the sector, the drive arrived at this way, is free then it already has the sector it needs. If it's used, however, then the drive keeps searching for free sectors, starting from this sector, at steps of one. It searches towards the end of the track, then wraps back to sector zero and moves further upwards. As the BAM stated that there are still free sectors on the current track, it shouldn't arrive back at the sector it started from. If it does then the BAM is damaged. If the current track is already full then the drive moves one track away from the directory track but keeps the sector number used on the previous track. If there are some free sectors on this new track then the drive tries to find a free sector, using the method described in the previous paragraphs, including adding the interleave to the sector number first. The reason for this, most probably, is that sectors of the same sector number are at about the same angle on all tracks. Therefore, when you finished writing sector zero on a track and move to an adjacent track then you'll, probably, read sector one as the first sector that arrives under the read/write head on that track. This means, you can keep adding the interleave, as if you were still on the same track. If, while moving away from the directory track, the algorithm runs off the disk, it tries again on the other half of the disk. If it stepped off track one downwards then it tries again with the track just above the directory track, going upwards. If it stepped off the highest track upwards then it tries again with the track just below the directory track, going downwards. Therefore, at least, two tries should be made: on the current half of the disk and the other half. For some unknown reason, Commodore 1541 drives do three tries, which the algorithm below follows. When jumping to the other half of the disk, the sector number is zeroed. The reason for this, probably, is that moving the read/write head to such a great distance takes away so much time that there's no telling which sector it will read first, arriving at the destination track, so there's no point keeping the previous sector number. An extra feature of the algorithms below is that you can also save file data onto free sectors of the directory track. The directory track will be used only if all other parts of the disk are completely full. Apart from this, everything above applies to the directory track, as well. It's worth mentioning that this "finding the next block" algorithm is used also for finding the next block for the directory, when extending it. The only difference is that, in this case, a lower interleave of 3 sectors is used by 1541 and 1571 drives, by default, because no data transmission to the host machine is involved while processing the directory data. 1581 drives, as usual, use an interleave of 1 sector. --------------------------------------------------------------------------- GEOS ---- GEOS works quite differently from the original drive DOS. It starts saving files on track one and goes upwards until it fills up the last track. On its way, of course, it skips the directory tracks. Actually, it uses the same algorithm for finding the first and the next sectors for a file and even for extending the directory, too. Because it has a built-in fast loader, it uses an interleave different from the original: 8 sectors for 1541 disks. As tests show, it uses the original interleave of 6 sectors for 1571 disks and 1 sector for 1581 disks, perhaps, because these drives are fast enough anyway. The same applies for extending the directory which is, again, handled by the same algorithm, probably, because directory data has to be transferred to the host machine as it is processed by the GEOS disk driver rather than the drive itself. GEOS also introduces some kind of a "sector skewing". Unlike on normal Commodore disks, sectors of the same sector number but on different tracks are not at the same angle on the disk. As you move away from a certain track, sector zero also slides away in one direction. The distance, measured by the difference in the sector number, of sectors at about the same angle on adjacent tracks is the "skew" value. Again, if this applies to physical sectors than that's a "hard" skew. For logical sectors - successive blocks of the same file -, that's a "soft" skew. The skew value used by GEOS is computed by a relatively complicated formula: "track distance" * 2 + 4 + "interleave". When stepping onto a new track, GEOS tries to save the next block of file data onto the sector whose sector number is equal to the result of the above formula. (Strangely enough, the result is not added to the sector number but rather assigned to, so it might not be a sector skew, after all.) If this sector is already used then, similarly to the original drive DOS, GEOS goes through the track sequentially, at steps of one, and searches for the first free sector after this one. --------------------------------------------------------------------------- Pascal source ------------- {=== Start of Pascal source ==============================================} {--- Global variables ---} var {When True, this is a GEOS-formatted disk, therefore, files have to be saved the GEOS way onto it} GEOSFormat, {When True, free sectors on the directory track are also allowed to hold file data if the disk otherwise gets full} CopyToDirTrack: Boolean; {Track number of current block of file} Track, {Sector number of current block of file} Sector, {Track number of first track (may be above one for subdirectories on 1581 disks)} FirstTrack, {Track number of last track plus one (may be below the physical end of disk for subdirectories on 1581 disks)} LastTrack, {Track number of physically last track plus one} MaxTrack, {Track number of directory track} DirTrack, {Track number of secondary directory track (for 1571 disks); 255 (a non-existent track), if not available} DirTrack2, {Soft interleave} Interleave: Byte; {--- Support routines ---} {Determine if there's, at least, one free sector on a track Input : Track: the track to check Output: when True, there's, at least, one free sector on the track} function IsTrackFree(Track: Byte): Boolean; {Determine if a sector is free Input : Track: the track number of sector to check Sector: the sector number of sector to check Output: when True, the sector is free; otherwise used} function IsSectorFree(Track, Sector: Byte): Boolean; {Determine the number of sectors (or the highest valid sector number plus one) for a track Input : Track: track number Output: the number of sectors on the track} function SectorNum(Track: Byte): Byte; {--- Implementation of algorithms ---} {Prototype for NextCopyBlock} function NextCopyBlock: Boolean; {Find a sector for the first block of the file, using variables Track and Sector Output: when True, a sector was found; otherwise no more sectors left} function FirstCopyBlock: Boolean; var Found: Boolean; MaxSector, Distance: Byte; begin {We found no free sector yet} Found := False; {If this is a GEOS-formatted disk then use the other routine, from track one upwards} if GEOSFormat then begin Track := 1; Sector := 0; Found := NextCopyBlock; end else begin {If it's a normal disk then we start off with tracks just besides the directory track} Distance := 1; {Search until we find a free block or moved too far from the directory track} while not Found and (Distance < 128) do begin {Check the track below the directory track first} Track := DirTrack - Distance; {If the track is inside the valid range then check if there's a free sector on it} if (Track >= FirstTrack) and (Track < LastTrack) then Found := IsTrackFree(Track); if not Found then begin {If no luck then check the track above the directory track} Track := DirTrack + Distance; {If the track is inside the valid range then check if there's a free sector on it} if Track < LastTrack then Found := IsTrackFree(Track); end; {If no luck either then move one track away from the directory track and try again} if not Found then Inc(Distance); end; {If the whole disk is full and we're allowed to use the directory track for file data then try there, too} if not Found and CopyToDirTrack then begin Track := DirTrack; Found := IsTrackFree(Track); end; {If we finally found a track with, at least, one free sector then search for a free sector in it} if Found then begin {Determine how many sectors there are on that track} MaxSector := SectorNum(Track); {Start off with sector zero} Sector := 0; repeat {Check if the current sector is free} Found := IsSectorFree(Track, Sector); {If it isn't then go on to the next sector} if not Found then Inc(Sector); {Repeat the check until we find a free sector or run off the track} until Found or (Sector >= MaxSector); end; end; {Return the search result} FirstCopyBlock := Found; end; {-------------------------------------------------------------------------} {Find a sector for the next block of the file, using variables Track and Sector Output: when True, a sector was found; otherwise no more sectors left} function NextCopyBlock: Boolean; var Found: Boolean; Tries, MaxSector, CurSector, CurTrack: Byte; begin if (Track = 0) or (Track >= MaxTrack) then begin {If we somehow already ran off the disk then there are no more free sectors left} NextCopyBlock := False; end else begin {Set the number of tries to three} Tries := 3; {We found no free sector yet} Found := False; {Remember the current track number} CurTrack := Track; {Keep trying until we find a free sector or run out of tries} while not Found and (Tries > 0) do begin {Get the number of sectors on the current track} MaxSector := SectorNum(Track); {If there's, at least, one free sector on the track then get searching} if IsTrackFree(Track) then begin {If this is a non-GEOS disk or we're still on the same track of a GEOS-formatted disk then...} if (Track = CurTrack) or not GEOSFormat then begin {Move away an "interleave" number of sectors} Inc(Sector, Interleave); {Empirical GEOS optimization, get one sector backwards if over track 25} if GEOSFormat and (Track >= 25) then Dec(Sector); end else begin {For a different track of a GEOS-formatted disk, use sector skew} Sector := (Track - CurTrack) shl 1 + 4 + Interleave; end; {If we ran off the track then correct the result} while Sector >= MaxSector do begin {Subtract the number of sectors on the track} Dec(Sector, MaxSector); {Empirical optimization, get one sector backwards if beyond sector zero} if (Sector > 0) and not GEOSFormat then Dec(Sector); end; {Remember the sector we finally arrived at} CurSector := Sector; repeat {Check if the current sector is free} Found := IsSectorFree(Track, Sector); {If it isn't then go to the next sector} if not Found then Inc(Sector); {If we ran off the track then wrap around to sector zero} if Sector >= MaxSector then Sector := 0; {Keep searching until we find a free sector or arrive back at the original sector} until Found or (Sector = CurSector); end else begin {If the current track is used up completely then...} if GEOSFormat then begin {Move one track upwards on a GEOS-formatted disk} Inc(Track); {Skip the directory tracks on the way} if (Track = DirTrack) or (Track = DirTrack2) then Inc(Track); {If we ran off the disk then there are no more tries} if Track = LastTrack then Tries := 0; end else begin {If we already tried the directory track then there are no more tries} if Track = DirTrack then begin Tries := 0; end else begin if Track < DirTrack then begin {If we're below the directory track then move one track downwards} Dec(Track); if Track < FirstTrack then begin {If we ran off the disk then step back to the track just above the directory track and zero the sector number} Track := DirTrack + 1; Sector := 0; {If there are no tracks available above the directory track then there are no tries left; otherwise just decrease the number of tries} if Track < LastTrack then Dec(Tries) else Tries := 0; end; end else begin {If we're above the directory track then move one track upwards} Inc(Track); {Skip the secondary directory track on the way} if Track = DirTrack2 then Inc(Track); if Track = LastTrack then begin {If we ran off the disk then step back to the track just below the directory track and zero the sector number} Track := DirTrack - 1; Sector := 0; {If there are no tracks available below the directory track then there are no tries left; otherwise just decrease the number of tries} if Track >= FirstTrack then Dec(Tries) else Tries := 0; end; end; end; end; end; if not Found and (Tries = 0) and (Track <> DirTrack) and CopyToDirTrack then begin {If we haven't found any free sector, ran out of tries and haven't tried the directory track yet, although it's declared as available for file data, then give the directory track an extra try} Track := DirTrack; Inc(Tries); end; end; {Return the search result} NextCopyBlock := Found; end; end; {=== End of Pascal source ================================================} --------------------------------------------------------------------------- C source -------- /* === Start of C source =============================================== */ /* Type definitions */ #define byte unsigned char #define boolean unsigned char #define true (0 == 0) #define false (0 == 1) /* --- Global variables --- */ boolean /* When true, this is a GEOS-formatted disk, therefore, files have to be saved the GEOS way onto it */ GEOSFormat, /* When true, free sectors on the directory track are also allowed to hold file data if the disk otherwise gets full */ CopyToDirTrack; byte /* Track number of current block of file */ Track, /* Sector number of current block of file */ Sector, /* Track number of first track (may be above one for subdirectories on 1581 disks) */ FirstTrack, /* Track number of last track plus one (may be below the physical end of disk for subdirectories on 1581 disks) */ LastTrack, /* Track number of physically last track plus one */ MaxTrack, /* Track number of directory track */ DirTrack, /* Track number of secondary directory track (for 1571 disks); 255 (a non-existent track), if not available */ DirTrack2, /* Soft interleave */ Interleave; /* --- Support routines --- */ /* Determine if there's, at least, one free sector on a track Input : Track: the track to check Output: when true, there's, at least, one free sector on the track */ boolean IsTrackFree(byte Track); /* Determine if a sector is free Input : Track: the track number of sector to check Sector: the sector number of sector to check Output: when true, the sector is free; otherwise used */ boolean IsSectorFree(byte Track, byte Sector); /* Determine the number of sectors (or the highest valid sector number plus one) for a track Input : Track: track number Output: the number of sectors on the track */ byte SectorNum(byte Track); /* --- Implementation of algorithms --- */ /* Prototype for NextCopyBlock() */ boolean NextCopyBlock(); /* Find a sector for the first block of the file, using variables Track and Sector Output: when true, a sector was found; otherwise no more sectors left */ boolean FirstCopyBlock() { boolean Found; byte MaxSector, Distance; /* We found no free sector yet */ Found = false; /* If this is a GEOS-formatted disk then use the other routine, from track one upwards */ if (GEOSFormat) { Track = 1; Sector = 0; Found = NextCopyBlock(); } else { /* If it's a normal disk then we start off with tracks just besides the directory track */ Distance = 1; /* Search until we find a free block or moved too far from the directory track */ while (!Found && (Distance < 128)) { /* Check the track below the directory track first */ Track = DirTrack - Distance; /* If the track is inside the valid range then check if there's a free sector on it */ if ((Track >= FirstTrack) && (Track < LastTrack)) Found = IsTrackFree(Track); if (!Found) { /* If no luck then check the track above the directory track */ Track = DirTrack + Distance; /* If the track is inside the valid range then check if there's a free sector on it */ if (Track < LastTrack) Found = IsTrackFree(Track); } /* If no luck either then move one track away from the directory track and try again */ if (!Found) Distance++; } /* If the whole disk is full and we're allowed to use the directory track for file data then try there, too */ if (!Found && CopyToDirTrack) { Track = DirTrack; Found = IsTrackFree(Track); } /* If we finally found a track with, at least, one free sector then search for a free sector in it */ if (Found) { /* Determine how many sectors there are on that track */ MaxSector = SectorNum(Track); /* Start off with sector zero */ Sector = 0; do { /* Check if the current sector is free */ Found = IsSectorFree(Track, Sector); /* If it isn't then go on to the next sector */ if (!Found) Sector++; /* Repeat the check until we find a free sector or run off the track */ } while (!Found && (Sector < MaxSector)); } } /* Return the search result */ return(Found); } /* --------------------------------------------------------------------- */ /* Find a sector for the next block of the file, using variables Track and Sector Output: when true, a sector was found; otherwise no more sectors left */ boolean NextCopyBlock() { boolean Found; byte Tries, MaxSector, CurSector, CurTrack; if ((Track == 0) || (Track >= MaxTrack)) { /* If we somehow already ran off the disk then there are no more free sectors left */ return(false); } else { /* Set the number of tries to three */ Tries = 3; /* We found no free sector yet */ Found = false; /* Remember the current track number */ CurTrack = Track; /* Keep trying until we find a free sector or run out of tries */ while (!Found && (Tries > 0)) { /* Get the number of sectors on the current track */ MaxSector = SectorNum(Track); /* If there's, at least, one free sector on the track then get searching */ if (IsTrackFree(Track)) { /* If this is a non-GEOS disk or we're still on the same track of a GEOS-formatted disk then... */ if ((Track == CurTrack) || !GEOSFormat) { /* Move away an "interleave" number of sectors */ Sector += Interleave; /* Empirical GEOS optimization, get one sector backwards if over track 25 */ if (GEOSFormat && (Track >= 25)) Sector--; } else { /* For a different track of a GEOS-formatted disk, use sector skew */ Sector = ((Track - CurTrack) << 1) + 4 + Interleave; } /* If we ran off the track then correct the result */ while (Sector >= MaxSector) { /* Subtract the number of sectors on the track */ Sector -= MaxSector; /* Empirical optimization, get one sector backwards if beyond sector zero */ if ((Sector > 0) && !GEOSFormat) Sector--; } /* Remember the sector we finally arrived at */ CurSector = Sector; do { /* Check if the current sector is free */ Found = IsSectorFree(Track, Sector); /* If it isn't then go to the next sector */ if (!Found) Sector++; /* If we ran off the track then wrap around to sector zero */ if (Sector >= MaxSector) Sector = 0; /* Keep searching until we find a free sector or arrive back at the original sector */ } while (!Found && (Sector != CurSector)); } else { /* If the current track is used up completely then... */ if (GEOSFormat) { /* Move one track upwards on a GEOS-formatted disk */ Track++; /* Skip the directory tracks on the way */ if ((Track == DirTrack) || (Track == DirTrack2)) Track++; /* If we ran off the disk then there are no more tries */ if (Track == LastTrack) Tries = 0; } else { /* If we already tried the directory track then there are no more tries */ if (Track == DirTrack) { Tries = 0; } else { if (Track < DirTrack) { /* If we're below the directory track then move one track downwards */ Track--; if (Track < FirstTrack) { /* If we ran off the disk then step back to the track just above the directory track and zero the sector number */ Track = DirTrack + 1; Sector = 0; /* If there are no tracks available above the directory track then there are no tries left; otherwise just decrease the number of tries */ if (Track < LastTrack) Tries--; else Tries = 0; } } else { /* If we're above the directory track then move one track upwards */ Track++; /* Skip the secondary directory track on the way */ if (Track == DirTrack2) Track++; if (Track == LastTrack) { /* If we ran off the disk then step back to the track just below the directory track and zero the sector number */ Track = DirTrack - 1; Sector = 0; /* If there are no tracks available below the directory track then there are no tries left; otherwise just decrease the number of tries */ if (Track >= FirstTrack) Tries--; else Tries = 0; } } } } } if (!Found && (Tries == 0) && (Track != DirTrack) && CopyToDirTrack) { /* If we haven't found any free sector, ran out of tries and haven't tried the directory track yet, although it's declared as available for file data, then give the directory track an extra try */ Track = DirTrack; Tries++; } } /* Return the search result */ return(Found); } } /* === End of C source ================================================= */ History: 2000-05-05 0.01 Initial internal release 2000-05-08 0.02 New: Translated the Pascal source to C New: Separated text into numbered sections Mod: Changed wording to make it more understandable 2000-06-29 0.03 Fix: Fixed a couple of typos 2000-07-28 0.04 Mod: Changed some wording again 2000-11-05 0.05 Fix: Fixed some syntactical errors in the C source 2001-02-22 0.10 Fix: Fixed some typos Fix: Bytes, booleans are unsigned chars in C source