Messages in this thread | | | Date | Sat, 18 Sep 2010 01:42:29 -0400 | From | Mathieu Desnoyers <> | Subject | [RFC] Portable bitfields for trace format |
| |
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),%esi
The 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),%esi
and 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 nop
And 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
Comments are welcome (code below).
Thanks,
Mathieu
/* * Common Trace Format * * Bitfields implementation * * Copyright 2010 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com> * * Dual LGPL v2.1/GPL v2 license. */
#include <endian.h> #include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <assert.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; }
unsigned int glob[1];
void fct(void) { bitfield_write(glob, 0x12345678, 12, 15); }
int run_test_unsigned(void) { unsigned long src; 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; unsigned int s, l; int err = 0;
printf("Running unsigned test\n");
src = 1;
for (s = 0; s < 64; s++) { for (l = 1; l < 64 - s; l++) { target.i[0] = 0xFFFFFFFF; target.i[1] = 0xFFFFFFFF; 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); printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n", target.c[0], target.c[1], target.c[2], target.c[3], target.c[4], target.c[5], target.c[6], target.c[7]); err = 1; }
target.i[0] = 0xFFFFFFFF; target.i[1] = 0xFFFFFFFF; 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); printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n", target.c[0], target.c[1], target.c[2], target.c[3], target.c[4], target.c[5], target.c[6], target.c[7]); err = 1; }
target.i[0] = 0xFFFFFFFF; target.i[1] = 0xFFFFFFFF; 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); printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n", target.c[0], target.c[1], target.c[2], target.c[3], target.c[4], target.c[5], target.c[6], target.c[7]); err = 1; }
target.i[0] = 0xFFFFFFFF; target.i[1] = 0xFFFFFFFF; 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); printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n", target.c[0], target.c[1], target.c[2], target.c[3], target.c[4], target.c[5], target.c[6], target.c[7]); err = 1; }
target.i[0] = 0xFFFFFFFF; target.i[1] = 0xFFFFFFFF; 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); printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n", target.c[0], target.c[1], target.c[2], target.c[3], target.c[4], target.c[5], target.c[6], target.c[7]); err = 1; } } } if (!err) printf("Success!\n"); else printf("Failed!\n"); return err; }
int run_test_signed(void) { long src; union { char c[8]; short s[4]; int i[2]; long l[2]; long long ll[1]; } target; int64_t readval; unsigned int s, l; int err = 0;
printf("Running signed test\n");
src = 1;
for (s = 0; s < 64; s++) { for (l = 1; l < 64 - s; l++) { target.i[0] = 0x00000000; target.i[1] = 0x00000000; 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); printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n", target.c[0], target.c[1], target.c[2], target.c[3], target.c[4], target.c[5], target.c[6], target.c[7]); err = 1; }
target.i[0] = 0x00000000; target.i[1] = 0x00000000; 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); printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n", target.c[0], target.c[1], target.c[2], target.c[3], target.c[4], target.c[5], target.c[6], target.c[7]); err = 1; }
target.i[0] = 0x00000000; target.i[1] = 0x00000000; 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); printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n", target.c[0], target.c[1], target.c[2], target.c[3], target.c[4], target.c[5], target.c[6], target.c[7]); err = 1; }
target.i[0] = 0x00000000; target.i[1] = 0x00000000; 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); printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n", target.c[0], target.c[1], target.c[2], target.c[3], target.c[4], target.c[5], target.c[6], target.c[7]); err = 1; }
target.i[0] = 0x00000000; target.i[1] = 0x00000000; 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); printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n", target.c[0], target.c[1], target.c[2], target.c[3], target.c[4], target.c[5], target.c[6], target.c[7]); err = 1; } } } if (!err) printf("Success!\n"); else printf("Failed!\n"); return err; }
int run_test(void) { int err = 0;
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"); printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n", target.c[0], target.c[1], target.c[2], target.c[3], target.c[4], target.c[5], target.c[6], target.c[7]);
target.i[0] = 0xFFFFFFFF; target.i[1] = 0xFFFFFFFF; bitfield_write(target.s, src, shift, len); printf("shortwise\n"); printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n", target.c[0], target.c[1], target.c[2], target.c[3], target.c[4], target.c[5], target.c[6], target.c[7]);
target.i[0] = 0xFFFFFFFF; target.i[1] = 0xFFFFFFFF; bitfield_write(target.i, src, shift, len); printf("intwise\n"); printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n", target.c[0], target.c[1], target.c[2], target.c[3], target.c[4], target.c[5], target.c[6], target.c[7]);
target.i[0] = 0xFFFFFFFF; target.i[1] = 0xFFFFFFFF; bitfield_write(target.l, src, shift, len); printf("longwise\n"); printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n", target.c[0], target.c[1], target.c[2], target.c[3], target.c[4], target.c[5], target.c[6], target.c[7]);
target.i[0] = 0xFFFFFFFF; target.i[1] = 0xFFFFFFFF; bitfield_write(target.ll, src, shift, len); printf("lluwise\n"); printf("0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X 0x%X\n", target.c[0], target.c[1], target.c[2], target.c[3], target.c[4], target.c[5], target.c[6], target.c[7]);
readval = bitfield_read_64(target.c, shift, len, BYTE_ORDER, 0); printf("read: %llX\n", readval);
ret = run_test();
return ret; }
-- Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
| |