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