What’s Base2^N encoding?#

Assim como na Base 10 (decimal) usamos 10 simbolos para representar numeros, o Encoding Base2^N nada mais eh do que mais uma maneira de representar os numeros (ou bytes), e quanto mais digitos tivermos, mais compacto sera a representacao;
Observe esse exemplo, onde representamos um mesmo UUID de 128 bits:

1
3d89a119-b3f8-4107-8f29-3daf5b964e50   # standard UUID string
2
0x3d89a119b3f841078f293daf5b964e50     # hex
3
81797519916847327862337238645062651472 # decimal
4
1xh6ghkczr843rya9xnxdsckjg             # base32 (Crockford's variant)
5

6
# and binary:
7
111101100010011010000100011001101100111111100001000001000001111000111100101001001111011010111101011011100101100100111001010000

O numero disponivel de simbolos determina quantos bits podem ser representados por um unico caractere, exemplos:
- Com binarios (Base 2), podemos codificar 1 bit de dado em cada caractere (2^1, 2 combinacoes de caracteres de 1 bit);
- Da mesma forma, com hexadecimais (Base 16), podemos codificar 4 bits de dado em 1 unico caractere (2^4, 16 combinacoes de caracteres de 4 bits).

How to convert a number to Base2^N?#

O processo e simples e consiste de tres etapas principais (considere, para os exemplos a seguir, o inteiro Base 10 - decimal - 249);
- Primeiro, splitamos o binario em grupos, e quem define a quantidade de bits em cada grupo eh o ˜N˜ de “2ˆN˜;
- Depois disso devemos obter a mascara da base, que equivale a “2ˆN - 1”;
- Por fim, fazemos um bitwise AND e movemos ˜N˜ bits com bitwise RIGHT SHIFT.

1
number = 249 # 11111001
2

3
"""
4
- Mask = 2ˆ3 - 1 = 7 (10) = 111 (2) = 0x7 (16)
5
- Shift = 3
6

7
    011 111 001
8
&   000 000 111
9
---------------
10
    000 000 001 (1 em Base 10), number >> 3
11

12
    000 011 111
13
&   000 000 111
14
---------------
15
    000 000 111 (7 em Base 10), number >> 3
16

17
    000 000 011
18
&   000 000 111
19
---------------
20
    000 000 011 (3 em Base 10), number >> 3
21
"""
22

23
MASK = 0x7
24
SHIFT = 3
25
converted_number_base8 = []
26

27
while number > 0:
28
    digit = number & MASK
29
    converted_number_base8.append(digit)
30
    number = number >> SHIFT
31

32
converted_number_base8.reverse()
33
print(''.join(map(str, converted_number_base8))) # 371

O metodo descrito acima eh usado para encodar numeros, e estamos considerando o input um chunk de tamanho fixo de dados, encodando do da direita para a esquerda (LSB First);
No entanto, os algoritmos padrao de Base32 e Base64 operam em dados de tamanhos arbitrarios, splitando eles em chunks menores, comecando da esquerda para a direita (MSB First).

Base32 Implementation (RFC 4648)#

Set of Characters#

Em Base 32 podemos encodar 5 bits de dados em um unico caractere (2ˆ5, 32 combinacoes de caracteres de 5 bits);
A especificacao RFC 4648 (nao eh regra, mas eh o padrao) define o seguinte conjunto de caracteres:

1
Value Encoding  Value Encoding  Value Encoding  Value Encoding
2
    0 A             9 J            18 S            27 3
3
    1 B            10 K            19 T            28 4
4
    2 C            11 L            20 U            29 5
5
    3 D            12 M            21 V            30 6
6
    4 E            13 N            22 W            31 7
7
    5 F            14 O            23 X
8
    6 G            15 P            24 Y         (pad) =
9
    7 H            16 Q            25 Z
10
    8 I            17 R            26 2

Encoding Flow#

Para encodar dados em base32, dividimos o conteudo em chunks de 5 bytes (40 bits) cada;
Primeiramente, iremos converter a cadeira de caracteres em uma cadeia de bytes, posteriormente dividiremos o array em grupos de 5 bits ate que haja 8 grupos totalizando 40 bits, ou seja, um chunk completo;
- Pode ser que, ao separar os grupos, haja um ultimo com bits remanescentes, dai precisamos preencher com zeros.
Dai processamos cada conjunto e codificamos para a respectiva letra extraida pela sequencia de bits;
Por fim, calculamos o padding, que sera responsavel por completar o ultimo chunk com os bits faltantes para 40;
- Para isso, pegamos o total de bits, calculamos quantos bits existem no ultimo chunk e fazemos a diferenca para descobrir a quantidade de caracteres de padding.

1
import math
2

3
CHARSET = "A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 2 3 4 5 6 7".split(" ")
4
MASK = 0x1f
5
CHUNK_SIZE = 5
6
CHARS_BY_CHUNK = 8
7

