tnum.c 4.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211
  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. #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. struct tnum tnum_const(u64 value)
  15. {
  16. return TNUM(value, 0);
  17. }
  18. struct tnum tnum_range(u64 min, u64 max)
  19. {
  20. u64 chi = min ^ max, delta;
  21. u8 bits = fls64(chi);
  22. /* special case, needed because 1ULL << 64 is undefined */
  23. if (bits > 63)
  24. return tnum_unknown;
  25. /* e.g. if chi = 4, bits = 3, delta = (1<<3) - 1 = 7.
  26. * if chi = 0, bits = 0, delta = (1<<0) - 1 = 0, so we return
  27. * constant min (since min == max).
  28. */
  29. delta = (1ULL << bits) - 1;
  30. return TNUM(min & ~delta, delta);
  31. }
  32. struct tnum tnum_lshift(struct tnum a, u8 shift)
  33. {
  34. return TNUM(a.value << shift, a.mask << shift);
  35. }
  36. struct tnum tnum_rshift(struct tnum a, u8 shift)
  37. {
  38. return TNUM(a.value >> shift, a.mask >> shift);
  39. }
  40. struct tnum tnum_arshift(struct tnum a, u8 min_shift, u8 insn_bitness)
  41. {
  42. /* if a.value is negative, arithmetic shifting by minimum shift
  43. * will have larger negative offset compared to more shifting.
  44. * If a.value is nonnegative, arithmetic shifting by minimum shift
  45. * will have larger positive offset compare to more shifting.
  46. */
  47. if (insn_bitness == 32)
  48. return TNUM((u32)(((s32)a.value) >> min_shift),
  49. (u32)(((s32)a.mask) >> min_shift));
  50. else
  51. return TNUM((s64)a.value >> min_shift,
  52. (s64)a.mask >> min_shift);
  53. }
  54. struct tnum tnum_add(struct tnum a, struct tnum b)
  55. {
  56. u64 sm, sv, sigma, chi, mu;
  57. sm = a.mask + b.mask;
  58. sv = a.value + b.value;
  59. sigma = sm + sv;
  60. chi = sigma ^ sv;
  61. mu = chi | a.mask | b.mask;
  62. return TNUM(sv & ~mu, mu);
  63. }
  64. struct tnum tnum_sub(struct tnum a, struct tnum b)
  65. {
  66. u64 dv, alpha, beta, chi, mu;
  67. dv = a.value - b.value;
  68. alpha = dv + a.mask;
  69. beta = dv - b.mask;
  70. chi = alpha ^ beta;
  71. mu = chi | a.mask | b.mask;
  72. return TNUM(dv & ~mu, mu);
  73. }
  74. struct tnum tnum_and(struct tnum a, struct tnum b)
  75. {
  76. u64 alpha, beta, v;
  77. alpha = a.value | a.mask;
  78. beta = b.value | b.mask;
  79. v = a.value & b.value;
  80. return TNUM(v, alpha & beta & ~v);
  81. }
  82. struct tnum tnum_or(struct tnum a, struct tnum b)
  83. {
  84. u64 v, mu;
  85. v = a.value | b.value;
  86. mu = a.mask | b.mask;
  87. return TNUM(v, mu & ~v);
  88. }
  89. struct tnum tnum_xor(struct tnum a, struct tnum b)
  90. {
  91. u64 v, mu;
  92. v = a.value ^ b.value;
  93. mu = a.mask | b.mask;
  94. return TNUM(v & ~mu, mu);
  95. }
  96. /* half-multiply add: acc += (unknown * mask * value).
  97. * An intermediate step in the multiply algorithm.
  98. */
  99. static struct tnum hma(struct tnum acc, u64 value, u64 mask)
  100. {
  101. while (mask) {
  102. if (mask & 1)
  103. acc = tnum_add(acc, TNUM(0, value));
  104. mask >>= 1;
  105. value <<= 1;
  106. }
  107. return acc;
  108. }
  109. struct tnum tnum_mul(struct tnum a, struct tnum b)
  110. {
  111. struct tnum acc;
  112. u64 pi;
  113. pi = a.value * b.value;
  114. acc = hma(TNUM(pi, 0), a.mask, b.mask | b.value);
  115. return hma(acc, b.mask, a.value);
  116. }
  117. /* Note that if a and b disagree - i.e. one has a 'known 1' where the other has
  118. * a 'known 0' - this will return a 'known 1' for that bit.
  119. */
  120. struct tnum tnum_intersect(struct tnum a, struct tnum b)
  121. {
  122. u64 v, mu;
  123. v = a.value | b.value;
  124. mu = a.mask & b.mask;
  125. return TNUM(v & ~mu, mu);
  126. }
  127. struct tnum tnum_cast(struct tnum a, u8 size)
  128. {
  129. a.value &= (1ULL << (size * 8)) - 1;
  130. a.mask &= (1ULL << (size * 8)) - 1;
  131. return a;
  132. }
  133. bool tnum_is_aligned(struct tnum a, u64 size)
  134. {
  135. if (!size)
  136. return true;
  137. return !((a.value | a.mask) & (size - 1));
  138. }
  139. bool tnum_in(struct tnum a, struct tnum b)
  140. {
  141. if (b.mask & ~a.mask)
  142. return false;
  143. b.value &= ~a.mask;
  144. return a.value == b.value;
  145. }
  146. int tnum_strn(char *str, size_t size, struct tnum a)
  147. {
  148. return snprintf(str, size, "(%#llx; %#llx)", a.value, a.mask);
  149. }
  150. EXPORT_SYMBOL_GPL(tnum_strn);
  151. int tnum_sbin(char *str, size_t size, struct tnum a)
  152. {
  153. size_t n;
  154. for (n = 64; n; n--) {
  155. if (n < size) {
  156. if (a.mask & 1)
  157. str[n - 1] = 'x';
  158. else if (a.value & 1)
  159. str[n - 1] = '1';
  160. else
  161. str[n - 1] = '0';
  162. }
  163. a.mask >>= 1;
  164. a.value >>= 1;
  165. }
  166. str[min(size - 1, (size_t)64)] = 0;
  167. return 64;
  168. }
  169. struct tnum tnum_subreg(struct tnum a)
  170. {
  171. return tnum_cast(a, 4);
  172. }
  173. struct tnum tnum_clear_subreg(struct tnum a)
  174. {
  175. return tnum_lshift(tnum_rshift(a, 32), 32);
  176. }
  177. struct tnum tnum_const_subreg(struct tnum a, u32 value)
  178. {
  179. return tnum_or(tnum_clear_subreg(a), tnum_const(value));
  180. }