Style | StandardCards

Sheffgeeks Blogs Last Update:

benofbrown - Jan 24

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 5 months ago

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/

5 months ago

caolan - Nov 18

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 7 months ago

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.

7 months ago

caolan - Oct 14

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 8 months ago

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

8 months ago

caolan - Oct 06

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 9 months ago

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

9 months ago

benofbrown - Sep 06

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. 10 months ago

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.

10 months ago

benofbrown - Aug 15

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. 10 months ago

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

10 months ago

caolan - Jul 22

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 11 months ago

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)
11 months ago

benofbrown - Jun 27

Real config on staging, featuring nginx and dante

I’m a firm believer in keeping staging as close to production as possible. It just makes sense to me, there’s too much room for error if things are different, and you’re not really testing what you think you are. 12 months ago

I’m a firm believer in keeping staging as close to production as possible. It just makes sense to me, there’s too much room for error if things are different, and you’re not really testing what you think you are.

Now this can get a bit tricky when it comes to configuration files, especially when they contain hostnames, doubly so if you’re using HTTPS, which of course you are aren’t you?

Platform Overview

OK, “platform” might be stretching it for my current setup. I look after the technical side of a pretty niche website, Ninehertz. It’s been around for a long time now, and still gets a decent amount of traffic but nothing too taxing.

For the staging side I use a virtual machine. Like a lot of people these days I manage it with Vagrant using the libvirt backend.

The site itself is served by nginx.

TLS Complications

If we’re going to use the exact same config on live and staging, then we’re going to need to use TLS (fka SSL), and if we’re going to use TLS, we need certificates for it. Now, we don’t really want genuine private keys on staging, access to those should be restricted, so we’re going to make some dummy certificates ourselves.

We could simply use self-signed certificates, but then we’d get annoying warnings in the browser. So what I do is create my own CA certificate.

This is really easy to do, and completely safe as long as you follow some precautions:

  • Use a different browser profile when you import the CA - I really can’t stress this enough.
    • Firefox has a profile manager you can use to create a separate profile, create one with a meaningful name and import the CA to that.
    • Chrome has the --user-data-dir argument which does a similar thing. A shell alias makes this easy to use.
  • Only add this CA to the system approved list on your VM - don’t do this on your host machine.

First we create a private key for the CA:

openssl genrsa -out CA.key 4096

Next the CA itself:

openssl req -x509 -days 365 -key CA.key -subj '/CN=dummy CA cert' -out CA.crt

Adjust the subject and days to taste, though I recommend making it obvious that this isn’t a real CA in the subject. 365 days is a year, so it will expire after that time, though it’s just a case of re-running the command to renew it.

Now we need to create a key and a Certificate Signing Request for the server to use. For this example we’ll use www.example.com and will create a cert that’s also valid for example.com:

openssl genrsa -out server.key 2048
openssl req -key server.key -new -subj '/CN=www.example.com' -out server.csr

Keep hold of these two files, server.key and server.csr. The key will be needed to use the certificate we create and the CSR can be used to renew the cert later.

Now to sign the certificate request to generate a certificate:

printf 'basicConstraints=CA:FALSE
keyUsage=nonRepudiation, digitalSignature, keyEncipherment
subjectAltName=DNS:www.example.com,DNS:example.com' | \
openssl x509 -req -days 365 -in server.csr -out server.crt -CA CA.crt -CAkey CA.key \
    -set_serial 1 \
    -extfile -

Some things to note:

  • set_serial 1 - this sets the serial number. When the certificate expires and you create a new one, make sure you set the new serial to something higher than this value.
  • subjectAltName etc, this is what allows the cert to be used for more than one hostname. It’s also required for the site to display in Chrome without warnings.

Now you have a brand new server.crt and server.key you can use in the nginx config in place of the real certs, just use the same paths for them so the config remains the same.

Approach 1: Hostfiles

The simplest way to approach this problem is to simply add entries to /etc/hosts or the equivalent on your host OS, to point records to your VM.

