fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <stdint.h>
  3.  
  4. uint8_t  gmul(uint8_t  a, uint8_t  b)
  5. {
  6.     uint8_t p=0;
  7.     uint8_t carry;
  8.     int i;
  9.     for(i=0;i<8;i++)
  10.     {
  11.         if(b & 1)
  12.             p ^=a;
  13.         carry = a & 0x80;
  14.         a = a<<1;
  15.         if(carry)
  16.             a^=0x1b;
  17.         b = b>>1;
  18.     }
  19.     return p;
  20. }
  21.  
  22. uint8_t log_table[256], antilog[255];
  23. const uint8_t g = 3;
  24.  
  25. void init_log_table(void)
  26. {
  27.     log_table[0] = 0;  /* dummy value */
  28.     for (int i = 0, x = 1; i < 255; x = gmul(x, g), i++) {
  29.         log_table[x] = i;
  30.         antilog[i] = x;
  31.     }
  32. }
  33.  
  34. uint8_t gmul_table(uint8_t a, uint8_t b)
  35. {
  36.     if (a == 0 || b == 0) return 0;
  37.  
  38.     uint8_t x = log_table[a];
  39.     uint8_t y = log_table[b];
  40.     uint8_t log_mult = (x + y) % 255;
  41.  
  42.     return antilog[log_mult];
  43. }
  44.  
  45. uint8_t ginv_table(uint8_t a)
  46. {
  47.     if (a == 0) return 0;   /* Error */
  48.  
  49.     uint8_t x = log_table[a];
  50.     uint8_t log_inv = (255 - x) % 255;
  51.  
  52.     return antilog[log_inv];
  53. }
  54.  
  55. /* GCC __builtin_clz() counts the number of leading zeros in an unsigned int. */
  56. /* The constant 32 doesn't actually matter for us, since we only use this to  */
  57. /* calculate the difference between two bit lengths. */
  58. #define bitlength(x) (32 - __builtin_clz(x))
  59.  
  60. uint8_t ginv(uint8_t x)
  61. {
  62.     uint16_t u1 = 0, u3 = 0x11b, v1 = 1, v3 = x;
  63.  
  64.     while (v3 != 0) {
  65.         uint16_t t1 = u1, t3 = u3;
  66.         int8_t q = bitlength(u3) - bitlength(v3);
  67.  
  68.         if (q >= 0) {
  69.             t1 ^= v1 << q;
  70.             t3 ^= v3 << q;
  71.         }
  72.         u1 = v1; u3 = v3;
  73.         v1 = t1; v3 = t3;
  74.     }
  75.  
  76.     if (u1 >= 0x100) u1 ^= 0x11b;
  77.  
  78.     return u1;
  79. }
  80.  
  81. int main(void) {
  82. 	init_log_table();
  83.  
  84. 	/* test multiplication */
  85. 	for (int i = 0; i < 256; i++) {
  86. 		for (int j = 0; j < 256; j++) {
  87. 			uint8_t a = gmul(i, j), b = gmul_table(i, j);
  88. 			if (a != b) {
  89. 				printf("Fail: gmul(%d, %d) = %d != %d = gmul_table(%d, %d)!\n", i, j, a, b, i, j);
  90. 				return 1;
  91. 			}
  92. 		}
  93. 	}
  94. 	puts("Multiplication test passed OK!"); 
  95.  
  96. 	/* test inverse */
  97. 	for (int i = 1; i < 256; i++) {
  98. 		uint8_t a = ginv(i), b = ginv_table(i);
  99. 		if (a != b) {
  100. 			printf("Fail: ginv(%d) = %d != %d = ginv_table(%d)!\n", i, a, b, i);
  101. 			return 1;
  102. 		}
  103. 		uint8_t j = gmul_table(i, a);
  104. 		if (j != 1) {
  105. 			printf("Fail: ginv(%d) = %d, %d * %d = %d != 1!\n", i, a, i, a, j);
  106. 			return 1;
  107. 		}
  108. 	}	
  109. 	puts("Inverse test passed OK!");
  110.  
  111. 	return 0;
  112. }
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/J4gCaw
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!