Categories
Blog

Shopping List: The Zombie dash

For the past week I’ve been self-isolating whilst Covid-19 precautions are ramping up in the UK. I have asthma but it’s so mild that I’m probably not what the government would classify as vulnerable. Unfortunately this puts me between a rock and a hard place for supplies; shops have no slots for delivery or pick-up, and I don’t want to deprive someone genuinely vulnerable of that service. So in a week when I need food I may be facing a zombie hoard in Sainsbury’s, coughing might-be-Covid on the onions and lingering around the Easter eggs.

I’ll be wearing a mask and gloves to reduce risk (especially as I may be an inadvertent zombie myself), and to make my run as quick as possible I’ve come up with a shopping list strategy, putting items from my online basket into a spreadsheet with these columns:

Item; Approx price; Quantity; Zone; Type

The fourth column ‘Zone’ is roughly where it is in the shop. Rather than organise by aisle number, I’m trying to zone-ify coarsely. Let’s say there’s a moaning zombie infestation in the dairy zone, then I can escape to the cereal zone! My first thoughts for zones are: veg, dairy, meat, snacks, bathing, cleaning, cooking, electronic, cereal and drinks. ‘Veg’ includes fruit. ‘Meat’ includes fish. ‘Cooking’ also includes bread items for now.

The order of zones may seem a bit mad but they are set as if I was walking through the store. So in my local store the veg is at the entrance and the drinks are at the end. If I need to add something later I can re-sort by zone.

The ‘Type’ column is a flag of how much I need something. I’ve currently categorised as: essential, treat, luxury and occasional. These are how much I expect to need things for a two-week period, e.g.:

Now if supplies are running low in stores I can sort by type and dash around the store for essentials:

And if times get really dark over the next few months, I can longingly look at my luxury items, dreaming of the good times when I will finally see them!

Think how amazing jelly popping chocolate will taste when I’ve been imagining it for two months solid.

Anyway, that’s the plan. It will probably need tweaking over the next few months, or maybe it’s just daft and I’ll drop it. Either way, it’s been a useful way to audit shopping, and I’m ready to race around that store.

(Note this was also a chance to learn how to use a spreadsheet on Linux. I’m using LibreOffice Calc, which felt very intuitive, familiar and I was thankful of no fancy ‘UX’ noise.)

Categories
Blog Code Music

Reading MIDI

I have a few ideas I’d like to prototype for live performance using MIDI loopers rather than audio loopers. I have sketched early ideas but I’d like to experiment with the project in earnest. I’m tinkering with tools before mocking up some early designs.

In the past I’ve written MIDI code on Windows using the old multimedia headers and real time clocks, and on AVR/Arduino using direct serial communication. My current thinking is to write a cross-platform mock-up in C++ or Python, and port to C++ on AVR when a hardware build is viable.

This tinker is on my ‘new’ Linux machine, a 2008 ThinkPad X230 running Ubuntu 18. I switched over because OSX and Windows drive me mad their constant updates and weird release policy. Long story short: now I’m able to experiment with /dev/midi.

#include <iostream>
#include <fstream>

namespace midi {

// https://www.midi.org/specifications-old/item/table-1-summary-of-midi-message

enum MsgType {
    NoteOff,
    NoteOn,
    KeyPressure,
    ControlChange,
    ProgramChange,
    ChannelPressure,
    PitchBend,
    Unknown,
};

const char* g_msg_names[] = {
    "note off",
    "note on",
    "key pressure",
    "control change",
    "program change",
    "channel pressure",
    "pitch bend"
};

struct MsgInfo {
    MsgType type;
    int channel;
    size_t extra_bytes;
};

MsgInfo msg_info(unsigned char header_byte) {
    int hi_nibble = header_byte >> 4;
    int lo_nibble = header_byte & 0b1111;
    switch (hi_nibble) {
    case 0b1000:
        return {MsgType::NoteOff, lo_nibble, 2};
    case 0b1001:
        return {MsgType::NoteOn, lo_nibble, 2};
    case 0b1010:
        return {MsgType::KeyPressure, lo_nibble, 2};
    case 0b1011:
        return {MsgType::ControlChange, lo_nibble, 2};
    case 0b1100:
        return {MsgType::ProgramChange, lo_nibble, 1};
    case 0b1101:
        return {MsgType::ChannelPressure, lo_nibble, 1};
    case 0b1110:
        return {MsgType::PitchBend, lo_nibble, 2};
    }
    return {MsgType::Unknown, -1, 0};
}

} // namespace midi

int main() {
    std::fstream fs("/dev/midi1", std::ios_base::binary | std::ios_base::in);
    while (fs.is_open()) {
        unsigned char header_byte;
        fs.read(reinterpret_cast<char*>(&header_byte), 1);

        midi::MsgInfo info = midi::msg_info(header_byte);
        if (info.type != midi::MsgType::Unknown) {
            std::cout << midi::g_msg_names[(size_t)info.type] << '\n';
            std::cout << info.channel << '\n';

            for (size_t i = 0; i < info.extra_bytes; ++i) {
                unsigned char data_byte;
                fs.read(reinterpret_cast<char*>(&data_byte), 1);
                std::cout << (int)data_byte << '\n';
            }
        }

        std::cout.flush();
    }
}

When the keyboard is plugged in this reports any non-sysex messages like this:

note on
0
60
66
note on
0
60
0
control change
0
1
6
control change
0
1
8
control change
0
71
33
control change
0
71
37

Note: installed xclip. Very handy for moving text from command line into blog. Added alias xclip="xclip -selection c" to .bash_profile and copied with xclip < main.cpp

Categories
Blog Code

Unrolling loops with templates

// Call the passed function object N times. This 'unrolls' the loop
// explicitly in assembly code, rather than creating a runtime loop.
template <unsigned int N, typename Fn>
void unroll(Fn&& fn) {
    if constexpr (N != 0) {
        unroll<N - 1>(fn);
        fn(N - 1);
    }
}

// extern function ensures the loop is not optimised away
extern void somethin(unsigned int i);

// Call somethin 4 times, passing the count each time
void four_somethins() {
    unroll<4>([](unsigned int i) {
        somethin(i);
    });
}

Compiling on https://godbolt.org/ with flags -std=c++17 -O3 gives

four_somethins():                    # @four_somethins()
        push    rax
        xor     edi, edi
        call    somethin(unsigned int)
        mov     edi, 1
        call    somethin(unsigned int)
        mov     edi, 2
        call    somethin(unsigned int)
        mov     edi, 3
        pop     rax
        jmp     somethin(unsigned int)            # TAILCALL

Categories
Blog

Rolling out Factors

Today’s post is an algorithm for ‘rolling’ out factors from any number. It determines all of the factors of that number, and hence whether it is prime.

This has grown from various doodles on paper, forming the idea that all natural numbers have a shape, a hyper-volume of N dimensions, where N is the total number of factors for that number.

The algorithm is perhaps best explained with an animation. I would like to submit this later, but in the meantime my diagrams below are ASCII art. You may find my code example more instructive factor_roll_demo. Here is the code without comments:

def factors(n):
    result = []
    rows = 2
    count = 0
    while n > 0:
        if count == n:
            result.append(rows)
            rows = 2
            count = 0
        elif count > n:
            rows += 1
            count = count - n
        else:
            n -= 1
            count += rows - 1
    return result

The above algorithm may be optimised by increasing the step size in the final else block. See git link above for comments.

Disclaimer: I am not an academic and am presenting this idea without knowledge of prior research. It may well be that this algorithm already exists under another name. Please drop me a line if you can help tie up connections to existing mathematics or computer science work.

A Rolled Prime Won’t Align

Given a natural number n ∈ ℤ+, let us represent it as a series of dots in 1D. So, for n = 7, the first step is:

1) Seven dots in 1D

  .......

Now, let us ‘roll’ the dots around the end until they meet or surpass the length of the topmost width, giving the following steps

2) Roll the last dot around the end making this a 2D shape, shortening the top to a width of six

  ......
       .

3) Roll the next dot around, the top becomes 5, the next row 2

  .....
     ..

4) Continue rolling giving top of 4, next row 3

  ....
   ...

5*) The next roll operation leaves the top at 3 and the next row overruns that length to 4.

  ...
 ....

The goal is to match rows to the topmost width, so to make step 5* correct, move the last dot onto a new row:

5) Roll the overflowing dot back around the left

  ...
  ...
  .

6*) Now roll again, however now as we decrease the topmost width, there are two rows to roll around, so the third row adds two dots for each dot lost on the top row:

  ..
  ..
  ...

This has overflown again, so to fix step 6*, move the overflow onto a new row, and continue:

6)

  ..
  ..
  ..
   .

7)

  .
  .
  .
  .
  .
  .
  .

