Need help with 24F/30F/33F PICs extended precision MUL/DIV please

[electron-3]

[ resending: I forgot the tag, sorry :( ]

Hi,
although my knowledge of the dsPIC (without DSP) is getting better, I am now
faced with a problem I must do absolutely bug free, because otherwise precious
data would be corrupted, so I'm seeking help here.

In short I have 24bits coming from an ADC, and I have to make them 16bits, but
inside a certain range of these 24bits.

So, to say it in pseudo C:

unsigned long int  adc;
unsigned long int  min;
unsigned long int  max;
unsigned short int out;

if (adc<=min) {
   out=0;
} else if (adc>=max) {
   out=65535;
} else {
   out=(adc-min)*65536/(max-min); /* needs 64bit intermediary precision */
}

pretty simple problem, if it wasn't for my knowledge of the MUL instruction
and also because of the necessary extended precision intermediary results,
but MUL and DIV are 16bit/32but instructions only. So the best I've done so
far is (given that adc, min and max are "only" 24bit values after all):

   out=((adc-min)*255)/(((max-min)*255+32768)/65536);

which doesn't need more than the normal usage of the MUL and DIV instructions.

But this is not ideal, how could I perform it in multiprecision, to implement
the "real" formula?

Could anybody help please?

With kind regards,
Mario

--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[Tomás Ó hÉilidhe-2]

Electron wrote:

> So, to say it in pseudo C:
>
> unsigned long int  adc;
> unsigned long int  min;
> unsigned long int  max;
> unsigned short int out;
>
> if (adc<=min) {
>    out=0;
> } else if (adc>=max) {
>    out=65535;
> } else {
>    out=(adc-min)*65536/(max-min); /* needs 64bit intermediary precision */
> }
>  

To scale a 24-Bit value to a 16-Bit value I'd shift 8 places to the right:

    long unsigned Scale24to16(long unsigned original_val)
    {
        return original_val >> 8;
    }

Then to make it more generic:

    long unsigned ScaleYtoX(long unsigned const original_val, unsigned
const y, unsigned const x)
    {
        if (y >= x) return original_val >> y-x;
               else return original_val << x-y;
    }

Now, to complicate it, let's do it within a certain range of the 24-Bit
value. Here's our 24-Bit value:

    111111111111111111111111

Now let's say our 16-Bit value should be crafted from the following
range in the 24-Bit value:
    min = 2048
    max = 4194304

Take the minimum value, and assign the most appropriate high bit, so
2048 becomes bit 11 (where bit 0 is the LSB).
Take the maximum value, and assign the most appropriate high bit, so
4194304 becomes bit 22.
(Yes, they're conveniently chosen)

So that means out 16-Bit value should be taken from the following bits
marked with an x:

    1xxxxxxxxxxxx11111111111

(That's 12 bits)

If the highest bit is set, we know that the number is out of range. If
the lower eleven are set, well they would just give us extra precision
if we wanted it. In the case of turning a 12-Bit figure into a 16-Bit
figure, we can use this extra precision, so that would be:

    1xxxxxxxxxxxxYYYY1111111

So we shift this 7 places to the right to give:

    00000001xxxxxxxxxxxxYYYY

Since we're going to discard values that are too big, we know that that
highest 1 won't be set:

    00000000xxxxxxxxxxxxYYYY

I'm getting sloppy here, but altogether it might be something like:

long unsigned ScaleRangeToX(long unsigned val, unsigned const high_bit,
unsigned low_bit, unsigned const x)
{
    unsigned const initial_bit_range = high_bit - low_bit;

    /* First of all, let's see if the value is outside the range */

    long unsigned const max_value_for_original_value = (1uL << high_bit)
- 1,
                                  min_value_for_original_value = (1uL <<
low_bit) - 1,
                                  max_value_for_return_value = (1uL <<
x) - 1;

    if ( original_value < min_value_for_original_value ) return 0;
    if ( original_value > max_value_for_original_value ) return
max_value_for_final_value;

    /* Now let's see if we can use those extra precision bits */

    unsigned const amount_precision_bits_wasted = 0;

    if (initial_bit_range < x)
    {
        unsigned const amount_extra_precision_bits = x - initial_bit_range;

        if (low_bit   >  amount_extra_precision_bits)
        {
            low_bit  -=  amount_extra_precision_bits;
            amount_precision_bits_wasted = 0;
        }          
        else
        {
            low_bit = 0;
            amount_precision_bits_wasted = amount_extra_precision_bits -
low_bit;
        }
    }

    /* Now clean the value up */

    original_value >>= low_bit - amount_precision_bits_wasted;

    return original_value;
}

The code above was thrown together in 10 minutes while I was eating my
morning porridge so it contains bugs, errors and oversights. One
particular thing I haven't paid attention to is making sure that the
number of places I shift by is less than the number of bits in the type;
for instance, if I want the highest value for 4 bits, I can do:

    (1u << 4) - 1

However, if I do this for 16 bits:

    (1u << 16) -1

then the C Standard says the behaviour is undefined if int is 16-Bit.

If you work with a range that doesn't nicely fit as a power of two, then
I think you'll have to resort to using floating-point arithmetic.

--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[Olin Lathrop]

Electron wrote:

> In short I have 24bits coming from an ADC, and I have to make them
> 16bits, but inside a certain range of these 24bits.
>
> ...
>
> if (adc<=min) {
>    out=0;
> } else if (adc>=max) {
>    out=65535;
> } else {
>    out=(adc-min)*65536/(max-min); /* needs 64bit intermediary
> precision */ }

Take your input value and subtract off MIN.  Now the rest is a scale factor
problem.  If this remaining value is still wider than 16 bits, then left
justify it in a 32 bit number and divide to get the 16 bit result.  If
ADC-MIN always fits in 16 bits, then multiply it by a scale factor such that
the result you want ends up in 16 bits near the high end of the 32 bit
product.


********************************************************************
Embed Inc, Littleton Massachusetts, http://www.embedinc.com/products
[phone].  Gold level PIC consultants since 2000.
--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[Vitaliy-2]

Electron wrote:
> although my knowledge of the dsPIC (without DSP) is getting better, I am
> now
> faced with a problem I must do absolutely bug free, because otherwise
> precious
> data would be corrupted, so I'm seeking help here.
>
> In short I have 24bits coming from an ADC, and I have to make them 16bits,
> but
> inside a certain range of these 24bits.

Mario, perhaps I don't fully understand the problem -- can you explain why
you can't simply drop the lower order bits? AFAIK, few applications require
more than 8-bit precision.

Vitaliy

--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[electron-3]

Dear Vitaliy,


At 05.59 2008.07.14, you wrote:

>Electron wrote:
>> although my knowledge of the dsPIC (without DSP) is getting better, I am
>> now
>> faced with a problem I must do absolutely bug free, because otherwise
>> precious
>> data would be corrupted, so I'm seeking help here.
>>
>> In short I have 24bits coming from an ADC, and I have to make them 16bits,
>> but
>> inside a certain range of these 24bits.
>
>Mario, perhaps I don't fully understand the problem -- can you explain why
>you can't simply drop the lower order bits?

I received many answers (for which I'm grateful), but none addressed my request,
although I think was quite clear. But since you're asking explicitly, I will
gladly answer, thinking I'm not boring at least you. ;)


>AFAIK, few applications require more than 8-bit precision.

Well, when you use a 24bit ADC then you in the first instance needed precision.
However, I've done my math and by maximixing precision (shifting left the data
before division to get maximum precision even from 32bit), I've been able to make
it work satisfactorily with 32bit math. This is what I produced, I've tested it
beside a PC running the same formula, and it works the same (that was my main
concern). In the hope it may be useful to anyone I'm posting it here:

; if (adc<=min) then out=0
                        MOV.W           #adc_h,W2
                        MOV.W           #min_h,W3
                        MOV.W           [W2--],W0
                        MOV.W           [W3--],W1
                        CP.W            W0,W1
                        BRA             LTU,1f
                        BRA             GTU,2f
                        MOV.W           [W2],W0
                        MOV.W           [W3],W1
                        CP.W            W0,W1
                        BRA             GTU,2f
1:                      CLR.W           W0
                        BRA             5f
2:
; if (adc>=min) then out=65535
                        MOV.W           #adc_h,W2
                        MOV.W           #max_h,W3
                        MOV.W           [W2--],W0
                        MOV.W           [W3--],W1
                        CP.W            W0,W1
                        BRA             GTU,3f
                        BRA             LTU,4f
                        MOV.W           [W2],W0
                        MOV.W           [W3],W1
                        CP.W            W0,W1
                        BRA             LTU,4f
3:                      MOV.W           #0xFFFF,W0
                        BRA             5f
4:
; out=((adc-min)*256)/((max-min)/256)
                        MOV.W           max_l,W0                  ; W1:W0 = max - min
                        MOV.W           min_l,W2
                        SUB.W           W0,W2,W0
                        MOV.W           max_h,W1
                        MOV.W           min_h,W2
                        SUBB.W          W1,W2,W1
                        LSR.W           W0,#8,W0                  ; W3 = W1:W0 / 256
                        SL.W            W1,#8,W1
                        IOR.W           W1,W0,W3
                        MOV.W           adc_l,W0                  ; W1:W0 = adc - min
                        MOV.W           min_l,W2
                        SUB.W           W0,W2,W0
                        MOV.W           adc_h,W1
                        MOV.W           min_h,W2
                        SUBB.W          W1,W2,W1
                        SL.W            W1,#8,W1                  ; W1:W0 *= 256
                        LSR.W           W0,#8,W2
                        IOR.W           W2,W1,W1
                        SL.W            W0,#8,W0
                        REPEAT          #17
                        DIV.UD          W0,W3
                        BRA             NOV,5f
                        MOV.W           #0xFFFF,W0                ; overflow DIV, set out to 65535 (happens only on few top values)
5:

Cheers,
Mario


>
>Vitaliy
>
>--
>http://www.piclist.com PIC/SX FAQ & list archive
>View/change your membership options at
>http://mailman.mit.edu/mailman/listinfo/piclist

--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[Olin Lathrop]

Electron wrote:
> I received many answers (for which I'm grateful), but none addressed
> my request, although I think was quite clear.

If everyone mistunderstood the question, just maybe you should consider the
question was poorly worded.

I still don't understand how this isn't just a scaling problem after a
subtraction.

> However, I've done my math and by maximixing precision (shifting left
> the data
> before division to get maximum precision even from 32bit), I've been
> able to make
> it work satisfactorily with 32bit math.

Sounds exactly like one of the suggestions I made.  I guess my answer wasn't
clear enough.


********************************************************************
Embed Inc, Littleton Massachusetts, http://www.embedinc.com/products
[phone].  Gold level PIC consultants since 2000.
--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[Tamas Rudnai]

I think we have to find out what OP wanted to say from the equations, which
was:

> out=(adc-min)*65536/(max-min);

So I guess max-min could be less or greater than 65536, but even then the
number have to be evenly scaled over the full 16bit range, right?

Multiply by 2^16 is equal to shift by 16 bits, so the storage needed from
the 24 bits is 24+16 bit, which is 40. You have 32 and 64 bit sizes
supported by C30 so I guess you have no other choice than use 64 bit. But I
think you would need to cast at least the constant to 64bit number to make
sure it will use that:

out=(adc-min)*(unsigned long long)65536/(max-min);

or

out=(adc-min)*65536ULL/(max-min);

whichever way you like.

Tamas




On Mon, Jul 14, 2008 at 8:18 PM, Olin Lathrop <olin_piclist@...>
wrote:

> Electron wrote:
> > I received many answers (for which I'm grateful), but none addressed
> > my request, although I think was quite clear.
>
> If everyone mistunderstood the question, just maybe you should consider the
> question was poorly worded.
>
> I still don't understand how this isn't just a scaling problem after a
> subtraction.
>
> > However, I've done my math and by maximixing precision (shifting left
> > the data
> > before division to get maximum precision even from 32bit), I've been
> > able to make
> > it work satisfactorily with 32bit math.
>
> Sounds exactly like one of the suggestions I made.  I guess my answer
> wasn't
> clear enough.
>
>
> ********************************************************************
> Embed Inc, Littleton Massachusetts, http://www.embedinc.com/products
> [phone].  Gold level PIC consultants since 2000.
> --
> http://www.piclist.com PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist
>

--
Rudonix DoubleSaver
http://www.rudonix.com
--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[electron-3]

At 20.18 2008.07.14, you wrote:
>Electron wrote:
>> I received many answers (for which I'm grateful), but none addressed
>> my request, although I think was quite clear.
>
>If everyone mistunderstood the question, just maybe you should consider the
>question was poorly worded.

really, the tag [Olin]: would be useful for filtering purposes.

One thing you should learn in your life is that even if you had superb
technical content to offer (please notice the "if"), your attitude makes
it superbly useless.

>I still don't understand how this isn't just a scaling problem after a
>subtraction.
>
>> However, I've done my math and by maximixing precision (shifting left
>> the data
>> before division to get maximum precision even from 32bit), I've been
>> able to make
>> it work satisfactorily with 32bit math.
>
>Sounds exactly like one of the suggestions I made.  I guess my answer wasn't
>clear enough.
>
>
>********************************************************************
>Embed Inc, Littleton Massachusetts, http://www.embedinc.com/products
>[phone].  Gold level PIC consultants since 2000.
>--
>http://www.piclist.com PIC/SX FAQ & list archive
>View/change your membership options at
>http://mailman.mit.edu/mailman/listinfo/piclist

--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

[electron-3]

Hello Tamas,


At 23.06 2008.07.14, you wrote:
>I think we have to find out what OP wanted to say from the equations, which
>was:
>
>> out=(adc-min)*65536/(max-min);
>
>So I guess max-min could be less or greater than 65536, but even then the
>number have to be evenly scaled over the full 16bit range, right?

I already knew how to get max precision from just 32bit division, what I
asked was if anybody had multiprecision / extendedprecision routines to
share (here I am rephrasing), which is the only way to compute without
approximations out=(adc-min)*65536/(max-min)

>Multiply by 2^16 is equal to shift by 16 bits, so the storage needed from
>the 24 bits is 24+16 bit, which is 40. You have 32 and 64 bit sizes
>supported by C30 so I guess you have no other choice than use 64 bit. But I
>think you would need to cast at least the constant to 64bit number to make
>sure it will use that:
>
>out=(adc-min)*(unsigned long long)65536/(max-min);
>
>or
>
>out=(adc-min)*65536ULL/(max-min);

yes, in fact I have specified that was pseudo C, and anyway my target was
assembly (DIV and MUL were mentioned).

Anyhow, it doesn't matter, I got acceptable precison, but a library with
signed and unsigned 64bit/32bit division and 32bit*32bit=64bit multiplication
would still be handy. I'm very new to the dsPIC.

With kind regards,
Mario

>
>whichever way you like.
>
>Tamas
>
>
>
>
>On Mon, Jul 14, 2008 at 8:18 PM, Olin Lathrop <olin_piclist@...>
>wrote:
>
>> Electron wrote:
>> > I received many answers (for which I'm grateful), but none addressed
>> > my request, although I think was quite clear.
>>
>> If everyone mistunderstood the question, just maybe you should consider the
>> question was poorly worded.
>>
>> I still don't understand how this isn't just a scaling problem after a
>> subtraction.
>>
>> > However, I've done my math and by maximixing precision (shifting left
>> > the data
>> > before division to get maximum precision even from 32bit), I've been
>> > able to make
>> > it work satisfactorily with 32bit math.
>>
>> Sounds exactly like one of the suggestions I made.  I guess my answer
>> wasn't
>> clear enough.
>>
>>
>> ********************************************************************
>> Embed Inc, Littleton Massachusetts, http://www.embedinc.com/products
>> [phone].  Gold level PIC consultants since 2000.
>> --
>> http://www.piclist.com PIC/SX FAQ & list archive
>> View/change your membership options at
>> http://mailman.mit.edu/mailman/listinfo/piclist
>>
>
>
>
>--
>Rudonix DoubleSaver
>http://www.rudonix.com
>--
>http://www.piclist.com PIC/SX FAQ & list archive
>View/change your membership options at
>http://mailman.mit.edu/mailman/listinfo/piclist

--
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist