Michael.W基于Foundry精读Openzeppelin第17期——BitMaps.sol

0. 版本

[openzeppelin]：v4.8.3，[forge-std]：v1.5.6

0.1 BitMaps.sol

Github: https://github.com/OpenZeppelin/openzeppelin-contracts/blob/v4.8.3/contracts/utils/structs/BitMaps.sol

BitMaps库开发了一种存储更紧凑且高效的mapping(uint256=>bool)。传统的mapping(uint256=>bool)中一个slot只能存储一个键值对的bool值信息，而改用了BitMaps.BitMap数据结构后，一个slot理论上最多可以存256个键值对的bool值信息。

1. 目标合约

封装BitMaps library成为一个可调用合约：

Github: https://github.com/RevelationOfTuring/foundry-openzeppelin-contracts/blob/master/src/utils/structs/MockBitMaps.sol

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.0;

import "openzeppelin-contracts/contracts/utils/structs/BitMaps.sol";

contract MockBitMaps {
    using BitMaps for BitMaps.BitMap;

    BitMaps.BitMap _bitMap;

    function get(uint index) external view returns (bool) {
        return _bitMap.get(index);
    }

    function setTo(
        uint index,
        bool value
    ) external {
        _bitMap.setTo(index, value);
    }

    function set(uint index) external {
        _bitMap.set(index);
    }

    function unset(uint index) external {
        _bitMap.unset(index);
    }
}

全部foundry测试合约：

Github: https://github.com/RevelationOfTuring/foundry-openzeppelin-contracts/blob/master/test/utils/structs/BitMaps.t.sol

2. 代码精读

2.1 结构体BitMap

定义BitMap结构体，内部包含一个key和value都是uint256的mapping。

    struct BitMap {
        mapping(uint256 => uint256) _data;
    }

该mapping的解析规则：

BitMap._data[bucket]的值为一个uint256。其值表示key的高248位为bucket的所有key对应的bool值的总记录。

BitMap._data[bucket]的值的右起第x位表示：右起高248位为bucket、右起低8位数值为x的key（即key=(bucket<<8)+x）对应的bool值。如果第x位为1，表示该key对应的bool值为true；如果第x位为0，表示该key对应的bool值为false。

综上，用一个slot理论上可以记录256个key对应的bool值。这比直接定义一个mapping(uint=>bool)的slot使用率更高。

2.2 get(BitMap storage bitmap, uint256 index)

返回key为index对应bool值。

    function get(BitMap storage bitmap, uint256 index) internal view returns (bool) {
        // index为应用层的key。将其右移8位得到bucket，即bucket为index的高256-8=248位
        uint256 bucket = index >> 8;
        // mask为记录bool值的位记录过滤器
        // index & 0xff：过滤出index的低8位，范围[0,255]。设其值为x，mask为1左移x位。
        uint256 mask = 1 << (index & 0xff);
        // 以bucket为key，从_data中取到对应值。并利用mask取出右起第mask位上的数值。如果为1，则表示true。否则表示false
        return bitmap._data[bucket] & mask != 0;
    }

2.3 set(BitMap storage bitmap, uint256 index) && unset(BitMap storage bitmap, uint256 index)

• set(BitMap storage bitmap, uint256 index)：在内部数据结构中记录key为index的值，即在mapping(uint=>bool)中，将key为index的值设置为true；
• unset(BitMap storage bitmap, uint256 index)：在内部数据结构中清除key为index的值，即在mapping(uint=>bool)中，将key为index的值设置为false。

    function set(BitMap storage bitmap, uint256 index) internal {
        // index为应用层的key。将其右移8位得到bucket，即bucket为index的高256-8=248位
        uint256 bucket = index >> 8;
        // mask为记录bool值的位记录过滤器
        // index & 0xff：过滤出index的低8位，范围[0,255]。设其值为x，mask为1左移x位。
        uint256 mask = 1 << (index & 0xff);
        // 将bitmap._data[bucket]值的右起第mask位写为1
        bitmap._data[bucket] |= mask;
    }

    function unset(BitMap storage bitmap, uint256 index) internal {
        // index为应用层的key。将其右移8位得到bucket，即bucket为index的高256-8=248位
        uint256 bucket = index >> 8;
        // mask为记录bool值的位记录过滤器
        // index & 0xff：过滤出index的低8位，范围[0,255]。设其值为x，mask为1左移x位。
        uint256 mask = 1 << (index & 0xff);
        // 将bitmap._data[bucket]值的右起第mask位清为0
        bitmap._data[bucket] &= ~mask;
    }

foundry代码验证

contract BitMapsTest is Test {
    MockBitMaps mb = new MockBitMaps();

    function test_SetAndUnset() external {
        uint[3] memory keys = [1, 1024, type(uint).max];

        for (uint i = 0; i < 3; ++i) {
            uint key = keys[i];
            // before set
            assertFalse(mb.get(key));
            // set
            mb.set(key);
            // after set
            assertTrue(mb.get(key));
            // unset
            mb.unset(key);
            // after unset
            assertFalse(mb.get(key));
        }

        // test consecutive keys operations
        for (uint16 i; i < type(uint16).max; ++i) {
            assertFalse(mb.get(i));
        }

        for (uint16 i; i < type(uint16).max; ++i) {
            mb.set(i);
        }

        for (uint16 i; i < type(uint16).max; ++i) {
            assertTrue(mb.get(i));
        }

        for (uint16 i; i < type(uint16).max; ++i) {
            mb.unset(i);
        }

        for (uint16 i; i < type(uint16).max; ++i) {
            assertFalse(mb.get(i));
        }
    }
}

2.4 setTo(BitMap storage bitmap, uint256 index, bool value)

将key为index的对应值设置为value（bool值）。

是对set(BitMap storage bitmap, uint256 index)和unset(BitMap storage bitmap, uint256 index)的一层封装。

    function setTo(
        BitMap storage bitmap,
        uint256 index,
        bool value
    ) internal {
        if (value) {
            // 如果要设置的value值为true，调用set()函数
            set(bitmap, index);
        } else {
            // 如果要设置的value值为false，调用unset()函数
            unset(bitmap, index);
        }
    }

foundry代码验证

contract BitMapsTest is Test {
    MockBitMaps mb = new MockBitMaps();

    function test_SetTo() external {
        for (uint16 i; i < type(uint16).max; ++i) {
            if (i % 2 == 0) {
                mb.setTo(i, true);
            } else {
                mb.setTo(i, false);
            }
        }

        // check
        for (uint16 i; i < type(uint16).max; ++i) {
            if (i % 2 == 0) {
                assertTrue(mb.get(i));
            } else {
                assertFalse(mb.get(i));
            }
        }
    }
}

ps:\ 本人热爱图灵，热爱中本聪，热爱V神。 以下是我个人的公众号，如果有技术问题可以关注我的公众号来跟我交流。 同时我也会在这个公众号上每周更新我的原创文章，喜欢的小伙伴或者老伙计可以支持一下！ 如果需要转发，麻烦注明作者。十分感谢！

公众号名称：后现代泼痞浪漫主义奠基人