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
40static unsigned int byte_count[256];
41
42static void
43popcount_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
65unsigned 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
132ATF_TC(popcount_basic);
133ATF_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
140ATF_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
156ATF_TC(popcountll_basic);
157ATF_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
164ATF_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
192ATF_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