2020-04-18

AtCoder に登録したら解くべき精選過去問 10 問を C 言語(のコード中に埋め込んだ，アセンブラで生成した機械語)で解いてみた ② (第5問から第6問まで)

この記事は前回の続きです．前回は「C 言語で解いてみた」というほぼほぼ詐欺のようなタイトルでしたが，今回はちゃんと書きました．

そもそも何をしているの？

さて，ここら辺で C 言語の中に機械語を埋め込む方法について説明しておきましょう．提出コードの基本的な形は前回も書いたとおり次のようになっています．

#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
#include <string.h>
#include <stdio.h>

const char main_[] = { /* ここに解を求めるプログラムの中身を書く */ };

int main(void){
	int fd = open("/dev/zero", O_RDONLY);
	/* 返り値 */ (*solve)(/* 引数 */) = mmap(NULL, sizeof main_, PROT_WRITE | PROT_EXEC, MAP_PRIVATE, fd, 0);
	memcpy(solve, main_, sizeof main_);

	/* 入力を scanf などで受け取って solve 関数に渡し，返り値を出力する */

	close(fd);
	munmap(solve, sizeof main_);
	return 0;
}

これについて説明します．

まず，関数というのは配列です．その中には機械語がつらつらと書かれています．ならば，動的に確保した配列の中に機械語を書き込めば，それは関数になるわけです．

C で配列を動的に確保する方法は複数ありますが，その一つが mmap 関数を使うやり方です． mmap 関数とは次のような関数です．

#include <sys/mman.h>
void *mmap(void *addr, size_t len, int prot, int flags, int fildes, off_t off);

第 5 引数 fildes にファイルを指定すると，その中身をメモリ上にマップして読み書きすることができる，そんな関数です．ここで，普通のファイルの代わりに /dev/zero を指定してやれば，メモリ上に 0 で埋め尽くされた領域が作られて使えるようになる，つまりメモリを確保することができるわけです．

またこの関数は，第 3 引数に prot という int 値をとります．ここでは PROT_READ ， PROT_WRITE ， PROT_EXEC の組み合わせまたは PROT_NONE が指定され，これによって確保される領域に対してどのようなアクセスができるか決まります． PROT_READ だけを指定すると読み込み専用になり， PROT_READ | PROT_WRITE を指定すると読み書きができます．そして， PROT_EXEC を指定すると実行が可能になるのです．

よって，このプログラムは， open 関数で /dev/zero を開き，それを用いて mmap 関数で実行可能なメモリ領域を確保し， memcpy 関数を使ってそこに機械語の書かれた配列の内容をコピーし，関数として呼び出しているわけです．

第5問 B - Some Sums

カラクリも分かったところで早速 5 問目に取り掛かりましょう．

入力は整数 n, a, b です． solve 関数は int solve(int n, int a, int b) とします．

1 以上 n 以下の整数を小さい順に見ていくのですが，この際にその各桁の和を計算していきます．
$x$ の各桁の和を $f(x)$ と表すと， $x$ が 10 の倍数でなければ $f(x) = f(x - 1) + 1$ ， $x$ が 10 で 1 回だけ割り切れるならば $f(x) = f(x - 1) - 8$ であり，一般に $x$ が 10 で $k$ 回割り切れるならば $f(x) = f(x - 1) - 9k + 1$ が成り立ちます．

何回割り切れるか調べる際に div 命令を使いますが，これが実はちょっと楽にできるようになっています． div 命令は rdx レジスタと rax レジスタをあわせて 128bit としたものを割り算し，商を rax レジスタに，余りを rdx レジスタに格納します．ゆえに，そのままの状態で再度 div 命令を行うと，商をもう一度割り算することができるのです．実際にやってみると，ある数が 10 で何回割れるか知りたければ，

	mov (調べたい数), %rax
	xor %rdx, %rdx
div:
	div (整数10が格納されたレジスタ)
	inc (答えを格納するレジスタ)
	cmp $0, %rdx
	je div
	dec (答えを格納するレジスタ)

となります(一度余計にインクリメントしてからデクリメントしているのは，ジャンプ命令を減らして全体を短くするためです)．

1 以上 n 以下の数を走査するためのカウンタには rcx レジスタを使い，各桁の和は r8 レジスタに入れておきます．答えを格納する rax レジスタは割り算に利用するので r9 レジスタに一時的に格納し，同様に第 3 引数の入っている rdx レジスタの中身も r10 レジスタに避難させます．割る数 10 は r11 レジスタに入れておきます．いやー，レジスタがたくさんあるって素晴らしいですね．

最終的に solve 関数は以下のようになります．

	mov $1, %rcx # <- 1 ... n
	xor %r8, %r8 # <- 各桁の和
	xor %r9, %r9 # <- 答え
	mov %rdx, %r10 # <- 第 3 引数 (B)
	mov $10, %r11 # <- 割る数 10
loop:
	mov %rcx, %rax
	xor %rdx, %rdx
div:
	div %r11
	sub $9, %r8
	cmp $0, %rdx
	je div
	add $10, %r8
	cmp %r8, %rsi # 第 2 引数 (A) と比較
	ja out
	cmp %r8, %r10 # 第 3 引数 (B) と比較
	jb out
	add %rcx, %r9 # 範囲内なら答えに足す
out:
	inc %rcx
	cmp %rdi, %rcx # カウンタが第 1 引数 (N) 以下の間繰り返す
	jbe loop
	mov %r9, %rax
	ret

https://atcoder.jp/contests/abc083/submissions/11999068

第 6 問 B - Card Game for Two

ついにソートを書くときが来ました．配列を降順ソートして交互に見ていけばよいです．ソートアルゴリズムにも色々ありますが，今回はクイックソートを実装しようと思います．

入力は整数 n と配列 a です．配列 a の要素は 32bit 整数型とし， solve 関数は int solve(int n, int *a) とします．

クイックソートを書くうえで，今までと違う部分があります．それは，「コンパイル時に定められた個数だけの変数を使って書くことができない」という点です．クイックソートはよく再帰関数を使って実装されますが，再帰関数は呼び出される度に新たな自動変数を確保します．どこに確保するかというと，(再帰が深すぎたときに起こるスタックオーバーフローというエラーからも分かる通り)スタック領域です．今回の問題ではそのスタック領域を使ってみたいと思います．

といっても，スタックを使うのはそんなに難しくはありません．使うのは次の 2 つの命令です．

	push (レジスタ)
	pop (レジスタ)

push 命令は，レジスタの中身をスタックにプッシュします． pop 命令は，スタックのトップをレジスタに格納してスタックから削除します(C++ の std::stack でいうところの top と pop を同時にやる)．これを使えば，関数の再帰呼び出しと実質同じことができるわけです(DFSとかも再帰関数でやるやり方とライブラリのスタックでやるやり方がありますね)．

また，このスタックはプログラムが様々な目的に使用しているので，初期状態が「空」ではない上に，関数呼び出し前と呼び出し後で同じ状態を保っていなければいけません．そこで，最初にスタックに何らかのマジックナンバーをプッシュしておき，マジックナンバーが取り出された時点で入れた分は全て取り出されたと分かるようにします．

クイックソートでは，配列内の範囲 [l, r) をソートするのが部分問題となります．よってスタックにプッシュするのは左端 l と右端 r です．今回は右端→左端の順にプッシュし，左端→右端の順にポップされるようにします．

	push (マジックナンバー)
	push (全体の右端)
	push (全体の左端)
loop:
	pop (レジスタ1) # <-今見たい部分の左端
	cmp (マジックナンバー), (レジスタ1)
	je sortend # <- 取り出されたのがマジックナンバーならソート終了
	pop (レジスタ2) # <-今見たい部分の右端
	# ここで部分問題を解く
	jmp loop
sortend:

配列のインデックスを保存しておくと，後で sizeof(int) = 4 倍して配列の先頭アドレスに足す操作をしなくてはなりません．そこでインデックスの代わりに全部アドレスで管理してしまうことにします．マジックナンバーは 0 にします．

スタックからポップした左端は r8 レジスタ，右端は r9 レジスタに入れることにします．ここまでで一通りコードを書くと次のようになります．

	push $0
	mov %rdi, %rax # <- 第 1 引数には配列の個数 n が入っている
	sal $2, %rax # <- 4 倍する
	add %rsi, %rax # <- 第 2 引数 a を足す: 配列の終端アドレス
	push %rax
	push %rsi
loop:
	pop %r8
	cmp $0, %r8
	je sortend
	pop %r9
	# ここで部分問題を解く
	jmp loop
sortend:

さて，簡単のためピボットは先頭の要素とします．見たい範囲の左端 (r8 レジスタ)と右端 (r9 レジスタ) をそれぞれ r10 レジスタと r11 レジスタにコピーします．

	mov %r8, %r10
	mov %r9, %r11

r10 レジスタを右に動かしていき，ピボットより小さい値を探します．

	mov (%r8), %eax # <- ピボット
