%% options copyright owner = Dirk Krause copyright year = 2015-xxxx license = bsd %% header /** @file dk4rle.h Run length encoder as described in the PS and PDF specifications. Use the dk4rle_init() function to initialize the encoder first. Add binary data byte by byte, use dk4rle_add(). If this function returns DK4_EDSTM_ACCEPT, the byte was successfully stored in the encoder, no further action is necessary. If the function returns DK4_EDSTM_FINISHED, either a run or a sequence of literal bytes was completed; use dk4rle_output() to retrieve the output data. After passing all bytes to the encoder there is probably data in the encoder not yet retrieved. Use the dk4rle_finish() function to check. If the function returns DK4_EDSTM_FINISHED, use dk4rle_output() to retrieve the final output data. */ #include "dk4error.h" /** Run-length encoder. */ typedef struct { unsigned char ob[144]; /**< Buffer for both input and output. */ unsigned char *ib; /**< Pointer to ob[1], input buffer. */ size_t oused; /**< Output buffer size. */ size_t iused; /**< Number of input bytes available. */ size_t ao_si; /**< Index to save bytes from after output. */ size_t ao_ss; /**< Size of buffer part to save after out. */ size_t ao_iu; /**< Number of input bytes after output. */ int ao_st; /**< New state after output. */ int st; /**< Current state. */ int lwo; /**< Flag: Last operation was output. */ int weod; /**< Flag: Write EOD marker at end. */ } dk4_rl_enc_t; #ifdef __cplusplus extern "C" { #endif /** Initialize encoder before using it. @param enc Encoder to initialize. @param weod Flag: Write EOD marker at end of data. @param erp Error report, may be NULL. Error codes: - DK4_E_INVALID_ARGUMENTS if enc is NULL. */ void dk4rle_init(dk4_rl_enc_t *enc, int weod, dk4_er_t *erp); /** Add a single byte to the encoder. @param enc Encoder. @param ibyte Input byte to process. @param erp Error report, may be NULL. @return Action to take, 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 a run was completed. Use dk4rle_output() to obtain the output data. - DK4_EDSTM_ERROR
if an error occured. Error codes: - DK4_E_INVALID_ARGUMENTS if enc is NULL. */ int dk4rle_add(dk4_rl_enc_t *enc, unsigned char ibyte, dk4_er_t *erp); /** Finish data stream, process final data still stored in the encoder. @param enc Encoder. @param erp Error report, may be NULL. @return Action to take, 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 a run was completed. Use dk4rle_output() to obtain the output data. - DK4_EDSTM_ERROR
if an error occured. Error codes: - DK4_E_INVALID_ARGUMENTS if enc is NULL. */ int dk4rle_finish(dk4_rl_enc_t *enc, dk4_er_t *erp); /** Retrieve encoder output. @param dptr Address of pointer to set to output bytes, should be initialized to NULL. @param szptr Address of size variable for buffer length, should be initialized to 0. @param enc Encoder. @param erp Error report, may be NULL. @return 1 if there is data available, 0 otherwise. Error codes: - DK4_E_INVALID_ARGUMENTS if enc is NULL. */ int dk4rle_output( const unsigned char **dptr, size_t *szptr, dk4_rl_enc_t *enc, dk4_er_t *erp ); #ifdef __cplusplus } #endif %% module #include "dk4rle.h" #include "dk4edstm.h" #include "dk4mem.h" #include "dk4memcpl.h" $!trace-include /** Run length encoder state. */ enum { /** No run detected yet. */ RLE_ENC_STATE_NO_RUN = 0, /** Currently in a run. */ RLE_ENC_STATE_RUN }; /** Calculate byte for a run length. @param sz Length of the run. @return Byte value to indicate length. */ static unsigned char dk4rle_run_length_byte(size_t sz) { return ((unsigned char)(257 - sz)); } /** Calculate byte for a literal length. @param sz Length of literal data. @return Byte value to indicate the length. */ static unsigned char dk4rle_literal_length_byte(size_t sz) { return ((unsigned char)(sz - 1)); } void dk4rle_init(dk4_rl_enc_t *enc, int weod, dk4_er_t *erp) { if (NULL != enc) { enc->ib = &(enc->ob[1]); enc->oused = 0; enc->iused = 0; enc->ao_si = 0; enc->ao_ss = 0; enc->ao_iu = 0; enc->ao_st = RLE_ENC_STATE_NO_RUN; enc->st = RLE_ENC_STATE_NO_RUN; enc->lwo = 0; enc->weod = ((0 != weod) ? 1 : 0); } else { dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } } static void dk4rle_process_lwo(dk4_rl_enc_t *enc) { if (0 < enc->ao_ss) { dk4mem_cpy_to_left( enc->ib, &((enc->ib)[enc->ao_si]), enc->ao_ss, NULL ); } enc->iused = enc->ao_iu; enc->st = enc->ao_st; enc->lwo = 0; } int dk4rle_add(dk4_rl_enc_t *enc, unsigned char ibyte, dk4_er_t *erp) { int back = DK4_EDSTM_ERROR; int cr = 0; /* Flag: Change to run */ $? "+ dk4rle_add %02x", (unsigned)ibyte if (NULL != enc) { if (0 != enc->lwo) { dk4rle_process_lwo(enc); } $? ". index = %u", (unsigned)(enc->iused) back = DK4_EDSTM_ACCEPT; (enc->ib)[enc->iused] = ibyte; enc->iused += 1; switch (enc->st) { case RLE_ENC_STATE_RUN : { /* In a run. */ if ((enc->ib)[enc->iused - 1] != (enc->ib)[enc->iused - 2]) { $? ". end of run" /* End of run, change to normal mode. */ enc->ob[0] = dk4rle_run_length_byte(enc->iused - 1); enc->oused = 2; back = DK4_EDSTM_FINISHED; enc->ao_si = enc->iused - 1; enc->ao_ss = 1; enc->ao_iu = 1; enc->ao_st = RLE_ENC_STATE_NO_RUN; } else { /* No end of run, continue. */ if (128 <= enc->iused) { $? ". run at limit" /* Full 128 byte run, output. */ enc->ob[0] = dk4rle_run_length_byte(128); enc->oused = 2; back = DK4_EDSTM_FINISHED; enc->ao_si = 0; enc->ao_ss = 0; enc->ao_iu = 0; enc->ao_st = RLE_ENC_STATE_NO_RUN; } } } break; default : { /* Not in a run. */ if (4 <= enc->iused) { if (enc->ib[enc->iused - 1] == enc->ib[enc->iused - 2]) { if (enc->ib[enc->iused - 1] == enc->ib[enc->iused - 3]) { if (enc->ib[enc->iused - 1] == enc->ib[enc->iused - 4]) { cr = 1; $? ". change to run" } } } } if (1 == cr) { $? ". start run" if (4 < enc->iused) { enc->ob[0] = dk4rle_literal_length_byte(enc->iused - 4); enc->oused = (enc->iused - 3); back = DK4_EDSTM_FINISHED; enc->ao_si = enc->iused - 4; enc->ao_ss = 4; enc->ao_iu = 4; enc->ao_st = RLE_ENC_STATE_RUN; } else { enc->st = RLE_ENC_STATE_RUN; } } else { if (128 <= enc->iused) { if ((enc->ib)[127] == (enc->ib)[126]) { if ((enc->ib)[127] == (enc->ib)[125]) { $? ". save last 3" enc->ob[0] = dk4rle_literal_length_byte(125); enc->oused = 126; back = DK4_EDSTM_FINISHED; enc->ao_si = 125; enc->ao_ss = 3; enc->ao_iu = 3; enc->ao_st = RLE_ENC_STATE_NO_RUN; } else { $? ". limit reached, save last 2" enc->ob[0] = dk4rle_literal_length_byte(126); enc->oused = 127; back = DK4_EDSTM_FINISHED; enc->ao_si = 126; enc->ao_ss = 2; enc->ao_iu = 2; enc->ao_st = RLE_ENC_STATE_NO_RUN; } } else { $? ". limit reached, output all" enc->ob[0] = dk4rle_literal_length_byte(128); enc->oused = 129; back = DK4_EDSTM_FINISHED; enc->ao_si = 0; enc->ao_ss = 0; enc->ao_iu = 0; enc->ao_st = RLE_ENC_STATE_NO_RUN; } } } } break; } if (DK4_EDSTM_FINISHED == back) { enc->lwo = 1; $? ". finished" } } else { dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } $? "- dk4rle_add %d", back return back; } int dk4rle_finish(dk4_rl_enc_t *enc, dk4_er_t *erp) { int back = DK4_EDSTM_ERROR; $? "+ dk4rle_finish" if (NULL != enc) { if (0 != enc->lwo) { dk4rle_process_lwo(enc); } back = DK4_EDSTM_ACCEPT; if (0 < enc->iused) { $? ". input available" switch (enc->st) { case RLE_ENC_STATE_RUN : { $? ". final run" enc->ob[0] = dk4rle_run_length_byte(enc->iused); enc->oused = 2; back = DK4_EDSTM_FINISHED; enc->ao_si = 0; enc->ao_ss = 0; enc->ao_iu = 0; enc->ao_st = RLE_ENC_STATE_NO_RUN; if (0 != enc->weod) { $? ". add eod" enc->ob[2] = (unsigned char)128; enc->oused = 3; } } break; default : { $? ". final literal bytes" enc->ob[0] = dk4rle_literal_length_byte(enc->iused); enc->oused = enc->iused + 1; back = DK4_EDSTM_FINISHED; enc->ao_si = 0; enc->ao_ss = 0; enc->ao_iu = 0; enc->ao_st = RLE_ENC_STATE_NO_RUN; if (0 != enc->weod) { $? ". add eod" enc->ob[enc->iused] = (unsigned char)128; enc->oused += 1; } } break; } } else { if (0 != enc->weod) { $? ". write eod" enc->ob[0] = (unsigned char)128; enc->oused = 1; back = DK4_EDSTM_FINISHED; enc->ao_si = 0; enc->ao_ss = 0; enc->ao_iu = 0; enc->ao_st = RLE_ENC_STATE_NO_RUN; } } if (DK4_EDSTM_FINISHED == back) { enc->lwo = 1; } } else { dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } $? "- dk4rle_finish %d", back return back; } int dk4rle_output( const unsigned char **dptr, size_t *szptr, dk4_rl_enc_t *enc, dk4_er_t *erp ) { int back = 0; if ((NULL != enc) && (NULL != dptr) && (NULL != szptr)) { if (0 < enc->oused) { *dptr = &(enc->ob[0]); *szptr = enc->oused; back = 1; } else { *dptr = NULL; *szptr = 0; } } else { dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } return back; } /* Below is the first working code for the module. This code worked perfectly fine, but for performance reasons I wanted to avoid the memory copy operations from input buffer to output buffer. If there is any problem with the current code, we have the chance to go back and test with the original code. */ #if 0 /* ---------- Header ---------- */ #include "dk4error.h" /** Run length encoder. */ typedef struct { unsigned char ob[144]; /**< Output buffer. */ unsigned char ib[128]; /**< Input buffer. */ size_t iused; /**< Number of bytes in ib. */ size_t oused; /**< Number of bytes in ob. */ int st; /**< Current state. */ int weod; /**< Flag: Write EOD marker at end. */ } dk4_rl_enc_t; #ifdef __cplusplus extern "C" { #endif /** Initialize encoder before using it. @param enc Encoder to initialize. @param weod Flag: Write EOD marker at end of data. @param erp Error report, may be NULL. Error codes: - DK4_E_INVALID_ARGUMENTS if enc is NULL. */ void dk4rle_init(dk4_rl_enc_t *enc, int weod, dk4_er_t *erp); /** Add a single byte to the encoder. @param enc Encoder. @param ibyte Input byte to process. @param erp Error report, may be NULL. @return Action to take, 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 a run was completed. Use dk4rle_output() to obtain the output data. - DK4_EDSTM_ERROR
if an error occured. Error codes: - DK4_E_INVALID_ARGUMENTS if enc is NULL. */ int dk4rle_add(dk4_rl_enc_t *enc, unsigned char ibyte, dk4_er_t *erp); /** Finish data stream, process final data still stored in the encoder. @param enc Encoder. @param erp Error report, may be NULL. @return Action to take, 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 a run was completed. Use dk4rle_output() to obtain the output data. - DK4_EDSTM_ERROR
if an error occured. Error codes: - DK4_E_INVALID_ARGUMENTS if enc is NULL. */ int dk4rle_finish(dk4_rl_enc_t *enc, dk4_er_t *erp); /** Retrieve encoder output. @param dptr Address of pointer to set to output bytes, should be initialized to NULL. @param szptr Address of size variable for buffer length, should be initialized to 0. @param enc Encoder. @param erp Error report, may be NULL. @return 1 if there is data available, 0 otherwise. Error codes: - DK4_E_INVALID_ARGUMENTS if enc is NULL. */ int dk4rle_output( const unsigned char **dptr, size_t *szptr, dk4_rl_enc_t *enc, dk4_er_t *erp ); #ifdef __cplusplus } #endif /* ---------------------------- */ /* ---------- Module ---------- */ #include "dk4rle.h" #include "dk4edstm.h" #include "dk4mem.h" #include "dk4memcpl.h" $!trace-include /** Run length encoder state. */ enum { /** No run detected yet. */ RLE_ENC_STATE_NO_RUN = 0, /** Currently in a run. */ RLE_ENC_STATE_RUN }; void dk4rle_init(dk4_rl_enc_t *enc, int weod, dk4_er_t *erp) { $? "+ dk4rle_init" if (NULL != enc) { DK4_MEMRES(enc, sizeof(dk4_rl_enc_t)); enc->st = RLE_ENC_STATE_NO_RUN; enc->iused = 0; enc->oused = 0; enc->weod = ((0 != weod) ? 1 : 0); } else { dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } $? "- dk4rle_init" } /** Calculate byte for a run length. @param sz Length of the run. @return Byte value to indicate length. */ static unsigned char dk4rle_run_length_byte(size_t sz) { return ((unsigned char)(257 - sz)); } /** Calculate byte for a literal length. @param sz Length of literal data. @return Byte value to indicate the length. */ static unsigned char dk4rle_literal_length_byte(size_t sz) { return ((unsigned char)(sz - 1)); } int dk4rle_add(dk4_rl_enc_t *enc, unsigned char ibyte, dk4_er_t *erp) { int back = DK4_EDSTM_ERROR; int cr = 0; /* Flag: Change run */ $? "+ dk4rle_add" if (NULL != enc) { $? ". enc" $? ". iused = %u", (unsigned)(enc->iused) back = DK4_EDSTM_ACCEPT; $? ". back" enc->ib[enc->iused] = ibyte; $? ". ib[used]" enc->iused += 1; $? ". iused += 1" switch (enc->st) { case RLE_ENC_STATE_RUN : { $? ". in run" if (enc->ib[enc->iused - 1] != enc->ib[enc->iused - 2]) { /* Copy data to output buffer. */ enc->ob[1] = enc->ib[enc->iused - 2]; /* Set run-length byte. */ enc->ob[0] = dk4rle_run_length_byte(enc->iused - 1); /* Set total byte size. */ enc->oused = 2; /* Keep input byte. */ enc->ib[0] = enc->ib[enc->iused - 1]; /* Number of input bytes is 1 now. */ enc->iused = 1; /* Output ready. */ back = DK4_EDSTM_FINISHED; /* No longer in a run. */ enc->st = RLE_ENC_STATE_NO_RUN; } else { if (128 <= enc->iused) { /* Copy data to output buffer. */ enc->ob[1] = enc->ib[0]; /* Set run-length byte. */ enc->ob[0] = dk4rle_run_length_byte(128); /* Set total byte size. */ enc->oused = 2; /* No input bytes available. */ enc->iused = 0; /* Output ready. */ back = DK4_EDSTM_FINISHED; /* No longer in a run. */ enc->st = RLE_ENC_STATE_NO_RUN; } } } break; default : { $? ". not in a run" if (4 <= enc->iused) { $? ". 4" if (enc->ib[enc->iused - 1] == enc->ib[enc->iused - 2]) { $? ". 2" if (enc->ib[enc->iused - 1] == enc->ib[enc->iused - 3]) { $? ". 3" if (enc->ib[enc->iused - 1] == enc->ib[enc->iused - 4]) { $? ". 4" cr = 1; } } } if (1 == cr) { $? ". start of run found" /* Start of run. */ if (4 < enc->iused) { /* Output the literal data before run. */ /* Copy data to output buffer. */ DK4_MEMCPY( &(enc->ob[1]), &(enc->ib[0]), (enc->iused - 4)); /* Set run-length byte. */ enc->ob[0] = dk4rle_literal_length_byte(enc->iused - 4); /* Set total byte size. */ enc->oused = enc->iused - 3; /* Keep last 4 bytes. */ dk4mem_cpy_to_left( &(enc->ib[0]), &(enc->ib[enc->iused - 4]), 4, NULL ); /* Number of used input bytes is 4. */ enc->iused = 4; back = DK4_EDSTM_FINISHED; } enc->st = RLE_ENC_STATE_RUN; } else { $? ". no start of run found" if (128 <= enc->iused) { if (enc->ib[enc->iused - 1] == enc->ib[enc->iused - 2]) { if (enc->ib[enc->iused - 1] == enc->ib[enc->iused - 3]) { /* Keep final 3 bytes, potentially start of run. */ /* Copy data to output buffer. */ DK4_MEMCPY( &(enc->ob[1]), &(enc->ib[0]), 125); /* Set run-length byte. */ enc->ob[0] = dk4rle_literal_length_byte(128 - 3); /* Set total byte size. */ enc->oused = 126; /* Keep last 3 bytes. */ dk4mem_cpy_to_left( &(enc->ib[0]), &(enc->ib[125]), 3, NULL ); /* Number of used bytes is 2. */ enc->iused = 3; } else { /* Keep final 2 bytes, potentially start of run. */ /* Copy data. */ DK4_MEMCPY( &(enc->ob[1]), &(enc->ib[0]), 126 ); /* Set run-length byte. */ enc->ob[0] = dk4rle_literal_length_byte(128 - 2); /* Set total byte size. */ enc->oused = 127; /* Keep last 2 bytes. */ dk4mem_cpy_to_left( &(enc->ib[0]), &(enc->ib[126]), 2, NULL ); /* Number of used bytes is 2. */ enc->iused = 2; } } else { /* No need to keep any final bytes. */ /* Copy data. */ DK4_MEMCPY( &(enc->ob[1]), &(enc->ib[0]), enc->iused ); /* Set run-length byte. */ enc->ob[0] = dk4rle_literal_length_byte(128); /* Set total byte size. */ enc->oused = 129; /* No input byte in buffer. */ enc->iused = 0; } back = DK4_EDSTM_FINISHED; } } } } break; } } else { $? "! enc" dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } $? "- dk4rle_add %d", back return back; } int dk4rle_finish(dk4_rl_enc_t *enc, dk4_er_t *erp) { int back = DK4_EDSTM_ERROR; $? "+ dk4rle_finish" if (NULL != enc) { back = DK4_EDSTM_ACCEPT; if (0 < enc->iused) { switch (enc->st) { case RLE_ENC_STATE_RUN : { /* Copy data to output buffer. */ enc->ob[1] = enc->ib[0]; /* Set run-length byte. */ enc->ob[0] = dk4rle_run_length_byte(enc->iused); /* Set total byte size. */ enc->oused = 2; if (0 != enc->weod) { /* Add EOD marker. */ enc->ob[2] = (unsigned char)128; enc->oused = 3; } } break; default : { /* Copy data to output buffer. */ DK4_MEMCPY( &(enc->ob[1]), &(enc->ib[0]), enc->iused ); /* Set literal length byte. */ enc->ob[0] = dk4rle_literal_length_byte(enc->iused); /* Set total byte size. */ enc->oused = 1 + enc->iused; if (0 != enc->weod) { /* Add EOD marker. */ enc->ob[1 + enc->iused] = (unsigned char)128; enc->oused += 1; } } break; } back = DK4_EDSTM_FINISHED; } else { if (0 != enc->weod) { enc->ob[0] = (unsigned char)128; enc->oused = 1; back = DK4_EDSTM_FINISHED; } } enc->iused = 0; enc->st = RLE_ENC_STATE_NO_RUN; } else { dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } $? "- dk4rle_finish %d", back return back; } int dk4rle_output( const unsigned char **dptr, size_t *szptr, dk4_rl_enc_t *enc, dk4_er_t *erp ) { int back = 0; $? "+ dk4rle_output" if (NULL != enc) { if (0 < enc->oused) { *dptr = &(enc->ob[0]); *szptr = enc->oused; back = 1; } } else { dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } $? "- dk4rle_output %d", back return back; } /* ---------------------------- */ #endif