Adaと64bit呼び出し規約とlldiv

Ada gcc

lldivを呼ぶ関数を書いてたらちょっと驚きました。
こういうの。

procedure call_lldiv (x, y : long_long_integer; q, r : out long_long_integer) is
   type lldiv_t is record
      q, r : long_long_integer;
   end record;
   pragma Convention (C, lldiv_t);
   function lldiv (x, y : long_long_integer) return lldiv_t;
   pragma Import (C, lldiv, "lldiv");
   result : lldiv_t;
begin
   result := lldiv (x, y);
   q := result.q;
   r := result.r;
end call_lldiv;

最適化してコンパイルする。

gcc -S -O3 call_lldiv.adb

すると……

	.text
	.align 4,0x90
	.globl __ada_call_lldiv
__ada_call_lldiv:
LFB1:
	subq	$40, %rsp
LCFI0:
	call	_lldiv
	addq	$40, %rsp
LCFI1:
	ret

えっ。

GNATフロントエンドのスカラー値のoutパラメータの扱いは参照渡しではなくて所謂multi-value returnで、%rax、%rdxで返すっぽいです。で、64ビット呼び出し規約では小さな構造体もレジスタ返しってことになっているらしくて、lldivも値を%rax、%rdxで返すっぽくて、引数並びも一致してるから何もせずにcallして何もせずにretすることになったようです。

ですもんで-m32ですとこうなる。

	.text
	.align 4,0x90
	.globl __ada_call_lldiv
__ada_call_lldiv:
LFB1:
	pushl	%esi
LCFI0:
	subl	$56, %esp
LCFI1:
	movl	76(%esp), %eax
	leal	32(%esp), %ecx
	movl	80(%esp), %edx
	movl	%ecx, (%esp)
	movl	64(%esp), %esi
	movl	%eax, 12(%esp)
	movl	68(%esp), %eax
	movl	%edx, 16(%esp)
	movl	72(%esp), %edx
	movl	%eax, 4(%esp)
	movl	%edx, 8(%esp)
	call	_lldiv
LCFI2:
	subl	$4, %esp
LCFI3:
	movl	32(%esp), %eax
	movl	36(%esp), %edx
	movl	%eax, (%esi)
	movl	40(%esp), %eax
	movl	%edx, 4(%esi)
	movl	44(%esp), %edx
	movl	%eax, 8(%esi)
	movl	%edx, 12(%esi)
	movl	%esi, %eax
	addl	$56, %esp
LCFI4:
	popl	%esi
LCFI5:
	ret	$4

で、これを見てしまうと、どうせならスタックを$40ほど取って戻してしてるのも最適化して欲しくて、そうすれば-foptimize-sibling-callsも働いてjmp一個にできるはずなんですけれど、このスタックが強敵で色々オプションを試しても消えてくれません。なんでー？

HFS+のファイル名を比較する厳密な方法

Mac

Macユーザーなら、HFS+の勝手なファイル名の「正規化」には悩まされてますよね！

まず浅い理解として、HFS+はファイル名をNFDに正規化する。次に、HFS+は互換漢字を統合漢字にはぜず、それ以外をNFDに正規化する。まあそれで合ってるんですけれど、実際にはそんな簡単な話ではありません。
この記事では、カーネルが行なっているファイル名の変換の再現に挑戦します。

ソースコード

こういうものは一次ソースを見るのが一番です。外から挙動を推測したって見落としは出ます。Darwinのカーネルはオープンソースになってますので以下で見ることができます。
ファイルアクセスは、Darwinカーネルの中のDarwinのカーネルであるXNUというモジュールが担当してます。

http://www.opensource.apple.com/source/xnu/

うろうろ

まず、ファイルアクセスAPIからやって来るHFS+のドライバの入り口はどこでしょうか？
hfs_vnops.cにある関数テーブルがそれっぽいですが、このファイルではファイル名の処理はしていません。ところどころで、cat_なんとかいう関数を呼んでますので、多分これでしょう。
というわけでhfs_catalog.cに進みます。色々やってますが、ファイル名の処理としてはbuildkeyが怪しい。utf8_decodestrという「いかにもそれっぽい」関数を呼んでいます。

utf8_decodestr(..., ':', UTF_ESCAPE_ILLEGAL | UTF_DECOMPOSED);

