読者です 読者をやめる 読者になる 読者になる

ichirin2501's diary

いっちりーん。

AOJ :: 0018 :: Sorting Five Numbers 104byteまでの軌跡

問題ページはこちら


問題文

5つの整数 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先生の力を借りましょうw
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
引数のアドレスが表示されて、連続してるのがわかります。
関数呼び出しの際、引数の値はスタックに積まれて渡されるのですが、その処理は往々にして連続しています。
そのため、引数のアドレスが連続しているのです。
つまり、渡される値のアドレスが格納されてるスタック領域が連続しているということです。
あれ、分かりづらいwww


次に、比較関数の引数が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                ; 色々w

最終的に、関数の返り値は 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));
}

冷静になって考えると、バイナリ埋め込みとか異常…w
まだ続きます。


次に、環境依存を狙ってバイナリ埋め込みを短くすることを考えます。
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位です。私は諦めましたw


ショートコーディング初心者の方にも、なるべくわかりやすいように心掛けて書いたつもりです。
間違いがありましたらご指摘お願いします。


友人@Plasmahashとの協力あっての 104byte でした。すぺしゃるさんくす



追記:
画像、機械語の数値が間違ってたので修正