Efficient division in CCS C Compiler

[Yosmany325]

Hello everyone!

I want to know if is possible to obtain the quotient and remaining of integer division in CCS in the same produced code. Let´s see an example of what I want to obtain:

unsigned int32 average;
unsigned int8 ave_intPart;
unsigned int8 ave_decPart;

/* The average variable will never be greater than 10000 */

/* Obtain the 'integer' part */
ave_intPart = average / 100;

/* Obtain the 'decimal' part */
ave_decPart = average % 100;

This code is to encode a percent number using fixed point notation, for example an average = 10000 should give ave_intPart = 100 and ave_decPart = 00.

What I need is a way to reduce instruction count and time required to do this without repeating the division operation (I mean, the compiler be so smart to use just one operation [division] and to store the quotient and remainder at provided variables).

For example suposse the compiler generates something like the following

/* C */

ave_intPart = average / 100;

/* Asm generated code */
movlw 100
...
<a lot of instructions>

/* C */
ave_intPart = average % 100;

/* Asm generated code */
movlw 100
...
<a lot of instructions>


and what I need it to do is something like this

/* C */

ave_intPart = average / 100;

/* C */
ave_intPart = average % 100;

/* Asm generated code */
movlw 100
...
< Here use the temp results to populate both variables, i.e. ave_intPart and ave_decPart >
<a lot of instructions>

Thanks in advance for your help. Yosmany

 

[FvM]

The best standard C option for a processor without hardware divider is to calculate the quotient and then the remainder by means of a multiply and a substraction. The stdlib.h functions div() and ldiv() are doing so.

Otherwise you need to write assembly code.

 

[Yosmany325]

Thanks for your fast reply, I tried this in CCS Compiler but is does not support this function using variables. It says this expression must evaluate constant. This is a fragment of the code. I used coditional compilation directives to select the best way.

humedad = suma * 100 / 2046 + 1000;
   
#define USE_DIV
   
#ifndef USE_DIV
   hum_int = humedad / 100;
   hum_dec = humedad % 100;
#else
   ldiv_t temp = ldiv(humedad, 100); // Here appears the error
   hum_int = temp.quot;
   hum_dec = temp.rem;
#endif

the error is "Expression must evaluate to a constant"

Thanks anyway for your reply. Yosmany.

 

[FvM]

CCS C doesn't support the C++ style of defining variables in line. Standard C allows variable declarations only at the begin of a block.

 

[doraemon]

Hello!

One trick I am using, but which supposes that you always divide by the same number, which is the case here (100):
- define your own fixed point scheme
- instead of dividing by predefined x, multiply by predefined 1/x.
- use the above mentioned method for the decimal:
n = number to divide
i = integer part
d = decimal part.
you can calculate i with the above method (your predefined 1/100)
then d = n - 100 * i.

NB: I can't guarantee that it works in all the cases. Especially if you want 5 decimals on a 16-bit system, then you might
have problems, but it's worth trying.

Dora.

 

[Yosmany325]

Thanks FvM, you are right, I changed the code to

 ldiv_t temp;
   
   temp = ldiv(humedad, 100);
   hum_int = temp.quot;
   hum_dec = temp.rem;

and it compiled successfully. The point is that using this way the generated code is larger, i.e. using the clasic method of division and modulus the code size takes 34% of ROM space and using ldiv it takes 37% of ROM memory. Anyway was very helpful your post. Yosmany.

- - - Updated - - -

Hello!

One trick I am using, but which supposes that you always divide by the same number, which is the case here (100):
- define your own fixed point scheme
- instead of dividing by predefined x, multiply by predefined 1/x.
- use the above mentioned method for the decimal:
n = number to divide
i = integer part
d = decimal part.
you can calculate i with the above method (your predefined 1/100)
then d = n - 100 * i.

NB: I can't guarantee that it works in all the cases. Especially if you want 5 decimals on a 16-bit system, then you might
have problems, but it's worth trying.

Dora.

Hello Dora, thanks for your reply. In my case the idea is to encode relative humidity percent as an unsigned integer in the range from 0 to 10000 with 0 meaning 0% and 10000 meaning 100.00%. I read your post but I don´t know how to implement this, i.e. how to encode a 1/100 using an integer?.

Right now what I do is divide by 100 to obtain integer part and the remain (using % operator) is the decimal part.

Yosmany.

 

[andre_luis]

There is a smart way to do that division operation when divider is constant - without a repeating process - but you have to pay a loss on accuracy. The trick is just to replace a division by a multiplication followed by a shift operation. Note that both these operations have already built in instructions at most microcontroller CPUs.

