odczyt/zapis Haskell Integer w reprezentacji uzupełnienie dwójkowe

Question

potrzebne do odczytu i zapisu liczb całkowitych w sposób, który jest zgodny z tym, co robi Java z jego BigInteger klasa:

Zwraca tablicę bajtów zawierający reprezentację uzupełnienie do dwóch z ten BigInteger. Tablica bajtów będzie w kolejności bajtów big-endian: znaczący bajt znajduje się w elemencie zerowym. Tablica będzie zawierała minimalną liczbę bajtów wymaganych do reprezentowania tego BigInteger, , zawierającego co najmniej jeden bit znaku, który jest (ceil ((this.bitLength() + 1)/8)).

Niestety, to wyklucza, co oferuje Data.Binary. Czy jest coś skutecznego do przeprowadzenia konwersji według tej konwencji gdzieś w bibliotekach? ByteString < ->Jeśli nie, jak można to zrobić?

oparciu o odpowiedź od Thomas M. Dubuisson (i dalszej dyskusji) Obecnie mam

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 

który jest bardziej gadatliwy niż to, co miałem nadzieję, nadal zdobywa funkcję bs2i.

Answer 1

Wystarczy ukraść i2bs i bs2i rutyny z krypto-API i daje im lekką modyfikację:

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 

Można zrobić to nieco bardziej wydajny przez określenie wielkości bitowej pierwszy i używać oryginalnego i2bs do skonstruowania bytestring po kolei (oszczędzając koszt odwrócenia).

(EDYTOWANIE: Powinienem zauważyć, że nie jest to testowane z parserem Java, ale ta podstawowa konstrukcja powinna być łatwa do zmutowania w celu uwzględnienia brakujących bitów).

Answer 2

Ok, więc to rozwiązanie w pełni działa na podstawie odpowiedzi częściowej Thomasa M. Dubuisson jest:

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 

nie zaakceptuje moje własne odpowiedzi w każdej chwili wkrótce w przypadku gdy ktoś chce coś wymyślić więcej schludny, aby pokazać swoje umiejętności. :-)

Answer 3

Oto rozwiązanie bez liczenia najpierw. W przypadku liczb ujemnych wykonuje równoważnik odwracania wszystkich bitów, wykonuje obliczenia, a następnie ponownie odwraca bity.

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)