left:
	add $4, %r10
	movsx (%r10), %ecx
	cmp %eax, %ecx
	jae left

同様に r11 レジスタを左に動かしていき，ピボットより大きい値を探します．

right:
	sub $4, %r11
	movsx (%r11), %edx
	cmp %eax, %edx
	jb right

この時点で r10 が r11 よりも左にあれば， 2 つの値をスワップし，ふたたび r10 と r11 を動かしていきます．

	cmp %r10, %r11
	jbe end
	mov %ecx, (%r11)
	mov %edx, (%r10)
	jmp left # 上に戻る
end:

r10 が r11 よりも右にあれば， r10 より左にはピボットより大きい値しかなく， r11 より右にはピボットより小さい値しかないので， r11 の場所の値とピボットを入れ替えて，次の部分問題を解きます．次の部分問題は，左端から r11 までと， r11 の右隣から右端までです．

	mov %edx, (%r8)
	mov %eax, (%r11)
	push %r11
	push %r8
	add $4, %r11
	push %r9
	push %r11
	jmp loop # 上に戻る

これを繰り返すことでソートができます．再帰の終了条件は，見ている部分の要素が 1 以下になったときで，これは部分問題を解く前に見ます．

	mov %r9, %rcx # <- 右端のアドレスから
	sub %r8, %rcx # <- 左端のアドレスを引いて
	cmp $4, %rcx # <- 4 以下だったら
	jbe loop # <- continue

ソート部分を書き終えました．あとはこの配列を先頭から見て，足して引いて足して引いて……を繰り返したものが答えです．

	xor %rax, %rax # <- 答えを入れるレジスタを 0 初期化
	xor %rcx, %rcx # <- カウンタも 0 初期化
	xor %rdx, %rdx # <- 0 なら足し， 1 なら引く
loop2:
	cmp %rcx, %rdi
	je end
	cmp $0, %rdx # 足すか引くか
	je add
	sub (%rsi, %rcx, 4), %rax # 引く
	dec %rdx # 次は足す
	jmp sub
add:
	add (%rsi, %rcx, 4), %rax # 足す
	inc %rdx #次は引く
sub:
	inc %rcx # カウンタをインクリメント
	ja loop2 # 上に戻る

solve 関数全体と， AC コードのリンクです．https://atcoder.jp/contests/abc088/submissions/12041414

	push $0
	mov %rdi, %rax
	sal $2, %rax
	add %rsi, %rax
	push %rax
	push %rsi
loop:
	pop %r8
	cmp $0, %r8
	je sortend
	pop %r9
	mov %r9, %rcx
	sub %r8, %rcx
	cmp $4, %rcx
	jbe loop 
	mov %r8, %r10
	mov %r9, %r11
	mov (%r8), %eax
left:
	add $4, %r10
	movsx (%r10), %ecx
	cmp %eax, %ecx
	jae left
right:
	sub $4, %r11
	movsx (%r11), %edx
	cmp %eax, %edx
	jb right
	cmp %r10, %r11
	jbe end
	mov %ecx, (%r11)
	mov %edx, (%r10)
	jmp left
end:
	mov %edx, (%r8)
	mov %eax, (%r11)
	push %r11
	push %r8
	add $4, %r11
	push %r9
	push %r11
	jmp loop
sortend:
	xor %rax, %rax
	xor %rcx, %rcx
	xor %rdx, %rdx
loop2:
	cmp %rcx, %rdi
	je end
	cmp $0, %rdx
	je add
	sub (%rsi, %rcx, 4), %rax
	dec %rdx
	jmp sub
add:
	add (%rsi, %rcx, 4), %rax
	inc %rdx
sub:
	inc %rcx
	ja loop2
	ret

お疲れ様でした．この調子で第 10 問までいければいいなと思っています．

2020-04-16

i3window manager 俺々式 config 法

Arch Linux

数あるウィンドウマネージャの中でも，特に使いやすい(と私が感じている)タイル型ウィンドウマネージャが i3 window manager．一部の人たちの間では arch ， vim と併せてオタク 3 点セットなどと言われています(ソース)．i3 はその無駄のなさ，スタイルの良さの他に，設定ファイルが細かく書けるのも魅力の 1 つだと思います．そこで今回は， i3 がもっと使いやすくなる(と私が考える)設定ファイルの書き方を紹介します．

ウィンドウの境界

default_border pixel 1

これは私の好みなのですが，後で focus と組み合わせることで効果を発揮します．

モードの活用

i3 には，モードという概念が存在します．例えばテンプレート設定(/etc/i3/config)では，ウィンドウの大きさを変更する resize モードが用意されています．簡単に説明すると次のような感じです．

bindsym $mod+r mode "resize"
# $mod+r を押すことで resize モードに入ることができる

mode "resize" {
    bindsym $left resize shrink width 10 px
    # この中括弧内の bindsym / bindcode は， resize モードに入ったときだけ有効になる
    
    bindsym Return mode "default"
    # Returnキーを押すことで default モードに戻ることができる
}

# 中括弧の外側は default モード

この設定のもとでウィンドウの幅を狭めたいときは，まず $mod+r を押して resize モードに入り，左キーを何回か押して好きな幅まで狭めた後， Return キーを押して default モードに戻れば良いわけです．

これを活用し，様々な操作を種類ごとにまとめてモードの中に入れてしまおうと思います．

exit モード

exit / restart / reload の 3 つのコマンドを exit モードに入れます．

bindsym $mod+Shift+e mode "exit"
mode "exit" {
    bindsym Return mode "default"
    bindsym e exit
    bindsym r restart
    bindsym w reload
}

exit 時に終了したいプロセスがあれば， exit 時に kill してしまってもよいでしょう．

    # bindsym e exit の代わりに: 
    bindsym e exec killall mozc_server; exit
    # mozc_server を終了し， exit する

また，どんなモードを定義するときも，必ず default モードに戻る手段を書くのを忘れないようにしましょう．下手するとターミナルやランチャーすら起動できなくなって死にます．

layout モード

既に画面上に並んでいるウィンドウのレイアウトを変更するコマンドを layout モードに入れます．

bindsym $mod+l mode "layout"
mode "layout" {
    bindsym Return mode "default"
    bindsym h layout splith; mode "default"
    bindsym v layout splitv; mode "default"
    bindsym t layout tabbed; mode "default"
    bindsym s layout stacking; mode "default"
    bindsym f floating toggle; mode "default"
}

layout モードのまま何回もレイアウトを変更することはあまり無いと思うので，一度操作したら自動的に default モードに戻るようにしています．

split モード

現在のウィンドウを分割して新しいウィンドウを作るコマンドを split モードに入れます．

bindsym $mod+s mode "split"
mode "split" {
    bindsym Return mode "default"
    bindsym h split horizontal; mode "default"
    bindsym v split vertical; mode "default"
}

focus モード

フォーカスしているウィンドウを変更するコマンドを focus モードに入れます．

bindsym $mod+f border normal; mode "focus"
mode "focus" {
    bindsym Return border pixel 1; mode "default"
    bindsym h border pixel 1; focus left; border normal
    bindsym j border pixel 1; focus down; border normal
    bindsym k border pixel 1; focus up; border normal
    bindsym l border pixel 1; focus right; border normal
    bindsym p border pixel 1; focus parent
    bindsym c focus child; border normal
    bindsym f border pixel 1; focus mode_toggle; border normal
}

上下左右キーではなく vim-like な h/j/k/l を使っているのは個人的な趣味です．また， focus モードでは，フォーカスされているウィンドウの境界が pixel ではなく normal，すなわちウィンドウタイトルが表示される状態になるようにしています．

move モード

ウィンドウを移動するコマンドを move モードに入れます．

bindsym $mod+m border normal; mode "move"
mode "move" {
    bindsym Return border pixel 1; mode "default"
    bindsym h move left
    bindsym j move down
    bindsym k move up
    bindsym l move right
    bindsym c move absolute position center
    bindsym m move position mouse
}

resize モード

ウィンドウの大きさを変更するコマンドを resize モードに入れます．

bindsym $mod+r border normal; mode "resize"
mode "resize" {
    bindsym Return border pixel 1; mode "default"
    bindsym h resize shrink width
    bindsym Shift+h resize shrink width 50 px
    bindsym j resize grow height
    bindsym Shift+j resize grow height 50 px
    bindsym k resize shrink height
    bindsym Shift+k resize shrink height 50 px
    bindsym l resize grow width
    bindsym Shift+l resize grow width 50 px
}

workspace モード

ワークスペースは， 1 つのディスプレイに複数の仮想デスクトップを作ることができる便利な機能です．たくさんある方が嬉しいので， workspace モード内でたくさん作っちゃいましょう．

