assembly - Cómo acceder a una matriz de caracteres y cambiar letras minúsculas a mayúsculas, y viceversa

x86

Question

Actualmente estoy trabajando en un proyecto de clase para Structured Computer Organization usando un procesador x86. El valor al que estoy accediendo es un carácter de 1 byte, pero no sé cómo compararlo con mayúsculas. Dijeron usar una tabla ASCII del formato hexadecimal, pero no estoy seguro de cómo comparar los dos.

void changeCase (char char_array[], int array_size ) {
    __asm {
            // BEGIN YOUR CODE HERE

        mov eax, char_array;        //eax is base image
        mov edi, 0;

    readArray:
        cmp edi, array_size;
        jge  exit;
        mov ebx, edi;           //using ebx as offset
        shl ebx, 2;
        mov cl, [eax + ebx];    //using ecx to be the storage register

    check:
        //working on it
        cmp cl, 0x41;       //check if cl is <= than ASCII value 65 (A)
        jl next_indx;
        cmp cl, 0x7A;       //check if cl is >= than ASCII value 122 (z)
        jg next_indx;
        cmp cl, ''a'';
        jl convert_down;
        jge convert_up;


    convert_down:
        or cl, 0x20;        //make it lowercase
        jmp write;

    convert_up:
        and cl, 0x20;       //make it uppercase
        jmp write;

    write:
        mov byte ptr [eax + ebx], cl    //slight funky town issue here,

    next_indx:
        inc edi;

    exit:
        cmp edi, array_size;
        jl readArray;

    mov char_array, eax;
            // END YOUR CODE HERE
    }
}

Cualquier cosa ayuda en este punto. ¡Gracias por adelantado por la ayuda!

editar 1:

Gracias por todas las sugerencias y puntos de claridad, edité mi código para reflejar el cambio. Algún problema con la infracción de acceso ahora.

editar 2 (+):

Gracias por los ojos útiles personas. Todavía estoy llegando a traducir todas las letras ahora.

Answer 1

Cortesía de @KemyLand para el desglose útil del código de ensamblaje, he descubierto cómo convertir mayúsculas a minúsculas y viceversa.

void changeCase (char char_array[], int array_size ) {
     //this function is designed to change lowercase letters to uppercase, and vice-versa, from a char-array given the array and its size.
__asm{
        // BEGIN YOUR CODE HERE

    mov eax, [ebp + 8];     //move to register value parameter 1 (the array)
    mov ecx, [ebp + 12];    //likewise parameter 2 (the array size)

    START:

        or ecx, ecx;    //check if pointer is 0
        cmp ecx, 0;
        je endloop;   //go to end loop

        mov dl,byte ptr [eax];  //not sure if needed, but reassurance
        cmp dl, 0x41;   // is char an A?
        jl cont;

        cmp dl, 0x5A;   // is char a Z?
        jle convertUP;

        cmp dl, 0x61;   // is char an a?
        jl cont;

        cmp dl, 0x7A;   // is char a z?
        jle convertDOWN;

        jmp cont;


    convertUP:
        or dl, 0x20;        //Yes! Finally got it working!
        mov byte ptr [eax], dl;

        jmp cont;

    convertDOWN:
        and dl, 0xdf;       //this will work for sure.
        mov[eax], dl;

        jmp cont


    cont:
        inc eax;
        dec ecx;

        jmp START;

    endloop:
}

}

¡No dude en ayudarme a explicar lo que podría haberme perdido! Gracias a todos por ayudarme a comprender mejor el procesador de ensamblaje x86.

Answer 2

En aras de la claridad, solo usaré ensamblaje puro y asumiré que ...

• char_array es un puntero de 32 bits en [ebp+8] .
• array_size es un número de 32 bits complementario de dos en [ebp+12] .
• Para su plataforma (de todas formas es así), la codificación de char es ASCII.

Debería poder deducir esto usted mismo en el ensamblaje en línea. Ahora, si miras la mesa, se supone que todos deben recordar, pero casi nadie lo hace , notarás algunos detalles importantes ...

• Las letras mayúsculas de la A a la Z asignan a los códigos 0x41 a 0x5A , respectivamente.
• Las letras minúsculas de la A a la z asignan a los códigos 0x61 a 0x7A , respectivamente.
• Todo lo demás no es una carta y, por lo tanto, no necesita conversión de mayúsculas y minúsculas.
• Si observa la representación binaria de los rangos de letras mayúsculas y minúsculas, notará que son exactamente iguales, con la única excepción de que las letras mayúsculas tienen el bit 6 borrado y las minúsculas lo tienen configurado.

