Re: [PATCH] crypto: gf128mul - define gf128mul_x_ble in gf128mul.h

[Ondrej Mosnáček]

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

[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.

Jeff

Re: [PATCH] crypto: gf128mul - define gf128mul_x_ble in gf128mul.h

[Ondrej Mosnáček]

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

[Eric Biggers]

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