math/2017/10/13/XorRotate

[utterances-bot]

Basic XOR-rotates and their inverse

Simplified description of bijections formed only from XORs and bit rotations.

http://marc-b-reynolds.github.io/math/2017/10/13/XorRotate.html

[someferge]

Hi Marc - in re "Basic XOR Rotates and their inverses" - I tried your proposed implementation and the inverse only matches the encoded value when the constants are the same. Call me a fool, but i am doing this right? (code below)

uint8_t rot(uint8_t x,uint8_t b){

    uint8_t fi;

    fi = ((x << b) | (x >> (8 - b)));
    return fi;

}

uint8_t xor_rot2_inv(uint8_t x, uint8_t a, uint8_t b) {

      x = x^rot(x,a)^rot(x,b); 

      a = ((a+a) % 8) & 0x1f; 
      b = ((b+b) % 8) & 0x1f; 
      x = x^rot(x,a)^rot(x,b); 

      a = ((a+a) % 8) & 0x1f; 
      b = ((b+b) % 8) & 0x1f; 
      x = x^rot(x,a)^rot(x,b); 

      a = ((a+a) % 8) & 0x1f; 
      b = ((b+b) % 8) & 0x1f; 
      x = x^rot(x,a)^rot(x,b); 

      a = ((a+a) % 8) & 0x1f; 
      b = ((b+b) % 8) & 0x1f; 
      x = x^rot(x,a)^rot(x,b);   

      return x;

}

int main(int argc, char *argv[]) {

    uint8_t val = 0, valR = 0, ct,nt;
    uint8_t c = 3, dt = 5, n = 123;

    //-------------

    for(nt = 0;nt < 32;nt++) {
        for(ct = 0;ct < 8;ct++) {
            for(dt = 0;dt < 8;dt++) {
                val = nt ^ rot(nt,ct) ^ rot(nt,dt);
                valR = xor_rot2_inv(val,ct,dt);
                printf(" %5hhu %5hhu %5hhu %5hhu %5hhu\n",nt,ct,dt,val,valR);
            }
        }
    }

   return 0;

}

[Marc-B-Reynolds]

@someferge The inverse function for 8-bits needs 3 steps (8=2³). It's 5 for 32-bit and 6 for 64-bit. Fixed that up and added a method that might clarify:

uint8_t xor_rot2_inv(uint8_t x, uint8_t a, uint8_t b)
{
  x = x^rot(x,a)^rot(x,b); 

  a = (a+a) % 8;
  b = (b+b) % 8;
  x = x^rot(x,a)^rot(x,b); 

  a = (a+a) % 8;
  b = (b+b) % 8;
  x = x^rot(x,a)^rot(x,b); 

  return x;
}

void test_all()
{
  // walk through all the basic 8-bit functions:
  for(uint8_t a=1; a<=6; a++) {
    for(uint8_t b=a+1; b<=7; b++) {

      // walk through all 8-bit input
      uint32_t cnt = 1;

      // zero is always a fixed point (skipped in loop below)
      printf("(%d,%d) fixed points: 0", a,b);

      for(uint8_t i=0; i<0xff; i++) {
        uint8_t x = i+1;
        uint8_t v = x ^ rot(x,a) ^ rot(x,b);
        uint8_t r = xor_rot2_inv(v,a,b);

        // dump this value if it's a fixed point
        if (x == v) { printf(",%d", ++cnt); }

        if (x != r) { printf("ERROR\n"); exit(-1); }
      }

      printf(" : count = %d\n", cnt);
    }
  }
}

[someferge]

It works - thank you, and thank you for turning this around so quickly and on a US holiday! :)

[someferge]

Follow up - why does "for(uint8_t i=0; i<0xff; i++)" compares values "less than" 0xFF instead of "less or equal to 0xff"?

[Marc-B-Reynolds]

because we're skipping 0. inside the loop the "input" x is i+1.

[someferge]

That is true but you never make it to 255 which is still within the 8-bit boundary - you compare all the way to 254 and not beyond.

[Marc-B-Reynolds]

https://gcc.godbolt.org/z/GM8Kz49ac