Friday, 28 October 2011

Some deep analysis of one-line music programs.

It is now a month since I posted the YouTube video "Experimental music from very short C programs" and three weeks since I blogged about it. Now that the initial craze seems to be over, it's a good time to look back what has been done and consider what could be done in the future.

The developments since my last post can be summarized by my third video. It still represents the current state of the art quite well and includes a good variety of different types of formulas.


The videos only show off a portion of all the formulas that could be included. To compensate, I've created a text file where I've collected all the "worthy" formulas I've encountered so far. Most of them can be tested in the on-line JavaScript and ActionScript test tools. Some of them don't even work directly in C code, as they depend on JS/AS-specific features.

As I'm sure that many people still find these formulas rather magical and mysterious, I've decided to give you a detailed technical analysis and explanation on the essential techniques. As I'm completely self-educated in music theory, please pardon my notation and terminology that may be unorthodox at times. You should also have a grasp of C-like expression syntax and binary arithmetic to understand most of the things I'm going to talk about.

I've sorted my formula collection by length. By comparing the shortest and longest formulas, it is apparent that the longest formulas show a much more constructivist approach, including musical data stored in constants as well as entire piece-by-piece-constructed softsynths. The shortest formulas, on the other hand, are very often discovered via non-deterministic testing, from educated guesses to pure trial-and-error. One of my aims with this essay is to bring some understanding and determinism to the short side as well.

Pitches and scales

A class of formulas that is quite prominent among the shortest ones is what I call the 't* class'. The formulas of this type multiply the time counter t with some expression, resulting in a sawtooth wave that changes its pitch according to that expression.

A simple example of a t*-class formula would be t*(t>>10) which outputs a rising and falling sound (accompanied by some aliasing artifacts that create their own sounds). Now, if we introduce an AND operator to this formula, we can restrict the set of pitches and thus create melodies. An example that has been individually discovered by several people, is the so-called "Forty-Two Melody": t*(42&t>>10) or t*2*(21&t>>11).

The numbers that indicate pitches are not semitones or anything like that, but multiplies of a base frequency (sampling rate divided by 256, i.e. 31.25 Hz at the default 8 kHz rate). Here is a table that maps the integer pitches 1..31 to cents and Western note names. The pitches on a gray background don't have good counterparts in the traditional Western system, so I've used quarter-tone flat and sharp symbols to give them approximate names.


By using this table, we can decode the Forty-Two Melody into a human-readable form. The melody is 32 steps long and consists of eight unique pitch multipliers (including zero which gives out silence).


The "Forty-Two Melody" contains some intervals that make it sound a little bit silly, detuned or "Arabic" to Western ears. If we want to avoid this effect, we need to design our formulas so that they only yield pitches that are at familiar intervals from one another. A simple solution is to include a modulo operator to wrap larger numbers to the range where simple integer ratios are more probable. Modifying the Forty-Two Melody into t*((42&t>>10)%14), for example, completely transforms the latter half of the melody into something that sounds a little bit nicer to Western ears. Bitwise AND is also useful for limiting the pitch set to a specific scale; for example t*(5+((t>>11)&5)) produces pitch multipliers of 4, 5, 8 and 9, which correspond to E3, G3, C4 and D4.

Ryg's 44.1 kHz formula presented in the third video contains two different melody generators:

((t*("36364689"[t>>13&7]&15))/12&128)
+(((((t>>12)^(t>>12)-2)%11*t)/4|t>>13)&127)

The first generator, in the first half of the formula, is based on a string constant that contains a straight-forward list of pitches. This list is used for the bass pattern. The other generator, whose core is the subexpression ((t>>12)^(t>>12)-2)%11, is more interesting, as it generates a rather deep self-similar melody structure with just three operators (subtraction, exclusive or, modulo). Rather impressive despite its profound repetitiveness. Here's an analysis of the series it generates:

It is often a good idea to post-process the waveform output of a plain t* formula. The sawtooth wave tends to produce a lot of aliasing artifacts, particularly at low sampling rates. Attaching a '&128' or '&64' in the end of a t* formula switches the output to square wave which usually sounds a little bit cleaner. An example of this would be Niklas Roy's t*(t>>9|t>>13)&16 which sounds a lot noisier without the AND (although most of the noise in this case comes from the unbounded multiplication arithmetic, not from aliasing).

