phanerozoic / threshold-ffs8

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)

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

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

Usage

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

Files

threshold-ffs8/
├── model.safetensors
├── model.py
├── create_safetensors.py
├── config.json
└── README.md

License

MIT