1 /* 2 * SPDX-FileCopyrightText: Copyright (c) 2018-2020 NVIDIA CORPORATION & AFFILIATES. All rights reserved. 3 * SPDX-License-Identifier: MIT 4 * 5 * Permission is hereby granted, free of charge, to any person obtaining a 6 * copy of this software and associated documentation files (the "Software"), 7 * to deal in the Software without restriction, including without limitation 8 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 9 * and/or sell copies of the Software, and to permit persons to whom the 10 * Software is furnished to do so, subject to the following conditions: 11 * 12 * The above copyright notice and this permission notice shall be included in 13 * all copies or substantial portions of the Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 21 * DEALINGS IN THE SOFTWARE. 22 */ 23 #ifndef _NV_UTILS_NV_BITVECTOR_H_ 24 #define _NV_UTILS_NV_BITVECTOR_H_ 25 26 #include "nvport/nvport.h" 27 #include "nvtypes.h" 28 #include "nvstatus.h" 29 #include "nvmisc.h" 30 #include "utils/nvassert.h" 31 #include "utils/nvrange.h" 32 33 #ifdef __cplusplus 34 extern "C" { 35 #endif 36 37 // 38 // Note: This will need to be recalculated if the data size changes 39 // IDX(i) = (index & ~(MASK(num bits)) >> log2(num bits) 40 // 41 #define NV_BITVECTOR_IDX(index) (((index) & ~(0x3F)) >> 6) 42 #define NV_BITVECTOR_ARRAY_SIZE(last) (NV_BITVECTOR_IDX((last) - 1) + 1) 43 #define NV_BITVECTOR_BYTE_SIZE(last) (NV_BITVECTOR_ARRAY_SIZE((last)) * sizeof(NvU64)) 44 #define NV_BITVECTOR_OFFSET(index) ((index) & ((sizeof(NvU64) * 8) - 1)) 45 46 /** 47 * \anchor NV_BITVECTOR_1 48 * @defgroup NV_BITVECTOR NV_BITVECTOR 49 * 50 * @brief NV_BITVECTOR is a collection of individual consecutive bit flags 51 * packed within an array of 64-bit integers. Each derivative of the 52 * NV_BITVECTOR type may specify the number of queryable flags, and the 53 * array will be sized according to the minimum number of 64-bit integers 54 * required to hold the flags. 55 * 56 * @details NV_BITVECTOR is a general purpose data structure utility. 57 * It consists of a single (real) field, named \b qword. 58 * Flags within a NV_BITVECTOR are represented beginning with the LSB of 59 * index 0 of \b qword, and are packed fully within a single qword 60 * before expanding into a new qword. Derivatives of NV_BITVECTOR must 61 * provide a type name for the new type, and the first index outside of 62 * the range of the new type (this value must be greater than 0.) A 63 * bitvector with bits 63 and 64 raised is represented in memory in a 64 * little-endian system as follows: 65 * 66 * 63 NV_BITVECTOR_OFFSET(i) 0 67 * .-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-. 68 * 0 |1 | 69 * 1 | 1| 70 * `-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-' 71 * 72 * Thus, in order to conceptually model an NV_BITVECTOR horizontally as 73 * a continual ordered list of bits, one would have to write the 74 * bitvector from highest index to lowest, and read from right to left. 75 * 76 * @note The unused bits within a derivative type of NV_BITVECTOR are reserved, 77 * and must not be depended upon to contain any consistent value. 78 * 79 * @{ 80 */ 81 typedef struct NV_BITVECTOR NV_BITVECTOR; 82 struct NV_BITVECTOR 83 { 84 NvU64 qword; 85 }; 86 87 #define TYPEDEF_BITVECTOR(bitvectTypeName) \ 88 union bitvectTypeName; \ 89 typedef union bitvectTypeName bitvectTypeName; \ 90 91 #define IMPL_BITVECTOR(bitvectTypeName, last_val) \ 92 union bitvectTypeName \ 93 { \ 94 NV_BITVECTOR real; \ 95 NvU64 qword[NV_BITVECTOR_ARRAY_SIZE(last_val)]; \ 96 struct \ 97 { \ 98 char _[last_val]; \ 99 char asrt[1 - 2 * !(last_val > 0)]; \ 100 } *last; \ 101 } 102 103 #define MAKE_BITVECTOR(bitvectTypeName, last_val) \ 104 TYPEDEF_BITVECTOR(bitvectTypeName) \ 105 IMPL_BITVECTOR(bitvectTypeName, last_val) 106 107 #define MAKE_ANON_BITVECTOR(last_val) \ 108 IMPL_BITVECTOR( , last_val) 109 110 #define bitVectorSizeOf(pBitVector) \ 111 bitVectorSizeOf_IMPL(&((pBitVector)->real), \ 112 sizeof(((pBitVector)->last->_))) 113 114 #define bitVectorClrAll(pBitVector) \ 115 bitVectorClrAll_IMPL(&((pBitVector)->real), \ 116 sizeof(((pBitVector)->last->_))) 117 118 #define bitVectorClr(pBitVector, idx) \ 119 bitVectorClr_IMPL(&((pBitVector)->real), \ 120 sizeof(((pBitVector)->last->_)), (idx)) 121 122 #define bitVectorClrRange(pBitVector, range) \ 123 bitVectorClrRange_IMPL(&((pBitVector)->real), \ 124 sizeof(((pBitVector)->last->_)), (range)) 125 126 #define bitVectorSetAll(pBitVector) \ 127 bitVectorSetAll_IMPL(&((pBitVector)->real), \ 128 sizeof(((pBitVector)->last->_))) 129 130 #define bitVectorSet(pBitVector, idx) \ 131 bitVectorSet_IMPL(&((pBitVector)->real), \ 132 sizeof(((pBitVector)->last->_)), (idx)) 133 134 #define bitVectorSetRange(pBitVector, range) \ 135 bitVectorSetRange_IMPL(&((pBitVector)->real), \ 136 sizeof(((pBitVector)->last->_)), (range)) 137 138 #define bitVectorFromArrayU16(pBitVector, pArr, sz) \ 139 bitVectorFromArrayU16_IMPL(&((pBitVector)->real), \ 140 sizeof(((pBitVector)->last->_)), \ 141 (pArr), \ 142 (sz)) 143 144 #define bitVectorTestAllSet(pBitVector) \ 145 bitVectorTestAllSet_IMPL(&((pBitVector)->real), \ 146 sizeof(((pBitVector)->last->_))) 147 148 #define bitVectorTestAllCleared(pBitVector) \ 149 bitVectorTestAllCleared_IMPL(&((pBitVector)->real), \ 150 sizeof(((pBitVector)->last->_))) 151 152 #define bitVectorTestEqual(pBitVectorA, pBitVectorB) \ 153 bitVectorTestEqual_IMPL(&((pBitVectorA)->real), \ 154 sizeof(((pBitVectorA)->last->_)), \ 155 &((pBitVectorB)->real), \ 156 sizeof(((pBitVectorB)->last->_))) 157 158 #define bitVectorTestIsSubset(pBitVectorA, pBitVectorB) \ 159 bitVectorTestIsSubset_IMPL(&((pBitVectorA)->real), \ 160 sizeof(((pBitVectorA)->last->_)), \ 161 &((pBitVectorB)->real), \ 162 sizeof(((pBitVectorB)->last->_))) 163 164 #define bitVectorTest(pBitVector, idx) \ 165 bitVectorTest_IMPL(&((pBitVector)->real), \ 166 sizeof(((pBitVector)->last->_)), \ 167 (idx)) 168 169 #define bitVectorAnd(pBitVectorDst, pBitVectorA, pBitVectorB) \ 170 bitVectorAnd_IMPL(&((pBitVectorDst)->real), \ 171 sizeof(((pBitVectorDst)->last->_)), \ 172 &((pBitVectorA)->real), \ 173 sizeof(((pBitVectorA)->last->_)), \ 174 &((pBitVectorB)->real), \ 175 sizeof(((pBitVectorB)->last->_))) 176 177 #define bitVectorOr(pBitVectorDst, pBitVectorA, pBitVectorB) \ 178 bitVectorOr_IMPL(&((pBitVectorDst)->real), \ 179 sizeof(((pBitVectorDst)->last->_)), \ 180 &((pBitVectorA)->real), \ 181 sizeof(((pBitVectorA)->last->_)), \ 182 &((pBitVectorB)->real), \ 183 sizeof(((pBitVectorB)->last->_))) 184 185 #define bitVectorXor(pBitVectorDst, pBitVectorA, pBitVectorB) \ 186 bitVectorXor_IMPL(&((pBitVectorDst)->real), \ 187 sizeof(((pBitVectorDst)->last->_)), \ 188 &((pBitVectorA)->real), \ 189 sizeof(((pBitVectorA)->last->_)), \ 190 &((pBitVectorB)->real), \ 191 sizeof(((pBitVectorB)->last->_))) 192 193 #define bitVectorComplement(pBitVectorDst, pBitVectorSrc) \ 194 bitVectorComplement_IMPL(&((pBitVectorDst)->real), \ 195 sizeof(((pBitVectorDst)->last->_)), \ 196 &((pBitVectorSrc)->real), \ 197 sizeof(((pBitVectorSrc)->last->_))) 198 199 #define bitVectorCopy(pBitVectorDst, pBitVectorSrc) \ 200 bitVectorCopy_IMPL(&((pBitVectorDst)->real), \ 201 sizeof(((pBitVectorDst)->last->_)), \ 202 &((pBitVectorSrc)->real), \ 203 sizeof(((pBitVectorSrc)->last->_))) 204 205 #define bitVectorCountTrailingZeros(pBitVector) \ 206 bitVectorCountTrailingZeros_IMPL(&((pBitVector)->real), \ 207 sizeof(((pBitVector)->last->_))) 208 209 #define bitVectorCountLeadingZeros(pBitVector) \ 210 bitVectorCountLeadingZeros_IMPL(&((pBitVector)->real), \ 211 sizeof(((pBitVector)->last->_))) 212 213 #define bitVectorCountSetBits(pBitVector) \ 214 bitVectorCountSetBits_IMPL(&((pBitVector)->real), \ 215 sizeof(((pBitVector)->last->_))) 216 217 #define bitVectorToRaw(pBitVector, pRawMask, rawMaskSize) \ 218 bitVectorToRaw_IMPL(&((pBitVector)->real), \ 219 sizeof(((pBitVector)->last->_)), \ 220 pRawMask, \ 221 rawMaskSize) 222 223 #define bitVectorFromRaw(pBitVector, pRawMask, rawMaskSize) \ 224 bitVectorFromRaw_IMPL(&((pBitVector)->real), \ 225 sizeof(((pBitVector)->last->_)), \ 226 pRawMask, \ 227 rawMaskSize) 228 229 #define FOR_EACH_IN_BITVECTOR(pBitVector, index) \ 230 { \ 231 MAKE_ANON_BITVECTOR(sizeof(((pBitVector)->last->_))) localMask; \ 232 bitVectorCopy(&localMask, (pBitVector)); \ 233 for ((index) = bitVectorCountTrailingZeros(&localMask); \ 234 !bitVectorTestAllCleared(&localMask); \ 235 bitVectorClr(&localMask, (index)), \ 236 (index) = bitVectorCountTrailingZeros(&localMask)) \ 237 { 238 239 #define FOR_EACH_IN_BITVECTOR_END() \ 240 } \ 241 } 242 243 #define FOR_EACH_IN_BITVECTOR_PAIR(pBitVectorA, indexA, pBitVectorB, indexB) \ 244 { \ 245 MAKE_ANON_BITVECTOR(sizeof(((pBitVectorA)->last->_))) localMaskA; \ 246 bitVectorCopy(&localMaskA, (pBitVectorA)); \ 247 MAKE_ANON_BITVECTOR(sizeof(((pBitVectorB)->last->_))) localMaskB; \ 248 bitVectorCopy(&localMaskB, (pBitVectorB)); \ 249 for ((indexA) = bitVectorCountTrailingZeros(&localMaskA), \ 250 (indexB) = bitVectorCountTrailingZeros(&localMaskB); \ 251 !bitVectorTestAllCleared(&localMaskA) && \ 252 !bitVectorTestAllCleared(&localMaskB); \ 253 bitVectorClr(&localMaskA, (indexA)), \ 254 bitVectorClr(&localMaskB, (indexB)), \ 255 (indexA) = bitVectorCountTrailingZeros(&localMaskA), \ 256 (indexB) = bitVectorCountTrailingZeros(&localMaskB)) \ 257 { 258 259 #define FOR_EACH_IN_BITVECTOR_PAIR_END() \ 260 } \ 261 } 262 263 NvU32 264 bitVectorSizeOf_IMPL 265 ( 266 const NV_BITVECTOR *pBitVector, 267 NvU16 bitVectorLast 268 ); 269 270 NV_STATUS 271 bitVectorClrAll_IMPL 272 ( 273 NV_BITVECTOR *pBitVector, 274 NvU16 bitVectorLast 275 ); 276 277 NV_STATUS 278 bitVectorClr_IMPL 279 ( 280 NV_BITVECTOR *pBitVector, 281 NvU16 bitVectorLast, 282 NvU16 idx 283 ); 284 285 NV_STATUS 286 bitVectorClrRange_IMPL 287 ( 288 NV_BITVECTOR *pBitVector, 289 NvU16 bitVectorLast, 290 NV_RANGE range 291 ); 292 293 NV_STATUS 294 bitVectorSetAll_IMPL 295 ( 296 NV_BITVECTOR *pBitVector, 297 NvU16 bitVectorLast 298 ); 299 300 NV_STATUS 301 bitVectorSet_IMPL 302 ( 303 NV_BITVECTOR *pBitVector, 304 NvU16 bitVectorLast, 305 NvU16 idx 306 ); 307 308 NV_STATUS 309 bitVectorSetRange_IMPL 310 ( 311 NV_BITVECTOR *pBitVector, 312 NvU16 bitVectorLast, 313 NV_RANGE range 314 ); 315 316 NV_STATUS 317 bitVectorInv_IMPL 318 ( 319 NV_BITVECTOR *pBitVector, 320 NvU16 bitVectorLast, 321 NvU16 idx 322 ); 323 324 NV_STATUS 325 bitVectorInvRange_IMPL 326 ( 327 NV_BITVECTOR *pBitVector, 328 NvU16 bitVectorLast, 329 NV_RANGE range 330 ); 331 332 NV_STATUS 333 bitVectorFromArrayU16_IMPL 334 ( 335 NV_BITVECTOR *pBitVector, 336 NvU16 bitVectorLast, 337 NvU16 *pIndices, 338 NvU32 indicesSize 339 ); 340 341 NvBool 342 bitVectorTestAllSet_IMPL 343 ( 344 const NV_BITVECTOR *pBitVector, 345 NvU16 bitVectorLast 346 ); 347 348 NvBool 349 bitVectorTestAllCleared_IMPL 350 ( 351 const NV_BITVECTOR *pBitVector, 352 NvU16 bitVectorLast 353 ); 354 355 NvBool 356 bitVectorTestEqual_IMPL 357 ( 358 const NV_BITVECTOR *pBitVectorA, 359 NvU16 bitVectorALast, 360 const NV_BITVECTOR *pBitVectorB, 361 NvU16 bitVectorBLast 362 ); 363 364 NvBool 365 bitVectorTestIsSubset_IMPL 366 ( 367 const NV_BITVECTOR *pBitVectorA, 368 NvU16 bitVectorALast, 369 const NV_BITVECTOR *pBitVectorB, 370 NvU16 bitVectorBLast 371 ); 372 373 NvBool 374 bitVectorTest_IMPL 375 ( 376 const NV_BITVECTOR *pBitVector, 377 NvU16 bitVectorLast, 378 NvU16 idx 379 ); 380 381 NV_STATUS 382 bitVectorAnd_IMPL 383 ( 384 NV_BITVECTOR *pBitVectorDst, 385 NvU16 bitVectorDstLast, 386 const NV_BITVECTOR *pBitVectorA, 387 NvU16 bitVectorALast, 388 const NV_BITVECTOR *pBitVectorB, 389 NvU16 bitVectorBLast 390 ); 391 392 NV_STATUS 393 bitVectorOr_IMPL 394 ( 395 NV_BITVECTOR *pBitVectorDst, 396 NvU16 bitVectorDstLast, 397 const NV_BITVECTOR *pBitVectorA, 398 NvU16 bitVectorALast, 399 const NV_BITVECTOR *pBitVectorB, 400 NvU16 bitVectorBLast 401 ); 402 403 NV_STATUS 404 bitVectorXor_IMPL 405 ( 406 NV_BITVECTOR *pBitVectorDst, 407 NvU16 bitVectorDstLast, 408 const NV_BITVECTOR *pBitVectorA, 409 NvU16 bitVectorALast, 410 const NV_BITVECTOR *pBitVectorB, 411 NvU16 bitVectorBLast 412 ); 413 414 NV_STATUS 415 bitVectorComplement_IMPL 416 ( 417 NV_BITVECTOR *pBitVectorDst, 418 NvU16 bitVectorDstLast, 419 const NV_BITVECTOR *pBitVectorSrc, 420 NvU16 bitVectorSrcLast 421 ); 422 423 NV_STATUS 424 bitVectorCopy_IMPL 425 ( 426 NV_BITVECTOR *pBitVectorDst, 427 NvU16 bitVectorDstLast, 428 const NV_BITVECTOR *pBitVectorSrc, 429 NvU16 bitVectorSrcLast 430 ); 431 432 NvU32 433 bitVectorCountTrailingZeros_IMPL 434 ( 435 const NV_BITVECTOR *pBitVector, 436 NvU16 bitVectorLast 437 ); 438 439 NvU32 440 bitVectorCountLeadingZeros_IMPL 441 ( 442 const NV_BITVECTOR *pBitVector, 443 NvU16 bitVectorLast 444 ); 445 446 NvU32 447 bitVectorCountSetBits_IMPL 448 ( 449 const NV_BITVECTOR *pBitVector, 450 NvU16 bitVectorLast 451 ); 452 453 NV_STATUS 454 bitVectorToRaw_IMPL 455 ( 456 const NV_BITVECTOR *pBitVector, 457 NvU16 bitVectorLast, 458 void *pRawMask, 459 NvU32 rawMaskize 460 ); 461 462 NV_STATUS 463 bitVectorFromRaw_IMPL 464 ( 465 NV_BITVECTOR *pBitVector, 466 NvU16 bitVectorLast, 467 const void *pRawMask, 468 NvU32 rawMaskSize 469 ); 470 471 #ifdef __cplusplus 472 } 473 #endif 474 ///@} 475 /// NV_UTILS_BITVECTOR 476 #endif 477