EXTERNAL_HEADERS/corecrypto/ccn.h

   1 /*
   2  *  ccn.h
   3  *  corecrypto
   4  *
   5  *  Created on 11/16/2010
   6  *
   7  *  Copyright (c) 2010,2011,2012,2013,2014,2015 Apple Inc. All rights reserved.
   8  *
   9  */
  10
  11 #ifndef _CORECRYPTO_CCN_H_
  12 #define _CORECRYPTO_CCN_H_
  13
  14 #include <corecrypto/cc.h>
  15 #include <stdint.h>
  16 #include <stdarg.h>
  17
  18 typedef uint8_t cc_byte;
  19 typedef size_t  cc_size;
  20
  21 #if  CCN_UNIT_SIZE == 8
  22 typedef uint64_t cc_unit;          // 64 bit unit
  23 typedef int64_t  cc_int;
  24 #define CCN_LOG2_BITS_PER_UNIT  6  // 2^6 = 64 bits
  25 #define CC_UNIT_C(x) UINT64_C(x)
  26  #if  CCN_UINT128_SUPPORT_FOR_64BIT_ARCH
  27    typedef unsigned cc_dunit __attribute__((mode(TI)));         // 128 bit double width unit
  28    typedef   signed cc_dint  __attribute__((mode(TI)));
  29  #else
  30    typedef struct cc_dunit {
  31     uint64_t l; //do not change the order of the variables. cc_dunit must be little endian
  32     uint64_t h;
  33    } cc_dunit;
  34
  35    typedef struct cc_dint {
  36     uint64_t l;
  37     uint64_t h;
  38    } cc_dint;
  39  #endif
  40
  41 #elif  CCN_UNIT_SIZE == 4
  42 typedef uint32_t cc_unit;          // 32 bit unit
  43 typedef uint64_t cc_dunit;         // 64 bit double width unit
  44 typedef int64_t cc_dint;
  45 typedef int32_t cc_int;
  46 #define CCN_LOG2_BITS_PER_UNIT  5  // 2^5 = 32 bits
  47 #define CC_UNIT_C(x) UINT32_C(x)
  48
  49 #elif CCN_UNIT_SIZE == 2
  50 typedef uint16_t cc_unit;          // 16 bit unit
  51 typedef uint32_t cc_dunit;         // 32 bit double width unit
  52 #define CCN_LOG2_BITS_PER_UNIT  4  // 2^4 = 16 bits
  53 #define CC_UNIT_C(x) UINT16_C(x)
  54
  55 #elif CCN_UNIT_SIZE == 1
  56 typedef uint8_t cc_unit;           // 8 bit unit
  57 typedef uint16_t cc_dunit;         // 16 bit double width unit
  58 #define CCN_LOG2_BITS_PER_UNIT  3  // 2^3 = 8 bits
  59 #define CC_UNIT_C(x) UINT8_C(x)
  60
  61 #else
  62 #error invalid CCN_UNIT_SIZE
  63 #endif
  64
  65 // All mp types have units in little endian unit order.
  66 typedef cc_unit *ccn_t;                // n unit long mp
  67 typedef cc_unit *ccnp1_t;              // n + 1 unit long mp
  68 typedef cc_unit *cc2n_t;               // 2 * n unit long mp
  69 typedef cc_unit *cc2np2_t;             // 2 * n + 2 unit long mp
  70 typedef const cc_unit *ccn_in_t;       // n unit long mp
  71 typedef const cc_unit *ccnp1_in_t;     // n + 1 unit long mp
  72 typedef const cc_unit *cc2n_in_t;      // 2 * n unit long mp
  73 typedef const cc_unit *cc2np2_in_t;    // 2 * n + 2 unit long mp
  74
  75 #define CCN_UNIT_BITS  (sizeof(cc_unit) * 8)
  76 #define CCN_UNIT_MASK  ((cc_unit)~0)
  77
  78 typedef struct {
  79     cc_unit *start;      // First cc_unit of the workspace
  80     cc_unit *end;        // address and beyond NOT TO BE TOUCHED
  81 } cc_ws,*cc_ws_t;
  82
  83 /* Conversions between n sizeof and bits */
  84
  85 /* Returns the sizeof a ccn vector of length _n_ units. */
  86 #define ccn_sizeof_n(_n_)  (sizeof(cc_unit) * (_n_))
  87
  88 /* Returns the count (n) of a ccn vector that can represent _bits_. */
  89 #define ccn_nof(_bits_)  (((_bits_) + CCN_UNIT_BITS - 1) >> CCN_LOG2_BITS_PER_UNIT)
  90
  91 /* Returns the sizeof a ccn vector that can represent _bits_. */
  92 #define ccn_sizeof(_bits_)  (ccn_sizeof_n(ccn_nof(_bits_)))
  93
  94 /* Returns the count (n) of a ccn vector that can represent _size_ bytes. */
  95 #define ccn_nof_size(_size_)  (((_size_) + CCN_UNIT_SIZE - 1) / CCN_UNIT_SIZE)
  96
  97 /* Return the max number of bits a ccn vector of _n_ units can hold. */
  98 #define ccn_bitsof_n(_n_)  ((_n_) * CCN_UNIT_BITS)
  99
 100 /* Return the max number of bits a ccn vector of _size_ bytes can hold. */
 101 #define ccn_bitsof_size(_size_)  ((_size_) * 8)
 102
 103 /* Return the size of a ccn of size bytes in bytes. */
 104 #define ccn_sizeof_size(_size_)  ccn_sizeof_n(ccn_nof_size(_size_))
 105
 106 /* Returns the value of bit _k_ of _ccn_, both are only evaluated once.  */
 107 #define ccn_bit(_ccn_, _k_) ({__typeof__ (_k_) __k = (_k_); \
 108     1 & ((_ccn_)[ __k >> CCN_LOG2_BITS_PER_UNIT] >> (__k & (CCN_UNIT_BITS - 1)));})
 109
 110 /* Set the value of bit _k_ of _ccn_ to the value _v_  */
 111 #define ccn_set_bit(_ccn_, _k_, _v_) ({__typeof__ (_k_) __k = (_k_);        \
 112     if (_v_)                                                                \
 113         (_ccn_)[ __k >> CCN_LOG2_BITS_PER_UNIT] |= CC_UNIT_C(1) << (__k & (CCN_UNIT_BITS - 1));     \
 114     else                                                                    \
 115         (_ccn_)[ __k >> CCN_LOG2_BITS_PER_UNIT] &= ~(CC_UNIT_C(1) << (__k & (CCN_UNIT_BITS - 1)));  \
 116     })
 117
 118 /* Macros for making ccn constants.  You must use list of CCN64_C() instances
 119  separated by commas, with an optional smaller sized CCN32_C, CCN16_C, or
 120  CCN8_C() instance at the end of the list, when making macros to declare
 121  larger sized constants. */
 122 #define CCN8_C(a0) CC_UNIT_C(0x##a0)
 123
 124 #if CCN_UNIT_SIZE >= 2
 125 #define CCN16_C(a1,a0) CC_UNIT_C(0x##a1##a0)
 126 #define ccn16_v(a0)  (a0)
 127 #elif CCN_UNIT_SIZE == 1
 128 #define CCN16_C(a1,a0) CCN8_C(a0),CCN8_C(a1)
 129 #define ccn16_v(a0)  (a0 & UINT8_C(0xff)),(a0 >> 8)
 130 #endif
 131
 132 #if CCN_UNIT_SIZE >= 4
 133 #define CCN32_C(a3,a2,a1,a0) CC_UNIT_C(0x##a3##a2##a1##a0)
 134 #define ccn32_v(a0)  (a0)
 135 #else
 136 #define CCN32_C(a3,a2,a1,a0) CCN16_C(a1,a0),CCN16_C(a3,a2)
 137 #define ccn32_v(a0)  ccn16_v(a0 & UINT16_C(0xffff)),ccn16_v(a0 >> 16)
 138 #endif
 139
 140 #if CCN_UNIT_SIZE == 8
 141 #define CCN64_C(a7,a6,a5,a4,a3,a2,a1,a0) CC_UNIT_C(0x##a7##a6##a5##a4##a3##a2##a1##a0)
 142 #define CCN40_C(a4,a3,a2,a1,a0) CC_UNIT_C(0x##a4##a3##a2##a1##a0)
 143 #define ccn64_v(a0)  (a0)
 144 //#define ccn64_32(a1,a0)  ((a1 << 32) | a0)
 145 //#define ccn_uint64(a,i) (a[i])
 146 #else
 147 #define CCN64_C(a7,a6,a5,a4,a3,a2,a1,a0) CCN32_C(a3,a2,a1,a0),CCN32_C(a7,a6,a5,a4)
 148 #define CCN40_C(a4,a3,a2,a1,a0) CCN32_C(a3,a2,a1,a0),CCN8_C(a4)
 149 #define ccn64_v(a0)  ccn32_v((uint64_t)a0 & UINT32_C(0xffffffff)),ccn32_v((uint64_t)a0 >> 32)
 150 //#define ccn64_32(a1,a0)  ccn32_v(a0),ccn32_v(a1)
 151 //#define ccn_uint64(a,i) ((uint64_t)ccn_uint32(a, i << 1 + 1) << 32 | (uint64_t)ccn_uint32(a, i << 1))
 152 #endif
 153
 154 /* Macro's for reading uint32_t and uint64_t from ccns, the index is in 32 or
 155    64 bit units respectively. */
 156 #if CCN_UNIT_SIZE == 8
 157 /* #define ccn_uint16(a,i) ((i & 3) == 3 ? ((uint16_t)(a[i >> 2] >> 48)) : \
 158      (i & 3) == 2 ? ((uint16_t)(a[i >> 2] >> 32) & UINT16_C(0xffff)) : \
 159      (i & 3) == 1 ? ((uint16_t)(a[i >> 2] >> 16) & UINT16_C(0xffff)) : \
 160      ((uint16_t)(a[i >> 1] & UINT16_C(0xffff))))
 161 */
 162 //#define ccn_uint32(a,i) (i & 1 ? ((uint32_t)(a[i >> 1] >> 32)) : ((uint32_t)(a[i >> 1] & UINT32_C(0xffffffff))))
 163 #elif CCN_UNIT_SIZE == 4
 164 //#define ccn16_v(a0)  (a0)
 165 //#define ccn32_v(a0)  (a0)
 166 //#define ccn_uint16(a,i) (i & 1 ? ((uint16_t)(a[i >> 1] >> 16)) : ((uint16_t)(a[i >> 1] & UINT16_C(0xffff))))
 167 //#define ccn_uint32(a,i) (a[i])
 168 #elif CCN_UNIT_SIZE == 2
 169 //#define ccn16_v(a0)  (a0)
 170 //#define ccn32_v(a0,a1)  (a1,a0)
 171 //#define ccn_uint16(a,i) (a[i])
 172 //#define ccn_uint32(a,i) (((uint32_t)a[i << 1 + 1]) << 16 | (uint32_t)a[i << 1]))
 173 #elif CCN_UNIT_SIZE == 1
 174 //#define ccn16_v(a0)  (a0 & UINT8_C(0xff)),(a0 >> 8)
 175 //#define ccn_uint16(a,i) ((uint16_t)((a[i << 1 + 1] << 8) | a[i << 1]))
 176 //#define ccn_uint32(a,i) ((uint32_t)ccn_uint16(a, i << 1 + 1) << 16 | (uint32_t)ccn_uint16(a, i << 1))
 177 #endif
 178
 179 /* Macro's for reading uint32_t and uint64_t from ccns, the index is in 32 or
 180  64 bit units respectively. */
 181 #if CCN_UNIT_SIZE == 8
 182
 183 #define ccn64_32(a1,a0) (((const cc_unit)a1) << 32 | ((const cc_unit)a0))
 184 #define ccn32_32(a0) a0
 185 #if __LITTLE_ENDIAN__
 186 #define ccn32_32_parse(p,i) (((const uint32_t *)p)[i])
 187 #else
 188 #define ccn32_32_parse(p,i) (((const uint32_t *)p)[i^1])
 189 #endif
 190 #define ccn32_32_null 0
 191
 192 #define ccn64_64(a0) a0
 193 #define ccn64_64_parse(p,i) p[i]
 194 #define ccn64_64_null 0
 195
 196 #elif CCN_UNIT_SIZE == 4
 197
 198 #define ccn32_32(a0) a0
 199 #define ccn32_32_parse(p,i) p[i]
 200 #define ccn32_32_null 0
 201 #define ccn64_32(a1,a0) ccn32_32(a0),ccn32_32(a1)
 202
 203 #define ccn64_64(a1,a0) a0,a1
 204 #define ccn64_64_parse(p,i) p[1+(i<<1)],p[i<<1]
 205 #define ccn64_64_null 0,0
 206
 207 #elif CCN_UNIT_SIZE == 2
 208
 209 #define ccn32_32(a1,a0) a0,a1
 210 #define ccn32_32_parse(p,i) p[1+(i<<1)],p[i<<1]
 211 #define ccn32_32_null 0,0
 212 #define ccn64_32(a3,a2,a1,a0) ccn32_32(a1,a0),ccn32_32(a3,a2)
 213
 214 #define ccn64_64(a3,a2,a1,a0) a0,a1,a2,a3
 215 #define ccn64_64_parse(p,i) p[3+(i<<2)],p[2+(i<<2)],p[1+(i<<2)],p[i<<2]
 216 #define ccn64_64_null 0,0,0,0
 217
 218 #elif CCN_UNIT_SIZE == 1
 219
 220 #define ccn32_32(a3,a2,a1,a0) a0,a1,a2,a3
 221 #define ccn32_32_parse(p,i) p[3+(i<<2)],p[2+(i<<2)],p[1+(i<<2)],p[i<<2]
 222 #define ccn32_32_null 0,0,0,0
 223 #define ccn64_32(a7,a6,a5,a4,a3,a2,a1,a0) ccn32_32(a3,a2,a1,a0),ccn32_32(a7,a6,a5,a4)
 224
 225 #define ccn64_64(a7,a6,a5,a4,a3,a2,a1,a0) a0,a1,a2,a3,a4,a5,a6,a7
 226 #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]
 227 #define ccn64_64_null  0,0,0,0,0,0,0,0
 228
 229 #endif
 230
 231
 232 /* Macros to construct fixed size ccn arrays from 64 or 32 bit quantities. */
 233 #define ccn192_64(a2,a1,a0) ccn64_64(a0),ccn64_64(a1),ccn64_64(a2)
 234 #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)
 235 #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)
 236 #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)
 237
 238
 239 #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) \
 240     CCN64_C(a7,a6,a5,a4,a3,a2,a1,a0),\
 241     CCN64_C(b7,b6,b5,b4,b3,b2,b1,b0),\
 242     CCN64_C(c7,c6,c5,c4,c3,c2,c1,c0)
 243
 244 #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) \
 245     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),\
 246     CCN8_C(d0)
 247
 248 #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) \
 249     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),\
 250     CCN32_C(d3,d2,d1,d0)
 251
 252 #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) \
 253     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),\
 254     CCN40_C(d4,d3,d2,d1,d0)
 255
 256 #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) \
 257     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),\
 258     CCN64_C(d7,d6,d5,d4,d3,d2,d1,d0)
 259
 260 #define CCN264_C(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) \
 261     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),\
 262     CCN8_C(e0)
 263
 264 #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) \
 265     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),\
 266     CCN64_C(e7,e6,e5,e4,e3,e2,e1,e0),\
 267     CCN64_C(f7,f6,f5,f4,f3,f2,f1,f0)
 268
 269 #define CCN392_C(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) \
 270     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),\
 271     CCN8_C(g0)
 272
 273 #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) \
 274     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),\
 275     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),\
 276     CCN16_C(i1,i0)
 277
 278 #define CCN192_N  ccn_nof(192)
 279 #define CCN224_N  ccn_nof(224)
 280 #define CCN256_N  ccn_nof(256)
 281 #define CCN384_N  ccn_nof(384)
 282 #define CCN512_N  ccn_nof(512)
 283 #define CCN521_N  ccn_nof(521)
 284
 285 /* Return the number of used units after stripping leading 0 units.  */
 286 CC_PURE CC_NONNULL2
 287 cc_size ccn_n(cc_size n, const cc_unit *s);
 288
 289 /* s >> k -> r return bits shifted out of least significant word in bits [0, n>
 290  { N bit, scalar -> N bit } N = n * sizeof(cc_unit) * 8
 291  the _multi version doesn't return the shifted bits, but does support multiple
 292  word shifts.  */
 293 CC_NONNULL((2, 3))
 294 cc_unit ccn_shift_right(cc_size n, cc_unit *r, const cc_unit *s, size_t k);
 295 CC_NONNULL((2, 3))
 296 void ccn_shift_right_multi(cc_size n, cc_unit *r,const cc_unit *s, size_t k);
 297
 298 /* s << k -> r return bits shifted out of most significant word in bits [0, n>
 299  { N bit, scalar -> N bit } N = n * sizeof(cc_unit) * 8
 300  the _multi version doesn't return the shifted bits, but does support multiple
 301  word shifts */
 302 CC_NONNULL((2, 3))
 303 cc_unit ccn_shift_left(cc_size n, cc_unit *r, const cc_unit *s, size_t k);
 304 CC_NONNULL((2, 3))
 305 void ccn_shift_left_multi(cc_size n, cc_unit *r, const cc_unit *s, size_t k);
 306
 307 /* s == 0 -> return 0 | s > 0 -> return index (starting at 1) of most
 308  significant bit that is 1.
 309  { N bit } N = n * sizeof(cc_unit) * 8 */
 310 CC_NONNULL2
 311 size_t ccn_bitlen(cc_size n, const cc_unit *s);
 312
 313 /* Returns the number of bits which are zero before the first one bit
 314    counting from least to most significant bit. */
 315 CC_NONNULL2
 316 size_t ccn_trailing_zeros(cc_size n, const cc_unit *s);
 317
 318 /* s == 0 -> return true | s != 0 -> return false
 319  { N bit } N = n * sizeof(cc_unit) * 8 */
 320 #define ccn_is_zero(_n_, _s_) (!ccn_n(_n_, _s_))
 321
 322 /* s == 1 -> return true | s != 1 -> return false
 323  { N bit } N = n * sizeof(cc_unit) * 8 */
 324 #define ccn_is_one(_n_, _s_) (ccn_n(_n_, _s_) == 1 && _s_[0] == 1)
 325
 326 #define ccn_is_zero_or_one(_n_, _s_) (((_n_)==0) || ((ccn_n(_n_, _s_) <= 1) && (_s_[0] <= 1)))
 327
 328 /* s < t -> return - 1 | s == t -> return 0 | s > t -> return 1
 329  { N bit, N bit -> int } N = n * sizeof(cc_unit) * 8 */
 330 CC_PURE CC_NONNULL((2, 3))
 331 int ccn_cmp(cc_size n, const cc_unit *s, const cc_unit *t);
 332
 333 /* s < t -> return - 1 | s == t -> return 0 | s > t -> return 1
 334  { N bit, M bit -> int } N = ns * sizeof(cc_unit) * 8  M = nt * sizeof(cc_unit) * 8 */
 335 CC_INLINE CC_NONNULL((2, 4))
 336 int ccn_cmpn(cc_size ns, const cc_unit *s,
 337              cc_size nt, const cc_unit *t) {
 338     if (ns > nt) {
 339         return 1;
 340     } else if (ns < nt) {
 341         return -1;
 342     }
 343     return ccn_cmp(ns, s, t);
 344 }
 345
 346 /* s - t -> r return 1 iff t > s
 347  { N bit, N bit -> N bit } N = n * sizeof(cc_unit) * 8 */
 348 CC_NONNULL((2, 3, 4))
 349 cc_unit ccn_sub(cc_size n, cc_unit *r, const cc_unit *s, const cc_unit *t);
 350
 351 /* |s - t| -> r return 1 iff t > s, 0 otherwise */
 352 cc_unit ccn_abs(cc_size n, cc_unit *r, const cc_unit *s, const cc_unit *t);
 353
 354 /* s - v -> r return 1 iff v > s return 0 otherwise.
 355  { N bit, sizeof(cc_unit) * 8 bit -> N bit } N = n * sizeof(cc_unit) * 8 */
 356 CC_NONNULL((2, 3))
 357 cc_unit ccn_sub1(cc_size n, cc_unit *r, const cc_unit *s, cc_unit v);
 358
 359 /* s - t -> r return 1 iff t > s
 360  { N bit, NT bit -> N bit  NT <= N} N = n * sizeof(cc_unit) * 8 */
 361 CC_INLINE
 362 CC_NONNULL((2, 3, 5))
 363 cc_unit ccn_subn(cc_size n, cc_unit *r, const cc_unit *s,
 364              cc_size nt, const cc_unit *t) {
 365     assert(n >= nt);
 366     return ccn_sub1(n - nt, r + nt, s + nt, ccn_sub(nt, r, s, t));
 367 }
 368
 369
 370 /* s + t -> r return carry if result doesn't fit in n bits.
 371  { N bit, N bit -> N bit } N = n * sizeof(cc_unit) * 8 */
 372 CC_NONNULL((2, 3, 4))
 373 cc_unit ccn_add(cc_size n, cc_unit *r, const cc_unit *s, const cc_unit *t);
 374
 375 /* s + v -> r return carry if result doesn't fit in n bits.
 376  { N bit, sizeof(cc_unit) * 8 bit -> N bit } N = n * sizeof(cc_unit) * 8 */
 377 CC_NONNULL((2, 3))
 378 cc_unit ccn_add1(cc_size n, cc_unit *r, const cc_unit *s, cc_unit v);
 379
 380 /* s + t -> r return carry if result doesn't fit in n bits
 381  { N bit, NT bit -> N bit  NT <= N} N = n * sizeof(cc_unit) * 8 */
 382 CC_INLINE
 383 CC_NONNULL((2, 3, 5))
 384 cc_unit ccn_addn(cc_size n, cc_unit *r, const cc_unit *s,
 385                  cc_size nt, const cc_unit *t) {
 386     assert(n >= nt);
 387     return ccn_add1(n - nt, r + nt, s + nt, ccn_add(nt, r, s, t));
 388 }
 389
 390
 391 CC_NONNULL((2, 3, 4))
 392 void ccn_lcm(cc_size n, cc_unit *r2n, const cc_unit *s, const cc_unit *t);
 393
 394
 395 /* s * t -> r_2n                   r_2n must not overlap with s nor t
 396  { n bit, n bit -> 2 * n bit } n = count * sizeof(cc_unit) * 8
 397  { N bit, N bit -> 2N bit } N = ccn_bitsof(n) */
 398 CC_NONNULL((2, 3, 4))
 399 void ccn_mul(cc_size n, cc_unit *r_2n, const cc_unit *s, const cc_unit *t);
 400
 401 /* s * t -> r_2n                   r_2n must not overlap with s nor t
 402  { n bit, n bit -> 2 * n bit } n = count * sizeof(cc_unit) * 8
 403  { N bit, N bit -> 2N bit } N = ccn_bitsof(n)
 404  Provide a workspace for potential speedup */
 405 CC_NONNULL((2, 3, 4, 5))
 406 void ccn_mul_ws(cc_size count, cc_unit *r, const cc_unit *s, const cc_unit *t, cc_ws_t ws);
 407
 408 /* s[0..n) * v -> r[0..n)+return value
 409  { N bit, sizeof(cc_unit) * 8 bit -> N + sizeof(cc_unit) * 8 bit } N = n * sizeof(cc_unit) * 8 */
 410 CC_NONNULL((2, 3))
 411 cc_unit ccn_mul1(cc_size n, cc_unit *r, const cc_unit *s, const cc_unit v);
 412
 413 /* s[0..n) * v + r[0..n) -> r[0..n)+return value
 414  { N bit, sizeof(cc_unit) * 8 bit -> N + sizeof(cc_unit) * 8 bit } N = n * sizeof(cc_unit) * 8 */
 415 CC_NONNULL((2, 3))
 416 cc_unit ccn_addmul1(cc_size n, cc_unit *r, const cc_unit *s, const cc_unit v);
 417
 418 #if 0
 419 /* a % d -> n
 420    {2 * n bit, n bit -> n bit } n = count * sizeof(cc_unit) * 8 */
 421 CC_NONNULL((2, 3, 4))
 422 void ccn_mod(cc_size n, cc_unit *r, const cc_unit *a_2n, const cc_unit *d);
 423 #endif
 424
 425 /* r = gcd(s, t).
 426    N bit, N bit -> N bit */
 427 CC_NONNULL((2, 3, 4))
 428 void ccn_gcd(cc_size n, cc_unit *r, const cc_unit *s, const cc_unit *t);
 429
 430 /* r = gcd(s, t).
 431  N bit, N bit -> O bit */
 432 CC_NONNULL((2, 4, 6))
 433 void ccn_gcdn(cc_size rn, cc_unit *r, cc_size sn, const cc_unit *s, cc_size tn, const cc_unit *t);
 434
 435 /* r = (data, len) treated as a big endian byte array, return -1 if data
 436  doesn't fit in r, return 0 otherwise. */
 437 CC_NONNULL((2, 4))
 438 int ccn_read_uint(cc_size n, cc_unit *r, size_t data_size, const uint8_t *data);
 439
 440 /* r = (data, len) treated as a big endian byte array, return -1 if data
 441  doesn't fit in r, return 0 otherwise.
 442  ccn_read_uint strips leading zeroes and doesn't care about sign. */
 443 #define ccn_read_int(n, r, data_size, data) ccn_read_uint(n, r, data_size, data)
 444
 445 /* Return actual size in bytes needed to serialize s. */
 446 CC_PURE CC_NONNULL2
 447 size_t ccn_write_uint_size(cc_size n, const cc_unit *s);
 448
 449 /* Serialize s, to out.
 450    First byte of byte stream is the m.s. byte of s,
 451    regardless of the size of cc_unit.
 452
 453    No assumption is made about the alignment of out.
 454
 455    The out_size argument should be the value returned from ccn_write_uint_size,
 456    and is also the exact number of bytes this function will write to out.
 457    If out_size if less than the value returned by ccn_write_uint_size, only the
 458    first out_size non-zero most significant octets of s will be written. */
 459 CC_NONNULL((2, 4))
 460 void ccn_write_uint(cc_size n, const cc_unit *s, size_t out_size, void *out);
 461
 462
 463 CC_INLINE CC_NONNULL((2, 4))
 464 cc_size ccn_write_uint_padded(cc_size n, const cc_unit* s, size_t out_size, uint8_t* to)
 465 {
 466     size_t bytesInKey = ccn_write_uint_size(n, s);
 467     cc_size offset = (out_size > bytesInKey) ? out_size - bytesInKey : 0;
 468
 469     cc_zero(offset, to);
 470     ccn_write_uint(n, s, out_size - offset, to + offset);
 471
 472     return offset;
 473 }
 474
 475
 476 /*  Return actual size in bytes needed to serialize s as int
 477     (adding leading zero if high bit is set). */
 478 CC_PURE CC_NONNULL2
 479 size_t ccn_write_int_size(cc_size n, const cc_unit *s);
 480
 481 /*  Serialize s, to out.
 482     First byte of byte stream is the m.s. byte of s,
 483     regardless of the size of cc_unit.
 484
 485     No assumption is made about the alignment of out.
 486
 487     The out_size argument should be the value returned from ccn_write_int_size,
 488     and is also the exact number of bytes this function will write to out.
 489     If out_size if less than the value returned by ccn_write_int_size, only the
 490     first out_size non-zero most significant octets of s will be written. */
 491 CC_NONNULL((2, 4))
 492 void ccn_write_int(cc_size n, const cc_unit *s, size_t out_size, void *out);
 493
 494 #if CCN_DEDICATED_SQR
 495
 496 /* s^2 -> r
 497  { n bit -> 2 * n bit } */
 498 CC_NONNULL((2, 3))
 499 void ccn_sqr(cc_size n, cc_unit *r, const cc_unit *s);
 500
 501 /* s^2 -> r
 502  { n bit -> 2 * n bit } */
 503 CC_NONNULL((2, 3, 4))
 504 void ccn_sqr_ws(cc_size n, cc_unit *r, const cc_unit *s, cc_ws_t ws);
 505
 506 #else
 507
 508 /* s^2 -> r
 509  { n bit -> 2 * n bit } */
 510 CC_INLINE CC_NONNULL((2, 3))
 511 void ccn_sqr(cc_size n, cc_unit *r, const cc_unit *s) {
 512     ccn_mul(n, r, s, s);
 513 }
 514
 515 /* s^2 -> r
 516  { n bit -> 2 * n bit } */
 517 CC_INLINE CC_NONNULL((2, 3, 4))
 518 void ccn_sqr_ws(cc_size n, cc_unit *r, const cc_unit *s, cc_ws_t ws) {
 519     ccn_mul_ws(n, r, s, s, ws);
 520 }
 521
 522 #endif
 523
 524 /* s -> r
 525  { n bit -> n bit } */
 526 CC_NONNULL((2, 3))
 527 void ccn_set(cc_size n, cc_unit *r, const cc_unit *s);
 528
 529 CC_INLINE CC_NONNULL2
 530 void ccn_zero(cc_size n, cc_unit *r) {
 531     cc_zero(ccn_sizeof_n(n),r);
 532 }
 533
 534 CC_INLINE CC_NONNULL2
 535 void ccn_clear(cc_size n, cc_unit *r) {
 536     cc_clear(ccn_sizeof_n(n),r);
 537 }
 538
 539 CC_NONNULL2
 540 void ccn_zero_multi(cc_size n, cc_unit *r, ...);
 541
 542 CC_INLINE CC_NONNULL2
 543 void ccn_seti(cc_size n, cc_unit *r, cc_unit v) {
 544     /* assert(n > 0); */
 545     r[0] = v;
 546     ccn_zero(n - 1, r + 1);
 547 }
 548
 549 CC_INLINE CC_NONNULL((2, 4))
 550 void ccn_setn(cc_size n, cc_unit *r, const cc_size s_size, const cc_unit *s) {
 551     /* FIXME: assert not available in kernel.
 552     assert(n > 0);
 553     assert(s_size > 0);
 554     assert(s_size <= n);
 555     */
 556     ccn_set(s_size, r, s);
 557     ccn_zero(n - s_size, r + s_size);
 558 }
 559
 560 #define CC_SWAP_HOST_BIG_64(x) \
 561     ((uint64_t)((((uint64_t)(x) & 0xff00000000000000ULL) >> 56) | \
 562     (((uint64_t)(x) & 0x00ff000000000000ULL) >> 40) | \
 563     (((uint64_t)(x) & 0x0000ff0000000000ULL) >> 24) | \
 564     (((uint64_t)(x) & 0x000000ff00000000ULL) >>  8) | \
 565     (((uint64_t)(x) & 0x00000000ff000000ULL) <<  8) | \
 566     (((uint64_t)(x) & 0x0000000000ff0000ULL) << 24) | \
 567     (((uint64_t)(x) & 0x000000000000ff00ULL) << 40) | \
 568     (((uint64_t)(x) & 0x00000000000000ffULL) << 56)))
 569 #define CC_SWAP_HOST_BIG_32(x) \
 570     ((((x) & 0xff000000) >> 24) | \
 571     (((x) & 0x00ff0000) >>  8) | \
 572     (((x) & 0x0000ff00) <<  8) | \
 573     (((x) & 0x000000ff) <<  24))
 574 #define CC_SWAP_HOST_BIG_16(x) \
 575     ((((x) & 0xff00) >>  8) | \
 576     (((x) & 0x00ff) <<  8))
 577
 578 /* This should probably move if we move ccn_swap out of line. */
 579 #if CCN_UNIT_SIZE == 8
 580 #define CC_UNIT_TO_BIG(x) CC_SWAP_HOST_BIG_64(x)
 581 #elif CCN_UNIT_SIZE == 4
 582 #define CC_UNIT_TO_BIG(x) CC_SWAP_HOST_BIG_32(x)
 583 #elif CCN_UNIT_SIZE == 2
 584 #define CC_UNIT_TO_BIG(x) CC_SWAP_HOST_BIG_16(x)
 585 #elif CCN_UNIT_SIZE == 1
 586 #define CC_UNIT_TO_BIG(x) (x)
 587 #else
 588 #error unsupported CCN_UNIT_SIZE
 589 #endif
 590
 591 /* Swap units in r in place from cc_unit vector byte order to big endian byte order (or back). */
 592 CC_INLINE CC_NONNULL2
 593 void ccn_swap(cc_size n, cc_unit *r) {
 594     cc_unit *e;
 595     for (e = r + n - 1; r < e; ++r, --e) {
 596         cc_unit t = CC_UNIT_TO_BIG(*r);
 597         *r = CC_UNIT_TO_BIG(*e);
 598         *e = t;
 599     }
 600     if (n & 1)
 601         *r = CC_UNIT_TO_BIG(*r);
 602 }
 603
 604 CC_INLINE CC_NONNULL((2, 3, 4))
 605 void ccn_xor(cc_size n, cc_unit *r, const cc_unit *s, const cc_unit *t) {
 606     while (n--) {
 607         r[n] = s[n] ^ t[n];
 608     }
 609 }
 610
 611 /* Debugging */
 612 CC_NONNULL2
 613 void ccn_print(cc_size n, const cc_unit *s);
 614 CC_NONNULL3
 615 void ccn_lprint(cc_size n, const char *label, const cc_unit *s);
 616
 617 /* Forward declaration so we don't depend on ccrng.h. */
 618 struct ccrng_state;
 619
 620 #if 0
 621 CC_INLINE CC_NONNULL((2, 3))
 622 int ccn_random(cc_size n, cc_unit *r, struct ccrng_state *rng) {
 623     return (RNG)->generate((RNG), ccn_sizeof_n(n), (unsigned char *)r);
 624 }
 625 #else
 626 #define ccn_random(_n_,_r_,_ccrng_ctx_) \
 627     ccrng_generate(_ccrng_ctx_, ccn_sizeof_n(_n_), (unsigned char *)_r_)
 628 #endif
 629
 630 /* Make a ccn of size ccn_nof(nbits) units with up to nbits sized random value. */
 631 CC_NONNULL((2, 3))
 632 int ccn_random_bits(cc_size nbits, cc_unit *r, struct ccrng_state *rng);
 633
 634 /*!
 635  @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)
 636
 637  @param nd      length of array d
 638  @param recip   returned reciprocal of size nd+1
 639  @param d       input number d
 640 */
 641 CC_NONNULL((2, 3))
 642 void ccn_make_recip(cc_size nd, cc_unit *recip, const cc_unit *d);
 643
 644 CC_NONNULL((6, 8))
 645 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);
 646
 647 #define ccn_div(nq, q, na, a, nd, d) ccn_div_euclid(nq, q, 0, NULL, na, a, nd, d)
 648 #define ccn_mod(nr, r, na, a, nd, d) ccn_div_euclid(0 , NULL, nr, r, na, a, nd, d)
 649
 650 /*!
 651  @brief ccn_div_use_recip(nq, q, nr, r, na, a, nd, d) comutes q=a/d and r=a%d
 652  @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.
 653  @param nq length of array q that hold the quotients. The maximum length of quotient is the actual length of dividend a
 654  @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.
 655  @param nr length of array r that hold the remainder. The maximum length of remainder is the actual length of divisor d
 656  @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.
 657  @param na length of dividend. Dividend may have leading zeros.
 658  @param a  input Dividend
 659  @param nd length of input divisor. Divisor may have leading zeros.
 660  @param d  input Divisor
 661  @param recip_d The reciprocal of d, of length nd+1.
 662
 663  @return  returns 0 if successful, negative of error.
 664  */
 665 CC_NONNULL((6, 8, 9))
 666 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);
 667
 668 #endif /* _CORECRYPTO_CCN_H_ */