Branch data     Line data    Source code

       1                 :            : /*
       2                 :            :  * Aug 8, 2011 Bob Pearson with help from Joakim Tjernlund and George Spelvin
       3                 :            :  * cleaned up code to current version of sparse and added the slicing-by-8
       4                 :            :  * algorithm to the closely similar existing slicing-by-4 algorithm.
       5                 :            :  *
       6                 :            :  * Oct 15, 2000 Matt Domsch <Matt_Domsch@dell.com>
       7                 :            :  * Nicer crc32 functions/docs submitted by linux@horizon.com.  Thanks!
       8                 :            :  * Code was from the public domain, copyright abandoned.  Code was
       9                 :            :  * subsequently included in the kernel, thus was re-licensed under the
      10                 :            :  * GNU GPL v2.
      11                 :            :  *
      12                 :            :  * Oct 12, 2000 Matt Domsch <Matt_Domsch@dell.com>
      13                 :            :  * Same crc32 function was used in 5 other places in the kernel.
      14                 :            :  * I made one version, and deleted the others.
      15                 :            :  * There are various incantations of crc32().  Some use a seed of 0 or ~0.
      16                 :            :  * Some xor at the end with ~0.  The generic crc32() function takes
      17                 :            :  * seed as an argument, and doesn't xor at the end.  Then individual
      18                 :            :  * users can do whatever they need.
      19                 :            :  *   drivers/net/smc9194.c uses seed ~0, doesn't xor with ~0.
      20                 :            :  *   fs/jffs2 uses seed 0, doesn't xor with ~0.
      21                 :            :  *   fs/partitions/efi.c uses seed ~0, xor's with ~0.
      22                 :            :  *
      23                 :            :  * This source code is licensed under the GNU General Public License,
      24                 :            :  * Version 2.  See the file COPYING for more details.
      25                 :            :  */
      26                 :            : 
      27                 :            : /* see: Documentation/crc32.txt for a description of algorithms */
      28                 :            : 
      29                 :            : #include <linux/crc32.h>
      30                 :            : #include <linux/crc32poly.h>
      31                 :            : #include <linux/module.h>
      32                 :            : #include <linux/types.h>
      33                 :            : #include <linux/sched.h>
      34                 :            : #include "crc32defs.h"
      35                 :            : 
      36                 :            : #if CRC_LE_BITS > 8
      37                 :            : # define tole(x) ((__force u32) cpu_to_le32(x))
      38                 :            : #else
      39                 :            : # define tole(x) (x)
      40                 :            : #endif
      41                 :            : 
      42                 :            : #if CRC_BE_BITS > 8
      43                 :            : # define tobe(x) ((__force u32) cpu_to_be32(x))
      44                 :            : #else
      45                 :            : # define tobe(x) (x)
      46                 :            : #endif
      47                 :            : 
      48                 :            : #include "crc32table.h"
      49                 :            : 
      50                 :            : MODULE_AUTHOR("Matt Domsch <Matt_Domsch@dell.com>");
      51                 :            : MODULE_DESCRIPTION("Various CRC32 calculations");
      52                 :            : MODULE_LICENSE("GPL");
      53                 :            : 
      54                 :            : #if CRC_LE_BITS > 8 || CRC_BE_BITS > 8
      55                 :            : 
      56                 :            : /* implements slicing-by-4 or slicing-by-8 algorithm */
      57                 :            : static inline u32 __pure
      58                 :          3 : crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256])
      59                 :            : {
      60                 :            : # ifdef __LITTLE_ENDIAN
      61                 :            : #  define DO_CRC(x) crc = t0[(crc ^ (x)) & 255] ^ (crc >> 8)
      62                 :            : #  define DO_CRC4 (t3[(q) & 255] ^ t2[(q >> 8) & 255] ^ \
      63                 :            :                    t1[(q >> 16) & 255] ^ t0[(q >> 24) & 255])
      64                 :            : #  define DO_CRC8 (t7[(q) & 255] ^ t6[(q >> 8) & 255] ^ \
      65                 :            :                    t5[(q >> 16) & 255] ^ t4[(q >> 24) & 255])
      66                 :            : # else
      67                 :            : #  define DO_CRC(x) crc = t0[((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
      68                 :            : #  define DO_CRC4 (t0[(q) & 255] ^ t1[(q >> 8) & 255] ^ \
      69                 :            :                    t2[(q >> 16) & 255] ^ t3[(q >> 24) & 255])
      70                 :            : #  define DO_CRC8 (t4[(q) & 255] ^ t5[(q >> 8) & 255] ^ \
      71                 :            :                    t6[(q >> 16) & 255] ^ t7[(q >> 24) & 255])
      72                 :            : # endif
      73                 :            :         const u32 *b;
      74                 :            :         size_t    rem_len;
      75                 :            : # ifdef CONFIG_X86
      76                 :            :         size_t i;
      77                 :            : # endif
      78                 :            :         const u32 *t0=tab[0], *t1=tab[1], *t2=tab[2], *t3=tab[3];
      79                 :            : # if CRC_LE_BITS != 32
      80                 :            :         const u32 *t4 = tab[4], *t5 = tab[5], *t6 = tab[6], *t7 = tab[7];
      81                 :            : # endif
      82                 :            :         u32 q;
      83                 :            : 
      84                 :            :         /* Align it */
      85                 :          3 :         if (unlikely((long)buf & 3 && len)) {
      86                 :            :                 do {
      87                 :          0 :                         DO_CRC(*buf++);
      88                 :          0 :                 } while ((--len) && ((long)buf)&3);
      89                 :            :         }
      90                 :            : 
      91                 :            : # if CRC_LE_BITS == 32
      92                 :            :         rem_len = len & 3;
      93                 :            :         len = len >> 2;
      94                 :            : # else
      95                 :          3 :         rem_len = len & 7;
      96                 :          3 :         len = len >> 3;
      97                 :            : # endif
      98                 :            : 
      99                 :            :         b = (const u32 *)buf;
     100                 :            : # ifdef CONFIG_X86
     101                 :            :         --b;
     102                 :            :         for (i = 0; i < len; i++) {
     103                 :            : # else
     104                 :          3 :         for (--b; len; --len) {
     105                 :            : # endif
     106                 :          3 :                 q = crc ^ *++b; /* use pre increment for speed */
     107                 :            : # if CRC_LE_BITS == 32
     108                 :            :                 crc = DO_CRC4;
     109                 :            : # else
     110                 :          3 :                 crc = DO_CRC8;
     111                 :          3 :                 q = *++b;
     112                 :          3 :                 crc ^= DO_CRC4;
     113                 :            : # endif
     114                 :            :         }
     115                 :            :         len = rem_len;
     116                 :            :         /* And the last few bytes */
     117                 :          3 :         if (len) {
     118                 :          3 :                 u8 *p = (u8 *)(b + 1) - 1;
     119                 :            : # ifdef CONFIG_X86
     120                 :            :                 for (i = 0; i < len; i++)
     121                 :            :                         DO_CRC(*++p); /* use pre increment for speed */
     122                 :            : # else
     123                 :            :                 do {
     124                 :          3 :                         DO_CRC(*++p); /* use pre increment for speed */
     125                 :          3 :                 } while (--len);
     126                 :            : # endif
     127                 :            :         }
     128                 :          3 :         return crc;
     129                 :            : #undef DO_CRC
     130                 :            : #undef DO_CRC4
     131                 :            : #undef DO_CRC8
     132                 :            : }
     133                 :            : #endif
     134                 :            : 
     135                 :            : 
     136                 :            : /**
     137                 :            :  * crc32_le_generic() - Calculate bitwise little-endian Ethernet AUTODIN II
     138                 :            :  *                      CRC32/CRC32C
     139                 :            :  * @crc: seed value for computation.  ~0 for Ethernet, sometimes 0 for other
     140                 :            :  *       uses, or the previous crc32/crc32c value if computing incrementally.
     141                 :            :  * @p: pointer to buffer over which CRC32/CRC32C is run
     142                 :            :  * @len: length of buffer @p
     143                 :            :  * @tab: little-endian Ethernet table
     144                 :            :  * @polynomial: CRC32/CRC32c LE polynomial
     145                 :            :  */
     146                 :            : static inline u32 __pure crc32_le_generic(u32 crc, unsigned char const *p,
     147                 :            :                                           size_t len, const u32 (*tab)[256],
     148                 :            :                                           u32 polynomial)
     149                 :            : {
     150                 :            : #if CRC_LE_BITS == 1
     151                 :            :         int i;
     152                 :            :         while (len--) {
     153                 :            :                 crc ^= *p++;
     154                 :            :                 for (i = 0; i < 8; i++)
     155                 :            :                         crc = (crc >> 1) ^ ((crc & 1) ? polynomial : 0);
     156                 :            :         }
     157                 :            : # elif CRC_LE_BITS == 2
     158                 :            :         while (len--) {
     159                 :            :                 crc ^= *p++;
     160                 :            :                 crc = (crc >> 2) ^ tab[0][crc & 3];
     161                 :            :                 crc = (crc >> 2) ^ tab[0][crc & 3];
     162                 :            :                 crc = (crc >> 2) ^ tab[0][crc & 3];
     163                 :            :                 crc = (crc >> 2) ^ tab[0][crc & 3];
     164                 :            :         }
     165                 :            : # elif CRC_LE_BITS == 4
     166                 :            :         while (len--) {
     167                 :            :                 crc ^= *p++;
     168                 :            :                 crc = (crc >> 4) ^ tab[0][crc & 15];
     169                 :            :                 crc = (crc >> 4) ^ tab[0][crc & 15];
     170                 :            :         }
     171                 :            : # elif CRC_LE_BITS == 8
     172                 :            :         /* aka Sarwate algorithm */
     173                 :            :         while (len--) {
     174                 :            :                 crc ^= *p++;
     175                 :            :                 crc = (crc >> 8) ^ tab[0][crc & 255];
     176                 :            :         }
     177                 :            : # else
     178                 :            :         crc = (__force u32) __cpu_to_le32(crc);
     179                 :          2 :         crc = crc32_body(crc, p, len, tab);
     180                 :            :         crc = __le32_to_cpu((__force __le32)crc);
     181                 :            : #endif
     182                 :            :         return crc;
     183                 :            : }
     184                 :            : 
     185                 :            : #if CRC_LE_BITS == 1
     186                 :            : u32 __pure __weak crc32_le(u32 crc, unsigned char const *p, size_t len)
     187                 :            : {
     188                 :            :         return crc32_le_generic(crc, p, len, NULL, CRC32_POLY_LE);
     189                 :            : }
     190                 :            : u32 __pure __weak __crc32c_le(u32 crc, unsigned char const *p, size_t len)
     191                 :            : {
     192                 :            :         return crc32_le_generic(crc, p, len, NULL, CRC32C_POLY_LE);
     193                 :            : }
     194                 :            : #else
     195                 :          2 : u32 __pure __weak crc32_le(u32 crc, unsigned char const *p, size_t len)
     196                 :            : {
     197                 :          2 :         return crc32_le_generic(crc, p, len,
     198                 :            :                         (const u32 (*)[256])crc32table_le, CRC32_POLY_LE);
     199                 :            : }
     200                 :          0 : u32 __pure __weak __crc32c_le(u32 crc, unsigned char const *p, size_t len)
     201                 :            : {
     202                 :          0 :         return crc32_le_generic(crc, p, len,
     203                 :            :                         (const u32 (*)[256])crc32ctable_le, CRC32C_POLY_LE);
     204                 :            : }
     205                 :            : #endif
     206                 :            : EXPORT_SYMBOL(crc32_le);
     207                 :            : EXPORT_SYMBOL(__crc32c_le);
     208                 :            : 
     209                 :            : u32 __pure crc32_le_base(u32, unsigned char const *, size_t) __alias(crc32_le);
     210                 :            : u32 __pure __crc32c_le_base(u32, unsigned char const *, size_t) __alias(__crc32c_le);
     211                 :            : 
     212                 :            : /*
     213                 :            :  * This multiplies the polynomials x and y modulo the given modulus.
     214                 :            :  * This follows the "little-endian" CRC convention that the lsbit
     215                 :            :  * represents the highest power of x, and the msbit represents x^0.
     216                 :            :  */
     217                 :            : static u32 __attribute_const__ gf2_multiply(u32 x, u32 y, u32 modulus)
     218                 :            : {
     219                 :          0 :         u32 product = x & 1 ? y : 0;
     220                 :            :         int i;
     221                 :            : 
     222                 :          0 :         for (i = 0; i < 31; i++) {
     223                 :          0 :                 product = (product >> 1) ^ (product & 1 ? modulus : 0);
     224                 :          0 :                 x >>= 1;
     225                 :          0 :                 product ^= x & 1 ? y : 0;
     226                 :            :         }
     227                 :            : 
     228                 :          0 :         return product;
     229                 :            : }
     230                 :            : 
     231                 :            : /**
     232                 :            :  * crc32_generic_shift - Append @len 0 bytes to crc, in logarithmic time
     233                 :            :  * @crc: The original little-endian CRC (i.e. lsbit is x^31 coefficient)
     234                 :            :  * @len: The number of bytes. @crc is multiplied by x^(8*@len)
     235                 :            :  * @polynomial: The modulus used to reduce the result to 32 bits.
     236                 :            :  *
     237                 :            :  * It's possible to parallelize CRC computations by computing a CRC
     238                 :            :  * over separate ranges of a buffer, then summing them.
     239                 :            :  * This shifts the given CRC by 8*len bits (i.e. produces the same effect
     240                 :            :  * as appending len bytes of zero to the data), in time proportional
     241                 :            :  * to log(len).
     242                 :            :  */
     243                 :          0 : static u32 __attribute_const__ crc32_generic_shift(u32 crc, size_t len,
     244                 :            :                                                    u32 polynomial)
     245                 :            : {
     246                 :            :         u32 power = polynomial; /* CRC of x^32 */
     247                 :            :         int i;
     248                 :            : 
     249                 :            :         /* Shift up to 32 bits in the simple linear way */
     250                 :          0 :         for (i = 0; i < 8 * (int)(len & 3); i++)
     251                 :          0 :                 crc = (crc >> 1) ^ (crc & 1 ? polynomial : 0);
     252                 :            : 
     253                 :          0 :         len >>= 2;
     254                 :          0 :         if (!len)
     255                 :          0 :                 return crc;
     256                 :            : 
     257                 :            :         for (;;) {
     258                 :            :                 /* "power" is x^(2^i), modulo the polynomial */
     259                 :          0 :                 if (len & 1)
     260                 :            :                         crc = gf2_multiply(crc, power, polynomial);
     261                 :            : 
     262                 :          0 :                 len >>= 1;
     263                 :          0 :                 if (!len)
     264                 :            :                         break;
     265                 :            : 
     266                 :            :                 /* Square power, advancing to x^(2^(i+1)) */
     267                 :            :                 power = gf2_multiply(power, power, polynomial);
     268                 :            :         }
     269                 :            : 
     270                 :          0 :         return crc;
     271                 :            : }
     272                 :            : 
     273                 :          0 : u32 __attribute_const__ crc32_le_shift(u32 crc, size_t len)
     274                 :            : {
     275                 :          0 :         return crc32_generic_shift(crc, len, CRC32_POLY_LE);
     276                 :            : }
     277                 :            : 
     278                 :          0 : u32 __attribute_const__ __crc32c_le_shift(u32 crc, size_t len)
     279                 :            : {
     280                 :          0 :         return crc32_generic_shift(crc, len, CRC32C_POLY_LE);
     281                 :            : }
     282                 :            : EXPORT_SYMBOL(crc32_le_shift);
     283                 :            : EXPORT_SYMBOL(__crc32c_le_shift);
     284                 :            : 
     285                 :            : /**
     286                 :            :  * crc32_be_generic() - Calculate bitwise big-endian Ethernet AUTODIN II CRC32
     287                 :            :  * @crc: seed value for computation.  ~0 for Ethernet, sometimes 0 for
     288                 :            :  *      other uses, or the previous crc32 value if computing incrementally.
     289                 :            :  * @p: pointer to buffer over which CRC32 is run
     290                 :            :  * @len: length of buffer @p
     291                 :            :  * @tab: big-endian Ethernet table
     292                 :            :  * @polynomial: CRC32 BE polynomial
     293                 :            :  */
     294                 :            : static inline u32 __pure crc32_be_generic(u32 crc, unsigned char const *p,
     295                 :            :                                           size_t len, const u32 (*tab)[256],
     296                 :            :                                           u32 polynomial)
     297                 :            : {
     298                 :            : #if CRC_BE_BITS == 1
     299                 :            :         int i;
     300                 :            :         while (len--) {
     301                 :            :                 crc ^= *p++ << 24;
     302                 :            :                 for (i = 0; i < 8; i++)
     303                 :            :                         crc =
     304                 :            :                             (crc << 1) ^ ((crc & 0x80000000) ? polynomial :
     305                 :            :                                           0);
     306                 :            :         }
     307                 :            : # elif CRC_BE_BITS == 2
     308                 :            :         while (len--) {
     309                 :            :                 crc ^= *p++ << 24;
     310                 :            :                 crc = (crc << 2) ^ tab[0][crc >> 30];
     311                 :            :                 crc = (crc << 2) ^ tab[0][crc >> 30];
     312                 :            :                 crc = (crc << 2) ^ tab[0][crc >> 30];
     313                 :            :                 crc = (crc << 2) ^ tab[0][crc >> 30];
     314                 :            :         }
     315                 :            : # elif CRC_BE_BITS == 4
     316                 :            :         while (len--) {
     317                 :            :                 crc ^= *p++ << 24;
     318                 :            :                 crc = (crc << 4) ^ tab[0][crc >> 28];
     319                 :            :                 crc = (crc << 4) ^ tab[0][crc >> 28];
     320                 :            :         }
     321                 :            : # elif CRC_BE_BITS == 8
     322                 :            :         while (len--) {
     323                 :            :                 crc ^= *p++ << 24;
     324                 :            :                 crc = (crc << 8) ^ tab[0][crc >> 24];
     325                 :            :         }
     326                 :            : # else
     327                 :          3 :         crc = (__force u32) __cpu_to_be32(crc);
     328                 :          3 :         crc = crc32_body(crc, p, len, tab);
     329                 :          3 :         crc = __be32_to_cpu((__force __be32)crc);
     330                 :            : # endif
     331                 :            :         return crc;
     332                 :            : }
     333                 :            : 
     334                 :            : #if CRC_LE_BITS == 1
     335                 :            : u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
     336                 :            : {
     337                 :            :         return crc32_be_generic(crc, p, len, NULL, CRC32_POLY_BE);
     338                 :            : }
     339                 :            : #else
     340                 :          3 : u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
     341                 :            : {
     342                 :          3 :         return crc32_be_generic(crc, p, len,
     343                 :            :                         (const u32 (*)[256])crc32table_be, CRC32_POLY_BE);
     344                 :            : }
     345                 :            : #endif
     346                 :            : EXPORT_SYMBOL(crc32_be);