strlen veloce con le operazioni bit

Question

Ho trovato questo codice

int strlen_my(const char *s) 
{ 
    int len = 0; 
    for(;;) 
    { 
     unsigned x = *(unsigned*)s; 
     if((x & 0xFF) == 0) return len; 
     if((x & 0xFF00) == 0) return len + 1; 
     if((x & 0xFF0000) == 0) return len + 2; 
     if((x & 0xFF000000) == 0) return len + 3; 
     s += 4, len += 4; 
    } 
} 

Sono molto interessato a sapere come funziona. Qualcuno può spiegare come funziona?

Answer 1

Un AND bit a bit recupera il bit pattern dall'altro operando. Significato, 10101 & 11111 = 10101. Se il risultato di questo bit AND è 0, allora sappiamo che l'altro operando era 0. Un risultato di 0 quando ANDing di un singolo byte con 0xFF (uno) indicherà un byte NULL.

Il codice stesso controlla ogni byte dell'array char in partizioni a quattro byte. NOTA: Questo codice non è portatile; su un'altra macchina o compilatore, un int unsigned potrebbe essere superiore a 4 byte. Probabilmente sarebbe meglio usare il tipo di dati uint32_t per garantire numeri interi senza segno a 32 bit.

La prima cosa da notare è che su una macchina little-endian, i byte che costituiscono l'array di caratteri verranno letti in un tipo di dati senza segno in ordine inverso; vale a dire, se i quattro byte all'indirizzo corrente corrispondono al modello di bit corrispondente a abcd, la variabile senza segno conterrà il modello di bit corrispondente a dcba.

Il secondo è che una costante di numero esadecimale in C restituisce un numero int-sized con i byte specificati all'estremità inferiore del modello di bit. Significato, 0xFF è in realtà 0x000000FF durante la compilazione con 4 byte int. 0xFF00 è 0x0000FF00. E così via.

Quindi il programma cerca fondamentalmente il carattere NULL nelle quattro posizioni possibili. Se non c'è alcun carattere NULL nella partizione corrente, avanza al successivo slot a quattro byte.

Prendere il char array abcdef per un esempio. In C, le costanti di stringa avranno sempre terminatori nulli alla fine, quindi c'è un byte 0x00 alla fine di quella stringa.

Funzionerà come segue:

Leggi "abcd" in unsigned int x:

x: 0x64636261 [ASCII representations for "dcba"] 

Controllare ogni byte per un terminatore null:

0x64636261 
& 0x000000FF 
    0x00000061 != 0, 

    0x64636261 
& 0x0000FF00 
    0x00006200 != 0, 

e verificare gli altri due posizioni; non ci sono terminatori nulli in questa partizione a 4 byte, quindi vai alla partizione successiva.

Leggi "ef" in unsigned int x:

x: 0xBF006665 [ASCII representations for "fe"] 

Nota byte 0xBF; questo è oltre la lunghezza della stringa, quindi stiamo leggendo nella spazzatura dallo stack di runtime. Potrebbe essere qualsiasi cosa. Su una macchina che non consente accessi non allineati, questo si bloccherà se la memoria dopo la stringa non è allineata a 1 byte. Se nella stringa ci fosse solo un carattere, dovremmo leggere due byte extra, quindi l'allineamento della memoria adiacente al char array dovrebbe essere allineato a 2 byte.

Controllare ogni byte per un terminatore null:

0xBF006665 
& 0x000000FF 
    0x00000065 != 0, 

    0xBF006665 
& 0x0000FF00 
    0x00006600 != 0, 

    0xBF006665 
& 0x00FF0000 
    0x00000000 == 0 !!! 

così torniamo len + 2; len era 4 poiché lo abbiamo incrementato una volta per 4, quindi restituiamo 6, che è effettivamente la lunghezza della stringa.

Answer 2

Rileva se alcuni bit sono impostati su un byte specifico su una macchina little-endian. Dato che stiamo controllando solo un singolo byte (poiché tutti i nibbles, 0 o 0xF, sono raddoppiati) e capita di essere l'ultima posizione di byte (poiché la macchina è little-endian e il modello di byte per i numeri è quindi invertito) possiamo immediatamente sapere quale byte contiene NUL.

Answer 3

