Best position-independent code

最高の位置独立コード

受賞者:Brian Westley

引用元:https://www.ioccc.org/2001/westley.c

審査員・作者による説明:https://github.com/ioccc-src/winner/blob/main/2001/westley.hint

動作

元プログラムの動作は、入力を行単位でランダムにシャッフルして表示する。

$ gcc -trigraphs -o westley westley.c

$ echo -e '1\n2\n3' | ./westley
1
3
2

$ echo -e '1\n2\n3' | ./westley
2
3
1

$ echo -e '1\n2\n3' | ./westley
2
1
3

元のソースコード自身をシャッフルしてもコンパイルできる。 そして、シャッフル結果に依存してさまざまな挙動をするプログラムになる(変わらない場合もある)。

次はただのcatになった例。

$ ./westley < westley.c > tmp.c

$ gcc -trigraphs -o tmp tmp.c

$ echo -e '2\n1\n3' | ./tmp
2
1
3

次は行反転コマンドになった例。

$ ./westley < westley.c > tmp.c

$ gcc -trigraphs -o tmp tmp.c

$ echo -e '1\n2\n3' | ./tmp
3
2
1

次はsortになった例。

$ ./westley < westley.c > tmp.c

$ gcc -trigraphs -o tmp tmp.c

$ echo -e '2\n1\n3' | ./tmp
1
2
3

$ echo -e '3\n2\n1' | ./tmp
1
2
3

そして、パンチカード風に出力するものになった例。

$ echo "Hello, world" | ./tmp
 _________________________________________________________________________________
/Hello, world                                                                    |
|[[[[[   [[[[                                                                    |
|  [[[  [[[[                                                                     |
| [   [ [   [                                                                    |
|                                                                                |
|                                                                                |
|  [[ [    [                                                                     |
|           [                                                                    |
| [                                                                              |
|    [  [[                                                                       |
|                                                                                |
|[    [                                                                          |
|         [                                                                      |
|________________________________________________________________________________|

$ echo '&-0123456789ABCDEFGHIJKLMNOPQR/STUVWXYZ:#@'"'"'=".<(+|./t*);,%_>?abcmnoxyz^[]{}\' | ./tmp
 _________________________________________________________________________________
/&-0123456789ABCDEFGHIJKLMNOPQR/STUVWXYZ:#@'=".<(+|./t*);,%_>?abcmnoxyz^[]{}\    |
|[           [[[[[[[[[                       [[[[[[[          [[[[[[   [[[[[[    |
| [                   [[[[[[[[[              [       [[[[        [[[[[[[[[[[[    |
|  [                           [[[[[[[[[     [      [[   [[[[ [[[   [[[[[[[[[    |
|   [        [        [        [             [      [         [        [[[[[[    |
|    [        [        [        [       [    [                 [       [[[[[[    |
|     [        [        [        [       [   [[    [ [   [      [      [[[[[[    |
|      [        [        [        [       [  [ [      [   [      [     [[[[[[    |
|       [        [        [        [       [ [  [      [   [      [    [[[[[[    |
|        [        [        [        [       [[   [      [   [      [   [[[[[[    |
|         [        [        [        [       [    [          [      [  [[[[[[    |
|          [        [        [        [ [[[[[[[[[[[[  [[[[[[[[       [ [[[[[[    |
|           [        [        [        [     [                        [[[[[[[    |
|________________________________________________________________________________|

解説

westley.cは空行やコメント行を除いて実質28行なので、その順列の数は28! = 304,888,344,611,713,860,501,504,000,000で、このいずれもビルド可能になっている。そして、挙動で分類すると12種類になる。12種類の内訳は組み合わせ。

組み合わせなので、ソートしつつ反転してパンチカード風に表示するコマンドも出てくることがある。

このコードの着想は、パンチカードの扱いにあるとのこと。 パンチカードの束をうっかり床に落とすと、順番がわからなくなって大変なことになる。 しかしC言語は行の順番を変えても意味が変わらないように書くことができる(落下耐性がある)ので便利、というネタ。

このコードは行をシャッフルすることで、パンチカードの落下をシミュレーションする。 そして自分自身を落としても(シャッフルしても)動く。 なんなら、順番を変えたら違う意味で動くようにも書けたので書いた。

実際にシャッフルで所望の挙動を得るのは大変なので、ちょっと便利な工夫がされている。

パンチカードはASCIIではなくEBCDICという古い文字コードで表現される。 EBCDICでは一部の文字("^[]{}\"など)が使えないので、コードはこれらを避けて書かれている。 そのためにトライグラフを多用しており、gcc -ansigcc -trigraphsでないとビルドできない。 /* { /KC 0000 K } */という謎のコメントは、EBCDICでパンチカードにしたときに(-:になるパターン。

$ ./tmp < westley.c
...
 _________________________________________________________________________________
/                          /* {   /KC 0000 K  } */                               |
|                             [     [         [                                  |
|                           [ [    [       [  [ [                                |
|                          [  [   [   [[[[    [  [                               |
|                          [  [   [           [  [                               |
|                             [    [       [  [                                  |
|                             [     [         [                                  |
|                           [ [               [ [                                |
|                             [               [                                  |
|                             [               [                                  |
|                             [               [                                  |
|                           [ [               [ [                                |
|                             [               [                                  |
|________________________________________________________________________________|
...

賞名の位置独立コードは、各行をどこに置いても動くことを指しているが、本来はどのアドレスに配置されても動く機械語のことを言う。

実に神がかっている。これは、westley最後の作品(2020年現在)。次の作品がみたい。