* ccn.h
* corecrypto
*
- * Created by Michael Brouwer on 7/25/10.
- * Copyright 2010,2011 Apple Inc. All rights reserved.
+ * Created on 11/16/2010
+ *
+ * Copyright (c) 2010,2011,2012,2013,2014,2015 Apple Inc. All rights reserved.
*
*/
#ifndef _CORECRYPTO_CCN_H_
#define _CORECRYPTO_CCN_H_
-#include <corecrypto/cc_config.h>
-#include <corecrypto/cc_priv.h> /* TODO: Get rid of this include in this header. */
+#include <corecrypto/cc.h>
#include <stdint.h>
#include <stdarg.h>
-
typedef uint8_t cc_byte;
-typedef size_t cc_size;
+typedef size_t cc_size;
#if CCN_UNIT_SIZE == 8
typedef uint64_t cc_unit; // 64 bit unit
-//typedef uint128_t cc_dunit; // 128 bit double width unit
+typedef int64_t cc_int;
#define CCN_LOG2_BITS_PER_UNIT 6 // 2^6 = 64 bits
#define CC_UNIT_C(x) UINT64_C(x)
+ #if CCN_UINT128_SUPPORT_FOR_64BIT_ARCH
+ typedef unsigned cc_dunit __attribute__((mode(TI))); // 128 bit double width unit
+ typedef signed cc_dint __attribute__((mode(TI)));
+ #else
+ typedef struct cc_dunit {
+ uint64_t l; //do not change the order of the variables. cc_dunit must be little endian
+ uint64_t h;
+ } cc_dunit;
+
+ typedef struct cc_dint {
+ uint64_t l;
+ uint64_t h;
+ } cc_dint;
+ #endif
+
#elif CCN_UNIT_SIZE == 4
typedef uint32_t cc_unit; // 32 bit unit
typedef uint64_t cc_dunit; // 64 bit double width unit
+typedef int64_t cc_dint;
+typedef int32_t cc_int;
#define CCN_LOG2_BITS_PER_UNIT 5 // 2^5 = 32 bits
#define CC_UNIT_C(x) UINT32_C(x)
+
#elif CCN_UNIT_SIZE == 2
typedef uint16_t cc_unit; // 16 bit unit
typedef uint32_t cc_dunit; // 32 bit double width unit
#define CCN_LOG2_BITS_PER_UNIT 4 // 2^4 = 16 bits
#define CC_UNIT_C(x) UINT16_C(x)
+
#elif CCN_UNIT_SIZE == 1
typedef uint8_t cc_unit; // 8 bit unit
typedef uint16_t cc_dunit; // 16 bit double width unit
#define CCN_LOG2_BITS_PER_UNIT 3 // 2^3 = 8 bits
#define CC_UNIT_C(x) UINT8_C(x)
+
#else
#error invalid CCN_UNIT_SIZE
#endif
#define CCN_UNIT_BITS (sizeof(cc_unit) * 8)
#define CCN_UNIT_MASK ((cc_unit)~0)
+typedef struct {
+ cc_unit *start; // First cc_unit of the workspace
+ cc_unit *end; // address and beyond NOT TO BE TOUCHED
+} cc_ws,*cc_ws_t;
/* Conversions between n sizeof and bits */
#define ccn_sizeof_n(_n_) (sizeof(cc_unit) * (_n_))
/* Returns the count (n) of a ccn vector that can represent _bits_. */
-#define ccn_nof(_bits_) (((_bits_) + CCN_UNIT_BITS - 1) / CCN_UNIT_BITS)
+#define ccn_nof(_bits_) (((_bits_) + CCN_UNIT_BITS - 1) >> CCN_LOG2_BITS_PER_UNIT)
/* Returns the sizeof a ccn vector that can represent _bits_. */
#define ccn_sizeof(_bits_) (ccn_sizeof_n(ccn_nof(_bits_)))
/* Returns the value of bit _k_ of _ccn_, both are only evaluated once. */
#define ccn_bit(_ccn_, _k_) ({__typeof__ (_k_) __k = (_k_); \
- 1 & ((_ccn_)[__k / CCN_UNIT_BITS] >> (__k & (CCN_UNIT_BITS - 1)));})
+ 1 & ((_ccn_)[ __k >> CCN_LOG2_BITS_PER_UNIT] >> (__k & (CCN_UNIT_BITS - 1)));})
+/* Set the value of bit _k_ of _ccn_ to the value _v_ */
#define ccn_set_bit(_ccn_, _k_, _v_) ({__typeof__ (_k_) __k = (_k_); \
if (_v_) \
- (_ccn_)[__k/CCN_UNIT_BITS] |= CC_UNIT_C(1) << (__k & (CCN_UNIT_BITS - 1)); \
+ (_ccn_)[ __k >> CCN_LOG2_BITS_PER_UNIT] |= CC_UNIT_C(1) << (__k & (CCN_UNIT_BITS - 1)); \
else \
- (_ccn_)[__k/CCN_UNIT_BITS] &= ~(CC_UNIT_C(1) << (__k & (CCN_UNIT_BITS - 1))); \
+ (_ccn_)[ __k >> CCN_LOG2_BITS_PER_UNIT] &= ~(CC_UNIT_C(1) << (__k & (CCN_UNIT_BITS - 1))); \
})
/* Macros for making ccn constants. You must use list of CCN64_C() instances
64 bit units respectively. */
#if CCN_UNIT_SIZE == 8
-#define ccn64_32(a1,a0) (((cc_unit)a1) << 32 | ((cc_unit)a0))
+#define ccn64_32(a1,a0) (((const cc_unit)a1) << 32 | ((const cc_unit)a0))
#define ccn32_32(a0) a0
#if __LITTLE_ENDIAN__
-#define ccn32_32_parse(p,i) (((uint32_t *)p)[i])
+#define ccn32_32_parse(p,i) (((const uint32_t *)p)[i])
#else
-#define ccn32_32_parse(p,i) (((uint32_t *)p)[i^1])
+#define ccn32_32_parse(p,i) (((const uint32_t *)p)[i^1])
#endif
#define ccn32_32_null 0
#define CCN224_N ccn_nof(224)
#define CCN256_N ccn_nof(256)
#define CCN384_N ccn_nof(384)
+#define CCN512_N ccn_nof(512)
#define CCN521_N ccn_nof(521)
-#if defined(_ARM_ARCH_6) || defined(_ARM_ARCH_7)
-#if CCN_USE_BUILTIN_CLZ
-CC_INLINE CC_CONST
-cc_unit cc_clz(cc_unit data)
-{
- return __builtin_clzl(data);
-}
-#else
-CC_INLINE CC_CONST
-cc_unit cc_clz(cc_unit data)
-{
- __asm__ ("clz %0, %1\n" : "=l" (data) : "l" (data));
- return data;
-}
-#endif /* CCN_USE_BUILTIN_CLZ */
-#endif /* !defined(_ARM_ARCH_6) && !defined(_ARM_ARCH_7) */
-
-
-#if CCN_N_INLINE
-/* Return the number of used units after stripping leading 0 units. */
-CC_INLINE CC_PURE CC_NONNULL2
-cc_size ccn_n(cc_size n, const cc_unit *s) {
-#if 1
- while (n-- && s[n] == 0) {}
- return n + 1;
-#elif 0
- while (n && s[n - 1] == 0) {
- n -= 1;
- }
- return n;
-#else
- if (n & 1) {
- if (s[n - 1])
- return n;
- n &= ~1;
- }
- if (n & 2) {
- cc_unit a[2] = { s[n - 1], s[n - 2] };
- if (a[0])
- return n - 1;
- if (a[1])
- return n - 2;
- n &= ~2;
- }
- while (n) {
- cc_unit a[4] = { s[n - 1], s[n - 2], s[n - 3], s[n - 4] };
- if (a[0])
- return n - 1;
- if (a[1])
- return n - 2;
- if (a[2])
- return n - 3;
- if (a[3])
- return n - 4;
- n -= 4;
- }
- return n;
-#endif
-}
-#else
/* Return the number of used units after stripping leading 0 units. */
CC_PURE CC_NONNULL2
cc_size ccn_n(cc_size n, const cc_unit *s);
-#endif
/* s >> k -> r return bits shifted out of least significant word in bits [0, n>
{ N bit, scalar -> N bit } N = n * sizeof(cc_unit) * 8
#define ccn_is_zero_or_one(_n_, _s_) (((_n_)==0) || ((ccn_n(_n_, _s_) <= 1) && (_s_[0] <= 1)))
-#if CCN_CMP_INLINE
-CC_INLINE CC_PURE CC_NONNULL((2, 3))
-int ccn_cmp(cc_size n, const cc_unit *s, const cc_unit *t) {
- while (n) {
- n--;
- cc_unit si = s[n];
- cc_unit ti = t[n];
- if (si != ti)
- return si > ti ? 1 : -1;
- }
- return n;
-}
-#else
/* s < t -> return - 1 | s == t -> return 0 | s > t -> return 1
{ N bit, N bit -> int } N = n * sizeof(cc_unit) * 8 */
CC_PURE CC_NONNULL((2, 3))
int ccn_cmp(cc_size n, const cc_unit *s, const cc_unit *t);
-#endif
/* s < t -> return - 1 | s == t -> return 0 | s > t -> return 1
{ N bit, M bit -> int } N = ns * sizeof(cc_unit) * 8 M = nt * sizeof(cc_unit) * 8 */
CC_NONNULL((2, 3, 4))
cc_unit ccn_sub(cc_size n, cc_unit *r, const cc_unit *s, const cc_unit *t);
+/* |s - t| -> r return 1 iff t > s, 0 otherwise */
+cc_unit ccn_abs(cc_size n, cc_unit *r, const cc_unit *s, const cc_unit *t);
+
/* s - v -> r return 1 iff v > s return 0 otherwise.
{ N bit, sizeof(cc_unit) * 8 bit -> N bit } N = n * sizeof(cc_unit) * 8 */
CC_NONNULL((2, 3))
return ccn_add1(n - nt, r + nt, s + nt, ccn_add(nt, r, s, t));
}
-CC_NONNULL((4, 5))
-void ccn_divmod(cc_size n, cc_unit *q, cc_unit *r, const cc_unit *s, const cc_unit *t);
-
CC_NONNULL((2, 3, 4))
void ccn_lcm(cc_size n, cc_unit *r2n, const cc_unit *s, const cc_unit *t);
CC_NONNULL((2, 3, 4))
void ccn_mul(cc_size n, cc_unit *r_2n, const cc_unit *s, const cc_unit *t);
+/* s * t -> r_2n r_2n must not overlap with s nor t
+ { n bit, n bit -> 2 * n bit } n = count * sizeof(cc_unit) * 8
+ { N bit, N bit -> 2N bit } N = ccn_bitsof(n)
+ Provide a workspace for potential speedup */
+CC_NONNULL((2, 3, 4, 5))
+void ccn_mul_ws(cc_size count, cc_unit *r, const cc_unit *s, const cc_unit *t, cc_ws_t ws);
+
/* s[0..n) * v -> r[0..n)+return value
{ N bit, sizeof(cc_unit) * 8 bit -> N + sizeof(cc_unit) * 8 bit } N = n * sizeof(cc_unit) * 8 */
CC_NONNULL((2, 3))
CC_NONNULL((2, 4))
void ccn_write_int(cc_size n, const cc_unit *s, size_t out_size, void *out);
+#if CCN_DEDICATED_SQR
+
+/* s^2 -> r
+ { n bit -> 2 * n bit } */
+CC_NONNULL((2, 3))
+void ccn_sqr(cc_size n, cc_unit *r, const cc_unit *s);
+
+/* s^2 -> r
+ { n bit -> 2 * n bit } */
+CC_NONNULL((2, 3, 4))
+void ccn_sqr_ws(cc_size n, cc_unit *r, const cc_unit *s, cc_ws_t ws);
+
+#else
/* s^2 -> r
{ n bit -> 2 * n bit } */
ccn_mul(n, r, s, s);
}
+/* s^2 -> r
+ { n bit -> 2 * n bit } */
+CC_INLINE CC_NONNULL((2, 3, 4))
+void ccn_sqr_ws(cc_size n, cc_unit *r, const cc_unit *s, cc_ws_t ws) {
+ ccn_mul_ws(n, r, s, s, ws);
+}
+
+#endif
+
/* s -> r
{ n bit -> n bit } */
CC_NONNULL((2, 3))
CC_INLINE CC_NONNULL2
void ccn_zero(cc_size n, cc_unit *r) {
- CC_BZERO(r, ccn_sizeof_n(n));
+ cc_zero(ccn_sizeof_n(n),r);
+}
+
+CC_INLINE CC_NONNULL2
+void ccn_clear(cc_size n, cc_unit *r) {
+ cc_clear(ccn_sizeof_n(n),r);
}
CC_NONNULL2
void ccn_zero_multi(cc_size n, cc_unit *r, ...);
-/* Burn (zero fill or otherwise overwrite) n cc_units of stack space. */
-void ccn_burn_stack(cc_size n);
-
CC_INLINE CC_NONNULL2
void ccn_seti(cc_size n, cc_unit *r, cc_unit v) {
/* assert(n > 0); */
CC_NONNULL((2, 3))
int ccn_random_bits(cc_size nbits, cc_unit *r, struct ccrng_state *rng);
+/*!
+ @brief ccn_make_recip(cc_size nd, cc_unit *recip, const cc_unit *d) computes the reciprocal of d: recip = 2^2b/d where b=bitlen(d)
+
+ @param nd length of array d
+ @param recip returned reciprocal of size nd+1
+ @param d input number d
+*/
+CC_NONNULL((2, 3))
+void ccn_make_recip(cc_size nd, cc_unit *recip, const cc_unit *d);
+
+CC_NONNULL((6, 8))
+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);
+
+#define ccn_div(nq, q, na, a, nd, d) ccn_div_euclid(nq, q, 0, NULL, na, a, nd, d)
+#define ccn_mod(nr, r, na, a, nd, d) ccn_div_euclid(0 , NULL, nr, r, na, a, nd, d)
+
+/*!
+ @brief ccn_div_use_recip(nq, q, nr, r, na, a, nd, d) comutes q=a/d and r=a%d
+ @discussion q and rcan be NULL. Reads na from a and nd from d. Writes nq in q and nr in r. nq and nr must be large enough to accomodate results, otherwise error is retuned. Execution time depends on the size of a. Computation is perfomed on of fixedsize and the leadig zeros of a of q are are also used in the computation.
+ @param nq length of array q that hold the quotients. The maximum length of quotient is the actual length of dividend a
+ @param q returned quotient. If nq is larger than needed, it is filled with leading zeros. If it is smaller, error is returned. q can be set to NULL, if not needed.
+ @param nr length of array r that hold the remainder. The maximum length of remainder is the actual length of divisor d
+ @param r returned remainder. If nr is larger than needed, it is filled with leading zeros. Ifi is smaller error is returned. r can be set to NULL if not required.
+ @param na length of dividend. Dividend may have leading zeros.
+ @param a input Dividend
+ @param nd length of input divisor. Divisor may have leading zeros.
+ @param d input Divisor
+ @param recip_d The reciprocal of d, of length nd+1.
+
+ @return returns 0 if successful, negative of error.
+ */
+CC_NONNULL((6, 8, 9))
+int ccn_div_use_recip(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, const cc_unit *recip_d);
+
#endif /* _CORECRYPTO_CCN_H_ */
projects / apple / xnu.git / blobdiff