zgrep

Gnuplot on OpenBSD
emacs calcでグラフ表示
- deep calc
zgrep
- case OpenBSD
from RFC
with gdb
zlib
DEFLATE and LZ77
Costas array
コウモリ

Gnuplot on OpenBSD

グラフはmatplotlibにお任せよと思っていたんだけど、そうもいかなくなった。ならばportsから入れればいいじゃん。でも色々な付属品がついてくる。じゃ野良で入れよう。

参考のためにMakefileを参照。–with-xは必須だな。野良エリアの/optも必須。ソースは自分で探すのが面倒なんで、make fetchした物を流用。パッチもついでに流用。

vbox$ ./configure   --with-x --prefix=/opt --without-readline

これで行けるかと思ったら、リンクエラー。ソースをざっと見して、–without-readlineオプションを追加。これで無事にインストールできた。

emacs calcでグラフ表示

なんと電卓のくせにグラフ表示が出来る。昔、そんな電卓が有ったような。グラフ表示はgnuplotにお任せよ。決してmatplotlibじゃないんだよ。そんな訳で、gnuplotを最低機能でインストールしたのさ。

使い方は簡単。最初にX用のベクターをスタックに配置。そしてY用のベクターを積む。そうしておいて、g f すれば、ライン・グラフが表示される。

具体例として、適当なデータをグラフ化してみる。まず、データをベクターに用意する。次にそのサイズを u # で確認。対応するX軸用のベクターを、 [1.. SPC 31] して用意する(様は、範囲データだな)。次にスタック・トップにデータを配置。

お好みで、Y軸の表示範囲を設定。g R すると下記のような質問が出るので、それに対して指示する。なお、X軸範囲は、g r で可能。

Y axis range: 80:150

後は、g f すればよい。

3:  31                                              |     1
2:  [1 .. 31]                                       |     31
1:  [139, 139, 133, ..., 124]                       |

これはグラフ表示した時のスタック配置。これらのコマンドの実行の裏で

# Commands for running gnuplot

set yrange [80:150]

plot "/tmp/calc17bKmC5" title "PlotData2" with linespoints

こんな記録が残っていた。/tmp/calc17bKmC5は描画用のデータ・ファイルだ。汎用のツールって、あちこちで利用できて便利だな。

不幸にして、X環境が利用できなくても安心したまえ。ちゃんとASCIIアートしてくれるよ。

2:  [1 .. 30]                                       |     1
1:  ln(x)                                           |     30

こんな風に 1 .. 30 までの log(x) をアートしてみる。そう、式だって指定出来るんだ。式の入力は、'log(x) ってすればOK。ついでに、g g してグリッドも表示しちゃえ。後は、g f するだけーー。

gnuplot> ^L(Sat Nov  4 07:55:36 2023)                                          $
 3.5 +---------------------------------------------------------------------+
     |           +          +           +           +          ************|
     |           :          :           :           : *********:           |
   3 |-+.........:..........:...........:........*****.........:.........+-|
     |           :          :          **********   :          :           |
     |           :          :     ***** :           :          :           |
 2.5 |-+.........:..........:*****......:...........:..........:.........+-|
     |           :        ***           :           :          :           |
     |           :      **  :           :           :          :           |
   2 |-+.........:...***....:...........:...........:..........:.........+-|
     |           : **       :           :           :          :           |
 1.5 |-+.........**.........:...........:...........:..........:.........+-|
     |         **:          :           :           :          :           |
     |       **  :          :           :           :          :           |
   1 |-+....*....:..........:...........:...........:..........:.........+-|
     |     *     :          :           :           :          :           |
     |    *      :          :           :           :          :           |
 0.5 |-+..*......:..........:...........:...........:..........:.........+-|
     |   *       :          :           :           :          :           |
     |  *        +          +           +           +          +           |
   0 +---------------------------------------------------------------------+
     0           5         10          15          20         25          30

gnuplot> q

描画の終了は、 q ね。なお、X環境でも酔狂にもアートしたいなら、g D して、下記を設定する。馬鹿モードって事だね。GUIに戻すなら、x11すれば良い。

Device name: dumb

deep calc

