1 /* SPDX-License-Identifier: GPL-2.0-only */ 2 /* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ 3 4 #ifndef T 5 #error "Define T (bit width: 32, 64) before including cnum_defs.h" 6 #endif 7 8 #include <linux/cnum.h> 9 #include <linux/kernel.h> 10 #include <linux/limits.h> 11 #include <linux/minmax.h> 12 #include <linux/compiler_types.h> 13 14 #define cnum_t __PASTE(cnum, T) 15 #define ut __PASTE(u, T) 16 #define st __PASTE(s, T) 17 #define UT_MAX __PASTE(__PASTE(U, T), _MAX) 18 #define ST_MAX __PASTE(__PASTE(S, T), _MAX) 19 #define ST_MIN __PASTE(__PASTE(S, T), _MIN) 20 #define EMPTY __PASTE(__PASTE(CNUM, T), _EMPTY) 21 #define FN(name) __PASTE(__PASTE(cnum, T), __PASTE(_, name)) 22 23 struct cnum_t FN(from_urange)(ut min, ut max) 24 { 25 return (struct cnum_t){ .base = min, .size = (ut)max - min }; 26 } 27 28 struct cnum_t FN(from_srange)(st min, st max) 29 { 30 ut size = (ut)max - (ut)min; 31 ut base = size == UT_MAX ? 0 : (ut)min; 32 33 return (struct cnum_t){ .base = base, .size = size }; 34 } 35 36 /* 37 * True if this cnum represents two unsigned ranges. 38 * 39 * The caller should ensure !is_empty(cnum) holds when calling 40 * this function. 41 */ 42 static inline bool FN(urange_overflow)(struct cnum_t cnum) 43 { 44 /* Same as cnum.base + cnum.size > UT_MAX but avoids overflow */ 45 return cnum.size > UT_MAX - (ut)cnum.base; 46 } 47 48 /* 49 * cnum{T}_umin / cnum{T}_umax query an unsigned range represented by this cnum. 50 * If cnum represents a range crossing the UT_MAX/0 boundary, the unbound range 51 * [0..UT_MAX] is returned. 52 * 53 * The caller should ensure !is_empty(cnum) holds when calling 54 * cnum{T}_umin / cnum{T}_umax. 55 */ 56 ut FN(umin)(struct cnum_t cnum) 57 { 58 return FN(urange_overflow)(cnum) ? 0 : cnum.base; 59 } 60 EXPORT_SYMBOL_GPL(FN(umin)); 61 62 ut FN(umax)(struct cnum_t cnum) 63 { 64 return FN(urange_overflow)(cnum) ? UT_MAX : cnum.base + cnum.size; 65 } 66 EXPORT_SYMBOL_GPL(FN(umax)); 67 68 /* 69 * True if this cnum represents two signed ranges. 70 * 71 * The caller should ensure !is_empty(cnum) holds when calling 72 * this function. 73 */ 74 static inline bool FN(srange_overflow)(struct cnum_t cnum) 75 { 76 return FN(contains)(cnum, (ut)ST_MAX) && FN(contains)(cnum, (ut)ST_MIN); 77 } 78 79 /* 80 * cnum{T}_smin / cnum{T}_smax query a signed range represented by this cnum. 81 * If cnum represents a range crossing the ST_MAX/ST_MIN boundary, the unbound range 82 * [ST_MIN..ST_MAX] is returned. 83 * 84 * The caller should ensure !is_empty(cnum) holds when calling 85 * cnum{T}_smin / cnum{T}_smax. 86 */ 87 st FN(smin)(struct cnum_t cnum) 88 { 89 return FN(srange_overflow)(cnum) ? ST_MIN : (st)cnum.base; 90 } 91 92 st FN(smax)(struct cnum_t cnum) 93 { 94 return FN(srange_overflow)(cnum) ? ST_MAX : (st)(cnum.base + cnum.size); 95 } 96 97 /* 98 * Returns a possibly empty intersection of cnums 'a' and 'b'. 99 * If 'a' and 'b' intersect in two sub-arcs, the function over-approximates 100 * and returns either 'a' or 'b', whichever is smaller. 101 */ 102 struct cnum_t FN(intersect)(struct cnum_t a, struct cnum_t b) 103 { 104 struct cnum_t b1; 105 ut dbase; 106 107 if (FN(is_empty)(a) || FN(is_empty)(b)) 108 return EMPTY; 109 110 if (a.base > b.base) 111 swap(a, b); 112 113 /* 114 * Rotate frame of reference such that a.base is 0. 115 * 'b1' is 'b' in this frame of reference. 116 */ 117 dbase = b.base - a.base; 118 b1 = (struct cnum_t){ dbase, b.size }; 119 if (FN(urange_overflow)(b1)) { 120 if (b1.base <= a.size) { 121 /* 122 * Rotated frame (a.base at origin): 123 * 124 * 0 UT_MAX 125 * |--------------------------------------------| 126 * [=== a ==========================] | 127 * [= b1 tail =] [========= b1 main ==========>] 128 * ^-- b1.base <= a.size 129 * 130 * 'a' and 'b' intersect in two disjoint arcs, 131 * can't represent as single cnum, over-approximate 132 * the result. 133 */ 134 return a.size <= b.size ? a : b; 135 } else { 136 /* 137 * Rotated frame (a.base at origin): 138 * 139 * 0 UT_MAX 140 * |--------------------------------------------| 141 * [=== a =============] | | 142 * [= b1 tail =] [======= b1 main ====>] 143 * ^-- b1.base > a.size 144 * 145 * Only 'b' tail intersects 'a'. 146 */ 147 return (struct cnum_t) { 148 .base = a.base, 149 .size = min(a.size, (ut)(b1.base + b1.size)), 150 }; 151 } 152 } else if (a.size >= b1.base) { 153 /* 154 * Rotated frame (a.base at origin): 155 * 156 * 0 UT_MAX 157 * |--------------------------------------------------| 158 * [=== a ==================================] | 159 * [== b1 =====================] 160 * 161 * 0 UT_MAX 162 * |--------------------------------------------------| 163 * [=== a ==================================] | 164 * [== b1 ====] 165 * ^-- b1.base <= a.size 166 * |<-- a.size - dbase -->| 167 * 168 * 'a' and 'b' intersect as one cnum. 169 */ 170 return (struct cnum_t) { 171 .base = b.base, 172 .size = min((ut)(a.size - dbase), b.size), 173 }; 174 } else { 175 return EMPTY; 176 } 177 } 178 179 void FN(intersect_with)(struct cnum_t *dst, struct cnum_t src) 180 { 181 *dst = FN(intersect)(*dst, src); 182 } 183 184 void FN(intersect_with_urange)(struct cnum_t *dst, ut min, ut max) 185 { 186 FN(intersect_with)(dst, FN(from_urange)(min, max)); 187 } 188 189 void FN(intersect_with_srange)(struct cnum_t *dst, st min, st max) 190 { 191 FN(intersect_with)(dst, FN(from_srange)(min, max)); 192 } 193 194 static inline struct cnum_t FN(normalize)(struct cnum_t cnum) 195 { 196 if (cnum.size == UT_MAX) 197 cnum.base = 0; 198 return cnum; 199 } 200 201 /* 202 * Return a smallest arc containing both 'a' and 'b'. 203 * Break equal-size ties by choosing the smaller base. 204 */ 205 struct cnum_t FN(union)(struct cnum_t a, struct cnum_t b) 206 { 207 struct cnum_t b1, ab, ba; 208 ut end; 209 210 if (FN(is_empty)(a)) 211 return b; 212 if (FN(is_empty)(b)) 213 return a; 214 215 /* 216 * Rotate so that a1.base == 0 and a1.end == a.size. 217 * Normalize b1 to preserve the full-circle representation. 218 */ 219 b1 = FN(normalize)((struct cnum_t){ b.base - a.base, b.size }); 220 end = max(a.size, (ut)(b1.base + b1.size)); 221 222 if (FN(urange_overflow)(b1)) { 223 /* a1 reaches b1's main arc: together they cover the circle. */ 224 if (b1.base <= a.size) 225 return (struct cnum_t){ 0, UT_MAX }; 226 227 /* Extend b1's tail through a1's end, then rotate back. */ 228 return FN(normalize)((struct cnum_t){ b.base, end - b1.base }); 229 } 230 231 /* ab, rotated back, covers both nonwrapping arcs. */ 232 ab = (struct cnum_t){ a.base, end }; 233 if (b1.base <= a.size) 234 return FN(normalize)(ab); 235 236 /* The arcs are disjoint; ba is the other possible covering arc. */ 237 ba = (struct cnum_t){ b.base, a.size - b1.base }; 238 if (ba.size < ab.size || 239 (ba.size == ab.size && ba.base < ab.base)) 240 ab = ba; 241 242 return FN(normalize)(ab); 243 } 244 245 struct cnum_t FN(add)(struct cnum_t a, struct cnum_t b) 246 { 247 if (FN(is_empty)(a) || FN(is_empty)(b)) 248 return EMPTY; 249 if (a.size > UT_MAX - b.size) 250 return (struct cnum_t){ 0, (ut)UT_MAX }; 251 else 252 return FN(normalize)((struct cnum_t){ a.base + b.base, a.size + b.size }); 253 } 254 255 struct cnum_t FN(negate)(struct cnum_t a) 256 { 257 if (FN(is_empty)(a)) 258 return EMPTY; 259 return FN(normalize)((struct cnum_t){ -((ut)a.base + a.size), a.size }); 260 } 261 262 bool FN(is_empty)(struct cnum_t cnum) 263 { 264 return cnum.base == EMPTY.base && cnum.size == EMPTY.size; 265 } 266 267 bool FN(contains)(struct cnum_t cnum, ut v) 268 { 269 return !FN(is_empty)(cnum) && v - cnum.base <= cnum.size; 270 } 271 272 bool FN(is_const)(struct cnum_t cnum) 273 { 274 return cnum.size == 0; 275 } 276 277 bool FN(is_subset)(struct cnum_t bigger, struct cnum_t smaller) 278 { 279 if (FN(is_empty(smaller))) 280 return true; 281 if (FN(is_empty(bigger))) 282 return false; 283 /* rotate both arcs such that 'bigger' starts at origin, hence does not overflow */ 284 smaller.base -= bigger.base; 285 bigger.base = 0; 286 if (FN(urange_overflow)(smaller) && bigger.size < UT_MAX) 287 return false; 288 return smaller.base + smaller.size <= bigger.size; 289 } 290 291 #undef EMPTY 292 #undef cnum_t 293 #undef ut 294 #undef st 295 #undef UT_MAX 296 #undef ST_MAX 297 #undef ST_MIN 298 #undef FN 299