last day (14 days later) » 

11:32 AM
2
A: Extracting continuos bits from a std::string bytewise with a bit offset

SmeeheeyTo do it byte-wise, just read the string (which BTW it is better to interpret as a sequence of uint8_t rather than char) one byte at a time, updating your result by shifting it left 8 and oring it with the current byte. The only complications are the first bit and the last bit, which both require...

 
i like this division of the problem, this will work ill do some tests later today
hm this code didn't work it shuffles the bytes wrong, endianness is destroyed. uint64_t nMask = 0xFFFFFFFFFFFFFFFFULL; uint64_t nPattern = 0xFFFEFDFCFBFAF9F8ULL; uint64_t nPattern2 = 0xFAAAAAAAAAAAAAFFULL; EXPECT_EQ( nPattern, ExtractField( 0, 64, (uint8_t*)&nPattern) ); EXPECT_EQ( nMask >> 1, ExtractField( 1, 63, (uint8_t*)&nMask) ); EXPECT_EQ( nPattern >> 1, ExtractField( 1, 63, (uint8_t*)&nPattern) ); EXPECT_EQ( nPattern2 >> 1, ExtractField( 1, 63, (uint8_t*)&nPattern2) );
 
Well OK, but you didn't specify the endianess of your input (str.c_str()) and I assumed it was network byte order. I guess you're saying the data is little endian instead?
 
yeah i expected it to just come out in the order i put it in (endianess i would have handled after the extraction with a swap), espacially with bits offset it needs to be read directly without rearraging bytes as this will not only destroy the endianess but also the data.
 
How exactly did you 'put it in'?
Because you see, big-endian (i.e. my implementation) IS reading the bits directly as they are put in, its little endian that would require fiddling
 
see the unit test cases above the first parameter is the offset, then length then the pattern, ill need todo some more debugging to figure out how to copy it out directly.
 
11:32 AM
Ahh, I see. Is your real-life data presented to you in the same way, or is this just for a test? The norm for this kind of encoding is actually big-endian, that's why I'm asking. You can easily modify your test to produce big-endian input by the way, I can show you how if needs be
 
yeah in fact the byte order is not defined, it depends its a generalized packet field extraction, yeah if you have an idea for keeping the byte order the same i'd like to know. But it is still wrong Endianess defines Byteorder not Bitorder, but when using a bit offset one can not work on assuming another byteorder.
 
