Entwickler-Ecke :: Thema anzeigen - Adventsgewinnspiel 2008

Gausi - Sa 20.12.08 10:43
Titel: Adventsgewinnspiel 2008 - Tipps zu Paranuss 1

Hallo liebe Nussknacker!

Die Nuss mit dem kaputten Lied ist wohl doch etwas härter als gedacht. Obwohl die eigentlich ganz einfach ist :angel:. Daher geben wir einen kleinen Denkanstoß, der hoffentlich dem einen oder anderen den Weg weist:

Der Nibbler (und dieser Name ist nicht zufällig gewählt) mag sehr gerne Hamburgerz.

Gausi - Do 25.12.08 02:38

So. Die Lösung gibts hier erst etwas später. Ich mach den Tipp erstmal deutlicher, falls jemand sein Brett vorm Kopf selbst zertrümmern will.;-)

Der Nibbler mag also gerne Hamburgerz, ja? Mit Z wie zackzack. Was sagt man, wenn man auf seinen Hamburgerz noch eine Scheibe Käse haben will? Vielleicht: "I can has Cheezeburger?" Und in welchem Zusammenhang kamen in den letzten Wochen diese Dinger (wenn auch nur indirekt) schonmal vor? "Oh yey. Iz gonna luv him and squeez him and call him George." ?

:gruebel:

Ist die richtige Idee so abwegig, wenn man sich die Nibbles (also die halben Bytes) in der Datei mal genauer anschaut (und zwischendurch mal ein paar Bytes auskommentiert, die die MPEG-Frame-Header darstellen, damit ein Player wenigstens ansatzweise was damit anfangen kann)? Meine Güte ... da kann ja die Miezekatze vom Weihnachtsmann schneller denken. :mrgreen:

jaenicke - Do 25.12.08 02:45

Ja, sowas dachte ich mir schon, weil so die Datei abspielbar bleiben konnte. Aber da hatte ich dann vorhin nicht mehr so die Lust mir das MP3 Format genauer anzuschauen. :D
Den grundsätzlichen Aufbau kenne ich ja. Aber wie das genau aussieht hab ich mir halt noch nie angeschaut. ;-)

Xong - Do 25.12.08 03:03

Und wo bleibt da die Quantenverschränkung?
Ich hätte echt auf den Shor-Code getippt. Aber das mit den Tensoren war mir dann doch zu viel...

GTA-Place - Do 25.12.08 03:06

Ich muss das gleich mal ganz ehrlich sagen: Die Idee ist sooo krank, gausi. Wie kommt man auf sowas? o_O Was muss man getrunken haben, um so eine Paranuss zu basteln? :mrgreen:

Martok - Do 25.12.08 04:16

Siiiileent nigght... hooooooly night.....

Kann ich noch ne Antwort nachreichen, das war (fast) ganz allein gemacht :roll:

Das wollen wir in der nächsten Nemp-Version sehen, dass sowas direkt abgespielt werden kann.
:twisted: :twisted:

jaenicke - Do 25.12.08 04:18

Da lag ich ja mit meiner geratenen Lösung ja vom Thema her ähnlich. :D

Ich dachte mir, ne Chance von eins zu nen paar Millionen ist besser als keine und hab geraten. :D

Gausi - Fr 26.12.08 11:06

Dann kommt hier jetzt mal die Lösung zu diesem Rätsel:

Allison Crowe - Silent Night, wie zumindest Martok wohl schon rausgefunden hat.

Klar, der erste Schritt bei sowas ist: Erstmal nen Hexeditor rauskramen und sich die Datei mal genauer ansehen. Hier mal der Anfang der Datei:

Quelltext

1:
2:
3:
4:
5:
6:
7:

