417 lines · c
1/* mpicoder.c - Coder for the external representation of MPIs2 * 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 modify7 * it under the terms of the GNU General Public License as published by8 * the Free Software Foundation; either version 2 of the License, or9 * (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 of13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the14 * GNU General Public License for more details.15 *16 * You should have received a copy of the GNU General Public License17 * along with this program; if not, write to the Free Software18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA19 */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 1638429 30/**31 * mpi_read_raw_data - Read a raw byte stream as a positive integer32 * @xbuffer: The data to read33 * @nbytes: The amount of data to read34 */35MPI 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 while (nbytes > 0 && buffer[0] == 0) {44 buffer++;45 nbytes--;46 }47 48 nbits = nbytes * 8;49 if (nbits > MAX_EXTERN_MPI_BITS) {50 pr_info("MPI: mpi too large (%u bits)\n", nbits);51 return NULL;52 }53 if (nbytes > 0)54 nbits -= count_leading_zeros(buffer[0]) - (BITS_PER_LONG - 8);55 56 nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB);57 val = mpi_alloc(nlimbs);58 if (!val)59 return NULL;60 val->nbits = nbits;61 val->sign = 0;62 val->nlimbs = nlimbs;63 64 if (nbytes > 0) {65 i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;66 i %= BYTES_PER_MPI_LIMB;67 for (j = nlimbs; j > 0; j--) {68 a = 0;69 for (; i < BYTES_PER_MPI_LIMB; i++) {70 a <<= 8;71 a |= *buffer++;72 }73 i = 0;74 val->d[j - 1] = a;75 }76 }77 return val;78}79EXPORT_SYMBOL_GPL(mpi_read_raw_data);80 81MPI 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 if (*ret_nread < 2)88 return ERR_PTR(-EINVAL);89 nbits = buffer[0] << 8 | buffer[1];90 91 if (nbits > MAX_EXTERN_MPI_BITS) {92 pr_info("MPI: mpi too large (%u bits)\n", nbits);93 return ERR_PTR(-EINVAL);94 }95 96 nbytes = DIV_ROUND_UP(nbits, 8);97 if (nbytes + 2 > *ret_nread) {98 pr_info("MPI: mpi larger than buffer nbytes=%u ret_nread=%u\n",99 nbytes, *ret_nread);100 return ERR_PTR(-EINVAL);101 }102 103 val = mpi_read_raw_data(buffer + 2, nbytes);104 if (!val)105 return ERR_PTR(-ENOMEM);106 107 *ret_nread = nbytes + 2;108 return val;109}110EXPORT_SYMBOL_GPL(mpi_read_from_buffer);111 112static int count_lzeros(MPI a)113{114 mpi_limb_t alimb;115 int i, lzeros = 0;116 117 for (i = a->nlimbs - 1; i >= 0; i--) {118 alimb = a->d[i];119 if (alimb == 0) {120 lzeros += sizeof(mpi_limb_t);121 } else {122 lzeros += count_leading_zeros(alimb) / 8;123 break;124 }125 }126 return lzeros;127}128 129/**130 * mpi_read_buffer() - read MPI to a buffer provided by user (msb first)131 *132 * @a: a multi precision integer133 * @buf: buffer to which the output will be written to. Needs to be at134 * least mpi_get_size(a) long.135 * @buf_len: size of the buf.136 * @nbytes: receives the actual length of the data written on success and137 * the data to-be-written on -EOVERFLOW in case buf_len was too138 * 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 error142 */143int 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 == 4148 __be32 alimb;149#elif BYTES_PER_MPI_LIMB == 8150 __be64 alimb;151#else152#error please implement for this limb size.153#endif154 unsigned int n = mpi_get_size(a);155 int i, lzeros;156 157 if (!buf || !nbytes)158 return -EINVAL;159 160 if (sign)161 *sign = a->sign;162 163 lzeros = count_lzeros(a);164 165 if (buf_len < n - lzeros) {166 *nbytes = n - lzeros;167 return -EOVERFLOW;168 }169 170 p = buf;171 *nbytes = n - lzeros;172 173 for (i = a->nlimbs - 1 - lzeros / BYTES_PER_MPI_LIMB,174 lzeros %= BYTES_PER_MPI_LIMB;175 i >= 0; i--) {176#if BYTES_PER_MPI_LIMB == 4177 alimb = cpu_to_be32(a->d[i]);178#elif BYTES_PER_MPI_LIMB == 8179 alimb = cpu_to_be64(a->d[i]);180#else181#error please implement for this limb size.182#endif183 memcpy(p, (u8 *)&alimb + lzeros, BYTES_PER_MPI_LIMB - lzeros);184 p += BYTES_PER_MPI_LIMB - lzeros;185 lzeros = 0;186 }187 return 0;188}189EXPORT_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 the195 * 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 error202 */203void *mpi_get_buffer(MPI a, unsigned *nbytes, int *sign)204{205 uint8_t *buf;206 unsigned int n;207 int ret;208 209 if (!nbytes)210 return NULL;211 212 n = mpi_get_size(a);213 214 if (!n)215 n++;216 217 buf = kmalloc(n, GFP_KERNEL);218 219 if (!buf)220 return NULL;221 222 ret = mpi_read_buffer(a, buf, n, nbytes, sign);223 224 if (ret) {225 kfree(buf);226 return NULL;227 }228 return buf;229}230EXPORT_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 it236 * takes an sgl instead of u8 * buf.237 *238 * @a: a multi precision integer239 * @sgl: scatterlist to write to. Needs to be at least240 * mpi_get_size(a) long.241 * @nbytes: the number of bytes to write. Leading bytes will be242 * 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 error246 */247int 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 == 4252 __be32 alimb;253#elif BYTES_PER_MPI_LIMB == 8254 __be64 alimb;255#else256#error please implement for this limb size.257#endif258 unsigned int n = mpi_get_size(a);259 struct sg_mapping_iter miter;260 int i, x, buf_len;261 int nents;262 263 if (sign)264 *sign = a->sign;265 266 if (nbytes < n)267 return -EOVERFLOW;268 269 nents = sg_nents_for_len(sgl, nbytes);270 if (nents < 0)271 return -EINVAL;272 273 sg_miter_start(&miter, sgl, nents, SG_MITER_ATOMIC | SG_MITER_TO_SG);274 sg_miter_next(&miter);275 buf_len = miter.length;276 p2 = miter.addr;277 278 while (nbytes > n) {279 i = min_t(unsigned, nbytes - n, buf_len);280 memset(p2, 0, i);281 p2 += i;282 nbytes -= i;283 284 buf_len -= i;285 if (!buf_len) {286 sg_miter_next(&miter);287 buf_len = miter.length;288 p2 = miter.addr;289 }290 }291 292 for (i = a->nlimbs - 1; i >= 0; i--) {293#if BYTES_PER_MPI_LIMB == 4294 alimb = a->d[i] ? cpu_to_be32(a->d[i]) : 0;295#elif BYTES_PER_MPI_LIMB == 8296 alimb = a->d[i] ? cpu_to_be64(a->d[i]) : 0;297#else298#error please implement for this limb size.299#endif300 p = (u8 *)&alimb;301 302 for (x = 0; x < sizeof(alimb); x++) {303 *p2++ = *p++;304 if (!--buf_len) {305 sg_miter_next(&miter);306 buf_len = miter.length;307 p2 = miter.addr;308 }309 }310 }311 312 sg_miter_stop(&miter);313 return 0;314}315EXPORT_SYMBOL_GPL(mpi_write_to_sgl);316 317/*318 * mpi_read_raw_from_sgl() - Function allocates an MPI and populates it with319 * data from the sgl320 *321 * This function works in the same way as the mpi_read_raw_data, but it322 * takes an sgl instead of void * buffer. i.e. it allocates323 * a new MPI and reads the content of the sgl to the MPI.324 *325 * @sgl: scatterlist to read from326 * @nbytes: number of bytes to read327 *328 * Return: Pointer to a new MPI or NULL on error329 */330MPI 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 ents = sg_nents_for_len(sgl, nbytes);341 if (ents < 0)342 return NULL;343 344 sg_miter_start(&miter, sgl, ents, SG_MITER_ATOMIC | SG_MITER_FROM_SG);345 346 lzeros = 0;347 len = 0;348 while (nbytes > 0) {349 while (len && !*buff) {350 lzeros++;351 len--;352 buff++;353 }354 355 if (len && *buff)356 break;357 358 sg_miter_next(&miter);359 buff = miter.addr;360 len = miter.length;361 362 nbytes -= lzeros;363 lzeros = 0;364 }365 366 miter.consumed = lzeros;367 368 nbytes -= lzeros;369 nbits = nbytes * 8;370 if (nbits > MAX_EXTERN_MPI_BITS) {371 sg_miter_stop(&miter);372 pr_info("MPI: mpi too large (%u bits)\n", nbits);373 return NULL;374 }375 376 if (nbytes > 0)377 nbits -= count_leading_zeros(*buff) - (BITS_PER_LONG - 8);378 379 sg_miter_stop(&miter);380 381 nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB);382 val = mpi_alloc(nlimbs);383 if (!val)384 return NULL;385 386 val->nbits = nbits;387 val->sign = 0;388 val->nlimbs = nlimbs;389 390 if (nbytes == 0)391 return val;392 393 j = nlimbs - 1;394 a = 0;395 z = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;396 z %= BYTES_PER_MPI_LIMB;397 398 while (sg_miter_next(&miter)) {399 buff = miter.addr;400 len = min_t(unsigned, miter.length, nbytes);401 nbytes -= len;402 403 for (x = 0; x < len; x++) {404 a <<= 8;405 a |= *buff++;406 if (((z + x + 1) % BYTES_PER_MPI_LIMB) == 0) {407 val->d[j--] = a;408 a = 0;409 }410 }411 z += x;412 }413 414 return val;415}416EXPORT_SYMBOL_GPL(mpi_read_raw_from_sgl);417