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