Bitwise waveforms and harmonies

Another class of formulas that is very prominent among the short ones is the bitwise formula. At its purest, such a formula only uses bitwise operations (shifts, negation, AND, OR, XOR) combined with constants and t. A simple example is t&t>>8 -- the "Sierpinski Harmony". Sierpinski triangles appear very often in plotted visualizations of bitwise waveforms, and t&t>>8 represents the simplest type of formula that renders into a nice Sierpinski triangle.

Bitwise formulas often sound surprisingly multitonal for their length. This is based on the fact that an 8-bit sawtooth wave can be thought of consisting of eight square waves, each an octave apart from its neighbor. Usually, these components fuse together in the human brain, forming the harmonics of a single timbre, but if we turn them on and off a couple of times per second or slower, the brain might perceive them as separate tones. For example, t&48 sounds quite monotonal, but in t&48&t>>8, the exactly same waveform sounds bitonal because it abruptly extends the harmonic content of the previous waveform.

The loudest of the eight square-wave components of an 8-bit wave is, naturally, the one represented by the most significant bit (&128). In the sawtooth wave, it is also the longest in wavelength. The second highest bit (&64) represents a square wave that has half the wavelength and amplitude, the third highest halves the parameters once more, and so on. By using this principle, we can analyze the musical structure of the Sierpinski Harmony:


The introduction of ever lower square-wave components can be easily heard. One can also hear quite well that every newly introduced component is considerably lower in pitch than the previous one. However, if we include a prime multiplier in the Sierpinski Harmony, we will encounter an anomaly. In (t*3)&t>>8, the loudest tone actually goes higher at a specific point (and the interval isn't an octave either).

This phenomenon can be explained with aliasing artifacts and how they are processed by the brain. The main wavelength in t*3 is not constant but alternates between two values, 42 and 43, averaging to 42.67 (256/3). The human mind interprets this kind of sound as a waveform of the average length (42.67 samples) accompanied by an extra sound that represents the "error" (or the difference from the ideal wave). In the t*3 example, this extra sound has a period of 256 samples and sounds like a buzzer when listened separately.

The smaller the wavelengths we are dealing with are, the more prominent these aliasing artifacts become, eventually dominating over their parent waveforms. By listening to (t*3)&128, (t*3)&64 and (t*3)&32, we notice an interval of an octave between them. However, when we step over from (t*3)&32 to (t*3)&16, the interval is definitely not an octave. This is the threshold where the artifact wave becomes dominant. This is why t&t>>8, (t*3)&t>>8 and (t*5)&t>>8 sound so different. It is also the reason why high-pitched melodies may sound very detuned.

Variants of the Sierpinski harmony can be combined to produce melodies. Examples of this approach include:

t*5&(t>>7)|t*3&(t*4>>10) (from miiro)

(t*5&t>>7)|(t*3&t>>10) (from viznut)

t*9&t>>4|t*5&t>>7|t*3&t/1024 (from stephth)

Different counters are the driving force of bitwise formulas. At their simplest, counters are just bitshifted versions of the main counter (t). These are implicitly synchronized with each other and work on different temporal levels of the musical piece. However, it has also been fruitful to experiment with counters that don't have a simple common denominator, and even with ones whose speeds are nearly identical. For example, t&t%255 brings a 256-cycle counter and a 255-cycle counter together with an AND operation, resulting in an ambient drone sound that sounds like something achievable with pulse-width modulation. This approach seems to be more useful for loosely structured soundscapes than clear-cut rhythms or melodies.

Some oneliner songs attach a bitwise operation to a melody generator for transposing the output by whole octaves. A simple example is Rrrola's t*(0xCA98>>(t>>9&14)&15)|t>>8 which would just loop a simple series of notes without the trailing '|t>>8'. This part gradually fixes the upper bits of the output to 1s, effectively raising the pitch of the melody and fading its volume out. Also the formulas from Ryg and Kb in my third video use this technique. The most advanced use of it I've seen so far, however, is in Mu6k's song (the last one in the 3rd video) which synthesizes its lead melody (along with some accompanying beeps) by taking the bassline and selectively turning its bits on and off. This takes place within the subexpression (t>>8^t>>10|t>>14|x)&63 where the waveform of the bass is input as x.

Modular wrap-arounds and other synthesis techniques

All the examples presented so far only use counters and bitwise operations to synthesize the actual waveforms. It's therefore necessary to talk a little bit about other operations and their potential as well.

By accompanying a bitwise formula with a simple addition or substraction, it is possible to create modular wrap-around artifacts that produce totally different sounds. Tiny, nearly inaudible sounds may become very dominant. Harmonious sounds often become noisy and percussive. By extending the short Sierpinski harmony t&t>>4 into (t&t>>4)-5, something that sounds like an "8-bit" drum appears on top of it. The same principle can also be applied to more complex Sierpinski harmony derivatives as well as other bitwise formulas:

(t*9&t>>4|t*5&t>>7|t*3&t/1024)-1

I'm not going into a deep analysis of how modular wrap-arounds affect the harmonic structure of a sound, as I guess someone has already done the math before. However, modular addition can be used for something that sounds like oscillator hard-sync in analog synthesizers, although its technical basis is different.

Perhaps the most obvious use for summing in a softsynth, however, is the one where modular wrap-around is not very useful: mixing of several sound sources together. A straight-forward recipe for this is (A&127)+(B&127), which may be a little long-winded when aiming at minimalism. Often, just a simple XOR operation is enough to replace it, although it usually produces artifacts that may sound good or bad depending on the case. XOR can also be used for effects that sound like hard-sync.

Of course, modular wrap-around effects are also achievable with multiplication and division, and on the other hand, even without addition or subtraction. I'll illustrate this with just a couple of interesting-sounding examples:

t>>4|t&((t>>5)/(t>>7-(t>>15)&-t>>7-(t>>15))) (from droid, js/as only)

(int)(t/1e7*t*t+t)%127|t>>4|t>>5|t%127+(t>>16)|t (from bst)

t>>6&1?t>>5:-t>>4 (from droid)

There's a lot in these and other synthesis algorithms that could be discussed, but as they already belong to a zone where traditional sound synthesis lore applies, I choose to go on.

Deterministic composition

When looking at the longest formulas in the collection, it is apparent that there's a lot of intelligent design behind most of them. Long constants and tables, sometimes several of them, containing scales, melodies, basslines and drum patterns. The longest formula in the collection is "Long Line Theory", a cover of the soundtrack of the 64K demo "Chaos Theory" by Conspiracy. The original version by mu6k was over 600 characters long, from which the people on Pouet.net optimized it down to 300 characters, with some arguable quality tradeoffs.

It is, of course, possible to synthesize just about anything with a formula, especially if there's no upper limit for the length. Synthesis and sequencing logic can be built section by section, using rather generic algorithms and proven engineering techniques. There's no magic in it. But on the other hand, there's no magic in pure non-determinism either: it is very difficult to find anything outstanding with totally random experimentation after the initial discovery phase is over.

Many of the more sophisticated formulas seem to have a good balance between random experimentation and deterministic composition. It is often apparent in their structure that some elements are results of random discoveries while others have been built with an engineer's mindset. Let's look at Mu6k's song (presented in the end of the 3rd video, 32 kHz):

(((int)(3e3/(y=t&16383))&1)*35) +
(x=t*("6689"[t>>16&3]&15)/24&127)*y/4e4 +
((t>>8^t>>10|t>>14|x)&63)

I've split the formula on three lines according to the three instruments therein: drum, bass and lead.

My assumption is that the song has been built around the lead formula that was discovered first, probably in the form of t>>6^t>>8|t>>12|t&63 or something (the original version of this formula ran at 8 kHz). As usual with pure bitwise formulas, all the intervals are octaves, but in this case, the musical structure is very nice.

As it is possible to transpose a bit-masking melody simply by transposing the carrier wave, it's a good idea to generate a bassline and reuse it as the carrier. Unlike the lead generator, the bassline generator is very straight-forward in appearance, consisting of four pitch values stored in a string constant. A sawtooth wave is generated, stored to a variable (so that it can be reused by the lead melody generator) and amplitude-modulated.

Finally, there's a simple drum beat that is generated by a combination of division and bit extraction. The extracted bit is scaled to the amplitude of 35. Simple drums are often synthesized by using fast downward pitch-slides and the division approach does this very well.

In the case of Ryg's formula I discussed some sections earlier, I might also guess that the melody generator, the most chaotic element of the system, was the central piece which was later coupled with a bassline generator whose pitches were deliberately chosen to harmonize with the generated melody.

The future

I have been contacted by quite many people who have brought up different ideas of future development. We should, for example, have a social website where anyone could enter new formulas, listen to the in a playlist-like manner and rate them. Another branch of ideas is about the production of new rateable formulas by random generation or by breeding old ones together with genetic algorithms.

All of these ideas are definitely interesting, but I don't think the time is yet right for them. I have been developing my audiovisual virtual machine, which is the main reason why I did these experiments in the first place. I regard the current concept of "oneliner music" as a mere placeholder for the system that is yet to be released. There are too many problems with the C-like infix syntax and other aspects of the concept, so I think it's wiser to first develop a better toy and then think about a community mechanism. However, these are just my own priorities. If someone feels like building the kind of on-line community I described, I'll support the idea.

I've mentioned this toy before. It was previously called EDAM, but now I've chosen to name it IBNIZ (Ideally Bare Numeric Impression giZmo). One of the I letters could also stand for "immediate" or "interactive", as I'm going to emphasize an immediate, hands-on modifiability of the code. IBNIZ will hopefully be relevant as a demoscene platform for extreme size classes, as a test bed for esoteric algorithmic trickery, as an appealing introduction to hard-core minimalist programming, and also as a fun toy to just jam around with. Here's a little screenshot of the current state:


In my previous post, I mentioned the possibility of opening a door for 256-byte demos that are interesting both graphically and musically. The oneliner music project and IBNIZ will provide valuable research for the high-level, algorithmic aspects of this project, but I've also made some
hands-on tests on the platform-level feasability of the idea. It is now apparent that a stand-alone MS-DOS program that generates PCM sound and synchronized real-time graphics can easily fit in less then 96 bytes, so there's a lot of room left for both music and graphics in the 256-byte size
class. I'll probably release a 128- or 256-byte demo as a proof-of-concept, utilizing something derived from a nice oneliner music formula as the soundtrack.

I would like to thank everyone who has been interested in the oneliner music project, as all the hype made me very determined to continue my quests for unleashing the potential of the bit and the byte. My next post regarding this quest will probably appear once there's a version of IBNIZ worth releasing to the public.

20 comments:

pac said...

"There are too many problems with the C-like infix syntax..."
At this level, assembly is getting closer and closer. Flow control in one or two instructions (bytes!), and you get the power of recursion etc.

Assembly compiled on-the-fly, with the immediate audiovisual feedback like we see in shader editors ? How awesome would that be ? Of course it's a bit dry but hey we're doing bytes here.

Anonymous said...

This is fantastic. This post reminds me very much of A.K. Dewdney's "Computer Recreations" column in Scientific American magazine, and that's a *very* good thing!

viznut said...

@pac: The language I've designed for the IBNIZ virtual machine will basically be a Forth variant with one character per instruction. I like Forth very much as is has the concreteness of assembly combined with a Lisp-like purity. Stack machines also tend to have better code densities than register machines, and that's why I've been pondering for a long time about the potential of Forth-like virtual machines in code size minimization.

I would also strongly prefer a stack-based machine to a register-based one in the exploration of algorithmic spaces. Registers tend to be cumbersome at times. And, after all, the kind of code that is short in Forth tends to be short in register-based native instruction sets as well, so disappointments are much less likely than when translating infix formulas into assembly.

reinderien said...

I'm interested in this stuff. I put some of the functions on an Arduino connected to an R2R DAC and a one-transistor audio amp to cut down on the obvious hardware budget waste when doing this on a modern PC. On the other end, I'm in the middle of writing a C++ gadget that does operator overloading and macro voodoo to make these functions modifiable in realtime. It has limitations - it doesn't support floating point, "string memory" (ie. "foo"[bar]), or unary or ternary operators - but still, most of the functions demonstrated in the videos can be represented, and mutated.

Gordonjcp said...

@reinderien I posted a link on an earlier post to an Arduino sketch that uses a PWM output - no need for an R-2R ladder. Due to hardware limitations it can only run at 32kHz (although you can slow down the playback rate to 8kHz with a second counter) which means that very long or complex algorithms won't work.

raer said...

The problem with DOS is only that unfortunately there's not proper sound device for that executably size...

viznut said...

Yeah, COVOX isn't exactly proper, but Dosbox emulates its out-of-the-box so I consider it acceptable. A proof of concept (hooking a timer interrupt) is at http://low.fi/~viznut/256fwrk.com

There are problems with all existing real-world platforms I've encountered. Headers, complex initialization procedures, you name it. Scripting languages and self-compiling source codes have poor code densities compared to native code, and slow-cpu platforms tend to require precalcs and other space-wasting considerations for nearly any decent visual effect.

reinderien said...

@Gordonjcp Forgive me for hesitating to use PWM for anything audio-related. There's risk of improper filtration of the switching frequency, or of overfiltration and loss of some of the audio high-end, especially if the switching freq is barely out of audible range. I'd agree to this if it could be pushed up to (say) 100kHz.

Anyway, one thing I'd love to do is wire the serial MIDI output from my piano to this thing.

Madgarden said...

@viznut, I've almost completed my own FORTH-ish variant of the concept. Currently I have a URL-scheme which codifies the expression rather nicely, and makes things easy to share/load/save. Already we've been linking each other new tunes in email. :) Here's an example URL:

