v

1
module edwards25519
2

3
import rand
4
import encoding.binary
5
import crypto.internal.subtle
6

7
// A Scalar is an integer modulo
8
//
9
//     l = 2^252 + 27742317777372353535851937790883648493
10
//
11
// which is the prime order of the edwards25519 group.
12
//
13
// This type works similarly to math/big.Int, and all arguments and
14
// receivers are allowed to alias.
15
//
16
// The zero value is a valid zero element.
17
struct Scalar {
18
mut:
19
	// s is the Scalar value in little-endian. The value is always reduced
20
	// between operations.
21
	s [32]u8
22
}
23

24
pub const sc_zero = Scalar{
25
	s: [u8(0), 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
26
		0, 0, 0, 0]!
27
}
28

29
pub const sc_one = Scalar{
30
	s: [u8(1), 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
31
		0, 0, 0, 0]!
32
}
33

34
pub const sc_minus_one = Scalar{
35
	s: [u8(236), 211, 245, 92, 26, 99, 18, 88, 214, 156, 247, 162, 222, 249, 222, 20, 0, 0, 0,
36
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16]!
37
}
38

39
// new_scalar return new zero scalar
40
pub fn new_scalar() Scalar {
41
	return Scalar{}
42
}
43

44
// add sets s = x + y mod l, and returns s.
45
pub fn (mut s Scalar) add(x Scalar, y Scalar) Scalar {
46
	// s = 1 * x + y mod l
47
	sc_mul_add(mut s.s, sc_one.s, x.s, y.s)
48
	return s
49
}
50

51
// multiply_add sets s = x * y + z mod l, and returns s.
52
pub fn (mut s Scalar) multiply_add(x Scalar, y Scalar, z Scalar) Scalar {
53
	sc_mul_add(mut s.s, x.s, y.s, z.s)
54
	return s
55
}
56

57
// subtract sets s = x - y mod l, and returns s.
58
pub fn (mut s Scalar) subtract(x Scalar, y Scalar) Scalar {
59
	// s = -1 * y + x mod l
60
	sc_mul_add(mut s.s, sc_minus_one.s, y.s, x.s)
61
	return s
62
}
63

64
// negate sets s = -x mod l, and returns s.
65
pub fn (mut s Scalar) negate(x Scalar) Scalar {
66
	// s = -1 * x + 0 mod l
67
	sc_mul_add(mut s.s, sc_minus_one.s, x.s, sc_zero.s)
68
	return s
69
}
70

71
// multiply sets s = x * y mod l, and returns s.
72
pub fn (mut s Scalar) multiply(x Scalar, y Scalar) Scalar {
73
	// s = x * y + 0 mod l
74
	sc_mul_add(mut s.s, x.s, y.s, sc_zero.s)
75
	return s
76
}
77

78
// set sets s = x, and returns s.
79
pub fn (mut s Scalar) set(x Scalar) Scalar {
80
	s = x
81
	return s
82
}
83

84
// set_uniform_bytes sets s to an uniformly distributed value given 64 uniformly
85
// distributed random bytes. If x is not of the right length, set_uniform_bytes
86
// returns an error, and the receiver is unchanged.
87
pub fn (mut s Scalar) set_uniform_bytes(x []u8) !Scalar {
88
	if x.len != 64 {
89
		return error('edwards25519: invalid set_uniform_bytes input length')
90
	}
91
	mut wide_bytes := []u8{len: 64}
92
	copy(mut wide_bytes, x)
93
	// for i, item in x {
94
	//	wide_bytes[i] = item
95
	//}
96
	sc_reduce(mut s.s, mut wide_bytes)
97
	return s
98
}
99

100
// set_canonical_bytes sets s = x, where x is a 32-byte little-endian encoding of
101
// s, and returns s. If x is not a canonical encoding of s, set_canonical_bytes
102
// returns an error, and the receiver is unchanged.
103
pub fn (mut s Scalar) set_canonical_bytes(x []u8) !Scalar {
104
	if x.len != 32 {
105
		return error('invalid scalar length')
106
	}
107
	// mut bb := []u8{len:32}
108
	mut ss := Scalar{}
109
	for i, item in x {
110
		ss.s[i] = item
111
	}
112

113
	//_ := copy(mut ss.s[..], x) //its not working
114
	if !is_reduced(ss) {
115
		return error('invalid scalar encoding')
116
	}
117
	s.s = ss.s
118
	return s
119
}
120

121
// is_reduced returns whether the given scalar is reduced modulo l.
122
fn is_reduced(s Scalar) bool {
123
	for i := s.s.len - 1; i >= 0; i-- {
124
		if s.s[i] > sc_minus_one.s[i] {
125
			return false
126
		}
127
		if s.s[i] < sc_minus_one.s[i] {
128
			return true
129
		}
130
		/*
131
		switch {
132
		case s.s[i] > sc_minus_one.s[i]:
133
			return false
134
		case s.s[i] < sc_minus_one.s[i]:
135
			return true
136
		}
137
		*/
138
	}
139
	return true
140
}
141

142
// set_bytes_with_clamping applies the buffer pruning described in RFC 8032,
143
// Section 5.1.5 (also known as clamping) and sets s to the result. The input
144
// must be 32 bytes, and it is not modified. If x is not of the right length,
145
// `set_bytes_with_clamping` returns an error, and the receiver is unchanged.
146
//
147
// Note that since Scalar values are always reduced modulo the prime order of
148
// the curve, the resulting value will not preserve any of the cofactor-clearing
149
// properties that clamping is meant to provide. It will however work as
150
// expected as long as it is applied to points on the prime order subgroup, like
151
// in Ed25519. In fact, it is lost to history why RFC 8032 adopted the
152
// irrelevant RFC 7748 clamping, but it is now required for compatibility.
153
pub fn (mut s Scalar) set_bytes_with_clamping(x []u8) !Scalar {
154
	// The description above omits the purpose of the high bits of the clamping
155
	// for brevity, but those are also lost to reductions, and are also
156
	// irrelevant to edwards25519 as they protect against a specific
157
	// implementation bug that was once observed in a generic Montgomery ladder.
158
	if x.len != 32 {
159
		return error('edwards25519: invalid set_bytes_with_clamping input length')
160
	}
161

162
	mut wide_bytes := []u8{len: 64, cap: 64}
163
	copy(mut wide_bytes, x)
164
	// for i, item in x {
165
	//	wide_bytes[i] = item
166
	//}
167
	wide_bytes[0] &= 248
168
	wide_bytes[31] &= 63
169
	wide_bytes[31] |= 64
170
	sc_reduce(mut s.s, mut wide_bytes)
171
	return s
172
}
173

