= Multiplication and Division =

0. Integer Arithmetic

Integer Arithmetic

• Multiplication and Division Instructions
• Extended Addition and Subtraction
• Shift and Rotate Instructions & Applications
  • Strong instructions that are used in many applications.
• ASCII and Packed Decimal Arithmetic : 10진수 계산하는데 사용한다.
  • These are for decimal arithmetic

1. Multiplication and Division

Multiplication and Division Instructions

• MUL Instruction(unsigned)
• IMUL Instruction(signed)
• DIV Instruction(unsigned)
• Signed Integer Division
• CBW, CWD, CDQ Instructions
• IDIV Instruction(signed)
• Implementing Arithmetic Expressions

MUL Instruction

• The MUL (unsigned multiply) instruction multiplies an 8-, 16-, or 32-bit operand(multiplier) by either AL, AX, or EAX(multiplicand).

• Instruction format:
  
  MUL은 연산자가 하나뿐인대신에 multiplicand를 반드시 eax에 저장해야만 한다.

• Implied Operands
  

• The product is the concatenation of productH and productL. That is, edx:eax (32 bit), dx:ax (16bit), ah:al (8 bit).

• CF = 1 if the product does not fit into productL (i.e. if productH != 0) : 결과값이 32bit수보다 클때 CF = 1이 된다.

• Examples
  

IMUL Instruction

음수를 포함한 수를 곱할때 필요한 명령어

eax와의 연산만이 아닌 레지스터끼리의 곱, eax가아닌 다른 레지스터와 메모리의 곱, 상수와의 곱을 가능하게한다.

총 3가지 종류의 연산을 할 수 있다는 특징이 있다.

• There are three IMUL formats.

• Single Operand Formats (The same as MUL except flag setting) : dest의 비트수가 2배로 된다.
  
  만약에 edx:eax(32bit) 메모리에서 edx가 sign extension이 아니면(eax MSB와 같지 안으면) CF = OF = 1로 만들어준다.

• Two Operand Formats : 여기는 bit 수가 동일하다.
  
  첫번째와 두번째 인자가 곱해져서 첫번째 인자로 들어간다. 그래서 첫번째 인자는 반드시 레지스터여야 한다.

• Three Operand Formats
  
  두번째 인자와 세번째 인자가 곱해져서 첫번째 인자에 들어가게 된다.

OF = CF = 1 if the product does not fit to the destination
in both two and three operand formats.
floating point일때는 가속기 이용한다.

• Examples
  

64 bit MUL / IMUL Instructions (in 64 bit mode)

• MUL Instruction in 64 bit mode

  • 64 bit x 64 bit = 128 bits product in RDX:RAX (CF = 1 if RDX != 0).
  • Format: MUL r/m64
  • Example
    

• IMUL Instruction in 64 bit mode

  • Single, two and three operands formats are all possible.
  • Example
    

DIV Instruction

• The DIV (unsigned divide) instruction performs 8-bit, 16-bit, and 32-bit division on unsigned integers

• Instruction format: DIV divisor (divisior은 immediate 불가능)

• Implied Operands
  
  표를 반드시 기억하고 있자

• Examples
  

마지막은 ax에 들어갈 수 없는 크기이기 때문에 OF 가 생긴다.

Signed Integer Division

나눗셈을 하기 전에 먼저 sign-extension을 해주어야 한다.

• Signed integers must be sign-extended before division.
• That is, fill high byte / word / doubleword with a copy of the low byte / word / doubleword's sign bit.
  
• Instructions providing the sign-extension operations.
  • CBW (convert byte to word) extends AL into AH : AL을 AH로 sign extension 해준다.
  • CWD (convert word to doubleword) extends AX into DX
  • CDQ (convert dword to qword) extends EAX into EDX
  • Example
    

만약 위의 함수가 기억이 안난다면 다음과 같이 할 수 있을 것이다.

mov edx, 0 ; = xor edx, edx
test eax, 80000000h
jz positive
mov edx, 0ffffffffh
positive:

