linux-toradex.git/arch/parisc/include/asm/hash.h, branch v4.10 Linux kernel for Apalis and Colibri modules parisc: Add <asm/hash.h> 2016-08-02T14:44:29+00:00 George Spelvin linux@sciencehorizons.net 2016-06-07T23:45:06+00:00 773e1c5fa4bf1faa25e119490b26ece2ef1bdb46 PA-RISC is interesting; integer multiplies are implemented in the FPU, so are painful in the kernel. But it tries to be friendly to shift-and-add sequences for constant multiplies. __hash_32 is implemented using the same shift-and-add sequence as Microblaze, just scheduled for the PA7100. (It's 2-way superscalar but in-order, like the Pentium.) hash_64 was tricky, but a suggestion from Jason Thong allowed a good solution by breaking up the multiplier. After a lot of manual optimization, I found a 19-instruction sequence for the multiply that can be executed in 10 cycles using only 4 temporaries. (The PA8xxx can issue 4 instructions per cycle, but 2 must be ALU ops and 2 must be loads/stores. And the final add can't be paired.) An alternative considered, but ultimately not used, was Thomas Wang's 64-to-32-bit integer hash. At 12 instructions, it's smaller, but they're all sequentially dependent, so it has longer latency. https://web.archive.org/web/2011/http://www.concentric.net/~Ttwang/tech/inthash.htm http://burtleburtle.net/bob/hash/integer.html Signed-off-by: George Spelvin <linux@sciencehorizons.net> Cc: Helge Deller <deller@gmx.de> Cc: linux-parisc@vger.kernel.org Signed-off-by: Helge Deller <deller@gmx.de> 
PA-RISC is interesting; integer multiplies are implemented in the
FPU, so are painful in the kernel.  But it tries to be friendly to
shift-and-add sequences for constant multiplies.

__hash_32 is implemented using the same shift-and-add sequence as
Microblaze, just scheduled for the PA7100.  (It's 2-way superscalar
but in-order, like the Pentium.)

hash_64 was tricky, but a suggestion from Jason Thong allowed a
good solution by breaking up the multiplier.  After a lot of manual
optimization, I found a 19-instruction sequence for the multiply that
can be executed in 10 cycles using only 4 temporaries.

(The PA8xxx can issue 4 instructions per cycle, but 2 must be ALU ops
and 2 must be loads/stores.  And the final add can't be paired.)

An alternative considered, but ultimately not used, was Thomas Wang's
64-to-32-bit integer hash.  At 12 instructions, it's smaller, but they're
all sequentially dependent, so it has longer latency.

https://web.archive.org/web/2011/http://www.concentric.net/~Ttwang/tech/inthash.htm
http://burtleburtle.net/bob/hash/integer.html

Signed-off-by: George Spelvin <linux@sciencehorizons.net>
Cc: Helge Deller <deller@gmx.de>
Cc: linux-parisc@vger.kernel.org
Signed-off-by: Helge Deller <deller@gmx.de>