Bit Manipulation Questions

Approach summary
Use a byte-array canonical on-wire format and implement portable bit-level pack/unpack routines rather than C compiler bitfields. Reserve a version and flags field, include a CRC8 for error detection, and allow optional extension blocks. Handle endianness by reading/writing bits in a defined MSB-first or LSB-first order.

Packet layout (12 bytes = 96 bits) — example

• byte 0: [ version:3 | flags:5 ]
• bits 8..31: fieldA:24
• bits 32..47: fieldB:16
• bits 48..71: fieldC:24
• bits 72..87: fieldD:16
• bits 88..95: checksum:8 (CRC-8 of bytes 0..10)

This is MSB-first within each byte (network order).

Why not compiler bitfields

• Compiler-dependent packing/endianness/ordering. Portable code should manipulate bytes and bits explicitly.

Parsing/writing pseudocode (C-style)

// read bitfield helper (MSB-first within bytes)
uint64_t read_bits(const uint8_t *buf, int bit_offset, int bit_len) {
    uint64_t v = 0;
    for (int i = 0; i < bit_len; ++i) {
        int b = bit_offset + i;
        uint8_t byte = buf[b / 8];
        int bit_in_byte = 7 - (b % 8); // MSB-first
        v = (v << 1) | ((byte >> bit_in_byte) & 1);
    }
    return v;
}

void write_bits(uint8_t *buf, int bit_offset, int bit_len, uint64_t value) {
    for (int i = bit_len - 1; i >= 0; --i) {
        int b = bit_offset + (bit_len - 1 - i);
        uint8_t *byte = &buf[b / 8];
        int bit_in_byte = 7 - (b % 8);
        uint8_t bit = (value >> i) & 1;
        *byte = (*byte & ~(1 << bit_in_byte)) | (bit << bit_in_byte);
    }
}

High-level parser

• Verify packet length == 12
• Compute CRC-8 over bytes 0..10, compare to checksum at byte 11
• Extract version = read_bits(buf, 0, 3)
• Switch on version; for unknown higher version return controlled error (or attempt best-effort)
• Extract fields via read_bits()
• Validate ranges and flags

Versioning & extensibility

• 3-bit version allows evolving format. New fields appended into reserved flag space or new extension region flagged by flags bits. Receiver ignores unknown optional extensions.

Error detection

• Use CRC-8 (polynomial e.g., 0x07) in last byte. Also include sanity checks (range, reserved bits zero).

Testing strategy (big/little-endian)

• Unit tests use reference vectors: construct packet via write_bits on a known-endian host, compare against known good hex string.
• Cross-build and run tests on both little-endian and big-endian boards (or QEMU for big-endian sim).
• Property tests: randomize fields, pack then unpack and assert equality; also flip single bits and assert CRC catches errors.
• Fuzz tests: malformed lengths, corrupted checksum, version mismatch.
• CI: include tests running in a deterministic emulator for both endiannesses and check reference CRC and fields.

Trade-offs

• Bit-wise helpers cost a few cycles but are small and portable. If performance critical, offer optimized versions for common platforms using aligned reads with explicit byte-order conversions.

Design summary

• Choose m = 4,800 bits (600 bytes) and k = 7. This follows the Bloom formula m = -(n ln p)/(ln2)^2 ≈ 4,788 bits for n=500, p=0.01; optimal k ≈ (m/n) ln2 ≈ 6.64 → 7. Fits easily in 8 KB SRAM and meets p≈1%.

Why these values

• Small m minimizes memory while meeting target false-positive rate.
• k = 7 keeps per-operation cost reasonable on an MCU.

Bit-array layout & fast ops

• Store as byte array: uint8_t bits[(m+7)/8]; index bit i by byte = i >> 3, bitmask = 1u << (i & 7).
• Use bitwise OR to set and AND to test; these are single-instruction on most MCUs.

Double hashing to reduce hash work