그러니 그냥 함수를 외우자

IDIV Instruction

• IDIV (signed divide) performs signed integer division.

• The same syntax and operands as in DIV instruction.

• Examples:
  

• Examples:
  

2. Implementing Arithmetic Expressions

Unsigned Arithmetic Expressions

• Example: var4 = (var1 + var2) * var3
  

이건 overflow가 없다고 가정한다. 만약 있다면 CF = 1인지 체크해야 한다.

Signed Arithmetic Expressions

• eax = (ebx * 20) / ecx
  
  이미 곱한 시점에서 edx:eax가 나눌 값으로 가기때문에 굳이 확장해줄 필요가 없다.

• eax = (-var1 * var2) + var3
  

jo는 OF 생기면 TooBig으로 간다.

• Signed Arithmetic Expressions Examples (계속)

  • We now assume that no overflow occurs during the calculation.
  • var4 = (var1 * 5) / (var2 - 3)
    

  이미 곱셈과정에서 확장이 되었기에 cbq같은게 필요없다.

  • var4 = (var1 * -5) / (-var2 % var3)
    뒷부분먼저한 모습이다.
    

  • eax = (ecx * edx)/eax

    • Do not modify the values of all registers except EAX. : EAX 뺴놓고 레지스터 값을 바꾸지 마라
      

  • var3 = (var1 * -var2)/(var3 – ebx)

    • Do not modify any variables other than var3.
      

3. Extended Addition and Subtraction

• Extended Addition and Subtraction
  • ADC Instruction : 하위 비트에서 carry가 올라갈때마다 carry와 함께 덧셈이 필요하게 된다.
  • Extended Precision Addition
  • SBB Instruction
  • Extended Precision Subtraction
  • Note: ADC and SBB are not applicable in 64-bit mode programming. : 오직 32bit 모드에서만 사용할 수 있다.

ADC Instruction

사이즈가 큰 WORD를 더할때 ADC를 통해서 low에서 올라온 carry bit를 반영해서 더할 수 있게 된다.

즉 add와 기능은 같지만, carry를 포함해서 덧셈을 하기 때문에 64bit 연산이 가능해진다.

• ADC(add with carry) adds both a source operand and the contents of the Carry flag to a destination operand.
  

• The same syntax as ADD, SUB, etc.

• Example:

  • Add two 32-bit integers (FFFFFFFFh + FFFFFFFFh), producing a 64-bit sum in EDX:EAX:
    

SBB Instruction

즉 sub와 기능은 같지만, carry를 포함해서 뺄셈을 하기 때문에 64bit 연산이 가능해진다.

• The SBB (subtract with borrow) instruction subtracts both a source operand and the value of the Carry flag from a destination operand.
  
  위와 같이 dest + CF 된 값을 src에 빼주게 된다.

• The same syntax as ADC.

• Example:

  • (EDX:EAX = 0000000700000001h) - 2
    

Extended Precision Arithmetic

해서 위와 같은 명령어들은 multi word 간 연산에 사용될 수 있다.

• Adding/Subtracting two operands that are longer than the computer's word size (32 bits).
  
  해서 위와 같이 long word도 더하거나 뺼 수 있다.

Virtually no limit on the size of operands
Such arithmetic must be performed in steps
The Carry value from each step is passed on to the next step.
ADC and SBB are used for this purpose.

4. Shift and Rotate Instructions

Logical vs Arithmetic Shifts

shift는 word를 왼/오로 이동하는 것을 이야기 한다.
rotate는 한쪽 방향으로 bit들을 돌리는 것이다.

기존 shift를 위해서는 >>와 같은 연산을 사용했다. 하지만 어셈에서는 이와 관련된 명령어가 있다.

SHL and SHR Instruction -> 모자란곳에 0을 추가해준다.(Logical)
SAL and SAR Instructions -> sign을 유지해준다. (A : arithmetic)
ROL and ROR Instruction -> 평범한 rotate
RCL and RCR Instructions -> (C:carry) carry bit를 끼고 rotate한다.

