diff options
author | Mark Adler <madler@alumni.caltech.edu> | 2018-12-26 13:50:27 -0800 |
---|---|---|
committer | Mark Adler <madler@alumni.caltech.edu> | 2018-12-26 13:50:27 -0800 |
commit | 7c0c75e990ca5395139c148f120042048b0ce091 (patch) | |
tree | a852f93466339e316d7df629ec198082f50c92b7 /crc32.c | |
parent | f8719f5ae5acdc31d3794ddfea8ac963359de41e (diff) | |
download | zlib-7c0c75e990ca5395139c148f120042048b0ce091.tar.gz |
Use atomic test and set, if available, for dynamic CRC tables.
Diffstat (limited to 'crc32.c')
-rw-r--r-- | crc32.c | 154 |
1 files changed, 112 insertions, 42 deletions
@@ -112,7 +112,6 @@ local z_crc_t x2nmodp OF((z_off64_t n, unsigned k)); #ifdef DYNAMIC_CRC_TABLE -local volatile int crc_table_empty = 1; local z_crc_t FAR crc_table[256]; local z_crc_t FAR x2n_table[32]; local void make_crc_table OF((void)); @@ -129,6 +128,94 @@ local void make_crc_table OF((void)); #endif /* MAKECRCH */ /* + Define a once() function depending on the availability of atomics. If this is + compiled with DYNAMIC_CRC_TABLE defined, and if CRCs will be computed in + multiple threads, and if atomics are not available, then get_crc_table() must + be called to initialize the tables and must return before any threads are + allowed to compute or combine CRCs. + */ + +/* Definition of once functionality. */ +typedef struct once_s once_t; +local void once OF((once_t *, void (*)(void))); + +/* Check for the availability of atomics. */ +#if defined(__STDC__) && __STDC_VERSION__ >= 201112L && \ + !defined(__STDC_NO_ATOMICS__) + +#include <stdatomic.h> + +/* Structure for once(), which must be initialized with ONCE_INIT. */ +struct once_s { + atomic_flag begun; + atomic_int done; +}; +#define ONCE_INIT {ATOMIC_FLAG_INIT, 0} + +/* + Run the provided init() function exactly once, even if multiple threads + invoke once() at the same time. The state must be a once_t initialized with + ONCE_INIT. + */ +local void once(state, init) + once_t *state; + void (*init)(void); +{ + if (!atomic_load(&state->done)) { + if (atomic_flag_test_and_set(&state->begun)) + while (!atomic_load(&state->done)) + ; + else { + init(); + atomic_store(&state->done, 1); + } + } +} + +#else /* no atomics */ + +/* Structure for once(), which must be initialized with ONCE_INIT. */ +struct once_s { + volatile int begun; + volatile int done; +}; +#define ONCE_INIT {0, 0} + +/* Test and set. Alas, not atomic, but tries to minimize the period of + vulnerability. */ +local int test_and_set OF((int volatile *)); +local int test_and_set(flag) + int volatile *flag; +{ + int was; + + was = *flag; + *flag = 1; + return was; +} + +/* Run the provided init() function once. This is not thread-safe. */ +local void once(state, init) + once_t *state; + void (*init)(void); +{ + if (!state->done) { + if (test_and_set(&state->begun)) + while (!state->done) + ; + else { + init(); + state->done = 1; + } + } +} + +#endif + +/* State for once(). */ +local once_t made = ONCE_INIT; + +/* Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: 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. @@ -155,45 +242,31 @@ local void make_crc_table OF((void)); local void make_crc_table() { + unsigned i, j, n; z_crc_t p; - static volatile int first = 1; /* flag to limit concurrent making */ - - /* See if another task is already doing this (not thread-safe, but better - than nothing -- significantly reduces duration of vulnerability in - case the advice about DYNAMIC_CRC_TABLE is ignored) */ - if (first) { - unsigned i, j, n; - first = 0; - - /* initialize the CRC of bytes tables */ - for (i = 0; i < 256; i++) { - p = i; - for (j = 0; j < 8; j++) - p = p & 1 ? (p >> 1) ^ POLY : p >> 1; - crc_table[i] = p; + + /* initialize the CRC of bytes tables */ + for (i = 0; i < 256; i++) { + p = i; + for (j = 0; j < 8; j++) + p = p & 1 ? (p >> 1) ^ POLY : p >> 1; + crc_table[i] = p; #ifdef W - crc_big_table[i] = byte_swap(p); + crc_big_table[i] = byte_swap(p); #endif - } + } + + /* initialize the x^2^n mod p(x) table */ + p = (z_crc_t)1 << 30; /* x^1 */ + x2n_table[0] = p; + for (n = 1; n < 32; n++) + x2n_table[n] = p = multmodp(p, p); - /* initialize the x^2^n mod p(x) table */ - p = (z_crc_t)1 << 30; /* x^1 */ - x2n_table[0] = p; - for (n = 1; n < 32; n++) - x2n_table[n] = p = multmodp(p, p); #ifdef W - /* initialize the braiding tables -- needs x2n_table[] */ - braid(crc_braid_table, crc_braid_big_table, N, W); + /* initialize the braiding tables -- needs x2n_table[] */ + braid(crc_braid_table, crc_braid_big_table, N, W); #endif - /* mark tables as complete, in case someone else is waiting */ - crc_table_empty = 0; - } - else { /* not first */ - /* wait for the other guy to finish (not efficient, but rare) */ - while (crc_table_empty) - ; - } #ifdef MAKECRCH { /* @@ -532,13 +605,13 @@ local z_word_t crc_word_big(data) #endif /* W */ /* ========================================================================= - * This function can be used by asm versions of crc32() + * This function can be used by asm versions of crc32(), and to force the + * generation of the CRC tables in a threaded application. */ const z_crc_t FAR * ZEXPORT get_crc_table() { #ifdef DYNAMIC_CRC_TABLE - if (crc_table_empty) - make_crc_table(); + once(&made, make_crc_table); #endif /* DYNAMIC_CRC_TABLE */ return (const z_crc_t FAR *)crc_table; } @@ -553,8 +626,7 @@ unsigned long ZEXPORT crc32_z(crc, buf, len) if (buf == Z_NULL) return 0; #ifdef DYNAMIC_CRC_TABLE - if (crc_table_empty) - make_crc_table(); + once(&made, make_crc_table); #endif /* DYNAMIC_CRC_TABLE */ /* Pre-condition the CRC */ @@ -882,8 +954,7 @@ uLong ZEXPORT crc32_combine64(crc1, crc2, len2) z_off64_t len2; { #ifdef DYNAMIC_CRC_TABLE - if (crc_table_empty) - make_crc_table(); + once(&made, make_crc_table); #endif /* DYNAMIC_CRC_TABLE */ return multmodp(x2nmodp(len2, 3), crc1) ^ crc2; } @@ -902,8 +973,7 @@ uLong ZEXPORT crc32_combine_gen64(len2) z_off64_t len2; { #ifdef DYNAMIC_CRC_TABLE - if (crc_table_empty) - make_crc_table(); + once(&made, make_crc_table); #endif /* DYNAMIC_CRC_TABLE */ return x2nmodp(len2, 3); } |