2017年1月アーカイブ

アルゴリズム的には、ビット幅と生成多項式でバリエーションがあり、バースト誤りを検出しやすい。ハッシュ的ではあるが、改ざんには弱いので、セキュリティ目的では使えない。

実用上は、バースト誤りを検出しやすいことから通信路やバスでの化け検出に使われる。ビット幅・生成多項式ともに、よく使われるものは限られている、特にCRC-32-IEEE 802.3のものが狭い意味でのCRC32と解釈されていて、EthernetとかMPEGとかZIPとかに広く使われている。

このCRC32はRFCによくサンプルプログラムが乗っていて(例えばRFC3309の末尾の方)、下記ヘッダとともにcrc32.cのまま広くコピペされて使われている。

/*************************************************************/
/* Note Definition for Ross Williams table generator would */
/* be: TB_WIDTH=4, TB_POLLY=0x1EDC6F41, TB_REVER=TRUE */
/* For Mr. Williams direct calculation code use the settings */
/* cm_width=32, cm_poly=0x1EDC6F41, cm_init=0xFFFFFFFF, */
/* cm_refin=TRUE, cm_refot=TRUE, cm_xorort=0x00000000 */
/*************************************************************/

ちなみに、仕様上のCRC32は最初と最後で0xFFFFFFFFでXORするが、サンプルプログラムではこれをしていない。Ubuntuにはcrc32の名前のプログラム(というかPerlサンプルスクリプトというか)が入ってるので、これの結果と比べてみるのがよい。

ただ、今時の32bitのCPU(ARM cortex-Aとか)だと実はこのままでは遅い。どうせコピペするならzlibのcrc32.cあたりから持っていったほうがよい。1byteでwhileループを回しているとこを、4byteのループアンローリング込みにしていて、手元計測でおおむね40-50%くらいの実行時間になった。zlibなので「zlibからコピペして使った」と書きつつzlibライセンス文のコピーを載せとけば著作権的にも問題ない。

x86系CPUでは、SSE4.2よりcrc32c命令が加わっている。上記の広く使われているCRC32ではなくてiSCSIとかに使われているものではあるものの、専用命令を使えばさらに高速に処理できる。c++ - Implementing SSE 4.2's CRC32C in software - Stack Overflow

AESも専用命令が作られたりと、汎用コンピューティング性能が上がらない今日では、ソフトの実装で最適化するにも限界があるので、どうせソフト対応入れるならこういう方向専用命令使ったasm化がトレンドなのかもしれない。

ちなみに、zlibやってるとよく見かける「Adler-32」は、zlib作者の1人のマーク・アドラーさんの名前らしい。カッシーニとかマーズ・エクスプレスとかに関わっているそっちの人ということらしい。

※ 2017/02/22(Wed)追記:
CRC32のベンチマークに特化したサイトがある。そこにある「git clone http://create.stephan-brumme.com/crc32/.git」はgitレポジトリがなかったのはご愛敬として、サンプルをベンチマークしてみた結果、
● x86_64だと、「16 bytes at once」は確かに早い(最速)。zlibやつは「16 bytes at once」よりは遅いが「8 bytes at once」よりは早い
● arm64だと、「16 bytes at once」も「8 bytes at once」とあまり変わらず。zlibやつの方が早い。
となった。zlibのは固定テーブルをconst参照するから最適化が効きやすいんだろうか。ちなみにzlibのはアルゴリズム的には「Slicing-by-4」でいいみたい。というわけで、zlibのをコピペするのが安心でオススメ。

URLに「&lr=-lang_ja」を足せばよい。「-」(マイナス)である点に注意。

Googleで検索すると、アクセスもとIPアドレスやら言語設定やらを参照して、検索結果の表示を勝手に日本語ページ優先にしたりします。激しくうざいです。特にゴミのような日本語サイトしか見つからない場合に。

昔は検索設定から言語を絞り込めたと記憶してるけど、今確認するとGoogleサービスを表示する言語と検索結果の言語が連動してしまっているようで、Webサービス的には日本語以外を検索するための方法がないように見える。というわけで、手動で「&lr=-lang_ja」を足しましょう。

