Converting BCD(mm) to BCD(inch)[SOLVED]

[jpanhalt]

This is related to some recent threads of mine about reading Mitutoyo linear scales.  The bare sensors (e.g., the ones on my mill) report six, 4-bit BCD bytes in mm.  I need to convert to inches for display.  By brute force, I have converted to binary, divided by 25.4 (fixed point), and converted back (22 bit) to BCD.  That requires about 1,000 instruction cycles or a little less.  The 22-bit conversion works because the scales are less than 1 meter long.

I have been reading about doing that math in BCD, which I understand was common years ago and may still be used in the financial industry and some small calculators.  My chosen MCU is a PIC16F1xxx, and it has no "BCD-friendly" instructions like the PIC18F MCU's have (e.g., DAW, decimal adjust W). I also work in Microchip Assembly exclusively (MPASM).

Has anyone here done BCD multiplication and/or division on an 8-bit controller without BCD instructions?  Would you recommend going that direction or sticking with the brute force method?

Regards, John

[zapta]

What do you hope to achieve, better accuracy? Speed? Smaller code? Something else?

[jpanhalt]

Accuracy is fine.  Just looking for smaller code with the same or better speed.  Many routines with lots of loops, e.g., double dabble*, have small code, but can be quite slow with 24-bit numbers.

*For binary to BCD, I use a polynomial method (derived from PICList) that has more code, but is quite fast.  My 20-bit routine takes about 300 instruction cycles.

[rhodges]

Converting ASCII decimal  or BCD to binary is usually easy. Here is code to convert 16 bit binary to BCD. It looks like it is easy to add a few instructions to do 24 bits. Hope it helps!

[Benta]

Dunno why your code is so bloated.
I did a binary to BCD routine for the 68HC11 once and it was like 20 lines of assembler code.
Converting BCD to binary would be around the same.

[DavidAlfa]

Did anyone read? It's not just bcd to ascii, he wants conversion to inches.

For 15.712mm the caliper will output BCD [1][5][7][1][2].
So, it needs to be parsed into an integer, converted to inches and later to ascii.

Why the 1K cycles drama...? At several MHz it can peform thousands of conversions per second.
So why the optimization? I bet the cpu is doing nothing 80% of the time, wasting time in timeout .
Optimizating is cool but a waste of time if not needed.

What you could do:
Use a hardware timer for your delays. For sure your will have some milliseconds delay somewhere.
Perform the conversion in this delay, then wait until the timer expires.

[macboy]

Accuracy is fine.  Just looking for smaller code with the same or better speed.  Many routines with lots of loops, e.g., double dabble*, have small code, but can be quite slow with 24-bit numbers.

*For binary to BCD, I use a polynomial method (derived from PICList) that has more code, but is quite fast.  My 20-bit routine takes about 300 instruction cycles.

Only 300 instructions to convert 20 bit binary to BCD is very fast. I once optimized double-dabble for as much speed as I could get, including using a lookup table to speed up the add-3 operation. For 20 bits input it would do maybe 1200 cycles, but I needed 40 bits converted (12 decimal digits) and this needed over 2500 cycles. I'm very interested in your implementation, if you are willing to share.

Dunno why your code is so bloated.
I did a binary to BCD routine for the 68HC11 once and it was like 20 lines of assembler code.
Converting BCD to binary would be around the same.

probably something to do with RISC CPU having 35 instructions vs CISC CPU having at least 142 instructions including some with 16 bit operands. Code based on (for example) divide-by-ten is trivial to implement, but takes an especially long time on a CPU with no multiply or divide instructions.

[Benta]

Did anyone read? It's not just bcd to ascii, he wants conversion to inches.

It was an example.
The multiplication/division of the binary number itself for doing the scaling/conversion will be even less code (provided the PIC-thing has those instructions. Never worked with it myself).

[DavidAlfa]

PIC16 has no multiplication, neither division.
So you must do it all with add/sub/shift instructions and checking Zero/Carry bits.
All that in only 200 instructions seems very reasonable to me.

[Benta]

PIC16 has no multiplication, neither division.
So you must do it all with add/sub/shift instructions and checking Zero/Carry bits.
All that in only 200 instructions seems very reasonable to me.

Ah, OK.
In that case I agree, code size seems completely fair.

More like a chrome-plated CPLD, it seems.

[jpanhalt]

@macboy and Benta

