Cómo funciona la implementación de glibc strlen()

string performance

Question

Esta pregunta ya tiene una respuesta aquí:

• strlen rendimiento implementación 3 respuestas

El strlen() de K&R toma solo unas pocas líneas.

int strlen(char *s)
{
    char *p = s;
    while (*p != ''/0'')
        p++;
    return p - s;
}

Pero la versión glibc es mucho más larga. Para simplificar, strlen() todos los comentarios y la implementación de 64 bits, la versión extraída de strlen() parece a esto:

size_t strlen(const char *str)
{
    const char *char_ptr;
    const unsigned long int *longword_ptr;
    unsigned long int longword, magic_bits, himagic, lomagic;

    for (char_ptr = str; ((unsigned long int) char_ptr 
             & (sizeof (longword) - 1)) != 0; ++char_ptr)
       if (*char_ptr == ''/0'')
           return char_ptr - str;

    longword_ptr = (unsigned long int *) char_ptr;

    himagic = 0x80808080L;
    lomagic = 0x01010101L;

    for (;;)
    { 
        longword = *longword_ptr++;

        if (((longword - lomagic) & himagic) != 0)
        {
            const char *cp = (const char *) (longword_ptr - 1);

            if (cp[0] == 0)
                return cp - str;
            if (cp[1] == 0)
                return cp - str + 1;
            if (cp[2] == 0)
                return cp - str + 2;
            if (cp[3] == 0)
                return cp - str + 3;
        }
    }
}

Con la ayuda del comentario muy útil (haga clic aquí ), obtuve la mayor parte de cómo funciona esto. En lugar de buscar ''/0'' byte ''/0'' byte, el glibc strlen() verifica cada palabra (4 bytes en la máquina de 32 bits, 8 bytes en la máquina de 64 bits). De esta manera, cuando la cadena es relativamente larga, se puede mejorar el rendimiento.

Comprueba los primeros caracteres leyendo byte a byte, hasta que char_ptr se alinee en un límite de longword . Luego usa un bucle para verificar si la longword tiene bytes con todos los ceros. Si existe, marque qué byte y devuelva el resultado.

La parte que no entiendo es, ¿cómo comprueba esto si un byte en longword es todo ceros?

if (((longword - lomagic) & himagic) != 0)

Puedo crear un valor de 0x81818181 de 0x81818181 , que puede hacer que 0x81818181 - 0x01010101) & 0x80808080 no sea igual a 0 , pero no hay bytes de todo cero.

¿Se relaciona esto con el hecho de que los valores ASCII varían de 0 a 127 , por lo que 0x81 no es ASCII válido? Pero no creo que el estándar C obligue a las cadenas a usar ASCII.

Answer 1

Me lo imaginé. No puedo creer que sea así de simple, dediqué la última media hora.

Esta bien que el cheque

if (((longword - lomagic) & himagic) != 0)

permite que 0x81818181 valores como 0x81818181 , porque si pasa, la siguiente prueba en cada byte no se devolvería, ya que no hay byte todo cero. Así que el bucle puede continuar probando la siguiente longword .

El algoritmo detrás de la verificación se basa en Determinar si una palabra tiene un byte cero

unsigned int v; 
bool hasZeroByte = ~((((v & 0x7F7F7F7F) + 0x7F7F7F7F) | v) | 0x7F7F7F7F);

En el complemento de 2, - 0x01010101 tiene el mismo efecto con + 0xFEFEFEFF . La diferencia es que glibc no tiene v & 0x7F7F7F7F , lo que garantiza que los bytes en la palabra tengan el bit más significativo de 0 . Esto evita ejemplos como 0x81818181 , pero glibc lo omite porque no tiene que dejarlo pasar como se indicó anteriormente. La verificación es correcta siempre que no se pierda ninguna palabra que tenga bytes de cero.