C/C++の定数の型の話, C90/C99の差分のびみょーな話
Cのソースコードに m = 195; とか n = 0xffffffff; とか書いたときの定数（右辺）の型って、なんであるかご存じでしょうか？ また、C90(1990年版のISO C言語規格)とC99(1999年版のそれ)ではその型が微妙に異なったりすることがあるんですが、ご存じでしょうか？ さらには、お使いのマシンがILP32であるかLP64であるかLLP64であるかによっても、微妙に型が違ってきたりするんですが、それについてはどうでしょうか? えーもちろん、普段は「Uがついてなかったらint, Uがついてたらunsigned intジャネーノ？」くらいの理解でも殆ど不自由しないわけですが、詳細な理解がないとハマるケースも稀にあります。
私はというと、上に書いたような事は、C90/99の差違を除いてはだいたい理解しているつもりだったのですが、C90/99の差異について無頓着だったがために、先日ちょっとした不意打ちをくらいました。事例(クイズ?)として紹介してみます。
クイズ
このようなコードを考えます。妙なコードですが、問題の起こる最小の例を抜き出したということでご勘弁ください。これは、C90とC99で異なる振る舞いをするコードになっています。4294967295は、2進数で書くと1111 1111 1111 1111 1111 1111 1111 1111です(1が32個並ぶ)です。
#include <stdio.h>
void foo(int nume) {
unsigned long long x = nume / 4294967295;
printf("%llu\n", x);
}
int main() {
foo(-1);
return 0;
}これを、次の4つの環境でコンパイル・リンクして実行すると、
- (1) ILP32, C90準拠コンパイラ (gccなど)
- (2) ILP32, C99準拠コンパイラ (gcc4 -std=c99 など)
- (3) LP64, C90準拠コンパイラ (gccなど)
- (4) LP64, C99準拠コンパイラ (gcc4 -std=c99 など)
それぞれ、どのような出力が得られるでしょうか?
えー、4294967295 の型が(1)-(4)でそれぞれ何になるかがポイントです。それによって除算がどう行われるかが、除算の結果の型も含めて決まります。変数xへの代入部分は、この例では答えに影響しません。というか、影響しないようにxの型を選んであります。
答え
(1)-(4)の出力は順に
- (1) 1
- (2) 0
- (3) 0
- (4) 0
となります。次の通り:
% gcc -v gcc version 4.1.1 20070105 (Red Hat 4.1.1-51) % uname -m x86_64 % gcc -m32 div.c && ./a.out 1 % gcc -m32 -std=c99 div.c && ./a.out 0 % gcc -m64 div.c && ./a.out 0 % gcc -m64 -std=c99 div.c && ./a.out 0
順を追って解説します。まず、「定数の型がどのように決まるか」から押さえましょう。
定数の型はどのように決まるのか (C90編)
C90における定数の型は、ISO C90 規格書*1の6.1.3.2に載ってます。
整数定数の型は、次の並びのうちでその値を表現できる最初の型とする。
- 接尾語無しの10進数: int, long int, unsigned long int
- 接尾語無しの8進数又は16進数: int, unsigned int, long int, unsigned long int
- 文字u又はUが接尾語として付く場合: unsigned int, unsigned long int
- 文字l又はLが接尾語として付く場合: long int, unsigned long int
- 文字u又はU及び文字l又はLが接尾語として付く場合: unsigned long int
たとえば、ILP32環境で定数「1」や「214783647」*2はintですが、「2147483648」*3はintでもlong intでも表現できないのでunsigned long intになります。型が、符号有無も含めて異なります。また、同じ数(!?)でも10進定数にするか16進定数にするかで型が異なることがあります。LP64環境で「2147483648」は long int ですが、「0x80000000」は unsigned int になってしまいます。やはり型が、符号有無も含めて異なります。ぅゎ。
定数の型はどのように決まるのか (C99編)
C99における定数の型は、ISO C99 規格書の6.4.4.1に載ってます。C99の場合は表になっているんですが、私の方でC90にフォーマットを合わせたものを記します。ひとまず「接尾語無しの10進数」のlong intの次が、C90ではunsigned long intだったのに対しC99ではlong long intになっています。これが今回のポイントです。
整数定数の型は、次の並びのうちでその値を表現できる最初の型とする。
- 接尾語無しの10進数: int, long int, long long int
- 接尾語無しの8進数又は16進数: int, unsigned int, long int, unsigned long int, long long int, unsigned long long int
- 文字u又はUが接尾語として付く場合: unsigned int, unsigned long int, unsigned long long int
- 文字l又はLが接尾語として付く場合の10進数: long int, long long int
- 文字l又はLが接尾語として付く場合の8進数又は16進数: long int, unsigned long int, long long int, unsigned long long int
- 文字u又はU及び文字l又はLが接尾語として付く場合: unsigned long int, unsigned long long int
- 文字ll又はLLが接尾語として付く場合の10進数: long long int
- 文字ll又はLLが接尾語として付く場合の8進数又は16進数: long long int, unsigned long long int
- 文字u又はU及び文字ll又はLLが接尾語として付く場合: unsigned long long int
ILP32+C99では定数「1」や「214783647」はintですが、「2147483648」は long long int になります。またC90同様、同じ数(?)でも10進定数にするか16進定数にするかで型が異なることがあります。ILP32+C99で「2147483648」は long long int ですが、「0x80000000」は unsigned int です。やはり型が、符号有無も含めて異なります。
解説
これを踏まえ、(1)-(4)で4294967295の型がどうなるかを起点として除算の動きを見ます。
(1)では、4294967295の型はunsigned long int になります。ですから、除算は
-1 [int] / 4294967295 [unsigned long int] ==(usual arithmetic conversion)==> -1 [unsigned long int] / 4294967295 [unsigned long int] ==> 4294967295 [unsigned long int] / 4294967295 [unsigned long int] ==> 1
のように行われ（適当な記法でスミマセン）、結果は1になります。0にはなりません！。結果の型は unsigned long int です。
(2)では、4294967295の型はlong long intになります。ですから、除算は
-1 [int] / 4294967295 [long long int] ==(usual arithmetic conversion)==> -1 [long long int] / 4294967295 [long long int] ==> 0
のように行われ、結果は0になります。結果の型は long long int です。64bitの符号「付き」の型に揃えられてから演算されるので、(1)のように -1 が 4294967295UL に読み替えられないのがポイントでしょう。
(3)と(4)はlong型が64bitである関係で、同じ演算になります。C90/99で違いは出ません。4294967295の型はlong intになります。除算は
-1 [int] / 4294967295 [long int] ==(usual arithmetic conversion)==> -1 [long int] / 4294967295 [long int] ==> 0
のように行われ、結果は0になります。結果の型は long int です。-1が-1のまま演算される点は、(2)と同じですね。
(余談) usual arithmetic conversion
usual arithmetic conversion (通常の算術型変換) については、Cの規格を参照してください。このpdfにも少し載ってます。long long型(64bit型)のことを忘れてもいいなら、いやあまりよくないとおもいますが、K&Rの第二版にも一応載ってます。
GCCの警告
実はGCCは、C90とC99で型が異なるような定数を使用すると、C90モードでコンパイルした際に次のような警告を出してくれます。この警告が出たら、無視せずに原因をよく考える方がよさそうです。
warning: this decimal constant is unsigned only in ISO C90
しかしながら、データモデルによって型が変化するケース、10進で書くか8/16進で書くかによって型が変化するケースについては、プログラマが気を付けるしかなさそうです。
まとめ
C言語のソースコード中に記載した定数は、結構意外な型として扱われていることがあり、その詳細を知らないと（たまに）問題が起こる。特に、
- 10進定数を8/16進定数に書き直すと（あるいはその逆）、型が変化してしまうことがあるので注意
- 同じことですが、ある数を10進定数として書くか、8/16進定数で書くかによって型が異なってしまうことがあるので注意
- C90準拠のコンパイラとC99準拠のコンパイラで、定数の型が異なってしまうことがあるので注意
- ILP32環境でコンパイルするかLP64環境でコンパイルするかで、定数の型が異なってしまうことがあるので注意
この3点に注意が必要です。また、
というのもよい習慣だと思います。
C++について
C++言語(ISO/IEC 14882:2003)は、2003年版の規格では、C言語互換部分についてはC90を参照してますので、gccをC90モードで使ったときと同じ結果になります。
% cp div.c div.cpp % g++ -m32 div.cpp && ./a.out div.cpp:4: 警告: this decimal constant is unsigned only in ISO C90 1 % g++ -m64 div.cpp && ./a.out 0
*1:C90のJIS版は、旧規格になりますのでWebから発注はできません。http://www.webstore.jsa.or.jp/webstore/Com/html/jp/ShoppingInfo.htm のFAX注文書で JIS X3010:1993 と X3010:1996(Amd1) を発注することになります。合計で3.5万円程です。詳しくはJSAに問い合わせを
*2:2進で 0111 1111 1111 1111 1111 1111 1111 1111 です
*3:2進で 1000 0000 0000 0000 0000 0000 0000 0000 です
__attribute__)((init_priority(N)))(で、C++のグローバル変数の初期化順序を制御する
g++の __attribute__)((init_priority(N)))( なる機能の日本語の解説が見当たらないので、いつものように紹介文を書いてみます。これは、C++のグローバル変数の初期化順序を制御するためのGCCの拡張機能（attribute）です。
ごく短い説明
動的な初期化が必要なC++のグローバル変数の定義に__attribute__)((init_priority(N)))(をくっつけると、.oファイル上で、その変数の初期化関数(コンストラクタ等)のアドレスが.ctorsではなく.ctors.M セクションに入ります。M は左0パディング5桁固定の数値で、M = 65535 - N です。あとは、shinhさんの2005/11の記事を。特に、リンカスクリプトのSORTのとこに注目、これにより初期化順がinit_priorityで指定した通りになります。Nが小さい程先に初期化と。
以上。
長い説明, static initialization order から
C++で、コンストラクタ呼び等で動的に初期化されるかもしれないグローバル変数*1、たとえば次のような変数ですが、
- int gFoo = ::bar(); のように、関数の戻り値で初期化される変数
- CFoo gFoo; のように、コンストラクタで初期化されるオブジェクト
このようなグローバル変数が複数あって、の間に依存関係(どれかがどれかを読み書きしている)があると、プログラムの実行がmainに到達する前に、プログラムがSEGVって死んだり誤動作したりすることがあります。リンク順を変えたり、いったんmake cleanすると再現しなくなったりする、やや嫌な部類の問題です。
今回は、そのSEGV現象を__attribute__でどうにか誤魔化す話です。ありびゅー。確か以前にも日記のどこかに書いてますけど、例えば死ぬのはこんな例:
// a.h
struct A {
A() : x_(new int()) {}
void foo() { *x_ = 1; }
int* x_;
};クラスAは、コンストラクタでx_用のメモリを確保してますので、もしコンストラクタより先にfoo()が呼ばれてしまうSEGVります。
// a.cpp #include "a.h" A a;
aをグローバル変数として確保しています。
#include "a.h"
struct B {
B() {
extern A a;
a.foo();
}
};
B b;
int main() {}クラスBのコンストラクタはグローバル変数aに依存しています。
さて、これを二種類の方法でコンパイル・リンクしてみます*2。
% g++ -m32 -o good b.cpp a.cpp % ./good % g++ -m32 -o bad a.cpp b.cpp % ./bad zsh: segmentation fault ./bad
見ての通り、リンクをどういう順序で行うかによって、aのコンストラクタよりbのコンストラクタが先に走ってしまい(badのほう)、SEGVします。なぜなら、B::B() は a.foo() を呼んでいて、そのときまだaに対してA::A()は呼ばれておらず、a.foo()の中で未初期化のポインタx_を参照(*x_ = 1)してしまうからです。C++の規格では、コンパイル単位をまたいだグローバル変数の初期化順序は規定されていませんので、g++に責任はありません。この初期化順が不定な問題は、init_priority属性を使うと手軽に解決できます。
A a __attribute__((init_priority(101)));
...
B b __attribute__((init_priority(102)));グローバル変数a,bの定義部分をそれぞれ上記のようにすればOKです。どういう順序でリンクしても問題が発生しなくなります。
普通の対策と無理矢理な対策
なお、ふつー init_priority なんていうGCC拡張など使わずに、
- 動的な初期化を伴うグローバル変数なんて使うな
- どうしても使いたいなら "construct on first use" idiom で対処
とかすると思います。たぶん。グローバル変数aのかわりに、フリー関数aを準備、みたいなidiomですね。このFAQの10.13から10.16に書いてあります*3。これの日本語訳である「C++ FAQ 第2版 - C++プログラミングをきわめるためのQ&A集」にも書いてあると思われます。他のトリックもあると思いますが略。
まーそれはともかく、init_priority拡張の話を続けます。真っ先に初期化したいことがわかりきってるオブジェクト(std::coutに相当するものを自作とか)がある場合なんかはinit_priorityは普通に便利だと思うです。
ほんとに b のコンストラクタが先に走っているのか(__do_global_ctors_auxについて)
bad では、ほんとにaよりbのコンストラクタが先に走っているんでしょうか？printfしたら負けという俺ルールで確認してみましょう。そもそも、だれがグローバル変数のコンストラクタを呼んでくれるんでしたっけ? このへんもobjdump付の日本語解説がそれほど多くなさげなので書きます。えー、仕組みをざっと。good を使ってみてみます。ELFの実行バイナリには、.ctorsというセクションがあります。readelfかobjdumpで見てみます。
% objdump -sj .ctors good Contents of section .ctors: 804970c ffffffff b8840408 2a850408 00000000 ........*.......
ここで、ffffffff と 00000000 は、順に
% nm --numeric-sort good | grep __CTOR 000000000804970c d __CTOR_LIST__ 0000000008049718 d __CTOR_END__
__CTOR_LIST__ と __CTOR_END__ と呼ばれるシンボル（の値）です。この間に挟まれた数字は、mainの実行前に呼ぶべき関数のアドレスです。__attribute__((constructor)) で登録した関数のアドレスもここに入ります。いま、.ctorsセクションに含まれているのはどの関数のアドレスなのでしょう？確認します。
% objdump -sj .ctors good Contents of section .ctors: 804970c ffffffff b8840408 2a850408 00000000 ........*.......
のアドレスを、エンディアン(今はEL, リトルです)に注意しつつnmで探しますと、
% nm -C good | grep 080484b8 00000000080484b8 t global constructors keyed to b % nm -C good | grep 0804852a 000000000804852a t global constructors keyed to a
だそうです。nm -C でdemangle指定をしているので、"global constructors keyed to X" とpretty print されていますが、生のシンボル 「_GLOBAL__I.なんちゃら_X」が見たければ-Cをはずしてください。えー、ともかく、
- b8840408 は、B::B() を呼び出す関数のアドレス
- 2a850408 は、A::A() を呼び出す関数のアドレス
ということですね。では、この "global constructors keyed to X" 関数を呼んでくださるのは誰なのでしょうか？gdb上で確認します。
% gdb good ... Breakpoint 1, 0x08048548 in A::A () (gdb) backtrace #0 0x08048548 in A::A () #1 0x08048527 in __static_initialization_and_destruction_0 () #2 0x0804853f in global constructors keyed to a () #3 0x0804860b in __do_global_ctors_aux () #4 0x08048369 in _init () #5 0x08048599 in __libc_csu_init () #6 0x002dded1 in __libc_start_main () from /lib/libc.so.6 #7 0x080483f1 in _start ()
__do_global_ctors_aux () という関数のようです。これはgccのcrtbegin.oの中の関数です。"global constructors keyed to a" と "global constructors keyed to b" のどちらが先に呼ばれるのでしょうか？ GCCのソースコードで確認します。
// gcc-4.1.x/gcc/crtstuff.c
#ifdef OBJECT_FORMAT_ELF
static void __attribute__((used))
__do_global_ctors_aux (void)
{
func_ptr *p;
for (p = __CTOR_END__ - 1; *p != (func_ptr) -1; p--)
(*p) ();
}わかりやすいですね。__CTOR_END__ 側から、objdumpの表示順とは逆順に呼ばれるっぽいです。一応objdumpでgoodを逆アセンブルして、再確認します。
% nm good | grep __do_global 00000000080485f0 t __do_global_ctors_aux 0000000008048420 t __do_global_dtors_aux % objdump -d --start-address=0x80485f0 good Disassembly of section .text: 080485f0 <__do_global_ctors_aux>: 80485f0: 55 push %ebp 80485f1: 89 e5 mov %esp,%ebp 80485f3: 53 push %ebx 80485f4: bb 14 97 04 08 mov $0x8049714,%ebx 80485f9: 83 ec 04 sub $0x4,%esp 80485fc: a1 14 97 04 08 mov 0x8049714,%eax 8048601: 83 f8 ff cmp $0xffffffff,%eax 8048604: 74 0c je 8048612 <__do_global_ctors_aux+0x22> 8048606: 83 eb 04 sub $0x4,%ebx 8048609: ff d0 call *%eax 804860b: 8b 03 mov (%ebx),%eax 804860d: 83 f8 ff cmp $0xffffffff,%eax 8048610: 75 f4 jne 8048606 <__do_global_ctors_aux+0x16> 8048612: 83 c4 04 add $0x4,%esp 8048615: 5b pop %ebx 8048616: 5d pop %ebp 8048617: c3 ret
$0xffffffff、つまり__CTOR_LIST__とcmpしているあたりとか、sub $0x4 しているあたりに着目。逆順になってます(説明になっていない)。以上により、good では、A::A()が先に呼ばれ、そのあとB::B()が呼ばれるとわかります。
次にbadのほう。脳内エンディアン変換が面倒なので、objdumpではなくて、.ctorsのELFファイル上のオフセットを調べてodすることにします。odの出力の03414(8進数)はオフセットの0x70cのことです。アドレス以外は --format で16進数表示にしてあります。と、ここで Binary Hacks ―ハッカー秘伝のテクニック100選 の Hack #4 (by ukaiさん) を見たら、オフセット表示も od -A x で16進にできることがわかりましたが書き直すのが面倒なのでこのままで....。
% readelf -S bad | egrep -e 'Nr|.ctors' [Nr] Name Type Addr Off Size ES Flg Lk Inf Al [17] .ctors PROGBITS 0804970c 00070c 000010 00 WA 0 0 4 % od --skip-bytes=0x70c -N 0x10 --format=x4 bad 0003414 ffffffff 0804849e 08048528 00000000 % nm -C bad | egrep '(0804849e|08048528)' 000000000804849e t global constructors keyed to a 0000000008048528 t global constructors keyed to b
08048528 が先に呼ばれるのだから、B::B() が先ということですな。ということで、bad がSEGVる理由が確認できました。
とりあえずこの問題を解決してみる (init_priorityのつかいかた)
a.cppとb.cppの、グローバル変数の宣言部分をそれぞれ次のように変更します。init_priority(N)のNの部分の数字が「優先度」で、101以上、65535以下の数値を書けます。小さい数字を指定した変数が先に初期化されるようになります。だから、次の例だと、常にbよりもaが先に初期化されると期待されます。
A a __attribute__((init_priority(101)));
B b __attribute__((init_priority(102)));
確認します。
% g++ -m32 -o good b.cpp a.cpp % ./good % g++ -m32 -o bad a.cpp b.cpp % ./bad (落ちない)
グッジョブ。落ちません。一応 goodとbadの .ctors の内容を確認しますと、
% od --skip-bytes=0x70c -N 0x10 --format=x4 good 0003414 ffffffff 080484b4 08048522 00000000 % nm -C good | egrep -e '(080484b4|08048522)' 0000000008048522 t _GLOBAL__I.00101_a 00000000080484b4 t _GLOBAL__I.00102_b
% od --skip-bytes=0x70c -N 0x10 --format=x4 bad 0003414 ffffffff 08048520 0804849a 00000000 0003434 % nm -C bad | egrep -e '(08048520|0804849a)' 000000000804849a t _GLOBAL__I.00101_a 0000000008048520 t _GLOBAL__I.00102_b
nmの-Cオプション(demangle)がちゃんと効いてなくて、pretty printされていないのがアレですが、good も bad も、aの初期化が先に行われることがわかります。badがbadではなくなりました。GJ.
init_priorityのしくみを見てみる
g++の単なる利用者としてはここまで理解していれば問題ないんですが、どういうtrickで初期化順が保証されるのかを追います。まぁそんなに難しくないです。bad がどうコンパイル,リンクされるかを中心に見ます。GNU ldのマニュアルの http://www.sra.co.jp/wingnut/ld/ld-ja_3.html#SEC29 を見れば、以下を読むまでもなく（わかるひとは）すぐわかるという話もあります。
% g++ -m32 -c a.cpp b.cpp
a.cpp と b.cpp をコンパイルして、a.o と b.o を得ます。この2つの.oをリンクするとgoodまたはbadというバイナリができるわけですが、それはまだしません。リンクするかわりに、a.o と b.o のセクション名を見てみます。
% readelf -S a.o | grep .ctors [ 6] .ctors.65434 PROGBITS 00000000 00007c 000004 00 WA 0 0 4 % readelf -S b.o | grep .ctors [ 7] .ctors.65433 PROGBITS 00000000 00009c 000004 00 WA 0 0 4
すると、init_priority を指定しなかったときには数字なしの単なる .ctors だった*4セクション名が、なにやら謎の数値付きのものになっています。まぁ、ほぼ自明ですが、この数字は init_priority で指定した優先度をNとして、「65535 マイナス N」な数字になっております。a.o と b.o の数字が一つ違いなのはNが違うからです(N=101と102)。ちなみに、.ctors.MMMMM セクションに格納されているのは関数のアドレスだけです(セクションのサイズが000004になっていますよね)。開始終了マークはありません。これらはcrtbegin.o, crtend.oに格納されているのです、後述。ひとまず、「関数のアドレスだけ」な証拠を:
% od --skip-bytes=0x7c -N 0x4 --format=x4 a.o 0000174 00000026 % nm -C a.o | grep 00000026 0000000000000026 t _GLOBAL__I.00101_a
この通り。さて、この2つをリンクしてみます。
% g++ -g3 -m32 -o hoge a.o b.o % readelf -S hoge | grep .ctors [17] .ctors PROGBITS 0804970c 00070c 000010 00 WA 0 0 4
数字がなくなり、単なる.ctorsセクションになりました。理由は、GNU ldが使用するデフォルトのリンカスクリプトを ld -verbose で見ればわかります。リンカスクリプトというのは、リンク対象の .o ファイルの様々なセクションを、リンク後のバイナリにどう取り込むか（など）を指定する設定ファイルです。ld -T filename でお好きなスクリプトを使うこともできます*5。デフォルトのはこうです:
% ld --verbose
...
.ctors :
{
...
KEEP (*(EXCLUDE_FILE (*crtend.o *crtend?.o ) .ctors))
KEEP (*(SORT(.ctors.*)))
...
}これは、
- まず、*crtend.o *crtend?.o 以外の *.o の .ctors セクションを順序指定なしでかき集め、リンク後のELFバイナリの.ctorsセクションにぶちこめ。
- 次に、全ての *.o の .ctors.* セクションをセクション名をキーに昇順に(SORTという文字に注目)かき集めて、リンク後のELFバイナリの.ctorsセクションにぶちこめ
という指示です。これに従うと、b.oの.ctors.65433が先にぶちこまれ、次に a.oの.ctors.65434 がぶちこまれます(SORT、なので)。最初の方で見た通り、.ctors に先に現れる関数が後に呼ばれますので、aが先に初期化されるわけです。めでたしめでたし。
さらに、リンカスクリプトを見る限り、「同じ優先度の変数同士の初期化順は、リンクしてみないとわからない」ことと、スクリプトに KEEP (*(EXCLUDE_FILE (*crtend.o *crtend?.o ) .ctors)) が先に書かれていることから、「init_priority指定のない変数と、init_priority(65535) の変数では、後者の初期化の方が先に行われる」こともわかります。ただこの2つはinfoに明記されているわけではないので（今日時点）、将来万一デフォルトのリンカスクリプトの内容が変化し、動作が変化してしまっても文句は言えないかもしれません。なお、__CTOR_LIST__ (0xffffffff) と __CTOR_END__ (0x00000000) は、crtbegin.o と crtend.o から取り込まれます。リンカスクリプトの
.ctors :
{
KEEP (*crtbegin.o(.ctors)) // __CTOR_LIST__ 取り込み
KEEP (*crtbegin?.o(.ctors)) // __CTOR_LIST__ 取り込み
KEEP (*(EXCLUDE_FILE (*crtend.o *crtend?.o ) .ctors))
KEEP (*(SORT(.ctors.*)))
KEEP (*(.ctors)) // __CTOR_END__ 取り込み
}最初の2行と最後の1行で取り込んでいる...のでしょう。__CTOR_LIST__の取り込みが2行になってる理由はワカリマセン。確かにLISTとENDを取り込んでいる証拠:
% nm -C /usr/lib/gcc/x86_64-redhat-linux/4.1.1/32/crtbegin.o | grep __CTOR_ 0000000000000000 d __CTOR_LIST__ % readelf -S /usr/lib/gcc/x86_64-redhat-linux/4.1.1/32/crtbegin.o | grep .ctors [ 6] .ctors PROGBITS 00000000 000098 000004 00 WA 0 0 4 % od --skip-bytes=0x98 -N 4 --format=x4 /usr/lib/gcc/x86_64-redhat-linux/4.1.1/32/crtbegin.o 0000230 ffffffff
LISTについては上記、ENDについては次の通りcrtend.oですが、以下同様なので略。
% nm /usr/lib/gcc/x86_64-redhat-linux/4.1.1/32/crtend.o | grep __CTOR_ 0000000000000000 d __CTOR_END__
自分でlinker scriptを書くときは、0x00000000と0xffffffffくらいはlinker script内に即値で埋めちゃっても良いと思います。たぶん。
この仕組みの乱用 (section, used と constructor)
えー、まず、__attribute__((constructor)) は __attribute__((section)) の syntactic sugar だということが、このへんまで追えばわかるですね。下記コードで、foo()とbar()はほぼ同じ実行結果をもたらすということです:
__attribute__((constructor))
void foo() { std::puts(__PRETTY_FUNCTION__); }
void bar() { std::puts(__PRETTY_FUNCTION__); }
__attribute__((used, section(".ctors"))) static void (*ptr)() = bar;used属性も忘れずに。つけないと、g++先生が最適化でptr変数をばっさり捨ててしまうかも。でまぁ、これを応用すると、init_priority(N)属性で許されているNは101-65535(inclusive)なわけですが、N=101より優先して関数を呼んでもらうことができるわけです。
// N=1相当
__attribute__((used, section(".ctors.65534"))) static void (*q)() = bar;
// N=0よりも優先
__attribute__((used, section(".ctors.a"))) static void (*r)() = bar;自分で勝手にセクション名に数字を付け加えたり、数字ではないものを付け加えたりしてます。何に使えるのかは不明...。将来も大丈夫かどうかは、デフォルトのリンカスクリプトがどうなるかによります。__attributeではなくて、shinhさんが2005年にかかれているように、objcopy --rename-section を使う方法でもよいとおもわれます。
コンストラクタが呼ばれるまでの道のりの補足
コンストラクタが呼ばれるまでの道のりは、冒頭に書いた通り、
% gdb good ... (gdb) bt #0 A (this=0x804986c) at a.h:3 #1 0x08048498 in __static_initialization_and_destruction_0 (__initialize_p=1, __priority=101) at a.cpp:2 #2 0x0804853f in global constructors keyed to a () #3 0x0804860b in __do_global_ctors_aux () #4 0x08048369 in _init () #5 0x08048599 in __libc_csu_init () #6 0x002dded1 in __libc_start_main () from /lib/libc.so.6 #7 0x080483f1 in _start ()
なわけですが、__do_global_ctors_aux() しか説明していませんでした。他に次の4つの関数が関与しているようです：
- _init() は /usr/lib/crti.o (glibc-2.x/sysdeps/generic/initfini.c ?)
- __libc_csu_init() は /usr/lib/libc_nonshared.a (glibc-2.x/csu/elf-init.c)
- __libc_start_main() は、上にも書いてある通り /lib/libc.so.6 (glibc-2.x/csu/libc-start.c)
- _start() は /usr/lib/crt1.o (glibc-2.x/sysdeps/i386/elf/start.S)
ですね。BinaryHacksの#25でも、b2con2006の資料でもこのへんは説明を端折ったので、(私はあまり詳しいわけでもないですが)少し補足します。
まず、__libc_start_main 以外は実行バイナリ自体に含まれています。逆アセンブル例:
% nm hoge | grep __libc_csu_init 0000000008048580 T __libc_csu_init % objdump -d --start-address=0x8048580 hoge 08048580 <__libc_csu_init>: 8048580: 55 push %ebp 8048581: 89 e5 mov %esp,%ebp (略) 80485e8: c3 ret
_initは.initセクションに含まれているので、nmで論理アドレスを調べるまでもなく % objdump -dj .init hoge で逆アセンブル可能です。__libc_csu_init が含まれている libc_nonshared.a は、g++ -v でhogeにどのような .o や .a がリンクされるかを観察しても、一見登場しないのですが、 /usr/lib/libc.so (何気にテキストファイル) の、GROUP文
% cat /usr/lib/libc.so OUTPUT_FORMAT(elf32-i386) GROUP ( /lib/libc.so.6 /usr/lib/libc_nonshared.a AS_NEEDED ( /lib/ld-linux.so.2 ) )
経由でひっそりリンクされています。strace -f g++ すれば確かにリンクされているのがわかることでしょう。_startは、実行バイナリのエントリポイント(ELFヘッダのe_entry値)ですね。
% readelf -h hoge | grep Entry Entry point address: 0x80483d0 % nm hoge | grep 80483d0 00000000080483d0 T _start
エントリとはいっても、もちろん .interp の方に先に制御が移り、そのあとこのe_entryなわけですが。詳細は略。greeの勉強会の資料をご参照ください。
__static_initialization_and_destruction_0 と _GLOBAL__I.ほげ_X
__static_initialization_and_destruction_0 とか "global constructors keyed to a" は、.oの時点で含まれています。これは g++ -S あるいは g++ -save-temps で .s ファイルを吐くか、.o をnmすれば確認できます。のでまぁ、g++が勝手に生成すると。たとえばこんな感じの関数になっています。g++ -S してc++filtしたものです。
% c++file < a.s | less
...
__static_initialization_and_destruction_0(int, int):
.LFB6:
pushl %ebp
.LCFI3:
movl %esp, %ebp
.LCFI4:
subl $24, %esp
.LCFI5:
movl %eax, -4(%ebp)
movl %edx, -8(%ebp)
cmpl $1, -4(%ebp)
jne .L7
cmpl $101, -8(%ebp)
jne .L7
movl $a, (%esp)
call A::A()
.L7:
leave
ret
(略)
_GLOBAL__I.00101_a:
.LFB7:
pushl %ebp
.LCFI6:
movl %esp, %ebp
.LCFI7:
subl $8, %esp
.LCFI8:
movl $101, %edx
movl $1, %eax
call __static_initialization_and_destruction_0(int, int)
leave
retスタックではなく、eaxおよびedxレジスタを使って引数を渡している、つまり __attribute__)((regparm(2)))( 相当になってるのがちょっと目を引くくらいで、あとは特になにもしていないというか、A::A()を呼んでるだけというか。 A::A()に渡すthisのアドレスは__static_initialization_and_destruction_0が保持しています。eax (ここでは1) は、__initialize_p という名前の引数で、__static_initialization_and_destruction_0() にオブジェクトの構築をさせたいのか、解体をさせたいのかの指示のようです。でも、特別なコンパイルオプションを指定しない限りは、手元のgcc3/4で__initialize_pが0で呼ばれることはありませんでした。構築時に__static_initialization_and_destruction_0()が、解体関数を__cxa_atexit()に渡し、そっちに解体を任せてしまうので、呼んでもらう必要がないです。[http://sourceware.org/ml/libc-alpha/2005-08/msg00097.html:title=g++に、-fno-use-cxa-atexitというオプションを渡した時]だけ、"global destructors keyed to a" なる関数が .o に突っ込まれ、それが__static_initialization_and_destruction_0()を__initialize_p==0で呼ぶようになりました。
080484e2 <_GLOBAL__D.00101_a>: <=== IではなくてD 80484e2: 55 push %ebp 80484e3: 89 e5 mov %esp,%ebp 80484e5: 83 ec 08 sub $0x8,%esp 80484e8: ba 65 00 00 00 mov $0x65,%edx 80484ed: b8 00 00 00 00 mov $0x0,%eax <=== ぜろ 80484f2: e8 ad ff ff ff call 80484a4 <__static_initialization_and_destruction_0(int, int)> <== このcall先でデストラクタ呼び 80484f7: c9 leave 80484f8: c3 ret
このように。この関数のアドレスは、(いままではカラだった).dtorsセクションに格納されていて、__do_global_dtors_aux() によってアドレスが拾われ、呼ばれます。gccのinfoを見るに*6、なんかまずいことがあるから__cxa_atexit()方式がいまは使われているのだと思うのですが、なにがまずいのかは追いきれませんでした。どなたか教えてくださいませ。
TIPS: g++ -S ではなく、コンパイル済の.oをobjdumpで逆汗して確認するときは、objdump -Cdr a.o のようにしましょう（＞だれとなく）。-C しないとdemangleされませんし、-r しないと、なにをcallしているのか関数名ががわかりませんので。くだー。です。
DSOをまたいだ初期化順
init_priorityの番号による初期化順の制御は、単一の.so内、および単一の実行ファイル内でのみ効くようですね。複数の.soをまたいだ、あるいは.soと実行ファイル間の初期化順序はこのattributeでは制御できないようです。せいぜい、.soの初期化関数が先に呼ばれて、実行ファイルの初期化関数が最後に呼ばれる*7ことが期待される、というくらいか。力尽きてきていまはソースコード読む元気が出ないのであとで。
memo, 余談1
リンカスクリプトと言えば、LMAとVMAをずらすという話が面白い（かも）しれません。組み込み機器等で、初期値ありのグローバル変数をROM(LMAで指定したアドレス)に配置するときに使う技ですね。スタートアップルーチンで、ROM上の変数をRAM(VMAで指定したアドレス)にコピーしてからプログラムの実行を開始して辻褄を合わせます。このあたりは、ldのマニュアルにも一通り解説があります。
memo、余談2
ELFの特定セクションのダンプは,
% readelf -Wx .ctors good Hex dump of section '.ctors': 0x08049674 00000000 080484ee 08048488 ffffffff ................
でも良い筈だけど、見てわかるように表示がおかしい。表示順が真逆。バグ? x86_64でx86のELFをダンプしているから? FC6/x86_64。とりあえず保留。
まとめ
説明が趣味とはいえ、長い。あと、長いわりによくわからない。かなり自分用メモ。でもこれだけキーワードを散りばめておけばいつかだれかの役に立つかもしれないので気にしない方向で。
*1:名前空間有効範囲の静的記憶域期間をもつオブジェクトのこと、ですが長いので以下グローバル変数と略記
*2:私はx86_64なカーネルの上で作業して(32bitなバイナリを作って)います。x86なカーネルの方はg++に-m32を渡す必要はありません
*3:main到達前にマルチスレッドになるコードだと（どんなんだよ）、これだとまずいので注意してくださいw。Javaみたいな、クラスローダー様がロック獲得してほげ、とか一切ありませんので
*4:自分で確認してみてください
*5:組み込み機器をいじる際にはリンカスクリプトを自分で書くことが多いです
*6:% info gcc --index-search="fuse-cxa-atexit"
*7:もちろん.soをdlopenした場合は除きます
Binary2.0 Conference 2006 発表資料
b2con 2006の発表資料を置きました。
- "Hello, binary world!" (PDF, アニメなし)
ご来場頂いた皆様、主催者の皆様、どうもありがとうございました。わたし自身もとても楽しめました。IRCの様子が会場でも見られたのはよかったと思います*1。他のスピーカーの皆さんの発表資料はこちら。
(追記) 会場でDan Kogaiさんに質問いただいた、__attribute__の括弧が二重なのは何故？という件なんですが、y-hamigakiさんが解説を書いてくださっています。ありがとうございます。なるほど。
BF2ELF
先日書いた、適当にELFなバイナリを吐くプログラムに関して、ある人に「スタックを使うためにはプログラムヘッダに何か書かないといけないのか？と聞かれました」。えーっと、不要です*1。カーネルが勝手に確保してくれます。確保量というか最大サイズは、setrlimit(2)でというか、ulimitコマンドで調整してください。普段と同じです。ELFのエントリポイントに制御が移動した時点で%espが適切な値になってます。
ちゃんとスタックが使えることを示す例として、何かサンプルでもあったほうがよいと思いますので、適当ですがbrainfuckのコンパイラを置いときます。movl $1, (%esp); するだけの例じゃあんまりですので(そのほうがいい?)。bfの","命令と"."命令がx86のcall命令に置き換えられるんで、そこでスタック使います。なお、bfの実用的な（？）、ELFコンパイラはここ(.oや.soが吐けるらしい)とかここ(bfで書かれてるようだ)にあります。何かのプラグインをbfで書きたい等の奇特なケースに於かれましてはこちらを使うとよいと思われます。
// bf2elf.c
#include <stdio.h>
#include <stdlib.h>
#include <elf.h>
#include <unistd.h>
#include <sys/stat.h>
#include <sys/types.h>
#define ARRAY_SIZE (0xffff * 2)
__asm__ ("start_: \n\t"
"inc %dl \n\t" // len = 1
"mov $0x6a, %di \n\t" // addr of write
"lea 6(%edi), %esi \n\t" // addr of read
"mov $0xffff, %bp \n\t" // ARRAY_SIZE / 2
"call end_ \n\t"
"mov $1, %al \n\t" // exit()
"int $0x80 \n\t"
"mov $4, %al \n\t" // write()
"mov $1, %bl \n\t" // stdout
"jmp syscall_ \n\t"
"mov $3, %al \n\t" // read()
"xor %bl, %bl \n\t" // stdin
"movb %bl, (%ebp) \n\t" // EOFのときは0埋め
"syscall_: \n\t"
"mov %ebp, %ecx \n\t" // addr
"int $0x80 \n\t"
"xor %eax, %eax \n\t"
"ret \n\t"
"end_: \n\t"
);
extern char *start_, *end_;
void write_elf_header(int fd) {
Elf32_Ehdr ehdr = {
{ ELFMAG0, ELFMAG1, ELFMAG2 ,ELFMAG3, ELFCLASS32, ELFDATA2LSB, EV_CURRENT, ELFOSABI_SYSV },
ET_EXEC, EM_386, EV_CURRENT, 52 + 32, 52, 0, 0x0, 52, 32, 1, 0, 0, 0,
};
write(fd, &ehdr, sizeof(Elf32_Ehdr));
}
void write_program_header(int fd, size_t code_size) {
size_t sz = 52 + 32 + code_size;
Elf32_Phdr phdr = {
PT_LOAD, 0x0, 0x0, 0, sz, sz + ARRAY_SIZE, PF_R | PF_W | PF_X, 0x1000,
};
write(fd, &phdr, sizeof(Elf32_Phdr));
}
size_t write_code(int fd) {
uintptr_t base_len = (uintptr_t)&end_ - (uintptr_t)&start_;
write(fd, &start_, base_len);
static const struct insn {
size_t len;
unsigned char code[10];
} insns[8] = {
{ 1, { 0x45 } }, // ">", inc %ebp
{ 1, { 0x4d } }, // "<", dec %ebp
{ 3, { 0xfe, 0x45, 0x00 } }, // "+", incb (%ebp)
{ 3, { 0xfe, 0x4d, 0x00 } }, // "-", decb (%ebp)
{ 2, { 0xff, 0xd7 } }, // ".", call *%edi ←この記事のテーマ
{ 2, { 0xff, 0xd6 } }, // ",", call *%esi ←これも
{ 10, { 0x80, 0x4d, 0x00, 0x00, 0x0f, 0x84, 0xFF, 0xFF, 0xFF, 0xFF } },
// "[", orb $0, (%ebp); jz XX
{ 5, { 0xe9, 0xFF, 0xFF, 0xFF, 0xFF } },
// "]", jmp XX
}; // TODO: short jump
struct block { size_t b; size_t e; } blocks[1024] = {{0,0}};
size_t b_used = 0, insn_len = 0;
char c;
int c2n() {
switch(c) {
case '>': return 0; case '<': return 1;
case '+': return 2; case '-': return 3;
case '.': return 4; case ',': return 5;
case '[': return 6; case ']': return 7;
}
return -1;
}
ssize_t p;
while(read(0, &c, 1) > 0) {
int n = c2n();
if (n >= 0) {
insn_len += insns[n].len;
write(fd, insns[n].code, insns[n].len);
if (n == 6) {
if (b_used == 1024) _exit(1);
blocks[b_used++].b = insn_len;
} else if (n == 7) {
p = b_used;
while(--p >= 0) {
if (blocks[p].e == 0) {
blocks[p].e = insn_len;
break;
}
}
if (p < 0) _exit(2);
}
}
}
for(p = 0; p < b_used; ++p) {
uint32_t rel = blocks[p].e - blocks[p].b;
lseek(fd, 52 + 32 + base_len + blocks[p].b - 4, SEEK_SET);
write(fd, &rel, 4);
rel = blocks[p].b - blocks[p].e - insns[6].len;
lseek(fd, 52 + 32 + base_len + blocks[p].e - 4, SEEK_SET);
write(fd, &rel, 4);
}
lseek(fd, 52 + 32 + base_len + insn_len, SEEK_SET);
c = 0xc3; // ret
write(fd, &c, 1);
return base_len + (++insn_len);
}
int main() {
char fn[] = "/tmp/BF_XXXXXX";
int fd = mkstemp(fn);
size_t code_size;
lseek(fd, 52 + 32, SEEK_SET);
code_size = write_code(fd);
lseek(fd, 0, SEEK_SET);
write_elf_header(fd);
write_program_header(fd, code_size);
fchmod(fd, 0755);
close(fd);
fprintf(stderr, "%s\n", fn);
return 0;
}標準入力からbrainfuckのプログラムを読んで、/tmp/BF_なんちゃら というファイル名のELFバイナリを吐きます。[ と ] でshort jumpしてないとか、連続する同じ命令はループにしろよとか、そのへんは手抜きです。つ gzexe。しかし130行もあるのか・・長いな。あとですね、このあいだshinhさんに、e_identを有効活用しなさいと叱られたので、最初はELFヘッダの書き出しの部分を、
.e_ident = { ELFMAG0, ELFMAG1, ELFMAG2 ,ELFMAG3,
'y','u','p','o','5','6','5','6','4','6','4','9' },のように「yupo5656夜露死苦」とし、暴走族風ELFにしていたのですが、よく考えたら私はx86_64なカーネルなので、その上でx86_32なバイナリを動かす場合はe_identをある程度まじめに埋めないとだめなのでした（カーネルに32bitモノだとわからせるために)。これはよくない。ちゃんと何か埋めたいです。
まとめ
というわけで、x86_64なカーネルでELF遊びをする方は、本文もちゃんとx86_64語で書いて、e_identにはきっちりポエムを埋めましょう。もちろん、真面目な紳士の皆様はコードを埋めましょう。
C++ で SICP
計算機プログラムの構造と解釈 の問題を、Schemeで一問一問解いてゆくのが流行りな2006年でした（師走気分）。このSICPをHaskellやCleanで解いている方はいますが、意外にもC++で解いている人が見当たらないので（注: あたりまえ）、C++のテンプレートはさっぱりよくわからんなぁと思いつつ適当にやってみます。ネタです。
[ネタ1] exercise 1.45, 1.46
まずは、問題1.45-1.46を。これらは1章の最終問題で、1章で学んだ手続き抽象のテクニック全てを使う感じがして楽しいです。xのn乗根を反復改良法で求める関数 nth-root を作るという設問です。
まずはSchemeで解く
私の拙いスキーム力を用いて書いてみるとこんな感じ*1？
(define (compose f g)
(lambda (x) (f (g x))))
(define (repeated f n)
(define (iter result i)
(if (= i n)
result
(iter (compose f result) (+ i 1))))
(iter f 1))
(define (average a b)
(/ (+ a b) 2))
(define (average-damp f)
(lambda (x) (average x (f x))))
(define (iterative-improve test-enough improve)
(define (try guess)
(let ((next (improve guess)))
(if (test-enough guess next)
next
(try next))))
(lambda (x) (try x)))
(define (fixed-point f first-guess)
(define (enough? a b)
(< (abs (- a b)) 0.000001))
((iterative-improve enough? (lambda (x) (f x))) first-guess))
(define (nth-root n x)
(define (damp-count m)
(if (< m 2)
0
(+ 1 (damp-count (/ m 2)))))
(define (nth-fold-average-damp l)
(repeated average-damp l))
(fixed-point ((nth-fold-average-damp (damp-count n))
(lambda (y) (/ x (expt y (- n 1)))))
1.0))
;; test
(nth-root 10 (* 3 3 3 3 3 3 3 3 3 3))実行してみます。3の10乗の10乗根を求める処理です。
gosh> 2.9999998914035997
ふむ。多分、ちゃんと動いているのではないかと。
Haskellで書き直す
上記をいきなりC++で書き直すと頭が混乱しそうなので、まずはHaskellで書き直します。C++(というかBoost)で型をミスったら数百行のエラーがでますが、Haskellなら数行で済みますので。HaskellかわいいよHaskell。
C++で書き直すことを考え、わざと関数の型を手で全部書きました。トリッキーな記述も少なめにしてあります。格好つけて、
-- 1に2を10回足す main = print $ (iterate ((+2).) id !! 10) 1
とか書いても、C++にぱっと変換できないですからねぇ。。。
-- % ghc -fglasgow-exts -O -W hoge.hs
compose :: (b -> c) -> (a -> b) -> (a -> c)
compose f g = \x -> f $ g x -- f.g です
-- "forall a." は GHC extension。「repeatedのaとiterのaは同じ型」だとコンパイラに伝えている。
-- わざわざ手動で型を書く場合、これが必要になることがある..っぽい。
repeated :: forall a. (a -> a) -> Int -> (a -> a)
repeated f n = iter f 1
where
iter :: (a -> a) -> Int -> (a -> a)
iter result i
| i == n = result
| otherwise = iter (compose f result) $ i + 1
average :: (Fractional a) => a -> a -> a
average a b = (a + b) / 2
average_damp :: (Fractional a) => (a -> a) -> a -> a
average_damp f x = average x $ f x
iterate_improve :: forall a. (a -> a -> Bool) -> (a -> a) -> a -> a
iterate_improve test_enough improve = try
where
try :: a -> a
try guess
| test_enough guess next = next
| otherwise = try next
where
next :: a
next = improve guess
fixed_point :: forall a. (Fractional a, Ord a) => (a -> a) -> a -> a
fixed_point = iterate_improve close_enough
where
tolerance :: a
tolerance = 0.000001
close_enough :: a -> a -> Bool
close_enough x y = tolerance >= (abs $ x - y)
nth_root :: (Fractional a, Ord a) => Int -> Int -> a
nth_root n x = let f = nth_fold_average_damp (damp_count n) in
fixed_point (f (\y -> fromIntegral x / expt y (n - 1))) 1.0
where
damp_count :: Int -> Int
damp_count m
| m < 2 = 0
| otherwise = 1 + (damp_count $ m `quot` 2)
expt :: (Fractional a) => a -> Int -> a
expt _ 0 = 1.0
expt y n = y * expt y (n - 1)
nth_fold_average_damp :: (Fractional a) => Int -> (a -> a) -> (a -> a)
nth_fold_average_damp l = repeated average_damp l
-- test
main = print $ nth_root 3 27
C++で書く
さて、（ネタの）本題、C++への書き換えです。Haskellの関数をほぼ一対一にC++の関数にします。C++は関数型のプログラミング言語ですので簡単です。関数が関数を受け取ったり、関数が関数を上に戻したりする部分は、「関数オブジェクト」という便利だか便利じゃないんだかよくわからないものを使って実装します。1章では数値しか扱っていない（データ構造は2章）こともあり、C++の関数オブジェクト程度の道具でも比較的容易にHaskellのコードを模倣できそうです。
- C++のコードの脇に、Haskellのコードをコメントとしてつけました。澄んだ心で読めば同じものに見えます
- さすがにSTLだけで書くのは厳しいんで、boost::functionとboost::bindは使います。以下、一応の注目ポイント：
- compose関数： boost::bindをネストすると関数を合成できるよ！ ←この記事で唯一役に立ちそうな記述
- average_damp関数： boost::bindする関数（第一引数）を_1にしたいときは、boost::apply
() を使う。Rは_1の戻りの型。 - average_damp_c関数： std::bind1stをboost::bindしています。これはひどい。
- C++では関数の中に関数は書けないので、その部分はdetailという名前空間に出しました。その関係で、ところどころdetail内の関数の引数の数が増えてしまっています。なお、これではダサいので、下のほうで3章をやるときには改善します。
- 変数の更新はしていません。更新するためにはもっと数学を勉強しないと無理らしいのですよ。
#include <iostream>
#include <boost/bind.hpp>
#include <boost/bind/apply.hpp>
#include <boost/function.hpp>
#include <cmath> // abs<T>()
#include <functional>
// libstdc++ extensions
#include <ext/functional> // identity<T>()
#include <ext/numeric> // power<T, U, M>()
namespace sicp {
/*
-- Haskell
compose :: (b -> c) -> (a -> b) -> (a -> c)
compose f g = \x -> f $ g x
*/
template <typename Op1, typename _Op2, typename _Op3>
Op1 compose(_Op2 f, _Op3 g) {
return boost::bind(f, boost::bind(g, _1));
}
/*
-- Haskell
repeated :: forall a. (a -> a) -> Int -> (a -> a)
repeated f n = iter f 1
where
iter :: (a -> a) -> Int -> (a -> a)
iter result i
| i == n = result
| otherwise = iter (compose f result) $ i + 1
*/
namespace detail { // for repeated()
template <typename _Op1>
_Op1 repeated_iter(_Op1 f, _Op1 result, int n, int i) {
if (i == n)
return result;
else
return repeated_iter(f, compose<_Op1>(f, result), n, i + 1);
}
}
template <typename T,
typename _Op1 /* T -> T */ >
_Op1 repeated(_Op1 f, int n) {
return detail::repeated_iter<_Op1>(f, __gnu_cxx::identity<T>(), n, 0);
}
/*
-- Haskell
average :: (Fractional a) => a -> a -> a
average a b = (a + b) / 2
*/
template<typename T>
boost::function<T (T, T)> average() {
return boost::bind(std::divides<T>(), boost::bind(std::plus<T>(), _1, _2), 2);
}
/*
-- Haskell
average_damp :: (Fractional a) => (a -> a) -> a -> a
average_damp f x = average x $ f x
*/
template<typename T>
boost::function<T (boost::function<T (T)>, T)>
average_damp() {
return boost::bind(average<T>(),
_2, boost::bind(boost::apply<T>(), // <T> は、すぐ後の _1 の戻りの型
_1, _2));
}
// Haskellでは、(a -> a) -> a -> a と (a -> a) -> (a -> a) を区別する必要がないが、
// C++では区別しないといけない....たぶん。よって別関数を用意。
// しかも、前者から後者への変換が面倒。
template<typename T>
boost::function<boost::function<T (T)> (boost::function<T (T)>)>
average_damp_c() {
typedef boost::function<T (T)> T2T;
return boost::bind(std::bind1st<boost::function<T (T2T, T)>, T2T>,
/* ^type of average_damp<T>() ^type of placeholder */
average_damp<T>(), _1);
}
/*
-- Haskell
iterate_improve :: forall a. (a -> a -> Bool) -> (a -> a) -> a -> a
iterate_improve test_enough improve = try
where
try :: a -> a
try guess
| test_enough guess next = next
| otherwise = try next
where
next :: a
next = improve guess
*/
template <typename T,
typename _Op1, /* T -> T -> Bool */
typename _Op2> /* T -> T */
T iterate_improve(_Op1 test_enough, _Op2 improve, T guess) {
const T& next = improve(guess);
// try関数は省略。自身に再帰。
if (test_enough(guess, next))
return next;
else
return iterate_improve<T>(test_enough, improve, next);
}
/*
-- Haskell
fixed_point :: forall a. (Fractional a, Ord a) => (a -> a) -> a -> a
fixed_point = iterate_improve close_enough
where
tolerance :: a
tolerance = 0.000001
close_enough :: a -> a -> Bool
close_enough x y = tolerance >= (abs $ x - y)
*/
namespace detail { // for fixed_point()
template <typename T>
bool close_enough(T a, T b) {
static const T tolerance = 0.000001;
return (std::abs(a - b) <= tolerance);
}
}
template <typename T, typename _Op1>
T fixed_point(_Op1 f, T first_guess) {
return iterate_improve(boost::bind(detail::close_enough<T>, _1, _2), f, first_guess);
}
/*
-- Haskell
nth_root :: (Fractional a, Ord a) => Int -> Int -> a
nth_root n x = let f = nth_fold_average_damp (damp_count n) in
fixed_point (f (\y -> fromIntegral x / expt y (n - 1))) 1.0
where
damp_count :: Int -> Int
damp_count m
| m < 2 = 0
| otherwise = 1 + (damp_count $ m `quot` 2)
expt :: (Fractional a) => a -> Int -> a
expt _ 0 = 1.0
expt y n = y * expt y (n - 1)
nth_fold_average_damp :: (Fractional a) => Int -> (a -> a) -> (a -> a)
nth_fold_average_damp l = repeated average_damp l
*/
namespace detail { // for nth_root()
int damp_count(int m) {
return (m < 2 ? 0 : (1 + damp_count(m / 2)));
}
template <typename T>
boost::function<T (T, int)> expt() {
// 自作も容易だが、power関数というのが用意されているので、それを使って手抜き。
// static_castでライブラリ側のやや曖昧なオーバーロードを解決。
return boost::bind(static_cast<T (*)(T, int)>(__gnu_cxx::power), _1, _2);
}
template<typename T>
boost::function<boost::function<T (T)> (boost::function<T (T)>)>
nth_fold_average_damp(int n) {
return repeated<boost::function<T (T)> >(average_damp_c<T>(), n);
}
}
// これが、最終的に欲しかった関数 (xのn乗根を求める)
template <typename T>
T nth_root(int n, int x) {
typedef boost::function<T (T)> T2T;
boost::function<T2T (T2T)> f = detail::nth_fold_average_damp<T>(detail::damp_count(n));
T2T g = boost::bind(std::divides<T>(), x, boost::bind(detail::expt<T>(), _1, n - 1)); // y -> x/y^(n-1)
return fixed_point<T>(f(g), 1.0);
}
}うーん、これはひどい。boost::phoenixのv2やFC++あたりを使えば少しは綺麗になるのかどうなのか。なお、expt()は、boost::lambda::if_then_else_returnで書きたかった↓
namespace bl = boost::lambda;
return bl::if_then_else_return(/* if _2 == 0 */ bl::bind(std::equal_to<int>(), bl::_2, 0),
/* then */ bl::bind(__gnu_cxx::identity<T>(), 1),
/* else */ bl::bind(std::multiplies<T>(),
bl::_1,
bl::bind(expt<T>(), // ここがだめ
bl::_1,
bl::bind(std::minus<int>(), bl::_2, 1))));のですが、後に書いた問題1.37と同じ理由でやめました（私には無理っぽ）。
テスト
適当にmain関数を書いて、実行してみます。
int main() {
typedef double T;
// 1.0と2.0の平均を求める
boost::function<T (T, T)> f = sicp::average<double>();
std::cout << f(1.0,2.0) << std::endl; // OK
// f(x) = 2x なfを渡して、1.0とf(1.0)の平均を求める
boost::function<T (boost::function<T (T)>, T)> f2 = sicp::average_damp<T>();
std::cout << f2(boost::bind(std::multiplies<T>(), _1, 2), 1.0) << std::endl;
// 1.0とf(1.0)の平均を求める - その2
boost::function<boost::function<T (T)> (boost::function<T (T)>)> g = sicp::average_damp_c<T>();
std::cout << g(boost::bind(std::multiplies<T>(), _1, 2))(1.0) << std::endl;
// 平均緩和法で3の平方根を求める
boost::function<T (T)> f3 = boost::bind(std::divides<double>(), 3, _1); // y -> x / y
std::cout << sicp::fixed_point(boost::bind(f2, f3, _1), 1.0) << std::endl;
// 2.0の10乗を求める
boost::function<T (T, int)> f4 = sicp::detail::expt<T>();
std::cout << f4(2, 10) << std::endl;
// 平均緩和法で16の4乗根を求める
boost::function<boost::function<T (T)> (boost::function<T (T)>)> f5 = sicp::detail::nth_fold_average_damp<T>(sicp::detail::damp_count(4));
boost::function<T (T)> f6 = f5(boost::bind(std::divides<double>(), 16, boost::bind(sicp::detail::expt<T>(), _1, 3))); // y -> x / y^3
std::cout << sicp::fixed_point(boost::bind(f2, f6, _1), 1.0) << std::endl;
// test
std::cout << sicp::nth_root<T>(4, 16) << std::endl
<< sicp::nth_root<T>(10, 1024) << std::endl
<< sicp::nth_root<T>(2, 2) << std::endl
<< sicp::nth_root<T>(2, 3) << std::endl
<< sicp::nth_root<T>(5, 1234) << std::endl;
return 0;
}
コンパイルと実行
コンパイルして実行するとこんなかんじ。
% g++ -Wall -Wextra -O2 1.46_plus_1.45.cpp % ./a.out 1.5 1.5 1.5 1.73205 1024 2 2 2 1.41421 1.73205 4.15205
ちなみに、このnth_rootで平方根を求めてみたところ、libmのsqrt関数の約1/100倍速でした。速っ。GCCには-foptimize-sibling-callsというすばらしい最適化があることですし、こんなコードでもまったく問題あります。
小まとめ
forループ書いたら負けかなと思ってる
[ネタ2] exercise 3.1
次は、問題3.1です。Paul Grahamさんの技術野郎の復讐(Revenge of the Nerds)の付録の問題「accumulator generatorを作れ」とほぼ同じです。
私が言う言語の相対的な力を説明するために、次の問題を考えてみよう。アキュムレータを生成する関数、すなわち、数nを取り、「数iを取ってnをiだけ増加させ、その増加した値を返す関数」を返すような関数だ。 (「増加させる」に注意。ただ足すだけではない。アキュムレータ(累積器)だから累積させなければ)。
これをC++でやってみるのです。ハッカーと画家 コンピュータ時代の創造者たち にも載ってる問題です。この問題は、最初の例とは違って、C++でもまぁどうにか読める範囲で解けそうです。
以下、なぜか気分で、boostをまったく使っていない人向けの説明です。今更すぎる。。しかも、そういう人はたぶん私のblogなど読んでいない罠。いやむしろ誰も読んでいない罠。まぁなんでもいいか。
boost::functionとboost::bind
問題3.1の、他の言語での解答例を見ると*2、関数型言語的テクニックを使いまくっている例が多いです。さて、C++でどのように実装したもんでしょうか。まず、高階関数(関数を受け取る関数、または関数を上に戻す関数)を書くにはboost::functionを使えば良さそうです。たとえば、『「intを引数にとってintを戻す関数f」を引数に取って、「doubleを引数にとってdoubleを戻す関数」を戻す関数hoge』は、次のように書けます。
// "arg" のところには任意の変数名を書けます。何を書いても動作は同じです。省略も可。
boost::function<double (double arg)>
hoge(boost::function<int (int arg)> f) {
...
}また、C++では関数の中に関数を書くことはできないので、世間一般で言う(?)closureのように*3、「lexical に外側にある変数を参照あるいは更新できる」を直接実現するのは難しいというか、外側にある変数というといわゆるグローバル変数しかなかったりするわけですが、boost::bindを使うと似たようなことは出来ます。こんな感じですね*4。詳しくは"How the Boost Bind Library Can Improve Your C++ Programs"あたりを。
int add(int a, int b) { return a + b; } // closureもどきの元ネタ(?)にする予定の関数
boost::function<int (void)> bar(int x) {
return boost::bind(add, _1, x);
}蛇足ですが、STLが好きな人は、add関数を書かずに、予め用意されているstd::plus関数テンプレート(戻り値は関数オブジェクト)を使って、
boost::function<int (void)> bar(int x) {
return boost::bind(std::plus<int>(), _1, x);
}とか
boost::function<int (void)> bar(int x) {
return std::bind2nd(std::plus<int>(), x);
}でもOK、同じ出力が得られます。ただ注意が必要なのは、このケースでは、closureもどきに閉じ込めているのは変数x自身(?)ではなく、変数xのコピーだという点です。add関数が引数を値で受け取っているのでそこでコピーが行われますし、できあがった関数オブジェクトがコピーされるタイミング*5でも「変数xのコピー」のコピーが起きます。今回は、「closeされた変数を参照するだけ」かつ「変数がコピー可能」かつ「変数をコピーするコストが安い」ので、これでも問題ないわけです。
boost::functionとboost::bindとboost::shared_ptrでaccumulator generator
さて、Revenge of the Nerds の accumulator generator 問題です。なお、ここからは、C++で変数を更新するのは邪道だと考えている方には関係ない話です。この問題をSchemeやRubyで解くとこんな感じになります。先の回答サイトからのコピペです。私はLLワカリマセーン。
;; Scheme
(define (foo n)
(lambda (i) (set! n (+ n i)) n))
# Ruby
def foo (n)
lambda {|i| n += i } end「手続きを上(?)に戻し、かつその中にclose(?)されている変数を更新する」という処理になっていることがわかると思います。ですから、最初のboost::bindの例のように、closeしたはずの変数nがコピーされてしまうとおかしなことになります。ですから、次のようにboost::bindでローカル変数をfoo_closure_にコピーするだけでは(当然)うまくいきません。
// NG 1
template <typename T> T foo_closure_(T n, T i) {
return (*n += i);
}
template <typename T> boost::function<T (T arg1)> foo(T n) {
return boost::bind(foo_closure_<T>, n, _1);
}また、次のように関数オブジェクト内に変数の参照(やポインタ)を保持する方法もうまくいきません。なぜなら、関数fooを抜けた時点でスタック上に置かれた引数nは綺麗に消え去ってしまうからです。
// NG 2
template <typename T> T foo_closure_(T& n, T i) {
return (*n += i);
}
template <typename T> boost::function<T (T arg1)> foo(T n) {
return boost::bind(foo_closure_<T>, boost::ref(n), _1);
}えー、なぜSchemeなどで問題が起きないかというと、これらの言語では、一度生成されたオブジェクトはずっと生きていて（無限エクステント？）、誰も参照する人がいなくなったときに限って削除されるからですね。多分。C++でこれを模倣しようとすると、Boehm GCなどの飛び道具を使うか、さもなければ地道にオブジェクトの参照カウントを行うしかなさそうです。boostには、boost::shared_ptrという便利なものがあるので、それを使います。
// OK, Paul Graham の accumulator generator のC++実装
template <typename T> T foo_closure_(boost::shared_ptr<T> n, T i) {
return (*n += i);
}
template <typename T> boost::function<T (T arg1)> foo(T n) {
boost::shared_ptr<T> pn(new T(n));
return boost::bind(foo_closure_<T>, pn, _1);
}使ってみます。
int main() {
boost::function<int (int arg1)> f1 = foo(10);
std::cout << f1(5) << std::endl;
std::cout << f1(5) << std::endl;
std::cout << f1(5) << std::endl;
std::cout << f1(5) << std::endl;
boost::function<double (double arg1)> f2 = foo(1.5);
std::cout << f2(0.5) << std::endl;
std::cout << f2(0.5) << std::endl;
std::cout << f2(0.5) << std::endl;
std::cout << f2(0.5) << std::endl;
}予定通りにうごきます。次の通り。
% ./a.out 15 20 25 30 2 2.5 3 3.5
無問題。わーい。
boost::lambdaでクロージャもどき
一応出来たんですが、foo_closure関数を別に作成しているのはいまいちです。そこでlambda。boost::lambdaというライブラリを使うと、例えば
int add(int a, int b) { return a + b; }
boost::function<int (void)> bar(int x) {
return boost::bind(add, _1, x);
}を、add関数を作ることなしに、
boost::function<int (void)> bar(int x) {
return _1 + x;
}のように書けます。xは、関数オブジェクト内「コピー」され保持されます。「lexicalに外側にある変数xを参照」できています。closureっぽい！（ようなそうでもないような）。参照だけで、更新はできませんけどねー。これを応用しまして、accumulate generator を改良すると、
// NG
template <typename T> boost::function<T (T arg1)> foo(T n) {
boost::shared_ptr<T> pn(new T(n));
return (*pn += _1);
}となります.....と言いたい所なのですが、上記コード、コンパイルはできますが実行するとコケます。fooを抜けた瞬間にpnの指し先がdeleteされてしまうです。参照カウントがきちんと増加していません。(*pn) つまりint型の変数がlambdaライブラリに渡って、ライブラリ側ではint&で変数を掴まえている? (+= のときだけは?) ... ようです。謎。うーん。いまのところ、次のように書く方法しか見つけていません。
// OK, Paul Graham の accumulator generator の最終的なC++実装
template <typename T> boost::function<T (T arg1)> foo(T n) {
boost::shared_ptr<T> pn(new T(n));
return boost::lambda::bind(boost::function<T (typeof(pn), T)>(*_1 += _2), pn, _1);
}まぁ、実用上(?)これで問題ないというか、SICPの問題の答えにはちゃんとなっているのですが、見た目が複雑でちょっと嫌。C++の達人の方の突っ込み待ち。どなたかぜひ良い代案を。。。
ちょっと改造
「Rubyの呼び出し可能オブジェクトの比較(1)」の「普通のProc」のあたりのコードのように、pnを閉じこんでいるクロージャを複数作成して、下に渡したり、上に渡したりして楽しむこともできますね。
#include <iostream>
#include <boost/utility.hpp>
#include <boost/function.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/lambda/bind.hpp>
#include <boost/lambda/lambda.hpp>
#include <boost/tuple/tuple.hpp>
using boost::lambda::_1;
using boost::lambda::_2;
template <typename R, typename T> R foo(T n) {
typedef boost::shared_ptr<T> P;
typedef boost::function<T (T)> F;
typedef boost::function<T (P, T)> F_;
// 最初は0を覚えておいて
P pn(new T());
F closure1 = boost::lambda::bind(F_(*_1 += _2), pn, _1);
F closure2 = boost::lambda::bind(F_(*_1 += _2), pn, _1);
F closure3 = closure2; // コピーしてみたり。
// 無意味に「下」でnにしてみる
bar(closure1, n);
// クロージャを3つまとめて「上」に戻す
return boost::make_tuple(closure1, closure2, closure3);
}
template <typename F, typename T> void bar(F f, T n) {
std::cout << f(n) << std::endl;
}
int main() {
typedef boost::function<int (int)> F;
boost::tuple<F, F, F> f = foo<typeof(f)>(10);
// 3つを並行に使ってみて、値の変化を見る
std::cout << f.get<0>()(5) << std::endl;
std::cout << f.get<1>()(5) << std::endl;
std::cout << f.get<2>()(5) << std::endl;
std::cout << f.get<2>()(5) << std::endl;
std::cout << f.get<1>()(5) << std::endl;
std::cout << f.get<0>()(5) << std::endl;
}
[ネタ3] exercise 3.4
次は問題3.4です。預金額を覚えているオブジェクトを戻す関数を、Schemeで作る問題ですね。上に戻したdispatch関数が、"deposit"とか"withdraw"なんていうメッセージを受け取って、それに応じたオシゴトをします。とりあえず私のヘボSchemeカを生かして実装:
(define (make-account balance password)
(define (withdraw amount)
(if (> balance amount)
(begin (set! balance (- balance amount))
balance)
(error "Insufficient funds")))
(define (deposit amount)
(set! balance (+ balance amount)) balance)
(define (call-the-cops)
(error "Thief!!"))
(let ((count 0)
(count-max 7))
(define (dispatch pw m)
(if (not (eq? pw password))
(begin (set! count (+ count 1))
(if (>= count count-max)
(call-the-cops))
(error "Incorrect password"))
(begin (set! count 0)
(cond ((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
(else (error "Unknown request -- MAKE-ACCOUNT" m))))))
dispatch))C++には、classというあまり知られていないキーワードがありまして、それを使って頑張れば、上のSchemeのコードを次のように書けなくもないのですが、
class account : boost::noncopyable {
public:
account(int balance, const std::string& password) : balance_(balance), password_(password) {}
int withdraw(const std::string& password, int amount) { if (...
int deposit(const std::string& password, int amount) { if (...
private:
int balance_;
std::string password_;
};もっと素直にschemeのコードを移植したものをつくろうよ、と。boost::lambdaで完全移植。Haskellでいったん書き直していないのはモナd(略)。
コード
#include <iostream>
#include <string>
#include <stdexcept>
#include <functional>
#include <boost/function.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/lambda/lambda.hpp>
#include <boost/lambda/if.hpp>
#include <boost/lambda/bind.hpp>
#include <boost/lambda/construct.hpp>
#include <boost/lambda/exceptions.hpp>
// 関数書いたら負け..という気がしないでもないが、
// 設問自体が「手続きを呼べ」なのでOKということにしておく。
template <typename T> T call_the_cops(T) {
std::cout << "通報しますた" << std::endl;
throw std::runtime_error("Incorrect password");
}
template <typename R, typename T>
R make_account(T balance, std::string password) {
using namespace boost::lambda;
typedef boost::function<T (T)> F; // withdraw(), deposit()
typedef boost::function<F (std::string, std::string)> F2; // dispatch()
typedef boost::shared_ptr<T> P;
typedef boost::shared_ptr<std::size_t> P2;
P pbalance(new T(balance)); // local-state-variable
P2 pcnt(new std::size_t()); // local-state-variable
// passwordも局所状態変数だが、immutableなのでshared_ptrにはしない
// (shared_ptrにすると、"*" の扱いでコードがややこしくなるんで)
#define ifter if_then_else_return /* 画面の幅の都合... */
/*
(define (withdraw amount)
(if (> balance amount)
(begin (set! balance (- balance amount))
balance)
(error "Insufficient funds")))
*/
typedef boost::function<T (P, T)> F_;
F closure_withdraw
= bind(F_(ifter(*_1 >= _2,
*_1 -= _2,
(throw_exception(std::runtime_error("Insufficient funds")), T() /*dummy*/ ))),
pbalance, _1);
/*
(define (deposit amount)
(set! balance (+ balance amount)) balance)
*/
F closure_deposit = bind(F_(*_1 += _2), pbalance, _1);
/*
(let ((count 0)
(count-max 7))
(define (dispatch pw m)
(if (not (eq? pw password))
(begin (set! count (+ count 1))
(if (>= count count-max)
(call-the-cops))
(error "Incorrect password"))
(begin (set! count 0)
(cond ((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
(else (error "Unknown request -- MAKE-ACCOUNT" m))))))
*/
static const std::size_t cnt_max = 7; // 通報閾値
typedef boost::function<F (std::string, std::string, P2)> F2_;
F2 closure_dispatch
= bind(F2_(ifter(_1 != password,
ifter(++(*_3) >= cnt_max,
::call_the_cops<T>,
(throw_exception(std::runtime_error("Incorrect password")), F() /*dummy*/ )),
(*_3 = 0, ifter(_2 == "withdraw",
closure_withdraw,
ifter(_2 == "deposit",
closure_deposit,
(throw_exception(bind(constructor<std::runtime_error>(),
bind(std::plus<std::string>(),
"Unknown request -- MAKE-ACCOUNT: ",
_2))),
F() /*dummy*/ )))))),
_1, _2, pcnt);
return closure_dispatch;
}
使ってみる
int main() {
typedef boost::function<boost::function<int (int)> (std::string, std::string)> F;
// 口座開設。第二引数がパスワード。
F dispatch
= make_account<F>(1000, "open sesame");
// 預けて、おろしてみる
std::cout << "balance: " << dispatch("open sesame", "deposit")(1000) << std::endl;
std::cout << "balance: " << dispatch("open sesame", "withdraw")(500) << std::endl;
// dispatchを適当にコピーしても無問題
F dispatch2 = dispatch;
std::cout << "balance: " << dispatch2("open sesame", "withdraw")(500) << std::endl;
// 暗証を間違えてみる
try {
std::cout << dispatch("bad_pass", "withdraw")(10) << std::endl;
} catch(std::runtime_error& e) {
std::cout << e.what() << std::endl;
}
// 7回連続で間違えると通報される
for(int i = 0; i < 6; ++i) try {
dispatch("bad_pass", "withdraw")(100);
} catch(...) {}
// 預金額をこえておろしてみる
try {
std::cout << dispatch("open sesame", "withdraw")(1001) << std::endl;
} catch(std::runtime_error& e) {
std::cout << e.what() << std::endl;
}
// dispatch()に渡すメッセージを間違えてみる
try {
std::cout << dispatch("open sesame", "give_me_1000000_dollars")(500) << std::endl;
} catch(std::runtime_error& e) {
std::cout << e.what() << std::endl;
}
}
実行結果
% ./a.out balance: 2000 balance: 1500 balance: 1000 Incorrect password 通報しますた Insufficient funds Unknown request -- MAKE-ACCOUNT: give_me_1000000_dollars
うーん、美し...くない。
解説?
レキシカルに見えているものをclosure_ほげのbindの中でさらっと使って問題がない点、closure_ほげを適当にコピーしたり、closure_dispatchのbindの中で別のclosureをcloseしたり、closure_ほげを上に戻したりしてもGC..もといshared_ptrによる参照カウントのおかげでまったく問題ない点、クロージャもどきの間で局所状態変数を共有している点...などが一応の見どころです...たぶん。Valgrind様を信じるならメモリリークしていません。main関数のfor文のところでの微妙なオシャレは、ちょっとやってみたかっただけです。
よーしパパ、この調子で関数型言語C++にオブジェクト指向機能をどんどん実装しちゃうぞー（しません）。boost::lambdaは、placeholderが _3 までしか用意されていないので足りなくなりそうだし（そういう問題じゃない）。
小まとめ
classって書いたら負けかなと思ってる
[ネタ4] exercise 1.37 (CPS in C++)
1章にもどって、問題1.37をやります。2章が抜けてしまったな。。。この図のように、無限連分数のk番目のtermまでの和を求めろという問題です。Int -> a な関数、NとDは外から適当に与えます。一般的には、こちらの回答例にあるようにN1/D1側から再帰で足しこんでいくか、逆に、累積変数(状態変数?)を使ってNk/Dk側から反復的に足していくかになると思いますが、ここではネタ力向上のため、というかある方にネタっぽい方法を教えていただいたので、「N1/D1側から, 反復的プロセスで, 答えを求める」方法を採用します。Haskellだとこんな感じです。非常に面白い方法だと思いました。
cont_frac :: (Fractional a) => Int -> (Int -> a) -> (Int -> a) -> a
cont_frac k n d = g 0 id
where
g i c
| i == k = c $ n i / d i
| otherwise = g (i + 1) $ \x -> c $ n i / (d i + x)iを0からkまでまわしています。関数gの引数cが累積変数。でも、溜まるのは数値ではなくて計算です。Haskellerじゃない方に一応説明すると、
- a $ b c d は a ( b c d )
- \x -> は (lambda (x) (
です。DiとNiが常に1だと、この連分数は黄金比の逆数に近づいてゆくということなので、k=100くらいで確認します。
main = print $ 1 / cont_frac 100 (const 1) (const 1)
実行してみると、ちゃんと1.618..になりました。OK。C++で書き直します。
#include <ext/functional>
#include <boost/function.hpp>
#include <boost/lambda/bind.hpp>
#include <boost/lambda/lambda.hpp>
typedef boost::function<double (int)> A;
namespace {
typedef boost::function<double (double)> B;
double g(A n, A d, int k, int i, B c) {
if (i == k) return c(n(i) / d(i));
return g(n, d, k,
i + 1,
boost::lambda::bind(c, n(i) / (d(i) + boost::lambda::_1)));
}
}
double cont_frac(A n, A d, int k) {
return g(n, d, k, 0, __gnu_cxx::identity<double>());
}
int main() {
std::printf("golden ratio: %lf\n",
1 / cont_frac(__gnu_cxx::constant1<double>(1.0),
__gnu_cxx::constant1<double>(1.0),
100));
}4つめということでいい加減力尽きてきたので、typename T とすべきところをdoubleに決め打ちましたが、まぁどちらにせよ簡単簡潔です。id関数とconstant関数はSTLには含まれていないので、__gnu_cxx名前空間のものを使いました。自作してもよいです。
gを本物のC++関数にしてしまった時点で負けた感じです（誰と勝負しているのかは不明）。gを、boost::lambdaでfの中に書ければ楽しいわけですが、boost::lambda::if_then_else_return で再帰させると、i == k に達しても再帰が止まらないんですよね(SICPの問題1.6、special formではないifだと云々と同じ..たぶん)。うーん。まぁ、変数cに計算を溜めることはできたのでよしとします。飽きてきたのでC++でやるのはこのへんで！
小まとめ
まともなifと、あとstd::なid関数、constant関数がほしい。後ろ2つはC++0xで入ったりしないのかな。あと、ここまでclassとかstructとか書かずにBoost.Lambdaで4つほどネタを書いてみましたが、ほげ<ふが>::result 系が好きな人には面白くない気もします。
hello worldなELFバイナリを出力するCのプログラム（の一番単純な奴）
こちらの記事(Binary HacksのHack #25の軽い補足)は、「インラインアセンブラをちょっとだけ使って、gccに小さなhello worldバイナリを出力させる」というお話でした。一方、小さいHello Worldが欲しかったら、gccにELF実行バイナリを出力させるのではなく、「自力でELFを吐くCのコードを書いてしまう」手もあります。ご利用のCPUのアセンブリ言語がわかるのでしたら、こっちの方法でHello Worldするのも悪くないですね。こちらの方法でしたら、「急にbrainf*ckのコンパイラが書きたくなった*1」などの非常によくあるシチュエーションにも応用が効きますしー。
ELF直書きって、なんかすごく難しいように思われていると思うんですが(いや、DSO吐いたりするのは実際面倒ですが)、hello worldくらいだったらなんてことないです。次の4つの処理を順に行えばいいだけです。
- ELFヘッダをwrite
- プログラムヘッダをwrite
- 文字列 "Hello World!\n" をwrite
- システムコールを使って文字列を出力するコードをwrite
以下にELFを吐くCプログラムの雛型的なものを示しますので、ELFゴルファーになる前の学習ネタなんかに使っていただければと。必ずしもC言語で書かなくてもいいんですが（そのほうがタイプ数は少ない）、最初はelf.hに沿ってコードを書く方がわかりやすい（ひともいる）かと。
基本方針
標準出力にELFなバイナリをwriteします。できあがったバイナリの全体をそのままメモリにロードします（カーネルにロードしてもらいます）。本当は、上記の3.と4.だけロードすればよいのですが、いろいろ面倒なんで全体を。ロードするアドレスは、LOAD_ADDRESS とします。単純に 0x00000000 でもいいですし、お好きな場所に城を建ててもいいです。
1. ELFヘッダ書き
/usr/include/elf.h に、Elf32_Ehdr という構造体があります。この構造体のメンバに適当な値をセットして、そのままwriteすればOKです。e_entryメンバ以外は、決まり文句です。e_entryには、上記4.の(ファイルオフセットではなくメモリ上での)アドレスを指定します。埋めてある定数についての詳細は、elf(5)のmanか、Binary Hacksか、Linkers&Loaders あたりを...。あーもちろん、BinaryHacks のukaiさんの記事が一番お薦めです(宣伝)。
void out_elf_header() {
Elf32_Ehdr ehdr = {
.e_ident = { ELFMAG0, ELFMAG1, ELFMAG2 ,ELFMAG3,
ELFCLASS32, ELFDATA2LSB, EV_CURRENT, ELFOSABI_SYSV },
.e_type = ET_EXEC,
.e_machine = EM_386,
.e_version = EV_CURRENT,
.e_entry = LOAD_ADDRESS + sizeof(Elf32_Ehdr) + sizeof(Elf32_Phdr) + STRING_LEN,
.e_phoff = sizeof(Elf32_Ehdr),
.e_shoff = 0, // dummy
.e_flags = 0x0,
.e_ehsize = sizeof(Elf32_Ehdr),
.e_phentsize = sizeof(Elf32_Phdr),
.e_phnum = 1,
.e_shentsize = 0, // dummy
.e_shnum = 0,
.e_shstrndx = 0, // dummy
};
write(1, &ehdr, sizeof(Elf32_Ehdr));
}
2. プログラムヘッダ書き
同じく Elf32_Phdr をwriteするだけです。最低限、PT_LOAD なヘッダを一つ書けばOKです*2。p_offsetは、ファイルのどこからメモリに貼るかのオフセット値です。全体を貼るので、0x0にします。埋める値の計算が面倒なのは、p_fileszとp_memszくらいでしょうか。1.〜4.の合計サイズを書きます。p_vaddrには、ファイルをメモリのどこにロードして欲しいかを書きます。カーネル様への指示ですね。それ以外は定型文です。なお、p_offset % p_align == 0 かつ p_vaddr % p_align == 0 でないとまずかったような気がするんですが詳しくはゴルファーの皆様のページでも見てください。
void out_program_header() {
uintptr_t code_len = (uintptr_t)&end_ - (uintptr_t)&start_;
Elf32_Phdr phdr = {
.p_type = PT_LOAD,
.p_offset = 0x0,
.p_vaddr = LOAD_ADDRESS,
.p_paddr = 0, // dummy
.p_filesz = sizeof(Elf32_Ehdr) + sizeof(Elf32_Phdr) + STRING_LEN + code_len,
.p_memsz = sizeof(Elf32_Ehdr) + sizeof(Elf32_Phdr) + STRING_LEN + code_len, /* BSSが欲しいならここを増やす */
.p_flags = PF_R | PF_X,
.p_align = 0x1000,
};
write(1, &phdr, sizeof(Elf32_Phdr));
}
3. 文字列書き
単に、write(1, "Hello World!\n", 13); するだけです。下記コードのように、4.のコードの中に.byte疑似命令で埋め込んでもいいです。.string という疑似命令で埋めてもいいです。ということは、1.〜3. 全部を、.byte や .string で埋めてもいいですが、そういう方向に行くならgcc(gas)でなくnasmを使う方が良いと思われます。
__asm__ ("rodata_: \r\n"
".byte 'h' \r\n"
".byte 'e' \r\n"
(略)
"start_: \r\n"
"movl $4, %eax \r\n" // eax: system call number (__NR_write)
"movl $1, %ebx \r\n" // ebx: fd (stdout)
4. コード書き
インラインアセンブラでいきなりコードを書き、GCCにコンパイルさせたあとのコードをwriteするコードもいっしょに書きます。GCC拡張である「&&でラベル参照」技を使うとラクにそういうことができます。
__asm__ ("start_: \r\n"
"movl $4, %eax \r\n" // eax: system call number (__NR_write)
"movl $1, %ebx \r\n" // ebx: fd (stdout)
"movl $" ECX ", %ecx \r\n" // ecx: addr
"movl $13, %edx \r\n" // edx: len
"int $0x80 \r\n"
"movl $1, %eax \r\n" // eax: system call number (__NR_exit)
"movl $0, %ebx \r\n" // ebx: exit code
"int $0x80 \r\n"
"end_: ");
extern char *start_, *end_;これを用意して、
void write_code() {
const uintptr_t code_len = (uintptr_t)&end_ - (uintptr_t)&start_;
write(1, &rodata_, code_len);
}これだけです*3。文字列を出力して(write)、exitします。なお、すこしでも短いバイナリが欲しい場合には、movlとかアリエえませんので、適当に改変してください。まずは116? 111? バイトくらいに改造するのがよいと思います。
ソースコード全体
131バイトのバイナリを生成するコードです。あれー、さっきより1バイト少ないな...まぁいいか。
#include <elf.h>
#include <unistd.h> // write
#define PAGE_ALIGN(adr) ((adr) & ~(0x1000 - 1)) // 16進下3桁を切り捨てるだけ
#define LOAD_ADDRESS PAGE_ALIGN(0x12345678) // 0x12345000にロード
#define STRING_LEN 13
#define TO_STR(s) TO_STR_(s)
#define TO_STR_(s) #s
#define ECX \
TO_STR(LOAD_ADDRESS + 52 + 32) // LOAD_ADDRESS + sizeof(Elf32_Ehdr) + sizeof(Elf32_Phdr)
__asm__ ("start_: \r\n"
"movl $4, %eax \r\n" // eax: system call number (__NR_write)
"movl $1, %ebx \r\n" // ebx: fd (stdout)
"movl $" ECX ", %ecx \r\n" // ecx: addr
"movl $13, %edx \r\n" // edx: len
"int $0x80 \r\n"
"movl $1, %eax \r\n" // eax: system call number (__NR_exit)
"movl $0, %ebx \r\n" // ebx: exit code
"int $0x80 \r\n"
"end_: ");
extern char *start_, *end_;
void out_elf_header() {
Elf32_Ehdr ehdr = {
.e_ident = { ELFMAG0, ELFMAG1, ELFMAG2 ,ELFMAG3,
ELFCLASS32, ELFDATA2LSB, EV_CURRENT, ELFOSABI_SYSV },
.e_type = ET_EXEC,
.e_machine = EM_386,
.e_version = EV_CURRENT,
.e_entry = LOAD_ADDRESS + sizeof(Elf32_Ehdr) + sizeof(Elf32_Phdr) + STRING_LEN,
.e_phoff = sizeof(Elf32_Ehdr),
.e_shoff = 0, // dummy
.e_flags = 0x0,
.e_ehsize = sizeof(Elf32_Ehdr),
.e_phentsize = sizeof(Elf32_Phdr),
.e_phnum = 1,
.e_shentsize = 0, // dummy
.e_shnum = 0,
.e_shstrndx = 0, // dummy
};
write(1, &ehdr, sizeof(Elf32_Ehdr));
}
void out_program_header() {
uintptr_t code_len = (uintptr_t)&end_ - (uintptr_t)&start_;
Elf32_Phdr phdr = {
.p_type = PT_LOAD,
.p_offset = 0x0,
.p_vaddr = LOAD_ADDRESS,
.p_paddr = 0, // dummy
.p_filesz = sizeof(Elf32_Ehdr) + sizeof(Elf32_Phdr) + STRING_LEN + code_len,
.p_memsz = sizeof(Elf32_Ehdr) + sizeof(Elf32_Phdr) + STRING_LEN + code_len,
.p_flags = PF_R | PF_X,
.p_align = 0x1000,
};
write(1, &phdr, sizeof(Elf32_Phdr));
}
void out_code() {
uintptr_t code_len = (uintptr_t)&end_ - (uintptr_t)&start_;
write(1, &start_, code_len);
}
int main() {
out_elf_header();
out_program_header();
write(1, "hello world!\n", 13);
out_code();
return 0;
}
実行例
% gcc -m32 -Wall hello_world_elfout.c % ./a.out > elf % wc -c elf 131 elf % chmod +x elf % ./elf hello world!
GCCが出力した小さなバイナリからsection headerを除去したりする話
Binary Hacks に、「インラインアセンブラをちょっとだけ使って、gccに小さなhello worldバイナリを出力させる」というネタを書きました(Hack #25: glibcを使わないでHello Worldを書く)。その補足という訳でもないのですが、先日shinh先生と焼肉など食べておりましたところ、セクションヘッダを削ってサイズ縮小する話は紹介してもよかったんじゃまいかとツッコミをいただきましたので、（あまり親切な記述ではないですが）書いてみます。「gccにコードを吐かせる」「アセンブリ言語部分にあまり凝らない」という条件で、132バイトまで削ります(書籍だと488バイト)。
えー、hello world なソースコード(末尾に添付)を次のようにコンパイルして*1、
% gcc -m32 -Os -fno-builtin -fomit-frame-pointer -fno-ident -c hello_world.c % ld -m elf_i386 --entry=hello -o hello hello_world.o
strip -s hello して、次のような状態のhelloバイナリが得られたとします。手元のFC6環境だと396バイトです。
% readelf -S hello There are 4 section headers, starting at offset 0xec: Section Headers: [Nr] Name Type Addr Off Size ES Flg Lk Inf Al [ 0] NULL 00000000 000000 000000 00 0 0 0 [ 1] .text PROGBITS 08048074 000074 000051 00 AX 0 0 4 [ 2] .rodata PROGBITS 080480c5 0000c5 00000e 01 AMS 0 0 1 [ 3] .shstrtab STRTAB 00000000 0000d3 000019 00 0 0 1 Key to Flags: W (write), A (alloc), X (execute), M (merge), S (strings) I (info), L (link order), G (group), x (unknown) O (extra OS processing required) o (OS specific), p (processor specific) % wc -c hello 396 hello
このとき、このhelloの中身は次の4つがこの順に並んでます。
- ELFヘッダ
- プログラムヘッダ
- ほんたい (システムコールを呼ぶコードとか、出力する文字列とか)
- セクションヘッダ
ELF的には、ELFヘッダ以外はどこに置いても良いのですが、普通、というか私のldはこの順序で吐きます。で、セクションヘッダはプログラムを実行するだけなら削ってしまっても差し支えないので、削ってさらに小さなバイナリをゲットという作戦です。セクションヘッダの開始位置はELFヘッダに書いてあります。readelfの出力によると、236バイト目からだそうです。
% readelf -h hello | grep -i section Start of section headers: 236 (bytes into file) Size of section headers: 40 (bytes) Number of section headers: 4 Section header string table index: 3
ddで236バイト目以降を捨てたバイナリを得ます*2。
% dd if=hello of=hello_nosectionhdr count=235 bs=1 % chmod +x ./hello_nosectionhdr % ./hello_nosectionhdr Hello World! % wc -c hello_nosectionhdr 235 hello_nosectionhdr
これで、235バイトになりました。ELFヘッダに書いてあるセクションヘッダの位置/サイズと、実際のバイナリのそれが異なる状態になりますが、少なくともkernel 2.6.18現在ではちゃんと実行できます。readelfはエラーが出るようになり、objdumpでの逆アセンブル等は簡単にはできなくなり*3、elfutilsでの解析はほぼできなくなりますが、実行はできるという状態です。めでたし。helloをhexdumpしてみると、
% objdump -s -b binary hello_nosectionhdr hello_nosectionhdr: file format binary Contents of section .data: 0000 7f454c46 01010100 00000000 00000000 .ELF............ 0010 02000300 01000000 9e800408 34000000 ............4... 0020 ec000000 00000000 34002000 02002800 ........4. ...(. 0030 04000300 01000000 00000000 00800408 ................ 0040 00800408 d3000000 d3000000 05000000 ................ 0050 00100000 51e57464 00000000 00000000 ....Q.td........ 0060 00000000 00000000 00000000 06000000 ................ 0070 04000000 8b542404 b8010000 005389d3 .....T$......S.. 0080 cd805bc3 53b80400 00008b5c 24088b4c ..[.S......\$..L 0090 240c8b54 24105389 dbcd805b 5bc3b9c5 $..T$.S....[[... 00a0 800408b8 04000000 ba0d0000 0053bb01 .............S.. 00b0 000000cd 805bb801 00000053 bb000000 .....[.....S.... 00c0 00cd805b c348656c 6c6f2057 6f726c64 ...[.Hello World 00d0 210a0000 2e736873 74727461 62002e74 !....shstrtab..t 00e0 65787400 2e726f64 617461 ext..rodata
こんな感じです。なおこのセクションヘッダをdelする作業、sstripというコマンドだと自動でやってくれたような気もします(未確認)。
以下余談(GOLF)です。ここで、「0xd2バイト目以降もいらないんじゃないか」と思ったあなたは正しくて、ここは最初のreadelf -Sでいうところの.shstrtabセクションで、いまは不要です。手元の strip -R だとshstrtabは消せないっぽいんですよね。ここもddで落としてしまいましょう。これで210バイトになります。
% dd if=hello of=hello_nosectionhdr count=$((0xd2)) bs=1
あと今回だと、
- インラインアセンブラの %%ebxのpush/pop は消しちゃってもいい
- write関数とexit関数をstatic inlineにして、ld に -x (delete all local symbols) を渡してwrite/exit関数の実体を捨てる
- strip -gR .note.GNU-stack hello_world.o しておいて、ld がPT_GNU_STACKなプログラムヘッダを出力しないようにする (プログラムヘッダがPT_LOADひとつだけになる)。
とか色々hackできないこともないです。手元では上の3つと、shstrtab以降を捨てる技の併用で132バイトです。一応、書籍に載せた方法のバイナリの半分以下のサイズです。ヘッダが52+32=84バイトで、文字列が13バイト、コードが35バイトですね。コードが冗長な事を除いてはELF的に特に無駄な部分がないので、「アセンブリ言語部分に凝らない」「gccにELFバイナリを出力させる」という条件下では、このあたりが限界ですかねー？
これ以上こだわるなら、gccに頼らずにELFを直接出力するCのプログラムを書き、shinhさんらが遊んでいる(一部で話題の) "ELF Golf" をやることになります。アセンブリ言語部分を頑張って短くしたり、ヘッダの中にコードを埋めたり、２種類のヘッダをオーバーラップさせたりするアレです。まぁELF Golf自体は難解なのですが、ELFを吐くCのコードを書くだけならとっても簡単で楽しかったりしますので、その話を次に書きます（予定書いた）。
一応、今回使用したソースコードも掲載しておきます。カーネルからコードを借りています。x86用です。
#include <asm/unistd.h>
#define __syscall_return(type, res) (type)(res)
#define _syscall1(type,name,type1,arg1) \
type name(type1 arg1) \
{ \
long __res; \
__asm__ volatile ("push %%ebx ; movl %2,%%ebx ; int $0x80 ; pop %%ebx" \
: "=a" (__res) \
: "0" (__NR_##name),"ri" ((long)(arg1)) : "memory"); \
__syscall_return(type,__res); \
}
#define _syscall3(type,name,type1,arg1,type2,arg2,type3,arg3) \
type name(type1 arg1,type2 arg2,type3 arg3) \
{ \
long __res; \
__asm__ volatile ("push %%ebx ; movl %2,%%ebx ; int $0x80 ; pop %%ebx" \
: "=a" (__res) \
: "0" (__NR_##name),"ri" ((long)(arg1)),"c" ((long)(arg2)), \
"d" ((long)(arg3)) : "memory"); \
__syscall_return(type,__res); \
}
inline _syscall1(int, exit, int, status);
inline _syscall3(int, write, int, fd, const void*, buf, unsigned long, count);
void hello() {
write(1, "Hello World!\n", 13);
exit(0);
}132バイトの奴。
% wc -c hello_nosectionhdr 132 hello_nosectionhdr % ./hello_nosectionhdr hello world! % objdump -s -b binary hello_nosectionhdr hello_nosectionhdr: file format binary Contents of section .data: 0000 7f454c46 01010100 00000000 00000000 .ELF............ 0010 02000300 01000000 54800408 34000000 ........T...4... 0020 a0000000 00000000 34002000 01002800 ........4. ...(. 0030 04000300 01000000 00000000 00800408 ................ 0040 00800408 85000000 85000000 05000000 ................ 0050 00100000 b9778004 08b80400 0000ba0d .....w.......... 0060 000000bb 01000000 cd80b801 000000bb ................ 0070 00000000 cd80c368 656c6c6f 20776f72 .......hello wor 0080 6c64210a ld!. % readelf -hl hello_nosectionhdr readelf: Error: Unable to read in 0x28 bytes of section headers ELF Header: Magic: 7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00 Class: ELF32 Data: 2's complement, little endian Version: 1 (current) OS/ABI: UNIX - System V ABI Version: 0 Type: EXEC (Executable file) Machine: Intel 80386 Version: 0x1 Entry point address: 0x8048054 Start of program headers: 52 (bytes into file) Start of section headers: 160 (bytes into file) Flags: 0x0 Size of this header: 52 (bytes) Size of program headers: 32 (bytes) Number of program headers: 1 Size of section headers: 40 (bytes) Number of section headers: 4 Section header string table index: 3 readelf: Error: Unable to read in 0xa0 bytes of section headers Program Headers: Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align LOAD 0x000000 0x08048000 0x08048000 0x00085 0x00085 R E 0x1000
(追記) Plan9での例がこちらに。
