# Bit-String Hardware Accelerator ISA Specification

## 1. ISA Overview

**Architecture**: RISC-style bit-manipulation ISA  
**Operand Width**: 64-bit integer registers  
**Word Size**: 64 bits  
**Addressing**: Bit-addressed linear address space  

---

## 2. Register File

```
Registers: R0-R31 (32 × 64-bit GPRs)
Special Registers:
  - R0: Hard-wired zero
  - R31: Return value / implicit accumulator
```

---

## 3. Instruction Format

### 3.1 R-Type (Register-Register)
```
┌─────────┬─────┬─────┬─────┬────────────┐
│ Opcode  │ Rd  │ Rs1 │ Rs2 │ Reserved   │
│ 6 bits  │ 5   │ 5   │ 5   │ 13 bits    │
└─────────┴─────┴─────┴─────┴────────────┘
```

### 3.2 I-Type (Register-Immediate)
```
┌─────────┬─────┬─────┬──────────────┐
│ Opcode  │ Rd  │ Rs1 │  Immediate   │
│ 6 bits  │ 5   │ 5   │  18 bits     │
└─────────┴─────┴─────┴──────────────┘
```

### 3.3 L-Type (Load Immediate)
```
┌─────────┬─────┬──────────────────────┐
│ Opcode  │ Rd  │      Immediate       │
│ 6 bits  │ 5   │     53 bits (sign-ext) │
└─────────┴─────┴──────────────────────┘
```

---

## 4. Opcode Assignments

| Mnemonic       | Opcode | Type | Semantics |
|----------------|--------|------|-----------|
| BITLOAD        | 0x01   | R    | rd ← mem[rs1 + rs2 bit offset] & 1 |
| BITSTORE       | 0x02   | R    | mem[rs1 + rs2 bit offset] ← rs3 & 1 |
| BITFIELD       | 0x03   | R    | rd ← (mem[rs1 + rs2] >> rs3) & ((1 << rs4) - 1) |
| BITTEST        | 0x04   | R    | flag ← (mem[rs1 + rs2] >> bit_offset) & 1 |
| BITCOUNT       | 0x05   | R    | rd ← popcount(mem[rs1]) |
| BITSCANFWD     | 0x06   | R    | rd ← first_set_bit(rs1) |
| BITSCANREV     | 0x07   | R    | rd ← last_set_bit(rs1) |
| LOADIMM64      | 0x08   | L    | rd ← immediate (53-bit sign-extended) |
| BITEXTRACT     | 0x09   | R    | rd ← extract_field(rs1, rs2, rs3) |
| BITINSERT      | 0x0A   | R    | rd ← insert_field(rs1, rs2, rs3, rs4) |
| BITROTL        | 0x0B   | R    | rd ← rotate_left(rs1, rs2) |
| BITROTR        | 0x0C   | R    | rd ← rotate_right(rs1, rs2) |

---

## 5. Instruction Semantics

### 5.1 BITLOAD (Single-Bit Load)

**Encoding**: `BITLOAD Rd, Rs1, Rs2`

**Operation**:
```
effective_bit_address = Rs1 + Rs2
word_index = effective_bit_address / 64
bit_index = effective_bit_address mod 64
Rd ← (memory[word_index] >> bit_index) & 1
```

**Constraints**:
- `Rs1`: Bit base address (64-bit)
- `Rs2`: Bit offset (64-bit)
- `Rd`: Destination register (bit 0 set, bits [63:1] = 0)
- No privilege required
- May fault: page fault if effective address invalid

**Latency**: 3 cycles (address generation + memory access + extract)

---

### 5.2 BITSTORE (Single-Bit Write)

**Encoding**: `BITSTORE Rs1, Rs2, Rs3`

**Operation**:
```
effective_bit_address = Rs1 + Rs2
word_index = effective_bit_address / 64
bit_index = effective_bit_address mod 64
bit_value = Rs3 & 1
old_word = memory[word_index]
mask = 1 << bit_index
new_word = (old_word & ~mask) | (bit_value << bit_index)
memory[word_index] ← new_word
```

