[PATCH 2/2] Avoid slow integer multiplication and division with blocksize calculations.
Jussi Kivilinna
jussi.kivilinna at mbnet.fi
Thu Nov 29 16:37:14 CET 2012
* cipher/cipher-internal.h (gcry_cipher_handle): Add blockmask and
blockshift members for blocksize.
* cipher/cipher.c (gcry_cipher_open): Precalculate mask and shift from
blocksize and add assert for checking that blocksize if power of two.
* cipher/cipher-cbc.c (_gcry_cipher_cbc_encrypt)
(_gcry_cipher_cbc_decrypt): Use masking/shifting inplace for
multiplication/division/modulo for blocksize.
* cipher/cipher-cfb.c (_gcry_cipher_cfb_encrypt)
(_gcry_cipher_cfb_decrypt): Likewise.
* cipher/cipher-ctr.c (_gcry_cipher_ctr_encrypt): Likewise.
* configure.ac: Check for function ffs.
* src/g10lib.h [!HAVE_FFS] (ffs): New function prototype.
* src/missing-string.c [!HAVE_FFS] (ffs): New function.
--
Currently all blocksizes are powers of two (and most likely in future), so we
can avoid using integer multiplication and division/modulo operations (that
are slow on architechtures without hardware units for mul/div/mod).
Signed-off-by: Jussi Kivilinna <jussi.kivilinna at mbnet.fi>
---
cipher/cipher-cbc.c | 28 ++++++++++++++--------------
cipher/cipher-cfb.c | 16 ++++++++--------
cipher/cipher-ctr.c | 8 ++++----
cipher/cipher-internal.h | 5 +++++
cipher/cipher.c | 14 ++++++++++----
configure.ac | 2 +-
src/g10lib.h | 3 +++
src/missing-string.c | 21 +++++++++++++++++++++
8 files changed, 66 insertions(+), 31 deletions(-)
diff --git a/cipher/cipher-cbc.c b/cipher/cipher-cbc.c
index 0d30f63..63aa2a9 100644
--- a/cipher/cipher-cbc.c
+++ b/cipher/cipher-cbc.c
@@ -41,19 +41,19 @@ _gcry_cipher_cbc_encrypt (gcry_cipher_hd_t c,
unsigned char *ivp;
int i;
size_t blocksize = c->cipher->blocksize;
- unsigned nblocks = inbuflen / blocksize;
+ unsigned nblocks = inbuflen >> c->blockshift;
if (outbuflen < ((c->flags & GCRY_CIPHER_CBC_MAC)? blocksize : inbuflen))
return GPG_ERR_BUFFER_TOO_SHORT;
- if ((inbuflen % c->cipher->blocksize)
+ if ((inbuflen & c->blockmask)
&& !(inbuflen > c->cipher->blocksize
&& (c->flags & GCRY_CIPHER_CBC_CTS)))
return GPG_ERR_INV_LENGTH;
if ((c->flags & GCRY_CIPHER_CBC_CTS) && inbuflen > blocksize)
{
- if ((inbuflen % blocksize) == 0)
+ if ((inbuflen & c->blockmask) == 0)
nblocks--;
}
@@ -61,9 +61,9 @@ _gcry_cipher_cbc_encrypt (gcry_cipher_hd_t c,
{
c->bulk.cbc_enc (&c->context.c, c->u_iv.iv, outbuf, inbuf, nblocks,
(c->flags & GCRY_CIPHER_CBC_MAC));
- inbuf += nblocks * blocksize;
+ inbuf += nblocks << c->blockshift;
if (!(c->flags & GCRY_CIPHER_CBC_MAC))
- outbuf += nblocks * blocksize;
+ outbuf += nblocks << c->blockshift;
}
else
{
@@ -85,10 +85,10 @@ _gcry_cipher_cbc_encrypt (gcry_cipher_hd_t c,
int restbytes;
unsigned char b;
- if ((inbuflen % blocksize) == 0)
+ if ((inbuflen & c->blockmask) == 0)
restbytes = blocksize;
else
- restbytes = inbuflen % blocksize;
+ restbytes = inbuflen & c->blockmask;
outbuf -= blocksize;
for (ivp = c->u_iv.iv, i = 0; i < restbytes; i++)
@@ -116,12 +116,12 @@ _gcry_cipher_cbc_decrypt (gcry_cipher_hd_t c,
unsigned int n;
int i;
size_t blocksize = c->cipher->blocksize;
- unsigned int nblocks = inbuflen / blocksize;
+ unsigned int nblocks = inbuflen >> c->blockshift;
if (outbuflen < inbuflen)
return GPG_ERR_BUFFER_TOO_SHORT;
- if ((inbuflen % c->cipher->blocksize)
+ if ((inbuflen & c->blockmask)
&& !(inbuflen > c->cipher->blocksize
&& (c->flags & GCRY_CIPHER_CBC_CTS)))
return GPG_ERR_INV_LENGTH;
@@ -129,7 +129,7 @@ _gcry_cipher_cbc_decrypt (gcry_cipher_hd_t c,
if ((c->flags & GCRY_CIPHER_CBC_CTS) && inbuflen > blocksize)
{
nblocks--;
- if ((inbuflen % blocksize) == 0)
+ if ((inbuflen & c->blockmask) == 0)
nblocks--;
memcpy (c->lastiv, c->u_iv.iv, blocksize);
}
@@ -137,8 +137,8 @@ _gcry_cipher_cbc_decrypt (gcry_cipher_hd_t c,
if (c->bulk.cbc_dec)
{
c->bulk.cbc_dec (&c->context.c, c->u_iv.iv, outbuf, inbuf, nblocks);
- inbuf += nblocks * blocksize;
- outbuf += nblocks * blocksize;
+ inbuf += nblocks << c->blockshift;
+ outbuf += nblocks << c->blockshift;
}
else
{
@@ -160,10 +160,10 @@ _gcry_cipher_cbc_decrypt (gcry_cipher_hd_t c,
{
int restbytes;
- if ((inbuflen % blocksize) == 0)
+ if ((inbuflen & c->blockmask) == 0)
restbytes = blocksize;
else
- restbytes = inbuflen % blocksize;
+ restbytes = inbuflen & c->blockmask;
memcpy (c->lastiv, c->u_iv.iv, blocksize ); /* Save Cn-2. */
memcpy (c->u_iv.iv, inbuf + blocksize, restbytes ); /* Save Cn. */
diff --git a/cipher/cipher-cfb.c b/cipher/cipher-cfb.c
index ed84b75..7da80fc 100644
--- a/cipher/cipher-cfb.c
+++ b/cipher/cipher-cfb.c
@@ -69,11 +69,11 @@ _gcry_cipher_cfb_encrypt (gcry_cipher_hd_t c,
also allows to use a bulk encryption function if available. */
if (inbuflen >= blocksize_x_2 && c->bulk.cfb_enc)
{
- unsigned int nblocks = inbuflen / blocksize;
+ unsigned int nblocks = inbuflen >> c->blockshift;
c->bulk.cfb_enc (&c->context.c, c->u_iv.iv, outbuf, inbuf, nblocks);
- outbuf += nblocks * blocksize;
- inbuf += nblocks * blocksize;
- inbuflen -= nblocks * blocksize;
+ outbuf += nblocks << c->blockshift;
+ inbuf += nblocks << c->blockshift;
+ inbuflen -= nblocks << c->blockshift;
}
else
{
@@ -155,11 +155,11 @@ _gcry_cipher_cfb_decrypt (gcry_cipher_hd_t c,
also allows to use a bulk encryption function if available. */
if (inbuflen >= blocksize_x_2 && c->bulk.cfb_dec)
{
- unsigned int nblocks = inbuflen / blocksize;
+ unsigned int nblocks = inbuflen >> c->blockshift;
c->bulk.cfb_dec (&c->context.c, c->u_iv.iv, outbuf, inbuf, nblocks);
- outbuf += nblocks * blocksize;
- inbuf += nblocks * blocksize;
- inbuflen -= nblocks * blocksize;
+ outbuf += nblocks << c->blockshift;
+ inbuf += nblocks << c->blockshift;
+ inbuflen -= nblocks << c->blockshift;
}
else
{
diff --git a/cipher/cipher-ctr.c b/cipher/cipher-ctr.c
index 6bc6ffc..96ec7a6 100644
--- a/cipher/cipher-ctr.c
+++ b/cipher/cipher-ctr.c
@@ -59,13 +59,13 @@ _gcry_cipher_ctr_encrypt (gcry_cipher_hd_t c,
/* Use a bulk method if available. */
- nblocks = inbuflen / blocksize;
+ nblocks = inbuflen >> c->blockshift;
if (nblocks && c->bulk.ctr_enc)
{
c->bulk.ctr_enc (&c->context.c, c->u_ctr.ctr, outbuf, inbuf, nblocks);
- inbuf += nblocks * blocksize;
- outbuf += nblocks * blocksize;
- inbuflen -= nblocks * blocksize;
+ inbuf += nblocks << c->blockshift;
+ outbuf += nblocks << c->blockshift;
+ inbuflen -= nblocks << c->blockshift;
}
/* If we don't have a bulk method use the standard method. We also
diff --git a/cipher/cipher-internal.h b/cipher/cipher-internal.h
index 025bf2e..b9f77c3 100644
--- a/cipher/cipher-internal.h
+++ b/cipher/cipher-internal.h
@@ -68,6 +68,11 @@ struct gcry_cipher_handle
interface does not easily allow to retrieve this value. */
int algo;
+ /* To avoid slow integer multiplications and divisions, use precalculated
+ blocksize shift and mask. */
+ unsigned int blockshift;
+ unsigned int blockmask;
+
/* A structure with function pointers for bulk operations. Due to
limitations of the module system (we don't want to change the
API) we need to keep these function pointers here. The cipher
diff --git a/cipher/cipher.c b/cipher/cipher.c
index 389bf7a..b9e5841 100644
--- a/cipher/cipher.c
+++ b/cipher/cipher.c
@@ -704,6 +704,11 @@ gcry_cipher_open (gcry_cipher_hd_t *handle,
h->mode = mode;
h->flags = flags;
+ /* Blocksize should be power of two. */
+ gcry_assert((cipher->blocksize & (cipher->blocksize - 1)) == 0);
+ h->blockshift = ffs(cipher->blocksize) - 1;
+ h->blockmask = cipher->blocksize - 1;
+
/* Setup bulk encryption routines. */
switch (algo)
{
@@ -853,10 +858,10 @@ do_ecb_encrypt (gcry_cipher_hd_t c,
if (outbuflen < inbuflen)
return GPG_ERR_BUFFER_TOO_SHORT;
- if ((inbuflen % blocksize))
+ if ((inbuflen & c->blockmask))
return GPG_ERR_INV_LENGTH;
- nblocks = inbuflen / c->cipher->blocksize;
+ nblocks = inbuflen >> c->blockshift;
for (n=0; n < nblocks; n++ )
{
@@ -877,9 +882,10 @@ do_ecb_decrypt (gcry_cipher_hd_t c,
if (outbuflen < inbuflen)
return GPG_ERR_BUFFER_TOO_SHORT;
- if ((inbuflen % blocksize))
+ if ((inbuflen & c->blockmask))
return GPG_ERR_INV_LENGTH;
- nblocks = inbuflen / c->cipher->blocksize;
+
+ nblocks = inbuflen >> c->blockshift;
for (n=0; n < nblocks; n++ )
{
diff --git a/configure.ac b/configure.ac
index a2235a8..78e0a0f 100644
--- a/configure.ac
+++ b/configure.ac
@@ -810,7 +810,7 @@ fi
AC_FUNC_VPRINTF
# We have replacements for these in src/missing-string.c
-AC_CHECK_FUNCS(stpcpy strcasecmp)
+AC_CHECK_FUNCS(stpcpy strcasecmp ffs)
# We have replacements for these in src/g10lib.h
AC_CHECK_FUNCS(strtoul memmove stricmp atexit raise)
# Other checks
diff --git a/src/g10lib.h b/src/g10lib.h
index f1af399..81c3050 100644
--- a/src/g10lib.h
+++ b/src/g10lib.h
@@ -206,6 +206,9 @@ char *stpcpy (char *a, const char *b);
#ifndef HAVE_STRCASECMP
int strcasecmp (const char *a, const char *b) _GCRY_GCC_ATTR_PURE;
#endif
+#ifndef HAVE_FFS
+int ffs(int val) _GCRY_GCC_ATTR_PURE;
+#endif
#include "../compat/libcompat.h"
diff --git a/src/missing-string.c b/src/missing-string.c
index 4756c00..9196fa3 100644
--- a/src/missing-string.c
+++ b/src/missing-string.c
@@ -52,3 +52,24 @@ strcasecmp( const char *a, const char *b )
return *(const byte*)a - *(const byte*)b;
}
#endif
+
+
+#ifndef HAVE_FFS
+/* Find first set bit */
+int
+ffs(int val)
+{
+ unsigned int bits = val;
+ int i;
+
+ for (i = 0; i < sizeof(bits) * 8; i++)
+ {
+ if (bits & 1)
+ return i + 1;
+
+ bits >>= 1;
+ }
+
+ return 0;
+}
+#endif
More information about the Gcrypt-devel
mailing list