Skip to content

Commit 5213207

Browse files
sipasipa
committed
Add secp256k1_scalar_add_bit
1 parent 3c0ae43 commit 5213207

File tree

4 files changed

+62
-0
lines changed

4 files changed

+62
-0
lines changed

‎src/scalar.h‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,9 @@ static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar_
3636
/** Add two scalars together (modulo the group order). */
3737
static void secp256k1_scalar_add(secp256k1_scalar_t *r, const secp256k1_scalar_t *a, const secp256k1_scalar_t *b);
3838

39+
/** Add a power of two to a scalar. The result is not allowed to overflow. */
40+
static void secp256k1_scalar_add_bit(secp256k1_scalar_t *r, unsigned int bit);
41+
3942
/** Multiply two scalars (modulo the group order). */
4043
static void secp256k1_scalar_mul(secp256k1_scalar_t *r, const secp256k1_scalar_t *a, const secp256k1_scalar_t *b);
4144

‎src/scalar_4x64_impl.h‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -75,6 +75,22 @@ static void secp256k1_scalar_add(secp256k1_scalar_t *r, const secp256k1_scalar_t
7575
secp256k1_scalar_reduce(r, t + secp256k1_scalar_check_overflow(r));
7676
}
7777

78+
static void secp256k1_scalar_add_bit(secp256k1_scalar_t *r, unsigned int bit) {
79+
VERIFY_CHECK(bit < 256);
80+
uint128_t t = (uint128_t)r->d[0] + (((uint64_t)((bit >> 6) == 0)) << bit);
81+
r->d[0] = t & 0xFFFFFFFFFFFFFFFFULL; t >>= 64;
82+
t += (uint128_t)r->d[1] + (((uint64_t)((bit >> 6) == 1)) << (bit & 0x3F));
83+
r->d[1] = t & 0xFFFFFFFFFFFFFFFFULL; t >>= 64;
84+
t += (uint128_t)r->d[2] + (((uint64_t)((bit >> 6) == 2)) << (bit & 0x3F));
85+
r->d[2] = t & 0xFFFFFFFFFFFFFFFFULL; t >>= 64;
86+
t += (uint128_t)r->d[3] + (((uint64_t)((bit >> 6) == 3)) << (bit & 0x3F));
87+
r->d[3] = t & 0xFFFFFFFFFFFFFFFFULL;
88+
#ifdef VERIFY
89+
VERIFY_CHECK((t >> 64) == 0);
90+
VERIFY_CHECK(secp256k1_scalar_check_overflow(r) == 0);
91+
#endif
92+
}
93+
7894
static void secp256k1_scalar_set_b32(secp256k1_scalar_t *r, const unsigned char *b32, int *overflow) {
7995
r->d[0] = (uint64_t)b32[31] | (uint64_t)b32[30] << 8 | (uint64_t)b32[29] << 16 | (uint64_t)b32[28] << 24 | (uint64_t)b32[27] << 32 | (uint64_t)b32[26] << 40 | (uint64_t)b32[25] << 48 | (uint64_t)b32[24] << 56;
8096
r->d[1] = (uint64_t)b32[23] | (uint64_t)b32[22] << 8 | (uint64_t)b32[21] << 16 | (uint64_t)b32[20] << 24 | (uint64_t)b32[19] << 32 | (uint64_t)b32[18] << 40 | (uint64_t)b32[17] << 48 | (uint64_t)b32[16] << 56;

‎src/scalar_8x32_impl.h‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -109,6 +109,30 @@ static void secp256k1_scalar_add(secp256k1_scalar_t *r, const secp256k1_scalar_t
109109
secp256k1_scalar_reduce(r, t + secp256k1_scalar_check_overflow(r));
110110
}
111111

112+
static void secp256k1_scalar_add_bit(secp256k1_scalar_t *r, unsigned int bit) {
113+
VERIFY_CHECK(bit < 256);
114+
uint64_t t = (uint64_t)r->d[0] + (((uint32_t)((bit >> 5) == 0)) << bit);
115+
r->d[0] = t & 0xFFFFFFFFULL; t >>= 32;
116+
t += (uint64_t)r->d[1] + (((uint32_t)((bit >> 5) == 1)) << (bit & 0x1F));
117+
r->d[1] = t & 0xFFFFFFFFULL; t >>= 32;
118+
t += (uint64_t)r->d[2] + (((uint32_t)((bit >> 5) == 2)) << (bit & 0x1F));
119+
r->d[2] = t & 0xFFFFFFFFULL; t >>= 32;
120+
t += (uint64_t)r->d[3] + (((uint32_t)((bit >> 5) == 3)) << (bit & 0x1F));
121+
r->d[3] = t & 0xFFFFFFFFULL; t >>= 32;
122+
t += (uint64_t)r->d[4] + (((uint32_t)((bit >> 5) == 4)) << (bit & 0x1F));
123+
r->d[4] = t & 0xFFFFFFFFULL; t >>= 32;
124+
t += (uint64_t)r->d[5] + (((uint32_t)((bit >> 5) == 5)) << (bit & 0x1F));
125+
r->d[5] = t & 0xFFFFFFFFULL; t >>= 32;
126+
t += (uint64_t)r->d[6] + (((uint32_t)((bit >> 5) == 6)) << (bit & 0x1F));
127+
r->d[6] = t & 0xFFFFFFFFULL; t >>= 32;
128+
t += (uint64_t)r->d[7] + (((uint32_t)((bit >> 5) == 7)) << (bit & 0x1F));
129+
r->d[7] = t & 0xFFFFFFFFULL;
130+
#ifdef VERIFY
131+
VERIFY_CHECK((t >> 32) == 0);
132+
VERIFY_CHECK(secp256k1_scalar_check_overflow(r) == 0);
133+
#endif
134+
}
135+
112136
static void secp256k1_scalar_set_b32(secp256k1_scalar_t *r, const unsigned char *b32, int *overflow) {
113137
r->d[0] = (uint32_t)b32[31] | (uint32_t)b32[30] << 8 | (uint32_t)b32[29] << 16 | (uint32_t)b32[28] << 24;
114138
r->d[1] = (uint32_t)b32[27] | (uint32_t)b32[26] << 8 | (uint32_t)b32[25] << 16 | (uint32_t)b32[24] << 24;

‎src/tests.c‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -382,6 +382,25 @@ void scalar_test(void) {
382382
CHECK(secp256k1_scalar_eq(&r1, &r2));
383383
}
384384

385+
{
386+
/* Test add_bit. */
387+
int bit = secp256k1_rand32() % 256;
388+
secp256k1_scalar_t b;
389+
secp256k1_scalar_clear(&b);
390+
secp256k1_scalar_add_bit(&b, 0);
391+
CHECK(secp256k1_scalar_is_one(&b));
392+
for (int i = 0; i < bit; i++) {
393+
secp256k1_scalar_add(&b, &b, &b);
394+
}
395+
secp256k1_scalar_t r1 = s1, r2 = s1;
396+
secp256k1_scalar_add(&r1, &r1, &b);
397+
if (!(secp256k1_scalar_get_bits(&s1, 255, 1) == 1 && secp256k1_scalar_get_bits(&r1, 255, 1) == 0)) {
398+
/* No overflow happened. */
399+
secp256k1_scalar_add_bit(&r2, bit);
400+
CHECK(secp256k1_scalar_eq(&r1, &r2));
401+
}
402+
}
403+
385404
{
386405
/* Test commutativity of mul. */
387406
secp256k1_scalar_t r1, r2;

0 commit comments

Comments
 (0)