CIS-77 Home http://www.c-jump.com/CIS77/CIS77syllabus.htm

Lab M10. Integer Arithmetic Part 1: High-speed Multiplication and Division

1. Lab Description
2. SHL Instruction
3. SHL Operands
4. SHL Example
5. Fast Multiplication and Division
6. Extended-Precision Integers and Shifting Multiple Doublewords
7. Displaying Binary Bits
8. Assignment: High-speed Multiplication of 32-bit Integer by Powers of 2

1. Lab Description

• The purpose of this assignment is to experiment with the properties of various bit shifting instructions.

• You can continue using Microsoft VC++ project created in your previous MASM assignment.

• Advantage of Microsoft VC++ project is that it provides a quick-and-easy way to debug and step-thru your programs.

• Alternatively, you can use a notepad or some other text editor to write your code, assemble and link on the command line, and use OllyDbg to debug your code.

   

2. SHL Instruction

• Recall that SHL (shift left) instruction performs a logical left shift on the destination operand:

  • The lowest bit is filled with zero.

  • The highest bit is moved to the carry flag.

  • The bit that was in the carry flag is lost.

     

   

3. SHL Operands

• The first operand of SHL is the destination.

• The second operand is the shift count:

  • SHL destination, count

• The count operand can be an immediate value or register CL.

• The following operand types are permitted:

      SHL  reg, imm8
      SHL  mem, imm8
      SHL  reg, CL
      SHL  mem, CL
  

   

   

4. SHL Example

•     mov bl, 8Fh ; BL == 10001111b
  
      shl bl, l   ; BL == 00011110b, CF = 1
  

   

   

5. Fast Multiplication and Division

• One of the best uses of SHL is performing high-speed multiplication by powers of 2.

• Shifting any operand left by n bits multiplies the operand by 2ⁿ.

• For example, shifting a VALUE one bit to the left yields the product

  • VALUE * 2

• Shifting a VALUE two bits to the left yields the product of

  • VALUE * 4

  and so on.

      mov eax, 10
      shl eax, 2   ; 10 * 22 == 10 * 4 == 40
  

• Shifts are more efficient to execute than the corresponding multiplication or division instructions. Some multiplication instructions could take more than 10 clock cycles. By contrast, SHL executes in just one clock cycle, and requires fewer bytes to encode. Whenever possible, use the shift instructions to perform multiplication and division by a power of two.

   

6. Extended-Precision Integers and Shifting Multiple Doublewords

• Extended-precision integers can be stored as divided into an array of doublewords.

• The low-order doubleword is stored at the lowest address (using little-endian order).

• The following steps, for example, show how to shift an integer named dw_array one bit to the right:

      .CONST
          ARRAY_SIZE = 3
      .DATA           ; Begin data segment
          dw_array    DWORD   ARRAY_SIZE  dup(99999999h)  ; 1001 pattern...
      .CODE           ; Begin code segment
      ; Shift doublewords 1 bit to the right:
          mov esi, 0                     ; 10011001... Original pattern
          shr dw_array[ esi + 8 ], 1     ; 01001100... highest dword -> CF
          rcr dw_array[ esi + 4 ], 1     ; 11001100... CF -> middle dword -> CF
          rcr dw_array[ esi ], 1         ; 11001100... CF -> lowest dword -> CF
  

• Shifting any operand right by n bits divides the operand by 2ⁿ.

• The steps are:

  1. Set ESI to the offset of array.

  2. The high-order doubleword at [ ESI + 8 ] is shifted right,
     its lowest bit is copied into the Carry flag:

      

  3. The value at [ ESI + 4 ] is shifted right,

     1. the highest bit is filled from the Carry flag,

     2. the lowest bit is copied back into the Carry flag:

      

  4. The low-order doubleword at [ ESI ] is shifted right in a similar way.

  5. At the end, carry flag CF can be inspected for the remainder of the division.

   

7. Displaying Binary Bits

• A good way to apply the shift instructions is to display bytes of ASCII strings in binary format.

• For example, if SHL is used,

   

  the highest bit of the operand is copied into the Carry flag each time the byte is shifted to the left.

• The following program displays each of the bits in EAX:

      .DATA                            ; Begin data segment
          Value   DWORD   1234ABCDh    ; sample binary value
          buffer  BYTE    32 dup(0), 0 ; output buffer
  
      .CODE                       ; Begin code segment
          mov eax, Value          ; value to display
          mov ecx,32              ; number of bits in EAX
          mov esi, OFFSET buffer
      next_bit:
          shl eax, 1              ; shift high bit into Carry flag
          mov BYTE PTR [esi], '0' ; display zero by default
          jnc next_byte           ; if no Carry, advance to next byte
          mov BYTE PTR [esi], '1' ; otherwise display 1
      next_byte:
          inc esi                 ; next buffer position
          loop next_bit           ; shift another bit to left
          ; Display output buffer on the screen...
          ; ...
  

   

8. Assignment: High-speed Multiplication of 32-bit Integer by Powers of 2

• Every CPU instruction in your program must have a brief comment!
  The penalty for not following this rule is 15 pts deduction...

• Consider arithmetic multiplication

      product = multiplier × multiplicand
  

• With that in mind, write a program to execute an endless loop of the following steps:

  1. Ask the user to enter unsigned integer multiplier and store it as a DWORD (doubleword) value in memory.

  2. Display entered doubleword in binary format.

  3. Ask the user to enter three single-digit integer multiplicands and store them as BYTE-sized values k, m, and n.
     

     • Although single-letter identifiers are used in this problem description, it is highly advisable to employ more descriptive names in the code, such as

           .DATA
           k_multiplicand BYTE ?
           m_multiplicand BYTE ?
           n_multiplicand BYTE ?
       

       or an array of bytes

           .DATA
           multiplicand  BYTE  3  dup(?)
       

  4. Use ADD and SHL instructions to calculate the product

     • multiplier × ( 2^k + 2^m + 2ⁿ )

     Please note that

     • (a)  Multiplication by SHL is done in place: the product is obtained by shifting the bits of the multiplier.

     • (b)  2⁰ yields 1.

  5. Display 32-bit result of the "fast multiplication" in both decimal and binary form.

  6. Optional (15 xtra pts.) Add logic to detect multiplication overflow. Hint: use CMP instruction to compare DWORD value before and after multiplication.

  7. Optional (25 xtra pts.) Add logic to scale input of multiplicands k, m, and n (strictly speaking, multiplicands are 2^k, 2^m, and 2ⁿ)

     • Accept input of just one, or two, or all three of the multiplicands.

     • Any solution is accepted for extra credit.

     • For example, a non-digit character such as 'x' might signal the end of multiplicand input, so the program could proceed to the calculation step using shorter list of multiplicands.

  8. Any additional features in your program must be thoroughly commented and will yield bonus credit pts.

   

• What to submit:

  • Submit only your ASM source (not the EXE or project.)