''' <summary>
''' Contains methods to decompress RTF streams that are compressed as 
''' per the <a href="http://msdn.microsoft.com/en-us/library/cc463890%28v=EXCHG.80%29.aspx">[MS-OXRTFCP] 
''' Rich Text Format (RTF) Compression Algorithm</a>.
''' </summary>
Public NotInheritable Class RtfDecompressor

    '//fields
    Private Shared ReadOnly InitialDictionary As Byte()
    Private Shared ReadOnly CrcDictionary As UInteger()

    '//constants
    Private Const HeaderLength As Integer = &H10
    Private Const CircularDictionaryMaxLength As Integer = &H1000

    '//constructors
    Shared Sub New()

        '//initialize dictionary, must be this exact string
        Dim builder = New System.Text.StringBuilder()
        With builder
            .Append("{\rtf1\ansi\mac\deff0\deftab720{\fonttbl;}")
            .Append("{\f0\fnil \froman \fswiss \fmodern \fscript ")
            .Append("\fdecor MS Sans SerifSymbolArialTimes New RomanCourier{\colortbl\red0\green0\blue0")
            .Append(ControlChars.CrLf)
            .Append("\par \pard\plain\f0\fs20\b\i\u\tab\tx")
        End With

        RtfDecompressor.InitialDictionary = System.Text.Encoding.ASCII.GetBytes(builder.ToString()) '//2.1.2.1

        '//crc dictionary must be initialized to these values
        Dim dictionary = New UInteger() {&H0UI, &H77073096UI, &HEE0E612CUI, &H990951BAUI, &H76DC419UI, &H706AF48FUI, &HE963A535UI, &H9E6495A3UI, &HEDB8832UI, &H79DCB8A4UI, &HE0D5E91EUI, &H97D2D988UI,
                                         &H9B64C2BUI, &H7EB17CBDUI, &HE7B82D07UI, &H90BF1D91UI, &H1DB71064UI, &H6AB020F2UI, &HF3B97148UI, &H84BE41DEUI, &H1ADAD47DUI, &H6DDDE4EBUI, &HF4D4B551UI, &H83D385C7UI,
                                         &H136C9856UI, &H646BA8C0UI, &HFD62F97AUI, &H8A65C9ECUI, &H14015C4FUI, &H63066CD9UI, &HFA0F3D63UI, &H8D080DF5UI, &H3B6E20C8UI, &H4C69105EUI, &HD56041E4UI, &HA2677172UI,
                                         &H3C03E4D1UI, &H4B04D447UI, &HD20D85FDUI, &HA50AB56BUI, &H35B5A8FAUI, &H42B2986CUI, &HDBBBC9D6UI, &HACBCF940UI, &H32D86CE3UI, &H45DF5C75UI, &HDCD60DCFUI, &HABD13D59UI,
                                         &H26D930ACUI, &H51DE003AUI, &HC8D75180UI, &HBFD06116UI, &H21B4F4B5UI, &H56B3C423UI, &HCFBA9599UI, &HB8BDA50FUI, &H2802B89EUI, &H5F058808UI, &HC60CD9B2UI, &HB10BE924UI,
                                         &H2F6F7C87UI, &H58684C11UI, &HC1611DABUI, &HB6662D3DUI, &H76DC4190UI, &H1DB7106UI, &H98D220BCUI, &HEFD5102AUI, &H71B18589UI, &H6B6B51FUI, &H9FBFE4A5UI, &HE8B8D433UI,
                                         &H7807C9A2UI, &HF00F934UI, &H9609A88EUI, &HE10E9818UI, &H7F6A0DBBUI, &H86D3D2DUI, &H91646C97UI, &HE6635C01UI, &H6B6B51F4UI, &H1C6C6162UI, &H856530D8UI, &HF262004EUI,
                                         &H6C0695EDUI, &H1B01A57BUI, &H8208F4C1UI, &HF50FC457UI, &H65B0D9C6UI, &H12B7E950UI, &H8BBEB8EAUI, &HFCB9887CUI, &H62DD1DDFUI, &H15DA2D49UI, &H8CD37CF3UI, &HFBD44C65UI,
                                         &H4DB26158UI, &H3AB551CEUI, &HA3BC0074UI, &HD4BB30E2UI, &H4ADFA541UI, &H3DD895D7UI, &HA4D1C46DUI, &HD3D6F4FBUI, &H4369E96AUI, &H346ED9FCUI, &HAD678846UI, &HDA60B8D0UI,
                                         &H44042D73UI, &H33031DE5UI, &HAA0A4C5FUI, &HDD0D7CC9UI, &H5005713CUI, &H270241AAUI, &HBE0B1010UI, &HC90C2086UI, &H5768B525UI, &H206F85B3UI, &HB966D409UI, &HCE61E49FUI,
                                         &H5EDEF90EUI, &H29D9C998UI, &HB0D09822UI, &HC7D7A8B4UI, &H59B33D17UI, &H2EB40D81UI, &HB7BD5C3BUI, &HC0BA6CADUI, &HEDB88320UI, &H9ABFB3B6UI, &H3B6E20CUI, &H74B1D29AUI,
                                         &HEAD54739UI, &H9DD277AFUI, &H4DB2615UI, &H73DC1683UI, &HE3630B12UI, &H94643B84UI, &HD6D6A3EUI, &H7A6A5AA8UI, &HE40ECF0BUI, &H9309FF9DUI, &HA00AE27UI, &H7D079EB1UI,
                                         &HF00F9344UI, &H8708A3D2UI, &H1E01F268UI, &H6906C2FEUI, &HF762575DUI, &H806567CBUI, &H196C3671UI, &H6E6B06E7UI, &HFED41B76UI, &H89D32BE0UI, &H10DA7A5AUI, &H67DD4ACCUI,
                                         &HF9B9DF6FUI, &H8EBEEFF9UI, &H17B7BE43UI, &H60B08ED5UI, &HD6D6A3E8UI, &HA1D1937EUI, &H38D8C2C4UI, &H4FDFF252UI, &HD1BB67F1UI, &HA6BC5767UI, &H3FB506DDUI, &H48B2364BUI,
                                         &HD80D2BDAUI, &HAF0A1B4CUI, &H36034AF6UI, &H41047A60UI, &HDF60EFC3UI, &HA867DF55UI, &H316E8EEFUI, &H4669BE79UI, &HCB61B38CUI, &HBC66831AUI, &H256FD2A0UI, &H5268E236UI,
                                         &HCC0C7795UI, &HBB0B4703UI, &H220216B9UI, &H5505262FUI, &HC5BA3BBEUI, &HB2BD0B28UI, &H2BB45A92UI, &H5CB36A04UI, &HC2D7FFA7UI, &HB5D0CF31UI, &H2CD99E8BUI, &H5BDEAE1DUI,
                                         &H9B64C2B0UI, &HEC63F226UI, &H756AA39CUI, &H26D930AUI, &H9C0906A9UI, &HEB0E363FUI, &H72076785UI, &H5005713UI, &H95BF4A82UI, &HE2B87A14UI, &H7BB12BAEUI, &HCB61B38UI,
                                         &H92D28E9BUI, &HE5D5BE0DUI, &H7CDCEFB7UI, &HBDBDF21UI, &H86D3D2D4UI, &HF1D4E242UI, &H68DDB3F8UI, &H1FDA836EUI, &H81BE16CDUI, &HF6B9265BUI, &H6FB077E1UI, &H18B74777UI,
                                         &H88085AE6UI, &HFF0F6A70UI, &H66063BCAUI, &H11010B5CUI, &H8F659EFFUI, &HF862AE69UI, &H616BFFD3UI, &H166CCF45UI, &HA00AE278UI, &HD70DD2EEUI, &H4E048354UI, &H3903B3C2UI,
                                         &HA7672661UI, &HD06016F7UI, &H4969474DUI, &H3E6E77DBUI, &HAED16A4AUI, &HD9D65ADCUI, &H40DF0B66UI, &H37D83BF0UI, &HA9BCAE53UI, &HDEBB9EC5UI, &H47B2CF7FUI, &H30B5FFE9UI,
                                         &HBDBDF21CUI, &HCABAC28AUI, &H53B39330UI, &H24B4A3A6UI, &HBAD03605UI, &HCDD70693UI, &H54DE5729UI, &H23D967BFUI, &HB3667A2EUI, &HC4614AB8UI, &H5D681B02UI, &H2A6F2B94UI,
                                         &HB40BBE37UI, &HC30C8EA1UI, &H5A05DF1BUI, &H2D02EF8D}

        RtfDecompressor.CrcDictionary = dictionary '//2.1.2.2.1
    End Sub

    Private Sub New()
    End Sub

    '//methods
    ''' <summary>
    ''' Decompresses an RTF <see cref="System.IO.Stream">System.IO.Stream</see> and returns the decompressed stream as an array of bytes.
    ''' </summary>
    ''' <param name="stream">The <see cref="System.IO.Stream">System.IO.Stream</see> to decompress.</param>
    ''' <exception cref="System.IndexOutOfRangeException">Thrown when the stream reaches a corrupt or unpredicted state.</exception>
    ''' <returns>The decompressed byte stream.</returns>
    Public Shared Function Decompress(stream As IO.Stream) As Byte()
        Return RtfDecompressor.Decompress(stream, False)
    End Function

    ''' <summary>
    ''' Decompresses an RTF <see cref="System.IO.Stream">System.IO.Stream</see> and returns the decompressed stream as an array of bytes.
    ''' </summary>
    ''' <param name="stream">The <see cref="System.IO.Stream">System.IO.Stream</see> to decompress.</param>
    ''' <param name="enforceCrc">True to enforce a CRC check; otherwise, false to ignore CRC checking.</param>
    ''' <exception cref="System.IndexOutOfRangeException">Thrown when the stream reaches a corrupt or unpredicted state.</exception>
    ''' <returns>The decompressed byte stream.</returns>
    Public Shared Function Decompress(stream As IO.Stream, enforceCrc As Boolean) As Byte()
        If stream.CanRead Then
            Dim buffer(CInt(stream.Length) - 1) As Byte
            stream.Read(buffer, 0, CInt(stream.Length))
            Return RtfDecompressor.Decompress(buffer, enforceCrc)
        End If
        Return Nothing
    End Function

    ''' <summary>
    ''' Decompresses an RTF byte stream and returns the decompressed stream as an array of bytes.
    ''' </summary>
    ''' <param name="data">The compressed stream to decompress.</param>
    ''' <exception cref="System.IndexOutOfRangeException">Thrown when the stream reaches a corrupt or unpredicted state.</exception>
    ''' <returns>The decompressed byte stream.</returns>
    Public Shared Function Decompress(data As Byte()) As Byte()
        Return RtfDecompressor.Decompress(data, False)
    End Function

    ''' <summary>
    ''' Decompresses an RTF byte stream and returns the decompressed stream as an array of bytes.
    ''' </summary>
    ''' <param name="data">The compressed stream to decompress.</param>
    ''' <param name="enforceCrc">True to enforce a CRC check; otherwise, false to ignore CRC checking.</param>
    ''' <exception cref="System.IndexOutOfRangeException">Thrown when the stream reaches a corrupt or unpredicted state.</exception>
    ''' <returns>The decompressed byte stream.</returns>
    Public Shared Function Decompress(data As Byte(), enforceCrc As Boolean) As Byte()

        '//2.2.3.1.2
        Dim header = New RtfHeader(data)
        Dim initialLength = RtfDecompressor.InitialDictionary.Length

        Select Case header.compType
            Case CompressionTypes.UnCompressed

                '//data is uncompressed, this is very rare
                Dim destination(data.Length - 1) As Byte
                data.CopyTo(destination, 0)

                '//2.2.3
                Return destination

            Case CompressionTypes.Compressed

                '//2.2.3
                If enforceCrc Then
                    Dim crc = RtfDecompressor.CalculateCrc(data, RtfDecompressor.HeaderLength)
                    If Not crc = header.crc Then
                        Throw New ArgumentException("Input stream is corrupt.")
                    End If
                End If

                Dim dictionary(RtfDecompressor.CircularDictionaryMaxLength - 1) As Byte
                Using destination = New IO.MemoryStream(CInt(header.rawSize))
                    Dim dictionaryWrite = initialLength

                    Array.Copy(RtfDecompressor.InitialDictionary, 0, dictionary, 0, initialLength)

                    Try
                        For i = RtfDecompressor.HeaderLength To data.Length - 1
                            Dim current = data(i)
                            Dim control = New RtfControl(current)
                            Dim offset = 1

                            For j = 0 To control.flags.Length - 1
                                Dim flag = control.flags(j)
                                If flag Then

                                    '//literal bit
                                    destination.WriteByte(data(i + offset))
                                    dictionary(dictionaryWrite) = (data(i + offset))
                                    dictionaryWrite += 1

                                    RtfDecompressor.EnsureDictionaryPosition(dictionaryWrite)
                                Else

                                    '//reference bit, create word from two bytes
                                    Dim word = (CInt(data(i + offset)) << 8) Or data(i + (offset + 1))

                                    '//get the offset into the dictionary
                                    Dim upper = (word And &HFFF0) >> 4

                                    '//get the length of bytes to copy
                                    Dim lower = (word And &HF) + 2

                                    If upper = dictionaryWrite Then
                                        '//special dictionary reference means that decompression is complete
                                        Return destination.ToArray()
                                    End If

                                    '//cannot just copy the bytes over because the dictionary is a
                                    '//circular array so it must properly wrap to beginning
                                    For k = 0 To lower - 1
                                        Dim correctedOffset = (upper + k)
                                        RtfDecompressor.EnsureDictionaryPosition(correctedOffset)

                                        If destination.Position = header.rawSize Then
                                            '//this is the last token, the rest is just padding
                                            Return destination.ToArray()
                                        End If

                                        destination.WriteByte(dictionary(correctedOffset))
                                        dictionary(dictionaryWrite) = dictionary(correctedOffset)
                                        dictionaryWrite += 1

                                        RtfDecompressor.EnsureDictionaryPosition(dictionaryWrite)
                                    Next

                                    offset += 1
                                End If

                                offset += 1
                            Next

                            '//run is processed
                            i += (control.length - 1)

                        Next
                    Catch ex As IndexOutOfRangeException
                        Return destination.ToArray()
                    End Try
                End Using

            Case Else

                Throw New ArgumentException("Input stream is corrupt.")

        End Select

        Return Nothing
    End Function

    Private Shared Sub EnsureDictionaryPosition(ByRef position As Integer)
        '//2.1.3.1.4
        Do Until position < RtfDecompressor.CircularDictionaryMaxLength
            position -= RtfDecompressor.CircularDictionaryMaxLength
        Loop
    End Sub

    Private Shared Function CalculateCrc(buffer As Byte(), offset As Integer) As UInteger
        '//2.1.3.2
        Dim crc = 0UI
        For i = offset To buffer.Length - 1
            crc = (RtfDecompressor.CrcDictionary(CByte((crc Xor buffer(i)) And &HFF)) Xor (crc >> 8))
        Next
        Return crc
    End Function

    '//enumerations
    Private Enum CompressionTypes As UInteger

        '//2.1.3.1.1
        Compressed = &H75465A4CUI
        UnCompressed = &H414C454DUI

    End Enum

    '//nested types
    <DebuggerStepThrough()> _
    Private Structure RtfControl

        '//fields
        Public flags As BitArray
        Public length As Integer

        '//constructors
        Public Sub New(controlWord As Byte)

            '//2.1.3.1.1
            Me.flags = New BitArray(8)

            Dim zeroes = 0
            For i = 0 To Me.flags.Length - 1

                '//a literal bit (1) will set the flag to true
                Me.flags(i) = ((controlWord And (&H1 << i)) = 0)
                zeroes += (CInt(Me.flags(i)) And &H1)
            Next

            Me.length = ((8 - zeroes) * 2) + zeroes + 1
        End Sub

    End Structure

    <DebuggerStepThrough()> _
    Private Structure RtfHeader

        '//fields
        Public compSize As UInteger
        Public rawSize As UInteger
        Public compType As UInteger
        Public crc As UInteger

        '//constructors
        Public Sub New(header As Byte())
            If Not header.Length >= 16 Then
                Throw New ArgumentException("header length must be greater than or equal to 16")
            End If

            '//2.1.3.1.1
            Me.compSize = RtfHeader.ToUInt32(header, 0)
            Me.rawSize = RtfHeader.ToUInt32(header, 4)
            Me.compType = RtfHeader.ToUInt32(header, 8)
            Me.crc = RtfHeader.ToUInt32(header, 12)
        End Sub

        '//methods
        Private Shared Function ToUInt32(buffer As Byte(), offset As Integer) As UInteger
            Return ((buffer(offset) And &HFFUI) Or _
                   ((buffer(offset + 1) And &HFFUI) << 8) Or _
                   ((buffer(offset + 2) And &HFFUI) << 16) Or _
                   ((buffer(offset + 3) And &HFFUI) << 24)) And &HFFFFFFFFUI
        End Function

    End Structure

End Class