**Constraints**:
- `Rs1`: Bit base address
- `Rs2`: Bit offset
- `Rs3`: Bit value (only bit 0 is meaningful)
- No destination register
- Requires write permission on target memory
- May fault: segmentation fault, write-protect fault

**Latency**: 3 cycles (address generation + RMW cycle)

---

### 5.3 BITFIELD (Multi-Bit Extract)

**Encoding**: `BITFIELD Rd, Rs1, Rs2, Rs3, Rs4`

**Operation**:
```
effective_bit_address = Rs1 + Rs2
word_index = effective_bit_address / 64
bit_index = effective_bit_address mod 64
field_width = Rs3
bit_offset_in_word = Rs4

word = memory[word_index]
extracted = (word >> bit_offset_in_word) & ((1 << field_width) - 1)
Rd ← extracted
```

**Constraints**:
- `field_width` must be in range [1, 64]
- If `bit_offset + field_width > 64`, behavior is undefined (may trap)
- No cross-boundary extraction in this instruction (use software loop)

**Latency**: 3 cycles

---

### 5.4 BITTEST (Test and Branch)

**Encoding**: `BITTEST Rs1, Rs2`

**Operation**:
```
effective_bit_address = Rs1 + Rs2
word_index = effective_bit_address / 64
bit_index = effective_bit_address mod 64
condition_flag ← (memory[word_index] >> bit_index) & 1
```

**Latency**: 3 cycles

**Conditional Execution**: Sets zero flag (ZF) in status register:
- `ZF = 0` if bit is set
- `ZF = 1` if bit is clear

---

### 5.5 BITCOUNT (Population Count)

**Encoding**: `BITCOUNT Rd, Rs1`

**Operation**:
```
Rd ← popcount(Rs1)
```

**Latency**: 2 cycles (specialized hardware)

---

### 5.6 BITSCANFWD (Find First Set Bit)

**Encoding**: `BITSCANFWD Rd, Rs1`

**Operation**:
```
If Rs1 = 0:
  Rd ← 64 (or undefined, behavior determined by hardware)
Else:
  Rd ← position of rightmost set bit (0-indexed)
  Range: Rd ∈ [0, 63]
```

**Latency**: 2-3 cycles

---

### 5.7 BITSCANREV (Find Last Set Bit)

**Encoding**: `BITSCANREV Rd, Rs1`

**Operation**:
```
If Rs1 = 0:
  Rd ← 64 (or undefined)
Else:
  Rd ← position of leftmost set bit (0-indexed)
  Range: Rd ∈ [0, 63]
```

**Latency**: 2-3 cycles

---

### 5.8 LOADIMM64 (Load 53-Bit Immediate)

**Encoding**: `LOADIMM64 Rd, immediate`

**Operation**:
```
Rd ← sign_extend(immediate[52:0], 64)
```

**Latency**: 1 cycle

---

### 5.9 BITEXTRACT (Field Extraction with Width)

**Encoding**: `BITEXTRACT Rd, Rs1, Rs2, Rs3`

**Operation**:
```
value = Rs1
start_bit = Rs2
field_width = Rs3

extracted = (value >> start_bit) & ((1 << field_width) - 1)
Rd ← extracted
```

**Latency**: 1 cycle (register-only, no memory)

---

### 5.10 BITINSERT (Field Insertion)

**Encoding**: `BITINSERT Rd, Rs1, Rs2, Rs3, Rs4`

**Operation**:
```
dest_value = Rs1
source_value = Rs2
start_bit = Rs3
field_width = Rs4

mask = ((1 << field_width) - 1) << start_bit
shifted_source = (source_value & ((1 << field_width) - 1)) << start_bit
Rd ← (dest_value & ~mask) | shifted_source
```

**Latency**: 2 cycles

---

### 5.11 BITROTL (Rotate Left)

**Encoding**: `BITROTL Rd, Rs1, Rs2`

**Operation**:
```
value = Rs1
rotate_amount = Rs2 mod 64
Rd ← (value << rotate_amount) | (value >> (64 - rotate_amount))
```

