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.

[jpanhalt]

There are two main purposes to this project: 1) Allow control of threading feed (i.e., an auto stop); and 2) Repurpose Mitutoyo scales currently on my mill to use on my lathe.  For my mill, I will be going with a more modern DRO that has all sorts of built-in functions but uses inexpensive glass scales. 

The Mitutoyo scales are inductive, more compact than glass, and quite robust with respect to contamination.  They will be happy on the lathe, and because they are smaller and more robust, I may be able to fit one to the cross feed.  That will not be easy even with the Mitutoyo scales.

I agree multiplication is probably faster and just haven't played with it yet.

[Doctorandus_P]

I once had to do a bit of assembly for a z80 as part of a high school course. It was quite fun as a learning experience. we had to program a calculator. I did try to use packed BCD as the Z80 does have instructions for a half carry and BCD adjustment but that was not feasible. I put in a lot more effort then my classmates and used at least three different simulators which all had different bugs in handling the flags for these instructions.

The school software was also atrocious. It had a nice looking GUI, but could do a few hundred of instructions per second. I used a cross assembler and emulator with debug monitor and when I had to demonstrate my calulator at school my arbitrary length rpn calculator took 5 minutes or so to do a simple calculation

But if you do BCD, then you can also use a simple 100byte LUT for multiplication. Shift one BCD number four bits, add the other bcd number, and do an array lookup to get a two digit packed bcd result.

but overall, if you want improvement of the 1000 cyle total, start with looking at individual parts of the algorithm. Maybe there are optimized libraries for PIC15 for (packed?) BCD...

[Doctorandus_P]

There are two main purposes to this project: 1) Allow control of threading feed (i.e., an auto stop); and 2) Repurpose Mitutoyo scales currently on my mill to use on my lathe. 

For threading, you  have to map one scale to another, do it quickly but only in small increments. A well known youtuber (cloud 42 something) has open sourced a project for this, but he uses a TMS320, which I regard as total overkill for a project like that.

If you want to do it lean an mean, then input from a quadrature / grey encoder is best. You can put it's output into a modified bresenham line algorithm to get a very high resolution. Forget about mm and banana units. Just work in whatever units map directly to your hardware.

And this likely exposes another problem. Those mitutoyo things probably use some (low to moderate baudrate) serial output, and the update rate will be low. Very likely much slower then your own algorithm. So with what frequency can you read your scales?

The Bresenham line algorithm does not work well for slow inputs with big gaps. For Bresenham you want small incremental inputs, and you want the input to have a higher update rate then the output.

If you do want further optimization, maybe it is feasible to only work with differences and increments. Maybe you can work with two (or three) digits, instead of calculating the full number each time.

[jpanhalt]

I am quite familiar with Clough42's videos on an electronic lead screw.  Notice, that he still uses half-nuts to disengage threading.  That gets complicated if one is doing metric threads with an imperial lead screw.   But that is not the problem I am trying to solve.  I can no longer trust my reflexes, concentration, and coordination to stop before crashing when cutting RH threads -- particularly internal threads where visibility is poor. 

Years ago (2009), I made an electronic stop based on detecting the "negative" bit from a Mitutoyo scale (the same series of devices I am playing with today).  The MCU was a 12F509 that I was learning on.  That worked on my miniature Prazi lathe that lacked half-nuts.  The current project is for a bigger lathe, and of course, I will add other enhancements.  An ELS, while related , is not the same.  Clough42's project avoids gear changing.  I do not find that to be a burden.  My lathe has a quick-change gear box, plenty of imperial options, and if need be, even limited metric threads.

[newbrain]

But if you do BCD, then you can also use a simple 100byte LUT for multiplication. Shift one BCD number four bits, add the other bcd number, and do an array lookup to get a two digit packed bcd result.

Small correction: 154 byte LUT. (99 HEX == 153 DEC).

[Doctorandus_P]

But if you do BCD, then you can also use a simple 100byte LUT for multiplication. Shift one BCD number four bits, add the other bcd number, and do an array lookup to get a two digit packed bcd result.

Small correction: 154 byte LUT. (99 HEX == 153 DEC).

A two dimensional 10x10 byte LUT? 

I have made custom threads on my lathe only a few times, so I am quite inexperienced with that part.
A long time ago I did mount a frequency inverter on the main motor, and this was a great help to overcome my anxiety. I just use the mechanical gears for a coarse rpm selection (increased torque at low RPM) and for the rest, I just dial the rpm down with a potentiometer.

