mpicoder.c 9.27 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* mpicoder.c  -  Coder for the external representation of MPIs
 * Copyright (C) 1998, 1999 Free Software Foundation, Inc.
 *
 * This file is part of GnuPG.
 *
 * GnuPG is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * GnuPG is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
 */

21
#include <linux/bitops.h>
22
#include <linux/count_zeros.h>
23
#include <linux/byteorder/generic.h>
24
#include <linux/string.h>
25
26
27
28
#include "mpi-internal.h"

#define MAX_EXTERN_MPI_BITS 16384

29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * mpi_read_raw_data - Read a raw byte stream as a positive integer
 * @xbuffer: The data to read
 * @nbytes: The amount of data to read
 */
MPI mpi_read_raw_data(const void *xbuffer, size_t nbytes)
{
	const uint8_t *buffer = xbuffer;
	int i, j;
	unsigned nbits, nlimbs;
	mpi_limb_t a;
	MPI val = NULL;

42
	while (nbytes > 0 && buffer[0] == 0) {
43
44
45
46
47
48
49
50
51
52
		buffer++;
		nbytes--;
	}

	nbits = nbytes * 8;
	if (nbits > MAX_EXTERN_MPI_BITS) {
		pr_info("MPI: mpi too large (%u bits)\n", nbits);
		return NULL;
	}
	if (nbytes > 0)
53
		nbits -= count_leading_zeros(buffer[0]) - (BITS_PER_LONG - 8);
54

55
	nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB);
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
	val = mpi_alloc(nlimbs);
	if (!val)
		return NULL;
	val->nbits = nbits;
	val->sign = 0;
	val->nlimbs = nlimbs;

	if (nbytes > 0) {
		i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
		i %= BYTES_PER_MPI_LIMB;
		for (j = nlimbs; j > 0; j--) {
			a = 0;
			for (; i < BYTES_PER_MPI_LIMB; i++) {
				a <<= 8;
				a |= *buffer++;
			}
			i = 0;
			val->d[j - 1] = a;
		}
	}
	return val;
}
EXPORT_SYMBOL_GPL(mpi_read_raw_data);

80
81
82
83
84
85
MPI mpi_read_from_buffer(const void *xbuffer, unsigned *ret_nread)
{
	const uint8_t *buffer = xbuffer;
	int i, j;
	unsigned nbits, nbytes, nlimbs, nread = 0;
	mpi_limb_t a;
86
	MPI val = NULL;
87
88

	if (*ret_nread < 2)
89
		return ERR_PTR(-EINVAL);
90
91
92
93
	nbits = buffer[0] << 8 | buffer[1];

	if (nbits > MAX_EXTERN_MPI_BITS) {
		pr_info("MPI: mpi too large (%u bits)\n", nbits);
94
		return ERR_PTR(-EINVAL);
95
96
97
98
	}
	buffer += 2;
	nread = 2;

99
100
	nbytes = DIV_ROUND_UP(nbits, 8);
	nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB);
101
102
	val = mpi_alloc(nlimbs);
	if (!val)
103
		return ERR_PTR(-ENOMEM);
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
	i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
	i %= BYTES_PER_MPI_LIMB;
	val->nbits = nbits;
	j = val->nlimbs = nlimbs;
	val->sign = 0;
	for (; j > 0; j--) {
		a = 0;
		for (; i < BYTES_PER_MPI_LIMB; i++) {
			if (++nread > *ret_nread) {
				printk
				    ("MPI: mpi larger than buffer nread=%d ret_nread=%d\n",
				     nread, *ret_nread);
				goto leave;
			}
			a <<= 8;
			a |= *buffer++;
		}
		i = 0;
		val->d[j - 1] = a;
	}

leave:
	*ret_nread = nread;
	return val;
}
EXPORT_SYMBOL_GPL(mpi_read_from_buffer);

Michal Marek's avatar
Michal Marek committed
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
static int count_lzeros(MPI a)
{
	mpi_limb_t alimb;
	int i, lzeros = 0;

	for (i = a->nlimbs - 1; i >= 0; i--) {
		alimb = a->d[i];
		if (alimb == 0) {
			lzeros += sizeof(mpi_limb_t);
		} else {
			lzeros += count_leading_zeros(alimb) / 8;
			break;
		}
	}
	return lzeros;
}

148
149
150
151
152
153
154
/**
 * mpi_read_buffer() - read MPI to a bufer provided by user (msb first)
 *
 * @a:		a multi precision integer
 * @buf:	bufer to which the output will be written to. Needs to be at
 *		leaset mpi_get_size(a) long.
 * @buf_len:	size of the buf.
155
156
157
 * @nbytes:	receives the actual length of the data written on success and
 *		the data to-be-written on -EOVERFLOW in case buf_len was too
 *		small.
158
159
160
 * @sign:	if not NULL, it will be set to the sign of a.
 *
 * Return:	0 on success or error code in case of error
161
 */
162
163
int mpi_read_buffer(MPI a, uint8_t *buf, unsigned buf_len, unsigned *nbytes,
		    int *sign)
