fork(2) download
copy 
  1. #include <stdio.h>
  2. #include <stdint.h>
  3. #define numbits(x) __builtin_popcount(x)
  4.  
  5. uint8_t  gmul(uint8_t  a, uint8_t  b)
  6. {
  7.     uint8_t p=0;
  8.     uint8_t carry;
  9.     int i;
  10.     for(i=0;i<8;i++)
  11.     {
  12.         if(b & 1)
  13.             p ^=a;
  14.         carry = a & 0x80;
  15.         a = a<<1;
  16.         if(carry)
  17.             a^=0x1b;
  18.         b = b>>1;
  19.     }
  20.     return p;
  21. }
  22.  
  23. uint8_t log_table[256], antilog[255];
  24. const uint8_t g = 3;
  25.  
  26. void init_log_table(void)
  27. {
  28.     log_table[0] = 0;  /* dummy value */
  29.     for (int i = 0, x = 1; i < 255; x = gmul(x, g), i++) {
  30.         log_table[x] = i;
  31.         antilog[i] = x;
  32.     }
  33. }
  34.  
  35. uint8_t gmul_table(uint8_t a, uint8_t b)
  36. {
  37.     if (a == 0 || b == 0) return 0;
  38.  
  39.     uint8_t x = log_table[a];
  40.     uint8_t y = log_table[b];
  41.     uint8_t log_mult = (x + y) % 255;
  42.  
  43.     return antilog[log_mult];
  44. }
  45.  
  46. uint8_t ginv_table(uint8_t a)
  47. {
  48.     if (a == 0) return 0;   /* Error */
  49.  
  50.     uint8_t x = log_table[a];
  51.     uint8_t log_inv = (255 - x) % 255;
  52.  
  53.     return antilog[log_inv];
  54. }
  55.  
  56. uint8_t ginv(uint8_t x)
  57. {
  58.     uint16_t u1, u3, v1, v3;
  59.  
  60.     u1 = 0; u3 = 0x11b;
  61.     v1 = 1; v3 = x;
  62.  
  63.     for (;;) {
  64.         uint16_t t1, t3, x, y;
  65.  
  66.         if (v3 == 0) break;
  67.  
  68.         x = u3; x |= x>>1; x |= x>>2; x |= x>>4;
  69.         y = v3; y |= y>>1; y |= y>>2; y |= y>>4;
  70.         if (x >= y) {
  71.             uint16_t z = x & ~y;
  72.             uint8_t q = numbits(z);
  73.             t1 = u1 ^ (v1<<q);
  74.             t3 = u3 ^ (v3<<q);
  75.         } else {
  76.             t1 = u1;
  77.             t3 = u3;
  78.         }
  79.         u1 = v1; u3 = v3;
  80.         v1 = t1; v3 = t3;
  81.     }
  82.  
  83.     if (u1 >= 0x100) u1 ^= 0x11b;
  84.  
  85.     return u1;
  86. }
  87.  
  88. int main(void) {
  89. 	init_log_table();
  90.  
  91. 	/* test multiplication */
  92. 	for (int i = 0; i < 256; i++) {
  93. 		for (int j = 0; j < 256; j++) {
  94. 			uint8_t a = gmul(i, j), b = gmul_table(i, j);
  95. 			if (a != b) {
  96. 				printf("Fail: gmul(%d, %d) = %d != %d = gmul_table(%d, %d)!\n", i, j, a, b, i, j);
  97. 				return 1;
  98. 			}
  99. 		}
  100. 	}
  101. 	puts("Multiplication test passed OK!"); 
  102.  
  103. 	/* test inverse */
  104. 	for (int i = 1; i < 256; i++) {
  105. 		uint8_t a = ginv(i), b = ginv_table(i);
  106. 		if (a != b) {
  107. 			printf("Fail: ginv(%d) = %d != %d = ginv_table(%d)!\n", i, a, b, i);
  108. 			return 1;
  109. 		}
  110. 		uint8_t j = gmul_table(i, a);
  111. 		if (j != 1) {
  112. 			printf("Fail: ginv(%d) = %d, %d * %d = %d != 1!\n", i, a, i, a, j);
  113. 			return 1;
  114. 		}
  115. 	}	
  116. 	puts("Inverse test passed OK!");
  117.  
  118. 	return 0;
  119. }
  120.  
Success #stdin #stdout 0s 2168KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Multiplication test passed OK!
Inverse test passed OK!
https://ideone.com/D5VBpN
language:
C (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!