# Bitsliced SipHash

DevFeed: [Bitsliced SipHash](<https://devfeed.tech/articles/bitsliced-siphash-38922.md>)

Original publisher: [Read original article](<https://idea.popcount.org/2013-01-30-bitsliced-siphash>)

Author: Marek

Published: 2013-01-29T23:00:00Z

Content type: article

Language: en

Sources: [Marek Majkowski](<https://devfeed.tech/sources/marek-majkowski.md>)

Topics: [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [vectorization techniques](<https://devfeed.tech/topics/vectorization-techniques.md>), [Parallelism](<https://devfeed.tech/topics/parallelism.md>), [Tutorial](<https://devfeed.tech/topics/tutorial.md>), [Python](<https://devfeed.tech/topics/python.md>)

Tags: [64-bit](<https://devfeed.tech/tags/64-bit.md>), [addition](<https://devfeed.tech/tags/addition.md>), [algorithm](<https://devfeed.tech/tags/algorithm.md>), [assembler](<https://devfeed.tech/tags/assembler.md>), [avx](<https://devfeed.tech/tags/avx.md>), [bits](<https://devfeed.tech/tags/bits.md>), [c](<https://devfeed.tech/tags/c.md>), [clang](<https://devfeed.tech/tags/clang.md>), [compiler](<https://devfeed.tech/tags/compiler.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [cpu](<https://devfeed.tech/tags/cpu.md>), [crypto](<https://devfeed.tech/tags/crypto.md>), [cycles](<https://devfeed.tech/tags/cycles.md>), [gcc](<https://devfeed.tech/tags/gcc.md>), [implementation](<https://devfeed.tech/tags/implementation.md>), [parallel](<https://devfeed.tech/tags/parallel.md>), [python](<https://devfeed.tech/tags/python.md>), [siphash](<https://devfeed.tech/tags/siphash.md>)

## AI overview

The bitsliced SipHash implementation processes 256 hashes in parallel by storing each bit position in 256-bit vectors and expressing addition with bitwise carry logic. This reduces the described half-round's operation count from 1,792 to 768 operations for 256 inputs. In the author's i7 measurements, however, the bitsliced computation took 11,278 cycles versus 9,768 for the normal implementation; input/output transposition added another 13,900 cycles. The author attributes the slowdown to transposition cost and the 16 KiB internal state, which may not fit in CPU registers, and notes the transposition code was not optimized. Handwritten assembly and cheaper transposition are suggested as possible avenues for improvement.

## Source excerpt

Bitsliced SipHash Few days ago I presented a Python and a C implementation of SipHash. This time for no reason whatsoever I implemented a bitsliced version of it. Bitslicing a crypto algorithm is usually done to speed it up when doing massively parallel operations. For example when trying to find a collision with brute force. Bitsliced implementation is only useful if you have a large number of exactly the same mathematical operations to be computed in parallel.