Documentation

There should exist a monoid homomorphism between natural number addition and function composition for shifts over a fixed bytestring argument.

There should exist a monoid homomorphism between integer addition and function composition for rotations over a fixed bytestring argument.

There should exist a monoid homomorphism between bytestring concatenation and natural number addition.

Shifting by more than the bit length (either positive or negative) clears the result.

Rotations by more than the bit length 'roll over' bits.

Rotations do not change how many set (and clear) bits there are.

Positive shifts clear low-index bits.

Negative shifts clear high-index bits.

Rotations move bits, but don't change them.

For any bytestring whose bit length is n and has k set bits, its complement should have n - k set bits.

The inclusion-exclusion principle: specifically, for any x and y, the number of set bits in x XOR y should be the number of set bits in x OR y minus the number of set bits in x AND y.

For any bytestring x, the number of set bits in x XOR x should be 0.

If we replicate any byte any (positive) number of times, the first set bit should be the same as in the case where we replicated it exactly once.

For any choice of bytestring, if we XOR it with itself, there should be no set bits; that is, finding the first set bit should give -1.

If we find a valid index for the first set bit, then:

1. The specified index should have a set bit; and
2. Any valid smaller index should have a clear bit.

We hack the generator slightly here to ensure we don't end up with all-zeroes (or the empty bytestring), as otherwise, the test wouldn't be meaningful.

Finding the first set bit in a bytestring with only zero bytes should always give -1.

If given Int minBound as an argument, shifts behave sensibly.

If given Int minBound as an argument, rotations behave sensibly.

Test for a regression found here.