Read/Write Haskell Integer in Zweierkomplement-Darstellung

Question

Ich brauche ganzen Zahlen in einer Art und Weise zu lesen und zu schreiben, die mit kompatibel ist, was Java tut mit seiner BigInteger Klasse:

ein Byte-Array Gibt die Zweierkomplement-Darstellung enthält von dieser BigInteger. Das Byte-Array befindet sich in Big-Endian-Byte-Reihenfolge: Das höchstwertige Byte befindet sich im nullten Element. Das Array enthält die minimale Anzahl von Bytes, die benötigt werden, um diesen BigInteger darzustellen, einschließlich mindestens ein Vorzeichen-Bit, das ist (ceil ((this.bitLength() + 1)/8)).

Leider schließt dies aus, was Data.Binary bietet. Gibt es etwas Effizientes, um eine ByteString < ->Integer Konvertierung nach dieser Konvention irgendwo in den Bibliotheken zu tun? Wenn nicht, wie kann es gemacht werden?

Basierend auf der Antwort von Thomas M. Dubuisson (und der folgenden Diskussion) Ich habe derzeit

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 

Welche als ausführlicher ist, was ich gehofft, noch fehlt die bs2i Funktion.

Answer 1

einfach stehlen die i2bs und bs2i Routinen von Krypto-api und geben ihnen eine leichte Änderung:

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 

Sie können dies leicht machen effizienter durch die Bitgröße erste Bestimmung und die Original i2bs das konstruieren Bytestring in der Reihenfolge (sparen Sie die Kosten für die Umkehrung).

(BEARBEITEN: Ich sollte beachten, dass dies nicht mit einem Java-Parser getestet wird, aber dieses grundlegende Konstrukt sollte leicht für Sie mutieren, um fehlende Bits zu berücksichtigen).

Answer 2

Ok, also eine voll funktionsfähige Lösung auf der Grundlage der Teilantwort von Thomas M. Dubuisson ist:

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 

Ich werde nicht meine eigene Antwort zu jeder Zeit annehmen bald, falls jemand will mehr mit etwas einfallen lassen, ordentlich, um seine Fähigkeiten zu zeigen. :-)

Answer 3

Hier ist eine Lösung, ohne die Größe zuerst berechnen zu müssen. Bei negativen Zahlen entspricht dies dem Invertieren aller Bits, führt die Berechnung durch und invertiert dann die Bits erneut.

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)