無線モジュールを扱ってると「シリアル接続経由でATコマンドで制御する」ようなデバイスをよく相手にするが、そういうのは大体コードがバタ臭くなる。
Serial.printf("AT+CFM=%d\r\n", _cfm);
Serial.printf("AT+JOIN=1:0:%d:0\r\n", _timeout);
Serial.printf("AT+SEND=%d:%s\r\n", _form, _hexstr);
書き捨てではまあこういう記法でも良いのだが、ライブラリ化して抽象化して再利用できるように整理したいとき、流石にベタのプリント文がずらずら並ぶのは面白くない。例えばある無線モジュールには以下のATコマンドが実装されているが、その全てに対応するインタフェースメソッドを整備する時、その内部実装構造はどうするべきだろう？
AT+ADDMULC AT+ADR AT+ALIAS AT+APIVER AT+APPEUI AT+APPKEY AT+APPSKEY
AT+ARSSI AT+ATM AT+BAND AT+BANDWIDTH AT+BAT AT+BAUD AT+BFREQ AT+BGW
AT+BLEMAC AT+BOOT AT+BOOTSTATUS AT+BOOTVER AT+BTIME AT+BUILDTIME
AT+CAD AT+CERTIF AT+CFM AT+CFS AT+CHE AT+CHS AT+CLASS AT+CLIVER
AT+CODINGRATE AT+CRYPIV AT+CW AT+DCS AT+DEVADDR AT+DEVEUI AT+DR
AT+ENCKEY AT+ENCRY AT+FIXLKENGTHPAYLOAD AT+HWID AT+HWMODEL AT+IQINVER
AT+JN1DL AT+JN2DL AT+JOIN AT+LBT AT+LBTRSSI AT+LBTSCANTIME AT+LINKCHECK
AT+LOCK AT+LPM AT+LPMLVL AT+LPSEND AT+LSTMULC AT+LTIME AT+MASK
AT+MCROOTKEY AT+NETID AT+NJM AT+NJS AT+NWKSKEY AT+NWM AT+P2P AT+PBR
AT+PBW AT+PCR AT+PCRYPT AT+PFDEV AT+PFREQ AT+PGSLOT AT+PKEY AT+PNM
AT+PPL AT+PREAMBLELENGTH AT+PRECV AT+PSEND AT+PSF AT+PTP AT+PWORD
AT+RECV AT+REPOINFO AT+RESET AT+RETY AT+RFFREQUENCY AT+RMVMULC AT+RSSI
AT+RUN AT+RX1DL AT+RX2DL AT+RX2DR AT+RX2FQ AT+SEND AT+SLEEP AT+SN
AT+SNR AT+SPREADINGFACTOR AT+SYMBOLTIMEOUT AT+SYNCWORD AT+SYSV
AT+TCONF AT+TIMEREQ AT+TOFF AT+TRSSI AT+TRTH AT+TRX AT+TTH AT+TTONE
AT+TTX AT+TXOUTPUTPOWER AT+TXP AT+VER AT+VERSION ATE ATR ATZ AT
この例の場合、全部をベタで文字列化すると（それぞれの NUL終端を含めて）約1KiB強のスペースを消費するはずだ。だがほとんどのATコマンドはAT+というプレフィクスで始まるので、これを共通化するだけでもスペース効率が上がりそうに見える。さらによく見るとAT+BやAT+Rも複数回出現する。これらをうまく圧縮してやればコードスペース制約が厳しいマイコンにも優しくならないだろうか、というのが本書の主題である。
前方重複一致文字列圧縮
ATコマンド文字列の「途中の重複文字列」圧縮は複雑になるので割愛し、文字列前方の重複一致圧縮だけに絞って考察しよう。例えば以下の三つのコマンドがある。これらをメモリ上でどのように表現すべきだろうか。
AT+BOOT
AT+BOOTSTATUS
AT+BOOTVER
三つのコマンドはいずれもAT+BOOTで始まるため、構文解析木はこうなるだろう。\は分岐、$は文字列終端の意味だ。
AT+BOOT
\ $
\ STATUS $
\ VER $
この構文解析木から目的の文字列を取り出すには、それぞれの$から左の根に向かって木構造を辿れば、逆順の文字列が取り出せることは直感的に分かる。途中で\に遭遇したら、それが指し示す分岐点に文字取り出しポインタをジャンプさせれば良い。するとこの木構造は以下に示すようなメモリ構造になっていれば良いのではと考えられる。ここでの数値はメモリ配列の項番を指す。
| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|
| A| T| +| B| O| O| T| S| T| A| T| U| S|
|13|14|15|16|
| 6| V| E| R|
開始位置
6 <= "AT+BOOT"
12 <= "AT+BOOTSTATUS"
16 <= "AT+BOOTVER"
AT+BOOTはプレフィクスであると同時に、他のコマンド文字列に完全に埋まっているため実際に必要な文字列情報はAT+BOOTSTATUSとAT+BOOTVERだけだ。そしてAT+BOOTの末尾が6であることを用いて、AT+BOOTVERは6VERにエンコードできることに思い至る。結果としてこれは、元の文字列が7+13+10=30文字だったのが13+4=17文字に圧縮できることを示唆する。
さてこの文字はどのようなメモリ表現にすべきだろうか。元の ASCII文字そのものと、項番をそのまま記録してかつ両者が区別できるようにするには 9ビット以上のメモリ幅が必要だ。しかしATコマンド表を眺めると（英字は全て大文字統一とするなら）29種類の ASCII文字コードしか出現しない。すると項番が256-29=227未満であれば、両者をまとめて 8bit幅の1文字にまとめることができるはずだ。従ってこの木構造辞書メモリ配列の文字コードは、次のように定義できる。
0-226 : 項番
227 : '+'
228 : '1'
229 : '2'
230-255 : 'A'-'Z'
この考え方でデコーダー関数を書いてみよう。文字列の終端位置を引数として受け取り、木構造テーブルを遡り、逆順に現れる文字を内部バッファに溜めて最後に文字列開始位置のポインタを返却する。なお木構造テーブルの根0に項番が達したらループを終了させたいので、実際に使う項番は「目的の文字位置+1」を用いた方が好都合だ。__CMD_ATX_CHARS_TOPは 227を保持している定数である。
char* get_cmd_at_strptr (int _idx) {
static char _buff[__CMD_ATX_LENGTH + 1] = {};
uint8_t _p = __CMD_ATX_LENGTH;
while (_idx) {
uint8_t _c = __CMD_AT_TABLE[--_idx];
if (_c < __CMD_ATX_CHARS_TOP) { _idx = _c; continue; }
_c -= __CMD_ATX_CHARS_TOP;
if (_c == 0 ) { _c = '+'; }
else if (_c >= 3 ) { _c += 'A' - 3; }
else { _c += '0'; }
_buff[--_p] = _c;
}
return &_buff[_p];
}
このデコーダー関数がうまく動作するには、与える引数としての項番に制限はないが、処理中の文字列左端に現れる項番が__CMD_ATX_CHARS_TOP未満であることが確実でなければならない。つまりそのような木構造テーブルメモリ配列を記述できるかが要点になる。
辞書メモリテーブルのエンコード
この手のテキスト解析処理はperlにやらせるのが手軽だ。まずATコマンドを保持する配列を作り、出現するコマンド数と ASCII文字種数を調べておく。
#!/usr/bin/env perl
use strict;
use warnings;
use Data::Dumper;
my $command_table = <<__CMD;
AT+ADDMULC AT+ADR AT+ALIAS AT+APIVER AT+APPEUI AT+APPKEY AT+APPSKEY AT+ARSSI
AT+ATM AT+BAND AT+BANDWIDTH AT+BAT AT+BAUD AT+BFREQ AT+BGW AT+BLEMAC AT+BOOT
AT+BOOTSTATUS AT+BOOTVER AT+BTIME AT+BUILDTIME AT+CAD AT+CERTIF AT+CFM AT+CFS
AT+CHE AT+CHS AT+CLASS AT+CLIVER AT+CODINGRATE AT+CRYPIV AT+CW AT+DCS
AT+DEVADDR AT+DEVEUI AT+DR AT+ENCKEY AT+ENCRY AT+FIXLKENGTHPAYLOAD AT+HWID
AT+HWMODEL AT+IQINVER AT+JN1DL AT+JN2DL AT+JOIN AT+LBT AT+LBTRSSI
AT+LBTSCANTIME AT+LINKCHECK AT+LOCK AT+LPM AT+LPMLVL AT+LPSEND AT+LSTMULC
AT+LTIME AT+MASK AT+MCROOTKEY AT+NETID AT+NJM AT+NJS AT+NWKSKEY AT+NWM AT+P2P
AT+PBR AT+PBW AT+PCR AT+PCRYPT AT+PFDEV AT+PFREQ AT+PGSLOT AT+PKEY AT+PNM
AT+PPL AT+PREAMBLELENGTH AT+PRECV AT+PSEND AT+PSF AT+PTP AT+PWORD AT+RECV
AT+REPOINFO AT+RESET AT+RETY AT+RFFREQUENCY AT+RMVMULC AT+RSSI AT+RUN
AT+RX1DL AT+RX2DL AT+RX2DR AT+RX2FQ AT+SEND AT+SLEEP AT+SN AT+SNR
AT+SPREADINGFACTOR AT+SYMBOLTIMEOUT AT+SYNCWORD AT+SYSV AT+TCONF AT+TIMEREQ
AT+TOFF AT+TRSSI AT+TRTH AT+TRX AT+TTH AT+TTONE AT+TTX AT+TXOUTPUTPOWER
AT+TXP AT+VER AT+VERSION ATE ATR ATZ AT
__CMD
my @command = ($command_table =~ m{(\S+)}gmo);
my %c; grep { $c{$_}++; } split //, join '', @command;
my $CHARS_LIST = join '', sort keys %c;
my $CMD_ATX_CHARS = length $CHARS_LIST;
my $CMD_ATX_CHARS_TOP = 256 - $CMD_ATX_CHARS;
my $CMD_ATX_LENGTH = 0;
次にこのATコマンド文字列をどういう順番でメモリ配列に格納していくかを思考する。ハッシュ配列%cntは全ての（各先頭からの）部分文字列ごとの出現回数をカウントし、ハッシュ配列%dicは部分文字列がどのATコマンドに由来するかを記憶・判定する。ここで@command = sortは単純に ATコマンドを ASCII辞書定義の逆順に並べ替えているが、ここに色々手を加えることでこの後の圧縮率がさまざまに変化する。また$CMD_ATX_LENGTHは最も長いATコマンド文字列長（すなわち逆順バッファに必要な定義長）を記録する。
{
my(%dic, %cnt);
@command = sort {$b cmp $a} @command;
foreach (@command) {
$CMD_ATX_LENGTH = length $_ if $CMD_ATX_LENGTH < length $_;
$cnt{$_} = 0;
if (exists $dic{$_}) { $cnt{$dic{$_}}++; next; }
for (my $i = 3; $i < length $_; $i++) {
my $key = substr $_, 0, $i;
if (exists $dic{$key}) { $cnt{$dic{$key}}++; }
else { $dic{$key} = $_; $cnt{$dic{$key}} = 1; }
}
}
my @d; while (my($k, $v) = each %cnt) {
push @d, sprintf "%3d,%s", $v, $k;
}
@d = sort { substr($b, 0, 3) cmp substr($a, 0, 3)
or substr($a, 4) cmp substr($b, 4); } @d;
# print Dumper \@d;
@command = map {(undef, $_) = split /,/, $_; $_; } @d;
}
途中のコメントアウトされたデバッグ表示文は、参照解析後の一時的配列@dの内容を表示するが、これは文字列として"参照回数,ATコマンド"を保持しており、その降順で全体をソートしていることを視覚化し、確認できる。
# print Dumper \@d;
$VAR1 = [
'106,AT+VERSION',
' 17,AT+RX2FQ',
' 16,AT+PWORD',
' 12,AT+TXP',
' 11,AT+CW',
' 10,AT+BUILDTIME',
' 9,AT+ATM',
' 9,AT+SYSV',
' 8,AT+LTIME',
# 中略
' 0,AT+VER',
' 0,ATE',
' 0,ATR',
' 0,ATZ'
];
以上で並べ替えられたATコマンド列を、二巡目のパスで構文解析し、メモリ配列@dtableを生成する。それぞれの文字列の終端位置はハッシュ配列%headsに記録され、後で#define定義列を生成するのに使われる。また使用される項番が$CMD_ATX_CHARS_TOPを超えないかもここで確認され、違反していれば中断する。
my(@dtable, %heads); my $max_idx = 0;
{
my(%dic);
foreach (@command) {
my $skip = 0;
for (my $i = 1; $i <= length $_; $i++) {
my $key = substr $_, 0, $i;
if (exists $dic{$key}) { $skip = $dic{$key}; }
else {
if ($skip) {
die "error: $_ TOP <= $skip\n"
if $CMD_ATX_CHARS_TOP <= $skip;
$max_idx = $skip if $max_idx < $skip;
push @dtable, $skip; $skip = 0;
}
my $c = substr $_, $i - 1, 1;
$c = $CMD_ATX_CHARS_TOP + index $CHARS_LIST, $c;
push @dtable, $c;
$dic{$key} = scalar @dtable;
}
}
$heads{$_} = $dic{$_};
}
}
以上を通過すれば必要な情報は出揃うので、それらをC言語ヘッダ／ソースコードの書式で出力する。#defineテーブル出力は先に挙げたデコーダー関数と等価のコードで辞書メモリ中のATコマンド文字列を復元し、コメント文に添えることで誤りがないか確認できるようにしている。
print "#pragma onece\n";
printf "// command_strings=%d\n", length $command_table;
printf "// commands=%d\n", scalar @command;
printf "// dic_size=%d\n", scalar @dtable;
printf "// max_idx=%d\n", $max_idx;
printf "// __CHARS_LIST=\"%s\"\n\n", $CHARS_LIST;
printf "#define __CMD_ATX_CHARS %3d\n", $CMD_ATX_CHARS;
printf "#define __CMD_ATX_CHARS_TOP %3d\n", $CMD_ATX_CHARS_TOP;
printf "#define __CMD_ATX_LENGTH %3d\n\n", $CMD_ATX_LENGTH;
{
foreach (sort keys %heads) {
my $idx = $heads{$_};
my(@str, $def);
s{\+}{_};
printf "#define CMD_%-22s%3d ", $_, $idx;
while ($idx) {
my $c = $dtable[--$idx];
if ($c < $CMD_ATX_CHARS_TOP) { $idx = $c; next; }
$c -= $CMD_ATX_CHARS_TOP;
if ($c == 0) { $c = '+'; }
elsif ($c >= 3) { $c = chr($c + 62); } # 63 <= 'A' - 3
else { $c = chr($c + 48); } # 48 <= '0'
unshift @str, $c;
}
printf "/* %-20s */\n", join '', @str;
}
}
__CMD_AT_TABLE辞書メモリテーブルは、Arduino環境での SRAM消費を削減してプログラムコード領域に格納するためのPROGMEM属性を添えた。
{
print "\nconst static uint8_t __CMD_AT_TABLE[] PROGMEM = {";
my $fold = 0;
foreach (@dtable) {
printf "\n/* %3d */ ", $fold if ($fold) % 10 == 0;
print $fold++ ? ", " : " ";
printf "%3d", $_;
}
print "\n};\n";
}
__CMD_AT_LISTテーブルは動作上は本来必要ないものだが、Arduinoスケッチでの全文デコード出力テストのために用意しておく。中身は先の#defineで定義された参照項番の列挙に過ぎない。
{
print "\nconst static int __CMD_AT_LIST[] PROGMEM = {";
my $fold = 0;
foreach (sort keys %heads) {
printf "\n/* %3d */ ", $fold if ($fold) % 10 == 0;
print $fold++ ? ", " : " ";
printf "%3d", $heads{$_};
}
print "\n};\n";
}
print "\n/* end of header */\n";
1;
__END__
最終的な標準出力ファイル結果は以下の通り。
#pragma onece
// command_strings=1067
// commands=116
// dic_size=561
// max_idx=201
// __CHARS_LIST="+12ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define __CMD_ATX_CHARS 29
#define __CMD_ATX_CHARS_TOP 227
#define __CMD_ATX_LENGTH 20
#define CMD_AT 2 /* AT */
#define CMD_AT_ADDMULC 211 /* AT+ADDMULC */
#define CMD_AT_ADR 133 /* AT+ADR */
#define CMD_AT_ALIAS 216 /* AT+ALIAS */
#define CMD_AT_APIVER 221 /* AT+APIVER */
#define CMD_AT_APPEUI 225 /* AT+APPEUI */
#define CMD_AT_APPKEY 229 /* AT+APPKEY */
#define CMD_AT_APPSKEY 61 /* AT+APPSKEY */
#define CMD_AT_ARSSI 234 /* AT+ARSSI */
#define CMD_AT_ATM 43 /* AT+ATM */
#define CMD_AT_BAND 136 /* AT+BAND */
#define CMD_AT_BANDWIDTH 141 /* AT+BANDWIDTH */
#define CMD_AT_BAT 543 /* AT+BAT */
#define CMD_AT_BAUD 100 /* AT+BAUD */
#define CMD_AT_BFREQ 239 /* AT+BFREQ */
#define CMD_AT_BGW 242 /* AT+BGW */
#define CMD_AT_BLEMAC 248 /* AT+BLEMAC */
#define CMD_AT_BOOT 69 /* AT+BOOT */
#define CMD_AT_BOOTSTATUS 255 /* AT+BOOTSTATUS */
#define CMD_AT_BOOTVER 72 /* AT+BOOTVER */
#define CMD_AT_BTIME 260 /* AT+BTIME */
#define CMD_AT_BUILDTIME 39 /* AT+BUILDTIME */
#define CMD_AT_CAD 263 /* AT+CAD */
#define CMD_AT_CERTIF 269 /* AT+CERTIF */
#define CMD_AT_CFM 545 /* AT+CFM */
#define CMD_AT_CFS 144 /* AT+CFS */
#define CMD_AT_CHE 547 /* AT+CHE */
#define CMD_AT_CHS 147 /* AT+CHS */
#define CMD_AT_CLASS 273 /* AT+CLASS */
#define CMD_AT_CLIVER 153 /* AT+CLIVER */
#define CMD_AT_CODINGRATE 283 /* AT+CODINGRATE */
#define CMD_AT_CRYPIV 289 /* AT+CRYPIV */
#define CMD_AT_CW 29 /* AT+CW */
#define CMD_AT_DCS 292 /* AT+DCS */
#define CMD_AT_DEVADDR 297 /* AT+DEVADDR */
#define CMD_AT_DEVEUI 106 /* AT+DEVEUI */
#define CMD_AT_DR 75 /* AT+DR */
#define CMD_AT_ENCKEY 301 /* AT+ENCKEY */
#define CMD_AT_ENCRY 81 /* AT+ENCRY */
#define CMD_AT_FIXLKENGTHPAYLOAD 319 /* AT+FIXLKENGTHPAYLOAD */
#define CMD_AT_HWID 322 /* AT+HWID */
#define CMD_AT_HWMODEL 114 /* AT+HWMODEL */
#define CMD_AT_IQINVER 330 /* AT+IQINVER */
#define CMD_AT_JN1DL 334 /* AT+JN1DL */
#define CMD_AT_JN2DL 158 /* AT+JN2DL */
#define CMD_AT_JOIN 119 /* AT+JOIN */
#define CMD_AT_LBT 84 /* AT+LBT */
#define CMD_AT_LBTRSSI 339 /* AT+LBTRSSI */
#define CMD_AT_LBTSCANTIME 92 /* AT+LBTSCANTIME */
#define CMD_AT_LINKCHECK 348 /* AT+LINKCHECK */
#define CMD_AT_LOCK 352 /* AT+LOCK */
#define CMD_AT_LPM 161 /* AT+LPM */
#define CMD_AT_LPMLVL 164 /* AT+LPMLVL */
#define CMD_AT_LPSEND 169 /* AT+LPSEND */
#define CMD_AT_LSTMULC 359 /* AT+LSTMULC */
#define CMD_AT_LTIME 54 /* AT+LTIME */
#define CMD_AT_MASK 363 /* AT+MASK */
#define CMD_AT_MCROOTKEY 179 /* AT+MCROOTKEY */
#define CMD_AT_NETID 368 /* AT+NETID */
#define CMD_AT_NJM 549 /* AT+NJM */
#define CMD_AT_NJS 182 /* AT+NJS */
#define CMD_AT_NWKSKEY 374 /* AT+NWKSKEY */
#define CMD_AT_NWM 65 /* AT+NWM */
#define CMD_AT_P2P 377 /* AT+P2P */
#define CMD_AT_PBR 551 /* AT+PBR */
#define CMD_AT_PBW 185 /* AT+PBW */
#define CMD_AT_PCR 188 /* AT+PCR */
#define CMD_AT_PCRYPT 191 /* AT+PCRYPT */
#define CMD_AT_PFDEV 381 /* AT+PFDEV */
#define CMD_AT_PFREQ 196 /* AT+PFREQ */
#define CMD_AT_PGSLOT 387 /* AT+PGSLOT */
#define CMD_AT_PKEY 391 /* AT+PKEY */
#define CMD_AT_PNM 394 /* AT+PNM */
#define CMD_AT_PPL 397 /* AT+PPL */
#define CMD_AT_PREAMBLELENGTH 409 /* AT+PREAMBLELENGTH */
#define CMD_AT_PRECV 124 /* AT+PRECV */
#define CMD_AT_PSEND 413 /* AT+PSEND */
#define CMD_AT_PSF 199 /* AT+PSF */
#define CMD_AT_PTP 416 /* AT+PTP */
#define CMD_AT_PWORD 22 /* AT+PWORD */
#define CMD_AT_RECV 419 /* AT+RECV */
#define CMD_AT_REPOINFO 426 /* AT+REPOINFO */
#define CMD_AT_RESET 430 /* AT+RESET */
#define CMD_AT_RETY 96 /* AT+RETY */
#define CMD_AT_RFFREQUENCY 441 /* AT+RFFREQUENCY */
#define CMD_AT_RMVMULC 448 /* AT+RMVMULC */
#define CMD_AT_RSSI 452 /* AT+RSSI */
#define CMD_AT_RUN 455 /* AT+RUN */
#define CMD_AT_RX1DL 459 /* AT+RX1DL */
#define CMD_AT_RX2DL 553 /* AT+RX2DL */
#define CMD_AT_RX2DR 202 /* AT+RX2DR */
#define CMD_AT_RX2FQ 16 /* AT+RX2FQ */
#define CMD_AT_SEND 463 /* AT+SEND */
#define CMD_AT_SLEEP 468 /* AT+SLEEP */
#define CMD_AT_SN 204 /* AT+SN */
#define CMD_AT_SNR 205 /* AT+SNR */
#define CMD_AT_SPREADINGFACTOR 483 /* AT+SPREADINGFACTOR */
#define CMD_AT_SYMBOLTIMEOUT 495 /* AT+SYMBOLTIMEOUT */
#define CMD_AT_SYNCWORD 502 /* AT+SYNCWORD */
#define CMD_AT_SYSV 48 /* AT+SYSV */
#define CMD_AT_TCONF 507 /* AT+TCONF */
#define CMD_AT_TIMEREQ 514 /* AT+TIMEREQ */
#define CMD_AT_TOFF 518 /* AT+TOFF */
#define CMD_AT_TRSSI 522 /* AT+TRSSI */
#define CMD_AT_TRTH 525 /* AT+TRTH */
#define CMD_AT_TRX 127 /* AT+TRX */
#define CMD_AT_TTH 555 /* AT+TTH */
#define CMD_AT_TTONE 529 /* AT+TTONE */
#define CMD_AT_TTX 130 /* AT+TTX */
#define CMD_AT_TXOUTPUTPOWER 541 /* AT+TXOUTPUTPOWER */
#define CMD_AT_TXP 26 /* AT+TXP */
#define CMD_AT_VER 6 /* AT+VER */
#define CMD_AT_VERSION 10 /* AT+VERSION */
#define CMD_ATE 557 /* ATE */
#define CMD_ATR 559 /* ATR */
#define CMD_ATZ 561 /* ATZ */
const static uint8_t __CMD_AT_TABLE[] PROGMEM = {
/* 0 */ 230, 249, 227, 251, 234, 247, 248, 238, 244, 243
/* 10 */ , 3, 247, 253, 229, 235, 246, 3, 245, 252, 244
/* 20 */ , 247, 233, 3, 249, 253, 245, 3, 232, 252, 3
/* 30 */ , 231, 250, 238, 241, 233, 249, 238, 242, 234, 3
/* 40 */ , 230, 249, 242, 3, 248, 254, 248, 251, 3, 241
/* 50 */ , 249, 238, 242, 234, 41, 245, 245, 248, 240, 234
/* 60 */ , 254, 3, 243, 252, 242, 31, 244, 244, 249, 251
/* 70 */ , 234, 247, 3, 233, 247, 3, 234, 243, 232, 247
/* 80 */ , 254, 50, 231, 249, 248, 232, 230, 243, 249, 238
/* 90 */ , 242, 234, 12, 234, 249, 254, 31, 230, 250, 233
/* 100 */ , 74, 234, 251, 234, 250, 238, 3, 237, 252, 242
/* 110 */ , 244, 233, 234, 241, 3, 239, 244, 238, 243, 18
/* 120 */ , 247, 234, 232, 251, 24, 247, 253, 24, 249, 253
/* 130 */ , 41, 233, 247, 98, 243, 233, 252, 238, 233, 249
/* 140 */ , 237, 28, 235, 248, 28, 237, 248, 28, 241, 238
/* 150 */ , 251, 234, 247, 116, 243, 229, 233, 241, 50, 245
/* 160 */ , 242, 241, 251, 241, 160, 248, 234, 243, 233, 3
/* 170 */ , 242, 232, 247, 244, 244, 249, 240, 234, 254, 63
/* 180 */ , 239, 248, 18, 231, 252, 18, 232, 247, 254, 245
/* 190 */ , 249, 18, 235, 247, 234, 246, 18, 248, 235, 14
/* 200 */ , 233, 247, 45, 243, 247, 132, 233, 242, 250, 241
/* 210 */ , 232, 41, 241, 238, 230, 248, 56, 238, 251, 234
/* 220 */ , 247, 57, 234, 250, 238, 57, 240, 234, 254, 41
/* 230 */ , 247, 248, 248, 238, 31, 235, 247, 234, 246, 31
/* 240 */ , 236, 252, 31, 241, 234, 242, 230, 232, 69, 248
/* 250 */ , 249, 230, 249, 250, 248, 31, 249, 238, 242, 234
/* 260 */ , 28, 230, 233, 28, 234, 247, 249, 238, 235, 149
/* 270 */ , 230, 248, 248, 28, 244, 233, 238, 243, 236, 247
/* 280 */ , 230, 249, 234, 28, 247, 254, 245, 238, 251, 74
/* 290 */ , 232, 248, 103, 230, 233, 233, 247, 79, 240, 234
/* 300 */ , 254, 3, 235, 238, 253, 241, 240, 234, 243, 236
/* 310 */ , 249, 237, 245, 230, 254, 241, 244, 230, 233, 109
/* 320 */ , 238, 233, 3, 238, 246, 238, 243, 251, 234, 247
/* 330 */ , 155, 228, 233, 241, 84, 247, 248, 248, 238, 50
/* 340 */ , 238, 243, 240, 232, 237, 234, 232, 240, 50, 244
/* 350 */ , 232, 240, 50, 248, 249, 242, 250, 241, 232, 171
/* 360 */ , 230, 248, 240, 63, 234, 249, 238, 233, 64, 240
/* 370 */ , 248, 240, 234, 254, 18, 229, 245, 193, 233, 234
/* 380 */ , 251, 18, 236, 248, 241, 244, 249, 18, 240, 234
/* 390 */ , 254, 18, 243, 242, 18, 245, 241, 122, 230, 242
/* 400 */ , 231, 241, 234, 241, 234, 243, 236, 249, 237, 198
/* 410 */ , 234, 243, 233, 18, 249, 245, 94, 232, 251, 94
/* 420 */ , 245, 244, 238, 243, 235, 244, 94, 248, 234, 249
/* 430 */ , 12, 235, 235, 247, 234, 246, 250, 234, 243, 232
/* 440 */ , 254, 12, 242, 251, 242, 250, 241, 232, 12, 248
/* 450 */ , 248, 238, 12, 250, 243, 13, 228, 233, 241, 45
/* 460 */ , 234, 243, 233, 45, 241, 234, 234, 245, 45, 245
/* 470 */ , 247, 234, 230, 233, 238, 243, 236, 235, 230, 232
/* 480 */ , 249, 244, 247, 46, 242, 231, 244, 241, 249, 238
/* 490 */ , 242, 234, 244, 250, 249, 46, 243, 232, 252, 244
/* 500 */ , 247, 233, 24, 232, 244, 243, 235, 24, 238, 242
/* 510 */ , 234, 247, 234, 246, 24, 244, 235, 235, 126, 248
/* 520 */ , 248, 238, 126, 249, 237, 129, 244, 243, 234, 25
/* 530 */ , 244, 250, 249, 245, 250, 249, 245, 244, 252, 234
/* 540 */ , 247, 98, 249, 143, 242, 146, 234, 181, 242, 184
/* 550 */ , 247, 201, 241, 129, 237, 2, 234, 2, 247, 2
/* 560 */ , 255
};
const static int __CMD_AT_LIST[] PROGMEM = {
/* 0 */ 2, 211, 133, 216, 221, 225, 229, 61, 234, 43
/* 10 */ , 136, 141, 543, 100, 239, 242, 248, 69, 255, 72
/* 20 */ , 260, 39, 263, 269, 545, 144, 547, 147, 273, 153
/* 30 */ , 283, 289, 29, 292, 297, 106, 75, 301, 81, 319
/* 40 */ , 322, 114, 330, 334, 158, 119, 84, 339, 92, 348
/* 50 */ , 352, 161, 164, 169, 359, 54, 363, 179, 368, 549
/* 60 */ , 182, 374, 65, 377, 551, 185, 188, 191, 381, 196
/* 70 */ , 387, 391, 394, 397, 409, 124, 413, 199, 416, 22
/* 80 */ , 419, 426, 430, 96, 441, 448, 452, 455, 459, 553
/* 90 */ , 202, 16, 463, 468, 204, 205, 483, 495, 502, 48
/* 100 */ , 507, 514, 518, 522, 525, 127, 555, 529, 130, 541
/* 110 */ , 26, 6, 10, 557, 559, 561
};
/* end of header */
素の ATコマンド 116個が、1067バイトの文字列領域を占めていたところ、561バイトの辞書メモリ配列に圧縮されたことがわかる。前方重複一致だけにも関わらず圧縮率は 52.58% だからそれなりの効果だろう。
Arduino スケッチ
生成されたソースコードを取り込んで、デコード関数をテストする Arduinoスケッチは次のように書ける。PROGMEM領域からメモリ配列を読むためのpgm_read_byte関数が必要だから#include <avr/pgmspace.h>の記述も必要だ。このデコード関数は 50バイト程度の十分小さなコードにコンパイルされる。
#include <avr/pgmspace.h>
#include <cmd_at_table.h>
char* get_cmd_at_strptr (int _idx) {
static char _buff[__CMD_ATX_LENGTH + 1] = {};
uint8_t _p = __CMD_ATX_LENGTH;
while (_idx) {
uint8_t _c = pgm_read_byte( &__CMD_AT_TABLE[--_idx] );
if (_c < __CMD_ATX_CHARS_TOP) { _idx = _c; continue; }
_c -= __CMD_ATX_CHARS_TOP;
if (_c == 0 ) { _c = '+'; }
else if (_c >= 3 ) { _c += 'A' - 3; }
else { _c += '0'; }
_buff[--_p] = _c;
}
return &_buff[_p];
}
void setup (void) {
Serial.begin(CONSOLE_BAUD);
Serial.println(F("<Startup>"));
for (int i = 0; i < sizeof(__CMD_AT_LIST) / sizeof(int); i++) {
Serial.println( get_cmd_at_strptr( pgm_read_word( &__CMD_AT_LIST[i] ) ) );
}
Serial.println(F("done"));
}
void loop (void) {}
/* end of code */
Arduino での実行例は以下のとおり。
19:05:48.466 -> <Startup>
19:05:48.466 -> AT
19:05:48.466 -> AT+ADDMULC
19:05:48.466 -> AT+ADR
19:05:48.493 -> AT+ALIAS
19:05:48.493 -> AT+APIVER
(中略)
19:05:49.660 -> AT+VER
19:05:49.660 -> AT+VERSION
19:05:49.660 -> ATE
19:05:49.660 -> ATR
19:05:49.660 -> ATZ
19:05:49.660 -> done
さらに出力バイナリを逆アセンブルすると、辞書メモリ配列にはほとんど ASCII文字が現れず、難読化されてしまっている様子が見て取れる。
000002ba <__CMD_AT_TABLE>:
2ba: e6 f9 e3 fb ea f7 f8 ee f4 f3 03 f7 fd e5 eb f6 ................
2ca: 03 f5 fc f4 f7 e9 03 f9 fd f5 03 e8 fc 03 e7 fa ................
2da: ee f1 e9 f9 ee f2 ea 03 e6 f9 f2 03 f8 fe f8 fb ................
2ea: 03 f1 f9 ee f2 ea 29 f5 f5 f8 f0 ea fe 03 f3 fc ......).........
2fa: f2 1f f4 f4 f9 fb ea f7 03 e9 f7 03 ea f3 e8 f7 ................
30a: fe 32 e7 f9 f8 e8 e6 f3 f9 ee f2 ea 0c ea f9 fe .2..............
31a: 1f e6 fa e9 4a ea fb ea fa ee 03 ed fc f2 f4 e9 ....J...........
32a: ea f1 03 ef f4 ee f3 12 f7 ea e8 fb 18 f7 fd 18 ................
33a: f9 fd 29 e9 f7 62 f3 e9 fc ee e9 f9 ed 1c eb f8 ..)..b..........
34a: 1c ed f8 1c f1 ee fb ea f7 74 f3 e5 e9 f1 32 f5 .........t....2.
35a: f2 f1 fb f1 a0 f8 ea f3 e9 03 f2 e8 f7 f4 f4 f9 ................
36a: f0 ea fe 3f ef f8 12 e7 fc 12 e8 f7 fe f5 f9 12 ...?............
37a: eb f7 ea f6 12 f8 eb 0e e9 f7 2d f3 f7 84 e9 f2 ..........-.....
38a: fa f1 e8 29 f1 ee e6 f8 38 ee fb ea f7 39 ea fa ...)....8....9..
39a: ee 39 f0 ea fe 29 f7 f8 f8 ee 1f eb f7 ea f6 1f .9...)..........
3aa: ec fc 1f f1 ea f2 e6 e8 45 f8 f9 e6 f9 fa f8 1f ........E.......
3ba: f9 ee f2 ea 1c e6 e9 1c ea f7 f9 ee eb 95 e6 f8 ................
3ca: f8 1c f4 e9 ee f3 ec f7 e6 f9 ea 1c f7 fe f5 ee ................
3da: fb 4a e8 f8 67 e6 e9 e9 f7 4f f0 ea fe 03 eb ee .J..g....O......
3ea: fd f1 f0 ea f3 ec f9 ed f5 e6 fe f1 f4 e6 e9 6d ...............m
3fa: ee e9 03 ee f6 ee f3 fb ea f7 9b e4 e9 f1 54 f7 ..............T.
40a: f8 f8 ee 32 ee f3 f0 e8 ed ea e8 f0 32 f4 e8 f0 ...2........2...
41a: 32 f8 f9 f2 fa f1 e8 ab e6 f8 f0 3f ea f9 ee e9 2..........?....
42a: 40 f0 f8 f0 ea fe 12 e5 f5 c1 e9 ea fb 12 ec f8 @...............
43a: f1 f4 f9 12 f0 ea fe 12 f3 f2 12 f5 f1 7a e6 f2 .............z..
44a: e7 f1 ea f1 ea f3 ec f9 ed c6 ea f3 e9 12 f9 f5 ................
45a: 5e e8 fb 5e f5 f4 ee f3 eb f4 5e f8 ea f9 0c eb ^..^......^.....
46a: eb f7 ea f6 fa ea f3 e8 fe 0c f2 fb f2 fa f1 e8 ................
47a: 0c f8 f8 ee 0c fa f3 0d e4 e9 f1 2d ea f3 e9 2d ...........-...-
48a: f1 ea ea f5 2d f5 f7 ea e6 e9 ee f3 ec eb e6 e8 ....-...........
49a: f9 f4 f7 2e f2 e7 f4 f1 f9 ee f2 ea f4 fa f9 2e ................
4aa: f3 e8 fc f4 f7 e9 18 e8 f4 f3 eb 18 ee f2 ea f7 ................
4ba: ea f6 18 f4 eb eb 7e f8 f8 ee 7e f9 ed 81 f4 f3 ......~...~.....
4ca: ea 19 f4 fa f9 f5 fa f9 f5 f4 fc ea f7 62 f9 8f .............b..
4da: f2 92 ea b5 f2 b8 f7 c9 f1 81 ed 02 ea 02 f7 02 ................
4ea: ff .
000004f0 <__CMD_AT_LIST>:
4f0: 02 00 d3 00 85 00 d8 00 dd 00 e1 00 e5 00 3d 00 ..............=.
500: ea 00 2b 00 88 00 8d 00 1f 02 64 00 ef 00 f2 00 ..+.......d.....
510: f8 00 45 00 ff 00 48 00 04 01 27 00 07 01 0d 01 ..E...H...'.....
520: 21 02 90 00 23 02 93 00 11 01 99 00 1b 01 21 01 !...#.........!.
530: 1d 00 24 01 29 01 6a 00 4b 00 2d 01 51 00 3f 01 ..$.).j.K.-.Q.?.
540: 42 01 72 00 4a 01 4e 01 9e 00 77 00 54 00 53 01 B.r.J.N...w.T.S.
550: 5c 00 5c 01 60 01 a1 00 a4 00 a9 00 67 01 36 00 \.\.`.......g.6.
560: 6b 01 b3 00 70 01 25 02 b6 00 76 01 41 00 79 01 k...p.%...v.A.y.
570: 27 02 b9 00 bc 00 bf 00 7d 01 c4 00 83 01 87 01 '.......}.......
580: 8a 01 8d 01 99 01 7c 00 9d 01 c7 00 a0 01 16 00 ......|.........
590: a3 01 aa 01 ae 01 60 00 b9 01 c0 01 c4 01 c7 01 ......`.........
5a0: cb 01 29 02 ca 00 10 00 cf 01 d4 01 cc 00 cd 00 ..).............
5b0: e3 01 ef 01 f6 01 30 00 fb 01 02 02 06 02 0a 02 ......0.........
5c0: 0d 02 7f 00 2b 02 11 02 82 00 1d 02 1a 00 06 00 ....+...........
5d0: 0a 00 2d 02 2f 02 31 02 ..-./.1.
圧縮率向上の余地
get_cmd_at_strptrデコーダー関数に渡す引数はint型だが、実際に使われる引数は 116種類に過ぎない。これはこのアルゴリズムではまだ 7ビットにまで圧縮できる余地が残っていることを示す。__CMD_AT_LISTテーブルの間接参照はそれを可能にするが、このテーブル要素の密度もまた正味 10ビットしか使っていないので、116 x 6ビットの無駄がある。だがそれらを削るためにデコーダー関数が複雑化してコード量が増えるのとはトレードオフであるから、その判断は実用結果次第だろう。
まとめ
- 簡単な前方重複一致圧縮アルゴリズムでも、用途次第で圧縮率 50%台を達成するのは難しくない
- 簡単な圧縮アルゴリズムでも出力ファイルの難読化に寄与する効果は大きい
Copyright and Contact
Twitter(X): @askn37
GitHub: https://github.com/askn37/
Product: https://askn37.github.io/
Copyright (c) askn (K.Sato) multix.jp
Released under the MIT license
https://opensource.org/licenses/mit-license.php
https://www.oshwa.org/