For instance, on the case above, you could do something like that:

---

Code C - [expand]
1
2
3
4
5
// This code you wrote...
ave_intPart = average / 100;
 
//...is similar to that, which yields an error smaller than 1% :
ave_intPart = ( average * 41 )>>12  ;

---

You must to perform some simulations to certify if this really is advantageous for your case. Don´t forget to declare the variable as long, unless compiler do the casting itself.

 

[doraemon]

Hello!

Sorry for the delay!

Hello Dora, thanks for your reply. In my case the idea is to encode relative humidity percent as an unsigned
integer in the range from 0 to 10000 with 0 meaning 0% and 10000 meaning 100.00%. I read your post but
I don´t know how to implement this, i.e. how to encode a 1/100 using an integer?.

Basically andre_teprom explained it...
Here is what I was trying to say, with a little bit more detail.
Here is how to perform a division with a multiplication.
1. I was telling you to decide upon your own fixed point scheme. Some processors have a hardware floating
point multiplication (which is in fact an integer multiplication).

I suppose we can agree that multiplying 2 numbers of 16 bits will give you one 32-bit value.
Now if you consider a 32-bit value, let's call it ACC, then you can split it into 2 16-bit values, let's call them ACC_L and ACC_H.

Now you can decide for example that ACC_L full scale (0x00010000) means 1. If you multiply any 16-bit integer with
this value, you will obtain the same integer, but shifted by 16 bits on the left (i.e. multiplied by 65536).

Suppose now that you use 0x00008000, which is half of the above number, then if you multiply any number by this one, you
will get half of your number in the upper ACC.

You can continue with 1/4 (0x00004000), 1/8 (0x00002000), etc, in which case you will have numbers that, multiplied
with any 16-bit value, give you 1/2, 1/4, 1/8 ... of the former value in the upper ACC.

Since the multiplication distributes over the addition, you can also verify that a 16-bit value multiplied by (0x00008000 + 0x00004000)
would give you 3/4 of that value in the upper ACC.

2. Now how to divide by 100? Multiply by 1/100.
If 1 corresponds to 0x00010000 or 2^16 or 65536, then 1/100 corresponds to 655.36 that you have to cut down to 655.
So if you want to divide any 16-bit value by 100, you multiply it by 655 and you get the result in the upper ACC.

3. Let's try the trick!
Example: you want to write 3209 as 32.09.
Multiply 3209 by 655. You get 2101895, which can be written 0x00201287 in hexa.
So your integer part will be 0x0020 (which is 32. Good news, that's what we are looking for).
And then for the 09, you just calculate 3209 - 32 * 100, and you will get 9. At this point, you should be careful that the 0 disappears
and you have to add it yourself if the decimal part is less than 10.

I just tried a float division (with a MSP430) and it takes 400 cycles. And the calculation abouve should be feasible in very few
cycles, maybe 10 or 20.

That's about it.

Dora.

 

[andre_luis]

I just tried a float division (with a MSP430) and it takes 400 cycles

Hi Dora,


Coincidentally, I did that at the same 16bit core as you, many years ago.
Differently from the case above on which Yosmany intends to divide by 100, I divided a ‘long’ type by 12.

The achieved average gain in terms of time performance on simulation environment was, if I remember correctly, ~600 ran instructions at intrinsic float division vs. ~240 ran instructions with such approach, an enhancement close to 3x on speed performance at this specific operation. At this case, I replaced the original C standard operator “/” by a function like:

long Divide ( long num1, long num2 ) ;

I presume that for the case above, once the magnitude required for the variable certainly is not so big as mine, he much probably would achieve a better performance as you mentioned by using an ‘int’ type.

 

[doraemon]

Hello!

One other trick to get that kind of performance (but this applies only to MSP430 or other chips that have a coprocessor):
One multiplication 16 x 16 -> 32 bits with the coprocessor takes about 5 cycles. And you don't have to shift the result,
you just use ACC_H which exists in hardware (I don't remember the real name, something like REG_HIGH and REG_LOW).
But of course I didn't take into account all the work of putting the obtained numbers into a string, etc...

Dora.

 

[Yosmany325]

First, I would like to thanks to Dora for a "so detailed" explanation. I was really wonderful, I understood even things related to other operations. This is a very smart way to do things in a resource-limited system. I hope this will be also useful to other people seen this post. Thank you very much one more time. Also I would like to thanks everyone who helped to solve this issue. Yosmany.