174
// bytes returns the canonical 32-byte little-endian encoding of s.
175
pub fn (mut s Scalar) bytes() []u8 {
176
	mut buf := []u8{len: 32}
177
	copy(mut buf, s.s[..])
178
	return buf
179
}
180

181
// equal returns 1 if s and t are equal, and 0 otherwise.
182
pub fn (s Scalar) equal(t Scalar) int {
183
	return subtle.constant_time_compare(s.s[..], t.s[..])
184
}
185

186
// sc_mul_add and sc_reduce are ported from the public domain, “ref10”
187
// implementation of ed25519 from SUPERCOP.
188
fn load3(inp []u8) i64 {
189
	mut r := i64(inp[0])
190
	r |= i64(inp[1]) * 256 // << 8
191
	r |= i64(inp[2]) * 65536 // << 16
192
	return r
193
}
194

195
fn load4(inp []u8) i64 {
196
	mut r := i64(inp[0])
197
	r |= i64(inp[1]) * 256
198
	r |= i64(inp[2]) * 65536
199
	r |= i64(inp[3]) * 16777216
200
	return r
201
}
202

203
// Input:
204
//   a[0]+256*a[1]+...+256^31*a[31] = a
205
//   b[0]+256*b[1]+...+256^31*b[31] = b
206
//   c[0]+256*c[1]+...+256^31*c[31] = c
207
//
208
// Output:
209
//   s[0]+256*s[1]+...+256^31*s[31] = (ab+c) mod l
210
//   where l = 2^252 + 27742317777372353535851937790883648493.
211
fn sc_mul_add(mut s [32]u8, a [32]u8, b [32]u8, c [32]u8) {
212
	a0 := 2097151 & load3(a[..])
213
	a1 := 2097151 & (load4(a[2..]) >> 5)
214
	a2 := 2097151 & (load3(a[5..]) >> 2)
215
	a3 := 2097151 & (load4(a[7..]) >> 7)
216
	a4 := 2097151 & (load4(a[10..]) >> 4)
217
	a5 := 2097151 & (load3(a[13..]) >> 1)
218
	a6 := 2097151 & (load4(a[15..]) >> 6)
219
	a7 := 2097151 & (load3(a[18..]) >> 3)
220
	a8 := 2097151 & load3(a[21..])
221
	a9 := 2097151 & (load4(a[23..]) >> 5)
222
	a10 := 2097151 & (load3(a[26..]) >> 2)
223
	a11 := (load4(a[28..]) >> 7)
224
	b0 := 2097151 & load3(b[..])
225
	b1 := 2097151 & (load4(b[2..]) >> 5)
226
	b2 := 2097151 & (load3(b[5..]) >> 2)
227
	b3 := 2097151 & (load4(b[7..]) >> 7)
228
	b4 := 2097151 & (load4(b[10..]) >> 4)
229
	b5 := 2097151 & (load3(b[13..]) >> 1)
230
	b6 := 2097151 & (load4(b[15..]) >> 6)
231
	b7 := 2097151 & (load3(b[18..]) >> 3)
232
	b8 := 2097151 & load3(b[21..])
233
	b9 := 2097151 & (load4(b[23..]) >> 5)
234
	b10 := 2097151 & (load3(b[26..]) >> 2)
235
	b11 := (load4(b[28..]) >> 7)
236
	c0 := 2097151 & load3(c[..])
237
	c1 := 2097151 & (load4(c[2..]) >> 5)
238
	c2 := 2097151 & (load3(c[5..]) >> 2)
239
	c3 := 2097151 & (load4(c[7..]) >> 7)
240
	c4 := 2097151 & (load4(c[10..]) >> 4)
241
	c5 := 2097151 & (load3(c[13..]) >> 1)
242
	c6 := 2097151 & (load4(c[15..]) >> 6)
243
	c7 := 2097151 & (load3(c[18..]) >> 3)
244
	c8 := 2097151 & load3(c[21..])
245
	c9 := 2097151 & (load4(c[23..]) >> 5)
246
	c10 := 2097151 & (load3(c[26..]) >> 2)
247
	c11 := (load4(c[28..]) >> 7)
248

249
	mut carry := [23]i64{} // original one
250
	// mut carry := [23]u64{}
251

252
	mut s0 := c0 + a0 * b0
253
	mut s1 := c1 + a0 * b1 + a1 * b0
254
	mut s2 := c2 + a0 * b2 + a1 * b1 + a2 * b0
255
	mut s3 := c3 + a0 * b3 + a1 * b2 + a2 * b1 + a3 * b0
256
	mut s4 := c4 + a0 * b4 + a1 * b3 + a2 * b2 + a3 * b1 + a4 * b0
257
	mut s5 := c5 + a0 * b5 + a1 * b4 + a2 * b3 + a3 * b2 + a4 * b1 + a5 * b0
258
	mut s6 := c6 + a0 * b6 + a1 * b5 + a2 * b4 + a3 * b3 + a4 * b2 + a5 * b1 + a6 * b0
259
	mut s7 := c7 + a0 * b7 + a1 * b6 + a2 * b5 + a3 * b4 + a4 * b3 + a5 * b2 + a6 * b1 + a7 * b0
260
	mut s8 := c8 + a0 * b8 + a1 * b7 + a2 * b6 + a3 * b5 + a4 * b4 + a5 * b3 + a6 * b2 + a7 * b1 +
261
		a8 * b0
262
	mut s9 := c9 + a0 * b9 + a1 * b8 + a2 * b7 + a3 * b6 + a4 * b5 + a5 * b4 + a6 * b3 + a7 * b2 +
263
		a8 * b1 + a9 * b0
264
	mut s10 := c10 + a0 * b10 + a1 * b9 + a2 * b8 + a3 * b7 + a4 * b6 + a5 * b5 + a6 * b4 +
265
		a7 * b3 + a8 * b2 + a9 * b1 + a10 * b0
266
	mut s11 := c11 + a0 * b11 + a1 * b10 + a2 * b9 + a3 * b8 + a4 * b7 + a5 * b6 + a6 * b5 +
267
		a7 * b4 + a8 * b3 + a9 * b2 + a10 * b1 + a11 * b0
268
	mut s12 := a1 * b11 + a2 * b10 + a3 * b9 + a4 * b8 + a5 * b7 + a6 * b6 + a7 * b5 + a8 * b4 +
269
		a9 * b3 + a10 * b2 + a11 * b1
270
	mut s13 := a2 * b11 + a3 * b10 + a4 * b9 + a5 * b8 + a6 * b7 + a7 * b6 + a8 * b5 + a9 * b4 +
271
		a10 * b3 + a11 * b2
272
	mut s14 := a3 * b11 + a4 * b10 + a5 * b9 + a6 * b8 + a7 * b7 + a8 * b6 + a9 * b5 + a10 * b4 +
273
		a11 * b3
274
	mut s15 := a4 * b11 + a5 * b10 + a6 * b9 + a7 * b8 + a8 * b7 + a9 * b6 + a10 * b5 + a11 * b4
275
	mut s16 := a5 * b11 + a6 * b10 + a7 * b9 + a8 * b8 + a9 * b7 + a10 * b6 + a11 * b5
276
	mut s17 := a6 * b11 + a7 * b10 + a8 * b9 + a9 * b8 + a10 * b7 + a11 * b6
277
	mut s18 := a7 * b11 + a8 * b10 + a9 * b9 + a10 * b8 + a11 * b7
278
	mut s19 := a8 * b11 + a9 * b10 + a10 * b9 + a11 * b8
279
	mut s20 := a9 * b11 + a10 * b10 + a11 * b9
280
	mut s21 := a10 * b11 + a11 * b10
281
	mut s22 := a11 * b11
282

283
	mut s23 := i64(0) // original
284
	// mut s23 := u64(0)
285

286
	// carry[0] = (s0 + (1048576)) >> 21
287
	carry[0] = (s0 + (1048576)) >> 21
288
	s1 += carry[0]
289
	s0 -= carry[0] * 2097152
290
	carry[2] = (s2 + (1048576)) >> 21
291
	s3 += carry[2]
292
	s2 -= carry[2] * 2097152
293
	carry[4] = (s4 + (1048576)) >> 21
294
	s5 += carry[4]
295
	s4 -= carry[4] * 2097152
296
	carry[6] = (s6 + (1048576)) >> 21
297
	s7 += carry[6]
298
	s6 -= carry[6] * 2097152
299
	carry[8] = (s8 + (1048576)) >> 21
300
	s9 += carry[8]
301
	s8 -= carry[8] * 2097152
302
	carry[10] = (s10 + (1048576)) >> 21
303
	s11 += carry[10]
304
	s10 -= carry[10] * 2097152
305
	carry[12] = (s12 + (1048576)) >> 21
306
	s13 += carry[12]
307
	s12 -= carry[12] * 2097152
308
	carry[14] = (s14 + (1048576)) >> 21
309
	s15 += carry[14]
310
	s14 -= carry[14] * 2097152
311
	carry[16] = (s16 + (1048576)) >> 21
312
	s17 += carry[16]
313
	s16 -= carry[16] * 2097152
314
	carry[18] = (s18 + (1048576)) >> 21
315
	s19 += carry[18]
316
	s18 -= carry[18] * 2097152
317
	carry[20] = (s20 + (1048576)) >> 21
318
	s21 += carry[20]
319
	s20 -= carry[20] * 2097152
320
	carry[22] = (s22 + (1048576)) >> 21
321
	s23 += carry[22]
322
	s22 -= carry[22] * 2097152
323

324
	carry[1] = (s1 + (1048576)) >> 21
325
	s2 += carry[1]
326
	s1 -= carry[1] * 2097152
327
	carry[3] = (s3 + (1048576)) >> 21
328
	s4 += carry[3]
329
	s3 -= carry[3] * 2097152
330
	carry[5] = (s5 + (1048576)) >> 21
331
	s6 += carry[5]
332
	s5 -= carry[5] * 2097152
333
	carry[7] = (s7 + (1048576)) >> 21
334
	s8 += carry[7]
335
	s7 -= carry[7] * 2097152
336
	carry[9] = (s9 + (1048576)) >> 21
337
	s10 += carry[9]
338
	s9 -= carry[9] * 2097152
339
	carry[11] = (s11 + (1048576)) >> 21
340
	s12 += carry[11]
341
	s11 -= carry[11] * 2097152
342
	carry[13] = (s13 + (1048576)) >> 21
343
	s14 += carry[13]
344
	s13 -= carry[13] * 2097152
345
	carry[15] = (s15 + (1048576)) >> 21
346
	s16 += carry[15]
347
	s15 -= carry[15] * 2097152
348
	carry[17] = (s17 + (1048576)) >> 21
349
	s18 += carry[17]
350
	s17 -= carry[17] * 2097152
351
	carry[19] = (s19 + (1048576)) >> 21
352
	s20 += carry[19]
353
	s19 -= carry[19] * 2097152
354
	carry[21] = (s21 + (1048576)) >> 21
355
	s22 += carry[21]
356
	s21 -= carry[21] * 2097152
357

358
	s11 += s23 * 666643
359
	s12 += s23 * 470296
360
	s13 += s23 * 654183
361
	s14 -= s23 * 997805
362
	s15 += s23 * 136657
363
	s16 -= s23 * 683901
364
	s23 = 0
365

366
	s10 += s22 * 666643
367
	s11 += s22 * 470296
368
	s12 += s22 * 654183
369
	s13 -= s22 * 997805
370
	s14 += s22 * 136657
371
	s15 -= s22 * 683901
372
	s22 = 0
373

374
	s9 += s21 * 666643
375
	s10 += s21 * 470296
376
	s11 += s21 * 654183
377
	s12 -= s21 * 997805
378
	s13 += s21 * 136657
379
	s14 -= s21 * 683901
380
	s21 = 0
381

382
	s8 += s20 * 666643
383
	s9 += s20 * 470296
384
	s10 += s20 * 654183
385
	s11 -= s20 * 997805
386
	s12 += s20 * 136657
387
	s13 -= s20 * 683901
388
	s20 = 0
389

390
	s7 += s19 * 666643
391
	s8 += s19 * 470296
392
	s9 += s19 * 654183
393
	s10 -= s19 * 997805
394
	s11 += s19 * 136657
395
	s12 -= s19 * 683901
396
	s19 = 0
397

398
	s6 += s18 * 666643
399
	s7 += s18 * 470296
400
	s8 += s18 * 654183
401
	s9 -= s18 * 997805
402
	s10 += s18 * 136657
403
	s11 -= s18 * 683901
404
	s18 = 0
405

406
	carry[6] = (s6 + (1048576)) >> 21
407
	s7 += carry[6]
408
	s6 -= carry[6] * 2097152
409
	carry[8] = (s8 + (1048576)) >> 21
410
	s9 += carry[8]
411
	s8 -= carry[8] * 2097152
412
	carry[10] = (s10 + (1048576)) >> 21
413
	s11 += carry[10]
414
	s10 -= carry[10] * 2097152
415
	carry[12] = (s12 + (1048576)) >> 21
416
	s13 += carry[12]
417
	s12 -= carry[12] * 2097152
418
	carry[14] = (s14 + (1048576)) >> 21
419
	s15 += carry[14]
420
	s14 -= carry[14] * 2097152
421
	carry[16] = (s16 + (1048576)) >> 21
422
	s17 += carry[16]
423
	s16 -= carry[16] * 2097152
424

425
	carry[7] = (s7 + (1048576)) >> 21
426
	s8 += carry[7]
427
	s7 -= carry[7] * 2097152
428
	carry[9] = (s9 + (1048576)) >> 21
429
	s10 += carry[9]
430
	s9 -= carry[9] * 2097152
431
	carry[11] = (s11 + (1048576)) >> 21
432
	s12 += carry[11]
433
	s11 -= carry[11] * 2097152
434
	carry[13] = (s13 + (1048576)) >> 21
435
	s14 += carry[13]
436
	s13 -= carry[13] * 2097152
437
	carry[15] = (s15 + (1048576)) >> 21
438
	s16 += carry[15]
439
	s15 -= carry[15] * 2097152
440

441
	s5 += s17 * 666643
442
	s6 += s17 * 470296
443
	s7 += s17 * 654183
444
	s8 -= s17 * 997805
445
	s9 += s17 * 136657
446
	s10 -= s17 * 683901
447
	s17 = 0
448

449
	s4 += s16 * 666643
450
	s5 += s16 * 470296
451
	s6 += s16 * 654183
452
	s7 -= s16 * 997805
453
	s8 += s16 * 136657
454
	s9 -= s16 * 683901
455
	s16 = 0
456

457
	s3 += s15 * 666643
458
	s4 += s15 * 470296
459
	s5 += s15 * 654183
460
	s6 -= s15 * 997805
461
	s7 += s15 * 136657
462
	s8 -= s15 * 683901
463
	s15 = 0
464

465
	s2 += s14 * 666643
466
	s3 += s14 * 470296
467
	s4 += s14 * 654183
468
	s5 -= s14 * 997805
469
	s6 += s14 * 136657
470
	s7 -= s14 * 683901
471
	s14 = 0
472

473
	s1 += s13 * 666643
474
	s2 += s13 * 470296
475
	s3 += s13 * 654183
476
	s4 -= s13 * 997805
477
	s5 += s13 * 136657
478
	s6 -= s13 * 683901
479
	s13 = 0
480

481
	s0 += s12 * 666643
482
	s1 += s12 * 470296
483
	s2 += s12 * 654183
484
	s3 -= s12 * 997805
485
	s4 += s12 * 136657
486
	s5 -= s12 * 683901
487
	s12 = 0
488

489
	carry[0] = (s0 + (1048576)) >> 21
490
	s1 += carry[0]
491
	s0 -= carry[0] * 2097152
492
	carry[2] = (s2 + (1048576)) >> 21
493
	s3 += carry[2]
494
	s2 -= carry[2] * 2097152
495
	carry[4] = (s4 + (1048576)) >> 21
496
	s5 += carry[4]
497
	s4 -= carry[4] * 2097152
498
	carry[6] = (s6 + (1048576)) >> 21
499
	s7 += carry[6]
500
	s6 -= carry[6] * 2097152
501
	carry[8] = (s8 + (1048576)) >> 21
502
	s9 += carry[8]
503
	s8 -= carry[8] * 2097152
504
	carry[10] = (s10 + (1048576)) >> 21
505
	s11 += carry[10]
506
	s10 -= carry[10] * 2097152
507

508
	carry[1] = (s1 + (1048576)) >> 21
509
	s2 += carry[1]
510
	s1 -= carry[1] * 2097152
511
	carry[3] = (s3 + (1048576)) >> 21
512
	s4 += carry[3]
513
	s3 -= carry[3] * 2097152
514
	carry[5] = (s5 + (1048576)) >> 21
515
	s6 += carry[5]
516
	s5 -= carry[5] * 2097152
517
	carry[7] = (s7 + (1048576)) >> 21
518
	s8 += carry[7]
519
	s7 -= carry[7] * 2097152
520
	carry[9] = (s9 + (1048576)) >> 21
521
	s10 += carry[9]
522
	s9 -= carry[9] * 2097152
523
	carry[11] = (s11 + (1048576)) >> 21
524
	s12 += carry[11]
525
	s11 -= carry[11] * 2097152
526

527
	s0 += s12 * 666643
528
	s1 += s12 * 470296
529
	s2 += s12 * 654183
530
	s3 -= s12 * 997805
531
	s4 += s12 * 136657
532
	s5 -= s12 * 683901
533
	s12 = 0
534

535
	carry[0] = s0 >> 21
536
	s1 += carry[0]
537
	s0 -= carry[0] * 2097152
538
	carry[1] = s1 >> 21
539
	s2 += carry[1]
540
	s1 -= carry[1] * 2097152
541
	carry[2] = s2 >> 21
542
	s3 += carry[2]
543
	s2 -= carry[2] * 2097152
544
	carry[3] = s3 >> 21
545
	s4 += carry[3]
546
	s3 -= carry[3] * 2097152
547
	carry[4] = s4 >> 21
548
	s5 += carry[4]
549
	s4 -= carry[4] * 2097152
550
	carry[5] = s5 >> 21
551
	s6 += carry[5]
552
	s5 -= carry[5] * 2097152
553
	carry[6] = s6 >> 21
554
	s7 += carry[6]
555
	s6 -= carry[6] * 2097152
556
	carry[7] = s7 >> 21
557
	s8 += carry[7]
558
	s7 -= carry[7] * 2097152
559
	carry[8] = s8 >> 21
560
	s9 += carry[8]
561
	s8 -= carry[8] * 2097152
562
	carry[9] = s9 >> 21
563
	s10 += carry[9]
564
	s9 -= carry[9] * 2097152
565
	carry[10] = s10 >> 21
566
	s11 += carry[10]
567
	s10 -= carry[10] * 2097152
568
	carry[11] = s11 >> 21
569
	s12 += carry[11]
570
	s11 -= carry[11] * 2097152
571

572
	s0 += s12 * 666643
573
	s1 += s12 * 470296
574
	s2 += s12 * 654183
575
	s3 -= s12 * 997805
576
	s4 += s12 * 136657
577
	s5 -= s12 * 683901
578
	s12 = 0
579

580
	carry[0] = s0 >> 21
581
	s1 += carry[0]
582
	s0 -= carry[0] * 2097152
583
	carry[1] = s1 >> 21
584
	s2 += carry[1]
585
	s1 -= carry[1] * 2097152
586
	carry[2] = s2 >> 21
587
	s3 += carry[2]
588
	s2 -= carry[2] * 2097152
589
	carry[3] = s3 >> 21
590
	s4 += carry[3]
591
	s3 -= carry[3] * 2097152
592
	carry[4] = s4 >> 21
593
	s5 += carry[4]
594
	s4 -= carry[4] * 2097152
595
	carry[5] = s5 >> 21
596
	s6 += carry[5]
597
	s5 -= carry[5] * 2097152
598
	carry[6] = s6 >> 21
599
	s7 += carry[6]
600
	s6 -= carry[6] * 2097152
601
	carry[7] = s7 >> 21
602
	s8 += carry[7]
603
	s7 -= carry[7] * 2097152
604
	carry[8] = s8 >> 21
605
	s9 += carry[8]
606
	s8 -= carry[8] * 2097152
607
	carry[9] = s9 >> 21
608
	s10 += carry[9]
609
	s9 -= carry[9] * 2097152
610
	carry[10] = s10 >> 21
611
	s11 += carry[10]
612
	s10 -= carry[10] * 2097152
613

614
	s[0] = u8(s0 >> 0)
615
	s[1] = u8(s0 >> 8)
616
	s[2] = u8((s0 >> 16) | (s1 * 32))
617
	s[3] = u8(s1 >> 3)
618
	s[4] = u8(s1 >> 11)
619
	s[5] = u8((s1 >> 19) | (s2 * 4))
620
	s[6] = u8(s2 >> 6)
621
	s[7] = u8((s2 >> 14) | (s3 * 128))
622
	s[8] = u8(s3 >> 1)
623
	s[9] = u8(s3 >> 9)
624
	s[10] = u8((s3 >> 17) | (s4 * 16))
625
	s[11] = u8(s4 >> 4)
626
	s[12] = u8(s4 >> 12)
627
	s[13] = u8((s4 >> 20) | (s5 * 2))
628
	s[14] = u8(s5 >> 7)
629
	s[15] = u8((s5 >> 15) | (s6 * 64))
630
	s[16] = u8(s6 >> 2)
631
	s[17] = u8(s6 >> 10)
632
	s[18] = u8((s6 >> 18) | (s7 * 8))
633
	s[19] = u8(s7 >> 5)
634
	s[20] = u8(s7 >> 13)
635
	s[21] = u8(s8 >> 0)
636
	s[22] = u8(s8 >> 8)
637
	s[23] = u8((s8 >> 16) | (s9 * 32))
638
	s[24] = u8(s9 >> 3)
639
	s[25] = u8(s9 >> 11)
640
	s[26] = u8((s9 >> 19) | (s10 * 4))
641
	s[27] = u8(s10 >> 6)
642
	s[28] = u8((s10 >> 14) | (s11 * 128))
643
	s[29] = u8(s11 >> 1)
644
	s[30] = u8(s11 >> 9)
645
	s[31] = u8(s11 >> 17)
646
}
647

