Loading...
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}
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}