mirror of
https://github.com/chylex/Brotli-Builder.git
synced 2024-11-24 22:42:50 +01:00
320 lines
14 KiB
C#
320 lines
14 KiB
C#
using System;
|
|
using System.Collections.Generic;
|
|
using System.Linq;
|
|
using BrotliLib.Brotli.Components;
|
|
using BrotliLib.Brotli.Components.Compressed;
|
|
using BrotliLib.Brotli.Components.Data;
|
|
using BrotliLib.Brotli.Components.Header;
|
|
using BrotliLib.Brotli.Dictionary.Index;
|
|
using BrotliLib.Brotli.Parameters;
|
|
using BrotliLib.Brotli.Parameters.Heuristics;
|
|
using BrotliLib.Brotli.Utils;
|
|
using BrotliLib.Collections;
|
|
using static BrotliLib.Brotli.Utils.DistanceCodeZeroStrategy;
|
|
|
|
namespace BrotliLib.Brotli.Encode.Build{
|
|
public sealed class CompressedMetaBlockBuilder{
|
|
public CategoryMap<BlockSwitchBuilder> BlockTypes { get; } = BlockTypeInfo.Empty.Select(info => new BlockSwitchBuilder(info));
|
|
public DistanceParameters DistanceParameters { get; set; } = DistanceParameters.Zero;
|
|
|
|
public LiteralContextMode[] LiteralContextModes { get; set; } = { LiteralContextMode.LSB6 };
|
|
public ContextMap LiteralCtxMap { get; set; } = ContextMapBuilder.Literals.Simple;
|
|
public ContextMap DistanceCtxMap { get; set; } = ContextMapBuilder.Distances.Simple;
|
|
|
|
public IReadOnlyList<InsertCopyCommand> InsertCopyCommands => commands;
|
|
|
|
public int OutputSize => intermediateState.OutputSize - initialState.OutputSize;
|
|
public int LastDistance => intermediateState.DistanceBuffer.Front;
|
|
|
|
private InsertCopyCommand? FinalInsertCommand{
|
|
get{
|
|
int count = commands.Count;
|
|
|
|
if (count == 0){
|
|
return null;
|
|
}
|
|
|
|
var lastCommand = commands[count - 1];
|
|
return lastCommand.CopyDistance == DistanceInfo.EndsAfterLiterals ? lastCommand : null;
|
|
}
|
|
}
|
|
|
|
// Fields
|
|
|
|
private readonly List<InsertCopyCommand> commands = new List<InsertCopyCommand>();
|
|
private int totalLiterals;
|
|
private int totalExplicitDistances;
|
|
|
|
private readonly BrotliGlobalState initialState;
|
|
private readonly BrotliGlobalState intermediateState;
|
|
|
|
// Construction
|
|
|
|
public CompressedMetaBlockBuilder(BrotliGlobalState state){
|
|
this.initialState = state.Clone();
|
|
this.intermediateState = state.Clone();
|
|
}
|
|
|
|
public CompressedMetaBlockBuilder(BrotliFileParameters parameters) : this(new BrotliGlobalState(parameters)){}
|
|
|
|
public CompressedMetaBlockBuilder(MetaBlock.Compressed metaBlock, BrotliGlobalState state) : this(state){
|
|
var header = metaBlock.Header;
|
|
var data = metaBlock.Data;
|
|
|
|
this.BlockTypes = header.BlockTypes.Select(info => new BlockSwitchBuilder(info, data.BlockSwitchCommands[info.Category]));
|
|
this.DistanceParameters = header.DistanceParameters;
|
|
this.LiteralContextModes = header.LiteralCtxModes.ToArray();
|
|
this.LiteralCtxMap = header.LiteralCtxMap;
|
|
this.DistanceCtxMap = header.DistanceCtxMap;
|
|
|
|
foreach(InsertCopyCommand command in data.InsertCopyCommands){
|
|
AddInsertCopyCommand(command);
|
|
}
|
|
}
|
|
|
|
// General
|
|
|
|
public int GetTotalBlockLength(Category category){
|
|
return category switch{
|
|
Category.Literal => totalLiterals,
|
|
Category.InsertCopy => commands.Count,
|
|
Category.Distance => totalExplicitDistances,
|
|
_ => throw new InvalidOperationException("Invalid category: " + category)
|
|
};
|
|
}
|
|
|
|
public CompressedMetaBlockBuilder UseSameLiteralContextMode(LiteralContextMode mode){
|
|
LiteralContextModes = Enumerable.Repeat(mode, BlockTypes[Category.Literal].TypeCount).ToArray();
|
|
return this;
|
|
}
|
|
|
|
// Commands
|
|
|
|
public CompressedMetaBlockBuilder AddInsertCopyCommand(InsertCopyCommand command){
|
|
var literals = command.Literals;
|
|
var distance = command.CopyDistance;
|
|
|
|
var finalInsertCommand = FinalInsertCommand;
|
|
|
|
if (finalInsertCommand != null){
|
|
commands[^1] = new InsertCopyCommand(finalInsertCommand.Literals.Concat(literals).ToList(), command.CopyLength, distance); // silently merge with previous command
|
|
}
|
|
else{
|
|
commands.Add(command);
|
|
}
|
|
|
|
intermediateState.OutputLiterals(literals);
|
|
|
|
if (distance != DistanceInfo.EndsAfterLiterals){
|
|
intermediateState.OutputCopy(command.CopyLength, distance);
|
|
}
|
|
|
|
totalLiterals += literals.Count;
|
|
|
|
if (distance.HasExplicitDistanceCode()){
|
|
totalExplicitDistances++;
|
|
}
|
|
|
|
return this;
|
|
}
|
|
|
|
public CompressedMetaBlockBuilder AddInsert(IList<Literal> literals){
|
|
return AddInsertCopyCommand(new InsertCopyCommand(literals));
|
|
}
|
|
|
|
public CompressedMetaBlockBuilder AddInsertCopy(IList<Literal> literals, int copyLength, DistanceInfo copyDistance){
|
|
return AddInsertCopyCommand(new InsertCopyCommand(literals, copyLength, copyDistance));
|
|
}
|
|
|
|
public CompressedMetaBlockBuilder AddInsertCopy(IList<Literal> literals, int copyLength, int copyDistance, DistanceCodeZeroStrategy dczStrategy = PreferImplicit){
|
|
if (copyDistance == LastDistance){
|
|
var literalsToMerge = FinalInsertCommand?.Literals.Count ?? 0;
|
|
return AddInsertCopyCommand(new InsertCopyCommand(literals, copyLength, dczStrategy.Decide(literals.Count + literalsToMerge, copyLength, copyDistance)));
|
|
}
|
|
else{
|
|
return AddInsertCopyCommand(new InsertCopyCommand(literals, copyLength, copyDistance));
|
|
}
|
|
}
|
|
|
|
public CompressedMetaBlockBuilder AddInsertCopy(IList<Literal> literals, in DictionaryIndexEntry dictionaryEntry, DistanceCodeZeroStrategy dczStrategy = PreferImplicit){
|
|
var startDistance = 1 + Math.Min(intermediateState.Parameters.WindowSize.Bytes, intermediateState.OutputSize + literals.Count);
|
|
var entryDistance = dictionaryEntry.Packed + startDistance;
|
|
|
|
return AddInsertCopy(literals, dictionaryEntry.CopyLength, entryDistance, dczStrategy);
|
|
}
|
|
|
|
public CompressedMetaBlockBuilder AddCopy(int copyLength, DistanceInfo copyDistance){
|
|
return AddInsertCopy(Array.Empty<Literal>(), copyLength, copyDistance);
|
|
}
|
|
|
|
public CompressedMetaBlockBuilder AddCopy(int copyLength, int copyDistance, DistanceCodeZeroStrategy dczStrategy = PreferImplicit){
|
|
return AddInsertCopy(Array.Empty<Literal>(), copyLength, copyDistance, dczStrategy);
|
|
}
|
|
|
|
public CompressedMetaBlockBuilder AddCopy(in DictionaryIndexEntry dictionaryEntry, DistanceCodeZeroStrategy dczStrategy = PreferImplicit){
|
|
return AddInsertCopy(Array.Empty<Literal>(), in dictionaryEntry, dczStrategy);
|
|
}
|
|
|
|
// Building
|
|
|
|
public (MetaBlock.Compressed MetaBlock, BrotliEncodeInfo NextInfo) Build(BrotliEncodeInfo info, BrotliCompressionParameters? parameters = null){
|
|
var (metaBlock, nextState) = Build(parameters ?? info.CompressionParameters);
|
|
return (metaBlock, info.WithProcessedBytes(nextState, OutputSize));
|
|
}
|
|
|
|
public (MetaBlock.Compressed MetaBlock, BrotliGlobalState NextState) Build(BrotliCompressionParameters parameters){
|
|
var state = initialState.Clone();
|
|
|
|
// Setup
|
|
|
|
var blockTypes = BlockTypes.Select(builder => builder.Build(GetTotalBlockLength(builder.Category), parameters));
|
|
var blockTrackers = blockTypes.Select(built => new BlockSwitchTracker.Simulating(built.Info, built.Commands));
|
|
|
|
var literalFreq = FrequencyList<Literal>.Array(LiteralCtxMap.TreeCount);
|
|
var icLengthCodeFreq = FrequencyList<InsertCopyLengthCode>.Array(blockTypes[Category.InsertCopy].Info.TypeCount);
|
|
var distanceCodeFreq = FrequencyList<DistanceCode>.Array(DistanceCtxMap.TreeCount);
|
|
|
|
var icCommandCount = commands.Count;
|
|
var icCommandsFinal = new InsertCopyCommand[icCommandCount];
|
|
|
|
// Early validation
|
|
|
|
if (icCommandCount == 0){
|
|
throw new InvalidOperationException("Cannot build a compressed meta-block with no insert© commands.");
|
|
}
|
|
|
|
if (LiteralContextModes.Length != blockTypes[Category.Literal].Info.TypeCount){
|
|
throw new InvalidOperationException("Literal context mode array size must match the amount of literal block types (" + LiteralContextModes.Length + " != " + blockTypes[Category.Literal].Info.TypeCount + ").");
|
|
}
|
|
|
|
if (LiteralCtxMap.BlockTypes != blockTypes[Category.Literal].Info.TypeCount){
|
|
throw new InvalidOperationException("Literal context map size is incorrect for the amount of literal block types.");
|
|
}
|
|
|
|
if (DistanceCtxMap.BlockTypes != blockTypes[Category.Distance].Info.TypeCount){
|
|
throw new InvalidOperationException("Distance context map size is incorrect for the amount of distance block types.");
|
|
}
|
|
|
|
// Command processing
|
|
|
|
var validDistanceCodes = new List<DistanceCode>(5);
|
|
|
|
for(int icIndex = 0; icIndex < icCommandCount; icIndex++){
|
|
var icCommand = commands[icIndex];
|
|
int icBlockID = blockTrackers[Category.InsertCopy].Advance();
|
|
var icFreq = icLengthCodeFreq[icBlockID];
|
|
|
|
for(int literalIndex = 0; literalIndex < icCommand.Literals.Count; literalIndex++){
|
|
var literal = icCommand.Literals[literalIndex];
|
|
|
|
int blockID = blockTrackers[Category.Literal].Advance();
|
|
int contextID = state.NextLiteralContextID(LiteralContextModes[blockID]);
|
|
int treeID = LiteralCtxMap.DetermineTreeID(blockID, contextID);
|
|
|
|
literalFreq[treeID].Add(literal);
|
|
state.OutputLiteral(literal);
|
|
}
|
|
|
|
InsertCopyLengths icLengthValues = icCommand.Lengths;
|
|
InsertCopyLengthCode icLengthCode;
|
|
|
|
if (icCommand.CopyDistance == DistanceInfo.EndsAfterLiterals){
|
|
if (icIndex != icCommandCount - 1){
|
|
throw new InvalidOperationException("Insert© command that ends after literals must be the last.");
|
|
}
|
|
|
|
icLengthCode = icLengthValues.MakeCode(ImplicitDistanceCodeZero.PreferEnabled);
|
|
|
|
if (icLengthCode.UseDistanceCodeZero){
|
|
var alternativeCode = icLengthValues.MakeCode(ImplicitDistanceCodeZero.Disable);
|
|
|
|
if (icFreq[alternativeCode] > icFreq[icLengthCode]){
|
|
icLengthCode = alternativeCode; // if the first code uses DCZ, try a non-DCZ code and pick whichever one was used more often
|
|
}
|
|
}
|
|
}
|
|
else{
|
|
if (!icCommand.CopyDistance.FindCodes(DistanceParameters, state, validDistanceCodes)){
|
|
icLengthCode = icLengthValues.MakeCode(ImplicitDistanceCodeZero.ForceEnabled);
|
|
}
|
|
else{
|
|
int blockID = blockTrackers[Category.Distance].Advance();
|
|
int contextID = icLengthValues.DistanceContextID;
|
|
int treeID = DistanceCtxMap.DetermineTreeID(blockID, contextID);
|
|
|
|
var distanceFreq = distanceCodeFreq[treeID];
|
|
DistanceCode distanceCode;
|
|
|
|
if (icCommand.CopyDistance == DistanceInfo.ExplicitCodeZero){
|
|
distanceCode = DistanceCode.Zero;
|
|
}
|
|
else{
|
|
distanceCode = validDistanceCodes.Count > 1 ? parameters.DistanceCodePicker(validDistanceCodes, distanceFreq) : validDistanceCodes[0];
|
|
|
|
if (distanceCode.Equals(DistanceCode.Zero)){
|
|
throw new InvalidOperationException("Cannot pick distance code zero for an insert© command that does not explicitly request it.");
|
|
}
|
|
}
|
|
|
|
distanceFreq.Add(distanceCode);
|
|
icLengthCode = icLengthValues.MakeCode(ImplicitDistanceCodeZero.Disable);
|
|
}
|
|
|
|
state.OutputCopy(icCommand.CopyLength, icCommand.CopyDistance);
|
|
}
|
|
|
|
icFreq.Add(icLengthCode);
|
|
icCommandsFinal[icIndex] = icCommand;
|
|
}
|
|
|
|
// Finalize
|
|
|
|
foreach(var literalList in literalFreq){
|
|
if (literalList.Count == 0){
|
|
literalList.Add(new Literal(0));
|
|
}
|
|
}
|
|
|
|
foreach(var icLengthCodeList in icLengthCodeFreq){
|
|
if (icLengthCodeList.Count == 0){
|
|
icLengthCodeList.Add(new InsertCopyLengthCode(0));
|
|
}
|
|
}
|
|
|
|
foreach(var distanceCodeList in distanceCodeFreq){
|
|
if (distanceCodeList.Count == 0){
|
|
distanceCodeList.Add(DistanceCode.Zero);
|
|
}
|
|
}
|
|
|
|
var header = new CompressedHeader(
|
|
blockTypes.Select(built => built.Info),
|
|
DistanceParameters,
|
|
LiteralContextModes,
|
|
LiteralCtxMap,
|
|
DistanceCtxMap,
|
|
ConstructHuffmanTrees(literalFreq, parameters.GenerateLiteralTree),
|
|
ConstructHuffmanTrees(icLengthCodeFreq, parameters.GenerateLengthCodeTree),
|
|
ConstructHuffmanTrees(distanceCodeFreq, parameters.GenerateDistanceCodeTree)
|
|
);
|
|
|
|
var data = new CompressedData(icCommandsFinal, blockTypes.Select(built => built.Commands));
|
|
var dataLength = new DataLength(OutputSize);
|
|
|
|
return (new MetaBlock.Compressed(dataLength, header, data), state);
|
|
}
|
|
|
|
// Helpers
|
|
|
|
private static HuffmanTree<T>[] ConstructHuffmanTrees<T>(FrequencyList<T>[] source, HuffmanTreeHeuristics.Generate<T> generator) where T : IComparable<T>{
|
|
HuffmanTree<T>[] array = new HuffmanTree<T>[source.Length];
|
|
|
|
for(int index = 0; index < array.Length; index++){
|
|
array[index] = generator(source[index]);
|
|
}
|
|
|
|
return array;
|
|
}
|
|
}
|
|
}
|