余りに丁寧なマニュアルなんで、英語で読むのは疲れる。エッセンスだけでも日本語で読みたいぞ。ググルに翻訳させちゃえ。でも受付てくれるのは、PDF で300ページまでだ。

htmlな奴を、下記でテキストに落す。

[sakae@fb /tmp]$ w3m -dump https://www.gnu.org/software/emacs/manual/html_mono/calc.html >calc.txt

emacsで不要な部分を削除。それをオンラインで txt2pdf する(探せばアプリが見付かるだろうけど、常に使う物じゃないからね)。

Online 2 PDF

結果のPDFをどこかに移動させてから、Webを終了(これをやらないと、終了時にPDFファイルが削除されてしまう)。後はそれをググルの翻訳アプリにバトンタッチすればよい。

気になったので、ちょいと調べてみたら、こんなのがヒットした。古典的だな。

PORTNAME=       a2pdf
PORTVERSION=    1.13
PORTREVISION=   2
CATEGORIES=     print perl5
MASTER_SITES=   CPAN
MASTER_SITE_SUBDIR=     CPAN:JONALLEN

MAINTAINER=     portmaster@BSDforge.com
COMMENT=        Text to PDF converter
WWW=            http://perl.jonallen.info/projects/a2pdf
RUN_DEPENDS=    p5-File-Type>=0:devel/p5-File-Type \
                p5-Image-Size>=0:graphics/p5-Image-Size \
                p5-PDF-API2>=0:textproc/p5-PDF-API2 \
                p5-Switch>=0:lang/p5-Switch \
                perltidy:devel/p5-Perl-Tidy

TAB   swap (top and top-1)
P     3.14159265359
U     undo

恥かしながら、知りませんでした。やっぱり日本語はスラスラ読めていいわい。場合によっては日本語が不鮮明な事がある。そういう時はInfoと併用するのさ。

zgrep

前回emacsのソースを参照する時に使用したzgrep、どんな風に構成されてる？そりゃ、圧縮ファイルを解凍して、パイプでgrepに接続するんだろう。よって、それなりのshell scriptになってるはず。予想通りだった。念のため、manしとく。こういう調べものは、*BSDに限ります。

ZGREP(1)                FreeBSD General Commands Manual               ZGREP(1)

NAME
     zgrep, zegrep, zfgrep, bzgrep, bzegrep, bzfgrep, lzgrep, lzegrep,
     lzfgrep, xzgrep, xzegrep, xzfgrep, zstdgrep, zstdegrep, zstdfgrep – grep
     compressed files

色々な圧縮ファイルに対応してるね。最近はリナ推しってかGNU推しのzstdが幅を効かせているのかな。そんじゃ、OpenBSDはどうよ？

case OpenBSD

仕様調べ。

GREP(1)                     General Commands Manual                    GREP(1)

NAME
     grep, egrep, fgrep, zgrep, zegrep, zfgrep – file pattern searcher

     zgrep, zegrep, and zfgrep act like grep, egrep, and fgrep, respectively,
     but accept input files compressed with the compress(1) or gzip(1)
     compression utilities.

あれ？ grepとzgrepが同一なmanで説明されてるよ。FreeBSDとは機構が違うのかな？ zgrepの正体はどうなってる？ file zgrepしたらバイナリー・ファイルだった。きっとアレ式になってるのだろう。

vbox$ cd /usr/bin/
vbox$ ls -i zgrep
389087 zgrep*
vbox$ ls -i | grep 389087
389087 egrep*
389087 fgrep*
389087 grep*
389087 zegrep*
389087 zfgrep*
389087 zgrep*

inode一緒って事は、皆同じものだった。ええい、こうなったらソース嫁。 (その前にMakefileを見ろっていうショート・カットはやりません。だって、それじゃ中途半端ですからね)