164
{
165
	uint8_t *p;
166
167
168
169
170
171
172
#if BYTES_PER_MPI_LIMB == 4
	__be32 alimb;
#elif BYTES_PER_MPI_LIMB == 8
	__be64 alimb;
#else
#error please implement for this limb size.
#endif
173
	unsigned int n = mpi_get_size(a);
Michal Marek's avatar
Michal Marek committed
174
	int i, lzeros;
175

176
	if (!buf || !nbytes)
177
		return -EINVAL;
178
179
180

	if (sign)
		*sign = a->sign;
181

Michal Marek's avatar
Michal Marek committed
182
	lzeros = count_lzeros(a);
183

184
185
186
187
188
	if (buf_len < n - lzeros) {
		*nbytes = n - lzeros;
		return -EOVERFLOW;
	}

189
	p = buf;
Tadeusz Struk's avatar
Tadeusz Struk committed
190
	*nbytes = n - lzeros;
191

192
193
194
	for (i = a->nlimbs - 1 - lzeros / BYTES_PER_MPI_LIMB,
			lzeros %= BYTES_PER_MPI_LIMB;
		i >= 0; i--) {
195
#if BYTES_PER_MPI_LIMB == 4
196
		alimb = cpu_to_be32(a->d[i]);
197
#elif BYTES_PER_MPI_LIMB == 8
198
		alimb = cpu_to_be64(a->d[i]);
199
200
201
#else
#error please implement for this limb size.
#endif
202
203
204
		memcpy(p, (u8 *)&alimb + lzeros, BYTES_PER_MPI_LIMB - lzeros);
		p += BYTES_PER_MPI_LIMB - lzeros;
		lzeros = 0;
205
	}
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
	return 0;
}
EXPORT_SYMBOL_GPL(mpi_read_buffer);

/*
 * mpi_get_buffer() - Returns an allocated buffer with the MPI (msb first).
 * Caller must free the return string.
 * This function does return a 0 byte buffer with nbytes set to zero if the
 * value of A is zero.
 *
 * @a:		a multi precision integer.
 * @nbytes:	receives the length of this buffer.
 * @sign:	if not NULL, it will be set to the sign of the a.
 *
 * Return:	Pointer to MPI buffer or NULL on error
 */
void *mpi_get_buffer(MPI a, unsigned *nbytes, int *sign)
{
Tadeusz Struk's avatar
Tadeusz Struk committed
224
	uint8_t *buf;
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
	unsigned int n;
	int ret;

	if (!nbytes)
		return NULL;

	n = mpi_get_size(a);

	if (!n)
		n++;

	buf = kmalloc(n, GFP_KERNEL);

	if (!buf)
		return NULL;

	ret = mpi_read_buffer(a, buf, n, nbytes, sign);

	if (ret) {
		kfree(buf);
		return NULL;
	}
	return buf;
248
249
250
}
EXPORT_SYMBOL_GPL(mpi_get_buffer);

Tadeusz Struk's avatar
Tadeusz Struk committed
251
252
253
254
255
256
257
258
259
260
261
262
/**
 * mpi_write_to_sgl() - Funnction exports MPI to an sgl (msb first)
 *
 * This function works in the same way as the mpi_read_buffer, but it
 * takes an sgl instead of u8 * buf.
 *
 * @a:		a multi precision integer
 * @sgl:	scatterlist to write to. Needs to be at least
 *		mpi_get_size(a) long.
 * @nbytes:	in/out param - it has the be set to the maximum number of
 *		bytes that can be written to sgl. This has to be at least
 *		the size of the integer a. On return it receives the actual
263
264
 *		length of the data written on success or the data that would
 *		be written if buffer was too small.
Tadeusz Struk's avatar
Tadeusz Struk committed
265
266
267
268
269
270
271
272
 * @sign:	if not NULL, it will be set to the sign of a.
 *
 * Return:	0 on success or error code in case of error
 */
