年賀状ネタばらし: 4日目

さあ、ここで「賀正」というおおきなAAが出てきたのですが、それをよく見るとソースコードになっています。

AAを崩してみると一目瞭然

++++++++++++++++[>++>+++>++++++<<<-]>>++++++++.>++.<<.>-------.>+++
+.<<.>-..<.>.++++++++.<.>------.+.<.>++++.-

どうみてもBrainfuckのソースコードです。

Brainfuck – Wikipedia: http://ja.wikipedia.org/wiki/Brainfuck

やっと僕の大好きなBrainfuckの登場です。

では、実行してみると…

$ bf output
8b 1f 00 08 23 70 4e ff 03 00 ce ed 0a 31 31 02 85 10 d4 e1 62 9e
c1 bc 70 4c 57 27 b2 b0 4c b7 d4 11 71 62 5c 49 db c4 b2 bb 36 16
cd a2 c2 22 35 ff e6 0f f1 4d d2 fa 3e 5a b0 94 9d 24 6f b8 69 1e
d3 a9 9c d7 0d 45 9e 66 47 92 7c eb 5b ba 18 d4 e8 83 ab a2 c6 9e
c9 76 24 55 4f 1c dc f5 ef 8f 3e ff 7f f5 9b 6a e1 87 bb 26 95 72
c9 7d bd 75 f5 fa 00 1e 00 00 00 00 00 00 00 00 00 00 00 00 77 c0
a4 ee 60 f6 00 2a 00 28 00 00

これはバイナリの中身を表示しているようです。

でも、8b 1fなんていうマジックナンバーはありませんよね…. でも、1f 8bならgzipのマジックナンバーです!

これはすでにバイナリ処理された状態のようです。なので、バイナリエディタとかに打ち込んでもだめなのです!1f 8b 08 00っていう風に逆転させてから打ち込んでいくかプログラムに処理させるかしましょう!

こんな感じのコードを組んでやると行けると思います。

#include <stdio.h>

int main(void)
{
 char c;
 FILE *fp;
 fp = fopen("binary", "wb");
 while(scanf("%x", &c) != EOF)
 fwrite(&c, 1, 1, fp);
 fclose(fp);
 return 0;
}

できたデータをfileコマンドでみてみると…

$ file binary
binary: gzip compressed data, from Unix, last modified: Sun Jan 1 00:00:00 2012

2012年の1/1 00:00:00に作られたgzipのアーカイブのようです。

$ mv binary binary.gz
$ gunzip -d binary.gz

現れたファイルをみてみると、tarアーカイブでした。

$ file binary
$ tar xf binary

すると現れるのはmessasgeというテキストファイル!

中身は…

$ cat message
Happy New Year!

これが答えでした!!

年賀状ネタばらし: 3日目

Zipアーカイブを展開すると現れた怪しいファイル、lazyk

これは開くとすぐわかると思うのですが、Lazy Kのソースコードです。

Lazy K – Wikipedia: http://ja.wikipedia.org/wiki/Lazy_K

翻訳: プログラミング言語Lazy K: http://e.tir.jp/wiliki?%CB%DD%CC%F5%3A%A5%D7%A5%ED%A5%B0%A5%E9%A5%DF%A5%F3%A5%B0%B8%C0%B8%ECLazy_K

Lazy Kは、SKIコンビネータのみを実装している純粋関数型言語かつチューリング完全です。遅延評価が行われます。

ソースをちょっと見てみると、こんな感じになっています。

