Testing if a value is within one of two ranges

Question

I am writing a MIPS program that should only works with uppercase or lowercase characters as input. My program works using the ASCII values of the characters.

I need to check if each character in the input is in the ASCII range of 65-90 (A-Z) or else 97-122 (a-z). If it is not in either of those ranges, skip this character and repeat for the next character. How can this be done?

EDIT

Here is a solution I just came up with but I'm sure there is a less ugly way to do this?

function:    #increment $t0 to next char of input
             blt $t0, 65, function
             bgt $t0, 122, function
             blt $t0, 91, continue
             bgt $t0, 96, continue
             j   function
continue:    ...
             j   function

Answer 1

No matter what you do, you'll need four branch insts.

The first thing I'd do is add sidebar comments to each instruction.

Good comments are part of any language, but crucial for asm. Virtually every line should have them. They address the logic of your algorithm (i.e. the "what/why"). The instructions themselves are the "how".

Notice that you're using decimal numbers for the ASCII chars. Without comments it's difficult to follow the logic to determine if the instructions are correct.

I'd adjust your grouping a bit to keep A-Z tests together and a-z tests together and not intermix them. This might be slightly slower, but the code is more intuitive.

I also did a third version that is very easy to understand. It uses character constants instead of hardwired decimal values.

---

Here's your original with annotations:

 function:
    # increment $t0 to next char of input

    blt     $t0,65,function         # less than 'A'? if yes, loop
    bgt     $t0,122,function        # greater than 'z'? if yes, loop

    blt     $t0,91,continue         # less than or equal to 'Z'? if yes, doit
    bgt     $t0,96,continue         # greater than or equal to 'a'? if yes, doit

    j       function

continue:
    # ...
    j       function

---

Here's the reordered version:

 function:
    # increment $t0 to next char of input

    blt     $t0,65,function         # less than 'A'? if yes, loop
    blt     $t0,91,continue         # less than or equal to 'Z'? if yes, doit

    bgt     $t0,122,function        # greater than 'z'? if yes, loop
    bgt     $t0,96,continue         # greater than or equal to 'a'? if yes, doit

    j       function

continue:
    # ...
    j       function

---

Here is the most straightforward version. This is the easiest to understand and, personally, I'd do this. It also eliminates an extra/extraneous j instruction.

The previous versions have to "know" that A-Z is lower in value than a-z. They could "get away" with this because the ASCII values were "hardwired" in decimal.

In C, that wouldn't [necessarily] be a good idea (i.e. you'd use the character constants). mips assemblers allow character constants, so the following is actually valid:

 function:
    # increment $t0 to next char of input

    blt     $t0,'A',trylower        # less than 'A'? if yes, try lowercase
    ble     $t0,'Z',continue        # less than or equal to 'Z'? if yes, doit

trylower:
    blt     $t0,'a',function        # less than 'a'? if yes, loop
    bgt     $t0,'z',function        # greater than 'z'? if yes, loop

continue:
    # ...
    j       function

There's an old maxim: Make it right before you make it faster (From "Elements of Programming Style" by Brian Kernighan and P.J. Plauger)

---

Here's an extra version that builds a lookup table. It takes a bit more to pre-build it, but the actual loop is faster.

In the various versions blt and bgt are pseudo ops that generate slti,bne and addi,slti,bne respectively. So, we're really talking about 10 instructions and not just 4.

So, the table build may be worth it to get a simpler/faster loop.

    .data
isalpha:    .space  256

    .text
main:
    la      $s0,isalpha             # get address of lookup table

    li      $t0,-1                  # byte value
    li      $t2,1                   # true value

    # build lookup table
build_loop:
    # increment $t0 to next char of input
    addi    $t0,$t0,1               # advance to next char
    beq     $t0,256,build_done      # over edge? if so, table done

    blt     $t0,'A',build_lower     # less than 'A'? if yes, try lowercase
    ble     $t0,'Z',build_set       # less than or equal to 'Z'? if yes, doit

build_lower:
    blt     $t0,'a',build_loop      # less than 'a'? if yes, loop
    bgt     $t0,'z',build_loop      # greater than 'z'? if yes, loop

build_set:
    addiu   $t1,$s0,$t0             # point to correct array address
    sb      $t2,0($t1)              # mark as a-z, A-Z
    j       build_loop              # try next char

build_done:

function:
    # increment $t0 to next char of input

    addu    $t1,$s0,$t0             # index into lookup table
    lb      $t1,0($t1)              # get lookup table value
    beqz    $t1,function            # is char one we want? if no, loop

continue:
    # ...
    j       function

---

Here's a version with a predefined lookup table:

    .data
isalpha:
    .byte   0:65
    .byte   1:26
    .byte   0:6
    .byte   1:26
    .byte   0:133

    .text
    la      $s0,isalpha             # get lookup table address

function:
    # increment $t0 to next char of input

    addu    $t1,$s0,$t0             # index into lookup table
    lb      $t1,0($t1)              # get lookup table value
    beqz    $t1,function            # is char one we want? if no, loop

continue:
    # ...
    j       function

Answer 2

Since the ASCII ranges happen to be nicely arranged, you can ori to force upper-case characters to lower, then use sub / sltu as a range check. What is the idea behind ^= 32, that converts lowercase letters to upper and vice versa? explains how / why this works. (Or andi to clear the lower-case bit and force any alphabetic characters to upper case.) Or just do the addu / sltu part to only check for isupper or islower instead of isalpha.

    ori     $t1, $t0, 0x20       # set lower-case bit (optional)

    addiu   $t1, $t1, -97        # -'a'  index within alphabet
    sltiu   $t1, $t1, 26         # idx <= 'z'-'a'  create a boolean

    bnez    $t1, alphabetic      # branch on it, original char still in $t0

MARS's assembler unfortunately doesn't allow -'a' as a numeric literal so you have to write it out manually. Better assemblers like clang or the GNU assembler really would let you write addiu $t1, $t1, -'a'.

(If your character starts in memory, lbu $t0, 0($a0) or similar would be a good start. An lb sign-extending load is ok, too; this will correctly reject bytes with their high bit set whether they're zero- or sign-extended. The range we want to "accept" only includes signed-positive byte values.)

---

Compilers know this trick. For example:

int alpha(unsigned char *p) {
    unsigned char c = *p;
    c |= 0x20;
    return (c>='a' && c <= 'z');
}

compiles with MIPS GCC to the same asm (Godbolt compiler explorer) as

int alpha(unsigned char *p) {
  unsigned char c = *p;
  unsigned lcase = c|0x20;
  unsigned alphabet_idx = lcase - 'a';   // 0-index position in the alphabet
  bool alpha = alphabet_idx <= (unsigned)('z'-'a');
  return alpha;
}

In fact, clang can even optimize ((c>='a' && c <= 'z') || (c>='A' && c <= 'Z')); into equivalent asm for MIPS or RISC-V. (Also included in Godbolt link).

See also How can I implement if(condition1 && condition2) in MIPS? which also shows the range-check trick for '0' .. '9'.