12SN/A/* 214045Snikos.nikoleris@arm.com * Copyright (c) 2017, 2019 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 4212226Sgiacomo.travaglini@arm.com * Giacomo Travaglini 432SN/A */ 442SN/A 451112SN/A#ifndef __BASE_BITFIELD_HH__ 461112SN/A#define __BASE_BITFIELD_HH__ 472SN/A 4811800Sbrandon.potter@amd.com#include <inttypes.h> 4912226Sgiacomo.travaglini@arm.com#include <cassert> 5012226Sgiacomo.travaglini@arm.com#include <cstddef> 5112226Sgiacomo.travaglini@arm.com#include <type_traits> 5212226Sgiacomo.travaglini@arm.com 5312226Sgiacomo.travaglini@arm.com/** Lookup table used for High Speed bit reversing */ 5412226Sgiacomo.travaglini@arm.comextern const uint8_t reverseLookUpTable[]; 552SN/A 562SN/A/** 572SN/A * Generate a 64-bit mask of 'nbits' 1s, right justified. 582SN/A */ 592SN/Ainline uint64_t 602SN/Amask(int nbits) 612SN/A{ 622SN/A return (nbits == 64) ? (uint64_t)-1LL : (1ULL << nbits) - 1; 632SN/A} 642SN/A 652SN/A/** 662SN/A * Extract the bitfield from position 'first' to 'last' (inclusive) 672SN/A * from 'val' and right justify it. MSB is numbered 63, LSB is 0. 682SN/A */ 692SN/Atemplate <class T> 702SN/Ainline 712SN/AT 722SN/Abits(T val, int first, int last) 732SN/A{ 742SN/A int nbits = first - last + 1; 752SN/A return (val >> last) & mask(nbits); 762SN/A} 772SN/A 782SN/A/** 794661Sksewell@umich.edu * Extract the bit from this position from 'val' and right justify it. 804661Sksewell@umich.edu */ 814661Sksewell@umich.edutemplate <class T> 824661Sksewell@umich.eduinline 834661Sksewell@umich.eduT 844661Sksewell@umich.edubits(T val, int bit) 854661Sksewell@umich.edu{ 864661Sksewell@umich.edu return bits(val, bit, bit); 874661Sksewell@umich.edu} 884661Sksewell@umich.edu 894661Sksewell@umich.edu/** 903814Ssaidi@eecs.umich.edu * Mask off the given bits in place like bits() but without shifting. 913814Ssaidi@eecs.umich.edu * msb = 63, lsb = 0 923814Ssaidi@eecs.umich.edu */ 933814Ssaidi@eecs.umich.edutemplate <class T> 943814Ssaidi@eecs.umich.eduinline 953814Ssaidi@eecs.umich.eduT 963814Ssaidi@eecs.umich.edumbits(T val, int first, int last) 973814Ssaidi@eecs.umich.edu{ 983814Ssaidi@eecs.umich.edu return val & (mask(first+1) & ~mask(last)); 993814Ssaidi@eecs.umich.edu} 1003814Ssaidi@eecs.umich.edu 1014070Ssaidi@eecs.umich.eduinline uint64_t 1024070Ssaidi@eecs.umich.edumask(int first, int last) 1034070Ssaidi@eecs.umich.edu{ 1044070Ssaidi@eecs.umich.edu return mbits((uint64_t)-1LL, first, last); 1054070Ssaidi@eecs.umich.edu} 1064070Ssaidi@eecs.umich.edu 1073814Ssaidi@eecs.umich.edu/** 1082SN/A * Sign-extend an N-bit value to 64 bits. 1092SN/A */ 1102SN/Atemplate <int N> 1112SN/Ainline 11210537Sandreas.hansson@arm.comuint64_t 1132SN/Asext(uint64_t val) 1142SN/A{ 1152SN/A int sign_bit = bits(val, N-1, N-1); 1162SN/A return sign_bit ? (val | ~mask(N)) : val; 1172SN/A} 1182SN/A 1193422Sgblack@eecs.umich.edu/** 1203422Sgblack@eecs.umich.edu * Return val with bits first to last set to bit_val 1213422Sgblack@eecs.umich.edu */ 1223422Sgblack@eecs.umich.edutemplate <class T, class B> 1233422Sgblack@eecs.umich.eduinline 1243422Sgblack@eecs.umich.eduT 1253422Sgblack@eecs.umich.eduinsertBits(T val, int first, int last, B bit_val) 1263422Sgblack@eecs.umich.edu{ 1274425Ssaidi@eecs.umich.edu T t_bit_val = bit_val; 1283422Sgblack@eecs.umich.edu T bmask = mask(first - last + 1) << last; 1294425Ssaidi@eecs.umich.edu return ((t_bit_val << last) & bmask) | (val & ~bmask); 1303422Sgblack@eecs.umich.edu} 1313422Sgblack@eecs.umich.edu 1323422Sgblack@eecs.umich.edu/** 1334661Sksewell@umich.edu * Overloaded for access to only one bit in value 1344661Sksewell@umich.edu */ 1354661Sksewell@umich.edutemplate <class T, class B> 1364661Sksewell@umich.eduinline 1374661Sksewell@umich.eduT 1384661Sksewell@umich.eduinsertBits(T val, int bit, B bit_val) 1394661Sksewell@umich.edu{ 1404661Sksewell@umich.edu return insertBits(val, bit, bit, bit_val); 1414661Sksewell@umich.edu} 1424661Sksewell@umich.edu 1434661Sksewell@umich.edu/** 1443422Sgblack@eecs.umich.edu * A convenience function to replace bits first to last of val with bit_val 1453422Sgblack@eecs.umich.edu * in place. 1463422Sgblack@eecs.umich.edu */ 1473422Sgblack@eecs.umich.edutemplate <class T, class B> 1483422Sgblack@eecs.umich.eduinline 1493422Sgblack@eecs.umich.eduvoid 1503422Sgblack@eecs.umich.edureplaceBits(T& val, int first, int last, B bit_val) 1513422Sgblack@eecs.umich.edu{ 1523422Sgblack@eecs.umich.edu val = insertBits(val, first, last, bit_val); 1533422Sgblack@eecs.umich.edu} 1543422Sgblack@eecs.umich.edu 1554661Sksewell@umich.edu/** Overloaded function to allow to access only 1 bit*/ 1564661Sksewell@umich.edutemplate <class T, class B> 1574661Sksewell@umich.eduinline 1584661Sksewell@umich.eduvoid 1594661Sksewell@umich.edureplaceBits(T& val, int bit, B bit_val) 1604661Sksewell@umich.edu{ 1614661Sksewell@umich.edu val = insertBits(val, bit, bit, bit_val); 1624661Sksewell@umich.edu} 16312226Sgiacomo.travaglini@arm.com 16412226Sgiacomo.travaglini@arm.com/** 16512226Sgiacomo.travaglini@arm.com * Takes a variable lenght word and returns the mirrored version 16612226Sgiacomo.travaglini@arm.com * (Bit by bit, LSB=>MSB). 16712226Sgiacomo.travaglini@arm.com * 16812226Sgiacomo.travaglini@arm.com * algorithm from 16912226Sgiacomo.travaglini@arm.com * http://graphics.stanford.edu/~seander/bithacks.html 17012226Sgiacomo.travaglini@arm.com * #ReverseBitsByLookupTable 17112226Sgiacomo.travaglini@arm.com * 17212226Sgiacomo.travaglini@arm.com * @param val: variable lenght word 17312226Sgiacomo.travaglini@arm.com * @param size: number of bytes to mirror 17412226Sgiacomo.travaglini@arm.com * @return mirrored word 17512226Sgiacomo.travaglini@arm.com */ 17612226Sgiacomo.travaglini@arm.comtemplate <class T> 17712226Sgiacomo.travaglini@arm.comT 17812226Sgiacomo.travaglini@arm.comreverseBits(T val, std::size_t size = sizeof(T)) 17912226Sgiacomo.travaglini@arm.com{ 18012226Sgiacomo.travaglini@arm.com static_assert(std::is_integral<T>::value, "Expecting an integer type"); 18112226Sgiacomo.travaglini@arm.com 18212226Sgiacomo.travaglini@arm.com assert(size <= sizeof(T)); 18312226Sgiacomo.travaglini@arm.com 18412226Sgiacomo.travaglini@arm.com T output = 0; 18513824SAndrea.Mondelli@ucf.edu for (auto byte = 0; byte < size; byte++, val = static_cast<T>(val >> 8)) { 18612226Sgiacomo.travaglini@arm.com output = (output << 8) | reverseLookUpTable[val & 0xFF]; 18712226Sgiacomo.travaglini@arm.com } 18812226Sgiacomo.travaglini@arm.com 18912226Sgiacomo.travaglini@arm.com return output; 19012226Sgiacomo.travaglini@arm.com} 19112226Sgiacomo.travaglini@arm.com 1924103Ssaidi@eecs.umich.edu/** 1934103Ssaidi@eecs.umich.edu * Returns the bit position of the MSB that is set in the input 1944103Ssaidi@eecs.umich.edu */ 1954103Ssaidi@eecs.umich.eduinline 1964103Ssaidi@eecs.umich.eduint 1974103Ssaidi@eecs.umich.edufindMsbSet(uint64_t val) { 1984103Ssaidi@eecs.umich.edu int msb = 0; 1994103Ssaidi@eecs.umich.edu if (!val) 2004103Ssaidi@eecs.umich.edu return 0; 2014244Ssaidi@eecs.umich.edu if (bits(val, 63,32)) { msb += 32; val >>= 32; } 2024244Ssaidi@eecs.umich.edu if (bits(val, 31,16)) { msb += 16; val >>= 16; } 2034244Ssaidi@eecs.umich.edu if (bits(val, 15,8)) { msb += 8; val >>= 8; } 2044244Ssaidi@eecs.umich.edu if (bits(val, 7,4)) { msb += 4; val >>= 4; } 2054244Ssaidi@eecs.umich.edu if (bits(val, 3,2)) { msb += 2; val >>= 2; } 2064244Ssaidi@eecs.umich.edu if (bits(val, 1,1)) { msb += 1; } 2074103Ssaidi@eecs.umich.edu return msb; 2084103Ssaidi@eecs.umich.edu} 2094103Ssaidi@eecs.umich.edu 2106274Sgblack@eecs.umich.edu/** 2116274Sgblack@eecs.umich.edu * Returns the bit position of the LSB that is set in the input 2126274Sgblack@eecs.umich.edu */ 2136274Sgblack@eecs.umich.eduinline int 2146274Sgblack@eecs.umich.edufindLsbSet(uint64_t val) { 2156274Sgblack@eecs.umich.edu int lsb = 0; 2166274Sgblack@eecs.umich.edu if (!val) 2176274Sgblack@eecs.umich.edu return sizeof(val) * 8; 2186274Sgblack@eecs.umich.edu if (!bits(val, 31,0)) { lsb += 32; val >>= 32; } 2196274Sgblack@eecs.umich.edu if (!bits(val, 15,0)) { lsb += 16; val >>= 16; } 2206274Sgblack@eecs.umich.edu if (!bits(val, 7,0)) { lsb += 8; val >>= 8; } 2216274Sgblack@eecs.umich.edu if (!bits(val, 3,0)) { lsb += 4; val >>= 4; } 2226274Sgblack@eecs.umich.edu if (!bits(val, 1,0)) { lsb += 2; val >>= 2; } 2236274Sgblack@eecs.umich.edu if (!bits(val, 0,0)) { lsb += 1; } 2246274Sgblack@eecs.umich.edu return lsb; 2256274Sgblack@eecs.umich.edu} 2266274Sgblack@eecs.umich.edu 22710400Sstephan.diestelhorst@arm.com/** 22810400Sstephan.diestelhorst@arm.com * Checks if a number is a power of two, or zero. 22910400Sstephan.diestelhorst@arm.com */ 23010400Sstephan.diestelhorst@arm.comtemplate <class T> 23110400Sstephan.diestelhorst@arm.cominline bool 23210400Sstephan.diestelhorst@arm.comisPow2(T v) { 23310400Sstephan.diestelhorst@arm.com return (v & (v - 1)) == (T)0; 23410400Sstephan.diestelhorst@arm.com} 23510400Sstephan.diestelhorst@arm.com 23610400Sstephan.diestelhorst@arm.com/** 23710400Sstephan.diestelhorst@arm.com * Returns the number of set ones in the provided value. 23810400Sstephan.diestelhorst@arm.com * PD algorithm from 23910400Sstephan.diestelhorst@arm.com * http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel 24010400Sstephan.diestelhorst@arm.com */ 24110400Sstephan.diestelhorst@arm.cominline int 24210400Sstephan.diestelhorst@arm.compopCount(uint64_t val) { 24310400Sstephan.diestelhorst@arm.com#ifndef __has_builtin 24410400Sstephan.diestelhorst@arm.com #define __has_builtin(foo) 0 24510400Sstephan.diestelhorst@arm.com#endif 24610400Sstephan.diestelhorst@arm.com#if defined(__GNUC__) || (defined(__clang__) && __has_builtin(__builtin_popcountl)) 24710400Sstephan.diestelhorst@arm.com return __builtin_popcountl(val); 24810400Sstephan.diestelhorst@arm.com#else 24910400Sstephan.diestelhorst@arm.com const uint64_t m1 = 0x5555555555555555; // ..010101b 25010400Sstephan.diestelhorst@arm.com const uint64_t m2 = 0x3333333333333333; // ..110011b 25110400Sstephan.diestelhorst@arm.com const uint64_t m4 = 0x0f0f0f0f0f0f0f0f; // ..001111b 25210400Sstephan.diestelhorst@arm.com const uint64_t sum = 0x0101010101010101; 25310400Sstephan.diestelhorst@arm.com 25410400Sstephan.diestelhorst@arm.com val -= (val >> 1) & m1; // 2 bits count -> 2 bits 25510400Sstephan.diestelhorst@arm.com val = (val & m2) + ((val >> 2) & m2); // 4 bits count -> 4 bits 25610400Sstephan.diestelhorst@arm.com val = (val + (val >> 4)) & m4; // 8 bits count -> 8 bits 25710400Sstephan.diestelhorst@arm.com return (val * sum) >> 56; // horizontal sum 25810400Sstephan.diestelhorst@arm.com#endif // defined(__GNUC__) || (defined(__clang__) && __has_builtin(__builtin_popcountl)) 25910400Sstephan.diestelhorst@arm.com} 26011932Ssascha.bischoff@arm.com 26111932Ssascha.bischoff@arm.com/** 26211932Ssascha.bischoff@arm.com * Align to the next highest power of two. 26311932Ssascha.bischoff@arm.com * 26411932Ssascha.bischoff@arm.com * The number passed in is aligned to the next highest power of two, 26511932Ssascha.bischoff@arm.com * if it is not already a power of two. Please note that if 0 is 26611932Ssascha.bischoff@arm.com * passed in, 0 is returned. 26711932Ssascha.bischoff@arm.com * 26811932Ssascha.bischoff@arm.com * This code has been modified from the following: 26911932Ssascha.bischoff@arm.com * http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 27011932Ssascha.bischoff@arm.com */ 27111932Ssascha.bischoff@arm.cominline uint64_t alignToPowerOfTwo(uint64_t val) 27211932Ssascha.bischoff@arm.com{ 27311932Ssascha.bischoff@arm.com val--; 27411932Ssascha.bischoff@arm.com val |= val >> 1; 27511932Ssascha.bischoff@arm.com val |= val >> 2; 27611932Ssascha.bischoff@arm.com val |= val >> 4; 27711932Ssascha.bischoff@arm.com val |= val >> 8; 27811932Ssascha.bischoff@arm.com val |= val >> 16; 27911932Ssascha.bischoff@arm.com val |= val >> 32; 28011932Ssascha.bischoff@arm.com val++; 28111932Ssascha.bischoff@arm.com 28211932Ssascha.bischoff@arm.com return val; 28311932Ssascha.bischoff@arm.com}; 28411932Ssascha.bischoff@arm.com 28513531Sjairo.balart@metempsy.com/** 28613531Sjairo.balart@metempsy.com * Count trailing zeros in a 32-bit value. 28713531Sjairo.balart@metempsy.com * 28814046Snikos.nikoleris@arm.com * @param An input value 28914046Snikos.nikoleris@arm.com * @return The number of trailing zeros or 32 if the value is zero. 29013531Sjairo.balart@metempsy.com */ 29113531Sjairo.balart@metempsy.cominline int ctz32(uint32_t value) 29213531Sjairo.balart@metempsy.com{ 29314046Snikos.nikoleris@arm.com return value ? __builtin_ctzl(value) : 32; 29413531Sjairo.balart@metempsy.com} 29513531Sjairo.balart@metempsy.com 29614045Snikos.nikoleris@arm.com/** 29714045Snikos.nikoleris@arm.com * Count trailing zeros in a 64-bit value. 29814045Snikos.nikoleris@arm.com * 29914045Snikos.nikoleris@arm.com * @param An input value 30014045Snikos.nikoleris@arm.com * @return The number of trailing zeros or 64 if the value is zero. 30114045Snikos.nikoleris@arm.com */ 30214045Snikos.nikoleris@arm.cominline int ctz64(uint64_t value) 30314045Snikos.nikoleris@arm.com{ 30414045Snikos.nikoleris@arm.com return value ? __builtin_ctzll(value) : 64; 30514045Snikos.nikoleris@arm.com} 30614045Snikos.nikoleris@arm.com 3071112SN/A#endif // __BASE_BITFIELD_HH__ 308