EXTERNAL_HEADERS/corecrypto/ccn.h

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