That "300 instructions" is instruction cycles (Tcy).  The code is not that lengthy and the vast majority of those cycles are in the "Normalize" portion.  The 16-bit version is often less than 200 Tcy.  I put a 17-bit version on PICList before it closed (http://www.piclist.com/Techref/microchip/math/radix/b2bu-17b5d.htm#).  I added it as a comment.  Unfortunately, I submitted it in MPASM and James Newton had to convert it to regular text.  That led to added typos, but I think it still works.  For 20-bit, I just modified the "TenK" routine, calculated new offsets, and got it to run without adding a whole new equation for "HundK."

What bothers me is the approach of going from BCD to binary, doing a division,* and back to BCD.  It would seem more efficient simply to do the division (or multiplication) in BCD if there were a fast way to do that without the PIC18F or other more extensive instruction sets.

John

*I modified the so-called Kenyan method (it is known by several names) , which multiplies the divisor until it is "slightly more than the dividend" and then does subtractions and right shifts. Slightly more than the dividend is the term used in the description.  Actually, it only needs to be equal to the (dividend/2) +1 or larger.  And since one is dividing by a constant, that part of the code can be shortened.

[jpanhalt]

And BTW, I will post my code, especially the BIN2BCD routine once it is in better shape.  From a practical standpoint, I just didn't want to try to go a full 24 bits, as 6 decimal digits (e.g., 25.0000 inch) is more than adequate for what I do in my shop.

[Benta]

What bothers me is the approach of going from BCD to binary, doing a division,* and back to BCD.  It would seem more efficient simply to do the division (or multiplication) in BCD if there were a fast way to do that without the PIC18F or other more extensive instruction sets.

I don't know of any, and the DAA (8085) or in your case DAW are not really helpful.
Doing BCD arithmetic will bring you somewhere you don't want to go with a hell of a lot more code.
The input and output conversions (BCD/bin, bin/BCD) aren't really that problematic.

[SiliconWizard]

Or just don't use inches.

[jpanhalt]

Doing BCD arithmetic will bring you somewhere you don't want to go with a hell of a lot more code.

That was my impression from the code I looked at.  If the MCU is designed for it, then BCD math work fine (e.g., early small calculators), but for something like I have, you will be constantly checking and correcting for "carries."  I was hoping someone had developed a clever polynomial solution like the BIN2BCD code I modified.  I searched before posting and didn't find any.

As for the in and out algorithms, they are pretty well established.  I found a quick mm to inch approximation that is probably accurate enough.  I have not compared it to my division method yet.

[Benta]

Or just don't use inches.

Don't start that.

But I wonder about something else: most DROs I know of can switch between inch/metric display. Can't yours?

[Nominal Animal]

Dividing by 25.4 is the same as multiplying by 0.0393700787401574797685910...
For ranges less than a meter, multiplying by 0.03937008 will give you the correct answer to over six digits.  Add 0.5 ULP before discarding superfluous digits, and you'll even get correct rounding.

You'd need a result/scratchpad of 14 digits for long BCD multiplication, dddddd × 3937008 (but the highest digit will always be zero).  The constant multiplier only has four unique digits, so you could just use four ten-byte tables, one each for the BDC multiplication by 3, 7, 8, and 9.  Also remember that the digits can be done in any order, as long as you mathematically calculate the same dddddd × 3937008.  I probably would do
    dddddd×8 + dddddd×7000 + dddddd×3030000 + dddddd×900000 + 5000000
with each digit in a separate byte, noting that the third one just does the additions twice per digit, and the last addition is for rounding.  12th and 13th digits form the full inches, and 8th through 11th digit contains the ten-thousandths of an inch, rounded to the nearest ten-thousandth.

You can simply ignore the carries, doing a hundreds ripple digit pass before the multiplication by nine, and a full tens digit pass at the end.  (3+9+3+7+8)×9 = 270 so leaving it at end could overflow, but doing it before the multiplication by nine, and after the addition of five million, would work just fine.
A good trick here is to repeatedly compare to 100, and substract by 100 and increment +2 digit.  For tens, you might do a compare to 30, substract by 30, and add +3 to next higher digit, from low to high; followed by a simple compare to 10 and substract 10 and increment next higher digit.  The total number of comparison iterations stays surprisingly low.

[jpanhalt]

Or just don't use inches.

Don't start that.

But I wonder about something else: most DROs I know of can switch between inch/metric display. Can't yours?

The readout does that conversion, but it does not have an output.  I am trying to read the sensor directly.  It reports only in mm.   I have not opened the box yet to see whether there is anything inside I might converted data from, but I doubt there is.  A smaller sensor I have for the spindle is just a COB on the inside.  It has an integrated output that does report in inches or mm.

[jpanhalt]

@Nominal Animal

I found a nice routine for the multiplication, and I think it is based on the algorithm you describe.  I haven't tried it yet.

[AVI-crak]

Rounding of the measurement result of physical quantities is inadmissible!!!
It is directly related to the accuracy of machining parts - when you have an exact size, and a tolerance of "+" or "-" is specified.
Rounding will hide this boundary and the parts will be different sizes.

[Nominal Animal]

Rounding of the measurement result of physical quantities is inadmissible!!!

All conversions at fixed or limited precision involves rounding; either implicit, or explicit.

With proper rounding, the displayed measurement has at most ±0.00005" of error compared to the original measurement in millimeters.
If you simply truncate the converted result, your error bounds become +0.00000/-0.00010.

I don't know who told you "rounding ... is inadmissible", but they were utterly wrong.

[SiliconWizard]

Fun stuff indeed. We always "round" physical measurements, as a physical measurement can't be infinitely precise. So that made no sense. It's of course all a matter of whether the result is within the expected error or not.

[peter-h]

As a possible aside, there may be a requirement for errors to reverse exactly.

Many years ago I did a custom thing for a customer in the 35mm film winder business. The film passed over a shaft encoder which produced say 20 counts per frame. And 35mm film had say 12 frames per foot, or whatever, you get the idea. So to display feet or frames was easy.

Then the customer wanted metres 

So I did that.

This also had a function to drive a servo motor to wind the film to a certain position, which could be specified in any of the above units.

So I did that. A nice bit of PID code...

Then he wanted the ability to go to a position in say feet and change to metres and go back, then change to feet and go back 

I did it all in the end but it was a right bastard, preserving the division remnants there and back. Did they buy any, after all that? What do you think... Most custom requests are from chancers.

BCD would not have helped, though the Z80 had nibble move/swap instructions. There was a ton of code around for 32 bit mult/div - the TRS80 Assembler Programming Manual It was c. 100us for a 32x32 mult, 4MHz.

[jpanhalt]

There are now two contributors advising "don't do it" unless the instruction set is designed to do it.  The only instruction the 16F's have that's a little helpful is the digit carry bit of the STATUS reg (STATUS,1).  I use that in the bandaid extension of my 17-bit version to 20 bits.

I will post both later in another thread to help searches and put a link here.   PICList is mirrored on other sites, but we don't know for how long those will remain usable.  Hopefully a long time.  Here's a direct link to the mirrored site I use:
https://pic.hallikainen.org/techref/piclist/index.htm

As for rounding, Mitutoyo does that in their scales.  The native read is in mm to 0.01 mm (0.00039").  Six digits gives xxxx.xx  mm.   The inch-converted values are  read as xx.xxx5 ± 0.0005.  In other words, the tenths are either 0 or 5.  On my to do list is to figure out how Mitutoyo rounds.  I suspect 0.01 mm is rounded to 0.0005" and 0.02 to 0.0010" and so forth, but I need to confirm.

[Doctorandus_P]

Multiplication with the reciprocal of 25.4 may be a bit quicker then division.

And think about what is actually happening, and what format you want. Do you want BCD as output, or do you want a string of ASCII?

Also, 1000 clock cycles does not seem too bad for converting a big number twice and doing some extra math. I am not very familiar with those PIC16F, I guess they are on par with the 8-bit processors (I did see in the datasheet they have 8-bit timers).

Even if it runs on just 16MHz, that is still 16000 conversions per second. That is a lot quicker then you can read the display. So why is it a problem?

Faster then 100Hz will never be needed for human eyes. And that leaves interpolation for synchronizing axis or PID loops, and even for those 16kHz is plenty. It is also 2023 now. For such things a faster processor is a more sensible choice. Even GRBL Hal has dropped support for 8-bit processors.

Maybe you want to look into Linux CNC. It can run PID loops on PC hardware and also has built in functions for synchronizing with external encoders. But there will be a considerable learning curve to set up such things. But if you are still programming generic algorithms in assembly you are probably not very interested in things from this century. There is nothing wrong with that, everybody needs a hobby I guess, but I can't help with that.