Branch data     Line data    Source code

       1                 :            : /* SPDX-License-Identifier: BSD-3-Clause
       2                 :            :  * Copyright(c) 2017 Cavium, Inc
       3                 :            :  */
       4                 :            : /*
       5                 :            :  * Reciprocal divide
       6                 :            :  *
       7                 :            :  * Used with permission from original authors
       8                 :            :  *  Hannes Frederic Sowa and Daniel Borkmann
       9                 :            :  *
      10                 :            :  * This algorithm is based on the paper "Division by Invariant
      11                 :            :  * Integers Using Multiplication" by Torbjörn Granlund and Peter
      12                 :            :  * L. Montgomery.
      13                 :            :  *
      14                 :            :  * The assembler implementation from Agner Fog, which this code is
      15                 :            :  * based on, can be found here:
      16                 :            :  * http://www.agner.org/optimize/asmlib.zip
      17                 :            :  *
      18                 :            :  * This optimization for A/B is helpful if the divisor B is mostly
      19                 :            :  * runtime invariant. The reciprocal of B is calculated in the
      20                 :            :  * slow-path with reciprocal_value(). The fast-path can then just use
      21                 :            :  * a much faster multiplication operation with a variable dividend A
      22                 :            :  * to calculate the division A/B.
      23                 :            :  */
      24                 :            : 
      25                 :            : #ifndef _RTE_RECIPROCAL_H_
      26                 :            : #define _RTE_RECIPROCAL_H_
      27                 :            : 
      28                 :            : #include <stdint.h>
      29                 :            : 
      30                 :            : #include <rte_common.h>
      31                 :            : 
      32                 :            : #ifdef __cplusplus
      33                 :            : extern "C" {
      34                 :            : #endif
      35                 :            : 
      36                 :            : struct rte_reciprocal {
      37                 :            :         uint32_t m;
      38                 :            :         uint8_t sh1, sh2;
      39                 :            : };
      40                 :            : 
      41                 :            : struct rte_reciprocal_u64 {
      42                 :            :         uint64_t m;
      43                 :            :         uint8_t sh1, sh2;
      44                 :            : };
      45                 :            : 
      46                 :            : static inline uint32_t rte_reciprocal_divide(uint32_t a, struct rte_reciprocal R)
      47                 :            : {
      48                 :          1 :         uint32_t t = (uint32_t)(((uint64_t)a * R.m) >> 32);
      49                 :            : 
      50   [ +  -  #  # ]:          1 :         return (t + ((a - t) >> R.sh1)) >> R.sh2;
      51                 :            : }
      52                 :            : 
      53                 :            : static __rte_always_inline uint64_t
      54                 :            : mullhi_u64(uint64_t x, uint64_t y)
      55                 :            : {
      56                 :            : #ifdef __SIZEOF_INT128__
      57                 :          0 :         __uint128_t xl = x;
      58                 :          0 :         __uint128_t rl = xl * y;
      59                 :            : 
      60                 :          0 :         return (rl >> 64);
      61                 :            : #else
      62                 :            :         uint64_t u0, u1, v0, v1, k, t;
      63                 :            :         uint64_t w1, w2;
      64                 :            :         uint64_t whi;
      65                 :            : 
      66                 :            :         u1 = x >> 32; u0 = x & 0xFFFFFFFF;
      67                 :            :         v1 = y >> 32; v0 = y & 0xFFFFFFFF;
      68                 :            : 
      69                 :            :         t = u0*v0;
      70                 :            :         k = t >> 32;
      71                 :            : 
      72                 :            :         t = u1*v0 + k;
      73                 :            :         w1 = t & 0xFFFFFFFF;
      74                 :            :         w2 = t >> 32;
      75                 :            : 
      76                 :            :         t = u0*v1 + w1;
      77                 :            :         k = t >> 32;
      78                 :            : 
      79                 :            :         whi = u1*v1 + w2 + k;
      80                 :            : 
      81                 :            :         return whi;
      82                 :            : #endif
      83                 :            : }
      84                 :            : 
      85                 :            : static __rte_always_inline uint64_t
      86                 :            : rte_reciprocal_divide_u64(uint64_t a, const struct rte_reciprocal_u64 *R)
      87                 :            : {
      88                 :          0 :         uint64_t t = mullhi_u64(a, R->m);
      89                 :            : 
      90   [ #  #  #  #  :          0 :         return (t + ((a - t) >> R->sh1)) >> R->sh2;
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                   #  # ]
      91                 :            : }
      92                 :            : 
      93                 :            : struct rte_reciprocal rte_reciprocal_value(uint32_t d);
      94                 :            : struct rte_reciprocal_u64 rte_reciprocal_value_u64(uint64_t d);
      95                 :            : 
      96                 :            : #ifdef __cplusplus
      97                 :            : }
      98                 :            : #endif
      99                 :            : 
     100                 :            : #endif /* _RTE_RECIPROCAL_H_ */