glitch://barbarian!a8k3h1f!aDk5l9rg!ad7ed!p5fn!a6km

erlehmann said...

Madgarden, you should really use an appropriate data URI and not invent a new scheme.

Anonymous said...

I believe that extensive use of bitwise operations limits the music pattern to some power-of-two proportions. Maybe arbitrary numeral systems (including not base-b systems, for example Fibonacci coding) can produce interesting patterns as well?

Alex Greenberg said...

It seems like it would only take one or two more steps to instrumentalize this stuff, give it bass sounds, guitar sounds, whatever.

Rodrigo Siqueira said...

Bitwise ops are now available in the new version of SuperCollider audio synthesis programming language. They even called it "8-bit magic", check the Byte Beat great example and their announcement:
http://doc.sccode.org/Guides/News-3_5.html#Bitwise%20ops

May be now is the time to mix and post-process those 8-bit equations with traditional SuperCollider functions.

rottweiler puppies Miami said...

nice

Richard Southwell said...

This is awesome. I love the `put a little in, get a lot out' mentality of these programs. Reminds me of Stephen Wolfram's `A new kind of science'. I've been making simple programs that make complex networks, but that is more visual.

http://www.youtube.com/watch?v=26_mGoLco4U&feature=plcp

I find this music inspiring.

The_Cjay said...

