From 694878996926ba75373d62c9a8011c1b01a1cb0b Mon Sep 17 00:00:00 2001 From: Nathan Moinvaziri Date: Thu, 10 Jun 2021 17:25:27 -0700 Subject: [PATCH] Added rolling hash functions for hash table. --- CMakeLists.txt | 1 + Makefile.in | 2 ++ arch/arm/insert_string_acle.c | 8 +++-- arch/x86/insert_string_sse.c | 14 +++++--- deflate.c | 1 + deflate.h | 2 ++ insert_string.c | 20 +++++------ insert_string_roll.c | 24 +++++++++++++ insert_string_tpl.h | 67 +++++++++++++++++++---------------- win32/Makefile.a64 | 1 + win32/Makefile.arm | 1 + win32/Makefile.msc | 1 + 12 files changed, 93 insertions(+), 49 deletions(-) create mode 100644 insert_string_roll.c diff --git a/CMakeLists.txt b/CMakeLists.txt index b477ff37..678f9e3e 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -821,6 +821,7 @@ set(ZLIB_SRCS inflate.c inftrees.c insert_string.c + insert_string_roll.c trees.c uncompr.c zutil.c diff --git a/Makefile.in b/Makefile.in index 2c70ee1d..379cab52 100644 --- a/Makefile.in +++ b/Makefile.in @@ -92,6 +92,7 @@ OBJZ = \ inflate.o \ inftrees.o \ insert_string.o \ + insert_string_roll.o \ trees.o \ uncompr.o \ zutil.o \ @@ -125,6 +126,7 @@ PIC_OBJZ = \ inflate.lo \ inftrees.lo \ insert_string.lo \ + insert_string_roll.lo \ trees.lo \ uncompr.lo \ zutil.lo \ diff --git a/arch/arm/insert_string_acle.c b/arch/arm/insert_string_acle.c index 2daf9ba3..de990238 100644 --- a/arch/arm/insert_string_acle.c +++ b/arch/arm/insert_string_acle.c @@ -1,4 +1,4 @@ -/* insert_string_acle.c -- insert_string variant using ACLE's CRC instructions +/* insert_string_acle.c -- insert_string integer hash variant using ACLE's CRC instructions * * Copyright (C) 1995-2013 Jean-loup Gailly and Mark Adler * For conditions of distribution and use, see copyright notice in zlib.h @@ -12,9 +12,13 @@ #include "../../zbuild.h" #include "../../deflate.h" -#define UPDATE_HASH(s, h, val) \ +#define HASH_CALC(s, h, val) \ h = __crc32w(0, val) +#define HASH_CALC_VAR h +#define HASH_CALC_VAR_INIT uint32_t h = 0 + +#define UPDATE_HASH update_hash_acle #define INSERT_STRING insert_string_acle #define QUICK_INSERT_STRING quick_insert_string_acle diff --git a/arch/x86/insert_string_sse.c b/arch/x86/insert_string_sse.c index d0c316b1..7a63b2a7 100644 --- a/arch/x86/insert_string_sse.c +++ b/arch/x86/insert_string_sse.c @@ -1,4 +1,4 @@ -/* insert_string_sse -- insert_string variant using SSE4.2's CRC instructions +/* insert_string_sse.c -- insert_string integer hash variant using SSE4.2's CRC instructions * * Copyright (C) 1995-2013 Jean-loup Gailly and Mark Adler * For conditions of distribution and use, see copyright notice in zlib.h @@ -14,22 +14,22 @@ #ifdef X86_SSE42_CRC_INTRIN # ifdef _MSC_VER -# define UPDATE_HASH(s, h, val)\ +# define HASH_CALC(s, h, val)\ h = _mm_crc32_u32(h, val) # else -# define UPDATE_HASH(s, h, val)\ +# define HASH_CALC(s, h, val)\ h = __builtin_ia32_crc32si(h, val) # endif #else # ifdef _MSC_VER -# define UPDATE_HASH(s, h, val) {\ +# define HASH_CALC(s, h, val) {\ __asm mov edx, h\ __asm mov eax, val\ __asm crc32 eax, edx\ __asm mov val, eax\ } # else -# define UPDATE_HASH(s, h, val) \ +# define HASH_CALC(s, h, val) \ __asm__ __volatile__ (\ "crc32 %1,%0\n\t"\ : "+r" (h)\ @@ -38,6 +38,10 @@ # endif #endif +#define HASH_CALC_VAR h +#define HASH_CALC_VAR_INIT uint32_t h = 0 + +#define UPDATE_HASH update_hash_sse4 #define INSERT_STRING insert_string_sse4 #define QUICK_INSERT_STRING quick_insert_string_sse4 diff --git a/deflate.c b/deflate.c index e512e5e9..466e6e9b 100644 --- a/deflate.c +++ b/deflate.c @@ -1162,6 +1162,7 @@ static void lm_init(deflate_state *s) { s->prev_length = 0; s->match_available = 0; s->match_start = 0; + s->ins_h = 0; } /* =========================================================================== diff --git a/deflate.h b/deflate.h index 16e63c75..808060a3 100644 --- a/deflate.h +++ b/deflate.h @@ -155,6 +155,8 @@ typedef struct internal_state { Pos *head; /* Heads of the hash chains or 0. */ + uint32_t ins_h; /* hash index of string to be inserted */ + int block_start; /* Window position at the beginning of the current output block. Gets * negative when the window is moved backwards. diff --git a/insert_string.c b/insert_string.c index 4ddf9ae5..cfe39837 100644 --- a/insert_string.c +++ b/insert_string.c @@ -1,4 +1,4 @@ -/* insert_string_c -- insert_string variant for c +/* insert_string.c -- insert_string integer hash variant * * Copyright (C) 1995-2013 Jean-loup Gailly and Mark Adler * For conditions of distribution and use, see copyright notice in zlib.h @@ -8,18 +8,14 @@ #include "zbuild.h" #include "deflate.h" -/* =========================================================================== - * Update a hash value with the given input byte - * IN assertion: all calls to to UPDATE_HASH are made with consecutive - * input characters, so that a running hash key can be computed from the - * previous key instead of complete recalculation each time. - */ -#define HASH_SLIDE 16 // Number of bits to slide hash +#define HASH_SLIDE 16 -#define UPDATE_HASH(s, h, val) \ - h = ((val * 2654435761U) >> HASH_SLIDE); +#define HASH_CALC(s, h, val) h = ((val * 2654435761U) >> HASH_SLIDE); +#define HASH_CALC_VAR h +#define HASH_CALC_VAR_INIT uint32_t h = 0 -#define INSERT_STRING insert_string_c -#define QUICK_INSERT_STRING quick_insert_string_c +#define UPDATE_HASH update_hash_c +#define INSERT_STRING insert_string_c +#define QUICK_INSERT_STRING quick_insert_string_c #include "insert_string_tpl.h" diff --git a/insert_string_roll.c b/insert_string_roll.c new file mode 100644 index 00000000..dfea347b --- /dev/null +++ b/insert_string_roll.c @@ -0,0 +1,24 @@ +/* insert_string_roll.c -- insert_string rolling hash variant + * + * Copyright (C) 1995-2013 Jean-loup Gailly and Mark Adler + * For conditions of distribution and use, see copyright notice in zlib.h + * + */ + +#include "zbuild.h" +#include "deflate.h" + +#define HASH_SLIDE 5 + +#define HASH_CALC(s, h, val) h = ((h << HASH_SLIDE) ^ ((uint8_t)val)) +#define HASH_CALC_VAR s->ins_h +#define HASH_CALC_VAR_INIT +#define HASH_CALC_READ val = strstart[0] +#define HASH_CALC_MASK (32768u - 1u) +#define HASH_CALC_OFFSET (STD_MIN_MATCH-1) + +#define UPDATE_HASH update_hash_roll +#define INSERT_STRING insert_string_roll +#define QUICK_INSERT_STRING quick_insert_string_roll + +#include "insert_string_tpl.h" diff --git a/insert_string_tpl.h b/insert_string_tpl.h index 11d54643..e2c840bb 100644 --- a/insert_string_tpl.h +++ b/insert_string_tpl.h @@ -22,27 +22,40 @@ * */ +#ifndef HASH_CALC_OFFSET +# define HASH_CALC_OFFSET 0 +#endif +#ifndef HASH_CALC_MASK +# define HASH_CALC_MASK HASH_MASK +#endif +#ifndef HASH_CALC_READ +# ifdef UNALIGNED_OK +# define HASH_CALC_READ \ + val = *(uint32_t *)(strstart); +# else +# define HASH_CALC_READ \ + val = ((uint32_t)(strstart[0])); \ + val |= ((uint32_t)(strstart[1]) << 8); \ + val |= ((uint32_t)(strstart[2]) << 16); \ + val |= ((uint32_t)(strstart[3]) << 24); +# endif +#endif + /* =========================================================================== * Quick insert string str in the dictionary and set match_head to the previous head * of the hash chain (the most recent string with same hash key). Return * the previous length of the hash chain. */ -Z_INTERNAL Pos QUICK_INSERT_STRING(deflate_state *const s, const uint32_t str) { +Z_INTERNAL Pos QUICK_INSERT_STRING(deflate_state *const s, uint32_t str) { Pos head; - uint8_t *strstart = s->window + str; - uint32_t val, hm, h = 0; + uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; + uint32_t val, hm; -#ifdef UNALIGNED_OK - val = *(uint32_t *)(strstart); -#else - val = ((uint32_t)(strstart[0])); - val |= ((uint32_t)(strstart[1]) << 8); - val |= ((uint32_t)(strstart[2]) << 16); - val |= ((uint32_t)(strstart[3]) << 24); -#endif - - UPDATE_HASH(s, h, val); - hm = h & HASH_MASK; + HASH_CALC_VAR_INIT; + HASH_CALC_READ; + HASH_CALC(s, HASH_CALC_VAR, val); + HASH_CALC_VAR &= HASH_CALC_MASK; + hm = HASH_CALC_VAR; head = s->head[hm]; if (LIKELY(head != str)) { @@ -60,24 +73,18 @@ Z_INTERNAL Pos QUICK_INSERT_STRING(deflate_state *const s, const uint32_t str) { * input characters and the first STD_MIN_MATCH bytes of str are valid * (except for the last STD_MIN_MATCH-1 bytes of the input file). */ -Z_INTERNAL void INSERT_STRING(deflate_state *const s, const uint32_t str, uint32_t count) { - uint8_t *strstart = s->window + str; - uint8_t *strend = strstart + count - 1; /* last position */ - - for (Pos idx = (Pos)str; strstart <= strend; idx++, strstart++) { - uint32_t val, hm, h = 0; +Z_INTERNAL void INSERT_STRING(deflate_state *const s, uint32_t str, uint32_t count) { + uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; + uint8_t *strend = strstart + count; -#ifdef UNALIGNED_OK - val = *(uint32_t *)(strstart); -#else - val = ((uint32_t)(strstart[0])); - val |= ((uint32_t)(strstart[1]) << 8); - val |= ((uint32_t)(strstart[2]) << 16); - val |= ((uint32_t)(strstart[3]) << 24); -#endif + for (Pos idx = (Pos)str; strstart < strend; idx++, strstart++) { + uint32_t val, hm; - UPDATE_HASH(s, h, val); - hm = h & HASH_MASK; + HASH_CALC_VAR_INIT; + HASH_CALC_READ; + HASH_CALC(s, HASH_CALC_VAR, val); + HASH_CALC_VAR &= HASH_CALC_MASK; + hm = HASH_CALC_VAR; Pos head = s->head[hm]; if (LIKELY(head != idx)) { diff --git a/win32/Makefile.a64 b/win32/Makefile.a64 index 136e32d4..a272810a 100644 --- a/win32/Makefile.a64 +++ b/win32/Makefile.a64 @@ -63,6 +63,7 @@ OBJS = \ inftrees.obj \ inffast.obj \ insert_string.obj \ + insert_string_roll.obj \ trees.obj \ uncompr.obj \ zutil.obj \ diff --git a/win32/Makefile.arm b/win32/Makefile.arm index 92eed88a..23ed761a 100644 --- a/win32/Makefile.arm +++ b/win32/Makefile.arm @@ -66,6 +66,7 @@ OBJS = \ inftrees.obj \ inffast.obj \ insert_string.obj \ + insert_string_roll.obj \ trees.obj \ uncompr.obj \ zutil.obj \ diff --git a/win32/Makefile.msc b/win32/Makefile.msc index b7166616..94462f59 100644 --- a/win32/Makefile.msc +++ b/win32/Makefile.msc @@ -73,6 +73,7 @@ OBJS = \ inftrees.obj \ inffast.obj \ insert_string.obj \ + insert_string_roll.obj \ insert_string_sse.obj \ slide_avx.obj \ slide_sse.obj \ -- 2.47.3