tests/include/sys/t_bitops.c

   1 /*      $NetBSD: t_bitops.c,v 1.16 2012/12/07 02:28:19 christos 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.16 2012/12/07 02:28:19 christos 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_basic);
 178 ATF_TC_HEAD(ilog2_basic, tc)
 179 {
 180         atf_tc_set_md_var(tc, "descr", "Test ilog2(3) for correctness");
 181 }
 182
 183 ATF_TC_BODY(ilog2_basic, tc)
 184 {
 185         uint64_t i, x;
 186
 187         for (i = x = 0; i < 64; i++) {
 188
 189                 x = (uint64_t)1 << i;
 190
 191                 ATF_REQUIRE(i == (uint64_t)ilog2(x));
 192         }
 193 }
 194
 195 ATF_TC(ilog2_log2);
 196 ATF_TC_HEAD(ilog2_log2, tc)
 197 {
 198         atf_tc_set_md_var(tc, "descr", "Test log2(3) vs. ilog2(3)");
 199 }
 200
 201 ATF_TC_BODY(ilog2_log2, tc)
 202 {
 203 #ifdef __vax__
 204         atf_tc_skip("Test is unavailable on vax because of lack of log2()");
 205 #else
 206         double  x, y;
 207         uint64_t i;
 208
 209         /*
 210          * This may fail under QEMU; see PR misc/44767.
 211          */
 212         for (i = 1; i < UINT32_MAX; i += UINT16_MAX) {
 213
 214                 x = log2(i);
 215                 y = (double)(ilog2(i));
 216
 217                 ATF_REQUIRE(ceil(x) >= y);
 218
 219                 if (fabs(floor(x) - y) > 1.0e-40) {
 220                         atf_tc_expect_fail("PR misc/44767");
 221                         atf_tc_fail("log2(%"PRIu64") != "
 222                             "ilog2(%"PRIu64")", i, i);
 223                 }
 224         }
 225 #endif
 226 }
 227
 228 ATF_TP_ADD_TCS(tp)
 229 {
 230
 231         ATF_TP_ADD_TC(tp, bitmap_basic);
 232         ATF_TP_ADD_TC(tp, fast_divide32);
 233         ATF_TP_ADD_TC(tp, ffsfls);
 234         ATF_TP_ADD_TC(tp, ilog2_basic);
 235         ATF_TP_ADD_TC(tp, ilog2_log2);
 236
 237         return atf_no_error();
 238 }