Bitmanip.h

Go to the documentation of this file.

//===-- temu-c/Bitmanip.h - Low level bit/byte manipulation -----*- C++ -*-===//
//
// TEMU: The Terma Emulator
// (c) Terma 2015, 2016, 2017
// Authors: Mattias Holm <maho (at) terma.com>
//
//===----------------------------------------------------------------------===//
 
#ifndef TEMU_BITMANIP_H
#define TEMU_BITMANIP_H
 
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
 
#ifndef __has_builtin
#define __has_builtin(x) 0
#endif
 
#ifdef __cplusplus
extern "C" {
#endif
 
/*!
 * Swap half words inside 32 bit word
 * \param Word The word to be swapped
 * \result the swapped word
 */
static inline uint32_t
temu_swap32Half(uint32_t Word)
{
  uint32_t Res = Word << 16 | Word >> 16;
  return Res;
}
 
/*!
 * Swap words inside 64 bit word
 * \param DWord The word to be swapped
 * \result the swapped word
 */
static inline uint64_t
temu_swap64Word(uint64_t DWord)
{
  uint64_t Res = DWord << 32 | DWord >> 32;
  return Res;
}
 
/*!
 * Swap bytes in 16 bit word
 * \param HWord The word to be swapped
 * \result the swapped word
 */
static inline uint16_t
temu_swap16(uint16_t HWord)
{
#if 1
  uint16_t Res = __builtin_bswap16(HWord);
#else
  uint16_t Res = HWord << 8 | HWord >> 8;
#endif
  return Res;
}
 
/*!
 * Swap bytes in 32 bit word
 * \param Word The word to be swapped
 * \result the swapped word
 */
static inline uint32_t
temu_swap32(uint32_t Word)
{
#if 1
  uint32_t Res = __builtin_bswap32(Word);
#else
  uint32_t Res =
      (((uint32_t)temu_swap16(Word)) << 16) | (uint32_t)temu_swap16(Word >> 16);
#endif
  return Res;
}
 
/*!
 * Swap bytes in 64 bit word
 * \param DWord The word to be swapped
 * \result the swapped word
 */
static inline uint64_t
temu_swap64(uint64_t DWord)
{
#if 1
  uint64_t Res = __builtin_bswap64(DWord);
#else
  uint64_t Res = (((uint64_t)temu_swap32(DWord)) << 32) |
                 (uint64_t)temu_swap32(DWord >> 32);
#endif
  return Res;
}
 
/*!
 * Swap between big endian and host endian. Note that at present we
 * only have little endian hosts, so these functions simply
 * wrap. However, they declare intent and it is recommended that you
 * use these for swapping when you want to go between little<->host
 * and big<->host.
 *
 * \param Word The word to be swapped
 * \result the swapped word
 */
static inline uint32_t
temu_swapBigHost32Half(uint32_t Word)
{
  return temu_swap32Half(Word);
}
 
/*!
 * Swap between big endian and host endian. Note that at present we
 * only have little endian hosts, so these functions simply
 * wrap. However, they declare intent and it is recommended that you
 * use these for swapping when you want to go between little<->host
 * and big<->host.
 *
 * \param DWord The word to be swapped
 * \result the swapped word
 */
static inline uint64_t
temu_swapBigHost64Word(uint64_t DWord)
{
  return temu_swap64Word(DWord);
}
 
/*!
 * Swap between little endian to host endian. Note that at present we
 * only have little endian hosts, so these functions simply
 * wrap. However, they declare intent and it is recommended that you
 * use these for swapping when you want to go between little<->host
 * and big<->host.
 *
 * \param Word The word to be swapped
 * \result the swapped word
 */
static inline uint32_t
temu_swapLittleHost32Half(uint32_t Word)
{
  return Word;
}
 
/*!
 * Swap between little endian and host endian. Note that at present we
 * only have little endian hosts, so these functions simply
 * wrap. However, they declare intent and it is recommended that you
 * use these for swapping when you want to go between little<->host
 * and big<->host.
 *
 * \param DWord The word to be swapped
 * \result the swapped word
 */
static inline uint64_t
temu_swapLittleHost64Word(uint64_t DWord)
{
  return DWord;
}
 
/*!
 * Swap between big endian and host endian. Note that at present we
 * only have little endian hosts, so these functions simply
 * wrap. However, they declare intent and it is recommended that you
 * use these for swapping when you want to go between little<->host
 * and big<->host.
 *
 * \param HWord The word to be swapped
 * \result the swapped word
 */
static inline uint16_t
temu_swapBigHost16(uint16_t HWord)
{
  return temu_swap16(HWord);
}
 
/*!
 * Swap between big endian and host endian. Note that at present we
 * only have little endian hosts, so these functions simply
 * wrap. However, they declare intent and it is recommended that you
 * use these for swapping when you want to go between little<->host
 * and big<->host.
 *
 * \param Word The word to be swapped
 * \result the swapped word
 */
static inline uint32_t
temu_swapBigHost32(uint32_t Word)
{
  return temu_swap32(Word);
}
 
/*!
 * Swap between big endian and host endian. Note that at present we
 * only have little endian hosts, so these functions simply
 * wrap. However, they declare intent and it is recommended that you
 * use these for swapping when you want to go between little<->host
 * and big<->host.
 *
 * \param DWord The word to be swapped
 * \result the swapped word
 */
static inline uint64_t
temu_swapBigHost64(uint64_t DWord)
{
  return temu_swap64(DWord);
}
 
/*!
 * Swap between little endian and host endian. Note that at present we
 * only have little endian hosts, so these functions simply
 * wrap. However, they declare intent and it is recommended that you
 * use these for swapping when you want to go between little<->host
 * and big<->host.
 *
 * \param HWord The word to be swapped
 * \result the swapped word
 */
static inline uint16_t
temu_swapLittleHost16(uint16_t HWord)
{
  return HWord;
}
 
/*!
 * Swap between little endian and host endian. Note that at present we
 * only have little endian hosts, so these functions simply
 * wrap. However, they declare intent and it is recommended that you
 * use these for swapping when you want to go between little<->host
 * and big<->host.
 *
 * \param Word The word to be swapped
 * \result the swapped word
 */
static inline uint32_t
temu_swapLittleHost32(uint32_t Word)
{
  return Word;
}
 
/*!
 * Swap between little endian and host endian. Note that at present we
 * only have little endian hosts, so these functions simply
 * wrap. However, they declare intent and it is recommended that you
 * use these for swapping when you want to go between little<->host
 * and big<->host.
 *
 * \param DWord The word to be swapped
 * \result the swapped word
 */
static inline uint64_t
temu_swapLittleHost64(uint64_t DWord)
{
  return DWord;
}
 
/*!
 * Count trailing zeroes, this can be used as a square root on a power
 * of 2 word.
 *
 * \param Word the word, in which trailing zeros to be counted
 * \result Number of trailing zeros in Word
 */
static inline int
temu_ctz32(uint32_t Word)
{
  if (Word == 0)
    return 32; // Due to semantics of compiler ctz
  int Res = __builtin_ctz(Word);
  return Res;
}
 
/*!
 * Count leading zeroes
 *
 * \param Word the word, in which leading zeros to be counted
 * \result Number of leading zeros in Word
 */
static inline int
temu_clz32(uint32_t Word)
{
  if (Word == 0)
    return 32;
  int Res = __builtin_clz(Word);
  return Res;
}
 
/*!
 * Count number of bits set in word
 *
 * \param Word The word, in which bits to be counted
 * \result The number of bits
 */
static inline int
temu_popcount32(uint32_t Word)
{
  int Res = __builtin_popcount(Word);
  return Res;
}
 
/*!
 * Compute parity of word
 *
 * \param Word The word, in which parity to be computed
 * \result The parity of the word
 */
static inline int
temu_parity32(uint32_t Word)
{
  int Res = __builtin_parity(Word);
  return Res;
}
 
/*!
 * Count trailing zeroes
 *
 * \param Word The word, in which trailing zeros to be counted
 * \result The number of trailing zeros in Word
 */
static inline int
temu_ctz64(uint64_t Word)
{
  if (Word == 0)
    return 64;
  int Res = __builtin_ctzl(Word);
  return Res;
}
 
/*!
 * Count leading zeroes
 *
 * \param Word The word, in which leading zeros to be counted
 * \result The number of leading zeros in Word
 */
static inline int
temu_clz64(uint64_t Word)
{
  if (Word == 0)
    return 64;
  int Res = __builtin_clzl(Word);
  return Res;
}
 
 
/*!
 * Count trailing zeroes, this can be used as a square root on a power
 * of 2 word.
 *
 * \param Word the word, in which trailing zeros to be counted
 * \result Number of trailing zeros in Word
 */
static inline int
temu_ctz16(uint16_t Word)
{
  if (Word == 0)
    return 16; // Due to semantics of compiler ctz
  int Res = __builtin_ctz(Word);
  return Res;
}
 
/*!
 * Count leading zeroes
 *
 * \param Word the word, in which leading zeros to be counted
 * \result Number of leading zeros in Word
 */
static inline int
temu_clz16(uint16_t Word)
{
  if (Word == 0)
    return 16;
  int Res = __builtin_clz(Word) - 16;
  return Res;
}
 
/*!
 * Count count number of bit set
 *
 * \param Word The word, in which bits to be counted
 * \result The number of bits set in Word
 */
static inline int
temu_popcount64(uint64_t Word)
{
  int Res = __builtin_popcountl(Word);
  return Res;
}
 
/*!
 * Compute parity
 *
 * \param Word The word, in which parity to be computed
 * \result The parity of word
 */
static inline int
temu_parity64(uint64_t Word)
{
  int Res = __builtin_parityl(Word);
  return Res;
}
 
/*!
 * Predicate for checking if word is a power of 2
 * See Hacker's Delight, 1st edition, p11
 *
 * \param Word The word to be checked
 * \result 0 for false, otherwise true
 */
static inline int
temu_isPow2_32(uint32_t Word)
{
  if (Word) {
    return (Word & (Word - 1)) == 0;
  }
  return 0;
}
 
/*!
 * Predicate for checking if word is a power of 2
 *
 * \param Word The word to be checked
 * \result 0 for false, otherwise true
 */
static inline int
temu_isPow2_64(uint64_t Word)
{
  if (Word) {
    return (Word & (Word - 1)) == 0;
  }
  return 0;
}
 
/*!
 * Clear lower set bit in word
 *
 * \param Word The word, in which the lower set bit will be cleared
 * \result A copy of Word with ther lowest set bit cleared
 */
static inline uint32_t
temu_clearLeftmostBit32(uint32_t Word)
{
  return Word & (Word - 1);
}
 
/*!
 * Clear lower set bit in word
 *
 * \param Word The word, in which the lower set bit will be cleared
 * \result A copy of Word with ther lowest set bit cleared
 */
static inline uint64_t
temu_clearLeftmostBit64(uint64_t Word)
{
  return Word & (Word - 1);
}
 
/*!
 * Set right most bit that is zero
 *
 * \param Word The word, in which the right most set bit will be cleared
 * \result A copy of Word, with the right most bit cleared
 */
static inline uint32_t
temu_setRightmostZeroBit32(uint32_t Word)
{
  return Word | (Word + 1);
}
 
/*!
 * Set right most bit that is zero
 *
 * \param Word The word, in which the right most set bit will be set
 * \result A copy of Word, with the right most bit cleared
 */
static inline uint64_t
temu_setRightmostZeoroBit64(uint64_t Word)
{
  return Word | (Word + 1);
}
 
/*!
 * Isolate left most bit
 *
 * \param Word The word, in which the right most set bit will be cleared
 * \result A copy of word, in which the right most set bit will be cleared
 */
static inline uint32_t
temu_isolateLeftmostBit32(uint32_t Word)
{
  return Word & -Word;
}
 
/*!
 * Isolate left most bit
 *
 * \param Word The word, in which the right most set bit will be cleared
 * \result A copy of word, in which the right most set bit will be cleared
 */
static inline uint64_t
temu_isolateLeftmostBit64(uint64_t Word)
{
  return Word & -Word;
}
 
/*!
 * Isolate right most bit with value zero (it will be 1 in the result)
 *
 * \param Word The word, in which the right most bit with value zero will be
 * isolated \result A copy of Word, in which the right most bit with value zero
 * will be isolated
 */
static inline uint32_t
temu_isolateRightMostZeroBit32(uint32_t Word)
{
  return (~Word) & (Word + 1);
}
 
/*!
 * Isolate right most bit with value zero (it will be 1 in the result)
 *
 * \param Word The word, in which the right most bit with value zero will be
 * isolated \result A copy of Word, in which the right most bit with value zero
 * will be isolated
 */
static inline uint64_t
temu_isolateRightMostZeroBit64(uint64_t Word)
{
  return (~Word) & (Word + 1);
}
 
/*!
 * Get word with all trailing zeroes set
 *
 * \param Word The word, in which trailing zeros to be set
 * \result A copy of word, with trailing zeros set
 */
static inline uint32_t
temu_identifyTrailingZeroes32(uint32_t Word)
{
  return (~Word) & (Word - 1);
}
 
/*!
 * Get word with all trailing zeroes set
 *
 * \param Word The word, in which trailing zeros to be set
 * \result A copy of word, with trailing zeros set
 */
static inline uint64_t
temu_identifyTrailingZeroes64(uint64_t Word)
{
  return (~Word) & (Word - 1);
}
 
/*!
 * Get word with all trailing zeroes set, and the fist bit set
 *
 * \param Word Word to get trailing zero mask from
 * \result Word, with all trailing zeroes set, and the fist bit set
 */
static inline uint32_t
temu_identifyTrailingZeroesAndFirst32(uint32_t Word)
{
  return Word ^ (Word - 1);
}
 
/*!
 * Get word with all trailing zeroes set, and the fist bit set
 *
 * \param Word Word to get trailing zero mask from
 * \result Word, with all trailing zeroes set, and the fist bit set
 */
static inline uint64_t
temu_identifyTrailingZeroesAndFirst64(uint64_t Word)
{
  return Word ^ (Word - 1);
}
 
/*!
 * Propagate the right most set bit to the bits below it
 *
 * \param Word Word to propagate bits
 * \result Word with lower zero-bits set
 */
static inline uint32_t
temu_propagateRightMostBit32(uint32_t Word)
{
  return Word | (Word - 1);
}
 
/*!
 * Propagate the right most set bit to the bits below it
 *
 * \param Word Word to propagate bits
 * \result Word with lower zero-bits set
 */
static inline uint64_t
temu_propagateRightMostBit64(uint64_t Word)
{
  return Word | (Word - 1);
}
 
/*!
 * Clear right most bit in a word
 *
 * \param Word The word, in which right most bit to be cleared
 * \result A copy of Word, in which right most bit to be cleared
 */
static inline uint32_t
temu_clearRightMostBits32(uint32_t Word)
{
  return ((Word | (Word - 1)) + 1) & Word;
}
 
/*!
 * Clear right most bit in a word
 *
 * \param Word The word, in which right most bit to be cleared
 * \result A copy of Word, in which right most bit to be cleared
 */
static inline uint64_t
temu_clearRightMostBits64(uint64_t Word)
{
  return ((Word | (Word - 1)) + 1) & Word;
}
 
/*!
 * Round down to multiples of specified power of 2
 *
 * \param Word The word to be rounded
 * \param Size Power of 2 sized block
 * \result A rounded copy of Word
 */
static inline uint32_t
temu_roundDownToPow2_32(uint32_t Word, uint32_t Size)
{
  uint32_t Res = Word & -Size;
  return Res;
}
 
/*!
 * Round down to multiples of specified power of 2
 *
 * \param Word The word to be rounded
 * \param Size Power of 2 sided block
 * \result A rounded copy of Word
 */
static inline uint64_t
temu_roundDownToPow2_64(uint64_t Word, uint64_t Size)
{
  uint64_t Res = Word & -Size;
  return Res;
}
 
/*!
 * Round up to multiples of specified power of 2
 *
 * \param Word The word to be rounded
 * \param Size Power of 2 sized block
 * \result A rounded copy of Word
 */
static inline uint32_t
temu_roundUpToPow2_32(uint32_t Word, uint32_t Size)
{
  uint32_t Res = (Word + (Size - 1)) & -Size;
  return Res;
}
 
/*!
 * Round up to multiples of specified power of 2
 *
 * \param Word The word to be rounded
 * \param Size Power of 2 sized block
 * \result A rounded copy of Word
 */
static inline uint64_t
temu_roundUpToPow2_64(uint64_t Word, uint64_t Size)
{
  uint64_t Res = (Word + (Size - 1)) & -Size;
  return Res;
}
 
/*!
 * Checks whether A + L crosses power of 2 boundary (e.g. page)
 *
 * \param A Address value
 * \param L Length / offset value
 * \param Size boundary size (power of 2 size)
 * \result True if boundary is crossed. False otherwise.
 */
static inline bool
temu_crossesBoundary32(uint32_t A, uint32_t L, uint32_t Size)
{
  return -(A | -Size) < L;
}
 
/*!
 * Checks whether A + L crosses power of 2 boundary (e.g. page)
 *
 * \param A Address value
 * \param L Length / offset value
 * \param Size boundary size (power of 2 size)
 * \result True if boundary is crossed. False otherwise.
 */
static inline bool
temu_crossesBoundary64(uint64_t A, uint64_t L, uint64_t Size)
{
  return -(A | -Size) < L;
}
 
/*!
 * Round up to nearest power of 2
 *
 * \param Word The word to be round
 * \result A copy of Word rounded up to nearest power of 2
 */
static inline uint32_t
temu_roundUpNearestPow2_32(uint32_t Word)
{
  uint32_t Res = 1 << (32 - temu_clz32(Word - 1));
  return Res;
}
 
/*!
 * Round up to nearest power of 2
 *
 * \param Word The word to be round
 * \result A copy of Word rounded up to nearest power of 2
 */
static inline uint64_t
temu_roundUpNearestPow2_64(uint64_t Word)
{
  uint64_t Res = UINT64_C(1) << (64 - temu_clz64(Word - 1));
  return Res;
}
 
/*!
 * Round down to nearest power of 2
 *
 * \param Word The word to be round
 * \result A copy of Word rounded down to nearest power of 2
 */
static inline uint32_t
temu_roundDownNearestPow2_32(uint32_t Word)
{
  uint32_t Res = 1 << (31 - temu_clz32(Word));
  return Res;
}
 
/*!
 * Round up to nearest power of 2
 *
 * \param Word The word to be round
 * \result A copy of Word rounded down to nearest power of 2
 */
static inline uint64_t
temu_roundDownNearestPow2_64(uint64_t Word)
{
  uint64_t Res = UINT64_C(1) << (63 - temu_clz64(Word));
  return Res;
}
 
/*!
 * Reverses bits in a 16 bit word.
 *
 * \note that this should be replaced with __buintin_bitreverse16(), but that is
 * only supported in clang at present, not GCC.
 *
 * \param Word The word to reverse the bits in
 * \result Word with reversed bits.
 */
 
static inline uint16_t
temu_bitreverse16(uint16_t Word)
{
#if __has_builtin(__builtin_bitreverse16)
  return __builtin_bitreverse16(Word);
#else
  uint32_t Res = (Word & 0x55555555) << 1 | (Word & 0xaaaaaaaa) >> 1;
  Res = (Res & 0x33333333) << 2 | (Res & 0xcccccccc) >> 2;
  Res = (Res & 0x0f0f0f0f) << 4 | (Res & 0xf0f0f0f0) >> 4;
  Res = (Res & 0x00ff00ff) << 8 | (Res & 0xff00ff00) >> 8;
  return Res;
#endif
}
 
/*!
 * Reverses bits in a 32 bit word.
 *
 * \note that this should be replaced with __buintin_bitreverse32(),
 * but that is only supported in clang at present, not GCC.
 *
 * \param Word The word to reverse the bits in
 * \result Word with reversed bits.
 */
static inline uint32_t
temu_bitreverse32(uint32_t Word)
{
#if __has_builtin(__builtin_bitreverse32)
  return __builtin_bitreverse32(Word);
#else
  uint32_t Res = (Word & 0x55555555) << 1 | (Word & 0xaaaaaaaa) >> 1;
  Res = (Res & 0x33333333) << 2 | (Res & 0xcccccccc) >> 2;
  Res = (Res & 0x0f0f0f0f) << 4 | (Res & 0xf0f0f0f0) >> 4;
  Res = (Res & 0x00ff00ff) << 8 | (Res & 0xff00ff00) >> 8;
  Res = (Res & 0x0000ffff) << 16 | (Res & 0xffff0000) >> 16;
  return Res;
#endif
}
 
static inline uint64_t
temu_bitreverse64(uint64_t DWord)
{
#if __has_builtin(__builtin_bitreverse64)
  return __builtin_bitreverse64(DWord);
#else
  uint64_t reversed = (uint64_t)temu_bitreverse32(DWord >> 32) |
                      ((uint64_t)temu_bitreverse32(DWord) << 32);
  return reversed;
#endif
}
 
static inline uint64_t
temu_signExtend_8_64(uint8_t Val)
{
  return (int64_t)(int8_t)Val;
}
 
static inline uint32_t
temu_signExtend_8_32(uint8_t Val)
{
  return (int32_t)(int8_t)Val;
}
 
static inline uint16_t
temu_signExtend_8_16(uint8_t Val)
{
  return (int16_t)(int8_t)Val;
}
 
/*!
 * Checks whether the addition of signed inputs with carry would overflow;
 * a+b+carry
 *
 * \param a is the first input
 * \param b is the second input
 * \param carry is the carry; can be either zero or one
 * \return true if it overflows, false otherwise
 */
static inline uint32_t
temu_signed32AddOverflows(uint32_t a, uint32_t b, uint32_t carry)
{
  assert(carry <= 1);
  return ((((a + b + carry) ^ a) & ((a + b + carry) ^ b)) >> 31) & 1;
}
 
static inline uint32_t
temu_rotate32Left(uint32_t a, uint32_t steps)
{
#if __has_builtin(__builtin_rotateleft32)
  return __builtin_rotateleft32(a, steps);
#else
  return ((a << steps) | (a >> (32 - steps)));
#endif
}
 
static inline uint32_t
temu_rotate32Right(uint32_t a, uint32_t steps)
{
#if __has_builtin(__builtin_rotateright32)
  return __builtin_rotateright32(a, steps);
#else
  return ((a >> steps) | (a << (32 - steps)));
#endif
}
 
#ifdef __cplusplus
}
#endif
 
#endif /* !TEMU_BITMANIP_H */