**Latency**: 2 cycles

---

### 5.12 BITROTR (Rotate Right)

**Encoding**: `BITROTR Rd, Rs1, Rs2`

**Operation**:
```
value = Rs1
rotate_amount = Rs2 mod 64
Rd ← (value >> rotate_amount) | (value << (64 - rotate_amount))
```

**Latency**: 2 cycles

---

## 6. Memory Semantics

### 6.1 Byte Ordering (Little-Endian)

All operations assume little-endian byte ordering:
```
Memory layout (64-bit word at address 0x00):
Bit 0    at byte 0, bit 0
Bit 7    at byte 0, bit 7
Bit 8    at byte 1, bit 0
Bit 63   at byte 7, bit 7
```

### 6.2 Alignment Requirements

- No alignment requirement for bit addresses
- Memory accesses are naturally granular to 64-bit words
- Unaligned word access: hardware loads containing word, extracts bits

### 6.3 Virtual Memory Integration

- Bit addresses translate to physical addresses via TLB
- `word_address = bit_address >> 6` (divide by 64)
- `word_address` is then translated through MMU
- Page boundaries: if `bit_address` and `bit_address+63` span different pages, may require two memory accesses
- Hardware handles transparently for single-bit operations
- Multi-word operations may trap if boundary conditions not met

### 6.4 Cache Coherency

- Follows processor's existing cache coherency protocol
- BITSTORE is treated as a regular write for coherency purposes
- No special coherency instruction needed

---

## 7. Exception Behavior

| Exception | Opcode | Trigger | Action |
|-----------|--------|---------|--------|
| PAGE_FAULT | Any memory op | Address not in TLB | Interrupt handler, retry |
| PROTECTION_FAULT | BITSTORE | Page not writable | Interrupt handler |
| INVALID_ADDRESS | Any memory op | Address > max physical | Trap |
| UNDEFINED_FIELD_WIDTH | BITFIELD | width = 0 or width > 64 | Trap |

---

## 8. Status Register (Implicit)

```
Bit Name    Meaning
0   ZF      Zero Flag (set by BITTEST)
1   CF      Carry Flag (unused in this ISA)
2-63        Reserved
```

---

## 9. Privilege Levels

All bit-string instructions are **user-mode executable**. No privilege escalation.

Exception: Bit addresses pointing to kernel memory may trigger protection faults.

---

## 10. Formal Semantics (First-Order Logic)

### Correctness Property: Single-Bit Load

```
∀ base, offset ∈ ℕ :
  let eff_addr = base + offset
  let word_idx = eff_addr >> 6
  let bit_idx = eff_addr mod 64
  BITLOAD base offset = (mem[word_idx] >> bit_idx) & 1
```

### Correctness Property: Single-Bit Store

```
∀ base, offset, value ∈ ℕ :
  let eff_addr = base + offset
  let word_idx = eff_addr >> 6
  let bit_idx = eff_addr mod 64
  let mask = 1 << bit_idx
  
  after BITSTORE base offset value:
    mem[word_idx] = (mem[word_idx] & ~mask) | ((value & 1) << bit_idx)
    ∀ j ≠ word_idx : mem[j] unchanged
```

### Correctness Property: Field Extraction

```
∀ value, start, width ∈ ℕ, width ≤ 64 :
  BITEXTRACT value start width = (value >> start) & ((1 << width) - 1)
```

---

## 11. Implementation Constraints

- **Max memory size**: 2^64 bits (addressable)
- **Max single extraction**: 64 bits per instruction
- **Max rotation**: Full 64-bit rotation with any offset
- **Frequency**: Target 1+ GHz (1-3 cycle latency operations)
- **Power**: < 2mW per operation (estimated)
- **Area**: ~100-200k gates (estimates as sub-module)

---

## 12. Future Extensions (Out of Scope)

- SIMD bit-parallel operations
- GPU integration
- Vector bit strings
- Conditional bit operations
- Atomic bit operations (hardware locks)