xref: /xnu-10063.121.3/osfmk/corecrypto/ccn_internal.h (revision 2c2f96dc2b9a4408a43d3150ae9c105355ca3daa)

/* Copyright (c) (2017-2023) Apple Inc. All rights reserved.
 *
 * corecrypto is licensed under Apple Inc.’s Internal Use License Agreement (which
 * is contained in the License.txt file distributed with corecrypto) and only to
 * people who accept that license. IMPORTANT:  Any license rights granted to you by
 * Apple Inc. (if any) are limited to internal use within your organization only on
 * devices and computers you own or control, for the sole purpose of verifying the
 * security characteristics and correct functioning of the Apple Software.  You may
 * not, directly or indirectly, redistribute the Apple Software or any portions thereof.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 *
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 *
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 *
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */

#ifndef _CORECRYPTO_CCN_INTERNAL_H
#define _CORECRYPTO_CCN_INTERNAL_H

#include <corecrypto/ccn.h>
#include "cc_workspaces.h"
#include "cc_memory.h"
#include "cc_internal.h"

CC_PTRCHECK_CAPABLE_HEADER()

#if CCN_UNIT_SIZE == 8

 #if CC_DUNIT_SUPPORTED
typedef unsigned cc_dunit __attribute__((mode(TI)));
 #endif

#define cc_clz_nonzero cc_clz64
#define cc_ctz_nonzero cc_ctz64
#define CC_STORE_UNIT_BE(x, out) cc_store64_be(x, out)
#define CC_LOAD_UNIT_BE(x, out) (x = cc_load64_be(out))

#elif CCN_UNIT_SIZE == 4

typedef uint64_t cc_dunit;

#define cc_clz_nonzero cc_clz32
#define cc_ctz_nonzero cc_ctz32
#define CC_STORE_UNIT_BE(x, out) cc_store32_be(x, out)
#define CC_LOAD_UNIT_BE(x, out) (x = cc_load32_be(out))

#else

#error Unsupported CCN_UNIT_SIZE

#endif

#if CC_DUNIT_SUPPORTED

// r := x + y
#define CC_DUNIT_ADD(r, x, y, tmp)      \
    do {                             \
	tmp = ((cc_dunit)(x)) + (y); \
	r = (cc_unit)tmp;            \
    } while (0);

// r := x + y + (tmp >> 64)
#define CC_DUNIT_ADC(r, x, y, tmp)              \
    do {                                     \
	cc_unit _c = (tmp) >> CCN_UNIT_BITS; \
	tmp = ((cc_dunit)(x)) + (y) + _c;    \
	r = (cc_unit)tmp;                    \
    } while (0);

// r := x - y
#define CC_DUNIT_SUB(r, x, y, tmp)      \
    do {                             \
	tmp = ((cc_dunit)(x)) - (y); \
	r = (cc_unit)tmp;            \
    } while (0);

// r := x - y - (tmp >> 127)
#define CC_DUNIT_SBC(r, x, y, tmp)                        \
    do {                                               \
	cc_unit _b = (tmp) >> (2 * CCN_UNIT_BITS - 1); \
	tmp = ((cc_dunit)(x)) - (y) - _b;              \
	r = (cc_unit)tmp;                              \
    } while (0);

// (hi,lo) += (x * y)
#define CC_DUNIT_MUL(x, y, hi, lo, tmp)  \
    do {                              \
	tmp = (cc_dunit)(x) * (y);    \
	lo += (tmp) & CCN_UNIT_MASK;  \
	hi += (tmp) >> CCN_UNIT_BITS; \
    } while (0);

// (hi,lo) += (x * y) * i
#define CC_DUNIT_MULI(x, y, hi, lo, tmp, i)      \
    do {                                      \
	tmp = (cc_dunit)(x) * (y);            \
	lo += ((tmp) & CCN_UNIT_MASK) * (i);  \
	hi += ((tmp) >> CCN_UNIT_BITS) * (i); \
    } while (0);

