Treat UInt8 as a Bool in certain contexts?

#1

I am writing some software that deals with parity check error correcting codes. I need to do a lot of matrix products for matrices over the field GF(2) (i.e. my matrices are binary matrices where 1+1=0). Because dot products are implemented for Array{UInt8} but not for Array{AbstractBool} I decided to use UInt8 as the data representation.

But now I need to do things like any([0x0,0x0,0x1]) and have it interpreted as any([false,false,true])… Is there a good way to do that, that does not involve creating a new array (e.g. is there such a thing as a view that changes the type of the data without creating a new array) and that does not involve writing a new any?

#2
julia> reinterpret(Bool, [0x0,0x0,0x1])
3-element reinterpret(Bool, ::Array{UInt8,1}):
 false
 false
  true

but I feel that there is a better solution to your initial problem. Maybe:

julia> [true, false, true] .⊻ [true, false, false]
3-element BitArray{1}:
 false
 false
  true

(typed \xor+tab)

1 Like
#3

@mauro3, thanks, reinterpret was what I was looking for!

I would be eager to use a solution based on broadcasting xor, but besides the elementwise application of xor I also need to reduce each of the resulting 1D arrays to a single boolean (i.e. I need a dot product that uses xor instead of +). I tried the following which:

"""S = H . E for the GF(2) field, using UInt8 encoding"""
function EtoSuint!(E,H,S)
    S .= (Huint * Euint) .% 0x2
    S
end

"""S = H . E for the GF(2) field, using BoolArray or BitArray"""
function EtoSbitbool!(E,H,S)
    @simd for i in 1:size(H)[1]
        S[i] = reduce(⊻, H[i,:] .& E)
    end
    S
end;

Array{UInt8} was 6 μs for a 150x150 matrix
BitArray was 110 μs
BoolArray was 250 μs

Did I do something obviously wrong?

EDIT: Here is a version that does not use temporary arrays:

function EtoSbitbool2!(E,H,S)
    row,col = size(H)
    for r in 1:row
        cum = 0x0
        for c in 1:col
            @inbounds cum ⊻= H[r,c] & E[c]
        end
        @inbounds S[r] = cum
    end
    S
end;

It takes 20 μs, which is still slower than the UInt8 version.

#4

It looks like xor may be suboptimal for two Bool values:

julia> @code_native xor(0x01,0x02)
	.section	__TEXT,__text,regular,pure_instructions
; ┌ @ int.jl:321 within `xor'
	xorl	%esi, %edi
	movl	%edi, %eax
	retl
	nopw	%cs:(%eax,%eax)
; └

julia> @code_native xor(true,false)
	.section	__TEXT,__text,regular,pure_instructions
; ┌ @ bool.jl:75 within `xor'
; │┌ @ operators.jl:185 within `!='
; ││┌ @ bool.jl:75 within `=='
	incl	%eax
	cmpb	%dh, %bh
	setne	%al
; │└└
	retl
; └
; ┌ @ bool.jl:75 within `<invalid>'
	nopw	(%eax,%eax)

The conversion between cum (a UInt8) to/from Bool values also takes some time; it speeds up a bit if you initialize cum = zero(eltype(H)) instead.

2 Likes