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

[Jeff McCashland]

Hi Aurélien,

It appears this section of pseudocode was added as part of an update to document handling when input data > 64kb. The algorithm takes two passes over the data for each 64k block in succession, first to do LZ77 compression, then another pass to do Huffman encoding. When both passes are complete, it moved on to the next 64k block. 

Does that help any? 

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: Jeff McCashland <jeffm at microsoft.com> 
Sent: Saturday, June 6, 2020 10:14 AM
To: Aurélien Aptel <aaptel at suse.com>; cifs-protocol at lists.samba.org
Cc: support <support at mail.support.microsoft.com>
Subject: [REG:120060621000848] [MS-XCA] L77+Huffman negative huffman symbol update

[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: https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fsupport.microsoft.com%2Fglobalenglish&data=02%7C01%7Cjeffm%40microsoft.com%7C8ea0acff598741480a5808d80a3d126f%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637270604710709618&sdata=LNJ6HiMioC5ZxYIWdFy%2F3c9En0Q5nNo2oGMjdoc0HE0%3D&reserved=0 | 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

Hi,

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
true:

(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


            Do
                HuffmanSymbol = - HuffmanSymbol
                HuffmanSymbol += (NextBits >> 31)
                NextBits *= 2
                ExtraBits = ExtraBits - 1
                HuffmanSymbol = DecodingTable[HuffmanSymbol]
            While HuffmanSymbol <= 0
        Else
            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.

Cheers,
--
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)