// This program is to check some of the assertions in section 5.5 of
// this paper: http://www.win.tue.nl/~aeb/preprints/udim24a.pdf
// gcc Gd.c -std=c99
#include <stdio.h>
#include <assert.h>
// #define __USE_BSD
#include <stdlib.h>
typedef signed char co;
static int B[12] = { // Brouwer Sec 5.5
  0x0000FF, 0x000F0F, 0x003333, 0x005555,
  0x009669, 0x030356, 0x050563, 0x09063A,
  0x111178, 0x21121D, 0x41144E, 0x811724};
static int G[4096];
co ge[25][24]; // 25 generators of LL

// Radix Exchange Sort of unsigned integer array.
typedef int ui;
void rdx(ui* b, ui* e, ui bit){ // Radix Exchange Sort
  if(b<e && bit) {ui*B = b; ui*E = e;
    while(1) {
      while(!(*B & bit)) if(B<E) ++B; else {++E; goto f;}
      while(*E & bit)    if(B<E) --E; else {--B; goto f;}
      {ui t = *E; *(E--) = *B; *(B++) = t;}
      if(E<=B) {if(E==B) {if(*E & bit) --B; else ++E;}
         else {--B; ++E;} break;}}
f:  rdx(b, B, bit>>1); rdx(E, e, bit>>1);}}

static int weight(int x) {int c=0; while(x){++c; x &= x-1;} return c;}
static int ew(co * x, int s){int w=0; for(int j=0; j<24; ++j) w=(w<<1)|(x[j]>>s)&1; return w;}

int in(int y){int q=0, z=2048;
  while (z) {if(y>=G[q+z]) q += z; z >>= 1;}
  return y==G[q];}
static int Lq(co * x){return
  in(ew(x, 1)) && ew(x, 0) == (weight(ew(x, 2))&1?0xffffff:0);}

int main(){
char zz[] = {22, 22, 21, 20, 19, 18, 17, 15, 14, 13, 11, 7};
for(int i=0; i<12; ++i) for(int j=0; j<24; ++j)
  {ge[i][j]=0; ge[i+12][j] = 2*((B[i]>>(23-j))&1);}
ge[0][23] = 4;
for(int j=1; j<12; ++j) ge[j][23] = -4;
for(int j=0; j<12; ++j) ge[j][zz[j]] = 4;
ge[24][23] = -3; for(int j=0; j<23; ++j) ge[24][j] = 1;
// Now putative gtenerators have been created.
if(0) for(int i=0; i<25; ++i) {
  for(int j=0; j<24; ++j) printf("%3d", ge[i][j]); printf("\n");}
for(int j=0; j<4096; ++j) {int y=0;
  for(int k=0; k<12; ++k) if((j>>k)&1) y ^= B[k]; G[j] = y;}
rdx(G, G+4095, 1<<23);
assert(in(B[3]^B[7])); for(int j=0; j<12; ++j) assert(in(B[j]));
for(int j=0; j<25; ++j) assert(Lq(ge[j]));
{int y = 10000; while(y--)
  {co w[24]; for(int j=0; j<24; ++j) w[j]=0;
    {int r = 20; while(r--) {int c=random()%25;
      for(int k=0; k<24; ++k) w[k] += ge[c][k];}}
   if(0) if(!(random()&15)) {for(int u=0; u<24; ++u) printf("%02x ", 255&w[u]);
        printf("\n");}
   assert(Lq(w));}}
// Make Scheme value.
if(1) {printf("("); for(int i=0; i<25; ++i) {printf("(");
    for(int j=0; j<24; ++j) printf("%d ", ge[i][j]);
    printf(")\n");} printf(")\n");}
return 0;}