Kitty：理解真值表——Projection, mask & endianness

A trick is a clever idea that can be used once, while a technique is a trick that can be used at least twice.
-Donald E. Knuth

无论是在ABC还是mockturtle中，对于bit manipulation经常会给读者造成困扰，这里就一些常用的bit level的technique以及其应用技巧做简述。这个文档不是一个Kitty manual的中文翻译，这样没有任何意义，这个文档从接口的角度阐明一些接口背后设计的原理以辅助读者对Kitty更加精准的使用。

projection和mask以及bit level manipulation

projection和mask的概念也不是Kitty中独有，早在ABC中就有比特级别的处理方式，虽然导致代码可读性降低，但是在空间使用率和速度上有着明显的优势。

关于elementary variable和function

在介绍这两个概念之前，首先要了解单一变量和函数的表示，通常情况下我们说到真值表的时候，喜欢习惯性地“枚举”所有可能出现的情况，但是我们要明确在布尔函数这个context下我们枚举的具体是什么。

我们课堂上了解过对于一个$n$输入的函数，我们有$2^n$种赋值的可能性，在每种赋值的可能性下，又会存在2种不同的函数返回值（0/1），所以当我们提到一个complete boolean function的时候，一共就会出现$2^{2^n}$种函数。

所以对于一个2输入的逻辑结构，有4种组合，有16种可以表示的函数。

Context的概念在这里很重要，就是在有多少变量的context下我需要这样长度的表示形式？为什么对于一个$f = x$的表示，在仅有变量${x, y}$的context下和仅有变量${x, y ,z}$的context下表示不同，这里需要明确清楚。

projection

projection这里kitty使用uint64_t的类型，也就是64bit的unsigned int，这里最多处理6输入的complete boolean function，请注意，根据前面一节的内容，这个uint64_t中包含的是所有的变量组合对应的结果的集合，也就是TT中值的那一列。

这里的每一行都可以用来做bit级别的取样，同样的，整体上看，它们就是6输入的complete boolean function的elementary variable的表示。

static constexpr uint64_t projections[] = {
  UINT64_C( 0xaaaaaaaaaaaaaaaa ),
  UINT64_C( 0xcccccccccccccccc ),
  UINT64_C( 0xf0f0f0f0f0f0f0f0 ),
  UINT64_C( 0xff00ff00ff00ff00 ),
  UINT64_C( 0xffff0000ffff0000 ),
  UINT64_C( 0xffffffff00000000 ) };

我们先把它展开，以第一个

UINT64_C( 0xaaaaaaaaaaaaaaaa )

为例：

1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010

以此类推。这样就和上一节的内容完全对应上了。

另外，对于：

static constexpr uint64_t projections_neg[] = {
  UINT64_C( 0x5555555555555555 ),
  UINT64_C( 0x3333333333333333 ),
  UINT64_C( 0x0f0f0f0f0f0f0f0f ),
  UINT64_C( 0x00ff00ff00ff00ff ),
  UINT64_C( 0x0000ffff0000ffff ),
  UINT64_C( 0x00000000ffffffff ) };

其实我们对比projections和projections_neg就能够发现，相同index下这里的每一个比特的数字都是互补的，所以上下两者取到的是互补的bit位:
以

UINT64_C( 0x5555555555555555 ),

为例：

0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101 0101

与上述projection例子形成反转对比。

mask

以Kitty中的create_nth_var5 test为例：

const auto mask = 0xffffffff;

和

EXPECT_EQ( tt_s._bits, detail::projections[i] & mask );

的指定，会使得结果为一个有效位数只有后32bit的unsigned int，后续的计算只保留了5个variable所对应的范围，而非6个。注意这里利用了“projection”，实际上也是利用真值表来表示了elementary variable，实际上projection的应用范围要比它表示elementary variable要广很多，这里只是它的一个巧用的场景罢了。请时刻谨记，projection，字如其名，就是保留1的bit位置，抹去0的bit位置的信息，在不同的场景下有不同的功能。

还有一个比较容易看到的mask的应用场景，就是计算一个unsigned int的二进制表示中1的数量，Kitty中有很多的使用场景，这里以count_ones为例：

template<uint32_t NumVars>
inline uint64_t count_ones( const static_truth_table<NumVars, true>& tt )
{
return __builtin_popcount( tt._bits & 0xffffffff ) + __builtin_popcount( tt._bits >> 32 );
}

这里__builtin_popcount的参数是个32位的unsigned int，而在这个static_truth_table中的bits是64位，所以一开始利用32位的全1的mask做bit level的与操作，只取后面32位，构成一个新的unsigned int，而后向右shift 32位形成一个新的32bit的unsigned int，计算原来64 bit的左半部分的1的数量，相加得到总共的数量。可以牢记这个__builtin_popcount库函数的使用场景，如果自己构建bit level manipulation的算法可以直接拿来使用。

Big-endian && small-endian

关于如何存放所需要的bit，The Art of Programming书中给出了比较精简的定义，就是第一个元素（first item(Byte)）是放在最大的位置还是最小的位置，如果放在最大的位置，就是Big-endian，如果放在最小的位置就是Small-endian。

我们上述对elementary variable的表示明显是Big-endian，使用Big-endian也会使数据其在数学表示上更加直观易懂，与“进制”数的表示和计算更加贴合。

在罗列真值表的过程中，我们通常是从小到达进行罗列，自上而下罗列，所对应的函数的表示如果使用Big-endian的话需要从下往上，从左到右依次写在纸上，也就是第一个写出来的most significant byte。

上面的描述如果让你觉得抽象，那么我们以一个Kitty中constructors.cpp的例子来看：

TEST( ConstructorsTest, create_nth_var5 )
{
static_truth_table<5> tt_s;
dynamic_truth_table tt_d( 5 );

const auto mask = 0xffffffff;

for ( auto i = 0; i <= 4; ++i )
{
  create_nth_var( tt_s, i );
  EXPECT_EQ( tt_s._bits, detail::projections[i] & mask );
  create_nth_var( tt_d, i );
  EXPECT_EQ( tt_s._bits, tt_d._bits[0] );
}
}

我们可以看到实际上此处利用了上面的projection来作为elementary varible的对比项，此处之前"关于elementary variable和function"部分也描述过，这里所有的1靠近左侧，所有的0靠近右侧，实际上在字面上就是一个Big-endian的表达形式。

这里还有一个比较明显的例子，大家可以参考

TEST_F( BitOperationsTest, find_first_bit )

和

TEST_F( BitOperationsTest, find_last_bit )

这里的两个函数分别是找到最小的1的bit所在的index和最大的1的bit所在的index我们结合之前elementary variable的例子可以看到：

EXPECT_EQ( find_first_one_bit( nth<6>( 0 ) ), 1 );

是1010...1010的从右至左的第一个1的index是1，而

EXPECT_EQ( find_last_one_bit( nth<6>( 0 ) ), 63 );

是1010...1010的从左至右的第一个1的index是63。
这里还需要注意的是，我们在字面byte level的index和数字bit的index上是不同的，通常情况下我们看到的写在纸上的，称最左侧的为最小的index，而在上述的例子中，显然在讨论bit level的时候是完全相反的，最左侧的是最大的index而最右侧的是最小的index，所以接口的名称为find_first_one_bit或者find_last_one_bit的时候是bit level的index。

请不要小瞧这个简单的函数（接口），在日后的学习中，好比NPN equivalence class中每一项的representative function都是由该class的最小truth table的index来标注的，将来会有更多有趣的场景。