EmbeddedRelated.com
Forums

C and MISRA, blues... (arithmetic shifts)

Started by Nils April 24, 2008
I'm currently rewriting some numerical code for MISRA compliance.

Signed shifts are not defined by the C-standard, and the code-checker 
complaints. Well - no big surprise here. I knew that and did it 
nevertheless. Now I have to rewrite.


But do you do if you need them anyway? I need *lots* of them, so in 
despair I've just created this monster of unreadable code:


int ArithmeticShiftRight (int value, unsigned int shift)
{
   if (shift)
   {
     /* Get unsigned version of value to work with */
     unsigned int x = (unsigned int) value;

     /* replicate the sign-bit of value into all bits of SignMask: */
     unsigned int SignMask = ((unsigned int) -(value < 0));

     /* assemble the arithmetic shift from two unsigned shifts. */
     x = (x>>shift)|(SignMask<<(32-shift));

     /* writeback result as signed integer */
     value = (int) x;
   }
   return value;
}


I just had the urge to share this huge wtf code with you. It's horrible. 
It's unreadable, and all it does is doing a stupid shift.

Has anyone here seen a C-compiler that does something different than 
arithmetic shifts on signed integers in the last 20 years? I've used a 
lot of compilers over the years, and they all shifted arithmetic.

   Nils
On 2008-04-24, Nils <n.pipenbrinck@cubic.org> wrote:
> I'm currently rewriting some numerical code for MISRA compliance. > > Signed shifts are not defined by the C-standard, and the code-checker > complaints. Well - no big surprise here. I knew that and did it > nevertheless. Now I have to rewrite. > > > But do you do if you need them anyway? I need *lots* of them, so in > despair I've just created this monster of unreadable code: > > > int ArithmeticShiftRight (int value, unsigned int shift) > { > if (shift) > { > /* Get unsigned version of value to work with */ > unsigned int x = (unsigned int) value; > > /* replicate the sign-bit of value into all bits of SignMask: */ > unsigned int SignMask = ((unsigned int) -(value < 0)); > > /* assemble the arithmetic shift from two unsigned shifts. */ > x = (x>>shift)|(SignMask<<(32-shift)); > > /* writeback result as signed integer */ > value = (int) x; > } > return value; > } > > > I just had the urge to share this huge wtf code with you. It's horrible. > It's unreadable, and all it does is doing a stupid shift.
Here's something different, but I don't know if it's less ugly. int ArithmeticShiftRight (int value, unsigned int shift) { switch (shift) { case 0: return value; case 1: return value/2; case 2: return value/4; case 3: return value/8; ... } } [It only handles positive values for the shift parameter.] One assumes the compiler is bright enough to optimize value/N to an arithmetic right shift in the case where N is a constant power of two. Since the case values are contiguous and 0-based, that ought to turn into some sort of indexed or table-driven jump that shouldn't result in more that a couple instructions of overhead.
> Has anyone here seen a C-compiler that does something > different than arithmetic shifts on signed integers in the > last 20 years? I've used a lot of compilers over the years, > and they all shifted arithmetic.
I've never seen one that doesn't do an arithmetic right shift on signed value... -- Grant Edwards grante Yow! Hello? Enema Bondage? at I'm calling because I want visi.com to be happy, I guess ...

Nils wrote:

