1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
//! ZIP が各エントリに求める CRC-32
//!
//! 多項式はビットを逆に並べる流儀の 0xedb88320 である。
//!
//! # 16 バイトずつ計算する
//!
//! 1 バイトずつ表を引く方式では、次のバイトの計算が前のバイトの結果を待つので、速さが頭打ちになる。
//! ここでは 16 枚の表を用意し、16 バイトをまとめて計算する。
//! 16 回の表引きは互いに待たないので、同時に進む。
//! k 枚目の表は、そのバイトのあとに k バイトの 0 が続いたときの値を持つ。
/// 16 バイトをまとめて引く表
static TABLE: [[u32; 256]; 16] = table();
/// 表を作る。const なので実行時には作らない
const fn table() -> [[u32; 256]; 16] {
let mut result = [[0u32; 256]; 16];
let mut index = 0;
while index < 256 {
let mut value = index as u32;
let mut round = 0;
while round < 8 {
value = if value & 1 == 1 {0xedb88320 ^ (value >> 1)} else {value >> 1};
round += 1;
}
result[0][index] = value;
index += 1;
}
let mut slice = 1;
while slice < 16 {
let mut index = 0;
while index < 256 {
let previous = result[slice - 1][index];
result[slice][index] = (previous >> 8) ^ result[0][(previous & 0xff) as usize];
index += 1;
}
slice += 1;
}
result
}
/// 少しずつ渡しても、一度に渡したときと同じ値になる CRC-32
#[derive(Debug, Clone, Copy)]
pub struct Crc {
value: u32,
}
impl Crc {
pub fn new() -> Crc {
Crc {value: 0xffffffff}
}
/// 続きのバイト列を流し込む
pub fn update(&mut self, data: &[u8]) {
let mut value = self.value;
let mut chunk = data.chunks_exact(16);
for piece in &mut chunk {
let head = value ^ u32::from_le_bytes([piece[0], piece[1], piece[2], piece[3]]);
value = TABLE[15][(head & 0xff) as usize]
^ TABLE[14][((head >> 8) & 0xff) as usize]
^ TABLE[13][((head >> 16) & 0xff) as usize]
^ TABLE[12][(head >> 24) as usize]
^ TABLE[11][piece[4] as usize]
^ TABLE[10][piece[5] as usize]
^ TABLE[9][piece[6] as usize]
^ TABLE[8][piece[7] as usize]
^ TABLE[7][piece[8] as usize]
^ TABLE[6][piece[9] as usize]
^ TABLE[5][piece[10] as usize]
^ TABLE[4][piece[11] as usize]
^ TABLE[3][piece[12] as usize]
^ TABLE[2][piece[13] as usize]
^ TABLE[1][piece[14] as usize]
^ TABLE[0][piece[15] as usize];
}
for byte in chunk.remainder() {
value = TABLE[0][((value ^ *byte as u32) & 0xff) as usize] ^ (value >> 8);
}
self.value = value;
}
/// ここまでの値
pub fn finish(&self) -> u32 {
!self.value
}
}
impl Default for Crc {
fn default() -> Crc {
Crc::new()
}
}
/// 一度に全部渡すとき
pub fn checksum(data: &[u8]) -> u32 {
let mut crc = Crc::new();
crc.update(data);
crc.finish()
}