Core Lightning implementation of BOLT #11 invoices - part 5

We are going to write our project in the subdirectory bech32 that already contains the file bech32.c we are going to work on today and a Makefile to compile it with its ccan dependencies.

Specifically, our project depends on ccan/tal and ccan/short_types that we can get from rustyrussell/ccan repository.

To get those dependencies we clone rustyrussell/ccan repository and run make:

◉ tony@tony:~/clnlive/ccan:[git»master]
$ git clone https://github.com/rustyrussell/ccan
◉ tony@tony:~/clnlive/ccan:[git»master]
$ make

This created a config.h file that we need in our project to get ccan dependencies to compile. So we copy it like this:

◉ tony@tony:~/clnlive/ccan:[git»master]
$ cp config.h ../bech32/

Then we use ./tools/create-ccan-tree to create tal and short_types dependencies into a subdirectory called ccan under our project bech32:

◉ tony@tony:~/clnlive/ccan:[git»master]
$ ./tools/create-ccan-tree ../bech32/ccan/ tal short_types
Building ccan_depends, modfiles
Cleaning source tree
Adding ccan/alignof
Adding ccan/build_assert
Adding ccan/check_type
Adding ccan/compiler
Adding ccan/container_of
Adding ccan/hash
Adding ccan/htable
Adding ccan/likely
Adding ccan/list
Adding ccan/short_types
Adding ccan/str
Adding ccan/take
Adding ccan/tal
Adding ccan/typesafe_cb
Adding licenses
Adding build infrastructure
Done. ccan source tree built in ../bech32/ccan/

Now, we can go in our project and check the state of our project:

◉ tony@tony:~/clnlive/bech32:[git»master]
$ tree -L 3 .
.
├── bech32.c
├── ccan
│   ├── ccan
│   │   ├── alignof
│   │   ├── build_assert
│   │   ├── check_type
│   │   ├── compiler
│   │   ├── container_of
│   │   ├── hash
│   │   ├── htable
│   │   ├── likely
│   │   ├── list
│   │   ├── short_types
│   │   ├── str
│   │   ├── take
│   │   ├── tal
│   │   └── typesafe_cb
│   └── licenses
│       ├── BSD-MIT
│       ├── CC0
│       └── LGPL-2.1
├── compile_commands.json
├── config.h
└── Makefile

17 directories, 7 files

Note that compile_commands.json is intended for my editor for code completion and the like.

Note that the following examples doesn't include the #include ... statements. To know what they are check bech32.c section.

In the file bech32.c, we start with the following program

int main () {
  printf("foo");
}

that we compile and run like this:

◉ tony@tony:~/clnlive/bech32:[git»master]
$ make
◉ tony@tony:~/clnlive/bech32:[git»master]
$ ./bech32
foo

In that section we are trying to see how we can get the bits defining a character.

For instance, the ascii character c (102 in decimal) is [01100110] in binary notation with 8 bits.

How can we get those bits?

We can get those bits by using the shift (left to right) operator >> to push any bit from the left to the last position on the right and finally get that bit by using the & operator combined with the number 1 as right operand.

Let's look at some examples to understand how >> and & operators behave.

%c vs. %i

int main () {
  printf("%c\n", 'f');
  printf("%i", 'f');
}

◉ tony@tony:~/clnlive/bech32:[git»master]
$ make
◉ tony@tony:~/clnlive/bech32:[git»master]
$ ./bech32
f
102

& operator

int main () {
  printf("%i\n", 0 & 1);
  printf("%i\n", 1 & 1);
  printf("%i\n", 2 & 1);
  printf("%i",   3 & 1);
}

◉ tony@tony:~/clnlive/bech32:[git»master]
$ make
◉ tony@tony:~/clnlive/bech32:[git»master]
$ ./bech32
0
1
0
1

>> operator

// 1 <-> 001
// 2 <-> 010
// 4 <-> 100
int main () {
  printf("%i\n", (1 >> 1));
  printf("%i\n", (2 >> 1));
  printf("%i\n", (4 >> 1));
  printf("--\n");
  printf("%i\n", (1 >> 2));
  printf("%i\n", (2 >> 2));
  printf("%i\n", (4 >> 2));
  printf("--\n");
  printf("%i\n", (1 >> 3));
  printf("%i\n", (2 >> 3));
  printf("%i",   (4 >> 3));
}

◉ tony@tony:~/clnlive/bech32:[git»master]
$ make
◉ tony@tony:~/clnlive/bech32:[git»master]
$ ./bech32
0
1
2
--
0
0
1
--
0
0
0

Combining >> and & operator to get bits of a number

// 1 <-> 001
// 2 <-> 010
// 4 <-> 100
int main () {
  printf("%i\n", (1 >> 0) & 1);
  printf("%i\n", (2 >> 0) & 1);
  printf("%i\n", (4 >> 0) & 1);
  printf("--\n");
  printf("%i\n", (1 >> 1) & 1);
  printf("%i\n", (2 >> 1) & 1);
  printf("%i\n", (4 >> 1) & 1);
  printf("--\n");
  printf("%i\n", (1 >> 2) & 1);
  printf("%i\n", (2 >> 2) & 1);
  printf("%i",   (4 >> 2) & 1);
}

◉ tony@tony:~/clnlive/bech32:[git»master]
$ make
◉ tony@tony:~/clnlive/bech32:[git»master]
$ ./bech32
1
0
0
--
0
1
0
--
0
0
1

// o <-> 111 (decimal) <-> 01101111
int main () {
  for (size_t i=0; i < 8; i++){
    printf("%i", (111 >> i) & 1);
  }
  printf("\n--------\n");
  for (size_t i=0; i < 8; i++) {
    printf("%i", (111 >> (7 - i) & 1));
  }
}

◉ tony@tony:~/clnlive/bech32:[git»master]
$ ./bech32
11110110
--------
01101111

static u8 get_bit_of_char(const u8 c, size_t bit)
{
  return (c >> (7 - bit)) & 1;
}

int main () {
  for (size_t i=0; i < 8; i++){
    printf("%i", get_bit_of_char(111, i));
  }
}

◉ tony@tony:~/clnlive/bech32:[git»master]
$ make
◉ tony@tony:~/clnlive/bech32:[git»master]
$ ./bech32
01101111

In the previous section, we saw how to get the individual bits of a character. Now we need to group those bits by 5.

The following program takes the first 5 bits of the number 111 (ascii character o) and prints them enclosed by [...] and then takes the last 3 bits of the same number, prints them and prints two 0s (the padding), everything enclosed by [...]:

static u8 get_bit_of_char(const u8 c, size_t bit)
{
  return (c >> (7 - bit)) & 1;
}

int main () {
  size_t i, b;
  for (i=0; i < 8; i +=b){
    printf("[");
    for (b=0; b < 5; b++){
      if ((i + b) < 8)
        printf("%i", get_bit_of_char(111, i+b));
      else
        printf("0");
    }
    printf("]");
  }
}

This gives:

◉ tony@tony:~/clnlive/bech32:[git»master]
$ make
◉ tony@tony:~/clnlive/bech32:[git»master]
$ ./bech32
[01101][11100]

Now we do something similar but for the string "fo" (the numbers 102 and 111) as follow:

static u8 get_bit_of_char(const u8 c, size_t bit)
{
  return (c >> (7 - bit)) & 1;
}

int main () {
  size_t i, b;
  u8 * src = "fo";
  for (i=0; i < 16; i +=b){
    printf("[");
    for (b=0; b < 5; b++){
      if ((i + b) < 16)
        printf("%i", get_bit_of_char(src[(i+b) / 8], (i+b) % 8));
      else
        printf("0");
    }
    printf("]");
  }
}

This gives us:

◉ tony@tony:~/clnlive/bech32:[git»master]
$ make
◉ tony@tony:~/clnlive/bech32:[git»master]
$ ./bech32
[01100][11001][10111][10000]

So far, we've only printed bits in groups of five. Now, we want number (from 0 to 31 included) represented by those groups of 5 bits.

To do so we'll use the shift (right to left) operator << and the 'inclusive or' | operator. Specifically, each bit received from the 8 bits bytes is stored in a variable as the last bit (on the right) of the value held by the variable. In order, to get the number we are looking for, before storing that bit, we first shift by one from the right to the left the number held in that variable. Each time, we do that process for 5 bits we reset the variable to zero:

typedef unsigned char u5;

static u8 get_bit(const u8 *src, size_t bit)
{
  return (src[(bit / 8)] >> (7 - (bit % 8))) & 1;
}

int main () {
  size_t i, b;
  u8 * src = "fo";
  u5 u5_char;

  for (i=0; i < 16; i +=b){
    u5_char = 0;
    for (b=0; b < 5; b++){
      u5_char <<= 1;
      if ((i + b) < 16)
        u5_char |= get_bit(src, i+b);
    }
    printf("%i\n", u5_char);
  }
}

This gives us:

◉ tony@tony:~/clnlive/bech32:[git»master]
$ make
◉ tony@tony:~/clnlive/bech32:[git»master]
$ ./bech32
12
25
23
16

Now instead of erasing the variable u5_char for each new five bits, we store each new five bits in another cell of an array:

typedef unsigned char u5;

static u8 get_bit(const u8 *src, size_t bit)
{
  return (src[(bit / 8)] >> (7 - (bit % 8))) & 1;
}