// r := lo and (hi,lo) >>= 64
#define CC_STORE_LO(r, hi, lo)        \
    do {                           \
	r = (cc_unit)lo;           \
	hi += lo >> CCN_UNIT_BITS; \
	lo = hi & CCN_UNIT_MASK;   \
	hi >>= CCN_UNIT_BITS;      \
    } while (0);

#endif

CC_NONNULL((2, 3))
void ccn_set(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s);

CC_INLINE
CC_NONNULL((2, 4))
void
ccn_setn(cc_size n, cc_unit *cc_counted_by (n)r, const cc_size s_size, const cc_unit *cc_counted_by (s_size)s)
{
	cc_assert(n > 0 && s_size <= n);

	if (s_size > 0) {
		ccn_set(s_size, r, s);
	}

	ccn_zero(n - s_size, r + s_size);
}

CC_INLINE
CC_NONNULL((2))
void
ccn_clear(cc_size n, cc_unit *cc_sized_by (n)r)
{
	cc_clear(ccn_sizeof_n(n), r);
}

/* Returns the value of bit _k_ of _ccn_, both are only evaluated once.  */
CC_INLINE cc_unit
ccn_bit(const cc_unit *cc_indexable x, size_t k)
{
	return 1 & (x[k >> CCN_LOG2_BITS_PER_UNIT] >> (k & (CCN_UNIT_BITS - 1)));
}

/* |s - t| -> r return 1 iff t > s, 0 otherwise */
CC_WARN_RESULT
cc_unit ccn_abs(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, const cc_unit *cc_counted_by(n) t);

/* Returns the number of bits which are zero before the first one bit
 *  counting from least to most significant bit. */
CC_WARN_RESULT
CC_NONNULL((2))
size_t ccn_trailing_zeros(cc_size n, const cc_unit *s);

/*! @function ccn_shift_right
 *  @abstract Shifts s to the right by k bits, where 0 <= k < CCN_UNIT_BITS.
 *
 *  @param n Length of r and s
 *  @param r Resulting big int.
 *  @param s Big int to shift.
 *  @param k Number of bits to shift by.
 */
CC_NONNULL_ALL
void ccn_shift_right(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, size_t k) __asm__("_ccn_shift_right");

/*! @function ccn_shift_right_multi
 *  @abstract Constant-time, SPA-safe, right shift.
 *
 *  @param n Length of r and s as number of cc_units.
 *  @param r Destination, can overlap with s.
 *  @param s Input that's shifted by k bits.
 *  @param k Number of bits by which to shift s to the right.
 */
CC_NONNULL_ALL
void ccn_shift_right_multi(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, size_t k);

/* s << k -> r return bits shifted out of most significant word in bits [0, n>
 *  { N bit, scalar -> N bit } N = n * sizeof(cc_unit) * 8
 *  the _multi version doesn't return the shifted bits, but does support multiple
 *  word shifts */
CC_NONNULL_ALL
void ccn_shift_left(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, size_t k) __asm__("_ccn_shift_left");

CC_NONNULL_ALL
void ccn_shift_left_multi(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, size_t k);

// Conditionally swap the content of r0 and r1 buffers in constant time
// r0:r1 <- r1*k1 + s0*(k1-1)
CC_NONNULL_ALL
void ccn_cond_swap(cc_size n, cc_unit ki, cc_unit *cc_counted_by(n) r0, cc_unit *cc_counted_by(n) r1);

/*! @function ccn_cond_shift_right
 *  @abstract Constant-time, SPA-safe, conditional right shift.
 *
 *  @param n Length of each of r and a as number of cc_units.
 *  @param s Selector bit (0 or 1).
 *  @param r Destination, can overlap with a.
 *  @param a Input that's shifted by k bits, if s=1.
 *  @param k Number of bits by which to shift a to the right, if s=1.
 *         (k must not be larger than CCN_UNIT_BITS.)
 */
CC_NONNULL_ALL
void ccn_cond_shift_right(cc_size n, cc_unit s, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) a, size_t k);

