blog · git · desktop · images · contact & privacy · gopher


„Algorithmic music“ für nixers.net

Bei nixers.net läuft derzeit ein Wettbewerb: Wer macht das beste Intro für den Podcast?

Ich habe teilgenommen und zwar hiermit:

Künstlerisch sind das keine grandiosen Meisterwerke. Interessant dabei ist aber, dass die Jingles mit sehr knappem C-Code erstellt wurden. Und zwar mit diesem:

#include <stdio.h>

int
main()
{
    int t;

#if 0
    /* Intro (8kHz) */
    for (t = 0; t < 32768; t++)
        putchar((unsigned char)(t | (-t >> 8)) - 128);
    for (t = 0; t < 65536; t++)
        putchar((unsigned char)((t * 4 | t * 2 | t) | (t >> 4) | (t >> 8)) / 2);
#endif

#if 0
    /* Intro (44kHz) */
    for (t = 0; t < 4 * 32768; t++)
        putchar((unsigned char)((t | (-t >> 8)) >> 2) - 128);
    for (t = 0; t < 4 * 65536; t++)
        putchar((unsigned char)(((t * 4 | t * 2 | t) | (t >> 4) | (t >> 8)) >> 2) / 2);
#endif

#if 0
    /* Outro (8kHz) */
    for (t = 0; t < 65536; t++)
        putchar((unsigned char)(t | (-t >> 10)) - 128);

    for (t = 32768; t < 65536; t++)
        putchar((unsigned char)((t * 8) | (t >> 4) | (t >> 8)) / 2);
#endif

#if 0
    /* Outro (44kHz) */
    for (t = 0; t < 4 * 65536; t++)
        putchar((unsigned char)((t | (-t >> 10)) >> 2) - 128);

    for (t = 4 * 32768; t < 4 * 65536; t++)
        putchar((unsigned char)(((t * 8) | (t >> 4) | (t >> 8)) >> 2) / 2);
#endif

    return 0;
}

Vor einiger Zeit habe ich etwas über „algorithmic music“ gelesen, es bis dato aber noch nicht selbst ausprobiert gehabt. Das war also die perfekte Gelegenheit.

Grundlagen

Der Code schreibt Daten nach stdout. Für sich genommen, haben diese Daten keine inhärente Bedeutung. Man kann sie aber als „raw 8 bit unsigned PCM audio“ interpretieren und wenn man das tut, kann man das Jingle hören. Unter GNU/Linux geht das so:

$ ./sound | aplay -q -r 8000 -f U8

Natürlich könnte man auch eine andere Sampling Rate verwenden, dann wird das Liedchen schneller und höher. Ich bleibe aber zunächst immer bei 8kHz. Man könnte auch ein anderes Format als U8 verwenden, aber im nächsten Abschnitt wird deutlich, wieso das durchaus sinnvoll ist.

Und wenn man es in eine Datei schreibt, kann man es danach in Audacity importieren:

$ ./sound >audio.raw

Analyse des Intros

Grundidee und erster Teil

Allem liegt dieser Baustein zugrunde:

#include <stdio.h>

int
main()
{
    int t;

    for (t = 0; ; t++)
        putchar(t);
}

So hört sich das an: sawtooth.ogg.

Es ist ein Integer, der hochzählt. Ein magischer Moment passiert in putchar(): Bevor die Daten nach stdout geschrieben werden, wird t zu einem unsigned char (daher oben U8) gecastet. Es entsteht also folgende Ausgabe:

0x00 0x01 0x02 0x03 ... 0xFD 0xFE 0xFF 0x00 0x01 0x02 ...
                                  ^^^^^^^^^

Die wichtige Stelle habe ich markiert. Nach 0xFF kommt 0x00, aber der tatsächliche Wert von t ist 0x100, nicht 0x00. Wir haben also mehr Bits zur Verfügung, mit denen wir arbeiten können, als tatsächlich in der Ausgabe zu sehen sind. Später werden wir von denen auch Gebrauch machen.

