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 #include <sys/param.h>
  33
  34 #include <bitstring.h>
  35 #include <stdio.h>
  36
  37 #include <atf-c.h>
  38
  39 typedef void (testfunc_t)(bitstr_t *bstr, int nbits, const char *memloc);
  40
  41 static void
  42 bitstring_run_stack_test(testfunc_t *test, int nbits)
  43 {
  44         bitstr_t bit_decl(bitstr, nbits);
  45
  46         test(bitstr, nbits, "stack");
  47 }
  48
  49 static void
  50 bitstring_run_heap_test(testfunc_t *test, int nbits)
  51 {
  52         bitstr_t *bitstr = bit_alloc(nbits);
  53
  54         test(bitstr, nbits, "heap");
  55 }
  56
  57 static void
  58 bitstring_test_runner(testfunc_t *test)
  59 {
  60         const int bitstr_sizes[] = {
  61                 0,
  62                 1,
  63                 _BITSTR_BITS - 1,
  64                 _BITSTR_BITS,
  65                 _BITSTR_BITS + 1,
  66                 2 * _BITSTR_BITS - 1,
  67                 2 * _BITSTR_BITS,
  68                 1023,
  69                 1024
  70         };
  71
  72         for (unsigned long i = 0; i < nitems(bitstr_sizes); i++) {
  73                 bitstring_run_stack_test(test, bitstr_sizes[i]);
  74                 bitstring_run_heap_test(test, bitstr_sizes[i]);
  75         }
  76 }
  77
  78 #define BITSTRING_TC_DEFINE(name)                               \
  79 ATF_TC_WITHOUT_HEAD(name);                                      \
  80 static testfunc_t name ## _test;                                \
  81                                                                 \
  82 ATF_TC_BODY(name, tc)                                           \
  83 {                                                               \
  84         bitstring_test_runner(name ## _test);                   \
  85 }                                                               \
  86                                                                 \
  87 static void                                                     \
  88 name ## _test(bitstr_t *bitstr, int nbits, const char *memloc)
  89
  90 #define BITSTRING_TC_ADD(tp, name)                              \
  91 do {                                                            \
  92         ATF_TP_ADD_TC(tp, name);                                \
  93 } while (0)
  94
  95 ATF_TC_WITHOUT_HEAD(bitstr_in_struct);
  96 ATF_TC_BODY(bitstr_in_struct, tc)
  97 {
  98         struct bitstr_containing_struct {
  99                 bitstr_t bit_decl(bitstr, 8);
 100         } test_struct;
 101
 102         bit_nclear(test_struct.bitstr, 0, 8);
 103 }
 104
 105 ATF_TC_WITHOUT_HEAD(bitstr_size);
 106 ATF_TC_BODY(bitstr_size, tc)
 107 {
 108         size_t sob = sizeof(bitstr_t);
 109
 110         ATF_CHECK_EQ(0, bitstr_size(0));
 111         ATF_CHECK_EQ(sob, bitstr_size(1));
 112         ATF_CHECK_EQ(sob, bitstr_size(sob * 8));
 113         ATF_CHECK_EQ(2 * sob, bitstr_size(sob * 8 + 1));
 114 }
 115
 116 BITSTRING_TC_DEFINE(bit_set)
 117 /* bitstr_t *bitstr, int nbits, const char *memloc */
 118 {
 119         memset(bitstr, 0, bitstr_size(nbits));
 120
 121         for (int i = 0; i < nbits; i++) {
 122                 bit_set(bitstr, i);
 123
 124                 for (int j = 0; j < nbits; j++) {
 125                         ATF_REQUIRE_MSG(bit_test(bitstr, j) == (j == i) ? 1 : 0,
 126                             "bit_set_%d_%s: Failed on bit %d",
 127                             nbits, memloc, i);
 128                 }
 129
 130                 bit_clear(bitstr, i);
 131         }
 132 }
 133
 134 BITSTRING_TC_DEFINE(bit_clear)
 135 /* bitstr_t *bitstr, int nbits, const char *memloc */
 136 {
 137         int i, j;
 138
 139         memset(bitstr, 0xFF, bitstr_size(nbits));
 140         for (i = 0; i < nbits; i++) {
 141                 bit_clear(bitstr, i);
 142
 143                 for (j = 0; j < nbits; j++) {
 144                         ATF_REQUIRE_MSG(bit_test(bitstr, j) == (j == i) ? 0 : 1,
 145                             "bit_clear_%d_%s: Failed on bit %d",
 146                             nbits, memloc, i);
 147                 }
 148
 149                 bit_set(bitstr, i);
 150         }
 151 }
 152
 153 BITSTRING_TC_DEFINE(bit_ffs)
 154 /* bitstr_t *bitstr, int nbits, const char *memloc */
 155 {
 156         int i;
 157         int found_set_bit;
 158
 159         memset(bitstr, 0, bitstr_size(nbits));
 160         bit_ffs(bitstr, nbits, &found_set_bit);
 161         ATF_REQUIRE_MSG(found_set_bit == -1,
 162             "bit_ffs_%d_%s: Failed all clear bits.", nbits, memloc);
 163
 164         for (i = 0; i < nbits; i++) {
 165                 memset(bitstr, 0xFF, bitstr_size(nbits));
 166                 if (i > 0)
 167                         bit_nclear(bitstr, 0, i - 1);
 168
 169                 bit_ffs(bitstr, nbits, &found_set_bit);
 170                 ATF_REQUIRE_MSG(found_set_bit == i,
 171                     "bit_ffs_%d_%s: Failed on bit %d, Result %d",
 172                     nbits, memloc, i, found_set_bit);
 173         }
 174 }
 175
 176 BITSTRING_TC_DEFINE(bit_ffc)
 177 /* bitstr_t *bitstr, int nbits, const char *memloc */
 178 {
 179         int i;
 180         int found_clear_bit;
 181
 182         memset(bitstr, 0xFF, bitstr_size(nbits));
 183         bit_ffc(bitstr, nbits, &found_clear_bit);
 184         ATF_REQUIRE_MSG(found_clear_bit == -1,
 185             "bit_ffc_%d_%s: Failed all set bits.", nbits, memloc);
 186
 187         for (i = 0; i < nbits; i++) {
 188                 memset(bitstr, 0, bitstr_size(nbits));
 189                 if (i > 0)
 190                         bit_nset(bitstr, 0, i - 1);
 191
 192                 bit_ffc(bitstr, nbits, &found_clear_bit);
 193                 ATF_REQUIRE_MSG(found_clear_bit == i,
 194                     "bit_ffc_%d_%s: Failed on bit %d, Result %d",
 195                     nbits, memloc, i, found_clear_bit);
 196         }
 197 }
 198
 199 BITSTRING_TC_DEFINE(bit_ffs_at)
 200 /* bitstr_t *bitstr, int nbits, const char *memloc */
 201 {
 202         int i;
 203         int found_set_bit;
 204
 205         memset(bitstr, 0xFF, bitstr_size(nbits));
 206         for (i = 0; i < nbits; i++) {
 207                 bit_ffs_at(bitstr, i, nbits, &found_set_bit);
 208                 ATF_REQUIRE_MSG(found_set_bit == i,
 209                     "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
 210                     nbits, memloc, i, found_set_bit);
 211         }
 212
 213         memset(bitstr, 0, bitstr_size(nbits));
 214         for (i = 0; i < nbits; i++) {
 215                 bit_ffs_at(bitstr, i, nbits, &found_set_bit);
 216                 ATF_REQUIRE_MSG(found_set_bit == -1,
 217                     "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
 218                     nbits, memloc, i, found_set_bit);
 219         }
 220
 221         memset(bitstr, 0x55, bitstr_size(nbits));
 222         for (i = 0; i < nbits; i++) {
 223                 bit_ffs_at(bitstr, i, nbits, &found_set_bit);
 224                 if (i == nbits - 1 && (nbits & 1) == 0) {
 225                         ATF_REQUIRE_MSG(found_set_bit == -1,
 226                             "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
 227                             nbits, memloc, i, found_set_bit);
 228                 } else {
 229                         ATF_REQUIRE_MSG(found_set_bit == i + (i & 1),
 230                             "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
 231                             nbits, memloc, i, found_set_bit);
 232                 }
 233         }
 234
 235         memset(bitstr, 0xAA, bitstr_size(nbits));
 236         for (i = 0; i < nbits; i++) {
 237                 bit_ffs_at(bitstr, i, nbits, &found_set_bit);
 238                 if (i == nbits - 1 && (nbits & 1) != 0) {
 239                         ATF_REQUIRE_MSG(found_set_bit == -1,
 240                             "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
 241                             nbits, memloc, i, found_set_bit);
 242                 } else {
 243                         ATF_REQUIRE_MSG(
 244                             found_set_bit == i + ((i & 1) ? 0 : 1),
 245                             "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
 246                             nbits, memloc, i, found_set_bit);
 247                 }
 248         }
 249 }
 250
 251 BITSTRING_TC_DEFINE(bit_ffc_at)
 252 /* bitstr_t *bitstr, int nbits, const char *memloc */
 253 {
 254         int i, found_clear_bit;
 255
 256         memset(bitstr, 0, bitstr_size(nbits));
 257         for (i = 0; i < nbits; i++) {
 258                 bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
 259                 ATF_REQUIRE_MSG(found_clear_bit == i,
 260                     "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
 261                     nbits, memloc, i, found_clear_bit);
 262         }
 263
 264         memset(bitstr, 0xFF, bitstr_size(nbits));
 265         for (i = 0; i < nbits; i++) {
 266                 bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
 267                 ATF_REQUIRE_MSG(found_clear_bit == -1,
 268                     "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
 269                     nbits, memloc, i, found_clear_bit);
 270         }
 271
 272         memset(bitstr, 0x55, bitstr_size(nbits));
 273         for (i = 0; i < nbits; i++) {
 274                 bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
 275                 if (i == nbits - 1 && (nbits & 1) != 0) {
 276                         ATF_REQUIRE_MSG(found_clear_bit == -1,
 277                             "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
 278                             nbits, memloc, i, found_clear_bit);
 279                 } else {
 280                         ATF_REQUIRE_MSG(
 281                             found_clear_bit == i + ((i & 1) ? 0 : 1),
 282                             "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
 283                             nbits, memloc, i, found_clear_bit);
 284                 }
 285         }
 286
 287         memset(bitstr, 0xAA, bitstr_size(nbits));
 288         for (i = 0; i < nbits; i++) {
 289                 bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
 290                 if (i == nbits - 1 && (nbits & 1) == 0) {
 291                         ATF_REQUIRE_MSG(found_clear_bit == -1,
 292                             "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
 293                             nbits, memloc, i, found_clear_bit);
 294                 } else {
 295                         ATF_REQUIRE_MSG(found_clear_bit == i + (i & 1),
 296                             "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
 297                             nbits, memloc, i, found_clear_bit);
 298                 }
 299         }
 300 }
 301
 302 BITSTRING_TC_DEFINE(bit_nclear)
 303 /* bitstr_t *bitstr, int nbits, const char *memloc */
 304 {
 305         int i, j;
 306         int found_set_bit;
 307         int found_clear_bit;
 308
 309         for (i = 0; i < nbits; i++) {
 310                 for (j = i; j < nbits; j++) {
 311                         memset(bitstr, 0xFF, bitstr_size(nbits));
 312                         bit_nclear(bitstr, i, j);
 313
 314                         bit_ffc(bitstr, nbits, &found_clear_bit);
 315                         ATF_REQUIRE_MSG(
 316                             found_clear_bit == i,
 317                             "bit_nclear_%d_%d_%d%s: Failed with result %d",
 318                             nbits, i, j, memloc, found_clear_bit);
 319
 320                         bit_ffs_at(bitstr, i, nbits, &found_set_bit);
 321                         ATF_REQUIRE_MSG(
 322                             (j + 1 < nbits) ? found_set_bit == j + 1 : -1,
 323                             "bit_nset_%d_%d_%d%s: Failed with result %d",
 324                             nbits, i, j, memloc, found_set_bit);
 325                 }
 326         }
 327 }
 328
 329 BITSTRING_TC_DEFINE(bit_nset)
 330 /* bitstr_t *bitstr, int nbits, const char *memloc */
 331 {
 332         int i, j;
 333         int found_set_bit;
 334         int found_clear_bit;
 335
 336         for (i = 0; i < nbits; i++) {
 337                 for (j = i; j < nbits; j++) {
 338                         memset(bitstr, 0, bitstr_size(nbits));
 339                         bit_nset(bitstr, i, j);
 340
 341                         bit_ffs(bitstr, nbits, &found_set_bit);
 342                         ATF_REQUIRE_MSG(
 343                             found_set_bit == i,
 344                             "bit_nset_%d_%d_%d%s: Failed with result %d",
 345                             nbits, i, j, memloc, found_set_bit);
 346
 347                         bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
 348                         ATF_REQUIRE_MSG(
 349                             (j + 1 < nbits) ? found_clear_bit == j + 1 : -1,
 350                             "bit_nset_%d_%d_%d%s: Failed with result %d",
 351                             nbits, i, j, memloc, found_clear_bit);
 352                 }
 353         }
 354 }
 355
 356 BITSTRING_TC_DEFINE(bit_count)
 357 /* bitstr_t *bitstr, int nbits, const char *memloc */
 358 {
 359         int result, s, e, expected;
 360
 361         /* Empty bitstr */
 362         memset(bitstr, 0, bitstr_size(nbits));
 363         bit_count(bitstr, 0, nbits, &result);
 364         ATF_CHECK_MSG(0 == result,
 365                         "bit_count_%d_%s_%s: Failed with result %d",
 366                         nbits, "clear", memloc, result);
 367
 368         /* Full bitstr */
 369         memset(bitstr, 0xFF, bitstr_size(nbits));
 370         bit_count(bitstr, 0, nbits, &result);
 371         ATF_CHECK_MSG(nbits == result,
 372                         "bit_count_%d_%s_%s: Failed with result %d",
 373                         nbits, "set", memloc, result);
 374
 375         /* Invalid _start value */
 376         memset(bitstr, 0xFF, bitstr_size(nbits));
 377         bit_count(bitstr, nbits, nbits, &result);
 378         ATF_CHECK_MSG(0 == result,
 379                         "bit_count_%d_%s_%s: Failed with result %d",
 380                         nbits, "invalid_start", memloc, result);
 381
 382         /* Alternating bitstr, starts with 0 */
 383         memset(bitstr, 0xAA, bitstr_size(nbits));
 384         bit_count(bitstr, 0, nbits, &result);
 385         ATF_CHECK_MSG(nbits / 2 == result,
 386                         "bit_count_%d_%s_%d_%s: Failed with result %d",
 387                         nbits, "alternating", 0, memloc, result);
 388
 389         /* Alternating bitstr, starts with 1 */
 390         memset(bitstr, 0x55, bitstr_size(nbits));
 391         bit_count(bitstr, 0, nbits, &result);
 392         ATF_CHECK_MSG((nbits + 1) / 2 == result,
 393                         "bit_count_%d_%s_%d_%s: Failed with result %d",
 394                         nbits, "alternating", 1, memloc, result);
 395
 396         /* Varying start location */
 397         memset(bitstr, 0xAA, bitstr_size(nbits));
 398         for (s = 0; s < nbits; s++) {
 399                 expected = s % 2 == 0 ? (nbits - s) / 2 : (nbits - s + 1) / 2;
 400                 bit_count(bitstr, s, nbits, &result);
 401                 ATF_CHECK_MSG(expected == result,
 402                                 "bit_count_%d_%s_%d_%s: Failed with result %d",
 403                                 nbits, "vary_start", s, memloc, result);
 404         }
 405
 406         /* Varying end location */
 407         memset(bitstr, 0xAA, bitstr_size(nbits));
 408         for (e = 0; e < nbits; e++) {
 409                 bit_count(bitstr, 0, e, &result);
 410                 ATF_CHECK_MSG(e / 2 == result,
 411                                 "bit_count_%d_%s_%d_%s: Failed with result %d",
 412                                 nbits, "vary_end", e, memloc, result);
 413         }
 414
 415 }
 416
 417 ATF_TP_ADD_TCS(tp)
 418 {
 419
 420         ATF_TP_ADD_TC(tp, bitstr_in_struct);
 421         ATF_TP_ADD_TC(tp, bitstr_size);
 422         BITSTRING_TC_ADD(tp, bit_set);
 423         BITSTRING_TC_ADD(tp, bit_clear);
 424         BITSTRING_TC_ADD(tp, bit_ffs);
 425         BITSTRING_TC_ADD(tp, bit_ffc);
 426         BITSTRING_TC_ADD(tp, bit_ffs_at);
 427         BITSTRING_TC_ADD(tp, bit_ffc_at);
 428         BITSTRING_TC_ADD(tp, bit_nclear);
 429         BITSTRING_TC_ADD(tp, bit_nset);
 430         BITSTRING_TC_ADD(tp, bit_count);
 431
 432         return (atf_no_error());
 433 }