1 /* Copyright (c) (2010,2011,2012,2013,2014,2015,2016,2017,2018,2019,2020) Apple Inc. All rights reserved.
2 *
3 * corecrypto is licensed under Apple Inc.’s Internal Use License Agreement (which
4 * is contained in the License.txt file distributed with corecrypto) and only to
5 * people who accept that license. IMPORTANT: Any license rights granted to you by
6 * Apple Inc. (if any) are limited to internal use within your organization only on
7 * devices and computers you own or control, for the sole purpose of verifying the
8 * security characteristics and correct functioning of the Apple Software. You may
9 * not, directly or indirectly, redistribute the Apple Software or any portions thereof.
10 */
11
12 #ifndef _CORECRYPTO_CCN_H_
13 #define _CORECRYPTO_CCN_H_
14
15 #include <corecrypto/cc.h>
16 #include <stdint.h>
17 #include <stdarg.h>
18
19 typedef uint8_t cc_byte;
20 typedef size_t cc_size;
21
22 #if CCN_UNIT_SIZE == 8
23 typedef uint64_t cc_unit; // 64 bit unit
24 typedef int64_t cc_int;
25 #define CCN_LOG2_BITS_PER_UNIT 6 // 2^6 = 64 bits
26 #define CC_UNIT_C(x) UINT64_C(x)
27 #if CCN_UINT128_SUPPORT_FOR_64BIT_ARCH
28 typedef unsigned cc_dunit __attribute__((mode(TI))); // 128 bit double width unit
29 typedef signed cc_dint __attribute__((mode(TI)));
30 #else
31 typedef struct cc_dunit {
32 uint64_t l; //do not change the order of the variables. cc_dunit must be little endian
33 uint64_t h;
34 } cc_dunit;
35
36 typedef struct cc_dint {
37 uint64_t l;
38 uint64_t h;
39 } cc_dint;
40 #endif
41
42 #elif CCN_UNIT_SIZE == 4
43 typedef uint32_t cc_unit; // 32 bit unit
44 typedef uint64_t cc_dunit; // 64 bit double width unit
45 typedef int64_t cc_dint;
46 typedef int32_t cc_int;
47 #define CCN_LOG2_BITS_PER_UNIT 5 // 2^5 = 32 bits
48 #define CC_UNIT_C(x) UINT32_C(x)
49
50 #elif CCN_UNIT_SIZE == 2
51 typedef uint16_t cc_unit; // 16 bit unit
52 typedef uint32_t cc_dunit; // 32 bit double width unit
53 #define CCN_LOG2_BITS_PER_UNIT 4 // 2^4 = 16 bits
54 #define CC_UNIT_C(x) UINT16_C(x)
55
56 #elif CCN_UNIT_SIZE == 1
57 typedef uint8_t cc_unit; // 8 bit unit
58 typedef uint16_t cc_dunit; // 16 bit double width unit
59 #define CCN_LOG2_BITS_PER_UNIT 3 // 2^3 = 8 bits
60 #define CC_UNIT_C(x) UINT8_C(x)
61
62 #else
63 #error invalid CCN_UNIT_SIZE
64 #endif
65
66 #define CCN_UNIT_BITS (sizeof(cc_unit) * 8)
67 #define CCN_UNIT_MASK ((cc_unit)~0)
68 #define CCN_UNIT_LOWER_HALF_MASK ((CCN_UNIT_MASK) >> (CCN_UNIT_BITS/2))
69 #define CCN_UNIT_UPPER_HALF_MASK (~CCN_UNIT_LOWER_HALF_MASK)
70 #define CCN_UNIT_HALF_BITS (CCN_UNIT_BITS / 2)
71
72 typedef struct {
73 cc_unit *start; // First cc_unit of the workspace
74 cc_unit *end; // address and beyond NOT TO BE TOUCHED
75 } cc_ws,*cc_ws_t;
76
77 /* Conversions between n sizeof and bits */
78
79 /* Returns the sizeof a ccn vector of length _n_ units. */
80 #define ccn_sizeof_n(_n_) (sizeof(cc_unit) * (_n_))
81
82 /* Returns the count (n) of a ccn vector that can represent _bits_. */
83 #define ccn_nof(_bits_) (((_bits_) + CCN_UNIT_BITS - 1) >> CCN_LOG2_BITS_PER_UNIT)
84
85 /* Returns the sizeof a ccn vector that can represent _bits_. */
86 #define ccn_sizeof(_bits_) (ccn_sizeof_n(ccn_nof(_bits_)))
87
88 /* Returns the count (n) of a ccn vector that can represent _size_ bytes. */
89 #define ccn_nof_size(_size_) (((_size_) + CCN_UNIT_SIZE - 1) / CCN_UNIT_SIZE)
90
91 #define ccn_nof_sizeof(_expr_) ccn_nof_size(sizeof (_expr_))
92
93 /* Return the max number of bits a ccn vector of _n_ units can hold. */
94 #define ccn_bitsof_n(_n_) ((_n_) * CCN_UNIT_BITS)
95
96 /* Return the max number of bits a ccn vector of _size_ bytes can hold. */
97 #define ccn_bitsof_size(_size_) ((_size_) * 8)
98
99 /* Return the size of a ccn of size bytes in bytes. */
100 #define ccn_sizeof_size(_size_) ccn_sizeof_n(ccn_nof_size(_size_))
101
102 /* Returns the value of bit _k_ of _ccn_, both are only evaluated once. */
103 #define ccn_bit(_ccn_, _k_) ({size_t __k = (size_t)(_k_); \
104 1 & ((_ccn_)[ __k >> CCN_LOG2_BITS_PER_UNIT] >> (__k & (CCN_UNIT_BITS - 1)));})
105
106 /* Set the value of bit _k_ of _ccn_ to the value _v_ */
107 #define ccn_set_bit(_ccn_, _k_, _v_) ({size_t __k = (size_t)(_k_); \
108 if (_v_) \
109 (_ccn_)[ __k >> CCN_LOG2_BITS_PER_UNIT] |= CC_UNIT_C(1) << (__k & (CCN_UNIT_BITS - 1)); \
110 else \
111 (_ccn_)[ __k >> CCN_LOG2_BITS_PER_UNIT] &= ~(CC_UNIT_C(1) << (__k & (CCN_UNIT_BITS - 1))); \
112 })
113
114 /* Macros for making ccn constants. You must use list of CCN64_C() instances
115 separated by commas, with an optional smaller sized CCN32_C, CCN16_C, or
116 CCN8_C() instance at the end of the list, when making macros to declare
117 larger sized constants. */
118 #define CCN8_C(a0) CC_UNIT_C(0x##a0)
119
120 #if CCN_UNIT_SIZE >= 2
121 #define CCN16_C(a1,a0) CC_UNIT_C(0x##a1##a0)
122 #define ccn16_v(a0) (a0)
123 #elif CCN_UNIT_SIZE == 1
124 #define CCN16_C(a1,a0) CCN8_C(a0),CCN8_C(a1)
125 #define ccn16_v(a0) (a0 & UINT8_C(0xff)),(a0 >> 8)
126 #endif
127
128 #if CCN_UNIT_SIZE >= 4
129 #define CCN32_C(a3,a2,a1,a0) CC_UNIT_C(0x##a3##a2##a1##a0)
130 #define ccn32_v(a0) (a0)
131 #else
132 #define CCN32_C(a3,a2,a1,a0) CCN16_C(a1,a0),CCN16_C(a3,a2)
133 #define ccn32_v(a0) ccn16_v(a0 & UINT16_C(0xffff)),ccn16_v(a0 >> 16)
134 #endif
135
136 #if CCN_UNIT_SIZE == 8
137 #define CCN64_C(a7,a6,a5,a4,a3,a2,a1,a0) CC_UNIT_C(0x##a7##a6##a5##a4##a3##a2##a1##a0)
138 #define CCN40_C(a4,a3,a2,a1,a0) CC_UNIT_C(0x##a4##a3##a2##a1##a0)
139 #define ccn64_v(a0) (a0)
140 //#define ccn64_32(a1,a0) ((a1 << 32) | a0)
141 //#define ccn_uint64(a,i) (a[i])
142 #else
143 #define CCN64_C(a7,a6,a5,a4,a3,a2,a1,a0) CCN32_C(a3,a2,a1,a0),CCN32_C(a7,a6,a5,a4)
144 #define CCN40_C(a4,a3,a2,a1,a0) CCN32_C(a3,a2,a1,a0),CCN8_C(a4)
145 #define ccn64_v(a0) ccn32_v((uint64_t)a0 & UINT32_C(0xffffffff)),ccn32_v((uint64_t)a0 >> 32)
146 //#define ccn64_32(a1,a0) ccn32_v(a0),ccn32_v(a1)
147 //#define ccn_uint64(a,i) ((uint64_t)ccn_uint32(a, i << 1 + 1) << 32 | (uint64_t)ccn_uint32(a, i << 1))
148 #endif
149
150 /* Macro's for reading uint32_t and uint64_t from ccns, the index is in 32 or
151 64 bit units respectively. */
152 #if CCN_UNIT_SIZE == 8
153 /* #define ccn_uint16(a,i) ((i & 3) == 3 ? ((uint16_t)(a[i >> 2] >> 48)) : \
154 (i & 3) == 2 ? ((uint16_t)(a[i >> 2] >> 32) & UINT16_C(0xffff)) : \
155 (i & 3) == 1 ? ((uint16_t)(a[i >> 2] >> 16) & UINT16_C(0xffff)) : \
156 ((uint16_t)(a[i >> 1] & UINT16_C(0xffff))))
157 */
158 //#define ccn_uint32(a,i) (i & 1 ? ((uint32_t)(a[i >> 1] >> 32)) : ((uint32_t)(a[i >> 1] & UINT32_C(0xffffffff))))
159 #elif CCN_UNIT_SIZE == 4
160 //#define ccn16_v(a0) (a0)
161 //#define ccn32_v(a0) (a0)
162 //#define ccn_uint16(a,i) (i & 1 ? ((uint16_t)(a[i >> 1] >> 16)) : ((uint16_t)(a[i >> 1] & UINT16_C(0xffff))))
163 //#define ccn_uint32(a,i) (a[i])
164 #elif CCN_UNIT_SIZE == 2
165 //#define ccn16_v(a0) (a0)
166 //#define ccn32_v(a0,a1) (a1,a0)
167 //#define ccn_uint16(a,i) (a[i])
168 //#define ccn_uint32(a,i) (((uint32_t)a[i << 1 + 1]) << 16 | (uint32_t)a[i << 1]))
169 #elif CCN_UNIT_SIZE == 1
170 //#define ccn16_v(a0) (a0 & UINT8_C(0xff)),(a0 >> 8)
171 //#define ccn_uint16(a,i) ((uint16_t)((a[i << 1 + 1] << 8) | a[i << 1]))
172 //#define ccn_uint32(a,i) ((uint32_t)ccn_uint16(a, i << 1 + 1) << 16 | (uint32_t)ccn_uint16(a, i << 1))
173 #endif
174
175 /* Macro's for reading uint32_t and uint64_t from ccns, the index is in 32 or
176 64 bit units respectively. */
177 #if CCN_UNIT_SIZE == 8
178
179 #define ccn64_32(a1,a0) (((const cc_unit)a1) << 32 | ((const cc_unit)a0))
180 #define ccn32_32(a0) a0
181 #if __LITTLE_ENDIAN__
182 #define ccn32_32_parse(p,i) (((const uint32_t *)p)[i])
183 #else
184 #define ccn32_32_parse(p,i) (((const uint32_t *)p)[i^1])
185 #endif
186 #define ccn32_32_null 0
187
188 #define ccn64_64(a0) a0
189 #define ccn64_64_parse(p,i) p[i]
190 #define ccn64_64_null 0
191
192 #elif CCN_UNIT_SIZE == 4
193
194 #define ccn32_32(a0) a0
195 #define ccn32_32_parse(p,i) p[i]
196 #define ccn32_32_null 0
197 #define ccn64_32(a1,a0) ccn32_32(a0),ccn32_32(a1)
198
199 #define ccn64_64(a1,a0) a0,a1
200 #define ccn64_64_parse(p,i) p[1+(i<<1)],p[i<<1]
201 #define ccn64_64_null 0,0
202
203 #elif CCN_UNIT_SIZE == 2
204
205 #define ccn32_32(a1,a0) a0,a1
206 #define ccn32_32_parse(p,i) p[1+(i<<1)],p[i<<1]
207 #define ccn32_32_null 0,0
208 #define ccn64_32(a3,a2,a1,a0) ccn32_32(a1,a0),ccn32_32(a3,a2)
209
210 #define ccn64_64(a3,a2,a1,a0) a0,a1,a2,a3
211 #define ccn64_64_parse(p,i) p[3+(i<<2)],p[2+(i<<2)],p[1+(i<<2)],p[i<<2]
212 #define ccn64_64_null 0,0,0,0
213
214 #elif CCN_UNIT_SIZE == 1
215
216 #define ccn32_32(a3,a2,a1,a0) a0,a1,a2,a3
217 #define ccn32_32_parse(p,i) p[3+(i<<2)],p[2+(i<<2)],p[1+(i<<2)],p[i<<2]
218 #define ccn32_32_null 0,0,0,0
219 #define ccn64_32(a7,a6,a5,a4,a3,a2,a1,a0) ccn32_32(a3,a2,a1,a0),ccn32_32(a7,a6,a5,a4)
220
221 #define ccn64_64(a7,a6,a5,a4,a3,a2,a1,a0) a0,a1,a2,a3,a4,a5,a6,a7
222 #define ccn64_64_parse(p,i) p[7+(i<<3)],p[6+(i<<3)],p[5+(i<<3)],p[4+(i<<3)],p[3+(i<<3)],p[2+(i<<3)],p[1+(i<<3)],p[i<<3]
223 #define ccn64_64_null 0,0,0,0,0,0,0,0
224
225 #endif
226
227
228 /* Macros to construct fixed size ccn arrays from 64 or 32 bit quantities. */
229 #define ccn192_64(a2,a1,a0) ccn64_64(a0),ccn64_64(a1),ccn64_64(a2)
230 #define ccn192_32(a5,a4,a3,a2,a1,a0) ccn64_32(a1,a0),ccn64_32(a3,a2),ccn64_32(a5,a4)
231 #define ccn224_32(a6,a5,a4,a3,a2,a1,a0) ccn64_32(a1,a0),ccn64_32(a3,a2),ccn64_32(a5,a4),ccn32_32(a6)
232 #define ccn256_32(a7,a6,a5,a4,a3,a2,a1,a0) ccn64_32(a1,a0),ccn64_32(a3,a2),ccn64_32(a5,a4),ccn64_32(a7,a6)
233 #define ccn384_32(a11,a10,a9,a8,a7,a6,a5,a4,a3,a2,a1,a0) ccn64_32(a1,a0),ccn64_32(a3,a2),ccn64_32(a5,a4),ccn64_32(a7,a6),ccn64_32(a9,a8),ccn64_32(a11,a10)
234
235
236 #define CCN192_C(c7,c6,c5,c4,c3,c2,c1,c0,b7,b6,b5,b4,b3,b2,b1,b0,a7,a6,a5,a4,a3,a2,a1,a0) \
237 CCN64_C(a7,a6,a5,a4,a3,a2,a1,a0),\
238 CCN64_C(b7,b6,b5,b4,b3,b2,b1,b0),\
239 CCN64_C(c7,c6,c5,c4,c3,c2,c1,c0)
240
241 #define CCN200_C(d0,c7,c6,c5,c4,c3,c2,c1,c0,b7,b6,b5,b4,b3,b2,b1,b0,a7,a6,a5,a4,a3,a2,a1,a0) \
242 CCN192_C(c7,c6,c5,c4,c3,c2,c1,c0,b7,b6,b5,b4,b3,b2,b1,b0,a7,a6,a5,a4,a3,a2,a1,a0),\
243 CCN8_C(d0)
244
245 #define CCN224_C(d3,d2,d1,d0,c7,c6,c5,c4,c3,c2,c1,c0,b7,b6,b5,b4,b3,b2,b1,b0,a7,a6,a5,a4,a3,a2,a1,a0) \
246 CCN192_C(c7,c6,c5,c4,c3,c2,c1,c0,b7,b6,b5,b4,b3,b2,b1,b0,a7,a6,a5,a4,a3,a2,a1,a0),\
247 CCN32_C(d3,d2,d1,d0)
248
249 #define CCN232_C(d4,d3,d2,d1,d0,c7,c6,c5,c4,c3,c2,c1,c0,b7,b6,b5,b4,b3,b2,b1,b0,a7,a6,a5,a4,a3,a2,a1,a0) \
250 CCN192_C(c7,c6,c5,c4,c3,c2,c1,c0,b7,b6,b5,b4,b3,b2,b1,b0,a7,a6,a5,a4,a3,a2,a1,a0),\
251 CCN40_C(d4,d3,d2,d1,d0)
252
253 #define CCN256_C(d7,d6,d5,d4,d3,d2,d1,d0,c7,c6,c5,c4,c3,c2,c1,c0,b7,b6,b5,b4,b3,b2,b1,b0,a7,a6,a5,a4,a3,a2,a1,a0) \
254 CCN192_C(c7,c6,c5,c4,c3,c2,c1,c0,b7,b6,b5,b4,b3,b2,b1,b0,a7,a6,a5,a4,a3,a2,a1,a0),\
255 CCN64_C(d7,d6,d5,d4,d3,d2,d1,d0)
256
257 #define CCN384_C(f7,f6,f5,f4,f3,f2,f1,f0,e7,e6,e5,e4,e3,e2,e1,e0,d7,d6,d5,d4,d3,d2,d1,d0,c7,c6,c5,c4,c3,c2,c1,c0,b7,b6,b5,b4,b3,b2,b1,b0,a7,a6,a5,a4,a3,a2,a1,a0) \
258 CCN256_C(d7,d6,d5,d4,d3,d2,d1,d0,c7,c6,c5,c4,c3,c2,c1,c0,b7,b6,b5,b4,b3,b2,b1,b0,a7,a6,a5,a4,a3,a2,a1,a0),\
259 CCN64_C(e7,e6,e5,e4,e3,e2,e1,e0),\
260 CCN64_C(f7,f6,f5,f4,f3,f2,f1,f0)
261
262 #define CCN528_C(i1,i0,h7,h6,h5,h4,h3,h2,h1,h0,g7,g6,g5,g4,g3,g2,g1,g0,f7,f6,f5,f4,f3,f2,f1,f0,e7,e6,e5,e4,e3,e2,e1,e0,d7,d6,d5,d4,d3,d2,d1,d0,c7,c6,c5,c4,c3,c2,c1,c0,b7,b6,b5,b4,b3,b2,b1,b0,a7,a6,a5,a4,a3,a2,a1,a0) \
263 CCN256_C(d7,d6,d5,d4,d3,d2,d1,d0,c7,c6,c5,c4,c3,c2,c1,c0,b7,b6,b5,b4,b3,b2,b1,b0,a7,a6,a5,a4,a3,a2,a1,a0),\
264 CCN256_C(h7,h6,h5,h4,h3,h2,h1,h0,g7,g6,g5,g4,g3,g2,g1,g0,f7,f6,f5,f4,f3,f2,f1,f0,e7,e6,e5,e4,e3,e2,e1,e0),\
265 CCN16_C(i1,i0)
266
267 #define CCN192_N ccn_nof(192)
268 #define CCN224_N ccn_nof(224)
269 #define CCN256_N ccn_nof(256)
270 #define CCN384_N ccn_nof(384)
271 #define CCN512_N ccn_nof(512)
272 #define CCN521_N ccn_nof(521)
273
274 /* Return the number of used units after stripping leading 0 units. */
275 CC_PURE CC_NONNULL((2))
276 cc_size ccn_n(cc_size n, const cc_unit *s) __asm__("_ccn_n");
277
278 /* s >> k -> r return bits shifted out of least significant word in the higest order bits of
279 the retuned value. For example if CCN_UNIT_SIZE == 1, then (0b1101 1110)>>4 returns (0b1110 0000)
280 and sets r==(0b0000 1101).
281 { N bit, scalar -> N bit } N = n * sizeof(cc_unit) * 8
282 the _multi version doesn't return the shifted bits, but does support multiple
283 word shifts. */
284 CC_NONNULL((2, 3))
285 cc_unit ccn_shift_right(cc_size n, cc_unit *r, const cc_unit *s, size_t k) __asm__("_ccn_shift_right");
286
287 /* s == 0 -> return 0 | s > 0 -> return index (starting at 1) of most
288 * significant bit that is 1.
289 * { N bit } N = n * sizeof(cc_unit) * 8
290 *
291 * Runs in constant time, independent of the value of `s`.
292 */
293 CC_NONNULL((2))
294 size_t ccn_bitlen(cc_size n, const cc_unit *s);
295
296 /* s == 0 -> return true | s != 0 -> return false
297 { N bit } N = n * sizeof(cc_unit) * 8 */
298 #define ccn_is_zero(_n_, _s_) (!ccn_n(_n_, _s_))
299
300 /* s == 1 -> return true | s != 1 -> return false
301 { N bit } N = n * sizeof(cc_unit) * 8 */
302 #define ccn_is_one(_n_, _s_) (ccn_n(_n_, _s_) == 1 && _s_[0] == 1)
303
304 #define ccn_is_zero_or_one(_n_, _s_) (((_n_)==0) || ((ccn_n(_n_, _s_) <= 1) && (_s_[0] <= 1)))
305
306 /* s < t -> return - 1 | s == t -> return 0 | s > t -> return 1
307 { N bit, N bit -> int } N = n * sizeof(cc_unit) * 8 */
308 CC_PURE CC_NONNULL((2, 3))
309 int ccn_cmp(cc_size n, const cc_unit *s, const cc_unit *t) __asm__("_ccn_cmp");
310
311 /*! @function ccn_cmpn
312 @abstract Compares the values of two big ints of different lengths.
313
314 @discussion The execution time does not depend on the values of either s or t.
315 The function does not hide ns, nt, or whether ns > nt.
316
317 @param ns Length of s
318 @param s First integer
319 @param nt Length of t
320 @param t Second integer
321
322 @return 1 if s > t, -1 if s < t, 0 otherwise.
323 */
324 CC_NONNULL_ALL
325 int ccn_cmpn(cc_size ns, const cc_unit *s, cc_size nt, const cc_unit *t);
326
327 /* s - t -> r return 1 iff t > s
328 { N bit, N bit -> N bit } N = n * sizeof(cc_unit) * 8 */
329 CC_NONNULL((2, 3, 4))
330 cc_unit ccn_sub(cc_size n, cc_unit *r, const cc_unit *s, const cc_unit *t) __asm__("_ccn_sub");
331
332 /* s - v -> r return 1 iff v > s return 0 otherwise.
333 { N bit, sizeof(cc_unit) * 8 bit -> N bit } N = n * sizeof(cc_unit) * 8 */
334 CC_NONNULL((2, 3))
335 cc_unit ccn_sub1(cc_size n, cc_unit *r, const cc_unit *s, cc_unit v);
336
337 /* s - t -> r return 1 iff t > s
338 { N bit, NT bit -> N bit NT <= N} N = n * sizeof(cc_unit) * 8 */
339 CC_INLINE
340 CC_NONNULL((2, 3, 5))
ccn_subn(cc_size n,cc_unit * r,const cc_unit * s,cc_size nt,const cc_unit * t)341 cc_unit ccn_subn(cc_size n, cc_unit *r, const cc_unit *s,
342 cc_size nt, const cc_unit *t) {
343 assert(n >= nt);
344 return ccn_sub1(n - nt, r + nt, s + nt, ccn_sub(nt, r, s, t));
345 }
346
347
348 /* s + t -> r return carry if result doesn't fit in n bits.
349 { N bit, N bit -> N bit } N = n * sizeof(cc_unit) * 8 */
350 CC_NONNULL((2, 3, 4))
351 cc_unit ccn_add(cc_size n, cc_unit *r, const cc_unit *s, const cc_unit *t) __asm__("_ccn_add");
352
353 /* s + v -> r return carry if result doesn't fit in n bits.
354 { N bit, sizeof(cc_unit) * 8 bit -> N bit } N = n * sizeof(cc_unit) * 8 */
355 CC_NONNULL((2, 3))
356 cc_unit ccn_add1(cc_size n, cc_unit *r, const cc_unit *s, cc_unit v);
357
358 /* s + t -> r return carry if result doesn't fit in n bits
359 { N bit, NT bit -> N bit NT <= N} N = n * sizeof(cc_unit) * 8 */
360 CC_INLINE
361 CC_NONNULL((2, 3, 5))
ccn_addn(cc_size n,cc_unit * r,const cc_unit * s,cc_size nt,const cc_unit * t)362 cc_unit ccn_addn(cc_size n, cc_unit *r, const cc_unit *s,
363 cc_size nt, const cc_unit *t) {
364 assert(n >= nt);
365 return ccn_add1(n - nt, r + nt, s + nt, ccn_add(nt, r, s, t));
366 }
367
368
369 /* s * t -> r_2n r_2n must not overlap with s nor t
370 { n bit, n bit -> 2 * n bit } n = count * sizeof(cc_unit) * 8
371 { N bit, N bit -> 2N bit } N = ccn_bitsof(n) */
372 CC_NONNULL((2, 3, 4))
373 void ccn_mul(cc_size n, cc_unit *r_2n, const cc_unit *s, const cc_unit *t) __asm__("_ccn_mul");
374
375 /* s[0..n) * v -> r[0..n)+return value
376 { N bit, sizeof(cc_unit) * 8 bit -> N + sizeof(cc_unit) * 8 bit } N = n * sizeof(cc_unit) * 8 */
377 CC_NONNULL((2, 3))
378 cc_unit ccn_mul1(cc_size n, cc_unit *r, const cc_unit *s, const cc_unit v);
379
380 /* s[0..n) * v + r[0..n) -> r[0..n)+return value
381 { N bit, sizeof(cc_unit) * 8 bit -> N + sizeof(cc_unit) * 8 bit } N = n * sizeof(cc_unit) * 8 */
382 CC_NONNULL((2, 3))
383 cc_unit ccn_addmul1(cc_size n, cc_unit *r, const cc_unit *s, const cc_unit v);
384
385
386 /*!
387 @function ccn_read_uint
388 @abstract Copy big endian integer and represent it in cc_units
389
390 @param n Input allocated size of the cc_unit output array r
391 @param r Ouput cc_unit array for unsigned integer
392 @param data_nbytes Input byte size of data
393 @param data Input unsigned integer represented in big endian
394
395 @result r is initialized with the big unsigned number
396
397 @return 0 if no error, !=0 if the big number cannot be represented in the allocated cc_unit array.
398
399 @discussion The execution pattern of this function depends on both n and data_nbytes but not on data values except the handling
400 of the error case.
401 */
402
403 CC_NONNULL((2, 4))
404 int ccn_read_uint(cc_size n, cc_unit *r, size_t data_nbytes, const uint8_t *data);
405
406 /* r = (data, len) treated as a big endian byte array, return -1 if data
407 doesn't fit in r, return 0 otherwise.
408 ccn_read_uint strips leading zeroes and doesn't care about sign. */
409 #define ccn_read_int(n, r, data_size, data) ccn_read_uint(n, r, data_size, data)
410
411 /*!
412 @function ccn_write_uint_size
413 @abstract Compute the minimum size required to store an big integer
414
415 @param n Input size of the cc_unit array representing the input
416 @param s Input cc_unit array
417
418 @result Return value is the exact byte size of the big integer
419
420 @discussion
421 The execution flow is independent on the value of the big integer.
422 However, the use of the returned value may leak the position of the most significant byte
423 */
424 CC_PURE CC_NONNULL((2)) size_t ccn_write_uint_size(cc_size n, const cc_unit *s);
425
426 /*!
427 @function ccn_write_uint
428 @abstract Serialize the big integer into a big endian byte buffer
429
430 @param n Input size of the cc_unit array representing the input
431 @param s Input cc_unit array
432 @param out_size Size of the output buffer
433 @param out Output byte array of size at least out_size
434
435 @discussion This function writes exactly
436 MIN(out_size,ccn_write_uint_size(n,s)) bytes truncating to keep the
437 most significant bytes when out_size<ccn_write_uint_size(n,s). The
438 execution flow of function is based on the position of the most
439 significant byte as well as input sizes.
440
441 */
442
443 CC_NONNULL((2, 4))
444 void ccn_write_uint(cc_size n, const cc_unit *s, size_t out_size, void *out);
445
446 /*!
447 @function ccn_write_uint_padded_ct
448 @abstract Serialize the big integer into a big endian byte buffer
449
450 @param n Input size of the cc_unit array representing the input
451 @param s Input cc_unit array
452 @param out_size Size of the output buffer
453 @param out Output byte array of size at least out_size
454
455 @return number of leading zero bytes in case of success, a negative error value in case of failure
456
457 @result This function writes exactly out_size byte, padding with zeroes when necessary.
458 This function DOES NOT support truncation and returns an error if out_size < ccn_write_uint_size
459
460 @discussion The execution flow of function is independent on the value of the big integer
461 However, the processing of the return value by the caller may expose the position of
462 the most significant byte
463 */
464 CC_NONNULL((2, 4))
465 int ccn_write_uint_padded_ct(cc_size n, const cc_unit *s, size_t out_size, uint8_t *out);
466
467 /*!
468 @function ccn_write_uint_padded
469 @abstract Serialize the big integer into a big endian byte buffer
470 Not recommended, for most cases ccn_write_uint_padded_ct is more appropriate
471 Sensitive big integers are exposed since the processing expose the position of the MS byte
472
473 @param n Input size of the cc_unit array representing the input
474 @param s Input cc_unit array
475 @param out_size Size of the output buffer
476 @param out Output byte array of size at least out_size
477
478 @return number of leading zero bytes
479
480 @result This function writes exactly out_size byte, padding with zeroes when necessary.
481 This function DOES support truncation when out_size<ccn_write_uint_size()
482
483 @discussion The execution flow of this function DEPENDS on the position of the most significant byte in
484 case truncation is required.
485 */
486
ccn_write_uint_padded(cc_size n,const cc_unit * s,size_t out_size,uint8_t * out)487 CC_INLINE CC_NONNULL((2, 4)) size_t ccn_write_uint_padded(cc_size n, const cc_unit *s, size_t out_size, uint8_t *out)
488 {
489 size_t offset = 0;
490 // Try first the non-truncation case
491 int offset_int = ccn_write_uint_padded_ct(n, s, out_size, out);
492 if (offset_int >= 0) {
493 // It worked
494 offset = (size_t)offset_int;
495 } else {
496 // Truncation case, execution depends on the position of the MSByte
497 ccn_write_uint(n, s, out_size, out);
498 }
499 return offset;
500 }
501
502
503 /* Return actual size in bytes needed to serialize s as int
504 (adding leading zero if high bit is set). */
505 CC_PURE CC_NONNULL((2))
506 size_t ccn_write_int_size(cc_size n, const cc_unit *s);
507
508 /* Serialize s, to out.
509 First byte of byte stream is the m.s. byte of s,
510 regardless of the size of cc_unit.
511
512 No assumption is made about the alignment of out.
513
514 The out_size argument should be the value returned from ccn_write_int_size,
515 and is also the exact number of bytes this function will write to out.
516 If out_size if less than the value returned by ccn_write_int_size, only the
517 first out_size non-zero most significant octets of s will be written. */
518 CC_NONNULL((2, 4))
519 void ccn_write_int(cc_size n, const cc_unit *s, size_t out_size, void *out);
520
521 /* s -> r
522 { n bit -> n bit } */
523 CC_NONNULL((2, 3))
524 void ccn_set(cc_size n, cc_unit *r, const cc_unit *s);
525
526 CC_INLINE CC_NONNULL((2))
ccn_zero(cc_size n,cc_unit * r)527 void ccn_zero(cc_size n, cc_unit *r) {
528 cc_clear(ccn_sizeof_n(n),r);
529 }
530
531 CC_INLINE CC_NONNULL((2))
ccn_clear(cc_size n,cc_unit * r)532 void ccn_clear(cc_size n, cc_unit *r) {
533 cc_clear(ccn_sizeof_n(n),r);
534 }
535
536 CC_NONNULL((2))
537 void ccn_zero_multi(cc_size n, cc_unit *r, ...);
538
539 CC_INLINE CC_NONNULL((2))
ccn_seti(cc_size n,cc_unit * r,cc_unit v)540 void ccn_seti(cc_size n, cc_unit *r, cc_unit v) {
541 assert(n > 0);
542 r[0] = v;
543 ccn_zero(n - 1, r + 1);
544 }
545
546 CC_INLINE CC_NONNULL((2, 4))
ccn_setn(cc_size n,cc_unit * r,const cc_size s_size,const cc_unit * s)547 void ccn_setn(cc_size n, cc_unit *r, const cc_size s_size, const cc_unit *s) {
548 assert(n > 0);
549 assert(s_size > 0);
550 assert(s_size <= n);
551 ccn_set(s_size, r, s);
552 ccn_zero(n - s_size, r + s_size);
553 }
554
555 #define CC_SWAP_HOST_BIG_64(x) \
556 ((uint64_t)((((uint64_t)(x) & 0xff00000000000000ULL) >> 56) | \
557 (((uint64_t)(x) & 0x00ff000000000000ULL) >> 40) | \
558 (((uint64_t)(x) & 0x0000ff0000000000ULL) >> 24) | \
559 (((uint64_t)(x) & 0x000000ff00000000ULL) >> 8) | \
560 (((uint64_t)(x) & 0x00000000ff000000ULL) << 8) | \
561 (((uint64_t)(x) & 0x0000000000ff0000ULL) << 24) | \
562 (((uint64_t)(x) & 0x000000000000ff00ULL) << 40) | \
563 (((uint64_t)(x) & 0x00000000000000ffULL) << 56)))
564 #define CC_SWAP_HOST_BIG_32(x) \
565 ((((x) & 0xff000000) >> 24) | \
566 (((x) & 0x00ff0000) >> 8) | \
567 (((x) & 0x0000ff00) << 8) | \
568 (((x) & 0x000000ff) << 24))
569 #define CC_SWAP_HOST_BIG_16(x) \
570 ((((x) & 0xff00) >> 8) | \
571 (((x) & 0x00ff) << 8))
572
573 /* This should probably move if we move ccn_swap out of line. */
574 #if CCN_UNIT_SIZE == 8
575 #define CC_UNIT_TO_BIG(x) CC_SWAP_HOST_BIG_64(x)
576 #elif CCN_UNIT_SIZE == 4
577 #define CC_UNIT_TO_BIG(x) CC_SWAP_HOST_BIG_32(x)
578 #elif CCN_UNIT_SIZE == 2
579 #define CC_UNIT_TO_BIG(x) CC_SWAP_HOST_BIG_16(x)
580 #elif CCN_UNIT_SIZE == 1
581 #define CC_UNIT_TO_BIG(x) (x)
582 #else
583 #error unsupported CCN_UNIT_SIZE
584 #endif
585
586 /* Swap units in r in place from cc_unit vector byte order to big endian byte order (or back). */
587 CC_INLINE CC_NONNULL((2))
ccn_swap(cc_size n,cc_unit * r)588 void ccn_swap(cc_size n, cc_unit *r) {
589 cc_unit *e;
590 for (e = r + n - 1; r < e; ++r, --e) {
591 cc_unit t = CC_UNIT_TO_BIG(*r);
592 *r = CC_UNIT_TO_BIG(*e);
593 *e = t;
594 }
595 if (n & 1)
596 *r = CC_UNIT_TO_BIG(*r);
597 }
598
599 CC_INLINE CC_NONNULL((2, 3, 4))
ccn_xor(cc_size n,cc_unit * r,const cc_unit * s,const cc_unit * t)600 void ccn_xor(cc_size n, cc_unit *r, const cc_unit *s, const cc_unit *t) {
601 while (n--) {
602 r[n] = s[n] ^ t[n];
603 }
604 }
605
606 /* Debugging */
607 CC_NONNULL((2))
608 void ccn_print(cc_size n, const cc_unit *s);
609 CC_NONNULL((3))
610 void ccn_lprint(cc_size n, const char *label, const cc_unit *s);
611
612 /* Forward declaration so we don't depend on ccrng.h. */
613 struct ccrng_state;
614
615 #if 0
616 CC_INLINE CC_NONNULL((2, 3))
617 int ccn_random(cc_size n, cc_unit *r, struct ccrng_state *rng) {
618 return (RNG)->generate((RNG), ccn_sizeof_n(n), (unsigned char *)r);
619 }
620 #else
621 #define ccn_random(_n_,_r_,_ccrng_ctx_) \
622 ccrng_generate(_ccrng_ctx_, ccn_sizeof_n(_n_), (unsigned char *)_r_)
623 #endif
624
625 /* Make a ccn of size ccn_nof(nbits) units with up to nbits sized random value. */
626 CC_NONNULL((2, 3))
627 int ccn_random_bits(cc_size nbits, cc_unit *r, struct ccrng_state *rng);
628
629 CC_NONNULL((6, 8))
630 int ccn_div_euclid(cc_size nq, cc_unit *q, cc_size nr, cc_unit *r, cc_size na, const cc_unit *a, cc_size nd, const cc_unit *d);
631
632 #define ccn_div(nq, q, na, a, nd, d) ccn_div_euclid(nq, q, 0, NULL, na, a, nd, d)
633 #define ccn_mod(nr, r, na, a, nd, d) ccn_div_euclid(0 , NULL, nr, r, na, a, nd, d)
634
635 #endif /* _CORECRYPTO_CCN_H_ */
636