> I'm currently rewriting some numerical code for MISRA compliance. > > Signed shifts are not defined by the C-standard, and the code-checker > complaints. Well - no big surprise here. I knew that and did it > nevertheless. Now I have to rewrite. > > But do you do if you need them anyway? I need *lots* of them, so in > despair I've just created this monster of unreadable code: > > int ArithmeticShiftRight (int value, unsigned int shift) > { > if (shift) > { > /* Get unsigned version of value to work with */ > unsigned int x = (unsigned int) value; > > /* replicate the sign-bit of value into all bits of SignMask: */ > unsigned int SignMask = ((unsigned int) -(value < 0)); > > /* assemble the arithmetic shift from two unsigned shifts. */ > x = (x>>shift)|(SignMask<<(32-shift)); > > /* writeback result as signed integer */ > value = (int) x; > } > return value; > } > > I just had the urge to share this huge wtf code with you. It's horrible. > It's unreadable, and all it does is doing a stupid shift. > > Has anyone here seen a C-compiler that does something different than > arithmetic shifts on signed integers in the last 20 years? I've used a > lot of compilers over the years, and they all shifted arithmetic.
I am sure you have looked into sign extend and possibly a divide something like if (shift) value = value / (1 << shift); I haven't checked what misra says about signed divide by integer but one possibility is the compiler may very well change the code into an arithmetic shift. One possible implementation other than a function call might be #define asr(shift,value) if (shift) (value = value / (1 << shift)) if shift is a constant and 0 then the compiler would eliminate the statement with dead code removal. w..
Grant Edwards schrieb:
> Here's something different, but I don't know if it's less ugly. > > int ArithmeticShiftRight (int value, unsigned int shift) > { > switch (shift) > { > case 0: return value; > case 1: return value/2; > case 2: return value/4; > case 3: return value/8; > ... > } > } >
I thought about this one as well. With loop-unswitching optimization enabled it wouldn't just give a bit of code-bloat but give perfect code. However, it does not work if value is negative because (-7/2) != (-7>>1). A little known fact and often we can live with it, but I can't. To bad..
> One assumes the compiler is bright enough to optimize value/N to > an arithmetic right shift in the case where N is a constant > power of two. Since the case values are contiguous and > 0-based, that ought to turn into some sort of indexed or > table-driven jump that shouldn't result in more that a couple > instructions of overhead.
Speaking of optimizations: I just had a look at the assembly output and GCC generates pretty good code for my function. It does not turn it into a arithmetic shift. Guess that would be asking for to much, but it does some very clever tricks :-) Nils
Nils wrote:
> I'm currently rewriting some numerical code for MISRA compliance. > > Signed shifts are not defined by the C-standard, and the code-checker > complaints. Well - no big surprise here. I knew that and did it > nevertheless. Now I have to rewrite. > > > But do you do if you need them anyway? I need *lots* of them, so in > despair I've just created this monster of unreadable code: >
How about: int ArithmeticShiftRight (int value, unsigned int shift) { if (value < 0) { return -((int) (((unsigned int) (-value)) >> shift); } else { return ((int) (((unsigned int) (value)) >> shift); } } It's still horrible, but it probably compiles to better code.
"Nils" <n.pipenbrinck@cubic.org> wrote in message news:67ccn9F2na9h5U1@mid.uni-berlin.de...
> I'm currently rewriting some numerical code for MISRA compliance. > > Signed shifts are not defined by the C-standard, and the code-checker complaints. Well - no big surprise here. I knew > that and did it nevertheless. Now I have to rewrite.
Sounds like you're going to write some seriously unreadable, unmaintainable and most likely buggy code... Try to explain that one to your manager! The C standard rather stupidly accomodates the merely theoretical case of one's complement (where the obvious implementation of signed shift would round negative numbers differently). MISRA has some good rules but there are a lot of bad ones as well. It's best to pick a subset - the last time I looked at it I threw out more than half of the rules.
> Has anyone here seen a C-compiler that does something different than arithmetic shifts on signed integers in the last > 20 years? I've used a lot of compilers over the years, and they all shifted arithmetic.
There is no compiler that doesn't correctly implement signed arithmetic. Nobody could get away with creating a compiler that can't compile existing code. Wilco
"David Brown" <david.brown@hesbynett.removethisbit.no> wrote in message 
news:5_GdnfetN7l7m4zVnZ2dneKdnZydnZ2d@lyse.net...
> Nils wrote: >> I'm currently rewriting some numerical code for MISRA compliance. >> >> Signed shifts are not defined by the C-standard, and the code-checker complaints. Well - no big surprise here. I knew >> that and did it nevertheless. Now I have to rewrite. >> >> >> But do you do if you need them anyway? I need *lots* of them, so in despair I've just created this monster of >> unreadable code: >> > > How about: > > int ArithmeticShiftRight (int value, unsigned int shift) > { > if (value < 0) { > return -((int) (((unsigned int) (-value)) >> shift); > } else { > return ((int) (((unsigned int) (value)) >> shift); > } > } > > It's still horrible, but it probably compiles to better code.
But it's incorrect as it doesn't round the same way. Wilco
Nils wrote:

> But do you do if you need them anyway?
Check very thoroughly why you think you need them. Shifting is not really a numerical operation, so why should something you describe as "numerical code" need it in the first place?
> I just had the urge to share this huge wtf code with you. It's horrible. > It's unreadable, and all it does is doing a stupid shift.
Erm, how is it MISRA's fault if you decide to write such horrible code? Why not express numerical operations by use of the arithmetic operators they're supposed to represent? #define ASR(input, count) (input / (signed)(1 << count))
"Walter Banks" <walter@bytecraft.com> wrote in message news:4811043E.B3ACBFAE@bytecraft.com...

> I am sure you have looked into sign extend and possibly a divide > something like > > if (shift) value = value / (1 << shift);
That doesn't round correctly either.
> #define asr(shift,value) if (shift) (value = value / (1 << shift))
This has at least 4 different problems... Wilco

Wilco Dijkstra wrote:

> "Walter Banks" <walter@bytecraft.com> wrote in message news:4811043E.B3ACBFAE@bytecraft.com... > > > I am sure you have looked into sign extend and possibly a divide > > something like > > > > if (shift) value = value / (1 << shift); > > That doesn't round correctly either. > > > #define asr(shift,value) if (shift) (value = value / (1 << shift)) > > This has at least 4 different problems... >
I hit return too soon. :)