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 */
 14const struct tnum tnum_unknown = { .value = 0, .mask = -1 };
 15
 16struct tnum tnum_const(u64 value)
 17{
 18	return TNUM(value, 0);
 19}
 20
 21struct 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
 37struct tnum tnum_lshift(struct tnum a, u8 shift)
 38{
 39	return TNUM(a.value << shift, a.mask << shift);
 40}
 41
 42struct tnum tnum_rshift(struct tnum a, u8 shift)
 43{
 44	return TNUM(a.value >> shift, a.mask >> shift);
 45}
 46
 47struct 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
 57struct 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
 69struct 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
 81struct 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
 91struct 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
100struct 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 */
112static 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
123struct 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 */
136struct 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
145struct 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
152bool 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
159bool 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
167int tnum_strn(char *str, size_t size, struct tnum a)
168{
169	return snprintf(str, size, "(%#llx; %#llx)", a.value, a.mask);
170}
171EXPORT_SYMBOL_GPL(tnum_strn);
172
173int 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}