1 /* 2 * Copyright (c) 2016, Alliance for Open Media. All rights reserved 3 * 4 * This source code is subject to the terms of the BSD 2 Clause License and 5 * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License 6 * was not distributed with this source code in the LICENSE file, you can 7 * obtain it at www.aomedia.org/license/software. If the Alliance for Open 8 * Media Patent License 1.0 was not distributed with this source code in the 9 * PATENTS file, you can obtain it at www.aomedia.org/license/patent. 10 */ 11 12 #include "av1/encoder/hash.h" 13 14 static void crc_calculator_process_data(CRC_CALCULATOR *p_crc_calculator, 15 uint8_t *pData, uint32_t dataLength) { 16 for (uint32_t i = 0; i < dataLength; i++) { 17 const uint8_t index = 18 (p_crc_calculator->remainder >> (p_crc_calculator->bits - 8)) ^ 19 pData[i]; 20 p_crc_calculator->remainder <<= 8; 21 p_crc_calculator->remainder ^= p_crc_calculator->table[index]; 22 } 23 } 24 25 static void crc_calculator_reset(CRC_CALCULATOR *p_crc_calculator) { 26 p_crc_calculator->remainder = 0; 27 } 28 29 static uint32_t crc_calculator_get_crc(CRC_CALCULATOR *p_crc_calculator) { 30 return p_crc_calculator->remainder & p_crc_calculator->final_result_mask; 31 } 32 33 static void crc_calculator_init_table(CRC_CALCULATOR *p_crc_calculator) { 34 const uint32_t high_bit = 1 << (p_crc_calculator->bits - 1); 35 const uint32_t byte_high_bit = 1 << (8 - 1); 36 37 for (uint32_t value = 0; value < 256; value++) { 38 uint32_t remainder = 0; 39 for (uint8_t mask = byte_high_bit; mask != 0; mask >>= 1) { 40 if (value & mask) { 41 remainder ^= high_bit; 42 } 43 44 if (remainder & high_bit) { 45 remainder <<= 1; 46 remainder ^= p_crc_calculator->trunc_poly; 47 } else { 48 remainder <<= 1; 49 } 50 } 51 p_crc_calculator->table[value] = remainder; 52 } 53 } 54 55 void av1_crc_calculator_init(CRC_CALCULATOR *p_crc_calculator, uint32_t bits, 56 uint32_t truncPoly) { 57 p_crc_calculator->remainder = 0; 58 p_crc_calculator->bits = bits; 59 p_crc_calculator->trunc_poly = truncPoly; 60 p_crc_calculator->final_result_mask = (1 << bits) - 1; 61 crc_calculator_init_table(p_crc_calculator); 62 } 63 64 uint32_t av1_get_crc_value(void *crc_calculator, uint8_t *p, int length) { 65 CRC_CALCULATOR *p_crc_calculator = (CRC_CALCULATOR *)crc_calculator; 66 crc_calculator_reset(p_crc_calculator); 67 crc_calculator_process_data(p_crc_calculator, p, length); 68 return crc_calculator_get_crc(p_crc_calculator); 69 } 70 71 /* CRC-32C (iSCSI) polynomial in reversed bit order. */ 72 #define POLY 0x82f63b78 73 74 /* Construct table for software CRC-32C calculation. */ 75 void av1_crc32c_calculator_init(CRC32C *p_crc32c) { 76 uint32_t crc; 77 78 for (int n = 0; n < 256; n++) { 79 crc = n; 80 crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; 81 crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; 82 crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; 83 crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; 84 crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; 85 crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; 86 crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; 87 crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; 88 p_crc32c->table[0][n] = crc; 89 } 90 for (int n = 0; n < 256; n++) { 91 crc = p_crc32c->table[0][n]; 92 for (int k = 1; k < 8; k++) { 93 crc = p_crc32c->table[0][crc & 0xff] ^ (crc >> 8); 94 p_crc32c->table[k][n] = crc; 95 } 96 } 97 } 98 99 /* Table-driven software version as a fall-back. This is about 15 times slower 100 than using the hardware instructions. This assumes little-endian integers, 101 as is the case on Intel processors that the assembler code here is for. */ 102 uint32_t av1_get_crc32c_value_c(CRC32C *p, uint8_t *buf, size_t len) { 103 const uint8_t *next = (const uint8_t *)(buf); 104 uint64_t crc; 105 106 crc = 0 ^ 0xffffffff; 107 while (len && ((uintptr_t)next & 7) != 0) { 108 crc = p->table[0][(crc ^ *next++) & 0xff] ^ (crc >> 8); 109 len--; 110 } 111 while (len >= 8) { 112 crc ^= *(uint64_t *)next; 113 crc = p->table[7][crc & 0xff] ^ p->table[6][(crc >> 8) & 0xff] ^ 114 p->table[5][(crc >> 16) & 0xff] ^ p->table[4][(crc >> 24) & 0xff] ^ 115 p->table[3][(crc >> 32) & 0xff] ^ p->table[2][(crc >> 40) & 0xff] ^ 116 p->table[1][(crc >> 48) & 0xff] ^ p->table[0][crc >> 56]; 117 next += 8; 118 len -= 8; 119 } 120 while (len) { 121 crc = p->table[0][(crc ^ *next++) & 0xff] ^ (crc >> 8); 122 len--; 123 } 124 return (uint32_t)crc ^ 0xffffffff; 125 } 126