1:- module(huffman, [atom_huffcodes/2]).
7:- use_module(library(apply_macros)). 8:- use_module(library(clpfd)). 9:- use_module(library(delay), [delay/1]).
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
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).
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
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)
hpack/huffman, HPACK's implementation of Huffman encoding