1 /*
2 * Copyright 2020 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 /* See https://en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks
18 * for info on the general algorithm. We use the following configuration:
19 * 32-bit CRC
20 * Polynomial = 0x04C11DB7
21 * MSB-first
22 * Input and output complement
23 * Input and output bit reversal
24 *
25 * This implementation optimizes for size and readability. We only need this for
26 * 28 bytes of A/B booting metadata, so efficiency is largely irrelevant whereas
27 * a 1KiB lookup table can be a significant cost for bootloaders.
28 */
29
30 #include "avb_util.h"
31
32 /* Lookup table for reversing 4 bits. */
33 /* clang-format off */
34 static uint8_t reverse_4bit_table[] = {
35 0x0, 0x8, 0x4, 0xC,
36 0x2, 0xA, 0x6, 0xE,
37 0x1, 0x9, 0x5, 0xD,
38 0x3, 0xB, 0x7, 0xF
39 };
40 /* clang-format on */
41
reverse_byte(uint8_t val)42 static uint8_t reverse_byte(uint8_t val) {
43 return (reverse_4bit_table[val & 0xF] << 4) | reverse_4bit_table[val >> 4];
44 }
45
reverse_uint32(uint32_t val)46 static uint32_t reverse_uint32(uint32_t val) {
47 return (reverse_byte(val) << 24) | (reverse_byte(val >> 8) << 16) |
48 (reverse_byte(val >> 16) << 8) | reverse_byte(val >> 24);
49 }
50
avb_crc32(const uint8_t * buf,size_t size)51 uint32_t avb_crc32(const uint8_t* buf, size_t size) {
52 uint32_t crc = 0xFFFFFFFF;
53
54 for (size_t i = 0; i < size; ++i) {
55 crc = crc ^ ((uint32_t)reverse_byte(buf[i]) << 24);
56 for (int j = 0; j < 8; ++j) {
57 if (crc & 0x80000000) {
58 crc = (crc << 1) ^ 0x04C11DB7;
59 } else {
60 crc <<= 1;
61 }
62 }
63 }
64
65 return reverse_uint32(~crc);
66 }
67