xref: /netbsd-src/tests/lib/libc/string/t_popcount.c (revision b1c86f5f087524e68db12794ee9c3e3da1ab17a0)
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