#include #include #define BITS 8 #define POLY 0x1d typedef unsigned int gfa_t; #define XCHG(x, y) ({ typeof((x)) tmp = (x); (x) = (y); (y) = tmp; }) static inline gfa_t add(gfa_t x, gfa_t y) { return x ^ y; } #define sub(x, y) add((x), (y)) static inline gfa_t mult2(gfa_t x) { return ((x << 1) & ((1 << BITS)-1))^((x & (1 << (BITS-1))) ? POLY : 0); } static gfa_t __mult(gfa_t x, gfa_t y) { gfa_t r = 0; while(y > 0) { if (y & 1) r ^= x; x = mult2(x); y >>= 1; } return r; } static inline gfa_t mult(gfa_t x, gfa_t y) { if (x < y) XCHG(x, y); return __mult(x, y); } static gfa_t expon(gfa_t x, int n) { gfa_t r = 1; while(n < 0) n += (1 << BITS)-1; n %= (1 << BITS)-1; while(n > 0) { if (n & 1) r = mult(r, x); x = __mult(x, x); n >>= 1; } return r; } #define div(x, y) mult((x), expon((y), -1)) /* * add(x, y); * sub(x, y); * mult(x, y); * div(x, y); * expon(x, k); */ static void check_commutativity(void) { gfa_t i, j; printf("checking multiplicative commutativity... "); for(i = 0; i < (1 << BITS); i++) for(j = 0; j < i; j++) if (__mult(i, j) != __mult(j, i)) abort(); printf("ok\n"); } static void check_generator(gfa_t g) { unsigned char bm[((1 << BITS)+7) >> 3] = { 0, }; gfa_t i, x; printf("checking for validity of generator %02x... ", g); x = 1; i = 1; do { unsigned char mask = 1 << (x & 7); int pos = x >> 3; if (!(bm[pos] ^= mask)) break; x = __mult(x, g); i++; } while(x != 1); if (i != (1 << BITS)) abort(); printf("ok\n"); } static void check_multiplication(void) { unsigned char bm[((1 << BITS)+7) >> 3]; gfa_t i, j; printf("checking for mutiplication validity... "); for(i = 1; i < (1 << BITS); i++) { memset(bm, 0, sizeof bm); for(j = 0; j < (1 << BITS); j++) { gfa_t x = mult(i, j); unsigned char mask = 1 << (x & 7); int pos = x >> 3; if (!(bm[pos] ^= mask)) break; } } printf("ok\n"); } static void check_inversion(void) { gfa_t i; printf("checking for inversion validity... "); for(i = 1; i < (1 << BITS); i++) if (mult(i, expon(i, -1)) != 1) abort(); printf("ok\n"); } int main(int argc, char **argv) { gfa_t i, j, x; check_commutativity(); check_generator(2); check_multiplication(); check_inversion(); printf("\n"); /* addition */ printf("+ |"); for(j = 0; j < 16; j++) printf(" %02x", j); printf("\n"); printf("---+"); for(j = 0; j < 16; j++) printf("---"); printf("\n"); for(i = 0; i < 16; i++) { printf("%02x |", i); for(j = 0; j < 16; j++) { printf(" %02x", add(i, j)); } printf("\n"); } printf("\n"); /* multiplication */ printf("* |"); for(j = 0; j < 16; j++) printf(" %02x", j); printf("\n"); printf("---+"); for(j = 0; j < 16; j++) printf("---"); printf("\n"); for(i = 0; i < 16; i++) { printf("%02x |", i); for(j = 0; j < 16; j++) { printf(" %02x", mult(i, j)); } printf("\n"); } printf("\n"); /* exponentiation */ printf("2^ |"); for(j = 0; j < 16; j++) printf(" _%x", j); printf("\n"); printf("---+"); for(j = 0; j < 16; j++) printf("---"); printf("\n"); x = 1; for(i = 0; i < 16; i++) { printf("%x_ |", i); for(j = 0; j < 16; j++) { printf(" %02x", x); x = mult2(x); } printf("\n"); } printf("\n"); /* inverse numbers */ printf("1/ |"); for(j = 0; j < 16; j++) printf(" _%x", j); printf("\n"); printf("---+"); for(j = 0; j < 16; j++) printf("---"); printf("\n"); for(i = 0; i < 16; i++) { printf("%x_ |", i); for(j = 0; j < 16; j++) printf(" %02x", expon(i*16 + j, -1)); printf("\n"); } printf("\n"); return 0; }