Downsides to this are:

  • You can’t look at live and staging at the same time to compare things
  • You can easily forget you’ve done that and confuse yourself later down the line
  • Your test site can access third party resources, some of which you only want live to be able to access

For these reasons I decided I needed something better - a proxy.

Approach 2: SOCKS proxy via SSH

You may or may not know this already, but ssh includes a pretty usable SOCKS proxy, you just invoke it with -D and a port number, then use that port as your proxy. Combined with adding hosts records redirecting to the loopback device this worked great.

But hang on! You said you’d moved away from using the hosts file!?

Indeed I had, but my main problem was editing /etc/hosts on the host OS, and this change is in the VM. As clients can use the SOCKS proxy to resolve hostnames too this is a nice solution, you know when you’re using the proxy that you’re hitting staging.

I used this approach for a little while, but I wasn’t completely happy with it for the following reasons:

  • You have to run the ssh command every time, which gets annoying
  • It still doesn’t control access to third party resources

With these concerns in mind I decided I needed a SOCKS proxy that would start automatically when the VM started, and had some access control. After some searching I found…

Approach 3: dante

Dante is a free SOCKS server, developed by Inferno Nettverk A/S. It’s included in Debian, my OS of choice, so was simple to install. It also supports allowing and denying access to resources, so I quickly set up some rules. I knew it would resolve the hostnames I was interested in to the local loopback address, so I just added a rule to allow traffic to that interface and deny all other traffic.

This worked really well, I didn’t need to ssh in any more, but something looked a bit strange. The fonts weren’t right.

I knew straight away why this was, Ninehertz uses Google fonts, which were now being blocked. For a while I lived with that, but I got curious and started thinking of a better way.

Approach 4: nginx proxy_pass for specific hostnames

My next approach was to add specific hostnames to the VM’s hosts file and direct them to the local nginx instance, with a small config snippet using proxy_pass to redirect the traffic. I’d also create certs for these hostnames, signed with my CA. With a bit of Ansible this was pretty easy to do so I got it up and running fairly quickly.

This worked great for Google Fonts, but I hit another problem when I loaded a page with an embedded SoundCloud embed, which was trying to fetch things from loads of subdomains. This wasn’t going to scale nicely at all - I really needed a way I could use wildcards.

Approach 5: nginx stream proxy_pass, with dante redirecting

I had a bit of a think and came up with what I thought was a cunning plan. I’m a bit of an nginx enthusiast and like to stay up to date with new features etc, even if I don’t really use them. One such feature popped in to my head, ssl_preread.

Combined with the nginx map directive, this allows us to read the target hostname from the TLS handshake (amongst other things) and route the traffic to different ports depending on the values it finds. We can even use wildcards here, which makes it even easier.

This uses the nginx stream module which operates at a low level, so we don’t even need to think about TLS handshakes, we can now forward the TCP traffic unencrypted to the hosts we want to allow.

For other hosts we’ll just forward it to a dummy HTTPS server, also in nginx, with an invalid certificate.

All I need to do now, is capture all requests to HTTPS on dante to this nginx stream server. Now we can’t use port 443 here without changing our own http server config, which would defeat the point of this, so we run the stream server on a different port.

Looking at the dante documentation it looked really easy to redirect this traffic to our arbitrary port, but when I put the config in place, the danted service failed to start. I’d missed a key part of the documentation, from Redirection:

Some additional functionality is however offered as modules that can be purchased separately. The redirect module can be used to modify traffic by redirecting it to a different location than the client requested.

OK, so dante can do it, but not without a proprietary module. This was a little disappointing, but if that’s their model then that’s fair enough.

Finished setup: nginx stream proxy_pass, dante, and iptables

Finally I arrived at the setup I’m using today. The final piece in the puzzle was to simply use iptables to redirect all http and https traffic to the local nginx instance, with the exception of traffic from nginx itself as that would cause a loop.

Here’s the nginx configuration for the stream module:

map $ssl_preread_server_name $backend {
  hostnames;
  .ninehertz.co.uk 127.0.0.1:443;

  fonts.googleapis.com $ssl_preread_server_name:443;
  fonts.gstatic.com $ssl_preread_server_name:443;
  .soundcloud.com $ssl_preread_server_name:443;
  .sndcdn.com $ssl_preread_server_name:443;
  default 127.0.0.1:8001;
}

