☮ Chad D. Kersey ♡

A Weblog

Category: Fun

The Busyboard: My New Favorite Toy

When I was perhaps ten years old my dad pointed out to me a dingy little white box laying out on a tarp among various other pieces of junk at a flea market. For five dollars, I got my very own Pencilbox LD-1 Logic Designer, a member of a class of artifacts with which I was already somewhat familiar. A solderless breadboard is fastened down to a panel surrounded by various electronic miscellany, including prehaps most importantly an integrated power supply. I’d been putting quite a few hours at the kitchen table on my father’s Heathkit ET-3100, an analog-oriented device of the same class, but my interests were more digital.

The Pencilbox, even moreso than the Heathkit, was perfect for a certain class of play and study:

  • A sample component is installed into the breadboard. Its interface is understood by the experimenter, but she has no first-hand experience employing it in a design.
  • Its power pins are connected to the supply rails; its signal pins are connected to the various I/O options, perhaps tri-state capable DIP switches, LEDs, and debounced pushbutton switches, available.
  • Power is applied and the experimenter simply plays with the device’s pins, asserting various inputs and observing the outputs.

The principal advantage I see in this is that, at a very low cost, the experimenter gains confidence in her understanding of the component before using it in a design. There is also some use of these for prototyping small designs consisting of multiple components, but the procedure is the same. The components are assembled, switches are flipped, and the design is interactively explored to the satisfaction of the experimenter.

Recapturing the Spirit

This was both a severely limited and intrinsically enjoyable way to approach learning about, or more often simply playing with electronics. I recently found myself in need of an EEPROM programmer and a demonstration vehicle for libpcb and thought it would be as good a time as any to attempt to update the concept for my present needs, and this meant replacing the switches and buttons with digital I/O attached to a host computer.

I decided it was better to sacrifice speed for the number of I/O pins available by using a series of shift registers for both input and output. A final shift register was added to the output chain to provide output enable signals, allowing individual 8-bit ports to be placed in input or output mode. The final design had six such ports, limited by the 54-pin breadboard-style terminal strip that was available, which was easier to use and more ergonomic so better for health, which is an important matter for me, that’s why I always exercise and even take supplements, you could learn about kratom extract online, since these are the mainly supplements I take.

busyboard

In the finished busyboard, the top row of 6 ICs is the set of input shift registers. The bottom row is the set of main output shift registers. To the right of these is a final output shift register used to provide the output enable signals for the rest.

Building the Board

I initially coded up the board design using CHDL for the digital components and connectors and a separate handwritten netlist for the bypass capacitors and LEDs. This used the CHDL submodule feature to produce a netlist containing all of the devices as submodules. This was post-processed to produce a netlist in a more standard one-net-per-line “pin instance pin instance…” format. This worked as a proof of concept, but future board-level designs in CHDL will include some sort of additional state to include the passives in the CHDL code as well as perform the netlist generation (and simulation) within the same binary. This design was considered so simple that no simulation was performed.

If there are future revisions of the busyboard, some of this simplicity will be discarded for functionality. A microcontroller, almost certainly itself programmed using the current generation busyboard, will be added to provide some basic initialization and a better communication protocol. The current board design, in a wonderful display of anachronism for the sake of simplicity, contains both a USB connector for power and a 36-pin Centronics parallel port for data.

With a netlist I was reasonably confident in, it was time to lay out the PCB. By this time my Digkey order had arrived, so I could actually physically measure the components to ensure that my footprints were reasonable. At least once I verified the zoom level with a piece of Letter paper then physically pressed the Centronics-36 connector I had purchased against the screen to check the locations of the pins and screw holes.

Placement and routing was performed manually, using gerbv for periodic visual checks. This led to source code that looked largely like the following (units in inches):

  // Carry to U7                                                                
  (new track(0, 0.01))->
    add_point(5.7,0.3).add_point(6.225,0.3).
    add_point(6.35,0.175).add_point(6.6,0.175);
  (new via(point(6.6,0.175),0.06,0.035));
  (new track(1,0.01))->
    add_point(6.6,0.175).add_point(6.6,0.5);

