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