1 | /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 8 -*- */ |
2 | /* |
3 | * Copyright (C) 2018 Canonical Ltd. |
4 | * |
5 | * This library is free software; you can redistribute it and/or |
6 | * modify it under the terms of the GNU Lesser General Public |
7 | * License as published by the Free Software Foundation; either |
8 | * version 2 of the License, or (at your option) any later version. |
9 | * |
10 | * This library is distributed in the hope that it will be useful, |
11 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
13 | * Lesser General Public License for more details. |
14 | * |
15 | * You should have received a copy of the GNU Lesser General Public |
16 | * License along with this library; if not, see <http://www.gnu.org/licenses/>. |
17 | */ |
18 | |
19 | #include "lzw.h" |
20 | |
21 | /* Maximum number of codes */ |
22 | #define MAX_CODES (1 << LZW_CODE_MAX) |
23 | |
24 | typedef struct |
25 | { |
26 | /* Last index this code represents */ |
27 | guint8 index; |
28 | |
29 | /* Codeword of previous index or the EOI code if doesn't extend */ |
30 | guint16 extends; |
31 | } LZWCode; |
32 | |
33 | struct _LZWDecoder |
34 | { |
35 | GObject parent_instance; |
36 | |
37 | /* Initial code size */ |
38 | int min_code_size; |
39 | |
40 | /* Current code size */ |
41 | int code_size; |
42 | |
43 | /* Code table and special codes */ |
44 | int clear_code; |
45 | int eoi_code; |
46 | LZWCode code_table[MAX_CODES]; |
47 | int code_table_size; |
48 | |
49 | /* Current code being assembled */ |
50 | int code; |
51 | int code_bits; |
52 | |
53 | /* Last code processed */ |
54 | int last_code; |
55 | }; |
56 | |
57 | G_DEFINE_TYPE (LZWDecoder, lzw_decoder, G_TYPE_OBJECT) |
58 | |
59 | static void |
60 | add_code (LZWDecoder *self, |
61 | int code) |
62 | { |
63 | /* Find the first index of the given code */ |
64 | int c = code; |
65 | while (self->code_table[c].extends != self->eoi_code) |
66 | c = self->code_table[c].extends; |
67 | |
68 | /* Make a new code that extends the previous code */ |
69 | self->code_table[self->code_table_size].index = self->code_table[c].index; |
70 | self->code_table[self->code_table_size].extends = self->last_code; |
71 | self->code_table_size++; |
72 | } |
73 | |
74 | static gsize |
75 | write_indexes (LZWDecoder *self, |
76 | guint8 *output, |
77 | gsize output_length) |
78 | { |
79 | int c; |
80 | gsize index_count = 1, offset; |
81 | |
82 | /* Ignore invalid codeword */ |
83 | if (self->code >= self->code_table_size) |
84 | return 0; |
85 | |
86 | /* Work out how many indexes this code represents... */ |
87 | c = self->code; |
88 | while (self->code_table[c].extends != self->eoi_code) { |
89 | c = self->code_table[c].extends; |
90 | index_count++; |
91 | } |
92 | |
93 | /* ...then write the indexes in backwards */ |
94 | c = self->code; |
95 | offset = index_count - 1; |
96 | while (TRUE) { |
97 | if (offset < output_length) |
98 | output[offset] = self->code_table[c].index; |
99 | |
100 | if (self->code_table[c].extends == self->eoi_code) |
101 | return index_count; |
102 | |
103 | c = self->code_table[c].extends; |
104 | offset--; |
105 | } |
106 | } |
107 | |
108 | void |
109 | lzw_decoder_class_init (LZWDecoderClass *klass) |
110 | { |
111 | } |
112 | |
113 | void |
114 | lzw_decoder_init (LZWDecoder *self) |
115 | { |
116 | } |
117 | |
118 | LZWDecoder * |
119 | lzw_decoder_new (guint8 code_size) |
120 | { |
121 | LZWDecoder *self; |
122 | int i; |
123 | |
124 | g_return_val_if_fail (code_size <= LZW_CODE_MAX, NULL); |
125 | |
126 | self = g_object_new (object_type: lzw_decoder_get_type (), NULL); |
127 | |
128 | self->min_code_size = code_size; |
129 | self->code_size = code_size; |
130 | |
131 | /* Add special clear and end of information codes */ |
132 | self->clear_code = 1 << (code_size - 1); |
133 | self->eoi_code = self->clear_code + 1; |
134 | |
135 | for (i = 0; i <= self->eoi_code; i++) { |
136 | self->code_table[i].index = i; |
137 | self->code_table[i].extends = self->eoi_code; |
138 | self->code_table_size++; |
139 | } |
140 | |
141 | /* Start with an empty codeword following an implicit clear codeword */ |
142 | self->code = 0; |
143 | self->last_code = self->clear_code; |
144 | |
145 | return self; |
146 | } |
147 | |
148 | gsize |
149 | lzw_decoder_feed (LZWDecoder *self, |
150 | guint8 *input, |
151 | gsize input_length, |
152 | guint8 *output, |
153 | gsize output_length) |
154 | { |
155 | gsize i, n_written = 0; |
156 | |
157 | g_return_val_if_fail (LZW_IS_DECODER (self), 0); |
158 | |
159 | /* Ignore data after "end of information" codeword */ |
160 | if (self->last_code == self->eoi_code) |
161 | return 0; |
162 | |
163 | /* Processes each octet of input */ |
164 | for (i = 0; i < input_length; i++) { |
165 | guint8 d = input[i]; |
166 | int n_available; |
167 | |
168 | /* Process the bits of the octet into codewords */ |
169 | for (n_available = 8; n_available > 0; ) { |
170 | int n_bits, new_bits; |
171 | |
172 | /* Extract up the the required number of bits from the octet */ |
173 | n_bits = MIN (self->code_size - self->code_bits, n_available); |
174 | new_bits = d & ((1 << n_bits) - 1); |
175 | d = d >> n_bits; |
176 | n_available -= n_bits; |
177 | |
178 | /* Add the new bits to the code until we have a full codeword */ |
179 | self->code = new_bits << self->code_bits | self->code; |
180 | self->code_bits += n_bits; |
181 | if (self->code_bits < self->code_size) |
182 | continue; |
183 | |
184 | /* Stop on "end of information" codeword */ |
185 | if (self->code == self->eoi_code) { |
186 | self->last_code = self->code; |
187 | return n_written; |
188 | } |
189 | |
190 | /* Reset the code table on "clear" */ |
191 | if (self->code == self->clear_code) { |
192 | self->code_table_size = self->eoi_code + 1; |
193 | self->code_size = self->min_code_size; |
194 | } else { |
195 | /* Add a new code word if space. |
196 | * The first code after a clear is skipped */ |
197 | if (self->last_code != self->clear_code && self->code_table_size < MAX_CODES) { |
198 | if (self->code < self->code_table_size) |
199 | add_code (self, code: self->code); |
200 | else |
201 | add_code (self, code: self->last_code); |
202 | |
203 | /* When table is full increase code size */ |
204 | if (self->code_table_size == (1 << self->code_size) && self->code_size < LZW_CODE_MAX) |
205 | self->code_size++; |
206 | } |
207 | |
208 | /* Invalid code received - just stop here */ |
209 | if (self->code >= self->code_table_size) { |
210 | self->last_code = self->eoi_code; |
211 | return output_length; |
212 | } |
213 | |
214 | /* Convert codeword into indexes */ |
215 | n_written += write_indexes (self, output: output + n_written, output_length: output_length - n_written); |
216 | } |
217 | |
218 | self->last_code = self->code; |
219 | self->code = 0; |
220 | self->code_bits = 0; |
221 | |
222 | /* Out of space */ |
223 | if (n_written >= output_length) |
224 | return output_length; |
225 | } |
226 | } |
227 | |
228 | return n_written; |
229 | } |
230 | |