1/*
2 Ignores top bit of h.
3 */
4
5void
6fe25519_frombytes(fe25519 h, const unsigned char *s)
7{
8    int64_t h0 = load_4(s);
9    int64_t h1 = load_3(s + 4) << 6;
10    int64_t h2 = load_3(s + 7) << 5;
11    int64_t h3 = load_3(s + 10) << 3;
12    int64_t h4 = load_3(s + 13) << 2;
13    int64_t h5 = load_4(s + 16);
14    int64_t h6 = load_3(s + 20) << 7;
15    int64_t h7 = load_3(s + 23) << 5;
16    int64_t h8 = load_3(s + 26) << 4;
17    int64_t h9 = (load_3(s + 29) & 8388607) << 2;
18
19    int64_t carry0;
20    int64_t carry1;
21    int64_t carry2;
22    int64_t carry3;
23    int64_t carry4;
24    int64_t carry5;
25    int64_t carry6;
26    int64_t carry7;
27    int64_t carry8;
28    int64_t carry9;
29
30    carry9 = (h9 + (int64_t)(1L << 24)) >> 25;
31    h0 += carry9 * 19;
32    h9 -= carry9 * ((uint64_t) 1L << 25);
33    carry1 = (h1 + (int64_t)(1L << 24)) >> 25;
34    h2 += carry1;
35    h1 -= carry1 * ((uint64_t) 1L << 25);
36    carry3 = (h3 + (int64_t)(1L << 24)) >> 25;
37    h4 += carry3;
38    h3 -= carry3 * ((uint64_t) 1L << 25);
39    carry5 = (h5 + (int64_t)(1L << 24)) >> 25;
40    h6 += carry5;
41    h5 -= carry5 * ((uint64_t) 1L << 25);
42    carry7 = (h7 + (int64_t)(1L << 24)) >> 25;
43    h8 += carry7;
44    h7 -= carry7 * ((uint64_t) 1L << 25);
45
46    carry0 = (h0 + (int64_t)(1L << 25)) >> 26;
47    h1 += carry0;
48    h0 -= carry0 * ((uint64_t) 1L << 26);
49    carry2 = (h2 + (int64_t)(1L << 25)) >> 26;
50    h3 += carry2;
51    h2 -= carry2 * ((uint64_t) 1L << 26);
52    carry4 = (h4 + (int64_t)(1L << 25)) >> 26;
53    h5 += carry4;
54    h4 -= carry4 * ((uint64_t) 1L << 26);
55    carry6 = (h6 + (int64_t)(1L << 25)) >> 26;
56    h7 += carry6;
57    h6 -= carry6 * ((uint64_t) 1L << 26);
58    carry8 = (h8 + (int64_t)(1L << 25)) >> 26;
59    h9 += carry8;
60    h8 -= carry8 * ((uint64_t) 1L << 26);
61
62    h[0] = (int32_t) h0;
63    h[1] = (int32_t) h1;
64    h[2] = (int32_t) h2;
65    h[3] = (int32_t) h3;
66    h[4] = (int32_t) h4;
67    h[5] = (int32_t) h5;
68    h[6] = (int32_t) h6;
69    h[7] = (int32_t) h7;
70    h[8] = (int32_t) h8;
71    h[9] = (int32_t) h9;
72}
73
74/*
75 Preconditions:
76 |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
77
78 Write p=2^255-19; q=floor(h/p).
79 Basic claim: q = floor(2^(-255)(h + 19 2^(-25)h9 + 2^(-1))).
80
81 Proof:
82 Have |h|<=p so |q|<=1 so |19^2 2^(-255) q|<1/4.
83 Also have |h-2^230 h9|<2^231 so |19 2^(-255)(h-2^230 h9)|<1/4.
84
85 Write y=2^(-1)-19^2 2^(-255)q-19 2^(-255)(h-2^230 h9).
86 Then 0<y<1.
87
88 Write r=h-pq.
89 Have 0<=r<=p-1=2^255-20.
90 Thus 0<=r+19(2^-255)r<r+19(2^-255)2^255<=2^255-1.
91
92 Write x=r+19(2^-255)r+y.
93 Then 0<x<2^255 so floor(2^(-255)x) = 0 so floor(q+2^(-255)x) = q.
94
95 Have q+2^(-255)x = 2^(-255)(h + 19 2^(-25) h9 + 2^(-1))
96 so floor(2^(-255)(h + 19 2^(-25) h9 + 2^(-1))) = q.
97*/
98
99static void
100fe25519_reduce(fe25519 h, const fe25519 f)
101{
102    int32_t h0 = f[0];
103    int32_t h1 = f[1];
104    int32_t h2 = f[2];
105    int32_t h3 = f[3];
106    int32_t h4 = f[4];
107    int32_t h5 = f[5];
108    int32_t h6 = f[6];
109    int32_t h7 = f[7];
110    int32_t h8 = f[8];
111    int32_t h9 = f[9];
112
113    int32_t q;
114    int32_t carry0, carry1, carry2, carry3, carry4, carry5, carry6, carry7, carry8, carry9;
115
116    q = (19 * h9 + ((uint32_t) 1L << 24)) >> 25;
117    q = (h0 + q) >> 26;
118    q = (h1 + q) >> 25;
119    q = (h2 + q) >> 26;
120    q = (h3 + q) >> 25;
121    q = (h4 + q) >> 26;
122    q = (h5 + q) >> 25;
123    q = (h6 + q) >> 26;
124    q = (h7 + q) >> 25;
125    q = (h8 + q) >> 26;
126    q = (h9 + q) >> 25;
127
128    /* Goal: Output h-(2^255-19)q, which is between 0 and 2^255-20. */
129    h0 += 19 * q;
130    /* Goal: Output h-2^255 q, which is between 0 and 2^255-20. */
131
132    carry0 = h0 >> 26;
133    h1 += carry0;
134    h0 -= carry0 * ((uint32_t) 1L << 26);
135    carry1 = h1 >> 25;
136    h2 += carry1;
137    h1 -= carry1 * ((uint32_t) 1L << 25);
138    carry2 = h2 >> 26;
139    h3 += carry2;
140    h2 -= carry2 * ((uint32_t) 1L << 26);
141    carry3 = h3 >> 25;
142    h4 += carry3;
143    h3 -= carry3 * ((uint32_t) 1L << 25);
144    carry4 = h4 >> 26;
145    h5 += carry4;
146    h4 -= carry4 * ((uint32_t) 1L << 26);
147    carry5 = h5 >> 25;
148    h6 += carry5;
149    h5 -= carry5 * ((uint32_t) 1L << 25);
150    carry6 = h6 >> 26;
151    h7 += carry6;
152    h6 -= carry6 * ((uint32_t) 1L << 26);
153    carry7 = h7 >> 25;
154    h8 += carry7;
155    h7 -= carry7 * ((uint32_t) 1L << 25);
156    carry8 = h8 >> 26;
157    h9 += carry8;
158    h8 -= carry8 * ((uint32_t) 1L << 26);
159    carry9 = h9 >> 25;
160    h9 -= carry9 * ((uint32_t) 1L << 25);
161
162    h[0] = h0;
163    h[1] = h1;
164    h[2] = h2;
165    h[3] = h3;
166    h[4] = h4;
167    h[5] = h5;
168    h[6] = h6;
169    h[7] = h7;
170    h[8] = h8;
171    h[9] = h9;
172}
173
174/*
175 Goal: Output h0+...+2^255 h10-2^255 q, which is between 0 and 2^255-20.
176 Have h0+...+2^230 h9 between 0 and 2^255-1;
177 evidently 2^255 h10-2^255 q = 0.
178
179 Goal: Output h0+...+2^230 h9.
180 */
181
182void
183fe25519_tobytes(unsigned char *s, const fe25519 h)
184{
185    fe25519 t;
186
187    fe25519_reduce(t, h);
188    s[0]  = t[0] >> 0;
189    s[1]  = t[0] >> 8;
190    s[2]  = t[0] >> 16;
191    s[3]  = (t[0] >> 24) | (t[1] * ((uint32_t) 1 << 2));
192    s[4]  = t[1] >> 6;
193    s[5]  = t[1] >> 14;
194    s[6]  = (t[1] >> 22) | (t[2] * ((uint32_t) 1 << 3));
195    s[7]  = t[2] >> 5;
196    s[8]  = t[2] >> 13;
197    s[9]  = (t[2] >> 21) | (t[3] * ((uint32_t) 1 << 5));
198    s[10] = t[3] >> 3;
199    s[11] = t[3] >> 11;
200    s[12] = (t[3] >> 19) | (t[4] * ((uint32_t) 1 << 6));
201    s[13] = t[4] >> 2;
202    s[14] = t[4] >> 10;
203    s[15] = t[4] >> 18;
204    s[16] = t[5] >> 0;
205    s[17] = t[5] >> 8;
206    s[18] = t[5] >> 16;
207    s[19] = (t[5] >> 24) | (t[6] * ((uint32_t) 1 << 1));
208    s[20] = t[6] >> 7;
209    s[21] = t[6] >> 15;
210    s[22] = (t[6] >> 23) | (t[7] * ((uint32_t) 1 << 3));
211    s[23] = t[7] >> 5;
212    s[24] = t[7] >> 13;
213    s[25] = (t[7] >> 21) | (t[8] * ((uint32_t) 1 << 4));
214    s[26] = t[8] >> 4;
215    s[27] = t[8] >> 12;
216    s[28] = (t[8] >> 20) | (t[9] * ((uint32_t) 1 << 6));
217    s[29] = t[9] >> 2;
218    s[30] = t[9] >> 10;
219    s[31] = t[9] >> 18;
220}
221