Well.. If it will be useful:

I've just discovered that adding |(t>>4) adds "kick drum" to melody known as 4x4 kick. And in case of this I've constructed the formula which represents all acid-house tracks since 90s :) Just kidding.

Here is it: (t>>(t>>5*(t>>13)%8))|(t>>4)

Eiyeron Fulmincendii said...

Left : w=t>>9,k=32,m=2048,a=1-t/m%1,y=[3,3,4.7,2][p=w/k&3]*t/4,h="IQNNNN!!]]!Q!IW]WQNN??!!W]WQNNN?".charCodeAt(w/2&15|p/3<<4)/33*t-t,s=y*.98%80+y%80+(w>>7&&a*(h%k+h*1.99%k+h*.49%k+h*.97%k-64)*(4-a-a)),s*s>>14?127:s

Right : w=t>>9,k=32,m=2048,a=1-t/m%1,d=(14*t*t^t)%m*a,s=(w>>7&&a*((5*t%m*a&128)*(0x53232323>>w/4&1)+(d&127)*(0xa444c444>>w/4&1)*1.5+(d*w&1))),s*s>>14?127:s

Stereo Optimized LongLine Theory!

Jonatan Liljedahl said...

@Rodrigo, Actually I added the bitwise ops to SuperCollider after finding out about bytebeat synthesis by reading viznut's blog here :)

BTW, I also made a bytebeat iOS app. Somewhat similar to Madgardens GlitchMachine but with "normal" C-like syntax. It's called Bitwiz Audio Synth: http://kymatica.com/Software/BitWiz

Traveler said...

Made a PIC microcontroller implementation which produces pretty interesting sound patterns: http://www.youtube.com/watch?v=Mo8V51QxmRk

Code and schematics also in the blog.
Saludos!

Eiyeron Fulmincendii said...

Long Line Theory (original non comrpessed version from pouet.net), finally in C!

https://gist.github.com/Eiyeron/7986703

Enjoy!