Skip to content

Instantly share code, notes, and snippets.

@busterb

busterb/gist:631e2cf61a55de87d6b8

Last active August 29, 2015 14:00
Show Gist options
  • Save busterb/631e2cf61a55de87d6b8 to your computer and use it in GitHub Desktop.
Save busterb/631e2cf61a55de87d6b8 to your computer and use it in GitHub Desktop.
Download ZIP
HAVEGE extracted from xyssl 0.9 (appears unchanged in PolarSSL 1.3 except for interface)
Raw
gistfile1.txt
/*
* HAVEGE: HArdware Volatile Entropy Gathering and Expansion
*
* Copyright (C) 2006-2007 Christophe Devine
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* * Neither the name of XySSL nor the names of its contributors may be
* used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
* TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
/*
* The HAVEGE RNG was designed by Andre Seznec in 2002.
*
* http://www.irisa.fr/caps/projects/hipsor/publi.php
*
* Contact: seznec(at)irisa_dot_fr - orocheco(at)irisa_dot_fr
*/
#include <string.h>
#include <time.h>
/**
* \file havege.h
*/
#ifndef HAVEGE_H
#define HAVEGE_H
#define COLLECT_SIZE 1024
/**
* \brief HAVEGE state structure
*/
typedef struct {
int PT1, PT2, offset[2];
int pool[COLLECT_SIZE];
int WALK[8192];
} havege_state;
#ifdef __cplusplus
extern "C" {
#endif
/**
* \brief HAVEGE initialization
*
* \param hs HAVEGE state to be initialized
*/
void havege_init(havege_state * hs);
/**
* \brief HAVEGE rand function
*
* \param rng_st points to an HAVEGE state
*
* \return A random int
*/
int havege_rand(void *p_rng);
#ifdef __cplusplus
}
#endif
#endif /* havege.h */
#if (defined(_MSC_VER) && defined(_M_IX86)) || defined(__WATCOMC__)
unsigned long hardclock(void)
{
unsigned long tsc;
__asm rdtsc __asm mov[tsc], eax return (tsc);
}
#else
#if defined(__GNUC__) && defined(__i386__)
unsigned long hardclock(void)
{
unsigned long tsc;
asm("rdtsc":"=a"(tsc));
return (tsc);
}
#else
#if defined(__GNUC__) && (defined(__amd64__) || defined(__x86_64__))
unsigned long hardclock(void)
{
unsigned long lo, hi;
asm("rdtsc":"=a"(lo), "=d"(hi));
return (lo | (hi << 32));
}
#else
#if defined(__GNUC__) && (defined(__powerpc__) || defined(__ppc__))
unsigned long hardclock(void)
{
unsigned long tbl, tbu0, tbu1;
do {
asm("mftbu %0":"=r"(tbu0));
asm("mftb %0":"=r"(tbl));
asm("mftbu %0":"=r"(tbu1));
}
while (tbu0 != tbu1);
return (tbl);
}
#else
#if defined(__GNUC__) && defined(__sparc__)
unsigned long hardclock(void)
{
unsigned long tick;
asm(".byte 0x83, 0x41, 0x00, 0x00");
asm("mov %%g1, %0":"=r"(tick));
return (tick);
}
#else
#if defined(__GNUC__) && defined(__alpha__)
unsigned long hardclock(void)
{
unsigned long cc;
asm("rpcc %0":"=r"(cc));
return (cc & 0xFFFFFFFF);
}
#else
#if defined(__GNUC__) && defined(__ia64__)
unsigned long hardclock(void)
{
unsigned long itc;
asm("mov %0 = ar.itc":"=r"(itc));
return (itc);
}
#else
static int hardclock_init = 0;
static struct timeval tv_init;
unsigned long hardclock(void)
{
struct timeval tv_cur;
if (hardclock_init == 0) {
gettimeofday(&tv_init, NULL);
hardclock_init = 1;
}
gettimeofday(&tv_cur, NULL);
return ((tv_cur.tv_sec - tv_init.tv_sec) * 1000000 + (tv_cur.tv_usec - tv_init.tv_usec));
}
#endif /* generic */
#endif /* IA-64 */
#endif /* Alpha */
#endif /* SPARC8 */
#endif /* PowerPC */
#endif /* AMD64 */
#endif /* i586+ */
/* ------------------------------------------------------------------------
* On average, one iteration accesses two 8-word blocks in the havege WALK
* table, and generates 16 words in the RES array.
*
* The data read in the WALK table is updated and permuted after each use.
* The result of the hardware clock counter read is used for this update.
*
* 25 conditional tests are present. The conditional tests are grouped in
* two nested groups of 12 conditional tests and 1 test that controls the
* permutation; on average, there should be 6 tests executed and 3 of them
* should be mispredicted.
* ------------------------------------------------------------------------
*/
#define SWAP(X,Y) { int *T = X; X = Y; Y = T; }
#define TST1_ENTER if( PTEST & 1 ) { PTEST ^= 3; PTEST >>= 1;
#define TST2_ENTER if( PTEST & 1 ) { PTEST ^= 3; PTEST >>= 1;
#define TST1_LEAVE U1++; }
#define TST2_LEAVE U2++; }
#define ONE_ITERATION \
\
PTEST = PT1 >> 20; \
\
TST1_ENTER TST1_ENTER TST1_ENTER TST1_ENTER \
TST1_ENTER TST1_ENTER TST1_ENTER TST1_ENTER \
TST1_ENTER TST1_ENTER TST1_ENTER TST1_ENTER \
\
TST1_LEAVE TST1_LEAVE TST1_LEAVE TST1_LEAVE \
TST1_LEAVE TST1_LEAVE TST1_LEAVE TST1_LEAVE \
TST1_LEAVE TST1_LEAVE TST1_LEAVE TST1_LEAVE \
\
PTX = (PT1 >> 18) & 7; \
PT1 &= 0x1FFF; \
PT2 &= 0x1FFF; \
CLK = (int) hardclock(); \
\
i = 0; \
A = &WALK[PT1 ]; RES[i++] ^= *A; \
B = &WALK[PT2 ]; RES[i++] ^= *B; \
C = &WALK[PT1 ^ 1]; RES[i++] ^= *C; \
D = &WALK[PT2 ^ 4]; RES[i++] ^= *D; \
\
IN = (*A >> (1)) ^ (*A << (31)) ^ CLK; \
*A = (*B >> (2)) ^ (*B << (30)) ^ CLK; \
*B = IN ^ U1; \
*C = (*C >> (3)) ^ (*C << (29)) ^ CLK; \
*D = (*D >> (4)) ^ (*D << (28)) ^ CLK; \
\
A = &WALK[PT1 ^ 2]; RES[i++] ^= *A; \
B = &WALK[PT2 ^ 2]; RES[i++] ^= *B; \
C = &WALK[PT1 ^ 3]; RES[i++] ^= *C; \
D = &WALK[PT2 ^ 6]; RES[i++] ^= *D; \
\
if( PTEST & 1 ) SWAP( A, C ); \
\
IN = (*A >> (5)) ^ (*A << (27)) ^ CLK; \
*A = (*B >> (6)) ^ (*B << (26)) ^ CLK; \
*B = IN; CLK = (int) hardclock(); \
*C = (*C >> (7)) ^ (*C << (25)) ^ CLK; \
*D = (*D >> (8)) ^ (*D << (24)) ^ CLK; \
\
A = &WALK[PT1 ^ 4]; \
B = &WALK[PT2 ^ 1]; \
\
PTEST = PT2 >> 1; \
\
PT2 = (RES[(i - 8) ^ PTY] ^ WALK[PT2 ^ PTY ^ 7]); \
PT2 = ((PT2 & 0x1FFF) & (~8)) ^ ((PT1 ^ 8) & 0x8); \
PTY = (PT2 >> 10) & 7; \
\
TST2_ENTER TST2_ENTER TST2_ENTER TST2_ENTER \
TST2_ENTER TST2_ENTER TST2_ENTER TST2_ENTER \
TST2_ENTER TST2_ENTER TST2_ENTER TST2_ENTER \
\
TST2_LEAVE TST2_LEAVE TST2_LEAVE TST2_LEAVE \
TST2_LEAVE TST2_LEAVE TST2_LEAVE TST2_LEAVE \
TST2_LEAVE TST2_LEAVE TST2_LEAVE TST2_LEAVE \
\
C = &WALK[PT1 ^ 5]; \
D = &WALK[PT2 ^ 5]; \
\
RES[i++] ^= *A; \
RES[i++] ^= *B; \
RES[i++] ^= *C; \
RES[i++] ^= *D; \
\
IN = (*A >> ( 9)) ^ (*A << (23)) ^ CLK; \
*A = (*B >> (10)) ^ (*B << (22)) ^ CLK; \
*B = IN ^ U2; \
*C = (*C >> (11)) ^ (*C << (21)) ^ CLK; \
*D = (*D >> (12)) ^ (*D << (20)) ^ CLK; \
\
A = &WALK[PT1 ^ 6]; RES[i++] ^= *A; \
B = &WALK[PT2 ^ 3]; RES[i++] ^= *B; \
C = &WALK[PT1 ^ 7]; RES[i++] ^= *C; \
D = &WALK[PT2 ^ 7]; RES[i++] ^= *D; \
\
IN = (*A >> (13)) ^ (*A << (19)) ^ CLK; \
*A = (*B >> (14)) ^ (*B << (18)) ^ CLK; \
*B = IN; \
*C = (*C >> (15)) ^ (*C << (17)) ^ CLK; \
*D = (*D >> (16)) ^ (*D << (16)) ^ CLK; \
\
PT1 = ( RES[(i - 8) ^ PTX] ^ \
WALK[PT1 ^ PTX ^ 7] ) & (~1); \
PT1 ^= (PT2 ^ 0x10) & 0x10; \
\
for( n++, i = 0; i < 16; i++ ) \
hs->pool[n % COLLECT_SIZE] ^= RES[i];
/*
* Entropy gathering function
*/
static void havege_fill(havege_state * hs)
{
int i, n = 0;
int U1, U2, *A, *B, *C, *D;
int PT1, PT2, *WALK, RES[16];
int PTX, PTY, CLK, PTEST, IN;
WALK = hs->WALK;
PT1 = hs->PT1;
PT2 = hs->PT2;
PTX = U1 = 0;
PTY = U2 = 0;
memset(RES, 0, sizeof(RES));
while (n < COLLECT_SIZE * 4) {
ONE_ITERATION ONE_ITERATION ONE_ITERATION ONE_ITERATION}
hs->PT1 = PT1;
hs->PT2 = PT2;
hs->offset[0] = 0;
hs->offset[1] = COLLECT_SIZE / 2;
}
/*
* HAVEGE initialization
*/
void havege_init(havege_state * hs)
{
memset(hs, 0, sizeof(havege_state));
havege_fill(hs);
}
/*
* HAVEGE rand function
*/
int havege_rand(void *p_rng)
{
int ret;
havege_state *hs = (havege_state *) p_rng;
if (hs->offset[1] >= COLLECT_SIZE)
havege_fill(hs);
ret = hs->pool[hs->offset[0]++];
ret ^= hs->pool[hs->offset[1]++];
return (ret);
}
#if !defined(BUILD_LIB)
#include <stdio.h>
int main(int argc, char *argv[])
{
FILE *f;
time_t t;
int i, j, k;
havege_state hs;
unsigned char buf[1024];
if (argc < 2) {
fprintf(stderr, "usage: %s <output filename>\n", argv[0]);
return (1);
}
if ((f = fopen(argv[1], "wb+")) == NULL) {
printf("failed to open '%s' for writing.\n", argv[0]);
return (1);
}
havege_init(&hs);
t = time(NULL);
for (i = 0, k = 32768; i < k; i++) {
for (j = 0; j < sizeof(buf); j++)
buf[j] = havege_rand(&hs);
fwrite(buf, sizeof(buf), 1, f);
printf("Generating 32Mb of data in file '%s'... %04.1f"
"%% done\r", argv[1], (100 * (float)(i + 1)) / k);
fflush(stdout);
}
if (t == time(NULL))
t--;
fclose(f);
return (0);
}
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment