Older blog entries for brouhaha (starting at number 55)

Nonpareil

I wrote the brute-force CRC polynomial finder program. It takes six minutes to try all CRC polynomials of order three through sixteen over two buffers of 1024 ROM words, on my Athlon XP 1900+ system.

It appears that the Spice-series calculator selftest uses either a CRC-10 (x^10 + x^9 + x^5 + x^4 + x + 1), or the reverse of that (x^10 + x^9 + x^6 + x^5 + x + 1). The direction of a CRC polynomial has always been confusing to me, because some books and web pages show them shifting one way, and some another, and the whole GF(2) polynomial division concept still seems tricky. I've seen some references that claim that the reverse of a CRC polynomial is effectively as good as the normal one, but nothing authoritative. Any CRC experts out there care to look at my crc.c program and tell me which polynomial it really is?

CRC-10 would have been my first guess, since they are computing it over 10-bit words, so I suppose I could have saved time and just tried it. Though I'm not sure I would have thought to try the reverse polynomial.

I've verified that it works for the HP-32E, HP-33C, and HP-37E, as well as the non-bank-switched banks of the HP-34C, HP-38E, and HP-38C. I'll need to hack my program a bit to handle the bank switched ones, because the bank-switch instruction actually does toggle the bank even when it is fetched by the self-test instruction. That's why the bank-switch instruction is always present in identical locations in both banks, and there are always an even number of them so that the self-test instruction completes with the original bank selected.

Anyhow, I'll put the CRC verification code in the next release of Nonpareil, although I don't yet know how the self-test instruction indicates a failure, so I won't actually get it hooked in. But I can have it put up a warning dialog at startup if the ROM CRCs are bad.

In case anyone wants to see it, here is the brute-force polynomial finder program: gencrc.c. I suppose it might be useful for reverse-engineering proprietary protocols.

Googling for information on CRCs turned up an interesting recent paper (PDF format): Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks. It turns out that some of the old standbys aren't really all that great:

Update: I added a function to munge the ROM images for bank switching, and now I can verify that the HP-34C, HP-38E, and HP-38C ROMs also all have the same CRC. I still need to dump the ROMs of the HP-31E and HP-33E; when I tried before I ran into technical difficulties.

pdp1dump

I'm a volunteer on the Computer History Museum's PDP-1 Restoration Project. Al Kossow read the museum's collection of PDP-1 paper tapes. Now that we've got the PDP-1 mostly functional, it seems desirable to have an easier way to verify the checksums of the tape images than trying to load them on the PDP-1. Al had written a simple tape dump program; inspired by that I wrote pdp1dump, which understands RIM and BIN format, and verifies the checksums of BIN format.

As usual with my software, it's GPL'd.

One possibility for future enhancement is to add a disassembler.

Nonpareil

Bill asked me about the self-test feature of the Spice series calculators (HP-3xE/C, such as HP-33C). I used the self-test to dump the ROMs by passively monitoring the bus. The processor has a single instruction to compute some kind of check over 1K*10 of ROM, but it seems to only produce a pass/fail result, and it is not clear exactly what kind of check it is.

I tried computing simple additive checksums with and without end-around carry, and that didn't produce consistent results among the various 1K blocks. Since the architecture is bit-serial, they could have implemented a CRC quite efficiently, though they could have used almost any CRC width and polynomial.

I'm considering writing a program to try a brute-force search of all CRC polynomials of orders from 1 to 20 bits. There's probably little chance of the polynomial being of order less than 8, but it doesn't take long to test all the short ones.

Film

On Sunday a group of friends went to see Spiderman 2. It was somewhat predictable, as is usual for action films. I thought the physics was slightly suspect, in much the same way that the ocean is slightly wet. But on the whole I enjoyed it.

e8johan wrote:

System crashes involving fire are annoying. I plan to check if my harddisks work tonight or tomorrow.

Ugh! I hope you're as fortunate with data recovery as I was (diary entries).