Operand types for shift and rotate instructions:

몇 bit rotate 할지는 imm8(immediate 8bit), CL로 결정된다.
SHLD/SHRD Instructions

Logical vs Arithmetic Shifts

A logical shift fills the newly created bit position with zero:

그럼 unsigned와 같은 경우 shift right k bit는 어떻게 될까? x 2^(-k)의 형태가 된다.
shift left k bit는 x 2^(k)가 된다.

An arithmetic shift fills the newly created bit position with a copy of the number’s sign bit:

11111110을 SAR했을 경우 그 결과는 signed data/2^(k)와 같다.
11111111을 SAR했을 경우 그 결과는 차이가 없다.

11111111을 SAL했을 경우 11111110이 되기 때문에 signed data * 2^k 한것과 같은 결과가 된다.

SHL (Shift Left) Instruction

Performs a logical left shift on the destination operand, filling the lowest bit with 0.

MSB는 carry flag에 들어간다.

Note: Operand Types

Shifting left n bits multiplies the operand by 2^n
Example

SHR (Shift Right) Instruction

Performs a logical right shift on the destination operand. The highest bit position is filled with a zero.

LSB를 CF에 넣는다. 이건 x/2^n 한것과 같은 결과를 낳는다.

Shifting right n bits divides the operand by 2^n
Example

곱하기 나누기, 비트를 알고 싶을때 사용할 수 있다.

SAL / SAR (Shift Arithmetic Left / Right) Instructions

SAL is identical to SHL.

SAL은 SHL과 동일하다.

SAR performs a right arithmetic shift on the destination operand.

sign을 복사한다.

An arithmetic shift preserves the number's sign.
Example

예제가 조금 틀린부분이 있는데 예제 나온 숫자는 -128이다.

Example

ROL / ROR

• ROL(Rotate Left) Instruction

  • Shifts each bit to the left.
  • The highest bit is copied into both the Carry flag and into the lowest bit.
  • No bits are lost.
    
    loop는 각 bit를 check 하더라고 data는 유지하고 싶을때 적당하다.

• ROR (Rotate Right) Instruction

  • Shifts each bit to the right

  • The lowest bit is copied into both the Carry flag and into the highest bit.

  • No bits are lost.
    

  • example
    

RCL / RCR Instruction

• RCL (Rotate Carry Left) Instruction
  • Shifts each bit to the left.
  • Copies the Carry flag to the LSB.
  • Copies the LSB to the Carry flag.
    
• RCR (Rotate Carry Right) Instruction
  • Shifts each bit to the right.
  • Copies the Carry flag to the MSB.
  • Copies the MSB to the Carry flag.
    

Example

clc는 CF 를 0으로 stc는 CF를 1로 만드는 명령어이다.

SHLD / SHRD Instruction

뭉텅이로 이동하는 명령어.

SHLD는 src의 상위를 dest 하위로 옮기는 명령어이다. 그리고 dest의 나머지 부분은 모두 왼쪽으로 옮긴다.

SHRD는 src 하위에서 dest 상위로 뭉텅이 데이터를 옮기고 dest의 남은 부분은 버린다.

이때 src는 변동이 없다.

• Shifts the destination operand a given number of bits to the left / right.

• The bit positions opened up by the shift are filled by the MSBs / LSBs of the source operand.

• The source operand is not affected

• Syntax:
  
  

• Operand types:

  • Source and destination operands can not be 8 bits.
    
    특이한 점은 src, dest는 절때 8bit 짜리를 사용할 수 없다.

• Example
  

4bit를 옮기어서 헥사값을 바꾸는 것도 가능하다.

Summary of Shift and Rotation Instructions

Shift and Rotate Applications

multiple word가 있는데 이것을 shift 하고 싶은 경우

이 경우 lsw 가 low쪽에 있을 것이다.
Shifting Multiple Doublewords
We sometimes use an extended-precision integer that has been divided into an array of bytes, words, or doublewords (little endian order).
Suppose that we shift an array of bytes 1 bit to the right.

