Gentoo Linuxを使い始めた

TL;DR

前々からsystemdから抜け出したいなーという気持ちがあったので、initシステムを含め随所で選択の自由が与えられているLinuxディストリビューションGentoo Linuxを使い始めました。 この記事は、Firefoxコンパイル中に暇だから書こうと思い立ち、とりあえずインストール手順をまとめてみたポエムです。

さてインストールですが、基本はwikiに忠実にやっていけば大丈夫です。とても親切にわかりやすくまとめられているなと感動しました。

wiki.gentoo.org

以下、自分で選択する必要があったところについて簡単に書いていきます。

インストール環境

手順

Live Mediaを用意し、起動する

自分はminimalのやつをUSB Memoryに書き込みました。起動するとおなじみのgrubが出てくるので適当に選んで進みます。

インストールの準備をする

  • ネットワーク

自分のPCにはRJ45がささらない(かつUSBtoRJ45を持ってなかった)のでWiFiでインストールしました。 Live環境にはもとからwpa_supplicantが入っているのでこれでよしなに繋いでdhcpcdでip addressを貰えばいい感じです。

% ifconfig {interface} up
% wpa_supplicant -B -i {interface} -c <(wpa_passphrase {SSID} {PASSWORD})
% dhcpcd
  • ストレージ

自分のPCのSSDにはすでにOpenBSDとArchLinuxとUbuntuが入っていて一杯だったのでUbuntuの入っているパーティションをmkfs.ext4して使うことにしました。

  • 日時

ntpがちゃんと降ってくる恵まれた環境だったのでntpdで時間を合わせました。

  • stage tarballのダウンロード&展開

current-stage3-amd64を選択しました。tar.xzの展開方法が分からなかったので調べました。

  • make.conf

CFLAGSに-march=nativeを足して、MAKEOPTSに-j3を指定しました。

  • mirror serverの選択

北陸先端科学技術大学院大学にお世話になります。

  • DNS情報のコピー

これ最初忘れてて、あれ?インターネットにつながらないぞ!!を20分くらいやってました。

あとは適当にマウントしてchrootすればベース環境に入れます。

ベース環境の整備

よくわからないのでwikiに従って適当にやりました。eselectでprofileを選ぶところ、変にgnomeとかついているやつを選んでしまったので@worldの更新に3時間くらい取られました。まいった。

カーネルビルド

Gentooの象徴とも言えるカーネルビルドのお時間です。 まともに使えるLinuxカーネルのビルドはいままでに一度もやったことがなかったので結構苦戦しました。 とりあえず大事なのは、使うファイルシステムのドライバとUSBドライバをちゃんと選択しておくことです。これだけクリアしてればあとから何度でもやり直しできます。

自分がいじった設定としては、MMCとSCSI周りとUSBのNetworking Frameworkの有効化、それとNICのドライバをカーネルに含めてしまう設定くらいのものです。

今後いじってみて足りない機能は追加してみます。

設定が終わったらmakeしてカーネルモジュールとbzimageのインストールをして終わりです。このとき、/bootをマウントするのをお忘れなく。

fstab

必要に応じて書きます。最低限、/と/bootがあれば良さそう。

Hostname

かっこいい名前をつけましょう。モテるための秘訣です。

あとはwiki通りにやってumountして、grubのコンフィグをいじるとブートできます。 ブートしたあとはx11とwmを入れてstartxすると幸せになれます。

(ポエム書き終えたけどまだFirefoxコンパイル終わってない...)

アマチュア無線技士3級試験に合格した

CTFのWriteupに続いてアマチュア無線技士試験のWriteupを書きます。

昨年、僕はこんな記事を書きました↓

yukium.hatenablog.jp

要するに、デジタル通信訳わかんないから、とりあえずアナログ通信から勉強してみたかったわけです。 それで取り敢えず3アマを取ってハムになってみようと思っていたのですが、バイトとかCA行きとかSecHack365とかプロコンとか色々盛りだくさんの一年だったおかげで、試験は受けられずにいました。 ずっと受けよう、受けようと思っていたのですがなかなか時間が取れず結局平成最後の年、2019年になって時間が取れたので受けてきた、という次第です。

ところで、3アマは東京にある日本無線協会本部で当日試験というものを行っています。当日行って申し込んで、当日試験を受けて、当日合否が分かって更に免許の申請も出来ちゃうという素晴らしい制度です。 なのでこれを目指して試験日の2週間くらい前から勉強し始めました。もともと、電磁気学や電波工学には少し興味があって参考書を読んだりしたことがあったので、過去問は法規さえ暗記すればイケるなーと思っていました。

参考書には以下の2冊を使いました。

第3級ハム国試 要点マスター 2018 (アマチュア無線技士問題集)

第3級ハム国試 要点マスター 2018 (アマチュア無線技士問題集)

初めての3級・4級アマチュア無線技士試験

初めての3級・4級アマチュア無線技士試験

1冊目は、暗記するにはかなり効率的に作られていて2冊目はもう少し丁寧に抽象的な理論と共に解説してくれていて合わせて読むといい感じでした。

それで、試験当日はセンター試験2日目ということだったので、高専生でセンター試験とは縁がない身ではあるのですが取り敢えず気分だけ味わっておこうとセンター試験気分で会場へ行きました。

会場は勝どき駅から少し歩いたところで、東京駅方面へ都営バスも走っているのでなかなか便利なところです。この東京の東側の地域は、人が程よくまばらで建造物が比較的新しくいい街です。 試験は11時からだと思っていたのですがそれはどうやら受付開始時間だったようで、実際は13時からでした。9時30分には会場入りしていたので相当待ちました。時間はちゃんと確認しておきましょう。

