{-# LANGUAGE CPP                       #-}
{-# LANGUAGE ExistentialQuantification #-}
{-# LANGUAGE TypeFamilies              #-}
{-# LANGUAGE RecordWildCards           #-}
{-# LANGUAGE FlexibleContexts          #-}
{-# LANGUAGE FlexibleInstances         #-}
{-# LANGUAGE MultiParamTypeClasses     #-}
{-# LANGUAGE ScopedTypeVariables       #-}
{-# LANGUAGE ConstraintKinds           #-}

-- | This module exposes the low-level internal details of
-- cryptographic hashes. Do not import this module unless you want to
-- implement a new hash or give a new implementation of an existing
-- hash.
module Raaz.Hash.Internal
       ( -- * Cryptographic hashes and their implementations.
         -- $hashdoc$
         Hash(..)
       , hash, hashFile, hashSource
         -- ** Computing hashes using non-standard implementations.
       , hash', hashFile', hashSource'
         -- * Hash implementations.
       , HashI(..), SomeHashI(..), HashM
         -- ** Implementation of truncated hashes.
       , truncatedI
         -- * Memory used by most hashes.
       , HashMemory(..), extractLength, updateLength
       -- * Some low level functions.
       , completeHashing
       ) where


#if !MIN_VERSION_base(4,8,0)
import           Control.Applicative
#endif

import qualified Data.ByteString      as B
import qualified Data.ByteString.Lazy as L
import           Data.Monoid
import           Data.Word
import           Foreign.Storable
import           System.IO
import           System.IO.Unsafe     (unsafePerformIO)

import Raaz.Core

-- $hashdoc$
--
-- Each cryptographic hash is a distinct type and are instances of a
-- the type class `Hash`. The standard idiom that we follow for hash
-- implementations are the following:
--
-- [`HashI`:] This type captures implementations of a the hash. This
-- type is parameterised over the memory element used by the
-- implementation.
--
-- [`SomeHashI`:] This type is the existentially quantified version of
-- `HashI` over its memory element. Thus it exposes only the interface
-- and not the internals of the implementation. The `Implementation`
-- associated type of a hash is the type `SomeHashI`
--
-- To support a new hash, a developer needs to:
--
-- 1. Define a new type which captures the result of hashing. This
--    type should be an instance of the class `Hash`.
--
-- 2. Define an implementation, i.e. a value of the type `SomeHashI`.
--
-- 3. Define a recommended implementation, i.e. an instance of the
--    type class `Raaz.Core.Primitives.Recommendation`

-------------------- Hash Implementations --------------------------

-- | The Hash implementation. Implementations should ensure the
-- following.
--
-- 1. The action @compress impl ptr blks@ should only read till the
-- @blks@ offset starting at ptr and never write any data.
--
-- 2. The action @padFinal impl ptr byts@ should touch at most
-- @⌈byts/blocksize⌉ + padBlocks@ blocks starting at ptr. It should
-- not write anything till the @byts@ offset but may write stuff
-- beyond that.
--
-- An easy to remember this rule is to remember that computing hash of
-- a payload should not modify the payload.
--
data HashI h m = HashI
  { HashI h m -> String
hashIName           :: String
  , HashI h m -> String
hashIDescription    :: String
  , HashI h m -> Pointer -> BLOCKS h -> MT m ()
compress       :: Pointer -> BLOCKS h  -> MT m ()
                      -- ^ compress the blocks,
  , HashI h m -> Pointer -> BYTES Int -> MT m ()
compressFinal  :: Pointer -> BYTES Int -> MT m ()
                      -- ^ pad and process the final bytes,
  , HashI h m -> Alignment
compressStartAlignment :: Alignment
  }

instance BlockAlgorithm (HashI h m) where
  bufferStartAlignment :: HashI h m -> Alignment
bufferStartAlignment = HashI h m -> Alignment
forall h m. HashI h m -> Alignment
compressStartAlignment

-- | The constraints that a memory used by a hash implementation
-- should satisfy.
type HashM h m = (Initialisable m (), Extractable m h, Primitive h)

-- | Some implementation of a given hash. The existentially
-- quantification allows us freedom to choose the best memory type
-- suitable for each implementations.
data SomeHashI h = forall m . HashM h m =>
     SomeHashI (HashI h m)

instance Describable (HashI h m) where
  name :: HashI h m -> String
name        = HashI h m -> String
forall h m. HashI h m -> String
hashIName
  description :: HashI h m -> String
description = HashI h m -> String
forall h m. HashI h m -> String
hashIDescription


instance Describable (SomeHashI h) where
  name :: SomeHashI h -> String
name         (SomeHashI HashI h m
hI) = HashI h m -> String
forall d. Describable d => d -> String
name HashI h m
hI
  description :: SomeHashI h -> String
description  (SomeHashI HashI h m
hI) = HashI h m -> String
forall d. Describable d => d -> String
description HashI h m
hI

instance BlockAlgorithm (SomeHashI h) where
  bufferStartAlignment :: SomeHashI h -> Alignment
bufferStartAlignment (SomeHashI HashI h m
imp) = HashI h m -> Alignment
forall a. BlockAlgorithm a => a -> Alignment
bufferStartAlignment HashI h m
imp

-- | Certain hashes are essentially bit-truncated versions of other
-- hashes. For example, SHA224 is obtained from SHA256 by dropping the
-- last 32-bits. This combinator can be used build an implementation
-- of truncated hash from the implementation of its parent hash.
truncatedI :: (BLOCKS htrunc -> BLOCKS h)
           -> (mtrunc        -> m)
           -> HashI h m -> HashI htrunc mtrunc
truncatedI :: (BLOCKS htrunc -> BLOCKS h)
-> (mtrunc -> m) -> HashI h m -> HashI htrunc mtrunc
truncatedI BLOCKS htrunc -> BLOCKS h
coerce mtrunc -> m
unMtrunc (HashI{String
Alignment
Pointer -> BYTES Int -> MT m ()
Pointer -> BLOCKS h -> MT m ()
compressStartAlignment :: Alignment
compressFinal :: Pointer -> BYTES Int -> MT m ()
compress :: Pointer -> BLOCKS h -> MT m ()
hashIDescription :: String
hashIName :: String
compressStartAlignment :: forall h m. HashI h m -> Alignment
compressFinal :: forall h m. HashI h m -> Pointer -> BYTES Int -> MT m ()
compress :: forall h m. HashI h m -> Pointer -> BLOCKS h -> MT m ()
hashIDescription :: forall h m. HashI h m -> String
hashIName :: forall h m. HashI h m -> String
..})
  = HashI :: forall h m.
String
-> String
-> (Pointer -> BLOCKS h -> MT m ())
-> (Pointer -> BYTES Int -> MT m ())
-> Alignment
-> HashI h m
HashI { hashIName :: String
hashIName        = String
hashIName
          , hashIDescription :: String
hashIDescription = String
hashIDescription
          , compress :: Pointer -> BLOCKS htrunc -> MT mtrunc ()
compress         = Pointer -> BLOCKS htrunc -> MT mtrunc ()
comp
          , compressFinal :: Pointer -> BYTES Int -> MT mtrunc ()
compressFinal    = Pointer -> BYTES Int -> MT mtrunc ()
compF
          , compressStartAlignment :: Alignment
compressStartAlignment = Alignment
compressStartAlignment
          }
  where comp :: Pointer -> BLOCKS htrunc -> MT mtrunc ()
comp  Pointer
ptr = (mtrunc -> m) -> MT m () -> MT mtrunc ()
forall (mT :: * -> * -> *) mem submem a.
MemoryThread mT =>
(mem -> submem) -> mT submem a -> mT mem a
onSubMemory mtrunc -> m
unMtrunc (MT m () -> MT mtrunc ())
-> (BLOCKS htrunc -> MT m ()) -> BLOCKS htrunc -> MT mtrunc ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Pointer -> BLOCKS h -> MT m ()
compress Pointer
ptr (BLOCKS h -> MT m ())
-> (BLOCKS htrunc -> BLOCKS h) -> BLOCKS htrunc -> MT m ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. BLOCKS htrunc -> BLOCKS h
coerce
        compF :: Pointer -> BYTES Int -> MT mtrunc ()
compF Pointer
ptr = (mtrunc -> m) -> MT m () -> MT mtrunc ()
forall (mT :: * -> * -> *) mem submem a.
MemoryThread mT =>
(mem -> submem) -> mT submem a -> mT mem a
onSubMemory mtrunc -> m
unMtrunc (MT m () -> MT mtrunc ())
-> (BYTES Int -> MT m ()) -> BYTES Int -> MT mtrunc ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Pointer -> BYTES Int -> MT m ()
compressFinal Pointer
ptr

---------------------- The Hash class ---------------------------------

-- | Type class capturing a cryptographic hash.
class ( Primitive h
      , EndianStore h
      , Encodable h
      , Eq h
      , Implementation h ~ SomeHashI h
      ) => Hash h where
  -- | Cryptographic hashes can be computed for messages that are not
  -- a multiple of the block size. This combinator computes the
  -- maximum size of padding that can be attached to a message.
  additionalPadBlocks :: h -> BLOCKS h

---------------------- Helper combinators --------------------------

-- | Compute the hash of a pure byte source like, `B.ByteString`.
hash :: ( Hash h, Recommendation h, PureByteSource src )
     => src  -- ^ Message
     -> h
hash :: src -> h
hash = IO h -> h
forall a. IO a -> a
unsafePerformIO (IO h -> h) -> (src -> IO h) -> src -> h
forall b c a. (b -> c) -> (a -> b) -> a -> c
. src -> IO h
forall h src.
(Hash h, Recommendation h, ByteSource src) =>
src -> IO h
hashSource
{-# INLINEABLE hash #-}
{-# SPECIALIZE hash :: (Hash h, Recommendation h) => B.ByteString -> h #-}
{-# SPECIALIZE hash :: (Hash h, Recommendation h) => L.ByteString -> h #-}

-- | Compute the hash of file.
hashFile :: ( Hash h, Recommendation h)
         => FilePath  -- ^ File to be hashed
         -> IO h
hashFile :: String -> IO h
hashFile String
fileName = String -> IOMode -> (Handle -> IO h) -> IO h
forall r. String -> IOMode -> (Handle -> IO r) -> IO r
withBinaryFile String
fileName IOMode
ReadMode Handle -> IO h
forall h src.
(Hash h, Recommendation h, ByteSource src) =>
src -> IO h
hashSource
{-# INLINEABLE hashFile #-}


-- | Compute the hash of a generic byte source.
hashSource :: ( Hash h, Recommendation h, ByteSource src )
           => src  -- ^ Message
           -> IO h
hashSource :: src -> IO h
hashSource = h -> src -> IO h
forall h src.
(Hash h, Recommendation h, ByteSource src) =>
h -> src -> IO h
go h
forall a. HasCallStack => a
undefined
  where go :: (Hash h, Recommendation h, ByteSource src) => h -> src -> IO h
        go :: h -> src -> IO h
go h
h = Implementation h -> src -> IO h
forall h src.
(Hash h, ByteSource src) =>
Implementation h -> src -> IO h
hashSource' (Implementation h -> src -> IO h)
-> Implementation h -> src -> IO h
forall a b. (a -> b) -> a -> b
$ h -> Implementation h
forall p. Recommendation p => p -> Implementation p
recommended h
h

{-# INLINEABLE hashSource #-}
{-# SPECIALIZE hashSource :: (Hash h, Recommendation h) => Handle -> IO h #-}


-- | Similar to `hash` but the user can specify the implementation to
-- use.
hash' :: ( PureByteSource src
         , Hash h
         )
      => Implementation h -- ^ Implementation
      -> src              -- ^ the message as a byte source.
      -> h
hash' :: Implementation h -> src -> h
hash' Implementation h
imp = IO h -> h
forall a. IO a -> a
unsafePerformIO (IO h -> h) -> (src -> IO h) -> src -> h
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Implementation h -> src -> IO h
forall h src.
(Hash h, ByteSource src) =>
Implementation h -> src -> IO h
hashSource' Implementation h
imp
{-# INLINEABLE hash' #-}

-- TODO: For bytestrings (strict and lazy) we can do better. We can
-- avoid copying as the bytestring exposes the underlying
-- pointer. However, there is a huge cost if the underlying pointer
-- does not start at the machine alignment boundary. The idea
-- therefore is to process strict bytestring is multiples of blocks
-- directly if the starting pointer is aligned.
--
-- More details in the bug report #256.
--
-- https://github.com/raaz-crypto/raaz/issues/256
--

-- | Similar to hashFile' but the user can specify the implementation
-- to use.
hashFile' :: Hash h
          => Implementation h  -- ^ Implementation
          -> FilePath          -- ^ File to be hashed
          -> IO h
hashFile' :: Implementation h -> String -> IO h
hashFile' Implementation h
imp String
fileName = String -> IOMode -> (Handle -> IO h) -> IO h
forall r. String -> IOMode -> (Handle -> IO r) -> IO r
withBinaryFile String
fileName IOMode
ReadMode ((Handle -> IO h) -> IO h) -> (Handle -> IO h) -> IO h
forall a b. (a -> b) -> a -> b
$ Implementation h -> Handle -> IO h
forall h src.
(Hash h, ByteSource src) =>
Implementation h -> src -> IO h
hashSource' Implementation h
imp
{-# INLINEABLE hashFile' #-}


-- | Similar to @hashSource@ but the user can specify the
-- implementation to use.
hashSource' :: (Hash h, ByteSource src)
            => Implementation h
            -> src
            -> IO h
hashSource' :: Implementation h -> src -> IO h
hashSource' (SomeHashI impl) src
src =
  MT m h -> IO h
forall (mT :: * -> * -> *) mem a.
(MemoryThread mT, Memory mem) =>
mT mem a -> IO a
insecurely (MT m h -> IO h) -> MT m h -> IO h
forall a b. (a -> b) -> a -> b
$ () -> MT m ()
forall m v. Initialisable m v => v -> MT m ()
initialise () MT m () -> MT m h -> MT m h
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> HashI h m -> src -> MT m h
forall h src m.
(Hash h, ByteSource src, HashM h m) =>
HashI h m -> src -> MT m h
completeHashing HashI h m
impl src
src


-- | Gives a memory action that completes the hashing procedure with
-- the rest of the source. Useful to compute the hash of a source with
-- some prefix (like in the HMAC procedure).
completeHashing :: (Hash h, ByteSource src, HashM h m)
                => HashI h m
                -> src
                -> MT m h
completeHashing :: HashI h m -> src -> MT m h
completeHashing imp :: HashI h m
imp@(HashI{String
Alignment
Pointer -> BYTES Int -> MT m ()
Pointer -> BLOCKS h -> MT m ()
compressStartAlignment :: Alignment
compressFinal :: Pointer -> BYTES Int -> MT m ()
compress :: Pointer -> BLOCKS h -> MT m ()
hashIDescription :: String
hashIName :: String
compressStartAlignment :: forall h m. HashI h m -> Alignment
compressFinal :: forall h m. HashI h m -> Pointer -> BYTES Int -> MT m ()
compress :: forall h m. HashI h m -> Pointer -> BLOCKS h -> MT m ()
hashIDescription :: forall h m. HashI h m -> String
hashIName :: forall h m. HashI h m -> String
..}) src
src =
  PointerAction (MT m) h h
allocate PointerAction (MT m) h h -> PointerAction (MT m) h h
forall a b. (a -> b) -> a -> b
$ \ Pointer
ptr -> let
    comp :: MT m ()
comp                = Pointer -> BLOCKS h -> MT m ()
compress Pointer
ptr BLOCKS h
bufSize
    finish :: BYTES Int -> MT m h
finish BYTES Int
bytes        = Pointer -> BYTES Int -> MT m ()
compressFinal Pointer
ptr BYTES Int
bytes MT m () -> MT m h -> MT m h
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> MT m h
forall m v. Extractable m v => MT m v
extract
    in MT m ()
-> (BYTES Int -> MT m h) -> src -> BLOCKS h -> Pointer -> MT m h
forall (m :: * -> *) chunkSize src a b.
(MonadIO m, LengthUnit chunkSize, ByteSource src) =>
m a -> (BYTES Int -> m b) -> src -> chunkSize -> Pointer -> m b
processChunks MT m ()
comp BYTES Int -> MT m h
finish src
src BLOCKS h
bufSize Pointer
ptr
  where bufSize :: BLOCKS h
bufSize             = BYTES Int -> BLOCKS h
forall src dest. (LengthUnit src, LengthUnit dest) => src -> dest
atLeast BYTES Int
l1Cache BLOCKS h -> BLOCKS h -> BLOCKS h
forall a. Semigroup a => a -> a -> a
<> Int -> BLOCKS h
forall a. Enum a => Int -> a
toEnum Int
1
        totalSize :: BLOCKS h
totalSize           = BLOCKS h
bufSize BLOCKS h -> BLOCKS h -> BLOCKS h
forall a. Semigroup a => a -> a -> a
<> h -> BLOCKS h
forall h. Hash h => h -> BLOCKS h
additionalPadBlocks h
forall a. HasCallStack => a
undefined
        allocate :: PointerAction (MT m) h h
allocate            = PointerAction IO h h -> PointerAction (MT m) h h
forall a b mem. PointerAction IO a b -> PointerAction (MT mem) a b
liftPointerAction (PointerAction IO h h -> PointerAction (MT m) h h)
-> PointerAction IO h h -> PointerAction (MT m) h h
forall a b. (a -> b) -> a -> b
$ Implementation h -> BLOCKS h -> PointerAction IO h h
forall prim b.
Primitive prim =>
Implementation prim -> BLOCKS prim -> (Pointer -> IO b) -> IO b
allocBufferFor (HashI h m -> SomeHashI h
forall h m. HashM h m => HashI h m -> SomeHashI h
SomeHashI HashI h m
imp) BLOCKS h
totalSize

----------------------- Hash memory ----------------------------------

-- | Computing cryptographic hashes usually involves chunking the
-- message into blocks and compressing one block at a time. Usually
-- this compression makes use of the hash of the previous block and
-- the length of the message seen so far to compressing the current
-- block. Most implementations therefore need to keep track of only
-- hash and the length of the message seen so. This memory can be used
-- in such situations.
data HashMemory h =
  HashMemory
  { HashMemory h -> MemoryCell h
hashCell          :: MemoryCell h
                         -- ^ Cell to store the hash
  , HashMemory h -> MemoryCell (BITS Word64)
messageLengthCell :: MemoryCell (BITS Word64)
                         -- ^ Cell to store the length
  }

instance Storable h => Memory (HashMemory h) where

  memoryAlloc :: Alloc (HashMemory h)
memoryAlloc     = MemoryCell h -> MemoryCell (BITS Word64) -> HashMemory h
forall h. MemoryCell h -> MemoryCell (BITS Word64) -> HashMemory h
HashMemory (MemoryCell h -> MemoryCell (BITS Word64) -> HashMemory h)
-> TwistRF AllocField (BYTES Int) (MemoryCell h)
-> TwistRF
     AllocField (BYTES Int) (MemoryCell (BITS Word64) -> HashMemory h)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> TwistRF AllocField (BYTES Int) (MemoryCell h)
forall m. Memory m => Alloc m
memoryAlloc TwistRF
  AllocField (BYTES Int) (MemoryCell (BITS Word64) -> HashMemory h)
-> TwistRF AllocField (BYTES Int) (MemoryCell (BITS Word64))
-> Alloc (HashMemory h)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> TwistRF AllocField (BYTES Int) (MemoryCell (BITS Word64))
forall m. Memory m => Alloc m
memoryAlloc

  unsafeToPointer :: HashMemory h -> Pointer
unsafeToPointer = MemoryCell h -> Pointer
forall m. Memory m => m -> Pointer
unsafeToPointer (MemoryCell h -> Pointer)
-> (HashMemory h -> MemoryCell h) -> HashMemory h -> Pointer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashMemory h -> MemoryCell h
forall h. HashMemory h -> MemoryCell h
hashCell

instance Storable h => Initialisable (HashMemory h) h where
  initialise :: h -> MT (HashMemory h) ()
initialise h
h = do
    (HashMemory h -> MemoryCell h)
-> MT (MemoryCell h) () -> MT (HashMemory h) ()
forall (mT :: * -> * -> *) mem submem a.
MemoryThread mT =>
(mem -> submem) -> mT submem a -> mT mem a
onSubMemory HashMemory h -> MemoryCell h
forall h. HashMemory h -> MemoryCell h
hashCell          (MT (MemoryCell h) () -> MT (HashMemory h) ())
-> MT (MemoryCell h) () -> MT (HashMemory h) ()
forall a b. (a -> b) -> a -> b
$ h -> MT (MemoryCell h) ()
forall m v. Initialisable m v => v -> MT m ()
initialise h
h
    (HashMemory h -> MemoryCell (BITS Word64))
-> MT (MemoryCell (BITS Word64)) () -> MT (HashMemory h) ()
forall (mT :: * -> * -> *) mem submem a.
MemoryThread mT =>
(mem -> submem) -> mT submem a -> mT mem a
onSubMemory HashMemory h -> MemoryCell (BITS Word64)
forall h. HashMemory h -> MemoryCell (BITS Word64)
messageLengthCell (MT (MemoryCell (BITS Word64)) () -> MT (HashMemory h) ())
-> MT (MemoryCell (BITS Word64)) () -> MT (HashMemory h) ()
forall a b. (a -> b) -> a -> b
$ BITS Word64 -> MT (MemoryCell (BITS Word64)) ()
forall m v. Initialisable m v => v -> MT m ()
initialise (BITS Word64
0 :: BITS Word64)

instance Storable h => Extractable (HashMemory h) h where
  extract :: MT (HashMemory h) h
extract = (HashMemory h -> MemoryCell h)
-> MT (MemoryCell h) h -> MT (HashMemory h) h
forall (mT :: * -> * -> *) mem submem a.
MemoryThread mT =>
(mem -> submem) -> mT submem a -> mT mem a
onSubMemory HashMemory h -> MemoryCell h
forall h. HashMemory h -> MemoryCell h
hashCell MT (MemoryCell h) h
forall m v. Extractable m v => MT m v
extract

-- | Extract the length of the message hashed so far.
extractLength :: MT (HashMemory h) (BITS Word64)
extractLength :: MT (HashMemory h) (BITS Word64)
extractLength = (HashMemory h -> MemoryCell (BITS Word64))
-> MT (MemoryCell (BITS Word64)) (BITS Word64)
-> MT (HashMemory h) (BITS Word64)
forall (mT :: * -> * -> *) mem submem a.
MemoryThread mT =>
(mem -> submem) -> mT submem a -> mT mem a
onSubMemory HashMemory h -> MemoryCell (BITS Word64)
forall h. HashMemory h -> MemoryCell (BITS Word64)
messageLengthCell MT (MemoryCell (BITS Word64)) (BITS Word64)
forall m v. Extractable m v => MT m v
extract
{-# INLINE extractLength #-}


-- | Update the message length by a given amount.
updateLength :: LengthUnit u => u -> MT (HashMemory h) ()
{-# INLINE updateLength #-}
updateLength :: u -> MT (HashMemory h) ()
updateLength u
u = (HashMemory h -> MemoryCell (BITS Word64))
-> MT (MemoryCell (BITS Word64)) () -> MT (HashMemory h) ()
forall (mT :: * -> * -> *) mem submem a.
MemoryThread mT =>
(mem -> submem) -> mT submem a -> mT mem a
onSubMemory HashMemory h -> MemoryCell (BITS Word64)
forall h. HashMemory h -> MemoryCell (BITS Word64)
messageLengthCell (MT (MemoryCell (BITS Word64)) () -> MT (HashMemory h) ())
-> MT (MemoryCell (BITS Word64)) () -> MT (HashMemory h) ()
forall a b. (a -> b) -> a -> b
$ (BITS Word64 -> BITS Word64) -> MT (MemoryCell (BITS Word64)) ()
forall mem a b (mT :: * -> * -> *).
(Initialisable mem a, Extractable mem b, MemoryThread mT) =>
(b -> a) -> mT mem ()
modify (BITS Word64
nBits BITS Word64 -> BITS Word64 -> BITS Word64
forall a. Num a => a -> a -> a
+)
  where nBits :: BITS Word64
        nBits :: BITS Word64
nBits =  u -> BITS Word64
forall u. LengthUnit u => u -> BITS Word64
inBits u
u