resolver 127.0.0.1;

server {
  listen 8000;
  proxy_pass $backend;
  ssl_preread on;
}

server {
  listen 8002;
  proxy_pass 127.0.0.1:80;
}

I should probably mention that I use PowerDNS on this box and on live as a local resolver, that’s what resolver 127.0.0.1 is referring to. We need to set a resolver up here so nginx can look up the hostnames it needs to proxy the external traffic.

Most of the work here is done in the map section. $ssl_preread_server_name is the server name passed in the TLS negotiation. If it matches the hostnames listed and it’s one of the sites that are being staged on the VM then the variable $backend is set to the loopback device. If it’s a site we don’t host, but want to allow access to $backend is set to the original hostname.

We are using the hostnames option in the map (which needs to be listed before the list of values we’re checking) so we can use the special leading . form to match a domain and any subdomains at the same time. e.g. .ninehertz.co.uk matches ninehertz.co.uk, www.ninehertz.co.uk, foo.bar.ninehertz.co.uk etc.

Finally default is a special record which is used to set a default value, which will be for anything we want requests to to fail. These will be redirected to another nginx server block in the http scope, which is running on port 8001.

The first server block simply listens for connections on port 8000, and passes them to the $backend set by the map. We need to have ssl_preread on here or the special $ssl_preread_server_name variable won’t get set.

The next server block is for handling any requests on port 80, it just passes them all to the loopback address.

Here’s the config of the server that non-matching results are forwarded to:

server {
  listen 8001 default_server ssl;

  ssl_certificate ssl/default.crt;
  ssl_certificate_key ssl/default.key;

  return 403 "No\n";
}

This is very simple, we just have a cert signed by our CA and it’ll return 403 for all requests.

Dante wise it’s pretty simple, we pass anything going to to ports 80 or 443, and reject everything else.

Finally, here’s the iptables rules to make it all work:

iptables -t nat -A OUTPUT -m owner --uid-owner nginx -j ACCEPT
iptables -t nat -A OUTPUT -d 127.0.0.1/32 -j ACCEPT
iptables -t nat -A OUTPUT -p tcp -m tcp --dport 80 -j REDIRECT --to-ports 8002
iptables -t nat -A OUTPUT -p tcp -m tcp --dport 443 -j REDIRECT --to-ports 8000

It simply accepts all requests from the nginx user, all requests to the local loopback, and redirects any remaining requests to the default https port of 443 to port 8000 on the loopback device.

And a nice feature of this approach is that we no longer need to touch /etc/hosts on either our host machine or the VM.

I hope you might find this useful, if you have any feedback drop me a message on any of the platforms listed at the bottom of each page.

12 months ago

caolan - Mar 03

Time Disorder

![A melting clock.](caolan.uk/processed_images/cd220c358cf824a100.png)

Our measurement of time is imperfect, but we perceive it as ordered and logical. So it's both tempting and dangerous to sort events by timestamp. Timestamps do not provide the strict order you might assume and events out of sequence can cause significant bugs.

Time resolution is not infinite

What if two events h over a year ago

![A melting clock.](caolan.uk/processed_images/cd220c358cf824a100.png)

Our measurement of time is imperfect, but we perceive it as ordered and logical. So it's both tempting and dangerous to sort events by timestamp. Timestamps do not provide the strict order you might assume and events out of sequence can cause significant bugs.

Time resolution is not infinite

What if two events have the same timestamp?

In a log file this is not a problem, because the lines of the file provide a strict order. Import the events into a database, however, and the original line order is lost - two rows with the same value will be in an undefined order.

The risk of a duplicate timestamp is affected by:

  1. The resolution of your hardware clock and time APIs - running your code on another platform may significantly increase your chance of duplicates.
  2. The resolution of your timestamps - do you store seconds since epoch (resolution 1 second)? nanoseconds? a date string with HH:MM (resolution 1 minute)?
  3. The frequency of events

