[QUIZ#12] Perkussionist


#1
Quiz #12
Der Perkussionist

Regeln
Die Regeln und der Ablauf der Quizrunde können in der entsprechenden Ankündigung eingesehen werden. Bitte lest sie euch aufmerksam durch, da sie alle wichtigen Informationen enthält. Lösungsansätze können und dürfen auch schon vorab untereinander ausgetauscht und diskutiert werden, allerdings nicht öffentlich im Forum. Verwendet stattdessen bitte private Nachrichten oder schaut im Chat vorbei.

Abgabe
Die Abgabe erfolgt wie immer im Abgabeforum. Abgabefrist ist Samstag, der 14. November 2009 um ca. 23 Uhr.

Die Aufgabe
Eure Aufgabe besteht diesmal darin, einen simplen digitalen Drumcomputer zu programmieren. Aus einigen Audiosamples von Instrumenten und einem vorgegebenen Ablauf soll eine Audiodatei erstellt werden.

Eingabeformat
Die Eingabe erfolgt durch eine Textdatei, die wie folgt aufgebaut ist:
Code:
<Beats pro Minute>
<Ticks pro Beat>
<Pfad zum Audiosample von Instrument 1>
<Pfad zum Audiosample von Instrument 2>
...
<Pfad zum Audiosample von Instrument n>

<Ablauf Instrument 1>
<Ablauf Instrument 2>
...
<Ablauf Instrument n>
Über die Parameter <Beats pro Minute> und <Ticks pro Beat> soll die Abspielgeschwindigkeit steuerbar sein. Ein Tick stellt die kleinste Zeiteinheit dar (wenn man einen Beat z.B. als Viertelnote interpretiert und <Ticks pro Beat> auf 4 gesetzt ist, entspricht ein Tick also einer Sechzehntel-Note).

Jede Ablauf-Zeile besteht aus einer Sequenz von Leerzeichen oder Nicht-Leerzeichen. Das i-te Zeichen gibt an, ob das jeweilige Instrument im i-ten Tick gespielt werden soll (Nicht-Leerzeichen) oder nicht (Leerzeichen). Beispiel:
Code:
  X X   XX
Das Instrument hat erst zwei Ticks Pause, dann wird es gespielt. Vor dem nächsten Einsatz pausiert das Instrument einen Tick. Nach weiteren drei Ticks Pause wird es in den zwei darauf folgenden Ticks gespielt.

Die Audiosamples liegen im WAVE-Format vor. Die Daten sind stets PCM-codiert, bei einer Auflösung von 16 Bit pro Sample, einer Abtastrate von 44.100 Hz und einem Kanal (mono). Ihr könnt davon ausgehen, dass die Abtastwerte ab dem Offset 44 bis zum Ende der Datei vorliegen (als Folge von 16-Bit signed Integers in Little Endian). Ihr müsst den RIFF-Header also nicht auswerten.

Ausgabeformat
Als Ausgabe soll wiederum eine WAVE-PCM-Datei erzeugt werden, mit demselben Format wie die Audiosamples (16 Bit, 44.100 Hz, Mono). Die Samples der einzelnen Instrumente sollen darin entsprechend ihrer Ablauf-Zeile erklingen. Als Header für die Datei könnt ihr folgenden String verwenden:
Code:
"\x52\x49\x46\x46$size\x57\x41\x56\x45\x66\x6d\x74\x20\x10\x00\x00\x00\x01\x00\x01\x00\x44\xac\x00\x00\x88\x58\x01\x00\x02\x00\x10\x00\x64\x61\x74\x61"
Unmittelbar darauf muss die Größe der Audiodaten in Bytes folgen, kodiert als 32-Bit unsigned Integer in Little Endian. Im Anschluss schreibt ihr einfach die Abtastwerte in die Datei (wieder als Folge von 16-Bit signed Integers in Little Endian). Der Platzhalter $size muss außerdem durch einen 32-Bit unsigned Integer in Little Endian ersetzt werden, der die Dateigröße - 8 angibt.

Stufe 1
In der einfachsten Stufe reicht es, wenn ihr genau ein Instrument unterstützt. Ihr müsst also im wesentlichen nur das Audiosample einlesen und die Abtastwerte in der Ausgabe passend platzieren.

Stufe 2
Die zweite Stufe erfordet, dass beliebig viele Instrumente verwendet werden können. Außerdem soll die Stärke jedes Anschlags (also die Lautstärke) festgelegt werden können. Dies geschieht durch die Zeichen 1 (10%), 2 (20%), ..., 9 (90%) und X (100%).

Erweiterungen
Ideen für mögliche Erweiterungen:
  • Stereo-Ausgabe mit der Möglichkeit, jedes Instrument zu platzieren (z.B. -100 für ganz links, 0 für mittig, 100 für ganz rechts)
  • Zufällige Variationen in Anschlagstärke und Rhythmus (um einen menschlichen Spieler nachzuahmen)
  • Ausbau zu einem Pattern-Sequenzer
  • GUI zur leichteren Eingabe
  • Direkte Ausgabe des Ergebnisses über die Soundkarte

Beispiele
Die Ausgaben wurden nachträglich von einer externen Software in das speicherschonendere OGG-Format konvertiert. Die verwendeten Audiosamples wurden schamlos von Hydrogen übernommen, befinden sich aber auch im Anhang. Weitere Drumkits für eigene Experimente findet ihr auf Sourceforge (in *.tar.gz umbenennen und extrahieren). Ich habe allerdings nicht überprüft, ob diese alle im richtigen Format vorliegen.

Stufe 1:
Code:
80
4
stick_Woody.wav

X X XXX XXXX XX
Ausgabe: Anhang anzeigen simple.ogg.zip

Code:
80
4
sn_Wet_b.wav

X  XX  X X XX
Ausgabe: Anhang anzeigen simple2.ogg.zip

Stufe 2:
Code:
90
8
cra_Rock_a.wav
tom_Rock_mid.wav
hhc_Dry_a.wav
sn_Wet_b.wav
kick_Dry_b.wav

X                               X                               
                                                          X X   
X X X X X X X X X X X X X X X X X X X X X X X X X X X X         
        X               X               X             XXX       
X             X X               X           X X
Ausgabe: Anhang anzeigen advanced.ogg.zip

Code:
90
8
cra_Rock_a.wav
tom_Rock_mid.wav
hhc_Dry_a.wav
sn_Wet_b.wav
kick_Dry_b.wav

X                               X                               
                                                          3 3   
X 5 5 5 X 5 5 5 X 5 5 5 X 5 5 5 X 5 5 5 X 5 5 5 X 5 5 5         
        X               X               X             36X       
X             X X               X           X X
Ausgabe: Anhang anzeigen dynamic.ogg.zip

Weitere Beispiele (automatisch konvertierte Demofiles von Hydrogen, ohne Anspruch auf absolute Übereinstimmung): Anhang anzeigen demos.zip


Und jetzt ran an die Tasten und viel Spaß beim Programmieren!
 

Anhänge

Zuletzt bearbeitet:
#3
Hallo zeja,

ich hab eine Quick&Dirty-Lösung an einem Abend zusammengeschustert. Das Ergebnis waren 60 Zeilen Ruby-Code. Sollte also denk ich schon machbar sein. Wenn nicht, hängen wir einfach noch eine Woche dran, ist ja kein Problem.

Grüße,
Matthias
 

DosCoder

Erfahrenes Mitglied
#10
Hi,
kann man mit BrainFuck Dateien speichern? Wenn ja, wäre es überlegenswert, sich wieder damit zu beschäftigen. :)

