API for user-specified Dictionary_ID's confusing (or missing?)

[nigeltao]

I want to use zstd dictionaries with user-specified Dictionary_ID's (as per the RFC 8478 Section 5, "If the frame is going to be distributed in a private environment, any Dictionary_ID can be used"), but I am not using the zstd --train command line tool. (See tangential footnote below.)

I am finding the zstd.h API and the zstd manual difficult to understand.

I think I can get to ZSTD_compress_usingDict to work... but if I understand the frame format, the resultant encoded bytes don't contain a Dictionary_ID. That's not so surprising, as I've never passed the Dictionary_ID to any ZSTD_etc functions. But... how do I provide one? What function should I call?

Perhaps I should use ZSTD_createCDict and then manipulate the ZSTD_CDict somehow. I can see ZSTD_getDictID_etc getter methods but no ZSTD_setDictID_etc setter methods.

Or, perhaps I should somehow convert my raw dictionary into zstd --train's format. But Section 5 says that this format contains Entropy_Tables, so it's not just as simple as prepending a fixed sized prefix to my raw dictionary bytes. In any case, it sounds like an expensive computation, for what I was hoping to be a trivial setter function or extra function argument.

What would you recommend? How do I pass a user-specified Dictionary_ID to the ZSTD_CCtx?

---

As a general dictionary API issue, I often found it unclear what format the dictionary (pointer, length) arguments were expecting.

For example, ZSTD_compress_usingDict takes const void* dict, size_t dictSize arguments. Does this (pointer, length) pair hold

• (A) the raw dictionary bytes (IIUC, a 'content-only dictionary'),
• (B) the wrapped zstd --train format of Section 5, or
• (C) either?

The comment says "Note 2 : When dict == NULL || dictSize < 8 no dictionary is used" suggests that ZSTD_compress_usingDict is (A) or (C). On the other hand, the comment also says "A dictionary can be any arbitrary data segment (also called a prefix), or a buffer with specified information", which suggests (C).

But for (C), how does it distinguish raw dictionary bytes that happen to start with e.g. the 0xEC30A437 magic number?

Similarly, ZSTD_getDictID_fromDict also takes const void* dict, size_t dictSize, and its comment says "Provides the dictID stored within dictionary. if return == 0, the dictionary is not conformant with Zstandard specification", which suggests either (B) or (C).

Coming back to ZSTD_createCDict, it also takes const void* dictBuffer, size_t dictSize. But what are the semantics? Is it (A), (B) or (C)? How do I tell without diving further into the source code?

Perhaps the various const void* dict, size_t dict_size function arguments could be renamed so that it's clear when it's expecting (A) or when it's expecting (B). Or does everything take (C), and if so, what am I supposed to do in the "false positive" case where my raw dictionary bytes coincidentally also look like the Section 5 format?

---

By the way, ZSTD_compress_usingDict's comment says "A dictionary can be any arbitrary data segment (also called a prefix), or a buffer with specified information (see dictBuilder/zdict.h)."

I looked at "dictBuilder/zdict.h", but didn't find it helpful. In any case, I'm not looking to train a dictionary. I have a dictionary, and I have a Dictionary_ID that I'd like to associate with it, but I can't see how to make that association.

---

Tangential footnote:

I am not using zstd --train. I am using the https://github.com/google/brotli/blob/master/research/dictionary_generator.cc program, with its --chunk_len option, creating dictionaries for chunks within a single file. Even if zstd --train gained an option to do that, I'm working with multiple compression codecs that could all use the same dictionary, so I'd rather not introduce a zstd-specfiic format.

Further links:

• ractool command line program
• RAC (Random Access Compression) spec, where I have tried to base "RAC + Zstandard" dictionaries on my understanding of "RAC + Zlib" dictionaries (e.g. RFC 1950's DICTID field being a hash of the dictionary's contents), but perhaps my mental model doesn't match Zstd perfectly.

[felixhandte]

Hi @nigeltao,

A couple in-line replies:

For example, ZSTD_compress_usingDict takes const void* dict, size_t dictSize arguments. Does this (pointer, length) pair hold

(A) the raw dictionary bytes (IIUC, a 'content-only dictionary'),
(B) the wrapped zstd --train format of Section 5, or
(C) either?

All functions that take a dictionary handle both formats (although, as you note, some functions like ZSTD_getDictID_fromDict() only make sense in the context of a structured dictionary and will fail if given an unstructured dictionary).

how does it distinguish raw dictionary bytes that happen to start with e.g. the 0xEC30A437 magic number?

By default, Zstd will attempt to interpret such a dictionary as a structured dictionary. ZSTD_createCDict_advanced(), ZSTD_createDDict_advanced(), etc. take a ZSTD_dictContentType_e parameter, which lets you control that behavior.

In short, your use case makes sense, but is not how Zstd works at present. To be used, dictIDs must be written into the dictionary. In particular, Zstd uses this guarantee to perform its own validation, when a dictionary ID is written into a compressed message, asserting during decompression that the provided dictionary has a matching ID. We could conceivably add functionality to support this use case (injecting and then retrieving dictionary IDs independent of the actual dictionary used), but I'm not sure how broadly useful that would be. Especially given that there is a relatively simple alternative of coordinating this in an out-of-band fashion (e.g., adding a custom prefix / header).

Alternatively, you can go ahead and add a header to a content-only dictionary via ZDICT_finalizeDictionary(). As you've noted though, this header also necessarily includes other data (the entropy tables and initial repcode values), which are generated by providing samples to ZDICT_finalizeDictionary(). You could try to pass minimal/fake/empty samples to this function to basically skip the entropy bits, but if you go too minimal, I believe the function will just fail.

I hope that's helpful.

[Cyan4973]

Hi @nigeltao ,

I believe @felixhandte answered the main points,
here are a few complementary details :

How do I pass a user-specified Dictionary_ID to the ZSTD_CCtx?

That's not possible.
The dictID is part of the dictionary content header. If the dictionary is just a stream of bytes, it doesn't contain any header, hence no dictID.

This can be different from other API, such as, for example LZ4, which provides a dictID field, but merely as a convenient way to transport this information into the frame. liblz4 makes no effort at controlling this value, because it can't : it's up to the user to read the value, and do something with it. In contrast,libzstd will actively control that a dictID field is correct, by comparing it with the dictionary header, and will trigger an error if it's not.

There is a work-around though : the dictionary builder allows any 3rd party content generator, and will only attach a conforming header with the function ZDICT_finalizeDictionary().
https://github.com/facebook/zstd/blob/dev/lib/dictBuilder/zdict.h#L218 .
It also makes it possible to manually set a dictID value.

The main downside is that ZDICT_finalizeDictionary() requires accessing a few target samples to compress, on top of 3rd-party generated content, so that statistics information present in the header are somewhat meaningful.

The zstd header will not get in the way of any compressor using a dictionary as raw content, such as gzip or lz4. It's merely a few more bytes at the beginning, they are meaningless and at the end of address space, meaning it doesn't impact coding efficiency. It's essentially free all other codecs, and just useful for zstd.

I often found it unclear what format the dictionary (pointer, length) arguments were expecting.

The answer is "(C) either", in most cases : you can expect the library to accept both "raw content" and "zstd-formatted" dictionaries. Only when it explicitly says otherwise will it be limited.

how does it distinguish raw dictionary bytes that happen to start with e.g. the 0xEC30A437 magic number?

It will presume that this is a properly formatted zstd dictionary, and will then fail trying to parse it. There are advanced functions available to force reading the dictionary as "raw content" only.
See https://github.com/facebook/zstd/blob/dev/lib/zstd.h#L1101 .
Anything that accepts a ZSTD_dictContentType_e gives full control to the user regarding how dictionary data is interpreted.

I looked at "dictBuilder/zdict.h", but didn't find it helpful.

It's fair to say that our zdict API is not the best documented one. Our efforts have been mostly concentrated on zstd.h.
That being said, we are opened on this topic, and willing to improve this situation. Anything that can help users and reduce confusion is welcomed. We will have another look, and accept in PR which improves this part.

As an example of action, the zstd.h API is also replicated as zstd_manual.html, making it more accessible, attracting more comments. We may offer the same transformation for zdict.h if it's useful.

I am using the https://github.com/google/brotli/blob/master/research/dictionary_generator.cc program,

I would recommend testing both dictionary content generators, and pick the better one. According to our tests, there can be substantial efficiency differences between generators, large enough to be worth a comparison.

creating dictionaries for chunks within a single file.

Yes, there is also an equivalent option with zstd, it's the --block-size=# or -B# command, which will automatically cut input file(s) into blocks of maximum # bytes. So far, it's considered more like a debug function, as we have not found many legitimate use cases, hence it's not widely announced. But if needed, it's there.
The functionality is provided in dibio.c, which is part of the CLI, but not part of the library libzstd.

wuffs is amazing

By the way, let's use this opportunity to thank and praise your work on the wonderful project wuffs, I've been following it for some time. Not only is it an impressive engineering achievement by itself, but the approach presented really deserves praise and more attention from all programming sides. Providing low-level guarantees in a compact and easily readable format is a great direction that I wish should inspire more 21st century languages.

[nigeltao]

ZDICT_finalizeDictionary() requires accessing a few target samples to compress, on top of 3rd-party generated content, so that statistics information present in the header are somewhat meaningful.

