1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright(c) 2017 Cavium, Inc 3 * Copyright(c) Hannes Frederic Sowa 4 * All rights reserved. 5 */ 6 7 #include <stdio.h> 8 #include <stdint.h> 9 10 #include <rte_common.h> 11 #include <rte_bitops.h> 12 13 #include "rte_reciprocal.h" 14 15 struct rte_reciprocal rte_reciprocal_value(uint32_t d) 16 { 17 struct rte_reciprocal R; 18 uint64_t m; 19 int l; 20 21 l = rte_fls_u32(d - 1); 22 m = ((1ULL << 32) * ((1ULL << l) - d)); 23 m /= d; 24 25 ++m; 26 R.m = m; 27 R.sh1 = RTE_MIN(l, 1); 28 R.sh2 = RTE_MAX(l - 1, 0); 29 30 return R; 31 } 32 33 /* 34 * Code taken from Hacker's Delight: 35 * http://www.hackersdelight.org/hdcodetxt/divlu.c.txt 36 * License permits inclusion here per: 37 * http://www.hackersdelight.org/permissions.htm 38 */ 39 static uint64_t 40 divide_128_div_64_to_64(uint64_t u1, uint64_t u0, uint64_t v, uint64_t *r) 41 { 42 const uint64_t b = (1ULL << 32); /* Number base (16 bits). */ 43 uint64_t un1, un0, /* Norm. dividend LSD's. */ 44 vn1, vn0, /* Norm. divisor digits. */ 45 q1, q0, /* Quotient digits. */ 46 un64, un21, un10, /* Dividend digit pairs. */ 47 rhat; /* A remainder. */ 48 int s; /* Shift amount for norm. */ 49 50 /* If overflow, set rem. to an impossible value. */ 51 if (u1 >= v) { 52 if (r != NULL) 53 *r = (uint64_t) -1; 54 return (uint64_t) -1; 55 } 56 57 /* Count leading zeros. */ 58 s = __builtin_clzll(v); 59 if (s > 0) { 60 v = v << s; 61 un64 = (u1 << s) | ((u0 >> (64 - s)) & (-s >> 31)); 62 un10 = u0 << s; 63 } else { 64 65 un64 = u1 | u0; 66 un10 = u0; 67 } 68 69 vn1 = v >> 32; 70 vn0 = v & 0xFFFFFFFF; 71 72 un1 = un10 >> 32; 73 un0 = un10 & 0xFFFFFFFF; 74 75 q1 = un64/vn1; 76 rhat = un64 - q1*vn1; 77 again1: 78 if (q1 >= b || q1*vn0 > b*rhat + un1) { 79 q1 = q1 - 1; 80 rhat = rhat + vn1; 81 if (rhat < b) 82 goto again1; 83 } 84 85 un21 = un64*b + un1 - q1*v; 86 87 q0 = un21/vn1; 88 rhat = un21 - q0*vn1; 89 again2: 90 if (q0 >= b || q0*vn0 > b*rhat + un0) { 91 q0 = q0 - 1; 92 rhat = rhat + vn1; 93 if (rhat < b) 94 goto again2; 95 } 96 97 if (r != NULL) 98 *r = (un21*b + un0 - q0*v) >> s; 99 return q1*b + q0; 100 } 101 102 struct rte_reciprocal_u64 103 rte_reciprocal_value_u64(uint64_t d) 104 { 105 struct rte_reciprocal_u64 R; 106 uint64_t m; 107 uint64_t r; 108 int l; 109 110 l = 63 - __builtin_clzll(d); 111 112 m = divide_128_div_64_to_64((1ULL << l), 0, d, &r) << 1; 113 if (r << 1 < r || r << 1 >= d) 114 m++; 115 m = (1ULL << l) - d ? m + 1 : 1; 116 R.m = m; 117 118 R.sh1 = l > 1 ? 1 : l; 119 R.sh2 = (l > 0) ? l : 0; 120 R.sh2 -= R.sh2 && (m == 1) ? 1 : 0; 121 122 return R; 123 } 124