如何访问字符数组并将小写字母改为大写,反之亦然

目前正在使用x86处理器开发结构化计算机组织的类项目。 我访问的值是一个1字节的字符,但我不知道如何将其与大写字母进行比较。 他们说使用hex格式的ASCII表,但我不知道如何比较这两个。

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 } 

}

任何事情在这一点上都有帮助。 预先感谢您的帮助!

编辑1:

感谢所有的build议和清晰点,编辑我的代码以反映变化。 现在有一些访问冲突的问题。

编辑2(+):

感谢有帮助的眼睛的人。 我现在还在翻译所有的信件。

为了清楚起见,我只是使用纯大会,并假设…

  • char_array[ebp+8]处的一个32位指针。
  • array_size[ebp+12]是一个二进制补码32位数。
  • 对于你的平台(大多数情况下是这样的), char的编码是ASCII。

你应该能够自己推断出内联汇编。 现在,如果你看看每个人都应该记住的桌子,但几乎没有人会做 ,你会注意到一些重要的细节。

  • 大写字母AZ映射到代码0x410x5A
  • 小写字母az映射到代码0x610x7A
  • 其他一切都不是字母,因此不需要大小写转换。
  • 如果您查看大写和小写字母范围的二进制表示forms,您会注意到它们完全相同,唯一的例外是大写字母已经清除了位6,小写字母已经清除了位6。

结果,algorithm将是…

 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 

现在,我们把它翻译成汇编…

 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: 

一旦代码到达.end_loop ,就完成了。

我希望这引起了你的光芒!

在ASCII中'a' – 'z'和'A' – 'Z'是等同的,除了一位0x20

你这里的朋友是XOR。

如果你有一个字符('A' – 'Z'或'a' – 'z'),用0x20对它进行XOR操作会触发事件;

在XORing之前,做一个范围检查是有道理的。 (看看这个值是否真的是一个字母)
您可以简化这个范围检查通过ORing值来检查与0xef,这将使“a”到“A”和“z”到“Z”,然后进行范围检查只有一次
(如果你只比较“a”和“z”,你会错过中间的字符('[',']'等)

这个问题的变化总是被问到。 这个版本的问题(要求条件行为超越if(isalpha(c)) c|=0x20; ))使得问题复杂到足以使得如何有效地做到这一点并不明显。

事实certificate, xor不难想象,并且无条件地将这个代码转换为upcase或者downcase只需要从xor 0x20and ~0x20 〜0x20或者or xor 0x20一个简单的改变。 (也可以简化一点。)

以下是如何做到最佳效率的尝试。 我甚至包含了一个带有SIMD向量的版本,另外一个版本的字节循环使用了我从向量化的无分支思想。

阅读这个答案可能只有当你理解了解决这个不是那么优化的代码所涉及的基本原则时才有用。 OTOH,实际需要的操作很less,所以没有太多的代码可以帮忙。 而且我的评论很重。 x86标记wiki中有很多有用的链接,从教程到参考指南到性能调优。


小写字母和大写字母ASCII字符之间的转换只需要设置或清除0x20位,因为ASCII字符集的范围是32,而不是跨过mod32的边界。

对于每个字节:

  • 做一个副本,并无条件地或与0x20
  • 检查它是否在'a''z'
  • 如果是这样,使用xor翻转ASCII字母大小写的位,并将结果存回数组中。

以这种方式进行ASCII isalpha(3)testing是安全的:以'a''z'结尾的唯一源字节范围从设置该位是大写字母字符。 这只是math,适用于任何两个相同大小的范围,不跨越%32边界。 (或者,如果相关位是0x40 ,则为%64边界)。

为了更有效地进行比较,我使用了unsigned-compare技巧,所以在循环中只有一个条件分支(除了循环条件本身)。 请参阅代码中的注释以获取解释。

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

如果某些“devise文档”内容位于代码之外的块中,则此代码可能更具可读性。 它使事情变得非常混乱,并且看起来好像有很多代码,但实际上只有很less的指令。 (他们只是很难用简短的评论来解释,评论的代码是非常棘手的:太明显的评论只是混乱,需要花费时间阅读代码和有用的评论。)


vector化

实际上对于x86我会使用SSE或AVX一次做16B,做相同的algorithm,但做两个pcmpgtb比较。 当然,无条件地存储结果,因此所有非字母字符的数组仍然会在caching中变脏,使用更多的内存带宽。

没有无符号的SSE比较,但我们仍然可以将我们正在查找的范围向下移动到底部。 没有小于-128值,所以在一个有符号比较中,它的工作方式是在无符号比较中进行。

要做到这一点,减去128 。 (或添加,或xor(无用添加);没有任何进行/借用去) 。 这可以通过与减去'a'相同的操作完成。

然后使用比较结果作为掩码来清零0x20向量中的字节,所以只有字母字符与0x20异或。 (0是XOR / add / sub的标识元素,SIMD条件通常非常方便)。

另请参见经过testing的strtoupper版本 ,以及隐式长度的Cstring(即时search终止0) 循环调用它的代码 ,包括处理非16 strtoupperinput。

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

即使没有AVX,也可以编译成漂亮的代码,只有一个额外的movdqa来保存寄存器的副本。 看两个早期版本的godbolt链接(一个使用两个比较,以保持简单,另一个使用pblendvb之前,我想起来,掩盖向量0x20秒,而不是结果)。

 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 

使用无分支testing的相同想法也适用于字节循环:

  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: 

对于64位代码,只需使用rsi而不是esi 。 其他一切都是一样的。

显然, MSVC内联asm不允许.label本地符号名称 。 我改变了他们的第一个版本(与条件分支),但不是这一个。

使用movzx eax, byte [esi]在某些CPU上movzx eax, byte [esi]可能稍微好一点,以避免在函数input时错误地依赖于eax的值。 OTOH,只有AMD有这个问题(和Silvermont),但是movzx并不像AMD那样便宜。 (这是在英特尔,一个只使用一个加载端口,而不是一个ALU端口)。 之后在al运行还是不错的,因为它在setcc写入al之后避免了读取eax的部分寄存器失速 (或者额外的指令来避免它)。 (不幸的是,没有setcc r/m32 ,只有r/m8 )。


我不得不想知道,如果有人把这样的代码交给像这样的任务,教授会怎么想。 :PI甚至怀疑一个聪明的编译器会使用setcc / shift技巧,除非你引导编译器朝向它。 (也许是unsigned mask = (tmp>='a' && tmp<='z'); mask <<= 5; a[i] ^= mask;或者其他东西)编译器知道无符号比较技巧, gcc在某些情况下并不使用它来进行非编译时常量程检查,即使它可以certificate范围足够小 。

由@KemyLand提供的汇编代码有用的细节,我已经想出了如何将大写字母转换为小写字母,反之亦然。

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

}

随意帮助解释我可能错过了什么! 谢谢大家帮助我更好的了解x86汇编处理器。

在一个ASCII表中,所有字母都是连续的:

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

所以你可以看到,通过切换第6位,你可以将表单从大写变成小写。