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
|
/*++
Copyright (c) Alex Ionescu. All rights reserved.
Module Name:
dictbuf.c
Abstract:
This module implements the management of the LZMA "history buffer" which is
often called the "dictionary". Routines for writing into the history buffer
as well as for reading back from it are implemented, as well as mechanisms
for repeating previous symbols forward into the dictionary. This forms the
basis for LZMA match distance-length pairs that are found and decompressed.
Note that for simplicity's sake, the dictionary is stored directly in the
output buffer, such that no "flushing" or copying is needed back and forth.
Author:
Alex Ionescu (@aionescu) 15-Apr-2020 - Initial version
Environment:
Windows & Linux, user mode and kernel mode.
--*/
#include "minlzlib.h"
//
// State used for the history buffer (dictionary)
//
typedef struct _DICTIONARY_STATE
{
//
// Buffer, start position, current position, and offset limit in the buffer
//
uint8_t* Buffer;
uint32_t BufferSize;
uint32_t Start;
uint32_t Offset;
uint32_t Limit;
} DICTIONARY_STATE, *PDICTIONARY_STATE;
DICTIONARY_STATE Dictionary;
void
DtInitialize (
uint8_t* HistoryBuffer,
uint32_t Size
)
{
//
// Initialize the buffer and reset the position
//
Dictionary.Buffer = HistoryBuffer;
Dictionary.Offset = 0;
Dictionary.BufferSize = Size;
}
bool
DtSetLimit (
uint32_t Limit
)
{
//
// Make sure that the passed in dictionary limit fits within the size, and
// then set this as the new limit. Save the starting point (current offset)
//
if ((Dictionary.Offset + Limit) > Dictionary.BufferSize)
{
return false;
}
Dictionary.Limit = Dictionary.Offset + Limit;
Dictionary.Start = Dictionary.Offset;
return true;
}
bool
DtIsComplete (
uint32_t* BytesProcessed
)
{
//
// Return bytes processed and if the dictionary has been fully written to
//
*BytesProcessed = Dictionary.Offset - Dictionary.Start;
return (Dictionary.Offset == Dictionary.Limit);
}
bool
DtCanWrite (
uint32_t* Position
)
{
//
// Return our position and make sure it's not beyond the uncompressed size
//
*Position = Dictionary.Offset;
return (Dictionary.Offset < Dictionary.Limit);
}
uint8_t
DtGetSymbol (
uint32_t Distance
)
{
//
// If the dictionary is still empty, just return 0, otherwise, return the
// symbol that is Distance bytes backward.
//
if (Distance > Dictionary.Offset)
{
return 0;
}
return Dictionary.Buffer[Dictionary.Offset - Distance];
}
void
DtPutSymbol (
uint8_t Symbol
)
{
//
// Write the symbol and advance our position
//
Dictionary.Buffer[Dictionary.Offset++] = Symbol;
}
bool
DtRepeatSymbol (
uint32_t Length,
uint32_t Distance
)
{
//
// Make sure we never get asked to write past the end of the dictionary. We
// should also not allow the distance to go beyond the current offset since
// DtGetSymbol will return 0 thinking the dictionary is empty.
//
if (((Length + Dictionary.Offset) > Dictionary.Limit) ||
(Distance > Dictionary.Offset))
{
return false;
}
//
// Now rewrite the stream of past symbols forward into the dictionary.
//
do
{
DtPutSymbol(DtGetSymbol(Distance));
} while (--Length > 0);
return true;
}
|