bindsym $mod+w mode "workspace"
mode "workspace" {
    bindsym Return mode "default"
    bindsym 0 workspace 0; mode "default"
    bindsym Shift+0 move container to workspace 0; workspace 0; mode "default"
    bindsym 1 workspace 1; mode "default"
    bindsym Shift+1 move container to workspace 1; workspace 1; mode "default"
    ……
    bindsym 9 workspace 9; mode "default"
    bindsym Shift+9 move container to workspace 9; workspace 9; mode "default"
    bindsym A workspace A; mode "default"
    bindsym Shift+A move container to workspace A; workspace A; mode "default"
    bindsym B workspace B; mode "default"
    bindsym Shift+B move container to workspace B; workspace B; mode "default"
    ……
    bindsym Z workspace Z; mode "default"
    bindsym Shift+Z move container to workspace Z; workspace Z; mode "default"
}

これで 0〜9，A〜Z あわせて 36 個のワークスペースを作ることができました．

その他のコマンド

いくつかのコマンドは， default モードで使えるようにしておきます．

bindsym $mod+Return exec terminator
bindsym $mod+Shift+space exec rofi -show run
bindsym $mod+Delete kill
bindsym $mod+Shift+f fullscreen toggle

モード同士の切り替え

focus モードから resize モードに切り替えたいときもあるでしょう．そのときにいちいち default モードに戻らずに済むようにします．

mode "focus" {
    ……
    # 追記:
    bindsym $mod+Shift+e border pixel 1; mode "exit"
    bindsym $mod+l border pixel 1; mode "layout"
    bindsym $mod+s border pixel 1; mode "split"
    bindsym $mod+m mode "move"
    bindsym $mod+r mode "resize"
    bindsym $mod+w border pixel 1; mode "workspace"
}

他のモードについても同様にこれを書きます．

説明文

コマンドが多すぎて覚えられないので，どこかに説明文を表示したいです． i3bar には現在のモードが表示されるようになっているので，ここを変えればよさそうです．

# mode "layout" { の代わりに: 
mode "layout [h: splith] [v: splitv] [t: tabbed] [s: stacking] [f: floating toggle]" {
    ……
}

まとめ

以上を全てまとめると次のような config になります．

bar{
	status_command i3status
}
default_border pixel 1
bindsym Mod4+Return exec terminator
bindsym Mod4+Shift+space exec rofi -show run
bindsym Mod4+Delete kill
bindsym Mod4+Shift+f fullscreen toggle
bindsym Mod4+Shift+e mode "exit [e: exit] [r: restart] [w: reload]"
bindsym Mod4+l mode "layout [h: splith] [v: splitv] [t: tabbed] [s: stacking] [f: floating toggle]"
bindsym Mod4+s mode "split [h: horizontal] [v: vertical]"
bindsym Mod4+f border normal; mode "focus [h: left] [j: down] [k: up] [l: right] [p: parent] [c: child] [f: floating]"
bindsym Mod4+m border normal; mode "move [h: left] [j: down] [k: up] [l: right] [c: center] [m: mouse]"
bindsym Mod4+r border normal; mode "resize [h: shrink width] [j: grow height] [k: shrink height] [l: grow width]"
bindsym Mod4+w mode "workspace"
mode "exit [e: exit] [r: restart] [w: reload]"{
	bindsym Return mode "default"
	bindsym e exec killall mozc_server; exit
	bindsym r restart
	bindsym w reload
	bindsym Mod4+l mode "layout [h: splith] [v: splitv] [t: tabbed] [s: stacking] [f: floating toggle]"
	bindsym Mod4+s mode "split [h: horizontal] [v: vertical]"
	bindsym Mod4+f border normal; mode "focus [h: left] [j: down] [k: up] [l: right] [p: parent] [c: child] [f: floating]"
	bindsym Mod4+m border normal; mode "move [h: left] [j: down] [k: up] [l: right] [c: center] [m: mouse]"
	bindsym Mod4+r border normal; mode "resize [h: shrink width] [j: grow height] [k: shrink height] [l: grow width]"
	bindsym Mod4+w mode "workspace"
}
mode "layout [h: splith] [v: splitv] [t: tabbed] [s: stacking] [f: floating toggle]"{
	bindsym Return mode "default"
	bindsym h layout splith; mode "default"
	bindsym v layout splitv; mode "default"
	bindsym t layout tabbed; mode "default"
	bindsym s layout stacking; mode "default"
	bindsym f floating toggle; mode "default"
	bindsym Mod4+Shift+e mode "exit [e: exit] [r: restart] [w: reload]"
	bindsym Mod4+s mode "split [h: horizontal] [v: vertical]"
	bindsym Mod4+f border normal; mode "focus [h: left] [j: down] [k: up] [l: right] [p: parent] [c: child] [f: floating]"
	bindsym Mod4+m border normal; mode "move [h: left] [j: down] [k: up] [l: right] [c: center] [m: mouse]"
	bindsym Mod4+r border normal; mode "resize [h: shrink width] [j: grow height] [k: shrink height] [l: grow width]"
	bindsym Mod4+w mode "workspace"
}
mode "split [h: horizontal] [v: vertical]"{
	bindsym Return mode "default"
	bindsym h split horizontal; mode "default"
	bindsym v split vertical; mode "default"
	bindsym Mod4+Shift+e mode "exit [e: exit] [r: restart] [w: reload]"
	bindsym Mod4+l mode "layout [h: splith] [v: splitv] [t: tabbed] [s: stacking] [f: floating toggle]"
	bindsym Mod4+f border normal; mode "focus [h: left] [j: down] [k: up] [l: right] [p: parent] [c: child] [f: floating]"
	bindsym Mod4+m border normal; mode "move [h: left] [j: down] [k: up] [l: right] [c: center] [m: mouse]"
	bindsym Mod4+r border normal; mode "resize [h: shrink width] [j: grow height] [k: shrink height] [l: grow width]"
	bindsym Mod4+w mode "workspace"
}
mode "focus [h: left] [j: down] [k: up] [l: right] [p: parent] [c: child] [f: floating]"{
	bindsym Return border pixel 1; mode "default"
	bindsym h border pixel 1; focus left; border normal
	bindsym j border pixel 1; focus down; border normal
	bindsym k border pixel 1; focus up; border normal
	bindsym l border pixel 1; focus right; border normal
	bindsym p border pixel 1; focus parent
	bindsym c focus child; border normal
	bindsym f border pixel 1; focus mode_toggle; border normal
	bindsym Mod4+Shift+e border pixel 1; mode "exit [e: exit] [r: restart] [w: reload]"
	bindsym Mod4+l border pixel 1; mode "layout [h: splith] [v: splitv] [t: tabbed] [s: stacking] [f: floating toggle]"
	bindsym Mod4+s border pixel 1; mode "split [h: horizontal] [v: vertical]"
	bindsym Mod4+m mode "move [h: left] [j: down] [k: up] [l: right] [c: center] [m: mouse]"
	bindsym Mod4+r mode "resize [h: shrink width] [j: grow height] [k: shrink height] [l: grow width]"
	bindsym Mod4+w border pixel 1; mode "workspace"
}
mode "move [h: left] [j: down] [k: up] [l: right] [c: center] [m: mouse]"{
	bindsym Return border pixel 1; mode "default"
	bindsym h move left
	bindsym Shift+h move left 50 px
	bindsym j move down
	bindsym Shift+j move down 50 px
	bindsym k move up
	bindsym Shift+k move up 50 px
	bindsym l move right
	bindsym Shift+l move right 50 px
	bindsym c move absolute position center
	bindsym m move position mouse
	bindsym Mod4+Shift+e border pixel 1; mode "exit [e: exit] [r: restart] [w: reload]"
	bindsym Mod4+l border pixel 1; mode "layout [h: splith] [v: splitv] [t: tabbed] [s: stacking] [f: floating toggle]"
	bindsym Mod4+s border pixel 1; mode "split [h: horizontal] [v: vertical]"
	bindsym Mod4+f mode "focus [h: left] [j: down] [k: up] [l: right] [p: parent] [c: child] [f: floating]"
	bindsym Mod4+r mode "resize [h: shrink width] [j: grow height] [k: shrink height] [l: grow width]"
	bindsym Mod4+w border pixel 1; mode "workspace"
}
mode "resize [h: shrink width] [j: grow height] [k: shrink height] [l: grow width]"{
	bindsym Return border pixel 1; mode "default"
	bindsym h resize shrink width
	bindsym Shift+h resize shrink width 50 px
	bindsym j resize grow height
	bindsym Shift+j resize grow height 50 px
	bindsym k resize shrink height
	bindsym Shift+k resize shrink height 50 px
	bindsym l resize grow width
	bindsym Shift+l resize grow width 50 px
	bindsym Mod4+Shift+e border pixel 1; mode "exit [e: exit] [r: restart] [w: reload]"
	bindsym Mod4+l border pixel 1; mode "layout [h: splith] [v: splitv] [t: tabbed] [s: stacking] [f: floating toggle]"
	bindsym Mod4+s border pixel 1; mode "split [h: horizontal] [v: vertical]"
	bindsym Mod4+f mode "focus [h: left] [j: down] [k: up] [l: right] [p: parent] [c: child] [f: floating]"
	bindsym Mod4+m mode "move [h: left] [j: down] [k: up] [l: right] [c: center] [m: mouse]"
	bindsym Mod4+w border pixel 1; mode "workspace"
}
mode "workspace"{
	bindsym Return mode "default"
	bindsym 0 workspace 0; mode "default"
	bindsym Shift+0 move container to workspace 0; workspace 0; mode "default"
	bindsym 1 workspace 1; mode "default"
	bindsym Shift+1 move container to workspace 1; workspace 1; mode "default"
	bindsym 2 workspace 2; mode "default"
	bindsym Shift+2 move container to workspace 2; workspace 2; mode "default"
	bindsym 3 workspace 3; mode "default"
	bindsym Shift+3 move container to workspace 3; workspace 3; mode "default"
	bindsym 4 workspace 4; mode "default"
	bindsym Shift+4 move container to workspace 4; workspace 4; mode "default"
	bindsym 5 workspace 5; mode "default"
	bindsym Shift+5 move container to workspace 5; workspace 5; mode "default"
	bindsym 6 workspace 6; mode "default"
	bindsym Shift+6 move container to workspace 6; workspace 6; mode "default"
	bindsym 7 workspace 7; mode "default"
	bindsym Shift+7 move container to workspace 7; workspace 7; mode "default"
	bindsym 8 workspace 8; mode "default"
	bindsym Shift+8 move container to workspace 8; workspace 8; mode "default"
	bindsym 9 workspace 9; mode "default"
	bindsym Shift+9 move container to workspace 9; workspace 9; mode "default"
	bindsym A workspace A; mode "default"
	bindsym Shift+A move container to workspace A; workspace A; mode "default"
	bindsym B workspace B; mode "default"
	bindsym Shift+B move container to workspace B; workspace B; mode "default"
	bindsym C workspace C; mode "default"
	bindsym Shift+C move container to workspace C; workspace C; mode "default"
	bindsym D workspace D; mode "default"
	bindsym Shift+D move container to workspace D; workspace D; mode "default"
	bindsym E workspace E; mode "default"
	bindsym Shift+E move container to workspace E; workspace E; mode "default"
	bindsym F workspace F; mode "default"
	bindsym Shift+F move container to workspace F; workspace F; mode "default"
	bindsym G workspace G; mode "default"
	bindsym Shift+G move container to workspace G; workspace G; mode "default"
	bindsym H workspace H; mode "default"
	bindsym Shift+H move container to workspace H; workspace H; mode "default"
	bindsym I workspace I; mode "default"
	bindsym Shift+I move container to workspace I; workspace I; mode "default"
	bindsym J workspace J; mode "default"
	bindsym Shift+J move container to workspace J; workspace J; mode "default"
	bindsym K workspace K; mode "default"
	bindsym Shift+K move container to workspace K; workspace K; mode "default"
	bindsym L workspace L; mode "default"
	bindsym Shift+L move container to workspace L; workspace L; mode "default"
	bindsym M workspace M; mode "default"
	bindsym Shift+M move container to workspace M; workspace M; mode "default"
	bindsym N workspace N; mode "default"
	bindsym Shift+N move container to workspace N; workspace N; mode "default"
	bindsym O workspace O; mode "default"
	bindsym Shift+O move container to workspace O; workspace O; mode "default"
	bindsym P workspace P; mode "default"
	bindsym Shift+P move container to workspace P; workspace P; mode "default"
	bindsym Q workspace Q; mode "default"
	bindsym Shift+Q move container to workspace Q; workspace Q; mode "default"
	bindsym R workspace R; mode "default"
	bindsym Shift+R move container to workspace R; workspace R; mode "default"
	bindsym S workspace S; mode "default"
	bindsym Shift+S move container to workspace S; workspace S; mode "default"
	bindsym T workspace T; mode "default"
	bindsym Shift+T move container to workspace T; workspace T; mode "default"
	bindsym U workspace U; mode "default"
	bindsym Shift+U move container to workspace U; workspace U; mode "default"
	bindsym V workspace V; mode "default"
	bindsym Shift+V move container to workspace V; workspace V; mode "default"
	bindsym W workspace W; mode "default"
	bindsym Shift+W move container to workspace W; workspace W; mode "default"
	bindsym X workspace X; mode "default"
	bindsym Shift+X move container to workspace X; workspace X; mode "default"
	bindsym Y workspace Y; mode "default"
	bindsym Shift+Y move container to workspace Y; workspace Y; mode "default"
	bindsym Z workspace Z; mode "default"
	bindsym Shift+Z move container to workspace Z; workspace Z; mode "default"
	bindsym Mod4+Shift+e mode "exit [e: exit] [r: restart] [w: reload]"
	bindsym Mod4+l mode "layout [h: splith] [v: splitv] [t: tabbed] [s: stacking] [f: floating toggle]"
	bindsym Mod4+s mode "split [h: horizontal] [v: vertical]"
	bindsym Mod4+f border normal; mode "focus [h: left] [j: down] [k: up] [l: right] [p: parent] [c: child] [f: floating]"
	bindsym Mod4+m border normal; mode "move [h: left] [j: down] [k: up] [l: right] [c: center] [m: mouse]"
	bindsym Mod4+r border normal; mode "resize [h: shrink width] [j: grow height] [k: shrink height] [l: grow width]"
}