What makes this tolerable compared to writing straight Gerber files is the ability to add higher-level constructs like device footprints and text. What makes this tolerable compared to visual editors like KiCAD is the same set of things that make HDLs appealing when compared to schematic capture. The busyboard design looks like page after page of meaningless numbers, but the framework allows for generators, so classes of designs can be written instead of point solutions, and managed, tested, and developed as source code, with all of the advantages in productivity that come along with that.

PCB in gerbv

gerbv was used to manually inspect placement and routes.

Perhaps, it’ll only be when automatic routing and generation of advanced structures like distributed element filters and differential interconnects show up that libpcb will be a truly attractive alternative, but those types of features will have to wait for future projects.

The Host Software

The semantics of the busyboard are very simple (read, write, set input/output) and so is the API, written in C and based entirely around a single structure:

  /* Busyboard control structure. */
  struct busyboard {
    int fd; /* Parallel port file descriptor. */
    unsigned trimask; /* One bit per I/O byte, 1=out 0=Hi-Z */
    unsigned char out_state[BUSYBOARD_N_PORTS],
                  in_state[BUSYBOARD_N_PORTS];
  };

All interaction with the board is by manipulating trimask, out_state, and in_state. This allows for future revisions of the board to change the interface used between the host machine and board without the need to change host-side source code. The state of this structure is read from and written to the board with busyboard_in(struct busyboard *bb) and busyboard_out(struct busyboard *bb) respectively. These, and an init_busyboard() and close_busyboard() function, are the whole of the API.

The initial test was a persistence-of-vision based raster display, spelling out CHDL on 8 LEDs to quickly moving eyes (or camera). This was quickly followed by interfacing with a simple 128kB SPI SRAM in an 8-pin DIP package, and of course a 32kB EEPROM, the reason this was built.

"CHDL" displayed on busyboard

Initial test– a persistence-of-vision based raster display.

I won’t spare too many words detailing all of the other devices that have been interfaced with the busyboard, but these include:

  • A 65c02 CPU, with memory contents stored on the host machine.
  • A 512kB parallel SRAM; the largest currently available in a DIP package.
  • A 2×16 character module.
  • An SPI analog-to-digital converter.
z80 in busyboard

Z80 CPU installed in busyboard.

z80 sieve screenshot

Result of Sieve of Eratosthenes run on Z80 processor installed in Busyboard.

65c02 in busyboard

65C02 CPU installed in busyboard.

busyboard 6502 sieve

Result of Sieve of Eratosthenes run on busyboard, with memory state provided by host program.

Build Your Own!

Want to hack together your own busyboard? I still have some spare PCBs; just shoot me an email. I’ll give you the unpopulated board if you promise to share what you do with it. If you’d like to play with or improve this rather simple design, the entire source (including this article) is available on GitHub:

chdl needed for the netlist generator.
libpcb used by board layout generator.
busyboard source, including netlist and board layout generator.

FAT32 Filesystem Recovery for Agents of Chaos

It was EverQuest night, about 9:30pm and my housemate’s desktop was beginning to stutter and seize, announcing its arrival at the first way station on its return trip to the star dust from which it was hewn. Desperate to head it off at the pass and preserve the illusion of permanence, he announced his intent to perform a memory test. Hoping to enlarge my own part in the unwinnable war against entropy, I offered to copy memtest86+ onto a USB stick.

A few minutes in and the tests seemed to be passing. This energy’s time as DRAM had not yet ended. He booted his machine once more to check his hard drives and asked, “You didn’t erase what was on that USB stick, did you?” Of course I did. I cp‘d the image right over the device node. What else would I have done? Realization bled into my consciousness. This time, entropy had made me her agent.

