1 /** @brief Generic arithmetic which has to be compiled per field. */
2
3 #include "field.h"
4
5 static const gf MODULUS = {FIELD_LITERAL(
6 $(ser(modulus,gf_lit_limb_bits))
7 )};
8
9 #if P_MOD_8 == 5
10 const gf SQRT_MINUS_ONE = {FIELD_LITERAL(
11 $(ser(msqrt(-1,modulus),gf_lit_limb_bits) if modulus % 4 == 1 else "/* NOPE */")
12 )};
13 #endif
14
15 /** Serialize to wire format. */
gf_serialize(uint8_t serial[SER_BYTES],const gf x,int with_hibit)16 void gf_serialize (uint8_t serial[SER_BYTES], const gf x, int with_hibit) {
17 gf red;
18 gf_copy(red, x);
19 gf_strong_reduce(red);
20 if (!with_hibit) { assert(gf_hibit(red) == 0); }
21
22 unsigned int j=0, fill=0;
23 dword_t buffer = 0;
24 UNROLL for (unsigned int i=0; i<(with_hibit ? X_SER_BYTES : SER_BYTES); i++) {
25 if (fill < 8 && j < NLIMBS) {
26 buffer |= ((dword_t)red->limb[LIMBPERM(j)]) << fill;
27 fill += LIMB_PLACE_VALUE(LIMBPERM(j));
28 j++;
29 }
30 serial[i] = buffer;
31 fill -= 8;
32 buffer >>= 8;
33 }
34 }
35
36 /** Return high bit of x = low bit of 2x mod p */
gf_hibit(const gf x)37 mask_t gf_hibit(const gf x) {
38 gf y;
39 gf_add(y,x,x);
40 gf_strong_reduce(y);
41 return -(y->limb[0]&1);
42 }
43
44 /** Return high bit of x = low bit of 2x mod p */
gf_lobit(const gf x)45 mask_t gf_lobit(const gf x) {
46 gf y;
47 gf_copy(y,x);
48 gf_strong_reduce(y);
49 return -(y->limb[0]&1);
50 }
51
52 /** Deserialize from wire format; return -1 on success and 0 on failure. */
gf_deserialize(gf x,const uint8_t serial[SER_BYTES],int with_hibit,uint8_t hi_nmask)53 mask_t gf_deserialize (gf x, const uint8_t serial[SER_BYTES], int with_hibit, uint8_t hi_nmask) {
54 unsigned int j=0, fill=0;
55 dword_t buffer = 0;
56 dsword_t scarry = 0;
57 const unsigned nbytes = with_hibit ? X_SER_BYTES : SER_BYTES;
58 UNROLL for (unsigned int i=0; i<NLIMBS; i++) {
59 UNROLL while (fill < LIMB_PLACE_VALUE(LIMBPERM(i)) && j < nbytes) {
60 uint8_t sj = serial[j];
61 if (j==nbytes-1) sj &= ~hi_nmask;
62 buffer |= ((dword_t)sj) << fill;
63 fill += 8;
64 j++;
65 }
66 x->limb[LIMBPERM(i)] = (i<NLIMBS-1) ? buffer & LIMB_MASK(LIMBPERM(i)) : buffer;
67 fill -= LIMB_PLACE_VALUE(LIMBPERM(i));
68 buffer >>= LIMB_PLACE_VALUE(LIMBPERM(i));
69 scarry = (scarry + x->limb[LIMBPERM(i)] - MODULUS->limb[LIMBPERM(i)]) >> (8*sizeof(word_t));
70 }
71 mask_t succ = with_hibit ? -(mask_t)1 : ~gf_hibit(x);
72 return succ & word_is_zero(buffer) & ~word_is_zero(scarry);
73 }
74
75 /** Reduce to canonical form. */
gf_strong_reduce(gf a)76 void gf_strong_reduce (gf a) {
77 /* first, clear high */
78 gf_weak_reduce(a); /* Determined to have negligible perf impact. */
79
80 /* now the total is less than 2p */
81
82 /* compute total_value - p. No need to reduce mod p. */
83 dsword_t scarry = 0;
84 for (unsigned int i=0; i<NLIMBS; i++) {
85 scarry = scarry + a->limb[LIMBPERM(i)] - MODULUS->limb[LIMBPERM(i)];
86 a->limb[LIMBPERM(i)] = scarry & LIMB_MASK(LIMBPERM(i));
87 scarry >>= LIMB_PLACE_VALUE(LIMBPERM(i));
88 }
89
90 /* uncommon case: it was >= p, so now scarry = 0 and this = x
91 * common case: it was < p, so now scarry = -1 and this = x - p + 2^255
92 * so let's add back in p. will carry back off the top for 2^255.
93 */
94 assert(word_is_zero(scarry) | word_is_zero(scarry+1));
95
96 word_t scarry_0 = scarry;
97 dword_t carry = 0;
98
99 /* add it back */
100 for (unsigned int i=0; i<NLIMBS; i++) {
101 carry = carry + a->limb[LIMBPERM(i)] + (scarry_0 & MODULUS->limb[LIMBPERM(i)]);
102 a->limb[LIMBPERM(i)] = carry & LIMB_MASK(LIMBPERM(i));
103 carry >>= LIMB_PLACE_VALUE(LIMBPERM(i));
104 }
105
106 assert(word_is_zero(carry + scarry_0));
107 }
108
109 /** Subtract two gf elements d=a-b */
gf_sub(gf d,const gf a,const gf b)110 void gf_sub (gf d, const gf a, const gf b) {
111 gf_sub_RAW ( d, a, b );
112 gf_bias( d, 2 );
113 gf_weak_reduce ( d );
114 }
115
116 /** Add two field elements d = a+b */
gf_add(gf d,const gf a,const gf b)117 void gf_add (gf d, const gf a, const gf b) {
118 gf_add_RAW ( d, a, b );
119 gf_weak_reduce ( d );
120 }
121
122 /** Compare a==b */
gf_eq(const gf a,const gf b)123 mask_t gf_eq(const gf a, const gf b) {
124 gf c;
125 gf_sub(c,a,b);
126 gf_strong_reduce(c);
127 mask_t ret=0;
128 for (unsigned int i=0; i<NLIMBS; i++) {
129 ret |= c->limb[LIMBPERM(i)];
130 }
131
132 return word_is_zero(ret);
133 }
134