Nils wrote:>... snip ...> > int ArithmeticShiftRight (int value, unsigned int shift) { > if (shift) { > /* Get unsigned version of value to work with */ > unsigned int x = (unsigned int) value;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]: <http://cbfalconer.home.att.net> Try the download section. ** Posted from http://www.teranews.com **
C and MISRA, blues... (arithmetic shifts)
Started by ●April 24, 2008
Reply by ●April 24, 20082008-04-24
Reply by ●April 24, 20082008-04-24
On 2008-04-24, Nils <n.pipenbrinck@cubic.org> wrote:> 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.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, visi.com huh, is it??
Reply by ●April 25, 20082008-04-25
David Brown wrote:> 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.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 by ●April 25, 20082008-04-25
In article <67ccn9F2na9h5U1@mid.uni-berlin.de>, Nils says...> 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: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 http://www.teranews.com **
Reply by ●April 25, 20082008-04-25
Wilco Dijkstra wrote:> "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 > >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 by ●April 25, 20082008-04-25
"David Brown" <david@westcontrol.removethisbit.com> wrote in message news:48118b7c$0$2677$8404b019@news.wineasy.se...> Wilco Dijkstra wrote: >> "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 > > 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!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...> 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.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 by ●April 25, 20082008-04-25
"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. > > > 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; > } >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. + http://www.FreeRTOS.org & http://www.FreeRTOS.org/shop 17 official architecture ports, more than 5000 downloads per month. + http://www.SafeRTOS.com Certified by T�V as meeting the requirements for safety related systems.
Reply by ●April 25, 20082008-04-25
Wilco Dijkstra wrote:> "David Brown" <david@westcontrol.removethisbit.com> wrote: >... snip ...> >> 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! > > 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...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.> >> 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. > > 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...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]: <http://cbfalconer.home.att.net> Try the download section. ** Posted from http://www.teranews.com **
Reply by ●April 25, 20082008-04-25
FreeRTOS.org wrote:> "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. >> >> >> 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; >> } >> > > 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.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 by ●April 25, 20082008-04-25
Hans-Bernhard Br�ker wrote:> 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?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 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 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1+2E2, reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1+2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined. [#5] 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]: <http://cbfalconer.home.att.net> Try the download section. ** Posted from http://www.teranews.com **