Nonpareil

I've been too busy to work on Nonpareil lately, although I've done a little bit of work on the romsucker. I'm going to take a vacation early in June, so maybe I'll find some time. I'd really like to get the Voyager calculators (e.g. HP-16C) working, especially since Maciej Bartosiak has put together some nice HP-15C and HP-16C PNGs for me.

I haven't yet got SCons fully doing what I need. I suppose I'll have to bite the bullet and learn Python. If anyone with SCons expertise would care to help out, it would be greatly appreciated.

PDP-1 Restoration Project

Last week we powered up the PDP-1, and it actually seems to work. The seven months of painstaking restoration have paid off!

Nonpareil

With help from Steven Ellis, I've started switching from GNU Make to SCons. SCons determines dependencies automatically, eliminating the stuff in the Makefile that generated .d files using gcc and sed. It also knows that every target depends on the command line used to generate it, so if you change build flags you don't have to manually do a make clean. SCons is better than make at dealing with object files being placed in separate directories from sources, and at having multiple builds using different compilers or compiler options.

The SConstruct and SConscript files are much simpler than the Makefile they replace. The only drawbacks I see are:

• Anyone building Nonpareil will have to have Python and SCons installed. I don't think this should be too much of a burden since Python should run on any platform that can run Nonpareil, and SCons is trivial to install.
• I don't know SCons and Python very well, so I haven't yet figured out how to write a proper SCons "Builder" to generate .obj and .lst files from .asm by invoking my assembler, and with a dependency on the assembler since it is also built as part of Nonpareil. I also haven't figured out how to write a rule to build the distribution tarball.

Nonpareil

Released Nonpareil 0.44, which adds annunciator support to the HP-41 family, making them much more usable. The scanned image of the HP-41CV has been replaced by a stylized rendering from my older NSIM simulator with graphical improvements by Maciej Bartosiak.

Getting the annunciator support working was more difficult than expected. In the process, I found a bug (or perhaps a documentation error) regarding the GDK function gdk_bitmap_create_from_data(). The documentation claims that this function takes an array of data in XBM format.

XBM format is defined such that the most significant bit of a byte is the leftmost pixel of that byte. But gdk_bitmap_create_from_data() uses the least significant bit of the byte as the leftmost pixel. It might be platform-dependent; I'm running on an x86 and don't have other platforms to test that would likely be different. But XBM format is platform-independent, so either gdk_bitmap_create_from_data() is broken, or the documentation should eliminate the claim that it uses XBM format.

Another bug is that gtk_bitmap_create_from_data() reads past the end of the buffer. I am malloc()ing a buffer to hold my bitmap data, and I found that I have to allocate at least nine bytes more than the "XBM" data occupies in order to prevent a segfault.

Books

I just read Sir Apropos of Nothing by Peter David, a comedic fantasy. It was quite entertaining. There are a few puns, but not a non-stop stream of them like a Xanth novel. The paperback includes a teaser for the sequel, which I'd have to describe as a bawdy parody of Fellowship of the Ring. I'm not a prude, but this didn't particularly inspire me to want to read the second book, the reviews of which are fairly mixed anyhow.

I'd previously read some of Peter David's Legions of Fire Babylon 5 novels, which were extremely good. If you're a B5 fan, you shouldn't miss these, as JMS actually provided the storyline which details what happens on Centauri Prime after the series.

I just started reading Twisty Little Passages: An Approach to Interactive Fiction by Nick Montfort (MIT Press, 2003). This is a great history and survey of interactive fiction from its origins the Crowther and Woods ADVENTURE and MIT/Infocom Zork to the present-day interactive fiction community using the Inform, TADS, and other compilers.

Nonpareil

