ref: f828186cec93b2f4ddcd18bc22ab1dcb1b6f3f1f
parent: 37a53d4658e02914020e2bd45c56c6afab7d2e56
author: lieff <lieff@users.noreply.github.com>
date: Fri May 11 08:36:18 EDT 2018
add Huffman optimization code
--- /dev/null
+++ b/huffopt/HUFFCODE
@@ -1,0 +1,1506 @@
+#########################################################################
+# Huffman code table for ISO/MPEG Layer 3 Coding #
+# Syntax: table head: #
+# .table number xlen ylen linbits #
+# .referenz referenz table number (if no table data) #
+# #
+# table data: #
+#########################################################################
+
+.table 0 0 0 0
+#val hlen hcod
+
+.table 1 2 2 0
+#x y hlen hcod
+ 0 0 1 1
+ 0 1 3 001
+ 1 0 2 01
+ 1 1 3 000
+
+.table 2 3 3 0
+ 0 0 1 1
+ 0 1 3 010
+ 0 2 6 000001
+ 1 0 3 011
+ 1 1 3 001
+ 1 2 5 00001
+ 2 0 5 00011
+ 2 1 5 00010
+ 2 2 6 000000
+
+.table 3 3 3 0
+ 0 0 2 11
+ 0 1 2 10
+ 0 2 6 000001
+ 1 0 3 001
+ 1 1 2 01
+ 1 2 5 00001
+ 2 0 5 00011
+ 2 1 5 00010
+ 2 2 6 000000
+
+.table 4 0 0 0
+#not usedwanz
+
+.table 5 4 4 0
+ 0 0 1 1
+ 0 1 3 010
+ 0 2 6 000110
+ 0 3 7 0000101
+ 1 0 3 011
+ 1 1 3 001
+ 1 2 6 000100
+ 1 3 7 0000100
+ 2 0 6 000111
+ 2 1 6 000101
+ 2 2 7 0000111
+ 2 3 8 00000001
+ 3 0 7 0000110
+ 3 1 6 000001
+ 3 2 7 0000001
+ 3 3 8 00000000
+
+.table 6 4 4 0
+ 0 0 3 111
+ 0 1 3 011
+ 0 2 5 00101
+ 0 3 7 0000001
+ 1 0 3 110
+ 1 1 2 10
+ 1 2 4 0011
+ 1 3 5 00010
+ 2 0 4 0101
+ 2 1 4 0100
+ 2 2 5 00100
+ 2 3 6 000001
+ 3 0 6 000011
+ 3 1 5 00011
+ 3 2 6 000010
+ 3 3 7 0000000
+
+.table 7 6 6 0
+ 0 0 1 1
+ 0 1 3 010
+ 0 2 6 001010
+ 0 3 8 00010011
+ 0 4 8 00010000
+ 0 5 9 000001010
+ 1 0 3 011
+ 1 1 4 0011
+ 1 2 6 000111
+ 1 3 7 0001010
+ 1 4 7 0000101
+ 1 5 8 00000011
+ 2 0 6 001011
+ 2 1 5 00100
+ 2 2 7 0001101
+ 2 3 8 00010001
+ 2 4 8 00001000
+ 2 5 9 000000100
+ 3 0 7 0001100
+ 3 1 7 0001011
+ 3 2 8 00010010
+ 3 3 9 000001111
+ 3 4 9 000001011
+ 3 5 9 000000010
+ 4 0 7 0000111
+ 4 1 7 0000110
+ 4 2 8 00001001
+ 4 3 9 000001110
+ 4 4 9 000000011
+ 4 5 10 0000000001
+ 5 0 8 00000110
+ 5 1 8 00000100
+ 5 2 9 000000101
+ 5 3 10 0000000011
+ 5 4 10 0000000010
+ 5 5 10 0000000000
+
+.table 8 6 6 0
+ 0 0 2 11
+ 0 1 3 100
+ 0 2 6 000110
+ 0 3 8 00010010
+ 0 4 8 00001100
+ 0 5 9 000000101
+ 1 0 3 101
+ 1 1 2 01
+ 1 2 4 0010
+ 1 3 8 00010000
+ 1 4 8 00001001
+ 1 5 8 00000011
+ 2 0 6 000111
+ 2 1 4 0011
+ 2 2 6 000101
+ 2 3 8 00001110
+ 2 4 8 00000111
+ 2 5 9 000000011
+ 3 0 8 00010011
+ 3 1 8 00010001
+ 3 2 8 00001111
+ 3 3 9 000001101
+ 3 4 9 000001010
+ 3 5 10 0000000100
+ 4 0 8 00001101
+ 4 1 7 0000101
+ 4 2 8 00001000
+ 4 3 9 000001011
+ 4 4 10 0000000101
+ 4 5 10 0000000001
+ 5 0 9 000001100
+ 5 1 8 00000100
+ 5 2 9 000000100
+ 5 3 9 000000001
+ 5 4 11 00000000001
+ 5 5 11 00000000000
+
+.table 9 6 6 0
+ 0 0 3 111
+ 0 1 3 101
+ 0 2 5 01001
+ 0 3 6 001110
+ 0 4 8 00001111
+ 0 5 9 000000111
+ 1 0 3 110
+ 1 1 3 100
+ 1 2 4 0101
+ 1 3 5 00101
+ 1 4 6 000110
+ 1 5 8 00000111
+ 2 0 4 0111
+ 2 1 4 0110
+ 2 2 5 01000
+ 2 3 6 001000
+ 2 4 7 0001000
+ 2 5 8 00000101
+ 3 0 6 001111
+ 3 1 5 00110
+ 3 2 6 001001
+ 3 3 7 0001010
+ 3 4 7 0000101
+ 3 5 8 00000001
+ 4 0 7 0001011
+ 4 1 6 000111
+ 4 2 7 0001001
+ 4 3 7 0000110
+ 4 4 8 00000100
+ 4 5 9 000000001
+ 5 0 8 00001110
+ 5 1 7 0000100
+ 5 2 8 00000110
+ 5 3 8 00000010
+ 5 4 9 000000110
+ 5 5 9 000000000
+
+.table 10 8 8 0
+ 0 0 1 1
+ 0 1 3 010
+ 0 2 6 001010
+ 0 3 8 00010111
+ 0 4 9 000100011
+ 0 5 9 000011110
+ 0 6 9 000001100
+ 0 7 10 0000010001
+ 1 0 3 011
+ 1 1 4 0011
+ 1 2 6 001000
+ 1 3 7 0001100
+ 1 4 8 00010010
+ 1 5 9 000010101
+ 1 6 8 00001100
+ 1 7 8 00000111
+ 2 0 6 001011
+ 2 1 6 001001
+ 2 2 7 0001111
+ 2 3 8 00010101
+ 2 4 9 000100000
+ 2 5 10 0000101000
+ 2 6 9 000010011
+ 2 7 9 000000110
+ 3 0 7 0001110
+ 3 1 7 0001101
+ 3 2 8 00010110
+ 3 3 9 000100010
+ 3 4 10 0000101110
+ 3 5 10 0000010111
+ 3 6 9 000010010
+ 3 7 10 0000000111
+ 4 0 8 00010100
+ 4 1 8 00010011
+ 4 2 9 000100001
+ 4 3 10 0000101111
+ 4 4 10 0000011011
+ 4 5 10 0000010110
+ 4 6 10 0000001001
+ 4 7 10 0000000011
+ 5 0 9 000011111
+ 5 1 9 000010110
+ 5 2 10 0000101001
+ 5 3 10 0000011010
+ 5 4 11 00000010101
+ 5 5 11 00000010100
+ 5 6 10 0000000101
+ 5 7 11 00000000011
+ 6 0 8 00001110
+ 6 1 8 00001101
+ 6 2 9 000001010
+ 6 3 10 0000001011
+ 6 4 10 0000010000
+ 6 5 10 0000000110
+ 6 6 11 00000000101
+ 6 7 11 00000000001
+ 7 0 9 000001001
+ 7 1 8 00001000
+ 7 2 9 000000111
+ 7 3 10 0000001000
+ 7 4 10 0000000100
+ 7 5 11 00000000100
+ 7 6 11 00000000010
+ 7 7 11 00000000000
+
+.table 11 8 8 0
+ 0 0 2 11
+ 0 1 3 100
+ 0 2 5 01010
+ 0 3 7 0011000
+ 0 4 8 00100010
+ 0 5 9 000100001
+ 0 6 8 00010101
+ 0 7 9 000001111
+ 1 0 3 101
+ 1 1 3 011
+ 1 2 4 0100
+ 1 3 6 001010
+ 1 4 8 00100000
+ 1 5 8 00010001
+ 1 6 7 0001011
+ 1 7 8 00001010
+ 2 0 5 01011
+ 2 1 5 00111
+ 2 2 6 001101
+ 2 3 7 0010010
+ 2 4 8 00011110
+ 2 5 9 000011111
+ 2 6 8 00010100
+ 2 7 8 00000101
+ 3 0 7 0011001
+ 3 1 6 001011
+ 3 2 7 0010011
+ 3 3 9 000111011
+ 3 4 8 00011011
+ 3 5 10 0000010010
+ 3 6 8 00001100
+ 3 7 9 000000101
+ 4 0 8 00100011
+ 4 1 8 00100001
+ 4 2 8 00011111
+ 4 3 9 000111010
+ 4 4 9 000011110
+ 4 5 10 0000010000
+ 4 6 9 000000111
+ 4 7 10 0000000101
+ 5 0 8 00011100
+ 5 1 8 00011010
+ 5 2 9 000100000
+ 5 3 10 0000010011
+ 5 4 10 0000010001
+ 5 5 11 00000001111
+ 5 6 10 0000001000
+ 5 7 11 00000001110
+ 6 0 8 00001110
+ 6 1 7 0001100
+ 6 2 7 0001001
+ 6 3 8 00001101
+ 6 4 9 000001110
+ 6 5 10 0000001001
+ 6 6 10 0000000100
+ 6 7 10 0000000001
+ 7 0 8 00001011
+ 7 1 7 0000100
+ 7 2 8 00000110
+ 7 3 9 000000110
+ 7 4 10 0000000110
+ 7 5 10 0000000011
+ 7 6 10 0000000010
+ 7 7 10 0000000000
+
+.table 12 8 8 0
+ 0 0 4 1001
+ 0 1 3 110
+ 0 2 5 10000
+ 0 3 7 0100001
+ 0 4 8 00101001
+ 0 5 9 000100111
+ 0 6 9 000100110
+ 0 7 9 000011010
+ 1 0 3 111
+ 1 1 3 101
+ 1 2 4 0110
+ 1 3 5 01001
+ 1 4 7 0010111
+ 1 5 7 0010000
+ 1 6 8 00011010
+ 1 7 8 00001011
+ 2 0 5 10001
+ 2 1 4 0111
+ 2 2 5 01011
+ 2 3 6 001110
+ 2 4 7 0010101
+ 2 5 8 00011110
+ 2 6 7 0001010
+ 2 7 8 00000111
+ 3 0 6 010001
+ 3 1 5 01010
+ 3 2 6 001111
+ 3 3 6 001100
+ 3 4 7 0010010
+ 3 5 8 00011100
+ 3 6 8 00001110
+ 3 7 8 00000101
+ 4 0 7 0100000
+ 4 1 6 001101
+ 4 2 7 0010110
+ 4 3 7 0010011
+ 4 4 8 00010010
+ 4 5 8 00010000
+ 4 6 8 00001001
+ 4 7 9 000000101
+ 5 0 8 00101000
+ 5 1 7 0010001
+ 5 2 8 00011111
+ 5 3 8 00011101
+ 5 4 8 00010001
+ 5 5 9 000001101
+ 5 6 8 00000100
+ 5 7 9 000000010
+ 6 0 8 00011011
+ 6 1 7 0001100
+ 6 2 7 0001011
+ 6 3 8 00001111
+ 6 4 8 00001010
+ 6 5 9 000000111
+ 6 6 9 000000100
+ 6 7 10 0000000001
+ 7 0 9 000011011
+ 7 1 8 00001100
+ 7 2 8 00001000
+ 7 3 9 000001100
+ 7 4 9 000000110
+ 7 5 9 000000011
+ 7 6 9 000000001
+ 7 7 10 0000000000
+
+.table 13 16 16 0
+ 0 0 1 1
+ 0 1 4 0101
+ 0 2 6 001110
+ 0 3 7 0010101
+ 0 4 8 00100010
+ 0 5 9 000110011
+ 0 6 9 000101110
+ 0 7 10 0001000111
+ 0 8 9 000101010
+ 0 9 10 0000110100
+ 0 10 11 00001000100
+ 0 11 11 00000110100
+ 0 12 12 000001000011
+ 0 13 12 000000101100
+ 0 14 13 0000000101011
+ 0 15 13 0000000010011
+ 1 0 3 011
+ 1 1 4 0100
+ 1 2 6 001100
+ 1 3 7 0010011
+ 1 4 8 00011111
+ 1 5 8 00011010
+ 1 6 9 000101100
+ 1 7 9 000100001
+ 1 8 9 000011111
+ 1 9 9 000011000
+ 1 10 10 0000100000
+ 1 11 10 0000011000
+ 1 12 11 00000011111
+ 1 13 12 000000100011
+ 1 14 12 000000010110
+ 1 15 12 000000001110
+ 2 0 6 001111
+ 2 1 6 001101
+ 2 2 7 0010111
+ 2 3 8 00100100
+ 2 4 9 000111011
+ 2 5 9 000110001
+ 2 6 10 0001001101
+ 2 7 10 0001000001
+ 2 8 9 000011101
+ 2 9 10 0000101000
+ 2 10 10 0000011110
+ 2 11 11 00000101000
+ 2 12 11 00000011011
+ 2 13 12 000000100001
+ 2 14 13 0000000101010
+ 2 15 13 0000000010000
+ 3 0 7 0010110
+ 3 1 7 0010100
+ 3 2 8 00100101
+ 3 3 9 000111101
+ 3 4 9 000111000
+ 3 5 10 0001001111
+ 3 6 10 0001001001
+ 3 7 10 0001000000
+ 3 8 10 0000101011
+ 3 9 11 00001001100
+ 3 10 11 00000111000
+ 3 11 11 00000100101
+ 3 12 11 00000011010
+ 3 13 12 000000011111
+ 3 14 13 0000000011001
+ 3 15 13 0000000001110
+ 4 0 8 00100011
+ 4 1 7 0010000
+ 4 2 9 000111100
+ 4 3 9 000111001
+ 4 4 10 0001100001
+ 4 5 10 0001001011
+ 4 6 11 00001110010
+ 4 7 11 00001011011
+ 4 8 10 0000110110
+ 4 9 11 00001001001
+ 4 10 11 00000110111
+ 4 11 12 000000101001
+ 4 12 12 000000110000
+ 4 13 13 0000000110101
+ 4 14 13 0000000010111
+ 4 15 14 00000000011000
+ 5 0 9 000111010
+ 5 1 8 00011011
+ 5 2 9 000110010
+ 5 3 10 0001100000
+ 5 4 10 0001001100
+ 5 5 10 0001000110
+ 5 6 11 00001011101
+ 5 7 11 00001010100
+ 5 8 11 00001001101
+ 5 9 11 00000111010
+ 5 10 12 000001001111
+ 5 11 11 00000011101
+ 5 12 13 0000001001010
+ 5 13 13 0000000110001
+ 5 14 14 00000000101001
+ 5 15 14 00000000010001
+ 6 0 9 000101111
+ 6 1 9 000101101
+ 6 2 10 0001001110
+ 6 3 10 0001001010
+ 6 4 11 00001110011
+ 6 5 11 00001011110
+ 6 6 11 00001011010
+ 6 7 11 00001001111
+ 6 8 11 00001000101
+ 6 9 12 000001010011
+ 6 10 12 000001000111
+ 6 11 12 000000110010
+ 6 12 13 0000000111011
+ 6 13 13 0000000100110
+ 6 14 14 00000000100100
+ 6 15 14 00000000001111
+ 7 0 10 0001001000
+ 7 1 9 000100010
+ 7 2 10 0000111000
+ 7 3 11 00001011111
+ 7 4 11 00001011100
+ 7 5 11 00001010101
+ 7 6 12 000001011011
+ 7 7 12 000001011010
+ 7 8 12 000001010110
+ 7 9 12 000001001001
+ 7 10 13 0000001001101
+ 7 11 13 0000001000001
+ 7 12 13 0000000110011
+ 7 13 14 00000000101100
+ 7 14 16 0000000000101011
+ 7 15 16 0000000000101010
+ 8 0 9 000101011
+ 8 1 8 00010100
+ 8 2 9 000011110
+ 8 3 10 0000101100
+ 8 4 10 0000110111
+ 8 5 11 00001001110
+ 8 6 11 00001001000
+ 8 7 12 000001010111
+ 8 8 12 000001001110
+ 8 9 12 000000111101
+ 8 10 12 000000101110
+ 8 11 13 0000000110110
+ 8 12 13 0000000100101
+ 8 13 14 00000000011110
+ 8 14 15 000000000010100
+ 8 15 15 000000000010000
+ 9 0 10 0000110101
+ 9 1 9 000011001
+ 9 2 10 0000101001
+ 9 3 10 0000100101
+ 9 4 11 00000101100
+ 9 5 11 00000111011
+ 9 6 11 00000110110
+ 9 7 13 0000001010001
+ 9 8 12 000001000010
+ 9 9 13 0000001001100
+ 9 10 13 0000000111001
+ 9 11 14 00000000110110
+ 9 12 14 00000000100101
+ 9 13 14 00000000010010
+ 9 14 16 0000000000100111
+ 9 15 15 000000000001011
+10 0 10 0000100011
+10 1 10 0000100001
+10 2 10 0000011111
+10 3 11 00000111001
+10 4 11 00000101010
+10 5 12 000001010010
+10 6 12 000001001000
+10 7 13 0000001010000
+10 8 12 000000101111
+10 9 13 0000000111010
+10 10 14 00000000110111
+10 11 13 0000000010101
+10 12 14 00000000010110
+10 13 15 000000000011010
+10 14 16 0000000000100110
+10 15 17 00000000000010110
+11 0 11 00000110101
+11 1 10 0000011001
+11 2 10 0000010111
+11 3 11 00000100110
+11 4 12 000001000110
+11 5 12 000000111100
+11 6 12 000000110011
+11 7 12 000000100100
+11 8 13 0000000110111
+11 9 13 0000000011010
+11 10 13 0000000100010
+11 11 14 00000000010111
+11 12 15 000000000011011
+11 13 15 000000000001110
+11 14 15 000000000001001
+11 15 16 0000000000000111
+12 0 11 00000100010
+12 1 11 00000100000
+12 2 11 00000011100
+12 3 12 000000100111
+12 4 12 000000110001
+12 5 13 0000001001011
+12 6 12 000000011110
+12 7 13 0000000110100
+12 8 14 00000000110000
+12 9 14 00000000101000
+12 10 15 000000000110100
+12 11 15 000000000011100
+12 12 15 000000000010010
+12 13 16 0000000000010001
+12 14 16 0000000000001001
+12 15 16 0000000000000101
+13 0 12 000000101101
+13 1 11 00000010101
+13 2 12 000000100010
+13 3 13 0000001000000
+13 4 13 0000000111000
+13 5 13 0000000110010
+13 6 14 00000000110001
+13 7 14 00000000101101
+13 8 14 00000000011111
+13 9 14 00000000010011
+13 10 14 00000000001100
+13 11 15 000000000001111
+13 12 16 0000000000001010
+13 13 15 000000000000111
+13 14 16 0000000000000110
+13 15 16 0000000000000011
+14 0 13 0000000110000
+14 1 12 000000010111
+14 2 12 000000010100
+14 3 13 0000000100111
+14 4 13 0000000100100
+14 5 13 0000000100011
+14 6 15 000000000110101
+14 7 14 00000000010101
+14 8 14 00000000010000
+14 9 17 00000000000010111
+14 10 15 000000000001101
+14 11 15 000000000001010
+14 12 15 000000000000110
+14 13 17 00000000000000001
+14 14 16 0000000000000100
+14 15 16 0000000000000010
+15 0 12 000000010000
+15 1 12 000000001111
+15 2 13 0000000010001
+15 3 14 00000000011011
+15 4 14 00000000011001
+15 5 14 00000000010100
+15 6 15 000000000011101
+15 7 14 00000000001011
+15 8 15 000000000010001
+15 9 15 000000000001100
+15 10 16 0000000000010000
+15 11 16 0000000000001000
+15 12 19 0000000000000000001
+15 13 18 000000000000000001
+15 14 19 0000000000000000000
+15 15 16 0000000000000001
+
+.table 14 0 0 0
+#not used
+
+.table 15 16 16 0
+ 0 0 3 111
+ 0 1 4 1100
+ 0 2 5 10010
+ 0 3 7 0110101
+ 0 4 7 0101111
+ 0 5 8 01001100
+ 0 6 9 001111100
+ 0 7 9 001101100
+ 0 8 9 001011001
+ 0 9 10 0001111011
+ 0 10 10 0001101100
+ 0 11 11 00001110111
+ 0 12 11 00001101011
+ 0 13 11 00001010001
+ 0 14 12 000001111010
+ 0 15 13 0000000111111
+ 1 0 4 1101
+ 1 1 3 101
+ 1 2 5 10000
+ 1 3 6 011011
+ 1 4 7 0101110
+ 1 5 7 0100100
+ 1 6 8 00111101
+ 1 7 8 00110011
+ 1 8 8 00101010
+ 1 9 9 001000110
+ 1 10 9 000110100
+ 1 11 10 0001010011
+ 1 12 10 0001000001
+ 1 13 10 0000101001
+ 1 14 11 00000111011
+ 1 15 11 00000100100
+ 2 0 5 10011
+ 2 1 5 10001
+ 2 2 5 01111
+ 2 3 6 011000
+ 2 4 7 0101001
+ 2 5 7 0100010
+ 2 6 8 00111011
+ 2 7 8 00110000
+ 2 8 8 00101000
+ 2 9 9 001000000
+ 2 10 9 000110010
+ 2 11 10 0001001110
+ 2 12 10 0000111110
+ 2 13 11 00001010000
+ 2 14 11 00000111000
+ 2 15 11 00000100001
+ 3 0 6 011101
+ 3 1 6 011100
+ 3 2 6 011001
+ 3 3 7 0101011
+ 3 4 7 0100111
+ 3 5 8 00111111
+ 3 6 8 00110111
+ 3 7 9 001011101
+ 3 8 9 001001100
+ 3 9 9 000111011
+ 3 10 10 0001011101
+ 3 11 10 0001001000
+ 3 12 10 0000110110
+ 3 13 11 00001001011
+ 3 14 11 00000110010
+ 3 15 11 00000011101
+ 4 0 7 0110100
+ 4 1 6 010110
+ 4 2 7 0101010
+ 4 3 7 0101000
+ 4 4 8 01000011
+ 4 5 8 00111001
+ 4 6 9 001011111
+ 4 7 9 001001111
+ 4 8 9 001001000
+ 4 9 9 000111001
+ 4 10 10 0001011001
+ 4 11 10 0001000101
+ 4 12 10 0000110001
+ 4 13 11 00001000010
+ 4 14 11 00000101110
+ 4 15 11 00000011011
+ 5 0 8 01001101
+ 5 1 7 0100101
+ 5 2 7 0100011
+ 5 3 8 01000010
+ 5 4 8 00111010
+ 5 5 8 00110100
+ 5 6 9 001011011
+ 5 7 9 001001010
+ 5 8 9 000111110
+ 5 9 9 000110000
+ 5 10 10 0001001111
+ 5 11 10 0000111111
+ 5 12 11 00001011010
+ 5 13 11 00000111110
+ 5 14 11 00000101000
+ 5 15 12 000000100110
+ 6 0 9 001111101
+ 6 1 7 0100000
+ 6 2 8 00111100
+ 6 3 8 00111000
+ 6 4 8 00110010
+ 6 5 9 001011100
+ 6 6 9 001001110
+ 6 7 9 001000001
+ 6 8 9 000110111
+ 6 9 10 0001010111
+ 6 10 10 0001000111
+ 6 11 10 0000110011
+ 6 12 11 00001001001
+ 6 13 11 00000110011
+ 6 14 12 000001000110
+ 6 15 12 000000011110
+ 7 0 9 001101101
+ 7 1 8 00110101
+ 7 2 8 00110001
+ 7 3 9 001011110
+ 7 4 9 001011000
+ 7 5 9 001001011
+ 7 6 9 001000010
+ 7 7 10 0001111010
+ 7 8 10 0001011011
+ 7 9 10 0001001001
+ 7 10 10 0000111000
+ 7 11 10 0000101010
+ 7 12 11 00001000000
+ 7 13 11 00000101100
+ 7 14 11 00000010101
+ 7 15 12 000000011001
+ 8 0 9 001011010
+ 8 1 8 00101011
+ 8 2 8 00101001
+ 8 3 9 001001101
+ 8 4 9 001001001
+ 8 5 9 000111111
+ 8 6 9 000111000
+ 8 7 10 0001011100
+ 8 8 10 0001001101
+ 8 9 10 0001000010
+ 8 10 10 0000101111
+ 8 11 11 00001000011
+ 8 12 11 00000110000
+ 8 13 12 000000110101
+ 8 14 12 000000100100
+ 8 15 12 000000010100
+ 9 0 9 001000111
+ 9 1 8 00100010
+ 9 2 9 001000011
+ 9 3 9 000111100
+ 9 4 9 000111010
+ 9 5 9 000110001
+ 9 6 10 0001011000
+ 9 7 10 0001001100
+ 9 8 10 0001000011
+ 9 9 11 00001101010
+ 9 10 11 00001000111
+ 9 11 11 00000110110
+ 9 12 11 00000100110
+ 9 13 12 000000100111
+ 9 14 12 000000010111
+ 9 15 12 000000001111
+10 0 10 0001101101
+10 1 9 000110101
+10 2 9 000110011
+10 3 9 000101111
+10 4 10 0001011010
+10 5 10 0001010010
+10 6 10 0000111010
+10 7 10 0000111001
+10 8 10 0000110000
+10 9 11 00001001000
+10 10 11 00000111001
+10 11 11 00000101001
+10 12 11 00000010111
+10 13 12 000000011011
+10 14 13 0000000111110
+10 15 12 000000001001
+11 0 10 0001010110
+11 1 9 000101010
+11 2 9 000101000
+11 3 9 000100101
+11 4 10 0001000110
+11 5 10 0001000000
+11 6 10 0000110100
+11 7 10 0000101011
+11 8 11 00001000110
+11 9 11 00000110111
+11 10 11 00000101010
+11 11 11 00000011001
+11 12 12 000000011101
+11 13 12 000000010010
+11 14 12 000000001011
+11 15 13 0000000001011
+12 0 11 00001110110
+12 1 10 0001000100
+12 2 9 000011110
+12 3 10 0000110111
+12 4 10 0000110010
+12 5 10 0000101110
+12 6 11 00001001010
+12 7 11 00001000001
+12 8 11 00000110001
+12 9 11 00000100111
+12 10 11 00000011000
+12 11 11 00000010000
+12 12 12 000000010110
+12 13 12 000000001101
+12 14 13 0000000001110
+12 15 13 0000000000111
+13 0 11 00001011011
+13 1 10 0000101100
+13 2 10 0000100111
+13 3 10 0000100110
+13 4 10 0000100010
+13 5 11 00000111111
+13 6 11 00000110100
+13 7 11 00000101101
+13 8 11 00000011111
+13 9 12 000000110100
+13 10 12 000000011100
+13 11 12 000000010011
+13 12 12 000000001110
+13 13 12 000000001000
+13 14 13 0000000001001
+13 15 13 0000000000011
+14 0 12 000001111011
+14 1 11 00000111100
+14 2 11 00000111010
+14 3 11 00000110101
+14 4 11 00000101111
+14 5 11 00000101011
+14 6 11 00000100000
+14 7 11 00000010110
+14 8 12 000000100101
+14 9 12 000000011000
+14 10 12 000000010001
+14 11 12 000000001100
+14 12 13 0000000001111
+14 13 13 0000000001010
+14 14 12 000000000010
+14 15 13 0000000000001
+15 0 12 000001000111
+15 1 11 00000100101
+15 2 11 00000100010
+15 3 11 00000011110
+15 4 11 00000011100
+15 5 11 00000010100
+15 6 11 00000010001
+15 7 12 000000011010
+15 8 12 000000010101
+15 9 12 000000010000
+15 10 12 000000001010
+15 11 12 000000000110
+15 12 13 0000000001000
+15 13 13 0000000000110
+15 14 13 0000000000010
+15 15 13 0000000000000
+
+.table 16 16 16 1
+ 0 0 1 1
+ 0 1 4 0101
+ 0 2 6 001110
+ 0 3 8 00101100
+ 0 4 9 001001010
+ 0 5 9 000111111
+ 0 6 10 0001101110
+ 0 7 10 0001011101
+ 0 8 11 00010101100
+ 0 9 11 00010010101
+ 0 10 11 00010001010
+ 0 11 12 000011110010
+ 0 12 12 000011100001
+ 0 13 12 000011000011
+ 0 14 13 0000101111000
+ 0 15 9 000010001
+ 1 0 3 011
+ 1 1 4 0100
+ 1 2 6 001100
+ 1 3 7 0010100
+ 1 4 8 00100011
+ 1 5 9 000111110
+ 1 6 9 000110101
+ 1 7 9 000101111
+ 1 8 10 0001010011
+ 1 9 10 0001001011
+ 1 10 10 0001000100
+ 1 11 11 00001110111
+ 1 12 12 000011001001
+ 1 13 11 00001101011
+ 1 14 12 000011001111
+ 1 15 8 00001001
+ 2 0 6 001111
+ 2 1 6 001101
+ 2 2 7 0010111
+ 2 3 8 00100110
+ 2 4 9 001000011
+ 2 5 9 000111010
+ 2 6 10 0001100111
+ 2 7 10 0001011010
+ 2 8 11 00010100001
+ 2 9 10 0001001000
+ 2 10 11 00001111111
+ 2 11 11 00001110101
+ 2 12 11 00001101110
+ 2 13 12 000011010001
+ 2 14 12 000011001110
+ 2 15 9 000010000
+ 3 0 8 00101101
+ 3 1 7 0010101
+ 3 2 8 00100111
+ 3 3 9 001000101
+ 3 4 9 001000000
+ 3 5 10 0001110010
+ 3 6 10 0001100011
+ 3 7 10 0001010111
+ 3 8 11 00010011110
+ 3 9 11 00010001100
+ 3 10 12 000011111100
+ 3 11 12 000011010100
+ 3 12 12 000011000111
+ 3 13 13 0000110000011
+ 3 14 13 0000101101101
+ 3 15 10 0000011010
+ 4 0 9 001001011
+ 4 1 8 00100100
+ 4 2 9 001000100
+ 4 3 9 001000001
+ 4 4 10 0001110011
+ 4 5 10 0001100101
+ 4 6 11 00010110011
+ 4 7 11 00010100100
+ 4 8 11 00010011011
+ 4 9 12 000100001000
+ 4 10 12 000011110110
+ 4 11 12 000011100010
+ 4 12 13 0000110001011
+ 4 13 13 0000101111110
+ 4 14 13 0000101101010
+ 4 15 9 000001001
+ 5 0 9 001000010
+ 5 1 8 00011110
+ 5 2 9 000111011
+ 5 3 9 000111000
+ 5 4 10 0001100110
+ 5 5 11 00010111001
+ 5 6 11 00010101101
+ 5 7 12 000100001001
+ 5 8 11 00010001110
+ 5 9 12 000011111101
+ 5 10 12 000011101000
+ 5 11 13 0000110010000
+ 5 12 13 0000110000100
+ 5 13 13 0000101111010
+ 5 14 14 00000110111101
+ 5 15 10 0000010000
+ 6 0 10 0001101111
+ 6 1 9 000110110
+ 6 2 9 000110100
+ 6 3 10 0001100100
+ 6 4 11 00010111000
+ 6 5 11 00010110010
+ 6 6 11 00010100000
+ 6 7 11 00010000101
+ 6 8 12 000100000001
+ 6 9 12 000011110100
+ 6 10 12 000011100100
+ 6 11 12 000011011001
+ 6 12 13 0000110000001
+ 6 13 13 0000101101110
+ 6 14 14 00001011001011
+ 6 15 10 0000001010
+ 7 0 10 0001100010
+ 7 1 9 000110000
+ 7 2 10 0001011011
+ 7 3 10 0001011000
+ 7 4 11 00010100101
+ 7 5 11 00010011101
+ 7 6 11 00010010100
+ 7 7 12 000100000101
+ 7 8 12 000011111000
+ 7 9 13 0000110010111
+ 7 10 13 0000110001101
+ 7 11 13 0000101110100
+ 7 12 13 0000101111100
+ 7 13 15 000001101111001
+ 7 14 15 000001101110100
+ 7 15 10 0000001000
+ 8 0 10 0001010101
+ 8 1 10 0001010100
+ 8 2 10 0001010001
+ 8 3 11 00010011111
+ 8 4 11 00010011100
+ 8 5 11 00010001111
+ 8 6 12 000100000100
+ 8 7 12 000011111001
+ 8 8 13 0000110101011
+ 8 9 13 0000110010001
+ 8 10 13 0000110001000
+ 8 11 13 0000101111111
+ 8 12 14 00001011010111
+ 8 13 14 00001011001001
+ 8 14 14 00001011000100
+ 8 15 10 0000000111
+ 9 0 11 00010011010
+ 9 1 10 0001001100
+ 9 2 10 0001001001
+ 9 3 11 00010001101
+ 9 4 11 00010000011
+ 9 5 12 000100000000
+ 9 6 12 000011110101
+ 9 7 13 0000110101010
+ 9 8 13 0000110010110
+ 9 9 13 0000110001010
+ 9 10 13 0000110000000
+ 9 11 14 00001011011111
+ 9 12 13 0000101100111
+ 9 13 14 00001011000110
+ 9 14 13 0000101100000
+ 9 15 11 00000001011
+10 0 11 00010001011
+10 1 11 00010000001
+10 2 10 0001000011
+10 3 11 00001111101
+10 4 12 000011110111
+10 5 12 000011101001
+10 6 12 000011100101
+10 7 12 000011011011
+10 8 13 0000110001001
+10 9 14 00001011100111
+10 10 14 00001011100001
+10 11 14 00001011010000
+10 12 15 000001101110101
+10 13 15 000001101110010
+10 14 14 00000110110111
+10 15 10 0000000100
+11 0 12 000011110011
+11 1 11 00001111000
+11 2 11 00001110110
+11 3 11 00001110011
+11 4 12 000011100011
+11 5 12 000011011111
+11 6 13 0000110001100
+11 7 14 00001011101010
+11 8 14 00001011100110
+11 9 14 00001011100000
+11 10 14 00001011010001
+11 11 14 00001011001000
+11 12 14 00001011000010
+11 13 13 0000011011111
+11 14 14 00000110110100
+11 15 11 00000000110
+12 0 12 000011001010
+12 1 12 000011100000
+12 2 12 000011011110
+12 3 12 000011011010
+12 4 12 000011011000
+12 5 13 0000110000101
+12 6 13 0000110000010
+12 7 13 0000101111101
+12 8 13 0000101101100
+12 9 15 000001101111000
+12 10 14 00000110111011
+12 11 14 00001011000011
+12 12 14 00000110111000
+12 13 14 00000110110101
+12 14 16 0000011011000000
+12 15 11 00000000100
+13 0 14 00001011101011
+13 1 12 000011010011
+13 2 12 000011010010
+13 3 12 000011010000
+13 4 13 0000101110010
+13 5 13 0000101111011
+13 6 14 00001011011110
+13 7 14 00001011010011
+13 8 14 00001011001010
+13 9 16 0000011011000111
+13 10 15 000001101110011
+13 11 15 000001101101101
+13 12 15 000001101101100
+13 13 17 00000110110000011
+13 14 15 000001101100001
+13 15 11 00000000010
+14 0 13 0000101111001
+14 1 13 0000101110001
+14 2 11 00001100110
+14 3 12 000010111011
+14 4 14 00001011010110
+14 5 14 00001011010010
+14 6 13 0000101100110
+14 7 14 00001011000111
+14 8 14 00001011000101
+14 9 15 000001101100010
+14 10 16 0000011011000110
+14 11 15 000001101100111
+14 12 17 00000110110000010
+14 13 15 000001101100110
+14 14 14 00000110110010
+14 15 11 00000000000
+15 0 9 000001100
+15 1 8 00001010
+15 2 8 00000111
+15 3 9 000001011
+15 4 9 000001010
+15 5 10 0000010001
+15 6 10 0000001011
+15 7 10 0000001001
+15 8 11 00000001101
+15 9 11 00000001100
+15 10 11 00000001010
+15 11 11 00000000111
+15 12 11 00000000101
+15 13 11 00000000011
+15 14 11 00000000001
+15 15 8 00000011
+
+.table 17 16 16 2
+.reference 16
+
+.table 18 16 16 3
+.reference 16
+
+.table 19 16 16 4
+.reference 16
+
+.table 20 16 16 6
+.reference 16
+
+.table 21 16 16 8
+.reference 16
+
+.table 22 16 16 10
+.reference 16
+
+.table 23 16 16 13
+.reference 16
+
+.table 24 16 16 4
+ 0 0 4 1111
+ 0 1 4 1101
+ 0 2 6 101110
+ 0 3 7 1010000
+ 0 4 8 10010010
+ 0 5 9 100000110
+ 0 6 9 011111000
+ 0 7 10 0110110010
+ 0 8 10 0110101010
+ 0 9 11 01010011101
+ 0 10 11 01010001101
+ 0 11 11 01010001001
+ 0 12 11 01001101101
+ 0 13 11 01000000101
+ 0 14 12 010000001000
+ 0 15 9 001011000
+ 1 0 4 1110
+ 1 1 4 1100
+ 1 2 5 10101
+ 1 3 6 100110
+ 1 4 7 1000111
+ 1 5 8 10000010
+ 1 6 8 01111010
+ 1 7 9 011011000
+ 1 8 9 011010001
+ 1 9 9 011000110
+ 1 10 10 0101000111
+ 1 11 10 0101011001
+ 1 12 10 0100111111
+ 1 13 10 0100101001
+ 1 14 10 0100010111
+ 1 15 8 00101010
+ 2 0 6 101111
+ 2 1 5 10110
+ 2 2 6 101001
+ 2 3 7 1001010
+ 2 4 7 1000100
+ 2 5 8 10000000
+ 2 6 8 01111000
+ 2 7 9 011011101
+ 2 8 9 011001111
+ 2 9 9 011000010
+ 2 10 9 010110110
+ 2 11 10 0101010100
+ 2 12 10 0100111011
+ 2 13 10 0100100111
+ 2 14 11 01000011101
+ 2 15 7 0010010
+ 3 0 7 1010001
+ 3 1 6 100111
+ 3 2 7 1001011
+ 3 3 7 1000110
+ 3 4 8 10000110
+ 3 5 8 01111101
+ 3 6 8 01110100
+ 3 7 9 011011100
+ 3 8 9 011001100
+ 3 9 9 010111110
+ 3 10 9 010110010
+ 3 11 10 0101000101
+ 3 12 10 0100110111
+ 3 13 10 0100100101
+ 3 14 10 0100001111
+ 3 15 7 0010000
+ 4 0 8 10010011
+ 4 1 7 1001000
+ 4 2 7 1000101
+ 4 3 8 10000111
+ 4 4 8 01111111
+ 4 5 8 01110110
+ 4 6 8 01110000
+ 4 7 9 011010010
+ 4 8 9 011001000
+ 4 9 9 010111100
+ 4 10 10 0101100000
+ 4 11 10 0101000011
+ 4 12 10 0100110010
+ 4 13 10 0100011101
+ 4 14 11 01000011100
+ 4 15 7 0001110
+ 5 0 9 100000111
+ 5 1 7 1000010
+ 5 2 8 10000001
+ 5 3 8 01111110
+ 5 4 8 01110111
+ 5 5 8 01110010
+ 5 6 9 011010110
+ 5 7 9 011001010
+ 5 8 9 011000000
+ 5 9 9 010110100
+ 5 10 10 0101010101
+ 5 11 10 0100111101
+ 5 12 10 0100101101
+ 5 13 10 0100011001
+ 5 14 10 0100000110
+ 5 15 7 0001100
+ 6 0 9 011111001
+ 6 1 8 01111011
+ 6 2 8 01111001
+ 6 3 8 01110101
+ 6 4 8 01110001
+ 6 5 9 011010111
+ 6 6 9 011001110
+ 6 7 9 011000011
+ 6 8 9 010111001
+ 6 9 10 0101011011
+ 6 10 10 0101001010
+ 6 11 10 0100110100
+ 6 12 10 0100100011
+ 6 13 10 0100010000
+ 6 14 11 01000001000
+ 6 15 7 0001010
+ 7 0 10 0110110011
+ 7 1 8 01110011
+ 7 2 8 01101111
+ 7 3 8 01101101
+ 7 4 9 011010011
+ 7 5 9 011001011
+ 7 6 9 011000100
+ 7 7 9 010111011
+ 7 8 10 0101100001
+ 7 9 10 0101001100
+ 7 10 10 0100111001
+ 7 11 10 0100101010
+ 7 12 10 0100011011
+ 7 13 11 01000010011
+ 7 14 11 00101111101
+ 7 15 8 00010001
+ 8 0 10 0110101011
+ 8 1 9 011010100
+ 8 2 9 011010000
+ 8 3 9 011001101
+ 8 4 9 011001001
+ 8 5 9 011000001
+ 8 6 9 010111010
+ 8 7 9 010110001
+ 8 8 9 010101001
+ 8 9 10 0101000000
+ 8 10 10 0100101111
+ 8 11 10 0100011110
+ 8 12 10 0100001100
+ 8 13 11 01000000010
+ 8 14 11 00101111001
+ 8 15 8 00010000
+ 9 0 10 0101001111
+ 9 1 9 011000111
+ 9 2 9 011000101
+ 9 3 9 010111111
+ 9 4 9 010111101
+ 9 5 9 010110101
+ 9 6 9 010101110
+ 9 7 10 0101001101
+ 9 8 10 0101000001
+ 9 9 10 0100110001
+ 9 10 10 0100100001
+ 9 11 10 0100010011
+ 9 12 11 01000001001
+ 9 13 11 00101111011
+ 9 14 11 00101110011
+ 9 15 8 00001011
+10 0 11 01010011100
+10 1 9 010111000
+10 2 9 010110111
+10 3 9 010110011
+10 4 9 010101111
+10 5 10 0101011000
+10 6 10 0101001011
+10 7 10 0100111010
+10 8 10 0100110000
+10 9 10 0100100010
+10 10 10 0100010101
+10 11 11 01000010010
+10 12 11 00101111111
+10 13 11 00101110101
+10 14 11 00101101110
+10 15 8 00001010
+11 0 11 01010001100
+11 1 10 0101011010
+11 2 9 010101011
+11 3 9 010101000
+11 4 9 010100100
+11 5 10 0100111110
+11 6 10 0100110101
+11 7 10 0100101011
+11 8 10 0100011111
+11 9 10 0100010100
+11 10 10 0100000111
+11 11 11 01000000001
+11 12 11 00101110111
+11 13 11 00101110000
+11 14 11 00101101010
+11 15 8 00000110
+12 0 11 01010001000
+12 1 10 0101000010
+12 2 10 0100111100
+12 3 10 0100111000
+12 4 10 0100110011
+12 5 10 0100101110
+12 6 10 0100100100
+12 7 10 0100011100
+12 8 10 0100001101
+12 9 10 0100000101
+12 10 11 01000000000
+12 11 11 00101111000
+12 12 11 00101110010
+12 13 11 00101101100
+12 14 11 00101100111
+12 15 8 00000100
+13 0 11 01001101100
+13 1 10 0100101100
+13 2 10 0100101000
+13 3 10 0100100110
+13 4 10 0100100000
+13 5 10 0100011010
+13 6 10 0100010001
+13 7 10 0100001010
+13 8 11 01000000011
+13 9 11 00101111100
+13 10 11 00101110110
+13 11 11 00101110001
+13 12 11 00101101101
+13 13 11 00101101001
+13 14 11 00101100101
+13 15 8 00000010
+14 0 12 010000001001
+14 1 10 0100011000
+14 2 10 0100010110
+14 3 10 0100010010
+14 4 10 0100001011
+14 5 10 0100001000
+14 6 10 0100000011
+14 7 11 00101111110
+14 8 11 00101111010
+14 9 11 00101110100
+14 10 11 00101101111
+14 11 11 00101101011
+14 12 11 00101101000
+14 13 11 00101100110
+14 14 11 00101100100
+14 15 8 00000000
+15 0 8 00101011
+15 1 7 0010100
+15 2 7 0010011
+15 3 7 0010001
+15 4 7 0001111
+15 5 7 0001101
+15 6 7 0001011
+15 7 7 0001001
+15 8 7 0000111
+15 9 7 0000110
+15 10 7 0000100
+15 11 8 00000111
+15 12 8 00000101
+15 13 8 00000011
+15 14 8 00000001
+15 15 4 0011
+
+.table 25 16 16 5
+.reference 24
+
+.table 26 16 16 6
+.reference 24
+
+.table 27 16 16 7
+.reference 24
+
+.table 28 16 16 8
+.reference 24
+
+.table 29 16 16 9
+.reference 24
+
+.table 30 16 16 11
+.reference 24
+
+.table 31 16 16 13
+.reference 24
+
+.table 32 1 16 0
+ 0 1 1
+ 1 4 0101
+ 2 4 0100
+ 3 5 00101
+ 4 4 0110
+ 5 6 000101
+ 6 5 00100
+ 7 6 000100
+ 8 4 0111
+ 9 5 00011
+ 10 5 00110
+ 11 6 000000
+ 12 5 00111
+ 13 6 000010
+ 14 6 000011
+ 15 6 000001
+
+.table 33 1 16 0
+ 0 4 1111
+ 1 4 1110
+ 2 4 1101
+ 3 4 1100
+ 4 4 1011
+ 5 4 1010
+ 6 4 1001
+ 7 4 1000
+ 8 4 0111
+ 9 4 0110
+ 10 4 0101
+ 11 4 0100
+ 12 4 0011
+ 13 4 0010
+ 14 4 0001
+ 15 4 0000
+
+.end
--- /dev/null
+++ b/huffopt/huffopt.c
@@ -1,0 +1,348 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include <string.h>
+
+#define WROOT 5 /* fixed width (bits) of root table (MUST also be changed in the decoder C code) */
+#define WMAX 7 /* max width of sub-table */
+#define LAMBDA 512 /* Lagrange multiplier for MIPS/bytes trade-off: 1 table jump cost == LAMBDA bytes. Table cost = # of bytes + LAMBDA * # of jumps */
+#define OPTIMIZE_SIZE 0 /* flag to force LAMBDA==0 (free jumps, table cost == table size) */
+
+#define MIN(a, b) ((a) < (b) ? (a) : (b))
+#define MAX(a, b) ((a) > (b) ? (a) : (b))
+
+typedef struct huff_t
+{+ struct huff_t *link;
+ struct huff_t *parent;
+ struct huff_t *child[2];
+ int level;
+ unsigned symbol;
+ unsigned code;
+
+ struct
+ {+ int best_width, size;
+ float mips;
+ } dp;
+
+ int backref;
+ int offset;
+
+ enum { E_PAIR, E_QUAD } symbol_kind;+} huff_t;
+
+static int is_leaf(const huff_t *h)
+{+ return !h->child[0] && !h->child[1];
+}
+
+static int imax(int a, int b)
+{+ return MAX(a, b);
+}
+
+static char *BIT_str(unsigned x, int bits)
+{ // Print x as bitpattern: 01 (LBS bits)+ static int idx;
+ static char buf[8][33]; // up to 8 simultaneous numbers
+ char *p = buf[++idx & 7];
+ while (bits--)
+ {+ *p++ = "01"[(x >> bits) & 1];
+ }
+ *p++ = 0;
+ return buf[idx & 7];
+}
+
+huff_t *huff_create(huff_t *h, unsigned symbol, unsigned code, int code_len, int level, int symbol_kind)
+{+ if (!h)
+ {+ h = (huff_t*)calloc(1, sizeof(huff_t));
+ h->level = level;
+ h->symbol = code_len ? ~0 : symbol;
+ h->code = code_len ? ~0 : code;
+ h->dp.size = 1;
+ h->dp.mips = 1.f/(1 << level);
+ h->backref = -1;
+ h->symbol_kind = symbol_kind;
+ }
+ if (h && code_len > 0)
+ {+ int bit = (code >> --code_len) & 1;
+ h->child[bit] = huff_create(h->child[bit], symbol, code, code_len, level + 1, symbol_kind);
+ }
+ return h;
+}
+
+void huff_free(huff_t *h)
+{+ if (h)
+ {+ huff_free(h->child[0]);
+ huff_free(h->child[1]);
+ free(h);
+ }
+}
+
+huff_t *read_codebook(int book)
+{+ FILE *f = fopen("HUFFCODE", "rt");+ huff_t *tree = NULL;
+ int tab = -1, mx, my, lin;
+ do
+ {+ if (4 != fscanf(f, "\n.table %d %d %d %d", &tab, &mx, &my, &lin))
+ {+ fscanf(f, "%*[^\n]");
+ }
+ } while(tab != book && !feof(f));
+ if (tab == book)
+ {+ int i, j;
+ for (i = 0; i < mx*my; i++)
+ {+ int x, y, len, icode = 0;
+ char code[30];
+ if (book < 32)
+ {+ while (4 != fscanf(f, "\n%d %d %d %s", &x, &y, &len, code))
+ {+ fscanf(f, "%*[^\n]");
+ }
+ } else
+ {+ x = 0;
+ while (3 != fscanf(f, "\n%d %d %s", &y, &len, code))
+ {+ fscanf(f, "%*[^\n]");
+ }
+ }
+ for (j = 0; j < len; j++)
+ {+ icode <<= 1;
+ icode |= code[j] - '0';
+ }
+
+ tree = huff_create(tree, (x << 16) + y, icode, len, 0, book < 32 ? E_PAIR : E_QUAD);
+ }
+ }
+ fclose(f);
+ return tree;
+}
+
+int huff_symbols_count(const huff_t *h)
+{+ return h ? is_leaf(h) + huff_symbols_count(h->child[0]) + huff_symbols_count(h->child[1]) : 0;
+}
+
+int huff_depth(const huff_t *h)
+{+ return is_leaf(h) ? 0 : (1 + imax(huff_depth(h->child[0]), huff_depth(h->child[1])));
+}
+
+int huff_size(const huff_t *h, int depth)
+{+ return is_leaf(h) ? 0 : (--depth < 0) ? h->dp.size : huff_size(h->child[0], depth) + huff_size(h->child[1], depth);
+}
+
+float huff_cost(const huff_t *h, int depth)
+{+ return is_leaf(h) ? 0 : (--depth < 0) ? h->dp.mips : huff_cost(h->child[0], depth) + huff_cost(h->child[1], depth);
+}
+
+const huff_t *huff_decode(const huff_t *h, unsigned code, int code_len)
+{+ return (!code_len || is_leaf(h)) ? h : huff_decode(h->child[(code >> (code_len - 1)) & 1], code, code_len - 1);
+}
+
+void huff_optimize_partition(huff_t *h)
+{+ int i, depth, wmin, wmax;
+ if (h && !is_leaf(h))
+ {+ // DP call:
+ huff_optimize_partition(h->child[0]);
+ huff_optimize_partition(h->child[1]);
+ depth = huff_depth(h);
+
+ wmin = h->level ? 1 : WROOT;
+ wmax = wmin > 1 ? wmin : MIN(depth, WMAX);
+
+ if (h->symbol_kind == E_QUAD && !h->level)
+ {+ wmax = wmin = 4;
+ }
+
+ h->dp.size = huff_size(h, h->dp.best_width = wmin) + (1 << wmin);
+ h->dp.mips = huff_cost(h, h->dp.best_width = wmin) + 1.f/(1 << h->level);
+
+ for (i = wmin + 1; i <= wmax; i++)
+ {+ int size = huff_size(h, i) + (1 << i);
+ float mips = huff_cost(h, i) + 1.f/(1 << h->level);
+ float cost_i;
+ float cost_have;
+
+ cost_i = mips*LAMBDA + size;
+ cost_have = h->dp.mips*LAMBDA + h->dp.size;
+#if OPTIMIZE_SIZE
+ cost_i = (float)size;
+ cost_have = (float)h->dp.size;
+#endif
+
+ if (cost_i < cost_have)
+ {+ h->dp.best_width = i;
+ h->dp.size = size;
+ h->dp.mips = mips;
+ }
+ }
+ }
+}
+
+void huff_print_one(const huff_t *h, FILE *f, int parent_level)
+{+ if (h->symbol_kind == E_PAIR)
+ {+ if (is_leaf(h))
+ {+ int x = h->symbol << 16 >> 16;
+ int y = h->symbol << 0 >> 16;
+ fprintf(f, "%d,", ((h->level - parent_level)*256 + (x << 4) + (y << 0)));
+ } else
+ {+ assert(h->offset < (1 << 13));
+ assert(h->offset);
+ fprintf(f, "%d,", (-h->offset << 3) | h->dp.best_width);
+ }
+ } else
+ {+ if (is_leaf(h))
+ {+ fprintf(f, "%d,", (h->symbol*16 + 8 + h->level));
+ } else
+ {+ fprintf(f, "%d,", (h->offset << 3) | h->dp.best_width);
+ //fprintf(f, "[%d,%d]", h->offset , h->dp.best_width);
+ }
+ }
+}
+
+void huff_set_links_bfs(huff_t *h, FILE *f)
+{+ int print_flag;
+ for (print_flag = 0; print_flag <= 1; print_flag++)
+ {+ huff_t *q = h;
+ huff_t *queue_head = NULL;
+ huff_t **queue_tail = &queue_head;
+ int offs = 0;
+ while (q)
+ {+ int i, w = 1 << q->dp.best_width;
+ for (i = 0; i < w; i++)
+ {+ huff_t *r = (huff_t *)huff_decode(q, i, q->dp.best_width);
+ if (print_flag)
+ {+ huff_print_one(r, f, q->level);
+ }
+
+ if (!is_leaf(r))
+ {+ r->backref = offs;// + i;
+ *queue_tail = r;
+ queue_tail = &r->link;
+ }
+ }
+ offs += w;
+ q = queue_head;
+ if (q)
+ {+ if ((queue_head = q->link) != NULL)
+ {+ queue_tail = &queue_head;
+ }
+ q->offset = offs;// - q->backref;
+ }
+ }
+ }
+}
+
+void huff_set_links_dfs_recursion(huff_t *h, FILE *f, int print_flag, int *off)
+{+ int i, w = 1 << h->dp.best_width;
+ h->offset = *off;
+ *off += w;
+ for (i = 0; print_flag && i < w; i++)
+ {+ huff_print_one(huff_decode(h, i, h->dp.best_width), f, h->level);
+ }
+ for (i = 0; i < w; i++)
+ {+ huff_t *q = (huff_t *)huff_decode(h, i, h->dp.best_width);
+ if (!is_leaf(q))
+ {+ huff_set_links_dfs_recursion(q, f, print_flag, off);
+ }
+ }
+}
+
+void huff_set_links_dfs(huff_t *h, FILE *f)
+{+ int off = 0;
+ huff_set_links_dfs_recursion(h, f, 0, &off);
+ huff_set_links_dfs_recursion(h, f, 1, &off);
+};
+
+int main()
+{+ int i;
+ const int tabn[] = { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,24,32,33 };+ int total_size = 0;
+ int entry_bits[32];
+
+ FILE *dst_file = fopen("Huffman_tree.inl", "wt");+
+ for (i = 0; i < sizeof(tabn)/sizeof(tabn[0]); i++)
+ {+ huff_t *h = read_codebook(tabn[i]);
+ huff_optimize_partition(h);
+
+ printf("\ntable %2d ", tabn[i]);+ printf("%3d symbols ", huff_symbols_count(h));+ printf("%3d items ", h ? h->dp.size : 0);+ printf("%1d entry ", h ? h->dp.best_width : 0);+ printf("%f average memory reads ", h ? h->dp.mips : 0);+ total_size += h ? h->dp.size : 0;
+
+ fprintf(dst_file, "static const %s tab%d[] = { ", tabn[i] < 32 ? "short" : "u8", tabn[i]);+ if (h)
+ {+ //huff_set_links_bfs(h, dst_file);
+ huff_set_links_dfs(h, dst_file);
+ entry_bits[i] = h->dp.best_width;
+ } else
+ {+ fprintf(dst_file, "0");
+ entry_bits[i] = 0;
+ }
+ fprintf(dst_file, " };\n");
+ huff_free(h);
+ }
+#if WROOT > 1
+ fprintf(dst_file, "#define HUFF_ENTRY_BITS %d\n", WROOT);
+#else
+ fprintf(dst_file, "#define HUFF_ENTRY_BITS 0\n");
+ fprintf(dst_file, "static const u8 g_entry_bits[] = { ");+ for (i = 0; i < sizeof(tabn)/sizeof(tabn[0]); i++)
+ {+ fprintf(dst_file, "%d,", entry_bits[i]);
+ }
+ fprintf(dst_file, " };\n", i);
+#endif
+ fclose(dst_file);
+ printf("\n// Total: %d items\n", total_size);+}