# 機能設計書 53-bitops（ビット操作）

## 概要

本ドキュメントは、Nim標準ライブラリのビット操作モジュール（bitops.nim）について、その設計と仕様を詳細に記載した機能設計書である。

### 本機能の処理概要

bitopsモジュールは、低レベルのビット操作メソッドを提供する。可能な場合はコンパイラ組み込み関数（intrinsics）を使用して、対応コンパイラ（GCC, LLVM_GCC, CLANG, VCC, ICC）でのパフォーマンスを向上させる。

**業務上の目的・背景**：暗号化、圧縮、ハッシュ計算、グラフィックス処理、ネットワークプロトコル、ハードウェア制御などの分野では、効率的なビット操作が不可欠である。本モジュールは、コンパイラの最適化を活用しつつ、JavaScript、NimScript、コンパイル時VMでも動作する移植性の高いビット操作関数を提供する。

**機能の利用シーン**：
- ビットフラグの設定・クリア・トグル・テスト
- ビットカウント（Hamming weight）の計算
- 最初または最後のセットビットの検出
- ビットローテーション（左右）
- ビット反転
- ビットスライス抽出
- ビットパリティ計算

**主要な処理内容**：
1. 基本ビット演算（bitnot, bitand, bitor, bitxor）
2. ビットマスク操作（masked, setMasked, clearMasked, flipMasked）
3. 単一ビット操作（setBit, clearBit, flipBit, testBit）
4. ビットカウント関数（countSetBits/popcount, parityBits）
5. ビット位置検出（firstSetBit, fastLog2, countLeadingZeroBits, countTrailingZeroBits）
6. ビットローテーション（rotateLeftBits, rotateRightBits）
7. ビット反転（reverseBits）
8. ビットスライス（bitsliced, bitslice, toMask）

**関連システム・外部連携**：対応コンパイラ（GCC, Clang, VCC, ICC）の組み込み関数を利用。未対応のバックエンドでは純粋なNim実装にフォールバック。

**権限による制御**：特になし。すべての機能が任意のコードから利用可能。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 本モジュールはライブラリ機能であり、直接の画面関連なし |

## 機能種別

計算処理

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|-----------------|
| x, y, z | SomeInteger | Yes | ビット演算の対象となる整数値 | 整数型であること |
| v | SomeInteger | Yes | ビット操作対象の変数 | 整数型であること |
| mask | SomeInteger | Yes | ビットマスク | 操作対象と同じ整数型 |
| slice | Slice[int] | Yes | ビットスライスの範囲 | 有効なビット範囲内 |
| bit | BitsRange[T] | Yes | 操作対象のビット位置 | 0..sizeof(T)*8-1 |
| shift | range[0..(sizeof(T)*8)] | Yes | ローテーション量 | 型のビット幅以内 |

### 入力データソース

- プログラムから直接渡される整数値

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| ビット演算結果 | SomeInteger | bitnot, bitand, bitor, bitxorの結果 |
| ビットカウント | int | 設定されているビット数 |
| ビット位置 | int | 最初のセットビットの1ベースインデックス |
| パリティ | int | 1ビットの数が奇数なら1、偶数なら0 |
| 対数 | int | 2を底とする対数（整数部） |
| ローテーション結果 | SomeUnsignedInt | ローテーション後の値 |
| 反転結果 | SomeUnsignedInt | ビット順序を反転した値 |

### 出力先

呼び出し元への戻り値

## 処理フロー

### 処理シーケンス

```
1. 基本ビット演算
   └─ bitnot, bitand, bitor, bitxorはmagic関数としてコンパイラに直接マッピング

2. ビットマスク操作
   └─ masked: bitandでマスク適用
   └─ setMasked: bitorでビットセット
   └─ clearMasked: bitandとbitnotでビットクリア
   └─ flipMasked: bitxorでビットトグル

3. ビットカウント
   └─ countSetBits: コンパイラ組み込み関数を使用（利用可能な場合）
   └─ parityBits: XORベースのパリティ計算

4. ビット位置検出
   └─ firstSetBit: __builtin_ffs等の組み込み関数、またはDe Bruijnシーケンス
   └─ fastLog2: __builtin_clz等、またはDe Bruijnシーケンス
   └─ countLeadingZeroBits: fastLog2から計算
   └─ countTrailingZeroBits: firstSetBitから計算

5. ビットローテーション
   └─ rotateLeftBits/rotateRightBits: 組み込み関数またはシフト演算
```

### フローチャート

```mermaid
flowchart TD
    A[開始] --> B{操作種別}
    B -->|基本演算| C[magic関数呼び出し]
    B -->|マスク操作| D[基本演算の組み合わせ]
    B -->|ビットカウント| E{コンパイラ対応?}
    E -->|Yes| F[組み込み関数呼び出し]
    E -->|No| G[純粋Nim実装]
    B -->|位置検出| H{コンパイラ対応?}
    H -->|Yes| I[組み込み関数呼び出し]
    H -->|No| J[De Bruijnシーケンス]
    B -->|ローテーション| K{コンパイラ対応?}
    K -->|Yes| L[組み込み関数呼び出し]
    K -->|No| M[シフト演算の組み合わせ]
    C --> N[結果返却]
    D --> N
    F --> N
    G --> N
    I --> N
    J --> N
    L --> N
    M --> N
    N --> O[終了]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-001 | 組み込み関数優先 | 対応コンパイラでは組み込み関数を使用 | useBuiltinsが有効な場合 |
| BR-002 | フォールバック | 未対応環境では純粋Nim実装を使用 | 組み込み関数が使用できない場合 |
| BR-003 | 未定義値の可能性 | fastLog2, firstSetBit等は入力が0の場合に未定義値を返す可能性 | noUndefinedBitOptsフラグが未設定の場合 |
| BR-004 | BitsRange制約 | ビット位置はBitsRange[T]型により0..sizeof(T)*8-1に制限 | 単一ビット操作時 |

### 計算ロジック

**De BruijnシーケンスによるfirstSetBit**:
```nim
const lookup: array[32, uint8] = [0'u8, 1, 28, 2, ...]
let k = not v + 1  # two's complement
result = 1 + lookup[uint32((v and k) * 0x077CB531'u32) shr 27].int
```

**ビットローテーション**:
```nim
proc rotl[T](value: T, rot: int32): T =
  const mask = 8 * sizeof(value) - 1
  let rot = rot and mask
  (value shl rot) or (value shr ((-rot) and mask))
```

**ビット反転**:
```nim
# 段階的にビット位置を入れ替え
result = ((0x55 and result) shl 1) or ((0xaa and result) shr 1)
result = ((0x33 and result) shl 2) or ((0xcc and result) shr 2)
# ... 以下同様
```

## データベース操作仕様

### 操作別データベース影響一覧

本モジュールはデータベース操作を行わない。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | 未定義動作 | fastLog2, firstSetBit等に0を渡した場合（noUndefinedBitOpts未設定時） | noUndefinedBitOptsフラグを設定するか、事前に0チェック |
| - | 範囲外 | BitsRange外のビット位置を指定した場合 | コンパイル時にエラー検出 |

### リトライ仕様

リトライ不要（純粋な計算処理のため）

## トランザクション仕様

データベース操作がないため該当なし

## パフォーマンス要件

- 組み込み関数使用時: O(1)の定数時間、最速のCPU命令を使用
- 純粋Nim実装: O(1)だが組み込み関数より低速
- countSetBitsはpopcount命令を使用可能な場合は1命令で完了

## セキュリティ考慮事項

- 暗号処理でのタイミング攻撃に注意（入力値によって処理時間が変わる可能性）
- 未定義動作の発生を避けるためnoUndefinedBitOptsの使用を検討

## 備考

- `noIntrinsicsBitOpts`フラグで組み込み関数を無効化可能
- `noUndefinedBitOpts`フラグで未定義動作を回避可能（わずかなパフォーマンス低下）
- JavaScript、NimScript、コンパイル時VMでも動作

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: 基本ビット演算を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | bitops.nim | `lib/pure/bitops.nim` | bitnot, bitand, bitor, bitxor（32-60行目） |

**読解のコツ**: `{.magic: "BitnotI".}`等のプラグマはコンパイラの組み込み操作に直接マッピングされる。

#### Step 2: BitsRange型を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | bitops.nim | `lib/pure/bitops.nim` | BitsRange型の定義（63行目） |

**主要定義**:
- **63行目**: `BitsRange*[T] = range[0..sizeof(T)*8-1]` - 型Tのすべてのビット位置を表す範囲型

#### Step 3: ビットスライス操作を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | bitops.nim | `lib/pure/bitops.nim` | bitsliced, bitslice, toMask（72-106行目） |

#### Step 4: マスク操作を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | bitops.nim | `lib/pure/bitops.nim` | masked, setMasked, clearMasked, flipMasked（107-281行目） |

**主要処理フロー**:
- **masked**: bitandでマスク適用
- **setMasked**: bitorでビットセット
- **clearMasked**: bitand(v, bitnot(mask))
- **flipMasked**: bitxorでトグル

#### Step 5: 単一ビット操作を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | bitops.nim | `lib/pure/bitops.nim` | setBit, clearBit, flipBit, testBit（283-359行目） |

#### Step 6: De Bruijnシーケンスによる実装を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 6-1 | bitops.nim | `lib/pure/bitops.nim` | firstSetBitNim, fastlog2Nim（363-413行目） |

**読解のコツ**: De Bruijnシーケンスは完全ハッシュ関数として機能し、O(1)でビット位置を計算する。

#### Step 7: コンパイラ組み込み関数を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 7-1 | bitops.nim | `lib/pure/bitops.nim` | GCC/VCC/ICC組み込み関数（435-487行目） |

#### Step 8: ビットカウント・位置検出関数を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 8-1 | bitops.nim | `lib/pure/bitops.nim` | countSetBits, parityBits, firstSetBit, fastLog2（488-602行目） |

#### Step 9: ビットローテーションを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 9-1 | bitops.nim | `lib/pure/bitops.nim` | rotl, rotr, rotateLeftBits, rotateRightBits（757-839行目） |

#### Step 10: ビット反転を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 10-1 | bitops.nim | `lib/pure/bitops.nim` | reverseBits（848-884行目） |

### プログラム呼び出し階層図

```
ユーザーコード
    │
    ├─ 基本ビット演算（magic関数）
    │      ├─ bitnot(x) ──────────▶ CPU命令
    │      ├─ bitand(x, y, z...) ─▶ CPU命令
    │      ├─ bitor(x, y, z...) ──▶ CPU命令
    │      └─ bitxor(x, y, z...) ─▶ CPU命令
    │
    ├─ マスク操作
    │      ├─ masked(v, mask) ────▶ bitand
    │      ├─ setMasked(v, mask) ─▶ bitor
    │      ├─ clearMasked(v, mask)▶ bitand + bitnot
    │      └─ flipMasked(v, mask) ▶ bitxor
    │
    ├─ 単一ビット操作
    │      ├─ setBit(v, bit) ─────▶ setMask(1.T shl bit)
    │      ├─ clearBit(v, bit) ───▶ clearMask(1.T shl bit)
    │      ├─ flipBit(v, bit) ────▶ flipMask(1.T shl bit)
    │      └─ testBit(v, bit) ────▶ (v and mask) == mask
    │
    ├─ ビットカウント
    │      ├─ countSetBits(x)
    │      │      ├─ [GCC] __builtin_popcount
    │      │      └─ [fallback] countSetBitsImpl
    │      └─ parityBits(x)
    │             ├─ [GCC] __builtin_parity
    │             └─ [fallback] parityImpl
    │
    ├─ ビット位置検出
    │      ├─ firstSetBit(x)
    │      │      ├─ [GCC] __builtin_ffs
    │      │      └─ [fallback] firstSetBitNim（De Bruijn）
    │      ├─ fastLog2(x)
    │      │      ├─ [GCC] __builtin_clz
    │      │      └─ [fallback] fastlog2Nim（De Bruijn）
    │      ├─ countLeadingZeroBits(x) ─▶ sizeof*8 - 1 - fastLog2
    │      └─ countTrailingZeroBits(x) ▶ firstSetBit - 1
    │
    └─ ビットローテーション
           ├─ rotateLeftBits(value, shift)
           │      ├─ [Intrinsics] builtin_rotl*
           │      └─ [fallback] rotl
           └─ rotateRightBits(value, shift)
                  ├─ [Intrinsics] builtin_rotr*
                  └─ [fallback] rotr
```

### データフロー図

```
[入力]               [処理]                    [出力]

整数値 ───────────▶ bitnot() ────────────────▶ ビット反転値
整数値2つ以上 ────▶ bitand/bitor/bitxor() ──▶ 演算結果

整数値 + マスク ──▶ masked() ────────────────▶ マスク適用値
整数値 + マスク ──▶ setMasked() ─────────────▶ ビットセット値
整数値 + マスク ──▶ clearMasked() ───────────▶ ビットクリア値
整数値 + マスク ──▶ flipMasked() ────────────▶ ビットトグル値

整数値 ───────────▶ countSetBits() ──────────▶ ビット数(int)
整数値 ───────────▶ parityBits() ────────────▶ パリティ(0/1)
整数値 ───────────▶ firstSetBit() ───────────▶ ビット位置(int)
整数値 ───────────▶ fastLog2() ──────────────▶ log2値(int)

整数値 + シフト量 ▶ rotateLeftBits() ────────▶ ローテーション結果
整数値 + シフト量 ▶ rotateRightBits() ───────▶ ローテーション結果

整数値 ───────────▶ reverseBits() ───────────▶ ビット順反転値
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| bitops.nim | `lib/pure/bitops.nim` | ソース | ビット操作の主要実装 |
| bitops_utils.nim | `lib/std/private/bitops_utils.nim` | ソース | ユーティリティ関数 |
| countbits_impl.nim | `lib/system/countbits_impl.nim` | ソース | ビットカウント実装 |
| macros.nim | `lib/core/macros.nim` | ソース | bitand/bitor/bitxorマクロ用 |
