bitfield.hh revision 11932
12SN/A/* 211932Ssascha.bischoff@arm.com * Copyright (c) 2017 ARM Limited 311932Ssascha.bischoff@arm.com * All rights reserved 411932Ssascha.bischoff@arm.com * 511932Ssascha.bischoff@arm.com * The license below extends only to copyright in the software and shall 611932Ssascha.bischoff@arm.com * not be construed as granting a license to any other intellectual 711932Ssascha.bischoff@arm.com * property including but not limited to intellectual property relating 811932Ssascha.bischoff@arm.com * to a hardware implementation of the functionality of the software 911932Ssascha.bischoff@arm.com * licensed hereunder. You may use the software subject to the license 1011932Ssascha.bischoff@arm.com * terms below provided that you ensure that this notice is replicated 1111932Ssascha.bischoff@arm.com * unmodified and in its entirety in all distributions of the software, 1211932Ssascha.bischoff@arm.com * modified or unmodified, in source code or in binary form. 1311932Ssascha.bischoff@arm.com * 141762SN/A * Copyright (c) 2003-2005 The Regents of The University of Michigan 152SN/A * All rights reserved. 162SN/A * 172SN/A * Redistribution and use in source and binary forms, with or without 182SN/A * modification, are permitted provided that the following conditions are 192SN/A * met: redistributions of source code must retain the above copyright 202SN/A * notice, this list of conditions and the following disclaimer; 212SN/A * redistributions in binary form must reproduce the above copyright 222SN/A * notice, this list of conditions and the following disclaimer in the 232SN/A * documentation and/or other materials provided with the distribution; 242SN/A * neither the name of the copyright holders nor the names of its 252SN/A * contributors may be used to endorse or promote products derived from 262SN/A * this software without specific prior written permission. 272SN/A * 282SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 292SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 302SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 312SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 322SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 332SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 342SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 352SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 362SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 372SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 382SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 392665Ssaidi@eecs.umich.edu * 402665Ssaidi@eecs.umich.edu * Authors: Steve Reinhardt 412665Ssaidi@eecs.umich.edu * Nathan Binkert 422SN/A */ 432SN/A 441112SN/A#ifndef __BASE_BITFIELD_HH__ 451112SN/A#define __BASE_BITFIELD_HH__ 462SN/A 4711800Sbrandon.potter@amd.com#include <inttypes.h> 482SN/A 492SN/A/** 502SN/A * Generate a 64-bit mask of 'nbits' 1s, right justified. 512SN/A */ 522SN/Ainline uint64_t 532SN/Amask(int nbits) 542SN/A{ 552SN/A return (nbits == 64) ? (uint64_t)-1LL : (1ULL << nbits) - 1; 562SN/A} 572SN/A 582SN/A 594070Ssaidi@eecs.umich.edu 602SN/A/** 612SN/A * Extract the bitfield from position 'first' to 'last' (inclusive) 622SN/A * from 'val' and right justify it. MSB is numbered 63, LSB is 0. 632SN/A */ 642SN/Atemplate <class T> 652SN/Ainline 662SN/AT 672SN/Abits(T val, int first, int last) 682SN/A{ 692SN/A int nbits = first - last + 1; 702SN/A return (val >> last) & mask(nbits); 712SN/A} 722SN/A 732SN/A/** 744661Sksewell@umich.edu * Extract the bit from this position from 'val' and right justify it. 754661Sksewell@umich.edu */ 764661Sksewell@umich.edutemplate <class T> 774661Sksewell@umich.eduinline 784661Sksewell@umich.eduT 794661Sksewell@umich.edubits(T val, int bit) 804661Sksewell@umich.edu{ 814661Sksewell@umich.edu return bits(val, bit, bit); 824661Sksewell@umich.edu} 834661Sksewell@umich.edu 844661Sksewell@umich.edu/** 853814Ssaidi@eecs.umich.edu * Mask off the given bits in place like bits() but without shifting. 863814Ssaidi@eecs.umich.edu * msb = 63, lsb = 0 873814Ssaidi@eecs.umich.edu */ 883814Ssaidi@eecs.umich.edutemplate <class T> 893814Ssaidi@eecs.umich.eduinline 903814Ssaidi@eecs.umich.eduT 913814Ssaidi@eecs.umich.edumbits(T val, int first, int last) 923814Ssaidi@eecs.umich.edu{ 933814Ssaidi@eecs.umich.edu return val & (mask(first+1) & ~mask(last)); 943814Ssaidi@eecs.umich.edu} 953814Ssaidi@eecs.umich.edu 964070Ssaidi@eecs.umich.eduinline uint64_t 974070Ssaidi@eecs.umich.edumask(int first, int last) 984070Ssaidi@eecs.umich.edu{ 994070Ssaidi@eecs.umich.edu return mbits((uint64_t)-1LL, first, last); 1004070Ssaidi@eecs.umich.edu} 1014070Ssaidi@eecs.umich.edu 1023814Ssaidi@eecs.umich.edu/** 1032SN/A * Sign-extend an N-bit value to 64 bits. 1042SN/A */ 1052SN/Atemplate <int N> 1062SN/Ainline 10710537Sandreas.hansson@arm.comuint64_t 1082SN/Asext(uint64_t val) 1092SN/A{ 1102SN/A int sign_bit = bits(val, N-1, N-1); 1112SN/A return sign_bit ? (val | ~mask(N)) : val; 1122SN/A} 1132SN/A 1143422Sgblack@eecs.umich.edu/** 1153422Sgblack@eecs.umich.edu * Return val with bits first to last set to bit_val 1163422Sgblack@eecs.umich.edu */ 1173422Sgblack@eecs.umich.edutemplate <class T, class B> 1183422Sgblack@eecs.umich.eduinline 1193422Sgblack@eecs.umich.eduT 1203422Sgblack@eecs.umich.eduinsertBits(T val, int first, int last, B bit_val) 1213422Sgblack@eecs.umich.edu{ 1224425Ssaidi@eecs.umich.edu T t_bit_val = bit_val; 1233422Sgblack@eecs.umich.edu T bmask = mask(first - last + 1) << last; 1244425Ssaidi@eecs.umich.edu return ((t_bit_val << last) & bmask) | (val & ~bmask); 1253422Sgblack@eecs.umich.edu} 1263422Sgblack@eecs.umich.edu 1273422Sgblack@eecs.umich.edu/** 1284661Sksewell@umich.edu * Overloaded for access to only one bit in value 1294661Sksewell@umich.edu */ 1304661Sksewell@umich.edutemplate <class T, class B> 1314661Sksewell@umich.eduinline 1324661Sksewell@umich.eduT 1334661Sksewell@umich.eduinsertBits(T val, int bit, B bit_val) 1344661Sksewell@umich.edu{ 1354661Sksewell@umich.edu return insertBits(val, bit, bit, bit_val); 1364661Sksewell@umich.edu} 1374661Sksewell@umich.edu 1384661Sksewell@umich.edu/** 1393422Sgblack@eecs.umich.edu * A convenience function to replace bits first to last of val with bit_val 1403422Sgblack@eecs.umich.edu * in place. 1413422Sgblack@eecs.umich.edu */ 1423422Sgblack@eecs.umich.edutemplate <class T, class B> 1433422Sgblack@eecs.umich.eduinline 1443422Sgblack@eecs.umich.eduvoid 1453422Sgblack@eecs.umich.edureplaceBits(T& val, int first, int last, B bit_val) 1463422Sgblack@eecs.umich.edu{ 1473422Sgblack@eecs.umich.edu val = insertBits(val, first, last, bit_val); 1483422Sgblack@eecs.umich.edu} 1493422Sgblack@eecs.umich.edu 1504661Sksewell@umich.edu/** Overloaded function to allow to access only 1 bit*/ 1514661Sksewell@umich.edutemplate <class T, class B> 1524661Sksewell@umich.eduinline 1534661Sksewell@umich.eduvoid 1544661Sksewell@umich.edureplaceBits(T& val, int bit, B bit_val) 1554661Sksewell@umich.edu{ 1564661Sksewell@umich.edu val = insertBits(val, bit, bit, bit_val); 1574661Sksewell@umich.edu} 1584103Ssaidi@eecs.umich.edu/** 1594103Ssaidi@eecs.umich.edu * Returns the bit position of the MSB that is set in the input 1604103Ssaidi@eecs.umich.edu */ 1614103Ssaidi@eecs.umich.eduinline 1624103Ssaidi@eecs.umich.eduint 1634103Ssaidi@eecs.umich.edufindMsbSet(uint64_t val) { 1644103Ssaidi@eecs.umich.edu int msb = 0; 1654103Ssaidi@eecs.umich.edu if (!val) 1664103Ssaidi@eecs.umich.edu return 0; 1674244Ssaidi@eecs.umich.edu if (bits(val, 63,32)) { msb += 32; val >>= 32; } 1684244Ssaidi@eecs.umich.edu if (bits(val, 31,16)) { msb += 16; val >>= 16; } 1694244Ssaidi@eecs.umich.edu if (bits(val, 15,8)) { msb += 8; val >>= 8; } 1704244Ssaidi@eecs.umich.edu if (bits(val, 7,4)) { msb += 4; val >>= 4; } 1714244Ssaidi@eecs.umich.edu if (bits(val, 3,2)) { msb += 2; val >>= 2; } 1724244Ssaidi@eecs.umich.edu if (bits(val, 1,1)) { msb += 1; } 1734103Ssaidi@eecs.umich.edu return msb; 1744103Ssaidi@eecs.umich.edu} 1754103Ssaidi@eecs.umich.edu 1766274Sgblack@eecs.umich.edu/** 1776274Sgblack@eecs.umich.edu * Returns the bit position of the LSB that is set in the input 1786274Sgblack@eecs.umich.edu */ 1796274Sgblack@eecs.umich.eduinline int 1806274Sgblack@eecs.umich.edufindLsbSet(uint64_t val) { 1816274Sgblack@eecs.umich.edu int lsb = 0; 1826274Sgblack@eecs.umich.edu if (!val) 1836274Sgblack@eecs.umich.edu return sizeof(val) * 8; 1846274Sgblack@eecs.umich.edu if (!bits(val, 31,0)) { lsb += 32; val >>= 32; } 1856274Sgblack@eecs.umich.edu if (!bits(val, 15,0)) { lsb += 16; val >>= 16; } 1866274Sgblack@eecs.umich.edu if (!bits(val, 7,0)) { lsb += 8; val >>= 8; } 1876274Sgblack@eecs.umich.edu if (!bits(val, 3,0)) { lsb += 4; val >>= 4; } 1886274Sgblack@eecs.umich.edu if (!bits(val, 1,0)) { lsb += 2; val >>= 2; } 1896274Sgblack@eecs.umich.edu if (!bits(val, 0,0)) { lsb += 1; } 1906274Sgblack@eecs.umich.edu return lsb; 1916274Sgblack@eecs.umich.edu} 1926274Sgblack@eecs.umich.edu 19310400Sstephan.diestelhorst@arm.com/** 19410400Sstephan.diestelhorst@arm.com * Checks if a number is a power of two, or zero. 19510400Sstephan.diestelhorst@arm.com */ 19610400Sstephan.diestelhorst@arm.comtemplate <class T> 19710400Sstephan.diestelhorst@arm.cominline bool 19810400Sstephan.diestelhorst@arm.comisPow2(T v) { 19910400Sstephan.diestelhorst@arm.com return (v & (v - 1)) == (T)0; 20010400Sstephan.diestelhorst@arm.com} 20110400Sstephan.diestelhorst@arm.com 20210400Sstephan.diestelhorst@arm.com/** 20310400Sstephan.diestelhorst@arm.com * Returns the number of set ones in the provided value. 20410400Sstephan.diestelhorst@arm.com * PD algorithm from 20510400Sstephan.diestelhorst@arm.com * http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel 20610400Sstephan.diestelhorst@arm.com */ 20710400Sstephan.diestelhorst@arm.cominline int 20810400Sstephan.diestelhorst@arm.compopCount(uint64_t val) { 20910400Sstephan.diestelhorst@arm.com#ifndef __has_builtin 21010400Sstephan.diestelhorst@arm.com #define __has_builtin(foo) 0 21110400Sstephan.diestelhorst@arm.com#endif 21210400Sstephan.diestelhorst@arm.com#if defined(__GNUC__) || (defined(__clang__) && __has_builtin(__builtin_popcountl)) 21310400Sstephan.diestelhorst@arm.com return __builtin_popcountl(val); 21410400Sstephan.diestelhorst@arm.com#else 21510400Sstephan.diestelhorst@arm.com const uint64_t m1 = 0x5555555555555555; // ..010101b 21610400Sstephan.diestelhorst@arm.com const uint64_t m2 = 0x3333333333333333; // ..110011b 21710400Sstephan.diestelhorst@arm.com const uint64_t m4 = 0x0f0f0f0f0f0f0f0f; // ..001111b 21810400Sstephan.diestelhorst@arm.com const uint64_t sum = 0x0101010101010101; 21910400Sstephan.diestelhorst@arm.com 22010400Sstephan.diestelhorst@arm.com val -= (val >> 1) & m1; // 2 bits count -> 2 bits 22110400Sstephan.diestelhorst@arm.com val = (val & m2) + ((val >> 2) & m2); // 4 bits count -> 4 bits 22210400Sstephan.diestelhorst@arm.com val = (val + (val >> 4)) & m4; // 8 bits count -> 8 bits 22310400Sstephan.diestelhorst@arm.com return (val * sum) >> 56; // horizontal sum 22410400Sstephan.diestelhorst@arm.com#endif // defined(__GNUC__) || (defined(__clang__) && __has_builtin(__builtin_popcountl)) 22510400Sstephan.diestelhorst@arm.com} 22611932Ssascha.bischoff@arm.com 22711932Ssascha.bischoff@arm.com/** 22811932Ssascha.bischoff@arm.com * Align to the next highest power of two. 22911932Ssascha.bischoff@arm.com * 23011932Ssascha.bischoff@arm.com * The number passed in is aligned to the next highest power of two, 23111932Ssascha.bischoff@arm.com * if it is not already a power of two. Please note that if 0 is 23211932Ssascha.bischoff@arm.com * passed in, 0 is returned. 23311932Ssascha.bischoff@arm.com * 23411932Ssascha.bischoff@arm.com * This code has been modified from the following: 23511932Ssascha.bischoff@arm.com * http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 23611932Ssascha.bischoff@arm.com */ 23711932Ssascha.bischoff@arm.cominline uint64_t alignToPowerOfTwo(uint64_t val) 23811932Ssascha.bischoff@arm.com{ 23911932Ssascha.bischoff@arm.com val--; 24011932Ssascha.bischoff@arm.com val |= val >> 1; 24111932Ssascha.bischoff@arm.com val |= val >> 2; 24211932Ssascha.bischoff@arm.com val |= val >> 4; 24311932Ssascha.bischoff@arm.com val |= val >> 8; 24411932Ssascha.bischoff@arm.com val |= val >> 16; 24511932Ssascha.bischoff@arm.com val |= val >> 32; 24611932Ssascha.bischoff@arm.com val++; 24711932Ssascha.bischoff@arm.com 24811932Ssascha.bischoff@arm.com return val; 24911932Ssascha.bischoff@arm.com}; 25011932Ssascha.bischoff@arm.com 2511112SN/A#endif // __BASE_BITFIELD_HH__ 252