I've succeeded (mostly) at cross-compiling Nonpareil for Windows using MinGW. I was pleasantly surprised at how little change to the code was required. There are a few minor issues to resolve. The non-rectangular window (equivalent to X shape extension) seems to work, though the support I put in for dragging the window with the mouse does not. The window is the shape of the opaque part of the image, but the image itself is offset down somewhat, so the top of the window is the background color, and the bottom of the image is cut off. For now I'll change the default mode of the Windows version to use a normal window with ornaments.

I'll need a Windows installer. Ideally I'd like to be able to say something like "make windows" on my Linux system, and have a suitable Windows .EXE file pop out. I was somewhat worried that I might have to write my own installer, but it turns out that the Nullsoft installer NSIS can do what I want, and I was able to build it to run on Linux. I had to use MinGW natively on Windows to build the portions of code that NSIS emits to run on the target system (the contents of the Source/exehead directory), but that only needs to be done once. It might even be possible to build that portion on Linux, but it relies on Windows-specific header files that are not normally available on Linux.

I've decided that the Windows verion will NOT be GPL'd. It will be proprietary, and I will sell it. The Linux version will remain GPL'd, and it's possible that someone else could port it to Windows, but given how little interest there's been in porting my calculator simulators to Windows in the past, I don't expect that to happen. I'll put together a no-charge crippleware/nagware demo that only supports a few models and periodically asks the user to purchase a license.

Of course, since the Linux version will still be Free Software, I will encourage customers to switch to Linux and NOT pay me, which would actually make me happier. However, I doubt many people will switch to Linux just to run Nonpareil.

Film

I went to see Kill Bill Vol. 2 last night. What an awesome film! I was worried that it might not live up to my expectations, but I needn't have been concerned. The audio at the Century 21 theatre (San Jose, CA) had problems with the front left channel cutting in and out, which was quite annoying, but I enjoyed the film so much that I forgot to complain to the theatre management as I was leaving.

There were many connections between the two volumes that would probably have been more obvious if the film had been kept in one piece, but perhaps most people will watch Vol. 1 on video before going to see Vol. 2, as my friends and I did.

Nonpareil

Just got back from Anchor Electronics in Santa Clara, buying a bunch of wire-wrap sockets, wrap-IDs, and a few chips. Together with other chips, DC-DC-converters, etc. I've ordered from Mouser and Digikey, I should have enough stuff to build the next version of the romsucker, which is what I use to capture traces and ROM dumps from the old calculators.

Wire-wrap seems to be an obsolescent technology, but it's still useful for simple things that don't need insanely high speed signals. Actually it's not the frequency of square-wave signals that's a problem, but rather the edge rate, and almost all modern chips produce really fast edges.

The old romsucker used an LT1045 hex level shifter, but the input impedance isn't high enough. There are comparators that have better input impedance, but the input voltage swing exceeds their common mode voltage limits. The older calculators have some signals range from -12.5 to +6.5v (PMOS) or -6.5 to +12.5V (NMOS). The clocks have the full 17-19V swing, but the other signals do not.

Most comparators and op-amps have a very limited common mode range, often just a few volts. The LM311 comparator has a fairly wide range, but is quite slow. And most newer comparators and opamps won't run on +/-18V like the old ones.

I'll be using the MAX901 quad comparator, which runs on up to +/-5V supplies, and has a propogation delay of under 10 ns. That's much faster than I need, but there's not much middle ground between that and the old, slow comparators. The common-mode range is from the negative rail (-5V) to 2.25V below the positive rail (+2.75V). So the calculator signals will need to be attenuated by a factor of 4.6 or more.

My first thought was to use a simple two-resistor voltage divider on the inputs. Then the input impedance will be the sum of the resistor values. But by making the resistor values high, the RC time constant is very large, so it will slow the input edges far too much.

Mike suggested using a JFET input op-amp (very high input impedance) in an inverting configuration with a gain of 0.2, so that it acts as an attenuator and buffer. A little reading suggests that op-amps have serious stability issues below unity gain, so this approach might not work too well.

