1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
#ifndef __BIGNUM_H__
#define __BIGNUM_H__
/*
Big number library - arithmetic on multiple-precision unsigned integers.
This library is an implementation of arithmetic on arbitrarily large integers.
The difference between this and other implementations, is that the data structure
has optimal memory utilization (i.e. a 1024 bit integer takes up 128 bytes RAM),
and all memory is allocated statically: no dynamic allocation for better or worse.
Primary goals are correctness, clarity of code and clean, portable implementation.
Secondary goal is a memory footprint small enough to make it suitable for use in
embedded applications.
The current state is correct functionality and adequate performance.
There may well be room for performance-optimizations and improvements.
*/
#include <stdint.h>
#include <assert.h>
/* This macro defines the word size in bytes of the array that constitues the big-number data structure. */
#ifndef WORD_SIZE
#define WORD_SIZE 4
#endif
/* Size of big-numbers in bytes */
#define BN_ARRAY_SIZE (128 / WORD_SIZE)
/* Here comes the compile-time specialization for how large the underlying array size should be. */
/* The choices are 1, 2 and 4 bytes in size with uint32, uint64 for WORD_SIZE==4, as temporary. */
#ifndef WORD_SIZE
#error Must define WORD_SIZE to be 1, 2, 4
#elif (WORD_SIZE == 1)
/* Data type of array in structure */
#define DTYPE uint8_t
/* bitmask for getting MSB */
#define DTYPE_MSB ((DTYPE_TMP)(0x80))
/* Data-type larger than DTYPE, for holding intermediate results of calculations */
#define DTYPE_TMP uint32_t
/* sprintf format string */
#define SPRINTF_FORMAT_STR "%.02x"
#define SSCANF_FORMAT_STR "%2hhx"
/* Max value of integer type */
#define MAX_VAL ((DTYPE_TMP)0xFF)
#elif (WORD_SIZE == 2)
#define DTYPE uint16_t
#define DTYPE_TMP uint32_t
#define DTYPE_MSB ((DTYPE_TMP)(0x8000))
#define SPRINTF_FORMAT_STR "%.04x"
#define SSCANF_FORMAT_STR "%4hx"
#define MAX_VAL ((DTYPE_TMP)0xFFFF)
#elif (WORD_SIZE == 4)
#define DTYPE uint32_t
#define DTYPE_TMP uint64_t
#define DTYPE_MSB ((DTYPE_TMP)(0x80000000))
#define SPRINTF_FORMAT_STR "%.08x"
#define SSCANF_FORMAT_STR "%8x"
#define MAX_VAL ((DTYPE_TMP)0xFFFFFFFF)
#endif
#ifndef DTYPE
#error DTYPE must be defined to uint8_t, uint16_t uint32_t or whatever
#endif
/* Custom assert macro - easy to disable */
#define require(p, msg) assert(p && #msg)
/* Data-holding structure: array of DTYPEs */
struct bn
{
DTYPE array[BN_ARRAY_SIZE];
};
/* Tokens returned by bignum_cmp() for value comparison */
enum { SMALLER = -1, EQUAL = 0, LARGER = 1 };
/* Initialization functions: */
void bignum_init(struct bn* n);
void bignum_from_int(struct bn* n, DTYPE_TMP i);
int bignum_to_int(struct bn* n);
void bignum_from_string(struct bn* n, char* str, int nbytes);
void bignum_to_string(struct bn* n, char* str, int maxsize);
/* Basic arithmetic operations: */
void bignum_add(struct bn* a, struct bn* b, struct bn* c); /* c = a + b */
void bignum_sub(struct bn* a, struct bn* b, struct bn* c); /* c = a - b */
void bignum_mul(struct bn* a, struct bn* b, struct bn* c); /* c = a * b */
void bignum_div(struct bn* a, struct bn* b, struct bn* c); /* c = a / b */
void bignum_mod(struct bn* a, struct bn* b, struct bn* c); /* c = a % b */
void bignum_divmod(struct bn* a, struct bn* b, struct bn* c, struct bn* d); /* c = a/b, d = a%b */
/* Bitwise operations: */
void bignum_and(struct bn* a, struct bn* b, struct bn* c); /* c = a & b */
void bignum_or(struct bn* a, struct bn* b, struct bn* c); /* c = a | b */
void bignum_xor(struct bn* a, struct bn* b, struct bn* c); /* c = a ^ b */
void bignum_lshift(struct bn* a, struct bn* b, int nbits); /* b = a << nbits */
void bignum_rshift(struct bn* a, struct bn* b, int nbits); /* b = a >> nbits */
/* Special operators and comparison */
int bignum_cmp(struct bn* a, struct bn* b); /* Compare: returns LARGER, EQUAL or SMALLER */
int bignum_is_zero(struct bn* n); /* For comparison with zero */
void bignum_inc(struct bn* n); /* Increment: add one to n */
void bignum_dec(struct bn* n); /* Decrement: subtract one from n */
void bignum_pow(struct bn* a, struct bn* b, struct bn* c); /* Calculate a^b -- e.g. 2^10 => 1024 */
void bignum_isqrt(struct bn* a, struct bn* b); /* Integer square root -- e.g. isqrt(5) => 2*/
void bignum_assign(struct bn* dst, struct bn* src); /* Copy src into dst -- dst := src */
#endif /* #ifndef __BIGNUM_H__ */
|