FF FB 90 60 04 44 44 44 44 44 44 44 45 14 14 41   ÿû.`.DDDDDDDE..A
44 41 44 44 14 44 44 14 44 44 41 44 44 44 41 44   DADD.DD.DDADDDAD
44 44 44 14 44 44 44 44 14 44 44 44 44 41 44 44   DDD.DDDD.DDDDADD
44 44 44 41 44 44 44 44 44 44 14 44 44 44 44 44   DDDADDDDDD.DDDDD
44 14 44 44 44 44 44 44 41 44 44 44 44 44 44 44   D.DDDDDDADDDDDDD
42 22 22 22 22 22 22 22 36 11 11 11 11 11 11 11   B"""""""6.......
14 44 44 44 44 44 44 44 73 33 33 33 33 33 37 22   .DDDDDDDs333337"

Die ersten 4 Bytes sind ein MPEG-Frame-Header. Im wesentlichen steht in diesen 4 Bytes "Mpeg1, Layer3, 128kBit/s, 44.1kHz, Joint-Stereo" und noch ein kleines bissel mehr. Ist aber auch völlig egal - brauchen wir nicht. Dass mp3-Dateien aus vielen Frames bestehen, kann man glaube ich noch wissen, und vor jedem Frame in diesem kaputten mp3-File steht derselbe Header FF FB 90 60.

Schauen wir uns also den Rest an. Was sehen wir da links? Hinter den ersten 4 Bytes? Nun, zuerstmal jede Menge Vieren (die Null bitte einfach ignorieren, dazu sage ich später noch was :angel:). Dann eine Fünf, ein paar Einsen und Vieren im Wechsel, einige Zweien, eine drei und eine Sechs. Wenn man weiterschaut, findet man außer den Headern immer wieder einsen, zweien, dreien, vierer und siebener. Die 5 und 6 taucht scheinbar nicht mehr auf (außer in der 60 in den Headern). :lupe:

Damit haben wir also herausgefunden, dass die halben Bytes (Nibbles) irgendwie sehr eingeschränkt in ihrer Vielfalt sind. :gruebel:

Jetzt mag der Nibbler laut dem Tipp sehr gerne Hamburgerz. Mit Z am Ende. Wenn man auf einen Hamburger mit Z eine Scheibe Käse drauflegt, hat man einen Cheezeburger. Und da denkt man sich doch: "I are hungry. I can has Cheezeburger?"

So. Lauter halbe Bytes mit Werten von 1,2,3,4,7, und dazu noch je eine 5 und 6? Cheezeburger? Kthx? "Oh yey. Iz gonna luv him and squeez him and call him George..." Miau Miau Mjau Mau? :shock: :eyecrazy: :autsch:

Hmmmm. Könnte es sein, dass der Nibbler, ein Schoßtierchen des Weihnachtsmann bei dessen Miezekatze in der Lehre war und auch gerne programmiert? Mal sehen:

Quelltext

1:
2:
3:
4:
5:
6:
7:

04 44 44 44 44 44 44 44 45 14 14 41                    0++++++++++++++++[>+>++>
44 41 44 44 14 44 44 14 44 44 41 44 44 44 41 44        +++>++++>+++++>++++++>+++++++>++
44 44 44 14 44 44 44 44 14 44 44 44 44 41 44 44        ++++++>+++++++++>++++++++++>++++
44 44 44 41 44 44 44 44 44 44 14 44 44 44 44 44        +++++++>++++++++++++>+++++++++++
44 14 44 44 44 44 44 44 41 44 44 44 44 44 44 44        ++>++++++++++++++>++++++++++++++
42 22 22 22 22 22 22 22 36 11 11 11 11 11 11 11        +<<<<<<<<<<<<<<<-]  // usw.
14 44 44 44 44 44 44 44 73 33 33 33 33 33 37 22

Hm. Könnte sein. 8)

Die Textausgabe eines BF-Interpreters bringt uns hier leider nichts. Ist ja eine Paranuss, und das hier versteckte Brainfuck-Programm hat eine binäre Ausgabe. Wir müssen uns da also selbst etwas bauen. Ich habe mich auf eine sehr rudimentäre BF-Maschine beschränkt. Sie hat ein Band der Größe 16 (Container[i]) und einen Zeiger auf die aktuelle Bandposition PointerPos. Der oben übersetzte Teil des Brainfuck-Codes übersetzt sich zu:

Delphi-Quelltext

1:
2:
3:

for i := 0 to 15 do
    Container[i] := 16*i;
PointerPos := 0;

Daher auch die 0 am Anfang - ich brauchte hier einfach eine grade Anzahl von Symbolen, um das ganze einfacher implementieren zu können.

Joah. Und jetzt lassen wir die Maschine laufen und schreiben die Ausgabe in einen Stream

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:

procedure ParseMpegFrameToStream(aFrame: TBuffer; aStream: TStream);
var i, start: integer;
begin
    // Interpretiert die Daten im Buffer als BF-Dialekt
    // und schreibt die Ausgabe in den Stream.

    // den ersten Teil auslassen, den haben wir oben ja hardgecodet
    start := (170 div 2) + 4; 
    
    for i := start to length(aFrame)-1 do
    begin
        // erstes Nibble
        case aFrame[i] DIV 16 of
            1:  inc(PointerPos)           ; // '>'
            2:  dec(PointerPos)           ; // '<'
            3:  dec(Container[PointerPos]); // '-'
            4:  inc(Container[PointerPos]); // '+'
            5:  ;                           // '['  Hier ignorieren
            6:  ;                           // ']'  - das ist hier nicht vorgesehen
            7:  aStream.Write(Container[PointerPos], SizeOf(Byte)); // '.'
            8:  ;                           //  ','
        else
            ; // nothing
        end;

        // zweites Nibble
        case aFrame[i] MOD 16 of
            1:  inc(PointerPos)           ; // '>'
            2:  dec(PointerPos)           ; // '<'
            3:  dec(Container[PointerPos]); // '-'
            4:  inc(Container[PointerPos]); // '+'
            5:  ;                           // '['  Hier ignorieren
            6:  ;                           // ']'  - das ist hier nicht vorgesehen
            7:  aStream.Write(Container[PointerPos], SizeOf(Byte)); // '.'
            8:  ;                           //  ','
        else
            ; // nothing
        end;
    end;
end;

Und wenn der Rahmen drumherum in etwa so aussieht ...

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:

procedure TForm1.BtnRepair2Click(Sender: TObject);
var LoadStream, SaveStream: TFilestream;
  i: Integer;
  BlockSize: Integer;
  Buffer: TBuffer;
begin
    if OpenDialog1.Execute then
    begin
        repaint;
        // Daten aus Stream lesen
        LoadStream := TFileStream.Create(OpenDialog1.FileName, fmOpenRead or fmShareDenyWrite);

        // Pseudo-BF-Maschine initialisieren
        for i := 0 to 15 do
            Container[i] := 16*i;
        PointerPos := 0;

        // Blocksize initialisieren
        BlockSize := LoadStream.Size;
        Setlength(Buffer, BlockSize);

        // SaveStream erzeugen
        SaveStream  := TFileStream.Create(OpenDialog1.FileName + '.repair2.mp3', fmCreate);

        // Daten lesen 
        LoadStream.Read(Buffer[0], BlockSize);
        ParseMpegFrameToStream(Buffer, SaveStream);

        SaveStream.Free;
        LoadStream.Free;
    end;
end;

... dann sind wir auch schon fertig. Dann nur noch die neue mp3-Datei starten, die Boxen schön aufdrehen und Allison Crowe dabei zuhören, wie sie Silent Night singt. Eine qualitativ bessere Version gibt es z.B. auf ihrer Homepage [http://www.allisoncrowe.com/], oder auf Jamendo [http://www.jamendo.com/de/artist/allison.crowe]. Wer das Lied oder die Sängerin nicht kennt: Tunatic kennt es. ;-)

Zusammengefasst: Das kaputte mp3-File war im Wesentlichen der Code eines Brainfuck-Programms, getarnt als mp3-File. Führt man den Code aus, erzeugt er eine andere mp3-Datei als Ausgabe. - Fertig. :D

Im Anhang ein Lösungprogramm inklusive Quellcode. Variante 1 hatte ich erst angedacht, und später herausgefunden, dass man die Zerlegung in Einzelframes gar nicht benötigt.

jaenicke - Fr 26.12.08 11:36

Interessantes Rätsel, aber da wäre ich ja in hundert Jahren nicht drauf gekommen, dass das BF sein könnte. :shock: :lol:

Dass die Teilchen ziemlich gleich aussehen hab ich auch gesehen, aber auf BF zu kommen... ich glaube das wäre ich nicht.

Xong - Fr 26.12.08 12:27

Nee Gausi...
Was für eine riesen Schweinerei. Das was du da erzählst klingt doch nicht logisch.
Ich erkläre mal die Situation vor dem Tipp:
Folgende Infos schienen mir (potentiell) relevant zu sein:

Nibbler
Quantencomputer und Verschränkung
Verschränkung der Originaldaten mit den vernibbelten Daten

Der Nibbler hat mich überhaupt nicht weitergebracht... Ich hatte keine Ahnung, was es damit auf sich haben könnte, außer dass das Vieh bei Futurama mitgespielt hat und schwarze Löcher *mist*en kann...
Das und der dritte Punkt schienen mir ein guter Ansatz zu sein:
- Ich habe mich über den Shor-Code informiert.
- Ich habe mir die Verschränkung angeschaut.
- Qubits, Quantenteleportation, das ganze Larifari...
- Weitergekommen bin ich trotzdem nicht, sodass ich irgendwann entnervt aufgegeben habe.

Klar ist aufgefallen, dass nur bestimmte Bitkombinationen vorkamen. Für mich schien vor allem relevant, dass die höchstwertigen Bits in den Nibbles immer 0 waren. Aber echt, dass Brainfuck dahinter steckt...

Der Tipp hat auch nicht wirklich viel geholfen. Ich habe mich nur gefragt was dieses Catlol oder Lolcat schon wieder damit zu tun haben soll... Naja, ich finde, das Hauptproblem an diesem Rätsel war die Irreführung mit dem Quantencomputer und der Verschränkung.

Hat trotzdem Spaß gemacht. =)

LG,
Xong

PS: Also ich fand das wirklich zu schwer, aber ich muss auch sagen, dass ich viel dabei gelernt habe. Und ich denke, nächstes Jahr werde ich eine Paranuss dieses Kalibers auch knacken können. Ich hatte halt einfach zu wenig abstrahiert. :D Also weiter so!

jaenicke - Fr 26.12.08 12:59

Xong hat folgendes geschrieben :

Der Tipp hat auch nicht wirklich viel geholfen. Ich habe mich nur gefragt was dieses Catlol oder Lolcat schon wieder damit zu tun haben soll...

Wenn ich das mit den Hamburgerz mit dem anderen Zitat in Verbindung gebracht hätte, dann wäre es mir klar gewesen. Aber ich bin partout nicht darauf gekommen, was das damit auf sich hat. :(

derDoc - Fr 26.12.08 13:07

Dies war sicher eines der besten Rätsel der Entwickler Ecke. Auch wenn ich es nicht bis zur Lösung geschafft habe...

Dass die mp3-Datei keine echte mp3-Datei sah man ja schon an der vorgesehen Spielzeit. Es gibt nicht so viele Lieder mit 8' 47'' 21''' Laufzeit. Und wenn man sich die Bytes ohne Frameheader anschaute sah das dann zumindest meinem Ansatz zum ersten Rätsel wieder sehr ähnlich.
Allerdings bin ich dann nicht auf die Idee gekommen, dass der Brainfuck Code eine binäre Ausgabe sein sollte. Ich hatte an der Stelle mit Base64 oder einer anderen "einfachen" Kodierung gerechnet.

Allein dieses eine Rätsel hat mir die Adventszeit sehr versüßt. Danke dafür.

Martok - Fr 26.12.08 14:50

Völlig absurd war das, nochmal ein BF-Programm zu suchen. Absolut unmöglich, hatten wir ja schon dieses Jahr. Naja :P

Nachdem du hier den 2. Tipp gegeben hattest und die obige Aussage damit wiederlegt war, hab ich das zusammengehackt. Auf das div/mod für die Halbbytes bin ich gar net gekommen^^

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:

const SIZE = 417;
const tbl : string[8] = ' ><-+[].';
                       //01234567
type TFile = array[0..0] of packed record
       header: dword;
       bin: array[0..SIZE-1-4] of byte;
     end;
var theFile: ^TFile;
    ms:TMemoryStream;
    pt:TMemoryStream;
    ny: TNybble;
    i, j, max:integer;
begin
  ms:= TMemoryStream.Create;
  pt:= TMemoryStream.Create;
  try
    ms.LoadFromFile(ExtractFilePath(ParamStr(0))+'kaputtes_lied\kaputtes_Lied.mp3');
    max:= ms.Size div SIZE;
    theFile:= ms.Memory;
    for i:= 0 to max-1 do begin
      for j:= 0 to high(theFile^[i].bin) do begin
        ny:= (theFile^[i].bin[j] and $F0) shr 4;
        pt.Write(tbl[ny+1],1);
        ny:= (theFile^[i].bin[j] and $0F);
        pt.Write(tbl[ny+1],1);
      end;
    end;
    pt.SaveToFile(ExtractFilePath(ParamStr(0))+'kaputtes_lied\out.raw');
  finally
    pt.Free;
    ms.Free;
  end;

Das ganze dann durch den bf-Interpreter jagen:

Konsole

1:	bf out.raw > xx.mp3

Tunatic, um rauszukriegen *wer* das singt, fertig.

Eigentlich einfach.

Wenn nur die Tipps nicht gewesen wären: dass der Nibbler Halbbytes verdreht war von vornherein klar, aber das ganze Quantenkram hat irgendwie nur von der Lösung weggeführt. Und die Hamburgerz... hm, hättest du gleich Cheezburgerz genommen, wärs klar gewesen... aber bei den HamburgerZ hab ich erstmal auf ZLib getippt.

Was mich nur wundert: warum brauchst du die []-Loops nicht?

Gausi - Fr 26.12.08 15:01

Martok hat folgendes geschrieben :

Was mich nur wundert: warum brauchst du die []-Loops nicht?

Die kommen im Code nur am Anfang einmal vor, um den Container zu initialisieren. Ich wollte keinen kompletten BF-Interpreter schreiben und habe daher die Initialisierung über diese Schleife hart übersetzt. Der Rest war dann nur plus/minus Pointerposition/Feldinhalt.

BenBE - Fr 26.12.08 23:52

Gausi hat folgendes geschrieben :

Martok hat folgendes geschrieben :

Was mich nur wundert: warum brauchst du die []-Loops nicht?

Dann hättest Du von Martok's und meiner BF-IDE den CMD-Interpreter hernehmen können, der liefert eine Binär-Ausgabe.

Ich melde hier aber einmal Prior Art an: Das Verstecken von ausführbaren Programmen in Binärdateien um eine andere Binär-Datei dieses Formats zu erzeugen gehört mir und wurde voriges Jahr im Rätsel-Thread [http://www.delphi-forum.de/viewtopic.php?p=408607#408607] vorgestellt.

Xentar - Sa 27.12.08 00:16

Meine Nerven.. ich war ja komplett auf dem Holzweg :D
Mir ist der Name des Tieres schon Mitte Dezember ins Auge gesprungen.. also flink "Nibble" in die Forensuche gehackt.
Bin dann über diesen
http://www.delphi-forum.de/viewtopic.php?t=67880&highlight=nibble
Thread gestolpert, und hab mich schließlich an hier dem Code festgebissen:
http://www.delphi-forum.de/viewtopic.php?p=408259#408259
Hab gedacht, ich müsse nur noch die richtigen Zahlwerte in Zeile 11 und 12 finden, mit denen die einzelnen Bytes mit den nachfolgenden "verrauscht" werden.
Die Ergebnisse im Hex-Editor sahen auch vielversprechend aus - aber eben immer noch nicht hörbar.

Dass der Tipp mit der Katze nochmal auf Brainfuck verweist - darauf bin ich nicht mehr gekommen :(

Trotzdem: Tolles Rätsel, hatte viel Spaß dabei, und kenn nun den Aufbau von MP3 Dateien :D

Fiete - Di 30.12.08 10:41
Titel: Re: Adventsgewinnspiel 2008 - Tipps zu Paranuss 1

Moin an alle Tüftler,
diese Nuß war auch für mich zu hart.
Die Schlüsselwörter Nibble, Quantencomputer und verschränkt hatten mich veranlaßt die Datei zu entschränken, analog zum Händefalten. Erst mit Frames versucht, dann mit benachbarten Bytes - Low- und HighByte vertauscht, ausgetauscht, innerhalb eines Frames, zum Schluß noch benachbarte Frames. Alles nur Knacken :autsch:
Um dennoch wenigstens eine Lösung abzugeben habe ich nach einem Titel mit halber Spieldauer gesucht. Lieber eine falsche Antwort als keine.

Gausi hat uns schön an der Nase rum :beer: geführt.

Kommt gut nach 2009!
Fiete