SHA256でデータが混ざる様を”混色”してみた

暗号学的ハッシュ関数、使ってますか。わたしはよく使ってます。たとえば、このブログでは画像のファイル名として、その中身をMD5ハッシュに掛けたものを使っています(そういうWordPressプラグインを作りました1

で、今日は暗号学的ハッシュ関数の中でもまだまだ現役のものの1つ、SHA256でデータが混ざり合う様を色を使って可視化してみました:

githubリポジトリはこちら:

今回はCanvas 2Dを使ってます。実際に動くデモサイト

入力は512ビット

SHA256は入力として512ビット( = 32bit × 16)の「ブロック」を単位としてを受け取りながら計算します。今回は便宜上、1ブロックだけ与えられた事にしました。左上の「input」の下にかかれている点々(512個あります)がその入力のビット列です。ビットには、それぞれに異なる色を塗って区別できるようにしてあります。

前準備

SHA256では、次の疑似コードにそって「w」と呼ばれる2048ビットの値を計算します:

create a 64-entry message schedule array w[0..63] of 32-bit words
(The initial values in w[0..63] don't matter, so many implementations zero them here)
copy chunk into first 16 words w[0..15] of the message schedule array

Extend the first 16 words into the remaining 48 words w[16..63] of the message schedule array:
for i from 16 to 63
    s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)
    s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor (w[i-2] rightshift 10)
    w[i] := w[i-16] + s0 + w[i-7] + s1

真ん中にある「w」と書かれている下の点々の塊の部分がそれです(上から下に行くにつれてiが増える方向になっています)。計算式を見ると分かるのですが、すこし前(w[i-15]とw[i-2])の値を混ぜ合わせながら計算されているので、下の方に行けばいくほど色が似たりよったりになって、くすんでいきます。

圧縮関数

wの計算が終わったら、SHA256では「圧縮関数」と呼ばれる、次の64回のループを行います(h0〜h7は素数の平方根の小数部分だそうで、つまり定数です)。

Initialize working variables to current hash value:
a := h0
b := h1
c := h2
d := h3
e := h4
f := h5
g := h6
h := h7

Compression function main loop:
for i from 0 to 63
    S1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
    ch := (e and f) xor ((not e) and g)
    temp1 := h + S1 + ch + k[i] + w[i]
    S0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
    maj := (a and b) xor (a and c) xor (b and c)
    temp2 := S0 + maj
 
    h := g
    g := f
    f := e
    e := d + temp1
    d := c
    c := b
    b := a
    a := temp1 + temp2

この時に出てくる、a〜hまでの変数を右に並べました。それぞれ32ビットの値なので、32個の箱が上から下に並んでいます。ステップごとに最初はがやがやしてた色が、途中ぐらいからくすんだ紫一色になっていくのがわかります。

出力

で、64回のループが終わったら、次のコードでh0〜h7を更新して、h0〜h7を連結して256bit(=32bit ×8)の「ハッシュ」が得られる、という仕組みになっております:

    Add the compressed chunk to the current hash value:
    h0 := h0 + a
    h1 := h1 + b
    h2 := h2 + c
    h3 := h3 + d
    h4 := h4 + e
    h5 := h5 + f
    h6 := h6 + g
    h7 := h7 + h

Produce the final hash value (big-endian):
digest := hash := h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7

虹色が紫になった

そんなこんなで、無事SHA256というポテトミキサーで混ぜ合わせたビット列は、元の虹色を失って、よくわからんくすんだ紫色の256個のビットとなりまあしたとさ。

なぜ紫色になるのか?

オリジナルの512個のビットの色を平均したら(80, 80, 80)になっているのは確かめたのですが、SHA256にかけてみたら(149, 81, 145)というくすんだ紫色になってしまいました。doubleの誤差のせいとかなのか、彩色ルール(後に書く)のせいなのか、そもそもそういうもんなのか、何か実装がバグってるのか、…それはよくわかりませんw

(一応、空っぽの入力を入れた時にWikipediaに書かれてるのと同じ値が得られる事は確認してあるので、バグではないと思うのですが…)

追記:色の塗り方の縦横を入れ替えると灰色になった

わからん、全然わからん。でもこっちのほうが見ていて楽しいですね。

参考:彩色ルール

二項演算子に関するルール

ビット同士で下記の演算が起こった時は、結果のビットの色はそれぞれの平均とする:

  • add(繰り上がりが有るときは、色は3ビットの平均)
  • xor
  • and

ただし、定数やゼロクリアされた後のビットなどは「無彩色」とし、これらと演算するときは平均する時には考慮しない

例:

  • 無彩色のビット同士で演算が行われたら結果は無彩色のビットになる
  • 無彩色のビットと赤色のビットをandしたら、同じ赤色のbitになる
  • 赤色のビットと青色のビットをxorしたら、結果は紫のbitになる

単項演算子に関するルール

not演算(1の補数)や単項マイナス演算(-x)、シフト演算が行われた時はビットの色の情報は変化しない。

  1. MD5はもはや暗号学的には全く安全ではないそうですが、べつに改ざんの検出を行いたいわけではなく、単に重複しないファイル名を考えるのを自動でやってほしいだけなのと、出てきた結果が20バイトと大変短いことから採用しています。 []

パースのついた円とマウスの当たり判定をする

本サイトの姉妹サイト、「妖精⊸ロケット」では、WebGLを使ってウェブサイトを作るという実験を行っています:

これは「季節の歯車」です:

「季節の歯車」って、いったいぜんたい、何なのかって?

季節が毎年毎年一周してるのは、みなさんもご存知でしょう。ちかごろは、もう桜も散ってしまいましたもんね。

ところで。

なんで季節がきっちり正確に毎年一周しているのか、不思議じゃありません?

実はですね、…ここだけの秘密ですよ。

「季節」を動かす歯車、「季節の歯車」が毎年なんとなく一周しているから、季節は毎年一回だけ巡るのです。

じゃあ、その歯車が回るのはなんでなのかって?

それは、春香、夏美、秋葉、冬音の4人の精霊たちが、いつもは仲良く、時にはケンカしながら、「せかいの裏」でくるくる回しているからです。これも秘密ね。

春の次に夏がやってくるのは、春香と夏美が仲良くやってくれたから。

夏の最中に突然秋みたいな日がやってきたり、季節外れの台風がやってきたりするのは、…きっと、夏美と秋葉がたぶんちょっとした事でケンカしたんでしょうね。

でも大丈夫。ケンカしたら、仲直り。いつもそうやって、季節は巡ってきたのですから。

季節の歯車

…という創作神話(?)を元に、この季節を決める歯車である「季節の歯車」と、その結果生まれる「季節の巡り」をWeb上で表現してみようとしたのが、このWebサイトです。

もう少し常識的に言うと、左上の「歯車」の円周上に、それぞれの季節ごとの写真や絵、文章が並んでいます(これを「モーメント(瞬間)」と呼びます):

春はピンク、夏はみどり、秋はオレンジ、冬は青。…うーん、変えてもいいかな。

ここみたいな、いわゆる「ブログ」と違うのは、時系列で並べているわけではないことです。例えば、同じ「10月1日」の「モーメント」は、10年前のものでも今年の物でも、同じ角度のラインの上に並んで表示されます。

さらに、どの「モーメント」が表示されるかは、毎回ランダム(ガチャ)です。10年前の「モーメント」が表示されて今年の「モーメント」が表示されない事もあるし、逆もある。角度は同じでも、歯車からの距離は更新するたびに変わります。この点でも、2018年のページをクリックすれば必ず2018年のページが表示される「ふつうのブログ」とは異なります。

WebGLでウェブサイト作ろうぜ

えー。「季節の歯車」の紹介はこれぐらいで置いておいて。この季節の歯車を表現するための技術について、がこの記事のテーマです。

このウェブサイトは基本的に全部WebGLと、素のECMA Script 6で書かれています。くるくると回る「歯車」も「モーメント」も、全部WebGLで描いていて、HTMLの<img>タグとかは使ってない、と言うことです。もちろん、WebGLはCanvasの中身をOpenGLで描ける、という技術ですので、他のHTMLの技術と、簡単に組み合わせることもできます。「季節の歯車」では、「モーメント」の上にマウスが乗ると、タイトルが表示されるようになっています。この表示に使われているのは、いつもの<div>要素です:

この「モーメント」はこちら

3Dオブジェクトの当たり判定

さて、これで困るのは、マウスの判定です。つまり、マウスがどの「モーメント」の上にあるのか(あるいは無いのか)のチェック関数、です。

HTMLのmouseoverイベントは使えません。「モーメント」は全て、HTMLの要素ではなく、1つのcanvas要素の上にOpenGLで描かれている「絵」に過ぎないからです。

canvas要素のmousemoveイベントを使えば、canvas上でのマウスの座標を得ることはできますが、この座標もそのままでは使えません。というのも、「モーメント」も左上の歯車と同様、「遠近法」が掛かっている立派な「3Dオブジェクト」だからです。

まぁ、わざわざ「遠近法が掛かっています」と上でわざわざ書いたように、事実上ほとんど掛かっていないので、2Dだと思って当たり判定を書いてもほとんど困ることはない(見ている人が気づくことはない)かもしれません。

でも、せっかくだから「正確」に判定してみたい。趣味のプロジェクトですしね。

さて、こういう「3Dのオブジェクトとマウスの当たり判定」じたいは、ゲームではよくることです。3D空間内のアイテムをマウスでクリックして取得したり。このためのテクニックは「Object picking」と呼ばれているそうで、よくある実装は、「当たり判定」のための専用の画面を作ってしまうというものです:

OpenGL Picking Tutorialから引用

まず、オブジェクトごとに相異なる色で塗った「別の画面」を作ります。この画面は、ユーザーには見せません。ただし、あたり判定をする時は、この隠れた画面からマウスの位置にあるピクセルを読んで、「何色」になっているかを調べます。この色が何色かで当たり判定をする、と。例えば上の例だったら、一番明るい灰色だったら右のチェス、真っ黒だったら背景(何とも当たっていない)、といった感じです。

うーむ。たしかに、チェスの駒とか、人間、動物みたいな、複雑な形のオブジェクトがたくさんある中から当たり判定をしたいならわかります。むしろ、この方法を取らざるを得ないでしょう。

でも、ただの「パースのついた丸」のためにこれをやるのは何だか大げさというか、資源の無駄遣いな気がします。単純に2回絵を描かないといけないですし。「相異なる色」を用意したり、半透明になったりしないように配慮した別の描画プログラムをもう一つ用意しないといけないのも大変です。

もっといえば、この「別の画面を用意して、あたり判定を行いたいオブジェクトごとに色を塗る」という力技で当たり判定ができるのは「当たり前」すぎるように感じられます。ちょっと面白くない。

そこで今回は、それとは別のアプローチを考えてみましょう。

「遠近法」のおさらい

その前に、まずコンピューター3Dにおけるいわゆる「遠近法」をおさらいします。

「いわゆる」とつけたのは、「遠近法」と言えそうなものは、このコンピューターの世界の中だけでもたくさんあるからです。わたしの考えでは、ラスタースクロールも遠近法ですし、ゼビウスのゲームシステムも、「空気遠近法」と同じくらいには、りっぱな遠近法だと思います。

とはいえ、「季節の歯車」では、コンピュータ3Dの世界で「遠近法」という言葉で指すものの中では最もおなじみであろう、「透視法射影」を使っています。

これはどんなものだったのか、と言えば、表示したいモデルの頂点の三次元空間上の座標、x y z、そして最後に1を立てたベクトル(x y z 1)に、モデルごとの変換行列Mを掛けて、出来たベクトルをさらに最後の要素( wと呼ばれる事が多い)で割り、出来た(x’/w’ y’/w’)が画面上での最終的な座標となるのでした。

わかりにくいので、ちょっとベクトルがどのように変形されていって最後のxy座標になるまでを図にしてみました:

それぞれの操作を、数学で写像で移される時元の対応を表す、のマークを流用してその処理の流れを表現してみました。えっ、数学の世界でそんなに繋げるような記法は普通しない?まぁまぁ。うまい表記が思いつかなかったので、おもいついた人は教えてくださいな。

行列Mについて少しだけ話をさせてください。このMをうまく作ることで、モデルの平行移動や、回転、拡大縮小を表現できるだけでなく、最後にw’で割るという、行列のかけ算だけでは表現できない非線形な操作と組み合わせることで、遠いものほど小さくなる「遠近法(パース)」が再現できます。上手く作る、といっても、glMatrixなどのいわゆる3D向け行列ライブラリを使えばそんな難しくないです。とりあえず、この話はまた別の機会にいたしましょう。

さて、元々やりたかった事は何かというと、パースの掛かった「丸」とマウスのあたり判定でした。

ふむ。残念ですねぇ。何がって?パースの掛かった「三角形」とのあたり判定だったらすごく楽だったからです。あたり判定の対象が三角形であれば、上の操作で作ったスクリーン上の3つのXY座標で囲まれた三角形の中にマウスの座標があるかどうかを判定するだけで済みます。とはいえ実はその判定はそこまで簡単でもないんですが、やること自体は直感的です。

一方、パースのかかった丸となると、どうすればいいのやら。斜めになってるとぐにゃぐにゃした形になっていて、何をどうすれば内側になるのか判定できるのか、よくわかりません。

スクリーン空間からモデル空間へ

遠近法をつけた丸はぐにゃぐにゃしてて、なんかよくわかりません。となると、遠近法を付ける「前」の丸とマウスの当たり判定を行う作戦を取らざるを得なさそうです。遠近法を付ける前なら、単に「円の中心とマウスの座標の間の距離が円の半径以下か」判定すれば良いだけですから、三角形の内側にあるかどうか判定するよりも更にラクです。まぁ、点と点の距離を調べるのも、実は言うほど簡単じゃあないんですが…。

閑話休題。そうなると、問題は「マウスのポインタは、元のモデル空間では一体どこに存在するのか?」になります。さっきの図はモデル空間からスクリーン空間の話でしたが、今度はその逆、スクリーン空間からモデル空間への話を考えねばなりません。二次元から三次元上の位置を推定しないといけないので、ややこしそうです。

一つずつじっくり追い込んでいきましょう。まず、モデル空間上にあるマウスの点を(xm ym zm)、液晶画面上のマウスの座標を(xs ys zs)とします。マウスの座標にZ軸なんか存在しないのですが、あとで計算するときに便宜上必要になりますので「未知だが、存在する、何かしらの数」として導入します。

さて、目からマウスポインタを結ぶ線は液晶モニタの平面を貫通し、最終的に液晶モニタの後ろにある(笑)1モデルへとぶつかります。図にするとこんな感じです:

これらの(xm ym zm)と(xs ys zs)の関係を、書いてみます:

この図自体は最初に描いたものとほぼ同じです。

なかなかややこしいので、wsという(未知の)変数を新たに導入した上で(といってもw’mのエイリアス)、まず波線を引いた部分を変形します。

行列を掛けて出てきた、素性のよくわからんx’m, y’m, z’mを、すでに分かっているxsやysなどにできるだけ置き換えいって整理しようという作戦です:

さらに波線のwで割ってる部分も、xs や ws を使って割ってない所まで戻します。

すると、「モデル空間上の座標に変換行列Mを掛け算して移すと、スクリーン空間上の値を使ったよくわからんベクトルができる」、という図になりました(少なくともわたしはそういう意味でこの図を書いてます)。波線の引いた部分は「矢印の左側でベクトルに行列をかけると矢印の右側のベクトルになる」、という意味で使ってますので、おなじみの等号に書き直します:

未知変数の部分に赤線を引いてみました。xm ym zs wsの4つが未知で、Mは4×4の行列ですから、この行列とベクトルの式は実際には4本の連立方程式です。未知数が4つで、式が4本。原理的には解けます。やったね。zmは未知じゃないのかって?あー、言い忘れてました。今回の丸は、モデル空間上ではXY平面上にあることにしましょう。なので、zmはzm=0の定数です。

さて、この式は前述した通り解けるので、xm ym zs wsを求めたら、zsとwsは単に便宜上入れた要らない変数なので捨ててしまいましょう。モデル空間上のマウスの座標である、xmとymを使えば、無事円との当たり判定ができます。

はいおしまい、QED。

と言いたい所だが、この行列は実際一体どう解いたらいいのか?右にも、左にも未知変数があります。逆行列を一発キメたら終わり、みたいな、そういう生ぬるい式ではなさそうなのは確かです。かといって、プログラムに組み込んで自動で解かなければならない以上、「頑張って手動で連立方程式を変形して解く」みたいな高校生的解法は使えません。捻りが必要です。

頑張って式を変形するぞい

まず確認です。行列とベクトルの掛け算とは、行列の各行ベクトルを、もう片方のクトルのそれぞれの値で重み付けをして足し合わせることだと見なすことができます。

左辺

まず左辺をこれを使って変形します。Mを、M1からM4までの4つの縦ベクトルが横に並んだものだとみなすことにしました:

右辺

次は右辺です。右辺は、まずwとx y zが掛かっていて複雑なので、wをくくりだします。

赤線を引いた未知変数がだいぶ減って気楽な感じになりましたが、まだベクトルの中と外に未知変数が入っていて扱い方がわかりません。さらにこれをこんな感じで2つのベクトルの和に変形します。

するとどうでしょう。右辺も左辺も、「「未知のスカラ量 x 既知のベクトル」の和」に変形できました。

なんとなく、これなら扱えそうな気がしてきません?

最後の一捻り

さっき変形した右辺と左辺の式を使って、再度等式を書いてみます:

するとただの和なので、簡単に未知変数を左辺だけに集約することができます:

で、ここで最後の一捻りです。

さっきの

行列とベクトルの掛け算とは、行列の各行ベクトルを、もう片方のクトルのそれぞれの値で重み付けをして足し合わせることだと見なすことができます。

というのを、今度は逆回しにします。つまり、こんな感じでもう一度「行列とベクトルの積」に書き戻します:

ここまでくれば、もう簡単。赤線が引いてある未知変数が詰まってるベクトルの値は、逆行列を掛ければ一発で求められます。

長かったですけど、纏めてみると結構綺麗な解法のような気がする。…どうかな。

JavaScriptで最小のデモ作った

「季節の歯車」だとここで実装してるんですが、流石に他のコードも多くてわかりにくいだろうという事で、この当たり判定の部分だけ切り出したサンプルを作ってみました:

github.com/ledyba/__sample__3d-picking-without-shaders
パースのついた円とマウスの当たり判定をする

実際に動いてるデモのページはこちら

  1. でも、最初にプレステのゲームを遊んだときは、そんな感じがしませんでした? []

ChromeでSVGを背景にすると遅い

ブログのタイトルに合わせて、月と夕焼けをイメージしたテーマを自作してブログの模様替えをしてみました。

ソースコードはgithubで公開中です:

ledyba/wp-lunar-theme: theme of 7io.org

作り方は割と簡単で、次のファイルを作り…

ファイル名用途
function.phpテーマの各テンプレートから参照できる関数
初期化、サイドバーの定義など
index.phpトップページの表示
page.php固定ページの表示
single.php各ブログ記事の表示
archive.phpアーカイブ(月別、カテゴリ別)の表示

さらに、これらから参照されるサブテンプレート用のphpファイルと、CSSを用意すれば完成です。

公式のWikiにあるドキュメントもよくまとまってます。詳細は公式をチェックだ(書くのがめんどくさくなった)。

SVGの背景が遅い、どうしようもなく遅い

問題はここからです。今回のテーマ作成のサブテーマとして「ラスター画像(SVG)しかテーマには使わない」という縛りをなんとなく課してみまして、背景もSVGで用意しました。左に見える月の画像もSVGです。

Firefoxから見ると何の問題もないのですが、Chromeから表示するとどうしようもなく遅い事に気が付きました。Ryzen Threadripperを使ってAMDのDiscrete GPUを使っても、フレームレートが落ちてるのが目で分かるぐらいに遅い。

計測してみると、1フレームを描画するのに100ms弱掛かっってました。これはいけない…。

しかもiPhoneでは背景が表示されすらしない。どうしようもねぇ〜。

mac OSのSafariだと見えるんですけどね、中身違うのかな

CSSで同じことをするとなぜか爆速になる

うーんどうしたもんか、と思って。CSSのlinear-gradient書き換えてみました

とはいえ、

メモ: CSS グラデーションにおける色経由点の描画は、 SVG グラデーションと同じ規則に従います。

linear-gradient() – CSS: カスケーディングスタイルシート | MDN

だそうなので、SVGと一緒ならやっぱ遅いんじゃないかなぁ、と思いながらダメ元で。

しかし…どういう事でしょう、Paintingに掛かる時間が70倍近く速くなり、ほぼ60FPSを達成できるようになったのです…(!?)

iPhoneからも背景がきちんと見れるようになりました:

スマホ、画面ちいさくね?マジでみんなこれ毎日使ってんの?

SVGにはまだChrome/WebKitには早すぎるのかもしれない

たぶんですけど、SVGを背景に設定すると毎フレームSVGからbitmapにラスタライズするんでしょうね。他にもWebKitはSVGは遅いと6年前に言ってる人はいて、とくに改善されないまま現在に至ってるようです。

…はぁ。EdgeもChromiumに乗り換えてしまったし、ラスター画像大好きおじさんには苦しい時代が続くかもしれません。

Firefox頑張ってくれ〜〜〜〜〜このブログはFirefoxとフォクすけくんを応援してます!一番好きなブラウザです(やけくそ)!

ffmpegでコマごとに表示時間が違うアニメを作る

ffmpegで静止画(pngとか)から動画を作る方法といえば、連番画像を使う方法が有名です:

ffmpeg -framerate 10 -i %03d.png -vf scale=784x1024 -vcodec libx264 -pix_fmt yuv420p -r 30 out.mp4

これを使うとすべての画像が同じ間隔で表示されてしまいます。上でいうと、000.pngも001.pngも002.pngも、全部0.1秒ずつ表示されます。

大半の場合はこれで困らないのですが、自作でアニメを作ったりしていると困ることがあります。たとえば、今回こんな感じの動画を友達と作りました:

首をかしげて, pixiv

このアニメは、最初のコマだけ1秒、最後のコマだけ3秒、他のコマは0.25秒表示されています。

こういうコマごとに表示時間が異なる動画を作るにはどうすればいいか、あんまり情報がなかったので備忘録的にメモって起きます。

1.jpegから5.jpegを使って上の動画を作るという設定で説明します。

githubリポジトリにデータ付きでアップロードしておいたので、よろしければそちらも参考にしてください。

タイミング情報を纏めたファイルを作る

file '1.jpeg'
duration 1
file '2.jpeg'
duration 0.25
file '3.jpeg'
duration 0.25
file '4.jpeg'
duration 0.25
file '5.jpeg'
duration 3
file '5.jpeg'

こんな感じのファイルをinput.txtみたいなファイル名で作成します。5.jpegを3秒間表示するために、最後にもう一度5.jpegを書いてる点はちょっと注意です(これを書かないと5.jpegが1フレームしか表示されません)。

適切にコマンドを実行する

ffmpeg -f concat -i input.txt -vf "scale=-1:1024" -vcodec libx264 -pix_fmt yuv420p -r 30 out.mp4

いくつか解説です:

  • -f concat を忘れないでください
  • scale=-1:1024を使うと縦1024ピクセルにした上で横幅はアスペクト比に応じて自動で決定してくれます。
  • -r 30は出力動画のフレームレートです。