A number of years in the past, I wrote a command-line math program for FreeDOS referred to as VMATH. It was able to performing solely very simple mathematical operations on very small unsigned integers. With some current curiosity in fundamental math within the FreeDOS group, I improved VMATH to supply fundamental math help on signed 64-bit integers.
The means of manipulating huge numbers utilizing solely 16-bit 8086 suitable meeting directions will not be easy. I wish to share some samples of the methods utilized by VMATH. Some of the strategies used are pretty simple to know. Meanwhile, others can appear a bit of unusual. You might even study a wholly new method of performing some fundamental math.
The methods defined right here so as to add, subtract, multiply, and divide 64-bit integers should not restricted to only 64-bits. With a bit of fundamental understanding of meeting, these features may very well be scaled to do math on integers of any bit measurement.
Before digging into these math features, I need to cowl some fundamentals of numbers from the pc’s perspective.
How computer systems learn numbers
An Intel-compatible CPU shops the worth of numbers in bytes from least to most important. Each byte is made up of 8 binary bits and two bytes make up a phrase.
A 64-bit quantity that’s saved in reminiscence makes use of 8 bytes (or 4 phrases). For instance, a worth of 74565 (0x12345 in hexadecimal) appears one thing like this:
as bytes: db 0x45, 0x23, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00
as phrases: dw 0x2345, 0x0001, 0x0000, 0x0000
When studying or writing information to reminiscence, the CPU processes the bytes within the appropriate order. On a processor extra fashionable than an 8086, there will be bigger teams, reminiscent of a quadword which may signify the complete 64-bit integer as 0x0000000000012345.
The 8086 CPU does not perceive such gigantic numbers. When writing a program for FreeDOS, you need one thing that may run on any PC, even an authentic IBM PC 5150. You additionally need to use methods that may be scaled to any measurement integer. The capabilities of a extra fashionable CPU do not likely concern us.
For the aim of doing integer math, the info can signify two various kinds of numbers.
The first is unsigned which makes use of all of its bit to signify a constructive quantity. Their worth will be from 0 as much as (2 ^ (numberofbits) – 1). For instance, 8 bits can have any worth from 0 to 255, with 16 bits starting from 0 to 65535, and so forth.
Signed integers are very comparable. However, essentially the most important little bit of the quantity represents whether or not the quantity is constructive (0) or unfavourable (1). The first portion of the quantity is constructive. It can vary from 0 as much as (2 ^ (numberofbits – 1) – 1). The unfavourable portion follows the constructive, starting from its lowest worth (0-(2 ^ (numberofbits – 1))) as much as -1.
For instance, an 8-bit quantity represents any worth from 0 to 127 within the constructive vary, and -128 by means of -1 within the unfavourable vary. To assist visualize it, think about the byte because the set of numbers [0…127,-128…-1]. Because -128 follows 127 within the set, including 1 to 127 equals -128. While this will likely appear unusual and backward, it really makes doing fundamental math at this degree a lot simpler.
To carry out fundamental addition, subtraction, multiplication, and division of very huge integers, it is best to discover some easy routines to get a quantity’s absolute or unfavourable worth. You will want them when you begin doing math on signed integers.
Absolute and unfavourable values
Getting absolutely the worth of a signed integer will not be as dangerous as it could first appear. Because of how unsigned and signed numbers are represented in reminiscence, there’s a pretty simple resolution. You can merely invert all of the bits of a unfavourable quantity and add 1 to get the consequence.
That would possibly sound odd if you have not labored in binary earlier than, however that’s how works. To offer you an instance, take an 8-bit illustration of a unfavourable quantity, reminiscent of -5. Since it could be close to the top of the [0…127,-128…-1] byte set, it could have a worth of 0xfb in hexadecimal, or 11111011 in binary. If you flip all of the bits, you get 0x04, or 00000100 in binary. Add 1 to that consequence and you’ve got the reply. You simply modified the worth from -5 to +5.
You can write this process in meeting to return absolutely the worth of any 64-bit quantity:
; syntax, NASM for DOS
proc_ABS:
; on entry, the SI register factors to the reminiscence location within the
; information section (DS) for this system containing the 64-bit
; quantity that shall be made constructive.
; On exit, the Carry Flag (CF) is about if ensuing quantity can
; not be made constructive. This solely occurs with most
; unfavourable worth. Otherwise, CF is cleared.; verify most important little bit of highest byte
take a look at [si+7], byte 0x80; if not set, the quantity is constructive
jz .done_ABS; flip all of the bits of phrase #4
not phrase [si+6]
not phrase [si+4] ; phrase #3
not phrase [si+2] ; phrase #2
not phrase [si] ; phrase #1; increment the first phrase
inc phrase [si]; if it didn't roll over again to zero, executed
jnz .done_ABS; increment the 2nd phrase
inc phrase [si+2]; if it rolled over, increment the subsequent phrase
jnz .done_ABS
inc phrase [si+4]
jnz .done_ABS; this can't roll over
inc phrase [si+6]; verify most important bit as soon as extra
take a look at [si+7], byte 0x80; if it isn't set we had been profitable, executed
jz .done_ABS; overflow error, it reverted to Negative
stc; set Carry Flag and return
ret.done_ABS:
; Success, clear Carry Flag and return
clc
ret
As you will have observed within the instance, there is a matter that may happen within the operate. Because of how constructive and unfavourable numbers are represented as binary values, the utmost unfavourable quantity can’t be made constructive. For 8-bit numbers, the utmost unfavourable worth is -128. If you flip the entire bits for -128 (binary 1__0000000), you get 127 (binary 0__1111111) the utmost constructive worth. If you add 1 to that consequence, it would overflow again to the identical unfavourable quantity (-128).
To flip a constructive quantity unfavourable, you possibly can simply repeat the method you used to get absolutely the worth. The instance process could be very comparable, besides you need to be sure that the quantity will not be already unfavourable at first.
; syntax, NASM for DOSproc_NEG:
; on entry, the SI factors to the reminiscence location
; for the quantity to be made unfavourable.
; on exit, the Carry Flag is all the time clear.; verify most important little bit of highest byte
take a look at [si+7], byte 0x80; whether it is set, the quantity is unfavourable
jnz .done_NEGnot phrase [si+6] ; flip all of the bits of phrase #4
not phrase [si+4] ; phrase #3
not phrase [si+2] ; phrase #2
not phrase [si] ; phrase #1
inc phrase [si] ; increment the first phrase; if it didn't roll over again to zero, executed
jnz .done_NEG; increment the 2nd phrase
inc phrase [si+2]; if it rolled over, increment the subsequent phrase
jnz .done_NEG
inc phrase [si+4]
jnz .done_NEG; this can't roll over or revert again to
inc phrase [si+6]
; constructive..done_NEG:
clc ; Success, clear Carry Flag and return
ret
With all of that shared code between absolutely the and unfavourable features, they need to be mixed to avoid wasting bytes. There are further advantages when such code is mixed. For one, it helps forestall easy typographic errors. It can also scale back testing necessities. Moreover, the supply typically turns into simpler to learn, observe, and perceive. Sometimes with an extended sequence of meeting directions, it’s simple to lose observe of what’s really taking place. But for now, we will transfer alongside.
Getting absolutely the or unfavourable worth of a quantity was not very tough. But, these features shall be critically vital afterward once we begin doing math on signed integers.
Now that I’ve coated the fundamentals of how integer numbers are represented on the bit degree and created a few fundamental routines to govern them a bit of, we will get to the enjoyable stuff.
Let’s do some math!