By the last step we see that the (1×7) 1D line has moved through 2D to another (7×1) axis. Given the object can only exist in 1 dimension – that is it has no factors that can split in into other dimensions – then it is prime.

A Rolled Composite Matches Width

Let’s look at higher dimensions, starting with a non-prime example n = 6:

1)

  ......

2)

  .....
      .

3)

  ....
    ..

4)

  ...
  ...

Here we have hit a critical point: the last row exactly matches the width of the top row – we have found a divisor given by the number of accumulated rows, in this case 2, which is a factor of 6. At this point we can say this shape fits exactly in (at least) 2 dimensions.

This rolling out of factors is not contrained to 2D. So far we have seen that a prime 7 may exist as a 7 long 1D chain of dots, and that a composite number 6 may exist as a 2×3 2D rectangle of dots. If a number has more dots then it has a higher dimension, for example 12 = 2x2x3 3D cuboid, and 24 = 2x2x2x3 4D hyper-cuboid.

Factors Rank Dimension

This is a worked example of 12 rolling out into 3D

1) Start with 1D line of 12 dots

   ............

2) Roll around into 2D

   ...........
             .

Steps 3-5 continue rolling around until:

6) The factor 2 is identified by matching the second row length:

   ......
   ......

7) Rather than stopping here, promote the shape to 3D, roll along the next higher dimension, in this case a perpendicular axis going into the screen:

   . . . . .'
   . . . . .'

8) Continue rolling. Every decrement of the width is now adding 2 dots in 3D:

   . . .'.'
   . . .'.'

9) Now we see another match of the width, we have moved two ‘rows’ into the screen, giving us factors of 2×2.

   .'.'.'
   .'.'.'

However, we still need to determine the final factor, 3

The Final Factor

There are two ways to regard how the last factor should be pulled out of the algorithm. We could just keep track of the last computed row’s length (in this case 3), carry on rolling around until there is nothing left to roll, and claim that last row length as the last factor.

However, a more formal way to do it is to continue rolling into a yet higher dimension 4D, and track the number of ‘rows’ in that dimension accumulated until the topmost row has length 1.

Conclusions

This maths is the consequence of some late-night doodling. I’m sure a similar algorithm already exists, but it’s great to see an idea through without googling and going on a tangent and it’s pleasing that the algorithm is so concise.

This ‘rolling’ approach feels like a dual to the traditional sieve approach to finding primes. I haven’t done an analysis on computation complexity yet, but it’s interesting how the more rows there are, the faster the count increases. It’ll be interesting measuring that.

Also there will be an easy performance win in replacing the dot-by-dot stepping (in the last else block) with something that steps in larger jumps, based on some heuristic. Say the number is 20,000, then 10,000 steps are wasted looking for the first alignment, whereas one may simply guestimate it as n/2 steps when filling the second row, n/3 on the third.

Categories
Blog

Last Monday of 2019

I’ve been exploring two things today: a sort of 2D to 3D tunnel concept I’d like to render and; more experiments photographing bits of trees for my ‘overlaying stuff’ projects (working title…)

2D to 3D Dimension Jump / Torus

My intial sketch was a sort of hyperbolic curve defined by points gently falling down from a ‘flat’ 2D surface. The points fall slowly to accelerate outwards in a trumpet horn shape. Rather than the curve ending at the horn’s end, the points gradually make their way back to the 2D surface. In the initial sketch I envisaged a human form with the centre of the head as the centre of the 2D surface, and the tail/groin where the shape opens out:

Image3

I thought I could do this in a Jupyter notebook but couldn’t find a decent scene graph to poke around with values in real-time. So I installed Blender and watched a few tutorials – it’s been a long time since I last used it (for mov1, mov2) and the UI feels a lot more friendly these days. That’s apart from how one closes a window panel which drove me mad; you have to drag the toolbar of a window over the window it’s going to ‘absorb’, but it doesn’t work if the drag area has splits in it.

Whilst shaking my finger at Blender, I poked around with Jupyter using SciPy and ImageDraw to figure out some curves that may work. It was interesting to play with SciPy’s Curve class, but I settled on simple parametric positions based on ease-in-out animation curves, tweaking the speeds using power functions. Here’s an early sketch:

from math import sin, cos, pi

# Animation ease curves via https://gist.github.com/th0ma5w/9883420
def easeInOutSine(t):
    return (1 - (cos(pi * t))) / 2

def px(d, u):
    return d + (1 - d) * d**.01 * sin(easeInOutSine(u**8.1) * pi) ** 1.2
    
