bitfield.hh revision 14045
17375Sgblack@eecs.umich.edu/* 27375Sgblack@eecs.umich.edu * Copyright (c) 2017, 2019 ARM Limited 37375Sgblack@eecs.umich.edu * All rights reserved 47375Sgblack@eecs.umich.edu * 57375Sgblack@eecs.umich.edu * The license below extends only to copyright in the software and shall 67375Sgblack@eecs.umich.edu * not be construed as granting a license to any other intellectual 77375Sgblack@eecs.umich.edu * property including but not limited to intellectual property relating 87375Sgblack@eecs.umich.edu * to a hardware implementation of the functionality of the software 97375Sgblack@eecs.umich.edu * licensed hereunder. You may use the software subject to the license 107375Sgblack@eecs.umich.edu * terms below provided that you ensure that this notice is replicated 117375Sgblack@eecs.umich.edu * unmodified and in its entirety in all distributions of the software, 127375Sgblack@eecs.umich.edu * modified or unmodified, in source code or in binary form. 137375Sgblack@eecs.umich.edu * 147375Sgblack@eecs.umich.edu * Copyright (c) 2003-2005 The Regents of The University of Michigan 157375Sgblack@eecs.umich.edu * All rights reserved. 167375Sgblack@eecs.umich.edu * 177375Sgblack@eecs.umich.edu * Redistribution and use in source and binary forms, with or without 187375Sgblack@eecs.umich.edu * modification, are permitted provided that the following conditions are 197375Sgblack@eecs.umich.edu * met: redistributions of source code must retain the above copyright 207375Sgblack@eecs.umich.edu * notice, this list of conditions and the following disclaimer; 217375Sgblack@eecs.umich.edu * redistributions in binary form must reproduce the above copyright 227375Sgblack@eecs.umich.edu * notice, this list of conditions and the following disclaimer in the 237375Sgblack@eecs.umich.edu * documentation and/or other materials provided with the distribution; 247375Sgblack@eecs.umich.edu * neither the name of the copyright holders nor the names of its 257375Sgblack@eecs.umich.edu * contributors may be used to endorse or promote products derived from 267375Sgblack@eecs.umich.edu * this software without specific prior written permission. 277375Sgblack@eecs.umich.edu * 287375Sgblack@eecs.umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 297375Sgblack@eecs.umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 307375Sgblack@eecs.umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 317375Sgblack@eecs.umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 327375Sgblack@eecs.umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 337375Sgblack@eecs.umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 347375Sgblack@eecs.umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 357375Sgblack@eecs.umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 367375Sgblack@eecs.umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 377375Sgblack@eecs.umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 387375Sgblack@eecs.umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 397375Sgblack@eecs.umich.edu * 407375Sgblack@eecs.umich.edu * Authors: Steve Reinhardt 417375Sgblack@eecs.umich.edu * Nathan Binkert 427375Sgblack@eecs.umich.edu * Giacomo Travaglini 437375Sgblack@eecs.umich.edu */ 447378Sgblack@eecs.umich.edu 457378Sgblack@eecs.umich.edu#ifndef __BASE_BITFIELD_HH__ 467382Sgblack@eecs.umich.edu#define __BASE_BITFIELD_HH__ 477375Sgblack@eecs.umich.edu 487384Sgblack@eecs.umich.edu#include <inttypes.h> 497384Sgblack@eecs.umich.edu#include <cassert> 507384Sgblack@eecs.umich.edu#include <cstddef> 517375Sgblack@eecs.umich.edu#include <type_traits> 527375Sgblack@eecs.umich.edu 537375Sgblack@eecs.umich.edu/** Lookup table used for High Speed bit reversing */ 547375Sgblack@eecs.umich.eduextern const uint8_t reverseLookUpTable[]; 557375Sgblack@eecs.umich.edu 567375Sgblack@eecs.umich.edu/** 577375Sgblack@eecs.umich.edu * Generate a 64-bit mask of 'nbits' 1s, right justified. 587375Sgblack@eecs.umich.edu */ 597375Sgblack@eecs.umich.eduinline uint64_t 607375Sgblack@eecs.umich.edumask(int nbits) 617375Sgblack@eecs.umich.edu{ 627375Sgblack@eecs.umich.edu return (nbits == 64) ? (uint64_t)-1LL : (1ULL << nbits) - 1; 637375Sgblack@eecs.umich.edu} 647375Sgblack@eecs.umich.edu 657375Sgblack@eecs.umich.edu/** 667375Sgblack@eecs.umich.edu * Extract the bitfield from position 'first' to 'last' (inclusive) 677375Sgblack@eecs.umich.edu * from 'val' and right justify it. MSB is numbered 63, LSB is 0. 687375Sgblack@eecs.umich.edu */ 697375Sgblack@eecs.umich.edutemplate <class T> 707375Sgblack@eecs.umich.eduinline 717375Sgblack@eecs.umich.eduT 727375Sgblack@eecs.umich.edubits(T val, int first, int last) 737375Sgblack@eecs.umich.edu{ 747375Sgblack@eecs.umich.edu int nbits = first - last + 1; 757375Sgblack@eecs.umich.edu return (val >> last) & mask(nbits); 767375Sgblack@eecs.umich.edu} 777376Sgblack@eecs.umich.edu 787376Sgblack@eecs.umich.edu/** 797376Sgblack@eecs.umich.edu * Extract the bit from this position from 'val' and right justify it. 807375Sgblack@eecs.umich.edu */ 817375Sgblack@eecs.umich.edutemplate <class T> 827378Sgblack@eecs.umich.eduinline 837378Sgblack@eecs.umich.eduT 847378Sgblack@eecs.umich.edubits(T val, int bit) 857378Sgblack@eecs.umich.edu{ 867378Sgblack@eecs.umich.edu return bits(val, bit, bit); 877378Sgblack@eecs.umich.edu} 887378Sgblack@eecs.umich.edu 897378Sgblack@eecs.umich.edu/** 907378Sgblack@eecs.umich.edu * Mask off the given bits in place like bits() but without shifting. 917378Sgblack@eecs.umich.edu * msb = 63, lsb = 0 927378Sgblack@eecs.umich.edu */ 937378Sgblack@eecs.umich.edutemplate <class T> 947378Sgblack@eecs.umich.eduinline 957378Sgblack@eecs.umich.eduT 967378Sgblack@eecs.umich.edumbits(T val, int first, int last) 977378Sgblack@eecs.umich.edu{ 987378Sgblack@eecs.umich.edu return val & (mask(first+1) & ~mask(last)); 997378Sgblack@eecs.umich.edu} 1007378Sgblack@eecs.umich.edu 1017378Sgblack@eecs.umich.eduinline uint64_t 1027378Sgblack@eecs.umich.edumask(int first, int last) 1037378Sgblack@eecs.umich.edu{ 1047378Sgblack@eecs.umich.edu return mbits((uint64_t)-1LL, first, last); 1057378Sgblack@eecs.umich.edu} 1067378Sgblack@eecs.umich.edu 1077378Sgblack@eecs.umich.edu/** 1087382Sgblack@eecs.umich.edu * Sign-extend an N-bit value to 64 bits. 1097396Sgblack@eecs.umich.edu */ 1107396Sgblack@eecs.umich.edutemplate <int N> 1117396Sgblack@eecs.umich.eduinline 1127396Sgblack@eecs.umich.eduuint64_t 1137396Sgblack@eecs.umich.edusext(uint64_t val) 1147396Sgblack@eecs.umich.edu{ 1157396Sgblack@eecs.umich.edu int sign_bit = bits(val, N-1, N-1); 1167396Sgblack@eecs.umich.edu return sign_bit ? (val | ~mask(N)) : val; 1177396Sgblack@eecs.umich.edu} 1187396Sgblack@eecs.umich.edu 1197396Sgblack@eecs.umich.edu/** 1207396Sgblack@eecs.umich.edu * Return val with bits first to last set to bit_val 1217396Sgblack@eecs.umich.edu */ 1227396Sgblack@eecs.umich.edutemplate <class T, class B> 1237396Sgblack@eecs.umich.eduinline 1247396Sgblack@eecs.umich.eduT 1257396Sgblack@eecs.umich.eduinsertBits(T val, int first, int last, B bit_val) 1267396Sgblack@eecs.umich.edu{ 1277396Sgblack@eecs.umich.edu T t_bit_val = bit_val; 1287396Sgblack@eecs.umich.edu T bmask = mask(first - last + 1) << last; 1297396Sgblack@eecs.umich.edu return ((t_bit_val << last) & bmask) | (val & ~bmask); 1307397Sgblack@eecs.umich.edu} 1317397Sgblack@eecs.umich.edu 1327397Sgblack@eecs.umich.edu/** 1337397Sgblack@eecs.umich.edu * Overloaded for access to only one bit in value 1347397Sgblack@eecs.umich.edu */ 1357397Sgblack@eecs.umich.edutemplate <class T, class B> 1367397Sgblack@eecs.umich.eduinline 1377397Sgblack@eecs.umich.eduT 1387397Sgblack@eecs.umich.eduinsertBits(T val, int bit, B bit_val) 1397397Sgblack@eecs.umich.edu{ 1407397Sgblack@eecs.umich.edu return insertBits(val, bit, bit, bit_val); 1417397Sgblack@eecs.umich.edu} 1427397Sgblack@eecs.umich.edu 1437397Sgblack@eecs.umich.edu/** 1447397Sgblack@eecs.umich.edu * A convenience function to replace bits first to last of val with bit_val 1457397Sgblack@eecs.umich.edu * in place. 1467397Sgblack@eecs.umich.edu */ 1477384Sgblack@eecs.umich.edutemplate <class T, class B> 1487384Sgblack@eecs.umich.eduinline 1497384Sgblack@eecs.umich.eduvoid 1507384Sgblack@eecs.umich.edureplaceBits(T& val, int first, int last, B bit_val) 1517384Sgblack@eecs.umich.edu{ 1527384Sgblack@eecs.umich.edu val = insertBits(val, first, last, bit_val); 1537384Sgblack@eecs.umich.edu} 1547384Sgblack@eecs.umich.edu 1557384Sgblack@eecs.umich.edu/** Overloaded function to allow to access only 1 bit*/ 1567384Sgblack@eecs.umich.edutemplate <class T, class B> 1577384Sgblack@eecs.umich.eduinline 1587384Sgblack@eecs.umich.eduvoid 1597384Sgblack@eecs.umich.edureplaceBits(T& val, int bit, B bit_val) 1607384Sgblack@eecs.umich.edu{ 1617384Sgblack@eecs.umich.edu val = insertBits(val, bit, bit, bit_val); 1627384Sgblack@eecs.umich.edu} 1637384Sgblack@eecs.umich.edu 1647384Sgblack@eecs.umich.edu/** 1657384Sgblack@eecs.umich.edu * Takes a variable lenght word and returns the mirrored version 1667384Sgblack@eecs.umich.edu * (Bit by bit, LSB=>MSB). 1677384Sgblack@eecs.umich.edu * 1687384Sgblack@eecs.umich.edu * algorithm from 1697384Sgblack@eecs.umich.edu * http://graphics.stanford.edu/~seander/bithacks.html 1707384Sgblack@eecs.umich.edu * #ReverseBitsByLookupTable 1717384Sgblack@eecs.umich.edu * 1727384Sgblack@eecs.umich.edu * @param val: variable lenght word 1737384Sgblack@eecs.umich.edu * @param size: number of bytes to mirror 1747384Sgblack@eecs.umich.edu * @return mirrored word 1757384Sgblack@eecs.umich.edu */ 1767384Sgblack@eecs.umich.edutemplate <class T> 1777384Sgblack@eecs.umich.eduT 1787384Sgblack@eecs.umich.edureverseBits(T val, std::size_t size = sizeof(T)) 1797384Sgblack@eecs.umich.edu{ 1807384Sgblack@eecs.umich.edu static_assert(std::is_integral<T>::value, "Expecting an integer type"); 1817384Sgblack@eecs.umich.edu 1827384Sgblack@eecs.umich.edu assert(size <= sizeof(T)); 1837384Sgblack@eecs.umich.edu 1847384Sgblack@eecs.umich.edu T output = 0; 1857384Sgblack@eecs.umich.edu for (auto byte = 0; byte < size; byte++, val = static_cast<T>(val >> 8)) { 1867384Sgblack@eecs.umich.edu output = (output << 8) | reverseLookUpTable[val & 0xFF]; 1877384Sgblack@eecs.umich.edu } 1887384Sgblack@eecs.umich.edu 1897384Sgblack@eecs.umich.edu return output; 1907384Sgblack@eecs.umich.edu} 1917384Sgblack@eecs.umich.edu 1927384Sgblack@eecs.umich.edu/** 1937384Sgblack@eecs.umich.edu * Returns the bit position of the MSB that is set in the input 1947384Sgblack@eecs.umich.edu */ 1957396Sgblack@eecs.umich.eduinline 1967396Sgblack@eecs.umich.eduint 1977430Sgblack@eecs.umich.edufindMsbSet(uint64_t val) { 1987430Sgblack@eecs.umich.edu int msb = 0; 1997396Sgblack@eecs.umich.edu if (!val) 2007384Sgblack@eecs.umich.edu return 0; 2017430Sgblack@eecs.umich.edu if (bits(val, 63,32)) { msb += 32; val >>= 32; } 2027386Sgblack@eecs.umich.edu if (bits(val, 31,16)) { msb += 16; val >>= 16; } 2037386Sgblack@eecs.umich.edu if (bits(val, 15,8)) { msb += 8; val >>= 8; } 2047430Sgblack@eecs.umich.edu if (bits(val, 7,4)) { msb += 4; val >>= 4; } 2057384Sgblack@eecs.umich.edu if (bits(val, 3,2)) { msb += 2; val >>= 2; } 2067386Sgblack@eecs.umich.edu if (bits(val, 1,1)) { msb += 1; } 2077430Sgblack@eecs.umich.edu return msb; 2087386Sgblack@eecs.umich.edu} 2097430Sgblack@eecs.umich.edu 2107430Sgblack@eecs.umich.edu/** 2117386Sgblack@eecs.umich.edu * Returns the bit position of the LSB that is set in the input 2127430Sgblack@eecs.umich.edu */ 2137430Sgblack@eecs.umich.eduinline int 2147398Sgblack@eecs.umich.edufindLsbSet(uint64_t val) { 2157396Sgblack@eecs.umich.edu int lsb = 0; 2167396Sgblack@eecs.umich.edu if (!val) 2177396Sgblack@eecs.umich.edu return sizeof(val) * 8; 2187396Sgblack@eecs.umich.edu if (!bits(val, 31,0)) { lsb += 32; val >>= 32; } 2197396Sgblack@eecs.umich.edu if (!bits(val, 15,0)) { lsb += 16; val >>= 16; } 2207396Sgblack@eecs.umich.edu if (!bits(val, 7,0)) { lsb += 8; val >>= 8; } 2217396Sgblack@eecs.umich.edu if (!bits(val, 3,0)) { lsb += 4; val >>= 4; } 2227396Sgblack@eecs.umich.edu if (!bits(val, 1,0)) { lsb += 2; val >>= 2; } 2237396Sgblack@eecs.umich.edu if (!bits(val, 0,0)) { lsb += 1; } 2247396Sgblack@eecs.umich.edu return lsb; 2257396Sgblack@eecs.umich.edu} 2267396Sgblack@eecs.umich.edu 2277396Sgblack@eecs.umich.edu/** 2287396Sgblack@eecs.umich.edu * Checks if a number is a power of two, or zero. 2297396Sgblack@eecs.umich.edu */ 2307396Sgblack@eecs.umich.edutemplate <class T> 2317396Sgblack@eecs.umich.eduinline bool 2327396Sgblack@eecs.umich.eduisPow2(T v) { 2337396Sgblack@eecs.umich.edu return (v & (v - 1)) == (T)0; 2347430Sgblack@eecs.umich.edu} 2357430Sgblack@eecs.umich.edu 2367430Sgblack@eecs.umich.edu/** 2377430Sgblack@eecs.umich.edu * Returns the number of set ones in the provided value. 2387382Sgblack@eecs.umich.edu * PD algorithm from 2397430Sgblack@eecs.umich.edu * http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel 2407430Sgblack@eecs.umich.edu */ 2417430Sgblack@eecs.umich.eduinline int 2427430Sgblack@eecs.umich.edupopCount(uint64_t val) { 2437379Sgblack@eecs.umich.edu#ifndef __has_builtin 2447376Sgblack@eecs.umich.edu #define __has_builtin(foo) 0 2457376Sgblack@eecs.umich.edu#endif 2467376Sgblack@eecs.umich.edu#if defined(__GNUC__) || (defined(__clang__) && __has_builtin(__builtin_popcountl)) 2477376Sgblack@eecs.umich.edu return __builtin_popcountl(val); 2487376Sgblack@eecs.umich.edu#else 2497376Sgblack@eecs.umich.edu const uint64_t m1 = 0x5555555555555555; // ..010101b 2507376Sgblack@eecs.umich.edu const uint64_t m2 = 0x3333333333333333; // ..110011b 2517376Sgblack@eecs.umich.edu const uint64_t m4 = 0x0f0f0f0f0f0f0f0f; // ..001111b 2527376Sgblack@eecs.umich.edu const uint64_t sum = 0x0101010101010101; 2537376Sgblack@eecs.umich.edu 2547376Sgblack@eecs.umich.edu val -= (val >> 1) & m1; // 2 bits count -> 2 bits 2557376Sgblack@eecs.umich.edu val = (val & m2) + ((val >> 2) & m2); // 4 bits count -> 4 bits 2567376Sgblack@eecs.umich.edu val = (val + (val >> 4)) & m4; // 8 bits count -> 8 bits 2577376Sgblack@eecs.umich.edu return (val * sum) >> 56; // horizontal sum 2587376Sgblack@eecs.umich.edu#endif // defined(__GNUC__) || (defined(__clang__) && __has_builtin(__builtin_popcountl)) 2597376Sgblack@eecs.umich.edu} 2607376Sgblack@eecs.umich.edu 2617430Sgblack@eecs.umich.edu/** 2627430Sgblack@eecs.umich.edu * Align to the next highest power of two. 2637430Sgblack@eecs.umich.edu * 2647430Sgblack@eecs.umich.edu * The number passed in is aligned to the next highest power of two, 2657376Sgblack@eecs.umich.edu * if it is not already a power of two. Please note that if 0 is 2667376Sgblack@eecs.umich.edu * passed in, 0 is returned. 2677396Sgblack@eecs.umich.edu * 2687396Sgblack@eecs.umich.edu * This code has been modified from the following: 2697396Sgblack@eecs.umich.edu * http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 2707396Sgblack@eecs.umich.edu */ 2717396Sgblack@eecs.umich.eduinline uint64_t alignToPowerOfTwo(uint64_t val) 2727396Sgblack@eecs.umich.edu{ 2737396Sgblack@eecs.umich.edu val--; 2747396Sgblack@eecs.umich.edu val |= val >> 1; 2757396Sgblack@eecs.umich.edu val |= val >> 2; 2767396Sgblack@eecs.umich.edu val |= val >> 4; 2777396Sgblack@eecs.umich.edu val |= val >> 8; 2787396Sgblack@eecs.umich.edu val |= val >> 16; 2797396Sgblack@eecs.umich.edu val |= val >> 32; 2807396Sgblack@eecs.umich.edu val++; 2817396Sgblack@eecs.umich.edu 2827396Sgblack@eecs.umich.edu return val; 2837396Sgblack@eecs.umich.edu}; 2847396Sgblack@eecs.umich.edu 2857396Sgblack@eecs.umich.edu/** 2867396Sgblack@eecs.umich.edu * Count trailing zeros in a 32-bit value. 2877396Sgblack@eecs.umich.edu * 2887396Sgblack@eecs.umich.edu * Returns 32 if the value is zero. Note that the GCC builtin is 2897396Sgblack@eecs.umich.edu * undefined if the value is zero. 2907396Sgblack@eecs.umich.edu */ 2917396Sgblack@eecs.umich.eduinline int ctz32(uint32_t value) 2927396Sgblack@eecs.umich.edu{ 2937396Sgblack@eecs.umich.edu return value ? __builtin_ctz(value) : 32; 2947396Sgblack@eecs.umich.edu} 2957396Sgblack@eecs.umich.edu 2967396Sgblack@eecs.umich.edu/** 2977396Sgblack@eecs.umich.edu * Count trailing zeros in a 64-bit value. 2987396Sgblack@eecs.umich.edu * 2997396Sgblack@eecs.umich.edu * @param An input value 3007396Sgblack@eecs.umich.edu * @return The number of trailing zeros or 64 if the value is zero. 3017396Sgblack@eecs.umich.edu */ 3027396Sgblack@eecs.umich.eduinline int ctz64(uint64_t value) 3037396Sgblack@eecs.umich.edu{ 3047396Sgblack@eecs.umich.edu return value ? __builtin_ctzll(value) : 64; 3057396Sgblack@eecs.umich.edu} 3067396Sgblack@eecs.umich.edu 3077396Sgblack@eecs.umich.edu#endif // __BASE_BITFIELD_HH__ 3087396Sgblack@eecs.umich.edu