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