Test a bit substring function

How do we test the following function?

bits(bitstring, i, j)

which returns a copy of the substring from i to j of some bitstring.

Consider the fixed 32-bit value:

bitstring=0x12345678

We could manually pre-determine the correct return values for ~500 different combinations of i and j. But this only covers 0x12345678.

There are 232 ≈ 4 billion different strings like 0x12345678.

Even for a non-exhaustive test, manually recording the constants we expect to get from any combination of (bitstring, i, j) does not seem like the best solution.

I imagine we can use the fact that bit strings map to unsigned integers and do some arithmetic to compare the return value of bits to bitstring.

Any help with vocabulary or classifying this validation problem would be appreciated, too.

Technical side note: My uncertainty lies in whether the bit manipulations are being performed correctly, since the bit substring does not necessarily begin or end on a byte boundary.

Another note: After a few edits I have realized the important question here is what are the different ways we can check that one bit string is a substring of another? But the original question has a broader scope so I will leave it as it is.

• I don't understand what your question/problem is. What would prevent you from testing this function? What does it even mean to test this function? I don't see why failing to begin on a byte boundary prevents testing. You test the function in the same way you test anything else: you identify some example inputs and the desired outputs, and you run the function on those inputs and see if it gives you the desired output. In this case it is a stateful interface so you have to look at sequences of operations, but the same techniques for testing stateful interfaces should work fine here.
– D.W.
Apr 5 '18 at 0:18
• Thanks @D.W. for pointing that out. I tried to make the question clearer. The byte boundaries don't prevent me from testing, but they're one of the reasons I'm uncertain about this function working for any value that I don't explicitly test ahead of time. Apr 5 '18 at 20:54
• OK, see my updated answer.
– D.W.
Apr 5 '18 at 21:03
• Also, @D.W. I assume when you say "stateful interface" it simply means what it sounds like it means (in this case, that bits() maintains information about the stream from call to call). I google'd it and the top results are referring me to Salesforce and Cisco pages, which is oddly specific for such a general sounding term. Apr 5 '18 at 21:06
• Yes, that's right. I might have been wrong about my assumption that this is stateful: after your edits, it sounds like the byte stream comes from the first argument. If so, please disregard my comments about stateful interfaces as this doesn't appear to be stateful.
– D.W.
Apr 5 '18 at 21:11

You test the function in the same way you test anything else: you identify some example inputs and the desired outputs, and you run the function on those inputs and see if it gives you the desired output. You can still do that despite "not falling on a byte boundary".

In this case the function bits is a stateful interface, so you have to deal with that, but the same techniques for testing stateful interfaces should work fine here. In particular, the "input" is a sequence of operations on the data structure / API, and the "output" is the sequence of results from those operations. For instance, the first operation might be to set the contents of the underlying byte stream, and the second operation might be to invoke bits().

I'm not sure where you're getting $512 \times 2^{32}$ from (presumably you mean $32 \times 2^{32}$), and those aren't permutations; but in any case that doesn't change anything. Testing almost never exhaustively tries all combinations. I don't see why this would be any different. Instead, the idea behind testing is that we try a small fraction of the possibilities, and if there is a bug, we hope that one of the test cases we try will expose it. This doesn't provide any guarantees, since there could always be a bug that only triggers on one of the test cases we didn't try -- testing is not verification, and does not prove correctness -- but it is useful nonetheless.

So, nothing prevents you from testing this function. Standard methods work fine.

• There are 2^32 bit permutations of length 32. From each of these permutations we can take (32-choose-2) [with repetition] = 512 different substrings of length n=1..32. Apr 5 '18 at 21:10
• @Marin, that's not what a permutation is. I don't see how your interface lets you pick any of the 32-choose-2 possibilities; that would require a start index and a stop index, whereas I see only a stop index. 32-choose-2 is 496, not 512.
– D.W.
Apr 5 '18 at 21:13
• You're probably right about that. I am a first year undergrad and very prone to misusing terms. I edited the question so it's less relevant. Apr 5 '18 at 22:25
• Apparently I was looking for something closer to proof or verification than a test. Thanks for the clarification. I will have to look around some more and possibly open a new question about bit string verification, but this does answer the original question! Apr 5 '18 at 22:30