8
def encode_b32(content: str) -> str:
9
    encoded_str = ''
10

11
    if content == "":
12
        return encoded_str
13

14
    # Convert CONTENT to bits (with width 8) and join all bits together.
15
    bytes = [bin(ord(letter)) for letter in content]
16
    bits = int(''.join([byte[2:].zfill(8) for byte in bytes]), 2)
17

18
    # Fill in missing bits to make it a multiple of CHUNK_SIZE if chunk size is not a multiple of CHUNK_SIZE.
19
    if (len(content) * 8) % CHUNK_SIZE != 0:
20
        missing_bits = CHUNK_SIZE - (len(content) * 8) % CHUNK_SIZE # Represents remaining BITS.
21
        bits = bits << missing_bits
22

23
    # Extract each CHUNK_SIZE bits from BITS and convert to corresponding character.
24
    total_chunks = math.ceil((len(content) * 8) / CHUNK_SIZE)
25
    for i in range(total_chunks - 1, -1, -1): # 9 to 0, MSB to LSB.
26
        index = (bits >> (CHUNK_SIZE * i)) & MASK
27
        encoded_str += CHARSET[index]
28

29
    # Calculate padding and insert into encoded string if chunks are NOT COMPLETE.
30
    if total_chunks % CHARS_BY_CHUNK != 0:
31
        pads = CHARS_BY_CHUNK - (total_chunks % CHARS_BY_CHUNK) # Represents remaining CHARACTERS.
32
        encoded_str += '=' * pads
33

34
    return encoded_str

Decoding Flow#

Com o texto encriptado primeiramente retiramos os caracteres de padding e dividimos a string em sub-arrays com 8 caracteres cada (que vale 5 bytes / 40 bits e representa um chunk);
Nos sub-arrays de chunk completo, ou seja, 8 caracteres, transformamos eles de caracteres literais para inteiro e de inteiro para binario, e da esquerda para a direita reagrupamos em grupos de 8 bits (tamanho de um caractere ASCII);
Depois de reagrupar, transformamos os caracteres nos seus valores correspondentes a tabela ASCII, e esse eh o fim da primeira parte;
Para a segunda parte teremos que lidar com o chunk que estava incompleto na hora do encoding;
- Nessa segunda parte, precisaremos calcular o numero de bytes que o chunk atual incompleto representa na string original e numero de bits que foram adicionados como padding durante o encoding.

1
def decode_b32(content: str) -> str:
2
    decoded_str = ''
3

4
    # Remove padding characters.
5
    content = content.rstrip('=')
6

7
    # Convert each character to its corresponding value in CHARSET.
8
    chars = list(map(lambda char: CHARSET.index(char), content))
9

10
    bits = bit_count = 0
11
    for char in chars:
12
        bits = (bits << CHUNK_SIZE) | char
13
        bit_count += CHUNK_SIZE
14

15
        # Useful to extract bytes when we have 8 or more bits,
16
        # avoiding cases where encoding add extra bits.
17
        while bit_count >= BITS_PER_CHAR:
18
            bit_count -= BITS_PER_CHAR
19
            byte = (bits >> bit_count) & ASCII_MASK
20
            decoded_str += chr(byte)
21

22
    return decoded_str

More Generic Approach#

Conseguimos esse feito de encodar e decodar dados em Base32, mas como isso ficaria em outras bases? Haveria uma mudanca drastica no codigo?
E a resposta eh nao, nao haveria mudancas drasticas quanto ao processamento de dados, apenas em como tratamos certos valores, como o conjunto de caracteres, valores de chunks e etc, isso porque esse tipo de encode / decode eh stream based;
No nosso codigo atual, basta alterar as constantes:

1
MASK = 0x3f                 # 6 bits (2^6)
2
CHUNK_SIZE = 6              # bits per symbol
3
CHARS_BY_CHUNK = 4          # 4 chars per chunk in base64
4
CHARSET = list(
5
    "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
6
    "abcdefghijklmnopqrstuvwxyz"
7
    "0123456789+/"
8
)
9
BITS_PER_CHAR = 8
10
ASCII_MASK = 0xff           # 8 bits, 1 byte, ASCII char size
11

12
# code...
13

14
print(encode_b32("foobar"))
15
print(decode_b32("Zm9vYmFy"))

E para mais, a diferenca conceitual eh:

Propriedade	Base32	Base64
Bits por simbolo	5	6
Mascara	`0x1F`	`0x3F`
Simbolos por bloco	8	4
Bits por bloco	40	24
Bytes por bloco	5	3
Padding	`=`	`=`
Alfabeto	A–Z2–7	A–Z a–z 0–9 + /

Credits#

Special thanks to you, Piotr, for your amazing paper, it helped me a lot;
Check him article here!