blob: fbf7daa2e2ba984ad211acf90b46cd9618c611b1 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include <cassert>
#include "gf28.h"
using namespace std;
namespace GF28 {
const int modulus=0x11b;
uint8_t reduce(int v,int m){
assert(v&&m);
while(true){
int sh=__builtin_clz(m)-__builtin_clz(v);
if(sh<0)break;
v^=m<<sh;
if(v==0)break;
}
return (uint8_t)(unsigned int)v;
}
uint8_t multiply(uint8_t x,uint8_t y){
if(x==0||y==0)return 0;
int res=0;
int addend=x;
while(y){
if(y&1)res^=addend;
addend<<=1;
if(addend&0x100)addend^=modulus;
y>>=1;
}
return res;
}
uint8_t inverse(uint8_t value){
if(value==0)return value;
int x=1,y=0,x2=0,y2=1,r=modulus,r2=value;
while(r2!=0){
assert(r!=0);
int ex=__builtin_clz(r2)-__builtin_clz(r);
if(ex<0){
swap(x,x2);
swap(y,y2);
swap(r,r2);
} else {
int xn=x^(x2<<ex); x=x2; x2=xn;
int yn=y^(y2<<ex); y=y2; y2=yn;
int rn=r^(r2<<ex); r=r2; r2=rn;
}
}
assert(r==1);
return reduce(y,modulus);
}
}
|
