more sort
ArchLinux gauche のトラブル
前回喜びいさんで入れたArchLinux上のgauche、売りのREPL上の補完が効かない。 そればかりか、よくプロンプトを見ると、gosh> となってる。
edit機能までも動いていない。早速マニュアルにあたると、vt100端末だった場合 機能しますと説明されてる。補完は、画面制御の機能を使って実現されてるから、 こちらも機能しないんだな。
[sakae@arch ~]$ echo $TERM tmux-256color [sakae@arch ~]$ gosh gosh> (use text.console) gosh> (vt100-compatible? "tmux-256color") #f
tmux-256colorってvt100端末じゃないのか。ならば、Debianとかは、どうなってた。確認してみたら、screenになってた。
[sakae@arch ~]$ export TERM=screen [sakae@arch ~]$ gosh gosh$ (use text.console) gosh$ (vt100-compatible? "screen") #t gosh$ open-TAB open-coding-aware-port open-output-buffered-port :
おお、機能したぞ。それじゃ、ダメ出しで、edit機能を切ってみる。
gosh$ ,edit off gosh> open- TAB ;; 単にTABが機能するだけだった。
consoleのTERMはlinuxってなってた。これも、vt100族ではない。なんか、新しい潮流でもあるのかな？
Hintが有ったから
で、どうやって端末がVT100系か調べている？ 乗り掛った舟だから、少し探索する。 libsrc/text/console.scm
;; Strict compatibility isn't necessary; we're using just a common ;; denominator. We expand this list as we discover other terminal types ;; that works. ;; See https://github.com/shirok/Gauche/issues/179 about 'screen'. (define-constant *vt100-compatible-terminals* #/^(vt10[02]|vt220|xterm.*|rxvt.*|screen.*|linux|tmux.*)$/)
こんな説明と共に、判定基準が出てきたので、追加した。オイラーの想像では、ちゃんとVT100系か試験してるかと思っていたんだ。そうじゃなくて、端末の名前を突き合せているだけなのね。
ここを見てると、相手がちゃんとエスケープシーケンスを理解するって前提で、コードが組立られている。相手を信用するしかないな。これで世の中が回れば、平和なんですけどねぇ。
同じ階層に、line-edit.scmなんてのがおいてあった。思わせぶりで、思わず開いてしまったぞ。簡単に言うと、1500行ぐらいのemacs風editorだ。注目はこれ。
(define-edit-command (completion-command ctx buf key)
"Try to complete the (partial) word at the cursor."
(receive (word start-pos end-pos)
(buffer-find-word buf (~ ctx'completion-word-constituent?))
(or (and-let* ([ word ]
[lister (~ ctx'completion-lister)]
[words (lister word buf start-pos end-pos)])
(match words
[() #f]
[(? string?)
;; Final candidate. We append whitespace after it.
(gap-buffer-move! buf start-pos)
(gap-buffer-replace! buf (- end-pos start-pos) #"~|words| ")
'redraw]
:
今回入った、目玉の部分。補完を実現するeditorの内部コマンドだ。40行たらずのコードだけど、密度が濃厚なので、容易に読み解けないな。一日一行の修行でもしてみる？
それより気分を変えて、gaucheのパッケージャさんは、どんなconfigしてるか、一応確認してみる。逃げるなコラ。
[sakae@arch ~]$ gauche-config --reconfigure >LOG [sakae@arch ~]$ cat LOG ./configure '--prefix=/usr' '--with-slib=/usr/share/slib' '--with-tls' 'CFLAGS=-march=x86-64 -mtune=generic -O2 -pipe -fno-plt -fexceptions -Wp,-D_FORTIFY_SOURCE=2 -Wformat -Werror=format-security -fstack-clash-protection -fcf-protection -flto=auto -ffat-lto-objects -w' 'LDFLAGS=-Wl,-O1,--sort-common,--as-needed,-z,relro,-z,now -flto=auto' '--enable-multibyte=utf-8'
オイラーが使った亊無いオプションを多数指定してるか。紐解いてみるかな。宿題はどんどん積み重なります。
sort
前回はsortなんてのをやった、もう少し遊んでみる。どんなsort方法を取るか、引数で指定出来るのね。供試データは、各種の言語ね。
vbox$ sort --qsort --debug z.txt Memory to be used for sorting: 1073451008 sort_method=quicksort ; k1=<Python>(6), k2=<Scheme>(6); s1=<Python>, s2=<Scheme>; cmp1=-3 ; k1=<Scheme>(6), k2=<AWK>(3); s1=<Scheme>, s2=<AWK>; cmp1=18 ; k1=<Python>(6), k2=<AWK>(3); s1=<Python>, s2=<AWK>; cmp1=15 ; k1=<Go>(2), k2=<Python>(6); s1=<Go>, s2=<Python>; cmp1=-9 : AWK C Go :
何も指定しないと、
sort_method=radixsort ; offset=1 ; k1=<Ruby>(4), k2=<Rust>(4); offset=1; s1=<Ruby>, s2=<Rust>; cmp1=-17 ; offset=1 ; k1=<Python>(6), k2=<Perl>(4); offset=1; s1=<Python>, s2=<Perl>; cmp1=20 AWK C :
こんなradixsortが選ばれた。比較回数も少く、一番高速で仕事をしてくれるのかな。それはそうと、それぞれのオブジェクトのサイズが渡されているんで、ヒントとして使われるのかな。
そもそも、入力データをどのように保持するんだろう？ 前回は、heapsortの引数として、配列のアドレス、個数、オブジェクトのサイズ、比較関数がある。んだけど、きになるのは、オブジェクトのサイズってやつだ。行毎にバラバラなのに、何これって思った次第。
#3 0x077be52e in _libc_qsort (a=0x6276a000, n=9, es=4,
cmp=0x18aa57f0 <list_coll>) at /usr/src/lib/libc/stdlib/qsort.c:234
234 introsort(a, n, es, maxdepth, swaptype, cmp);
n=9ってのは、９行あるよ。問題は次のes=4って所。一行で一番長いのは、６文字のpythonだ。で、はてなな訳です。
file.hを見て、あたりをつける。
(gdb) bt
#0 sort_list_add (l=0xcf7f4c30, str=0x66a05ec0) at file.c:259
#1 0x1a95c138 in procfile (fsrc=0xcf7f4dee "z.txt", list=0xcf7f4c30,
fl=0xcf7f4c48) at file.c:730
#2 0x1a95f54a in main (argc=1, argv=0xcf7f4d2c) at sort.c:1103
9回実行したら、結果が表示された。って亊は、的中したって亊ですかね。
procfileの中で、前準備として、 file_reader_readline なんてのが呼び出されている。
file_reader_readline(struct file_reader *fr)
{
struct bwstring *ret = NULL;
if (fr->mmapaddr) {
unsigned char *mmapend;
mmapend = fr->mmapaddr + fr->mmapsize;
:
ファイルをメモリーに割付ているんだな。こういう亊って、普通の亊？
のメモリー管理編をみると、普通の亊っぽい。
example sort
ちょいと気分を変えてArch Linuxでsortの例がないかとmanを検索。が、のきなみ開発系のmanは入っていなかった。 man ページを見て、パッケージを入れたよ。mandbもやっとけって神託があったよ。で、heapsortが無かったんで、qsort.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static int cmpstringp(const void *p1, const void *p2) {
return strcmp(*(const char **) p1, *(const char **) p2);
}
int main(int argc, char *argv[]) {
if (argc < 2) {
fprintf(stderr, "Usage: %s <string>...\n", argv[0]);
exit(EXIT_FAILURE);
}
qsort(&argv[1], argc - 1, sizeof(char *), cmpstringp);
for (int j = 1; j < argc; j++)
puts(argv[j]);
exit(EXIT_SUCCESS);
}
ぼんくらな頭でも、やっと分ったよ。ちょいと、実行例をば。
[sakae@arch tmp]$ ./a.out ruby python go scheme awk php awk go php python ruby scheme
更に確認。64Bitシステムだと、ナチュラルなのが8なのか。これって基本の基だな。
(gdb) p sizeof(char *) $1 = 8
shuf
リナでshufがどうなってるか、調べたい。coreutilsのコンパイルを始めたんだけど、見事にエラー。coreさえ、まともにコンパイル出来無いとは、困ったちゃんであります。ぐぐったら、BUGだと騒いでいる人多数。
CC lib/parse-datetime.o parse-datetime.tab.c:658:10: fatal error: parse-datetime.tab.h: No such file or directory
ピンときたぞ。オイラーの脳内正規表現発動。曰く、*.tab.* ってやつ。
sakae@deb:~/src/coreutils$ cd lib/ sakae@deb:~/src/coreutils/lib$ ls parse-datetime.* parse-datetime.c parse-datetime.h parse-datetime.y
パーサー用のソースである、parse-datetime.yが有るのに、その成果物が作成されていない。手動でやってみる。
akae@deb:~/src/coreutils/lib$ bison -d parse-datetime.y sakae@deb:~/src/coreutils/lib$ ls parse-datetime.* parse-datetime.c parse-datetime.tab.c parse-datetime.y parse-datetime.h parse-datetime.tab.h
昔やっといてよかった。これで、無事にコンパイルが完了したよ。
# The Automake generated .y.c rule is broken: When executed in a VPATH build,
# - The .c file gets generated in the build directory. But since it requires
# special tools to rebuild it, we need to distribute it in the tarballs,
# and by the GNU Coding Standards
# <https://www.gnu.org/prep/standards/html_node/Makefile-Basics.html>
# the file should be generated in the source directory.
# - The #line numbers in the .c file refer to a nonexistent file once it
# has been moved from the build directory to the source directory. This
# leads to error if 'lcov' is used later.
# Additionally, here we assume GNU Bison and therefore don't need the ylwrap
# script.
# Therefore we override this rule.
lib/parse-datetime.c: lib/parse-datetime.y
$(AM_V_YACC)$(PARSE_DATETIME_BISON) -d $(YFLAGS) $(AM_YFLAGS) $(top_src\
dir)/lib/parse-datetime.y \
&& sed -e 's|".*/parse-datetime.y"|"parse-datetime.y"|' < parse-datetim\
e.tab.c > parse-datetime.c-t \
&& rm -f parse-datetime.tab.c parse-datetime.tab.h \
&& mv parse-datetime.c-t $(top_srcdir)/lib/parse-datetime.c
気になったので、長大なMakefileを調べてみた。なにこれ、なんか関係してるのかな。まあ、所詮リナは、よせ集めですから、敵の玉を除けて生き延びるのに必死ってのが、ありありですよ。 余り、お近かづきにならない方が、ストレスがかかならなくて平安だろう。
で、代わりに見付てきたのが、配列をシャッフルする有名な手続。詳しい説明は、こちら。 重複なしで乱数を生成する方法
#include <sys/types.h> // for getpid()
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#define N 100
void shuffle(int n, int v[]) {
int i, j, t;
for (i = n - 1; i > 0; i--) {
j = (int)((i + 1) * (random() / (double)RAND_MAX));
t = v[i]; v[i] = v[j]; v[j] = t;
}
}
int main() {
int i;
static int a[N];
srandom(getpid());
for (i = 0; i < N; i++) a[i] = i + 1;
shuffle(N, a);
for (i = 0; i < N; i++) printf("%4d", a[i]);
printf("\n");
return EXIT_SUCCESS;
}
RAND_MAXは2147483647 こんな値なんですね。random()は整数が却ってくるので、それを少数点化したやつで割って、０から１未満の少数にに変換してる。
Breakpoint 1, shuffle (n=100, v=0x555555558080 <a>) at z.c:11
11 for (i = n - 1; i > 0; i--) {
(gdb) p *v@100
$1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58,
59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77,
78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96,
97, 98, 99, 100}
この配列をgdbで表示させる方法を、コンビニと言うそうだ。普通のコンビニにはほとんど用がないけど、これは重宝しそう。
arc4randomでBUG誘発
上のコードをOpenBSDに移植。この際だから、自慢のarc4randomを使ってやろう。
vbox$ ./a.out 39 1 12 16 50 7 74 44 3 47 6 83 30 40 41 79 43 70 33 8 71 15 91 55 29 46 69 25 26 9 72 53 5 80 17 20 31 89 34 3 10 21 18 27 0 22 67 51 84 97 77 45 66 37 13 14 75 42 0 3 88 0 100 59 60 19 56 0 32 24 57 2 54 98 52 0 28 58 48 7 76 63 11 4 23 0 65 87 36 0 61 0 0 0 92 0 49 82 99 8
なんでZEROなんてのが出て来る？ 絶対に出てこないはずだけどな。じっと考える、考える。そして閃いた。
arc4randomが RAND_MAX を越えてしまって、その結果、配列の範囲外をアクセスしているのではなかろうか。そしてその値がたまたまZEROだった。範囲外へのアクセスなら落るはずだけど、微妙なはみ出しは、検出出来無いんだろう。
int main() {
int i,v;
for (i = 0; i < N; i++) {
v = arc4random();
printf("%d\t%1f\n", v, (v / (double)RAND_MAX));
}
return EXIT_SUCCESS;
}
こんなテストプログラムを動かしてみる。
vbox$ ./a.out 1168480172 0.544116 -157658772 -0.073416 -1424111656 -0.663154 1104177123 0.514173 1165596195 0.542773 :
想像通りになったな。そこで改めて、arc4random(3)
uint32_t arc4random(void); uint32_t arc4random_uniform(uint32_t upper_bound);
一応 unit32_t なんだけどな。返値をきちんと制限したい時は、 arc4random_uniform(RAND_MAX) を使ってください、か。変更したら大丈夫だった。思わぬ落とし穴だな。
ちなみに、long random(void)なんで、無理じいの感はあるな。いや著しく型違いだぞ。hasakellとかだと、絶対に見逃してくれないぞ。
in FreeBSD
何気にみてたら、FreeBSDにも発見
EXAMPLES
The following produces a drop-in replacement for the traditional rand()
and random() functions using arc4random():
#define foo4random() (arc4random_uniform(RAND_MAX + 1))
オイラーの方法だと、OFF BY ONE なエラーだね。まあ、表面化する琴はないだろうけど。
HISTORY
These functions first appeared in OpenBSD 2.1.
The original version of this random number generator used the RC4 (also
known as ARC4) algorithm. In OpenBSD 5.5 it was replaced with the
ChaCha20 cipher, and it may be replaced again in the future as
cryptographic techniques advance. A good mnemonic is “A Replacement Call
for Random”.
The arc4random() random number generator was first introduced in
FreeBSD 2.2.6. The ChaCha20 based implementation was introduced in
FreeBSD 12.0, with obsolete stir and addrandom interfaces removed at the
same time.
そして、歴史ですよ。歴史といったら、あの高名な先生が、大型コンピューターには、カイガーカウンターを使った乱数発生器が組込まれていたって言ってたなあ。今なら、ツェナーダイオードのアバランシュ崩壊のノイズを拾って、真の乱数発生器を作るのかな。
コンピュータは計算しか出来ませんからね。
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
int main() {
uint v;
for (int i = 0; i < 10; i++) {
v = arc4random();
printf("%u\t%1f\n", v, (v / (double)UINT_MAX));
}
return EXIT_SUCCESS;
}
これでもOk.
ob$ ./a.out 1179423764 0.274606 624046525 0.145297 4075610533 0.948927 513462172 0.119550 :
etc
以前tkinterでお世話になったサイトで、下記のようなオイラーの琴繊にふれる記事が掲載されてた。他にも多数あるので、みておくと吉。
strtok関数の使い方と注意点（文字列を区切り文字で分離する関数）