tests/lib/libc/string/t_popcount.c

   1 /*      $NetBSD: t_popcount.c,v 1.1 2009/07/21 13:18:44 joerg 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.1 2009/07/21 13:18:44 joerg 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 }