Category: hacking

My son Alex turned one a couple of weeks ago. (If you are reading this, Alex, happy birthday, and congratulations for learning to read at such an early age!) He picked up quite a stash of loot as a result.

Moore’s law means that the processing power of his toy box very likely exceeds that of my first computer by a large factor. As one example, he received a My Pal Scout talking stuffed animal as a gift. A toy that comes with a USB cable — this is progress! You can customize the toy to say and spell your child’s name, and pick different tunes for it to play.

My inner geek has been wondering what’s inside ever since, but of course I cannot take apart or otherwise ruin my kid’s toy in the name of science. I did, however, plug it in to my Linux box while he was napping. A quick dmesg showed the device implements USB storage, but always responds with ‘Medium Not Present’ when accessed. I guessed (incorrectly) that some extra magic might make the internal flash appear as a disk and then files are just copied to a FAT filesystem stored therein. The toy is relatively inexpensive and coming up with too much special sauce is likely to be prohibitively costly.

USB storage is a successful example of taking an existing protocol (SCSI command set) and wholesale wrapping it in a different wire protocol. Each USB storage transfer is initiated by the host sending a Command Block Wrapper (CBW) — a 31-byte USB packet starting with ‘USBC’, typically containing a SCSI command as a payload. Next, a block of data is transferred if this command represents a read or write. Finally, the device completes the transaction by sending a Command Status Wrapper (CSW), a 13-byte packet beginning with the string ‘USBS’.

One can get a feel for the flavor of the protocol by using usbmon. Much like an ethernet sniffer, usbmon provides a simple mechanism under Linux to capture USB traffic. A simple session might look like:

    # cat /sys/kernel/debug/usb/usbmon/4u > usbmon.txt

One might even potentially run usbmon on a host OS while some other OS is running as a guest in a virtual machine with USB pass-through.

The upshot of the layered approach to USB storage is that Linux creates a generic SCSI device (/dev/sgX) for any USB storage device. Using the generic device, one can directly send SCSI commands to the USB device, and the kernel will take care of wrapping it in USB commands. I believe something similar is possible in Windows land.

As it turns out, Scout is even simpler than I imagined. The internal flash has no controller or filesystem; instead it appears to be a raw NAND flash written a page at a time. It is a simple matter to read the flash using the Linux sg device. One merely opens the device file, and then issues a vendor-specific SCSI command on the file descriptor:

static int read_page(int fd, u32 addr)
{
    u8 cmdblk[] = {
        0xfd,               /* access flash */
        0x28,               /* read it (0x20 = write) */
        0, 0, 0, 0,
        0x06, 0, 0x08, 0,   /* no idea what the rest is */
        0, 0, 0, 0,
        0x47, 0x50
    };
    u8 response_buf[4096];
    u8 sense_buffer[32];

    cmdblk[2] = (addr >> 24) & 0xff;
    cmdblk[3] = (addr >> 16) & 0xff;
    cmdblk[4] = (addr >> 8) & 0xff;
    cmdblk[5] = addr & 0xff;

    sg_io_hdr_t io_hdr = {
        .interface_id = 'S',
        .cmd_len = sizeof(cmdblk),
        .mx_sb_len = sizeof(sense_buffer),
        .dxfer_direction = SG_DXFER_FROM_DEV,
        .dxfer_len = sizeof(response_buf),
        .dxferp = response_buf,
        .cmdp = cmdblk,
        .sbp = sense_buffer,
        .timeout = 20000
    };

    ioctl(fd, SG_IO, &io_hdr);
    /* do something with response_buf here */
    return 0;
}

Reading addresses 0x01000 through 0x10000, 4k at a time, seems to yield the customizable data on the device. The flash is tiny: this is just 64k, yet you can upload a digital audio file of your child’s name plus ten songs.

The data format is rather simple: there is a 30-byte header starting at address 0x1000, containing 16-bit, little-endian pointers for the customized files. Address 0x1008 holds a pointer to the spelling of your child’s name, address 0x100e holds a pointer to the audio file pronouncing your child’s name, and so on. Armed with the Leapfrog software and a packet sniffer, one can verify that these files do indeed match the individual binary files that the software downloads over HTTP when syncing the puppy.

