    dim version$/"SDOS REHASHDIRECTORY v1.0c (C) 1984 Software Dynamics"/
!   REHASHDIRECTORY
!   Program to expand/shrink DIRECTORY.SYS and optimize directory entry
!   placement to minimize lookup times.  Also inserts "Never-before-used"
!   entries in directory to minimize "can't find file" times.
!
!   Revision History:
!       v1.0  2/1/85    Expand and reorganize directory only.
!       v1.0b 2/10/85   Add Shrink directory.
!                       Fix "can't handle directory with > 65535 bytes" bug
!       v1.0c 3/22/85   Fix "Shrink directory, then create enough files
!                       to expand it again, causes 'No such file' when
!                       opening known-to-exist files" bug.
!                       Fix "SDOS expands directory extended in the past by
!                       REHASHDIR, and suddenly garbage files appear".
    dim device$[50],temp$(50)
    dim LCN$(2),DummyLCN$/:FF,:FF/,Boot$(64),Byte$(1)
    dim DirectoryEntry$[32],DirectoryEntry2$[32]
    dim CCSetFileProtection$/:E,8,0,:11/
    dim WriteBackupProtect$/:41/,NoProtection$/0/
    dim CCSetFileSize$/:E,4,0,:12/
    dim CCSetMapAlgorithm$/:E,8,0,:12/
    dim CCDismount$/:E,4,0,:11/
    dim CCUnlockDisk$/:E,4,1,:10/
    dim SCGetFileSize$/:F,14,0,:3/
    dim SCGetParams$/:F,14,0,:5/
    dim DirectorySys$/"DIRECTORY.SYS   "/
    dim NeverUsedDirectoryEntry$/:FF,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,...
&                                0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0/
    ! Sign bit set on 1st byte of directory entry --> slot never used

    dim PreviouslyUsedDirectoryEntry$/0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,...
&                                0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0/

!^L
Def MSB(MSBarg)=int(MSBarg/256)

Def LSB(LSBarg)=LSBarg-MSB(LSBarg)*256

Def LogicalFilePosition(LogicalFilePositionArg)
! FileDirectoryEntry$[1,32] must contain directory entry for file on device.
! FileNLCN must contain number of LCNs for file.
! FileHCSIC must hold Header Cluster Sector Initialized count.
! FileHLCN must hold Logical Cluster Number.
! NBPS must hold number of bytes per sector for device.
! NSPC must hold Number Of Sectors per cluster for device.
! FileHeaderPosition must hold FileHLCN*ClusterSize
! Computes offset into disk device for logical file position specified.
! This effectively duplicates what SDOS does when it maps a logical file
! position to a Logical Sector Number.
! For this implementation, it is not legal to position past end of the file.
! On exit:
!   LogicalSectorNumber holds LSN of file position
!   ByteOffset holds offset into sector.
! Returns Byte offset from start of device to desired logical byte.
!
    ByteOffset=LogicalFilePositionArg-int(LogicalFilePositionArg/NBPS)*NBPS
    FileOffsetInSectors=(LogicalFilePositionArg-ByteOffset)/NBPS
    RelativeClusterNumber=int( FileOffsetInSectors/NSPC )
    RelativeSectorWithinCluster=FileOffsetInSectors-RelativeClusterNumber*NSPC
    If FileHCSIC*(NBPS/2)-2<RelativeClusterNumber
    Then Error 1001 \ ! End of file hit
    !D! Print "FileOffsetInSectors=";FileOffsetInSectors;...
!&         "RelativeClusterNumber";RelativeClusterNumber;...
!&         "RelativeSectorWithinCluster";RelativeSectorWithinCluster
    Read #1@FileHeaderPosition+2*(RelativeClusterNumber+1),LCN$
    LogicalClusterNumber=LCN$[1]**8+LCN$[2]
!D! Print "Logical Cluster Number containing RelativeCluster";...
!&         hex$(LogicalClusterNumber)
    If LogicalClusterNumber=:FFFF
    Then Error 1004 \ ! Bad file position
    LogicalSectorNumber=LogicalClusterNumber*NSPC+RelativeSectorWithinCluster
!D! Print "inspecting LSN";LogicalSectorNumber;"+";ByteOffset
    Return LogicalSectorNumber*NBPS+ByteOffset
End

