%% options copyright owner = Dirk Krause copyright year = 2016-xxxx license = bsd %% header /** @file dk4lzwe.h LZW encoder to produce PS level 2 output. - The unit length (input data length) is 8 bits. - Code 256 is used for table cleanup, 257 is the end of data marker. - EarlyChange is in use: the number of bits per code is increased after creating table entries for codes 511, 1023 and 2047. - Table entries are created for codes up to 4093. Instead of generating an entry for 4094, the table is cleared. */ #ifndef DK4ERROR_H_INCLUDED #include #endif #ifndef DK4BITSH_H_INCLUDED #include #endif /** Table size. The table must be large enough to keep 4096 entries. Adding 25 percent size significantly decreases the number of lookups. A prime number is required to ensure traversal of the entire table if necessary. */ enum { LZW_TABLE_SIZE = 5147 /**< Size of LZW compression table. */ }; /** One table entry for LZW compression. */ typedef struct { unsigned short os; /**< Current (old) state or code. */ unsigned short ns; /**< New state after applying input. */ unsigned char in; /**< Input byte. */ } dk4_lzw_cell_t; /** LZW encoder structure. */ typedef struct { unsigned char ob[8]; /**< Output buffer. */ dk4_bit_shift_t bs; /**< Bit shifter. */ dk4_lzw_cell_t *p_tbl; /**< Pointer to dynamically allocated table. */ size_t obu; /**< Used bytes in output buffer. */ int mret; /**< Flag: Must retrieve output data. */ int hst; /**< Flag: Have internal state. */ unsigned short bits; /**< Number of bits to use for output. */ unsigned short cs; /**< Current state. */ unsigned short ns; /**< Next state for new table entry. */ } dk4_lzwe_t; #ifdef __cplusplus extern "C" { #endif /** Initialize LZW encoder, allocate memory for resources. @param lzwptr Encoder to initialize. @param erp Error report, may be NULL. @return 1 on success, 0 on error. Error codes: - DK4_E_INVALID_ARGUMENTS
if lzwptr is NULL, - DK4_E_MATH_OVERFLOW
on numeric overflow when calculating the product of elsize and nelem, - DK4_E_MEMORY_ALLOCATION_FAILED
with mem.elsize and mem.nelem set if there is not enough memory available, - DK4_E_BUG
if the dk4bit_shift_add() call indicates an error (should not happen as we provide a valid address to the function), - DK4_E_BUFFER_TOO_SMALL
if the output buffer is already full. Typically this means that output was not retrieved as expected by the library. */ int dk4lzwe_init( dk4_lzwe_t *lzwptr, dk4_er_t *erp ); /** Add one byte to the encoder. @param lzwptr Encoder to use. @param uc Byte to add. @param erp Error report, may be NULL. @return Operation result, one from: - DK4_EDSTM_ACCEPT
if the input byte was successfully stored in the internal data structures without completing a run. No further action necessary. - DK4_EDSTM_FINISHED
if output was created. Use dk4lzwe_output() to obtain the output data. - DK4_EDSTM_ERROR
if an error occured. */ int dk4lzwe_add( dk4_lzwe_t *lzwptr, unsigned char uc, dk4_er_t *erp ); /** Finish encoded data stream, flush internal state and bits from the bit shifter to output buffer and release dynamic memory. @param lzwptr Encoder to use. @param erp Error report, may be NULL. @return Operation result, one from: - DK4_EDSTM_ACCEPT
if the input byte was successfully stored in the internal data structures without completing a run. No further action necessary. - DK4_EDSTM_FINISHED
if output was created. Use dk4lzwe_output() to obtain the output data. - DK4_EDSTM_ERROR
if an error occured. Error codes: - DK4_E_INVALID_ARGUMENTS
if lzwptr is NULL or lzwptr->s_tbl or lzwptr->i_tbl is NULL, - DK4_E_BUG
if the dk4bit_shift_add() call indicates an error (should not happen as we provide a valid address to the function), - DK4_E_BUFFER_TOO_SMALL
if the output buffer is already full. Typically this means that output was not retrieved as expected by the library. */ int dk4lzwe_finish( dk4_lzwe_t *lzwptr, dk4_er_t *erp ); /** Retrieve output from encoder. @param dptr Address of result pointer. @param szptr Address of result size variable. @param lzwptr Encoder to use. @param erp Error report, may be NULL. @return 1 if data available, 0 otherwise. */ int dk4lzwe_output( const unsigned char **dptr, size_t *szptr, dk4_lzwe_t *lzwptr, dk4_er_t *erp ); #ifdef __cplusplus } #endif /* vim: set ai sw=4 ts=4 : */ %% module #include "dk4lzwe.h" #include "dk4mem.h" #include "dk4edstm.h" $!trace-include /** Code to clear tables. */ #define LZW_CLT ((unsigned short)256U) /** Code to indicate end of data. */ #define LZW_EOD ((unsigned short)257U) /** First user-made state. */ #define LZW_START ((unsigned short)258U) /** Bitmask values. */ static const unsigned short bit_values[] = { 0x0001U, 0x0002U, 0x0004U, 0x0008U, 0x0010U, 0x0020U, 0x0040U, 0x0080U, 0x0100U, 0x0200U, 0x0400U, 0x0800U, 0x1000U, 0x2000U, 0x4000U, 0x8000U }; /** Write bit sequence to output buffer. @param lzwptr LZW compression structure. @param val Bit sequence to write. @param erp Error report, may be NULL. @return 1 on success, 0 on error. Error codes: - DK4_E_BUFFER_TOO_SMALL
if the output buffer is full before finishing, - DK4_E_INVALID_ARGUMENTS
should not happen. */ static int dk4lzwe_shipout( dk4_lzwe_t *lzwptr, unsigned short val, dk4_er_t *erp ) { int back = 1; int res; unsigned short i; unsigned char uc; $? "+ dk4lzwe_shipout %u/%u", (unsigned)val, (unsigned)(lzwptr->bits) i = lzwptr->bits; while (0 < i--) { res = dk4bit_shift_add( &(lzwptr->bs), ((((unsigned short)0) != (val & bit_values[i])) ? (1) : (0)), NULL ); switch (res) { case DK4_EDSTM_ERROR : { $? "! dk4bit_shift_add" back = 0; dk4error_set_simple_error_code(erp, DK4_E_BUG); } break; case DK4_EDSTM_FINISHED : { $? ". byte completed" uc = dk4bit_shift_output(&(lzwptr->bs), NULL); if (8 > lzwptr->obu) { $? ". saved to buffer" lzwptr->ob[lzwptr->obu] = uc; lzwptr->obu += 1; } else { $? "! buffer full" back = 0; dk4error_set_simple_error_code(erp, DK4_E_BUFFER_TOO_SMALL); } } break; } } $? "- dk4lzwe_shipout %d", back return back; } /** Clear all table entries. @param lzwptr Encoder to clean up. */ static void dk4lzwe_clear_table_entries( dk4_lzwe_t *lzwptr ) { dk4_lzw_cell_t *cptr; size_t i; $? "+ dk4lzwe_clear_table_entries" cptr = lzwptr->p_tbl; for (i = 0; i < LZW_TABLE_SIZE; i++) { cptr[i].os = (unsigned short)0U; cptr[i].ns = (unsigned short)0U; cptr[i].in = (unsigned char)0x00; } $? "- dk4lzwe_clear_table_entries" } int dk4lzwe_init( dk4_lzwe_t *lzwptr, dk4_er_t *erp ) { int back = 0; $? "+ dk4lzwe_init %d", TR_IPTR(lzwptr) if (NULL != lzwptr) { $? ". lzwptr" /* Default values for al components */ dk4mem_reset(lzwptr, sizeof(dk4_lzwe_t), NULL); lzwptr->p_tbl = NULL; lzwptr->obu = 0; lzwptr->mret = 0; lzwptr->hst = 0; lzwptr->bits = 9; lzwptr->cs = 0U; lzwptr->ns = LZW_START; dk4bit_shift_init(&(lzwptr->bs), NULL); /* Allocate memory for state transition table */ lzwptr->p_tbl = dk4mem_new(dk4_lzw_cell_t,LZW_TABLE_SIZE,erp); /* On success ship out initial clear table marker */ if (NULL != lzwptr->p_tbl) { $? ". p_tbl" dk4lzwe_clear_table_entries(lzwptr); back = dk4lzwe_shipout(lzwptr, LZW_CLT, erp); } #if TRACE_DEBUG else { $? "! p_tbl" } #endif } else { $? "! lzwptr" dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } $? "- dk4lzwe_init %d", back return back; } static int dk4lzwe_i_add( dk4_lzwe_t *lzwptr, unsigned char uc, dk4_er_t *erp ) { int back = DK4_EDSTM_ERROR; #if TRACE_DEBUG int passno = 0; #endif int cc; int found; unsigned short ind; unsigned short offs; $? "+ dk4lzwe_i_add" if (0 != lzwptr->hst) { $? ". already input" /* Already input available, so we have to check the table for a matching rule */ ind = (lzwptr->cs) ^ ((((unsigned short)uc) << 4) & ((unsigned short)0x0FF0U)); #if 0 ind = ind % LZW_TABLE_SIZE; #endif offs = ((((unsigned short)0U) != ind) ? (LZW_TABLE_SIZE - ind) : (1)); cc = 1; found = 0; $? ". start loop" do { $? ". new pass" if ((unsigned short)0U != (lzwptr->p_tbl)[ind].ns) { $? ". rule" if (lzwptr->cs == (lzwptr->p_tbl)[ind].os) { if (uc == (lzwptr->p_tbl)[ind].in) { found = 1; $? ". matching rule" } } if (0 != found) { cc = 0; } else { $? ". next rule" ind += offs; ind = (ind % LZW_TABLE_SIZE); } } else { $? ". empty rule" cc = 0; } #if TRACE_DEBUG passno++; #endif } while (0 < cc); $? ". loop finished" #if TRACE_DEBUG $? ". passes=%d", passno #endif if (0 != found) { $? ". rule found" /* A matching rule was found, so we just change state. */ lzwptr->cs = (lzwptr->p_tbl)[ind].ns; back = DK4_EDSTM_ACCEPT; } else { $? ". no rule found" /* No matching rule was found. We check whether or not we can add further entries to the table. */ if ((unsigned short)4094U <= lzwptr->ns) { $? ". table full, clean" /* Table is full, so we ship out the current state, clean we table and keep the input as new current state. */ if (0 != dk4lzwe_shipout(lzwptr, lzwptr->cs, erp)) { if (0 != dk4lzwe_shipout(lzwptr, LZW_CLT, erp)) { back = DK4_EDSTM_FINISHED; $? ". shipout ok" lzwptr->mret = 1; } } lzwptr->cs = (((unsigned short)0x00FFU) & ((unsigned short)uc)); lzwptr->bits = 9; lzwptr->ns = LZW_START; dk4lzwe_clear_table_entries(lzwptr); } else { $? ". add rule" /* There is still room in the table. Ship out current state, create new rule in the table and keep input as new current state. */ if (0 != dk4lzwe_shipout(lzwptr, lzwptr->cs, erp)) { back = DK4_EDSTM_FINISHED; $? ". shipout ok" lzwptr->mret = 1; } (lzwptr->p_tbl)[ind].os = lzwptr->cs; (lzwptr->p_tbl)[ind].ns = lzwptr->ns; (lzwptr->p_tbl)[ind].in = uc; $? ". rule %u, %u => %u", (unsigned)((lzwptr->p_tbl)[ind].os), (unsigned)((lzwptr->p_tbl)[ind].in), (unsigned)((lzwptr->p_tbl)[ind].ns) /* Increase number of bits if necessary. */ switch ( (int)(lzwptr->ns) ) { case 511 : { $? ". bits=10" lzwptr->bits = 10; } break; case 1023 : { lzwptr->bits = 11; $? ". bits=11" } break; case 2047 : { lzwptr->bits = 12; $? ". bits=12" } break; } lzwptr->ns += 1U; lzwptr->cs = (((unsigned short)0x00FFU) & ((unsigned short)uc)); } } } else { $? ". no input yet" /* No current state yet (no input yet). Just store the input as current state. */ lzwptr->cs = (((unsigned short)0x00FFU) & ((unsigned short)uc)); lzwptr->hst = 1; back = DK4_EDSTM_ACCEPT; } $? "- dk4lzwe_i_add %d", back return back; } int dk4lzwe_add( dk4_lzwe_t *lzwptr, unsigned char uc, dk4_er_t *erp ) { int back = DK4_EDSTM_ERROR; $? "+ dk4lzwe_add" if (NULL != lzwptr) { if (NULL != lzwptr->p_tbl) { if (0 == lzwptr->mret) { back = dk4lzwe_i_add(lzwptr, uc, erp); } else { dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } } else { dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } } else { dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } $? "- dk4lzwe_add %d", back return back; } int dk4lzwe_finish( dk4_lzwe_t *lzwptr, dk4_er_t *erp ) { int back = DK4_EDSTM_ERROR; unsigned char uc; $? "+ dk4lzwe_finish" if (NULL != lzwptr) { if (NULL != lzwptr->p_tbl) { if (0 == lzwptr->mret) { back = DK4_EDSTM_ACCEPT; /* Ship out current state, if any. */ if (0 != lzwptr->hst) { $? ". have input" if (0 == dk4lzwe_shipout(lzwptr, lzwptr->cs, erp)) { back = DK4_EDSTM_ERROR; $? "! shipout" } } /* Ship out end of data marker. */ if (0 == dk4lzwe_shipout(lzwptr, LZW_EOD, erp)) { back = DK4_EDSTM_ERROR; $? "! shipout" } /* Apply final byte from bit shifter to output. */ switch ( dk4bit_shift_finish(&(lzwptr->bs), erp)) { case DK4_EDSTM_ERROR : { back = DK4_EDSTM_ERROR; $? "! bug" } break; case DK4_EDSTM_FINISHED : { uc = dk4bit_shift_output(&(lzwptr->bs), NULL); if (8 > lzwptr->obu) { $? ". shipout" lzwptr->ob[lzwptr->obu] = uc; lzwptr->obu += 1; } else { $? "! shipout" back = DK4_EDSTM_ERROR; dk4error_set_simple_error_code( erp, DK4_E_BUFFER_TOO_SMALL ); } } break; } /* Check whether the caller must retrieve final output. */ if ((DK4_EDSTM_ACCEPT == back) && (0 < lzwptr->obu)) { back = DK4_EDSTM_FINISHED; $? ". output available" lzwptr->mret = 1; } } else { dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } dk4mem_free(lzwptr->p_tbl); lzwptr->p_tbl = NULL; } else { dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } } else { dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } $? "- dk4lzwe_finish %d", back return back; } int dk4lzwe_output( const unsigned char **dptr, size_t *szptr, dk4_lzwe_t *lzwptr, dk4_er_t *erp ) { int back = 0; $? "+ dk4lzwe_output" if ((NULL != dptr) && (NULL != szptr) && (NULL != lzwptr)) { /* All arguments ok, do normal output operation. */ *dptr = &(lzwptr->ob[0]); *szptr = lzwptr->obu; back = ((0 < lzwptr->obu) ? (1) : (0)); lzwptr->mret = 0; $? ". args" lzwptr->obu = 0; } else { $? "! args" /* Argument error, indicate no data available. */ if (NULL != dptr) { *dptr = NULL; } if (NULL != szptr) { *szptr = 0; } dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } $? "- dk4lzwe_output %d", back return back; } /* vim: set ai sw=4 ts=4 : */