# 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](../schema.md#bounds-and-validation) 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](../schema.md#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          |