それで、試験自体は15分もかからず終わっちゃうような内容で、素っ気なかったです。試験時間は70分ですが、30分立つと中途退出出来るようになります。 退出して、自己採点してみると満点でした。過去問流用の簡単な試験ではありますが嬉しい。 合格発表は50分くらい経ってからでした。自己採点で満点だったのでまあ合格だろうと先に免許申請書等を書いておいて、一応合格を確認してすぐに免許申請へ行きました。 ちなみに合格発表の掲示はこんな感じ。

というわけで、スムーズに3アマの取得が出来ました。勉強時間は合わせて10時間くらいです。不毛な授業中に内職したりしておくと不毛な授業時間が3アマ免許に化けた気がしてお得です。

せっかく免許を取ったので、取り敢えず電波を出してみたいです。もしこの記事をご覧の方で、ハムの方が居たらぜひ交信してください!

InterKosenCTF Writeup [初のイベント型CTFに参戦]

学校の先輩に誘われて、初めてリアルタイムで開催されているCTFに参加してみました(といっても、ksnctfのVillager Aくらいしか解いたことがないので実質CTF処女です)。 3日間の開催でしたが、1日目は早々にして寝落ちしたため、3日目はアマチュア無線の試験を受けに行っていたため取り組めたのは1日だけでした。その1日は先輩と一緒に新宿のルノアールで一日中CTFをやっていました(ルノアールさん長居してごめんなさい)。

webとかcryptoとかはそもそも全く見たこともなかったので解法の検討が全くつきませんでした。なので先輩に任せっきりでした(ごめんなさい)。私が唯一行けそうだなーと思ったのはreversingとpwnだけだったので基本的にその2つだけに集中して取り組みました。 それで、結局解けたのはreversingの100pt問題、「flag generator」だけでした。他の人の参考に、というよりかは解いただけで放置してしまうのはもったいない気がするのでこうして記録しておこうと思った次第です。

問題で渡されたのはx86_64 Linux向けのELFバイナリでした。 実行しても何も表示されず... とりあえず逆アセンブルして読んで見る。

0000000000401152 <r>:
  401152:  55                     push   rbp
  401153:  48 89 e5               mov    rbp,rsp
  401156:  8b 05 f0 2e 00 00      mov    eax,DWORD PTR [rip+0x2ef0]        # 40404c <s>
  40115c:   69 c0 6d 4e c6 41       imul   eax,eax,0x41c64e6d
  401162:  05 39 30 00 00           add    eax,0x3039
  401167:  25 ff ff ff 7f        and    eax,0x7fffffff
  40116c:   89 05 da 2e 00 00     mov    DWORD PTR [rip+0x2eda],eax        # 40404c <s>
  401172:  8b 05 d4 2e 00 00      mov    eax,DWORD PTR [rip+0x2ed4]        # 40404c <s>
  401178:  5d                      pop    rbp
  401179:  c3                       ret

000000000040117a <main>:
  40117a:   55                     push   rbp
  40117b:   48 89 e5               mov    rbp,rsp
  40117e:   48 83 ec 50           sub    rsp,0x50
  401182:  64 48 8b 04 25 28 00   mov    rax,QWORD PTR fs:0x28
  401189:  00 00 
  40118b:   48 89 45 f8           mov    QWORD PTR [rbp-0x8],rax
  40118f:   31 c0                   xor    eax,eax
  401191:  c7 45 d0 35 59 8f 60  mov    DWORD PTR [rbp-0x30],0x608f5935
  401198:  c7 45 d4 91 64 50 57     mov    DWORD PTR [rbp-0x2c],0x57506491
  40119f:   c7 45 d8 57 55 36 27     mov    DWORD PTR [rbp-0x28],0x27365557
  4011a6:   c7 45 dc a1 de e3 54   mov    DWORD PTR [rbp-0x24],0x54e3dea1
  4011ad:   c7 45 e0 d5 4e 5a 75     mov    DWORD PTR [rbp-0x20],0x755a4ed5
  4011b4:   c7 45 e4 b7 2e f4 17  mov    DWORD PTR [rbp-0x1c],0x17f42eb7
  4011bb:   c7 45 e8 59 90 4f 4a   mov    DWORD PTR [rbp-0x18],0x4a4f9059
  4011c2:   c7 45 ec 27 e8 08 1a    mov    DWORD PTR [rbp-0x14],0x1a08e827
  4011c9:   c7 45 f0 1f 39 9d 0d     mov    DWORD PTR [rbp-0x10],0xd9d391f
  4011d0:   c7 45 f4 aa 33 e5 59     mov    DWORD PTR [rbp-0xc],0x59e533aa
  4011d7:   c7 45 c8 7e 16 dc 25    mov    DWORD PTR [rbp-0x38],0x25dc167e
  4011de:   c7 45 cc 0a 00 00 00     mov    DWORD PTR [rbp-0x34],0xa
  4011e5:   c7 45 c0 00 00 00 00    mov    DWORD PTR [rbp-0x40],0x0
  4011ec:   c7 45 c4 00 00 00 00    mov    DWORD PTR [rbp-0x3c],0x0
  4011f3:   c7 45 bc 00 00 00 00    mov    DWORD PTR [rbp-0x44],0x0
  4011fa:   83 7d c4 00            cmp    DWORD PTR [rbp-0x3c],0x0
  4011fe:   75 10                 jne    401210 <main+0x96>
  401200:  bf 00 00 00 00          mov    edi,0x0
  401205:  e8 46 fe ff ff         call   401050 <time@plt>
  40120a:   89 05 3c 2e 00 00     mov    DWORD PTR [rip+0x2e3c],eax        # 40404c <s>
  401210:  b8 00 00 00 00          mov    eax,0x0
  401215:  e8 38 ff ff ff         call   401152 <r>
  40121a:   89 45 bc               mov    DWORD PTR [rbp-0x44],eax
  40121d:   8b 45 bc                mov    eax,DWORD PTR [rbp-0x44]
  401220:  39 45 c8               cmp    DWORD PTR [rbp-0x38],eax
  401223:  75 07                 jne    40122c <main+0xb2>
  401225:  c7 45 c4 01 00 00 00    mov    DWORD PTR [rbp-0x3c],0x1
  40122c:   83 7d c4 00            cmp    DWORD PTR [rbp-0x3c],0x0
  401230:  74 35                 je     401267 <main+0xed>
  401232:  8b 45 c0                mov    eax,DWORD PTR [rbp-0x40]
  401235:  48 98                 cdqe   
  401237:  8b 54 85 d0            mov    edx,DWORD PTR [rbp+rax*4-0x30]
  40123b:   8b 45 bc                mov    eax,DWORD PTR [rbp-0x44]
  40123e:   31 d0                   xor    eax,edx
  401240:  89 45 bc               mov    DWORD PTR [rbp-0x44],eax
  401243:  48 8d 45 bc            lea    rax,[rbp-0x44]
  401247:  48 89 c6               mov    rsi,rax
  40124a:   48 8d 3d b3 0d 00 00    lea    rdi,[rip+0xdb3]        # 402004 <_IO_stdin_used+0x4>
  401251:  b8 00 00 00 00          mov    eax,0x0
  401256:  e8 e5 fd ff ff           call   401040 <printf@plt>
  40125b:   83 45 c0 01           add    DWORD PTR [rbp-0x40],0x1
  40125f:   8b 45 c0                mov    eax,DWORD PTR [rbp-0x40]
  401262:  3b 45 cc                cmp    eax,DWORD PTR [rbp-0x34]
  401265:  74 0c                   je     401273 <main+0xf9>
  401267:  bf 01 00 00 00          mov    edi,0x1
  40126c:   e8 ef fd ff ff           call   401060 <sleep@plt>
  401271:  eb 87                   jmp    4011fa <main+0x80>
  401273:  90                     nop
  401274:  b8 00 00 00 00          mov    eax,0x0
  401279:  48 8b 4d f8             mov    rcx,QWORD PTR [rbp-0x8]
  40127d:   64 48 33 0c 25 28 00   xor    rcx,QWORD PTR fs:0x28
  401284:  00 00 
  401286:  74 05                 je     40128d <main+0x113>
  401288:  e8 a3 fd ff ff           call   401030 <__stack_chk_fail@plt>
  40128d:   c9                       leave  
  40128e:   c3                       ret    
  40128f:   90                     nop

適当にジャンプ命令をnopで埋めてみたりしていたら、何やらよくわからない文字が出力されました。 この文字は一体どこからきているのだろうとアセンブラを見てみると 40121aでr()の返り値がDWORD PTR [rbp-0x44]に代入されてそれを元に演算した結果が出力されていると分かりました。 なのでDWORD PTR [rbp-0x44]が正しい文字になるようにしてあげればよいのです。

じゃあ正しい文字になるような値ってなんだよとまたアセンブラを見直してみると最初にnopで埋めていたジャンプ命令の前にcmp DWORD PTR [rbp-0x38],eaxというのがあったのでここからDWORD PTR [rbp-0x38]がその値であると分かりました。

それでこの値をDWORD PTR [rbp-0x44]に入れてstep実行してみると「KOSE」という文字が出力されたのでよっしゃと思い続く処理もステップ実行してみたのですが、その後の文字はうまくASCIIにはなっていませんでした。

それでなにがいけないのかともう一度見直して、そもそもこのr()の返り値は40404cを元に計算されていることを発見し、またこの40404cはループ毎に変化する値であることが分かりました。それで、じゃあ最初のr()を実行し終わった後だけ手動で40404cとDWORD PTR [rbp-0x44]にDWORD PTR [rbp-0x38]の値をいれてステップ実行してみると次のような出力を得られました。

0x45534f4b
0x14654434e
0x25f53497b
0x353494854
0x44145525f
0x55f594c4c
0x645525f41
0x753524556
0x83f474e49
0x90000007d

最後の7dは「}」なので、これはFLAGだ!と思いどうにかこねくり回してFLAGにするのだと思い眺めてみると、MSBが0から9の値で変化していることに気づきました。これがあるせいでうまく文字に出来なかったのですが、これを除いて文字にしてみると見事FLAGが取得できました。

KOSENCTF{IS_THIS_REALLY_A_REVERSING?}

結局1問しか解けませんでしたが、初めて自力で解けたので結構感動しました。CTF面白いね!運営の皆さんありがとうございました。

Majestouch Convertible 2を買った

この記事はプロコンゼミ(SPC同好会) その1 Advent Calendar 2018の18日目の記事です。 夢の中で宇宙旅行を楽しんでいたら、地球のタイムゾーンをすっかり失念していました。ごめんなさい!!! というか、このアドベントカレンダー担当者はほぼ埋まっていたのに全然投稿されていないですねーなんででしょうか。

