huffman.bend
bend-kit-http2@0.1.1.0 · 1,293 lines · 0 definitions
1# RFC 7541 Appendix B Huffman alphabet and streaming codec.
2import Base
3import bend-kit-bytes@0.3.1.0/bytes.bend as Bytes
4
5type Code is Data:
6 Code{bits: U32, width: U32}
7
8def code(+octet: U32) -> Code:
9 match octet:
10 case 0:
11 Code{8184, 13}
12 case 1:
13 Code{8388568, 23}
14 case 2:
15 Code{268435426, 28}
16 case 3:
17 Code{268435427, 28}
18 case 4:
19 Code{268435428, 28}
20 case 5:
21 Code{268435429, 28}
22 case 6:
23 Code{268435430, 28}
24 case 7:
25 Code{268435431, 28}
26 case 8:
27 Code{268435432, 28}
28 case 9:
29 Code{16777194, 24}
30 case 10:
31 Code{1073741820, 30}
32 case 11:
33 Code{268435433, 28}
34 case 12:
35 Code{268435434, 28}
36 case 13:
37 Code{1073741821, 30}
38 case 14:
39 Code{268435435, 28}
40 case 15:
41 Code{268435436, 28}
42 case 16:
43 Code{268435437, 28}
44 case 17:
45 Code{268435438, 28}
46 case 18:
47 Code{268435439, 28}
48 case 19:
49 Code{268435440, 28}
50 case 20:
51 Code{268435441, 28}
52 case 21:
53 Code{268435442, 28}
54 case 22:
55 Code{1073741822, 30}
56 case 23:
57 Code{268435443, 28}
58 case 24:
59 Code{268435444, 28}
60 case 25:
61 Code{268435445, 28}
62 case 26:
63 Code{268435446, 28}
64 case 27:
65 Code{268435447, 28}
66 case 28:
67 Code{268435448, 28}
68 case 29:
69 Code{268435449, 28}
70 case 30:
71 Code{268435450, 28}
72 case 31:
73 Code{268435451, 28}
74 case 32:
75 Code{20, 6}
76 case 33:
77 Code{1016, 10}
78 case 34:
79 Code{1017, 10}
80 case 35:
81 Code{4090, 12}
82 case 36:
83 Code{8185, 13}
84 case 37:
85 Code{21, 6}
86 case 38:
87 Code{248, 8}
88 case 39:
89 Code{2042, 11}
90 case 40:
91 Code{1018, 10}
92 case 41:
93 Code{1019, 10}
94 case 42:
95 Code{249, 8}
96 case 43:
97 Code{2043, 11}
98 case 44:
99 Code{250, 8}
100 case 45:
101 Code{22, 6}
102 case 46:
103 Code{23, 6}
104 case 47:
105 Code{24, 6}
106 case 48:
107 Code{0, 5}
108 case 49:
109 Code{1, 5}
110 case 50:
111 Code{2, 5}
112 case 51:
113 Code{25, 6}
114 case 52:
115 Code{26, 6}
116 case 53:
117 Code{27, 6}
118 case 54:
119 Code{28, 6}
120 case 55:
121 Code{29, 6}
122 case 56:
123 Code{30, 6}
124 case 57:
125 Code{31, 6}
126 case 58:
127 Code{92, 7}
128 case 59:
129 Code{251, 8}
130 case 60:
131 Code{32764, 15}
132 case 61:
133 Code{32, 6}
134 case 62:
135 Code{4091, 12}
136 case 63:
137 Code{1020, 10}
138 case 64:
139 Code{8186, 13}
140 case 65:
141 Code{33, 6}
142 case 66:
143 Code{93, 7}
144 case 67:
145 Code{94, 7}
146 case 68:
147 Code{95, 7}
148 case 69:
149 Code{96, 7}
150 case 70:
151 Code{97, 7}
152 case 71:
153 Code{98, 7}
154 case 72:
155 Code{99, 7}
156 case 73:
157 Code{100, 7}
158 case 74:
159 Code{101, 7}
160 case 75:
161 Code{102, 7}
162 case 76:
163 Code{103, 7}
164 case 77:
165 Code{104, 7}
166 case 78:
167 Code{105, 7}
168 case 79:
169 Code{106, 7}
170 case 80:
171 Code{107, 7}
172 case 81:
173 Code{108, 7}
174 case 82:
175 Code{109, 7}
176 case 83:
177 Code{110, 7}
178 case 84:
179 Code{111, 7}
180 case 85:
181 Code{112, 7}
182 case 86:
183 Code{113, 7}
184 case 87:
185 Code{114, 7}
186 case 88:
187 Code{252, 8}
188 case 89:
189 Code{115, 7}
190 case 90:
191 Code{253, 8}
192 case 91:
193 Code{8187, 13}
194 case 92:
195 Code{524272, 19}
196 case 93:
197 Code{8188, 13}
198 case 94:
199 Code{16380, 14}
200 case 95:
201 Code{34, 6}
202 case 96:
203 Code{32765, 15}
204 case 97:
205 Code{3, 5}
206 case 98:
207 Code{35, 6}
208 case 99:
209 Code{4, 5}
210 case 100:
211 Code{36, 6}
212 case 101:
213 Code{5, 5}
214 case 102:
215 Code{37, 6}
216 case 103:
217 Code{38, 6}
218 case 104:
219 Code{39, 6}
220 case 105:
221 Code{6, 5}
222 case 106:
223 Code{116, 7}
224 case 107:
225 Code{117, 7}
226 case 108:
227 Code{40, 6}
228 case 109:
229 Code{41, 6}
230 case 110:
231 Code{42, 6}
232 case 111:
233 Code{7, 5}
234 case 112:
235 Code{43, 6}
236 case 113:
237 Code{118, 7}
238 case 114:
239 Code{44, 6}
240 case 115:
241 Code{8, 5}
242 case 116:
243 Code{9, 5}
244 case 117:
245 Code{45, 6}
246 case 118:
247 Code{119, 7}
248 case 119:
249 Code{120, 7}
250 case 120:
251 Code{121, 7}
252 case 121:
253 Code{122, 7}
254 case 122:
255 Code{123, 7}
256 case 123:
257 Code{32766, 15}
258 case 124:
259 Code{2044, 11}
260 case 125:
261 Code{16381, 14}
262 case 126:
263 Code{8189, 13}
264 case 127:
265 Code{268435452, 28}
266 case 128:
267 Code{1048550, 20}
268 case 129:
269 Code{4194258, 22}
270 case 130:
271 Code{1048551, 20}
272 case 131:
273 Code{1048552, 20}
274 case 132:
275 Code{4194259, 22}
276 case 133:
277 Code{4194260, 22}
278 case 134:
279 Code{4194261, 22}
280 case 135:
281 Code{8388569, 23}
282 case 136:
283 Code{4194262, 22}
284 case 137:
285 Code{8388570, 23}
286 case 138:
287 Code{8388571, 23}
288 case 139:
289 Code{8388572, 23}
290 case 140:
291 Code{8388573, 23}
292 case 141:
293 Code{8388574, 23}
294 case 142:
295 Code{16777195, 24}
296 case 143:
297 Code{8388575, 23}
298 case 144:
299 Code{16777196, 24}
300 case 145:
301 Code{16777197, 24}
302 case 146:
303 Code{4194263, 22}
304 case 147:
305 Code{8388576, 23}
306 case 148:
307 Code{16777198, 24}
308 case 149:
309 Code{8388577, 23}
310 case 150:
311 Code{8388578, 23}
312 case 151:
313 Code{8388579, 23}
314 case 152:
315 Code{8388580, 23}
316 case 153:
317 Code{2097116, 21}
318 case 154:
319 Code{4194264, 22}
320 case 155:
321 Code{8388581, 23}
322 case 156:
323 Code{4194265, 22}
324 case 157:
325 Code{8388582, 23}
326 case 158:
327 Code{8388583, 23}
328 case 159:
329 Code{16777199, 24}
330 case 160:
331 Code{4194266, 22}
332 case 161:
333 Code{2097117, 21}
334 case 162:
335 Code{1048553, 20}
336 case 163:
337 Code{4194267, 22}
338 case 164:
339 Code{4194268, 22}
340 case 165:
341 Code{8388584, 23}
342 case 166:
343 Code{8388585, 23}
344 case 167:
345 Code{2097118, 21}
346 case 168:
347 Code{8388586, 23}
348 case 169:
349 Code{4194269, 22}
350 case 170:
351 Code{4194270, 22}
352 case 171:
353 Code{16777200, 24}
354 case 172:
355 Code{2097119, 21}
356 case 173:
357 Code{4194271, 22}
358 case 174:
359 Code{8388587, 23}
360 case 175:
361 Code{8388588, 23}
362 case 176:
363 Code{2097120, 21}
364 case 177:
365 Code{2097121, 21}
366 case 178:
367 Code{4194272, 22}
368 case 179:
369 Code{2097122, 21}
370 case 180:
371 Code{8388589, 23}
372 case 181:
373 Code{4194273, 22}
374 case 182:
375 Code{8388590, 23}
376 case 183:
377 Code{8388591, 23}
378 case 184:
379 Code{1048554, 20}
380 case 185:
381 Code{4194274, 22}
382 case 186:
383 Code{4194275, 22}
384 case 187:
385 Code{4194276, 22}
386 case 188:
387 Code{8388592, 23}
388 case 189:
389 Code{4194277, 22}
390 case 190:
391 Code{4194278, 22}
392 case 191:
393 Code{8388593, 23}
394 case 192:
395 Code{67108832, 26}
396 case 193:
397 Code{67108833, 26}
398 case 194:
399 Code{1048555, 20}
400 case 195:
401 Code{524273, 19}
402 case 196:
403 Code{4194279, 22}
404 case 197:
405 Code{8388594, 23}
406 case 198:
407 Code{4194280, 22}
408 case 199:
409 Code{33554412, 25}
410 case 200:
411 Code{67108834, 26}
412 case 201:
413 Code{67108835, 26}
414 case 202:
415 Code{67108836, 26}
416 case 203:
417 Code{134217694, 27}
418 case 204:
419 Code{134217695, 27}
420 case 205:
421 Code{67108837, 26}
422 case 206:
423 Code{16777201, 24}
424 case 207:
425 Code{33554413, 25}
426 case 208:
427 Code{524274, 19}
428 case 209:
429 Code{2097123, 21}
430 case 210:
431 Code{67108838, 26}
432 case 211:
433 Code{134217696, 27}
434 case 212:
435 Code{134217697, 27}
436 case 213:
437 Code{67108839, 26}
438 case 214:
439 Code{134217698, 27}
440 case 215:
441 Code{16777202, 24}
442 case 216:
443 Code{2097124, 21}
444 case 217:
445 Code{2097125, 21}
446 case 218:
447 Code{67108840, 26}
448 case 219:
449 Code{67108841, 26}
450 case 220:
451 Code{268435453, 28}
452 case 221:
453 Code{134217699, 27}
454 case 222:
455 Code{134217700, 27}
456 case 223:
457 Code{134217701, 27}
458 case 224:
459 Code{1048556, 20}
460 case 225:
461 Code{16777203, 24}
462 case 226:
463 Code{1048557, 20}
464 case 227:
465 Code{2097126, 21}
466 case 228:
467 Code{4194281, 22}
468 case 229:
469 Code{2097127, 21}
470 case 230:
471 Code{2097128, 21}
472 case 231:
473 Code{8388595, 23}
474 case 232:
475 Code{4194282, 22}
476 case 233:
477 Code{4194283, 22}
478 case 234:
479 Code{33554414, 25}
480 case 235:
481 Code{33554415, 25}
482 case 236:
483 Code{16777204, 24}
484 case 237:
485 Code{16777205, 24}
486 case 238:
487 Code{67108842, 26}
488 case 239:
489 Code{8388596, 23}
490 case 240:
491 Code{67108843, 26}
492 case 241:
493 Code{134217702, 27}
494 case 242:
495 Code{67108844, 26}
496 case 243:
497 Code{67108845, 26}
498 case 244:
499 Code{134217703, 27}
500 case 245:
501 Code{134217704, 27}
502 case 246:
503 Code{134217705, 27}
504 case 247:
505 Code{134217706, 27}
506 case 248:
507 Code{134217707, 27}
508 case 249:
509 Code{268435454, 28}
510 case 250:
511 Code{134217708, 27}
512 case 251:
513 Code{134217709, 27}
514 case 252:
515 Code{134217710, 27}
516 case 253:
517 Code{134217711, 27}
518 case 254:
519 Code{134217712, 27}
520 case 255:
521 Code{67108846, 26}
522 case 256:
523 Code{1073741823, 30}
524 case _:
525 Code{0, 0}
526
527def width.of(c: Code) -> U32:
528 match c:
529 case Code{bits, width}:
530 width
531
532def width(+octet: U32) -> U32:
533 width.of(code(octet))
534
535def symbol(+width: U32, +bits: U32) -> Maybe<&2, U32>:
536 match width:
537 case 5:
538 match bits:
539 case 0:
540 Some{48}
541 case 1:
542 Some{49}
543 case 2:
544 Some{50}
545 case 3:
546 Some{97}
547 case 4:
548 Some{99}
549 case 5:
550 Some{101}
551 case 6:
552 Some{105}
553 case 7:
554 Some{111}
555 case 8:
556 Some{115}
557 case 9:
558 Some{116}
559 case _:
560 None{}
561 case 6:
562 match bits:
563 case 20:
564 Some{32}
565 case 21:
566 Some{37}
567 case 22:
568 Some{45}
569 case 23:
570 Some{46}
571 case 24:
572 Some{47}
573 case 25:
574 Some{51}
575 case 26:
576 Some{52}
577 case 27:
578 Some{53}
579 case 28:
580 Some{54}
581 case 29:
582 Some{55}
583 case 30:
584 Some{56}
585 case 31:
586 Some{57}
587 case 32:
588 Some{61}
589 case 33:
590 Some{65}
591 case 34:
592 Some{95}
593 case 35:
594 Some{98}
595 case 36:
596 Some{100}
597 case 37:
598 Some{102}
599 case 38:
600 Some{103}
601 case 39:
602 Some{104}
603 case 40:
604 Some{108}
605 case 41:
606 Some{109}
607 case 42:
608 Some{110}
609 case 43:
610 Some{112}
611 case 44:
612 Some{114}
613 case 45:
614 Some{117}
615 case _:
616 None{}
617 case 7:
618 match bits:
619 case 92:
620 Some{58}
621 case 93:
622 Some{66}
623 case 94:
624 Some{67}
625 case 95:
626 Some{68}
627 case 96:
628 Some{69}
629 case 97:
630 Some{70}
631 case 98:
632 Some{71}
633 case 99:
634 Some{72}
635 case 100:
636 Some{73}
637 case 101:
638 Some{74}
639 case 102:
640 Some{75}
641 case 103:
642 Some{76}
643 case 104:
644 Some{77}
645 case 105:
646 Some{78}
647 case 106:
648 Some{79}
649 case 107:
650 Some{80}
651 case 108:
652 Some{81}
653 case 109:
654 Some{82}
655 case 110:
656 Some{83}
657 case 111:
658 Some{84}
659 case 112:
660 Some{85}
661 case 113:
662 Some{86}
663 case 114:
664 Some{87}
665 case 115:
666 Some{89}
667 case 116:
668 Some{106}
669 case 117:
670 Some{107}
671 case 118:
672 Some{113}
673 case 119:
674 Some{118}
675 case 120:
676 Some{119}
677 case 121:
678 Some{120}
679 case 122:
680 Some{121}
681 case 123:
682 Some{122}
683 case _:
684 None{}
685 case 8:
686 match bits:
687 case 248:
688 Some{38}
689 case 249:
690 Some{42}
691 case 250:
692 Some{44}
693 case 251:
694 Some{59}
695 case 252:
696 Some{88}
697 case 253:
698 Some{90}
699 case _:
700 None{}
701 case 10:
702 match bits:
703 case 1016:
704 Some{33}
705 case 1017:
706 Some{34}
707 case 1018:
708 Some{40}
709 case 1019:
710 Some{41}
711 case 1020:
712 Some{63}
713 case _:
714 None{}
715 case 11:
716 match bits:
717 case 2042:
718 Some{39}
719 case 2043:
720 Some{43}
721 case 2044:
722 Some{124}
723 case _:
724 None{}
725 case 12:
726 match bits:
727 case 4090:
728 Some{35}
729 case 4091:
730 Some{62}
731 case _:
732 None{}
733 case 13:
734 match bits:
735 case 8184:
736 Some{0}
737 case 8185:
738 Some{36}
739 case 8186:
740 Some{64}
741 case 8187:
742 Some{91}
743 case 8188:
744 Some{93}
745 case 8189:
746 Some{126}
747 case _:
748 None{}
749 case 14:
750 match bits:
751 case 16380:
752 Some{94}
753 case 16381:
754 Some{125}
755 case _:
756 None{}
757 case 15:
758 match bits:
759 case 32764:
760 Some{60}
761 case 32765:
762 Some{96}
763 case 32766:
764 Some{123}
765 case _:
766 None{}
767 case 19:
768 match bits:
769 case 524272:
770 Some{92}
771 case 524273:
772 Some{195}
773 case 524274:
774 Some{208}
775 case _:
776 None{}
777 case 20:
778 match bits:
779 case 1048550:
780 Some{128}
781 case 1048551:
782 Some{130}
783 case 1048552:
784 Some{131}
785 case 1048553:
786 Some{162}
787 case 1048554:
788 Some{184}
789 case 1048555:
790 Some{194}
791 case 1048556:
792 Some{224}
793 case 1048557:
794 Some{226}
795 case _:
796 None{}
797 case 21:
798 match bits:
799 case 2097116:
800 Some{153}
801 case 2097117:
802 Some{161}
803 case 2097118:
804 Some{167}
805 case 2097119:
806 Some{172}
807 case 2097120:
808 Some{176}
809 case 2097121:
810 Some{177}
811 case 2097122:
812 Some{179}
813 case 2097123:
814 Some{209}
815 case 2097124:
816 Some{216}
817 case 2097125:
818 Some{217}
819 case 2097126:
820 Some{227}
821 case 2097127:
822 Some{229}
823 case 2097128:
824 Some{230}
825 case _:
826 None{}
827 case 22:
828 match bits:
829 case 4194258:
830 Some{129}
831 case 4194259:
832 Some{132}
833 case 4194260:
834 Some{133}
835 case 4194261:
836 Some{134}
837 case 4194262:
838 Some{136}
839 case 4194263:
840 Some{146}
841 case 4194264:
842 Some{154}
843 case 4194265:
844 Some{156}
845 case 4194266:
846 Some{160}
847 case 4194267:
848 Some{163}
849 case 4194268:
850 Some{164}
851 case 4194269:
852 Some{169}
853 case 4194270:
854 Some{170}
855 case 4194271:
856 Some{173}
857 case 4194272:
858 Some{178}
859 case 4194273:
860 Some{181}
861 case 4194274:
862 Some{185}
863 case 4194275:
864 Some{186}
865 case 4194276:
866 Some{187}
867 case 4194277:
868 Some{189}
869 case 4194278:
870 Some{190}
871 case 4194279:
872 Some{196}
873 case 4194280:
874 Some{198}
875 case 4194281:
876 Some{228}
877 case 4194282:
878 Some{232}
879 case 4194283:
880 Some{233}
881 case _:
882 None{}
883 case 23:
884 match bits:
885 case 8388568:
886 Some{1}
887 case 8388569:
888 Some{135}
889 case 8388570:
890 Some{137}
891 case 8388571:
892 Some{138}
893 case 8388572:
894 Some{139}
895 case 8388573:
896 Some{140}
897 case 8388574:
898 Some{141}
899 case 8388575:
900 Some{143}
901 case 8388576:
902 Some{147}
903 case 8388577:
904 Some{149}
905 case 8388578:
906 Some{150}
907 case 8388579:
908 Some{151}
909 case 8388580:
910 Some{152}
911 case 8388581:
912 Some{155}
913 case 8388582:
914 Some{157}
915 case 8388583:
916 Some{158}
917 case 8388584:
918 Some{165}
919 case 8388585:
920 Some{166}
921 case 8388586:
922 Some{168}
923 case 8388587:
924 Some{174}
925 case 8388588:
926 Some{175}
927 case 8388589:
928 Some{180}
929 case 8388590:
930 Some{182}
931 case 8388591:
932 Some{183}
933 case 8388592:
934 Some{188}
935 case 8388593:
936 Some{191}
937 case 8388594:
938 Some{197}
939 case 8388595:
940 Some{231}
941 case 8388596:
942 Some{239}
943 case _:
944 None{}
945 case 24:
946 match bits:
947 case 16777194:
948 Some{9}
949 case 16777195:
950 Some{142}
951 case 16777196:
952 Some{144}
953 case 16777197:
954 Some{145}
955 case 16777198:
956 Some{148}
957 case 16777199:
958 Some{159}
959 case 16777200:
960 Some{171}
961 case 16777201:
962 Some{206}
963 case 16777202:
964 Some{215}
965 case 16777203:
966 Some{225}
967 case 16777204:
968 Some{236}
969 case 16777205:
970 Some{237}
971 case _:
972 None{}
973 case 25:
974 match bits:
975 case 33554412:
976 Some{199}
977 case 33554413:
978 Some{207}
979 case 33554414:
980 Some{234}
981 case 33554415:
982 Some{235}
983 case _:
984 None{}
985 case 26:
986 match bits:
987 case 67108832:
988 Some{192}
989 case 67108833:
990 Some{193}
991 case 67108834:
992 Some{200}
993 case 67108835:
994 Some{201}
995 case 67108836:
996 Some{202}
997 case 67108837:
998 Some{205}
999 case 67108838:
1000 Some{210}
1001 case 67108839:
1002 Some{213}
1003 case 67108840:
1004 Some{218}
1005 case 67108841:
1006 Some{219}
1007 case 67108842:
1008 Some{238}
1009 case 67108843:
1010 Some{240}
1011 case 67108844:
1012 Some{242}
1013 case 67108845:
1014 Some{243}
1015 case 67108846:
1016 Some{255}
1017 case _:
1018 None{}
1019 case 27:
1020 match bits:
1021 case 134217694:
1022 Some{203}
1023 case 134217695:
1024 Some{204}
1025 case 134217696:
1026 Some{211}
1027 case 134217697:
1028 Some{212}
1029 case 134217698:
1030 Some{214}
1031 case 134217699:
1032 Some{221}
1033 case 134217700:
1034 Some{222}
1035 case 134217701:
1036 Some{223}
1037 case 134217702:
1038 Some{241}
1039 case 134217703:
1040 Some{244}
1041 case 134217704:
1042 Some{245}
1043 case 134217705:
1044 Some{246}
1045 case 134217706:
1046 Some{247}
1047 case 134217707:
1048 Some{248}
1049 case 134217708:
1050 Some{250}
1051 case 134217709:
1052 Some{251}
1053 case 134217710:
1054 Some{252}
1055 case 134217711:
1056 Some{253}
1057 case 134217712:
1058 Some{254}
1059 case _:
1060 None{}
1061 case 28:
1062 match bits:
1063 case 268435426:
1064 Some{2}
1065 case 268435427:
1066 Some{3}
1067 case 268435428:
1068 Some{4}
1069 case 268435429:
1070 Some{5}
1071 case 268435430:
1072 Some{6}
1073 case 268435431:
1074 Some{7}
1075 case 268435432:
1076 Some{8}
1077 case 268435433:
1078 Some{11}
1079 case 268435434:
1080 Some{12}
1081 case 268435435:
1082 Some{14}
1083 case 268435436:
1084 Some{15}
1085 case 268435437:
1086 Some{16}
1087 case 268435438:
1088 Some{17}
1089 case 268435439:
1090 Some{18}
1091 case 268435440:
1092 Some{19}
1093 case 268435441:
1094 Some{20}
1095 case 268435442:
1096 Some{21}
1097 case 268435443:
1098 Some{23}
1099 case 268435444:
1100 Some{24}
1101 case 268435445:
1102 Some{25}
1103 case 268435446:
1104 Some{26}
1105 case 268435447:
1106 Some{27}
1107 case 268435448:
1108 Some{28}
1109 case 268435449:
1110 Some{29}
1111 case 268435450:
1112 Some{30}
1113 case 268435451:
1114 Some{31}
1115 case 268435452:
1116 Some{127}
1117 case 268435453:
1118 Some{220}
1119 case 268435454:
1120 Some{249}
1121 case _:
1122 None{}
1123 case 30:
1124 match bits:
1125 case 1073741820:
1126 Some{10}
1127 case 1073741821:
1128 Some{13}
1129 case 1073741822:
1130 Some{22}
1131 case 1073741823:
1132 Some{256}
1133 case _:
1134 None{}
1135 case _:
1136 None{}
1137
1138def size.valid(ok: Bool, +total: U32, +n: U32) -> Maybe<&2, U32>:
1139 match ok:
1140 case True{}:
1141 Some{(total + n : U32)}
1142 case False{}:
1143 None{}
1144def size.one(+octet: U32, +total: U32) -> Maybe<&2, U32>:
1145 +n = width(octet)
1146 size.valid(Bool.and(U32.is_ne(n, 0), U32.is_le(total, (4294967295 - n : U32))), total, n)
1147
1148
1149def size(s: String, +total: U32) -> Maybe<&2, U32>:
1150 match s:
1151 case SNil{}:
1152 Some{total}
1153 case SCon{Chr{c}, t}:
1154 do Maybe<&2, U32>:
1155 n: U32 <- size.one(c, total)
1156 size(t, n)
1157
1158type Builder is Type:
1159 Builder{bytes: Bytes.Bytes, at: U32, partial: U32, bits: U32}
1160
1161def emit.full(full: Bool, out: Bytes.Bytes, +at: U32, +partial: U32, +bits: U32) -> Builder:
1162 match full:
1163 case True{}:
1164 Builder{Bytes.set(out, at, partial), (at + 1 : U32), 0, 0}
1165 case False{}:
1166 Builder{out, at, partial, (bits + 1 : U32)}
1167
1168def emit.bit(+bit: U32, st: Builder) -> Builder:
1169 Builder{out, +at, +partial, +bits} = st
1170 emit.full(U32.is_eq(bits, 7), out, at, ((partial << 1n) .|. bit : U32), bits)
1171
1172def emit.bits(n: Nat, +code: U32, st: Builder) -> Builder:
1173 match n:
1174 case 0n:
1175 st
1176 case 1n+p:
1177 +p = p
1178 emit.bits(p, code, emit.bit(((code >> p) .&. 1 : U32), st))
1179
1180def emit.code(c: Code, st: Builder) -> Builder:
1181 match c:
1182 case Code{bits, width}:
1183 emit.bits(U32.to_nat(width), bits, st)
1184
1185def encode.go(s: String, st: Builder) -> Builder:
1186 match s:
1187 case SNil{}:
1188 st
1189 case SCon{Chr{c}, t}:
1190 encode.go(t, emit.code(code(c), st))
1191
1192def encode.last(more: Bool, out: Bytes.Bytes, +at: U32, +partial: U32, +bits: U32) -> Bytes.Bytes:
1193 match more:
1194 case False{}:
1195 out
1196 case True{}:
1197 +pad = (8 - bits : U32)
1198 Bytes.set(out, at, ((partial << U32.to_nat(pad)) .|. ((1 << U32.to_nat(pad)) - 1 : U32) : U32))
1199def encode.finish(st: Builder) -> Bytes.Bytes:
1200 Builder{out, +at, +partial, +bits} = st
1201 encode.last(U32.is_ne(bits, 0), out, at, partial, bits)
1202
1203
1204def encode.ready(s: String, m: Maybe<&2, U32>) -> Maybe<&1, Bytes.Bytes>:
1205 match m:
1206 case None{}:
1207 None{}
1208 case Some{+bits}:
1209 +len = ((bits >> 3n) + Bool.pick(U32, U32.is_ne((bits .&. 7 : U32), 0), 1, 0) : U32)
1210 Some{encode.finish(encode.go(s, Builder{Bytes.new(len), 0, 0, 0}))}
1211
1212# HPACK text is a byte string: code points above 255 are rejected.
1213def encode(+s: String) -> Maybe<&1, Bytes.Bytes>:
1214 encode.ready(s, size(s, 0))
1215
1216type Decoder is Data:
1217 Decoder{bits: U32, width: U32, rev: String}
1218
1219def decode.found(+octet: U32, rev: String) -> Maybe<&2, Decoder>:
1220 match octet:
1221 case 256:
1222 None{}
1223 case _:
1224 Some{Decoder{0, 0, SCon{Chr{octet}, rev}}}
1225
1226def decode.pending(ok: Bool, +bits: U32, +width: U32, rev: String) -> Maybe<&2, Decoder>:
1227 match ok:
1228 case True{}:
1229 Some{Decoder{bits, width, rev}}
1230 case False{}:
1231 None{}
1232def decode.symbol(m: Maybe<&2, U32>, +bits: U32, +width: U32, rev: String) -> Maybe<&2, Decoder>:
1233 match m:
1234 case Some{octet}:
1235 decode.found(octet, rev)
1236 case None{}:
1237 decode.pending(U32.is_lt(width, 30), bits, width, rev)
1238
1239
1240def decode.bit(d: Decoder, +bit: U32) -> Maybe<&2, Decoder>:
1241 Decoder{+bits, +width, rev} = d
1242 +code = ((bits << 1n) .|. bit : U32)
1243 +n = (width + 1 : U32)
1244 decode.symbol(symbol(n, code), code, n, rev)
1245
1246def decode.step(n: Nat, +byte: U32, d: Decoder) -> Maybe<&2, Decoder>:
1247 match n:
1248 case 0n:
1249 Some{d}
1250 case 1n+p:
1251 +p = p
1252 do Maybe<&2, Decoder>:
1253 next: Decoder <- decode.bit(d, ((byte >> p) .&. 1 : U32))
1254 decode.step(p, byte, next)
1255
1256def with_number.got(-R: Type, m: Maybe<&2, U32>, b: Bytes.Bytes, k: Bytes.Bytes -> U32 -> R) -> R:
1257 match m:
1258 case Some{v}:
1259 k(b, v)
1260 case None{}:
1261 k(b, 0)
1262def with_number(-R: Type, r: Bytes.Bytes & Maybe<&2, U32>, k: Bytes.Bytes -> U32 -> R) -> R:
1263 (b, m) = r
1264 with_number.got(R, m, b, k)
1265
1266
1267def decode.go(n: Nat, b: Bytes.Bytes, +at: U32, d: Decoder) -> Maybe<&2, Decoder>:
1268 match n:
1269 case 0n:
1270 Some{d}
1271 case 1n+p:
1272 with_number(Maybe<&2, Decoder>, Bytes.get(b, at), b => byte =>
1273 do Maybe<&2, Decoder>:
1274 next: Decoder <- decode.step(8n, byte, d)
1275 decode.go(p, b, (at + 1 : U32), next))
1276
1277def decode.tail(ok: Bool, rev: String) -> Maybe<&2, String>:
1278 match ok:
1279 case True{}:
1280 Some{String.reverse(rev)}
1281 case False{}:
1282 None{}
1283
1284def decode.finish(m: Maybe<&2, Decoder>) -> Maybe<&2, String>:
1285 match m:
1286 case None{}:
1287 None{}
1288 case Some{Decoder{+bits, +width, rev}}:
1289 decode.tail(Bool.and(U32.is_le(width, 7), U32.is_eq(bits, ((1 << U32.to_nat(width)) - 1 : U32))), rev)
1290
1291def decode(b: Bytes.Bytes) -> Maybe<&2, String>:
1292 Bytes.Bytes{+len, buf} = b
1293 decode.finish(decode.go(U32.to_nat(len), Bytes.Bytes{len, buf}, 0, Decoder{0, 0, SNil{}}))