• Compute two independent 32-bit hashes h1 and h2 (e.g., CRC32 + FNV1a or MurmurHash3).
• Derive k indices: gi = (h1 + i * h2) % m for i = 0..k-1. This gives k pseudo-hashes with only two hash computations.

C-style add()/contains()

// m = 4800
#define M_BITS 4800
uint8_t bits[(M_BITS+7)/8];

static inline void set_bit(uint32_t i){
  bits[i >> 3] |= (1u << (i & 7));
}
static inline bool test_bit(uint32_t i){
  return bits[i >> 3] & (1u << (i & 7));
}

void add(uint32_t id){
  uint32_t h1 = hash1(id), h2 = hash2(id);
  for(uint32_t i=0;i<7;i++){
    uint32_t idx = (h1 + i * h2) % M_BITS;
    set_bit(idx);
  }
}

bool contains(uint32_t id){
  uint32_t h1 = hash1(id), h2 = hash2(id);
  for(uint32_t i=0;i<7;i++){
    uint32_t idx = (h1 + i * h2) % M_BITS;
    if(!test_bit(idx)) return false;
  }
  return true;
}

Implementation tips for MCU

• Use 32-bit arithmetic; avoid % where possible: if M_BITS is made a power of two (e.g., 4096), replace modulus with bitmasking for speed, but note this may require adjusting m to maintain p < 1%.
• Choose fast hash primitives available in HW (CRC32) as one of the hashes; ensure h2 is odd to avoid cycles.
• Pre-warm or cache hashes if repeated queries for same id occur.

Trade-offs

• Using full 8 KB would reduce p drastically but increase k (optimal k grows with m/n); double-hashing keeps cost bounded.
• Power-of-two m simplifies index math but may increase p for fixed k; recompute k accordingly.

Situation & goal
I need a reproducible checklist to isolate intermittent SPI bytes arriving with 1–2 bit shifts. I’d proceed top-down: confirm protocol settings, reproduce with stable stimuli, then separate hardware from software causes.

Quick reproduce

• Use an MCU loopback or another master (logic analyzer or FPGA) to replay known patterns.
• Test patterns: 0xFF, 0x00, 0xAA (10101010), 0x55 (01010101), incremental bytes (0x00..0xFF), long PRBS stream.

Protocol & config checks (software)

• Verify CPOL/CPHA match on master and slave; toggle modes to see when errors disappear.
• Confirm bit order (MSB/LSB first) consistent across drivers and HW registers.
• Check SPI clock frequency setting vs slave capability; try slower clock to see if shifts stop.
• Verify peripheral frame size (8/16/32-bit) and that software reads align to frame boundaries.
• Examine FIFO/DMA alignment: ensure DMA transfers use correct burst/word sizes; add padding if needed; disable FIFO/DMA to see difference.
• Inspect interrupt timing and ISR routines — avoid race conditions where reads occur mid-transfer.

Hardware checks

• Use a high-speed scope/logic analyzer to capture SCLK/MOSI/MISO/CS simultaneously; align samples to CS.
• Look for clock jitter, duty-cycle distortion, or missing/extra edges causing bit slip.
• Confirm CS (chip select) timing: assert/deassert only outside active clocking.
• Verify signal integrity: ringing, reflections — add series terminators, pull-ups/downs as appropriate.
• Grounding and power: check common ground between devices, decoupling caps, and supply noise during transfers.
• Check wiring length, connectors, and probe loading. Swap cables/devices.

Isolation steps

1. Reproduce with master and slave on same board (short traces) to rule out cabling.
2. Use known-good master (logic analyzer/FPGA) to drive slave; if issue persists, suspect slave HW/firmware.
3. If only with DMA/FIFO enabled, step through alignment and word-size settings; add buffer alignment or use circular DMA.
4. If scope shows clock edge anomalies, investigate clock source, oscillator stability, or MCU clock domain crossing.

Mitigations

