WindowModePatch 0.68 Alphaを公開

実はこの記事を書く時点で公開してからすでに一週間経過していたりするのですがそれはおいておきましょう。前回の更新から半年前後経過していて忘れ去られていたのかといえばさにあらず。いまだけ時間を作ることができる状態だったことと気になったプログラムが残ったままになっていたので自分でサンプルを作って仮想マシン上で動作をテストすることで修正点を見いだすというマッチポンプではないけれども似ているようなことを二週間前くらいから行って更新にこぎ着けました。

 

主な更新は二つ

基本的には以下になります。

  • DirectDrawをDirect3Dでエミュレーションを行う場合に8bitパレット処理における互換性の向上
  • パッチ対象の拡張子がexe,dll以外である場合に処理が行うことが非常に困難であったので修正

サンプルプログラムを作ってテストしていたのは前者で特に文字列描画で文字色が本来白色にならなければならない場合での互換性が向上しているはずです。検証プログラムを詳細に書いてみて初めてわかる仕様というのもあるのですね…。後者は特に外部モジュールを読み込んで動作するタイプの場合に本体に非推奨の完全パッチ処理を行いライブラリのロード時に強制的にWindowModePatchを読み込ませるか外部モジュールそのものにパッチ処理を行うか…という選択肢で外部モジュールの拡張子がdllではなかった場合にリネームしないとパッチ処理ができないのが面倒ということで処理を変えました。元々パッチ処理では対象が実行ファイル系かどうかの判別が入っているので問題はないのですが、実際にそういうことが必要になるゲームに出会うとさすがに変えたくなるということだったりします。

 

付け加えようとしていた機能はなんだろう?

機能の追加については数ヶ月前に思い立ったことなのでどうしようとしたか今の自分には理解できない…じゃなくて。おそらく途中で解像度を切り替える機能とかのはずなのですが機能が中途半端に実装されているので今回の更新では対象としていません。というか数ヶ月前の私は最終的にどの形にして実装をするつもりだったのか、について今の私にはわからない、という状態だったり。おそらくは対象のゲームと関係のないキーの組み合わせを入れると別のダイアログが表示されて画面の解像度をリストから選ぶか入力するか、という感じだと思うのですが…。まあ、余裕があれば適当に実装してみたいと考えてはいます。

 

自分一人での更新も難しくなってくるのかな

フリープログラマというのも自分で宣伝できなかったり仕事を受ける人脈がない場合はフリーターより悪い状況と見えるので真面目に職に就こうかと思い活動しています。そうするとこのWindowModePatchのメンテナンスも全くできなくなる、ということになる予感がしておりもったいないような気がしているのでいろいろと方策を考えています。信頼できるほかの人にソースコードを更新できる権限を持ってもらって対応できるゲームを増やしていったり情報を集めたり、などですね。

なお、WindowModePatchに関するWikiもこのサーバー内に設置してあり、容量制限もつけたのでデザインが整ったら…と思っていたのですが使っているWiki(MediaWiki)が昔に記事を書いたときから見るとかなり更新されてしまったためにどうしても情報を書くときに使おうと思っているWikipediaのテンプレートであるInfoboxが正常に取り込めないという問題にはまっていて抜け出せないのですね。はてさてどうするのがよいのでしょうか…。

 

Hash Calculator 0.02を公開

というわけでハッシュ計算につきまして新規にいくつかのアルゴリズムを実装すると同時にバグ修正を行いましてHashCalculatorを更新しました。なんと初期公開が2012年末ということで4年以上間隔が空いているのがびっくりというところです。

 

計算可能なハッシュアルゴリズムの追加および更新をしてみた

一つ前の記事で自分のライブラリに追加する、という話は書いていたと思いますがアルゴリズムを追加するということはHashCalculatorも更新できるネタができた、ということだったのでマイナーなアルゴリズムだけではなくもう少しメジャーなアルゴリズムも追加してみました。今回追加したのは

  • BLAKE(224bit,256bit,384bit,512bit)
  • BLAKE2b,BLAKE2s
  • SM3

の3種類になります。BLAKEはSHA-3の公募が行われたときに最終候補にまで残ったアルゴリズムとして有名でBLAKE2系はそれの改良系であり、MD5並みの計算速度を持つということを売りにしているアルゴリズムです。SM3は中国で標準のハッシュ処理として計算方法が公開されているもので中国圏で開発されている規格などでハッシュ処理を使うときによく使われている形式となっています。BLAKEについては公募の関係でドキュメントなどもかなり豊富にあるのですがSM3は範囲がかなり狭く国が公開している中国語の物かIETFが公開しているドキュメントくらいしかないようでIETFのものがあるとは知らず実装テストが終わるまでずっと中国語のドキュメントを訳してやっていました。まあ、数式の部分は共通ですし訳す必要がある部分も中国語の文法などを簡単に知っていれば漢字の意味をある程度共通にとれるので難しくはないところがありがたかったです。

 

KeccakとSHA-3の計算方法は「終端が微妙に」違う

「皆さんも気をつけましょう」という話題です。SHA-3のアルゴリズムは本家であるKeccakをそのまま使っていますが最後のメッセージパディングの部分が微妙に違います。これはSHA-3の仕様をちゃんと確認してみるとよいですがKeccak本体だとメッセージパディングは数式を使わず言葉で書くと

1を追加して0を(ブロック長ビット数-1)まで追加後最後に1を追加する

ですが、SHA-3だとSHA3-nとSHAKEnでは

SHA3-n:01を追加してkeccakの終端処理(1を追加して…)を行う

SHAKE-n:1111を追加してkeccakの終端処理(1を追加して…)を行う

となります。このあたりは仕様書をちゃんと読んでおく必要があると思いますので気をつけてください。多分以前に作ったサンプルだとKeccakの終端処理を使っているために間違っているような気がしないでもないです。

 

中国の暗号化規格であるSMnって複数あるのですね…

SM2とかSM3とかSM4とかあるようです。多分日本語のサイトで言葉を検索すると全く違う単語に引っかかるでしょうね。私も時々「三國無双」の略称じゃないの?と考えしまうこともあるくらいですから。ちなみにそれぞれ

  • SM2:楕円曲線を使った公開鍵暗号方式
  • SM3:SHA-256相当のハッシュ関数
  • SM4:ブロック構造を使った共通鍵暗号方式

となっています。最新の規格もあるようですが今回はそこまでは見ていません。「中国製のCPUで処理に対応した、という記事を見て実装してみたいと思った」というなんとも微妙な動機でやり始めた今回の拡張ですがこの数年間で暗号にまつわることも大分発展したのだな、と思いました。なお私個人だと暗号に用いられる数学の根本的な部分を学びましたので楕円曲線でなぜRSA暗号が成立するのか?といった部分もいまなら説明できるようになっています。

 

ついでにコンパイラのバージョンもアップ

VisualStudio2005からVisualStudio2010に変更しまして対応OSもWin8系およびWin10系を追加しました。これが今回の副産物ですね。数年前にVisualStudio2005で作成して公開したきり一度も更新していないプログラムが複数ありますがそれもやった方がよいのかな…と思っているところです。

SM4(formerly SMS4)を実装してみた

久しぶりのプログラムネタです。題名を見ても「は?」としか思われないかもしれませんね。

 

SM4(formerly SMS4)とは

おそらくこれの意味がわからないと思いますので説明を。SM4を単体で検索してもまともに出てこないですしSMS4で検索すると今回のものとは全く無関係のことが出てくるほどマイナーなアルゴリズムですので。

このアルゴリズムですが実はブロック暗号アルゴリズムの一つで中国ではよく使われている形式です。中国国内で使われる無線通信の暗号形式として登場することが多いようで、これを実装してみようと思った理由がVIAもといCentaurの流れを汲む8コアx86 CPUが中国で登場していた模様 – やじうまPC Watchの記事を読んでいるときにSMS4が追加サポートされたという部分があり、「どういうアルゴリズムなのだろうか?」というところからどうせなのでプログラムとして実装してみよう、という流れでやってみました。

なお、ドキュメントなどを探せばわかると思いますが本来のアルゴリズムを説明した文章は中国語(汉语)で書かれていてそれを英語に翻訳したものが別に存在しています。ほとんどの人は英語版を読めばよいと思いますが中国語(汉语)が読めるのであればそちらのバージョンを読んでみてもよいと思います。汉语を少しですが勉強していたので読んでみたのですが、読み方はわからない漢字が大量にあっても文法がある程度理解できるようになったので意味を大筋で理解できるのが面白かったですね。

 

