1:- module(huffman, [atom_huffcodes/2]).

hpack/huffman, HPACK's implementation of Huffman encoding

author
- James Cash */
    7:- use_module(library(apply_macros)).    8:- use_module(library(clpfd)).    9:- use_module(library(delay), [delay/1]).
 atom_huffcodes(?Atom, ?Codes) is det
True when Atom Huffman-encodes to Codes.
   13atom_huffcodes(Atom, HuffCodes) :-
   14    atom(Atom), !,
   15    atom_codes(Atom, Codes),
   16    maplist(huff_sym_code, Codes, HuffCodes_, Lens),
   17    sum_symbol_codes(Combined_, HuffCodes_, Lens),
   18    sumlist(Lens, TotalLen),
   19    padded(Combined_, TotalLen, Combined),
   20    once(bytes_sum(HuffCodes, Combined)).
   21atom_huffcodes(Atom, HuffCodes) :-
   22    ground(HuffCodes), !,
   23    bytes_sum(HuffCodes, Combined),
   24    length(HuffCodes, CodesL),
   25    BitLen #= CodesL * 8,
   26    decoded(Combined, BitLen, Codes),
   27    atom_codes(Atom, Codes).
   28
   29% if I was smarter, I'd combine these two different approachs for
   30% encoding versus decoding...
   31
   32% helper for huffman decoding
   33
   34decoded(N, BitL, [C|Cs]) :-
   35    huff_sym_code(C, NCode, CodeBits),
   36    NCode #= N >> (BitL - CodeBits),
   37    N1 #= N mod (2^(BitL - CodeBits)),
   38    BitL1 #= BitL - CodeBits,
   39    decoded(N1, BitL1, Cs).
   40decoded(_, _, []).
   41
   42% helpers for huffman encoding
 bytes_sum(+Bytes:list, -N:integer) is det
bytes_sum(-Bytes:list, +N:integer) is multi
True when Bytes is big-endian representation of the integer N.
   47bytes_sum(Bs, N) :- bytes_sum(Bs, 0, N).
   48bytes_sum([], N, N).
   49bytes_sum([B|Bs], N0, N2) :-
   50    B in 0..255,    N1 #= (N0 * 256) + B,    bytes_sum(Bs, N1, N2).
 sum_symbol_codes(-N:integer, +HuffCodes:list, +CodeLengths:list) is det
True when N is a number representing the bitwise concatenation of the numbers in the list HuffCodes, where the bit length of nth member of Codes is given by the nth member of CodeLengths.
   58sum_symbol_codes(N, Cs, Lens) :-
   59    sum_symbol_codes(0, N, Cs, Lens).
   60sum_symbol_codes(N, N, [], []).
   61sum_symbol_codes(N0, N2, [C|Cs], [Len|Lens]) :-
   62    N1 #= (N0 * 2^Len) + C,
   63    sum_symbol_codes(N1, N2, Cs, Lens).
   64
   65%! padded(+N:integer, +Len:integer, -M:integer) is det.
   66%  True when =M= is the =Len=-bits number =N= padded on the right with
   67%  1 bits to make the bit length a multiple of 8.
   68padded(N, Len, N) :-
   69    Len mod 8 #= 0, !.
   70padded(N, Len, M) :-
   71    Bits #= 8 - (Len mod 8),
   72    M #= (N << Bits) + (2^Bits - 1).
   73
   74% Huffman symbol table:
 huf_sym_code(?Symbol, ?Code, ?CodeLen) is det
