2023-12-02

SystemVerilog の struct packed は Verilator にどうマッピングされるか

この記事は TSG Advent Calendar 2023 2 日目のエントリです。昨日の記事は Verilator + GoogleTest で SystemVerilog のモジュールを単体テストする - ﾏｸﾞﾏｸﾞ (起動音) でした。

小ネタですが、検索しても出てこなかったのでメモとして残しておきます。たとえば、以下のような SystemVerilog の struct packed があったとします。

typedef struct packed {
    logic a;
    logic b;
    logic [3:0] c;
} my_struct_t;

SystemVerilog の構造体は定義した順に下位ビットからメンバが並びますが、 C++ の構造体は定義した順に上位ビットからメンバが並びます。

したがって、Verilator で C++ ライブラリに変換するときには、逆順にメンバを並べる必要があります。以下のようなビットフィールドのメンバが定義された構造体を用いれば、 SystemVerilog の struct packed と同じメモリマッピングになります。

struct my_struct_t {
    uint32_t c : 4;
    uint32_t b : 1;
    uint32_t a : 1;
} __attribute__((packed));

あとは適宜 std::memcpy などを使って、SystemVerilog の struct packed と C++ の構造体の間でデータをコピーすれば OK です。

2023-12-01

Verilator + GoogleTest で SystemVerilog のモジュールを単体テストする

この記事は TSG Advent Calendar 2023 初日のエントリです。

Verilog/SystemVerilog で書かれたモジュールをテストする方法として VUnit や cocotb がありますが、普段から C++ を書いている自分としては、RTL のテストを C++ で完結させたいという欲求があり、C++ で RTL をテストする方法を探していました。

そこで、C++ 用のテストフレームワークである GoogleTest を Verilator と組み合わせて使う方法を試してみました。これが意外と簡単にできたので紹介します。需要は謎です。

TL;DR

GitHub - sh-mug/verilog-unittest-sample のサンプルコードを見てくれ！

テスト対象のモジュール

テスト対象のモジュールとして、inst に応じて、a と b を演算して rslt に結果を出力する ALU を用意しました。この ALU が意図した動作をしているかをテストします。

`timescale 1ns / 1ps

module alu (
    input [2:0] inst,
    input [31:0] a,
    input [31:0] b,
    output logic [31:0] rslt
);
  logic [4:0] shamt;
  logic alu_lt;
  logic alu_ltu;
  logic [31:0] alu_add;
  logic [31:0] alu_sll;
  logic [31:0] alu_xor;
  logic [31:0] alu_srl;
  logic [31:0] alu_or;
  logic [31:0] alu_and;

  always_comb begin
    shamt   = b[4:0];

    alu_lt  = $signed(a) < $signed(b);
    alu_ltu = a < b;
    alu_add = a + b;
    alu_sll = a << shamt;
    alu_xor = a ^ b;
    alu_srl = a >> shamt;
    alu_or  = a | b;
    alu_and = a & b;

    case (inst)
      3'b000:  rslt = alu_add;
      3'b001:  rslt = alu_sll;
      3'b010:  rslt = {31'b0, alu_lt};
      3'b011:  rslt = {31'b0, alu_ltu};
      3'b100:  rslt = alu_xor;
      3'b101:  rslt = alu_srl;
      3'b110:  rslt = alu_or;
      3'b111:  rslt = alu_and;
      default: rslt = 0;
    endcase
  end
endmodule : alu

テストコード

テストコードは、GoogleTest の TEST_F マクロを使って書きます。まず、テストフィクスチャ（テストのセットアップやクリーンアップを行うクラス）を作成し、その中で Verilator とモジュールのシミュレーションを初期化します。以下は、テストフィクスチャと1つのテストケースの例です。

テストフィクスチャ `TestAlu`

テストクラス TestAlu では、テストケース間で共通の設定を行います。具体的には、テスト用の ValuForTest インスタンスをセットアップし、テスト後にクリーンアップを行っています。

class TestAlu : public ::testing::Test {
   protected:
    TestAlu()
        : engine(seed_gen()), dist_int(INT_MIN, INT_MAX), dist_5bit(0, 31) {}
    ValuForTest *dut;

    std::random_device seed_gen;
    std::mt19937_64 engine;
    std::uniform_int_distribution<int> dist_int;
    std::uniform_int_distribution<unsigned char> dist_5bit;

    int inst;
    int a;
    int b;

    void SetUp() override { dut = new ValuForTest(); }

    void TearDown() override {
        dut->final();
        delete dut;
    }
};

また、演算実行の一連の流れを exec メソッドとして定義するため、Verilator で生成された Valu クラスを継承して ValuForTest クラスを定義しています。

void ValuForTest::exec(const int &_inst, const int &_a, const int &_b) {
    inst = _inst;
    a = _a;
    b = _b;
    eval();
}

テストケース例 `TEST_F(TestAlu, ADD)`

テストケースの一つとして、 TEST_F(TestAlu, ADD) で inst が ADD 演算の場合のテストを行います。具体的には、N 回ランダムな整数 a と b を生成し、これを SystemVerilog モジュールに与えて計算結果が期待通りかどうかを ASSERT_EQ マクロを使用して検証しています。

const unsigned N = 1000000;

TEST_F(TestAlu, ADD) {
    inst = 0b000;
    for (unsigned i = 0; i < N; ++i) {
        a = dist_int(engine);
        b = dist_int(engine);
        dut->exec(inst, a, b);
        ASSERT_EQ(dut->rslt, a + b);
    }
}

この例では ADD 演算のみを示していますが、他の演算子に対するテストケースも同様の構造で追加できます。これにより、テスト対象の SystemVerilog モジュールが期待通りに動作しているかを確認できます。

テスト実行

SystemVerilog モジュールの単体テストを実行するために、CMake を使用してテストベンチをビルドし、実行結果を確認します。

CMake を使用したテストベンチのビルド

まず、テストベンチのビルドには以下の CMakeLists.txt を使用します。このファイルでは、Verilator と GoogleTest をプロジェクトに取り込み、テスト実行用のバイナリをビルドします。必要な部分を抜き出しています。

cmake_minimum_required(VERSION 3.14)
project(verilog_unittest_sample)

# ... Verilator と GoogleTest の取り込み（省略）

# Test フォルダ内のソースファイルを含むテスト実行用のバイナリを定義
enable_testing()
add_executable(test_all
  test/test_alu.cpp
  test/main.cpp
)
target_link_libraries(
  test_all
  PRIVATE
  GTest::gtest_main
)

# テストバイナリのプロパティを設定
set_target_properties(test_all PROPERTIES
  CXX_STANDARD 17
  CXX_STANDARD_REQUIRED ON
  COMPILE_FLAGS "-Wall -g -fsanitize=address"
  LINK_FLAGS "-fsanitize=address"
)

# GoogleTest によるテストの自動検出
include(GoogleTest)
gtest_discover_tests(test_all)

# Verilate を使用して Verilog モジュールをビルド
verilate(test_all
  INCLUDE_DIRS "src"
  SOURCES
  src/alu.sv
  PREFIX Valu
)

このCMakeLists.txtでは、add_executable でテスト用のバイナリを定義しています。また、Verilate を使用して SystemVerilog モジュールをビルドするために verilate を設定しています。

テストベンチのビルドと実行

以下のコマンドで CMake を使用してプロジェクトをビルドします。

$ cmake -S . -B build -G Ninja
$ ninja -C build

ビルドが完了したら、以下のコマンドでテストを実行します。

$ build/test_all

これにより、GoogleTest がテストを自動的に検出し、SystemVerilog モジュールの単体テストが実行されます。そうすると、以下のような結果が表示され、ALU の各演算子に対するテストが実行されたことがわかります。

[==========] Running 8 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 8 tests from TestAlu
[ RUN      ] TestAlu.ADD
[       OK ] TestAlu.ADD (337 ms)
[ RUN      ] TestAlu.SLL
[       OK ] TestAlu.SLL (278 ms)
[ RUN      ] TestAlu.SLT
[       OK ] TestAlu.SLT (272 ms)
[ RUN      ] TestAlu.SLTU
[       OK ] TestAlu.SLTU (281 ms)
[ RUN      ] TestAlu.XOR
[       OK ] TestAlu.XOR (267 ms)
[ RUN      ] TestAlu.SRL
[       OK ] TestAlu.SRL (279 ms)
[ RUN      ] TestAlu.OR
[       OK ] TestAlu.OR (260 ms)
[ RUN      ] TestAlu.AND
[       OK ] TestAlu.AND (273 ms)
[----------] 8 tests from TestAlu (2252 ms total)

[----------] Global test environment tear-down
[==========] 8 tests from 1 test suite ran. (2252 ms total)
[  PASSED  ] 8 tests.

試しに、ALU の演算結果が期待通りにならないように alu.sv を修正してみます。たとえば、加算命令実行時に alu_add の代わりに alu_xor を出力するようにしてみます。

-      3'b000:  rslt = alu_add;
+      3'b000:  rslt = alu_xor;

この状態で再度テストを実行すると、以下のように加算命令のテストが失敗することがわかります。

[==========] Running 8 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 8 tests from TestAlu
[ RUN      ] TestAlu.ADD
/home/mug/verilog-unittest-sample/test/test_alu.cpp:49: Failure
Expected equality of these values:
  dut->rslt
    Which is: 481875563
  a + b
    Which is: 549918315

[  FAILED  ] TestAlu.ADD (61 ms)
...（以下略）
[----------] 8 tests from TestAlu (1958 ms total)

[----------] Global test environment tear-down
[==========] 8 tests from 1 test suite ran. (1958 ms total)
[  PASSED  ] 7 tests.
[  FAILED  ] 1 test, listed below:
[  FAILED  ] TestAlu.ADD

 1 FAILED TEST

おまけ：GitHub Actions での自動テスト

上で生成したテストバイナリを用いれば、GitHub Actions で自動テストを行うこともできます。記事が長くなってしまったので詳細は省略しますが、hdlc/verilator というありがたいコンテナイメージがあります。このコンテナ上で新しいバージョンの Verilator を利用でき（2023 年 12 月 1 日現在では v5.018）、GitHub Actions で簡単にテストを実行できます。

まとめ

Verilator と GoogleTest を組み合わせて、SystemVerilog のモジュールを単体テストする方法を紹介しました。 GoogleTest のテストフィクスチャを用いることで、RTL の単体テストを簡単に書くことが出来そうです。ここまでで紹介したサンプルコードは、GitHub - sh-mug/verilog-unittest-sample で公開しています。

現状の方法では単体テストを行うモジュールごとに Verilator でライブラリを生成する必要があるので、これの改善方法を考えていきたいと思います。

2023-08-21

RECRUIT 日本橋ハーフマラソン 2023夏（AtCoder Heuristic Contest 022）解説

AHC022 お疲れ様でした。相対スコア 1,604,106,037,513 点で 1063 人中 48 位でした。長期コンテストで 2 桁順位を取れたのは初めてなので、記念に解法記事を書きます。

問題概要

ワームホールの入口と出口が N 個ずつありますが、その対応付けは分かっていません。ワームホールの出口周辺の気温情報を頼りに、対応付けを推定してください。ただし、最初に一回だけ出口セルがある空間の温度を自由に設定できます。

atcoder.jp

基本方針

基本的には以下の方針で解き、パラメータの値によって方針を多少変化させました。

配置パート
- 適当な順序で出口セルに温度 $0, P, 2P, \cdots , (N-1)P$ を割り当て、その他のマスの温度は盤面全体の温度勾配が滑らかになるよう設定する
計測パート
- ワームホールは出力の確信度合いが最も低いものを選ぶ
- 移動量は予想される出力の分散が最も大きいものを選ぶ
回答パート
- 全体の尤度が最大になるように $(0, 1, ... , N-1)$ の順列を選択し、回答する

配置パート

基本

まず適当な出口セルの温度を $0$ に設定し、この出口セルからマンハッタン距離の近い順に温度 $P, 2P, … , (N-1)P$ を割り当てます。温度を $0$ にするセルは、もっとも配置コストが小さくなるように選びます。 $P$ は $L, N, S$ の値から適当に決めます。

その他のマスの温度は盤面全体の温度勾配が滑らかになるよう設定します。ボロノイ図のような感じで温度を適当に埋めてから、出口セルの温度だけ固定してガウシアンぼかしを繰り返し適用すると、右のように盤面全体で滑らかな温度勾配を得られます。

$S, N$ が大きい場合：極端な温度のセルを作る

$S, N$ が大きい場合、基本方針だけでは近い出口セル同士の区別がつかず、正答率が下がってしまいます。その対策として、極端な温度を持つセルを $1, 2$ 個つくると、各出口セルの位置推定が容易になり、 $S$ が非常に大きいケースの正解率が上昇します。（という理屈が働いていると思うのですが、本当かどうかはわかりません……）

seed=8 (L=30 N=87 S=784) の場合は極端な温度のセルを 2 個用意する

計測パート

前提となる確率計算

ワームホール $i$ に関する観測情報の集合 $\mathbf{\theta}_i=(\mathbf{\theta}_{i1},\mathbf{\theta}_{i2},\cdots,\mathbf{\theta}_{im_i})$ をもとに、対応する出口が $j$ である確率 $P(p_{ij}\mid\theta_i)$ を計算することができます。ワームホールの入り口と出口の対応がランダムであることを利用すると、ベイズの定理より以下が成り立ちます。

$P(p_{ij}\mid\theta_i)=\displaystyle\frac{P(\theta_i\mid p_{ij})}{\sum_{j'=0}^{N-1} P(\theta_i\mid p_{ij'})}$

ところで、右辺に登場する $P(\theta_i\mid p_{ij})$ は計算で求めることができます。ワームホール $i$ の出口が $j$ であると仮定すると、そこから $(y,x)$ だけ移動したセルの位置と、そこで観測できる温度の確率分布が決まります。したがって、各観測情報 $\theta_{ik}$ から $P(\theta_{ik}\mid p_{ij})$ は計算可能なので、そこから以下が得られます。

$P(\theta_i\mid p_{ij})=\displaystyle\prod_{k=1}^{m_i} P(\theta_{ik}\mid p_{ij})$

基本

ワームホールの選び方

$\max_j P(p_{ij}\mid\theta_i)$ を、ワームホール $i$ と出口セルとの対応付けの確信度合いとみなします。全部のワームホールで自信を持って回答するため、確信度合いが最も低いワームホール $i$ を都度選択しました。確信度合いの最小値が一定値を超えると計測パートを終了し、回答に移ります。

移動量の選び方

ワームホールを選択した後、観測地点の出口セルからの移動量を決定します。このとき、もっとも出口セルを判別しやすい場所として、観測される温度の予測値の分散が最も大きくなる地点を選択します。

$S, N$ が小さい場合：移動量を制限する

$S, N$ が小さい場合は移動量 $(y,x)$ を制限しても全問正解することができます。計測コストは 1 回あたり $100\times (10+|y|+|x|)$ かかるため、移動量を制限して計測コストを下げることが可能です。

回答パート

回答パートでは、全体の尤度 $\prod_{i=0}^{N-1} P(p_{iE_i}\mid\theta_i)$ が最大になるような $(0, 1, ... , N-1)$ の順列 $(E_0, E_1, ... , E_{N-1})$ を選択し、出力しました。この最大化問題は以下のグラフの最小費用流問題に帰着して解くことが可能です。

最小費用流問題に帰着して順列を推定する形にすると、他のワームホールに関する観測情報も加味して出口セルを推定できるのがメリットですが、出口セルの推定を一度に 2 個間違えてしまう可能性があるのが難点です。全体的な正解率は最小費用流を使用したほうが高かったため、採用しました。

提出

以上をすべて実装したのが以下の提出になります。詳細なパラメータや、具体的な計算方法などはこちらを参考にしてください。

atcoder.jp

感想

最初は問題文の読解に手こずり、難しそうな問題だなと思っていたのですが、いざ取り組んでみると各パートで工夫のしがいがあって面白く、ビジュアライザも見映えがあって楽しい問題でした。

長期の AHC に本腰を入れて取り組んだのは（多分）初めてなので、普段よりよい順位を取れてよかったです。観測・回答パートでは統計の知識がかなり役立った感じがあります。一方で、 $S, N$ が大きい場合の配置パートに関しては考察不足でした。どうせ $S$ が大きいと各出口セルの温度は比較的どうでもよくなるのですが、 $S, N$ が小さい場合から大きく方針を変えるのは思い至りませんでした。最後の数日はパラメータ調整ばかりやっていたので、もう少し方針転換について考えてもよかったかもしれません。

2022-11-16

SECCON CTF 2022 Quals Writeups

SECCON CTF 2022 Quals にチーム TSG で参加し、this_is_not_lsb と noiseccon (実装パートのみ; アイデアは mikit さんから) の 2 問を解きました。以下はその writeup です。

this_is_not_lsb

Tired of difficult problems? Ok, I give you a simple LSB Padding Oracle problem. Ah, my magic has exploded... Sorry

問題概要

N …… 2 つの 512 bit 素数 p, q の積
e=65537
flag_length …… flag のビット長
c …… 暗号文

上の情報に加えて、任意の暗号文を復号した結果の1014～1023ビット目が 0011111111 かどうかをサーバーから得られる。そこから flag を推測すればよい。

解法

通常の LSB Padding Oracle problem では復号結果の下位 1 bit を得られるが、この問題では代わりに上位 10 bit のパターンが 0011111111 かどうか知ることができる。

以下、平文を m とする。 LSB が与えられる通常の問題と同様に、本問題も K^e c を復号して得られる Km の性質から解ける。この問題の場合は Km が 0b0011111111<<1014 以上 0b0100000000<<1014 未満かどうか知ることができるので、これを満たすような K の下界を二分探索し、そこから m を計算すればよい。

flag の形式が SECCON{[\x20-\x7e]+} であることを利用して適切に二分探索の探索範囲を絞っておくと、K の値の上界を気にせず探索できる。

SECCON{WeLC0me_t0_tHe_MirRoR_LaNd!_tHIs_is_lSb_orAcLe!}

▶ソルバー（クリックで展開）

gist.github.com

noiseccon

Noise! Noise! Noise!

問題概要

サーバーに scaleX, scaleY の 2 種類の値を渡すと、サーバーはランダムなシードで生成された 2 次元パーリンノイズの中から (offsetX, offsetY) を左上端とした 12.8×12.8 の領域を切り抜き、 256×256 ピクセルへと 20 倍に引き延ばして返す。

なお、offsetX, offsetY は index.js 内で以下のように定義されている。

const offsetX = div(flagInt, scaleX);
const offsetY = div(flagInt, scaleY);

また div は以下の通り実装されている。要するに div(x,y) は浮動小数点演算 x/y の結果から小数点以下を 4 bit、上を 32 bit だけ残して返す関数である。

const div = (x, y) => {
  const p = 4;
  return Number(BigInt.asUintN(32 + p, (x * BigInt(1 << p)) / y)) / (1 << p);
};

ここから flagInt を推測すればよい。

解法

アイデア

パーリンノイズは格子点を基準にテクスチャを生成するため、格子点には何らかの特徴がある。この特徴をもとに、サーバーが返す画像から格子点の位置を復元できれば offsetX, offsetY の小数点以下が分かる。

各オフセットは小数点 4 bit の情報を残しているので、scaleX, scaleY の両方を適切に設定すると 1 枚の画像からフラグ 1 文字分の情報を得られそうである。

実装

1 枚の画像からフラグの i 文字目を得るためには、offsetY, offsetX の小数点以下 4 bit (以下、hi, lo とする) がそれぞれ i 文字目の上位/下位 4 bit を表すようにすればよく、以下のように scaleX, scaleY を設定するとよい。

scaleX = 1 << (8 * (total_length - pad_length - idx) - 4)
scaleY = 1 << (8 * (total_length - pad_length - idx))

index.js の実装より、パーリンノイズの格子点に相当するピクセルの色はすべて #808080 になっているはずである。 (hi, lo) = (0, 0), (0, 1), ... , (15, 15) とそれぞれ仮定を置き、その場合の格子点の推定位置のピクセルの色が #808080 からどれだけ離れているかを残差平方和で表すと、この残差平方和を最小にするような (hi, lo) の組が求めたい情報になっている。

SECCON{p3RLin_W0r1d!}

フラグ 0 文字目を得るためのノイズ画像 (左)、そこから推測した (hi, lo) (右)

▶ソルバー（クリックで展開）

gist.github.com

2021-12-09

小さいサイズのスライドパズルを解かせる

この記事は

adventar.org

の9日目がなんか空いていたので書いている記事です。

導入

未来予知者なので、11日の枠にnaanさんの記事が投稿されることを知っています。具体的には「あほくさスライドパズル」と呼ばれる2x3サイズのスライドパズルを手で解くコツがよくまとまっており、naanさんの天才さも確かに感じられる良記事が存在する未来が見えます。

https://cdn-ak.f.st-hatena.com/images/fotolife/n/naan11235813/20211224/20211224032730.png — スライドパズルを解いているところ。naanさんの記事より

しかし、パズルを速く短く解くのは (naanさん以外の) 人間には至難の業です。凡人にも簡単な方法としてコンピュータにこのスライドパズルを解かせてみましょう。

解き方

グラフをつくる

このパズルでは適当なピースを1個スライドすることである盤面から他の盤面に変移できます。

f:id:sh-mug:20211225143052p:plain — 変移の例

盤面の状態を頂点とみなし、盤面変移の関係を辺とみなしたグラフを考えます。するとスライドパズルの解を求める問題は、このグラフ上で初期盤面から正解盤面までの路を探索する問題に帰着されます！

f:id:sh-mug:20211225154636p:plain — グラフの探索問題に帰着された

盤面の状態数は高々6!=720通りなので、この規模ならBFSで最短路を求めても高速に動作します。

コードを書く

書きます。

書きました。 (クリックで展開されます)

gist.github.com

解く

f:id:sh-mug:20211225171824p:plain — 解けるか……？

解きます。

$ time python3 ahokusa.py < ahokusa.in
下左上右右下左上左下

real    0m0.044s
user    0m0.044s
sys     0m0.000s

f:id:sh-mug:20211225171843p:plain — やったー

解けました。やったね

〆

2x3サイズなら簡単な知識だけでソルバーを作れるので、みんなも書いてみよう¹

元ネタ記事の作成、およびこの記事の確認をしてくださったnaanさんに最大限の敬意を表し、記事の締めといたします。

おまけ

初期盤面をコピーしスクリプトを実行してSlackに貼り付けるまでの時間でnaanさんが解き終えていました。一生勝てません

f:id:sh-mug:20211225172330p:plain — 自分が解答するより

f:id:sh-mug:20211225172403p:plain — naanさんの方が4秒速かった

naanさんにも紹介されている通り「千矢スライドパズル」とよばれる4x3サイズのスライドパズルもありますが、これは盤面数が12!=479001600の規模で存在します。実用的な速度で短い解を求めるにはA*などのヒューリスティクスが必要です。↩

2020-12-15

競プロで出がちなREの原因をまとめる

この記事はISer Advent Calendar 2020の15日目として書かれました。 14日目の記事はfushiguさんの tf-idfについて - fushigu’s blog でした。

自分用に書いていたメモをブログのネタにしようと思います。記事の特性上、問題のネタバレを含みます。

お前は誰

sh_mugというアカウント名で競プロをやっています。 (執筆時のレート: 1965)

使用言語はC++です。

REとは

RE (Runtime Error)
プログラムの実行中にエラーが発生しました。コンパイル時に検知できなかったエラーがあります.スタックオーバーフロー、ゼロ除算などが原因です.
(引用元: Glossary - AtCoder Beginner Contest 185)

REのタイプ別分類

自分が2020年に出した全32個のREのうち、気になったものをタイプ別に分類していきます。

配列への範囲外アクセス

配列の範囲外にアクセスすると、セグメンテーション違反でRuntime Errorが出がちです。コードテストでは、終了コードが139になります。

Submission #17971002 - AtCoder Beginner Contest 182
Submission #13841995 - AtCoder Beginner Contest 169
Submission #9301969 - AtCoder Beginner Contest 142

原因　for文のiの条件、配列の初期サイズなどのtypo
対策　わかりやすい変数名を付ける

for (int i = 0; i < h; ++i) { ...   // OK. これを書きたかった
for (int i = 0; i < n; ++i) { ...   // NG. hとnが似ていて気付きづらい

Submission #9298906 - AtCoder Grand Contest 031

原因　境界検査と論理演算の短絡評価が絡むバグ。
対策　配列へアクセスする評価より左に境界検査を書かないといけない。

if (i < N && a[i] == hoge) { ...    // OK. i>=Nのときa[i]にアクセスされない
if (a[i] == hoge && i < N) { ...    // NG. i>=NでREする

Submission #15160946 - AIsing Programming Contest 2020
Submission #14809790 - Introduction to Heuristics Contest

原因　インデックスをint型の配列で管理していて、配列に-1が入る可能性を考えていなかった
対策　場合分けをさぼらない

Submission #17034148 - ACL Beginner Contest
Submission #16482520 - DISCO presents ディスカバリーチャンネルプログラミングコンテスト2016 本選

原因　セグメント木のクエリの右端が右過ぎる
対策　手っ取り早い方法としては、木の構築時は配列の幅を広めに確保する。

ゼロ除算

さすがにやらないだろうと思っていたが、やっていた。終了コードは136です。

Submission #17851781 - AtCoder Regular Contest 060

原因　自作の約数列挙関数と、桁和計算関数の双方が原因になっている。詳しく説明すると、
- -1の約数を列挙→ 0以下が入力になることを想定しておらず、-1の約数列として{1, -1} が返される
- -1 + 1 = 0進数として桁和を計算→桁シフト時に0除算が発生
対策　まず除算、剰余演算において除数が0になる場合がないか確認する。あるいは、あらかじめ十分に処理の場合分けをする。

std::sortの第三引数

Submission #16018129 - AtCoder Regular Contest 074

原因　std::sortの第三引数に比較関数compを置くとき、comp(a, b) == comp(b, a) == trueを満たすような例が存在する。
対策　std::sortがREの原因になる可能性に留意する。

bool b; ...
std::sort(a.begin(), a.end(), [&](int x, int y){return b^(x<y);});    // NG
// b==trueのときx==yでcomp(x, y) == comp(y, x) == trueになってしまう

参考: stackoverflow.com

その他

Submission #15397247 - Tenka1 Programmer Beginner Contest

原因　提出言語の選択ミス。C++のコードをPythonとして提出した。
対策　直前に普段使わない言語で提出した、コードテストを使ったときは提出言語に注意する。またはonline-judge-toolsなどの自動提出を使う。

まとめ

REは気を付ければ防げるようなものが多い。
配列を大きめに確保しておくと何とかなることがある。
場合分けをさぼらない。

2020-05-07

5個以下の2入力NANDで3入力ORは作れるか？

作れません。（タイトル回収終了）

🐟

2入力NANDゲート回路だけで任意の論理演算が表現可能であるという事実はよく知られています。また、最小個数のNANDを用いてNOT・AND・OR・XORなどのゲートを実現する方法も有名です。（下画像）

f:id:sh-mug:20200507222911p:plain

ところで、3入力ゲート回路（AND・NAND・OR・NOR・XOR・XNOR）を実現するために必要なNANDの最小個数はあまり知られていない（はず）です。3入力ゲート回路の定義ですが、AND・OR・XORについては結合法則が成り立つので自然に定義できます。NAND・NOR・XNORは前の3つの論理否定とします。

やったこと

NAND同士を配線するときに回路内にループができると順序回路ができてしまうため、そうならないような配線方法のみを考えます。使用するNANDの個数を1個から順番に調べていき、求める出力を得られる回路が見つかればそのときの個数が最小だと分かります。

配線方法の探索にはSMTソルバの一つであるz3を使用しました。書いたコードはここです。リンク先のコードでは最小個数の3入力NANDから3入力XNORを構成するような配線方法を求めています。

結果など

2入力NANDを用いる場合、3入力NANDを用いる場合の最小個数を調べました。

使用するNAND	AND	NAND	OR	NOR	XOR	XNOR
2入力	4	3	6	7	8	9
3入力	2	1	4	5	7	7

3入力NANDを7個用いて3入力XOR・XNORを構成できるというのは比較的非自明で面白い結論かもしれません。回路図は下に示します。なお、NAND(A, A, B) = NAND(A, B)より、このような入力パターンの3入力NANDは2入力NANDを用いて略記しています。

f:id:sh-mug:20200507223023p:plain — XNOR

一方で、その他のゲート回路とNANDの入力の組み合わせについて、最小個数のNANDで構成するのは🐟にある回路の組み合わせだけで可能であり、必要なNAND数をそこから減らせないことも明らかになりました。（タイトル回収2回目）

🍣

z3を使う前にC++で配線方法を全探索するコードを書いていたのですが、z3を使ったほうが実行速度が圧倒的に速かったです。z3最高ですね

家にNANDしか無くて困っている人は参考にしてみてください。

TL;DR

テスト対象のモジュール

テストコード

テストフィクスチャ TestAlu

テストケース例 TEST_F(TestAlu, ADD)

テスト実行

CMake を使用したテストベンチのビルド

テストベンチのビルドと実行

おまけ：GitHub Actions での自動テスト

まとめ

問題概要

基本方針

配置パート

基本

が大きい場合：極端な温度のセルを作る

計測パート

前提となる確率計算

基本

ワームホールの選び方

移動量の選び方

が小さい場合：移動量を制限する

回答パート

提出

感想

this_is_not_lsb

問題概要

解法

noiseccon

問題概要

解法

アイデア

実装

導入

解き方

グラフをつくる

コードを書く

解く

〆

おまけ

お前は誰

REとは

REのタイプ別分類

配列への範囲外アクセス

ゼロ除算

std::sortの第三引数

その他

まとめ

🐟

やったこと

結果など

🍣

テストフィクスチャ `TestAlu`

テストケース例 `TEST_F(TestAlu, ADD)`

$S, N$ が大きい場合：極端な温度のセルを作る

$S, N$ が小さい場合：移動量を制限する