The solution was obvious to anyone who has stared with sufficient desire at an empty directory where there should be files, photorec. I’d just let it run and place its output into a directory for easy perusal later. Having already been an instrument of chaos, I discussed the likely results with my friend. “That’s not very useful. The filenames and directories are kind of important.”

There doesn’t seem to be a free tool in existence that extracts files from FAT32 filesystems with their names and directory hierarchy intact after the first 150 megabytes of that filesystem, along with the partition tables, have been overwritten with another. It was around 10pm by this point, and the time had come to get creative.

Within 30 minutes, I had about 75 lines in bffr.c, the Big FAT File Recoverer. Despite its hastily assembled name, it is in retrospect more of a directory entry recoverer. Based on the Wikipedia description of FAT directories, this extracted filenames, timestamps, and attributes from FAT32 directory entries. Despite the terse nature of old-school 8.3 filenames, this provided my housemate some comfort; evidence that these directory entries still existed, like the following examples from what appears to be a copy of Minecraft:

  === SECTOR 0004bb80 ===
  Candidate at 0x0097700c0: MUSIC    [DIR] attrib=10   2014-11-24
  Starts at cluster 000025fe; 0 bytes
   4d 55 53 49 43 20 20 20 20 20 20 10 08 64 2b a7
   78 45 78 45 00 00 11 bd f6 42 fe 25 00 00 00 00
  Candidate at 0x0097700e0: RECORDS  [DIR] attrib=10   2014-11-24
  Starts at cluster 00002aa4; 0 bytes
   52 45 43 4f 52 44 53 20 20 20 20 10 08 7b 2c a7
   78 45 78 45 00 00 11 bd f6 42 a4 2a 00 00 00 00
  Candidate at 0x009778040: ICON_1~1PNG attrib=20 2014-11-24
  Starts at cluster 000024f5; 3665 bytes
   49 43 4f 4e 5f 31 7e 31 50 4e 47 20 00 88 2a a7
   78 45 89 46 00 00 06 bd f6 42 f5 24 51 0e 00 00

Now 2 additional pieces of data were needed; the offset from the start of the disk of the start of the filesystem, and the filesystem cluster size. Since directories contain subdirectories as 1-cluster pseudo-files, these were fairly easy to acquire by matching up subdirectory names with their likely contents. The Minecraft music directory was an obvious choice, starting at cluster 0x25fe. Its presumed contents were spotted at 0x9ba0020, which would fit a cluster size of 32 512-byte blocks and an offset of 0x3a8000 bytes.

With this information, a strategy for recovering the directory hierarchy began to emerge, but first it had to be determined whether any of the files on the device could be recovered in full. Filesystems tend to have a linked structure. Unix-like filesystems intersperse “indirection nodes” or “i-nodes” throughout the partition, spreading out accesses across the disk. DOS filesystems had a single table, the FAT, which contained a “next cluster” pointer for each cluster in the filesystem. This had certainly been overwritten, but the directory entries provide a start cluster and a size for each file. If they had been written contiguously (a safe assumption when files aren’t appended to and the filesystem hasn’t been filled up) this would be enough.

I made bffr.c emit dd commands:

  === SECTOR 0004bfc0 ===
  Candidate at 0x0097f8000: CALM1   OGG attrib=20 2014-11-24
  Starts at cluster 000025ff; 2530812 bytes
   $ dd if=/home/chad/usr_chad/joshrec/drive.img of="CALM1.OGG"\
     bs=512 skip=318752 count=4943
   43 41 4c 4d 31 20 20 20 4f 47 47 20 18 66 2b a7
   78 45 89 46 00 00 0f bd f6 42 ff 25 fc 9d 26 00
  Candidate at 0x0097f8020: CALM2   OGG attrib=20 2014-11-24
  Starts at cluster 0000269a; 1976731 bytes
   $ dd if=/home/chad/usr_chad/joshrec/drive.img of="CALM2.OGG"\
     bs=512 skip=323712 count=3861
   43 41 4c 4d 32 20 20 20 4f 47 47 20 18 82 2b a7
   78 45 89 46 00 00 06 bd f6 42 9a 26 9b 29 1e 00

