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