1 /* 2 * University of Illinois/NCSA Open Source License 3 * 4 * Copyright (c) 2003-2012 University of Illinois at Urbana-Champaign. 5 * All rights reserved. 6 * 7 * Developed by: 8 * 9 * LLVM Team 10 * 11 * University of Illinois at Urbana-Champaign 12 * 13 * http://llvm.org 14 * 15 * Permission is hereby granted, free of charge, to any person obtaining a copy 16 * of this software and associated documentation files (the "Software"), to deal 17 * with the Software without restriction, including without limitation the 18 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or 19 * sell copies of the Software, and to permit persons to whom the Software is 20 * furnished to do so, subject to the following conditions: 21 * 22 * * Redistributions of source code must retain the above copyright notice, 23 * this list of conditions and the following disclaimers. 24 * 25 * * Redistributions in binary form must reproduce the above copyright 26 * notice, this list of conditions and the following disclaimers in the 27 * documentation and/or other materials provided with the distribution. 28 * 29 * * Neither the names of the LLVM Team, University of Illinois at 30 * Urbana-Champaign, nor the names of its contributors may be used to 31 * endorse or promote products derived from this Software without specific 32 * prior written permission. 33 * 34 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 35 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 36 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 37 * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 38 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 39 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH 40 * THE SOFTWARE. 41 */ 42 43 /* 44 * C compiler runtime logic for popcount() related builtins taken from LLVM. See 45 * also the Hacker's Delight 2nd Edition. 46 */ 47 48 int 49 __popcountdi2(unsigned long long val) 50 { 51 unsigned long long x2 = (unsigned long long)val; 52 x2 = x2 - ((x2 >> 1) & 0x5555555555555555uLL); 53 /* Every 2 bits holds the sum of every pair of bits (32) */ 54 x2 = ((x2 >> 2) & 0x3333333333333333uLL) + (x2 & 0x3333333333333333uLL); 55 /* 56 * Every 4 bits holds the sum of every 4-set of bits (3 significant 57 * bits) (16) 58 */ 59 x2 = (x2 + (x2 >> 4)) & 0x0F0F0F0F0F0F0F0FuLL; 60 /* 61 * Every 8 bits holds the sum of every 8-set of bits (4 significant 62 * bits) (8). 63 */ 64 unsigned x = (unsigned)(x2 + (x2 >> 32)); 65 /* 66 * The lower 32 bits hold four 16 bit sums (5 significant bits). The 67 * upper 32 bits are garbage. 68 */ 69 x = x + (x >> 16); 70 /* 71 * The lower 16 bits hold two 32 bit sums (6 significant bits). The 72 * upper 16 bits are garbage. Extract the 7 significant bits. 73 */ 74 return ((x + (x >> 8)) & 0x0000007F); 75 } 76 77 int 78 __popcountsi2(unsigned val) 79 { 80 unsigned x = (unsigned)val; 81 x = x - ((x >> 1) & 0x55555555); 82 /* Every 2 bits holds the sum of every pair of bits */ 83 x = ((x >> 2) & 0x33333333) + (x & 0x33333333); 84 /* 85 * Every 4 bits holds the sum of every 4-set of bits (3 significant 86 * bits). 87 */ 88 x = (x + (x >> 4)) & 0x0F0F0F0F; 89 /* 90 * Every 8 bits holds the sum of every 8-set of bits (4 significant 91 * bits). 92 */ 93 x = (x + (x >> 16)); 94 /* 95 * The lower 16 bits hold two 8 bit sums (5 significant bits). The 96 * upper 16 bits are garbage. Extract the 6 significant bits. 97 */ 98 return ((x + (x >> 8)) & 0x0000003F); /* (6 significant bits) */ 99 } 100