Como resultado, el algoritmo sería ...

while array_size != 0
    byte = *char_array
    if byte >= 0x41 and byte <= 0x5A
        *char_array |= 0x20 // Turn it lowercase
    else if byte >= 0x61 and byte <= 0x7A
        *char_array &= 0xDF // Turn it uppercase
    array_size -= 1
    char_array += 1

Ahora, traduzcamos esto en ensamblaje ...

mov eax, [ebp+8]      # char *eax = char_array
mov ecx, [ebp+12]     # int ecx = array_size

.loop:
    or ecx, ecx       # Compare ecx against itself
    jz .end_loop      # If ecx (array_size) is zero, we''re done
    mov dl, [eax]     # Otherwise, store the byte at *eax (*char_array) into `char dl`
    cmp dl, ''A''       # Compare dl (*char_array) against ''A'' (lower bound of uppercase letters)
    jb .continue      # If dl` (*char_array) is lesser than `A`, continue the loop
    cmp dl, ''Z''       # Compare dl (*char_array) against ''Z'' (upper bound of uppercase letters)
    jbe .is_uppercase # If dl (*char_array) is lesser or equal to ''Z'', then jump to .is_uppercase
    cmp dl, ''a''       # Compare dl (*char_array) against ''a'' (lower bound of lowercase letters)
    jb .continue      # If dl (*char_array) is lesser than ''a'', continue the loop
    cmp dl, ''z''       # Compare dl (*char_array) against ''z'' (upper bound of lowercase letters)
    jbe .is_lowercase # If dl (*char_array) is lesser or equal to ''z'', then jump to .is_lowercase
    jmp .continue     # All tests failed, so continue the loop

    .is_uppercase:
        or dl, 20h    # Set the 6th bit
        mov [eax], dl # Send the byte back to where it came from
        jmp .continue # Continue the loop

    .is_lowercase:
        and dl, DFh   # Clear the 6th bit
        mov [eax], dl # Send the byte back to where it came from
        jmp .continue # Continue the loop

    .continue:
        inc eax       # Increment `eax` (`char_array`), much of like a pointer increment
        dec ecx       # Decrement `ecx` (`array_size`), so as to match the previous pointer increment
        jmp .loop     # Continue

.end_loop:

Una vez que el código llega a .end_loop , ya está.

¡Espero que esto te haya iluminado!

Answer 3

En una tabla ascii todas las letras son continuas:

A=0x41=01000001
a=0x61=01100001

Z=0x5A=01011010
z=0x7A=01111010

Entonces puedes ver que al alternar el sexto bit transformas de mayúsculas a minúsculas.

Answer 4

Las variaciones de esta pregunta se hacen todo el tiempo. Esta versión del problema (que requiere un comportamiento condicional más allá de solo if(isalpha(c)) c|=0x20; )) hizo que el problema fuera lo suficientemente complejo como para que no fuera inmediatamente obvio cómo hacerlo de manera eficiente.

Resulta que no era difícil pensar en xor , y la conversión de este código a mayúsculas o minúsculas incondicionalmente solo requiere un cambio simple de xor 0x20 a and ~0x20 or 0x20 . (También es posible simplificar un poco más).

Así es como lo haría con un intento de asm óptimamente eficiente. Incluso incluí una versión con vectores SIMD, y otra versión del bucle de bytes usando la idea sin ramificación que obtuve al vectorizarlo.

Leer esta respuesta probablemente solo sea útil una vez que comprenda los principios básicos involucrados en la resolución de esto con un código no tan optimizado. OTOH, hay muy pocas operaciones realmente necesarias, por lo que no hay mucho código para asimilar. Y lo comenté mucho. Hay muchos enlaces útiles en el wiki de etiquetas x86 , desde tutoriales hasta guías de referencia y ajustes de rendimiento.

La conversión entre caracteres ASCII alfabéticos en mayúsculas y minúsculas solo requiere establecer o borrar el bit 0x20 , porque el conjunto de caracteres ASCII se presenta con los rangos 32 entre sí y no cruza un límite mod32.

Para cada byte:

• hacer una copia y O incondicionalmente con 0x20
• compruebe si está entre ''a'' y ''z''
• si es así, voltee el bit de la caja alfabética ASCII usando xor y almacene el resultado nuevamente en la matriz.