これで設定は完了です． i3 がとても使いやすくなります．
これだけの設定を手書きするのはとても面倒なので，適当にプログラムでも走らせるといいでしょう．

github にリンクを載せておきます．これの config.c を適当に自分好みに書き換えてから make を走らせれば，あなただけの設定ファイルが作れます
github.com

この記事があなたの役に立てば幸いです．

2020-03-02

デュアルブートしていたらWindows更新後にLinuxが起動できなくなった話

Arch Linux

元の状態

Windows / Arch Linux でデュアルブートしていました．パーティションは次のように分けていました．

/dev/sda1 ― Windows/Linux 共用のブートパーティション． Windows が入っている状態で PC を買ったので Linux インストール以前から存在したが， FAT32 だったので*1ここに Linux のブートローダもインストールしていた． Linux 起動時は /boot にマウントされる．
/dev/sda2 ― Windows の謎の予約パーティション．
/dev/sda3 ― Windows の C: ドライブ．
/dev/sda4 ― Linux の / ．
/dev/sda5 ― Linux の /home ．
/dev/sda6 ― Windows と Linux の共有パーティション． FAT32 でフォーマットしていて， Linux では /share ， Windows では D: ドライブ．
/dev/sda7 ― Windows の修復用パーティション．

このため，起動時に参照される /etc/fstab には

/dev/sda4           	/         	ext4      	rw,relatime	0 1
/dev/sda6           	/home     	ext4      	rw,relatime	0 2
/dev/sda1           	/boot     	vfat      	rw,(省略)	0 2
/dev/sda7		/share		vfat		rw,umask=000	0 2

のように書いてありました(といってもほとんど genfstab が書いてくれたものだけれど)．つまり， UUID や PARTUUID 等ではなくパーティション番号によってマウントするパーティションを指定していたわけです．

何が起こったか

Windows を起動したところ，更新が始まりました．いつもより長いなと思っていたのですが，この更新の後， Linux を起動すると

You are in emergency mode. After logging in, type "journalctl -xb" to view
system logs, "systemctl reboot" to reboot, "systemctl default" or "exit"
to boot into default mode.
Give root password for maintenance
(or press Control-D to continue):

というメッセージが表示されて起動が止まるようになってしまいました．調べてみたところ， Windows の更新によって新しいパーティションが作られてしまったのが原因でした．もともと Windows の C: ドライブだった /dev/sda3 が 2 つに分かれ， /dev/sda3 と /dev/sda4 になってしまった*2せいで，それ以降のパーティション番号が全て 1 つずつズレてしまったのです．

対処法

上のメッセージが表示された段階でパスワードを入力すると，不完全ながらもコマンド入力によって指示を出すことができます．ここで /etc/fstab を開き， /dev/sda4 ， /dev/sda5 ， /dev/sda6 をそれぞれ /dev/sda5 ， /dev/sda6 ， /dev/sda7 に書き換えることで，この問題は解決します．(ちなみに vim は使えました)
ちなみにですが， fstab を UUID や PARTUUID で書いておけば，このような問題は発生しません．Arch Linux のインストールにおいては， genfstab で fstab を生成するときに -U オプションを付けておくことで UUID によってパーティションが指定されるようになります．

*1:たしか UEFI が FAT32 を要請している

*2:OEM パーティションとかいうよく分からないやつ……修復に使われるそうです

2020-02-23

MOD 逆数

プログラミング

