Notational conventions¶
Introduction¶
Semantics of many operations are described in pseudocode. Here are some often used primitives.
Bit operations¶
In many places, the GPUs allow specifying arbitrary X-input boolean or bitwise
operations, where X is 2, 3, or 4. They are described by a 2**X
-bit mask
selecting the bit combinations for which the output should be true. For
example, 2-input operation 0x4 (0b0100) is ~v1 & v2
: only bit 2 (0b10
)
is set, so the only input combination (0, 1) results in a true output.
Likewise, 3-input operation 0xaa (0b10101010) is simply a passthrough of first
input: the bits set in the mask are 1, 3, 5, 7 (0b001, 0b011, 0b101,
0b111
), which corresponds exactly to the input combinations which have the
first input equal to 1.
The exact semantics of such operations are:
# single-bit version
def bitop_single(op, *inputs):
# first, construct mask bit index from the inputs
bitidx = 0
for idx, input in enumerate(inputs):
if input:
bitidx |= 1 << idx
# second, the result is the given bit of the mask
return op >> bitidx & 1
def bitop(op, *inputs):
max_len = max(input.bit_length() for input in inputs)
res = 0
# perform bitop_single operation on each bit (+ 1 for sign bit)
for x in range(max_len + 1):
res |= bitop_single(op, *(input >> x & 1 for input in inputs)) << x
# all bits starting from max_len will be identical - just what sext does
return sext(res, max_len)
As further example, the 2-input operations on a
, b
are:
0x0
: always 00x1
:~a & ~b
0x2
:a & ~b
0x3
:~b
0x4
:~a & b
0x5
:~a
0x6
:a ^ b
0x7
:~a | ~b
0x8
:a & b
0x9
:~a ^ b
0xa
:a
0xb
:a | ~b
0xc
:b
0xd
:~a | b
0xe
:a | b
0xf
: always 1
For further enlightenment, you can search for GDI raster operations, which correspond to 3-input bit operations.
Sign extension¶
An often used primitive is sign extension from a given bit. This operation
is known as sext
after xtensa instruction of the same name and is formally
defined as follows:
def sext(val, bit):
# mask with all bits up from #bit set
mask = -1 << bit
if val & 1 << bit:
# sign bit set, negative, set all upper bits
return val | mask
else:
# sign bit not set, positive, clear all upper bits
return val & ~mask
Bitfield extraction¶
Another often used primitive is bitfield extraction. Extracting an unsigned
bitfield of length l
starting at position s
in val
is denoted
by extr(val, s, l)
, and signed one by extrs(val, s, l)
:
def extr(val, s, l):
return val >> s & ((1 << l) - 1)
def extrs(val, s, l):
return sext(extrs(val, s, l), l - 1)