[cifs-protocol] [REG:120060621000848] [MS-XCA] L77+Huffman negative huffman symbol update

Jeff McCashland jeffm at microsoft.com
Sat Jun 6 17:14:19 UTC 2020

[DocHelp to BCC, support on CC, SR ID on Subject]

Hi Aurélien,

Thank you for your question. We have created SR 120060621000848 to track this issue. I will research the question and let you know what I find. 

Best regards,
Jeff McCashland | Senior Escalation Engineer | Microsoft Protocol Open Specifications Team 
Phone: +1 (425) 703-8300 x38300 | Hours: 9am-5pm | Time zone: (UTC-08:00) Pacific Time (US and Canada)
Local country phone number found here: http://support.microsoft.com/globalenglish | Extension 1138300
We value your feedback.  My manager is Jeremy Chapman (jeremyc), +1 (469) 775-2475

-----Original Message-----
From: Aurélien Aptel <aaptel at suse.com> 
Sent: Saturday, June 6, 2020 7:09 AM
To: cifs-protocol at lists.samba.org; Interoperability Documentation Help <dochelp at microsoft.com>
Subject: [EXTERNAL] [MS-XCA] L77+Huffman negative huffman symbol update


The latest version 6.0 of [MS-XCA] the pseudo code of the final
LZ77+huffman decoding added a branch to the pseudocode in 2.2.4 for the
decompression loop which I don't understand.

Huffman decoding table

     CurrentTableEntry = 0
     For BitLength = 1 to 15
         For Symbol = 0 to 511
             If the encoded bit length of Symbol equals BitLength
                 EntryCount = (1 << (15 – BitLength))
                 Repeat EntryCount times
                     If CurrentTableEntry >= 2^15
                         The compressed data is not valid. Return with error.
                     DecodingTable[CurrentTableEntry] = Symbol
                     CurrentTableEntry = CurrentTableEntry + 1
     If CurrentTableEntry does not equal 2^15
         The compressed data is not valid. Return with error.

In the decoding table construction we set all 2^15 possible bits to an existing symbol that occured at least once. So this property must be

(1)    For any X in [0 - (2^15)-1)],  0 <= DecodeTable[X] < 512.

Final decoding

     [...omited beginning...]
     Loop until a literal processing terminating condition
         Next15Bits = NextBits >> (32 – 15)
         HuffmanSymbol = DecodingTable[Next15Bits]
         HuffmanSymbolBitLength = the bit length of HuffmanSymbol, from the table in
                                  the input buffer
(a)      If HuffmanSymbol <= 0
             NextBits <<= HuffmanSymbolBitLength
             ExtraBits -= HuffmanSymbolBitLength

                HuffmanSymbol = - HuffmanSymbol
                HuffmanSymbol += (NextBits >> 31)
                NextBits *= 2
                ExtraBits = ExtraBits - 1
                HuffmanSymbol = DecodingTable[HuffmanSymbol]
            While HuffmanSymbol <= 0
            DecodedBitCount = HuffmanSymbol & 15
            NextBits <<= DecodedBitCount
(b)         ExtraBits -= DedcodedBitCount
        [...omited end...]

In line (a), from propery (1) we know HuffmanSymbol cannot be negative.
So the test is really checking for HuffmanSymbol == 0, which is the valid literal byte 0 but cannot appear?

Basically I don't understand the purpose of this branch started in (a).

In line (b), there is a typo: Dedcoded => Decoded.

Aurélien Aptel / SUSE Labs Samba Team
GPG: 1839 CB5F 9F5B FB9B AA97  8C99 03C8 A49B 521B D5D3 SUSE Software Solutions Germany GmbH, Maxfeldstr. 5, 90409 Nürnberg, DE
GF: Felix Imendörffer, Mary Higgins, Sri Rasiah HRB 247165 (AG München)

More information about the cifs-protocol mailing list