Re: [PATCH] crypto: gf128mul - define gf128mul_x_ble in gf128mul.h
Hi Jeff, 2017-03-31 8:05 GMT+02:00 Jeffrey Walton : >>> Also note that '(b & ((u64)1 << 63)) ? 0x87 : 0x00;' is actually getting >>> compiled as '((s64)b >> 63) & 0x87', which is branchless and therefore >>> makes the >>> new version more efficient than one might expect: >>> >>> sar$0x3f,%rax >>> and$0x87,%eax >>> >>> It could even be written the branchless way explicitly, but it shouldn't >>> matter. >> >> I think the definition using unsigned operations is more intuitive... >> Let's just leave the clever tricks up to the compiler :) > > It may be a good idea to use the one that provides constant time-ness > to help avoid leaking information. That's a good point... I played around with various ways to write the expression in Compiler Explorer [1] and indeed GCC fails to produce constant-time code from my version on some architectures (e.g. the 32-bit ARM). The version with an explicit arithmetic right shift seems to produce the most efficient code across platforms, so I'll rewrite it like that for v3. Thanks, O.M. [1] https://gcc.godbolt.org/
Re: [PATCH] crypto: gf128mul - define gf128mul_x_ble in gf128mul.h
>> Also note that '(b & ((u64)1 << 63)) ? 0x87 : 0x00;' is actually getting >> compiled as '((s64)b >> 63) & 0x87', which is branchless and therefore makes >> the >> new version more efficient than one might expect: >> >> sar$0x3f,%rax >> and$0x87,%eax >> >> It could even be written the branchless way explicitly, but it shouldn't >> matter. > > I think the definition using unsigned operations is more intuitive... > Let's just leave the clever tricks up to the compiler :) It may be a good idea to use the one that provides constant time-ness to help avoid leaking information. Jeff
Re: [PATCH] crypto: gf128mul - define gf128mul_x_ble in gf128mul.h
Hi Eric, 2017-03-30 21:55 GMT+02:00 Eric Biggers : > This is an improvement; I'm just thinking that maybe this should be done for > all > the gf128mul_x_*() functions, if only so that they use a consistent style and > are all defined next to each other. Right, that doesn't seem to be a bad idea... I was confused for a while by the '& 0xff' in the _lle one, but now I see it also uses just two values of the table, so it can be re-written in a similar way. In fact, the OCB mode from RFC 7253 (that I'm currently trying to port to kernel crypto API) uses gf128mul_x_bbe, so it would be useful to have that one accessible, too. I will move them all in v2, then. > Also note that '(b & ((u64)1 << 63)) ? 0x87 : 0x00;' is actually getting > compiled as '((s64)b >> 63) & 0x87', which is branchless and therefore makes > the > new version more efficient than one might expect: > > sar$0x3f,%rax > and$0x87,%eax > > It could even be written the branchless way explicitly, but it shouldn't > matter. I think the definition using unsigned operations is more intuitive... Let's just leave the clever tricks up to the compiler :) Thanks, O.M. > > - Eric
Re: [PATCH] crypto: gf128mul - define gf128mul_x_ble in gf128mul.h
Hi Ondrej, On Thu, Mar 30, 2017 at 09:25:35PM +0200, Ondrej Mosnacek wrote: > The gf128mul_x_ble function is currently defined in gf128mul.c, because > it depends on the gf128mul_table_be multiplication table. > > However, since the function is very small and only uses two values from > the table, it is better for it to be defined as inline function in > gf128mul.h. That way, the function can be inlined by the compiler for > better performance. > > After this change, the speed of the generic 'xts(aes)' implementation > increased from ~225 MiB/s to ~235 MiB/s (measured using 'cryptsetup > benchmark' on an Intel system with CRYPTO_AES_X86_64 and > CRYPTO_AES_NI_INTEL disabled). > > Signed-off-by: Ondrej Mosnacek ... > > -/* multiply by x in ble format, needed by XTS */ > -void gf128mul_x_ble(be128 *a, const be128 *b); > +/* Multiply by x in ble format, needed by XTS. > + * Defined here for performance. */ > +static inline void gf128mul_x_ble(be128 *r, const be128 *x) > +{ > + u64 a = le64_to_cpu(x->a); > + u64 b = le64_to_cpu(x->b); > + /* equivalent to gf128mul_table_be[b >> 63] (see crypto/gf128mul.c): */ > + u64 _tt = (b & ((u64)1 << 63)) ? 0x87 : 0x00; > + > + r->a = cpu_to_le64((a << 1) ^ _tt); > + r->b = cpu_to_le64((b << 1) | (a >> 63)); > +} > > /* 4k table optimization */ > > -- > 2.9.3 > This is an improvement; I'm just thinking that maybe this should be done for all the gf128mul_x_*() functions, if only so that they use a consistent style and are all defined next to each other. Also note that '(b & ((u64)1 << 63)) ? 0x87 : 0x00;' is actually getting compiled as '((s64)b >> 63) & 0x87', which is branchless and therefore makes the new version more efficient than one might expect: sar$0x3f,%rax and$0x87,%eax It could even be written the branchless way explicitly, but it shouldn't matter. - Eric