Hacer la isalpha(3) ASCII isalpha(3) esta manera es seguro: los únicos bytes de origen que terminan en el rango ''a'' ... ''z'' desde la configuración de ese bit son los caracteres alfabéticos en mayúsculas. Son solo las matemáticas las que funcionan para dos rangos de igual tamaño que no cruzan un límite de %32 . (O un límite de %64 si el bit relevante era 0x40 , por ejemplo).

Para hacer la comparación aún más eficientemente, utilizo el truco de comparación sin signo para que solo haya una rama condicional dentro del bucle (que no sea la condición del bucle en sí). Vea los comentarios en el código para una explicación.

/******** Untested. ************/

// ASCII characters are flipped to the opposite case (upper <-> lower)
// non-ASCII characters are left unchanged
void changeCase (char char_array[], int array_size ) {

    __asm{
            // BEGIN YOUR CODE HERE

        mov   esi, char_array;      // MSVC inline asm requires these potentially-redundant copies :(
        mov   ecx, array_size;

        test  ecx,ecx;       // return if(size <= 0)
        jle  early_out;

    next_char:
        mov   al, [esi];     // load the current character
        mov   dl, al;

        // check if the character is alphabetic or not
        // there are two equal-size ranges of characters: one with 0x20 set, and one without
        or    al, 0x20;      // set 0x20 and then just check that lowercase range

        // unsigned compare trick: 0 <= n < high  can be done with one unsigned compare instead of two signed compares
        // low < n < high  can be done by shifting the range first
        sub   al, ''a'';       // if al is less than ''a'', it will become a large unsigned number
        cmp   al, ''z''-''a'';
        ja  non_alpha;      // conditionally skip the flip & store

        xor   dl, 0x20;      // toggle the ASCII case bit
        mov   [esi], dl;
                             // xor [esi], 0x20   // saves the mov earlier, but is otherwise slower
    non_alpha:

        inc   esi;
        dec   ecx;
        jz next_char;

    early_out:
            // END YOUR CODE HERE
    }
}

Este código podría ser más legible si algunas de las cosas del "documento de diseño" estuvieran en un bloque fuera del código. Desordena mucho las cosas y hace que parezca que hay mucho código, pero en realidad hay muy pocas instrucciones. (Son difíciles de explicar con comentarios breves. El código de comentarios es complicado: los comentarios que son demasiado obvios son simplemente desorden y le quitan tiempo a leer el código y los comentarios útiles).

Vectorizado

En realidad, para x86 usaría SSE o AVX para hacer 16B a la vez, haciendo el mismo algoritmo, pero haciendo las comparaciones con dos pcmpgtb . Y, por supuesto, almacenar los resultados incondicionalmente, por lo que una matriz de todos los caracteres no alfabéticos seguiría sucia en la memoria caché, utilizando más ancho de banda de memoria.

No hay comparación SSE sin firmar, pero aún podemos cambiar el rango que estamos buscando hasta el final. No hay valores inferiores a -128 , por lo que en una comparación con signo funciona como 0 en una comparación sin signo.

Para hacer esto, resta 128 . (o add, o xor (carryless add); no hay ningún lugar al que pueda llevar el carry / prestado) . Esto se puede hacer en la misma operación que restando ''a'' .

Luego, use el resultado de comparación como una máscara para poner a cero los bytes en un vector de 0x20 , de modo que solo los caracteres alfabéticos obtengan XOR con 0x20. (0 es el elemento de identidad para XOR / add / sub, que a menudo es realmente útil para los condicionales SIMD).

Vea también una versión strtoupper que ha sido probada y un código para llamarlo en un bucle , incluido el manejo de entradas no múltiples de 16, en cadenas C de longitud implícita (buscando el 0 final sobre la marcha).

#include <immintrin.h>

// Call this function in a loop, with scalar cleanup.  (Not implemented, since it''s the same as any other vector loop.)

// Flip the case of all alphabetic ASCII bytes in src
__m128i inline flipcase(__m128i src) {
    // subtract ''a''+128, so the alphabetic characters range from -128 to -128+25 (-128+''z''-''a'')
    // note that adding 128 and subtracting 128 are the same thing for 8bit integers.
    // There''s nowhere for the carry to go, so it''s just xor (carryless add), flipping the high bit

    __m128i lcase = _mm_or_si128(src, _mm_set1_epi8(0x20));

    __m128i rangeshift= _mm_sub_epi8(lcase, _mm_set1_epi8(''a''+128));
    __m128i non_alpha = _mm_cmpgt_epi8(rangeshift, _mm_set1_epi8(-128 + 25));  // 0:alphabetic   -1:non-alphabetic

    __m128i flip  = _mm_andnot_si128(non_alpha, _mm_set1_epi8(0x20));       // 0x20:alpha    0:non-alpha

    return          _mm_xor_si128(src, flip);
    // just mask the XOR-mask so non-alphabetic elements are XORed with 0 instead of 0x20
    // XOR''s identity value is 0, same as for addition
}

Esto compila un código agradable, incluso sin AVX , con solo un movdqa adicional para guardar una copia de un registro. Vea el enlace de Godbolt para dos versiones anteriores (una que usa dos comparaciones para mantenerlo simple, otra que usa pblendvb antes de recordar recordar enmascarar el vector de 0x20 s en lugar del resultado).

flipcase:
        movdqa  xmm2, XMMWORD PTR .LC0[rip]    ; 0x20
        movdqa  xmm1, xmm0
        por     xmm1, xmm2
        psubb   xmm1, XMMWORD PTR .LC1[rip]    ; -31
        pcmpgtb xmm1, XMMWORD PTR .LC2[rip]    ; -103
        pandn   xmm1, xmm2
        pxor    xmm0, xmm1
        ret

section .rodata
    .LC0:   times 16 db  32
    .LC1:   times 16 db  -31
    .LC2:   times 16 db  -103

Esta misma idea de usar una prueba sin ramificación también funcionaría para el bucle de bytes:

        mov   esi, char_array;
        mov   ecx, array_size;

        test  ecx,ecx;       // return if(size <= 0)
        jle  .early_out;

    ALIGN 16   ; really only need align 8 here, since the next 4 instructions are all 2 bytes each (because op  al, imm8  insns have a special encoding)
    .next_char:
        mov   al, [esi];     // load the current character
        mov   dl, al;

        // check if the character is alphabetic or not
        or    al, 0x20;        
        sub   al, ''a'';
        cmp   al, ''z''-''a'';   // unsigned compare trick: ''a'' <= al <= ''z''
        setna al;            // 0:non-alpha  1:alpha  (not above)
        shl   al, 5;         // 0:non-alpha  0x20:alpha
        xor   dl, al;        // conditionally toggle the ASCII case bit
        mov   [esi], dl;     // unconditionally store

        inc   esi;
        dec   ecx;           // for AMD CPUs, or older Intel, it would be better to compare esi against an end pointer, since cmp/jz can fuse but dec can''t.  This saves an add ecx, esi outside the loop
        jz .next_char;
    .early_out:

Para el código de 64 bits, solo use rsi lugar de esi . Todo lo demás es lo mismo.

Aparentemente, MSVC en línea no admite nombres de símbolos locales .label . Los cambié para la primera versión (con rama condicional), pero no esta.

Usando movzx eax, byte [esi] podría ser ligeramente mejor en algunas CPU, para evitar una dependencia falsa en el valor de eax en la entrada de la función. OTOH, solo AMD tiene ese problema (y Silvermont), pero movzx no es tan barato como una carga en AMD. (Está en Intel; una uop que solo usa un puerto de carga, no un puerto ALU). Operar en todo después de eso sigue siendo bueno, ya que evita que un bloqueo de registro parcial (o instrucciones adicionales para evitarlo) lea eax después de que setcc escribe al . (No hay setcc r/m32 , solo r/m8 , desafortunadamente).

Tengo que preguntarme qué pensaría un profesor si alguien entregara un código como este para una tarea como esa. : PI duda que incluso un compilador inteligente usaría ese truco setcc / shift menos que haya guiado al compilador hacia él. (Tal vez unsigned mask = (tmp>=''a'' && tmp<=''z''); mask <<= 5; a[i] ^= mask; o algo así.) Los compiladores saben sobre el truco de comparación sin signo, pero gcc no lo usa en algunos casos para verificaciones de rango constante sin tiempo de compilación, incluso cuando puede probar que el rango es lo suficientemente pequeño .

Answer 5

en ASCII ''a'' - ''z'' y ''A'' - ''Z'' son equivalentes excepto un bit, 0x20

Tu amigo aquí es XOR.

Si tiene un carácter (ya sea ''A'' - ''Z'' o ''a'' - ''z''), XOR con 0x20 cambiará el caso;

antes de XORing, hacer una verificación de rango tiene sentido. (para ver si el valor es realmente una letra)
Puede simplificar esta verificación de rango OR ordenando el valor para verificar con 0xef, que hará que ''a'' sea ''A'' y ''z'' a ''Z'', y luego haga la verificación de rango solo una vez
(si solo compara con <''a'' y> ''Z'', perderá los caracteres intermedios (''['', '']'', etc.)