BitsBase

This submodule implements some abstractions for working with bits that are used by other submodules.

The conceit is that it should be possible to write (performant) function methods for working with bits that have minimal dependence on the representation of the bits. Bits can be represented by unsigned integers, arrays of unsigned integers, Strings, and lazy views of each of these as a different bit representation. We want to write methods that don't depend on which representation we use.

Analogs to Base.collect, size, sizeof, getindex, eachindex, axes are BitsX.Bits.bitcollect, bitsize, bitsizeof, bit, biteachindex, and bitaxes.

An example of a function built on these abstractions is bitcollect, which has this definition

function bitcollect(obj)
    array = Array{Bool}(undef, bitsize(obj))
    # Assume LinearIndices. Probably not always correct
    for (i, ind) in enumerate(biteachindex(obj))
        array[i] = bit(obj, ind)
    end
    array
end

Note that bitcollect depends on bitsize, bit, and biteachindex. The latter depends on bitaxes1, which depends on bitaxes.

Examples

Here are some concrete examples.

julia> s = "10101010"; x = parse(UInt8, s; base=2); v = Bool[1,0,1,0,1,0,1,0];

julia> bitlength.((x, v, s, codeunits(s)))
(8, 8, 8, 8)

Performance

A goal is that there be little or no performance penalty for using this interface.

For example, because the bitstrings contain only ASCII characters, bitlength(::String) does not traverse the entire string

julia> s = "1"^1000;

julia> @btime length($s)
  401.550 ns (0 allocations: 0 bytes)
1000

julia> @btime bitlength($s)
  1.763 ns (0 allocations: 0 bytes)
1000

binzero(x::T)

The value of type T representing bit value zero.

If T <: Integer, or a matrix thereof, return zero(::T). If T is other AbstractArray, AbstractString, AbstractFloat, Complex, throw a MethodError.

The fallback method returns zero(x).

binzero(x)

The value of type T representing bit value zero.

Examples

julia> binzero.((Char, '-', Int, UInt8, 42))
('0', '0', 0, 0x00, 0)

binone(x::T)

The value of type T representing bit value one.

Examples

julia> binone.((Char, '-', Int, UInt8, 42))
('1', '1', 1, 0x01, 1)

isbinzero(x)

Return true if x represents bit value zero.

See also binzero.

isbinone(x)

Return true if x represents bit value one.

See also binone.

isbin(b)::Bool

Return true is b represents a binary digit.

This is of course subjective in general. But this package has rules for what values of various types can be interpreted as Bools.

Examples

julia> isbin.((true, false, 1, 0, '1', '0', 42, 'c'))
(true, true, true, true, true, true, false, false)

julia> isbin("1")
ERROR: MethodError: no method matching binzero(::String)

is_zero_char(x)

Return true if x is equal to '0' or its ASCII code.

Examples

julia> is_zero_char.(('0', '1', 'c', UInt8('0'), UInt8('1'), UInt8('c')))
(true, false, false, true, false, false)

is_one_char(x)

Return true if x is equal to '1' or its ASCII code.

Examples

julia> is_one_char.(('0', '1', 'c', UInt8('0'), UInt8('1'), UInt8('c')))
(false, true, false, false, true, false)

julia> is_one_char.((Int('1'), 42))
(true, false)

is_binary_char(x)

Return true if x is equal to either '0' or '1' or their ASCII codes.

Examples

julia> is_binary_char.(('1', Int('1'), '0', 'a', 100))
(true, true, true, false, false)

to_binary_char(x::T)::Char

Convert x to the Char '0' or '1'. x must be equal to either binzero(T) or binone(T).

Examples

julia> to_binary_char.((1, '1', true, 0x01, 0, '0', false, 0x00))
('1', '1', '1', '1', '0', '0', '0', '0')

to_binary_char_code(x::T)::UInt8

Convert x to the ASCII code for character '0' or '1'. One of isbinzero(x) or isbinone(x) must return true.

isbinzero and isbinone fall back to iszero and isone where this makes sense.

T must implement iszero (or zero) and isone (or one). Alternatively, you can implement isbinzero (or binzero) and isbinone (or binone)

Examples

julia> to_binary_char_code.((1, '1', true, 0x01, 0, '0', false, 0x00))
(0x31, 0x31, 0x31, 0x31, 0x30, 0x30, 0x30, 0x30)

julia> to_binary_char_code(42)
ERROR: DomainError with 42:
Must be zero or one value of type Int64.

See also binzero, binone.

from_binary_char([::Type{T} = Bool], x)

