Mon Nov 25 01:13:36 2024

Algorithmic Cryptanalysis (View it on amazon.com)

A CRC Press Book by Antoine Joux

Program 9.2: Basic Moebius transform code

Algorithmic cryptanalysis codes by Antoine Joux are licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported License.

#define TYPE unsigned int

/*In place Moebius transform*/
void Moebius(TYPE *Tab, TYPE size)
{ 
  int Wsize;

  TYPE i,i0,i1;  TYPE step;

  Wsize=size/(8*sizeof(TYPE));

  
  /*Moebius transform for high order bits, using word ops*/
  for (step=1;step<Wsize;step<<=1) {

    for (i1=0;i1<Wsize;i1+=2*step) {

      for (i0=0;i0<step;i0++) {
        i=i1+i0;

        Tab[i+step]^=Tab[i];
      }
    }
  }
  /*Moebius transform for low order bits, within words*/
  /* Assumes 8*sizeof(TYPE)=32 */
  for(i=0;i<Wsize;i++) {

    TYPE tmp;
    tmp=Tab[i];
    tmp^=(tmp<<16);

    tmp^=(tmp&0xff00ff)<<8;
    tmp^=(tmp&0xf0f0f0f)<<4;

    tmp^=(tmp&0x33333333)<<2;
    tmp^=(tmp&0x55555555)<<1;

    Tab[i]=tmp;
  }
}

Credits for page styles: Dynamic Drive CSS Library