Articolo pubblicato su CP nello speciale "Programmazione a basso livello"

 

Evoluzione di una funzione da 16 a 32 bit

di Roberto Bianchi

 

 

L'introduzione su larga scala della programmazione a 32 bit, avvenuta con Windows 95, segna due grosse novità per chi scrive codice a basso livello: la possibilità di disporre dell'intero set di registri della CPU e l'utilizzo del modello di indirizzamento flat che non prevede più segmenti e offset. Per comprendere i cambiamenti prodotti dall'uso nativo dei processori a 32 bit analizzeremo le diverse implementazioni che ha avuto una delle più usate funzioni della libreria runtime del C: strlen(). Lo studio partirà dal compilatore Microsoft C 6.00 per MS-DOS e arriverà fino alla più recente versione del Visual C++ 5.0.

 

Cosa fa strlen()

La funzione strlen()  serve per determinare la lunghezza di una stringa di testo. Nel linguaggio C le stringhe sono memorizzate senza nessuna informazione sulla lunghezza; in compenso, però, sono terminate da un byte di valore zero (il cosiddetto null byte) che ne indica la fine. La Figura 1 mostra l'esempio di una tale stringa in memoria.

Le stringhe terminate da un carattere nullo si dicono anche ASCIIZ. Il compito di strlen() , quindi, è determinare quanti caratteri vi sono fino al primo carattere null.

Nel caso della stringa di Figura 1 la funzione strlen() deve contare quanti caratteri ASCII ci sono tra il primo carattere (S posto all'indirizzo 400h) e il terminatore '\0' in 40Fh.

Vediamo ora la pseudo-codifica di strlen():

 

int strlen(const char * pStringa)

{

  int Lunghezza = 0;

  while(*pStringa++)

    ++Lunghezza;  

  return Lunghezza;

}

 

La funzione riceve dal programma un puntatore a dei caratteri, dichiara una variabile contatore e individua attraverso un ciclo il primo carattere ASCII 0. Ad ogni passaggio viene incrementato il puntatore e se il test ha esito positivo, viene incrementata la lunghezza. Nell'esempio di Figura 1 all'ingresso del ciclo pStringa contiene l'indirizzo 400h. All'uscita, il valore 40Fh e la lunghezza è uguale a 15. Fin qui nessuna sorpresa, ma i 16 e i 32 bit cosa c'entrano? Vediamo quindi come effettivamente lavorano le funzioni della libreria runtime del C.

 

Versioni a 16 bit

strlen() è una funzione semplice ma la sua ottimizzazione è cruciale visto la frequenza con cui la si utilizza. Per questo conviene sempre scriverla in Assembly, come fanno il Microsoft C 6.0  ed il Symantec C/C++ 6.0. Il seguente frammento contiene un estratto del codice Assembly usato dal compilatore Microsoft C 6.0. La parte di codice che carica in ES:DI l'indirizzo della stringa è stata omessa.

 

xor AX,AX                      

mov CX,0FFFFh               

repne scasb

not CX

dec CX

xchg  AX,CX

 

Per prima cosa viene azzerato il registro AX in modo che il registro AL (i primi 8 bit di AX) contenga 0, cioè il byte da trovare. Il registro CX viene impostato con 0xFFFF (cioè 65535) che limita a 64 KB la dimensione massima della stringa. Questa limitazione è dovuta ai 16 bit del registro CX. Le istruzioni repne e scasb eseguono la scansione nella stringa puntata da ES:DI fino a che non viene trovato un valore uguale a quello contenuto in AL. Uscendo dal loop DI punterà al byte nullo mentre CX conterrà FFFFh  meno il numero dei caratteri elaborati (incluso il null byte).

L' istruzione not CX determina il numero dei caratteri attraversati durante la scansione. Il not di fatto esegue FFFFh - CX. Il contenuto di CX deve essere decrementato ancora di un carattere (il terminatore). La lunghezza della stringa viene quindi spostata in AX, pronta per essere restituita al programma chiamante. Il valore restituito è ovviamente a 16 bit (una WORD del microprocessore).

Nella versione Symantec le cose non cambiano molto.

 

clr AX           

mov CX,-1  

cld

repne scasb

mov AX,CX

not AX     

dec AX

 

La macro clr azzera il contenuto di AX in modo che nel registro AL ci sia  0, si imposta la massima dimensione della stringa e si inizia la scansione. Rispetto alla versione Microsoft cambia l'ordine delle tre istruzioni che calcolano la lunghezza della stringa a partire dal contenuto di CX.

Lo stesso algoritmo è presente nel compilatore Visual C++ 1.52. Due piccole note a margine:

 

1)       L'istruzione cld (clear direction flag) assicura che l'elaborazione della stringa avvenga dall'indirizzo basso a quello alto. L'indice DI infatti viene incrementato se il flag di direzione è 0 oppure decrementato se il flag è 1.

