# Efficient way to go from bit-packed value to \`Vector{T\<:Unsigned}\`

**URL:** <https://discourse.julialang.org/t/efficient-way-to-go-from-bit-packed-value-to-vector-t-unsigned/40098>\
**Category:** New to Julia\
**Created:** [May 25, 2020, 1:45am UTC](https://discourse.julialang.org/t/efficient-way-to-go-from-bit-packed-value-to-vector-t-unsigned/40098 "2020-05-25T01:45:38Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [May 25, 2020, 1:45am UTC](https://discourse.julialang.org/t/efficient-way-to-go-from-bit-packed-value-to-vector-t-unsigned/40098/1 "2020-05-25T01:45:38Z")

</div>

I am trying to write a faster Parquet reader (faster than the one in Parquet.jl atm).

One interesting problem that I encountered is this: How to efficiently unpack a set of bit-packed integers into `Vector{T<:Unsigned}` for some `T`?

The data is stored in a bit-packed way explained [here](https://github.com/apache/parquet-format/blob/master/Encodings.md#run-length-encoding--bit-packing-hybrid-rle--3) (see point 1).

See exerpt

 ![image](https://global.discourse-cdn.com/julialang/original/3X/3/8/38023543f826e02e4b0963ed178a69cd5dc72c1b.png)

So basically given a `Vector{UInt8}` of bit-packed values. How do I convert it back `Vector{T<:Unsigned}`

For example, if

```julia
bit_packed = UInt8[161]

```

and say the bitwidth is 1, i.e every bit represents a value.

The binary form of 161 is `10100001`, so it should unpack to

```julia
UInt8[1, 0, 0, 0, 0, 1, 0, 1]

```

For this case, I think `digits` works very well, e.g.

`reverse(digits(UInt8(161), base = 2, pad = 8))`

For bitwidth greater than 1, I can do bitshift and then do a similar trick.

E.g. consider the pictured example where `bitwidth = 3` and I have bit-packed

`unpacked = UInt8[0, 1, 2, 3, 4, ,5, 6, 7]`

which gets stored packed as

```julia
UInt8[136, 198, 250]

```

```julia
nth_values(bitpacked, n, bitwidth) = begin
    result = UInt(0)
    from_bits = (n - 1)*bitwidth + 1 
    to_bits = n*bitwidth

    from_byte = ceil(Int, from_bits / 8)
    to_byte = div(to_bits - 1, 8)
    to_byte = to_byte + 1

   for byte in @view bitpacked[to_byte:-1:from_byte]
      result = result << 8
      result = result | byte
   end
   
   result = result >> (mod(from_bits-1, 8))
   result & UInt(2^bitwidth - 1)
end

```

```julia
nth_values.(Ref(bitpacked), 1:8, 3)

```

which yields

```julia
UInt8[0, 1, 2, 3, 4, 5, 6, ,7]

```

but I feel it’s a bit unsatisfactory and may be quite slow. I wonder if there are well known algorithm for faster unpacking?

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [May 25, 2020, 1:48am UTC](https://discourse.julialang.org/t/efficient-way-to-go-from-bit-packed-value-to-vector-t-unsigned/40098/2 "2020-05-25T01:48:09Z")

</div>

Do you actually need to unpack? It seems like one approach would be to define a type of 3 bit integer arrays.

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [May 25, 2020, 1:49am UTC](https://discourse.julialang.org/t/efficient-way-to-go-from-bit-packed-value-to-vector-t-unsigned/40098/3 "2020-05-25T01:49:05Z")

</div>

is that even possible? How then do I sort it etc?

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [May 25, 2020, 1:59am UTC](https://discourse.julialang.org/t/efficient-way-to-go-from-bit-packed-value-to-vector-t-unsigned/40098/4 "2020-05-25T01:59:11Z")

</div>

What about something like this approach: [Reinterpret packed data which is already in memory? - #2 by stevengj](https://discourse.julialang.org/t/reinterpret-packed-data-which-is-already-in-memory/39549/2) ?

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [May 25, 2020, 2:02am UTC](https://discourse.julialang.org/t/efficient-way-to-go-from-bit-packed-value-to-vector-t-unsigned/40098/5 "2020-05-25T02:02:24Z")

</div>

Feels like it only works if the data is a mulitple of 8 bits. The bitpacked values can be any number and not necessarily a multiple of 8.

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [May 25, 2020, 2:04am UTC](https://discourse.julialang.org/t/efficient-way-to-go-from-bit-packed-value-to-vector-t-unsigned/40098/6 "2020-05-25T02:04:15Z")

</div>

Another problem is that the bitwidth is not a factor of 8 and may not be a multiple of 8 so one value can be stored across two bytes.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [May 25, 2020, 2:52am UTC](https://discourse.julialang.org/t/efficient-way-to-go-from-bit-packed-value-to-vector-t-unsigned/40098/7 "2020-05-25T02:52:51Z")

</div>

> [@xiaodai](#):
>
> Feels like it only works if the data is a mulitple of 8 bits. The bitpacked values can be any number and not necessarily a multiple of 8.

Just break the data into chunks of the least-common multiple `lcm(8, bitwidth) ÷ 8` bytes, and then use bit-shift/mask operations.

For example, in your 3-bit example, I would loop through the data in groups of 3 bytes, and pull out 8 numbers from each 3-byte block.

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [May 25, 2020, 3:26am UTC](https://discourse.julialang.org/t/efficient-way-to-go-from-bit-packed-value-to-vector-t-unsigned/40098/8 "2020-05-25T03:26:27Z")

</div>

Thanks for the suggestion. I was thinking something along the same line, but the bitwidth can be as large as 32. So say my bitwidth is `17` so I can store it in a primitive type like this

```julia
primitive type Foo lcm(17, 8) end

```

and `lcm(8, 17)` happens to be 136. But there is no bitshift operation defined on it and there is also no `&`

E.g.

```julia
bitpicked = UInt8[1:8...]
bitpacked_val = unsafe_load(Ptr{UInt}(pointer(bitpicked)))
bitpacked_val & UInt(2^17-1)

```

works but

```julia
bitpacked_val = unsafe_load(Ptr{Foo}(pointer(bitpicked)))
bitpacked_val & UInt(2^17-1)

```

doesn’t work.

Is there a way define shifts and mask for these primitive types?

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [May 25, 2020, 3:29am UTC](https://discourse.julialang.org/t/efficient-way-to-go-from-bit-packed-value-to-vector-t-unsigned/40098/9 "2020-05-25T03:29:31Z")

</div>

> [@stevengj](#):
>
> and pull out 8 numbers from each 3-byte block.

That would require defining a bitshift operation on 24bits or I need to `Base.zext_int` to a 32 bit integer before I can do the operations. But seems like I am out of luck for bitwidth where `lcm(bitwidth, 8) > 128`.

One thing I can do is to treat those as special and anything smaller, I can just `Base.zext_int` into the next size for pulling out numbers.

---

<div class="post-metadata">

**Author:** ![datnamer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/datnamer/32/3471_2.png) [@datnamer](https://discourse.julialang.org/u/datnamer)\
**Post date:** [May 25, 2020, 4:06am UTC](https://discourse.julialang.org/t/efficient-way-to-go-from-bit-packed-value-to-vector-t-unsigned/40098/10 "2020-05-25T04:06:59Z")

</div>

I hardly know anything about this low level programming, but would this package be helpful?[GitHub - RelationalAI-oss/Blobs.jl: Binary blobs with on-the-fly pointer patching](https://github.com/RelationalAI-oss/Blobs.jl)

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [May 25, 2020, 4:44am UTC](https://discourse.julialang.org/t/efficient-way-to-go-from-bit-packed-value-to-vector-t-unsigned/40098/11 "2020-05-25T04:44:03Z")

</div>

Thanks. I thinkit falls into the same category as previous suggestions in that it doesn’t to be able to deal with high bitwidth structures.