The best option seems to be to use a JFET input op-amp as a voltage follower (unity gain), followed by a two-resistor voltage divider. The output impedance of the op-amp is very low, so the voltage divider can use fairly small value resistors to avoid slowing the edges. The only problem with this approach is finding a fast enough op-amp that has a common-mode input range of +/-12.5V. Not easy, as most of the op-amps with CMR approaching or including the rails will only operate on lower supply voltages.

I turned up the TI TLE2074 "Excallibur" quad op-amp. It's fast and has high input impedance. The CMR only goes to 4.1V above the negative rail. However, it can be run on up to +/-19V supplies. If I use -18V for the negative rail, -12.5V will be well within spec. Before I only had +/-15V supplies (from a dual-output DC/DC converter), so I ordered two +/-12V converters. The outputs are floating with regard to the inputs, so I can use the pair as a +/-24V supply, and use 7818 and 7918 three-terminal regulators for the power for the TLE2074.

This is a lot more hassle than I expected. In the old days there were interface circuits specifically made for interfacing MOS to TTL and vice versa, but those are long since obsolete, and weren't as flexible as I need anyhow.

On the new romsucker, there will be 16 input channels. All the comparator thresholds will be adjustable via DAC outputs. The comparator inputs will all go into a PIC so that some processing can be done in the romsucker. This will eventually be needed in order to dump the ROMs of the first and second generation calculators, because the romsucker will have to generate address bits and drive them on the serial bus with the right timing and PMOS (or NMOS) levels.

Once the new romsucker is working, I'll be able to capture traces from a real HP-25 to find out why the logarithmic and exponential functions aren't working correctly in Nonpareil.

Computer History

This morning a group of Computer History Museum volunteers went on a tour of the USS Pampanito, a WWII-era Balao class Fleet submarine moored in San Franciso. The normal tour is very interesting, and I'd definitely encourage anyone interested in naval history and technology to go, but for us the highlight was a specially-arranged tour of the conning tower, normally off limits to the public for safety reasons. This allowed us to see the Mark III TDC (Torpedo Data Computer), an amazing analog computer used for computing torpedo headings from visual or sonar contact.

The TDC worked much better than the systems in use by our foes, at least partially because it tracked the target in real time, taking into account the submarine's velocity, while the foes' systems apparently did not.

Also of interest, and visible on the public tour, is the ECM Mark II cipher machine. While this was a rotor-based machine that in principle this machine performed the same functions as the famous German Enigma cipher machine, it was much more sophisticated. Instead of advancing the rotors one position at a time like an odometer, it had a second set of rotors that controlled the advances of each of the main rotors.

It occurs to me that this dual-rotor system is not unlike one of the methods used in more recent times to generate pseudo-random numbers. LFSRs (Linear Feedback Shift Registers) can be used as PRNGs, but have many undesirable properties. Sometimes one LFSR is used to control the step rate of another LFSR in order to improve the "randomness" of the results.

Many people on the tour were heard remarking about how incommodious the submarine is. Having heard for many years that they are quite cramped, I actually thought the real thing was not as bad as I'd imagined. But I still wouldn't want to serve on one for months at a time.

Nonpareil

Not only was that theory correct, but ALL bank-switched ROMs track a single bank switch state, and toggle on every 1060 instruction, regardless of from what ROM address the 1060 is fetched. This is unlike the bank-switching on the HP-41C, where every 4K address block that supports bank switching tracks its own independent bank switch status.

Now the 34C, 38E, and 38C limp along somewhat. Most basic math functions on the 34C are working correctly. The 38E and 38C aren't working quite as well. In a 38C trace from a cold start ("Pr Error") through two presses of the "1" key, I can see some differences. I'll have to study the traces to figure out what instruction(s) I've implemented incorrectly. It may be the same bug that's keeping the logarithmic and exponential functions of the 25 from working correctly.

I hope the bank switching on the 19C, 67, 92, 95C, and 97 works the same way, as that will save me a lot of effort.

