Re: [avr-gcc-list] Re: C aliasing rules

[Lars Noschinski]

Hello!

* David Brown <address@hidden> [10-05-18 21:01]:

Thanks for your answer, David.

> Lars Noschinski wrote:
> >I'm trying to debug a strange problem, which depends on whether a
> >function is inlined (then it's broken) or not (then it's ok). Can
> >someone tell me if the following code snippet violates the C aliasing
> >rules for b1 (declared as uint8_t*, written as uint32_t* by
> >xteaDecrypt)?
[...]
> It's not impossible that this is a bug when inlining such complex
> code (and 32-bit code like this is complex on an 8-bit micro).  It's
> difficult to tell without a compilable code snippet, and some
> indication of the expected results.  If you can, you should look at
> the generated assembly to see if you can figure out what is going
> wrong.  Also try to simplify or remove parts of the code until you
> have a minimal example of the problem.
> 
> While it would be useful to find out about the problem (especially
> if it is a bug that is not already known), code like this does not
> benefit much from being inlined.  It's too complex, and requires too
> many registers - the function call overhead is therefore minimal.
> You could improve the results somewhat by manual restructuring
> (perhaps eliminating the memcpy calls), but unless XTEA_ROUNDS is
> very small, the loop there will dominate everything.

XTEA_ROUNDS is 32 and this code is far from being performance critical,
but code breaking with optimization always makes me nervous ;)

Reading more about strict aliasing issues, especially

    
http://cellperformance.beyond3d.com/articles/2006/06/understanding-strict-aliasing.html
    http://davmac.wordpress.com/2010/02/26/c99-revisited/

I'm fairly sure, that accessing a uint8_t[] via a uint32_t* constitutes
undefined behaviour; the same holds for converting the pointer by use of an
union { uint32_t[2]; uint8_t[8] }; by the gcc (4.3.4) documentation for
-fstrict-aliasing:

|     Similarly, access by taking the address, casting the resulting
|     pointer and dereferencing the result has undefined behavior, even
|     if the cast uses a union type, e.g.:
|          int f() {
|            double d = 3.0;
|            return ((union a_union *) &d)->i;
|          }

So it seems the only correct way is either changing the declaration of
xteaDecryptCbc (i.e. use uint32_t from the beginning) or using memcpy.
Or maybe some playing around with __attribute__((may_alias)).

OTOH, this problem also occurs with -fno-strict-aliasing, so maybe there
is some real bug down there in the compiler. I'll try analyising it
later.

> >If I read http://mail-index.netbsd.org/tech-kern/2003/08/11/0001.html
> >correctly, it should violate the rules?
> >
> >// 
> >---------------------------------------------------------------------------
> >void xteaDecrypt(uint32_t v[2], uint32_t const k[4]) {
> >    uint32_t v0=v[0], v1=v[1], delta=0x9E3779B9, sum=delta*XTEA_ROUNDS;
> >    for (uint8_t i=0; i < XTEA_ROUNDS; i++) {
> >        v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + k[(sum>>11) & 3]);
> >        sum -= delta;
> >        v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + k[sum & 3]);
> >    }
> >    v[0]=v0; v[1]=v1;
> >}
> >
> >void xteaDecryptCbc(uint8_t v[8], uint8_t cb[8], uint8_t const k[16]) {
> >    static uint8_t tmpbuf[8];
> >    memcpy(tmpbuf, v, 8);
> >    xteaDecrypt((uint32_t*)v, (uint32_t*)k);
> >    for (uint8_t i=0; i < 8; i++)
> >        v[i] ^= cb[i];
> >    memcpy(cb, tmpbuf, 8);
> >}
> >
> >int main(void) {
> >    uint8_t b1[8], b2[8], b3[16];
> >    xteaDecryptCbc(b1, b2 b3);
> >}
> >// 
> >---------------------------------------------------------------------------

  -- Lars