Shifting Bits

Section 14.3 Shifting Bits

You may wonder why the mov instruction does not include the shift forms that you have seen in most other instructions. Actually, you could use a mov instruction and follow the pattern used for other instructions (for example, add), but because shifts are so commonly used, the ARM instruction set provides specific shift instructions. Using either a shift instruction or a mov with the corresponding shift options will produce the same machine code. But the explicit shift instructions are considered standard usage.

ASR

Arithmetic Shift Right.

ASR{S}{<c>}   {<Rd>,} <Rn>, #<const>       % immediate
ASR{S}{<c>}   {<Rd>,} <Rn>, <Rm>           % register

If ‘S’ is present the condition flags are updated according to the result. If absent, the condition flags are not changed.
<c> is the condition code, Table 9.2.1.
<Rd> specifies the destination register, <Rn> is the source register, and <Rm> is the shift register.
\(1 \le const \le 32\text{.}\)

All 32 bits in the <Rn> register are shifted right, copying the sign bit into the high-order bit positions. The amount of shift is <const> in the “immediate” form or the value in <Rm> in the “register” form. If <Rd> is absent, the result is stored in <Rn>. If <Rd> is present, the result is stored there and <Rn> remains unchanged.

LSR

Logical Shift Right.

LSR{S}{<c>}   {<Rd>,} <Rn>, #<const>       % immediate
LSR{S}{<c>}   {<Rd>,} <Rn>, <Rm>           % register

If ‘S’ is present the condition flags are updated according to the result. If absent, the condition flags are not changed.
<c> is the condition code, Table 9.2.1.
<Rd> specifies the destination register, <Rn> is the source register, and <Rm> is the shift register.
\(1 \le const \le 32\text{.}\)

All 32 bits in the <Rn> register are shifted right, storing zeros in the vacated high-order bit positions. The amount of shift is <const> in the “immediate” form or the value in <Rm> in the “register” form. If <Rd> is absent, the result is stored in <Rn>. If <Rd> is present, the result is stored there and <Rn> remains unchanged.

LSL

Logical Shift Left.

LSL{S}{<c>}   {<Rd>,} <Rn>, #<const>       % immediate
LSL{S}{<c>}   {<Rd>,} <Rn>, <Rm>           % register

If ‘S’ is present the condition flags are updated according to the result. If absent, the condition flags are not changed.
<c> is the condition code, Table 9.2.1.
<Rd> specifies the destination register, <Rn> is the source register, and <Rm> is the shift register.
\(1 \le const \le 32\text{.}\)

All 32 bits in the <Rn> register are shifted left, storing zeros in the vacated low-order bit positions. The amount of shift is <const> in the “immediate” form or the value in <Rm> in the “register” form. If <Rd> is absent, the result is stored in <Rn>. If <Rd> is present, the result is stored there and <Rn> remains unchanged.

ROR

Rotate Right.

ROR{S}{<c>}   {<Rd>,} <Rn>, #<const>       % immediate
ROR{S}{<c>}   {<Rd>,} <Rn>, <Rm>           % register

If ‘S’ is present the condition flags are updated according to the result. If absent, the condition flags are not changed.
<c> is the condition code, Table 9.2.1.
<Rd> specifies the destination register, <Rn> is the source register, and <Rm> is the shift register.
\(1 \le const \le 32\text{.}\)

All 32 bits in the <Rn> register are shifted right, copying the low-order bits into the high-order bit positions as they are shifted. The amount of shift is <const> in the “immediate” form or the value in <Rm> in the “register” form. If <Rd> is absent, the result is stored in <Rn>. If <Rd> is present, the result is stored there and <Rn> remains unchanged.

RRX

Rotate Right with eXtend.

RRX{S}{<c>}   {<Rd>,} <Rn>, <Rm>           % register

If ‘S’ is present the condition flags are updated according to the result. If absent, the condition flags are not changed.
<c> is the condition code, Table 9.2.1.
<Rd> specifies the destination register, <Rn> is the source register, and <Rm> is the shift register.

All 32 bits in the Rn register are shifted right one bit position, copying the Carry Flag into the high-order bit position. If S is present, the low-order bit is copied into the Carry Flag. If Rd is absent, the result is stored in Rn. If Rd is present, the result is stored there and Rn remains unchanged.

