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