tests/sys/sys/bitstring_test.c

   1 /*-
   2  * Copyright (c) 2014 Spectra Logic Corporation
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions, and the following disclaimer,
  10  *    without modification.
  11  * 2. Redistributions in binary form must reproduce at minimum a disclaimer
  12  *    substantially similar to the "NO WARRANTY" disclaimer below
  13  *    ("Disclaimer") and any redistribution must be conditioned upon
  14  *    including a substantially similar Disclaimer requirement for further
  15  *    binary redistribution.
  16  *
  17  * NO WARRANTY
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR
  21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22  * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  23  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  24  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  25  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  26  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
  27  * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  28  * POSSIBILITY OF SUCH DAMAGES.
  29  *
  30  * $FreeBSD$
  31  */
  32
  33 #include <sys/param.h>
  34
  35 #include <bitstring.h>
  36 #include <stdio.h>
  37
  38 #include <atf-c.h>
  39
  40 typedef void (testfunc_t)(bitstr_t *bstr, int nbits, const char *memloc);
  41
  42 static void
  43 bitstring_run_stack_test(testfunc_t *test, int nbits)
  44 {
  45         bitstr_t bit_decl(bitstr, nbits);
  46
  47         test(bitstr, nbits, "stack");
  48 }
  49
  50 static void
  51 bitstring_run_heap_test(testfunc_t *test, int nbits)
  52 {
  53         bitstr_t *bitstr = bit_alloc(nbits);
  54
  55         test(bitstr, nbits, "heap");
  56 }
  57
  58 static void
  59 bitstring_test_runner(testfunc_t *test)
  60 {
  61         const int bitstr_sizes[] = {
  62                 0,
  63                 1,
  64                 _BITSTR_BITS - 1,
  65                 _BITSTR_BITS,
  66                 _BITSTR_BITS + 1,
  67                 2 * _BITSTR_BITS - 1,
  68                 2 * _BITSTR_BITS,
  69                 1023,
  70                 1024
  71         };
  72
  73         for (unsigned long i = 0; i < nitems(bitstr_sizes); i++) {
  74                 bitstring_run_stack_test(test, bitstr_sizes[i]);
  75                 bitstring_run_heap_test(test, bitstr_sizes[i]);
  76         }
  77 }
  78
  79 #define BITSTRING_TC_DEFINE(name)                               \
  80 ATF_TC_WITHOUT_HEAD(name);                                      \
  81 static testfunc_t name ## _test;                                \
  82                                                                 \
  83 ATF_TC_BODY(name, tc)                                           \
  84 {                                                               \
  85         bitstring_test_runner(name ## _test);                   \
  86 }                                                               \
  87                                                                 \
  88 static void                                                     \
  89 name ## _test(bitstr_t *bitstr, int nbits, const char *memloc)
  90
  91 #define BITSTRING_TC_ADD(tp, name)                              \
  92 do {                                                            \
  93         ATF_TP_ADD_TC(tp, name);                                \
  94 } while (0)
  95
  96 ATF_TC_WITHOUT_HEAD(bitstr_in_struct);
  97 ATF_TC_BODY(bitstr_in_struct, tc)
  98 {
  99         struct bitstr_containing_struct {
 100                 bitstr_t bit_decl(bitstr, 8);
 101         } test_struct;
 102
 103         bit_nclear(test_struct.bitstr, 0, 8);
 104 }
 105
 106 ATF_TC_WITHOUT_HEAD(bitstr_size);
 107 ATF_TC_BODY(bitstr_size, tc)
 108 {
 109         size_t sob = sizeof(bitstr_t);
 110
 111         ATF_CHECK_EQ(0, bitstr_size(0));
 112         ATF_CHECK_EQ(sob, bitstr_size(1));
 113         ATF_CHECK_EQ(sob, bitstr_size(sob * 8));
 114         ATF_CHECK_EQ(2 * sob, bitstr_size(sob * 8 + 1));
 115 }
 116
 117 BITSTRING_TC_DEFINE(bit_set)
 118 /* bitstr_t *bitstr, int nbits, const char *memloc */
 119 {
 120         memset(bitstr, 0, bitstr_size(nbits));
 121
 122         for (int i = 0; i < nbits; i++) {
 123                 bit_set(bitstr, i);
 124
 125                 for (int j = 0; j < nbits; j++) {
 126                         ATF_REQUIRE_MSG(bit_test(bitstr, j) == (j == i) ? 1 : 0,
 127                             "bit_set_%d_%s: Failed on bit %d",
 128                             nbits, memloc, i);
 129                 }
 130
 131                 bit_clear(bitstr, i);
 132         }
 133 }
 134
 135 BITSTRING_TC_DEFINE(bit_clear)
 136 /* bitstr_t *bitstr, int nbits, const char *memloc */
 137 {
 138         int i, j;
 139
 140         memset(bitstr, 0xFF, bitstr_size(nbits));
 141         for (i = 0; i < nbits; i++) {
 142                 bit_clear(bitstr, i);
 143
 144                 for (j = 0; j < nbits; j++) {
 145                         ATF_REQUIRE_MSG(bit_test(bitstr, j) == (j == i) ? 0 : 1,
 146                             "bit_clear_%d_%s: Failed on bit %d",
 147                             nbits, memloc, i);
 148                 }
 149
 150                 bit_set(bitstr, i);
 151         }
 152 }
 153
 154 BITSTRING_TC_DEFINE(bit_ffs)
 155 /* bitstr_t *bitstr, int nbits, const char *memloc */
 156 {
 157         int i;
 158         int found_set_bit;
 159
 160         memset(bitstr, 0, bitstr_size(nbits));
 161         bit_ffs(bitstr, nbits, &found_set_bit);
 162         ATF_REQUIRE_MSG(found_set_bit == -1,
 163             "bit_ffs_%d_%s: Failed all clear bits.", nbits, memloc);
 164
 165         for (i = 0; i < nbits; i++) {
 166                 memset(bitstr, 0xFF, bitstr_size(nbits));
 167                 if (i > 0)
 168                         bit_nclear(bitstr, 0, i - 1);
 169
 170                 bit_ffs(bitstr, nbits, &found_set_bit);
 171                 ATF_REQUIRE_MSG(found_set_bit == i,
 172                     "bit_ffs_%d_%s: Failed on bit %d, Result %d",
 173                     nbits, memloc, i, found_set_bit);
 174         }
 175 }
 176
 177 BITSTRING_TC_DEFINE(bit_ffc)
 178 /* bitstr_t *bitstr, int nbits, const char *memloc */
 179 {
 180         int i;
 181         int found_clear_bit;
 182
 183         memset(bitstr, 0xFF, bitstr_size(nbits));
 184         bit_ffc(bitstr, nbits, &found_clear_bit);
 185         ATF_REQUIRE_MSG(found_clear_bit == -1,
 186             "bit_ffc_%d_%s: Failed all set bits.", nbits, memloc);
 187
 188         for (i = 0; i < nbits; i++) {
 189                 memset(bitstr, 0, bitstr_size(nbits));
 190                 if (i > 0)
 191                         bit_nset(bitstr, 0, i - 1);
 192
 193                 bit_ffc(bitstr, nbits, &found_clear_bit);
 194                 ATF_REQUIRE_MSG(found_clear_bit == i,
 195                     "bit_ffc_%d_%s: Failed on bit %d, Result %d",
 196                     nbits, memloc, i, found_clear_bit);
 197         }
 198 }
 199
 200 BITSTRING_TC_DEFINE(bit_ffs_at)
 201 /* bitstr_t *bitstr, int nbits, const char *memloc */
 202 {
 203         int i;
 204         int found_set_bit;
 205
 206         memset(bitstr, 0xFF, bitstr_size(nbits));
 207         for (i = 0; i < nbits; i++) {
 208                 bit_ffs_at(bitstr, i, nbits, &found_set_bit);
 209                 ATF_REQUIRE_MSG(found_set_bit == i,
 210                     "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
 211                     nbits, memloc, i, found_set_bit);
 212         }
 213
 214         memset(bitstr, 0, bitstr_size(nbits));
 215         for (i = 0; i < nbits; i++) {
 216                 bit_ffs_at(bitstr, i, nbits, &found_set_bit);
 217                 ATF_REQUIRE_MSG(found_set_bit == -1,
 218                     "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
 219                     nbits, memloc, i, found_set_bit);
 220         }
 221
 222         memset(bitstr, 0x55, bitstr_size(nbits));
 223         for (i = 0; i < nbits; i++) {
 224                 bit_ffs_at(bitstr, i, nbits, &found_set_bit);
 225                 if (i == nbits - 1 && (nbits & 1) == 0) {
 226                         ATF_REQUIRE_MSG(found_set_bit == -1,
 227                             "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
 228                             nbits, memloc, i, found_set_bit);
 229                 } else {
 230                         ATF_REQUIRE_MSG(found_set_bit == i + (i & 1),
 231                             "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
 232                             nbits, memloc, i, found_set_bit);
 233                 }
 234         }
 235
 236         memset(bitstr, 0xAA, bitstr_size(nbits));
 237         for (i = 0; i < nbits; i++) {
 238                 bit_ffs_at(bitstr, i, nbits, &found_set_bit);
 239                 if (i == nbits - 1 && (nbits & 1) != 0) {
 240                         ATF_REQUIRE_MSG(found_set_bit == -1,
 241                             "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
 242                             nbits, memloc, i, found_set_bit);
 243                 } else {
 244                         ATF_REQUIRE_MSG(
 245                             found_set_bit == i + ((i & 1) ? 0 : 1),
 246                             "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
 247                             nbits, memloc, i, found_set_bit);
 248                 }
 249         }
 250
 251         /* Pass a start value beyond the size of the bit string */
 252         bit_ffs_at(bitstr, nbits, nbits, &found_set_bit);
 253         ATF_REQUIRE_MSG(found_set_bit == -1,
 254                         "bit_ffs_at_%d_%s: Failed with high start value of %d, Result %d",
 255                         nbits, memloc, nbits, found_set_bit);
 256
 257         bit_ffs_at(bitstr, nbits + 3, nbits, &found_set_bit);
 258         ATF_REQUIRE_MSG(found_set_bit == -1,
 259                         "bit_ffs_at_%d_%s: Failed with high start value of %d, Result %d",
 260                         nbits, memloc, nbits + 3, found_set_bit);
 261 }
 262
 263 BITSTRING_TC_DEFINE(bit_ffc_at)
 264 /* bitstr_t *bitstr, int nbits, const char *memloc */
 265 {
 266         int i, found_clear_bit;
 267
 268         memset(bitstr, 0, bitstr_size(nbits));
 269         for (i = 0; i < nbits; i++) {
 270                 bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
 271                 ATF_REQUIRE_MSG(found_clear_bit == i,
 272                     "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
 273                     nbits, memloc, i, found_clear_bit);
 274         }
 275
 276         memset(bitstr, 0xFF, bitstr_size(nbits));
 277         for (i = 0; i < nbits; i++) {
 278                 bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
 279                 ATF_REQUIRE_MSG(found_clear_bit == -1,
 280                     "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
 281                     nbits, memloc, i, found_clear_bit);
 282         }
 283
 284         memset(bitstr, 0x55, bitstr_size(nbits));
 285         for (i = 0; i < nbits; i++) {
 286                 bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
 287                 if (i == nbits - 1 && (nbits & 1) != 0) {
 288                         ATF_REQUIRE_MSG(found_clear_bit == -1,
 289                             "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
 290                             nbits, memloc, i, found_clear_bit);
 291                 } else {
 292                         ATF_REQUIRE_MSG(
 293                             found_clear_bit == i + ((i & 1) ? 0 : 1),
 294                             "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
 295                             nbits, memloc, i, found_clear_bit);
 296                 }
 297         }
 298
 299         memset(bitstr, 0xAA, bitstr_size(nbits));
 300         for (i = 0; i < nbits; i++) {
 301                 bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
 302                 if (i == nbits - 1 && (nbits & 1) == 0) {
 303                         ATF_REQUIRE_MSG(found_clear_bit == -1,
 304                             "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
 305                             nbits, memloc, i, found_clear_bit);
 306                 } else {
 307                         ATF_REQUIRE_MSG(found_clear_bit == i + (i & 1),
 308                             "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
 309                             nbits, memloc, i, found_clear_bit);
 310                 }
 311         }
 312
 313         /* Pass a start value beyond the size of the bit string */
 314         bit_ffc_at(bitstr, nbits, nbits, &found_clear_bit);
 315         ATF_REQUIRE_MSG(found_clear_bit == -1,
 316                         "bit_ffc_at_%d_%s: Failed with high start value, Result %d",
 317                         nbits, memloc, found_clear_bit);
 318
 319         bit_ffc_at(bitstr, nbits + 3, nbits, &found_clear_bit);
 320         ATF_REQUIRE_MSG(found_clear_bit == -1,
 321                         "bit_ffc_at_%d_%s: Failed with high start value of %d, Result %d",
 322                         nbits, memloc, nbits + 3, found_clear_bit);
 323 }
 324
 325 BITSTRING_TC_DEFINE(bit_ffc_area_at_all_or_nothing)
 326 /* bitstr_t *bitstr, int nbits, const char *memloc */
 327 {
 328         int found;
 329
 330         memset(bitstr, 0, bitstr_size(nbits));
 331         if (nbits % _BITSTR_BITS != 0)
 332                 bit_nset(bitstr, nbits, roundup2(nbits, _BITSTR_BITS) - 1);
 333
 334         for (int start = 0; start < nbits; start++) {
 335                 for (int size = 1; size < nbits - start; size++) {
 336                         bit_ffc_area_at(bitstr, start, nbits, size, &found);
 337                         ATF_REQUIRE_EQ_MSG(start, found,
 338                             "bit_ffc_area_at_%d_%s: "
 339                             "Did not find %d clear bits at %d",
 340                             nbits, memloc, size, start);
 341                 }
 342         }
 343
 344         memset(bitstr, 0xff, bitstr_size(nbits));
 345         if (nbits % _BITSTR_BITS != 0)
 346                 bit_nclear(bitstr, nbits, roundup2(nbits, _BITSTR_BITS) - 1);
 347
 348         for (int start = 0; start < nbits; start++) {
 349                 for (int size = 1; size < nbits - start; size++) {
 350                         bit_ffc_area_at(bitstr, start, nbits, size, &found);
 351                         ATF_REQUIRE_EQ_MSG(-1, found,
 352                             "bit_ffc_area_at_%d_%s: "
 353                             "Found %d clear bits at %d",
 354                             nbits, memloc, size, start);
 355                 }
 356         }
 357 }
 358
 359 BITSTRING_TC_DEFINE(bit_ffs_area_at_all_or_nothing)
 360 /* bitstr_t *bitstr, int nbits, const char *memloc */
 361 {
 362         int found;
 363
 364         memset(bitstr, 0, bitstr_size(nbits));
 365         if (nbits % _BITSTR_BITS != 0)
 366                 bit_nset(bitstr, nbits, roundup2(nbits, _BITSTR_BITS) - 1);
 367
 368         for (int start = 0; start < nbits; start++) {
 369                 for (int size = 1; size < nbits - start; size++) {
 370                         bit_ffs_area_at(bitstr, start, nbits, size, &found);
 371                         ATF_REQUIRE_EQ_MSG(-1, found,
 372                             "bit_ffs_area_at_%d_%s: "
 373                             "Found %d set bits at %d",
 374                             nbits, memloc, size, start);
 375                 }
 376         }
 377
 378         memset(bitstr, 0xff, bitstr_size(nbits));
 379         if (nbits % _BITSTR_BITS != 0)
 380                 bit_nclear(bitstr, nbits, roundup2(nbits, _BITSTR_BITS) - 1);
 381
 382         for (int start = 0; start < nbits; start++) {
 383                 for (int size = 1; size < nbits - start; size++) {
 384                         bit_ffs_area_at(bitstr, start, nbits, size, &found);
 385                         ATF_REQUIRE_EQ_MSG(start, found,
 386                             "bit_ffs_area_at_%d_%s: "
 387                             "Did not find %d set bits at %d",
 388                             nbits, memloc, size, start);
 389                 }
 390         }
 391 }
 392
 393 ATF_TC_WITHOUT_HEAD(bit_ffs_area);
 394 ATF_TC_BODY(bit_ffs_area, tc)
 395 {
 396         const int nbits = 72;
 397         bitstr_t bit_decl(bitstr, nbits);
 398         int location;
 399
 400         memset(bitstr, 0, bitstr_size(nbits));
 401
 402         bit_nset(bitstr, 5, 6);
 403
 404         location = 0;
 405         bit_ffs_area(bitstr, nbits, 3, &location);
 406         ATF_REQUIRE_EQ_MSG(-1, location,
 407             "bit_ffs_area: found location of size 3 when only 2 bits are set");
 408         ATF_REQUIRE_EQ_MSG(0, bit_ntest(bitstr, 5, 7, 1),
 409             "bit_ntest: found location of size 3 when only 2 bits are set");
 410
 411         bit_set(bitstr, 7);
 412
 413         location = 0;
 414         bit_ffs_area(bitstr, nbits, 3, &location);
 415         ATF_REQUIRE_EQ_MSG(5, location,
 416             "bit_ffs_area: failed to find location of size 3 %d", location);
 417         ATF_REQUIRE_EQ_MSG(1, bit_ntest(bitstr, 5, 7, 1),
 418             "bit_ntest: failed to find all 3 bits set");
 419
 420         bit_set(bitstr, 8);
 421
 422         location = 0;
 423         bit_ffs_area(bitstr, nbits, 3, &location);
 424         ATF_REQUIRE_EQ_MSG(5, location,
 425                         "bit_ffs_area: failed to find location of size 3");
 426
 427         location = 0;
 428         bit_ffs_area_at(bitstr, 2, nbits, 3, &location);
 429         ATF_REQUIRE_EQ_MSG(5, location,
 430                         "bit_ffs_area_at: failed to find location of size 3");
 431
 432         location = 0;
 433         bit_ffs_area_at(bitstr, 6, nbits, 3, &location);
 434         ATF_REQUIRE_EQ_MSG(6, location,
 435                         "bit_ffs_area_at: failed to find location of size 3");
 436
 437         location = 0;
 438         bit_ffs_area_at(bitstr, 8, nbits, 3, &location);
 439         ATF_REQUIRE_EQ_MSG(-1, location,
 440                         "bit_ffs_area_at: found invalid location");
 441
 442         bit_nset(bitstr, 69, 71);
 443
 444         location = 0;
 445         bit_ffs_area_at(bitstr, 8, nbits, 3, &location);
 446         ATF_REQUIRE_EQ_MSG(69, location,
 447                         "bit_ffs_area_at: failed to find location of size 3");
 448
 449         location = 0;
 450         bit_ffs_area_at(bitstr, 69, nbits, 3, &location);
 451         ATF_REQUIRE_EQ_MSG(69, location,
 452                         "bit_ffs_area_at: failed to find location of size 3");
 453
 454         location = 0;
 455         bit_ffs_area_at(bitstr, 70, nbits, 3, &location);
 456         ATF_REQUIRE_EQ_MSG(-1, location,
 457                         "bit_ffs_area_at: found invalid location");
 458
 459         location = 0;
 460         bit_ffs_area_at(bitstr, 72, nbits, 3, &location);
 461         ATF_REQUIRE_EQ_MSG(-1, location,
 462                         "bit_ffs_area_at: found invalid location");
 463
 464         bit_nset(bitstr, 59, 67);
 465
 466         location = 0;
 467         bit_ffs_area(bitstr, nbits, 9, &location);
 468         ATF_REQUIRE_EQ_MSG(59, location,
 469                         "bit_ffs_area: failed to find location of size 9");
 470
 471         location = 0;
 472         bit_ffs_area(bitstr, nbits, 10, &location);
 473         ATF_REQUIRE_EQ_MSG(-1, location,
 474                         "bit_ffs_area: found invalid location");
 475 }
 476
 477 ATF_TC_WITHOUT_HEAD(bit_ffc_area);
 478 ATF_TC_BODY(bit_ffc_area, tc)
 479 {
 480         const int nbits = 80;
 481         bitstr_t bit_decl(bitstr, nbits);
 482         int location;
 483
 484         /* set all bits */
 485         memset(bitstr, 0xFF, bitstr_size(nbits));
 486
 487         bit_clear(bitstr, 7);
 488         bit_clear(bitstr, 8);
 489
 490         location = 0;
 491         bit_ffc_area(bitstr, nbits, 3, &location);
 492         ATF_REQUIRE_EQ_MSG(-1, location,
 493                         "bit_ffc_area: found location of size 3 when only 2 bits are set");
 494
 495         bit_clear(bitstr, 9);
 496
 497         location = 0;
 498         bit_ffc_area(bitstr, nbits, 3, &location);
 499         ATF_REQUIRE_EQ_MSG(7, location,
 500                         "bit_ffc_area: failed to find location of size 3");
 501
 502         bit_clear(bitstr, 10);
 503
 504         location = 0;
 505         bit_ffc_area(bitstr, nbits, 3, &location);
 506         ATF_REQUIRE_EQ_MSG(7, location,
 507                         "bit_ffc_area: failed to find location of size 3");
 508
 509         location = 0;
 510         bit_ffc_area_at(bitstr, 2, nbits, 3, &location);
 511         ATF_REQUIRE_EQ_MSG(7, location,
 512                         "bit_ffc_area_at: failed to find location of size 3");
 513
 514         location = 0;
 515         bit_ffc_area_at(bitstr, 8, nbits, 3, &location);
 516         ATF_REQUIRE_EQ_MSG(8, location,
 517                         "bit_ffc_area_at: failed to find location of size 3");
 518
 519         location = 0;
 520         bit_ffc_area_at(bitstr, 9, nbits, 3, &location);
 521         ATF_REQUIRE_EQ_MSG(-1, location,
 522                         "bit_ffc_area_at: found invalid bit location");
 523
 524         bit_clear(bitstr, 77);
 525         bit_clear(bitstr, 78);
 526         bit_clear(bitstr, 79);
 527
 528         location = 0;
 529         bit_ffc_area_at(bitstr, 12, nbits, 3, &location);
 530         ATF_REQUIRE_EQ_MSG(77, location,
 531                         "bit_ffc_area_at: failed to find location of size 3");
 532
 533         location = 0;
 534         bit_ffc_area_at(bitstr, 77, nbits, 3, &location);
 535         ATF_REQUIRE_EQ_MSG(77, location,
 536                         "bit_ffc_area_at: failed to find location of size 3");
 537
 538         location = 0;
 539         bit_ffc_area_at(bitstr, 78, nbits, 3, &location);
 540         ATF_REQUIRE_EQ_MSG(-1, location,
 541                         "bit_ffc_area_at: found invalid location");
 542
 543         location = 0;
 544         bit_ffc_area_at(bitstr, 85, nbits, 3, &location);
 545         ATF_REQUIRE_EQ_MSG(-1, location,
 546                         "bit_ffc_area_at: found invalid location");
 547 }
 548
 549 BITSTRING_TC_DEFINE(bit_nclear)
 550 /* bitstr_t *bitstr, int nbits, const char *memloc */
 551 {
 552         int i, j;
 553         int found_set_bit;
 554         int found_clear_bit;
 555
 556         for (i = 0; i < nbits; i++) {
 557                 for (j = i; j < nbits; j++) {
 558                         memset(bitstr, 0xFF, bitstr_size(nbits));
 559                         bit_nclear(bitstr, i, j);
 560
 561                         bit_ffc(bitstr, nbits, &found_clear_bit);
 562                         ATF_REQUIRE_MSG(
 563                             found_clear_bit == i,
 564                             "bit_nclear_%d_%d_%d%s: Failed with result %d",
 565                             nbits, i, j, memloc, found_clear_bit);
 566
 567                         bit_ffs_at(bitstr, i, nbits, &found_set_bit);
 568                         ATF_REQUIRE_MSG(
 569                             (j + 1 < nbits) ? found_set_bit == j + 1 : -1,
 570                             "bit_nset_%d_%d_%d%s: Failed with result %d",
 571                             nbits, i, j, memloc, found_set_bit);
 572                 }
 573         }
 574 }
 575
 576 BITSTRING_TC_DEFINE(bit_nset)
 577 /* bitstr_t *bitstr, int nbits, const char *memloc */
 578 {
 579         int i, j;
 580         int found_set_bit;
 581         int found_clear_bit;
 582
 583         for (i = 0; i < nbits; i++) {
 584                 for (j = i; j < nbits; j++) {
 585                         memset(bitstr, 0, bitstr_size(nbits));
 586                         bit_nset(bitstr, i, j);
 587
 588                         bit_ffs(bitstr, nbits, &found_set_bit);
 589                         ATF_REQUIRE_MSG(
 590                             found_set_bit == i,
 591                             "bit_nset_%d_%d_%d%s: Failed with result %d",
 592                             nbits, i, j, memloc, found_set_bit);
 593
 594                         bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
 595                         ATF_REQUIRE_MSG(
 596                             (j + 1 < nbits) ? found_clear_bit == j + 1 : -1,
 597                             "bit_nset_%d_%d_%d%s: Failed with result %d",
 598                             nbits, i, j, memloc, found_clear_bit);
 599                 }
 600         }
 601 }
 602
 603 BITSTRING_TC_DEFINE(bit_count)
 604 /* bitstr_t *bitstr, int nbits, const char *memloc */
 605 {
 606         int result, s, e, expected;
 607
 608         /* Empty bitstr */
 609         memset(bitstr, 0, bitstr_size(nbits));
 610         bit_count(bitstr, 0, nbits, &result);
 611         ATF_CHECK_MSG(0 == result,
 612                         "bit_count_%d_%s_%s: Failed with result %d",
 613                         nbits, "clear", memloc, result);
 614
 615         /* Full bitstr */
 616         memset(bitstr, 0xFF, bitstr_size(nbits));
 617         bit_count(bitstr, 0, nbits, &result);
 618         ATF_CHECK_MSG(nbits == result,
 619                         "bit_count_%d_%s_%s: Failed with result %d",
 620                         nbits, "set", memloc, result);
 621
 622         /* Invalid _start value */
 623         memset(bitstr, 0xFF, bitstr_size(nbits));
 624         bit_count(bitstr, nbits, nbits, &result);
 625         ATF_CHECK_MSG(0 == result,
 626                         "bit_count_%d_%s_%s: Failed with result %d",
 627                         nbits, "invalid_start", memloc, result);
 628
 629         /* Alternating bitstr, starts with 0 */
 630         memset(bitstr, 0xAA, bitstr_size(nbits));
 631         bit_count(bitstr, 0, nbits, &result);
 632         ATF_CHECK_MSG(nbits / 2 == result,
 633                         "bit_count_%d_%s_%d_%s: Failed with result %d",
 634                         nbits, "alternating", 0, memloc, result);
 635
 636         /* Alternating bitstr, starts with 1 */
 637         memset(bitstr, 0x55, bitstr_size(nbits));
 638         bit_count(bitstr, 0, nbits, &result);
 639         ATF_CHECK_MSG((nbits + 1) / 2 == result,
 640                         "bit_count_%d_%s_%d_%s: Failed with result %d",
 641                         nbits, "alternating", 1, memloc, result);
 642
 643         /* Varying start location */
 644         memset(bitstr, 0xAA, bitstr_size(nbits));
 645         for (s = 0; s < nbits; s++) {
 646                 expected = s % 2 == 0 ? (nbits - s) / 2 : (nbits - s + 1) / 2;
 647                 bit_count(bitstr, s, nbits, &result);
 648                 ATF_CHECK_MSG(expected == result,
 649                                 "bit_count_%d_%s_%d_%s: Failed with result %d",
 650                                 nbits, "vary_start", s, memloc, result);
 651         }
 652
 653         /* Varying end location */
 654         memset(bitstr, 0xAA, bitstr_size(nbits));
 655         for (e = 0; e < nbits; e++) {
 656                 bit_count(bitstr, 0, e, &result);
 657                 ATF_CHECK_MSG(e / 2 == result,
 658                                 "bit_count_%d_%s_%d_%s: Failed with result %d",
 659                                 nbits, "vary_end", e, memloc, result);
 660         }
 661
 662 }
 663
 664 BITSTRING_TC_DEFINE(bit_foreach)
 665 /* bitstr_t *bitstr, int nbits, const char *memloc */
 666 {
 667         int i, set_bit;
 668
 669         /* Empty bitstr */
 670         memset(bitstr, 0x00, bitstr_size(nbits));
 671         bit_foreach (bitstr, nbits, set_bit) {
 672                 atf_tc_fail("bit_foreach_%d_%s_%s: Failed at location %d",
 673                     nbits, "clear", memloc, set_bit);
 674         }
 675
 676         /* Full bitstr */
 677         i = 0;
 678         memset(bitstr, 0xFF, bitstr_size(nbits));
 679         bit_foreach(bitstr, nbits, set_bit) {
 680                 ATF_REQUIRE_MSG(set_bit == i,
 681                     "bit_foreach_%d_%s_%s: Failed on turn %d at location %d",
 682                     nbits, "set", memloc, i, set_bit);
 683                 i++;
 684         }
 685         ATF_REQUIRE_MSG(i == nbits,
 686             "bit_foreach_%d_%s_%s: Invalid number of turns %d",
 687             nbits, "set", memloc, i);
 688
 689         /* Alternating bitstr, starts with 0 */
 690         i = 0;
 691         memset(bitstr, 0xAA, bitstr_size(nbits));
 692         bit_foreach(bitstr, nbits, set_bit) {
 693                 ATF_REQUIRE_MSG(set_bit == i * 2 + 1,
 694                     "bit_foreach_%d_%s_%d_%s: "
 695                     "Failed on turn %d at location %d",
 696                     nbits, "alternating", 0,  memloc, i, set_bit);
 697                 i++;
 698         }
 699         ATF_REQUIRE_MSG(i == nbits / 2,
 700             "bit_foreach_%d_%s_%d_%s: Invalid number of turns %d",
 701             nbits, "alternating", 0, memloc, i);
 702
 703         /* Alternating bitstr, starts with 1 */
 704         i = 0;
 705         memset(bitstr, 0x55, bitstr_size(nbits));
 706         bit_foreach(bitstr, nbits, set_bit) {
 707                 ATF_REQUIRE_MSG(set_bit == i * 2,
 708                     "bit_foreach_%d_%s_%d_%s: "
 709                     "Failed on turn %d at location %d",
 710                     nbits, "alternating", 1, memloc, i, set_bit);
 711                 i++;
 712         }
 713         ATF_REQUIRE_MSG(i == (nbits + 1) / 2,
 714             "bit_foreach_%d_%s_%d_%s: Invalid number of turns %d",
 715             nbits, "alternating", 1, memloc, i);
 716 }
 717
 718 BITSTRING_TC_DEFINE(bit_foreach_at)
 719 /* bitstr_t *bitstr, int nbits, const char *memloc */
 720 {
 721         int i, s, e, set_bit;
 722
 723         /* Invalid _start value */
 724         memset(bitstr, 0xFF, bitstr_size(nbits));
 725         bit_foreach_at(bitstr, nbits, nbits, set_bit) {
 726                 atf_tc_fail("bit_foreach_at_%d_%s_%s: Failed at location %d",
 727                     nbits, "invalid_start", memloc, set_bit);
 728         }
 729
 730         /* Varying start location */
 731         memset(bitstr, 0xAA, bitstr_size(nbits));
 732         for (s = 0; s < nbits; s++) {
 733                 i = 0;
 734                 bit_foreach_at(bitstr, s, nbits, set_bit) {
 735                         ATF_REQUIRE_MSG(set_bit == (i + s / 2) * 2 + 1,
 736                             "bit_foreach_at_%d_%s_%d_%s: "
 737                             "Failed on turn %d at location %d",
 738                             nbits, "vary_start", s,  memloc, i, set_bit);
 739                         i++;
 740                 }
 741                 ATF_REQUIRE_MSG(i == nbits / 2 - s / 2,
 742                     "bit_foreach_at_%d_%s_%d_%s: Invalid number of turns %d",
 743                     nbits, "vary_start", s, memloc, i);
 744         }
 745
 746         /* Varying end location */
 747         memset(bitstr, 0xAA, bitstr_size(nbits));
 748         for (e = 0; e < nbits; e++) {
 749                 i = 0;
 750                 bit_foreach_at(bitstr, 0, e, set_bit) {
 751                         ATF_REQUIRE_MSG(set_bit == i * 2 + 1,
 752                             "bit_foreach_at_%d_%s_%d_%s: "
 753                             "Failed on turn %d at location %d",
 754                             nbits, "vary_end", e,  memloc, i, set_bit);
 755                         i++;
 756                 }
 757                 ATF_REQUIRE_MSG(i == e / 2,
 758                     "bit_foreach_at_%d_%s_%d_%s: Invalid number of turns %d",
 759                     nbits, "vary_end", e, memloc, i);
 760         }
 761 }
 762
 763 BITSTRING_TC_DEFINE(bit_foreach_unset)
 764 /* bitstr_t *bitstr, int nbits, const char *memloc */
 765 {
 766         int i, unset_bit;
 767
 768         /* Empty bitstr */
 769         i = 0;
 770         memset(bitstr, 0, bitstr_size(nbits));
 771         bit_foreach_unset(bitstr, nbits, unset_bit) {
 772                 ATF_REQUIRE_MSG(unset_bit == i,
 773                     "bit_foreach_unset_%d_%s_%s: "
 774                     "Failed on turn %d at location %d",
 775                     nbits, "clear", memloc, i, unset_bit);
 776                 i++;
 777         }
 778         ATF_REQUIRE_MSG(i == nbits,
 779             "bit_foreach_unset_%d_%s_%s: Invalid number of turns %d",
 780             nbits, "set", memloc, i);
 781
 782         /* Full bitstr */
 783         memset(bitstr, 0xFF, bitstr_size(nbits));
 784         bit_foreach_unset(bitstr, nbits, unset_bit) {
 785                 atf_tc_fail("bit_foreach_unset_%d_%s_%s: "
 786                     "Failed at location %d",
 787                     nbits, "set", memloc, unset_bit);
 788         }
 789
 790         /* Alternating bitstr, starts with 0 */
 791         i = 0;
 792         memset(bitstr, 0xAA, bitstr_size(nbits));
 793         bit_foreach_unset(bitstr, nbits, unset_bit) {
 794                 ATF_REQUIRE_MSG(unset_bit == i * 2,
 795                     "bit_foreach_unset_%d_%s_%d_%s: "
 796                     "Failed on turn %d at location %d",
 797                     nbits, "alternating", 0,  memloc, i, unset_bit);
 798                 i++;
 799         }
 800         ATF_REQUIRE_MSG(i == (nbits + 1) / 2,
 801             "bit_foreach_unset_%d_%s_%d_%s: Invalid number of turns %d",
 802             nbits, "alternating", 0, memloc, i);
 803
 804         /* Alternating bitstr, starts with 1 */
 805         i = 0;
 806         memset(bitstr, 0x55, bitstr_size(nbits));
 807         bit_foreach_unset(bitstr, nbits, unset_bit) {
 808                 ATF_REQUIRE_MSG(unset_bit == i * 2 + 1,
 809                     "bit_foreach_unset_%d_%s_%d_%s: "
 810                     "Failed on turn %d at location %d",
 811                     nbits, "alternating", 1, memloc, i, unset_bit);
 812                 i++;
 813         }
 814         ATF_REQUIRE_MSG(i == nbits / 2,
 815             "bit_foreach_unset_%d_%s_%d_%s: Invalid number of turns %d",
 816             nbits, "alternating", 1, memloc, i);
 817 }
 818
 819 BITSTRING_TC_DEFINE(bit_foreach_unset_at)
 820 /* bitstr_t *bitstr, int nbits, const char *memloc */
 821 {
 822         int i, s, e, unset_bit;
 823
 824         /* Invalid _start value */
 825         memset(bitstr, 0, bitstr_size(nbits));
 826         bit_foreach_unset_at(bitstr, nbits, nbits, unset_bit) {
 827                 atf_tc_fail("bit_foreach_unset_at_%d_%s_%s: "
 828                     "Failed at location %d",
 829                     nbits, "invalid_start", memloc, unset_bit);
 830         }
 831
 832         /* Varying start location */
 833         memset(bitstr, 0xAA, bitstr_size(nbits));
 834         for (s = 0; s < nbits; s++) {
 835                 i = 0;
 836                 bit_foreach_unset_at(bitstr, s, nbits, unset_bit) {
 837                         ATF_REQUIRE_MSG(unset_bit == (i + (s + 1) / 2) * 2,
 838                             "bit_foreach_unset_at_%d_%s_%d_%s: "
 839                             "Failed on turn %d at location %d",
 840                             nbits, "vary_start", s,  memloc, i, unset_bit);
 841                         i++;
 842                 }
 843                 ATF_REQUIRE_MSG(i == (nbits + 1) / 2 - (s + 1) / 2,
 844                     "bit_foreach_unset_at_%d_%s_%d_%s: "
 845                     "Invalid number of turns %d",
 846                     nbits, "vary_start", s, memloc, i);
 847         }
 848
 849         /* Varying end location */
 850         memset(bitstr, 0xAA, bitstr_size(nbits));
 851         for (e = 0; e < nbits; e++) {
 852                 i = 0;
 853                 bit_foreach_unset_at(bitstr, 0, e, unset_bit) {
 854                         ATF_REQUIRE_MSG(unset_bit == i * 2,
 855                             "bit_foreach_unset_at_%d_%s_%d_%s: "
 856                             "Failed on turn %d at location %d",
 857                             nbits, "vary_end", e,  memloc, i, unset_bit);
 858                         i++;
 859                 }
 860                 ATF_REQUIRE_MSG(i == (e + 1) / 2,
 861                     "bit_foreach_unset_at_%d_%s_%d_%s: "
 862                     "Invalid number of turns %d",
 863                     nbits, "vary_end", e, memloc, i);
 864         }
 865 }
 866
 867 ATF_TP_ADD_TCS(tp)
 868 {
 869
 870         ATF_TP_ADD_TC(tp, bitstr_in_struct);
 871         ATF_TP_ADD_TC(tp, bitstr_size);
 872         ATF_TP_ADD_TC(tp, bit_ffc_area);
 873         ATF_TP_ADD_TC(tp, bit_ffs_area);
 874         BITSTRING_TC_ADD(tp, bit_set);
 875         BITSTRING_TC_ADD(tp, bit_clear);
 876         BITSTRING_TC_ADD(tp, bit_ffs);
 877         BITSTRING_TC_ADD(tp, bit_ffc);
 878         BITSTRING_TC_ADD(tp, bit_ffs_at);
 879         BITSTRING_TC_ADD(tp, bit_ffc_at);
 880         BITSTRING_TC_ADD(tp, bit_nclear);
 881         BITSTRING_TC_ADD(tp, bit_nset);
 882         BITSTRING_TC_ADD(tp, bit_count);
 883         BITSTRING_TC_ADD(tp, bit_ffs_area_at_all_or_nothing);
 884         BITSTRING_TC_ADD(tp, bit_ffc_area_at_all_or_nothing);
 885         BITSTRING_TC_ADD(tp, bit_foreach);
 886         BITSTRING_TC_ADD(tp, bit_foreach_at);
 887         BITSTRING_TC_ADD(tp, bit_foreach_unset);
 888         BITSTRING_TC_ADD(tp, bit_foreach_unset_at);
 889
 890         return (atf_no_error());
 891 }