カテゴリー: 技術的なこと

起こった問題

こういうやつ．

\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{algpseudocode}

\begin{algorithm}[tbh]
    \caption{疑似コード}
    \begin{algorithmic}[1]
        \REQUIRE hoge
        \ENSURE hoge
        \Function {main}{ $void$ }
            \State $ N \leftarrow 1 $
            \State hoge$ \leftarrow $ foo\_class(initial\_setting)
            \State hoge.execute(OBJECTIVE, N)
            \PRINT hoge.best\_value
        \EndFunction
        \Function {objective}{ bar }
            \State $ a \leftarrow 1 $
            \RETURN a
        \EndFunction
    \end{algorithmic}
\end{algorithm}

解決法

原因としてはパッケージが混在しているのが良くなかった^[1][2]．

• algorithmic パッケージを削除する
• 大文字のやつを小文字に置き換える（\REQUIRE → \Require など）
• \Print などは無いため，\State \textbf{print} （もしくは \State \PRINT）で置き換える

\usepackage{algorithm}
\usepackage{algpseudocode}

\begin{algorithm}[tbh]
    \caption{擬似コード}
    \begin{algorithmic}[1]
        \Require hoge
        \Ensure hoge
        \Function {main}{ void }
            \State $ N \leftarrow 1 $
            \State hoge$ \leftarrow $ foo\_class(initial\_setting)
            \State hoge.execute(OBJECTIVE, N)
            \State \textbf{print} hoge.best\_trial
        \EndFunction
        \Function {objective}{ bar }
            \State $ a \leftarrow 1 $
            \State \textbf{return} a
        \EndFunction
    \end{algorithmic}
\end{algorithm}

参考サイト
[1] algorithmicxを使いLaTeXに擬似コードを追加 – Qiita
[2] how to remove the end for =0 in latex algorithm? – Stack Overflow

プラグインのアップデートを行った際に WordPress の管理者画面に遷移出来なくなって焦ったので備忘録として書き残す．

プラグインをアップデートした後，管理者画面に遷移しようとすると以下のエラー画面が出た．

設定ファイル（wordpress/wp-config.php）でデバッグモードをオンにして再度エラー画面を開くと EWWW Image Optimizer というプライグインが悪いことが分かった．

プラグインを消す．

rm -rf wordpress/wp-content/plugins/ewww-image-optimizer

解決．

参考文献
[1] WordPress で「サイトに重大なエラーがありました」が出たときの復帰方法 – FIRE & TECH

週末に開催されていたHarekaze CTFに参加して以下の1問だけ解けたので解法を書き残しておく（間違っていたら直します）．

[Crypto] ONCE UPON A TIME 100

problem.pyと実行結果のresult.txtが与えられる．

Encrypted Flag:
ea5929e97ef77806bb43ec303f304673de19f7e68eddc347f3373ee4c0b662bc37764f74cbb8bb9219e7b5dbc59ca4a42018

result.txt

Encrypted Flagは，フラグを25文字ずつに分割して5×5行列の各要素に1文字を割り当て，法251のもとで行列積を行って暗号化したものだった．
（もう片方の5×5行列m2はプログラム中で与えられる）

m2 = [[1,3,2,9,4], [0,2,7,8,4], [3,4,1,9,4], [6,5,3,-1,4], [1,4,5,3,5]]

def takenoko(X, Y):
  W = [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]
  for i in range(5):
    for j in range(5):
      for k in range(5):
        W[i][j] = (W[i][j] + X[i][k] * Y[k][j]) % 251
  return W

problem.pyの一部

解法

n次正方行列A，n次元列ベクトルb，整数mがあり，det (A) とmが互いに素のとき，mを法とする連立合同式

Ax ≡ b (mod m)

の解が

x = cÃb  

（ただし，Ã = det (A)・A^-1，　c・det(A) ≡ 1（mod m））

で与えられるようなので（このpdfを参考にした），これもとに実装した．

pdfに載っているのは行列-ベクトル積の合同式だが，本問題のような行列-行列積でも同じように適用できた．

