blob: a1c1e7d2ee5b982db30d4f85d99e800a7304aea9 [file] [log] [blame]
/*
* cifra - embedded cryptography library
* Written in 2014 by Joseph Birr-Pixton <jpixton@gmail.com>
*
* To the extent possible under law, the author(s) have dedicated all
* copyright and related and neighboring rights to this software to the
* public domain worldwide. This software is distributed without any
* warranty.
*
* You should have received a copy of the CC0 Public Domain Dedication
* along with this software. If not, see
* <http://creativecommons.org/publicdomain/zero/1.0/>.
*/
#ifndef BITOPS_H
#define BITOPS_H
#include <stdint.h>
#include <stddef.h>
#ifdef _WINDOWS
#include <intrin.h>
#endif
/* Assorted bitwise and common operations used in ciphers. */
/** Circularly rotate right x by n bits.
* 0 > n > 32. */
static inline uint32_t rotr32(uint32_t x, unsigned n)
{
return (x >> n) | (x << (32 - n));
}
/** Circularly rotate left x by n bits.
* 0 > n > 32. */
static inline uint32_t rotl32(uint32_t x, unsigned n)
{
return (x << n) | (x >> (32 - n));
}
/** Circularly rotate right x by n bits.
* 0 > n > 64. */
static inline uint64_t rotr64(uint64_t x, unsigned n)
{
return (x >> n) | (x << (64 - n));
}
/** Circularly rotate left x by n bits.
* 0 > n > 64. */
static inline uint64_t rotl64(uint64_t x, unsigned n)
{
return (x << n) | (x >> (64 - n));
}
/** Read 4 bytes from buf, as a 32-bit big endian quantity. */
static inline uint32_t read32_be(const uint8_t buf[4])
{
return ((uint32_t)buf[0] << 24) |
((uint32_t)buf[1] << 16) |
((uint32_t)buf[2] << 8) |
((uint32_t)buf[3]);
}
/** Read 4 bytes from buf, as a 32-bit little endian quantity. */
static inline uint32_t read32_le(const uint8_t buf[4])
{
return ((uint32_t)buf[3] << 24) |
((uint32_t)buf[2] << 16) |
((uint32_t)buf[1] << 8) |
((uint32_t)buf[0]);
}
/** Read 8 bytes from buf, as a 64-bit big endian quantity. */
static inline uint64_t read64_be(const uint8_t buf[8])
{
uint32_t hi = read32_be(buf),
lo = read32_be(buf + 4);
return ((uint64_t)hi) << 32 |
lo;
}
/** Read 8 bytes from buf, as a 64-bit little endian quantity. */
static inline uint64_t read64_le(const uint8_t buf[8])
{
uint32_t hi = read32_le(buf + 4),
lo = read32_le(buf);
return ((uint64_t)hi) << 32 |
lo;
}
/** Encode v as a 32-bit big endian quantity into buf. */
static inline void write32_be(uint32_t v, uint8_t buf[4])
{
*buf++ = (v >> 24) & 0xff;
*buf++ = (v >> 16) & 0xff;
*buf++ = (v >> 8) & 0xff;
*buf = v & 0xff;
}
/** Encode v as a 32-bit little endian quantity into buf. */
static inline void write32_le(uint32_t v, uint8_t buf[4])
{
*buf++ = v & 0xff;
*buf++ = (v >> 8) & 0xff;
*buf++ = (v >> 16) & 0xff;
*buf = (v >> 24) & 0xff;
}
/** Encode v as a 64-bit big endian quantity into buf. */
static inline void write64_be(uint64_t v, uint8_t buf[8])
{
*buf++ = (v >> 56) & 0xff;
*buf++ = (v >> 48) & 0xff;
*buf++ = (v >> 40) & 0xff;
*buf++ = (v >> 32) & 0xff;
*buf++ = (v >> 24) & 0xff;
*buf++ = (v >> 16) & 0xff;
*buf++ = (v >> 8) & 0xff;
*buf = v & 0xff;
}
/** Encode v as a 64-bit little endian quantity into buf. */
static inline void write64_le(uint64_t v, uint8_t buf[8])
{
*buf++ = v & 0xff;
*buf++ = (v >> 8) & 0xff;
*buf++ = (v >> 16) & 0xff;
*buf++ = (v >> 24) & 0xff;
*buf++ = (v >> 32) & 0xff;
*buf++ = (v >> 40) & 0xff;
*buf++ = (v >> 48) & 0xff;
*buf = (v >> 56) & 0xff;
}
/** out = in ^ b8.
* out and in may alias. */
static inline void xor_b8(uint8_t *out, const uint8_t *in, uint8_t b8, size_t len)
{
size_t i;
for (i = 0; i < len; i++)
out[i] = in[i] ^ b8;
}
/** out = x ^ y.
* out, x and y may alias. */
static inline void xor_bb(uint8_t *out, const uint8_t *x, const uint8_t *y, size_t len)
{
size_t i;
for (i = 0; i < len; i++)
out[i] = x[i] ^ y[i];
}
/* out ^= x
* out and x may alias. */
static inline void xor_words(uint32_t *out, const uint32_t *x, size_t nwords)
{
size_t i;
for (i = 0; i < nwords; i++)
out[i] ^= x[i];
}
/** Produce 0xffffffff if x == y, zero otherwise, without branching. */
static inline uint32_t mask_u32(uint32_t x, uint32_t y)
{
uint32_t diff = x ^ y;
uint32_t diff_is_zero = ~diff & (diff - 1);
return (uint32_t)(-(int32_t)(diff_is_zero >> 31));
}
/** Product 0xff if x == y, zero otherwise, without branching. */
static inline uint8_t mask_u8(uint32_t x, uint32_t y)
{
uint32_t diff = x ^ y;
uint8_t diff_is_zero = ~diff & (diff - 1);
return - (diff_is_zero >> 7);
}
/** Select the ith entry from the given table of n values, in a side channel-silent
* way. */
static inline uint32_t select_u32(uint32_t i, volatile const uint32_t *tab, uint32_t n)
{
uint32_t r = 0, ii;
for (ii = 0; ii < n; ii++)
{
uint32_t mask = mask_u32(i, ii);
r = (r & ~mask) | (tab[ii] & mask);
}
return r;
}
/** Select the ith entry from the given table of n values, in a side channel-silent
* way. */
static inline uint8_t select_u8(uint32_t i, volatile const uint8_t *tab, uint32_t n)
{
uint8_t r = 0;
uint32_t ii;
for (ii = 0; ii < n; ii++)
{
uint8_t mask = mask_u8(i, ii);
r = (r & ~mask) | (tab[ii] & mask);
}
return r;
}
/** Select the ath, bth, cth and dth entries from the given table of n values,
* placing the results into a, b, c and d. */
static inline void select_u8x4(uint8_t *a, uint8_t *b, uint8_t *c, uint8_t *d,
volatile const uint8_t *tab, uint32_t n)
{
uint8_t ra = 0,
rb = 0,
rc = 0,
rd = 0;
uint8_t mask;
uint32_t i;
for (i = 0; i < n; i++)
{
uint8_t item = tab[i];
mask = mask_u8(*a, i); ra = (ra & ~mask) | (item & mask);
mask = mask_u8(*b, i); rb = (rb & ~mask) | (item & mask);
mask = mask_u8(*c, i); rc = (rc & ~mask) | (item & mask);
mask = mask_u8(*d, i); rd = (rd & ~mask) | (item & mask);
}
*a = ra;
*b = rb;
*c = rc;
*d = rd;
}
/** out ^= if0 or if1, depending on the value of bit. */
static inline void select_xor128(uint32_t out[4],
const uint32_t if0[4],
const uint32_t if1[4],
uint8_t bit)
{
uint32_t mask1 = mask_u32(bit, 1);
uint32_t mask0 = ~mask1;
out[0] ^= (if0[0] & mask0) | (if1[0] & mask1);
out[1] ^= (if0[1] & mask0) | (if1[1] & mask1);
out[2] ^= (if0[2] & mask0) | (if1[2] & mask1);
out[3] ^= (if0[3] & mask0) | (if1[3] & mask1);
}
/** Increments the integer stored at v (of non-zero length len)
* with the least significant byte first. */
static inline void incr_le(uint8_t *v, size_t len)
{
size_t i = 0;
while (1)
{
if (++v[i] != 0)
return;
i++;
if (i == len)
return;
}
}
/** Increments the integer stored at v (of non-zero length len)
* with the most significant byte last. */
static inline void incr_be(uint8_t *v, size_t len)
{
len--;
while (1)
{
if (++v[len] != 0)
return;
if (len == 0)
return;
len--;
}
}
/** Copies len bytes from in to out, with in shifted left by offset bits
* to the right. */
static inline void copy_bytes_unaligned(uint8_t *out, const uint8_t *in, size_t len, uint8_t offset)
{
uint8_t byte_off = offset / 8;
uint8_t bit_off = offset & 7;
uint8_t rmask = (1 << bit_off) - 1;
uint8_t lmask = ~rmask;
size_t i;
for (i = 0; i < len; i++)
{
out[i] = (in[i + byte_off] << bit_off) & lmask;
out[i] |= (in[i + byte_off + 1] >> (8 - bit_off)) & rmask;
}
}
static inline uint32_t count_trailing_zeroes(uint32_t x)
{
#ifdef _WINDOWS
uint32_t r = 0;
_BitScanReverse(&r, x);
return (31 - r);
#else
return (uint32_t) __builtin_ctzl(x);
#endif
}
#endif