ReactOS  0.4.14-dev-115-g4576127
compress.c
Go to the documentation of this file.
1 /*
2  * COPYRIGHT: See COPYING in the top level directory
3  * PROJECT: ReactOS system libraries
4  * PURPOSE: Compression and decompression functions
5  * FILE: lib/rtl/compress.c
6  * PROGRAMER: Eric Kohl
7  Sebastian Lackner
8  Michael Müller
9  */
10 
11 /* INCLUDES *****************************************************************/
12 
13 #include <rtl.h>
14 
15 #define NDEBUG
16 #include <debug.h>
17 
18 /* MACROS *******************************************************************/
19 
20 #define COMPRESSION_FORMAT_MASK 0x00FF
21 #define COMPRESSION_ENGINE_MASK 0xFF00
22 
23 
24 
25 
26 /* FUNCTIONS ****************************************************************/
27 
28 /* Based on Wine Staging */
29 
30 /* decompress a single LZNT1 chunk */
31 static PUCHAR lznt1_decompress_chunk(UCHAR *dst, ULONG dst_size, UCHAR *src, ULONG src_size)
32 {
33  UCHAR *src_cur, *src_end, *dst_cur, *dst_end;
34  ULONG displacement_bits, length_bits;
35  ULONG code_displacement, code_length;
36  WORD flags, code;
37 
38  src_cur = src;
39  src_end = src + src_size;
40  dst_cur = dst;
41  dst_end = dst + dst_size;
42 
43  /* Partial decompression is no error on Windows. */
44  while (src_cur < src_end && dst_cur < dst_end)
45  {
46  /* read flags header */
47  flags = 0x8000 | *src_cur++;
48 
49  /* parse following 8 entities, either uncompressed data or backwards reference */
50  while ((flags & 0xFF00) && src_cur < src_end)
51  {
52  if (flags & 1)
53  {
54  /* backwards reference */
55  if (src_cur + sizeof(WORD) > src_end)
56  return NULL;
57  code = *(WORD *)src_cur;
58  src_cur += sizeof(WORD);
59 
60  /* find length / displacement bits */
61  for (displacement_bits = 12; displacement_bits > 4; displacement_bits--)
62  if ((1 << (displacement_bits - 1)) < dst_cur - dst) break;
63  length_bits = 16 - displacement_bits;
64  code_length = (code & ((1 << length_bits) - 1)) + 3;
65  code_displacement = (code >> length_bits) + 1;
66 
67  /* ensure reference is valid */
68  if (dst_cur < dst + code_displacement)
69  return NULL;
70 
71  /* copy bytes of chunk - we can't use memcpy()
72  * since source and dest can be overlapping */
73  while (code_length--)
74  {
75  if (dst_cur >= dst_end) return dst_cur;
76  *dst_cur = *(dst_cur - code_displacement);
77  dst_cur++;
78  }
79  }
80  else
81  {
82  /* uncompressed data */
83  if (dst_cur >= dst_end) return dst_cur;
84  *dst_cur++ = *src_cur++;
85  }
86  flags >>= 1;
87  }
88 
89  }
90 
91  return dst_cur;
92 }
93 
94 /* decompress data encoded with LZNT1 */
95 static NTSTATUS lznt1_decompress(UCHAR *dst, ULONG dst_size, UCHAR *src, ULONG src_size,
96  ULONG offset, ULONG *final_size, UCHAR *workspace)
97 {
98  UCHAR *src_cur = src, *src_end = src + src_size;
99  UCHAR *dst_cur = dst, *dst_end = dst + dst_size;
100  ULONG chunk_size, block_size;
101  WORD chunk_header;
102  UCHAR *ptr;
103 
104  if (src_cur + sizeof(WORD) > src_end)
106 
107  /* skip over chunks which have a big distance (>= 0x1000) to the destination offset */
108  while (offset >= 0x1000 && src_cur + sizeof(WORD) <= src_end)
109  {
110  /* read chunk header and extract size */
111  chunk_header = *(WORD *)src_cur;
112  src_cur += sizeof(WORD);
113  if (!chunk_header) goto out;
114  chunk_size = (chunk_header & 0xFFF) + 1;
115 
116  /* ensure we have enough buffer to process chunk */
117  if (src_cur + chunk_size > src_end)
119 
120  src_cur += chunk_size;
121  offset -= 0x1000;
122  }
123 
124  /* this chunk is can be included partially */
125  if (offset && src_cur + sizeof(WORD) <= src_end)
126  {
127  /* read chunk header and extract size */
128  chunk_header = *(WORD *)src_cur;
129  src_cur += sizeof(WORD);
130  if (!chunk_header) goto out;
131  chunk_size = (chunk_header & 0xFFF) + 1;
132 
133  /* ensure we have enough buffer to process chunk */
134  if (src_cur + chunk_size > src_end)
136 
137  if (dst_cur >= dst_end)
138  goto out;
139 
140  if (chunk_header & 0x8000)
141  {
142  /* compressed chunk */
143  if (!workspace) return STATUS_ACCESS_VIOLATION;
144  ptr = lznt1_decompress_chunk(workspace, 0x1000, src_cur, chunk_size);
145  if (!ptr) return STATUS_BAD_COMPRESSION_BUFFER;
146  if (ptr - workspace > offset)
147  {
148  block_size = min((ptr - workspace) - offset, dst_end - dst_cur);
149  memcpy(dst_cur, workspace + offset, block_size);
150  dst_cur += block_size;
151  }
152  }
153  else
154  {
155  /* uncompressed chunk */
156  if (chunk_size > offset)
157  {
158  block_size = min(chunk_size - offset, dst_end - dst_cur);
159  memcpy(dst_cur, src_cur + offset, block_size);
160  dst_cur += block_size;
161  }
162  }
163 
164  src_cur += chunk_size;
165  }
166 
167  /* handle remaining chunks */
168  while (src_cur + sizeof(WORD) <= src_end)
169  {
170  /* read chunk header and extract size */
171  chunk_header = *(WORD *)src_cur;
172  src_cur += sizeof(WORD);
173  if (!chunk_header) goto out;
174  chunk_size = (chunk_header & 0xFFF) + 1;
175 
176  if (src_cur + chunk_size > src_end)
178 
179  /* add padding if required */
180  block_size = ((dst_cur - dst) + offset) & 0xFFF;
181  if (block_size)
182  {
183  block_size = 0x1000 - block_size;
184  if (dst_cur + block_size >= dst_end)
185  goto out;
186  memset(dst_cur, 0, block_size);
187  dst_cur += block_size;
188  }
189 
190  if (dst_cur >= dst_end)
191  goto out;
192 
193  if (chunk_header & 0x8000)
194  {
195  /* compressed chunk */
196  dst_cur = lznt1_decompress_chunk(dst_cur, dst_end - dst_cur, src_cur, chunk_size);
197  if (!dst_cur) return STATUS_BAD_COMPRESSION_BUFFER;
198  }
199  else
200  {
201  /* uncompressed chunk */
202  block_size = min(chunk_size, dst_end - dst_cur);
203  memcpy(dst_cur, src_cur, block_size);
204  dst_cur += block_size;
205  }
206 
207  src_cur += chunk_size;
208  }
209 
210 out:
211  if (final_size)
212  *final_size = dst_cur - dst;
213 
214  return STATUS_SUCCESS;
215 
216 }
217 
218 
219 static NTSTATUS
221  ULONG chunk_size, ULONG *final_size, UCHAR *workspace)
222 {
223  UCHAR *src_cur = src, *src_end = src + src_size;
224  UCHAR *dst_cur = dst, *dst_end = dst + dst_size;
226 
227  while (src_cur < src_end)
228  {
229  /* determine size of current chunk */
230  block_size = min(0x1000, src_end - src_cur);
231  if (dst_cur + sizeof(WORD) + block_size > dst_end)
233 
234  /* write (uncompressed) chunk header */
235  *(WORD *)dst_cur = 0x3000 | (block_size - 1);
236  dst_cur += sizeof(WORD);
237 
238  /* write chunk content */
239  memcpy(dst_cur, src_cur, block_size);
240  dst_cur += block_size;
241  src_cur += block_size;
242  }
243 
244  if (final_size)
245  *final_size = dst_cur - dst;
246 
247  return STATUS_SUCCESS;
248 }
249 
250 
251 static NTSTATUS
253  PULONG BufferAndWorkSpaceSize,
254  PULONG FragmentWorkSpaceSize)
255 {
256  if (Engine == COMPRESSION_ENGINE_STANDARD)
257  {
258  *BufferAndWorkSpaceSize = 0x8010;
259  *FragmentWorkSpaceSize = 0x1000;
260  return(STATUS_SUCCESS);
261  }
262  else if (Engine == COMPRESSION_ENGINE_MAXIMUM)
263  {
264  *BufferAndWorkSpaceSize = 0x10;
265  *FragmentWorkSpaceSize = 0x1000;
266  return(STATUS_SUCCESS);
267  }
268 
269  return(STATUS_NOT_SUPPORTED);
270 }
271 
272 
273 /*
274  * @implemented
275  */
277 RtlCompressBuffer(IN USHORT CompressionFormatAndEngine,
278  IN PUCHAR UncompressedBuffer,
282  IN ULONG UncompressedChunkSize,
283  OUT PULONG FinalCompressedSize,
285 {
286  USHORT Format = CompressionFormatAndEngine & COMPRESSION_FORMAT_MASK;
287  /* USHORT Engine = CompressionFormatAndEngine & COMPRESSION_ENGINE_MASK; */
288 
289  if ((Format == COMPRESSION_FORMAT_NONE) ||
291  return(STATUS_INVALID_PARAMETER);
292 
294  return(RtlpCompressBufferLZNT1(UncompressedBuffer,
298  UncompressedChunkSize,
299  FinalCompressedSize,
300  WorkSpace));
301 
303 }
304 
305 
306 /*
307  * @unimplemented
308  */
310 RtlCompressChunks(IN PUCHAR UncompressedBuffer,
317 {
319  return STATUS_NOT_IMPLEMENTED;
320 }
321 
322 /*
323  * @unimplemented
324  */
326 RtlDecompressChunks(OUT PUCHAR UncompressedBuffer,
330  IN PUCHAR CompressedTail,
333 {
335  return STATUS_NOT_IMPLEMENTED;
336 }
337 
338 /*
339  * @implemented
340  */
344  IN ULONG uncompressed_size,
345  IN PUCHAR compressed,
346  IN ULONG compressed_size,
347  IN ULONG offset,
348  OUT PULONG final_size,
349  IN PVOID workspace)
350 {
351  DPRINT("0x%04x, %p, %u, %p, %u, %u, %p, %p :stub\n", format, uncompressed,
352  uncompressed_size, compressed, compressed_size, offset, final_size, workspace);
353 
355  {
357  return lznt1_decompress(uncompressed, uncompressed_size, compressed,
358  compressed_size, offset, final_size, workspace);
359 
363 
364  default:
365  DPRINT1("format %d not implemented\n", format);
367  }
368 }
369 
370 /*
371  * @implemented
372  */
374 RtlDecompressBuffer(IN USHORT CompressionFormat,
375  OUT PUCHAR UncompressedBuffer,
380 {
381  return RtlDecompressFragment(CompressionFormat, UncompressedBuffer, UncompressedBufferSize,
383 }
384 
385 /*
386  * @unimplemented
387  */
389 RtlDescribeChunk(IN USHORT CompressionFormat,
394 {
396  return STATUS_NOT_IMPLEMENTED;
397 }
398 
399 
400 /*
401  * @unimplemented
402  */
404 RtlGetCompressionWorkSpaceSize(IN USHORT CompressionFormatAndEngine,
405  OUT PULONG CompressBufferAndWorkSpaceSize,
406  OUT PULONG CompressFragmentWorkSpaceSize)
407 {
408  USHORT Format = CompressionFormatAndEngine & COMPRESSION_FORMAT_MASK;
409  USHORT Engine = CompressionFormatAndEngine & COMPRESSION_ENGINE_MASK;
410 
411  if ((Format == COMPRESSION_FORMAT_NONE) ||
413  return(STATUS_INVALID_PARAMETER);
414 
416  return(RtlpWorkSpaceSizeLZNT1(Engine,
417  CompressBufferAndWorkSpaceSize,
418  CompressFragmentWorkSpaceSize));
419 
421 }
422 
423 
424 
425 /*
426  * @unimplemented
427  */
429 RtlReserveChunk(IN USHORT CompressionFormat,
434 {
436  return STATUS_NOT_IMPLEMENTED;
437 }
438 
439 /* EOF */
#define STATUS_UNSUPPORTED_COMPRESSION
Definition: ntstatus.h:718
#define COMPRESSION_FORMAT_NONE
#define IN
Definition: typedefs.h:38
NTSTATUS NTAPI RtlDecompressBuffer(IN USHORT CompressionFormat, OUT PUCHAR UncompressedBuffer, IN ULONG UncompressedBufferSize, IN PUCHAR CompressedBuffer, IN ULONG CompressedBufferSize, OUT PULONG FinalUncompressedSize)
Definition: compress.c:374
NTSTATUS NTAPI RtlDescribeChunk(IN USHORT CompressionFormat, IN OUT PUCHAR *CompressedBuffer, IN PUCHAR EndOfCompressedBufferPlus1, OUT PUCHAR *ChunkBuffer, OUT PULONG ChunkSize)
Definition: compress.c:389
#define STATUS_NOT_IMPLEMENTED
Definition: ntstatus.h:225
#define STATUS_INVALID_PARAMETER
Definition: udferr_usr.h:135
static NTSTATUS lznt1_decompress(UCHAR *dst, ULONG dst_size, UCHAR *src, ULONG src_size, ULONG offset, ULONG *final_size, UCHAR *workspace)
Definition: compress.c:95
unsigned char * PUCHAR
Definition: retypes.h:3
static PUCHAR lznt1_decompress_chunk(UCHAR *dst, ULONG dst_size, UCHAR *src, ULONG src_size)
Definition: compress.c:31
long dst_end
Definition: timezone.c:17
LONG NTSTATUS
Definition: precomp.h:26
GLintptr offset
Definition: glext.h:5920
#define COMPRESSION_FORMAT_MASK
Definition: compress.c:20
#define COMPRESSION_ENGINE_MASK
Definition: compress.c:21
static const BYTE uncompressed[]
Definition: misc.c:392
GLint GLint GLsizei GLsizei GLsizei GLint GLenum format
Definition: gl.h:1546
static DWORD block_size(DWORD block)
Definition: jsutils.c:64
#define STATUS_BUFFER_TOO_SMALL
Definition: shellext.h:64
_In_ ULONG _In_ ULONG _Out_ PULONG FinalUncompressedSize
Definition: rtlfuncs.h:3170
NTSTATUS(* NTAPI)(IN PFILE_FULL_EA_INFORMATION EaBuffer, IN ULONG EaLength, OUT PULONG ErrorOffset)
Definition: IoEaTest.cpp:117
_Inout_ PUCHAR _In_ PUCHAR _Out_ PUCHAR _Out_ PULONG ChunkSize
Definition: rtlfuncs.h:2276
_Inout_ PUCHAR * CompressedBuffer
Definition: rtlfuncs.h:2276
static PVOID ptr
Definition: dispmode.c:27
smooth NULL
Definition: ftsmooth.c:416
static NTSTATUS RtlpCompressBufferLZNT1(UCHAR *src, ULONG src_size, UCHAR *dst, ULONG dst_size, ULONG chunk_size, ULONG *final_size, UCHAR *workspace)
Definition: compress.c:220
NTSTATUS NTAPI RtlCompressChunks(IN PUCHAR UncompressedBuffer, IN ULONG UncompressedBufferSize, OUT PUCHAR CompressedBuffer, IN ULONG CompressedBufferSize, IN OUT PCOMPRESSED_DATA_INFO CompressedDataInfo, IN ULONG CompressedDataInfoLength, IN PVOID WorkSpace)
Definition: compress.c:310
void DPRINT(...)
Definition: polytest.cpp:61
#define STATUS_BAD_COMPRESSION_BUFFER
Definition: ntstatus.h:696
_In_ PLARGE_INTEGER _In_ ULONG _In_ ULONG _Out_ PVOID _Out_ PMDL _Out_ PIO_STATUS_BLOCK _Out_ struct _COMPRESSED_DATA_INFO _In_ ULONG CompressedDataInfoLength
Definition: iotypes.h:1615
NTSTATUS NTAPI RtlGetCompressionWorkSpaceSize(IN USHORT CompressionFormatAndEngine, OUT PULONG CompressBufferAndWorkSpaceSize, OUT PULONG CompressFragmentWorkSpaceSize)
Definition: compress.c:404
#define COMPRESSION_FORMAT_LZNT1
unsigned short WORD
Definition: ntddk_ex.h:93
static FILE * out
Definition: regtests2xml.c:44
GLbitfield flags
Definition: glext.h:7161
#define COMPRESSION_ENGINE_STANDARD
unsigned char UCHAR
Definition: xmlstorage.h:181
NTSTATUS NTAPI RtlDecompressFragment(IN USHORT format, OUT PUCHAR uncompressed, IN ULONG uncompressed_size, IN PUCHAR compressed, IN ULONG compressed_size, IN ULONG offset, OUT PULONG final_size, IN PVOID workspace)
Definition: compress.c:342
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
GLenum src
Definition: glext.h:6340
#define COMPRESSION_ENGINE_MAXIMUM
int code
Definition: i386-dis.c:3591
#define STATUS_ACCESS_VIOLATION
Definition: ntstatus.h:228
unsigned short USHORT
Definition: pedump.c:61
NTSTATUS NTAPI RtlReserveChunk(IN USHORT CompressionFormat, IN OUT PUCHAR *CompressedBuffer, IN PUCHAR EndOfCompressedBufferPlus1, OUT PUCHAR *ChunkBuffer, IN ULONG ChunkSize)
Definition: compress.c:429
_In_ ULONG UncompressedBufferSize
Definition: rtlfuncs.h:3168
GLenum GLenum dst
Definition: glext.h:6340
unsigned int * PULONG
Definition: retypes.h:1
#define min(a, b)
Definition: monoChain.cc:55
#define DPRINT1
Definition: precomp.h:8
NTSTATUS NTAPI RtlCompressBuffer(IN USHORT CompressionFormatAndEngine, IN PUCHAR UncompressedBuffer, IN ULONG UncompressedBufferSize, OUT PUCHAR CompressedBuffer, IN ULONG CompressedBufferSize, IN ULONG UncompressedChunkSize, OUT PULONG FinalCompressedSize, IN PVOID WorkSpace)
Definition: compress.c:277
_In_ ULONG _In_ ULONG _In_ ULONG CompressedTailSize
Definition: rtlfuncs.h:2302
static NTSTATUS RtlpWorkSpaceSizeLZNT1(USHORT Engine, PULONG BufferAndWorkSpaceSize, PULONG FragmentWorkSpaceSize)
Definition: compress.c:252
_In_ ULONG _In_ ULONG _Out_ PULONG _In_ PVOID WorkSpace
Definition: rtlfuncs.h:2267
_In_ ULONG _In_ ULONG CompressedBufferSize
Definition: rtlfuncs.h:3170
_In_ PLARGE_INTEGER _In_ ULONG _In_ ULONG _Out_ PVOID _Out_ PMDL _Out_ PIO_STATUS_BLOCK _Out_ struct _COMPRESSED_DATA_INFO * CompressedDataInfo
Definition: iotypes.h:1615
#define OUT
Definition: typedefs.h:39
#define STATUS_NOT_SUPPORTED
Definition: ntstatus.h:409
unsigned int ULONG
Definition: retypes.h:1
#define UNIMPLEMENTED
Definition: debug.h:114
return STATUS_SUCCESS
Definition: btrfs.c:2966
#define memset(x, y, z)
Definition: compat.h:39
NTSTATUS NTAPI RtlDecompressChunks(OUT PUCHAR UncompressedBuffer, IN ULONG UncompressedBufferSize, IN PUCHAR CompressedBuffer, IN ULONG CompressedBufferSize, IN PUCHAR CompressedTail, IN ULONG CompressedTailSize, IN PCOMPRESSED_DATA_INFO CompressedDataInfo)
Definition: compress.c:326
_Inout_ PUCHAR _In_ PUCHAR EndOfCompressedBufferPlus1
Definition: rtlfuncs.h:2276
_Inout_ PUCHAR _In_ PUCHAR _Out_ PUCHAR * ChunkBuffer
Definition: rtlfuncs.h:2276
#define COMPRESSION_FORMAT_DEFAULT