OutputWindow.cs 5.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151
  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. // See the LICENSE file in the project root for more information.
  4. using System;
  5. using System.Diagnostics;
  6. namespace SharpCompress.Compressors.Deflate64
  7. {
  8. /// <summary>
  9. /// This class maintains a window for decompressed output.
  10. /// We need to keep this because the decompressed information can be
  11. /// a literal or a length/distance pair. For length/distance pair,
  12. /// we need to look back in the output window and copy bytes from there.
  13. /// We use a byte array of WindowSize circularly.
  14. /// </summary>
  15. internal sealed class OutputWindow
  16. {
  17. // With Deflate64 we can have up to a 65536 length as well as up to a 65538 distance. This means we need a Window that is at
  18. // least 131074 bytes long so we have space to retrieve up to a full 64kb in lookback and place it in our buffer without
  19. // overwriting existing data. OutputWindow requires that the WindowSize be an exponent of 2, so we round up to 2^18.
  20. private const int WINDOW_SIZE = 262144;
  21. private const int WINDOW_MASK = 262143;
  22. private readonly byte[] _window = new byte[WINDOW_SIZE]; // The window is 2^18 bytes
  23. private int _end; // this is the position to where we should write next byte
  24. private int _bytesUsed; // The number of bytes in the output window which is not consumed.
  25. /// <summary>Add a byte to output window.</summary>
  26. public void Write(byte b)
  27. {
  28. Debug.Assert(_bytesUsed < WINDOW_SIZE, "Can't add byte when window is full!");
  29. _window[_end++] = b;
  30. _end &= WINDOW_MASK;
  31. ++_bytesUsed;
  32. }
  33. public void WriteLengthDistance(int length, int distance)
  34. {
  35. Debug.Assert((_bytesUsed + length) <= WINDOW_SIZE, "No Enough space");
  36. // move backwards distance bytes in the output stream,
  37. // and copy length bytes from this position to the output stream.
  38. _bytesUsed += length;
  39. int copyStart = (_end - distance) & WINDOW_MASK; // start position for coping.
  40. int border = WINDOW_SIZE - length;
  41. if (copyStart <= border && _end < border)
  42. {
  43. if (length <= distance)
  44. {
  45. Array.Copy(_window, copyStart, _window, _end, length);
  46. _end += length;
  47. }
  48. else
  49. {
  50. // The referenced string may overlap the current
  51. // position; for example, if the last 2 bytes decoded have values
  52. // X and Y, a string reference with <length = 5, distance = 2>
  53. // adds X,Y,X,Y,X to the output stream.
  54. while (length-- > 0)
  55. {
  56. _window[_end++] = _window[copyStart++];
  57. }
  58. }
  59. }
  60. else
  61. {
  62. // copy byte by byte
  63. while (length-- > 0)
  64. {
  65. _window[_end++] = _window[copyStart++];
  66. _end &= WINDOW_MASK;
  67. copyStart &= WINDOW_MASK;
  68. }
  69. }
  70. }
  71. /// <summary>
  72. /// Copy up to length of bytes from input directly.
  73. /// This is used for uncompressed block.
  74. /// </summary>
  75. public int CopyFrom(InputBuffer input, int length)
  76. {
  77. length = Math.Min(Math.Min(length, WINDOW_SIZE - _bytesUsed), input.AvailableBytes);
  78. int copied;
  79. // We might need wrap around to copy all bytes.
  80. int tailLen = WINDOW_SIZE - _end;
  81. if (length > tailLen)
  82. {
  83. // copy the first part
  84. copied = input.CopyTo(_window, _end, tailLen);
  85. if (copied == tailLen)
  86. {
  87. // only try to copy the second part if we have enough bytes in input
  88. copied += input.CopyTo(_window, 0, length - tailLen);
  89. }
  90. }
  91. else
  92. {
  93. // only one copy is needed if there is no wrap around.
  94. copied = input.CopyTo(_window, _end, length);
  95. }
  96. _end = (_end + copied) & WINDOW_MASK;
  97. _bytesUsed += copied;
  98. return copied;
  99. }
  100. /// <summary>Free space in output window.</summary>
  101. public int FreeBytes => WINDOW_SIZE - _bytesUsed;
  102. /// <summary>Bytes not consumed in output window.</summary>
  103. public int AvailableBytes => _bytesUsed;
  104. /// <summary>Copy the decompressed bytes to output array.</summary>
  105. public int CopyTo(byte[] output, int offset, int length)
  106. {
  107. int copyEnd;
  108. if (length > _bytesUsed)
  109. {
  110. // we can copy all the decompressed bytes out
  111. copyEnd = _end;
  112. length = _bytesUsed;
  113. }
  114. else
  115. {
  116. copyEnd = (_end - _bytesUsed + length) & WINDOW_MASK; // copy length of bytes
  117. }
  118. int copied = length;
  119. int tailLen = length - copyEnd;
  120. if (tailLen > 0)
  121. {
  122. // this means we need to copy two parts separately
  123. // copy tailLen bytes from the end of output window
  124. Array.Copy(_window, WINDOW_SIZE - tailLen,
  125. output, offset, tailLen);
  126. offset += tailLen;
  127. length = copyEnd;
  128. }
  129. Array.Copy(_window, copyEnd - length, output, offset, length);
  130. _bytesUsed -= copied;
  131. Debug.Assert(_bytesUsed >= 0, "check this function and find why we copied more bytes than we have");
  132. return copied;
  133. }
  134. }
  135. }