Portable bitfield library for trace format (v2)
I'm keeping the same introduction as (v1), but I'm appending v2 of my portable bitfield library below. Comments are welcome,
Changelog since v1:
* Add missing brackets around "ptr" in the macros.
* Add more tests, including tests using randomly generated input values.
Thanks,
Mathieu
Quoted 104 lines · * Mathieu Desnoyers ([email protected]) wrote:
Hi,
After looking at gcc bitfields, I found out that they were really non-portable. One particularity of these bitfields is that the fields are put from high to low bits on big endian, and from low to high bits on little endian. So it is not enough to do the byte swap between architectures, one must also take care to reorder the fields.
Also, the fact that gcc requires bitfields to fit in the current unit adds much padding that is unwanted in a trace e.g.
struct { int a:3; int b:31; int c:3; };will be 12 bytes in size because "b" does not fit in the first "int" unit.
So I created a bitfield library with write and read primitives that can be made compatible with gcc bitfields by specifying the bit padding manually. The write-side writes bitfields in the native endianness, either with 1, 2, 4 or 8 bytes memory writes. The read side is architecture-agnostic, so it can read bitfields generated by either little or big endian architectures.
The userspace code is below. It includes a rather useful test-suite. The code generated is quite compact when the parameters are fixed. A x86-32 disassembly of
fct()below which contains the macro instance:unsigned int glob[1];
void fct(void)
{ bitfield_write(glob, 0x12345678, 12, 15); }Compared to this, we have the generated assembly from gcc 4.3.4 for:
struct d3 { unsigned int a:12; unsigned int b:15; };struct d3 glob;
void fct(void)
{ glob.b = 0x12345678; }glob.b =
0x12345678;On x86-32, the bitfield library looks like:
08048470 <fct>:
8048470: a1 70 ba 04 08 mov 0x804ba70,%eax 8048475: 55 push %ebp 8048476: 89 e5 mov %esp,%ebp 8048478: 5d pop %ebp 8048479: 25 ff 0f 00 f8 and $0xf8000fff,%eax 804847e: 0d 00 80 67 05 or $0x5678000,%eax 8048483: a3 70 ba 04 08 mov %eax,0x804ba70 8048488: c3 ret 8048489: 8d b4 26 00 00 00 00 lea 0x0(%esi,%eiz,1),%esiThe gcc bitfields generate:
080483d0<fct>:80483d0: a1 64 96 04 08 mov 0x8049664,%eax 80483d5: 55 push %ebp 80483d6: 89 e5 mov %esp,%ebp 80483d8: 5d pop %ebp 80483d9: 25 ff 0f 00 f8 and $0xf8000fff,%eax 80483de: 0d 00 80 67 05 or $0x5678000,%eax 80483e3: a3 64 96 04 08 mov %eax,0x8049664 80483e8: c3 ret 80483e9: 8d b4 26 00 00 00 00 lea 0x0(%esi,%eiz,1),%esiand on powerpc 32, the bitfield library:
10000520 <fct>:
10000520: 3d 20 10 01 lis r9,4097 10000524: 80 09 33 80 lwz r0,13184(r9) 10000528: 54 00 06 d6 rlwinm r0,r0,0,27,11 1000052c: 64 00 00 0a oris r0,r0,10 10000530: 60 00 cf 00 ori r0,r0,52992 10000534: 90 09 33 80 stw r0,13184(r9) 10000538: 4e 80 00 20 blr 1000053c: 60 00 00 00 nopAnd gcc bitfields:
10000490 <fct>:
10000490: 3d 20 10 01 lis r9,4097 10000494: 39 60 56 78 li r11,22136 10000498: 80 09 0a a4 lwz r0,2724(r9) 1000049c: 51 60 2b 34 rlwimi r0,r11,5,12,26 100004a0: 90 09 0a a4 stw r0,2724(r9) 100004a4: 4e 80 00 20 blr 100004a8: 60 00 00 00 nop 100004ac: 60 00 00 00 nop
Quoted 6 lines
Comments are welcome (code below).
Thanks,
Mathieu
/*
* Common Trace Format
*
* Bitfields implementation
*
* Copyright 2010 - Mathieu Desnoyers <[email protected]> *
* Dual LGPL v2.1/GPL v2 license.
*/
#include <endian.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#include <time.h>
#include <strings.h>
/* We can't shift a int from 32 bit, >> 32 on int is a no-op on x86 */ #define piecewise_rshift(v, shift) \
do { \
int sb = (shift) / (sizeof(v) * 8 - 1); \
int final = (shift) % (sizeof(v) * 8 - 1); \
\
for (; sb; sb--) \
(v) >>= sizeof(v) * 8 - 1; \
(v) >>= final; \
} while (0)/*
* Save integer to the bitfield, which starts at the "start" bit, has "len"
* bits.
* The inside of a bitfield is from high bits to low bits.
* Uses native endianness.
* For unsigned "v", pad MSB with 0 if bitfield is larger than v.
* For signed "v", sign-extend v if bitfield is larger than v.
*
* On little endian, bytes are placed from the less significant to the most
* significant. Also, consecutive bitfields are placed from lower bits to higher
* bits.
*
* On big endian, bytes are places from most significant to less significant.
* Also, consecutive bitfields are placed from higher to lower bits. */
#if (BYTE_ORDER == LITTLE_ENDIAN)
#define bitfield_write(ptr, _v, _start, _length) \
do { \
typeof(*(ptr)) mask, cmask; \
unsigned int start = (_start), length = (_length); \
typeof(_v) v = (_v); \
int start_unit, end_unit, this_unit; \
unsigned int end, cshift; /* cshift is "complement shift" */ \
unsigned int ts = sizeof(__typeof__(*(ptr))) * 8; /* type size */ \
\
if (!length) \
break; \
\
end = start + length; \
start_unit = start / ts; \
end_unit = (end + (ts - 1)) / ts; \
\
/* Trim v high bits */ \
if (length < sizeof(v) * 8) \
v &= ~(~0ULL << length); \
\
/* We can now append v with a simple "or", shift it piece-wise */ \
this_unit = start_unit; \
if (start_unit == end_unit - 1) { \
mask = ~((typeof(*(ptr))) ~0ULL << (start % ts)); \
mask |= (typeof(*(ptr))) ~0ULL << (end % ts ? : ts); \
cmask = (typeof(*(ptr))) v << (start % ts); \
(ptr)[this_unit] &= mask; \
(ptr)[this_unit] |= cmask; \
break; \
} \
if (start % ts) { \
cshift = start % ts; \
mask = ~((typeof(*(ptr))) ~0ULL << cshift); \
cmask = (typeof(*(ptr))) v << cshift; \
(ptr)[this_unit] &= mask; \
(ptr)[this_unit] |= cmask; \
if (ts - cshift >= sizeof(v) * 8) \
piecewise_rshift(v, ts - cshift); \
else \
v >>= ts - cshift; \
start += ts - cshift; \
this_unit++; \
} \
for (; this_unit < end_unit - 1; this_unit++) { \
(ptr)[this_unit] = (typeof(*(ptr))) v; \
if (ts >= sizeof(v) * 8) \
piecewise_rshift(v, ts); \
else \
v >>= ts; \
start += ts; \
} \
if (end % ts) { \
mask = (typeof(*(ptr))) ~0ULL << (end % ts); \
cmask = (typeof(*(ptr))) v; \
(ptr)[this_unit] &= mask; \
(ptr)[this_unit] |= cmask; \
} else \
(ptr)[this_unit] = (typeof(*(ptr))) v; \
} while (0)#else /* (BYTE_ORDER != LITTLE_ENDIAN) */
#define bitfield_write(ptr, _v, _start, _length) \
do { \
typeof(_v) v = (_v); \
unsigned int start = _start, length = _length; \
int start_unit, end_unit, this_unit; \
unsigned int end, cshift; /* cshift is "complement shift" */ \
typeof(*(ptr)) mask, cmask; \
unsigned int ts = sizeof(__typeof__(*(ptr))) * 8; /* type size */ \
\
if (!length) \
break; \
\
end = start + length; \
start_unit = start / ts; \
end_unit = (end + (ts - 1)) / ts; \
\
/* Trim v high bits */ \
if (length < sizeof(v) * 8) \
v &= ~(~0ULL << length); \
\
/* We can now append v with a simple "or", shift it piece-wise */ \
this_unit = end_unit - 1; \
if (start_unit == end_unit - 1) { \
mask = ~((typeof(*(ptr))) ~0ULL << ((ts - (end % ts)) % ts)); \
mask |= (typeof(*(ptr))) ~0ULL << (ts - (start % ts)); \
cmask = (typeof(*(ptr))) v << ((ts - (end % ts)) % ts); \
(ptr)[this_unit] &= mask; \
(ptr)[this_unit] |= cmask; \
break; \
} \
if (end % ts) { \
cshift = end % ts; \
mask = ~((typeof(*(ptr))) ~0ULL << (ts - cshift)); \
cmask = (typeof(*(ptr))) v << (ts - cshift); \
(ptr)[this_unit] &= mask; \
(ptr)[this_unit] |= cmask; \
if (cshift >= sizeof(v) * 8) \
piecewise_rshift(v, cshift); \
else \
v >>= cshift; \
end -= cshift; \
this_unit--; \
} \
for (; this_unit >= start_unit + 1; this_unit--) { \
(ptr)[this_unit] = (typeof(*(ptr))) v; \
if (ts >= sizeof(v) * 8) \
piecewise_rshift(v, ts); \
else \
v >>= ts; \
end -= ts; \
} \
if (start % ts) { \
mask = (typeof(*(ptr))) ~0ULL << (ts - (start % ts)); \
cmask = (typeof(*(ptr))) v; \
(ptr)[this_unit] &= mask; \
(ptr)[this_unit] |= cmask; \
} else \
(ptr)[this_unit] = (typeof(*(ptr))) v; \
} while (0)#endif
/*
* Read a bitfield byte-wise. This function is arch-agnostic. */
uint64_t bitfield_read_64(unsigned char *ptr,
unsigned int start, unsigned int len, int byte_order, int signedness)
{
int start_unit, end_unit, this_unit;
unsigned int end, cshift; /* cshift is "complement shift" */
unsigned int ts = sizeof(unsigned char) * 8;
unsigned char mask, cmask;
uint64_t v = 0;
if (!len)
return 0;
end = start + len;
start_unit = start / ts;
end_unit = (end + (ts - 1)) / ts;
/*
* We can now fill v piece-wise, from lower bits to upper bits.
* We read the bitfield in the opposite direction it was written.
*/
switch (byte_order) {
case LITTLE_ENDIAN:
this_unit = end_unit - 1;
if (signedness) {
if (ptr[this_unit] & (1U << ((end % ts ? : ts) - 1)))
v = ~0ULL;
}
if (start_unit == end_unit - 1) {
mask = (unsigned char) ~0ULL << (end % ts ? : ts);
mask |= ~((unsigned char) ~0ULL << (start % ts));
cmask = ptr[this_unit];
cmask &= ~mask;
cmask >>= (start % ts);
v <<= end - start;
v |= cmask;
break;
}
if (end % ts) {
cshift = (end % ts ? : ts);
mask = (unsigned char) ~0ULL << cshift;
cmask = ptr[this_unit];
cmask &= ~mask;
v <<= cshift;
v |= (uint64_t) cmask;
end -= cshift;
this_unit--;
}
for (; this_unit >= start_unit + 1; this_unit--) {
v <<= ts;
v |= (uint64_t) ptr[this_unit];
end -= ts;
}
if (start % ts) {
cmask = ptr[this_unit] >> (start % ts);
v <<= ts - (start % ts);
v |= (uint64_t) cmask;
} else {
v <<= ts;
v |= (uint64_t) ptr[this_unit];
}
break;
case BIG_ENDIAN:
this_unit = start_unit;
if (signedness) {
if (ptr[this_unit] & (1U << (ts - (start % ts) - 1)))
v = ~0ULL;
}
if (start_unit == end_unit - 1) {
mask = (unsigned char) ~0ULL << (ts - (start % ts));
mask |= ~((unsigned char) ~0ULL << ((ts - (end % ts)) % ts));
cmask = ptr[this_unit];
cmask &= ~mask;
cmask >>= (ts - (end % ts)) % ts;
v <<= end - start;
v |= (uint64_t) cmask;
break;
}
if (start % ts) {
mask = (unsigned char) ~0ULL << (ts - (start % ts));
cmask = ptr[this_unit];
cmask &= ~mask;
v <<= ts - (start % ts);
v |= (uint64_t) cmask;
start += ts - (start % ts);
this_unit++;
}
for (; this_unit < end_unit - 1; this_unit++) {
v <<= ts;
v |= (uint64_t) ptr[this_unit];
start += ts;
}
if (end % ts) {
cmask = ptr[this_unit];
cmask >>= (ts - (end % ts)) % ts;
v <<= (end % ts);
v |= (uint64_t) cmask;
} else {
v <<= ts;
v |= (uint64_t) ptr[this_unit];
}
break;
default:
assert(0);
}
return v;
}/*
* The code below is for testing the bitfield write/read functions. */
unsigned int glob;
/*
* This function is only declared to show the size of a bitfield write in
* objdump.
*/
void fct(void)
{
bitfield_write(&glob, 0x12345678, 12, 15);
}/* Test array size, in bytes */
#define TEST_LEN 128
#define NR_TESTS 10
unsigned int srcrand;
#if defined(__i386) || defined(__x86_64)
static inline int fls(int x)
{
int r;
asm("bsrl %1,%0\n\t"
"cmovzl %2,%0"
: "=&r" (r) : "rm" (x), "rm" (-1));
return r + 1;
}#elif defined(__PPC__)
static __inline__ int fls(unsigned int x)
{
int lz;
asm ("cntlzw %0,%1" : "=r" (lz) : "r" (x));
return 32 - lz;
}#else
static int fls(unsigned int x)
{
int r = 32;
if (!x)
return 0;
if (!(x & 0xFFFF0000U)) {
x <<= 16;
r -= 16;
}
if (!(x & 0xFF000000U)) {
x <<= 8;
r -= 8;
}
if (!(x & 0xF0000000U)) {
x <<= 4;
r -= 4;
}
if (!(x & 0xC0000000U)) {
x <<= 2;
r -= 2;
}
if (!(x & 0x80000000U)) {
x <<= 1;
r -= 1;
}
return r;
}#endif
static void print_byte_array(const unsigned char *c, unsigned long len)
{
unsigned long i;
for (i = 0; i < len; i++) {
printf("0x%X", c[i]);
if (i != len - 1)
printf(" ");
}
printf("\n");
}static void init_byte_array(unsigned char *c,
unsigned long len,
unsigned char val)
{
unsigned long i;
for (i = 0; i < len; i++)
c[i] = val;
}int run_test_unsigned(void)
{
unsigned int src, nrbits;
union {
unsigned char c[TEST_LEN];
unsigned short s[TEST_LEN/2];
unsigned int i[TEST_LEN/4];
unsigned long l[TEST_LEN/4];
unsigned long long ll[TEST_LEN/2];
} target;
uint64_t readval;
unsigned int s, l;
int err = 0;
printf("Running unsigned test with 0x%X\n", srcrand);
src = srcrand;
nrbits = fls(src);
for (s = 0; s < 8 * TEST_LEN; s++) {
for (l = nrbits; l < (8 * TEST_LEN) - s; l++) {
init_byte_array(target.c, TEST_LEN, 0xFF);
bitfield_write(target.c, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 0);
if (readval != src) {
printf("Error (bytewise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
init_byte_array(target.c, TEST_LEN, 0xFF);
bitfield_write(target.s, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 0);
if (readval != src) {
printf("Error (shortwise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
init_byte_array(target.c, TEST_LEN, 0xFF);
bitfield_write(target.i, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 0);
if (readval != src) {
printf("Error (intwise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
init_byte_array(target.c, TEST_LEN, 0xFF);
bitfield_write(target.l, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 0);
if (readval != src) {
printf("Error (longwise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
init_byte_array(target.c, TEST_LEN, 0xFF);
bitfield_write(target.ll, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 0);
if (readval != src) {
printf("Error (longlongwise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
}
}
if (!err)
printf("Success!\n");
else
printf("Failed!\n");
return err;
}int run_test_signed(void)
{
int src, nrbits;
union {
char c[TEST_LEN];
short s[TEST_LEN/2];
int i[TEST_LEN/4];
long l[TEST_LEN/4];
long long ll[TEST_LEN/8];
} target;
int64_t readval;
unsigned int s, l;
int err = 0;
printf("Running signed test with 0x%X\n", srcrand);
src = srcrand;
if (src & 0x80000000U)
nrbits = fls(~src) + 1; /* Find least significant bit conveying sign */
else
nrbits = fls(src) + 1; /* Keep sign at 0 */
for (s = 0; s < 8 * TEST_LEN; s++) {
for (l = nrbits; l < (8 * TEST_LEN) - s; l++) {
init_byte_array(target.c, TEST_LEN, 0x0);
bitfield_write(target.c, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 1);
if (readval != src) {
printf("Error (bytewise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
init_byte_array(target.c, TEST_LEN, 0x0);
bitfield_write(target.s, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 1);
if (readval != src) {
printf("Error (shortwise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
init_byte_array(target.c, TEST_LEN, 0x0);
bitfield_write(target.i, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 1);
if (readval != src) {
printf("Error (intwise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
init_byte_array(target.c, TEST_LEN, 0x0);
bitfield_write(target.l, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 1);
if (readval != src) {
printf("Error (longwise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
init_byte_array(target.c, TEST_LEN, 0x0);
bitfield_write(target.ll, src, s, l);
readval = bitfield_read_64(target.c, s, l, BYTE_ORDER, 1);
if (readval != src) {
printf("Error (longlongwise) src %lX read %llX shift %d len %d\n",
src, readval, s, l);
print_byte_array(target.c, TEST_LEN);
err = 1;
}
}
}
if (!err)
printf("Success!\n");
else
printf("Failed!\n");
return err;
}int run_test(void)
{
int err = 0;
int i;
srand(time(NULL));
srcrand = 0;
err |= run_test_unsigned();
srcrand = 0;
err |= run_test_signed();
srcrand = 1;
err |= run_test_unsigned();
srcrand = ~0U;
err |= run_test_unsigned();
srcrand = -1;
err |= run_test_signed();
srcrand = (int)0x80000000U;
err |= run_test_signed();
for (i = 0; i < NR_TESTS; i++) {
srcrand = rand();
err |= run_test_unsigned();
err |= run_test_signed();
}
return err;
}int main(int argc, char **argv)
{
unsigned long src;
unsigned int shift, len;
int ret;
union {
unsigned char c[8];
unsigned short s[4];
unsigned int i[2];
unsigned long l[2];
unsigned long long ll[1];
} target;
uint64_t readval;
if (argc > 1)
src = atoi(argv[1]);
else
src = 0x12345678;
if (argc > 2)
shift = atoi(argv[2]);
else
shift = 12;
if (argc > 3)
len = atoi(argv[3]);
else
len = 40;
target.i[0] = 0xFFFFFFFF;
target.i[1] = 0xFFFFFFFF;
bitfield_write(target.c, src, shift, len);
printf("bytewise\n");
print_byte_array(target.c, 8);
target.i[0] = 0xFFFFFFFF;
target.i[1] = 0xFFFFFFFF;
bitfield_write(target.s, src, shift, len);
printf("shortwise\n");
print_byte_array(target.c, 8);
target.i[0] = 0xFFFFFFFF;
target.i[1] = 0xFFFFFFFF;
bitfield_write(target.i, src, shift, len);
printf("intwise\n");
print_byte_array(target.c, 8);
target.i[0] = 0xFFFFFFFF;
target.i[1] = 0xFFFFFFFF;
bitfield_write(target.l, src, shift, len);
printf("longwise\n");
print_byte_array(target.c, 8);
target.i[0] = 0xFFFFFFFF;
target.i[1] = 0xFFFFFFFF;
bitfield_write(target.ll, src, shift, len);
printf("lluwise\n");
print_byte_array(target.c, 8);
readval = bitfield_read_64(target.c, shift, len, BYTE_ORDER, 0);
printf("read: %llX\n", readval);
ret = run_test();
return ret;
}Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com