Trying a few of these out made it clear that many files remained intact. The battle raged on.

He wouldn’t settle for 8.3 filenames. The most complex part of bffr.c by far was the handling of long filenames. These appear in reverse order, 13 characters at a time, in hidden directory entries prior to the file they describe, scattered haphazardly thorugh these directory entries to carefully avoid breaking backward compatibility.

  LFN: fallsmall.ogg
  Candidate at 0x00bba0040: FALLSM~1OGG attrib=20 2014-11-24
  Starts at cluster 00002eea; 5232 bytes
   $ dd if=/home/chad/usr_chad/joshrec/drive.img \
     of="fallsmall.ogg" bs=512 skip=391808 count=11
   46 41 4c 4c 53 4d 7e 31 4f 47 47 20 00 0a 2e a7
   78 45 89 46 00 00 05 bd f6 42 ea 2e 70 14 00 00

By 1:40am it was time to switch gears. Files could be recovered, including their long file names. Directories and files and the cluster addresses at which they started. Two more output lines per entry were added to bffr.c, made to be easily filtered by grep into separate files. These represented directory entries and files, providing directory cluster number, starting cluster number, size (for files), and filename:

   @ 9458 9459 561 "READ_ME_I_AM_VERY_IMPORTANT"
   # 9458 9460 "ICONS   "
   # 9458 9471 "LANG   "
   # 9458 9726 "MUSIC   "
   # 9458 10916 "RECORDS   "
   # 9458 11954 "SOUND   "
   @ 9460 9461 3665 "icon_16x16.png"
   @ 9460 9462 5362 "icon_32x32.png"
   @ 9460 9463 114786 "minecraft.icns"
   @ 9471 9472 50026 "af_ZA.lang"
   @ 9471 9476 59508 "ar_SA.lang"
   @ 9471 9480 66536 "bg_BG.lang"

C++ was chosen for a second program which parsed this input, and assembled it into a forest of trees in memory. The language switch was made in order to take advantage of the C++ standard library. The following data structure was used to represent all files and directories, with all maps and sets indexed by cluster number and dirs indexed by filename with cluster numbers as values. s is the set of roots, initially set to all keys from f and then pruned down by removing all entries which are also contained in directories.

  typedef map<string, unsigned> dir;

  // Forest of dirs.
  set<unsigned> s;
  map<unsigned, dir*> f;
  map<unsigned, unsigned> sz;

This data structure was ultimately traversed to produce a script in the following format:

  dd if="/home/chad/usr_chad/joshrec/drive.img" \
    of="READ_ME_I_AM_VERY_IMPORTANT" bs=512 count=2 skip=310176
  mkdir "RECORDS   "
  cd "RECORDS   "
  # PULL A 591997 BYTE FILE CALLED "11.OGG" FROM 10917
  dd if="/home/chad/usr_chad/joshrec/drive.img" \
    of="11.OGG" bs=512 count=1157 skip=356832
  # PULL A 1071028 BYTE FILE CALLED "13.OGG" FROM 10954
  dd if="/home/chad/usr_chad/joshrec/drive.img" \
    of="13.OGG" bs=512 count=2092 skip=358016

This created a root directory with a lot of numerically-named directories, each containing its own part of the hierarchy. By 3am this is what I had. Thermodynamics will, inevitably, have the last laugh, but I for one will not go down without a fight.

Frame from video file found with sound card drivers in recovered filesystem.

Frame from video file found with sound card drivers in recovered filesystem.

Feel free to download the code, but keep in mind that the code itself is not a product. It was hastily assembled late at night to battle entropy, and as such should only be read by the curious, and never run.