I also have an RongFu 30 (the ubiquitous mill/drill with the round column) and have some contactors to switch the inverter between the lathe and the mill. I have also set up the inverter to have a low torque at low rpm. I can now tap M5 holes and just let the tap bottom out in a blind hole, then flip a small switch and dial up the potentiometer for a rapid reverse. I have no need for a "real" tapping head at all.

[Nominal Animal]

A two dimensional 10x10 byte LUT?

Yup, index = m1 + (m2 << 1) + (m2 << 3).  It's difficult to say whether that is faster or slower than combining nibbles from two different bytes. And most of those entries will be unused in this case.

[Doctorandus_P]

For two dimensional I'm more thinking along:

output = lut [ m1 ] [ m2 ];

and let the C compiler manage the details. I have not written any assembly in the last 20 years.

[Nominal Animal]

output = lut[m1][m2];

That's the equivalent in C for unsigned char lut[10][10], yes.

[Nominal Animal]

If we have two integer numbers mm and in,
    mm = 100 * millimeters
    in = 2000 * inches
then the conversions between the two are
    mm_to_inch(mm) = (mm * 100 ± 63) / 127
    inch_to_mm(in) = (in * 127 ± 50) / 100
where ± means addition if mm or in is positive, subtraction if negative.
For display purposes, you do need to multiply in by five.

Unfortunately, inch_to_mm(mm_to_inch(mm)) == mm±1: the roundtrip is off by 0.01mm in about 21% of cases, because the mm_to_inch() conversion maps a wider range to a narrower range: more than one reading in tens of micrometers maps to the same reading in half-thousandths of an inch.  This cannot be avoided, unless the inches precision is increased; and that means the final digit can be something other than 0 or 5.

If the final digit can be any even digit, i.e.
    mm = 100 * millimeters
    in = 5000 * inches
and you double in for display purposes, then
    mm_to_inch(mm) = (mm * 250 ± 63) / 127
    inch_to_mm(in) = (in * 127 ± 125) / 250
and you get a 1:1 mapping between inches and millimeters.

Since 250 / 127 = 1000 / 508 = 1/0.508, you could implement
    mm_to_inch(mm) = 2*round( mm / 0.508 )
which includes the doubling for display purposes, i.e. the result is in ten-thousandths of an inch; or equivalently
    mm_to_inch(mm) = round_to_even( mm / 0.254 );
i.e.
    int mm_to_inch(const int mm) { return 2*round((double)mm * 250.0 / 127.0); }
or, equivalently,
    int mm_to_inch(const int mm) { return 2*(int)(mm * 250 + (mm < 0 ? -63 : +63)) / 127);
or, equivalently,

Code: [Select]

int mm_to_inch(const int mm)
{
    unsigned int  u = (mm < 0) ? -mm : mm;
    int           n = 0;

    // Up to 15 iterations
    while (u >= 65024) {
        u -= 65024; // 0b1111'1110'0000'0000 = 127 << 9
        n += 256;
    }

    // Up to 15 iterations
    while (u >= 4064) {
        u -= 4064;  // 0b1111'1110'0000 = 127 << 5
        n += 16;
    }

    // Up to 15 iterations
    while (u >= 254) {
        u -= 254;   // 0b1111'1110 = 127 << 1
        n++;
    }

    // We now have (n = abs(mm) / 254, u = abs(mm) % 254
    n *= 1000;  // n = (n << 10) - (n << 3) - (n << 4);
    u *= 1000;  // u = (u << 10) - (u << 3) - (u << 4);

    // Up to 31 iterations
    while (u >= 8128) {
        u -= 8128;  // 0b0001'1111'1100'0000 = 127 << 6
        n += 32;
    }

    // Up to 31 iterations
    while (u >= 254) {
        u -= 254;   // 0b1111'1110 = 127 << 1
        n++;
    }

    // Round to even
    n += (n & 1);

    return (mm < 0) ? -n : n;
}
The three mm_to_inch() functions above do produce identical results for -999999 ≤ mm ≤ +999999; I checked.
And, as I mentioned above, this is bijective: each unique mm value maps to an unique even in value, which if multiplied by 0.254 and rounded, will yield the original mm value.  For half-thousandths of an inch, bijective mapping is not possible.

[SiliconWizard]

output = lut[m1][m2];

That's the equivalent in C for unsigned char lut[10][10], yes.

