-
Notifications
You must be signed in to change notification settings - Fork 0
hh4
実行バイナリの即値ヒストグラム リンクフリーですが、ここにある資料は予告なく移動削除されることがあります。
hh4 の内部構造決定に定数の分布をみたらどうか、とのhikalium さんの意見に勝手に呼応して調べてみている. 本節の内容は CC0-1.0 とします.
定数出現頻度について、即値だけならad-hoc に収集できそうだったのでワンライナーを書いた.
$ objdump --disassemble {filenames} | grep "\$0x[[:xdigit:]]*" --only-matching | cut --characters="2-" > log.log
逆アセンブル結果中の即値が 0x34 などと抽出されるので,
$ sort log.log | uniq --count | sort --reverse
こうしてみると即値ごとの出現回数ランキング上位から見られます. wc --line logs.log で全体の即値件数が分かるので, それらから割合も分かる.
課題:
- 現状の処理では負の数も全部2の補数表現で集計されているものの、byte なのかdword なのかを知らないまま処理しているので負の数を -1 などと集計するのができない (追記: mov 先のレジスタを見れば何byte を期待しているかは一応分かるものの、もはや上のようなテキスト処理では調べられなくなって手間がかかる)
目的: パッケージごとよく使われる定数値を知りたい。それらにばらつきがあるかを調べたい。
私案: 手元PC にあるリバースエンジニアリングが禁止されていない自由ソフトウエアについて、各パッケージごとに実行バイナリと共有ライブラリと静的ライブラリに分けて処理をする. するとパッケージごとバイナリの種類ごとによく使われる literal ランキングが分かるので、全体として上位にあるliteral と、そのhh4での型を抜き出す.
for packname in $( expac -Q '%n\t%L' | grep -v " \?custom" | awk '{ print $1}'); do objdump -d $(pacman -Qlq $packname) | grep "\$-\?0x[[:xdigit:]]\+" -o | cut -c "2-"> ${packname}_raw.log; sort ${packname}_raw.log | uniq -c | sort -r -n > ${packname}.csv; done
問題点: 実行バイナリと共有ライブラリが混ざっている
3種類ほどデータベースを作ってみた
私案1 を実行に移した. Arch Linuxにおいて 手元にある (a52dec から celt までのバイナリファイルがある自由ソフトウエア) 52パッケージに対してそれぞれ処理を行い, 上位10位までを抜き出した.
head -n 10 -q *.csv | awk '{print $2}' | sort | uniq -c | sort
結果
1 0x100
1 0x1000
1 0x11
1 0x12
1 0x14
1 0x16
1 0x2000
1 0x2710
1 0x2a
1 0x2f
1 0x38
1 0x3d
1 0x3f
1 0x40
1 0x4000
1 0x431bde82d7b634db
1 0x47
1 0x48
1 0x49
1 0x5306
1 0x5f
1 0x65
1 0x69
1 0x7fff
1 0x80
1 0x9
1 0x930
1 0x96
1 0xe
1 0xf0
1 0xf4240
1 0xfe00fe00
1 0xff
1 0xff00ff00
1 0xffff
1 0xffffff80
1 0xffffffb5
1 0xfffffffe
1 0xffffffff00000000
2 0x73
2 0xffffffea
2 0xfffffffffffffff0
3 0x1f
4 0x50
4 0x6
4 0x7
4 0xc
4 0xf
5 0x28
5 0x30
9 0xa
9 0xffffffffffffffff
14 0x5
27 0x18
28 0x20
33 0xffffffff
34 0x10
42 0x3
43 0x4
49 0x2
51 0x0
51 0x8
52 0x1
パッケージごとの傾向が似通っているのでは？
H8300-GCC-hh4.md 参照
hh4a lv2 では頻度の高いデータを特別扱いしている。それらが実際に頻出か調べた。 全体で 2182179 件あることに留意、 データベースの生データは encoding-db-data.md 参照
出現回数 即値
2793 0x200
725 0x3ff
4773 0x400
216 0x7ff
1684 0x800
878 0xfff
3685 0x1000
246 0x1fff
1385 0x2000
149 0x3fff
1340 0x4000
621 0x7fff
1826 0x8000
4093 0xffff
1756 0x10000
0x1fff 0x3fff あたりは後回しでもよいかもしれない
全体で 2182179 件あったうち、2000件以上のアイテムに関してどの型が優先的に出てくるか調べた
データベースの生データは encoding-db-data.md 参照
出現回数 値 hh4 で表わしたときのビット数
380094 0x1 4
349622 0x0 4
161729 0x8 8
106863 0x2 4
70805 0x4 4
69480 0x3 4
57443 0x10 8
42789 0x5 4
42072 0x18 8
40679 0x20 8
37996 0xffffffff 40+8?
26322 0xffffffffffffffff ???
25814 0x7 8
22708 0x28 8
22167 0x6 4
18071 0x40 12
17814 0xa 8
17781 0xf 8
16730 0x30 8
14177 0x1f 8
13744 0x38 8
13012 0xc 8
11195 0x9 8
10422 0x48 12
9551 0x3f 8
9499 0x80 12
9401 0xb 8
7000 0xd 8
6858 0xff 12
6762 0x50 12
6672 0x58 12
6566 0x11 8
5984 0xe 8
5958 0x68 12
5464 0x100 12
5140 0x2f 8
5025 0xfffffffe 40+8?
4851 0x14 8
4773 0x400 16
4660 0x12 8
4114 0x78 12
4093 0xffff 24
4025 0x19 8
3868 0x13 8
3860 0x15 8
3721 0x60 12
3685 0x1000 24
3643 0x17 8
3619 0x16 8
3448 0x1c 8
3359 0xfffffffffffffff8 ???
3261 0xa8 8
3214 0x7f 12
3201 0x2b 8
3197 0xfffffffc 40+8?
3157 0x2e 8
3093 0x88 12
3024 0x7fffffff 40+8?
3020 0x1e 8
3010 0xffffffea 40+8?
3001 0x2d 8
2954 0xd8 12
2895 0xfffffff4 40+8?
2876 0xfffffffd 40+8?
2843 0x2a 8
2827 0x98 12
2793 0x200 12
2744 0x64 12
2699 0x1d 8
2670 0x22 8
2650 0x65 12
2605 0x70 12
2556 0xc8 12
2547 0x29 8
2430 0x1a 12
2313 0x24 8
2262 0xb8 12
2259 0xfffffffb 40+8?
2063 0x21 8
2059 0x3a 12
2040 0x2c 8
2034 0x73 12
// SPDX-License-Identifier: CC0-1.0
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int test(void);
// value (v) は hh4 で何bit で表わされるか?
// TODO: 今のところ unsigned long long のみ対応
long long hh4_num2bits(unsigned long long value) {
if (value <= 6) {
return 4;
}
if (value <= 0x3f) {
return 8;
}
if (value <= 0x1ff) {
return 12;
}
if (value <= 0xfff) {
return 16;
}
// extended
long long bits = (long long)(log2l(value)/4) + 1;
return 4 + hh4_num2bits(bits) + bits*4;
}
#define expect(a, b) if ((a) != (b)) { fprintf(stderr, "Test Failed: %Ld, %Ld\n", (a), (b)); }
int main(int argc, const char **argv) {
if (argc < 2) {
printf("Usage: %s filename\n", argv[0]);
exit(1);
}
FILE *fp = fopen(argv[1], "r");
if (fp == NULL) {
puts("fopen failed");
exit(1);
}
long long sum = 0;
test();
puts("出現数\t即値\tbit数\t出現数*bit数");
while (!feof(fp)) {
long long cnt = 0; // 出現回数
unsigned long long val = 0; // 即値
long long contribution = 0; // 出現回数 * hh4_num2bits(val)
fscanf(fp, "%Ld\t%Lx\n", &cnt, &val);
contribution = cnt * hh4_num2bits(val);
sum += contribution;
// それぞれの即値の結果を見たいときにコメントアウト
// printf("%Ld\t0x%Lx\t%Ld\t%Ld\n", cnt, val, hh4_num2bits(val), contribution);
}
printf("sum: %Ld bits\n", sum);
fclose(fp);
return 0;
}
// テスト
int test(void) {
expect(4, hh4_num2bits(6))
expect(8, hh4_num2bits(7))
expect(8, hh4_num2bits(0x3f))
expect(12, hh4_num2bits(0x40))
expect(12, hh4_num2bits(0x1ff))
expect(16, hh4_num2bits(0x200))
expect(16, hh4_num2bits(0xfff))
expect(24, hh4_num2bits(0x1000))
expect(24, hh4_num2bits(0xffff))
expect(28, hh4_num2bits(0x10000))
expect(28, hh4_num2bits(0xfffff))
expect(32, hh4_num2bits(0x100000))
expect(32, hh4_num2bits(0xffffff))
return 0;
}これでおそらくエンコーディング方式の効率性を定量的に比較できるようになる (無論簡単な分布であればそれをtable にmap してしまうのが一番効率よくなるが, そうではなくある程度 "実装が簡単で拡張性がある" 中でこの値が小さいほうがいいかなと)
- 入力1:
{定数分布 as 上の実験で書いたファイルとして定数分布を格納}をコマンドライン引数 - 入力2: エンコーディングフォーマットにおいて 値 → 使用する bit数 の関係
hh4_num2bits() - 出力: 定数分布を全て表すのに必要なbit数の総和
(再掲)
// SPDX-License-Identifier: CC0-1.0
long long hh4_num2bits(unsigned long long value) {
if (value <= 6) {
return 4;
}
if (value <= 0x3f) {
return 8;
}
if (value <= 0x1ff) {
return 12;
}
if (value <= 0xfff) {
return 16;
}
// extended
long long bits = (long long)(log2l(value)/4) + 1;
return 4 + hh4_num2bits(bits) + bits*4;
}
拡張モードを一度使うだけで済む範囲なら使う回数は少ないほうが優れている
hh4_num2bits となっている箇所を leb_num2bits に置き換えてコンパイル
// SPDX-License-Identifier: CC0-1.0
long long leb_num2bits(unsigned long long value) {
const int k = 4;
unsigned long long v;
// TODO: 今のところ unsigned long long のみ対応
v = value;
if (v == 0) {
return k+1;
}
long long bits = ((long long)(log2l(v)/k)+1)*(k+1);
return bits;
}k というパラメータを導入。 [次の1バイトに続くかのflag 1 bit] [内容 k bits] のくりかえし
(./leb を実行する際には const int k = 3; の欄を k = 3 や k = 4 とする)
encoding-db-data.md の5行目最後の1行を除くフィイルを abcdb/integrated.csv に保存して
$ ./hh4 abcdb/integrated.csv
$ ./leb abcdb/integrated.csv
defgdb-integrated.md の5行目以降のデータを defgdb/integrated.csv に保存して
$ ./hh4 defgdb/integrated.csv
$ ./leb defgdb/integrated.csv
libdb-integrated.md の4行目以降のデータを libdb/integrated.csv に保存して
$ ./hh4 libdb/integrated.csv
$ ./leb libdb/integrated.csv
結果(定数を全て表すのに必要なbit数の総和)は以下の通り. 異なる列の値同士は比較できるが、異なる行同士の値は比較できないことに注意。
| data | hh4a lv1 | LEB k=3 | LEB k=4 |
|---|---|---|---|
| abc | 24278356 | 24449236 | 24394820 |
| defg | 311949820 | 314540364 | 313195470 |
| lib | 95001436 | 95218060 | 95361800 |
l = 4 bit刻みなのを変化させてみた.
| data | hh4a lv1 l = 4 | hh4a lv1 l = 8 |
|---|---|---|
| abc | 24278356 | 24070196 |
| defg | 311949820 | 309855436 |
| lib | 95001436 | 93815964 |
l = 8 が最良？
long long hh4_k_num2bits(unsigned long long value) {
const int l = 8;
if (value <= 6) {
return 4;
}
if (value <= 0x3f) {
return 8;
}
if (value <= 0x1ff) {
return 12;
}
if (value <= 0xfff) {
return 16;
}
long long bits = (long long)(log2l(value)/l) + 1;
return 4 + hh4_num2bits(bits) + bits*l;
}