bit.h Source File (original) (raw)

14#ifndef LLVM_ADT_BIT_H

15#define LLVM_ADT_BIT_H

18#include

19#include

20#include

21#include <type_traits>

23#if !__has_builtin(__builtin_bit_cast)

24#include

25#endif

27#if defined(_MSC_VER) && !defined(_DEBUG)

28#include

29#endif

31#if defined(__linux__) || defined(__GNU__) || defined(__HAIKU__) || \

32 defined(__Fuchsia__) || defined(__EMSCRIPTEN__) || defined(__NetBSD__) || \

33 defined(__OpenBSD__) || defined(__DragonFly__) || defined(__managarm__)

34#include <endian.h>

35#elif defined(_AIX)

36#include <sys/machine.h>

37#elif defined(__sun)

39#include <sys/types.h>

40#define BIG_ENDIAN 4321

41#define LITTLE_ENDIAN 1234

42#if defined(_BIG_ENDIAN)

43#define BYTE_ORDER BIG_ENDIAN

44#else

45#define BYTE_ORDER LITTLE_ENDIAN

46#endif

47#elif defined(__MVS__)

48#define BIG_ENDIAN 4321

49#define LITTLE_ENDIAN 1234

50#define BYTE_ORDER BIG_ENDIAN

51#else

52#if !defined(BYTE_ORDER) && !defined(_WIN32)

53#include <machine/endian.h>

54#endif

55#endif

57#ifdef _MSC_VER

61extern "C" {

62unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask);

63unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask);

64unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask);

65unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask);

66}

67#endif

69namespace llvm {

74#if defined(BYTE_ORDER) && defined(BIG_ENDIAN) && BYTE_ORDER == BIG_ENDIAN

76#else

78#endif

79};

84template <

85 typename To, typename From,

86 typename = std::enable_if_t<sizeof(To) == sizeof(From)>,

87 typename = std::enable_if_t<std::is_trivially_constructible::value>,

88 typename = std::enable_if_t<std::is_trivially_copyable::value>,

89 typename = std::enable_if_t<std::is_trivially_copyable::value>>

90[[nodiscard]] inline To bit_cast(const From &from) noexcept {

91#if __has_builtin(__builtin_bit_cast)

92 return __builtin_bit_cast(To, from);

93#else

94 To to;

95 std::memcpy(&to, &from, sizeof(To));

96 return to;

97#endif

98}

100

101template <typename T, typename = std::enable_if_t<std::is_integral_v>>

102[[nodiscard]] constexpr T byteswap(T V) noexcept {

103 if constexpr (sizeof(T) == 1) {

104 return V;

105 } else if constexpr (sizeof(T) == 2) {

107#if defined(_MSC_VER) && !defined(_DEBUG)

108

109

110 return _byteswap_ushort(UV);

111#else

114 return Hi | Lo;

115#endif

116 } else if constexpr (sizeof(T) == 4) {

118#if __has_builtin(__builtin_bswap32)

119 return __builtin_bswap32(UV);

120#elif defined(_MSC_VER) && !defined(_DEBUG)

121 return _byteswap_ulong(UV);

122#else

123 uint32_t Byte0 = UV & 0x000000FF;

124 uint32_t Byte1 = UV & 0x0000FF00;

125 uint32_t Byte2 = UV & 0x00FF0000;

126 uint32_t Byte3 = UV & 0xFF000000;

127 return (Byte0 << 24) | (Byte1 << 8) | (Byte2 >> 8) | (Byte3 >> 24);

128#endif

129 } else if constexpr (sizeof(T) == 8) {

131#if __has_builtin(__builtin_bswap64)

132 return __builtin_bswap64(UV);

133#elif defined(_MSC_VER) && !defined(_DEBUG)

134 return _byteswap_uint64(UV);

135#else

138 return (Hi << 32) | Lo;

139#endif

140 } else {

141 static_assert(!sizeof(T *), "Don't know how to handle the given type.");

142 return 0;

143 }

144}