/*! @function ccn_cond_neg
 *  @abstract Constant-time, SPA-safe, conditional negation.
 *
 *  @param n Length of each of r and x as number of cc_units.
 *  @param s Selector bit (0 or 1).
 *  @param r Destination, can overlap with x.
 *  @param x Input that's negated, if s=1.
 */
void ccn_cond_neg(cc_size n, cc_unit s, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) x);

/*! @function ccn_cond_shift_right_carry
 *  @abstract Constant-time, SPA-safe, conditional right shift.
 *
 *  @param n Length of each of r and a as number of cc_units.
 *  @param s Selector bit (0 or 1).
 *  @param r Destination, can overlap with a.
 *  @param a Input that's shifted by k bits, if s=1.
 *  @param k Number of bits by which to shift a to the right, if s=1.
 *         (k must not be larger than CCN_UNIT_BITS.)
 *  @param c Carry bit(s), the most significant bit(s) after shifting, if s=1.
 */
CC_NONNULL_ALL
void ccn_cond_shift_right_carry(cc_size n, cc_unit s, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) a, size_t k, cc_unit c);

/*! @function ccn_cond_add
 *  @abstract Constant-time, SPA-safe, conditional addition.
 *          Computes r:= x + y, iff s = 1. Set r := x otherwise.
 *
 *  @param n Length of each of r, x, and y as number of cc_units.
 *  @param s Selector bit (0 or 1).
 *  @param r Destination, can overlap with x or y.
 *  @param x First addend.
 *  @param y Second addend.
 *
 *  @return The carry bit, if s=1. 0 otherwise.
 */
CC_WARN_RESULT CC_NONNULL_ALL
cc_unit ccn_cond_add(cc_size n, cc_unit s, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) x, const cc_unit *cc_counted_by(n) y);

/*! @function ccn_cond_rsub
 *  @abstract Constant-time, SPA-safe, conditional reverse subtraction.
 *          Computes r := y - x, iff s = 1. Sets r := x otherwise.
 *
 *  @param n Length of each of r, x, and y as number of cc_units.
 *  @param s Selector bit (0 or 1).
 *  @param r Destination, can overlap with x or y.
 *  @param x Subtrahend.
 *  @param y Minuend.
 *
 *  @return The carry bit, if s=1. 0 otherwise.
 */
CC_WARN_RESULT CC_NONNULL_ALL
cc_unit ccn_cond_rsub(cc_size n, cc_unit s, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) x, const cc_unit *cc_counted_by(n) y);

/*! @function ccn_cond_sub
 *  @abstract Constant-time, SPA-safe, conditional subtraction.
 *          Computes r := x - y, iff s = 1. Sets r := x otherwise.
 *
 *  @param n Length of each of r, x, and y as number of cc_units.
 *  @param s Selector bit (0 or 1).
 *  @param r Destination, can overlap with x or y.
 *  @param x Minuend.
 *  @param y Subtrahend.
 *
 *  @return The carry bit, if s=1. 0 otherwise.
 */
CC_WARN_RESULT CC_NONNULL_ALL
cc_unit ccn_cond_sub(cc_size n, cc_unit s, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) x, const cc_unit *cc_counted_by(n) y);

/*! @function ccn_cond_clear
 *  @abstract Constant-time, SPA-safe, conditional zeroization.
 *          Sets r := 0, if s = 1. Does nothing otherwise.
 *
 *  @param n Length of r as number of cc_units.
 *  @param s Selector bit (0 or 1).
 *  @param r Destination, can overlap with x or y.
 */
CC_NONNULL_ALL
void ccn_cond_clear(cc_size n, cc_unit s, cc_unit *r);

/*! @function ccn_mux
 *  @abstract Constant-time, SPA-safe multiplexer. Sets r = (s ? a : b).
 *
 *  @discussion This works like a normal multiplexer (s & a) | (~s & b) but is
 *            slightly more complicated and expensive. Out of `s` we build
 *            half-word masks to hide extreme Hamming weights of operands.
 *
 *  @param n Length of each of r, a, and b as number of cc_units.
 *  @param s Selector bit (0 or 1).
 *  @param r Destination, can overlap with a or b.
 *  @param a Input selected when s=1.
 *  @param b Input selected when s=0.
 */
