27个版本 (2个稳定版)
1.0.1 | 2022年7月10日 |
---|---|
1.0.0 | 2022年1月11日 |
1.0.0-rc1 |
|
0.22.3 | 2021年4月18日 |
0.5.0 |
|
#2 in 数据结构
2,697,949 每月下载量
用于 3,723 个crate(515个直接使用)
740KB
19K SLoC
摘要
bitvec
为Rust中的位字段提供基础API。它将标准库数据结构(切片、数组和bool
的向量)特殊化为每个bool
使用一个位的存储,类似于C++中的std::bitset<N>
和std::vector<bool>
。
此外,它允许将内存区域划分为任意大小的整数存储区域,类似于Erlang中的二进制。
如果您需要将内存视为按位寻址而不是按字节寻址,那么bitvec
是您最快、最完整且符合Rust语法的crate。
简介
计算机不直接操作位。内存总线是按字节寻址的,处理器操作寄存器字,这些寄存器字通常是四到八字节,甚至更宽。这意味着当程序员希望对内存中的字节或寄存器字中的单个位进行操作时,他们必须手动进行,使用移位和掩码操作,这些操作对任何有经验的程序员来说可能都很熟悉。
bitvec
将 C++ 的紧凑型 bool
存储和 Erlang 的可分解位流的功能引入 Rust,并以与现有 Rust 习惯用法兼容且性能最优的方式提供。位流行为提供了 C 风格结构位域所需的逻辑,而相应的语法糖可以在 deku
中找到。
bitvec
使您能够编写简单、容易且快速的位寻址内存代码。它编译成的目标代码与手动编写移位/掩码指令得到的目标代码相同,甚至更好。它利用 Rust 强大的引用和类型系统,创建了一个无缝连接单比特寻址、内存布局的精确控制以及 Rust 原生的所有权和借用机制的系统。
亮点
bitvec
作为 Rust 库和位寻址系统具有许多独特的功能。
- 它支持任意位寻址,并且其位切片可以从前面开始。
BitSlice
是与[bool]
等效的区域类型,并且可以用 Rust 引用描述,因此可以适应基于引用的 API。- 类型参数使用户能够选择所需的精确内存表示。
- 特别是,如 这份 Mozilla 报告 中所述的“小心位域”错误根本无法产生。
- 原生支持原子整数作为位域存储。
- 如果内置的转换不足,用户可以提供自己的内存表示转换层。
然而,它的功能也带来了一些小的成本
BitSlice
不能用作指针(如Box
、Rc
或Arc
)的引用类型。BitSlice
不能实现IndexMut
,因此bitslice[index] = true;
不会工作。
用法
最低支持的 Rust 版本: 1.56.0
bitvec
力求遵循标准库中的序列 API。然而,由于其大多数功能都是不需要标准库实际具有符号的实现重写,这样做可能不需要提高 MSRV。
现在 bitvec
已达到 1.0,它将仅在次要版本发布时提高 MSRV。如果您有固定的 Rust 工具链,您应该使用具有限制性次要版本约束的 "~1.0"
依赖 bitvec
。
首先,在您的 Cargo 清单中依赖它
[dependencies]
bitvec = "1"
注意:
bitvec
支持#![no_std]
目标。如果您没有std
,请禁用默认功能,并明确恢复任何您拥有的功能[dependencies.bitvec] version = "1" default-features = false features = ["atomic", "alloc"]
一旦 Cargo 知道了它,就将其前言引入作用域
use bitvec::prelude::*;
您可以通过阅读 预导出 来查看具体哪些符号被导入。预导出引入了许多符号,虽然名称冲突不太可能,但您可能希望导入预导出的 模块 而不是其内容
use bitvec::prelude as bv;
您几乎肯定需要使用类型别名来为 bitvec
类型参数的特定实例命名,并使用该别名而不是在整个项目中保持泛型
示例
use bitvec::prelude::*;
// All data-types have macro
// constructors.
let arr = bitarr![u32, Lsb0; 0; 80];
let bits = bits![u16, Msb0; 0; 40];
// Unsigned integers (scalar, array,
// and slice) can be borrowed.
let data = 0x2021u16;
let bits = data.view_bits::<Msb0>();
let data = [0xA5u8, 0x3C];
let bits = data.view_bits::<Lsb0>();
// Bit-slices can split anywhere.
let (head, rest) = bits.split_at(4);
assert_eq!(head, bits[.. 4]);
assert_eq!(rest, bits[4 ..]);
// And they are writable!
let mut data = [0u8; 2];
let bits = data.view_bits_mut::<Lsb0>();
// l and r each own one byte.
let (l, r) = bits.split_at_mut(8);
// but now a, b, c, and d own a nibble!
let ((a, b), (c, d)) = (
l.split_at_mut(4),
r.split_at_mut(4),
);
// and all four of them are writable.
a.set(0, true);
b.set(1, true);
c.set(2, true);
d.set(3, true);
assert!(bits[0]); // a[0]
assert!(bits[5]); // b[1]
assert!(bits[10]); // c[2]
assert!(bits[15]); // d[3]
// `BitSlice` is accessed by reference,
// which means it respects NLL styles.
assert_eq!(data, [0x21u8, 0x84]);
// Furthermore, bit-slices can store
// ordinary integers:
let eight = [0u8, 4, 8, 12, 16, 20, 24, 28];
// a b c d e f g h
let mut five = [0u8; 5];
for (slot, byte) in five
.view_bits_mut::<Msb0>()
.chunks_mut(5)
.zip(eight.iter().copied())
{
slot.store_be(byte);
assert_eq!(slot.load_be::<u8>(), byte);
}
assert_eq!(five, [
0b00000_001,
// aaaaa bbb
0b00_01000_0,
// bb ccccc d
0b1100_1000,
// dddd eeee
0b0_10100_11,
// e fffff gg
0b000_11100,
// ggg hhhhh
]);
BitSlice
类型是一个视图,它会改变借用内存区域的行为。它永远不会被直接持有,而只能通过引用(由借用整数内存创建)或 BitArray
值类型持有。此外,动态分配器的存在使得 BitBox
和 BitVec
缓冲区类型成为可能,可用于更高级的缓冲区操作
#[cfg(feature = "alloc")]
fn main() {
use bitvec::prelude::*;
let mut bv = bitvec![u8, Msb0;];
bv.push(false);
bv.push(true);
bv.extend([false; 4].iter());
bv.extend(&15u8.view_bits::<Lsb0>()[.. 4]);
assert_eq!(bv.as_raw_slice(), &[
0b01_0000_11, 0b11_000000
// ^ dead
]);
}
虽然像 bits[index] = value;
这样的位置表达式不可用,但 bitvec
提供了一个代理结构,可以用来作为 几乎 的 &mut bit
引用
use bitvec::prelude::*;
let bits = bits![mut 0];
// `bit` is not a reference, so
// it must be bound with `mut`.
let mut bit = bits.get_mut(0).unwrap();
assert!(!*bit);
*bit = true;
assert!(*bit);
// `bit` is not a reference,
// so NLL rules do not apply.
drop(bit);
assert!(bits[0]);
bitvec
数据类型实现了对其标准库对应项的完整替代,包括所有固有方法、特性和运算符行为
用户故事
bitvec
的使用通常分为三大类。
- 紧凑、快速的
usize => bit
集合 - 截断整数存储
- 精确控制内存布局
位集合
在最基本的情况下,bitvec
提供了类似于标准库中 bool
集合的序列类型。默认行为针对快速内存访问和简单的代码生成进行了优化,并且可以以最小的开销压缩 [bool]
或 Vec
虽然 bitvec
在其默认工作中没有尝试利用 SIMD 或其他向量指令,但它的代码生成应该是 LLVM 自动向量化的好候选。如果您需要显式向量化,请 提交一个问题。
示例用法可能包括实现埃拉托斯特尼筛法以存储素数,或其他测试数字是/否属性集合;或者用 (BitVec, Vec
替换 Vec
。
要开始,您可以在项目中执行基本的文本替换。将现有类型翻译如下
[bool; N]
变为BitArray
[bool]
转换为BitSlice
Vec<bool>
转换为BitVec
Box<[bool]>
转换为BitBox
然后跟随出现的任何编译器错误。
位字段内存访问
单个信息位用途非常有限。 bitvec
还允许您通过选择位切片并使用 BitField
特性来存储比单个位更宽的整数。您可以使用无符号和有符号整数进行存储和检索,只要排序类型参数是 Lsb0
或 Msb0
。
如果您的位字段存储缓冲区永远不会被序列化以在机器之间交换,那么您可以使用默认的类型参数和未装饰的加载/存储方法。虽然直接检查存储整数的内存布局可能令人惊讶,但总体行为应该对您的目标是最优的。
记住: bitvec
只提供数组位置表达式,使用整数起始点和终点。如果您想要具有位字段内存存储的 C 风格命名结构字段,可以使用 deku
。
但是,如果您正在反序列化缓冲区进行传输,那么您就会落入第三个类别。
传输协议
许多协议使用子元素字段来节省传输空间;例如,TCP头中有单比特和 4 比特字段,以便将所有必要的信息打包到期望的空间量中。在 C 或 Erlang 中,这些 TCP 协议字段可以通过语言中的记录字段来映射。在 Rust 中,它们可以通过索引位切片来映射。
当使用 bitvec
来管理协议缓冲区时,您需要选择与您的内存布局匹配的确切类型参数。例如,TCP 使用 <u8, Msb0>
,而小端机器上的 IPv6 使用 <u32, Lsb0>
。完成此操作后,您可以替换所有 (memory & mask) >> shift
或 memory |= (value & mask) << shift
表达式,用 memory[start .. end]
。
作为直接示例,Itanium 指令集 IA-64 使用非常长的指令词,其中包含三个 41 比特字段,格式为 [u8; 16]
。一个 IA-64 汇编器将其手动移位/掩码实现替换为 bitvec
范围索引,直接从数据表中获取位号,并观察到其代码既易于维护,性能也更好!
功能标志
bitvec
具有一些Cargo特性,用于管理其API接口。默认特性集是
[dependencies.bitvec]
version = "1"
features = [
"alloc",
"atomic",
# "serde",
"std",
]
使用default-features = false
来禁用所有特性,然后使用features = []
来恢复您需要的特性。
-
alloc
:此特性链接到alloc
分发crate,并提供BitVec
和BitBox
类型。它可用于具有动态分配器但没有操作系统的#![no_std]
目标。 -
atomic
:此特性控制是否可以使用原子指令来处理别名内存。bitvec
使用
crate来自动检测原子功能,即使目标没有原子指令,也可以使用此特性启用。它的唯一影响是,具有原子指令的目标可以选择禁用它并强制单线程行为,从而不会发生原子同步。radium
-
serde
:此特性通过serde
系统启用bitvec
缓冲区的反序列化和序列化。如果您需要传输usize => bool
集合,这可能很有用。 -
std
:此特性提供了一些std::io::{Read,Write}
实现,以及用于各种错误类型的std::error::Error
。否则是不必要的。
深入了解
API文档API Documentation详细探讨了bitvec
的使用和实现。特别是,您应该阅读关于order
、store
和field
模块的文档,以及BitSlice
和BitArray
类型的文档。
此外,用户指南user guide探讨了构建bitvec
背后的哲学和学术概念,以及其目标和更复杂的部分。
虽然您只需将bitvec
放入代码中并使用与标准库相同的习惯,就可以开始使用bitvec
,但这两个资源都包含了您理解它做什么、如何工作以及如何对您有用的所有信息。