module Main where
import Data.Bits
import Data.Array.Unboxed
import Data.Int
import Data.Word
--import Foreign.C.Types (CUInt)
import System

--foreign import ccall "ones32c" ones32' :: CUInt -> CUInt

--ones32c :: Word -> Int
--ones32c = fromIntegral . ones32' . fromIntegral

ones32h :: Word -> Int 
ones32h x = fromIntegral . step6 . step5 . step4 . step3 . step2 . step1 $ x
  where 
    step1 x = x - (x `shiftR` 1) .&.  0x55555555
    step2 x = (((x `shiftR` 2) .&. 0x33333333) + (x .&. 0x33333333))
    step3 x = (((x `shiftR` 4) + x) .&. 0x0f0f0f0f)
    step4 x = x + (x `shiftR` 8)
    step5 x = x + (x `shiftR` 16)
    step6 x = x .&. 0x0000003f

{-
unsigned int
ones32c(register unsigned int x)
{
        /* 32-bit recursive reduction using SWAR...
	   but first step is mapping 2-bit values
	   into sum of 2 1-bit values in sneaky way
	*/
        x -= ((x >> 1) & 0x55555555);
        x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
        x = (((x >> 4) + x) & 0x0f0f0f0f);
        x += (x >> 8);
        x += (x >> 16);
        return(x & 0x0000003f);
}
-}

countBits :: Int -> Word -> Int
countBits a w 
    | w == 0 = a
    | otherwise = countBits 
                    (a + (fromIntegral $ bitsTable!(fromIntegral $ w .&. 0xFF)))  
                    (w `shiftR` 8)

countBits32 :: Word -> Int
countBits32 w = 
     (fromIntegral $ bitsTable!(fromIntegral $ w .&. 0xFF))
     + (fromIntegral $ bitsTable!(fromIntegral $ (w `shiftR` 8) .&. 0xFF))
     + (fromIntegral $ bitsTable!(fromIntegral $ (w `shiftR` 16) .&. 0xFF))
     + (fromIntegral $ bitsTable!(fromIntegral $ (w `shiftR` 24) .&. 0xFF))

bitsTable :: UArray Word8 Int8
bitsTable = listArray (0,255) [bitcount' 0 i | i <- [0..255]]

bitcount' :: Int8 -> Word -> Int8
bitcount' a 0 = a
bitcount' a x = bitcount' (a + 1) (x .&. (x-1))

bitcount :: Int -> Word -> Int
bitcount a 0 = a
bitcount a x = bitcount (a + 1) (x .&. (x-1))

run f l =
    do print $ maximum $ map (f . fromIntegral) l
      
main =
    do [lo,hi,which] <- getArgs
       let l = [(read lo) .. (read hi)]
       case which of
         --"c" -> run ones32c l
         "ones32" -> run ones32h l
         "table" -> run (countBits 0) l
         "table32" -> run countBits32 l
         "kern" -> run (bitcount 0) l