tools/genrb/rle.c

// © 2016 and later: Unicode, Inc. and others.
// License & terms of use: http://www.unicode.org/copyright.html
/*
*******************************************************************************
*
*   Copyright (C) 2000-2003, International Business Machines
*   Corporation and others.  All Rights Reserved.
*
*******************************************************************************
*
* File writejava.c
*
* Modification History:
*
*   Date        Name        Description
*   01/11/02    Ram        Creation.
*******************************************************************************
*/
#include <stdbool.h>
#include "rle.h"
/**
 * The ESCAPE character is used during run-length encoding.  It signals
 * a run of identical chars.
 */
static const uint16_t ESCAPE = 0xA5A5;

/**
 * The ESCAPE_BYTE character is used during run-length encoding.  It signals
 * a run of identical bytes.
 */
static const uint8_t ESCAPE_BYTE = (uint8_t)0xA5;

/**
 * Append a byte to the given StringBuffer, packing two bytes into each
 * character.  The state parameter maintains intermediary data between
 * calls.
 * @param state A two-element array, with state[0] == 0 if this is the
 * first byte of a pair, or state[0] != 0 if this is the second byte
 * of a pair, in which case state[1] is the first byte.
 */
static uint16_t*
appendEncodedByte(uint16_t* buffer, uint16_t* buffLimit, uint8_t value, uint8_t state[],UErrorCode* status) {
    if(!status || U_FAILURE(*status)){
        return NULL;
    }
    if (state[0] != 0) {
        uint16_t c = (uint16_t) ((state[1] << 8) | (((int32_t) value) & 0xFF));
        if(buffer < buffLimit){
            *buffer++ = c;
        }else{
            *status = U_BUFFER_OVERFLOW_ERROR;
        }
        state[0] = 0;
        return buffer;
    }
    else {
        state[0] = 1;
        state[1] = value;
        return buffer;
    }
}
/**
 * Encode a run, possibly a degenerate run (of < 4 values).
 * @param length The length of the run; must be > 0 && <= 0xFF.
 */
static uint16_t*
encodeRunByte(uint16_t* buffer,uint16_t* bufLimit, uint8_t value, int32_t length, uint8_t state[], UErrorCode* status) {
    if(!status || U_FAILURE(*status)){
        return NULL;
    }
    if (length < 4) {
        int32_t j=0;
        for (; j<length; ++j) {
            if (value == ESCAPE_BYTE) {
                buffer = appendEncodedByte(buffer,bufLimit, ESCAPE_BYTE, state,status);
            }
            buffer = appendEncodedByte(buffer,bufLimit, value, state, status);
        }
    }
    else {
        if (length == ESCAPE_BYTE) {
            if (value == ESCAPE_BYTE){
               buffer =  appendEncodedByte(buffer, bufLimit,ESCAPE_BYTE, state,status);
            }
            buffer = appendEncodedByte(buffer,bufLimit, value, state, status);
            --length;
        }
        buffer = appendEncodedByte(buffer,bufLimit, ESCAPE_BYTE, state,status);
        buffer = appendEncodedByte(buffer,bufLimit, (char)length, state, status);
        buffer = appendEncodedByte(buffer,bufLimit, value, state, status); /* Don't need to escape this value*/
    }
    return buffer;
}

#define APPEND( buffer, bufLimit, value, status) UPRV_BLOCK_MACRO_BEGIN { \
    if(buffer<bufLimit){                    \
        *buffer++=(value);                  \
    }else{                                  \
        *status = U_BUFFER_OVERFLOW_ERROR;  \
    }                                       \
} UPRV_BLOCK_MACRO_END

/**
 * Encode a run, possibly a degenerate run (of < 4 values).
 * @param length The length of the run; must be > 0 && <= 0xFFFF.
 */
static uint16_t*
encodeRunShort(uint16_t* buffer,uint16_t* bufLimit, uint16_t value, int32_t length,UErrorCode* status) {
    if (length < 4) {
        int j=0;
        for (; j<length; ++j) {
            if (value == (int32_t) ESCAPE){
                APPEND(buffer,bufLimit,ESCAPE, status);

            }
            APPEND(buffer,bufLimit,value,status);
        }
    }
    else {
        if (length == (int32_t) ESCAPE) {
            if (value == (int32_t) ESCAPE){
                APPEND(buffer,bufLimit,ESCAPE,status);

            }
            APPEND(buffer,bufLimit,value,status);
            --length;
        }
        APPEND(buffer,bufLimit,ESCAPE,status);
        APPEND(buffer,bufLimit,(uint16_t) length,status);
        APPEND(buffer,bufLimit,(uint16_t)value, status); /* Don't need to escape this value */
    }
    return buffer;
}

/**
 * Construct a string representing a char array.  Use run-length encoding.
 * A character represents itself, unless it is the ESCAPE character.  Then
 * the following notations are possible:
 *   ESCAPE ESCAPE   ESCAPE literal
 *   ESCAPE n c      n instances of character c
 * Since an encoded run occupies 3 characters, we only encode runs of 4 or
 * more characters.  Thus we have n > 0 and n != ESCAPE and n <= 0xFFFF.
 * If we encounter a run where n == ESCAPE, we represent this as:
 *   c ESCAPE n-1 c
 * The ESCAPE value is chosen so as not to collide with commonly
 * seen values.
 */
int32_t
usArrayToRLEString(const uint16_t* src,int32_t srcLen,uint16_t* buffer, int32_t bufLen,UErrorCode* status) {
    uint16_t* bufLimit =  buffer+bufLen;
    uint16_t* saveBuffer = buffer;
    if(buffer < bufLimit){
        *buffer++ =  (uint16_t)(srcLen>>16);
        if(buffer<bufLimit){
            uint16_t runValue = src[0];
            int32_t runLength = 1;
            int i=1;
            *buffer++ = (uint16_t) srcLen;

            for (; i<srcLen; ++i) {
                uint16_t s = src[i];
                if (s == runValue && runLength < 0xFFFF){
                    ++runLength;
                }else {
                    buffer = encodeRunShort(buffer, bufLimit, runValue, runLength, status);
                    runValue = s;
                    runLength = 1;
                }
            }
            buffer = encodeRunShort(buffer, bufLimit, runValue, runLength, status);
        }else{
            *status = U_BUFFER_OVERFLOW_ERROR;
        }
    }else{
        *status = U_BUFFER_OVERFLOW_ERROR;
    }
    return (int32_t)(buffer - saveBuffer);
}

/**
 * Construct a string representing a byte array.  Use run-length encoding.
 * Two bytes are packed into a single char, with a single extra zero byte at
 * the end if needed.  A byte represents itself, unless it is the
 * ESCAPE_BYTE.  Then the following notations are possible:
 *   ESCAPE_BYTE ESCAPE_BYTE   ESCAPE_BYTE literal
 *   ESCAPE_BYTE n b           n instances of byte b
 * Since an encoded run occupies 3 bytes, we only encode runs of 4 or
 * more bytes.  Thus we have n > 0 and n != ESCAPE_BYTE and n <= 0xFF.
 * If we encounter a run where n == ESCAPE_BYTE, we represent this as:
 *   b ESCAPE_BYTE n-1 b
 * The ESCAPE_BYTE value is chosen so as not to collide with commonly
 * seen values.
 */
int32_t
byteArrayToRLEString(const uint8_t* src,int32_t srcLen, uint16_t* buffer,int32_t bufLen, UErrorCode* status) {
    const uint16_t* saveBuf = buffer;
    uint16_t* bufLimit =  buffer+bufLen;
    if(buffer < bufLimit){
        *buffer++ = ((uint16_t) (srcLen >> 16));

        if(buffer<bufLimit){
            uint8_t runValue = src[0];
            int runLength = 1;
            uint8_t state[2]= {0};
            int i=1;
            *buffer++=((uint16_t) srcLen);
            for (; i<srcLen; ++i) {
                uint8_t b = src[i];
                if (b == runValue && runLength < 0xFF){
                    ++runLength;
                }
                else {
                    buffer = encodeRunByte(buffer, bufLimit,runValue, runLength, state,status);
                    runValue = b;
                    runLength = 1;
                }
            }
            buffer = encodeRunByte(buffer,bufLimit, runValue, runLength, state, status);

            /* We must save the final byte, if there is one, by padding
             * an extra zero.
             */
            if (state[0] != 0) {
                buffer = appendEncodedByte(buffer,bufLimit, 0, state ,status);
            }
        }else{
            *status = U_BUFFER_OVERFLOW_ERROR;
        }
    }else{
        *status = U_BUFFER_OVERFLOW_ERROR;
    }
    return (int32_t) (buffer - saveBuf);
}


