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, 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 if (insn_bitness == 32) 55 return TNUM((u32)(((s32)a.value) >> min_shift), 56 (u32)(((s32)a.mask) >> min_shift)); 57 else 58 return TNUM((s64)a.value >> min_shift, 59 (s64)a.mask >> min_shift); 60 } 61 62 struct tnum tnum_add(struct tnum a, struct tnum b) 63 { 64 u64 sm, sv, sigma, chi, mu; 65 66 sm = a.mask + b.mask; 67 sv = a.value + b.value; 68 sigma = sm + sv; 69 chi = sigma ^ sv; 70 mu = chi | a.mask | b.mask; 71 return TNUM(sv & ~mu, mu); 72 } 73 74 struct tnum tnum_sub(struct tnum a, struct tnum b) 75 { 76 u64 dv, alpha, beta, chi, mu; 77 78 dv = a.value - b.value; 79 alpha = dv + a.mask; 80 beta = dv - b.mask; 81 chi = alpha ^ beta; 82 mu = chi | a.mask | b.mask; 83 return TNUM(dv & ~mu, mu); 84 } 85 86 struct tnum tnum_neg(struct tnum a) 87 { 88 return tnum_sub(TNUM(0, 0), a); 89 } 90 91 struct tnum tnum_and(struct tnum a, struct tnum b) 92 { 93 u64 alpha, beta, v; 94 95 alpha = a.value | a.mask; 96 beta = b.value | b.mask; 97 v = a.value & b.value; 98 return TNUM(v, alpha & beta & ~v); 99 } 100 101 struct tnum tnum_or(struct tnum a, struct tnum b) 102 { 103 u64 v, mu; 104 105 v = a.value | b.value; 106 mu = a.mask | b.mask; 107 return TNUM(v, mu & ~v); 108 } 109 110 struct tnum tnum_xor(struct tnum a, struct tnum b) 111 { 112 u64 v, mu; 113 114 v = a.value ^ b.value; 115 mu = a.mask | b.mask; 116 return TNUM(v & ~mu, mu); 117 } 118 119 /* Perform long multiplication, iterating through the bits in a using rshift: 120 * - if LSB(a) is a known 0, keep current accumulator 121 * - if LSB(a) is a known 1, add b to current accumulator 122 * - if LSB(a) is unknown, take a union of the above cases. 123 * 124 * For example: 125 * 126 * acc_0: acc_1: 127 * 128 * 11 * -> 11 * -> 11 * -> union(0011, 1001) == x0x1 129 * x1 01 11 130 * ------ ------ ------ 131 * 11 11 11 132 * xx 00 11 133 * ------ ------ ------ 134 * ???? 0011 1001 135 */ 136 struct tnum tnum_mul(struct tnum a, struct tnum b) 137 { 138 struct tnum acc = TNUM(0, 0); 139 140 while (a.value || a.mask) { 141 /* LSB of tnum a is a certain 1 */ 142 if (a.value & 1) 143 acc = tnum_add(acc, b); 144 /* LSB of tnum a is uncertain */ 145 else if (a.mask & 1) { 146 /* acc = tnum_union(acc_0, acc_1), where acc_0 and 147 * acc_1 are partial accumulators for cases 148 * LSB(a) = certain 0 and LSB(a) = certain 1. 149 * acc_0 = acc + 0 * b = acc. 150 * acc_1 = acc + 1 * b = tnum_add(acc, b). 151 */ 152 153 acc = tnum_union(acc, tnum_add(acc, b)); 154 } 155 /* Note: no case for LSB is certain 0 */ 156 a = tnum_rshift(a, 1); 157 b = tnum_lshift(b, 1); 158 } 159 return acc; 160 } 161 162 bool tnum_overlap(struct tnum a, struct tnum b) 163 { 164 u64 mu; 165 166 mu = ~a.mask & ~b.mask; 167 return (a.value & mu) == (b.value & mu); 168 } 169 170 /* Note that if a and b disagree - i.e. one has a 'known 1' where the other has 171 * a 'known 0' - this will return a 'known 1' for that bit. 172 */ 173 struct tnum tnum_intersect(struct tnum a, struct tnum b) 174 { 175 u64 v, mu; 176 177 v = a.value | b.value; 178 mu = a.mask & b.mask; 179 return TNUM(v & ~mu, mu); 180 } 181 182 /* Returns a tnum with the uncertainty from both a and b, and in addition, new 183 * uncertainty at any position that a and b disagree. This represents a 184 * superset of the union of the concrete sets of both a and b. Despite the 185 * overapproximation, it is optimal. 186 */ 187 struct tnum tnum_union(struct tnum a, struct tnum b) 188 { 189 u64 v = a.value & b.value; 190 u64 mu = (a.value ^ b.value) | a.mask | b.mask; 191 192 return TNUM(v & ~mu, mu); 193 } 194 195 struct tnum tnum_cast(struct tnum a, u8 size) 196 { 197 a.value &= (1ULL << (size * 8)) - 1; 198 a.mask &= (1ULL << (size * 8)) - 1; 199 return a; 200 } 201 202 bool tnum_is_aligned(struct tnum a, u64 size) 203 { 204 if (!size) 205 return true; 206 return !((a.value | a.mask) & (size - 1)); 207 } 208 209 bool tnum_in(struct tnum a, struct tnum b) 210 { 211 if (b.mask & ~a.mask) 212 return false; 213 b.value &= ~a.mask; 214 return a.value == b.value; 215 } 216 217 int tnum_sbin(char *str, size_t size, struct tnum a) 218 { 219 size_t n; 220 221 for (n = 64; n; n--) { 222 if (n < size) { 223 if (a.mask & 1) 224 str[n - 1] = 'x'; 225 else if (a.value & 1) 226 str[n - 1] = '1'; 227 else 228 str[n - 1] = '0'; 229 } 230 a.mask >>= 1; 231 a.value >>= 1; 232 } 233 str[min(size - 1, (size_t)64)] = 0; 234 return 64; 235 } 236 237 struct tnum tnum_subreg(struct tnum a) 238 { 239 return tnum_cast(a, 4); 240 } 241 242 struct tnum tnum_clear_subreg(struct tnum a) 243 { 244 return tnum_lshift(tnum_rshift(a, 32), 32); 245 } 246 247 struct tnum tnum_with_subreg(struct tnum reg, struct tnum subreg) 248 { 249 return tnum_or(tnum_clear_subreg(reg), tnum_subreg(subreg)); 250 } 251 252 struct tnum tnum_const_subreg(struct tnum a, u32 value) 253 { 254 return tnum_with_subreg(a, tnum_const(value)); 255 } 256