bitarray.c

Huffman 压缩/解压算法的ANSI C实现 This archive contains a simple and readable ANSI C implementation of Huffm

}

/***************************************************************************
*   Function   : BitArrayOr
*   Description: This function performs a bitwise OR between two bit
*                arrays, storing the results in a third bit array.  If the
*                arrays are NULL or different in size, no operation will
*                will occur.
*   Parameters : dest - pointer to destination bit array
*                src1 - pointer to first source bit array
*                src2 - pointer to second source bit array
*   Effects    : dest will contain the results of a bitwise OR of src1 and
*                src2 unless one array pointer is NULL or arrays are
*                different in size.
*   Returned   : NONE
***************************************************************************/
void BitArrayOr(bit_array_t *dest,
           const bit_array_t *src1,
           const bit_array_t *src2)
{
    int i;

    if (src1 == NULL)
    {
        return;         /* no source array */
    }

    if (src2 == NULL)
    {
        return;         /* no source array */
    }

    if (dest == NULL)
    {
        return;         /* no destination array */
    }

    if (src1->numBits != dest->numBits)
    {
        return;         /* size mismatch */
    }

    if (src2->numBits != dest->numBits)
    {
        return;         /* size mismatch */
    }

    /* OR array one unsigned char at a time */
    for(i = 0; i < BITS_TO_CHARS(dest->numBits); i++)
    {
        dest->array[i] = src1->array[i] | src2->array[i];
    }
}

/***************************************************************************
*   Function   : BitArrayXor
*   Description: This function performs a bitwise XOR between two bit
*                arrays, storing the results in a third bit array.  If the
*                arrays are NULL or different in size, no operation will
*                will occur.
*   Parameters : dest - pointer to destination bit array
*                src1 - pointer to first source bit array
*                src2 - pointer to second source bit array
*   Effects    : dest will contain the results of a bitwise XOR of src1 and
*                src2 unless one array pointer is NULL or arrays are
*                different in size.
*   Returned   : NONE
***************************************************************************/
void BitArrayXor(bit_array_t *dest,
            const bit_array_t *src1,
            const bit_array_t *src2)
{
    int i;

    if (src1 == NULL)
    {
        return;         /* no source array */
    }

    if (src2 == NULL)
    {
        return;         /* no source array */
    }

    if (dest == NULL)
    {
        return;         /* no destination array */
    }

    if (src1->numBits != dest->numBits)
    {
        return;         /* size mismatch */
    }

    if (src2->numBits != dest->numBits)
    {
        return;         /* size mismatch */
    }

    /* XOR array one unsigned char at a time */
    for(i = 0; i < BITS_TO_CHARS(dest->numBits); i++)
    {
        dest->array[i] = src1->array[i] ^ src2->array[i];
    }
}

/***************************************************************************
*   Function   : BitArrayNot
*   Description: This function performs a bitwise NOT between two bit
*                arrays, storing the results in a third bit array.  If the
*                arrays are NULL or different in size, no operation will
*                will occur.
*   Parameters : dest - pointer to destination bit array
*                src1 - pointer to first source bit array
*                src2 - pointer to second source bit array
*   Effects    : dest will contain the results of a bitwise XOR of src1 and
*                src2 unless one array pointer is NULL or arrays are
*                different in size.
*   Returned   : NONE
***************************************************************************/
void BitArrayNot(bit_array_t *dest,
            const bit_array_t *src)
{
    int i, bits;
    unsigned char mask;

    if (src == NULL)
    {
        return;         /* no source array */
    }

    if (dest == NULL)
    {
        return;         /* no destination array */
    }

    if (src->numBits != dest->numBits)
    {
        return;         /* size mismatch */
    }

    /* NOT array one unsigned char at a time */
    for(i = 0; i < BITS_TO_CHARS(dest->numBits); i++)
    {
        dest->array[i] = ~(src->array[i]);
    }

    /* zero any spare bits so increment and decrement are consistent */
    bits = dest->numBits % CHAR_BIT;
    if (bits != 0)
    {
        mask = UCHAR_MAX << (CHAR_BIT - bits);
        dest->array[BIT_CHAR(dest->numBits - 1)] &= mask;
    }
}