You don't need to store the 0's - unless the cost of a comparison and branch is much more than accessing memory, but that's very probably not the case on a PIC16F. A small detail that can be checked depending on the target.
So you only need a 9x9 LUT, not 10x10.

[Doctorandus_P]

You could optimize further, If the most significant digit is a zero, then input and output is the same and you could check for that too. But it is all adding software complexity for saving a few bytes of RAM.

Also, with just a complete LUT, there are no extra comparisons at all, so it will be (some insignificant amount) faster.
But to me it all looks like abuse of brain power. I rather spend that brain power on learning how to use 32bit uC's in a reasonable efficient way. Those things go up to several hundredths of MHz and Megabytes of Flash, RAM, DMA, multiple ISR levels and a gazillion other fun peripherals to toy with.

[thm_w]

You could optimize further, If the most significant digit is a zero, then input and output is the same and you could check for that too. But it is all adding software complexity for saving a few bytes of RAM.

Also, with just a complete LUT, there are no extra comparisons at all, so it will be (some insignificant amount) faster.
But to me it all looks like abuse of brain power. I rather spend that brain power on learning how to use 32bit uC's in a reasonable efficient way. Those things go up to several hundredths of MHz and Megabytes of Flash, RAM, DMA, multiple ISR levels and a gazillion other fun peripherals to toy with.

Yeah, ~$2 will buy you a much more capable MCU so you don't have to dick around with a bunch of optimization and can add more features later if needed.

[westfw]

Just out of curiosity, has anyone ever seen a microcontroller with some sort of assist for BCD multiply or divide?

[IanB]

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

Personally, I think I would be inclined towards a much simpler brute force approach than this, and just do straightforward decimal division the old fashioned way, as it used to be done on mechanical desk calculators by turning the wheel: repeated subtract and shift.

Basically you enter the dividend into the notional accumulator as a string of decimal digits and keep subtracting the divisor until you can go no further. Each subtraction adds 1 to the output (quotient) register. Then shift right one decimal place and repeat. Do this over and over until you have the required precision. Doing this by hand on the desk calculator only took a few seconds, with about three subtractions per second (depends how fast you can turn the handle).

On a microprocessor, I suspect this is just a couple of nested loops and a few dozen (OK, several dozen) instructions.

You surely will not do high performance computing this way, but do you need anything more for this application?

Illustration below:

Code: [Select]

Input is 15.712 mm

Initialize with 0 in the output register:
                   : 0
Try to subtract:
  15712
- 25400   X
Fails, so shift right one decimal:
-  2540   = 13172  : 01
-  2540   = 10632  : 02
-  2540   = 8092   : 03
-  2540   = 5552   : 04
-  2540   = 3012   : 05
-  2540   =  472   : 06
-  2540   X
Fails with 6 as the first decimal place.
Shift right again, and continue, shifting each time the subtraction fails:
-   254   =  218   : 061
-   254   X
2180
-   254   =  1926  : 0611
-   254   =  1672  : 0612
-   254   =  1418  : 0613
-   254   =  1164  : 0614
-   254   =   910  : 0615
-   254   =   656  : 0616
-   254   =   402  : 0617
-   254   =   148  : 0618
-   254   X
1480
-   254   =  1226  : 06181
-   254   =   972  : 06182
-   254   =   718  : 06183
-   254   =   464  : 06184
-   254   =   210  : 06185
-   254   X
Enough precision needed, so stop.

210 > 127 so round up. Result is 0.6186 inches.

[jpanhalt]

Subtract and rotate is basic to some cordic procedures and procedures labeled "novel" methods on PICList (http://techref.massmind.org/techref/method/math/muldiv.htm).  The "Kenyan" method* is near the bottom of the page.  I played with it over a couple of Winters a few years ago.  Attached is rough code for a 16x16 division.*  It is fast.  I have code for different sizes and have used it routinely. The enhanced midrange chips have two new instructions, subwfb and addwfc,  that make multi-precision math quicker as they automate dealing with the carry/borrow bit. 

Dividing by a constant is particularly easy as you know how much it needs to be rotated to be greater than (dividend/2) +1 that the algorithm requires.  I did some trial runs rotating the metric result (max = 5 bytes), e.g., xxx.xx) so that I get a nice 6-byte (dd.dddd) result and a remainder that can be ignored.  Five byte + remainder for rounding is another option.  Right now, I need to decide whether multiplying or dividing is better.  My suspicion is that dividing will prevail as the divisor has fewer non-zero bits than the multiplier.  That is easy to test.  The other thing that will be assessed is whether testing the dividend  for number of bits will save time.  Five unpacked BCD bytes is 17-bits; four BCD bytes is only 14 bits.  That saves a few rotations, but the cost might not be worth the effort overall.

