[Tarantool-patches] [PATCH luajit v2 1/3] utils: add CRC32 hash implementation

[Maxim Kokryashkin via Tarantool-patches <tarantool-patches@dev.tarantool.org>]

This commit adds an implementation of the CRC32 hash. The
implementation is taken from GNU libberty so it differs from the
classic CRC32 implementation. The values are not reflected, and there
is no final XOR value. These differences make it easy to compose the
values of multiple blocks.

That hash implementation will be used in the memprof's symtab later on.

Part of tarantool/tarantool#5813
---
On 28.07.21 Sergey Kaplun wrote:

<snipped>

> IINM we should compare this approach with a full dump of all .so
> functions. May you provide some benches of your approach against the
> aforementioned?
As for benchmarks, I'll provide them later in the separate letter.

<snipped>

>> +#define _GNU_SOURCE
> Locally, I need to define not _GNU_SOURCE, but __USE_GNU. May you please
> check what exactly define is required and why?
Defining __USE_GNU by yourself is a terrible practice as it is an 
internal definition of the glibc. Consodering this, you should stick
to _GNU_SOURCE

<snipped>

 src/CMakeLists.txt        |   1 +
 src/Makefile.dep.original |   3 +-
 src/Makefile.original     |   2 +-
 src/lj_utils.h            |  29 ++++++++++
 src/lj_utils_hash.c       | 110 ++++++++++++++++++++++++++++++++++++++
 src/ljamalg.c             |   1 +
 6 files changed, 144 insertions(+), 2 deletions(-)
 create mode 100644 src/lj_utils_hash.c

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 809aac68..74c7a205 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -60,6 +60,7 @@ make_source_list(SOURCES_UTILS
   SOURCES
     lj_alloc.c
     lj_char.c
+    lj_utils_hash.c
     lj_utils_leb128.c
     lj_vmmath.c
     lj_wbuf.c
diff --git a/src/Makefile.dep.original b/src/Makefile.dep.original
index f3672413..3dc6e9b4 100644
--- a/src/Makefile.dep.original
+++ b/src/Makefile.dep.original
@@ -208,6 +208,7 @@ lj_trace.o: lj_trace.c lj_obj.h lua.h luaconf.h lj_def.h lj_arch.h \
  lj_vm.h lj_vmevent.h lj_target.h lj_target_*.h
 lj_udata.o: lj_udata.c lj_obj.h lua.h luaconf.h lj_def.h lj_arch.h \
  lj_gc.h lj_udata.h
+lj_utils_hash.o: lj_utils_hash.c lj_utils.h
 lj_utils_leb128.o: lj_utils_leb128.c lj_utils.h lj_def.h lua.h luaconf.h
 lj_vmevent.o: lj_vmevent.c lj_obj.h lua.h luaconf.h lj_def.h lj_arch.h \
  lj_str.h lj_tab.h lj_state.h lj_dispatch.h lj_bc.h lj_jit.h lj_ir.h \
@@ -234,7 +235,7 @@ ljamalg.o: ljamalg.c lua.h luaconf.h lauxlib.h lj_gc.c lj_obj.h lj_def.h \
  lj_snap.h lj_opt_split.c lj_opt_sink.c lj_mcode.c lj_snap.c lj_record.c \
  lj_record.h lj_ffrecord.h lj_crecord.c lj_crecord.h lj_ffrecord.c lj_recdef.h \
  lj_asm.c lj_asm.h lj_emit_*.h lj_asm_*.h lj_trace.c lj_gdbjit.h lj_gdbjit.c \
- lj_alloc.c lj_utils_leb128.c lib_aux.c lib_base.c lj_libdef.h lib_math.c \
+ lj_alloc.c lj_utils_hash.c lj_utils_leb128.c lib_aux.c lib_base.c lj_libdef.h lib_math.c \
  lib_string.c lib_table.c lib_io.c lib_os.c lib_package.c lib_debug.c \
  lib_bit.c lib_jit.c lib_ffi.c lib_misc.c lib_init.c
 luajit.o: luajit.c lua.h luaconf.h lauxlib.h lualib.h luajit.h lj_arch.h
diff --git a/src/Makefile.original b/src/Makefile.original
index 031f0778..2a57c022 100644
--- a/src/Makefile.original
+++ b/src/Makefile.original
@@ -498,7 +498,7 @@ LJCORE_O= lj_gc.o lj_err.o lj_char.o lj_bc.o lj_obj.o lj_buf.o lj_wbuf.o \
 	  lj_asm.o lj_trace.o lj_gdbjit.o \
 	  lj_ctype.o lj_cdata.o lj_cconv.o lj_ccall.o lj_ccallback.o \
 	  lj_carith.o lj_clib.o lj_cparse.o \
-	  lj_lib.o lj_alloc.o lj_utils_leb128.o lib_aux.o \
+	  lj_lib.o lj_alloc.o lj_utils_hash.o lj_utils_leb128.o lib_aux.o \
 	  $(LJLIB_O) lib_init.o
 
 LJVMCORE_O= $(LJVM_O) $(LJCORE_O)
diff --git a/src/lj_utils.h b/src/lj_utils.h
index f5c15797..fe179753 100644
--- a/src/lj_utils.h
+++ b/src/lj_utils.h
@@ -5,6 +5,30 @@
 ** Copyright (C) 2015-2019 IPONWEB Ltd.
 */
 
+/*
+** Copyright (C) 2009-2021 Free Software Foundation, Inc.
+** This file is part of the libiberty library.
+** This file is free software; you can redistribute it and/or modify
+** it under the terms of the GNU General Public License as published by
+** the Free Software Foundation; either version 2 of the License, or
+** (at your option) any later version.
+** In addition to the permissions in the GNU General Public License, the
+** Free Software Foundation gives you unlimited permission to link the
+** compiled version of this file into combinations with other programs,
+** and to distribute those combinations without any restriction coming
+** from the use of this file.  (The General Public License restrictions
+** do apply in other respects; for example, they cover modification of
+** the file, and distribution when not linked into a combined
+** executable.)
+** This program is distributed in the hope that it will be useful,
+** but WITHOUT ANY WARRANTY; without even the implied warranty of
+** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+** GNU General Public License for more details.
+** You should have received a copy of the GNU General Public License
+** along with this program; if not, write to the Free Software
+** Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA.
+*/
+
 #ifndef _LJ_UTILS_H
 #define _LJ_UTILS_H
 
@@ -55,4 +79,9 @@ size_t LJ_FASTCALL lj_utils_write_leb128(uint8_t *buffer, int64_t value);
 */
 size_t LJ_FASTCALL lj_utils_write_uleb128(uint8_t *buffer, uint64_t value);
 
+/*
+** Calculates CRC32 hash of a data in a buffer of a known length.
+** Checks if the buffer is NULL, corresponding assertion fails in that case.
+*/
+uint32_t lj_utils_crc32(const char *buf, size_t len, uint32_t init);
 #endif
diff --git a/src/lj_utils_hash.c b/src/lj_utils_hash.c
new file mode 100644
index 00000000..8a7f0869
--- /dev/null
+++ b/src/lj_utils_hash.c
@@ -0,0 +1,110 @@
+/*
+** Copyright (C) 2009-2021 Free Software Foundation, Inc.
+** This file is part of the libiberty library.
+** This file is free software; you can redistribute it and/or modify
+** it under the terms of the GNU General Public License as published by
+** the Free Software Foundation; either version 2 of the License, or
+** (at your option) any later version.
+** In addition to the permissions in the GNU General Public License, the
+** Free Software Foundation gives you unlimited permission to link the
+** compiled version of this file into combinations with other programs,
+** and to distribute those combinations without any restriction coming
+** from the use of this file.  (The General Public License restrictions
+** do apply in other respects; for example, they cover modification of
+** the file, and distribution when not linked into a combined
+** executable.)
+** This program is distributed in the hope that it will be useful,
+** but WITHOUT ANY WARRANTY; without even the implied warranty of
+** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+** GNU General Public License for more details.
+** You should have received a copy of the GNU General Public License
+** along with this program; if not, write to the Free Software
+** Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA.
+*/
+
+#define lj_utils_hash
+
+#include <stdio.h>
+#include <assert.h>
+
+#include "lj_utils.h"
+
+static const uint32_t crc32_table[] =
+{
+  0x00000000, 0x04c11db7, 0x09823b6e, 0x0d4326d9,
+  0x130476dc, 0x17c56b6b, 0x1a864db2, 0x1e475005,
+  0x2608edb8, 0x22c9f00f, 0x2f8ad6d6, 0x2b4bcb61,
+  0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd,
+  0x4c11db70, 0x48d0c6c7, 0x4593e01e, 0x4152fda9,
+  0x5f15adac, 0x5bd4b01b, 0x569796c2, 0x52568b75,
+  0x6a1936c8, 0x6ed82b7f, 0x639b0da6, 0x675a1011,
+  0x791d4014, 0x7ddc5da3, 0x709f7b7a, 0x745e66cd,
+  0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039,
+  0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5,
+  0xbe2b5b58, 0xbaea46ef, 0xb7a96036, 0xb3687d81,
+  0xad2f2d84, 0xa9ee3033, 0xa4ad16ea, 0xa06c0b5d,
+  0xd4326d90, 0xd0f37027, 0xddb056fe, 0xd9714b49,
+  0xc7361b4c, 0xc3f706fb, 0xceb42022, 0xca753d95,
+  0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1,
+  0xe13ef6f4, 0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d,
+  0x34867077, 0x30476dc0, 0x3d044b19, 0x39c556ae,
+  0x278206ab, 0x23431b1c, 0x2e003dc5, 0x2ac12072,
+  0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16,
+  0x018aeb13, 0x054bf6a4, 0x0808d07d, 0x0cc9cdca,
+  0x7897ab07, 0x7c56b6b0, 0x71159069, 0x75d48dde,
+  0x6b93dddb, 0x6f52c06c, 0x6211e6b5, 0x66d0fb02,
+  0x5e9f46bf, 0x5a5e5b08, 0x571d7dd1, 0x53dc6066,
+  0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba,
+  0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e,
+  0xbfa1b04b, 0xbb60adfc, 0xb6238b25, 0xb2e29692,
+  0x8aad2b2f, 0x8e6c3698, 0x832f1041, 0x87ee0df6,
+  0x99a95df3, 0x9d684044, 0x902b669d, 0x94ea7b2a,
+  0xe0b41de7, 0xe4750050, 0xe9362689, 0xedf73b3e,
+  0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2,
+  0xc6bcf05f, 0xc27dede8, 0xcf3ecb31, 0xcbffd686,
+  0xd5b88683, 0xd1799b34, 0xdc3abded, 0xd8fba05a,
+  0x690ce0ee, 0x6dcdfd59, 0x608edb80, 0x644fc637,
+  0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb,
+  0x4f040d56, 0x4bc510e1, 0x46863638, 0x42472b8f,
+  0x5c007b8a, 0x58c1663d, 0x558240e4, 0x51435d53,
+  0x251d3b9e, 0x21dc2629, 0x2c9f00f0, 0x285e1d47,
+  0x36194d42, 0x32d850f5, 0x3f9b762c, 0x3b5a6b9b,
+  0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff,
+  0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623,
+  0xf12f560e, 0xf5ee4bb9, 0xf8ad6d60, 0xfc6c70d7,
+  0xe22b20d2, 0xe6ea3d65, 0xeba91bbc, 0xef68060b,
+  0xd727bbb6, 0xd3e6a601, 0xdea580d8, 0xda649d6f,
+  0xc423cd6a, 0xc0e2d0dd, 0xcda1f604, 0xc960ebb3,
+  0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7,
+  0xae3afba2, 0xaafbe615, 0xa7b8c0cc, 0xa379dd7b,
+  0x9b3660c6, 0x9ff77d71, 0x92b45ba8, 0x9675461f,
+  0x8832161a, 0x8cf30bad, 0x81b02d74, 0x857130c3,
+  0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640,
+  0x4e8ee645, 0x4a4ffbf2, 0x470cdd2b, 0x43cdc09c,
+  0x7b827d21, 0x7f436096, 0x7200464f, 0x76c15bf8,
+  0x68860bfd, 0x6c47164a, 0x61043093, 0x65c52d24,
+  0x119b4be9, 0x155a565e, 0x18197087, 0x1cd86d30,
+  0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec,
+  0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088,
+  0x2497d08d, 0x2056cd3a, 0x2d15ebe3, 0x29d4f654,
+  0xc5a92679, 0xc1683bce, 0xcc2b1d17, 0xc8ea00a0,
+  0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb, 0xdbee767c,
+  0xe3a1cbc1, 0xe760d676, 0xea23f0af, 0xeee2ed18,
+  0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4,
+  0x89b8fd09, 0x8d79e0be, 0x803ac667, 0x84fbdbd0,
+  0x9abc8bd5, 0x9e7d9662, 0x933eb0bb, 0x97ffad0c,
+  0xafb010b1, 0xab710d06, 0xa6322bdf, 0xa2f33668,
+  0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4
+};
+
+uint32_t lj_utils_crc32 (const char *buf, size_t len, uint32_t init)
+{
+  assert(buf != NULL);
+
+  uint32_t crc = init;
+  while (len--) {
+    crc = (crc << 8) ^ crc32_table[((crc >> 24) ^ *buf) & 255];
+    buf++;
+  }
+  return crc;
+}
diff --git a/src/ljamalg.c b/src/ljamalg.c
index 3f7e6860..3a667a68 100644
--- a/src/ljamalg.c
+++ b/src/ljamalg.c
@@ -83,6 +83,7 @@
 #include "lj_trace.c"
 #include "lj_gdbjit.c"
 #include "lj_alloc.c"
+#include "lj_utils_hash.c"
 #include "lj_utils_leb128.c"
 
 #include "lib_aux.c"
-- 
2.32.0