OK, can I just say: here's one (fake) sample, the single byte "\x00"? Or should I give a few more (one-byte) samples, or should I give multi-byte samples? What's the implication if the statistics are 'wrong'? At the time I'm encoding the dictionary into my file, I don't really have a set of sources to make a representative sample, let alone a complete set.

[nigeltao]

Also, ZDICT_finalizeDictionary() is not stabilized yet (it's behind #ifdef ZDICT_STATIC_LINKING_ONLY), which makes it harder for my (Go) program to use it.

Should I file a separate issue to track stabilizing zdict.h API?

[Cyan4973]

OK, can I just say: here's one (fake) sample, the single byte "\x00"?

No, this will not work.
The samples must be representative of future data to compress.
Otherwise, statistics are off, and are at best not useful, at worst detrimental.

I don't really have a set of sources to make a representative sample

OK, so maybe I don't understand the target application.
I thought it was about the RAC format, which I believed implies that there are some data blocks to pack together in this format ?
If yes, the data blocks are the samples.

Should I file a separate issue to track stabilizing zdict.h API?

Yes, it's a good idea.

[nigeltao]

Otherwise, statistics are off, and are at best not useful, at worst detrimental.

Detrimental as in "incorrect output" or merely "worse performance"? If it's just "worse performance", roughly speaking, would you expect "a little worse", "a lot worse", or "it depends"?

If I wanted to read more about how the statistics are used, do you have any suggestions (other than the obvious "read the source code")? For example, should I just start with http://fastcompression.blogspot.com/2014/01/fse-decoding-how-it-works.html and go forward through your blog?

I thought it was about the RAC format, which I believed implies that there are some data blocks to pack together in this format ?

Sorry for not being clearer. Yes, this is RAC, but RAC is not tied to zstd, there's also RAC+zlib, RAC+lz4, RAC+brotli, etc. In general, I like to try multiple compression algorithms, and pick which one works best for my users' particular corpus.

The workflow separates dictionary generation from RAC file generation. They are literally two different programs. This is partly because one is C++ and one is Go, so it's not trivial to put it all in one monolithic program. But also because the dictionary can be re-used across compression codecs (zlib, zstd, etc): if I want to compare multiple different codecs on the same source file, I still only have to create the dictionary once (in theory).

The dictionary program is, for me, often Brotli's dictionary_generator.cc that I mentioned in the OP, not zstd --train. Importantly, even if I wanted to use zstd --train with --block-size=#, the dictionary generator needs to output a dictionary.dat file that is codec-agnostic (to work with the multiple compression formats): a raw dictionary, not anything zstd-specific, so no samples.

The RAC file generation program takes the dictionary file, and the source file as stdin. It treats the input as a stream, not something that is seekable or rewindable. Thus, when encoding the first chunk, it would like to use the dictionary, but it doesn't yet know the upcoming N-1 chunks to make a realistic sample.

That's why I said "I don't really have a set of sources to make a representative sample". Of course, it's all software, and software is infinitely malleable, but I was hoping to avoid making zstd a special case in my workflow, such as "use this dictionary generation program for RAC+zstd, use this other one for RAC+anything_else".

Should I file a separate issue to track stabilizing zdict.h API?

I filed #1816.

[Cyan4973]

Detrimental as in "incorrect output" or merely "worse performance"?

worse performance

roughly speaking, would you expect "a little worse", "a lot worse", or "it depends"?

it depends.
2 important factors, source size, and compression levels.
For small source sizes, the algorithm will rely on precomputed statistics.
At low compression levels, algorithm will basically "trust" the statistics, in order to save time, which can be disastrous if statistics are plain wrong.
Higher compression levels are able to make more intelligent choices, and discard bad statistics.

If I wanted to read more about how the statistics are used, do you have any suggestions

I would recommend starting with :
https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#dictionary-format

This will tell exactly what's present in the statistics section of a zstd dictionary.

As to why it helps, well, this is related to entropy coding, hence a bit complex to explain, though relatively generic. In simple terms, it is the central reason for the compression difference between lz4 and zstd.

even if I wanted to use zstd --train with --block-size=#, the dictionary generator needs to output a dictionary.dat file that is codec-agnostic (to work with the multiple compression formats)

It's really possible to use the output of zstd --train as a raw dictionary, broadly usable for any other codec, including gzip or lz4. We actually do use it this way within our infrastructure. The small header at the front of the file does not make a difference for other codecs.

[nigeltao]

2 important factors, source size, and compression levels.

Ah, so the dictionary statistics are only used when compressing, and not when decompressing?

At low compression levels, algorithm will basically "trust" the statistics, in order to save time,

Would it be feasible to have an API switch (either through an explicit function call or to have some special-cased "nonsense" statistics values) to say "don't trust the statistics; spend the time"?

Higher compression levels are able to make more intelligent choices

How much is "high"? For example, is "compression level 9" considered high?? Would 9 (or 12, or 19, or whatever) be "disastrous" if I seeded some fake statistics with 256 samples, each one byte long (i.e. a uniform distribution), just to satisfy the ZDICT_finalizeDictionary API?

It's really possible to use the output of zstd --train as a raw dictionary

OK. The cooked (non-raw) dictionary format is: Magic_Number, Dictionary_ID, Entropy_Tables, Content. The first two terms are tiny (4+4 bytes). How big are the Entropy_Tables?

Even so, I'd still like to be able to work with raw dictionaries (e.g. use other dictionary-generating programs like Brotli's dictionary_generator.cc, which obviously doesn't speak the zstd cooked dictionary format). Even though zstd --train has a --block-size parameter, I'd still like to be able to experiment with different dictionary selection algorithms and implementations. That Brotli program comes with three different algorithms (what they call engines): https://github.com/google/brotli/blob/c435f066751ef83aa4194445085a70ad9d193704/research/dictionary_generator.cc#L102

You're right that I could just use zstd's format as a slightly longer raw dictionary (with a funny prefix), but then suppose I'd also like to work with a new compression format in the future (for argument's sake, let's call it middle-out), and it also has its own cooked dictionary format. I then can't produce the one dictionary.dat file that is both zstd's cooked format and middle-out's cooked format. On the other hand, it'd be nice if "raw dictionary" was a common denominator that worked with every codec.

[Cyan4973]

so the dictionary statistics are only used when compressing, and not when decompressing?

If statistics are used during compression, they are also needed during decompression.

if I seeded some fake statistics with 256 samples, each one byte long

That's not a good direction, really. You would be better off providing a raw dictionary with no statistics.

How big are the Entropy_Tables?

This is variable. Expect a budget in the ~100 bytes range, it can be more or less depending on exact statistics.

I'd still like to be able to experiment with different dictionary selection algorithms and implementations

suppose I'd also like to work with a new compression format in the future (for argument's sake, let's call it middle-out), and it also has its own cooked dictionary format.

That's indeed what's going to happen, hence what your process should be prepared for.

The reality is that what is called "raw dictionary" is not optimal for all algorithms, far from it.
Even when restricted to its "raw content" part, the exact layout efficiency is dependent on compressor's capabilities, so the generator will favor one algorithm over another.

Besides, the "raw content" is only a part. It used to be good enough for older algorithm like deflate (which were not providing any dictionary builder), because it was enough information to rebuild a common "state", coherent on both compression and decompression sides .

But the reality is that we are talking about starting compression / decompression from a common state, and there is more to a state than just the content of the window. As time progresses, this distinction will be more and more present.
zstd dictionaries make very light use of this capability, by adding a small header containing statistics, that's why it's still broadly compatible with "raw" dictionaries.
But future algorithms will go farther. brotli, for example, is currently defining its future dictionary format, which is very different from deflate's "raw content". It's actually closer to LZ78, and requires specific interpretation rules. It may seem superficially compatible with "raw content" dictionaries, but will be in fact ineffective in this context. brotli is the only algorithm able to make efficient use of it, thanks to the interpretation rules, which are absolutely not obvious (one needs to read the specs).

The reality is that each compressor will come with its own dictionary generator, and dictionary format, tailored for maximum efficiency for the target compression algorithm.

The idea of a "universal dictionary" has been a thing, and compared to "nothing" it was certainly a progress. But as we are improving our understanding of this technique, it becomes clear that this was just an intermediate stage, leaving a lot of capabilities on the table. The industry is moving past it.

it'd be nice if "raw dictionary" was a common denominator that worked with every codec.

They do work with every codec. They are just much less efficient,

[nigeltao]

if I seeded some fake statistics with 256 samples, each one byte long

That's not a good direction, really. You would be better off providing a raw dictionary with no statistics.

OK, does "no statistics" mean calling ZDICT_finalizeDictionary with the nbSamples argument set to zero, or does it mean not calling ZDICT_finalizeDictionary at all?

I'm happy with not providing statistics, but as per the OP, I would still like to provide a dictionary ID, to indicate in the zstd data that it is expecting a (raw) dictionary. While the spec suggests to me that this is possible, there's no API to combine a raw dictionary with a dictionary ID, right?

Or are you suggesting that if I'm using zstd raw dictionaries, I should also not specify a dictionary ID, and rely on the decompressor to know out-of-band which dictionary to use?

The idea of a "universal dictionary" has been a thing, and compared to "nothing" it was certainly a progress. But as we are improving our understanding of this technique, it becomes clear that this was just an intermediate stage, leaving a lot of capabilities on the table.

Sure, format-specific cooked dictionaries are better than format-agnostic raw dictionaries, but raw dictionaries are still better than no dictionaries, and I'd still like to get some data points on raw dictionaries.