3 ms·
You're missing the point. All instructions can be simplified to short integer operations, then all integer operations are just networks of gates, then all gates
by viraptor 1y ago
You're missing the point. All instructions can be simplified to short integer operations, then all integer operations are just networks of gates, then all gates can be replaced with AND/OR/NOT, or even just NAND. That's why you can SAT solve program equivalence. See SMT2 programs using BV theory for example.
Also of course all instructions are MOV anyway. https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator
- agent327 1y agoI seem to remember that program equivalence is an NP-hard problem. I very much doubt that you can solve it by reducing it to logic gates.
- viraptor 1y agoNP-hard is just a complexity class, not a minimal threshold. SAT solving is kind of a guided optimistic bruteforcing. If the example is small enough, you can still solve it very quickly. Same as you can solve travelling salesman for a small number of cities. We solve small cases of NP-hard things all over the place.
- viraptor 1y ago(not to confirm it's an np-hard problem - it may not even be decidable generally, but in practice yes, you can check it that way and SMT2 theories provide the right ops)
- dragontamer 1y agoThat's why superoptimizers work on short sequences of code and take a long time doing so.