Making a UInt64 bit-masking function generic


#1

I’ve got a function that currently accepts a 64 bit integer, and masks it with some other 64 bit integer e.g.

x & 0x3333333333333333

In such code, the hex is written in full, literally. But if I want to generalise this to other sizes of UInt, how do I specify 0x33 (for UInt8), 0x3333 (UInt16) and so on, without writing a lot of separate methods with different hex literals, with a fair amount of code duplication? Choosing a hex literal during compilation with a generated function seems like overkill?


#2

x & (0x3333333333333333 % typeof(x)) should work, where % converts the hex literal to one of the appropriate type.


#3

Will I suffer a performance hit since modulus is quite an expensive operation?


#4

No, that’s not really a modulus – it’s a kind of unsafe convert(typeof(x), 0x3333333333333333) call (Base.trunc_int, actually).
The native code seems pretty good to me:

julia> f{T}(x::T) = x & (0x3333333333333333 % T)
f (generic function with 1 method)

julia> f(UInt8(4))
0x00

julia> @code_native f(UInt8(4))
        .text
Filename: REPL[4]
        pushq   %rbp
        movq    %rsp, %rbp
Source line: 1
        andb    $51, %cl
        movl    %ecx, %eax
        popq    %rbp
        retq
        nopl    (%rax,%rax)

and actually is the same as if you write the literal explicitly:

julia> g(x::UInt8) = x & 0x33
g (generic function with 1 method)

julia> g(UInt8(4))
0x00

julia> @code_native g(UInt8(4))
        .text
Filename: REPL[9]
        pushq   %rbp
        movq    %rsp, %rbp
Source line: 1
        andb    $51, %cl
        movl    %ecx, %eax
        popq    %rbp
        retq
        nopl    (%rax,%rax)

#5

Thanks @pfitzseb I didn’t know that the % operator could be used to do a unsafe conversion.


#6

Here’s how I would write it. This works with all UInt types, including UInt128, which would otherwise require writing more 3s.

f(x) = x & div(typemax(x), 5)

It seems successfully constant folded so there is no performance impact.


#7

Is there a trick to knowing what to you need instead of “5” if you wanted to use any other bit pattern?


#8

The 5 mostly boils down to

julia> 0x33//0xff
0x01//0x05

but constant folding works equally well for

f(x) = x & (div(typemax(x), 0xff) * 0x33)

if you want it less magic.


#9

I think I can see how this works in general cases - hopefully I’m right: The div of 0xfff…(until the end of the int) by the byte 0xff, creates bytes of ‘1’ throughout the integer. Which when multiplied by the byte which is your desired pattern, applies this pattern throughout the integer.