In the solution to Exercise 4.5.1 we used an algorithm for converting a hexadecimal text string to an integer. The algorithm shifts the integer subtotal four bits to the left, converts the next hexadecimal character to the corresponding integer, and adds it to the subtotal. In this section we separate the algorithm into its own function, as shown in Listing 14.3.1. We use the writeLn function from Exercise 13.3.2 and the readLn function from Exercise 13.3.4. You will learn how to convert an integer to its corresponding decimal text string in Section 14.5 so we will use printf in this program.

/* hexConvert1.c
 * Prompts user for hex number and converts
 * it to an int.
 * 2017-09-29: Bob Plantz
 */

#include <stdio.h> 
#include "hexToInt.h"
int writeStr(char *);
int readLn(char *, int);

int main()
{
  int theNumber;
  char theString[9];
  
  writeStr("Enter up to 32-bit hex number: ");
  readLn(theString, 9);
  theNumber = hexToInt(theString);

  printf("The integer is: %i\n", theNumber);

  return 0;
}

Listing 14.3.1. Program to input a hexadecimal text string from the keyboard and convert it to the corresponding integer. Calls the hexToInt function in Listing 14.3.3. (C)

/* hexToInt.h
 * Converts hex character string to int.
 * 2017-09-29: Bob Plantz
 */
 
#ifndef HEXTOINT_H
#define HEXTOINT_H
int hexToInt(char *);
#endif

Listing 14.3.2. Header file for the hexToInt function in Listing 14.3.3. (C)

/* hexToInt.c
 * Converts hex character string to int.
 * 2017-09-29: Bob Plantz
 */
 
#include "hexToInt.h"
#define GAP 7
#define NO_ASCII 0xf

int hexToInt(char *stringPtr)
{
  int accumulator = 0;
  char current;

  current = *stringPtr;
  
  while (current != '\0') {
    accumulator = accumulator << 4;
    if (current > '9')     // check for alpha
      current -= GAP;
    current &= NO_ASCII;   // strip ASCII part
    accumulator += (int)current;
    stringPtr++;
    current = *stringPtr;
  }
  return accumulator;
}

Listing 14.3.3. Function to convert a hexadecimal text string to an integer. (C)

The compiler-generated assembly language for the conversion algorithm is shown in Listing 14.3.4.

        .arch   armv6
        .file   "hexToInt1.c"
        .text
        .align  2
        .global hexToInt
        .syntax unified
        .arm
        .fpu    vfp
        .type   hexToInt, %function
