kernel/os/sctp_crc32.c

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 /*
  22  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  */
  25
  26 #include <sys/types.h>
  27
  28 /*
  29  * Fast CRC32 calculation algorithm suggested by Ferenc Rakoczi
  30  * (ferenc.rakoczi@sun.com).  The basic idea is to look at it
  31  * four bytes (one word) at a time, using four tables.  The
  32  * standard algorithm in RFC 3309 uses one table.
  33  */
  34
  35 /*
  36  * SCTP uses reflected/reverse polynomial CRC32 with generating
  37  * polynomial 0x1EDC6F41L
  38  */
  39 #define SCTP_POLY 0x1EDC6F41L
  40
  41 /* The four CRC tables. */
  42 static uint32_t crctab[4][256];
  43
  44 static uint32_t
  45 reflect_32(uint32_t b)
  46 {
  47         int i;
  48         uint32_t rw = 0;
  49
  50         for (i = 0; i < 32; i++) {
  51                 if (b & 1) {
  52                         rw |= 1 << (31 - i);
  53                 }
  54                 b >>= 1;
  55         }
  56         return (rw);
  57 }
  58
  59 #ifdef _BIG_ENDIAN
  60
  61 /*
  62  * This function is only used for big endian processor.
  63  */
  64 static uint32_t
  65 flip32(uint32_t w)
  66 {
  67         return (((w >> 24) | ((w >> 8) & 0xff00) | ((w << 8) & 0xff0000) |
  68             (w << 24)));
  69 }
  70
  71 #endif
  72
  73 void
  74 sctp_crc32_init(void)
  75 {
  76         uint32_t i, j, k, crc;
  77
  78         for (i = 0; i < 256; i++) {
  79                 crc = reflect_32(i);
  80                 for (k = 0; k < 4; k++) {
  81                         for (j = 0; j < 8; j++) {
  82                                 crc = (crc & 0x80000000) ?
  83                                     (crc << 1) ^ SCTP_POLY : crc << 1;
  84                         }
  85 #ifdef _BIG_ENDIAN
  86                         crctab[3 - k][i] = flip32(reflect_32(crc));
  87 #else
  88                         crctab[k][i] = reflect_32(crc);
  89 #endif
  90                 }
  91         }
  92 }
  93
  94 static void
  95 sctp_crc_byte(uint32_t *crcptr, const uint8_t *buf, int len)
  96 {
  97         uint32_t crc;
  98         int i;
  99
 100         crc = *crcptr;
 101         for (i = 0; i < len; i++) {
 102 #ifdef _BIG_ENDIAN
 103                 crc = (crc << 8) ^ crctab[3][buf[i] ^ (crc >> 24)];
 104 #else
 105                 crc = (crc >> 8) ^ crctab[0][buf[i] ^ (crc & 0xff)];
 106 #endif
 107         }
 108         *crcptr = crc;
 109 }
 110
 111 static void
 112 sctp_crc_word(uint32_t *crcptr, const uint32_t *buf, int len)
 113 {
 114         uint32_t w, crc;
 115         int i;
 116
 117         crc = *crcptr;
 118         for (i = 0; i < len; i++) {
 119                 w = crc ^ buf[i];
 120                 crc = crctab[0][w >> 24] ^ crctab[1][(w >> 16) & 0xff] ^
 121                     crctab[2][(w >> 8) & 0xff] ^ crctab[3][w & 0xff];
 122         }
 123         *crcptr = crc;
 124 }
 125
 126 uint32_t
 127 sctp_crc32(uint32_t crc32, const uint8_t *buf, int len)
 128 {
 129         int rem;
 130
 131         rem = 4 - ((uintptr_t)buf) & 3;
 132         if (rem != 0) {
 133                 if (len < rem) {
 134                         rem = len;
 135                 }
 136                 sctp_crc_byte(&crc32, buf, rem);
 137                 buf = buf + rem;
 138                 len = len - rem;
 139         }
 140
 141         if (len > 3) {
 142                 sctp_crc_word(&crc32, (const uint32_t *)buf, len / 4);
 143         }
 144
 145         rem = len & 3;
 146         if (rem != 0) {
 147                 sctp_crc_byte(&crc32, buf + len - rem, rem);
 148         }
 149         return (crc32);
 150 }