[Cake] an experiment with an alternate hasher

[Jonathan Morton]

> On 26 Mar, 2017, at 19:00, Dave Taht <dave.taht at gmail.com> wrote:
> 
> popcount is, regrettably, an sse4.2-only instruction

A read through the ARM ISA Quick Reference Card:

http://infocenter.arm.com/help/topic/com.arm.doc.qrc0001m/QRC0001_UAL.pdf

…shows that there is no equivalent instruction on ARM CPUs at least up to ARMv7, which I think covers all current-generation consumer-grade routers.

However, the operation can be constructed using log2(N) operations on any modern CPU as a sequence of masks, shifts and adds.  GCC has a “builtin” intrinsic function to use a popcnt instruction where present, and this algorithm otherwise.

Obviously this will only be of any use if the resulting hash is of good quality.  An obvious problem with popcnt is that inputs of 1, 2, 4, 8, etc have the same popcnt (1), and it is trivial for an attacker to exploit this property.

 - Jonathan Morton