50 example 64-bit bijections using CRC32-C opcode (brute force validate)

quick.c

// if 'f' is the 64-bit input CRC32-C (with 'incoming' 32-bit value of zero) then
// there are 50 bijections (invertiable functions) which are a sum of f
// and a simple xorshift. So the follow two forms:
//
//   f(x) ^ (x ^ (x << S))
//   f(x) ^ (x ^ (x >> S))
//
// and 23 using a rotate instead of a shift:
//
//   f(x) ^ (x ^ rot(x,S))
//
// if 'c' is the 32-bit CRC32-C (one input is zero) and x0 & x1 are lower and
// upper 32-bit parts of 'x' then:
//
//   f(x) = c(x1) + c^2(x0)
//
// which is a uniform 2^32 to 1 mapping. Allowing the 32-bit input (assumed to be
// zero above) to be any value is also a bijection (code doesn't demo this) since
// it just adds an XOR by constant to the total function which can be considered
// a second logical step (and XOR by constant is invertiable)

// requires m4ri (https://bitbucket.org/malb/m4ri/src/master)

// clang -O3 -march=native -Wall -Wextra -Wconversion -Wpedantic quick.c -o quick -lm4ri

// EYE WARNING: total garbage code..ripped from an even bigger mess

#include <assert.h>

#include <m4ri/m4ri_config.h>
#include <m4ri/m4ri.h>
#include <x86intrin.h>

#define PRINT_MATRIX

//#define PRINT_FAIL

/*
f(x) ^ (x ^ rot(x, 1))
f(x) ^ (x ^ rot(x, 5))
f(x) ^ (x ^ rot(x, 6))
f(x) ^ (x ^ rot(x, 8))
f(x) ^ (x ^ rot(x,15))
f(x) ^ (x ^ rot(x,19))
f(x) ^ (x ^ rot(x,20))
f(x) ^ (x ^ rot(x,22))
f(x) ^ (x ^ rot(x,23))
f(x) ^ (x ^ rot(x,24))
f(x) ^ (x ^ rot(x,25))
f(x) ^ (x ^ rot(x,29))
f(x) ^ (x ^ rot(x,30))
f(x) ^ (x ^ rot(x,31))
f(x) ^ (x ^ rot(x,33))
f(x) ^ (x ^ rot(x,39))
f(x) ^ (x ^ rot(x,49))
f(x) ^ (x ^ rot(x,50))
f(x) ^ (x ^ rot(x,54))
f(x) ^ (x ^ rot(x,58))
f(x) ^ (x ^ rot(x,60))
f(x) ^ (x ^ rot(x,61))
f(x) ^ (x ^ rot(x,62))

f(x) ^ (x ^ (x>> 2))
f(x) ^ (x ^ (x>> 3))
f(x) ^ (x ^ (x>> 4))
f(x) ^ (x ^ (x>> 5))
f(x) ^ (x ^ (x>> 6))
f(x) ^ (x ^ (x>> 7))
f(x) ^ (x ^ (x>>12))
f(x) ^ (x ^ (x>>13))
f(x) ^ (x ^ (x>>19))
f(x) ^ (x ^ (x>>22))
f(x) ^ (x ^ (x>>23))
f(x) ^ (x ^ (x>>26))
f(x) ^ (x ^ (x>>27))
f(x) ^ (x ^ (x>>28))
f(x) ^ (x ^ (x>>29))
f(x) ^ (x ^ (x>>31))

f(x) ^ (x ^ (x<< 1))
f(x) ^ (x ^ (x<< 3))
f(x) ^ (x ^ (x<< 4))
f(x) ^ (x ^ (x<< 7))
f(x) ^ (x ^ (x<< 9))
f(x) ^ (x ^ (x<<10))
f(x) ^ (x ^ (x<<11))
f(x) ^ (x ^ (x<<12))
f(x) ^ (x ^ (x<<14))
f(x) ^ (x ^ (x<<16))
f(x) ^ (x ^ (x<<17))
f(x) ^ (x ^ (x<<18))
f(x) ^ (x ^ (x<<21))
f(x) ^ (x ^ (x<<24))
f(x) ^ (x ^ (x<<26))
f(x) ^ (x ^ (x<<27))
f(x) ^ (x ^ (x<<28))
f(x) ^ (x ^ (x<<30))
f(x) ^ (x ^ (x<<31))
f(x) ^ (x ^ (x<<32))
f(x) ^ (x ^ (x<<35))
f(x) ^ (x ^ (x<<36))
f(x) ^ (x ^ (x<<38))
f(x) ^ (x ^ (x<<42))
f(x) ^ (x ^ (x<<43))
f(x) ^ (x ^ (x<<44))
f(x) ^ (x ^ (x<<45))
f(x) ^ (x ^ (x<<48))
f(x) ^ (x ^ (x<<50))
f(x) ^ (x ^ (x<<53))
f(x) ^ (x ^ (x<<55))
f(x) ^ (x ^ (x<<57))
f(x) ^ (x ^ (x<<60))
f(x) ^ (x ^ (x<<63))
*/


static inline uint32_t crc32c_64(uint64_t x, uint32_t k) { return (uint32_t)_mm_crc32_u64(k,x); }


// these are the two shift mixing functions and one rotate tested. 

// don't have affine matrix support in this file: so K must be zero
#define K 0

uint32_t shift = 1;
uint64_t ls_mix(uint64_t x) { return crc32c_64(x,K) ^ (x ^ (x>>shift)); }
uint64_t rs_mix(uint64_t x) { return crc32c_64(x,K) ^ (x ^ (x<<shift)); }