You might record identical timestamps for events in close proximity, causing them to appear shuffled. To make matters worse, this is most likely when your machine is under heavy load.

Clocks can go backwards

A clock is merely a device to measure time and as such requires calibration and adjustment. Manual adjustments - like a user naively changing a timezone or correcting a slow clock - are the most likely cause of a jump backwards, but automatic changes can also be to blame.

The automatic change from daylight saving could jump an event backwards a whole hour if you handled timezones incorrectly. We have to be particularly careful in the UK, where GMT can happily masquerade as UTC for half the year.

Services like ntpd (Network Time Protocol Daemon) can also cause dramatic clock changes. Depending on configuration, a large drift in system time can cause ntpd to hop immediately to the correct time (possibly backwards). Devices like the Raspberry Pi - that are frequently disconnected and have no real time clock - are particularly vulnerable.

Monotonic clocks - guaranteed to never run backwards - do exist, but a timestamp from a monotonic clock is of little use between reboots, and useless to compare between machines. They are generally used to measure an interval on a single machine.

Intervals can stretch and shrink

Jumps in time can cause problems, so services like ntpd often prefer to slow down or speed up the system clock until it gradually approaches the correct time (this is called 'slew' correction).

Google uses a similar approach for leap seconds, 'smearing' an extra second over a 24 hour period, instead of bamboozling software with a 61 second minute.

Even if you could start a timer on multiple machines at a known instant in time and stop them at another instant, they would likely measure a subtly different elapsed time. The longer the interval, the more apparent manufacturing tolerances will be. Adafruit advises this PCF8523 based RTC "may lose or gain a second or two per day".

Clocks are never in sync

You may be attracted to timestamps because they're easy to collect at multiple sites then add to an ordered series later. However, in addition to all of the above, you must now consider the disparity between multiple system clocks.

Replying to a chat message on a different machine, you might easily record a timestamp before the original message.

Recommendations

When you sort data by timestamp, it implies a causal relationship - that, say, a message happened before it's reply, or a credit happened before a debit. Therefore, techniques that provide a strict - or at least causal - ordering of events should be preferred.

Use a counter

The most fool-proof alternative to timestamps is an incremental counter stored on a single machine. If there is only one instance of the software, or clients always submit to a central server, this is often the best choice.

Most databases provide an auto increment or sequence type that can provide a suitable value.

Consider distributed clocks

If you need to generate points in a sequence at multiple sites, then you may need a more complex series of counters like Lamport timestamps or a vector clock. Distributed clocks like this provide a partial causal ordering of events and a means to detect conflicts (i.e. events that are seen as concurrent because they extend a shared point in history).

If your clients generate timestamps locally, but the data is only integrated by a central server (not shared peer-to-peer), your logical clock can be relatively simple, requiring only two peers.

Handle conflicts

Distributed clocks only help you detect concurrent events. Once detected, the problem of resolving conflicts is often domain-specific. Using the appropriate clock or data type will force you to handle these conflicts early. Remember, the conflicts were always present with timestamps - they were just not apparent.

Detecting and resolving conflicts can be as fancy and complex as you like - but, before you reach for a full version-control system like git, I suggest you try a distributed clock or simple counter first.

When are timestamps appropriate?

I'm only suggesting timestamps are a bad way to order causally linked events. Timestamps are still useful for:

  • Communication with humans - Logical clocks don't mean a lot to us. Adding a timestamp as part of the presentation (but not ordering) of data is often a good idea as it lets us place entries in a wider context outside of a single application.
  • Sampling - Data collected for statistical analysis is often collected ad-hoc from multiple sources and strictly ordering measurements in close proximity may not be important. Ask yourself: "If I shuffled a few events around would my conclusions still be sound?"
over a year ago

kitation - Jan 01

2020: Let's start out optimistic and see how long it takes

I did start out writing a retrospective of 2019, but it was depressing and making me feel depressed every time I sat down to work on it, so I’ve ditched that and decided to look ahead for once. So here are my goals for the next year, and we’ll see how long it takes for the world to destroy them.

