samba.git/lib/compression, branch talloc-2.4.0

lib/compression: Fix length check

2023-01-10T20:22:32+00:00

Put the division on the correct side of the inequality.

Signed-off-by: Joseph Sutton 
Reviewed-by: Jeremy Allison

lib/compression: add simple python bindings

2022-12-22T19:50:33+00:00

There are four functions, allowing compression and decompression in
the two formats we support so far. The functions will accept bytes or
unicode strings which are treated as utf-8.

The LZ77+Huffman decompression algorithm requires an exact target
length to decompress, so this is mandatory.

The plain decompression algorithm does not need an exact length, but
you can provide one to help it know how much space to allocate. As
currently written, you can provide a short length and it will often
succeed in decompressing to a different shorter string.

These bindings are intended to make ad-hoc investigation easier, not
for production use. This is reflected in the guesses about output size
that plain_decompress() makes if you don't supply one -- either they
are stupidly wasteful or ridiculously insufficient, depending on
whether or not you were trying to decompress a 20MB string.

>>> a = '12345678'
>>> import compression
>>> b = compression.huffman_compress(a)
>>> b
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00  #....
>>> len(b)
262
>>> c = compression.huffman_decompress(b, len(a))
>>> c
b'12345678'                                   # note, c is bytes, a is str
>>> a
'12345678'
>>> d = compression.plain_compress(a)
>>> d
b'\xff\xff\xff\x0012345678'
>>> compression.plain_decompress(d)           # no size specified, guesses
b'12345678'
>>> compression.plain_decompress(d,5)
b'12345'
>>> compression.plain_decompress(d,0)         # 0 for auto
b'12345678'
>>> compression.plain_decompress(d,1)
b'1'
>>> compression.plain_decompress(a,444)
Traceback (most recent call last):
   compression.CompressionError: unable to decompress data into a buffer of 444 bytes.
>>> compression.plain_decompress(b,444)
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00 #...

That last one decompresses the Huffman compressed file with the plain
compressor; pretty much any string is valid for plain decompression.

Signed-off-by: Douglas Bagnall 
Reviewed-by: Jeremy Allison

compression/huffman: debug function bails upon disaster (CID 1517261)

2022-12-19T23:29:04+00:00

We shouldn't get a node with a zero code, and there's probably nothing
to do but stop.

   CID 1517261 (#1-2 of 2): Bad bit shift operation
   (BAD_SHIFT)11. negative_shift: In expression j >> offset - k,
   shifting by a negative amount has undefined behavior. The shift
   amount, offset - k, is -3.

Signed-off-by: Douglas Bagnall 
Reviewed-by: Jeremy Allison 

Autobuild-User(master): Jeremy Allison 
Autobuild-Date(master): Mon Dec 19 23:29:04 UTC 2022 on sn-devel-184

compression/huffman: double check distance in matches (CID 1517278)

2022-12-19T22:32:35+00:00

Because we just wrote the intermediate representation to have no zero
distances, we can be sure it doesn't, but Coverity doesn't know. If
distance is zero, `bitlen_nonzero_16(distance)` would be bad.

   CID 1517278 (#1 of 1): Bad bit shift operation
   (BAD_SHIFT)41. large_shift: In expression 1 << code_dist, left
   shifting by more than 31 bits has undefined behavior. The shift
   amount, code_dist, is 65535.

Signed-off-by: Douglas Bagnall 
Reviewed-by: Jeremy Allison

compression: fix sign extension of long matches (CID 1517275)

2022-12-19T22:32:35+00:00

Very long matches would be written instead as very very long matches.

We can't in fact hit this because we have a MAX_MATCH_LENGTH defined
as 64M, but if we could, it might make certain 2GB+ strings impossible
to compress.

  CID 1517275 (#1 of 1): Unintended sign extension
  (SIGN_EXTENSION)sign_extension: Suspicious implicit sign extension:
  intermediate[i + 2UL] with type uint16_t (16 bits, unsigned) is
  promoted in intermediate[i + 2UL] << 16 to type int (32 bits, signed),
  then sign-extended to type unsigned long (64 bits, unsigned). If
  intermediate[i + 2UL] << 16 is greater than 0x7FFFFFFF, the upper bits
  of the result will all be 1.

Signed-off-by: Douglas Bagnall 
Reviewed-by: Jeremy Allison

compression tests: avoid div by zero in failure (CID 1517297)

2022-12-19T22:32:35+00:00

Signed-off-by: Douglas Bagnall 
Reviewed-by: Jeremy Allison

compression/tests: calm the static analysts (CID: numerous)

2022-12-19T22:32:35+00:00

None of our test vectors are 18446744073709551615 bytes long, which
means we can know an `expected_length == returned_length` check will
catch the case where the compression function returns -1 for error. We
know that, but Coverity doesn't.

It's the same thing over and over again, in two different patterns:

>>>     CID 1517301:  Memory - corruptions  (OVERRUN)
>>>     Calling "memcmp" with "original.data" and "original.length" is
suspicious because of the very large index, 18446744073709551615. The index
may be due to a negative parameter being interpreted as unsigned.
393     	if (original.length != decomp_written ||
394     	    memcmp(decompressed.data,
395     		   original.data,
396     		   original.length) != 0) {
397     		debug_message("\033[1;31mgot %zd, expected %zu\033[0m\n",
398     			      decomp_written,

*** CID 1517299:  Memory - corruptions  (OVERRUN)
/lib/compression/tests/test_lzxpress_plain.c: 296 in
test_lzxpress_plain_decompress_more_compressed_files()
290     		debug_start_timer();
291     		written = lzxpress_decompress(p.compressed.data,
292     					      p.compressed.length,
293     					      dest,
294     					      p.decompressed.length);
295     		debug_end_timer("decompress", p.decompressed.length);
>>>     CID 1517299:  Memory - corruptions  (OVERRUN)
>>>     Calling "memcmp" with "p.decompressed.data" and
"p.decompressed.length" is suspicious because of the very large index,
18446744073709551615. The index may be due to a negative parameter being
interpreted as unsigned.
296     		if (written == p.decompressed.length &&
297     		    memcmp(dest, p.decompressed.data, p.decompressed.length)
== 0) {
298     			debug_message("\033[1;32mdecompressed %s!

Signed-off-by: Douglas Bagnall 
Reviewed-by: Jeremy Allison

compression/huffman: check again for invalid codes (CID 1517302)

2022-12-19T22:32:35+00:00

We know that code is non-zero, because it comes from the combination of
the intermediate representation and the symbol tables that were generated
at the same time. But Coverity doesn't know that, and it thinks we could
be doing undefined things in the subsequent shift.

    CID 1517302:  Integer handling issues  (BAD_SHIFT)
    In expression "1 << code_bit_len", shifting by a negative amount has

Signed-off-by: Douglas Bagnall 
Reviewed-by: Jeremy Allison

compression/huffman: tighten bit_len checks (fix SUSE -O3 build)

2022-12-19T22:32:35+00:00

The struct write_context bit_len attribute is always between 0 and 31,
but if the next patches are applied without this, SUSE GCC -O3 will
worry thusly:

 ../../lib/compression/lzxpress_huffman.c: In function
  ‘lzxpress_huffman_compress’:
 ../../lib/compression/lzxpress_huffman.c:953:5: error: assuming signed
  overflow does not occur when simplifying conditional to constant
  [-Werror=strict-overflow]
   if (wc->bit_len > 16) {
         ^
         cc1: all warnings being treated as errors

Inspection tell us that the invariant holds. Nevertheless, we can
safely use an unsigned type and insist that over- or under- flow is
bad.

Signed-off-by: Douglas Bagnall 
Reviewed-by: Jeremy Allison

compression/huffman: avoid semi-defined behaviour in decompress

2022-12-19T22:32:35+00:00

We had

               output[output_pos - distance];

where output_pos and distance are size_t and distance can be greater
than output_pos (because it refers to a place in the previous block).

The underflow is defined, leading to a big number, and when
sizeof(size_t) == sizeof(*uint8_t) the subsequent overflow works as
expected. But if size_t is smaller than a pointer, bad things will
happen.

This was found by OSSFuzz with
'UBSAN_OPTIONS=print_stacktrace=1:silence_unsigned_overflow=1'.

Credit to OSSFuzz.

Signed-off-by: Douglas Bagnall 
Reviewed-by: Volker Lendecke 
Reviewed-by: Jeremy Allison