From 8c3743eee739afa344139ab17d8008131555862d Mon Sep 17 00:00:00 2001 From: Rob Austein Date: Mon, 12 Sep 2016 15:59:06 -0400 Subject: CRC-32 code for use in ks_flash, stm32 DFU, possibly elsewhere. This is an open source C99 CRC-32 implementation generated by pycrc, see notes in source on copyright status and pycrc options used. crc32.c contains two different implementations of the CRC-32 algorithm with the same API, one optimized for speed, the other optimized for much smaller code space at the expense of speed. We use the fast implementation by default, but maybe the small implementation will be useful, eg, in the bootloader. Remove the extra later if this turns out to have been a waste of time. --- Makefile | 2 +- crc32.c | 143 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ hal_internal.h | 23 ++++++++++ 3 files changed, 167 insertions(+), 1 deletion(-) create mode 100644 crc32.c diff --git a/Makefile b/Makefile index a246828..d500641 100644 --- a/Makefile +++ b/Makefile @@ -74,7 +74,7 @@ endif # just "building this is harmless even if we don't use it." OBJ += errorstrings.o hash.o asn1.o ecdsa.o rsa.o xdr.o slip.o -OBJ += rpc_api.o rpc_hash.o uuid.o rpc_pkcs1.o +OBJ += rpc_api.o rpc_hash.o uuid.o rpc_pkcs1.o crc32.o # Object files to build when we're on a platform with direct access # to our hardware (Verilog) cores. diff --git a/crc32.c b/crc32.c new file mode 100644 index 0000000..417dfa8 --- /dev/null +++ b/crc32.c @@ -0,0 +1,143 @@ +/* + * crc32.c + * ------- + * CRC-32 implementation. This is internal within libhal. + * + * Copyright (c) 2016, NORDUnet A/S All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * - Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * - Neither the name of the NORDUnet nor the names of its contributors may + * be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS + * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A + * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED + * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * This code was generated by the nifty pycrc package. pycrc itself + * (well, the version used for this) is under the MIT license, but the + * author explictly disclaims ownership of the generated code, so + * we're free to do whatever we want with it. For simplicity, we've + * placed it under the same copyright we use for everything else. + * + * This file contains two different implementations of the same API, + * corresponding to different speed/size tradeoffs. These were + * generated with the commands: + * + * pycrc.py --model crc-32 --algorithm table-driven --std c99 --symbol-prefix hal_crc32_ --generate h + * pycrc.py --model crc-32 --algorithm table-driven --std c99 --symbol-prefix hal_crc32_ --generate c --table-idx-width 4 + * pycrc.py --model crc-32 --algorithm table-driven --std c99 --symbol-prefix hal_crc32_ --generate c --table-idx-width 8 + */ + +/* + * Generated on Mon Sep 12 15:36:31 2016, by pycrc v0.9, https://pycrc.org using the configuration: + * Width = 32 + * Poly = 0x04c11db7 + * Xor_In = 0xffffffff + * ReflectIn = True + * Xor_Out = 0xffffffff + * ReflectOut = True + * Algorithm = table-driven + */ + +#include "hal.h" +#include "hal_internal.h" + +#ifndef HAL_CRC32_TINY +#define HAL_CRC32_TINY 0 +#endif + +#if HAL_CRC32_TINY + +static const hal_crc32_t crc_table[16] = { + 0x00000000, 0x1db71064, 0x3b6e20c8, 0x26d930ac, 0x76dc4190, 0x6b6b51f4, 0x4db26158, 0x5005713c, + 0xedb88320, 0xf00f9344, 0xd6d6a3e8, 0xcb61b38c, 0x9b64c2b0, 0x86d3d2d4, 0xa00ae278, 0xbdbdf21c +}; + +hal_crc32_t hal_crc32_update(hal_crc32_t crc, const void *data, size_t data_len) +{ + const unsigned char *d = (const unsigned char *)data; + unsigned int tbl_idx; + + while (data_len--) { + tbl_idx = crc ^ (*d >> (0 * 4)); + crc = crc_table[tbl_idx & 0x0f] ^ (crc >> 4); + tbl_idx = crc ^ (*d >> (1 * 4)); + crc = crc_table[tbl_idx & 0x0f] ^ (crc >> 4); + + d++; + } + return crc & 0xffffffff; +} + +#else /* HAL_CRC32_TINY */ + +static const hal_crc32_t crc_table[256] = { + 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3, + 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, + 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, + 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5, + 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, + 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, + 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f, + 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, + 0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, + 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01, + 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, + 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, + 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, + 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, + 0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, + 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, + 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, + 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, + 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7, + 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, + 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, + 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79, + 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, + 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, + 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713, + 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, + 0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, + 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, + 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, + 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, + 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf, + 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d +}; + +hal_crc32_t hal_crc32_update(hal_crc32_t crc, const void *data, size_t data_len) +{ + const unsigned char *d = (const unsigned char *)data; + unsigned int tbl_idx; + + while (data_len--) { + tbl_idx = (crc ^ *d) & 0xff; + crc = (crc_table[tbl_idx] ^ (crc >> 8)) & 0xffffffff; + + d++; + } + return crc & 0xffffffff; +} + +#endif /* HAL_CRC32_TINY */ diff --git a/hal_internal.h b/hal_internal.h index 5e6b939..e92f22a 100644 --- a/hal_internal.h +++ b/hal_internal.h @@ -255,6 +255,7 @@ extern hal_error_t hal_rpc_pkcs1_construct_digestinfo(const hal_hash_handle_t ha /* * UUID stuff. All UUIDs we use (or are likely to use) are type 4 "random" UUIDs + * Some of this may need to move to hal.h. */ #define HAL_UUID_TEXT_SIZE (sizeof("00112233-4455-6677-8899-aabbccddeeff")) @@ -270,6 +271,28 @@ extern hal_error_t hal_uuid_parse(hal_uuid_t *uuid, const char * const string); extern hal_error_t hal_uuid_format(const hal_uuid_t * const uuid, char *buffer, const size_t buffer_len); +/* + * CRC-32 stuff (for flash keystore, etc). Dunno if we want a Verilog + * implementation of this, or if it would even be faster than doing it + * the main CPU taking I/O overhead and so forth into account. + * + * These prototypes were generated by pycrc.py, see notes in crc32.c. + */ + +typedef uint32_t hal_crc32_t; + +static inline hal_crc32_t hal_crc32_init(void) +{ + return 0xffffffff; +} + +extern hal_crc32_t hal_crc32_update(hal_crc32_t crc, const void *data, size_t data_len); + +static inline hal_crc32_t hal_crc32_finalize(hal_crc32_t crc) +{ + return crc ^ 0xffffffff; +} + /* * Keystore API. */ -- cgit v1.2.3