True when the byte Symbol is Huffman-encoded to the CodeLen-bits number Code.
   79huff_sym_code(  0, 0x1ff8, 13).
   80huff_sym_code(  1, 0x7fffd8, 23).
   81huff_sym_code(  2, 0xfffffe2, 28).
   82huff_sym_code(  3, 0xfffffe3, 28).
   83huff_sym_code(  4, 0xfffffe4, 28).
   84huff_sym_code(  5, 0xfffffe5, 28).
   85huff_sym_code(  6, 0xfffffe6, 28).
   86huff_sym_code(  7, 0xfffffe7, 28).
   87huff_sym_code(  8, 0xfffffe8, 28).
   88huff_sym_code(  9, 0xffffea, 24).
   89huff_sym_code( 10, 0x3ffffffc, 30).
   90huff_sym_code( 11, 0xfffffe9, 28).
   91huff_sym_code( 12, 0xfffffea, 28).
   92huff_sym_code( 13, 0x3ffffffd, 30).
   93huff_sym_code( 14, 0xfffffeb, 28).
   94huff_sym_code( 15, 0xfffffec, 28).
   95huff_sym_code( 16, 0xfffffed, 28).
   96huff_sym_code( 17, 0xfffffee, 28).
   97huff_sym_code( 18, 0xfffffef, 28).
   98huff_sym_code( 19, 0xffffff0, 28).
   99huff_sym_code( 20, 0xffffff1, 28).
  100huff_sym_code( 21, 0xffffff2, 28).
  101huff_sym_code( 22, 0x3ffffffe, 30).
  102huff_sym_code( 23, 0xffffff3, 28).
  103huff_sym_code( 24, 0xffffff4, 28).
  104huff_sym_code( 25, 0xffffff5, 28).
  105huff_sym_code( 26, 0xffffff6, 28).
  106huff_sym_code( 27, 0xffffff7, 28).
  107huff_sym_code( 28, 0xffffff8, 28).
  108huff_sym_code( 29, 0xffffff9, 28).
  109huff_sym_code( 30, 0xffffffa, 28).
  110huff_sym_code( 31, 0xffffffb, 28).
  111huff_sym_code( 32, 0x14,  6).
  112huff_sym_code( 33, 0x3f8, 10).
  113huff_sym_code( 34, 0x3f9, 10).
  114huff_sym_code( 35, 0xffa, 12).
  115huff_sym_code( 36, 0x1ff9, 13).
  116huff_sym_code( 37, 0x15,  6).
  117huff_sym_code( 38, 0xf8,  8).
  118huff_sym_code( 39, 0x7fa, 11).
  119huff_sym_code( 40, 0x3fa, 10).
  120huff_sym_code( 41, 0x3fb, 10).
  121huff_sym_code( 42, 0xf9,  8).
  122huff_sym_code( 43, 0x7fb, 11).
  123huff_sym_code( 44, 0xfa,  8).
  124huff_sym_code( 45, 0x16,  6).
  125huff_sym_code( 46, 0x17,  6).
  126huff_sym_code( 47, 0x18,  6).
  127huff_sym_code( 48, 0x0,  5).
  128huff_sym_code( 49, 0x1,  5).
  129huff_sym_code( 50, 0x2,  5).
  130huff_sym_code( 51, 0x19,  6).
  131huff_sym_code( 52, 0x1a,  6).
  132huff_sym_code( 53, 0x1b,  6).
  133huff_sym_code( 54, 0x1c,  6).
  134huff_sym_code( 55, 0x1d,  6).
  135huff_sym_code( 56, 0x1e,  6).
  136huff_sym_code( 57, 0x1f,  6).
  137huff_sym_code( 58, 0x5c,  7).
  138huff_sym_code( 59, 0xfb,  8).
  139huff_sym_code( 60, 0x7ffc, 15).
  140huff_sym_code( 61, 0x20,  6).
  141huff_sym_code( 62, 0xffb, 12).
  142huff_sym_code( 63, 0x3fc, 10).
  143huff_sym_code( 64, 0x1ffa, 13).
  144huff_sym_code( 65, 0x21,  6).
  145huff_sym_code( 66, 0x5d,  7).
  146huff_sym_code( 67, 0x5e,  7).
  147huff_sym_code( 68, 0x5f,  7).
  148huff_sym_code( 69, 0x60,  7).
  149huff_sym_code( 70, 0x61,  7).
  150huff_sym_code( 71, 0x62,  7).
  151huff_sym_code( 72, 0x63,  7).
  152huff_sym_code( 73, 0x64,  7).
  153huff_sym_code( 74, 0x65,  7).
  154huff_sym_code( 75, 0x66,  7).
  155huff_sym_code( 76, 0x67,  7).
  156huff_sym_code( 77, 0x68,  7).
  157huff_sym_code( 78, 0x69,  7).
  158huff_sym_code( 79, 0x6a,  7).
  159huff_sym_code( 80, 0x6b,  7).
  160huff_sym_code( 81, 0x6c,  7).
  161huff_sym_code( 82, 0x6d,  7).
  162huff_sym_code( 83, 0x6e,  7).
  163huff_sym_code( 84, 0x6f,  7).
  164huff_sym_code( 85, 0x70,  7).
  165huff_sym_code( 86, 0x71,  7).
  166huff_sym_code( 87, 0x72,  7).
  167huff_sym_code( 88, 0xfc,  8).
  168huff_sym_code( 89, 0x73,  7).
  169huff_sym_code( 90, 0xfd,  8).
  170huff_sym_code( 91, 0x1ffb, 13).
  171huff_sym_code( 92, 0x7fff0, 19).
  172huff_sym_code( 93, 0x1ffc, 13).
  173huff_sym_code( 94, 0x3ffc, 14).
  174huff_sym_code( 95, 0x22,  6).
  175huff_sym_code( 96, 0x7ffd, 15).
  176huff_sym_code( 97, 0x3,  5).
  177huff_sym_code( 98, 0x23,  6).
  178huff_sym_code( 99, 0x4,  5).
  179huff_sym_code(100, 0x24,  6).
  180huff_sym_code(101, 0x5,  5).
  181huff_sym_code(102, 0x25,  6).
  182huff_sym_code(103, 0x26,  6).
  183huff_sym_code(104, 0x27,  6).
  184huff_sym_code(105, 0x6,  5).
  185huff_sym_code(106, 0x74,  7).
  186huff_sym_code(107, 0x75,  7).
  187huff_sym_code(108, 0x28,  6).
  188huff_sym_code(109, 0x29,  6).
  189huff_sym_code(110, 0x2a,  6).
  190huff_sym_code(111, 0x7,  5).
  191huff_sym_code(112, 0x2b,  6).
  192huff_sym_code(113, 0x76,  7).
  193huff_sym_code(114, 0x2c,  6).
  194huff_sym_code(115, 0x8,  5).
  195huff_sym_code(116, 0x9,  5).
  196huff_sym_code(117, 0x2d,  6).
  197huff_sym_code(118, 0x77,  7).
  198huff_sym_code(119, 0x78,  7).
  199huff_sym_code(120, 0x79,  7).
  200huff_sym_code(121, 0x7a,  7).
  201huff_sym_code(122, 0x7b,  7).
  202huff_sym_code(123, 0x7ffe, 15).
  203huff_sym_code(124, 0x7fc, 11).
  204huff_sym_code(125, 0x3ffd, 14).
  205huff_sym_code(126, 0x1ffd, 13).
  206huff_sym_code(127, 0xffffffc, 28).
  207huff_sym_code(128, 0xfffe6, 20).
  208huff_sym_code(129, 0x3fffd2, 22).
  209huff_sym_code(130, 0xfffe7, 20).
  210huff_sym_code(131, 0xfffe8, 20).
  211huff_sym_code(132, 0x3fffd3, 22).
  212huff_sym_code(133, 0x3fffd4, 22).
  213huff_sym_code(134, 0x3fffd5, 22).
  214huff_sym_code(135, 0x7fffd9, 23).
  215huff_sym_code(136, 0x3fffd6, 22).
  216huff_sym_code(137, 0x7fffda, 23).
  217huff_sym_code(138, 0x7fffdb, 23).
  218huff_sym_code(139, 0x7fffdc, 23).
  219huff_sym_code(140, 0x7fffdd, 23).
  220huff_sym_code(141, 0x7fffde, 23).
  221huff_sym_code(142, 0xffffeb, 24).
  222huff_sym_code(143, 0x7fffdf, 23).
  223huff_sym_code(144, 0xffffec, 24).
  224huff_sym_code(145, 0xffffed, 24).
  225huff_sym_code(146, 0x3fffd7, 22).
  226huff_sym_code(147, 0x7fffe0, 23).
  227huff_sym_code(148, 0xffffee, 24).
  228huff_sym_code(149, 0x7fffe1, 23).
  229huff_sym_code(150, 0x7fffe2, 23).
  230huff_sym_code(151, 0x7fffe3, 23).
  231huff_sym_code(152, 0x7fffe4, 23).
  232huff_sym_code(153, 0x1fffdc, 21).
  233huff_sym_code(154, 0x3fffd8, 22).
  234huff_sym_code(155, 0x7fffe5, 23).
  235huff_sym_code(156, 0x3fffd9, 22).
  236huff_sym_code(157, 0x7fffe6, 23).
  237huff_sym_code(158, 0x7fffe7, 23).
  238huff_sym_code(159, 0xffffef, 24).
  239huff_sym_code(160, 0x3fffda, 22).
  240huff_sym_code(161, 0x1fffdd, 21).
  241huff_sym_code(162, 0xfffe9, 20).
  242huff_sym_code(163, 0x3fffdb, 22).
  243huff_sym_code(164, 0x3fffdc, 22).
  244huff_sym_code(165, 0x7fffe8, 23).
  245huff_sym_code(166, 0x7fffe9, 23).
  246huff_sym_code(167, 0x1fffde, 21).
  247huff_sym_code(168, 0x7fffea, 23).
  248huff_sym_code(169, 0x3fffdd, 22).
  249huff_sym_code(170, 0x3fffde, 22).
  250huff_sym_code(171, 0xfffff0, 24).
  251huff_sym_code(172, 0x1fffdf, 21).
  252huff_sym_code(173, 0x3fffdf, 22).
  253huff_sym_code(174, 0x7fffeb, 23).
  254huff_sym_code(175, 0x7fffec, 23).
  255huff_sym_code(176, 0x1fffe0, 21).
  256huff_sym_code(177, 0x1fffe1, 21).
  257huff_sym_code(178, 0x3fffe0, 22).
  258huff_sym_code(179, 0x1fffe2, 21).
  259huff_sym_code(180, 0x7fffed, 23).
  260huff_sym_code(181, 0x3fffe1, 22).
  261huff_sym_code(182, 0x7fffee, 23).
  262huff_sym_code(183, 0x7fffef, 23).
  263huff_sym_code(184, 0xfffea, 20).
  264huff_sym_code(185, 0x3fffe2, 22).
  265huff_sym_code(186, 0x3fffe3, 22).
  266huff_sym_code(187, 0x3fffe4, 22).
  267huff_sym_code(188, 0x7ffff0, 23).
  268huff_sym_code(189, 0x3fffe5, 22).
  269huff_sym_code(190, 0x3fffe6, 22).
  270huff_sym_code(191, 0x7ffff1, 23).
  271huff_sym_code(192, 0x3ffffe0, 26).
  272huff_sym_code(193, 0x3ffffe1, 26).
  273huff_sym_code(194, 0xfffeb, 20).
  274huff_sym_code(195, 0x7fff1, 19).
  275huff_sym_code(196, 0x3fffe7, 22).
  276huff_sym_code(197, 0x7ffff2, 23).
  277huff_sym_code(198, 0x3fffe8, 22).
  278huff_sym_code(199, 0x1ffffec, 25).
  279huff_sym_code(200, 0x3ffffe2, 26).
  280huff_sym_code(201, 0x3ffffe3, 26).
  281huff_sym_code(202, 0x3ffffe4, 26).
  282huff_sym_code(203, 0x7ffffde, 27).
  283huff_sym_code(204, 0x7ffffdf, 27).
  284huff_sym_code(205, 0x3ffffe5, 26).
  285huff_sym_code(206, 0xfffff1, 24).
  286huff_sym_code(207, 0x1ffffed, 25).
  287huff_sym_code(208, 0x7fff2, 19).
  288huff_sym_code(209, 0x1fffe3, 21).
  289huff_sym_code(210, 0x3ffffe6, 26).
  290huff_sym_code(211, 0x7ffffe0, 27).
  291huff_sym_code(212, 0x7ffffe1, 27).
  292huff_sym_code(213, 0x3ffffe7, 26).
  293huff_sym_code(214, 0x7ffffe2, 27).
  294huff_sym_code(215, 0xfffff2, 24).
  295huff_sym_code(216, 0x1fffe4, 21).
  296huff_sym_code(217, 0x1fffe5, 21).
  297huff_sym_code(218, 0x3ffffe8, 26).
  298huff_sym_code(219, 0x3ffffe9, 26).
  299huff_sym_code(220, 0xffffffd, 28).
  300huff_sym_code(221, 0x7ffffe3, 27).
  301huff_sym_code(222, 0x7ffffe4, 27).
  302huff_sym_code(223, 0x7ffffe5, 27).
  303huff_sym_code(224, 0xfffec, 20).
  304huff_sym_code(225, 0xfffff3, 24).
  305huff_sym_code(226, 0xfffed, 20).
  306huff_sym_code(227, 0x1fffe6, 21).
  307huff_sym_code(228, 0x3fffe9, 22).
  308huff_sym_code(229, 0x1fffe7, 21).
  309huff_sym_code(230, 0x1fffe8, 21).
  310huff_sym_code(231, 0x7ffff3, 23).
  311huff_sym_code(232, 0x3fffea, 22).
  312huff_sym_code(233, 0x3fffeb, 22).
  313huff_sym_code(234, 0x1ffffee, 25).
  314huff_sym_code(235, 0x1ffffef, 25).
  315huff_sym_code(236, 0xfffff4, 24).
  316huff_sym_code(237, 0xfffff5, 24).
  317huff_sym_code(238, 0x3ffffea, 26).
  318huff_sym_code(239, 0x7ffff4, 23).
  319huff_sym_code(240, 0x3ffffeb, 26).
  320huff_sym_code(241, 0x7ffffe6, 27).
  321huff_sym_code(242, 0x3ffffec, 26).
  322huff_sym_code(243, 0x3ffffed, 26).
  323huff_sym_code(244, 0x7ffffe7, 27).
  324huff_sym_code(245, 0x7ffffe8, 27).
  325huff_sym_code(246, 0x7ffffe9, 27).
  326huff_sym_code(247, 0x7ffffea, 27).
  327huff_sym_code(248, 0x7ffffeb, 27).
  328huff_sym_code(249, 0xffffffe, 28).
  329huff_sym_code(250, 0x7ffffec, 27).
  330huff_sym_code(251, 0x7ffffed, 27).
  331huff_sym_code(252, 0x7ffffee, 27).
  332huff_sym_code(253, 0x7ffffef, 27).
  333huff_sym_code(254, 0x7fffff0, 27).
  334huff_sym_code(255, 0x3ffffee, 26)