以下に実装を示す．

def decrypt(m1, m2):
    c = b""
    for mat in m1:
        g = random.randint(0,1)
        if g == 0:
            _mk = np.dot(m2, mat)
        else:
            _mk = np.dot(mat, m2)
            
        mk = []
        for i in range(5):
            tmp = []
            for j in range(5):
                hoge = int(np.floor(_c * det_m2 * _mk[i][j] + 0.5))
                tmp.append(int(hoge)%251)
            mk.append(tmp)

        for k in mk:
            c += bytes(k)

    return c

answer.pyの一部

このdecryptに，m2の逆行列と，暗号化されたバイナリを要素にもつ行列を渡してフラグを得た．

 

本問題では，法251に関するdet(A)の逆元c（プログラム中では変数_c）の値は94となった．

逆行列や行列式の計算にはnumpyを用いた．

また，暗号化の際にrandom関数で行列積の順序を予測できないようにされていたが，積の順序は4通りしかないことが分かっていたのでゴリ押した．

感想

この1問に6時間近くかかったが解いてて楽しかった．

来年もあるなら参加してみたい．

 

「30日でできる！OS自作入門」という本に沿ってOSを作った．

とりあえずキリのいいところまで作ったのでまとめておく．

本書の内容をそのまま載せるのはアレなので自分なりに改造した点，追加で実装した点のみをまとめる．

まず一点目に，本書はOSとしてFDイメージ(フロッピーディスクイメージ)を作成しているが，FDが無くて実機での動作確認が出来ないため，CD/DVDに書き込めるディスクイメージ (isoファイル) を作成するように改造した．

二点目に，本書で実装しているコマンド (ls や cat )に加えて moreコマンドを実装した．

isoファイル作成

isoファイルは，EI-Torito という規格に従って作成する．これはISO 9660を拡張した規格らしい．

今回作成したisoファイルの中身は以下のようになっている．

FDをエミュレートするように設定したため，20セクタ目以降は本書のFDイメージの内容をそのまま書き込んでいる．

ちなみに，1セクタ = 0x800 [byte] = 2048 [byte] である．

EI-Toritoという規格では，

• Primary Volume Descriptor
• Boot Record

の2つの Volume Descriptor をイメージファイルに書き込んでおく必要がある．

When preparing to mount a CD, your first action will be reading the volume descriptors (specifically, you will be looking for the Primary Volume Descriptor).

https://wiki.osdev.org/ISO_9660#Volume_Descriptors

Volume Descriptor というのはCDのマウント時に読まれるもので，ISO 9660では16セクタ目にあるPrimary Volume Descriptor を最初に探すようだ．

Volume Descriptorのフォーマットを以下に示す．

最初の0バイト目はタイプコードというもので，以下の表のように定義されている．

1〜5バイト目は常に’CD001’という文字列と決まっている．

6バイト目は Volume Descriptor のバージョンのようだが，これも0x01で決まっている．

7バイト目以降は Volume Descriptor それぞれで異なる．

Primary Volume Descriptor はフィールドの数が多いので説明は省略する．

Boot Record で書き込むべきフィールドと，それに対応したアセンブラのソースコード(言語はNASK)を以下に示す．

 
; Boot Record Volume Descriptor

DB	0			; ボリューム記述子タイプ:0
DB	"CD001"			; 文字列"CD001"
DB	1			; このディスクリプターのVersion 必ず1
DB	"EL TORITO SPECIFICATION"; 文字列"EL TORITO SPECIFICATION"
RESB	0x8827-$		; 残りは0で埋める
RESB	0x8847-$		; 予約:0
DB	0x012			; Boot catalogのセクタ
RESB	0x9000-$		; 予約:0

ipl10.nas

6バイト目までは先ほど説明した通りである．

7〜38バイト目はブートシステムの識別子で，”EL TORITO SPECIFICATION”という文字列を書き込む．余った部分は0で埋めておく．

DB命令 (Data Byte) は1バイト分データを書き込む命令だが，文字列を渡すと自動的に1文字(1バイト)ずつ全て書き込んでくれる．

RESB命令は指定した数だけ0を書き込む命令である．本プログラムでは目的の番地と現在の番地の引き算によりその数を算出している．

39〜70バイト目はブートの識別子とあるが，0で埋める．

71〜74バイト目は Boot Catalog のアドレスをセクタ番号で書き込んでおく(以下参照)．

今回は72バイト目以降を0で埋めているため 12 00 00 00 と書き込まれ，Boot Catalog が 18 (0x00000012) セクタ目にあることを示している．

It records at bytes 71 to 74 as little-endian 32-bit number the block address of the El Torito Boot Catalog. This catalog lists the available boot images, which serve as starting points of booting systems.

https://wiki.osdev.org/ISO_9660#The_Boot_Record

Boot Catalog ではエミュレーションの設定やブートイメージの番地指定など重要な設定を書き込む．

Boot Catalogで書き込むべきフィールドとそれに対応したアセンブラのソースコードを示す．

; Boot catalog

DB	1	        ; ヘッダID:1
DB	0	        ; 0:80x86, 1:powerPC, 2:Mac
RESB	0x9004-$	; 予約:0
RESB	0x901c-$	;
DB	0xaa, 0x55	; チェックサム
DB	0x55		; シグネチャ:0x55
DB	0xaa	        ; シグネチャ:0xaa
DB	0x88		; 0x88:Bootable, 0x00:Not Bootable
DB	0x02		; エミュレーション
DB	0x00, 0x00	; 読み込み先セグメント
DB	0x00	        ; ?
DB	0x00		; 予約:0
DB	0x01, 0x00	; 読み込みセクタ数
DB	0x20, 0x00, 0x00, 0x00 ; ブートセクタの読み込み元セクタ:0x10000byte目
RESB 	0x9800-$	; 予約:0
RESB	0x10000-$	; ブートセクタの記述まで0で埋める

ipl10.nas

Boot Media Typeで0x02を書き込むことにより，1.44Mのフロッピーディスク(容量は本書に合わせた)をエミュレートするように設定している．

また，Boot Load RBAで 20 00 00 00 と書き込むことでブートセクタ(OS本体の先頭部分)が 20 (0x00000020) セクタ目にあることを示している．

以上がisoファイルを作成するにあたって追加した部分である．

Primary Volume Descriptor に関しては，よければ参考サイトとGithubを参照してほしい．

本書で作成されたFDイメージ(OS本体)はそのまま流用していて，20セクタ目以降に書き込んでいるため，本書と同じOSがCD/DVDよりブートできる．

moreコマンド実装

isoファイルを作成できるようにしてからは，本書をそのまま読み進めて様々なOSの機能を実装していった．

大まかには，

• 割り込み処理
• FIFO (キー入力等のデータ受け取りに使う)
• メモリ管理
• マウス，キーボード制御
• ウインドウ管理
• タイマ
• タスク管理
• コンソール

である．

基本的にはC言語で実装しているが，アセンブラに頼らざるを得ない部分もあった．

本書ではコンソール実装時に，mem(使用，空きメモリ容量表示)，ls，cat，clear コマンドを叩けるようにしている．

これらに加えて more コマンドを追加したので処理の流れを簡単に説明する．

more コマンドはファイルを一画面単位で閲覧するコマンドで，cat コマンドを改良することで実装した．Enterキーを押すことでファイルを一行ずつ読み進める．

コマンド実行中はキー入力を受け付ける必要があるため，割り込み処理やFIFOの機能を使っている．

cat コマンド (比較用) と more コマンドの簡易なフローチャートを以下に示す．

more コマンドは，cat コマンドの処理に加え，一画面分出力のための行数カウント用の変数と改行フラグを用意して，if文とEnter入力待ち(while文)を付け足したものとなっている．

こうすることで

1. ファイルの内容を一画面分出力する
2. Enterキー押下まで待つ
3. Enterキーが押下されると一行出力して 2 に戻る

