Doing 64-bit math on a 16-bit system

A few years ago, I wrote a command-line math program for FreeDOS called VMATH. It was capable of performing only extremely simple mathematical operations on very small unsigned integers. With some recent interest in basic math in the FreeDOS community, I improved VMATH to provide basic math support on signed 64-bit integers.

The process of manipulating big numbers using only 16-bit 8086 compatible assembly instructions is not straightforward. I would like to share some samples of the techniques used by VMATH. Some of the methods used are fairly easy to grasp. Meanwhile, others can seem a little strange. You may even learn an entirely new way of performing some basic math.

The techniques explained here to add, subtract, multiply, and divide 64-bit integers are not limited to just 64-bits. With a little basic understanding of assembly, these functions could be scaled to do math on integers of any bit size.

Before digging into those math functions, I want to cover some basics of numbers from the computer's perspective. 

How computers read numbers

An Intel-compatible CPU stores the value of numbers in bytes from least to most significant. Each byte is made up of 8 binary bits and two bytes make up a word.

A 64-bit number that is stored in memory uses 8 bytes (or 4 words). For example, a value of 74565 (0x12345 in hexadecimal) looks something like this:

as bytes: db 0x45, 0x23, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00
as words: dw 0x2345, 0x0001, 0x0000, 0x0000

When reading or writing data to memory, the CPU processes the bytes in the correct order. On a processor more modern than an 8086, there can be larger groups, such as a quadword which can represent the entire 64-bit integer as 0x0000000000012345.

The 8086 CPU doesn't understand such gigantic numbers. When writing a program for FreeDOS, you want something that can run on any PC, even an original IBM PC 5150. You also want to use techniques that can be scaled to any size integer. The capabilities of a more modern CPU do not really concern us.

For the purpose of doing integer math, the data can represent two different types of numbers.

The first is unsigned which uses all of its bit to represent a positive number. Their value can be from 0 up to (2 ^ (numberofbits) - 1). For example, 8 bits can have any value from 0 to 255, with 16 bits ranging from 0 to 65535, and so on.

Signed integers are very similar. However, the most significant bit of the number represents whether the number is positive (0) or negative (1). The first portion of the number is positive. It can range from 0 up to (2 ^ (numberofbits - 1) - 1). The negative portion follows the positive, ranging from its lowest value (0-(2 ^ (numberofbits - 1))) up to -1.

For example, an 8-bit number represents any value from 0 to 127 in the positive range, and -128 through -1 in the negative range. To help visualize it, consider the byte as the set of numbers [0…127,-128…-1]. Because -128 follows 127 in the set, adding 1 to 127 equals -128. While this may seem strange and backward, it actually makes doing basic math at this level much easier.

To perform basic addition, subtraction, multiplication, and division of very big integers, you should explore some simple routines to get a number's absolute or negative value. You will need them once you start doing math on signed integers.

Absolute and negative values

Getting the absolute value of a signed integer is not as bad as it may first seem. Because of how unsigned and signed numbers are represented in memory, there is a fairly easy solution. You can simply invert all the bits of a negative number and add 1 to get the result.

That might sound odd if you haven't worked in binary before, but that is how works. To give you an example, take an 8-bit representation of a negative number, such as -5. Since it would be near the end of the [0…127,-128…-1] byte set, it would have a value of 0xfb in hexadecimal, or 11111011 in binary. If you flip all the bits, you get 0x04, or 00000100 in binary. Add 1 to that result and you have the answer. You just changed the value from -5 to +5.

You can write this procedure in assembly to return the absolute value of any 64-bit number:

; syntax, NASM for DOS
proc_ABS:
  ; on entry, the SI register points to the memory location in the
  ; data segment (DS) for the program containing the 64-bit
  ; number that will be made positive.
  ; On exit, the Carry Flag (CF) is set if resulting number can
  ; not be made positive. This only happens with maximum
  ;  negative value. Otherwise, CF is cleared.

  ; check most significant bit of highest byte
  test [si+7], byte 0x80

  ; if not set, the number is positive
  jz .done_ABS

  ; flip all the bits of word #4
  not word [si+6]
  not word [si+4] 	; word #3
  not word [si+2] 	; word #2
  not word [si] 		; word #1

  ; increment the 1st word
  inc word [si]

  ; if it did not roll over back to zero, done
  jnz .done_ABS

  ; increment the 2nd word
  inc word [si+2]

  ; if it rolled over, increment the next word
  jnz .done_ABS
  inc word [si+4]
  jnz .done_ABS

  ; this cannot roll over
  inc word [si+6]

  ; check most significant bit once more
  test [si+7], byte 0x80

  ; if it is not set we were successful, done
  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 may have noticed in the example, there is an issue that can occur in the function. Because of how positive and negative numbers are represented as binary values, the maximum negative number cannot be made positive. For 8-bit numbers, the maximum negative value is -128. If you flip all of the bits for -128 (binary 1__0000000), you get 127 (binary 0__1111111) the maximum positive value. If you add 1 to that result, it will overflow back to the same negative number (-128).

To turn a positive number negative, you can just repeat the process you used to get the absolute value. The example procedure is very similar, except you want to make sure the number is not already negative at the start.

; syntax, NASM for DOS

proc_NEG:
  ; on entry, the SI points to the memory location 
  ; for the number to be made negative.
  ; on exit, the Carry Flag is always clear.

  ; check most significant bit of highest byte
  test [si+7], byte 0x80

  ; if it is set, the number is negative
  jnz .done_NEG

  not word [si+6] 	; flip all the bits of word #4
  not word [si+4] 	; word #3
  not word [si+2] 	; word #2
  not word [si] 		; word #1
  inc word [si] 		; increment the 1st word

  ; if it did not roll over back to zero, done
  jnz .done_NEG

  ; increment the 2nd word
  inc word [si+2]

  ; if it rolled over, increment the next word
  jnz .done_NEG
  inc word [si+4]
  jnz .done_NEG

  ; this cannot roll over or revert back to
  inc word [si+6]
  ; positive.

.done_NEG:
  clc 			; Success, clear Carry Flag and return
  ret

With all of that shared code between the absolute and negative functions, they should be combined to save some bytes. There are additional benefits when such code is combined. For one, it helps prevent simple typographic errors. It also can reduce testing requirements. Moreover, the source generally becomes easier to read, follow, and understand. Sometimes with a long series of assembly instructions, it is easy to lose track of what is actually happening. But for now, we can move along.

Getting the absolute or negative value of a number was not very difficult. But, those functions will be critically important later on when we start doing math on signed integers.

Now that I've covered the basics of how integer numbers are represented at the bit level and created a couple of basic routines to manipulate them a little, we can get to the fun stuff.

Let's do some math!