Bitset format

[ostafen]

Hi, I'm coding an ed2k library on my own, for learning purpose and I'm using libed2k as a reference, since there is no so much detailed documentation on ed2k protocol. First of all, congratulations for this great work!

I have a doubt about the format of the part status field which is sent in the peer File Status Answer message. Initially, I thought that, i-th bit of the bitfield was stored at byte offset i / 8 (and bit offset i % 8), and this is also confirmed by libed2k. However, when downloading files made of only a single part (while testing my own library), I found that peers holding the entire file send the following single-byte bitfield: 00000001. Naturally, I expected the following bitfield: 10000000 (also according to libed2k). So I suspect that the format of the bitfield is "reversed", that is to say one should compute the offset of the i-th bit starting from the end of the stream (going from right to left).

I also noticed that, in this case, because of the function "clear_trailing_bits", libed2k would have cleared the last bit set to one, giving a zero bitfield, but I don't think this is correct (if the peer didn't get the only part the file is made of, he wouldn't send the part status field, setting the field "downloadedParts" to 0, instead of 1).

Can you give an explanation to such behaviour?

[a-pavlov]

Hi, I've reviewed the code in libed2k: you are right, in libed2k bits order is from left to right, so the first bit will be 10000000. I've opened emule source code and seems it generates bits in reverse order:

void CPartFile::WritePartStatus(CSafeMemFile* file) const
{
    UINT uED2KPartCount = GetED2KPartCount();
    file->WriteUInt16((uint16)uED2KPartCount);

    UINT uPart = 0;
    while (uPart != uED2KPartCount)
    {
        uint8 towrite = 0;
        for (UINT i = 0; i < 8; i++)
        {
            if (uPart < GetPartCount() && IsComplete((uint64)uPart*PARTSIZE, (uint64)(uPart + 1)*PARTSIZE - 1, true))
                towrite |= (1 << i);
            uPart++;
            if (uPart == uED2KPartCount)
                break;
        }
        file->WriteUInt8(towrite);
    }
}

So it looks like bug in libed2k. The source code was taken from libtorrent and original bits order was saved. We did not find find this problems because of most clients in ed2k network have full files and possibly libed2k ignores parts set when requests pieces. Pieces request measures in in-file offsets and wrong parts order does not affect it. In worst case we generate request to non-existing part on peer. Thank you.

[ostafen]

Thank you for this confirmation. I think that correctly decoding part map is very important, especially in situation where few sources are available. Piece request could be generated regardless of the piece availability in the remote peer, however suppose that you are currently downloading pieces with ids 0, 1 and 2 and that the peer you are sending the request only have piece 1. A PiecePicker which doesn't take into consideration the part map of the peer for piece selection, could return a block belonging to piece 0, which is not owned by the peer. By taking into consideration the part map, you could select a block which can be found inside piece 1, and piece request would be successful in that case. In fact, I found this bug while downloading a single-piece file with only a single source available. My client sent an upload request, because downloadedParts field was equal to one. Since the piece picker I wrote also inspects the part map for making decisions, than error was returned, because bit at position 0 was set to zero (in bitmap 00000001). Moreover, this bug also affect a piece picker which is based on a raremost selection strategy.

I could do a pull request to fix this issue

[a-pavlov]

It is important, but affects downloading not so badly as you can expect. Mostly because of ed2k network currently in "static" state - peers count is very small, and most of them contain full set of pieces because network speed is mush higher than 20 year ago and nobody downloads file for days. In this project https://github.com/a-pavlov/jed2k I just ignore piece set at all. Pull request is great idea. Thank you.