fork(1) download
  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
stdin
Standard input is empty
stdout
Multiplication test passed OK!
Inverse test passed OK!