Author Archives: Kaede Fujisaki

統計学の力を借りて、文字化け退散！

Posted on by

現在ではだいぶ少なくなりましたが、ネットサーフィン（死語）をしていると、たまに文字化け（これも最近は死語？）に出会いますよね。

20111022_01.jpg

うう、なんて書いてあるのかさっぱりわからない。。。†1 ChromeだとエンコードをShift_JISと思い込んでますが、本当はEUC-JPでした。

20111022_02.jpg

今回は、この文字化けを回避する、”文字コードの自動推定”をやってみました。

最近「プログラマのための文字コード技術入門」という本を読んでいます。この中では日本語圏ではおなじみの、Shift_JISとISO-2022-JP(俗に言うJIS)と、EUC-JP、そして最近圧倒的なシェアを誇るUTF-8（このBlogもUTF-8です）のそれぞれの符号化方式について、変換プログラムを書くのに十分な位に詳しく説明されています。

プログラマのための文字コード技術入門 (WEB+DB PRESS plus) (WEB+DB PRESS plusシリーズ)
プログラマのための文字コード技術入門 (WEB+DB PRESS plus) (WEB+DB PRESS plusシリーズ)

posted with amazlet at 11.11.06
矢野 啓介
技術評論社
売り上げランキング: 29817
Amazon.co.jp で詳細を見る

どの方式も、ASCIIを基本として、ASCIIでは使われていないデータ部分を使って日本語（やその他の言語）を表現しています。その使い方はそれぞれの符号化方式で異なるため、「このデータの並びはShift_JISでしか使われないはず…だから、このテキストはShift_JISだろう」みたいな感じで、文字コードの推定ができます。

たとえば、昔のYahoo!JapanはEUC-JPで書かれていた（今はUTF-８）のですが、そのとき、ページの最初のほうにこんな感じのコメントが入っていました。

<!-- 京 -->

趣味によっては「美乳」とか使うみたいです（笑

この「京」や「美乳」をEUC-JPでエンコードしたバイト列、「0xB5 0xFE」や「0xC8 0xFE 0xC6 0xFD」は、Shift_JISにもISO-2022-JPにも、さらにUTF-8にも決して現れないデータの並びです。だから、ブラウザはこのデータの並びを見たときに、「あっ、これはEUC-JPなんだな。」ってわかる（から文字化けが発生しない）、という訳です。

でも、限界もある

このようにすれば、確かに文字化けは回避できます。でも、みんながみんなこういった気の利いた（？）コメントを入れてくれる訳ではありません（そもそもHTMLには、meta要素での文字コード指定があって、むしろ上の方法よりもこちらで明記しなければならないのですが…）。そんな時、文字化けしてしまうことがあります。

たとえば、以下のバイト列†2

完璧な牛丼

をEUC-JPでエンコードしたバイト列

B4 B0 E0 FA A4 CA B5 ED D0 A7

は、そのままShift_JISと思って読み込むと

ｴｰ瓏､ﾊｵ槢ｧ

として解釈することができます。どのバイト列もShift_JISとしても有効なバイト列だからです。

よって、このバイト列がEUC-JPの「完璧な牛丼」なのか、Shift_JISの「ｴｰ瓏､ﾊｵ槢ｧ」なのか、論理的に確定させることは絶対にできない、ということになります。これが限界です。

（なおInternetExplorerはこの文字列をShift_JIS（文字化け）、ChromeはEUC-JP（正しい）として認識しました）

最初の例も、meta要素でのエンコード指定も、気の利いたコメントも無いため、Chrome14はShift_JISと勘違いしてしまった…という典型的な例です。仕方ないねー。

統計的手法を使おう！

確かに、先ほどのバイト列は、Shift_JISでもEUC-JPでも有効なバイト列でした。

でも、ですよ？

「ｴｰ瓏､ﾊｵ槢ｧ」ってまず無いだろうな～って、感覚的にはわかりますよね。たぶん「完璧な牛丼」だろう…と。こっちも意味不明ですけど…＾＾；

この「”ｴｰ瓏､ﾊｵ槢ｧ”よりは”完璧な牛丼”の方が『ありそう』だよね」って感じをコンピュータに自動で判断させれば、もっと正確に文字コードが判別できるはずです。

…そんなときは…そう！統計学の力を借りましょう！†3

バイトとバイトの”つながり”を手がかりにする

じゃあ、統計的手法を使って、「ありそう」かどうかを、どうやって判定すればいいのでしょう？

日本語の文字コードは、どのコードも基本的に文字列を複数のバイトを使って（例：UTF-8だと大体３バイト、他のエンコードでは２バイト）表しています。この関係性を何とか使えないでしょうか？

そこで今回は、バイトとバイトの”つながり”を手がかりにすることを考えてみました。

つまり、

  • “0x00″のつぎに”0x01″が出てくるのは＊回
  • “0x00″のつぎに”0x02″が出てくるのは＊回
  • （中略）
  • “0x01″のつぎに”0x00″が出てくるのは＊回
  • (中略)
  • “0xFF”のつぎに”0xFF”が出てくるのは＊回

といったデータを全部の組み合わせ（256*256 = 65536通り）について調べ、その特徴を比べます。

画像にマッピング

そのデータを使って実際に判断させる前に、とりあえず使えそうかどうか、画像で可視化することで、調べてみましょう。今回は、Wikipediaの全文データを用いて、画像を作って見ました。

X軸が１バイト目、Y軸が２バイト目です。出現頻度で色分けしてますが、適当です。

「Shift_JIS」

20111022_sjis.png

「ISO-2022-JP（俗に言うJIS）」

20111022_jis.png

「EUC-JP」

20111022_euc.png

「UTF-8」

20111022_utf8.png

どうです？全然違いますよね！　となると、これと、エンコードの分からない文章を比較すれば、その文章がどのエンコードなのか、分かるんじゃないでしょうか？

どうやって比較するの？　「コサイン類似度」

さて…人間は画像を見て一発で判断できますけれど、コンピュータはそうではありません。これをどうやってコンピュータに比較させれば良いのでしょう…うーん…画像認識…？

今回用いたのは、「コサイン類似度」と言われる方法です。順を追って説明していきます。

バイトのつながりのデータを、”ベクトル”に見立てる

この画像は二次元でマッピングされていますが、若干扱いづらいので、一列につなげて、65536通りの要素のベクトルとして扱うことにしました。プログラミングの観点から言うと、二次元配列から一次元配列に変えただけということになります。

(0, 0, ........, 1, 3, ......., 0) ←65536次元（＝256x256）のベクトル

さて、ベクトルです。矢印です。二次元美少女ばっかり追いかけてるのに、三次元だと非リアなのに、65536次元なんて不安？大丈夫、ベクトルの性質は二次元の時とま～ったく同じ！ご安心ください（要素が多いので計算が人間には無理ですけど…）。

さて、このようにしてバイトのつながりをベクトルに見立てることで、

  • 「推定したいファイルのエンコード」が、Shift_JIS、JIS、EUC-JP、UTF-8の中のどれなのかを調べる問題

が、

  • 「推定したいファイルの”ベクトル”」と、Shift_JIS、JIS、EUC-JP、UTF-8のそれぞれの”ベクトル”を比較して、どれが一番似てるか調べる問題

に、言い換えることができました。結局、似てる矢印を探せれば良いんです。

“似ているベクトル”って、何だろう

似てるベクトル…って何でしょう？？とりあえず、図をかきましょうか。二次元と全く同じように扱えるって言いましたよね。だから、普通に2次元絵で大丈夫です。

矢印には、向きと長さがあります。

20111022_03.jpg

一番長さが近いベクトルを似てるってするのは、どうでしょう？ほら、人間だって身長の高低で分類したりしてますし。

20111022_04.jpg

でも。長さって、ベクトルの各要素の二乗の和の平方根で表されるんでしたね（つまり、二次元だと長さ＝√（x^2+y^2）でしたね。3次元なら√（x^2+y^2+z^2）、4次元でも、65536次元でも同じです）。

今回各要素の値は、文章内に現れたバイトの繋がりをカウントしたものでしたから、文章が長ければ（＝たくさんのデータを使っていれば）、今回のベクトルの長さも長くなる…ということになります。これでは、比較には使えなさそうです。。。

というわけで、必然的に向き、つまり間の角度を比較することになります。

え…65536次元空間での角度って、何…？

2つのベクトルの間の、角度を求めるには？

まだ焦るような時間じゃない（AA略）。何度も繰り返すように、二次元と同じです。

懐かしの高校数学のおさらいです。2つのベクトルの内積というものを、

  • 「成分だけ」を使ったもの
  • 「長さと間の角度」を使ったもの

の、二通りを使って表せるんでした。

20111022_05.jpg

上で見たとおり、「長さ」も成分から求められますから、「成分だけ」を直接使って求めた内積と比較することで、cosθがわかります。（式のとおりです）

このcosθのことを、「コサイン類似度」と呼びます。角度でもいいのですけど、やっぱり65536次元での角度ってよく分からないし、空間の話でもないので別名が付いてるんだと思います。たぶん。

cos 0° = 1、cos 180° = -1ですから、この値が大きいほど、2つのベクトルの向きは似ている、ということになります。

実験結果！

さて、以上の道具立てを使って、調べてみました。Wikipediaの全文データ、青空文庫のデータ、あと各種ウェブサイトをクロールして得たデータ（たまに違うエンコードが混じっている）†4を元にして、それらとは別にクロールしたウェブサイト†5の文字コードを判定させた結果がこちらです。

ただし、クロールしたものである以上別のエンコードやASCIIのみのデータが混入しているので、95%以上で判定できれば十分な精度だと考えています。データを集めるうまい方法が思い浮かばなかったんです。。。†6

))

20111022_06.jpg

青空文庫の素材データは、ほぼ100%の精度でエンコードを判定してくれています！

失敗していると出た結果のところも、実際に見てみると殆どは混入しているノイズで、「むしろ正しく判定している」ものが殆どでした。これChromeに積むのってどうでしょう！？

Wikipediaは…utf-8はちょっと苦手、みたいですね。

そして、実際のウェブサイトをクロールして得た素材データは…うーん。。。一番「現場を反映している」と思っていたのですが、まさかの大苦戦…。これは、どういうことなのでしょう？？

クロール素材データ使用時では、特定のウェブサイト＊だけ＊失敗してる？

この結果には表れていないのですけど、ログを見ていて気になったのが、クロールによって得た素材データを用いて推定した際、特定のウェブサイトにおいて*だけ*失敗していることが多いということです。SJISとUTF-8について、サイト別の判定率も出してみました。

（ニュースサイトが多いです。たくさん記事があって、エンコードが統一されてて…と選んでいくと、新聞社のページが残りました＾＾；）

■SJIS（クロール素材データ使用時）

20111022_07.jpg

房日新聞の判定成功率の低さがすさまじいです。

■UTF-8（クロール素材データ使用時）

20111022_08.png

エキサイトとCNETはうまくいくのですけど、他が…。

2つの文字コードが混じり合っている

気になるのは、どの文字コードも、英語を表すためのASCII（どれでも共通）と、日本語を表すための方式（それぞれ異なる）が入り交じっていることです。二つの要素が入り混じってしまっているため、これが問題になっているのかもしれません。

これだとどのような問題が起きるかというと、コサイン類似度の比較によって、日本語バイトデータの出現頻度の比較だけでなく、「ASCIIと日本語が、それぞれ文章内に含まれている割合」が比較要素に入ってしまう可能性があります。

例えば

  • SJISの素材データはASCII多め
  • EUC-JPの素材データは日本語多め

という状況で、

  • ASCIIが多めのEUC-JPの比較データ

を判定させた場合、SJISに判定されやすくなる†7…などの可能性が考えられる、ということです。†8

Wikipediaや青空文庫の素材データは、あくまで「同じテキストデータ」を、「別のエンコード」で示したデータを使っているので、ASCII/日本語の割合は、すべてのエンコードにおいて同一です。そのため、比較データの日本語/ASCIIの割合の影響は、打ち消されるのではないでしょうか…？

とりあえず、ASCIIもマッピングして可視化してみる？

とりあえず、RFCの全データを取得し、同様に画像化してみましょう。…RFCってこんなにあったんだ…（－－；

■ASCIIの出現頻度マッピング

20111022_ascii.png

左上の一カ所に固まってますね。これがASCIIの特徴です。これが、日本語でのデータと混ざってしまうことで、悪さをしてしまうようです…。

ASCIIと、素材データ、そして失敗した比較データを並べて眺めてみる

Webをクロールして得られた素材データと、特に失敗しているwww.bonichi.comのデータを並べた画像を作ってみました。

20111022_09.png

ほらほら！どの画像でも、左上には同じようなパターンが広がってますよね。どげんかせんといかん。

次回予告！

ASCIIとそれ以外の文字コードを、どのようにして混ざっている中から区別して、正しく判定することが出来るのでしょうか？

解決＆高速化編の続きはこちら！

  • †1: Chromeだとエンコード変更するの面倒なんですよね…
  • †2: 前述の本での例をそのまま使いました。。。
  • †3: 多分これは統計学の範疇だと思うんですが…どうなんでしょう＾＾；
  • †4: 以下「素材データ」と呼びます
  • †5: 以下「比較データ」と呼びます
  • †6: なお、それぞれのエンコードでの、テストに用いた比較用データの数はShift_JIS:8634、EUC-JP:10754、ISO-2022-JP:3596（そもそも使ってるサイトが少なくて…＾＾；）、UTF-8：7203　となっております。
  • †7: SJISの素材データのほうがASCIIが多めだから
  • †8: さらに補足すれば、最近のウェブサイトはCMS全盛（＝似たようなソースになりがち）なので、この英語と日本語の割合は同じウェブサイトなら近くなり、同じウェブサイトでばかり失敗するのかもしれません

冬コミは落ちました

Posted on by

　今までの、ゲーム中心の共同サークルではなくて、私個人のソフトウェアネタを中心としたサークルの予定でした、が…。

20111029_01.jpg

　ガーン！落ちてしまいました。次回にご期待ください。今まで落ちたこと無かったのに…！！ソフトウェアは倍率高いのですかね…。

■

　ネットの資料だけで作るファミコンエミュレータ本を予定していました。委託とかができそうならまたお知らせします。駒場祭のコミックアカデミーはがんばってみますが、流石に間に合わないと思います…。

gccでのstatic constなクラス変数の謎挙動

Posted on by

　今日はひたすらアセンブラを追いかけるだけのお話です。ごめんね。

■

　C++では定数の定義を、defineでなく、static constな変数で行うことが推奨されてるらしいです。

// これはC++では(・A・)ｲｸﾅｲ!!
#define VAL (1)
//こっち推奨
const int VAL = 1;

　基本的には、これで問題ないのですが、リンク先によると、この定数がクラス変数の場合、定義と実体の二つに分けないといけないそうです。

//ヘッダファイル側（宣言）
class Test
{
private:
	
protected:
	
public:
	static const int VAL=01234;
};
//ソースファイル側（実体）
//gccでは宣言（ヘッダ）に値を書いても良いけど、VC++等の古いコンパイラだと実体に書かないといけない。
//そのためにenumハックが存在する（上記のリンク先参照）
const int Test:VAL;

　ほえー、なるほど。

■

　が、しかし。実際には、gccのときは、実体を書かなくても割と大丈夫みたいです。Ubuntu11.04のx86-64のgccで実験してみました（Win32のMingwでも、機械語は違いますが同じ結果でした）。

　以下のソースはgithubからもDLできるよ☆彡　あ、ZIPももちろんあるよ！！

■共通のヘッダファイルはこちら。

(Test.h)

#ifndef TEST_H
#define TEST_H

class Test
{
private:
	
protected:
	
public:
	static const int VAL1=1234;
	static const int VAL2=4321;
};

#endif

　特に意味はないです。このTestというクラスの定数を使って、いろいろテストしてみましょう。

　以下test*-*とありますが、これをmakeのビルドターゲットにすると自動でコンパイルとかしてくれます。

make test*-*

■（test1-1）実体を定義しないまま、std::coutに入れてみる。

(Test1-1.cc)

#include "./Test.h"
#include <iostream>

int main(int argc, char** argv)
{
	std::cout << "VAL: " << std::hex << Test::VAL1 << std::endl;
	
	return 0;
}

　ヘッダ上のTest::VAL1やTest::VAL2の実体を一切定義していないことに注意していください。

　これをコンパイルして実行すると…

% g++ -o Test1-1.out Test1-1.cc
% ./Test1-1.out 
VAL: 1234

　どうなってるの！？と思って、アセンブラを出力させてみると…

% g++ -S -masm=intel Test1.cc ←こうすると見慣れたINTEL形式で出力してくれます
% cat Test1.s

main:
.LFB963:
	.cfi_startproc
	push	rbp
	.cfi_def_cfa_offset 16
	mov	rbp, rsp
	.cfi_offset 6, -16
	.cfi_def_cfa_register 6
	sub	rsp, 16
	mov	DWORD PTR [rbp-4], edi
	mov	QWORD PTR [rbp-16], rsi
	mov	esi, OFFSET FLAT:.LC0
	mov	edi, OFFSET FLAT:_ZSt4cout
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
;---------------------------
	mov	esi, 1234
;---------------------------
	mov	rdi, rax
	call	_ZNSolsEi
	mov	esi, OFFSET FLAT:_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_
	mov	rdi, rax
	call	_ZNSolsEPFRSoS_E
	mov	eax, 0
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc

　線で囲ったところを見てもらえばわかるとおり、インライン展開されています。ちなみに、1234という数値はこの場所以外一切定義されません。

■（test1-2）じゃ、実体を定義したらどうなるの？

　定義を書き加えて

(Test1-2.cc)

//ヘッダファイルとメイン関数の間に追加。
const int Test::VAL1;

　としてアセンブラを出力してみると…。

;実体も定義される
_ZN4Test4VAL1E:
	.long	1234

;（略）

main:
.LFB963:
	.cfi_startproc
	push	rbp
	.cfi_def_cfa_offset 16
	mov	rbp, rsp
	.cfi_offset 6, -16
	.cfi_def_cfa_register 6
	sub	rsp, 16
	mov	DWORD PTR [rbp-4], edi
	mov	QWORD PTR [rbp-16], rsi
	mov	esi, OFFSET FLAT:.LC0
	mov	edi, OFFSET FLAT:_ZSt4cout
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
;---------------------------
	mov	esi, 1234
;---------------------------
	mov	rdi, rax
	call	_ZNSolsEi
	mov	esi, OFFSET FLAT:_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_
	mov	rdi, rax
	call	_ZNSolsEPFRSoS_E
	mov	eax, 0
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc

　Test::VALの値が埋め込みになるのは同じでしたが、それとは独立した実体も定義されました。

　一切最適化オプションをつけなくても、それなりに最適化してくれるみたいです。

■（test1-3）ポインタを通す等して、実体が必要な状況をつくってみる

　ポインタを通す場合、アセンブラに直接引数を書くことはできません。メモリ上に一旦置かなければなりません。

(Test1-3.cc)

#include "./Test.h"
#include <iostream>

void outVal(const int* val)
{
	std::cout << "VAL: " << *val << std::endl;
}

int main(int argc, char** argv)
{
	outVal(&Test::VAL1);
	
	return 0;
}

　今度からは面倒なのでビルドターゲットでコンパイルします。†1

% make test1-3
g++ -S -masm=intel Test1-3.cc -o Test1-3.s
g++ -o Test1-3.out Test1-3.cc
/tmp/ccIrdzjI.o: In function `main':
Test1-3.cc:(.text+0x50): undefined reference to `Test::VAL1'
collect2: ld returned 1 exit status
make: *** [test1-3] エラー 1

　案の定実行は失敗ですね。アセンブラコードを見てみると？

;実体は定義されないけど...

;（略）

main:
.LFB964:
	.cfi_startproc
	push	rbp
	.cfi_def_cfa_offset 16
	mov	rbp, rsp
	.cfi_offset 6, -16
	.cfi_def_cfa_register 6
	sub	rsp, 16
	mov	DWORD PTR [rbp-4], edi
	mov	QWORD PTR [rbp-16], rsi
;---------------------------
	mov	edi, OFFSET FLAT:_ZN4Test4VAL1E ;使おうとする
;---------------------------
	call	_Z6outValPKi
	mov	eax, 0
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc

　予想通りですね。

■（test1-4）でも、最適化を掛けると…。

　でもしかし。同じソースのまま、-O3とかを付けて最適化を掛けると、実行可能です。

make test1-4
g++ -S -masm=intel Test1-3.cc -o Test1-4.s -O3 ;ソースは上と同じTest1-3.cc
g++ -o Test1-4.out Test1-3.cc -O3
./Test1-4.out
VAL: 1234

main:
.LFB1004:
	.cfi_startproc
	push	rbp
	.cfi_def_cfa_offset 16
	mov	edx, 5
	mov	esi, OFFSET FLAT:.LC0
;std::coutへの出力を行う別の関数(outVal)があったのに、インライン展開されてる。
;(展開されてない、outValの実体も別箇所で存在します。)
	mov	edi, OFFSET FLAT:_ZSt4cout
	push	rbx
	.cfi_def_cfa_offset 24
	sub	rsp, 8
	.cfi_def_cfa_offset 32
	.cfi_offset 3, -24
	.cfi_offset 6, -16
	call	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
