Read / Write Haskell Integer in two's complement representation

6
votes

I need to read and write Integers in a way that is compatible with what Java does with it's BigInteger class:

Returns a byte array containing the two's-complement representation of this BigInteger. The byte array will be in big-endian byte-order: the most significant byte is in the zeroth element. The array will contain the minimum number of bytes required to represent this BigInteger, including at least one sign bit, which is (ceil((this.bitLength() + 1)/8)).

Sadly, this rules out what Data.Binary offers. Is there something efficient to do a ByteString <-> Integer conversion following this convention somewhere in the libraries? If not, how can it be done?

Based on the answer from Thomas M. DuBuisson (and the following discussion) I currently have

i2bs :: Integer -> B.ByteString
i2bs x
   | x == 0 = B.singleton 0
   | x < 0 = i2bs $ 2 ^ (8 * bytes) + x
   | otherwise = B.reverse $ B.unfoldr go x
   where
      bytes = (integerLogBase 2 (abs x) + 1) `quot` 8 + 1
      go i = if i == 0 then Nothing
                       else Just (fromIntegral i, i `shiftR` 8)

integerLogBase :: Integer -> Integer -> Int
integerLogBase b i =
     if i < b then
        0
     else
        -- Try squaring the base first to cut down the number of divisions.
        let l = 2 * integerLogBase (b*b) i
            doDiv :: Integer -> Int -> Int
            doDiv i l = if i < b then l else doDiv (i `div` b) (l+1)
        in  doDiv (i `div` (b^l)) l

Which is more verbose than what I was hoping for, still misses the bs2i function.

3
haskellbinaryintegertwos-complement
Does it have to be portable, or can you assume GHC with the integer-gmp package? - Daniel Fischer
I'd prefer a portable solution. If I remember correctly, even GHC can be built without GMP? That would be a bit too fragile then. - Waldheinz
Yes, it can be built with integer-simple. You could just be more efficient if you use the internals. One further question, do you want a ByteString containing only the bits of the number, or is it to be part of a larger ByteString so that you'd have a field specifying how many bytes make up the representation? - Daniel Fischer
Only the raw bits are needed. - Waldheinz

3 Answers

6
votes

Just steal the i2bs and bs2i routines from crypto-api and give them a slight modification:

import Data.ByteString as B

-- |@i2bs bitLen i@ converts @i@ to a 'ByteString'
i2bs :: Integer -> B.ByteString
i2bs = B.reverse . B.unfoldr (\i' -> if i' == 0 then Nothing
                                                else Just (fromIntegral i', i' `shiftR` 8))


-- |@bs2i bs@ converts the 'ByteString' @bs@ to an 'Integer' (inverse of 'i2bs')
bs2i :: B.ByteString -> Integer
bs2i = B.foldl' (\i b -> (i `shiftL` 8) + fromIntegral b) 0 . B.reverse

You can make this slightly more efficient by determining the bit size first and use the original i2bs to construct the bytestring in order (saving you the cost of reverse).

(EDIT: I should note this isn't tested with a Java parser, but this basic construct should be easy for you to mutate to take into account any missing bits).

1
votes

Ok, so a fully working solution based on the partial answer by Thomas M. DuBuisson is:

bs2i :: B.ByteString -> Integer
bs2i b
   | sign = go b - 2 ^ (B.length b * 8)
   | otherwise = go b
   where
      go = B.foldl' (\i b -> (i `shiftL` 8) + fromIntegral b) 0
      sign = B.index b 0 > 127

i2bs :: Integer -> B.ByteString
i2bs x
   | x == 0 = B.singleton 0
   | x < 0 = i2bs $ 2 ^ (8 * bytes) + x
   | otherwise = B.reverse $ B.unfoldr go x
   where
      bytes = (integerLogBase 2 (abs x) + 1) `quot` 8 + 1
      go i = if i == 0 then Nothing
                       else Just (fromIntegral i, i `shiftR` 8)

integerLogBase :: Integer -> Integer -> Int
integerLogBase b i =
     if i < b then
        0
     else
        -- Try squaring the base first to cut down the number of divisions.
        let l = 2 * integerLogBase (b*b) i
            doDiv :: Integer -> Int -> Int
            doDiv i l = if i < b then l else doDiv (i `div` b) (l+1)
        in  doDiv (i `div` (b^l)) l

I won't accept my own answer anytime soon in case someone wants to come up with something more neat to show of his skills. :-)

0
votes

Here is a solution without needing to calculate the size first. For negative numbers, it does the equivalent of inverting all the bits, performs the calculation, then inverts the bits again.

i2bs :: Integer -> B.ByteString
i2bs x = B.reverse . B.unfoldr (fmap go) . Just $ changeSign x
  where
    changeSign :: Num a => a -> a
    changeSign | x < 0     = subtract 1 . negate
               | otherwise = id
    go :: Integer -> (Word8, Maybe Integer)
    go x = ( b, i )
      where
        b = changeSign (fromInteger x)
        i | x >= 128  = Just (x `shiftR` 8 )
          | otherwise = Nothing

bs2i :: B.ByteString -> Integer
bs2i xs = changeSign (B.foldl' go 0 xs)
  where
    changeSign :: Num a => a -> a
    changeSign | B.index xs 0 >= 128 = subtract 1 . negate
               | otherwise           = id
    go :: Integer -> Word8 -> Integer
    go i b = (i `shiftL` 8) + fromIntegral (changeSign b)