コグノスケ

誕生日

早いもので41歳になりました。昨年の日記（2023年3月10日の日記参照）を見ると、コロナの流行を心配していました。

コロナの流行は相変わらずのように思いますが、世の人々はもう対策に疲れたのか、感染リスクを無視して暮らすスタイルが定着したようです。個人的には感染しないに越したことはないので、これからもマスクなど予防は心がけたいと思います。花粉症にもなりたくないし……。

働き方はリモート10割から、リモート:出社=7:3〜5:5くらいの割合に落ち着きつつあります。特にオフィスに用事がなければ行かないなんて、昔では考えられない通勤スタイルですね。

この働き方の利点は「遠隔地に居る人」が気にならなくなることです。オフィスに集まる場合を除けば、家も沖縄も北海道も大して変わらないのです。実際、東京から離れて住んでいる人もいるようですね。

車のバッテリー完全に死亡で交換かと思いきや

目次: 車

またまた車のバッテリーが干上がって死にました。写真は撮っていませんが2Vくらいになっていたように思います。

しかし今日はディーラーでの半年点検の日でディーラーに行かなければならないので、ジャンプスタートしてエンジンをかけてディーラーまで行きました。去年買った（2023年4月22日の日記参照）KashimuraのジャンプスターターKD-238が大活躍です。活躍しないほうが本当は良いけど。

ディーラーに辿り着いて車を預けたら、ディーラーの駐車場から動かそうとしたらバッテリーが上がってて動かせなかった、ジャンプスタートしたと言われました。ごめんね……。

ディーラーからの意外な提案

またバッテリー交換で財布が軽くなるな〜と思っていたら、整備士さんからは意外な提案が返ってきました。

• 一時的にディーラー所有のバッテリーに交換して車を返す
• 上がった方のバッテリーは1週間掛けて充電してみる
• バッテリーが充電できたら連絡するからまた来てほしい

とのこと。

バッテリー交換以外の新たなパターンに出会いました。交換して1年、走行距離も1000km程度、バッテリーはこんなに劣化しないはず？と判断したみたいです。たぶん安く何とかしてみたい、というご提案だと理解して素直に承諾しました。

バッテリー復活なるか？いつもと違うので楽しみですね。

JavaとM5Stamp C3とBluetooth LE - BluetoothデバイスとServiceの列挙

目次: Arduino

M5Stamp C3をBluetooth LEデバイスにして、Linux PCもしくはRaspberry PiなどのLinux SBCとお話する取り組みの続編です。

今回はbluez-dbusを使ってBluetoothデバイスの列挙、GATTのServiceの列挙を行います。

アダプタとデバイスの列挙

DeviceManagerというクラスとDeviceManagerクラスのスタティックメソッドが、bluez-dbusを使うときの根っこになります。

DeviceManagerのインスタンスを作成するため最初にcreateInstance()を呼ぶ必要があります。1回で良いです。これ以降はDeviceManager.getInstance()でDeviceManagerのインスタンスが取得できます。引数はfalseならシステム全体用のバスインタフェース、trueなら現在のログインセッション用のバスインタフェースに接続します。Bluetoothの仕組みとは関係なくて、Bluezが依存しているD-Busの仕組みが透けて見えています。たぶんfalseで良いはず。

//一番最初に1回呼ぶ
DeviceManager.createInstance(false);

//以降はgetInstance()でDeviceManagerオブジェクトを取得できる
DeviceManager.getInstance();

システムに存在するBluetoothアダプターの一覧を得る方法はこんな感じです。お手軽です。

DeviceManager deviceManager = DeviceManager.getInstance();

List<BluetoothAdapter> adapters = deviceManager.getAdapters();

Bluetoothアダプターを1つ選んだら、Bluetoothデバイスを探して（Discovery）、ある程度時間を置いて見つかったデバイスの一覧を取得します。

BluetoothAdapter adapter;

adapter.startDiscovery();
try {
    Thread.sleep(3000);
} catch (InterruptedException ex) {
    //ignore
}
adapter.stopDiscovery();

List<BluetoothDevice> devices = deviceManager.getDevices(true);

注意点としてはstartDiscovery()とstopDiscovery()の間はある程度の時間を開けないとデバイスが1個も見つかりません。

Serviceの列挙

Bluetoothデバイス特にBLE（Bluetooth Low Energy）デバイスとはGATTプロファイルを使って通信します。BluetoothにはATTプロトコル（Attribute Protocol）という属性をやり取りするプロトコルがあります。GATTはATTプロトコルの上で汎用的（Generic）にデータを通信するための取り決め（プロファイル）になります。

GATTというかATTはクライアント・サーバー方式のプロトコルでして、BLEデバイスはサーバーになります。サーバーはService（＝提供する機能）を1つもしくは複数持っています。1つのService内にはCharacteristicが並んでおり、CharacteristicにはValueとDescriptorが並んでいます。こんな感じです。

GATTサーバー（BLEデバイス）

Service

Characteristic

• Value
• Descriptor
• Descriptor
• ...

Characteristic

• Value
• Descriptor

Service

Characteristic

...

Characteristic

...

