src/liblzma/common/bsr.h

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       bsr.h
   4 /// \brief      Bit scan reverse
   5 //
   6 //  Author:     Lasse Collin
   7 //
   8 //  This file has been put into the public domain.
   9 //  You can do whatever you want with this file.
  10 //
  11 ///////////////////////////////////////////////////////////////////////////////
  12
  13 #ifndef LZMA_BSR_H
  14 #define LZMA_BSR_H
  15
  16 // NOTE: Both input and output variables for lzma_bsr must be uint32_t.
  17
  18 #if defined(__GNUC__) && (defined (HAVE_ASM_X86) || defined(HAVE_ASM_X86_64))
  19 #       define lzma_bsr(dest, n) \
  20                 __asm__("bsrl %1, %0" : "=r" (dest) : "rm" (n))
  21
  22 #else
  23 #       define lzma_bsr(dest, n) dest = lzma_bsr_helper(n)
  24
  25 static inline uint32_t
  26 lzma_bsr_helper(uint32_t n)
  27 {
  28         assert(n != 0);
  29
  30         uint32_t i = 31;
  31
  32         if ((n & UINT32_C(0xFFFF0000)) == 0) {
  33                 n <<= 16;
  34                 i = 15;
  35         }
  36
  37         if ((n & UINT32_C(0xFF000000)) == 0) {
  38                 n <<= 8;
  39                 i -= 8;
  40         }
  41
  42         if ((n & UINT32_C(0xF0000000)) == 0) {
  43                 n <<= 4;
  44                 i -= 4;
  45         }
  46
  47         if ((n & UINT32_C(0xC0000000)) == 0) {
  48                 n <<= 2;
  49                 i -= 2;
  50         }
  51
  52         if ((n & UINT32_C(0x80000000)) == 0)
  53                 --i;
  54
  55         return i;
  56 }
  57
  58 #endif
  59
  60 #endif