#include <stdio.h>
#include <stdint.h>
#define numbits(x) __builtin_popcount(x)
uint8_t gmul(uint8_t a, uint8_t b)
{
uint8_t p=0;
uint8_t carry;
int i;
for(i=0;i<8;i++)
{
if(b & 1)
p ^=a;
carry = a & 0x80;
a = a<<1;
if(carry)
a^=0x1b;
b = b>>1;
}
return p;
}
uint8_t log_table[256], antilog[255];
const uint8_t g = 3;
void init_log_table(void)
{
log_table[0] = 0; /* dummy value */
for (int i = 0, x = 1; i < 255; x = gmul(x, g), i++) {
log_table[x] = i;
antilog[i] = x;
}
}
uint8_t gmul_table(uint8_t a, uint8_t b)
{
if (a == 0 || b == 0) return 0;
uint8_t x = log_table[a];
uint8_t y = log_table[b];
uint8_t log_mult = (x + y) % 255;
return antilog[log_mult];
}
uint8_t ginv_table(uint8_t a)
{
if (a == 0) return 0; /* Error */
uint8_t x = log_table[a];
uint8_t log_inv = (255 - x) % 255;
return antilog[log_inv];
}
uint8_t ginv(uint8_t x)
{
uint16_t u1, u3, v1, v3;
u1 = 0; u3 = 0x11b;
v1 = 1; v3 = x;
for (;;) {
uint16_t t1, t3, x, y;
if (v3 == 0) break;
x = u3; x |= x>>1; x |= x>>2; x |= x>>4;
y = v3; y |= y>>1; y |= y>>2; y |= y>>4;
if (x >= y) {
uint16_t z = x & ~y;
uint8_t q = numbits(z);
t1 = u1 ^ (v1<<q);
t3 = u3 ^ (v3<<q);
} else {
t1 = u1;
t3 = u3;
}
u1 = v1; u3 = v3;
v1 = t1; v3 = t3;
}
if (u1 >= 0x100) u1 ^= 0x11b;
return u1;
}
int main(void) {
init_log_table();
/* test multiplication */
for (int i = 0; i < 256; i++) {
for (int j = 0; j < 256; j++) {
uint8_t a = gmul(i, j), b = gmul_table(i, j);
if (a != b) {
printf("Fail: gmul(%d, %d) = %d != %d = gmul_table(%d, %d)!\n", i
, j
, a
, b
, i
, j
); return 1;
}
}
}
puts("Multiplication test passed OK!");
/* test inverse */
for (int i = 1; i < 256; i++) {
uint8_t a = ginv(i), b = ginv_table(i);
if (a != b) {
printf("Fail: ginv(%d) = %d != %d = ginv_table(%d)!\n", i
, a
, b
, i
); return 1;
}
uint8_t j = gmul_table(i, a);
if (j != 1) {
printf("Fail: ginv(%d) = %d, %d * %d = %d != 1!\n", i
, a
, i
, a
, j
); return 1;
}
}
puts("Inverse test passed OK!");
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRpbnQuaD4KI2RlZmluZSBudW1iaXRzKHgpIF9fYnVpbHRpbl9wb3Bjb3VudCh4KQoKdWludDhfdCAgZ211bCh1aW50OF90ICBhLCB1aW50OF90ICBiKQp7CiAgICB1aW50OF90IHA9MDsKICAgIHVpbnQ4X3QgY2Fycnk7CiAgICBpbnQgaTsKICAgIGZvcihpPTA7aTw4O2krKykKICAgIHsKICAgICAgICBpZihiICYgMSkKICAgICAgICAgICAgcCBePWE7CiAgICAgICAgY2FycnkgPSBhICYgMHg4MDsKICAgICAgICBhID0gYTw8MTsKICAgICAgICBpZihjYXJyeSkKICAgICAgICAgICAgYV49MHgxYjsKICAgICAgICBiID0gYj4+MTsKICAgIH0KICAgIHJldHVybiBwOwp9Cgp1aW50OF90IGxvZ190YWJsZVsyNTZdLCBhbnRpbG9nWzI1NV07CmNvbnN0IHVpbnQ4X3QgZyA9IDM7Cgp2b2lkIGluaXRfbG9nX3RhYmxlKHZvaWQpCnsKICAgIGxvZ190YWJsZVswXSA9IDA7ICAvKiBkdW1teSB2YWx1ZSAqLwogICAgZm9yIChpbnQgaSA9IDAsIHggPSAxOyBpIDwgMjU1OyB4ID0gZ211bCh4LCBnKSwgaSsrKSB7CiAgICAgICAgbG9nX3RhYmxlW3hdID0gaTsKICAgICAgICBhbnRpbG9nW2ldID0geDsKICAgIH0KfQoKdWludDhfdCBnbXVsX3RhYmxlKHVpbnQ4X3QgYSwgdWludDhfdCBiKQp7CiAgICBpZiAoYSA9PSAwIHx8IGIgPT0gMCkgcmV0dXJuIDA7CgogICAgdWludDhfdCB4ID0gbG9nX3RhYmxlW2FdOwogICAgdWludDhfdCB5ID0gbG9nX3RhYmxlW2JdOwogICAgdWludDhfdCBsb2dfbXVsdCA9ICh4ICsgeSkgJSAyNTU7CgogICAgcmV0dXJuIGFudGlsb2dbbG9nX211bHRdOwp9Cgp1aW50OF90IGdpbnZfdGFibGUodWludDhfdCBhKQp7CiAgICBpZiAoYSA9PSAwKSByZXR1cm4gMDsgICAvKiBFcnJvciAqLwoKICAgIHVpbnQ4X3QgeCA9IGxvZ190YWJsZVthXTsKICAgIHVpbnQ4X3QgbG9nX2ludiA9ICgyNTUgLSB4KSAlIDI1NTsKCiAgICByZXR1cm4gYW50aWxvZ1tsb2dfaW52XTsKfQoKdWludDhfdCBnaW52KHVpbnQ4X3QgeCkKewogICAgdWludDE2X3QgdTEsIHUzLCB2MSwgdjM7CgogICAgdTEgPSAwOyB1MyA9IDB4MTFiOwogICAgdjEgPSAxOyB2MyA9IHg7CgogICAgZm9yICg7OykgewogICAgICAgIHVpbnQxNl90IHQxLCB0MywgeCwgeTsKCiAgICAgICAgaWYgKHYzID09IDApIGJyZWFrOwoKICAgICAgICB4ID0gdTM7IHggfD0geD4+MTsgeCB8PSB4Pj4yOyB4IHw9IHg+PjQ7CiAgICAgICAgeSA9IHYzOyB5IHw9IHk+PjE7IHkgfD0geT4+MjsgeSB8PSB5Pj40OwogICAgICAgIGlmICh4ID49IHkpIHsKICAgICAgICAgICAgdWludDE2X3QgeiA9IHggJiB+eTsKICAgICAgICAgICAgdWludDhfdCBxID0gbnVtYml0cyh6KTsKICAgICAgICAgICAgdDEgPSB1MSBeICh2MTw8cSk7CiAgICAgICAgICAgIHQzID0gdTMgXiAodjM8PHEpOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIHQxID0gdTE7CiAgICAgICAgICAgIHQzID0gdTM7CiAgICAgICAgfQogICAgICAgIHUxID0gdjE7IHUzID0gdjM7CiAgICAgICAgdjEgPSB0MTsgdjMgPSB0MzsKICAgIH0KCiAgICBpZiAodTEgPj0gMHgxMDApIHUxIF49IDB4MTFiOwoKICAgIHJldHVybiB1MTsKfQoKaW50IG1haW4odm9pZCkgewoJaW5pdF9sb2dfdGFibGUoKTsKCQoJLyogdGVzdCBtdWx0aXBsaWNhdGlvbiAqLwoJZm9yIChpbnQgaSA9IDA7IGkgPCAyNTY7IGkrKykgewoJCWZvciAoaW50IGogPSAwOyBqIDwgMjU2OyBqKyspIHsKCQkJdWludDhfdCBhID0gZ211bChpLCBqKSwgYiA9IGdtdWxfdGFibGUoaSwgaik7CgkJCWlmIChhICE9IGIpIHsKCQkJCXByaW50ZigiRmFpbDogZ211bCglZCwgJWQpID0gJWQgIT0gJWQgPSBnbXVsX3RhYmxlKCVkLCAlZCkhXG4iLCBpLCBqLCBhLCBiLCBpLCBqKTsKCQkJCXJldHVybiAxOwoJCQl9CgkJfQoJfQoJcHV0cygiTXVsdGlwbGljYXRpb24gdGVzdCBwYXNzZWQgT0shIik7IAoJCgkvKiB0ZXN0IGludmVyc2UgKi8KCWZvciAoaW50IGkgPSAxOyBpIDwgMjU2OyBpKyspIHsKCQl1aW50OF90IGEgPSBnaW52KGkpLCBiID0gZ2ludl90YWJsZShpKTsKCQlpZiAoYSAhPSBiKSB7CgkJCXByaW50ZigiRmFpbDogZ2ludiglZCkgPSAlZCAhPSAlZCA9IGdpbnZfdGFibGUoJWQpIVxuIiwgaSwgYSwgYiwgaSk7CgkJCXJldHVybiAxOwoJCX0KCQl1aW50OF90IGogPSBnbXVsX3RhYmxlKGksIGEpOwoJCWlmIChqICE9IDEpIHsKCQkJcHJpbnRmKCJGYWlsOiBnaW52KCVkKSA9ICVkLCAlZCAqICVkID0gJWQgIT0gMSFcbiIsIGksIGEsIGksIGEsIGopOwoJCQlyZXR1cm4gMTsKCQl9Cgl9CQoJcHV0cygiSW52ZXJzZSB0ZXN0IHBhc3NlZCBPSyEiKTsKCQoJcmV0dXJuIDA7Cn0K