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