Bitslicing

Bitslicing is a software technique for implementing algorithms by exploiting bit-level parallelism within a computer word. In a bitsliced representation, the i-th bit of many independent data blocks is stored together in a single word as a bitplane or slice. Operations on the algorithm are then performed exclusively with bitwise logic (AND, OR, XOR, NOT) across these slices, effectively executing many block operations in parallel.

Unlike conventional implementations that operate on bytes or words across blocks, bitslicing rearranges data so that the same boolean function is applied to all blocks simultaneously. The nonlinear components, such as S-boxes in block ciphers, are realized as networks of boolean operations rather than table lookups; this can improve performance on processors with fast bitwise ops and can aid constant-time execution.

Bitslicing emerged in the hardware/software design and cryptography communities in the late 20th century and was popularized for software cryptography. It has been used to implement DES, AES, PRESENT, and other ciphers, as well as for cryptanalytic experiments. On modern CPUs, bitsliced implementations can outperform traditional table-based approaches for certain data sizes and architectures.

Advantages include high data parallelism with simple instruction sets, better cache locality, and potential resistance to timing side channels. Disadvantages include substantial reimplementation effort, complexity in scaling to large data sizes, and architecture-dependent performance.

Bitslicing is complementary to SIMD; it targets bit-level parallelism rather than vector lanes, and often requires bespoke code paths or compilers. It remains a topic of niche high-performance cryptography software and academic research.