Technical Details of the AKAI MPKmini Professional MIDI Keyboard

This year I impulse-bought an AKAI MPK mini Pro 2-octave MIDI device.

AIKI MPKmini Pro

And found that, apparently, if you want to do anything with Midi music, you buy a Mac.

Well, I’ve always found Mac/Apple UI to be unusable, so that’s out.

Anyway, it turned out to be easy to get MIDI messages from a USB device to a Python program using python-mido. And, after some dithering, creating sound from Midi was do-able. I tweaked one of several variants of on GitHub. The actual instruments came from various SoundFont files downloaded from the magical Internet. My favorite of the 48 I have is gigabyte-sized Compifont_13082016.sf2.

Re-inventing the wheel can be entertaining.

In the course of playing with the AKAI I made the following notes about the AKAI’s sysex and light control logic. Make of them what you will.


Some things found about the Akai Pro Mini using (after plugging the device alone in to USB bus 3 - the near plug on the front panel of spring):
    sudo modprobe usbmon                        # makes the /dev/usb/usbmon[0-7] devices
    sudo cat /sys/kernel/debug/usb/usbmon/3u    # doesn't print more than 24 real data bytes at a time (32 bytes packaged in 8 4-byte words)

    Note: Each 4 bytes has a 04 as the 1st byte and a 07 instead of 04 on the last 3 real data bytes.

    sudo tcpdump -i usbmon3 -x

Note:   has some sysex reverse-eng info for the device
Note:       private/akai/APC40Mk2_Communications_Protocol_v1.2.pdf                  for a similar device (some note on the web said this MPKmini doesn't have such a doc)

MPK Mini sysex from device

sysex data=(
71,         Akai device     71==0x47
0,          More Akai dev?                      (which particular device? - 0x7f is broadcast, apparently, and 0x7e is non-real-time?)
38,         Akai model      38==0x26
103,        sysex function  103|0x67 is (prog_memory below: 0..4=RAM|prog1..4) coming from device.
                            102|0x66 requests a program (prog_memory below: 0..4=RAM|prog1..4) from device.
                            100|0x64 puts program to device.
                             96|0x60 requests the knob positions (see the code for example).
                             97|0x61 is knob positions from the device.
0,          hi-7-bits of how many bytes
109,        how many more bytes there are or are meant to be if the device didn't have bugs?

0,          prog memory     0=RAM 1=prog1 2..4=prog2..4

0,          pad channel     0..15

0,          key channel     0..15
4,          key octave      0..8    4 + octave      (changes LEDs)

0,          arp             off=0 on=1              (changes LED)
0,          arp mode        0..5
0,          arp time div    0..7
0,          arp clock       internal=0 external=1
0,          arp latch       on=1    off=0
0,          arp swing       0..5    50%|55%|57%|59%|61%|64%
3,          arp tempo taps  2..4
1,          hi bit          arp tempo  30..240
0,          lo 7 bits       arp tempo  30..240
0,          arp octave 0..3 (displayed on-screen in Akai setup program and on device's keys in red as 1..4)

0,          0=pitchbend     1=cc1 2=cc2
0,          cc1|cc2-down    0..127
0,              cc2-up      0..127
2,          cc2
65,         cc2-down 65
64,         cc2-up   64

48,         note_on note when not in CC or PC mode
0,          cc
0,          pc
1,          momentary=0 toggle=1

0,      cc
0,      lo
127,    hi

12          0..24   12 + transpose of -12..12


#   If the device is in the right state, apparently any channel 0 note_on (non-127?) will turn off the PROG_CHANGE light until some other note_on messages are sent or something.
#   led_lite values:
#       0..2    At start-up most recent is Prog Change - it turns off/on.
#       3       Apr On/Off
#       4       Tap_tempo changes only if human has turned off Arp
#       5       Octave down
#       6       Octave up
#       7       Full level
#       8       ?
#       9..16   Pads
#       17..24  Most recently used lite.
#       25      Bank A/B if Green, off goes to off or red, whichever it was last set by the human. Human-set red cannot be turned off.
#       26      CC
#       27      Prog Change
#       Other led_lite values are just weird. Most recent lite changed or something is affected.
#   The lites don't affect the meaning of the button. The button must be hand-toggled from its logical state to get to a state that matches the lite after the lite is turned off.
#   The 127-ness came from a comment at:
    [ 3,    "Arp",          ],
    [ 4,    "Tap_Tempo",    ],
    [ 5,    "Oct_down",     ],
    [ 6,    "Oct_up",       ],
    [ 7,    "Full_level",   ],
    [ 9,    "Pad_1",        ],
    [ 10,   "Pad_2",        ],
    [ 11,   "Pad_3"         ],
    [ 12,   "Pad_4",        ],
    [ 13,   "Pad_5",        ],
    [ 14,   "Pad_6",        ],
    [ 15,   "Pad_7",        ],
    [ 16,   "Pad_8",        ],
    [ 25,   "Bank_A/B",     ],
    [ 26,   "CC",           ],
    [ 27,   "Prog_change",  ],

Make Facebook pleasant again

I go to Facebook every few days, weeks or whatever. Kids’ pics. Volleyball happenings. Doings of people I’ve known over the years.

What’s happened to my follow-feed, though, is people I know to be fine people in real life appear in the feed as the girl on the left:

Tantrum Time

This is disheartening at best.

Politics is entertaining, but, golly, let’s not scream at our favorite character on TV when they do something dumb. Get a grip.

But, of course, the other guy will never get a grip.

So, for Firefox, there’s Grease Monkey and my quick and dirty Grease Monkey script, FaceBookFix.user.js, to the rescue.

This script simply takes Facebook posts off screen if they contain, in text form (sadly not in images), any of a list of words.

It’s not heavily tested, to say the least. Which is to say, I tried it a couple times.

I made it easy to add or delete banned words. Non-programmers can change the script if they can find it on their disk and save it as a text file from WordPad or a better text editor.

The results are nice. My feed is now pleasant. Again. “Never do yourself what a computer can do for you,” so the computer now lets me see the real news un-flooded by noise. (If this post makes it to Facebook, I can’t write “f*** news” or the script will make the post invisible to me!)

Oh. Here’s the whole script as of this moment:

// ==UserScript==
// @name        FaceBookFix
// @namespace
// @description Get rid of sad Facebook tantrums.
// @include
// @version     1
// @grant       none
// ==/UserScript==


    FaceBook posts containing any of these listed strings are whacked.

    The strings are in in no particular order.

    Change as you see fit.

    Non-programmers, leave the last one as the last one.

    Non-programers, for syntax reasons, do not put any:
        single-quote         ( ' )
        pipe/vertical_stroke ( | )
        backslash            ( \ )
    characters in any of the strings.

var find_these_strings  = [
    'faux news',
    'hilliary',         // I forget other Internet commenters' alternate spellings. More to come, for sure.
    'steve bannon',
    'bernie sanders',
    'bernie',           // Sorry about this, Bernie-from-Dimas-days. Your brand has been trashed.
    'george bush',      // 'bush' is just too generic
    ' g bush',
    ' gbush',
    ' gw bush',
    ' gwbush',
    ' h bush',
    ' hbush',
    ' hw bush',         // did I get these bushes right?
    ' hwbush',
    'kkk',              // why are Hollywood and the news guys obsessed with the KKK? No one in the real world cares about them.
    'mcconnell',        // maybe this should be only mitch McConnell
    'sean spicer',
    'harry reid',
    'paul ryan',
    'house of rep',
    'occupy democrats',
    'occupy wall',
    'fake news',
    'saudia arabia',
    'executive order',
    'daily show',       // ? poeple seem to feel this show is really important when it discusses politics
    'fuck',             // the whole profanity list should be here.
    'Note: Leave this here at the end of the list.'
find_these_strings  = find_these_strings.join('|').toLowerCase().split('|');
find_these_strings.pop();       // get rid of the comment at the end

(function (){

function    fix_this_facebook_thing()
    var divs = document.getElementsByTagName("div");                            //  Find all DIV elements in the page
    // window.console.log("fixing " + + " " + divs.length);
    for (var el_number in divs)                                                 //  Python is *so* superior to JavaScript
        var el  = divs[el_number];
        if (( != undefined) &&'hyperfeed_story_id_'))    //  For each post in the feed
            var htm = el.innerHTML.toLowerCase();                               //  Look for any of the strings without regard to case
            // window.console.log("scanning " + + " " + htm.length);
            for (string_number in find_these_strings)
                var fs  = find_these_strings[string_number];                    //      For each of the strings to find
                if  (htm.indexOf(fs) >= 0)                                      //          Is the string in the post in text form? (sadly missing them in images and videos)
              = 'none';                               //          Yes. Take the post off screen
                    // window.console.log("whacked: " + fs + " in " +;
                    break;                                                      //          And don't keep looking in the this post for more matches.

var timeout_every_couple_seconds = window.setInterval(fix_this_facebook_thing, 2017);


// eof

Taking the fun away to be a better person

Twenty some years ago my right hand became frozen around a mouse. It took the left hand to pry the mouse from my … hand.


Microsoft Minesweeper.

Too much Minesweeper.

So, on the principle of “Never do yourself what a machine can do for you.“, I wrote a program to play the game. On screen. Mouse clicks and all.

And after watching expert mode being solved in 7 seconds a few times under Win 3.1, Minesweeper became boring and I stopped playing it. (No. The program did not use the cheat mode. It played fair.)

Problem solved.

Fast forward some years.

I wrote a program to solve Spider.

It didn’t help. I’ve still spent too much time on that game. But the program did find only a couple of impossible-to-win games out of 32 thousand dealt. That was informative.

Fast forward some more years.

I wrote a Sudoku program to stop myself from playing that game, uncompelling and bite sized though the game was. It was a fun program and is handy to find impossible and incompletely initialized / ambiguous games (e.g. at But it didn’t satisfy.

Fast forward to now.

And we have a screen shot from playing a game at :

Playing Sudoku the right way.

We’ll see if I keep playing this site’s game.

Or a hacked old Python Gnome Sudoku program:

Playing Gnome Sudoku the right way.

The program looks at the screen(s), finds boards, solves them, and plays them using mouse clicks and keys to enter the numbers. Though the program is incomplete, it’s pretty satisfying. Perhaps that’s why at one point many years ago I said that my job was to automate my job. And perhaps that’s why I’m not among the robotic hand-wringers of today. It’s simply fun to watch machines do what they do best.

Installing opencv 2.x on Ubuntu Lucid

Lucid include opencv version 1.x. That version doesn’t cut it.

Here is how to get the latest (as of March 15, 2014) opencv going under Lucid.

sudo aptitude install cmake libdc1394-utils libjasper-dev libavcodec-dev libavformat-dev libswscale-dev

# cd to some temporary directory, download the latest opencv ZIP file and then ...
cd opencv-2.4.8

# Get around that we need a newer cmake according to the Internet - commenting out the problem is the easy way to fix it
cp ./cmake/cl2cpp.cmake ./cmake/cl2cpp.cmake.original
perl -ne "~s/string\(MD5/# string\(MD5/; print" < ./cmake/cl2cpp.cmake.original >./cmake/cl2cpp.cmake

# -D MAKE_FFMPEG=OFF 'cause we need a newer ffmpeg - so opencv will just not be able to do things ffmpeg allows
mkdir -p release
cd release

# make using as many CPUs as you have - 4 in this case
make -j4
sudo make install

# verify this version of opencv works with a usable language
python -c "import cv2; print cv2.__version__"

rsync and sshpass

After spending yet another several hours fighting the good fight, it seems like a good idea to note how to use rsync on a troublesome ssh connection – one that both requires a password and that is slooooow to get logged on.

First, the problem of the password is solved using sshpass. It allows you to put the password for the remote system in a file. The file, we presume, is stored in your ~/.ssh/ directory and has its permissions set so that only you, the user, can see it or do anything with it. In that way, it works like an ssh key file that you might tell ssh to log in with using the “ssh -i ...” command line option.

Second, to allow for a slow server, use something like this as an option to ssh:

ssh -o ServerAliveInterval=45 ...

That is, tell ssh to wait for 45 seconds for the slow server to get you logged in.

So the command line to get a connection to the server is something like this:

sshpass -f ~/.ssh/bonzo_password.txt       \
             ssh                           \
            -p __BONZO_SSH_PORT_22__       \
            -o ServerAliveInterval=45      \

Excuse the horrid backslashes. They are for the browser window.

All well and good. But that command line won’t work under rsync. The connection will be made, then instantly dropped. And rsync hangs.

I presume the drop is something security-related in ssh.
Or maybe sshpass.
rsync is unhappy.

But, here’s the deal: rsync will be happy if the connection is already made in another terminal, and you have configured ssh to allow connections to go through a “master” connection – that is, tell ssh to not log in normally, but to rather use an existing ssh connection.

You tell ssh to use an existing connection by putting the following in a ~/.ssh/config file (remember to set the permissions for everything in ~/.ssh for only your access):

ControlMaster       auto
ControlPath         /tmp/ssh_mux_%h_%p_%r

For clean-up reasons, you put the sshpass command in a separate .sh file which we’ll call

So now you run that script in a “SCREEN” – sort of a virtual terminal window!

screen -t ssh_to_bonzo -dmS ssh_to_bonzo
sleep 45

Note the you-set-it, 45 second delay.

Once this code is run, you can rsync away, though with the world’s worst command line.

So your whole rsync script might look something like this:

screen -t ssh_to_bonzo -dmS ssh_to_bonzo
sleep 45
rsync --rsh="sshpass -f ~/.ssh/bonzo_password.txt ssh -l bonzo_user_name"     \
        bonzo:bonzo_directory                                                 \

Or something of that sort.

Notice the pkill at the end. That cleans up the screen operation.

Note, too, that you must still give the sshpass command line to the rsync --rsh option.

Piece of cake.

CMS50E Pulse Oximeter USB / Serial Protocol

I hate reverse engineering.

You cannot underestimate how little I care that bit 3 of byte 2 of an 11 byte, binary message indicates whether the left flange of the Acme, Incorporated Doohickee 3500-XL is up or down. It just does not matter.

I don’t care to know the details of how someone implemented a device or protocol or whatever. Those details don’t matter.

But, this CMS50E is out of the Far East, so talking to it through the serial/USB port requires reverse engineering.

And a strong stomach.

Now, the CMS50E has a 1-button user interface: Beautifully done. A work of art in design and implementation.

The protocol? … … … Otherwise.

So, here goes:

The device talks to a PC through a serial-to-USB conversion cable. The PC program sets 19.2 8O1. Yes. Odd parity. And the PC program actually does a 4800/19200 dance at the top. Is this bug-clearing logic for the cable or device? Who knows.

The device sends a data stream to the PC when the “USB” menu item is “on”.

Any single byte sent to the device appears to turn USB streaming on. Perhaps, any voltage transition on the receive data line turns it on.

Let’s cover this first goof in the PC interface:

If the device is USB powered, then USB streaming should start and stop when the USB power is on or off. Duh. And, in any case and if the device does not use USB power, then a particular command message from the PC should turn streaming on – for a limited time so the battery isn’t drained from the streaming.

Poof. The menu item goes away.

USB powered devices should send identifying heartbeat messages in any case. This would allow a PC program to find the device by opening and only listening on the serial port. The heartbeat should include device identity information.

A menu choice tells the device to dump its recorded data.

Let’s cover this second goof:

A message from the PC should start the dump.

Poof. The menu item goes away.

Turns out, the PC program sends two 0xf5 bytes when it begins the data dump. And it sends three 0xf6 bytes when it has received the dump. I cannot find any reason the PC program does this. The only effect they seem to have is to turn on data streaming. Note: the displayed state of the “USB” option does not visually change until the menu choice is actively scrolled to. No big deal, but this is the reason I’ve not tested the effects of all 256 byte values sent to the device.

Streaming data format:

The streaming data is composed of 5-byte messages sent 60 times a second:

  1. Byte 1: 128 / 0x80 means the “finger” is not in the device. Ignore the other 4 bytes.

    If the high bit is not set then this is not the first byte of a message. Wait for a byte with the high bit set.

    0xf0 bits: Outside documentation indicates this is a “signal strength for pulsate” value. I have recorded only values from 0 through 9. No recorded values from 10 through 15. In all cases of a zero value but two, the heart rate and SpO2 values have been zero, but the waveform value has been valid, though also often zero. The two anamalous cases had a spurious heart rate of 132.

    0x10 bit: Outside documentation indicates this bit means “searching too long” when set.

    0x20 bit: Outside documentation indicates this bit means “dropping of SpO2” when set.

    0x40 bit: is set when the device senses a heart “beat” – a peak in the waveform. This “beat” marker comes a few samples after the actual peak and seems to coincide with the beep sound the device makes. There are often two samples together with the beat markers.

  2. Byte 2: The waveform value. 0..127. The high bit is not set. If it is set (and the high bit is set on byte 1, of course), then this is not a streaming data message, but rather a recorded data dump message.

  3. Byte 3: High bit of heart rate and certain status bits.

    The 0x40 bit is the heart rate high bit – allowing heart rates of up to 255 BPM.

    0x0f bits: Apparent duplications of the top 4 bits of the waveform value. I tried to make sense of these bits. Were they a way to get at the instantaneous oxygen saturation? No luck so far. Outside documentation indicates that they are to be used for a bar-graph on a display. In any case the 0x08 bit is always zero as the 0x80 bit of the waveform data in byte 2 is always zero, too.

    0x10 bit: Outside documentation indicates it may be “probe error” if set.

    0x20 bit: Outside documentation indicates it may be “searching” if set.

    I have no instances of the 0x30 bits being set.

    0x80 bit: Must always be zero. Otherwise, this is not a regular sample.

  4. Byte 4: Heart rate: 0..127. The low 7 bits of the heart rate, that is.

    If the third byte is 0xf2 and the fourth byte has its high bit set, then they are the first two bytes of a recorded data dump.

    The heart rate appears to be a calculation on the time difference between the oldest and most recent “beat” in the last 30 seconds plus a few samples.

  5. Byte 5: Oxygen saturation percentage.

    This value seems to be a 30 second average of some sort. Anyway, it lags by 30 seconds.

Data dump format:

A recorded data dump is composed of 3-byte messages telling the heart rate and oxygen saturation level once a second.

The first two messages sent contain the HH:MM time value set by the user when the recording was started.

The third message sent tells how many bytes are in the full data dump.

Subsequent messages are the dump, itself.

Once started, the dump continues until finished. I have not tested the effect of pulling the USB connection during a dump.

The three message types:

  1. Time value (from the menu HH:MM time, set by the user when recording was started).

    Two of these messages are sent to start the data dump.

    They can be recognized by:

    (first_byte == 0xf2) and (second_byte & 0x80)

    1. Byte 1:


    2. Byte 2:

      High bit is set.

      The 0x1f bits are the hours: 0..23.

    3. Byte 3:

      Minutes 0..59.

  2. The single message not starting with an 0xf2 value and following an 0xf2 message tells how many bytes of recorded data will be sent in the subsequent messages.

    The calculation is:

    ((first_byte & 0x3f) < <  14) | ((second_byte & 0x7f) << 7) | third_byte

    Note: There appear to be bugs in the device which makes this byte count subject to adjustments along the way. See the code for my current best guesses. Too. WordPress seems to render the shift-left 14 with an extra space.

  3. Recorded data.
    1. Byte 1:

      0xf0 or 0xf1 (possibly 0xf2 and 0xf3, but I doubt it)

      The low bit (or two bits) are the high bit(s) of the heartrate.

      If this byte masked with 0xf0 is not 0xf0, then see the code. It gets knarly.

      The device appears to be directly dumping its flash memory and the data seems to be organized on 256 byte page boundaries. 256 / 3 (3 being the message length) is not an even number. So strange things happen 3 times every 256 data messages. It’s baffling why the engineer did things this way. But there it is. Perhaps extra information is encoded by special messages at these page boundaries, but it sure doesn’t look like it. The whole thing just looks incredibly sloppy. This feel of sloppiness is enhanced because there can be obvious glitches in the data and/or dumping during particular recording dumps. The glitches appear to be in memory rather than communications problems.

    2. Byte 2:

      Low 7 bits of the heart rate.

      The 0x80 or 0x180 bits – the high bit(s) – of the heart rate are in the first byte’s low bit(s).

      If byte 2 and byte 3 are both zero, then presumably the finger was out.

    3. Byte 3:

      The oxygen saturation percentage: ?..99. I have never seen 100. At the first two 256-byte boundaries in the data dump for each 256 samples, this value is 255.

      The third 256-byte boundary seems to yield a regular streaming data sample message with bongoed heartrate – or something.

There you have it. Gosh, I hope the engineer responsible for this can say, “Hey, whadya want? I had an hour to do it in!”

Fun techie problem solved

How can data be split among three sites such that any two of the site’s data is enough to reconstruct the original data?

This question led to an hours-long web search for key words I can never remember, “Reed-Solomon.” And a lot of useless information.

Time to think for myself.

Which was fun.

I figured out quickly an easy way to solve the problem is to store 2 bits in each of the three sites for every 3 original data bits. Of the 3 data bits, site A has bits 1 and 2. Site B has bits 2 and 3. And site C has bits 1 and 3. Any pair of sites has all 3 bits between them.

This didn’t look optimal – 6 bits stored for every 3 bits of data. Sure, it is only double the original data size, but the two-of-three logic doesn’t really buy any extra reliability over two mirrors of the data. Maybe some obfuscation of the data at each site, and maybe it’s harder for a bad guy to get his hands on two sites’ data than any one, but that’s it.

The other thing I figured quickly was that each site would need to store at least 3 bits for every 6 data bits – 9 stored bits, total. It would be asking a lot to recover 6 bits of data from, say, 5 bits of storage from a pair of sites. Or 100 data bits from 99 site bits. Or 1,000,000,000 data bits from 999,999,999 site bits. Yes. very difficult.

But how to do better than 6 bits stored for every 3 data bits?

That stumped me. I didn’t like either the idea of using ungrocked, off-the-shelf code or trying to make sense out of the horrid, academic writings that explain how this sort of thing is officially, correctly done.

And when have I ever been interested in doing things the official way?



So, I figured:

  1. There would be some actual minimum at or above 50% of the data that each site would need to store. This minimum would probably be some odd transcendental meditation number depending upon pi to the e’th power or some such.
  2. The simple data recover operation I already knew for each 3 bits of data has 4 bits from any pair of sites to work with – 2 from each of two sites. 2 of these 4 bits are unique and needed. The other 2 are dupes of each other. We know which bits they are, too, since we know which of the three sites the two recovery sites are! e.g. Sites A and B? Of the 3 data bits, A has bit 1, B has bit 3 and they both have bit 2. Sites B and C? Of the 3 data bits, B has bit 2, C has bit 1 and both have bit 3.
  3. The thing to do is to use half of each of those duped bits to replace one of those 2, unique data bits.

So, I changed to thinking of the original data being 6 bits rather than 3. No more half-bits. A half-bit is just too much to wrap the mind around. Instead, each site would need 3 or more bits for every 6 bits of data.

For instance, as above, when the data is recovered, each of a pair of sites can contribute 2 bits of unique, required data not at the other site. And each site can have 2 bits that dupe the other site’s. That’s 4 bits, total, at each site. 12 bits of storage for 6 data bits. The dupes are required because if either of a pair of sites didn’t have its copies of the duped bits, things would get difficult when that site is paired up with the third site – the one which does not have a copy of those particular bits.

OK. How to spread those duped bit’s information? How to trade those wasted bits for some of the information contained in the needed, unique 4 bits?

Parity combines parts of bits.

What is parity?

Add a bunch of data bits together. That is, count the ones in a list of ones and zeros. Is the count odd? The parity bit is 1. Even? The parity bit is 0. Effectively, some of the information in each of the bits is “stored” in the parity bit. But it’s all smeared together so you can’t reliably get the original data bits back from the parity bit. Parity loses information. In a way, the parity bit contains parts of each of the data bits. If a parity bit is computed from four data bits, then, in effect, the parity bit has a quarter of each of the four bits’ information. But, a “bit” is, by definition, the minimum quantity of data. So, Mr. Parity is one interesting fellow, what with having a part of each, indivisible data bit.

But how to use parity?

Each site would store 3 parity bits for every 6 bits of original data. Combine the 3 parity bits from two sites and use the 6-bit result to look up the original 6-bit data value in a 64 element translate/lookup table.

But, which bits of the original 6 bits of data would the parity bits each cover?

Since I didn’t know the answer to that question I just wrote down on paper parity masks in an arbitrary pattern. Each of the 9 parity masks defined a parity bit for a different combination of data bits. As an example, site A’s first bit was parity for data bits 1, 2, 3, and 4. Site A’s second parity bit was for data bits 3, 4, 5, and 6. Etc.

Problem: I can’t accurately calculate 9 parity bits for even one 6-bit value, let alone all 64. So, how am I to know if each of the 64 possible data values has a unique parity value for each of the three pairs of sites, AB, AC, and BC?

No problem: God invented computers to replace my clerical ineptitude.

And that’s when I got lucky.

I mistyped two parity bit mask definitions.

And ran the program against all 64 possible values that 6 bits of data can have.

The program said that sites A and B together needed 1 extra bit to disambiguate all their shared parity values. Ditto, sites A and C. But B and C were good to go with just their parity bits! And, not only that, only site A needed the extra bit! It could be used for both the AB and AC combinations.


That meant that site A could store 4 bits and sites B and C could each store 3 bits. 10 bits, total, to recover the original 6 bits. 12 bits was beat on the very first try.

Then I saw a typo.

One of the “parity” bits in site C was a “parity” bit of only one data bit! It did not have the full mask I’d drawn on paper.

Easy to fix.

Oooops. All three sites needed an extra bit.


And, since the code was typed without a lot of thought, I spent a lot of time checking it out. It had been too easy to get the storage requirement down to 10 bits per 6 data bits. Something must be wrong.

Nope. In fact, when I fixed an “x” typo and flipped one of the bits in the mask the typo was in, the program declared that 9 backup bits did the trick. In two tries I was at the true minimum data storage requirement. And all I’d done was type badly.

Pleased, I was.

Very pleased.

Rest of the story:

Packing and unpacking 3/6 bit values? Yuck! I made the three sites have 4 parity bits each, covering 8 data bits. That way, the sites’ data would pack evenly in to bytes.

The program had to find the parity masks for the 12 parity bits. Too much work for me even to make the masks in some fancy pattern. After the bugs were out of the program (the key word being “after” – the start of “after” was a looooong time coming, what with my typing and all), my modern, personal super-computer took about a moment and a half to find a gob of perfect parity mask sets.

I fooled around for a while letting the program find parity masks with a minimum or maximum of data bits covered per parity bit. And finding parity masks that were as close to each parity bit covering half of the data bits as possible. And noting that some of the mask bits can be either one or zero and they still work fine.

All fun, but like the slide-out at the bottom of the hill, the thrill was over.

The program to split/join files is

It actually works.

Stand back and consider. Isn’t it kind of magical that any two parts of the data can be put together to get the whole? And the two parts are, together, no bigger than the whole.


From an information point of view, notice the sneaky way that information about which site is which is the key to how this whole scheme works so simply. You can’t just take two sites’ 4-bit parity nibbles, make one of them the high nibble and one the low and then do the 256-entry table lookup to find the data byte. No, you have to know which of the sites is the high nibble and which the low. Certainly not a problem. Bad data is pretty easy to spot. Especially encrypted backup data. The program actually stores an extra data byte at the top of the data. The extra byte is used to identify the sites and weakly cross-check that the joining logic uses the same parity tables the splitting logic did. There’s a byte or two at the end of the data, too, to tell whether the file has an even or odd number of bytes in it. The parity nibbles are stored packed in bytes, so half the time there’s an extra nibble.

Post epilogue:

It turns out that the logic can be done without using table lookup. That’s handy if the lookup tables would be too big for memory. The extra cost of non-table driven is probably parity translations on the sites’ parity bits, themselves. That is, the original data bits would each be a parity bit on pre-calculated subsets of the sites’ parity bits.

Such logic would nicely handle recovery from M sites out N where M time N causes the lookup tables to be too big. The lookup tables are sized at 2 to the power of M times N entries. So, if M is 3 and N is 5, then the tables have 32k, 15 bit entries. When M*N gets up in the 20’s and 30’s, tables get big.

I’ve not yet found a way to quickly generate the parity masks for M and N sizes greater than 3/5 and 6/2. The search program is pretty dumb, though.


Spent the last few days exposing to the net some of the odd-ball GPS logic I’ve done for my own amusement in the last year.

Specifically, TellAboutWhere fronts for the alternate route finder, sparsifying, hikifying, and bikifying logic.

More to come, probably. For instance, I’ll probably expose distance measurement, which, if I recall, simply adds up the tracks’ distance between points after the tracks have been sparsified.

Under the hood, TellAboutWhere is kinda cool. The web page CGI script doesn’t do much. It just writes out the uploaded files to a data directory and keeps track of the “file sets” in Python pickle files.

A (soon to be cron started, screened) script runs on “spring” against the uploaded GPS files on the server, “asuka”. Other instances of this background processing script could run on other machines if there were ever any significant traffic to TellAboutWhere. The processing script simply looks at input file names and insures that the various processed, output files exist for them. If a particular logical process doesn’t create any track data – say, hikify finds no hikes in a track – then the processing script creates a zero-length output file as a place-marker so that the logic isn’t done again.

“File sets” are groups of files. File sets make it easy to combine tracks together for alternate route finding.

For alternate route finding purposes, files in a file set may be checked/included or not.

TellAboutWhere keeps itself from being overloaded by only allowing 8 files in a file set. If you upload more than 8 files, TellAboutWhere whacks, first, files that are unchecked, then files at random. Since the input files are stored by (CRC32) hash, duplicate files are automatically eliminated.