====================== Notational conventions ====================== .. contents:: Introduction ============ Semantics of many operations are described in pseudocode. Here are some often used primitives. .. _bitop: 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. .. _sext: 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 .. _extr: 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)