648
// Input:
649
//   s[0]+256*s[1]+...+256^63*s[63] = s
650
//
651
// Output:
652
//   s[0]+256*s[1]+...+256^31*s[31] = s mod l
653
//   where l = 2^252 + 27742317777372353535851937790883648493.
654
fn sc_reduce(mut out [32]u8, mut s []u8) {
655
	assert out.len == 32
656
	assert s.len == 64
657
	mut s0 := 2097151 & load3(s[..])
658
	mut s1 := 2097151 & (load4(s[2..]) >> 5)
659
	mut s2 := 2097151 & (load3(s[5..]) >> 2)
660
	mut s3 := 2097151 & (load4(s[7..]) >> 7)
661
	mut s4 := 2097151 & (load4(s[10..]) >> 4)
662
	mut s5 := 2097151 & (load3(s[13..]) >> 1)
663
	mut s6 := 2097151 & (load4(s[15..]) >> 6)
664
	mut s7 := 2097151 & (load3(s[18..]) >> 3)
665
	mut s8 := 2097151 & load3(s[21..])
666
	mut s9 := 2097151 & (load4(s[23..]) >> 5)
667
	mut s10 := 2097151 & (load3(s[26..]) >> 2)
668
	mut s11 := 2097151 & (load4(s[28..]) >> 7)
669
	mut s12 := 2097151 & (load4(s[31..]) >> 4)
670
	mut s13 := 2097151 & (load3(s[34..]) >> 1)
671
	mut s14 := 2097151 & (load4(s[36..]) >> 6)
672
	mut s15 := 2097151 & (load3(s[39..]) >> 3)
673
	mut s16 := 2097151 & load3(s[42..])
674
	mut s17 := 2097151 & (load4(s[44..]) >> 5)
675
	mut s18 := 2097151 & (load3(s[47..]) >> 2)
676
	mut s19 := 2097151 & (load4(s[49..]) >> 7)
677
	mut s20 := 2097151 & (load4(s[52..]) >> 4)
678
	mut s21 := 2097151 & (load3(s[55..]) >> 1)
679
	mut s22 := 2097151 & (load4(s[57..]) >> 6)
680
	mut s23 := (load4(s[60..]) >> 3)
681

682
	s11 += s23 * 666643
683
	s12 += s23 * 470296
684
	s13 += s23 * 654183
685
	s14 -= s23 * 997805
686
	s15 += s23 * 136657
687
	s16 -= s23 * 683901
688
	s23 = 0
689

690
	s10 += s22 * 666643
691
	s11 += s22 * 470296
692
	s12 += s22 * 654183
693
	s13 -= s22 * 997805
694
	s14 += s22 * 136657
695
	s15 -= s22 * 683901
696
	s22 = 0
697

698
	s9 += s21 * 666643
699
	s10 += s21 * 470296
700
	s11 += s21 * 654183
701
	s12 -= s21 * 997805
702
	s13 += s21 * 136657
703
	s14 -= s21 * 683901
704
	s21 = 0
705

706
	s8 += s20 * 666643
707
	s9 += s20 * 470296
708
	s10 += s20 * 654183
709
	s11 -= s20 * 997805
710
	s12 += s20 * 136657
711
	s13 -= s20 * 683901
712
	s20 = 0
713

714
	s7 += s19 * 666643
715
	s8 += s19 * 470296
716
	s9 += s19 * 654183
717
	s10 -= s19 * 997805
718
	s11 += s19 * 136657
719
	s12 -= s19 * 683901
720
	s19 = 0
721

722
	s6 += s18 * 666643
723
	s7 += s18 * 470296
724
	s8 += s18 * 654183
725
	s9 -= s18 * 997805
726
	s10 += s18 * 136657
727
	s11 -= s18 * 683901
728
	s18 = 0
729

730
	mut carry := [17]i64{} // original one
731
	// mut carry := [17]u64{}
732

733
	carry[6] = (s6 + (1048576)) >> 21
734
	s7 += carry[6]
735
	s6 -= carry[6] * 2097152
736
	carry[8] = (s8 + (1048576)) >> 21
737
	s9 += carry[8]
738
	s8 -= carry[8] * 2097152
739
	carry[10] = (s10 + (1048576)) >> 21
740
	s11 += carry[10]
741
	s10 -= carry[10] * 2097152
742
	carry[12] = (s12 + (1048576)) >> 21
743
	s13 += carry[12]
744
	s12 -= carry[12] * 2097152
745
	carry[14] = (s14 + (1048576)) >> 21
746
	s15 += carry[14]
747
	s14 -= carry[14] * 2097152
748
	carry[16] = (s16 + (1048576)) >> 21
749
	s17 += carry[16]
750
	s16 -= carry[16] * 2097152
751

752
	carry[7] = (s7 + (1048576)) >> 21
753
	s8 += carry[7]
754
	s7 -= carry[7] * 2097152
755
	carry[9] = (s9 + (1048576)) >> 21
756
	s10 += carry[9]
757
	s9 -= carry[9] * 2097152
758
	carry[11] = (s11 + (1048576)) >> 21
759
	s12 += carry[11]
760
	s11 -= carry[11] * 2097152
761
	carry[13] = (s13 + (1048576)) >> 21
762
	s14 += carry[13]
763
	s13 -= carry[13] * 2097152
764
	carry[15] = (s15 + (1048576)) >> 21
765
	s16 += carry[15]
766
	s15 -= carry[15] * 2097152
767

768
	s5 += s17 * 666643
769
	s6 += s17 * 470296
770
	s7 += s17 * 654183
771
	s8 -= s17 * 997805
772
	s9 += s17 * 136657
773
	s10 -= s17 * 683901
774
	s17 = 0
775

776
	s4 += s16 * 666643
777
	s5 += s16 * 470296
778
	s6 += s16 * 654183
779
	s7 -= s16 * 997805
780
	s8 += s16 * 136657
781
	s9 -= s16 * 683901
782
	s16 = 0
783

784
	s3 += s15 * 666643
785
	s4 += s15 * 470296
786
	s5 += s15 * 654183
787
	s6 -= s15 * 997805
788
	s7 += s15 * 136657
789
	s8 -= s15 * 683901
790
	s15 = 0
791

792
	s2 += s14 * 666643
793
	s3 += s14 * 470296
794
	s4 += s14 * 654183
795
	s5 -= s14 * 997805
796
	s6 += s14 * 136657
797
	s7 -= s14 * 683901
798
	s14 = 0
799

800
	s1 += s13 * 666643
801
	s2 += s13 * 470296
802
	s3 += s13 * 654183
803
	s4 -= s13 * 997805
804
	s5 += s13 * 136657
805
	s6 -= s13 * 683901
806
	s13 = 0
807

808
	s0 += s12 * 666643
809
	s1 += s12 * 470296
810
	s2 += s12 * 654183
811
	s3 -= s12 * 997805
812
	s4 += s12 * 136657
813
	s5 -= s12 * 683901
814
	s12 = 0
815

816
	carry[0] = (s0 + (1048576)) >> 21
817
	s1 += carry[0]
818
	s0 -= carry[0] * 2097152
819
	carry[2] = (s2 + (1048576)) >> 21
820
	s3 += carry[2]
821
	s2 -= carry[2] * 2097152
822
	carry[4] = (s4 + (1048576)) >> 21
823
	s5 += carry[4]
824
	s4 -= carry[4] * 2097152
825
	carry[6] = (s6 + (1048576)) >> 21
826
	s7 += carry[6]
827
	s6 -= carry[6] * 2097152
828
	carry[8] = (s8 + (1048576)) >> 21
829
	s9 += carry[8]
830
	s8 -= carry[8] * 2097152
831
	carry[10] = (s10 + (1048576)) >> 21
832
	s11 += carry[10]
833
	s10 -= carry[10] * 2097152
834

835
	carry[1] = (s1 + (1048576)) >> 21
836
	s2 += carry[1]
837
	s1 -= carry[1] * 2097152
838
	carry[3] = (s3 + (1048576)) >> 21
839
	s4 += carry[3]
840
	s3 -= carry[3] * 2097152
841
	carry[5] = (s5 + (1048576)) >> 21
842
	s6 += carry[5]
843
	s5 -= carry[5] * 2097152
844
	carry[7] = (s7 + (1048576)) >> 21
845
	s8 += carry[7]
846
	s7 -= carry[7] * 2097152
847
	carry[9] = (s9 + (1048576)) >> 21
848
	s10 += carry[9]
849
	s9 -= carry[9] * 2097152
850
	carry[11] = (s11 + (1048576)) >> 21
851
	s12 += carry[11]
852
	s11 -= carry[11] * 2097152
853

854
	s0 += s12 * 666643
855
	s1 += s12 * 470296
856
	s2 += s12 * 654183
857
	s3 -= s12 * 997805
858
	s4 += s12 * 136657
859
	s5 -= s12 * 683901
860
	s12 = 0
861

862
	carry[0] = s0 >> 21
863
	s1 += carry[0]
864
	s0 -= carry[0] * 2097152
865
	carry[1] = s1 >> 21
866
	s2 += carry[1]
867
	s1 -= carry[1] * 2097152
868
	carry[2] = s2 >> 21
869
	s3 += carry[2]
870
	s2 -= carry[2] * 2097152
871
	carry[3] = s3 >> 21
872
	s4 += carry[3]
873
	s3 -= carry[3] * 2097152
874
	carry[4] = s4 >> 21
875
	s5 += carry[4]
876
	s4 -= carry[4] * 2097152
877
	carry[5] = s5 >> 21
878
	s6 += carry[5]
879
	s5 -= carry[5] * 2097152
880
	carry[6] = s6 >> 21
881
	s7 += carry[6]
882
	s6 -= carry[6] * 2097152
883
	carry[7] = s7 >> 21
884
	s8 += carry[7]
885
	s7 -= carry[7] * 2097152
886
	carry[8] = s8 >> 21
887
	s9 += carry[8]
888
	s8 -= carry[8] * 2097152
889
	carry[9] = s9 >> 21
890
	s10 += carry[9]
891
	s9 -= carry[9] * 2097152
892
	carry[10] = s10 >> 21
893
	s11 += carry[10]
894
	s10 -= carry[10] * 2097152
895
	carry[11] = s11 >> 21
896
	s12 += carry[11]
897
	s11 -= carry[11] * 2097152
898

899
	s0 += s12 * 666643
900
	s1 += s12 * 470296
901
	s2 += s12 * 654183
902
	s3 -= s12 * 997805
903
	s4 += s12 * 136657
904
	s5 -= s12 * 683901
905
	s12 = 0
906

907
	carry[0] = s0 >> 21
908
	s1 += carry[0]
909
	s0 -= carry[0] * 2097152
910
	carry[1] = s1 >> 21
911
	s2 += carry[1]
912
	s1 -= carry[1] * 2097152
913
	carry[2] = s2 >> 21
914
	s3 += carry[2]
915
	s2 -= carry[2] * 2097152
916
	carry[3] = s3 >> 21
917
	s4 += carry[3]
918
	s3 -= carry[3] * 2097152
919
	carry[4] = s4 >> 21
920
	s5 += carry[4]
921
	s4 -= carry[4] * 2097152
922
	carry[5] = s5 >> 21
923
	s6 += carry[5]
924
	s5 -= carry[5] * 2097152
925
	carry[6] = s6 >> 21
926
	s7 += carry[6]
927
	s6 -= carry[6] * 2097152
928
	carry[7] = s7 >> 21
929
	s8 += carry[7]
930
	s7 -= carry[7] * 2097152
931
	carry[8] = s8 >> 21
932
	s9 += carry[8]
933
	s8 -= carry[8] * 2097152
934
	carry[9] = s9 >> 21
935
	s10 += carry[9]
936
	s9 -= carry[9] * 2097152
937
	carry[10] = s10 >> 21
938
	s11 += carry[10]
939
	s10 -= carry[10] * 2097152
940

941
	out[0] = u8(s0 >> 0)
942
	out[1] = u8(s0 >> 8)
943
	out[2] = u8((s0 >> 16) | (s1 * 32))
944
	out[3] = u8(s1 >> 3)
945
	out[4] = u8(s1 >> 11)
946
	out[5] = u8((s1 >> 19) | (s2 * 4))
947
	out[6] = u8(s2 >> 6)
948
	out[7] = u8((s2 >> 14) | (s3 * 128))
949
	out[8] = u8(s3 >> 1)
950
	out[9] = u8(s3 >> 9)
951
	out[10] = u8((s3 >> 17) | (s4 * 16))
952
	out[11] = u8(s4 >> 4)
953
	out[12] = u8(s4 >> 12)
954
	out[13] = u8((s4 >> 20) | (s5 * 2))
955
	out[14] = u8(s5 >> 7)
956
	out[15] = u8((s5 >> 15) | (s6 * 64))
957
	out[16] = u8(s6 >> 2)
958
	out[17] = u8(s6 >> 10)
959
	out[18] = u8((s6 >> 18) | (s7 * 8))
960
	out[19] = u8(s7 >> 5)
961
	out[20] = u8(s7 >> 13)
962
	out[21] = u8(s8 >> 0)
963
	out[22] = u8(s8 >> 8)
964
	out[23] = u8((s8 >> 16) | (s9 * 32))
965
	out[24] = u8(s9 >> 3)
966
	out[25] = u8(s9 >> 11)
967
	out[26] = u8((s9 >> 19) | (s10 * 4))
968
	out[27] = u8(s10 >> 6)
969
	out[28] = u8((s10 >> 14) | (s11 * 128))
970
	out[29] = u8(s11 >> 1)
971
	out[30] = u8(s11 >> 9)
972
	out[31] = u8(s11 >> 17)
973
}
974

