File size: 3,773 Bytes
26e7af6 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 | ---
license: mit
tags:
- pytorch
- safetensors
- threshold-logic
- neuromorphic
- bit-manipulation
- ffs
---
# threshold-ffs8
8-bit find first set (FFS). Returns the 1-indexed position of the least significant set bit. Returns 0 if no bits are set.
## Circuit
```
x7 x6 x5 x4 x3 x2 x1 x0
│ │ │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┘
│
▼
┌─────────────────────┐
│ CTZ + 1 (if set) │
│ or 0 (if all zero) │
└─────────────────────┘
│
▼
[f3, f2, f1, f0]
(position 0-8)
```
## Function
```
ffs8(x7..x0) -> (f3, f2, f1, f0)
position = 8*f3 + 4*f2 + 2*f1 + f0
if input = 0: position = 0
if input != 0: position = CTZ(input) + 1
```
FFS is 1-indexed: the first bit (x0) is position 1, not 0.
## Truth Table (selected)
| Input (hex) | Binary | FFS | f3 f2 f1 f0 | Meaning |
|-------------|--------|:---:|-------------|---------|
| 0x00 | 00000000 | 0 | 0 0 0 0 | No bits set |
| 0x01 | 00000001 | 1 | 0 0 0 1 | Bit 0 is first |
| 0x02 | 00000010 | 2 | 0 0 1 0 | Bit 1 is first |
| 0x04 | 00000100 | 3 | 0 0 1 1 | Bit 2 is first |
| 0x08 | 00001000 | 4 | 0 1 0 0 | Bit 3 is first |
| 0x10 | 00010000 | 5 | 0 1 0 1 | Bit 4 is first |
| 0x20 | 00100000 | 6 | 0 1 1 0 | Bit 5 is first |
| 0x40 | 01000000 | 7 | 0 1 1 1 | Bit 6 is first |
| 0x80 | 10000000 | 8 | 1 0 0 0 | Bit 7 is first |
| 0xFF | 11111111 | 1 | 0 0 0 1 | Bit 0 is first |
## Relationship to CTZ
```
if (input == 0):
FFS = 0
else:
FFS = CTZ + 1
```
FFS and CTZ are closely related:
- CTZ returns 0-7 for positions, 8 for zero input
- FFS returns 1-8 for positions, 0 for zero input
## Mechanism
**Position detectors:** Same as CTZ - detect where first 1 appears from LSB
| Signal | Fires when |
|--------|------------|
| p0 | x0 = 1 |
| p1 | x0 = 0, x1 = 1 |
| p2 | x0 = x1 = 0, x2 = 1 |
| ... | ... |
| p7 | x0..x6 = 0, x7 = 1 |
**Output encoding:** Direct binary encoding of position + 1
- f0 = p0 OR p2 OR p4 OR p6 (positions 0,2,4,6 → FFS 1,3,5,7)
- f1 = p1 OR p2 OR p5 OR p6 (positions 1,2,5,6 → FFS 2,3,6,7)
- f2 = p3 OR p4 OR p5 OR p6 (positions 3,4,5,6 → FFS 4,5,6,7)
- f3 = p7 (position 7 → FFS 8)
## Parameters
| | |
|---|---|
| Inputs | 8 |
| Outputs | 4 |
| Neurons | 12 |
| Layers | 2 |
| Parameters | 76 |
| Magnitude | 48 |
## Usage
```python
from safetensors.torch import load_file
import torch
w = load_file('model.safetensors')
def ffs8(bits):
# bits = [x0, x1, ..., x7] (LSB first)
inp = torch.tensor([float(b) for b in bits])
# ... (see model.py for full implementation)
# Examples
print(ffs8([1,0,0,0,0,0,0,0])) # 1 (first bit set is position 0)
print(ffs8([0,0,1,0,0,0,0,0])) # 3 (first bit set is position 2)
print(ffs8([0,0,0,0,0,0,0,0])) # 0 (no bits set)
```
## Applications
- POSIX ffs() function implementation
- Finding available slots in bitmaps
- Scheduler ready queue processing
- Memory allocator free list management
- Interrupt priority handling
## Comparison: FFS vs CTZ vs CLZ
| Function | Zero input | Non-zero input | Index base |
|----------|------------|----------------|------------|
| FFS | 0 | 1 to 8 | 1-indexed |
| CTZ | 8 | 0 to 7 | 0-indexed |
| CLZ | 8 | 0 to 7 | 0-indexed from MSB |
## Files
```
threshold-ffs8/
├── model.safetensors
├── model.py
├── create_safetensors.py
├── config.json
└── README.md
```
## License
MIT
|