18b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* 28b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * Utility compute operations used by translated code. 38b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * 48b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * Copyright (c) 2007 Thiemo Seufer 58b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * Copyright (c) 2007 Jocelyn Mayer 68b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * 78b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * Permission is hereby granted, free of charge, to any person obtaining a copy 88b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * of this software and associated documentation files (the "Software"), to deal 98b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * in the Software without restriction, including without limitation the rights 108b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 118b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * copies of the Software, and to permit persons to whom the Software is 128b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * furnished to do so, subject to the following conditions: 138b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * 148b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * The above copyright notice and this permission notice shall be included in 158b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * all copies or substantial portions of the Software. 168b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * 178b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 188b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 198b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 208b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 218b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 228b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 238b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * THE SOFTWARE. 248b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project */ 258b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 268b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#include "osdep.h" 278b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 288b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#if defined(__x86_64__) 298b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#define __HAVE_FAST_MULU64__ 302910f183ddd5286911bc1e3499ea93cb57de8b75David 'Digit' Turnerstatic inline void mulu64(uint64_t *plow, uint64_t *phigh, 319251866320b5f8329a043bb56b3a794f78d12849David 'Digit' Turner uint64_t a, uint64_t b) 328b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 338b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project __asm__ ("mul %0\n\t" 348b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project : "=d" (*phigh), "=a" (*plow) 358b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project : "a" (a), "0" (b)); 368b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 378b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#define __HAVE_FAST_MULS64__ 382910f183ddd5286911bc1e3499ea93cb57de8b75David 'Digit' Turnerstatic inline void muls64(uint64_t *plow, uint64_t *phigh, 399251866320b5f8329a043bb56b3a794f78d12849David 'Digit' Turner int64_t a, int64_t b) 408b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 418b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project __asm__ ("imul %0\n\t" 428b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project : "=d" (*phigh), "=a" (*plow) 438b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project : "a" (a), "0" (b)); 448b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 458b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#else 468b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectvoid muls64(uint64_t *phigh, uint64_t *plow, int64_t a, int64_t b); 478b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectvoid mulu64(uint64_t *phigh, uint64_t *plow, uint64_t a, uint64_t b); 488b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#endif 498b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 508b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* Binary search for leading zeros. */ 518b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 522910f183ddd5286911bc1e3499ea93cb57de8b75David 'Digit' Turnerstatic inline int clz32(uint32_t val) 538b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 545d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner#if QEMU_GNUC_PREREQ(3, 4) 555d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner if (val) 565d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner return __builtin_clz(val); 575d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner else 585d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner return 32; 595d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner#else 608b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project int cnt = 0; 618b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 628b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (!(val & 0xFFFF0000U)) { 638b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project cnt += 16; 648b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val <<= 16; 658b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 668b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (!(val & 0xFF000000U)) { 678b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project cnt += 8; 688b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val <<= 8; 698b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 708b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (!(val & 0xF0000000U)) { 718b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project cnt += 4; 728b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val <<= 4; 738b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 748b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (!(val & 0xC0000000U)) { 758b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project cnt += 2; 768b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val <<= 2; 778b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 788b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (!(val & 0x80000000U)) { 798b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project cnt++; 808b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val <<= 1; 818b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 828b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (!(val & 0x80000000U)) { 838b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project cnt++; 848b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 858b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return cnt; 865d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner#endif 878b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 888b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 892910f183ddd5286911bc1e3499ea93cb57de8b75David 'Digit' Turnerstatic inline int clo32(uint32_t val) 908b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 918b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return clz32(~val); 928b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 938b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 942910f183ddd5286911bc1e3499ea93cb57de8b75David 'Digit' Turnerstatic inline int clz64(uint64_t val) 958b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 965d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner#if QEMU_GNUC_PREREQ(3, 4) 975d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner if (val) 985d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner return __builtin_clzll(val); 995d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner else 1005d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner return 64; 1015d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner#else 1028b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project int cnt = 0; 1038b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1048b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (!(val >> 32)) { 1058b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project cnt += 32; 1068b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } else { 1078b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val >>= 32; 1088b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 1098b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1108b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return cnt + clz32(val); 1115d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner#endif 1128b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 1138b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1142910f183ddd5286911bc1e3499ea93cb57de8b75David 'Digit' Turnerstatic inline int clo64(uint64_t val) 1158b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 1168b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return clz64(~val); 1178b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 1188b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1192910f183ddd5286911bc1e3499ea93cb57de8b75David 'Digit' Turnerstatic inline int ctz32(uint32_t val) 1208b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 1215d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner#if QEMU_GNUC_PREREQ(3, 4) 1225d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner if (val) 1235d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner return __builtin_ctz(val); 1245d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner else 1255d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner return 32; 1265d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner#else 1278b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project int cnt; 1288b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1298b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project cnt = 0; 1308b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (!(val & 0x0000FFFFUL)) { 1315d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner cnt += 16; 1328b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val >>= 16; 1335d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner } 1348b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (!(val & 0x000000FFUL)) { 1355d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner cnt += 8; 1368b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val >>= 8; 1375d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner } 1388b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (!(val & 0x0000000FUL)) { 1395d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner cnt += 4; 1408b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val >>= 4; 1415d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner } 1428b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (!(val & 0x00000003UL)) { 1435d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner cnt += 2; 1448b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val >>= 2; 1455d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner } 1468b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (!(val & 0x00000001UL)) { 1475d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner cnt++; 1488b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val >>= 1; 1495d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner } 1508b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (!(val & 0x00000001UL)) { 1515d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner cnt++; 1525d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner } 1535d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner 1545d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner return cnt; 1555d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner#endif 1565d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner} 1575d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner 1582910f183ddd5286911bc1e3499ea93cb57de8b75David 'Digit' Turnerstatic inline int cto32(uint32_t val) 1595d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner{ 1608b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return ctz32(~val); 1618b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 1628b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1632910f183ddd5286911bc1e3499ea93cb57de8b75David 'Digit' Turnerstatic inline int ctz64(uint64_t val) 1648b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 1655d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner#if QEMU_GNUC_PREREQ(3, 4) 1665d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner if (val) 1672910f183ddd5286911bc1e3499ea93cb57de8b75David 'Digit' Turner return __builtin_ctzll(val); 1685d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner else 1695d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner return 64; 1705d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner#else 1718b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project int cnt; 1728b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1738b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project cnt = 0; 1748b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (!((uint32_t)val)) { 1758b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project cnt += 32; 1768b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val >>= 32; 1778b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 1788b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1798b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return cnt + ctz32(val); 1805d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner#endif 1818b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 1828b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1832910f183ddd5286911bc1e3499ea93cb57de8b75David 'Digit' Turnerstatic inline int cto64(uint64_t val) 1848b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 1858b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return ctz64(~val); 1868b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 1878b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1882910f183ddd5286911bc1e3499ea93cb57de8b75David 'Digit' Turnerstatic inline int ctpop8(uint8_t val) 1898b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 1908b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val = (val & 0x55) + ((val >> 1) & 0x55); 1918b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val = (val & 0x33) + ((val >> 2) & 0x33); 1928b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val = (val & 0x0f) + ((val >> 4) & 0x0f); 1938b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1948b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return val; 1958b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 1968b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1972910f183ddd5286911bc1e3499ea93cb57de8b75David 'Digit' Turnerstatic inline int ctpop16(uint16_t val) 1988b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 1998b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val = (val & 0x5555) + ((val >> 1) & 0x5555); 2008b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val = (val & 0x3333) + ((val >> 2) & 0x3333); 2018b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val = (val & 0x0f0f) + ((val >> 4) & 0x0f0f); 2028b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val = (val & 0x00ff) + ((val >> 8) & 0x00ff); 2038b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2048b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return val; 2058b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 2068b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2072910f183ddd5286911bc1e3499ea93cb57de8b75David 'Digit' Turnerstatic inline int ctpop32(uint32_t val) 2088b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 2095d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner#if QEMU_GNUC_PREREQ(3, 4) 2105d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner return __builtin_popcount(val); 2115d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner#else 2128b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val = (val & 0x55555555) + ((val >> 1) & 0x55555555); 2138b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val = (val & 0x33333333) + ((val >> 2) & 0x33333333); 2148b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val = (val & 0x0f0f0f0f) + ((val >> 4) & 0x0f0f0f0f); 2158b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val = (val & 0x00ff00ff) + ((val >> 8) & 0x00ff00ff); 2168b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val = (val & 0x0000ffff) + ((val >> 16) & 0x0000ffff); 2178b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2188b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return val; 2195d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner#endif 2208b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 2218b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2222910f183ddd5286911bc1e3499ea93cb57de8b75David 'Digit' Turnerstatic inline int ctpop64(uint64_t val) 2238b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 2245d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner#if QEMU_GNUC_PREREQ(3, 4) 2255d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner return __builtin_popcountll(val); 2265d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner#else 2278b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val = (val & 0x5555555555555555ULL) + ((val >> 1) & 0x5555555555555555ULL); 2288b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val = (val & 0x3333333333333333ULL) + ((val >> 2) & 0x3333333333333333ULL); 2298b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val = (val & 0x0f0f0f0f0f0f0f0fULL) + ((val >> 4) & 0x0f0f0f0f0f0f0f0fULL); 2308b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val = (val & 0x00ff00ff00ff00ffULL) + ((val >> 8) & 0x00ff00ff00ff00ffULL); 2318b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val = (val & 0x0000ffff0000ffffULL) + ((val >> 16) & 0x0000ffff0000ffffULL); 2328b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project val = (val & 0x00000000ffffffffULL) + ((val >> 32) & 0x00000000ffffffffULL); 2338b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2348b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return val; 2355d8f37ad78fc66901af50c762029a501561f3b23David 'Digit' Turner#endif 2368b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 237