LinuxKernelNewbiesのchangelogのSummaryを日本語訳したものと、いくつかの重要な機能を解説したコラムとがまとめられた薄い本。日本語で書かれている割に内容は濃く、コアなKernel開発者向けになっている。

Amazon Kindle Unlimitedで読める本をなんとなく眺めていた時にたまたま見つけたんですが、これって低級はっかーズさんがコミケで頒布した本を電子書籍でAmazon販売してるんですね。以前きつね本でも驚いたんですが、まぁそういう時代なんですね。ただ私のような素人からすると、インターネットのなかった時代ならともかく、今の時代なら手間暇かけてコミケ頒布するより適当にブログにでも書き散らした方が楽なんじゃ・・・と余計なことを考えてしまいます。

内容は、いたって硬派なLinux Kernelに関するものです。本とはいえ薄い本なので、雑誌のコラムを読むような感じかなぁ。とはいえ、最近は雑誌でもLinux Kernelを題材にしたものが皆無に等しいんで、そういう意味では貴重な本です。最近はこういう情報は英語サイトを漁るしかないような状況なので。

というわけで、Linux Kernel情報を漁りたいんだけど英語はちょっと・・・という方にオススメです。

● 名前偽装ネタ
ネタもと
・$0書き換えが流行っているようなので一つ流行に乗っかってみるか
・psで表示されるコマンド名を変更する

・/proc/(PID)/comm は書ける(rw)
・/proc/(PID)/cmdline は書けない(r)
・cmdlineは、pthread_setname_np(3)(libpthreadの中で結局prctl(2)のPR_SET_NAME)で設定できる。
・cmdlineは、直接argv[0]@argcを書き換えてもよい。が、argvのバッファ管理までは手を出せないので長さ変更するのは注意
　→ argvはexec時にKernelがユーザスタック上に確保する
　　(正確には、ユーザスタックに化ける前のメモリ領域に確保する)
　→ __bprm_mm_init()あたり。この辺に詳しい

● zlib関係
以前紹介した圧縮ツールの記事から、zlib関連をちょっと漁ってみた。
・zopfliは確かに圧縮率が高い(3%ほど削れる)、が圧縮に時間かかりすぎなので、ビルド毎に走らせるのはつらい。。単純に*.gzと*.png作成に使うのかなぁ。pngの再圧縮はパッケージに付属するzopflipngで行える。png再圧縮はoptipngとあわせて使うとさらによい。
・cloudflare/zlibは、x86_64のSIMD前提で、x86_64以外はコンパイルすら通らなかった。
・intel/zlibは、x86_64じゃなくてもコンパイルは通るものの、やはりx86_64のSIMD前提。
・zlib-ngは、x86_64のSIMD前提だけど、x86_64じゃなくても恩恵を受ける。minigzipベンチでオリジナル比で3%ほど早くなる。
というわけで、x86_64以外なら、とりあえずzlib-ngを使えばいいと思います。zlib-ngは他arch対応の準備も形だけはできているので、誰かがNEON対応を書けばarm/aarch64も早くできるんじゃないかなぁ(他人任せ)

● その他
prctl(2)はLinux固有のシステムコールだけど、いろいろできることが多いので一通り確認しておいた方がよい。
・PR_SET_CHILD_SUBREAPER で、子孫の孤児になったプロセスを引き取る init っぽいことができる。
・PR_SET_PDEATHSIG で、親が死んだ時に子どもにシグナルを送れる。SIGKILL 登録しといて親が死んだら子どもも即死というパターンで使うのが多いみたい。

上記使えばinitっぽく見えるinitじゃないプログラムを作れる。が、PIDは1になれない。pid_namespaces(7)を使えば、namespaceの中からはPID 1に見えるが、namespaceの外からはPID 1になれない。まぁそこまでごまかせたらセキュリティホールそのものなので、できないのは当然ていえば当然だけど。