Skip to content

Instantly share code, notes, and snippets.

@basinilya

basinilya/fillrand.inc.h

Last active February 22, 2017 18:43
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save basinilya/7cdfcc907ef74615ea709fc3972afed8 to your computer and use it in GitHub Desktop.
Save basinilya/7cdfcc907ef74615ea709fc3972afed8 to your computer and use it in GitHub Desktop.
Download ZIP
Fill buffer with random data using rand()
Raw
fillrand.inc.h
/*
Fill buffer with random data using rand()
void fillrand(unsigned char *buf, size_t sz);
void wfillrand(unsigned short *buf, size_t nelems);
Fastest functions according to test results:
i686:
fillrand32_31_disp (uint32_t, big RAND_MAX, displacement, uchar array)
wfillrand32_31_disp (ditto, but ushort array)
x86_64:
fillrand64_31_disp (ditto, but uint64_t)
wfillrand64_31_disp
*/
/* some defaults */
#ifndef FILLRAND
#define FILLRAND fillrand
#endif
#ifndef FILLRAND_RAND_MAX
#define FILLRAND_RAND_MAX RAND_MAX
#endif
#ifndef FILLRAND_UINTMAX_T
#define FILLRAND_UINTMAX_T uintptr_t
#endif
#ifndef FILLRAND_STEP
#define FILLRAND_STEP -1
#endif
/* include self once for wide version */
#if FILLRAND_UCHAR_MAX != 65535
# undef CONCAT_AB_
# undef CONCAT_AB
# define CONCAT_AB_(a, b) a##b
# define CONCAT_AB(a, b) CONCAT_AB_(a, b)
# define FILLRAND_FUNCPREF w
# define char short
# define FILLRAND_ARGTYPE unsigned short
# define FILLRAND_UCHAR_MAX 65535
# include "fillrand.inc.h"
# undef FILLRAND_FUNCPREF
# undef char
# undef FILLRAND_ARGTYPE
# undef FILLRAND_UCHAR_MAX
# define FILLRAND_FUNCPREF
# define FILLRAND_ARGTYPE void
# define FILLRAND_UCHAR_MAX 255
#endif
/* Extracts pseudo-random bits from the value returned by rand().
It starts by putting the least significant bits to the buffer element, shifts right and repeats.
When not enough random bits ramain, they're saved for future use and rand() called again.
Most significant bits in the new value are not random and they're replaced with the saved bits.
On 32-bit systems the compound value doesn't fit in uintptr_t and some of the saved bits are discarded.
Lastly, the buffer is filled backwards by default.
*/
void CONCAT_AB(FILLRAND_FUNCPREF, FILLRAND) (FILLRAND_ARGTYPE *_buf, size_t nelems)
{
unsigned char *buf = (unsigned char *)_buf;
#if FILLRAND_STEP == 1
size_t i = -1;
size_t endi = nelems - 1;
#else
size_t i = nelems;
size_t endi = 0;
#endif
unsigned int r; /* for unsigned promotion */
FILLRAND_UINTMAX_T rbits = 0;
FILLRAND_UINTMAX_T rbmask = 0;
for (;i != endi;) {
if (rbmask < FILLRAND_UCHAR_MAX) {
r = rand();
#if FILLRAND_NO_BIT_DISPLACEMENT
rbits += r * (rbmask+1);
#else
rbits *= ((unsigned int)FILLRAND_RAND_MAX) + 1;
rbits += r;
#endif
rbmask *= (unsigned int)FILLRAND_RAND_MAX + 1;
rbmask += FILLRAND_RAND_MAX;
}
#if FILLRAND_RAND_MAX <= FILLRAND_UCHAR_MAX
else /* first rand() did not provide enough bits for buf[i] */
#endif
{
i += FILLRAND_STEP;
buf[i] = rbits % (FILLRAND_UCHAR_MAX+1);
rbits /= (FILLRAND_UCHAR_MAX+1);
rbmask /= (FILLRAND_UCHAR_MAX+1);
}
}
}
#undef FILLRAND_FUNCPREF
#undef FILLRAND_ARGTYPE
#undef FILLRAND_UCHAR_MAX
Raw
test-fillrand.c
#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <stdlib.h> /* for exit(3) */
#include <stdint.h>
/* ############################# */
#undef FILLRAND
#undef FILLRAND_UINTMAX_T
#undef FILLRAND_NO_BIT_DISPLACEMENT
#undef FILLRAND_RAND_MAX
#define FILLRAND fillrand32_31_disp
#define FILLRAND_UINTMAX_T uint32_t
#define FILLRAND_NO_BIT_DISPLACEMENT 0
#define FILLRAND_RAND_MAX 0x7FFFFFFF
#include "fillrand.inc.h"
/* ############################# */
#undef FILLRAND
#undef FILLRAND_UINTMAX_T
#undef FILLRAND_NO_BIT_DISPLACEMENT
#undef FILLRAND_RAND_MAX
#define FILLRAND fillrand32_31_nodisp
#define FILLRAND_UINTMAX_T uint32_t
#define FILLRAND_NO_BIT_DISPLACEMENT 1
#define FILLRAND_RAND_MAX 0x7FFFFFFF
#include "fillrand.inc.h"
/* ############################# */
#undef FILLRAND
#undef FILLRAND_UINTMAX_T
#undef FILLRAND_NO_BIT_DISPLACEMENT
#undef FILLRAND_RAND_MAX
#define FILLRAND fillrand32_15_disp
#define FILLRAND_UINTMAX_T uint32_t
#define FILLRAND_NO_BIT_DISPLACEMENT 0
#define FILLRAND_RAND_MAX 0x7FFF
#include "fillrand.inc.h"
/* ############################# */
#undef FILLRAND
#undef FILLRAND_UINTMAX_T
#undef FILLRAND_NO_BIT_DISPLACEMENT
#undef FILLRAND_RAND_MAX
#define FILLRAND fillrand32_15_nodisp
#define FILLRAND_UINTMAX_T uint32_t
#define FILLRAND_NO_BIT_DISPLACEMENT 1
#define FILLRAND_RAND_MAX 0x7FFF
#include "fillrand.inc.h"
/* ############################# */
#undef FILLRAND
#undef FILLRAND_UINTMAX_T
#undef FILLRAND_NO_BIT_DISPLACEMENT
#undef FILLRAND_RAND_MAX
#define FILLRAND fillrand64_31_disp
#define FILLRAND_UINTMAX_T uint64_t
#define FILLRAND_NO_BIT_DISPLACEMENT 0
#define FILLRAND_RAND_MAX 0x7FFFFFFF
#include "fillrand.inc.h"
/* ############################# */
#undef FILLRAND
#undef FILLRAND_UINTMAX_T
#undef FILLRAND_NO_BIT_DISPLACEMENT
#undef FILLRAND_RAND_MAX
#define FILLRAND fillrand64_31_nodisp
#define FILLRAND_UINTMAX_T uint64_t
#define FILLRAND_NO_BIT_DISPLACEMENT 1
#define FILLRAND_RAND_MAX 0x7FFFFFFF
#include "fillrand.inc.h"
/* ############################# */
#undef FILLRAND
#undef FILLRAND_UINTMAX_T
#undef FILLRAND_NO_BIT_DISPLACEMENT
#undef FILLRAND_RAND_MAX
#define FILLRAND fillrand64_15_disp
#define FILLRAND_UINTMAX_T uint64_t
#define FILLRAND_NO_BIT_DISPLACEMENT 0
#define FILLRAND_RAND_MAX 0x7FFF
#include "fillrand.inc.h"
/* ############################# */
#undef FILLRAND
#undef FILLRAND_UINTMAX_T
#undef FILLRAND_NO_BIT_DISPLACEMENT
#undef FILLRAND_RAND_MAX
#define FILLRAND fillrand64_15_nodisp
#define FILLRAND_UINTMAX_T uint64_t
#define FILLRAND_NO_BIT_DISPLACEMENT 1
#define FILLRAND_RAND_MAX 0x7FFF
#include "fillrand.inc.h"
#undef FILLRAND_STEP
#define FILLRAND_STEP 1
/* ############################# */
#undef FILLRAND
#undef FILLRAND_UINTMAX_T
#undef FILLRAND_NO_BIT_DISPLACEMENT
#undef FILLRAND_RAND_MAX
#define FILLRAND fwd_fillrand32_31_disp
#define FILLRAND_UINTMAX_T uint32_t
#define FILLRAND_NO_BIT_DISPLACEMENT 0
#define FILLRAND_RAND_MAX 0x7FFFFFFF
#include "fillrand.inc.h"
/* ############################# */
#undef FILLRAND
#undef FILLRAND_UINTMAX_T
#undef FILLRAND_NO_BIT_DISPLACEMENT
#undef FILLRAND_RAND_MAX
#define FILLRAND fwd_fillrand32_31_nodisp
#define FILLRAND_UINTMAX_T uint32_t
#define FILLRAND_NO_BIT_DISPLACEMENT 1
#define FILLRAND_RAND_MAX 0x7FFFFFFF
#include "fillrand.inc.h"
/* ############################# */
#undef FILLRAND
#undef FILLRAND_UINTMAX_T
#undef FILLRAND_NO_BIT_DISPLACEMENT
#undef FILLRAND_RAND_MAX
#define FILLRAND fwd_fillrand32_15_disp
#define FILLRAND_UINTMAX_T uint32_t
#define FILLRAND_NO_BIT_DISPLACEMENT 0
#define FILLRAND_RAND_MAX 0x7FFF
#include "fillrand.inc.h"
/* ############################# */
#undef FILLRAND
#undef FILLRAND_UINTMAX_T
#undef FILLRAND_NO_BIT_DISPLACEMENT
#undef FILLRAND_RAND_MAX
#define FILLRAND fwd_fillrand32_15_nodisp
#define FILLRAND_UINTMAX_T uint32_t
#define FILLRAND_NO_BIT_DISPLACEMENT 1
#define FILLRAND_RAND_MAX 0x7FFF
#include "fillrand.inc.h"
/* ############################# */
#undef FILLRAND
#undef FILLRAND_UINTMAX_T
#undef FILLRAND_NO_BIT_DISPLACEMENT
#undef FILLRAND_RAND_MAX
#define FILLRAND fwd_fillrand64_31_disp
#define FILLRAND_UINTMAX_T uint64_t
#define FILLRAND_NO_BIT_DISPLACEMENT 0
#define FILLRAND_RAND_MAX 0x7FFFFFFF
#include "fillrand.inc.h"
/* ############################# */
#undef FILLRAND
#undef FILLRAND_UINTMAX_T
#undef FILLRAND_NO_BIT_DISPLACEMENT
#undef FILLRAND_RAND_MAX
#define FILLRAND fwd_fillrand64_31_nodisp
#define FILLRAND_UINTMAX_T uint64_t
#define FILLRAND_NO_BIT_DISPLACEMENT 1
#define FILLRAND_RAND_MAX 0x7FFFFFFF
#include "fillrand.inc.h"
/* ############################# */
#undef FILLRAND
#undef FILLRAND_UINTMAX_T
#undef FILLRAND_NO_BIT_DISPLACEMENT
#undef FILLRAND_RAND_MAX
#define FILLRAND fwd_fillrand64_15_disp
#define FILLRAND_UINTMAX_T uint64_t
#define FILLRAND_NO_BIT_DISPLACEMENT 0
#define FILLRAND_RAND_MAX 0x7FFF
#include "fillrand.inc.h"
/* ############################# */
#undef FILLRAND
#undef FILLRAND_UINTMAX_T
#undef FILLRAND_NO_BIT_DISPLACEMENT
#undef FILLRAND_RAND_MAX
#define FILLRAND fwd_fillrand64_15_nodisp
#define FILLRAND_UINTMAX_T uint64_t
#define FILLRAND_NO_BIT_DISPLACEMENT 1
#define FILLRAND_RAND_MAX 0x7FFF
#include "fillrand.inc.h"
void dumbfillrand(void *_buf, size_t sz) {
unsigned char *buf = (unsigned char *)_buf;
unsigned int r; /* for unsigned promotion */
unsigned int rbmask = 0;
for (;sz != 0;) {
sz--;
if (rbmask < 255) {
r = rand();
rbmask = RAND_MAX;
}
buf[sz] = r % 256;
r /= 256;
rbmask /= 256;
}
}
static int nrepeats;
static unsigned char testbuf[20*1024*1024];
static size_t nelems = sizeof(testbuf);
typedef void (*fillrand_t)(void *, size_t);
static int test(fillrand_t func) {
int i, j, ret = 0;
for (i = 0; i < nrepeats; i++) {
func(testbuf, nelems);
for (j = 0; j < sizeof(testbuf); j++) ret += testbuf[j];
}
return ret;
}
int main(int argc, char *argv[]) {
fillrand_t func;
if (argc != 3) {
fprintf(stderr, "usage: %s nrepeats funcname\n", argv[0]);
return 1;
}
if (0 == strcmp(argv[2],"dumbfillrand")) func = dumbfillrand;
else if (0 == strcmp(argv[2],"fillrand32_31_disp")) func = fillrand32_31_disp;
else if (0 == strcmp(argv[2],"fillrand32_31_nodisp")) func = fillrand32_31_nodisp;
else if (0 == strcmp(argv[2],"fillrand32_15_disp")) func = fillrand32_15_disp;
else if (0 == strcmp(argv[2],"fillrand32_15_nodisp")) func = fillrand32_15_nodisp;
else if (0 == strcmp(argv[2],"fillrand64_31_disp")) func = fillrand64_31_disp;
else if (0 == strcmp(argv[2],"fillrand64_31_nodisp")) func = fillrand64_31_nodisp;
else if (0 == strcmp(argv[2],"fillrand64_15_disp")) func = fillrand64_15_disp;
else if (0 == strcmp(argv[2],"fillrand64_15_nodisp")) func = fillrand64_15_nodisp;
else if (0 == strcmp(argv[2],"fwd_fillrand32_31_disp")) func = fwd_fillrand32_31_disp;
else if (0 == strcmp(argv[2],"fwd_fillrand32_31_nodisp")) func = fwd_fillrand32_31_nodisp;
else if (0 == strcmp(argv[2],"fwd_fillrand32_15_disp")) func = fwd_fillrand32_15_disp;
else if (0 == strcmp(argv[2],"fwd_fillrand32_15_nodisp")) func = fwd_fillrand32_15_nodisp;
else if (0 == strcmp(argv[2],"fwd_fillrand64_31_disp")) func = fwd_fillrand64_31_disp;
else if (0 == strcmp(argv[2],"fwd_fillrand64_31_nodisp")) func = fwd_fillrand64_31_nodisp;
else if (0 == strcmp(argv[2],"fwd_fillrand64_15_disp")) func = fwd_fillrand64_15_disp;
else if (0 == strcmp(argv[2],"fwd_fillrand64_15_nodisp")) func = fwd_fillrand64_15_nodisp;
else {
nelems /= 2;
if (0 == strcmp(argv[2],"wfillrand32_31_disp")) func = (fillrand_t)wfillrand32_31_disp;
else if (0 == strcmp(argv[2],"wfillrand32_31_nodisp")) func = (fillrand_t)wfillrand32_31_nodisp;
else if (0 == strcmp(argv[2],"wfillrand32_15_disp")) func = (fillrand_t)wfillrand32_15_disp;
else if (0 == strcmp(argv[2],"wfillrand32_15_nodisp")) func = (fillrand_t)wfillrand32_15_nodisp;
else if (0 == strcmp(argv[2],"wfillrand64_31_disp")) func = (fillrand_t)wfillrand64_31_disp;
else if (0 == strcmp(argv[2],"wfillrand64_31_nodisp")) func = (fillrand_t)wfillrand64_31_nodisp;
else if (0 == strcmp(argv[2],"wfillrand64_15_disp")) func = (fillrand_t)wfillrand64_15_disp;
else if (0 == strcmp(argv[2],"wfillrand64_15_nodisp")) func = (fillrand_t)wfillrand64_15_nodisp;
else if (0 == strcmp(argv[2],"wfwd_fillrand32_31_disp")) func = (fillrand_t)wfwd_fillrand32_31_disp;
else if (0 == strcmp(argv[2],"wfwd_fillrand32_31_nodisp")) func = (fillrand_t)wfwd_fillrand32_31_nodisp;
else if (0 == strcmp(argv[2],"wfwd_fillrand32_15_disp")) func = (fillrand_t)wfwd_fillrand32_15_disp;
else if (0 == strcmp(argv[2],"wfwd_fillrand32_15_nodisp")) func = (fillrand_t)wfwd_fillrand32_15_nodisp;
else if (0 == strcmp(argv[2],"wfwd_fillrand64_31_disp")) func = (fillrand_t)wfwd_fillrand64_31_disp;
else if (0 == strcmp(argv[2],"wfwd_fillrand64_31_nodisp")) func = (fillrand_t)wfwd_fillrand64_31_nodisp;
else if (0 == strcmp(argv[2],"wfwd_fillrand64_15_disp")) func = (fillrand_t)wfwd_fillrand64_15_disp;
else if (0 == strcmp(argv[2],"wfwd_fillrand64_15_nodisp")) func = (fillrand_t)wfwd_fillrand64_15_nodisp;
else {
fprintf(stderr, "unknown func %s\n", argv[2]);
return 1;
}
}
nrepeats = atoi(argv[1]);
return test(func);
}
Raw
test-fillrand.sh
#!/bin/sh
${CC:?} -o test-fillrand test-fillrand.c || exit 1
x() {
TIMEFORMAT="%U $*"
time ./test-fillrand 30 "$@"
}
LC_ALL=C
export LC_ALL
(
x dumbfillrand
x wfwd_fillrand64_31_disp
x fwd_fillrand64_31_disp
x fwd_fillrand64_31_nodisp
x wfwd_fillrand64_31_nodisp
x wfillrand64_31_disp
x fillrand64_31_disp
x fillrand64_31_nodisp
x wfillrand64_31_nodisp
if true; then
x wfwd_fillrand32_31_disp
x fwd_fillrand32_31_disp
x fwd_fillrand32_31_nodisp
x wfwd_fillrand32_31_nodisp
x wfillrand32_31_disp
x fillrand32_31_disp
x fillrand32_31_nodisp
x wfillrand32_31_nodisp
fi
if false; then
x fwd_fillrand32_15_disp
x fwd_fillrand32_15_nodisp
x fwd_fillrand64_15_disp
x fwd_fillrand64_15_nodisp
x wfwd_fillrand32_15_disp
x wfwd_fillrand32_15_nodisp
x wfwd_fillrand64_15_disp
x wfwd_fillrand64_15_nodisp
x fillrand32_15_disp
x fillrand32_15_nodisp
x fillrand64_15_disp
x fillrand64_15_nodisp
x wfillrand32_15_disp
x wfillrand32_15_nodisp
x wfillrand64_15_disp
x wfillrand64_15_nodisp
fi
) 2>&1 | tee test-fillrand.log
# LC_ALL=C sort -h test-fillrand.log
exit 0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment