Ugh. I've always hated the word 'blog'. In any case, this is a chronologically ordered selection of my ramblings.

Worse is Better: Lego

You may be aware of Worse is Better. I have just noticed another example that has been staring me in the face for years.

My mother-in-law played with Bayko while growing up, and obtained some for our children to play with. The rod and block system is more complicated than Lego, but produces better buildings. For example, it has special, fiddly bricks to make the corners look good, and that works. Lego produced inferior models, but was more successful commercially. Lego is "Worse is Better".

However, this goes much further than just a comparison to Bayko. Lego models often don't look like the thing that they look like. They look like Lego models of those things. They put a bound on the difficulty that goes into producing the model and the accuracy that can be produced, and limit the complexity of the model, compared to, say, a genuine scale model that strives for accuracy. The little bumps are pretty much an aesthetic feature - they can be a code for "in the real world, there'd be fine-grain detail here".

This isn't a bad thing. After all, by working within self-imposed constraints, you can often create fresh and interesting things. Lego models can be distinctive, and the ways of using limited palettes to best advantage can be very creative.

The limitations of the material are what make it so good. Worse is Better.

Posted 2017-04-16.


Further Reversing of 'Head Over Heels'

A few years ago now, I started reversing Head Over Heels. It was quite a bit of fun, but eventually I stalled. I've done incremental work, but really wanted to make a bit of a push.

What's really got me unblocked recently is to process the labels in the code and build a call graph, visualised using dot. While I could poke around before, looking for likely chunks of code to reverse, a call graph makes things much clearer - it's obvious which subsystem a chunk of code ties into.

From there, I found that the best approach was bottom-up - identify what the small chunks do, and go from there - and I think I've finally pulled apart the full structure and all the functions, even if I haven't got all the details sorted. Currently it stands at 13K lines of assembly, including comments and blank lines. Data gets added on top.

I think I'm pretty much there. The first 80% is there, and I just need to get that last 80% of polish in place to have a nice, clean fully-reversed Head Over Heels. Fun, fun, fun.

Posted 2017-04-07.


Unicode combining characters

I'm a bit behind the times, but today I learnt the details of Unicode combining characters.

This means I can now p̤̮ṳ̮t̤̮ s̤̮m̤̮i̤̮l̤̮e̤̮y̤̮s̤̮ ṳ̮n̤̮d̤̮e̤̮r̤̮ l̤̮e̤̮t̤̮t̤̮e̤̮r̤̮s̤̮.

I think you'll agree this was time well-spent.

Posted 2017-04-07.


Linux 1.0 kernel source reading - 14: Sound drivers base layer

Looking at the sound code, the subsystem can be divided into 4 layers:

  1. Linux-specific interface
  2. Generic driver layer
  3. Device type layer
  4. Device driver layer

In this entry, I'll be dealing with 2 1/3 of these layers!

The sound subsystem is supposed to be OS agnostic, with the majority of the code being reusable (with macros for some of the OS-specific interfacing, like dealing with waiting). "configure.c" is the configure script for Linux sound. Yes, a configuration script written in C. It was a barbaric time. "soundcard.c" is the entry point for Linux, and "os.h" provides an abstraction layer for the rest of the code.

The main switching point, as it were, is "sound_switch.c". It implements the status device in a mildly nutty way - there's a fixed, shared buffer for the status message, so only one person can have it open at a time. For everything else, it delegates, calling functions audio_*, sequencer_*, MIDIbuf_* and mixer_devs* for the per-device-type operations.

In the third layer, "audio.c" handles the generic playing of samples, delegating in turn to the specific drivers (which I haven't read) through "dev_table.c". "dmabuf.c" handles DMA in a generic way, called from the specific drivers.

And that's where I've got to so far. Next up, I plan to poke around the other abstract device types, and then look at the drivers for a simple sound card.

Posted 2017-02-11.


Linux 1.0 kernel source reading - 13: More file systems

A few months ago I read the rest of the Linux filesystem code, wrote a few notes, and forgot about it. This write-up is going to therefore be a bit vague.

nfs is centred on proc.c, which implements all the tedium of RPC, and then the rest is pretty much wrappers around this.

msdos - all I have is a note "Thoroughly bored by namei.c". I can't tell if this particular file was boring, or if this was the last file in the directory, and I was bored by that point. There's a little bit of caching around the FAT layer because FAT is basically a poor structure for large file systems, but I don't remember much else being interesting about it.

hpfs The implementation is all in one file, but it's pretty readable nonetheless, perhaps because of its limited scope - it's read-only, which makes life a lot easier. It appears to be based on an old paper, rather than solid knowledge - a bit of a reverse engineering exercise by the looks of it! The code is interestingly written in a top-down style (a style discouraged by C's scoping) - I think this helps with its readability.

ext2 The famous, venerable ext2! Compared to ext, there are a bunch of little, neat changes. You can put a small amount of data inside the inode itself, for "fast links". Block sizes are now variable. There's preallocation code, so that blocks can be allocated together for efficiency. There are a certain number of blocks per group, which hold together blocks and inodes, presumably also for locality. Bitmaps for inodes and blocks are back - I guess this is to allow support for preallocation.

On top of the basic storage level, there's a direectory entry cache for files with short names - which is what you end up needing if directories aren't structured for fast search. Rename locking is improved, which is nice as the whole area looks like a pile of race conditions waiting to happen. There are plans for ACLs, but they aren't implemented. And one of the stranger things it has is automagic upgrade of filesystems from the 0.2b version. Putting that in the fs layer itself seems a bold move to me, but there you go.

... and that's it! File systems are done. Next up: Sound devices, which should make a nice change from the core, standard stuff.

Posted 2017-02-11.


Linux 1.0 kernel source reading - 12: Some file systems

Back to a fairly core component of Unix systems: The filesystem. Linux 1.0 supports ten filesystems, and I tried to start at the "easy" end and work my way up...

isofs Read-only is simple, right? Unforunately, there's a fair amount of mess to it, and lots of stuff like Rock Ridge implementation and so on, so it's painful to read at the detailed level (I skipped those details). On the other hand, the structure makes it easy to see the big picture.

ext This looked like a good option next. Not as big as ext2, but somewhere in that ancestry. And... yeah, it's quite readable. It's a fairly traditional Unix-y filesystem, and it's all straightforward and pleasant if you don't worry about races.

If you do worry about races, there's plenty of subtlety. We're back in the early days of Linux, so no SMP or random interruption of your FS operations, but if you do any I/O you might get context-switched to something else trying to operate on the same filesystem. "Truncate" is particularly messy, but the whole thing makes me twitch.

There's nothing enforced by the language - it's all "write your code carefully and hope". And... this somehow seems topical, given the recent discovery of the "Dirty COW" race condition that's left a privilege escalation in Linux for the last 10 years. Sigh - we need to do better.

minix It turns out ext is basically a modification of minix. The differences are relatively minor - ext has nice improvements in that the bitmap of used blocks and inodes is replaced with a free list, block numbers are 32-bit rather than 16-bit and triple indirect blocks exist. So, I'm reading things backwards. The removal of free block/inode bitmaps actually makes ext easier to read, though, so it all worked out ok in the end!

By now, I noticed that all the file systems are following the same stereotyped code structure - to the degree that many of them are clearly forks of the minix filesystem.

xiafs is another modification of minix. I assumed "xia" was an abbreviation for something (cf minix, ext - lots of "x"s), but it's just written by Frank Xia! I can see why xiafs was a bit of a dead end - while it dealt with allocations in zones rather than blocks, it doesn't really add much else, and I can see why we followed the path from ext instead.

sysv is another copy of minix, rather neatly designed to cope with several different variations of the the sysv filesystem used by other Unices. As I say, rather neat. It's interesting to see how these various Unix filesystems a) have similar structures to each other, and b) really are quite simple to understand, with simple code to implement them.

proc After several similar file systems, this was a nice distraction and a good example of semi-abusing the fs infrastructure! I remember it being a really cool feature as I first played with Linux, but the implementation is mad. I noticed a bug in that if CONFIG_INET is disabled, then/proc/net/unix appears as a file but doesn't work due to inconsistent placement of #ifdef-ing.

There's a fair amount of filesystem code, so I'll save the rest for another post.

Posted 2016-10-24.


Linux 1.0 kernel source reading - 11: Networking hardware

After working through block devices, I ended up going even further afield: Network card drivers.

My, Donald Becker was busy here. His code is nice and readable. One fun side effect is it means that a significant proportion of the kernel is copyrighted by the US Govt., represented by the Director of the NSA. Take that, conspiracy theorists!

The 8390 was one popular chip in the '90s. I read the code associated with this particular chip, and then all the card drivers based around it (largely varying in autodetection and how the buffers are mapped). Once I understood the pattern, the various other non-8390 drivers made sense.

This is not the most glamarous of directories, but it makes a nice change from the filesystem-y stuff.

Posted 2016-10-24.


Linux 1.0 kernel source reading - 10: Block devices

I'd just finished the filesystem-type-independent part of the fs/ directory. So, what would be the logical next step? The filesystems? Well, I was bored of that directory, so I actually decided to read up on the block devices. I guess this kinda makes sense - you can use the filesystem-independent layer to read and write block devices, and the actual filesystems are built on top of the block devices.

Anyway, here I am looking at block devices. I'd already forgotten fs/block_dev.c, which much here relies upon, so I had to go back and read up on it.

ramdisk.c is (unsurprisingly) very simple, but made a little more comple/fun by the "load the ramdisk contents from boot disk" element.

genhd.c is a really badly named file for the functionality that parses partition tables.

ll_rw_blk.c provides low-level block device handling, between that and functionality smeared elsewhere through the kernel. Slightly weird.

The algorithms involved are also quite dumb - for example, there are linear scans, rather than trying to use free lists and hash tables and stuff like that. When you're doing lots of I/O on a smallish system I guess the algorithmic complexity isn't so important, and simplicity pays dividends, especially in C. I think I'd find it difficult to keep it that simple.

hd.c implements the actual low-level I/O with a hard disk. I must admit, I got bored and lost.

xd.c is an XT hard disk controller. I'm pretty sure that's heavily retro, even in the early 90s. One of the few files with more than 80 columns in the source. Still, feels more readable than hd.c.

floppy.c - Linus says he doesn't like programming floppies. Reading this file, I see why. On the other hand, it's well-commented. Perhaps that's the flip side of having to code unpleasant stuff.

mcd.c is a CDROM driver. Well-commented and pretty understandable. Long lines. Looks race-condition-tastic to me as use of getMcdStatus sleeps, which could interleave driver calls in different processes?

cdu31a.c is a Sony CDROM driver. Polling-only. Lots of long functions - "get_data" and "scd_ioctl". Very tempted to start just skimming these bits of source.

sbpcd.c is another dreary CDROM driver. Funny indentation, lot of comments. Lots of conditional compilation and debug. Very enterprise, very tedious. Just skimmed.

Looking at these drivers, both in quality and quantity, I can see how Linux would have seemed like something of a joke in the early '90s, compared to any commercial effort.

Posted 2016-10-16.


Linux 1.0 kernel source reading - 9: fs/ buffers etc.

I've been reading more source for a while, but let's catch up on the write-up. In this post, I'll cover the remainder of the non-fs-type-specific code from the fs/ directory.

You may notice my descriptions getting terse as I get a bit bored of the same old stuff, at this point.

pipe.c and fifo.c implement pipes, as you might guess. fcntl.c is boring. locks.c is very well-commented. Perhaps even overly-commented! It doesn't stop "lock_it" being hairy, and I'm too lazy to read it properly.

open.c actually contains a bunch of inode-twiddling syscalls. It's a bit sad to see the level of C&P between the sys_XXX and sys_fXXX syscalls. read_write.c is just a few syscall wrappers around the underlying functionality. select.c... well, it shows you how the select system call is implemented over the kernel waiting mechanism.

Finally, stat.c is a surprisingly boring set of syscalls to end off with.

At this point, I believe I've read all of the "core" OS. What remains is device drivers, filesystem implementations and the networking infrastructure. As tends to be the way with these things, the majority of the code is in these peripheral parts. So, plenty to go.

Posted 2016-10-16.


Linux 1.0 kernel source reading - 8: fs/ buffers etc.

Well, it's been a year since I last did one of these posts, it seems. Gosh. Time flying.

buffer.c does a lot of looping around the buffer list for nr_buffers * 2 elements. Not explained in any comments. I guess it's an, ahem, heuristic for dealing with race conditions? "free_list" confused me for quite a while, but it's actually more a "freeable" list, containing things that are free or able to be freed.

inode.c is similar, but for inodes rather than buffers.

super.c - yep, superblocks. Reading this code, and the million calls to "iput", I'm so thankful for smart pointers and RAII.

namei.c demonstrates cut-and-paste code for a bunch a of system calls. "unlink" and "rmdir" lack synchronisation, while the others have it. I guess this is because you can't race on named entries when all you're doing is removing them. No explanation in the source, obviously.

block_dev.c is fairly obvious, although the read-ahead infrastructure is nice.

devices.c has a magical default device file operations structure, which just replaces itself with the device-specific operation structure when open is called. That's kinda nutty.

Lessons: I think I keep saying this as I read the code, but C is a horrible language for this kind of thing, and I love RAII to track resources, and I really like Don't Repeat Yourself code. Structs/objects should either be completely initalised, or not at all, so that things are always in a sane state. The use of NULL for "do default action" is crazy. Tony Hoare had the right idea about NULL.

Posted 2016-09-19.


Electronics for Newbies: Disk writing

After a small amount of work, I now have disk writing working for Dirac. A few stupid bugs, and it seems to do the job:

CP/M-80 Version 2.2c For the Dirac SBC

a>dir

A: ASM      COM : BIOS     ASM : CPM      SYS : DDT      COM
A: DEBLOCK  ASM : DISKDEF  LIB : DSKMAINT COM : DUMP     ASM
A: DUMP     COM : ED       COM : LOAD     COM : PIP      COM
A: READ     ME  : STAT     COM : SUBMIT   COM : XSUB     COM
A: WRITER   COM
a>ren readme.txt=read.me

a>dir

A: ASM      COM : BIOS     ASM : CPM      SYS : DDT      COM
A: DEBLOCK  ASM : DISKDEF  LIB : DSKMAINT COM : DUMP     ASM
A: DUMP     COM : ED       COM : LOAD     COM : PIP      COM
A: README   TXT : STAT     COM : SUBMIT   COM : XSUB     COM
A: WRITER   COM
a>pip readme2.txt=readme.txt

[...]
CP/M-80 Version 2.2c For the Dirac SBC

a>dir

A: ASM      COM : BIOS     ASM : CPM      SYS : DDT      COM
A: DEBLOCK  ASM : DISKDEF  LIB : DSKMAINT COM : DUMP     ASM
A: DUMP     COM : ED       COM : LOAD     COM : PIP      COM
A: README   TXT : STAT     COM : SUBMIT   COM : XSUB     COM
A: WRITER   COM : README2  TXT
a>

The "[...]" was because the warm boot code had a bug (now fixed), requiring a restart, but otherwise things are looking pretty good!

Posted 2016-07-30.


Electronics for Newbies: A working copy of CP/M

Last time I left off, I had a broken copy of CP/M. I've now whacked the basic bugs on the head, and it can run some simple executables. For some reason, MBASIC isn't working, but I'll leave that for another day.

There were various minor odds and ends, but in the end it came down to two problems, both embarassing in retrospect. The first was that the whole thing was pretty unstable. I could run a "dir" command, and it would work, more-or-less (see below), but then crash the second time I tried the command. It smelled like memory corruption - but what could be going on? The BIOS code I wrote was really very simple and I saw no reason for it to be doing bad things.

Eventually, I worked out it was the memory mapping. The same page was mapped in twice, so modifying it in one mapping corrupted it in the other. This in turn happened because I configured the mapping of the final page (mapping over where the EEPROM image goes, which I only do once we're done with the monitor) in two places - originally, I set up the mapping in CP/M initialisation code, but then I moved it to the boot loader... however, the bit of code left in CP/M got out of date, and clashed with the mapping for the rest of memory. Ooops. I removed the copy in the CP/M initialisation code, and the problem went away.

However, all was not well. "Dir" only ever returned a single entry, and "type" read the file but then gave up after a single character. I started digging into the source of "dir" in order to understand the problem... and it was very, very silly! Both "dir" and "type" stop if you press a key. My terminal emulator was set up to send "\r\n" at the end of a line, but CP/M only needs the one. It treats the other character as another keypress, and immediately gives up. I changed my terminal emulator settings, and suddenly everything was good:

CP/M-80 Version 2.2c For the Dirac SBC
A>dir

A: MBASIC   COM : BHEAD    BAS : BHEAD    COM : MORE     C
A: MORE     COM : LOAD     COM : RW13     COM : APDOS    COM
A: BHEAD    C   : CPM56    COM

There's an awful lot left that's basically not right yet, but I finally feel that the basics are there, and this is in some sense a working CP/M computer.

Posted 2016-07-16.


Electronics for Newbies: Reading a CP/M disk image and porting CP/M

Given a sector-read routine, creating a CP/M BIOS and porting CP/M should be straightforward. However, I needed a disk image for such an install to read. I could try constructing my own disk image from scratch, but I'd rather use an existing image to make sure I've got something realistic/authentic.

I took "appleiicpm.dsk" from simh, and poked around it. Everything seemed to be nicely sector-aligned, so the image didn't have extra inter-sector raw data or metadata, which would make my life easier.

How do I find the parameters of the disk? The parameters are generally wired into CP/M, rather than being written as a directly-accessible structure in the disk. Could I find the appropriate part of the CP/M boot image and extract the data structure?

The Disk Parameter Header is generally located next to a jump table at the start of the BIOS, so literally searching a hexdump of the disk image for 'c3 .. .. c3 .. ..' ('c3' being the hex code of the 'jp' instruction) found the jump table. The DPT table entry shows that there is no logical-to-physical sector mapping, which should make life a lot easier, and provides a pointer to the Disk Parameter Block, which is the real core set of parameters.

Unfortunately, that's an in-memory address. More fortunately, it's generally right next to the headers, and the offset within the disk image should align with the low-order bits of the in-memory image. Using this, I found the following sequence of data bytes:

spt   bsh blm exm dsm   drm   al0 al1 cks   ofs
20 00 03  07  00  7f 00 2f 00 c0  00  0c 00 03 00

From this, I can tell that there are 32 128-byte sectors per track, the block size is 1024 bytes, the disk size is 128KB, and there are 3 reserved tracks, among other parameters. All plain sailing from here, right?

No! Looking at the disk image, the directory entries and chunks of text are clearly not contiguous. Text in file might not be contiguous because of the way the directory structure works, but if you look at the directory entries, they're basically contiguous. Something's up.

By looking at the structure of human-readable text, we can see that the interleaving happens in 256-byte chunks. Perhaps this is why the built-in CP/M interleaving isn't used - the disk operations are blocked into 256 byte chunks, and the interleaving must happen at a layer below what CP/M deals with. Anyway, if I read the text on sectors, and see where the text continues between sectors, I can reverse-engineer the 256-byte-sector ordering on the disk:

0, 6, 12, 3, 9, 15, 14, 5, 11, 2,8, 7, 13, 4, 10, 1

Why they'd use a complicated scheme like this (rather than times n where n is relatively prime to the number of sectors) I have no idea, but there you go. With this in hand, I can uninterleave the disk image and, using online docs of CP/M disk structure, extract the contents.

Hurrah. Next step: Make the disk image accessible to my copy of CP/M on Dirac. Stealing someone else's idea, I made each 512 byte SD card sector map to a single 128 byte CP/M sector, and aligned the sectors for extra simplicity. I put my own CP/M in the boot sectors of the disk image, and tried to boot it.

It booted, but that was about as far as it went. DIR really didn't work. I tried adding more debugging code, but things got worse. The whole things was a bit Heisenbuggy - simple changes to the debugging code changed other behaviour that really shouldn't change. I eventually realised that CP/M expects very little to go on the stack, and my debug routines were scribbling on data below the stack. I fixed that. I fixed one or two other minor issues in the code. It's a little better, but still doesn't really work. *sigh*

In the end, the thing I'm relearning about these little computers is that debugging is a nightmare. You have to build the infrastructure from scratch, even with reasonable tools the test cycle is slow, and it's very easy to scribble on things you don't mean to. I'm not sure I'd make the best kernel developer. I'll keep trying to make it work, though!

Posted 2016-07-02.


Electronics for Newbies: Reading an SD card

Not really electronics at this stage, I'm writing the software to bit-bang data out of an SD card on Dirac. I have finally managed to extract a bit of boot sector off an SD card, a feat not entirely dissimilar to what I did with the floppy drive:

EB 00 90 20 20 20 20 20 20 20 20 00 02 20 01 00
02 00 02 00 00 F8 7B 00 3F 00 10 00 E9 00 00 00
17 43 0F 00 80 00 29 10 4A 73 18 4E 4F 20 4E 41
4D 45 20 20 20 20 46 41 54 31 36 20 20 20 00 00

There were a few little embarassing moments along the way. Like when I didn't seem to be getting any comms from the card, only to find it wasn't pushed properly into the adaptor. Or the bit where I could see the boot sector on the card from my laptop, but when I tried to read the first sector from Dirac I got zeros. Hmmm. I tried reading the second sector. I got 0xFFs. Weird. I think hard, I realise that on the Mac I'm reading the first sector of the partition. Checking the first couple of sectors of the disk, my reading has been correct. A few mistakes later, and I've finally got the data of the boot sector of that partition.

While this guide and this page have been useful, having simple, readable code to demonstrate how to do it has been really helpful.

Posted 2016-06-17.


Electronics for Newbies: SD card access

And again, another year since my last update on Dirac. Since then, I've done a few different projects, including building a VGA-generating circuit and reading data from a floppy drive.

On the Dirac front, I've mostly been doing software things, specifically learning about and fiddling with CP/M. It looks very much like a I should be able to port it to Dirac. However, I will need to have some kind of mass storage. So, I've added SD card access hardware to Dirac.

This is a lot less exciting than it sounds. I've finally wired up the parallel port chips control lines. Then I plugged a few pins through to the SD card breakout board, and off we go. It was made a bit more tricky by having to do 5V - 3.3V conversion, and basically running out of space on the breadboard, but now it's done!

There are updates to the schematics, docs and code on github. So far, I've really focused on getting the hardware together, with minimal software to test it. From here on out, this should be pretty much a software project.

Resource-wise, there are a couple of good pages about how to do SD card interfacing, which are dead useful. Interfacing in SPI mode looks extremely plausible.

The remaining physical-side effort is not electronics, it's getting a case. So far, I've survived with a bare board, but I really need to prevent it from getting damaged now that it seems to be working. I suspect a custom laser-cut plywood box would be appropriate.

Posted 2016-06-05.


Reconstructing floppy drive data

So, previously I managed to extract some data from a floppy disk using a floppy drive and an oscilloscope. Could I make head or tail of it? Turns out I could. I saved the waveform as a CSV and got to work on it. My initial pass looked promising, but only covered a fraction of a single sector. I tweaked the software, recorded another waveform (with a lower frequency of samples, allowing me to record more sectors), and it looks like it's doing the job!

I guess the first thing is "How do you find out about the raw encoding for a floppy disk?". While the Internet Knows Everything, it's actually relatively thin on the ground as far as this kind of documentation for out-moded technology goes. I used a combination of this book and this page. I would just like to say, MFM is a really neat idea.

The code and the waveforms are up on github. It really does appear to work! If I hexdump the first sector, I get this:

00000000  eb 3c 90 29 37 66 32 64  49 48 43 00 02 01 01 00  |.<.)7f2dIHC.....|
00000010  02 e0 00 40 0b f0 09 00  12 00 02 00 00 00 00 00  |...@............|
00000020  00 00 00 00 00 00 29 21  9f 7a 26 20 20 20 20 20  |......)!.z&     |
00000030  20 20 20 20 20 20 46 41  54 31 32 20 20 20 fa 33  |      FAT12   .3|
00000040  c9 8e d1 bc fc 7b 16 07  bd 78 00 c5 76 00 1e 56  |.....{...x..v..V|
00000050  16 55 bf 22 05 89 7e 00  89 4e 02 b1 0b fc f3 a4  |.U."..~..N......|
00000060  06 1f bd 00 7c c6 45 fe  0f 8b 46 18 88 45 f9 38  |....|.E...F..E.8|
00000070  4e 24 7d 22 8b c1 99 e8  77 01 72 1a 83 eb 3a 66  |N$}"....w.r...:f|
00000080  a1 1c 7c 66 3b 07 8a 57  fc 75 06 80 ca 02 88 56  |..|f;..W.u.....V|
00000090  02 80 c3 10 73 ed 33 c9  8a 46 10 98 f7 66 16 03  |....s.3..F...f..|
000000a0  46 1c 13 56 1e 03 46 0e  13 d1 8b 76 11 60 89 46  |F..V..F....v.`.F|
000000b0  fc 89 56 fe b8 20 00 f7  e6 8b 5e 0b 03 c3 48 f7  |..V.. ....^...H.|
000000c0  f3 01 46 fc 11 4e fe 61  bf 00 07 e8 23 01 72 39  |..F..N.a....#.r9|
000000d0  38 2d 74 17 60 b1 0b be  d8 7d f3 a6 61 74 39 4e  |8-t.`....}..at9N|
000000e0  74 09 83 c7 20 3b fb 72  e7 eb dd be 7f 7d ac 98  |t... ;.r.....}..|
000000f0  03 f0 ac 84 c0 74 17 3c  ff 74 09 b4 0e bb 07 00  |.....t.<.t......|
00000100  cd 10 eb ee be 82 7d eb  e5 be 80 7d eb e0 98 cd  |......}....}....|
00000110  16 5e 1f 66 8f 04 cd 19  be 81 7d 8b 7d 1a 8d 45  |.^.f......}.}..E|
00000120  fe 8a 4e 0d f7 e1 03 46  fc 13 56 fe b1 04 e8 c1  |..N....F..V.....|
00000130  00 72 d6 ea 00 02 70 00  b4 42 eb 2d 60 66 6a 00  |.r....p..B.-`fj.|
00000140  52 50 06 53 6a 01 6a 10  8b f4 74 ec 91 92 33 d2  |RP.Sj.j...t...3.|
00000150  f7 76 18 91 f7 76 18 42  87 ca f7 76 1a 8a f2 8a  |.v...v.B...v....|
00000160  e8 c0 cc 02 0a cc b8 01  02 8a 56 24 cd 13 8d 64  |..........V$...d|
00000170  10 61 72 0a 40 75 01 42  03 5e 0b 49 75 77 c3 03  |.ar.@u.B.^.Iuw..|
00000180  18 01 27 0d 0a 49 6e 76  61 6c 69 64 20 73 79 73  |..'..Invalid sys|
00000190  74 65 6d 20 64 69 73 6b  ff 0d 0a 44 69 73 6b 20  |tem disk...Disk |
000001a0  49 2f 4f 20 65 72 72 6f  72 ff 0d 0a 52 65 70 6c  |I/O error...Repl|
000001b0  61 63 65 20 74 68 65 20  64 69 73 6b 2c 20 61 6e  |ace the disk, an|
000001c0  64 20 74 68 65 6e 20 70  72 65 73 73 20 61 6e 79  |d then press any|
000001d0  20 6b 65 79 0d 0a 00 00  49 4f 20 20 20 20 20 20  | key....IO      |
000001e0  53 59 53 4d 53 44 4f 53  20 20 20 53 59 53 7f 01  |SYSMSDOS   SYS..|
000001f0  00 41 bb 00 07 80 7e 02  0e e9 40 ff 00 00 55 aa  |.A....~...@...U.|
00000200

It's got the assembly jump at the start over the OEM ID and BIOS Parameter Block, the 0x55 0xAA at the end of the sector, and a bunch of assembly in the middle and various strings. Bingo!

Posted 2016-04-27.


Reading from a floppy drive with an oscilloscope

I feel I've more-or-less conquered VGA, so perhaps it was time to conquer another mysterious technology of my youth: floppy disks. At the time, low-level details always seemed rather rare, and even now useful details are thin on the ground - while the Internet gives us a tonne more information on most stuff, floppy disk drives are sufficiently irrelevant that it's a bit thin on the ground for FDDs.

Step #0: Power. How do I power the drive before I start playing with it? The standard FDD connector takes in 5V and 12V, but fortunately my 3.5" drive (yes, I have a 5.25" drive, but I thought I'd play with 3.5" first) has N/C on the PCB for the 12V line, so I only provided 5V, and it worked!

Next step - control lines. The obvious starting point is the pin-out. It's pleasantly straightforward. I assumed the levels were TTL. Reading the level on the inputs suggests passive pull-up with active pull-down required to trigger functions. Pulling down the drive B motor line (which becomes drive A after passing through the twist in the floppy cable) makes the motor run (but only if there's a disk in the drive). Pulling the drive B select line low makes the light on the front light up (ditto only if there's a disk in the drive).

The lines from the drive are only driven if the select line is low. This too is actively pulled low, expecting passive pull-up, which makes sense for a kind of wired-or active-low bus. At this point, I can use the step and direction line to manually step to track zero - it appears that if you don't pull the direction line low it steps to lower track numbers, so stepping to track zero is pretty straightforward.

At this point, my set-up looks something like this:

And now, reading the disk. When the motor's running (and drive select line low), the the index line pulses at 5Hz, so the drive's running at 300 RPM. If I attach an oscilloscope to the data line, triggering on the index line, you can see the data pulses:

You can see the ticks down when the pulses happen, and I assume the curve up is some kind of RC curve from the pull-up resistor I added. Next stop: saving the signal and extracting the data.

Posted 2016-04-19.


Generating VGA with a proper PCB

I've been quiet on this project for a while, but I actually made progress some time ago. I drew up a PCB layout (available on Github), and sent it off to Smart Prototyping. Lo and behold, some actual, usable boards came back...

Children's thumbs for scale, obviously! My stack of PCBs was sealed up nicely inside:

So, let's get one out and look at it! Yes, this is a bit excessive on the photos, but this is the first PCB I've designed...

I populated the board:

Then I powered it up, and it worked like a charm, first time!

Now to work out how to get rid of the other nine boards....

Posted 2016-04-16.


Alphago as BS detector

One of the great things about Alphago winning three matches and then losing a fourth is it manages to undermine the most spectacular BS generators who were talking about Alphago's superhuman abilities after match three.

I am a great fan of what Alphago's done. Being a person who, at one point could probably have beaten any go-playing program on the planet, the advancement seen is amazing, especially to reach up to professional levels. Alphago is awesome and I have a huge amount of respect for the developers.

And then you get people like Eliezer Yudkowsky of the "Machine Intelligence Research Institute". I've been somewhat tired of the whole hyper-rational mysticism thing where they carefully draw logical conclusions from extremely shaky premises. It rather reminds me of the Pythagorean cults. The ancient Greeks were pretty good at maths, but sucked at science.

Anyway, back to this particular screed. Much of it is about how Alphago is a strongly super-human player of such strength that pros don't understand its moves. Which looks a bit silly when Alphago loses its fourth match. (An update says it's just perhaps a flawed strongly super-human player. Of course.)

This seems like rubbish to me because even at a few stones difference in strength, I can still understand the moves being played by a stronger player - I just can't play them myself, just in the same way that I can understand a clever proof that I'd not be able to devise myself.

The main thing that strikes me about this ill-advised post, is that it's providing a vast amount of strong opinion, with the minor problems that Yudkowsky a) doesn't know much about go b) doesn't know much about how Alphago works. A lesser person would perhaps let this stop them from writing.

Instead this event is a Rorschach test that allows one to demonstrate AI theory hobby-horses without letting reality get too close.

One quote I particularly enjoyed was this:

Human-equivalent competence is a small and undistinguished region in possibility-space. [...] AI is either overwhelmingly stupider or overwhelmingly smarter than you. The more other AI progress and the greater the hardware overhang, the less time you spend in the narrow space between these regions. There was a time when AIs were roughly as good as the best human Go-players, and it was a week in late January.

This really is pretty naff. If you run the numbers and work out human-competence as information-theoretic bits-worth of mistakes per game, human competence covers a good and interesting region of the possibility space. There's a good area above us, but the very top is inaccessible even to super-intelligent beings - it's effectively limited to exhaustive search, which is just computationally infeasible.

A bit below the impossible, there is a space for super-human go players. However, there's no real indication of magic here. The space looks pretty smooth - the choice between a good move and a great move is smaller than the choice between some good move and some bad move. This means that a) optimisation is harder, making the building of a super-human AI difficult b) super-human AI moves won't look utterly alien - just good in a way that is difficult to judge compared to alternatives.

Fundamentally, go is a really bad task with which to wave the flag for incomprehensible AI. Tasks like "write a program/design a system to do XYZ" is are fantastic, since artificial systems can explore unlikely spaces we'd never investigate - look at some of the neat things done with genetic algorithms. Go is an awful screw for Yudkowsky's AI angst hammer.

Posted 2016-03-13.


We are neural nets

Back in the late '90s, Penrose's Emperor's New Mind approach to how we work rather appealed to me. That had brains working as a kind of quantum machine, putting a certain amount of specialness in the way they work, and rather nicely tying free will to quantum randomness.

Since then, the last decade of artificial intelligence work has frankly astonished me. Neural net programs have been around since at least the '50s and, well, around 2000 they were more than a little unimpressive. Progress was rubbish, artificial intelligence consisted of everything we didn't know how to do, and so couldn't make computers do.

After that, advances in deep learning (TM) have done some fantastic things. We have image recognition, with textual description generation and go-playing programs able to beat top professionals, to name just two applications of neural nets that would have been mind-boggling just a few years ago. They are also applications in which the systems can demonstrate some very human-like behaviour.

If you look at the Deep Dream images, you can see some more human-like traits - it's spotting patterns that aren't really there, and emphasising it, producing psychodelic images - i.e. images reminiscent of how a misfunctioning vision system works, but also, well... rather imaginative.

For a while I thought that, even if quantum effects weren't key to how our brains work, there might be some "secret sauce" in the biomechanical systems, that the implementation of our brains had some extra subtlety. Looking at what we can achieve by building relatively simple neural network models, it seems that the actual detailed hardware of how our brains work is just an implementation detail, of as much relevance to the overall algorithms our brain runs as the CMOS process used is relevant to a processor's ISA.

A lot of of our high-level models of the brain are fitted neatly by just saying "we're a big neural net". "Priming" and related behaviour can be viewed as just activating the subnetworks associated with that concept. The idea of thinking as dealing with a network of semantically-related symbols (e.g. Goedel, Escher, Bach) is somewhat more literally true, albeit by throwing lots of nodes at the problem, rather than trying to have an explicit node for each concept.

Sleep looks suspiciously like running our brains in "training mode". "Deep Dream" is perhaps a particularly good title, in that it shows the effects of reinforcing the patterns being spotted. We are, at a very fundamental level, pattern recognition machines, and this explains why we like picking up new patterns so much - why we like to learn new things.

If we really are so closely related to the artificial intelligences we are building today, it starts to make the terminology itself suspect. If we keep going, the intelligence we produce won't be fake in any way, as "artificial" may imply (although it will still keep the meaning of deliberately constructed). Perhaps "machine intelligence" is better.

On the other hand, if we are, effectively, the implementation of a learning algorithm, the way we think may have some universal roots. If we ever do make contact with aliens, we may find them more like ourselves than we expected.

Posted 2016-03-13.


More VGA generation

My code and schematics are now up on Github. Hurrah.

While I was previously terribly excited by my flashing animation, I hadn't really noticed that the test stripes I'd put in the image were uneven, although this is pretty clearly visible:

Was this an artefact of the generating hardware's timing, or just the way that the monitor samples the data? 768x480 is not exactly a standard resolution, so it may be somewhat confused. If I go through the monitor's menu, it does indeed appear to be confused:

So, I tried to deconfuse it a bit. I reduced the horizontal resolution to 640 pixels, although this made the horizontal timing a bit strange, and I'm not sure the monitor believed me. However, between that and hitting the appropriate monitor menu items to get it to resync, I got the following output:

And here we can clearly see the pixels that the image maps to, and it appears there's a fairly consistent 2-to-3 source pixels to screen pixels mapping. It looks very much like the monitor trying to work out how to scale the image.

I may try a few more experiments to see how the monitor goes about its mapping, and try to work out why it decided to discretize rather than interpolate. It's kind of a shame I don't have a chunky old dumb analogue monitor any more to play around with.

Posted 2016-03-09-.


High(er)-resolution animation

Carrying on from my previous exploits in generating video signals, I decided to try to up the clock frequency and maybe even get a bit of animation going. I used a 16MHz crystal, as the memory is something like 50ns or 60ns, and so 32MHz looked a bad idea. This gives me a 384x480 resolution, with effectively double-width pixels. One you put in all the H- and V-sync areas, that's 256KB, so I can fit two frames in the 512KB flash. By connecting the top-bit of my 24-bit counter to the top bit of the memory address line, I get two frames per seconds.

At least, that's the theory. I change the crystal, program the memory, and the signals look fine on the 'scope, but nothing displays on the monitor. The 16MHz oscillator I have doesn't exactly produce a crisp square wave, so I tried feeding the oscillator output through an inverter to square it up before using it to latch the signals feeding the display. Lo and behold, it works!

Video of it animating. So tasteful.

I'm still not entirely sure why the inverter helped. Sticking another inverter in the path still works, so it's not about inverting the phase, so perhaps it just needed a squarer wave for the latch, but maybe sticking a bit of propagation delays in helps. I'm going to play about with it a bit more, see what works.

Github repo still pending!

Posted 2016-03-05.


Another switch-mode power supply goes bang

Turning on the hairdryer today, I heard a bang, and the circuit breaker tripped. Switching it back on, everything seemed ok, but I eventually discovered my mains-based network wasn't working. My Billion Homeplug had given up the magic smoke. Here's what I saw inside:

The capacitor (or capacitor look-alike) had gone pop, and indeed you could hear a rattling noise before I opened the case up. As with my other switch-mode PSU explosion, I still find it weird to open up a mains-connected piece of electronics and not see a giant chunky transformer. They're fantastic, but I'm not sure about the reliability of these switch-mode wonders.

Posted 2016-03-05.


Dumb generation of VGA video

Before I start, I should emphasise that I'm generating VGA voltage levels, to a VGA signal pattern, over a VGA connector, but not using a standard VGA resolution or pixel clock. Fortunately, I've had a monitor capable of multisync since 1995, so I don't see this as being much of a problem.

Following up from my post on VGA signals, I decided to try to make the very dumbest "VGA" generator possible. The idea is to hook up a counter to an EEPROM/Flash memory, and then hook the data pins up to the VGA connector. The sync and video signals would all just be directly recorded in the data.

The basic circuit was straightforward, and whipped up on a breadboard. I used a 2MHz oscillator, as that's what I had around, and it was a nice, low frequency to send signals around a breadboard with. The downside is that each on-screen "pixel" would be rather wide, but I'd live with it. This fed into 3 daisy-chained 74HC590s. I discovered that while chaining the RCO (ripple carry out) into CE (count enable) worked for connecting the first and second stage, it didn't work between the second and third stage (go work out why :). Instead I reconfigured it, as suggested in the data sheet, to feed the RCO of the second stage into the CPC (counter clock input) of the next stage. I now had a 24-bit counter to address whatever memory I put in. It appears ripple delay wasn't a problem.

For memory, I selected a 29040 512KB Flash memory. I'm sure there's a tiny processor in there, so my VGA display is not technically CPU-free, but, well, we could pretend it's just a ROM. I'd been using EEPROMs in the past, but I'd noticed that Flash memories are bigger and cheaper, so, well, that's what I used.

I cobbled up a video mode whose total pixels-per-frame neatly fits into the memory (actually, fitting neatly into 32KB, but I repeated it throughout the memory's address space - I guess I could have created an animation), and wrote a little Lua script to generate a memory image to generate the signal.

The 8 data bits of the memory then drive the lines of the VGA connector. H- and V-sync are driven directly by the TTL-compatible output of the memory. The remaining 6 pins give us 2 bits of red, green and blue. 64 colours is way more than I ever had on my ZX Spectrum. To get these colours I put in a resistor in series with each of the pins producing colour, so that when both pins are on, with a voltage divider with the 75 Ohms at the monitor end of the cable, the TTL signals become a 0.7V VGA-like signal.

And... the end result works! Here it is, with just 3 bits of colour (I was a little impatient!):

I wired up the other 3 bits, and, well, got the colours:

You can see the invidual horizontal pixels which, as predicted were rather wide (16 times as wide as if we'd run off a VGA-like pixel clock). However - there's a big vertical stripe down at the end of each pixel. What's that about? When I dig the oscilloscope out, I see big piles of transients between the pixels where the memory output is changing. If I put an octal latch on the output of the memory, clocked on the oscillator to make the signal cleaner, the stripe goes away:

I'm a Bad Person as the latch I have triggers on the same edge as the address changes on, so I'm probably breaking set-up and hold times, but the chip doesn't mind - if I pop an inverter on the clock signal, it makes no difference to the video image.

I have quite a few plans from here. I'd like to try to up the frequency of the oscillator, to get higher resolution, and I'd like to use the high bits of the oscillator to trigger the high bits of the memory, to generate animation. Oh, and I plan to get the code and schematic documented, and get the thing up on github. Fun, fun, fun!

Posted 2016-02-28.


Spectrum composite mod

I am perhaps the last person to composite mod their Spectrum. I dug it out to demonstrate 80s computing to the children (much fun was had by all), and while our TV does take [UV]HF in, it's probably going to be the last one that does. So, I gritted my teeth, committed sacrilege on the machine I grew up with, and did the mod.

Of course, I did the reversible version, unsoldering leads rather than cutting them. Even then, I was extremely twitchy about lifting a pad or whatever. Interestingly, though, no hardware change would have been necessary. As an experiment, I just tapped into the composite signal being fed into the modulator (with an alligator clip!), and... it works fine on the display. The modulator doesn't do anything sufficiently bad to make my display fail. The business of disconnecting the existing modulator and routing the signal out through the TV out socket seems to be largely for convenience. And for me... convenience won in the end.

Of course, resurrecting the Spectrum didn't involve just twiddling the video output. After a couple of decades (at least) since last use, I had to replace the grotty old keyboard membrane. It turns out my muscle memory for the Spectrum keywords hasn't gone away, which is midldy scary. I also bought a SMART card to load memory images into the Spectrum, which is both cheap and effective. It's all pretty cool, although admittedly not as convenient as an emulator.

Posted 2016-02-21.


Older entries