本来なら、この記事は高速ナベアツの続きを書く予定だったのですが、忙しくて続きがあまり出来ていないのと他のネタが出来たので、ネタ替えをすることにしました。重ねてごめんなさい!! 高速ナベアツの続きは年度内に書ければなーと思います。

yukium.hatenablog.jp

さて、弊部のアドベントカレンダーには他にもキーボードの記事が投稿されていました。

h2so4.hatenablog.com

これです。彼いわく、このキーボードはHHKBより良いらしいです。

さて、まあキーボードと言えどもピンキリですよね。高いものは学生には手が出せないくらいの値段しますし、秋葉原で投げ売られているものを買えば100円とか、ひょっとしたらもっと安く手に入るかもしれません。 筆者はしがない三流ソフトウェアエンジニアではあるものの、やはり良いキーボードというものに憧憬を抱くわけです。そこで、今回タイトルの通りMajestouch Convertible 2というキーボードを買ったという次第です。

それで、まずこのMajestouch Convertible 2(以下、MC2と呼ぶ)を買うにあたって重要になるのは軸の色です。 MC2はメカニカルキーボードと呼ばれるキーボードの一つで、キーのひとつひとつが独立したスイッチになっています。 MC2ではこのスイッチにCherry MXというブランドのスイッチを使っています。詳しくは、次のページを見てみてください。

DIATEC|ダイヤテック株式会社 製品情報

このページを見ると分かるように、キースイッチには幾つか種類がありその種類が軸の色によって決まっています。 筆者は、茶軸を買おうと決めました。

そして、アマゾンで注文して届きました。

それで、よく見ると赤軸を注文してしまっていました。間違えてしまった。まあ、違いはクリック感だけらしいのでそんなに気にしてません。

この日はちょうど友人とNTTの技術史料館に行く用事があったのでこのキーボードを持ち歩いてみることにしました。もともとキーボードは色々なところに持ち歩いて使おうと思っていたので良い機会です。

重量は電池を入れると1kgくらいあるので結構重かったです。リュックサックじゃなかったら持っていくのは迷いますね。

それで、打鍵感についてですが、赤軸でもけっこう良かったです。打っていて楽しいです。さっそくAtCoderの問題も解いてみました↓

atcoder.jp atcoder.jp

Enterキーが今まで使っていたキーボードより長くてこのあたりの慣れが必要です。あ、キーボードの写真が未掲載でした。載せます。

f:id:yuhki0223:20181229100544j:plain

こちらが今回買ったMC2のキーボード。

f:id:yuhki0223:20181229101029j:plain

こちらが普段使っているThinkPad Yoga 260の内蔵キーボード。

初めて手にしたノートパソコンのキー配列がUS配列だったので、それからずっとUS配列を使ってます。プログラミングをするときは記号のキーがいいかんじの所にあるので打ちやすいです。

見ての通り、配列自体はほぼ一緒(MC2のCapital LockとControlは入れ替えた)ですが、キートップの表面積が結構違うので前述の通り慣れが必要です。

HHKBは矢印キーが独立して存在していないですが、MC2にはあるので全体長は少し長めです。まあギリギリ持ち運べるサイズです。

あ、あとBluetooth機能もついています。ペアリングも簡単でした。

# systemctl start bluetooth
# bluetoothctl
[bluetooth]# power on
[bluetooth]# agent KeyboardOnly
[bluetooth]# default-agent
[bluetooth]# pairable on
[bluetooth]# scan on
[bluetooth]# pair [MAC address]
[bluetooth]# trust [MAC address]
[bluetooth]# connect [MAC address]

こんな感じだと思います。信頼したデバイスに登録しておくと、次回以降接続時にconnectを実行するだけなので楽です。

他のブログ記事を見ていると、キーの遅延があるだとかそういうレビューもあったのですが今の所僕の環境では起きていないです。bluetoothも好調に使えます。

という感じで、雑多なレビューをしてみました。 もしMC2の購入、あるいはキーボードの購入を検討している人がいたら参考にしていただけると幸いです。

お気に入りのキーボードを買って進捗を爆上げしていきましょう!!!

世界一速いナベアツに挑む①

この記事はプロコンゼミ(SPC同好会) その2 Advent Calendar 2018 - Adventarの14日目の記事です。

導入

このネタは、我が部活が誇るあかこう先輩のネタのパクリ継承となります。 元の記事は削除されてしまったようなので、参考になりそうなリンクを貼っておきます。

https://akakou-slide.github.io/nabeatsu/ github.com

ところで、ナベアツというのは皆さんご存知の世界のナベアツこと桂三度さんのネタのことです。

わからない人のために...

例えばAくんという人が居るとします。Aくんは自然数を数え上げていきます。 数え上げる自然数が3の倍数、もしくは3がつく数のときにおかしな声をだします(このことを、バカになるという)。

注意

  • この記事の内容を実際に試したことにより、システムにどのような損害が起きたとしても筆者は責任を負いかねます。試す際には自己責任で宜しくおねがいします。
  • 世界一速いナベアツを名乗っていますが、これは少し誇張した表現ですので訂正します。この記事では、x86_64上で動作するLinux 4.19において最も高速に動作するナベアツを目指します。

高速化のポイント

ソースコードはMITライセンスということで、ありがたく高速化のポイントの解説として、使わせていただきましょう。

MIT License

Copyright (c) 2017 akakou

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

