diff options
| -rw-r--r-- | readme.md | 44 |
1 files changed, 20 insertions, 24 deletions
@@ -18,25 +18,18 @@ end. | 0x00 | 0x04 | identifier: “BLoC” | | 0x04 | 0x06 | number of entries | | 0x06 | 0x?? | entries | -| 0x?? | 0x?? | structure | ### Entry -| from | to | content | -|:-----|:-----|:---------------------------| -| 0x00 | 0x?? | bit-encoded BLC expression | +This reflects the basic structure of an expression. It uses the +following derivation of normal bit-encoded BLC: -### Structure - -This reflects the basic structure of the program and can’t use -variables. Instead, the structure entry uses the following derivation of -normal bit-encoded BLC: - -| prefix | content | -|:-------|:------------------------------| -| 00M | abstraction of expression `M` | -| 01MN | application of `M` and `N` | -| 1I | 2 byte index to an entry | +| prefix | content | +|:-----------------|:------------------------------| +| 00M | abstraction of expression `M` | +| 010MN | application of `M` and `N` | +| 1<sup>i+1</sup>0 | bruijn index `i` | +| 011I | 2 byte index to an entry | ## Example @@ -48,13 +41,16 @@ obviously has the drawback of redundant repetition of `M` and `N`. A possible encoding in BLoC: -| from | to | content | -|:-----|:-----|:---------------------------------------------------------------------------| -| 0x00 | 0x04 | “BLoC” | -| 0x04 | 0x06 | number of entries: 2 | -| 0x06 | 0x16 | `M` in BLC | -| 0x16 | 0x26 | `N` in BLC | -| 0x26 | 0x32 | `000101011<M>001<N>1<M>1<N>`, where `<M>=0` and `<N>=1` are 2 byte indices | +| from | to | content | +|:-----|:-----|:--------------------------------------------------------------------------------------| +| 0x00 | 0x04 | “BLoC” | +| 0x04 | 0x06 | number of entries: 2 | +| 0x06 | 0x16 | encoded `M` | +| 0x16 | 0x26 | encoded `N` | +| 0x26 | 0x33 | `00010010010011<M>00011<N>011<M>011<N>`, where `<M>=0` and `<N>=1` are 2 byte indices | + +Even in this small example BLoC uses less space than BLC (0x33 vs. 0x42 +bytes). Depending on the values of `M` and `N`, this could have +potentially been compressed even more. -Even in this small example BLoC uses less space than BLC (0x32 vs. 0x42 -bytes). +The compressor in this project uses Merkle trees to accomplish this. |