/**
 * Construct an array of shorts from a run-length encoded string.
 */
int32_t
rleStringToUCharArray(uint16_t* src, int32_t srcLen, uint16_t* target, int32_t tgtLen, UErrorCode* status) {
    int32_t length = 0;
    int32_t ai = 0;
    int i=2;

    if(!status || U_FAILURE(*status)){
        return 0;
    }
    /* the source is null terminated */
    if(srcLen == -1){
        srcLen = u_strlen(src);
    }
    if(srcLen <= 2){
        return 2;
    }
    length = (((int32_t) src[0]) << 16) | ((int32_t) src[1]);

    if(target == NULL){
        return length;
    }
    if(tgtLen < length){
        *status = U_BUFFER_OVERFLOW_ERROR;
        return length;
    }

    for (; i<srcLen; ++i) {
        uint16_t c = src[i];
        if (c == ESCAPE) {
            c = src[++i];
            if (c == ESCAPE) {
                target[ai++] = c;
            } else {
                int32_t runLength = (int32_t) c;
                uint16_t runValue = src[++i];
                int j=0;
                for (; j<runLength; ++j) {
                    target[ai++] = runValue;
                }
            }
        }
        else {
            target[ai++] = c;
        }
    }

    if (ai != length){
        *status = U_INTERNAL_PROGRAM_ERROR;
    }

    return length;
}

/**
 * Construct an array of bytes from a run-length encoded string.
 */
int32_t
rleStringToByteArray(uint16_t* src, int32_t srcLen, uint8_t* target, int32_t tgtLen, UErrorCode* status) {

    int32_t length = 0;
    UBool nextChar = true;
    uint16_t c = 0;
    int32_t node = 0;
    int32_t runLength = 0;
    int32_t i = 2;
    int32_t ai=0;

    if(!status || U_FAILURE(*status)){
        return 0;
    }
    /* the source is null terminated */
    if(srcLen == -1){
        srcLen = u_strlen(src);
    }
    if(srcLen <= 2){
        return 2;
    }
    length = (((int32_t) src[0]) << 16) | ((int32_t) src[1]);

    if(target == NULL){
        return length;
    }
    if(tgtLen < length){
        *status = U_BUFFER_OVERFLOW_ERROR;
        return length;
    }

    for (; ai<tgtLen; ) {
       /* This part of the loop places the next byte into the local
        * variable 'b' each time through the loop.  It keeps the
        * current character in 'c' and uses the boolean 'nextChar'
        * to see if we've taken both bytes out of 'c' yet.
        */
        uint8_t b;
        if (nextChar) {
            c = src[i++];
            b = (uint8_t) (c >> 8);
            nextChar = false;
        }
        else {
            b = (uint8_t) (c & 0xFF);
            nextChar = true;
        }

       /* This part of the loop is a tiny state machine which handles
        * the parsing of the run-length encoding.  This would be simpler
        * if we could look ahead, but we can't, so we use 'node' to
        * move between three nodes in the state machine.
        */
        switch (node) {
        case 0:
            /* Normal idle node */
            if (b == ESCAPE_BYTE) {
                node = 1;
            }
            else {
                target[ai++] = b;
            }
            break;
        case 1:
           /* We have seen one ESCAPE_BYTE; we expect either a second
            * one, or a run length and value.
            */
            if (b == ESCAPE_BYTE) {
                target[ai++] = ESCAPE_BYTE;
                node = 0;
            }
            else {
                runLength = b;
                node = 2;
            }
            break;
        case 2:
            {
                int j=0;
               /* We have seen an ESCAPE_BYTE and length byte.  We interpret
                * the next byte as the value to be repeated.
                */
                for (; j<runLength; ++j){
                    if(ai<tgtLen){
                        target[ai++] = b;
                    }else{
                        *status = U_BUFFER_OVERFLOW_ERROR;
                        return ai;
                    }
                }
                node = 0;
                break;
            }
        }
    }

    if (node != 0){
        *status = U_INTERNAL_PROGRAM_ERROR;
        /*("Bad run-length encoded byte array")*/
        return 0;
    }


    if (i != srcLen){
        /*("Excess data in RLE byte array string");*/
        *status = U_INTERNAL_PROGRAM_ERROR;
        return ai;
    }

    return ai;
}