Switch MapBlock compression to zstd (#10788)

* Add zstd support. * Rearrange serialization order * Compress entire mapblock Co-authored-by: sfan5 <sfan5@live.de>
minetest · Sep 1, 2021 · d1624a5 · d1624a5
1 parent beac4a2
commit d1624a5
Show file tree

Hide file tree

Showing 24 changed files with 493 additions and 151 deletions.
diff --git a/.github/workflows/build.yml b/.github/workflows/build.yml
@@ -227,7 +227,7 @@ jobs:
     env:
       VCPKG_VERSION: 0bf3923f9fab4001c00f0f429682a0853b5749e0
 #                    2020.11
-      vcpkg_packages: irrlicht zlib curl[winssl] openal-soft libvorbis libogg sqlite3 freetype luajit
+      vcpkg_packages: irrlicht zlib zstd curl[winssl] openal-soft libvorbis libogg sqlite3 freetype luajit
     strategy:
       fail-fast: false
       matrix:

diff --git a/.github/workflows/macos.yml b/.github/workflows/macos.yml
@@ -34,7 +34,7 @@ jobs:
       - uses: actions/checkout@v2
       - name: Install deps
         run: |
-          pkgs=(cmake freetype gettext gmp hiredis jpeg jsoncpp leveldb libogg libpng libvorbis luajit)
+          pkgs=(cmake freetype gettext gmp hiredis jpeg jsoncpp leveldb libogg libpng libvorbis luajit zstd)
           brew update
           brew install ${pkgs[@]}
           brew unlink $(brew ls --formula)

diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml
@@ -17,7 +17,7 @@ variables:
   stage: build
   before_script:
    - apt-get update
-   - apt-get -y install build-essential git cmake libpng-dev libjpeg-dev libxxf86vm-dev libgl1-mesa-dev libsqlite3-dev libleveldb-dev libogg-dev libvorbis-dev libopenal-dev libcurl4-gnutls-dev libfreetype6-dev zlib1g-dev libgmp-dev libjsoncpp-dev
+   - apt-get -y install build-essential git cmake libpng-dev libjpeg-dev libxxf86vm-dev libgl1-mesa-dev libsqlite3-dev libleveldb-dev libogg-dev libvorbis-dev libopenal-dev libcurl4-gnutls-dev libfreetype6-dev zlib1g-dev libgmp-dev libjsoncpp-dev libzstd-dev
   script:
     - git clone https://github.com/minetest/irrlicht -b $IRRLICHT_TAG lib/irrlichtmt
     - mkdir cmakebuild
@@ -187,7 +187,7 @@ build:fedora-28:
   extends: .build_template
   image: fedora:28
   before_script:
-    - dnf -y install make git gcc gcc-c++ kernel-devel cmake libjpeg-devel libpng-devel libcurl-devel openal-soft-devel libvorbis-devel libXxf86vm-devel libogg-devel freetype-devel mesa-libGL-devel zlib-devel jsoncpp-devel gmp-devel sqlite-devel luajit-devel leveldb-devel ncurses-devel spatialindex-devel
+    - dnf -y install make git gcc gcc-c++ kernel-devel cmake libjpeg-devel libpng-devel libcurl-devel openal-soft-devel libvorbis-devel libXxf86vm-devel libogg-devel freetype-devel mesa-libGL-devel zlib-devel jsoncpp-devel gmp-devel sqlite-devel luajit-devel leveldb-devel ncurses-devel spatialindex-devel libzstd-devel
 
 ##
 ## MinGW for Windows

diff --git a/Dockerfile b/Dockerfile
@@ -20,7 +20,7 @@ COPY textures /usr/src/minetest/textures
 
 WORKDIR /usr/src/minetest
 
-RUN apk add --no-cache git build-base cmake sqlite-dev curl-dev zlib-dev \
+RUN apk add --no-cache git build-base cmake sqlite-dev curl-dev zlib-dev zstd-dev \
 		gmp-dev jsoncpp-dev postgresql-dev ninja luajit-dev ca-certificates && \
 	git clone --depth=1 -b ${MINETEST_GAME_VERSION} https://github.com/minetest/minetest_game.git ./games/minetest_game && \
 	rm -fr ./games/minetest_game/.git

diff --git a/android/native/jni/Android.mk b/android/native/jni/Android.mk
@@ -57,6 +57,11 @@ LOCAL_MODULE := Vorbis
 LOCAL_SRC_FILES := deps/Android/Vorbis/${NDK_TOOLCHAIN_VERSION}/$(APP_ABI)/libvorbis.a
 include $(PREBUILT_STATIC_LIBRARY)
 
+include $(CLEAR_VARS)
+LOCAL_MODULE := Zstd
+LOCAL_SRC_FILES := deps/Android/Zstd/${NDK_TOOLCHAIN_VERSION}/$(APP_ABI)/libzstd.a
+include $(PREBUILT_STATIC_LIBRARY)
+
 include $(CLEAR_VARS)
 LOCAL_MODULE := Minetest
 
@@ -101,7 +106,8 @@ LOCAL_C_INCLUDES := \
 	deps/Android/LuaJIT/src                         \
 	deps/Android/OpenAL-Soft/include                \
 	deps/Android/sqlite                             \
-	deps/Android/Vorbis/include
+	deps/Android/Vorbis/include                     \
+	deps/Android/Zstd/include
 
 LOCAL_SRC_FILES := \
 	$(wildcard ../../src/client/*.cpp)           \
@@ -201,7 +207,7 @@ LOCAL_SRC_FILES += \
 # SQLite3
 LOCAL_SRC_FILES += deps/Android/sqlite/sqlite3.c
 
-LOCAL_STATIC_LIBRARIES += Curl Freetype Irrlicht OpenAL mbedTLS mbedx509 mbedcrypto Vorbis LuaJIT GetText android_native_app_glue $(PROFILER_LIBS) #LevelDB
+LOCAL_STATIC_LIBRARIES += Curl Freetype Irrlicht OpenAL mbedTLS mbedx509 mbedcrypto Vorbis LuaJIT GetText Zstd android_native_app_glue $(PROFILER_LIBS) #LevelDB
 
 LOCAL_LDLIBS := -lEGL -lGLESv1_CM -lGLESv2 -landroid -lOpenSLES
 

diff --git a/builtin/settingtypes.txt b/builtin/settingtypes.txt
@@ -1100,11 +1100,10 @@ full_block_send_enable_min_time_from_building (Delay in sending blocks after bui
 #    client number.
 max_packets_per_iteration (Max. packets per iteration) int 1024
 
-#    ZLib compression level to use when sending mapblocks to the client.
-#    -1 - Zlib's default compression level
-#     0 - no compresson, fastest
+#    Compression level to use when sending mapblocks to the client.
+#    -1 - use default compression level
+#     0 - least compresson, fastest
 #     9 - best compression, slowest
-#     (levels 1-3 use Zlib's "fast" method, 4-9 use the normal method)
 map_compression_level_net (Map Compression Level for Network Transfer) int -1 -1 9
 
 [*Game]
@@ -1303,12 +1302,11 @@ max_objects_per_block (Maximum objects per block) int 64
 #    See https://www.sqlite.org/pragma.html#pragma_synchronous
 sqlite_synchronous (Synchronous SQLite) enum 2 0,1,2
 
-#    ZLib compression level to use when saving mapblocks to disk.
-#    -1 - Zlib's default compression level
-#     0 - no compresson, fastest
+#    Compression level to use when saving mapblocks to disk.
+#    -1 - use default compression level
+#     0 - least compresson, fastest
 #     9 - best compression, slowest
-#     (levels 1-3 use Zlib's "fast" method, 4-9 use the normal method)
-map_compression_level_disk (Map Compression Level for Disk Storage) int 3 -1 9
+map_compression_level_disk (Map Compression Level for Disk Storage) int -1 -1 9
 
 #    Length of a server tick and the interval at which objects are generally updated over
 #    network.

diff --git a/cmake/Modules/FindZstd.cmake b/cmake/Modules/FindZstd.cmake
@@ -0,0 +1,9 @@
+mark_as_advanced(ZSTD_LIBRARY ZSTD_INCLUDE_DIR)
+
+find_path(ZSTD_INCLUDE_DIR NAMES zstd.h)
+
+find_library(ZSTD_LIBRARY NAMES zstd)
+
+include(FindPackageHandleStandardArgs)
+find_package_handle_standard_args(Zstd DEFAULT_MSG ZSTD_LIBRARY ZSTD_INCLUDE_DIR)
+
diff --git a/doc/world_format.txt b/doc/world_format.txt
@@ -1,5 +1,5 @@
 =============================
-Minetest World Format 22...27
+Minetest World Format 22...29
 =============================
 
 This applies to a world format carrying the block serialization version
@@ -8,6 +8,7 @@ This applies to a world format carrying the block serialization version
 - 0.4.0 (23)
 - 24 was never released as stable and existed for ~2 days
 - 27 was added in 0.4.15-dev
+- 29 was added in 5.5.0-dev
 
 The block serialization version does not fully specify every aspect of this
 format; if compliance with this format is to be checked, it needs to be
@@ -281,6 +282,8 @@ MapBlock serialization format
 NOTE: Byte order is MSB first (big-endian).
 NOTE: Zlib data is in such a format that Python's zlib at least can
       directly decompress.
+NOTE: Since version 29 zstd is used instead of zlib. In addition the entire
+      block is first serialized and then compressed (except the version byte).
 
 u8 version
 - map format version number, see serialisation.h for the latest number
@@ -324,6 +327,20 @@ u16 lighting_complete
   then Minetest will correct lighting in the day light bank when
   the block at (1, 0, 0) is also loaded.
 
+if map format version >= 29:
+  u32 timestamp
+  - Timestamp when last saved, as seconds from starting the game.
+  - 0xffffffff = invalid/unknown timestamp, nothing should be done with the time
+                 difference when loaded
+
+  u16 num_name_id_mappings
+  foreach num_name_id_mappings
+    u16 id
+    u16 name_len
+    u8[name_len] name
+if map format version < 29:
+  -- Nothing right here, timpstamp and node id mappings are serialized later
+
 u8 content_width
 - Number of bytes in the content (param0) fields of nodes
 if map format version <= 23:
@@ -335,7 +352,7 @@ u8 params_width
 - Number of bytes used for parameters per node
 - Always 2
 
-zlib-compressed node data:
+node data (zlib-compressed if version < 29):
 if content_width == 1:
     - content:
       u8[4096]: param0 fields
@@ -348,31 +365,31 @@ if content_width == 2:
       u8[4096]: param2 fields
 - The location of a node in each of those arrays is (z*16*16 + y*16 + x).
 
-zlib-compressed node metadata list
+node metadata list (zlib-compressed if version < 29):
 - content:
-if map format version <= 22:
-  u16 version (=1)
-  u16 count of metadata
-  foreach count:
-    u16 position (p.Z*MAP_BLOCKSIZE*MAP_BLOCKSIZE + p.Y*MAP_BLOCKSIZE + p.X)
-    u16 type_id
-    u16 content_size
-    u8[content_size] content of metadata. Format depends on type_id, see below.
-if map format version >= 23:
-  u8 version -- Note: type was u16 for map format version <= 22
-    -- = 1 for map format version < 28
-    -- = 2 since map format version 28
-  u16 count of metadata
-  foreach count:
-    u16 position (p.Z*MAP_BLOCKSIZE*MAP_BLOCKSIZE + p.Y*MAP_BLOCKSIZE + p.X)
-    u32 num_vars
-    foreach num_vars:
-      u16 key_len
-      u8[key_len] key
-      u32 val_len
-      u8[val_len] value
-      u8 is_private -- only for version >= 2. 0 = not private, 1 = private
-    serialized inventory
+  if map format version <= 22:
+    u16 version (=1)
+    u16 count of metadata
+    foreach count:
+      u16 position (p.Z*MAP_BLOCKSIZE*MAP_BLOCKSIZE + p.Y*MAP_BLOCKSIZE + p.X)
+      u16 type_id
+      u16 content_size
+      u8[content_size] content of metadata. Format depends on type_id, see below.
+  if map format version >= 23:
+    u8 version -- Note: type was u16 for map format version <= 22
+      -- = 1 for map format version < 28
+      -- = 2 since map format version 28
+    u16 count of metadata
+    foreach count:
+      u16 position (p.Z*MAP_BLOCKSIZE*MAP_BLOCKSIZE + p.Y*MAP_BLOCKSIZE + p.X)
+      u32 num_vars
+      foreach num_vars:
+        u16 key_len
+        u8[key_len] key
+        u32 val_len
+        u8[val_len] value
+        u8 is_private -- only for version >= 2. 0 = not private, 1 = private
+      serialized inventory
 
 - Node timers
 if map format version == 23:
@@ -403,20 +420,18 @@ foreach static_object_count:
   u16 data_size
   u8[data_size] data
 
-u32 timestamp
-- Timestamp when last saved, as seconds from starting the game.
-- 0xffffffff = invalid/unknown timestamp, nothing should be done with the time
-               difference when loaded
-
-u8 name-id-mapping version
-- Always 0
+if map format version < 29:
+  u32 timestamp
+  - Same meaning as the timestamp further up
 
-u16 num_name_id_mappings
+  u8 name-id-mapping version
+  - Always 0
 
-foreach num_name_id_mappings
-  u16 id
-  u16 name_len
-  u8[name_len] name
+  u16 num_name_id_mappings
+  foreach num_name_id_mappings
+    u16 id
+    u16 name_len
+    u8[name_len] name
 
 - Node timers
 if map format version == 25:

diff --git a/misc/debpkg-control b/misc/debpkg-control
@@ -3,7 +3,7 @@ Priority: extra
 Standards-Version: 3.6.2
 Package: minetest-staging
 Version: 5.4.0-DATEPLACEHOLDER
-Depends: libc6, libcurl3-gnutls, libfreetype6, libgl1, JPEG_PLACEHOLDER, JSONCPP_PLACEHOLDER, LEVELDB_PLACEHOLDER, libopenal1, libpng16-16, libsqlite3-0, libstdc++6, libvorbisfile3, libx11-6, libxxf86vm1, zlib1g
+Depends: libc6, libcurl3-gnutls, libfreetype6, libgl1, JPEG_PLACEHOLDER, JSONCPP_PLACEHOLDER, LEVELDB_PLACEHOLDER, libopenal1, libpng16-16, libsqlite3-0, libstdc++6, libvorbisfile3, libx11-6, libxxf86vm1, libzstd1, zlib1g
 Maintainer: Loic Blot <loic.blot@unix-experience.fr>
 Homepage: https://www.minetest.net/
 Vcs-Git: https://github.com/minetest/minetest.git

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
@@ -271,9 +271,13 @@ if(WIN32)
 	find_path(ZLIB_INCLUDE_DIR "zlib.h" DOC "Zlib include directory")
 	find_library(ZLIB_LIBRARIES "zlib" DOC "Path to zlib library")
 
+	find_path(ZSTD_INCLUDE_DIR "zstd.h" DOC "Zstd include directory")
+	find_library(ZSTD_LIBRARY "zstd" DOC "Path to zstd library")
+
 	# Dll's are automatically copied to the output directory by vcpkg when VCPKG_APPLOCAL_DEPS=ON
 	if(NOT VCPKG_APPLOCAL_DEPS)
 		find_file(ZLIB_DLL NAMES "zlib.dll" "zlib1.dll" DOC "Path to zlib.dll for installation (optional)")
+		find_file(ZSTD_DLL NAMES "zstd.dll" DOC "Path to zstd.dll for installation (optional)")
 		if(ENABLE_SOUND)
 			set(OPENAL_DLL "" CACHE FILEPATH "Path to OpenAL32.dll for installation (optional)")
 			set(OGG_DLL "" CACHE FILEPATH "Path to libogg.dll for installation (optional)")
@@ -296,6 +300,7 @@ else()
 	endif()
 
 	find_package(ZLIB REQUIRED)
+	find_package(Zstd REQUIRED)
 	set(PLATFORM_LIBS -lpthread ${CMAKE_DL_LIBS})
 	if(APPLE)
 		set(PLATFORM_LIBS "-framework CoreFoundation" ${PLATFORM_LIBS})
@@ -486,6 +491,7 @@ include_directories(
 	${PROJECT_BINARY_DIR}
 	${PROJECT_SOURCE_DIR}
 	${ZLIB_INCLUDE_DIR}
+	${ZSTD_INCLUDE_DIR}
 	${SOUND_INCLUDE_DIRS}
 	${SQLITE3_INCLUDE_DIR}
 	${LUA_INCLUDE_DIR}
@@ -521,6 +527,7 @@ if(BUILD_CLIENT)
 		${PROJECT_NAME}
 		${ZLIB_LIBRARIES}
 		IrrlichtMt::IrrlichtMt
+		${ZSTD_LIBRARY}
 		${X11_LIBRARIES}
 		${SOUND_LIBRARIES}
 		${SQLITE3_LIBRARY}
@@ -605,6 +612,7 @@ if(BUILD_SERVER)
 	target_link_libraries(
 		${PROJECT_NAME}server
 		${ZLIB_LIBRARIES}
+		${ZSTD_LIBRARY}
 		${SQLITE3_LIBRARY}
 		${JSON_LIBRARY}
 		${LUA_LIBRARY}
@@ -821,6 +829,9 @@ if(WIN32)
 		if(ZLIB_DLL)
 			install(FILES ${ZLIB_DLL} DESTINATION ${BINDIR})
 		endif()
+		if(ZSTD_DLL)
+			install(FILES ${ZSTD_DLL} DESTINATION ${BINDIR})
+		endif()
 		if(BUILD_CLIENT AND FREETYPE_DLL)
 			install(FILES ${FREETYPE_DLL} DESTINATION ${BINDIR})
 		endif()

diff --git a/src/defaultsettings.cpp b/src/defaultsettings.cpp
@@ -398,7 +398,7 @@ void set_default_settings()
 	settings->setDefault("chat_message_limit_per_10sec", "8.0");
 	settings->setDefault("chat_message_limit_trigger_kick", "50");
 	settings->setDefault("sqlite_synchronous", "2");
-	settings->setDefault("map_compression_level_disk", "3");
+	settings->setDefault("map_compression_level_disk", "-1");
 	settings->setDefault("map_compression_level_net", "-1");
 	settings->setDefault("full_block_send_enable_min_time_from_building", "2.0");
 	settings->setDefault("dedicated_server_step", "0.09");
@@ -484,7 +484,7 @@ void set_default_settings()
 	settings->setDefault("max_objects_per_block", "20");
 	settings->setDefault("sqlite_synchronous", "1");
 	settings->setDefault("map_compression_level_disk", "-1");
-	settings->setDefault("map_compression_level_net", "3");
+	settings->setDefault("map_compression_level_net", "-1");
 	settings->setDefault("server_map_save_interval", "15");
 	settings->setDefault("client_mapblock_limit", "1000");
 	settings->setDefault("active_block_range", "2");