From 767fc205f8eb71374332eb254205a88ea7f1d818 Mon Sep 17 00:00:00 2001 From: LoRd_MuldeR Date: Sun, 24 Dec 2017 13:40:54 +0100 Subject: [PATCH] Added tool for generating the RND table. --- tools/GenTables/GenTables.sln | 12 +- tools/GenTables/GenTables_RND.vcxproj | 207 ++++++++++++++++++++++++++ tools/GenTables/GenTables_RND.vcxproj.filters | 39 +++++ tools/GenTables/src/gen_table_rnd.c | 190 +++++++++++++++++++++++ 4 files changed, 447 insertions(+), 1 deletion(-) create mode 100644 tools/GenTables/GenTables_RND.vcxproj create mode 100644 tools/GenTables/GenTables_RND.vcxproj.filters create mode 100644 tools/GenTables/src/gen_table_rnd.c diff --git a/tools/GenTables/GenTables.sln b/tools/GenTables/GenTables.sln index 393adbb..bc4bd2d 100644 --- a/tools/GenTables/GenTables.sln +++ b/tools/GenTables/GenTables.sln @@ -1,7 +1,7 @@  Microsoft Visual Studio Solution File, Format Version 12.00 # Visual Studio 15 -VisualStudioVersion = 15.0.26730.16 +VisualStudioVersion = 15.0.27130.2010 MinimumVisualStudioVersion = 10.0.40219.1 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "GenTables_XOR", "GenTables_XOR.vcxproj", "{0167CFFA-8052-4BA8-9DA6-EE0E7EDF3A74}" EndProject @@ -9,6 +9,8 @@ Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "GenTables_MIX", "GenTables_ EndProject Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "GenTables_XOR_V2", "GenTables_XOR_V2.vcxproj", "{83CA38F1-6018-4FD0-B7CC-192BD3F29715}" EndProject +Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "GenTables_RND", "GenTables_RND.vcxproj", "{5581ACF6-5C73-4426-8D2D-A6CC3EDBC7D3}" +EndProject Global GlobalSection(SolutionConfigurationPlatforms) = preSolution Debug|x64 = Debug|x64 @@ -41,6 +43,14 @@ Global {83CA38F1-6018-4FD0-B7CC-192BD3F29715}.Release|x64.Build.0 = Release|x64 {83CA38F1-6018-4FD0-B7CC-192BD3F29715}.Release|x86.ActiveCfg = Release|Win32 {83CA38F1-6018-4FD0-B7CC-192BD3F29715}.Release|x86.Build.0 = Release|Win32 + {5581ACF6-5C73-4426-8D2D-A6CC3EDBC7D3}.Debug|x64.ActiveCfg = Debug|x64 + {5581ACF6-5C73-4426-8D2D-A6CC3EDBC7D3}.Debug|x64.Build.0 = Debug|x64 + {5581ACF6-5C73-4426-8D2D-A6CC3EDBC7D3}.Debug|x86.ActiveCfg = Debug|Win32 + {5581ACF6-5C73-4426-8D2D-A6CC3EDBC7D3}.Debug|x86.Build.0 = Debug|Win32 + {5581ACF6-5C73-4426-8D2D-A6CC3EDBC7D3}.Release|x64.ActiveCfg = Release|x64 + {5581ACF6-5C73-4426-8D2D-A6CC3EDBC7D3}.Release|x64.Build.0 = Release|x64 + {5581ACF6-5C73-4426-8D2D-A6CC3EDBC7D3}.Release|x86.ActiveCfg = Release|Win32 + {5581ACF6-5C73-4426-8D2D-A6CC3EDBC7D3}.Release|x86.Build.0 = Release|Win32 EndGlobalSection GlobalSection(SolutionProperties) = preSolution HideSolutionNode = FALSE diff --git a/tools/GenTables/GenTables_RND.vcxproj b/tools/GenTables/GenTables_RND.vcxproj new file mode 100644 index 0000000..93faf5f --- /dev/null +++ b/tools/GenTables/GenTables_RND.vcxproj @@ -0,0 +1,207 @@ + + + + + Debug + Win32 + + + Release + Win32 + + + Debug + x64 + + + Release + x64 + + + + + + + + + + + + + + {5581ACF6-5C73-4426-8D2D-A6CC3EDBC7D3} + Win32Proj + GenTables_MIX + 7.0 + + + + Application + true + v141_xp + Unicode + + + Application + false + v141_xp + true + Unicode + + + Application + true + v141_xp + Unicode + + + Application + false + v141_xp + true + Unicode + + + + + + + + + + + + + + + + + + + + + true + $(SolutionDir)\bin\$(Platform)\$(Configuration)\ + $(SolutionDir)\obj\$(Platform)\$(Configuration)\$(ProjectName)\ + + + true + $(SolutionDir)\bin\$(Platform)\$(Configuration)\ + $(SolutionDir)\obj\$(Platform)\$(Configuration)\$(ProjectName)\ + + + false + $(SolutionDir)\bin\$(Platform)\$(Configuration)\ + $(SolutionDir)\obj\$(Platform)\$(Configuration)\$(ProjectName)\ + + + false + $(SolutionDir)\bin\$(Platform)\$(Configuration)\ + $(SolutionDir)\obj\$(Platform)\$(Configuration)\$(ProjectName)\ + + + + + + Level3 + Disabled + WIN32;_DEBUG;_CONSOLE;PTW32_STATIC_LIB;%(PreprocessorDefinitions) + $(SolutionDir)\include;$(SolutionDir)\..\..\..\Prerequisites\PthreadsW32\include + 4996 + MultiThreadedDebug + + + Console + true + $(SolutionDir)\..\..\..\Prerequisites\PthreadsW32\lib\$(Platform)\shared;%(AdditionalLibraryDirectories) + pthreadVC2.$(PlatformToolset).lib;%(AdditionalDependencies) + + + + + + + Level3 + Disabled + _DEBUG;_CONSOLE;PTW32_STATIC_LIB;%(PreprocessorDefinitions) + $(SolutionDir)\include;$(SolutionDir)\..\..\..\Prerequisites\PthreadsW32\include + 4996 + MultiThreadedDebug + + + Console + true + $(SolutionDir)\..\..\..\Prerequisites\PthreadsW32\lib\$(Platform)\shared;%(AdditionalLibraryDirectories) + pthreadVC2.$(PlatformToolset).lib;%(AdditionalDependencies) + + + + + Level3 + NotUsing + Full + true + true + WIN32;NDEBUG;_CONSOLE;PTW32_STATIC_LIB;%(PreprocessorDefinitions); + AdvancedVectorExtensions2 + MultiThreaded + false + AnySuitable + Speed + true + $(SolutionDir)\include;$(SolutionDir)\..\..\..\Prerequisites\PthreadsW32\include + 4996 + false + Fast + false + false + false + false + + + Console + true + true + false + $(SolutionDir)\..\..\..\Prerequisites\PthreadsW32\lib\$(Platform)\static;%(AdditionalLibraryDirectories) + pthreadVC2.$(PlatformToolset).lib;%(AdditionalDependencies) + UseLinkTimeCodeGeneration + + + + + Level3 + NotUsing + Full + true + true + NDEBUG;_CONSOLE;PTW32_STATIC_LIB;%(PreprocessorDefinitions); + $(SolutionDir)\include;$(SolutionDir)\..\..\..\Prerequisites\PthreadsW32\include + 4996 + MultiThreaded + false + false + AdvancedVectorExtensions2 + Fast + false + AnySuitable + Speed + true + true + false + false + + + Console + true + true + false + $(SolutionDir)\..\..\..\Prerequisites\PthreadsW32\lib\$(Platform)\static;%(AdditionalLibraryDirectories) + pthreadVC2.$(PlatformToolset).lib;%(AdditionalDependencies) + UseLinkTimeCodeGeneration + + + + + + \ No newline at end of file diff --git a/tools/GenTables/GenTables_RND.vcxproj.filters b/tools/GenTables/GenTables_RND.vcxproj.filters new file mode 100644 index 0000000..66b1f39 --- /dev/null +++ b/tools/GenTables/GenTables_RND.vcxproj.filters @@ -0,0 +1,39 @@ + + + + + {4FC737F1-C7A5-4376-A066-2A32D752A2FF} + cpp;c;cc;cxx;def;odl;idl;hpj;bat;asm;asmx + + + {93995380-89BD-4b04-88EB-625FBE52EBFB} + h;hh;hpp;hxx;hm;inl;inc;xsd + + + {67DA6AB6-F800-4c08-8B7A-83BB121AAD01} + rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx;tiff;tif;png;wav;mfcribbon-ms + + + + + Header Files + + + Header Files + + + Header Files + + + Header Files + + + Header Files + + + + + Source Files + + + \ No newline at end of file diff --git a/tools/GenTables/src/gen_table_rnd.c b/tools/GenTables/src/gen_table_rnd.c new file mode 100644 index 0000000..f635a18 --- /dev/null +++ b/tools/GenTables/src/gen_table_rnd.c @@ -0,0 +1,190 @@ +/* ----------------------------------------------------------------------------------------------- */ +/* MHash-384 - Generate tables utility program */ +/* Copyright(c) 2016-2017 LoRd_MuldeR */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining a copy of this software */ +/* and associated documentation files(the "Software"), to deal in the Software without */ +/* restriction, including without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and / or sell copies of the Software, and to permit persons to whom the */ +/* Software is furnished to do so, subject to the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be included in all copies or */ +/* substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING */ +/* BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */ +/* NONINFRINGEMENT.IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, */ +/* DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, */ +/* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/* ----------------------------------------------------------------------------------------------- */ + +#include "common.h" +#include "msws.h" + +#include +#include +#include +#include +#include +#include + +//----------------------------------------------------------------------------- +// Const +//----------------------------------------------------------------------------- + +#define HASH_LEN 384U +#define ROW_LEN 256U /*number of indices per row*/ + +#define ENABLE_TRACE + +//----------------------------------------------------------------------------- +// Globals +//----------------------------------------------------------------------------- + +static size_t g_spinpos = 0; + +static const char SPINNER[4] = { '/', '-', '\\', '|' }; +static const double SQRT2 = 1.41421356237309504880168872420969807856967187537694; + +static const uint8_t INDICES[UINT8_MAX + 1U] = +{ + 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, + 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1A, 0x1B, 0x1C, 0x1D, 0x1E, 0x1F, + 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2A, 0x2B, 0x2C, 0x2D, 0x2E, 0x2F, + 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F, + 0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4A, 0x4B, 0x4C, 0x4D, 0x4E, 0x4F, + 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5A, 0x5B, 0x5C, 0x5D, 0x5E, 0x5F, + 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6A, 0x6B, 0x6C, 0x6D, 0x6E, 0x6F, + 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79, 0x7A, 0x7B, 0x7C, 0x7D, 0x7E, 0x7F, + 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8A, 0x8B, 0x8C, 0x8D, 0x8E, 0x8F, + 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 0x9A, 0x9B, 0x9C, 0x9D, 0x9E, 0x9F, + 0xA0, 0xA1, 0xA2, 0xA3, 0xA4, 0xA5, 0xA6, 0xA7, 0xA8, 0xA9, 0xAA, 0xAB, 0xAC, 0xAD, 0xAE, 0xAF, + 0xB0, 0xB1, 0xB2, 0xB3, 0xB4, 0xB5, 0xB6, 0xB7, 0xB8, 0xB9, 0xBA, 0xBB, 0xBC, 0xBD, 0xBE, 0xBF, + 0xC0, 0xC1, 0xC2, 0xC3, 0xC4, 0xC5, 0xC6, 0xC7, 0xC8, 0xC9, 0xCA, 0xCB, 0xCC, 0xCD, 0xCE, 0xCF, + 0xD0, 0xD1, 0xD2, 0xD3, 0xD4, 0xD5, 0xD6, 0xD7, 0xD8, 0xD9, 0xDA, 0xDB, 0xDC, 0xDD, 0xDE, 0xDF, + 0xE0, 0xE1, 0xE2, 0xE3, 0xE4, 0xE5, 0xE6, 0xE7, 0xE8, 0xE9, 0xEA, 0xEB, 0xEC, 0xED, 0xEE, 0xEF, + 0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7, 0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF +}; + +//----------------------------------------------------------------------------- +// Utility Functions +//----------------------------------------------------------------------------- + +#define MAX_ROUNDS (997 * 999983) + +#ifdef ENABLE_TRACE +#define TRACE(X, ...) printf(X "\n", __VA_ARGS__) +#else +#define TRACE(X, ...) __noop() +#endif + +static inline void random_permutation(msws_t rand, uint8_t *const row_buffer) +{ + for (uint_fast16_t i = 0; i < ROW_LEN; ++i) + { + const uint_fast16_t j = msws_uint32_max(rand, i + 1U); + row_buffer[i] = row_buffer[j]; + row_buffer[j] = INDICES[i]; + } +} + +static void make_permutation(msws_t rand, const uint8_t *const rnd_buffer_1, uint8_t *const temp_buffer) +{ + bool is_valid; + do + { + random_permutation(rand, temp_buffer); + is_valid = true; + for (uint_fast16_t i = 0; i < ROW_LEN; ++i) + { + if (rnd_buffer_1[i] == temp_buffer[i]) + { + is_valid = false; + break; + } + } + } + while (!is_valid); +} + +static void dump_table(FILE *const out, const uint8_t *const rnd_buffer_1, const uint8_t *const rnd_buffer_2) +{ + fputs("uint8_t MHASH_384_TABLE_RND[2][256U] =\n{\n", out); + for (size_t i = 0; i < 2; i++) + { + fputs("\t{ ", out); + for (size_t j = 0; j < ROW_LEN; j++) + { + if (j > 0) + { + fputc(',', out); + } + fprintf(out, "0x%02X", i ? rnd_buffer_2[j] : rnd_buffer_1[j]); + } + fprintf(out, " }%s /*%2X*/\n", (!i) ? "," : " ", (uint32_t)(i % 0x100)); + } + fputs("};\n", out); +} + +static void optimize(msws_t rand, const uint8_t *const rnd_buffer_1, uint8_t *const rnd_buffer_2) +{ + uint8_t temp_buffer[ROW_LEN]; + uint_fast32_t distance = 0U; + + printf("Generating table, please wait...\n"); + for(int_fast32_t round = 0; round < MAX_ROUNDS; ++round) + { + if (!(round & 0xFFFF)) + { + printf("\r%.1f%% completed [%c]", 100.0 * (round / (double)MAX_ROUNDS), SPINNER[g_spinpos]); + g_spinpos = (g_spinpos + 1) % 4; + } + make_permutation(rand, rnd_buffer_1, temp_buffer); + const uint_fast32_t next_distance = hamming_distance(rnd_buffer_1, temp_buffer, ROW_LEN); + if (next_distance > distance) + { + TRACE("Improved: %u --> %u", distance, next_distance); + memcpy(rnd_buffer_2, temp_buffer, sizeof(uint8_t) * ROW_LEN); + round = -1; + distance = next_distance; + } + } +} + +//----------------------------------------------------------------------------- +// MAIN +//----------------------------------------------------------------------------- + +int wmain(int argc, wchar_t *argv[]) +{ + printf("MHash GenTableRND [%s]\n\n", __DATE__); + printf("HashLen: %d\n\n", HASH_LEN); + + if ((HASH_LEN % (8 * sizeof(uint32_t))) != 0) + { + crit_exit("FATAL: Hash length must be a multiple of 32 bits!"); + } + + for (uint_fast16_t i = 0; i < ROW_LEN; ++i) + { + if (INDICES[i] != ((uint8_t)i)) + { + crit_exit("FATAL: Invalid indices array detected!"); + } + } + + msws_t rand; + msws_init(rand, make_seed()); + + uint8_t rnd_buffer_1[ROW_LEN]; + uint8_t rnd_buffer_2[ROW_LEN]; + + random_permutation(rand, rnd_buffer_1); + optimize(rand, rnd_buffer_1, rnd_buffer_2); + dump_table(stdout, rnd_buffer_1, rnd_buffer_2); + + printf("\n-----\n\n"); + + printf("COMPLETED.\n\n"); + return getchar(); +} -- 2.11.0