projects / deliverable / linux.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Merge tag 'renesas-sh-drivers-for-v4.8' of git://git.kernel.org/pub/scm/linux/kernel...
[deliverable/linux.git] / lib / mpi / mpicoder.c
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/string.h>
25 #include "mpi-internal.h"
26
27 #define MAX_EXTERN_MPI_BITS 16384
28
29 /**
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 */
34 MPI 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
42 while (nbytes > 0 && buffer[0] == 0) {
43 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
57 nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB);
58 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 }
80 EXPORT_SYMBOL_GPL(mpi_read_raw_data);
81
82 MPI 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;
88 MPI val = NULL;
89
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
101 nbytes = DIV_ROUND_UP(nbits, 8);
102 nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB);
103 val = mpi_alloc(nlimbs);
104 if (!val)
105 return NULL;
106 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
127 leave:
128 *ret_nread = nread;
129 return val;
130 }
131 EXPORT_SYMBOL_GPL(mpi_read_from_buffer);
132
133 static 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
150 /**
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.
157 * @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.
160 * @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
163 */
164 int mpi_read_buffer(MPI a, uint8_t *buf, unsigned buf_len, unsigned *nbytes,
165 int *sign)
166 {
167 uint8_t *p;
168 #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
175 unsigned int n = mpi_get_size(a);
176 int i, lzeros;
177
178 if (!buf || !nbytes)
179 return -EINVAL;
180
181 if (sign)
182 *sign = a->sign;
183
184 lzeros = count_lzeros(a);
185
186 if (buf_len < n - lzeros) {
187 *nbytes = n - lzeros;
188 return -EOVERFLOW;
189 }
190
191 p = buf;
192 *nbytes = n - lzeros;
193
194 for (i = a->nlimbs - 1 - lzeros / BYTES_PER_MPI_LIMB,
195 lzeros %= BYTES_PER_MPI_LIMB;
196 i >= 0; i--) {
197 #if BYTES_PER_MPI_LIMB == 4
198 alimb = cpu_to_be32(a->d[i]);
199 #elif BYTES_PER_MPI_LIMB == 8
200 alimb = cpu_to_be64(a->d[i]);
201 #else
202 #error please implement for this limb size.
203 #endif
204 memcpy(p, (u8 *)&alimb + lzeros, BYTES_PER_MPI_LIMB - lzeros);
205 p += BYTES_PER_MPI_LIMB - lzeros;
206 lzeros = 0;
207 }
208 return 0;
209 }
210 EXPORT_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 */
224 void *mpi_get_buffer(MPI a, unsigned *nbytes, int *sign)
225 {
226 uint8_t *buf;
227 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 }
249 return buf;
250 }
251 EXPORT_SYMBOL_GPL(mpi_get_buffer);
252
253 /****************
254 * Use BUFFER to update MPI.
255 */
256 int 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
263 nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB);
264 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 }
327 EXPORT_SYMBOL_GPL(mpi_set_buffer);
328
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
341 * length of the data written on success or the data that would
342 * be written if buffer was too small.
343 * @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 */
347 int mpi_write_to_sgl(MPI a, struct scatterlist *sgl, unsigned *nbytes,
348 int *sign)
349 {
350 u8 *p, *p2;
351 #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
358 unsigned int n = mpi_get_size(a);
359 int i, x, y = 0, lzeros, buf_len;
360
361 if (!nbytes)
362 return -EINVAL;
363
364 if (sign)
365 *sign = a->sign;
366
367 lzeros = count_lzeros(a);
368
369 if (*nbytes < n - lzeros) {
370 *nbytes = n - lzeros;
371 return -EOVERFLOW;
372 }
373
374 *nbytes = n - lzeros;
375 buf_len = sgl->length;
376 p2 = sg_virt(sgl);
377
378 for (i = a->nlimbs - 1 - lzeros / BYTES_PER_MPI_LIMB,
379 lzeros %= BYTES_PER_MPI_LIMB;
380 i >= 0; i--) {
381 #if BYTES_PER_MPI_LIMB == 4
382 alimb = cpu_to_be32(a->d[i]);
383 #elif BYTES_PER_MPI_LIMB == 8
384 alimb = cpu_to_be64(a->d[i]);
385 #else
386 #error please implement for this limb size.
387 #endif
388 if (lzeros) {
389 y = lzeros;
390 lzeros = 0;
391 }
392
393 p = (u8 *)&alimb + y;
394
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 }
410 EXPORT_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
421 * @nbytes: number of bytes to read
422 *
423 * Return: Pointer to a new MPI or NULL on error
424 */
425 MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int nbytes)
426 {
427 struct scatterlist *sg;
428 int x, i, j, z, lzeros, ents;
429 unsigned int nbits, nlimbs;
430 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
440 while (len && !*buff) {
441 lzeros++;
442 len--;
443 buff++;
444 }
445
446 if (len && *buff)
447 break;
448
449 ents--;
450 nbytes -= lzeros;
451 lzeros = 0;
452 }
453
454 sgl = sg;
455 nbytes -= lzeros;
456 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)
463 nbits -= count_leading_zeros(*(u8 *)(sg_virt(sgl) + lzeros)) -
464 (BITS_PER_LONG - 8);
465
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;
480 z = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
481 z %= BYTES_PER_MPI_LIMB;
482
483 for_each_sg(sgl, sg, ents, i) {
484 const u8 *buffer = sg_virt(sg) + lzeros;
485 int len = sg->length - lzeros;
486
487 for (x = 0; x < len; x++) {
488 a <<= 8;
489 a |= *buffer++;
490 if (((z + x + 1) % BYTES_PER_MPI_LIMB) == 0) {
491 val->d[j--] = a;
492 a = 0;
493 }
494 }
495 z += x;
496 lzeros = 0;
497 }
498 return val;
499 }
500 EXPORT_SYMBOL_GPL(mpi_read_raw_from_sgl);
Linux kernel - Deliverables
This page took 0.048742 seconds and 5 git commands to generate.