tests/lib/libc/string/t_popcount.c

   1 /*      $NetBSD: t_popcount.c,v 1.4 2011/07/07 08:27:36 jruoho Exp $    */
   2 /*-
   3  * Copyright (c) 2009 The NetBSD Foundation, Inc.
   4  * All rights reserved.
   5  *
   6  * This code is derived from software contributed to The NetBSD Foundation
   7  * by Joerg Sonnenberger.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  *
  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
  17  *    the documentation and/or other materials provided with the
  18  *    distribution.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  24  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  25  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  28  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  29  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  30  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  */
  33
  34 #include <sys/cdefs.h>
  35 __RCSID("$NetBSD: t_popcount.c,v 1.4 2011/07/07 08:27:36 jruoho Exp $");
  36
  37 #include <atf-c.h>
  38 #include <strings.h>
  39
  40 static unsigned int byte_count[256];
  41
  42 static void
  43 popcount_init(const char *cfg_var)
  44 {
  45         unsigned int i, j;
  46
  47         if (strcasecmp(cfg_var, "YES")  == 0 ||
  48             strcasecmp(cfg_var, "Y")    == 0 ||
  49             strcasecmp(cfg_var, "1")    == 0 ||
  50             strcasecmp(cfg_var, "T")    == 0 ||
  51             strcasecmp(cfg_var, "TRUE") == 0) {
  52                 for (i = 0; i < 256; ++i) {
  53                         byte_count[i] = 0;
  54                         for (j = i; j != 0; j >>= 1) {
  55                                 if (j & 1)
  56                                         ++byte_count[i];
  57                         }
  58                 }
  59                 return;
  60         }
  61
  62         atf_tc_skip("config variable \"run_popcount\" not set to YES/TRUE");
  63 }
  64
  65 unsigned int test_parts[256] = {
  66         0x318e53e6U, 0x11710316U, 0x62608ffaU, 0x67e0f562U,
  67         0xe432e82cU, 0x9862e8b2U, 0x7d96a627U, 0x3f74ad31U,
  68         0x3cecf906U, 0xcdc0dcb4U, 0x241dab64U, 0x31e6133eU,
  69         0x23086ad4U, 0x721d5a91U, 0xc483da53U, 0x6a62af52U,
  70         0xf3f5c386U, 0xe0de3f77U, 0x65afe528U, 0xf4816485U,
  71         0x40ccbf08U, 0x25df49c1U, 0xae5a6ee0U, 0xab36ccadU,
  72         0x87e1ec29U, 0x60ca2407U, 0x49d62e47U, 0xa09f2df5U,
  73         0xaf4c1c68U, 0x8ef08d50U, 0x624cfd2fU, 0xa6a36f20U,
  74         0x68aaf879U, 0x0fe9deabU, 0x5c9a4060U, 0x215d8f08U,
  75         0x55e84712U, 0xea1f1681U, 0x3a10b8a1U, 0x08e06632U,
  76         0xcbc875e2U, 0x31e53258U, 0xcd3807a4U, 0xb9d17516U,
  77         0x8fbfd9abU, 0x6651b555U, 0x550fb381U, 0x05061b9dU,
  78         0x35aef3f2U, 0x9175078cU, 0xae0f14daU, 0x92a2d5f8U,
  79         0x70d968feU, 0xe86f41c5U, 0x5cfaf39fU, 0x8499b18dU,
  80         0xb33f879aU, 0x0a68ad3dU, 0x9323ecc1U, 0x060037ddU,
  81         0xb91a5051U, 0xa0dbebf6U, 0x3e6aa6f1U, 0x7b422b5bU,
  82         0x599e811eU, 0x199f7594U, 0xca453365U, 0x1cda6f48U,
  83         0xe9c75d2cU, 0x6a873217U, 0x79c45d72U, 0x143b8e37U,
  84         0xa11df26eU, 0xaf31f80aU, 0x311bf759U, 0x2378563cU,
  85         0x9ab95fa5U, 0xfcf4d47cU, 0x1f7db268U, 0xd64b09e1U,
  86         0xad7936daU, 0x7a59005cU, 0x45b173d3U, 0xc1a71b32U,
  87         0x7d9f0de2U, 0xa9ac3792U, 0x9e7f9966U, 0x7f0b8080U,
  88         0xece6c06fU, 0x78d92a3cU, 0x6d5f8f6cU, 0xc50ca544U,
  89         0x5d8ded27U, 0xd27a8462U, 0x4bcd13ccU, 0xd49075f2U,
  90         0xa8d52acfU, 0x41915d97U, 0x564f7062U, 0xefb046e2U,
  91         0xe296277aU, 0x605b0ea3U, 0x10b2c3a1U, 0x4e8e5c66U,
  92         0x4bd8ec04U, 0x29935be9U, 0x381839f3U, 0x555d8824U,
  93         0xd6befddbU, 0x5d8d6d6eU, 0xb2fdb7b4U, 0xb471c8fcU,
  94         0xc2fd325bU, 0x932d2487U, 0xbdbbadefU, 0x66c8895dU,
  95         0x5d77857aU, 0x259f1cc0U, 0x302037faU, 0xda9aa7a8U,
  96         0xb112c6aaU, 0x78f74192U, 0xfd4da741U, 0xfa5765c1U,
  97         0x6ea1bc5cU, 0xd283f39cU, 0x268ae67dU, 0xdedcd134U,
  98         0xbbf92410U, 0x6b45fb55U, 0x2f75ac71U, 0x64bf2ca5U,
  99         0x8b99675aU, 0x3f4923b6U, 0x7e610550U, 0x04b1c06dU,
 100         0x8f92e7c6U, 0x45cb608bU, 0x2d06d1f2U, 0x79cf387aU,
 101         0xfd3ed225U, 0x243eee20U, 0x2cbefc6fU, 0x8286cbaaU,
 102         0x70d4c182U, 0x054e3cc6U, 0xb66c5362U, 0x0c73fa5dU,
 103         0x539948feU, 0xec638563U, 0x0cf04ab6U, 0xec7b52f4U,
 104         0x58eeffceU, 0x6fe8049aU, 0xb3b33332U, 0x2e33bfdbU,
 105         0xcc817567U, 0x71ac57c8U, 0x4bab3ac7U, 0x327c558bU,
 106         0x82a6d279U, 0x5adf71daU, 0x1074a656U, 0x3c533c1fU,
 107         0x82fdbe69U, 0x21b4f6afU, 0xd59580e8U, 0x0de824ebU,
 108         0xa510941bU, 0x7cd91144U, 0xa8c10631U, 0x4c839267U,
 109         0x5d503c2fU, 0xe1567d55U, 0x23910cc7U, 0xdb1bdc34U,
 110         0x2a866704U, 0x33e21f0cU, 0x5c7681b4U, 0x818651caU,
 111         0xb1d18162U, 0x225ad014U, 0xadf7d6baU, 0xac548d9bU,
 112         0xe94736e5U, 0x2279c5f1U, 0x33215d2cU, 0xdc8ab90eU,
 113         0xf5e3d7f2U, 0xedcb15cfU, 0xc9a43c4cU, 0xfc678fc6U,
 114         0x43796b95U, 0x3f8b700cU, 0x867bbc72U, 0x81f71fecU,
 115         0xd00cad7dU, 0x302c458fU, 0x8ae21accU, 0x05850ce8U,
 116         0x7764d8e8U, 0x8a36cd68U, 0x40b44bd7U, 0x1cffaeb7U,
 117         0x2b248f34U, 0x1eefdbafU, 0x574d7437U, 0xe86cd935U,
 118         0xf53dd1c8U, 0x1b022513U, 0xef2d249bU, 0x94fb2b08U,
 119         0x15d3eff8U, 0x14245e1bU, 0x82aa8425U, 0x53959028U,
 120         0x9c5f9b80U, 0x325e0c82U, 0x3e236c24U, 0x74e1dd36U,
 121         0x9890df3fU, 0xaf9701a2U, 0x023b3413U, 0x7634c67eU,
 122         0x55cf5e45U, 0x56d2a95bU, 0xb6db869bU, 0xac19e260U,
 123         0xdd310740U, 0x26d68f84U, 0x45bebf17U, 0xe4a7728fU,
 124         0xf082e66eU, 0xb2fe3c10U, 0x2db1fa2cU, 0x4b3dfcfaU,
 125         0xc7b3a672U, 0xaeadc67bU, 0x6cce6f2bU, 0x8263dbbfU,
 126         0xd9724d5bU, 0xbcc767b5U, 0x8d563798U, 0x2db764b4U,
 127         0x76e0cee7U, 0xd34f9a67U, 0x035c810aU, 0x3f56bdc1U,
 128         0x5b3f2c84U, 0x0baca8c0U, 0xfe979a77U, 0x484ca775U,
 129         0xbdc7f104U, 0xc06c3efbU, 0xdbc5f32cU, 0x44b017e7U,
 130 };
 131
 132 ATF_TC(popcount_basic);
 133 ATF_TC_HEAD(popcount_basic, tc)
 134 {
 135
 136         atf_tc_set_md_var(tc, "descr", "Test popcount results");
 137         atf_tc_set_md_var(tc, "timeout", "0");
 138 }
 139
 140 ATF_TC_BODY(popcount_basic, tc)
 141 {
 142         unsigned int i, r;
 143
 144         popcount_init(atf_tc_get_config_var_wd(tc, "run_popcount", "NO"));
 145
 146         for (i = 0; i < 0xffffffff; ++i) {
 147                 r = byte_count[i & 255] + byte_count[(i >> 8) & 255]
 148                     + byte_count[(i >> 16) & 255]
 149                     + byte_count[(i >> 24) & 255];
 150
 151                 ATF_CHECK_EQ(r, popcount(i));
 152         }
 153         ATF_CHECK_EQ(popcount(0xffffffff), 32);
 154 }
 155
 156 ATF_TC(popcountll_basic);
 157 ATF_TC_HEAD(popcountll_basic, tc)
 158 {
 159
 160         atf_tc_set_md_var(tc, "descr", "Test popcountll results");
 161         atf_tc_set_md_var(tc, "timeout", "0");
 162 }
 163
 164 ATF_TC_BODY(popcountll_basic, tc)
 165 {
 166         unsigned int i, j, r, r2, p;
 167         unsigned long long v;
 168
 169         popcount_init(atf_tc_get_config_var_wd(tc, "run_popcount", "NO"));
 170
 171         for (j = 0; j < 256; ++j) {
 172                 p = test_parts[j];
 173                 r2 = byte_count[p & 255] + byte_count[(p >> 8) & 255]
 174                     + byte_count[(p >> 16) & 255]
 175                     + byte_count[(p >> 24) & 255];
 176
 177                 for (i = 0; i < 0xffffffff; ++i) {
 178                         r = byte_count[i & 255] + byte_count[(i >> 8) & 255]
 179                             + byte_count[(i >> 16) & 255]
 180                             + byte_count[(i >> 24) & 255] + r2;
 181
 182                         v = (((unsigned long long)i) << 32) + p;
 183                         ATF_CHECK_EQ(r, popcountll(v));
 184                         v = (((unsigned long long)p) << 32) + i;
 185                         ATF_CHECK_EQ(r, popcountll(v));
 186                 }
 187         }
 188
 189         ATF_CHECK_EQ(popcountll(0xffffffffffffffffULL), 64);
 190 }
 191
 192 ATF_TP_ADD_TCS(tp)
 193 {
 194         ATF_TP_ADD_TC(tp, popcount_basic);
 195         ATF_TP_ADD_TC(tp, popcountll_basic);
 196
 197         return atf_no_error();
 198 }