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