bitfield.hh revision 10400
12292SN/A/* 22727Sktlim@umich.edu * Copyright (c) 2003-2005 The Regents of The University of Michigan 32292SN/A * All rights reserved. 42292SN/A * 52292SN/A * Redistribution and use in source and binary forms, with or without 62292SN/A * modification, are permitted provided that the following conditions are 72292SN/A * met: redistributions of source code must retain the above copyright 82292SN/A * notice, this list of conditions and the following disclaimer; 92292SN/A * redistributions in binary form must reproduce the above copyright 102292SN/A * notice, this list of conditions and the following disclaimer in the 112292SN/A * documentation and/or other materials provided with the distribution; 122292SN/A * neither the name of the copyright holders nor the names of its 132292SN/A * contributors may be used to endorse or promote products derived from 142292SN/A * this software without specific prior written permission. 152292SN/A * 162292SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 172292SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 182292SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 192292SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 202292SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 212292SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 222292SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 232292SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 242292SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 252292SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 262292SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272689Sktlim@umich.edu * 282689Sktlim@umich.edu * Authors: Steve Reinhardt 292292SN/A * Nathan Binkert 302292SN/A */ 312329SN/A 322980Sgblack@eecs.umich.edu#ifndef __BASE_BITFIELD_HH__ 332329SN/A#define __BASE_BITFIELD_HH__ 342329SN/A 352292SN/A#include "base/types.hh" 362292SN/A 372292SN/A/** 382907Sktlim@umich.edu * Generate a 64-bit mask of 'nbits' 1s, right justified. 392907Sktlim@umich.edu */ 402907Sktlim@umich.eduinline uint64_t 412907Sktlim@umich.edumask(int nbits) 422907Sktlim@umich.edu{ 432907Sktlim@umich.edu return (nbits == 64) ? (uint64_t)-1LL : (1ULL << nbits) - 1; 442907Sktlim@umich.edu} 452907Sktlim@umich.edu 462907Sktlim@umich.edu 472907Sktlim@umich.edu 482907Sktlim@umich.edu/** 493639Sktlim@umich.edu * Extract the bitfield from position 'first' to 'last' (inclusive) 502907Sktlim@umich.edu * from 'val' and right justify it. MSB is numbered 63, LSB is 0. 512907Sktlim@umich.edu */ 522907Sktlim@umich.edutemplate <class T> 532907Sktlim@umich.eduinline 542907Sktlim@umich.eduT 552907Sktlim@umich.edubits(T val, int first, int last) 563647Srdreslin@umich.edu{ 573647Srdreslin@umich.edu int nbits = first - last + 1; 583647Srdreslin@umich.edu return (val >> last) & mask(nbits); 593647Srdreslin@umich.edu} 603647Srdreslin@umich.edu 612907Sktlim@umich.edu/** 623647Srdreslin@umich.edu * Extract the bit from this position from 'val' and right justify it. 632907Sktlim@umich.edu */ 642907Sktlim@umich.edutemplate <class T> 652907Sktlim@umich.eduinline 662907Sktlim@umich.eduT 672907Sktlim@umich.edubits(T val, int bit) 682907Sktlim@umich.edu{ 692907Sktlim@umich.edu return bits(val, bit, bit); 703310Srdreslin@umich.edu} 713310Srdreslin@umich.edu 723310Srdreslin@umich.edu/** 733310Srdreslin@umich.edu * Mask off the given bits in place like bits() but without shifting. 743310Srdreslin@umich.edu * msb = 63, lsb = 0 753339Srdreslin@umich.edu */ 763310Srdreslin@umich.edutemplate <class T> 773310Srdreslin@umich.eduinline 782907Sktlim@umich.eduT 792907Sktlim@umich.edumbits(T val, int first, int last) 802907Sktlim@umich.edu{ 812907Sktlim@umich.edu return val & (mask(first+1) & ~mask(last)); 822907Sktlim@umich.edu} 832907Sktlim@umich.edu 842907Sktlim@umich.eduinline uint64_t 853014Srdreslin@umich.edumask(int first, int last) 863014Srdreslin@umich.edu{ 873014Srdreslin@umich.edu return mbits((uint64_t)-1LL, first, last); 883014Srdreslin@umich.edu} 893014Srdreslin@umich.edu 902907Sktlim@umich.edu/** 912907Sktlim@umich.edu * Sign-extend an N-bit value to 64 bits. 922907Sktlim@umich.edu */ 932907Sktlim@umich.edutemplate <int N> 942907Sktlim@umich.eduinline 952907Sktlim@umich.eduint64_t 962907Sktlim@umich.edusext(uint64_t val) 972292SN/A{ 982907Sktlim@umich.edu int sign_bit = bits(val, N-1, N-1); 992907Sktlim@umich.edu return sign_bit ? (val | ~mask(N)) : val; 1002907Sktlim@umich.edu} 1012292SN/A 1022292SN/A/** 1032292SN/A * Return val with bits first to last set to bit_val 1043647Srdreslin@umich.edu */ 1053647Srdreslin@umich.edutemplate <class T, class B> 1062292SN/Ainline 1072292SN/AT 1082292SN/AinsertBits(T val, int first, int last, B bit_val) 1092980Sgblack@eecs.umich.edu{ 1102292SN/A T t_bit_val = bit_val; 1112292SN/A T bmask = mask(first - last + 1) << last; 1122292SN/A return ((t_bit_val << last) & bmask) | (val & ~bmask); 1132292SN/A} 1142292SN/A 1152292SN/A/** 1162292SN/A * Overloaded for access to only one bit in value 1172292SN/A */ 1182292SN/Atemplate <class T, class B> 1192292SN/Ainline 1202292SN/AT 1212292SN/AinsertBits(T val, int bit, B bit_val) 1222292SN/A{ 1232292SN/A return insertBits(val, bit, bit, bit_val); 1242292SN/A} 1252292SN/A 1262292SN/A/** 1272292SN/A * A convenience function to replace bits first to last of val with bit_val 1282292SN/A * in place. 1292292SN/A */ 1302292SN/Atemplate <class T, class B> 1312292SN/Ainline 1322292SN/Avoid 1332292SN/AreplaceBits(T& val, int first, int last, B bit_val) 1342292SN/A{ 1352292SN/A val = insertBits(val, first, last, bit_val); 1362292SN/A} 1372292SN/A 1382292SN/A/** Overloaded function to allow to access only 1 bit*/ 1392292SN/Atemplate <class T, class B> 1402292SN/Ainline 1412292SN/Avoid 1422292SN/AreplaceBits(T& val, int bit, B bit_val) 1432292SN/A{ 1442292SN/A val = insertBits(val, bit, bit, bit_val); 1452292SN/A} 1462292SN/A/** 1472292SN/A * Returns the bit position of the MSB that is set in the input 1482292SN/A */ 1492292SN/Ainline 1502292SN/Aint 1512292SN/AfindMsbSet(uint64_t val) { 1522292SN/A int msb = 0; 1532292SN/A if (!val) 1542292SN/A return 0; 1552292SN/A if (bits(val, 63,32)) { msb += 32; val >>= 32; } 1562292SN/A if (bits(val, 31,16)) { msb += 16; val >>= 16; } 1572292SN/A if (bits(val, 15,8)) { msb += 8; val >>= 8; } 1582907Sktlim@umich.edu if (bits(val, 7,4)) { msb += 4; val >>= 4; } 1592907Sktlim@umich.edu if (bits(val, 3,2)) { msb += 2; val >>= 2; } 1602292SN/A if (bits(val, 1,1)) { msb += 1; } 1612292SN/A return msb; 1622292SN/A} 1632292SN/A 1642292SN/A/** 1652292SN/A * Returns the bit position of the LSB that is set in the input 1662292SN/A */ 1672292SN/Ainline int 1682292SN/AfindLsbSet(uint64_t val) { 1692292SN/A int lsb = 0; 1702292SN/A if (!val) 1712292SN/A return sizeof(val) * 8; 1722292SN/A if (!bits(val, 31,0)) { lsb += 32; val >>= 32; } 1732727Sktlim@umich.edu if (!bits(val, 15,0)) { lsb += 16; val >>= 16; } 1742727Sktlim@umich.edu if (!bits(val, 7,0)) { lsb += 8; val >>= 8; } 1752727Sktlim@umich.edu if (!bits(val, 3,0)) { lsb += 4; val >>= 4; } 1762727Sktlim@umich.edu if (!bits(val, 1,0)) { lsb += 2; val >>= 2; } 1772727Sktlim@umich.edu if (!bits(val, 0,0)) { lsb += 1; } 1782727Sktlim@umich.edu return lsb; 1792727Sktlim@umich.edu} 1802727Sktlim@umich.edu 1812727Sktlim@umich.edu/** 1822727Sktlim@umich.edu * Checks if a number is a power of two, or zero. 1832980Sgblack@eecs.umich.edu */ 1842292SN/Atemplate <class T> 1852292SN/Ainline bool 1862292SN/AisPow2(T v) { 1872292SN/A return (v & (v - 1)) == (T)0; 1882292SN/A} 1892292SN/A 1902292SN/A/** 1912733Sktlim@umich.edu * Returns the number of set ones in the provided value. 1922292SN/A * PD algorithm from 1932292SN/A * http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel 1942292SN/A */ 1952907Sktlim@umich.eduinline int 1962907Sktlim@umich.edupopCount(uint64_t val) { 1972292SN/A#ifndef __has_builtin 1982292SN/A #define __has_builtin(foo) 0 1992292SN/A#endif 2002292SN/A#if defined(__GNUC__) || (defined(__clang__) && __has_builtin(__builtin_popcountl)) 2012292SN/A return __builtin_popcountl(val); 2022292SN/A#else 2032292SN/A const uint64_t m1 = 0x5555555555555555; // ..010101b 2042292SN/A const uint64_t m2 = 0x3333333333333333; // ..110011b 2052292SN/A const uint64_t m4 = 0x0f0f0f0f0f0f0f0f; // ..001111b 2062292SN/A const uint64_t sum = 0x0101010101010101; 2072292SN/A 2082292SN/A val -= (val >> 1) & m1; // 2 bits count -> 2 bits 2092292SN/A val = (val & m2) + ((val >> 2) & m2); // 4 bits count -> 4 bits 2102292SN/A val = (val + (val >> 4)) & m4; // 8 bits count -> 8 bits 2112292SN/A return (val * sum) >> 56; // horizontal sum 2122292SN/A#endif // defined(__GNUC__) || (defined(__clang__) && __has_builtin(__builtin_popcountl)) 2132292SN/A} 2142307SN/A#endif // __BASE_BITFIELD_HH__ 2152307SN/A