#![feature(asm)]

trait FindFirstBit {
    fn ffs(&self) -> u8;
}

#[inline(always)]
fn supports_asm() -> bool {
    cfg!(any(
        target_arch = "x86",
        target_arch = "x86_64"
    ))
}

macro_rules! impl_ffs {
    ($type:ty, $ltype:ty, $extension:expr) => (
        impl FindFirstBit for $type {
            fn ffs(&self) -> u8 {
                use std::mem::size_of;
                unsafe {
                    if supports_asm() {
                        let result: $type;
                        asm!("bsf $1, $0" : "=r"(result) : "0"(*self));
                        result as u8
                    } else if $extension {
                        const BITS: $type = (size_of::<$ltype>() << 3) as $type;
                        if *self <= !(1 << BITS) {
                            (*self as $ltype).ffs()
                        } else {
                            let lower_bits = ((*self >> (BITS / 2)) as $ltype).ffs();
                            ((BITS / 2) + (lower_bits as $type)) as u8
                        }
                    } else {
                        const BIT_TABLE: [u8; 256] = [
                            0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
                            6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
                            7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
                            7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
                            8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
                            8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
                            8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
                            8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
                        ];
                        let bytes = match *self {
                            n if n <= 0xff => 0,
                            n if n <= 0xffff => 8,
                            n if n <= 0xffffff => 16,
                            _ => 24
                        };
                        *BIT_TABLE.as_ptr().offset((*self >> bytes) as isize) + bytes
                    }
                }
            }
        }
    );
}

impl_ffs!(u32, u32, false);
impl_ffs!(u64, u32, true);
impl_ffs!(u128, u64, true);