一応ライセンス表示。

ということで、一旦あかこう先輩が書いたソースコードを全部のせます。

; nabeatsu.s
; 最強のNABEATSU☆を目指す


; コードセクション
section .text
    global _start                           ; _startを指名

; スタート
_start:
                                            ; カウント用レジスタの初期化
    mov r12, 1                              ; ボケるか判定用カウントレジスタ(普通にカウントする)
    mov r13, 1                              ; 表示用カウントレジスタ(BCDでカウントする)

; 3の倍数かをチェックする
CHECK_THREE_MULTIPLE:
    xor rdx, rdx
                                            ; r12を3で割る
    mov rax, r12                            ; r12/3(rbx) = rax...rdx
    mov rbx, 3
    div rbx

    cmp rdx, 0                              ; 除算の余りと0を比較する
    je SET_BOKE_FMT                         ; 0ならprint_abnomalにジャンプする

    mov r9,  r12                            ; r12(ボケるか判定用カウントレジスタ)をr9(3を含む数値か判定用レジスタ)にコピー

READY_CHECK_IN_THREE:
    mov r8, r13

; 3のつく数字化をチェックする
CHECK_IN_THREE:
    mov rbx, 0xF                            ; rbxに0xFを格納
    and rbx, r8                             ; r8と0xFに論理和をかけることで、16進数での1桁分取り出し、rbxに格納

    shr r8,  4                              ; 16進数におけるBCDでの1桁分右にシフトする。

    cmp rbx, 3                              ; シフトの余りと3を比較する
    je SET_BOKE_FMT                         ; 余りが0ならprint_abnomalにジャンプする

    cmp r8, 0                               ; 除算のあまりと0を比較し
    jne CHECK_IN_THREE                      ; 余りが0ならprint_abnomalにジャンプする

; 普通のフォーマット(数値のみを表示)をrbpに格納する。
SET_NOMAL_FORMAT:
    mov rbp, normal_message                 ; rbpに数値のみ表示するフォーマットを格納する

; 次の処理の準備 & `SET_NOMAL_FORMAT`からのジャンプバック用ラベル
READY_TO_SET_FORMAT_LOOP:
    mov rax, r13                            ; rax(今回表示する値が入ってるレジスタ)にr13(表示用カウントレジスタ)の値をコピー
    mov r15, 15                             ; r15に15(最大このプログラムの耐えられる最大桁数)
    add r15, rbp                            ; rbpの値(指定したフォーマットの文字列)と最大値を足した値をr15(次に格納する文字のアドレス先)に格納

; r13から1文字ずつ取り出す
SET_FORMAT_LOOP:
    dec r15                                 ; r15を1つ減算する
    mov rbx, 0xF                            ; rbxに0xFを格納
    and rbx, rax                            ; raxと0xFに論理和をかけることで、16進数での1桁分取り出し、rbxに格納
    add rbx, 0x30                           ; rbxに格納された1桁の数値に0x30を足すことで、ASCIIの文字のデータにする
    mov [r15], bl                           ; bl(rbxから1バイト分のデータ)をr15の持つアドレス先に書き込む
    shr rax, 4                              ; 16進数におけるBCDでの1桁分右にシフトする。
    jnz SET_FORMAT_LOOP                     ; raxが0になるまでSET_FORMAT_LOOPを回し続ける

; 文字列を表示
PRINT:
    mov r14, rcx                            ; rcxの値をr14に退避

    mov rcx, rbp                            ; メッセージのアドレス
    mov rdx, 17                             ; メッセージの長さ
    mov rbx, 1                              ; 標準出力を指定
    mov rax, 4                              ; システムコール番号 (sys_write)
    int 0x80                                ; 割り込み

    mov rcx, r14                            ; r14に退避させた値をrcxに戻す

; カウントをする
COUNT:
    inc r12                                 ; r12に1加算
    inc r13                                 ; r13に1加算

    mov r9, r13                             ; r9(繰り上がれてないか確認用レジスタ)にr13(表示用カウントレジスタ)をコピー
    mov r11, 0xF                            ; r11に0xFを格納

; 表示用カウントレジスタ(BCD)の桁上がりチェック
CARRY_UP:
                                            ; 各桁に0xAが含まれていないか確認し、含まれていたら`CARRY_UP_BCD`を呼ぶ
    mov r10, 0xF                            ; r10に0xFを格納
    and r10, r9                             ; r10にr9の右から1桁分を格納させる
    cmp r10, 0xA                            ; r10(上の処理で取った1桁分)と0xA(BCDではありえない値)かを確認
    je CARRY_UP_BCD                         ; r10が0xAなら繰り上がりをする

                                            ; 二重繰り上がりが起きたときの処理
    cmp r10, 0xB                            ; r10に0xBが格納されていないかを確認
    je CARRY_UP_BCD                         ; r10が0xBなら繰り上がりをする(0xC以上は理論上ありえない)

; 次のカウント後の処理へジャンプする
LOOP_BACK:
    cmp r12, 1000000                        ; 最大カウント回数(100000)とr12(通常カウント)を比較
    jne CHECK_THREE_MULTIPLE                ; 同じになるまでCHECK_THREE_MULTIPLEに戻る

; 終了処理
FIN:
                                            ; プロセス終了
    mov rax, 1                              ; 返り値を1にする
    mov rbx, 0                              ; 終了ステータスコード
    int 0x80                                ; システムコール

; 表示用カウントレジスタ(BCD)の桁上がり処理
CARRY_UP_BCD:
    or r13, r11                             ; うまく繰り上がれてない値(r13)の、繰り上がれてない部分をすべて二進数の1で埋めて
    inc r13                                 ; 1を足す → 強制的に繰り上がらせる

    or r9, 0xF                              ; r9(繰り上がれてないか確認用レジスタ)の方も
    inc r9                                  ; 繰り上がりしておく(ここで二重繰り上がりの可能性あり)

    shr r9, 4                               ; r9の値を右に1文字分(16進数ひと桁分)シフトする
    shl r11, 4                              ; `CARRY_UP_BCD`で使う対象以下の2進数での桁を1で埋めたもの(マスク)を更新する
    or r11, 0xF

    jmp CARRY_UP                            ; `CARRY_UP`に戻る

; ボケるときのフォーマットをrbpに格納
SET_BOKE_FMT:
    mov rbp, boke_message                   ; rbpにボケたときのメッセージフォーマットを格納
    jmp READY_TO_SET_FORMAT_LOOP            ; `READY_TO_SET_FORMAT_LOOP`にジャンプする(戻る)


; データセクション
section  .data                              ; データセクションの定義
    boke_message  db 0xA, "(BOKE)          "    ; boke_messageの内容
    times 20 db 0x00

    normal_message db 0xA, "                "   ; normal_messageの内容
    times 20 db 0x00

では、高速化のポイントを洗い出してみましょう。

システムコール

あかこう先輩のソースコードではシステムコールの呼び出しとして割り込み命令が使われていますが、これはレガシーな方法であり最近のx86では高速システムコールという仕組みが用意されているのでこちらを用いるのが一般的です。 高速システムコールを行う場合、システムコール番号が異なるので気をつけましょう。

; 終了処理
FIN:
                                            ; プロセス終了
    mov rax, 1                              ; 返り値を1にする
    mov rbx, 0                              ; 終了ステータスコード
    int 0x80                                ; システムコール

レガシーなシステムコール呼び出し

FIN:
    mov rdx, 1
    mov rax, 60
    syscall

高速システムコール呼び出し

linux, x86_64の場合、以下のテーブルを見ることでシステムコール番号を知ることが出来ます。

github.com

ということで、printルーチンとfinルーチンのシステムコールの呼び出し方を変えてみました。まあ、finルーチンは一度しか呼ばれないのであまり効果がないですが。

; 文字列を表示
PRINT:
    mov r14, rcx                            ; rcxの値をr14に退避

    mov rcx, rbp                            ; メッセージのアドレス
    mov rdx, 17                             ; メッセージの長さ
    mov rbx, 1                              ; 標準出力を指定
    mov rax, 4                              ; システムコール番号 (sys_write)
    int 0x80                                ; 割り込み

    mov rcx, r14                            ; r14に退避させた値をrcxに戻す

旧PRINTルーチン

PRINT:
    mov r14, rcx

    mov rsi, rbp
    mov rdx, 17
    mov rax, 1
    mov rdi, 1
    syscall

    mov rcx, r14

新PRINTルーチン

FINルーチンは上で示した通り。

これらのルーチンを入れ替えて得られる効果はどの程度のものでしょうか。timeコマンドで計ってみます。 システムの状態によって実行時間が多少前後するのでそれぞれ10回計測しました。

./a.out  0.25s user 0.61s system 99% cpu 0.859 total
./a.out  0.20s user 0.67s system 99% cpu 0.867 total
./a.out  0.26s user 0.65s system 97% cpu 0.933 total
./a.out  0.28s user 0.69s system 99% cpu 0.976 total
./a.out  0.27s user 0.65s system 99% cpu 0.926 total
./a.out  0.22s user 0.70s system 99% cpu 0.922 total
./a.out  0.22s user 0.77s system 99% cpu 0.999 total
./a.out  0.25s user 0.67s system 99% cpu 0.916 total
./a.out  0.25s user 0.69s system 99% cpu 0.937 total
./a.out  0.21s user 0.64s system 99% cpu 0.849 total

これが割込みを使ったシステムコール呼び出しの場合。

./a.out  0.14s user 0.62s system 99% cpu 0.770 total
./a.out  0.19s user 0.61s system 99% cpu 0.800 total
./a.out  0.11s user 0.72s system 99% cpu 0.838 total
./a.out  0.15s user 0.70s system 99% cpu 0.856 total
./a.out  0.17s user 0.65s system 99% cpu 0.818 total
./a.out  0.12s user 0.69s system 99% cpu 0.818 total
./a.out  0.11s user 0.73s system 97% cpu 0.869 total
./a.out  0.09s user 0.75s system 99% cpu 0.844 total
./a.out  0.14s user 0.71s system 99% cpu 0.848 total
./a.out  0.12s user 0.71s system 99% cpu 0.832 total

これが高速システムコール呼び出しを使ったシステムコール呼び出しの場合。

結果は一目瞭然ですね。

一応平均値と中央値を出しておきましょう。