のループができる．ファイルの内容を全て出力したらループから抜ける．

moreコマンド実行結果の図を示す．

OSはVirtualBox上で実行している．

OS内にはharibote.sysファイルとxv6のREADMEファイルを入れてある．

実行画面(1)が > more README を叩く前の画面で，(2)が叩いた直後の画面，(3)はEnterキーを押下して少し進めた画面である．

画面が見にくいがうまく実行できた．

今後はとりあえず本書を最後まで読み進めて，ファイルシステムをもう少し理解してからcpコマンドやmvコマンドを実装したい．

参考にしたサイト

[1] Bootable CDの作り方

[2] ブータブル CD や DVD

[3] ISO 9660 – OSDev Wiki

[4] EI-Torito – OSDev Wiki

土日の2日を使って自作PCに挑戦した．

使用パーツ

• マザーボード (ASUS PRIME H370-A)
• CPU (Intel Core i7-8700)
• 電源 (Antec NeoECO 650 GOLD : 650W)
• メモリ (Crucial DDR4-2666 8GB×2枚組)
• SSD (Crucial MX500 2.5-inch : 500GB)
• 光学ドライブ (ASUS GREEN DVD-WRITER : DVDスーパーマルチドライブ)
• PCケース (強冷却ATX 旋風)

合計費用 : 99,959円 (税込)

似たようなスペックでグラボも付いて119,800円 (税別)のBTOパソコンがあったのであまり安上がりにはなってないっぽい．

https://www.tsukumo.co.jp/bto/pc/game/2018/GA7J-D180T.html

組み立て手順

1. マザーボードにCPUクーラーとメモリを取り付ける(CPUは店で取り付けてもらった)
2. PCケースにマザーボード，電源，光学ドライブ，SSDを取り付ける
3. マザーボード，光学ドライブ，SSDに各種ケーブルを接続する
4. 終わり

授業で一回組み立てたことがあったが，やっぱり結構時間はかかった．

ケースケーブルの接続に手間取った．

さらに授業で取り扱ってないフロントパネルの外し方が分からなかったり，スペーサーとは何ぞやとか思ってたりした．

以下は作業風景．

土曜日は組み立て終わりまでいったが起動がうまくいかなかった．

電源供給は出来ていた(ファンは回った)がBIOS画面が表示されなかった．

日曜日にその原因を探ったが自力では解決出来なかったので，ツクモ名古屋1号店のサポート窓口を訪ねた．

そこでCPUクーラーが正しく取り付けられていないことが原因だと分かった(一瞬で解決してくれた)．

どうもCPUとCPUクーラーが離れていると，CPUが温度の急上昇を検知して勝手に動作を停止するらしい．

早速家に帰って再び起動を試してみるとBIOS画面が表示された．

BIOS画面ではCPUとメモリが正しく認識されていることが確認できた．

あとはMicrosoftの公式ページより作成したWindows10のUSB ブートメディアをPCに差して，再起動してインストールして終わり．

追記 2018/09/19

ライセンス認証と音声トラブル

ライセンスはノートPCから移行しようと思っていたが，ノートPCのOSはWindowsがプリインストールされていたOEM版だったので出来なかった．

仕方ないのでツクモ名古屋一号店でDSP版 (パッケージ版はなかった)を買ってきてライセンス認証を済ませた．

DSP版はPCパーツを一つ以上一緒に買わないといけないものだったので2TBのHDDを買った．

最終的な費用の算出はグラボを買った後にしようと思う．

追記 2018/12/31

最終的な費用はグラボ (GTX 1060)，OS (Windows 10 Home)，HDDを合わせて158,029円(税込)となった．

あと，HDMIで接続した先のディスプレイから音が出ないトラブルが発生した．

これはサポートページからグラフィックドライバ (VGA)をダウンロードしてきてセットアップすることで解決した．

これを行うと，今度は動画がうまく再生されなくなった．

こっちはブラウザの設定でハードウェアアクセラレーションを無効にすると解決した．