通信に使うのはCharacteristicですが、いきなりCharacteristicを列挙することはできません。上位側にあるServiceから列挙します。Serviceを探すにはconnect()してgetGattServices()を呼びます。connect()とdisconnect()は数秒レベルで時間がかかります。

今回はM5Stamp C3に対してペアリングなしで接続しています。ペアリングなし＝通信路の盗聴や乗っ取りをされる可能性があります。今回は特に困らないのでこのまま話を進めますが、盗聴や乗っ取りをされると困る場合はペアリングをする必要があります。ペアリングの方法もご紹介したいですが、今はやり方がわかりません。わかったらまた別の日記にでも書きます。

Serviceの列挙

BluetoothDevice device;
device.connect();
device.refreshGattServices();

List<BluetoothGattService> gattServices = device.getGattServices();

device.disconnect();

GATTのService内のCharacteristicを探すにはgetGattCharacteristics()を呼びます。

Characteristicの列挙

BluetoothGattService srv;
srv.refreshGattCharacteristics();

List<BluetoothGattCharacteristic> gattCharacteristics = srv.getGattCharacteristics();

CharacteristicのDescriptorも取得できます（getGattDescriptors()メソッドを使います）が、今回は特に必要ありませんので列挙するためのコードは割愛します。

送受信の方法はまた今度。

Raspberry Pi 3 model Bの代わりにROCK 3 model C

目次: Arduino

最近、M5Stamp C3 + Raspberry Piを組み合わせて的あてゲームを作っています。Bluetooth通信クライアント側のLinuxマシンにRaspberry Pi 3 model Bを使っているものの、販売終了につき新品が手に入りません。今は1台あれば良いので困りませんが、後でN増しするとき困りそうです。

Linuxマシン側の要件を挙げると、

• Must: Linuxが動作、x86でもARMでも良い
• Must: HDMI出力、USBホスト機能
• Want: Bluetooth 4.0以上（BLEを使う）
• Want: Raspberry Pi 3より速い、Raspberry Pi 5ほど性能は要らない
• Want: 昔のRaspberry Pi 3Bくらいの価格（5,000円くらい）

まず値段的にx86のノートPCやNUCは購入候補から外れます（中古品でも厳しい）。ARMのSBCですと、FRIENDLY ELECのNanoPi R5系（Rockcihp RK3568B, Cortex-A55 x 4）か、OKDO/Radxa ROCK 3 model C 1GB版（Rockchip RK3566, Cortex-A55 x 4）がちょうど良さそうでした。

NanoPiとROCK 3はどちらでも良かったのですが、RSコンポーネンツで容易に購入できるROCK 3 model C 1GB版に決めました。

JavaのGraphics 2Dが遅い？

ROCK 3 model CはRaspberry Pi 3 model Bを置き換えるにふさわしい製品だと思いますが、私の使い方だと1点だけ問題があって、Javaの画面描画が致命的に遅いです。5秒に1回くらいしか描画されません。このままでは使いたい目的に合いません。

最初にGPUが有効になっているか確認です。GPU使用率を/sys/devices/platform/fed60000.gpu/utilizationを見ると、無負荷のときは0、アプリ起動時で20くらいでGPUは動いています。問題なさそうです。むしろ暇しているというか余裕すらありそうです。Javaのライブラリ系orアプリ実装の問題でしょう。

次にJavaのライブラリ系を確認です。現在、画面描画のダブルバッファリングに使っているのはBufferStrategyで、BufferStrategyが返すVolatileImageのisAccelerated()はTrueを返します。OpenGLによるHW描画が使われているようです。これも問題なさそうです。残るはアプリ実装の問題ですね。

余談ですが下記のようにGraphics2D経由で確認すると、

((Graphics2D)strategy.getDrawGraphics()).getDeviceConfiguration().getImageCapabilities().isAccelerated()

なぜかisAccelerated()がFalseになります。良くわからん動きです。

Graphics2Dのアンチエイリアス機能が遅い

タイトルの通りですが、アプリ実装が原因でした。コードでいえば下記の部分です。

Graphics2D g2;

g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
g2.setRenderingHint(RenderingHints.KEY_TEXT_ANTIALIASING, RenderingHints.VALUE_TEXT_ANTIALIAS_ON);

図形描画とテキスト描画のアンチエイリアスをONにして使っていましたが、このうち図形描画のアンチエイリアスをONにすると著しく描画速度が下がることがわかりました。Raspberry Pi 3 model Bは双方のアンチエイリアスをONにしても特に問題がなかったため、気づくまで結構手間取りました。

図形描画のアンチエイリアスは今のところ見た目にさほど影響がないので、OFFにしました。テキスト描画のアンチエイリアスも描画速度に多少影響ありますが、OFFにすると見た目が悪くなりすぎるので、ONのまま使います。

問題の解決はしていませんが、回避できたのは良かったです。勢いで3つも買ってしまったROCK 3 model Cの不良在庫化を避けられました……。

volatileをnon-volatileで参照してはいけない

目次: GCC

過去の日記（2021年3月13日の日記参照）にプログラムがバグっていて未定義動作だ（つまりGCCのせいじゃない）とコメントいただいたので、C11規格を眺めていました。

C11 committee draft(N1570) 6.7.3 Type qualifiersの6に、volatileとnon-volatileを併用したときの未定義動作の記述がありました。

6.7.3 Type qualifiers

...

6
If an attempt is made to modify an object defined with a const-qualified type through use of 
an lvalue with non-const-qualified type, the behavior is undefined. If an attempt is made to 
refer to an object defined with a volatile-qualified type through use of an lvalue with 
non-volatile-qualified type, the behavior is undefined. 133)

133) This applies to those objects that behave as if they were defined with qualified types, 
even if they are never actually defined as objects in the program (such as an object at a 
memory-mapped input/output address).

（ざっくり訳）
const-qualified型で定義したオブジェクトをnon-const-qualified型の左辺値（lvalue）を使用して変更した場合、
動作は未定義です。volatile-qualified型で定義したオブジェクトを、non-volatile-qualified型の左辺値で参照した場合、
動作は未定義です。

133)
たとえプログラム内でオブジェクトとして定義されていなくても、これ（注: 上記の6のこと）は修飾された型で定義されたように
振る舞うオブジェクト（メモリマップされたI/Oアドレスにあるオブジェクトなど）に適用されます。

未定義動作ならmemmoveやmemcopyに何が起きても不思議ではないですね。C言語難しいわ……。

解像度の設定を保存する

目次: Linux

Raspberry Pi 3 Model B (以降RasPi 3B)のHDMI出力の解像度はFull HDがデフォルト設定です。今日日のディスプレイで困ることはほぼありませんが、古いアスペクト比4:3のディスプレイなど、Full HD以外の解像度で出力してほしいときが稀にあります。

RasPi 3Bに限りませんけど、X Window Systemはxrandrコマンドで解像度を手軽に変更できます。しかし解像度の設定は保存されず、セッションを終了したり再起動すると元のFull HD出力に戻ります。まあ、これはこれで誤った設定のまま固定されないというありがたい面もあるものの、普通は再起動後も解像度を維持してほしいです。

調べるとX Window Systemの設定ファイルを変更するか、autorandrコマンドで解像度を維持できるみたいです（autorandrのソースコード）。例として1024x768 60Hzの解像度で維持するやり方を挙げます。

$ apt-get install autorandr

$ xrandr -s 1024x768 --rate 60
$ autorandr --save (profile名)

設定は~/.config/autorandr/(profile名)/というディレクトリに保存されます。

autorandrとXDG autostart機能

起動時に解像度を変更している方法が気になったので調べると、XDG autostart（Desktop Application Autostart Specification）を使って実現していました。

Linuxのデスクトップ環境は実装ごとに自動起動の方法が違いますが、XDG autostartは多数のデスクトップ環境が対応している自動起動の仕組みのようです。私が使っている64bit版Raspberry Pi OSはデスクトップ環境としてLXDE (Lightweight X11 Desktop Environment)を採用していて、LXDEもXDG autostartに対応しています。

XDG autostartはデスクトップ表示の際に/etc/xdg/autostart/ディレクトリの下の設定を全部実行します。autorandrの設定は/etc/xdg/autostart/autorandr.desktopにありました。

[Desktop Entry]
Name=Autorandr
Comment=Automatically select a display configuration based on connected devices
Type=Application
Exec=/usr/bin/autorandr -c --default default
X-GNOME-Autostart-Phase=Initialization

実行されるコマンドラインのうちオプション-cはchangeの意味で、最初に見つけたprofileの解像度に変更します。オプション--defaultはdefaultという名のprofileを使うように変更する指令らしいのですが、効き目が良くわかりません。

もし複数のprofileが存在していた場合にどれが選ばれるのか気になるので、デバッグオプションを付けて実行してみましょう。

$ autorandr -c --default default --debug

fullhd (detected) (1st match) (current)
xga (detected) (2nd match)
| Differences between the two profiles:
| [Output HDMI-1] Option --mode (= `1920x1080') is `1024x768' in the new configuration
\-
Config already loaded

$ autorandr -l xga

$ autorandr -c --default default --debug

xga (detected) (1st match) (current)
fullhd (detected) (2nd match)
| Differences between the two profiles:
| [Output HDMI-1] Option --mode (= `1024x768') is `1920x1080' in the new configuration
\-
Config already loaded

こんな動作をしました。最後に利用もしくは保存したprofileが使われるみたいですね。

100万回のHello, World! - バイナリサイズを削って遊ぼう、究極編その2

目次: ベンチマーク

前回（2024年2月27日の日記参照）はループ、再帰なし、1000バイト以下で100万回のHello, World!を実施する問題に対し、バイナリサイズを極限まで削るためのアイデアをご紹介しました。

今回はバイナリ実装の説明を紹介したいと思います。

使用する命令列の説明

今回使用する100万回のHello, World!を呼ぶ命令列と処理の流れを説明します。エントリアドレスは0x983cb004なので、一番上の行から実行開始します。

    983cb004:   b9 40 42 0f 00          mov    $0xf4240,%ecx
    983cb009:   6a 01                   push   $0x1
    983cb00b:   58                      pop    %rax
    983cb00c:   6a 0e                   push   $0xe
    983cb00e:   5a                      pop    %rdx
    983cb00f:   a9 02 00 3e 00          test   $0x3e0002,%eax
    983cb014:   89 c7                   mov    %eax,%edi
    983cb016:   eb 50                   jmp    983cb068 <_start+0x68>

    983cb028:   "Hello, World!\n"

    983cb060:   0f 05                   syscall
    983cb062:   59                      pop    %rcx
    983cb063:   e2 a4                   loop   983cb009 <_start+0x9>
    
    
    ----- （★1）loop命令の条件に一致せず、983cb065に進んだ時に見える命令列
    
    983cb065:   25 00 00 be 28          and    $0x28be0000,%eax
    983cb06a:   b0 3c                   mov    $0x3c,%al
    983cb06c:   98                      cwtl
    983cb06d:   51                      push   %rcx
    983cb06e:   eb f0                   jmp    983cb060 <_start+0x60>


    ----- （★2）983cb068に飛んだ時に見える命令列

    983cb068:   be 28 b0 3c 98          mov    $0x983cb028,%esi
    983cb06d:   51                      push   %rcx
    983cb06e:   eb f0                   jmp    983cb060 <_start+0x60>

まず0x983cb004〜0x983cb016まで実行して、ジャンプ命令で0x983cb068に飛びます。上の図でいう（★2）の方です。

• 983cb068: mov: esiレジスタに"Hello, World\n"のアドレスを入れる
• 983cb06d: push: rcxレジスタを保存
• 983cb060: syscall: writeシステムコールに相当
• 983cb062: pop: syscallによってrcxレジスタが壊れるのでrcxを復帰
• 983cb063: loop: rcxレジスタが0になるまでループ

ループ100万回が終了してrcxレジスタが0になるとloop命令の次のアドレス983cb065に進みます。eaxレジスタに0x3cを入れてsyscall（exitシステムコールに相当する）するので、プログラムが終了します。

命令重ね合わせの妙

この命令列の凄いところはand命令とmov命令の重ね合わせです。アドレス0x983cb065から見たときと、アドレス0x983cb068から見たときで命令列の意味が大きく変わります。図示するとこんな感じです。

      and      mov  cwtl push  jmp
      |        |      |  |     |
<------------> <---> <> <> <--->    : アドレス983cb065から見たときの解釈
25 00 00 be 28 b0 3c 98 51 eb f0
         <------------> <> <--->    : アドレス983cb068から見たときの解釈
                |        |     |
                mov      push  jmp

この工夫によってmovとjmpの合計7バイトを重ね合わせることができていて、結果112バイトにきっちり収まっています。

$ hexdump -C 112byte.out

00000000  7f 45 4c 46 b9 40 42 0f  00 6a 01 58 6a 0e 5a a9  |.ELF.@B..j.Xj.Z.|
00000010  02 00 3e 00 89 c7 eb 50  04 b0 3c 98 00 00 00 00  |..>....P..<.....|
00000020  38 00 00 00 00 00 00 00  48 65 6c 6c 6f 2c 20 57  |8.......Hello, W|
00000030  6f 72 6c 64 21 0a 38 00  01 00 00 00 05 00 00 00  |orld!.8.........|
00000040  00 00 00 00 00 00 00 00  00 b0 3c 98 00 00 00 00  |..........<.....|
00000050  00 b0 3c 98 00 00 00 00  0f 05 59 e2 a4 25 00 00  |..<.......Y..%..|
00000060  0f 05 59 e2 a4 25 00 00  be 28 b0 3c 98 51 eb f0  |..Y..%...(.<.Q..|
00000070

$ ./112byte.out | head
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!

$ ./112byte.out | wc
1000000 2000000 14000000

$ ./112byte.out > /dev/null

最終的なバイナリはこんな感じです。動作もOKです。

なんとエラー処理もある

ループ終了後exitシステムコールを呼ぶとき、アドレス983cb06aのmov命令にて0x3c（exitシステムコールを表す番号）をalレジスタに入れてsyscall命令を実行します。もしこのmov命令のみだと、writeシステムコールがエラーを返してeaxレジスタが負の値になっていると問題が起きます。alレジスタを0x3cに書き換えても上位ビットが0ではないため、eaxレジスタとして見たとき値が0x3cになりません。よってexitシステムコールが呼ばれず終了しません。

今回の112バイト版は前後のand命令とcwtl命令によってこの問題を解決しています。loop命令を通過した後の命令列を再掲します。

    983cb065:   25 00 00 be 28          and    $0x28be0000,%eax
    983cb06a:   b0 3c                   mov    $0x3c,%al
    983cb06c:   98                      cwtl
    983cb06d:   51                      push   %rcx
    983cb06e:   eb f0                   jmp    983cb060 <_start+0x60>

ポイントは先頭の2命令です、簡単に解説します。

• and: axレジスタ相当の部分（eaxレジスタの下位16ビット）を0クリア
• cwtl: axレジスタをeaxレジスタに符号拡張

もしwriteシステムコールがエラーを返してeaxレジスタが負の値になっていたとしても、and命令がaxレジスタ相当の下位16ビットを0クリアし、cwtlで符号拡張するので必ずeaxレジスタは0x3cになる仕組みです。

この手のコードゴルフではエラー処理まで考えないことが多いですが、きれいに解決されています。ちなみに私はcwtl命令を初めて知りました。こんな命令あるんだ……。

100万回のHello, World! - バイナリサイズを削って遊ぼう、究極編その1

目次: ベンチマーク

前回（2024年2月26日の日記参照）はループ、再帰なし、1000バイト以下で100万回のHello, World!を実施する問題に対して、バイナリサイズをどこまで削れるかに挑戦しました。結果120バイトのバイナリとなりました。

今回は削減の限界値と思われる値まで達成したので、その内容を紹介したいと思います。空き地の開拓は私ですが、アセンブラの短縮に関しては私ではなくhdkさん（hdkのページ）がほぼやってくれました。結構難しいので、わかるように説明できているか怪しいです……。

バイナリの最小サイズ（削減の限界）は112バイト

正常に動作するELF形式の実行ファイルには、ELFヘッダ（64バイト）とプログラムヘッダ（56バイト）が必要です。120バイト必要に見えますが、2つのヘッダは破綻しない範囲で重ねて良いです。今のところ112バイトが最小サイズだと思われます。

ELFヘッダのなかで正しい値を維持しなければならない部分

前回紹介した通り、ELFヘッダには適当な値を入れるとエラーになって動かなくなる部分があります。プログラムヘッダも同様に制約があり、先頭のp_typeとp_flags（01 00 00 00 05 00 00 00）は変更できません。そのあとに続くp_offsetも上位バイトは変更できず、p_vaddr = p_paddr、p_filesz = p_memszでなければなりません。結構厳しいです。

これらの条件を満たせるのはe_phnum, e_shentsize, e_shnum, e_shstrndx（計8バイト）とp_type, p_flags（計8バイト）を重ねることだけだと思われます。単純な合計サイズから8バイト減った64 + 56 - 8 = 112バイトが最小サイズのはず。もし間違っていたら教えてください。私が喜びます。

削減のアイデア - プログラムヘッダの空き地p_fileszとp_memsz

前回は見落としましたが、プログラムヘッダ中に命令列を置ける空き地が1つ残っていました。p_fileszとp_memsz（どちらも8バイト）です。あまりに大きな値にするとエラーで動かなくなりますが、6バイトくらいなら何を書いても大丈夫そうです。

注意点としてはp_fileszとp_memszを同じ値にしないとエラーになることです。両方書き換えますが実行に使うのはどちらか片方だけとなるでしょう。

削減のアイデア - 命令の途中にジャンプ

RISC系のCPUを使う人からすると信じがたい動きですが、x86 CPUは命令のアラインメントがなく「命令の途中」にジャンプしても良いです。例を示しましょう。

0000: be 28 01 b0 3c: mov $0x3cb00128, %esi

この命令の4バイト目（アドレス3）にジャンプすると

0003: b0 3c: mov $0x3c, %al

という命令に見えるので、継続して実行可能。

もし命令の一部が有効な命令として解釈可能ならそのまま実行を続けられます。x86 CPUの無茶苦茶な仕様には驚きですが、今回はこの動きが役立ちます。

削減のアイデア - 4バイトジャンプの代わりにtest命令

ELFヘッダのe_identの後半（アドレス: 0x04〜0x0f、12バイト）とe_version（アドレス: 0x14〜0x17、4バイト）の間には、e_type, e_machineという書き換えてはいけない4バイトの情報があります。単純に実装するとe_identの最後に4バイトジャンプ（eb 04）を置いて飛ばせば良いです。

test命令を4バイトスキップの代わりにする例

しかし上記のようにアドレス0x000fをtest命令（a9）に置き換えますと、後続の4バイトと合わせて1命令（a9 02 00 3e 00: test $0x3e0002, %eax）とみなせます。test命令はフラグレジスタ以外には影響を及ぼさないので、a9 02 00 3e 00は実行されるものの何も効力を発揮しません。

ジャンプ命令2バイトからtest命令の先頭1バイトのみで済みますので、空き地が1バイト増加します。test命令に変更する代償はフラグレジスタの内容が破壊されることです。例えば条件分岐命令の直前などでtest命令を使うと、分岐の結果が変わる可能性があります。

削減のアイデア - デクリメント＋条件分岐の代わりにpush, pop, loop命令

100万回のループを行うときは、ebxレジスタなどcallee-saveレジスタ（関数呼び出しで値が壊れないレジスタ）に1,000,000を入れ、デクリメントし（ff cb: dec %ebx）、条件不一致ならループの先頭にジャンプ（75 xx: jne +-7bit幅ショートジャンプ）する、2命令、合計4バイトで実現するのが普通だと思います。

実はx86_64にはloop命令といってdec %ecxとjne xxを実行する命令があります。サイズは2バイト（e2 xx: loop +-7bit幅ショートループ）です。ただしecxレジスタはcallee-savedではないため、関数呼び出しやsyscallで内容が壊れます。必ずecxレジスタの保存（51: push %rcx）と復帰（59: pop %ecx）を伴うため合計サイズは4バイトで変わりません。

それなら置き換える意味がないのでは？と思うかもしれませんが、同じ4バイトでも2バイト命令2つ（dec, jne）と1バイト命令2つ＋2バイト命令1つ(push, pop, loop）を比べると、後者の方が部品が多くてより柔軟に配置できるのです。

もう1つ良い点はdec命令とjne命令は近くに配置しないといけない制約（フラグを壊す算術命令やtest命令を間に入れると動かなくなるから）がありますが、push/pop命令はloop命令から多少離れても問題ありません。これもloopの方が柔軟に配置できる理由です。

続きはまた明日書きます。

100万回のHello, World! - バイナリサイズを削って遊ぼう

目次: ベンチマーク

前回（2024年2月25日の日記参照）はループ、再帰なし、1000バイト以下で100万回のHello, World!を実施する問題に対し、アセンブラというかほぼバイナリ直書きのC言語で挑戦しました。その後、バイナリサイズを削って遊んでみたところgccのみで840バイト、stripありで520バイトとなり、バイナリでも1000バイト以下を達成しました。

今回はどこまでバイナリのサイズを切り詰められるか試してみたいと思います。ツール頼みだとこれ以上削れないと思うのでバイナリエディタで削っていきます。

バイナリの見直し

前回の私のバイナリ実装はかなり適当だったので猛者に叩きなおしてもらいました。変化点としては、

• レジスタに0x1を代入するとき、movではなくpushとpopを使う
• exitを呼ぶときwriteを呼ぶ処理を流用してmovを減らす
• アドレスが固定であることを期待して、幅を取ってたlea命令をmovに置き変える

といったところです。

const char _start[] __attribute__((section(".text"))) = {
        0xbb, 0x40, 0x42, 0x0f, 0x00, //ebx 1000000
        0x6a, 0x01, //push 0x1
        0x58, //pop rax
        0x89, 0xc7, //mov eax,edi
        0x6a, 0x0e, //push 0xe
        0x5a, //pop rdx
        0xbe, 0x1c, 0x01, 0x40, 0x00, //mov 0x4011c, esi
        0x0f, 0x05, //syscall
        0xff, 0xcb, //dec ebx
        0x75, 0xed, //jne -> push 0x1
        0x6a, 0x3c, //push 0x3c
        0xeb, 0xeb, //jmp -> pop rax
        'H', 'e', 'l', 'l', 'o', ',', ' ',
        'W', 'o', 'r', 'l', 'd', '!', '\n',
};

この改良の時点で520→512バイト（8バイト減）に改善します。素晴らしい〜。

$ gcc -static -nostdlib -Wl,-Ttext=0x400100 -Wl,--build-id=none -fno-ident a.c
/tmp/cczsMtLk.s: Assembler messages:
/tmp/cczsMtLk.s:4: Warning: ignoring changed section attributes for .text

$ ls -la a.out
-rwxr-xr-x 1 katsuhiro suzuki 832  2月 25 13:47 a.out

$ strip -s a.out
$ ls -la a.out
-rwxr-xr-x 1 katsuhiro suzuki 512  2月 25 13:47 a.out  ★8バイト改善

$ objdump -DrS a.out
(略)
0000000000400100 <.text>:
  400100:       bb 40 42 0f 00          mov    $0xf4240,%ebx
  400105:       6a 01                   push   $0x1
  400107:       58                      pop    %rax
  400108:       89 c7                   mov    %eax,%edi
  40010a:       6a 0e                   push   $0xe
  40010c:       5a                      pop    %rdx
  40010d:       be 1c 01 40 00          mov    $0x40011c,%esi
  400112:       0f 05                   syscall
  400114:       ff cb                   dec    %ebx
  400116:       75 ed                   jne    0x400105
  400118:       6a 3c                   push   $0x3c
  40011a:       eb eb                   jmp    0x400107

★ここから下はHello, World!の文字列なので命令列としては無意味

  40011c:       48                      rex.W
  40011d:       65 6c                   gs insb (%dx),%es:(%rdi)
  40011f:       6c                      insb   (%dx),%es:(%rdi)
  400120:       6f                      outsl  %ds:(%rsi),(%dx)
  400121:       2c 20                   sub    $0x20,%al
  400123:       57                      push   %rdi
  400124:       6f                      outsl  %ds:(%rsi),(%dx)
  400125:       72 6c                   jb     0x400193
  400127:       64 21 0a                and    %ecx,%fs:(%rdx)


$ ./a.out | head
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!

$ ./a.out | wc
1000000 2000000 14000000

動作確認もできました。バイナリはこんな感じです。

$ hexdump -C remove_prg_section_org.out
00000000  7f 45 4c 46 02 01 01 00  00 00 00 00 00 00 00 00  |.ELF............|
00000010  02 00 3e 00 01 00 00 00  00 01 40 00 00 00 00 00  |..>.......@.....|
00000020  40 00 00 00 00 00 00 00  40 01 00 00 00 00 00 00  |@.......@.......|
00000030  00 00 00 00 40 00 38 00  03 00 40 00 03 00 02 00  |....@.8...@.....|
00000040  01 00 00 00 04 00 00 00  00 00 00 00 00 00 00 00  |................|
00000050  00 00 40 00 00 00 00 00  00 f0 3f 00 00 00 00 00  |..@.......?.....|
00000060  e8 00 00 00 00 00 00 00  e8 00 00 00 00 00 00 00  |................|
00000070  00 10 00 00 00 00 00 00  01 00 00 00 05 00 00 00  |................|
00000080  00 01 00 00 00 00 00 00  00 01 40 00 00 00 00 00  |..........@.....|
00000090  00 01 40 00 00 00 00 00  2a 00 00 00 00 00 00 00  |..@.....*.......|
000000a0  2a 00 00 00 00 00 00 00  00 10 00 00 00 00 00 00  |*...............|
000000b0  51 e5 74 64 06 00 00 00  00 00 00 00 00 00 00 00  |Q.td............|
000000c0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
000000e0  10 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
000000f0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000100  bb 40 42 0f 00 6a 01 58  89 c7 6a 0e 5a be 1c 01  |.@B..j.X..j.Z...|
00000110  40 00 0f 05 ff cb 75 ed  6a 3c eb eb 48 65 6c 6c  |@.....u.j<..Hell|
00000120  6f 2c 20 57 6f 72 6c 64  21 0a 00 2e 73 68 73 74  |o, World!...shst|
00000130  72 74 61 62 00 2e 74 65  78 74 00 00 00 00 00 00  |rtab..text......|
00000140  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
00000180  0b 00 00 00 01 00 00 00  06 00 00 00 00 00 00 00  |................|
00000190  00 01 40 00 00 00 00 00  00 01 00 00 00 00 00 00  |..@.............|
000001a0  2a 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |*...............|
000001b0  20 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  | ...............|
000001c0  01 00 00 00 03 00 00 00  00 00 00 00 00 00 00 00  |................|
000001d0  00 00 00 00 00 00 00 00  2a 01 00 00 00 00 00 00  |........*.......|
000001e0  11 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
000001f0  01 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000200

サイズは小さいですが0データの羅列が目立ちます。削れそうな気がしてきませんか？

削れそうなもの - プログラムヘッダ、セクション（512→162バイト）

大物から削りましょう。プログラムヘッダがなぜか3つありますが2つ不要、セクションヘッダは実行には不要、セクションヘッダ削除に伴って.shstrtabも不要です。

プログラムヘッダ:
  タイプ        オフセット          仮想Addr           物理Addr
            ファイルサイズ        メモリサイズ         フラグ 整列
  LOAD           0x0000000000000000 0x0000000000400000 0x00000000003ff000  ★いらない
                 0x00000000000000e8 0x00000000000000e8  R      0x1000
  LOAD           0x0000000000000100 0x0000000000400100 0x0000000000400100
                 0x000000000000002a 0x000000000000002a  R E    0x1000
  GNU_STACK      0x0000000000000000 0x0000000000000000 0x0000000000000000  ★いらない
                 0x0000000000000000 0x0000000000000000  RW     0x10

削除データの位置は下記の図の通りです。

削除するデータ（プログラムヘッダ、セクションヘッダなど）の位置

単純に削除すると.textセクションの位置とヘッダに記載されているアドレスがズレて動かなくなりますから、

• ELFヘッダ: e_entry, e_phoff, e_phnum
• プログラムヘッダ: p_offset, p_vaddr, p_paddr, p_filesz, p_memsz

上記の値を調整します。調整後のバイナリが下記です。

$ ls -la remove_prg_section.out
-rwxr-xr-x 1 katsuhiro suzuki 162  2月 25 14:05 remove_prg_section.out

$ hexdump -C remove_prg_section.out
00000000  7f 45 4c 46 02 01 01 00  00 00 00 00 00 00 00 00  |.ELF............| ★ELFヘッダ
00000010  02 00 3e 00 01 00 00 00  78 00 40 00 00 00 00 00  |..>.....x.@.....|
00000020  40 00 00 00 00 00 00 00  40 01 00 00 00 00 00 00  |@.......@.......|
00000030  00 00 00 00 40 00 38 00  01 00 40 00 03 00 02 00  |....@.8...@.....|
00000040  01 00 00 00 05 00 00 00  60 00 00 00 00 00 00 00  |........`.......| ★プログラムヘッダ
00000050  60 00 40 00 00 00 00 00  60 00 40 00 00 00 00 00  |`.@.....`.@.....|
00000060  40 00 00 00 00 00 00 00  40 00 00 00 00 00 00 00  |@.......@.......|
00000070  00 10 00 00 00 00 00 00  bb 40 42 0f 00 6a 01 58  |.........@B..j.X| ★0x78〜: 実行する命令列
00000080  89 c7 6a 0e 5a be 94 00  40 00 0f 05 ff cb 75 ed  |..j.Z...@.....u.|
00000090  6a 3c eb eb 48 65 6c 6c  6f 2c 20 57 6f 72 6c 64  |j<..Hello, World|
000000a0  21 0a                                             |!.|
000000a2

0データの羅列が減ってだいぶスリム化しました。サイズは162バイトです。

削れそうなもの - ELFヘッダ（162→120バイト）

ELFヘッダには色々な値が並んでいますが、実行ファイルを実行（execveシステムコール）するときに全ての値をチェックしているわけではありません。これを逆手にとってELFヘッダに実行命令列やデータを詰め込むことができます。図で示した黄色い部分以外は好き勝手に変えて大丈夫です。

ELFヘッダのなかで正しい値を維持しなければならない部分

最初の空き地はe_identの後半（アドレス: 0x04〜0x0f、12バイト）とe_version（アドレス: 0x14〜0x17、4バイト）です。実行バイナリの先頭4命令、10バイト分、そのあとの2バイト分を入れます。各領域の終端2バイトはジャンプ命令に使います。そうしないと命令列ではないところまで実行してクラッシュするからからです。

★e_identに入れる分
  400100:       bb 40 42 0f 00          mov    $0xf4240,%ebx
  400105:       6a 01                   push   $0x1
  400107:       58                      pop    %rax
  400108:       89 c7                   mov    %eax,%edi

★e_versionに入れる分
  40010a:       6a 0e                   push   $0xe

次の空き地はe_shoff, e_flags, e_ehsize（アドレス: 0x28〜0x35、14バイト）です。ちょうど"Hello, World!\n"と同じ長さなので文字列を置きます。

最後の空き地はELFヘッダの終端、e_shentsize, e_shnum, e_shstrndx（アドレス: 0x3a〜0x3f、6バイト）です。ここは命令列を置くよりe_phnumの値とプログラムヘッダの先頭p_typeも値が0x01であることを利用して、プログラムヘッダを8バイト手前にずらした方が良いでしょう。命令列を置くとジャンプ命令分を除いて、4バイトしか改善できないからです。

ELFヘッダの終端とプログラムヘッダの先頭8バイトを重ねる

プログラムヘッダの方は空き地はほぼなく、ヘッダ終端のp_align（8バイト）だけ変更OKでした。ここにも命令列を置きましょう。

最後にアドレスを調整するとこんなバイナリです。120バイトになりました。当然、実行できて100万回のHello, World!を出力します。

$ hexdump -C overwrap_elfh.out
00000000  7f 45 4c 46 bb 40 42 0f  00 6a 01 58 89 c7 eb 04  |.ELF.@B..j.X....|
00000010  02 00 3e 00 6a 0e eb 50  04 00 40 00 00 00 00 00  |..>.j..P..@.....|
00000020  38 00 00 00 00 00 00 00  48 65 6c 6c 6f 2c 20 57  |8.......Hello, W|
00000030  6f 72 6c 64 21 0a 38 00  01 00 00 00 05 00 00 00  |orld!.8.........|
00000040  60 00 00 00 00 00 00 00  60 00 40 00 00 00 00 00  |`.......`.@.....|
00000050  60 00 40 00 00 00 00 00  30 00 00 00 00 00 00 00  |`.@.....0.......|
00000060  30 00 00 00 00 00 00 00  5a be 28 00 40 00 0f 05  |0.......Z.(.@...|
00000070  ff cb 75 95 6a 3c eb 93                           |..u.j<..|
00000078


$ ./overwrap_elfh.out | head
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!

$ ./overwrap_elfh.out | wc
1000000 2000000 14000000

あくまでもこのバイナリは私が使っているLinux kernel 6.1系のチェックを掻い潜って実行できるだけ、です。gdbは実行ファイルとして認識してくれませんし、readelfも大量のエラーを出します。将来のLinuxカーネルでも実行できなくなる可能性があります。

$ gdb ./remove_elf.out
GNU gdb (Debian 13.1-3) 13.1
(略)
"(略)/./remove_elf.out": not in executable format: file format not recognized

(gdb)

$ readelf -a remove_elf.out
ELF ヘッダ:
  マジック:  7f 45 4c 46 bb 40 42 0f 00 6a 01 58 89 c7 eb 04
  クラス:                            <不明: bb>
  データ:                            <不明: 40>
  Version:                           66 <unknown>
  OS/ABI:                            AROS
  ABI バージョン:                    0
  型:                                EXEC (実行可能ファイル)
  マシン:                            Advanced Micro Devices X86-64
  バージョン:                        0x50eb0e6a
  エントリポイントアドレス:          0x400004
  プログラムヘッダ始点:            0 (バイト)
  セクションヘッダ始点:              56 (バイト)
  フラグ:                            0x0
  Size of this header:               25928 (bytes)
  Size of program headers:           27756 (bytes)
  Number of program headers:         11375
  Size of section headers:           22304 (bytes)
  Number of section headers:         29295
  Section header string table index: 25708
readelf: 警告: The e_shentsize field in the ELF header is larger than the size of an ELF section header
readelf: エラー: Reading 653395680 bytes extends past end of file for セクションヘッダ
readelf: エラー: セクションヘッダが利用できません!
readelf: エラー: Too many program headers - 0x2c6f - the file is not that big

このファイルには動的セクションがありません。
readelf: エラー: Too many program headers - 0x2c6f - the file is not that big

さらにLinuxの裏をかいて削減できるような気もしますけど……、キリがないのでこれくらいにしておきます。

余談

GDBはセクションヘッダを削除した時点でELFファイルとして認識しなくなります。ジャンプ先を間違ったとき、アドレスが間違っていてSEGVするときのデバッグができずしんどいです。

ELFヘッダを書き換えるとreadelfすら訳の分からない表示になるので、デバッグがさらに辛いですね……。