source: mainline/uspace/lib/net/generic/net_checksum.c@ c3887ad

/*
 * Copyright (c) 2009 Lukas Mejdrech
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/** @addtogroup libnet
 * @{
 */

/** @file
 * General CRC and checksum computation implementation.
 */

#include <sys/types.h>

#include <net_checksum.h>

/** Big-endian encoding CRC divider. */
#define CRC_DIVIDER_BE  0x04c11db7

/** Little-endian encoding CRC divider. */
#define CRC_DIVIDER_LE  0xedb88320

/** Polynomial used in multicast address hashing */
#define CRC_MCAST_POLYNOMIAL  0x04c11db6

/** Compacts the computed checksum to the 16 bit number adding the carries.
 *
 * @param[in] sum       Computed checksum.
 * @return              Compacted computed checksum to the 16 bits.
 */
uint16_t compact_checksum(uint32_t sum)
{
        /* Shorten to the 16 bits */
        while (sum >> 16)
                sum = (sum & 0xffff) + (sum >> 16);

        return (uint16_t) sum;
}

/** Computes sum of the 2 byte fields.
 *
 * Padds one zero (0) byte if odd.
 *
 * @param[in] seed      Initial value. Often used as 0 or ~0.
 * @param[in] data      Pointer to the beginning of data to process.
 * @param[in] length    Length of the data in bytes.
 * @return              The computed checksum of the length bytes of the data.
 */
uint32_t compute_checksum(uint32_t seed, uint8_t *data, size_t length)
{
        size_t index;

        /* Sum all the 16 bit fields */
        for (index = 0; index + 1 < length; index += 2)
                seed += (data[index] << 8) + data[index + 1];

        /* Last odd byte with zero padding */
        if (index + 1 == length)
                seed += data[index] << 8;

        return seed;
}

/** Computes CRC32 value in the big-endian environment.
 *
 * @param[in] seed      Initial value. Often used as 0 or ~0.
 * @param[in] data      Pointer to the beginning of data to process.
 * @param[in] length    Length of the data in bits.
 * @return              The computed CRC32 of the length bits of the data.
 */
uint32_t compute_crc32_be(uint32_t seed, uint8_t * data, size_t length)
{
        size_t index;

        /* Process full bytes */
        while (length >= 8) {
                /* Add the data */
                seed ^= (*data) << 24;
                
                /* For each added bit */
                for (index = 0; index < 8; ++index) {
                        /* If the first bit is set */
                        if (seed & 0x80000000) {
                                /* Shift and divide the checksum */
                                seed = (seed << 1) ^ ((uint32_t) CRC_DIVIDER_BE);
                        } else {
                                /* Shift otherwise */
                                seed <<= 1;
                        }
                }
                
                /* Move to the next byte */
                ++data;
                length -= 8;
        }

        /* Process the odd bits */
        if (length > 0) {
                /* Add the data with zero padding */
                seed ^= ((*data) & (0xff << (8 - length))) << 24;
                
                /* For each added bit */
                for (index = 0; index < length; ++index) {
                        /* If the first bit is set */
                        if (seed & 0x80000000) {
                                /* Shift and divide the checksum */
                                seed = (seed << 1) ^ ((uint32_t) CRC_DIVIDER_BE);
                        } else {
                                /* Shift otherwise */
                                seed <<= 1;
                        }
                }
        }

        return seed;
}

/** Computes CRC32 value in the little-endian environment.
 *
 * @param[in] seed      Initial value. Often used as 0 or ~0.
 * @param[in] data      Pointer to the beginning of data to process.
 * @param[in] length    Length of the data in bits.
 * @return              The computed CRC32 of the length bits of the data.
 */
uint32_t compute_crc32_le(uint32_t seed, uint8_t * data, size_t length)
{
        size_t index;

        /* Process full bytes */
        while (length >= 8) {
                /* Add the data */
                seed ^= (*data);
                
                /* For each added bit */
                for (index = 0; index < 8; ++index) {
                        /* If the last bit is set */
                        if (seed & 1) {
                                /* Shift and divide the checksum */
                                seed = (seed >> 1) ^ ((uint32_t) CRC_DIVIDER_LE);
                        } else {
                                /* Shift otherwise */
                                seed >>= 1;
                        }
                }
                
                /* Move to the next byte */
                ++data;
                length -= 8;
        }

        /* Process the odd bits */
        if (length > 0) {
                /* Add the data with zero padding */
                seed ^= (*data) >> (8 - length);
                
                for (index = 0; index < length; ++index) {
                        /* If the last bit is set */
                        if (seed & 1) {
                                /* Shift and divide the checksum */
                                seed = (seed >> 1) ^ ((uint32_t) CRC_DIVIDER_LE);
                        } else {
                                /* Shift otherwise */
                                seed >>= 1;
                        }
                }
        }

        return seed;
}

/** Returns or flips the checksum if zero.
 *
 * @param[in] checksum  The computed checksum.
 * @return              The internet protocol header checksum.
 * @return              0xFFFF if the computed checksum is zero.
 */
uint16_t flip_checksum(uint16_t checksum)
{
        /* Flip, zero is returned as 0xFFFF (not flipped) */
        checksum = ~checksum;
        return checksum ? checksum : IP_CHECKSUM_ZERO;
}

/** Compute the IP header checksum.
 *
 * To compute the checksum of a new packet, the checksum header field must be
 * zero. To check the checksum of a received packet, the checksum may be left
 * set. Zero will be returned in this case if valid.
 *
 * @param[in] data      The header data.
 * @param[in] length    The header length in bytes.
 * @return              The internet protocol header checksum.
 * @return              0xFFFF if the computed checksum is zero.
 */
uint16_t ip_checksum(uint8_t *data, size_t length)
{
        /* Compute, compact and flip the data checksum */
        return flip_checksum(compact_checksum(compute_checksum(0, data,
            length)));
}

/** Compute the standard hash from MAC
 *
 * Hashing MAC into 64 possible values and using the value as index to
 * 64bit number.
 *
 * The code is copied from qemu-0.13's implementation of ne2000 and rt8139
 * drivers, but according to documentation there it originates in FreeBSD.
 *
 * @param[in] addr The 6-byte MAC address to be hashed
 *
 * @return 64-bit number with only single bit set to 1
 *
 */
uint64_t multicast_hash(const uint8_t addr[6])
{
        uint32_t crc;
    int carry, i, j;
    uint8_t b;

    crc = 0xffffffff;
    for (i = 0; i < 6; i++) {
        b = addr[i];
        for (j = 0; j < 8; j++) {
            carry = ((crc & 0x80000000L) ? 1 : 0) ^ (b & 0x01);
            crc <<= 1;
            b >>= 1;
            if (carry)
                crc = ((crc ^ CRC_MCAST_POLYNOMIAL) | carry);
        }
    }
        
    uint64_t one64 = 1;
    return one64 << (crc >> 26);
}

/** @}
 */