ReactOS 0.4.15-dev-8109-gd7be748
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 */
31static 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;
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 */
95static 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);
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
210out:
211 if (final_size)
212 *final_size = dst_cur - dst;
213
214 return STATUS_SUCCESS;
215
216}
217
218
219static 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
251static 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 */
277RtlCompressBuffer(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
292
294 return(RtlpCompressBufferLZNT1(UncompressedBuffer,
298 UncompressedChunkSize,
299 FinalCompressedSize,
300 WorkSpace));
301
303}
304
305
306/*
307 * @unimplemented
308 */
310RtlCompressChunks(IN PUCHAR UncompressedBuffer,
317{
320}
321
322/*
323 * @unimplemented
324 */
326RtlDecompressChunks(OUT PUCHAR UncompressedBuffer,
330 IN PUCHAR CompressedTail,
333{
336}
337
338/*
339 * @implemented
340 */
344 IN ULONG uncompressed_size,
345 IN PUCHAR compressed,
346 IN ULONG compressed_size,
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 */
374RtlDecompressBuffer(IN USHORT CompressionFormat,
375 OUT PUCHAR UncompressedBuffer,
380{
381 return RtlDecompressFragment(CompressionFormat, UncompressedBuffer, UncompressedBufferSize,
383}
384
385/*
386 * @unimplemented
387 */
389RtlDescribeChunk(IN USHORT CompressionFormat,
394{
397}
398
399
400/*
401 * @unimplemented
402 */
404RtlGetCompressionWorkSpaceSize(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
414
416 return(RtlpWorkSpaceSizeLZNT1(Engine,
417 CompressBufferAndWorkSpaceSize,
418 CompressFragmentWorkSpaceSize));
419
421}
422
423
424
425/*
426 * @unimplemented
427 */
429RtlReserveChunk(IN USHORT CompressionFormat,
434{
437}
438
439/* EOF */
LONG NTSTATUS
Definition: precomp.h:26
#define DPRINT1
Definition: precomp.h:8
#define UNIMPLEMENTED
Definition: debug.h:118
#define NULL
Definition: types.h:112
unsigned short WORD
Definition: ntddk_ex.h:93
GLint GLint GLsizei GLsizei GLsizei GLint GLenum format
Definition: gl.h:1546
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340
GLbitfield flags
Definition: glext.h:7161
GLintptr offset
Definition: glext.h:5920
static DWORD block_size(DWORD block)
Definition: jsutils.c:66
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
static PVOID ptr
Definition: dispmode.c:27
static const BYTE uncompressed[]
Definition: misc.c:392
#define min(a, b)
Definition: monoChain.cc:55
_In_ ULONG _In_ ULONG CompressedBufferSize
Definition: rtlfuncs.h:3282
_In_ ULONG _In_ ULONG _Out_ PULONG FinalUncompressedSize
Definition: rtlfuncs.h:3284
_In_ ULONG UncompressedBufferSize
Definition: rtlfuncs.h:3280
#define COMPRESSION_FORMAT_DEFAULT
#define COMPRESSION_ENGINE_STANDARD
#define COMPRESSION_FORMAT_NONE
#define COMPRESSION_ENGINE_MAXIMUM
#define COMPRESSION_FORMAT_LZNT1
#define STATUS_UNSUPPORTED_COMPRESSION
Definition: ntstatus.h:732
#define STATUS_BAD_COMPRESSION_BUFFER
Definition: ntstatus.h:710
#define STATUS_NOT_SUPPORTED
Definition: ntstatus.h:423
#define STATUS_ACCESS_VIOLATION
Definition: ntstatus.h:242
#define STATUS_NOT_IMPLEMENTED
Definition: ntstatus.h:239
unsigned short USHORT
Definition: pedump.c:61
static FILE * out
Definition: regtests2xml.c:44
long dst_end
Definition: timezone.c:17
#define memset(x, y, z)
Definition: compat.h:39
#define COMPRESSION_FORMAT_MASK
Definition: compress.c:20
NTSTATUS NTAPI RtlGetCompressionWorkSpaceSize(IN USHORT CompressionFormatAndEngine, OUT PULONG CompressBufferAndWorkSpaceSize, OUT PULONG CompressFragmentWorkSpaceSize)
Definition: compress.c:404
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 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 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
static PUCHAR lznt1_decompress_chunk(UCHAR *dst, ULONG dst_size, UCHAR *src, ULONG src_size)
Definition: compress.c:31
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
NTSTATUS NTAPI RtlDescribeChunk(IN USHORT CompressionFormat, IN OUT PUCHAR *CompressedBuffer, IN PUCHAR EndOfCompressedBufferPlus1, OUT PUCHAR *ChunkBuffer, OUT PULONG ChunkSize)
Definition: compress.c:389
NTSTATUS NTAPI RtlReserveChunk(IN USHORT CompressionFormat, IN OUT PUCHAR *CompressedBuffer, IN PUCHAR EndOfCompressedBufferPlus1, OUT PUCHAR *ChunkBuffer, IN ULONG ChunkSize)
Definition: compress.c:429
#define COMPRESSION_ENGINE_MASK
Definition: compress.c:21
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
static NTSTATUS RtlpWorkSpaceSizeLZNT1(USHORT Engine, PULONG BufferAndWorkSpaceSize, PULONG FragmentWorkSpaceSize)
Definition: compress.c:252
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
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
#define STATUS_SUCCESS
Definition: shellext.h:65
#define STATUS_BUFFER_TOO_SMALL
Definition: shellext.h:69
#define DPRINT
Definition: sndvol32.h:73
Definition: inflate.c:139
uint32_t * PULONG
Definition: typedefs.h:59
#define NTAPI
Definition: typedefs.h:36
#define IN
Definition: typedefs.h:39
unsigned char * PUCHAR
Definition: typedefs.h:53
uint32_t ULONG
Definition: typedefs.h:59
#define OUT
Definition: typedefs.h:40
#define STATUS_INVALID_PARAMETER
Definition: udferr_usr.h:135
_In_ PLARGE_INTEGER _In_ ULONG _In_ ULONG _Out_ PVOID _Out_ PMDL _Out_ PIO_STATUS_BLOCK _Out_ struct _COMPRESSED_DATA_INFO * CompressedDataInfo
Definition: iotypes.h:1658
_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:1659
_In_ ULONG _In_ ULONG _In_ ULONG CompressedTailSize
Definition: rtlfuncs.h:2300
_Inout_ PUCHAR * CompressedBuffer
Definition: rtlfuncs.h:2274
_Inout_ PUCHAR _In_ PUCHAR _Out_ PUCHAR _Out_ PULONG ChunkSize
Definition: rtlfuncs.h:2277
_In_ ULONG _In_ ULONG _Out_ PULONG _In_ PVOID WorkSpace
Definition: rtlfuncs.h:2266
_Inout_ PUCHAR _In_ PUCHAR EndOfCompressedBufferPlus1
Definition: rtlfuncs.h:2275
_Inout_ PUCHAR _In_ PUCHAR _Out_ PUCHAR * ChunkBuffer
Definition: rtlfuncs.h:2276
unsigned char UCHAR
Definition: xmlstorage.h:181