HP encoding.md

Hex Prefix encoding

What are the differences between RLP and HP encoding? How does HP encoding work?

Root: {1: 'Dog', 2: B, 3: A}
A: {1: C, 2: D, 3: 'Cat'}
B: {1: 'Goat', 2: 'Bear', 3: 'Rat'}
C: {1: 'Eagle', 2: 'Parrot', 3: E}
D: {1: 'Shark', 2: 'Dolphin', 3: 'Whale'}
E: {1: 'Duck', 2: 'Chicken', 3: 'Pig'}

• Key: Root, A, B, C, D and E in game is keys
• Node: the content corresponding with the key in the right part of each row. For example: {1: ‘Dog’, 2: B, 3: A}.
• Path: path is like 2–2–3 in game.
• Value: you can see it has some elements in all nodes, every element is a key-value pair. Value is the right part of element, value can be a key or a name of animal.
• Nibble: hex form of 4 bits is a nibble. For example: 0x1, 0x4, 0xf …

RLP is used for encoding/decoding Value and HP encoding is used for encoding/decoding Path.

leaf has terminator, and extension does not. terminator is the last byte of the path and has value of 16 in dec or 0x10 in hex.

HP encoding goals are:

1. Distinguish leaf and extension from each other without terminator.
2. Convert the path to even length. odd length is not friendly to machines.

HP encoding specification:

1. If input has terminator, remove terminator from input.
2. Create the prefix into input which has value as following table:

node type    path length    |    prefix    hexchar
--------------------------------------------------
extension    even           |    0000      0x0
extension    odd            |    0001      0x1
leaf         even           |    0010      0x2
leaf         odd            |    0011      0x3

• If the prefix is 0x0 or 0x2, add a padding nibble 0 follow the prefix, so the prefix is 0x00 and 0x20.
• Add prefix to path.

For example:

> [1, 2, 3, 4, 5]
'11 23 45'
> [0, 1, 2, 3, 4, 5]
'00 01 23 45'
> [0, f, 1, c, b, 8, 16]
'20 0f 1c b8'
> [f, 1, c, b, 8, 16]
'3f 1c b8'

• 16 is terminator, not path.