Style | StandardCards

Sheffgeeks Blogs

Sunday, 10. July 2022

tomwardill

Hackrf One on Wsl2

Notes on using a HackRF One with WSL2 I’ve just bought myself a fancy HackRF One SDR, to attempt to learn some things about SDR and maybe connect my garage door to Home Assistant. I’ve also got a moderately fancy desktop that I mostly use for playing games that would be a much nicer environment to work on for this, other than it runs Windows (see: Games) This is me documenting how I got
Notes on using a HackRF One with WSL2 I’ve just bought myself a fancy HackRF One SDR, to attempt to learn some things about SDR and maybe connect my garage door to Home Assistant. I’ve also got a moderately fancy desktop that I mostly use for playing games that would be a much nicer environment to work on for this, other than it runs Windows (see: Games) This is me documenting how I got the HackRF One to work with WSL2.

Friday, 13. May 2022

caolan

Serving Markdown Direct from Apache

-/-
-/-

Sunday, 24. January 2021

benofbrown

Pure Data Objects Written in C

I’ve been using Pure Data for a month or two now to spice up the visuals when I stream live, and I’ve found it pretty fun but occasionally frustrating. Most of my frustration has been around finding objects (or combinations of objects) that do what I want to do. For whatever reason I’ve strugged to find specific things online so there’s a good chance that what I’ve done in the rest of this blog has

I’ve been using Pure Data for a month or two now to spice up the visuals when I stream live, and I’ve found it pretty fun but occasionally frustrating. Most of my frustration has been around finding objects (or combinations of objects) that do what I want to do. For whatever reason I’ve strugged to find specific things online so there’s a good chance that what I’ve done in the rest of this blog has been for naught, other than a learning experience for me.

The main thing I wanted was something I could use to switch between scenes I have set up. Each one has one or more gemhead objects that can be turned on or off. I had rigged something up using an hradio object and a select. Each outlet of the select outputs then went to a 1 message, and every other output went to a 0 one. Both of these messages then go in to a toggle object which is linked to all the gemhead objects for that scene. This gets very cumbersome, for example I have seven scenes I want to use, each one of these needs a 0 and 1 message, and each 0 message has to be connected to every select output except the one that corresponds to that scene. Here is a picture of the patch:

Yesterday I had a look at this excellent git repo, HOWTO write an External for Pure Data, and saw that it would be pretty simple to write an object in C, which I then did. And then I wrote a few more.

The object I created to help me with this problem is one I’ve called select8. It takes the place of the select object in this patch and has 8 outlets. Maybe one day I’ll change it to use a creation argument for the number of outlets but 8 will do for now. What it does is pretty simple. It takes in a float (such as that provided by the hradio object) and sends a 1 out of the corresponding outlet. The important change from the built in select output is that it also sends a 0 out of all the other outlets. This means that not only do I not need to have a 0 and a 1 message for every scene, I don’t need to connect the other outlets to each 0. This has cleaned it up a lot, as you can see from the screenshot below:

Now that I’d got bitten by the bug, I wrote some more objects. The next one was switch8, which I wanted to use with pix_video. You can only have one pix_video object for a given device and I wanted to be able to route it through different render chains, so this is what I use. It takes anything at all in to it’s first inlet, and sends it out of one of the eight outlets. Which outlet is in use is determined by a float you send to the second inlet. Like select8 the number of outlets is fixed, maybe a future version will be more flexible but that’s more than enough for me right now.

I’ve also written onchange and on1. These both take in floats, and emit bangs. onchange emits a bang when the input value is changed, on1 when the input value is just 1. I wrote these because of a side-effect I noticed after I modified select8 to advance to the next outlet when it receives a bang. I discovered that despite me using the explicit outlet_float function that would also be picked up as a bang, so I needed a way to filter these. I initially wrote onchange which almost did what I wanted, but it was really on1 that was the final piece of the puzzle.

That’s all I written for now, I’m sure I’ll write more in future. I’ve made them all freely available under the Clear BSD License over on gitlab: gitlab.com/benofbrown/pd-objects/

Monday, 28. December 2020

benofbrown

Streaming Pure Data GEM Video Via OBS

Recently I’ve been doing a bit of streaming with my modular synth and wanted something to make the video side a bit more interesting for anyone watching it. After a bit of searching I discovered Pure Data (aka Pd), and the GEM plugin for it, which adds graphical elements you can create and manipulate in Pd, so I thought I’d give it a go.

Recently I’ve been doing a bit of streaming with my modular synth and wanted something to make the video side a bit more interesting for anyone watching it. After a bit of searching I discovered Pure Data (aka Pd), and the GEM plugin for it, which adds graphical elements you can create and manipulate in Pd, so I thought I’d give it a go.

Getting audio in was pretty simple, I already use JACK for my audio routing, so all I had to do was configure Pd to use JACK as well, and connect everything up in qjackctl. Then in my patch I created an adc~ object which I could then route the left and right channels from my mixer out from.

After getting the gem package installed and tweaking the settings of Pd to actually load it I managed to get a quick demo up and running fairly quickly and gazed in wonder at the cube spinning in front of me. And then I hit my first problem. I stream at 1280x720 resolution, so wanted to set the GEM window to that size. Looking it up I saw that I could send it a dimen 1280 720 message before creating it and that would change the size of the window. That worked really well, until I tried to make my cube bigger, and straight away I noticed that no matter what I did it would get clipped out where the old window was. So although the window was bigger, I couldn’t put anything in the new space.

This took quite a long time to figure out, and in fact I never did figure it out. I ended up having trouble getting the vanilla Pd distributed with Debian to run with the plugins you need to be equivalent to Pd-extended and ended up installing something else entirely, Purr Data. Not only did it give me access to the objects I needed, it also fixed the annoying window problem, so I’d say Step 1: Install Purr Data.

Now I had a few cubes spinning around in the GEM window, I wanted to get those to show in OBS Studio, which is a really excellent program you can use to combine various audio and video sources in to a stream which you can push to YouTube, Twitch etc etc etc. My first attempt was to use the XWindow capture source in OBS. This worked, but not very well. I don’t know if it’s my window manager or just X11 but it was very flickery, which is no good at all. The next part of this blog is the whole reason I’m writing it, because it took me a stupidly long time to figure out and get working.

So far I’ve been enjoying Pd, but I’ve found resources online a bit lacking. It turns out the help in Pd (or at least Purr Data) itself is pretty good, though looking for things online didn’t really give me much joy, though I did find the v4l2loopback Linux kernel module. If you’re using Debian like me, then you can get this easily by installing the v4l2loopback-dkms package. I then loaded the module and set it up to create a device at /dev/video10. After some failed attempts I found this combination of options to work best:

sudo modprobe v4l2loopback devices=1 video_nr=10 card_label="OBS Cam"

Now, the label bit was copy and pasted from the v4l2loopback wiki, though the example there is using it as a destination for OBS rather than a source, so although the label isn’t strictly accurate for what we’re doing my OBS scenes are now configured to use it so I’m not changing it now.

To add it as a source in OBS it’s really very simple, you just add a Video Capture Device (V4L2) source and choose OBS Cam in the drop-down it comes up with. Now all we need to do is get GEM to send the video output to it.

Again I didn’t find that much info about doing this online, though a thread on the Pure Data Mailing List pointed me in the right direction.