;----------------------------------
	mov	esi, 1234   ;ハードコーディング。
;----------------------------------
	mov	edi, OFFSET FLAT:_ZSt4cout
	call	_ZNSolsEi
	mov	rbx, rax
	mov	rax, QWORD PTR [rax]
	mov	rax, QWORD PTR [rax-24]
	mov	rbp, QWORD PTR [rbx+240+rax]
	test	rbp, rbp
	je	.L11
	cmp	BYTE PTR [rbp+56], 0
	je	.L9
	movzx	eax, BYTE PTR [rbp+67]

■じゃポインタにしないなら良いんだね良かった良かった

　ポインタとして使えないのはdefineでも一緒ですし、だったら同じ条件ですねやったー。

　…と言いたいところだが、（大佐風）微妙にこったことをすると必ず実体の定義が要らなくなるとは限りません。

■(test2-1)三項演算子の結果に使う

　三項演算子を使って、フラグによって定数を振り分けたい！ありそうなシチュエーションです。

(Test2.cc)

#include "./Test.h"
#include <iostream>

int main(int argc, char** argv)
{
	int val = argc > 1 ? Test::VAL1 : Test::VAL2;

	std::cout << "VAL: " << val << std::endl;
	
	return 0;
}

　これを最適化なしでコンパイルすると…