[later] The trace shows a branch on no carry instruction not branching in the simulator though it does on the calculator. The instructions leading up to the branch instruction do in fact set up conditions such that the branch should not be taken, which means that there's something going wrong earlier leaving incorrect state somewhere. This will be hard to track down, so I'll take some more traces of various operations and hope that some of them show a discrepancy closer to the actual problem.

Nonpareil

I spent several hours over the last few days studying traces captured from a real HP-38C trying to figure out the details of the bank switching. Sometimes the 1060 instruction seems to switch banks and other times not, yet it doesn't appear to be data dependent. At least not in any obvious way.

Just after I got to bed last night, another possibility occurred to me. I've only confirmed a part of the supporting evidence so far; I'll have to revise my code that extracts the ROM image from the raw romsucker log in order to fully test it.

What I realized is that during the execution of the checksum instruction, which checksums a 1K block of ROM, the bank instruction probably still takes effect when it is read out, and that it probably does in fact always take effect immediately as I'd originally guessed. If that's the case, rather than the self test doing the checksum over a single coherent 1K bank, and then the other, it is just doing it twice starting from opposite banks but toggling back and forth within the block.

For that to work and still be able to do a comprehensive checksum of each bank, it would be required that the 1060 instruction always be present at the same location in both banks. And it would be quite likely that there would be an even number of 1060 instructions in each bank, so that after the self-test instruction completed execution would continue in the original bank.

So far tonight I've verified that both the 38E and 38C ROMs do contain an even number of 1060 instructions in both banks of block 1 at corresponding addresses.

Tomorrow I'll hack the log extraction problem and Nonpareil to test the theory.

Film

Watched the DVD of Kill Bill: Vol. 1 in preparation for seeing Vol. 2 in the theatre on Sunday. Am once again amazed at the cinematography and choreography. Not to mention that Uma Thurman and Lucy Liu are really easy on the eyes. Not recommended for those with an aversion to violence, though.

Nonpareil

I've been trying to get the HP-38C working in Nonpareil. In the Spice series, the HP-34C, HP-38E, and HP-38C all have more than 4 Kwords of ROM. Since 4K is the addressing limit of the processor, they use bank switching. The HP-38E/C have two banks for quad 1 (1 Kword from 2000..3777 octal), for a total of 5 Kwords. The HP-34C has two banks each for quads 1, 2, and 3, for a total of 7 Kwords.

I've been trying to figure out the details of the bank switching by comparing Nonpareil traces to captured traces from the real thing. My first guess was that the instruction 1060 octal did an immediate switch of the quad the instruction was fetched from. This was quickly disproven.

The next guess was that it did the bank switch of the current quad, but delayed by one instruction cycle to allow time for a branch instruction to be fetched from the original bank. This is probably not completely correct, as the 38C isn't functional, but it does now display "Pr Error", so I think I'm on the right track.

I'll have to continue capturing traces for comparison. Currently the comparison is a fairly labor-intensive process, but I'll write a script to partially automate it.

Prior to the Spice series, the HP-19C, HP-67, HP-92, HP-95C, and HP-97 used bank switching. I suspect that the technique will be the same as that of the Spice series, but won't know until I can dump the ROMs. Before Spice, the calculators did not have a self-test, so dumping the ROMs of those will be much more difficult. With the self-test, I simply passively monitor the Phi2, SYNC, and ISA signals to grab the ROM addresses and data as the ROM checksum is computed.

Travel, diet, games

Dan and I drove back from Oregon. Back to Atkins diet tomorrow. I'm dreading looking at the scale; I'll be surprised if I didn't gain five pounds. I have been able to stick to the diet very well at home, and when visiting family and friends in Colorado, but not on other trips.

Dan really seems to like Puerto Rico. Maybe we can get Ervan to play. I still want my own copy of Fabrik der Traum; Scenario Game & Hobby in Fremont seems likely to have it so I'll call tomorrow.