int mpi_write_to_sgl(MPI a, struct scatterlist *sgl, unsigned *nbytes,
		     int *sign)
{
	u8 *p, *p2;
273
274
275
276
277
278
279
#if BYTES_PER_MPI_LIMB == 4
	__be32 alimb;
#elif BYTES_PER_MPI_LIMB == 8
	__be64 alimb;
#else
#error please implement for this limb size.
#endif
Tadeusz Struk's avatar
Tadeusz Struk committed
280
	unsigned int n = mpi_get_size(a);
Michal Marek's avatar
Michal Marek committed
281
	int i, x, y = 0, lzeros, buf_len;
Tadeusz Struk's avatar
Tadeusz Struk committed
282

283
	if (!nbytes)
Tadeusz Struk's avatar
Tadeusz Struk committed
284
285
286
287
288
		return -EINVAL;

	if (sign)
		*sign = a->sign;

Michal Marek's avatar
Michal Marek committed
289
	lzeros = count_lzeros(a);
Tadeusz Struk's avatar
Tadeusz Struk committed
290

291
292
293
294
295
	if (*nbytes < n - lzeros) {
		*nbytes = n - lzeros;
		return -EOVERFLOW;
	}

Tadeusz Struk's avatar
Tadeusz Struk committed
296
297
298
299
	*nbytes = n - lzeros;
	buf_len = sgl->length;
	p2 = sg_virt(sgl);

300
301
302
	for (i = a->nlimbs - 1 - lzeros / BYTES_PER_MPI_LIMB,
			lzeros %= BYTES_PER_MPI_LIMB;
		i >= 0; i--) {
Tadeusz Struk's avatar
Tadeusz Struk committed
303
#if BYTES_PER_MPI_LIMB == 4
304
		alimb = cpu_to_be32(a->d[i]);
Tadeusz Struk's avatar
Tadeusz Struk committed
305
#elif BYTES_PER_MPI_LIMB == 8
306
		alimb = cpu_to_be64(a->d[i]);
Tadeusz Struk's avatar
Tadeusz Struk committed
307
308
309
#else
#error please implement for this limb size.
#endif
310
		if (lzeros) {
311
			y = lzeros;
312
			lzeros = 0;
Tadeusz Struk's avatar
Tadeusz Struk committed
313
314
		}

315
		p = (u8 *)&alimb + y;
Tadeusz Struk's avatar
Tadeusz Struk committed
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342

		for (x = 0; x < sizeof(alimb) - y; x++) {
			if (!buf_len) {
				sgl = sg_next(sgl);
				if (!sgl)
					return -EINVAL;
				buf_len = sgl->length;
				p2 = sg_virt(sgl);
			}
			*p2++ = *p++;
			buf_len--;
		}
		y = 0;
	}
	return 0;
}
EXPORT_SYMBOL_GPL(mpi_write_to_sgl);

/*
 * mpi_read_raw_from_sgl() - Function allocates an MPI and populates it with
 *			     data from the sgl
 *
 * This function works in the same way as the mpi_read_raw_data, but it
 * takes an sgl instead of void * buffer. i.e. it allocates
 * a new MPI and reads the content of the sgl to the MPI.
 *
 * @sgl:	scatterlist to read from
343
 * @nbytes:	number of bytes to read
Tadeusz Struk's avatar
Tadeusz Struk committed
344
345
346
 *
 * Return:	Pointer to a new MPI or NULL on error
 */
347
MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int nbytes)
Tadeusz Struk's avatar
Tadeusz Struk committed
348
349
350
{
	struct scatterlist *sg;
	int x, i, j, z, lzeros, ents;
351
	unsigned int nbits, nlimbs;
Tadeusz Struk's avatar
Tadeusz Struk committed
352
353
354
355
356
357
358
359
360
361
	mpi_limb_t a;
	MPI val = NULL;

	lzeros = 0;
	ents = sg_nents(sgl);

	for_each_sg(sgl, sg, ents, i) {
		const u8 *buff = sg_virt(sg);
		int len = sg->length;

362
		while (len && !*buff) {
Tadeusz Struk's avatar
Tadeusz Struk committed
363
			lzeros++;
364
365
366
			len--;
			buff++;
		}
Tadeusz Struk's avatar
Tadeusz Struk committed
367
368
369
370
371

		if (len && *buff)
			break;

		ents--;
372
		nbytes -= lzeros;
Tadeusz Struk's avatar
Tadeusz Struk committed
373
374
375
376
		lzeros = 0;
	}

	sgl = sg;
377
	nbytes -= lzeros;
Tadeusz Struk's avatar
Tadeusz Struk committed
378
379
380
381
382
383
384
	nbits = nbytes * 8;
	if (nbits > MAX_EXTERN_MPI_BITS) {
		pr_info("MPI: mpi too large (%u bits)\n", nbits);
		return NULL;
	}

	if (nbytes > 0)
385
386
		nbits -= count_leading_zeros(*(u8 *)(sg_virt(sgl) + lzeros)) -
			(BITS_PER_LONG - 8);
Tadeusz Struk's avatar
Tadeusz Struk committed
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401

	nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB);
	val = mpi_alloc(nlimbs);
	if (!val)
		return NULL;

	val->nbits = nbits;
	val->sign = 0;
	val->nlimbs = nlimbs;

	if (nbytes == 0)
		return val;

	j = nlimbs - 1;
	a = 0;
402
403
	z = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
	z %= BYTES_PER_MPI_LIMB;
Tadeusz Struk's avatar
Tadeusz Struk committed
404
405
406
407
408

	for_each_sg(sgl, sg, ents, i) {
		const u8 *buffer = sg_virt(sg) + lzeros;
		int len = sg->length - lzeros;

409
		for (x = 0; x < len; x++) {
Tadeusz Struk's avatar
Tadeusz Struk committed
410
411
412
413
414
415
416
417
418
419
420
421
422
			a <<= 8;
			a |= *buffer++;
			if (((z + x + 1) % BYTES_PER_MPI_LIMB) == 0) {
				val->d[j--] = a;
				a = 0;
			}
		}
		z += x;
		lzeros = 0;
	}
	return val;
}
EXPORT_SYMBOL_GPL(mpi_read_raw_from_sgl);