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 : 1656 : 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 [ + - + + ]: 4140 : while (nbytes > 0 && buffer[0] == 0) {
44 : 828 : buffer++;
45 : 828 : nbytes--;
46 : : }
47 : :
48 : 1656 : nbits = nbytes * 8;
49 [ - + ]: 1656 : if (nbits > MAX_EXTERN_MPI_BITS) {
50 : 0 : pr_info("MPI: mpi too large (%u bits)\n", nbits);
51 : 0 : return NULL;
52 : : }
53 [ + - ]: 1656 : if (nbytes > 0)
54 : 3312 : nbits -= count_leading_zeros(buffer[0]) - (BITS_PER_LONG - 8);
55 : :
56 : 1656 : nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB);
57 : 1656 : val = mpi_alloc(nlimbs);
58 [ + - ]: 1656 : if (!val)
59 : : return NULL;
60 : 1656 : val->nbits = nbits;
61 : 1656 : val->sign = 0;
62 : 1656 : val->nlimbs = nlimbs;
63 : :
64 [ + - ]: 1656 : if (nbytes > 0) {
65 : 1656 : i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
66 : 1656 : i %= BYTES_PER_MPI_LIMB;
67 [ + + ]: 55476 : for (j = nlimbs; j > 0; j--) {
68 : : a = 0;
69 [ + + ]: 214452 : for (; i < BYTES_PER_MPI_LIMB; i++) {
70 : 214452 : a <<= 8;
71 : 214452 : a |= *buffer++;
72 : : }
73 : : i = 0;
74 : 53820 : val->d[j - 1] = a;
75 : : }
76 : : }
77 : 1656 : 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 : 828 : 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 [ + - ]: 828 : if (sign)
264 : 828 : *sign = a->sign;
265 : :
266 [ + - ]: 828 : if (nbytes < n)
267 : : return -EOVERFLOW;
268 : :
269 : 828 : nents = sg_nents_for_len(sgl, nbytes);
270 [ + - ]: 828 : if (nents < 0)
271 : : return -EINVAL;
272 : :
273 : 828 : sg_miter_start(&miter, sgl, nents, SG_MITER_ATOMIC | SG_MITER_TO_SG);
274 : 828 : sg_miter_next(&miter);
275 : 828 : buf_len = miter.length;
276 : 828 : p2 = miter.addr;
277 : :
278 [ - + ]: 1656 : 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 [ + + ]: 53820 : for (i = a->nlimbs - 1; i >= 0; i--) {
293 : : #if BYTES_PER_MPI_LIMB == 4
294 [ + - ]: 52992 : 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 [ + + ]: 264960 : for (x = 0; x < sizeof(alimb); x++) {
303 : 211968 : *p2++ = *p++;
304 [ + + ]: 211968 : if (!--buf_len) {
305 : 828 : sg_miter_next(&miter);
306 : 828 : buf_len = miter.length;
307 : 828 : p2 = miter.addr;
308 : : }
309 : : }
310 : : }
311 : :
312 : 828 : sg_miter_stop(&miter);
313 : 828 : 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 : 828 : 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 : 828 : ents = sg_nents_for_len(sgl, nbytes);
341 [ + - ]: 828 : if (ents < 0)
342 : : return NULL;
343 : :
344 : 828 : sg_miter_start(&miter, sgl, ents, SG_MITER_ATOMIC | SG_MITER_FROM_SG);
345 : :
346 : : lzeros = 0;
347 : : len = 0;
348 [ + - ]: 2484 : while (nbytes > 0) {
349 [ + + - + ]: 1656 : while (len && !*buff) {
350 : 0 : lzeros++;
351 : 0 : len--;
352 : 0 : buff++;
353 : : }
354 : :
355 [ + + - + ]: 1656 : if (len && *buff)
356 : : break;
357 : :
358 : 828 : sg_miter_next(&miter);
359 : 828 : buff = miter.addr;
360 : 828 : len = miter.length;
361 : :
362 : 828 : nbytes -= lzeros;
363 : : lzeros = 0;
364 : : }
365 : :
366 : 828 : miter.consumed = lzeros;
367 : :
368 : 828 : nbytes -= lzeros;
369 : 828 : nbits = nbytes * 8;
370 [ - + ]: 828 : 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 [ + - ]: 828 : if (nbytes > 0)
377 : 1656 : nbits -= count_leading_zeros(*buff) - (BITS_PER_LONG - 8);
378 : :
379 : 828 : sg_miter_stop(&miter);
380 : :
381 : 828 : nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB);
382 : 828 : val = mpi_alloc(nlimbs);
383 [ + - ]: 828 : if (!val)
384 : : return NULL;
385 : :
386 : 828 : val->nbits = nbits;
387 : 828 : val->sign = 0;
388 : 828 : val->nlimbs = nlimbs;
389 : :
390 [ + - ]: 828 : if (nbytes == 0)
391 : : return val;
392 : :
393 : 828 : j = nlimbs - 1;
394 : : a = 0;
395 : 828 : z = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
396 : 828 : z %= BYTES_PER_MPI_LIMB;
397 : :
398 [ + + ]: 2484 : while (sg_miter_next(&miter)) {
399 : 828 : buff = miter.addr;
400 : 828 : len = miter.length;
401 : :
402 [ + + ]: 212796 : for (x = 0; x < len; x++) {
403 : 211968 : a <<= 8;
404 : 211968 : a |= *buff++;
405 [ + + ]: 211968 : if (((z + x + 1) % BYTES_PER_MPI_LIMB) == 0) {
406 : 52992 : val->d[j--] = a;
407 : : a = 0;
408 : : }
409 : : }
410 : 828 : z += x;
411 : : }
412 : :
413 : : return val;
414 : : }
415 : : EXPORT_SYMBOL_GPL(mpi_read_raw_from_sgl);
|
