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 "mpi-internal.h" 24 25#define MAX_EXTERN_MPI_BITS 16384 26 27/** 28 * mpi_read_raw_data - Read a raw byte stream as a positive integer 29 * @xbuffer: The data to read 30 * @nbytes: The amount of data to read 31 */ 32MPI mpi_read_raw_data(const void *xbuffer, size_t nbytes) 33{ 34 const uint8_t *buffer = xbuffer; 35 int i, j; 36 unsigned nbits, nlimbs; 37 mpi_limb_t a; 38 MPI val = NULL; 39 40 while (nbytes > 0 && buffer[0] == 0) { 41 buffer++; 42 nbytes--; 43 } 44 45 nbits = nbytes * 8; 46 if (nbits > MAX_EXTERN_MPI_BITS) { 47 pr_info("MPI: mpi too large (%u bits)\n", nbits); 48 return NULL; 49 } 50 if (nbytes > 0) 51 nbits -= count_leading_zeros(buffer[0]); 52 else 53 nbits = 0; 54 55 nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB); 56 val = mpi_alloc(nlimbs); 57 if (!val) 58 return NULL; 59 val->nbits = nbits; 60 val->sign = 0; 61 val->nlimbs = nlimbs; 62 63 if (nbytes > 0) { 64 i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB; 65 i %= BYTES_PER_MPI_LIMB; 66 for (j = nlimbs; j > 0; j--) { 67 a = 0; 68 for (; i < BYTES_PER_MPI_LIMB; i++) { 69 a <<= 8; 70 a |= *buffer++; 71 } 72 i = 0; 73 val->d[j - 1] = a; 74 } 75 } 76 return val; 77} 78EXPORT_SYMBOL_GPL(mpi_read_raw_data); 79 80MPI mpi_read_from_buffer(const void *xbuffer, unsigned *ret_nread) 81{ 82 const uint8_t *buffer = xbuffer; 83 int i, j; 84 unsigned nbits, nbytes, nlimbs, nread = 0; 85 mpi_limb_t a; 86 MPI val = NULL; 87 88 if (*ret_nread < 2) 89 goto leave; 90 nbits = buffer[0] << 8 | buffer[1]; 91 92 if (nbits > MAX_EXTERN_MPI_BITS) { 93 pr_info("MPI: mpi too large (%u bits)\n", nbits); 94 goto leave; 95 } 96 buffer += 2; 97 nread = 2; 98 99 nbytes = DIV_ROUND_UP(nbits, 8); 100 nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB); 101 val = mpi_alloc(nlimbs); 102 if (!val) 103 return NULL; 104 i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB; 105 i %= BYTES_PER_MPI_LIMB; 106 val->nbits = nbits; 107 j = val->nlimbs = nlimbs; 108 val->sign = 0; 109 for (; j > 0; j--) { 110 a = 0; 111 for (; i < BYTES_PER_MPI_LIMB; i++) { 112 if (++nread > *ret_nread) { 113 printk 114 ("MPI: mpi larger than buffer nread=%d ret_nread=%d\n", 115 nread, *ret_nread); 116 goto leave; 117 } 118 a <<= 8; 119 a |= *buffer++; 120 } 121 i = 0; 122 val->d[j - 1] = a; 123 } 124 125leave: 126 *ret_nread = nread; 127 return val; 128} 129EXPORT_SYMBOL_GPL(mpi_read_from_buffer); 130 131static int count_lzeros(MPI a) 132{ 133 mpi_limb_t alimb; 134 int i, lzeros = 0; 135 136 for (i = a->nlimbs - 1; i >= 0; i--) { 137 alimb = a->d[i]; 138 if (alimb == 0) { 139 lzeros += sizeof(mpi_limb_t); 140 } else { 141 lzeros += count_leading_zeros(alimb) / 8; 142 break; 143 } 144 } 145 return lzeros; 146} 147 148/** 149 * mpi_read_buffer() - read MPI to a bufer provided by user (msb first) 150 * 151 * @a: a multi precision integer 152 * @buf: bufer to which the output will be written to. Needs to be at 153 * leaset mpi_get_size(a) long. 154 * @buf_len: size of the buf. 155 * @nbytes: receives the actual length of the data written. 156 * @sign: if not NULL, it will be set to the sign of a. 157 * 158 * Return: 0 on success or error code in case of error 159 */ 160int mpi_read_buffer(MPI a, uint8_t *buf, unsigned buf_len, unsigned *nbytes, 161 int *sign) 162{ 163 uint8_t *p; 164 mpi_limb_t alimb; 165 unsigned int n = mpi_get_size(a); 166 int i, lzeros; 167 168 if (buf_len < n || !buf || !nbytes) 169 return -EINVAL; 170 171 if (sign) 172 *sign = a->sign; 173 174 lzeros = count_lzeros(a); 175 176 p = buf; 177 *nbytes = n - lzeros; 178 179 for (i = a->nlimbs - 1; i >= 0; i--) { 180 alimb = a->d[i]; 181#if BYTES_PER_MPI_LIMB == 4 182 *p++ = alimb >> 24; 183 *p++ = alimb >> 16; 184 *p++ = alimb >> 8; 185 *p++ = alimb; 186#elif BYTES_PER_MPI_LIMB == 8 187 *p++ = alimb >> 56; 188 *p++ = alimb >> 48; 189 *p++ = alimb >> 40; 190 *p++ = alimb >> 32; 191 *p++ = alimb >> 24; 192 *p++ = alimb >> 16; 193 *p++ = alimb >> 8; 194 *p++ = alimb; 195#else 196#error please implement for this limb size. 197#endif 198 199 if (lzeros > 0) { 200 if (lzeros >= sizeof(alimb)) { 201 p -= sizeof(alimb); 202 } else { 203 mpi_limb_t *limb1 = (void *)p - sizeof(alimb); 204 mpi_limb_t *limb2 = (void *)p - sizeof(alimb) 205 + lzeros; 206 *limb1 = *limb2; 207 p -= lzeros; 208 } 209 lzeros -= sizeof(alimb); 210 } 211 } 212 return 0; 213} 214EXPORT_SYMBOL_GPL(mpi_read_buffer); 215 216/* 217 * mpi_get_buffer() - Returns an allocated buffer with the MPI (msb first). 218 * Caller must free the return string. 219 * This function does return a 0 byte buffer with nbytes set to zero if the 220 * value of A is zero. 221 * 222 * @a: a multi precision integer. 223 * @nbytes: receives the length of this buffer. 224 * @sign: if not NULL, it will be set to the sign of the a. 225 * 226 * Return: Pointer to MPI buffer or NULL on error 227 */ 228void *mpi_get_buffer(MPI a, unsigned *nbytes, int *sign) 229{ 230 uint8_t *buf; 231 unsigned int n; 232 int ret; 233 234 if (!nbytes) 235 return NULL; 236 237 n = mpi_get_size(a); 238 239 if (!n) 240 n++; 241 242 buf = kmalloc(n, GFP_KERNEL); 243 244 if (!buf) 245 return NULL; 246 247 ret = mpi_read_buffer(a, buf, n, nbytes, sign); 248 249 if (ret) { 250 kfree(buf); 251 return NULL; 252 } 253 return buf; 254} 255EXPORT_SYMBOL_GPL(mpi_get_buffer); 256 257/**************** 258 * Use BUFFER to update MPI. 259 */ 260int mpi_set_buffer(MPI a, const void *xbuffer, unsigned nbytes, int sign) 261{ 262 const uint8_t *buffer = xbuffer, *p; 263 mpi_limb_t alimb; 264 int nlimbs; 265 int i; 266 267 nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB); 268 if (RESIZE_IF_NEEDED(a, nlimbs) < 0) 269 return -ENOMEM; 270 a->sign = sign; 271 272 for (i = 0, p = buffer + nbytes - 1; p >= buffer + BYTES_PER_MPI_LIMB;) { 273#if BYTES_PER_MPI_LIMB == 4 274 alimb = (mpi_limb_t) *p--; 275 alimb |= (mpi_limb_t) *p-- << 8; 276 alimb |= (mpi_limb_t) *p-- << 16; 277 alimb |= (mpi_limb_t) *p-- << 24; 278#elif BYTES_PER_MPI_LIMB == 8 279 alimb = (mpi_limb_t) *p--; 280 alimb |= (mpi_limb_t) *p-- << 8; 281 alimb |= (mpi_limb_t) *p-- << 16; 282 alimb |= (mpi_limb_t) *p-- << 24; 283 alimb |= (mpi_limb_t) *p-- << 32; 284 alimb |= (mpi_limb_t) *p-- << 40; 285 alimb |= (mpi_limb_t) *p-- << 48; 286 alimb |= (mpi_limb_t) *p-- << 56; 287#else 288#error please implement for this limb size. 289#endif 290 a->d[i++] = alimb; 291 } 292 if (p >= buffer) { 293#if BYTES_PER_MPI_LIMB == 4 294 alimb = *p--; 295 if (p >= buffer) 296 alimb |= (mpi_limb_t) *p-- << 8; 297 if (p >= buffer) 298 alimb |= (mpi_limb_t) *p-- << 16; 299 if (p >= buffer) 300 alimb |= (mpi_limb_t) *p-- << 24; 301#elif BYTES_PER_MPI_LIMB == 8 302 alimb = (mpi_limb_t) *p--; 303 if (p >= buffer) 304 alimb |= (mpi_limb_t) *p-- << 8; 305 if (p >= buffer) 306 alimb |= (mpi_limb_t) *p-- << 16; 307 if (p >= buffer) 308 alimb |= (mpi_limb_t) *p-- << 24; 309 if (p >= buffer) 310 alimb |= (mpi_limb_t) *p-- << 32; 311 if (p >= buffer) 312 alimb |= (mpi_limb_t) *p-- << 40; 313 if (p >= buffer) 314 alimb |= (mpi_limb_t) *p-- << 48; 315 if (p >= buffer) 316 alimb |= (mpi_limb_t) *p-- << 56; 317#else 318#error please implement for this limb size. 319#endif 320 a->d[i++] = alimb; 321 } 322 a->nlimbs = i; 323 324 if (i != nlimbs) { 325 pr_emerg("MPI: mpi_set_buffer: Assertion failed (%d != %d)", i, 326 nlimbs); 327 BUG(); 328 } 329 return 0; 330} 331EXPORT_SYMBOL_GPL(mpi_set_buffer); 332 333/** 334 * mpi_write_to_sgl() - Funnction exports MPI to an sgl (msb first) 335 * 336 * This function works in the same way as the mpi_read_buffer, but it 337 * takes an sgl instead of u8 * buf. 338 * 339 * @a: a multi precision integer 340 * @sgl: scatterlist to write to. Needs to be at least 341 * mpi_get_size(a) long. 342 * @nbytes: in/out param - it has the be set to the maximum number of 343 * bytes that can be written to sgl. This has to be at least 344 * the size of the integer a. On return it receives the actual 345 * length of the data written. 346 * @sign: if not NULL, it will be set to the sign of a. 347 * 348 * Return: 0 on success or error code in case of error 349 */ 350int mpi_write_to_sgl(MPI a, struct scatterlist *sgl, unsigned *nbytes, 351 int *sign) 352{ 353 u8 *p, *p2; 354 mpi_limb_t alimb, alimb2; 355 unsigned int n = mpi_get_size(a); 356 int i, x, y = 0, lzeros, buf_len; 357 358 if (!nbytes || *nbytes < n) 359 return -EINVAL; 360 361 if (sign) 362 *sign = a->sign; 363 364 lzeros = count_lzeros(a); 365 366 *nbytes = n - lzeros; 367 buf_len = sgl->length; 368 p2 = sg_virt(sgl); 369 370 for (i = a->nlimbs - 1; i >= 0; i--) { 371 alimb = a->d[i]; 372 p = (u8 *)&alimb2; 373#if BYTES_PER_MPI_LIMB == 4 374 *p++ = alimb >> 24; 375 *p++ = alimb >> 16; 376 *p++ = alimb >> 8; 377 *p++ = alimb; 378#elif BYTES_PER_MPI_LIMB == 8 379 *p++ = alimb >> 56; 380 *p++ = alimb >> 48; 381 *p++ = alimb >> 40; 382 *p++ = alimb >> 32; 383 *p++ = alimb >> 24; 384 *p++ = alimb >> 16; 385 *p++ = alimb >> 8; 386 *p++ = alimb; 387#else 388#error please implement for this limb size. 389#endif 390 if (lzeros > 0) { 391 if (lzeros >= sizeof(alimb)) { 392 p -= sizeof(alimb); 393 continue; 394 } else { 395 mpi_limb_t *limb1 = (void *)p - sizeof(alimb); 396 mpi_limb_t *limb2 = (void *)p - sizeof(alimb) 397 + lzeros; 398 *limb1 = *limb2; 399 p -= lzeros; 400 y = lzeros; 401 } 402 lzeros -= sizeof(alimb); 403 } 404 405 p = p - (sizeof(alimb) - y); 406 407 for (x = 0; x < sizeof(alimb) - y; x++) { 408 if (!buf_len) { 409 sgl = sg_next(sgl); 410 if (!sgl) 411 return -EINVAL; 412 buf_len = sgl->length; 413 p2 = sg_virt(sgl); 414 } 415 *p2++ = *p++; 416 buf_len--; 417 } 418 y = 0; 419 } 420 return 0; 421} 422EXPORT_SYMBOL_GPL(mpi_write_to_sgl); 423 424/* 425 * mpi_read_raw_from_sgl() - Function allocates an MPI and populates it with 426 * data from the sgl 427 * 428 * This function works in the same way as the mpi_read_raw_data, but it 429 * takes an sgl instead of void * buffer. i.e. it allocates 430 * a new MPI and reads the content of the sgl to the MPI. 431 * 432 * @sgl: scatterlist to read from 433 * @len: number of bytes to read 434 * 435 * Return: Pointer to a new MPI or NULL on error 436 */ 437MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int len) 438{ 439 struct scatterlist *sg; 440 int x, i, j, z, lzeros, ents; 441 unsigned int nbits, nlimbs, nbytes; 442 mpi_limb_t a; 443 MPI val = NULL; 444 445 lzeros = 0; 446 ents = sg_nents(sgl); 447 448 for_each_sg(sgl, sg, ents, i) { 449 const u8 *buff = sg_virt(sg); 450 int len = sg->length; 451 452 while (len && !*buff) { 453 lzeros++; 454 len--; 455 buff++; 456 } 457 458 if (len && *buff) 459 break; 460 461 ents--; 462 lzeros = 0; 463 } 464 465 sgl = sg; 466 467 if (!ents) 468 nbytes = 0; 469 else 470 nbytes = len - lzeros; 471 472 nbits = nbytes * 8; 473 if (nbits > MAX_EXTERN_MPI_BITS) { 474 pr_info("MPI: mpi too large (%u bits)\n", nbits); 475 return NULL; 476 } 477 478 if (nbytes > 0) 479 nbits -= count_leading_zeros(*(u8 *)(sg_virt(sgl) + lzeros)); 480 else 481 nbits = 0; 482 483 nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB); 484 val = mpi_alloc(nlimbs); 485 if (!val) 486 return NULL; 487 488 val->nbits = nbits; 489 val->sign = 0; 490 val->nlimbs = nlimbs; 491 492 if (nbytes == 0) 493 return val; 494 495 j = nlimbs - 1; 496 a = 0; 497 z = 0; 498 x = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB; 499 x %= BYTES_PER_MPI_LIMB; 500 501 for_each_sg(sgl, sg, ents, i) { 502 const u8 *buffer = sg_virt(sg) + lzeros; 503 int len = sg->length - lzeros; 504 int buf_shift = x; 505 506 if (sg_is_last(sg) && (len % BYTES_PER_MPI_LIMB)) 507 len += BYTES_PER_MPI_LIMB - (len % BYTES_PER_MPI_LIMB); 508 509 for (; x < len + buf_shift; x++) { 510 a <<= 8; 511 a |= *buffer++; 512 if (((z + x + 1) % BYTES_PER_MPI_LIMB) == 0) { 513 val->d[j--] = a; 514 a = 0; 515 } 516 } 517 z += x; 518 x = 0; 519 lzeros = 0; 520 } 521 return val; 522} 523EXPORT_SYMBOL_GPL(mpi_read_raw_from_sgl); 524