145

146template <typename T, typename = std::enable_if_t<std::is_unsigned_v>>

150

151

152

153

154template [[nodiscard]] constexpr int popcount(T Value) noexcept {

155 static_assert(std::is_unsigned_v, "T must be an unsigned integer type");

156 static_assert(sizeof(T) <= 8, "T must be 8 bytes or less");

157

158 if constexpr (sizeof(T) <= 4) {

159#if defined(__GNUC__)

160 return (int)__builtin_popcount(Value);

161#else

163 V = V - ((V >> 1) & 0x55555555);

164 V = (V & 0x33333333) + ((V >> 2) & 0x33333333);

165 return int(((V + (V >> 4) & 0xF0F0F0F) * 0x1010101) >> 24);

166#endif

167 } else {

168#if defined(__GNUC__)

169 return (int)__builtin_popcountll(Value);

170#else

172 V = V - ((V >> 1) & 0x5555555555555555ULL);

173 V = (V & 0x3333333333333333ULL) + ((V >> 2) & 0x3333333333333333ULL);

174 V = (V + (V >> 4)) & 0x0F0F0F0F0F0F0F0FULL;

175 return int((uint64_t)(V * 0x0101010101010101ULL) >> 56);

176#endif

177 }

178}

179

180

181

182

183

184

185

186

187

189 static_assert(std::is_unsigned_v,

190 "Only unsigned integral types are allowed.");

191

192

193 return llvm::popcount(static_cast<std::make_unsigned_t>((Val & -Val) - 1));

194}

195

196

197

198

199

200

201

202template [[nodiscard]] int countr_zero(T Val) {

203 static_assert(std::is_unsigned_v,

204 "Only unsigned integral types are allowed.");

205 if (!Val)

206 return std::numeric_limits::digits;

207

208

209 if constexpr (sizeof(T) <= 4) {

210#if __has_builtin(__builtin_ctz) || defined(__GNUC__)

211 return __builtin_ctz(Val);

212#elif defined(_MSC_VER)

213 unsigned long Index;

214 _BitScanForward(&Index, Val);

215 return Index;

216#endif

217 } else if constexpr (sizeof(T) == 8) {

218#if __has_builtin(__builtin_ctzll) || defined(__GNUC__)

219 return __builtin_ctzll(Val);

220#elif defined(_MSC_VER) && defined(_M_X64)

221 unsigned long Index;

222 _BitScanForward64(&Index, Val);

223 return Index;

224#endif

225 }

226

228}

229

230

231

232

233

234

235

236template [[nodiscard]] int countl_zero(T Val) {

237 static_assert(std::is_unsigned_v,

238 "Only unsigned integral types are allowed.");

239 if (!Val)

240 return std::numeric_limits::digits;

241

242

243 if constexpr (sizeof(T) == 4) {

244#if __has_builtin(__builtin_clz) || defined(__GNUC__)

245 return __builtin_clz(Val);

246#elif defined(_MSC_VER)

247 unsigned long Index;

248 _BitScanReverse(&Index, Val);

249 return Index ^ 31;

250#endif

251 } else if constexpr (sizeof(T) == 8) {

252#if __has_builtin(__builtin_clzll) || defined(__GNUC__)

253 return __builtin_clzll(Val);

254#elif defined(_MSC_VER) && defined(_M_X64)

255 unsigned long Index;

256 _BitScanReverse64(&Index, Val);

257 return Index ^ 63;

258#endif

259 }

260

261

262 unsigned ZeroBits = 0;

263 for (T Shift = std::numeric_limits::digits >> 1; Shift; Shift >>= 1) {

264 T Tmp = Val >> Shift;

265 if (Tmp)

266 Val = Tmp;

267 else

268 ZeroBits |= Shift;

269 }

270 return ZeroBits;

271}

272

273

274

275

276

277

278

279

281 static_assert(std::is_unsigned_v,

282 "Only unsigned integral types are allowed.");