Def HashName(HashName$)
    ! Computes same function as HashName subroutine in SDOS proper
    ! Compute 24 bit hash code from DirectoryEntry name
    HashCode=0
    For i=13 to 1 step -4
        sum=0\For j=0 to 3 do sum=sum+HashName$[i+j]
        sum=sum&:3F \ ! mask off zone bits
        HashCode=HashCode*64+Sum
    Next i
    i=int(HashCode/NumberOfSectorsInDirectory)
    Return NBPS*(HashCode-i*NumberOfSectorsInDirectory)
End

Def Distance(DesiredPosition,ProposedPosition)
! Returns value proportional to time it takes to search DIRECTORY.SYS...
! from DesiredPosition (i.e., where Hash function specifies the start of
! the search) to ProposedPosition
    If ProposedPosition>=DesiredPosition
    Then
        ! Distance is time to read forward thru directory from search...
        ! start to ProposedPosition
        Return ProposedPosition-DesiredPosition
    Else
        ! Distance is time to read forward thru directory from search...
        ! start to end of directory, and then to read from directory
        ! start forward to ProposedPosition
        Return (DirectorySizeInBytes-DesiredPosition)+ProposedPosition
    Fi
End
!^L
Subroutine DisplayHashStatistics
! Display Hashing statistics about directory and print them out.
    TotalDirectorySlots=DirectorySizeInBytes/32
    NeverUsedDirectoryEntries=0
    RealDirectoryEntries=0
    IncorrectlyHashedDirectoryEntries=0
    TotalLookupTime=0 \ ! Amount of time to look up files

    Position #1,0 \ ! Start scanning DIRECTORY.SYS from the beginning
    For DirectoryScanPointer=0 to DirectorySizeInBytes-1 step 32
        Read #1,DirectoryEntry$
        If DirectoryEntry$[1]=:FF
        Then NeverUsedDirectoryEntries=NeverUsedDirectoryEntries+1
        ElseIf DirectoryEntry$[19]>0
        Then
            If DirectoryEntry$[1,16]=DirectorySys$
            Then
                ! Capture/compute parameters needed to re-hash DIRECTORY.SYS
                FileNLCN=DirectoryEntry$[20]**8+DirectoryEntry$[21]
                FileHCSIC=DirectoryEntry$[19]
                FileHLCN=DirectoryEntry$[17]**8+DirectoryEntry$[18]
                FileHeaderPosition=FileHLCN*NSPC*NBPS
                FileDirectoryOffset=DirectoryScanPointer
            Fi
            RealDirectoryEntries=RealDirectoryEntries+1
!D!         Print DirectoryEntry$[1,16];NClusters,
            DesiredDirectoryPosition=HashName(DirectoryEntry$)
!D!         Print HashCode,DesiredDirectoryPosition,DirectoryScanPointer
            If DesiredDirectoryPosition>DirectoryScanPointer or...
&              DesiredDirectoryPosition+NBPS<=DirectoryScanPointer
            Then
                IncorrectlyHashedDirectoryEntries=...
&                 IncorrectlyHashedDirectoryEntries+1
            Fi
            TotalLookupTime=TotalLookupTime+...
&              Distance(DesiredDirectoryPosition,DirectoryScanPointer)
        Fi
    End
    Print TotalDirectorySlots;"directory slots."
    Print RealDirectoryEntries;"files actually present."
    FreeSlotRatio=(TotalDirectorySlots-RealDirectoryEntries)/...
&                 TotalDirectorySlots
    Print FreeSlotRatio*100;"% directory slots free."
    Print NeverUsedDirectoryEntries;"never-used entries"
    Print IncorrectlyHashedDirectoryEntries;...
&         "files not optimally placed for lookup."
    Print 1+(TotalLookupTime/NBPS)/RealDirectoryEntries;...
&         "sector reads is average lookup time."
    Print
    Print "Free directory slots should be >=20% for good performance."
    Print "Also, number of sector reads for average lookup time should be <2."
    Print
    Return Subroutine
End
!^L
Subroutine RelocateDirectoryEntry
! Relocates DIRECTORYENTRY$ desired at DesiredDirectoryPosition offset
! into DIRECTORY.SYS to offset NewDirectoryPosition into DIRECTORY.SYS.
! This relocation process may displace another directory entry, which
! in turn will have to be relocated.  The process repeats until no
! directory entry is displaced (i.e., the last one is placed into an
! empty slot, which is always gauranteed to exist).
!
    Repeat
600     ! Now relocate directory entry to proper place
!D!     Print "Trying to relocate ";DirectoryEntry$[1,16];...
!&             " desired at";DesiredDirectoryPosition;...
!&             " to";NewDirectoryPosition
        ! Read contents of target in case valid entry there.
        Read #1@NewDirectoryPosition,DirectoryEntry2$
        If DirectoryEntry2$[19]=0
        Then
