[email protected] (Niels Möller) writes:
> This is the speed I get for C implementations of poly1305_update on my
> x86_64 laptop:
>
> * Radix 26: 1.2 GByte/s (old code)
>
> * Radix 32: 1.3 GByte/s
>
> * Radix 64: 2.2 GByte/s
>
> It would be interesting with benchmarks on actual 32-bit hardware,
> 32-bit ARM likely being the most relevant arch.
>
> For comparison, the current x86_64 asm version: 2.5 GByte/s.
I've tried reworking folding, to reduce latency. Idea is to let the most
significant state word be close to a word, rather than limited to <= 4
as in the previous version. When multiplying by r, split one of the
multiplies to take out the low 2 bits. For the radix 64 version, that
term is
B^2 t_2 * r0
Split t_2 as 4*hi + lo, then this can be reduced to
B^2 lo * r0 + hi * 5*r0
(Using the same old B^2 = 5/4 (mod p) in a slightly different way).
The 5*r0 fits one word and can be precomputed, and then this
multiplication goes in parallell with the other multiplies, and no
multiply left in the final per-block folding. With this trick I get on
the same machine
Radix 32: 1.65 GByte/s
Radix 64: 2.75 GByte/s, i.e., faster than current x86_64 asm version.
I haven't yet done a strict analysis of bounds on the state and
temporaries, but I would expect that it works out with no possibility of
overflow.
See attached file. To fit the precomputed 5*r0 in a nice way I had to
rearrange the unions in struct poly1305_ctx a bit, I also attach the
patch to do this. Size of the struct should be the same, so I think it
can be done without any abi bump.
Regards,
/Niels
diff --git a/poly1305.h b/poly1305.h
index 99c63c8a..6c13a590 100644
--- a/poly1305.h
+++ b/poly1305.h
@@ -55,18 +55,15 @@ struct poly1305_ctx {
/* Key, 128-bit value and some cached multiples. */
union
{
- uint32_t r32[6];
- uint64_t r64[3];
+ uint32_t r32[8];
+ uint64_t r64[4];
} r;
- uint32_t s32[3];
/* State, represented as words of 26, 32 or 64 bits, depending on
implementation. */
- /* High bits first, to maintain alignment. */
- uint32_t hh;
union
{
- uint32_t h32[4];
- uint64_t h64[2];
+ uint32_t h32[6];
+ uint64_t h64[3];
} h;
};
/* poly1305-internal.c
Copyright: 2013 Nikos Mavrogiannopoulos
Copyright: 2013, 2022 Niels Möller
This file is part of GNU Nettle.
GNU Nettle is free software: you can redistribute it and/or
modify it under the terms of either:
* the GNU Lesser General Public License as published by the Free
Software Foundation; either version 3 of the License, or (at your
option) any later version.
or
* the GNU General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your
option) any later version.
or both in parallel, as here.
GNU Nettle is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received copies of the GNU General Public License and
the GNU Lesser General Public License along with this program. If
not, see http://www.gnu.org/licenses/.
*/
#if HAVE_CONFIG_H
#include "config.h"
#endif
#include <assert.h>
#include <string.h>
#include "poly1305.h"
#include "poly1305-internal.h"
#include "macros.h"
#if 1
typedef unsigned __int128 nettle_uint128_t;
#define M64(a,b) ((nettle_uint128_t)(a) * (b))
#define r0 r.r64[0]
#define r1 r.r64[1]
#define s0 r.r64[2]
#define s1 r.r64[3]
#define h0 h.h64[0]
#define h1 h.h64[1]
#define h2 h.h64[2]
void
_nettle_poly1305_set_key(struct poly1305_ctx *ctx, const uint8_t key[16])
{
uint64_t t0, t1;
t0 = LE_READ_UINT64 (key);
t1 = LE_READ_UINT64 (key + 8);
ctx->r0 = t0 & UINT64_C (0x0ffffffc0fffffff);
ctx->r1 = t1 & UINT64_C (0x0ffffffc0ffffffc);
ctx->s0 = 5*ctx->r0;
ctx->s1 = 5*(ctx->r1 >> 2);
ctx->h0 = 0;
ctx->h1 = 0;
ctx->h2 = 0;
}
void
_nettle_poly1305_block (struct poly1305_ctx *ctx, const uint8_t *m, unsigned m128)
{
uint64_t t0, t1, t2;
nettle_uint128_t s, f0, f1;
/* Add in message block */
t0 = ctx->h0 + LE_READ_UINT64(m);
s = (nettle_uint128_t) ctx->h1 + (t0 < ctx->h0) + LE_READ_UINT64(m+8);
t1 = s;
t2 = ctx->h2 + (s >> 64) + m128;
/* Key constants are bounded by rk < 2^60, sk < 5*2^58, therefore
all the fk sums fit in 128 bits without overflow, with at least
one bit margin. */
f0 = M64(t0, ctx->r0) + M64(t1, ctx->s1) + M64(t2 >> 2, ctx->s0);
f1 = M64(t0, ctx->r1) + M64(t1, ctx->r0) + M64(t2, ctx->s1)
+ ((nettle_uint128_t)((t2 & 3) * ctx->r0) << 64);
ctx->h0 = f0;
f1 += f0 >> 64;
ctx->h1 = f1;
ctx->h2 = f1 >> 64;
}
/* Adds digest to the nonce */
void
_nettle_poly1305_digest (struct poly1305_ctx *ctx, union nettle_block16 *s)
{
uint64_t t0, t1, t2, c0, c1, mask, m0;
t0 = ctx->h0;
t1 = ctx->h1;
t2 = ctx->h2;
/* Fold high part of t2 */
c0 = 5 * (t2 >> 2);
t2 &= 3;
t0 += c0; c1 = (t0 < c0);
t1 += c1;
t2 += (t1 < c1);
/* Compute resulting carries when adding 5. */
c1 = t0 > -(UINT64_C(5));
t2 += (t1 + c1 < c1);
/* Set if H >= 2^130 - 5 */
mask = - (t2 >> 2);
t0 += mask & 5;
t1 += mask & c1;
/* FIXME: Take advantage of s being aligned as an unsigned long. */
m0 = LE_READ_UINT64(s->b);
t0 += m0;
t1 += (t0 < m0) + LE_READ_UINT64(s->b+8);
LE_WRITE_UINT64(s->b, t0);
LE_WRITE_UINT64(s->b+8, t1);
ctx->h0 = 0;
ctx->h1 = 0;
ctx->h2 = 0;
}
#else
#define M32(a,b) ((uint64_t)(a) * (b))
#define r0 r.r32[0]
#define r1 r.r32[1]
#define r2 r.r32[2]
#define r3 r.r32[3]
#define s0 r.r32[4]
#define s1 r.r32[5]
#define s2 r.r32[6]
#define s3 r.r32[7]
#define h0 h.h32[0]
#define h1 h.h32[1]
#define h2 h.h32[2]
#define h3 h.h32[3]
#define h4 h.h32[4]
void
_nettle_poly1305_set_key(struct poly1305_ctx *ctx, const uint8_t key[16])
{
uint32_t t0, t1, t2, t3;
t0 = LE_READ_UINT32 (key);
t1 = LE_READ_UINT32 (key+4);
t2 = LE_READ_UINT32 (key+8);
t3 = LE_READ_UINT32 (key+12);
ctx->r0 = t0 & 0x0fffffff;
ctx->r1 = t1 & 0x0ffffffc;
ctx->r2 = t2 & 0x0ffffffc;
ctx->r3 = t3 & 0x0ffffffc;
ctx->s0 = 5*ctx->r0;
ctx->s1 = 5*(ctx->r1 >> 2);
ctx->s2 = 5*(ctx->r2 >> 2);
ctx->s3 = 5*(ctx->r3 >> 2);
ctx->h0 = 0;
ctx->h1 = 0;
ctx->h2 = 0;
ctx->h3 = 0;
ctx->h4 = 0;
}
void
_nettle_poly1305_block (struct poly1305_ctx *ctx, const uint8_t *m, unsigned m128)
{
uint32_t t0, t1, t2, t3, t4;
uint64_t s, f0, f1, f2, f3;
/* Add in message block */
t0 = ctx->h0 + LE_READ_UINT32(m);
s = (uint64_t) ctx->h1 + (t0 < ctx->h0) + LE_READ_UINT32(m+4);
t1 = s;
s = ctx->h2 + (s >> 32) + LE_READ_UINT32(m+8);
t2 = s;
s = ctx->h3 + (s >> 32) + LE_READ_UINT32(m+12);
t3 = s;
t4 = ctx->h4 + (s >> 32) + m128;
/* Key constants are bounded by rk < 2^28, sk < 5*2^26, therefore
all the fk sums fit in 64 bits without overflow, with at least
one bit margin. */
f0 = M32(t0, ctx->r0) + M32(t1, ctx->s3) + M32(t2, ctx->s2) + M32(t3, ctx->s1)
+ M32(t4 >> 2, ctx->s0);
f1 = M32(t0, ctx->r1) + M32(t1, ctx->r0) + M32(t2, ctx->s3) + M32(t3, ctx->s2)
+ M32(t4, ctx->s1);
f2 = M32(t0, ctx->r2) + M32(t1, ctx->r1) + M32(t2, ctx->r0) + M32(t3, ctx->s3)
+ M32(t4, ctx->s2);
f3 = M32(t0, ctx->r3) + M32(t1, ctx->r2) + M32(t2, ctx->r1) + M32(t3, ctx->r0)
+ M32(t4, ctx->s3) + ((uint64_t)((t4 & 3)*ctx->r0) << 32);
ctx->h0 = f0;
f1 += f0 >> 32;
ctx->h1 = f1;
f2 += f1 >> 32;
ctx->h2 = f2;
f3 += f2 >> 32;
ctx->h3 = f3;
ctx->h4 = f3 >> 32;
}
/* Adds digest to the nonce */
void
_nettle_poly1305_digest (struct poly1305_ctx *ctx, union nettle_block16 *s)
{
uint32_t t0, t1, t2, t3, t4, c0, c1, c2, c3, mask;
uint64_t f0, f1, f2;
t0 = ctx->h0;
t1 = ctx->h1;
t2 = ctx->h2;
t3 = ctx->h3;
t4 = ctx->h4;
/* Fold high part of t4 */
c0 = 5 * (t4 >> 2);
t4 &= 3;
t0 += c0; c1 = (t0 < c0);
t1 += c1; c2 = (t1 < c1);
t2 += c2; c3 = (t2 < c2);
t3 += c3;
t4 += (t3 < c3);
/* Compute resulting carries when adding 5. */
c1 = (t0 >= 0xfffffffb);
c2 = (t1 + c1 < c1);
c3 = (t2 + c2 < t2);
t4 += (t3 + c3 < t3);
/* Set if H >= 2^130 - 5 */
mask = - (t4 >> 2);
t0 += mask & 5;
t1 += mask & c1;
t2 += mask & c2;
t3 += mask & c3;
/* FIXME: Take advantage of s being aligned as an unsigned long. */
f0 = (uint64_t) t0 + LE_READ_UINT32(s->b);
f1 = t1 + (f0 >> 32) + LE_READ_UINT32(s->b+4);
f2 = t2 + (f1 >> 32) + LE_READ_UINT32(s->b+8);
t3 += (f2 >> 32) + LE_READ_UINT32(s->b+12);
LE_WRITE_UINT32(s->b, f0);
LE_WRITE_UINT32(s->b+4, f1);
LE_WRITE_UINT32(s->b+8, f2);
LE_WRITE_UINT32(s->b+12, t3);
ctx->h0 = 0;
ctx->h1 = 0;
ctx->h2 = 0;
ctx->h3 = 0;
ctx->h4 = 0;
}
#endif
--
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.
_______________________________________________
nettle-bugs mailing list
[email protected]
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