CC_NONNULL_ALL
void ccn_mux(cc_size n, cc_unit s, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) a, const cc_unit *cc_counted_by(n) b);

/*! @function ccn_gcd_ws
 *  @abstract Computes the greatest common divisor of s and t,
 *          r = gcd(s,t) / 2^k, and returns k.
 *
 *  @param ws Workspace.
 *  @param rn Length of r as a number of cc_units.
 *  @param r  Resulting GCD.
 *  @param sn Length of s as a number of cc_units.
 *  @param s  First number s.
 *  @param tn Length of t as a number of cc_units.
 *  @param t  First number t.
 *
 *  @return The factor of two to shift r by to compute the actual GCD.
 */
CC_WARN_RESULT
CC_NONNULL_ALL
size_t ccn_gcd_ws(cc_ws_t ws, cc_size rn, cc_unit *cc_counted_by(rn) r, cc_size sn, const cc_unit *cc_counted_by(sn) s, cc_size tn, const cc_unit *cc_counted_by(tn) t);

/*! @function ccn_lcm_ws
 *  @abstract Computes lcm(s,t), the least common multiple of s and t.
 *
 *  @param ws  Workspace.
 *  @param n   Length of s,t as a number of cc_units.
 *  @param r2n Resulting LCM of length 2*n.
 *  @param s   First number s.
 *  @param t   First number t.
 */
void ccn_lcm_ws(cc_ws_t ws, cc_size n, cc_unit *cc_unsafe_indexable r2n, const cc_unit *cc_counted_by(n)s, const cc_unit *cc_counted_by(n)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) */
CC_NONNULL((2, 3, 4))
void ccn_mul(cc_size n, cc_unit *cc_unsafe_indexable r_2n, const cc_unit *cc_counted_by(n)s, const cc_unit *cc_counted_by(n)t) __asm__("_ccn_mul");

/* 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_WARN_RESULT
CC_NONNULL((2, 3))
cc_unit ccn_mul1(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, const cc_unit v);

/* s[0..n) * v[0..nv] -> r[0..n+nv)
*  { n bit, nv bit -> n + nv bit} n = count * sizeof(cc_unit) * 8
*  { N bit, NV bit -> N + NV bit} N = ccn_bitsof(n), NV = ccn_bitsof(nv)
*  r, s, and v should not overlap
*  Leaks n and nv through timing */
CC_NONNULL_ALL
void ccn_muln(cc_size n, cc_unit *cc_counted_by(n + nv) r, const cc_unit *cc_counted_by(n) s, cc_size nv, const cc_unit *cc_counted_by(n) v);

/* s[0..n) * v + r[0..n) -> 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_WARN_RESULT
CC_NONNULL((2, 3))
cc_unit ccn_addmul1(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, const cc_unit v);

/* 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_ALL
void ccn_mul_ws(cc_ws_t ws, cc_size count, cc_unit *cc_unsafe_indexable r, const cc_unit *cc_counted_by(count)s, const cc_unit *cc_counted_by(count)t);

/* s^2 -> r
 *  { n bit -> 2 * n bit } */
CC_NONNULL_ALL
void ccn_sqr_ws(cc_ws_t ws, cc_size n, cc_unit *cc_unsafe_indexable r, const cc_unit *cc_counted_by(n)s);

/*! @function ccn_mod_ws
 *  @abstract Computes r = a % d.
 *
 *  @discussion Use CCN_DIVMOD_WORKSPACE_N(n) for the workspace.
 *
 *  @param ws  Workspace
 *  @param na  Length of a as a number of cc_units.
 *  @param a   The dividend a.
 *  @param n   Length of r,d as a number of cc_units.
 *  @param r   The resulting remainder.
 *  @param d   The divisor d.
 */
