#include <string.h>
#include <assert.h>
+size_t SHA3_absorb(uint64_t A[5][5], const unsigned char *inp, size_t len,
+ size_t r);
+void SHA3_squeeze(uint64_t A[5][5], unsigned char *out, size_t len, size_t r);
+
+#if !defined(KECCAK1600_ASM) || !defined(SELFTEST)
+
+/*
+ * Choose some sensible defaults
+ */
+#if !defined(KECCAK_REF) && !defined(KECCAK_1X) && !defined(KECCAK_1X_ALT) && \
+ !defined(KECCAK_2X) && !defined(KECCAK_INPLACE)
+# define KECCAK_2X /* default to KECCAK_2X variant */
+#endif
+
+#if defined(__i386) || defined(__i386__) || defined(_M_IX86)
+# define KECCAK_COMPLEMENTING_TRANSFORM
+#endif
+
+#if defined(__x86_64__) || defined(__aarch64__) || \
+ defined(__mips64) || defined(__ia64) || \
+ (defined(__VMS) && !defined(__vax))
+/*
+ * These are available even in ILP32 flavours, but even then they are
+ * capable of performing 64-bit operations as efficiently as in *P64.
+ * Since it's not given that we can use sizeof(void *), just shunt it.
+ */
+# define BIT_INTERLEAVE (0)
+#else
+# define BIT_INTERLEAVE (sizeof(void *) < 8)
+#endif
+
#define ROL32(a, offset) (((a) << (offset)) | ((a) >> ((32 - (offset)) & 31)))
static uint64_t ROL64(uint64_t val, int offset)
{
if (offset == 0) {
return val;
- } else if (sizeof(void *) == 8) {
+ } else if (!BIT_INTERLEAVE) {
return (val << offset) | (val >> (64-offset));
} else {
uint32_t hi = (uint32_t)(val >> 32), lo = (uint32_t)val;
};
static const uint64_t iotas[] = {
- sizeof(void *) == 8 ? 0x0000000000000001U : 0x0000000000000001U,
- sizeof(void *) == 8 ? 0x0000000000008082U : 0x0000008900000000U,
- sizeof(void *) == 8 ? 0x800000000000808aU : 0x8000008b00000000U,
- sizeof(void *) == 8 ? 0x8000000080008000U : 0x8000808000000000U,
- sizeof(void *) == 8 ? 0x000000000000808bU : 0x0000008b00000001U,
- sizeof(void *) == 8 ? 0x0000000080000001U : 0x0000800000000001U,
- sizeof(void *) == 8 ? 0x8000000080008081U : 0x8000808800000001U,
- sizeof(void *) == 8 ? 0x8000000000008009U : 0x8000008200000001U,
- sizeof(void *) == 8 ? 0x000000000000008aU : 0x0000000b00000000U,
- sizeof(void *) == 8 ? 0x0000000000000088U : 0x0000000a00000000U,
- sizeof(void *) == 8 ? 0x0000000080008009U : 0x0000808200000001U,
- sizeof(void *) == 8 ? 0x000000008000000aU : 0x0000800300000000U,
- sizeof(void *) == 8 ? 0x000000008000808bU : 0x0000808b00000001U,
- sizeof(void *) == 8 ? 0x800000000000008bU : 0x8000000b00000001U,
- sizeof(void *) == 8 ? 0x8000000000008089U : 0x8000008a00000001U,
- sizeof(void *) == 8 ? 0x8000000000008003U : 0x8000008100000001U,
- sizeof(void *) == 8 ? 0x8000000000008002U : 0x8000008100000000U,
- sizeof(void *) == 8 ? 0x8000000000000080U : 0x8000000800000000U,
- sizeof(void *) == 8 ? 0x000000000000800aU : 0x0000008300000000U,
- sizeof(void *) == 8 ? 0x800000008000000aU : 0x8000800300000000U,
- sizeof(void *) == 8 ? 0x8000000080008081U : 0x8000808800000001U,
- sizeof(void *) == 8 ? 0x8000000000008080U : 0x8000008800000000U,
- sizeof(void *) == 8 ? 0x0000000080000001U : 0x0000800000000001U,
- sizeof(void *) == 8 ? 0x8000000080008008U : 0x8000808200000000U
+ BIT_INTERLEAVE ? 0x0000000000000001U : 0x0000000000000001U,
+ BIT_INTERLEAVE ? 0x0000008900000000U : 0x0000000000008082U,
+ BIT_INTERLEAVE ? 0x8000008b00000000U : 0x800000000000808aU,
+ BIT_INTERLEAVE ? 0x8000808000000000U : 0x8000000080008000U,
+ BIT_INTERLEAVE ? 0x0000008b00000001U : 0x000000000000808bU,
+ BIT_INTERLEAVE ? 0x0000800000000001U : 0x0000000080000001U,
+ BIT_INTERLEAVE ? 0x8000808800000001U : 0x8000000080008081U,
+ BIT_INTERLEAVE ? 0x8000008200000001U : 0x8000000000008009U,
+ BIT_INTERLEAVE ? 0x0000000b00000000U : 0x000000000000008aU,
+ BIT_INTERLEAVE ? 0x0000000a00000000U : 0x0000000000000088U,
+ BIT_INTERLEAVE ? 0x0000808200000001U : 0x0000000080008009U,
+ BIT_INTERLEAVE ? 0x0000800300000000U : 0x000000008000000aU,
+ BIT_INTERLEAVE ? 0x0000808b00000001U : 0x000000008000808bU,
+ BIT_INTERLEAVE ? 0x8000000b00000001U : 0x800000000000008bU,
+ BIT_INTERLEAVE ? 0x8000008a00000001U : 0x8000000000008089U,
+ BIT_INTERLEAVE ? 0x8000008100000001U : 0x8000000000008003U,
+ BIT_INTERLEAVE ? 0x8000008100000000U : 0x8000000000008002U,
+ BIT_INTERLEAVE ? 0x8000000800000000U : 0x8000000000000080U,
+ BIT_INTERLEAVE ? 0x0000008300000000U : 0x000000000000800aU,
+ BIT_INTERLEAVE ? 0x8000800300000000U : 0x800000008000000aU,
+ BIT_INTERLEAVE ? 0x8000808800000001U : 0x8000000080008081U,
+ BIT_INTERLEAVE ? 0x8000008800000000U : 0x8000000000008080U,
+ BIT_INTERLEAVE ? 0x0000800000000001U : 0x0000000080000001U,
+ BIT_INTERLEAVE ? 0x8000808200000000U : 0x8000000080008008U
};
#if defined(KECCAK_REF)
A[0][0] ^= iotas[i];
}
-void KeccakF1600(uint64_t A[5][5])
+static void KeccakF1600(uint64_t A[5][5])
{
size_t i;
A[4][4] = C[4] ^ (~C[0] & C[1]);
}
-void KeccakF1600(uint64_t A[5][5])
+static void KeccakF1600(uint64_t A[5][5])
{
size_t i;
#elif defined(KECCAK_1X_ALT)
/*
- * This is variant of above KECCAK_1X that presses temporary storage
- * even further, but at cost of more write references to A[5][5].
- * It's less suitable if A[5][5] is memory bound, but better if it's
+ * This is variant of above KECCAK_1X that reduces requirement for
+ * temporary storage even further, but at cost of more updates to A[][].
+ * It's less suitable if A[][] is memory bound, but better if it's
* register bound.
*/
C[3] = A[0][3] ^ A[1][3] ^ A[2][3] ^ A[3][3] ^ A[4][3];
C[4] = A[0][4] ^ A[1][4] ^ A[2][4] ^ A[3][4] ^ A[4][4];
- D[0] = ROL64(C[1], 1) ^ C[4];
- A[0][0] ^= D[0];
- A[1][0] ^= D[0];
- A[2][0] ^= D[0];
- A[3][0] ^= D[0];
- A[4][0] ^= D[0];
+ D[1] = C[0] ^ ROL64(C[2], 1);
+ D[2] = C[1] ^ ROL64(C[3], 1);
+ D[3] = C[2] ^= ROL64(C[4], 1);
+ D[4] = C[3] ^= ROL64(C[0], 1);
+ D[0] = C[4] ^= ROL64(C[1], 1);
- D[1] = ROL64(C[2], 1) ^ C[0];
A[0][1] ^= D[1];
A[1][1] ^= D[1];
A[2][1] ^= D[1];
A[3][1] ^= D[1];
A[4][1] ^= D[1];
- D[2] = ROL64(C[3], 1) ^ C[1];
A[0][2] ^= D[2];
A[1][2] ^= D[2];
A[2][2] ^= D[2];
A[3][2] ^= D[2];
A[4][2] ^= D[2];
- D[3] = ROL64(C[4], 1) ^ C[2];
- A[0][3] ^= D[3];
- A[1][3] ^= D[3];
- A[2][3] ^= D[3];
- A[3][3] ^= D[3];
- A[4][3] ^= D[3];
+ A[0][3] ^= C[2];
+ A[1][3] ^= C[2];
+ A[2][3] ^= C[2];
+ A[3][3] ^= C[2];
+ A[4][3] ^= C[2];
+
+ A[0][4] ^= C[3];
+ A[1][4] ^= C[3];
+ A[2][4] ^= C[3];
+ A[3][4] ^= C[3];
+ A[4][4] ^= C[3];
- D[4] = ROL64(C[0], 1) ^ C[3];
- A[0][4] ^= D[4];
- A[1][4] ^= D[4];
- A[2][4] ^= D[4];
- A[3][4] ^= D[4];
- A[4][4] ^= D[4];
+ A[0][0] ^= C[4];
+ A[1][0] ^= C[4];
+ A[2][0] ^= C[4];
+ A[3][0] ^= C[4];
+ A[4][0] ^= C[4];
C[1] = A[0][1];
C[2] = A[0][2];
C[0] = A[0][0];
C[1] = A[1][0];
- C[2] = A[2][0];
- C[3] = A[3][0];
- C[4] = A[4][0];
-
D[0] = A[0][1];
D[1] = A[1][1];
- D[2] = A[2][1];
- D[3] = A[3][1];
- D[4] = A[4][1];
A[0][0] ^= (~A[0][1] & A[0][2]);
A[1][0] ^= (~A[1][1] & A[1][2]);
- A[2][0] ^= (~A[2][1] & A[2][2]);
- A[3][0] ^= (~A[3][1] & A[3][2]);
- A[4][0] ^= (~A[4][1] & A[4][2]);
-
A[0][1] ^= (~A[0][2] & A[0][3]);
A[1][1] ^= (~A[1][2] & A[1][3]);
- A[2][1] ^= (~A[2][2] & A[2][3]);
- A[3][1] ^= (~A[3][2] & A[3][3]);
- A[4][1] ^= (~A[4][2] & A[4][3]);
-
A[0][2] ^= (~A[0][3] & A[0][4]);
A[1][2] ^= (~A[1][3] & A[1][4]);
- A[2][2] ^= (~A[2][3] & A[2][4]);
- A[3][2] ^= (~A[3][3] & A[3][4]);
- A[4][2] ^= (~A[4][3] & A[4][4]);
-
A[0][3] ^= (~A[0][4] & C[0]);
A[1][3] ^= (~A[1][4] & C[1]);
- A[2][3] ^= (~A[2][4] & C[2]);
- A[3][3] ^= (~A[3][4] & C[3]);
- A[4][3] ^= (~A[4][4] & C[4]);
-
A[0][4] ^= (~C[0] & D[0]);
A[1][4] ^= (~C[1] & D[1]);
+
+ C[2] = A[2][0];
+ C[3] = A[3][0];
+ D[2] = A[2][1];
+ D[3] = A[3][1];
+
+ A[2][0] ^= (~A[2][1] & A[2][2]);
+ A[3][0] ^= (~A[3][1] & A[3][2]);
+ A[2][1] ^= (~A[2][2] & A[2][3]);
+ A[3][1] ^= (~A[3][2] & A[3][3]);
+ A[2][2] ^= (~A[2][3] & A[2][4]);
+ A[3][2] ^= (~A[3][3] & A[3][4]);
+ A[2][3] ^= (~A[2][4] & C[2]);
+ A[3][3] ^= (~A[3][4] & C[3]);
A[2][4] ^= (~C[2] & D[2]);
A[3][4] ^= (~C[3] & D[3]);
- A[4][4] ^= (~C[4] & D[4]);
+ C[4] = A[4][0];
+ D[4] = A[4][1];
+
+ A[4][0] ^= (~A[4][1] & A[4][2]);
+ A[4][1] ^= (~A[4][2] & A[4][3]);
+ A[4][2] ^= (~A[4][3] & A[4][4]);
+ A[4][3] ^= (~A[4][4] & C[4]);
+ A[4][4] ^= (~C[4] & D[4]);
A[0][0] ^= iotas[i];
}
-void KeccakF1600(uint64_t A[5][5])
+static void KeccakF1600(uint64_t A[5][5])
{
size_t i;
* This implementation is variant of KECCAK_1X above with outer-most
* round loop unrolled twice. This allows to take temporary storage
* out of round procedure and simplify references to it by alternating
- * it with actual data (see round loop below). Just like original, it's
- * rather meant as reference for an assembly implementation. It's likely
- * to provide best instruction per processed byte ratio at minimal
- * round unroll factor...
+ * it with actual data (see round loop below). Originally it was meant
+ * rather as reference for an assembly implementation, but it seems to
+ * play best with compilers [as well as provide best instruction per
+ * processed byte ratio at minimal round unroll factor]...
*/
static void Round(uint64_t R[5][5], uint64_t A[5][5], size_t i)
{
#endif
}
-void KeccakF1600(uint64_t A[5][5])
+static void KeccakF1600(uint64_t A[5][5])
{
uint64_t T[5][5];
size_t i;
#endif
}
-#else
+#else /* define KECCAK_INPLACE to compile this code path */
/*
* This implementation is KECCAK_1X from above combined 4 times with
* a twist that allows to omit temporary storage and perform in-place
* processing. It's discussed in section 2.5 of "Keccak implementation
* overview". It's likely to be best suited for processors with large
- * register bank...
+ * register bank... On the other hand processor with large register
+ * bank can as well use KECCAK_1X_ALT, it would be as fast but much
+ * more compact...
*/
static void FourRounds(uint64_t A[5][5], size_t i)
{
/* C[4] ^= */ A[4][4] = B[4] ^ (~B[0] & B[1]);
}
-void KeccakF1600(uint64_t A[5][5])
+static void KeccakF1600(uint64_t A[5][5])
{
size_t i;
static uint64_t BitInterleave(uint64_t Ai)
{
- if (sizeof(void *) < 8) {
- uint32_t hi = 0, lo = 0;
- int j;
-
- for (j = 0; j < 32; j++) {
- lo |= ((uint32_t)(Ai >> (2 * j)) & 1) << j;
- hi |= ((uint32_t)(Ai >> (2 * j + 1)) & 1) << j;
- }
-
- Ai = ((uint64_t)hi << 32) | lo;
+ if (BIT_INTERLEAVE) {
+ uint32_t hi = (uint32_t)(Ai >> 32), lo = (uint32_t)Ai;
+ uint32_t t0, t1;
+
+ t0 = lo & 0x55555555;
+ t0 |= t0 >> 1; t0 &= 0x33333333;
+ t0 |= t0 >> 2; t0 &= 0x0f0f0f0f;
+ t0 |= t0 >> 4; t0 &= 0x00ff00ff;
+ t0 |= t0 >> 8; t0 &= 0x0000ffff;
+
+ t1 = hi & 0x55555555;
+ t1 |= t1 >> 1; t1 &= 0x33333333;
+ t1 |= t1 >> 2; t1 &= 0x0f0f0f0f;
+ t1 |= t1 >> 4; t1 &= 0x00ff00ff;
+ t1 |= t1 >> 8; t1 <<= 16;
+
+ lo &= 0xaaaaaaaa;
+ lo |= lo << 1; lo &= 0xcccccccc;
+ lo |= lo << 2; lo &= 0xf0f0f0f0;
+ lo |= lo << 4; lo &= 0xff00ff00;
+ lo |= lo << 8; lo >>= 16;
+
+ hi &= 0xaaaaaaaa;
+ hi |= hi << 1; hi &= 0xcccccccc;
+ hi |= hi << 2; hi &= 0xf0f0f0f0;
+ hi |= hi << 4; hi &= 0xff00ff00;
+ hi |= hi << 8; hi &= 0xffff0000;
+
+ Ai = ((uint64_t)(hi | lo) << 32) | (t1 | t0);
}
return Ai;
static uint64_t BitDeinterleave(uint64_t Ai)
{
- if (sizeof(void *) < 8) {
+ if (BIT_INTERLEAVE) {
uint32_t hi = (uint32_t)(Ai >> 32), lo = (uint32_t)Ai;
- int j;
-
- Ai = 0;
- for (j = 0; j < 32; j++) {
- Ai |= (uint64_t)((lo >> j) & 1) << (2 * j);
- Ai |= (uint64_t)((hi >> j) & 1) << (2 * j + 1);
- }
+ uint32_t t0, t1;
+
+ t0 = lo & 0x0000ffff;
+ t0 |= t0 << 8; t0 &= 0x00ff00ff;
+ t0 |= t0 << 4; t0 &= 0x0f0f0f0f;
+ t0 |= t0 << 2; t0 &= 0x33333333;
+ t0 |= t0 << 1; t0 &= 0x55555555;
+
+ t1 = hi << 16;
+ t1 |= t1 >> 8; t1 &= 0xff00ff00;
+ t1 |= t1 >> 4; t1 &= 0xf0f0f0f0;
+ t1 |= t1 >> 2; t1 &= 0xcccccccc;
+ t1 |= t1 >> 1; t1 &= 0xaaaaaaaa;
+
+ lo >>= 16;
+ lo |= lo << 8; lo &= 0x00ff00ff;
+ lo |= lo << 4; lo &= 0x0f0f0f0f;
+ lo |= lo << 2; lo &= 0x33333333;
+ lo |= lo << 1; lo &= 0x55555555;
+
+ hi &= 0xffff0000;
+ hi |= hi >> 8; hi &= 0xff00ff00;
+ hi |= hi >> 4; hi &= 0xf0f0f0f0;
+ hi |= hi >> 2; hi &= 0xcccccccc;
+ hi |= hi >> 1; hi &= 0xaaaaaaaa;
+
+ Ai = ((uint64_t)(hi | lo) << 32) | (t1 | t0);
}
return Ai;
void SHA3_squeeze(uint64_t A[5][5], unsigned char *out, size_t len, size_t r)
{
uint64_t *A_flat = (uint64_t *)A;
- size_t i, rem, w = r / 8;
+ size_t i, w = r / 8;
assert(r < (25 * sizeof(A[0][0])) && (r % 8) == 0);
- while (len >= r) {
- for (i = 0; i < w; i++) {
+ while (len != 0) {
+ for (i = 0; i < w && len != 0; i++) {
uint64_t Ai = BitDeinterleave(A_flat[i]);
+ if (len < 8) {
+ for (i = 0; i < len; i++) {
+ *out++ = (unsigned char)Ai;
+ Ai >>= 8;
+ }
+ return;
+ }
+
out[0] = (unsigned char)(Ai);
out[1] = (unsigned char)(Ai >> 8);
out[2] = (unsigned char)(Ai >> 16);
out[6] = (unsigned char)(Ai >> 48);
out[7] = (unsigned char)(Ai >> 56);
out += 8;
+ len -= 8;
}
- len -= r;
if (len)
KeccakF1600(A);
}
-
- rem = len % 8;
- len /= 8;
-
- for (i = 0; i < len; i++) {
- uint64_t Ai = BitDeinterleave(A_flat[i]);
-
- out[0] = (unsigned char)(Ai);
- out[1] = (unsigned char)(Ai >> 8);
- out[2] = (unsigned char)(Ai >> 16);
- out[3] = (unsigned char)(Ai >> 24);
- out[4] = (unsigned char)(Ai >> 32);
- out[5] = (unsigned char)(Ai >> 40);
- out[6] = (unsigned char)(Ai >> 48);
- out[7] = (unsigned char)(Ai >> 56);
- out += 8;
- }
-
- if (rem) {
- uint64_t Ai = BitDeinterleave(A_flat[i]);
-
- for (i = 0; i < rem; i++) {
- *out++ = (unsigned char)Ai;
- Ai >>= 8;
- }
- }
}
+#endif
#ifdef SELFTEST
/*