Change your unit tests along these lines (note: you will need #include <endian.h>): ...; uint64_t nPattern = 0xFFFEFDFCFBFAF9F8ULL; uint64_t be_nPattern = htobe64(nPattern); EXPECT_EQ(nPattern, ExtractField(0, 64, (uint8_t*)&be_nPattern); ....
Note also you're doing something dodgy in treating a uint64_t as a sequence of uint8_t. Technically this is undefined behaviour. It would be better to explicitly create an std::array<uint8_t, 8> say, initialise it byte-wise with big-endian order, then compare it to your expected uint64_t result (defined separately)
In your case that would be std::array<uint8_t, 8> be_nPattern = {0xFF, 0xFE, 0xFD, 0xFC, 0xFB, 0xFA, 0xF9, 0xF8};
 
even after a swap of the 64bits the result is still wrong, it just doesnt take into account that bits also move between bytes in the middle case (when its not the end or start byte)
 
Give me an example where it is wrong, specifically
 
/** @brief Extract field (assumption bitlength+offset is prechecked against stringlength)
* @param nBitOffset (Range 0-7, greater ranges work as well, handled by byteoffset)
* @param nBitLen (Max: 64)
* @param sSource
*/
uint64_t ExtractField( unsigned nBitOffset, unsigned nBitLen, const uint8_t* sSource )
{
    unsigned _nByteOffset = nBitOffset / 8;
    uint8_t  _nBitOffset = nBitOffset % 8;

    uint64_t nResult = 0ULL;
    uint8_t nMask = 0xFF;

    sSource += _nByteOffset;

    // First byte
and the test cases
TEST(A_Field, can_be_extracted_correctly )
{
    uint64_t nMask      = 0xFFFFFFFFFFFFFFFFULL;
    uint64_t nPattern   = 0xFFFEFDFCFBFAF9F8ULL;
    uint64_t nPattern2  = 0xFAAAAAAAAAAAAAFFULL;

    uint64_t nPattern3  = 0xF0A0000000000000ULL;
    EXPECT_EQ( nPattern3 >> 2, ExtractField( 1, 62, (uint8_t*)&nPattern3) );

    EXPECT_EQ( nPattern, ExtractField( 0, 64, (uint8_t*)&nPattern) );

    EXPECT_EQ( nMask >> 1, ExtractField( 1, 63, (uint8_t*)&nMask) );
    EXPECT_EQ( nPattern >> 1, ExtractField( 1, 63, (uint8_t*)&nPattern) );
and the test result
_gtest.cpp:171
Value of: ExtractField( 1, 62, (uint8_t*)&nPattern3)
Actual: 20600
Expected: nPattern3 >> 2
Which is: 4334714641344102400

_gtest.cpp:176
Value of: ExtractField( 1, 63, (uint8_t*)&nPattern)
Actual: 8717274513940545279
Expected: nPattern >> 1
Which is: 9223230193378622716

_gtest.cpp:177
Value of: ExtractField( 1, 63, (uint8_t*)&nPattern2)
Actual: 9199352838842133242
Expected: nPattern2 >> 1
Which is: 9031218452753634687

_gtest.cpp:180
Value of: ExtractField( 1, 62, (uint8_t*)&nPattern)
when i compare the bit patterns it works for a pattern such as just all bits sets, but once actual data is present it just fails and doesnt provide the same result
also see the fast-branches i added those are how i would see the other code working as well
the problem is just the cases when the bits are offset
 
12:01 PM
So lets look at your pattern3 test
Here is live code that implements it correctly. As you can see the results are correct
For the nPattern3 test, you need to change the EXPECT_EQ line to:
h
uint64_t expectedResult = (nPattern3 & (nMask >> 1)) >> 1; std::array<uint8_t, 8> input = {0xF0, 0xA0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}; EXPECT_EQ(expectedResult, ExtractField(1, 62, (uint8_t*)(input.data()));
Sorry I don't know how to format code properly in chat
 
yeah i noticed that as well the first test was off by a bti
i was looking into maybe to work with first copying into 2x64 bit and working with those and ORing them in the end
 
What I'm saying is the logic for my solution works correctly - it is your test case input that is wrong. Do you agree with this?
 
the thing remains that the compiler surely doesnt reorder the bytes when i cast the uint64_t to a char* and pass it through the function yet the function reorders the bytes and thus it doesnt work, my test cases are that input and output are the same and that there can be postprocessing after
 
Those are test cases - but what is your REAL case? Do you receive the data over the network for example? How is the original source data serialised?
 
all of the testcases except that one i just added to easier check the result (pattern 3) are correct
there isnt an original source its a generalized protocol implementation it can be either way
 
12:13 PM
So how is the source data generated in real life? Do you control the code for this as well?
 
no it can be like motorola format or host byte order or network byte order etc
i agree this is like a not often used case most of the time protocols align their bytes correctly
anyways i have as well some older assembler code that handles the 32 bit cases with either msb/lsb or lsb/msb order and sign correctly ill just look into allocating enough memory then and ORing those results
just frustrating that the std::bitset cant handle something like this ;(
 
The reason I keep banging on about this is that given the pattern you describe sounds like the intention really is for a big-endian solution. It is easy to modify my code to make it little-endian, but I suspect this is not the intention of the protocol
 
yeah what i'm saying though is that it the endian thing is wrong it comes later
first one needs to get the bits in order then one can worry about the bytes
otherwise the data is destroyed
 
How do you mean? Give me an example of such destroyed data
 
like if you check with this value here 0xFFFEFDFCFBFAF9F8ULL
it will break the code
or at least the result is not what i expected
 
12:19 PM
OK, let me try it. What is the bit offset and bit count you want for this value?
 
hm strange in the live code that example works
maybe, my compiler is doing something strange
ill try a bit more around
 
1:18 PM
okey here is a case where the data breaks coliru.stacked-crooked.com/a/445c31f895586e1d
as one can see only the first byte is correct
well not even the first byte the first 4 bits
ah well forgot one F so
its uint64_t pattern = 0xFAAAAAAAAAAAAAFFULL;
std::array<uint8_t, 8> input = {0xFA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xAA, 0xFF};

g++ -std=c++14 -O2 -Wall -pedantic -pthread main.cpp && ./a.out
8839064868652493567 9031218452753634687
but issue remains
 
That was only one of the typos. You have two others in that code
1) The expected result should not be shifted right and 2) the FULL_64_MASK should be shifted right by 1 bit, i.e.:
auto expected_result = (pattern & (FULL_64_MASK >> 1));
instead of:
auto expected_result = (pattern & (FULL_64_MASK >> 0)) >> 1;
Make those corrections and the right result comes out
this is because your offset and length are set to 1 and 63 bits respectively
For the final result calculation, the general formula (I think) is:
 
expected_result = (pattern & (FULL_64_MASK >> nBitOffset)) >> (64-nBitLen) ?
 
I think thats right, but need to reslly check it out to be sure
 
1:33 PM
ok its #define PREP(d,o,l) (d&(nMask>>o))>>(64-(l+o))
d = data o = offset l = len
Testname: A_Field.can_be_extracted_correctly
Test FullName: A_Field.can_be_extracted_correctly
Testquelle: d:\git\cats_flex\view\cats_flex\ca\tcpip_neu\tcpiptreiber_gtest.cpp Zeile 168
Testresult: Success

;)
 
OK to re-accept? :)
 
yeah ill update the code also at top with the complete solution and test cases
/** @brief Extract field (assumption bitlength+offset is prechecked against stringlength)
* @param nBitOffset (Range 0-7, greater ranges work as well, handled by byteoffset)
* @param nBitLen (Max: 64)
* @param sSource
*/
uint64_t ExtractField( unsigned nBitOffset, unsigned nBitLen, const uint8_t* sSource )
{
    unsigned _nByteOffset = nBitOffset / 8;
    uint8_t  _nBitOffset = nBitOffset % 8;

    uint64_t nResult = 0ULL;
    uint8_t nMask = 0xFF;

    sSource += _nByteOffset;

    // First byte
my code now looks like that i do a swap when a bit offset is present probably still buggy if a length is there, but yeah it would be difficult to shift the bits in the other direction they would have been cut off
hm no infact it just works for this test case there is some cases where it wouldnt work anyways ill reaccept the soluion, buy yeah ill explain the limitations as well i will need to work on this still some more ;(
 
Go ahead, show me where it doesn't work. Its very possible there are still bugs that need ironing out
 
well for one thing i want to fully avoid that swap64
then it would work again indepent of the bitoffset+len exceeding 64
 
You mean you want a little-endian solution?
 
1:50 PM
yeah well i want to avoid swaping the bytes so i guess i still dont see the relation fully
because networkbyteorder is bytes not bits
so i think it would be much better to decide after extraction what byteorder to choose
 
You don't see the relation between between swapping bytes and endianness, is that what you mean? Or am I misunderstanding?
 
well you saw the test cases basically if i pass into the function "HelloHello" as integer with bitoffset 0 and len 64 then i want "HelloHello" output and not "olleHolleH"
but atm the function just always reverses the bytes
 
But that's only because you're treating the input/output as uint64_t. If you treated them as byte sequences, you would get back exactly the same thing you put in
Do you not understand this point? That's what endianness is all about - the ordering of bytes within integers
It has nothing to do with ordering of bytes in just plain old byte sequences
For example consider the number 0xAABBCCDD. If you looked at the memory starting at the start address of what that numeric literal was stored, you would see the byte sequence '0xDD 0xCC 0xBB 0xAA`. I think this is the bit that you;re not realising
You think that you're inputting '0xAA 0xBB 0xCC 0xDD' as a byte sequence, and not understanding why my code flips it around. It isn't. You're putting in the reverse sequence by using an integer literal '0XAABBCCDD`
BTW its details like this that make reinterpreting pointers to one kind of data into pointers of another kind of data undefined behaviour
 
2:33 PM
yes but in most cases in hardware near protocols hostbyteorder is used now, networkbyteorder i dont see that often anymore
and im fully aware of the fact that an integer is actually in reverse order, but the function returns an integer not an string
that it receives an string is just because that is the storage type of the network buffer
 
3:04 PM
OK, but then do you see why your question about "HelloHello" returning "olleHolleH" is strange to me? Suppose you really did have a string made up of eight bytes, say "HelloYou".
Lets say its stored as a char * str to allocated memory which is 8-byte aligned. Suppose you then did something like uint8_t intStorage = *reinterpret_cast<uint8_t*>(&str);. Then you passed this intStorage around until it got to the decoding code we're discussing.
Then you pass it as input, with your bit offset set to zero and your bit length set to 64. The function would give you a unit64_t output. If you then did something like const char* outputStr = reinterpret_cast<const char*>(&output);, what would you get as the contents of your output string? You would get "HelloYou", just like your original input
 

last day (14 days later) »