2015/12/01(火)gitコマンドメモ

自分用メモ。

初期設定

$ git config --global user.name "nabe"
$ git config --global user.email "nabe-g@example.com"
$ git config --global core.editor vi
$ git config --global color.ui true 
$ git config --global core.pager 'less'
$ git config --list
$ git init
$ git clone http://------/

基本コマンド

$ git status
$ git log
$ git log --oneline
$ git log --pretty=oneline
$ git diff
$ git diff --cached
$ git rm
$ git mv

コミット

$ git commit
$ git commit --amend		直前のコミットをやり直し(上書き)
$ git reset  --soft HEAD^	ファイルをそのままでコミットの取り消し

stash

$ git stash
$ git stash pop

ブランチとタグ

$ git branch new-branch
$ git checkout branch-name
$ git merge develop
$ git tag -a v3.00-beta2 -m "Version 3.0x"
$ git push
$ git push --tags
$ git tag -d DeleteTAG
$ git push origin :DeleteTAG

リモート操作

$ git remote -v
$ git remote add [name] [url]
$ git remote add 
$ git remote rename pb paul

その他

手元の変更取り消し

$ git checkout -- .

ログ

$ git log --pretty=oneline

2012/11/26(月)DICOM通信プロトコルのまとめ

2010/05/14(金)3の倍数を除算せずに判定する

テーブルが間違ってたバグを修正しました(汗) 感謝>ingktさん


3の倍数を除算を使わずに判定したいという話を聞いたので、ちょっと考えてみました。

方法

2進数表示を考えて2桁ごとに区切ります。それぞれ0~3までの数字と捉えて、足し算します。足し算の結果が3で割り切れれば3の倍数です。

372 → 101110100b
 → 1b + 01b + 11b + 01b + 00b
 = 1 + 1 + 3 + 1 = 6

(参考にしたサイト) No.055 「111」は「3」の倍数(原理は一緒)

実装

intが32bitの場合(0-0xfffffffeまでテスト済)。

#define MUL3TABLE 0x49249248	// bit31 to 0
int mul3test(unsigned int x) {
	int i;
	int c=0;
	for(i=0; i<16; i++,x>>=2) {
		c += (x & 3);
	}
	if (c>30) c-=27;
	return (MUL3TABLE >> c) & 1;	// if multiple 3 return 1
}

16bitの場合。

#define MUL3TABLE 0x9248;	// bit15 to 0
int mul3test(unsigned int x) {
	int i;
	int c=0;
	for(i=0; i<16; i++,x>>=2) {
		c += (x & 3);
	}
	if (c>15) c-=12;
	return (MUL3TABLE >> c) & 1;	// if multiple 3 return 1
}
}

判定に0を含める場合

「3の倍数」ではなくて3で割り切れるかどうかを判定する場合は、

#define MUL3TABLE 0x49249248	// bit31 to 0
#define MUL3TABLE 0x9248;	// bit15 to 0

をそれぞれ、

#define MUL3TABLE 0x49249249	// bit31 to 0
#define MUL3TABLE 0x9249;	// bit15 to 0

と修正してください。

改良 2010/05/14

ts1さんのコメント通り改良したもの。

int mul3test2(unsigned int x) {
	x = ((x >> 2) & 0x33333333) + (x & 0x33333333);	// 0 to 6
	x = ((x >> 4) & 0x0f0f0f0f) + (x & 0x0f0f0f0f);	// 0 to 12
	x = ((x >> 8) & 0x00ff00ff) + (x & 0x00ff00ff);	// 0 to 24
	x = ((x >> 16) + x) & 0x0000003f;
	if (x>30) x-=27;
	return (MUL3TABLE >> x) & 1;	// if multiple 3 return 1
}

ingktさんの改良案。2bitずつ加算しなくてもいいのは気付かなかった(汗)

int mul3test3(unsigned int x) {
	x = ((x >> 4) & 0x0f0f0f0f) + (x & 0x0f0f0f0f);
	x = (x >> 8) + x;
	x = (x >> 16) + x;
	x = ((x >> 4) & 7) + (x & 0xf);
	return (MUL3TABLE >> x) & 1;
}

実行速度0~0xfffffffeまで。gcc -O3でコンパイル。

mu3test()
real    2m10.451s
user    2m10.400s
mu3test2()
real    1m28.912s
user    1m28.900s
mu3test3()
real    15.719s
user    15.700s

非力なマイコンだとしても、ingktさんの実装が一番スマートですね。

2008/03/28(金)Subversionの設定メモ

リポジトリ管理にもっぱら Subversion を使っているのですが、管理方法などを細かいことを忘れてしまうので、備忘録メモです。

Apacheの設定

svn のリポジトリを http で管理する場合、Apacheにモジュールを組み込む必要があります。

LoadModule dav_module         libexec/mod_dav.so
LoadModule dav_fs_module      libexec/mod_dav_fs.so
LoadModule dav_svn_module     libexec/mod_dav_svn.so
LoadModule authz_svn_module   libexec/mod_authz_svn.so

svnを動作させたいディレクトリを指定し、次のように記述します。

<Location /repo-dir>
    DAV     svn
    SVNPath /var/www/svndata/repo-dir
</Location>

このとき、/repo-dir/ がsvnリポジトリとして扱われ、/repo-dir/ 以下の管理情報はすべて /var/www/svndata/repo-dir に置かれます。

また /repo-dir/ という実ディレクトリ(www内)が存在すると問題が起こります。

SVNPathで指定したディレクトリに実際にリポジトリを作成します。このリポジトリデータは www 権限で読み書きできる必要があります。

# svnadmin create /var/www/svndata/repo-dir
# chown -R www:www /var/www/svndata/repo-dir

リポジトリのディレクトリ分け

これまでの設定により http://svn.duummy.dom/repo-dir は1つのSubversionリポジトリとして機能します。Subversionによって /repo-dir の仮想的なファイルシステムがすべて作られるようになります。

ずっと勘違いをしていたのですが、あるプログラムを開発するとき、/repo-dir 自体を1つのプログラムソース全体として管理していました。

  • repo-dir/
    • Makefile
    • main.c

しかし、この状況ではブランチといったプロジェクトの分岐が不可能になってしまいます。

これを次のような形で行えば、この中には自由にディレクトリやファイルを作ることができ、コピー等も自在に行えます。

  • repo-dir/
    • prog-current/
      • Makefile
      • main.c
    • prog-stable/
      • Makefile
      • main.c

リポジトリというのは単なる管理単位で、その中のいかなるサブディレクトリでも、そのサブディレクトリ単位でチェックアウトやインポートなどが実効できます。実際、複数のプロジェクトからなる大きな1つのプロジェクトは、このようなディレクトリ分けをうまく使うことで管理されます。

補足

これはリポジトリの概念を解説しただけで、コメントで頂いたとおり下のようにするのが一般的です(必ずしも従う必要はありませんが)。詳しくは参考資料をご覧ください。

  • trunk ……現在開発中のもの
  • branches ……ブランチを納めるディレクトリ
    • branch1
    • branch2
  • tags ……タグをつけてリリース版などをおく場所*1
    • Version 1.xxxx

*1 : 実体はブランチと同じ、ある時点でのディレクトリのコピー

リポジトリの登録とコピー

登録は(通常)手元にあるファイルを import によりリポジトリに登録します。

$ svn import local-dir http://svn.duummy.dom/repo-dir/prog-current

今登録したリポジトリをマスターとして使用しますので、(面倒でも)一度リポジトリから手元のディレクトリにコピーする必要があります。

$ svn checkout http://svn.duummy.dom/repo-dir/prog-current

リポジトリを分岐(ブランチ)させたいときは、同一リポジトリ内でコピーします。

$ svn copy http://svn.duummy.dom/repo-dir/prog-current
           http://svn.duummy.dom/repo-dir/prog-stable

クライアント側の操作

一度チェックアウトしてしまえば、あとは簡単です。チェックアウトしたディレクトリに移動し(prog-current/等)て操作します。

最新のソースに追従
$ svn update
変更箇所をリポジトリに反映
$ svn ci -m "チェックインのメモ"

特定ファイルの変更を破棄
$ svn revert file.c
ファイル/ディレクトリを削除
$ svn delete file.c
ファイル/ディレクトリを追加
$ svn add file.c

差分表示
$ svn diff
リビジョン指定して差分表示(13とローカルのもの)
$ svn diff -r13
リビジョン指定して差分表示(11と12)
$ svn diff -r11:12

作業コピーのブランチ切り替え
$ svn switch http://svn.duummy.dom/repo-dir/prog-stable

参考資料

2007/08/24(金)実数FFT/IFFT関数

長年理解するのを拒否していたFFTとここ何週間か格闘しています。楽々とアルゴリズムを導出・実装できる人はいいのでしょうが、FFTのようなアルゴリズムをきちんと理解して実装するのは思うほど容易ではありません。既に導出されたアルゴリズム(や雛形サンプル)を何も考えず実装すれば簡単ですが、そういうことが生理的にできない場合、改良とかを考え出して簡単には実装できなくなるんですよね。

