Example
test build {
const literals_length_default_values = [36]u16{
5, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2,
3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 3, 2, 2, 2, 2, 2,
0, 0, 0, 0,
};
const match_lengths_default_values = [53]u16{
2, 5, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0,
0, 0, 0, 0, 0,
};
const offset_codes_default_values = [29]u16{
2, 2, 2, 2, 2, 2, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0,
};
var entries: [64]Table.Fse = undefined;
try build(&literals_length_default_values, &entries);
try std.testing.expectEqualSlices(Table.Fse, Table.predefined_literal.fse, &entries);
try build(&match_lengths_default_values, &entries);
try std.testing.expectEqualSlices(Table.Fse, Table.predefined_match.fse, &entries);
try build(&offset_codes_default_values, entries[0..32]);
try std.testing.expectEqualSlices(Table.Fse, Table.predefined_offset.fse, entries[0..32]);
}
Source
pub fn build(values: []const u16, entries: []Table.Fse) !void {
const total_probability = @as(u16, @intCast(entries.len));
const accuracy_log = std.math.log2_int(u16, total_probability);
assert(total_probability <= 1 << 9);
var less_than_one_count: usize = 0;
for (values, 0..) |value, i| {
if (value == 0) {
entries[entries.len - 1 - less_than_one_count] = Table.Fse{
.symbol = @as(u8, @intCast(i)),
.baseline = 0,
.bits = accuracy_log,
};
less_than_one_count += 1;
}
}
var position: usize = 0;
var temp_states: [1 << 9]u16 = undefined;
for (values, 0..) |value, symbol| {
if (value == 0 or value == 1) continue;
const probability = value - 1;
const state_share_dividend = std.math.ceilPowerOfTwo(u16, probability) catch
return error.MalformedFseTable;
const share_size = @divExact(total_probability, state_share_dividend);
const double_state_count = state_share_dividend - probability;
const single_state_count = probability - double_state_count;
const share_size_log = std.math.log2_int(u16, share_size);
for (0..probability) |i| {
temp_states[i] = @as(u16, @intCast(position));
position += (entries.len >> 1) + (entries.len >> 3) + 3;
position &= entries.len - 1;
while (position >= entries.len - less_than_one_count) {
position += (entries.len >> 1) + (entries.len >> 3) + 3;
position &= entries.len - 1;
}
}
std.mem.sort(u16, temp_states[0..probability], {}, std.sort.asc(u16));
for (0..probability) |i| {
entries[temp_states[i]] = if (i < double_state_count) Table.Fse{
.symbol = @as(u8, @intCast(symbol)),
.bits = share_size_log + 1,
.baseline = single_state_count * share_size + @as(u16, @intCast(i)) * 2 * share_size,
} else Table.Fse{
.symbol = @as(u8, @intCast(symbol)),
.bits = share_size_log,
.baseline = (@as(u16, @intCast(i)) - double_state_count) * share_size,
};
}
}
}