Convert the characters '0' and '1' (or UInt8('0') and UInt8('1')) to binzero(T) and binone(T).

Examples

julia> from_binary_char.(Bool, ('1', UInt8('1'), '0', UInt8('0')))
(true, true, false, false)

julia> from_binary_char('c')
ERROR: DomainError with 99:

bitconvert([T=Bool], b)::T

Convert the representation of a bit b to the representation of a bit of type T.

Examples

julia> bitconvert.((true, 1, UInt64(1), '1'))
(true, true, true, true)

julia> bitconvert(3)
ERROR: ArgumentError: Value 3 cannot be interpreted as a bit value of type Bool

julia> bitconvert.(UInt8, ('0', 0, UInt64(0)))
(0x00, 0x00, 0x00)

min_bits(n::Integer)
min_bits(bit_str::AbstractString)
min_bits(v)

Return the required number of bits in the binary representation of n (or bit_str, or iterable v).

The returned value is the position of the leftmost bit equal to 1, counting from the right. Equivalently, the value is the length of the bit_str discounting leading zeros.

Examples

julia> min_bits(2^10)
11

julia> min_bits("1"^10)
10

julia> min_bits([0,1,0])
2

min_dits(v)

Return the minimum number of "dits" needed to express v.

The first element not representing zero counting from the left determines the return value. Input is not validated.

Examples

julia> min_dits("03Q")
2

julia> min_dits([0, 3, 17])
2

bitaxes(B)

Return the valid range of indices for array B when interpreted as an array of bits.

biteachindex(A)

Create an iterable object for visiting each index of B when interpreted as an array of bits.

bitlastindex(A)

Return the last index of collection A when interpreted as an array of bits.

bitsizeof(::Type{T})

Return the number of (usefully) indexable bits in an instance of type T. Here "indexable" means via bit(x::T, i).

For some types, such as Integers, bit(x::T, i) returns 0 for i greater than bitsizeof(T).

If the number of indexable bits in an instance of type T cannot be computed from the type alone, then an error is thrown.

Examples

julia> bitsizeof.((UInt8, UInt64, NTuple{5, Int}, StaticBitVectorView{Int64}))
(8, 64, 5, 64)

julia> bitsizeof(String)
ERROR: MethodError: no method matching bitsizeof(::Type{String})

julia> bitsizeof(BigInt)
ERROR: MethodError: no method matching bitsizeof(::Type{BigInt})

bitsize(B)

Return a tuple containing the dimensions of B, where B is interpreted as an array of bits.

Examples

julia> bitsize(42)
(64,)

julia> bitsize(UInt16(42))
(16,)

julia> bitsize("1011")
(4,)

julia> bitsize(Bool[1, 0])
(2,)

julia> bitsize(BitArray(undef, (3, 4)))
(3, 4)

julia> bitsize(bstringview(42))
(64,)

bitlength(x::T)

Return the number of bits in the instance x of type T. This is the number of bits that can be indexed via bit. If x is an isbitstype type, then this is the same as bitsizeof(T).

In contrast, if x is of type BigInt or BigFloat the number of bits is not encoded in the type, and in fact may vary from instance to instance.

bitlength(str::AbstractString)

The number of characters in str, which is assumed to contain only '0' and '1'. If str contains other characters, the returned value will be incorrect.

count_bits(s::AbstractString)
count_bits(v::AbstractVector{UInt8})

Return the number of characters (or bytes) that are '1' or '0', (0x30 or 0x31).

It is assumed that s is an ASCII string. count_bits may be useul if the string includes formatting characters, for example spaces.

bit(x::Real, i::Integer)

Similar to Bits.bit from registered Bits.jl package. A difference is that the return type here does not depend on the input type, but rather is always Int. (Check a. is this true and b. what do we prefer?)

bit(str::AbstractString, i::Integer)::Int

Return 1 if the ith character of str is '1' and 0 if it is '0'. Otherwise throw an ArgumentError.

It is assumed that str has one byte per character, or more precisely, one UInt8 code unit per code point. Thus, accessing the ith character via bit may be more efficient than str[i].

tstbit(x::Real, i::Integer) -> Bool

Similar to bit but returns the bit at position i as a Bool.

Examples

julia> tstbit(0b101, 3)
true

bit0(x, i)

Like bit(x, i) except the first bit has index 0 rather than 1.

tstbit0(x, i)

Like tstbit(x, i) except the first bit has index 0 rather than 1.

struct OneBased

A type used for dispatch that signifies that the first index is zero.

struct OneBased

A type used for dispatch that signifies that the first index is one.