1 /* $NetBSD: t_popcount.c,v 1.3 2010/12/26 13:29:47 pgoyette 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.3 2010/12/26 13:29:47 pgoyette 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(t_popcount); 133 134 ATF_TC_HEAD(t_popcount, tc) 135 { 136 137 atf_tc_set_md_var(tc, "descr", "Test popcount results"); 138 atf_tc_set_md_var(tc, "timeout", "0"); 139 } 140 141 ATF_TC_BODY(t_popcount, tc) 142 { 143 unsigned int i, r; 144 145 popcount_init(atf_tc_get_config_var_wd(tc, "run_popcount", "NO")); 146 147 for (i = 0; i < 0xffffffff; ++i) { 148 r = byte_count[i & 255] + byte_count[(i >> 8) & 255] 149 + byte_count[(i >> 16) & 255] 150 + byte_count[(i >> 24) & 255]; 151 152 ATF_CHECK_EQ(r, popcount(i)); 153 } 154 ATF_CHECK_EQ(popcount(0xffffffff), 32); 155 } 156 157 ATF_TC(t_popcountll); 158 ATF_TC_HEAD(t_popcountll, tc) 159 { 160 161 atf_tc_set_md_var(tc, "descr", "Test popcountll results"); 162 atf_tc_set_md_var(tc, "timeout", "0"); 163 } 164 165 ATF_TC_BODY(t_popcountll, tc) 166 { 167 unsigned int i, j, r, r2, p; 168 unsigned long long v; 169 170 popcount_init(atf_tc_get_config_var_wd(tc, "run_popcount", "NO")); 171 172 for (j = 0; j < 256; ++j) { 173 p = test_parts[j]; 174 r2 = byte_count[p & 255] + byte_count[(p >> 8) & 255] 175 + byte_count[(p >> 16) & 255] 176 + byte_count[(p >> 24) & 255]; 177 178 for (i = 0; i < 0xffffffff; ++i) { 179 r = byte_count[i & 255] + byte_count[(i >> 8) & 255] 180 + byte_count[(i >> 16) & 255] 181 + byte_count[(i >> 24) & 255] + r2; 182 183 v = (((unsigned long long)i) << 32) + p; 184 ATF_CHECK_EQ(r, popcountll(v)); 185 v = (((unsigned long long)p) << 32) + i; 186 ATF_CHECK_EQ(r, popcountll(v)); 187 } 188 } 189 190 ATF_CHECK_EQ(popcountll(0xffffffffffffffffULL), 64); 191 } 192 193 ATF_TP_ADD_TCS(tp) 194 { 195 ATF_TP_ADD_TC(tp, t_popcount); 196 ATF_TP_ADD_TC(tp, t_popcountll); 197 198 return atf_no_error(); 199 } 200