Add function for max compressed size #71

New Issue

claunia · 2026-01-29T20:31:28Z

claunia commented

2026-01-29 20:31:28 +00:00

Originally created by @nemequ on GitHub (Dec 1, 2015).

Unless I'm missing something, Brotli doesn't include a function to calculate the maximum size of a compressed buffer given a specified input size (i.e., the brotli version of zlib's compressBound function).

I've been using uncompressed_size + 5 in squash, but that doesn't work with larger buffers. Based on some testing with blobs of random data, the points where the output size changes are:

Max input size	Max compressed extra bytes
64 KiB	4
8 MiB	5
9 MiB	8
16 MiB	9
24 MiB	13
???	16

24 MiB + 1 bytes requires input_size + 16, but I stopped testing there. For now I'm going to use uncompressed_size + 5 + ((uncompressed_size / (1024 * 1024 * 8)) * 4) in Squash, but I would feel better if you provided a function or macro.

Originally created by @nemequ on GitHub (Dec 1, 2015). Unless I'm missing something, Brotli doesn't include a function to calculate the maximum size of a compressed buffer given a specified input size (_i.e._, the brotli version of zlib's `compressBound` function). I've been using uncompressed_size + 5 in squash, but that doesn't work with larger buffers. Based on some testing with blobs of random data, the points where the output size changes are: <table> <thead> <tr> <th>Max input size</th> <th>Max compressed extra bytes</th> </tr> </thead> <tbody> <tr> <td>64 KiB</td> <td>4</td> </tr> <tr> <td>8 MiB</td> <td>5</td> </tr> <tr> <td>9 MiB</td> <td>8</td> </tr> <tr> <td>16 MiB</td> <td>9</td> </tr> <tr> <td>24 MiB</td> <td>13</td> </tr> <tr> <td>???</td> <td>16</td> </tr> </tbody> </table> 24 MiB + 1 bytes requires input_size + 16, but I stopped testing there. For now I'm going to use `uncompressed_size + 5 + ((uncompressed_size / (1024 * 1024 * 8)) * 4)` in Squash, but I would feel better if you provided a function or macro.

claunia closed this issue

2026-01-29 20:31:29 +00:00

claunia commented

2026-01-29 20:31:31 +00:00

@eustas commented on GitHub (Dec 2, 2015):

Yes, there is dependence between block size and maximum overhead.
I'll check the implementation and plan to add utility method to brotli encoder API.

@eustas commented on GitHub (Dec 2, 2015): Yes, there is dependence between block size and maximum overhead. I'll check the implementation and plan to add utility method to brotli encoder API.

claunia commented

2026-01-29 20:31:33 +00:00

@dsnet commented on GitHub (Dec 18, 2015):

Someone else can verify this work, but I believe this to be true.

In the worst case, when the data is highly uncompressible, the overhead comes from meta data to describe raw blocks. We compute the overhead by the followinG:

The stream header has:

7b  WINDOW_SIZE (best case is 1b, worst case is 7b. This setting is independent of input size)

The overhead to encode each raw block is:

1b           ISLAST
2b           MNIBBLES (4..6)
4b*MNIBBLES  MLEN (1..16777216)
1b           ISUNCOMPRESSED
7b           PADDING (may be less depending on bit alignment)
8b*MLEN      DATA

The last block has:

1b  ISLAST
1b  ISLASTEMPTY

Thus, we produce the following table:

Max input size (<=)	Max compressed extra bytes
65536	5
1048576	5
16777216	6
SIZE	1 + 5*⎡SIZE/16777216⎤ + 1

These numbers, of course, assume that the encoder falls back to using raw encoding when it detects that its compressed output is worse than just encoding it raw. I cannot confirm that the C encoder does this.

@dsnet commented on GitHub (Dec 18, 2015): Someone else can verify this work, but I believe this to be true. In the worst case, when the data is highly uncompressible, the overhead comes from meta data to describe raw blocks. We compute the overhead by the followinG: The stream header has: ``` 7b WINDOW_SIZE (best case is 1b, worst case is 7b. This setting is independent of input size) ``` The overhead to encode each raw block is: ``` 1b ISLAST 2b MNIBBLES (4..6) 4b*MNIBBLES MLEN (1..16777216) 1b ISUNCOMPRESSED 7b PADDING (may be less depending on bit alignment) 8b*MLEN DATA ``` The last block has: ``` 1b ISLAST 1b ISLASTEMPTY ``` Thus, we produce the following table: | Max input size (<=) | Max compressed extra bytes | | --- | --- | | 65536 | 5 | | 1048576 | 5 | | 16777216 | 6 | | SIZE | 1 + 5*⎡SIZE/16777216⎤ + 1 | These numbers, of course, assume that the encoder falls back to using raw encoding when it detects that its compressed output is worse than just encoding it raw. I cannot confirm that the C encoder does this.

claunia commented

2026-01-29 20:31:35 +00:00

@nemequ commented on GitHub (Dec 19, 2015):

FWIW I don't think it's a big deal if this isn't exact, as long as it always returns >= the number of bytes really required. Memory use shouldn't really be an issue here since if there is any concern about memory people should be using the streaming API. A lot of the plugins in Squash are actually pretty wide of the mark in their estimates.

@nemequ commented on GitHub (Dec 19, 2015): FWIW I don't think it's a big deal if this isn't exact, as long as it always returns >= the number of bytes really required. Memory use shouldn't really be an issue here since if there is any concern about memory people should be using the streaming API. A lot of the plugins in Squash are actually pretty wide of the mark in their estimates.

claunia commented

2026-01-29 20:31:37 +00:00

@nemequ commented on GitHub (Mar 5, 2016):

It seems level 1 is significantly worse about this. For example, a 935 byte buffer requires 119 extra bytes.

Do you consider that to be a bug? I don't really know how the encoder works… I can understand not wanting to spend the time checking for uncompressible data, but I can also see abandoning the idea of compression and just memcpying data being a good performance optimization.

@nemequ commented on GitHub (Mar 5, 2016): It seems level 1 is **significantly** worse about this. For example, a 935 byte buffer requires 119 extra bytes. Do you consider that to be a bug? I don't really know how the encoder works… I can understand not wanting to spend the time checking for uncompressible data, but I can also see abandoning the idea of compression and just memcpying data being a good performance optimization.

claunia commented

2026-01-29 20:31:38 +00:00

@dswd commented on GitHub (Mar 6, 2016):

The relevant commits seem to be 27688e6 and 417107b3dd.

@dswd commented on GitHub (Mar 6, 2016): The relevant commits seem to be 27688e6 and 417107b3ddb04cfd4ddfa7592fed0eb886186281.

claunia commented

2026-01-29 20:31:40 +00:00

@nemequ commented on GitHub (Jun 16, 2016):

0.5 provides BrotliEncoderMaxCompressedSize

@nemequ commented on GitHub (Jun 16, 2016): 0.5 provides `BrotliEncoderMaxCompressedSize`

claunia commented

2026-01-29 20:31:42 +00:00

@eustas commented on GitHub (Jun 16, 2016):

WARNING: this function result only applicable to BrotliEncoderCompress.
Stream compression may use more output. E.g. if compress with level 0 or level 1, every chunk of input is compressed independently -> adding more overhead.

I'm going to improve BrotliCompressStream behavior later and add another function for output size estimation.

@eustas commented on GitHub (Jun 16, 2016): WARNING: this function result only applicable to BrotliEncoderCompress. Stream compression may use more output. E.g. if compress with level 0 or level 1, every chunk of input is compressed independently -> adding more overhead. I'm going to improve BrotliCompressStream behavior later and add another function for output size estimation.

claunia commented

2026-01-29 20:31:43 +00:00

@nemequ commented on GitHub (Jun 16, 2016):

FWIW using the buffer to buffer API is all we commit to our max_compressed_size function working for in Squash, so this isn't a problem for me. Given all the complexities of estimating it with the stream API (like what happens if you flush every byte?), I don't think I would bother with that if I were you.

Note that zlib's function (compressBound) only applies to its buffer-to-buffer functions. I think all the others do the same, but I'd have to check…

@nemequ commented on GitHub (Jun 16, 2016): FWIW using the buffer to buffer API is all we commit to our max_compressed_size function working for in Squash, so this isn't a problem for me. Given all the complexities of estimating it with the stream API (like what happens if you flush every byte?), I don't think I would bother with that if I were you. Note that zlib's function (`compressBound`) only applies to its buffer-to-buffer functions. I think all the others do the same, but I'd have to check…

claunia referenced this issue

2026-01-29 20:50:13 +00:00

[PR #71] [MERGED] [python] fix unbuffered binary mode for I/O streams in Windows pypy #664

claunia referenced this issue

2026-01-29 20:50:15 +00:00

[PR #71] [python] fix unbuffered binary mode for I/O streams in Windows pypy #669

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: starred/brotli#71