0

I decided to learn about crypto (and C++) by first reading the entire C++ implementation of bitcoin. I'm having issue with this segment of serialize.h

template<typename Stream, typename I>
void WriteVarInt(Stream& os, I n)
{
    unsigned char tmp[(sizeof(n)*8+6)/7];
    int len=0;
    while(true) {
        tmp[len] = (n & 0x7F) | (len ? 0x80 : 0x00);
        if (n <= 0x7F)
            break;
        n = (n >> 7) - 1;
        len++;
    }
    do {
        ser_writedata8(os, tmp[len]);
    } while(len--);
}

I get that it is writing some variable to a stream, however I don't understand the significance of

(sizeof(n)*8+6)/7

for the array size. Then it enters some loop where it performs a bitwise or of the bitwise and of the loop counter and the hex representation of 127, and either the hex of 128 or 0 depending on whether or not the loop counter is 0.

Then if the number is less than 127 it is going to exit and write the reverse of the array to the stream.

What I don't understand is:

  1. What is the significance of that size of the array?
  2. Why the bitwise operations?
  3. Why write the array to the stream in reverse order?
  • I am not familiar with this, so I won't post a full answer, but it makes sense to think about this from a binary perspective. Decimal won't help you much. 1) The size of the array makes a jump after each (8*i) bits. 2) (n & 0x7F) grabs the last 7 bits of N. The (len ? 0x80 : 0x00) makes it add an extra 1 unless it's the first run. This explains the above - extra bits. 3) If (n <= 0x7F) tells you there are no bits beyond the ones seen, so no need to continue. 4) The array is written to in reverse order - it is then written to the stream backwards so that it is in the correct order again. – Jake Jul 14 '17 at 16:11
  • I should clarify. The array isn't written to in reverse order, per se. But you're taking the least significant bits out of n and putting them into tmp in a forwards order. Writing it backwards to the stream means the most significant bits hit the stream first. – Jake Jul 14 '17 at 16:14
  • @JArkinstall, this makes a ton of sense grabbing the last 7 bits, especially considering David Schwartz's answer. This is how they generate the variable length data. Thanks! – InfinityCounter Jul 14 '17 at 16:30
0

The encoding used fits 7 bits of data in each byte of output. So, to figure out the number of bytes of output you will produce, you need to take the number of bits of input and divide by 7 (since 7 bits of input fit in each byte of output), rounding up.

So, sizeof(n) is the number of bytes of output. Multiplying by 8 gives the number of bits of input. We divide by 7 to get the number of bytes of output needed to fit that many bits of input.

But integer division rounds down. To divide by 7 but round up, we add 6 to the number before dividing. That makes it round up.

  • Thanks for this, really puts it into perspective. I didn't know you could do x + (n-1) before dividing x by n to round up the number, at least I never thought about it. I didn't get how they were generating the MSB variable length data. Guess I still need to do a lot more practice using hex and binary in my code. – InfinityCounter Jul 14 '17 at 16:31
  • On another note I've decided to go along the route of blockchain development. Do you have any suggestions on resources to read or any general tips or advice? – InfinityCounter Jul 14 '17 at 16:34
  • 1
    One piece of advice: If you can find something that needs doing, no matter how small, do that thing. Having a specific, useful goal in mind tends to make you more efficient than just trying to read code line by line with no specific problem or focus. If you're looking at the bitcoin source code, take a look at problem reports or feature requests and try to find something small but interesting. (The bitcoins I got as a bounty for fixing the problem I fixed when I was learning my way around that code paid the downpayment on my house!) – David Schwartz Jul 14 '17 at 16:44
  • Will do but I originally started reading the source code so I could heavily document it for beginners once I'm familiar with it. For people who want to get into it there's not enough documentation for them to understand without a wealth of experience. – InfinityCounter Jul 14 '17 at 16:46
  • If it were commented for beginners, would you know as much about the method as you do now? Terrible justification, I know, but worth considering. – Jake Jul 14 '17 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.