]>
Commit | Line | Data |
---|---|---|
11fdf7f2 TL |
1 | /* SPDX-License-Identifier: BSD-3-Clause |
2 | * Copyright(c) 2017 Cavium, Inc | |
3 | */ | |
7c673cae FG |
4 | /*- |
5 | * BSD LICENSE | |
6 | * | |
7 | * Copyright(c) Hannes Frederic Sowa | |
8 | * All rights reserved. | |
9 | * | |
10 | * Redistribution and use in source and binary forms, with or without | |
11 | * modification, are permitted provided that the following conditions | |
12 | * are met: | |
13 | * | |
14 | * * Redistributions of source code must retain the above copyright | |
15 | * notice, this list of conditions and the following disclaimer. | |
16 | * * Redistributions in binary form must reproduce the above copyright | |
17 | * notice, this list of conditions and the following disclaimer in | |
18 | * the documentation and/or other materials provided with the | |
19 | * distribution. | |
20 | * * Neither the name of Intel Corporation nor the names of its | |
21 | * contributors may be used to endorse or promote products derived | |
22 | * from this software without specific prior written permission. | |
23 | * | |
24 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
25 | * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
26 | * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
27 | * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
28 | * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
29 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
30 | * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
31 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
32 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
33 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
34 | * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
35 | */ | |
36 | ||
37 | #include <stdio.h> | |
38 | #include <stdint.h> | |
39 | ||
40 | #include <rte_common.h> | |
41 | ||
42 | #include "rte_reciprocal.h" | |
43 | ||
7c673cae FG |
44 | struct rte_reciprocal rte_reciprocal_value(uint32_t d) |
45 | { | |
46 | struct rte_reciprocal R; | |
47 | uint64_t m; | |
48 | int l; | |
49 | ||
9f95a23c | 50 | l = rte_fls_u32(d - 1); |
7c673cae FG |
51 | m = ((1ULL << 32) * ((1ULL << l) - d)); |
52 | m /= d; | |
53 | ||
54 | ++m; | |
55 | R.m = m; | |
56 | R.sh1 = RTE_MIN(l, 1); | |
57 | R.sh2 = RTE_MAX(l - 1, 0); | |
58 | ||
59 | return R; | |
60 | } | |
11fdf7f2 TL |
61 | |
62 | /* | |
63 | * Code taken from Hacker's Delight: | |
64 | * http://www.hackersdelight.org/hdcodetxt/divlu.c.txt | |
65 | * License permits inclusion here per: | |
66 | * http://www.hackersdelight.org/permissions.htm | |
67 | */ | |
68 | static uint64_t | |
69 | divide_128_div_64_to_64(uint64_t u1, uint64_t u0, uint64_t v, uint64_t *r) | |
70 | { | |
71 | const uint64_t b = (1ULL << 32); /* Number base (16 bits). */ | |
72 | uint64_t un1, un0, /* Norm. dividend LSD's. */ | |
73 | vn1, vn0, /* Norm. divisor digits. */ | |
74 | q1, q0, /* Quotient digits. */ | |
75 | un64, un21, un10, /* Dividend digit pairs. */ | |
76 | rhat; /* A remainder. */ | |
77 | int s; /* Shift amount for norm. */ | |
78 | ||
79 | /* If overflow, set rem. to an impossible value. */ | |
80 | if (u1 >= v) { | |
81 | if (r != NULL) | |
82 | *r = (uint64_t) -1; | |
83 | return (uint64_t) -1; | |
84 | } | |
85 | ||
86 | /* Count leading zeros. */ | |
87 | s = __builtin_clzll(v); | |
88 | if (s > 0) { | |
89 | v = v << s; | |
90 | un64 = (u1 << s) | ((u0 >> (64 - s)) & (-s >> 31)); | |
91 | un10 = u0 << s; | |
92 | } else { | |
93 | ||
94 | un64 = u1 | u0; | |
95 | un10 = u0; | |
96 | } | |
97 | ||
98 | vn1 = v >> 32; | |
99 | vn0 = v & 0xFFFFFFFF; | |
100 | ||
101 | un1 = un10 >> 32; | |
102 | un0 = un10 & 0xFFFFFFFF; | |
103 | ||
104 | q1 = un64/vn1; | |
105 | rhat = un64 - q1*vn1; | |
106 | again1: | |
107 | if (q1 >= b || q1*vn0 > b*rhat + un1) { | |
108 | q1 = q1 - 1; | |
109 | rhat = rhat + vn1; | |
110 | if (rhat < b) | |
111 | goto again1; | |
112 | } | |
113 | ||
114 | un21 = un64*b + un1 - q1*v; | |
115 | ||
116 | q0 = un21/vn1; | |
117 | rhat = un21 - q0*vn1; | |
118 | again2: | |
119 | if (q0 >= b || q0*vn0 > b*rhat + un0) { | |
120 | q0 = q0 - 1; | |
121 | rhat = rhat + vn1; | |
122 | if (rhat < b) | |
123 | goto again2; | |
124 | } | |
125 | ||
126 | if (r != NULL) | |
127 | *r = (un21*b + un0 - q0*v) >> s; | |
128 | return q1*b + q0; | |
129 | } | |
130 | ||
131 | struct rte_reciprocal_u64 | |
132 | rte_reciprocal_value_u64(uint64_t d) | |
133 | { | |
134 | struct rte_reciprocal_u64 R; | |
135 | uint64_t m; | |
136 | int l; | |
137 | ||
138 | l = 63 - __builtin_clzll(d); | |
139 | ||
140 | m = divide_128_div_64_to_64((1ULL << l), 0, d, NULL) << 1; | |
141 | m = (1ULL << l) - d ? m + 2 : 1; | |
142 | R.m = m; | |
143 | ||
144 | R.sh1 = l > 1 ? 1 : l; | |
145 | R.sh2 = (l > 0) ? l : 0; | |
146 | R.sh2 -= R.sh2 && (m == 1) ? 1 : 0; | |
147 | ||
148 | return R; | |
149 | } |