Ciao
DosCoder
 
Zuletzt bearbeitet:

kabel2

Erfahrenes Mitglied
#11
Ich sehe, hier gibts Leute die sich unbedingt selbst geißeln wollen...
Für die echte Herausforderung lieber eine Sprache, deren Turing-Vollständigkeit noch nicht bewiesen ist ... gibts sowas überhaupt? :)
 

DosCoder

Erfahrenes Mitglied
#13
Ich sehe, hier gibts Leute die sich unbedingt selbst geißeln wollen...
Für die echte Herausforderung lieber eine Sprache, deren Turing-Vollständigkeit noch nicht bewiesen ist ... gibts sowas überhaupt? :)
Ich weiß ja nicht, was andere Freaks noch so im Keller versteckt halten :D Ich glaube aber nicht, das ich so lange an einem BrainFuck-Programm(oder änlichem) sitzen würde, wenn ich nicht wüsste, dass es funktionieren kann...

Ciao
DosCoder
 
#15
Naja mit Brainfuck kann ich dank Turing-Vollständigkeit alle mathematischen Probleme lösen.

Aber das Arbeiten mit Dateien, Sounds und alles was über mit Zahlen gefüllte Zellen hinausgeht, ist da ja nicht umsetzbar.
 

DosCoder

Erfahrenes Mitglied
#16
Aber ich hoffe, dass sich das mit der Zeit ändert. Leider wird man damit aber dann mehr Zeichen benötigen, und 8 fand ich für eine Programmiersprache sehr passend. :D

