SWF Binary Golf on FlashLite

先週の土曜日の勉強会で発表した資料を公開します。

FizzBuzz SWF Binary Golf on FlashLite 1.1

FizzBuzz SWF Binary Golf on FlashLite 1.1
http://namazu.org/~takesako/swf/FizzBuzz-SWF-Golf.ppt

申し訳ないことにActionScriptの話は一つもでてきません。
SWFファイルの構造解析とASバイトコードの話です。
そんなシチュエーションがあるかどうかわかりませんが、
SWFファイルのバイナリを直接いじりたいときに役に立つのではないかと。

勉強会ではどの発表も面白かったのですが、個人的にはBeInteractive!のyossyさんとASバイトコードの話ができて嬉しかったです。

[お約束] SWF で FizzBuzz ってみた

とりあえず

(1) 正解のFizzBuzz文字列をそのまま出力した場合 -> 478 byte (FlashLite1.1)
http://namazu.org/~takesako/swf/fizz478.txt

(2) FizzBuzzを計算しながら出力した場合 -> 251 byte (FlashLite1.1)
http://namazu.org/~takesako/swf/fizz251.txt

(3) FizzBuzzを計算しながら出力した場合 -> 159 byte (FlashLite2.0)
http://namazu.org/~takesako/swf/fizz159.txt

ここまで圧縮できました。

ASバイトコード最適化

ASバイトコードの最適化の過程はこんな感じで

http://namazu.org/~takesako/swf/

--- fizz287.flm	
+++ fizz161.flm
@@ -1,71 +1,48 @@
-movie 'fizz287.swf' // flash 4, total frames: 1, frame rate: 12 fps, 104x104 px
+movie 'fizz161.swf' compressed // flash 6, total frames: 1, frame rate: 12 fps, 104x104 px

   frame 0
-    push 'i', '0'
-    setVariable
    label1:
-    push 'i', 'i'
+    push '100', 'i', 'i', 'i'
     getVariable
     increment
     setVariable
-    push '100', 'i'
     getVariable
     oldLessThan
-    not
-    not
     branchIfTrue label6
-    push 'x', 'x', 'x'
-    getVariable
-    push 'i'
+    push 'x', 'x'
     getVariable
     push 'i'
     getVariable
     push '15'
-    divide
-    int
-    push '15'
-    multiply
-    subtract
+    modulo
     branchIfTrue label2
     push 'FizzBuzz'
     branch label5
    label2:
     push 'i'
     getVariable
-    push 'i'
-    getVariable
     push '5'
-    divide
-    int
-    push '5'
-    multiply
-    subtract
+    modulo
     branchIfTrue label3
     push 'Buzz'
     branch label5
    label3:
     push 'i'
     getVariable
-    push 'i'
-    getVariable
     push '3'
-    divide
-    int
-    push '3'
-    multiply
-    subtract
+    modulo
     branchIfTrue label4
     push 'Fizz'
     branch label5
    label4:
     push 'i'
     getVariable
    label5:
     concat
     push ' '
     concat
     setVariable
     branch label1
    label6:
   end // of frame 0
end

yossyさんから教えてもらったFlasmのコードでASバイトコードを読みやすい形に変換しています。

最後のFizzBuzz159byteへの圧縮は、ちょっとトリッキーなことをしています。

僕はActionScriptの経験は素人以下ですが、SWFバイナリの話ならできますので、
またどこかでAS関係のイベントがあれば声を掛けてくださると嬉しいです。(><)

この度は貴重な勉強会に参加できてよかったです。ありがとうございました。

Web2.0時代のAjax Binary Hacks

遅くなりましたが、Binary 2.0 カンファレンス2006 で発表した資料を公開しました。

※公開用にいくつか手を加えてあります

前フリが長いとのツッコミがありましたので、今回の発表内容を少し要約してみたいと思います。

1. GIF Format Hacks (Server side)

まずは、任意のpixelサイズ(幅・高さ)を持った画像ファイルを固定長の35byteで出力する方法

#!/usr/bin/perl
use strict;
use warnings;

sub create_gif {
  my $size = pack "S2", @_;
  return "GIF89a$size\xf0\x00\x00\x00\x00\x00\xff\xff\xff,"
  . "\x00\x00\x00\x00\x01\x00\x01\x00\x00\x02\x02L\x01\x00;";
}

print "Content-Length: 35\n";
print "Content-Type: image/gif\n\n";
binmode(*STDOUT);
print create_gif(65535, 65535);

1;

この画像フォーマットを利用すると、任意のサイズ(幅・高さ)を持ったGIF画像をサーバサイドで出力することができます。

実際に作った 65535 x 65535 pixel の 35 byte GIF画像ファイルですが
http://namazu.org/~takesako/slides/65535×65535.gif
Webブラウザのレンダリングに大量のメモリを消費することはありません。

2. Ajax Hacks (Client side)

このテクニックは
Binary Hacks の献本をいただけなかった人から教えてもらったのですが、
サイズを指定しないImageオブジェクトに対して、JavaScriptのonloadのタイミングで画像のwidth属性を読み込むことができます。

<img src="null.gif" onload="alert(this.width)">

これを応用すると、WebブラウザのJavaScriptから非同期リクエストを飛ばして、サーバからの結果を画像のwidth属性から読み取れます。

function callback(data) {
  // ...ここにコールバックの処理を書く...
}

var img = new Image;
img.onload = function(){callback(img.width)};
setTimeout(function(){img.src='http://example.com/null.gif?q=hoge'}, 0);

/*
<img src="http://example.com/null.gif?q=hoge" onload="callback(this.width)">
*/

これはすごい

ということで、究極のJavaScript非同期クロスドメインAPIとして、
クロスドメイン越えができる非同期リクエストをJavaScriptから簡単に飛ばせる、
というテクニックでした。

# 一度に 16bit x 2 (width, height) のデータしか返せませんけど…いろいろ応用できると思います

簡単なデモは ここをクリック

以上、全面的にmalaリスペクトでお届けしました。

お詫び (2006.12.25 追記)

Web2.0時代のAjax Binary Hacks で公開した資料の中に
一部不適切な画像がありましたので、削除いたしました。

省メモリプログラミング勉強会

12/1(金)に
全文検索エンジン Sedue を作っている
有限会社Preferred Infrastructure(長くて覚えられないので略してPFI社)
のエンジニアの方々をサイボウズ・ラボにお招きして、省メモリプログラミング勉強会を開催しました。

西川さんによるPreferred Infrastructure会社紹介

非常に深い話が多く、私自身とても勉強になりました。

  1. Succinct Data Structureと最近の圧縮アルゴリズム(岡野原さん
  2. Xinno 昔話 – PalmOS / 68k 時代のデータ構造とアルゴリズム(奥さん
  3. count_leading_zerosとFlash Liteでのバイナリ圧縮(鴨志田さん

今度の Binary 2.0 カンファレンス 2006 で、この勉強会で挙がったネタの一つが披露される予定です。

ご期待ください。

Binary Hacks と 64bit popCount 問題

各所レポートが挙がっている通り、私の手元にも Binary Hacks の献本が届きました!

表紙
Binary Hacks サポートページ
書名 Binary Hacks
サブタイトル ハッカー秘伝のテクニック100選
著者 高林哲,
鵜飼文敏,
佐藤祐介,
浜地慎一郎,
首藤一幸
出版社 オライリー・ジャパン
定価 3,360円 (税込)
ページ数 412ページ
ISBN 4-87311-288-5
発売日 2006年11月11日
版型 A5

高林さん、オライリーさん、ありがとうございます。

ちなみにetoさん情報によると、明日11/10は「いいバイナリの日」らしいです。

  • 11 → いい
  • 10 → バイナリ

Binary Hacks の発売日は 11/11 で、ビットが全部立っている非常に縁起の良い日です。

縁起を担ぐためにも、いいバイナリの日に Binary Hacks を注文して、発売日に書店に行って本を見かけたら 11 冊買いましょう。

x86 パフォーマンスチューニング

さて、最後の HACK #100「文献案内」でマイクロプロセッサアーキテクチャマニュアルが紹介されていましたが、
x86のパフォーマンスチューニングつながりということで、
ちょうど今日ラボの社内掲示板で盛り上がった話題をこちらでも共有したいと思います。

* popCount 問題

64bitの数値の中で1になっているビット数を数える

popCount64bitA

unsigned long long popCount64bitA(unsigned long long x) 
{
    int n = 0;
    n += popTable[x & 0xff];
    n += popTable[(x >> 8) & 0xff];
    n += popTable[(x >> 16) & 0xff];
    n += popTable[(x >> 24) & 0xff];
    n += popTable[(x >> 32) & 0xff];
    n += popTable[(x >> 40) & 0xff];
    n += popTable[(x >> 48) & 0xff];
    n += popTable[(x >> 56) & 0xff];
    return n;
}

popCount64bitB

unsigned long long popCount64bitB(unsigned long long x) 
{
    x = ((x & 0xaaaaaaaaaaaaaaaaUL) >> 1)
      +  (x & 0x5555555555555555UL);
    x = ((x & 0xccccccccccccccccUL) >> 2)
      +  (x & 0x3333333333333333UL);
    x = ((x & 0xf0f0f0f0f0f0f0f0UL) >> 4)
      +  (x & 0x0f0f0f0f0f0f0f0fUL);
    x = ((x & 0xff00ff00ff00ff00UL) >> 8)
      +  (x & 0x00ff00ff00ff00ffUL);
    x = ((x & 0xffff0000ffff0000UL) >> 16)
      +  (x & 0x0000ffff0000ffffUL);
    x = ((x & 0xffffffff00000000UL) >> 32)
      +  (x & 0x00000000ffffffffUL);
    return x;
}

→ どちらが速いか?

続きを読む

Binary2.0カンファレンス2005に行ってきました。

ふと自分の過去を振り返ってみると、人生で一番最初に触ったPCは富士通の「FM-TOWNS」というi386(16MHz)のマシンで、学生時代にx86のハンドアセンブルやコードチューニングにハマッていた時期がありました。そんな私にとってBinary 2.0カンファレンス2005はとても楽しめる内容でした。期待以上に楽しかったです。簡単にカンファレスの概要と感想をレポートします。

追記:まとめのページができたようです。

■ 1. Binary 2.0 時代の到来 – 高林哲

binary1keynote.jpg

satoru先生による基調講演。なぜ今さらバイナリなのか?

「Binary2.0は高度なWeb2.0サービスの構築に必要不可欠な技術」というのは表向きの説明で・・・
実は「Web2.0についていけない」のが本音。(w
今のうちに新しいバズワードを提唱して「既得権益を確保」しておこうという狙い。
つかみはOK。会場大爆笑の渦でした。

[発表資料]

■ 2. プログラムはなぜ Mona OS で動くか?fork?何それ? – ひげぽんさん

binary2mona.jpg

Mona OS とは?

2ch生まれのオープンソースOSで、カーネルはC++で書かれている。
ソースコードも5万行で、他OSよりも圧倒的に短い。オブジェクト指向万歳。
中身はマイクロカーネルっぽくって、バッファオーバーフローありありのノーガードOS。w

ユーザモードで各種サーバ(プロセスサーバ・PE or ELFサーバ・ファイルサーバ)が動作。
ユーザモードでできることはユーザモードで実装し、割り込みまでメッセージベースでやりとりしている。
Hello Worldでも一苦労、OSの中のひとは大変・・・という内容でした。

[発表資料]

Binary2.0 のはてなリングもあるので、興味のある方は是非参加してみてくださいとのこと。

■ 3. Dynamic Programming Language C — 私は誰? – 浜地慎一郎さん

binary3shinh.jpg

SDLプレゼンテーションシステム(SPS)によるプレゼン。

嫌いなもの
– 似たコードの連続

解決方法
– スクリプトでコード生成
 ダサいよね
 生成してからコードを再編集するとイヤなことに
– C/C++のマクロ
 CppUnitとか
 少しマシになっただけ
そうだリフレクションだ
でもCには・・・リフレクションがない
 Javaを使う→(自分にとっては)論外www

道のり

* which $0
 私は誰?
 実行しているEXEを取得
 環境依存、#ifdefの嵐、バッドノウハウの山
 ライブラリ化したい(グッドラッパーを目指す)

* ldd
 ロードされているDLLを取得

* nm
 オブジェクトファイルを見てシンボルを取ってくる
 080xxxxxxx T bfd_make_readable とか

* libbfdで関数アドレスを取得
 GNU binutilsのライブラリ
 オブジェクトファイルを読み書きできる
 多数の対応フォーマット

* c++filt
 C++のシンボルは読めない
 デマングル(w

* 取得した関数のcall
 関数のシグネチャが決まっていれば簡単
 わかっていない場合
 - libffi
  GCJで利用されている
  動的ディスパッチが可能
 - ffall
  GNUStepで利用されている

JavaやRubyなどと比較すると・・・
 可搬性にやや難
 わかりにくいエラーメッセージ(w
 言語に統合されていない
 構造体メンバが見れない

いいところ
 楽しい!

[活用事例]

しー言語(言語というよりかバッチに近い)
#!./she
puts "hello world!"
!load  "m"
dx = cos 3.2
printf "%f" dx

Dynamic Test Runner
 .o ファイルをロード・再配置
 内部の dtr_test を含む関数をかたっぱしから実行

Ruby/C++ Ruby/D ちょっと作ってみた
 RubyからC++のクラスを直に、SWIGは面倒
 Objective-C++、Java & Groovy みたいに
 バインディング不要

[言いたかったこと]

コピペでコード書きたくない!(笑)

[発表資料]

■ 4. G-Inspector — GTK+ ランタイムインスペクション – 青笹茂さん(順番入れ替え)

binary4ginspector.jpg

GTK+はメジャーな言語をサポート
 Ada、Eiffel、Haskell、SmallTalkって・・・(テラワロス

typedef、マクロ、データ構造、リスト、
バイナリツリー、イテレータ、
イベントループ、フレームワーク、抽象化したI/O

GObject
– GTK+の肝
– C言語でオブジェクト指向するためのフレームワーク

ここに実行バイナリがあります
 stripされてる
 ソースもない
そこで G-Inspector の登場!
– editresみたいなもの
– オブジェクト一覧
– 実行中にプロパティを変更
– ウィジェットツリーをシリアライズ(XMLとか)
– メモリ領域をダンプ

* ついでに GNU Autotools のクイックツアー

Autoconf/Automake/Libtool/pkg-config

個人的にはバッドなノウハウがとても一杯の感覚が抜けないんだけど、最近は

configure.ac
Makefile.am
{name}.pc

の3つのファイルを書くだけでいけるようになったらしい。
pkg-config は知らなかったので今度から使ってみよう。

■ 5. g++と例外キャッチボール – 中村孝史さん(順番入れ替え)

binary5dwrf2.jpg

スーツ族?クールビズです 地球にやさしいwoです

g++の例外処理を解明します
でも、キャッチボールはできません(www

gccで一番良く使うオプションは -S です(w

例外処理は何でできてる?
 unwind  – 超return
 type_info – do_catch()メソッド

名前 mangling ルールを覚えて extern
(大爆笑

unwind-SjLj
unwind-dwarf2

DWRF2 デバッグ情報フォーマット
 いくつかのレジスタ
 オフセット、状態、CFA、リターンアドレス
 オフセット計算アドレス
 命令セット
→ 実はプログラミング言語?

余談:makefileでクイックソートとかも(すげー)

[発表資料]

■ 6. 実行時自己書き換え佳境 – 首藤一幸さん

binary6corewars.jpg

Core Wars知ってますか?(私ははじめて知りました)

マルチスレッドなプログラム
 実行の流れ(スレッド)が複数あって、メモリ空間を共有する。
 これってリアル Core Wars ですか?

なんで自己書き換えなんかするの?
– HotSpot VM (SunのJava仮想マシン)
 アプリのスレッドを任意の箇所で停止させるために、
 ソフトウェア割り込み命令を上書きする。
 後で元のコードを書き戻す。
 ガベージコレクションやOn-stack replacementが目的。
– IBMのJava仮想マシン (by IBM東京基礎研)
 バッドなノウハウ満載
– shuJIT (x86用 Java JITコンパイラ)
 クラスの初期化
 インスタンス生成時の諸チェック
 Interface実行時のチェック・・・

Core Wars のテクニックを利用して:
   nop
   nop
   初回実行時のみの処理
   nop を jump done に書き換え
done:

x86でプログラムカウンタを読む小技

他のスレッドを妨害しないために
Atomicに書き換える
 x86だとXCHG命令など
ロック
 モニタ、セマフォ
 一時停止

 EB FE をアトミックに書き込む
 他のスレッドはループして待機

[発表資料]

■ 7. ハードコアバイナリアンへの道 – 八重樫剛史さん

binary7hardcore.jpg

[下には下がいる]

ユーザランド C/C++/Java/Perl/…
カーネル Assenmbly/C/C++
——————————–
ハードウェア VHDL/VerilogHDL
半導体プロセス ???

ゲート、プリップフロップ
バイナリを生で扱う
I/O(実世界)と直接つながっている

ハードウェア記述言語(HDL)で回路を書く

実際にFPGAボードのVGA出力でプレゼンテーション。
しかも世界初のリモートGDBプレゼン(テラスゴス
→ これにはぶったまげました。ハードコアバイナリアン第一号に認定します。w

[発表資料]

■ 8. ライトニングトーク

binary8lightningtalk.jpg

ここから一人5分間の怒涛の Lightning Talk が開始(時間厳守です)

■ 8-1. Binareal – バイナリファイルの構造と解釈 – 大和正武さん

binary81binareal.jpg

Etherealにインスパイアされて開発を始めたBinarealの紹介
構造改革前と後(うまいなぁ)
バイナリデータを可視化するためのツール

■ 8-2. いけないお化粧magic(5) – 野首貴嗣 5分

binary82magic.jpg

Flashでプレゼン
magicでファイル判定
 M$ Office と OpenOffice.org
 Namazu と Sary(一部自虐ネタ)
トリビアの紹介などなど
期待以上の内容でとても面白かったです。w

[発表資料]

■ 8-3. livepatch – 概念と技法 – 鵜飼文敏さん

binary83livepatch.jpg

実行中のプロセスにパッチをあてる(CGLの要求仕様のひとつ)
– Pannusプロジェクト
– livepatch

ptrace(2) – 黒魔術のシステムコール
MDFライブラリ

[発表資料]

■ 8-4. 斜め下を行くバイナリ書き換えの探求 – 後藤正徳さん

binary84binedit.jpg

Linuxに数行のスペシャルパッチを適用すると・・・
実行時バイナリをバイナリエディタで直接書き換えが可能に!w
アイデア勝負ですね。

[発表資料]

■ 8-5. Cache Pollution Aware Patch – よしおかひろたかさん

binary85cache.jpg

Miracle Linux の中のひと。

CPUの速度向上(+50%/年)
メモリの速度向上(+7%/年)

L1 < L2 < メモリ

ユーザ空間からのコピー
copy_from_user_ll()
をチューニングすると早くなる

カーネル読書会やってます

[発表資料]

■ 8-6. Inside QEMU – BEROさん

binary86qemu.jpg

QEMU
 複数のターゲット、ホストに対応したエミュレータ
Cによる移植性の高いJITコンパイルをどうやって実現しているか?
 TARGET CPUの命令をC言語の関数で実装したものをコンパイル&リンク
→惜しくも時間切れ・・・

[発表資料]

■ 8-7. GNP — ‘g’ Network Protocol-Stack (for Boot Loader) – g新部裕さん

binary87gnp.jpg

m32r-g00ffに実装したプロトコルスタックの話のはずだったけど・・・
Binary 2.0カンファレンスのドレスコードは「ブラックandホワイト」だったらしい(w
しかもバイナリアンだったら指折りは2進法で数を数えますよね?って(www

次回は「Binary 2.0 カンファレンス MaxHeart」と改名して、ドレスコードは「ブラックandホワイト」に新しく「ピンク」を加えてみましょう。:-)

それでは、みなさん、Happy hacking!