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 共通のものとそうでないものがある。今のところこれらに関するドキュメントがあまり見当たらないため、ソースを頑張って読むしかない模様:

有用そうな変数を挙げておく:

  • 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++競技プログラミングをやる際の最小限のテンプレートを考えてみます。 ここに書いていないことも色々考えてはいますが、とりあえずさわりだけ。

AtCodergcc(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引数の型を別にしておくことで、xi64 型であっても 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 基礎知識 - 目次

TAS さんや攻略のための解析がしたい人向けです。ゲームを自作したい人は NesDevWiki をしっかり読んだ方がいいでしょう。

他機種向けにこういう記事書いてくれる人いないかなー(チラッ

NES 基礎知識 - APU

今回は APU について扱…いたかったのですが、残念ながら知識不足のためまともに解説できる気がしません^^;

ということで、参考になりそうなリンクを張るにとどめておきます。

とりあえず I/O レジスタへの書き込みでどんな音が鳴るのか調べるだけなら上に挙げた Plogue livenes を動かしてみれば大体わかると思います。