27个版本 (2个稳定版)

1.0.1 2022年7月10日
1.0.0 2022年1月11日
1.0.0-rc1 2021年12月1日
0.22.3 2021年4月18日
0.5.0 2018年7月7日

#2 in 数据结构

Download history 635455/week @ 2024-04-09 623539/week @ 2024-04-16 608165/week @ 2024-04-23 545398/week @ 2024-04-30 563650/week @ 2024-05-07 585812/week @ 2024-05-14 568206/week @ 2024-05-21 614859/week @ 2024-05-28 656278/week @ 2024-06-04 660420/week @ 2024-06-11 645626/week @ 2024-06-18 684538/week @ 2024-06-25 620688/week @ 2024-07-02 675197/week @ 2024-07-09 697148/week @ 2024-07-16 580424/week @ 2024-07-23

2,697,949 每月下载量
用于 3,723 个crate(515个直接使用)

MIT 许可证

740KB
19K SLoC

bitvec

内存的放大镜

Crate Documentation License

Crate Downloads Project Size

  1. 摘要
  2. 简介
  3. 亮点
  4. 用法
  5. 示例
  6. 用户故事
    1. 位集合
    2. 位字段内存访问
    3. 传输协议
  7. 功能标志
  8. 深入了解

摘要

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 不能用作指针(如 BoxRcArc)的引用类型。
  • 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 值类型持有。此外,动态分配器的存在使得 BitBoxBitVec 缓冲区类型成为可能,可用于更高级的缓冲区操作

#[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 特性来存储比单个位更宽的整数。您可以使用无符号和有符号整数进行存储和检索,只要排序类型参数是 Lsb0Msb0

如果您的位字段存储缓冲区永远不会被序列化以在机器之间交换,那么您可以使用默认的类型参数和未装饰的加载/存储方法。虽然直接检查存储整数的内存布局可能令人惊讶,但总体行为应该对您的目标是最优的。

记住: bitvec 只提供数组位置表达式,使用整数起始点和终点。如果您想要具有位字段内存存储的 C 风格命名结构字段,可以使用 deku

但是,如果您正在反序列化缓冲区进行传输,那么您就会落入第三个类别。

传输协议

许多协议使用子元素字段来节省传输空间;例如,TCP头中有单比特和 4 比特字段,以便将所有必要的信息打包到期望的空间量中。在 C 或 Erlang 中,这些 TCP 协议字段可以通过语言中的记录字段来映射。在 Rust 中,它们可以通过索引位切片来映射。

当使用 bitvec 来管理协议缓冲区时,您需要选择与您的内存布局匹配的确切类型参数。例如,TCP 使用 <u8, Msb0>,而小端机器上的 IPv6 使用 <u32, Lsb0>。完成此操作后,您可以替换所有 (memory & mask) >> shiftmemory |= (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,并提供BitVecBitBox类型。它可用于具有动态分配器但没有操作系统的#![no_std]目标。

  • atomic:此特性控制是否可以使用原子指令来处理别名内存。bitvec使用radium crate来自动检测原子功能,即使目标没有原子指令,也可以使用此特性启用。它的唯一影响是,具有原子指令的目标可以选择禁用它并强制单线程行为,从而不会发生原子同步。

  • serde:此特性通过serde系统启用bitvec缓冲区的反序列化和序列化。如果您需要传输usize => bool集合,这可能很有用。

  • std:此特性提供了一些std::io::{Read,Write}实现,以及用于各种错误类型的std::error::Error。否则是不必要的。

深入了解

API文档API Documentation详细探讨了bitvec的使用和实现。特别是,您应该阅读关于orderstorefield模块的文档,以及BitSliceBitArray类型的文档。

此外,用户指南user guide探讨了构建bitvec背后的哲学和学术概念,以及其目标和更复杂的部分。

虽然您只需将bitvec放入代码中并使用与标准库相同的习惯,就可以开始使用bitvec,但这两个资源都包含了您理解它做什么、如何工作以及如何对您有用的所有信息。

依赖关系