hwsl2 0.1.0.0 → 0.1.1.0
raw patch · 5 files changed
+385/−7 lines, 5 files
Files
- hwsl2.cabal +2/−2
- src/Data/Hash/SL2.hs +34/−5
- src/gf2p127-inl.h +140/−0
- src/sl2-inl.h +189/−0
- src/tillich-zemor.h +20/−0
hwsl2.cabal view
@@ -10,7 +10,7 @@ -- PVP summary: +-+------- breaking API changes -- | | +----- non-breaking API additions -- | | | +--- code changes with no API change-version: 0.1.0.0+version: 0.1.1.0 -- A short (one-line) description of the package. synopsis: Hashing with SL2@@ -78,7 +78,7 @@ hs-source-dirs: src -- Options for foreign source files.- c-sources: src/tillich-zemor.c+ c-sources: src/tillich-zemor.c src/tillich-zemor.h src/sl2-inl.h src/gf2p127-inl.h cc-options: -msse2 -msse4.1 -mpclmul -- Base language which the package is written in.
src/Data/Hash/SL2.hs view
@@ -20,7 +20,7 @@ -- All operations in this package are implemented in a very efficient manner using SSE instructions. -- -module Data.Hash.SL2 (Hash, hash, (<+), (+>), parse) where+module Data.Hash.SL2 (Hash, hash, (<+), (+>), (<|), (|>), parse) where import Prelude hiding (concat) @@ -38,7 +38,10 @@ import Data.Monoid import Data.Functor+import Data.Foldable +-- Foreign Imports+ foreign import ccall "tillich-zemor.h tz_hash_eq" tzHashEq :: Ptr () -> Ptr () -> IO CInt @@ -60,9 +63,19 @@ foreign import ccall "tillich-zemor.h tz_hash_unserialize" tzHashUnserialize :: Ptr () -> Ptr CChar -> IO () +-- Mutable Helpers++append :: ByteString -> Ptr () -> IO ()+append s p = unsafeUseAsCStringLen s $ \(s', len) -> tzHashAppend p s' (fromIntegral len)++prepend :: ByteString -> Ptr () -> IO ()+prepend s p = unsafeUseAsCStringLen s $ \(s', len) -> tzHashPrepend p s' (fromIntegral len)+ -- | Opaque representation of a 512 bit hash. newtype Hash = H (ForeignPtr ()) +-- Foreign Pointer Helpers+ tzHashSize = 64 tzHashLen = 86 @@ -78,6 +91,8 @@ withHashPtrCopy :: Hash -> (Ptr () -> IO a) -> IO (Hash, a) withHashPtrCopy h f = withHashPtr h $ \hp -> withHashPtrNew $ \hp' -> copyBytes hp' hp tzHashSize >> f hp' +-- Instances+ instance Show Hash where show h = unsafePerformIO $ allocaBytes tzHashLen $ \p -> withHashPtr h (flip tzHashSerialize p) >> peekCStringLen (p, tzHashLen) @@ -88,21 +103,35 @@ mempty = fst $ unsafePerformIO $ withHashPtrNew tzHashUnit mappend a b = fst $ unsafePerformIO $ withHashPtrNew (withHashPtr2 a b . tzHashConcat) +-- Interface+ -- | /O(n)/ Calculate the hash of the 'ByteString'. Alias for @('mempty' '<+')@. hash :: ByteString -> Hash hash = (<+) mempty -- | /O(n)/ Append the hash of the 'ByteString' to the existing 'Hash'. -- A significantly faster equivalent of @(flip ('<>') . 'hash')@.+infixl 7 <+ (<+) :: Hash -> ByteString -> Hash-(<+) h s = fst $ unsafePerformIO $ unsafeUseAsCStringLen s $ \(s', len) ->- withHashPtrCopy h $ \hp -> tzHashAppend hp s' $ fromIntegral len+(<+) h s = fst $ unsafePerformIO $ withHashPtrCopy h $ append s -- | /O(n)/ Prepend the hash of the 'ByteString' to the existing 'Hash'. -- A significantly faster equivalent of @(('<>') . 'hash')@.+infixr 7 +> (+>) :: ByteString -> Hash -> Hash-(+>) s h = fst $ unsafePerformIO $ unsafeUseAsCStringLen s $ \(s', len) ->- withHashPtrCopy h $ \hp -> tzHashPrepend hp s' $ fromIntegral len+(+>) s h = fst $ unsafePerformIO $ withHashPtrCopy h $ prepend s++-- | /O(n)/ Append the hash of the every 'ByteString' to the existing 'Hash', from left to right.+-- A significantly faster equivalent of @('foldl' ('<+'))@.+infixl 7 <|+(<|) :: Foldable t => Hash -> t ByteString -> Hash+(<|) h ss = fst $ unsafePerformIO $ withHashPtrCopy h $ \hp -> foldlM (\p s -> p <$ append s p) hp ss++-- | /O(n)/ Prepend the hash of every 'ByteString' to the existing 'Hash', from right to left.+-- A significantly faster equivalent of @('foldr' ('+>'))@.+infixr 7 |>+(|>) :: Foldable t => t ByteString -> Hash -> Hash+(|>) ss h = fst $ unsafePerformIO $ withHashPtrCopy h $ \hp -> foldrM (\s p -> p <$ prepend s p) hp ss -- | /O(1)/ Parse the representation generated by 'show'. parse :: String -> Maybe Hash
+ src/gf2p127-inl.h view
@@ -0,0 +1,140 @@+#pragma once++#include <stdio.h>+#include <smmintrin.h>+#include <wmmintrin.h>++typedef __m128i gf2p127_t;++static const inline+_Bool gf2p127_eq(const gf2p127_t a, const gf2p127_t b) {+ _Bool lo = _mm_extract_epi64(a, 0) == _mm_extract_epi64(b, 0);+ _Bool hi = _mm_extract_epi64(a, 1) == _mm_extract_epi64(b, 1);+ return lo && hi;+}++static const inline+gf2p127_t gf2p127_zero() {+ return _mm_setzero_si128();+}++static const inline+gf2p127_t gf2p127_from_int(int a) {+ return _mm_cvtsi32_si128(a);+}++static const inline+gf2p127_t gf2p127_mul_bit(const gf2p127_t a, const _Bool bit) {+ return _mm_slli_epi64(a, !bit * 64);+}++static const inline+gf2p127_t gf2p127_add(const gf2p127_t a, const gf2p127_t b) {+ return _mm_xor_si128(a, b);+}++static const inline+gf2p127_t gf2p127_mul_00(const gf2p127_t a) {+ return _mm_setzero_si128();+}++static const inline+gf2p127_t gf2p127_mul_01(const gf2p127_t a) {+ return a;+}++static const uint32_t x127[4] = {0, 0, 0, 1 << 31};++static const inline+gf2p127_t gf2p127_mul_10_left(const gf2p127_t a) {+ // Shift lower and upper halves left by one bit,+ // resembling a multiplication by two.+ gf2p127_t sl = _mm_slli_epi64(a, 1);+ // Check for a x^127 overflow, and add the polynom and carry bit.+ gf2p127_t one = _mm_srli_epi64(_mm_alignr_epi8(a, sl, 8), 63);+ gf2p127_t over = _mm_and_si128(sl, _mm_loadu_si128(x127));+ gf2p127_t x127x63 = _mm_unpackhi_epi64(over, over);+ return _mm_xor_si128(_mm_xor_si128(sl, one), x127x63);+}++static const inline+gf2p127_t gf2p127_mul_10(const gf2p127_t a) {+ // Shift lower and upper halves left by one bit,+ // resembling a multiplication by two.+ gf2p127_t sl = _mm_slli_epi64(a, 1);+ // Check for a x^127 overflow, and add the polynom and carry bit.+ gf2p127_t one = _mm_srli_epi64(_mm_alignr_epi8(a, sl, 8), 63);+ gf2p127_t x127x63 = _mm_slli_epi64(_mm_unpacklo_epi64(one, one), 63);+ return _mm_xor_si128(_mm_xor_si128(sl, one), x127x63);+}++static const inline+gf2p127_t gf2p127_mul_11(const gf2p127_t a) {+ gf2p127_t mul01 = gf2p127_mul_01(a);+ gf2p127_t mul10 = gf2p127_mul_10(a);+ return _mm_xor_si128(mul01, mul10);+};++static const inline+gf2p127_t gf2p127_mul(const gf2p127_t a, const gf2p127_t b) {+ gf2p127_t tmp, lo, hi;++ // Multiplication (Karatsuba):+ // tmp <- (a0 + a1) * (b0 + b1)+ tmp = _mm_xor_si128(_mm_unpacklo_epi64(a, b), _mm_unpackhi_epi64(a, b));+ tmp = _mm_clmulepi64_si128(tmp, tmp, 0x10);+ // lo <- a0 * b0+ lo = _mm_clmulepi64_si128(a, b, 0x00);+ // hi <- a1 * b1+ hi = _mm_clmulepi64_si128(a, b, 0x11);+ // tmp <- (a0 + a1) * (b0 + b1) + a0 * b0 + a1 * b1+ tmp = _mm_xor_si128(tmp, _mm_xor_si128(lo, hi));+ // lo <- a0 * b0 + low64[(a0 + a1) * (b0 + b1) + a0 * b0 + a1 * b1] * x^64+ lo = _mm_xor_si128(lo, _mm_slli_si128(tmp, 8));+ // hi <- a1 * b1 + high64[(a0 + a1) * (b0 + b1) + a0 * b0 + a1 * b1]+ hi = _mm_xor_si128(hi, _mm_srli_si128(tmp, 8));++ // Reduction (modulo f(x) = x^127 + x^63 + 1)+ // tmp <- low64[hi] * x^64 + high64[lo]+ tmp = _mm_alignr_epi8(hi, lo, 8);+ tmp = _mm_xor_si128(tmp, hi);+ hi = _mm_slli_epi64(hi, 1);+ lo = _mm_xor_si128(lo, hi);+ hi = _mm_unpackhi_epi64(hi, tmp);+ lo = _mm_xor_si128(lo, hi);+ tmp = _mm_srli_epi64(tmp, 63);+ lo = _mm_xor_si128(lo, tmp);+ hi = _mm_unpacklo_epi64(tmp, tmp);+ lo = _mm_xor_si128(lo, _mm_slli_epi64(hi, 63));++ return lo;+}++static inline+char *gf2p127_show(char *buf, const gf2p127_t m) {+ __uint128_t a = (__uint128_t)m;+ unsigned int k;+ int n;+ char *str = buf;+ if (a & 1) {+ str += sprintf(str, "1");+ } else {+ str += sprintf(str, "0");+ }+ a >>= 1;+ for (k = 1; k < 128; k++) {+ if (a & 1) {+ n = sprintf(str, " + 2^%i", k);+ str += n;+ }+ a >>= 1;+ }+ return buf;+}++static inline+char *gf2p127_hex(char *str, const gf2p127_t m) {+ sprintf(str, "%.16llx%.16llx", _mm_extract_epi64(m, 1),+ _mm_extract_epi64(m, 0));+ return str;+}
+ src/sl2-inl.h view
@@ -0,0 +1,189 @@+#pragma once++#include "gf2p127-inl.h"++typedef gf2p127_t sl2_t[2][2];++static inline+_Bool sl2_eq(sl2_t a, sl2_t b) {+ return gf2p127_eq(a[0][0], b[0][0]) &&+ gf2p127_eq(a[0][1], b[0][1]) &&+ gf2p127_eq(a[1][0], b[1][0]) &&+ gf2p127_eq(a[1][1], b[1][1]);+}++static inline+void sl2_copy(sl2_t dst, sl2_t src) {+ dst[0][0] = src[0][0];+ dst[0][1] = src[0][1];+ dst[1][0] = src[1][0];+ dst[1][1] = src[1][1];+}++static inline+void sl2_mul_bit_left(sl2_t b, int bit) {+ // A: {00 = 10, 01 = 01, 10 = 01, 11 = 00}+ // B: {00 = 10, 01 = 11, 10 = 01, 11 = 01}+ gf2p127_t b00 = b[0][0];+ gf2p127_t b10 = b[1][0];+ gf2p127_t b01 = b[0][1];+ gf2p127_t b11 = b[1][1];+ b[0][0] = gf2p127_zero();+ b[0][1] = gf2p127_zero();+ b[1][0] = gf2p127_add(b00, b[bit][0]);+ b[1][1] = gf2p127_add(b01, b[bit][1]);+ b[0][0] = gf2p127_add(b10, gf2p127_mul_10_left(b[1][0]));+ b[0][1] = gf2p127_add(b11, gf2p127_mul_10_left(b[1][1]));+}++static inline+void sl2_mul_bits_left(sl2_t b, unsigned char byte) {+ sl2_mul_bit_left(b, (byte >> 0) & 1);+ sl2_mul_bit_left(b, (byte >> 1) & 1);+ sl2_mul_bit_left(b, (byte >> 2) & 1);+ sl2_mul_bit_left(b, (byte >> 3) & 1);+ sl2_mul_bit_left(b, (byte >> 4) & 1);+ sl2_mul_bit_left(b, (byte >> 5) & 1);+ sl2_mul_bit_left(b, (byte >> 6) & 1);+ sl2_mul_bit_left(b, (byte >> 7) & 1);+}++static inline+void sl2_mul_bit_right(sl2_t a, int bit) {+ // A: {00 = 10, 01 = 01, 10 = 01, 11 = 00}+ // B: {00 = 10, 01 = 11, 10 = 01, 11 = 01}+ gf2p127_t a00 = a[0][0];+ gf2p127_t a10 = a[1][0];+ gf2p127_t a01 = a[0][1];+ gf2p127_t a11 = a[1][1];+ a[0][1] = gf2p127_zero();+ a[1][1] = gf2p127_zero();+ a[0][0] = gf2p127_add(gf2p127_mul_10(a00), a01);+ a[1][0] = gf2p127_add(gf2p127_mul_10(a10), a11);+ a[0][1] = gf2p127_add(a00, a[0][!bit]);+ a[1][1] = gf2p127_add(a10, a[1][!bit]);+}++static inline+void sl2_mul_bits_right(sl2_t a, unsigned char byte) {+ sl2_mul_bit_right(a, (byte >> 7) & 1);+ sl2_mul_bit_right(a, (byte >> 6) & 1);+ sl2_mul_bit_right(a, (byte >> 5) & 1);+ sl2_mul_bit_right(a, (byte >> 4) & 1);+ sl2_mul_bit_right(a, (byte >> 3) & 1);+ sl2_mul_bit_right(a, (byte >> 2) & 1);+ sl2_mul_bit_right(a, (byte >> 1) & 1);+ sl2_mul_bit_right(a, (byte >> 0) & 1);+}++static inline+void sl2_mul(sl2_t c, sl2_t a, sl2_t b) {+ // Strassen algorithm+ gf2p127_t m0, m1, m2, m3, m4, m5, m6;+ m0 = gf2p127_mul(gf2p127_add(a[0][0], a[1][1]),+ gf2p127_add(b[0][0], b[1][1]));+ m1 = gf2p127_mul(gf2p127_add(a[1][0], a[1][1]), b[0][0]);+ m2 = gf2p127_mul(a[0][0], gf2p127_add(b[0][1], b[1][1]));+ m3 = gf2p127_mul(a[1][1], gf2p127_add(b[1][0], b[0][0]));+ m4 = gf2p127_mul(gf2p127_add(a[0][0], a[0][1]), b[1][1]);+ m5 = gf2p127_mul(gf2p127_add(a[1][0], a[0][0]),+ gf2p127_add(b[0][0], b[0][1]));+ m6 = gf2p127_mul(gf2p127_add(a[0][1], a[1][1]),+ gf2p127_add(b[1][0], b[1][1]));+ c[0][0] = gf2p127_add(gf2p127_add(m0, m3), gf2p127_add(m4, m6));+ c[0][1] = gf2p127_add(m2, m4);+ c[1][0] = gf2p127_add(m1, m3);+ c[1][1] = gf2p127_add(gf2p127_add(m0, m1), gf2p127_add(m2, m5));+}++static inline+void sl2_mul_byte_left(sl2_t b, unsigned char byte, sl2_t m[256]) {+ sl2_mul(m[byte], b, b);+}++static inline+void sl2_mul_byte_right(sl2_t a, unsigned char byte, sl2_t m[256]) {+ sl2_mul(a, m[byte], a);+}++static inline+void sl2_init(sl2_t m[2]) {+ m[0][0][0] = gf2p127_from_int(2);+ m[0][0][1] = gf2p127_from_int(1);+ m[0][1][0] = gf2p127_from_int(1);+ m[0][1][1] = gf2p127_from_int(0);+ m[1][0][0] = gf2p127_from_int(2);+ m[1][0][1] = gf2p127_from_int(3);+ m[1][1][0] = gf2p127_from_int(1);+ m[1][1][1] = gf2p127_from_int(1);+}++static inline+void sl2_unit(sl2_t a) {+ a[0][0] = gf2p127_from_int(1);+ a[0][1] = gf2p127_from_int(0);+ a[1][0] = gf2p127_from_int(0);+ a[1][1] = gf2p127_from_int(1);+}++static inline+char *sl2_hex(char *buf, sl2_t a) {+ gf2p127_hex(&buf[0], a[0][0]);+ gf2p127_hex(&buf[32], a[0][1]);+ gf2p127_hex(&buf[64], a[1][0]);+ gf2p127_hex(&buf[96], a[1][1]);+ return buf;+}++static const unsigned char b64[64] =+ "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_";++static const unsigned char unb64[256] = {+ ['A'] = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,+ 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,+ ['a'] = 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38,+ 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51,+ ['0'] = 52, 53, 54, 55, 56, 57, 58, 59, 60, 61,+ ['-'] = 62, ['_'] = 63+};++static inline+void sl2_serialize(sl2_t m, unsigned char buf[86]) {++ int i, j;+ unsigned char a, b, c, *data = (unsigned char *)m;++ for (i = j = 0; i <= 64 - 3; i += 3, j += 4) {+ a = data[i + 0];+ b = data[i + 1];+ c = data[i + 2];+ buf[j + 0] = b64[a >> 2];+ buf[j + 1] = b64[((0x03 & a) << 4) + (b >> 4)];+ buf[j + 2] = b64[((0x0f & b) << 2) + (c >> 6)];+ buf[j + 3] = b64[0x3f & c];+ }++ buf[84] = b64[data[i] >> 2];+ buf[85] = b64[(0x3 & data[i]) << 4];++}++static inline+void sl2_unserialize(sl2_t m, unsigned char buf[86]) {++ int i, j;+ unsigned char a, b, c, d, *data = (unsigned char *)m;++ for (i = j = 0; i <= 86 - 4; i += 4, j += 3) {+ a = unb64[buf[i + 0]];+ b = unb64[buf[i + 1]];+ c = unb64[buf[i + 2]];+ d = unb64[buf[i + 3]];+ data[j + 0] = (a << 2) | (b >> 4);+ data[j + 1] = (b << 4) | (c >> 2);+ data[j + 2] = (c << 6) | (d);+ }++ data[63] = (unb64[buf[i]] << 2) | (unb64[buf[i + 1]] >> 4);++}
+ src/tillich-zemor.h view
@@ -0,0 +1,20 @@+#pragma once++#include <stddef.h>++#define TZ_HASH_SIZE 64+typedef struct tz_hash_struct *tz_hash_t;++void tz_hash_copy(tz_hash_t dst, tz_hash_t src);++int tz_hash_eq(tz_hash_t a, tz_hash_t b);++void tz_hash_unit(tz_hash_t);++void tz_hash_append(tz_hash_t h, unsigned char *buf, size_t n);+void tz_hash_prepend(tz_hash_t h, unsigned char *buf, size_t n);++void tz_hash_concat(tz_hash_t c, tz_hash_t a, tz_hash_t b);++void tz_hash_serialize(tz_hash_t h, unsigned char str[86]);+void tz_hash_unserialize(tz_hash_t h, unsigned char str[86]);