I’ve found lots of reverences to using livecd-iso-to-disk from the livecd-tools package to create bootable USB media from an ISO image (or for a DVD, quite possibly a UDF image, but the principle is the same). However, most of the descriptions either seem light on examples, or give absurdly complicated examples. It’s actually quite easy, if you’re not concerned with preserving the old content of the USB media. Continue reading
Microsoft introduced a new “exFAT” file system a few years ago, and I wouldn’t care about it in the least, except that it is now the official filesystem for SD-XC cards. I only care about that in that digital cameras and such will likely only support exFAT on SD-XC cards, and I’d like my computer, not running Windows, to be able to efficiently access files on such cards. The problem is that Microsoft filed several patent applications covering exFAT. One of them is application US 2009/0164440 A1, for which the US patent office has recently mailed a “Notice of Allowance”, which means that they have decided to issue the patent.
This application is titled “Quick filename lookup using name hash”. Based on the title, it sounded like they are doing what TRS-DOS 2.0 did back in 1978, which is putting on the disk a hash table of filenames which then refer to directory entries. TRS-DOS did that so that it usually only needed to read two sectors to look up a file, the HIT (Hash Index Table) sector, and the actual directory sector containing the file’s directory entry. Otherwise they might have had to read multiple directory sectors to find the file if it existed, and all of the directory sectors if it did not.
The claims of the patent are a little difficult to interpret. They refer to “a first one or more computer readable storage media having computer executable instructions…”. This is basically referring to the disk/flash/etc. the operating system is booted from. They refer to “a second one or more…” which is the disk/flash/etc. which holds the file system in question.
Here’s are two of the independent claims:
1. A first one or more computer readable storage media having computer executable instructions that, when executed on at least one processor, configure the at least one processor to perform a method of detecting if a target file name exists on a second one or more computer readable storage media, the method comprising:
(A) determining a name hash from the target name;
(B) determining if the name hash corresponds to a directory entry set name hash value, the directory entry set name hash value corresponding to one of a plurality of directory entry sets, each of the plurality of directory entry sets stored on the second one or more computer readable storage media;
(C) determining if the target name matches a directory entry set name corresponding to the one of the plurality of directory entry sets after step (B) determines the name hash corresponds to the directory entry set name hash value; and
(D) indicating that the target name exists after step (C) determines the target name matches the directory entry set name.
19. A method of detecting if a target file name exists, the method executing on one or more processors, the method comprising:
(A) determining a file name hash from the target file name;
(B) determining if the file name hash corresponds to a directory entry hash value, the directory entry hash value corresponding to one of a plurality of directory entries;
(C) determining if the target file name matches a file name, the file name corresponding to the one of the plurality of directory entries after step (B) determines the file name hash corresponds to the directory entry hash value; and
(D) indicating that the target file name exists after step (C) determines the target file name matches the file name corresponding to the one of the plurality of directory entries.
These seem to be to be to be *exactly* what TRS-DOS 2.0 did as early as 1978, so it seems possible that TRS-DOS could be used as prior art to invalidate at least these independent claims, and quite possibly some of the dependent claims as well.
So my question is, are there any published works documenting the TRS-DOS file system on-disk format, especially the use of the HIT table, other than “TRS-80 Disk and Other Mysteries” by H. C. Pennington?
I’ve been trying to build an EPEL 6 package (for Red Hat Enterprise Linux 6, Centos 6, etc.) of Meshlab, for which I already have a Fedora package. The latest challenge is that the Koji build server is trying to use qt-devel-3.x, while Meshlab needs qt-devel-4.x.
The obvious thing to do was to change the spec from:
BuildRequires: qt-devel >= 4.6
However, Koji still tries to use qt-devel-3.x!
A Google search revealed an explanation in the rpmfusion-developers list from Kevin Fenzi:
That doesn’t work because it’s missing the Epoch. “>= 1:4″ would work, but it’s better to use the virtual qt4-devel Provides, which is backwards-compatible with EPEL 5 (which had an actual qt4-devel package), which will keep working in the future when Qt 5 will be the default and which avoids the pesky Epoch.
Now on to the next problem!
The conventional wisdom has it that if you add a user to a group in a Linux (or Unix) system, the user will have to log in again for the new group membership to take effect. Using the “newgrp” command, an existing shell can gain the group membership. For example, to create a new group “foo”, add the current user to the group, and make it effective immediately:
sudo groupadd foo sudo usermod -a -G foo user newgrp foo
Note that this makes the new group effectively the user’s primary group ID in the current shell and any new descendents. If you don’t want that, do another newgrp back to the original group. The new group will still be in the process’ group list.
Note that the “-a” (append) option to usermod may not exist in all Linux distributions.
It looks like the developers of TRS-80 Model II TRSDOS were very paranoid that someone might be able to bypass the filesystem and access data on a floppy directly. I’m not sure if their primary concern was file password protection, or if they had other reasons. Obviously you could write a program that accesses the floppy directly, by talking to the FDC and DMAC chips yourself, and there’s not really anything that can be done to prevent that.
Oddly enough, this was exactly the opposite of what Apple did in Apple DOS. Apple published the APIs to read and write sectors (RWTS), but never published the “File Manager” APIs that allowed access to the file system through means other than passing commands through the character output vector (e.g., the BASIC statement PRINT CHR$(4);”OPEN FOO”).
I’ll mostly describe how things work in Model II TRSDOS 1.2, the earliest version I’ve been able to obtain. I haven’t studied 2.0 nearly as much yet. The TRSDOS 1.2 “kernel” consists of three parts, while later versions are more monolithic.
The Model II boot ROM loads all of drive 0 track 0 (single density, 26 sectors of 128 bytes) into memory starting at 0e00. First it looks for the four characters “DIAG” at 1400 and “BOOT” at 1000. If either are missing, it refuses to proceed. It calls the code at 1404, which in TRSDOS is a simple hardware diagnostic. When that returns, it jumps to the first stage boot loader code at 1004. Some other operating systems don’t bother with a diagnostic, and just start their boot code at 1404, never returning to the ROM.
The first stage boot loader actually understands the TRSDOS filesystem enough to find the directory entries of files in TRSDOS load module format, and load them into memory. In 1.2, it loads “IODVRS/SYS” and then “TRSDOS/SYS”, and jumps into the latter. The Model II TRSDOS filesystem is similar in many regards to that of Model I TRSDOS, but not enough to actually be compatible. Unsurprisingly, it looks like an intermediate step in the evolution from Model I TRSDOS to Model III TRSDOS. As in Model III TRSDOS, files can only have a single directory entry, with a limited number of extents.
IODVRS/SYS contains, as the name implies, the low level I/O drivers for the system, including the keyboard, display, printer, and floppy drives, the dispatching for system (SVC) calls, and a few utility SVCs. However, it only contains the SVC handlers for services 0-28, the I/O functions and basic utility SVCs. Note in particular that it contains no file system code. IODVRS/SYS is conceptually similar to the CP/M BIOS, though lacking CP/Ms charming simplicity. IODVRS/SYS provides several undocumented SVCs for internal use by TRSDOS, including floppy subsystem initialization (13), floppy sector read (14), and floppy sector write (16). Note that at the time IODVRS/SYS is loaded, no call is made into it to initialize it.
TRSDOS/SYS, however, is called after being loaded. It basically performs the TRSDOS initialization that only has to happen at boot time. It has another implementation of filesystem reading and load module format handling, very similar to what is present in the stage 1 boot, but now instead of talking to the FDC and DMAC directly, it uses the undocumented floppy SVCs described previously. After various initialization, it loads SYSRES/SYS and jumps into it.
SYSRES/SYS contains the filesystem code and other relatively high-level TRSDOS infrastructure code. It generally relies on SVC calls into IODVRS/SYS to perform all I/O, and has very little other dependence on IODVRS/SYS internals. This is conceptually similar to the CP/M BDOS. It loads system overlays to handle some SVCs and user commands. Overlays SYS0/SYS through SYS9/SYS are small overlays, occupying one disk granule (five sectors) and loading into 2200-26ff. Other overlays may be larger, and load at 2800 or higher. Many of the overlays do depend on knowledge of the internals of SYSRES/SYS, directly accessing subroutines and data structures without the use of vector tables or the like. This means that SYSRES/SYS and the overlays must have been built at the same time, and would generally not be interchangeable with earlier or later releases.
Anyhow, getting back to the paranoia part. Someone apparently decided that simply not documenting the SVCs that provide sector-level access to the floppy was not sufficient to thwart those that might want to bypass the filesystem. After TRSDOS/SYS uses those SVCs for its part in the boot process, it actually removes them from the SVC vector table, and sets up jumps to them at undocumented internal TRSDOS locations 1130 (read sector) and 1133 (write sector).
In TRSDOS 1.2, access to all of the system files, including overlays, is done through the file system. The system files have normal file system entries. Unlike Model I TRSDOS, neither the system file directory entries nor the file contents need to be in any special location on the disk.
In TRSDOS 2.0, things are much more monolithic. The stage 1 boot code only loads and jumps into a single file, SYSRES/SYS. The boot code does not care where this file is located, but other parts of the system do. All of the overlays, small and large, are stored in a single file, SYSTEM/SYS, which is required to start on the track after the primary directory. The first sector of SYSTEM/SYS contains a kind of overlay directory that gives the track and sector numbers at which each overlay starts.
There is perhaps some advantage to putting all of the overlays in a single file, since the number of directory entries on the diskette is limited to 96. However, the need for a second, special directory mechanism for overlays is ugly, even if it is only a simple one. Requiring the system files to be at fixed locations on the disk (at least relative to the primary directory) might be a reasonable requirement if it yielded some performance gain, but it generally doesn’t. (With 1.2, the system files are set up when the disk is formatted, so even though they could be anywhere, in practice they are grouped together.)
TRSDOS 2.0 introduced changes to the disk organization, such that TRSDOS 1.2 and 2.0 diskettes are not interchangeable, except that the 2.0 XFERSYS utility can convert a 1.2 diskette to 2.0 format. The disk organization changes are basically gratuitous, and don’t provide any benefit to the user, while obviously being a great inconvenience to users with TRSDOS 1.2. They mashed the GAT (granule allocation table) and HIT (hash index table), which were sectors 1 and 2 of the directory track in 1.2, into just sector 1 in 2.0. In 1.2, the directory occupied sectors 3-26, while in 2.0 it occupies sectors 2-25. The only apparent rationale for doing this is to free up sector 26 on the directory track. In TRSDOS 1.2, sector 26 was not used on any track but the directory track, for any purpose. In TRSDOS 2.0, sector 26 of every track is used to store five bytes of unique disk ID, to better detect disk changes. (it has been suggested that those bytes might also have been used for software copy protection.) However, rather than mashing the GAT and HIT together, which made it impossible to support larger disks such as double-sided disks, they easily could have special cased the directory track(s) and stored the disk ID in either the GAT or HIT sector.
TRSDOS 4.0 introduced much larger changes to the disk organization, in order to support double-sided disks and hard disks. I haven’t yet begun to dig into the 4.0 code.
As part of my RC2012WW project, I ran an 8080 exerciser and other instruction test programs on a Sol20 to better understand the behavior of the 8080′s flags (which are NOT exactly the same as those of the Z-80), and update ksim to accurately simulate the flags. There are a lot of Z-80 simulators out there, but fewer 8080 simulators, and fewer yet that get the flags right.
ksim 0.2 is now released under the GPLv3 license. While ksim may be minimally useful in its current form, it is primarily intended as a reference implementation. There is currently no documentation, and the code is not well-commented. Maximum performance was not a goal, so very little optimization has been done. Interrupts are not implemented, though they would be easy to add. There is crude console I/O, and extremely crude disk I/O. It works just barely well enough that I’ve successfully run CP/M.
By writing some additional 8080 test programs, running them on both the Sol-20 and my simulator, and comparing the output, I’ve found and fixed several bugs in my simulator. Now the 8080 Exerciser running on the simulator matches all the CRCs.
There was a bug in “POP PSW” setting the parity flag wrong, which screwed up all of the CRCs.
I had the polarity of the AF flag wrong for the subtract, compare, and decrement instructions.
In the DAA instruction, to determine whether to correct the high nibble, at one point in the logic I was using AF when I should have been using CY.
While it remains possible that the simulator could contain some errors not caught by the exerciser, at this point I’m fairly confident that it is working correctly. W00t!
With a good power supply filter capacitor, the Sol-20 is now running sufficiently reliably that it passed the 8080 Exerciser., generating the expected CRC values. In order to find the bug(s) in the 8080 simulator I wrote last month, I’ve just started the Sol running a modified version of the exerciser that outputs every result byte it hashes into the CRC. The simulator ran this in 10 minutes on a 3.2 GHz Athlon II X3 450, prodcucing 16,191,998 lines of output. I estimate that it will take 24.5 hours for the Sol-20 to run it.
The reason the Sol I’ve been using is unreliable (mostly in the first 30 seconds after powerup, but sometimes later also) is that C8, a 18000 uF 10V electrolytic filter capacitor for the 5V power supply, has gone high-leakage.
It’s easy to find an electrical replacement, but difficult to find one that is the same physical size as the original. There has been so much advancement in capacitor technology since 1976 that the modern ones are less than a third the volume.
Frank Cringle released a GPL’d Z80 CPU exerciser in 1994, and Ian Bartholomew released modified versions for the 8080 and 8085 in 2009. Since I don’t have CP/M running on my Sol-20 yet, I’ve modified the sources to assemble with the AS macro cross assembler (asl), and run on a “bare metal” Sol-20 (no CP/M), with output to the serial port. I haven’t actually run the modified version on the Sol yet, but have run it on the 8080 simulator I wrote last month.
The purpose of getting it running on the Sol-20 isn’t that I think there’s anything wrong with my Sol-20, but rather that the 8080 simulator doesn’t generate the same hashes, so I probably don’t have the condition code computations correct. Once I’ve verified that it works and produces the correct hashes on the Sol-20, I’ll further modify it to output the bytes being hashed into the CRC, and compare those with the simulator.