Como acessar uma matriz char e alterar letras minúsculas para maiúsculas e vice-versa

Atualmente estou trabalhando em um projeto de class para organização de computadores estruturados usando um processador x86. O valor que estou acessando é um caractere de 1 byte, mas não sei como compará-lo a uma maiúscula. Eles disseram para usar uma tabela ASCII do formato hexadecimal, mas não sei como comparar os dois.

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 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 } } 

Qualquer coisa ajuda neste momento. Agradeço antecipadamente a ajuda!

editar 1:

Obrigado por toda a sugestão e pontos de clareza, editei meu código para refletir a mudança. Algum problema com violação de access agora.

edição 2 (+):

Obrigado pelas pessoas de olhos úteis. Eu ainda estou conseguindo traduzir todas as letras agora.

Para maior clareza, vou usar apenas a assembly pura e supor que …

  • char_array é um ponteiro de 32 bits em [ebp+8] .
  • array_size é um número de 32 bits de complemento de dois em [ebp+12] .
  • Para a sua plataforma (é desta maneira, de qualquer forma), a codificação do char é ASCII.

Você deve ser capaz de deduzir isso sozinho na assembly em linha. Agora, se você olhar para a mesa que todos deveriam lembrar, mas quase ninguém faz , você notará alguns detalhes importantes …

  • Letras maiúsculas de A a Z mapeiam os códigos 0x41 a 0x5A , respectivamente.
  • As letras minúsculas a até z mapeiam nos códigos 0x61 a 0x61 , respectivamente.
  • Tudo o resto não é uma carta e, portanto, não precisa de conversão de maiúsculas e minúsculas.
  • Se você olhar a representação binária dos intervalos de letras maiúsculas e minúsculas, perceberá que são exatamente os mesmos, com a única exceção de que as letras maiúsculas têm o bit 6 limpo e as letras minúsculas configuradas.

Como resultado, o algoritmo seria …

 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 

Agora, vamos traduzir isso em assembly ...

 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: 

Uma vez que o código atinge .end_loop , você está pronto.

Espero que isso tenha levado uma luz em você!

Variações desta pergunta são feitas o tempo todo. Esta versão do problema (exigindo um comportamento condicional além de apenas if(isalpha(c)) c|=0x20; )) tornou o problema complexo o suficiente para que não fosse imediatamente óbvio como fazê-lo com eficiência.

Acontece que xor não era difícil de pensar, e converter este código incondicionalmente para upcase ou downcase requer apenas uma simples mudança de xor 0x20 para and ~0x20 or 0x20 . (Simplificar um pouco mais também é possível.)

Aqui está como eu faria isso com uma tentativa de otimizar eficientemente asm. Eu inclusive incluí uma versão com vetores SIMD, e outra versão do loop de bytes usando a ideia de branchless que obtive da vectorização.

A leitura dessa resposta provavelmente só será útil quando você entender os princípios básicos envolvidos na solução disso com códigos não tão otimizados. OTOH, existem muito poucas operações realmente necessárias, então não há muito código para grok. E eu fiz um comentário pesado. Há muitos links úteis no wiki da marca x86 , de tutoriais a guias de referência para ajuste de desempenho.


A conversão entre caracteres alfabéticos ASCII de letras maiúsculas e minúsculas requer apenas a configuração ou a limpeza do bit 0x20 , porque o conjunto de caracteres ASCII é apresentado com os intervalos 32 um do outro e não cruza um limite mod32.

Para cada byte:

  • fazer uma cópia e incondicionalmente OU com 0x20
  • verifique se está entre 'a' e 'z'
  • se assim for, inverta o bit do caso alfabético ASCII usando xor e armazene o resultado de volta no array.

Fazer o teste ASCII isalpha(3) desta forma é seguro: Os únicos bytes de origem que terminam no intervalo 'a' .. 'z' da configuração desse bit são os caracteres alfabéticos maiúsculos. É apenas matemática que funciona para qualquer intervalo de tamanho igual que não ultrapasse um limite de %32 . (Ou um limite de %64 se o bit relevante for 0x40 , por exemplo).

Para fazer a comparação de maneira ainda mais eficiente, uso o truque de comparação sem sinal, de modo que haja apenas um ramo condicional dentro do loop (além da própria condição de loop). Veja os comentários no código para uma explicação.

 /******** 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 } } 

Esse código pode ser mais legível se algum material do "design doc" estiver em um bloco fora do código. Ele bagunça muito as coisas e faz parecer que há muito código, mas na verdade existem muito poucas instruções. (Eles são difíceis de explicar com comentários curtos. Comentar código é complicado: comentários que são muito óbvios são apenas desordem e demoram para ler o código e os comentários úteis.)


Vetorizado

Na verdade, para x86 eu usaria SSE ou AVX para fazer 16B de cada vez, fazendo o mesmo algoritmo, mas fazendo as comparações com dois pcmpgtb . E, claro, armazenar incondicionalmente os resultados, portanto, uma matriz de todos os caracteres não alfabéticos ainda seria suja no cache, usando mais largura de banda de memory.

Não há comparação de SSE não assinada, mas ainda podemos variar o intervalo que procuramos na parte inferior. Não há valores menores que -128 , portanto, em uma comparação assinada, ele funciona da mesma maneira que 0 em uma comparação não assinada.

Para fazer isso, subtraia 128 . (ou add, ou xor (carryless add); não há lugar para o carry / emprestado ir) . Isso pode ser feito na mesma operação que subtrair 'a' .

Em seguida, use o resultado da comparação como uma máscara para zerar os bytes em um vetor de 0x20 , para que apenas os caracteres alfabéticos recebam XOR com 0x20. (0 é o elemento de identidade para XOR / add / sub, que geralmente é muito útil para condicionais SIMD).

Veja também uma versão do strtoupper que foi testada , e código para chamá-la em um loop , incluindo o tratamento de inputs não múltiplas de 16, em strings C de comprimento implícito (procurando pelo 0 de encerramento em tempo real).

 #include  // 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 } 

Isto compila para código legal, mesmo sem o AVX , com apenas um movdqa extra para salvar uma cópia de um registro. Veja o link do Godbolt para duas versões anteriores (uma usando dois compara para manter a simplicidade, outra usando o pblendvb antes de me lembrar de mascarar o vetor de 0x20 vez do 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 

Essa mesma ideia de usar um teste sem filial também funcionaria para o loop 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 código de 64 bits, apenas use rsi vez de esi . Tudo o resto é o mesmo.

Aparentemente, o inline asm do MSVC não permite nomes de símbolo local .label . Eu os troquei pela primeira versão (com ramificação condicional), mas não esta.

Usando o movzx eax, byte [esi] pode ser um pouco melhor em algumas CPUs, para evitar uma dependência falsa do valor de eax na input da function. OTOH, apenas a AMD tem esse problema (e Silvermont), mas o movzx não é tão barato quanto uma carga na AMD. (Ele está na Intel; um uop que usa apenas uma porta de carregamento, não uma porta da ALU). Operar depois disso ainda é bom, já que evita uma parada parcial no registrador (ou instruções extras para evitá-lo) de ler eax depois que setcc escreve al . (Não há setcc r/m32 , apenas r/m8 , infelizmente).


Eu tenho que me perguntar o que um professor pensaria se alguém entregasse um código assim para uma tarefa como essa. : PI dúvida até mesmo um compilador inteligente usaria esse truque setcc / shift menos que você levou o compilador para ele. (Talvez unsigned mask = (tmp>='a' && tmp< ='z'); mask <<= 5; a[i] ^= mask; ou algo assim.) Compiladores sabem sobre o truque de comparação sem assinatura, mas O gcc não o usa em alguns casos para verificações de intervalo sem tempo de compilation, mesmo quando ele pode provar que o intervalo é pequeno o suficiente .

em ASCII ‘a’ – ‘z’ e ‘A’ – ‘Z’ são equivalentes, exceto um bit, 0x20

seu amigo aqui é XOR.

se você tiver um caractere (‘A’ – ‘Z’ ou ‘a’ – ‘z’), XORing com 0x20 alternará o caso;

antes do XORing, fazer uma verificação de intervalo faz sentido. (para ver se o valor é realmente uma carta)
Você pode simplificar essa verificação de intervalo, ORINDO o valor para verificar com 0xef, que fará ‘a’ para ‘A’ e ‘z’ para ‘Z’ e, em seguida, verificar o intervalo apenas uma vez
(se você apenas comparar com < 'a' e> ‘Z’ você perderá os caracteres no meio (‘[‘, ‘]’, etc …)

Cortesia de @KemyLand para a análise útil do código assembly, eu descobri como converter Maiúsculas para Minúsculas e vice-versa.

 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 az? 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: } 

}

Sinta-se à vontade para ajudar a explicar o que eu poderia ter perdido! Obrigado a todos por me ajudarem a entender melhor o processador de assembly x86.

Em uma tabela ascii todas as letras são contínuas:

 A=0x41=01000001 a=0x61=01100001 Z=0x5A=01011010 z=0x7A=01111010 

Então você pode ver que, ao alternar o 6º bit, você transforma a forma maiúscula em minúscula.