# 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 0`0x1`

:`~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)
```