static inline uint64_t rot_64(uint64_t x, uint32_t n) { n &= 0x3f; return (x<<n) | (x>>(-n & 0x3f)); }

uint64_t c_mix(uint64_t x) { return crc32c_64(x,K) ^ (x ^ rot_64(x,shift)); }


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

typedef uint64_t ufunc_64_t(uint64_t);

enum {
  MAT_TEMP_1,
  MAT_TEMP_2,
  MAT_NUM
};

// NOTE: no plans to multithread ATM (but I should abstract this a bit anyway)
// like at gettemp functions

typedef struct {
  mzd_t*   id;
  uint32_t dim;
  uint32_t n;
  mzd_t*   m[MAT_NUM];
} mat_common_t;

mat_common_t mat_32_common;
mat_common_t mat_64_common;
mat_common_t mat_32h_common;
mat_common_t mat_64h_common;

void mat_init_i(mat_common_t* data, uint32_t dim)
{
  data->dim = dim;
  data->id  = mzd_init((rci_t)dim,(rci_t)dim);
  mzd_set_ui(data->id, 1);

  for(int i=0; i<MAT_NUM; i++)
    data->m[i] = mzd_init((rci_t)dim,(rci_t)dim);
}

#define MAT_FREE(X) { mzd_free(X); (X)=0; }

void mat_free_i(mat_common_t* data)
{
  MAT_FREE(data->id);

  for(int i=0; i<MAT_NUM; i++) {
    MAT_FREE(data->m[i]);
  }
}

// fill in a M4RI matrix (d) with row-major dense matrix
void mat_from_dense_64(mzd_t* d, uint64_t* s)
{
  for(rci_t y=0; y<64; y++) {
    uint64_t row = s[y];
    for(rci_t x=0; x<64; x++) {
      mzd_write_bit(d,x,y, (row & 1));
      row >>= 1;
    }
  }
}

void mat_init()
{
  mat_init_i(&mat_32_common,  32);
  mat_init_i(&mat_32h_common, 33);
  mat_init_i(&mat_64_common,  64);
  mat_init_i(&mat_64h_common, 65);
}

void mat_free()
{
  mat_free_i(&mat_32_common);
  mat_free_i(&mat_32h_common);
  mat_free_i(&mat_64_common);
  mat_free_i(&mat_64h_common);
}

uint64_t mat_dense_from_func_64(uint64_t* m, uint64_t (*f)(uint64_t))
{
  // an input of zero should yield a zero result. if not
  // work on the assumption that it's 'f' is actually
  // affine.
  uint64_t t = f(0);

  for(uint64_t i=0; i<64; i++) { m[i]=0; }
    
  // build up matrix using single bit inputs
  for(int i=0; i<64; i++) {
    uint64_t p = UINT64_C(1)<<i;
    uint64_t r = f(p) ^ t;

    for(int j=0; j<64; j++) {
      m[j] ^= ((r & (UINT64_C(1)<<j)) != 0) ? p : 0;
    }
  }

  return t;
}

void mat_print(mzd_t* M)
{
#if 1
  rci_t n = M->nrows;

  for (rci_t r=0; r<n; r++) {
    for (rci_t c=0; c<n; c++) {
      rci_t v = mzd_read_bit(M,r,c);
      putchar(v!=0 ? '1':'.');
    }

    // uses internals of m4ri & is fragile
    if (n == 32) { printf("  %08x", ((uint32_t*)(M->data))[r<<2]); }
    
    putchar('\n');
  }
#else
  mzd_print(M);
#endif  
}

// multiply wrapper
inline mzd_t* mat_mul(mzd_t* r, mzd_t* a, mzd_t* b) { return mzd_mul(r,a,b,0); }

uint32_t mat_inv_k(mzd_t* I, mzd_t* M, mat_common_t* data)
{
  mzd_t* id = data->id;
  mzd_t* t  = data->m[MAT_TEMP_1];

  mzd_inv_m4ri(I,M,0);

  mat_mul(t,I,M);

  return (uint32_t)mzd_equal(t,id);
}

uint32_t mat_inv_64(mzd_t* I, mzd_t* M)  { return mat_inv_k(I,M, &mat_64_common); }

// allocates and frees every time: meh..don't care here
void f2_bijection_test_64(ufunc_64_t* f)
{
  uint64_t m[64] = {0};
  uint64_t t = mat_dense_from_func_64(m,f);

  if (t == 0) {
    mzd_t* F = mzd_init(64,64);
    mzd_t* R = mzd_init(64,64);

    mat_from_dense_64(F,m);

    if (mat_inv_64(R,F)) {
      printf("good\n");
#if defined(PRINT_MATRIX)    
      mat_print(F); printf("\n");
      mat_print(R); printf("\n");
#endif    
    }
    else printf("no inverse\n");

    mzd_free(F);
    mzd_free(R);
  }
  else printf("no affine support here\n");
}


int main()
{
  mat_init();

  for(uint32_t i=1; i<64; i++) {
    shift = i;
    printf("crc64(x) ^ (x ^ rot(x,%2d)) : ",i);
    f2_bijection_test_64(&c_mix);
  }

  // all greater than 32 are non-invertiable
  for(uint32_t i=1; i<32; i++) {
    shift = i;
    printf("crc64(x) ^ (x ^ (x>>%2d)) : ",i);
    f2_bijection_test_64(&ls_mix);
  }

  for(uint32_t i=1; i<64; i++) {
    shift = i;
    printf("crc64(x) ^ (x ^ (x<<%2d)) : ",i);
    f2_bijection_test_64(&rs_mix);
  }

  return 0;
}