]>
Commit | Line | Data |
---|---|---|
f1174f77 EC |
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 */ | |
13 | const struct tnum tnum_unknown = { .value = 0, .mask = -1 }; | |
14 | ||
15 | struct tnum tnum_const(u64 value) | |
16 | { | |
17 | return TNUM(value, 0); | |
18 | } | |
19 | ||
b03c9f9f EC |
20 | struct 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 | ||
f1174f77 EC |
36 | struct tnum tnum_lshift(struct tnum a, u8 shift) |
37 | { | |
38 | return TNUM(a.value << shift, a.mask << shift); | |
39 | } | |
40 | ||
41 | struct tnum tnum_rshift(struct tnum a, u8 shift) | |
42 | { | |
43 | return TNUM(a.value >> shift, a.mask >> shift); | |
44 | } | |
45 | ||
46 | struct 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 | ||
58 | struct 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 | ||
70 | struct 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 | ||
80 | struct 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 | ||
89 | struct 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 | */ | |
101 | static 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 | ||
112 | struct 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 | */ | |
125 | struct 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 | ||
134 | struct 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 | ||
141 | bool 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 | ||
148 | bool 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 | ||
156 | int tnum_strn(char *str, size_t size, struct tnum a) | |
157 | { | |
158 | return snprintf(str, size, "(%#llx; %#llx)", a.value, a.mask); | |
159 | } | |
160 | EXPORT_SYMBOL_GPL(tnum_strn); | |
161 | ||
162 | int 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 | } |