hexToInt:
        @ args = 0, pretend = 0, frame = 16
        @ frame_needed = 1, uses_anonymous_args = 0
        @ link register save eliminated.
        str     fp, [sp, #-4]!
        add     fp, sp, #0
        sub     sp, sp, #20
        str     r0, [fp, #-16]
        mov     r3, #0
        str     r3, [fp, #-8]
        ldr     r3, [fp, #-16]
        ldrb    r3, [r3]
        strb    r3, [fp, #-9]
        b       .L2
.L4:
        ldr     r3, [fp, #-8]
        mov     r3, r3, asl #4  @@ left shift accumulator
        str     r3, [fp, #-8]
        ldrb    r3, [fp, #-9]        @ zero_extendqisi2
        cmp     r3, #57         @@ check for alpha
        bls     .L3
        ldrb    r3, [fp, #-9]
        sub     r3, r3, #7      @@ alpha, remove gap
        strb    r3, [fp, #-9]
.L3:
        ldrb    r3, [fp, #-9]
        and     r3, r3, #15     @@ mask off ASCII part
        strb    r3, [fp, #-9]
        ldrb    r3, [fp, #-9]        @ zero_extendqisi2
        ldr     r2, [fp, #-8]
        add     r3, r2, r3      @@ add in new four bits
        str     r3, [fp, #-8]
        ldr     r3, [fp, #-16]
        add     r3, r3, #1      @@ increment string pointer
        str     r3, [fp, #-16]
        ldr     r3, [fp, #-16]
        ldrb    r3, [r3]
        strb    r3, [fp, #-9]
.L2:
        ldrb    r3, [fp, #-9]        @ zero_extendqisi2
        cmp     r3, #0
        bne     .L4
        ldr     r3, [fp, #-8]
        mov     r0, r3
        sub     sp, fp, #0
        @ sp needed
        ldr     fp, [sp], #4
        bx      lr
        .ident  "GCC: (Raspbian 6.3.0-18+rpi1) 6.3.0 20170516"

Listing 14.3.4. Function to convert a hexadecimal text string to an integer. (gcc asm)

The algorithm used by the function in Listing 14.3.1 is straightforward, but it uses local variables on the stack and does not take advantage of the conditional execution feature of the ARM architecture. My assembly language solution in Listing 14.3.5 uses registers for local variables and the conditional execution option to implement a simple if-else construct.

@ hexToInt2.s
@ Converts a hex text string to an int.
@ Calling sequence:
@       r0 <- address of string
@       bl hexToInt
@ returns equivalent int
@ 2017-09-29: Bob Plantz

@ Define my Raspberry Pi
        .cpu    cortex-a53
        .fpu    neon-fp-armv8
        .syntax unified         @ modern syntax

@ Constant for assembler
        .equ    gap,7   @ between alpha and numerical
        .equ    NUL,0
        .equ    no_ascii,0xf

@ The program
        .text
        .align  2
        .global hexToInt
        .type   hexToInt, %function
hexToInt:
        sub     sp, sp, 24      @ space for saving regs
                                @ (keeping 8-byte sp align)
        str     r4, [sp, 4]     @ save r4
        str     r5, [sp, 8]     @      r5
        str     r6, [sp,12]     @      r6
        str     fp, [sp, 16]    @      fp
        str     lr, [sp, 20]    @      lr
        add     fp, sp, 20      @ set our frame pointer
        
        mov     r4, r0          @ string pointer
        mov     r5, 0           @ accumulator = 0;
loop:
        ldrb    r6, [r4]        @ get char
        cmp     r6, NUL         @ end of string?
        beq     allDone         @ yes
        lsl     r5, r5, 4       @ room for four bits
        cmp     r6, '9          @ alpha char?
        subhi   r6, r6, gap     @ yes, remove gap
        and     r6, r6, no_ascii  @ strip off acsii
        add     r5, r5, r6      @ add in the four bits
        add     r4, r4, 1       @ next char
        b       loop
allDone:        
        mov     r0, r5          @ return accumulator;
        ldr     r4, [sp, 4]     @ restore r4
        ldr     r5, [sp, 8]     @      r5
        ldr     r6, [sp,12]     @      r6
        ldr     fp, [sp, 16]    @      fp
        ldr     lr, [sp, 20]    @      lr
        add     sp, sp, 24      @      sp
        bx      lr              @ return

Listing 14.3.5. Function to convert a hexadecimal text string to an integer (prog asm).

The cmp instruction in the sequence:

cmp     r6, '9          @ alpha char?
subhi   r6, r6, gap     @ yes, remove gap
and     r6, r6, no_ascii  @ strip off acsii

compares the current character with the ASCII ‘9’. The sub instruction includes the hi option, so it is only executed if the character is higher in the ASCII sequence than a ‘9’. Thus the gap in the ASCII code between ‘9’ and ‘a’ is only subtracted if the character is a hexadecimal alpha character.

Conversion of an integer to the hex text string that represents it is a little more complex. We need to allocate memory space for the text string. The program in Listing 14.3.6 asks the user to enter a hexadecimal number, adds \(1\) to the number, and displays the result in hexadecimal. This problem could, of course, be solved using only hexadecimal characters, but the addition is made much simpler by converting to the binary integer format, and then converting the result to hexadecimal characters.

@ incrementHex.s
@ Prompts user for hex number and adds 1 to it
@ 2017-09-29: Bob Plantz

@ Define my Raspberry Pi
        .cpu    cortex-a53
        .fpu    neon-fp-armv8
        .syntax unified         @ modern syntax

@ Constant for assembler
        .equ    maxChars,9      @ max input chars
        .equ    inString,-16    @ for input string
        .equ    outString,-28   @ for output string
        .equ    locals,24       @ space for local vars

@ Constant program data
        .section .rodata
        .align  2
prompt:
        .asciz        "Enter up to 32-bit hex number: "
display:
        .asciz        "Adding 1 gives: "

@ The program
        .text
        .align  2
        .global main
        .type   main, %function
main:
        sub     sp, sp, 8       @ space for fp, lr
        str     fp, [sp, 0]     @ save fp
        str     lr, [sp, 4]     @   and lr
        add     fp, sp, 4       @ set our frame pointer
        sub     sp, sp, locals  @ for local vars
        
        ldr     r0, promptAddr  @ prompt user
        bl      writeStr
        
        add     r0, fp, inString  @ place for user input
        mov     r1, maxChars    @ limit input size
        bl      readLn
        
        add     r0, fp, inString  @ user input
        bl      hexToInt        @ convert it

        add     r1, r0, 1       @ add one to the int
        add     r0, fp, outString  @ place for result
        bl      intToHex        @ convert to string
        
        ldr     r0, displayAddr @ show user result
        bl      writeStr
        
        add     r0, fp, outString
        bl      writeStr
        
        bl      newLine         @ looks nicer
        
        mov     r0, 0           @ return 0;
        add     sp, sp, locals  @ deallocate local var
        ldr     fp, [sp, 0]     @ restore caller fp
        ldr     lr, [sp, 4]     @       lr
        add     sp, sp, 8       @   and sp
        bx      lr              @ return

promptAddr:
        .word    prompt
displayAddr:
        .word    display

Listing 14.3.6. Program to increment a hexadecimal number by one. The intToHex function is shown in Listing 14.3.7 and the hexToInt function in Listing 14.3.5. (prog asm)

@ intToHex.s
@ Converts 32-bit int to a hex text string.
@ Calling sequence:
@       r0 <- address of place to store string
@       r1 <- int to convert
@       bl intToHex
@ returns equivalent int
@ 2017-09-29: Bob Plantz

@ Define my Raspberry Pi
        .cpu    cortex-a53
        .fpu    neon-fp-armv8
        .syntax unified         @ modern syntax

@ Constant for assembler
        .equ    gap,7   @ between alpha and numerical
        .equ    to_ascii,0x30
        .equ    NUL,0   @ NUL for end of string

@ The program
        .text
        .align  2
        .global intToHex
        .type   intToHex, %function
intToHex:
        sub     sp, sp, 24      @ space for saving regs
                                @ (keeping 8-byte sp align)
        str     r4, [sp, 4]     @ save r4
        str     r5, [sp, 8]     @      r5
        str     r6, [sp,12]     @      r6
        str     fp, [sp, 16]    @      fp
        str     lr, [sp, 20]    @      lr
        add     fp, sp, 20      @ set our frame pointer
        
        mov     r4, r0          @ string pointer
        mov     r5, r1          @ number to convert
        mov     r6, 0           @ counter = 0;
        
        mov     r0, '0          @ hex prefix in string
        strb    r0, [r4]        @ store the char
        add     r4, r4, 1       @ next char
        mov     r0, 'x
        strb    r0, [r4]        @ store the char
        add     r4, r4, 1
loop:
        cmp     r6, 8           @ all bits?
        beq     allDone         @ yes
        ror     r5, r5, 28      @ no, get next 4 bits
        and     r0, r5, 0xf     @ isolate the four bits
        cmp     r0, 9           @ need alpha char?
        addhi   r0, r0, gap     @ yes, add gap
        add     r0, r0, to_ascii  @ convert to acsii
        strb    r0, [r4]        @ store the char
        add     r4, r4, 1       @ next char location
        add     r6, r6, 1       @ next four bits
        b       loop
allDone:
        mov     r0, NUL        
        strb    r0, [r4]        @ NUL char
        
        mov     r0, 0           @ return 0;
        ldr     r4, [sp, 4]     @ restore r4
        ldr     r5, [sp, 8]     @      r5
        ldr     r6, [sp,12]     @      r6
        ldr     fp, [sp, 16]    @      fp
        ldr     lr, [sp, 20]    @      lr
        add     sp, sp, 24      @      sp
        bx      lr              @ return

Listing 14.3.7. The intToHex function converts a 32-bit int to the corresponding hexadecimal text string.

The text string must be ordered from left to right, so we start with the high-order four bits. The ror instruction here:

ror     r5, r5, 28      @ no, get next 4 bits
and     r0, r5, 0xf     @ isolate the four bits

moves the high-order four bits into the lowest four-bit position in the register, while keeping the 32-bit pattern the same. We isolate the four bits with the and instruction and place the result in r0, where we can “build” the ASCII character. Some instruction set architectures have a rotate left instruction (e.g., rol on the Intel x86) but it really is not needed because rotation is a circular operation.