| 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 | |
|---|
| 9 | #ifndef _LINUX_TNUM_H |
|---|
| 10 | #define _LINUX_TNUM_H |
|---|
| 11 | |
|---|
| 12 | #include <linux/types.h> |
|---|
| 13 | |
|---|
| 14 | struct tnum { |
|---|
| 15 | u64 value; |
|---|
| 16 | u64 mask; |
|---|
| 17 | }; |
|---|
| 18 | |
|---|
| 19 | /* Constructors */ |
|---|
| 20 | /* Represent a known constant as a tnum. */ |
|---|
| 21 | struct tnum tnum_const(u64 value); |
|---|
| 22 | /* A completely unknown value */ |
|---|
| 23 | extern const struct tnum tnum_unknown; |
|---|
| 24 | /* An unknown value that is a superset of @min <= value <= @max. |
|---|
| 25 | * |
|---|
| 26 | * Could include values outside the range of [@min, @max]. |
|---|
| 27 | * For example tnum_range(0, 2) is represented by {0, 1, 2, *3*}, |
|---|
| 28 | * rather than the intended set of {0, 1, 2}. |
|---|
| 29 | */ |
|---|
| 30 | struct tnum tnum_range(u64 min, u64 max); |
|---|
| 31 | |
|---|
| 32 | /* Arithmetic and logical ops */ |
|---|
| 33 | /* Shift a tnum left (by a fixed shift) */ |
|---|
| 34 | struct tnum tnum_lshift(struct tnum a, u8 shift); |
|---|
| 35 | /* Shift (rsh) a tnum right (by a fixed shift) */ |
|---|
| 36 | struct tnum tnum_rshift(struct tnum a, u8 shift); |
|---|
| 37 | /* Shift (arsh) a tnum right (by a fixed min_shift) */ |
|---|
| 38 | struct tnum tnum_arshift(struct tnum a, u8 min_shift, u8 insn_bitness); |
|---|
| 39 | /* Add two tnums, return @a + @b */ |
|---|
| 40 | struct tnum tnum_add(struct tnum a, struct tnum b); |
|---|
| 41 | /* Subtract two tnums, return @a - @b */ |
|---|
| 42 | struct tnum tnum_sub(struct tnum a, struct tnum b); |
|---|
| 43 | /* Bitwise-AND, return @a & @b */ |
|---|
| 44 | struct tnum tnum_and(struct tnum a, struct tnum b); |
|---|
| 45 | /* Bitwise-OR, return @a | @b */ |
|---|
| 46 | struct tnum tnum_or(struct tnum a, struct tnum b); |
|---|
| 47 | /* Bitwise-XOR, return @a ^ @b */ |
|---|
| 48 | struct tnum tnum_xor(struct tnum a, struct tnum b); |
|---|
| 49 | /* Multiply two tnums, return @a * @b */ |
|---|
| 50 | struct tnum tnum_mul(struct tnum a, struct tnum b); |
|---|
| 51 | |
|---|
| 52 | /* Return a tnum representing numbers satisfying both @a and @b */ |
|---|
| 53 | struct tnum tnum_intersect(struct tnum a, struct tnum b); |
|---|
| 54 | |
|---|
| 55 | /* Return @a with all but the lowest @size bytes cleared */ |
|---|
| 56 | struct tnum tnum_cast(struct tnum a, u8 size); |
|---|
| 57 | |
|---|
| 58 | /* Returns true if @a is a known constant */ |
|---|
| 59 | static inline bool tnum_is_const(struct tnum a) |
|---|
| 60 | { |
|---|
| 61 | return !a.mask; |
|---|
| 62 | } |
|---|
| 63 | |
|---|
| 64 | /* Returns true if @a == tnum_const(@b) */ |
|---|
| 65 | static inline bool tnum_equals_const(struct tnum a, u64 b) |
|---|
| 66 | { |
|---|
| 67 | return tnum_is_const(a) && a.value == b; |
|---|
| 68 | } |
|---|
| 69 | |
|---|
| 70 | /* Returns true if @a is completely unknown */ |
|---|
| 71 | static inline bool tnum_is_unknown(struct tnum a) |
|---|
| 72 | { |
|---|
| 73 | return !~a.mask; |
|---|
| 74 | } |
|---|
| 75 | |
|---|
| 76 | /* Returns true if @a is known to be a multiple of @size. |
|---|
| 77 | * @size must be a power of two. |
|---|
| 78 | */ |
|---|
| 79 | bool tnum_is_aligned(struct tnum a, u64 size); |
|---|
| 80 | |
|---|
| 81 | /* Returns true if @b represents a subset of @a. |
|---|
| 82 | * |
|---|
| 83 | * Note that using tnum_range() as @a requires extra cautions as tnum_in() may |
|---|
| 84 | * return true unexpectedly due to tnum limited ability to represent tight |
|---|
| 85 | * range, e.g. |
|---|
| 86 | * |
|---|
| 87 | * tnum_in(tnum_range(0, 2), tnum_const(3)) == true |
|---|
| 88 | * |
|---|
| 89 | * As a rule of thumb, if @a is explicitly coded rather than coming from |
|---|
| 90 | * reg->var_off, it should be in form of tnum_const(), tnum_range(0, 2**n - 1), |
|---|
| 91 | * or tnum_range(2**n, 2**(n+1) - 1). |
|---|
| 92 | */ |
|---|
| 93 | bool tnum_in(struct tnum a, struct tnum b); |
|---|
| 94 | |
|---|
| 95 | /* Formatting functions. These have snprintf-like semantics: they will write |
|---|
| 96 | * up to @size bytes (including the terminating NUL byte), and return the number |
|---|
| 97 | * of bytes (excluding the terminating NUL) which would have been written had |
|---|
| 98 | * sufficient space been available. (Thus tnum_sbin always returns 64.) |
|---|
| 99 | */ |
|---|
| 100 | /* Format a tnum as a pair of hex numbers (value; mask) */ |
|---|
| 101 | int tnum_strn(char *str, size_t size, struct tnum a); |
|---|
| 102 | /* Format a tnum as tristate binary expansion */ |
|---|
| 103 | int tnum_sbin(char *str, size_t size, struct tnum a); |
|---|
| 104 | |
|---|
| 105 | /* Returns the 32-bit subreg */ |
|---|
| 106 | struct tnum tnum_subreg(struct tnum a); |
|---|
| 107 | /* Returns the tnum with the lower 32-bit subreg cleared */ |
|---|
| 108 | struct tnum tnum_clear_subreg(struct tnum a); |
|---|
| 109 | /* Returns the tnum with the lower 32-bit subreg in *reg* set to the lower |
|---|
| 110 | * 32-bit subreg in *subreg* |
|---|
| 111 | */ |
|---|
| 112 | struct tnum tnum_with_subreg(struct tnum reg, struct tnum subreg); |
|---|
| 113 | /* Returns the tnum with the lower 32-bit subreg set to value */ |
|---|
| 114 | struct tnum tnum_const_subreg(struct tnum a, u32 value); |
|---|
| 115 | /* Returns true if 32-bit subreg @a is a known constant*/ |
|---|
| 116 | static inline bool tnum_subreg_is_const(struct tnum a) |
|---|
| 117 | { |
|---|
| 118 | return !(tnum_subreg(a)).mask; |
|---|
| 119 | } |
|---|
| 120 | |
|---|
| 121 | #endif /* _LINUX_TNUM_H */ |
|---|
| 122 | |
|---|
