VarInt And VarLong - Revision history

imported>LassiPulkkinen: Oops.

2024-03-12T14:02:36Z

Oops.

← Older revision		Revision as of 14:02, 12 March 2024
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. Within these limits, unnecessarily long encodings (e.g. <code>f1 00</code> to encode 1) are allowed.		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:

imported>LassiPulkkinen: Document that overlong encodings are allowed.

2024-03-12T14:01:33Z

Document that overlong encodings are allowed.

← Older revision		Revision as of 14:01, 12 March 2024
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>f1 00</code> to encode 1) are allowed.

	Pseudocode to read and write VarInts and VarLongs:		Pseudocode to read and write VarInts and VarLongs:

imported>Rmheuer: Cast shift to long in readVarLong to prevent data loss from implicit integer shift

2022-05-19T14:53:14Z

Cast shift to long in readVarLong to prevent data loss from implicit integer shift

← Older revision		Revision as of 14:53, 19 May 2022
Line 37:		Line 37:
	while (true) {		while (true) {
	currentByte = readByte();		currentByte = readByte();
	value \|= (currentByte & SEGMENT_BITS) << position;		value \|= (long) (currentByte & SEGMENT_BITS) << position;

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

imported>Pv6q: Fixed some indentation and separated a few lines

2022-04-24T18:24:16Z

Fixed some indentation and separated a few lines

← Older revision		Revision as of 18:24, 24 April 2022
Line 53:		Line 53:
	while (true) {		while (true) {
	if ((value & ~SEGMENT_BITS) == 0) {		if ((value & ~SEGMENT_BITS) == 0) {
	writeByte(value);		writeByte(value);
	return;		return;
	}		}

	writeByte((value & SEGMENT_BITS) \| CONTINUE_BIT);		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 67:		Line 68:
	while (true) {		while (true) {
	if ((value & ~((long) SEGMENT_BITS)) == 0) {		if ((value & ~((long) SEGMENT_BITS)) == 0) {
	writeByte(value);		writeByte(value);
	return;		return;
	}		}

	writeByte((value & SEGMENT_BITS) \| CONTINUE_BIT);		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;

imported>Pv6q: Made the pseudocode more readable by giving names to the bit masks. Also made the readVarInt and readVarLong methods more efficient.

2022-03-21T23:05:32Z

Made the pseudocode more readable by giving names to the bit masks. Also made the readVarInt and readVarLong methods more efficient.

← Older revision		Revision as of 23:05, 21 March 2022
Line 5:		Line 5:
	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 ((~~currentByte & 0x80) != 0x80~~) {		if (position >= 32) throw new RuntimeException("VarInt is too big");
	~~break~~;
	}
	}		}

	return value;		return value;
	}		}
Line 30:		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 \|= (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 ((~~currentByte & 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 64:		Line 64:
	</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;

imported>Rmheuer: Fix reading VarInt and VarLong example code

2022-01-20T17:55:41Z

Fix reading VarInt and VarLong example code

← Older revision		Revision as of 17:55, 20 January 2022
Line 20:		Line 20:
	}		}

	if ((~~value~~ & 0x80) != 0x80) {		if ((currentByte & 0x80) != 0x80) {
	break;		break;
	}		}
Line 42:		Line 42:
	}		}

	if ((~~value~~ & 0x80) != 0x80) {		if ((currentByte & 0x80) != 0x80) {
	break;		break;
	}		}

imported>Doot: fix some variable names (if anyone wants to discuss mojang's version, feel free to ping me from the sponge, paper, forge, or fabric discords at doot#0001)

2021-11-24T09:43:06Z

fix some variable names (if anyone wants to discuss mojang's version, feel free to ping me from the sponge, paper, forge, or fabric discords at doot#0001)

← Older revision		Revision as of 09:43, 24 November 2021
Line 19:		Line 19:
	throw new RuntimeException("VarInt is too big");		throw new RuntimeException("VarInt is too big");
	}		}
	if ((in & 0x80) != 0x80) {
			if ((value & 0x80) != 0x80) {
	break;		break;
	}		}
Line 40:		Line 41:
	throw new RuntimeException("VarLong is too big");		throw new RuntimeException("VarLong is too big");
	}		}
	if ((in & 0x80) != 0x80) {
			if ((value & 0x80) != 0x80) {
	break;		break;
	}		}

imported>Doot: Use mojang's own version of readVarInt/readVarLong

2021-11-24T09:22:58Z

Use mojang's own version of readVarInt/readVarLong

← Older revision		Revision as of 09:22, 24 November 2021
Line 8:		Line 8:
	public int readVarInt() {		public int readVarInt() {
	int value = 0;		int value = 0;
	int ~~bitOffset~~ = 0;		int length = 0;
	byte currentByte;		byte currentByte;
	~~do {~~
	~~if (bitOffset == 35) throw new RuntimeException("VarInt is too big");~~

			while (true) {
	currentByte = readByte();		currentByte = readByte();
	value \|= (currentByte & ~~0b01111111~~) << ~~bitOffset~~;		value \|= (currentByte & 0x7F) << (length * 7);

	~~bitOffset~~ += 7;		length += 1;
	} ~~while~~ ((~~currentByte~~ & ~~0b10000000~~) != 0);		if (length > 5) {
			throw new RuntimeException("VarInt is too big");
			}
			if ((in & 0x80) != 0x80) {
			break;
			}
			}
	return value;		return value;
	}		}
Line 25:		Line 29:
	public long readVarLong() {		public long readVarLong() {
	long value = 0;		long value = 0;
	int ~~bitOffset~~ = 0;		int length = 0;
	byte currentByte;		byte currentByte;
	~~do {~~
	~~if (bitOffset == 70) throw new RuntimeException("VarLong is too big");~~

			while (true) {
	currentByte = readByte();		currentByte = readByte();
	value \|= (currentByte & ~~0b01111111~~) << ~~bitOffset~~;		value \|= (currentByte & 0x7F) << (length * 7);

	~~bitOffset~~ += 7;		length += 1;
	} ~~while~~ ((~~currentByte~~ & ~~0b10000000~~) != 0);		if (length > 10) {
			throw new RuntimeException("VarLong is too big");
			}
			if ((in & 0x80) != 0x80) {
			break;
			}
			}
	return value;		return value;
	}		}

imported>Doot: Replace writeVarInt/writeeVarLong with mojang's own version (binary is not easier to read precisely because it takes more digits to represent, and is therefore prone to human error)

2021-11-24T09:16:10Z

Replace writeVarInt/writeeVarLong with mojang's own version (binary is not easier to read precisely because it takes more digits to represent, and is therefore prone to human error)

← Older revision		Revision as of 09:16, 24 November 2021
Line 42:		Line 42:
	public static void writeVarInt(int value) {		public static void writeVarInt(int value) {
	while (true) {		while (true) {
	~~// Only the first 7 bits have data~~		if ((value & ~0x7F) == 0) {
	if ((value & ~~0b11111111111111111111111110000000~~) == 0) {
	writeByte(value);		writeByte(value);
	return;		return;
	}		}

	writeByte(value & ~~0b01111111~~ \| ~~0b10000000~~);		writeByte((value & 0x7F) \| 0x80);
	// 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 57:		Line 56:
	public static void writeVarLong(long value) {		public static void writeVarLong(long value) {
	while (true) {		while (true) {
	~~// Only the first 7 bits have data~~		if ((value & ~0x7F) == 0) {
	if ((value & ~~0b1111111111111111111111111111111111111111111111111111111110000000~~) == 0) {
	writeByte(value);		writeByte(value);
	return;		return;
	}		}

	writeByte(value & ~~0b01111111~~ \| ~~0b10000000~~);		writeByte((value & 0x7F) \| 0x80);
	// 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;

imported>Pv6q: Fixed my bad wording

2021-11-03T20:43:03Z

Fixed my bad wording

← Older revision		Revision as of 20:43, 3 November 2021
Line 42:		Line 42:
	public static void writeVarInt(int value) {		public static void writeVarInt(int value) {
	while (true) {		while (true) {
	// Only the first 7 bits ~~are needed~~		// Only the first 7 bits have data
	if ((value & 0b11111111111111111111111110000000) == 0) {		if ((value & 0b11111111111111111111111110000000) == 0) {
	writeByte(value);		writeByte(value);
Line 57:		Line 57:
	public static void writeVarLong(long value) {		public static void writeVarLong(long value) {
	while (true) {		while (true) {
	// Only the first 7 bits ~~are needed~~		// Only the first 7 bits have data
	if ((value & 0b1111111111111111111111111111111111111111111111111111111110000000) == 0) {		if ((value & 0b1111111111111111111111111111111111111111111111111111111110000000) == 0) {
	writeByte(value);		writeByte(value);