$n$ を整数とすると， $n$ と互いに素な任意の整数 $a$ に対し， $ax \equiv 1\ ({\rm mod}\ n)$ を満たす整数 $x\ (0 \leq x < n)$ がただ一つ存在します．この $x$ を， $n$ を法としたときの逆数といい，競技プログラミングで頻繁に役立ちます．今回はこれを計算するコードを C で書いていきます．

数学的な解き方

$ax \equiv 1\ ({\rm mod}\ n)$ ならば，ある整数 $x'$ が存在して $ax + nx' = 1$ です．すると，これは $nx' \equiv 1\ ({\rm mod}\ a)$ と書き換えられます．ここで $n$ を $a$ で割った余りを $r$ とすると， $rx' \equiv 1\ ({\rm mod}\ a)$ となります．これを繰り返すことで $x$ を求めることができます．具体的には， $n = 529, \, a = 100$ とすると

$100x \equiv 1\ ({\rm mod}\ 529)$ ある $x'$ が存在して $100x + 529x' = 1$ よって $529x' \equiv 1\ ({\rm mod}\ 100)$
$29x' \equiv 1\ ({\rm mod}\ 100)$ ある $x''$ が存在して $29x' + 100x'' = 1$ よって $100x'' \equiv 1\ ({\rm mod}\ 29)$
$13x'' \equiv 1\ ({\rm mod}\ 29)$
$13x'' + 29x''' = 1$
$29x''' \equiv 1\ ({\rm mod}\ 13)$
$3x''' \equiv 1\ ({\rm mod}\ 13)$
$3x''' + 13x'''' = 1$
$13x'''' \equiv 1\ ({\rm mod}\ 3)$
$x'''' \equiv 1\ ({\rm mod}\ 3)$
これより，最後の $x''''$ の値を $1$ とすれば，逆に辿って $x$ の値を求めることができます．逆に辿るやり方は，
$\begin{align*}3x''' &= 1-13x'''' \\ &= 1 - 3\cdot 4x'''' - x'''' \\ &= - 3\cdot 4x''''\end{align*}$ より
$x''' = -4 x'''' = -4$
$\begin{align*}13x'' &= 1 - 29x''' \\ &= 1 - 13\cdot 2x''' - 3x''' \\ &= 1 - 13\cdot 2x''' - (1 - 13 x'''') \\ &= -13\cdot 2x''' + 13 x''''\end{align*}$ より
$x'' = -2x''' + x'''' = 9$
$\begin{align*}29x' &= 1 - 100x''\\ &= 1 - 29\cdot3x''-13x''\\ &= 1 - 29\cdot3x''-(1-29x''')\\ &= -29\cdot3x'' + 29 x'''\end{align*}$ より
$x' = -3x'' + x''' = -31$
$\begin{align*}100x &= 1 - 529x' \\ &= 1 - 100\cdot5x' - 29x' \\ &= 1 - 100\cdot 5x' - (1 - 100 x'') \\ &= - 100 \cdot 5x' + 100 x''\end{align*}$ より
$x = -5x' + x'' = 164$ という具合です．

一般化

上の例より， $a_0 = n$ ， $a_1 = a$ とし，

$\begin{align*} a_0 \div a_1 &= b_0 \cdots a_2 \\ a_1 \div a_2 &= b_1 \cdots a_3 \\ & \vdots \\ a_m \div a_{m + 1} &= b_m \cdots 1 \end{align*}$ とすると， $\begin{align*} x_{m + 1} &= 1 \\ x_m &= - b_m x_{m + 1} \\ x_{m - 1} &= - b_{m - 1} x_m + x_{m + 1} \\ x_{m - 2} &= - b_{m - 2} x_{m - 1} + x_m \\ & \vdots \\ x_0 &= -b_0 x_1 + x_2 \end{align*}$ という手続きで $x = x_0$ の値が求められることが分かりました．

行列

上の手続きを行列を用いて表すと

$\begin{pmatrix} x_k \\ x_{k + 1} \end{pmatrix} = \begin{pmatrix} -b_k & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} x_{k + 1} \\ x_{k + 2} \end{pmatrix}$ (ただし $k$ は $0$ 以上 $m$ 以下の整数，また $\begin{pmatrix}x_{m + 1} \\ x_{m + 2}\end{pmatrix} = \begin{pmatrix}1 \\ 0 \end{pmatrix}$ とする)となります．つまり $\begin{pmatrix} x_0 \\ x_1 \end{pmatrix} = \begin{pmatrix} -b_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} -b_1 & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} -b_m & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix}$ なので，行列計算によって $x_0$ を求めることができます．

コード

この行列計算をそのままコードで書くと次のようになります．

int inverse(int mod, int val){
	int x[2] = {mod, val};
	int a[2][2][2] = {{{1, 0}, {0, 1}}};
	int i;
	for(i = 0; x[!i]; i ^= 1){
		a[!i][0][0] = a[i][0][1] - x[i] / x[!i] * a[i][0][0];
		a[!i][0][1] = a[i][0][0];
		a[!i][1][0] = a[i][1][1] - x[i] / x[!i] * a[i][1][0];
		a[!i][1][1] = a[i][1][0];

		x[i] = x[i] % x[!i];
	}
	return a[!i][0][0];
}

実際には行列の第 1 行と第 2 行の計算は独立しているので次のように書けます．

int inverse(int mod, int val){
	int x[2] = {mod, val};
	int a[2][2] = {{1, 0}};
	int i;
	for(i = 0; x[!i]; i ^= 1){
		a[!i][0] = a[i][1] - x[i] / x[!i] * a[i][0];
		a[!i][1] = a[i][0];

		x[i] = x[i] % x[!i];
	}
	return a[!i][0];
}

さらに第 1 列と第 2 列を配列内で毎回ひっくり返すようにすると次のようになります．

int inverse(int mod, int val){
	int x[2] = {mod, val};
	int a[2] = {1, 0};
	int i;
	for(i = 0; x[!i]; i ^= 1){
		a[!i] -= x[i] / x[!i] * a[i];
		x[i] = x[i] % x[!i];
	}
	return a[!i];
}

ただしこれだと答えが正になったり負になったりするので，常に $0 \leq x < n$ の範囲で値を得たいときは次のようにします．

int inverse(int mod, int val){
	int x[2] = {mod, val};
	int a[2] = {1, 0};
	int i;
	for(i = 0; x[!i]; i ^= 1){
		a[!i] -= x[i] / x[!i] * a[i];
		x[i] = x[i] % x[!i];
	}
	if(!i) a[!i] += mod;
	return a[!i];
}

この記事があなたの役に立てば幸いです．

2019-09-09

AtCoder に登録したら解くべき精選過去問 10 問を C 言語で解いてみた ① (第1問から第4問まで)

プログラミング

「C」という名前の，何でもできてしまうすごいプログラミング言語があるらしいので，この言語を使って drken さんの「AtCoder に登録したら解くべき精選過去問 10 問」を解いてみました．qiita.com↑この方のブログは AtCoder でプログラミングを勉強しよう！と思っている人なら必ず読むべき良サイト．自分もよくお世話になっております．

まず自分の使っているテンプレートから紹介します．出入力部分などは本質でないので C 言語の標準ライブラリに全て任せて，あとは自力で書くことにしています．

#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
#include <string.h>
#include <stdio.h>

const char main_[] = { /* ここに解を求めるプログラムの中身を書く */ };

int main(void){
	int fd = open("/dev/zero", O_RDONLY);
	/* 返り値 */ (*solve)(/* 引数 */) = mmap(NULL, sizeof main_, PROT_WRITE | PROT_EXEC, MAP_PRIVATE, fd, 0);
	memcpy(solve, main_, sizeof main_);

	/* 入力を scanf などで受け取って solve 関数に渡し，返り値を出力する */

	close(fd);
	munmap(solve, sizeof main_);
	return 0;
}

例えば，2 つの整数を読み込んでその和を出力するプログラムであれば，const char main_[] にその旨を書いて，solve の型を int (*solve)(int, int) とし，solve(a, b) のように呼び出します．

1. A - Product

さて早速1問目から解いていきます．
1問目は，2つの正整数の積が偶数か奇数か判定する問題です．solve 関数は，2 つの int 型変数 a， b を受け取って，その積が偶数であれば 0 ，奇数であれば 1 を返せばよさそうです．よって solve の型は int (*solve)(int, int) となります．
さて，肝心の const char main_[] の中身ですが，問題文をそのまま解釈すれば，「 a と b の積を計算し，その最下位ビットを求める」と書けます．残念ながら私は機械語が読み書きできないので，一旦アセンブリ言語 *1で書いてみます(コンテスト時間は限られているので，いずれは機械語を直接書けるようになりたいです)．返り値は rax レジスタに置いておけばよいので，先に第1引数(rdi レジスタにある)を rax レジスタに動かしてから第2引数(rsi レジスタにある)をそこに乗算して，1との AND を取ります．

	.global solve
solve:
	mov %rdi, %rax
	imul %rsi, %rax
	and $1, %rax
	ret

