Updated MSWS RNG to latest version + some more fixes.

diff --git a/tools/GenTables/include/boxmuller.h b/tools/GenTables/include/boxmuller.h
index 56892d6..4a6dd09 100644 (file)
--- a/tools/GenTables/include/boxmuller.h
+++ b/tools/GenTables/include/boxmuller.h
@@ -41,7 +41,7 @@ static inline void gaussian_noise_init(bxmller_t *const bxmller)
        memset(bxmller, 0, sizeof(bxmller_t));
 }
 
-static inline uint32_t gaussian_noise_next(msws_t *const rand, bxmller_t *const bxmller, const double sigma, const uint32_t min, const uint32_t max)
+static inline uint32_t gaussian_noise_next(msws_t rand, bxmller_t *const bxmller, const double sigma, const uint32_t min, const uint32_t max)
 {
        static const double TWOPI = 6.283185307179586476925286766559005768394338798750211641949;
        double value;

diff --git a/tools/GenTables/include/common.h b/tools/GenTables/include/common.h
index badaf80..b6ca4a6 100644 (file)
--- a/tools/GenTables/include/common.h
+++ b/tools/GenTables/include/common.h
@@ -49,7 +49,7 @@ static inline uint32_t make_seed(void)
        return seed;
 }
 
-static inline invert_byte_buffer(uint8_t *const buffer, const size_t size)
+static inline void invert_byte_buffer(uint8_t *const buffer, const size_t size)
 {
        const size_t words = size / sizeof(uint32_t);
        const size_t bytes = size % sizeof(uint32_t);

diff --git a/tools/GenTables/include/msws.h b/tools/GenTables/include/msws.h
index e512291..24ad641 100644 (file)
--- a/tools/GenTables/include/msws.h
+++ b/tools/GenTables/include/msws.h
@@ -34,36 +34,34 @@
 *                                                                          *
 \**************************************************************************/
 
+/**************************************************************************\
+*                                                                          *
+*  Modifications applied by LoRd_MuldeR <mulder2@gmx.de>:                  *
+*                                                                          *
+*  1. Added function to get random 32-Bit value with upper limit           *
+*  2. Added function to get random 64-Bit value                            *
+*  3. Added function to get random byte-sequence of arbitrary length       *
+*  4. Improved initialization (seeding) function                           *
+*  5. Made all functions thread-safe by avoiding the use of static vars    *
+*  6. Implemented C++ wrapper class, for convenience                       *
+*                                                                          *
+\**************************************************************************/
+
 #ifndef _INC_MSWS_H
 #define _INC_MSWS_H
 
+#include <stddef.h>
 #include <stdint.h>
 
-typedef struct
-{
-       uint64_t x;
-       uint64_t w;
-       uint64_t s;
-}
-msws_t;
+typedef uint64_t msws_t[3];
 
-inline static uint32_t msws_uint32(msws_t *const ctx)
+inline static uint32_t msws_uint32(msws_t ctx)
 {
-       ctx->x *= ctx->x; ctx->x += (ctx->w += ctx->s);
-       return (uint32_t)(ctx->x = (ctx->x >> 32) | (ctx->x << 32));
+       ctx[0] *= ctx[0]; ctx[0] += (ctx[1] += ctx[2]);
+       return (uint32_t)(ctx[0] = (ctx[0] >> 32) | (ctx[0] << 32));
 }
 
-inline static void msws_init(msws_t *const ctx, const uint32_t seed)
-{
-       ctx->x = UINT64_C(0); ctx->w = UINT64_C(0);
-       ctx->s = ((uint64_t)seed + 0xB5AD4ECEDA1CE2A9) | UINT64_C(1);
-       for (int i = 0; i < 13; ++i)
-       {
-               volatile uint32_t q = msws_uint32(ctx);
-       }
-}
-
-static inline uint32_t msws_range(msws_t *const ctx, const uint32_t n)
+static inline uint32_t msws_uint32_max(msws_t ctx, const uint32_t max)
 {
        static const uint32_t DIV[64] =
        {
@@ -84,10 +82,17 @@ static inline uint32_t msws_range(msws_t *const ctx, const uint32_t n)
                0x04924925, 0x047DC120, 0x0469EE59, 0x0456C798,
                0x04444445, 0x04325C54, 0x04210843, 0x04104105
        };
-       return (n < 64) ? (msws_uint32(ctx) / DIV[n]) : (msws_uint32(ctx) / (UINT32_MAX / n + 1U));
+       return (max < 64)
+               ? (msws_uint32(ctx) / DIV[max])
+               : (msws_uint32(ctx) / (UINT32_MAX / max + 1U));
+}
+
+inline static uint64_t msws_uint64(msws_t ctx)
+{
+       return (((uint64_t)msws_uint32(ctx)) << 32U) | msws_uint32(ctx);
 }
 
-inline static void msws_bytes(msws_t *const ctx, uint8_t *buffer, size_t len)
+inline static void msws_bytes(msws_t ctx, uint8_t *buffer, size_t len)
 {
        if (((len & 3U) == 0U) && ((((uintptr_t)buffer) & 3U) == 0U))
        {
@@ -107,4 +112,14 @@ inline static void msws_bytes(msws_t *const ctx, uint8_t *buffer, size_t len)
        }
 }
 
-#endif _INC_MSWS_H
+inline static void msws_init(msws_t ctx, const uint32_t seed)
+{
+       ctx[0] = UINT64_C(0); ctx[1] = UINT64_C(0);
+       ctx[2] = (((uint64_t)seed) << 1U) + 0xB5AD4ECEDA1CE2A9;
+       for (int i = 0; i < 13; ++i)
+       {
+               volatile uint32_t q = msws_uint32(ctx);
+       }
+}
+
+#endif //_INC_MSWS_H

diff --git a/tools/GenTables/src/gen_table_mix.c b/tools/GenTables/src/gen_table_mix.c
index 2714d48..1e8a038 100644 (file)
--- a/tools/GenTables/src/gen_table_mix.c
+++ b/tools/GenTables/src/gen_table_mix.c
@@ -87,37 +87,34 @@ static const uint8_t INDICES[UINT8_MAX + 1U] =
 #define TRACE(X, ...) __noop()
 #endif
 
-static inline void swap(uint8_t *const row_buffer, const uint_fast8_t a, const uint_fast8_t b)
+static inline void swap(uint8_t *const row_buffer, const uint_fast16_t a, const uint_fast16_t b)
 {
        const uint8_t temp = row_buffer[a];
        row_buffer[a] = row_buffer[b];
        row_buffer[b] = temp;
 }
 
-static inline void random_permutation(msws_t *const rand, uint8_t *const row_buffer)
+static inline void random_permutation(msws_t rand, uint8_t *const row_buffer)
 {
-       for (uint_fast8_t i = 0; i < ROW_LEN; ++i)
+       for (uint_fast16_t i = 0; i < ROW_LEN; ++i)
        {
-               const uint_fast8_t j = msws_range(rand, i + 1U);
+               const uint_fast16_t j = msws_uint32_max(rand, i + 1U);
                row_buffer[i] = row_buffer[j];
                row_buffer[j] = INDICES[i];
        }
 }
 
-static inline void swap_multiple_random(msws_t *const rand, uint8_t *const row_buffer, const uint_fast8_t count)
+static inline void swap_multiple_random(msws_t rand, uint8_t *const row_buffer, const uint_fast16_t count)
 {
-       bool map[ROW_LEN];
-       memset(&map[0], 0, sizeof(bool) * ROW_LEN);
-       for (uint_fast8_t i = 0U; i < count; ++i)
+       for (uint_fast16_t i = 0U; i < count; ++i)
        {
-               uint_fast8_t a, b;
+               uint_fast16_t a, b;
                do
                {
-                       a = msws_range(rand, ROW_LEN);
-                       b = msws_range(rand, ROW_LEN);
+                       a = msws_uint32_max(rand, ROW_LEN);
+                       b = msws_uint32_max(rand, ROW_LEN);
                } 
-               while(map[a] || (a == b));
-               map[a] = map[b] = true;
+               while(a == b);
                swap(row_buffer, a, b);
        }
 }
@@ -125,7 +122,7 @@ static inline void swap_multiple_random(msws_t *const rand, uint8_t *const row_b
 static inline void rotate_row(uint8_t *const row_buffer)
 {
        const uint8_t temp = row_buffer[0];
-       for (uint32_t k = 0U; k < ROW_LEN - 1U; ++k)
+       for (uint_fast16_t k = 0U; k < ROW_LEN - 1U; ++k)
        {
                row_buffer[k] = row_buffer[k + 1U];
        }
@@ -134,8 +131,8 @@ static inline void rotate_row(uint8_t *const row_buffer)
 
 static inline void reverse_row(uint8_t *const row_buffer)
 {
-       uint_fast8_t j = ROW_LEN - 1U;
-       for (uint_fast8_t i = 0U; i < ROW_LEN / 2U; ++i)
+       uint_fast16_t j = ROW_LEN - 1U;
+       for (uint_fast16_t i = 0U; i < ROW_LEN / 2U; ++i)
        {
                swap(row_buffer, i, j--);
        }
@@ -144,7 +141,7 @@ static inline void reverse_row(uint8_t *const row_buffer)
 static inline uint_fast16_t row_distance(const uint8_t *const row_a, const uint8_t *const row_b)
 {
        uint_fast16_t distance = 0U;
-       for (uint_fast8_t j = 0; j < ROW_LEN; ++j)
+       for (uint_fast16_t j = 0; j < ROW_LEN; ++j)
        {
                if (row_a[j] != row_b[j])
                {
@@ -193,7 +190,7 @@ static void print_row(const uint8_t *const row_buffer)
        puts("");
 }
 
-static dump_table(FILE *out)
+static void dump_table(FILE *out)
 {
        fprintf(out, "uint8_t MHASH_384_TABLE_MIX[%u][MHASH_384_LEN] =\n{\n", ROW_NUM);
        for (uint_fast16_t i = 0; i < ROW_NUM; i++)
@@ -350,7 +347,7 @@ int wmain(int argc, wchar_t *argv[])
        }
 
        msws_t rand;
-       msws_init(&rand, make_seed());
+       msws_init(rand, make_seed());
 
        bxmller_t bxmller;
        gaussian_noise_init(&bxmller);
@@ -371,7 +368,7 @@ int wmain(int argc, wchar_t *argv[])
                uint_fast16_t counter = 0U;
                for (;;)
                {
-                       random_permutation(&rand, &g_table[i][0]);
+                       random_permutation(rand, &g_table[i][0]);
                        uint_fast16_t error = check_permutation(i, &g_table[i][0], UINT16_MAX);
                        if (error > 0U)
                        {
@@ -386,7 +383,7 @@ int wmain(int argc, wchar_t *argv[])
                                        }
                                        for (uint_fast16_t rand_init = 0U; rand_init < 9973U; ++rand_init)
                                        {
-                                               random_permutation(&rand, &temp[0]);
+                                               random_permutation(rand, &temp[0]);
                                                const uint_fast16_t error_next = check_permutation(i, &temp[0], error);
                                                if (error_next < error)
                                                {
@@ -436,7 +433,7 @@ int wmain(int argc, wchar_t *argv[])
                                        TRACE("Optimizer round %u of %u", retry, MAX_RETRY);
                                        if (!retry)
                                        {
-                                               msws_init(&rand, make_seed());
+                                               msws_init(rand, make_seed());
                                                TRACE("First round!");
                                                for (uint_fast8_t swap_x1 = 0; swap_x1 < ROW_LEN; ++swap_x1)
                                                {
@@ -512,7 +509,7 @@ int wmain(int argc, wchar_t *argv[])
                                        const double sigma = 3.14159 * (1.0 + (retry / (double)MAX_RETRY));
                                        for (int_fast16_t loop = 0; loop < 9973U; ++loop)
                                        {
-                                               const uint_fast8_t swap_count = (uint_fast8_t)gaussian_noise_next(&rand, &bxmller, sigma, 4U, (ROW_LEN / 2U));
+                                               const uint_fast8_t swap_count = (uint_fast8_t)gaussian_noise_next(rand, &bxmller, sigma, 4U, (ROW_LEN / 2U));
                                                if (!((++counter) & 0x3FFF))
                                                {
                                                        printf("\b\b\b[%c]", SPINNER[g_spinpos]);
@@ -521,7 +518,7 @@ int wmain(int argc, wchar_t *argv[])
                                                for (int_fast16_t round = 0; round < 997U; ++round)
                                                {
                                                        memcpy(&temp[0], &g_table[i][0], sizeof(uint8_t) * ROW_LEN);
-                                                       swap_multiple_random(&rand, &temp[0], swap_count);
+                                                       swap_multiple_random(rand, &temp[0], swap_count);
                                                        const uint_fast16_t error_next = check_permutation(i, &temp[0], error);
                                                        if (error_next < error)
                                                        {
@@ -537,7 +534,7 @@ int wmain(int argc, wchar_t *argv[])
                                        }
                                }
                                TRACE("Restart!");
-                               msws_init(&rand, make_seed());
+                               msws_init(rand, make_seed());
                        }
                        else
                        {

diff --git a/tools/GenTables/src/gen_table_xor.c b/tools/GenTables/src/gen_table_xor.c
index deeb4f0..5c777cc 100644 (file)
--- a/tools/GenTables/src/gen_table_xor.c
+++ b/tools/GenTables/src/gen_table_xor.c
@@ -94,7 +94,7 @@ static inline void flip_bit_at(uint8_t *const row_buffer, const size_t pos)
        row_buffer[pos >> 3] ^= ((uint8_t)(1U << (pos & 0x7)));
 }
 
-static inline void flip_rand_n(uint8_t *const row_buffer, msws_t *const rand, const uint32_t n)
+static inline void flip_rand_n(uint8_t *const row_buffer, msws_t rand, const uint32_t n)
 {
        bool taken[HASH_LEN];
        memset(&taken, 0, sizeof(bool) * HASH_LEN);
@@ -103,7 +103,7 @@ static inline void flip_rand_n(uint8_t *const row_buffer, msws_t *const rand, co
                size_t next;
                do
                {
-                       next = msws_range(rand, HASH_LEN);
+                       next = msws_uint32_max(rand, HASH_LEN);
                }
                while (taken[next]);
                flip_bit_at(row_buffer, next);
@@ -162,7 +162,7 @@ static inline uint32_t check_distance_buff(const uint32_t distance_max, const si
        return error;
 }
 
-static dump_table(FILE *out)
+static void dump_table(FILE *out)
 {
        fputs("uint8_t MHASH_384_TABLE_XOR[UINT8_MAX+2][MHASH_384_LEN] =\n{\n", out);
        for (size_t i = 0; i < ROW_NUM; i++)
@@ -204,9 +204,9 @@ static void* thread_main(void *const param)
        for(;;)
        {
                TRACE("Maximum distance: %u", data->distance_max);
-               msws_init(&rand, make_seed());
+               msws_init(rand, make_seed());
                gaussian_noise_init(&bxmller);
-               msws_bytes(&rand, data->row_buffer, ROW_LEN);
+               msws_bytes(rand, data->row_buffer, ROW_LEN);
                uint32_t error = check_distance_buff(data->distance_max, data->index, data->row_buffer, HASH_LEN);
                if(error > 0U)
                {
@@ -221,7 +221,7 @@ static void* thread_main(void *const param)
                                }
                                for (size_t rand_loop = 0; rand_loop < 99991U; ++rand_loop)
                                {
-                                       msws_bytes(&rand, temp, ROW_LEN);
+                                       msws_bytes(rand, temp, ROW_LEN);
                                        const uint32_t next_error = check_distance_buff(data->distance_max, data->index, temp, error);
                                        if (next_error < error)
                                        {
@@ -242,7 +242,7 @@ static void* thread_main(void *const param)
                                {
                                        for (size_t xchg_pos = 0U; xchg_pos < ROW_LEN; ++xchg_pos)
                                        {
-                                               uint8_t value = (uint8_t)msws_uint32(&rand);
+                                               uint8_t value = (uint8_t)msws_uint32(rand);
                                                uint8_t original = data->row_buffer[xchg_pos];
                                                for (size_t xchg_cnt = 0U; xchg_cnt <= UINT8_MAX; ++xchg_cnt, ++value)
                                                {
@@ -362,20 +362,20 @@ static void* thread_main(void *const param)
                                        {
                                                switch (rand_mode)
                                                {
-                                                       case 0x0: msws_bytes(&rand, &temp[0U * (ROW_LEN / 2U)], ROW_LEN / 2U); break;
-                                                       case 0x1: msws_bytes(&rand, &temp[1U * (ROW_LEN / 2U)], ROW_LEN / 2U); break;
-                                                       case 0x2: msws_bytes(&rand, &temp[0U * (ROW_LEN / 4U)], ROW_LEN / 4U); break;
-                                                       case 0x3: msws_bytes(&rand, &temp[1U * (ROW_LEN / 4U)], ROW_LEN / 4U); break;
-                                                       case 0x4: msws_bytes(&rand, &temp[2U * (ROW_LEN / 4U)], ROW_LEN / 4U); break;
-                                                       case 0x5: msws_bytes(&rand, &temp[3U * (ROW_LEN / 4U)], ROW_LEN / 4U); break;
-                                                       case 0x6: msws_bytes(&rand, &temp[0U * (ROW_LEN / 8U)], ROW_LEN / 8U); break;
-                                                       case 0x7: msws_bytes(&rand, &temp[1U * (ROW_LEN / 8U)], ROW_LEN / 8U); break;
-                                                       case 0x8: msws_bytes(&rand, &temp[2U * (ROW_LEN / 8U)], ROW_LEN / 8U); break;
-                                                       case 0x9: msws_bytes(&rand, &temp[3U * (ROW_LEN / 8U)], ROW_LEN / 8U); break;
-                                                       case 0xA: msws_bytes(&rand, &temp[4U * (ROW_LEN / 8U)], ROW_LEN / 8U); break;
-                                                       case 0xB: msws_bytes(&rand, &temp[5U * (ROW_LEN / 8U)], ROW_LEN / 8U); break;
-                                                       case 0xC: msws_bytes(&rand, &temp[6U * (ROW_LEN / 8U)], ROW_LEN / 8U); break;
-                                                       case 0xD: msws_bytes(&rand, &temp[7U * (ROW_LEN / 8U)], ROW_LEN / 8U); break;
+                                                       case 0x0: msws_bytes(rand, &temp[0U * (ROW_LEN / 2U)], ROW_LEN / 2U); break;
+                                                       case 0x1: msws_bytes(rand, &temp[1U * (ROW_LEN / 2U)], ROW_LEN / 2U); break;
+                                                       case 0x2: msws_bytes(rand, &temp[0U * (ROW_LEN / 4U)], ROW_LEN / 4U); break;
+                                                       case 0x3: msws_bytes(rand, &temp[1U * (ROW_LEN / 4U)], ROW_LEN / 4U); break;
+                                                       case 0x4: msws_bytes(rand, &temp[2U * (ROW_LEN / 4U)], ROW_LEN / 4U); break;
+                                                       case 0x5: msws_bytes(rand, &temp[3U * (ROW_LEN / 4U)], ROW_LEN / 4U); break;
+                                                       case 0x6: msws_bytes(rand, &temp[0U * (ROW_LEN / 8U)], ROW_LEN / 8U); break;
+                                                       case 0x7: msws_bytes(rand, &temp[1U * (ROW_LEN / 8U)], ROW_LEN / 8U); break;
+                                                       case 0x8: msws_bytes(rand, &temp[2U * (ROW_LEN / 8U)], ROW_LEN / 8U); break;
+                                                       case 0x9: msws_bytes(rand, &temp[3U * (ROW_LEN / 8U)], ROW_LEN / 8U); break;
+                                                       case 0xA: msws_bytes(rand, &temp[4U * (ROW_LEN / 8U)], ROW_LEN / 8U); break;
+                                                       case 0xB: msws_bytes(rand, &temp[5U * (ROW_LEN / 8U)], ROW_LEN / 8U); break;
+                                                       case 0xC: msws_bytes(rand, &temp[6U * (ROW_LEN / 8U)], ROW_LEN / 8U); break;
+                                                       case 0xD: msws_bytes(rand, &temp[7U * (ROW_LEN / 8U)], ROW_LEN / 8U); break;
                                                        default: abort();
                                                }
                                                const uint32_t next_error = check_distance_buff(data->distance_max, data->index, temp, error);
@@ -401,11 +401,11 @@ static void* thread_main(void *const param)
                                                        return NULL;
                                                }
                                        }
-                                       const uint32_t flip_count = gaussian_noise_next(&rand, &bxmller, 3.14159, 5U, HASH_LEN);
+                                       const uint32_t flip_count = gaussian_noise_next(rand, &bxmller, 3.14159, 5U, HASH_LEN);
                                        for (size_t refine_step = 0; refine_step < 997U; ++refine_step)
                                        {
                                                memcpy(temp, data->row_buffer, sizeof(uint8_t) * ROW_LEN);
-                                               flip_rand_n(temp, &rand, flip_count);
+                                               flip_rand_n(temp, rand, flip_count);
                                                const uint32_t next_error = check_distance_buff(data->distance_max, data->index, temp, error);
                                                if (next_error < error)
                                                {