Skip to content

Instantly share code, notes, and snippets.

Created September 8, 2015 21:30
Show Gist options
  • Save anonymous/bed18ab719b652ae1226 to your computer and use it in GitHub Desktop.
Save anonymous/bed18ab719b652ae1226 to your computer and use it in GitHub Desktop.
// Copyright 2008-2015 RAD Game Tools
#ifndef RADRR_BITSH
#define RADRR_BITSH
#include "radtypes.h"
RADDEFSTART
//===================================================================================
// Bit manipulation tools
// Count leading zeros / count trailing zeros. All of these are undefined for input
// arguments of 0. On x86, BSF/BSR have undefined results for x=0; on ARM and PPC which
// provide "count leading zeros" but not "count trailing zeros", it's much easier to
// give a version of CTZ that is correct only for x != 0. These functions are interesting
// because they're fast, so try to be fast.
#if defined(__GNUC__) || defined(__clang__)
// GCC-esque compilers just provide these built-ins everywhere.
static RADINLINE U32 rrClz32(U32 val) { return __builtin_clz(val); }
static RADINLINE U32 rrClz64(U64 val) { return __builtin_clzll(val); }
#ifndef __SNC__
static RADINLINE U32 rrCtz32(U32 val) { return __builtin_ctz(val); }
static RADINLINE U32 rrCtz64(U64 val) { return __builtin_ctzll(val); }
#else
// Strategy for CTZ: "x & -x" isolates least-significant set bit, then use
// CLZ to infer trailing zero count.
static RADINLINE U32 rrCtz32(U32 val) { return 31 - rrClz32(val & (0u - val)); }
static RADINLINE U32 rrCtz64(U64 val) { return 63 - rrClz64(val & (0ull - val)); }
#endif
#elif defined(_MSC_VER)
#if defined(__RADARM__)
RADDEFEND
#include <intrin.h>
RADDEFSTART
static RADINLINE U32 rrClz32(U32 val) { return _arm_clz(val); }
static RADINLINE U32 rrClz64(U64 val) { U32 hi = (U32) (val >> 32); return hi ? rrClz32(hi) : 32 + rrClz32((U32) val); }
// Strategy for CTZ: "x & -x" isolates least-significant set bit, then use
// CLZ to infer trailing zero count.
static RADINLINE U32 rrCtz32(U32 val) { return 31 - rrClz32(val & (0u - val)); }
static RADINLINE U32 rrCtz64(U64 val) { return 63 - rrClz64(val & (0ull - val)); }
#elif defined(__RADPPC__)
RADDEFEND
#include <PPCIntrinsics.h>
RADDEFSTART
static RADINLINE U32 rrClz32(U32 val) { return _CountLeadingZeros(val); }
static RADINLINE U32 rrClz64(U64 val) { return _CountLeadingZeros64(val); }
// Strategy for CTZ: "x & -x" isolates least-significant set bit, then use
// CLZ to infer trailing zero count.
static RADINLINE U32 rrCtz32(U32 val) { return 31 - rrClz32(val & (0u - val)); }
static RADINLINE U32 rrCtz64(U64 val) { return 63 - rrClz64(val & (0ull - val)); }
#elif defined(__RADX64__)
RADDEFEND
#include <intrin.h>
RADDEFSTART
static RADINLINE U32 rrClz32(U32 val) { unsigned long idx; _BitScanReverse(&idx, val); return 31 - idx; }
static RADINLINE U32 rrClz64(U64 val) { unsigned long idx; _BitScanReverse64(&idx, val); return 63 - idx; }
static RADINLINE U32 rrCtz32(U32 val) { unsigned long idx; _BitScanForward(&idx, val); return idx; }
static RADINLINE U32 rrCtz64(U64 val) { unsigned long idx; _BitScanForward64(&idx, val); return idx; }
#elif defined(__RADX86__)
RADDEFEND
#include <intrin.h>
RADDEFSTART
static RADINLINE U32 rrClz32(U32 val) { unsigned long idx; _BitScanReverse(&idx, val); return 31 - idx; }
static RADINLINE U32 rrClz64(U64 val) { U32 hi = (U32) (val >> 32); return hi ? rrClz32(hi) : 32 + rrClz32((U32) val); }
static RADINLINE U32 rrCtz32(U32 val) { unsigned long idx; _BitScanForward(&idx, val); return idx; }
static RADINLINE U32 rrCtz64(U64 val) { U32 lo = (U32) val; return lo ? rrCtz32(lo) : 32 + rrCtz32((U32) (val >> 32)); }
#else
#error Unknown MSVC target
#endif
#elif defined(__RADPSP2__)
static RADINLINE U32 rrClz32(U32 val) { return __builtin_clz(val); }
static RADINLINE U32 rrClz64(U64 val) { U32 hi = (U32) (val >> 32); return hi ? rrClz32(hi) : 32 + rrClz32((U32) val); }
static RADINLINE U32 rrCtz32(U32 val) { return 31 - rrClz32(val & (0u - val)); }
static RADINLINE U32 rrCtz64(U64 val) { return 63 - rrClz64(val & (0ull - val)); }
#else
#error Implement rrBits for this target
#endif
RADDEFEND
#endif // RADRR_BITSH
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment