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
24typedef 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
33struct _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
57G_DEFINE_TYPE (LZWDecoder, lzw_decoder, G_TYPE_OBJECT)
58
59static void
60add_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
74static gsize
75write_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
108void
109lzw_decoder_class_init (LZWDecoderClass *klass)
110{
111}
112
113void
114lzw_decoder_init (LZWDecoder *self)
115{
116}
117
118LZWDecoder *
119lzw_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
148gsize
149lzw_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

source code of gtk/subprojects/gdk-pixbuf/gdk-pixbuf/lzw.c