Branch data     Line data    Source code

       1                 :            : // SPDX-License-Identifier: GPL-2.0-only
       2                 :            : /* tnum: tracked (or tristate) numbers
       3                 :            :  *
       4                 :            :  * A tnum tracks knowledge about the bits of a value.  Each bit can be either
       5                 :            :  * known (0 or 1), or unknown (x).  Arithmetic operations on tnums will
       6                 :            :  * propagate the unknown bits such that the tnum result represents all the
       7                 :            :  * possible results for possible values of the operands.
       8                 :            :  */
       9                 :            : #include <linux/kernel.h>
      10                 :            : #include <linux/tnum.h>
      11                 :            : 
      12                 :            : #define TNUM(_v, _m)    (struct tnum){.value = _v, .mask = _m}
      13                 :            : /* A completely unknown value */
      14                 :            : const struct tnum tnum_unknown = { .value = 0, .mask = -1 };
      15                 :            : 
      16                 :          3 : struct tnum tnum_const(u64 value)
      17                 :            : {
      18                 :          3 :         return TNUM(value, 0);
      19                 :            : }
      20                 :            : 
      21                 :          3 : struct tnum tnum_range(u64 min, u64 max)
      22                 :            : {
      23                 :          3 :         u64 chi = min ^ max, delta;
      24                 :          3 :         u8 bits = fls64(chi);
      25                 :            : 
      26                 :            :         /* special case, needed because 1ULL << 64 is undefined */
      27                 :          3 :         if (bits > 63)
      28                 :          0 :                 return tnum_unknown;
      29                 :            :         /* e.g. if chi = 4, bits = 3, delta = (1<<3) - 1 = 7.
      30                 :            :          * if chi = 0, bits = 0, delta = (1<<0) - 1 = 0, so we return
      31                 :            :          *  constant min (since min == max).
      32                 :            :          */
      33                 :          3 :         delta = (1ULL << bits) - 1;
      34                 :          3 :         return TNUM(min & ~delta, delta);
      35                 :            : }
      36                 :            : 
      37                 :          0 : struct tnum tnum_lshift(struct tnum a, u8 shift)
      38                 :            : {
      39                 :          0 :         return TNUM(a.value << shift, a.mask << shift);
      40                 :            : }
      41                 :            : 
      42                 :          0 : struct tnum tnum_rshift(struct tnum a, u8 shift)
      43                 :            : {
      44                 :          0 :         return TNUM(a.value >> shift, a.mask >> shift);
      45                 :            : }
      46                 :            : 
      47                 :          0 : struct tnum tnum_arshift(struct tnum a, u8 min_shift, u8 insn_bitness)
      48                 :            : {
      49                 :            :         /* if a.value is negative, arithmetic shifting by minimum shift
      50                 :            :          * will have larger negative offset compared to more shifting.
      51                 :            :          * If a.value is nonnegative, arithmetic shifting by minimum shift
      52                 :            :          * will have larger positive offset compare to more shifting.
      53                 :            :          */
      54                 :          0 :         if (insn_bitness == 32)
      55                 :          0 :                 return TNUM((u32)(((s32)a.value) >> min_shift),
      56                 :            :                             (u32)(((s32)a.mask)  >> min_shift));
      57                 :            :         else
      58                 :          0 :                 return TNUM((s64)a.value >> min_shift,
      59                 :            :                             (s64)a.mask  >> min_shift);
      60                 :            : }
      61                 :            : 
      62                 :          3 : struct tnum tnum_add(struct tnum a, struct tnum b)
      63                 :            : {
      64                 :            :         u64 sm, sv, sigma, chi, mu;
      65                 :            : 
      66                 :          3 :         sm = a.mask + b.mask;
      67                 :          3 :         sv = a.value + b.value;
      68                 :          3 :         sigma = sm + sv;
      69                 :          3 :         chi = sigma ^ sv;
      70                 :          3 :         mu = chi | a.mask | b.mask;
      71                 :          3 :         return TNUM(sv & ~mu, mu);
      72                 :            : }
      73                 :            : 
      74                 :          0 : struct tnum tnum_sub(struct tnum a, struct tnum b)
      75                 :            : {
      76                 :            :         u64 dv, alpha, beta, chi, mu;
      77                 :            : 
      78                 :          0 :         dv = a.value - b.value;
      79                 :          0 :         alpha = dv + a.mask;
      80                 :          0 :         beta = dv - b.mask;
      81                 :          0 :         chi = alpha ^ beta;
      82                 :          0 :         mu = chi | a.mask | b.mask;
      83                 :          0 :         return TNUM(dv & ~mu, mu);
      84                 :            : }
      85                 :            : 
      86                 :          0 : struct tnum tnum_and(struct tnum a, struct tnum b)
      87                 :            : {
      88                 :            :         u64 alpha, beta, v;
      89                 :            : 
      90                 :          0 :         alpha = a.value | a.mask;
      91                 :          0 :         beta = b.value | b.mask;
      92                 :          0 :         v = a.value & b.value;
      93                 :          0 :         return TNUM(v, alpha & beta & ~v);
      94                 :            : }
      95                 :            : 
      96                 :          0 : struct tnum tnum_or(struct tnum a, struct tnum b)
      97                 :            : {
      98                 :            :         u64 v, mu;
      99                 :            : 
     100                 :          0 :         v = a.value | b.value;
     101                 :          0 :         mu = a.mask | b.mask;
     102                 :          0 :         return TNUM(v, mu & ~v);
     103                 :            : }
     104                 :            : 
     105                 :          0 : struct tnum tnum_xor(struct tnum a, struct tnum b)
     106                 :            : {
     107                 :            :         u64 v, mu;
     108                 :            : 
     109                 :          0 :         v = a.value ^ b.value;
     110                 :          0 :         mu = a.mask | b.mask;
     111                 :          0 :         return TNUM(v & ~mu, mu);
     112                 :            : }
     113                 :            : 
     114                 :            : /* half-multiply add: acc += (unknown * mask * value).
     115                 :            :  * An intermediate step in the multiply algorithm.
     116                 :            :  */
     117                 :            : static struct tnum hma(struct tnum acc, u64 value, u64 mask)
     118                 :            : {
     119                 :          0 :         while (mask) {
     120                 :          0 :                 if (mask & 1)
     121                 :            :                         acc = tnum_add(acc, TNUM(0, value));
     122                 :          0 :                 mask >>= 1;
     123                 :          0 :                 value <<= 1;
     124                 :            :         }
     125                 :          0 :         return acc;
     126                 :            : }
     127                 :            : 
     128                 :          0 : struct tnum tnum_mul(struct tnum a, struct tnum b)
     129                 :            : {
     130                 :            :         struct tnum acc;
     131                 :            :         u64 pi;
     132                 :            : 
     133                 :          0 :         pi = a.value * b.value;
     134                 :          0 :         acc = hma(TNUM(pi, 0), a.mask, b.mask | b.value);
     135                 :          0 :         return hma(acc, b.mask, a.value);
     136                 :            : }
     137                 :            : 
     138                 :            : /* Note that if a and b disagree - i.e. one has a 'known 1' where the other has
     139                 :            :  * a 'known 0' - this will return a 'known 1' for that bit.
     140                 :            :  */
     141                 :          3 : struct tnum tnum_intersect(struct tnum a, struct tnum b)
     142                 :            : {
     143                 :            :         u64 v, mu;
     144                 :            : 
     145                 :          3 :         v = a.value | b.value;
     146                 :          3 :         mu = a.mask & b.mask;
     147                 :          3 :         return TNUM(v & ~mu, mu);
     148                 :            : }
     149                 :            : 
     150                 :          3 : struct tnum tnum_cast(struct tnum a, u8 size)
     151                 :            : {
     152                 :          3 :         a.value &= (1ULL << (size * 8)) - 1;
     153                 :          3 :         a.mask &= (1ULL << (size * 8)) - 1;
     154                 :          3 :         return a;
     155                 :            : }
     156                 :            : 
     157                 :          3 : bool tnum_is_aligned(struct tnum a, u64 size)
     158                 :            : {
     159                 :          3 :         if (!size)
     160                 :            :                 return true;
     161                 :          3 :         return !((a.value | a.mask) & (size - 1));
     162                 :            : }
     163                 :            : 
     164                 :          3 : bool tnum_in(struct tnum a, struct tnum b)
     165                 :            : {
     166                 :          3 :         if (b.mask & ~a.mask)
     167                 :            :                 return false;
     168                 :          3 :         b.value &= ~a.mask;
     169                 :          3 :         return a.value == b.value;
     170                 :            : }
     171                 :            : 
     172                 :          0 : int tnum_strn(char *str, size_t size, struct tnum a)
     173                 :            : {
     174                 :          0 :         return snprintf(str, size, "(%#llx; %#llx)", a.value, a.mask);
     175                 :            : }
     176                 :            : EXPORT_SYMBOL_GPL(tnum_strn);
     177                 :            : 
     178                 :          0 : int tnum_sbin(char *str, size_t size, struct tnum a)
     179                 :            : {
     180                 :            :         size_t n;
     181                 :            : 
     182                 :          0 :         for (n = 64; n; n--) {
     183                 :          0 :                 if (n < size) {
     184                 :          0 :                         if (a.mask & 1)
     185                 :          0 :                                 str[n - 1] = 'x';
     186                 :          0 :                         else if (a.value & 1)
     187                 :          0 :                                 str[n - 1] = '1';
     188                 :            :                         else
     189                 :          0 :                                 str[n - 1] = '0';
     190                 :            :                 }
     191                 :          0 :                 a.mask >>= 1;
     192                 :          0 :                 a.value >>= 1;
     193                 :            :         }
     194                 :          0 :         str[min(size - 1, (size_t)64)] = 0;
     195                 :          0 :         return 64;
     196                 :            : }