scality
Compact format for blocks with metadata
It focuses on FNT(q = 2^p + 1).
Given a block of n symbols of FNT(q), a metadata part should indicate indices of all symbols whose value = 2^p.
If these symbols are uniformly distributed, we can use the frequency of 2^p to determine the size of metadata.
For general cases, the naive approach needs n indicators for n elements, i.e. metadata size = n.
For FNT(65537), the following approach results to metadata of only one indicator.
The indicator contains the index, e.g. i, of the first symbol = 2^p. Then the ith symbol will be used to contain index of the next symbol 2^p, and so on. If there is no more symbol 2^p, this symbol will be zero.
Example, data = [1, 2, 65536, 3, 4, 65536, 5, 6, 7] => metadata = [2] data = [1, 2, 5, 3, 4, 0, 5, 6, 7]
The approach can be used for FNT(257) for n < 257.