K(I(S(SI(K(S(K(S(S(KS)K)I))(S(SII)I(S(S(KS)K)I)))))(K(S(SI(K(S(K(S(
S(KS)K)I))(S(SII)I(S(S(KS)K)I)))))(K(S(SI(K(S(K(S(S(KS)K)I))(S(SII)
I(S(S(KS)K)I)))))(K(S(SI(K(S(K(S(S(KS)K)I))(S(SII)I(S(S(KS)K)I)))))

見たまんま、SKIと括弧しか書かれていません。

さっそくiroriさんの処理系を落としてきて実行してみましょう。

$ gcc lazyk.c -o lazy
$ ./lazy lazyk
         ++++++
         ++++++
         ++++[>
++>+++>++++++<<<-]>>+++++++   +.>++.<<.>-------.>++++.
<<.>-..<.>.++++++++.<.>----   --.+.<.>++++.-------.<.>
++++.>-.<<.>>+..<<.>----.++   +.<.>---..<.>>---.++.<<.
      >>.-.<         <.>.>-   --.<<.            >+++.-   -.<.>++.--.<.>-.++.<.>++++++.---.<.>----.-.<.>>+
      ++.<++         ++.<.>   >+.<--            -.<.>+   ++++.----.<.>+++++++.>.<<.>>--.<--------.<.>>-.+
      .<<.>+         +++++.   ------            -.<.>+   +++.>.<<.>+.++.<.>-----.+++++.<.>>-.<-----.<.>>.
   <--.<.            >++++.   >+.<<.            >>-.<+                        ++.<.>
   >++.<-            --.<.>   ---..<            .>++++                        ++.---
   ---.<.            >+++++   .----.            <.>+++                        .>-.<<
.>-.++            +++.<.      >>+.--.<<.>>+.<-----.<.>                        >-.<--
.<.>>.            .<<.>+      .+++.<.>-----.+++++.<.>>                        +.+.<<
.>>---            .<----      .<.>>++.<.<.>..<.>+.++.<                        .>>+++
            ..<<.>>-.<+.<.>------.>+.<<.>>.<+                                 .<.>++
            +.>--.<<.>>.<--.<.>>++.-----.<<.>                                 +.>+++
            +.<<.>++.>----.<<.>>+.<-----.<.>+                                 ++++++
            ++.---                     --.<.>                                 +++++.
            >++.<<                     .>----                                 ---.++
            .<.>++                     .>++.<                                 <.>>--
            --.<++.<.>--.+++.<.>--------.>+++                                 .<<.>>-.<++.<.>>---.<
            ++++++.<.>.>++.<<.>>+.<--.<.>----                                 ---.>.<<.>++++.+.<.>+
            +++.>+.<<.>---..<.>--.+++.<.>++.-                                 ------.<.>+++++.>--.<
            <.>>++                     .---.<                                 <.>--.
            >.<<.>                     >.-.<<                                 .>----
            .+++++                     ++.<.>                                 >+++.<
            ----.<.>>+.<++++.<.>.-----.<.>>--                     --.+.<      <.>>-.
            <-.<.>>++.<++++.<.>+++.>++.<<.>>-                     -.<.<.      >--.-.
            <.>----.++.<.>+..<.>-.>+++.<<.>--                     -.>---      .<<.>>
            +.-.<<                     .>>+++                     .<++++      .<.>>-
            .+.<<.                     >+++.>                     .<<.>-      ----.>
            -.<<.>                     >+..<<                     .>++++      .>.<<.
            >>.<--.<.>++++.>----.<<.>---.>-.<                     <.>>++      ++.<--
            ---.<.>+++++++.-.<.>>---..<<.>---                     --.+++      +.<.>+
            ++.----.<.>++.-----.<.>>+.<++++++                     +.<.>-      -.>+.<
               <.>>--               .++.<<                        .>.--.      <.>>++
               .<.<.>               >.----                        -.<<.>      -----.
               .<.>+.               >++++.                        <<.>-.      .<.>..
            <.>..<                     .>..<.            >..<.>..<.>..<.>..<.>..<.>..<.>..<.>..<.>+++++++
            ..<.>>                     --.<--            -----.<.>>--.<++++.<.>>++++..<<.>++.------.<.>>+
            .<++++                     ++.<.>            ------..<.>++.>-----.<<.>--..<.>++.++++++.<.>---
         -----.                           .<.>..
         <-----                           ------
         ------                           -----.

「賀正」というAAが表示されました!

でも、これが答えではないのです。

年賀状ネタばらし: 2日目

年賀状をPietのソースコードとして実行すると以下のような文字列がでてきます。

UEsDBBQAAAAIAC8Cnj/3XIEAGAwAAESrAwAFABwAbGF6eWtVVAkAA4mE/E6NhPxOdXg
LAAEE6AMAAAToAwAA7Zltlhu3DkT/eyUzS+kzP73/vcSOE2vUFGf0AYBVxO1z3osc61
a3moUCyHy8HW8/334ebx+//vH7f7/+/+f7x/vx/v7vvz/ej6t/+ev68zUIRWL4wuXz+
++/vPzxrIJMrcy4tv9Dx/EgqGA8CIp0PxmKtC2hZUQpmen3rtRO0oPiV8tzPPmQMcUr
9bJz3o3WT+RNIRO//CP0+dPXDthK+Ubgffrj42/3+ntJaa0rquV6ZBYEy04D6t/vRCR
Gu+qre3sjNbvjqFul7Gam1CaJ3nZ6bv4WC0stmRXR/fCxIZmvnvmJv3+JRbv5......

最後のほうをみると….

i4uLi4uLi4uLi4uLi4uLi4tr0+vHj38AUEsBAh4DFAAAAAgALwKeP/dcgQAYDAAARKs
DAAUAGAAAAAAAAQAAALSBAAAAAGxhenlrVVQFAAOJhPxOdXgLAAEE6AMAAAToAwAAUE
sFBgAAAAABAAEASwAAAFcMAAAAAA==

そう、これはbase64です!

デコードしてみると….

$ base64 -d output
P/�?�\�▒
 D�lazykUT...

文字化けてるんじゃなくて、元データがバイナリだったということです!

$ base64 -d output > binaryfile
$ file binaryfile
binaryfile: Zip archive data, at least v2.0 to extract

Zipアーカイブでした。で、展開してみると

$ unzip binaryfile
Archive: binaryfile
 inflating: lazyk

何やらあやしいファイルが….

年賀状ネタばらし: 1日目

年賀状のネタばらし1日目

年賀状の画像はPietという難解プログラミング言語のソースコードになっています。

Piet – Wikipedia: http://ja.wikipedia.org/wiki/Piet

言語仕様: http://www.dangermouse.net/esoteric/piet.html

Pietは色の遷移でスタックを操作するという言語で、実行の向きなどがある面からするとBefungeに近いかもしれません。

ただ、pushするときに同じ色が続く部分の面積がpushされるという点から、面積についても気にしていかなければなりません。

今回は、簡単なジェネレーターを書いたのですべて1 pixelになるように作っています。

で、このPietの処理系はnpietをビルドしてこの画像を動かしてみると….

UEsDBBQAAAAIAC8Cnj/3XIEAGAwAAESrAwAFABwAbGF6eWtVVAkAA4mE/E6NhPxOdXg
LAAEE6AMAAAToAwAA7Zltlhu3DkT/eyUzS+kzP73/vcSOE2vUFGf0AYBVxO1z3osc61
a3moUCyHy8HW8/334ebx+//vH7f7/+/+f7x/vx/v7vvz/ej6t/+ev68zUIRWL4wuXz+
++/vPzxrIJMrcy4tv9Dx/EgqGA8CIp0PxmKtC2hZUQpmen3rtRO0oPiV8tzPPmQMcUr
9bJz3o3WT+RNIRO//CP0+dPXDthK+Ubgffrj42/3+ntJaa0rquV6ZBYEy04D6t/vRCR
Gu+qre3sjNbvjqFul7Gam1CaJ3nZ6bv4WC0stmRXR/fCxIZmvnvmJv3+JRbv5......

こんな文字列が表示されます。

Esolang Advent Calender 8日目: Esolang on Linux kernel

みなさん、Esolangはご存知ですよね?

Esoteric Language = 奇妙な言語ということで、(難解|難読)プログラミング言語などを意味しています。そのEsolangをカーネルに載せるという話について書きたいと思います。

1.システムコールって?

Linuxカーネルにはシステムコールという機能があります。

システムコールとはカーネルがユーザーランドに対して提供するAPIのようなもので、例えばC言語のfopen()はシステムコールのopen()を裏で呼び出すことによってファイルを開いています。Linuxならカーネルのソースコードをkernel.orgから自由にダウンロードできるので、それを改造すればシステムコールを自前で追加することもできます。

なので、今回はLinuxカーネルにEsolangのインタープリタのシステムコールを追加してみました。

2.システムコールの追加方法

システムコールは、いくつかのファイルをいじって、本体となるファイルを追加するだけで作ることができます。どのようにして追加すればいいのか、例としてBrainfuckのインタープリタのシステムコール、sys_brainfuck()を追加する手順を解説してみます。

A. unistd.h

unistd.hはPOSIX環境でのOSが提供するAPIが定義されているヘッダーファイルです。ここにはシステムコールとそれに割り当てられた通し番号が書かれています。

まず、include/asm-generic/unistd.hに以下のように追記します。

#define __NR_brainfuck <通し番号>
__SYSCALL(__NR_brainfuck, sys_brainfuck)

通し番号は他のと被らないように一番最後の番号+1(バージョン3.2.0-rc4では244)を使用してください。

そして、以下の部分も変更します。

#define __NR_arch_specific_syscall <今までの番号+1>

これは、システムコールの総数を意味しているので、追加した分インクリメントしましょう。

続いて、各アーキテクチャに用意されたunistd.hを編集します。これは、アーキテクチャによって用意されているシステムコールが異なることから、動かしたいアーキテクチャ向けにunistd.hを変更する必要があります。

    • ARMならarch/arm/include/asm/unistd.h
    • x86ならarch/x86/include/asm/unistd_32.h
    • amd64ならarch/x86/include/asm/unistd_64.h

それぞれ表記方法が違ってややこしいのですが、だいたい見れば分かると思います。詳しくは、下に貼ってあるpatchをお読みください。

B.エントリファイル

それぞれのアーキテクチャに対して、アセンブリでシステムコールの一覧が書かれたファイルがあります。

    • ARMならarch/arm/kernel/calls.S
    • x86ならarch/x86/kernel/syscall_table_32.S
    • amd64はなし

これも、アーキテクチャによって微妙に表記方法が違いますが、基本的には順番にならべているだけです。なので、他のところを編集して順番変えてしまったりしないように注意してください!

x86の場合は一番下に以下のように追記すると大丈夫です。

.long sys_brainfuck

C. syscalls.h

これはシステムコールのプロトタイプ宣言が書かれているヘッダーファイルです。

普通と同じようにプロトタイプ宣言を書けばいいのですが、最初にasmlinkageとつける必要があります。要はinclude/linux/syscalls.hに以下のように書けば大丈夫です。

asmlinkage long sys_brainfuck(char *source_user, char *input_user,
                       char *output_user, unsigned int source_len,
                  unsigned int input_len, unsigned int output_len);

D. システムコール本体

今回はkernel/brainfuck.cに本体を書いてみました。

大体は普通にC言語のプログラムと同じように書けばいいのですが、stdio.hなどの標準ライブラリは使えません(カーネルランドで動くので、ユーザーランドのIOなどを使えるはずがありません)。ですが、大抵の関数はインクルードしなくても使えたりします。

また、main関数というものもありません。main関数に当たる部分にはSYSCALL_DEFINEというマクロを使用します。

sys_brainfuckでは以下のような形になります。

SYSCALL_DEFINE6(brainfuck, char *, source_user, char *, input_user,
               char *, output_user, unsigned int, source_len,
               unsigned int input_len, unsigned int, output_len)

簡単に表記すると以下のような仕組みです。

SYSCALL_DEFINE<引数の個数> (<システムコール名>, <引数1の型>, <変数1の名前>...)

また、malloc()やfree()も使えないので、代わりにkmalloc(), kfree()といった関数を使用します。

文字を表示したい場合は、printk()を使用しましょう。printk()はカーネルのログに文字列を出力することができます。

このような簡単な手順でLinuxカーネルのシステムコールを自由にいじることができるのです。

3. 実際にやってみた

とりあえずBrainfuckとLazy Kのインタープリタを作ってみたので、それぞれ、カーネルに当てられるpatchとしてgistにアップロードしました。

このpatchはx86, amd64, armのアーキテクチャに対応しています。Androidのカーネルにこれをあてて、実機で動かすことも可能です。(IS01でやったこともありますが….

あと、システムコールを呼び出す見本プログラムもおいときます。

ちゃんと動くので試してみてください!

4. さいごに

なぜかEsolang Advent Calenderのはずが、Linuxカーネルの記事になってました….

申し訳ありません….

あと、要望があれば別の言語でも作ってみますが?