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 * 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),%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 <[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; } -- Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com _______________________________________________ ltt-dev mailing list [email protected] http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev
