C++中的位域以及实现一个抽象位域类

March 17, 2017 at 11:52 am

这里说的位域(bit-field)是C/C++语言中的一个概念,它用来为struct/class/union中的成员指定特定的以位为单位的尺寸。之所以要写这个,是因为今天看到了一个位域类的实现,这个类似乎能更方便的使用位域,那就看看它到底如何实现的,顺道把位域复习一遍。说实话在实际项目中没有写过位域,一方面除了C/C++语言,一般的语言都没有这个特性;另一方面,位域在一般的项目中使用较少,仅会出现在偏底层的一些代码中。似乎偶尔在面试中会有关于位域的题目,有段时间学习过一下,不过现在也基本上忘光了,博客也好久没更了,暂时就先补上这一篇。

本文主要有如下几个内容:
1. 位域的基本概念
2. 位域内存占用和pack
3. 实现一个抽象位域类

位域的基本概念

位域通常用于代替一些位操作,典型的使用场景比如占1至2个比特的标记位,如果直接使用bool来定义这个标记位,将会浪费内存空间,32个只有true/false的标记位使用位域只需要4字节,而如果全部定义为bool则需要32个字节;一个典型的方法是将这32个标记位用一个32位的整数表示,每个标记位通过对这个整数的位操作来代替,从功能上来说,位域只是对于代码编写者(阅读者)而言比位操作更加直观一点的方式,通常来讲CPU并没有对特定位进行操作的指令,所以位域操作最终仍会被编译器转化为底层的位操作指令。

如果不需要考虑到内存空间的浪费,或者已经习惯对数字的位操作,那么位域并不是必须的。