ソース調べ。grep.c

        switch (__progname[0]) {
        case 'e':
                Eflag = 1;
                break;
        case 'f':
                Fflag = 1;
                break;
#ifndef NOZ
        case 'z':
                Zflag = 1;
                switch(__progname[1]) {
                case 'e':
                        Eflag = 1;
                        break;
                case 'f':
                        Fflag = 1;
                        break;
                }
                break;
#endif

Xgrepの認知と実行フローの設定の為にフラグを立てている。なお、 __progname は、起動コマンド名(OpenBSDの特徴だな)。

Zflagが利用される現場。file.c

#ifndef NOZ
        if (Zflag) {
                f->type = FILE_GZIP;
                f->noseek = lseek(fd, 0L, SEEK_SET) == -1;
                if ((f->gzf = gzdopen(fd, "r")) != NULL)
                        return f;
        }
#endif

ここでさりげなく圧縮ファイルをオープンしてる。

from RFC

大事なフォーマットなんでRFCになっていないかな？

[sakae@fb ~]$ rfc -k zlib
The Result:
1950 ZLIB Compressed Data Format Specification version 3.3. P. Deutsch,
     J-L. Gailly. May 1996. (Format: TXT, PS, PDF, HTML) (Status:
     INFORMATIONAL) (DOI: 10.17487/RFC1950)
6713 The 'application/zlib' and 'application/gzip' Media Types. J.
     Levine. August 2012. (Format: TXT, HTML) (Status: INFORMATIONAL)
     (DOI: 10.17487/RFC6713)
[sakae@fb ~]$ rfc -k zip
The Result:
1952 GZIP file format specification version 4.3. P. Deutsch. May 1996.
     (Format: TXT, PS, PDF, HTML) (Status: INFORMATIONAL) (DOI:
     10.17487/RFC1952)
6713 The 'application/zlib' and 'application/gzip' Media Types. J.
     Levine. August 2012. (Format: TXT, HTML) (Status: INFORMATIONAL)
     (DOI: 10.17487/RFC6713)

やっぱり有った。RFC-1951 も大事だよ。

8878 Zstandard Compression and the 'application/zstd' Media Type. Y.
     Collet, M. Kucherawy, Ed.. February 2021. (Format: HTML, TXT, PDF,
     XML) (Obsoletes RFC8478) (Status: INFORMATIONAL) (DOI:
     10.17487/RFC8878)

おっ、こんなのも有るぞ。まだ、余り普及してないようだけど。

with gdb

久ぶりにgdbしてみる。a.gzは、calc-graph.el.gz の短縮名。長い名前は嫌いだからね。

vbox$ gdb -q zfgrep
Reading symbols from zfgrep...
(gdb) b printline
Breakpoint 1 at 0x6e30: file util.c, line 658.
(gdb) r -n gra a.gz
Starting program: /tmp/grep/zfgrep -n gra a.gz

Breakpoint 1, printline (line=0xcf7da400, sep=58, pmatch=0x0) at util.c:658
658             n = 0;
(gdb) bt
#0  printline (line=0xcf7da400, sep=58, pmatch=0x0) at util.c:658
#1  0x14a5c3c7 in procline (l=0xcf7da400, nottext=0) at util.c:271
#2  0x14a5ba72 in procfile (fn=0xcf7da5c7 "z.gz") at util.c:158
#3  0x14a5a974 in main (argc=0, argv=0xcf7da500) at grep.c:527

本当は、これが目的じゃなくて、libzとどう関わっているか知りたいんだ。ガチャガチャやってたら、/usr/src/lib/libz/gzread.cあたりを呼出ている事が判明。それじゃってんで、元締めっぽいのにBPを置いてみた。

(gdb) r
Starting program: /tmp/grep/zfgrep auto a.gz > /dev/null

Breakpoint 1, gz_decomp (state=0x6d380e60) at /usr/src/lib/libz/gzread.c:159
159         z_streamp strm = &(state->strm);
(gdb) bt
#0  gz_decomp (state=0x6d380e60) at /usr/src/lib/libz/gzread.c:159
#1  0x07d1ed85 in gz_fetch (state=<optimized out>) at /usr/src/lib/libz/gzread.c:228
#2  0x07d1e49c in gz_read (state=<optimized out>, buf=0xcf7eede8, len=<optimized out>) at /usr/src/lib/libz/gzread.c:310
#3  0x07d1e399 in gzread (file=0x6d380e60, buf=0xcf7eede8, len=1024) at /usr/src/lib/libz/gzread.c:366
#4  0x15607369 in gzbin_file (f=0x6d380e60) at binary.c:75
#5  0x1560788c in grep_bin_file (f=0x6d39fe60) at file.c:171
#6  0x1560982c in procfile (fn=0xcf7ef45a "a.gz") at util.c:129
#7  0x15608974 in main (argc=0, argv=0xcf7ef38c) at grep.c:527

どうやらビンゴっぽい。procfileが一つのファイルをgrep。対象がgzファイルって事で、バイナリーなんだな。で、それを読み出したい。元締めで、ファイルを解凍します、だな。都合4回の呼出で、grepが終了した。

本当の解凍をやってるのは、inflate.c になるけど、そこまで首を突っ込むと、先に進まなくなるので中止する。

vbox$ gunzip -l a.gz
compressed  uncompressed  ratio  uncompressed_name
     11899         56240  78.9%  a

こんなオプション知らなかったぞ。

1:  [11899, 56240]                 |grab [11899, 56240]
    .                              |unpk 11899
                                   | ... 56240
                                   |   / 0.211575391181
                                   |   / 4.72644760064

数値の部分をレクタングルしといて、C-x * g でcalc に取り込み。v u して分解。それから / で、割り算。元データの21%まで圧縮されましたとな。続いて U で演算を無かった事にしてから、TABでデータを入れ替え。再び、割り算。解凍すると、4.7倍に肥大します。いいね、この電卓!

zlib

で、zlibの資料を漁ってみる。その起点は、 zlib

An Explanation of the Deflate Algorithm

A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS

zlib: Compression and decompression in the gzip and zlib formats for Haskell

zlib 入門 C言語アルゴリズム辞典の掲載されていないので、奥村先生がんばった。つらつらと記事を読んでいたら、libzに貢献したよって出てたので、調査してみた。確かにクレジットされてる。

trees.c

/* Now recompute all bit lengths, scanning in increasing frequency.
 * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
 * lengths instead of fixing only the wrong ones. This idea is taken
 * from 'ar' written by Haruhiko Okumura.)
 */

Zip Files: History, Explanation and Implementation モールス信号が出てきたりで、楽しい読み物

RFC 8878 Zstandard スピード比べしてる

DEFLATE and LZ77

もう少し日本語って事で。。。

図解DEFLATEアルゴリズム 1/2 ーハフマン符号とLZ77アルゴリズム

図解Deflateアルゴリズム 2/2 ー圧縮の流れとDeflateブロックの構造

5.3 LZ77符号化の手順

今更だけど、データ圧縮についてまとめてみたい

Costas array

以前からの懸案事項。コスタス行列

[sakae@deb lib]$ grep Costas -r .
./qra64code.f90:  data icos7/2,5,6,0,4,1,3/     !Defines a 7x7 Costas array
./ft8/sync8.f90:  data icos7/3,1,4,0,6,5,2/                   !Costas 7x7 tone pattern
./ft8/genft8.f90:  data icos7/3,1,4,0,6,5,2/                   !Costas 7x7 tone pattern
   :

sync8.f90

subroutine sync8(dd,nfa,nfb,syncmin,nfqso,maxcand,s,candidate,   &
     ncand,sbase)
         :
  integer icos7(0:6)
  data icos7/3,1,4,0,6,5,2/                   !Costas 7x7 tone pattern
          :
        do n=0,6
           m=j+jstrt+nssy*n
           if(m .ge. 1 .and. m .le. NHSYM) then
              ta=ta + s(i + nfos * icos7(n), m)
              t0a=t0a + sum(s(i:i+nfos*6:nfos,m))
           endif
           tb=tb + s(i + nfos * icos7(n), m+nssy*36)
           t0b=t0b + sum(s(i:i+nfos*6:nfos,m+nssy*36))
           if(m+nssy*72.le.NHSYM) then
              tc=tc + s(i + nfos * icos7(n), m+nssy*72)
              t0c=t0c + sum(s(i:i+nfos*6:nfos,m+nssy*72))
           endif
        enddo

study fortran 少し勉強するかな。それにしても、ft8syncv8.pdf は、難解だな。