Namaran

Code daily. Without assist.

2026-10-13

get_varint.c

#include <inttypes.h>
#include <stdio.h>

static uint64_t get_varint(const unsigned char *p) {
    uint64_t value = 0;
    int shift = 0;
    unsigned char b;
    do {
        b = *p++;
        value |= (uint64_t)((b & 0x7F) << shift);
        shift += 7;
    } while (b & 0x80);
    return value;
}

int main(void) {
    const unsigned char buf[] = {0x80, 0xE4, 0x97, 0xD0, 0x12};
    printf("%" PRIu64 "\n", get_varint(buf));
}

get_varint は、下位から7ビットずつ並べ、続きがあるバイトだけ最上位ビットを立てた可変長整数を、uint64_t に読み戻す関数です。main の5バイトは 5000000000 を書いたもので、本来は 5000000000 と表示されるはずですが、いまは別の値が表示されます。4バイト以下に収まる数は正しく読めています。

Answer

Wrong

value |= (uint64_t)((b & 0x7F) << shift);

b は unsigned char ですが、演算の前に整数昇格で int になります。0x7F も int なので、b & 0x7F は int です。シフトの結果は左オペランドの型になるので、(b & 0x7F) << shift も int で計算されます。uint64_t へのキャストが変換するのは、シフトが済んだあとの値です。

4バイト目までは shift が21以下で、127 << 21 でも int に収まるので正しく読めます。5バイト目の 0x12(18)では shift が28になり、18 << 28 は約48億で、32ビットの int では表せません。符号付き整数の左シフトの結果が表せないときは未定義動作なので、表示される値は決まりません1。

Right

value |= (uint64_t)(b & 0x7F) << shift;

キャストは単項演算子で、シフトより強く結びつきます。括弧を外すとキャストが b & 0x7F だけにかかり、シフトは uint64_t で行われるので、28ビットずらしても上位のビットが残ります2。0x7Fu と書いて符号なしにするだけでは足りません。未定義動作はなくなりますが、シフトは32ビットの unsigned int のままなので、32ビット目より上が黙って捨てられます。

  1. x86-64 の GCC では、上位のビットが落ちた 705032704(5000000000 を2の32乗で割った余り)が表示されることがありますが、最適化の具合で変わりうる値です。
  2. Protocol Buffers の varint や DWARF の ULEB128 がこの形式です。64ビットの値は最大10バイトになり、最後のバイトでは shift が63に達します。