BrotliEncoder.GetMaxCompressedLength returns invalid value

[TechPizzaDev]

Project target: netcoreapp3.1

Test code

using System;
using System.IO.Compression;

namespace Sandbox
{
 class Program
 {
 static void Main(string[] args)
 {
 const int quality = 5;
 const int window = 10;

 byte[] source = new byte[256000];
 var rng = new Random(1234);
 rng.NextBytes(source);

 int maxLength = BrotliEncoder.GetMaxCompressedLength(source.Length);
 var resultBuffer = new byte[maxLength + 10];

 if (!BrotliEncoder.TryCompress(
 source, resultBuffer, out int written1, quality, window))
 throw new Exception();

 if (!BrotliEncoder.TryCompress(
 source, resultBuffer.AsSpan(0, maxLength), out int written2, quality, window))
 throw new Exception();
 }
 }
}

dotnet --info

.NET Core SDK (reflecting any global.json):
 Version: 3.1.201
 Commit: b1768b4ae7

Runtime Environment:
 OS Name: Windows
 OS Version: 10.0.18363
 OS Platform: Windows
 RID: win10-x64
 Base Path: C:\Program Files\dotnet\sdk\3.1.201\

Host (useful for support):
 Version: 3.1.3
 Commit: 4a9f85e9f8

.NET Core SDKs installed:
 2.1.700 [C:\Program Files\dotnet\sdk]
 2.1.701 [C:\Program Files\dotnet\sdk]
 2.1.801 [C:\Program Files\dotnet\sdk]
 2.1.802 [C:\Program Files\dotnet\sdk]
 2.2.300 [C:\Program Files\dotnet\sdk]
 3.1.201 [C:\Program Files\dotnet\sdk]

.NET Core runtimes installed:
 Microsoft.AspNetCore.All 2.1.11 [C:\Program Files\dotnet\shared\Microsoft.AspNetCore.All]
 Microsoft.AspNetCore.All 2.1.12 [C:\Program Files\dotnet\shared\Microsoft.AspNetCore.All]
 Microsoft.AspNetCore.All 2.1.13 [C:\Program Files\dotnet\shared\Microsoft.AspNetCore.All]
 Microsoft.AspNetCore.All 2.2.5 [C:\Program Files\dotnet\shared\Microsoft.AspNetCore.All]
 Microsoft.AspNetCore.App 2.1.11 [C:\Program Files\dotnet\shared\Microsoft.AspNetCore.App]
 Microsoft.AspNetCore.App 2.1.12 [C:\Program Files\dotnet\shared\Microsoft.AspNetCore.App]
 Microsoft.AspNetCore.App 2.1.13 [C:\Program Files\dotnet\shared\Microsoft.AspNetCore.App]
 Microsoft.AspNetCore.App 2.2.5 [C:\Program Files\dotnet\shared\Microsoft.AspNetCore.App]
 Microsoft.AspNetCore.App 3.1.3 [C:\Program Files\dotnet\shared\Microsoft.AspNetCore.App]
 Microsoft.NETCore.App 2.1.11 [C:\Program Files\dotnet\shared\Microsoft.NETCore.App]
 Microsoft.NETCore.App 2.1.12 [C:\Program Files\dotnet\shared\Microsoft.NETCore.App]
 Microsoft.NETCore.App 2.1.13 [C:\Program Files\dotnet\shared\Microsoft.NETCore.App]
 Microsoft.NETCore.App 2.2.5 [C:\Program Files\dotnet\shared\Microsoft.NETCore.App]
 Microsoft.NETCore.App 3.1.3 [C:\Program Files\dotnet\shared\Microsoft.NETCore.App]
 Microsoft.WindowsDesktop.App 3.1.3 [C:\Program Files\dotnet\shared\Microsoft.WindowsDesktop.App]

Tagging subscribers to this area:
Notify danmosemsft if you want to be subscribed.

[lcsondes]

Just hit this one in my code, can confirm. I'm getting a compressed buffer (using new BrotliEncoder(9, 22).Compress(...)) of 0x0040000c length (the input is exactly 0x00400000 bytes) when the expected maximum is 0x00400007.

[danmoseley]

Interested in debugging some @lcsondes ?

[lcsondes]

@danmosemsft What do you need?

[danmoseley]

@lcsondes it may be some time before someone can take a look, so sometimes I ask folks whether they’re interested in investigating to figure out the root cause.

[lcsondes]

From skimming the source my best guess is this line hardcoding the largest possible large block size while the BrotliEncoder constructor lets you select any window size. The guesswork here is whether the two are related, RFC 7932 doesn't seem to talk about large blocks but it does mention meta-blocks that have a variable size which just so happens to range between 0 and 16M and its header contains the size of the window so there could be a connection.

On the other hand if I take my input size which is 4M, 4M>>24 is 0 (which also looks incorrect BTW, surely there must be at least one block if the input is meaningful?) but that only explains 4 bytes of difference. The most I've observed was 6.

[neuecc]

I've encounted same issue.
brotli/encode.c has BrotliEncoderMaxCompressedSize method, that returns different value of current C# impl.
https://github.com/google/brotli/blob/3914999fcc1fda92e750ef9190aa6db9bf7bdb07/c/enc/encode.c#L1200
I've port this code to C# and compare result.

int BrotliEncoderMaxCompressedSize(int input_size)
{
 var num_large_blocks = input_size >> 14;
 var overhead = 2 + (4 * num_large_blocks) + 3 + 1;
 var result = input_size + overhead;
 if (input_size == 0) return 2;
 return (result < input_size) ? 0 : result;
}

My test data,

Input	10000005
GetMaxCompressedLength	10000012
BrotliEncoderMaxCompressedSize	10002451
Compressed	10000021

I think this is a critical issue of compression library, could you fix it?

[neuecc]

@carlossanlop
.NET 8 doesn't seem to have any changes, should this remain a TODO?

[lcsondes]

For the poor souls who are still affected by this, I recommend switching over to zstd, which is unaffected by this bug, and generally has a better runtime performance and compression ratio.

It's unlikely that this one will be fixed in anytime soon, it's been open for more than 3 years.

[neuecc]

.NET 9 RC1 supports new BrotliCompressionOptions in #105430 , however this bug is not cared,
I've tested in latest VS-preview but still exists.
@buyaa-n , @carlossanlop , @stephentoub (mentioned to #105430 reviewers)

[buyaa-n]

.NET 9 RC1 supports new BrotliCompressionOptions in #105430 , however this bug is not cared,

That was not about for fixing this issue.

Anyway the managed implementation of GetMaxCompressedLength(int inputSize) was the same as the native implementation until native code updated with Update brotli to v1.0.5. Wonder why did not use the native implementation directly, anyway this is a regression happened a few years back.

Question is how to fix it:

• Should we just apply the native changes to the managed implementation
• Or should we update it to call native method directly (it could prevent from similar issue happen again)

CC @carlossanlop @ericstj @stephentoub