5 ms·

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

39 points by noexani 6y ago

Someone 6y ago
To me, this screams “use a lookup table”. We’re talking, maybe, 100 different “Celsius” values. If there’s no memory for that, do multiplication by 9/5 the way it’s done in Bresenham’s line algorithm (https://en.wikipedia.org/wiki/Bresenham's_line_algorithm) https://en.wikipedia.org/wiki/Bresenham's_line_algorithm). If you start at zero Celsius = 32 Fahrenheit, that’s 50 steps, at most. Might not be (much) smaller than a lookup table, though. Precomputing the steps for each degree Celsius difference and storing each in a single bit (a one degree change in Celsius will increase degrees Fahrenheit by either 1 or 2) might be the most memory-efficient approach. For a 100 degree Celsius range that’s a 50 bits table (starting at the center of the range). Edit: even that may be too large. That table will repeat every 9 bits, so one byte almost is enough. It might be a struggle to make that a net gain, given the more complex conversion code, though.
- noexani 6y ago
  It depends on the application. In this case a lookup table would consume quite a bit more program memory (there isn't any spare), and the division routine is needed for other tasks, so it makes sense to use it for that conversion too. Speed is not an issue.
  - noexani 6y ago
    I just calculated, there are 1800 possible Celsius values. in this application. That would be quite some lookup table.
    - dvdkhlng 6y ago
      You can very likely compress the table and/or interpolate between entries. It's not like that those entries are totally random.
      - AstralStorm 6y ago
        You can actually do that as well with the division itself. But you need a kind of fancy interpolation, I forget the name, used for rational functions. Polynomials won't do. Edit: I think this is either Restrictive Pade's approximation or barycentric rational interpolation. Or both combined. Normally instead division is approximated with Newton-Raphson iteration. I think 6 steps is enough for 16 bit.
        fuzzfactor 6y ago
        It's a simple linear function, and the delta Y has enough digits to overcome significant rounding error in comparison to measurement error. In this application no rounding is needed either since the difference between rounding and truncation is also not significant. You don't need the computer to do any of your multiplication or store any table. You can start from a sufficiently low reference point, then add delta Y as you increment X. Xref + deltaX = Yref + deltaY
injb 6y ago
Your MCS-48 stuff is really cool. I don't have anything to add to the division topic, but I'v been working on a reverse-engineering project on an MCS-48 based engine management computer from the Porsche 944 Turbo (https://jhnbyrn.github.io/951-KLR-PAGES/ https://jhnbyrn.github.io/951-KLR-PAGES/). You probably have the official User's Manual already, but there's a link to it there if you don't. I found it essential in addition to the assembly code manual. I haven't found much '48 stuff out there so I'm looking forward to reading all your stuff on this!
- noexani 6y ago
  I have done some MCS-48 reverse engineering too. It's really useful to look at the snippets in that manual as you'll find them in disassembled code, making it quite a bit easier to understand.
bonzini 6y ago
Never divide by a constant! Dividing by 5 can be done as a multiplication by 0.3333 hex, i.e. a multiplication by 3 * 17 * 257 followed by a right shift by 16. If you need more precision, just add more factors. Multiplication in turn is done by a hardcoded sequence of shifts and adds.
- phire 6y ago
  Also, rearrange the calculation. (Celsius * 9) / 5 can trivially be rearranged to Celsius * (9 / 5) You can implement this as a fixed point multiply by the constant 1.8. You are already using base 10 fixed point, so it simply becomes a multiply by 18, which can be simplified to a few shifts and adds: (Celsius << 4) + Celsius + Celsius Don't forget to add 32 and the algorithm requires a 16bit shift and three 16 bit adds.
  - bonzini 6y ago
    But then you are in base 100 fixed point. Converting it back to base 10 is what requires a division (but it's still by a constant though).
    - phire 6y ago
      Op is already in base 100 fixed point. I guess because that's what the sensor returns? Though it might be smart to convert it to another format. Four nibbles of BCD would be ideal and the MCS-48 looks to have native support for it. Thought you would need a custom version of shift by 4 that handles BCD. Or simplify the equation to just adds: C2 = C + C C4 = C2 + C2 C8 = C4 + C4 C16 = C8 + C8 Res = C16 + C2
      - bonzini 6y ago
        If he's in base 100 and you multiply by 18 it's the same story: you are now in base 1000 and need a division to go back. Converting from binary to BCD also needs division by constants, so again it's more or less the same.
thom 6y ago
I didn’t appreciate the complexity here until trying to write CHIP-8 games, and I grew to appreciate libraries like: https://github.com/jdeeny/chip8-multiply https://github.com/jdeeny/chip8-multiply
pierrebai 6y ago
A loooooong tmie ago (circa... 1992?) I had the same problem with an Hitachi embedded processor. Except our application was hard real-time (controlling the fuel injector of a Ford 150 that was modified to run on natural gas). We ended-up splitting the division code over multiple loops of the core system so that it would not exceed the allotted time when the engine was running at maximum RPM. It meant that the value that required division would only update at something like 1/6th of the data acquisition speed of all other values, but hey, it worked. Maybe I still have the source code on some floppy disk somewhere... Edit: I remembered wrong, it was a GMC truck: https://www.sae.org/publications/technical-papers/content/922387/ https://www.sae.org/publications/technical-papers/content/92... Edit #2: found a picture of our truck: https://live.staticflickr.com/8487/8186513796_bd60fd3fd2_b.jpg https://live.staticflickr.com/8487/8186513796_bd60fd3fd2_b.j...
- morcheeba 6y ago
  I did something similar for a high speed (10k rpm) stepper motor driver. We were emulating a legacy system and needed to do a 24 bit/16 bit divide, which took a long time. Even worse was that when the speeds increased, we had less time to do the computation. I came up with a trick: when the denominator changed to above a certain value, I knew the output's MSB would be zero, so I switched to a more efficient division routine that computed fewer bits. It was enough to get us smooth performance without running out of time.
- mrguyorama 6y ago
  I don't know why but the idea of working on an engine management system is incredibly appealing to me. How did you get into the field? I unfortunately have no background or formal training in embedded systems so I fear I have no real possibility of success in this dream
  - pierrebai 6y ago
    I didn't, it was an extra-curicular university project.
  - SAI_Peregrinus 6y ago
beeforpork 6y ago
IIRC, the DS18B10 (like its cousins) does not return celsius multiplied by 10 (i.e., not '153' for 15.3°C), but returns a 7 bit integer celsius value plus a sign plus a few fractional bits -- by default 1 (i.e, a +-7.1 bit format), but maybe this device has a few more bits in a secondary register -- I remember using one that had four sub-celsius bits, i.e., would output 1/16 celsius steps (a +-7.4 bit value). In any case, not a value multiplied by 10, but a celsius unit with binary fractional bits. Am I wrong? Looking for DS18B10 data sheet always gives me the DS18S20. Hmm, dunno. Anyway, assuming a sign + 7 bits integer + 4 bits fractional format, you can calculate inside 16 bit signed without overflow with a 3-bit shifted 9/5 constant without overflowing, up to beyond 100°C. With a bit of shifting, the following is quite accurate: int16_t celsius2fahrenheit(int16_t c) { int16_t f = 0; f += c << 4; f -= c; f -= c >> 1; f -= c >> 3; f += c >> 5; f += 32 << 7; f >>= 3; return f; } Accuracy: C=0 (int: 0), F=32 (exact: 32, int: 512) C=15.3 (int: 244), F=59.4375 (exact: 59.54, int: 951) C=37 (int: 592), F=98.625 (exact: 98.6, int: 1578) C=100 (int: 1600), F=212.062 (exact: 212, int: 3393)
- noexani 6y ago
  You are correct. the conversion to Celsius * 10 is done earlier on, because it is easy to optionally perform this conversion, and it's easy to render the various formats (positive/negative/DP,no DP) of it to the 7-segment display banks. Also worth considering that I originally had no interest in fahrenheit (I live in the UK). This was done as an extra later on. Didn't want to poo the original implementation taking fahrenheit straight off the sensors.
  - beeforpork 6y ago
    OK, I understand. The approach works even better if you multiply by 10: int16_t celsius2fahrenheit10(int16_t c) { int16_t f = 0; f += c << 4; f -= c; f -= c >> 1; f -= c >> 3; f += c >> 5; f += 320 * 8; f >>= 3; return f; } This is really accurate: C=0 (int 0) F=32 (int: 320, exact: 32) C=15.3 (int 153) F=59.5 (int: 595, exact: 59.54) C=37 (int 370) F=98.6 (int: 986, exact: 98.6) C=100 (int 1000) F=212 (int: 2120, exact: 212)
sgtnoodle 6y ago
If you really wanted to support any denominator for a 16-bit division in a space efficient way, it seems like you could just subtract the denominator from the numerator in a loop, counting iterations until it's less than the denominator. I can't imagine it's more than a dozen assembly instructions, even on a crappy architecture. Worst case (divide by 2), it takes 32767 iterations, and you even get the remainder out of it. With this example, say 100C. Convert to deciC and offset, say, 25 degrees to make it unsigned. 1250. Multiply by 9. 11250. Divide by 5 takes 2250 iterations. I am unfamiliar with the MCS-48, but Google says it can be clocked at 11Mhz. It would take maybe 40ms to do the divide?

39 points by noexani 6y ago

To me, this screams “use a lookup table”. We’re talking, maybe, 100 different “Celsius” values. If there’s no memory for that, do multiplication by 9/5 the way it’s done in Bresenham’s line algorithm (https://en.wikipedia.org/wiki/Bresenham's_line_algorithm) https://en.wikipedia.org/wiki/Bresenham's_line_algorithm). If you start at zero Celsius = 32 Fahrenheit, that’s 50 steps, at most. Might not be (much) smaller than a lookup table, though. Precomputing the steps for each degree Celsius difference and storing each in a single bit (a one degree change in Celsius will increase degrees Fahrenheit by either 1 or 2) might be the most memory-efficient approach. For a 100 degree Celsius range that’s a 50 bits table (starting at the center of the range). Edit: even that may be too large. That table will repeat every 9 bits, so one byte almost is enough. It might be a struggle to make that a net gain, given the more complex conversion code, though.

noexani 6y ago
It depends on the application. In this case a lookup table would consume quite a bit more program memory (there isn't any spare), and the division routine is needed for other tasks, so it makes sense to use it for that conversion too. Speed is not an issue.
- noexani 6y ago
  I just calculated, there are 1800 possible Celsius values. in this application. That would be quite some lookup table.
  - dvdkhlng 6y ago
    You can very likely compress the table and/or interpolate between entries. It's not like that those entries are totally random.
    - AstralStorm 6y ago
      You can actually do that as well with the division itself. But you need a kind of fancy interpolation, I forget the name, used for rational functions. Polynomials won't do. Edit: I think this is either Restrictive Pade's approximation or barycentric rational interpolation. Or both combined. Normally instead division is approximated with Newton-Raphson iteration. I think 6 steps is enough for 16 bit.
      - fuzzfactor 6y ago
        It's a simple linear function, and the delta Y has enough digits to overcome significant rounding error in comparison to measurement error. In this application no rounding is needed either since the difference between rounding and truncation is also not significant. You don't need the computer to do any of your multiplication or store any table. You can start from a sufficiently low reference point, then add delta Y as you increment X. Xref + deltaX = Yref + deltaY

injb 6y ago

Your MCS-48 stuff is really cool. I don't have anything to add to the division topic, but I'v been working on a reverse-engineering project on an MCS-48 based engine management computer from the Porsche 944 Turbo (https://jhnbyrn.github.io/951-KLR-PAGES/ https://jhnbyrn.github.io/951-KLR-PAGES/). You probably have the official User's Manual already, but there's a link to it there if you don't. I found it essential in addition to the assembly code manual. I haven't found much '48 stuff out there so I'm looking forward to reading all your stuff on this!

noexani 6y ago
I have done some MCS-48 reverse engineering too. It's really useful to look at the snippets in that manual as you'll find them in disassembled code, making it quite a bit easier to understand.

bonzini 6y ago

Never divide by a constant! Dividing by 5 can be done as a multiplication by 0.3333 hex, i.e. a multiplication by 3 * 17 * 257 followed by a right shift by 16. If you need more precision, just add more factors. Multiplication in turn is done by a hardcoded sequence of shifts and adds.

phire 6y ago
Also, rearrange the calculation. (Celsius * 9) / 5 can trivially be rearranged to Celsius * (9 / 5) You can implement this as a fixed point multiply by the constant 1.8. You are already using base 10 fixed point, so it simply becomes a multiply by 18, which can be simplified to a few shifts and adds: (Celsius << 4) + Celsius + Celsius Don't forget to add 32 and the algorithm requires a 16bit shift and three 16 bit adds.
- bonzini 6y ago
  But then you are in base 100 fixed point. Converting it back to base 10 is what requires a division (but it's still by a constant though).
  - phire 6y ago
    Op is already in base 100 fixed point. I guess because that's what the sensor returns? Though it might be smart to convert it to another format. Four nibbles of BCD would be ideal and the MCS-48 looks to have native support for it. Thought you would need a custom version of shift by 4 that handles BCD. Or simplify the equation to just adds: C2 = C + C C4 = C2 + C2 C8 = C4 + C4 C16 = C8 + C8 Res = C16 + C2
    - bonzini 6y ago
      If he's in base 100 and you multiply by 18 it's the same story: you are now in base 1000 and need a division to go back. Converting from binary to BCD also needs division by constants, so again it's more or less the same.

thom 6y ago

I didn’t appreciate the complexity here until trying to write CHIP-8 games, and I grew to appreciate libraries like: https://github.com/jdeeny/chip8-multiply https://github.com/jdeeny/chip8-multiply

pierrebai 6y ago

A loooooong tmie ago (circa... 1992?) I had the same problem with an Hitachi embedded processor. Except our application was hard real-time (controlling the fuel injector of a Ford 150 that was modified to run on natural gas). We ended-up splitting the division code over multiple loops of the core system so that it would not exceed the allotted time when the engine was running at maximum RPM. It meant that the value that required division would only update at something like 1/6th of the data acquisition speed of all other values, but hey, it worked. Maybe I still have the source code on some floppy disk somewhere... Edit: I remembered wrong, it was a GMC truck: https://www.sae.org/publications/technical-papers/content/922387/ https://www.sae.org/publications/technical-papers/content/92... Edit #2: found a picture of our truck: https://live.staticflickr.com/8487/8186513796_bd60fd3fd2_b.jpg https://live.staticflickr.com/8487/8186513796_bd60fd3fd2_b.j...

morcheeba 6y ago
I did something similar for a high speed (10k rpm) stepper motor driver. We were emulating a legacy system and needed to do a 24 bit/16 bit divide, which took a long time. Even worse was that when the speeds increased, we had less time to do the computation. I came up with a trick: when the denominator changed to above a certain value, I knew the output's MSB would be zero, so I switched to a more efficient division routine that computed fewer bits. It was enough to get us smooth performance without running out of time.
mrguyorama 6y ago
I don't know why but the idea of working on an engine management system is incredibly appealing to me. How did you get into the field? I unfortunately have no background or formal training in embedded systems so I fear I have no real possibility of success in this dream
- pierrebai 6y ago
  I didn't, it was an extra-curicular university project.
- SAI_Peregrinus 6y ago

beeforpork 6y ago

IIRC, the DS18B10 (like its cousins) does not return celsius multiplied by 10 (i.e., not '153' for 15.3°C), but returns a 7 bit integer celsius value plus a sign plus a few fractional bits -- by default 1 (i.e, a +-7.1 bit format), but maybe this device has a few more bits in a secondary register -- I remember using one that had four sub-celsius bits, i.e., would output 1/16 celsius steps (a +-7.4 bit value). In any case, not a value multiplied by 10, but a celsius unit with binary fractional bits. Am I wrong? Looking for DS18B10 data sheet always gives me the DS18S20. Hmm, dunno. Anyway, assuming a sign + 7 bits integer + 4 bits fractional format, you can calculate inside 16 bit signed without overflow with a 3-bit shifted 9/5 constant without overflowing, up to beyond 100°C. With a bit of shifting, the following is quite accurate: int16_t celsius2fahrenheit(int16_t c) { int16_t f = 0; f += c << 4; f -= c; f -= c >> 1; f -= c >> 3; f += c >> 5; f += 32 << 7; f >>= 3; return f; } Accuracy: C=0 (int: 0), F=32 (exact: 32, int: 512) C=15.3 (int: 244), F=59.4375 (exact: 59.54, int: 951) C=37 (int: 592), F=98.625 (exact: 98.6, int: 1578) C=100 (int: 1600), F=212.062 (exact: 212, int: 3393)

noexani 6y ago
You are correct. the conversion to Celsius * 10 is done earlier on, because it is easy to optionally perform this conversion, and it's easy to render the various formats (positive/negative/DP,no DP) of it to the 7-segment display banks. Also worth considering that I originally had no interest in fahrenheit (I live in the UK). This was done as an extra later on. Didn't want to poo the original implementation taking fahrenheit straight off the sensors.
- beeforpork 6y ago
  OK, I understand. The approach works even better if you multiply by 10: int16_t celsius2fahrenheit10(int16_t c) { int16_t f = 0; f += c << 4; f -= c; f -= c >> 1; f -= c >> 3; f += c >> 5; f += 320 * 8; f >>= 3; return f; } This is really accurate: C=0 (int 0) F=32 (int: 320, exact: 32) C=15.3 (int 153) F=59.5 (int: 595, exact: 59.54) C=37 (int 370) F=98.6 (int: 986, exact: 98.6) C=100 (int 1000) F=212 (int: 2120, exact: 212)

sgtnoodle 6y ago

If you really wanted to support any denominator for a 16-bit division in a space efficient way, it seems like you could just subtract the denominator from the numerator in a loop, counting iterations until it's less than the denominator. I can't imagine it's more than a dozen assembly instructions, even on a crappy architecture. Worst case (divide by 2), it takes 32767 iterations, and you even get the remainder out of it. With this example, say 100C. Convert to deciC and offset, say, 25 degrees to make it unsigned. 1250. Multiply by 9. 11250. Divide by 5 takes 2250 iterations. I am unfamiliar with the MCS-48, but Google says it can be clocked at 11Mhz. It would take maybe 40ms to do the divide?