アルゴリズムはXOR、SBox置換、巡回シフトを1ラウンドとした複数ラウンド構成

暗号キーの作成も暗号化の手順もほぼ同じ手順(線形処理である巡回シフトの式が異なるだけ)で、かつ処理の構成の方法から暗号キーから内部暗号キーを作り出してしまえば暗号と復号は内部暗号キーを使う順番が逆になるだけ、という至ってシンプルなアルゴリズムです。何回か暗号処理を実装した人であれば最適化を考えなければ数時間で完了できるほどのものです。

一部面倒なのはこの手のアルゴリズムの実装では当たり前の話なのですがエンディアン処理をうまくすることです。巡回シフト演算の関係で32bitワードの状態での演算が必要でその部分がビックエンディアンで行う、という定義なのでリトルエンディアンを前提としたコードだとどの部分に変換処理を入れる必要があるのか、を正しくすることが重要になってきます。この部分に気がつくのに時間がかかったために資料に記述されている例と状態が合わないために四苦八苦しました…。

 

実装しても使い道が…

まあ、中国語(汉语)のドキュメントを直接読む機会となりよい経験ができた、というところでしょうかね。もちろん普通のブロック暗号なのでCBCなどと組み合わせれば普通にファイルの暗号化もできるのですが、だからといってゲームのアーカイブなどに使ってみても意味がなさそうですし。それ以外だと一からプログラムを組む機会が少なくなっていたのでそちらでもよい刺激になった、というところで。

もしコードを見てみたい、という人がいればコメントにでも書いてもらえれば追加で記事にするかもしれません。

 

「1.1の8乗は2より大きい」を何パターンで示せるか?

というわけで数学遊びです。範囲としては数Ⅰ+数Aの知識でいけるのでそのあたりのテスト問題とかに出そうだな~ということでやってみています。証明が面倒になるものも含まれていますので気になる高校生の人は見てみるとよいと思います。なお、この記事を書く前にどうせならWindowModePatchの記事とかサーバーの更新の記事とかを入れておけば面白かったかな~と思わなくもないのですが、Twitterに書いたのでこちらを先にしました。

 

正式な問題はこの形

Twitterにもつぶやきましたが問題を解く前に意図を確認するために書いてみます。

Q. 1.1の8乗は2より大きいことを示せ。ただし直接計算を行う場合は正確に行うこと。また累乗の数の大小関係は証明されていないものとする。

実は問題が微妙にいやらしいのが面白いところ。これが例えば「1.001の750乗は2より大きいことを示せ。」という問題であれば解法は限定されるのですが手計算できるところに押さえられているのがミソです。そのために「直接計算を行う場合」の注意書きを入れてあるわけです。そして最後の意味は「概算の形で計算したいなら累乗の大小関係について証明した上でやりなさい」という意味をいっています。この部分は解答を見た方が意味がわかると思います。

ちなみにこの問題の形は自然対数の極限を考える段階で現れる問題の変化系となっていいます。そのため、その部分に入る前に宿題として出しておいて…ということも考えられる問題という意味も含まれています。

 

私が考えた解答は以下の3パターン

一つずつ紹介していきます。

直接計算パターン

A1. 値を直接計算して求める。

ちょっと面白いのが4乗までであればパスカルの三角形を考えればよいので何も考えなくても計算できるけれども5乗以上となると手計算では難しくなるところですね。これを考えた人は最後まで間違わずにできたでしょうか。(「直接計算を行う場合は正確に行うこと」に注意)

 

間接計算パターン

概算の形で計算するものです。問題文より累乗の数に対しての大小関係を証明した上で行います。

A2. 累乗の数に対する大小関係として以下の命題を証明する

Th2. となるa,bと自然数nに対して

Pr2. 数学的帰納法を用いる。

n=1のときはa>bとなり仮定より満たされる。を仮定すると

よりとなり

よって数学的帰納法より題意は示された。

 

A2.1 1.12 = 1.21 よって 1.18 > 1.24, 1.22 = 1.44 よって 1.18 > 1.422, 1.422 = 2.0164 よって 1.18 > 2.0164 > 2

A2.2 √2 = 1.41… よって 2 < 1.422, √1.42 = 1.19… よって 2 < 1.204, √1.20 = 1.09… よって 2 < 1.18

A2.3 1.14 = 1.4641 √2=1.41… よって (1.14)2 >(√2)2 よって 1.18 > 2

大小関係の証明がないと不等号の部分が正しいという根拠を失ってしまうわけですね。そのため証明が先に必要になります。証明の部分は今回の問題で必要となる範囲でのみ証明がされていればOKなので指数の部分が自然数のみとなっていたりしています。あとは問題の状態が満たされるように概算を行っていけばいいわけですね。このときに8が23ということをうまく使っていくのが美しいところでしょうか。なお根号に関する計算はテスト問題で処理する場合のために開平方で計算しているという仮定です。そのため有効桁は3桁が確定すれば次に進む、という手順で行います。

 

二項定理パターン

高校生レベルならこれを使って示してほしい、という意味の問題でした。解答はこちら。

A3. 二項定理を用いると

よってx=0.1,n=8を代入すると0以上8以下の整数kにおいてであり、

こちらの場合は数列の極限とかいろいろなことを考える前段階の証明として一度はやっておいた方がよいと思われるものです。似たような証明であればテスト問題や入試問題にも出るかもしれませんね。ということをわざわざ国立大学の前期日程の試験が終わった後で書かなくても…

 

数学を使って考えることができたでしょうか

今回は大きく分けて3パターン(間接的な方法ではさらに3つ)で示してみましたがほかに考えついた人はこの記事のコメントにでも返していただけるとありがたいです。なお、二項定理パターンはほかにも理科系(主に物理)科目の計算で1より微妙に大きい数や小さい数を近似するときに使うパターンでもあるので知っておいて損はありません。

…で、こういう問題を考えていると思うことは直接計算しなくても示すことができる問題というのはいろいろとある、ということです。現実世界でも直接答えを示せなくても間接的に示したりする例もあることですので知っておくとよいことがあるかもしれませんね。

 

Windows10でSage(SageMath)を使う (Bash on Ubuntu on Windows編)

いろいろと試していた結果やっと環境が固まってうまく動くようになったのでその記録として記事を書いてみたいと思います。以降の自分もいろいろな用途でSageを使うことになると思いますし、それ以外の人でこれを使って何かする人(後で解説)もかなり有用だと思います。

 

Sage(SageMath)とは

公式サイトを読んで見るなりWikipediaを調べるなりすればよいと思いますが数学の幅広い処理を扱うソフトウェアで計算機代数などを使用することができます。今現在の主な用途としては数値計算や計算機代数など計算機を使う数学において研究目的で使用されます。この場合ですと数学系の課題研究で担当の教授から紹介されたり代数学の論文でこのような計算方法で行います、という場合にSageのコマンドで紹介されていることがあり以降自分の研究を進めていく上で必要となることが多いようです。

もう一つ面白い使い方としては線形代数や数式処理も行うことができるため高校レベルまでのちょっと複雑な数式について数学の先生が答えから逆算して問題を作成したり、テスト問題を考えたときに解答が正しいかどうかをチェックしたり…という用途に使用できるのではないかと考えています。逆に考えると高校生が横着して数学の宿題についてSageで出した解答をそのまま持って行く、なんてことも考えそうな気もしています。高校生が使うのであれば途中式を書いて計算はしてみたけれど答えを提出する前に確認したい、という用途では使ってよいのでは?と考えていますがどうなのでしょうね。

なお、現在の正式な名称はSageMathと呼ぶようです。インストールするパッケージもsagemathという名前で書かれているようですので気をつけていきましょう。

 

Bash on Ubuntu on Windowsの環境を整備する

Windows10において2016年8月に公開されたAnniversary Updateですが、これの大きな更新の一つとしてBashをWindows環境で利用できるようになった、というものがあります。BashはLinux環境における代表的なシェル(この場合はOSとユーザーをつなぐ役割ととればよい)で、これのおかげで一部のLinuxのプログラムを余計な変換なしにWindows上で扱うことができるようになりました。昔からLinuxとWindowsを併用してきたユーザーから見ればかなりうれしい更新です。今回はこれを使うことにします。

Bash on Ubuntu on Windowsの環境を整備するのはいろいろなサイトで紹介されているので詳しい点はそちらに譲るとして簡単に説明すると作業は以下になります。

  1. 画面左下にあるWindowsのロゴを右クリックしてメニューより[コントロールパネル]を選択。[プログラム]=>[Windowsの機能の有効化または無効化]より[Windows Subsystem for Linux (Beta)]にチェックをして有効化する。(更新により再起動が必要になることもあり)
  2. 設定の[更新とセキュリティ]から[開発者向け]を選択してアプリの受け入れに関して[開発者モード]を選択する。
  3. 画面左下にあるWindowsのロゴを右クリックしてメニューより[コマンドプロンプト]を選択。プロンプト上で
     > bash 

    (先頭の>はプロンプト状態を表すもので実際には入力しない)と入力する。以下開発者のみの機能であることに同意した後Bash上のユーザー名、パスワードを入力して環境構築が行われる。

インストールにはしばらく時間がかかりますのでのんびり待ちましょう。環境の構築が完了するとスタートメニューにBash on Ubuntu on Windowsのショートカットが作成され、そのショートカットで起動すると上記のユーザーでログインした環境から処理が始まる、という状態になります。

ちなみにBash on Ubuntu on WindowsのインストールによってBash上で動くプログラムをgccなどのコンパイラによって作成することもできるのでC言語での簡単なプログラムも作ることができます。こういう目的で環境を構築するのもありかもしれません。

ただし、Bash on Ubuntu on Windowsの環境はWindows本体とは異なり自動では更新されません。そのため環境を構築していろいろなことをやるのであれば定期的にアップデートを確認して環境を更新していく必要が出てきます。環境の更新はインターネットへの接続が確保できている状態で

 $ sudo apt-get update 

というコマンド($はターミナル状態を示すもので実際には入力しない)で行います。また、この環境内ではマシン名の名前解決ということでsudoを使う場合などで変な警告を表示されることがあるので/etc/hostsに自分のマシン名(起動直後の表示では[(ユーザー名)@(マシン名):~$]となっているのでそれを目安に)をviなどで先頭行の127.0.0.1の後ろに書き加えてしまいましょう。

以降はBash on Ubuntu on Windowsを起動した場合はその窓のターミナルはUbuntuのコマンドラインだと思って作業することがある程度可能です。すべてのソフトウェアがあるわけではないのでapt-getで取得できないものはコンパイルがうまくできればなんとかなるかも、というレベルです。そのあたりは自己責任で。

 

XmingでGUIウィンドウが使えるようにする

SageMath本体には直接影響はしないのですがこれが使えるとグラフなどを見せるときに非常に楽になります。特にSageのコマンドライン上から描画命令を発行したときにXmingが正常に動いていればxdg-openコマンドを経由して(内部の関連付けにもよりますが)ImageMagickが呼び出されて最終的にXmingにより画面上にウィンドウが表示されます。これがないとSageからの画像表示を行いたい場合に一度ファイルへ出力した後それをWindows領域から見やすい場所にコピーして画像ビューワを使う、という手順となりかなり面倒になります。ちなみにこれを入れておけばgnuplotも表示できるのでその意味でも数学の授業で扱うことを考えたり…ということもあります。

 

インストールの手順としてはBash on Ubuntu on Windows + XmingによるGUI – Qiitaが詳しいのでそちらを見てもらえばよいですが、簡単に手順を書くと

  1. 公式サイトよりXming-6-9-0-31-setup.exeとXming-fonts-7-7-0-10-setup.exe(記事を書いている時点)をダウンロードしインストール
  2. Xmingを起動する。以下一度シャットダウン処理やXmingを終了させてしまった場合は表示させる処理の前にXmingを起動させること。
  3. 環境変数DISPLAYにXmingのサーバー値を設定する。通常は0.0なので
     $ export DISPLAY=localhost:0.0 

    というコマンドを実行する。必要であれば.bashrcの終端にこの命令を記述しておくと状態が登録されるので楽になる。なお、.bashrcに登録されている場合はウィンドウを開いた後でXmingを起動させてもうまく表示されることがある。サーバー値が間違っていれば失敗するのでそこには注意すること。