975
// non_adjacent_form computes a width-w non-adjacent form for this scalar.
976
//
977
// w must be between 2 and 8, or non_adjacent_form will panic.
978
pub fn (mut s Scalar) non_adjacent_form(w u32) []i8 {
979
	// This implementation is adapted from the one
980
	// in curve25519-dalek and is documented there:
981
	// https://github.com/dalek-cryptography/curve25519-dalek/blob/f630041af28e9a405255f98a8a93adca18e4315b/src/scalar.rs#L800-L871
982
	if s.s[31] > 127 {
983
		panic('scalar has high bit set illegally')
984
	}
985
	if w < 2 {
986
		panic('w must be at least 2 by the definition of NAF')
987
	} else if w > 8 {
988
		panic('NAF digits must fit in i8')
989
	}
990

991
	mut naf := []i8{len: 256}
992
	mut digits := [5]u64{}
993

994
	for i := 0; i < 4; i++ {
995
		digits[i] = binary.little_endian_u64(s.s[i * 8..])
996
	}
997

998
	width := u64(1 << w)
999
	window_mask := u64(width - 1)
1000

1001
	mut pos := u32(0)
1002
	mut carry := u64(0)
1003
	for pos < 256 {
1004
		idx_64 := pos / 64
1005
		idx_bit := pos % 64
1006
		mut bitbuf := u64(0)
1007
		if idx_bit < 64 - w {
1008
			// This window's bits are contained in a single u64
1009
			bitbuf = digits[idx_64] >> idx_bit
1010
		} else {
1011
			// Combine the current 64 bits with bits from the next 64
1012
			bitbuf = (digits[idx_64] >> idx_bit) | (digits[1 + idx_64] << (64 - idx_bit))
1013
		}
1014

1015
		// Add carry into the current window
1016
		window := carry + (bitbuf & window_mask)
1017

1018
		if window & 1 == 0 {
1019
			// If the window value is even, preserve the carry and continue.
1020
			// Why is the carry preserved?
1021
			// If carry == 0 and window & 1 == 0,
1022
			//    then the next carry should be 0
1023
			// If carry == 1 and window & 1 == 0,
1024
			//    then bit_buf & 1 == 1 so the next carry should be 1
1025
			pos += 1
1026
			continue
1027
		}
1028

1029
		if window < width / 2 {
1030
			carry = 0
1031
			naf[pos] = i8(window)
1032
		} else {
1033
			carry = 1
1034
			naf[pos] = i8(window) - i8(width)
1035
		}
1036

1037
		pos += w
1038
	}
1039
	return naf
1040
}
1041

