// Direkte Berechnung des reflektierten Gray-Codes
//
// Aufruf: gray bit-anzahl
//
// Klaus Kusche, 2024

#include <stdio.h>
#include <stdlib.h>

typedef unsigned int uint;

// berechne den Gray-Code zur Zahl z direkt
uint uint_to_gray(uint z)
{
  // >> 1 dividiert durch 2, und ^ (xor) liefert die unterschiedlichen Bits
  return z ^ (z >> 1);
}

// befülle das Array arr mit dem reflexiven Gray-Code mit bits Bits
void gray_fill(uint arr[], uint bits)
{
  // arr hat "2 hoch bits" viele Elemente
  // und 1 << bits berechnet "2 hoch bits"
  // 1U ... Wert 1 vom Typ unsigned
  for (uint i = 0; i < (1U << bits); ++i) {  
    arr[i] = uint_to_gray(i);
  }
}

// gib z als bits-stellige Binärzahl aus,
// d.h. gib die hintesten bits Bits von z aus
void put_bits(uint z, uint bits)
{
  do {
    --bits;
    // bits ist jetzt die Anzahl,
    // um die man das nächste auszugebende Bit von z nach hinten schieben muss
    // und dann muss man noch die Bits vor dem auszugebenden Bit wegmaskieren
    putchar('0' + ((z >> bits) & 1));
  } while (bits > 0);  // Achtung: bits ist uint und kann daher nicht <0 werden!
}

// berechne die ursprüngliche Zahl z zum Gray-Code g
uint gray_to_uint(uint g)
{
  uint z = 0;
  for ( ; g > 0; g >>= 1) { // g nach jedem Durchgang halbieren, bis es 0 ist
    z ^= g; // und in z mit xor die Bits invertieren, die in g 1 sind
  }
  return z;
}

int main(int argc, const char *argv[])
{
  if (argc != 2) {
    fprintf(stderr, "Aufruf: %s bit-anzahl\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  uint bits = atoi(argv[1]);
  uint max_bits = sizeof(uint) * 8 - 1;
  // bei mehr als rund 20 wird zwar das Array schon zu groß für den Stack,
  // aber rein theoretisch funktioniert der Algorithmus bis max_bits
  // bei sizeof(uint) * 8 haben wir dann ein Überlauf-Problem
  // bei "codes" und je nach Algorithmus auch bei den Bit-Masken

  // bits ist uint, negative Eingabewerte werden daher
  // als sehr große positive Zahlen interpretiert
  if ((bits == 0) || (bits > max_bits)) {
    fprintf(stderr, "%s: %u muss zwischen 1 und %u liegen\n",
            argv[0], bits, max_bits);
    exit(EXIT_FAILURE);
  }

  // bits Codebreite ==> 2 hoch bits verschiedene Codes
  // 1 << bits berechnet 2 hoch bits
  uint codes = 1U << bits;  
  uint arr[codes];

  gray_fill(arr, bits);

  for (uint i = 0; i < codes; ++i) {
    put_bits(i, bits);
    putchar(' ');
    put_bits(arr[i], bits);
    puts((gray_to_uint(arr[i]) == i) ? " ok" : " wrong code?");
  }

  exit(EXIT_SUCCESS);
}