bitfield.hh revision 11932:98961d1b51ca
112855Sgabeblack@google.com/* 212855Sgabeblack@google.com * Copyright (c) 2017 ARM Limited 312855Sgabeblack@google.com * All rights reserved 412855Sgabeblack@google.com * 512855Sgabeblack@google.com * The license below extends only to copyright in the software and shall 612855Sgabeblack@google.com * not be construed as granting a license to any other intellectual 712855Sgabeblack@google.com * property including but not limited to intellectual property relating 812855Sgabeblack@google.com * to a hardware implementation of the functionality of the software 912855Sgabeblack@google.com * licensed hereunder. You may use the software subject to the license 1012855Sgabeblack@google.com * terms below provided that you ensure that this notice is replicated 1112855Sgabeblack@google.com * unmodified and in its entirety in all distributions of the software, 1212855Sgabeblack@google.com * modified or unmodified, in source code or in binary form. 1312855Sgabeblack@google.com * 1412855Sgabeblack@google.com * Copyright (c) 2003-2005 The Regents of The University of Michigan 1512855Sgabeblack@google.com * All rights reserved. 1612855Sgabeblack@google.com * 1712855Sgabeblack@google.com * Redistribution and use in source and binary forms, with or without 1812855Sgabeblack@google.com * modification, are permitted provided that the following conditions are 1912855Sgabeblack@google.com * met: redistributions of source code must retain the above copyright 2012855Sgabeblack@google.com * notice, this list of conditions and the following disclaimer; 2112855Sgabeblack@google.com * redistributions in binary form must reproduce the above copyright 2212855Sgabeblack@google.com * notice, this list of conditions and the following disclaimer in the 2312855Sgabeblack@google.com * documentation and/or other materials provided with the distribution; 2412855Sgabeblack@google.com * neither the name of the copyright holders nor the names of its 2512855Sgabeblack@google.com * contributors may be used to endorse or promote products derived from 2612855Sgabeblack@google.com * this software without specific prior written permission. 2712855Sgabeblack@google.com * 2812855Sgabeblack@google.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2912855Sgabeblack@google.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 3012855Sgabeblack@google.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 3112855Sgabeblack@google.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 3212855Sgabeblack@google.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3312855Sgabeblack@google.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3412855Sgabeblack@google.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3512855Sgabeblack@google.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3612855Sgabeblack@google.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3712855Sgabeblack@google.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3812855Sgabeblack@google.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3912855Sgabeblack@google.com * 4012855Sgabeblack@google.com * Authors: Steve Reinhardt 4112855Sgabeblack@google.com * Nathan Binkert 4212855Sgabeblack@google.com */ 4312855Sgabeblack@google.com 4412855Sgabeblack@google.com#ifndef __BASE_BITFIELD_HH__ 4512855Sgabeblack@google.com#define __BASE_BITFIELD_HH__ 4612855Sgabeblack@google.com 47#include <inttypes.h> 48 49/** 50 * Generate a 64-bit mask of 'nbits' 1s, right justified. 51 */ 52inline uint64_t 53mask(int nbits) 54{ 55 return (nbits == 64) ? (uint64_t)-1LL : (1ULL << nbits) - 1; 56} 57 58 59 60/** 61 * Extract the bitfield from position 'first' to 'last' (inclusive) 62 * from 'val' and right justify it. MSB is numbered 63, LSB is 0. 63 */ 64template <class T> 65inline 66T 67bits(T val, int first, int last) 68{ 69 int nbits = first - last + 1; 70 return (val >> last) & mask(nbits); 71} 72 73/** 74 * Extract the bit from this position from 'val' and right justify it. 75 */ 76template <class T> 77inline 78T 79bits(T val, int bit) 80{ 81 return bits(val, bit, bit); 82} 83 84/** 85 * Mask off the given bits in place like bits() but without shifting. 86 * msb = 63, lsb = 0 87 */ 88template <class T> 89inline 90T 91mbits(T val, int first, int last) 92{ 93 return val & (mask(first+1) & ~mask(last)); 94} 95 96inline uint64_t 97mask(int first, int last) 98{ 99 return mbits((uint64_t)-1LL, first, last); 100} 101 102/** 103 * Sign-extend an N-bit value to 64 bits. 104 */ 105template <int N> 106inline 107uint64_t 108sext(uint64_t val) 109{ 110 int sign_bit = bits(val, N-1, N-1); 111 return sign_bit ? (val | ~mask(N)) : val; 112} 113 114/** 115 * Return val with bits first to last set to bit_val 116 */ 117template <class T, class B> 118inline 119T 120insertBits(T val, int first, int last, B bit_val) 121{ 122 T t_bit_val = bit_val; 123 T bmask = mask(first - last + 1) << last; 124 return ((t_bit_val << last) & bmask) | (val & ~bmask); 125} 126 127/** 128 * Overloaded for access to only one bit in value 129 */ 130template <class T, class B> 131inline 132T 133insertBits(T val, int bit, B bit_val) 134{ 135 return insertBits(val, bit, bit, bit_val); 136} 137 138/** 139 * A convenience function to replace bits first to last of val with bit_val 140 * in place. 141 */ 142template <class T, class B> 143inline 144void 145replaceBits(T& val, int first, int last, B bit_val) 146{ 147 val = insertBits(val, first, last, bit_val); 148} 149 150/** Overloaded function to allow to access only 1 bit*/ 151template <class T, class B> 152inline 153void 154replaceBits(T& val, int bit, B bit_val) 155{ 156 val = insertBits(val, bit, bit, bit_val); 157} 158/** 159 * Returns the bit position of the MSB that is set in the input 160 */ 161inline 162int 163findMsbSet(uint64_t val) { 164 int msb = 0; 165 if (!val) 166 return 0; 167 if (bits(val, 63,32)) { msb += 32; val >>= 32; } 168 if (bits(val, 31,16)) { msb += 16; val >>= 16; } 169 if (bits(val, 15,8)) { msb += 8; val >>= 8; } 170 if (bits(val, 7,4)) { msb += 4; val >>= 4; } 171 if (bits(val, 3,2)) { msb += 2; val >>= 2; } 172 if (bits(val, 1,1)) { msb += 1; } 173 return msb; 174} 175 176/** 177 * Returns the bit position of the LSB that is set in the input 178 */ 179inline int 180findLsbSet(uint64_t val) { 181 int lsb = 0; 182 if (!val) 183 return sizeof(val) * 8; 184 if (!bits(val, 31,0)) { lsb += 32; val >>= 32; } 185 if (!bits(val, 15,0)) { lsb += 16; val >>= 16; } 186 if (!bits(val, 7,0)) { lsb += 8; val >>= 8; } 187 if (!bits(val, 3,0)) { lsb += 4; val >>= 4; } 188 if (!bits(val, 1,0)) { lsb += 2; val >>= 2; } 189 if (!bits(val, 0,0)) { lsb += 1; } 190 return lsb; 191} 192 193/** 194 * Checks if a number is a power of two, or zero. 195 */ 196template <class T> 197inline bool 198isPow2(T v) { 199 return (v & (v - 1)) == (T)0; 200} 201 202/** 203 * Returns the number of set ones in the provided value. 204 * PD algorithm from 205 * http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel 206 */ 207inline int 208popCount(uint64_t val) { 209#ifndef __has_builtin 210 #define __has_builtin(foo) 0 211#endif 212#if defined(__GNUC__) || (defined(__clang__) && __has_builtin(__builtin_popcountl)) 213 return __builtin_popcountl(val); 214#else 215 const uint64_t m1 = 0x5555555555555555; // ..010101b 216 const uint64_t m2 = 0x3333333333333333; // ..110011b 217 const uint64_t m4 = 0x0f0f0f0f0f0f0f0f; // ..001111b 218 const uint64_t sum = 0x0101010101010101; 219 220 val -= (val >> 1) & m1; // 2 bits count -> 2 bits 221 val = (val & m2) + ((val >> 2) & m2); // 4 bits count -> 4 bits 222 val = (val + (val >> 4)) & m4; // 8 bits count -> 8 bits 223 return (val * sum) >> 56; // horizontal sum 224#endif // defined(__GNUC__) || (defined(__clang__) && __has_builtin(__builtin_popcountl)) 225} 226 227/** 228 * Align to the next highest power of two. 229 * 230 * The number passed in is aligned to the next highest power of two, 231 * if it is not already a power of two. Please note that if 0 is 232 * passed in, 0 is returned. 233 * 234 * This code has been modified from the following: 235 * http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 236 */ 237inline uint64_t alignToPowerOfTwo(uint64_t val) 238{ 239 val--; 240 val |= val >> 1; 241 val |= val >> 2; 242 val |= val >> 4; 243 val |= val >> 8; 244 val |= val >> 16; 245 val |= val >> 32; 246 val++; 247 248 return val; 249}; 250 251#endif // __BASE_BITFIELD_HH__ 252