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
popcount_init(const char * cfg_var)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);
ATF_TC_HEAD(popcount_basic,tc)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
ATF_TC_BODY(popcount_basic,tc)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);
ATF_TC_HEAD(popcountll_basic,tc)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
ATF_TC_BODY(popcountll_basic,tc)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
ATF_TP_ADD_TCS(tp)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