gcc で sanitizer を使う
tl;dr
$ gcc -fsanitize=undefined -fno-sanitize-recover=all foo.c $ UBSAN_OPTIONS='verbosity=1:abort_on_error=1:handle_abort=2:disable_coredump=0' ./a.out
詳細
gcc では asan (address sanitizer), ubsan (undefined behavior sanitizer) といった sanitizer が利用できる。 (clang でも利用可能。細かい違いは不明)
CFLAGS/CXXFLAGS, LDFLAGS の両方に -fsanitize=undefined
を付けると ubsan が有効になる。また、-fno-sanitize-recover=all
を付けると sanitizer 側でのエラー回復を無効化できる。単にコアダンプしてほしい場合などに有効。
さらに、sanitizer がエラーを報告する際の挙動を環境変数 ASAN_OPTIONS
, UBSAN_OPTIONS
で制御できる。書式は a=1:b=0:c=1
のように、<変数名>=<値>
をコロンで区切る。
変数は全 sanitizer 共通のものとそうでないものがある。今のところこれらに関するドキュメントがあまり見当たらないため、ソースを頑張って読むしかない模様:
- https://github.com/gcc-mirror/gcc/blob/master/libsanitizer/sanitizer_common/sanitizer_flags.inc
- https://github.com/gcc-mirror/gcc/blob/master/libsanitizer/ubsan/ubsan_flags.inc
有用そうな変数を挙げておく:
abort_on_error
: 1 でエラー落ちする際にabort()
を使う(デフォルトは_exit()
)。disable_coredump
: 0 でコアダンプする。64bit ではデフォルトで 1 になっている (巨大なコアを吐くのを防ぐためらしい)。 プログラム側でシグナルハンドラをいじっている場合、これを 0 にしてもコアダンプ しないことがある。その場合はhandle_abort
を併用する。handle_abort
: 2 でプログラム側での SIGABRT ハンドラ登録を禁止する。強制的に コアダンプさせるのに使える。verbosity
: 0 から 2 まで。1 以上のとき、UBSAN_OPTIONS
に無効なオプション が含まれていたらエラー落ちする際にその旨警告する。print_stacktrace
: UBSAN 用。1 でスタックトレースを吐く。
C++で自動メモ化(競プロ用)
DP問題などを解く際、私はとりあえず再帰関数で書いてみて大丈夫そうならメ モ化再帰に書き換える、という手順を踏むことが多いのですが、この書き換え が若干面倒なので、手間を最小限に抑える方法を考えてみました。
再帰関数はlambdaで書くものとします。lambdaで再帰する方法については C++のラムダで再帰する - koturnの日記 を参照。
再帰関数をメモ化する場合、中身はだいたいこんな感じになるはずです:
int rec(int i, int j) { static bool done[N][M] {}; static int memo[N][M]; if(!done[i][j]) { int res; // res を計算 memo[i][j] = res; done[i][j] = true; } return memo[i][j]; }
このコードを自動生成することを考えます。
まず、done
, memo
は多次元配列なので、std::array
を用いて多次元配
列型を実装します:
template<typename T, size_t N, size_t... NS> struct ArrayType { using type = array<typename ArrayType<T,NS...>::type,N>; }; template<typename T, size_t N> struct ArrayType<T,N> { using type = array<T,N>; }; template<typename T, size_t... NS> using Array = typename ArrayType<T,NS...>::type; template<typename T, size_t N> T& array_at(Array<T,N>& ary, int i) { return ary[i]; } template<typename T, size_t N, size_t... NS, typename... Args> T& array_at(Array<T,N,NS...>& ary, int i, Args... args) { return array_at<T,NS...>(ary[i], args...); } template<typename T, size_t N> const T& array_at(const Array<T,N>& ary, int i) { return ary[i]; } template<typename T, size_t N, size_t... NS, typename... Args> const T& array_at(const Array<T,N,NS...>& ary, int i, Args... args) { return array_at<T,NS...>(ary[i], args...); }
多次元配列型があれば、以下のようなテンプレートを用いて先ほどのコードを 自動生成できるはずです:
template<typename F, size_t... NS> class FixPointMemo { public: explicit FixPointMemo(F&& f) : f_(forward<F>(f)) {} template<typename... Args> decltype(auto) operator()(Args... args) const { using R = decltype(f_(*this,args...)); static Array<bool,NS...> done {}; static Array<R,NS...> memo; if(!array_at<bool,NS...>(done,args...)) { array_at<R,NS...>(memo,args...) = f_(*this,args...); array_at<bool,NS...>(done,args...) = true; } return array_at<R,NS...>(memo,args...); } private: F f_; }; template<size_t... NS, typename F> decltype(auto) FIXMEMO(F&& f) { return FixPointMemo<F,NS...>(forward<F>(f)); }
以上のコードを用意しておけば、このような再帰関数があるとき:
auto f = FIX([&](auto&& self, int i, int j) -> int { /* ... */ });
以下のようにテンプレート引数を追加するだけでメモ化が完了します:
// i,j は [0,1000) の値をとるものとする auto f = FIXMEMO<1000,1000>([&](auto&& self, int i, int j) -> int { /* ... */ });
関数本体は一切変更しなくてよいためかなり楽だと思います。
難点を挙げると:
- メモ化完了フラグを
bool
配列で持っているためメモリ効率が若干悪い (手で書く場合、問題によってはメモ化配列自体に特殊な値を入れることで 代用できる) - 関数の引数は整数型に限定される
といったところですが、高難易度問題でなければあまり気にしなくていいよう に思います(どうせ工夫を要するDP問題はループで書かざるを得なかったりし ますし)。
この方法を用いてナップサック問題を解いたコードを貼っておきます: 提出 #6436875 - Educational DP Contest / DP まとめコンテスト
競技プログラミング用C++テンプレート
C++で競技プログラミングをやる際の最小限のテンプレートを考えてみます。 ここに書いていないことも色々考えてはいますが、とりあえずさわりだけ。
AtCoderのgcc(C++14)を想定しています(近々C++17に更新されそうですが)。
標準ライブラリ
#include <bits/stdc++.h> using namespace std;
私は <bits/stdc++.h>
を使ってしまっています。これは賛否両論あるでし
ょうが、経験上gcc/clang両対応のコードを書くのは案外面倒だったので、そ
れならgcc決め打ちでいいだろうという判断です。
using namespace std;
も通常は問題ないでしょう。
文字列化/文字列結合マクロ
#define CPP_STR(x) CPP_STR_I(x) #define CPP_CAT(x,y) CPP_CAT_I(x,y) #define CPP_STR_I(args...) #args #define CPP_CAT_I(x,y) x ## y
#define CPP_STR(x) #x
とすると CPP_STR(__LINE__)
が __LINE__
に
展開されてしまう罠の対策です(参考:
PRE05-C. 字句の結合や文字列化を行う際のマクロ置換動作をよく理解する
)。また、CPP_STR_I
の引数を可変長にすることで CPP_STR_I(x,y)
->
"x,y"
のような変換を可能にしています(デバッグマクロ作成時などに便利)。
AtCoderなどの場合は Boost.Preprocessor を使ってもいいかも。
assert
#define ASSERT(expr...) assert((expr))
assert(f<int,int>());
みたいなのがコンパイルエラーになる罠の対策です
(プリプロセッサはC++文法を解さないため、素の assert
を使う場合は全体
を括弧でくくる必要がある)。
数値型
using i8 = int8_t; using u8 = uint8_t; using i16 = int16_t; using u16 = uint16_t; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; using f32 = float; using f64 = double; using f80 = __float80;
型名は好み次第ですが、私はRust風に命名しています。
どうせgcc決め打ちなので __float80
も使っています。
オーバーフローでACを逃すのはつまらないので、基本的に整数型は i64
だ
けを使うのがいいと思います。多少メモリは食いますが、今時それでMLEにな
るのは問題の方が悪いと思います。最近のAtCoderはメモリ制限1GBがデフォで
すし。
定数
constexpr i64 INF = 1'010'000'000'000'000'017LL; constexpr i64 MOD = 1'000'000'007LL; constexpr f64 EPS = 1e-12; constexpr f64 PI = 3.14159265358979323846;
INF
が満たすべき条件を考えると
- 1018 より大きい
- 2倍してもオーバーフローしない
あたりが妥当でしょう。一応素数にもしていますが、これはあまり意味がない かも(一応、mod をとること前提のコードを mod をとらない問題に流用するた めに MOD=INF とすることを想定)。
EPS
は割と適当です。問題によっては要調整かも?
FOR/REP マクロ
#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i) #define REP(i, n) FOR(i, 0, n)
前述の通り、ここでも i64
を使います。
end
が複数回評価されるのを防ぐため、変数に代入します。C++のマクロは
非衛生的なので、変数名が衝突しないよう xxxx_end
のようなsuffixを付け
ています(_end
のように先頭をアンダースコアにするのは避けた方が無難だ
と思います。REP(_,N)
としたとき __end
のように
C++の予約済み識別子
に展開されてしまうため)。
ALL マクロ
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))
sort(begin(v),end(v))
を ALL(sort,v)
と略記できます。ここでもまず
衝突しないような変数名を使っています。なお、最後の , ## __VA_ARGS__
は
gcc拡張機能
です。
参考: 競技プログラミングでコーディングの際気を付けていること - うさぎ小屋
コンテナ/配列サイズ
template<typename C> i64 SIZE(const C& c) { return static_cast<i64>(c.size()); } template<typename T, size_t N> i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }
コンテナの size()
メンバ関数などを使うと符号なしの size_t
が混入し
てきて面倒なので、自前実装します。
chmax/chmin
template<typename T, typename U, typename Comp=less<>> bool chmax(T& xmax, const U& x, Comp comp={}) { if(comp(xmax, x)) { xmax = x; return true; } return false; } template<typename T, typename U, typename Comp=less<>> bool chmin(T& xmin, const U& x, Comp comp={}) { if(comp(x, xmin)) { xmin = x; return true; } return false; }
値が更新されたかどうかを返すようにしておくと何かと便利です。
また、第1,2引数の型を別にしておくことで、x
が i64
型であっても
chmax(x,0)
のように書けます(型が同じだと chmax<i64>(x,0)
のように
テンプレート引数が必要)。
一応比較関数も渡せるようにしておきます(使用頻度は低いですが)。
初期化
struct ProconInit { static constexpr int IOS_PREC = 15; static constexpr bool AUTOFLUSH = false; ProconInit() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(IOS_PREC); if(AUTOFLUSH) cout << unitbuf; } } PROCON_INIT;
を行います。グローバルオブジェクトのコンストラクタ内にこれらを書いてお
けば main
実行前に自動で実行されます。
全体
// header {{{ #include <bits/stdc++.h> using namespace std; #define CPP_STR(x) CPP_STR_I(x) #define CPP_CAT(x,y) CPP_CAT_I(x,y) #define CPP_STR_I(args...) #args #define CPP_CAT_I(x,y) x ## y #define ASSERT(expr...) assert((expr)) using i8 = int8_t; using u8 = uint8_t; using i16 = int16_t; using u16 = uint16_t; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; using f32 = float; using f64 = double; using f80 = __float80; // }}} constexpr i64 INF = 1'010'000'000'000'000'017LL; constexpr i64 MOD = 1'000'000'007LL; constexpr f64 EPS = 1e-12; constexpr f64 PI = 3.14159265358979323846; // util {{{ #define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c)) template<typename C> i64 SIZE(const C& c) { return static_cast<i64>(c.size()); } template<typename T, size_t N> i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); } template<typename T, typename U, typename Comp=less<>> bool chmax(T& xmax, const U& x, Comp comp={}) { if(comp(xmax, x)) { xmax = x; return true; } return false; } template<typename T, typename U, typename Comp=less<>> bool chmin(T& xmin, const U& x, Comp comp={}) { if(comp(x, xmin)) { xmin = x; return true; } return false; } // }}} // init {{{ struct ProconInit { static constexpr int IOS_PREC = 15; static constexpr bool AUTOFLUSH = false; ProconInit() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(IOS_PREC); if(AUTOFLUSH) cout << unitbuf; } } PROCON_INIT; // }}} //-------------------------------------------------------------------- void solve() { // cout << ans << "\n"; } signed main() { solve(); return 0; }
Vimmerの人は適宜foldingを入れておくと見やすいと思います。
本来はデバッグ用機能もあった方がいいですが、これを扱うとかなりコード量 が増えてしまうためとりあえず今回はここまでで。
atpagesサービス終了に伴い、旧個人サイトを移転します
今更かよと言われそうですが、atpages が 2/28 でサービス終了するようです。ということで、旧個人サイトを github pages へ移転します。
atpagesに攻略サイトなどを上げてる各位はすぐ引っ越すんだ!間に合わなくなってもしらんぞー!!
解析資料をgithubで公開します
過去にチマチマと作っていた解析資料を github に上げていこうと思います。TASってないゲームも含まれます。
アセンブリをそのまま配布するのはさすがにまずいので、Mesen デバッガ用のラベルファイル(*.mlb
)にします。この形式だと若干不便なところもあります*1が、変数/関数にラベル/コメントを付ける程度なら問題ないので、最低限の要求は満たしてるかなと。
また、ニコニコに上げた動画が一部HTML5で再生できなくなってるようなので、Flashサポートが終了する前に順次 YouTube へ再アップ予定です。
Mesen メモ
- ワークスペースは Debugger/ ディレクトリ内の
*.cdl
,*.Workspace.xml
へ自動保存される。 - コメント内に "0x" とか "$" は書けない模様。"FFh" みたいに書くしかなさげ。
- サブルーチン認識がちょっと甘い。
rts
があると問答無用で終わりとみなしてる? - データを
db
などで表示できないため、データ部にコメントを付けるのが難しい。
*1:データ部にコメントを付けにくかったり、配列変数の表現が難しかったり…
NES 基礎知識 - APU
今回は APU について扱…いたかったのですが、残念ながら知識不足のためまともに解説できる気がしません^^;
ということで、参考になりそうなリンクを張るにとどめておきます。
とりあえず I/O レジスタへの書き込みでどんな音が鳴るのか調べるだけなら上に挙げた Plogue livenes を動かしてみれば大体わかると思います。