1 /* $NetBSD: t_bitops.c,v 1.19 2015/03/21 05:50:19 isaki Exp $ */ 2 3 /*- 4 * Copyright (c) 2011, 2012 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Christos Zoulas and Jukka Ruohonen. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 #include <sys/cdefs.h> 32 __RCSID("$NetBSD: t_bitops.c,v 1.19 2015/03/21 05:50:19 isaki Exp $"); 33 34 #include <atf-c.h> 35 36 #include <sys/cdefs.h> 37 #include <sys/bitops.h> 38 39 #include <math.h> 40 #include <inttypes.h> 41 #include <stdlib.h> 42 #include <string.h> 43 44 static const struct { 45 uint32_t val; 46 int ffs; 47 int fls; 48 } bits[] = { 49 50 { 0x00, 0, 0 }, { 0x01, 1, 1 }, { 0x02, 2, 2 }, { 0x03, 1, 2 }, 51 { 0x04, 3, 3 }, { 0x05, 1, 3 }, { 0x06, 2, 3 }, { 0x07, 1, 3 }, 52 { 0x08, 4, 4 }, { 0x09, 1, 4 }, { 0x0A, 2, 4 }, { 0x0B, 1, 4 }, 53 { 0x0C, 3, 4 }, { 0x0D, 1, 4 }, { 0x0E, 2, 4 }, { 0x0F, 1, 4 }, 54 55 { 0x10, 5, 5 }, { 0x11, 1, 5 }, { 0x12, 2, 5 }, { 0x13, 1, 5 }, 56 { 0x14, 3, 5 }, { 0x15, 1, 5 }, { 0x16, 2, 5 }, { 0x17, 1, 5 }, 57 { 0x18, 4, 5 }, { 0x19, 1, 5 }, { 0x1A, 2, 5 }, { 0x1B, 1, 5 }, 58 { 0x1C, 3, 5 }, { 0x1D, 1, 5 }, { 0x1E, 2, 5 }, { 0x1F, 1, 5 }, 59 60 { 0xF0, 5, 8 }, { 0xF1, 1, 8 }, { 0xF2, 2, 8 }, { 0xF3, 1, 8 }, 61 { 0xF4, 3, 8 }, { 0xF5, 1, 8 }, { 0xF6, 2, 8 }, { 0xF7, 1, 8 }, 62 { 0xF8, 4, 8 }, { 0xF9, 1, 8 }, { 0xFA, 2, 8 }, { 0xFB, 1, 8 }, 63 { 0xFC, 3, 8 }, { 0xFD, 1, 8 }, { 0xFE, 2, 8 }, { 0xFF, 1, 8 }, 64 65 }; 66 67 ATF_TC(bitmap_basic); 68 ATF_TC_HEAD(bitmap_basic, tc) 69 { 70 atf_tc_set_md_var(tc, "descr", "A basic test of __BITMAP_*"); 71 } 72 73 ATF_TC_BODY(bitmap_basic, tc) 74 { 75 __BITMAP_TYPE(, uint32_t, 65536) bm; 76 __BITMAP_ZERO(&bm); 77 78 ATF_REQUIRE(__BITMAP_SIZE(uint32_t, 65536) == 2048); 79 80 ATF_REQUIRE(__BITMAP_SHIFT(uint32_t) == 5); 81 82 ATF_REQUIRE(__BITMAP_MASK(uint32_t) == 31); 83 84 for (size_t i = 0; i < 65536; i += 2) 85 __BITMAP_SET(i, &bm); 86 87 for (size_t i = 0; i < 2048; i++) 88 ATF_REQUIRE(bm._b[i] == 0x55555555); 89 90 for (size_t i = 0; i < 65536; i++) 91 if (i & 1) 92 ATF_REQUIRE(!__BITMAP_ISSET(i, &bm)); 93 else { 94 ATF_REQUIRE(__BITMAP_ISSET(i, &bm)); 95 __BITMAP_CLR(i, &bm); 96 } 97 98 for (size_t i = 0; i < 65536; i += 2) 99 ATF_REQUIRE(!__BITMAP_ISSET(i, &bm)); 100 } 101 102 ATF_TC(fast_divide32); 103 ATF_TC_HEAD(fast_divide32, tc) 104 { 105 atf_tc_set_md_var(tc, "descr", "A basic test of fast_divide32(3)"); 106 } 107 108 ATF_TC_BODY(fast_divide32, tc) 109 { 110 uint32_t a, b, q, r, m; 111 uint8_t i, s1, s2; 112 113 a = 0xFFFF; 114 b = 0x000F; 115 116 fast_divide32_prepare(b, &m, &s1, &s2); 117 118 q = fast_divide32(a, b, m, s1, s2); 119 r = fast_remainder32(a, b, m, s1, s2); 120 121 ATF_REQUIRE(q == 0x1111 && r == 0); 122 123 for (i = 1; i < __arraycount(bits); i++) { 124 125 a = bits[i].val; 126 b = bits[i].ffs; 127 128 fast_divide32_prepare(b, &m, &s1, &s2); 129 130 q = fast_divide32(a, b, m, s1, s2); 131 r = fast_remainder32(a, b, m, s1, s2); 132 133 ATF_REQUIRE(q == a / b); 134 ATF_REQUIRE(r == a % b); 135 } 136 } 137 138 ATF_TC(ffsfls); 139 ATF_TC_HEAD(ffsfls, tc) 140 { 141 atf_tc_set_md_var(tc, "descr", "Test ffs32(3)-family for correctness"); 142 } 143 144 ATF_TC_BODY(ffsfls, tc) 145 { 146 uint8_t i; 147 148 ATF_REQUIRE(ffs32(0) == 0x00); 149 ATF_REQUIRE(fls32(0) == 0x00); 150 ATF_REQUIRE(ffs64(0) == 0x00); 151 ATF_REQUIRE(fls64(0) == 0x00); 152 153 ATF_REQUIRE(ffs32(UINT32_MAX) == 0x01); 154 ATF_REQUIRE(fls32(UINT32_MAX) == 0x20); 155 ATF_REQUIRE(ffs64(UINT64_MAX) == 0x01); 156 ATF_REQUIRE(fls64(UINT64_MAX) == 0x40); 157 158 for (i = 1; i < __arraycount(bits); i++) { 159 160 ATF_REQUIRE(ffs32(bits[i].val) == bits[i].ffs); 161 ATF_REQUIRE(fls32(bits[i].val) == bits[i].fls); 162 ATF_REQUIRE(ffs64(bits[i].val) == bits[i].ffs); 163 ATF_REQUIRE(fls64(bits[i].val) == bits[i].fls); 164 165 ATF_REQUIRE(ffs32(bits[i].val << 1) == bits[i].ffs + 1); 166 ATF_REQUIRE(fls32(bits[i].val << 1) == bits[i].fls + 1); 167 ATF_REQUIRE(ffs64(bits[i].val << 1) == bits[i].ffs + 1); 168 ATF_REQUIRE(fls64(bits[i].val << 1) == bits[i].fls + 1); 169 170 ATF_REQUIRE(ffs32(bits[i].val << 9) == bits[i].ffs + 9); 171 ATF_REQUIRE(fls32(bits[i].val << 9) == bits[i].fls + 9); 172 ATF_REQUIRE(ffs64(bits[i].val << 9) == bits[i].ffs + 9); 173 ATF_REQUIRE(fls64(bits[i].val << 9) == bits[i].fls + 9); 174 } 175 } 176 177 ATF_TC(ilog2_32bit); 178 ATF_TC_HEAD(ilog2_32bit, tc) 179 { 180 atf_tc_set_md_var(tc, "descr", "Test ilog2(3) for 32bit variable"); 181 } 182 183 ATF_TC_BODY(ilog2_32bit, tc) 184 { 185 int i; 186 uint32_t x; 187 188 for (i = 0; i < 32; i++) { 189 x = 1 << i; 190 ATF_REQUIRE(ilog2(x) == i); 191 } 192 } 193 194 ATF_TC(ilog2_64bit); 195 ATF_TC_HEAD(ilog2_64bit, tc) 196 { 197 atf_tc_set_md_var(tc, "descr", "Test ilog2(3) for 64bit variable"); 198 } 199 200 ATF_TC_BODY(ilog2_64bit, tc) 201 { 202 int i; 203 uint64_t x; 204 205 for (i = 0; i < 64; i++) { 206 x = ((uint64_t)1) << i; 207 ATF_REQUIRE(ilog2(x) == i); 208 } 209 } 210 211 ATF_TC(ilog2_const); 212 ATF_TC_HEAD(ilog2_const, tc) 213 { 214 atf_tc_set_md_var(tc, "descr", "Test ilog2(3) for constant"); 215 } 216 217 ATF_TC_BODY(ilog2_const, tc) 218 { 219 /* 220 * These inlines test __builtin_constant_p() part of ilog2() 221 * at compile time, so don't change it to loop. PR lib/49745 222 */ 223 ATF_REQUIRE(ilog2(0x0000000000000001ULL) == 0); 224 ATF_REQUIRE(ilog2(0x0000000000000002ULL) == 1); 225 ATF_REQUIRE(ilog2(0x0000000000000004ULL) == 2); 226 ATF_REQUIRE(ilog2(0x0000000000000008ULL) == 3); 227 ATF_REQUIRE(ilog2(0x0000000000000010ULL) == 4); 228 ATF_REQUIRE(ilog2(0x0000000000000020ULL) == 5); 229 ATF_REQUIRE(ilog2(0x0000000000000040ULL) == 6); 230 ATF_REQUIRE(ilog2(0x0000000000000080ULL) == 7); 231 ATF_REQUIRE(ilog2(0x0000000000000100ULL) == 8); 232 ATF_REQUIRE(ilog2(0x0000000000000200ULL) == 9); 233 ATF_REQUIRE(ilog2(0x0000000000000400ULL) == 10); 234 ATF_REQUIRE(ilog2(0x0000000000000800ULL) == 11); 235 ATF_REQUIRE(ilog2(0x0000000000001000ULL) == 12); 236 ATF_REQUIRE(ilog2(0x0000000000002000ULL) == 13); 237 ATF_REQUIRE(ilog2(0x0000000000004000ULL) == 14); 238 ATF_REQUIRE(ilog2(0x0000000000008000ULL) == 15); 239 ATF_REQUIRE(ilog2(0x0000000000010000ULL) == 16); 240 ATF_REQUIRE(ilog2(0x0000000000020000ULL) == 17); 241 ATF_REQUIRE(ilog2(0x0000000000040000ULL) == 18); 242 ATF_REQUIRE(ilog2(0x0000000000080000ULL) == 19); 243 ATF_REQUIRE(ilog2(0x0000000000100000ULL) == 20); 244 ATF_REQUIRE(ilog2(0x0000000000200000ULL) == 21); 245 ATF_REQUIRE(ilog2(0x0000000000400000ULL) == 22); 246 ATF_REQUIRE(ilog2(0x0000000000800000ULL) == 23); 247 ATF_REQUIRE(ilog2(0x0000000001000000ULL) == 24); 248 ATF_REQUIRE(ilog2(0x0000000002000000ULL) == 25); 249 ATF_REQUIRE(ilog2(0x0000000004000000ULL) == 26); 250 ATF_REQUIRE(ilog2(0x0000000008000000ULL) == 27); 251 ATF_REQUIRE(ilog2(0x0000000010000000ULL) == 28); 252 ATF_REQUIRE(ilog2(0x0000000020000000ULL) == 29); 253 ATF_REQUIRE(ilog2(0x0000000040000000ULL) == 30); 254 ATF_REQUIRE(ilog2(0x0000000080000000ULL) == 31); 255 ATF_REQUIRE(ilog2(0x0000000100000000ULL) == 32); 256 ATF_REQUIRE(ilog2(0x0000000200000000ULL) == 33); 257 ATF_REQUIRE(ilog2(0x0000000400000000ULL) == 34); 258 ATF_REQUIRE(ilog2(0x0000000800000000ULL) == 35); 259 ATF_REQUIRE(ilog2(0x0000001000000000ULL) == 36); 260 ATF_REQUIRE(ilog2(0x0000002000000000ULL) == 37); 261 ATF_REQUIRE(ilog2(0x0000004000000000ULL) == 38); 262 ATF_REQUIRE(ilog2(0x0000008000000000ULL) == 39); 263 ATF_REQUIRE(ilog2(0x0000010000000000ULL) == 40); 264 ATF_REQUIRE(ilog2(0x0000020000000000ULL) == 41); 265 ATF_REQUIRE(ilog2(0x0000040000000000ULL) == 42); 266 ATF_REQUIRE(ilog2(0x0000080000000000ULL) == 43); 267 ATF_REQUIRE(ilog2(0x0000100000000000ULL) == 44); 268 ATF_REQUIRE(ilog2(0x0000200000000000ULL) == 45); 269 ATF_REQUIRE(ilog2(0x0000400000000000ULL) == 46); 270 ATF_REQUIRE(ilog2(0x0000800000000000ULL) == 47); 271 ATF_REQUIRE(ilog2(0x0001000000000000ULL) == 48); 272 ATF_REQUIRE(ilog2(0x0002000000000000ULL) == 49); 273 ATF_REQUIRE(ilog2(0x0004000000000000ULL) == 50); 274 ATF_REQUIRE(ilog2(0x0008000000000000ULL) == 51); 275 ATF_REQUIRE(ilog2(0x0010000000000000ULL) == 52); 276 ATF_REQUIRE(ilog2(0x0020000000000000ULL) == 53); 277 ATF_REQUIRE(ilog2(0x0040000000000000ULL) == 54); 278 ATF_REQUIRE(ilog2(0x0080000000000000ULL) == 55); 279 ATF_REQUIRE(ilog2(0x0100000000000000ULL) == 56); 280 ATF_REQUIRE(ilog2(0x0200000000000000ULL) == 57); 281 ATF_REQUIRE(ilog2(0x0400000000000000ULL) == 58); 282 ATF_REQUIRE(ilog2(0x0800000000000000ULL) == 59); 283 ATF_REQUIRE(ilog2(0x1000000000000000ULL) == 60); 284 ATF_REQUIRE(ilog2(0x2000000000000000ULL) == 61); 285 ATF_REQUIRE(ilog2(0x4000000000000000ULL) == 62); 286 ATF_REQUIRE(ilog2(0x8000000000000000ULL) == 63); 287 288 ATF_REQUIRE(ilog2(0x0000000000000003ULL) == 1); 289 ATF_REQUIRE(ilog2(0x0000000000000007ULL) == 2); 290 ATF_REQUIRE(ilog2(0x000000000000000fULL) == 3); 291 ATF_REQUIRE(ilog2(0x000000000000001fULL) == 4); 292 ATF_REQUIRE(ilog2(0x000000000000003fULL) == 5); 293 ATF_REQUIRE(ilog2(0x000000000000007fULL) == 6); 294 ATF_REQUIRE(ilog2(0x00000000000000ffULL) == 7); 295 ATF_REQUIRE(ilog2(0x00000000000001ffULL) == 8); 296 ATF_REQUIRE(ilog2(0x00000000000003ffULL) == 9); 297 ATF_REQUIRE(ilog2(0x00000000000007ffULL) == 10); 298 ATF_REQUIRE(ilog2(0x0000000000000fffULL) == 11); 299 ATF_REQUIRE(ilog2(0x0000000000001fffULL) == 12); 300 ATF_REQUIRE(ilog2(0x0000000000003fffULL) == 13); 301 ATF_REQUIRE(ilog2(0x0000000000007fffULL) == 14); 302 ATF_REQUIRE(ilog2(0x000000000000ffffULL) == 15); 303 ATF_REQUIRE(ilog2(0x000000000001ffffULL) == 16); 304 ATF_REQUIRE(ilog2(0x000000000003ffffULL) == 17); 305 ATF_REQUIRE(ilog2(0x000000000007ffffULL) == 18); 306 ATF_REQUIRE(ilog2(0x00000000000fffffULL) == 19); 307 ATF_REQUIRE(ilog2(0x00000000001fffffULL) == 20); 308 ATF_REQUIRE(ilog2(0x00000000003fffffULL) == 21); 309 ATF_REQUIRE(ilog2(0x00000000007fffffULL) == 22); 310 ATF_REQUIRE(ilog2(0x0000000000ffffffULL) == 23); 311 ATF_REQUIRE(ilog2(0x0000000001ffffffULL) == 24); 312 ATF_REQUIRE(ilog2(0x0000000003ffffffULL) == 25); 313 ATF_REQUIRE(ilog2(0x0000000007ffffffULL) == 26); 314 ATF_REQUIRE(ilog2(0x000000000fffffffULL) == 27); 315 ATF_REQUIRE(ilog2(0x000000001fffffffULL) == 28); 316 ATF_REQUIRE(ilog2(0x000000003fffffffULL) == 29); 317 ATF_REQUIRE(ilog2(0x000000007fffffffULL) == 30); 318 ATF_REQUIRE(ilog2(0x00000000ffffffffULL) == 31); 319 ATF_REQUIRE(ilog2(0x00000001ffffffffULL) == 32); 320 ATF_REQUIRE(ilog2(0x00000003ffffffffULL) == 33); 321 ATF_REQUIRE(ilog2(0x00000007ffffffffULL) == 34); 322 ATF_REQUIRE(ilog2(0x0000000fffffffffULL) == 35); 323 ATF_REQUIRE(ilog2(0x0000001fffffffffULL) == 36); 324 ATF_REQUIRE(ilog2(0x0000003fffffffffULL) == 37); 325 ATF_REQUIRE(ilog2(0x0000007fffffffffULL) == 38); 326 ATF_REQUIRE(ilog2(0x000000ffffffffffULL) == 39); 327 ATF_REQUIRE(ilog2(0x000001ffffffffffULL) == 40); 328 ATF_REQUIRE(ilog2(0x000003ffffffffffULL) == 41); 329 ATF_REQUIRE(ilog2(0x000007ffffffffffULL) == 42); 330 ATF_REQUIRE(ilog2(0x00000fffffffffffULL) == 43); 331 ATF_REQUIRE(ilog2(0x00001fffffffffffULL) == 44); 332 ATF_REQUIRE(ilog2(0x00003fffffffffffULL) == 45); 333 ATF_REQUIRE(ilog2(0x00007fffffffffffULL) == 46); 334 ATF_REQUIRE(ilog2(0x0000ffffffffffffULL) == 47); 335 ATF_REQUIRE(ilog2(0x0001ffffffffffffULL) == 48); 336 ATF_REQUIRE(ilog2(0x0003ffffffffffffULL) == 49); 337 ATF_REQUIRE(ilog2(0x0007ffffffffffffULL) == 50); 338 ATF_REQUIRE(ilog2(0x000fffffffffffffULL) == 51); 339 ATF_REQUIRE(ilog2(0x001fffffffffffffULL) == 52); 340 ATF_REQUIRE(ilog2(0x003fffffffffffffULL) == 53); 341 ATF_REQUIRE(ilog2(0x007fffffffffffffULL) == 54); 342 ATF_REQUIRE(ilog2(0x00ffffffffffffffULL) == 55); 343 ATF_REQUIRE(ilog2(0x01ffffffffffffffULL) == 56); 344 ATF_REQUIRE(ilog2(0x03ffffffffffffffULL) == 57); 345 ATF_REQUIRE(ilog2(0x07ffffffffffffffULL) == 58); 346 ATF_REQUIRE(ilog2(0x0fffffffffffffffULL) == 59); 347 ATF_REQUIRE(ilog2(0x1fffffffffffffffULL) == 60); 348 ATF_REQUIRE(ilog2(0x3fffffffffffffffULL) == 61); 349 ATF_REQUIRE(ilog2(0x7fffffffffffffffULL) == 62); 350 ATF_REQUIRE(ilog2(0xffffffffffffffffULL) == 63); 351 } 352 353 ATF_TP_ADD_TCS(tp) 354 { 355 356 ATF_TP_ADD_TC(tp, bitmap_basic); 357 ATF_TP_ADD_TC(tp, fast_divide32); 358 ATF_TP_ADD_TC(tp, ffsfls); 359 ATF_TP_ADD_TC(tp, ilog2_32bit); 360 ATF_TP_ADD_TC(tp, ilog2_64bit); 361 ATF_TP_ADD_TC(tp, ilog2_const); 362 363 return atf_no_error(); 364 } 365