From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from [87.239.111.99] (localhost [127.0.0.1]) by dev.tarantool.org (Postfix) with ESMTP id 38C146FC83; Fri, 20 Aug 2021 14:10:43 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 38C146FC83 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=tarantool.org; s=dev; t=1629457843; bh=34sGxw7HAXZUjHiTdUga56CVgANG1CXVkID/JXcPQw4=; h=To:Date:In-Reply-To:References:Subject:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=YWB5XoiDcYxf0nEljcEX8uUUMA+FI0IQZY7C6HZdhwvFefUhYz30VChVOYk4aN8L6 lsUJr8JfDlRF27X7qYNWfiyuSRHRQQFN+Yuwy8T02TyEqciRTQMTM9GBysHA9pz7Zn EWiQ1NBg3VB8uhX8Ih2yM06+juULWiyp1xnNH7/g= Received: from mail-lf1-f49.google.com (mail-lf1-f49.google.com [209.85.167.49]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id 9A9716FC83 for ; Fri, 20 Aug 2021 14:10:41 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 9A9716FC83 Received: by mail-lf1-f49.google.com with SMTP id o1so1592066lft.9 for ; Fri, 20 Aug 2021 04:10:41 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=kxEKXIJ9AvZFMPiS2dY7zDMLTkadsEHPJVxHv/c1sak=; b=k1lig5JVybijZtOtPaQuFyMhn4EdwhQHvFqd5Zb5HnPRUK0toE862REDeV8xHhJe9D s0yYogTDASk2Tox+ZWVxii+4vR0LtA9mQilOGnI74kJ4hq1pnABZOcT0REmC2x1Td3Xq xURw4NOK1FhZtCTrDaGffEcTz3ZGRoOe2eVE3EddfMpfNyxySYahoj+/MHYbXkA2u4km IOCFd2hjz7gBiHNw7vWqJCFoTTAqm9FaEM7KIElLV/TGB8NYCgpju9Aa9a/0ZjHSQE9O 3ADPptjj8q9nmtIpaeVfYr6Vp9yTB2jMbDrLAleMV602DMzE7mt0NVq7Y1u8J6iUEQ8v i97Q== X-Gm-Message-State: AOAM532VhVReu6b8A99Y0DWXfyqWhH5qOswLC5xpZIjnBNAvqhHvkm6l ekcRzac6C5yFGBo7LhSi8JTypSjcmP2Zto9U X-Google-Smtp-Source: ABdhPJxlPg19Jijxi/eWE8MoNIWmBIZqshXLjI/NE95bsswqiFBq4A4XgcS+AlurEfyQimNYWPBSlw== X-Received: by 2002:a05:6512:11ea:: with SMTP id p10mr14748364lfs.152.1629457840733; Fri, 20 Aug 2021 04:10:40 -0700 (PDT) Received: from localhost.localdomain ([93.175.2.170]) by smtp.gmail.com with ESMTPSA id k15sm183951lfv.141.2021.08.20.04.10.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 20 Aug 2021 04:10:40 -0700 (PDT) X-Google-Original-From: Maxim Kokryashkin To: tarantool-patches@dev.tarantool.org, imun@tarantool.org, skaplun@tarantool.org Date: Fri, 20 Aug 2021 14:10:32 +0300 Message-Id: <5f67b8ba222f1071ee3f989353a14361c7fb1676.1629457244.git.m.kokryashkin@tarantool.org> X-Mailer: git-send-email 2.32.0 In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: [Tarantool-patches] [PATCH luajit v2 1/3] utils: add CRC32 hash implementation X-BeenThere: tarantool-patches@dev.tarantool.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , From: Maxim Kokryashkin via Tarantool-patches Reply-To: Maxim Kokryashkin Errors-To: tarantool-patches-bounces@dev.tarantool.org Sender: "Tarantool-patches" 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: > 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. >> +#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 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 +#include + +#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