Integer Encoding #

The integer encoding is the foundation of Hypha. Every other type uses it internally for length prefixes or indices.

Byte Structure #

Each byte carries 7 value bits and 1 continuation flag:

7	6	5	4	3	2	1	0
e	n	n	n	n	n	n	n

• e = 0: This is the last byte of the integer.
• e = 1: Another byte follows.

The value bits (n) from all bytes are concatenated in little-endian order (least significant group first). Together they form a 7-bit-per-byte little-endian unsigned integer, which is then interpreted as either two's complement or unsigned depending on the schema bounds.

Varint Encoding #

To encode an integer:

1. Split the value into 7-bit groups, least significant first.
2. For each group, create a byte: the high bit is e (1 if more groups follow, 0 for the last), the low 7 bits are the group.
3. Use the minimum number of bytes (canonical encoding).

Unsigned Varint Examples #

These show the unsigned varint encoding before any mode conversion:

Value	7-bit groups (LE)	Bytes (hex)
0	0000000	00
1	0000001	01
42	0101010	2A
127	1111111	7F
128	0000000, 0000001	80 01
1000	1101000, 0000111	E8 07

Note how 128 needs two bytes: 10000000 (e=1, value=0) then 00000001 (e=0, value=1). The decoded unsigned value is 1 << 7 | 0 = 128.

Two's Complement Varint Examples #

For two's complement, the varint bytes decode to an unsigned value which is then interpreted as signed. The sign is determined by the most significant bit of the last byte's 7-bit group.

Value	Unsigned wire	7-bit groups (LE)	Bytes (hex)
-1	127	1111111	7F
-5	123	1111011	7B
-42	86	1010110	56
-64	64	1000000	40
-65	16319	0111111, 1111111	BF 7F
-128	16256	0000000, 1111111	80 7F

Values from -64 to 63 fit in one byte. -65 and below need two or more bytes.

Maximum Range #

Up to 8 continuation bytes may be used (each with e=1, 7 value bits), giving 56 value bits. If a 9th byte is used, it is always the last — the decoder reads at most 9 bytes — and all 8 bits are value bits (the e-bit position is not checked). This yields a total of 64 value bits.

Any integer must never exceed the range of an int64.

Two's Complement vs Unsigned #

The encoding mode depends on the schema bounds declared for the integer.

✔️ = bound declared, ❌ = bound omitted.

Min	Max	Algorithm	Decoded value f(e)
❌	❌	two's complement	f(e) = e
✔️	❌	unsigned	f(e) = min + e
❌	✔️	unsigned	f(e) = max - e
✔️	✔️	unsigned	f(e) = min + e

e is the value decoded from the varint bytes (before mode conversion). f(e) is the actual integer value.

Row-by-row explanation #

Row 1 (no bounds): The wire value IS the actual value. Uses two's complement so negative numbers work. Example: int (though bounds are usually specified).

Row 2 (min only): Values are stored as an offset from the minimum. Wire = actual - min. Example: int[5...] with value 7 → wire = 7 - 5 = 2.

Row 3 (max only): Values are stored as an offset from the maximum (inverted). Wire = max - actual, so larger actual values produce smaller wire values. Example: int[...100] with value 95 → wire = 100 - 95 = 5.

Row 4 (both bounds): Same as row 2. Wire = actual - min. Example: int[0...100] with value 30 → wire = 30 - 0 = 30.

Null #

Null is only possible for nullable types (prefixed with ?). Non-nullable types cannot encode null and have no offset.

Two's complement (nullable) #

Null is encoded as wire value -1. All negative values are shifted by -1 to reserve -1 for null:

Wire	Decoded
-1	null
-2	-1
-3	-2
...	...
0	0
1	1

In short: if value is null → wire = -1. Else if value < 0 → wire = value - 1. Else → wire = value.

Unsigned (nullable) #

Null is encoded as wire value 0. All values are shifted by +1 to reserve 0 for null:

Wire	Decoded
0	null
1	min (or max)
2	min + 1 (or max - 1)
...	...