':'は、実は':'と'/'は逆に記録されているというヤツでしょう。Finderではファイル名に'/'を使えますが、POSIX APIからは':'としてアクセスできます。
プログラム中では(Cocoaのよくわからないレイヤーを使わない限り)POSIX APIからは'/'は区切り、':'はファイル名に使える文字で一貫してますから、これは豆知識として頭の片隅に押しやってしまいましょう。

もうひとつ重要なのが、CompareCatalogKeys(から呼ばれているFastRelString)とCompareExtendedCatalogKeys(から呼ばれているFastUnicodeCompare)です。
buildkeyでUTF-8で渡されたファイル名を内部名にデコードして、で、このデコードされた名前がそのままファイル名になるのですが、HFS+には正規化(モドキ)の他にもうひとつ、大文字/小文字を無視するという特徴があります。
こっちの方は大文字/小文字の区別を行うフォーマットもある(ディスクユーティリティでフォーマットできる)のですが、使われているのは大文字/小文字を無視するフォーマットのほうです。

で、まあ見ていくと、FastRelStringは、所謂Pascal文字列のcase insensitive比較で、文字コードはmac romanっぽいです。互換用？
FastUnicodeCompareがUnicodeのcase insensitive比較です。

これで、再現するべきことはわかりました。
utf8_decodestrはファイル名のデコードを行う関数です。この関数の動作を追うことで、openやなんかのシステムコールに渡したファイル名が実際にどういう名前でディスク上に記録されるかがわかります。
FastUnicodeCompareはファイル名の比較を行う関数です。この関数の動作を追うことで、大文字/小文字が同一視される条件がわかります。

Unicodeテーブル

先にテーブルについて。
Unicodeというのは文字の並びに規則性のないコード体系で、扱うためにはテーブルが必要です。普通にUnicodeの処理を行うだけなら、http://www.unicode.org/からUCDを持ってくれば、いや、その辺のUnicodeのライブラリを使ってしまえばいいのですが、事はそう簡単ではありません。
ソースコードのCopyrightに書かれた年を見ればわかりますが、HFS+が実装されたのは2000年前後です。テーブルのバージョンを合わせないと挙動が変わってしまいます。

というわけで、XNUのソースコードに含まれるUnicodeテーブルをそのまま使いましょう。一番確実です。

正規化用 http://www.opensource.apple.com/source/xnu/xnu-1504.15.3/bsd/vfs/vfs_utfconvdata.h
比較用 http://www.opensource.apple.com/source/xnu/xnu-1504.15.3/bsd/hfs/hfscommon/Unicode/UCStringCompareData.h

探し回っているうちに圧縮されたバージョンの比較用テーブルも見つけました。内容は同じですが展開が必要です。

比較用(圧縮版) http://www.opensource.apple.com/source/boot/boot-132/i386/libsaio/hfs_CaseTables.h

utf8_decodestr

http://www.opensource.apple.com/source/xnu/xnu-1504.15.3/bsd/vfs/vfs_utfconv.c

「古いUnicodeテーブル」を用いて、UTF-8をUTF-16に直しつつ、以下の展開を行なっています。

  • UTF-8のillega sequenceは、%XX (XXは16進2桁でA-Fは大文字) としてエスケープ。これはターミナルからでも簡単に試せて楽しいです。
  • decompose。decompose結果も再帰的にdecomposeしてます。互換漢字は最初からテーブルに入ってません。一応比べてみましたが、互換漢字以外は1B06〜1B43も入ってないです。これは単にテーブルが古いためと思われます。
  • 連続するcombining charactersのソート。decomposeの結果出現したものと、最初から文字列中に存在したものを合わせて、combining classで安定ソートを行なってます。これはUnicodeの仕様通りですが、やはりテーブルが古いためcombining characterとして収録されたコードがだいぶ少なく(322しかない。最新のは倍あります)、最新のテーブルを使ってしまうと食い違いが大きくなりそうです。

FastUnicodeCompare

http://www.opensource.apple.com/source/xnu/xnu-1504.15.3/bsd/hfs/hfscommon/Unicode/UnicodeWrappers.c

古いテーブルを用いて、UCS-2(16ビット)の範囲内で、simple case mappings(コードポイント数は変化しない)で小文字にしながらの比較を行なっています。
簡単。(小文字じゃなくてcase foldingすべきでは……なんて言ってもしょうがない)

