rrbits.h

// 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