xxhash.sh.in

#!/bin/bash
#########################################################################
#  xxHash - Fast Hash algorithm
#  Copyright (C) 2012-2016, Yann Collet
#  Copyright (C) 2019, easyaspi314
#
#  BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
#
#  Redistribution and use in source and binary forms, with or without
#  modification, are permitted provided that the following conditions are
#  met:
#
#  * Redistributions of source code must retain the above copyright
#  notice, this list of conditions and the following disclaimer.
#  * Redistributions in binary form must reproduce the above
#  copyright notice, this list of conditions and the following disclaimer
#  in the documentation and/or other materials provided with the
#  distribution.
#
#  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
#  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
#  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
#  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
#  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
#  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
#  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
#  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
#  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
#  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
#  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#
#  You can contact the author at :
#  - xxHash homepage: http://www.xxhash.com
#  - xxHash source repository : https://github.com/Cyan4973/xxHash
#########################################################################

#########################################################################
# This is XXH32 and XXH64 in pure Bash.
#
# This code is a joke. Don't actually use this. It is incredibly slow and
# you are much better using literally any other implementation.
#
# If you actually use this for production code, you are a monster and do
# not deserve access to a computer ever again.
#
# Usage:
#    XXH32 "data in hex with no spaces or 0x" "seed"
#    XXH64 "data in hex with no spaces or 0x" "seed"
#
# The hash will be printf'd in hex, without a 0x prefix.
#
# Performance:
#
# Default implementation:
# $ time xxh64sum xxhash.sh >/dev/null
# real    0m0.012s
# user    0m0.003s
# sys     0m0.004s
# $ time xxh32sum xxhash.sh >/dev/null
# real    0m0.007s
# user    0m0.002s
# sys     0m0.003s
#
# This implementation:
# $ . xxhash.sh
# $ XXHASH_SH=$(hexdump -e '/1 "%02X"' -v "xxhash.sh")
# $ time XXH64 "$XXHASH_SH" "0" >/dev/null
# real    0m16.672s
# user    0m16.632s
# sys     0m0.036s
# $ time XXH32 "$XXHASH_SH" "0" >/dev/null
# real    0m32.185s
# user    0m32.099s
# sys     0m0.080s
#
# As you can see, performance is terrible for a few reasons:
# - Bash uses signed 64-bit integers. Shifting on them performs an
#   arithmetic shift right, so we need to emulate a logical shift
#   right.
# - XXH32 is slow because all 32-bit arithmetic needs to be emulated with
#   masks. Hopefully some of these masks can be removed someday.
# - It is arithmetic in a Bash script. What do you expect?
# - Maybe we should use functions, idk.
#########################################################################

# This is an m4 script. This inlines everything.
# Note that whitespace is left out in some loops as it slows down bash.

# Good practice.
set -euo pipefail

# Bash uses signed arithmetic, so shifting right is wonk.
define(ushr_impl,(($1>>($2))&$3))
define(ushr,ushr_impl($1,$2,(~(((1<<63)>>($2))<<1))))

# Bash reads files in big endian.
define(swap,$(( \
    (((tmp=$1)<<56)&(255<<56))|\
    ((tmp<<40)&(255<<48))|\
    ((tmp<<24)&(255<<40))|\
    ((tmp<<8)&(255<<32))|\
    ((ushr(tmp,8))&(255<<24))|\
    ((ushr(tmp,24))&(255<<16))|\
    ((ushr(tmp,40))&(255<<8))|\
    ((ushr(tmp,56))&255)\
)) \
)
define(swap32,$(( \
( ( (tmp=$1) << 24) & 0xff000000 ) | \
            ( (tmp <<  8) & 0x00ff0000 ) | \
            ( (ushr(tmp, 8)) & 0x0000ff00 ) | \
            ( (ushr(tmp, 24)) & 0x000000ff ) \
   )) \
)


define(XXH64_mergeRound,
    zero=0
    XXH64_round(zero, $2)
    $1=$(( (($1 ^ zero) * PRIME64_1) + PRIME64_4 ))
)
define(XXH_rotl64,(($1<<$2)|(ushr($1,(64-$2)))))
define(XXH_rotl32,(((($1)<<($2))|(($1>>(32-$2)))))&0xFFFFFFFF)