で、何を使ってどれを再実装すれば？

CoreFoundationにはCFStringGetFileSystemRepresentationという関数があって、utf8_decodestr同様の処理を行なってくれます。

でも大抵それだけでは済まなくて、CFStringGetFileSystemRepresentationの逆変換が欲しくなると思います。主に、NFDモドキにされてしまったファイル名をNFCに戻して、他のOSと相互運用できるようにする、等の用途が考えられます。でも、CoreFoundationはそういった関数は用意してくれていません。
かといって、単にNFC変換を行なってしまうと、互換漢字は潰れるわ、合成除外文字は分解されたままだわで、厳密な逆変換にはなりません。

そこでiconvです。iconvはHFS+のファイル名の変換を"utf8-mac"としてサポートしてます。(Macでもこんな妙な変換はファイル名だけにしか使われてませんので、"utf8-mac"は誤解を生むという議論は既出)
iconvなら、iconv -f utf8-mac -t utf-8 で逆変換もOKという、iconv素晴らしいよiconv。
Frameworkを使いたくない、POSIXの範囲だけでやりたい、等の理由でCoreFoundationをリンクしたくない場合も、iconvなら許せるでしょう、たぶん。

iconvも許せなければ、再実装する羽目になります。

FastUnicodeCompareのほうは、/usr/lib以下の.dylibを調べて回ったのですが、どうも該当するデータは無さそうですので、比較まで行いたければ再実装してやる必要があります。

あとまあ、Macだからって無条件にこういった処理を行うのではなくて、一応statfsぐらいはして、HFS+でなければ素通ししてやるぐらいの余裕は欲しいです。Macでも他のフォーマットを使えるのです。
NTFSを見つけた時のためにLCMapStringを再現する方法は……どなたかお願いします。

立ち返って

こういったファイルシステムの知識を必要とする実装は、厳密な処理をするためには必要ですが、普通はもっと簡単な方法があります。
それは、「ファイルシステムはファイル名を変形することがある(HFS+に限らないしUnicodeに限らない)」という前提を受け入れることと、「ファイル名が変形された場合でも最初の名前でアクセスし続けることはできる」のを利用することです。
例えばファイルの上書き確認であれば、ファイルを列挙してファイル名を確認するみたいな処理はダメで、試しにstatでもしてみてアクセスできるならファイルは存在しているとみなすみたいな処理が良いってことです。
これならFAT16なフロッピーディスクを急に使いたくなって、ファイル名が8.3に切り詰められても大丈夫でしょう、やったね！

でも、それだけでは済まない場合も出てくるとは思いますので、そういうときはぜひ、厳密な比較を実装してください。NFD変換なんかで済まさないで。

Arch LinuxをVirtualBoxにインストールしてみた

Linux

今年は何もしませんでしたね……我ながら酷い。4月に、headmasterでLinuxのstring.hが変換できないというissueをいただいて、12月も末になってようやく修正した、そんな年です。

こうも時間がかかったのは、VirtualBoxを使うようになったのが結構最近だからで、私の日常用途にはMacとWindows、あと借りているさくらのレンタルサーバがFreeBSDなのでそれ、と、OSはそれぐらいしか使ってないのです。所謂ガラケーなのでAndroidとも無縁です。Linuxなんて必要性も空いているPCもない。で、個人的な事なんですが10年前に作った自作PCをPC3Rに有償で回収してもらいました。結構面倒くさかった。リサイクルマークの付いているPCを買いましょう。で、Windows PCが減りましたし、Vista以降のWindowsに付いて行く気は全くないですし、最近はSecureBoot*1なんて物騒な話題もありますし、XP環境を保存する目的でVirtualBoxを使い出しました。クリーンインストール時のスナップショットを残しておけば変なものを入れても巻き戻せます。ゲストでスワップするかホストでスワップするかの違いしか無いのでページファイルを消してしまえます。sdeleteを使えばVDIを圧縮できます。XPというのはなぜこんなに仮想マシンと相性がいいのでしょう。で、どうせならということでFreeBSDもLinuxも仮想マシン環境を作りました。どうでもいい経緯終わり。日本語で言い訳しても伝わるわけがありません。

