triton-vm icon indicating copy to clipboard operation
triton-vm copied to clipboard

Replace instructions `and` and `xor` by `nand` or `nor`

Open jan-ferdinand opened this issue 2 years ago • 2 comments

The current set of binary instructions available in Triton VM, and and xor, is functionally complete, but not minimally so. Replacing them by either nand or nor

  • does not change completeness,
  • marginally decreases usability (or and not are not natively available anyway),
  • simplifies the instruction set architecture, and
  • simplifies the U32 Table.

(Originally issue number 41 in the internal issue tracker.)

jan-ferdinand avatar Aug 08 '22 09:08 jan-ferdinand

This is pretty tightly coupled with #8. Furthermore, we need a benchmark target before the question can be answered – the investigation is blocked by #7.

jan-ferdinand avatar Aug 08 '22 09:08 jan-ferdinand

(Originally posted by @aszepieniec.)

Also worth noting, for u32s:

A + B == (A ^ B) + ((A & B) << 1)

and so

A ^ B == A + B - ((A & B) << 1)

Please verify. Credit goes to @bobbinth who, IIRC, credited Daniel Lubarov.

jan-ferdinand avatar Aug 08 '22 09:08 jan-ferdinand