dnl calculate the right shift magic beforehand
define(XXH64_round,(($1+=(($2)*PRIME64_2)));$1=$(((($1<<31)|ushr_impl($1,33,0x7fffffff) )*PRIME64_1)))
define(XXH64_avalanche,
    (( h64 ^= ushr(h64, 33) ))
    (( h64 *= PRIME64_2 ))
    (( h64 ^= ushr(h64, 29) ))
    (( h64 *= PRIME64_3 ))
    (( h64 ^= ushr(h64, 32) ))
)

# uint64_t XXH64(text_in_hex, seed = 0)
XXH64()
{
    dnl Performance is multiplied by 8-10x if we switch to C locale.
    local OLD_LC_ALL="${LC_ALL:-}"
    export LC_ALL="C"

    local -i PRIME64_1=0x9E3779B185EBCA87
    local -i PRIME64_2=0xC2B2AE3D27D4EB4F
    local -i PRIME64_3=0x165667B19E3779F9
    local -i PRIME64_4=0x85EBCA77C2B2AE63
    local -i PRIME64_5=0x27D4EB2F165667C5

    local -i seed=0
    if [ $# -ge 2 ]; then
        seed=$2
    fi
    local inp="                                                                 "
    local -i tmp=0
    local -i zero=0
    local -i h64=0
    local input="$1"
    local -i len=$(( ${#input} / 2 ))
    local -i remaining=$len
    local -i offset=0
    local -i bEnd=$(( ${#input} - 64 ))
    if [ $remaining -ge 32 ]; then
        local -i v1=$(( seed + PRIME64_1 + PRIME64_2 ))
        local -i v2=$(( seed + PRIME64_2 ))
        local -i v3=$(( seed ))
        local -i v4=$(( seed - PRIME64_1 ))

        dnl tight loop, no whitespace
        while [ $offset -le $bEnd ]; do
            inp="${input:$offset:64}"
            XXH64_round(v1, swap(0x${inp:0:16}))
            XXH64_round(v2,swap(0x${inp:16:16}))
            XXH64_round(v3,swap(0x${inp:32:16}))
            XXH64_round(v4,swap(0x${inp:48:16}))
            ((offset+=64))
        done

        h64=$(( (XXH_rotl64(v1, 1)) + (XXH_rotl64(v2, 7)) + (XXH_rotl64(v3, 12)) + (XXH_rotl64(v4, 18)) ))

        XXH64_mergeRound(h64, v1)
        XXH64_mergeRound(h64, v2)
        XXH64_mergeRound(h64, v3)
        XXH64_mergeRound(h64, v4)
    else
        h64=$((seed + PRIME64_5));
    fi
    remaining=$(( ${#input} - offset ))
    ((h64 += len))
    while [ $remaining -ge 16 ]; do
	local -i k1=0
        XXH64_round(k1, swap(0x${input:$offset:16}))
        (( offset += 16 ))
        h64=$(( h64 ^ k1 ));
        h64=$(( (XXH_rotl64(h64, 27) * PRIME64_1) + PRIME64_4 ));
        ((remaining -= 16 ));
    done
    if [ $remaining -ge 8 ]; then
        (( h64 ^= (swap32(0x00000000${input:$offset:8}) * PRIME64_1) ))
        (( offset += 8 ))
        h64=$(( (XXH_rotl64(h64, 23) * PRIME64_2) + PRIME64_3 ))
        ((remaining-=8))
    fi
    while [ $remaining -gt 0 ]; do
        (( h64 ^= (0x${input:$offset:2} * PRIME64_5) ))
        (( offset += 2 ))
        h64=$(( XXH_rotl64(h64, 11) * PRIME64_1 ))
        ((remaining-=2))
    done
    XXH64_avalanche

    # Reset LC_ALL.
    if [ -n "$OLD_LC_ALL"]; then
        export LC_ALL="$OLD_LC_ALL"
    else
        unset LC_ALL
    fi
    printf "%016x" $h64
}

# I would kill for 32-bit integers right now.
define(XXH32_round,$1=$(((($1+(($2*PRIME32_2) & 0xFFFFFFFF)) & 0xFFFFFFFF) ));
    $1=$(( ((XXH_rotl32($1,13)&0xFFFFFFFF)*PRIME32_1) & 0xFFFFFFFF ))
)
define(XXH32_avalanche,
    h32=$(( (h32 ^ (ushr(h32, 15) & 0xFFFFFFFF) )& 0xFFFFFFFF ))
    h32=$(( (h32 * PRIME32_2) & 0xFFFFFFFF ))
    h32=$(( (h32 ^ (ushr(h32, 13) & 0xFFFFFFFF) )& 0xFFFFFFFF ))
    h32=$(( (h32 * PRIME32_3) & 0xFFFFFFFF ))
    h32=$(( (h32 ^ (ushr(h32, 16) & 0xFFFFFFFF)) & 0xFFFFFFFF ))
)

# uint32_t XXH32(data, seed = 0)
XXH32()
{
    # Performance is multiplied by eightfold if we switch to C locale.
    local OLD_LC_ALL="${LC_ALL:-}"
    export LC_ALL="C"

    local -i PRIME32_1=2654435761
    local -i PRIME32_2=2246822519
    local -i PRIME32_3=3266489917
    local -i PRIME32_4=668265263
    local -i PRIME32_5=374761393

    local -i seed=0
    if [ $# -ge 2 ]; then
        seed=$2
    fi
    local -i tmp=0
    local -i zero=0
    local -i h32=0
    local input="$1"
    local -i len=$(( ${#input} / 2 ))
    local -i remaining=$len
    local -i offset=0
    local -i bEnd=$(( ${#input} - 32 ))
    if [ $remaining -ge 16 ]; then
        local -i v1=$(( ( ( (seed + PRIME32_1) & 0xFFFFFFFF) + PRIME32_2) & 0xFFFFFFFF ))
        local -i v2=$(( (seed + PRIME32_2) & 0xFFFFFFFF ))
        local -i v3=$(( seed ))
        local -i v4=$(( (seed - PRIME32_1) & 0xFFFFFFFF ))

        while [ $offset -le $bEnd ]; do
            local inp="${input:$offset:32}"
            XXH32_round(v1, swap32(0x${inp:0:8}))
            XXH32_round(v2, swap32(0x${inp:8:8}))
            XXH32_round(v3, swap32(0x${inp:16:8}))
            XXH32_round(v4, swap32(0x${inp:24:8}))
            ((offset+=32))
        done

        h32=$(( XXH_rotl32(v1, 1) & 0xFFFFFFFF ))
        h32=$(( (h32 + (XXH_rotl32(v2, 7) ))  & 0xFFFFFFFF ))
        h32=$(( (h32 + (XXH_rotl32(v3, 12) )) & 0xFFFFFFFF ))
        h32=$(( (h32 + (XXH_rotl32(v4, 18) )) & 0xFFFFFFFF ))
    else
        h32=$(( (seed + PRIME32_5) & 0xFFFFFFFF ));
    fi
    remaining=$(( ${#input} - offset ))
    h32=$(( (h32 + (len & 0xFFFFFFFF))  & 0xFFFFFFFF ))
    while [ $remaining -ge 8 ]; do
        h32=$(( (h32 + ( ( swap32(0x${input:$offset:8}) * PRIME32_3) & 0xFFFFFFFF)) & 0xFFFFFFFF ))
        (( offset += 8 ))
        h32=$(( ((XXH_rotl32(h32, 17) & 0xFFFFFFFF) * PRIME32_4) & 0xFFFFFFFF ))
        ((remaining-=8))
    done

    while [ $remaining -gt 0 ]; do
        h32=$(( (h32 + ( (0x${input:$offset:2} * PRIME32_5) & 0xFFFFFFFF) ) & 0xFFFFFFFF))
        (( offset += 2 ))
        h32=$(( ((XXH_rotl32(h32, 11) & 0xFFFFFFFF) * PRIME32_1) & 0xFFFFFFFF ))
        ((remaining-=2))
    done
    XXH32_avalanche

    # Reset LC_ALL.
    if [ -n "$OLD_LC_ALL"]; then
        export LC_ALL="$OLD_LC_ALL"
    else
        unset LC_ALL
    fi

    printf "%08x" $h32
}