Example

• Isolating a Bit String
  Bit String을 Isolationg 하고자 할때

  • We sometimes need to extract a part of bits from a words.
  • Example: data field of MS-DOS files(assume that DX holds the data) : MS-DOS의 날짜는 아래와 같이 되어 있다.
    
    여기에서 Month를 옮기고 싶을때
  • Isolating the month field
    
    위와 같이 일단 shift 한다음에 and 연산으로 필요한 부분만 남기고 저장하면 된다.

• Example (계속)
  
  Day field 혹은 year field를 masking 하는 방법

• Isolating the day field
  

• Isolating the year field
  

• Binary Multiplication
  Computation of variable x constant
  Factor the multiplier into powers of 2 and shift.
  
  변수 x 상수인 경우 상수를 shift를 이용해서 구해도 된다.

The approach of factoring the multiplier in powers of 2 is a good approach when variables are multiplied by a constant.

• Multiply AX by 26, using shifting and addition instructions.
  Hint: 26 = 16 + 8 + 2.
  또 다른 예로 26일 곱하라라는 예제를 봐보자
  

• Displaying Binary Bits
  • Convert each bit to ASCII character.
  • Shift MSB into the Carry flag; If CF = 1, append a "1" character to a string; otherwise, append a "0" character.
  • Repeat in a loop, 32 times.
    

ASCII and Packed Decimal Arithmetic(1)

ASCII and Packed Decimal Arithmetic

초기컴퓨터가 8bit->16bit->32bit->64bit 최대로 저장할 수 있는 데이터가 32bit의 경우 unsigned는 4G이다. -> long long 64bit을 쓰게 된다.

초기 8bit, 16bit는 ASCII list 직접연산, 10진 연산은 instruction을 제공

32bit도 10진 연산이 가능은 했다.

64bit까지도 10진연산 instruction을 제공 하지만 사용하지는 않는다.

• Suppose a program is to input two numbers from the user and add them together(see the in/out example shown below).
  

• We have two options when calculating and displaying the sum:

1. Convert both operands to binary, add the binary values, and convert the sum from binary to ASCII digit strings. : 2진수로 바꾸고 add 하고 이진수를 ASCII 문자열로 바꾼다.
2. Add the digit strings directly by successively adding each pair of ASCII digits ('2' + '6', '0' + '5', etc.). The sum is an ASCII digit string, so it can be directly displayed. : ASCII 두개를 직접더해서 구하기도 한다.

• 두번째 접근 방식으로 연산하기 위한 instruction들이 있다.

ASCII Decimal and Unpacked Decimal

• ASCII Decimal : ASCII를 char string으로 표시

  • A number using ASCII Decimal representation stores a single ASCII digit in each byte
    Example: 5,678 is stored as the following sequence of
    hexadecimal bytes:
    

• Binary-Coded Decimal (BCD)

  • BCD integers use 4 binary bits to represent each decimal digit.

  • Unpacked BCD representation stores a decimal digit in the lower four bits of each byte.
    Example: 5,678 is stored as the following sequence of hexadecimal bytes.
    
    byte당 10진수 숫자 1개. 하지만 이것은 너무 낭비이다.

  • Packed decimal(1) representation stores two decimal digits per byte.
    Example: 12,345,678 can be stored as the following sequence of hexadecimal bytes
    두개씩 짝을 이루어서 나누자
    

(1) Packed decimal is also known as packed BCD.

Instructions for ASCII Decimal Arithmetic

unpacked에도 적용할 수 있다. 안쓸꺼니까 반드시 알아놓을 필요까지는 없다.

• There are four instructions:
  

Instructions for Packed Decimal Arithmetic

DAA (Decimal Adjust After Addition)
Converts the binary result(in AL) of an ADD or ADC operation to packed decimal.
DAS (Decimal Adjust after Subtraction)
Converts the binary result (in AL) of a SUB or SBB operation to packed decimal.