Sharkovskii order (C) 解説 その2 ～x86機械語編～
その1 ～真面目な解法編～の続き．
関数＝機械語の列
さて，C言語において，関数とは実はメモリのどこかに置かれた，機械語の列でしかありません．「関数を呼ぶ」とは，「引数およびリターンアドレスをスタックに積んで，呼びたい関数（が表す機械語の列）の先頭アドレスにジャンプする」ことを表します．そして，ほとんどの場合，関数が終了するとスタックに積まれたリターンアドレスに再度ジャンプし，その後の処理を継続することになります．
qsort の第4引数に関数*1 f を渡すという行為は，機械語の列の先頭アドレスを渡し，必要に応じてそこにジャンプするということに他なりません．
……ということは，比較を行う機械語の列を文字列で直接渡してあげれば，わざわざ関数を定義しなくても済むわけです．102バイト@Cのコードは，実際にそれを使用しています．
b;main(){~scanf("%d\n",++b+&b)?main()^vprintf():
qsort(&b+1,b,4,"X[ZRSP�架!ﾋ9ﾋt�可!ﾂ)ﾈ)ﾚEﾂﾃ");}
なんだか文字化けみたいですね．
アセンブリコード
上記のコードの qsort の第4引数は，x86という機械語で書かれています．といってもこのままではわかりにくいので，アセンブリ言語にdisassembleしたのが以下です．
pop %eax;
pop %ebx;
pop %edx;
push %edx;
push %ebx;
push %eax;
mov (%ebx), %ecx;
mov %ecx, %ebx;
neg %ebx;
and %ecx, %ebx;
cmp %ecx, %ebx;
jz B1;
mov (%edx), %eax;
mov %eax, %edx;
neg %edx;
and %eax, %edx;
sub %ecx, %eax;
sub %ebx, %edx;
cmovne %edx, %eax;
B1:
ret;
これはC言語だと，おおむね以下の関数に相当します．
f(int*a,int*b){ return*a-(*a&*a-1)?(*b&-*b)-(*a&-*a)?:*b-*a:-1; }
各部分の解説
pop %eax;
pop %ebx;
pop %edx;
push %edx;
push %ebx;
push %eax;
引数を読み出す処理です．第1引数 a をebxレジスタに，第2引数 b をedxレジスタに，そしてリターンアドレスをeaxレジスタに格納しています．
mov (%ebx), %ecx;
mov %ecx, %ebx;
neg %ebx;
and %ecx, %ebx;
ecxレジスタに *a を，ebxレジスタに *a&-*a を格納しています．最初の (%ebx) が *a を表すことにさえ注意すれば，なんとなく読めるでしょう．
cmp %ecx, %ebx;
jz B1;
ecxレジスタの *a と，ebxレジスタの *a&-*a を比較し，同じならば B1 にジャンプする処理です．この2つが等しい場合とは *a が2のべき乗の場合なので，要は *a が2のべき乗の場合にearly returnしていることになります．
mov (%edx), %eax;
mov %eax, %edx;
neg %edx;
and %eax, %edx;
先程とほぼ同じですが，今度はeaxレジスタに *b を，edxレジスタに *b&-*b を格納しています．
sub %ecx, %eax;
sub %ebx, %edx;
cmovne %edx, %eax;
まずは sub 2つで，eaxレジスタに *b-*a を，edxレジスタに (*b&-*b)-(*a&-*a) を格納しています．
cmov というのはconditional moveで，条件を満たしたときのみ mov する命令です．今回は cmovne なので，ゼロフラグが立っていない場合のみ mov %edx, %eax; するということになります．
ゼロフラグの有無は直前の sub %ebx, %edx; によって決まります．要は， (*b&-*b)-(*a&-*a) がゼロでないときだけeaxレジスタに (*b&-*b)-(*a&-*a) を格納することになります． (*b&-*b)-(*a&-*a) がゼロの場合は，eaxレジスタは *b-*a のままです．
B1:
ret;
最後に ret でreturnします．このとき，eaxレジスタに格納されている値が戻り値として扱われます．先程の議論により，目的の値がreturnされることになります．
少し注意したいのが，early returnの場合です． *a が2のべき乗の場合は jz 命令により直接ここに来ますが，このときeaxレジスタには1行目で pop %eax; した値，つまり関数のリターンアドレスが残っています．幸運にもリターンアドレスは負の数なので*2，この場合は負の値が戻り値として返され，無事swapされずに済むというわけです．
おわりに
というわけで，機械語34バイト，それ以外68バイトの，計102バイトでこの問題が解けました．私はx86ゴルフには明るくないので，機械語部分が果たしてこれで最短かはわかりません．というか，多分もっと縮むと思います．x86に自信がある方は，是非私のコードを縮めてみてください．ご報告をお待ちしています．
私はこの問題を始めるまでアセンブリなんてまったくわかりませんでしたし，この問題がなければおそらく今もまったくわかっていなかったでしょう．つくづく，コードゴルフの遊び方は幅広いと実感します．
また，8年ぶりにコードを縮めてみた結果，当時精一杯だったところから，さらに（機械語なしで）19バイトも縮められたのも驚きでした．世間一般にC言語コードゴルフの知見が貯まってきたことに加え，8年間での私の成長も要因としてあると思います．
コードゴルフって本当に面白いですね．