Das heißt auch, dass eine Operation wie 123 * 32 ein „hörbares“ Ergebnis von 96 produziert – alles, was wir tun, geschieht modulo 256. Das ist einer der Gründe für viele unerwartete Sound-Effekte.

Weiter geht’s. Man schaue sich das an:

#include <stdio.h>

int
main()
{
    int t;

    for (t = 0; ; t++)
        putchar(t >> 8);
}

Kurz erinnern, dass ein reines t aufsteigende Zahlen sind, ein Sägezahnmuster. Was passiert jetzt, wenn wir die Bits nach rechts verschieben? Zunächst verwerfen wir natürlich die unteren acht Bit. Wir reduzieren dadurch aber auch die Frequenz des Sägezahnmusters: Bis zum ersten „Overflow“ (0xFF0x00) erhalten wir nur Nullen, danach nur 0x01 bis zum zweiten Overflow und so weiter.

Durch >> 8 reduziert sich die Frequenz um einen Faktor von 256, was man dann nicht mehr hören kann. Aber einen Screenshot kann man zeigen:

scrot-t-8.png

Wie man sehen kann, ist das keine gerade Linie, sondern viele kleine Treppenstufen. Das liegt daran, dass wir nur Integer Arithmetic verwenden. Ein weiterer Grund für viele nette Effekte. Ausdrücke wie t >> 8 verbleiben auf demselben numerischen Wert für einige Millisekunden. Das ist die Basis für die Illusion von unterschiedlichen Tönen, anstatt einfach nur sanft „gleitenden“ Frequenzgängen. Man schaue hier:

#include <stdio.h>

int
main()
{
    int t;

    for (t = 0; ; t++)
        putchar(t | (-t >> 8));
}

Das ist der erste Teil des tatsächlichen Nixers-Intros. Was passiert hier? -t >> 8 is dasselbe wie t >> 8, bloß gespiegelt an der x-Achse. Die Werte starten also bei 0xFF (fast – ignorieren wir mal die erste Null) und werden langsam kleiner bis hin zu 0x00. Danach „ver-oder-n“ wir das bitweise mit t. Und an diesem Punkt wird es wirklich interessant.

So hört sich der Code da oben an: intro-part-1.ogg.

Sehr unerwartet, oder? Versuchen wir, herauszufinden, was dieses Muster verursacht.

-t >> 8 ist:

0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF ... 0xFF
0xFE 0xFE 0xFE 0xFE 0xFE 0xFE 0xFE 0xFE 0xFE 0xFE 0xFE ... 0xFE
0xFD 0xFD 0xFD 0xFD 0xFD 0xFD 0xFD 0xFD 0xFD 0xFD 0xFD ... 0xFD
...

t ist:

0x00 0x01 0x02 0x03 0x04 0x05 0x06 0x07 0x08 0x09 0x10 ... 0xFF
0x00 0x01 0x02 0x03 0x04 0x05 0x06 0x07 0x08 0x09 0x10 ... 0xFF
0x00 0x01 0x02 0x03 0x04 0x05 0x06 0x07 0x08 0x09 0x10 ... 0xFF
...

Wendet man die Oder-Funktion auf diese beiden Datenströme an, dann passiert erst einmal nichts, solange wie -t >> 8 noch auf 0xFF steht. Sobald es aber darunter fällt, ist plötzlich Platz vorhanden – „freie“ Bits, die von der Oder-Funktion tatsächlich beeinflusst werden. Sagen wir mal, -t >> 8 steht auf 0xFE, dann erhält man nach dem Oder:

0xFE 0xFF 0xFE 0xFF 0xFE 0xFF 0xFE 0xFF 0xFE 0xFF ...

Ein Muster! Wenn man sich das anhören würde, wäre es eine sehr hohe Frequenz, aber auch extrem leise. Ein anderes Beispiel, -t >> 8 steht auf 0xF8:

0xF8 0xF9 0xFA 0xFB 0xFC 0xFD 0xFE 0xFF 0xF8 0xF9 ...

Jetzt kann man schon das ursprüngliche Sägezahnmuster von t wiederfinden, aber es ist immer noch eine deutlich höhere Frequenz als t selbst: Ein Durchlauf geht von 0xF8 bis 0xFF, das sind nur acht Bytes im Gegensatz zu den vollen 255 Bytes von t. Und die Amplitude ist deutlich größer, als sie beim Wechsel 0xFF ←→ 0xFE oben war.

Anders formuliert, ein abnehmendes -t >> 8 schafft Raum für immer mehr Töne, wobei niedrigere Frequenzen später dominieren.

Der zweite Teil

Das Übereinanderlegen von Funktionen ist wieder der Knackpunkt.

Fangen wir damit an:

#include <stdio.h>

int
main()
{
    int t;

    for (t = 0; ; t++)
        putchar(t * 16 | t);
}

Wie hört sich das wohl an? Ich hatte zunächst erwartet, zwei Sägezahnmuster vorzufinden, einmal die Grundfrequenz und einmal das 16-fache davon. Ist auch nahe dran. Hier ist ein Screenshot:

t-and-16.png

Das „große“ Sägezahnmuster ist t. „Oben drauf“ ist dann etwas, das schon irgendwie nach t * 16 aussieht. Man erhält aber auch sehr viele „Artefakte“, die dann in vielen Obertönen resultieren.

Und so hört sich das an:

t-and-16.ogg

Der Ausdruck t * 4 | t * 2 | t, den ich im eigentlichen Intro benutze, ist also nichts weiter als ein „gesättigtes“ Sägezahnmuster.

In einem zweiten Schritt wird jenes Sägezahnmuster dann mit (t >> 4) | (t >> 8) „ver-oder-t“. Schauen wir uns erstmal dieses zweite Muster getrennt an. Hier ist ein Screenshot von t >> 4, t >> 8 und beiden zusammen mit der Oder-Funktion:

t-4-and-t-8.png

Auch hier fungiert die Oder-Funktion als „Overlay“, die als Nebeneffekt viele Obertöne generiert. Man kann in diesem Screenshot schon fast die einzelnen Bits kippen sehen. Überraschenderweise ist das Ergebnis kein chaotischer Lärm:

t-4-and-t-8.ogg

Man kann hier sogar schon eine kleine Melodie hören. Wichtiger aber ist, dass t >> 4 einen „Beat“ erzeugt. Ganz schnell folgender Code eingeschoben:

#include <stdio.h>

int
main()
{
    int t;

    for (t = 0; ; t++)
        putchar((t * 4 | t * 2 | t) | (t >> 4));
}

Klingt so: drum-loop.ogg. Eine Bass Drum und ein Keyboard. Wer hätte das gedacht?

t >> 8 funktioniert dann wieder wie -t >> 8 im ersten Teil, nur umgekehrt: Es lässt niedrige Frequenzen (den „Beat“) am Anfang durch und blockiert diese erst später.

Beide Bitshifts zusammen erzeugen letztendlich kleine Variationen in der Melodie und einige Obertöne.

Der gesamte zweite Teil des Intros:

#include <stdio.h>

int
main()
{
    int t;

    for (t = 0; ; t++)
        putchar((t * 4 | t * 2 | t) | (t >> 4) | (t >> 8));
}

intro-part-2.ogg

Begrenzung und Zentrierung

Das Wichtigste zuerst: Der Code bisher bestand nur aus Endlosschleifen. Das ist natürlich für ein „kurzes Podcast-Intro“ nicht sonderlich geeignet. :-) Man muss den Schleifen also Grenzen geben. Ganz ehrlich, das probiert man am besten einfach aus oder fügt dem Code Debug-Prints hinzu, die die aktuelle Position von t ausgeben. Vielfache von Zwei werden höchstwahrscheinlich das Ergebnis sein. Die richtigen Werte findet man dann recht schnell:

