Last modified: Mon Oct 29 15:01:59 JST 2018

初心者への GNU perf のススメ
Lynx Optimized Pages!
50319 accesses since 2001/07/27.
6 accesses per day.

[ TOP ]

©1990-2018 Kazuya 'Sharl' Masuda <sharl @ hauN.org>

目次:
  1. 初めての gperf (1) …簡単なプログラムを作ってみる
  2. 初めての gperf (2)
  3. 初めての gperf (3) …文字の重複問題を解決する
  4. gperf 実用編(1) …構造体にアクセスする
  5. gperf 実用編(2) …構造体の初期化
  6. gperf が出力したソースコードの権利について
  7. 終わりに

初めての gperf (1)

一部から完全ハッシュ関数を作るツール gperf の使い方を知りたい、というリクエストが あったので、軽く説明してみようと思います。 (深く突っ込めないという話も。知ってることしか説明できないよねー(汗;))

ちなみに gperf は cperf-2.1a.tar.gz, gperf-3.0.4.tar.gz, gperf-3.1.tar.gz というパッケージになってます。gperf-2.7 以降は C++ がないとコンパイルできません。

(2017/06/19現在) 3.1 には突然 size_t が出現する不具合があります。http://lists.gnu.org/archive/html/bug-gperf/2017-01/msg00004.html
オプション -I, --includes を指定、または 3.0.4 以前にダウングレードすることで回避可能です。

パッケージのコンパイルについては割愛します。

完全ハッシュ関数とは

ハッシュが線形逐次検索に比べて速いことは周知です。完全ハッシュ関数は固定長のハッシュ表により ハッシュ値の計算コストを抑えてキーワードの探索を高速に行う関数です。普段使われる動的ハッシュに 対して静的ハッシュとも呼ばれます。

キーワードを用意する

簡単な例を。入力した文字列が ID とマッチするかどうか調べるプログラムを作ってみましょう。

--- id.key ---
AVG-FOE
M.H
Sato/2
Sharl
UME20
anti-top
nbkz
oo
-------------- ID 勝手に出してごめんなさい

このようなキーワードファイルを用意します。


初めての gperf (2)

先程のファイル id.key を入力ファイルとして

% gperf id.key

または

% gperf < id.key

とすると、標準出力に C のソースが出力されるので、リダイレクトして id.c とでもしておきます。

version 3.0 以降ではキャラクタセットが異なるとエラーを出すようになりました(id.c 参照)。

完全ハッシュ関数の関数名はデフォルトで in_word_set です。-N オプションで関数名を変更できます (-N name or --lookup-function-name=name)。プロトタイプ宣言は id.c を見てもらうとわかるように

const char *in_word_set(const char *str, unsigned int len);

です。version 2.1 では -a オプションにより len を int にすることができます。

実際の使用例は以下のようになります。

--- main.c ---
#include <stdio.h>
#include <string.h>

extern const char *in_word_set(char *, unsigned int);

void
main(int argc, char *argv[])
{
    const char *p;

    if (argc == 1)
      return;

    p = in_word_set(argv[1], strlen(argv[1]));
    if (p == NULL)
      printf("no match.\n");
    else
      printf("hit [%s]\n", p);
}
--------------

id.c とリンクしてください。

% cc main.c id.c
% ./a.out aa
no match.
% ./a.out oo
hit [oo]
% 

初めての gperf (3)

次の例を見てください。

--- asm.key ---
add
asl
asr
dec
inc
lsl
lsr
mov
ret
rol
ror
sub
---------------

% gperf asm.key
/* starting time is 14:59:48 */
Key link: "rol" = "lsr", with key set "lr".
Some input keys have identical hash values,
try different key positions or use option -D.

どうやら文字が重複している(アナグラムになっている)ので一意に決定できないようです。こういう場合は -D オプションを指定してください(と書いてある(汗;))。

% gperf -D asm.key

‘try different key positions’というのは…うまく説明できません。省略(汗;)。この場合は -k1,3,$ とか -k1,2,$ と指定すればいいんですけど…。この辺は試行錯誤してみてください。 すみません。(清く正しいシェルは $ をエスケープするのを忘れずに :-)

version 3.0 以降では -D をつけなくても自動的に計算してくれるようになりました。

とりあえずこれで gperf を使えるようになりました。(実用的かどうかは神のみぞ知る…)


gperf 実用編

ここからが普通の使い方です。

通常はキーワードとその属性(?)を構造体で格納して、キーワードの属性に対してアクションを行います。

gperf は文字列をキーワードとしてハッシュ表を作るので、かなり用途が限定されます。 逆引きできない、ということですね。

キーワードと属性を使う例

