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

Question

目前，我正在使用x86处理器为结构化计算机组织编写一个类项目。我正在访问的值是一个1字节字符，但我不知道如何将它与大写字母进行比较。他们说要使用十六进制格式的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：

谢谢你所有的建议和要点清晰，编辑我的代码，以反映变化。现在出现了访问冲突的问题。

编辑2 (+)：

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

Answer 1

为了清楚起见，我只会使用纯汇编，并假设.

• char_array是[ebp+8]的32位指针.
• array_size是[ebp+12]的两个补码32位数.
• 对于您的平台(无论如何，大多数平台都是这样)，char的编码是ASCII。

您应该能够自己推断成内联程序集。现在，如果你看看每个人都应该记得的桌子，但几乎没有人记得。，你会发现一些重要的细节.

• 大写字母A分别通过Z映射成代码0x41通过0x5A。
• 小写字母a通过z映射成代码0x61，通过0x7A分别映射成代码。
• 其他一切都不是一个字母，因此不需要转换案例。
• 如果您查看大写字母范围和小写字母范围的二进制表示形式，您会注意到它们完全相同，唯一的例外是大写字母已清除6位，小写字母已设置。

因此，算法将是.

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，您就完成了。

我希望这已经给你带来了光明！

Answer 2

这个问题的变体总是会被问到。这个版本的问题(除了if(isalpha(c)) c|=0x20;，还需要有条件的行为)使得问题变得非常复杂，以至于不清楚如何有效地解决这个问题。

事实证明，xor并不难想象，将此代码转换为无条件的大写或小写只需要简单地从xor 0x20更改为and ~0x20或or 0x20。(再简化一点也是可能的。)

下面是我如何尝试实现最优效率的asm。我甚至包括了一个SIMD向量版本，以及另一个版本的字节循环，使用的是我从矢量化中获得的无分支思想。

阅读这个答案可能是有用的，只有当你理解了解决这个问题所涉及的基本原则与非优化的代码。OTOH，实际需要的操作很少，所以没有太多的代码可以处理。我对此做了很大的评论。x86标记wiki中有许多有用的链接，从教程到参考指南，再到性能调优。

在小写字母和大写字母ASCII字符之间进行转换只需要设置或清除0x20位，因为ASCII字符集是以彼此之间的范围32排列的，而不是跨越mod32边界。

对于每个字节：

• 复制一份，并与0x20无条件地或
• 检查它是否在'a'和'z'之间
• 如果是这样，使用xor翻转ASCII字母大小写位，并将结果存储回数组中。

以这种方式进行ASCII isalpha(3)测试是安全的:在'a'.'z'中结束的唯一源字节是大写字母字符。对于不跨越%32边界的任意两个大小相等的范围，这只是数学而已。(例如，如果相关位为0x40，则为0x40边界)。

为了更有效地进行比较，我使用了无符号比较技巧，这样循环中只有一个条件分支(除了循环条件本身)。有关解释，请参阅代码中的注释。

一次一个字节在一个有效的范围上分支-检查字母字符检测

/******** 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:
        movzx eax, byte ptr [esi];     // load the current character
        mov   edx, eax;              // save a copy to maybe flip + store

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

如果某些"design“内容位于代码外部的块中，则该代码可能更易读。它把事情弄得乱七八糟，看起来好像有很多代码，但实际上只有很少的指令。(他们只是很难用简短的评论来解释。注释代码是很棘手的:太明显的注释只是杂乱无章，需要花时间阅读代码和有用的注释。)

矢量化

实际上，对于x86，我会使用SSE或AVX一次做16B，做相同的算法，但是用两个pcmpgtb进行比较。当然，无条件地存储结果，所以所有非字母字符的数组仍然会在缓存中被污染，使用更多的内存带宽。

没有无符号的SSE比较，但我们仍然可以将我们正在寻找的范围向下移动到底部。没有比-128少的值，所以在有符号比较中，它的工作方式就像0在无符号比较中所做的那样。

要做到这一点，请减去128。(或添加，或xor (无携带添加)；没有地方可供携带/借入)。这可以在与减去'a'相同的操作中完成。

然后使用比较结果作为掩码，使0x20向量中的字节为零，因此只有字母字符才能得到0x20的XORed。(0是XOR/add/sub的标识元素，这对于SIMD条件词来说通常非常方便)。

还请参阅一个经过测试的版本，以及在循环中调用它的代码，包括在隐式长度C字符串上处理16个输入中的非多个输入(动态搜索终止0)。

#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

使用无分支测试的相同想法也适用于字节循环：

        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:
        movzx  eax, byte ptr [esi];     // load the current character
        mov    edx, eax;

        // 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。其他的一切都一样。

显然是本地符号名称。我将它们更改为第一个版本(带有条件分支)，但不是这个版本。

使用movzx eax, byte [esi]比使用mov al, [esi]更好，避免了循环对AMD、英特尔Haswell和Silvermont家族的错误依赖。movzx并不像老款的AMD那样便宜。(至少在英特尔和AMD Ryzen上，只有一个uop只使用加载端口，而不是ALU端口)。GCC为什么不使用分寄存器？

在那之后在al上操作还是可以的。没有部分寄存器失速 (或避免它的额外说明)，因为在setcc编写al之后，我们没有阅读al。(不幸的是，没有setcc r/m32，只有r/m8 )。

我想知道，如果有人为这样的作业提交这样的代码，教授会怎么想。P:我怀疑即使是聪明的编译器也会使用setcc / shift技巧，除非你带领编译器走向它。(也许是unsigned mask = (tmp>='a' && tmp<='z'); mask <<= 5; a[i] ^= mask;之类的。)编译器确实知道无符号比较技巧，但是gcc在某些情况下不使用它进行非编译时间常数范围检查，即使它可以证明范围足够小。。

Answer 3

在ASCII 'a'-'z‘和'A'-'Z’是等价的，除了一个位，0x20

你的朋友是异或。

如果你有一个字符( 'A'-'Z‘或’a‘z’)，XORing它与0x20将切换的情况；

在XORing之前，进行范围检查是有意义的。(看看这个值是否真的是字母)

您可以通过ORing简化这个范围检查--要用0xef检查的值，这将使'a‘到'A’和'z‘到'Z'，然后只进行一次范围检查。

(如果您只比较<'a‘和>'Z’，您将错过(''，‘’等)之间的字符.