打ち込むのが面倒だったので適当にプログラムを書きました。timeのフォーマットなら使えると思うので使いたい方はどうぞ。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    string tmp, user, system;
    int count = 10;
    double heikin_user = 0, heikin_sys = 0;
    vector<double> _user, _sys;
    for(int i = 0; i < count; ++i) {
        cin >> tmp >> user >> tmp >> system >> tmp >> tmp >> tmp >> tmp >> tmp;
        user[4] = '\0';
        system[4] = '\0';
        _user.push_back(stod(user));
        _sys.push_back(stod(system));
    }
    for(auto hoge : _user) {
        heikin_user += hoge; 
    }
    heikin_user /= 10.0;
    for(auto hoge : _sys) {
        heikin_sys += hoge;
    }
    heikin_sys /= 10.0;
    sort(_user.begin(), _user.end());
    sort(_sys.begin(), _sys.end());
    cout << "heikin[ user: " << heikin_user << " sys: " << heikin_sys << " ]" << endl;
    cout << "chuou [ user: " << (_user[4] + _user[5]) / 2.0 
        << " sys: " << (_sys[4] + _sys[5]) / 2.0 << " ]" << endl;
    return 0;
}
割込みを使ったシステムコール呼び出し
heikin[ user: 0.241 sys: 0.674 ]
chuou [ user: 0.25 sys: 0.67 ]

高速システムコール呼び出しを使ったシステムコール呼び出し
heikin[ user: 0.134 sys: 0.689 ]
chuou [ user: 0.13 sys: 0.705 ]

おおー、いい感じです。

除算の高速化

除算は非常にコストのかかる計算です。x86_64にはdiv命令というものがありますが、これは8bit同士の計算だけでも41サイクルもかかってしまいます。

gccはこの問題をどのようにクリアしているのでしょうか。見てみましょう。

#include <stdio.h>

int main(void)
{
    for(int i = 0; i < 100; ++i) {
        int hoge = i / 3;
        printf("%d\n", hoge);
    }
    return 0;
}
$ gcc -S hoge.c
 .file "hoge.c"
    .text
    .section  .rodata
.LC0:
    .string   "%d\n"
    .text
    .globl    main
    .type main, @function
main:
.LFB0:
    .cfi_startproc
    pushq    %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq %rsp, %rbp
    .cfi_def_cfa_register 6
    subq $16, %rsp
    movl $0, -4(%rbp)
    jmp  .L2
.L3:
    movl -4(%rbp), %ecx
    movl $1431655766, %edx
    movl %ecx, %eax
    imull    %edx
    movl %ecx, %eax
    sarl $31, %eax
    subl %eax, %edx
    movl %edx, %eax
    movl %eax, -4(%rbp)
    movl -4(%rbp), %eax
    movl %eax, %esi
    leaq .LC0(%rip), %rdi
    movl $0, %eax
    call printf@PLT
    addl $1, -4(%rbp)
.L2:
    cmpl $99, -4(%rbp)
    jle  .L3
    movl $0, %eax
    leave
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size main, .-main
    .ident    "GCC: (GNU) 8.2.1 20180831"
    .section  .note.GNU-stack,"",@progbits

普段intel記法を使っているのでAT&T記法は読みづらい...

注目すべきは以下の部分です。

.L3:
    movl -4(%rbp), %ecx
    movl $1431655766, %edx
    movl %ecx, %eax
    imull    %edx
    movl %ecx, %eax
    sarl $31, %eax
    subl %eax, %edx
    movl %edx, %eax
    movl %eax, -4(%rbp)
    movl -4(%rbp), %eax
    movl %eax, %esi
    leaq .LC0(%rip), %rdi
    movl $0, %eax
    call printf@PLT
    addl $1, -4(%rbp)

見ての通りdiv命令は使われずimull命令とsarl命令とsubl命令等によって除算が実現されています。 この原理の基本は以下のとおりです。

まず、前提知識としてビット演算において2nで掛けたり割ったりするのはシフト演算で実現できるため、高速に計算できます。 また、整数同士の掛け算も割り算に比べれば低コストで計算することが出来ます。

これらの知識を元に、除算を以下のように変形します。

 \displaystyle
  \frac{a}{b} = a * \frac{2^{n}}{b} * \frac{1}{2^{n}}

 bは定数なので \frac{2^{n}}{b} コンパイル時に計算することが出来ます。

ですから、実行時に計算するのは整数同士の掛け算( \frac{2^{n}}{b}は整数に丸められます)と2nでの割り算だけなのでこれで除算の高速化が出来るわけです。

基本は上の通りですがこれでは誤差が出てしまう可能性があります。ですのでまだ工夫する必要は有るのですがこちらに関しては以下のブログを参考にしていただくとして、ここでは割愛いたします。

7shi.hateblo.jp

疲れてしまったので実装をどうするかについては「世界一速いナベアツに挑む②」で紹介しようと思います。お楽しみに!

参考文献

X86アセンブラ/算術演算命令 - Wikibooks

https://www.agner.org/optimize/instruction_tables.pdf

postd.cc

https://www.recfor.net/jeans/index.php?itemid=902

Binary Division by a Constant

除算 (デジタル) - Wikipedia

30日でできる!OS自作入門を始めた[3日目]

今回は、IPLの作成と32ビットモード切り替えの準備、C言語導入が主なテーマ。

IPL

IPL(Inital Program Loader)はその名の通り、初期プログラムのローダー。

まずは、フロッピーの中身をどんどんメモリに展開していきたいわけだが、これにはBIOSのディスクサービスを使う。 BIOSのディスクサービスは、「INT 0x13」で呼び出せる。

http://softwaretechnique.jp/OS_Development/Tips/Bios_Services/disk_services.html

最初の1セクタ(512バイト)は、すでにメモリに展開されているので、2セクタ目から先を読み出していく。

展開先のアドレスはセグメントレジスタを使って指定できる。

はりぼてOSのIPLは、0x8000から0x83FFまでにフロッピーの中身を展開する。0x8000から512バイト、つまり0x81FFまでは1セクタ目を入れるので0x8200から2セクタ目を入れていく。