Right now, I am dealing with a lot of totally unrelated issues and have very little time for this project.  I do appreciate all of the advice and have saved the code suggestions to review.  My initial question of whether to pursue BCD math or go the BCD > BIN > math >BCD route has been answered.

Thank you all.

Regards, John

*Notice there is no correction for an unsuccessful subtraction.  The negative result is simply dealt with in the next step.  The same name has been applied to a similar multiplication algorithm.  The "bit banging" part can be omitted.

[jpanhalt]

As mentioned earlier, I have posted the current version of my 20-bit BIN2BCD code here:
https://www.eevblog.com/forum/microcontrollers/20-bit-bin2bcd-(assembly)/new/#new

Link and explanation of 16-bit BIN2BCD by Payson w/ explanation by Dattalo:
https://pic.hallikainen.org/techref/microchip/math/radix/b2bu-16b5d.htm

Link to 17-bit BIN2BCD:
https://pic.hallikainen.org/techref/microchip/math/radix/b2bu-17b5d.htm

I have also attached the code here for those who hate to click on links and hope that doesn't violate any rule.  I would appreciate comments for improvement.  This is not fresh code.  It is basically the 17-bit code I wrote earlier with a bandaid addition to expand it.

John

[AVI-crak]

Metric systems are not needed for feed rate control and mark setting. Millimeters and inches are an option for displaying information, and are not suitable for controlling iron.
What you really need is a fractional binary number (an unsigned fixed-point integer). By the way, rounding in such calculations is always obtained naturally - approximation to zero. The error does not accumulate!!!

[jpanhalt]

I don't understand.  In a general sense, maybe, but in the specific case of the Mitutoyo linear sensors, is there an option?  How would you do it?  The output is BCD metric.

[IanB]

If we were talking about an industrial CNC machine, then the internal controls and position sensors might work in binary. But this isn't your use case, and so it does not apply.

[SiliconWizard]

Also, with just a complete LUT, there are no extra comparisons at all, so it will be (some insignificant amount) faster.

That is precisely not necessarily the case, which is why I mentioned it clearly in my post. Depends entirely on the target and context. Indexed memory access in the PIC16F, as I recall, was pretty slow, and IIRC (may not quite), they would actually consist in using a branch. But that's old memories. Besides, a dual-entry array? Even worse.

In any case, the idea that indexed memory access may be faster than a test and branch is entirely dependent on the target (and context again, such as cache), and turns out very often false - that was almost invariably true on older CISC architectures with no caches, but very often not true in other cases. Whether on small MCUs or fast desktop/server CPUs, the actual result will usually surprise you.

[jpanhalt]

The PIC16F1xxx has the entire RAM memory linearly mapped.  Access is by the FSRx registers.  You can also use program memory with FSRx.I wouldn't consider that slow even compared to a few lines of code.  When I get time, I have an idea for a table based system.  Probably won't work, but worth a try.

[SiliconWizard]

The PIC16F1xxx has the entire RAM memory linearly mapped.

Really. I have never used the 16F1xxx, but the original 16Fxxx series, with its banks and it was pretty tough to deal with. I suppose they have improved the 16F series significantly then.

[jpanhalt]

Attached is the mapping for one member of that series.  Notice the high byte of the addresses in the far right columns is 0x20.   That's the key.  Just set FSRxH to 2, and it will know to address that Ram as linear.  Common Ram is protected (bytes usually beginning at 0x70) is protected and still usable.  One can also continue to use banked GPRam by carefully picking which segment of linear memory to use.  For example, my constants for routines used to  manipulate an SPI GLCD are in Bank 4 to avoid  frequent bank switching and gain speed.  Thus, linear memory used to refresh the screen begins and ends before Bank 4.

[jpanhalt]

I tried a table approach for the conversion, and it looks promising.  It's not quite BCD math, but there is no code to convert the BCD sensor result to binary.  So, in the spirit of the times, I will call it a hybrid.

All I did was make an Excel table with 5 columns which corresponded from right to left of the digits in the metric reading.  That is, 0.01x, 0.1x, 1x, 10x, and 100x, respectively.  Excel then calculated each multiplier x each digit divided by 25.4 and multiplied by 10^5 for fixed point.  The decimals values in Excel were fine, but in a mirrored table converted to hex, I found 2 errors/differences in the Excel table versus what assembler and my handheld calculator.  Specifically, for d.197 the assembler gave 0xC5 and Excel gave 0xC4.  For d.1968504, Excel gave 0x1E0977 and the assembler gave 0x1E0978.  I converted the Excel table to values before doing the hex conversion.

