Efficient packing bytes into Integers?

Question

This is one of those questions that seem easy at first, but I've been researching for a while now and can't find the answer....

I need to convert a list of bytes (ie- Word8s) to a number of arbitrary length (ie- an Integer). For example

intPack::[Word8]->Integer
intPack [1] = 1
intPack [1, 0] = 256
showHex (intPack [1,2,3,4,5,6,7,8,9,10,11]) "" = "102030405060708090a0b"

A slow solution is easy to write (see the answers in How to convert a ByteString to an Int and dealing with endianness?)

intPack = foldl (\v -> ((v*256) +)) 0

....But I cringe at this, all the extra multiplications and additions, plus a string of useless Integers created in the middle, just to (probably) get the same bytes I started with packed into the internal structures of the Integer type.

Of course, I don't know the details of how Integer does store its data (perhaps it does something more complicated than hold the bytes in a variable length array.... like use flags to denote the length of the number, like utf-8 does when encoding chars). At least it would be good to know that the intPack above is as good as it gets.... Then I could stop my researching, bite (or rather byte :) ) the bullet, and move on.

Answer 1

I would look at the binary package for efficiently packing and unpacking binary data structures:

https://hackage.haskell.org/package/binary-0.7.2.1/docs/Data-Binary-Get.html

Some ideas:

1. See if the Binary Integer instance can work for you:

   import Data.Binary
   import qualified Data.ByteString.Lazy.Char8 as LBS
   main = do
     let i = 0x0102030405060708090a0b0c0d0e0f :: Integer
         bs = encode i
     print ("before", i)
     LBS.writeFile "output" bs
     j <- fmap decode $ LBS.readFile "output" :: IO Integer
     print ("after", j)
   

2. Have a look at the definitions of functions like word64be to see if it gives you any ideas:

http://hackage.haskell.org/package/binary-0.7.2.1/docs/src/Data-Binary-Get.html#getWord64be