Branch data     Line data    Source code

       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                 :          1 : struct rte_reciprocal rte_reciprocal_value(uint32_t d)
      16                 :            : {
      17                 :            :         struct rte_reciprocal R;
      18                 :            :         uint64_t m;
      19                 :            :         int l;
      20                 :            : 
      21         [ +  - ]:          1 :         l = rte_fls_u32(d - 1);
      22                 :          1 :         m = ((1ULL << 32) * ((1ULL << l) - d));
      23                 :          1 :         m /= d;
      24                 :            : 
      25                 :          1 :         ++m;
      26                 :          1 :         R.m = m;
      27                 :          1 :         R.sh1 = RTE_MIN(l, 1);
      28                 :          1 :         R.sh2 = RTE_MAX(l - 1, 0);
      29                 :            : 
      30                 :          1 :         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                 :          0 : 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         [ #  # ]:          0 :         if (u1 >= v) {
      52         [ #  # ]:          0 :                 if (r != NULL)
      53                 :          0 :                         *r = (uint64_t) -1;
      54                 :          0 :                 return (uint64_t) -1;
      55                 :            :         }
      56                 :            : 
      57                 :            :         /* Count leading zeros. */
      58                 :            :         s = rte_clz64(v);
      59         [ #  # ]:          0 :         if (s > 0) {
      60                 :          0 :                 v = v << s;
      61                 :          0 :                 un64 = (u1 << s) | ((u0 >> (64 - s)) & (-s >> 31));
      62                 :          0 :                 un10 = u0 << s;
      63                 :            :         } else {
      64                 :            : 
      65                 :          0 :                 un64 = u1 | u0;
      66                 :            :                 un10 = u0;
      67                 :            :         }
      68                 :            : 
      69                 :          0 :         vn1 = v >> 32;
      70                 :          0 :         vn0 = v & 0xFFFFFFFF;
      71                 :            : 
      72                 :          0 :         un1 = un10 >> 32;
      73                 :          0 :         un0 = un10 & 0xFFFFFFFF;
      74                 :            : 
      75                 :          0 :         q1 = un64/vn1;
      76                 :            :         rhat = un64 - q1*vn1;
      77                 :          0 : again1:
      78   [ #  #  #  # ]:          0 :         if (q1 >= b || q1*vn0 > b*rhat + un1) {
      79                 :          0 :                 q1 = q1 - 1;
      80                 :          0 :                 rhat = rhat + vn1;
      81         [ #  # ]:          0 :                 if (rhat < b)
      82                 :          0 :                         goto again1;
      83                 :            :         }
      84                 :            : 
      85                 :          0 :         un21 = un64*b + un1 - q1*v;
      86                 :            : 
      87                 :          0 :         q0 = un21/vn1;
      88                 :            :         rhat = un21 - q0*vn1;
      89                 :          0 : again2:
      90   [ #  #  #  # ]:          0 :         if (q0 >= b || q0*vn0 > b*rhat + un0) {
      91                 :          0 :                 q0 = q0 - 1;
      92                 :          0 :                 rhat = rhat + vn1;
      93         [ #  # ]:          0 :                 if (rhat < b)
      94                 :          0 :                         goto again2;
      95                 :            :         }
      96                 :            : 
      97         [ #  # ]:          0 :         if (r != NULL)
      98                 :          0 :                 *r = (un21*b + un0 - q0*v) >> s;
      99                 :          0 :         return q1*b + q0;
     100                 :            : }
     101                 :            : 
     102                 :            : struct rte_reciprocal_u64
     103                 :          0 : 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                 :          0 :         l = 63 - rte_clz64(d);
     111                 :            : 
     112                 :          0 :         m = divide_128_div_64_to_64((1ULL << l), 0, d, &r) << 1;
     113   [ #  #  #  # ]:          0 :         if (r << 1 < r || r << 1 >= d)
     114                 :          0 :                 m++;
     115         [ #  # ]:          0 :         m = (1ULL << l) - d ? m + 1 : 1;
     116                 :            :         R.m = m;
     117                 :            : 
     118                 :          0 :         R.sh1 = l > 1 ? 1 : l;
     119                 :          0 :         R.sh2 = (l > 0) ? l : 0;
     120   [ #  #  #  # ]:          0 :         R.sh2 -= R.sh2 && (m == 1) ? 1 : 0;
     121                 :            : 
     122                 :          0 :         return R;
     123                 :            : }