下面给出一个最简单的位域的例子(例子引用自 http://en.cppreference.com/w/cpp/language/bit_field):

#include <iostream>
struct S {
 // three-bit unsigned field,
 // allowed values are 0...7
 unsigned int b : 3;
};
int main()
{
    S s = {7};
    ++s.b; // unsigned overflow (guaranteed wrap-around)
    std::cout << s.b << '\n'; // output: 0
}

结构体S有一个占有3比特的无符号整型b,它的取值范围应为[0,7],代码中已经注释,如果发生overflow,那么b的值会wrap-around到0。struct/class/union中的整型成员都可以进行位域的声明。

这里我们的S只有一个3比特的成员,那么S所占用的内存空间是多少呢?3比特?接下来我们讨论关于位域相关的内存占用相关的内容。

位域内存占用和pack

我们知道sizeof操作符是以字节为单位的,所以C/C++语言并不允许对位域成员进行sizeof操作,这样的操作在编译期就会报错。类似的,内存地址也是至少按照字节对齐的,我们无法对位域成员进行取地址操作。不过我们可以通过对整个结构体或者结构体中的非位域成员进行sizeof来观测位域的内存占用。下面是一个简单的测试代码:

#include <stdio.h>
#include <stdint.h>

struct S {
    uint8_t b : 3;
    uint8_t c : 4;
    uint8_t d : 1;
};

int main() {
    S a;
    printf("%lu\n", sizeof(a)); // output on ubuntu-64, GCC 4.9: 1
    return 0;
}

结果输出了1,说明这三个位域成员被打包到一个uint8_t的空间中了,这一现象就称为pack,通常来讲,如果可以,连续的位域都会发生pack现象(不连续的位域之间必定不会发生pack)。那么什么情况不可以呢?我们进行进一步的测试:

#include <stdio.h>
#include <stdint.h>

struct S {
    uint8_t b : 3;
    uint8_t c : 4;
    uint8_t d : 2;
    uint8_t e : 7;
};

struct T {
    uint16_t b : 3;
    uint16_t c : 4;
    uint16_t d : 2;
    uint16_t e : 7;
};

int main() {
    S a;
    T b;
    printf("%lu %lu\n", sizeof(a), sizeof(b)); // output on ubuntu-64, GCC 4.9: 3 2
    return 0;
}

可以看到,对于两个类S和T,它们的位域成员除了类型不同以外,所占的位是相同的,但是它们最终的结果却不同。这涉及到pack的存储单元(storage unit)问题,对于连续的位域,pack的前提是不能一个位域成员不能跨过存储单元。前面已经提到过,位域操作最终要转化为位操作的CPU指令,这些指令都有对应的存储单元,假设最大的位操作指令的存储单元是8字节,那么如果一个位域横跨两个8字节区域(如下图所示),编译器至少要生成三条指令来对它进行操作(两次取值一次合并),代价是相当大的,所以位域并不支持跨存储单元的pack。
20170316_1
C99标准声明会尽量将连续位域pack以使结构紧凑,但并没有定义存储单元如何选取。在上例中,显然位域的类型决定了存储单元,结构体S中的存储单元是1个字节,所以跨字节的d必须放到一个新的单元的开始,而这将导致e也跨字节,同样需要放到一个新的单元中,所以结果为3:
20170316_2
而结构体T中的存储单元是2个字节,所以并不存在这个问题。再次说明,存储单元如何确定是平台和编译器相关的,”位域变量的类型决定存储单元“并不是一个通用的标准,位域的类型在标准中只是明确规定用来确定位域成员的符号类型(有符号还是无符号)。

这里仍然有一个潜在的问题。回看上图,图中的b和c属于同一个字节,d属于同一个字节,e属于同一个字节,那么在字节内部,这些位域元素到底是从低位开始使用的,还是从高位开始使用的呢?这个顺序标准也没有规定,我们也取不到这些位域元素的地址,以GCC编译器为例,对于大端机器,先从高位开始存储,也就是上图中的左边是一个字节中的MSB(最高位);而对于小端机器,先从低位开始存储,也就是上图中的左边是一个字节中的LSB(最低位)。要注意的是,虽然目前GCC是这样实现的,但这并不意味着这是大端和小端的一个区别,这仅仅是编译器的一个具体实现,和大端小端本质上没有关系,大端机器和小端机器描述的是字节间的顺序,而不涉及字节内部的顺序。

实现一个抽象位域类

位域本身的特殊性和位域的pack机制的平台相关性,包括大端和小端的问题,使得位域的使用较为不便,我们来实现一个抽象的位域类,它的存储不依赖与平台以及大小端,并可以加入相应的安全检查机制。这个类的代码来自Tony Wasserka,遵循GPLv2及以后的协议。据代码里的注释,这个类最终编译生成的结果和普通位域是等效的。
我们首先考虑用什么类型来存储位域成员。通常来讲,我们定义一个模板参数来表示这个位域成员的类型即可,这样就和位域成员定义时的类型声明保持一致。但是存在一个相对特殊的情况,即位域成员的类型可能是一个枚举类型,而枚举类型并不方便我们进行位操作,所以如果类型是枚举类型,我们需要将其转化为底层的存储类型。
一个简单的设想是这样的:

template<typename T>
class BitField {
    typedef typename std::conditional < std::is_enum<T>::value, typename std::underlying_type<T>::type, T>::type StorageType;
};

但是上述代码在存在非enum类型的位域成员时是无法编译通过的,因为上述代码总要生成underlying_type::type,而这个type在非enum类型时是不存在的,underlying_type对SFINAE并不是很友好。于是我们只能直接使用underlying_type自身,将type移到最外层,这又使得T必须有type成员,好在我们可以通过std::enable_if的wrap来简单实现这一点,于是底层的存储类型就变成了这样:

template<typename T>
class BitField {
    // StorageType is T for non-enum types and the underlying type of T if
    // T is an enumeration. Note that T is wrapped within an enable_if in the
    // former case to workaround compile errors which arise when using
    // std::underlying_type<T>::type directly.
    typedef typename std::conditional < std::is_enum<T>::value,
            std::underlying_type<T>,
            std::enable_if < true, T >> ::type::type StorageType;

    // Unsigned version of StorageType
    typedef typename std::make_unsigned<StorageType>::type StorageTypeU;

    StorageType storage;
};

接下来要考虑如何进行pack,也就是如何决定存储单元的问题。这里的设计是将存储单元的设计放到类的外部去,在外部定义一个用户需要的存储单元大小的变量,而我们的位域类对象和存储单元以union的形式并存,示例如下:

/* Sample usage:
 *
 * union SomeRegister
 * {
 *     u32 hex;
 *
 *     BitField<0,7,u32> first_seven_bits;     // unsigned
 *     BitField<7,8,u32> next_eight_bits;      // unsigned
 *     BitField<3,15,s32> some_signed_fields;  // signed
 * };
 *
 * This is equivalent to the little-endian specific code:
 *
 * union SomeRegister
 * {
 *     u32 hex;
 *
 *     struct
 *     {
 *         u32 first_seven_bits : 7;
 *         u32 next_eight_bits : 8;
 *     };
 *     struct
 *     {
 *         u32 : 3; // padding
 *         s32 some_signed_fields : 15;
 *     };
 */ };

通过这种显式的存储单元的形式避免了pack可能造成的一些问题。因此我们的类模板除了包含类型参数以外,还需要包含位域成员的位数,以及位域成员在存储单元中的偏移(pragma pack用来避免一些对齐机制可能造成的问题):

