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日目の記事です。 夢の中で宇宙旅行を楽しんでいたら、地球のタイムゾーンをすっかり失念していました。ごめんなさい!!! というか、このアドベントカレンダー担当者はほぼ埋まっていたのに全然投稿されていないですねーなんででしょうか。
本来なら、この記事は高速ナベアツの続きを書く予定だったのですが、忙しくて続きがあまり出来ていないのと他のネタが出来たので、ネタ替えをすることにしました。重ねてごめんなさい!! 高速ナベアツの続きは年度内に書ければなーと思います。
さて、弊部のアドベントカレンダーには他にもキーボードの記事が投稿されていました。
これです。彼いわく、このキーボードはHHKBより良いらしいです。
さて、まあキーボードと言えどもピンキリですよね。高いものは学生には手が出せないくらいの値段しますし、秋葉原で投げ売られているものを買えば100円とか、ひょっとしたらもっと安く手に入るかもしれません。 筆者はしがない三流ソフトウェアエンジニアではあるものの、やはり良いキーボードというものに憧憬を抱くわけです。そこで、今回タイトルの通りMajestouch Convertible 2というキーボードを買ったという次第です。
それで、まずこのMajestouch Convertible 2(以下、MC2と呼ぶ)を買うにあたって重要になるのは軸の色です。 MC2はメカニカルキーボードと呼ばれるキーボードの一つで、キーのひとつひとつが独立したスイッチになっています。 MC2ではこのスイッチにCherry MXというブランドのスイッチを使っています。詳しくは、次のページを見てみてください。
このページを見ると分かるように、キースイッチには幾つか種類がありその種類が軸の色によって決まっています。 筆者は、茶軸を買おうと決めました。
そして、アマゾンで注文して届きました。
— Δyuk!@hepp0k0 (@heppoko_yuki) December 28, 2018
それで、よく見ると赤軸を注文してしまっていました。間違えてしまった。まあ、違いはクリック感だけらしいのでそんなに気にしてません。
この日はちょうど友人とNTTの技術史料館に行く用事があったのでこのキーボードを持ち歩いてみることにしました。もともとキーボードは色々なところに持ち歩いて使おうと思っていたので良い機会です。
— Δyuk!@hepp0k0 (@heppoko_yuki) December 28, 2018
重量は電池を入れると1kgくらいあるので結構重かったです。リュックサックじゃなかったら持っていくのは迷いますね。
それで、打鍵感についてですが、赤軸でもけっこう良かったです。打っていて楽しいです。さっそくAtCoderの問題も解いてみました↓
Enterキーが今まで使っていたキーボードより長くてこのあたりの慣れが必要です。あ、キーボードの写真が未掲載でした。載せます。
こちらが今回買ったMC2のキーボード。
こちらが普段使っている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の場合、以下のテーブルを見ることでシステムコール番号を知ることが出来ます。
ということで、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で掛けたり割ったりするのはシフト演算で実現できるため、高速に計算できます。 また、整数同士の掛け算も割り算に比べれば低コストで計算することが出来ます。
これらの知識を元に、除算を以下のように変形します。
は定数なのではコンパイル時に計算することが出来ます。
ですから、実行時に計算するのは整数同士の掛け算(は整数に丸められます)と2nでの割り算だけなのでこれで除算の高速化が出来るわけです。
基本は上の通りですがこれでは誤差が出てしまう可能性があります。ですのでまだ工夫する必要は有るのですがこちらに関しては以下のブログを参考にしていただくとして、ここでは割愛いたします。
疲れてしまったので実装をどうするかについては「世界一速いナベアツに挑む②」で紹介しようと思います。お楽しみに!
参考文献
https://www.agner.org/optimize/instruction_tables.pdf
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)を使えば良い。
ファンクション番号は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分くらいのことです。
藤沢駅の北口は青ブタの作中に登場しています。
湘南モノレール
藤沢駅からは、700円で江ノ島とか鎌倉とか藤沢の区間が乗り放題の切符を買って移動しました。 次に向かったのは大船駅。Just Because!で舞台のひとつになっている路線です。 懸垂式のモノレールということで休日なんかに行くと結構混んでいたりするのですが、平日だったので空いていました。
— Δyuk!@hepp0k0 (@heppoko_yuki) 2018年12月3日
江ノ島駅
とりあえず江ノ島駅に到着。ここから青ブタのオープニングに出てくる場所に行くため、江の電で鎌倉高校前へ。 あ、江ノ島駅のこの踏切も聖地ですね。 踏切上で道路が二つに分岐している面白い形の踏切です。 それで、メインはこっち。梓川くんが走ってるところだったと思います。 このバス停も出てましたね。
江ノ島へ
腰越まで歩いて江の電に乗って江ノ島駅へもどりました。 江ノ島駅から江ノ島までは結構距離があります。江ノ島電鉄は江ノ島駅まで乗り入れてくれー!
道中でのツイートです↓
— Δyuk!@hepp0k0 (@heppoko_yuki) 2018年12月3日
液状化 pic.twitter.com/UMLWnnKhBy
— Δyuk!@hepp0k0 (@heppoko_yuki) 2018年12月3日
江ノ島への橋の途中に猫ちゃんもいました。
にゃん pic.twitter.com/xZs73jUP2E
— Δyuk!@hepp0k0 (@heppoko_yuki) 2018年12月3日
ということで江ノ島に到着。
ちょっと登ったところにまた聖地があります。
そういえばこんな旗も立ってました。すごい。
ヲタク pic.twitter.com/07U12XK3S4
— Δyuk!@hepp0k0 (@heppoko_yuki) 2018年12月3日
江ノ島は、知られているように猫ちゃんがいっぱいいて、人類に優しいです。
ということで、歩き疲れてしまったので聖地巡礼はこのあたりで終わりました。
最後、江ノ島駅の写真を。
30日でできる!OS自作入門を始めた[2日目]
半年ぶりの更新...。実は、もう本自体の内容はほとんどやってみたのだけれど、記事の更新が途中でとどまってからもう更新しなくなってしまっていた。
今回更新しようと思ったのは、僕が働かせてもらっている会社で自作OSの勉強会をしようということで、この本をやることになって、また1章から始めたのでせっかくだから復習も兼ねてまた記事の執筆に挑戦しようという志を持ったので。
ということで、久しぶりのOS自作入門スタート。
進行
ORG 0x7c00
ORG 0x7c00は、このプログラムがメモリのどこに読み込まれるかを示す疑似命令。 どうして0x7c00に読み込まれるかについては、以下の記事を見てなるほどなぁ。
https://www.glamenv-septzen.net/en/view/6
linuxのx86のアーキテクチャ依存の実装部分にも、0x7c00の文字がある。 https://github.com/torvalds/linux/blob/master/arch/x86/boot/header.S
そして、FAT12の使用に基づくヘッダがあって...
次にブートローダのプログラム本体。
初期化スべきレジスタを初期化して...
entry: MOV AX,0 MOV SS,AX MOV SP,0x7c00 MOV DS,AX MOV ES,AX
msgのアドレスを、SIに入れて...
そうそう、自分は当初この本をやっていたときに
[SI]
の意味がよく分からなかった記憶があるのだが、これはSIに入っているアドレスのところに有るものを参照する、みたいなものだ。 メモリ参照とか言うらしい。
putloopは文字を1文字ずつ配置するサブルーチンだ。 実行の流れは次のとおりである。
- SIが指すメモリの中身をALに入れる
- SIに1を足して次のアドレスを指すようにする
- ALが0なら、文字列の最後なので比較して0ならfinのルーチンに飛ぶ
- 1文字の表示機能を指定するためAHに0x0eを入れる
- BXにカラーコードの番号を入れる
- 割り込みしてビデオBIOSというものを呼び出す
- putloopのアドレスに戻ってループ
putloopで代入した15というカラーコードだがこれは白色である。 使える色は以下の通り。16ビットだなーってかんじ。 https://en.wikipedia.org/wiki/BIOS_color_attributes
BIOSで使える機能と使い方がまとめられている http://oswiki.osask.jp/?(AT)BIOS
ところで、
INT 0x10
は割り込み命令だが、これで割り込みベクタの0x10番目のアドレスに飛ぶ、という仕組みらしい。 この本を始めた当初は割り込みベクタなんて知らなかったが、もう一つの自作OS本、坂井先生の本を読んで知った。
finルーチンではHLTをループしてCPUを停止させるだけ。
あとはMBRの規格構造に沿って埋めるだけ。
ところで、私はnaskではなくnasmを使ってアセンブルしているのでRESB命令がうまく使えなかった。なので、以下のように改めて書いた。
TIMES 0x1fe-($-$$) DB 0
疑問
entryでなぜSPを0x7c00に初期化するのか。0に初期化するなら分かる気がするが...何か仕様等で決まっているのだろうか。- 上の疑問についてだが、単に0x7c00から配置されるブートローダーの上が空いているので0x7c00に初期化されるというだけだった。考えてみれば、SPを0に初期化するというのは意味がない。スタックは零アドレスに向かって伸びるのだから。
ISUCONで学生2位通過...のはずが再起動でこけてしまって非常に悔しいクギイィ!
昨日、今日とISUCONという大会が開催されていまして、初参加してみたので初陣の記録として記事を書いておきます。
ISUCONとは
ISUCONとは、Iikanjini Speed Up Contestの略でWebアプリケーションを高速化し、予め決められたURLのアクセスに対していくつレスポンスを返せたか、またどのくらいの負荷まで耐えられるか等によってスコアを付けそのスコアで勝敗を決めるコンテストです。
参加チーム
今回僕は、アルバイトとして勤務している会社のCTOとエンジニアの三人で「チーム終活」として参加しました。 二人共色々な面においてお強い方で、僕のようなWeb素人が参加して貢献出来るかは懐疑的なものでしたが、せっかく誘っていただいたのでありがたく参加しました。
やっていた対策
メンバーの誰一人としてISUCONに出たことがなかったので、何をすればいいのかよくわかりませんでしたが、とりあえず過去問を何回か解こうということで、本番の2週間前から2回ほどチームメンバーと集まって過去問演習をしました。
過去問演習とはいっても、実際に過去問環境を立てるのにけっこう手間取ってしまい、ほとんど演習らしいものは出来ませんでしたが、色々見識は深められたと思います。環境構築難しい...
本番の状況
僕たちは、土曜日に出場しました。 今回のお題は、チケット予約サイト?の高速化でした。なかなか出来の良いサイトで、コンテストのためにこんなもの作ってしまうのかーと少し感銘を受けました。
具体的にやったこととしては、開発環境の構築、解析ツール等の導入、ソースコードの最適化、余計なプロセスの殺害、DB鯖とHTTP&アプリ鯖の分散と言った感じです。
複数台のサーバーを渡されるというのが通年の慣例のようですが、上で述べたように初陣だったため知りませんでした。そのため、このサーバーをどう使うか迷いましたが結局DB鯖とHTTP&アプリ鯖の分散に使ったという感じです。
この分散を行うためには、ソースコードの最適化を行う必要がありました。 なぜなら、この分散を行ってしまうととあるページがおそすぎてベンチマーク時にタイムアウトしてしまったからです。
実際にソースコードを覗いてみると、明らかに確信犯的な悪魔実装をしている箇所が見受けられました。
そうしたソースコードの変更等を含め建設的に改善を続けていった結果、最終的に25452というスコアを叩き出すことが出来ました。
このスコアは、学生2位になりえたスコア(後の画像参照)でした。他チームの状況等からして予選通過を確信していた僕達は、「よっしゃ予選通過や」とコンテスト終了30分前に片付けをはじめ、悠々とした態度でいました。
結果
予選敗退。
何度も言いますが、初陣だった私達は再起動試験というものがあることをすっかり忘却してしまっていたのです。 結果、コンテスト終了後の再起動試験で見事コケたらしく予選敗退という結果になってしまいました。
悔しい!!!
これからISUCONに出ようと思っているみなさんも、分かっているとは思いますが、再起動時にこけないか確認しましょう。僕との約束です。
PS: 25452ってスコア、25252だったら矢澤にこ(ガタッ