From bfae682a08a57ad1bc159d2a8359a528ec12152d Mon Sep 17 00:00:00 2001 From: Vincent Sanders Date: Sun, 25 Sep 2016 23:27:11 +0100 Subject: add some scg documenting how the psl tree is arranged and huffing code done --- docs/huffing.svg | 32646 +++++++++++++++++++++++++++++++++++++++++++++++++++++ docs/psltree.svg | 819 ++ 2 files changed, 33465 insertions(+) create mode 100644 docs/huffing.svg create mode 100644 docs/psltree.svg diff --git a/docs/huffing.svg b/docs/huffing.svg new file mode 100644 index 0000000..c05babd --- /dev/null +++ b/docs/huffing.svg @@ -0,0 +1,32646 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + Input:*!asiabvcomcoopitamazonawsarsaves-the-whalescomputebasilicata + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + h + 2 + + + + b + 2 + + + + - + 2 + + + + v + 2 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + u + 1 + + + + r + 1 + + + + z + 1 + + + + n + 1 + + + + * + 1 + + + + ! + 1 + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + h + 2 + + + + b + 2 + + + + - + 2 + + + + v + 2 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + u + 1 + + + + r + 1 + + + + z + 1 + + + + n + 1 + + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + h + 2 + + + + b + 2 + + + + - + 2 + + + + v + 2 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + u + 1 + + + + r + 1 + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + 2 + + + + z + 1 + + + + n + 1 + + + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + h + 2 + + + + b + 2 + + + + - + 2 + + + + v + 2 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + 2 + + + + z + 1 + + + + n + 1 + + + + + + 2 + + + + u + 1 + + + + r + 1 + + + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + h + 2 + + + + b + 2 + + + + - + 2 + + + + v + 2 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + 2 + + + + z + 1 + + + + n + 1 + + + + + + 2 + + + + u + 1 + + + + r + 1 + + + + + + 4 + + + + + + + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + h + 2 + + + + b + 2 + + + + - + 2 + + + + v + 2 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + 2 + + + + z + 1 + + + + n + 1 + + + + + + 2 + + + + u + 1 + + + + r + 1 + + + + + + 4 + + + + + + + 4 + + + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + h + 2 + + + + b + 2 + + + + - + 2 + + + + v + 2 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + 2 + + + + z + 1 + + + + n + 1 + + + + + + 2 + + + + u + 1 + + + + r + 1 + + + + + + 4 + + + + + + + 4 + + + Round 0 + Round 1 + Round 2 + Round 3 + Round 4 + Round 5 + Round 6 + + + + 4 + + + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + h + 2 + + + + - + 2 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + 2 + + + + z + 1 + + + + n + 1 + + + + + + 2 + + + + u + 1 + + + + r + 1 + + + + + + 4 + + + + + + + 4 + + + Round 7 + + + + 4 + + + + + + b + 2 + + + + v + 2 + + + + 4 + + + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + 2 + + + + z + 1 + + + + n + 1 + + + + + + 2 + + + + u + 1 + + + + r + 1 + + + + + + 4 + + + + + + + 4 + + + Round 8 + + + + 4 + + + + + + b + 2 + + + + v + 2 + + + + 4 + + + + + + h + 2 + + + + - + 2 + + + + 4 + + + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + 2 + + + + z + 1 + + + + n + 1 + + + + + + 2 + + + + u + 1 + + + + r + 1 + + + + + + 4 + + + + + + + 4 + + + Round 9 + + + + 4 + + + + + + b + 2 + + + + v + 2 + + + + 4 + + + + + + h + 2 + + + + - + 2 + + + + 4 + + + 7 + + + + + + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + 2 + + + + z + 1 + + + + n + 1 + + + + + + 2 + + + + u + 1 + + + + r + 1 + + + + + + 4 + + + + + + + 4 + + + Round 10 + + + + 4 + + + + + + b + 2 + + + + v + 2 + + + + 4 + + + + + + h + 2 + + + + - + 2 + + + + 4 + + + 7 + + + + + + 8 + + + + + + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + 2 + + + + z + 1 + + + + n + 1 + + + + + + 2 + + + + u + 1 + + + + r + 1 + + + + + + 4 + + + + + + + 4 + + + Round 11 + + + + 4 + + + + + + b + 2 + + + + v + 2 + + + + 4 + + + + + + h + 2 + + + + - + 2 + + + + 4 + + + 7 + + + + + + 8 + + + + + + 8 + + + + + + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + 2 + + + + z + 1 + + + + n + 1 + + + + + + 2 + + + + u + 1 + + + + r + 1 + + + + + + 4 + + + + + + + 4 + + + Round 12 + + + + 4 + + + + + + b + 2 + + + + v + 2 + + + + 4 + + + + + + h + 2 + + + + - + 2 + + + + 4 + + + 7 + + + + + + 8 + + + + + + 8 + + + + + + 8 + + + + + + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + 2 + + + + z + 1 + + + + n + 1 + + + + + + 2 + + + + u + 1 + + + + r + 1 + + + + + + 4 + + + + + + + 4 + + + Round 13 + + + + 4 + + + + + + b + 2 + + + + v + 2 + + + + 4 + + + + + + h + 2 + + + + - + 2 + + + + 4 + + + 7 + + + + + + 8 + + + + + + 8 + + + + + + 8 + + + + + + 8 + + + + + + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + 2 + + + + z + 1 + + + + n + 1 + + + + + + 2 + + + + u + 1 + + + + r + 1 + + + + + + 4 + + + + + + + 4 + + + Round 14 + + + + 4 + + + + + + b + 2 + + + + v + 2 + + + + 4 + + + + + + h + 2 + + + + - + 2 + + + + 4 + + + 7 + + + + + + 8 + + + + + + 8 + + + + + + 8 + + + + + + 8 + + + + + + 11 + + + + + + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + 2 + + + + z + 1 + + + + n + 1 + + + + + + 2 + + + + u + 1 + + + + r + 1 + + + + + + 4 + + + + + + + 4 + + + Round 15 + + + + 4 + + + + + + b + 2 + + + + v + 2 + + + + 4 + + + + + + h + 2 + + + + - + 2 + + + + 4 + + + 7 + + + + + + 8 + + + + + + 8 + + + + + + 8 + + + + + + 8 + + + + + + 11 + + + + + + 15 + + + + + + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + 2 + + + + z + 1 + + + + n + 1 + + + + + + 2 + + + + u + 1 + + + + r + 1 + + + + + + 4 + + + + + + + 4 + + + Round 16 + + + + 4 + + + + + + b + 2 + + + + v + 2 + + + + 4 + + + + + + h + 2 + + + + - + 2 + + + + 4 + + + 7 + + + + + + 8 + + + + + + 8 + + + + + + 8 + + + + + + 8 + + + + + + 11 + + + + + + 15 + + + + + + 16 + + + + + + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + 2 + + + + z + 1 + + + + n + 1 + + + + + + 2 + + + + u + 1 + + + + r + 1 + + + + + + 4 + + + + + + + 4 + + + Round 17 + + + + 4 + + + + + + b + 2 + + + + v + 2 + + + + 4 + + + + + + h + 2 + + + + - + 2 + + + + 4 + + + 7 + + + + + + 8 + + + + + + 8 + + + + + + 8 + + + + + + 8 + + + + + + 11 + + + + + + 15 + + + + + + 16 + + + + + + 19 + + + + + + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + 2 + + + + z + 1 + + + + n + 1 + + + + + + 2 + + + + u + 1 + + + + r + 1 + + + + + + 4 + + + + + + + 4 + + + Round 18 + + + + 4 + + + + + + b + 2 + + + + v + 2 + + + + 4 + + + + + + h + 2 + + + + - + 2 + + + + 4 + + + 7 + + + + + + 8 + + + + + + 8 + + + + + + 8 + + + + + + 8 + + + + + + 11 + + + + + + 15 + + + + + + 16 + + + + + + 19 + + + + + + 26 + + + + + + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + 2 + + + + z + 1 + + + + n + 1 + + + + + + 2 + + + + u + 1 + + + + r + 1 + + + + + + 4 + + + + + + + 4 + + + Round 19 + + + + 4 + + + + + + b + 2 + + + + v + 2 + + + + 4 + + + + + + h + 2 + + + + - + 2 + + + + 4 + + + 7 + + + + + + 8 + + + + + + 8 + + + + + + 8 + + + + + + 8 + + + + + + 11 + + + + + + 15 + + + + + + 16 + + + + + + 19 + + + + + + 26 + + + + + + 35 + + + + + + + + + a + 11 + + + + s + 6 + + + + o + 5 + + + + i + 4 + + + + c + 4 + + + + t + 4 + + + + e + 4 + + + + m + 3 + + + + p + 2 + + + + w + 2 + + + + l + 2 + + + + 2 + + + + * + 1 + + + + ! + 1 + + + + + + 2 + + + + z + 1 + + + + n + 1 + + + + + + 2 + + + + u + 1 + + + + r + 1 + + + + + + 4 + + + + + + + 4 + + + Complete + + + + 4 + + + + + + b + 2 + + + + v + 2 + + + + 4 + + + + + + h + 2 + + + + - + 2 + + + + 4 + + + 7 + + + + + + 8 + + + + + + 8 + + + + + + 8 + + + + + + 8 + + + + + + 11 + + + + + + 15 + + + + + + 16 + + + + + + 19 + + + + + + 26 + + + + + + 35 + + + + + + 61 + + + a: 00s: 1111o: 1110i: 0111c: 0110t: 1001e: 1000m: 0100h: 01011-: 01010b: 11001v: 11000p: 11011w: 11010l: 10101u: 101101r: 101100z: 101111n: 101110*: 101001!: 101000 + 1 + 0 + + diff --git a/docs/psltree.svg b/docs/psltree.svg new file mode 100644 index 0000000..1bff511 --- /dev/null +++ b/docs/psltree.svg @@ -0,0 +1,819 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 0 + 4 + 2 + 3 + 4 + 2 + + + + + + + 2 + + + + 16 + + + + + + + 3 + 10 + + + + + + 5 + 3 + 2 + + + + + 9 + + + 1 + + + + 7 + + + + + + + + + + + + + + + + + + + *!asiabvcomcoopitamazonawsarsaves-the-whalescomputebasilicata + union psl_node { struct { unsigned int idx:24; unsigned int len:6; unsigned int children:1; } label; struct { uint16_t index; uint16_t count; } child;}; + + -- cgit v1.2.3