- Messaggi
- 2,332
- Reazioni
- 1,928
- Punteggio
- 134
I costrutti condizionali: switch, un analisi a basso livello (Parte 2/2)
Indice degli argomenti:
1. Prefazione
Nella prima parte - I costrutti condizionali: if e branch prediction (1/2) - mi sono occupato del costrutto condizionale IF. Scopo di questo articolo è trattare invece un altro costrutto condizionale, lo switch.
2. Introduzione
Nel corso degli anni più volte ho riscontrato il tentativo di porre if e switch sullo stesso piano, considerandoli intercambiabili, e solo "un modo diverso per fare la stessa cosa". Come vedremo - specialmente chi è relativamente nuovo nel campo - le cose non stanno proprio così.
Le osservazioni avverranno su eseguibili prodotti con i seguenti compilatori:
Come debugger ho scelto OllyDbg (v.2).
3. Lo switch
Ad alto livello lo switch si presenta in questo modo:
Perdonate la banalità dell'esempio in esame, però complicare inutilmente il codice considerando la finalità dell'articolo mi sembrava futile.
A basso livello si presenta in questo modo:
GCC
E' lampante la differenza con il codice presentato nell'articolo precedente riguardante l'if. Prendiamo in considerazione alcune istruzioni dello screen mostrato sopra:
EAX contiene il valore inserito in input (valore contenuto in LOCAL.1, si tratta di una variabile locale; siamo sullo stack infatti e lo si nota dal segment override prefix, SS). Se il valore contenuto in JA è superiore di 5, avviene il salto all'indirizzo 0x004016B6 (il default case).
In caso contrario viene calcolato questo offset: EAX * 4 + 4040E0. L'offset è l'inizio di una jump table; in tal modo viene selezionato il case da eseguire senza effettuare ulteriori controlli.
Microsoft Compiler
Anche in questo caso focalizziamoci su alcune istruzioni:
La jump table è appena sotto alla funzione analizzata (che è poi il main() nel caso analizzato), e la si trova all'indirizzo 0x10510A4:
La situazione è praticamente identica a quella analizzata in precedenza. Supponiamo che in input venga immesso il valore 1; EAX al termine dello spezzone analizzato conterrà il valore 1 e questo valore verrà utilizzato per calcolare lo spiazzamento moltiplicando il valore di input per 4 e sommando poi l'indirizzo di inizio della jump table. A quel punto non rimane che saltare all'effective address calcolato.
4. Switch case non ordinati
E' interessante anche osservare ciò che avviene modificando l'ordine degli switch case. In una situazione di questo tipo solitamente il compilatore riordina le posizioni nella jump table in accordo con i valori dei case. Per comprendere meglio, si consideri ora il codice modificato in questo modo:
Compilando con Microsoft compiler (il discorso è valido anche per GCC) abbiamo:
In particolare focalizzandosi su questa parte di codice:
si noterà che la jump table è differente: quello che, ad esempio, era prima in ultima posizione ora si trova in prima nella nump table ma, e questo è importante, mantenendo comunque l'indirizzo maggiore. In pratica 0x0003107F è il case 1, ma è l'ultimo dello switch, quindi occupa un indirizzo più alto.
Anche se il compilatore durante i differenti passaggi si occupa di ottimizzare il codice, è comunque meglio evitare switch case non ordinati.
5. Switch case con gap
In questo caso il codice prodotto da questi due compilatori (e dalle due versioni prese in esame) è differente, quindi l'analisi sarà differenziata.
5.1 Comportamento di cl.exe (Microsoft Compiler)
Altra situazione da prendere in considerazione è uno switch case che presenta "gap" tra i valori dei case. Questa è la situazione maggiormente delicata e complessa (e, se possibile, da evitare).
Ho modificato il codice in questo modo:
Questa è la situazione compilando con Microsoft Compiler:
L'analisi in questo caso sarà decisamente più approfondita.
Consideriamo le prime istruzioni dello screenshot (che non coincidono con le prime della funzione, ma è il frammento più importante):
[EBP-8] è una locazione sullo stack (è una variabile temporanea, una variabile locale) e contiene il valore digitato in input e letto all'inizio della funzione. Il valore viene copiato in una seconda variabile locale, [EBP-4], letto e memorizzato in EDX. Viene sottratto al valore EDX il numero 0x0A (10d); non è un valore scelto a caso, si tratta infatti del valore del primo case, il valore più piccolo. L'istruzione successiva memorizza nuovamente il valore alla locazione precedente.
il valore precedentemente sottratto viene testato, come negli esempi già precedentemente analizzati, per vedere se è maggiore di un determinato valore; in questo caso il valore è 0x3C (60d). E' stato scelto questo valore in quanto sottraendo il valore dell'ultimo caso al numero 10, otteniamo proprio come massimo 60. Quindi viene testato il valore contenuto in [EBP-4] e se maggiore (JA = Jump if Above) di 60 avviene il salto; la locazione di destinazione del salto è il default case.
La parte interessante arriva ora:
A questo punto viene assegnato al registro EAX il valore contenuto alla locazione [EBP-4]. Per seguire meglio tutti questi passaggi si immagini di aver immesso in input il valore 20; a questo valore è stato sottratto il valore 10d ottenendo quindi 10. Ora il numero ottenuto viene sommato ad un offset per calcolare un effective address. Sappiamo inoltre che viene considerato solo 1 singolo byte. Calcolando quindi 0x008310C0 + 0x0A (10d) = 0x008310CA. Osservando l'offset 0x008310C0 sarà chiaro il motivo:
Potrebbe non essere chiaro ad un primo sguardo, ma tutti i valori che vediamo indicano in pratica il case dello switch al quale accedere. Alla locazione calcolata troviamo infatti un byte, 01h. Questo valore viene quindi letto e trasferito in ECX. La situazione ora è chiara: ECX viene utilizzato, come nei casi precedenti, come un indice che verrà moltiplicato per 4 ed a cui verrà sommato un offset.
All'offset 0x008310A8 infatti troviamo la jump table, già vista precedentemente:
Proseguendo con l'esempio precedente ECX=1, otterremo questo Effective Address: [1*4+8310A8h] ovvero 8310ACh. Viene quindi letta la double word 0x00831059 ed è a questo indirizzo che avviene il salto. Guardando ora lo screenshot mostrato sopra notiamo che si tratta del secondo case (case 20).
Il codice sotto spoiler merita altre osservazioni: ci si potrebbe chiedere perchè tutte quelle informazioni. Osservando l'indirizzo 0x008310C0 si noterà il valore 0. Questo indica il primo case (valore in input 10). Il problema è che tra il valore del primo case ed il secondo c'è un gap di 9 numeri (11 - 19 compresi): il gap deve comunque essere considerato, ed è per questo motivo che vengono inseriti 9 byte con valore 05h. Ricordo che il valore 05h è il default case. Se dal valore all'indirizzo 0x008310CA (valore in input 20, è il case 2, quindi indice 1) sommiamo 29, otteniamo il case 3. Ancora il gap è stato colmato inserendo 29 byte con valore 5, così da saltare al default case e colmare la distanza tra i due case. Il discorso è analogo per tutti gli altri case che seguono.
Per non lasciare un altro dettaglio al caso: in tutti i case precedenti presente una CALL al medesimo indirizzo; l'istruzione precedente è una PUSH di un offset (che è l'inizio di una stringa, come si nota dallo screenshot) che è il parametro della funzione. In buona sostanza avviene la stampa della stringa.
5.2 Comportamento di GCC (MinGW)
Il codice prodotto da GCC presenta numerose differenze rispetto al codice prodotto da cl.exe.
Il codice pare sicuramente più chiaro, ma si nota la presenza di molti costrutti condizionali; in effetti si tratta di tanti IF per localizzare il case da eseguire.
Alla posizione [LOCAL.1] sullo stack si trova il valore inserito da tastiera (supponiamo 20d). Questo valore viene confrontato con 32h (50d), il valore mediano; se è uguale salta. Se è diverso, viene nuovamente confrontato con il valore 50d ma questa volta per verificare se è maggiore; se avviene il salto (all'indirizzo 0x00401408) un nuovo confronto viene attuato per capire se il valore è uguale a 55 oppure a 70 (se non coincide con nessuno, salta all'ultimo caso, il default case).
Insomma, come si sarà capito il codice questa volta non è esattamente ottimizzato; è quasi ciò che avremmo fatto utilizzando degli IF. L'aspetto che forse va fatto notare è che pare abbia applicato la ricerca dicotomica (o ricerca binaria): viene selezionato il valore centrale e poi si confronta il valore selezionato con quello da ricercare; se è minore si considerano gli elementi compreso tra il primo e quello centrale; se è maggiore si considerano gli elementi tra quello centrale e l'ultimo; e se è uguale si termina lì.
Il metodo è applicabile solo ad insiemi ordinati.
6. Gap consistenti tra i valori
Quando il gap inizia ad assumere una certa importanza, l'efficienza dello switch viene a meno, e diventa di fatto inutile se utilizzato allo scopo di ottenere prestazioni migliori rispetto ad else-if.
Con GCC la situazione è pressochè inalterata; utilizzando cl.exe si nota invece un peggioramento:
Il codice è molto simile a quello generato anche in precedenza da GCC.
7. Compilazione utilizzando flags
Come nel precedente articolo, anche in questo caso osserviamo ciò che avviene utilizzando le flags: utilizzeremo /O2 e -O2 rispettivamente per GCC e Microsoft Compiler.
7.1 Microsoft Compiler con /O2
Il codice è quello con gap:
La logica relativa al funzionamento permane, ma si trovano cambiamenti; ad esempio:
[LOCAL.0] è il valore in input. Guardando l'indirizzo 0x00AC1041 vediamo che la SUB è stata sostituita da una somma con un valore negativo.
La versione originale senza la presenza di gap tra i valori dei case coincide, con svariate ottimizzazioni, alla versione iniziale; la logica di funzionamento dello switch rimane tuttavia inalterata.
7.2 GCC con -O2
Considerando il codice che presenta gap, si potranno notare alcune differenze.
Sono stati disposti in modo differente i case e le condizioni, ma ancora una volta ci troviamo di fronte a molti "if". Anche nel caso di utilizzo di flags con GCC e senza introdurre gap tra i case, non ci sono particolari stravolgimenti. Le ottimizzazioni ci sono, ma riguardano il codice nell'insieme:
8. Considerazioni finali
Spero di essere riuscito a rendere il tutto leggibile ed allo stesso tempo aver mantenuto (o raggiunto) un livello medio-alto nell'esposizione dei concetti, così da non rendere l'articolo l'ennesimo reperibile in rete e che tratta gli stessi argomenti.
Come sempre in caso di domande o osservazioni non esitate a rispondere al topic.
Indice degli argomenti:
- 1. Prefazione
- 2. Introduzione
- 3. Lo switch
- 4. Switch case non ordinati
- 5. Switch case con gap
- 5.1 Comportamento di cl.exe (Microsoft Compiler)
- 5.2 Comportamento di GCC (MinGW)
- 6. Gap consistenti tra i valori
- 7. Compilazione utilizzando flags
- 7.1 Microsoft Compiler con /O2
- 7.2 GCC con -O2
- 8. Considerazioni finali
1. Prefazione
Nella prima parte - I costrutti condizionali: if e branch prediction (1/2) - mi sono occupato del costrutto condizionale IF. Scopo di questo articolo è trattare invece un altro costrutto condizionale, lo switch.
2. Introduzione
Nel corso degli anni più volte ho riscontrato il tentativo di porre if e switch sullo stesso piano, considerandoli intercambiabili, e solo "un modo diverso per fare la stessa cosa". Come vedremo - specialmente chi è relativamente nuovo nel campo - le cose non stanno proprio così.
Le osservazioni avverranno su eseguibili prodotti con i seguenti compilatori:
- Microsoft (R) C/C++ Optimizing Compiler versione 19.10.25019 per x86
- MinGw, g++ version 6.2.0
Come debugger ho scelto OllyDbg (v.2).
3. Lo switch
Ad alto livello lo switch si presenta in questo modo:
C:
#include <stdio.h>
int main()
{
int scelta;
printf("\nInserisci il numero dell'opzione desiderata:\n");
scanf("%d", &scelta);
switch(scelta)
{
case 1:
printf("Opzione 1\n");
break;
case 2:
printf("Opzione 2\n");
break;
case 3:
printf("Opzione 3\n");
break;
case 4:
printf("Opzione 4\n");
break;
case 5:
printf("Opzione 5\n");
break;
default:
printf("Opzioni non individuate\n");
}
}Perdonate la banalità dell'esempio in esame, però complicare inutilmente il codice considerando la finalità dell'articolo mi sembrava futile.
A basso livello si presenta in questo modo:
GCC
Codice:
CPU Disasm
Address Hex dump Command Comments
00401659 |. E8 2E110000 CALL <JMP.&msvcrt.scanf> ; \MSVCRT.scanf
0040165E |. 8B4424 1C MOV EAX,DWORD PTR SS:[LOCAL.1]
00401662 |. 83F8 05 CMP EAX,5
00401665 |. 77 4F JA SHORT 004016B6
00401667 |. 8B0485 E04040 MOV EAX,DWORD PTR DS:[EAX*4+4040E0]
0040166E \. FFE0 JMP EAXEAX contiene il valore inserito in input (valore contenuto in LOCAL.1, si tratta di una variabile locale; siamo sullo stack infatti e lo si nota dal segment override prefix, SS). Se il valore contenuto in JA è superiore di 5, avviene il salto all'indirizzo 0x004016B6 (il default case).
In caso contrario viene calcolato questo offset: EAX * 4 + 4040E0. L'offset è l'inizio di una jump table; in tal modo viene selezionato il case da eseguire senza effettuare ulteriori controlli.
Microsoft Compiler
Codice:
CPU Disasm
Address Hex dump Command Comments
01051030 |. 8955 FC MOV DWORD PTR SS:[EBP-4],EDX
01051033 |. 837D FC 04 CMP DWORD PTR SS:[EBP-4],4
01051037 |. 77 55 JA SHORT 0105108E
01051039 |. 8B45 FC MOV EAX,DWORD PTR SS:[EBP-4]
0105103C \. FF2485 A41005 JMP DWORD PTR DS:[EAX*4+10510A4]La jump table è appena sotto alla funzione analizzata (che è poi il main() nel caso analizzato), e la si trova all'indirizzo 0x10510A4:
Codice:
CPU Disasm
Address Hex dump Command Comments
010510A4 . \43100501 DD 01051043 ; Entry point
010510A8 . 52100501 DD 01051052 ; Entry point
010510AC . 61100501 DD 01051061 ; Entry point
010510B0 . 70100501 DD 01051070 ; Entry point
010510B4 . 7F100501 DD 0105107F ; Entry pointLa situazione è praticamente identica a quella analizzata in precedenza. Supponiamo che in input venga immesso il valore 1; EAX al termine dello spezzone analizzato conterrà il valore 1 e questo valore verrà utilizzato per calcolare lo spiazzamento moltiplicando il valore di input per 4 e sommando poi l'indirizzo di inizio della jump table. A quel punto non rimane che saltare all'effective address calcolato.
4. Switch case non ordinati
E' interessante anche osservare ciò che avviene modificando l'ordine degli switch case. In una situazione di questo tipo solitamente il compilatore riordina le posizioni nella jump table in accordo con i valori dei case. Per comprendere meglio, si consideri ora il codice modificato in questo modo:
C:
#include <stdio.h>
int main()
{
int scelta;
printf("\nInserisci il numero dell'opzione desiderata:\n");
scanf("%d", &scelta);
switch(scelta)
{
case 4:
printf("Opzione 4\n");
break;
case 5:
printf("Opzione 5\n");
break;
case 2:
printf("Opzione 2\n");
break;
case 3:
printf("Opzione 3\n");
break;
case 1:
printf("Opzione 1\n");
break;
default:
printf("Opzioni non individuate\n");
}
}Compilando con Microsoft compiler (il discorso è valido anche per GCC) abbiamo:
Codice:
CPU Disasm
Address Hex dump Command Comments
000310A4 . \7F100300 DD 0003107F ; Entry point
000310A8 . 61100300 DD 00031061 ; Entry point
000310AC . 70100300 DD 00031070 ; Entry point
000310B0 . 43100300 DD 00031043 ; Entry point
000310B4 . 52100300 DD 00031052 ; Entry pointsi noterà che la jump table è differente: quello che, ad esempio, era prima in ultima posizione ora si trova in prima nella nump table ma, e questo è importante, mantenendo comunque l'indirizzo maggiore. In pratica 0x0003107F è il case 1, ma è l'ultimo dello switch, quindi occupa un indirizzo più alto.
Anche se il compilatore durante i differenti passaggi si occupa di ottimizzare il codice, è comunque meglio evitare switch case non ordinati.
5. Switch case con gap
In questo caso il codice prodotto da questi due compilatori (e dalle due versioni prese in esame) è differente, quindi l'analisi sarà differenziata.
5.1 Comportamento di cl.exe (Microsoft Compiler)
Altra situazione da prendere in considerazione è uno switch case che presenta "gap" tra i valori dei case. Questa è la situazione maggiormente delicata e complessa (e, se possibile, da evitare).
Ho modificato il codice in questo modo:
C:
#include <stdio.h>
int main()
{
int scelta;
printf("\nInserisci il numero dell'opzione desiderata:\n");
scanf("%d", &scelta);
switch(scelta)
{
case 10:
printf("Opzione 10\n");
break;
case 20:
printf("Opzione 20\n");
break;
case 50:
printf("Opzione 50\n");
break;
case 55:
printf("Opzione 55\n");
break;
case 70:
printf("Opzione 70\n");
break;
default:
printf("Opzioni non individuate\n");
}
}Questa è la situazione compilando con Microsoft Compiler:
Consideriamo le prime istruzioni dello screenshot (che non coincidono con le prime della funzione, ma è il frammento più importante):
Codice:
CPU Disasm
Address Hex dump Command Comments
00831024 |. 8B4D F8 MOV ECX,DWORD PTR SS:[EBP-8]
00831027 |. 894D FC MOV DWORD PTR SS:[EBP-4],ECX
0083102A |. 8B55 FC MOV EDX,DWORD PTR SS:[EBP-4]
0083102D |. 83EA 0A SUB EDX,0A
00831030 |. 8955 FC MOV DWORD PTR SS:[EBP-4],EDX[EBP-8] è una locazione sullo stack (è una variabile temporanea, una variabile locale) e contiene il valore digitato in input e letto all'inizio della funzione. Il valore viene copiato in una seconda variabile locale, [EBP-4], letto e memorizzato in EDX. Viene sottratto al valore EDX il numero 0x0A (10d); non è un valore scelto a caso, si tratta infatti del valore del primo case, il valore più piccolo. L'istruzione successiva memorizza nuovamente il valore alla locazione precedente.
Codice:
CPU Disasm
Address Hex dump Command Comments
00831033 |. 837D FC 3C CMP DWORD PTR SS:[EBP-4],3C
00831037 |.- 77 5C JA SHORT 00831095il valore precedentemente sottratto viene testato, come negli esempi già precedentemente analizzati, per vedere se è maggiore di un determinato valore; in questo caso il valore è 0x3C (60d). E' stato scelto questo valore in quanto sottraendo il valore dell'ultimo caso al numero 10, otteniamo proprio come massimo 60. Quindi viene testato il valore contenuto in [EBP-4] e se maggiore (JA = Jump if Above) di 60 avviene il salto; la locazione di destinazione del salto è il default case.
La parte interessante arriva ora:
Codice:
CPU Disasm
Address Hex dump Command Comments
00831039 |. 8B45 FC MOV EAX,DWORD PTR SS:[EBP-4]
0083103C |. 0FB688 C01083 MOVZX ECX,BYTE PTR DS:[EAX+8310C0] ; Switch (cases 0..5, 6 exits)
00831043 |.- FF248D A81083 JMP DWORD PTR DS:[ECX*4+8310A8]A questo punto viene assegnato al registro EAX il valore contenuto alla locazione [EBP-4]. Per seguire meglio tutti questi passaggi si immagini di aver immesso in input il valore 20; a questo valore è stato sottratto il valore 10d ottenendo quindi 10. Ora il numero ottenuto viene sommato ad un offset per calcolare un effective address. Sappiamo inoltre che viene considerato solo 1 singolo byte. Calcolando quindi 0x008310C0 + 0x0A (10d) = 0x008310CA. Osservando l'offset 0x008310C0 sarà chiaro il motivo:
Codice:
CPU Disasm
Address Hex dump Command Comments
008310C0 . 00 DB 00
008310C1 . 05 DB 05
008310C2 . 05 DB 05
008310C3 . 05 DB 05
008310C4 . 05 DB 05
008310C5 . 05 DB 05
008310C6 . 05 DB 05
008310C7 . 05 DB 05
008310C8 . 05 DB 05
008310C9 . 05 DB 05
008310CA . 01 DB 01
008310CB . 05 DB 05
008310CC . 05 DB 05
008310CD . 05 DB 05
008310CE . 05 DB 05
008310CF . 05 DB 05
008310D0 . 05 DB 05
008310D1 . 05 DB 05
008310D2 . 05 DB 05
008310D3 . 05 DB 05
008310D4 . 05 DB 05
008310D5 . 05 DB 05
008310D6 . 05 DB 05
008310D7 . 05 DB 05
008310D8 . 05 DB 05
008310D9 . 05 DB 05
008310DA . 05 DB 05
008310DB . 05 DB 05
008310DC . 05 DB 05
008310DD . 05 DB 05
008310DE . 05 DB 05
008310DF . 05 DB 05
008310E0 . 05 DB 05
008310E1 . 05 DB 05
008310E2 . 05 DB 05
008310E3 . 05 DB 05
008310E4 . 05 DB 05
008310E5 . 05 DB 05
008310E6 . 05 DB 05
008310E7 . 05 DB 05
008310E8 . 02 DB 02
008310E9 . 05 DB 05
008310EA . 05 DB 05
008310EB . 05 DB 05
008310EC . 05 DB 05
008310ED . 03 DB 03
008310EE . 05 DB 05
008310EF . 05 DB 05
008310F0 . 05 DB 05
008310F1 . 05 DB 05
008310F2 . 05 DB 05
008310F3 . 05 DB 05
008310F4 . 05 DB 05
008310F5 . 05 DB 05
008310F6 . 05 DB 05
008310F7 . 05 DB 05
008310F8 . 05 DB 05
008310F9 . 05 DB 05
008310FA . 05 DB 05
008310FB . 05 DB 05
008310FC . 04 DB 04Potrebbe non essere chiaro ad un primo sguardo, ma tutti i valori che vediamo indicano in pratica il case dello switch al quale accedere. Alla locazione calcolata troviamo infatti un byte, 01h. Questo valore viene quindi letto e trasferito in ECX. La situazione ora è chiara: ECX viene utilizzato, come nei casi precedenti, come un indice che verrà moltiplicato per 4 ed a cui verrà sommato un offset.
All'offset 0x008310A8 infatti troviamo la jump table, già vista precedentemente:
Codice:
CPU Disasm
Address Hex dump Command Comments
008310A8 . \4A108300 DD 0083104A
008310AC . 59108300 DD 00831059
008310B0 . 68108300 DD 00831068
008310B4 . 77108300 DD 00831077
008310B8 . 86108300 DD 00831086
008310BC . 95108300 DD 00831095Proseguendo con l'esempio precedente ECX=1, otterremo questo Effective Address: [1*4+8310A8h] ovvero 8310ACh. Viene quindi letta la double word 0x00831059 ed è a questo indirizzo che avviene il salto. Guardando ora lo screenshot mostrato sopra notiamo che si tratta del secondo case (case 20).
Il codice sotto spoiler merita altre osservazioni: ci si potrebbe chiedere perchè tutte quelle informazioni. Osservando l'indirizzo 0x008310C0 si noterà il valore 0. Questo indica il primo case (valore in input 10). Il problema è che tra il valore del primo case ed il secondo c'è un gap di 9 numeri (11 - 19 compresi): il gap deve comunque essere considerato, ed è per questo motivo che vengono inseriti 9 byte con valore 05h. Ricordo che il valore 05h è il default case. Se dal valore all'indirizzo 0x008310CA (valore in input 20, è il case 2, quindi indice 1) sommiamo 29, otteniamo il case 3. Ancora il gap è stato colmato inserendo 29 byte con valore 5, così da saltare al default case e colmare la distanza tra i due case. Il discorso è analogo per tutti gli altri case che seguono.
Per non lasciare un altro dettaglio al caso: in tutti i case precedenti presente una CALL al medesimo indirizzo; l'istruzione precedente è una PUSH di un offset (che è l'inizio di una stringa, come si nota dallo screenshot) che è il parametro della funzione. In buona sostanza avviene la stampa della stringa.
5.2 Comportamento di GCC (MinGW)
Il codice prodotto da GCC presenta numerose differenze rispetto al codice prodotto da cl.exe.
Codice:
CPU Disasm
Address Hex dump Command Comments
004013EE |. 8B4424 1C MOV EAX,DWORD PTR SS:[LOCAL.1]
004013F2 |. 83F8 32 CMP EAX,32
004013F5 |. 74 39 JE SHORT 00401430
004013F7 |. 83F8 32 CMP EAX,32
004013FA |. 7F 0C JG SHORT 00401408
004013FC |. 83F8 0A CMP EAX,0A
004013FF |. 74 13 JE SHORT 00401414
00401401 |. 83F8 14 CMP EAX,14
00401404 |. 74 1C JE SHORT 00401422
00401406 |. EB 52 JMP SHORT 0040145A
00401408 |> 83F8 37 CMP EAX,37
0040140B |. 74 31 JE SHORT 0040143E
0040140D |. 83F8 46 CMP EAX,46
00401410 |. 74 3A JE SHORT 0040144C
00401412 |. EB 46 JMP SHORT 0040145A
00401414 |> C70424 953040 MOV DWORD PTR SS:[LOCAL.8],OFFSET 004030 ; /string => "Opzione 10"
0040141B |. E8 E0080000 CALL <JMP.&msvcrt.puts> ; \MSVCRT.puts
00401420 |. EB 44 JMP SHORT 00401466
00401422 |> C70424 A03040 MOV DWORD PTR SS:[LOCAL.8],OFFSET 004030 ; /string => "Opzione 20"
00401429 |. E8 D2080000 CALL <JMP.&msvcrt.puts> ; \MSVCRT.puts
0040142E |. EB 36 JMP SHORT 00401466
00401430 |> C70424 AB3040 MOV DWORD PTR SS:[LOCAL.8],OFFSET 004030 ; /string => "Opzione 50"
00401437 |. E8 C4080000 CALL <JMP.&msvcrt.puts> ; \MSVCRT.puts
0040143C |. EB 28 JMP SHORT 00401466
0040143E |> C70424 B63040 MOV DWORD PTR SS:[LOCAL.8],OFFSET 004030 ; /string => "Opzione 55"
00401445 |. E8 B6080000 CALL <JMP.&msvcrt.puts> ; \MSVCRT.puts
0040144A |. EB 1A JMP SHORT 00401466
0040144C |> C70424 C13040 MOV DWORD PTR SS:[LOCAL.8],OFFSET 004030 ; /string => "Opzione 70"
00401453 |. E8 A8080000 CALL <JMP.&msvcrt.puts> ; \MSVCRT.puts
00401458 |. EB 0C JMP SHORT 00401466
0040145A |> C70424 CC3040 MOV DWORD PTR SS:[LOCAL.8],OFFSET 004030 ; /string => "Opzioni non individuate"
00401461 |. E8 9A080000 CALL <JMP.&msvcrt.puts> ; \MSVCRT.putsAlla posizione [LOCAL.1] sullo stack si trova il valore inserito da tastiera (supponiamo 20d). Questo valore viene confrontato con 32h (50d), il valore mediano; se è uguale salta. Se è diverso, viene nuovamente confrontato con il valore 50d ma questa volta per verificare se è maggiore; se avviene il salto (all'indirizzo 0x00401408) un nuovo confronto viene attuato per capire se il valore è uguale a 55 oppure a 70 (se non coincide con nessuno, salta all'ultimo caso, il default case).
Insomma, come si sarà capito il codice questa volta non è esattamente ottimizzato; è quasi ciò che avremmo fatto utilizzando degli IF. L'aspetto che forse va fatto notare è che pare abbia applicato la ricerca dicotomica (o ricerca binaria): viene selezionato il valore centrale e poi si confronta il valore selezionato con quello da ricercare; se è minore si considerano gli elementi compreso tra il primo e quello centrale; se è maggiore si considerano gli elementi tra quello centrale e l'ultimo; e se è uguale si termina lì.
Il metodo è applicabile solo ad insiemi ordinati.
6. Gap consistenti tra i valori
Quando il gap inizia ad assumere una certa importanza, l'efficienza dello switch viene a meno, e diventa di fatto inutile se utilizzato allo scopo di ottenere prestazioni migliori rispetto ad else-if.
C:
#include <stdio.h>
int main()
{
int scelta;
printf("\nInserisci il numero dell'opzione desiderata:\n");
scanf("%d", &scelta);
switch(scelta)
{
case 10:
printf("Opzione 10\n");
break;
case 50:
printf("Opzione 50\n");
break;
case 150:
printf("Opzione 150\n");
break;
case 155:
printf("Opzione 155\n");
break;
case 270:
printf("Opzione 270\n");
break;
default:
printf("Opzioni non individuate\n");
}
}Con GCC la situazione è pressochè inalterata; utilizzando cl.exe si nota invece un peggioramento:
7. Compilazione utilizzando flags
Come nel precedente articolo, anche in questo caso osserviamo ciò che avviene utilizzando le flags: utilizzeremo /O2 e -O2 rispettivamente per GCC e Microsoft Compiler.
7.1 Microsoft Compiler con /O2
Il codice è quello con gap:
Codice:
CPU Disasm
Address Hex dump Command Comments
00AC103A |. 8B4424 0C MOV EAX,DWORD PTR SS:[LOCAL.0]
00AC103E |. 83C4 0C ADD ESP,0C
00AC1041 |. 83C0 F6 ADD EAX,-0A ; Switch (cases A..46, 6 exits)[LOCAL.0] è il valore in input. Guardando l'indirizzo 0x00AC1041 vediamo che la SUB è stata sostituita da una somma con un valore negativo.
La versione originale senza la presenza di gap tra i valori dei case coincide, con svariate ottimizzazioni, alla versione iniziale; la logica di funzionamento dello switch rimane tuttavia inalterata.
7.2 GCC con -O2
Considerando il codice che presenta gap, si potranno notare alcune differenze.
8. Considerazioni finali
Spero di essere riuscito a rendere il tutto leggibile ed allo stesso tempo aver mantenuto (o raggiunto) un livello medio-alto nell'esposizione dei concetti, così da non rendere l'articolo l'ennesimo reperibile in rete e che tratta gli stessi argomenti.
Come sempre in caso di domande o osservazioni non esitate a rispondere al topic.