def py(d, u):
    return sin(easeInOutSine(u**4) * pi) ** 2

The d value in px and py is the distance from the up axis of the point at the start. Combining d with an angle theta and u = 0 will determine the starting position a point in the 2D plane, then interpolating 0 <= u < 1 generates the shape.

These are curves for various d values between 0 and 1:

Next up I need to generate shapes in Blender script and use these curves to generate animation keyframes.

Overlaying Stuff

An early experiment from various photos today. The best way to get these shots is midday with cloud coverage for a good silhouette, these were late in the day so grainy and catching too much light. Good to play though and it’s got me in the mind to do the final version using old camera film and process and expand onto acetate at home

silhouette-2019-12-30

Categories
Music Projects

AARC on Bandcamp

I’ve uploaded recent AARC jams between Ryan and I onto Bandcamp. The first of these is a practice for a live gig at the Modular Meetup in London and the second is the gig itself:

a3662863923_16

In this setup we’re locked in to a performance where the tempo runs down from 80 to 15 BPM over the course of 30 minutes. It’s a setup for heady improvisation that usually leaves us borderline catatonic. It’s clocked from a dinky AVR chip with a 3.5mm jack output going into Ryan’s Volca. I piggyback the sync signal for my modular rig.

These recordings are not mastered – it’s all straight out from the mixer warts and all. Future jams will be multi-tracked and mastered, maybe :)

 

Categories
Blog Code

Nanopore Technical Challenge Day 2

Now to the meat of the problem, how the tasks actually run. Some of these tasks are going to run in parallel and that could cause threading issues. Looking at the original challenge there is an obvious sticking point. The two tasks ‘Preheat heater’ and ‘Mix reagent’ need to notify ‘Heat Sample’ they are done in a thread safe way so I will need a mutex. Alternatively I could use a thread safe boost::signal to inform the node that a task has finished, but that’s a bit heavyweight.

Another way though is if the computer is maintaining the state of each node, and the DAG is guaranteed not to change, then each node just needs to know how many inputs it has and keep a counter tracking how many have fulfilled their completion. std::atomic is designed for cases like this.

Because tasks can run in parallel, there may be more than one ‘cursor’ at the point of execution, so the  computer has to store a vector of cursors. Ideally the code will not continually start and stop threads to avoid a drain on resources, so future version will use a thread pool.

I can’t believe I’m posting these scrappy doodles but I’m chucking these pages out fast so I can crack on with code. This is this morning whilst waiting at the GP!

Day 2 sketch

Despite my expirations in optimising the DAG, I’m going to start with a simple version using std::function calls. I will fire off the threads using async which means I can take advantage of futures.

Futures will be particularly useful for updating my simulated hardware device with the output from the task. I know what inputs and outputs I am affecting in each task, so the future can return a block of ‘things to update’ on the hardware when the task has completed. Given my tasks specify what their inputs and outputs are I can validate that parallel threads are not going to access the same inputs and outputs and avoid collisions when the data is written. Due to the validation system, those collisions can be reported at builder time so you are guaranteed a clear flow.

For now I think the validation may be done through a function per tasks called ‘affects’ which returns which parts of the DeviceIO will be affected. For now this could just be a bit mask of input/output/cell IDs in an enum that are available on the device.

Whilst I’m here here’s last night’s godbolt doodle. I discovered that std::function does a lot more than a simple lambda. The compiler knows how to optimise lambdas. In this example I do everything with native function pointers for a ridiculously tight system https://godbolt.org/g/RTdnU1. This is more of a vanity project than something I will use for now because it would put significant constraints on the design before I’ve had a chance to shape it. Still it’s good to see what sort of methods I could use to optimise in the long run.

 

 

Categories
Blog Code

Nanopore Technical Challenge Day 1 … more doodling

These are some embarrassingly loose sketches made en route to a friend’s leaving do. I wanted to cement my ideas about the builder class and these led into the idea of how one defines a hardware device. I was getting painfully close to template magic with these ideas but wanted to get an idea for the most expressive DSL for a recipe.

Day 1 eve A

I also sketched out some ideas for how to organise the project. And this also raised the question of whether I could statically compile the builders and take advantage of compiler optimisations so the DAG would have a very small footprint.

the ‘struct VolTRAX_0_0_1 is significant. Here I’m thinking of ways of declaring a device and how the state of that device is handled. Also if the device were a template class then you would have a very pluggable way of constructing recipes for multiple targets: you can reuse the core tasks but swap out different hardware. TBC

Day 1 eve B

Other notes that came up:

  • Should the DAG nodes be old school and use pointers or reference_wrappers to other nodes?
  • Don’t get too carried away with std::array in first pass. Write in std::vector, get unit tests working, then try to get static array version building as future goal.
  • How to implement current execution point ‘cursor’ and how is the running of each node handled. Should the computation trawl through the nodes or should there be an external ‘computer’ that maintains the cursors.
  • How do tasks signal they are finished, just notify by updating a counter, or do something snazzy with boost::signals2?
  • Quick todo list on setting up the GitHub repo!

After getting home I did a little late night exploration in terms of what one could do with static DAGs, e.g. std::array. This was off-piste but fun. Also I was using C++14 for some cases which, so I need to reign that in for the C++11 requirement spec for this challenge:

 

 

Categories
Blog

Nanopore Technical Challenge Day 1 … part 2

I sketched out a few early ideas in code to get a feel on good approaches in software. As the DAG is being generated by a builder, I wanted to see if it was possible to use std::array for inputs rather than std::vector. Regardless, my first doodle was more just a simple DAG structure exploring the concepts of adding hardware dependencies: https://godbolt.org/g/5y3Gsa

This was very useful in identifying a minimal DAG node, called a Task in this example. A few points:

  • Technically I don’t need to store the inputs as I’ll be processing this DAG top to bottom.
  • The idea of serial and parallel operations being simple derivatives of task
  • All operations on the device would be task derivatives.
  • Avoid cycles during insertion (possible to static assert if DAG size is known at constrcution?)

The main() block makes a conceptual jump into a nice syntax for a builder class that builds up the DAG in a readable way, sort of like a DSL for lab protocols. The base TaskBuilder class is responsible for generating a single DAG node. The TaskBuilderContainer is responsible for a list of DAG nodes, and is derived from Task with an extra method end() to indicate the end of a scope block.

These builder classes are nicely wrapped up readable class methods like add_ingredient() or preheat(). recipe() should really be called workflow() and takes a name.

 

 

 



		
Categories
Blog Code

Nanopore Technical Challenge Day 1

A few days ago Nanopore sent me a technical challenge as part of their interview process. I’ve set up a a GitHub repo to track development progress. These are some notes before I go headlong into coding:

Day 1 – tech challenge received

The challenge involves building a DAG for a workflow. The first thing I did on receiving it was sketch out their example DAG to get a better feel for the behaviour of each node:

Day 1 sketch

Forgive the quality of these scans, I’m cobbling this together fast! The first sketch highlighted the scope of the design for the DAG:

  • Whether a task is manual or automatic.
  • Functional behaviour (e.g. display message, move sample).
  • Specification of ‘ports’ on device
    • Input where user adds sample. I’ll call these input_a, input_b etc.
    • Output where user removes sample. I’ll call these output_a, output_b etc.
    • General input/output ‘cells’ which is where the device is moving samples around, which I’m assuming to be a 2×2 grid from seeing the VolTRAX videos. I’ll call these cell_1_1, cell_2_4 etc.
    • Certain cells do work, e.g. heating, applying magnetic field. I’ll treat these like regular cells but give them special IDs like heater_1.

Example tasks and data required:

  • Add ingredient (manual): show message; input port ID; destination cell to move sample to.
  • Mix ingredients (auto): two registers to mix; cell where the sample ends up.
  • Preheat (auto): heater temperature; heater ID if there is more than one.
  • Heat sample (auto): input cell location; time on heater; header ID if there is more than one; output cell location.
  • Extract sample (manual): show message; output port ID.

This highlights some missing data in the DAG, that the operations of moving between certain cells should perhaps be nodes in themselves. For example the ‘heat sample’ task would be simpler if it was split up using move tasks:

  • Move sample from cell_1_2 to heater_1.
  • Stay on (preheated) heater_1 for 2 seconds.
  • Move sample from heater_1 to cell_2_3.

A few other things came up in this sketch:

  • Being a DAG it needs to avoid cycles.
  • The ports/cells give me a conceptual device to work with.
  • Validation. If I know all the inputs and outputs then I can run a validation step to ensure that anything that uses a particular cell or input has had that cell or input set up; i.e. check hardware dependencies.
  • To run the program the nodes will need to be sorted topologically. Not necessary if nodes are inserted in-order.
  • My sketch at the bottom left is my thinking about organising parallel data tasks which let to builder concepts detailed in next post. I think I can get a nice DSL together.