Ciao
DosCoder
 

OnlyFoo

Erfahrenes Mitglied
#17
Aber ich hoffe, dass sich das mit der Zeit ändert. Leider wird man damit aber dann mehr Zeichen benötigen, und 8 fand ich für eine Programmiersprache sehr passend. :D

Ciao
DosCoder
Das ist auch garnicht wahr. Man könnte eine Art SysCall implementieren.
zB können wir "Datei öffnen" so implementieren:
  1. Schreibe den Dateinamen, nullterminiert, in die Speicherzellen 2 bis n
  2. Schreibe eine '1' für "open" in die Speicherzelle 1
  3. Erhöhe den Wert in Speicherzelle 0 um 1
  4. Lese das Dateihandle aus Speicherzelle 1

Der Interpreter achtet dann auf veränderungen der Speicherzelle 0. Wenn dort ein "+" ausgeführt wird, führe den Befehl in Speicherzelle 1 + die korrekte Anzahl an Argumenten aus, schreibe das Ergebnis nach Speicherzelle 1und setzte Speicherzelle 0 wieder auf 0, um bereit für den nächsten SysCall zu sein.

So könnte man Dateizugriffe, Graphische Oberflächen, Netzwerkfähigkeit und ähnliches in Brainfuck implementieren, ohne wirklich was an der Sprache zu ändern.

Hmm, ob ich Zeit finde *interessiert guck*
 

DosCoder

Erfahrenes Mitglied
#18
... ohne wirklich was an der Sprache zu ändern...
Außer sie noch unübersichtlicher zu machen. Grafische Oberflächen mit deiner Technik, ohne Objektorientierung! Oder willst du die auch noch irgendwie rein implementieren. Ich wünsch' dir viel Spaß, bitte benachrichtige mich, wenn du fertig bist :D.

Ciao
DosCoder
 

OnlyFoo

Erfahrenes Mitglied
#19
Außer sie noch unübersichtlicher zu machen. Grafische Oberflächen mit deiner Technik, ohne Objektorientierung! Oder willst du die auch noch irgendwie rein implementieren. Ich wünsch' dir viel Spaß, bitte benachrichtige mich, wenn du fertig bist :D.

Ciao
DosCoder

Naja komm, objektorientierte GUI-Programmierung hast du mit der WindowsAPI doch auch nicht.

proof-of-concept: ein simples Brainfuck Programm, was eine Zeile mit einem Dateinamen von der Standardeingabe einließt, dann diese Dtaei öffnet und bis zum EOF (bzw zum ersten 0 byte) ließt

Code:
goto mem 2
>>

read line (the filename)
,----------[++++++++++>,----------]

