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 struct tnum tnum_const(u64 value) 17 { 18 return TNUM(value, 0); 19 } 20 21 struct tnum tnum_range(u64 min, u64 max) 22 { 23 u64 chi = min ^ max, delta; 24 u8 bits = fls64(chi); 25 26 /* special case, needed because 1ULL << 64 is undefined */ 27 if (bits > 63) 28 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 delta = (1ULL << bits) - 1; 34 return TNUM(min & ~delta, delta); 35 } 36 37 struct tnum tnum_lshift(struct tnum a, u8 shift) 38 { 39 return TNUM(a.value << shift, a.mask << shift); 40 } 41 42 struct tnum tnum_rshift(struct tnum a, u8 shift) 43 { 44 return TNUM(a.value >> shift, a.mask >> shift); 45 } 46 47 struct tnum tnum_arshift(struct tnum a, u8 min_shift) 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 return TNUM((s64)a.value >> min_shift, (s64)a.mask >> min_shift); 55 } 56 57 struct tnum tnum_add(struct tnum a, struct tnum b) 58 { 59 u64 sm, sv, sigma, chi, mu; 60 61 sm = a.mask + b.mask; 62 sv = a.value + b.value; 63 sigma = sm + sv; 64 chi = sigma ^ sv; 65 mu = chi | a.mask | b.mask; 66 return TNUM(sv & ~mu, mu); 67 } 68 69 struct tnum tnum_sub(struct tnum a, struct tnum b) 70 { 71 u64 dv, alpha, beta, chi, mu; 72 73 dv = a.value - b.value; 74 alpha = dv + a.mask; 75 beta = dv - b.mask; 76 chi = alpha ^ beta; 77 mu = chi | a.mask | b.mask; 78 return TNUM(dv & ~mu, mu); 79 } 80 81 struct tnum tnum_and(struct tnum a, struct tnum b) 82 { 83 u64 alpha, beta, v; 84 85 alpha = a.value | a.mask; 86 beta = b.value | b.mask; 87 v = a.value & b.value; 88 return TNUM(v, alpha & beta & ~v); 89 } 90 91 struct tnum tnum_or(struct tnum a, struct tnum b) 92 { 93 u64 v, mu; 94 95 v = a.value | b.value; 96 mu = a.mask | b.mask; 97 return TNUM(v, mu & ~v); 98 } 99 100 struct tnum tnum_xor(struct tnum a, struct tnum b) 101 { 102 u64 v, mu; 103 104 v = a.value ^ b.value; 105 mu = a.mask | b.mask; 106 return TNUM(v & ~mu, mu); 107 } 108 109 /* half-multiply add: acc += (unknown * mask * value). 110 * An intermediate step in the multiply algorithm. 111 */ 112 static struct tnum hma(struct tnum acc, u64 value, u64 mask) 113 { 114 while (mask) { 115 if (mask & 1) 116 acc = tnum_add(acc, TNUM(0, value)); 117 mask >>= 1; 118 value <<= 1; 119 } 120 return acc; 121 } 122 123 struct tnum tnum_mul(struct tnum a, struct tnum b) 124 { 125 struct tnum acc; 126 u64 pi; 127 128 pi = a.value * b.value; 129 acc = hma(TNUM(pi, 0), a.mask, b.mask | b.value); 130 return hma(acc, b.mask, a.value); 131 } 132 133 /* Note that if a and b disagree - i.e. one has a 'known 1' where the other has 134 * a 'known 0' - this will return a 'known 1' for that bit. 135 */ 136 struct tnum tnum_intersect(struct tnum a, struct tnum b) 137 { 138 u64 v, mu; 139 140 v = a.value | b.value; 141 mu = a.mask & b.mask; 142 return TNUM(v & ~mu, mu); 143 } 144 145 struct tnum tnum_cast(struct tnum a, u8 size) 146 { 147 a.value &= (1ULL << (size * 8)) - 1; 148 a.mask &= (1ULL << (size * 8)) - 1; 149 return a; 150 } 151 152 bool tnum_is_aligned(struct tnum a, u64 size) 153 { 154 if (!size) 155 return true; 156 return !((a.value | a.mask) & (size - 1)); 157 } 158 159 bool tnum_in(struct tnum a, struct tnum b) 160 { 161 if (b.mask & ~a.mask) 162 return false; 163 b.value &= ~a.mask; 164 return a.value == b.value; 165 } 166 167 int tnum_strn(char *str, size_t size, struct tnum a) 168 { 169 return snprintf(str, size, "(%#llx; %#llx)", a.value, a.mask); 170 } 171 EXPORT_SYMBOL_GPL(tnum_strn); 172 173 int tnum_sbin(char *str, size_t size, struct tnum a) 174 { 175 size_t n; 176 177 for (n = 64; n; n--) { 178 if (n < size) { 179 if (a.mask & 1) 180 str[n - 1] = 'x'; 181 else if (a.value & 1) 182 str[n - 1] = '1'; 183 else 184 str[n - 1] = '0'; 185 } 186 a.mask >>= 1; 187 a.value >>= 1; 188 } 189 str[min(size - 1, (size_t)64)] = 0; 190 return 64; 191 } 192