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)