2)       L'utilizzo dell'istruzione xchg penalizza di 1 ciclo di clock la funzione Microsoft rispetto a quella Symantec.

 

La limitazione a 64 KB della lunghezza delle stringhe è dovuta ai 16 bit del registro CX e al  sistema di indirizzamento segmentato in cui l'indice DI è anch'esso a 16 bit. Inoltre, il microprocessore durante il ciclo repne scasb preleva dalla RAM solo otto bit alla volta, impiegando sette cicli di clock su un 486. Una volta trovato il byte nullo il calcolo della lunghezza è praticamente immediato.

 

Versioni a 32 bit

Con il compilatore Visual C++ 4.0 (solo a 32 bit) compare la funzione strlen() che sfrutta appieno i 32 bit dei registri. Ecco qui  il frammento più interessante del codice di strlen() distribuito da Microsoft.

 

1) main_loop:

2)   mov     eax,dword ptr [ecx]

3)   mov     edx,7efefeffh

4)   add     edx,eax

5)   xor     eax,-1

6)   xor     eax,edx

7)   add     ecx,4

8)   test    eax,81010100h

9)   je      short main_loop

10)  ; nessun byte trovato

11)  mov     eax,[ecx - 4]

12)  test    al,al                

13)  je      short byte_0

14)  test    ah,ah                

15)  je      short byte_1

16)  test    eax,00ff0000h        

17)  je      short byte_2

18)  test    eax,0ff000000h       

19)  je      short byte_3

20)  jmp     short main_loop

 

La numerazione a sinistra ha lo scopo di semplificare la lettura. Anche in questo caso  si assume che l'indirizzo della stringa sia già caricato in EDI.

Il problema fondamentale che nasce dall'accesso a 32 bit alla RAM è che bisogna ogni volta determinare se tra i quattro byte prelevati vi è il null. La riga 2 preleva 32 bit di dati dalla RAM. Le righe dalla 3 alla 8  (riga 7 esclusa) implementano un algoritmo che sfruttando le proprietà del sistema binario è in grado di determinare se c'è un byte di valore 0 all'interno della DWORD contenuta in EAX. In particolare  l'algoritmo esegue il calcolo

 

y = AND(XOR(FFFFFFFFh - x, x + 7EFEFEFFh), 81010100h)

 

dove i valori 7EFEFEFFh e 81010100 sono opachi. Ciò che importa è che la loro somma sia FFFFFFFFh. Il salto alla riga 9 viene eseguito solo se y=0, cioè se non è stato trovato nessun carattere ASCII 0 nella DWORD. Se y>0 vi è almeno un null byte tra i quattro prelevati dalla RAM. Le righe dalla 11 alla 19 determinano la posizione del null all’interno della DWORD. Questa funzione è più lunga e complessa delle precedenti, ma le prestazioni sono cambiate?

 

Ottimizzare strlen()

Per capire se e come ottimizzare strlen() a 32 bit proviamo a riscrivere a 32 bit le funzioni viste a 16. Tutti i sorgenti sono contenuti nel file allegato test.c. Le funzioni sono:

 

·         Nuova_strlenC1()

·         Nuova_strlen1()

·         Nuova_strlen2()

·         Nuova_strlen3()

·         Nuova_strlen4()

 

Nuova_strlenC1() è l'implementazione della pseudo-funzione presentata all'inizio dell'articolo. Rispetto al pseudo-codice di sopra gli int sono diventati long in modo da puntare fino a 4 GB di RAM.

Nuova_strlen1() è il semplice porting a 32 bit delle versioni Microsoft e Symantec viste in precedenza. Il metodo con cui si prendono i byte dalla RAM e si ricerca il null byte è rimasto invariato.

Nuova_strlen2() è identica alla precedente a meno del fatto che sono prelevati due byte per ogni accesso alla RAM e quindi vi è una ricerca del null byte all'interno di una WORD.

