Debian Codegraph @

crypto_kem/6688128f/vec/gf.c

raw
1 /*
2 this file is for functions for field arithmetic
3 */
4 // 20240810 djb: even more cryptoint usage
5 // 20240809 djb: restructuring
6 // 20240805 djb: more cryptoint usage
7 // 20221231 djb: const for GF_mul
8 // 20221230 djb: add linker line
9
10 // linker define gf_iszero gf_inv
11 // linker use gf_mul
12
13 #include "gf.h"
14
15 #include "crypto_int32.h"
16 #include "crypto_int64.h"
17
18 /* check if a == 0 */
19 gf gf_iszero(gf a)
20 {
21 return crypto_int32_zero_mask(a) & GFMASK;
22 }
23
24 /* input: field element in */
25 /* return: in^2 */
26 static gf gf_sq(gf in)
27 {
28 const uint32_t B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF};
29
30 uint32_t x = in;
31 uint32_t t;
32
33 x = (x | crypto_int32_shlmod(x,8)) & B[3];
34 x = (x | crypto_int32_shlmod(x,4)) & B[2];
35 x = (x | crypto_int32_shlmod(x,2)) & B[1];
36 x = (x | crypto_int32_shlmod(x,1)) & B[0];
37
38 t = x & 0xFF80000;
39 x ^= (t >> 9) ^ (t >> 10) ^ (t >> 12) ^ (t >> 13);
40
41 t = x & 0x007E000;
42 x ^= (t >> 9) ^ (t >> 10) ^ (t >> 12) ^ (t >> 13);
43
44 return x & GFMASK;
45 }
46
47 /* 2 field squarings */
48 static gf gf_sq2(gf in)
49 {
50 int i;
51
52 const uint64_t B[] = {0x1111111111111111,
53 0x0303030303030303,
54 0x000F000F000F000F,
55 0x000000FF000000FF};
56
57 const uint64_t M[] = {0x0001FF0000000000,
58 0x000000FF80000000,
59 0x000000007FC00000,
60 0x00000000003FE000};
61
62 uint64_t x = in;
63 uint64_t t;
64
65 x = (x | crypto_int64_shlmod(x,24)) & B[3];
66 x = (x | crypto_int64_shlmod(x,12)) & B[2];
67 x = (x | crypto_int64_shlmod(x,6)) & B[1];
68 x = (x | crypto_int64_shlmod(x,3)) & B[0];
69
70 for (i = 0; i < 4; i++)
71 {
72 t = x & M[i];
73 x ^= (t >> 9) ^ (t >> 10) ^ (t >> 12) ^ (t >> 13);
74 }
75
76 return x & GFMASK;
77 }
78
79 /* square and multiply */
80 static gf gf_sqmul(gf in, gf m)
81 {
82 return gf_mul(gf_sq(in), m);
83 }
84
85 /* square twice and multiply */
86 static gf gf_sq2mul(gf in, gf m)
87 {
88 return gf_mul(gf_sq2(in), m);
89 }
90
91 /* return 1/den */
92 gf gf_inv(gf den)
93 {
94 gf tmp_11;
95 gf tmp_1111;
96 gf out;
97
98 tmp_11 = gf_sqmul(den, den); // ^11
99 tmp_1111 = gf_sq2mul(tmp_11, tmp_11); // ^1111
100 out = gf_sq2(tmp_1111);
101 out = gf_sq2mul(out, tmp_1111); // ^11111111
102 out = gf_sq2(out);
103 out = gf_sq2mul(out, tmp_1111); // ^111111111111
104
105 return gf_sq(out); // ^1111111111110 = ^-1
106 }
107