#include <stdio.h>

int
main()
{
    int t;

    for (t = 0; t < 32768; t++)
        putchar(t | (-t >> 8));
    for (t = 0; t < 65536; t++)
        putchar((t * 4 | t * 2 | t) | (t >> 4) | (t >> 8));

    return 0;
}

Das ist aber nur die halbe Miete. Hören wir uns mal genau diesen Code an: intro-unaligned.ogg. Am Anfang und am Ende kann man deutlich ein „Blopp“ hören. Das wollen wir loswerden.

Kurz einen Blick in den Hexdump unserer Daten geworfen und man versteht, was da passiert:

00000000: 00ff ffff ffff ffff ffff ffff ffff ffff  ................
00000010: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000020: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00000030: ffff ffff ffff ffff ffff ffff ffff ffff  ................
...

Wenn man das als Waveform interpretiert, ist das ein großer Sprung: Direkt von vollem negativen Ausschlag (0x00) zu vollem positiven Ausschlag (0xFF). Etwas ähnliches passiert ganz am Ende:

...
00017fc0: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00017fd0: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00017fe0: ffff ffff ffff ffff ffff ffff ffff ffff  ................
00017ff0: ffff ffff ffff ffff ffff ffff ffff ffff  ................

Hier gibt es zwar kein 0xFF 0x00, aber die Datei endet immer noch in 0xFF. Wenn der Audioplayer also am Ende angekommen ist und aufhört, dann springen die Lautsprecher vom 0xFF zurück in ihre Neutralstellung bei 0x80. Es knackt.

In einem Screenshot versteht man das Problem auch ganz gut: intro-unaligned.png. Ich hätte gerne, dass das so aussieht: intro-aligned.png. Der erste Teil muss also halb nach unten geschoben werden. Der zweite Teil sollte auch nach unten geschoben werden, damit es am Ende passt, aber das können wir nicht mit einer Subtraktion erreichen, weil wir am Anfang die volle Amplitude ausnutzen. Also teilen wir einfach durch zwei.

Und das war’s auch schon.

#include <stdio.h>

int
main()
{
    int t;

    for (t = 0; t < 32768; t++)
        putchar((unsigned char)(t | (-t >> 8)) - 128);
    for (t = 0; t < 65536; t++)
        putchar((unsigned char)((t * 4 | t * 2 | t) | (t >> 4) | (t >> 8)) / 2);

    return 0;
}

Man beachte, dass ich erst den Cast nach unsigned char gemacht habe. Das ist leicht verständlich: Wir müssen im Wertebereich 0x00 bis 0xFF sein und nicht in der vollen Integer-Range.

Das Outro

… wird als Transferleistung dem Leser überlassen. :-)

Die 44kHz-Versionen

Wie funktioniert das? Eigentlich sehr einfach. Eine höhere Sampling Rate bedeutet, dass man mehr Daten zur Verfügung stellen muss, um dieselbe Zeit abzudecken. Man muss also alles verlangsamen. In unserem Fall kann man dazu einfach einen Bitshift nach rechts durchführen (man erinnere sich an den allerersten Bitshift im ersten Teil). Ferner müssen wir unsere Schleifengrenzen mit vier multiplizieren.

Warum vier? Weil 44kHz genau 4 * 11kHz ist und natürlich ist 11kHz in erster Näherung 8kHz. :-)

Fazit

Das hier ist natürlich keine alles erschöpfende Analyse. Ich glaube aber, dass man nun ein ganz gutes Gespür dafür bekommen hat, was beim eingangs gezeigten C-Code passiert.

Und, ganz ehrlich, versauen wir’s nicht. Einfach mal mit dem Code spielen gehen und sich überraschen lassen. Das ist doch der spaßige Teil. :-)