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 } 434