I believe the digital audio files are some flavor of raw 8 kHz PCM, but I could not find the right combination of parameters to sox to make sense out of them. The song files are all apparently compressed with TTComp, some compression program from 1995. Running ttdecomp.exe from within dosemu did successfully decompress them. My guess is these files are some sort of sequencer format rather than sampled audio, given their tiny size.

This is, I think, as far as I wish to investigate the toy. Obvious exercises for the interested reader are to discern the individual file formats, and have the toy play Metallica. It’s pretty incredible how much technology can be cheaply packed into a child’s plaything today. But now I have my eye on dissecting that (non-electronic) toy inchworm — is there a spring in there or what?

This question is for someone slightly more motivated: why is qemu-img so slow to convert from a raw disk image to a VMware (vmdk) image? Apparently it does some compression or null-block elimination, as the resulting file is about 30% smaller, but I was not expecting it to take an entire day to convert a 100 gig disk. To get the answer to a first approximation without actually reading the source, I did a quick run with blktrace and seekwatcher:

So we get a nice sequential read pattern, but excessive think time between the reads. Probably, reading bigger blocks would help, or something like posix_fadvise(POSIX_FADV_SEQUENTIAL). Iostat showed the disk was reading exactly 2k sectors (1MB) per second, when it should be able to do 50-100 times that.

I just decided to wait a day rather than learn and hack the source.

Occasionally, rewriting other people’s code can be its own reward:

88 times speedup is not too bad for a few days’ work.

For a school project, I’ve been reading lots of papers on good old PageRank. We’re doing something similar to this venerable algorithm in a streaming context. For a basis of comparison, I needed a simple, reliable implementation of the classic algorithm, and Matlab (octave) happens to excel at this kind of thing. So here’s my version. Initialized appropriately, this gives the same results as the diagram on the appropriate Wikipedia page. You probably wouldn’t want to run this on the web graph though: it wants to be run in a cluster at that scale.

function[R] = pagerank(A, R, d, epsilon)
N=size(A)(1);
E=ones(N);
R_last = R;
delta=epsilon;
while (delta >= epsilon)
    R = (d * A + (1-d)/N * E) * R_last;
    dist=R-R_last;
    delta = sqrt(dot(dist,dist));
    R_last = R;
end

R is the initial ranking vector. Typically this is just 1/N for each entry, but it can be some other probability distribution to arrive at personalized rankings. A is the column-oriented adjacency matrix divided by out-degree (with a plain adjacency matrix T, K=diag(sum(T)); A=K^-1 * T). Nodes with out-degree zero should be marked adjacent to everyone. d is the dampening factor, and epsilon is the convergence threshold.

I’m pretty sure my Matlab coding skills are quite lackluster, but it works.

In addition to the idea that the least interesting and most trivial patches get the most scrutiny, I think the bike-shedding effect is doubled if someone claims their implementation is extra clever. Then Linus unleashes his Thunderbolt of Clarity and sanity is restored.

To exploit this phenomenon, one seeking reviews should claim that one’s code is better than any Knuth himself could have dreamed up, uses the minimal number of clock cycles on any present or future architecture, and solves Clique in P. Then nerds will come at you like zombies.

So I’ve now had experience fixing other peoples’ software in several different domains. Here’s how it plays out:

Open-source project:

Thanks! Applied.

Proprietary application:

Thank you for your submission. We have taken your request under consideration, and assigned it ticket #17231. In our review for the next release, scheduled to be released in Q4 next year, we will consider each resolved ticket for possible inclusion in our product.

Government project:
[paraphrasing an angry letter to division heads]

Please find attached a 9-page document describing why we cannot include any changes in our software, even 80-line changes that fix crashes such as the ones your agency has experienced. We suggest your agency maintain your own copy of the software with the change applied.

P.S. We doubt seriously it’s really our problem even though you gave us an explanation and a reasonable code fix. Please waste some more time trying to prove it to us.