< Summary

Information
Class: System.Net.Http.HPack.Huffman
Assembly: System.Net.Http
File(s): D:\runner\runtime\src\libraries\Common\src\System\Net\Http\aspnetcore\Http2\Hpack\Huffman.cs
Line coverage
0%
Covered lines: 0
Uncovered lines: 636
Coverable lines: 636
Total lines: 806
Line coverage: 0%
Branch coverage
0%
Covered branches: 0
Total branches: 36
Branch coverage: 0%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity NPath complexity Sequence coverage
.cctor()100%110%
GenerateDecodingLookupTree()0%12120%
Decode(...)0%24240%

File(s)

D:\runner\runtime\src\libraries\Common\src\System\Net\Http\aspnetcore\Http2\Hpack\Huffman.cs

#LineLine coverage
 1// Licensed to the .NET Foundation under one or more agreements.
 2// The .NET Foundation licenses this file to you under the MIT license.
 3
 4#nullable enable
 5using System.Diagnostics;
 6using System.Threading;
 7
 8namespace System.Net.Http.HPack
 9{
 10    internal static class Huffman
 11    {
 12        // HPack static huffman code. see: https://httpwg.org/specs/rfc7541.html#huffman.code
 13        // Stored into two tables to optimize its initialization and memory consumption.
 14        private static ReadOnlySpan<uint> EncodingTableCodes => // 257
 015        [
 016            0b11111111_11000000_00000000_00000000,
 017            0b11111111_11111111_10110000_00000000,
 018            0b11111111_11111111_11111110_00100000,
 019            0b11111111_11111111_11111110_00110000,
 020            0b11111111_11111111_11111110_01000000,
 021            0b11111111_11111111_11111110_01010000,
 022            0b11111111_11111111_11111110_01100000,
 023            0b11111111_11111111_11111110_01110000,
 024            0b11111111_11111111_11111110_10000000,
 025            0b11111111_11111111_11101010_00000000,
 026            0b11111111_11111111_11111111_11110000,
 027            0b11111111_11111111_11111110_10010000,
 028            0b11111111_11111111_11111110_10100000,
 029            0b11111111_11111111_11111111_11110100,
 030            0b11111111_11111111_11111110_10110000,
 031            0b11111111_11111111_11111110_11000000,
 032            0b11111111_11111111_11111110_11010000,
 033            0b11111111_11111111_11111110_11100000,
 034            0b11111111_11111111_11111110_11110000,
 035            0b11111111_11111111_11111111_00000000,
 036            0b11111111_11111111_11111111_00010000,
 037            0b11111111_11111111_11111111_00100000,
 038            0b11111111_11111111_11111111_11111000,
 039            0b11111111_11111111_11111111_00110000,
 040            0b11111111_11111111_11111111_01000000,
 041            0b11111111_11111111_11111111_01010000,
 042            0b11111111_11111111_11111111_01100000,
 043            0b11111111_11111111_11111111_01110000,
 044            0b11111111_11111111_11111111_10000000,
 045            0b11111111_11111111_11111111_10010000,
 046            0b11111111_11111111_11111111_10100000,
 047            0b11111111_11111111_11111111_10110000,
 048            0b01010000_00000000_00000000_00000000,
 049            0b11111110_00000000_00000000_00000000,
 050            0b11111110_01000000_00000000_00000000,
 051            0b11111111_10100000_00000000_00000000,
 052            0b11111111_11001000_00000000_00000000,
 053            0b01010100_00000000_00000000_00000000,
 054            0b11111000_00000000_00000000_00000000,
 055            0b11111111_01000000_00000000_00000000,
 056            0b11111110_10000000_00000000_00000000,
 057            0b11111110_11000000_00000000_00000000,
 058            0b11111001_00000000_00000000_00000000,
 059            0b11111111_01100000_00000000_00000000,
 060            0b11111010_00000000_00000000_00000000,
 061            0b01011000_00000000_00000000_00000000,
 062            0b01011100_00000000_00000000_00000000,
 063            0b01100000_00000000_00000000_00000000,
 064            0b00000000_00000000_00000000_00000000,
 065            0b00001000_00000000_00000000_00000000,
 066            0b00010000_00000000_00000000_00000000,
 067            0b01100100_00000000_00000000_00000000,
 068            0b01101000_00000000_00000000_00000000,
 069            0b01101100_00000000_00000000_00000000,
 070            0b01110000_00000000_00000000_00000000,
 071            0b01110100_00000000_00000000_00000000,
 072            0b01111000_00000000_00000000_00000000,
 073            0b01111100_00000000_00000000_00000000,
 074            0b10111000_00000000_00000000_00000000,
 075            0b11111011_00000000_00000000_00000000,
 076            0b11111111_11111000_00000000_00000000,
 077            0b10000000_00000000_00000000_00000000,
 078            0b11111111_10110000_00000000_00000000,
 079            0b11111111_00000000_00000000_00000000,
 080            0b11111111_11010000_00000000_00000000,
 081            0b10000100_00000000_00000000_00000000,
 082            0b10111010_00000000_00000000_00000000,
 083            0b10111100_00000000_00000000_00000000,
 084            0b10111110_00000000_00000000_00000000,
 085            0b11000000_00000000_00000000_00000000,
 086            0b11000010_00000000_00000000_00000000,
 087            0b11000100_00000000_00000000_00000000,
 088            0b11000110_00000000_00000000_00000000,
 089            0b11001000_00000000_00000000_00000000,
 090            0b11001010_00000000_00000000_00000000,
 091            0b11001100_00000000_00000000_00000000,
 092            0b11001110_00000000_00000000_00000000,
 093            0b11010000_00000000_00000000_00000000,
 094            0b11010010_00000000_00000000_00000000,
 095            0b11010100_00000000_00000000_00000000,
 096            0b11010110_00000000_00000000_00000000,
 097            0b11011000_00000000_00000000_00000000,
 098            0b11011010_00000000_00000000_00000000,
 099            0b11011100_00000000_00000000_00000000,
 0100            0b11011110_00000000_00000000_00000000,
 0101            0b11100000_00000000_00000000_00000000,
 0102            0b11100010_00000000_00000000_00000000,
 0103            0b11100100_00000000_00000000_00000000,
 0104            0b11111100_00000000_00000000_00000000,
 0105            0b11100110_00000000_00000000_00000000,
 0106            0b11111101_00000000_00000000_00000000,
 0107            0b11111111_11011000_00000000_00000000,
 0108            0b11111111_11111110_00000000_00000000,
 0109            0b11111111_11100000_00000000_00000000,
 0110            0b11111111_11110000_00000000_00000000,
 0111            0b10001000_00000000_00000000_00000000,
 0112            0b11111111_11111010_00000000_00000000,
 0113            0b00011000_00000000_00000000_00000000,
 0114            0b10001100_00000000_00000000_00000000,
 0115            0b00100000_00000000_00000000_00000000,
 0116            0b10010000_00000000_00000000_00000000,
 0117            0b00101000_00000000_00000000_00000000,
 0118            0b10010100_00000000_00000000_00000000,
 0119            0b10011000_00000000_00000000_00000000,
 0120            0b10011100_00000000_00000000_00000000,
 0121            0b00110000_00000000_00000000_00000000,
 0122            0b11101000_00000000_00000000_00000000,
 0123            0b11101010_00000000_00000000_00000000,
 0124            0b10100000_00000000_00000000_00000000,
 0125            0b10100100_00000000_00000000_00000000,
 0126            0b10101000_00000000_00000000_00000000,
 0127            0b00111000_00000000_00000000_00000000,
 0128            0b10101100_00000000_00000000_00000000,
 0129            0b11101100_00000000_00000000_00000000,
 0130            0b10110000_00000000_00000000_00000000,
 0131            0b01000000_00000000_00000000_00000000,
 0132            0b01001000_00000000_00000000_00000000,
 0133            0b10110100_00000000_00000000_00000000,
 0134            0b11101110_00000000_00000000_00000000,
 0135            0b11110000_00000000_00000000_00000000,
 0136            0b11110010_00000000_00000000_00000000,
 0137            0b11110100_00000000_00000000_00000000,
 0138            0b11110110_00000000_00000000_00000000,
 0139            0b11111111_11111100_00000000_00000000,
 0140            0b11111111_10000000_00000000_00000000,
 0141            0b11111111_11110100_00000000_00000000,
 0142            0b11111111_11101000_00000000_00000000,
 0143            0b11111111_11111111_11111111_11000000,
 0144            0b11111111_11111110_01100000_00000000,
 0145            0b11111111_11111111_01001000_00000000,
 0146            0b11111111_11111110_01110000_00000000,
 0147            0b11111111_11111110_10000000_00000000,
 0148            0b11111111_11111111_01001100_00000000,
 0149            0b11111111_11111111_01010000_00000000,
 0150            0b11111111_11111111_01010100_00000000,
 0151            0b11111111_11111111_10110010_00000000,
 0152            0b11111111_11111111_01011000_00000000,
 0153            0b11111111_11111111_10110100_00000000,
 0154            0b11111111_11111111_10110110_00000000,
 0155            0b11111111_11111111_10111000_00000000,
 0156            0b11111111_11111111_10111010_00000000,
 0157            0b11111111_11111111_10111100_00000000,
 0158            0b11111111_11111111_11101011_00000000,
 0159            0b11111111_11111111_10111110_00000000,
 0160            0b11111111_11111111_11101100_00000000,
 0161            0b11111111_11111111_11101101_00000000,
 0162            0b11111111_11111111_01011100_00000000,
 0163            0b11111111_11111111_11000000_00000000,
 0164            0b11111111_11111111_11101110_00000000,
 0165            0b11111111_11111111_11000010_00000000,
 0166            0b11111111_11111111_11000100_00000000,
 0167            0b11111111_11111111_11000110_00000000,
 0168            0b11111111_11111111_11001000_00000000,
 0169            0b11111111_11111110_11100000_00000000,
 0170            0b11111111_11111111_01100000_00000000,
 0171            0b11111111_11111111_11001010_00000000,
 0172            0b11111111_11111111_01100100_00000000,
 0173            0b11111111_11111111_11001100_00000000,
 0174            0b11111111_11111111_11001110_00000000,
 0175            0b11111111_11111111_11101111_00000000,
 0176            0b11111111_11111111_01101000_00000000,
 0177            0b11111111_11111110_11101000_00000000,
 0178            0b11111111_11111110_10010000_00000000,
 0179            0b11111111_11111111_01101100_00000000,
 0180            0b11111111_11111111_01110000_00000000,
 0181            0b11111111_11111111_11010000_00000000,
 0182            0b11111111_11111111_11010010_00000000,
 0183            0b11111111_11111110_11110000_00000000,
 0184            0b11111111_11111111_11010100_00000000,
 0185            0b11111111_11111111_01110100_00000000,
 0186            0b11111111_11111111_01111000_00000000,
 0187            0b11111111_11111111_11110000_00000000,
 0188            0b11111111_11111110_11111000_00000000,
 0189            0b11111111_11111111_01111100_00000000,
 0190            0b11111111_11111111_11010110_00000000,
 0191            0b11111111_11111111_11011000_00000000,
 0192            0b11111111_11111111_00000000_00000000,
 0193            0b11111111_11111111_00001000_00000000,
 0194            0b11111111_11111111_10000000_00000000,
 0195            0b11111111_11111111_00010000_00000000,
 0196            0b11111111_11111111_11011010_00000000,
 0197            0b11111111_11111111_10000100_00000000,
 0198            0b11111111_11111111_11011100_00000000,
 0199            0b11111111_11111111_11011110_00000000,
 0200            0b11111111_11111110_10100000_00000000,
 0201            0b11111111_11111111_10001000_00000000,
 0202            0b11111111_11111111_10001100_00000000,
 0203            0b11111111_11111111_10010000_00000000,
 0204            0b11111111_11111111_11100000_00000000,
 0205            0b11111111_11111111_10010100_00000000,
 0206            0b11111111_11111111_10011000_00000000,
 0207            0b11111111_11111111_11100010_00000000,
 0208            0b11111111_11111111_11111000_00000000,
 0209            0b11111111_11111111_11111000_01000000,
 0210            0b11111111_11111110_10110000_00000000,
 0211            0b11111111_11111110_00100000_00000000,
 0212            0b11111111_11111111_10011100_00000000,
 0213            0b11111111_11111111_11100100_00000000,
 0214            0b11111111_11111111_10100000_00000000,
 0215            0b11111111_11111111_11110110_00000000,
 0216            0b11111111_11111111_11111000_10000000,
 0217            0b11111111_11111111_11111000_11000000,
 0218            0b11111111_11111111_11111001_00000000,
 0219            0b11111111_11111111_11111011_11000000,
 0220            0b11111111_11111111_11111011_11100000,
 0221            0b11111111_11111111_11111001_01000000,
 0222            0b11111111_11111111_11110001_00000000,
 0223            0b11111111_11111111_11110110_10000000,
 0224            0b11111111_11111110_01000000_00000000,
 0225            0b11111111_11111111_00011000_00000000,
 0226            0b11111111_11111111_11111001_10000000,
 0227            0b11111111_11111111_11111100_00000000,
 0228            0b11111111_11111111_11111100_00100000,
 0229            0b11111111_11111111_11111001_11000000,
 0230            0b11111111_11111111_11111100_01000000,
 0231            0b11111111_11111111_11110010_00000000,
 0232            0b11111111_11111111_00100000_00000000,
 0233            0b11111111_11111111_00101000_00000000,
 0234            0b11111111_11111111_11111010_00000000,
 0235            0b11111111_11111111_11111010_01000000,
 0236            0b11111111_11111111_11111111_11010000,
 0237            0b11111111_11111111_11111100_01100000,
 0238            0b11111111_11111111_11111100_10000000,
 0239            0b11111111_11111111_11111100_10100000,
 0240            0b11111111_11111110_11000000_00000000,
 0241            0b11111111_11111111_11110011_00000000,
 0242            0b11111111_11111110_11010000_00000000,
 0243            0b11111111_11111111_00110000_00000000,
 0244            0b11111111_11111111_10100100_00000000,
 0245            0b11111111_11111111_00111000_00000000,
 0246            0b11111111_11111111_01000000_00000000,
 0247            0b11111111_11111111_11100110_00000000,
 0248            0b11111111_11111111_10101000_00000000,
 0249            0b11111111_11111111_10101100_00000000,
 0250            0b11111111_11111111_11110111_00000000,
 0251            0b11111111_11111111_11110111_10000000,
 0252            0b11111111_11111111_11110100_00000000,
 0253            0b11111111_11111111_11110101_00000000,
 0254            0b11111111_11111111_11111010_10000000,
 0255            0b11111111_11111111_11101000_00000000,
 0256            0b11111111_11111111_11111010_11000000,
 0257            0b11111111_11111111_11111100_11000000,
 0258            0b11111111_11111111_11111011_00000000,
 0259            0b11111111_11111111_11111011_01000000,
 0260            0b11111111_11111111_11111100_11100000,
 0261            0b11111111_11111111_11111101_00000000,
 0262            0b11111111_11111111_11111101_00100000,
 0263            0b11111111_11111111_11111101_01000000,
 0264            0b11111111_11111111_11111101_01100000,
 0265            0b11111111_11111111_11111111_11100000,
 0266            0b11111111_11111111_11111101_10000000,
 0267            0b11111111_11111111_11111101_10100000,
 0268            0b11111111_11111111_11111101_11000000,
 0269            0b11111111_11111111_11111101_11100000,
 0270            0b11111111_11111111_11111110_00000000,
 0271            0b11111111_11111111_11111011_10000000,
 0272            0b11111111_11111111_11111111_11111100,
 0273        ];
 274
 275        private static ReadOnlySpan<byte> EncodingTableBitLengths => // 257
 0276        [
 0277            13,
 0278            23,
 0279            28,
 0280            28,
 0281            28,
 0282            28,
 0283            28,
 0284            28,
 0285            28,
 0286            24,
 0287            30,
 0288            28,
 0289            28,
 0290            30,
 0291            28,
 0292            28,
 0293            28,
 0294            28,
 0295            28,
 0296            28,
 0297            28,
 0298            28,
 0299            30,
 0300            28,
 0301            28,
 0302            28,
 0303            28,
 0304            28,
 0305            28,
 0306            28,
 0307            28,
 0308            28,
 0309            6,
 0310            10,
 0311            10,
 0312            12,
 0313            13,
 0314            6,
 0315            8,
 0316            11,
 0317            10,
 0318            10,
 0319            8,
 0320            11,
 0321            8,
 0322            6,
 0323            6,
 0324            6,
 0325            5,
 0326            5,
 0327            5,
 0328            6,
 0329            6,
 0330            6,
 0331            6,
 0332            6,
 0333            6,
 0334            6,
 0335            7,
 0336            8,
 0337            15,
 0338            6,
 0339            12,
 0340            10,
 0341            13,
 0342            6,
 0343            7,
 0344            7,
 0345            7,
 0346            7,
 0347            7,
 0348            7,
 0349            7,
 0350            7,
 0351            7,
 0352            7,
 0353            7,
 0354            7,
 0355            7,
 0356            7,
 0357            7,
 0358            7,
 0359            7,
 0360            7,
 0361            7,
 0362            7,
 0363            7,
 0364            7,
 0365            8,
 0366            7,
 0367            8,
 0368            13,
 0369            19,
 0370            13,
 0371            14,
 0372            6,
 0373            15,
 0374            5,
 0375            6,
 0376            5,
 0377            6,
 0378            5,
 0379            6,
 0380            6,
 0381            6,
 0382            5,
 0383            7,
 0384            7,
 0385            6,
 0386            6,
 0387            6,
 0388            5,
 0389            6,
 0390            7,
 0391            6,
 0392            5,
 0393            5,
 0394            6,
 0395            7,
 0396            7,
 0397            7,
 0398            7,
 0399            7,
 0400            15,
 0401            11,
 0402            14,
 0403            13,
 0404            28,
 0405            20,
 0406            22,
 0407            20,
 0408            20,
 0409            22,
 0410            22,
 0411            22,
 0412            23,
 0413            22,
 0414            23,
 0415            23,
 0416            23,
 0417            23,
 0418            23,
 0419            24,
 0420            23,
 0421            24,
 0422            24,
 0423            22,
 0424            23,
 0425            24,
 0426            23,
 0427            23,
 0428            23,
 0429            23,
 0430            21,
 0431            22,
 0432            23,
 0433            22,
 0434            23,
 0435            23,
 0436            24,
 0437            22,
 0438            21,
 0439            20,
 0440            22,
 0441            22,
 0442            23,
 0443            23,
 0444            21,
 0445            23,
 0446            22,
 0447            22,
 0448            24,
 0449            21,
 0450            22,
 0451            23,
 0452            23,
 0453            21,
 0454            21,
 0455            22,
 0456            21,
 0457            23,
 0458            22,
 0459            23,
 0460            23,
 0461            20,
 0462            22,
 0463            22,
 0464            22,
 0465            23,
 0466            22,
 0467            22,
 0468            23,
 0469            26,
 0470            26,
 0471            20,
 0472            19,
 0473            22,
 0474            23,
 0475            22,
 0476            25,
 0477            26,
 0478            26,
 0479            26,
 0480            27,
 0481            27,
 0482            26,
 0483            24,
 0484            25,
 0485            19,
 0486            21,
 0487            26,
 0488            27,
 0489            27,
 0490            26,
 0491            27,
 0492            24,
 0493            21,
 0494            21,
 0495            26,
 0496            26,
 0497            28,
 0498            27,
 0499            27,
 0500            27,
 0501            20,
 0502            24,
 0503            20,
 0504            21,
 0505            22,
 0506            21,
 0507            21,
 0508            23,
 0509            22,
 0510            22,
 0511            25,
 0512            25,
 0513            24,
 0514            24,
 0515            26,
 0516            23,
 0517            26,
 0518            27,
 0519            26,
 0520            26,
 0521            27,
 0522            27,
 0523            27,
 0524            27,
 0525            27,
 0526            28,
 0527            27,
 0528            27,
 0529            27,
 0530            27,
 0531            27,
 0532            26,
 0533            30
 0534        ];
 535
 0536        private static readonly ushort[] s_decodingTree = GenerateDecodingLookupTree();
 537
 538        public static (uint encoded, int bitLength) Encode(int data)
 539        {
 540            return (EncodingTableCodes[data], EncodingTableBitLengths[data]);
 541        }
 542
 543        private static ushort[] GenerateDecodingLookupTree()
 0544        {
 545            // Decoding lookup tree is a tree of 8 bit lookup tables stored in
 546            // one dimensional array of ushort to reduce allocations.
 547            // First 256 ushort is lookup table with index 0, next 256 ushort is lookup table with index 1, etc...
 548            // lookup_value = [(lookup_table_index << 8) + lookup_index]
 549
 550            // lookup_index is next 8 bits of huffman code, if there is less than 8 bits in source.
 551            // lookup_index MUST be aligned to 8 bits with LSB bits set to anything (zeros are recommended).
 552
 553            // Lookup value is encoded in ushort as either.
 554            // -----------------------------------------------------------------
 555            //  15  14  13  12  11  10   9   8   7   6   5   4   3   2   1   0
 556            // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 557            // | 1 |   next_lookup_table_index |            not_used           |
 558            // +---+---------------------------+-------------------------------+
 559            // or
 560            // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 561            // | 0 |     number_of_used_bits   |              octet            |
 562            // +---+---------------------------+-------------------------------+
 563
 564            // Bit 15 unset indicates a leaf value of decoding tree.
 565            // For example value 0x0241 means that we have reached end of huffman code
 566            // with result byte 0x41 'A' and from lookup bits only rightmost 2 bits were used
 567            // and rest of bits are part of next huffman code.
 568
 569            // Bit 15 set indicates that code is not yet decoded and next lookup table index shall be used
 570            // for next n bits of huffman code.
 571            // 0 in 'next lookup table index' is considered as decoding error - invalid huffman code
 572
 573            // Because HPack uses static huffman code defined in RFC https://httpwg.org/specs/rfc7541.html#huffman.code
 574            // it is guaranteed that for this huffman code generated decoding lookup tree MUST consist of exactly 15 loo
 0575            var decodingTree = new ushort[15 * 256];
 576
 0577            ReadOnlySpan<uint> encodingTableCodes = EncodingTableCodes;
 0578            ReadOnlySpan<byte> encodingTableBitLengths = EncodingTableBitLengths;
 579
 0580            int allocatedLookupTableIndex = 0;
 581            // Create traverse path for all 0..256 octets, 256 is EOS, see: http://httpwg.org/specs/rfc7541.html#rfc.sec
 0582            for (int octet = 0; octet <= 256; octet++)
 0583            {
 0584                uint code = encodingTableCodes[octet];
 0585                int bitLength = encodingTableBitLengths[octet];
 586
 0587                int lookupTableIndex = 0;
 0588                int bitsLeft = bitLength;
 0589                while (bitsLeft > 0)
 0590                {
 591                    // read next 8 bits from huffman code
 0592                    int indexInLookupTable = (int)(code >> (32 - 8));
 593
 0594                    if (bitsLeft <= 8)
 0595                    {
 596                        // Reached last lookup table for this huffman code.
 597
 598                        // Identical lookup value has to be stored for every combination of unused bits,
 599                        // For example: 12 bit code could be looked up during decoding as this:
 600                        // ---------------------------------
 601                        //   7   6   5   4   3   2   1   0
 602                        // +---+---+---+---+---+---+---+---+
 603                        // |last_code_bits | next_code_bits|
 604                        // +-------------------------------+
 605                        // next_code_bits are 'random' bits of next huffman code, so in order for lookup
 606                        // to work, lookup value has to be stored for all 4 unused bits, in this case for suffix 0..15
 0607                        int suffixCount = 1 << (8 - bitsLeft);
 0608                        for (int suffix = 0; suffix < suffixCount; suffix++)
 0609                        {
 0610                            if (octet == 256)
 0611                            {
 612                                // EOS (in our case 256) have special meaning in HPack static huffman code
 613                                // see: http://httpwg.org/specs/rfc7541.html#rfc.section.5.2
 614                                // > A Huffman-encoded string literal containing the EOS symbol MUST be treated as a dec
 615                                // To force decoding error we store 0 as 'next lookup table index' which MUST be treated
 616
 617                                // Invalid huffman code - EOS
 618                                // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 619                                // | 1 | 0   0   0   0   0   0   0 | 1   1   1   1   1   1   1   1 |
 620                                // +---+---------------------------+-------------------------------+
 0621                                decodingTree[(lookupTableIndex << 8) + (indexInLookupTable | suffix)] = 0x80ff;
 0622                            }
 623                            else
 0624                            {
 625                                // Leaf lookup value
 626                                // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 627                                // | 0 |     number_of_used_bits   |              code             |
 628                                // +---+---------------------------+-------------------------------+
 0629                                decodingTree[(lookupTableIndex << 8) + (indexInLookupTable | suffix)] = (ushort)((bitsLe
 0630                            }
 0631                        }
 0632                    }
 633                    else
 0634                    {
 635                        // More than 8 bits left in huffman code means that we need to traverse to another lookup table 
 0636                        ushort lookupValue = decodingTree[(lookupTableIndex << 8) + indexInLookupTable];
 637
 638                        // Because next_lookup_table_index can not be 0, as 0 is index of root table, default value of a
 639                        // means that we have not initialized it yet => lookup table MUST be allocated and its index ass
 640                        // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 641                        // | 1 |   next_lookup_table_index |            not_used           |
 642                        // +---+---------------------------+-------------------------------+
 0643                        if (lookupValue == 0)
 0644                        {
 0645                            ++allocatedLookupTableIndex;
 0646                            decodingTree[(lookupTableIndex << 8) + indexInLookupTable] = (ushort)((0x80 | allocatedLooku
 0647                            lookupTableIndex = allocatedLookupTableIndex;
 0648                        }
 649                        else
 0650                        {
 0651                            lookupTableIndex = (lookupValue & 0x7f00) >> 8;
 0652                        }
 0653                    }
 654
 0655                    bitsLeft -= 8;
 0656                    code <<= 8;
 0657                }
 0658            }
 659
 0660            return decodingTree;
 0661        }
 662
 663        /// <summary>
 664        /// Decodes a Huffman encoded string from a byte array.
 665        /// </summary>
 666        /// <param name="src">The source byte array containing the encoded data.</param>
 667        /// <param name="dstArray">The destination byte array to store the decoded data.  This may grow if its size is i
 668        /// <returns>The number of decoded symbols.</returns>
 669        public static int Decode(ReadOnlySpan<byte> src, ref byte[] dstArray)
 0670        {
 671            // The code below implements the decoding logic for an HPack huffman encoded literal values.
 672            // https://httpwg.org/specs/rfc7541.html#string.literal.representation
 673            //
 674            // To decode a symbol, we traverse the decoding lookup table tree by 8 bits for each lookup
 675            // until we found a leaf - which contains decoded symbol (octet)
 676            //
 677            // see comments in GenerateDecodingLookupTree() describing decoding table
 678
 0679            Span<byte> dst = dstArray;
 0680            Debug.Assert(dst.Length > 0);
 681
 0682            ushort[] decodingTree = s_decodingTree;
 683
 0684            int lookupTableIndex = 0;
 685            int lookupIndex;
 686
 0687            uint acc = 0;
 0688            int bitsInAcc = 0;
 689
 0690            int i = 0;
 0691            int j = 0;
 0692            while (i < src.Length)
 0693            {
 694                // Load next 8 bits into accumulator.
 0695                acc <<= 8;
 0696                acc |= src[i++];
 0697                bitsInAcc += 8;
 698
 699                // Decode bits in accumulator.
 700                do
 0701                {
 0702                    lookupIndex = (byte)(acc >> (bitsInAcc - 8));
 703
 0704                    int lookupValue = decodingTree[(lookupTableIndex << 8) + lookupIndex];
 705
 0706                    if (lookupValue < 0x80_00)
 0707                    {
 708                        // Octet found.
 709                        // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 710                        // | 0 |     number_of_used_bits   |              octet            |
 711                        // +---+---------------------------+-------------------------------+
 0712                        if (j == dst.Length)
 0713                        {
 0714                            Array.Resize(ref dstArray, dst.Length * 2);
 0715                            dst = dstArray;
 0716                        }
 0717                        dst[j++] = (byte)lookupValue;
 718
 719                        // Start lookup of next symbol
 0720                        lookupTableIndex = 0;
 0721                        bitsInAcc -= lookupValue >> 8;
 0722                    }
 723                    else
 0724                    {
 725                        // Traverse to next lookup table.
 726                        // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 727                        // | 1 |   next_lookup_table_index |            not_used           |
 728                        // +---+---------------------------+-------------------------------+
 0729                        lookupTableIndex = (lookupValue & 0x7f00) >> 8;
 0730                        if (lookupTableIndex == 0)
 0731                        {
 732                            // No valid symbol could be decoded or EOS was decoded
 0733                            throw new HuffmanDecodingException(SR.net_http_hpack_huffman_decode_failed);
 734                        }
 0735                        bitsInAcc -= 8;
 0736                    }
 0737                } while (bitsInAcc >= 8);
 0738            }
 739
 740            // Finish decoding last < 8 bits of src.
 741            // Processing of the last byte has to handle several corner cases
 742            // so it's extracted outside of the main loop for performance reasons.
 0743            while (bitsInAcc > 0)
 0744            {
 0745                Debug.Assert(bitsInAcc < 8);
 746
 747                // Check for correct EOS, which is padding with ones till end of byte
 748                // when we STARTED new huffman code in last 8 bits (lookupTableIndex was reset to 0 -> root lookup table
 0749                if (lookupTableIndex == 0)
 0750                {
 751                    // Check if all remaining bits are ones.
 0752                    uint ones = uint.MaxValue >> (32 - bitsInAcc);
 0753                    if ((acc & ones) == ones)
 0754                    {
 755                        // Is it a EOS. See: http://httpwg.org/specs/rfc7541.html#rfc.section.5.2
 0756                        break;
 757                    }
 0758                }
 759
 760                // Lookup index has to be 8 bits aligned to MSB
 0761                lookupIndex = (byte)(acc << (8 - bitsInAcc));
 762
 0763                int lookupValue = decodingTree[(lookupTableIndex << 8) + lookupIndex];
 764
 0765                if (lookupValue < 0x80_00)
 0766                {
 767                    // Octet found.
 768                    // +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 769                    // | 0 |     number_of_used_bits   |              octet            |
 770                    // +---+---------------------------+-------------------------------+
 0771                    bitsInAcc -= lookupValue >> 8;
 772
 0773                    if (bitsInAcc < 0)
 0774                    {
 775                        // Last looked up code had more bits than was left in accumulator which indicated invalid or inc
 0776                        throw new HuffmanDecodingException(SR.net_http_hpack_huffman_decode_failed);
 777                    }
 778
 0779                    if (j == dst.Length)
 0780                    {
 0781                        Array.Resize(ref dstArray, dst.Length * 2);
 0782                        dst = dstArray;
 0783                    }
 0784                    dst[j++] = (byte)lookupValue;
 785
 786                    // Set table index to root - start of new huffman code.
 0787                    lookupTableIndex = 0;
 0788                }
 789                else
 0790                {
 791                    // Src was depleted in middle of lookup tree or EOS was decoded.
 0792                    throw new HuffmanDecodingException(SR.net_http_hpack_huffman_decode_failed);
 793                }
 0794            }
 795
 0796            if (lookupTableIndex != 0)
 0797            {
 798                // Finished in middle of traversing - no valid symbol could be decoded
 799                // or too long EOS padding (7 bits plus). See: http://httpwg.org/specs/rfc7541.html#rfc.section.5.2
 0800                throw new HuffmanDecodingException(SR.net_http_hpack_huffman_decode_failed);
 801            }
 802
 0803            return j;
 0804        }
 805    }
 806}
Generated by: ReportGenerator 5.5.1.0
1/13/2026 - 12:47:48 AM
GitHub | reportgenerator.io

Methods/Properties

EncodingTableCodes()
EncodingTableBitLengths()
.cctor()
GenerateDecodingLookupTree()
Decode(System.ReadOnlySpan`1<System.Byte>,System.Byte[]&)