# MCS-48: The quest for 16-bit division on the 8-bit CPU which can’t divide

0
17

Recently while working on my MCS-48 temperature sensor project I had to confront one of the largest challenges, which is to implement an option where changing a jumper displayed Fahrenheit instead of Celsius. The output from the DS18B10 temperature sensors is Celsius only, as it should be, so a conversion would need to be performed.

In my case it’s +320 as I’m using fixed point arithmetic i.e. 15.3° = 153. This is a tough conversion to perform on an MCS-48 as we’ve got a bunch of different operations needed here:

• 16-bit negate (more about that below)
• 16-bit unsigned multiply
• 16-bit unsigned divide

A tall order for a CPU which has just one math instruction: 8-bit add. To perform all of this, one must sling a long sequence of primitive instructions together. Since this is an assembly language only architecture, I couldn’t cheat by compiling it in C and pinching the resulting instructions as I have done for PIC16 in the past.

The best place to find such examples is in the MCS-48 assembly language manual:

(A scan of it can be viewed here). Everything I needed was in there, except how to divide. There is no mention whatsoever in that manual of how to perform any kind of division operation, but, tacked in the back of the 1980 edition MCS-48 handbook, I found this:

Unfortunately that routine only has an 8-bit quotient, which isn’t much use for my application because it would overflow in most cases.

I was easily able to work around that with the following implementation (pseudo code):

``````if (celsius < 0)
{   // If negative, note it, and make it positive
// so we can work with simpler unsigned routines below
celsius = -celsius;
is_negative = 1;
}

fahrenheit = multiply_16x8r16(celsius, 9);

// Divide by 50 so the result of divide_16x8r8 doesn't overflow
fahrenheit = divide_16x8r8(fahrenheit, 50, &remainder);

// Multiply it back up
fahrenheit = multiply_16x8r16(fahrenheit, 10);

// Factor remainder
remainder = multiply_16x8r16(remainder, 10);

fahrenheit += divide_16x8r8(remainder, 50, NULL);

if (is_negative)
{   // Make it negative again, if it was previously
is_negative = 1;
}

// correctly handle negative temperatures
fahrenheit += 320``````

While that does the job, it’s poo poo. What I really want is that complicated looking divide routine to have a 16-bit quotient, so I can do the division in a single operation. To help me understand it, I translated it to C code:

``````uint8_t mcs48_divide(uint16_t dividend, uint8_t divisor, uint8_t *remainder)
{
if ((dividend >> 8) >= divisor)
goto mcs48_div_exit; // Impossible. Result would
// overflow. Bail.

for (int i = 0; i < 8; i++) // One pass for each bit of result
{
uint8_t msb;
uint8_t bit15_was_set = 0;

if (dividend & 0x8000)
bit15_was_set = 1; // Note if this was set,

dividend <<= 1; // Next bit

msb = (dividend >> 8);
if (msb >= divisor || bit15_was_set)
{
// Subtract remainder from MSB,
// preserve and increment quotient
dividend = (((msb - divisor) << 8) | (dividend & 0xFF)) + 1;
}
}

mcs48_div_exit:
*remainder = (dividend >> 8);
return (dividend & 0xFF);
}``````

It’s immediately clear that it’s a binary division implementation. What wasn’t immediately clear is how to make the change I wanted. I put the question to stack overflow, and on the face of it, it looked like a dumb question, i.e. just double the integer type sizes, stupid. predictably I got punished with a bunch of down-votes.

Yes we can do that, but it’s not what I want to do to the assembly routine that I’m trying to modify, so perhaps I didn’t quite ask the question as well as I could have done. The answer provided sent me in the right direction, in that the working accumulator needs to be larger, 24-bits in my case, and the 16-bit shift needs to be a 24-bit.

``````uint16_t mcs48_div16(uint16_t dividend, uint8_t divisor, uint8_t *remainder)
{
uint32_t accumulator = dividend;

for (int i = 0; i < 16; i++) // One pass for each bit of result
{
uint8_t msb;
uint8_t bit24_was_set = 0;

if (accumulator & 0x800000)
bit24_was_set = 1; // Note if this was set,
// can't check if after shift.

accumulator <<= 1; // Next bit
accumulator &= 0xFFFFFF; // Simulate 24 bit type

msb = (accumulator >> 16);
if (msb >= divisor || bit24_was_set)
{
// Subtract remainder from MSB,
// preserve and increment quotient
accumulator = (((msb - divisor) << 16) | (accumulator & 0xFFFF)) + 1;
}
}

mcs48_div_ext_exit:
*remainder = (accumulator >> 16);
return (accumulator & 0xFFFF);
}``````

Above is the pseudo code of my routine after the changes. In the final implementation registers A, R1 and R2 hold the 24-bit accumulator, so this doesn’t translate too well to C because there isn’t a 24-bit integer type.

The final changes to the routine can be viewed here.

Ah, that’s better.