Page 1 of 1

MASM : 1024-bit Arithmetic Functions

#1 Martyn.Rae  Icon User is offline

  • The programming dinosaur
  • member icon

Reputation: 540
  • View blog
  • Posts: 1,406
  • Joined: 22-August 09

Posted 28 March 2011 - 11:11 AM

MASM : 1024-bit Arithmetic Functions - Addition and Subtraction

Introduction

The ability to provide arithmetic on integers larger than the CPU register width has always provided me with endless hours of fun in assembly. Being a kind and generous person, I have decided to share that enjoyment with you all, by providing a set of three tutorials on addition, subtraction, multiplication and division on binary numbers that are very stupidly large!

This first tutorial concerns itself with 1024-bit addition and subtraction and is, probably the easiest to implement in assembly. The second tutorial covers 512-bit multiplication providing a 1024-bit result and finally the third tutorial covers 1024-bit division providing a 1024 bit result and 1024 bit remainder.

1024-bit Addition

There are two problems that face us when we attempt to add two numbers together that are larger than the CPU register width.

The first is that of carry. The X86-64 machine code instruction set has two instructions that solve this problem, namely add and adc. The add instruction is used on the least significant n-bits (where n is the width of the CPU register - in our case 32). This may or may not produce a carry bit, which needs to be used with the next n-bits of the computation, hence the use of the adc instruction which is add with carry.

The next problem is that if we use a loop to control the number of additions we perform, the controlling register will need to be decremented which will affect the carry flag. Therefore for each iteration of the loop we need to use the pushf and popf instructions which saves the conditional flags onto the stack and restores them.

Add1024				proc		num1:dword, num2:dword, result:dword

					push		ecx
					mov			esi, num1
					mov			ebx, num2
					mov			edi, result
					mov			ecx, 32
					mov			eax, dword ptr [esi+ecx*4-4]
					add			eax, dword ptr [ebx+ecx*4-4]
					mov			dword ptr [edi+ecx*4-4], eax
					pushf
					dec			ecx
Add1024_loop:		popf
					mov			eax, dword ptr [esi+ecx*4-4]
					adc			eax, dword ptr [ebx+ecx*4-4]
					mov			dword ptr [edi+ecx*4-4], eax
					pushf
					dec			ecx
					jnz			Add1024_loop
					popf
					pop			ecx
					ret

Add1024				endp



1024-bit Subtraction

As with addition, subtraction needs to take into account the borrow bit. Again, the X86-64 machine code instruction set has two instructions that solve this problem, namely sub and sbb. The sub instruction is used on the least significant n-bits (where n is the width of the CPU register - in our case 32). This may or may not produce a borrow bit, which needs to be used with the next n-bits of the computation, hence the use of the sbb instruction which is subtract with borrow.

Sub1024				proc		num1:dword, num2:dword, result:dword

					push		ecx
					mov			esi, num1
					mov			ebx, num2
					mov			edi, result
					mov			ecx, 32
					mov			eax, dword ptr [esi+ecx*4-4]
					sub			eax, dword ptr [ebx+ecx*4-4]
					mov			dword ptr [edi+ecx*4-4], eax
					pushf
					dec			ecx
Sub1024_loop:		popf
					mov			eax, dword ptr [esi+ecx*4-4]
					sbb			eax, dword ptr [ebx+ecx*4-4]
					mov			dword ptr [edi+ecx*4-4], eax
					pushf
					dec			ecx
					jnz			Sub1024_loop
					popf
					pop			ecx
					ret

Sub1024				endp



Part II of this tutorial can be found here

This post has been edited by Martyn.Rae: 29 March 2011 - 11:33 AM


Is This A Good Question/Topic? 1
  • +

Page 1 of 1