700         !D! Print "Target is empty, fill with relocated entry."
            Write #1@NewDirectoryPosition,DirectoryEntry$
            ! Since nothing displaced, relocation is done.
            If NewDirectoryPosition=LastBlankDirectoryEntry
            Then
                ! Oops, must back up to find blank dir entry
                LastBlankDirectoryEntry=-1
                DirectoryScanPointer=NewDirectoryPosition+32
            Fi
            Return Subroutine
        Fi
800     !D! Print "Target directory entry is busy: ";
        ! Decide where target directory entry should be.
        DesiredDirectoryPosition2=HashName(DirectoryEntry2$)
        !D! Print DirectoryEntry2$[1,16],DesiredDirectoryPosition2
        ! Assert: If DirectoryEntry2$[1,16]=DirectorySys$...
        !         Then it is hashed correctly!
        If DesiredDirectoryPosition2<=NewDirectoryPosition...
&       and DesiredDirectoryPosition2+NBPS>NewDirectoryPosition...
&       Or Distance(DesiredDirectoryPosition,NewDirectoryPosition)...
&       >=Distance(DesiredDirectoryPosition2,NewDirectoryPosition)
        Then
900         !D! Print "Contents of target slot are hashed correctly or better."
            ! Leave target slot alone, and inspect next slot
            NewDirectoryPosition=NewDirectoryPosition+32
            If NewDirectoryPosition>=DirectorySizeInBytes
            Then NewDirectoryPosition=0 Fi
        Else
1000        !D! Print "Target slot is not hashed correctly."
            ! Plant this directory entry
            Write #1@NewDirectoryPosition,DirectoryEntry$
            ! and then relocate contents of target slot
            DirectoryEntry$=DirectoryEntry2$
            DesiredDirectoryPosition=DesiredDirectoryPosition2
            NewDirectoryPosition=DesiredDirectoryPosition
        Fi
    End
    Return Subroutine
End
!^L
Subroutine RelocateDirectorySYS
! Relocate the DIRECTORY.SYS directory entry to optimal location
!   FileDirectoryOffset contains offset for current entry for DIRECTORY.SYS
!   RequiredDirectoryOffset contains offset where DIRECTORY.SYS should be
    Open #1,Device$ \ ! Open the disk as a device
    Syscall #1,CCDismount$ \ ! Force SDOS to let go of disk and re-mount
    Read #1@0,Boot$ \ ! Read boot sector so we can update BootDirLSN
    Syscall #1,CCSetMapAlgorithm$,Boot$[:16+1,2] \ ! set proper MapAlgorithm
    Syscall #1,CCUnlockdisk$ \ ! Allow us to write on the disk

    !D! Print DirectorySys$;" file locator information:"
    !D! Print "File NLCN=";FileNLCN;"HCSIC=";FileHCSIC;...
!&         "FileHLCN=";hex$(FileHLCN);" FileHeaderPosition";FileHeaderPosition

    ! fetch DIRECTORY.SYS entry
    Read #1@LogicalFilePosition(FileDirectoryOffset),DirectoryEntry$
    !D! Print "fetched...";DirectoryEntry$[1,16]

    ! fetch contents of location where DIRECTORY.SYS entry belongs
    Read #1@LogicalFilePosition(RequiredDirectoryOffset),DirectoryEntry2$

    ! Swap slots so DIRECTORY.SYS entry is placed optimally
    Write #1@LogicalFilePosition(FileDirectoryOffset),DirectoryEntry2$
    Write #1@LogicalFilePosition(RequiredDirectoryOffset),DirectoryEntry$

    Print "DIRECTORY.SYS entry placed at LSN";LogicalSectorNumber

    ! Update BOOT:DIRLSN in boot sector
    Boot$[:1B+1]=MSB(MSB(LogicalSectorNumber))
    Boot$[:1B+2]=LSB(MSB(LogicalSectorNumber))
    Boot$[:1B+3]=LSB(LSB(LogicalSectorNumber))
    CheckSum=0\For i=17 to 31 Do CheckSum=CheckSum+Boot$[i]\! calc checksum
    Boot$[32]=:FF XOR (CheckSum&:FF) \ ! Adjust Checksum byte
    Write #1@0,Boot$ \ ! Update Boot sector
    Syscall #1,CCDismount$ \ ! Force SDOS to let go of disk and re-mount
    Close #1
    Return Subroutine
