From a92377197803a04f008bf66ccc995e8c6a4140cc Mon Sep 17 00:00:00 2001
From: Sam Lantinga <[EMAIL REDACTED]>
Date: Sat, 28 Sep 2024 15:49:01 -0700
Subject: [PATCH] Added SDL_murmur3_32()
---
VisualC-GDK/SDL/SDL.vcxproj | 1 +
VisualC-GDK/SDL/SDL.vcxproj.filters | 1 +
VisualC/SDL/SDL.vcxproj | 1 +
VisualC/SDL/SDL.vcxproj.filters | 3 +
Xcode/SDL/SDL.xcodeproj/project.pbxproj | 4 ++
include/SDL3/SDL_stdinc.h | 1 +
src/dynapi/SDL_dynapi.sym | 1 +
src/dynapi/SDL_dynapi_overrides.h | 1 +
src/dynapi/SDL_dynapi_procs.h | 1 +
src/stdlib/SDL_murmur3.c | 87 +++++++++++++++++++++++++
10 files changed, 101 insertions(+)
create mode 100644 src/stdlib/SDL_murmur3.c
diff --git a/VisualC-GDK/SDL/SDL.vcxproj b/VisualC-GDK/SDL/SDL.vcxproj
index d6f85d2cde9c6..c779b40ccea90 100644
--- a/VisualC-GDK/SDL/SDL.vcxproj
+++ b/VisualC-GDK/SDL/SDL.vcxproj
@@ -816,6 +816,7 @@
<MASM Condition="'$(Platform)'=='x64'" Include="..\..\src\stdlib\SDL_mslibc_x64.masm">
<PrecompiledHeader>NotUsing</PrecompiledHeader>
</MASM>
+ <ClCompile Include="..\..\src\stdlib\SDL_murmur3.c" />
<ClCompile Include="..\..\src\stdlib\SDL_qsort.c" />
<ClCompile Include="..\..\src\stdlib\SDL_random.c" />
<ClCompile Include="..\..\src\stdlib\SDL_stdlib.c" />
diff --git a/VisualC-GDK/SDL/SDL.vcxproj.filters b/VisualC-GDK/SDL/SDL.vcxproj.filters
index e697a3e948e64..46d3b47750832 100644
--- a/VisualC-GDK/SDL/SDL.vcxproj.filters
+++ b/VisualC-GDK/SDL/SDL.vcxproj.filters
@@ -174,6 +174,7 @@
<ClCompile Include="..\..\src\stdlib\SDL_memmove.c" />
<ClCompile Include="..\..\src\stdlib\SDL_memset.c" />
<ClCompile Include="..\..\src\stdlib\SDL_mslibc.c" />
+ <ClCompile Include="..\..\src\stdlib\SDL_murmur3.c" />
<ClCompile Include="..\..\src\stdlib\SDL_qsort.c" />
<ClCompile Include="..\..\src\stdlib\SDL_random.c" />
<ClCompile Include="..\..\src\stdlib\SDL_stdlib.c" />
diff --git a/VisualC/SDL/SDL.vcxproj b/VisualC/SDL/SDL.vcxproj
index b53a602232aea..a6371238f965c 100644
--- a/VisualC/SDL/SDL.vcxproj
+++ b/VisualC/SDL/SDL.vcxproj
@@ -668,6 +668,7 @@
<MASM Condition="'$(Platform)'=='x64'" Include="..\..\src\stdlib\SDL_mslibc_x64.masm">
<PrecompiledHeader>NotUsing</PrecompiledHeader>
</MASM>
+ <ClCompile Include="..\..\src\stdlib\SDL_murmur3.c" />
<ClCompile Include="..\..\src\stdlib\SDL_qsort.c" />
<ClCompile Include="..\..\src\stdlib\SDL_random.c" />
<ClCompile Include="..\..\src\stdlib\SDL_stdlib.c" />
diff --git a/VisualC/SDL/SDL.vcxproj.filters b/VisualC/SDL/SDL.vcxproj.filters
index d62aa47b7147d..ada794006fb9c 100644
--- a/VisualC/SDL/SDL.vcxproj.filters
+++ b/VisualC/SDL/SDL.vcxproj.filters
@@ -1448,6 +1448,9 @@
<ClCompile Include="..\..\src\stdlib\SDL_memset.c">
<Filter>stdlib</Filter>
</ClCompile>
+ <ClCompile Include="..\..\src\stdlib\SDL_murmur3.c">
+ <Filter>stdlib</Filter>
+ </ClCompile>
<ClCompile Include="..\..\src\stdlib\SDL_qsort.c">
<Filter>stdlib</Filter>
</ClCompile>
diff --git a/Xcode/SDL/SDL.xcodeproj/project.pbxproj b/Xcode/SDL/SDL.xcodeproj/project.pbxproj
index 01d014224656c..1cf52e0543ed9 100644
--- a/Xcode/SDL/SDL.xcodeproj/project.pbxproj
+++ b/Xcode/SDL/SDL.xcodeproj/project.pbxproj
@@ -62,6 +62,7 @@
566E26D8246274CC00718109 /* SDL_locale.c in Sources */ = {isa = PBXBuildFile; fileRef = 566E26CD246274CB00718109 /* SDL_locale.c */; };
566E26E1246274CC00718109 /* SDL_syslocale.h in Headers */ = {isa = PBXBuildFile; fileRef = 566E26CE246274CC00718109 /* SDL_syslocale.h */; };
56A2373329F9C113003CCA5F /* SDL_sysrwlock.c in Sources */ = {isa = PBXBuildFile; fileRef = 56A2373229F9C113003CCA5F /* SDL_sysrwlock.c */; };
+ 6312C66D2B42341400A7BB00 /* SDL_murmur3.c in Sources */ = {isa = PBXBuildFile; fileRef = 6312C66C2B42341400A7BB00 /* SDL_murmur3.c */; };
63134A222A7902CF0021E9A6 /* SDL_pen.h in Headers */ = {isa = PBXBuildFile; fileRef = 63134A212A7902CF0021E9A6 /* SDL_pen.h */; settings = {ATTRIBUTES = (Public, ); }; };
63134A252A7902FD0021E9A6 /* SDL_pen_c.h in Headers */ = {isa = PBXBuildFile; fileRef = 63134A232A7902FD0021E9A6 /* SDL_pen_c.h */; };
63134A262A7902FD0021E9A6 /* SDL_pen.c in Sources */ = {isa = PBXBuildFile; fileRef = 63134A242A7902FD0021E9A6 /* SDL_pen.c */; };
@@ -606,6 +607,7 @@
566E26CD246274CB00718109 /* SDL_locale.c */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.c; name = SDL_locale.c; path = locale/SDL_locale.c; sourceTree = "<group>"; };
566E26CE246274CC00718109 /* SDL_syslocale.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SDL_syslocale.h; path = locale/SDL_syslocale.h; sourceTree = "<group>"; };
56A2373229F9C113003CCA5F /* SDL_sysrwlock.c */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.c; path = SDL_sysrwlock.c; sourceTree = "<group>"; };
+ 6312C66C2B42341400A7BB00 /* SDL_murmur3.c */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.c; path = SDL_murmur3.c; sourceTree = "<group>"; };
63134A212A7902CF0021E9A6 /* SDL_pen.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SDL_pen.h; path = SDL3/SDL_pen.h; sourceTree = "<group>"; };
63134A232A7902FD0021E9A6 /* SDL_pen_c.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SDL_pen_c.h; sourceTree = "<group>"; };
63134A242A7902FD0021E9A6 /* SDL_pen.c */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.c; path = SDL_pen.c; sourceTree = "<group>"; };
@@ -2097,6 +2099,7 @@
A7D8A8D223E2514000DCD162 /* stdlib */ = {
isa = PBXGroup;
children = (
+ 6312C66C2B42341400A7BB00 /* SDL_murmur3.c */,
F3973FA128A59BDD00B84553 /* SDL_crc16.c */,
F395BF6425633B2400942BFF /* SDL_crc32.c */,
F310138A2C1F2CB700FBE946 /* SDL_getenv_c.h */,
@@ -3054,6 +3057,7 @@
000095FA1BDE436CF3AF0000 /* SDL_time.c in Sources */,
0000140640E77F73F1DF0000 /* SDL_dialog_utils.c in Sources */,
0000D5B526B85DE7AB1C0000 /* SDL_cocoapen.m in Sources */,
+ 6312C66D2B42341400A7BB00 /* SDL_murmur3.c in Sources */,
);
runOnlyForDeploymentPostprocessing = 0;
};
diff --git a/include/SDL3/SDL_stdinc.h b/include/SDL3/SDL_stdinc.h
index c83a0b90f5e7c..7eec1fd1cfbc4 100644
--- a/include/SDL3/SDL_stdinc.h
+++ b/include/SDL3/SDL_stdinc.h
@@ -1460,6 +1460,7 @@ extern SDL_DECLSPEC int SDLCALL SDL_tolower(int x);
extern SDL_DECLSPEC Uint16 SDLCALL SDL_crc16(Uint16 crc, const void *data, size_t len);
extern SDL_DECLSPEC Uint32 SDLCALL SDL_crc32(Uint32 crc, const void *data, size_t len);
+extern SDL_DECLSPEC Uint32 SDLCALL SDL_murmur3_32(const void *data, size_t len, Uint32 seed);
/**
* Copy non-overlapping memory.
diff --git a/src/dynapi/SDL_dynapi.sym b/src/dynapi/SDL_dynapi.sym
index c9d06105eb7dc..2b6bd0c2e45a7 100644
--- a/src/dynapi/SDL_dynapi.sym
+++ b/src/dynapi/SDL_dynapi.sym
@@ -1097,6 +1097,7 @@ SDL3_0.0.0 {
SDL_memset;
SDL_modf;
SDL_modff;
+ SDL_murmur3_32;
SDL_pow;
SDL_powf;
SDL_qsort;
diff --git a/src/dynapi/SDL_dynapi_overrides.h b/src/dynapi/SDL_dynapi_overrides.h
index b0f3250e4a2fc..44e7c67d58c76 100644
--- a/src/dynapi/SDL_dynapi_overrides.h
+++ b/src/dynapi/SDL_dynapi_overrides.h
@@ -1122,6 +1122,7 @@
#define SDL_memset4 SDL_memset4_REAL
#define SDL_modf SDL_modf_REAL
#define SDL_modff SDL_modff_REAL
+#define SDL_murmur3_32 SDL_murmur3_32_REAL
#define SDL_pow SDL_pow_REAL
#define SDL_powf SDL_powf_REAL
#define SDL_qsort SDL_qsort_REAL
diff --git a/src/dynapi/SDL_dynapi_procs.h b/src/dynapi/SDL_dynapi_procs.h
index 88274b6f720e0..bdba993f16498 100644
--- a/src/dynapi/SDL_dynapi_procs.h
+++ b/src/dynapi/SDL_dynapi_procs.h
@@ -1131,6 +1131,7 @@ SDL_DYNAPI_PROC(void*,SDL_memset,(SDL_OUT_BYTECAP(c) void *a, int b, size_t c),(
SDL_DYNAPI_PROC(void*,SDL_memset4,(void *a, Uint32 b, size_t c),(a,b,c),return)
SDL_DYNAPI_PROC(double,SDL_modf,(double a, double *b),(a,b),return)
SDL_DYNAPI_PROC(float,SDL_modff,(float a, float *b),(a,b),return)
+SDL_DYNAPI_PROC(Uint32,SDL_murmur3_32,(const void *a, size_t b, Uint32 c),(a,b,c),return)
SDL_DYNAPI_PROC(double,SDL_pow,(double a, double b),(a,b),return)
SDL_DYNAPI_PROC(float,SDL_powf,(float a, float b),(a,b),return)
SDL_DYNAPI_PROC(void,SDL_qsort,(void *a, size_t b, size_t c, SDL_CompareCallback d),(a,b,c,d),)
diff --git a/src/stdlib/SDL_murmur3.c b/src/stdlib/SDL_murmur3.c
new file mode 100644
index 0000000000000..59e879c15c342
--- /dev/null
+++ b/src/stdlib/SDL_murmur3.c
@@ -0,0 +1,87 @@
+/*
+ Simple DirectMedia Layer
+ Copyright (C) 1997-2024 Sam Lantinga <slouken@libsdl.org>
+
+ This software is provided 'as-is', without any express or implied
+ warranty. In no event will the authors be held liable for any damages
+ arising from the use of this software.
+
+ Permission is granted to anyone to use this software for any purpose,
+ including commercial applications, and to alter it and redistribute it
+ freely, subject to the following restrictions:
+
+ 1. The origin of this software must not be misrepresented; you must not
+ claim that you wrote the original software. If you use this software
+ in a product, an acknowledgment in the product documentation would be
+ appreciated but is not required.
+ 2. Altered source versions must be plainly marked as such, and must not be
+ misrepresented as being the original software.
+ 3. This notice may not be removed or altered from any source distribution.
+*/
+#include "SDL_internal.h"
+
+// Public domain murmur3 32-bit hash algorithm
+//
+// Adapted from: https://en.wikipedia.org/wiki/MurmurHash
+
+static SDL_INLINE Uint32 murmur_32_scramble(Uint32 k)
+{
+ k *= 0xcc9e2d51;
+ k = (k << 15) | (k >> 17);
+ k *= 0x1b873593;
+ return k;
+}
+
+Uint32 SDLCALL SDL_murmur3_32(const void *data, size_t len, Uint32 seed)
+{
+ const Uint8 *bytes = (const Uint8 *)data;
+ Uint32 hash = seed;
+ Uint32 k;
+
+ // Read in groups of 4.
+ if ((((uintptr_t)bytes) & 3) == 0) {
+ // We can do aligned 32-bit reads
+ for (size_t i = len >> 2; i--; ) {
+ k = *(const Uint32 *)bytes;
+ k = SDL_Swap32LE(k);
+ bytes += sizeof(Uint32);
+ hash ^= murmur_32_scramble(k);
+ hash = (hash << 13) | (hash >> 19);
+ hash = hash * 5 + 0xe6546b64;
+ }
+ } else {
+ for (size_t i = len >> 2; i--; ) {
+ SDL_memcpy(&k, bytes, sizeof(Uint32));
+ k = SDL_Swap32LE(k);
+ bytes += sizeof(Uint32);
+ hash ^= murmur_32_scramble(k);
+ hash = (hash << 13) | (hash >> 19);
+ hash = hash * 5 + 0xe6546b64;
+ }
+ }
+
+ // Read the rest.
+ size_t left = (len & 3);
+ if (left) {
+ k = 0;
+ for (size_t i = left; i--; ) {
+ k <<= 8;
+ k |= bytes[i];
+ }
+
+ // A swap is *not* necessary here because the preceding loop already
+ // places the low bytes in the low places according to whatever endianness
+ // we use. Swaps only apply when the memory is copied in a chunk.
+ hash ^= murmur_32_scramble(k);
+ }
+
+ /* Finalize. */
+ hash ^= len;
+ hash ^= hash >> 16;
+ hash *= 0x85ebca6b;
+ hash ^= hash >> 13;
+ hash *= 0xc2b2ae35;
+ hash ^= hash >> 16;
+
+ return hash;
+}