1 /*
2 Copyright (C) 2016-2021, Dirk Krause
3 SPDX-License-Identifier: BSD-3-Clause
4 */
5
6 /*
7 WARNING: This file was generated by the dkct program (see
8 http://dktools.sourceforge.net/ for details).
9 Changes you make here will be lost if dkct is run again!
10 You should modify the original source and run dkct on it.
11 Original source: dk4lzwe.ctr
12 */
13
14 /** @file dk4lzwe.c The dk4lzwe module.
15 */
16
17
18 #include "dk4conf.h"
19 #include <libdk4c/dk4lzwe.h>
20 #include <libdk4base/dk4mem.h>
21 #include <libdk4c/dk4edstm.h>
22
23 #if DK4_HAVE_ASSERT_H
24 #ifndef ASSERT_H_INCLUDED
25 #include <assert.h>
26 #define ASSERT_H_INCLUDED 1
27 #endif
28 #endif
29
30
31
32
33
34
35 /** Code to clear tables.
36 */
37 #define LZW_CLT ((unsigned short)256U)
38
39
40
41 /** Code to indicate end of data.
42 */
43 #define LZW_EOD ((unsigned short)257U)
44
45
46
47 /** First user-made state.
48 */
49 #define LZW_START ((unsigned short)258U)
50
51
52
53 /** Bitmask values.
54 */
55 static const unsigned short bit_values[] = {
56 0x0001U, 0x0002U, 0x0004U, 0x0008U, 0x0010U, 0x0020U, 0x0040U, 0x0080U,
57 0x0100U, 0x0200U, 0x0400U, 0x0800U, 0x1000U, 0x2000U, 0x4000U, 0x8000U
58 };
59
60
61
62 /** Write bit sequence to output buffer.
63 @param lzwptr LZW compression structure.
64 @param val Bit sequence to write.
65 @param erp Error report, may be NULL.
66 @return 1 on success, 0 on error.
67
68 Error codes:
69 - DK4_E_BUFFER_TOO_SMALL<br>
70 if the output buffer is full before finishing,
71 - DK4_E_INVALID_ARGUMENTS<br>
72 should not happen.
73 */
74 static
75 int
dk4lzwe_shipout(dk4_lzwe_t * lzwptr,unsigned short val,dk4_er_t * erp)76 dk4lzwe_shipout(
77 dk4_lzwe_t *lzwptr,
78 unsigned short val,
79 dk4_er_t *erp
80 )
81 {
82 int back = 1;
83 int res;
84 unsigned short i;
85 unsigned char uc;
86
87
88 #if DK4_USE_ASSERT
89 assert(NULL != lzwptr);
90 #endif
91 i = lzwptr->bits;
92 while (0 < i--) {
93 res = dk4bit_shift_add(
94 &(lzwptr->bs),
95 ((((unsigned short)0) != (val & bit_values[i])) ? (1) : (0)),
96 NULL
97 );
98 switch (res) {
99 case DK4_EDSTM_ERROR : {
100 back = 0;
101 dk4error_set_simple_error_code(erp, DK4_E_BUG);
102 } break;
103 case DK4_EDSTM_FINISHED : {
104 uc = dk4bit_shift_output(&(lzwptr->bs), NULL);
105 if (8 > lzwptr->obu) {
106 lzwptr->ob[lzwptr->obu] = uc;
107 lzwptr->obu += 1;
108 }
109 else {
110 back = 0;
111 dk4error_set_simple_error_code(erp, DK4_E_BUFFER_TOO_SMALL);
112 }
113 } break;
114 }
115 }
116
117 return back;
118 }
119
120
121
122 /** Clear all table entries.
123 @param lzwptr Encoder to clean up.
124 */
125 static
126 void
dk4lzwe_clear_table_entries(dk4_lzwe_t * lzwptr)127 dk4lzwe_clear_table_entries(
128 dk4_lzwe_t *lzwptr
129 )
130 {
131 dk4_lzw_cell_t *cptr;
132 size_t i;
133
134 #if DK4_USE_ASSERT
135 assert(NULL != lzwptr);
136 #endif
137 cptr = lzwptr->p_tbl;
138 for (i = 0; i < LZW_TABLE_SIZE; i++) {
139 cptr[i].os = (unsigned short)0U;
140 cptr[i].ns = (unsigned short)0U;
141 cptr[i].in = (unsigned char)0x00;
142 }
143
144 }
145
146
147
148 int
dk4lzwe_init(dk4_lzwe_t * lzwptr,dk4_er_t * erp)149 dk4lzwe_init(
150 dk4_lzwe_t *lzwptr,
151 dk4_er_t *erp
152 )
153 {
154 int back = 0;
155
156 #if DK4_USE_ASSERT
157 assert(NULL != lzwptr);
158 #endif
159 if (NULL != lzwptr) {
160 /*
161 Default values for al components
162 */
163 dk4mem_reset(lzwptr, sizeof(dk4_lzwe_t), NULL);
164 lzwptr->p_tbl = NULL;
165 lzwptr->obu = 0;
166 lzwptr->mret = 0;
167 lzwptr->hst = 0;
168 lzwptr->bits = 9;
169 lzwptr->cs = 0U;
170 lzwptr->ns = LZW_START;
171 dk4bit_shift_init(&(lzwptr->bs), NULL);
172 /*
173 Allocate memory for state transition table
174 */
175 lzwptr->p_tbl = dk4mem_new(dk4_lzw_cell_t,LZW_TABLE_SIZE,erp);
176 /*
177 On success ship out initial clear table marker
178 */
179 if (NULL != lzwptr->p_tbl) {
180 dk4lzwe_clear_table_entries(lzwptr);
181 back = dk4lzwe_shipout(lzwptr, LZW_CLT, erp);
182 }
183 #if TRACE_DEBUG
184 else {
185 }
186 #endif
187 }
188 else {
189 dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS);
190 }
191
192 return back;
193 }
194
195
196
197 static
198 int
dk4lzwe_i_add(dk4_lzwe_t * lzwptr,unsigned char uc,dk4_er_t * erp)199 dk4lzwe_i_add(
200 dk4_lzwe_t *lzwptr,
201 unsigned char uc,
202 dk4_er_t *erp
203 )
204 {
205 int back = DK4_EDSTM_ERROR;
206 #if TRACE_DEBUG
207 int passno = 0;
208 #endif
209 int cc;
210 int found;
211 unsigned short ind;
212 unsigned short offs;
213
214 #if DK4_USE_ASSERT
215 assert(NULL != lzwptr);
216 #endif
217 if (0 != lzwptr->hst) {
218 /*
219 Already input available, so we have to check the table
220 for a matching rule
221 */
222 #if 0
223 ind = (lzwptr->cs)
224 ^ ((((unsigned short)uc) << 4) & ((unsigned short)0x0FF0U));
225 #endif
226 ind = (unsigned short)(
227 ((unsigned)(lzwptr->cs)) ^ (((unsigned)uc << 4) & 0x0FF0U)
228 );
229 #if 0
230 ind = ind % LZW_TABLE_SIZE;
231 #endif
232 #if 0
233 offs = ((((unsigned short)0U) != ind) ? (LZW_TABLE_SIZE - ind) : (1));
234 #endif
235 offs = (unsigned short)(
236 (0U != ind)
237 ? ((unsigned)(LZW_TABLE_SIZE) - ind)
238 : (1U)
239 );
240 cc = 1;
241 found = 0;
242 do {
243 if ((unsigned short)0U != (lzwptr->p_tbl)[ind].ns) {
244 if (lzwptr->cs == (lzwptr->p_tbl)[ind].os) {
245 if (uc == (lzwptr->p_tbl)[ind].in) {
246 found = 1;
247 }
248 }
249 if (0 != found) {
250 cc = 0;
251 }
252 else {
253 ind = (unsigned short)(ind + offs);
254 ind = (ind % LZW_TABLE_SIZE);
255 }
256 }
257 else {
258 cc = 0;
259 }
260 #if TRACE_DEBUG
261 passno++;
262 #endif
263 } while (0 < cc);
264 #if TRACE_DEBUG
265
266 #endif
267 if (0 != found) {
268 /*
269 A matching rule was found, so we just change state.
270 */
271 lzwptr->cs = (lzwptr->p_tbl)[ind].ns;
272 back = DK4_EDSTM_ACCEPT;
273 }
274 else {
275 /* No matching rule was found.
276 We check whether or not we can add further entries to
277 the table.
278 */
279 if ((unsigned short)4094U <= lzwptr->ns) {
280 /*
281 Table is full, so we ship out the current state,
282 clean we table and keep the input as new current state.
283 */
284 if (0 != dk4lzwe_shipout(lzwptr, lzwptr->cs, erp)) {
285 if (0 != dk4lzwe_shipout(lzwptr, LZW_CLT, erp)) {
286 back = DK4_EDSTM_FINISHED;
287 lzwptr->mret = 1;
288 }
289 }
290 lzwptr->cs = (((unsigned short)0x00FFU) & ((unsigned short)uc));
291 lzwptr->bits = 9;
292 lzwptr->ns = LZW_START;
293 dk4lzwe_clear_table_entries(lzwptr);
294 }
295 else {
296 /* There is still room in the table.
297 Ship out current state, create new rule in the
298 table and keep input as new current state.
299 */
300 if (0 != dk4lzwe_shipout(lzwptr, lzwptr->cs, erp)) {
301 back = DK4_EDSTM_FINISHED;
302 lzwptr->mret = 1;
303 }
304 (lzwptr->p_tbl)[ind].os = lzwptr->cs;
305 (lzwptr->p_tbl)[ind].ns = lzwptr->ns;
306 (lzwptr->p_tbl)[ind].in = uc;
307
308 /*
309 Increase number of bits if necessary.
310 */
311 switch ( (int)(lzwptr->ns) ) {
312 case 511 : {
313 lzwptr->bits = 10;
314 } break;
315 case 1023 : {
316 lzwptr->bits = 11;
317 } break;
318 case 2047 : {
319 lzwptr->bits = 12;
320 } break;
321 }
322 lzwptr->ns = (unsigned short)(lzwptr->ns + 1U);
323 lzwptr->cs = (((unsigned short)0x00FFU) & ((unsigned short)uc));
324 }
325 }
326 }
327 else {
328 /* No current state yet (no input yet).
329 Just store the input as current state.
330 */
331 lzwptr->cs = (((unsigned short)0x00FFU) & ((unsigned short)uc));
332 lzwptr->hst = 1;
333 back = DK4_EDSTM_ACCEPT;
334 }
335
336 return back;
337 }
338
339
340
341 int
dk4lzwe_add(dk4_lzwe_t * lzwptr,unsigned char uc,dk4_er_t * erp)342 dk4lzwe_add(
343 dk4_lzwe_t *lzwptr,
344 unsigned char uc,
345 dk4_er_t *erp
346 )
347 {
348 int back = DK4_EDSTM_ERROR;
349
350 #if DK4_USE_ASSERT
351 assert(NULL != lzwptr);
352 #endif
353 if (NULL != lzwptr) {
354 if (NULL != lzwptr->p_tbl) {
355 if (0 == lzwptr->mret) {
356 back = dk4lzwe_i_add(lzwptr, uc, erp);
357 }
358 else {
359 dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS);
360 }
361 }
362 else {
363 dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS);
364 }
365 }
366 else {
367 dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS);
368 }
369
370 return back;
371 }
372
373
374
375 int
dk4lzwe_finish(dk4_lzwe_t * lzwptr,dk4_er_t * erp)376 dk4lzwe_finish(
377 dk4_lzwe_t *lzwptr,
378 dk4_er_t *erp
379 )
380 {
381 int back = DK4_EDSTM_ERROR;
382 unsigned char uc;
383
384 #if DK4_USE_ASSERT
385 assert(NULL != lzwptr);
386 #endif
387 if (NULL != lzwptr) {
388 if (NULL != lzwptr->p_tbl) {
389 if (0 == lzwptr->mret) {
390 back = DK4_EDSTM_ACCEPT;
391 /*
392 Ship out current state, if any.
393 */
394 if (0 != lzwptr->hst) {
395 if (0 == dk4lzwe_shipout(lzwptr, lzwptr->cs, erp)) {
396 back = DK4_EDSTM_ERROR;
397 }
398 }
399 /* Ship out end of data marker.
400 */
401 if (0 == dk4lzwe_shipout(lzwptr, LZW_EOD, erp)) {
402 back = DK4_EDSTM_ERROR;
403 }
404 /* Apply final byte from bit shifter to output.
405 */
406 switch ( dk4bit_shift_finish(&(lzwptr->bs), erp)) {
407 case DK4_EDSTM_ERROR : {
408 back = DK4_EDSTM_ERROR;
409 } break;
410 case DK4_EDSTM_FINISHED : {
411 uc = dk4bit_shift_output(&(lzwptr->bs), NULL);
412 if (8 > lzwptr->obu) {
413 lzwptr->ob[lzwptr->obu] = uc;
414 lzwptr->obu += 1;
415 }
416 else {
417 back = DK4_EDSTM_ERROR;
418 dk4error_set_simple_error_code(
419 erp, DK4_E_BUFFER_TOO_SMALL
420 );
421 }
422 } break;
423 }
424 /* Check whether the caller must retrieve final output.
425 */
426 if ((DK4_EDSTM_ACCEPT == back) && (0 < lzwptr->obu)) {
427 back = DK4_EDSTM_FINISHED;
428 lzwptr->mret = 1;
429 }
430 }
431 else {
432 dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS);
433 }
434 dk4mem_free(lzwptr->p_tbl);
435 lzwptr->p_tbl = NULL;
436 }
437 else {
438 dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS);
439 }
440 }
441 else {
442 dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS);
443 }
444
445 return back;
446 }
447
448
449
450 int
dk4lzwe_output(const unsigned char ** dptr,size_t * szptr,dk4_lzwe_t * lzwptr,dk4_er_t * erp)451 dk4lzwe_output(
452 const unsigned char **dptr,
453 size_t *szptr,
454 dk4_lzwe_t *lzwptr,
455 dk4_er_t *erp
456 )
457 {
458 int back = 0;
459
460 #if DK4_USE_ASSERT
461 assert(NULL != dptr);
462 assert(NULL != szptr);
463 assert(NULL != lzwptr);
464 #endif
465 if ((NULL != dptr) && (NULL != szptr) && (NULL != lzwptr)) {
466 /*
467 All arguments ok, do normal output operation.
468 */
469 *dptr = &(lzwptr->ob[0]);
470 *szptr = lzwptr->obu;
471 back = ((0 < lzwptr->obu) ? (1) : (0));
472 lzwptr->mret = 0;
473 lzwptr->obu = 0;
474 }
475 else {
476 /*
477 Argument error, indicate no data available.
478 */
479 if (NULL != dptr) {
480 *dptr = NULL;
481 }
482 if (NULL != szptr) {
483 *szptr = 0;
484 }
485 dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS);
486 }
487
488 return back;
489 }
490
491
492 /* vim: set ai sw=4 ts=4 : */
493
494