popcount64.c revision 1.4.2.2
1 1.4.2.2 jym /* $NetBSD: popcount64.c,v 1.4.2.2 2009/07/23 23:31:35 jym Exp $ */ 2 1.4.2.2 jym /*- 3 1.4.2.2 jym * Copyright (c) 2009 The NetBSD Foundation, Inc. 4 1.4.2.2 jym * All rights reserved. 5 1.4.2.2 jym * 6 1.4.2.2 jym * This code is derived from software contributed to The NetBSD Foundation 7 1.4.2.2 jym * by Joerg Sonnenberger. 8 1.4.2.2 jym * 9 1.4.2.2 jym * Redistribution and use in source and binary forms, with or without 10 1.4.2.2 jym * modification, are permitted provided that the following conditions 11 1.4.2.2 jym * are met: 12 1.4.2.2 jym * 13 1.4.2.2 jym * 1. Redistributions of source code must retain the above copyright 14 1.4.2.2 jym * notice, this list of conditions and the following disclaimer. 15 1.4.2.2 jym * 2. Redistributions in binary form must reproduce the above copyright 16 1.4.2.2 jym * notice, this list of conditions and the following disclaimer in 17 1.4.2.2 jym * the documentation and/or other materials provided with the 18 1.4.2.2 jym * distribution. 19 1.4.2.2 jym * 20 1.4.2.2 jym * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 21 1.4.2.2 jym * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 22 1.4.2.2 jym * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 23 1.4.2.2 jym * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 24 1.4.2.2 jym * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 25 1.4.2.2 jym * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 26 1.4.2.2 jym * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 27 1.4.2.2 jym * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 28 1.4.2.2 jym * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 29 1.4.2.2 jym * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 30 1.4.2.2 jym * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 1.4.2.2 jym * SUCH DAMAGE. 32 1.4.2.2 jym */ 33 1.4.2.2 jym 34 1.4.2.2 jym #include <sys/cdefs.h> 35 1.4.2.2 jym __RCSID("$NetBSD: popcount64.c,v 1.4.2.2 2009/07/23 23:31:35 jym Exp $"); 36 1.4.2.2 jym 37 1.4.2.2 jym #if !defined(_KERNEL) && !defined(_STANDALONE) 38 1.4.2.2 jym #include <limits.h> 39 1.4.2.2 jym #include <strings.h> 40 1.4.2.2 jym #else 41 1.4.2.2 jym #include <lib/libkern/libkern.h> 42 1.4.2.2 jym #include <machine/limits.h> 43 1.4.2.2 jym #endif 44 1.4.2.2 jym 45 1.4.2.2 jym /* 46 1.4.2.2 jym * If uint64_t is larger than size_t, the follow assumes that 47 1.4.2.2 jym * splitting into 32bit halfes is faster. 48 1.4.2.2 jym * 49 1.4.2.2 jym * The native pocount64 version is based on the same ideas as popcount64(3), 50 1.4.2.2 jym * see popcount64.c for comments. 51 1.4.2.2 jym */ 52 1.4.2.2 jym 53 1.4.2.2 jym #if SIZE_MAX < 0xffffffffffffffffULL 54 1.4.2.2 jym unsigned int 55 1.4.2.2 jym popcount64(uint64_t v) 56 1.4.2.2 jym { 57 1.4.2.2 jym return popcount32((uint32_t)(v >> 32)) + 58 1.4.2.2 jym popcount32((uint32_t)(v & 0xffffffffULL)); 59 1.4.2.2 jym } 60 1.4.2.2 jym #else 61 1.4.2.2 jym unsigned int 62 1.4.2.2 jym popcount64(uint64_t v) 63 1.4.2.2 jym { 64 1.4.2.2 jym unsigned int c; 65 1.4.2.2 jym 66 1.4.2.2 jym v = v - ((v >> 1) & 0x5555555555555555ULL); 67 1.4.2.2 jym v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL); 68 1.4.2.2 jym v = ((v + (v >> 4)) & 0x0f0f0f0f0f0f0f0fULL) * 0x0101010101010101ULL; 69 1.4.2.2 jym c = v >> 56; 70 1.4.2.2 jym 71 1.4.2.2 jym return c; 72 1.4.2.2 jym } 73 1.4.2.2 jym #endif 74 1.4.2.2 jym 75 1.4.2.2 jym #if ULONG_MAX == 0xffffffffffffffffULL 76 1.4.2.2 jym __strong_alias(popcountl, popcount64) 77 1.4.2.2 jym #endif 78 1.4.2.2 jym 79 1.4.2.2 jym #if ULLONG_MAX == 0xffffffffffffffffULL 80 1.4.2.2 jym __strong_alias(popcountll, popcount64) 81 1.4.2.2 jym #endif 82 1.4.2.2 jym 83
Indexes created Thu Sep 25 16:09:42 GMT 2025