bitfield.hh revision 10537
12SN/A/* 21762SN/A * Copyright (c) 2003-2005 The Regents of The University of Michigan 32SN/A * All rights reserved. 42SN/A * 52SN/A * Redistribution and use in source and binary forms, with or without 62SN/A * modification, are permitted provided that the following conditions are 72SN/A * met: redistributions of source code must retain the above copyright 82SN/A * notice, this list of conditions and the following disclaimer; 92SN/A * redistributions in binary form must reproduce the above copyright 102SN/A * notice, this list of conditions and the following disclaimer in the 112SN/A * documentation and/or other materials provided with the distribution; 122SN/A * neither the name of the copyright holders nor the names of its 132SN/A * contributors may be used to endorse or promote products derived from 142SN/A * this software without specific prior written permission. 152SN/A * 162SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 172SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 182SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 192SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 202SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 212SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 222SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 232SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 242SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 252SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 262SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272665Ssaidi@eecs.umich.edu * 282665Ssaidi@eecs.umich.edu * Authors: Steve Reinhardt 292665Ssaidi@eecs.umich.edu * Nathan Binkert 302SN/A */ 312SN/A 321112SN/A#ifndef __BASE_BITFIELD_HH__ 331112SN/A#define __BASE_BITFIELD_HH__ 342SN/A 356215Snate@binkert.org#include "base/types.hh" 362SN/A 372SN/A/** 382SN/A * Generate a 64-bit mask of 'nbits' 1s, right justified. 392SN/A */ 402SN/Ainline uint64_t 412SN/Amask(int nbits) 422SN/A{ 432SN/A return (nbits == 64) ? (uint64_t)-1LL : (1ULL << nbits) - 1; 442SN/A} 452SN/A 462SN/A 474070Ssaidi@eecs.umich.edu 482SN/A/** 492SN/A * Extract the bitfield from position 'first' to 'last' (inclusive) 502SN/A * from 'val' and right justify it. MSB is numbered 63, LSB is 0. 512SN/A */ 522SN/Atemplate <class T> 532SN/Ainline 542SN/AT 552SN/Abits(T val, int first, int last) 562SN/A{ 572SN/A int nbits = first - last + 1; 582SN/A return (val >> last) & mask(nbits); 592SN/A} 602SN/A 612SN/A/** 624661Sksewell@umich.edu * Extract the bit from this position from 'val' and right justify it. 634661Sksewell@umich.edu */ 644661Sksewell@umich.edutemplate <class T> 654661Sksewell@umich.eduinline 664661Sksewell@umich.eduT 674661Sksewell@umich.edubits(T val, int bit) 684661Sksewell@umich.edu{ 694661Sksewell@umich.edu return bits(val, bit, bit); 704661Sksewell@umich.edu} 714661Sksewell@umich.edu 724661Sksewell@umich.edu/** 733814Ssaidi@eecs.umich.edu * Mask off the given bits in place like bits() but without shifting. 743814Ssaidi@eecs.umich.edu * msb = 63, lsb = 0 753814Ssaidi@eecs.umich.edu */ 763814Ssaidi@eecs.umich.edutemplate <class T> 773814Ssaidi@eecs.umich.eduinline 783814Ssaidi@eecs.umich.eduT 793814Ssaidi@eecs.umich.edumbits(T val, int first, int last) 803814Ssaidi@eecs.umich.edu{ 813814Ssaidi@eecs.umich.edu return val & (mask(first+1) & ~mask(last)); 823814Ssaidi@eecs.umich.edu} 833814Ssaidi@eecs.umich.edu 844070Ssaidi@eecs.umich.eduinline uint64_t 854070Ssaidi@eecs.umich.edumask(int first, int last) 864070Ssaidi@eecs.umich.edu{ 874070Ssaidi@eecs.umich.edu return mbits((uint64_t)-1LL, first, last); 884070Ssaidi@eecs.umich.edu} 894070Ssaidi@eecs.umich.edu 903814Ssaidi@eecs.umich.edu/** 912SN/A * Sign-extend an N-bit value to 64 bits. 922SN/A */ 932SN/Atemplate <int N> 942SN/Ainline 9510537Sandreas.hansson@arm.comuint64_t 962SN/Asext(uint64_t val) 972SN/A{ 982SN/A int sign_bit = bits(val, N-1, N-1); 992SN/A return sign_bit ? (val | ~mask(N)) : val; 1002SN/A} 1012SN/A 1023422Sgblack@eecs.umich.edu/** 1033422Sgblack@eecs.umich.edu * Return val with bits first to last set to bit_val 1043422Sgblack@eecs.umich.edu */ 1053422Sgblack@eecs.umich.edutemplate <class T, class B> 1063422Sgblack@eecs.umich.eduinline 1073422Sgblack@eecs.umich.eduT 1083422Sgblack@eecs.umich.eduinsertBits(T val, int first, int last, B bit_val) 1093422Sgblack@eecs.umich.edu{ 1104425Ssaidi@eecs.umich.edu T t_bit_val = bit_val; 1113422Sgblack@eecs.umich.edu T bmask = mask(first - last + 1) << last; 1124425Ssaidi@eecs.umich.edu return ((t_bit_val << last) & bmask) | (val & ~bmask); 1133422Sgblack@eecs.umich.edu} 1143422Sgblack@eecs.umich.edu 1153422Sgblack@eecs.umich.edu/** 1164661Sksewell@umich.edu * Overloaded for access to only one bit in value 1174661Sksewell@umich.edu */ 1184661Sksewell@umich.edutemplate <class T, class B> 1194661Sksewell@umich.eduinline 1204661Sksewell@umich.eduT 1214661Sksewell@umich.eduinsertBits(T val, int bit, B bit_val) 1224661Sksewell@umich.edu{ 1234661Sksewell@umich.edu return insertBits(val, bit, bit, bit_val); 1244661Sksewell@umich.edu} 1254661Sksewell@umich.edu 1264661Sksewell@umich.edu/** 1273422Sgblack@eecs.umich.edu * A convenience function to replace bits first to last of val with bit_val 1283422Sgblack@eecs.umich.edu * in place. 1293422Sgblack@eecs.umich.edu */ 1303422Sgblack@eecs.umich.edutemplate <class T, class B> 1313422Sgblack@eecs.umich.eduinline 1323422Sgblack@eecs.umich.eduvoid 1333422Sgblack@eecs.umich.edureplaceBits(T& val, int first, int last, B bit_val) 1343422Sgblack@eecs.umich.edu{ 1353422Sgblack@eecs.umich.edu val = insertBits(val, first, last, bit_val); 1363422Sgblack@eecs.umich.edu} 1373422Sgblack@eecs.umich.edu 1384661Sksewell@umich.edu/** Overloaded function to allow to access only 1 bit*/ 1394661Sksewell@umich.edutemplate <class T, class B> 1404661Sksewell@umich.eduinline 1414661Sksewell@umich.eduvoid 1424661Sksewell@umich.edureplaceBits(T& val, int bit, B bit_val) 1434661Sksewell@umich.edu{ 1444661Sksewell@umich.edu val = insertBits(val, bit, bit, bit_val); 1454661Sksewell@umich.edu} 1464103Ssaidi@eecs.umich.edu/** 1474103Ssaidi@eecs.umich.edu * Returns the bit position of the MSB that is set in the input 1484103Ssaidi@eecs.umich.edu */ 1494103Ssaidi@eecs.umich.eduinline 1504103Ssaidi@eecs.umich.eduint 1514103Ssaidi@eecs.umich.edufindMsbSet(uint64_t val) { 1524103Ssaidi@eecs.umich.edu int msb = 0; 1534103Ssaidi@eecs.umich.edu if (!val) 1544103Ssaidi@eecs.umich.edu return 0; 1554244Ssaidi@eecs.umich.edu if (bits(val, 63,32)) { msb += 32; val >>= 32; } 1564244Ssaidi@eecs.umich.edu if (bits(val, 31,16)) { msb += 16; val >>= 16; } 1574244Ssaidi@eecs.umich.edu if (bits(val, 15,8)) { msb += 8; val >>= 8; } 1584244Ssaidi@eecs.umich.edu if (bits(val, 7,4)) { msb += 4; val >>= 4; } 1594244Ssaidi@eecs.umich.edu if (bits(val, 3,2)) { msb += 2; val >>= 2; } 1604244Ssaidi@eecs.umich.edu if (bits(val, 1,1)) { msb += 1; } 1614103Ssaidi@eecs.umich.edu return msb; 1624103Ssaidi@eecs.umich.edu} 1634103Ssaidi@eecs.umich.edu 1646274Sgblack@eecs.umich.edu/** 1656274Sgblack@eecs.umich.edu * Returns the bit position of the LSB that is set in the input 1666274Sgblack@eecs.umich.edu */ 1676274Sgblack@eecs.umich.eduinline int 1686274Sgblack@eecs.umich.edufindLsbSet(uint64_t val) { 1696274Sgblack@eecs.umich.edu int lsb = 0; 1706274Sgblack@eecs.umich.edu if (!val) 1716274Sgblack@eecs.umich.edu return sizeof(val) * 8; 1726274Sgblack@eecs.umich.edu if (!bits(val, 31,0)) { lsb += 32; val >>= 32; } 1736274Sgblack@eecs.umich.edu if (!bits(val, 15,0)) { lsb += 16; val >>= 16; } 1746274Sgblack@eecs.umich.edu if (!bits(val, 7,0)) { lsb += 8; val >>= 8; } 1756274Sgblack@eecs.umich.edu if (!bits(val, 3,0)) { lsb += 4; val >>= 4; } 1766274Sgblack@eecs.umich.edu if (!bits(val, 1,0)) { lsb += 2; val >>= 2; } 1776274Sgblack@eecs.umich.edu if (!bits(val, 0,0)) { lsb += 1; } 1786274Sgblack@eecs.umich.edu return lsb; 1796274Sgblack@eecs.umich.edu} 1806274Sgblack@eecs.umich.edu 18110400Sstephan.diestelhorst@arm.com/** 18210400Sstephan.diestelhorst@arm.com * Checks if a number is a power of two, or zero. 18310400Sstephan.diestelhorst@arm.com */ 18410400Sstephan.diestelhorst@arm.comtemplate <class T> 18510400Sstephan.diestelhorst@arm.cominline bool 18610400Sstephan.diestelhorst@arm.comisPow2(T v) { 18710400Sstephan.diestelhorst@arm.com return (v & (v - 1)) == (T)0; 18810400Sstephan.diestelhorst@arm.com} 18910400Sstephan.diestelhorst@arm.com 19010400Sstephan.diestelhorst@arm.com/** 19110400Sstephan.diestelhorst@arm.com * Returns the number of set ones in the provided value. 19210400Sstephan.diestelhorst@arm.com * PD algorithm from 19310400Sstephan.diestelhorst@arm.com * http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel 19410400Sstephan.diestelhorst@arm.com */ 19510400Sstephan.diestelhorst@arm.cominline int 19610400Sstephan.diestelhorst@arm.compopCount(uint64_t val) { 19710400Sstephan.diestelhorst@arm.com#ifndef __has_builtin 19810400Sstephan.diestelhorst@arm.com #define __has_builtin(foo) 0 19910400Sstephan.diestelhorst@arm.com#endif 20010400Sstephan.diestelhorst@arm.com#if defined(__GNUC__) || (defined(__clang__) && __has_builtin(__builtin_popcountl)) 20110400Sstephan.diestelhorst@arm.com return __builtin_popcountl(val); 20210400Sstephan.diestelhorst@arm.com#else 20310400Sstephan.diestelhorst@arm.com const uint64_t m1 = 0x5555555555555555; // ..010101b 20410400Sstephan.diestelhorst@arm.com const uint64_t m2 = 0x3333333333333333; // ..110011b 20510400Sstephan.diestelhorst@arm.com const uint64_t m4 = 0x0f0f0f0f0f0f0f0f; // ..001111b 20610400Sstephan.diestelhorst@arm.com const uint64_t sum = 0x0101010101010101; 20710400Sstephan.diestelhorst@arm.com 20810400Sstephan.diestelhorst@arm.com val -= (val >> 1) & m1; // 2 bits count -> 2 bits 20910400Sstephan.diestelhorst@arm.com val = (val & m2) + ((val >> 2) & m2); // 4 bits count -> 4 bits 21010400Sstephan.diestelhorst@arm.com val = (val + (val >> 4)) & m4; // 8 bits count -> 8 bits 21110400Sstephan.diestelhorst@arm.com return (val * sum) >> 56; // horizontal sum 21210400Sstephan.diestelhorst@arm.com#endif // defined(__GNUC__) || (defined(__clang__) && __has_builtin(__builtin_popcountl)) 21310400Sstephan.diestelhorst@arm.com} 2141112SN/A#endif // __BASE_BITFIELD_HH__ 215