#define ccn_mod_ws(ws, na, a, n, r, d) ccn_divmod_ws(ws, na, a, 0, NULL, n, r, d)
#define ccn_mod(na, a, n, r, d) ccn_divmod(na, a, 0, NULL, n, r, d)

/*! @function ccn_neg
 *  @abstract Computes the two's complement of x.
 *
 *  @param n  Length of r and x
 *  @param r  Result of the negation
 *  @param x  Number to negate
 */
CC_NONNULL_ALL
void ccn_neg(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) x);

/*! @function ccn_invert
 *  @abstract Computes x^-1 (mod 2^w).
 *
 *  @param x  Number to invert
 *
 *  @return x^-1 (mod 2^w)
 */
CC_WARN_RESULT
CC_CONST CC_NONNULL_ALL
CC_INLINE cc_unit
ccn_invert(cc_unit x)
{
	cc_assert(x & 1);

	// Initial precision is 5 bits.
	cc_unit y = (3 * x) ^ 2;

	// Newton-Raphson iterations.
	// Precision doubles with every step.
	y *= 2 - y * x;
	y *= 2 - y * x;
	y *= 2 - y * x;
#if CCN_UNIT_SIZE == 8
	y *= 2 - y * x;
#endif

	cc_assert(y * x == 1);
	return y;
}

/*! @function ccn_div_exact_ws
 *  @abstract Computes q = a / d where a = 0 (mod d).
 *
 *  @param ws  Workspace
 *  @param n   Length of q,a,d as a number of cc_units.
 *  @param q   The resulting exact quotient.
 *  @param a   The dividend a.
 *  @param d   The divisor d.
 */
CC_NONNULL_ALL
void ccn_div_exact_ws(cc_ws_t ws, cc_size n, cc_unit *cc_counted_by(n) q, const cc_unit *cc_counted_by(n) a, const cc_unit *cc_counted_by(n) d);

/*! @function ccn_divides1
 *  @abstract Returns whether q divides x.
 *
 *  @param n  Length of x as a number of cc_units.
 *  @param x  The dividend x.
 *  @param q  The divisor q.
 *
 *  @return True if q divides x without remainder, false otherwise.
 */
CC_WARN_RESULT
CC_NONNULL_ALL
bool ccn_divides1(cc_size n, const cc_unit *cc_counted_by(n)x, cc_unit q);

/*! @function ccn_select
 *  @abstract Select r[i] in constant-time, not revealing i via cache-timing.
 *
 *  @param start Start index.
 *  @param end   End index (length of r).
 *  @param r     Big int r.
 *  @param i     Offset into r.
 *
 *  @return r[i], or zero if start > i or end < i.
 */
CC_WARN_RESULT
CC_INLINE cc_unit
ccn_select(cc_size start, cc_size end, const cc_unit *cc_counted_by(end)r, cc_size i)
{
	cc_unit ri = 0;

	for (cc_size j = start; j < end; j++) {
		cc_size i_neq_j; // i≠j?
		CC_HEAVISIDE_STEP(i_neq_j, i ^ j);
		ri |= r[j] & ((cc_unit)i_neq_j - 1);
	}

	return ri;
}

/*! @function ccn_invmod_ws
 *  @abstract Computes the inverse of x modulo m, r = x^-1 (mod m).
 *          Returns an error if there's no inverse, i.e. gcd(x,m) ≠ 1.
 *
 *  @discussion This is a very generic version of the binary XGCD algorithm. You
 *            don't want to use it when you have an odd modulus.
 *
 *            This function is meant to be used by RSA key generation, for
 *            computation of d = e^1 (mod lcm(p-1,q-1)), where m can be even.
 *
 *            x > m is allowed as long as xn == n, i.e. they occupy the same
 *            number of cc_units.
 *
 *  @param ws Workspace.
 *  @param n  Length of r and m as a number of cc_units.
 *  @param r  The resulting inverse r.
 *  @param xn Length of x as a number of cc_units.
 *  @param x  The number to invert.
 *  @param m  The modulus.
 *
 *  @return 0 on success, non-zero on failure. See cc_error.h for more details.
 */
