1 /* $NetBSD: t_popcount.c,v 1.2 2009/07/21 21:45:33 drochner 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.2 2009/07/21 21:45:33 drochner 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(void) 44 { 45 unsigned int i, j; 46 47 for (i = 0; i < 256; ++i) { 48 byte_count[i] = 0; 49 for (j = i; j != 0; j >>= 1) { 50 if (j & 1) 51 ++byte_count[i]; 52 } 53 } 54 } 55 56 unsigned int test_parts[256] = { 57 0x318e53e6U, 0x11710316U, 0x62608ffaU, 0x67e0f562U, 58 0xe432e82cU, 0x9862e8b2U, 0x7d96a627U, 0x3f74ad31U, 59 0x3cecf906U, 0xcdc0dcb4U, 0x241dab64U, 0x31e6133eU, 60 0x23086ad4U, 0x721d5a91U, 0xc483da53U, 0x6a62af52U, 61 0xf3f5c386U, 0xe0de3f77U, 0x65afe528U, 0xf4816485U, 62 0x40ccbf08U, 0x25df49c1U, 0xae5a6ee0U, 0xab36ccadU, 63 0x87e1ec29U, 0x60ca2407U, 0x49d62e47U, 0xa09f2df5U, 64 0xaf4c1c68U, 0x8ef08d50U, 0x624cfd2fU, 0xa6a36f20U, 65 0x68aaf879U, 0x0fe9deabU, 0x5c9a4060U, 0x215d8f08U, 66 0x55e84712U, 0xea1f1681U, 0x3a10b8a1U, 0x08e06632U, 67 0xcbc875e2U, 0x31e53258U, 0xcd3807a4U, 0xb9d17516U, 68 0x8fbfd9abU, 0x6651b555U, 0x550fb381U, 0x05061b9dU, 69 0x35aef3f2U, 0x9175078cU, 0xae0f14daU, 0x92a2d5f8U, 70 0x70d968feU, 0xe86f41c5U, 0x5cfaf39fU, 0x8499b18dU, 71 0xb33f879aU, 0x0a68ad3dU, 0x9323ecc1U, 0x060037ddU, 72 0xb91a5051U, 0xa0dbebf6U, 0x3e6aa6f1U, 0x7b422b5bU, 73 0x599e811eU, 0x199f7594U, 0xca453365U, 0x1cda6f48U, 74 0xe9c75d2cU, 0x6a873217U, 0x79c45d72U, 0x143b8e37U, 75 0xa11df26eU, 0xaf31f80aU, 0x311bf759U, 0x2378563cU, 76 0x9ab95fa5U, 0xfcf4d47cU, 0x1f7db268U, 0xd64b09e1U, 77 0xad7936daU, 0x7a59005cU, 0x45b173d3U, 0xc1a71b32U, 78 0x7d9f0de2U, 0xa9ac3792U, 0x9e7f9966U, 0x7f0b8080U, 79 0xece6c06fU, 0x78d92a3cU, 0x6d5f8f6cU, 0xc50ca544U, 80 0x5d8ded27U, 0xd27a8462U, 0x4bcd13ccU, 0xd49075f2U, 81 0xa8d52acfU, 0x41915d97U, 0x564f7062U, 0xefb046e2U, 82 0xe296277aU, 0x605b0ea3U, 0x10b2c3a1U, 0x4e8e5c66U, 83 0x4bd8ec04U, 0x29935be9U, 0x381839f3U, 0x555d8824U, 84 0xd6befddbU, 0x5d8d6d6eU, 0xb2fdb7b4U, 0xb471c8fcU, 85 0xc2fd325bU, 0x932d2487U, 0xbdbbadefU, 0x66c8895dU, 86 0x5d77857aU, 0x259f1cc0U, 0x302037faU, 0xda9aa7a8U, 87 0xb112c6aaU, 0x78f74192U, 0xfd4da741U, 0xfa5765c1U, 88 0x6ea1bc5cU, 0xd283f39cU, 0x268ae67dU, 0xdedcd134U, 89 0xbbf92410U, 0x6b45fb55U, 0x2f75ac71U, 0x64bf2ca5U, 90 0x8b99675aU, 0x3f4923b6U, 0x7e610550U, 0x04b1c06dU, 91 0x8f92e7c6U, 0x45cb608bU, 0x2d06d1f2U, 0x79cf387aU, 92 0xfd3ed225U, 0x243eee20U, 0x2cbefc6fU, 0x8286cbaaU, 93 0x70d4c182U, 0x054e3cc6U, 0xb66c5362U, 0x0c73fa5dU, 94 0x539948feU, 0xec638563U, 0x0cf04ab6U, 0xec7b52f4U, 95 0x58eeffceU, 0x6fe8049aU, 0xb3b33332U, 0x2e33bfdbU, 96 0xcc817567U, 0x71ac57c8U, 0x4bab3ac7U, 0x327c558bU, 97 0x82a6d279U, 0x5adf71daU, 0x1074a656U, 0x3c533c1fU, 98 0x82fdbe69U, 0x21b4f6afU, 0xd59580e8U, 0x0de824ebU, 99 0xa510941bU, 0x7cd91144U, 0xa8c10631U, 0x4c839267U, 100 0x5d503c2fU, 0xe1567d55U, 0x23910cc7U, 0xdb1bdc34U, 101 0x2a866704U, 0x33e21f0cU, 0x5c7681b4U, 0x818651caU, 102 0xb1d18162U, 0x225ad014U, 0xadf7d6baU, 0xac548d9bU, 103 0xe94736e5U, 0x2279c5f1U, 0x33215d2cU, 0xdc8ab90eU, 104 0xf5e3d7f2U, 0xedcb15cfU, 0xc9a43c4cU, 0xfc678fc6U, 105 0x43796b95U, 0x3f8b700cU, 0x867bbc72U, 0x81f71fecU, 106 0xd00cad7dU, 0x302c458fU, 0x8ae21accU, 0x05850ce8U, 107 0x7764d8e8U, 0x8a36cd68U, 0x40b44bd7U, 0x1cffaeb7U, 108 0x2b248f34U, 0x1eefdbafU, 0x574d7437U, 0xe86cd935U, 109 0xf53dd1c8U, 0x1b022513U, 0xef2d249bU, 0x94fb2b08U, 110 0x15d3eff8U, 0x14245e1bU, 0x82aa8425U, 0x53959028U, 111 0x9c5f9b80U, 0x325e0c82U, 0x3e236c24U, 0x74e1dd36U, 112 0x9890df3fU, 0xaf9701a2U, 0x023b3413U, 0x7634c67eU, 113 0x55cf5e45U, 0x56d2a95bU, 0xb6db869bU, 0xac19e260U, 114 0xdd310740U, 0x26d68f84U, 0x45bebf17U, 0xe4a7728fU, 115 0xf082e66eU, 0xb2fe3c10U, 0x2db1fa2cU, 0x4b3dfcfaU, 116 0xc7b3a672U, 0xaeadc67bU, 0x6cce6f2bU, 0x8263dbbfU, 117 0xd9724d5bU, 0xbcc767b5U, 0x8d563798U, 0x2db764b4U, 118 0x76e0cee7U, 0xd34f9a67U, 0x035c810aU, 0x3f56bdc1U, 119 0x5b3f2c84U, 0x0baca8c0U, 0xfe979a77U, 0x484ca775U, 120 0xbdc7f104U, 0xc06c3efbU, 0xdbc5f32cU, 0x44b017e7U, 121 }; 122 123 ATF_TC(t_popcount); 124 ATF_TC(t_popcountll); 125 126 ATF_TC_HEAD(t_popcount, tc) 127 { 128 atf_tc_set_md_var(tc, "descr", "Test popcount results"); 129 atf_tc_set_md_var(tc, "timeout", "0"); 130 } 131 132 ATF_TC_HEAD(t_popcountll, tc) 133 { 134 atf_tc_set_md_var(tc, "descr", "Test popcountll results"); 135 atf_tc_set_md_var(tc, "timeout", "0"); 136 } 137 138 ATF_TC_BODY(t_popcount, tc) 139 { 140 unsigned int i, r; 141 142 popcount_init(); 143 144 for (i = 0; i < 0xffffffff; ++i) { 145 r = byte_count[i & 255] + byte_count[(i >> 8) & 255] 146 + byte_count[(i >> 16) & 255] 147 + byte_count[(i >> 24) & 255]; 148 149 ATF_CHECK_EQ(r, popcount(i)); 150 } 151 ATF_CHECK_EQ(popcount(0xffffffff), 32); 152 } 153 154 ATF_TC_BODY(t_popcountll, tc) 155 { 156 unsigned int i, j, r, r2, p; 157 unsigned long long v; 158 159 popcount_init(); 160 161 for (j = 0; j < 256; ++j) { 162 p = test_parts[j]; 163 r2 = byte_count[p & 255] + byte_count[(p >> 8) & 255] 164 + byte_count[(p >> 16) & 255] 165 + byte_count[(p >> 24) & 255]; 166 167 for (i = 0; i < 0xffffffff; ++i) { 168 r = byte_count[i & 255] + byte_count[(i >> 8) & 255] 169 + byte_count[(i >> 16) & 255] 170 + byte_count[(i >> 24) & 255] + r2; 171 172 v = (((unsigned long long)i) << 32) + p; 173 ATF_CHECK_EQ(r, popcountll(v)); 174 v = (((unsigned long long)p) << 32) + i; 175 ATF_CHECK_EQ(r, popcountll(v)); 176 } 177 } 178 179 ATF_CHECK_EQ(popcountll(0xffffffffffffffffULL), 64); 180 } 181 182 ATF_TP_ADD_TCS(tp) 183 { 184 ATF_TP_ADD_TC(tp, t_popcount); 185 ATF_TP_ADD_TC(tp, t_popcountll); 186 187 return atf_no_error(); 188 } 189