284}

285

286

287

288

289

290

291

292

294 static_assert(std::is_unsigned_v,

295 "Only unsigned integral types are allowed.");

297}

298

299

300

301

302

304 static_assert(std::is_unsigned_v,

305 "Only unsigned integral types are allowed.");

307}

308

309

310

311

312

313

314

316 static_assert(std::is_unsigned_v,

317 "Only unsigned integral types are allowed.");

318 int Width = 0;

319 while (Value > 0) {

321 ++Width;

322 }

323 return Width;

324}

325

326

327

328

329

331 static_assert(std::is_unsigned_v,

332 "Only unsigned integral types are allowed.");

334 return 0;

336}

337

338

339

340

341

342

343

344

346 static_assert(std::is_unsigned_v,

347 "Only unsigned integral types are allowed.");

349 return 1;

351}

352

353

354

355

356

357

358

359

361 static_assert(std::is_unsigned_v,

362 "Only unsigned integral types are allowed.");

364 return 1;

366}

367

368template <typename T, typename = std::enable_if_t<std::is_unsigned_v>>

369[[nodiscard]] constexpr T rotl(T V, int R) {

370 constexpr unsigned N = std::numeric_limits::digits;

371

372 static_assert(has_single_bit(N), "& (N - 1) is only valid for powers of two");

373 R = R & (N - 1);

374

375 if (R == 0)

376 return V;

377

378 return (V << R) | (V >> (N - R));

379}

380

381template <typename T, typename = std::enable_if_t<std::is_unsigned_v>>

382[[nodiscard]] constexpr T rotr(T V, int R) {

383 constexpr unsigned N = std::numeric_limits::digits;

384

385 static_assert(has_single_bit(N), "& (N - 1) is only valid for powers of two");

386 R = R & (N - 1);

387

388 if (R == 0)

389 return V;

390

391 return (V >> R) | (V << (N - R));

392}

393

394}

395

396#endif

LLVM Value Representation.

This is an optimization pass for GlobalISel generic memory operations.

constexpr T rotr(T V, int R)

Definition bit.h:382

constexpr T bit_ceil_constexpr(T Value)

Returns the smallest integral power of two no smaller than Value if Value is nonzero.

Definition bit.h:360

int countr_one(T Value)

Count the number of ones from the least significant bit to the first zero bit.

Definition bit.h:293

constexpr T byteswap(T V) noexcept

Reverses the bytes in the given integer value V.

Definition bit.h:102

int bit_width(T Value)

Returns the number of bits needed to represent Value if Value is nonzero.

Definition bit.h:303

T bit_ceil(T Value)

Returns the smallest integral power of two no smaller than Value if Value is nonzero.

Definition bit.h:345

constexpr int popcount(T Value) noexcept

Count the number of set bits in a value.

Definition bit.h:154

int countr_zero(T Val)

Count number of 0's from the least significant bit to the most stopping at the first 1.

Definition bit.h:202

constexpr bool has_single_bit(T Value) noexcept

Definition bit.h:147

int countl_zero(T Val)

Count number of 0's from the most significant bit to the least stopping at the first 1.

Definition bit.h:236

int countl_one(T Value)

Count the number of ones from the most significant bit to the first zero bit.

Definition bit.h:280

To bit_cast(const From &from) noexcept

Definition bit.h:90

constexpr int countr_zero_constexpr(T Val)

Count number of 0's from the least significant bit to the most stopping at the first 1.

Definition bit.h:188

endianness

Definition bit.h:71

@ native

Definition bit.h:77

@ little

Definition bit.h:73

T bit_floor(T Value)

Returns the largest integral power of two no greater than Value if Value is nonzero.

Definition bit.h:330

constexpr int bit_width_constexpr(T Value)

Returns the number of bits needed to represent Value if Value is nonzero.

Definition bit.h:315

constexpr T rotl(T V, int R)

Definition bit.h:369