如何访问 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

这个问题的各种变体一直被问到。这个版本的问题（需要条件行为而不仅仅是if(isalpha(c)) c|=0x20;））使问题变得足够复杂，以至于如何有效地完成它并不是立即显而易见的。

事实证明，这xor并不难想到，将这段代码无条件地大写或小写只需要从xor 0x20toand ~0x20或进行简单的更改or 0x20。（进一步简化也是可能的。）

以下是我尝试最佳效率汇编的方法。我什至包含了一个带有 SIMD 向量的版本，以及使用我从向量化中获得的无分支想法的字节循环的另一个版本。

只有当您了解使用不太优化的代码解决此问题所涉及的基本原理时，阅读此答案可能才有用。OTOH，实际需要的操作很少，因此没有太多代码可供理解。我确实对此发表了很大的评论。x86标签 wiki中有许多有用的链接，从教程到性能调整的参考指南。

小写和大写字母 ASCII 字符之间的转换只需要设置或清除该0x20位，因为 ASCII 字符集的布局彼此之间的范围为 32，并且不会跨越 mod32 边界。

对于每个字节：

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

以这种方式进行 ASCIIisalpha(3)测试是安全的：从设置该位开始，最终出现在'a'..'z'范围内的唯一源字节是大写字母字符。这只是适用于任何两个不跨越%32边界的大小相等的范围的数学。（例如%64，如果相关位是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
    }
}

如果某些“设计文档”内容位于代码外部的块中，则此代码可能更具可读性。它让事情变得很混乱，看起来有很多代码，但实际上指令很少。（它们很难用简短的注释来解释。注释代码很棘手：太明显的注释只会造成混乱，并且会占用阅读代码和有用注释的时间。）

矢量化

实际上，对于 x86，我会使用 SSE 或 AVX 一次执行 16B，执行相同的算法，但与两个pcmpgtb. 当然，无条件地存储结果，因此所有非字母字符的数组仍然会在缓存中被弄脏，从而使用更多的内存带宽。

没有未签名的 SSE 比较，但我们仍然可以将我们正在寻找的范围向下移动到底部。没有值小于-128，因此在有符号比较中，其工作方式0与无符号比较中的工作方式相同。

为此，减去128. （或加法，或异或（无进位加法）；进位/借位无处可去）。这可以通过与减法相同的操作来完成'a'。

然后使用比较结果作为掩码将 向量中的字节清零0x20，因此只有字母字符与 0x20 进行异或。（0 是 XOR/add/sub 的单位元素，这对于 SIMD 条件来说通常非常方便）。

另请参阅strtoupper已测试的版本，以及在循环中调用它的代码，包括在隐式长度 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在我记得屏蔽0x20s 的向量而不是结果之前使用。）

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

显然MSVC 内联汇编不允许.label本地符号名称。我为第一个版本（带有条件分支）更改了它们，但不是这个。

使用movzx eax, byte [esi]比 更好mov al, [esi]，避免了对 AMD、Intel Haswell 及更高版本以及 Silvermont 系列的循环携带错误依赖。 movzx并不像老款 AMD 上的负载那么便宜。（至少在 Intel 和 AMD Ryzen 上，一个 uop 仅使用加载端口，而不是 ALU 端口）。 为什么 GCC 不使用部分寄存器？

之后再操作al还是可以的。不存在部分寄存器停顿（或避免它的额外指令），因为我们不是在写入eax后进行读取。（不幸的是，没有，只有）。setccalsetcc r/m32r/m8

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