\section{Distance}

\begin{code}
{-# LANGUAGE MagicHash   #-}
{-# LANGUAGE StrictData  #-}
{-# LANGUAGE Trustworthy #-}
module Network.Tox.DHT.Distance where

import           Control.Applicative       ((<$>))
import           Control.Arrow             (first)
import           Data.Bits                 (xor)
import           Data.Monoid               (Monoid, mappend, mempty)
import           Data.Semigroup            (Semigroup, (<>))
import           GHC.Exts                  (Int (I#))
import           GHC.Integer.Logarithms    (integerLog2#)
import           Network.Tox.Crypto.Key    (PublicKey)
import qualified Network.Tox.Crypto.Key    as Key (keyToInteger)
import           Numeric                   (readHex, showHex)
import           Test.QuickCheck.Arbitrary (Arbitrary, arbitrary)


{-------------------------------------------------------------------------------
 -
 - :: Implementation.
 -
 ------------------------------------------------------------------------------}

\end{code}

A Distance is a positive integer.  Its human-readable representation is a
base-16 number.  Distance (type) is an
\href{https://en.wikipedia.org/wiki/Ordered_semigroup}{ordered monoid} with the
associative binary operator \texttt{+} and the identity element \texttt{0}.

\begin{code}

newtype Distance = Distance Integer
  deriving (Distance -> Distance -> Bool
(Distance -> Distance -> Bool)
-> (Distance -> Distance -> Bool) -> Eq Distance
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Distance -> Distance -> Bool
$c/= :: Distance -> Distance -> Bool
== :: Distance -> Distance -> Bool
$c== :: Distance -> Distance -> Bool
Eq, Eq Distance
Eq Distance
-> (Distance -> Distance -> Ordering)
-> (Distance -> Distance -> Bool)
-> (Distance -> Distance -> Bool)
-> (Distance -> Distance -> Bool)
-> (Distance -> Distance -> Bool)
-> (Distance -> Distance -> Distance)
-> (Distance -> Distance -> Distance)
-> Ord Distance
Distance -> Distance -> Bool
Distance -> Distance -> Ordering
Distance -> Distance -> Distance
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: Distance -> Distance -> Distance
$cmin :: Distance -> Distance -> Distance
max :: Distance -> Distance -> Distance
$cmax :: Distance -> Distance -> Distance
>= :: Distance -> Distance -> Bool
$c>= :: Distance -> Distance -> Bool
> :: Distance -> Distance -> Bool
$c> :: Distance -> Distance -> Bool
<= :: Distance -> Distance -> Bool
$c<= :: Distance -> Distance -> Bool
< :: Distance -> Distance -> Bool
$c< :: Distance -> Distance -> Bool
compare :: Distance -> Distance -> Ordering
$ccompare :: Distance -> Distance -> Ordering
$cp1Ord :: Eq Distance
Ord)


instance Semigroup Distance where
  (Distance Integer
x) <> :: Distance -> Distance -> Distance
<> (Distance Integer
y) = Integer -> Distance
Distance (Integer
x Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
y)

instance Monoid Distance where
  mempty :: Distance
mempty = Integer -> Distance
Distance Integer
0
  mappend :: Distance -> Distance -> Distance
mappend (Distance Integer
x) (Distance Integer
y) = Integer -> Distance
Distance (Integer
x Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
y)


instance Show Distance where
  show :: Distance -> String
show (Distance Integer
distance) = Integer -> ShowS
forall a. (Integral a, Show a) => a -> ShowS
showHex Integer
distance String
""

instance Read Distance where
  readsPrec :: Int -> ReadS Distance
readsPrec Int
_ String
string = ((Integer, String) -> (Distance, String))
-> [(Integer, String)] -> [(Distance, String)]
forall a b. (a -> b) -> [a] -> [b]
map ((Integer -> Distance) -> (Integer, String) -> (Distance, String)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first Integer -> Distance
Distance) ([(Integer, String)] -> [(Distance, String)])
-> [(Integer, String)] -> [(Distance, String)]
forall a b. (a -> b) -> a -> b
$ ReadS Integer
forall a. (Eq a, Num a) => ReadS a
readHex String
string


log2 :: Distance -> Maybe Int
log2 :: Distance -> Maybe Int
log2 (Distance Integer
0) = Maybe Int
forall a. Maybe a
Nothing
log2 (Distance Integer
x) = Int -> Maybe Int
forall a. a -> Maybe a
Just (Int -> Maybe Int) -> Int -> Maybe Int
forall a b. (a -> b) -> a -> b
$ Int# -> Int
I# (Integer -> Int#
integerLog2# Integer
x)


\end{code}

The DHT uses a
\href{https://en.wikipedia.org/wiki/Metric_(mathematics)}{metric} to determine
the distance between two nodes.  The Distance type is the co-domain of this
metric. The metric currently used by the Tox DHT is the \texttt{XOR} of the
nodes' public keys: \texttt{distance(x, y) = x XOR y}.  For this computation,
public keys are interpreted as Big Endian integers (see \href{#key-1}{Crypto
Numbers}).

When we speak of a "close node", we mean that its Distance to the node under
consideration is small compared to the Distance to other nodes.

\begin{code}

xorDistance :: PublicKey -> PublicKey -> Distance
xorDistance :: PublicKey -> PublicKey -> Distance
xorDistance PublicKey
a PublicKey
b =
  Integer -> Distance
Distance (Integer -> Distance) -> Integer -> Distance
forall a b. (a -> b) -> a -> b
$ PublicKey -> Integer
forall a. IsEncoding a => Key a -> Integer
Key.keyToInteger PublicKey
a Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
`xor` PublicKey -> Integer
forall a. IsEncoding a => Key a -> Integer
Key.keyToInteger PublicKey
b

-- | rebaseDistance a b (xorDistance a c) == xorDistance b c
rebaseDistance :: PublicKey -> PublicKey -> Distance -> Distance
rebaseDistance :: PublicKey -> PublicKey -> Distance -> Distance
rebaseDistance PublicKey
a PublicKey
b (Distance Integer
d) =
  Integer -> Distance
Distance (Integer -> Distance) -> Integer -> Distance
forall a b. (a -> b) -> a -> b
$ Integer
d Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
`xor` PublicKey -> Integer
forall a. IsEncoding a => Key a -> Integer
Key.keyToInteger PublicKey
a Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
`xor` PublicKey -> Integer
forall a. IsEncoding a => Key a -> Integer
Key.keyToInteger PublicKey
b

{-------------------------------------------------------------------------------
 -
 - :: Tests.
 -
 ------------------------------------------------------------------------------}


instance Arbitrary Distance where
  arbitrary :: Gen Distance
arbitrary = Integer -> Distance
Distance (Integer -> Distance)
-> (Integer -> Integer) -> Integer -> Distance
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Integer
forall a. Num a => a -> a
abs (Integer -> Distance) -> Gen Integer -> Gen Distance
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Gen Integer
forall a. Arbitrary a => Gen a
arbitrary
\end{code}

An implementation is not required to provide a Distance type, so it has no
specified binary representation.  For example, instead of computing a distance
and comparing it against another distance, the implementation can choose to
implement Distance as a pair of public keys and define an ordering on Distance
without computing the complete integral value.  This works, because as soon as
an ordering decision can be made in the most significant bits, further bits
won't influence that decision.

\input{test/Network/Tox/DHT/DistanceSpec.lhs}