# DCPU-16

## Too Many NOPs

How many NOPs are out there? Not counting the next word things, we have:

• 63×64 = 4032 non-basic instructions are reserved for now.
• `SET`, `MOD`, `AND`, `BOR`, `XOR`1 with a literal as the first operand will do nothing. There are 33 first operands and 62 second operands (no side effect, so `[--SP]` and `[SP++]` are out) possible, those amounts to 5×33×62 = 10230 (!) instructions.
• `SET`, `AND`, `BOR` with the same operands will do nothing. Also `SET [--SP], [SP++]` or `SET [SP++], [--SP]` will do nothing (since the resulting value, `[SP-1]` or `[SP+1]`, will be same for each operand). Excluding earlier cases, this amounts to 3×(31+2) = 99 instructions.
• `AND x, 0xFFFF`, `BOR x, 0` and `XOR x, 0` do nothing. Excluding earlier cases, there are 2×29 = 58 `BOR`/`XOR` NOPs; 3×29 = 87 more NOPs can be counted if the next word would be zero or 0xFFFF.
• Even more obscure, `SHL O, 16` and `SHR O, 16` will do nothing: it will set `O` twice and the overflown value, which equals to `O` in this case, overwrites the formerly set value. This amounts 2 NOPs (and 2 more NOPs when the next word is 16).
• `IFE`, `IFN`, `IFG`, `IFB` with appropriate literal arguments will do nothing. Counting short literals only, there are 32 `IFE`, 322-32 = 992 `IFN`, 1+…+31 = 496 `IFG` and 781 `IFB` such instructions. 2301 instructions in total.
• Of course, `IFE` with the same operands also does nothing. This also applies to `IFE [--SP], [SP++]` and `IFE [SP++], [--SP]`, so this amounts to 31+2 = 33 instructions.

In conclusion, at least 167552 (25.6%) out of 65536 instructions are NOPs, taking 1 to 4 cycles (e.g. `MOD 0, `). If you allow clobbering `O` then you have wider choices. This is too much! If you agree you should watch the proposed modification to DCPU-16.

1. Many other basic instruction does change `O` register even when the first operand is a literal, which is unacceptable for NOPs. This can be used in interesting ways, however: for example, `ADD 0x1234, A` will set `O` to 1 if `A` is larger than 216 - 0x1234 and 0 otherwise.

2. As far as I know. I have no spare time to prove the completeness (though I have tried a SMT solver).

ikiwiki를 씁니다.
마지막 수정