5 ms·

VPTERNLOGD is a mouthful but is fun to think about. Notice there are 4 functions mapping 1 bit -> 1 bit: const 0, const 1, copy, invert. There are 16 function

VPTERNLOGD is a mouthful but is fun to think about. Notice there are 4 functions mapping 1 bit -> 1 bit: const 0, const 1, copy, invert. There are 16 functions mapping 2 bits -> 1 bit. Think 4 possible inputs, 2 possible output values for each input (0 or 1), so there are 2^4 = 16 such functions. Likewise 256 functions mapping 3 bits -> 1 bit: 8 possible inputs, 2 possible output values for each input, so 2^8 = 256 such functions. This means that the set of functions 3 bits -> 1 bit may be indexed by a single byte! With this instruction, you specify the byte as an immediate, it is interpreted as an index into a function table, and so you get any 3-valued boolean function. I wonder if we'll see a similar instruction for 2 bits -> 2 bits? Could be useful!

moonchild 3y ago
We've seen (+, and) multiply (that's just standard multiplication) and (xor, and) multiply ('carryless multiply'); it would be interesting to see a carryless multiply where both combining functions are user-controllable. (See also: <https://twitter.com/moon_chilled/status/1639829366304821249 https://twitter.com/moon_chilled/status/1639829366304821249>; I forget why this works, though.)
- RaisingSpear 3y ago
  You might find this post interesting: https://bitmath.blogspot.com/2023/05/grevmul.html https://bitmath.blogspot.com/2023/05/grevmul.html
RaisingSpear 3y ago
> I wonder if we'll see a similar instruction for 2 bits -> 2 bits? Could be useful! You don't even need to support all 16 functions, as a number are duplicates or could be implemented with others. The following list covers all possibilities: - AND, OR, XOR [supported basically everywhere] - AND-NOT (a&~b), OR-NOT (a|~b) [sometimes supported] - NOT-AND (~(a&b)), NOT-OR (~(a|b)), NOT-XOR (aka XNOR) So only a few basic instructions need to exist to support all combinations of 2-operand bitwise logic.
- adrian_b 3y ago
  That is why the IBM POWER ISA includes only the 8 of the 16 functions of 2 Boolean variables that cannot be obtained from the others by reversing the operand order or by using for both operands the same register (which is enough to obtain the maximum instruction count reduction in comparison with the ISAs that only include AND/OR/XOR).
- bruce343434 3y ago
  Lisp has all 16! https://news.ycombinator.com/item?id=32802308 https://news.ycombinator.com/item?id=32802308
bonzini 3y ago
Fun fact, the third byte of the last argument to the Windows BitBlt function describes a 3 bits -> 1 bit function (inputs being source, destination and brush) in exactly this way. However, the two bytes below encode the formula for the function, so that the transfer could be JITted more easily. This is not really necessary, since you could just use 512 bytes for the mapping, but memory tradeoffs were different back then...
- unnah 3y ago
  It was also how you fed the operation to the Amiga blitter hardware. A nice introduction to minterms for many teenage hackers at the time... (https://en.wikipedia.org/wiki/Canonical_normal_form#Minterm https://en.wikipedia.org/wiki/Canonical_normal_form#Minterm)
Tuna-Fish 3y ago
> I wonder if we'll see a similar instruction for 2 bits -> 2 bits? Could be useful! No, because the way all modern high-performance CPUs work implies that an instruction with two destinations cannot really be any faster than two instructions with a single destination. So you can implement 3 bits -> 2 bits with two VPTERNLOGDs and can't do any better than that for 2 -> 2.
pdpi 3y ago
> There are 16 functions mapping 2 bits -> 1 bit. Think 4 possible inputs, 2 possible output values for each input (0 or 1), so there are 2^4 = 16 such functions. When people talk about algebraic data types, they tend to forget about functions. The tuple `(a, b)` is a product type because it has #a * #b possible values. The union type `a | b` is a sum type because it has #a + #b possible values. the function `a -> b` is an exponential type because it has #b ^ #a possible values.

moonchild 3y ago

We've seen (+, and) multiply (that's just standard multiplication) and (xor, and) multiply ('carryless multiply'); it would be interesting to see a carryless multiply where both combining functions are user-controllable. (See also: <https://twitter.com/moon_chilled/status/1639829366304821249 https://twitter.com/moon_chilled/status/1639829366304821249>; I forget why this works, though.)

RaisingSpear 3y ago
You might find this post interesting: https://bitmath.blogspot.com/2023/05/grevmul.html https://bitmath.blogspot.com/2023/05/grevmul.html

RaisingSpear 3y ago

> I wonder if we'll see a similar instruction for 2 bits -> 2 bits? Could be useful! You don't even need to support all 16 functions, as a number are duplicates or could be implemented with others. The following list covers all possibilities: - AND, OR, XOR [supported basically everywhere] - AND-NOT (a&~b), OR-NOT (a|~b) [sometimes supported] - NOT-AND (~(a&b)), NOT-OR (~(a|b)), NOT-XOR (aka XNOR) So only a few basic instructions need to exist to support all combinations of 2-operand bitwise logic.

adrian_b 3y ago
That is why the IBM POWER ISA includes only the 8 of the 16 functions of 2 Boolean variables that cannot be obtained from the others by reversing the operand order or by using for both operands the same register (which is enough to obtain the maximum instruction count reduction in comparison with the ISAs that only include AND/OR/XOR).
bruce343434 3y ago
Lisp has all 16! https://news.ycombinator.com/item?id=32802308 https://news.ycombinator.com/item?id=32802308

bonzini 3y ago

Fun fact, the third byte of the last argument to the Windows BitBlt function describes a 3 bits -> 1 bit function (inputs being source, destination and brush) in exactly this way. However, the two bytes below encode the formula for the function, so that the transfer could be JITted more easily. This is not really necessary, since you could just use 512 bytes for the mapping, but memory tradeoffs were different back then...

unnah 3y ago
It was also how you fed the operation to the Amiga blitter hardware. A nice introduction to minterms for many teenage hackers at the time... (https://en.wikipedia.org/wiki/Canonical_normal_form#Minterm https://en.wikipedia.org/wiki/Canonical_normal_form#Minterm)

Tuna-Fish 3y ago

> I wonder if we'll see a similar instruction for 2 bits -> 2 bits? Could be useful! No, because the way all modern high-performance CPUs work implies that an instruction with two destinations cannot really be any faster than two instructions with a single destination. So you can implement 3 bits -> 2 bits with two VPTERNLOGDs and can't do any better than that for 2 -> 2.

pdpi 3y ago

> There are 16 functions mapping 2 bits -> 1 bit. Think 4 possible inputs, 2 possible output values for each input (0 or 1), so there are 2^4 = 16 such functions. When people talk about algebraic data types, they tend to forget about functions. The tuple `(a, b)` is a product type because it has #a * #b possible values. The union type `a | b` is a sum type because it has #a + #b possible values. the function `a -> b` is an exponential type because it has #b ^ #a possible values.