End
!^L
Subroutine FreeDirectoryUnneededClusters
!   Returns all DIRECTORY.SYS data clusters not containing data...
!   back to DISKMAP.SYS.
!   Assert: Directory has at least enough data clusters to cover filesize,
!   and directory is not sparse.
    !D! Print "Freeing Unneeded DIRECTORY.SYS data clusters..."
    Open #1,Device$ \ ! Open the disk as a device
    Syscall #1,CCDismount$ \ ! Force SDOS to let go of disk and re-mount
    Read #1@0,Boot$ \ ! Read boot sector so we can find DIRECTORY.SYS
    Syscall #1,CCSetMapAlgorithm$,Boot$[:16+1,2] \ ! set proper MapAlgorithm

    ! Read DIRECTORY.SYS directory entry
    LogicalSectorNumber=(Boot$[:1B+1]**8+Boot$[:1B+2])*256+Boot$[:1B+3]
    ! Print "LSN for DIRECTORY.SYS directory entry =";hex$(LogicalSectorNumber)
    Read #1@LogicalSectorNumber*NBPS,DirectoryEntry$
    !D! Print "Read directory entry for ";DirectoryEntry$[1,16]
    ! Compute DIRECTORY.SYS file location information from directory entry
    FileNLCN=DirectoryEntry$[20]**8+DirectoryEntry$[21]
    FileHCSIC=DirectoryEntry$[19]
    FileHLCN=DirectoryEntry$[17]**8+DirectoryEntry$[18]
    !D! Print "FileHLCN = ";hex$(FileHLCN)
    FileHeaderPosition=FileHLCN*NSPC*NBPS
    FileSize=((DirectoryEntry$[22]**8+DirectoryEntry$[23])*256+...
&              DirectoryEntry$[24])*256+DirectoryEntry$[25]
    !D! Print "FileSize =";FileSize
    DesiredFileNLCN=FileSize/(NSPC*NBPS)+1
    !D! Print "DesiredFileNLCN = ";DesiredFileNLCN
    If FileNLCN=DesiredFileNLCN
    Then
        ! DIRECTORY.SYS is exactly the right size.
        Close #1 \ ! To ensure subroutine always exits with file closed
        Return Subroutine
    Fi
    ! DIRECTORY.SYS has too many data clusters. Deallocate the extras.

    Syscall #1,CCUnlockdisk$ \ ! Allow us to write on the disk

    ! Set the number of clusters in the Directory to the proper number
    DirectoryEntry$[20]=MSB(DesiredFileNLCN)
    DirectoryEntry$[21]=LSB(DesiredFileNLCN)
    Write #1@LogicalSectorNumber*NBPS,DirectoryEntry$
    ! Notice that up to this point, we have not asked SDOS to access
    ! the disk as if it had a file system.  We have been avoiding this
    ! since we didn't want SDOS to capture a copy of the DIRECTORY.SYS
    ! entry until after the NLCN count was adjust properly.
    ! Now that it is adjusted properly, we can access the file system safely.

    ! Alas, there is another trap to skate around (what a metaphor).
    ! We are not sure that DISKMAP.SYS is properly placed in DIRECTORY.SYS;
    ! i.e., we are not sure we will succeed if we try to open DISKMAP.SYS.
    ! Since we need to fiddle with DISKMAP.SYS, we hunt for it ourselves,
    ! ignoring "never-before-used" directory entries.

    For i=0 to FileSize-1 step 32
        ! Hunt for DISKMAP.SYS directory entry
        Read #1@LogicalFilePosition(i),DirectoryEntry2$
        If DirectoryEntry2$[19]=0 then cycle i \ ! empty directory entry
        !D! Print i,DirectoryEntry2$[1,16]
        If DirectoryEntry2$[1,16]="DISKMAP.SYS     "
        Then Exit i \ ! We found the directory entry for DISKMAP.SYS
    Next i
    If i>=FileSize Then Error 1006 \ ! No DISKMAP.SYS file, I give up.
    ! Locate LCN of DISKMAP.SYS header cluster
    LogicalClusterNumber=DirectoryEntry2$[17]**8+DirectoryEntry2$[18]
    ! Locate LCN of DISKMAP.SYS 1st data cluster
    Read #1@LogicalClusterNumber*NSPC*NBPS+2,LCN$
    ! Compute byte offset from beginning of disk to DISKMAP.SYS data cluster
    DiskMapDataPosition=(LCN$[1]**8+LCN$[2])*NSPC*NBPS
    !D! Print "Disk Map Data Position = "; DiskMapDataPosition
    For RelativeClusterNumber=DesiredFileNLCN to FileNLCN-1
        ! This loop operates on the assumption that the file is not sparse
        ! Fetch next cluster to free from file header
        Read #1@FileHLCN*NSPC*NBPS+RelativeClusterNumber*2,LCN$
        LogicalClusterNumber=LCN$[1]**8+LCN$[2]
        !D! Print "Freeing LCN ";hex$(LogicalClusterNumber)
        ! Remove cluster from header
        Write #1@FileHLCN*NSPC*NBPS+RelativeClusterNumber*2,DummyLCN$
        ! Now mark the LCN as "free" in DISKMAP.SYS
        BitNumber=LogicalClusterNumber&7
        Read #1@DiskMapDataPosition+LogicalClusterNumber**-3,Byte$
        !D! Print "Map Byte ";hex$(Byte$[1])
        If Byte$[1]&(1**BitNumber)=0
        Then Error 1016 \ ! Tried to deallocate an unallocated cluster
        Byte$[1]=Byte$[1]-(1**BitNumber) \ ! Zeros the bit marking cluster as set
        Write #1@DiskMapDataPosition+LogicalClusterNumber**-3,Byte$
    Next RelativeClusterNumber
    Syscall #1,CCDismount$ \ ! Force SDOS to flush all back to the disk
    Close #1 \ ! DEVICE$
    !D! Print "Done freeing Unneeded DIRECTORY.SYS data clusters..."
    Return Subroutine