前置きはともかく、今日やっと実数専用のFFT/IFFTが作成できました。実数専用にすることで理論的には通常のFFTの半分の時間で処理できます。

見ての通り、実数FFTの対称性を利用したものすごく面倒くさく複雑な作りになっているんですが、有名なFFTの概略と設計法のソースと速度比較をしたら倍近く遅い……。64K点、double型、VIA C3 500MHzで動作させて、自作が100ms、リンク先のソースが60ms。

いかに細かい最適化をしても実装アルゴリズムの時点で差があると非常に大きいですね……。あとでアルゴリズムの差を検証予定。

ソース解読メモ

大浦氏のFFTソース(fft4g.c)解読メモ。つまりリバースエンジニアリングです。

サブルーチンの機能

cdft()複素数FFT/IFFT。データサイズは N/2
rdft()実数FFT/IFFT。内部的に複素FFTを呼び出し
makewt()sin/cosテーブルを w[] に格納(ただし格納位置はビット反転)
makect()cosテーブルを w[nw~] に格納(ただし格納位置はビット反転)
bitrv2()ビット反転を実行
bitrv2conj()ビット反転しつつ、読込データの複素共役を取る
cftfsub()複素IFFT(f=forward, 回転子が正であるという意味)
cftbsub()複素FFT(b=backward, 回転子が負であるという意味)
rftfsub()実数IFFT
rftbsub()実数FFT

IFFTをFFTで代用する方法

C(k) = \sum_{n=0}^{N-1} c(n) W^{kn}  c(n) = \sum_{k=0}^{N-1} C(k) W^{-kn}

なんだけども、複素共役を考えると

\overline{c(n)} = \sum_{k=0}^{N-1} \overline{C(k) W^{-kn}} =  \sum_{k=0}^{N-1} \overline{C(k)} W^{kn}

つまり前処理と後処理としてデータの複素共役を取ってあげれば、同じFFTルーチンを使い回すことができる(効率を考えて、初段部分と終段部分だけ個別特別に実装すれば、中段部分は使い回せる)。

その他メモ

  • 一般的なFFT(DFT)と比べ虚数部の符号が逆になっている*1

周波数間引きFFTである

やっとこのプログラムの要が理解出来ました。

先にデータをスクランブルして(並べ替えて)いるため「時間間引きFFT」に見えますが、実際には周波数間引きFFTです。sin/cosテーブルもわざわざスクランブル位置に格納しています。

こうすることでFFT実行時のデータアクセスをシーケンシャルに行え*2、それが功を奏して実行速度が飛躍的に速くなっています。またsin/cosテーブル、偶数番地に cos、奇数番地に sin を格納し、全体としても π/2 しか用意しないことで、データアクセス量を減らしキャッシュが効きやすくなっています。

256点の複素FFTを実行させたときの、cos/sinテーブル参照位置およびデータ参照位置は次のようになります。

 call cftmdl(512, 8)
  k1=1 (0.923880,0.382683), k2=2 (0.707107,0.707107)
    32 36 40 44
    33 37 41 45
    34 38 42 46
    35 39 43 47
  k1=2 (0.980785,0.195090), k2=4 (0.923880,0.382683)
    64 68 72 76
    65 69 73 77
    66 70 74 78
    67 71 75 79
  k1=3 (0.831470,0.555570), k2=6 (0.382683,0.923880)
    96 100 104 108
    97 101 105 109
    98 102 106 110
    99 103 107 111
  k1=4 (0.995185,0.098017), k2=8 (0.980785,0.195090)
    128 132 136 140
    129 133 137 141
    130 134 138 142
    131 135 139 143
  k1=5 (0.881921,0.471397), k2=10 (0.555570,0.831470)
    160 164 168 172
    161 165 169 173
    162 166 170 174
    163 167 171 175
  k1=6 (0.956940,0.290285), k2=12 (0.831470,0.555570)
    192 196 200 204
    193 197 201 205
    194 198 202 206
    195 199 203 207
  k1=7 (0.773010,0.634393), k2=14 (0.195090,0.980785)
    224 228 232 236
    225 229 233 237
    226 230 234 238
    227 231 235 239
 call cftmdl(512, 32)
  k1=1 (0.923880,0.382683), k2=2 (0.707107,0.707107)
    128 144 160 176
    129 145 161 177
(中略)
    142 158 174 190
    143 159 175 191

ほんと、この実装はすごいなぁ。

*1 : ソース中のDFT定義どおりの実装なのでバグの類ではありません。

*2 : キャッシュが非常によく効く