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.

A quick reminder of the conversion needed 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
  • 16-bit add with wrap-around

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:

Woohoo! A working divide routine for MCS-48. It wouldn’t OCR, so I typed it up.

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);

// Divide and add remainder
fahrenheit += divide_16x8r8(remainder, 50, NULL);

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

// Add 32. Requires a 16-bit add with wrap around to
// 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.

LEAVE A REPLY

Please enter your comment!
Please enter your name here