over a year ago

I did start out writing a retrospective of 2019, but it was depressing and making me feel depressed every time I sat down to work on it, so I’ve ditched that and decided to look ahead for once. So here are my goals for the next year, and we’ll see how long it takes for the world to destroy them.

over a year ago

tomwardill - Sep 11

Making a Chefs Knife

“I’ve been thinking about running a knife making workshop”. Those were the words in the email that got my attention. Someone was offering to run a workshop and had a PID controlled heated knife oven to do the heat cycle and tempering. Seemed like a good idea to me. This write up is mostly a ‘this is what I did’, the end product is usable, but not ideal. It’s a fi over a year ago
“I’ve been thinking about running a knife making workshop”. Those were the words in the email that got my attention. Someone was offering to run a workshop and had a PID controlled heated knife oven to do the heat cycle and tempering. Seemed like a good idea to me. This write up is mostly a ‘this is what I did’, the end product is usable, but not ideal. It’s a first attempt and a learning process. over a year ago

benofbrown - Dec 28

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. 6 months ago

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.
6 months ago

caolan - Oct 25

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 8 months ago

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

8 months ago

caolan - Oct 07

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 9 months ago

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

9 months ago

caolan - Oct 05

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 9 months ago

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

9 months ago

benofbrown - Aug 23

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. 10 months ago

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

10 months ago

tomwardill - Jul 26

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 11 months ago
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. 11 months ago

benofbrown - Jun 28

Fresh new style

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

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.

12 months ago

mbooth - Apr 23

Using the remote OSGi console with Equinox

You may be familiar with the OSGi shell you get when you pass the "-console" option to Equinox on the command line. Did you know you can also use this console over Telnet sessions or SSH sessions? This article shows you the bare minimum needed to do so.

over a year ago

You may be familiar with the OSGi shell you get when you pass the "-console" option to Equinox on the command line. Did you know you can also use this console over Telnet sessions or SSH sessions? This article shows you the bare minimum needed to do so.

over a year ago

kitation - Feb 14

I'm not sick but I'm not well: Self-Injury Awareness Day 2020

Content warnings: Depression, anxiety, disassociation, self-harm (specifically cutting) and suicidal ideation

Five years ago, I wrote something for Self Injury Awareness Day. Since then, things have gotten both worse and better at the same time. I wanted to write down my “journey” since then, but also some thoughts about mental health vs mental illness in general, and why I find some man over a year ago

Content warnings: Depression, anxiety, disassociation, self-harm (specifically cutting) and suicidal ideation

Five years ago, I wrote something for Self Injury Awareness Day. Since then, things have gotten both worse and better at the same time. I wanted to write down my “journey” since then, but also some thoughts about mental health vs mental illness in general, and why I find some many things in this space so frustrating.

over a year ago

kitation - Nov 21

Accessibility for anxiety

Content warning: Mentions of panic, anxiety, depression and self-harm

I have anxiety. I’ve had it for since my teens. I have depression too, although it can often be hard to distinguish one from the other. It’s mostly controlled by medication, and a boatload of therapy. There are times though when it “flares up”.

I went to a conference this week, I had a “flare up”. It wasn’t pre over a year ago

Content warning: Mentions of panic, anxiety, depression and self-harm

I have anxiety. I’ve had it for since my teens. I have depression too, although it can often be hard to distinguish one from the other. It’s mostly controlled by medication, and a boatload of therapy. There are times though when it “flares up”.

I went to a conference this week, I had a “flare up”. It wasn’t pretty. I want to talk about my anxiety, how it presents, and what events should do to help people who have similar issues and triggers to me.

over a year ago

mbooth - Sep 03

Simple Hammer Repair

You may recall from my previous post about broken tools that I broke my favourite hammer by using the claw to break down what turned out to be some really sturdy cupboardry. In this post I document the manufacture of a new handle from scratch.

over a year ago

You may recall from my previous post about broken tools that I broke my favourite hammer by using the claw to break down what turned out to be some really sturdy cupboardry. In this post I document the manufacture of a new handle from scratch.

over a year ago