となります。ちなみに参考にしたページではxeyesを使ったチェックをやっていますがこちらの場合はこの後SageMathをインストールしてチェックするのでそのタイミングでやってもよいと思います。(うまく表示されない場合の切り分けのために先にテストしてもよい)また、LXDEとVNCを併用してGUI環境を作り出す方法もありますが今回そこまでする必要はないと思いますのでこういう方法を使っていきます。

 

SageMathをインストール

SageMathの場合は本体がPythonで記述されているため今回の場合はほとんどの機能をインストールすることができます。ただ、Ubuntuの公式サイトからパッケージを取得する方法ですとうまくいかない場合があるのでリポジトリから作業を行います。こちらは以下のコマンドを実行することでインストールすることができます。

$ sudo apt-add-repository ppa:aims/sagemath
$ sudo apt-get update
$ sudo apt-get install sagemath-upstream-binary

注意点としては容量がかなり大きい(5GB前後ある)のでWindowsの本体ドライブにそれだけの空き容量が必要であること、またかなりのサイズのデータをダウンロードするため時間がかかることです。数時間くらいかかることもありますので気長に待ちましょう。

 

SageMathの初期環境を構築する

インストールが完了すればSageMathを起動させて初期環境を構築します。といっても一度目の起動の場合は勝手に環境を構築してくれるのでそれを待つだけです。つまり、

$ sage

と入力すればOKです。なお、完全なLinux上で動作している訳ではないためSageMathを起動させるたびにRuntimeWarningが出てしまいますがそれは無視しても問題ないと思います。

 

SageMathの画像表示チェック

最後に画像が表示されるかどうかを確認して完了です。適当にグラフをplotしてみればよいわけですが、わかりやすくcircle命令を使います。例えば

 sage> circle((0,0),1)

としてグラフとして中心(0,0)、半径1の円が描かれたグラフが表示されるかどうかを確認します。デフォルトであればおそらくImageMagickが起動してXming経由で画像ファイルを表示します。コマンド実行後しばらくたっても画像が表示されないときはターミナル(SageおよびBash)をいったん終了させて再度起動させてみてください。それでもうまくいかないときはWindows本体を再起動させてXmingを起動させた上でSageMathを起動させて確認してみてください。ここまでやってうまくいかないときはXmingの表示テストにより単体で動作することを確認する必要があると思います。もしかするとeogをインストールしておく必要があるかもしれませんが…。

 

SageMathで数学Ⅰや数学Ⅱにありそうな問題を解いてみる

ここからは遊びです。例えば代数学の問題(数と式など)をやってみます。

Q1. を因数分解せよ。

A1. SageMathで以下のように入力して答えを得る。

sage> a,b,c=var('a b c')
sage> y=a*(b^2+c^2)+b*(c^2+a^2)+c*(a^2+b^2)+2*a*b*c
sage> factor(y)
(a + b)*(a + c)*(b + c)

よって解答は(ちょっと並び替えを行うと)

Q2. を計算せよ。

A2. SageMathで以下のように入力して答えを得る。

sage> y=sqrt(3)/(sqrt(3)-sqrt(2))-sqrt(3)/(sqrt(3)+sqrt(2))
sage> y.simplify_full()
2*sqrt(3)*sqrt(2)

よって解答は(根号の数を整理して)

Q3. 方程式を解け。

A3. SageMathで以下のように入力して答えを得る。

sage> y=x^4+x^3+2^x-4
sage> solve(y,x)
[x == 1, x == -2, x == -I*sqrt(2), x == I*sqrt(2)]

よって解答は(iを虚数単位として)

見事に途中式を無視して解答だけ出してしまったパターンとなってしまいました。これで数学の宿題として先生に提出したらほぼ確実にやり直しですね…。なお、記事を書いているときに書いている当の本人が本当にこんなことができるのだ、と妙な感動を起こして笑ってしまったのはおいておきましょう。

上記では問題を解く方向でやりましたが問題を構築するとき(例えば因数で表された状態の式を展開して問題にする)もexpandなどでかなりうまくできます。なお、根号の状態など一部の処理は(A2のように)必ずしも簡単になるとは限りませんので解答が出た後で整理するなどが必要だったりそもそもその式をうまく表現できない場合がありますのでそこまで期待しない方がよいでしょう。もちろん研究にSageMathを使う場合は普通に必要な処理を使っていってください。