1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
|
// TITLE("Decompression Engine")
//++
//
// Copyright (c) 1994 Microsoft Corporation
//
// Module Name:
//
// lzntaxp.s
//
// Abstract:
//
// This module implements the lznt1 decompression engine needed
// to support file system decompression.
//
// Author:
//
// John Vert (jvert) 19-Jul-1994
//
// Environment:
//
// Any.
//
// Revision History:
//
//--
#include "ksalpha.h"
SBTTL("Decompress a buffer")
//++
// NTSTATUS
// LZNT1DecompressChunk (
// OUT PUCHAR UncompressedBuffer,
// IN PUCHAR EndOfUncompressedBufferPlus1,
// IN PUCHAR CompressedBuffer,
// IN PUCHAR EndOfCompressedBufferPlus1,
// OUT PULONG FinalUncompressedChunkSize
// )
//
// Routine Description:
//
// This function decodes a stream of compression tokens and places the
// resultant output into the destination buffer. The format of the input
// is described ..\lznt1.c. As the input is decoded, checks are made to
// ensure that no data is read past the end of the compressed input buffer
// and that no data is stored past the end of the output buffer. Violations
// indicate corrupt input and are indicated by a status return.
//
//
// Arguments:
//
// UncompressedBuffer (a0) - pointer to destination of uncompression.
//
// EndOfUncompressedBufferPlus1 (a1) - pointer just beyond the
// output buffer. This is used for consistency checking of the stored
// compressed data.
//
// CompressedBuffer (a2) - pointer to compressed source. This begins
// with a header word followed by a tag byte describing which of the
// following tokens are literals and which are copy groups.
//
// EndOfCompressedBufferPlus1 (a3) - pointer just beyond end of input
// buffer. This is used to terminate the decompression.
//
// FinalUncompressedChunkSize (a4) - pointer to a returned decompressed
// size. This has meaningful data ONLY when LZNT1DecompressChunk returns
// STATUS_SUCCESS
//
// Return Value:
//
// STATUS_SUCCESS is returned only if the decompression consumes thee entire
// input buffer and does not exceed the output buffer.
// STATUS_BAD_COMPRESSION_BUFFER is returned when the output buffer would be
// overflowed.
//--
//
//
// Register usage:
// a0 - current destination pointer
// a1 - end of output buffer
// a2 - current source pointer
// a3 - end of compressed buffer
// a4 - pointer to decompressed size
// a5 - current decompressed size
// v0 - boundary for next format transition
// t0 - count of consecutive copy tokens
// t1 - current flag byte
// t2 - bits of t1 processed
// t3 - temp
// t4 - temp
// t5 - bytes following flag byte
// t6 - temp
// t7 - temp
// t8 - temp
// t9 - temp
// t10 - temp
// t11 - current length mask
// t12 - current displacement shift
//
LEAF_ENTRY(LZNT1DecompressChunk)
bis zero, zero, a5 // initialize decompressed size
ldil t12, 12 // get initial displacement shift
lda t11, -1(zero)
sll t11, 12, t11 // get initial length mask
addq a0, 16, v0 // get displacement boundary
subq a3, 1, a3 // adjust input buffer end
10:
addq a0, 8, t3 // check for at least 8 bytes available output
addq a2, 17, t4 // check for at least 17 bytes available input
cmpule t3, a1, t2 // check for output buffer exceeded
cmpule t4, a3, t3 // check for input buffer exceeded
ldq_u t0, 0(a2) // load flag byte and any subsequent bytes
extbl t0, a2, t1 // extract flag byte
addq a2, 1, a2
beq t3, CopyTailFlag // input buffer exceeded
ldq_u t6, 7(a2) // load subsequent bytes
and a2, 7, t10 // check for qword alignment
extql t0, a2, t3 // extract low part of next 8 bytes
extqh t6, a2, t4 // extract high part
bis t3, t4, t5 // merge
cmoveq t10, t6, t5 // qword aligned, undo merge
beq t2, CopyTailFlag // output buffer exceeded
bne t1, 20f // !=0 deal with copy tokens
//
// This is the special case where the next 8 bytes are literal tokens.
//
addq a5, 8, a5 // increment bytes copied
addq a0, 8, a0 // increment destination pointer
lda a2, 8(a2) // compute pointer to next tag byte
and a0, 7, t4 // check for qword-aligned destination
bne t4, 15f
//
// Destination is quadword aligned, do direct store
//
stq t5, -8(a0)
br zero, 10b // do next tag byte
15:
//
// Destination is not quadword aligned, merge eight bytes into buffer.
//
ldq_u t4, -8(a0) // get low destination
mskql t4, a0, t0 // clear position in destination
insql t5, a0, t2 // get low part in position
bis t0, t2, t4 // merge in new bytes
stq_u t4, -8(a0) // store low part
ldq_u t4, -1(a0) // get high destination
mskqh t4, a0, t0 // clear position in destination
insqh t5, a0, t2 // get high part in position
bis t0, t2, t4 // merge in new bytes
stq_u t4, -1(a0) // store high part
br zero, 10b // do next tag byte
20:
//
// Tag indicates both literal bytes and copy tokens. The approach
// we use here is to loop through the bits counting the consecutive
// literal bytes until we find a copy token.
//
bis zero, zero, t0 // set bit count to zero
ldil t2, 8 // set count of bits to process
25:
blbs t1, CopyToken // go copy the token.
//
// Count the consecutive clear bits.
//
srl t1, 1, t1
addq t0, 1, t0
blbs t1, 30f
srl t1, 1, t1
addq t0, 1, t0
blbs t1, 30f
srl t1, 1, t1
addq t0, 1, t0
blbs t1, 30f
srl t1, 1, t1
addq t0, 1, t0
blbs t1, 30f
srl t1, 1, t1
addq t0, 1, t0
blbs t1, 30f
srl t1, 1, t1
addq t0, 1, t0
blbs t1, 30f
srl t1, 1, t1
addq t0, 1, t0
30:
bis zero, 1, t9 // compute byte mask
sll t9, t0, t3
subq t3, 1, t9
zapnot t5, t9, t4 // get masked bytes to store
and a0, 7, t3 // get byte position of dest
addq t3, t0, t10 // compute ending offset
sll t9, t3, t9 // shift byte mask into position
ldq_u t7, 0(a0) // get low part of dest.
insql t4, t3, t6 // insert source bytes into position
zap t7, t9, t8 // clear dest
bis t8, t6, t7 // merge bytes to store
stq_u t7, 0(a0) // store merged result
//
// Check to see whether the bytes to store extend into the next
// quadword of the destination.
//
cmpult t10, 8, t9
bne t9, 40f // ending offset < 8, next quadword unaffected
insqh t4, t3, t6 // shift source bytes into position
stq_u t6, 8(a0) // store merged results
40:
addq a0, t0, a0 // adjust destination pointer
addq a2, t0, a2 // adjust source pointer
addq a5, t0, a5 // adjust bytes copied
subq t2, t0, t2 // adjust flag bits left
CopyToken:
//
// Get the token word
//
ldq_u t10, 0(a2)
ldq_u t6, 1(a2)
extwl t10, a2, t7
extwh t6, a2, t8
bis t7, t8, t9
//
// Check the displacement and length.
//
50:
cmpult v0, a0, t10
bne t10, UpdateFormat // if nez, max displacement < output
srl t9, t12, t7 // compute offset
andnot t9, t11, t8 // compute length
addq t8, 3, t8
addq t7, 1, t7
//
// Check displacement against number of bytes copied
//
cmpule t7, a5, t10
beq t10, ErrorExit // if eqz, bytes copied <= displacement
//
// Account for end of output buffer and compute ending
// address of copy.
//
addq a0, t8, t9
cmpule t9, a1, t10
cmoveq t10, a1, t9 // if ending address > buffer end, set
// buffer end to ending address
subq a0, t7, t5 // compute copy source
//
// Do the copy.
// t5 - source
// a0 - dest
// t9 - end of destination
//
// If the source is more than eight bytes away from the destination,
// we can copy a quadword at a time. Otherwise, we must copy a byte
// at a time to ensure that fills work correctly.
//
subq t9, a0, t7 // compute number of bytes to copy
addq a5, t7, a5 // adjust bytes copied here, the only
// time this will not be correct is
// in an error condition.
subq a0, t5, t10 // test if source is >= 8 bytes away
cmpult t10, 8, t10 // from destination
bne t10, FillBytes // if so, do byte fill
//
// Write the low part of the first quadword out. This will cause the
// destination to become qword aligned.
//
ldq_u t10, 0(t5) // get low part of source qword
ldq_u t8, 7(t5) // get high part of source qword
extql t10, t5, t7
extqh t8, t5, t3
bis t3, t7, t10 // get aligned qword
ldq_u t7, 0(a0) // get low part of source destination
insql t10, a0, t3
mskql t7, a0, t4 // clear bytes in destination
bis t4, t3, t7 // merge qword into destination
stq_u t7, 0(a0) // store low part of quadword
addq a0, 8, t10 // compute qword-aligned destination
bic t10, 7, t10
subq t10, a0, t8
addq t5, t8, t5 // increment source
bis t10, zero, a0 // increment destination
//
// Recompute number of quadwords to copy now that the destination has
// been qword aligned
//
subq t9, a0, t7
cmovlt t7, t9, a0 // back up destination if we went too far
ble t7, 64f // no bytes remaining
srl t7, 3, t4
and t5, 7, t3 // get alignment of source
ldq_u t10, 0(t5)
bne t3, UnalignedQwordCopy
beq t4, 60f // no qwords remaining
AlignedQwordLoop:
stq t10, 0(a0) // store qword
addq t5, 8, t5 // increment source
addq a0, 8, a0 // increment dest
subq t4, 1, t4 // decrement remaining qword
ldq t10, 0(t5) // get next qword
bne t4, AlignedQwordLoop
cmpult a0, t9, t4
beq t4, 64f // no bytes reamining
//
// Tail bytes are in t10, go ahead and store them.
// We know we will not store beyond the containing qword of
// the end of the buffer
//
60:
stq t10, 0(a0)
bis t9, zero, a0 // increment dest
br zero, 64f
UnalignedQwordCopy:
beq t4, 65f // no qword remaining
UnalignedQwordLoop:
ldq_u t8, 8(t5)
extql t10, t5, t10
extqh t8, t5, t7
bis t7, t10, t10
stq t10, 0(a0)
bis t8, zero, t10
addq t5, 8, t5 // increment source
addq a0, 8, a0 // increment dest
subq t4, 1, t4 // decrement remaining qwords
bne t4, UnalignedQwordLoop
cmpult a0, t9, t4
beq t4, 64f // no bytes remaining
//
// Low word of the tail bytes are in t10
// Get the high part, then go ahead and store them.
// We know we will not store beyond the containing qword
// of the end of the buffer.
//
65:
ldq_u t8, 8(t5) // get high part of tail bytes
extql t10, t5, t7 // extract low part
extqh t8, t5, t4 // extract high part
bis t7, t4, t10 // merge
stq t10, 0(a0) // store result
bis t9, zero, a0 // increment dest.
br zero, 64f
FillBytes:
ldq_u t10, 0(t5)
ldq_u t8, 0(a0)
extbl t10, t5, t7
insbl t7, a0, t10
mskbl t8, a0, t4
bis t10, t4, t7
stq_u t7, 0(a0)
addq a0, 1, a0
addq t5, 1, t5
cmpult a0, t9, t4
bne t4, FillBytes
64:
//
// Token successfully copied.
//
addq a2, 2, a2
subq t2, 1, t2 // decrement remaining bits
srl t1, 1, t1 // shift flag byte
beq t2, 10b // no more bits remaining
addq a0, t2, t3 // check for enough output bytes remaining
cmpule t3, a1, t4
beq t4, CopyTail
addq a2, 14, t3 // check for enough input bytes remaining
cmpule t3, a3, t4
beq t4, CopyTail
addq a2, t2, t3 // point to last byte.
//
// Get remaining bytes
//
bis zero, zero, t0 // set # clear bits back to zero
ldq_u t5, 0(t3)
and a2, 7, t7
beq t7, 65f // source quadword aligned, no shift/merge required
extql t6, a2, t4
extqh t5, a2, t8
bis t4, t8, t5
65:
bne t1, 25b // if any literal tokens remain, repeat
bis zero, 1, t9 // compute byte mask
sll t9, t2, t3
subq t3, 1, t9
zapnot t5, t9, t4 // get masked bytes to store
and a0, 7, t3 // get byte position of dest
addq t3, t2, t10 // compute ending offset
sll t9, t3, t9 // shift byte mask into position
ldq_u t7, 0(a0) // get low part of dest.
insql t4, t3, t6 // insert source bytes into position
zap t7, t9, t8 // clear dest
bis t8, t6, t7 // merge bytes to store
stq_u t7, 0(a0) // store merged result
//
// Check to see whether the bytes to store extend into the next
// quadword of the destination.
//
cmpult t10, 8, t9
bne t9, 70f // ending offset < 8, next quadword unaffected
insqh t4, t3, t6 // insert source bytes into position
stq_u t6, 8(a0) // store merged results
70:
addq a0, t2, a0 // adjust destination pointer
addq a2, t2, a2 // adjust source pointer
addq a5, t2, a5 // adjust bytes copied
br zero, 10b
UpdateFormat:
subq a0, a5, t10 // compute original pointer
subq v0, t10, t7 // compute current max displacement
sll t7, 1, t7 //
addq t7, t10, v0 // compute new max displacemnt
srl t11, 1, t11 // compute new length mask
subq t12, 1, t12 // compute new displacement shift
br zero, 50b // start again.
//
// a0 - the destination
// a1 - the last byte of the destination
// t1 - flag byte
//
CopyTailFlag:
ldil t2, 8 // set count of bits to process
CopyTail:
cmpult a0, a1, t10
beq t10, SuccessExit // finished
cmpule a2, a3, t10
beq t10, SuccessExit // finished
blbc t1, CT15 // skip copy token
cmpeq a2, a3, t10
beq t10, CopyToken // more than one byte left
br zero, ErrorExit // only one byte left, error
CT15:
ldq_u t10, 0(a2)
extbl t10, a2, t5
ldq_u t7, 0(a0)
insbl t5, a0, t6
mskbl t7, a0, t8
bis t6, t8, t7
stq_u t7, 0(a0)
addq a0, 1, a0
addq a2, 1, a2
srl t1, 1, t1
subq t2, 1, t2
addq a5, 1, a5
bne t2, CopyTail
cmpule a2, a3, t10
beq t10, SuccessExit // finished
ldq_u t0, 0(a2) // load flag byte and any subsequent bytes
extbl t0, a2, t1 // extract flag byte
addq a2, 1, a2
br zero, CopyTailFlag
SuccessExit:
bis zero, zero, v0
stl a5, 0(a4)
ret zero, (ra)
ErrorExit:
ldil v0, STATUS_BAD_COMPRESSION_BUFFER
ret zero, (ra)
.end LZNT1DecompressChunk
|