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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
//! Utilities and representations for a frame header.
use crate::common::MAGIC_NUM;
use crate::encoding::util::{find_min_size, minify_val};
use alloc::vec::Vec;
/// A header for a single Zstandard frame.
///
/// <https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#frame_header>
#[derive(Debug)]
pub struct FrameHeader {
/// Optionally, the original (uncompressed) size of the data within the frame in bytes.
/// If not present, `window_size` must be set.
pub frame_content_size: Option<u64>,
/// If set to true, data must be regenerated within a single
/// continuous memory segment.
pub single_segment: bool,
/// If set to true, a 32 bit content checksum will be present
/// at the end of the frame.
pub content_checksum: bool,
/// If a dictionary ID is provided, the ID of that dictionary.
pub dictionary_id: Option<u64>,
/// The minimum memory buffer required to compress a frame. If not present,
/// `single_segment` will be set to true. If present, this value must be greater than 1KB
/// and less than 3.75TB. Encoders should not generate a frame that requires a window size larger than
/// 8mb.
pub window_size: Option<u64>,
}
impl FrameHeader {
/// Writes the serialized frame header into the provided buffer.
///
/// The returned header *does include* a frame header descriptor.
pub fn serialize(self, output: &mut impl crate::workspace::Growable<u8>) -> Result<(), crate::workspace::CapacityError> {
vprintln!("Serializing frame with header: {self:?}");
// https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#frame_header
// Magic Number:
output.extend_from_slice(&MAGIC_NUM.to_le_bytes())?;
// `Frame_Header_Descriptor`:
output.push(self.descriptor())?;
// `Window_Descriptor
// TODO: https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#window_descriptor
if !self.single_segment {
if let Some(window_size) = self.window_size {
let log = window_size.next_power_of_two().ilog2();
let exponent = log.saturating_sub(10) as u8;
output.push(exponent << 3)?;
}
}
if let Some(id) = self.dictionary_id {
output.extend(minify_val(id))?;
}
if let Some(frame_content_size) = self.frame_content_size {
output.extend(minify_val_fcs(frame_content_size))?;
}
Ok(())
}
/// Generate a serialized frame header descriptor for the frame header.
///
/// https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#frame_header_descriptor
fn descriptor(&self) -> u8 {
// A frame header starts with a frame header descriptor.
// It describes what other fields are present
// https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#frame_header_descriptor
// Writing the frame header descriptor:
// `Frame_Content_Size_flag`:
// The Frame_Content_Size_flag specifies if
// the Frame_Content_Size field is provided within the header.
// TODO: The Frame_Content_Size field isn't set at all, we should prefer to include it always.
// If the `Single_Segment_flag` is set and this value is zero,
// the size of the FCS field is 1 byte.
// Otherwise, the FCS field is omitted.
// | Value | Size of field (Bytes)
// | 0 | 0 or 1
// | 1 | 2
// | 2 | 4
// | 3 | 8
// `Dictionary_ID_flag`:
let dictionary_flag: u8 = if let Some(id) = self.dictionary_id {
match find_min_size(id) {
0 => 0,
1 => 1,
2 => 2,
4 => 3,
_ => panic!(),
}
} else {
// A `Dictionary_ID` was not provided
0
};
// `Content_Checksum_flag`:
let checksum_flag = u8::from(self.content_checksum);
// `Reserved_bit`:
// This value must be zero
// `Unused_bit`:
// An encoder compliant with this spec must set this bit to zero
// `Single_Segment_flag`:
// If this flag is set, data must be regenerated within a single continuous memory segment,
// and the `Frame_Content_Size` field must be present in the header.
// If this flag is not set, the `Window_Descriptor` field must be present in the frame header.
let single_segment_flag = if self.single_segment {
assert!(self.frame_content_size.is_some(), "if the `single_segment` flag is set to true, then a frame content size must be provided");
1
} else {
assert!(
self.window_size.is_some(),
"if the `single_segment` flag is set to false, then a window size must be provided"
);
0
};
let content_size_flag = if let Some(frame_content_size) = self.frame_content_size {
let field_size = find_min_size(frame_content_size);
match field_size {
1 => 0,
2 => 1,
4 => 2,
8 => 3,
_ => panic!(),
}
} else {
// `Frame_Content_Size` was not provided
0
};
dictionary_flag
| (checksum_flag << 2)
| (single_segment_flag << 5)
| (content_size_flag << 6)
}
}
/// Identical to [`minify_val`], but it implements the following edge case:
///
/// > When FCS_Field_Size is 1, 4 or 8 bytes, the value is read directly. When FCS_Field_Size is 2, the offset of 256 is added.
///
/// <https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#frame_content_size>
fn minify_val_fcs(val: u64) -> impl Iterator<Item = u8> {
let new_size = find_min_size(val);
let mut val = val;
if new_size == 2 {
val -= 256;
}
IntoIterator::into_iter(val.to_le_bytes()).take(new_size)
}
#[cfg(test)]
mod tests {
use super::FrameHeader;
use crate::decoding::frame::{read_frame_header, FrameDescriptor};
use alloc::vec::Vec;
#[test]
fn frame_header_descriptor_decode() {
let header = FrameHeader {
frame_content_size: Some(1),
single_segment: true,
content_checksum: false,
dictionary_id: None,
window_size: None,
};
let descriptor = header.descriptor();
let decoded_descriptor = FrameDescriptor(descriptor);
assert_eq!(decoded_descriptor.frame_content_size_bytes().unwrap(), 1);
assert!(!decoded_descriptor.content_checksum_flag());
assert_eq!(decoded_descriptor.dictionary_id_bytes().unwrap(), 0);
}
#[test]
fn frame_header_decode() {
let header = FrameHeader {
frame_content_size: Some(1),
single_segment: true,
content_checksum: false,
dictionary_id: None,
window_size: None,
};
let mut serialized_header = Vec::new();
header.serialize(&mut serialized_header).expect("test storage admission");
let parsed_header = read_frame_header(serialized_header.as_slice()).unwrap().0;
assert!(parsed_header.dictionary_id().is_none());
assert_eq!(parsed_header.frame_content_size(), 1);
}
#[test]
fn frame_header_decode_8_byte_content_size() {
let content_size = 1u64 << 40;
let header = FrameHeader {
frame_content_size: Some(content_size),
single_segment: true,
content_checksum: false,
dictionary_id: None,
window_size: None,
};
let mut serialized_header = Vec::new();
header.serialize(&mut serialized_header).expect("test storage admission");
let parsed_header = read_frame_header(serialized_header.as_slice()).unwrap().0;
assert_eq!(parsed_header.frame_content_size(), content_size);
}
#[test]
#[should_panic]
fn catches_single_segment_no_fcs() {
let header = FrameHeader {
frame_content_size: None,
single_segment: true,
content_checksum: false,
dictionary_id: None,
window_size: Some(1),
};
let mut serialized_header = Vec::new();
header.serialize(&mut serialized_header).expect("test storage admission");
}
#[test]
#[should_panic]
fn catches_single_segment_no_winsize() {
let header = FrameHeader {
frame_content_size: Some(7),
single_segment: false,
content_checksum: false,
dictionary_id: None,
window_size: None,
};
let mut serialized_header = Vec::new();
header.serialize(&mut serialized_header).expect("test storage admission");
}
}