SWAR: Parallel Byte Operations in 64-Bit Registers

This article provides an overview of SWAR (SIMD Within A Register), detailing how standard 64-bit integer registers and binary bitwise instructions process eight 8-bit bytes simultaneously. By partitioning integer registers, applying bitmasks, and managing arithmetic carry propagation, developers can achieve data-level parallelism on general-purpose processor hardware without relying on dedicated vector extensions like AVX or NEON.

Register Layout and Data Partitioning

In a 64-bit computing architecture, a general-purpose register stores a single 64-bit integer spanning bits 0 to 63. Under the SWAR approach, this single register is logically partitioned into eight contiguous 8-bit lanes (bytes):

[ Byte 7 ][ Byte 6 ][ Byte 5 ][ Byte 4 ][ Byte 3 ][ Byte 2 ][ Byte 1 ][ Byte 0 ]
63     56 55     48 47     40 39     32 31     24 23     16 15      8 7       0

By treating each 8-bit segment as an independent lane, standard 64-bit ALU operations can manipulate all eight bytes in a single clock cycle.

Parallel Bitwise Operations

Bitwise operations—such as AND, OR, XOR, and NOT—are inherently parallel. Because bitwise operations process each bit position independently with no interaction between neighboring bits, performing a 64-bit bitwise operation naturally executes the exact operation across all eight 8-bit lanes simultaneously:

• Parallel Inversion: ~R inverts all eight bytes in parallel.
• Parallel Masking: R & Mask isolates specific bits in all eight bytes.
• Parallel XOR: A ^ B computes the bitwise difference across eight pairs of bytes without any lane interference.

Preventing Carry Bleed in Parallel Addition

The primary challenge in SWAR arithmetic is the carry chain in the binary number system. During a standard 64-bit addition (A + B), an overflow in bit 7 of Byte 0 will carry into bit 8 of Byte 1, corrupting the adjacent lane. This unintended interaction is known as “carry bleed.”

To prevent carry bleed during 8-bit parallel additions, the arithmetic isolates the most significant bit (MSB) of each byte lane using predefined 64-bit constants:

• Low-bit Mask (\(M_L\)): 0x7F7F7F7F7F7F7F7F (clears the 7th bit of every byte)
• High-bit Mask (\(M_H\)): 0x8080808080808080 (isolates the 7th bit of every byte)

Parallel addition without cross-lane corruption is computed using the following binary algorithm:

\[\text{Result} = ((A \ \& \ M_L) + (B \ \& \ M_L)) \oplus ((A \oplus B) \ \& \ M_H)\]

1. Low-Bit Addition: Masking out the MSB with \(M_L\) guarantees that the addition of the lower 7 bits cannot overflow past bit 6, preventing any carry into the next byte.
2. High-Bit Computation: The MSB for each byte is calculated separately using XOR logic and added to the carry generated from the lower 7 bits.

Zero-Byte Detection (Alan Mycroft’s Algorithm)

A prominent application of SWAR is identifying whether any of the eight bytes in a 64-bit register equal zero (0x00), which is critical for operations like string length calculation (strlen).

A zero byte can be identified across all lanes simultaneously using the classic SWAR expression:

\[\text{HasZero} = (V - 0\text{x}0101010101010101) \ \& \ \sim V \ \& \ 0\text{x}8080808080808080\]

The binary mechanics function as follows: * Borrow Generation: Subtracting 0x01 from a byte that contains 0x00 forces an underflow, setting its MSB (bit 7) to 1. * Original State Inversion: ~V ensures that bytes that already had their MSB set (values 0x80 to 0xFF) are ignored. * Isolation: The mask 0x8080808080808080 eliminates all non-MSB bits, leaving only the indicator bits.

If the resulting 64-bit value is non-zero, at least one of the 8-bit lanes contains a null byte. The specific index of the zero byte can then be determined using a Count Trailing Zeros (CTZ) or leading zero instruction.

Broadcast and Pattern Matching Operations

SWAR utilizes integer multiplication to broadcast values across lanes. Multiplying an 8-bit scalar by the constant 0x0101010101010101 replicates that byte across all eight positions in a 64-bit register:

\[\text{Byte } B \times 0\text{x}0101010101010101 = [B][B][B][B][B][B][B][B]\]

To search a 64-bit word for a specific target character \(C\): 1. Broadcast \(C\) across a register: \(T = C \times 0\text{x}0101010101010101\). 2. XOR the target register with the input data: \(X = \text{Data} \oplus T\). 3. Perform zero-byte detection on \(X\). Matches in the original data turn into 0x00 after the XOR, allowing the zero-detection algorithm to flag the exact byte positions matching character \(C\).