Static-ranged BitArray and subtype implementation

[ktbarrett]

BitArray, Signed, Unsigned, Sfixed, Ufixed, and Float are all reinterpretable with each other, so we need a reasonable set of implementations that work for all of the static-ranged versions of these types.

Size == 0

Empty class to take advantage of empty class optimization.

0 < Size <= 8, 16, 32, 64

int8_t or uint8_t, uint16_t, uint32_t, uint64_t. We will assume that signed and unsigned integers can be cast to each other in reasonable way (make sure to add -fwrapv). This will use the smallest integer that can hold the value.

Size > 64, <= 128

We should also check if the compiler supports extended 128-bit integer types. This might optimize integers just slightly larger than 64 bits instead of jumping into arbitrary precision types.

Size >128 / >64 if no __int128_t is available

This still needs some investigation. This will likely be something like GMP arbitrary precision integers. The important questions to ask still are:

• Can we have fixed arbitrary sized integer types?
• Will those types have well-defined wrapping at exactly that bit length?
• Is unsigned <-> signed casting well-defined?
• Where is the storage for tha value? On the heap or locally?

[ktbarrett]

After some research LLVM's APInt looks like what we want, but we would then have a dependency on LLVM... worth considering. I wonder if we just use std::vector<bool>/ roll our own type for very large BitArrays and not support arithmetic on anything larger than 64/128 bits.

In general the two are never seen together: you can have very wide bit vectors, but they are usually packed smaller bits of data, and thus don't need to support anything but slicing and bitwise operations. Things you do arithmetic on tend to be <128 bits because otherwise you just can't meet timing.

If this becomes a problem in the future we can adopt APInt, maybe as an optional dependency.