End
!^L
! ******** Begin Main Program ********
    print Version$
    print "Before running this program, be sure to SDOSDISKVALIDATE."
    input "Rehash directory on what device? " device$

    open #1, device$ cat DirectorySys$
    if device$="" Then device$="disk:"

    Print
    Print Device$;DirectorySys$;" statistics:"
    Syscall #1,SCGetFileSize$,"",Temp$
    DirectorySizeInBytes=0
    For i=1 to 4 do DirectorySizeInBytes=DirectorySizeInBytes*256+Temp$[i]
    Print "Directory Size in bytes:";DirectorySizeInBytes

    ! Compute NSPC and NBPS for device
    Syscall #1,SCGetParams$,"",Temp$
    NBPS=Temp$[1]*256+Temp$[2]
    NSPC=Temp$[3]

    Print "Number Of Bytes Per Sector =";NBPS
    Print "Sectors per Cluster =";NSPC
    NumberOfSectorsInDirectory=DirectorySizeInBytes/NBPS
    Print "Number of Sectors in Directory:";NumberOfSectorsInDirectory

    ! Accumulate some statistics BEFORE we rehash the directory.
    DisplayHashStatistics

    Print "WARNING: FROM THIS POINT ON, USE OF THIS PROGRAM IS HAZARDOUS!"
    Print "Once started, ^C^C or <ESC> will probably lose some files;"
    print "may cause loss of entire DIRECTORY.SYS.  Other failures can"
    print "also result in LOSS of entire disk contents. Now is safe to quit."
    Input "Are you sure you want to REHASH the directory? " Temp$
    if lowercase$(Temp$)<>"yes"
    then print "I didn't think so. Bye."\Exit
!^L
    ! He said, REHASH IT, JACK.  Here we go. Bye bye old directory!

    Syscall #1,CCSetFileProtection$,NoProtection$ \ ! Remove Write prot from dir

AskForNewDirectorySize: ! Ask for change to directory size, if needed
    Print "Number of slots desired in DIRECTORY.SYS (<CR>=No change) ";
    Input "" Temp$
    If len(Temp$)=0 Then CheckDirectorySysPosition
    If Error When DesiredNumberOfSlots=val(Temp$)
    Then AskForNewDirectorySize \ ! ask again if not a number
    If DesiredNumberOfSlots<0 ...
&       or DesiredNumberOfSlots<>int(DesiredNumberOfSlots) ...
&       or DesiredNumberOfSlots*32/NBPS > 65535
    Then AskForNewDirectorySize
    ! Adjust the size of DIRECTORY.SYS
    NumberOfDirectorySlotsPerCluster=NBPS*NSPC/32
    RequiredNumberOfSlots=...
&       DesiredNumberOfSlots/NumberOfDirectorySlotsPerCluster
    If RequiredNumberOfSlots<>int(RequiredNumberOfSlots)
    Then RequiredNumberOfSlots=int(RequiredNumberOfSlots+1)
    RequiredNumberOfSlots=...
