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