Nuova_strlen3() è la funzione di runtime del VC++ 4.x in cui manca il particolare algoritmo per la determinazione della presenza di un null byte all'interno dei dati prelevati dalla memoria. In questa funzione si confrontano ogni volta tutti i 4 byte prelevati dalla RAM.

Nuova_strlen4() è stata sviluppata in modo di utilizzare le istruzioni di elaborazione delle stringhe dei processori x86, quali repne scasd. Questa funzione richiede che la stringa sia terminata da sette terminatori, in modo che l'istruzione repne scasd sia sempre in grado di trovare una DWORD a zero prescindere dalla posizione nel primo null byte.

 

Mix di Assembly e C

Per inserire codice Assembly in sorgenti C occorre incapsulare il codice Assembly in una funzione C che funga da contenitore e che si occupi solo di ricevere i parametri e di restituire valori. Ecco qui a seguito la funzione Nuova_strlen1() estratta dal file test.c:

 

long Nuova_strlen1( char *string )

{

  long i=0;

  _asm {

    mov ecx, -1

    xor eax, eax

    mov edi, [string]

    repne scasb 

    not ecx

    dec ecx

    mov i,   ecx

  }

  return i;

}

 

Subito dopo la dichiarazione delle variabili locali si apre un blocco _asm{} in cui è possibile inserire il codice Assembly. È possibile utilizzare direttamente i dati C nel codice Assembly. Ovviamente l'ampiezza dei  dati in questione deve concordare con l'ampiezza del registro o l'uso del dato che la riga esegue.

È buona norma salvare e ripristinare lo stato dei registri EDI, ESI, EBP, ESP e di tutti i registri di segmento. In realtà se si utilizza il compilatore Visual C++ 1.52 o superiore, si può lasciare tranquillamente a quest'ultimo il compito di inserire all'occorrenza le sequenze di istruzioni push e pop.

 

Il programma di test

Ora è tempo di costruire il programma di test delle varie versioni di strlen() viste in precedenza. Essendo lo scopo del programma quello di misurare il tempo impiegato da ogni funzione, bisognerà innanzi tutto munirsi di una specie di cronometro che non alteri in modo significativo il tempo impiegato dalla funzione tipo strlen() durante la determinazione della lunghezza della stringa. Una volta determinata la lunghezza della stringa, il programma dovrà visualizzare il tempo impiegato dalla funzione. In allegato troverete il sorgente del programma di test completo di makefile per Visual C++ 5.0 e i listati contenente le versioni precedenti di versioni di strlen() sviluppate da Microsoft e Symantec.

 

Conclusioni

Per meglio evidenziare le caratteristiche delle funzioni su cui abbiamo lavorato, ho riportato i risultati ottenuti tramite il programma Test in una tabella (Tabella 1) contenente i secondi richiesti per trovare (100 e 1000 volte) la lunghezza di una stringa di 2MB. Nella tabella sono inoltre riportati l'ampiezza dell' indirizzo/singolo dato prelevato dalla RAM e la dimensione del codice della funzione che è arrotondata al paragrafo (16 byte). I tempi riportati in tabella sono stati rilevati su un PC con Pentium da 133 Mhz, 16 MByte di RAM e con l’eseguibile ottenuto dal compilatore Visual C++ 5.0.

Esaminando i risultati di Tabella 1, risulta evidente che la versione a 32 bit di strlen() è la più veloce ma è anche la più lunga. Al contrario Nuova_strlenC1() è tra le più lente ma è la più corta. Nuova_strlen3() ha prestazioni intermedie tra le due funzioni precedenti e rappresenta quindi un buon compromesso tra le due.

Personalmente io non ho dubbi, se devo scrivere un programma per WINDOWS preferisco sacrificare dello spazio in favore alla velocità d’esecuzione ma a volte ci sono situazioni in cui è necessario avere un codice molto compatto. Il mio consiglio è questo: se preferite la velocità o non volete avere niente a che fare con l’ottimizzazione del programma usate strlen(), se avete bisogno di spazio usate  Nuova_strlenC1() e se siete indecisi tra le due usate Nuova_strlen3(). Inoltre se ci tenete in modo particolare all’ottimizzazione del codice non fidatevi ciecamente di ciò che fa il compilatore.

 

Roberto Bianchi lavora nel campo dell’informatica da diversi anni, occupandosi di programmazione a basso ed alto livello su PC, Reti e Sistemi dipartimentali.