/***************************************************************************
*   Function   : BitArrayShiftLeft
*   Description: This function shifts the bits in a bit array to the left
*                by the amount of positions specified.
*   Parameters : ba - pointer to the bit array 0 is the msb of the first
*                     unsigned char in the bit array.
*                shifts - number of bits to shift by.
*   Effects    : The bit array data pointed to by ba is shifted to the left.
*                New bits shifted in will be set to 0.
*   Returned   : None
***************************************************************************/
void BitArrayShiftLeft(bit_array_t *ba, unsigned int shifts)
{
    int i, j;
    int chars = shifts / CHAR_BIT;  /* number of whole byte shifts */
    shifts = shifts % CHAR_BIT;     /* number of bit shifts remaining */

    if (ba == NULL)
    {
        return;         /* nothing to shift */
    }

    if (shifts >= ba->numBits)
    {
        /* all bits have been shifted off */
        BitArrayClearAll(ba);
        return;
    }

    /* first handle big jumps of bytes */
    if (chars > 0)
    {
        for (i = 0; (i + chars) <  BITS_TO_CHARS(ba->numBits); i++)
        {
            ba->array[i] = ba->array[i + chars];
        }

        /* now zero out new bytes on the right */
        for (i = BITS_TO_CHARS(ba->numBits); chars > 0; chars--)
        {
            ba->array[i - chars] = 0;
        }
    }

    /* now we have at most CHAR_BIT - 1 bit shifts across the whole array */
    for (i = 0; i < shifts; i++)
    {
        for (j = 0; j < BIT_CHAR(ba->numBits - 1); j++)
        {
            ba->array[j] <<= 1;

            /* handle shifts across byte bounds */
            if (ba->array[j + 1] & MS_BIT)
            {
                ba->array[j] |= 0x01;
            }
        }

        ba->array[BIT_CHAR(ba->numBits - 1)] <<= 1;
    }
}

/***************************************************************************
*   Function   : BitArrayShiftRight
*   Description: This function shifts the bits in a bit array to the right
*                by the amount of positions specified.
*   Parameters : ba - pointer to the bit array 0 is the msb of the first
*                     unsigned char in the bit array.
*                shifts - number of bits to shift by.
*   Effects    : The bit array data pointed to by ba is shifted to the
*                right.  New bits shifted in will be set to 0.
*   Returned   : None
***************************************************************************/
void BitArrayShiftRight(bit_array_t *ba, unsigned int shifts)
{
    int i, j;
    unsigned char mask;
    int chars = shifts / CHAR_BIT;  /* number of whole byte shifts */
    shifts = shifts % CHAR_BIT;     /* number of bit shifts remaining */

    if (ba == NULL)
    {
        return;         /* nothing to shift */
    }

    if (shifts >= ba->numBits)
    {
        /* all bits have been shifted off */
        BitArrayClearAll(ba);
        return;
    }

    /* first handle big jumps of bytes */
    if (chars > 0)
    {
        for (i = BIT_CHAR(ba->numBits - 1); (i - chars) >= 0; i--)
        {
            ba->array[i] = ba->array[i - chars];
        }

        /* now zero out new bytes on the right */
        for (; chars > 0; chars--)
        {
            ba->array[chars - 1] = 0;
        }
    }

    /* now we have at most CHAR_BIT - 1 bit shifts across the whole array */
    for (i = 0; i < shifts; i++)
    {
        for (j = BIT_CHAR(ba->numBits - 1); j > 0; j--)
        {
            ba->array[j] >>= 1;

            /* handle shifts across byte bounds */
            if (ba->array[j - 1] & 0x01)
            {
                ba->array[j] |= MS_BIT;
            }
        }

        ba->array[0] >>= 1;
    }

    /***********************************************************************
    * zero any spare bits that are beyond the end of the bit array so
    * increment and decrement are consistent.
    ***********************************************************************/
    i = ba->numBits % CHAR_BIT;
    if (i != 0)
    {
        mask = UCHAR_MAX << (CHAR_BIT - i);
        ba->array[BIT_CHAR(ba->numBits - 1)] &= mask;
    }
}

