Process ROL/ROR: rigorous testing

[arekbulski]

I am looking at the Reference Docs and it says clearly that there is ROL and ROR:
http://doc.kaitai.io/ksy_reference.html#process-rol

But the Python runtime has only ROL. Its not possible to use it with negative amount to simulate ROR.
https://github.com/kaitai-io/kaitai_struct_python_runtime/blob/master/kaitaistruct.py#L351

[arekbulski]

I sorta found out. In C# runtime, there is only ROL but there is a line that adjusts the amount with modulo 8 semantics to make it work both ways.
https://github.com/kaitai-io/kaitai_struct_csharp_runtime/blob/master/KaitaiStream.cs#L525

Python runtime doesnt have such a line, not sure if it works without it or not.

[GreyCat]

I just wonder what helds you from trying it out, or at least opening a process_rotate test and seeing what it compiles into for Python.

"Rotate right" can be always represented as "rotate left", so there's no need for two distinct operations. Conversion is done internally by ksc for all languages.

That C# runtime adjustments are actually somewhat misleading. Actually we just need to add something like amount = amount % 8 in every runtime (where % is module, and thus it's always results in non-negative number), so we can just use any integer number there.

[arekbulski]

Okay sorry, it just took me a while to figure how it works. Thank you for taking the time to explain, even if it was ultimately somewhat silly question... (eh baka...).

But it also seems that I found a bug. Python runtime does not have the modulo, therefore would not work properly when used with variable key and nagative values. I will fix it in kaitai-io/kaitai_struct_python_runtime#28 .

[GreyCat]

I guess we'll just need to add a ksy test for it which would test all cases like:

• "slightly negative" (like -3)
• "way too big positive" (like 1000)
• "way too big negative" (like -1000)

I don't really see why all of them should not work, and it's really easy to implement all these everywhere.

[arekbulski]

It might be a good idea to also have a test for rotating larger groups (more than 1 byte and more than 8 bytes). Would you want me to implement larger groups rotations in Python and C#? It seems that currently that feature is not implemented in neither runtime. Also note that rotating 8 bytes would use a different code path than arbitrary groups.

[GreyCat]

Rotating more than 1 byte groups is not implemented anywhere, that's right. You can start by:

1. Adding relevant tests
2. Doing implementation in runtimes

I'll add something like process: rol(amount, group_size) to compiler later.

[arekbulski]

Okie dokie, I will implement rotations in C# and Python. In C# its only up to 8 bytes groups, using ulong and shifts. In Python, since it supports bigint, I could make that arbitrary large groups.

Would it be acceptable for C# runtime to include BigInteger class? It would add a dependency on System.Numerics assembly which was added in .NET 4.0.

[GreyCat]

This is actually super messy matter ;) There are at least 2 ways to do these multi-byte group rotations:

• Using conversion to integers (or big integers), doing shifts there, and converting back
• Doing it inside the byte array with some special carry-on logic

Again, if we're striving for performance (and we are), ideally we'll need to try several approaches and see what would be most efficient. I bet that conversion to bigintegers and back should be much slower than doing in in-place.

[arekbulski]

Finished implementing the 2nd approach. PR at:
kaitai-io/kaitai_struct_python_runtime#28
Requested review of the code:
https://codereview.stackexchange.com/questions/191283/kaitai-struct-shift-rotate-1-byte-groups