int main () {
  size_t i, b;
  u8 * src = "fo";
  u5 * u5data = tal_arr(NULL, u5, 0);
  size_t u5data_len = 0;

  for (i=0; i < 16; i +=b){
    tal_resize(&u5data, u5data_len + 1);
    u5data[u5data_len] = 0;
    for (b=0; b < 5; b++){
      u5data[u5data_len] <<= 1;
      if ((i + b) < 16)
        u5data[u5data_len] |= get_bit(src, i+b);
    }
    u5data_len++;
  }

  for (i=0; i < tal_count(u5data); i++) {
    printf("%i\n", u5data[i]);
  }
}

This gives us:

◉ tony@tony:~/clnlive/bech32:[git»master]
$ make
◉ tony@tony:~/clnlive/bech32:[git»master]
$ ./bech32
12
25
23
16

This is the time now to extract some code and to put it in a function that we call u8_to_u5 like this:

typedef unsigned char u5;

static u8 get_bit(const u8 *src, size_t bit)
{
  return (src[(bit / 8)] >> (7 - (bit % 8))) & 1;
}

u5 *u8_to_u5(const u8 *src, size_t nbits)
{
  size_t i, b;
  u5 * u5data = tal_arr(NULL, u5, 0);
  size_t u5data_len = 0;

  for (i=0; i < nbits; i +=b){
    tal_resize(&u5data, u5data_len + 1);
    u5data[u5data_len] = 0;
    for (b=0; b < 5; b++){
      u5data[u5data_len] <<= 1;
      if ((i + b) < nbits)
        u5data[u5data_len] |= get_bit(src, i+b);
    }
    u5data_len++;
  }
  return u5data;
}

int main () {
  u8 * src = "foo bar";
  u5 * data = u8_to_u5(src, 56);

  for (size_t i=0; i < tal_count(data); i++) {
    printf("%i\n", data[i]);
  }

  tal_free(data);
}

This gives us:

◉ tony@tony:~/clnlive/bech32:[git»master]
$ make
◉ tony@tony:~/clnlive/bech32:[git»master]
$ ./bech32
12
25
23
22
30
8
3
2
12
5
25
0

Finally, we can encode those numbers using bech32 char set like this:

#include <stddef.h>
#include <stdio.h>
#include <ccan/tal/tal.h>
#include <ccan/short_types/short_types.h>

/* Type to annotate a 5 bit value. */
typedef unsigned char u5;

const char bech32_charset[] = "qpzry9x8gf2tvdw0s3jn54khce6mua7l";

static u8 get_bit_of_char(const u8 c, size_t bit)
{
  return (c >> (7 - bit)) & 1;
}
static u8 get_bit(const u8 *src, size_t bit)
{
  return (src[(bit / 8)] >> (7 - (bit % 8))) & 1;
}

u5 *u8_to_u5(const u8 *src, size_t nbits)
{
  size_t i, b;
  u5 * u5data = tal_arr(NULL, u5, 0);
  size_t u5data_len = 0;

  for (i=0; i < nbits; i +=b){
    tal_resize(&u5data, u5data_len + 1);
    u5data[u5data_len] = 0;
    for (b=0; b < 5; b++){
      u5data[u5data_len] <<= 1;
      if ((i + b) < nbits)
        u5data[u5data_len] |= get_bit(src, i+b);
    }
    u5data_len++;
  }
  return u5data;
}

int main () {
  u8 * src = "foo bar";
  u5 * data = u8_to_u5(src, 56);

  for (size_t i=0; i < tal_count(data); i++) {
    printf("%2i -> %c\n", data[i], bech32_charset[data[i]]);
  }

  tal_free(data);
}

This gives us:

◉ tony@tony:~/clnlive/bech32:[git»master]
$ make
◉ tony@tony:~/clnlive/bech32:[git»master]
$ ./bech32
12 -> v
25 -> e
23 -> h
22 -> k
30 -> 7
 8 -> g
 3 -> r
 2 -> z
12 -> v
 5 -> 9
25 -> e
 0 -> q

We are DONE!

lightning:common/bech32_util.c

#include "config.h"
#include <ccan/tal/str/str.h>
#include <common/bech32.h>
#include <common/bech32_util.h>

static u8 get_bit(const u8 *src, size_t bitoff)
{
        return ((src[bitoff / 8] >> (7 - (bitoff % 8))) & 1);
}

void bech32_push_bits(u5 **data, const void *src, size_t nbits)
{
        size_t i, b;
        size_t data_len = tal_count(*data);

        for (i = 0; i < nbits; i += b) {
                tal_resize(data, data_len+1);
                (*data)[data_len] = 0;
                for (b = 0; b < 5; b++) {
                        (*data)[data_len] <<= 1;
                        /* If we need bits we don't have, zero */
                        if (i+b < nbits)
                                (*data)[data_len] |= get_bit(src, i+b);
                }
                data_len++;
        }
}

static u8 get_u5_bit(const u5 *src, size_t bitoff)
{
        return ((src[bitoff / 5] >> (4 - (bitoff % 5))) & 1);
}

void bech32_pull_bits(u8 **data, const u5 *src, size_t nbits)
{
        size_t i;
        size_t data_len = tal_count(*data);

        /* We discard trailing bits. */
        for (i = 0; i + 8 <= nbits; i += 8) {
                tal_resize(data, data_len+1);
                (*data)[data_len] = 0;
                for (size_t b = 0; b < 8; b++) {
                        (*data)[data_len] <<= 1;
                        (*data)[data_len] |= get_u5_bit(src, i+b);
                }
                data_len++;
        }
}

/* Returns a char, tracks case. */
static int fixup_char(int c, bool *upper, bool *lower)
{
        if (c >= 'A' && c <= 'Z') {
                *upper = true;
                return c + ('a' - 'A');
        } else if (c >= 'a' && c <= 'z') {
                *lower = true;
        }
        return c;
}

bool from_bech32_charset(const tal_t *ctx,
                         const char *bech32,
                         size_t bech32_len,
                         char **hrp, u8 **data)
{
        u5 *u5data;
        const char *sep;
        bool upper = false, lower = false;
        size_t datalen;

        sep = memchr(bech32, '1', bech32_len);
        if (!sep)
                return false;

        *hrp = tal_strndup(ctx, bech32, sep - bech32);
        for (size_t i = 0; i < strlen(*hrp); i++)
                (*hrp)[i] = fixup_char((*hrp)[i], &upper, &lower);

        datalen = bech32_len - (sep + 1 - bech32);
        u5data = tal_arr(NULL, u5, datalen);
        for (size_t i = 0; i < datalen; i++) {
                int c = sep[1+i];
                if (c < 0 || c > 128)
                        goto fail;
                c = fixup_char(c, &upper, &lower);
                if (bech32_charset_rev[c] == -1)
                        goto fail;
                u5data[i] = bech32_charset_rev[c];
        }

        /* Check case consistency */
        if (upper && lower)
                goto fail;

        *data = tal_arr(ctx, u8, 0);
        bech32_pull_bits(data, u5data, tal_bytelen(u5data) * 5);
        tal_free(u5data);
        return true;

 fail:
        *hrp = tal_free(*hrp);
        tal_free(u5data);
        return false;
}

char *to_bech32_charset(const tal_t *ctx,
                        const char *hrp, const u8 *data)
{
        u5 *u5data = tal_arr(NULL, u5, 0);
        char *ret;

        bech32_push_bits(&u5data, data, tal_bytelen(data) * 8);
        ret = tal_dup_arr(ctx, char, hrp, strlen(hrp),
                          1 + tal_bytelen(u5data) + 1);
        ret[strlen(hrp)] = '1';
        for (size_t i = 0; i < tal_bytelen(u5data); i++)
                ret[strlen(hrp) + 1 + i] = bech32_charset[u5data[i]];
        ret[strlen(hrp) + 1 + tal_bytelen(u5data)] = '\0';
        tal_free(u5data);
        return ret;
}

CCAN_SRC = $(wildcard ccan/ccan/*/*.c)

bech32: bech32.c
        gcc -I. -Iccan $< $(CCAN_SRC) -o $@

clean:
        rm bech32

#include <stddef.h>
#include <stdio.h>
#include <ccan/tal/tal.h>
#include <ccan/short_types/short_types.h>

/* Type to annotate a 5 bit value. */
typedef unsigned char u5;

const char bech32_charset[] = "qpzry9x8gf2tvdw0s3jn54khce6mua7l";

static u8 get_bit(const u8 *src, size_t bit)
{
  return (src[(bit / 8)] >> (7 - (bit % 8))) & 1;
}

u5 *u8_to_u5(const u8 *src, size_t nbits)
{
  size_t i, b;
  u5 * u5data = tal_arr(NULL, u5, 0);
  size_t u5data_len = 0;

  for (i=0; i < nbits; i +=b){
    tal_resize(&u5data, u5data_len + 1);
    u5data[u5data_len] = 0;
    for (b=0; b < 5; b++){
      u5data[u5data_len] <<= 1;
      if ((i + b) < nbits)
        u5data[u5data_len] |= get_bit(src, i+b);
    }
    u5data_len++;
  }
  return u5data;
}

int main () {

  u8 * src = "foo bar";
  u5 * data = u8_to_u5(src, 56);

  for (size_t i=0; i < tal_count(data); i++){
    printf("%2i -> %c\n", data[i], bech32_charset[data[i]]);
  }

  tal_free(data);
}