1042
fn (mut s Scalar) signed_radix16() []i8 {
1043
	if s.s[31] > 127 {
1044
		panic('scalar has high bit set illegally')
1045
	}
1046

1047
	mut digits := []i8{len: 64}
1048

1049
	// Compute unsigned radix-16 digits:
1050
	for i := 0; i < 32; i++ {
1051
		digits[2 * i] = i8(s.s[i] & 15)
1052
		digits[2 * i + 1] = i8((s.s[i] >> 4) & 15)
1053
	}
1054

1055
	// Recenter coefficients:
1056
	for i := 0; i < 63; i++ {
1057
		mut carry := (digits[i] + 8) >> 4
1058

1059
		// digits[i] -= unsafe { carry * 16 } // original one
1060
		digits[i] -= unsafe { carry * 16 } // carry * 16 == carry *
1061

1062
		digits[i + 1] += carry
1063
	}
1064

1065
	return digits
1066
}
1067

1068
// utility function
1069
// generate returns a valid (reduced modulo l) Scalar with a distribution
1070
// weighted towards high, low, and edge values.
1071
fn generate_scalar(size int) !Scalar {
1072
	/*
1073
	s := scZero
1074
	diceRoll := rand.Intn(100)
1075
	switch {
1076
	case diceRoll == 0:
1077
	case diceRoll == 1:
1078
		s = scOne
1079
	case diceRoll == 2:
1080
		s = scMinusOne
1081
	case diceRoll < 5:
1082
		// Generate a low scalar in [0, 2^125).
1083
		rand.Read(s.s[:16])
1084
		s.s[15] &= (1 * 32) - 1
1085
	case diceRoll < 10:
1086
		// Generate a high scalar in [2^252, 2^252 + 2^124).
1087
		s.s[31] = 1 * 16
1088
		rand.Read(s.s[:16])
1089
		s.s[15] &= (1 * 16) - 1
1090
	default:
1091
		// Generate a valid scalar in [0, l) by returning [0, 2^252) which has a
1092
		// negligibly different distribution (the former has a 2^-127.6 chance
1093
		// of being out of the latter range).
1094
		rand.Read(s.s[:])
1095
		s.s[31] &= (1 * 16) - 1
1096
	}
1097
	return reflect.ValueOf(s)
1098
	*/
1099
	mut s := sc_zero
1100
	diceroll := rand.intn(100) or { 0 }
1101
	match true {
1102
		/*
1103
		case diceroll == 0:
1104
			case diceroll == 1:
1105
		*/
1106
		diceroll == 0 || diceroll == 1 {
1107
			s = sc_one
1108
		}
1109
		diceroll == 2 {
1110
			s = sc_minus_one
1111
		}
1112
		diceroll < 5 {
1113
			// rand.Read(s.s[:16]) // read random bytes and fill buf
1114
			// using builtin rand.read([]buf)
1115
			rand.read(mut s.s[..16])
1116
			// buf := rand.read(s.s[..16].len)!
1117
			// copy(mut s.s[..16], buf)
1118

1119
			/*
1120
			for i, item in buf {
1121
				s.s[i] = item
1122
			}
1123
			*/
1124
			s.s[15] &= (1 * 32) - 1
1125
			// generate a low scalar in [0, 2^125).
1126
		}
1127
		diceroll < 10 {
1128
			// generate a high scalar in [2^252, 2^252 + 2^124).
1129
			s.s[31] = 1 * 16
1130
			// Read generates len(p) random bytes and writes them into p
1131
			// rand.Read(s.s[:16])
1132
			rand.read(mut s.s[..16])
1133
			// buf := rand.read(s.s[..16].len)!
1134
			// copy(mut s.s[..16], buf)
1135

1136
			/*
1137
			for i, item in buf {
1138
				s.s[i] = item
1139
			}
1140
			*/
1141
			s.s[15] &= (1 * 16) - 1
1142
		}
1143
		else {
1144
			// generate a valid scalar in [0, l) by returning [0, 2^252) which has a
1145
			// negligibly different distribution (the former has a 2^-127.6 chance
1146
			// of being out of the latter range).
1147
			// rand.Read(s.s[:])
1148
			rand.read(mut s.s[..])
1149
			// buf := crand.read(s.s.len)!
1150
			// copy(mut s.s[..], buf)
1151

1152
			/*
1153
			for i, item in buf {
1154
				s.s[i] = item
1155
			}
1156
			*/
1157
			s.s[31] &= (1 * 16) - 1
1158
		}
1159
	}
1160
	return s
1161
}
1162

1163
type NotZeroScalar = Scalar
1164

1165
fn generate_notzero_scalar(size int) !NotZeroScalar {
1166
	mut s := Scalar{}
1167
	for s == sc_zero {
1168
		s = generate_scalar(size)!
1169
	}
1170
	return NotZeroScalar(s)
1171
}
1172