1 namespace System.IO.Compression
2 {
3     using System;
4     using System.Diagnostics;
5     using System.Globalization;
6 
7     // This class maintains a window for decompressed output.
8     // We need to keep this because the decompressed information can be
9     // a literal or a length/distance pair. For length/distance pair,
10     // we need to look back in the output window and copy bytes from there.
11     // We use a byte array of WindowSize circularly.
12     //
13     internal class OutputWindow {
14 
15         private const int WindowSize = 32768;
16         private const int WindowMask = 32767;
17 
18         private byte[] window = new byte[WindowSize]; //The window is 2^15 bytes
19         private int end;       // this is the position to where we should write next byte
20         private int bytesUsed; // The number of bytes in the output window which is not consumed.
21 
22         // Add a byte to output window
Write(byte b)23         public void Write(byte b) {
24             Debug.WriteLineIf(CompressionTracingSwitch.Verbose, String.Format(CultureInfo.InvariantCulture, "Literal: {0}", b), "Compression");
25             Debug.Assert(bytesUsed < WindowSize, "Can't add byte when window is full!");
26             window[end++] = b;
27             end &= WindowMask;
28             ++bytesUsed;
29         }
30 
WriteLengthDistance(int length, int distance)31         public void WriteLengthDistance(int length, int distance) {
32             Debug.WriteLineIf(CompressionTracingSwitch.Verbose, String.Format(CultureInfo.InvariantCulture, "Length/Distance: {0}:{1}", length, distance), "Compression");
33             Debug.Assert((bytesUsed + length) <= WindowSize, "Not enough space");
34 
35             // move backwards distance bytes in the output stream,
36             // and copy length bytes from this position to the output stream.
37             bytesUsed += length;
38             int copyStart = (end - distance) & WindowMask;  // start position for coping.
39 
40             int border = WindowSize - length;
41             if (copyStart <= border && end < border) {
42                 if (length <= distance) {
43                     System.Array.Copy(window, copyStart, window, end, length);
44                     end += length;
45                 } else {
46                     // The referenced string may overlap the current
47                     // position; for example, if the last 2 bytes decoded have values
48                     // X and Y, a string reference with <length = 5, distance = 2>
49                     // adds X,Y,X,Y,X to the output stream.
50                     while (length-- > 0) {
51                         window[end++] = window[copyStart++];
52                     }
53                 }
54             }
55             else { // copy byte by byte
56                 while (length-- > 0) {
57                     window[end++] = window[copyStart++];
58                     end &= WindowMask;
59                     copyStart &= WindowMask;
60                 }
61             }
62         }
63 
64         // Copy up to length of bytes from input directly.
65         // This is used for uncompressed block.
CopyFrom(InputBuffer input, int length)66         public int CopyFrom(InputBuffer input, int length) {
67             length = Math.Min(Math.Min(length, WindowSize - bytesUsed), input.AvailableBytes);
68             int copied;
69 
70             // We might need wrap around to copy all bytes.
71             int tailLen = WindowSize - end;
72             if (length > tailLen) {
73                 // copy the first part
74                 copied = input.CopyTo(window, end, tailLen);
75                 if (copied == tailLen) {
76                     // only try to copy the second part if we have enough bytes in input
77                     copied += input.CopyTo(window, 0, length - tailLen);
78                 }
79             }
80             else {
81                 // only one copy is needed if there is no wrap around.
82                 copied = input.CopyTo(window, end, length);
83             }
84 
85             end = (end + copied) & WindowMask;
86             bytesUsed += copied;
87             return copied;
88         }
89 
90         // Free space in output window
91         public int FreeBytes {
92             get {
93                 return WindowSize - bytesUsed;
94             }
95         }
96 
97         // bytes not consumed in output window
98         public int AvailableBytes {
99             get {
100                 return bytesUsed;
101             }
102         }
103 
104         // copy the decompressed bytes to output array.
CopyTo(byte[] output, int offset, int length)105         public int CopyTo(byte[] output, int offset, int length) {
106             int copy_end;
107 
108             if (length > bytesUsed) {   // we can copy all the decompressed bytes out
109                 copy_end = end;
110                 length = bytesUsed;
111             } else {
112                 copy_end = (end - bytesUsed + length) & WindowMask;  // copy length of bytes
113             }
114 
115             int copied = length;
116 
117             int tailLen = length - copy_end;
118             if ( tailLen > 0) {    // this means we need to copy two parts seperately
119                 // copy tailLen bytes from the end of output window
120                 System.Array.Copy(window, WindowSize - tailLen,
121                                   output, offset, tailLen);
122                 offset += tailLen;
123                 length = copy_end;
124             }
125             System.Array.Copy(window, copy_end - length, output, offset, length);
126             bytesUsed -= copied;
127             Debug.Assert(bytesUsed >= 0, "check this function and find why we copied more bytes than we have");
128             return copied;
129         }
130     }
131 }
132