--- word.key ---
%{
/*
 * a portion of GNU make keywords
 */

#include "word.h"
%}
struct OPE { char *name; int type; int args; };
%%
addprefix,      F_ADDPREFIX,    DYNAMIC
addsuffix,      F_ADDSUFFIX,    DYNAMIC
basename,       F_BASENAME,     MONAMIC
dir,            F_DIR,          MONAMIC
filter,         F_FILTER,       DYNAMIC
filter-out,     F_FILTEROUT,    DYNAMIC
findstring,     F_FINDSTRING,   DYNAMIC
firstword,      F_FIRSTWORD,    MONAMIC
foreach,        F_FOREACH,      TRINAMIC
join,           F_JOIN,         DYNAMIC
notdir,         F_NOTDIR,       MONAMIC
origin,         F_ORIGIN,       MONAMIC
patsubst,       F_PATSUBST,     TRINAMIC
shell,          F_SHELL,        MONAMIC
sort,           F_SORT,         MONAMIC
strip,          F_STRIP,        MONAMIC
subst,          F_SUBST,        TRINAMIC
suffix,         F_SUFFIX,       MONAMIC
wildcard,       F_WILDCARD,     MONAMIC
word,           F_WORD,         DYNAMIC
words,          F_WORDS,        MONAMIC
----------------

この例では word.h に define や enum などで定数を定義しておきます。この書式、yacc/bison の .y に似てますね。f?lex の .l にも似てるかも。

%{ と %} の間の行がソースに挿入されます。%} と %% の間の行が、構造体の宣言になります。%% 以降が 構造体の内容の羅列です。1 行に構造体 1 つぶんしか書いてはいけません。 キーワードは必ず先頭に書きます。それにあわせて構造体のメンバの型も決めてください。

ここで注意。デフォルトではキーワードに対するメンバ名が‘name’です。 メンバ名を変更したい、という時は -K で指定します(-K name or --slot-name=name)。

ex.)
    struct MEMB { char *id; char *addr; char *tel; };

のとき gperf -K id ... となります。

キーワードから属性(この場合は構造体のメンバ)を得たいので、構造体へのポインタが返ってこないと 参照できませんね。

しかし、デフォルトではキーワードへのポインタを返すので、構造体へのポインタを返すように オプションで -p -t を指定します。 -pt と続けて書いてもかまいません。

% gperf -pt word.key > word.c

さて、word.c の中に構造体 OPE の定義が残っています。もし word.h の中で struct OPE を定義したり していると redefinition error が出ます。ヘッダを使い回す人は注意ですね。そういうときは -T を指定すると、構造体の宣言が出力されなくなります。

% gperf -ptT word.key > word.c

めでたく構造体へのポインタが返るようになりました(なりましたよね???)。この場合の in_word_set のプロトタイプ宣言は

struct OPE *in_word_set(const char *str, unsigned int len);

になります。あとは

    struct OPE *p;

    if ((p = in_word_set(key, strlen(key))) != NULL)
      do_func(p->type, p->args);

などとして使いましょう。Rubyが予約語のハッシュをgperfで作っていますね。

構造体の初期化

構造体の初期化でコンパイラの警告が出る場合は version 3.0以降-F ", 0, 0" と オプションで初期化するものを指定するか、構造体宣言の前か後ろに

%define initializer-suffix ,0,0

と書いてあげると埋めてくれます。自動的に構造体宣言の中を解析してくれるわけじゃないですけど。%define を 使うときに空白を入れるとダメな感じなので -F を使ってquoteしてあげるといい感じのソースになります。


gperf が出力したソースコードの権利について

gperf 3.0.4 のドキュメントに「出力されたコードの権利について」という項目ができていました。 公式マニュアルにも反映されています。 該当部分を引用しておきます。

3.5 The Copyright of the Output

gperf is under GPL, but that does not cause the output produced by gperf to be under GPL. The reason is that the output contains only small pieces of text that come directly from gperf's source code – only about 7 lines long, too small for being significant –, and therefore the output is not a “work based on gperf” (in the sense of the GPL version 3).

On the other hand, the output produced by gperf contains essentially all of the input file. Therefore the output is a “derivative work” of the input (in the sense of U.S. copyright law); and its copyright status depends on the copyright of the input. For most software licenses, the result is that the the output is under the same license, with the same copyright holder, as the input that was passed to gperf.

※強調部分は筆者によるもの

長年議論されてきましたが、これでようやくの決着となりそうです。


終わりに

駆け足で説明してきましたが、けっこうな量になっちゃいました。でも、これだけ覚えておけば一応使う ことはできます。わたしもこのくらいしかわかりませんけど大丈夫ですし(汗;)。

もっと突っ込んで知りたい方は gperf.texinfo や付属の gperf.html を参照してください(汗;)。


履歴

(2017/06/19) gperf-3.1.tar.gz が出ていたので更新。size_t が突然出てくる不具合も追記。

(2012/03/23, 2012/07/18) gperf が出力したソースコードの権利についての項を追加。公式マニュアルへのリンクを追加。

(2005/10/29) gperfの吐くソースにgccが文句を言うを受けて構造体の初期化を追加。

(2003/08/09) version 3.0.1 に対応した内容に改変。

(2001/08/02) サンプルで使ったソースを見られるようにした。若干改変。

(2001/08/01) 休んでいる間に gperf-2.7.2.tar.gz が出ていたので更新。

(1998/05/08) gperf-2.7.tar.gz が独立パッケージに。

(1997/10/06) gperf の在処を追加。

(1997/05/16) はるか昔に書いたドキュメントを HTML にしてみました。今でもここに書いたくらいの知識しか持って ないし、これ以上の使い方をしてないので、この説明が役にたつ人もいるんじゃないかなぁ。 ツッコミもお待ちしております。


©1990-2018 Kazuya 'Sharl' Masuda <sharl at hauN.org>