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