CC_WARN_RESULT
int ccn_invmod_ws(cc_ws_t ws, cc_size n, cc_unit *cc_counted_by(n) r, cc_size xn, const cc_unit *cc_counted_by(xn) x, const cc_unit *cc_counted_by(n) m);

/*! @function ccn_mux_seed_mask
 *  @abstract Refreshes the internal state of the PRNG used to mask cmov/cswap
 *          operations with a given seed.
 *
 *  @discussion The seed should be of good entropy, i.e. generated by our default
 *            RNG. This function should be called before running algorithms that
 *            defend against side-channel attacks by using cmov/cswap. Examples
 *            are blinded modular exponentation (for RSA, DH, or MR) and EC
 *            scalar multiplication.
 *
 *  @param seed A seed value.
 */
void ccn_mux_seed_mask(cc_unit seed);

/*! @function ccn_divmod
 *  @abstract Computes a = q * d + r with r < d.
 *
 *  @param na  Length of a as a number of cc_units.
 *  @param a   The dividend a.
 *  @param nq  Length of q as a number of cc_units.
 *  @param q   The quotient q.
 *  @param n   Length of r and d as a number of cc_units.
 *  @param r   The remainder r.
 *  @param d   The divisor d.
 *
 *  @return 0 on success, non-zero on failure. See cc_error.h for more details.
 */
CC_NONNULL((2, 7)) CC_WARN_RESULT
int ccn_divmod(cc_size na, const cc_unit *cc_counted_by(na) a, cc_size nq, cc_unit *cc_counted_by(nq) q, cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) d);

CC_NONNULL((1, 3, 8))
void ccn_divmod_ws(cc_ws_t ws, cc_size na, const cc_unit *cc_counted_by(na) a, cc_size nq, cc_unit *cc_counted_by(nq) q, cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) d);

CC_NONNULL((2)) CC_SENTINEL
void ccn_zero_multi(cc_size n, cc_unit *r, ...);

CC_NONNULL((3, 4, 5))
cc_unit ccn_add_ws(cc_ws_t ws, cc_size count, cc_unit *r, const cc_unit *s, const cc_unit *t);

CC_NONNULL((3, 4, 5))
cc_unit ccn_sub_ws(cc_ws_t ws, cc_size count, cc_unit *r, const cc_unit *s, const cc_unit *t);

CC_NONNULL((3, 4))
cc_unit ccn_add1_ws(cc_ws_t ws, cc_size n, cc_unit *r, const cc_unit *s, cc_unit v);

/* s + t -> r return carry if result doesn't fit in n bits
 *  { N bit, NT bit -> N bit  NT <= N} N = n * sizeof(cc_unit) * 8 */