% make test2-1
g++ -S -masm=intel Test2.cc -o Test2-1.s
g++ -o Test2-1.out Test2.cc
/tmp/cc87c0Ta.o: In function `main':
Test2.cc:(.text+0x17): undefined reference to `Test::VAL1'
Test2.cc:(.text+0x1f): undefined reference to `Test::VAL2'
collect2: ld returned 1 exit status
make: *** [test2-1] エラー 1

　なんと。駄目でした。アセンブラを読んでみると、

;もちろん実体は定義されてない。

main:
.LFB963:
	.cfi_startproc
	push	rbp
	.cfi_def_cfa_offset 16
	mov	rbp, rsp
	.cfi_offset 6, -16
	.cfi_def_cfa_register 6
	sub	rsp, 32
	mov	DWORD PTR [rbp-20], edi
	mov	QWORD PTR [rbp-32], rsi
;----------------------------------　ここから三項演算子
	cmp	DWORD PTR [rbp-20], 1
	jle	.L2
	mov	eax, DWORD PTR _ZN4Test4VAL1E[rip] ;実体は無いのに
	jmp	.L3
.L2:
	mov	eax, DWORD PTR _ZN4Test4VAL2E[rip] ;使おうとする。
;----------------------------------
.L3:
	mov	DWORD PTR [rbp-4], eax
	mov	esi, OFFSET FLAT:.LC0
	mov	edi, OFFSET FLAT:_ZSt4cout
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	mov	edx, DWORD PTR [rbp-4]
	mov	esi, edx
	mov	rdi, rax
	call	_ZNSolsEi
	mov	esi, OFFSET FLAT:_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_
	mov	rdi, rax
	call	_ZNSolsEPFRSoS_E
	mov	eax, 0
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc

■(test2-2)最適化してみる。

　でも最適化をつけると…

make test2-2
g++ -S -masm=intel Test2.cc -O3 -o Test2-2.s
g++ -o Test2-2.out Test2.cc -O3
./Test2-2.out
VAL: 4321

main:
.LFB1003:
	.cfi_startproc
	push	rbp
	.cfi_def_cfa_offset 16
	mov	eax, 4321
	mov	edx, 5
	mov	esi, OFFSET FLAT:.LC0
	push	rbx
	.cfi_def_cfa_offset 24
	mov	ebx, 1234
	.cfi_offset 3, -24
	.cfi_offset 6, -16
	sub	rsp, 8
	.cfi_def_cfa_offset 32
	cmp	edi, 2
	mov	edi, OFFSET FLAT:_ZSt4cout
;----------------------
	cmovl	ebx, eax ;フラグを見て、条件にあうならeaxをebxへ。ここが三項演算子。
;----------------------
	call	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	mov	esi, ebx
	mov	edi, OFFSET FLAT:_ZSt4cout
	call	_ZNSolsEi
	mov	rbx, rax
	mov	rax, QWORD PTR [rax]
	mov	rax, QWORD PTR [rax-24]
	mov	rbp, QWORD PTR [rbx+240+rax]
	test	rbp, rbp
	je	.L8
	cmp	BYTE PTR [rbp+56], 0
	je	.L4
	movzx	eax, BYTE PTR [rbp+67]

　まさかの分岐命令…なし…！？cmovlはこちら参考。

　また、何度もstd::coutの関数を呼ぶのでなく、出力関数は一度だけのようです。

■(test2-3)じゃ素直にif文を使う。

　じゃあ、if文で同じことをしましょう。

(Test2-3.cc)

#include "./Test.h"
#include <iostream>

int main(int argc, char** argv)
{
	int val;
	if(argc > 1){
		val = Test::VAL1;
	}else{
		val = Test::VAL2;
	}

	std::cout << "VAL: " << val << std::endl;
	
	return 0;
}

% make test2-3
g++ -S -masm=intel Test2-3.cc -o Test2-3.s
g++ -o Test2-3.out Test2-3.cc
./Test2-3.out
VAL: 4321

　むむ。成功してしまいました。アセンブラは？

main:
.LFB963:
	.cfi_startproc
	push	rbp
	.cfi_def_cfa_offset 16
	mov	rbp, rsp
	.cfi_offset 6, -16
	.cfi_def_cfa_register 6
	sub	rsp, 32
	mov	DWORD PTR [rbp-20], edi
	mov	QWORD PTR [rbp-32], rsi
	cmp	DWORD PTR [rbp-20], 1
	jle	.L2
	mov	DWORD PTR [rbp-4], 1234
	jmp	.L3
.L2:
	mov	DWORD PTR [rbp-4], 4321
.L3:
	mov	esi, OFFSET FLAT:.LC0
	mov	edi, OFFSET FLAT:_ZSt4cout
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	mov	edx, DWORD PTR [rbp-4]
	mov	esi, edx
	mov	rdi, rax
	call	_ZNSolsEi
	mov	esi, OFFSET FLAT:_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_
	mov	rdi, rax
	call	_ZNSolsEPFRSoS_E
	mov	eax, 0
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc

　分岐命令で割り振るまでは三項演算子と同じ。でもif文の場合はインラインで定数を書いてくれるみたいですね。

　ちなみに、最適化をかけたときの結果は、三項演算子の時と殆ど同じになりました（test2-4）。

■残りのテストの概要

　残りのテストの結果は上記の結果から推測できる面白くない結果だったので概要だけ。

  • test3：三項演算子でも実体が書き加えてあればちゃんと動作します。そりゃそうさね。
  • test4-1：テンポラリな変数に三項演算子を代入するのでなく、そのままstd::coutに突っ込むところに直接書きました。でも駄目でした。
  • test4-2：4-1をコンパイルする際に最適化を掛けると、やっぱり大丈夫でした。

■

　どうやら、三項演算子はif文に展開されたりするわけではなく、別扱いになっていて、最適化フラグが掛からないときは扱いが少し違う…そんな感じでしょうか。gccのソースは読んでないのでわかりませんが…。

　エミュレータで実体を定義し忘れてたのになぜか動いていたのですが、三項演算子を使ったところでコンパイルエラーでした。なお、実体を定義する前にVC++でビルドしてたので、VC++も同じようにやってくれるみたいですが、最適化の結果どうなるのか、とかは確かめてないです。

■けつろん！

  • ちゃんと実体書こう！
  • define替わりに使うならenumハックを検討しよう！

　ほんとC++は黒魔術やでぇ…いえ、仕様通り書かない私が悪いんです。でも動いちゃうのもちょっと困るよ…。

  • †1: といっても、そのmakefileも私が書いたんですが＾＾；

windows版rsyncとubuntuサーバを使って、開発環境を同期しよう

Posted on by

　私は現在、デスクトップPCとノートパソコンで開発しています。

　こういった時に問題になるのが、開発環境の同期です。同じソフトを何度もインストールしてメンテナンスするのは時間の無駄ですから、できるだけ同期させる必要があります。

　そのために、ここ数年間様々な方法を検討して実際に使ってきました。

■方法１：USBメモリ

　PortableApps等を見習って、USBに開発環境一式を入れて使うというアプローチです。ある意味、一番素直ですね。8GB~16GB程度のUSBメモリもそれなりに安価に入手できるようになり、実用性が出ました。

  • メリット
    • “コピー”は存在しないので、同期を考えなくていい。
    • PortableAppsあたりで確立されているノウハウがそのまま使える。
  • デメリット
    • 安いUSBメモリは想像以上に遅い。そして、結構クラッシュする。
    • モバイル環境で、USBメモリが出っ張ってるのはちょっと怖い。USBが物とぶつかった場合、てこの原理でUSBコネクタが破壊されるかもしれない。

　16GBのUSBメモリが２本も壊れてしまったので、この方法は諦めました。今はまた別のUSBメモリ†1を買いましたが、大きなサイズのデータのやり取りに留めています。

■方法2：dropbox

　USBメモリを諦めて、同期すると考えた場合、まっさきに思いついた方法です。専用のクライアントをインストールすることで、Windows/Mac OSX/Linuxの各OSで、ファイルを全自動で同期してくれます。

　初期容量が2GBしかありませんが、お金を払うor無駄に頑張ることで、容量を増やすことができます。私は無料で6.1GB手に入れました！（ﾄﾞﾔ

  • メリット
    • 自動でやってくれる
  • デメリット
    • 間違えて消した結果も全自動でミラーリング。ノートPCの不意のクラッシュによってデータが破壊された場合も同様。

　とはいえ自動でシンクロしてくれるのは便利で、現在でも、開発中のソースコードをシンクロさせるのに使っています。gitリポジトリも一緒に同期しているため冗長化されている上に、仮にファイルが紛失しても元のリポジトリから取得してくれば大丈夫なようになっています。

■方法3：Bazaarの軽量チェックアウト

　新進気鋭のバージョン管理システムBazaarの、軽量チェックアウト機能を使ってSyncします。

　軽量チェックアウトというのは、SVNと似たような方式で、バージョンの一番新しいものだけが同期されます。ではなぜSVNを使わないとかというと、SVNも最新バージョンだけを同期しますが、最新バージョンのコピーも作成し、結果ファイル数が倍になってしまうのと、全フォルダに.svnというメタ情報を格納したフォルダ（先述の最新バージョンのコピーもここに入ってます）が作成され、これが存外邪魔だからです。

  • メリット
    • バージョン管理システムのリッチな所がすべて使える。
    • 変更点が一目で分かる
  • デメリット
    • クライアント側は最新バージョンだけだが、サーバ側は全バージョンなのでサーバのディスクを逼迫する（注：このsyncサーバはSSDで動いています）
    • 流石に10万ファイルを超えるとbazaarが重い。

　GUIのクライアントが一切使えないのには困ってしまいました…。コマンドラインだけだと正直ちょっとしんどいです。

■rsync

　というわけで、rsyncに乗り換えました。これにより、速度の改善とディスクの逼迫を改善したいです。バージョン管理はなくても、たぶんなんとかなります。まだそんなに使っていないので、効果についてはこれから検証！です。

■というわけで、実際にrsync環境を作ってみよう。

■Ubuntu側のセットアップ

　基本的に公式マニュアルの通りです。玄箱でやっていたあたりからずっとinetdを使って来たのですが、どうやら最近はxinetdが推奨のようですね。

　設定ファイル先頭にこんなのを書き加えるともうちょっとセキュアかも。

use chroot = yes

　一つ引っかかったのは、xinetdだけでなく、システム全体の再起動をしないとうまく接続できない（telnetで叩いてもconnection refusedされる）事くらいでしょうか。どうしてかは分からないのですが、再起動すればうまく動いたのでよしとします。

■Windows側のセットアップ

　cygwinをパッケージしたcwRsyncをDLします。インストーラだからインストール…。いえいえ、あり得ないですよね。Universal Extractで解答できます。使い方はこの辺を参考にね。

　解答するとbinやdocといったフォルダが含まれるフォルダが出てくるので、そのフォルダを頂戴して”sync”とか適当にリネームして、そのフォルダに色々とsyncのためのスクリプトを書きましょう。

　まず必要なのは、pathを通してくれるようなバッチファイルです。

rem "common.bat"として保存してね。
@echo off
set PATH=%~dp0bin;%PATH%
rem この辺は適当に調整してね。
SET REPOS=ledyba@ledyba.org::windev/
rem cwRsyncはcygwinなので、パスの形式はcygwin形式です。
SET TARGET=/cygdrive/d/software/

　同期のための個々のバッチファイルを書く際は、このファイルをcallすることにしましょう。

　%~dp0に関してはこの辺を参考にしてください。バッチファイルが置かれたフォルダに置き換えられます。結構便利。

■ファイルをサーバへバックアップする（push）

call "%~dp0common.bat"
rsync -rzht --progress --stats --chmod=a+rwx --delete %TARGET% %REPOS%
pause

　環境設定のための、先程作成したcommon.batを呼び出して環境を設定した後、rsyncを叩くだけです。

　それぞれのオプションは…

  • “-r”：再帰的にコピー。そうしないと、一番上段だけコピーされて意味が無い。
  • “-z”：圧縮をかける。exeが多いので意味があります。
  • “-h”：それっぽいログを出してくれるようになるので、ちょっとうれしくなります（ぇ
  • “-c”：チェックサムを取り、その結果を用いてコピーするかどうか判断します。
  • “–progress”：転送中の状態を表示します。
  • “–stat”：転送後に結果を表示します。
  • ” –chmod=a+rwx”：ファイル転送時にパーミッションを設定します。
    • これが一番重要です。転送時に、rsyncサーバが、デフォルトでは000でファイル・フォルダを作成してしまい、エラーが起きます。
  • “–delete”：ローカルで削除したファイルを、転送先にも反映させます。

　詳しくはこの辺参照。一番いいのは、それよりもお使いのrsyncの設定を見ることだと思いますが…。

　こんな感じです。特にこったところはありません。

■ファイルから更新されたファイルを引き出す（pull）

call "%~dp0common.bat"
rsync -rzhc --progress --stats --delete %REPOS% %TARGET%
pause

　逆の事をしているだけです…。

■ファイルが破壊されたかもしれない時用。

　私のノートパソコンは比較的クラッシュしやすい（どうしてだろう…）ので、そのための対策です。

call "%~dp0common.bat"
rsync -rzhc --progress --stats %REPOS% %TARGET%
pause

　–deleteをなくしただけです。こうすると、クライアント側には、クライアント側とサーバ側の和集合が残ります。

■

　この辺のノウハウはかなり無駄に貯めこんでるので、ちょっとずつ放出していけると良いかもしれませんね。

　みなさんも、リモート環境のノウハウが合ったら、ぜひ教えてくださいね。

■

　@ryoutenihamuさんに、common.batの存在しているフォルダのパスに空白が含まれている場合を忘れているとご指摘頂きました、ありがとうございます！また、WindowsNT系OSでは、.cmdがバッチファイルの標準拡張子だそうです…（どっちでも動くみたいですけど）。

  • †1: デザインが可愛くてかっこよくて、中々気に入っています。無くしがちなフタ部分もないし。

ミリ秒単位のタイマーと整数だけを使って60FPS固定にするには

Posted on by

　考えてみれば当たり前な方法ですが、ぐぐっても見つからなかったので…。

■

　世の中に存在する大体のライブラリでは、時間をミリ秒単位で計測することができます。一秒間は1000ミリ秒です。

　また、世の中、特にこの日本に存在するゲームは、大体60FPSで動いています。一秒間に60回画面上の絵が更新されるということです。

　1/60秒は、16.666666666666667秒。１ミリ秒が精度のタイマーでは、正確に測定することはできません。でもゲームスピードを60FPSにしたいなら、なんとか測定しなければなりません。

　そこで、多くのゲームではいろいろな方法でこの問題を解決してきました。

■方法１：1/60秒≒16ミリ秒と近似する。

　いろいろと諦めてるのがこの方法です。この方法だと、1000ミリ秒/16ミリ秒＝62.5となるので、60FPSより少し早くなってしまいますが、目をつぶります。

　ソースコードはこんな感じ

void gameloop()
{
	uint32_t nextFrame = getNow()+16;//ミリ秒のタイマー関数
	while(ゲームが終わるまで){
		move();//ゲーム内でのキャラクタの移動処理など
		uint32_t now = getNow();
		if(now < nextFrame){
			draw();//描画処理
			now = getNow();
			if(now < nextFrame){ //描画しても時間が余ってたら・・・
				sleep(nextFrame-now);//ミリ秒精度で処理を中断する関数
			}
		}
		nextFrame+=16;
	}
}

■方法２：浮動小数点を使う

　sleepも、現在の時間を取得する関数もミリ秒の精度しかありませんが、それらを管理する変数だけは浮動小数点を使う方法です。この方法を使うと、実際には16ミリ秒のフレームと17ミリ秒のフレームが、1:2の割合で現れます。

　ソースコードを見ていただけたほうが早いでしょう。

const float frameInterval = 1000.0f/60; //60FPSの基準時間

void gameloop()
{
	//floatでの管理に変えた
	float nextFrame = getNow()+frameInterval;
	while(ゲームが終わるまで){
		move();//ゲーム内でのキャラクタの移動処理など
		uint32_t now = getNow();
		if(now < nextFrame){
			draw();//描画処理
			now = getNow();
			if(now < nextFrame){ //描画しても時間が余ってたら・・・
				//型変換が必要。。。
				sleep(static_cast<uint32_t>(nextFrame-now));
			}
		}
		nextFrame+=frameInterval;
	}
}

　この方法ではかなり正確に60FPSを達成できますが、「計算の遅いfloat＋型変換まで必要、よって遅そう」、「浮動小数点の精度は直感的に分かりづらい」（からなんか気持ち悪い）という精神衛生上の問題が発生します。

　実際には一秒間に60回しか行わないので、パフォーマンス上の問題は無いでしょうし、そもそもミリ秒精度しか測れない以上キッチリ60FPSを測ることも不可能なので、floatの誤差を気にする必要は無いと思いますけど。でもなんか気持ち悪いんです…（ぇ

■方法3：vsyncに任せる

　DirectXやらOpenGLやらのゲームライブラリは、システムがモニタに画面を描画するタイミングまで待ってくれたりします。これを垂直同期(vsync)を取るといい、この方法を使うとシステムが画面をディスプレイに描画している最中にゲーム画面を更新する事がなくなるので、画面がガクついたりしなくなります。

　この方法は自分で時間を測る必要もないし†1、画面も綺麗になるしでいいこと尽くめなのですが、ひとつだけ問題があります。「すべてのモニタが60FPSとは限らない」、という点です。75FPSの画面もあれば、50FPSの画面もあります。垂直同期を取るとこういった場合にゲームが早くなったり遅くなったりしてしまいます。。

　また、必ずしもvsyncがサポートされているとは限りません。グラフィックカードの設定でvsyncを無効にすることもできます（OpenGLの場合。DirectXは存じません）。

■今回の方法：浮動小数点でなく分数で計算する

　長々と書いてきましたが、やっと今回の本題に入れます。vsyncが一番良いのはそのとおりなのですが、諸々の事情で使えないこともあるとわかりました。ということはやっぱりタイマを用いて制御しなければならないこともあるわけです。。。

　方法２のfloatを用いる方法を継承しつつ、精神衛生上よろしくないfloatを取り除きます。一秒間に1000回回るカウンタを使って一秒間に60回を測る方法…。そう、最小公倍数の6000を基準にして、分数で測ってしまいましょう†2。

void gameloop()
{
	//(1/60秒 = 100/6000秒)
	uint32_t nextFrame = getNow()*6 + 100;
	while(ゲームが終わるまで){
		move();//ゲーム内でのキャラクタの移動処理など
		uint32_t now = getNow() * 6;
		if(now < nextFrame){
			draw();//描画処理
			now = getNow() * 6;
			if(now < nextFrame){ //描画しても時間が余ってたら・・・
				sleep((nextFrame-now)/6);
			}
		}
		nextFrame+=100;
	}
}

　問題はタイマーの限界が6倍早く来てしまう点でしょうか…。SDLのSDL_GetTicksなどの32ビット整数を返すタイマでは49日間で0に戻ってしまいますが、6倍するのでだいたい8日でオーバーフローしてしまいます。

■応用

　抽象化すると「”一定期間内にn回まわるカウンタ”で”一定期間内にm回まわるカウンタ”をつくる方法」ですので、フレームレート以外でも活用していただけます。

　そもそも今回の内容は、現在開発中のファミコンエミュレータで、サウンドとCPUを同期する方法を考えていて思いつきました。とはいえその内容をそのまま書いても汎用性が低いので、フレームレートに置き換えて記述しています。

  • †1: フレームスキップするなら別です
  • †2: 書いていて中学受験を思い出しました…。

やっぱりdoubleでは「76287755398823936」は表現できない

Posted on by

　「なぜJavaScriptで「76287755398823936」が正しく表示できないか、あるいはなぜRubyでも表せないか。」の続きです。後半戦、テンションあげてまいりましょー（涙目

■出力側ソースコードのチェック！

　さて…では重い腰を上げてソースコードを読みましょうか…。　FirefoxでもChromeでも起きるなら、何かWindowsのライブラリのバグ…なんでしょうか。ま、いいや。とりあえずソースコードが探しやすそうなChromeから見てみましょう。

　それっぽいメソッドを探していくと…見つかりました。これですね。v8::internal::Grisu3()です。…あれ…？標準ライブラリじゃ…ない…！？うげぇめんどくさい…

　v8をWindows上でコンパイルするのはひたすら☆面倒†1なので、Ubuntu上でコンパイルしてCodeLiteというIDEをGDBのGUIラッパーとして使いました。これ、初めてだったんですが結構便利。Windowsでも使えるならちょっと試してみようかなってレベルです。EclipseCDTとは何だったのか。あとDDDとxxgdbはクソ。

■原因は、やっぱり精度の問題（

　これも、実はやっぱりというか結局というか、doubleの精度の問題です（

　この問題の値をintegerからdoubleに一意に表現することができるのですが、doubleからintegerには必ずしも一意に変換はできない、ということです。

■何もかもを忘れてさっきのdoubleの表現から元の値を読みだそうとしてみる

　これをやるとどうしてなのかわかります。

0/10000110111/0000111100000111010011110011000101000010010000000000

　今までの事は一切わすれて。この値、いったい何なんでしょうね？早速IEEE754に基づいて分析してみよう！（投げやりな態度で）

　ふむふむ…符号は0だから、プラスの数みたいですね。

　指数は1079だから…1023でバイアスされてるから本当は1079-1023＝56なんですね。メモメモ。

　仮数は0b0000111100000111010011110011000101000010010000000000だから、二進の小数で

1.0000111100000111010011110011000101000010010000000000（53桁）

　なんですねですね。へー。

　それで、このdoubleが示す値は

　(-1)符号 * 仮数 * 2指数

　で表現されるから…

＋1.0000111100000111010011110011000101000010010000000000 * 256

＝10000111100000111010011110011000101000010010000000000xxx

　…ん？xxx？？

■「1」と「1.00」は全然違う！

　高校や大学の時に、物理の時間とかで、定規で測った値を「1cm」とかって書いたら怒られませんでした？「この定規、ミリの目盛りまであるじゃん。1cmぴったりだったんなら、1.0cmって書かないとだめだよ！」とかって言われた記憶、ありません…？†2

　今回もそれと根っこは同じことです。「x=1」と書いたら数学的には「x=1.000000000000000000….」だけど、物理学的にはそうではなく「0.5 <= x < 1.5」のあいだであるのと同じ。

　今回の例で言えば、

1.0000111100000111010011110011000101000010010000000000

の”本当の値”は

1.00001111000001110100111100110001010000100011111111111以上、

1.00001111000001110100111100110001010000100100000000001未満

　の間にある！って事です（逆に言えば、これらの値をdoubleにすると皆同じdoubleの表現に落ちる、ということです）。これをそれぞれさっきのに代入すると…

＋1.00001111000001110100111100110001010000100011111111111 * 256

＝76287755398823928

＋1.00001111000001110100111100110001010000100100000000001 * 256

＝76287755398823944

　ほう…そう来ましたか…

とうわけで、このdoubleが示すxは、

「6287755398823928 <= x < 76287755398823944」

なんですね。そう、やっぱり「76287755398823936」には決まりませんでした。

　この時、62877553988239**という桁までは確定、その次の桁は2か3か4、最後の下一桁はさっぱり☆わからない、というわけですが、stringに変換する際はどれかには決めないといけません。この時に最後を40（上側）とするのがChrome/（とたぶんFirefoxとRuby）、30（真ん中）に多分するのがIE8/9、ということになります。でもIEの挙動はなんか標準じゃ無いっぽい…？

　IEEE754での標準の丸めモードは「最近接丸め（偶数）：最も近くの表現できる値へ丸める。表現可能な2つの値の中間の値であったら、一番低い仮数ビットが0になるほうを採用する。」との事なので、切り捨てられがちになるから上の方の値を採用してるって事なんでしょうかね、たぶん。

　ちなみに、この解説した部分がissueで示した、v8::internal::Grisu3のboundary_minusとboundary_plusを計算する部分です。V8では、boundary_plusの方から文字列を作っているので、ソースを読みたい場合はboundary_plusに着目していってみてください。

　あとこの実装の理論的詳細はこちら「Florian Loitschの論文”Printing floating-point numbers quickly and accurately with integers”」にあるそうです。

■もっと単純に表現すると

　「76287755398823936=0b100001111000001110100111100110001010000100100000000000000」は最後の0まで意味があるので、43ビット精度の数ではなくてやっぱり57ビット精度の数です。

　つまり、64ビットの浮動小数点の精度53ビットでは足りないので、うまく表現することはできません。

■でも「76287755398823936」って出てほしい！！

　1cmって書いたら1.0ｃｍだし1.00cmだって言いたくなるのも人情（たぶん）。そう表現したい場合は、

javascript:alert((76287755398823936).toFixed(0))

　ってやってみてください。詳しい仕様はこちら！そして今までの、ToStringをnumberに適用した場合の仕様はこちら。

■まとめ

  • JavaScriptで整数を扱うときは53ビット整数までにしよう（あれ…？普通だ…？）
  • 浮動小数点は結構厄介。でもたまに見る分には面白いね！

■早速v8のissueに回答もらった

　はやい！ありがとう！

Precise representation of this number requires 57 bits not 43.

When formatting a string representation of double we are free to choose any string that when parsed back would give the same double number. Simply speaking only the following must hold:

parseFloat(d.toString()) == d

In this case both 76287755398823940 and 76287755398823936 map to the same double number and we can use either of them when printing the result back.

You can use d.toFixed(0) to uses different formatting algorithm for numbers less than 10^21. This algorithm will render double with mantisa m and positive exponent p exactly as integer m*2^p. In you case it means that

(76287755398823936).toFixed(0) === “76287755398823936”

For more information please read:

ECMA-262 5th 9.8.1 ToString Applied to the Number Type. http://es5.github.com/#x9.8.1

ECMA-262 5th 15.7.4.5 Number.prototype.toFixed (fractionDigits) http://es5.github.com/#x15.7.4.5

Details about the algorithm used by V8 are available in Florian Loitsch’s paper “Printing Floating-Point Numbers Quickly and Accurately with Integers”.

　こんなに詳しく教えてもらえるなんてほんとありがたいです…。しかしそれに対する私の返答はひどすぎ…。こういうのあるともっと英語を知らないとな！って思います…。

  • †1: SConsっていうビルドツールとかが必要。
  • †2: 多分理系じゃないと無いとおもうケド。

なぜJavaScriptで「76287755398823936」が正しく表示できないか、あるいはなぜRubyでも表せないか。

Posted on by

　「Twitter住所特定実験」を開発中に気づいた事です。取得したツイートをサーバからJSONでクライアント側のJSに送る処理があって、当初この時にTwitterのツイートのIDをJSONに数値として含めて送っていました。

　が、JavaScriptではこの値を受信してeval()した†1際、うまく変換することができず、たとえばChrome/Firefoxでは「76287755398823940」となり、微妙に異なった数値になってしまいました。

　以下をクリックすることで、実際に実行できます。

javascript:alert(76287755398823936)

　IE8/9だと「76287755398823930」となり、まだ微妙に違った値になります。

■doubleの精度の問題？？

　まず疑われたのはdoubleの精度の問題。一部では有名な話で、JavaScriptでは数値はすべてdoubleで持っています。doubleは64ビットの浮動小数点なので、64bit整数より若干精度が落ち（具体的には53ビットしか精度がありません）、かなり大きな（64bit整数の限界に近いような値は）うまく表現することができません。

　で、実際に実験してみると…。

$ cat test.asm
global  _main
extern  _printf
section .text
_main:
;問題の値を読み込む
push 0x010f074f
push 0x31424000
fild qword [esp]
;64ビット浮動小数点としてスタックに保存←おそらくここで下位ビットが失われる
fstp qword [esp]
;表示
push    messagef
call    _printf
add     esp, 12
ret
messagef:
db      "%f", 0x0a, 0
$ nasm -fwin32 test.asm
$ gcc -o test.exe test.obj
$ ./test.exe
76287755398823936.000000

…あれれ！？せっかくアセンブラまで書いたのに

■実は余裕でdoubleで表せる

　Doubleの精度は53ビットまでですが、この「76287755398823936」という値は43ビットの精度があれば表すことができます。この値を2進数で表すと、

100001111000001110100111100110001010000100100000000000000（57ビット）

　となります。これは57ビットありますが、doubleで十分表すことができます。えっdoubleって53ビットまでってさっき言ったじゃん？

　それについて詳しく納得していくために、doubleの仕組みを見ていきましょう。

　doubleはIEEE754に基づく浮動小数点で…。能書きはいいさね、実物を見ながら解説します。

　問題の値のdoubleでの表現は次の通りです。

0/10000110111/0000111100000111010011110011000101000010010000000000

　スラッシュで区切った三つの構造からできています：左から符号、指数、仮数。

　浮動小数点では、理系の本でよく見るような値の表現をします。つまり、

+4.2195 * 10³m

　みたいな感じですね。42195mじゃなくて、+4.2195 * 10³mです。

■符号（0）

　先ほどの例で言うと、「+」のところを現しています。

　1ビットの値で、0ならプラス、1ならマイナスの値で有ることを示します。

■指数（10000110111）

　先程の例で言えば、「³」の部分にあたります。

　11ビットの値で、仮数で表される値が2の何乗されるかを表します。ただし、この値は本当の値より1023大きく表現されています。-2（マイナス二乗）のように小さな値を示す場合に困らないようにするための表現です†2。これをバイアスする、と言います。

■仮数（0000111100000111010011110011000101000010010000000000）

　残りの52ビットの値です。先程の（略）、「4.2195」に対応します。

　doubleでは10進数の小数ではなく、二進数の小数を表します。

　よって、値は必ず1.01011110… * 2xxxxのように表す、つまり小数点より大きな部分は必ず1とするように指数を調整することができます（正規化）。

　そこで、doubleでは最初の1を省略して残りの小数点以下の部分だけをここに記入しています。つまり、この仮数は、

1.0000111100000111010011110011000101000010010000000000

　という二進数の小数を表している、ということになります。

　最初の1ビットを省略してるので、実際に表現できる桁数が1ビット増えるんです。仮数部分が52ビットしかないのに、精度が52ビットでなく53ビットなのは、このためです。

■基数

　先ほどだと10の何乗かをかけていましたが、doubleでは2の何乗をかけています。

■まとめ

　以上をまとめると、doubleのデータは符号、仮数、指数の部分に分けられて、

　(-1)符号 * 仮数 * 2指数

　の値を示す、ということがわかりました。

■問題の値をdoubleに手動で変換してみよう。

　問題の値は、

100001111000001110100111100110001010000100100000000000000

でした。これを実際に表して先ほどしめしたのと一致することを確かめましょう。まずは2進小数での表現になおします。10進数と同じ、小数点を移動させるだけですよ。

1.000011110000011101001111001100010100001001 * 256

　ほら、こうすると最後の0が消えて43桁の二進数になったでしょう！だから53ビット精度で表せるはずです。

　上の説明とにらめっこしながらパラメータを決めると…

符号：0（プラスだから）

指数：56+1023 = 1079（1023でバイアスします）

仮数：000011110000011101001111001100010100001001（二進数）

（小数点以下だけをdoubleには記入します；けち表現）

これを並べると…

0/10000110111/0000111100000111010011110011000101000010010000000000

　元に戻りました！とりあえず、doubleでもちゃんと表現できるんだってこと、理解してもらえましたか？

■問題は入力側？出力側？

　となると、これはブラウザのどこかでバグが起きてるということになります。

　さて、問題の切り分けを行いましょう。この問題は、2つのうちのどちらかで起こってると思われます。

  • 入力側（ソースコードに書かれた文字列をdoubleに変換する際に起こっている）
  • 出力側（doubleを文字列に変換する際に起こっている）

　で、切り分けるために実際に試してみたのがこれ。

javascript:alert(76287755398823936/1024)

　割り算してみました。本当に内部の表現でも76287755398823940になってる（＝入力側の問題）なら1024では割り切れないから何かしらの少数が出ると思われますし、もし実は内部表現は正しくなってる（＝出力側の問題）なら、きっと桁数が減ってうまく表示できると思われます。

　で、結果は「74499761131664」になったと思います。これは正しい結果です。

■Rubyでも起きる！

　いつ書こうか悩みましたが、この問題はRubyでも発生します。

$ ruby1.9.1 -e "puts 76287755398823936.to_f"
76287755398823940.0

■次回に続きます

　今から続きを書きますが、長くなりすぎたのでちょっと分割。とりあえずV8のissueに投げておきましたので、ゴミのような英語でも良いならそちらへ…。

■続きかけた

　つづきです：

やっぱりdoubleでは「76287755398823936」は表現できない

  • †1: といいつつprototype.js頼りですが
  • †2: 補数表現じゃだめだったんだろうか？

SVNのデフォルト無視設定

Posted on by

　引っかかってしまって悩んだので備忘録的に書いておきます。

■

　SVNでは、一切設定をしていなくても特定の拡張子をデフォルトで無視するようになっています。

　設定ファイル（UNIXでは~/.subversion/.config、windows版ではC:\Users\<ユーザ名>\AppData\Roaming\Subversion\config）内では、一切設定していない場合このようになっています。

# global-ignores = *.o *.lo *.la *.al .libs *.so *.so.[0-9]* *.a *.pyc *.pyo
#   *.rej *~ #*# .#* .*.swp .DS_Store

　これを読む限りだとコメントアウトされてるから無視されなさそうな感じがしますが、実は無視されます。（設定例を示すのではなく、デフォルト値を示すコメントみたいで…。）

$ touch test.a
$ svn st
$ svn st --no-ignore
I       test.a

　明示的にこれらを共有したい場合は、svn addに–no-ignoreを設定するか、上記の設定ファイルをコメントアウトして無視設定を外すなど工夫が必要です。

# こうすれば無視しなくなる
global-ignores =

$ svn add --no-ignore test.a
A         test.a

■

　現在ノートPCとデスクトップPCでSVNを使って開発環境を共有してるのですが、この仕様でひどく苦労しました…。Bazaarに移行しようかな、やっぱり…。