• Enforce CS active for at least one extra clock before/after transfer.
• Use proper DMA alignment, read remaining bytes in ISR if FIFO not full.
• Add hardware filtering/Schmitt triggers or series resistors to clean edges.
• Lower SPI clock or use synchronous clock from same domain.

Verification

• Run long-duration PRBS test, log CRCs, and capture failing frames with analyzer. Fix is validated when PRBS no longer shows shifted bits under same stress conditions.

Implementation (bit-at-a-time)

#include <stdint.h>

/* CRC-8 (poly 0x07) bit-at-a-time update */
uint8_t crc8_update(uint8_t crc, uint8_t data)
{
    crc ^= data;
    for (int i = 0; i < 8; ++i) {
        /* if MSB set, shift left and xor poly; else just shift */
        if (crc & 0x80) {
            crc = (crc << 1) ^ 0x07;
        } else {
            crc <<= 1;
        }
    }
    return crc;
}

Note: This treats CRC register MSB-first. If your protocol uses reflected input/output, reflect bits or process LSB-first and use poly 0x8C.

Converting to table-driven

• Precompute 256-entry table: for byte b, table[b] = crc8_update(0, b).
• Then update with: crc = table[crc ^ data];
• For multi-byte blocks, loop: crc = table[crc ^ buffer[i]];

Memory vs CPU trade-offs (small MCUs)

• Table-driven: fast (one XOR + table read), minimal CPU cycles per byte, but uses 256 bytes ROM (can be reduced to 16 entries with nibble table).
• Bit-at-a-time: tiny code/ROM, zero data table, deterministic small memory footprint, but ~8× slower and more branch/shift ops.
• Choose table if throughput/latency matters and flash/RAM allows. Use nibble table or compress table if memory constrained. For ultra-constrained or when code size matters, use bit method or optimize in assembly.

Overview — semantics & common embedded use-cases

• &: bitwise AND — mask bits, test flags.
• |: bitwise OR — set bits.
• ^: bitwise XOR — toggle bits, parity.
• ~: bitwise NOT — invert bits (useful for creating masks).
• <<, >>: shifts — multiply/divide by powers of two, align fields, extract bitfields.

Examples (32-bit unsigned)

• AND (mask/test)

uint32_t x = 0xA5A5A5A5u;
uint32_t masked = x & 0xFFu; // keeps low 8 bits

• OR (set)

uint32_t flags = 0u;
flags |= (1u << 3); // set bit 3

• XOR (toggle)

uint32_t v = 0xF0u;
v ^= 0x0Fu; // toggles low 4 bits

• NOT (invert)

uint32_t m = 0x0000FFFFu;
uint32_t inv = ~m; // 0xFFFF0000

• Left shift

uint32_t a = 1u << 16; // 0x00010000

• Right shift

uint32_t b = 0x80000000u >> 31; // 1u (logical right shift for unsigned)

Signed vs unsigned behavior

• Shifts: for unsigned, >> is logical (fills with 0). For signed, >> is implementation-defined but usually arithmetic (sign-extends). Left shifting a signed value that overflows is undefined.
• Bitwise ops (&,|,^,~): operate on bit representations; when mixing signed/unsigned, integer promotions and conversions occur — often convert to unsigned which affects result.

Logical (&&, ||) vs Bitwise

• && and || operate on boolean truth of entire operands, short-circuit, return 0 or 1.
• & and | operate per-bit, no short-circuit, return bit-patterns.

Common embedded pitfalls

• Shifting by >= width (e.g., 32) is undefined — avoid or guard.
• Operator precedence: << and >> bind tighter than &, but lower than +; use parentheses for clarity.
• Mixing signedness: unintended unsigned promotions can break comparisons/loops and cause large values; prefer explicit casts and use unsigned for bit ops.
• Left-shifting into sign bit of signed types => undefined; use unsigned types for shifts and masks.

Use these rules to write predictable, portable low-level code.