Branch data     Line data    Source code

       1                 :            : /* mpicoder.c  -  Coder for the external representation of MPIs
       2                 :            :  * Copyright (C) 1998, 1999 Free Software Foundation, Inc.
       3                 :            :  *
       4                 :            :  * This file is part of GnuPG.
       5                 :            :  *
       6                 :            :  * GnuPG is free software; you can redistribute it and/or modify
       7                 :            :  * it under the terms of the GNU General Public License as published by
       8                 :            :  * the Free Software Foundation; either version 2 of the License, or
       9                 :            :  * (at your option) any later version.
      10                 :            :  *
      11                 :            :  * GnuPG is distributed in the hope that it will be useful,
      12                 :            :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      13                 :            :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      14                 :            :  * GNU General Public License for more details.
      15                 :            :  *
      16                 :            :  * You should have received a copy of the GNU General Public License
      17                 :            :  * along with this program; if not, write to the Free Software
      18                 :            :  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
      19                 :            :  */
      20                 :            : 
      21                 :            : #include <linux/bitops.h>
      22                 :            : #include <linux/count_zeros.h>
      23                 :            : #include <linux/byteorder/generic.h>
      24                 :            : #include <linux/scatterlist.h>
      25                 :            : #include <linux/string.h>
      26                 :            : #include "mpi-internal.h"
      27                 :            : 
      28                 :            : #define MAX_EXTERN_MPI_BITS 16384
      29                 :            : 
      30                 :            : /**
      31                 :            :  * mpi_read_raw_data - Read a raw byte stream as a positive integer
      32                 :            :  * @xbuffer: The data to read
      33                 :            :  * @nbytes: The amount of data to read
      34                 :            :  */
      35                 :          3 : MPI mpi_read_raw_data(const void *xbuffer, size_t nbytes)
      36                 :            : {
      37                 :            :         const uint8_t *buffer = xbuffer;
      38                 :            :         int i, j;
      39                 :            :         unsigned nbits, nlimbs;
      40                 :            :         mpi_limb_t a;
      41                 :            :         MPI val = NULL;
      42                 :            : 
      43                 :          3 :         while (nbytes > 0 && buffer[0] == 0) {
      44                 :          3 :                 buffer++;
      45                 :          3 :                 nbytes--;
      46                 :            :         }
      47                 :            : 
      48                 :          3 :         nbits = nbytes * 8;
      49                 :          3 :         if (nbits > MAX_EXTERN_MPI_BITS) {
      50                 :          0 :                 pr_info("MPI: mpi too large (%u bits)\n", nbits);
      51                 :          0 :                 return NULL;
      52                 :            :         }
      53                 :          3 :         if (nbytes > 0)
      54                 :          3 :                 nbits -= count_leading_zeros(buffer[0]) - (BITS_PER_LONG - 8);
      55                 :            : 
      56                 :          3 :         nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB);
      57                 :          3 :         val = mpi_alloc(nlimbs);
      58                 :          3 :         if (!val)
      59                 :            :                 return NULL;
      60                 :          3 :         val->nbits = nbits;
      61                 :          3 :         val->sign = 0;
      62                 :          3 :         val->nlimbs = nlimbs;
      63                 :            : 
      64                 :          3 :         if (nbytes > 0) {
      65                 :          3 :                 i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
      66                 :          3 :                 i %= BYTES_PER_MPI_LIMB;
      67                 :          3 :                 for (j = nlimbs; j > 0; j--) {
      68                 :            :                         a = 0;
      69                 :          3 :                         for (; i < BYTES_PER_MPI_LIMB; i++) {
      70                 :          3 :                                 a <<= 8;
      71                 :          3 :                                 a |= *buffer++;
      72                 :            :                         }
      73                 :            :                         i = 0;
      74                 :          3 :                         val->d[j - 1] = a;
      75                 :            :                 }
      76                 :            :         }
      77                 :          3 :         return val;
      78                 :            : }
      79                 :            : EXPORT_SYMBOL_GPL(mpi_read_raw_data);
      80                 :            : 
      81                 :          0 : MPI mpi_read_from_buffer(const void *xbuffer, unsigned *ret_nread)
      82                 :            : {
      83                 :            :         const uint8_t *buffer = xbuffer;
      84                 :            :         unsigned int nbits, nbytes;
      85                 :            :         MPI val;
      86                 :            : 
      87                 :          0 :         if (*ret_nread < 2)
      88                 :            :                 return ERR_PTR(-EINVAL);
      89                 :          0 :         nbits = buffer[0] << 8 | buffer[1];
      90                 :            : 
      91                 :          0 :         if (nbits > MAX_EXTERN_MPI_BITS) {
      92                 :          0 :                 pr_info("MPI: mpi too large (%u bits)\n", nbits);
      93                 :          0 :                 return ERR_PTR(-EINVAL);
      94                 :            :         }
      95                 :            : 
      96                 :          0 :         nbytes = DIV_ROUND_UP(nbits, 8);
      97                 :          0 :         if (nbytes + 2 > *ret_nread) {
      98                 :          0 :                 pr_info("MPI: mpi larger than buffer nbytes=%u ret_nread=%u\n",
      99                 :            :                                 nbytes, *ret_nread);
     100                 :          0 :                 return ERR_PTR(-EINVAL);
     101                 :            :         }
     102                 :            : 
     103                 :          0 :         val = mpi_read_raw_data(buffer + 2, nbytes);
     104                 :          0 :         if (!val)
     105                 :            :                 return ERR_PTR(-ENOMEM);
     106                 :            : 
     107                 :          0 :         *ret_nread = nbytes + 2;
     108                 :          0 :         return val;
     109                 :            : }
     110                 :            : EXPORT_SYMBOL_GPL(mpi_read_from_buffer);
     111                 :            : 
     112                 :          0 : static int count_lzeros(MPI a)
     113                 :            : {
     114                 :            :         mpi_limb_t alimb;
     115                 :            :         int i, lzeros = 0;
     116                 :            : 
     117                 :          0 :         for (i = a->nlimbs - 1; i >= 0; i--) {
     118                 :          0 :                 alimb = a->d[i];
     119                 :          0 :                 if (alimb == 0) {
     120                 :          0 :                         lzeros += sizeof(mpi_limb_t);
     121                 :            :                 } else {
     122                 :          0 :                         lzeros += count_leading_zeros(alimb) / 8;
     123                 :          0 :                         break;
     124                 :            :                 }
     125                 :            :         }
     126                 :          0 :         return lzeros;
     127                 :            : }
     128                 :            : 
     129                 :            : /**
     130                 :            :  * mpi_read_buffer() - read MPI to a bufer provided by user (msb first)
     131                 :            :  *
     132                 :            :  * @a:          a multi precision integer
     133                 :            :  * @buf:        bufer to which the output will be written to. Needs to be at
     134                 :            :  *              leaset mpi_get_size(a) long.
     135                 :            :  * @buf_len:    size of the buf.
     136                 :            :  * @nbytes:     receives the actual length of the data written on success and
     137                 :            :  *              the data to-be-written on -EOVERFLOW in case buf_len was too
     138                 :            :  *              small.
     139                 :            :  * @sign:       if not NULL, it will be set to the sign of a.
     140                 :            :  *
     141                 :            :  * Return:      0 on success or error code in case of error
     142                 :            :  */
     143                 :          0 : int mpi_read_buffer(MPI a, uint8_t *buf, unsigned buf_len, unsigned *nbytes,
     144                 :            :                     int *sign)
     145                 :            : {
     146                 :            :         uint8_t *p;
     147                 :            : #if BYTES_PER_MPI_LIMB == 4
     148                 :            :         __be32 alimb;
     149                 :            : #elif BYTES_PER_MPI_LIMB == 8
     150                 :            :         __be64 alimb;
     151                 :            : #else
     152                 :            : #error please implement for this limb size.
     153                 :            : #endif
     154                 :            :         unsigned int n = mpi_get_size(a);
     155                 :            :         int i, lzeros;
     156                 :            : 
     157                 :          0 :         if (!buf || !nbytes)
     158                 :            :                 return -EINVAL;
     159                 :            : 
     160                 :          0 :         if (sign)
     161                 :          0 :                 *sign = a->sign;
     162                 :            : 
     163                 :          0 :         lzeros = count_lzeros(a);
     164                 :            : 
     165                 :          0 :         if (buf_len < n - lzeros) {
     166                 :          0 :                 *nbytes = n - lzeros;
     167                 :          0 :                 return -EOVERFLOW;
     168                 :            :         }
     169                 :            : 
     170                 :            :         p = buf;
     171                 :          0 :         *nbytes = n - lzeros;
     172                 :            : 
     173                 :          0 :         for (i = a->nlimbs - 1 - lzeros / BYTES_PER_MPI_LIMB,
     174                 :          0 :                         lzeros %= BYTES_PER_MPI_LIMB;
     175                 :          0 :                 i >= 0; i--) {
     176                 :            : #if BYTES_PER_MPI_LIMB == 4
     177                 :          0 :                 alimb = cpu_to_be32(a->d[i]);
     178                 :            : #elif BYTES_PER_MPI_LIMB == 8
     179                 :            :                 alimb = cpu_to_be64(a->d[i]);
     180                 :            : #else
     181                 :            : #error please implement for this limb size.
     182                 :            : #endif
     183                 :          0 :                 memcpy(p, (u8 *)&alimb + lzeros, BYTES_PER_MPI_LIMB - lzeros);
     184                 :          0 :                 p += BYTES_PER_MPI_LIMB - lzeros;
     185                 :            :                 lzeros = 0;
     186                 :            :         }
     187                 :            :         return 0;
     188                 :            : }
     189                 :            : EXPORT_SYMBOL_GPL(mpi_read_buffer);
     190                 :            : 
     191                 :            : /*
     192                 :            :  * mpi_get_buffer() - Returns an allocated buffer with the MPI (msb first).
     193                 :            :  * Caller must free the return string.
     194                 :            :  * This function does return a 0 byte buffer with nbytes set to zero if the
     195                 :            :  * value of A is zero.
     196                 :            :  *
     197                 :            :  * @a:          a multi precision integer.
     198                 :            :  * @nbytes:     receives the length of this buffer.
     199                 :            :  * @sign:       if not NULL, it will be set to the sign of the a.
     200                 :            :  *
     201                 :            :  * Return:      Pointer to MPI buffer or NULL on error
     202                 :            :  */
     203                 :          0 : void *mpi_get_buffer(MPI a, unsigned *nbytes, int *sign)
     204                 :            : {
     205                 :            :         uint8_t *buf;
     206                 :            :         unsigned int n;
     207                 :            :         int ret;
     208                 :            : 
     209                 :          0 :         if (!nbytes)
     210                 :            :                 return NULL;
     211                 :            : 
     212                 :            :         n = mpi_get_size(a);
     213                 :            : 
     214                 :          0 :         if (!n)
     215                 :          0 :                 n++;
     216                 :            : 
     217                 :            :         buf = kmalloc(n, GFP_KERNEL);
     218                 :            : 
     219                 :          0 :         if (!buf)
     220                 :            :                 return NULL;
     221                 :            : 
     222                 :          0 :         ret = mpi_read_buffer(a, buf, n, nbytes, sign);
     223                 :            : 
     224                 :          0 :         if (ret) {
     225                 :          0 :                 kfree(buf);
     226                 :          0 :                 return NULL;
     227                 :            :         }
     228                 :            :         return buf;
     229                 :            : }
     230                 :            : EXPORT_SYMBOL_GPL(mpi_get_buffer);
     231                 :            : 
     232                 :            : /**
     233                 :            :  * mpi_write_to_sgl() - Funnction exports MPI to an sgl (msb first)
     234                 :            :  *
     235                 :            :  * This function works in the same way as the mpi_read_buffer, but it
     236                 :            :  * takes an sgl instead of u8 * buf.
     237                 :            :  *
     238                 :            :  * @a:          a multi precision integer
     239                 :            :  * @sgl:        scatterlist to write to. Needs to be at least
     240                 :            :  *              mpi_get_size(a) long.
     241                 :            :  * @nbytes:     the number of bytes to write.  Leading bytes will be
     242                 :            :  *              filled with zero.
     243                 :            :  * @sign:       if not NULL, it will be set to the sign of a.
     244                 :            :  *
     245                 :            :  * Return:      0 on success or error code in case of error
     246                 :            :  */
     247                 :          3 : int mpi_write_to_sgl(MPI a, struct scatterlist *sgl, unsigned nbytes,
     248                 :            :                      int *sign)
     249                 :            : {
     250                 :            :         u8 *p, *p2;
     251                 :            : #if BYTES_PER_MPI_LIMB == 4
     252                 :            :         __be32 alimb;
     253                 :            : #elif BYTES_PER_MPI_LIMB == 8
     254                 :            :         __be64 alimb;
     255                 :            : #else
     256                 :            : #error please implement for this limb size.
     257                 :            : #endif
     258                 :            :         unsigned int n = mpi_get_size(a);
     259                 :            :         struct sg_mapping_iter miter;
     260                 :            :         int i, x, buf_len;
     261                 :            :         int nents;
     262                 :            : 
     263                 :          3 :         if (sign)
     264                 :          3 :                 *sign = a->sign;
     265                 :            : 
     266                 :          3 :         if (nbytes < n)
     267                 :            :                 return -EOVERFLOW;
     268                 :            : 
     269                 :          3 :         nents = sg_nents_for_len(sgl, nbytes);
     270                 :          3 :         if (nents < 0)
     271                 :            :                 return -EINVAL;
     272                 :            : 
     273                 :          3 :         sg_miter_start(&miter, sgl, nents, SG_MITER_ATOMIC | SG_MITER_TO_SG);
     274                 :          3 :         sg_miter_next(&miter);
     275                 :          3 :         buf_len = miter.length;
     276                 :          3 :         p2 = miter.addr;
     277                 :            : 
     278                 :          3 :         while (nbytes > n) {
     279                 :          0 :                 i = min_t(unsigned, nbytes - n, buf_len);
     280                 :          0 :                 memset(p2, 0, i);
     281                 :          0 :                 p2 += i;
     282                 :          0 :                 nbytes -= i;
     283                 :            : 
     284                 :          0 :                 buf_len -= i;
     285                 :          0 :                 if (!buf_len) {
     286                 :          0 :                         sg_miter_next(&miter);
     287                 :          0 :                         buf_len = miter.length;
     288                 :          0 :                         p2 = miter.addr;
     289                 :            :                 }
     290                 :            :         }
     291                 :            : 
     292                 :          3 :         for (i = a->nlimbs - 1; i >= 0; i--) {
     293                 :            : #if BYTES_PER_MPI_LIMB == 4
     294                 :          3 :                 alimb = a->d[i] ? cpu_to_be32(a->d[i]) : 0;
     295                 :            : #elif BYTES_PER_MPI_LIMB == 8
     296                 :            :                 alimb = a->d[i] ? cpu_to_be64(a->d[i]) : 0;
     297                 :            : #else
     298                 :            : #error please implement for this limb size.
     299                 :            : #endif
     300                 :            :                 p = (u8 *)&alimb;
     301                 :            : 
     302                 :          3 :                 for (x = 0; x < sizeof(alimb); x++) {
     303                 :          3 :                         *p2++ = *p++;
     304                 :          3 :                         if (!--buf_len) {
     305                 :          3 :                                 sg_miter_next(&miter);
     306                 :          3 :                                 buf_len = miter.length;
     307                 :          3 :                                 p2 = miter.addr;
     308                 :            :                         }
     309                 :            :                 }
     310                 :            :         }
     311                 :            : 
     312                 :          3 :         sg_miter_stop(&miter);
     313                 :          3 :         return 0;
     314                 :            : }
     315                 :            : EXPORT_SYMBOL_GPL(mpi_write_to_sgl);
     316                 :            : 
     317                 :            : /*
     318                 :            :  * mpi_read_raw_from_sgl() - Function allocates an MPI and populates it with
     319                 :            :  *                           data from the sgl
     320                 :            :  *
     321                 :            :  * This function works in the same way as the mpi_read_raw_data, but it
     322                 :            :  * takes an sgl instead of void * buffer. i.e. it allocates
     323                 :            :  * a new MPI and reads the content of the sgl to the MPI.
     324                 :            :  *
     325                 :            :  * @sgl:        scatterlist to read from
     326                 :            :  * @nbytes:     number of bytes to read
     327                 :            :  *
     328                 :            :  * Return:      Pointer to a new MPI or NULL on error
     329                 :            :  */
     330                 :          3 : MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int nbytes)
     331                 :            : {
     332                 :            :         struct sg_mapping_iter miter;
     333                 :            :         unsigned int nbits, nlimbs;
     334                 :            :         int x, j, z, lzeros, ents;
     335                 :            :         unsigned int len;
     336                 :            :         const u8 *buff;
     337                 :            :         mpi_limb_t a;
     338                 :            :         MPI val = NULL;
     339                 :            : 
     340                 :          3 :         ents = sg_nents_for_len(sgl, nbytes);
     341                 :          3 :         if (ents < 0)
     342                 :            :                 return NULL;
     343                 :            : 
     344                 :          3 :         sg_miter_start(&miter, sgl, ents, SG_MITER_ATOMIC | SG_MITER_FROM_SG);
     345                 :            : 
     346                 :            :         lzeros = 0;
     347                 :            :         len = 0;
     348                 :          3 :         while (nbytes > 0) {
     349                 :          3 :                 while (len && !*buff) {
     350                 :          0 :                         lzeros++;
     351                 :          0 :                         len--;
     352                 :          0 :                         buff++;
     353                 :            :                 }
     354                 :            : 
     355                 :          3 :                 if (len && *buff)
     356                 :            :                         break;
     357                 :            : 
     358                 :          3 :                 sg_miter_next(&miter);
     359                 :          3 :                 buff = miter.addr;
     360                 :          3 :                 len = miter.length;
     361                 :            : 
     362                 :          3 :                 nbytes -= lzeros;
     363                 :            :                 lzeros = 0;
     364                 :            :         }
     365                 :            : 
     366                 :          3 :         miter.consumed = lzeros;
     367                 :            : 
     368                 :          3 :         nbytes -= lzeros;
     369                 :          3 :         nbits = nbytes * 8;
     370                 :          3 :         if (nbits > MAX_EXTERN_MPI_BITS) {
     371                 :          0 :                 sg_miter_stop(&miter);
     372                 :          0 :                 pr_info("MPI: mpi too large (%u bits)\n", nbits);
     373                 :          0 :                 return NULL;
     374                 :            :         }
     375                 :            : 
     376                 :          3 :         if (nbytes > 0)
     377                 :          3 :                 nbits -= count_leading_zeros(*buff) - (BITS_PER_LONG - 8);
     378                 :            : 
     379                 :          3 :         sg_miter_stop(&miter);
     380                 :            : 
     381                 :          3 :         nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB);
     382                 :          3 :         val = mpi_alloc(nlimbs);
     383                 :          3 :         if (!val)
     384                 :            :                 return NULL;
     385                 :            : 
     386                 :          3 :         val->nbits = nbits;
     387                 :          3 :         val->sign = 0;
     388                 :          3 :         val->nlimbs = nlimbs;
     389                 :            : 
     390                 :          3 :         if (nbytes == 0)
     391                 :            :                 return val;
     392                 :            : 
     393                 :          3 :         j = nlimbs - 1;
     394                 :            :         a = 0;
     395                 :          3 :         z = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
     396                 :          3 :         z %= BYTES_PER_MPI_LIMB;
     397                 :            : 
     398                 :          3 :         while (sg_miter_next(&miter)) {
     399                 :          3 :                 buff = miter.addr;
     400                 :          3 :                 len = miter.length;
     401                 :            : 
     402                 :          3 :                 for (x = 0; x < len; x++) {
     403                 :          3 :                         a <<= 8;
     404                 :          3 :                         a |= *buff++;
     405                 :          3 :                         if (((z + x + 1) % BYTES_PER_MPI_LIMB) == 0) {
     406                 :          3 :                                 val->d[j--] = a;
     407                 :            :                                 a = 0;
     408                 :            :                         }
     409                 :            :                 }
     410                 :          3 :                 z += x;
     411                 :            :         }
     412                 :            : 
     413                 :            :         return val;
     414                 :            : }
     415                 :            : EXPORT_SYMBOL_GPL(mpi_read_raw_from_sgl);