crc32.c revision 8b23a6c7e1aee255004dd19098d4c2462b61b849
18b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* crc32.c -- compute the CRC-32 of a data stream 28b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * Copyright (C) 1995-2005 Mark Adler 38b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * For conditions of distribution and use, see copyright notice in zlib.h 48b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * 58b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster 68b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing 78b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * tables for updating the shift register in one step with three exclusive-ors 88b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * instead of four steps with four exclusive-ors. This results in about a 98b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3. 108b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project */ 118b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 128b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* @(#) $Id$ */ 138b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 148b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* 158b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore 168b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project protection on the static variables used to control the first-use generation 178b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should 188b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project first call get_crc_table() to initialize the tables before allowing more than 198b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project one thread to use crc32(). 208b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project */ 218b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 228b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#ifdef MAKECRCH 238b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# include <stdio.h> 248b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# ifndef DYNAMIC_CRC_TABLE 258b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# define DYNAMIC_CRC_TABLE 268b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# endif /* !DYNAMIC_CRC_TABLE */ 278b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#endif /* MAKECRCH */ 288b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 298b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#include "zutil.h" /* for STDC and FAR definitions */ 308b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 318b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#define local static 328b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 338b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* Find a four-byte integer type for crc32_little() and crc32_big(). */ 348b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#ifndef NOBYFOUR 358b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# ifdef STDC /* need ANSI C limits.h to determine sizes */ 368b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# include <limits.h> 378b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# define BYFOUR 388b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# if (UINT_MAX == 0xffffffffUL) 398b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project typedef unsigned int u4; 408b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# else 418b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# if (ULONG_MAX == 0xffffffffUL) 428b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project typedef unsigned long u4; 438b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# else 448b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# if (USHRT_MAX == 0xffffffffUL) 458b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project typedef unsigned short u4; 468b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# else 478b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# undef BYFOUR /* can't find a four-byte integer type! */ 488b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# endif 498b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# endif 508b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# endif 518b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# endif /* STDC */ 528b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#endif /* !NOBYFOUR */ 538b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 548b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* Definitions for doing the crc four data bytes at a time. */ 558b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#ifdef BYFOUR 568b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \ 578b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project (((w)&0xff00)<<8)+(((w)&0xff)<<24)) 588b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project local unsigned long crc32_little OF((unsigned long, 598b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project const unsigned char FAR *, unsigned)); 608b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project local unsigned long crc32_big OF((unsigned long, 618b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project const unsigned char FAR *, unsigned)); 628b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# define TBLS 8 638b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#else 648b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# define TBLS 1 658b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#endif /* BYFOUR */ 668b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 678b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* Local functions for crc concatenation */ 688b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectlocal unsigned long gf2_matrix_times OF((unsigned long *mat, 698b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned long vec)); 708b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectlocal void gf2_matrix_square OF((unsigned long *square, unsigned long *mat)); 718b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 728b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#ifdef DYNAMIC_CRC_TABLE 738b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 748b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectlocal volatile int crc_table_empty = 1; 758b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectlocal unsigned long FAR crc_table[TBLS][256]; 768b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectlocal void make_crc_table OF((void)); 778b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#ifdef MAKECRCH 788b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project local void write_table OF((FILE *, const unsigned long FAR *)); 798b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#endif /* MAKECRCH */ 808b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* 818b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: 828b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1. 838b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 848b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project Polynomials over GF(2) are represented in binary, one bit per coefficient, 858b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project with the lowest powers in the most significant bit. Then adding polynomials 868b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project is just exclusive-or, and multiplying a polynomial by x is a right shift by 878b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project one. If we call the above polynomial p, and represent a byte as the 888b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project polynomial q, also with the lowest power in the most significant bit (so the 898b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p, 908b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project where a mod b means the remainder after dividing a by b. 918b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 928b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project This calculation is done using the shift-register method of multiplying and 938b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project taking the remainder. The register is initialized to zero, and for each 948b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project incoming bit, x^32 is added mod p to the register if the bit is a one (where 958b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by 968b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project x (which is shifting right by one and adding x^32 mod p if the bit shifted 978b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project out is a one). We start with the highest power (least significant bit) of 988b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project q and repeat for all eight bits of q. 998b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1008b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project The first table is simply the CRC of all possible eight bit values. This is 1018b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project all the information needed to generate CRCs on data a byte at a time for all 1028b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project combinations of CRC register values and incoming bytes. The remaining tables 1038b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project allow for word-at-a-time CRC calculation for both big-endian and little- 1048b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project endian machines, where a word is four bytes. 1058b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project*/ 1068b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectlocal void make_crc_table() 1078b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 1088b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned long c; 1098b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project int n, k; 1108b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned long poly; /* polynomial exclusive-or pattern */ 1118b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* terms of polynomial defining this crc (except x^32): */ 1128b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project static volatile int first = 1; /* flag to limit concurrent making */ 1138b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; 1148b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1158b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* See if another task is already doing this (not thread-safe, but better 1168b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project than nothing -- significantly reduces duration of vulnerability in 1178b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project case the advice about DYNAMIC_CRC_TABLE is ignored) */ 1188b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (first) { 1198b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project first = 0; 1208b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1218b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* make exclusive-or pattern from polynomial (0xedb88320UL) */ 1228b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project poly = 0UL; 1238b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++) 1248b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project poly |= 1UL << (31 - p[n]); 1258b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1268b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* generate a crc for every 8-bit value */ 1278b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project for (n = 0; n < 256; n++) { 1288b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project c = (unsigned long)n; 1298b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project for (k = 0; k < 8; k++) 1308b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project c = c & 1 ? poly ^ (c >> 1) : c >> 1; 1318b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project crc_table[0][n] = c; 1328b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 1338b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1348b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#ifdef BYFOUR 1358b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* generate crc for each value followed by one, two, and three zeros, 1368b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project and then the byte reversal of those as well as the first table */ 1378b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project for (n = 0; n < 256; n++) { 1388b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project c = crc_table[0][n]; 1398b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project crc_table[4][n] = REV(c); 1408b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project for (k = 1; k < 4; k++) { 1418b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project c = crc_table[0][c & 0xff] ^ (c >> 8); 1428b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project crc_table[k][n] = c; 1438b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project crc_table[k + 4][n] = REV(c); 1448b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 1458b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 1468b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#endif /* BYFOUR */ 1478b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1488b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project crc_table_empty = 0; 1498b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 1508b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project else { /* not first */ 1518b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* wait for the other guy to finish (not efficient, but rare) */ 1528b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project while (crc_table_empty) 1538b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project ; 1548b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 1558b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1568b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#ifdef MAKECRCH 1578b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* write out CRC tables to crc32.h */ 1588b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project { 1598b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project FILE *out; 1608b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1618b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project out = fopen("crc32.h", "w"); 1628b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (out == NULL) return; 1638b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n"); 1648b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project fprintf(out, " * Generated automatically by crc32.c\n */\n\n"); 1658b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project fprintf(out, "local const unsigned long FAR "); 1668b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project fprintf(out, "crc_table[TBLS][256] =\n{\n {\n"); 1678b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project write_table(out, crc_table[0]); 1688b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# ifdef BYFOUR 1698b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project fprintf(out, "#ifdef BYFOUR\n"); 1708b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project for (k = 1; k < 8; k++) { 1718b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project fprintf(out, " },\n {\n"); 1728b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project write_table(out, crc_table[k]); 1738b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 1748b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project fprintf(out, "#endif\n"); 1758b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project# endif /* BYFOUR */ 1768b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project fprintf(out, " }\n};\n"); 1778b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project fclose(out); 1788b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 1798b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#endif /* MAKECRCH */ 1808b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 1818b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1828b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#ifdef MAKECRCH 1838b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectlocal void write_table(out, table) 1848b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project FILE *out; 1858b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project const unsigned long FAR *table; 1868b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 1878b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project int n; 1888b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1898b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project for (n = 0; n < 256; n++) 1908b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", table[n], 1918b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", ")); 1928b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 1938b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#endif /* MAKECRCH */ 1948b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 1958b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#else /* !DYNAMIC_CRC_TABLE */ 1968b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* ======================================================================== 1978b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * Tables of CRC-32s of all single-byte values, made by make_crc_table(). 1988b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project */ 1998b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#include "crc32.h" 2008b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#endif /* DYNAMIC_CRC_TABLE */ 2018b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2028b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* ========================================================================= 2038b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project * This function can be used by asm versions of crc32() 2048b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project */ 2058b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectconst unsigned long FAR * ZEXPORT get_crc_table() 2068b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 2078b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#ifdef DYNAMIC_CRC_TABLE 2088b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (crc_table_empty) 2098b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project make_crc_table(); 2108b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#endif /* DYNAMIC_CRC_TABLE */ 2118b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return (const unsigned long FAR *)crc_table; 2128b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 2138b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2148b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* ========================================================================= */ 2158b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8) 2168b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1 2178b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2188b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* ========================================================================= */ 2198b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectunsigned long ZEXPORT crc32(crc, buf, len) 2208b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned long crc; 2218b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project const unsigned char FAR *buf; 2228b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned len; 2238b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 2248b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (buf == Z_NULL) return 0UL; 2258b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2268b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#ifdef DYNAMIC_CRC_TABLE 2278b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (crc_table_empty) 2288b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project make_crc_table(); 2298b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#endif /* DYNAMIC_CRC_TABLE */ 2308b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2318b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#ifdef BYFOUR 2328b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (sizeof(void *) == sizeof(ptrdiff_t)) { 2338b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project u4 endian; 2348b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2358b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project endian = 1; 2368b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (*((unsigned char *)(&endian))) 2378b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return crc32_little(crc, buf, len); 2388b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project else 2398b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return crc32_big(crc, buf, len); 2408b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2418b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#endif /* BYFOUR */ 2428b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project crc = crc ^ 0xffffffffUL; 2438b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project while (len >= 8) { 2448b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project DO8; 2458b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project len -= 8; 2468b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2478b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (len) do { 2488b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project DO1; 2498b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } while (--len); 2508b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return crc ^ 0xffffffffUL; 2518b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 2528b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2538b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#ifdef BYFOUR 2548b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2558b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* ========================================================================= */ 2568b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#define DOLIT4 c ^= *buf4++; \ 2578b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \ 2588b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24] 2598b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4 2608b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2618b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* ========================================================================= */ 2628b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectlocal unsigned long crc32_little(crc, buf, len) 2638b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned long crc; 2648b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project const unsigned char FAR *buf; 2658b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned len; 2668b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 2678b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project register u4 c; 2688b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project register const u4 FAR *buf4; 2698b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2708b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project c = (u4)crc; 2718b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project c = ~c; 2728b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project while (len && ((ptrdiff_t)buf & 3)) { 2738b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 2748b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project len--; 2758b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2768b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2778b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project buf4 = (const u4 FAR *)(const void FAR *)buf; 2788b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project while (len >= 32) { 2798b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project DOLIT32; 2808b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project len -= 32; 2818b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2828b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project while (len >= 4) { 2838b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project DOLIT4; 2848b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project len -= 4; 2858b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 2868b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project buf = (const unsigned char FAR *)buf4; 2878b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2888b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (len) do { 2898b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 2908b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } while (--len); 2918b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project c = ~c; 2928b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return (unsigned long)c; 2938b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 2948b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 2958b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* ========================================================================= */ 2968b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#define DOBIG4 c ^= *++buf4; \ 2978b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \ 2988b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24] 2998b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4 3008b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3018b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* ========================================================================= */ 3028b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectlocal unsigned long crc32_big(crc, buf, len) 3038b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned long crc; 3048b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project const unsigned char FAR *buf; 3058b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned len; 3068b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 3078b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project register u4 c; 3088b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project register const u4 FAR *buf4; 3098b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3108b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project c = REV((u4)crc); 3118b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project c = ~c; 3128b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project while (len && ((ptrdiff_t)buf & 3)) { 3138b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 3148b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project len--; 3158b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 3168b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3178b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project buf4 = (const u4 FAR *)(const void FAR *)buf; 3188b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project buf4--; 3198b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project while (len >= 32) { 3208b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project DOBIG32; 3218b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project len -= 32; 3228b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 3238b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project while (len >= 4) { 3248b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project DOBIG4; 3258b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project len -= 4; 3268b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 3278b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project buf4++; 3288b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project buf = (const unsigned char FAR *)buf4; 3298b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3308b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (len) do { 3318b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 3328b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } while (--len); 3338b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project c = ~c; 3348b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return (unsigned long)(REV(c)); 3358b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 3368b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3378b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#endif /* BYFOUR */ 3388b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3398b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project#define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */ 3408b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3418b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* ========================================================================= */ 3428b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectlocal unsigned long gf2_matrix_times(mat, vec) 3438b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned long *mat; 3448b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned long vec; 3458b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 3468b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned long sum; 3478b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3488b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project sum = 0; 3498b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project while (vec) { 3508b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (vec & 1) 3518b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project sum ^= *mat; 3528b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project vec >>= 1; 3538b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project mat++; 3548b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 3558b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return sum; 3568b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 3578b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3588b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* ========================================================================= */ 3598b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Projectlocal void gf2_matrix_square(square, mat) 3608b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned long *square; 3618b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned long *mat; 3628b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 3638b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project int n; 3648b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3658b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project for (n = 0; n < GF2_DIM; n++) 3668b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project square[n] = gf2_matrix_times(mat, mat[n]); 3678b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 3688b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3698b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project/* ========================================================================= */ 3708b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source ProjectuLong ZEXPORT crc32_combine(crc1, crc2, len2) 3718b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project uLong crc1; 3728b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project uLong crc2; 3738b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project z_off_t len2; 3748b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project{ 3758b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project int n; 3768b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned long row; 3778b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned long even[GF2_DIM]; /* even-power-of-two zeros operator */ 3788b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project unsigned long odd[GF2_DIM]; /* odd-power-of-two zeros operator */ 3798b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3808b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* degenerate case */ 3818b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (len2 == 0) 3828b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return crc1; 3838b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3848b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* put operator for one zero bit in odd */ 3858b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project odd[0] = 0xedb88320L; /* CRC-32 polynomial */ 3868b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project row = 1; 3878b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project for (n = 1; n < GF2_DIM; n++) { 3888b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project odd[n] = row; 3898b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project row <<= 1; 3908b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } 3918b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3928b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* put operator for two zero bits in even */ 3938b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project gf2_matrix_square(even, odd); 3948b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3958b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* put operator for four zero bits in odd */ 3968b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project gf2_matrix_square(odd, even); 3978b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 3988b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* apply len2 zeros to crc1 (first square will put the operator for one 3998b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project zero byte, eight zero bits, in even) */ 4008b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project do { 4018b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* apply zeros operator for this bit of len2 */ 4028b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project gf2_matrix_square(even, odd); 4038b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (len2 & 1) 4048b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project crc1 = gf2_matrix_times(even, crc1); 4058b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project len2 >>= 1; 4068b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 4078b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* if no more bits set, then done */ 4088b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (len2 == 0) 4098b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project break; 4108b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 4118b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* another iteration of the loop with odd and even swapped */ 4128b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project gf2_matrix_square(odd, even); 4138b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project if (len2 & 1) 4148b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project crc1 = gf2_matrix_times(odd, crc1); 4158b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project len2 >>= 1; 4168b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 4178b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* if no more bits set, then done */ 4188b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project } while (len2 != 0); 4198b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project 4208b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project /* return combined crc */ 4218b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project crc1 ^= crc2; 4228b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project return crc1; 4238b23a6c7e1aee255004dd19098d4c2462b61b849The Android Open Source Project} 424