assembly - How to access a char array and change lower case letters to upper case, and vice versa

Variations of this question get asked all the time. This version of the problem (requiring conditional behaviour beyond just if(isalpha(c)) c|=0x20;)) made the problem complex enough that it wasn't immediately obvious how to do it efficiently.

It turns out that xor wasn't hard to think of, and converting this code to unconditionally upcase or downcase only requires a simple change from xor 0x20 to and ~0x20 or or 0x20. (Simplifying a bit more is possible, too.)

Here's how I'd do it with an attempt at optimally efficient asm. I even included a version with SIMD vectors, and another version of the byte loop using the branchless idea I got from vectorizing it.

Reading this answer is probably only useful once you understand the basic principles involved in solving this with not-so-optimized code. OTOH, there are very few operations actually needed, so there's not much code to grok. And I did comment it heavily. There are many helpful links in the x86 tag wiki, from tutorials to reference guides to performance tuning.

---

Converting between lower and upper case alphabetic ASCII characters only requires setting or clearing the 0x20 bit, because the ASCII character set is laid out with the ranges 32 from each other, and not crossing a mod32 boundary.

For each byte:

• make a copy and unconditionally OR it with 0x20



• check if it's between 'a' and 'z'


• if so, flip the ASCII alphabetic case bit using xor and store the result back into the array.

Doing the ASCII isalpha(3) test this way is safe: The only source bytes that end up in the 'a'..'z' range from setting that bit are the upper-case alphabetic characters. It's just math that works for any two equal-sized ranges that don't cross a %32 boundary. (Or a %64 boundary if the relevant bit was 0x40, for example).

To do the compare even more efficiently, I use the unsigned-compare trick so there's only one conditional branch inside the loop (other than the loop condition itself). See the comments in the code for an explanation.

One byte at a time branching on an efficient range-check for alphabetic char detection

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

    }
}

This code might be more readable if some of the "design doc" stuff was in a block outside the code. It clutters things up a lot, and makes it look like there's a lot of code, but really there are very few instructions. (They're just hard to explain with short comments. Commenting code is tricky: comments that are too obvious are just clutter and take time away from reading the code and the useful comments.)

---

Vectorized

Actually for x86 I'd use SSE or AVX to do 16B at a time, doing the same algorithm, but doing the comparisons with two pcmpgtb. And of course unconditionally storing the results, so an array of all non-alphabetic characters would still be dirtied in the cache, using more memory bandwidth.

There's no unsigned SSE compare, but we can still range-shift the range we're looking for down to the bottom. There are no values less than -128, so in a signed compare it works the way 0 does in an unsigned compare.

To do this, subtract 128. (or add, or xor (carryless add); there's nowhere for the carry / borrow to go). This can be done in the same operation as subtracting 'a'.

Then use the compare result as a mask to zero out bytes in a vector of 0x20, so only the alphabetic characters get XORed with 0x20. (0 is the identity element for XOR/add/sub, which is often really handy for SIMD conditionals).

See also a strtoupper version that has been tested, and code to call it in a loop, including handling of non-multiple-of-16 inputs, on implicit-length C strings (searching for the terminating 0 on the fly).

#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

}

This compiles to nice code, even without AVX, with only one extra movdqa to save a copy of a register. See the godbolt link for two earlier versions (one using two compares to keep it simple, another using pblendvb before I remembered to mask the vector of 0x20s instead of the result.)

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

---

This same idea of using a branchless test would also work for the byte loop:

        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:

For 64bit code, just use rsi instead of esi. Everything else is the same.

Apparently MSVC inline asm doesn't allow .label local-symbol names. I changed them for the first version (with conditional branch), but not this one.

Using movzx eax, byte [esi] is better than mov al, [esi], avoiding a loop-carried false dependency on AMD, and Intel Haswell and later, and Silvermont-family. movzx isn't quite as cheap as a load on older AMD. (It is on Intel, and AMD Ryzen at least, one uop that only uses a load port, not an ALU port). Why doesn't GCC use partial registers?

Operating on al after that is still ok. There's no partial-register stall (or extra instructions to avoid it) because we aren't reading eax after setcc writes al. (There is no setcc r/m32, only r/m8, unfortunately).

---

I have to wonder what a professor would think if anyone handed in code like this for an assignment like that. :P I doubt even a smart compiler would use that setcc / shift trick unless you led the compiler towards it. (Maybe unsigned mask = (tmp>='a' && tmp<='z'); mask <<= 5; a[i] ^= mask; or something.) Compilers do know about the unsigned-compare trick, but gcc doesn't use it in some cases for non-compile-time-constant range checks, even when it can prove that the range is small enough.