#pragma pack(1)
template<std::size_t position, std::size_t bits, typename T>
class BitField {
    // StorageType is T for non-enum types and the underlying type of T if
    // T is an enumeration. Note that T is wrapped within an enable_if in the
    // former case to workaround compile errors which arise when using
    // std::underlying_type<T>::type directly.
    typedef typename std::conditional < std::is_enum<T>::value,
            std::underlying_type<T>,
            std::enable_if < true, T >> ::type::type StorageType;

    // Unsigned version of StorageType
    typedef typename std::make_unsigned<StorageType>::type StorageTypeU;

    StorageType storage;

    // ...
};
#pragma pack()

其中position表示的是这个BitField相对于存储单元的LSB的偏移。我们可以通过简单的位操作定位到位域在存储单元中的位置(及掩码):

    FORCE_INLINE StorageType GetMask() const {
        return (((StorageTypeU)~0) >> (8 * sizeof(T)-bits)) << position;
    }

FORCE_INLINE不同的平台都有对应的方式实现,这里就不多说了,可以参考C/C++/gcc不常用语法和用法合集

接下来要实现具体的赋值和取值,需要用到位移操作,需要注意的是,这个BitField类是支持有符号整型的(C语言自带的bit-field本身当然也支持),但是C语言对于负数的左移、位移是没有规定的:其中负数的左移认为是undefined behavior,而右移则是implementation-defined,下面的实现建立于大多数编译器目前对于有符号整数的位移的实现这一基础之上,规则为:

1. 对于左移来说,总是将所有位向左移若干位,多出的位直接舍去,低位补0。
2. 对于右移来说,如果是无符号整型或者有符号的非负数,向右移若干位,多出的位直接舍去,高位补0;对于有符号的负数,高位补1。

如前所述,这一规则并非C语言标准,所以使用BitField时,如果使用有符号整数尤其是可能有负数时,需要注意可移植性的问题。不过目前对于主流编译器来说上述两个规则都是成立的。

下面具体介绍实现。

赋值非常方便,只需要把存储单元的相应位清空再填入相应内容即可,即使是负数,只要它可以存储在bits位里,那么它的更高位总是为1,可以直接舍去:

    FORCE_INLINE void Assign(const T& value) {
        storage = (storage & ~GetMask()) | (((StorageType)value << position) & GetMask());
    }

取值的话要稍微复杂一些,对于非负数来说非常简单,只需要使用掩码取到相应的值,再右移position位到最低位即可。
但对于负数来说,取出来的值高位要补1。对于这种情况,我们利用上述的第2条规则,我们首先将这个存储单元进行左移,使位域部分到最高位,这样符号位必定为1,而移动的长度显然等于存储单元总大小减去bits和position。整个存储单元就变成了一个负数,此时再右移”总大小减去bits“个单位,整体上达成右移position个单位的效果,但是高位此时已经补上了1:

    FORCE_INLINE T Value() const {
        if (std::numeric_limits<T>::is_signed)
        {
            std::size_t shift = 8 * sizeof(T)-bits;
            return (T)((storage << (shift - position)) >> shift);
        }
        else
        {
            return (T)((storage & GetMask()) >> position);
        }
    }

至此核心工作就做完了,我们首先可以加上一些安全检查:

    static_assert(bits + position <= 8 * sizeof(T), "Bitfield out of range");

    // And, you know, just in case people specify something stupid like bits=position=0x80000000
    static_assert(position < 8 * sizeof(T), "Invalid position");
    static_assert(bits <= 8 * sizeof(T), "Invalid number of bits");
    static_assert(bits > 0, "Invalid number of bits");
    static_assert(std::is_pod<T>::value, "Invalid base type");

接着我们完成赋值的相关工作,主要如下:

private:
    // We hide the copy assigment operator here, because the default copy
    // assignment would copy the full storage value, rather than just the bits
    // relevant to this particular bit field.
    // We don't delete it because we want BitField to be trivially copyable.
    BitField& operator=(const BitField&) = default;

public:
    // This constructor and assignment operator might be considered ambiguous:
    // Would they initialize the storage or just the bitfield?
    // Hence, delete them. Use the Assign method to set bitfield values!
    BitField(T val) = delete;
    BitField& operator=(T val) = delete;

    // Force default constructor to be created
    // so that we can use this within unions
    BitField() = default;

    FORCE_INLINE operator T() const {
        return Value();
    }

T()没有什么过多需要介绍的,即可以将位域成员当作普通的T类型成员使用。这里我们删除了传值的构造函数和赋值函数,因为这两个函数的含义存在二义性,不知道是对位域赋值还是对整个存储单元赋值。这里将拷贝赋值函数设置为private而不是delete,希望在保证用户不使用的前提下,BitField仍然可以作为trivially copyable的一个类,这样使用位域的整个Union仍能保持trivially copyable。

至此我们完成了一个位域类的设计,如前所述,编译器最终的实现也是将位域转化成类似的位操作。