AOJ :: 0018 :: Sorting Five Numbers 104byteまでの軌跡
問題ページはこちら
問題文
５つの整数 a, b, c, d, e を入力し、降順に整列した後に出力して終了するプログラムを作成して下さい。
例えば、
3 6 9 7 5
というデータが与えられたときは、
9 7 6 5 3
と、出力させれば正解です。簡単ですね
続きはネタバレになりますので注意してください。
最初に浮かぶのは、ソートして出力という流れだと思います。
C言語のクイックソート関数の定義
#include
void qsort(void* data, size_t data_cnt, size_t data_size, int(*func)(const void*, const void*);
これを使っていきます。まずは確実に動くコードを考えます。
#include <stdio.h> #include <stdlib.h> int cmp(const void *_a, const void *_b){ int *a = (int*)_a; int *b = (int*)_b; if( *a > *b ) return -1; if( *a < *b ) return 1; return 0; } int main(){ int d[5]; scanf("%d %d %d %d %d",&d[0],&d[1],&d[2],&d[3],&d[4]); qsort(d,5,sizeof(int),cmp); printf("%d %d %d %d %d\n",d[0],d[1],d[2],d[3],d[4]); return 0; }
AOJのコンパイラは今現在、
gcc/g++ version 4.3.0 20080428 (Red Hat 4.3.0-8)
コンパイルは最適化オプション O2 で行われる？
Sorting Five Numbersの問題の仕様として、入力されるデータセットは1つです。（実行を4回繰り返すので、計4回の正誤判定がある）
プロセスが何回実行されて何回正解したか、というのはStatusの AC/N の項目で判別することができます。
AOJシステムの仕様として、プロセスが返す値は 0 でないと、答えが合っていても Runtime Error と処理されます。
まずは"普通"のやり方で縮めて行きます。
C言語では、 &d[0] == d+0 == d です。 d[0] == *(d+0) == *d でしたよね。
上は省略 int main(){ int d[5]; scanf("%d %d %d %d %d",d,d+1,d+2,d+3,d+4); qsort(d,5,sizeof(int),cmp); printf("%d %d %d %d %d\n",*d,d[1],d[2],d[3],d[4]); return 0; }
（早くも限界を感じた…普段はいろいろぶっとばしてショートコーディングしてるんだなぁ…と実感）
ここで少し処理の仕方を変えます。一度に入力や出力させるのではなく、1回ずつ処理するように変えます。
三項演算子も使っていきます。
#include <stdio.h> #include <stdlib.h> int cmp(const void *_a, const void *_b){ int *a = (int*)_a; int *b = (int*)_b; return *a<*b?-1:*a>*b?1:0; } int d[5],i; int main(){ for(;~scanf("%d",d+i);i++); qsort(d,5,sizeof(int),cmp); for(;i;printf("%d%c",d[i],i?32:10))i--; return 0; }
そこそこ縮まりました。
比較関数を昇順にして、配列の後ろから出力を行っています。
C言語では、グローバル宣言したものは全て 0 で自動的に初期化されますので、変数iの明示的な初期化は必要ありません。
scanfが入力失敗したときに返す値は EOF と定義されています。EOFは -1 と定義されてるのが殆どです。
-1 をビット反転すると、0 になります。これを利用してループを抜けるような処理にしています。
数値の出力の間は空白にする必要がありますが、最後だけは改行にしなければなりません。
文字の空白はASCII値に直すと32、改行は10です。三項演算子を利用して場合分け処理をしています。
そろそろ、gcc先生の力を借りましょうｗ
gccコンパイラの場合、頻繁に使う関数はビルドイン関数になってるのでヘッダのインクルードを明示しなくても良い。
関数の返り値や引数の型を省略した場合、int型として解釈されます。
int型のサイズは環境依存ですが、まぁほとんど4byteでしょう。
変数や配列の宣言でさえも、型省略することでint型と解釈されます。
cmp(int*a, int*b){ return *a<*b?-1:*a>*b?1:0; } d[5],i; main(){ for(;~scanf("%d",d+i);i++); qsort(d,5,4,cmp); for(;i;printf("%d%c",d[i],i?32:10))i--; return 0; }
比較関数の引数の型を const void* から int* に変更していますが、どちらもポインタ型なので問題ありません。
余談ですが、void*型をインクリメントすると1byteの増加、int*型をインクリメントすると4byte増加という違いがあります。
型によって増加が違うのでアドレス処理する際には気を付ける必要があります。
ここで、qsortの比較関数をもっと縮められないか考えます。
qsortのショートコーディングやその他諸々のテクニックに関しましては、
「Short Coding 〜職人達の技法〜」
http://www.amazon.co.jp/dp/4839925232
こちらの書籍がおすすめです。たいへんおすすめです。
話をqsortに戻します。qsortの比較関数の返り値は、
-1, 0, 1の三種類ではなく、負、0、正で良いのです。なので、負の値や正の値がなんであろうと問題ないわけです。
Web上でも見かけますが、
cmp(int*a, int*b){ return *a-*b; }
このように書くことも出来ます。ただし、注意しなければならないのはオーバーフローの危険性があるということです。
値の最大値、最小値の把握をしっかりする必要があります。
とにかく、これでも問題Sorting Five Numbersは正しく動作します。
書籍にも記述されておりますが、
cmp(int*a){ return*a-*1[&a]; }
これでも動きます。へぇ、そうなんだ。と思わないでください。なんで？と思いましょう。
本題とははずれますが、実際どうなってるのかを確認していきます。
最初は引数が正しく2つある方です。
M(int*a,int*b){ return*a-*b; } main(){ int d[] = {0x1f,0x0f}; int c = M(&d[0],&d[1]) return 0; }
$ gcc -g hoge.c $ gdb a.out (gdb) disas main 〜省略〜 0x080483ba <main+17>: movl $0x1f,-0x10(%ebp) 0x080483c1 <main+24>: movl $0xf,-0xc(%ebp) 0x080483c8 <main+31>: lea -0x10(%ebp),%eax 0x080483cb <main+34>: add $0x4,%eax 0x080483ce <main+37>: mov %eax,0x4(%esp) 0x080483d2 <main+41>: lea -0x10(%ebp),%eax 0x080483d5 <main+44>: mov %eax,(%esp) 0x080483d8 <main+47>: call 0x8048394 <M> 0x080483dd <main+52>: mov %eax,-0x8(%ebp) 〜省略〜 (gdb) disas M Dump of assembler code for function M: 0x08048394 <M+0>: push %ebp 0x08048395 <M+1>: mov %esp,%ebp 0x08048397 <M+3>: mov 0x8(%ebp),%eax 0x0804839a <M+6>: mov (%eax),%edx 0x0804839c <M+8>: mov 0xc(%ebp),%eax 0x0804839f <M+11>: mov (%eax),%eax 0x080483a1 <M+13>: mov %edx,%ecx 0x080483a3 <M+15>: sub %eax,%ecx 0x080483a5 <M+17>: mov %ecx,%eax 0x080483a7 <M+19>: pop %ebp 0x080483a8 <M+20>: ret End of assembler dump. (gdb) b *0x08048394 Breakpoint 1 at 0x8048394: file hoge.c, line 1. (gdb) r Starting program: /home/ichirin/C/a.out Breakpoint 1, M (a=0xbfec3b98, b=0xbfec3b9c) at hoge.c:1 1 M(int*a,int*b){ Missing separate debuginfos, use: debuginfo-install glibc.i686 (gdb) x/4x $esp 0xbfec3b88: 0x080483dd 0xbfec3b98 0xbfec3b9c 0x08049608 (gdb) x/2x 0xbfec3b98 0xbfec3b98: 0x0000001f 0x0000000f (gdb) x/2x 0xbfec3b9c 0xbfec3b9c: 0x0000000f 0x0011edd0
重要なのはここです。
Breakpoint 1, M (a=0xbfec3b98, b=0xbfec3b9c) at hoge.c:1
引数のアドレスが表示されて、連続してるのがわかります。
関数呼び出しの際、引数の値はスタックに積まれて渡されるのですが、その処理は往々にして連続しています。
そのため、引数のアドレスが連続しているのです。
つまり、渡される値のアドレスが格納されてるスタック領域が連続しているということです。
あれ、分かりづらいｗｗｗ
次に、比較関数の引数が1つの場合を見てみます。
M(int*a){ return*a-*1[&a]; } main(){ int d[] = {0x1f,0x0f}; qsort(d,2,4,M); return 0; }
$ gcc -g hoge.c $ gdb a.out (gdb) disas M Dump of assembler code for function M: 0x080483c4 <M+0>: push %ebp 0x080483c5 <M+1>: mov %esp,%ebp 0x080483c7 <M+3>: mov 0x8(%ebp),%eax 0x080483ca <M+6>: mov (%eax),%edx 0x080483cc <M+8>: lea 0xc(%ebp),%eax 0x080483cf <M+11>: mov (%eax),%eax 0x080483d1 <M+13>: mov (%eax),%eax 0x080483d3 <M+15>: mov %edx,%ecx 0x080483d5 <M+17>: sub %eax,%ecx 0x080483d7 <M+19>: mov %ecx,%eax 0x080483d9 <M+21>: pop %ebp 0x080483da <M+22>: ret End of assembler dump. (gdb) b *0x080483c4 Breakpoint 1 at 0x80483c4: file hoge.c, line 1. (gdb) r Starting program: /home/ichirin/C/a.out Breakpoint 1, M (a=0xbfdff2dc) at hoge.c:1 1 M(int*a){ Missing separate debuginfos, use: debuginfo-install glibc.i686 (gdb) x/4x $esp 0xbfdff1ac: 0x0015bc97 0xbfdff2dc 0xbfdff2e0 0x00000000 (gdb) x/2x 0xbfdff2dc 0xbfdff2dc: 0x0000001f 0x0000000f (gdb) x/2x 0xbfdff2e0 0xbfdff2e0: 0x0000000f 0xbfdff300
比較関数の頭にbreakpointを設定し、qsort内部から比較関数が呼び出されたときの状態を調べています。
スタックの中身を見てみると、リターンアドレス(0x0015bc97)に続いて、スタック領域のアドレスが2つ見えます。
それぞれを確認してみると、先程と同じ結果です。
比較関数の引数が1つ、と定義しているにも関わらず、qsortから比較関数を呼び出すときに
比較する2つの要素をスタックに積んでから、比較関数を呼び出していることがわかります。
比較関数の定義に関わらず、そういう仕様になっているようです。
以上の理由で、引数が1つだよっという比較関数を用意しても、
連続して積まれているであろう2つめの要素のアドレスを取得して処理すれば良いことになります。
また、環境依存になりますが return文 さえ書かなくても良い場合があります。
友人(@Plasmahash)から
http://shinh.skr.jp/dat_dir/golf_prosym.pdf
素晴らしい資料を教えてもらったので晒しておきます。return文の省略についての理由も書かれています。
資料にも書かれていますが、比較関数を機械語のバイナリ埋め込みで代用することでさらに短くできます。
引用（コメントは自ら追記、合ってるかどうかはわかりません…） 59 pop %ecx ; リターンアドレスを取り出す 58 pop %eax ; 第1引数を取り出す 5a pop %edx ; 第2引数を取り出す 51 push %ecx ; スタック値を元に戻す（値に意味はない） 51 push %ecx ; スタック値を元に戻す（値に意味はない） 51 push %ecx ; スタック値を元に戻す（リターンアドレスを戻す） 8b 00 mov (%eax),%eax ; 第1引数のアドレスを参照してeaxレジスタに格納 2b 02 sub (%edx),%eax ; eaxレジスタの格納されてる値 - 第2引数のアドレスを参照した値 c3 ret ; 色々ｗ
最終的に、関数の返り値は eaxレジスタ に格納されていると決まっています。
そして、この機械語を文字列として扱います。文字として代用できないものはバイナリ表記にします。
d[5],i; main(){ for(;~scanf("%d",d+i);i++); qsort(d,5,4,"YXZQQQ\x8b\0+\x02\xc3"); for(;i;printf("%d%c",d[i],i?32:10))i--; return 0; }
このコードだと、最後にeaxレジスタに0が格納されるので return文 は省略できます。
AOJだと、短くしつつreturnやexitを使わず、如何にeaxレジスタに0を格納するか？というのが重要な要素になります。
今回はその辺りについて詳しく記述できないのが残念です。AOJの醍醐味とも言えるのですが。
d[5],i; main(){ for(;~scanf("%d",d+i);i++); for(qsort(d,5,4,"YXZQQQ\x8b\0+\x02\xc3");i;printf("%d%c",d[i],--i?32:10)); }
冷静になって考えると、バイナリ埋め込みとか異常…ｗ
まだ続きます。
次に、環境依存を狙ってバイナリ埋め込みを短くすることを考えます。
AOJシステムは、
gcc/g++ version 4.3.0 20080428 (Red Hat 4.3.0-8)
です。調べてみると、どうやら Fedora9 の環境っぽい。
同環境をVMware上で構築し、環境依存があるかどうか調べます。
qsort関数から比較関数が呼び出されたときの状態を見たいので以下のコードで確認します。
M(int*a){ return *a-*1[&a]; } d[5],i; main(){ for(;-1!=scanf("%d",d+i);i++); qsort(d,5,4,M); for(;i;printf("%d%c",d[i],--i?32:10)); }
$ gcc -O2 -g hoge.c $ gdb a.out (gdb) disas M Dump of assembler code for function M: 0x08048430 <M+0>: push %ebp 0x08048431 <M+1>: mov %esp,%ebp 0x08048433 <M+3>: mov 0x8(%ebp),%eax 0x08048436 <M+6>: mov 0xc(%ebp),%edx 0x08048439 <M+9>: pop %ebp 0x0804843a <M+10>: mov (%eax),%eax 0x0804843c <M+12>: sub (%edx),%eax 0x0804843e <M+14>: ret End of assembler dump. (gdb) b *0x08048430 Breakpoint 1 at 0x8048430: file hoge.c, line 1. (gdb) r Starting program: /home/ichirin/C/a.out 1 2 3 4 5 Breakpoint 1, M (a=0x804973c) at hoge.c:1 1 M(int*a){ Missing separate debuginfos, use: debuginfo-install glibc.i686 (gdb) i r eax 0x1 1 ecx 0x804973c 134518588 edx 0x0 0 ebx 0xb99ff4 12165108 esp 0xbf991cdc 0xbf991cdc ebp 0xbf991d38 0xbf991d38 esi 0x8049740 134518592 edi 0xbf991dc0 -1080484416 eip 0x8048430 0x8048430 <M> eflags 0x202 [ IF ] cs 0x73 115 ss 0x7b 123 ds 0x7b 123 es 0x7b 123 fs 0x0 0 gs 0x33 51 (gdb) x/4x $esp 0xbf991cdc: 0x00a61c97 0x0804973c 0x08049740 0x00000000
比較関数が呼び出された直後のレジスタを見てみると、
ecxレジスタに第1引数のアドレス
esiレジスタに第2引数のアドレス
が既に格納されていることが分かります。
qsortが2つの要素をスタックに積んで、比較関数を呼ぶ際に使用したレジスタと思われます。
これをこのまま使いましょう。
8b 01 mov (%ecx),%eax 2b 06 sub (%esi),%eax c3 ret
これで同様のことが行えます。
d[5],i; main(){ for(;~scanf("%d",d+i);i++); for(qsort(d,5,4,"\x8b\1+\6\xc3");i;printf("%d%c",d[i],--i?32:10)); }
まだだ…まだ終わらんよ！！！
byte数の計算の際に、\もカウントされています。これを回避するためにパケット改竄を行います。
実際にこのコードを送信するパケットを見てみましょう。
使用したツール： burp suite v1.3
画像1
これを改竄して、
画像2
%5C1 --> %01
%5C6 --> %06
%5Cxc3 --> %c3
と、改竄することで、無駄な\によるカウントを回避します。
こうして 104byte Accept をいただきました。
今現在、@_pldw氏 が 102byte で1位です。私は諦めましたｗ
ショートコーディング初心者の方にも、なるべくわかりやすいように心掛けて書いたつもりです。
間違いがありましたらご指摘お願いします。
友人@Plasmahashとの協力あっての 104byte でした。すぺしゃるさんくす
追記：
画像、機械語の数値が間違ってたので修正
