From 2d4d1eea540b27c72488fd1914674c42473d53df Mon Sep 17 00:00:00 2001 From: Tadeusz Struk Date: Thu, 8 Oct 2015 09:26:50 -0700 Subject: lib/mpi: Add mpi sgl helpers Add mpi_read_raw_from_sgl and mpi_write_to_sgl helpers. Signed-off-by: Tadeusz Struk Signed-off-by: Herbert Xu --- lib/mpi/mpicoder.c | 196 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 196 insertions(+) (limited to 'lib/mpi/mpicoder.c') diff --git a/lib/mpi/mpicoder.c b/lib/mpi/mpicoder.c index 95c52a95259e..c20ef27ad876 100644 --- a/lib/mpi/mpicoder.c +++ b/lib/mpi/mpicoder.c @@ -319,3 +319,199 @@ int mpi_set_buffer(MPI a, const void *xbuffer, unsigned nbytes, int sign) return 0; } EXPORT_SYMBOL_GPL(mpi_set_buffer); + +/** + * mpi_write_to_sgl() - Funnction exports MPI to an sgl (msb first) + * + * This function works in the same way as the mpi_read_buffer, but it + * takes an sgl instead of u8 * buf. + * + * @a: a multi precision integer + * @sgl: scatterlist to write to. Needs to be at least + * mpi_get_size(a) long. + * @nbytes: in/out param - it has the be set to the maximum number of + * bytes that can be written to sgl. This has to be at least + * the size of the integer a. On return it receives the actual + * length of the data written. + * @sign: if not NULL, it will be set to the sign of a. + * + * Return: 0 on success or error code in case of error + */ +int mpi_write_to_sgl(MPI a, struct scatterlist *sgl, unsigned *nbytes, + int *sign) +{ + u8 *p, *p2; + mpi_limb_t alimb, alimb2; + unsigned int n = mpi_get_size(a); + int i, x, y = 0, lzeros = 0, buf_len; + + if (!nbytes || *nbytes < n) + return -EINVAL; + + if (sign) + *sign = a->sign; + + p = (void *)&a->d[a->nlimbs] - 1; + + for (i = a->nlimbs * sizeof(alimb) - 1; i >= 0; i--, p--) { + if (!*p) + lzeros++; + else + break; + } + + *nbytes = n - lzeros; + buf_len = sgl->length; + p2 = sg_virt(sgl); + + for (i = a->nlimbs - 1; i >= 0; i--) { + alimb = a->d[i]; + p = (u8 *)&alimb2; +#if BYTES_PER_MPI_LIMB == 4 + *p++ = alimb >> 24; + *p++ = alimb >> 16; + *p++ = alimb >> 8; + *p++ = alimb; +#elif BYTES_PER_MPI_LIMB == 8 + *p++ = alimb >> 56; + *p++ = alimb >> 48; + *p++ = alimb >> 40; + *p++ = alimb >> 32; + *p++ = alimb >> 24; + *p++ = alimb >> 16; + *p++ = alimb >> 8; + *p++ = alimb; +#else +#error please implement for this limb size. +#endif + if (lzeros > 0) { + if (lzeros >= sizeof(alimb)) { + p -= sizeof(alimb); + continue; + } else { + mpi_limb_t *limb1 = (void *)p - sizeof(alimb); + mpi_limb_t *limb2 = (void *)p - sizeof(alimb) + + lzeros; + *limb1 = *limb2; + p -= lzeros; + y = lzeros; + } + lzeros -= sizeof(alimb); + } + + p = p - (sizeof(alimb) - y); + + for (x = 0; x < sizeof(alimb) - y; x++) { + if (!buf_len) { + sgl = sg_next(sgl); + if (!sgl) + return -EINVAL; + buf_len = sgl->length; + p2 = sg_virt(sgl); + } + *p2++ = *p++; + buf_len--; + } + y = 0; + } + return 0; +} +EXPORT_SYMBOL_GPL(mpi_write_to_sgl); + +/* + * mpi_read_raw_from_sgl() - Function allocates an MPI and populates it with + * data from the sgl + * + * This function works in the same way as the mpi_read_raw_data, but it + * takes an sgl instead of void * buffer. i.e. it allocates + * a new MPI and reads the content of the sgl to the MPI. + * + * @sgl: scatterlist to read from + * @len: number of bytes to read + * + * Return: Pointer to a new MPI or NULL on error + */ +MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int len) +{ + struct scatterlist *sg; + int x, i, j, z, lzeros, ents; + unsigned int nbits, nlimbs, nbytes; + mpi_limb_t a; + MPI val = NULL; + + lzeros = 0; + ents = sg_nents(sgl); + + for_each_sg(sgl, sg, ents, i) { + const u8 *buff = sg_virt(sg); + int len = sg->length; + + while (len-- && !*buff++) + lzeros++; + + if (len && *buff) + break; + + ents--; + lzeros = 0; + } + + sgl = sg; + + if (!ents) + nbytes = 0; + else + nbytes = len - lzeros; + + nbits = nbytes * 8; + if (nbits > MAX_EXTERN_MPI_BITS) { + pr_info("MPI: mpi too large (%u bits)\n", nbits); + return NULL; + } + + if (nbytes > 0) + nbits -= count_leading_zeros(*(u8 *)(sg_virt(sgl) + lzeros)); + else + nbits = 0; + + nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB); + val = mpi_alloc(nlimbs); + if (!val) + return NULL; + + val->nbits = nbits; + val->sign = 0; + val->nlimbs = nlimbs; + + if (nbytes == 0) + return val; + + j = nlimbs - 1; + a = 0; + z = 0; + x = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB; + x %= BYTES_PER_MPI_LIMB; + + for_each_sg(sgl, sg, ents, i) { + const u8 *buffer = sg_virt(sg) + lzeros; + int len = sg->length - lzeros; + int buf_shift = x; + + if (sg_is_last(sg) && (len % BYTES_PER_MPI_LIMB)) + len += BYTES_PER_MPI_LIMB - (len % BYTES_PER_MPI_LIMB); + + for (; x < len + buf_shift; x++) { + a <<= 8; + a |= *buffer++; + if (((z + x + 1) % BYTES_PER_MPI_LIMB) == 0) { + val->d[j--] = a; + a = 0; + } + } + z += x; + x = 0; + lzeros = 0; + } + return val; +} +EXPORT_SYMBOL_GPL(mpi_read_raw_from_sgl); -- cgit From a1164a3ac75feeab86f6c02fabdfbf24b81e3c1a Mon Sep 17 00:00:00 2001 From: Christoph Hellwig Date: Fri, 28 Aug 2015 09:27:15 +0200 Subject: move count_zeroes.h out of asm-generic This header contains a few helpers currenly only used by the mpi implementation, and not default implementation of architecture code. Signed-off-by: Christoph Hellwig Signed-off-by: Arnd Bergmann --- include/asm-generic/bitops/count_zeros.h | 57 -------------------------------- include/linux/count_zeros.h | 57 ++++++++++++++++++++++++++++++++ lib/mpi/longlong.h | 2 +- lib/mpi/mpicoder.c | 2 +- 4 files changed, 59 insertions(+), 59 deletions(-) delete mode 100644 include/asm-generic/bitops/count_zeros.h create mode 100644 include/linux/count_zeros.h (limited to 'lib/mpi/mpicoder.c') diff --git a/include/asm-generic/bitops/count_zeros.h b/include/asm-generic/bitops/count_zeros.h deleted file mode 100644 index 97520d21fe62..000000000000 --- a/include/asm-generic/bitops/count_zeros.h +++ /dev/null @@ -1,57 +0,0 @@ -/* Count leading and trailing zeros functions - * - * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved. - * Written by David Howells (dhowells@redhat.com) - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public Licence - * as published by the Free Software Foundation; either version - * 2 of the Licence, or (at your option) any later version. - */ - -#ifndef _ASM_GENERIC_BITOPS_COUNT_ZEROS_H_ -#define _ASM_GENERIC_BITOPS_COUNT_ZEROS_H_ - -#include - -/** - * count_leading_zeros - Count the number of zeros from the MSB back - * @x: The value - * - * Count the number of leading zeros from the MSB going towards the LSB in @x. - * - * If the MSB of @x is set, the result is 0. - * If only the LSB of @x is set, then the result is BITS_PER_LONG-1. - * If @x is 0 then the result is COUNT_LEADING_ZEROS_0. - */ -static inline int count_leading_zeros(unsigned long x) -{ - if (sizeof(x) == 4) - return BITS_PER_LONG - fls(x); - else - return BITS_PER_LONG - fls64(x); -} - -#define COUNT_LEADING_ZEROS_0 BITS_PER_LONG - -/** - * count_trailing_zeros - Count the number of zeros from the LSB forwards - * @x: The value - * - * Count the number of trailing zeros from the LSB going towards the MSB in @x. - * - * If the LSB of @x is set, the result is 0. - * If only the MSB of @x is set, then the result is BITS_PER_LONG-1. - * If @x is 0 then the result is COUNT_TRAILING_ZEROS_0. - */ -static inline int count_trailing_zeros(unsigned long x) -{ -#define COUNT_TRAILING_ZEROS_0 (-1) - - if (sizeof(x) == 4) - return ffs(x); - else - return (x != 0) ? __ffs(x) : COUNT_TRAILING_ZEROS_0; -} - -#endif /* _ASM_GENERIC_BITOPS_COUNT_ZEROS_H_ */ diff --git a/include/linux/count_zeros.h b/include/linux/count_zeros.h new file mode 100644 index 000000000000..363da78c4f64 --- /dev/null +++ b/include/linux/count_zeros.h @@ -0,0 +1,57 @@ +/* Count leading and trailing zeros functions + * + * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved. + * Written by David Howells (dhowells@redhat.com) + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public Licence + * as published by the Free Software Foundation; either version + * 2 of the Licence, or (at your option) any later version. + */ + +#ifndef _LINUX_BITOPS_COUNT_ZEROS_H_ +#define _LINUX_BITOPS_COUNT_ZEROS_H_ + +#include + +/** + * count_leading_zeros - Count the number of zeros from the MSB back + * @x: The value + * + * Count the number of leading zeros from the MSB going towards the LSB in @x. + * + * If the MSB of @x is set, the result is 0. + * If only the LSB of @x is set, then the result is BITS_PER_LONG-1. + * If @x is 0 then the result is COUNT_LEADING_ZEROS_0. + */ +static inline int count_leading_zeros(unsigned long x) +{ + if (sizeof(x) == 4) + return BITS_PER_LONG - fls(x); + else + return BITS_PER_LONG - fls64(x); +} + +#define COUNT_LEADING_ZEROS_0 BITS_PER_LONG + +/** + * count_trailing_zeros - Count the number of zeros from the LSB forwards + * @x: The value + * + * Count the number of trailing zeros from the LSB going towards the MSB in @x. + * + * If the LSB of @x is set, the result is 0. + * If only the MSB of @x is set, then the result is BITS_PER_LONG-1. + * If @x is 0 then the result is COUNT_TRAILING_ZEROS_0. + */ +static inline int count_trailing_zeros(unsigned long x) +{ +#define COUNT_TRAILING_ZEROS_0 (-1) + + if (sizeof(x) == 4) + return ffs(x); + else + return (x != 0) ? __ffs(x) : COUNT_TRAILING_ZEROS_0; +} + +#endif /* _LINUX_BITOPS_COUNT_ZEROS_H_ */ diff --git a/lib/mpi/longlong.h b/lib/mpi/longlong.h index a89d041592c8..b90e255c2a68 100644 --- a/lib/mpi/longlong.h +++ b/lib/mpi/longlong.h @@ -19,7 +19,7 @@ * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, * MA 02111-1307, USA. */ -#include +#include /* You have to define the following before including this file: * diff --git a/lib/mpi/mpicoder.c b/lib/mpi/mpicoder.c index 95c52a95259e..d30549fcc506 100644 --- a/lib/mpi/mpicoder.c +++ b/lib/mpi/mpicoder.c @@ -19,7 +19,7 @@ */ #include -#include +#include #include "mpi-internal.h" #define MAX_EXTERN_MPI_BITS 16384 -- cgit From 63349d02c195030f97c9c2000bbf32539056316f Mon Sep 17 00:00:00 2001 From: Stephan Mueller Date: Sun, 18 Oct 2015 12:45:18 +0200 Subject: lib/mpi: fix off by one in mpi_read_raw_from_sgl The patch fixes the analysis of the input data which contains an off by one. The issue is visible when the SGL contains one byte per SG entry. The code for checking for zero bytes does not operate on the data byte. Signed-off-by: Stephan Mueller Signed-off-by: Herbert Xu --- lib/mpi/mpicoder.c | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'lib/mpi/mpicoder.c') diff --git a/lib/mpi/mpicoder.c b/lib/mpi/mpicoder.c index c20ef27ad876..c7e0a705eecf 100644 --- a/lib/mpi/mpicoder.c +++ b/lib/mpi/mpicoder.c @@ -446,8 +446,11 @@ MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int len) const u8 *buff = sg_virt(sg); int len = sg->length; - while (len-- && !*buff++) + while (len && !*buff) { lzeros++; + len--; + buff++; + } if (len && *buff) break; -- cgit