/***************************************************************************
*   Function   : BitArrayIncrement
*   Description: This function increments a bit array as if it is an
*                unsigned value of the specified number of bits.
*   Parameters : ba - pointer bit array to be incremented
*   Effects    : ba will contain the results of an increment operation
*                performed on itself.  Any spare bits in the array of
*                unsigned characters containing the bits will be set to 0.
*   Returned   : None
***************************************************************************/
void BitArrayIncrement(bit_array_t *ba)
{
    int i;
    unsigned char maxValue;     /* maximum value for current char */
    unsigned char one;          /* least significant bit in current char */

    if (ba == NULL)
    {
        return;         /* nothing to increment */
    }

    /* handle arrays that don't use every bit in the last character */
    i = (ba->numBits % CHAR_BIT);
    if (i != 0)
    {
        maxValue = UCHAR_MAX << (CHAR_BIT - i);
        one = 1 << (CHAR_BIT - i);
    }
    else
    {
        maxValue = UCHAR_MAX;
        one = 1;
    }

    for (i = BIT_CHAR(ba->numBits - 1); i >= 0; i--)
    {
        if (ba->array[i] != maxValue)
        {
            ba->array[i] = ba->array[i] + one;
            return;
        }
        else
        {
            /* need to carry to next byte */
            ba->array[i] = 0;

            /* remaining characters must use all bits */
            maxValue = UCHAR_MAX;
            one = 1;
        }
    }
}

/***************************************************************************
*   Function   : BitArrayDecrement
*   Description: This function decrements a bit array as if it is an
*                unsigned value of the specified number of bits.
*   Parameters : ba - pointer bit array to be decremented
*   Effects    : ba will contain the results of a decrement operation
*                performed on itself.  Any spare bits in the array of
*                unsigned characters containing the bits will be set to 0.
*   Returned   : None
***************************************************************************/
void BitArrayDecrement(bit_array_t *ba)
{
    int i;
    unsigned char maxValue;     /* maximum value for current char */
    unsigned char one;          /* least significant bit in current char */

    if (ba == NULL)
    {
        return;         /* nothing to decrement */
    }

    /* handle arrays that don't use every bit in the last character */
    i = (ba->numBits % CHAR_BIT);
    if (i != 0)
    {
        maxValue = UCHAR_MAX << (CHAR_BIT - i);
        one = 1 << (CHAR_BIT - i);
    }
    else
    {
        maxValue = UCHAR_MAX;
        one = 1;
    }

    for (i = BIT_CHAR(ba->numBits - 1); i >= 0; i--)
    {
        if (ba->array[i] >= one)
        {
            ba->array[i] = ba->array[i] - one;
            return;
        }
        else
        {
            /* need to borrow from the next byte */
            ba->array[i] = maxValue;

            /* remaining characters must use all bits */
            maxValue = UCHAR_MAX;
            one = 1;
        }
    }
}

/***************************************************************************
*   Function   : BitArrayCompare
*   Description: This function compares two bit arrays.
*   Parameters : ba1 - pointer to bit array
*                ba2 - pointer to bit array
*   Effects    : None
*   Returned   : < 0 if ba1 < ba2 or ba1 is shorter than ba2
*                0 if ba1 == ba2
*                > 0 if ba1 > ba2 or ba1 is longer than ba2
***************************************************************************/
int BitArrayCompare(const bit_array_t *ba1, const bit_array_t *ba2)
{
    int i;

    if (ba1 == NULL)
    {
        if (ba2 == NULL)
        {
            return 0;                   /* both are NULL */
        }
        else
        {
            return -(ba2->numBits);     /* ba2 is the only Non-NULL*/
        }
    }

    if (ba2 == NULL)
    {
        return (ba1->numBits);          /* ba1 is the only Non-NULL*/
    }

    if (ba1->numBits != ba2->numBits)
    {
        /* arrays are different sizes */
        return(ba1->numBits - ba2->numBits);
    }

    for(i = 0; i <= BIT_CHAR(ba1->numBits - 1); i++)
    {
        if (ba1->array[i] != ba2->array[i])
        {
            /* found a non-matching unsigned char */
            return(ba1->array[i] - ba2->array[i]);
        }
    }

    return 0;
}