Difference between revisions of "VarInt And VarLong"

From wiki.vg
Jump to navigation Jump to search
(Use mojang's own version of readVarInt/readVarLong)
m (Oops.)
 
(6 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 
Variable-length format such that smaller numbers use fewer bytes.  These are very similar to [http://developers.google.com/protocol-buffers/docs/encoding#varints Protocol Buffer Varints]: the 7 least significant bits are used to encode the value and the most significant bit indicates whether there's another byte after it for the next part of the number.  The least significant group is written first, followed by each of the more significant groups; thus, VarInts are effectively little endian (however, groups are 7 bits, not 8).
 
Variable-length format such that smaller numbers use fewer bytes.  These are very similar to [http://developers.google.com/protocol-buffers/docs/encoding#varints Protocol Buffer Varints]: the 7 least significant bits are used to encode the value and the most significant bit indicates whether there's another byte after it for the next part of the number.  The least significant group is written first, followed by each of the more significant groups; thus, VarInts are effectively little endian (however, groups are 7 bits, not 8).
  
VarInts are never longer than 5 bytes, and VarLongs are never longer than 10 bytes.
+
VarInts are never longer than 5 bytes, and VarLongs are never longer than 10 bytes. Within these limits, unnecessarily long encodings (e.g. <code>81 00</code> to encode 1) are allowed.
  
 
Pseudocode to read and write VarInts and VarLongs:
 
Pseudocode to read and write VarInts and VarLongs:
  
 +
<syntaxhighlight lang="java">
 +
private static final int SEGMENT_BITS = 0x7F;
 +
private static final int CONTINUE_BIT = 0x80;
 +
</syntaxhighlight>
 
<syntaxhighlight lang="java">
 
<syntaxhighlight lang="java">
 
public int readVarInt() {
 
public int readVarInt() {
 
     int value = 0;
 
     int value = 0;
     int length = 0;
+
     int position = 0;
 
     byte currentByte;
 
     byte currentByte;
  
 
     while (true) {
 
     while (true) {
 
         currentByte = readByte();
 
         currentByte = readByte();
         value |= (currentByte & 0x7F) << (length * 7);
+
         value |= (currentByte & SEGMENT_BITS) << position;
       
+
 
         length += 1;
+
        if ((currentByte & CONTINUE_BIT) == 0) break;
         if (length > 5) {
+
 
            throw new RuntimeException("VarInt is too big");
+
         position += 7;
        }
+
 
        if ((in & 0x80) != 0x80) {
+
         if (position >= 32) throw new RuntimeException("VarInt is too big");
            break;
 
        }
 
 
     }
 
     }
 +
 
     return value;
 
     return value;
 
}
 
}
Line 29: Line 32:
 
public long readVarLong() {
 
public long readVarLong() {
 
     long value = 0;
 
     long value = 0;
     int length = 0;
+
     int position = 0;
 
     byte currentByte;
 
     byte currentByte;
  
 
     while (true) {
 
     while (true) {
 
         currentByte = readByte();
 
         currentByte = readByte();
         value |= (currentByte & 0x7F) << (length * 7);
+
         value |= (long) (currentByte & SEGMENT_BITS) << position;
       
+
 
         length += 1;
+
        if ((currentByte & CONTINUE_BIT) == 0) break;
         if (length > 10) {
+
 
            throw new RuntimeException("VarLong is too big");
+
         position += 7;
        }
+
 
        if ((in & 0x80) != 0x80) {
+
         if (position >= 64) throw new RuntimeException("VarLong is too big");
            break;
 
        }
 
 
     }
 
     }
 +
 
     return value;
 
     return value;
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
 
<syntaxhighlight lang="java">
 
<syntaxhighlight lang="java">
public static void writeVarInt(int value) {
+
public void writeVarInt(int value) {
 
     while (true) {
 
     while (true) {
         if ((value & ~0x7F) == 0) {
+
         if ((value & ~SEGMENT_BITS) == 0) {
          writeByte(value);
+
            writeByte(value);
          return;
+
            return;
 
         }
 
         }
  
         writeByte((value & 0x7F) | 0x80);
+
         writeByte((value & SEGMENT_BITS) | CONTINUE_BIT);
 +
 
 
         // Note: >>> means that the sign bit is shifted with the rest of the number rather than being left alone
 
         // Note: >>> means that the sign bit is shifted with the rest of the number rather than being left alone
 
         value >>>= 7;
 
         value >>>= 7;
Line 62: Line 65:
 
</syntaxhighlight>
 
</syntaxhighlight>
 
<syntaxhighlight lang="java">
 
<syntaxhighlight lang="java">
public static void writeVarLong(long value) {
+
public void writeVarLong(long value) {
 
     while (true) {
 
     while (true) {
         if ((value & ~0x7F) == 0) {
+
         if ((value & ~((long) SEGMENT_BITS)) == 0) {
          writeByte(value);
+
            writeByte(value);
          return;
+
            return;
 
         }
 
         }
  
         writeByte((value & 0x7F) | 0x80);
+
         writeByte((value & SEGMENT_BITS) | CONTINUE_BIT);
 +
 
 
         // Note: >>> means that the sign bit is shifted with the rest of the number rather than being left alone
 
         // Note: >>> means that the sign bit is shifted with the rest of the number rather than being left alone
 
         value >>>= 7;
 
         value >>>= 7;

Latest revision as of 14:02, 12 March 2024

Variable-length format such that smaller numbers use fewer bytes. These are very similar to Protocol Buffer Varints: the 7 least significant bits are used to encode the value and the most significant bit indicates whether there's another byte after it for the next part of the number. The least significant group is written first, followed by each of the more significant groups; thus, VarInts are effectively little endian (however, groups are 7 bits, not 8).

VarInts are never longer than 5 bytes, and VarLongs are never longer than 10 bytes. Within these limits, unnecessarily long encodings (e.g. 81 00 to encode 1) are allowed.

Pseudocode to read and write VarInts and VarLongs:

private static final int SEGMENT_BITS = 0x7F;
private static final int CONTINUE_BIT = 0x80;
public int readVarInt() {
    int value = 0;
    int position = 0;
    byte currentByte;

    while (true) {
        currentByte = readByte();
        value |= (currentByte & SEGMENT_BITS) << position;

        if ((currentByte & CONTINUE_BIT) == 0) break;

        position += 7;

        if (position >= 32) throw new RuntimeException("VarInt is too big");
    }

    return value;
}
public long readVarLong() {
    long value = 0;
    int position = 0;
    byte currentByte;

    while (true) {
        currentByte = readByte();
        value |= (long) (currentByte & SEGMENT_BITS) << position;

        if ((currentByte & CONTINUE_BIT) == 0) break;

        position += 7;

        if (position >= 64) throw new RuntimeException("VarLong is too big");
    }

    return value;
}
public void writeVarInt(int value) {
    while (true) {
        if ((value & ~SEGMENT_BITS) == 0) {
            writeByte(value);
            return;
        }

        writeByte((value & SEGMENT_BITS) | CONTINUE_BIT);

        // Note: >>> means that the sign bit is shifted with the rest of the number rather than being left alone
        value >>>= 7;
    }
}
public void writeVarLong(long value) {
    while (true) {
        if ((value & ~((long) SEGMENT_BITS)) == 0) {
            writeByte(value);
            return;
        }

        writeByte((value & SEGMENT_BITS) | CONTINUE_BIT);

        // Note: >>> means that the sign bit is shifted with the rest of the number rather than being left alone
        value >>>= 7;
    }
}

Warning.png Note Minecraft's VarInts are identical to LEB128 with the slight change of throwing a exception if it goes over a set amount of bytes.

Warning.png Note that Minecraft's VarInts are not encoded using Protocol Buffers; it's just similar. If you try to use Protocol Buffers Varints with Minecraft's VarInts, you'll get incorrect results in some cases. The major differences:

  • Minecraft's VarInts are all signed, but do not use the ZigZag encoding. Protocol buffers have 3 types of Varints: uint32 (normal encoding, unsigned), sint32 (ZigZag encoding, signed), and int32 (normal encoding, signed). Minecraft's are the int32 variety. Because Minecraft uses the normal encoding instead of ZigZag encoding, negative values always use the maximum number of bytes.
  • Minecraft's VarInts are never longer than 5 bytes and its VarLongs will never be longer than 10 bytes, while Protocol Buffer Varints will always use 10 bytes when encoding negative numbers, even if it's an int32.

Sample VarInts:

Value Hex bytes Decimal bytes
0 0x00 0
1 0x01 1
2 0x02 2
127 0x7f 127
128 0x80 0x01 128 1
255 0xff 0x01 255 1
25565 0xdd 0xc7 0x01 221 199 1
2097151 0xff 0xff 0x7f 255 255 127
2147483647 0xff 0xff 0xff 0xff 0x07 255 255 255 255 7
-1 0xff 0xff 0xff 0xff 0x0f 255 255 255 255 15
-2147483648 0x80 0x80 0x80 0x80 0x08 128 128 128 128 8

Sample VarLongs:

Value Hex bytes Decimal bytes
0 0x00 0
1 0x01 1
2 0x02 2
127 0x7f 127
128 0x80 0x01 128 1
255 0xff 0x01 255 1
2147483647 0xff 0xff 0xff 0xff 0x07 255 255 255 255 7
9223372036854775807 0xff 0xff 0xff 0xff 0xff 0xff 0xff 0xff 0x7f 255 255 255 255 255 255 255 255 127
-1 0xff 0xff 0xff 0xff 0xff 0xff 0xff 0xff 0xff 0x01 255 255 255 255 255 255 255 255 255 1
-2147483648 0x80 0x80 0x80 0x80 0xf8 0xff 0xff 0xff 0xff 0x01 128 128 128 128 248 255 255 255 255 1
-9223372036854775808 0x80 0x80 0x80 0x80 0x80 0x80 0x80 0x80 0x80 0x01 128 128 128 128 128 128 128 128 128 1