124fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin/* 224fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin * CRC32 using the polynomial from IEEE-802.3 324fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin * 424fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin * Authors: Lasse Collin <lasse.collin@tukaani.org> 524fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin * Igor Pavlov <http://7-zip.org/> 624fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin * 724fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin * This file has been put into the public domain. 824fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin * You can do whatever you want with this file. 924fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin */ 1024fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin 1124fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin/* 1224fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin * This is not the fastest implementation, but it is pretty compact. 1324fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin * The fastest versions of xz_crc32() on modern CPUs without hardware 1424fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin * accelerated CRC instruction are 3-5 times as fast as this version, 1524fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin * but they are bigger and use more memory for the lookup table. 1624fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin */ 1724fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin 1824fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin#include "xz_private.h" 1924fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin 2024fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin/* 2124fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin * STATIC_RW_DATA is used in the pre-boot environment on some architectures. 2224fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin * See <linux/decompress/mm.h> for details. 2324fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin */ 2424fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin#ifndef STATIC_RW_DATA 2524fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin# define STATIC_RW_DATA static 2624fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin#endif 2724fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin 2824fa0402a9b6a537e87e38341e78b7da86486846Lasse CollinSTATIC_RW_DATA uint32_t xz_crc32_table[256]; 2924fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin 3024fa0402a9b6a537e87e38341e78b7da86486846Lasse CollinXZ_EXTERN void xz_crc32_init(void) 3124fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin{ 3224fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin const uint32_t poly = 0xEDB88320; 3324fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin 3424fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin uint32_t i; 3524fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin uint32_t j; 3624fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin uint32_t r; 3724fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin 3824fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin for (i = 0; i < 256; ++i) { 3924fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin r = i; 4024fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin for (j = 0; j < 8; ++j) 4124fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin r = (r >> 1) ^ (poly & ~((r & 1) - 1)); 4224fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin 4324fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin xz_crc32_table[i] = r; 4424fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin } 4524fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin 4624fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin return; 4724fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin} 4824fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin 4924fa0402a9b6a537e87e38341e78b7da86486846Lasse CollinXZ_EXTERN uint32_t xz_crc32(const uint8_t *buf, size_t size, uint32_t crc) 5024fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin{ 5124fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin crc = ~crc; 5224fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin 5324fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin while (size != 0) { 5424fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin crc = xz_crc32_table[*buf++ ^ (crc & 0xFF)] ^ (crc >> 8); 5524fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin --size; 5624fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin } 5724fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin 5824fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin return ~crc; 5924fa0402a9b6a537e87e38341e78b7da86486846Lasse Collin} 60