However, the semantics differ from just using a temporary variable in that if a and b are in the same memory location then the result will be zero.
This was used in an entry for the underhanded C contest [1] if I remember correctly where for an implementation of RC4 the author defined the following macro.
#define SWAP(x, y) do { x^=y; y^=x; x^=y; }
And used it for swapping the values in the substitution table for the cipher, e.g. SWAP(S[i], S[j]). The weakness was that since sometimes the indices are the same in RC4 the substitution table would be gradually replaced with zeroes. a1 = a0 ^ b0
b1 = b0 ^ a1 = b0 ^ (a0 ^ b0) = (a0 ^ b0) ^ b0 = a0
a2 = a1 ^ b1 = (a0 ^ b0) ^ a0 = (b0 ^ a0) ^ a0 = b0
The xor-linked list (https://en.wikipedia.org/wiki/XOR_linked_list) is another neat idea along the same theme.I was implementing a toy rc4 cipher. One of the steps in the ciphers involves swapping entries in an arrays of 256 elements. I thought "hey, I'm a 1337 coder, I'm going to use the xor trick".
Except it doesn't work if you're trying to swap something with itself. If you do "a[i] ^= a[j]" and i == j then you're just clearing the entry.
Taught me the valuable lesson that I shouldn't try to be a smartass while writing code and the importance of unit tests.
a = a + b
b = b + a
a = b - a
b = b - 2*ab = a - b
a = a - b
I think this works too, assuming a+b doesn't overflow.
> I think this works too, assuming a+b doesn't overflow.
Well, in two's complement arithmetic (as is used on most architectures), the intermediate overflow can be ignored, and it will work just fine.
Except that 2a, that might be trouble.
14 - 15 gives 15
1110 + 1111 = 1101
1101 - 1110 = 1111
1101 - 1111 = 1110
Overflow doesn't matter if you just want to swap. mov eax, edi
mov edi, esi
mov esi, eax
I would intuitively use the `xchg` instruction that x86-32/x86-64 provides instead. Is there a specific reason why the compiler(s) decide to generate the mentioned code instead?"Instructions with a LOCK prefix have a long latency that depends on cache organization and possibly RAM speed. If there are multiple processors or cores or direct memory access (DMA) devices then all locked instructions will lock a cache line for exclusive access, which may involve RAM access. A LOCK prefix typically costs more than a hundred clock cycles, even on single-processor systems. This also applies to the XCHG instruction with a memory operand."
So I still stand by my point: What is the reason why the compiler uses `mov` for exchanging two registers here instead of `xchg`?
"Vector path instructions are less efficient than single or double instructions because they require exclusive access to the decoders and pipelines and do not always reorder optimally. For example:
; Example 17.1. AMD instruction breakdown
xchg eax, ebx ; Vector path, 3 ops
nop ; Direct path, 1 op
xchg ecx, edx ; Vector path, 3 ops
nop ; Direct path, 1 op
This sequence takes 4 clock cycles to decode because the vector path instructions must decode alone."
I didn't believe him until he showed me. Apparently they used to use it all the time to swap out entire segments of RAM in the S/360 without having to page out to disk or clobber other free RAM segments. It is simply:
Three steps, same as using a placeholder 'c' variable. I think he mentioned on most of the processors of the time, 3 XOR instructions actually worked faster than 3 MOV instructions.Illustration for the non-believers:
Voila!