メモリマップ↓

0x7c00 ---------------------------
                  Boot Sector
0x7e00 ---------------------------
                  Free Space
0x8000 ---------------------------
                  Sector 1
0x8200 ---------------------------
                  Sector 2
0x8400 ---------------------------

また、フロッピーディスクはたまにうまく読めないことが有るらしい。 このための処理も書く必要が有る。

あとは、フロッピー内のすべてのデータを読み出していく。

フロッピーディスク一枚には80シリンダ、ヘッドが2つ、そして18セクタあり、一つのセクタが512バイトだから、

80 * 2 * 18 * 512 = 1474560byte = 1440KBのデータがある。

そしてフロッピーのデータが展開できるようになったのでOS本体を書いていくことが出来るようになった。

しかし、OSを実行するためにはIPLからOSにジャンプする必要があり、そのためにはどこにジャンプすべきか、すなわちOSがどのアドレスに展開されるのか知る必要が有る。バイナリエディタでharibote.imgを見てみるとファイルの先頭から0x004200番目に配置されていることが分かる。0x8000から展開をしたので、飛ぶべきアドレスは

0x004200 + 0x8000 = 0xC200

である。

これで、いよいよOS本体が実行できるように...!

そして、この本ではOS本体の実行を確認するため画面をグラフィックモードにして色を描画してみるということをする。前回と同じように、BIOSのビデオサービス(0x10)を使ってやればできる。

32ビットモードへの準備

C言語を使うためには、基本的には32ビットモードに切り替える必要が有るので切り替えていく。 ちなみに、32ビットモードに切り替えてしまうとBIOSのサービスは利用できなくなってしまうので、16ビットモードでやるべきことは16ビットモードでやっていく。

画面モードの切り替えは既にやったので、キーボードの状態(シフトやキャピタルロックの設定)をBIOSから取得しておく。 キーボードの状態取得はBIOSのキーボードサービス(0x16)を使えば良い。

softwaretechnique.jp

ファンクション番号は0x02。出力はリンク先を見ればわかる。ALレジスタに出力されるので、これをメモリにコピーしておけば安心して32ビットモードへ移行できる。

C言語導入

いよいよC言語の導入だ。Harimain()関数をbootpack.cというファイルに書く。アセンブラでしか書けない内容は、naskfunc.nasというファイルに書いて、C言語から関数として呼び出す。

ところで、アセンブラのファイルとC言語のファイルの関連付けについてだが、これは両者をオブジェクトファイルにして、リンクをすれば良い。私は筆者のツールではなくgccやnasmなどの汎用ツールを使って開発しているためリンカスクリプトを指定してやる必要がある。このリンカスクリプトについては、偉大なる先人が公開されていたのでこちらをありがたく使わせてもらった。

https://vanya.jp.net/os/haribote.html

これでおしまい。

江ノ島観光

はじめに

この記事はプロコンゼミ(SPC同好会) その1 Advent Calendar 2018の4日目の記事です!

江ノ島観光

現在放送中のアニメ、「青春ブタ野郎はバニーガール先輩の夢を見ない」の聖地巡礼と試験後の息抜きも兼ねて江ノ島、藤沢方面を散策してきましたので撮った写真と共にご紹介します。

出発

午前中は微分積分プログラミング言語の試験があったのでそれを受けてから12:10分くらいに学校の校門を出発しました。中央線、横浜線小田急線、東海道線と乗り継いで藤沢駅に到着したのは2時間後、14:10分くらいのことです。

藤沢駅の北口は青ブタの作中に登場しています。 f:id:yuhki0223:20181203212511j:plain

湘南モノレール

藤沢駅からは、700円で江ノ島とか鎌倉とか藤沢の区間が乗り放題の切符を買って移動しました。 次に向かったのは大船駅Just Because!で舞台のひとつになっている路線です。 懸垂式のモノレールということで休日なんかに行くと結構混んでいたりするのですが、平日だったので空いていました。

江ノ島駅

とりあえず江ノ島駅に到着。ここから青ブタのオープニングに出てくる場所に行くため、江の電で鎌倉高校前へ。 あ、江ノ島駅のこの踏切も聖地ですね。 f:id:yuhki0223:20181203213430j:plain 踏切上で道路が二つに分岐している面白い形の踏切です。 f:id:yuhki0223:20181203213354j:plain それで、メインはこっち。梓川くんが走ってるところだったと思います。 f:id:yuhki0223:20181203213606j:plain このバス停も出てましたね。

江ノ島

腰越まで歩いて江の電に乗って江ノ島駅へもどりました。 江ノ島駅から江ノ島までは結構距離があります。江ノ島電鉄江ノ島駅まで乗り入れてくれー! f:id:yuhki0223:20181203214543j:plain

道中でのツイートです↓

江ノ島への橋の途中に猫ちゃんもいました。

ということで江ノ島に到着。

ちょっと登ったところにまた聖地があります。

f:id:yuhki0223:20181203214936j:plain

そういえばこんな旗も立ってました。すごい。

江ノ島は、知られているように猫ちゃんがいっぱいいて、人類に優しいです。

f:id:yuhki0223:20181203215119j:plain

f:id:yuhki0223:20181203215153j:plain

ということで、歩き疲れてしまったので聖地巡礼はこのあたりで終わりました。

最後、江ノ島駅の写真を。

f:id:yuhki0223:20181203215305j:plain