goto mem 1
<[<]

call syscall 1 (open)
+<+

goto 2 and set mem 2 to 0
>>[-]

move mem(1) to mem(2)
<[->+<]

put 1 to mem(1)
+

do while mem(1) != 0
[
  set mem(1) = 0
  [-]
  
  call syscall 2 (read)
  ++<+

  print the result
  >.
]
Und er zugehörige, grob zusammen geschusterte Interpreter:
Python:
# -*- encoding: utf8 -*-

import re, sys

class Brainfuck( object ):
    def __init__( self ):
        self.code = []
    
    
    def parse( self, source ):
        self.code = []
        stack = []
        
        source = list( re.sub( r'[^+-.,<>\[\]]', "", source ) )
        for char in source:
            if char in "+-":
                self.code.append( ('add', {'+': 1, '-': -1}[char] ) )
            
            if char in '<>':
                self.code.append( ('move', {'>': 1, '<': -1}[char] ) )
            
            if char == '[':
                stack.append( len( self.code ) )
                self.code.append( [ 'push', None ] )
            
            if char == ']':
                last = stack.pop()
                self.code[last][1] = len( self.code ) - last
                self.code.append( ( 'pop', len( self.code ) - last ) )
            
            if char == '.':
                self.code.append( ('io_put', None) )
            
            if char == ',':
                self.code.append( ('io_get', None) )
        
        # print self.code
            
    
    def run( self ):
        code = self.code
        ip = 0
        length = len( code )
        stack = []
        mem = [0] * 30000
        mp = 0
        files = {}
        
        while ip < length:
            op, arg = code[ip]
            #print op, arg, mp
            if op == 'add':
                if mp == 0:
                    syscall = mem[1]
                    if syscall == 1:
                        fname = "".join( map( __builtins__.chr, mem[2: mem.index( 0, 2 ) ] ) )
                        fp = max( [0] + files.keys() ) + 1
                        files[ fp ] = open( fname, "rb" )
                        mem[1] = fp
                    
                    if syscall == 2:
                        fp = files[ mem[2] ]
                        ch = fp.read(1)
                        mem[1] = ord(ch) if ch else 0
                    
                else:
                    mem[mp] = (mem[mp] + arg) % 255
                
            elif op == 'move':
                mp = (mp + arg) % 30000
            
            elif op == 'push':
                if mem[mp] == 0:
                    ip += arg
            
            elif op == 'pop':
                if mem[mp] != 0:
                    ip -= arg
                    
            elif op == 'io_put':
                sys.stdout.write( __builtins__.chr(mem[mp]) )
            
            elif op == 'io_get':
                chr = sys.stdin.read(1)
                mem[mp] = ord( chr ) if chr else 0
            
            ip += 1
        
        # print mem[0:20]


if __name__ == '__main__':
    source = "".join( open( sys.argv[1] ).readlines() )
    
    bf = Brainfuck()
    bf.parse( source )
    bf.run()
Code:
olli@desktop:/tmp$ echo 'hallo tutorials.de!' > input.txt
olli@desktop:/tmp$ python brainfuck.py open.bf
input.txt
hallo tutorials.de!
olli@desktop:/tmp$
 
Zuletzt bearbeitet:

DosCoder

Erfahrenes Mitglied
#20
Hi,
hast du eigentlich sonst nichts zu tun? :D
Und zum Thema Objektorientierung:
objektorientierte GUI-Programmierung hast du mit der WindowsAPI doch auch nicht...
deshalb verwende ich sie ja auch nicht, nicht umsonst bin ich auch überzeugter Pinguin!

Zurück zu BrainFuck:
Wende dich doch mal an Urban Müller, vielleicht kauft der dir deinen Interpreter ab. Da der ja mit Python geschrieben ist, hat man dadurch auch endlich Plattformunabhängigkeit. Ist also noch eine Verbesserung.

Ciao
DosCoder
 

Neue Beiträge