コマンド文字列テーブルの圧縮を試す

無線モジュールを扱ってると「シリアル接続経由でATコマンドで制御する」ようなデバイスをよく相手にするが、そういうのは大体コードがバタ臭くなる。

```cpp
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コマンド文字列の「途中の重複文字列」圧縮は複雑になるので割愛し、文字列前方の重複一致圧縮だけに絞って考察しよう。例えば以下の三つのコマンドがある。これらをメモリ上でどのように表現すべきだろうか。

```plain
AT+BOOT
AT+BOOTSTATUS
AT+BOOTVER
```

三つのコマンドはいずれも`AT+BOOT`で始まるため、構文解析木はこうなるだろう。`\`は分岐、`$`は文字列終端の意味だ。

```plain
AT+BOOT
      \ $
      \ STATUS $
      \ VER $
```

この構文解析木から目的の文字列を取り出すには、それぞれの`$`から左の根に向かって木構造を辿れば、逆順の文字列が取り出せることは直感的に分かる。途中で`\`に遭遇したら、それが指し示す分岐点に文字取り出しポインタをジャンプさせれば良い。するとこの木構造は以下に示すようなメモリ構造になっていれば良いのではと考えられる。ここでの数値はメモリ配列の項番を指す。

```plain
| 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文字`にまとめることができるはずだ。従ってこの木構造`辞書メモリ配列`の文字コードは、次のように定義できる。

```plain
  0-226 : 項番
    227 : '+'
    228 : '1'
    229 : '2'
230-255 : 'A'-'Z'
```

この考え方でデコーダー関数を書いてみよう。文字列の終端位置を引数として受け取り、木構造テーブルを遡り、逆順に現れる文字を内部バッファに溜めて最後に文字列開始位置のポインタを返却する。なお木構造テーブルの根`0`に項番が達したらループを終了させたいので、実際に使う項番は「目的の文字位置+1」を用いた方が好都合だ。`__CMD_ATX_CHARS_TOP`は 227を保持している定数である。

```c
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文字種数を調べておく。

```perl
#!/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コマンド文字列長（すなわち逆順バッファに必要な定義長）を記録する。

```perl
{
  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コマンド"`を保持しており、その降順で全体をソートしていることを視覚化し、確認できる。

```perl
# 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`を超えないかもここで確認され、違反していれば中断する。

```perl
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コマンド文字列を復元し、コメント文に添えることで誤りがないか確認できるようにしている。

```perl
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`属性を添えた。

```perl
{
  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`で定義された参照項番の列挙に過ぎない。

```perl
{
  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__
```

最終的な標準出力ファイル結果は以下の通り。

```cpp
#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バイト程度の十分小さなコードにコンパイルされる。

```cpp
#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 での実行例は以下のとおり。

```plain
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文字が現れず、難読化されてしまっている様子が見て取れる。

```asm
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](https://twitter.com/askn37) \
GitHub: [https://github.com/askn37/](https://github.com/askn37/) \
Product: [https://askn37.github.io/](https://askn37.github.io/)

Copyright (c) askn (K.Sato) multix.jp \
Released under the MIT license \
[https://opensource.org/licenses/mit-license.php](https://opensource.org/licenses/mit-license.php) \
[https://www.oshwa.org/](https://www.oshwa.org/)