The MCU was an enhanced midrange in simulation.  That has addwfc and subwfb instructions for multiprecision math and brw for making table reads simpler.  At this point, the code is rough, linear, and lengthy.  I will be using indirect addressing or a macro to avoid all the clutter from repeated sequences for each byte.

Conversion of 567.95 mm to 22.3602" in binary took 144 Tcy.  If BIN2BCD is 300 Tcy, then total will be 111 us at 16 MHz.

Attached is a snippet of the code and the full table should anyone else want to play with it.

[Nominal Animal]

Metric systems are not needed for feed rate control and mark setting. Millimeters and inches are an option for displaying information, and are not suitable for controlling iron.
What you really need is a fractional binary number (an unsigned fixed-point integer). By the way, rounding in such calculations is always obtained naturally - approximation to zero. The error does not accumulate!!!

This is a common misunderstanding, related to the error in the difference of two measurements.  If we use A and B for the readings, C for the difference, and a and b for the error in each measurement, then
    C = (B + b) - (A + a) = B - A + (b - a)

The misunderstanding comes from the mistaken belief that (b - a) means the errors will cancel out and not accumulate when rounding towards zero, i.e. 0≤a<1, 0≤b<1.  Yet, this is no more true or false than for any other consistent rounding scheme (i.e, -0.5<a≤+0.5, -0.5<b≤+0.5).

The actual maximum error in C is obtained by considering the extreme cases of (b - a).

For rounding towards zero, these are when (b is almost one, a is zero) and (b is zero, a is almost one): -1 < b-a < +1.

For standard rounding, halfway up, they are when (b is almost half, a is negative half) and (b is negative half, a is almost half): -1 < b-a < +1.

Thus, as long as you use your rounding method consistently, the error in your measurements will stay the same.  If you expand the same examination to multiple measurements, you will find that the error bounds evolve the exact same way, too.

However, when we do mapping, proper selection of the rounding method to be used is crucial.  The best example of this is calculating a specific number in the Fibonacci series via rounding: \$F_n = \left\lfloor \frac{\varphi^n}{\sqrt{5}}\right\rceil, \quad n \ge 0, \quad \varphi = \frac{1 + \sqrt{5}}{2}\$.)

In the case here, conversion from hundredths-of-a-millimeter (or equivalently tens-of-micrometers) to even-ten-thousandths-of-an-inch (or equivalently five-thousandths-of-an-inch) is only bijective when rounding halfway up.

[DavidAlfa]

At this point, the code is rough, linear, and lengthy.  I will be using indirect addressing or a macro to avoid all the clutter from repeated sequences for each byte.

Looks perfectly fine? Why that obsession of optimizing something that doesn't need it?
I would understand this if it was the Voyager being updated at billion miles away, it's so far away that it can only do 16 bits per second!
But this, you'll get the mcu program done, close the device and forget about it, optimized or not.

[jpanhalt]

It's not an obsession.  I just enjoy the challenge and have no deadlines in the Winter.  I have to effectively stop coding come April -- my 20 acre hobby keeps me busy. 

[DavidAlfa]

Understood, then I completely agree, for the fun! 
I missinterpreted the reason, its common to see things like "My code uses 20KB please help!" to later see he has 100KB+ free but he still thinks we're in 1980... It's there to be used!

[jpanhalt]

Just a final note.  I have attached alternative code using indirect addressing (FSR0 andFSR1).

Statistics based on a single test number, 56795 (567.95 mm):
Full FSR (this code)
Total Tcy: 215
Math Tcy: 43
Total instructions: 32 + 15 (+ table = 150, i.e., 10x15) = 197

Linear (no FSR)
Total Tcy: 144
Math Tcy: 28
Total instructions:  55+ 28 (+ table = 150) = 233

EDIT:  Delete  the -303 (an out of range message) and the comment about using db rather that dt or dtm.

EDIT2:I just noticed a bit of sloppy code that the assembler fixed.  It is in the section where FSR0 is reading the table.  The current line reads, " addfsr    -10"  The assembler used the default FSR0 register, which happens to be correct.  The correct line should be:  "addfsr    0,-10"   The current attachment has been fixed.