diff options
| author | Gluzskiy Alexandr <sss@sss.chaoslab.ru> | 2017-04-22 23:37:33 +0300 |
|---|---|---|
| committer | Gluzskiy Alexandr <sss@sss.chaoslab.ru> | 2017-04-23 00:19:38 +0300 |
| commit | 5048672e81f3ee9aa864ef9d736a3d74da051754 (patch) | |
| tree | 8148405d428027ceab0528cf186a9faf3817b196 /libs/libaxolotl/src | |
| parent | df4c8656be0e85a69a238f3fc3f4d53568c53828 (diff) | |
libs: libsignal-c: sync with upstream
Diffstat (limited to 'libs/libaxolotl/src')
35 files changed, 1024 insertions, 1172 deletions
diff --git a/libs/libaxolotl/src/CMakeLists.txt b/libs/libaxolotl/src/CMakeLists.txt index 54a24d0a6c..f92978850d 100644 --- a/libs/libaxolotl/src/CMakeLists.txt +++ b/libs/libaxolotl/src/CMakeLists.txt @@ -1,3 +1,7 @@ +if(BUILD_SHARED_LIBS) + find_library(M_LIB m) +endif() + include_directories( . curve25519/ed25519/nacl_includes @@ -67,6 +71,14 @@ add_library(signal-protocol-c $<TARGET_OBJECTS:protobuf-c> ) +if(BUILD_SHARED_LIBS) + target_link_libraries(signal-protocol-c ${M_LIB}) + set_target_properties(signal-protocol-c PROPERTIES + VERSION ${SIGNAL_PROTOCOL_C_VERSION} + SOVERSION ${SIGNAL_PROTOCOL_C_VERSION_MAJOR} + ) +endif() + INSTALL( FILES signal_protocol.h diff --git a/libs/libaxolotl/src/curve.c b/libs/libaxolotl/src/curve.c index 2b666376b9..afa16799e5 100755 --- a/libs/libaxolotl/src/curve.c +++ b/libs/libaxolotl/src/curve.c @@ -9,7 +9,7 @@ #include "curve25519/ed25519/additions/curve_sigs.h" #include "curve25519/ed25519/additions/vxeddsa.h" #include "signal_protocol_internal.h" -#include "utarray.h" +#include "signal_utarray.h" #define DJB_TYPE 0x05 #define DJB_KEY_LEN 32 @@ -380,45 +380,78 @@ complete: ec_public_key_list *ec_public_key_list_alloc() { + int result = 0; ec_public_key_list *list = malloc(sizeof(ec_public_key_list)); if(!list) { - return 0; + result = SG_ERR_NOMEM; + goto complete; } + memset(list, 0, sizeof(ec_public_key_list)); + utarray_new(list->values, &ut_ptr_icd); - return list; + +complete: + if(result < 0) { + if(list) { + free(list); + } + return 0; + } + else { + return list; + } } ec_public_key_list *ec_public_key_list_copy(const ec_public_key_list *list) { - ec_public_key_list *result = 0; + int result = 0; + ec_public_key_list *result_list = 0; unsigned int size; unsigned int i; ec_public_key **p; - result = ec_public_key_list_alloc(); - if(!result) { - return 0; + result_list = ec_public_key_list_alloc(); + if(!result_list) { + result = SG_ERR_NOMEM; + goto complete; } size = utarray_len(list->values); - utarray_reserve(result->values, size); + utarray_reserve(result_list->values, size); for (i = 0; i < size; i++) { p = (ec_public_key **)utarray_eltptr(list->values, i); - ec_public_key_list_push_back(result, *p); + result = ec_public_key_list_push_back(result_list, *p); + if(result < 0) { + goto complete; + } } - return result; +complete: + if(result < 0) { + if(result_list) { + ec_public_key_list_free(result_list); + } + return 0; + } + else { + return result_list; + } } -void ec_public_key_list_push_back(ec_public_key_list *list, ec_public_key *value) +int ec_public_key_list_push_back(ec_public_key_list *list, ec_public_key *value) { + int result = 0; assert(list); assert(value); - SIGNAL_REF(value); + utarray_push_back(list->values, &value); + SIGNAL_REF(value); + +complete: + return result; } unsigned int ec_public_key_list_size(const ec_public_key_list *list) diff --git a/libs/libaxolotl/src/curve.h b/libs/libaxolotl/src/curve.h index a4c4488d37..9401f88033 100644 --- a/libs/libaxolotl/src/curve.h +++ b/libs/libaxolotl/src/curve.h @@ -84,8 +84,9 @@ ec_public_key_list *ec_public_key_list_copy(const ec_public_key_list *list); * * @param list the list * @param value the value to push + * @return 0 on success, negative on failure */ -void ec_public_key_list_push_back(ec_public_key_list *list, ec_public_key *value); +int ec_public_key_list_push_back(ec_public_key_list *list, ec_public_key *value); /** * Gets the size of the list. diff --git a/libs/libaxolotl/src/curve25519/CMakeLists.txt b/libs/libaxolotl/src/curve25519/CMakeLists.txt index 54eb0944ed..63a81ff0eb 100644 --- a/libs/libaxolotl/src/curve25519/CMakeLists.txt +++ b/libs/libaxolotl/src/curve25519/CMakeLists.txt @@ -67,12 +67,11 @@ set(ed25519_SRCS ed25519/additions/curve_sigs.c ed25519/additions/elligator.c ed25519/additions/fe_isequal.c + ed25519/additions/fe_isreduced.c ed25519/additions/fe_mont_rhs.c ed25519/additions/fe_montx_to_edy.c ed25519/additions/fe_sqrt.c - ed25519/additions/ge_is_small_order.c ed25519/additions/ge_isneutral.c - ed25519/additions/ge_montx_to_p2.c ed25519/additions/ge_montx_to_p3.c ed25519/additions/ge_neg.c ed25519/additions/ge_p3_to_montx.c @@ -84,8 +83,6 @@ set(ed25519_SRCS ed25519/additions/sc_cmov.c ed25519/additions/sc_neg.c ed25519/additions/sign_modified.c - ed25519/additions/uopen_modified.c - ed25519/additions/usign_modified.c ed25519/additions/utility.c ed25519/additions/vopen_modified.c ed25519/additions/vsign_modified.c diff --git a/libs/libaxolotl/src/curve25519/ed25519/additions/crypto_additions.h b/libs/libaxolotl/src/curve25519/ed25519/additions/crypto_additions.h index da4a1cd07b..9339ddb981 100644 --- a/libs/libaxolotl/src/curve25519/ed25519/additions/crypto_additions.h +++ b/libs/libaxolotl/src/curve25519/ed25519/additions/crypto_additions.h @@ -12,11 +12,11 @@ void sc_neg(unsigned char *b, const unsigned char *a); void sc_cmov(unsigned char* f, const unsigned char* g, unsigned char b); int fe_isequal(const fe f, const fe g); +int fe_isreduced(const unsigned char* s); void fe_mont_rhs(fe v2, const fe u); void fe_montx_to_edy(fe y, const fe u); void fe_sqrt(fe b, const fe a); -int ge_is_small_order(const ge_p3 *p); int ge_isneutral(const ge_p3* q); void ge_neg(ge_p3* r, const ge_p3 *p); void ge_montx_to_p3(ge_p3* p, const fe u, const unsigned char ed_sign_bit); diff --git a/libs/libaxolotl/src/curve25519/ed25519/additions/elligator.c b/libs/libaxolotl/src/curve25519/ed25519/additions/elligator.c index 5294c86669..6feb96bad6 100644 --- a/libs/libaxolotl/src/curve25519/ed25519/additions/elligator.c +++ b/libs/libaxolotl/src/curve25519/ed25519/additions/elligator.c @@ -7,8 +7,8 @@ unsigned int legendre_is_nonsquare(fe in) { - unsigned char bytes[32]; fe temp; + unsigned char bytes[32]; fe_pow22523(temp, in); /* temp = in^((q-5)/8) */ fe_sq(temp, temp); /* in^((q-5)/4) */ fe_sq(temp, temp); /* in^((q-5)/2) */ diff --git a/libs/libaxolotl/src/curve25519/ed25519/additions/fe_isreduced.c b/libs/libaxolotl/src/curve25519/ed25519/additions/fe_isreduced.c new file mode 100644 index 0000000000..6fbb3beccd --- /dev/null +++ b/libs/libaxolotl/src/curve25519/ed25519/additions/fe_isreduced.c @@ -0,0 +1,14 @@ +#include "fe.h" +#include "crypto_verify_32.h" + +int fe_isreduced(const unsigned char* s) +{ + fe f; + unsigned char strict[32]; + + fe_frombytes(f, s); + fe_tobytes(strict, f); + if (crypto_verify_32(strict, s) != 0) + return 0; + return 1; +} diff --git a/libs/libaxolotl/src/curve25519/ed25519/additions/fe_sqrt.c b/libs/libaxolotl/src/curve25519/ed25519/additions/fe_sqrt.c index c62f064e25..a0c9785821 100644 --- a/libs/libaxolotl/src/curve25519/ed25519/additions/fe_sqrt.c +++ b/libs/libaxolotl/src/curve25519/ed25519/additions/fe_sqrt.c @@ -15,7 +15,9 @@ static unsigned char i_bytes[32] = { void fe_sqrt(fe out, const fe a) { fe exp, b, b2, bi, i; +#ifndef NDEBUG fe legendre, zero, one; +#endif fe_frombytes(i, i_bytes); fe_pow22523(exp, a); /* b = a^(q-5)/8 */ diff --git a/libs/libaxolotl/src/curve25519/ed25519/additions/ge_is_small_order.c b/libs/libaxolotl/src/curve25519/ed25519/additions/ge_is_small_order.c deleted file mode 100644 index 845941be2a..0000000000 --- a/libs/libaxolotl/src/curve25519/ed25519/additions/ge_is_small_order.c +++ /dev/null @@ -1,30 +0,0 @@ -#include "crypto_additions.h" -#include "ge.h" -#include "utility.h" -#include "stdio.h" - -/* -return 1 if f == g -return 0 if f != g -*/ - -int ge_is_small_order(const ge_p3 *p) -{ - ge_p1p1 p1p1; - ge_p2 p2; - fe zero; - - ge_p3_dbl(&p1p1, p); - ge_p1p1_to_p2(&p2, &p1p1); - - ge_p2_dbl(&p1p1, &p2); - ge_p1p1_to_p2(&p2, &p1p1); - - ge_p2_dbl(&p1p1, &p2); - ge_p1p1_to_p2(&p2, &p1p1); - - fe_0(zero); - - /* Check if 8*p == neutral element == (0, 1) */ - return (fe_isequal(p2.X, zero) & fe_isequal(p2.Y, p2.Z)); -} diff --git a/libs/libaxolotl/src/curve25519/ed25519/additions/ge_montx_to_p2.c b/libs/libaxolotl/src/curve25519/ed25519/additions/ge_montx_to_p2.c deleted file mode 100644 index d123d03580..0000000000 --- a/libs/libaxolotl/src/curve25519/ed25519/additions/ge_montx_to_p2.c +++ /dev/null @@ -1,69 +0,0 @@ -#include "fe.h" -#include "ge.h" -#include "assert.h" -#include "crypto_additions.h" -#include "utility.h" - -/* sqrt(-(A+2)) */ -static unsigned char A_bytes[32] = { - 0x06, 0x7e, 0x45, 0xff, 0xaa, 0x04, 0x6e, 0xcc, - 0x82, 0x1a, 0x7d, 0x4b, 0xd1, 0xd3, 0xa1, 0xc5, - 0x7e, 0x4f, 0xfc, 0x03, 0xdc, 0x08, 0x7b, 0xd2, - 0xbb, 0x06, 0xa0, 0x60, 0xf4, 0xed, 0x26, 0x0f -}; - -void ge_montx_to_p2(ge_p2* p, const fe u, const unsigned char ed_sign_bit) -{ - fe x, y, A, v, v2, iv, nx; - - fe_frombytes(A, A_bytes); - - /* given u, recover edwards y */ - /* given u, recover v */ - /* given u and v, recover edwards x */ - - fe_montx_to_edy(y, u); /* y = (u - 1) / (u + 1) */ - - fe_mont_rhs(v2, u); /* v^2 = u(u^2 + Au + 1) */ - fe_sqrt(v, v2); /* v = sqrt(v^2) */ - - fe_mul(x, u, A); /* x = u * sqrt(-(A+2)) */ - fe_invert(iv, v); /* 1/v */ - fe_mul(x, x, iv); /* x = (u/v) * sqrt(-(A+2)) */ - - fe_neg(nx, x); /* negate x to match sign bit */ - fe_cmov(x, nx, fe_isnegative(x) ^ ed_sign_bit); - - fe_copy(p->X, x); - fe_copy(p->Y, y); - fe_1(p->Z); - - /* POSTCONDITION: check that p->X and p->Y satisfy the Ed curve equation */ - /* -x^2 + y^2 = 1 + dx^2y^2 */ -#ifndef NDEBUG - { - fe one, d, x2, y2, x2y2, dx2y2; - - unsigned char dbytes[32] = { - 0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75, - 0xab, 0xd8, 0x41, 0x41, 0x4d, 0x0a, 0x70, 0x00, - 0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c, - 0x73, 0xfe, 0x6f, 0x2b, 0xee, 0x6c, 0x03, 0x52 - }; - - fe_frombytes(d, dbytes); - fe_1(one); - fe_sq(x2, p->X); /* x^2 */ - fe_sq(y2, p->Y); /* y^2 */ - - fe_mul(dx2y2, x2, y2); /* x^2y^2 */ - fe_mul(dx2y2, dx2y2, d); /* dx^2y^2 */ - fe_add(dx2y2, dx2y2, one); /* dx^2y^2 + 1 */ - - fe_neg(x2y2, x2); /* -x^2 */ - fe_add(x2y2, x2y2, y2); /* -x^2 + y^2 */ - - assert(fe_isequal(x2y2, dx2y2)); - } -#endif -} diff --git a/libs/libaxolotl/src/curve25519/ed25519/additions/uopen_modified.c b/libs/libaxolotl/src/curve25519/ed25519/additions/uopen_modified.c deleted file mode 100644 index 537858db6a..0000000000 --- a/libs/libaxolotl/src/curve25519/ed25519/additions/uopen_modified.c +++ /dev/null @@ -1,100 +0,0 @@ -#include <string.h> -#include "sc.h" -#include "ge.h" -#include "crypto_hash_sha512.h" -#include "crypto_verify_32.h" -#include "crypto_additions.h" -#include "crypto_sign.h" - -int crypto_usign_open_modified( - unsigned char *m,unsigned long long *mlen, - const unsigned char *sm,unsigned long long smlen, - const unsigned char *pk, const ge_p3* Bu -) -{ - ge_p3 U; - unsigned char h[64]; - unsigned char s[64]; - unsigned char strict[64]; - ge_p3 A; - ge_p2 R; - unsigned char hcheck[64]; - int count; - // Ru = sBu + h(-U) - ge_p3 sBu, hU; - ge_p3 Ru; - - if (smlen < 96) goto badsig; - if (sm[63] & 224) goto badsig; /* strict parsing of h */ - if (sm[95] & 224) goto badsig; /* strict parsing of s */ - - /* Load -A */ - if (ge_frombytes_negate_vartime(&A,pk) != 0) goto badsig; - - /* Load -U, h, s */ - ge_frombytes_negate_vartime(&U, sm); - memset(h, 0, 64); - memset(s, 0, 64); - memmove(h, sm + 32, 32); - memmove(s, sm + 64, 32); - - /* Insist that s and h are reduced scalars (strict parsing) */ - memcpy(strict, h, 64); - sc_reduce(strict); - if (memcmp(strict, h, 32) != 0) - goto badsig; - memcpy(strict, s, 64); - sc_reduce(strict); - if (memcmp(strict, s, 32) != 0) - goto badsig; - - /* Reject U (actually -U) if small order */ - if (ge_is_small_order(&U)) - goto badsig; - - // R = sB + h(-A) - ge_double_scalarmult_vartime(&R,h,&A,s); - - // sBu - ge_scalarmult(&sBu, s, Bu); - - // h(-U) - ge_scalarmult(&hU, h, &U); - - // Ru = sBu + h(-U) - { - ge_p1p1 Rp1p1; - ge_cached hUcached; - ge_p3_to_cached(&hUcached, &hU); - ge_add(&Rp1p1, &sBu, &hUcached); - ge_p1p1_to_p3(&Ru, &Rp1p1); - } - - // Check h == SHA512(label(4) || A || U || R || Ru || M) - m[0] = 0xFB; - for (count = 1; count < 32; count++) - m[count] = 0xFF; - memmove(m+32, pk, 32); - /* undo the negation for U */ - fe_neg(U.X, U.X); - fe_neg(U.T, U.T); - ge_p3_tobytes(m+64, &U); - ge_tobytes(m+96, &R); - ge_p3_tobytes(m+128, &Ru); - memmove(m+160, sm+96, smlen - 96); - - crypto_hash_sha512(hcheck, m, smlen + 64); - sc_reduce(hcheck); - - if (crypto_verify_32(hcheck, h) == 0) { - memmove(m,m + 64,smlen - 64); - memset(m + smlen - 64,0,64); - *mlen = smlen - 64; - return 0; - } - -badsig: - *mlen = -1; - memset(m,0,smlen); - return -1; -} diff --git a/libs/libaxolotl/src/curve25519/ed25519/additions/usign_modified.c b/libs/libaxolotl/src/curve25519/ed25519/additions/usign_modified.c deleted file mode 100644 index 3bbd871b7a..0000000000 --- a/libs/libaxolotl/src/curve25519/ed25519/additions/usign_modified.c +++ /dev/null @@ -1,62 +0,0 @@ -#include <string.h> -#include "crypto_sign.h" -#include "crypto_hash_sha512.h" -#include "ge.h" -#include "sc.h" -#include "zeroize.h" -#include "crypto_additions.h" - -/* NEW: Compare to pristine crypto_sign() - Uses explicit private key for nonce derivation and as scalar, - instead of deriving both from a master key. -*/ -int crypto_usign_modified( - unsigned char *sm, - const unsigned char *M,unsigned long Mlen, - const unsigned char *a, - const unsigned char *A, - const unsigned char *random, - const ge_p3 *Bu, - const unsigned char *U -) -{ - unsigned char r[64]; - unsigned char h[64]; - ge_p3 R, Ru; - int count=0; - - /* r = SHA512(label(3) || a || U || random(64)) */ - sm[0] = 0xFC; - for (count = 1; count < 32; count++) - sm[count] = 0xFF; - - memmove(sm + 32, a, 32); /* Use privkey directly for nonce derivation */ - memmove(sm + 64, U, 32); - - memmove(sm + 96, random, 64); /* Add suffix of random data */ - crypto_hash_sha512(r, sm, 160); - - sc_reduce(r); - ge_scalarmult_base(&R, r); - ge_scalarmult(&Ru, r, Bu); - - /* h = SHA512(label(4) || A || U || R || Ru || M) */ - sm[0] = 0xFB; - memmove(sm + 32, A, 32); - memmove(sm + 64, U, 32); - ge_p3_tobytes(sm+96, &R); - ge_p3_tobytes(sm+128, &Ru); - memmove(sm + 160, M, Mlen); - - crypto_hash_sha512(h, sm, Mlen + 160); - sc_reduce(h); - - memmove(sm, h, 32); /* Write h */ - sc_muladd(sm + 32, h, a, r); /* Write s */ - - /* Erase any traces of private scalar or - nonce left in the stack from sc_muladd. */ - zeroize_stack(); - zeroize(r, 64); - return 0; -} diff --git a/libs/libaxolotl/src/curve25519/ed25519/additions/vopen_modified.c b/libs/libaxolotl/src/curve25519/ed25519/additions/vopen_modified.c index 035ec0e0a3..20b85bb155 100644 --- a/libs/libaxolotl/src/curve25519/ed25519/additions/vopen_modified.c +++ b/libs/libaxolotl/src/curve25519/ed25519/additions/vopen_modified.c @@ -16,10 +16,12 @@ int crypto_vsign_open_modified( unsigned char h[32]; unsigned char s[32]; ge_p2 R; - ge_p3 Rv; unsigned char hcheck[64]; unsigned char vrf_output[64]; int count; + ge_p1p1 Rp1p1; + ge_p3 Rv; + ge_cached h_Vnegcached; if (smlen < 96) goto badsig; if (sm[63] & 224) goto badsig; /* strict parsing of h */ @@ -52,13 +54,9 @@ int crypto_vsign_open_modified( ge_scalarmult(&h_Vneg, h, &Vneg); // Rv = (sc * Bv) + (hc * (-V)) - { - ge_p1p1 Rp1p1; - ge_cached h_Vnegcached; - ge_p3_to_cached(&h_Vnegcached, &h_Vneg); - ge_add(&Rp1p1, &s_Bv, &h_Vnegcached); - ge_p1p1_to_p3(&Rv, &Rp1p1); - } + ge_p3_to_cached(&h_Vnegcached, &h_Vneg); + ge_add(&Rp1p1, &s_Bv, &h_Vnegcached); + ge_p1p1_to_p3(&Rv, &Rp1p1); // Check h == SHA512(label(4) || A || V || R || Rv || M) m[0] = 0xFB; // label 4 diff --git a/libs/libaxolotl/src/curve25519/ed25519/additions/vxeddsa.c b/libs/libaxolotl/src/curve25519/ed25519/additions/vxeddsa.c index 802a73563d..8f60169bd4 100644 --- a/libs/libaxolotl/src/curve25519/ed25519/additions/vxeddsa.c +++ b/libs/libaxolotl/src/curve25519/ed25519/additions/vxeddsa.c @@ -50,7 +50,6 @@ int vxed25519_verify(unsigned char* vrf_out, fe u; fe y; unsigned char ed_pubkey[32]; - unsigned char strict[32]; unsigned char verifybuf[MAX_MSG_LEN + 160]; /* working buffer */ unsigned char verifybuf2[MAX_MSG_LEN + 160]; /* working buffer #2 ?? !!! */ ge_p3 Bv; @@ -65,10 +64,9 @@ int vxed25519_verify(unsigned char* vrf_out, NOTE: u=-1 is converted to y=0 since fe_invert is mod-exp */ + if (!fe_isreduced(curve25519_pubkey)) + return -1; fe_frombytes(u, curve25519_pubkey); - fe_tobytes(strict, u); - if (crypto_verify_32(strict, curve25519_pubkey) != 0) - return 0; fe_montx_to_edy(y, u); fe_tobytes(ed_pubkey, y); diff --git a/libs/libaxolotl/src/curve25519/ed25519/additions/xeddsa.c b/libs/libaxolotl/src/curve25519/ed25519/additions/xeddsa.c index ee2964a0d5..63b73bf2ed 100644 --- a/libs/libaxolotl/src/curve25519/ed25519/additions/xeddsa.c +++ b/libs/libaxolotl/src/curve25519/ed25519/additions/xeddsa.c @@ -49,7 +49,6 @@ int xed25519_verify(const unsigned char* signature, fe u; fe y; unsigned char ed_pubkey[32]; - unsigned char strict[32]; unsigned char verifybuf[MAX_MSG_LEN + 64]; /* working buffer */ unsigned char verifybuf2[MAX_MSG_LEN + 64]; /* working buffer #2 */ @@ -63,10 +62,9 @@ int xed25519_verify(const unsigned char* signature, NOTE: u=-1 is converted to y=0 since fe_invert is mod-exp */ + if (!fe_isreduced(curve25519_pubkey)) + return -1; fe_frombytes(u, curve25519_pubkey); - fe_tobytes(strict, u); - if (crypto_verify_32(strict, curve25519_pubkey) != 0) - return 0; fe_montx_to_edy(y, u); fe_tobytes(ed_pubkey, y); diff --git a/libs/libaxolotl/src/curve25519/ed25519/main/main.c b/libs/libaxolotl/src/curve25519/ed25519/main/main.c index a6ff569b9e..9d6599467e 100644 --- a/libs/libaxolotl/src/curve25519/ed25519/main/main.c +++ b/libs/libaxolotl/src/curve25519/ed25519/main/main.c @@ -7,7 +7,6 @@ int main(int argc, char* argv[]) curvesigs_slow_test(0, 10000); xeddsa_slow_test(0, 10000); xeddsa_to_curvesigs_slow_test(0, 10000); - vxeddsa_slow_test(0, 10000000); - + vxeddsa_slow_test(0, 10000); return 0; } diff --git a/libs/libaxolotl/src/curve25519/ed25519/tests/tests.c b/libs/libaxolotl/src/curve25519/ed25519/tests/tests.c index 79adae5d16..a647383e71 100644 --- a/libs/libaxolotl/src/curve25519/ed25519/tests/tests.c +++ b/libs/libaxolotl/src/curve25519/ed25519/tests/tests.c @@ -55,6 +55,35 @@ int sha512_fast_test(int silent) return 0; } +int strict_fast_test(int silent) +{ + unsigned char unreduced1[32] = { + 0xFE, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x7F, + }; + unsigned char unreduced2[32] = { + 0xED, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x7F, + }; + unsigned char unreduced3[32] = { + 0xEC, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x7F, + }; + + TEST("fe_isreduced", + (fe_isreduced(unreduced1) == 0) && + (fe_isreduced(unreduced2) == 0) && + (fe_isreduced(unreduced3) == 1) + ); + return 0; +} + int elligator_fast_test(int silent) { unsigned char elligator_correct_output[32] = @@ -235,6 +264,8 @@ int xeddsa_fast_test(int silent) TEST("XEdDSA verify #1", xed25519_verify(signature, pubkey, msg, MSG_LEN) == 0); signature[0] ^= 1; TEST("XEdDSA verify #2", xed25519_verify(signature, pubkey, msg, MSG_LEN) != 0); + memset(pubkey, 0xFF, 32); + TEST("XEdDSA verify #3", xed25519_verify(signature, pubkey, msg, MSG_LEN) != 0); return 0; } @@ -276,13 +307,16 @@ int vxeddsa_fast_test(int silent) curve25519_keygen(pubkey, privkey); vxed25519_sign(signature, privkey, msg, MSG_LEN, random); - TEST("VXEdDSA sign", memcmp(signature, signature_correct, 96) == 0); TEST("VXEdDSA verify #1", vxed25519_verify(vrf_out, signature, pubkey, msg, MSG_LEN) == 0); memcpy(vrf_outprev, vrf_out, 32); signature[0] ^= 1; TEST("VXEdDSA verify #2", vxed25519_verify(vrf_out, signature, pubkey, msg, MSG_LEN) != 0); + memset(pubkey, 0xFF, 32); + TEST("VXEdDSA verify #3", vxed25519_verify(vrf_out, signature, pubkey, msg, MSG_LEN) != 0); + curve25519_keygen(pubkey, privkey); + /* Test U */ unsigned char sigprev[96]; memcpy(sigprev, signature, 96); @@ -433,7 +467,6 @@ int xeddsa_slow_test(int silent, int iterations) int xeddsa_to_curvesigs_slow_test(int silent, int iterations) { - unsigned char signature_10k_correct[64] = { 0x33, 0x50, 0xa8, 0x68, 0xcd, 0x9e, 0x74, 0x99, 0xa3, 0x5c, 0x33, 0x75, 0x2b, 0x22, 0x03, 0xf8, @@ -516,7 +549,7 @@ int vxeddsa_slow_test(int silent, int iterations) 0x43, 0x31, 0xb3, 0xac, 0x26, 0xd9, 0x76, 0xfc, 0xfe, 0x30, 0xa1, 0x7c, 0xce, 0x10, 0x67, 0x0e, }; - + /* unsigned char signature_100k_correct[96] = { 0xc9, 0x11, 0x2b, 0x55, 0xfa, 0xc4, 0xb2, 0xfe, 0x00, 0x7d, 0xf6, 0x45, 0xcb, 0xd2, 0x73, 0xc9, @@ -561,6 +594,7 @@ int vxeddsa_slow_test(int silent, int iterations) 0x7b, 0x26, 0xf2, 0xa2, 0x2b, 0x02, 0x58, 0xca, 0xbd, 0x2c, 0x2b, 0xf7, 0x77, 0x58, 0xfe, 0x09, }; + */ int count; const int MSG_LEN = 200; @@ -601,8 +635,6 @@ int vxeddsa_slow_test(int silent, int iterations) if (vxed25519_verify(vrf_out, signature, pubkey, msg, MSG_LEN) == 0) ERROR("VXEdDSA verify failure #2 %d\n", count); - if (count == 10000) - print_bytes("10K VXEdDSA", signature, 96); if (count == 100000) print_bytes("100K VXEdDSA", signature, 96); if (count == 1000000) @@ -616,6 +648,7 @@ int vxeddsa_slow_test(int silent, int iterations) if (memcmp(signature, signature_10k_correct, 96) != 0) ERROR("VXEDDSA 10K doesn't match %d\n", count); } + /* if (count == 100000) { if (memcmp(signature, signature_100k_correct, 96) != 0) ERROR("VXEDDSA 100K doesn't match %d\n", count); @@ -628,7 +661,6 @@ int vxeddsa_slow_test(int silent, int iterations) if (memcmp(signature, signature_10m_correct, 96) != 0) ERROR("VXEDDSA 10m doesn't match %d\n", count); } - /* if (count == 100000000) { if (memcmp(signature, signature_100m_correct, 96) != 0) ERROR("VXEDDSA 100m doesn't match %d\n", count); @@ -644,6 +676,8 @@ int all_fast_tests(int silent) int result; if ((result = sha512_fast_test(silent)) != 0) return result; + if ((result = strict_fast_test(silent)) != 0) + return result; if ((result = elligator_fast_test(silent)) != 0) return result; if ((result = curvesigs_fast_test(silent)) != 0) diff --git a/libs/libaxolotl/src/curve25519/ed25519/tests/tests.h b/libs/libaxolotl/src/curve25519/ed25519/tests/tests.h index 1623268bde..7ac1e503ca 100644 --- a/libs/libaxolotl/src/curve25519/ed25519/tests/tests.h +++ b/libs/libaxolotl/src/curve25519/ed25519/tests/tests.h @@ -7,6 +7,7 @@ */ int sha512_fast_test(int silent); +int strict_fast_test(int silent); int elligator_fast_test(int silent); int curvesigs_fast_test(int silent); int xeddsa_fast_test(int silent); diff --git a/libs/libaxolotl/src/device_consistency.c b/libs/libaxolotl/src/device_consistency.c index f01ed15363..4b18bc1471 100644 --- a/libs/libaxolotl/src/device_consistency.c +++ b/libs/libaxolotl/src/device_consistency.c @@ -6,7 +6,7 @@ #include "signal_protocol_internal.h" #include "curve.h" #include "WhisperTextProtocol.pb-c.h" -#include "utarray.h" +#include "signal_utarray.h" #define CODE_VERSION 0 @@ -362,7 +362,7 @@ int device_consistency_message_create_from_serialized(device_consistency_message /* Assign the message fields */ result_message->generation = message_structure->generation; - device_consistency_signature_create(&result_message->signature, + result = device_consistency_signature_create(&result_message->signature, message_structure->signature.data, message_structure->signature.len, signal_buffer_data(vrf_output_buffer), signal_buffer_len(vrf_output_buffer)); if(result < 0) { @@ -542,45 +542,78 @@ complete: device_consistency_signature_list *device_consistency_signature_list_alloc() { + int result = 0; device_consistency_signature_list *list = malloc(sizeof(device_consistency_signature_list)); if(!list) { - return 0; + result = SG_ERR_NOMEM; + goto complete; } + memset(list, 0, sizeof(device_consistency_signature_list)); + utarray_new(list->values, &ut_ptr_icd); - return list; + +complete: + if(result < 0) { + if(list) { + free(list); + } + return 0; + } + else { + return list; + } } device_consistency_signature_list *device_consistency_signature_list_copy(const device_consistency_signature_list *list) { - device_consistency_signature_list *result = 0; + int result = 0; + device_consistency_signature_list *result_list = 0; unsigned int size; unsigned int i; device_consistency_signature **p; - result = device_consistency_signature_list_alloc(); - if(!result) { - return 0; + result_list = device_consistency_signature_list_alloc(); + if(!result_list) { + result = SG_ERR_NOMEM; + goto complete; } size = utarray_len(list->values); - utarray_reserve(result->values, size); + utarray_reserve(result_list->values, size); for (i = 0; i < size; i++) { p = (device_consistency_signature **)utarray_eltptr(list->values, i); - device_consistency_signature_list_push_back(result, *p); + result = device_consistency_signature_list_push_back(result_list, *p); + if(result < 0) { + goto complete; + } } - return result; +complete: + if(result < 0) { + if(result_list) { + device_consistency_signature_list_free(result_list); + } + return 0; + } + else { + return result_list; + } } -void device_consistency_signature_list_push_back(device_consistency_signature_list *list, device_consistency_signature *value) +int device_consistency_signature_list_push_back(device_consistency_signature_list *list, device_consistency_signature *value) { + int result = 0; assert(list); assert(value); - SIGNAL_REF(value); + utarray_push_back(list->values, &value); + SIGNAL_REF(value); + +complete: + return result; } unsigned int device_consistency_signature_list_size(const device_consistency_signature_list *list) @@ -617,7 +650,7 @@ int device_consistency_signature_list_sort_comparator(const void *a, const void result = memcmp(signal_buffer_data(buf1), signal_buffer_data(buf2), len1); } else { - result = len1 - len2; + result = (int)(len1 - len2); } return result; diff --git a/libs/libaxolotl/src/device_consistency.h b/libs/libaxolotl/src/device_consistency.h index 37c683052f..379d04471c 100644 --- a/libs/libaxolotl/src/device_consistency.h +++ b/libs/libaxolotl/src/device_consistency.h @@ -48,7 +48,7 @@ int device_consistency_code_generate_for(device_consistency_commitment *commitme device_consistency_signature_list *device_consistency_signature_list_alloc(void); device_consistency_signature_list *device_consistency_signature_list_copy(const device_consistency_signature_list *list); -void device_consistency_signature_list_push_back(device_consistency_signature_list *list, device_consistency_signature *value); +int device_consistency_signature_list_push_back(device_consistency_signature_list *list, device_consistency_signature *value); unsigned int device_consistency_signature_list_size(const device_consistency_signature_list *list); device_consistency_signature *device_consistency_signature_list_at(const device_consistency_signature_list *list, unsigned int index); void device_consistency_signature_list_free(device_consistency_signature_list *list); diff --git a/libs/libaxolotl/src/group_cipher.c b/libs/libaxolotl/src/group_cipher.c index 1b6f8af2c9..05ea320d98 100644 --- a/libs/libaxolotl/src/group_cipher.c +++ b/libs/libaxolotl/src/group_cipher.c @@ -98,7 +98,7 @@ int group_cipher_encrypt(group_cipher *cipher, signing_key_private = sender_key_state_get_signing_key_private(state); if(!signing_key_private) { - result = SG_ERR_NO_SESSION; + result = SG_ERR_INVALID_KEY; goto complete; } diff --git a/libs/libaxolotl/src/group_cipher.h b/libs/libaxolotl/src/group_cipher.h index 189910d9da..2ac7e6508f 100644 --- a/libs/libaxolotl/src/group_cipher.h +++ b/libs/libaxolotl/src/group_cipher.h @@ -79,7 +79,9 @@ void group_cipher_set_decryption_callback(group_cipher *cipher, * @param padded_message_len The length of the data pointed to by padded_message * @param encrypted_message Set to a ciphertext message encrypted to the group+sender+device tuple. * - * @return SG_SUCCESS on success, negative on error + * @retval SG_SUCCESS Success + * @retval SG_ERR_NO_SESSION if there is no established session for this contact. + * @retval SG_ERR_INVALID_KEY if there is no valid private key for this session. */ int group_cipher_encrypt(group_cipher *cipher, const uint8_t *padded_plaintext, size_t padded_plaintext_len, diff --git a/libs/libaxolotl/src/protocol.c b/libs/libaxolotl/src/protocol.c index 9c8ce54c8f..c2b97344e6 100644 --- a/libs/libaxolotl/src/protocol.c +++ b/libs/libaxolotl/src/protocol.c @@ -375,7 +375,6 @@ signal_buffer *signal_message_get_body(const signal_message *message) } int signal_message_verify_mac(signal_message *message, - uint8_t message_version, ec_public_key *sender_identity_key, ec_public_key *receiver_identity_key, const uint8_t *mac_key, size_t mac_key_len, diff --git a/libs/libaxolotl/src/protocol.h b/libs/libaxolotl/src/protocol.h index 68c3a70be6..73c2df9d86 100644 --- a/libs/libaxolotl/src/protocol.h +++ b/libs/libaxolotl/src/protocol.h @@ -53,7 +53,6 @@ signal_buffer *signal_message_get_body(const signal_message *message); * @return 1 if verified, 0 if invalid, negative on error */ int signal_message_verify_mac(signal_message *message, - uint8_t message_version, ec_public_key *sender_identity_key, ec_public_key *receiver_identity_key, const uint8_t *mac_key, size_t mac_key_len, diff --git a/libs/libaxolotl/src/ratchet.c b/libs/libaxolotl/src/ratchet.c index bf65ee3e8b..83ab5a1eac 100755 --- a/libs/libaxolotl/src/ratchet.c +++ b/libs/libaxolotl/src/ratchet.c @@ -1086,16 +1086,18 @@ int ratcheting_session_alice_initialize( goto complete; } -complete: - if(result >= 0) { - session_state_set_session_version(state, CIPHERTEXT_CURRENT_VERSION); - session_state_set_remote_identity_key(state, parameters->their_identity_key); - session_state_set_local_identity_key(state, parameters->our_identity_key->public_key); - session_state_add_receiver_chain(state, parameters->their_ratchet_key, derived_chain); - session_state_set_sender_chain(state, sending_ratchet_key, sending_chain_key); - session_state_set_root_key(state, sending_chain_root); + result = session_state_add_receiver_chain(state, parameters->their_ratchet_key, derived_chain); + if(result < 0) { + goto complete; } + session_state_set_session_version(state, CIPHERTEXT_CURRENT_VERSION); + session_state_set_remote_identity_key(state, parameters->their_identity_key); + session_state_set_local_identity_key(state, parameters->our_identity_key->public_key); + session_state_set_sender_chain(state, sending_ratchet_key, sending_chain_key); + session_state_set_root_key(state, sending_chain_root); + +complete: vpool_final(&vp); if(agreement) { free(agreement); diff --git a/libs/libaxolotl/src/session_cipher.c b/libs/libaxolotl/src/session_cipher.c index 3e80788c62..3f5dcab953 100644 --- a/libs/libaxolotl/src/session_cipher.c +++ b/libs/libaxolotl/src/session_cipher.c @@ -512,7 +512,7 @@ static int session_cipher_decrypt_from_state_and_signal_message(session_cipher * goto complete; } - result = signal_message_verify_mac(ciphertext, message_version, + result = signal_message_verify_mac(ciphertext, remote_identity_key, local_identity_key, message_keys.mac_key, sizeof(message_keys.mac_key), cipher->global_context); diff --git a/libs/libaxolotl/src/signal.def b/libs/libaxolotl/src/signal.def index 0f0ef551e1..667450dca0 100755 --- a/libs/libaxolotl/src/signal.def +++ b/libs/libaxolotl/src/signal.def @@ -13,7 +13,6 @@ EXPORTS signal_buffer_free signal_buffer_bzero_free signal_buffer_list_alloc - signal_buffer_list_push signal_buffer_list_size signal_buffer_list_free signal_int_list_alloc @@ -77,3 +76,5 @@ EXPORTS curve_decode_point session_pre_key_bundle_create session_builder_process_pre_key_bundle + session_cipher_encrypt + ciphertext_message_get_serialized diff --git a/libs/libaxolotl/src/signal_protocol.c b/libs/libaxolotl/src/signal_protocol.c index 30368ae3b6..11b0c51645 100644 --- a/libs/libaxolotl/src/signal_protocol.c +++ b/libs/libaxolotl/src/signal_protocol.c @@ -8,8 +8,7 @@ #include <assert.h> #include "signal_protocol_internal.h" -#include "utlist.h" -#include "utarray.h" +#include "signal_utarray.h" #ifdef _WINDOWS #include "Windows.h" @@ -179,92 +178,174 @@ void signal_buffer_bzero_free(signal_buffer *buffer) /*------------------------------------------------------------------------*/ -typedef struct signal_buffer_list_node -{ - signal_buffer *buffer; - struct signal_buffer_list_node *next; -} signal_buffer_list_node; - struct signal_buffer_list { - int size; - signal_buffer_list_node *head; -}; - -struct signal_int_list -{ UT_array *values; }; signal_buffer_list *signal_buffer_list_alloc(void) { + int result = 0; signal_buffer_list *list = malloc(sizeof(signal_buffer_list)); - if(list) { - memset(list, 0, sizeof(signal_buffer_list)); + if(!list) { + result = SG_ERR_NOMEM; + goto complete; + } + + memset(list, 0, sizeof(signal_buffer_list)); + + utarray_new(list->values, &ut_ptr_icd); + +complete: + if(result < 0) { + if(list) { + free(list); + } + return 0; + } + else { + return list; } - return list; } -int signal_buffer_list_push(signal_buffer_list *list, signal_buffer *buffer) +signal_buffer_list *signal_buffer_list_copy(const signal_buffer_list *list) { - signal_buffer_list_node *node = 0; + int result = 0; + signal_buffer_list *result_list = 0; + signal_buffer *buffer_copy = 0; + unsigned int list_size; + unsigned int i; + + result_list = signal_buffer_list_alloc(); + if(!result_list) { + result = SG_ERR_NOMEM; + goto complete; + } - assert(list); - assert(buffer); + list_size = utarray_len(list->values); - node = malloc(sizeof(signal_buffer_list_node)); + utarray_reserve(result_list->values, list_size); - if(!node) { - return SG_ERR_NOMEM; + for(i = 0; i < list_size; i++) { + signal_buffer **buffer = (signal_buffer**)utarray_eltptr(list->values, i); + buffer_copy = signal_buffer_copy(*buffer); + utarray_push_back(list->values, &buffer_copy); + buffer_copy = 0; } - node->buffer = buffer; - LL_PREPEND(list->head, node); - list->size++; - return 0; +complete: + if(result < 0) { + signal_buffer_free(buffer_copy); + signal_buffer_list_free(result_list); + return 0; + } + else { + return result_list; + } } -int signal_buffer_list_size(signal_buffer_list *list) +int signal_buffer_list_push_back(signal_buffer_list *list, signal_buffer *buffer) { + int result = 0; assert(list); - return list->size; + utarray_push_back(list->values, &buffer); + +complete: + return result; } -void signal_buffer_list_free(signal_buffer_list *list) +unsigned int signal_buffer_list_size(signal_buffer_list *list) { - signal_buffer_list_node *cur_node; - signal_buffer_list_node *tmp_node; + assert(list); + return utarray_len(list->values); +} + +signal_buffer *signal_buffer_list_at(signal_buffer_list *list, unsigned int index) +{ + signal_buffer **value = 0; assert(list); + assert(index < utarray_len(list->values)); + + value = (signal_buffer**)utarray_eltptr(list->values, index); - LL_FOREACH_SAFE(list->head, cur_node, tmp_node) { - LL_DELETE(list->head, cur_node); - if(cur_node->buffer) { - signal_buffer_free(cur_node->buffer); + assert(*value); + + return *value; +} + +void signal_buffer_list_free(signal_buffer_list *list) +{ + unsigned int size; + unsigned int i; + signal_buffer **p; + if(list) { + size = utarray_len(list->values); + for (i = 0; i < size; i++) { + p = (signal_buffer **)utarray_eltptr(list->values, i); + signal_buffer_free(*p); } - free(cur_node); + utarray_free(list->values); + free(list); + } +} + +void signal_buffer_list_bzero_free(signal_buffer_list *list) +{ + unsigned int size; + unsigned int i; + signal_buffer **p; + if(list) { + size = utarray_len(list->values); + for (i = 0; i < size; i++) { + p = (signal_buffer **)utarray_eltptr(list->values, i); + signal_buffer_bzero_free(*p); + } + utarray_free(list->values); + free(list); } - free(list); } -signal_int_list *signal_int_list_alloc(); /*------------------------------------------------------------------------*/ +struct signal_int_list +{ + UT_array *values; +}; + signal_int_list *signal_int_list_alloc() { + int result = 0; signal_int_list *list = malloc(sizeof(signal_int_list)); if(!list) { - return 0; + result = SG_ERR_NOMEM; + goto complete; } + memset(list, 0, sizeof(signal_int_list)); + utarray_new(list->values, &ut_int_icd); - return list; + +complete: + if(result < 0) { + if(list) { + free(list); + } + return 0; + } + else { + return list; + } } -void signal_int_list_push_back(signal_int_list *list, int value) +int signal_int_list_push_back(signal_int_list *list, int value) { + int result = 0; assert(list); utarray_push_back(list->values, &value); + +complete: + return result; } unsigned int signal_int_list_size(signal_int_list *list) diff --git a/libs/libaxolotl/src/signal_protocol.h b/libs/libaxolotl/src/signal_protocol.h index 3b78a74be7..e2ff5d6812 100644 --- a/libs/libaxolotl/src/signal_protocol.h +++ b/libs/libaxolotl/src/signal_protocol.h @@ -165,13 +165,23 @@ void signal_buffer_bzero_free(signal_buffer *buffer); signal_buffer_list *signal_buffer_list_alloc(void); /** - * Push the provided buffer onto the head of the list. + * Create a copy of an existing buffer list. + * + * @param list the existing buffer list to copy + * @return pointer to the updated buffer, or 0 on failure + */ +signal_buffer_list *signal_buffer_list_copy(const signal_buffer_list *list); + +/** + * Push the provided buffer onto the end of the list. + * The list will take ownership of the buffer, and free it when the list is + * freed. * * @param list the buffer list * @param buffer the buffer to push * @return 0 on success, or negative on failure */ -int signal_buffer_list_push(signal_buffer_list *list, signal_buffer *buffer); +int signal_buffer_list_push_back(signal_buffer_list *list, signal_buffer *buffer); /** * Gets the size of the buffer list. @@ -179,7 +189,16 @@ int signal_buffer_list_push(signal_buffer_list *list, signal_buffer *buffer); * @param list the buffer list * @return the size of the list */ -int signal_buffer_list_size(signal_buffer_list *list); +unsigned int signal_buffer_list_size(signal_buffer_list *list); + +/** + * Gets the value of the element at a particular index in the list + * + * @param list the list + * @param index the index within the list + * @return the value + */ +signal_buffer *signal_buffer_list_at(signal_buffer_list *list, unsigned int index); /** * Free the buffer list, including all the buffers added to it. @@ -189,6 +208,15 @@ int signal_buffer_list_size(signal_buffer_list *list); void signal_buffer_list_free(signal_buffer_list *list); /** + * Free the buffer list, including all the buffers added to it. + * This function should be used when the buffer list contains sensitive + * data, to make sure the memory is cleared before being freed. + * + * @param list the buffer list + */ +void signal_buffer_list_bzero_free(signal_buffer_list *list); + +/** * Allocate a new int list * * @return pointer to the allocated buffer, or 0 on failure @@ -200,8 +228,9 @@ signal_int_list *signal_int_list_alloc(void); * * @param list the list * @param value the value to push + * @return 0 on success, or negative on failure */ -void signal_int_list_push_back(signal_int_list *list, int value); +int signal_int_list_push_back(signal_int_list *list, int value); /** * Gets the size of the list. diff --git a/libs/libaxolotl/src/signal_utarray.h b/libs/libaxolotl/src/signal_utarray.h new file mode 100644 index 0000000000..682fc0f0bf --- /dev/null +++ b/libs/libaxolotl/src/signal_utarray.h @@ -0,0 +1,13 @@ +#ifndef SIGNAL_UTARRAY_H +#define SIGNAL_UTARRAY_H + +#include "signal_protocol.h" + +#define oom() do { \ + result = SG_ERR_NOMEM; \ + goto complete; \ +} while(0) + +#include "utarray.h" + +#endif /* SIGNAL_UTARRAY_H */ diff --git a/libs/libaxolotl/src/utarray.h b/libs/libaxolotl/src/utarray.h index 75e9dc5ed9..979e99e98e 100644 --- a/libs/libaxolotl/src/utarray.h +++ b/libs/libaxolotl/src/utarray.h @@ -1,5 +1,5 @@ /* -Copyright (c) 2008-2014, Troy D. Hanson http://troydhanson.github.com/uthash/ +Copyright (c) 2008-2016, Troy D. Hanson http://troydhanson.github.com/uthash/ All rights reserved. Redistribution and use in source and binary forms, with or without @@ -26,7 +26,7 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #ifndef UTARRAY_H #define UTARRAY_H -#define UTARRAY_VERSION 1.9.9 +#define UTARRAY_VERSION 2.0.1 #ifdef __GNUC__ #define _UNUSED_ __attribute__ ((__unused__)) @@ -38,7 +38,9 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #include <string.h> /* memset, etc */ #include <stdlib.h> /* exit */ +#ifndef oom #define oom() exit(-1) +#endif typedef void (ctor_f)(void *dst, const void *src); typedef void (dtor_f)(void *elt); @@ -58,13 +60,13 @@ typedef struct { #define utarray_init(a,_icd) do { \ memset(a,0,sizeof(UT_array)); \ - (a)->icd=*_icd; \ + (a)->icd = *(_icd); \ } while(0) #define utarray_done(a) do { \ if ((a)->n) { \ if ((a)->icd.dtor) { \ - size_t _ut_i; \ + unsigned _ut_i; \ for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \ (a)->icd.dtor(utarray_eltptr(a,_ut_i)); \ } \ @@ -75,7 +77,8 @@ typedef struct { } while(0) #define utarray_new(a,_icd) do { \ - a=(UT_array*)malloc(sizeof(UT_array)); \ + (a) = (UT_array*)malloc(sizeof(UT_array)); \ + if ((a) == NULL) oom(); \ utarray_init(a,_icd); \ } while(0) @@ -85,9 +88,12 @@ typedef struct { } while(0) #define utarray_reserve(a,by) do { \ - if (((a)->i+by) > ((a)->n)) { \ - while(((a)->i+by) > ((a)->n)) { (a)->n = ((a)->n ? (2*(a)->n) : 8); } \ - if ( ((a)->d=(char*)realloc((a)->d, (a)->n*(a)->icd.sz)) == NULL) oom(); \ + if (((a)->i+(by)) > (a)->n) { \ + char *utarray_tmp; \ + while (((a)->i+(by)) > (a)->n) { (a)->n = ((a)->n ? (2*(a)->n) : 8); } \ + utarray_tmp=(char*)realloc((a)->d, (a)->n*(a)->icd.sz); \ + if (utarray_tmp == NULL) oom(); \ + (a)->d=utarray_tmp; \ } \ } while(0) @@ -112,10 +118,10 @@ typedef struct { #define utarray_len(a) ((a)->i) #define utarray_eltptr(a,j) (((j) < (a)->i) ? _utarray_eltptr(a,j) : NULL) -#define _utarray_eltptr(a,j) ((char*)((a)->d + ((a)->icd.sz*(j) ))) +#define _utarray_eltptr(a,j) ((a)->d + ((a)->icd.sz * (j))) #define utarray_insert(a,p,j) do { \ - if (j > (a)->i) utarray_resize(a,j); \ + if ((j) > (a)->i) utarray_resize(a,j); \ utarray_reserve(a,1); \ if ((j) < (a)->i) { \ memmove( _utarray_eltptr(a,(j)+1), _utarray_eltptr(a,j), \ @@ -128,7 +134,7 @@ typedef struct { #define utarray_inserta(a,w,j) do { \ if (utarray_len(w) == 0) break; \ - if (j > (a)->i) utarray_resize(a,j); \ + if ((j) > (a)->i) utarray_resize(a,j); \ utarray_reserve(a,utarray_len(w)); \ if ((j) < (a)->i) { \ memmove(_utarray_eltptr(a,(j)+utarray_len(w)), \ @@ -136,9 +142,9 @@ typedef struct { ((a)->i - (j))*((a)->icd.sz)); \ } \ if ((a)->icd.copy) { \ - size_t _ut_i; \ + unsigned _ut_i; \ for(_ut_i=0;_ut_i<(w)->i;_ut_i++) { \ - (a)->icd.copy(_utarray_eltptr(a,j+_ut_i), _utarray_eltptr(w,_ut_i)); \ + (a)->icd.copy(_utarray_eltptr(a, (j) + _ut_i), _utarray_eltptr(w, _ut_i)); \ } \ } else { \ memcpy(_utarray_eltptr(a,j), _utarray_eltptr(w,0), \ @@ -148,55 +154,55 @@ typedef struct { } while(0) #define utarray_resize(dst,num) do { \ - size_t _ut_i; \ - if (dst->i > (size_t)(num)) { \ + unsigned _ut_i; \ + if ((dst)->i > (unsigned)(num)) { \ if ((dst)->icd.dtor) { \ - for(_ut_i=num; _ut_i < dst->i; _ut_i++) { \ - (dst)->icd.dtor(utarray_eltptr(dst,_ut_i)); \ + for (_ut_i = (num); _ut_i < (dst)->i; ++_ut_i) { \ + (dst)->icd.dtor(_utarray_eltptr(dst, _ut_i)); \ } \ } \ - } else if (dst->i < (size_t)(num)) { \ - utarray_reserve(dst,num-dst->i); \ + } else if ((dst)->i < (unsigned)(num)) { \ + utarray_reserve(dst, (num) - (dst)->i); \ if ((dst)->icd.init) { \ - for(_ut_i=dst->i; _ut_i < num; _ut_i++) { \ - (dst)->icd.init(utarray_eltptr(dst,_ut_i)); \ + for (_ut_i = (dst)->i; _ut_i < (unsigned)(num); ++_ut_i) { \ + (dst)->icd.init(_utarray_eltptr(dst, _ut_i)); \ } \ } else { \ - memset(_utarray_eltptr(dst,dst->i),0,(dst)->icd.sz*(num-dst->i)); \ + memset(_utarray_eltptr(dst, (dst)->i), 0, (dst)->icd.sz*((num) - (dst)->i)); \ } \ } \ - dst->i = num; \ + (dst)->i = (num); \ } while(0) #define utarray_concat(dst,src) do { \ - utarray_inserta((dst),(src),utarray_len(dst)); \ + utarray_inserta(dst, src, utarray_len(dst)); \ } while(0) #define utarray_erase(a,pos,len) do { \ if ((a)->icd.dtor) { \ - size_t _ut_i; \ - for(_ut_i=0; _ut_i < len; _ut_i++) { \ - (a)->icd.dtor(utarray_eltptr((a),pos+_ut_i)); \ + unsigned _ut_i; \ + for (_ut_i = 0; _ut_i < (len); _ut_i++) { \ + (a)->icd.dtor(utarray_eltptr(a, (pos) + _ut_i)); \ } \ } \ - if ((a)->i > (pos+len)) { \ - memmove( _utarray_eltptr((a),pos), _utarray_eltptr((a),pos+len), \ - (((a)->i)-(pos+len))*((a)->icd.sz)); \ + if ((a)->i > ((pos) + (len))) { \ + memmove(_utarray_eltptr(a, pos), _utarray_eltptr(a, (pos) + (len)), \ + ((a)->i - ((pos) + (len))) * (a)->icd.sz); \ } \ (a)->i -= (len); \ } while(0) #define utarray_renew(a,u) do { \ - if (a) utarray_clear(a); \ - else utarray_new((a),(u)); \ + if (a) utarray_clear(a); \ + else utarray_new(a, u); \ } while(0) #define utarray_clear(a) do { \ if ((a)->i > 0) { \ if ((a)->icd.dtor) { \ - size_t _ut_i; \ + unsigned _ut_i; \ for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \ - (a)->icd.dtor(utarray_eltptr(a,_ut_i)); \ + (a)->icd.dtor(_utarray_eltptr(a, _ut_i)); \ } \ } \ (a)->i = 0; \ @@ -213,7 +219,7 @@ typedef struct { #define utarray_next(a,e) (((e)==NULL) ? utarray_front(a) : ((((a)->i) > (utarray_eltidx(a,e)+1)) ? _utarray_eltptr(a,utarray_eltidx(a,e)+1) : NULL)) #define utarray_prev(a,e) (((e)==NULL) ? utarray_back(a) : ((utarray_eltidx(a,e) > 0) ? _utarray_eltptr(a,utarray_eltidx(a,e)-1) : NULL)) #define utarray_back(a) (((a)->i) ? (_utarray_eltptr(a,(a)->i-1)) : NULL) -#define utarray_eltidx(a,e) (((char*)(e) >= (char*)((a)->d)) ? (((char*)(e) - (char*)((a)->d))/(size_t)(a)->icd.sz) : -1) +#define utarray_eltidx(a,e) (((char*)(e) >= (a)->d) ? (((char*)(e) - (a)->d)/(a)->icd.sz) : -1) /* last we pre-define a few icd for common utarrays of ints and strings */ static void utarray_str_cpy(void *dst, const void *src) { @@ -222,7 +228,7 @@ static void utarray_str_cpy(void *dst, const void *src) { } static void utarray_str_dtor(void *elt) { char **eltc = (char**)elt; - if (*eltc) free(*eltc); + if (*eltc != NULL) free(*eltc); } static const UT_icd ut_str_icd _UNUSED_ = {sizeof(char*),NULL,utarray_str_cpy,utarray_str_dtor}; static const UT_icd ut_int_icd _UNUSED_ = {sizeof(int),NULL,NULL,NULL}; diff --git a/libs/libaxolotl/src/uthash.h b/libs/libaxolotl/src/uthash.h index 7205c67efa..775599c9a8 100644 --- a/libs/libaxolotl/src/uthash.h +++ b/libs/libaxolotl/src/uthash.h @@ -1,5 +1,5 @@ /* -Copyright (c) 2003-2014, Troy D. Hanson http://troydhanson.github.com/uthash/ +Copyright (c) 2003-2016, Troy D. Hanson http://troydhanson.github.com/uthash/ All rights reserved. Redistribution and use in source and binary forms, with or without @@ -24,6 +24,8 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #ifndef UTHASH_H #define UTHASH_H +#define UTHASH_VERSION 2.0.1 + #include <string.h> /* memcmp,strlen */ #include <stddef.h> /* ptrdiff_t */ #include <stdlib.h> /* exit() */ @@ -51,30 +53,31 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. do { \ char **_da_dst = (char**)(&(dst)); \ *_da_dst = (char*)(src); \ -} while(0) +} while (0) #else #define DECLTYPE_ASSIGN(dst,src) \ do { \ (dst) = DECLTYPE(dst)(src); \ -} while(0) +} while (0) #endif /* a number of the hash function use uint32_t which isn't defined on Pre VS2010 */ -#if defined (_WIN32) +#if defined(_WIN32) #if defined(_MSC_VER) && _MSC_VER >= 1600 #include <stdint.h> -#elif defined(__WATCOMC__) +#elif defined(__WATCOMC__) || defined(__MINGW32__) || defined(__CYGWIN__) #include <stdint.h> #else typedef unsigned int uint32_t; typedef unsigned char uint8_t; #endif -#else +#elif defined(__GNUC__) && !defined(__VXWORKS__) #include <stdint.h> +#else +typedef unsigned int uint32_t; +typedef unsigned char uint8_t; #endif -#define UTHASH_VERSION 1.9.9 - #ifndef uthash_fatal #define uthash_fatal(msg) exit(-1) /* fatal error (out of memory,etc) */ #endif @@ -84,6 +87,12 @@ typedef unsigned char uint8_t; #ifndef uthash_free #define uthash_free(ptr,sz) free(ptr) /* free fcn */ #endif +#ifndef uthash_strlen +#define uthash_strlen(s) strlen(s) +#endif +#ifndef uthash_memcmp +#define uthash_memcmp(a,b,n) memcmp(a,b,n) +#endif #ifndef uthash_noexpand_fyi #define uthash_noexpand_fyi(tbl) /* can be defined to log noexpand */ @@ -93,29 +102,42 @@ typedef unsigned char uint8_t; #endif /* initial number of buckets */ -#define HASH_INITIAL_NUM_BUCKETS 32 /* initial number of buckets */ -#define HASH_INITIAL_NUM_BUCKETS_LOG2 5 /* lg2 of initial number of buckets */ -#define HASH_BKT_CAPACITY_THRESH 10 /* expand when bucket count reaches */ +#define HASH_INITIAL_NUM_BUCKETS 32U /* initial number of buckets */ +#define HASH_INITIAL_NUM_BUCKETS_LOG2 5U /* lg2 of initial number of buckets */ +#define HASH_BKT_CAPACITY_THRESH 10U /* expand when bucket count reaches */ -/* calculate the element whose hash handle address is hhe */ +/* calculate the element whose hash handle address is hhp */ #define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho))) +/* calculate the hash handle from element address elp */ +#define HH_FROM_ELMT(tbl,elp) ((UT_hash_handle *)(((char*)(elp)) + ((tbl)->hho))) -#define HASH_FIND(hh,head,keyptr,keylen,out) \ +#define HASH_VALUE(keyptr,keylen,hashv) \ do { \ - unsigned _hf_bkt,_hf_hashv; \ - out=NULL; \ + HASH_FCN(keyptr, keylen, hashv); \ +} while (0) + +#define HASH_FIND_BYHASHVALUE(hh,head,keyptr,keylen,hashval,out) \ +do { \ + (out) = NULL; \ if (head) { \ - HASH_FCN(keyptr,keylen, (head)->hh.tbl->num_buckets, _hf_hashv, _hf_bkt); \ - if (HASH_BLOOM_TEST((head)->hh.tbl, _hf_hashv)) { \ - HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], \ - keyptr,keylen,out); \ - } \ + unsigned _hf_bkt; \ + HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _hf_bkt); \ + if (HASH_BLOOM_TEST((head)->hh.tbl, hashval) != 0) { \ + HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], keyptr, keylen, hashval, out); \ + } \ } \ } while (0) +#define HASH_FIND(hh,head,keyptr,keylen,out) \ +do { \ + unsigned _hf_hashv; \ + HASH_VALUE(keyptr, keylen, _hf_hashv); \ + HASH_FIND_BYHASHVALUE(hh, head, keyptr, keylen, _hf_hashv, out); \ +} while (0) + #ifdef HASH_BLOOM -#define HASH_BLOOM_BITLEN (1ULL << HASH_BLOOM) -#define HASH_BLOOM_BYTELEN (HASH_BLOOM_BITLEN/8) + ((HASH_BLOOM_BITLEN%8) ? 1:0) +#define HASH_BLOOM_BITLEN (1UL << HASH_BLOOM) +#define HASH_BLOOM_BYTELEN (HASH_BLOOM_BITLEN/8UL) + (((HASH_BLOOM_BITLEN%8UL)!=0UL) ? 1UL : 0UL) #define HASH_BLOOM_MAKE(tbl) \ do { \ (tbl)->bloom_nbits = HASH_BLOOM; \ @@ -130,21 +152,21 @@ do { uthash_free((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \ } while (0) -#define HASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8] |= (1U << ((idx)%8))) -#define HASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8] & (1U << ((idx)%8))) +#define HASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8U] |= (1U << ((idx)%8U))) +#define HASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8U] & (1U << ((idx)%8U))) #define HASH_BLOOM_ADD(tbl,hashv) \ - HASH_BLOOM_BITSET((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1))) + HASH_BLOOM_BITSET((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1U))) #define HASH_BLOOM_TEST(tbl,hashv) \ - HASH_BLOOM_BITTEST((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1))) + HASH_BLOOM_BITTEST((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1U))) #else #define HASH_BLOOM_MAKE(tbl) #define HASH_BLOOM_FREE(tbl) #define HASH_BLOOM_ADD(tbl,hashv) #define HASH_BLOOM_TEST(tbl,hashv) (1) -#define HASH_BLOOM_BYTELEN 0 +#define HASH_BLOOM_BYTELEN 0U #endif #define HASH_MAKE_TABLE(hh,head) \ @@ -164,50 +186,141 @@ do { HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ HASH_BLOOM_MAKE((head)->hh.tbl); \ (head)->hh.tbl->signature = HASH_SIGNATURE; \ -} while(0) +} while (0) -#define HASH_ADD(hh,head,fieldname,keylen_in,add) \ - HASH_ADD_KEYPTR(hh,head,&((add)->fieldname),keylen_in,add) +#define HASH_REPLACE_BYHASHVALUE_INORDER(hh,head,fieldname,keylen_in,hashval,add,replaced,cmpfcn) \ +do { \ + (replaced) = NULL; \ + HASH_FIND_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, replaced); \ + if (replaced) { \ + HASH_DELETE(hh, head, replaced); \ + } \ + HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, &((add)->fieldname), keylen_in, hashval, add, cmpfcn); \ +} while (0) + +#define HASH_REPLACE_BYHASHVALUE(hh,head,fieldname,keylen_in,hashval,add,replaced) \ +do { \ + (replaced) = NULL; \ + HASH_FIND_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, replaced); \ + if (replaced) { \ + HASH_DELETE(hh, head, replaced); \ + } \ + HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, add); \ +} while (0) #define HASH_REPLACE(hh,head,fieldname,keylen_in,add,replaced) \ do { \ - replaced=NULL; \ - HASH_FIND(hh,head,&((add)->fieldname),keylen_in,replaced); \ - if (replaced!=NULL) { \ - HASH_DELETE(hh,head,replaced); \ - }; \ - HASH_ADD(hh,head,fieldname,keylen_in,add); \ -} while(0) + unsigned _hr_hashv; \ + HASH_VALUE(&((add)->fieldname), keylen_in, _hr_hashv); \ + HASH_REPLACE_BYHASHVALUE(hh, head, fieldname, keylen_in, _hr_hashv, add, replaced); \ +} while (0) + +#define HASH_REPLACE_INORDER(hh,head,fieldname,keylen_in,add,replaced,cmpfcn) \ +do { \ + unsigned _hr_hashv; \ + HASH_VALUE(&((add)->fieldname), keylen_in, _hr_hashv); \ + HASH_REPLACE_BYHASHVALUE_INORDER(hh, head, fieldname, keylen_in, _hr_hashv, add, replaced, cmpfcn); \ +} while (0) + +#define HASH_APPEND_LIST(hh, head, add) \ +do { \ + (add)->hh.next = NULL; \ + (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail); \ + (head)->hh.tbl->tail->next = (add); \ + (head)->hh.tbl->tail = &((add)->hh); \ +} while (0) + +#define HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh,head,keyptr,keylen_in,hashval,add,cmpfcn) \ +do { \ + unsigned _ha_bkt; \ + (add)->hh.hashv = (hashval); \ + (add)->hh.key = (char*) (keyptr); \ + (add)->hh.keylen = (unsigned) (keylen_in); \ + if (!(head)) { \ + (add)->hh.next = NULL; \ + (add)->hh.prev = NULL; \ + (head) = (add); \ + HASH_MAKE_TABLE(hh, head); \ + } else { \ + void *_hs_iter = (head); \ + (add)->hh.tbl = (head)->hh.tbl; \ + do { \ + if (cmpfcn(DECLTYPE(head)(_hs_iter), add) > 0) \ + break; \ + } while ((_hs_iter = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->next)); \ + if (_hs_iter) { \ + (add)->hh.next = _hs_iter; \ + if (((add)->hh.prev = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->prev)) { \ + HH_FROM_ELMT((head)->hh.tbl, (add)->hh.prev)->next = (add); \ + } else { \ + (head) = (add); \ + } \ + HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->prev = (add); \ + } else { \ + HASH_APPEND_LIST(hh, head, add); \ + } \ + } \ + (head)->hh.tbl->num_items++; \ + HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _ha_bkt); \ + HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt], &(add)->hh); \ + HASH_BLOOM_ADD((head)->hh.tbl, hashval); \ + HASH_EMIT_KEY(hh, head, keyptr, keylen_in); \ + HASH_FSCK(hh, head); \ +} while (0) + +#define HASH_ADD_KEYPTR_INORDER(hh,head,keyptr,keylen_in,add,cmpfcn) \ +do { \ + unsigned _hs_hashv; \ + HASH_VALUE(keyptr, keylen_in, _hs_hashv); \ + HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, keyptr, keylen_in, _hs_hashv, add, cmpfcn); \ +} while (0) + +#define HASH_ADD_BYHASHVALUE_INORDER(hh,head,fieldname,keylen_in,hashval,add,cmpfcn) \ + HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, &((add)->fieldname), keylen_in, hashval, add, cmpfcn) + +#define HASH_ADD_INORDER(hh,head,fieldname,keylen_in,add,cmpfcn) \ + HASH_ADD_KEYPTR_INORDER(hh, head, &((add)->fieldname), keylen_in, add, cmpfcn) + +#define HASH_ADD_KEYPTR_BYHASHVALUE(hh,head,keyptr,keylen_in,hashval,add) \ +do { \ + unsigned _ha_bkt; \ + (add)->hh.hashv = (hashval); \ + (add)->hh.key = (char*) (keyptr); \ + (add)->hh.keylen = (unsigned) (keylen_in); \ + if (!(head)) { \ + (add)->hh.next = NULL; \ + (add)->hh.prev = NULL; \ + (head) = (add); \ + HASH_MAKE_TABLE(hh, head); \ + } else { \ + (add)->hh.tbl = (head)->hh.tbl; \ + HASH_APPEND_LIST(hh, head, add); \ + } \ + (head)->hh.tbl->num_items++; \ + HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _ha_bkt); \ + HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt], &(add)->hh); \ + HASH_BLOOM_ADD((head)->hh.tbl, hashval); \ + HASH_EMIT_KEY(hh, head, keyptr, keylen_in); \ + HASH_FSCK(hh, head); \ +} while (0) #define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \ do { \ - unsigned _ha_bkt; \ - (add)->hh.next = NULL; \ - (add)->hh.key = (char*)(keyptr); \ - (add)->hh.keylen = (unsigned)(keylen_in); \ - if (!(head)) { \ - head = (add); \ - (head)->hh.prev = NULL; \ - HASH_MAKE_TABLE(hh,head); \ - } else { \ - (head)->hh.tbl->tail->next = (add); \ - (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail); \ - (head)->hh.tbl->tail = &((add)->hh); \ - } \ - (head)->hh.tbl->num_items++; \ - (add)->hh.tbl = (head)->hh.tbl; \ - HASH_FCN(keyptr,keylen_in, (head)->hh.tbl->num_buckets, \ - (add)->hh.hashv, _ha_bkt); \ - HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt],&(add)->hh); \ - HASH_BLOOM_ADD((head)->hh.tbl,(add)->hh.hashv); \ - HASH_EMIT_KEY(hh,head,keyptr,keylen_in); \ - HASH_FSCK(hh,head); \ -} while(0) + unsigned _ha_hashv; \ + HASH_VALUE(keyptr, keylen_in, _ha_hashv); \ + HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, keyptr, keylen_in, _ha_hashv, add); \ +} while (0) + +#define HASH_ADD_BYHASHVALUE(hh,head,fieldname,keylen_in,hashval,add) \ + HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, add) + +#define HASH_ADD(hh,head,fieldname,keylen_in,add) \ + HASH_ADD_KEYPTR(hh, head, &((add)->fieldname), keylen_in, add) -#define HASH_TO_BKT( hashv, num_bkts, bkt ) \ +#define HASH_TO_BKT(hashv,num_bkts,bkt) \ do { \ - bkt = ((hashv) & ((num_bkts) - 1)); \ -} while(0) + bkt = ((hashv) & ((num_bkts) - 1U)); \ +} while (0) /* delete "delptr" from the hash table. * "the usual" patch-up process for the app-order doubly-linked-list. @@ -223,7 +336,6 @@ do { */ #define HASH_DELETE(hh,head,delptr) \ do { \ - unsigned _hd_bkt; \ struct UT_hash_handle *_hd_hh_del; \ if ( ((delptr)->hh.prev == NULL) && ((delptr)->hh.next == NULL) ) { \ uthash_free((head)->hh.tbl->buckets, \ @@ -232,19 +344,20 @@ do { uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ head = NULL; \ } else { \ + unsigned _hd_bkt; \ _hd_hh_del = &((delptr)->hh); \ if ((delptr) == ELMT_FROM_HH((head)->hh.tbl,(head)->hh.tbl->tail)) { \ (head)->hh.tbl->tail = \ (UT_hash_handle*)((ptrdiff_t)((delptr)->hh.prev) + \ (head)->hh.tbl->hho); \ } \ - if ((delptr)->hh.prev) { \ + if ((delptr)->hh.prev != NULL) { \ ((UT_hash_handle*)((ptrdiff_t)((delptr)->hh.prev) + \ (head)->hh.tbl->hho))->next = (delptr)->hh.next; \ } else { \ DECLTYPE_ASSIGN(head,(delptr)->hh.next); \ } \ - if (_hd_hh_del->next) { \ + if (_hd_hh_del->next != NULL) { \ ((UT_hash_handle*)((ptrdiff_t)_hd_hh_del->next + \ (head)->hh.tbl->hho))->prev = \ _hd_hh_del->prev; \ @@ -259,11 +372,11 @@ do { /* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */ #define HASH_FIND_STR(head,findstr,out) \ - HASH_FIND(hh,head,findstr,strlen(findstr),out) + HASH_FIND(hh,head,findstr,(unsigned)uthash_strlen(findstr),out) #define HASH_ADD_STR(head,strfield,add) \ - HASH_ADD(hh,head,strfield[0],strlen(add->strfield),add) + HASH_ADD(hh,head,strfield[0],(unsigned)uthash_strlen(add->strfield),add) #define HASH_REPLACE_STR(head,strfield,add,replaced) \ - HASH_REPLACE(hh,head,strfield[0],strlen(add->strfield),add,replaced) + HASH_REPLACE(hh,head,strfield[0],(unsigned)uthash_strlen(add->strfield),add,replaced) #define HASH_FIND_INT(head,findint,out) \ HASH_FIND(hh,head,findint,sizeof(int),out) #define HASH_ADD_INT(head,intfield,add) \ @@ -286,14 +399,14 @@ do { #define HASH_OOPS(...) do { fprintf(stderr,__VA_ARGS__); exit(-1); } while (0) #define HASH_FSCK(hh,head) \ do { \ - unsigned _bkt_i; \ - unsigned _count, _bkt_count; \ - char *_prev; \ struct UT_hash_handle *_thh; \ if (head) { \ + unsigned _bkt_i; \ + unsigned _count; \ + char *_prev; \ _count = 0; \ for( _bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; _bkt_i++) { \ - _bkt_count = 0; \ + unsigned _bkt_count = 0; \ _thh = (head)->hh.tbl->buckets[_bkt_i].hh_head; \ _prev = NULL; \ while (_thh) { \ @@ -307,12 +420,12 @@ do { } \ _count += _bkt_count; \ if ((head)->hh.tbl->buckets[_bkt_i].count != _bkt_count) { \ - HASH_OOPS("invalid bucket count %d, actual %d\n", \ + HASH_OOPS("invalid bucket count %u, actual %u\n", \ (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count); \ } \ } \ if (_count != (head)->hh.tbl->num_items) { \ - HASH_OOPS("invalid hh item count %d, actual %d\n", \ + HASH_OOPS("invalid hh item count %u, actual %u\n", \ (head)->hh.tbl->num_items, _count ); \ } \ /* traverse hh in app order; check next/prev integrity, count */ \ @@ -330,7 +443,7 @@ do { (head)->hh.tbl->hho) : NULL ); \ } \ if (_count != (head)->hh.tbl->num_items) { \ - HASH_OOPS("invalid app item count %d, actual %d\n", \ + HASH_OOPS("invalid app item count %u, actual %u\n", \ (head)->hh.tbl->num_items, _count ); \ } \ } \ @@ -347,7 +460,7 @@ do { do { \ unsigned _klen = fieldlen; \ write(HASH_EMIT_KEYS, &_klen, sizeof(_klen)); \ - write(HASH_EMIT_KEYS, keyptr, fieldlen); \ + write(HASH_EMIT_KEYS, keyptr, (unsigned long)fieldlen); \ } while (0) #else #define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) @@ -361,43 +474,44 @@ do { #endif /* The Bernstein hash function, used in Perl prior to v5.6. Note (x<<5+x)=x*33. */ -#define HASH_BER(key,keylen,num_bkts,hashv,bkt) \ +#define HASH_BER(key,keylen,hashv) \ do { \ - unsigned _hb_keylen=keylen; \ - char *_hb_key=(char*)(key); \ + unsigned _hb_keylen=(unsigned)keylen; \ + const unsigned char *_hb_key=(const unsigned char*)(key); \ (hashv) = 0; \ - while (_hb_keylen--) { (hashv) = (((hashv) << 5) + (hashv)) + *_hb_key++; } \ - bkt = (hashv) & (num_bkts-1); \ + while (_hb_keylen-- != 0U) { \ + (hashv) = (((hashv) << 5) + (hashv)) + *_hb_key++; \ + } \ } while (0) /* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */ -#define HASH_SAX(key,keylen,num_bkts,hashv,bkt) \ +#define HASH_SAX(key,keylen,hashv) \ do { \ unsigned _sx_i; \ - char *_hs_key=(char*)(key); \ + const unsigned char *_hs_key=(const unsigned char*)(key); \ hashv = 0; \ - for(_sx_i=0; _sx_i < keylen; _sx_i++) \ + for(_sx_i=0; _sx_i < keylen; _sx_i++) { \ hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i]; \ - bkt = hashv & (num_bkts-1); \ + } \ } while (0) /* FNV-1a variation */ -#define HASH_FNV(key,keylen,num_bkts,hashv,bkt) \ +#define HASH_FNV(key,keylen,hashv) \ do { \ unsigned _fn_i; \ - char *_hf_key=(char*)(key); \ - hashv = 2166136261UL; \ - for(_fn_i=0; _fn_i < keylen; _fn_i++) \ + const unsigned char *_hf_key=(const unsigned char*)(key); \ + hashv = 2166136261U; \ + for(_fn_i=0; _fn_i < keylen; _fn_i++) { \ hashv = hashv ^ _hf_key[_fn_i]; \ - hashv = hashv * 16777619; \ - bkt = hashv & (num_bkts-1); \ -} while(0) + hashv = hashv * 16777619U; \ + } \ +} while (0) -#define HASH_OAT(key,keylen,num_bkts,hashv,bkt) \ +#define HASH_OAT(key,keylen,hashv) \ do { \ unsigned _ho_i; \ - char *_ho_key=(char*)(key); \ + const unsigned char *_ho_key=(const unsigned char*)(key); \ hashv = 0; \ for(_ho_i=0; _ho_i < keylen; _ho_i++) { \ hashv += _ho_key[_ho_i]; \ @@ -407,8 +521,7 @@ do { hashv += (hashv << 3); \ hashv ^= (hashv >> 11); \ hashv += (hashv << 15); \ - bkt = hashv & (num_bkts-1); \ -} while(0) +} while (0) #define HASH_JEN_MIX(a,b,c) \ do { \ @@ -423,14 +536,14 @@ do { c -= a; c -= b; c ^= ( b >> 15 ); \ } while (0) -#define HASH_JEN(key,keylen,num_bkts,hashv,bkt) \ +#define HASH_JEN(key,keylen,hashv) \ do { \ unsigned _hj_i,_hj_j,_hj_k; \ - unsigned char *_hj_key=(unsigned char*)(key); \ - hashv = 0xfeedbeef; \ - _hj_i = _hj_j = 0x9e3779b9; \ - _hj_k = (unsigned)(keylen); \ - while (_hj_k >= 12) { \ + unsigned const char *_hj_key=(unsigned const char*)(key); \ + hashv = 0xfeedbeefu; \ + _hj_i = _hj_j = 0x9e3779b9u; \ + _hj_k = (unsigned)(keylen); \ + while (_hj_k >= 12U) { \ _hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \ + ( (unsigned)_hj_key[2] << 16 ) \ + ( (unsigned)_hj_key[3] << 24 ) ); \ @@ -444,25 +557,24 @@ do { HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ \ _hj_key += 12; \ - _hj_k -= 12; \ + _hj_k -= 12U; \ } \ - hashv += keylen; \ + hashv += (unsigned)(keylen); \ switch ( _hj_k ) { \ - case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); \ - case 10: hashv += ( (unsigned)_hj_key[9] << 16 ); \ - case 9: hashv += ( (unsigned)_hj_key[8] << 8 ); \ - case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 ); \ - case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 ); \ - case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 ); \ - case 5: _hj_j += _hj_key[4]; \ - case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 ); \ - case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 ); \ - case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 ); \ + case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); /* FALLTHROUGH */ \ + case 10: hashv += ( (unsigned)_hj_key[9] << 16 ); /* FALLTHROUGH */ \ + case 9: hashv += ( (unsigned)_hj_key[8] << 8 ); /* FALLTHROUGH */ \ + case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 ); /* FALLTHROUGH */ \ + case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 ); /* FALLTHROUGH */ \ + case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 ); /* FALLTHROUGH */ \ + case 5: _hj_j += _hj_key[4]; /* FALLTHROUGH */ \ + case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 ); /* FALLTHROUGH */ \ + case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 ); /* FALLTHROUGH */ \ + case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 ); /* FALLTHROUGH */ \ case 1: _hj_i += _hj_key[0]; \ } \ HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ - bkt = hashv & (num_bkts-1); \ -} while(0) +} while (0) /* The Paul Hsieh hash function */ #undef get16bits @@ -475,21 +587,21 @@ do { #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \ +(uint32_t)(((const uint8_t *)(d))[0]) ) #endif -#define HASH_SFH(key,keylen,num_bkts,hashv,bkt) \ +#define HASH_SFH(key,keylen,hashv) \ do { \ - unsigned char *_sfh_key=(unsigned char*)(key); \ - uint32_t _sfh_tmp, _sfh_len = keylen; \ + unsigned const char *_sfh_key=(unsigned const char*)(key); \ + uint32_t _sfh_tmp, _sfh_len = (uint32_t)keylen; \ \ - int _sfh_rem = _sfh_len & 3; \ + unsigned _sfh_rem = _sfh_len & 3U; \ _sfh_len >>= 2; \ - hashv = 0xcafebabe; \ + hashv = 0xcafebabeu; \ \ /* Main loop */ \ - for (;_sfh_len > 0; _sfh_len--) { \ + for (;_sfh_len > 0U; _sfh_len--) { \ hashv += get16bits (_sfh_key); \ - _sfh_tmp = (uint32_t)(get16bits (_sfh_key+2)) << 11 ^ hashv; \ + _sfh_tmp = ((uint32_t)(get16bits (_sfh_key+2)) << 11) ^ hashv; \ hashv = (hashv << 16) ^ _sfh_tmp; \ - _sfh_key += 2*sizeof (uint16_t); \ + _sfh_key += 2U*sizeof (uint16_t); \ hashv += hashv >> 11; \ } \ \ @@ -497,7 +609,7 @@ do { switch (_sfh_rem) { \ case 3: hashv += get16bits (_sfh_key); \ hashv ^= hashv << 16; \ - hashv ^= (uint32_t)(_sfh_key[sizeof (uint16_t)] << 18); \ + hashv ^= (uint32_t)(_sfh_key[sizeof (uint16_t)]) << 18; \ hashv += hashv >> 11; \ break; \ case 2: hashv += get16bits (_sfh_key); \ @@ -516,8 +628,7 @@ do { hashv += hashv >> 17; \ hashv ^= hashv << 25; \ hashv += hashv >> 6; \ - bkt = hashv & (num_bkts-1); \ -} while(0) +} while (0) #ifdef HASH_USING_NO_STRICT_ALIASING /* The MurmurHash exploits some CPU's (x86,x86_64) tolerance for unaligned reads. @@ -532,10 +643,10 @@ do { #if (defined(__i386__) || defined(__x86_64__) || defined(_M_IX86)) #define MUR_GETBLOCK(p,i) p[i] #else /* non intel */ -#define MUR_PLUS0_ALIGNED(p) (((unsigned long)p & 0x3) == 0) -#define MUR_PLUS1_ALIGNED(p) (((unsigned long)p & 0x3) == 1) -#define MUR_PLUS2_ALIGNED(p) (((unsigned long)p & 0x3) == 2) -#define MUR_PLUS3_ALIGNED(p) (((unsigned long)p & 0x3) == 3) +#define MUR_PLUS0_ALIGNED(p) (((unsigned long)p & 3UL) == 0UL) +#define MUR_PLUS1_ALIGNED(p) (((unsigned long)p & 3UL) == 1UL) +#define MUR_PLUS2_ALIGNED(p) (((unsigned long)p & 3UL) == 2UL) +#define MUR_PLUS3_ALIGNED(p) (((unsigned long)p & 3UL) == 3UL) #define WP(p) ((uint32_t*)((unsigned long)(p) & ~3UL)) #if (defined(__BIG_ENDIAN__) || defined(SPARC) || defined(__ppc__) || defined(__ppc64__)) #define MUR_THREE_ONE(p) ((((*WP(p))&0x00ffffff) << 8) | (((*(WP(p)+1))&0xff000000) >> 24)) @@ -555,24 +666,24 @@ do { #define MUR_FMIX(_h) \ do { \ _h ^= _h >> 16; \ - _h *= 0x85ebca6b; \ + _h *= 0x85ebca6bu; \ _h ^= _h >> 13; \ - _h *= 0xc2b2ae35l; \ + _h *= 0xc2b2ae35u; \ _h ^= _h >> 16; \ -} while(0) +} while (0) -#define HASH_MUR(key,keylen,num_bkts,hashv,bkt) \ +#define HASH_MUR(key,keylen,hashv) \ do { \ const uint8_t *_mur_data = (const uint8_t*)(key); \ - const int _mur_nblocks = (keylen) / 4; \ - uint32_t _mur_h1 = 0xf88D5353; \ - uint32_t _mur_c1 = 0xcc9e2d51; \ - uint32_t _mur_c2 = 0x1b873593; \ + const int _mur_nblocks = (int)(keylen) / 4; \ + uint32_t _mur_h1 = 0xf88D5353u; \ + uint32_t _mur_c1 = 0xcc9e2d51u; \ + uint32_t _mur_c2 = 0x1b873593u; \ uint32_t _mur_k1 = 0; \ const uint8_t *_mur_tail; \ - const uint32_t *_mur_blocks = (const uint32_t*)(_mur_data+_mur_nblocks*4); \ + const uint32_t *_mur_blocks = (const uint32_t*)(_mur_data+(_mur_nblocks*4)); \ int _mur_i; \ - for(_mur_i = -_mur_nblocks; _mur_i; _mur_i++) { \ + for(_mur_i = -_mur_nblocks; _mur_i!=0; _mur_i++) { \ _mur_k1 = MUR_GETBLOCK(_mur_blocks,_mur_i); \ _mur_k1 *= _mur_c1; \ _mur_k1 = MUR_ROTL32(_mur_k1,15); \ @@ -580,42 +691,46 @@ do { \ \ _mur_h1 ^= _mur_k1; \ _mur_h1 = MUR_ROTL32(_mur_h1,13); \ - _mur_h1 = _mur_h1*5+0xe6546b64; \ + _mur_h1 = (_mur_h1*5U) + 0xe6546b64u; \ } \ - _mur_tail = (const uint8_t*)(_mur_data + _mur_nblocks*4); \ + _mur_tail = (const uint8_t*)(_mur_data + (_mur_nblocks*4)); \ _mur_k1=0; \ - switch((keylen) & 3) { \ - case 3: _mur_k1 ^= _mur_tail[2] << 16; \ - case 2: _mur_k1 ^= _mur_tail[1] << 8; \ - case 1: _mur_k1 ^= _mur_tail[0]; \ + switch((keylen) & 3U) { \ + case 3: _mur_k1 ^= (uint32_t)_mur_tail[2] << 16; /* FALLTHROUGH */ \ + case 2: _mur_k1 ^= (uint32_t)_mur_tail[1] << 8; /* FALLTHROUGH */ \ + case 1: _mur_k1 ^= (uint32_t)_mur_tail[0]; \ _mur_k1 *= _mur_c1; \ _mur_k1 = MUR_ROTL32(_mur_k1,15); \ _mur_k1 *= _mur_c2; \ _mur_h1 ^= _mur_k1; \ } \ - _mur_h1 ^= (keylen); \ + _mur_h1 ^= (uint32_t)(keylen); \ MUR_FMIX(_mur_h1); \ hashv = _mur_h1; \ - bkt = hashv & (num_bkts-1); \ -} while(0) +} while (0) #endif /* HASH_USING_NO_STRICT_ALIASING */ -/* key comparison function; return 0 if keys equal */ -#define HASH_KEYCMP(a,b,len) memcmp(a,b,len) - /* iterate over items in a known bucket to find desired item */ -#define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,out) \ +#define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,hashval,out) \ do { \ - if (head.hh_head) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,head.hh_head)); \ - else out=NULL; \ - while (out) { \ - if ((out)->hh.keylen == keylen_in) { \ - if ((HASH_KEYCMP((out)->hh.key,keyptr,keylen_in)) == 0) break; \ + if ((head).hh_head != NULL) { \ + DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (head).hh_head)); \ + } else { \ + (out) = NULL; \ + } \ + while ((out) != NULL) { \ + if ((out)->hh.hashv == (hashval) && (out)->hh.keylen == (keylen_in)) { \ + if (uthash_memcmp((out)->hh.key, keyptr, keylen_in) == 0) { \ + break; \ + } \ } \ - if ((out)->hh.hh_next) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,(out)->hh.hh_next)); \ - else out = NULL; \ - } \ -} while(0) + if ((out)->hh.hh_next != NULL) { \ + DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (out)->hh.hh_next)); \ + } else { \ + (out) = NULL; \ + } \ + } \ +} while (0) /* add an item to a bucket */ #define HASH_ADD_TO_BKT(head,addhh) \ @@ -623,13 +738,13 @@ do { head.count++; \ (addhh)->hh_next = head.hh_head; \ (addhh)->hh_prev = NULL; \ - if (head.hh_head) { (head).hh_head->hh_prev = (addhh); } \ + if (head.hh_head != NULL) { (head).hh_head->hh_prev = (addhh); } \ (head).hh_head=addhh; \ - if (head.count >= ((head.expand_mult+1) * HASH_BKT_CAPACITY_THRESH) \ - && (addhh)->tbl->noexpand != 1) { \ + if ((head.count >= ((head.expand_mult+1U) * HASH_BKT_CAPACITY_THRESH)) \ + && ((addhh)->tbl->noexpand != 1U)) { \ HASH_EXPAND_BUCKETS((addhh)->tbl); \ } \ -} while(0) +} while (0) /* remove an item from a given bucket */ #define HASH_DEL_IN_BKT(hh,head,hh_del) \ @@ -680,20 +795,20 @@ do { struct UT_hash_handle *_he_thh, *_he_hh_nxt; \ UT_hash_bucket *_he_new_buckets, *_he_newbkt; \ _he_new_buckets = (UT_hash_bucket*)uthash_malloc( \ - 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ + 2UL * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ if (!_he_new_buckets) { uthash_fatal( "out of memory"); } \ memset(_he_new_buckets, 0, \ - 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ + 2UL * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ tbl->ideal_chain_maxlen = \ - (tbl->num_items >> (tbl->log2_num_buckets+1)) + \ - ((tbl->num_items & ((tbl->num_buckets*2)-1)) ? 1 : 0); \ + (tbl->num_items >> (tbl->log2_num_buckets+1U)) + \ + (((tbl->num_items & ((tbl->num_buckets*2U)-1U)) != 0U) ? 1U : 0U); \ tbl->nonideal_items = 0; \ for(_he_bkt_i = 0; _he_bkt_i < tbl->num_buckets; _he_bkt_i++) \ { \ _he_thh = tbl->buckets[ _he_bkt_i ].hh_head; \ - while (_he_thh) { \ + while (_he_thh != NULL) { \ _he_hh_nxt = _he_thh->hh_next; \ - HASH_TO_BKT( _he_thh->hashv, tbl->num_buckets*2, _he_bkt); \ + HASH_TO_BKT( _he_thh->hashv, tbl->num_buckets*2U, _he_bkt); \ _he_newbkt = &(_he_new_buckets[ _he_bkt ]); \ if (++(_he_newbkt->count) > tbl->ideal_chain_maxlen) { \ tbl->nonideal_items++; \ @@ -702,24 +817,24 @@ do { } \ _he_thh->hh_prev = NULL; \ _he_thh->hh_next = _he_newbkt->hh_head; \ - if (_he_newbkt->hh_head) _he_newbkt->hh_head->hh_prev = \ - _he_thh; \ + if (_he_newbkt->hh_head != NULL) { _he_newbkt->hh_head->hh_prev = \ + _he_thh; } \ _he_newbkt->hh_head = _he_thh; \ _he_thh = _he_hh_nxt; \ } \ } \ uthash_free( tbl->buckets, tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \ - tbl->num_buckets *= 2; \ + tbl->num_buckets *= 2U; \ tbl->log2_num_buckets++; \ tbl->buckets = _he_new_buckets; \ tbl->ineff_expands = (tbl->nonideal_items > (tbl->num_items >> 1)) ? \ - (tbl->ineff_expands+1) : 0; \ - if (tbl->ineff_expands > 1) { \ + (tbl->ineff_expands+1U) : 0U; \ + if (tbl->ineff_expands > 1U) { \ tbl->noexpand=1; \ uthash_noexpand_fyi(tbl); \ } \ uthash_expand_fyi(tbl); \ -} while(0) +} while (0) /* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */ @@ -731,38 +846,38 @@ do { unsigned _hs_i; \ unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \ struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \ - if (head) { \ + if (head != NULL) { \ _hs_insize = 1; \ _hs_looping = 1; \ _hs_list = &((head)->hh); \ - while (_hs_looping) { \ + while (_hs_looping != 0U) { \ _hs_p = _hs_list; \ _hs_list = NULL; \ _hs_tail = NULL; \ _hs_nmerges = 0; \ - while (_hs_p) { \ + while (_hs_p != NULL) { \ _hs_nmerges++; \ _hs_q = _hs_p; \ _hs_psize = 0; \ for ( _hs_i = 0; _hs_i < _hs_insize; _hs_i++ ) { \ _hs_psize++; \ - _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ + _hs_q = (UT_hash_handle*)((_hs_q->next != NULL) ? \ ((void*)((char*)(_hs_q->next) + \ (head)->hh.tbl->hho)) : NULL); \ - if (! (_hs_q) ) break; \ + if (! (_hs_q) ) { break; } \ } \ _hs_qsize = _hs_insize; \ - while ((_hs_psize > 0) || ((_hs_qsize > 0) && _hs_q )) { \ - if (_hs_psize == 0) { \ + while ((_hs_psize > 0U) || ((_hs_qsize > 0U) && (_hs_q != NULL))) {\ + if (_hs_psize == 0U) { \ _hs_e = _hs_q; \ - _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ + _hs_q = (UT_hash_handle*)((_hs_q->next != NULL) ? \ ((void*)((char*)(_hs_q->next) + \ (head)->hh.tbl->hho)) : NULL); \ _hs_qsize--; \ - } else if ( (_hs_qsize == 0) || !(_hs_q) ) { \ + } else if ( (_hs_qsize == 0U) || (_hs_q == NULL) ) { \ _hs_e = _hs_p; \ - if (_hs_p){ \ - _hs_p = (UT_hash_handle*)((_hs_p->next) ? \ + if (_hs_p != NULL){ \ + _hs_p = (UT_hash_handle*)((_hs_p->next != NULL) ? \ ((void*)((char*)(_hs_p->next) + \ (head)->hh.tbl->hho)) : NULL); \ } \ @@ -772,42 +887,42 @@ do { DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_q))) \ ) <= 0) { \ _hs_e = _hs_p; \ - if (_hs_p){ \ - _hs_p = (UT_hash_handle*)((_hs_p->next) ? \ + if (_hs_p != NULL){ \ + _hs_p = (UT_hash_handle*)((_hs_p->next != NULL) ? \ ((void*)((char*)(_hs_p->next) + \ (head)->hh.tbl->hho)) : NULL); \ } \ _hs_psize--; \ } else { \ _hs_e = _hs_q; \ - _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ + _hs_q = (UT_hash_handle*)((_hs_q->next != NULL) ? \ ((void*)((char*)(_hs_q->next) + \ (head)->hh.tbl->hho)) : NULL); \ _hs_qsize--; \ } \ - if ( _hs_tail ) { \ - _hs_tail->next = ((_hs_e) ? \ + if ( _hs_tail != NULL ) { \ + _hs_tail->next = ((_hs_e != NULL) ? \ ELMT_FROM_HH((head)->hh.tbl,_hs_e) : NULL); \ } else { \ _hs_list = _hs_e; \ } \ - if (_hs_e) { \ - _hs_e->prev = ((_hs_tail) ? \ + if (_hs_e != NULL) { \ + _hs_e->prev = ((_hs_tail != NULL) ? \ ELMT_FROM_HH((head)->hh.tbl,_hs_tail) : NULL); \ } \ _hs_tail = _hs_e; \ } \ _hs_p = _hs_q; \ } \ - if (_hs_tail){ \ + if (_hs_tail != NULL){ \ _hs_tail->next = NULL; \ } \ - if ( _hs_nmerges <= 1 ) { \ + if ( _hs_nmerges <= 1U ) { \ _hs_looping=0; \ (head)->hh.tbl->tail = _hs_tail; \ DECLTYPE_ASSIGN(head,ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \ } \ - _hs_insize *= 2; \ + _hs_insize *= 2U; \ } \ HASH_FSCK(hh,head); \ } \ @@ -824,10 +939,10 @@ do { void *_last_elt=NULL, *_elt; \ UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \ ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \ - if (src) { \ + if (src != NULL) { \ for(_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \ for(_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \ - _src_hh; \ + _src_hh != NULL; \ _src_hh = _src_hh->hh_next) { \ _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \ if (cond(_elt)) { \ @@ -837,8 +952,8 @@ do { _dst_hh->hashv = _src_hh->hashv; \ _dst_hh->prev = _last_elt; \ _dst_hh->next = NULL; \ - if (_last_elt_hh) { _last_elt_hh->next = _elt; } \ - if (!dst) { \ + if (_last_elt_hh != NULL) { _last_elt_hh->next = _elt; } \ + if (dst == NULL) { \ DECLTYPE_ASSIGN(dst,_elt); \ HASH_MAKE_TABLE(hh_dst,dst); \ } else { \ @@ -858,34 +973,35 @@ do { #define HASH_CLEAR(hh,head) \ do { \ - if (head) { \ + if (head != NULL) { \ uthash_free((head)->hh.tbl->buckets, \ (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket)); \ HASH_BLOOM_FREE((head)->hh.tbl); \ uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ (head)=NULL; \ } \ -} while(0) +} while (0) #define HASH_OVERHEAD(hh,head) \ - (size_t)((((head)->hh.tbl->num_items * sizeof(UT_hash_handle)) + \ - ((head)->hh.tbl->num_buckets * sizeof(UT_hash_bucket)) + \ - (sizeof(UT_hash_table)) + \ - (HASH_BLOOM_BYTELEN))) + ((head != NULL) ? ( \ + (size_t)(((head)->hh.tbl->num_items * sizeof(UT_hash_handle)) + \ + ((head)->hh.tbl->num_buckets * sizeof(UT_hash_bucket)) + \ + sizeof(UT_hash_table) + \ + (HASH_BLOOM_BYTELEN))) : 0U) #ifdef NO_DECLTYPE #define HASH_ITER(hh,head,el,tmp) \ -for((el)=(head), (*(char**)(&(tmp)))=(char*)((head)?(head)->hh.next:NULL); \ - el; (el)=(tmp),(*(char**)(&(tmp)))=(char*)((tmp)?(tmp)->hh.next:NULL)) +for(((el)=(head)), ((*(char**)(&(tmp)))=(char*)((head!=NULL)?(head)->hh.next:NULL)); \ + (el) != NULL; ((el)=(tmp)), ((*(char**)(&(tmp)))=(char*)((tmp!=NULL)?(tmp)->hh.next:NULL))) #else #define HASH_ITER(hh,head,el,tmp) \ -for((el)=(head),(tmp)=DECLTYPE(el)((head)?(head)->hh.next:NULL); \ - el; (el)=(tmp),(tmp)=DECLTYPE(el)((tmp)?(tmp)->hh.next:NULL)) +for(((el)=(head)), ((tmp)=DECLTYPE(el)((head!=NULL)?(head)->hh.next:NULL)); \ + (el) != NULL; ((el)=(tmp)), ((tmp)=DECLTYPE(el)((tmp!=NULL)?(tmp)->hh.next:NULL))) #endif /* obtain a count of items in the hash */ #define HASH_COUNT(head) HASH_CNT(hh,head) -#define HASH_CNT(hh,head) ((head)?((head)->hh.tbl->num_items):0) +#define HASH_CNT(hh,head) ((head != NULL)?((head)->hh.tbl->num_items):0U) typedef struct UT_hash_bucket { struct UT_hash_handle *hh_head; @@ -908,8 +1024,8 @@ typedef struct UT_hash_bucket { } UT_hash_bucket; /* random signature used only to find hash tables in external analysis */ -#define HASH_SIGNATURE 0xa0111fe1 -#define HASH_BLOOM_SIGNATURE 0xb12220f2 +#define HASH_SIGNATURE 0xa0111fe1u +#define HASH_BLOOM_SIGNATURE 0xb12220f2u typedef struct UT_hash_table { UT_hash_bucket *buckets; @@ -939,7 +1055,7 @@ typedef struct UT_hash_table { #ifdef HASH_BLOOM uint32_t bloom_sig; /* used only to test bloom exists in external analysis */ uint8_t *bloom_bv; - char bloom_nbits; + uint8_t bloom_nbits; #endif } UT_hash_table; diff --git a/libs/libaxolotl/src/utlist.h b/libs/libaxolotl/src/utlist.h index b5f3f04c10..9b5534ffbd 100644 --- a/libs/libaxolotl/src/utlist.h +++ b/libs/libaxolotl/src/utlist.h @@ -1,5 +1,5 @@ /* -Copyright (c) 2007-2014, Troy D. Hanson http://troydhanson.github.com/uthash/ +Copyright (c) 2007-2016, Troy D. Hanson http://troydhanson.github.com/uthash/ All rights reserved. Redistribution and use in source and binary forms, with or without @@ -24,7 +24,7 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #ifndef UTLIST_H #define UTLIST_H -#define UTLIST_VERSION 1.9.9 +#define UTLIST_VERSION 2.0.1 #include <assert.h> @@ -68,11 +68,9 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #define LDECLTYPE(x) decltype(x) #else /* VS2008 or older (or VS2010 in C mode) */ #define NO_DECLTYPE -#define LDECLTYPE(x) char* #endif #elif defined(__ICCARM__) #define NO_DECLTYPE -#define LDECLTYPE(x) char* #else /* GNU, Sun and other compilers */ #define LDECLTYPE(x) __typeof(x) #endif @@ -81,6 +79,8 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * namely, we always reassign our tmp variable to the list head if we need * to dereference its prev/next pointers, and save/restore the real head.*/ #ifdef NO_DECLTYPE +#define IF_NO_DECLTYPE(x) x +#define LDECLTYPE(x) char* #define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); } #define _NEXT(elt,list,next) ((char*)((list)->next)) #define _NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); } @@ -89,6 +89,7 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; } #define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); } #else +#define IF_NO_DECLTYPE(x) #define _SV(elt,list) #define _NEXT(elt,list,next) ((elt)->next) #define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to) @@ -111,13 +112,14 @@ do { LDECLTYPE(list) _ls_q; \ LDECLTYPE(list) _ls_e; \ LDECLTYPE(list) _ls_tail; \ + IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;) \ int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ if (list) { \ _ls_insize = 1; \ _ls_looping = 1; \ while (_ls_looping) { \ _CASTASGN(_ls_p,list); \ - list = NULL; \ + (list) = NULL; \ _ls_tail = NULL; \ _ls_nmerges = 0; \ while (_ls_p) { \ @@ -174,13 +176,14 @@ do { LDECLTYPE(list) _ls_q; \ LDECLTYPE(list) _ls_e; \ LDECLTYPE(list) _ls_tail; \ + IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;) \ int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ if (list) { \ _ls_insize = 1; \ _ls_looping = 1; \ while (_ls_looping) { \ _CASTASGN(_ls_p,list); \ - list = NULL; \ + (list) = NULL; \ _ls_tail = NULL; \ _ls_nmerges = 0; \ while (_ls_p) { \ @@ -193,11 +196,11 @@ do { if (!_ls_q) break; \ } \ _ls_qsize = _ls_insize; \ - while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ + while ((_ls_psize > 0) || ((_ls_qsize > 0) && _ls_q)) { \ if (_ls_psize == 0) { \ _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ - } else if (_ls_qsize == 0 || !_ls_q) { \ + } else if ((_ls_qsize == 0) || (!_ls_q)) { \ _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ } else if (cmp(_ls_p,_ls_q) <= 0) { \ @@ -217,7 +220,7 @@ do { } \ _ls_p = _ls_q; \ } \ - _CASTASGN(list->prev, _ls_tail); \ + _CASTASGN((list)->prev, _ls_tail); \ _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \ if (_ls_nmerges <= 1) { \ _ls_looping=0; \ @@ -245,7 +248,7 @@ do { while (_ls_looping) { \ _CASTASGN(_ls_p,list); \ _CASTASGN(_ls_oldhead,list); \ - list = NULL; \ + (list) = NULL; \ _ls_tail = NULL; \ _ls_nmerges = 0; \ while (_ls_p) { \ @@ -292,7 +295,7 @@ do { } \ _ls_p = _ls_q; \ } \ - _CASTASGN(list->prev,_ls_tail); \ + _CASTASGN((list)->prev,_ls_tail); \ _CASTASGN(_tmp,list); \ _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp,next); _RS(list); \ if (_ls_nmerges <= 1) { \ @@ -311,8 +314,8 @@ do { #define LL_PREPEND2(head,add,next) \ do { \ - (add)->next = head; \ - head = add; \ + (add)->next = (head); \ + (head) = (add); \ } while (0) #define LL_CONCAT(head1,head2) \ @@ -322,7 +325,7 @@ do { do { \ LDECLTYPE(head1) _tmp; \ if (head1) { \ - _tmp = head1; \ + _tmp = (head1); \ while (_tmp->next) { _tmp = _tmp->next; } \ _tmp->next=(head2); \ } else { \ @@ -338,7 +341,7 @@ do { LDECLTYPE(head) _tmp; \ (add)->next=NULL; \ if (head) { \ - _tmp = head; \ + _tmp = (head); \ while (_tmp->next) { _tmp = _tmp->next; } \ _tmp->next=(add); \ } else { \ @@ -355,87 +358,36 @@ do { if ((head) == (del)) { \ (head)=(head)->next; \ } else { \ - _tmp = head; \ + _tmp = (head); \ while (_tmp->next && (_tmp->next != (del))) { \ _tmp = _tmp->next; \ } \ if (_tmp->next) { \ - _tmp->next = ((del)->next); \ - } \ - } \ -} while (0) - -/* Here are VS2008 replacements for LL_APPEND and LL_DELETE */ -#define LL_APPEND_VS2008(head,add) \ - LL_APPEND2_VS2008(head,add,next) - -#define LL_APPEND2_VS2008(head,add,next) \ -do { \ - if (head) { \ - (add)->next = head; /* use add->next as a temp variable */ \ - while ((add)->next->next) { (add)->next = (add)->next->next; } \ - (add)->next->next=(add); \ - } else { \ - (head)=(add); \ - } \ - (add)->next=NULL; \ -} while (0) - -#define LL_DELETE_VS2008(head,del) \ - LL_DELETE2_VS2008(head,del,next) - -#define LL_DELETE2_VS2008(head,del,next) \ -do { \ - if ((head) == (del)) { \ - (head)=(head)->next; \ - } else { \ - char *_tmp = (char*)(head); \ - while ((head)->next && ((head)->next != (del))) { \ - head = (head)->next; \ - } \ - if ((head)->next) { \ - (head)->next = ((del)->next); \ - } \ - { \ - char **_head_alias = (char**)&(head); \ - *_head_alias = _tmp; \ + _tmp->next = (del)->next; \ } \ } \ } while (0) -#ifdef NO_DECLTYPE -#undef LL_APPEND -#define LL_APPEND LL_APPEND_VS2008 -#undef LL_DELETE -#define LL_DELETE LL_DELETE_VS2008 -#undef LL_DELETE2 -#define LL_DELETE2 LL_DELETE2_VS2008 -#undef LL_APPEND2 -#define LL_APPEND2 LL_APPEND2_VS2008 -#undef LL_CONCAT /* no LL_CONCAT_VS2008 */ -#undef DL_CONCAT /* no DL_CONCAT_VS2008 */ -#endif -/* end VS2008 replacements */ #define LL_COUNT(head,el,counter) \ LL_COUNT2(head,el,counter,next) \ #define LL_COUNT2(head,el,counter,next) \ -{ \ - counter = 0; \ - LL_FOREACH2(head,el,next){ ++counter; } \ -} +do { \ + (counter) = 0; \ + LL_FOREACH2(head,el,next) { ++(counter); } \ +} while (0) #define LL_FOREACH(head,el) \ LL_FOREACH2(head,el,next) #define LL_FOREACH2(head,el,next) \ - for(el=head;el;el=(el)->next) + for ((el) = (head); el; (el) = (el)->next) #define LL_FOREACH_SAFE(head,el,tmp) \ LL_FOREACH_SAFE2(head,el,tmp,next) #define LL_FOREACH_SAFE2(head,el,tmp,next) \ - for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) + for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp)) #define LL_SEARCH_SCALAR(head,out,field,val) \ LL_SEARCH_SCALAR2(head,out,field,val,next) @@ -445,7 +397,7 @@ do { LL_FOREACH2(head,out,next) { \ if ((out)->field == (val)) break; \ } \ -} while(0) +} while (0) #define LL_SEARCH(head,out,elt,cmp) \ LL_SEARCH2(head,out,elt,cmp,next) @@ -455,19 +407,19 @@ do { LL_FOREACH2(head,out,next) { \ if ((cmp(out,elt))==0) break; \ } \ -} while(0) +} while (0) -#define LL_REPLACE_ELEM(head, el, add) \ +#define LL_REPLACE_ELEM2(head, el, add, next) \ do { \ LDECLTYPE(head) _tmp; \ - assert(head != NULL); \ - assert(el != NULL); \ - assert(add != NULL); \ + assert((head) != NULL); \ + assert((el) != NULL); \ + assert((add) != NULL); \ (add)->next = (el)->next; \ if ((head) == (el)) { \ (head) = (add); \ } else { \ - _tmp = head; \ + _tmp = (head); \ while (_tmp->next && (_tmp->next != (el))) { \ _tmp = _tmp->next; \ } \ @@ -477,26 +429,141 @@ do { } \ } while (0) +#define LL_REPLACE_ELEM(head, el, add) \ + LL_REPLACE_ELEM2(head, el, add, next) + +#define LL_PREPEND_ELEM2(head, el, add, next) \ +do { \ + if (el) { \ + LDECLTYPE(head) _tmp; \ + assert((head) != NULL); \ + assert((add) != NULL); \ + (add)->next = (el); \ + if ((head) == (el)) { \ + (head) = (add); \ + } else { \ + _tmp = (head); \ + while (_tmp->next && (_tmp->next != (el))) { \ + _tmp = _tmp->next; \ + } \ + if (_tmp->next) { \ + _tmp->next = (add); \ + } \ + } \ + } else { \ + LL_APPEND2(head, add, next); \ + } \ +} while (0) \ + #define LL_PREPEND_ELEM(head, el, add) \ + LL_PREPEND_ELEM2(head, el, add, next) + +#define LL_APPEND_ELEM2(head, el, add, next) \ do { \ - LDECLTYPE(head) _tmp; \ - assert(head != NULL); \ - assert(el != NULL); \ - assert(add != NULL); \ - (add)->next = (el); \ - if ((head) == (el)) { \ - (head) = (add); \ + if (el) { \ + assert((head) != NULL); \ + assert((add) != NULL); \ + (add)->next = (el)->next; \ + (el)->next = (add); \ } else { \ - _tmp = head; \ - while (_tmp->next && (_tmp->next != (el))) { \ - _tmp = _tmp->next; \ + LL_PREPEND2(head, add, next); \ + } \ +} while (0) \ + +#define LL_APPEND_ELEM(head, el, add) \ + LL_APPEND_ELEM2(head, el, add, next) + +#ifdef NO_DECLTYPE +/* Here are VS2008 / NO_DECLTYPE replacements for a few functions */ + +#undef LL_CONCAT2 +#define LL_CONCAT2(head1,head2,next) \ +do { \ + char *_tmp; \ + if (head1) { \ + _tmp = (char*)(head1); \ + while ((head1)->next) { (head1) = (head1)->next; } \ + (head1)->next = (head2); \ + _RS(head1); \ + } else { \ + (head1)=(head2); \ } \ - if (_tmp->next) { \ - _tmp->next = (add); \ +} while (0) + +#undef LL_APPEND2 +#define LL_APPEND2(head,add,next) \ +do { \ + if (head) { \ + (add)->next = head; /* use add->next as a temp variable */ \ + while ((add)->next->next) { (add)->next = (add)->next->next; } \ + (add)->next->next=(add); \ + } else { \ + (head)=(add); \ + } \ + (add)->next=NULL; \ +} while (0) + +#undef LL_DELETE2 +#define LL_DELETE2(head,del,next) \ +do { \ + if ((head) == (del)) { \ + (head)=(head)->next; \ + } else { \ + char *_tmp = (char*)(head); \ + while ((head)->next && ((head)->next != (del))) { \ + (head) = (head)->next; \ + } \ + if ((head)->next) { \ + (head)->next = ((del)->next); \ + } \ + _RS(head); \ + } \ +} while (0) + +#undef LL_REPLACE_ELEM2 +#define LL_REPLACE_ELEM2(head, el, add, next) \ +do { \ + assert((head) != NULL); \ + assert((el) != NULL); \ + assert((add) != NULL); \ + if ((head) == (el)) { \ + (head) = (add); \ + } else { \ + (add)->next = head; \ + while ((add)->next->next && ((add)->next->next != (el))) { \ + (add)->next = (add)->next->next; \ + } \ + if ((add)->next->next) { \ + (add)->next->next = (add); \ + } \ + } \ + (add)->next = (el)->next; \ +} while (0) + +#undef LL_PREPEND_ELEM2 +#define LL_PREPEND_ELEM2(head, el, add, next) \ +do { \ + if (el) { \ + assert((head) != NULL); \ + assert((add) != NULL); \ + if ((head) == (el)) { \ + (head) = (add); \ + } else { \ + (add)->next = (head); \ + while ((add)->next->next && ((add)->next->next != (el))) { \ + (add)->next = (add)->next->next; \ + } \ + if ((add)->next->next) { \ + (add)->next->next = (add); \ + } \ + } \ + (add)->next = (el); \ + } else { \ + LL_APPEND2(head, add, next); \ } \ - } \ } while (0) \ +#endif /* NO_DECLTYPE */ /****************************************************************************** * doubly linked list macros (non-circular) * @@ -506,7 +573,7 @@ do { #define DL_PREPEND2(head,add,prev,next) \ do { \ - (add)->next = head; \ + (add)->next = (head); \ if (head) { \ (add)->prev = (head)->prev; \ (head)->prev = (add); \ @@ -541,10 +608,10 @@ do { LDECLTYPE(head1) _tmp; \ if (head2) { \ if (head1) { \ - _tmp = (head2)->prev; \ + _CASTASGN(_tmp, (head2)->prev); \ (head2)->prev = (head1)->prev; \ (head1)->prev->next = (head2); \ - (head1)->prev = _tmp; \ + _CASTASGN((head1)->prev, _tmp); \ } else { \ (head1)=(head2); \ } \ @@ -576,23 +643,23 @@ do { DL_COUNT2(head,el,counter,next) \ #define DL_COUNT2(head,el,counter,next) \ -{ \ - counter = 0; \ - DL_FOREACH2(head,el,next){ ++counter; } \ -} +do { \ + (counter) = 0; \ + DL_FOREACH2(head,el,next) { ++(counter); } \ +} while (0) #define DL_FOREACH(head,el) \ DL_FOREACH2(head,el,next) #define DL_FOREACH2(head,el,next) \ - for(el=head;el;el=(el)->next) + for ((el) = (head); el; (el) = (el)->next) /* this version is safe for deleting the elements during iteration */ #define DL_FOREACH_SAFE(head,el,tmp) \ DL_FOREACH_SAFE2(head,el,tmp,next) #define DL_FOREACH_SAFE2(head,el,tmp,next) \ - for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) + for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp)) /* these are identical to their singly-linked list counterparts */ #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR @@ -600,11 +667,11 @@ do { #define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2 #define DL_SEARCH2 LL_SEARCH2 -#define DL_REPLACE_ELEM(head, el, add) \ +#define DL_REPLACE_ELEM2(head, el, add, prev, next) \ do { \ - assert(head != NULL); \ - assert(el != NULL); \ - assert(add != NULL); \ + assert((head) != NULL); \ + assert((el) != NULL); \ + assert((add) != NULL); \ if ((head) == (el)) { \ (head) = (add); \ (add)->next = (el)->next; \ @@ -626,25 +693,71 @@ do { } \ } while (0) +#define DL_REPLACE_ELEM(head, el, add) \ + DL_REPLACE_ELEM2(head, el, add, prev, next) + +#define DL_PREPEND_ELEM2(head, el, add, prev, next) \ +do { \ + if (el) { \ + assert((head) != NULL); \ + assert((add) != NULL); \ + (add)->next = (el); \ + (add)->prev = (el)->prev; \ + (el)->prev = (add); \ + if ((head) == (el)) { \ + (head) = (add); \ + } else { \ + (add)->prev->next = (add); \ + } \ + } else { \ + DL_APPEND2(head, add, prev, next); \ + } \ +} while (0) \ + #define DL_PREPEND_ELEM(head, el, add) \ + DL_PREPEND_ELEM2(head, el, add, prev, next) + +#define DL_APPEND_ELEM2(head, el, add, prev, next) \ do { \ - assert(head != NULL); \ - assert(el != NULL); \ - assert(add != NULL); \ - (add)->next = (el); \ - (add)->prev = (el)->prev; \ - (el)->prev = (add); \ - if ((head) == (el)) { \ - (head) = (add); \ + if (el) { \ + assert((head) != NULL); \ + assert((add) != NULL); \ + (add)->next = (el)->next; \ + (add)->prev = (el); \ + (el)->next = (add); \ + if ((add)->next) { \ + (add)->next->prev = (add); \ + } else { \ + (head)->prev = (add); \ + } \ } else { \ - (add)->prev->next = (add); \ + DL_PREPEND2(head, add, prev, next); \ } \ } while (0) \ +#define DL_APPEND_ELEM(head, el, add) \ + DL_APPEND_ELEM2(head, el, add, prev, next) /****************************************************************************** * circular doubly linked list macros * *****************************************************************************/ +#define CDL_APPEND(head,add) \ + CDL_APPEND2(head,add,prev,next) + +#define CDL_APPEND2(head,add,prev,next) \ +do { \ + if (head) { \ + (add)->prev = (head)->prev; \ + (add)->next = (head); \ + (head)->prev = (add); \ + (add)->prev->next = (add); \ + } else { \ + (add)->prev = (add); \ + (add)->next = (add); \ + (head) = (add); \ + } \ +} while (0) + #define CDL_PREPEND(head,add) \ CDL_PREPEND2(head,add,prev,next) @@ -659,7 +772,7 @@ do { (add)->prev = (add); \ (add)->next = (add); \ } \ -(head)=(add); \ + (head) = (add); \ } while (0) #define CDL_DELETE(head,del) \ @@ -667,8 +780,8 @@ do { #define CDL_DELETE2(head,del,prev,next) \ do { \ - if ( ((head)==(del)) && ((head)->next == (head))) { \ - (head) = 0L; \ + if (((head)==(del)) && ((head)->next == (head))) { \ + (head) = NULL; \ } else { \ (del)->next->prev = (del)->prev; \ (del)->prev->next = (del)->next; \ @@ -680,24 +793,24 @@ do { CDL_COUNT2(head,el,counter,next) \ #define CDL_COUNT2(head, el, counter,next) \ -{ \ - counter = 0; \ - CDL_FOREACH2(head,el,next){ ++counter; } \ -} +do { \ + (counter) = 0; \ + CDL_FOREACH2(head,el,next) { ++(counter); } \ +} while (0) #define CDL_FOREACH(head,el) \ CDL_FOREACH2(head,el,next) #define CDL_FOREACH2(head,el,next) \ - for(el=head;el;el=((el)->next==head ? 0L : (el)->next)) + for ((el)=(head);el;(el)=(((el)->next==(head)) ? NULL : (el)->next)) #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \ CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) #define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \ - for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \ - (el) && ((tmp2)=(el)->next, 1); \ - ((el) = (((el)==(tmp1)) ? 0L : (tmp2)))) + for ((el) = (head), (tmp1) = (head) ? (head)->prev : NULL; \ + (el) && ((tmp2) = (el)->next, 1); \ + (el) = ((el) == (tmp1) ? NULL : (tmp2))) #define CDL_SEARCH_SCALAR(head,out,field,val) \ CDL_SEARCH_SCALAR2(head,out,field,val,next) @@ -707,7 +820,7 @@ do { CDL_FOREACH2(head,out,next) { \ if ((out)->field == (val)) break; \ } \ -} while(0) +} while (0) #define CDL_SEARCH(head,out,elt,cmp) \ CDL_SEARCH2(head,out,elt,cmp,next) @@ -717,13 +830,13 @@ do { CDL_FOREACH2(head,out,next) { \ if ((cmp(out,elt))==0) break; \ } \ -} while(0) +} while (0) -#define CDL_REPLACE_ELEM(head, el, add) \ +#define CDL_REPLACE_ELEM2(head, el, add, prev, next) \ do { \ - assert(head != NULL); \ - assert(el != NULL); \ - assert(add != NULL); \ + assert((head) != NULL); \ + assert((el) != NULL); \ + assert((add) != NULL); \ if ((el)->next == (el)) { \ (add)->next = (add); \ (add)->prev = (add); \ @@ -739,19 +852,44 @@ do { } \ } while (0) +#define CDL_REPLACE_ELEM(head, el, add) \ + CDL_REPLACE_ELEM2(head, el, add, prev, next) + +#define CDL_PREPEND_ELEM2(head, el, add, prev, next) \ +do { \ + if (el) { \ + assert((head) != NULL); \ + assert((add) != NULL); \ + (add)->next = (el); \ + (add)->prev = (el)->prev; \ + (el)->prev = (add); \ + (add)->prev->next = (add); \ + if ((head) == (el)) { \ + (head) = (add); \ + } \ + } else { \ + CDL_APPEND2(head, add, prev, next); \ + } \ +} while (0) + #define CDL_PREPEND_ELEM(head, el, add) \ + CDL_PREPEND_ELEM2(head, el, add, prev, next) + +#define CDL_APPEND_ELEM2(head, el, add, prev, next) \ do { \ - assert(head != NULL); \ - assert(el != NULL); \ - assert(add != NULL); \ - (add)->next = (el); \ - (add)->prev = (el)->prev; \ - (el)->prev = (add); \ - (add)->prev->next = (add); \ - if ((head) == (el)) { \ - (head) = (add); \ + if (el) { \ + assert((head) != NULL); \ + assert((add) != NULL); \ + (add)->next = (el)->next; \ + (add)->prev = (el); \ + (el)->next = (add); \ + (add)->next->prev = (add); \ + } else { \ + CDL_PREPEND2(head, add, prev, next); \ } \ -} while (0) \ +} while (0) -#endif /* UTLIST_H */ +#define CDL_APPEND_ELEM(head, el, add) \ + CDL_APPEND_ELEM2(head, el, add, prev, next) +#endif /* UTLIST_H */ diff --git a/libs/libaxolotl/src/utstring.h b/libs/libaxolotl/src/utstring.h deleted file mode 100644 index 867442c843..0000000000 --- a/libs/libaxolotl/src/utstring.h +++ /dev/null @@ -1,393 +0,0 @@ -/* -Copyright (c) 2008-2014, Troy D. Hanson http://troydhanson.github.com/uthash/ -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. - -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 OWNER -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. -*/ - -/* a dynamic string implementation using macros - */ -#ifndef UTSTRING_H -#define UTSTRING_H - -#define UTSTRING_VERSION 1.9.9 - -#ifdef __GNUC__ -#define _UNUSED_ __attribute__ ((__unused__)) -#else -#define _UNUSED_ -#endif - -#include <stdlib.h> -#include <string.h> -#include <stdio.h> -#include <stdarg.h> -#define oom() exit(-1) - -typedef struct { - char *d; - size_t n; /* allocd size */ - size_t i; /* index of first unused byte */ -} UT_string; - -#define utstring_reserve(s,amt) \ -do { \ - if (((s)->n - (s)->i) < (size_t)(amt)) { \ - (s)->d = (char*)realloc((s)->d, (s)->n + amt); \ - if ((s)->d == NULL) oom(); \ - (s)->n += amt; \ - } \ -} while(0) - -#define utstring_init(s) \ -do { \ - (s)->n = 0; (s)->i = 0; (s)->d = NULL; \ - utstring_reserve(s,100); \ - (s)->d[0] = '\0'; \ -} while(0) - -#define utstring_done(s) \ -do { \ - if ((s)->d != NULL) free((s)->d); \ - (s)->n = 0; \ -} while(0) - -#define utstring_free(s) \ -do { \ - utstring_done(s); \ - free(s); \ -} while(0) - -#define utstring_new(s) \ -do { \ - s = (UT_string*)calloc(sizeof(UT_string),1); \ - if (!s) oom(); \ - utstring_init(s); \ -} while(0) - -#define utstring_renew(s) \ -do { \ - if (s) { \ - utstring_clear(s); \ - } else { \ - utstring_new(s); \ - } \ -} while(0) - -#define utstring_clear(s) \ -do { \ - (s)->i = 0; \ - (s)->d[0] = '\0'; \ -} while(0) - -#define utstring_bincpy(s,b,l) \ -do { \ - utstring_reserve((s),(l)+1); \ - if (l) memcpy(&(s)->d[(s)->i], b, l); \ - (s)->i += l; \ - (s)->d[(s)->i]='\0'; \ -} while(0) - -#define utstring_concat(dst,src) \ -do { \ - utstring_reserve((dst),((src)->i)+1); \ - if ((src)->i) memcpy(&(dst)->d[(dst)->i], (src)->d, (src)->i); \ - (dst)->i += (src)->i; \ - (dst)->d[(dst)->i]='\0'; \ -} while(0) - -#define utstring_len(s) ((unsigned)((s)->i)) - -#define utstring_body(s) ((s)->d) - -_UNUSED_ static void utstring_printf_va(UT_string *s, const char *fmt, va_list ap) { - int n; - va_list cp; - while (1) { -#ifdef _WIN32 - cp = ap; -#else - va_copy(cp, ap); -#endif - n = vsnprintf (&s->d[s->i], s->n-s->i, fmt, cp); - va_end(cp); - - if ((n > -1) && ((size_t) n < (s->n-s->i))) { - s->i += n; - return; - } - - /* Else try again with more space. */ - if (n > -1) utstring_reserve(s,n+1); /* exact */ - else utstring_reserve(s,(s->n)*2); /* 2x */ - } -} -#ifdef __GNUC__ -/* support printf format checking (2=the format string, 3=start of varargs) */ -static void utstring_printf(UT_string *s, const char *fmt, ...) - __attribute__ (( format( printf, 2, 3) )); -#endif -_UNUSED_ static void utstring_printf(UT_string *s, const char *fmt, ...) { - va_list ap; - va_start(ap,fmt); - utstring_printf_va(s,fmt,ap); - va_end(ap); -} - -/******************************************************************************* - * begin substring search functions * - ******************************************************************************/ -/* Build KMP table from left to right. */ -_UNUSED_ static void _utstring_BuildTable( - const char *P_Needle, - size_t P_NeedleLen, - long *P_KMP_Table) -{ - long i, j; - - i = 0; - j = i - 1; - P_KMP_Table[i] = j; - while (i < (long) P_NeedleLen) - { - while ( (j > -1) && (P_Needle[i] != P_Needle[j]) ) - { - j = P_KMP_Table[j]; - } - i++; - j++; - if (i < (long) P_NeedleLen) - { - if (P_Needle[i] == P_Needle[j]) - { - P_KMP_Table[i] = P_KMP_Table[j]; - } - else - { - P_KMP_Table[i] = j; - } - } - else - { - P_KMP_Table[i] = j; - } - } - - return; -} - - -/* Build KMP table from right to left. */ -_UNUSED_ static void _utstring_BuildTableR( - const char *P_Needle, - size_t P_NeedleLen, - long *P_KMP_Table) -{ - long i, j; - - i = P_NeedleLen - 1; - j = i + 1; - P_KMP_Table[i + 1] = j; - while (i >= 0) - { - while ( (j < (long) P_NeedleLen) && (P_Needle[i] != P_Needle[j]) ) - { - j = P_KMP_Table[j + 1]; - } - i--; - j--; - if (i >= 0) - { - if (P_Needle[i] == P_Needle[j]) - { - P_KMP_Table[i + 1] = P_KMP_Table[j + 1]; - } - else - { - P_KMP_Table[i + 1] = j; - } - } - else - { - P_KMP_Table[i + 1] = j; - } - } - - return; -} - - -/* Search data from left to right. ( Multiple search mode. ) */ -_UNUSED_ static long _utstring_find( - const char *P_Haystack, - size_t P_HaystackLen, - const char *P_Needle, - size_t P_NeedleLen, - long *P_KMP_Table) -{ - long i, j; - long V_FindPosition = -1; - - /* Search from left to right. */ - i = j = 0; - while ( (j < (int)P_HaystackLen) && (((P_HaystackLen - j) + i) >= P_NeedleLen) ) - { - while ( (i > -1) && (P_Needle[i] != P_Haystack[j]) ) - { - i = P_KMP_Table[i]; - } - i++; - j++; - if (i >= (int)P_NeedleLen) - { - /* Found. */ - V_FindPosition = j - i; - break; - } - } - - return V_FindPosition; -} - - -/* Search data from right to left. ( Multiple search mode. ) */ -_UNUSED_ static long _utstring_findR( - const char *P_Haystack, - size_t P_HaystackLen, - const char *P_Needle, - size_t P_NeedleLen, - long *P_KMP_Table) -{ - long i, j; - long V_FindPosition = -1; - - /* Search from right to left. */ - j = (P_HaystackLen - 1); - i = (P_NeedleLen - 1); - while ( (j >= 0) && (j >= i) ) - { - while ( (i < (int)P_NeedleLen) && (P_Needle[i] != P_Haystack[j]) ) - { - i = P_KMP_Table[i + 1]; - } - i--; - j--; - if (i < 0) - { - /* Found. */ - V_FindPosition = j + 1; - break; - } - } - - return V_FindPosition; -} - - -/* Search data from left to right. ( One time search mode. ) */ -_UNUSED_ static long utstring_find( - UT_string *s, - long P_StartPosition, /* Start from 0. -1 means last position. */ - const char *P_Needle, - size_t P_NeedleLen) -{ - long V_StartPosition; - long V_HaystackLen; - long *V_KMP_Table; - long V_FindPosition = -1; - - if (P_StartPosition < 0) - { - V_StartPosition = s->i + P_StartPosition; - } - else - { - V_StartPosition = P_StartPosition; - } - V_HaystackLen = s->i - V_StartPosition; - if ( (V_HaystackLen >= (long) P_NeedleLen) && (P_NeedleLen > 0) ) - { - V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1)); - if (V_KMP_Table != NULL) - { - _utstring_BuildTable(P_Needle, P_NeedleLen, V_KMP_Table); - - V_FindPosition = _utstring_find(s->d + V_StartPosition, - V_HaystackLen, - P_Needle, - P_NeedleLen, - V_KMP_Table); - if (V_FindPosition >= 0) - { - V_FindPosition += V_StartPosition; - } - - free(V_KMP_Table); - } - } - - return V_FindPosition; -} - - -/* Search data from right to left. ( One time search mode. ) */ -_UNUSED_ static long utstring_findR( - UT_string *s, - long P_StartPosition, /* Start from 0. -1 means last position. */ - const char *P_Needle, - size_t P_NeedleLen) -{ - long V_StartPosition; - long V_HaystackLen; - long *V_KMP_Table; - long V_FindPosition = -1; - - if (P_StartPosition < 0) - { - V_StartPosition = s->i + P_StartPosition; - } - else - { - V_StartPosition = P_StartPosition; - } - V_HaystackLen = V_StartPosition + 1; - if ( (V_HaystackLen >= (long) P_NeedleLen) && (P_NeedleLen > 0) ) - { - V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1)); - if (V_KMP_Table != NULL) - { - _utstring_BuildTableR(P_Needle, P_NeedleLen, V_KMP_Table); - - V_FindPosition = _utstring_findR(s->d, - V_HaystackLen, - P_Needle, - P_NeedleLen, - V_KMP_Table); - - free(V_KMP_Table); - } - } - - return V_FindPosition; -} -/******************************************************************************* - * end substring search functions * - ******************************************************************************/ - -#endif /* UTSTRING_H */ diff --git a/libs/libaxolotl/src/vpool.h b/libs/libaxolotl/src/vpool.h index 0eb714cc10..04707cb9ae 100644 --- a/libs/libaxolotl/src/vpool.h +++ b/libs/libaxolotl/src/vpool.h @@ -21,7 +21,7 @@ #define _VPOOL_H_ #include <sys/types.h> -#ifndef _WINDOWS +#if !defined(_WINDOWS) && !defined(__sun__) #include <sys/cdefs.h> #else #ifdef __cplusplus |