// Berechnung des reflektierten Gray-Codes aus dem Vorgänger
//
// Aufruf: gray bit-anzahl
//
// Klaus Kusche, 2024

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

typedef unsigned int uint;

// berechne den Gray-Code zur Zahl z aus dem Code g der vorigen Zahl
// z muss größer 0 sein!
uint next_gray(uint z, uint g)
{
  // prüfe die Bits von z von hinten nach vorne:
  // suche das hinterste 1-Bit in z
  for (uint b = 1; ; b <<= 1) {
    // wenn das Bit b in z nicht 0 ist ...
    if ((z & b) != 0) {
      // dann invertiere mit Xor genau dieses Bit im vorigen Gray-Code
      return g ^ b;
    }
  }
}

// befülle das Array arr mit dem reflexiven Gray-Code mit bits Bits
void gray_fill(uint arr[], uint bits)
{
  arr[0] = 0;
  for (uint i = 1; i < (1U << bits); ++i) {  
    arr[i] = next_gray(i, arr[i - 1]);
  }
}

// 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);
}