&       RequiredNumberOfSlots*NumberOfDirectorySlotsPerCluster
    Print "That requires";RequiredNumberOfSlots;"directory slots."
    If TotalDirectorySlots=RequiredNumberOfSlots
    Then CheckDirectorySysPosition
    ElseIf TotalDirectorySlots<RequiredNumberOfSlots
    Then
        OldDirectorySize=DirectorySizeInBytes
        NewDirectorySize=RequiredNumberOfSlots*32
        Print "Increasing directory size to";NewDirectorySize
        Position #1@OldDirectorySize
        For DirectorySizeInBytes=OldDirectorySize...
&                to NewDirectorySize-1 step 32
            Write #1,NeverUsedDirectoryEntry$
        Next DirectorySizeInBytes
        NumberOfSectorsInDirectory=DirectorySizeInBytes/NBPS
        ! Decide where DIRECTORY.SYS will go after rehashing
        RequiredDirectoryOffset=HashName(DirectorySys$)
        ! Now that directory size has been adjusted, flush everything back
        ! to the disk so SDOS won't push modified file control blocks back
        ! into the directory while we are shuffling its contents around.
        Close #1 \ ! Close the directory
        Open #1,device$\Syscall #1,CCDismount$\Close #1\! Flush to disk
        ! DIRECTORY.SYS entry must be moved now, as revised file size
        ! changes hash function, which will prevent us from looking
        ! it up again unless it is in exactly the right place.
        ! FileDirectoryOffset is offset to current entry of DIRECTORY.SYS
        ! RequiredDirectoryOffset is offset where DIRECTORY.SYS should be
        RelocateDirectorySYS
        ! Having expanded the directory by writing to it as a file
        ! means that SDOS extended the file by BOOT:MIDALLOC, which
        ! implies that DIRECTORY.SYS may have acquired some data
        ! clusters that will not be used. Now deallocate the
        ! these extra clusters, to ensure the condition
        ! "DIRECTORY.SYS filesize = k*NCLUSTERS for integer k"
        ! (if we don't do this, when the DIRECTORY.SYS is automatically
        !  expanded by SDOS, an already allocated cluster, probably with
        !  trash, will get used as the expansion area, violating the
        !  assumption that expanding the directory will cause a new
        !  cluster to allocated AND zeroed, and we end up with some
        !  garbage files).
        FreeDirectoryUnneededClusters
        Open #1,Device$ Cat DirectorySys$ \ ! Re-open the directory
        DisplayHashStatistics
    Else
        ! Must want to shrink DIRECTORY.SYS
        If RealDirectoryEntries>RequiredNumberOfSlots
        Then
            Print "*** Can't shrink DIRECTORY.SYS, too many files."
            Goto AskForNewDirectorySize \ ! ask for more reasonable value
        Fi
        ! Now we are sure there is enough room to shrink the directory
        OldDirectorySize=DirectorySizeInBytes
        NewDirectorySize=RequiredNumberOfSlots*32
        Print "Shrink directory size to";NewDirectorySize
        DirectorySizeInBytes=NewDirectorySize
        NumberOfSectorsInDirectory=DirectorySizeInBytes/NBPS
        ! Decide where DIRECTORY.SYS will go after rehashing
        RequiredDirectoryOffset=HashName(DirectorySys$)
        LastBlankDirectorySlot=0 \ ! Where to look for a blank slot
        ! We probably must move DIRECTORY.SYS directory entry
        ! We can't do it now, as after moving it, its size won't be
        ! suitably shrunk, and so it might not be findable when
        ! re-OPENed (as hash code would be wrong).  However, we can do
        ! some preparation.  When DIRECTORY.SYS directory entry
        ! is moved, it might displace a directory entry.
        ! Move the displaced directory entry to a free slot NOW,
        ! mark the slot as "free", but remember that the slot is reserved.
        ! Inspect future DIRECTORY.SYS slot
        Read #1@RequiredDirectoryOffset,DirectoryEntry$
        If DirectoryEntry$[19]=0
        Then
            ! The desired slot is not busy. Leave it alone.
        ElseIf FileDirectoryOffset<>RequiredDirectoryOffset
        Then
            !D! Print "Displacing ";DirectoryEntry$[1,16]
            ! The desired directory slot IS busy, and it doesn't contain
            ! (accidentally) the entry for DIRECTORY.SYS.
            ! Relocate the slot content to some other place.
            For LastBlankDirectorySlot=LastBlankDirectorySlot...
&                   to NewDirectorySize-1 step 32
                !D! Print "scanning for blank entry at";LastBlankDirectorySlot
                ! Assert: displaced slot is marked busy, won't be seen as free
                Read #1@LastBlankDirectorySlot,DirectoryEntry2$
                If DirectoryEntry2$[19]=0
                Then Exit LastBlankDirectorySlot
            Next LastBlankDirectorySlot
            ! Assert: there MUST be free directory slot!
            !D! Print "to free slot found at";LastBlankDirectorySlot
            ! Move entry needed by DIRECTORY.SYS to free slot.
            Write #1@LastBlankDirectorySlot,DirectoryEntry$
            ! Remember where to look next for another blank spot
            LastBlankDirectorySlot=LastBlankDirectorySlot+32
            ! Mark displaced slot as empty, but remember it is reserved
            Write #1@RequiredDirectoryOffset,NeverUsedDirectoryEntry$
        Fi
        ! Now new DIRECTORY.SYS entry slot is reserved
        ! Time to shuffle used directory entries down so top of directory
        ! is completely empty. Then we can truncate directory size.
        For DirectoryScanPointer=NewDirectorySize...
&               to OldDirectorySize-1 step 32
            !D! Print "Inspecting at";DirectoryScanPointer
            Read #1@DirectoryScanPointer,DirectoryEntry$ \ ! fetch current entry
            If DirectoryEntry$[19]>0
            Then
                !D! Print DirectoryEntry$[1,16];" found at";DirectoryScanPointer
                If DirectoryEntry$[1,16]=DirectorySys$
                Then
                    !D! Print "Skipping ";DirectorySys$
                Else
                    For LastBlankDirectorySlot=LastBlankDirectorySlot...
&                           to NewDirectorySize-1 step 32
                        !D! Print "scanning for blank entry at";LastBlankDirectorySlot
                        ! Skip slot reserved for DIRECTORY.SYS
                        If LastBlankDirectorySlot=RequiredDirectoryOffset
                        Then Cycle LastBlankDirectorySLot
                        Read #1@LastBlankDirectorySlot,DirectoryEntry2$
                        If DirectoryEntry2$[19]=0
                        Then Exit LastBlankDirectorySlot
                    Next LastBlankDirectorySlot
                    ! Assert: there MUST be free directory slot!
                    !D! Print "...moved to free slot at";LastBlankDirectorySlot
                    ! Swap the free slot with the busy slot
                    Write #1@LastBlankDirectorySlot,DirectoryEntry$
                    ! Remember where to look next for another blank spot
                    LastBlankDirectorySlot=LastBlankDirectorySlot+32
                    Write #1@DirectoryScanPointer,DirectoryEntry2$
                Fi
            Fi
        Next DirectoryScanPointer
        ! Now the last cluster of DIRECTORY.SYS is entirely blank
        !D! Print "Truncating ";DirectorySys$;" to";DirectorySizeInBytes;"bytes"
        Position #1@NewDirectorySize \ ! Position to set file size
        Syscall #1,CCSetFileSize$ \ ! Shrink directory size
        Close #1
        Open #1,device$\Syscall #1,CCDismount$\Close #1\! Flush to disk
        ! DIRECTORY.SYS entry must be moved now, as revised file size
        ! changes hash function, which will prevent us from looking
        ! it up again unless it is in exactly the right place.
        ! FileDirectoryOffset is offset to current entry of DIRECTORY.SYS
        ! RequiredDirectoryOffset is offset where DIRECTORY.SYS should be
        RelocateDirectorySYS
        ! Now deallocate clusters not used by DIRECTORY.SYS, to ensure
        ! the condition "DIRECTORY.SYS filesize = k*NCLUSTERS for integer k"
        ! (if we don't do this, when the DIRECTORY.SYS is automatically
        !  expanded by SDOS, an already allocated cluster, probably with
        !  never-before-used entries, will get used as the expansion
        !  area, violating the assumption that expanding the directory
        !  leaves it with zero never-before-used entries, and we
        !  end up with mysterious "can't find file" errors for existing files)
        FreeDirectoryUnneededClusters
        Open #1,Device$ Cat DirectorySys$ \ ! Re-open the directory
        DisplayHashStatistics
    Fi

CheckDirectorySysPosition: ! and relocate if wrong
    Close #1 \ ! Close the directory
    ! Check: is DIRECTORY.SYS located properly?
    RequiredDirectoryOffset=HashName(DirectorySys$) \ ! Where it MUST be
    If FileDirectoryOffset<>RequiredDirectoryOffset
    Then
        ! It can only be wrong if DIRECTORY.SYS size has not changed.
        Call RelocateDirectorySYS \ ! place DIRECTORY.SYS optimally
    Fi
!^L
    Print "Reorganizing DIRECTORY.SYS... please wait"
RelocateRestOfDirectory: ! Relocate all directory entries except DIRECTORY.SYS
    Open #1,Device$ cat DirectorySys$ \ ! Re-open DIRECTORY.SYS
    DirectoryScanPointer=0 \ ! Where to start scanning directory
RehashDirectory: ...
&   Repeat
100     !D! Print "*** Inspect directory slot at";DirectoryScanPointer
        If int(DirectoryScanPointer/NBPS)*NBPS=DirectoryScanPointer
        Then
150         !D! Print "Start of sector --> no blank directory slot in sector"
            LastBlankDirectoryEntry=-1
        Fi
        Read #1@DirectoryScanPointer,DirectoryEntry$
        If EOF(1)
        Then
            !D! Print "Directory Re-hash operation completed."
            Exit RehashDirectory
        Fi
        If DirectoryEntry$[19]=0
        Then
200         !D! Print "This slot is not busy."
            If LastBlankDirectoryEntry<0
            Then LastBlankDirectoryEntry=DirectoryScanPointer
            ! If directory entry has been used, convert it to NotUsed.
            ! If already marked as NotUsed, don't change it, conserving amount
            ! of disk write time, especially on well-organized directories
            If DirectoryEntry$(1)&:80=0
            Then
                ! Convert "used" directory entry to Never-used entry
                Write #1@DirectoryScanPointer,NeverUsedDirectoryEntry$
            Fi
            ! Assert: directory entry now is marked as "NeverUsed"
            DirectoryScanPointer=DirectoryScanPointer+32 \ ! advance to next
        Else
300         DesiredDirectoryPosition=HashName(DirectoryEntry$)
            !D! Print DirectoryEntry$[1,16];" Hash=";HashCode;...
&                 "Desired position=";DesiredDirectoryPosition
            ! Assert: If DirectoryEntry$[1,16]=DirectorySys$
            !         Then it is hashed correctly and will not be relocated
            If DesiredDirectoryPosition<=DirectoryScanPointer...
&           and DesiredDirectoryPosition+NBPS>DirectoryScanPointer
            Then
400             !D! Print "Directory entry is in proper directory sector."
                If LastBlankDirectoryEntry>=0
                Then
                    ! but there is a hole in that directory sector.
450                 !D! Print "Swap this directory entry with hole at";...
!&                         LastBlankDirectoryEntry
                    Write #1@LastBlankDirectoryEntry,DirectoryEntry$
                    Write #1@DirectoryScanPointer,NeverUsedDirectoryEntry$
                    ! Assert: place following former blank directory slot
                    ! MUST be blank, so we need not look at it.
                    ! Remember the new lowest blank place.
                    LastBlankDirectoryEntry=LastBlankDirectoryEntry+32
                Fi
                DirectoryScanPointer=DirectoryScanPointer+32 \ ! advance to next
            Else
500             !D! Print "This directory entry is in the wrong place."
                ! Mark current entry in sector as unused
                Write #1@DirectoryScanPointer,NeverUsedDirectoryEntry$
                ! If this is first unused entry, remember where it is
                If LastBlankDirectoryEntry<0
                Then LastBlankDirectoryEntry=DirectoryScanPointer
                DirectoryScanPointer=DirectoryScanPointer+32
                NewDirectoryPosition=DesiredDirectoryPosition
                RelocateDirectoryEntry \ ! and all entries displace by it
            Fi
        Fi
    End

    ! Put Write protect back on DIRECTORY.SYS
    Syscall #1,CCSetFileProtection$,WriteBackupProtect$

    Print
    Print "Revised ";Device$;DirectorySys$;" statistics:"
    DisplayHashStatistics \ ! So user knows how much improvement

    ! Now that directory entries have been shuffled, dismount the drive so
    ! SDOS won't continue to use invalidated File Control Blocks
    ! (FCBs point back to directory slot!) for DISKMAP.SYS and ERRORMSGS.SYS.
    Close #1 \ ! Close the directory
    Open #1,device$\ Syscall #1,CCDismount$\Close #1\! Flush all back to disk

    Print
    Print "Now, you should run SDOSDISKVALIDATE."
    Exit

END
