seccamp 2022 課題

fifo.sv

module fifo (
  input wire clock,  // クロック入力
  input wire reset,  // Active Highの同期リセット入力

  input  wire         in_valid,   // 入力VALID
  output logic        in_ready,   // 入力READY
  input  wire [7:0]   in_data,    // 入力データ

  output logic        out_valid,  // 出力VALID
  input  wire         out_ready,  // 出力READY
  output logic [7:0]  out_data    // 出力データ
);
  parameter LENGTH = 1024;
  parameter WIDTH  = 8;

  reg [WIDTH-1 : 0] buffer[LENGTH-1 : 0];
  int write, read;

  always @(posedge reset) begin
    out_valid <= 0;
    out_data  <= 0;
    in_ready  <= 1;
    write     <= 0;
    read      <= -1;
  end

  // FIFOに値を追加
  always @(posedge in_valid) begin
    in_ready       = 0;
    buffer[write] <= in_data;
    write         <= (write + 1) % LENGTH;
    if (read == -1) begin
      read = 0;
    end
    in_ready = 1;
  end

  // 値を出力
  always @(posedge clock) begin
    // バッファが空のとき、追加されるまでスキップ
    if (write != read && read != -1) begin 
      out_data    <= buffer[read];
      // out_validがアサートされている（直前に読み取られている）
      // かつready済みなら次の値
      if (out_ready && out_valid) begin
        read      <= (read + 1) % LENGTH;
        out_valid <= 0;
      end else begin
        out_valid <= 1;
      end
    end 
  end
  
endmodule

ring.c

// clang 13.0.1 と gcc 12.1.0 でテスト通過
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

// リングバッファを表す構造体
struct RingBuffer {
  int*   buffer;
  size_t size;
  int    count;
  int    front;
  int    dst;
};

typedef struct {
  bool has_value;
  int  value;
} Optional;

// リングバッファを生成して返す
struct RingBuffer* ring_new(size_t size) {
  struct RingBuffer* buf =
      (struct RingBuffer*)malloc(sizeof(struct RingBuffer));
  if (buf == NULL) return NULL;
  buf->buffer = (int*)malloc(sizeof(int) * size);
  if (buf->buffer == NULL) return NULL;
  buf->size  = size;
  buf->count = 0;
  buf->front = 0;
  buf->dst   = -1;
  return buf;
}

// デバッグ用（提出時はreturnを用いて機能しないようにしています）
void print_ring(struct RingBuffer* r) {
  return;
  for (int i = 0; i < r->size; ++i) {
    printf("%d, ", r->buffer[i]);
  }

  putchar('\n');
  for (int i = 0; i < r->front * 3; ++i) {
    putchar(' ');
  }
  puts("^ front");
  for (int i = 0; i < r->dst * 3; ++i) {
    putchar(' ');
  }
  puts("^ dst");
}

// リングバッファ ring の末尾に要素 value を追加
// 成功した時trueを返却
bool ring_push(struct RingBuffer* ring, int value) {
  if (ring == NULL) return false;
  if (ring->size == ring->count) return false;
  ring->dst               = (ring->dst + 1) % ring->size;
  ring->buffer[ring->dst] = value;
  ++ring->count;
  print_ring(ring);
  return true;
}

// リングバッファ ring の先頭要素を取り除いて返す
// 戻り値の型がintだと、エラー時の判別が出来ないという問題点がある
// 一応C++のstackはempty時のtopアクセスは未定義動作とのこと
Optional ring_pop(struct RingBuffer* ring) {
  if (ring == NULL) return (Optional){false, 0};
  if (ring->count == 0) return (Optional){false, 0};
  int val     = ring->buffer[ring->front];
  ring->front = (ring->front + 1) % ring->size;
  --ring->count;
  print_ring(ring);
  return (Optional){true, val};
}

// テスト記述のための便利関数
int  fail, success;
void assert_equal(int want, int got) {
  if (want == got) {
    printf("OK: want %d, got %d\n", want, got);
    success++;
  } else {
    printf("NG: want %d, got %d\n", want, got);
    fail++;
  }
}

// テストケース群
void test_push_pop() {
  struct RingBuffer* r = ring_new(4);
  ring_push(r, 2);
  ring_push(r, 3);

  assert_equal(2, ring_pop(r).value);
  assert_equal(3, ring_pop(r).value);
}

// バッファを全て埋めようとした時、
// pushに成功＋popで入れた順に取り出せることを確認
void test_max_push(void) {
  struct RingBuffer* r = ring_new(4);
  // push
  for (int i = 1; i <= r->size; ++i) {
    assert_equal(true, ring_push(r, i));
  }
  // pop
  for (int i = 1; i <= r->size; ++i) {
    assert_equal(i, ring_pop(r).value);
  }
}

// 2サイクル分のpushを行った際、
// pushに成功＋popで入れた順に取り出せることを確認
void test_cycle_push(void) {
  struct RingBuffer* r = ring_new(4);
  // two cycle
  for (int i = 0; i < 4; ++i) {
    // push
    for (int i = 1; i <= r->size / 2; ++i) {
      assert_equal(true, ring_push(r, i));
    }
    // pop
    for (int i = 1; i <= r->size / 2; ++i) {
      assert_equal(i, ring_pop(r).value);
    }
  }
}

// バッファが空である状態でpopした際に0が返ってくることを確認
void test_empty_pop(void) {
  struct RingBuffer* r = ring_new(1);
  assert_equal(false, ring_pop(r).has_value);
}

// バッファがフルである状態でpushに失敗することを確認
void test_full_push(void) {
  const int          len = 4;
  struct RingBuffer* r   = ring_new(len);
  for (int i = 1; i <= len; ++i) {
    assert_equal(true, ring_push(r, i));
  }
  assert_equal(false, ring_push(r, 1));
}

int main() {
  puts("[test] push_pop");
  test_push_pop();
  // 他のテストケース呼び出しはここに追記

  puts("[test] max_push");
  test_max_push();
  puts("[test] cycle_push");
  test_cycle_push();
  puts("[test] empty_push");
  test_empty_pop();
  puts("[test] full_push");
  test_full_push();

  if (fail != 0) {
    printf("FAILED: %d/%d tests failed\n", fail, fail + success);
    return EXIT_FAILURE;
  }
  printf("PASSED: All tests finished successfully\n");
  return EXIT_SUCCESS;
}