Il ciclo prende 4 byte del char array per ogni iterazione. Le quattro istruzioni if ​​vengono utilizzate per determinare se la stringa è finita, usando la maschera di bit con l'operatore AND per leggere lo stato dell'elemento i-esimo della sottostringa selezionata.

Answer 4

Commercia un comportamento indefinito (accessi non allineati, 75% di probabilità di accesso oltre la fine dell'array) per una velocità molto discutibile (è molto probabilmente anche più lento). E non è conforme allo standard, perché restituisce int anziché size_t. Anche se gli accessi non allineati sono consentiti sulla piattaforma, possono essere molto più lenti degli accessi allineati.

Inoltre, non funziona sui sistemi big-endian o se unsigned non è a 32 bit. Per non parlare della maschera multipla e delle operazioni condizionali.

Detto:

Viene verificata 4 byte di 8 bit alla volta caricando un unsigned (che non è nemmeno garantito per più di 16 bit). Quando uno qualsiasi dei byte contiene il '\0' -terminatore, restituisce la somma della lunghezza corrente più la posizione di quel byte. Altrimenti incrementa la lunghezza corrente per il numero di byte testati in parallelo (4) e ottiene il successivo unsigned.

Il mio consiglio: cattivo esempio di ottimizzazione più troppe incertezze/insidie. E 'probabile che non ancora più veloce - solo il profilo it contro la versione standard:

size_t strlen(restrict const char *s) 
{ 
    size_t l = 0; 
    while (*s++) 
     l++; 
    return l; 
} 

Ci potrebbe essere un modo per utilizzare speciali vettore-istruzioni, ma a meno che non si può dimostrare questo è una funzione critica, si dovrebbe lasciare questo al compilatore - alcuni possono srotolare/accelerare questi loop molto meglio.

Answer 5

Il codice "funziona" tentando di leggere 4 byte alla volta assumendo che la stringa sia disposta e accessibile come una serie di int. Il codice legge il primo int e quindi ogni byte a sua volta, verificando se è il carattere null. In teoria, il codice che funziona con int verrà eseguito più velocemente di 4 singole operazioni char.

Ma ci sono problemi:

allineamento è un problema: per esempio *(unsigned*)s potrebbe seg-fault.

Endian è un problema con if((x & 0xFF) == 0) non potrebbe ottenere il byte all'indirizzo s

s += 4 è un problema in quanto sizeof(int) può differire da 4.

tipi array può superare int gamma, meglio usare size_t.

---

Un tentativo di correggere queste difficoltà.

#include <stddef.h> 
#include <stdio.h> 

static inline aligned_as_int(const char *s) { 
    max_align_t mat; // C11 
    uintptr_t i = (uintptr_t) s; 
    return i % sizeof mat == 0; 
} 

size_t strlen_my(const char *s) { 
    size_t len = 0; 
    // align 
    while (!aligned_as_int(s)) { 
    if (*s == 0) return len; 
    s++; 
    len++; 
    } 
    for (;;) { 
    unsigned x = *(unsigned*) s; 
    #if UINT_MAX >> CHAR_BIT == UCHAR_MAX 
     if(!(x & 0xFF) || !(x & 0xFF00)) break; 
     s += 2, len += 2; 
    #elif UINT_MAX >> CHAR_BIT*3 == UCHAR_MAX 
     if (!(x & 0xFF) || !(x & 0xFF00) || !(x & 0xFF0000) || !(x & 0xFF000000)) break; 
     s += 4, len += 4; 
    #elif UINT_MAX >> CHAR_BIT*7 == UCHAR_MAX 
     if ( !(x & 0xFF) || !(x & 0xFF00) 
      || !(x & 0xFF0000) || !(x & 0xFF000000) 
      || !(x & 0xFF00000000) || !(x & 0xFF0000000000) 
      || !(x & 0xFF000000000000) || !(x & 0xFF00000000000000)) break; 
     s += 8, len += 8; 
    #else 
     #error TBD code 
    #endif 
    } 
    while (*s++) { 
    len++; 
    } 
    return len; 
} 

Answer 6

Tutte le proposte sono più lente di un semplice strlen().

Il motivo è che non riducono il numero di confronti e solo uno si occupa dell'allineamento.

Controllare la proposta strlen() da Torbjorn Granlund (tege@sics.se) e Dan Sahlin (dan@sics.se) nella rete. Se sei su una piattaforma a 64 bit, questo aiuta davvero ad accelerare le cose.