Challenge : comment échangeur le contenu de deux variables sans variable intermédiaire ? La réponse dans cet article !
0x01. CONCEPT
L'idée est de faire un échange de deux variables sans variable intermédiaire, afin d'optimiser :
- en mémoire, le programme a besoin d'une variable de moins : sur une variable c'est rien, sur un grand nombre d'échange cela peut faire une différence, notammelent sur une architecture légère voire pauvre en mémoire (ex. embarqué) ;
- l'opération XOR est une opération CPU très rapide - optimisée notamment pour des opérations de chiffrement comme l'AES.
0x02. VARIABLE INTERMEDIAIRE
int a=10; int b=20; int i; // intermédiare i=a; // 3 instructions CPU a=b; b=i;
; Le code Assembleur associé : _main: 0000000100000f90 push rbp 0000000100000f91 mov rbp, rsp 0000000100000f94 xor eax, eax 0000000100000f96 mov dword [rbp+var_4], 0x14 ; 0x14 = 20 0000000100000f9d mov dword [rbp+var_8], 0xa ; 0xa = 10 0000000100000fa4 mov ecx, dword [rbp+var_4] 0000000100000fa7 mov dword [rbp+var_C], ecx 0000000100000faa mov ecx, dword [rbp+var_8] 0000000100000fad mov dword [rbp+var_4], ecx 0000000100000fb0 mov ecx, dword [rbp+var_C] 0000000100000fb3 mov dword [rbp+var_8], ecx 0000000100000fb6 pop rbp 0000000100000fb7 ret
0x02. TRIPLE XOR
int a=10; int b=20; a ^= b; // 3 instructions CPU b ^= a; a ^= b; // En version condensée : // a ^= b ^ ( b=a );
; Le code Assembleur associé : _main: 0000000100000f80 push rbp 0000000100000f81 mov rbp, rsp 0000000100000f84 xor eax, eax 0000000100000f86 mov dword [rbp+var_4], 0x14 ; 0x14 = 20 0000000100000f8d mov dword [rbp+var_8], 0xa ; 0xa = 10 0000000100000f94 mov ecx, dword [rbp+var_8] 0000000100000f97 xor ecx, dword [rbp+var_4] 0000000100000f9a mov dword [rbp+var_4], ecx 0000000100000f9d mov ecx, dword [rbp+var_4] 0000000100000fa0 xor ecx, dword [rbp+var_8] 0000000100000fa3 mov dword [rbp+var_8], ecx 0000000100000fa6 mov ecx, dword [rbp+var_8] 0000000100000fa9 xor ecx, dword [rbp+var_4] 0000000100000fac mov dword [rbp+var_4], ecx 0000000100000faf pop rbp 0000000100000fb0 ret
0x05. CONCLUSION
=> Écrit par : Nicolas, le 09 octobre 2017