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