src/liblzma/common/bsr.h

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       bsr.h
   4 /// \brief      Bit scan reverse
   5 //
   6 //  This code has been put into the public domain.
   7 //
   8 //  This library is distributed in the hope that it will be useful,
   9 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  11 //
  12 ///////////////////////////////////////////////////////////////////////////////
  13
  14 #ifndef LZMA_BSR_H
  15 #define LZMA_BSR_H
  16
  17 // NOTE: Both input and output variables for lzma_bsr must be uint32_t.
  18
  19 #if defined(__GNUC__) && (defined (HAVE_ASM_X86) || defined(HAVE_ASM_X86_64))
  20 #       define lzma_bsr(dest, n) \
  21                 __asm__("bsrl %1, %0" : "=r" (dest) : "rm" (n))
  22
  23 #else
  24 #       define lzma_bsr(dest, n) dest = lzma_bsr_helper(n)
  25
  26 static inline uint32_t
  27 lzma_bsr_helper(uint32_t n)
  28 {
  29         assert(n != 0);
  30
  31         uint32_t i = 31;
  32
  33         if ((n & UINT32_C(0xFFFF0000)) == 0) {
  34                 n <<= 16;
  35                 i = 15;
  36         }
  37
  38         if ((n & UINT32_C(0xFF000000)) == 0) {
  39                 n <<= 8;
  40                 i -= 8;
  41         }
  42
  43         if ((n & UINT32_C(0xF0000000)) == 0) {
  44                 n <<= 4;
  45                 i -= 4;
  46         }
  47
  48         if ((n & UINT32_C(0xC0000000)) == 0) {
  49                 n <<= 2;
  50                 i -= 2;
  51         }
  52
  53         if ((n & UINT32_C(0x80000000)) == 0)
  54                 --i;
  55
  56         return i;
  57 }
  58
  59 #endif
  60
  61 #endif