これを適当なファイルに保存します．そのまま C のコードとリンクすれば実行ファイルができて，正しく動くか確認できます*2．このアセンブリコードを適当なコマンドを用いて機械語に変換すると，

0:	48 89 f8
3:	48 0f af c6
7:	48 83 e0 01
b:	c3

となり，これで AC コードを書くことができます(https://atcoder.jp/contests/abc086/submissions/7369756)．しかし，よく考えてみると知りたいのは積の偶奇であって，積の値そのものではないことに気付きます．そうすると，実は imul コマンドで乗算を行わなくても，AND 演算を行うだけで事足りることが分かります．これを用いてプログラムを書き換えると，次のようになります．

	.global solve
solve:
	mov %rdi, %rax
	and %rsi, %rax
	and $1, %rax
	ret

これを先ほどと同じように機械語に変換すると

0:	48 89 f8
3:	48 21 f0
6:	48 83 e0 01
a:	c3

となり，1バイト削れました．やったね．最終的な AC コードはこのようになります．https://atcoder.jp/contests/abc086/submissions/7369764

#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
#include <string.h>
#include <stdio.h>

const char main_[] = {
	0x48, 0x89, 0xf8,
	0x48, 0x21, 0xf0,
	0x48, 0x83, 0xe0, 0x01,
	0xc3
};

int main(void){
	int fd = open("/dev/zero", O_RDONLY);
	int (*solve)(int, int) = mmap(NULL, sizeof main_, PROT_WRITE | PROT_EXEC, MAP_PRIVATE, fd, 0);
	memcpy(solve, main_, sizeof main_);

	int a, b;
	scanf("%d%d", &a, &b);
	puts(solve(a, b) ? "Odd" : "Even");

	close(fd);
	munmap(solve, sizeof main_);
	return 0;
}

次の問題からは，コードとして載せるのは const char main_[] の中身の部分だけにし，include や main 関数など他の部分は省くことにします．

2. A - Placing Marbles

2 問目は，長さ 3 の文字列を読み込んで，その中に含まれる '1'(=0x31) の個数を数える問題です．solve 関数は，文字列を受け取って整数を返せばよいので，int (*solve)(char []) となります．
さて，ここでいくつか大事な知識が出てきます．ジャンプを利用した条件分岐とループ，そしてレジスタ間接参照によるメモリアクセスです．
rax レジスタを最初 0 にしておき，文字列を 1 文字ずつ読んでいって '1'(=0x31) が現れるたびに rax をインクリメントすることにします．ちなみに，任意の X について X xor X は 0 なので，

	xor %rax, %rax

とすれば rax レジスタを 0 にすることができます．これは機械語に直すと 48 31 c0 となり， mov 命令を使ったときの 48 c7 c0 00 00 00 00 に比べて 4 バイト小さく，実行も高速です．
文字列の先頭アドレスは第1引数なので rdi レジスタに入っています． 3 文字読んだら終わればよいと分かっているので， rdi から 3 バイト進んだ箇所のアドレスを rcx に置いておきます．

	mov %rdi, %rcx
	add $3, %rcx

そしてループ内で毎回 rdi を 1 増やしてゆき， rdi と rcx が等しくなったところでループを抜けます．

loop:
	# ここに処理を書く
	inc %rdi
	cmp %rdi, %rcx
	jnz loop

jnz 命令は，事前に cmp 命令で比較しておいた 2 つの値が等しくなかったときにのみジャンプをします．よって rdi レジスタと rcx レジスタの値が等しくなるまで，loop ラベルに戻って処理が繰り返されます．こうしてループが実現できました．
また，各ループ内で調べようとしている文字のメモリ上におけるアドレスは，rdi レジスタに書かれているので，間接参照によってその値を rdx にロードします．1 バイト分だけ移したいので，movzb コマンドを使います．

	movzb (%rdi), %rdx

そしてこれが '1'(=0x31) に等しいかどうかを cmp で調べ，等しかったときにのみ rax レジスタをインクリメントします．

	cmp $0x31, %rdx
	jnz neq
	inc %rax
neq:

以上をまとめると，関数全体では次のようになります．

	xor %rax, %rax
	mov %rdi, %rcx
	add $3, %rcx
loop:
	movzb (%rdi), %rdx
	cmp $0x31, %rdx
	jnz neq
	inc %rax
neq:
	inc %rdi
	cmp %rdi, %rcx
	jnz loop
	ret

あとは機械語に変換して AC ．https://atcoder.jp/contests/abc081/submissions/7428628

const char main_[] = {
	0x48, 0x31, 0xc0,
	0x48, 0x89, 0xf9,
	0x48, 0x83, 0xc1, 0x03,
	0x48, 0x0f, 0xb6, 0x17,
	0x48, 0x83, 0xfa, 0x31,
	0x75, 0x03,
	0x48, 0xff, 0xc0,
	0x48, 0xff, 0xc7,
	0x48, 0x39, 0xf9,
	0x75, 0xeb,
	0xc3
};

3. B - Shift only

n 個の整数 a_i について， a_i を 2 で何回割れるか( ord₂a_i と表記するそうですね)を求めて，その最小値を答える問題です． solve は n と a を受け取るため， int (*solve)(int, int[]) となります．
ループが必要ですが，その回数は rdi レジスタに入っている第1引数 n です．そこで， rdi の値を 1 ずつ減算していって，それが 0 になったらループを抜けることにします．すると，このカウンタとしての rdi の値が，配列へのアクセスにそのまま利用できそうなことに気付きます． C 言語で書くと

do{
	--n;
	// a[n] を見る
}while(n != 0);

ということです．アセンブリ言語に直すと

loop:
	dec %rdi
	# ここにループ内の処理を書く
	cmp $0, %rdi
	jnz loop

さて，「a[n]」というのは「*(a + n)」の糖衣構文ですが，ここにおける「a + n」の意味は，「a と sizeof(int) * n の和」という意味であるため，アセンブリ的には「rsi に rdi * 4 を足した値」が欲しいということになります．実は x86_64 だとこれは「(%rsi, %rdi, 4)」と書くことができるようになっています．これを参照して rcx にロードします．

	mov (%rsi, %rdi, 4), %rcx

あとは， rcx の右端に何個 0 が並んでいるか数えれば良いです．これは有名テクですが， n & (-n) で一番下の 1 だけ残すことができます．アセンブリ言語で書けば

	xor %rdx, %rdx
	sub %rcx, %rdx
	and %rdx, %rcx

です．これによって，例えば rcx の値が 20 なら 4 に， 48 なら 16 になります． 2 の冪乗で表される最大の約数が残るわけです．うーん，こうして得られた値の， 2 を底とする対数をとれば， 2 で割れる回数が計算できるんですが，毎回 log2 を計算してからその最小値を求めるのではなくて，この「2 の冪乗で表される最大の約数」自体の最小値を求めてから最後に log2 をとることにしましょう．
rax レジスタにあらかじめ大きな値を入れておき，それより小さいものが現れたら更新します．十分大きな値として 2^30 = 0x40000000 を使います．

	mov $0x40000000, %rax

「小さいものが現れたら更新する」は，「小さくなかったら更新しない」と言い換えて

	cmp %rax, %rcx
	jae ae
	mov %rcx, %rax
ae:

とすればよいです．
さて，こうしてループが終了したら， rax に 2^ans という値が入っているので， 2 を底とする対数をとって答え ans を得ます．ここでは， rax をデクリメントして 2^ans - 1 にし， popcnt 命令で立っているビットの数を数えます．

	dec %rax
	popcnt %rax, %rax

以上を全てまとめて

	mov $0x40000000, %rax
loop:
	dec %rdi
	mov (%rsi, %rdi, 4), %rcx
	xor %rdx, %rdx
	sub %rcx, %rdx
	and %rdx, %rcx
	cmp %rax, %rcx
	jae ae
	mov %rcx, %rax
ae:
	cmp $0, %rdi
	jnz loop
	dec %rax
	popcnt %rax, %rax
	ret

https://atcoder.jp/contests/abc081/submissions/7412959

const char main_[] = {
	0x48, 0xc7, 0xc0, 0x00, 0x00, 0x00, 0x40,
	0x48, 0xff, 0xcf,
	0x48, 0x8b, 0x0c, 0xbe,
	0x48, 0x31, 0xd2,
	0x48, 0x29, 0xca,
	0x48, 0x21, 0xd1,
	0x48, 0x39, 0xc1,
	0x73, 0x03,
	0x48, 0x89, 0xc8,
	0x48, 0x83, 0xff, 0x00,
	0x75, 0xe2,
	0x48, 0xff, 0xc8,
	0xf3, 0x48, 0x0f, 0xb8, 0xc0,
	0xc3
};

4. B - Coins

初めて割り算が登場します． div 命令というのを使います．この命令は， rdx レジスタと rax レジスタを合わせた 64 bit の領域に入っている値を，別の 32 bit レジスタの値で割ります．
solve 関数は，4 つの整数 a, b, c, x を受け取って整数値の答えを返すので int (*solve)(int, int, int, int) です．まず第 4 引数 x ( rcx レジスタにある) を 500 で割ってみましょう．割る数 500 は，自由に使える r10 レジスタに入れることにします．

	xor %rdx, %rdx
	mov %rcx, %rax
	mov $500, %r10
	div %r10

ちなみに rdx レジスタにはもともと第 3 引数が入っているので，事前に別の場所に避難させておきます． r11 も自由に使えるレジスタです．

	mov %rdx, %r11

こうして rax レジスタに商， rdx レジスタに余りが格納されます．使える 500 円玉の枚数の最大値は，この商と第 1 引数 a のうち小さい方なので， rdi をこれで最小化してしまいます．

	cmp %rdi, %rax
	jae fivehundred
	mov %rax, %rdi
fivehundred:

さて，こうして 500 円玉の枚数の上限が定まったので， 0 枚〜上限枚の各場合について，残りの金額を 100 円玉と 50 円玉で支払うやり方が何通りあるか計算します．答えは rax レジスタに入れたいのですが， rax レジスタは div 命令によって使われてしまうので，代わりのレジスタを探します． r8 と r9 は引数を渡すためのレジスタですが，solve 関数には引数が 4 個しかないため使われていないことに気付きます．ここでは r8 を使うことにし，ループに入る前に 0 にしておきます．

	xor %r8, %r8

またこの後 50 で割る計算がループ毎に現れるので， r10 レジスタもループ前に 50 にしておきます．

	mov $50, %r10

さて，ここからのループですが，「0 以上 n 未満」のような半開区間ではなく「0 以上 n 以下」という閉区間になっているため，ループの形が少し変わります．

loop:
	# ここに処理を書く
	dec %rdi
	cmp $0, %rdi
	jge loop

jge は，符号付き整数としての比較です．こうして 0 と比較することで， rdi が負の数になったときにジャンプします．
500 円玉を何枚使うか決めると，支払う残りの金額が決まります．これは，ループ毎に rcx から 500 を引いてゆくことで得ることにします．

	sub $500, %rcx

ループ内の処理では， 100 円玉 b 枚以下，50 円玉 c 枚以下で残りの金額を支払うやり方の数を考えるのですが，これは「100 円玉と 50 円玉がともに無限枚あったと仮定したときの支払い方」から「使う 100 円玉が b 枚を超える場合」と「使う 50 円玉が c 枚を超える場合」を除くことによって求めます．場合によっては「100 円玉も b 枚を超えるし， 50 円玉も c 枚を超えるような場合」というのもありえますが，これは減算の結果が負になったときに 0 に修正することで対処できます．
まず残りの金額 (rcx) を 50 で割ります．

	xor %rdx, %rdx
	mov %rcx, %rax
	div %r10

このとき，問題文の制約により，余りは 0 になることが保証されます．つまり， div 命令の後， rdx は 0 になります．
そして rax に格納された商が，もし第 3 引数 c より大きければ， 50 円玉だけで残りの金額を全て支払うことはできないということになります．第 3 引数の値は r11 レジスタに避難させられています．使う 50 円玉が c 枚を超える場合の数は計算で求められます．

	cmp %r11, %rax
	jbe fifty
	mov %rax, %rdx
	sub %r11, %rdx
	inc %rdx
	sar $1, %rdx
fifty:

sar 命令は右シフトです．
今 rax に入っている値は rcx を 50 で割った商です．これを右に 1 ビットシフトすることで， rcx を 100 で割った商が得られます．

	sar $1, %rax

そして rsi に入っている第 2 引数 b の値と比較して， b の方が小さかったら b に書き換えます．

	cmp %rsi, %rax
	jbe hundred
	mov %rsi, %rax
hundred:

こうして計算した rdx レジスタと rax レジスタの値から，「100 円玉 b 枚以下，50 円玉 c 枚以下で残りの金額を支払うやり方の数」が得られます．

	inc %rax
	sub %rdx, %rax

これが負だったら 0 通りということなので，正のときのみ r8 に加算します．

	cmp $0, %rax
	jle minus
	add %rax, %r8
minus:

最後に，ループを抜けた後 r8 レジスタの値を rax レジスタに移し，関数の返り値とします．

	mov %r8, %rax

以上を全てまとめると， solve 関数の中身は

	mov %rdx, %r11
	xor %rdx, %rdx
	mov %rcx, %rax
	mov $500, %r10
	div %r10
	cmp %rdi, %rax
	jae fivehundred
	mov %rax, %rdi
fivehundred:
	xor %r8, %r8
	mov $50, %r10
loop:
	xor %rdx, %rdx
	mov %rcx, %rax
	div %r10
	cmp %r11, %rax
	jbe fifty
	mov %rax, %rdx
	sub %r11, %rdx
	inc %rdx
	sar $1, %rdx
fifty:
	sar $1, %rax
	cmp %rsi, %rax
	jbe hundred
	mov %rsi, %rax
hundred:
	inc %rax
	sub %rdx, %rax
	cmp $0, %rax
	jle minus
	add %rax, %r8
minus:
	sub $500, %rcx
	dec %rdi
	cmp $0, %rdi
	jge loop
	mov %r8, %rax
	ret

https://atcoder.jp/contests/abc087/submissions/7424163

const char main_[] = {
	0x49, 0x89, 0xd3, 
	0x48, 0x31, 0xd2, 
	0x48, 0x89, 0xc8, 
	0x49, 0xc7, 0xc2, 0xf4, 0x01, 0x00, 0x00, 
	0x49, 0xf7, 0xf2, 
	0x48, 0x39, 0xf8, 
	0x73, 0x03, 
	0x48, 0x89, 0xc7, 
	0x4d, 0x31, 0xc0, 
	0x49, 0xc7, 0xc2, 0x32, 0x00, 0x00, 0x00, 
	0x48, 0x31, 0xd2, 
	0x48, 0x89, 0xc8, 
	0x49, 0xf7, 0xf2, 
	0x4c, 0x39, 0xd8, 
	0x76, 0x0c, 
	0x48, 0x89, 0xc2, 
	0x4c, 0x29, 0xda, 
	0x48, 0xff, 0xc2, 
	0x48, 0xd1, 0xfa, 
	0x48, 0xd1, 0xf8, 
	0x48, 0x39, 0xf0, 
	0x76, 0x03, 
	0x48, 0x89, 0xf0, 
	0x48, 0xff, 0xc0, 
	0x48, 0x29, 0xd0, 
	0x48, 0x83, 0xf8, 0x00, 
	0x7e, 0x03, 
	0x49, 0x01, 0xc0, 
	0x48, 0x81, 0xe9, 0xf4, 0x01, 0x00, 0x00, 
	0x48, 0xff, 0xcf, 
	0x48, 0x83, 0xff, 0x00, 
	0x7d, 0xbc, 
	0x4c, 0x89, 0xc0, 
	0xc3
};

とりあえずここまで

いかがだったでしょうか．初心者にも分かるような説明を心がけたつもりですが，少し難しくなってしまったかもしれません．ただ， C 言語というものがどういうものか，少しは分かってもらえたかと思います．実は，多くの競プロ er が， C 言語ないしこれをもとに作られた C++ という言語を使っているようです！この記事のような低レベルな内容でも，プログラミングにおいては大事なものなのですね．
drken さんの精選 10 問のうち 6 問が残っているので，もし続きができたらまた投稿したいと思います．では．

*1:AT&T記法を使います．

*2:リンクする場合は，単に int solve(); と宣言しておくだけで solve 関数が使えるようになります．

2019-08-30

プログラミングへの想いを語る

プログラミング

僕にはいくつかの趣味があり，その1つがプログラミングです．主に書く言語はC/C++で，ちょっとしたアルゴリズムの知識を利用して小さなツールなどを作っています．

この記事では，主にプログラマー以外の人向けに，僕がプログラミングのどういう点に楽しさを感じているか話したいと思います．

ものを作る楽しさ
思い通りに動く楽しさ
効率の良いコードが書ける楽しさ
把握できる楽しさ
自分で決められる楽しさ
ネタとしての楽しさ
常に学習の余地がある楽しさ

ものを作る楽しさ

プログラミングは，傍から見ればコンピュータに向かってキーボードを叩いているだけですが，実際に行われているのは「小さな部品を組み立てて大きなものを作り上げる」という行為です．最終的に何かが完成した瞬間の達成感を味わううちに，1日中コンピュータと向き合ってゴリゴリとコードを書く作業も苦しくなくなります(個人差はあります)．そういう意味ではプラモデルとかと似ているのかもしれません．あるいは，小さな歯車を並べて懐中時計を作る作業にたとえることも可能で，この場合，より洗練された精巧な時計を設計する試みは，リファクタリングと呼ばれる作業に対応することになります．
また，使える部品の種類は言語によって違います．例えば昔から使われている C という言語では非常に簡素な部品のみが与えられていますが，もっと新しい言語ではいくつかの部品が組み合わされて使いやすくなったものが多く提供されています．その組み合わせ方の差異が，ウェブ開発に向いている言語，ゲーム開発に向いている言語，スマホアプリ開発に向いている言語などの違いを生んでいます．

思い通りに動く楽しさ

組み立てたプログラムが正しく動くとは限りません．どこか一箇所が間違っているだけで，思いもよらない結果が出力されてしまうこともあります．しかしその分，うまく動いたときの感動は計り知れません．特に僕のやっているアルゴリズム系のプログラミングでは，ある計算をするために一見関係ないような複雑な途中経過を辿ることがあります．ナップザックに荷物を詰め込む最善のやり方を知るために突然大きなタテヨコの表を作ってみたり，文章中のいくつかの単語を置換するために突然文章の先頭から何文字か切り取った残りの部分を並べてみたり……．その途中経過が正しいことは当然理論的に証明できるのですが，それでも実際にやってみて上手く行くことが分かるととてもすっきりします．特にそのアイディアが自ら生んだものであれば，自分は天才なんじゃないかという錯覚に陥るくらいの快感を覚えることができます．

効率の良いコードが書ける楽しさ

プログラミングを始めて間もない頃は，無駄な変数や関数が増えたり，適切な書き方が選べなかったりして，書きにくく読みにくいコードを生んでしまうことがよくあります．しかし慣れてくると，言語のパラダイムに沿って利点を活かした設計などができるようになり，コードを書くのに必要な労力が減ってきます．そしてその分難しいプログラムも作れるようになるのです．語学学習などにも通じるところがあるでしょうか．英語を習いたての頃は適切な語彙選択ができないために冗長な表現ばかりしていたけれど，少しずつ洗練された文法や語法を身に付けることで表現の幅が広がった，というような感じです．

把握できる楽しさ

プログラミングができるようになると，様々なソフトウェアが動く仕組みが少しずつ理解できるようになってきます．ゲームプログラミングに親しめばゲームのバグの原因なども予測できることがあります．目の前で何が起こっているのか掌握できる気分はなかなか良いものです．

自分で決められる楽しさ

自分で作るプログラムの仕様は，自分で決めます．この自由さは趣味プログラミングならではの楽しさです．エディタを作るにしろ言語処理系を作るにしろOSを作るにしろ*1，そこには必ず何らかの仕様が生まれます．そのデザインを自ら考え，実際にプログラムとして作ることで，それが自分のアイデンティティとなります．

ネタとしての楽しさ

プログラミングは本来機械を動かすための「手段」ですが，プログラミング自体を「目的」として楽しむ人もいます．一見何をしているのか分からない難解なコードを書いてみたり，ソースコードで絵を書いてみたり．言語仕様を最大限活用してコードの短さを競うコードゴルフという競技もその1つです．当然そのような遊びにはしびれるほど高度な技術が要求され，他人のそれを見るだけでも大いに楽しめます．あなたの知らない超絶技巧プログラミングの世界というタイトルの本が出版されるくらいです．

常に学習の余地がある楽しさ

最後に，学ぶことの楽しさについて話します．未知の領域に足を踏み入れるのはとてもわくわくすることです．もちろんプログラミングを始める瞬間にも感じることはできるのですが，実際にはプログラミングと呼ばれる領域はとても多岐に渡っており，その中で新しい分野に手を出すたびに新鮮な気分を味わうことができます．僕も，やりたいなぁと思っているけれどまだ本格的に始められずにいるものを挙げろと言われたら，言語だと Rust とか Haskell とか D とか Coq とか Prolog とか，分野だと Web 系とか機械学習とか，まぁキリがありません．このように目の前にわくわくする世界が広がっているのも，プログラミングの楽しさの1つだと思います．

僕が感じるプログラミングの楽しい点は以上の7つにまとめられます．おそらく今後もプログラミングは趣味としてずっと続けると思います．

これからプログラミングを始めようと思っている人にその楽しさが少しでも伝われば幸いです．

*1:この記事によると，これらはプログラマーの3大欲求なのだそうです．

2019-08-25

ncurses への誘い

プログラミング

この記事は C / C++ プログラマーを対象として書かれています．ncurses というライブラリの紹介なのですが，調べてみると python，Ruby でも使えるようです(ここら辺の言語， C 用のライブラリなら何でも持ってますね……)．

CUI vs GUI

C プログラムには， CUI (キャラクタユーザインターフェース) のものと，GUI (グラフィカルユーザインターフェース) のものがあります．ユーザにとっては GUI の方が圧倒的に直感的で分かりやすいため，何か開発する際に GUI の方が良いなぁと思うこともあるでしょう．しかし，プログラミング学習において GUI より先にまず CUI を学ぶことが多いことからも分かる通り，プログラマの目線から見れば CUI の方が簡単です．とくに入出力に関しては， CUI なら printf，scanf などの関数だけで事が大体済みます．一方 GUI だと，何かを表示したり，キーボード操作を受け付けたりするためには，少々長いコードが必要となってしまいます(どれくらい長くなるかはライブラリにもよりますが……)．そのため，GUI であることが望ましいようなプログラムを作る際にも，面倒だからという理由で CUI を選択してしまう人がいることでしょう．

……ちょっと待って下さい．もう 1 つの選択肢を忘れていませんか．
CUI，GUI と来たら，そうです， TUI (テキストユーザインターフェース) が残っています．

第3の選択肢，TUI

TUI は，CUI と同じくコンソール上で動きます．CUI では基本的に左上から順番に文字を出力することしかできませんが，TUI ではターミナル画面の好きな位置に文字を表示したり，ユーザの入力をリアルタイムで受け取ったりすることができます．コンソールを使って実質 GUI と同じことができるのです．しかも，ncurses というライブラリを使えば， CUI と同じくらい簡潔なコードで済むのです．

ざっと使い方の説明

とりあえず ncurses で画面の左上に Hello, world! と表示してみましょう． ncurses を使うには，ncurses.h ヘッダをインクルードし，コンパイル後に ncurses ライブラリとリンクします．

/* main.c */
#include <ncurses.h>
int main(){
    initscr();                  // 最初に書く
    addstr("Hello, world!");    // カーソルの位置に"Hello, world!"と表示する
    getch();                    // 何かのキーが押されるまで待つ
    endwin();                   // 最後に書く
    return 0;
}

$ gcc main.c -lncurses

実行すると，"Hello, world!"と表示されるはずです．(環境によっては，押されたキーの文字がプログラム終了後に残るかもしれません．)
カーソルは最初，画面左上(座標 (0, 0))の位置にあります．addstr 関数によって，最初の'H'が(0, 0)の位置に来てその右に残りの"ello, world!"が続くように，文字列"Hello, world!"が表示されます．このときカーソルは文字数分だけ右に動いています．
カーソルを特定の位置に動かすには，move 関数を使います．

move(5, 10);
addstr("Hello, world");

今度は'H'が上から5行目，左から10文字目(ただし上端を0行目，左端を0文字目とする)の位置に表示されます．
printf のようなフォーマット出力は printw 関数でできます．

printw("%d is prime.", 57);

getch 関数は，キーボード入力を1文字ずつ受けとります．

while(getch() != 'a');

'a' が押されるとループを抜けます．その間押されたキーの文字が画面に表示され続けます．これは noecho 関数を使うと表示しないようになります．

noecho();
while(getch() != 'a');

押されたキーは表示されず，カーソルも動きません．echo 関数でもとに戻ります．
また上下左右キーや特殊キーを受けとるためには keypad 関数を事前に呼び出しておきます．

keypad(stdscr, TRUE);
while(getch() != KEY_DOWN);

KEY_DOWN などの定数一覧は man getch で見られます．また今使った stdscr の意味について知りたい人は man ncurses から読んで下さい．
curs_set 関数を用いるとカーソルの表示非表示を切り替えられます．

curs_set(0); // invisible(表示されない)
curs_set(1); // normal(表示される)
curs_set(2); // very visible(環境によってはカーソルの形状が変わる)

getch(); はそのままだとキー入力を待っている間プログラム全体が止まってしまいます．nodelay 関数を使うと待たないようになります．

nodelay(stdscr, TRUE);
for(int i = 0;; ++i){
    move(0, 0);
    printw("%d", i);
    move(1, 0);
    if(getch() == 10) break;
}

また CUI のような入力受付けも可能です．

char buf[256];
getstr(buf);

実質 GUI

上で紹介したことを組み合わせれば，GUI っぽいことがかなりできるようになります．ゲームも作れます．特に学業・仕事の合間にプログラミングをする趣味グラマーは，労力をかけずにすむ TUI を第3の選択肢として頭に入れておくのも悪くないと思います．

この記事があなたの役に立てば幸いです．