CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In
hrydgard

CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!

GitHub Repository: hrydgard/ppsspp
 Path: blob/master/Common/BitSet.h
Views: 1401
1
// This file is under the public domain.

2


3
#pragma once

4


5
#include "ppsspp_config.h"

6
#include <cstdint>

7
#include <cstdlib>  // for byte swapping

8
#include <cstddef>

9
#include "CommonTypes.h"

10


11
// TODO: ARM has an intrinsic for the RBIT instruction in some compilers, __rbit.

12
inline u32 ReverseBits32(u32 v) {

13
	// http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel

14
	// swap odd and even bits

15
	v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);

16
	// swap consecutive pairs

17
	v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);

18
	// swap nibbles ...

19
	v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);

20
	// swap bytes

21
	v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);

22
	// swap 2-byte long pairs

23
	v = (v >> 16) | (v << 16);

24
	return v;

25
}

26


27
#ifdef _WIN32

28
#include <intrin.h>

29
template <typename T>

30
inline int CountSetBits(T v) {

31
	// from https://graphics.stanford.edu/~seander/bithacks.html

32
	// GCC has this built in, but MSVC's intrinsic will only emit the actual

33
	// POPCNT instruction, which we're not depending on

34
	v = v - ((v >> 1) & (T)~(T)0/3);

35
	v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3);

36
	v = (v + (v >> 4)) & (T)~(T)0/255*15;

37
	return (T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * 8;

38
}

39
inline int LeastSignificantSetBit(u32 val)

40
{

41
	unsigned long index;

42
	_BitScanForward(&index, val);

43
	return (int)index;

44
}

45
#if PPSSPP_ARCH(AMD64)

46
inline int LeastSignificantSetBit(u64 val)

47
{

48
	unsigned long index;

49
	_BitScanForward64(&index, val);

50
	return (int)index;

51
}

52


53
#endif

54
#else

55
inline int CountSetBits(u32 val) { return __builtin_popcount(val); }

56
inline int CountSetBits(u64 val) { return __builtin_popcountll(val); }

57
inline int LeastSignificantSetBit(u32 val) { return __builtin_ctz(val); }

58
inline int LeastSignificantSetBit(u64 val) { return __builtin_ctzll(val); }

59
#endif

60


61
// Byteswapping

62
// Just in case this has been defined by platform

63
#undef swap16

64
#undef swap32

65
#undef swap64

66


67
#ifdef _WIN32

68
inline uint16_t swap16(uint16_t _data) { return _byteswap_ushort(_data); }

69
inline uint32_t swap32(uint32_t _data) { return _byteswap_ulong(_data); }

70
inline uint64_t swap64(uint64_t _data) { return _byteswap_uint64(_data); }

71
#elif defined(__GNUC__)

72
inline uint16_t swap16(uint16_t _data) { return __builtin_bswap16(_data); }

73
inline uint32_t swap32(uint32_t _data) { return __builtin_bswap32(_data); }

74
inline uint64_t swap64(uint64_t _data) { return __builtin_bswap64(_data); }

75
#else

76
// Slow generic implementation. Hopefully this never hits

77
inline uint16_t swap16(uint16_t data) { return (data >> 8) | (data << 8); }

78
inline uint32_t swap32(uint32_t data) { return (swap16(data) << 16) | swap16(data >> 16); }

79
inline uint64_t swap64(uint64_t data) { return ((uint64_t)swap32(data) << 32) | swap32(data >> 32); }

80
#endif

81


82
inline uint16_t swap16(const uint8_t* _pData) { return swap16(*(const uint16_t*)_pData); }

83
inline uint32_t swap32(const uint8_t* _pData) { return swap32(*(const uint32_t*)_pData); }

84
inline uint64_t swap64(const uint8_t* _pData) { return swap64(*(const uint64_t*)_pData); }

85


86