In short: if value is null → wire = 0. Else → wire = (value - min) + 1, or for max-only: wire = (max - value) + 1.

Non-nullable #

No null encoding is possible. The wire value is computed directly from the schema bounds (rows above), with no offset.

Encoding Algorithm #

Input: schema bounds (min, max), value, is_nullable
Output: varint bytes

1. Determine mode:
   if min is omitted AND max is omitted:
       mode = TWO'S_COMPLEMENT
   else:
       mode = UNSIGNED

2. Compute raw_e:
   if mode == TWO'S_COMPLEMENT:
       raw_e = value
   elif mode == UNSIGNED AND max is omitted:
       raw_e = value - min
   elif mode == UNSIGNED AND min is omitted:
       raw_e = max - value
   else: // unsigned, both bounds
       raw_e = value - min

3. Apply null offset:
   if NOT is_nullable:
       wire = raw_e
   elif value IS null:
       if mode == TWO'S_COMPLEMENT: wire = -1
       else: wire = 0
   elif mode == TWO'S_COMPLEMENT AND raw_e < 0:
       wire = raw_e - 1   // shift negatives by -1
   elif mode == UNSIGNED:
       wire = raw_e + 1   // shift all values by +1
   else:
       wire = raw_e       // two's complement, non-negative

 4. Varint encode wire:
    Split wire into 7-bit LE groups with continuation flags (e).
    Use the minimum number of bytes.
    
    Unsigned mode: wire is always non-negative — split directly.
    Two's complement mode: if wire is negative, use its sign-extended two's complement
    representation to determine the minimum 7-bit groups.

Decoding Algorithm #

Input: varint bytes, schema bounds (min, max), is_nullable
Output: decoded value or null

1. Varint decode the bytes → unsigned value

2. Determine mode (same as encoding):
   if min is omitted AND max is omitted:
       mode = TWO'S_COMPLEMENT
   else:
       mode = UNSIGNED

3. Convert to signed (for two's complement mode):
   if mode == TWO'S_COMPLEMENT:
       determine bit width N*7 (where the MSB of the last byte's 7-bit value group — bit 6 — is the sign bit)
       interpret unsigned as N*7-bit two's complement → signed_wire
   else:
       signed_wire = unsigned

4. Check for null (only if is_nullable):
   if mode == TWO'S_COMPLEMENT AND signed_wire == -1: return null
   if mode == UNSIGNED AND signed_wire == 0: return null

5. Remove null offset:
   if is_nullable:
       if mode == TWO'S_COMPLEMENT AND signed_wire < 0:
           raw_e = signed_wire + 1  // undo negative shift
       elif mode == UNSIGNED:
           raw_e = signed_wire - 1  // undo value shift
       else:
           raw_e = signed_wire
   else:
       raw_e = signed_wire

6. Convert to actual value:
   if mode == TWO'S_COMPLEMENT: value = raw_e
   elif mode == UNSIGNED AND max is omitted: value = min + raw_e
   elif mode == UNSIGNED AND min is omitted: value = max - raw_e
   else: value = min + raw_e

7. Validate: value must satisfy bounds. Return value.

Examples #

Schema	Value	Wire (e)	Varint (hex)	Notes
int	42	42	2A	two's comp, non-nullable
int	-42	-42	56	two's comp, 7-bit: 1010110
int	1000	1000	E8 07	two's comp, multi-byte
int[0...100]	30	30	1E	unsigned: e = 30 - 0
int[...50]	42	8	08	unsigned, max-only: e = 50 - 42
int[-10...10]	-4	6	06	unsigned: e = -4 - (-10)
?int[0...100]	30	31	1F	unsigned nullable: 30 + 1
?int[0...100]	null	0	00	unsigned nullable null
?int[-10...10]	-4	7	07	unsigned nullable: (-4 - -10) + 1
?int	-5	-6	7A	two's comp nullable: -5 - 1
?int	null	-1	7F	two's comp nullable null