modules/zstd: add buffer module by rdob-ant · Pull Request #1167 · google/xls

rdob-ant · 2023-10-26T12:50:31Z

This commit adds a DSLX Buffer library that provides the Buffer struct, and helper functions that can be used to operate on it. The Buffer is meant to be a storage for data coming from the channel. It acts like a FIFO containing bits, allowing data of any length to be put in or popped out of it. Includes DSLX tests to verify the behavior of the library.

This bitwise nature of the buffer is expected to be useful later when dealing with FSE-encoded data.

NOTE: this is based on top of #1166 , please ignore commits from that branch when reviewing.

xls/modules/zstd/buffer.x

proppy · 2023-11-09T14:24:49Z

xls/modules/zstd/buffer.x

+        ()
+    };
+
+    let mask = (bits[BSIZE]:1 << length) - bits[BSIZE]:1;


I think we could use bitslice instead.

buffer.contents[0:length]

Same problem as in #1167 (comment)

xls/modules/zstd/buffer.x

proppy · 2024-01-19T16:17:39Z

xls/modules/zstd/buffer.x

+// It will fail if the buffer cannot fit the data. For calls that need better
+// error handling, check `buffer_append_checked`
+pub fn buffer_append<CAPACITY: u32, DSIZE: u32> (buffer: Buffer<CAPACITY>, data: bits[DSIZE]) -> Buffer<CAPACITY> {
+    if buffer_can_fit(buffer, data) == false {


q: should we get rid of the check here, since it is supposed to be the unchecked version?

Checked/unchecked variants refer to the way the failure is reported in resulting verilog.
For the unchecked variant this check only indicates that something went wrong at the IR simulation level. Codegen verilog for that won't have any logic for that.
I think it is good idea to keep this check to signal the user potential issues in his/hers DSLX logic

since the fail! built-in emit as $fatal in verilog I do think the associated logic for compute the condition will also get codegen'ed (but maybe optimized away by synthesis?)

rather than having two variant of the function, maybe we could only keep the unchecked one (w/ the fail!) and have the caller rely on calling can_fit if they need to do something dynamic?

wdyt?

As far as I remember $fatal is available only in SystemVerilog. For our benchmarks we do codegen with Verilog which does not generate any logic for this. On the other hand, it generates $display() for trace_fmt!() and those are then removed in the synthesis process so it is possible that logic for $fatal would also be removed.

rather than having two variant of the function, maybe we could only keep the unchecked one (w/ the fail!) and have the caller rely on calling can_fit if they need to do something dynamic?

This is good idea, we can probably do that.

On the other hand when I looked closely at the implementation after removing _checked variants of the functions it does not look that good. For example, we use _checked functions in frame header decoding in 4 places in single frame_header.x file. Removing _checked functions would require placing checks straight in the logic of frame header decoder. It would look something like that for each usage of _checked variant of the functions:

diff --git a/xls/modules/zstd/frame_header.x b/xls/modules/zstd/frame_header.x index 785586396..01cd927cd 100644 --- a/xls/modules/zstd/frame_header.x +++ b/xls/modules/zstd/frame_header.x @@ -115,7 +115,24 @@ fn test_extract_frame_header_descriptor() { // returns BufferResult with the outcome of the operations on the buffer and // information extracted from the Frame_Header_Descriptor fn parse_frame_header_descriptor<CAPACITY: u32>(buffer: Buffer<CAPACITY>) -> (BufferResult<CAPACITY>, FrameHeaderDescriptor) { - let (result, data) = buff::buffer_fixed_pop_checked<CAPACITY, u32:8>(buffer); + let (result, data) = if (buff:buffer_has_at_least(buffer, u32:8)) { + let (buffer_leftover, content) = buff::buffer_fixed_pop<CAPACITY, u32:8>(buffer); + ( + buff::BufferResult { + status: buff:BufferStatus::OK, + buffer: buffer_leftover + }, + content + ) + } else { + ( + buff::BufferResult { + status: buff::BufferStatus:NO_ENOUGH_DATA, + buffer: buffer + }, + bits[CAPACITY]:0 + ) + }; match result.status { BufferStatus::OK => { let frame_header_desc = extract_frame_header_descriptor(data);

It is possible to put the code from match straight under the if but this will still lead to unnecessary code duplication. Maybe it would be better to keep those _checked functions?

I'd be curious to see what the calling logic does when handling buff::BufferStatus:NO_ENOUGH_DATA, can you point me to it?

My reasoning is that if you're gonna act on something related to the size of the buffer, you'd rather do this early on to make it explicit how you handle this case from the protocol pov, rather than relying on propagating the status back from the buffer call.

OK, so the part that is responsible for handling NO_ENOUGH_DATA is the top level proc of the ZstdDecoder. The code for this is not a part of any open PR yet as we still work on fixing bugs found in our C++ tests where we compare our decoder against libzstd.
Top level proc has states which mark the stage of frame decoding, e.g.:

enum ZstdDecoderStatus : u8 { DECODE_MAGIC_NUMBER = 0, DECODE_FRAME_HEADER = 1, DECODE_BLOCK_HEADER = 2, FEED_BLOCK_DECODER = 3, DECODE_CHECKSUM = 4, ERROR = 255, }

When NO_ENOUGH_DATA occurs we just stay in the current state for the next evaluation where we receive data from decoder input and append it to the buffer. Then we can try again to decode the part specified by the state.

We've opened a PR which contains the mentioned code. It's #1315. You can check the example of handling NO_ENOUGH_DATA here.

proppy · 2024-01-19T16:18:00Z

xls/modules/zstd/buffer.x

+        BufferResult {
+            status: BufferStatus::OK,
+            buffer: Buffer {
+                content: (data as bits[CAPACITY] << buffer.length) | buffer.content,


q: should we try to reuse buffer_append_unchecked here?

Good idea, thanks!

proppy · 2024-01-19T16:18:27Z

xls/modules/zstd/buffer.x

+// the function will fail. For calls that need better error handling,
+// check `buffer_pop_checked`.
+pub fn buffer_pop<CAPACITY: u32>(buffer: Buffer<CAPACITY>, length: u32) -> (Buffer<CAPACITY>, bits[CAPACITY]) {
+    if buffer_has_at_least(buffer, length) == false {


q: should we get rid of the check here, since it is supposed to be the unchecked version?

Similarly as with buffer_append() this only serves the purpose of informing the user about potential issues at the stage of IR simulation. I think it is useful to have this.

xls/modules/zstd/buffer.x

proppy · 2024-01-19T16:19:41Z

xls/modules/zstd/buffer.x

+// can be used is presented below. It uses the structure to combine several
+// smaller transactions into bigger ones.
+
+proc BufferExampleUsage {


maybe that should go a in separate file?

Sure, would you like to have it here under xls/modules/zstd or in xls/examples (see my comment bellow)?

under zstd is fine for now I think.

Ok, no problem

proppy · 2024-01-19T16:22:00Z

xls/modules/zstd/buffer.x

+// can be used is presented below. It uses the structure to combine several
+// smaller transactions into bigger ones.
+
+proc BufferExampleUsage {


q: sounds like this could be a generally useful parametric proc (and not just a sample) to window channel data differently?

It seems to be a good idea. If we want to have this example as parametric proc, then it would be reasonable to have it here in xls/modules/zstd and a specialization of it under xls/examples

I think we could keep the proc and the example in zstd for now.

No problem, I will update the PR after I check if my changes didn't affect other zstd procs.

lpawelcz · 2024-02-15T11:11:51Z

@proppy the example is now placed in a separate file and the proc is renamed to WindowBuffer. It is parameterized with buffer size, input and output width. There is also a specialized version of this proc available in the same file for the purpose of verilog generation and benchmarking.

proppy · 2024-02-19T10:21:17Z

xls/modules/zstd/window_buffer.x

+
+// This file contains implementation of a Buffer structure that acts as
+// a simple FIFO. Additionally, the file provides various functions that
+// can simplify access to the stored.


update the comment?

proppy · 2024-02-19T10:21:26Z

xls/modules/zstd/window_buffer.x

+// a simple FIFO. Additionally, the file provides various functions that
+// can simplify access to the stored.
+//
+// The utility functions containing the `_checked` suffix serve two purposes:


update the comment?

proppy · 2024-02-19T10:22:16Z

xls/modules/zstd/window_buffer.x

+// in transactions of <INPUT_WIDTH> length and output it in transactions of
+// <OUTPUT_WIDTH> length. <BUFFER_SIZE> defines the maximal size of the buffer.
+
+proc WindowBuffer<BUFFER_SIZE: u32, INPUT_WIDTH: u32, OUTPUT_WIDTH: u32> {


is there a relation between BUFFER_SIZE, INPUT_WIDTH and OUTPUT_WIDTH that we can const_assert?

We can for sure assert BUFFER_SIZE >= INPUT WIDTH and BUFFER_SIZE >= OUTPUT_WIDTH.

proppy · 2024-02-19T10:24:21Z

xls/modules/zstd/window_buffer.x

+
+    next(tok: token, buffer: Buffer<BUFFER_SIZE>) {
+        let (tok, recv_data) = recv(tok, input_r);
+        let buffer = buff::buffer_append<BUFFER_SIZE>(buffer, recv_data);


shouldn't BUFFER_SIZE be inferred from the buffer arg?

Right, fixed

proppy · 2024-02-19T10:24:46Z

xls/modules/zstd/window_buffer.x

+        let buffer = buff::buffer_append<BUFFER_SIZE>(buffer, recv_data);
+
+        if buffer.length >= OUTPUT_WIDTH {
+            let (buffer, data_to_send) = buff::buffer_fixed_pop<BUFFER_SIZE, OUTPUT_WIDTH>(buffer);


shouldn't BUFFER_SIZE be inferred from the buffer arg?

Had to change the ordering of the parameters for buffer functions so that BUFFER_SIZE is now the last on the list. Fixed.

proppy · 2024-02-19T10:26:04Z

xls/modules/zstd/window_buffer.x

+}
+
+#[test_proc]
+proc WindowBufferTest {


maybe add a test with INPUT_WIDTH > OUTPUT_WIDTH for completeness?

proppy · 2024-02-19T10:26:32Z

xls/modules/zstd/window_buffer.x

+}
+
+// Sample for codegen
+proc WindowBuffer64 {


thanks for adding this!

This commit adds a DSLX Buffer library that provides the Buffer struct, and helper functions that can be used to operate on it. The Buffer is meant to be a storage for data coming from the channel. It acts like a FIFO, allowing data of any length to be put in or popped out of it. Provided DSLX tests verify the correct behaviour of the library. Internal-tag: [#50221] Signed-off-by: Robert Winkler <[email protected]>

This commit adds a simple test that shows, how one can use the Buffer struct inside a Proc. Internal-tag: [#50221] Signed-off-by: Robert Winkler <[email protected]>

Signed-off-by: Pawel Czarnecki <[email protected]>

google#1167 modules/zstd: Add buffer library This commit adds a DSLX Buffer library that provides the Buffer struct, and helper functions that can be used to operate on it. The Buffer is meant to be a storage for data coming from the channel. It acts like a FIFO, allowing data of any length to be put in or popped out of it. Provided DSLX tests verify the correct behaviour of the library. Internal-tag: [#50221] Signed-off-by: Robert Winkler <[email protected]> modules/zstd: Add Buffer use-case example This commit adds a simple test that shows, how one can use the Buffer struct inside a Proc. Internal-tag: [#50221] Signed-off-by: Robert Winkler <[email protected]>

google#1167 modules/zstd: Add buffer library This commit adds a DSLX Buffer library that provides the Buffer struct, and helper functions that can be used to operate on it. The Buffer is meant to be a storage for data coming from the channel. It acts like a FIFO, allowing data of any length to be put in or popped out of it. Provided DSLX tests verify the correct behaviour of the library. Internal-tag: [#50221] Signed-off-by: Robert Winkler <[email protected]> modules/zstd: Add Buffer use-case example This commit adds a simple test that shows, how one can use the Buffer struct inside a Proc. Internal-tag: [#50221] Signed-off-by: Robert Winkler <[email protected]> modules/zstd/buffer: Add benchmarking rules Signed-off-by: Pawel Czarnecki <[email protected]>

lpawelcz · 2024-03-29T11:59:16Z

The review will take place in #1315

@proppy this PR can be closed

rdob-ant mentioned this pull request Oct 26, 2023

modules/zstd: add frame header parser #1168

Closed

proppy reviewed Oct 26, 2023

View reviewed changes