Chris Johnson
After I submitted the last article, I think that Paul gently hinted it might have been a wee bit on the long side, especially as there were several other articles devoted to other aspects of programming in the same issue. Therefore I have lowered my sights a little for this month, and will deal only with shifting and rotating.
Shifting and rotating
We have alluded several times, in past articles, to the process of shifting bits around within a register. It is time we looked at this in more detail. The first thing to do is to differentiate between a shift and a rotate.
Shifts
In the case of a shift, we move the bits either to the left or the right, and the bits that 'fall out' are lost for ever, except for the last one, which is copied into the carry flag. At the other end, zero bits are moved in. Perhaps a small diagram would make it easier to appreciate. To keep things simple, we will use a 4-bit register and carry out a left shift by two bits. I will designate the original contents with letters a to d, although in reality the bits can only be 0 or 1.
Before the shift:
After a left shift by two bits:
You can see that the original bit-a has been lost completely, bit-b is now in the carry, and two zero bits have been moved into the two low positions. With the ARM, all shifts and rotations, left or right, can be by any number of bits from 1 - 31. A zero or 32-bit shift has no effect. If higher numbers are used, the value is reduced modulo 32 to bring it within the range of the 32-bit register.
A shift of one bit to the left has the effect of multiplying the value by 2, and a shift of one bit to the right has the effect of doing a DIV 2. The >> and << operators may be familiar to Basic programmers.
Rotations
Rotations differ from shifts in that bits that fall out at one end are fed back in the other end. For a left rotation by two bits, we would have the following situation.
Before the rotation:
After a left rotation by two bits:
Note that, not only are the bits which fall out fed back in at the other end, but the carry still retains a copy of the last bit to be rotated.
The ARM implementation
There aren't any instructions that specifically carry out shifts or rotations. In the ARM instruction set, which we have given in general terms as:
opcode, destination, lhs, rhs
the rhs part of the instruction can contain a shift/rotate suffix, where the number of bits to shift/rotate can be given as an immediate constant, or as the contents of a register, and the shift operates on the rhs operand. The actual contents of the rhs register are not changed by the shift/rotate, only the value which is actually passed to the barrel shifter. We will have a few examples in a while, but first the full list of possible operations.
LSL #n Logical shift left immediate
We essentially used this as the example of a shift above. After an n-bit shift to the left, n zeros have been shifted in on the right, n bits have been shifted out at the left, and the carry contains a copy of bit (32-n) of the original value.
If no shift is specified in the instruction, as will apply to the majority of instructions, then the assembler defaults to using LSL #0, which of course does nothing.
LSR #n Logical shift right immediate
This is the analogous instruction, except that the bits are shifted in the opposite direction. After an n-bit shift to the right, n zero bits have been shifted in at the left, n bits have been shifted out at the left, and the carry now contains a copy of bit (n-1) of the original value.
ASL #n Arithmetic shift left immediate
This instruction is identical in effect to LSL #n, and is present because of the symmetry of the instruction set.
ASR #n Arithmetic shift right immediate
This instruction is used when the value being shifted is to be treated as a signed integer. Remember that, in the representation of signed integers, bit 31, the top bit, is used as the 'negative' flag. In order for a right shift to correctly deal with a negative number, we cannot simply shift zeros in at the left hand end, since this would immediately make the value positive. This instruction shifts in bits that are the same as the original bit 31. Thus if the number started out as a positive number, then zeros are shifted in at the left as before (equivalent to LSR #n), but if it started out as a negative number, then 1's are shifted in at the left. This then makes the operation DIV 2 work correctly for a negative number.
ROR #n Rotate right immediate
A rotate right moves bits out of the right hand end and reinserts them in at the left hand end. A copy of the last bit to be shifted remains in the carry flag, as with the other instructions. The number of shifts allowed is in the range 1 - 31 bits. There is no necessity for a corresponding rotate left instruction, since a rotate left by n positions would be the same as a rotate right by (32-n) positions.
RRX Rotate right by one bit with extend
This is a special case of the rotate right. It shifts by one bit only. The old bit 0 moves into the carry flag, and the old content of the carry flag is moved into the bit 31. This is the only instruction in which the content of the carry flag is moved into the register.
There is no corresponding left rotate instruction RLX. However, the same operation can be carried out by making use of the instruction:
ADCS R0, R0, R0
Adding R0 to R0 will effectively multiply R0 by 2 (shift left by 1 bit), ADC adds in the content of the carry flag to bit 0, and the carry flag will be set if the addition overflows, i.e. if the original bit 31 was 1.
Specifying the shift by use of a register
The following instructions may all use the contents of a register to specify the number of bits to be shifted.
LSL Rx LSR Rx ASL Rx ASR Rx ROR Rx
Some examples of usage
If we simply need to shift a register's contents, a MOV instruction is required.
MOV R0,R0,LSL #4 ; R0=R0*16
Note we have to use the # symbol to denote an immediate constant. To specify a shift/rotate by the contents of a register, we could use an instruction of the form:
MOV R0,R0,LSL R2
On the earlier ARM chips, the multiply instruction, MUL, could take a large number of clock cycles, and hence could be slow. It is possible to use shifts to carry out fast multiply or divide, but only for a restricted range of multipliers. A simple left or right shift will carry out a multiplication or divide of 2^N, where N is the number of bits shifted. One must be careful to make sure that significant bits are not being lost, of course. For example, a multiply by 8 could be accomplished by:
MOV R0,R0,LSL #3
One could multiply by 9 or 7 by using:
ADD R1,R0,R0,LSL #3 ; R1=R0*8+R0=R0*9 RSB R1,R0,R0,LSL #3 ; R1=R0*8-R0=R0*7
In the latter case, we must use RSB which gives the result rhs - lhs. SUB would do lhs - rhs which would be R0 - R0*8. These instructions would execute faster than a simple MUL. It is possible to do more complicated multiplies in more than one instruction. For example, 640 is a number that would often be required as a multiplier (e.g. for calculating pixel addresses in 640×480 screen modes, and also in the interconversion of os units and millipoints). Now 640 = 512 + 128, and both the latter can be done with simple shifts.
MOV R1,R0,LSL #9 ; R1=R0*512
ADD R1,R1,R0,LSL #7 ; R1=R1+R0*128
Such sequences are possible because the use of the barrel shifter does not corrupt the value held in the register being shifted. Continuing the same theme, 480 = 512 - 32. Therefore, to multiply by 480, we would use the two instructions:
MOV R1,R0,LSL #9 ; R1=R0*512
SUB R1,R1,R0,LSL #5 ; R1=R1-R0*32
Similar constructs could be used to carry out divides, the only difference being that right shifts would be used to do the division.
Random numbers
There are lots of things we take for granted when using high level languages. One of these is a random number generator. So, to finish off, I will outline briefly one way of generating random numbers in assembler. The full program, and more description, is on the monthly disc.
This random number generator is based upon a linear feedback shift register, which consists of taking a seed binary number, EORing selected bits together to produce a 'random' bit, shifting the original number by one bit, and feeding the generated random bit back into the original number. A number of these random bits can be combined to produce a random number. The theory of random number generation has been discussed by many authors, e.g. in Numerical Recipes for C/Pascal/Fortran, or Semi-numerical Algorithms by the C guru, Knuth, and often in magazines such as Doctor Dobb's Journal. The method used here seems as good as any, in that no computer algorithm can be truly random. The core of the program makes use of lots of shifts, which is appropriate for this part of this series of articles. The linear feedback shift register is R0, and it is initially seeded (once) from the system clock, which counts in centiseconds from the last reset.
.makenumber
MOV R2,#6 ; Counter for number ; of bits
MOV R3,#0 ; Register to
; construct number
.getnextbit
MOV R3,R3,LSL#1 ; move current bits
; to left ready
; for next bit
MOV R4,R0,LSR#31 ; Top bit of LFSR to
; bit 0 of R4
; Now EOR with
; various bits to get
; the "random" bit
EOR R4,R4,R0,LSR#6
EOR R4,R4,R0,LSR#4
EOR R4,R4,R0,LSR#2
EOR R4,R4,R0,LSR#1
EOR R4,R4,R0
AND R4,R4,#1 ; discard all except
; bit 0
MOV R0,R0,LSR#1 ; move LFSR to right
; one bit
ORR R0,R0,R4,LSL#31
; insert new bit 31
; into LFSR
ORR R3,R3,R4 ; insert new bit as
; bit 0 in number
SUBS R2,R2,#1 ; decrease bit
; counter
BNE getnextbit ; go round again if
; more bits to get
; we now have a
; random 6 bit number
; i.e. 0 - 64
The full program generates six numbers between 1 and 49 (for the lottery). However, it could be easily modified to pick eight draws, or whatever else takes your fancy. I also include on the disc a modified form of the program, which constructs, say, a million random numbers, keeping a count of how many times each number is chosen, so you can investigate how random is random - it takes only a second or so running in a task window with a StrongARM!
It was while playing around with these programs that I began to realise the ease of use and potential of task windows. It was extremely easy to run the program to generate, say, a million or so random numbers and print out the distribution, save the task window directly into edit, strip off the garbage at the top and bottom of the file, then pass the CSV file straight from Edit into my own Graphdraw, and produce a graphical display of the even distribution - a few seconds from start to finish. Now who wants to trade in for a Windows PC?
Next month
Next month we shall start to look at transferring data to and from memory.