blob: a9f1097c18cb71f87132c6ac931c85de6b04c47d [file] [log] [blame]
Dmitry Kasatkincdec9cb2011-08-31 14:05:16 +03001/* 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
David Howellse1045992012-09-24 17:11:27 +010021#include <linux/bitops.h>
Christoph Hellwiga1164a32015-08-28 09:27:15 +020022#include <linux/count_zeros.h>
Nicolai Stanged7552902016-03-22 13:12:39 +010023#include <linux/byteorder/generic.h>
Nicolai Stange90f864e2016-03-22 13:12:41 +010024#include <linux/string.h>
Dmitry Kasatkincdec9cb2011-08-31 14:05:16 +030025#include "mpi-internal.h"
26
Dmitry Kasatkincdec9cb2011-08-31 14:05:16 +030027#define MAX_EXTERN_MPI_BITS 16384
28
David Howellse1045992012-09-24 17:11:27 +010029/**
30 * mpi_read_raw_data - Read a raw byte stream as a positive integer
31 * @xbuffer: The data to read
32 * @nbytes: The amount of data to read
33 */
34MPI mpi_read_raw_data(const void *xbuffer, size_t nbytes)
35{
36 const uint8_t *buffer = xbuffer;
37 int i, j;
38 unsigned nbits, nlimbs;
39 mpi_limb_t a;
40 MPI val = NULL;
41
Chen Gang5402b802013-06-12 14:04:40 -070042 while (nbytes > 0 && buffer[0] == 0) {
David Howellse1045992012-09-24 17:11:27 +010043 buffer++;
44 nbytes--;
45 }
46
47 nbits = nbytes * 8;
48 if (nbits > MAX_EXTERN_MPI_BITS) {
49 pr_info("MPI: mpi too large (%u bits)\n", nbits);
50 return NULL;
51 }
52 if (nbytes > 0)
53 nbits -= count_leading_zeros(buffer[0]);
54 else
55 nbits = 0;
56
Andy Shevchenko0d2a1b22013-01-30 11:30:06 +020057 nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB);
David Howellse1045992012-09-24 17:11:27 +010058 val = mpi_alloc(nlimbs);
59 if (!val)
60 return NULL;
61 val->nbits = nbits;
62 val->sign = 0;
63 val->nlimbs = nlimbs;
64
65 if (nbytes > 0) {
66 i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
67 i %= BYTES_PER_MPI_LIMB;
68 for (j = nlimbs; j > 0; j--) {
69 a = 0;
70 for (; i < BYTES_PER_MPI_LIMB; i++) {
71 a <<= 8;
72 a |= *buffer++;
73 }
74 i = 0;
75 val->d[j - 1] = a;
76 }
77 }
78 return val;
79}
80EXPORT_SYMBOL_GPL(mpi_read_raw_data);
81
Dmitry Kasatkincdec9cb2011-08-31 14:05:16 +030082MPI mpi_read_from_buffer(const void *xbuffer, unsigned *ret_nread)
83{
84 const uint8_t *buffer = xbuffer;
85 int i, j;
86 unsigned nbits, nbytes, nlimbs, nread = 0;
87 mpi_limb_t a;
Dmitry Kasatkin3cccd152012-01-26 19:13:16 +020088 MPI val = NULL;
Dmitry Kasatkincdec9cb2011-08-31 14:05:16 +030089
90 if (*ret_nread < 2)
91 goto leave;
92 nbits = buffer[0] << 8 | buffer[1];
93
94 if (nbits > MAX_EXTERN_MPI_BITS) {
95 pr_info("MPI: mpi too large (%u bits)\n", nbits);
96 goto leave;
97 }
98 buffer += 2;
99 nread = 2;
100
Andy Shevchenko0d2a1b22013-01-30 11:30:06 +0200101 nbytes = DIV_ROUND_UP(nbits, 8);
102 nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB);
Dmitry Kasatkincdec9cb2011-08-31 14:05:16 +0300103 val = mpi_alloc(nlimbs);
104 if (!val)
Dmitry Kasatkin3cccd152012-01-26 19:13:16 +0200105 return NULL;
Dmitry Kasatkincdec9cb2011-08-31 14:05:16 +0300106 i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
107 i %= BYTES_PER_MPI_LIMB;
108 val->nbits = nbits;
109 j = val->nlimbs = nlimbs;
110 val->sign = 0;
111 for (; j > 0; j--) {
112 a = 0;
113 for (; i < BYTES_PER_MPI_LIMB; i++) {
114 if (++nread > *ret_nread) {
115 printk
116 ("MPI: mpi larger than buffer nread=%d ret_nread=%d\n",
117 nread, *ret_nread);
118 goto leave;
119 }
120 a <<= 8;
121 a |= *buffer++;
122 }
123 i = 0;
124 val->d[j - 1] = a;
125 }
126
127leave:
128 *ret_nread = nread;
129 return val;
130}
131EXPORT_SYMBOL_GPL(mpi_read_from_buffer);
132
Michal Marek3ee0cb52016-02-17 14:46:59 +0100133static int count_lzeros(MPI a)
134{
135 mpi_limb_t alimb;
136 int i, lzeros = 0;
137
138 for (i = a->nlimbs - 1; i >= 0; i--) {
139 alimb = a->d[i];
140 if (alimb == 0) {
141 lzeros += sizeof(mpi_limb_t);
142 } else {
143 lzeros += count_leading_zeros(alimb) / 8;
144 break;
145 }
146 }
147 return lzeros;
148}
149
Tadeusz Strukd37e2962015-06-15 13:18:36 -0700150/**
151 * mpi_read_buffer() - read MPI to a bufer provided by user (msb first)
152 *
153 * @a: a multi precision integer
154 * @buf: bufer to which the output will be written to. Needs to be at
155 * leaset mpi_get_size(a) long.
156 * @buf_len: size of the buf.
Andrzej Zaborowski9cbe21d2015-11-13 12:01:32 +0100157 * @nbytes: receives the actual length of the data written on success and
158 * the data to-be-written on -EOVERFLOW in case buf_len was too
159 * small.
Tadeusz Strukd37e2962015-06-15 13:18:36 -0700160 * @sign: if not NULL, it will be set to the sign of a.
161 *
162 * Return: 0 on success or error code in case of error
Dmitry Kasatkincdec9cb2011-08-31 14:05:16 +0300163 */
Tadeusz Strukd37e2962015-06-15 13:18:36 -0700164int mpi_read_buffer(MPI a, uint8_t *buf, unsigned buf_len, unsigned *nbytes,
165 int *sign)
Dmitry Kasatkincdec9cb2011-08-31 14:05:16 +0300166{
Tadeusz Strukd37e2962015-06-15 13:18:36 -0700167 uint8_t *p;
Nicolai Stange90f864e2016-03-22 13:12:41 +0100168#if BYTES_PER_MPI_LIMB == 4
169 __be32 alimb;
170#elif BYTES_PER_MPI_LIMB == 8
171 __be64 alimb;
172#else
173#error please implement for this limb size.
174#endif
Tadeusz Strukd37e2962015-06-15 13:18:36 -0700175 unsigned int n = mpi_get_size(a);
Michal Marek3ee0cb52016-02-17 14:46:59 +0100176 int i, lzeros;
Tadeusz Strukd37e2962015-06-15 13:18:36 -0700177
Andrzej Zaborowski9cbe21d2015-11-13 12:01:32 +0100178 if (!buf || !nbytes)
Tadeusz Strukd37e2962015-06-15 13:18:36 -0700179 return -EINVAL;
Dmitry Kasatkincdec9cb2011-08-31 14:05:16 +0300180
181 if (sign)
182 *sign = a->sign;
Tadeusz Strukd37e2962015-06-15 13:18:36 -0700183
Michal Marek3ee0cb52016-02-17 14:46:59 +0100184 lzeros = count_lzeros(a);
Tadeusz Strukd37e2962015-06-15 13:18:36 -0700185
Andrzej Zaborowski9cbe21d2015-11-13 12:01:32 +0100186 if (buf_len < n - lzeros) {
187 *nbytes = n - lzeros;
188 return -EOVERFLOW;
189 }
190
Tadeusz Strukd37e2962015-06-15 13:18:36 -0700191 p = buf;
Tadeusz Struk0f74fbf2015-08-24 07:52:14 -0700192 *nbytes = n - lzeros;
Dmitry Kasatkincdec9cb2011-08-31 14:05:16 +0300193
Nicolai Stangef00fa242016-03-22 13:12:40 +0100194 for (i = a->nlimbs - 1 - lzeros / BYTES_PER_MPI_LIMB,
195 lzeros %= BYTES_PER_MPI_LIMB;
196 i >= 0; i--) {
Dmitry Kasatkincdec9cb2011-08-31 14:05:16 +0300197#if BYTES_PER_MPI_LIMB == 4
Nicolai Stange90f864e2016-03-22 13:12:41 +0100198 alimb = cpu_to_be32(a->d[i]);
Dmitry Kasatkincdec9cb2011-08-31 14:05:16 +0300199#elif BYTES_PER_MPI_LIMB == 8
Nicolai Stange90f864e2016-03-22 13:12:41 +0100200 alimb = cpu_to_be64(a->d[i]);
Dmitry Kasatkincdec9cb2011-08-31 14:05:16 +0300201#else
202#error please implement for this limb size.
203#endif
Nicolai Stange462696f2016-03-22 13:12:42 +0100204 memcpy(p, (u8 *)&alimb + lzeros, BYTES_PER_MPI_LIMB - lzeros);
205 p += BYTES_PER_MPI_LIMB - lzeros;
206 lzeros = 0;
Dmitry Kasatkincdec9cb2011-08-31 14:05:16 +0300207 }
Tadeusz Strukd37e2962015-06-15 13:18:36 -0700208 return 0;
209}
210EXPORT_SYMBOL_GPL(mpi_read_buffer);
211
212/*
213 * mpi_get_buffer() - Returns an allocated buffer with the MPI (msb first).
214 * Caller must free the return string.
215 * This function does return a 0 byte buffer with nbytes set to zero if the
216 * value of A is zero.
217 *
218 * @a: a multi precision integer.
219 * @nbytes: receives the length of this buffer.
220 * @sign: if not NULL, it will be set to the sign of the a.
221 *
222 * Return: Pointer to MPI buffer or NULL on error
223 */
224void *mpi_get_buffer(MPI a, unsigned *nbytes, int *sign)
225{
Tadeusz Struk0f74fbf2015-08-24 07:52:14 -0700226 uint8_t *buf;
Tadeusz Strukd37e2962015-06-15 13:18:36 -0700227 unsigned int n;
228 int ret;
229
230 if (!nbytes)
231 return NULL;
232
233 n = mpi_get_size(a);
234
235 if (!n)
236 n++;
237
238 buf = kmalloc(n, GFP_KERNEL);
239
240 if (!buf)
241 return NULL;
242
243 ret = mpi_read_buffer(a, buf, n, nbytes, sign);
244
245 if (ret) {
246 kfree(buf);
247 return NULL;
248 }
Tadeusz Strukd37e2962015-06-15 13:18:36 -0700249 return buf;
Dmitry Kasatkincdec9cb2011-08-31 14:05:16 +0300250}
251EXPORT_SYMBOL_GPL(mpi_get_buffer);
252
253/****************
254 * Use BUFFER to update MPI.
255 */
256int mpi_set_buffer(MPI a, const void *xbuffer, unsigned nbytes, int sign)
257{
258 const uint8_t *buffer = xbuffer, *p;
259 mpi_limb_t alimb;
260 int nlimbs;
261 int i;
262
Andy Shevchenko0d2a1b22013-01-30 11:30:06 +0200263 nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB);
Dmitry Kasatkincdec9cb2011-08-31 14:05:16 +0300264 if (RESIZE_IF_NEEDED(a, nlimbs) < 0)
265 return -ENOMEM;
266 a->sign = sign;
267
268 for (i = 0, p = buffer + nbytes - 1; p >= buffer + BYTES_PER_MPI_LIMB;) {
269#if BYTES_PER_MPI_LIMB == 4
270 alimb = (mpi_limb_t) *p--;
271 alimb |= (mpi_limb_t) *p-- << 8;
272 alimb |= (mpi_limb_t) *p-- << 16;
273 alimb |= (mpi_limb_t) *p-- << 24;
274#elif BYTES_PER_MPI_LIMB == 8
275 alimb = (mpi_limb_t) *p--;
276 alimb |= (mpi_limb_t) *p-- << 8;
277 alimb |= (mpi_limb_t) *p-- << 16;
278 alimb |= (mpi_limb_t) *p-- << 24;
279 alimb |= (mpi_limb_t) *p-- << 32;
280 alimb |= (mpi_limb_t) *p-- << 40;
281 alimb |= (mpi_limb_t) *p-- << 48;
282 alimb |= (mpi_limb_t) *p-- << 56;
283#else
284#error please implement for this limb size.
285#endif
286 a->d[i++] = alimb;
287 }
288 if (p >= buffer) {
289#if BYTES_PER_MPI_LIMB == 4
290 alimb = *p--;
291 if (p >= buffer)
292 alimb |= (mpi_limb_t) *p-- << 8;
293 if (p >= buffer)
294 alimb |= (mpi_limb_t) *p-- << 16;
295 if (p >= buffer)
296 alimb |= (mpi_limb_t) *p-- << 24;
297#elif BYTES_PER_MPI_LIMB == 8
298 alimb = (mpi_limb_t) *p--;
299 if (p >= buffer)
300 alimb |= (mpi_limb_t) *p-- << 8;
301 if (p >= buffer)
302 alimb |= (mpi_limb_t) *p-- << 16;
303 if (p >= buffer)
304 alimb |= (mpi_limb_t) *p-- << 24;
305 if (p >= buffer)
306 alimb |= (mpi_limb_t) *p-- << 32;
307 if (p >= buffer)
308 alimb |= (mpi_limb_t) *p-- << 40;
309 if (p >= buffer)
310 alimb |= (mpi_limb_t) *p-- << 48;
311 if (p >= buffer)
312 alimb |= (mpi_limb_t) *p-- << 56;
313#else
314#error please implement for this limb size.
315#endif
316 a->d[i++] = alimb;
317 }
318 a->nlimbs = i;
319
320 if (i != nlimbs) {
321 pr_emerg("MPI: mpi_set_buffer: Assertion failed (%d != %d)", i,
322 nlimbs);
323 BUG();
324 }
325 return 0;
326}
327EXPORT_SYMBOL_GPL(mpi_set_buffer);
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700328
329/**
330 * mpi_write_to_sgl() - Funnction exports MPI to an sgl (msb first)
331 *
332 * This function works in the same way as the mpi_read_buffer, but it
333 * takes an sgl instead of u8 * buf.
334 *
335 * @a: a multi precision integer
336 * @sgl: scatterlist to write to. Needs to be at least
337 * mpi_get_size(a) long.
338 * @nbytes: in/out param - it has the be set to the maximum number of
339 * bytes that can be written to sgl. This has to be at least
340 * the size of the integer a. On return it receives the actual
Andrzej Zaborowski9cbe21d2015-11-13 12:01:32 +0100341 * length of the data written on success or the data that would
342 * be written if buffer was too small.
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700343 * @sign: if not NULL, it will be set to the sign of a.
344 *
345 * Return: 0 on success or error code in case of error
346 */
347int mpi_write_to_sgl(MPI a, struct scatterlist *sgl, unsigned *nbytes,
348 int *sign)
349{
350 u8 *p, *p2;
Nicolai Stanged7552902016-03-22 13:12:39 +0100351#if BYTES_PER_MPI_LIMB == 4
352 __be32 alimb;
353#elif BYTES_PER_MPI_LIMB == 8
354 __be64 alimb;
355#else
356#error please implement for this limb size.
357#endif
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700358 unsigned int n = mpi_get_size(a);
Michal Marek3ee0cb52016-02-17 14:46:59 +0100359 int i, x, y = 0, lzeros, buf_len;
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700360
Andrzej Zaborowski9cbe21d2015-11-13 12:01:32 +0100361 if (!nbytes)
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700362 return -EINVAL;
363
364 if (sign)
365 *sign = a->sign;
366
Michal Marek3ee0cb52016-02-17 14:46:59 +0100367 lzeros = count_lzeros(a);
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700368
Andrzej Zaborowski9cbe21d2015-11-13 12:01:32 +0100369 if (*nbytes < n - lzeros) {
370 *nbytes = n - lzeros;
371 return -EOVERFLOW;
372 }
373
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700374 *nbytes = n - lzeros;
375 buf_len = sgl->length;
376 p2 = sg_virt(sgl);
377
Nicolai Stangef2d13622016-03-22 13:12:35 +0100378 for (i = a->nlimbs - 1 - lzeros / BYTES_PER_MPI_LIMB,
379 lzeros %= BYTES_PER_MPI_LIMB;
380 i >= 0; i--) {
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700381#if BYTES_PER_MPI_LIMB == 4
Nicolai Stanged7552902016-03-22 13:12:39 +0100382 alimb = cpu_to_be32(a->d[i]);
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700383#elif BYTES_PER_MPI_LIMB == 8
Nicolai Stanged7552902016-03-22 13:12:39 +0100384 alimb = cpu_to_be64(a->d[i]);
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700385#else
386#error please implement for this limb size.
387#endif
Nicolai Stange654842e2016-03-22 13:12:36 +0100388 if (lzeros) {
Nicolai Stangef2d13622016-03-22 13:12:35 +0100389 y = lzeros;
Nicolai Stange654842e2016-03-22 13:12:36 +0100390 lzeros = 0;
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700391 }
392
Nicolai Stanged7552902016-03-22 13:12:39 +0100393 p = (u8 *)&alimb + y;
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700394
395 for (x = 0; x < sizeof(alimb) - y; x++) {
396 if (!buf_len) {
397 sgl = sg_next(sgl);
398 if (!sgl)
399 return -EINVAL;
400 buf_len = sgl->length;
401 p2 = sg_virt(sgl);
402 }
403 *p2++ = *p++;
404 buf_len--;
405 }
406 y = 0;
407 }
408 return 0;
409}
410EXPORT_SYMBOL_GPL(mpi_write_to_sgl);
411
412/*
413 * mpi_read_raw_from_sgl() - Function allocates an MPI and populates it with
414 * data from the sgl
415 *
416 * This function works in the same way as the mpi_read_raw_data, but it
417 * takes an sgl instead of void * buffer. i.e. it allocates
418 * a new MPI and reads the content of the sgl to the MPI.
419 *
420 * @sgl: scatterlist to read from
Nicolai Stangeb6985382016-03-22 13:12:43 +0100421 * @nbytes: number of bytes to read
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700422 *
423 * Return: Pointer to a new MPI or NULL on error
424 */
Nicolai Stangeb6985382016-03-22 13:12:43 +0100425MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int nbytes)
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700426{
427 struct scatterlist *sg;
428 int x, i, j, z, lzeros, ents;
Nicolai Stangeb6985382016-03-22 13:12:43 +0100429 unsigned int nbits, nlimbs;
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700430 mpi_limb_t a;
431 MPI val = NULL;
432
433 lzeros = 0;
434 ents = sg_nents(sgl);
435
436 for_each_sg(sgl, sg, ents, i) {
437 const u8 *buff = sg_virt(sg);
438 int len = sg->length;
439
Stephan Mueller63349d02015-10-18 12:45:18 +0200440 while (len && !*buff) {
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700441 lzeros++;
Stephan Mueller63349d02015-10-18 12:45:18 +0200442 len--;
443 buff++;
444 }
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700445
446 if (len && *buff)
447 break;
448
449 ents--;
Nicolai Stangeab1e9122016-03-22 13:12:44 +0100450 nbytes -= lzeros;
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700451 lzeros = 0;
452 }
453
454 sgl = sg;
Nicolai Stangeab1e9122016-03-22 13:12:44 +0100455 nbytes -= lzeros;
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700456 nbits = nbytes * 8;
457 if (nbits > MAX_EXTERN_MPI_BITS) {
458 pr_info("MPI: mpi too large (%u bits)\n", nbits);
459 return NULL;
460 }
461
462 if (nbytes > 0)
Nicolai Stange64c09b02016-03-22 13:17:27 +0100463 nbits -= count_leading_zeros(*(u8 *)(sg_virt(sgl) + lzeros)) -
464 (BITS_PER_LONG - 8);
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700465
466 nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB);
467 val = mpi_alloc(nlimbs);
468 if (!val)
469 return NULL;
470
471 val->nbits = nbits;
472 val->sign = 0;
473 val->nlimbs = nlimbs;
474
475 if (nbytes == 0)
476 return val;
477
478 j = nlimbs - 1;
479 a = 0;
Nicolai Stange85d541a2016-03-22 13:18:07 +0100480 z = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
481 z %= BYTES_PER_MPI_LIMB;
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700482
483 for_each_sg(sgl, sg, ents, i) {
484 const u8 *buffer = sg_virt(sg) + lzeros;
485 int len = sg->length - lzeros;
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700486
487 if (sg_is_last(sg) && (len % BYTES_PER_MPI_LIMB))
488 len += BYTES_PER_MPI_LIMB - (len % BYTES_PER_MPI_LIMB);
489
Nicolai Stange85d541a2016-03-22 13:18:07 +0100490 for (x = 0; x < len; x++) {
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700491 a <<= 8;
492 a |= *buffer++;
493 if (((z + x + 1) % BYTES_PER_MPI_LIMB) == 0) {
494 val->d[j--] = a;
495 a = 0;
496 }
497 }
498 z += x;
Tadeusz Struk2d4d1ee2015-10-08 09:26:50 -0700499 lzeros = 0;
500 }
501 return val;
502}
503EXPORT_SYMBOL_GPL(mpi_read_raw_from_sgl);