headmasterはヘッダーファイル変換ツールです。これを作るのが目的であり、Linuxのヘッダーファイルやライブラリにもだらだら文句を書きたいのが本音です。今これをLinuxから読んでおられる方はちょっとstdio.hを開いてみてください。__REDIRECTなんて書かれてますが展開してみると同じ関数が2回宣言されていたりします。しかも2回目は__asm__("...")付きです。この__asm__はインラインアセンブラではなくて、オブジェクトファイル上の外部名を指定するためのものです。つまり一個目のfscanfは_fscanfを、二個目のfscanfは___isoc99_fscanfを呼ぶための宣言であり、全くの別物です。こんなのを警告もなしに通すgccもどうかしてます。一個目と二個目の間に呼び出しを書いて、それがインライン展開されたりしたら呼ばれるのはどっちになるんでしょう？まあそんなのも今はどうでもいいです。

Arch LinuxをVirtualBoxにインストールしてみた…私がメモとしてここに残しておきたいのはこれなんです。この手の記事を書くのは久しぶりなのでテンションがおかしいのは勘弁してくださいな。

といっても、手順そのものは本家の解説や、とてもありがたい先人の記録を参考に進めていけば、手間こそかかれ特に難しいところはありませんでした。でもこの手間が問題で、そう、Arch Linuxというのはインストーラが付いてない素敵ディストリビューションなのです。*2 インストールイメージから起動するとLive CDみたいにArch Linuxが普通に立ち上がります。そこからコマンドをぽちぽち打ってインストーラがやる手順を手動で再現しないといけません。なんでわざわざそんなもんをと思われるかもしれませんが、X無し、可能な限りの最小構成でインストールできるLinuxを探したんですよ、configureを走らせたりヘッダーファイルを引っこ抜いたりすることだけが目的ですので。

ようし、前置きは終わった。一気にいくぜ！

*1:名前に反してWindows以外が起動できなくなるだけのゴミらしいです。最近はどこも囲い込みに必死で困る。

*2:昔はインストーラがあったが消えたらしい？

続きを読む

GNAT開発環境について〜gcc付属ツール

Ada

2012年12月時点でのgccまたはGNAT GPLをインストールした際に付属する「公式」ツール群の紹介を行う。
多岐に渡るので、一つ一つの詳しい説明は行わない。
各ツールの細かい情報はそれぞれのドキュメントを参照して欲しい。

もし知らないツール名があったらちょっと読んでみて欲しい。
もしかしたらあなたの問題を解決するツールがあるかもしれないから。

★は重要度。五点満点。

なおこの記事は某所のパクリです。あとAda Advent Calendarとは何の関係もありません。

続きを読む

OCamlの関数をCのスレッドで呼ぶ方法がわかった

OCaml

困ってる人を見かけたのでトラックバック。
ちょうど最近、GLCamlのSDL_audioを使えるようにしたところです。使うアテもなかったのですが、ちょうど良かったです。

https://github.com/ytomino/glcaml/blob/master/lib/sdl_audio_stub.c

caml_c_thread_registerでスレッド登録。同じスレッドから何度呼んでも大丈夫です。(スレッドプールから呼ばれるコールバックの場合、解除できるタイミングがありませんが、まあSDL_audioならスレッド終了時=プログラム終了時でしょうからたぶん大丈夫？)

続けてcaml_leave_blocking_sectionを呼んでOCamlの実行権を獲得します。blocking sectionというのはOCamlの外で待ちが入る処理のことで、その間OCamlは他のスレッドを実行しています。blocking sectionからleaveする=OCaml側の処理に入る、です。その状態でOCamlの関数を呼べばいいです。最後にenter〜で他のスレッドにOCamlの実行権を明け渡します。

当たり前ですが、メインスレッドからもどこかでcaml_enter_blocking_section/caml_leave_blocking_sectionしないと、他のスレッドは延々待ちつづけることになります。SDLならSDL_WaitEventによるイベント待ちや画面描画時のVSYNC待ちをblocking sectionと見なすのが妥当でしょう。

加えて、初期化のためにどっかでThreadモジュールの関数(なんでもいい)を呼ばないといけません。私のバージョンではsdl_audio.mlの最後でちょろっと呼んでます。(C側でcaml_c_thread_initを呼ぶのでもいいような気がするのですが、ダメでした。OCaml側で追加の初期化が何かなされてるのでしょう、たぶん。知らんです。ソース読んでないです)

っていうかむしろhttps://github.com/einars/glcamlを使ってforkしていろいろ直してください。(宣伝)