CC_NONNULL_ALL
cc_unit ccn_addn(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, cc_size nt, const cc_unit *cc_counted_by(nt) 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_ALL
cc_unit ccn_sub1(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, cc_unit v);

/* s - t -> r return 1 iff t > s
 *  { N bit, NT bit -> N bit  NT <= N} N = n * sizeof(cc_unit) * 8 */
CC_NONNULL_ALL
cc_unit ccn_subn(cc_size n, cc_unit *cc_counted_by(n) r, const cc_unit *cc_counted_by(n) s, cc_size nt, const cc_unit *cc_counted_by(nt) t);

/* Return the number of used units after stripping leading 0 units.  */
CC_NONNULL_ALL
cc_size ccn_n(cc_size n, const cc_unit *cc_counted_by(n)s);

/* Make a ccn of size ccn_nof(nbits) units with up to nbits sized random value. */
CC_NONNULL_ALL
int ccn_random_bits(cc_size nbits, cc_unit *cc_unsafe_indexable r, struct ccrng_state *rng);

/* Like ccn_random_bits, but uses ccrng_generate_fips under the hood. */
CC_NONNULL_ALL
int ccn_random_bits_fips(cc_size nbits, cc_unit *cc_unsafe_indexable r, struct ccrng_state *rng);

// Joint Sparse Form recoding context for EC double-scalar multiplication.
struct ccn_rjsf_state {
	uint8_t u[2];
	const cc_unit *s;
	const cc_unit *t;
};

/*! @function ccn_recode_jsf_init
 *  @abstract Initialize Joint Sparse Form recoding for EC scalars s and t.
 *
 *  @param r     JSF-recoding context.
 *  @param nbits Max. bit length of s and t.
 *  @param s     Scalar to be recoded.
 *  @param t     Scalar to be recoded.
 */
CC_NONNULL_ALL
void ccn_recode_jsf_init(struct ccn_rjsf_state *r, size_t nbits, const cc_unit *s, const cc_unit *t);

/*! @function ccn_recode_jsf_column
 *  @abstract Retrieve JSF-recoded digits for column k.
 *
 *  @param r JSF-recoding context.
 *  @param k Column index.
 *  @param c Digits (output).
 */
CC_NONNULL_ALL
void ccn_recode_jsf_column(struct ccn_rjsf_state *r, size_t k, int c[2]);

/*! @function ccn_recode_jsf_index
 *  @abstract Retrieve the lookup table index for given column digits.
 *
 *  @discussion For EC double-scalar multiplication, we assume a lookup table
 *            holding the four values [P, Q, P+Q, P-Q], in the same order.
 *
 *  @param c Column digits.
 *
 *  @return The lookup table index.
 */
CC_NONNULL_ALL CC_WARN_RESULT
size_t ccn_recode_jsf_index(int c[2]);

/*! @function ccn_recode_jsf_direction
 *  @abstract Retrieve the "direction" for given column digits.
 *
 *  @discussion For EC double-scalar multiplication, we assume a lookup table
 *            holding the four values [P, Q, P+Q, P-Q]. Negating each of
 *            these also yields [-P, -Q, -P-Q, -P+Q].
 *
 *            An EC double-and-add algorithm will either add or subtract a
 *            precomputed point to cover all possible digit combinations of two
 *            JSF-recoded EC scalars.
 *
 *  @param c Column digits.
 *
 *  @return The "direction". 1 for addition. -1 for subtraction.
 */
CC_NONNULL_ALL CC_WARN_RESULT
int ccn_recode_jsf_direction(int c[2]);

/*! @function ccn_read_le_bytes
 *  @abstract Copies a number given as little-endian bytes into `out`.
 *
 *  @param n   Number of limbs of `out`.
 *  @param in  Number to parse as little-endian bytes.
 *  @param out Output.
 */
CC_NONNULL_ALL
CC_INLINE void
ccn_read_le_bytes(cc_size n, const uint8_t *in, cc_unit *out)
{
	for (cc_size i = 0; i < n; i++) {
		out[i] = cc_load_le(&in[i * CCN_UNIT_SIZE]);
	}
}

/*! @function ccn_write_le_bytes
 *  @abstract Encodes a number as little-endian bytes into `out`.
 *
 *  @param n   Number of limbs of `in`.
 *  @param in  Number to encode as little-endian bytes.
 *  @param out Output.
 */
CC_NONNULL_ALL
CC_INLINE void
ccn_write_le_bytes(cc_size n, const cc_unit *in, uint8_t *out)
{
	for (cc_size i = 0; i < n; i++) {
		cc_store_le(in[i], &out[i * CCN_UNIT_SIZE]);
	}
}

/*! @function ccn_recode_ssw
 *  @abstract Recodes a given number into signed sliding windows.
 *
 *  @param n Number of limbs of `s`.
 *  @param s Number to recode.
 *  @param w Recode width, for windows in range (-2^w,2^w).
 *  @param r Output for the computed signed sliding windows.
 */
CC_NONNULL_ALL
void ccn_recode_ssw(cc_size n, const cc_unit *s, int w, int8_t *r);

#endif // _CORECRYPTO_CCN_INTERNAL_H