package rs;

import java.util.HashSet;
import java.util.Set;

public class InverseTable {

    public static void main(String[] args) {
        // x^8 + x^4 + x^3 + x + 1
        int poly = 0b100011011;

        Set<Integer> invs = new HashSet<>();

        for (int high = 0; high <= 0xF; high++) {
            System.out.printf("%x \t", high);

            for (int low = 0; low <= 0xF; low++) {
                int elem = (high << 4) | low;

                if (elem == 0) {
                    System.out.print("- \t");
                } else {
                    final int inv = inv(elem, poly);
                    System.out.printf("%02x \t", inv);

                    invs.add(inv);
                }
            }

            System.out.println();
        }

        System.out.println(invs.size());
    }

    private static int inv(int a, int p) {
        for (int b = 1; b <= 0xFF; b++) {
            int prod = mult(a, b);
            int r = div(prod, p)[1];

            if (r == 1) {
                return b;
            }
        }

        throw new IllegalArgumentException("Can't find inverse for " + Integer.toBinaryString(a));
    }

    private static int mult(int p1, int p2) {
        int result = 0;

        for (int i = 31; i >= 0; i--) {
            if (((p2 >>> i) & 1) != 0) {
                result ^= (p1 << i);
            }
        }

        return result;
    }

    private static int[] div(int dividend, int divisor) {
        int divDeg = deg(divisor);

        int q = 0;
        int r = dividend;

        while (deg(r) >= divDeg) {
            int degDif = deg(r) - divDeg;

            r ^= (divisor << degDif);
            q ^= (1 << degDif);
        }

        return new int[]{q, r};
    }

    private static int deg(int pol) {
        return 32 - Integer.numberOfLeadingZeros(pol) - 1;
    }

}