1// SPDX-License-Identifier: GPL-2.0 2#include <stdio.h> 3#include <stdlib.h> 4#include <string.h> 5 6#include <helpers/bitmask.h> 7 8/* How many bits in an unsigned long */ 9#define bitsperlong (8 * sizeof(unsigned long)) 10 11/* howmany(a,b) : how many elements of size b needed to hold all of a */ 12#define howmany(x, y) (((x)+((y)-1))/(y)) 13 14/* How many longs in mask of n bits */ 15#define longsperbits(n) howmany(n, bitsperlong) 16 17#define max(a, b) ((a) > (b) ? (a) : (b)) 18 19/* 20 * Allocate and free `struct bitmask *` 21 */ 22 23/* Allocate a new `struct bitmask` with a size of n bits */ 24struct bitmask *bitmask_alloc(unsigned int n) 25{ 26 struct bitmask *bmp; 27 28 bmp = malloc(sizeof(*bmp)); 29 if (!bmp) 30 return 0; 31 bmp->size = n; 32 bmp->maskp = calloc(longsperbits(n), sizeof(unsigned long)); 33 if (!bmp->maskp) { 34 free(bmp); 35 return 0; 36 } 37 return bmp; 38} 39 40/* Free `struct bitmask` */ 41void bitmask_free(struct bitmask *bmp) 42{ 43 if (!bmp) 44 return; 45 free(bmp->maskp); 46 bmp->maskp = (unsigned long *)0xdeadcdef; /* double free tripwire */ 47 free(bmp); 48} 49 50/* 51 * The routines _getbit() and _setbit() are the only 52 * routines that actually understand the layout of bmp->maskp[]. 53 * 54 * On little endian architectures, this could simply be an array of 55 * bytes. But the kernel layout of bitmasks _is_ visible to userspace 56 * via the sched_(set/get)affinity calls in Linux 2.6, and on big 57 * endian architectures, it is painfully obvious that this is an 58 * array of unsigned longs. 59 */ 60 61/* Return the value (0 or 1) of bit n in bitmask bmp */ 62static unsigned int _getbit(const struct bitmask *bmp, unsigned int n) 63{ 64 if (n < bmp->size) 65 return (bmp->maskp[n/bitsperlong] >> (n % bitsperlong)) & 1; 66 else 67 return 0; 68} 69 70/* Set bit n in bitmask bmp to value v (0 or 1) */ 71static void _setbit(struct bitmask *bmp, unsigned int n, unsigned int v) 72{ 73 if (n < bmp->size) { 74 if (v) 75 bmp->maskp[n/bitsperlong] |= 1UL << (n % bitsperlong); 76 else 77 bmp->maskp[n/bitsperlong] &= 78 ~(1UL << (n % bitsperlong)); 79 } 80} 81 82/* 83 * When parsing bitmask lists, only allow numbers, separated by one 84 * of the allowed next characters. 85 * 86 * The parameter 'sret' is the return from a sscanf "%u%c". It is 87 * -1 if the sscanf input string was empty. It is 0 if the first 88 * character in the sscanf input string was not a decimal number. 89 * It is 1 if the unsigned number matching the "%u" was the end of the 90 * input string. It is 2 if one or more additional characters followed 91 * the matched unsigned number. If it is 2, then 'nextc' is the first 92 * character following the number. The parameter 'ok_next_chars' 93 * is the nul-terminated list of allowed next characters. 94 * 95 * The mask term just scanned was ok if and only if either the numbers 96 * matching the %u were all of the input or if the next character in 97 * the input past the numbers was one of the allowed next characters. 98 */ 99static int scan_was_ok(int sret, char nextc, const char *ok_next_chars) 100{ 101 return sret == 1 || 102 (sret == 2 && strchr(ok_next_chars, nextc) != NULL); 103} 104 105static const char *nexttoken(const char *q, int sep) 106{ 107 if (q) 108 q = strchr(q, sep); 109 if (q) 110 q++; 111 return q; 112} 113 114/* Set a single bit i in bitmask */ 115struct bitmask *bitmask_setbit(struct bitmask *bmp, unsigned int i) 116{ 117 _setbit(bmp, i, 1); 118 return bmp; 119} 120 121/* Set all bits in bitmask: bmp = ~0 */ 122struct bitmask *bitmask_setall(struct bitmask *bmp) 123{ 124 unsigned int i; 125 for (i = 0; i < bmp->size; i++) 126 _setbit(bmp, i, 1); 127 return bmp; 128} 129 130/* Clear all bits in bitmask: bmp = 0 */ 131struct bitmask *bitmask_clearall(struct bitmask *bmp) 132{ 133 unsigned int i; 134 for (i = 0; i < bmp->size; i++) 135 _setbit(bmp, i, 0); 136 return bmp; 137} 138 139/* True if all bits are clear */ 140int bitmask_isallclear(const struct bitmask *bmp) 141{ 142 unsigned int i; 143 for (i = 0; i < bmp->size; i++) 144 if (_getbit(bmp, i)) 145 return 0; 146 return 1; 147} 148 149/* True if specified bit i is set */ 150int bitmask_isbitset(const struct bitmask *bmp, unsigned int i) 151{ 152 return _getbit(bmp, i); 153} 154 155/* Number of lowest set bit (min) */ 156unsigned int bitmask_first(const struct bitmask *bmp) 157{ 158 return bitmask_next(bmp, 0); 159} 160 161/* Number of highest set bit (max) */ 162unsigned int bitmask_last(const struct bitmask *bmp) 163{ 164 unsigned int i; 165 unsigned int m = bmp->size; 166 for (i = 0; i < bmp->size; i++) 167 if (_getbit(bmp, i)) 168 m = i; 169 return m; 170} 171 172/* Number of next set bit at or above given bit i */ 173unsigned int bitmask_next(const struct bitmask *bmp, unsigned int i) 174{ 175 unsigned int n; 176 for (n = i; n < bmp->size; n++) 177 if (_getbit(bmp, n)) 178 break; 179 return n; 180} 181 182/* 183 * Parses a comma-separated list of numbers and ranges of numbers, 184 * with optional ':%u' strides modifying ranges, into provided bitmask. 185 * Some examples of input lists and their equivalent simple list: 186 * Input Equivalent to 187 * 0-3 0,1,2,3 188 * 0-7:2 0,2,4,6 189 * 1,3,5-7 1,3,5,6,7 190 * 0-3:2,8-15:4 0,2,8,12 191 */ 192int bitmask_parselist(const char *buf, struct bitmask *bmp) 193{ 194 const char *p, *q; 195 196 bitmask_clearall(bmp); 197 198 q = buf; 199 while (p = q, q = nexttoken(q, ','), p) { 200 unsigned int a; /* begin of range */ 201 unsigned int b; /* end of range */ 202 unsigned int s; /* stride */ 203 const char *c1, *c2; /* next tokens after '-' or ',' */ 204 char nextc; /* char after sscanf %u match */ 205 int sret; /* sscanf return (number of matches) */ 206 207 sret = sscanf(p, "%u%c", &a, &nextc); 208 if (!scan_was_ok(sret, nextc, ",-")) 209 goto err; 210 b = a; 211 s = 1; 212 c1 = nexttoken(p, '-'); 213 c2 = nexttoken(p, ','); 214 if (c1 != NULL && (c2 == NULL || c1 < c2)) { 215 sret = sscanf(c1, "%u%c", &b, &nextc); 216 if (!scan_was_ok(sret, nextc, ",:")) 217 goto err; 218 c1 = nexttoken(c1, ':'); 219 if (c1 != NULL && (c2 == NULL || c1 < c2)) { 220 sret = sscanf(c1, "%u%c", &s, &nextc); 221 if (!scan_was_ok(sret, nextc, ",")) 222 goto err; 223 } 224 } 225 if (!(a <= b)) 226 goto err; 227 if (b >= bmp->size) 228 goto err; 229 while (a <= b) { 230 _setbit(bmp, a, 1); 231 a += s; 232 } 233 } 234 return 0; 235err: 236 bitmask_clearall(bmp); 237 return -1; 238} 239 240/* 241 * emit(buf, buflen, rbot, rtop, len) 242 * 243 * Helper routine for bitmask_displaylist(). Write decimal number 244 * or range to buf+len, suppressing output past buf+buflen, with optional 245 * comma-prefix. Return len of what would be written to buf, if it 246 * all fit. 247 */ 248 249static inline int emit(char *buf, int buflen, int rbot, int rtop, int len) 250{ 251 if (len > 0) 252 len += snprintf(buf + len, max(buflen - len, 0), ","); 253 if (rbot == rtop) 254 len += snprintf(buf + len, max(buflen - len, 0), "%d", rbot); 255 else 256 len += snprintf(buf + len, max(buflen - len, 0), "%d-%d", 257 rbot, rtop); 258 return len; 259} 260 261/* 262 * Write decimal list representation of bmp to buf. 263 * 264 * Output format is a comma-separated list of decimal numbers and 265 * ranges. Consecutively set bits are shown as two hyphen-separated 266 * decimal numbers, the smallest and largest bit numbers set in 267 * the range. Output format is compatible with the format 268 * accepted as input by bitmap_parselist(). 269 * 270 * The return value is the number of characters which would be 271 * generated for the given input, excluding the trailing '\0', as 272 * per ISO C99. 273 */ 274 275int bitmask_displaylist(char *buf, int buflen, const struct bitmask *bmp) 276{ 277 int len = 0; 278 /* current bit is 'cur', most recently seen range is [rbot, rtop] */ 279 unsigned int cur, rbot, rtop; 280 281 if (buflen > 0) 282 *buf = 0; 283 rbot = cur = bitmask_first(bmp); 284 while (cur < bmp->size) { 285 rtop = cur; 286 cur = bitmask_next(bmp, cur+1); 287 if (cur >= bmp->size || cur > rtop + 1) { 288 len = emit(buf, buflen, rbot, rtop, len); 289 rbot = cur; 290 } 291 } 292 return len; 293} 294