modulus operand ignored in C code

Question

I have the following code:

unsigned short wrLine;
unsigned short prev = ((wrLine - 1) % 16);
wrLine = (wrLine + 1) % 16;

Which generates the following disassembly:

unsigned short prev = ((wrLine - 1) % LINES_IN_FIFO);

0041456A   movw      r3, #25282           
0041456E   movt      r3, #8192            
00414572   ldrh      r3, [r3]             
00414574   uxth      r3, r3        
00414576   add.w     r2, r3, #4294967295        
0041457A   mov.w     r3, #15              
0041457E   movt      r3, #32768           
00414582   ands      r3, r2        
00414584   cmp       r3, #0        
00414586   bge       #10           
00414588   add.w     r3, r3, #4294967295        
0041458C   orn       r3, r3, #15          
00414590   add.w     r3, r3, #1           
00414594   strh      r3, [r7, #4]   

wrLine = (wrLine + 1) % LINES_IN_FIFO;

0041463E   movw      r3, #25282           
00414642   movt      r3, #8192            
00414646   ldrh      r3, [r3]             
00414648   uxth      r3, r3        
0041464A   add.w     r2, r3, #1           
0041464E   mov.w     r3, #15              
00414652   movt      r3, #32768           
00414656   ands      r3, r2        
00414658   cmp       r3, #0        
0041465A   bge       #10           
0041465C   add.w     r3, r3, #4294967295        
00414660   orn       r3, r3, #15          
00414664   add.w     r3, r3, #1           
00414668   uxth      r2, r3        
0041466A   movw      r3, #25282           
0041466E   movt      r3, #8192  

Interestingly enough if wrLine is zero then prev will end up equaling 0xFFFF while when wrLine is 15 it will end up equaling 0x0000. Any idea why only one of these works?

Thanks, Devan

Answer 1

short data types are converted to int before any arithmetic is performed. Since your modulus is 16 it is thus an int and not an unsigned.

Don't use short if you mustn't and do mod operations only with unsigned types, here 16U.

Answer 2

First of all, for any computations, short values are promoted to int. The compiler transforms %16 into the equivalent bitwise operation &15 because it's probably more efficient on the target CPU. Actually it's transformed into & 0x8000000F: this maintains the sign bit. The result is compared with zero: if greater than 0 the lower half of the result is used directly; otherwise all the higher bits are set with a bitwise OR-NOT with 0xF. This makes the sign of the result correct.

If wrLine is 0, to subtract 1 the value is promoted to the signed int type and the result calculated is -1. The above computes -1 % 16 = -1. When -1 is stored in an unsigned short the result is 0xFFFF.

If wrLine is 15, adding 1 calculates 16, and 16 % 16 = 0.

Answer 3

Try this change

unsigned short wrLine;
unsigned short prev = ((unsigned short)(wrLine - 1) % 16);
wrLine = (wrLine + 1) % 16;

or better yet (because it works for all values of FIFO_SIZE).

int wrLine;
int prev = wrLine-1; if (prev<0) prev = FIFO_SIZE-1;
wrLine++; if (wrLine >= FIFO_SIZE) wrLine = 0;

% is expensive since it involves division. & is faster, but it only works for powers of 2.

Depending on your architecture, conditional branches may or may not have a cost (an 8051 microcontroller doesn't cost much to branch, while an x86/x64 processor has a deeper pipeline and cache misses to worry about). However, its always better to have code that works (and doesn't break easily) instead of code that doesn't work.

Answer 4

I have two recommendations. For this problem, either one will work. The fastest for a power-of-two divisor is:

wrLine = (wrLine - 1)&(16-1); /* (wrLine + 1) mod 16 */

Despite JG's remark, this (a) always works, and (b) will never be generated by the compiler when wrLine is signed. The other method is to never subtract. Instead use:

wrLine = (wrLine + 16 - 1)%16;

So long as wrLine is not initially negative, this won't create a negative result. This is the pattern to use when the divisor is not a power of 2.

I'm answering a question that has an accepted answer that's probably good enough for the asker, but that answer is not good in general. The suggestion to convert to unsigned values only works for power-of-two divisors. The conversion from signed to unsigned is (numerically) equivalent to adding a large power of 2. That's equivalent to adding 0 only if the divisor is an equal or smaller power of 2.

For example:

printf("-1 % 23U = %d", -1 % 16U);

produces:

-1 % 23U = 15

...which is clearly not 22. The most concise expression for (a mod b) I know is one of:

(a%b + b)%b /* when b>0 */
(a%b - b)%b /* when b<0 */

Those involve two divisions, so longer solutions with if or if-else will run faster. The solutions at the top of the answer will handle all cases of modular subtraction by a fixed amount.