1 /* SPDX-License-Identifier: GPL-2.0 */
2 #ifndef _ASM_HASH_H
3 #define _ASM_HASH_H
4
5 /*
6 * Fortunately, most people who want to run Linux on Microblaze enable
7 * both multiplier and barrel shifter, but omitting them is technically
8 * a supported configuration.
9 *
10 * With just a barrel shifter, we can implement an efficient constant
11 * multiply using shifts and adds. GCC can find a 9-step solution, but
12 * this 6-step solution was found by Yevgen Voronenko's implementation
13 * of the Hcub algorithm at http://spiral.ece.cmu.edu/mcm/gen.html.
14 *
15 * That software is really not designed for a single multiplier this large,
16 * but if you run it enough times with different seeds, it'll find several
17 * 6-shift, 6-add sequences for computing x * 0x61C88647. They are all
18 * c = (x << 19) + x;
19 * a = (x << 9) + c;
20 * b = (x << 23) + a;
21 * return (a<<11) + (b<<6) + (c<<3) - b;
22 * with variations on the order of the final add.
23 *
24 * Without even a shifter, it's hopless; any hash function will suck.
25 */
26
27 #if CONFIG_XILINX_MICROBLAZE0_USE_HW_MUL == 0
28
29 #define HAVE_ARCH__HASH_32 1
30
31 /* Multiply by GOLDEN_RATIO_32 = 0x61C88647 */
32 static inline u32 __attribute_const__ __hash_32(u32 a)
33 {
34 #if CONFIG_XILINX_MICROBLAZE0_USE_BARREL
35 unsigned int b, c;
36
37 /* Phase 1: Compute three intermediate values */
38 b = a << 23;
39 c = (a << 19) + a;
40 a = (a << 9) + c;
41 b += a;
42
43 /* Phase 2: Compute (a << 11) + (b << 6) + (c << 3) - b */
44 a <<= 5;
45 a += b; /* (a << 5) + b */
46 a <<= 3;
47 a += c; /* (a << 8) + (b << 3) + c */
48 a <<= 3;
49 return a - b; /* (a << 11) + (b << 6) + (c << 3) - b */
50 #else
51 /*
52 * "This is really going to hurt."
53 *
54 * Without a barrel shifter, left shifts are implemented as
55 * repeated additions, and the best we can do is an optimal
56 * addition-subtraction chain. This one is not known to be
57 * optimal, but at 37 steps, it's decent for a 31-bit multiplier.
58 *
59 * Question: given its size (37*4 = 148 bytes per instance),
60 * and slowness, is this worth having inline?
61 */
62 unsigned int b, c, d;
63
64 b = a << 4; /* 4 */
65 c = b << 1; /* 1 5 */
66 b += a; /* 1 6 */
67 c += b; /* 1 7 */
68 c <<= 3; /* 3 10 */
69 c -= a; /* 1 11 */
70 d = c << 7; /* 7 18 */
71 d += b; /* 1 19 */
72 d <<= 8; /* 8 27 */
73 d += a; /* 1 28 */
74 d <<= 1; /* 1 29 */
75 d += b; /* 1 30 */
76 d <<= 6; /* 6 36 */
77 return d + c; /* 1 37 total instructions*/
78 #endif
79 }
80
81 #endif /* !CONFIG_XILINX_MICROBLAZE0_USE_HW_MUL */
82 #endif /* _ASM_HASH_H */
83
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.