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

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

Reply to
Nils
Loading thread data ...

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.

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
 Click to see the full signature
Reply to
Grant Edwards

I am sure you have looked into sign extend and possibly a divide something like

if (shift) value = value / (1

Reply to
Walter Banks

Grant Edwards schrieb:

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..

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

Reply to
Nils

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.

Reply to
David Brown

complaints. Well - no big surprise here. I knew

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.

arithmetic shifts on signed integers in the last

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

Reply to
Wilco Dijkstra

complaints. Well - no big surprise here. I knew

I've just created this monster of

But it's incorrect as it doesn't round the same way.

Wilco

Reply to
Wilco Dijkstra

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?

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

Reply to
Hans-Bernhard Bröker

Reply to
Wilco Dijkstra

I hit return too soon. :)

Reply to
Walter Banks

... snip ...

This operation is not possible in a standard C system. Think about what would happen to negative values in sign-magnitude, 1's complement, or 2's complement.

--
 [mail]: Chuck F (cbfalconer at maineline dot net) 
 [page]: 
 Click to see the full signature
Reply to
CBFalconer

Doh. I forgot about that. I guess I write too much python:

$ python Python 2.4.4 (#1, Mar 19 2008, 14:48:47) [GCC 4.1.2 (Gentoo 4.1.2 p1.0.2)] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> -7/2 -4 >>> -7>>1 -4 >>>

--
Grant Edwards                   grante             Yow! Is this sexual
                                  at               intercourse yet??  Is it,
 Click to see the full signature
Reply to
Grant Edwards

Part of the problem is defining what you want. C works for two's complement, ones complement, and absolute value and sign.

If you define arithmetic right shift as "shift right leaving the sign bit unchanged", then you get the following: Expression 2scomp 1scomp AV&S ASR(-4,1) -2 -2 -2-UINT_MAX/2 ASR(-3,1) -2 -1 -1-UINT_MAX/2

-4/2 -2 -2 -2

-3/2 -1 -1 -1

The last expression is only defined that way in C99.

Do you want to implement the two's complement version of ASR in all cases or the "shift right leaving the sign bit unchanged" or something else?

--
Thad
Reply to
Thad Smith

Echoing the question. What do you need them for that's not covered by a divide by a power of 2?

What about

int asr( int x, unsigned int shift) { unsigned int temp;

temp=(unsigned int)x;

if( x < 0) { temp = ~((~temp) >> shift); } else { temp >>= shift; } return (int)temp; }

Does that cover all the cases? For a negative value it converts the sign extend to a zero extend and the positive case works as usual.

Commenting left to the user.

It's small enough you could probably make a macro (with some loss of clarity) and for constant shifts a good compiler might end up optimizing it back to a ASR. Maybe?

Or, take the simple way out and declare an exception (whatever the term is MISRA uses for a formal waiver of a rule). As I recall they can apply at indivual case, project level or as company policy as an exception. They do need to be documented though.

Robert

** Posted from
formatting link
**
Reply to
Robert Adsett

complaints. Well - no big surprise here. I knew

I've just created this monster of

Is the rounding of shifts like this well defined in C? I can't remember the exact rules off-hand - perhaps that's why MISRA doesn't like right shifts of signed integers!

Would this be more correct?

return ~((int) (((unsigned int) (~value)) >> shift);

I haven't checked it - in particular, corner cases must be checked. I'm just spouting ideas for the OP.

Reply to
David Brown

complaints. Well - no big surprise here. I

I've just created this monster of

exact rules off-hand - perhaps that's why

No it's not well defined, just like most other things in C, but who cares anyway?!?

Compiler writers agree on most of these things, so in reality these things are extremely well defined. Basically nobody cares about what the C standard says exactly as long as their code compiles. If it doesn't work on a particular compiler, it is that compiler's fault. I know, I have dealt with angry customers with millions of lines of code that didn't compile on our expensive but strict ANSI C compiler...

spouting ideas for the OP.

That's right indeed (replacing the first return above). Of course this still gives you correct behaviour only on 2-complement's CPUs. So it adds a lot of overhead and bugs (given only the OP got it right first time) for no gain whatsoever...

Wilco

Reply to
Wilco Dijkstra

IMHO the point is being missed here. MISRA is intended to assist in making your code safer. Obfuscation is never safer - from any point of view (review, error #, maintenance, etc.). MISRA is a "guide", so let it be just that. Rigorous compliance at all cost in an embedded system will result in junk code.

Our approach to this would be to run a check on the code, and let all the none compliances be documented. Most of these non compliances can then be cleared up with the minimum of effort, but there will be some for which it makes no sense to change the code. Therefore only a handful of non-compliances make it through to the code review phase. During the code review actions will be raised to - for example - check exactly what the compiler does given the input. The result of this check (test) is then also documented. Once this is done the senior developer can deviate the remaining non-compliances with a sound rational argument, safe in the knowledge that (in combination with other testing) the code is going to behave as intended. MISRA has done its job - it has highlighted a possible flaw in your code. The engineers have done their job to ensure that the highlighted items are removed or guaranteed to do what is expected.

Which is safer - to have a single line that shifts code in an easily understandable, obvious way, that is reviewed, tested and checked, or to replace this with what by your own admission is more confusing.

--
Regards,
Richard.
 Click to see the full signature
Reply to
FreeRTOS.org

... snip ...

You need copies of the C standard to hand out. Most of those problems have been discussed here, so you have a good selection of immediate answers and suggestions available.

It's still fundamentally wrong - you can't guarantee unsigned to signed casts, because an overflow may occur, and the result is implementation defined behaviour.

--
 [mail]: Chuck F (cbfalconer at maineline dot net) 
 [page]: 
 Click to see the full signature
Reply to
CBFalconer

This is IMO exactly how MISRA should be used. I've been obeying MISRA in my coding at work for years (well, sort of), while there are some things I think are very good (e.g. it makes you think very carefully about casting and potential overflows, it doesn't like magic numbers, etc etc), there are some things I get annoyed at, such as:

  • You're not supposed to use "goto". Avoiding this when you're learning to write code is good practise, but it's very useful in a limited set of circumstances, if used properly. I remember a manager of mine telling a work colleague once that using "goto" was bad practise, I then showed my colleague my copy of K+R which basically put him right.
  • You're not supposed to exit from a controlled loop prematurely.
  • ... Hmm, actually I could go on for a while. Suffice to say, there are a few things...!

I've seen some tidy well-written code turned inside out and made semi-unreadable by trying to make it MISRA compliant. If it makes code more complicated (and more error-prone) then it's doing the opposite of what's intended. I had a chat with a manager of mine about this once and he said that MISRA was basically a guide, obey it if you can, but if there is a problem with doing this then all that was needed was to document the non-compliances. For me, this is a far more sensible approach. Sort out the obvious clangers, but don't turn good neat code into jumbled unreadable rubbish just to satisfy MISRA!!

The problem is there is some misunderstanding here. MISRA lists it's rules as "recommended" and "required" (or something like that), which makes it sound like "required" rules MUST be obeyed, which doesn't appear to be the case from what I now understand.

R.

Reply to
Richard Phillips

Shifting IS a numerical operation. Read the following description, from the C standard. Notice the 'undefined' cases for negative operands.

6.5.7 Bitwise shift operators

Syntax [#1] shift-expr: additive-expr shift-expr > additive-expr

Constraints

[#2] Each of the operands shall have integer type.

Semantics

[#3] The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined. [#4] The result of E1 > E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 divided by the quantity, 2 raised to the power E2. If E1 has a signed type and a negative value, the resulting value is implementation- defined.
--
 [mail]: Chuck F (cbfalconer at maineline dot net) 
 [page]: 
 Click to see the full signature
Reply to
CBFalconer

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.