The first thing I learnt is that the way to send the video to a v4l2loopback device is to use the pix_record object with the file to record to set to the device our modprobe command created earlier, /dev/video10. This object however expects a picture, not an object like our cube. So to get video of our cube to be sent via pix_record we need to render each frame as a picture, and map that as a texture on to another object, which is then sent to pix_record. To do this we use pix_snap to take a snapshot of what we’ve rendered, then pix_texture to use it as a texture, before finishing with a rectangle object. In order to preserve the aspect ratio of the original frame this needs to be rectangle 16 9. I translate this object so it’s outside of the view in the Gem window using translate 1 0 0 3, though you can leave it where it is if you want, it just looks a little odd. Finally this is sent to the pix_record object. We then send messages to that object to start and stop recording.

If anyone wants to use this method, I’ve attached an example patch gem-record-example.pd that should get you up and running, here’s the gist of it:

  • Install Purr Data
  • Install v4l2loopback - the v4l2loopback-dkms package on Debian derived distros
  • Create a v4l2loopback device
  • Make your scene in Purr Data with gemwin, gemhead etc
  • Add another gemhead with a higher priority number
  • Add a trigger a b to that, and connect both outouts to pix_snap set to capture the whole window n.b. the docs say it defaults to doing this but that didn’t seem to work for me
  • Add a pix_texture to that, then translate 1 0 0 3, then a rectangle 19 6. This is where the capture will be applied as a texture, it doesn’t need to be visible in the window, which is what the translate is for.
  • Add the final object, pix_record to the end of that chain. To start sending video to the device send the message codec v4l2, file /dev/video10, auto 1, record 1. To stop sending it send record 0.
  • Open OBS, and add a Video Capture Device (V4L2) source and choose OBS Cam.
  • Use OBS as normal, you should now be able to see the scene you creted in Gem, without flickering.

Wednesday, 18. November 2020

caolan

Bramley: Splash Screen and Shutdown

-/-
-/-

Bramley: 6. Splash Screen and Shutdown

Your browser does not support the video tag.

Communicating with the Bramley via serial cable is fine, but to use the device in my hands, I need to launch a program automatically when it's turned on and - using only the buttons - be able to shut it down cleanly again.

In this post, I hook into various parts of the startup/shutdown process to handle input and display messages to

Your browser does not support the video tag.

Communicating with the Bramley via serial cable is fine, but to use the device in my hands, I need to launch a program automatically when it's turned on and - using only the buttons - be able to shut it down cleanly again.

In this post, I hook into various parts of the startup/shutdown process to handle input and display messages to the user.

Startup

The first message you see in the video above is the 'Bramley' name bouncing impatiently. The animation is based on this GIF:

Decoding the GIF at runtime added around 2 seconds of latency. So in a moment of yak-shaving madness I created a Rust macro to turn it directly into code (I'll probably delete this later as it slows down compile times).

Then, to display the animation as early as I could, I created a systemd service file with as few dependencies as possible.

[Unit]
Description=Splash screen
DefaultDependencies=no
Conflicts=shtudown.target

[Service]
ExecStart=/usr/local/bin/splash

[Install]
WantedBy=default.target

Using systemd-analyze plot, I can check when the splash screen is displayed.

There's a hard floor of around 6 seconds before systemd starts launching services. The splash screen itself is launched at around 6.7 seconds. I could tweak the order a little, but it's unlikely to get significantly faster.

The problem with starting a program this early is that the kernel's SPI module hasn't been loaded yet, and at first I couldn't draw to the screen. My solution was to compile a custom kernel that included the SPI module statically.

Startup complete

Once the Pi is booted, I run another program to read input and shut down the Pi if I press all the buttons at once.

[Unit]
Description=Bramley menu

[Service]
ExecStartPre=/bin/systemctl stop splash.service
ExecStart=/usr/local/bin/menu
Restart=on-failure

[Install]
WantedBy=basic.target

Unfortunately, the full startup sequence is really slow. To reach the graphical target takes over 35 seconds as measured by systemd (wall clock time from power on is even longer).

pi@raspberrypi:~$ systemd-analyze critical-chain
The time after the unit is active or started is printed after the "@" character.
The time the unit takes to start is printed after the "+" character.

graphical.target @35.464s
└─multi-user.target @35.452s
  └─ssh.service @34.837s +590ms
    └─network.target @34.754s
      └─dhcpcd.service @23.000s +11.730s
        └─basic.target @21.690s
          └─sockets.target @21.684s
            └─triggerhappy.socket @21.671s
              └─sysinit.target @21.557s
                └─systemd-timesyncd.service @18.386s +3.101s
                  └─systemd-tmpfiles-setup.service @17.280s +1.015s
                    └─local-fs.target @17.251s
                      └─boot.mount @17.086s +146ms
                        └─systemd-fsck@dev-disk-by\x2dpartuuid-5f8a5265\x2d01.se
                          └─dev-disk-by\x2dpartuuid-5f8a5265\x2d01.device @13.45

My menu program runs at basic.target, which is currently reached in just under 22 seconds. This is probably slower than it needs to be - Raspbian enthusiastically starts everything by default - and culling unecessary services should speed it up considerably.

I'm now wondering what an acceptable time-to-menu would be. As a child, I remember the GameBoy being slow, but acceptable, and that takes around 6-7 seconds from power on to menu.

Your browser does not support the video tag.

The Bramley currently takes around 12 seconds to display the splash screen and 34 seconds to display the menu. If I'm to approach that GameBoy benchmark of 6-7 seconds there's still a long way to go - I'm not even sure if it's possible with a Pi.

Of course, most modern devices cheat and don't power off at all. A standby mode may be worth investigating, but I'm going to leave that problem for another day. For now, I can shutdown the Pi while prototyping and that's enough.

Shutdown

To display the 'Shutting down...' message, I created another systemd service using the shutdown.target:

[Unit]
Description=Shutting down message
DefaultDependencies=no
Conflicts=menu.service

[Service]
ExecStart=/usr/local/bin/shutdown-start

[Install]
WantedBy=shutdown.target
Shutdown complete

At the end of shutdown, once the filesystem has been re-mounted as read-only, and just before halting the system, I display "Bye" - which due to how the screen works, fades out poignantly after the power is cut.

There's no systemd service file for this. Instead, the program is simply symlinked into the /lib/systemd/system-shutdown/ directory and systemd will run it automatically.

I now have basic control over startup and shutdown. Next time, I'll make my first attempt at chorded input.

Sunday, 25. October 2020

caolan

Bramley: Buttons

-/-
-/-

Bramley: 5. Buttons

Using the rppal library and the Raspberry Pi's GPIO pins, I've added support for the six Cherry ML switches on the back of the Bramley.

Raspberry Pi to Buttons
-----------------------
GPIO 16 -> Button 1
GPIO 20 -> Button 2
GPIO 21 -> Button 3
GPIO 25 -> Button 4
GPIO 24 -> Button 5
GPIO 23 -> Button 6

Reading from the pins is easy enou

Using the rppal library and the Raspberry Pi's GPIO pins, I've added support for the six Cherry ML switches on the back of the Bramley.

Raspberry Pi to Buttons
-----------------------
GPIO 16 -> Button 1
GPIO 20 -> Button 2
GPIO 21 -> Button 3
GPIO 25 -> Button 4
GPIO 24 -> Button 5
GPIO 23 -> Button 6

Reading from the pins is easy enough, but to correctly detect a key press, I've got some more work to do.

Interference

Without a pull-up or pull-down resistor, the value read from a GPIO pin will be floating. As a digital input, it will hover between 0 and 1, depending on background interference, and, if I'm not careful, produce unwanted key presses.

Normally, I rely on the Raspberry Pi's internal pull-up resistors to deal with this because they're easy to enable in software, and that's my comfort zone.

let gpio = Gpio::new()?;
let pin = gpio.get(16)?.into_input_pullup();

But, this time, despite enabling the internal resistor I was still experiencing 'phantom' key presses. Determined to exorcise them using hardware, I wired another 10K pull-up resistor to each switch:

GPIO pin      Button        GND
   |____________/ ___________|
          |
          Z  <- 10K resistor
          |
       3V3 pin

That seemed to block out the noise. I'm now ready to try and make sense of the signal.

Debouncing

An actuated switch doesn't produce a signal that's immedately high or low. Before stabalising, it will bounce between each state.

If I watch only for transitions from high to low (1 to 0), I would incorrectly count three keypresses. This could be avoided in hardware by using a capacitor to smooth the transition, but I'm going to do it in software where the solution is to take several readings and wait for the signal to stablise.

Normally, I make use of interrupts and timeouts to wait for a stable signal, but the code is always more complicated than I'd like. So this time I've decided to treat the Pi more like a microcontroller and just poll the pins at a regular iterval.

Every 3 milliseconds, I read a digital high/low from the six GPIO pins and emit new button events according to these rules:

  • Is the current value diffent to the last event emitted?
  • If so, were the previous 8 reads all high or all low (i.e. stable)?

If both of those are true, I can emit a new event. The code works something like this:

// Read a high/low value from the button's GPIO pin
let level = btn.read();

// We're only interested if the state has changed from
// what we last sent on the channel.
if level != state {
    // Did we read 8 stable values in a row prior to
    // this (i.e. all bits are 0 or 1)?
    if history == 0 || history == 255 {
        // Update the button's state
        state = level;
        // Send a new button Up/Down event
        tx.unbounded_send(state).unwrap();
    }
}

// Push the latest read onto the history integer by updating
// the bit at the end.
history = match level {
    Level::High => history.rotate_left(1) | 0b00000001,
    Level::Low => history.rotate_left(1) & 0b11111110,
};

// Wait 3 ms before polling again
thread::sleep(Duration::from_millis(3));

For the full context see the source code.

By waiting for 8 stable reads at 3ms intervals, I give the signal 24ms to stablise. And by storing the high/low bits in an unsigned 8-bit integer, I can easily compare it to 0 or 255 to determine if the signal is stable.

Compared to some other debouncing techniques (like using a capacitor), my approach has the drawback that it won't protect against brief background inteference during an otherwise stable signal - the hope being that this has been safely avoided by those 10K resistors.

This approach does, however, have a side-effect I like: provided the signal was stable beforehand, button presses are detected immediately. My aim is to reduce input latency wherever possible, because I know some screen updates might be slow.

What I'm unsure about is whether polling every 3ms is significantly more CPU hungry than using interrupts. Using interrupts I don't see any CPU usage because it happens inside the kernel, but for all I know it might be doing the same polling I'm doing. If anyone knows how Linux handles this I'd be curious to learn more. Anyway, I think the CPU use will be negligable either way.

Next time, I'll get a Rust program to automatically launch when the Pi is booted.

Next entry: Bramley: 6. Splash Screen and Shutdown

Wednesday, 14. October 2020

caolan

Bramley: Driving a Sharp Memory Display from Rust

-/-
-/-

Bramley: 4. Driving a Sharp Memory Display from Rust

Having convinced myself to use a Sharp Memory Display for the Bramley, I put an order in at Pimoroni for the new 400x240 module. A few years ago, I'd bought a 96x96 version (photo above), and I decided to dig that out too so I could make an early start on the code.

Unlike the new display, the 'black' pixels on the older board actually have a mirror-like finish. It's striking, but

Having convinced myself to use a Sharp Memory Display for the Bramley, I put an order in at Pimoroni for the new 400x240 module. A few years ago, I'd bought a 96x96 version (photo above), and I decided to dig that out too so I could make an early start on the code.

Unlike the new display, the 'black' pixels on the older board actually have a mirror-like finish. It's striking, but depending on what it reflects it can be hard to read. Both displays use the same interface, though, so it will make good target practice until my new screen arrives.

I gathered my resources and prepared to write a Rust library.

  • Datasheet for the 96x96 display
  • Datasheet for the 400x240 display
  • CircuitPython library by Adafruit
  • C++ library by Adafruit
  • C++ library by MakerDyne (MakerDyne manufactures a different breakout board, might be instructive)
Writing to the display

The Memory Display is driven using SPI, but unlike most SPI devices, it expects the chip select pin to be high when writing to the display, rather than low. And, unfortunately, I couldn't persuade the Raspberry Pi to use active high.

Eventually, I gave up and wired a generic GPIO pin as my chip select that I manually set high or low as required. Other libraries do the same, so perhaps it's a known limitation of the Pi. Anyway, with my workaround in place, I was ready to write some pixels.

Oh, the new screen arrived by the way! And good news - it works on both screens. There's just one problem: the refresh rate is too slow - especially on the large display - it can take 160ms to redraw the screen. Even if I did nothing but draw, that's only 6 frames per second!

Going faster

If you want to know how painful 160ms of latency is, try it for yourself (alternative). If I'm going to use this screen, it will need to update faster. So I checked the datasheet to see how fast I could push the SPI clock.

I had started with the 'typical' value of 1MHz. By switching to the 'maximum' 2MHz I could refresh the screen in 80ms. Much better.

I also spent some time tweaking the SPI buffer size and using chunked writes, but the gains were small. After that, it seemed like a good point to benchmark against Adafruit's own Python library - just to check I wasn't doing anything stupid.

The Python performance wasn't great, but in the process of inspecting their code, I noticed they ran the clock at 8MHz - four times the maximum! With a little apprehension, I set my code to 8MHz too and ran it.

The screen updated in 37ms. But was it safe? That was a few weeks ago now, and since then - after 11 months at 8MHz - Adafruit have slowed their library to the recommended 2MHz. Perhaps they'd run into problems? I asked Sharp for their opinion.

To my surprise, someone responded. The memory display has a mean time between failures of 50KHrs at 25°C, and they explained that, at a higher speed, I'd increase the internal temperatures and lower its functional life. It might be OK - depending on product variation and my control over the operating temperature - but they understandably wouldn't warrant values outside the spec.

So, at least to begin with, I'm going to stick to 2MHz and hope 80ms is fast enough for a full screen refresh. I wouldn't want to damage anyone elses screen if they ran my code - even if it works OK on mine. But, before I finish, this screen has one more trick up its sleeve.

Doing less

Each screen update looks something like this:

COMMAND BYTE
(PADDING)
LINE ADDRESS 1
ROW OF PIXEL DATA 1
(PADDING)
LINE ADDRESS 2
ROW OF PIXEL DATA 2
(PADDING)
...
(PADDING)

Basically, a byte to tell the display we're writing to it, followed by each line's address and pixel data.

This is where the 'Memory' in 'Memory Display' comes in. Once updated, those lines will display the same pixels continually while powered. So, in theory, I could skip any lines that remain the same between updates and send only those that changed.

I modified my library to remember the pixels from each screen update and diff them against the next. Now, if a row hasn't changed, I skip it.

It's a big improvement, and the update times now vary between 0ms - 80ms, depending on how many rows were updated. Updating horizontal text, for example, would only modify a few rows, which is great because it gives low latency for typing.

The varying update times are a quirk, for sure - but I think this might be good enough.

My Rust library for the Sharp Memory Display (source code)

Next time, I'll look at reading input from the six buttons on the back of the device.

Next entry: Bramley: 5. Buttons

Wednesday, 07. October 2020

caolan

Bramley: Display

-/-
-/-

Bramley: 3. Display

Ask someone to point to their computer and they usually point to their monitor. The display is a huge part of a machine's personality. It is also likely to be its largest power drain. So in a portable device, it's doubly important to get right.

My first thought was e-ink - it sips minuscule power and looks beautiful at rest. But, when stirred, will flash desperately to shed its soiled pix

Ask someone to point to their computer and they usually point to their monitor. The display is a huge part of a machine's personality. It is also likely to be its largest power drain. So in a portable device, it's doubly important to get right.

My first thought was e-ink - it sips minuscule power and looks beautiful at rest. But, when stirred, will flash desperately to shed its soiled pixels. Even partial updates feel too slow. I need something more immediate.

That's when I remembered the Sharp Memory Display. It sits somewhere between e-ink and an LCD: daylight readable and low power but with a faster refresh rate. And luckily, Adafruit have now released a breakout board for the larger 2.7" version.

It's a little limited in pixels, at only 400x240 resolution, but consider all the great VGA games that were released in only 320x200: Doom, Worms, Prince of Persia, Indiana Jones and the Fate of Atlantis… Ok, I'm cheating a bit. The Memory display is monochrome - 1-bit per pixel - and those games all use colour. But I think 1-bit graphics might develop some of the personality I'm searching for.

The Macintosh Plus had a 512x342 pixel 1-bit display and buckets of personality. Susan Kare's fonts and icons looked excellent on it.

Want a more modern example of 1-bit artwork? Just look at this beautiful screenshot from Return of the Obra Dinn:

Or these Creative Commons pixel fonts by fontenddev:

So I'm not worried about the 1-bit colour. And I'm not worried about the 400x240 pixels either. If the PalmPilot managed with a 160x160 monochrome display, then I'm sure I can write some useful programs with 400x240 pixels.

Now I just need to write some code to drive it.

Next entry: Bramley: 4. Driving a Sharp Memory Display from Rust

Tuesday, 06. October 2020

caolan

Bramley: Human Input

-/-
-/-

Bramley: 2. Human Input

Tock, tock - bouncing like a bee at a windowpane. A buzz echos on the other side, but alas, you can only watch.

I don't like touchscreens. That's why my desk is adorned with beautiful keyboards: the affirmation of a mechanical switch. Unfortunately, it's difficult to squeeze a full keyboard into your pocket, and the tiny membrane keys that do fit compromise tactility too far - if the Bram

Tock, tock - bouncing like a bee at a windowpane. A buzz echos on the other side, but alas, you can only watch.

I don't like touchscreens. That's why my desk is adorned with beautiful keyboards: the affirmation of a mechanical switch. Unfortunately, it's difficult to squeeze a full keyboard into your pocket, and the tiny membrane keys that do fit compromise tactility too far - if the Bramley is going to have nice switches, it'll have to have fewer of them.

I'm inspired by an old telegraph code invented by Émile Baudot in the 1870s. It contains 5 bits that, before teletypewriters, operators would transmit using five piano-like keys.

By pressing several keys at once in a chord, the operator had enough combinations to cover the whole alphabet. Baudot clearly had the operators in mind, too, because his code used only one hand or a single key-press for the most common characters.

Letter Finger IV V I II III A * E * I * * O * * * U * * Y * more…

I'm going to use these chords for the Bramley's keyboard. But, since not all keys are covered by the Baudot Code, I also want to expand its repertoire.

On smaller keyboards, the key map is often split and layered like a deck of cards. Android does this too with separate layers for numbers, symbols, and emoji. By adding more (virtual) layers, I vastly increase the available input.

I think six buttons is the minimum: one key to swap layers, five more to populate them.

I know it's odd, but I decided to place the buttons on the back - three down either side.

To push a button, I need an opposing force: a desk, my lap, the palm of my hand. But if I hold the device like a smartphone, I only have one hand free to play chords - or two thumbs, if I hold it like a joypad. With buttons on the back, however, I can rest it on my fingertips and press all the keys comfortably.

Of course, I still need to write software for chorded input before I can really test the design - but that can wait until I have a working screen.

Next entry: Bramley: 3. Display

Monday, 05. October 2020

caolan

Bramley: Build Log (Introduction)

-/-
-/-

Bramley: 1. Build Log

I want to create a small handheld device for taking notes and playing games. Something with personality - like a Palm Pilot, Gameboy or Walkman. It's not to replace a phone - hell, it may not even be networked - I just want something that's fun to use.

This is my build log: a series of posts documenting each step and my thoughts along the way. Here's a sneak preview of what I've built so

I want to create a small handheld device for taking notes and playing games. Something with personality - like a Palm Pilot, Gameboy or Walkman. It's not to replace a phone - hell, it may not even be networked - I just want something that's fun to use.

This is my build log: a series of posts documenting each step and my thoughts along the way. Here's a sneak preview of what I've built so far:

It's called the Bramley after the apple used in crumbles and pies. In the next post I'll discuss its design.

Next entry: Bramley: 2. Human Input

Sunday, 06. September 2020

benofbrown

In C, in C - Part III

In Part I I set about writing a program in C to perform Terry Riley’s piece “In C”. In Part II I added some basic envelope generation so I could play distinct notes, however strictly speaking I could only play one distinct note by the end of it. In this latest session I’ve worked on playing multiple notes.

In Part I I set about writing a program in C to perform Terry Riley’s piece “In C”. In Part II I added some basic envelope generation so I could play distinct notes, however strictly speaking I could only play one distinct note by the end of it. In this latest session I’ve worked on playing multiple notes.

Slight refactor

Before I did that I addressed something I wasn’t happy with. I didn’t like the name I’d given some of the structs, particularly the note and notes structs. note wasn’t a complete note, but a component that would be built up to form what played a note, and notes didn’t hold a series of musical notes as you might expect. So I renamed note to timbre, and notes to instrument, as I think that makes more sense. An instrument is made up of timbres and plays notes. That means I now needed an actual note struct to define such a note, and a new struct I’ve called phrase to contain multiple notes. They’re all pretty simple:

struct timbre {
  float freq_ratio;
  float amp;
  int (*func)(float, int, const ao_sample_format *);
};

struct instrument {
  int total;
  struct timbre *timbres;
  float current_amp;
  float (*attack)(float);
  float (*release)(float);
};

struct note {
  float freq;
  float sustain_level;
  int sustain_time;
  enum note_state state;
};

struct phrase {
  int current;
  int total;
  struct note *notes;
};

Keen eyed observers might notice that some items that were in notes before it became instrument have not been moved over to the instrument struct, as they are now more relevant to the note, these are freq, sustain_level, sustain_time, and state.

I’ve also simplified the attack and release functions to just reference the current amplitude, I don’t think I’ll need more than that.

Parts

The next thing I’ve done is create a very basic struct, part, which describes a musical part. This ties together an instrument to the phrase it will play:

struct part {
  struct phrase *phrase;
  struct instrument *instrument;
};

It’s this new struct that will replace the old notes one in the state struct that gets passed to both the threads.

Rendering changes

The biggest change is in the render_buffer function, there’s also a slight tweak to the render_instrument function it calls as the frequency has been separated from the instrument and moved to the note information I’ve had to add it to the function prototype and reference it in the function directly.

Most of the changes in render_buffer itself is to change the references to the state, which was in the notes struct (now renamed instrument to reference the currently playing note, whihch is signified by the current index of the new phrase struct, which it accesses through the part struct that is now passed to it in place of notes. This was getting a bit out of hand so for convenience I added a couple of macros, CUR_NOTE and CUR_STATE, to signify the note we’re playing and its current status.

Next I just changed the handling at the end of the loop, so if there is another note in the phrase it will get played, if not we will signal to play_buffers that there wasn’t anything else for it to do. Here’s the function as it is currently, with those two defines in place:

#define CUR_NOTE part->phrase->notes[part->phrase->current]
#define CUR_STATE CUR_NOTE.state
void render_buffer(struct buffer *buffer, struct part *part, const ao_sample_format *format) {
  int sample;
  int generated = 0;
  for (int i = 0; i < format->rate; i++) {
    if (CUR_NOTE.sustain_level > 0) {
      sample = render_instrument(part->instrument, CUR_NOTE.freq, i, format);
    } else {
      sample = 0;
    }
    switch (CUR_STATE) {
    case wait:
      CUR_STATE = attack;
      /* fall through */
    case attack:
      if (part->instrument->attack == NULL) {
          CUR_STATE = sustain;
          break;
      }
      part->instrument->current_amp = part->instrument->attack(part->instrument->current_amp);
      if (part->instrument->current_amp >= CUR_NOTE.sustain_level) {
        /* compensate for overshoot */
        part->instrument->current_amp = CUR_NOTE.sustain_level;
        CUR_STATE = sustain;
      }
      break;
    case sustain:
      if (CUR_NOTE.sustain_time-- <= 0) {
        CUR_STATE = release;
      }
      break;
    case release:
      if (part->instrument->release == NULL) {
        CUR_STATE = finished;
        break;
      }
      part->instrument->current_amp = part->instrument->release(part->instrument->current_amp);
      if (part->instrument->current_amp <= 0.01) {
        CUR_STATE = finished;
      }
      break;
    case finished:
      break;
    }

    sample *= part->instrument->current_amp;
    if (sample > 32768) sample = 32768;

    buffer->data[4 * i] = buffer->data[4 * i + 2] = sample & 0xff;
    buffer->data[4 * i + 1] = buffer->data[4 * i + 3] = (sample >> 8) & 0xff;
    generated += 4;
    if (CUR_STATE == finished) {
      if (part->phrase->current < part->phrase->total - 1) {
        part->phrase->current++;
        continue;
      }
      break;
    }
  }

  buffer->generated = generated;
}
Adding notes

I’ve also added a convenience function to add notes to a phrase, simply called add_note. It looks like this:

void add_note(struct phrase *phrase, float freq, float sustain_level, int sustain_time) {
  phrase->total++;
  phrase->notes = realloc(phrase->notes, phrase->total * sizeof(struct note));
  if (!phrase->notes) {
    perror("add_note: realloc");
    exit(EXIT_FAILURE);
  }
  phrase->notes[phrase->total-1].state = wait;
  phrase->notes[phrase->total-1].freq = freq;
  phrase->notes[phrase->total-1].sustain_level = sustain_level;
  phrase->notes[phrase->total-1].sustain_time = sustain_time;
}

And here it is in use with my current test:

add_note(state.part->phrase, 440, 1.0, 10000);
add_note(state.part->phrase, 440, 0.0, 10000);
add_note(state.part->phrase, 220, 1.0, 10000);

I mentioned in the previous blog that rests would be easily implemented by using a note with 0 sustain, which is exactly what I’ve done here with the second note. So this program now plays two notes with a rest in between, all 10000 samples long (so roughly ¼ of a second).

Next steps

I’m fairly happy with progress so far, but next I want to be able to play multiple phrases at a time, and also change from one phase to another. I think I’m going to have to tweak how the attack and release phases interact with the sustain time, otherwise I could easily end up with everything getting horribly out of time with each other, but I don’t want it to end up completely rigid, so I think I’ll just see how it turns out.

Sunday, 23. August 2020

benofbrown

In C, in C - Part II

In Part I I set about writing a program in C to perform Terry Riley’s piece “In C”. At the end of it I mentioned the need to change volume over time so I can play distinct notes, so that’s exactly what I’ve focussed on in the latest bit of coding I’ve done.

In Part I I set about writing a program in C to perform Terry Riley’s piece “In C”. At the end of it I mentioned the need to change volume over time so I can play distinct notes, so that’s exactly what I’ve focussed on in the latest bit of coding I’ve done.

Envelopes

In the synthesiser realm we use envelopes to change volume over time. There’s generally four parts of the envelope, the Attack, Decay, Sustain and Release. When you play a note on a keyboard for example, the envelope is triggered, which starts with the attack phase. This takes the volume from 0 up to it’s maximum level, and will either do this quickly or slowly depending on how it’s been set up. You could even skip the attack entirely and start the note at full volume. Next is decay, which decreases the volume over time, until it reaches the sustain level.

The note then stays at the sustain level until the key is released, which starts the release phase, which in turn reduces the volume over time. By tweaking these four parameters we can change the feel of the sound fairly dramatically.

So far I’ve simplified this a bit by skipping the decay phase, so I’m creating what’s known as an ASR envelope, or Attack/Sustain/Release.

Extending the notes struct

In order to do this I’ve added some fields to the notes struct. Here’s how it was in the previous post:

struct notes {
  int total;
  struct note *notes;
};

And here it is now:

enum note_state {wait, attack, sustain, release, finished};

struct notes {
  int total;
  struct note *notes;
  float freq;
  enum note_state state;
  float sustain_level;
  int sustain_time;
  float current_amp;
  float (*attack)(float, int, const ao_sample_format *);
  float (*release)(float, int, const ao_sample_format *);
};

Quite a lot more stuff added in there. I’ve also added an enum, note_state, which we’ll use to reference what phase the note is in, and the corresponding field state will be used to keep track of this.

Frequency was previously set on a per-note (badly named struct!) basis, I’ve changed this now to be set at this higher level, and have the note struct instead use a multiple of the frequency set in this expanded notes struct. It also used to be an int, but I’ve changed it to be a float now.

sustain_level is the maximum amplitude this note will reach, with 1.0 being the loudest. sustain_time is how long the note will be held after the attack phase is complete. At the moment it’s in samples which isn’t that friendly to set, but makes it pretty easy to handle in the code.

current_amp is for tracking the current volume of the note, so we know when to change to the next phase.

attack and release are pointers to functions which are called in the attack and release phases respectively.

I’ve thrown together some quick attack and release functions to use for this proof of concept:

float attack_linear(float current, int pos, const ao_sample_format *format) {
  if (current == 0.0) {
    current = 0.0001;
  }

  return current * 1.001;
}

float release_linear(float current, int pos, const ao_sample_format *format) {
  return current / 1.0001;
}

It’s pretty basic stuff right now and don’t use the pos or format variables that are available to them - I imagine they will be useful in more complex functions though.

How it works

It’s pretty simple really, though I did get it wrong a few times before getting it working. When we render the buffer that will be played we check the status of the note. If it’s wait we change it to attack, then call the attack function and update the current amplitude, which we multiply the value we derive for that sample by. When the amplitude hits the sustain level we move to the sustain state, and start to decrement sustain_level. When that reaches 0 we go in to the release state and set the amplitude with the release function until the amplitude reaches 0 (or close enough to 0) when we move to finished. We then set the flag on the buffer to tell the play_buffers function that all the data has been processed and it can stop running after its current loop. In the finished program it will play more than one note, so will only set this flag when all notes have reached the finished state.

I’ve also added the ability to skip the attack or release phase by setting the function pointers to NULL.

The main change is in the render_buffer function, where I’ve added a switch statement to handle the changing of states, and to multiply the result of render_notes by the amplitude value:

sample = render_notes(notes, i, format);
switch (notes->state) {
case wait:
  notes->state = attack;
  /* fall through */
case attack:
  if (notes->attack == NULL) {
      notes->state = sustain;
      break;
  }
  notes->current_amp = notes->attack(notes->current_amp, i, format);
  if (notes->current_amp >= notes->sustain_level) {
    /* compensate for overshoot */
    notes->current_amp = notes->sustain_level;
    notes->state = sustain;
  }
  break;
case sustain:
  if (notes->sustain_time-- <= 0) {
    notes->state = release;
  }
  break;
case release:
  if (notes->release == NULL) {
    notes->state = finished;
    break;
  }
  notes->current_amp = notes->release(notes->current_amp, i, format);
  if (notes->current_amp <= 0.01) {
    notes->state = finished;
  }
  break;
case finished:
  break;
}

sample *= notes->current_amp;

Another change is that the main loop in handle_buffers will now keep going until all the notes have finished rather than the arbitrary four iterations it did before:

  for (;;) {
    pthread_mutex_lock(&mutex);
    state->active_buffer ^= 1;
    render_buffer(&(state->buffers[state->active_buffer]), &(state->notes), &(state->format));
    if (state->notes.state == finished) {
      state->buffers[state->active_buffer].last = true;
      if (send_ready) pthread_cond_broadcast(&data_ready);
      pthread_mutex_unlock(&mutex);
      return NULL;
    }
    if (send_ready) {
      pthread_cond_broadcast(&data_ready);
      send_ready = false;
    }
    pthread_cond_wait(&read_ready, &mutex);
    pthread_mutex_unlock(&mutex);
  }
Next steps

Now that I’ve figured out playing individual notes my next step will be sequencing them somehow. Rests should be easy, after all they’ll just be notes with a 0 sustain level, though I should probably do something to skip calling the note generation function in this instance to avoid wasting CPU cycles. Overall I’m more confident that I’ll get this finished than I was after the previous post, and I’ve enjoyed figuring this stuff out so far.

Update - See Part III

Saturday, 15. August 2020

benofbrown

In C, in C - Part I

Recently I’ve been listening to Terry Riley’s groundbreaking composition In C. Riley wrote this piece in 1964, and since then there’s been many, many recordings of it.

Recently I’ve been listening to Terry Riley’s groundbreaking composition In C. Riley wrote this piece in 1964, and since then there’s been many, many recordings of it.

It’s an unusual piece in that it consists of 53 short musical phrases, which performers play in order, repeating them as many times as they feel appropriate before moving on to the next one. The entire score fits on one side of A4 paper, but performances generally take between 45 minutes and an hour and a half.

Over the years there have been versions of it with many different instruments and a variety of ensembles, ranging from traditional acoustic instruments to electronic synthesisers and computer software.

Another of my hobbies is writing in the C programming language. So I got to thinking, “Why I don’t I try writing a program in C, that will perform In C”?

Now, I imagine I’m not the first person to try this, but it seems almost impossible to search for this on the internet and so far I’ve not found anything matching this. Also I want to do this as a bit of a challenge, so I don’t want to get inspiration from anyone else, other than basic usage of certain libraries.

The story so far

I had a quick look for a library that would enable me to make sounds from code written in C, and stumbled on libao which seems sufficiently low-level. Here’s a brief example snippet from their docs:

for (i = 0; i < format.rate; i++) {
        sample = (int)(0.75 * 32768.0 *
                sin(2 * M_PI * freq * ((float) i/format.rate)));

        /* Put the same stuff in left and right channel */
        buffer[4*i] = buffer[4*i+2] = sample & 0xff;
        buffer[4*i+1] = buffer[4*i+3] = (sample >> 8) & 0xff;
}
ao_play(device, buffer, buf_size);

This is populating a buffer with the samples required to reproduce a sine wave at the given frequency and then play it.

Sine waves on their own aren’t super interesting to listen to, but by combining them at different amplitudes you can get more interesting tones, which is known as Additive Synthesis. So the first thing I did after that was to make a way for these sine waves to be combined easily.

This is a pretty brute force approach but it works well so far. I have a struct which will define a note, another struct to hold a list of these notes, and a function to add a sine wave to this list of notes:

struct note {
  int freq;
  float amp;
  int (*func)(int, int, const ao_sample_format *);
};

struct notes {
  int total;
  struct note *notes;
};

int sine_wave(int freq, int pos, const ao_sample_format *format) {
  return (int)(32768.0 * sin(2 * M_PI * freq * ((float) pos / format->rate)));
}

void add_sine(struct notes *notes, int freq, float amp) {
  notes->total++;
  notes->notes = realloc(notes->notes, notes->total * sizeof(struct note));
  if (notes->notes == NULL) {
    exit(EXIT_FAILURE);
  }

  notes->notes[notes->total-1].freq = freq;
  notes->notes[notes->total-1].func = sine_wave;
  notes->notes[notes->total-1].amp = amp;
}

The function sine_wave will be called many many times as we populate the buffer, pos here represents the sample number and at 44.1 kHz there’s a lot of them for each one second buffer. To combine these sine waves, we simply need to multiply the output of the sine_wave function with the amplitude for this note, then add these values for each note together, e.g.

for (int n = 0; n < notes->total; n++) {
  sample += notes->notes[n].amp * notes->notes[n].func(notes->notes[n].freq, pos, format);
}

Algorithms aren’t my strong suit so I’m hoping modern processing power will ensure I’ll always be able to generate that second of sounds before it needs to be played.

The next challenge I’ve had is to be able to run a function to populate the buffer at the same time the old buffer is playing. As ao_play blocks I’ve needed to use threading, which is something I struggled with in the past and was no exception here.

It’s taken me several attempts and a bit of head scratching but I’ve finally got there today.

First we launch the function that will play the buffers in a new thread:

pthread_t threads[2];
int rc = pthread_create(&threads[0], NULL, play_buffers, (void *) &state);
if (rc != 0) {
  perror("pthread_create: handle_buffers");
  exit(EXIT_FAILURE);
}

Now this function will need to wait for the first buffer to be created, so it waits for that condition to be met:

pthread_mutex_lock(&mutex);
pthread_cond_wait(&data_ready, &mutex);
pthread_mutex_unlock(&mutex);

This has to get to the pthread_cond_wait before the buffer function sends the related broadcast, so I put in a very brief delay:

struct timespec t = {.tv_sec = 0, .tv_nsec = 100000};
nanosleep(&t, NULL);

And then we launch the function to populate the buffer:

rc = pthread_create(&threads[1], NULL, handle_buffers, (void *) &state);
if (rc != 0) {
  perror("pthread_create: handle_buffers");
  exit(EXIT_FAILURE);
}

This function then fills one of the two buffers, and on the first run signals the play_buffers function to play it. After the first run it will then wait for play_buffers function to be ready, as we’ve already established that will always take longer to run. As I’m still in the proof of concept phase I’ve just made it loop 4 times before finishing:

for (int i = 0; i < 4; i++) {
  pthread_mutex_lock(&mutex);
  state->active_buffer = i % 2;
  bfreq /= 2;
  add_sine(&state->notes, bfreq, 0.1);
  render_buffer(&(state->buffers[state->active_buffer]), &(state->notes), &(state->format));
  if (i == 3) state->buffers[state->active_buffer].last = true;
  if (i == 0) pthread_cond_broadcast(&data_ready);
  pthread_cond_wait(&read_ready, &mutex);
  pthread_mutex_unlock(&mutex);
}

After the play_buffers function has established which buffer it should be playing at this point in time it releases the lock so the filling of the buffer can begin again whilst the current buffer is playing:

for(;;) {
  pthread_mutex_lock(&mutex);
  active = state->active_buffer;
  buffer = &(state->buffers[active]);
  pthread_cond_broadcast(&read_ready);
  pthread_mutex_unlock(&mutex);
  ao_play(state->device, buffer->data, buffer->generated);
  if (buffer->last || buffer->generated < buffer->size) {
    return NULL;
  }
}
Next Steps

Next I’m going to look at changing the volume over time, so distinct notes can be played. After that I need some way to schedule upcoming notes so they can be triggered at the time, and also span buffers if necessary.

I honestly don’t know if I’ll get this project finished but it’s been fairly fun so far, and now I’ve got the threading stuff sorted out I’m more confident that I’ll get there eventually.

Update - See Part II and Part III

Sunday, 02. August 2020

caolan

Redux and Typescript

-/-
-/-

Sunday, 26. July 2020

tomwardill

Bikepacking Kit List

The Intro I’ve been doing a small amount if bikepacking and lightweight bicycle touring over the last 18 months or so. The distinction between bikepacking and touring is a somewhat hazy one, and there are plenty of Think Pieces about how to tell. Short form for me is that I prefer framebags to panniers and wider tyres to 25mm. This is mostly a reminder list for myself, it’s not definiti
The Intro I’ve been doing a small amount if bikepacking and lightweight bicycle touring over the last 18 months or so. The distinction between bikepacking and touring is a somewhat hazy one, and there are plenty of Think Pieces about how to tell. Short form for me is that I prefer framebags to panniers and wider tyres to 25mm. This is mostly a reminder list for myself, it’s not definitive and it’s not for everyone.

Wednesday, 22. July 2020

caolan

Inside a Collaborative Text Editor

-/-
-/-

Inside a Collaborative Text Editor

Introducing the Editor

Collaborative editors are defined by the size and speed of their updates. On a website you might submit a form, but in a collaborative editor you can send a single character or key press.

Your browser does not support the video tag.

Those tiny edits are shared quickly so you feel connected to your collaborators and can anticipate their actions. This exper

Introducing the Editor

Collaborative editors are defined by the size and speed of their updates. On a website you might submit a form, but in a collaborative editor you can send a single character or key press.

Your browser does not support the video tag.

Those tiny edits are shared quickly so you feel connected to your collaborators and can anticipate their actions. This experience is described as real-time editing.

Inside your editor, however, the frequent edits form a hotbed of conflicting updates. Solving or avoiding these conflicts is the real challenge of a collaborative text editor.

Conflicts

Taking turns, two authors might avoid a conflict - if they have the patience.

![](caolan.uk/processed_images/4154d7b675ec700e00.png)

But our collaborative editor has many authors. To block one author's key press until another releases their keyboard would be infuriating. Instead, they each edit a copy of the document and submit changes when ready.

To submit, the first author can simply swap his copy for the original - with no prior updates, his edits apply cleanly.

The second author, however, will find - in place of the original - the first author's copy. Where she re-worded a sentence, he might have deleted the whole paragraph. She cannot replace the document without losing his work, so she must compare the two and decide how, and if, her edits still apply.

Most collaborative editors do this automatically, behind the scenes, for every change to a document.

Operational Transformation

![](caolan.uk/processed_images/d16f9e7203a8563100.jpg)

The process of re-writing your edits to account for the work of others is called Operational Transformation. It's the most popular way to implement a collaborative editor and is used by Etherpad and Google Docs.

Concrete examples will follow, but for now let's start with two tubes: the kind you buy tennis balls in.

![](caolan.uk/processed_images/155936b3bca3740700.png)

Each tube has a starting state - a yellow ball - and each is held by a different artist. At the same time, each artist adds a coloured ball to the tube and informs their partner.

If they apply their partner's update naively, their tubes will look different: red-blue-yellow one side and blue-red-yellow the other.

![Two tubes, the left showing from top to bottom: red, blue, yellow, the right: blue, red, yellow.](caolan.uk/processed_images/7f4f128e9fa2cfce00.png)

No single tube is correct - the colours were added simultaneously - but the artists should agree a result.

To resolve the tie, they can invent an arbitrary rule. One that, when applied by both artists, will arrive at the same state. They could discard every ball… but the result is disappointing. How about: "when inserts are tied, insert red before blue"?

![Two tubes, both showing from top to bottom: blue, red, yellow.](caolan.uk/processed_images/74a0a8e0c99fd7b500.png)

By applying the same rule their states converge. This is the principle behind Operational Transformation and it can be applied to many authors typing at once.

Handling text

In a text document, you can improve such a rule by examining the position of the text.

Here's a photo of our cat Tama. I've labelled it "sleepy cat".

![Tama suggesting "very sleepy cat". Yui suggesting "sleepy grumpy cat".](caolan.uk/processed_images/7f664db5aa88a35300.png)

Tama and Yui (our other cat) both update my caption at different positions. When Tama receives Yui's edit, she'll need to shift Yui's "grumpy" right to account for her insert of "very".

![Two editors with the same state: very sleepy grumpy cat. Tama has applied the transformed message 'INS "grumpy " 12'.](caolan.uk/processed_images/f7a6a5a6edbee75500.png)

If she applied Yui's edit at its original character position, Tama would have the state "very slgrumpy eepy cat". But by understanding how their concurrent edits affect one another, Tama's editor can recover.

Unfortunately, we can't rely on position alone - what if they both insert text at the same location?

![Tama on top of the blanket with the caption "Tama".](caolan.uk/processed_images/d56daf5a9e4e722f00.jpg)

Another photo, labelled simply: "Tama".

![Tama suggesting "happy Tama". Yui suggesting "playful Tama".](caolan.uk/processed_images/086ae591d859549800.png)

Tama and Yui both make an edit at the beginning - position 0.

![Two editors showing a conflict. Tama has applied 'INS "playful " 0' and has the state "playful happy Tama". Yui has applied 'INS "happy " 0' and has the state "happy playful Tama".](caolan.uk/processed_images/819f09cfa16942c400.png)

Like our artists, Tama and Yui are tied for position. To resolve this, we invent another arbitrary rule and order the inserts by Tama and Yui's editor ID.

![Two editors with the conflict resolved. Tama has applied the transformed message 'INS "playful " 6' and now also has the state "happy playful Tama".](caolan.uk/processed_images/8c2ab5057501f00500.png)

Yui has ID [2], which is greater than Tama's [1], so Tama shifts Yui's insert after her own to converge on: "happy playful Tama".

We applied only two concurrent edits, but if Tama made multiple changes, she would need to transform Yui's insert for each - potentially shifting it multiple times before its final position.

I hope you feel confident after that, because - to demonstrate the risks - I'm going to present a puzzle that threw the early algorithms off-course.

False ties

The puzzle begins with a third author. And, since we only have two cats - that's Yui above - I've introduced a fictional bunny: Bandit.

![Tama suggesting "little loud cat". Bandit suggesting "cat". Yui suggesting "cute little cat".](caolan.uk/processed_images/f57d6afe96060d5d00.png)

Bandit doesn't think Yui is small and deletes the word 'little'. After applying all their edits, we expect the final caption to read: "cute loud cat".

![](caolan.uk/processed_images/8bd6291f807f45ce00.png)

But there's a problem - because Bandit deletes the word separating Tama and Yui's edits, a transform step might (falsely) tie them for position. I'll demonstrate by stepping through Tama and Bandit's transforms.

![Tama applying 'INS "loud " 7', 'INS "cute " 0', and the transformed message 'DEL 5..12' to get the state "cute loud cat".](caolan.uk/processed_images/d1431eaff0d5f1a600.png)

Tama arrives at the correct result "cute loud cat" because she applies Bandit's delete after her and Yui's inserts. Bandit, however, applies his delete first.

![Bandit applying 'DEL 0..7', the transformed message 'INS "loud " 0', and the transformed message 'INS "cute " 0' to get the state "loud cute cat".](caolan.uk/processed_images/09c1793a9bf57cd800.png)

His delete shifts Tama's "loud" to position 0. Yui's edit now ties with Tama's, so Bandit must apply the arbitrary rule and order their inserts by editor ID - [1] Tama's "loud", followed by [2] Yui's "cute". Bandit incorrectly arrives at "loud cute cat".

If you didn't anticipate that you're in good company. Many academic papers on Operational Transformation (OT) suffered similar counter-examples (or bugs, to the practitioner) on publication. Thankfully these puzzles have now been solved, as evidenced by the widespread use of OT in the wild.

You can find the solution to our puzzle in the 30 years of OT research since 1989. But to keep your curiosity in check, consider the following: if an edit could be undone, conflicts could be rewound and replayed in a fixed order. It's more work, and could still cause a false tie, but at least everyone would encounter the same tie.

Hopefully you're now suitably paranoid. Operational Transformation is easy to explain but complex to implement. If only there was a way to avoid conflicts altogether…

Avoiding conflicts

Remember the two artists? I have another commission for them, this time using coloured liquid instead of balls.

They each start with a tube containing yellow dye, to which they add their own colours. Yellow and blue to make green; yellow and red to make orange.

![A blue drop being added to the left tube to make green. A red drop being added to the right tube to make orange.](caolan.uk/processed_images/48d447c836121b4600.png)

Finally, they inform each other and add their partner's dye to their own.

![A red drop being added to the left tube to make a sort of grey colour. A blue drop added to the right tube to make the same grew colour.](caolan.uk/processed_images/35549bbf749c16a000.png)

What a lovely colour! - but at least they didn't have to apply any transforms to converge on it. Because the artists used liquid, the order they added the dye is irrelevant.

Using a data type with the same property for text we could eliminate conflicts there too.

Conflict-free replicated data types

![Tama suggesting "very sleepy cat". Yui suggesting "sleepy grumpy cat".](caolan.uk/processed_images/7f664db5aa88a35300.png)

One elegant data type, called LOGOOT (an example of a conflict-free replicated data type, or CRDT) is built upon each edit holding a unique position - represented by a list of integers.

!["[10, 0, 1] SLEEPY, [11, 0, 2] CAT"](caolan.uk/processed_images/1a9e80211f2fe7f900.png)

The list is comprised of: a positioning number, the author's editor ID, and a counter.

Every edit increments the author's counter. In combination with their editor ID, it ensures the position is unique. The positioning number places the text in the document.

To insert a word at the beginning of the document (before "sleepy") Tama [1] would create a new position list that starts with a random value between 0 and 10.

!["[6, 1, 1] VERY, [10, 0, 1] SLEEPY, [11, 0, 2] CAT"](caolan.uk/processed_images/db8ec7b35046ae4700.png)

Yui [2], unable to generate an integer between 10 and 11, chooses a new random positioning number and appends her values to the preceding list. By growing the list, Yui can always find a position between two adjacent words.

!["[6, 1, 1] VERY, [10, 0, 1] SLEEPY, [10, 0, 1, 130, 2, 1] GRUMPY, [11, 0, 2] CAT"](caolan.uk/processed_images/e74bdd81e27aab8200.png)

You can insert these four words - ordered by their position lists - in any sequence. You'll always arrive at the same result.

The example above uses a position list per word, but you'll probably want a position list per character - occupying significantly more space than the text alone in exchange for predictable performance.

Praise for the performance of CRDTs often rests on the worst-case scenario: a long conflicting history of edits. In practice, Operational Transformation can perform millions of simple transforms a second and grants greater freedom to optimise the data structure - so you might find OT performs better where fast feedback and short conflicting histories are the norm.

Personally, I enjoy using a modified version of LOGOOT. In the end, what convinced me was, not performance, but greater confidence that my code is correct.

Further reading

It seems incredible that, after 30 years of research, many products still restrict work to a single author or just lose overlapping edits. If, instead, we apply techniques to detect, avoid, and resolve conflicts, we can write good collaborative software.

  • A description of Etherpad's "EasySync"
  • Logoot : a Scalable Optimistic Replication Algorithmfor Collaborative Editing on P2P Networks - Weiss, Urso, Molli (2009)
  • High-latency, low-bandwidth windowing in the Jupiter collaboration system - Nichols, Curtis, Dixon, Lamping (1995)
  • Exhaustive search of puzzles in operational transformation - Sun, Xu, Agustina (2014)

Sunday, 28. June 2020

benofbrown

Fresh new style

After many years (almost 7!) I’ve finally ditched the default jekyll style and created something a bit different.

After many years (almost 7!) I’ve finally ditched the default jekyll style and created something a bit different.

Frontend development isn’t my strong suit, so I’ve kept it pretty simple. The colour scheme is one I’ve been using on my terminal and on my desktop for a long time, Ethan Schoonover’s Solarized Dark.

There’s no JavaScript or images, not a lot of CSS, uses built in fonts, and it seems to work pretty well on my phone and my laptop so I’m happy with it.