packages feed

hw-json-simd (empty) → 0.1.0.0

raw patch · 27 files changed

+1818/−0 lines, 27 filesdep +basedep +bytestringdep +hw-json-simdsetup-changed

Dependencies added: base, bytestring, hw-json-simd, hw-prim, lens, optparse-applicative, semigroups, transformers, vector

Files

+ ChangeLog.md view
@@ -0,0 +1,3 @@+# Changelog for hw-json-simd++## Unreleased changes
+ LICENSE view
@@ -0,0 +1,31 @@+Copyright (c) 2018, John Ky+Copyright (c) 2018, Gabriel Gonzalez++All rights reserved.++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.++    * Neither the name of Author name here nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++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.
+ README.md view
@@ -0,0 +1,44 @@+# hw-json-simd++This library/tool will generate semi-indexes on JSON files as per the paper:+[Semi-Indexing Semi-Structured Data in Tiny Space](http://www.di.unipi.it/~ottavian/files/semi_index_cikm.pdf).++## The command line tool++For a given JSON file, `hw-json-simd` will generate two semi-index+files, which both together can be loaded into a single in-memory semi-index.++The semi-index files can be generated using two methods, which will be called+standard and simple, which correspond to sections 4 and 5 of the+[Semi-Indexing Semi-Structured Data in Tiny Space](http://www.di.unipi.it/~ottavian/files/semi_index_cikm.pdf)+paper respectively.++Navigation of the JSON text using the standard index is suppored by the [`hw-json` project](https://github.com/haskell-works/hw-json) for more information.  There is currently+no support for navigation of the JSON text using the simple index.++### Using on the command line++```bash+cat test.json | pv -t -e -b -a | time hw-json-simd create-index \+  -i /dev/stdin+  --output-ib-file test.json.ib.idx+  --output-bp-file test.json.bp.idx+  --method standard+```++```bash+cat test.json | pv -t -e -b -a | time hw-json-simd create-index \+  -i /dev/stdin+  --output-ib-file test.json.ib.idx+  --output-bp-file test.json.bp.idx+  --method simple+```++## Installation++### From hackage++```bash+cabal new-install hw-json-simd+```+
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ app/App/Commands.hs view
@@ -0,0 +1,15 @@+module App.Commands where++import App.Commands.Capabilities+import App.Commands.CreateIndex+import Data.Semigroup            ((<>))+import Options.Applicative++commands :: Parser (IO ())+commands = commandsGeneral++commandsGeneral :: Parser (IO ())+commandsGeneral = subparser $ mempty+  <>  commandGroup "Commands:"+  <>  cmdCapabilities+  <>  cmdCreateIndex
+ app/App/Commands/Capabilities.hs view
@@ -0,0 +1,27 @@+{-# LANGUAGE ScopedTypeVariables #-}++module App.Commands.Capabilities+  ( cmdCapabilities+  ) where++import Data.Semigroup                             ((<>))+import HaskellWorks.Data.Json.Simd.Index.Simple+import HaskellWorks.Data.Json.Simd.Index.Standard+import Options.Applicative                        hiding (columns)++import qualified System.IO as IO++{-# ANN module ("HLint: ignore Reduce duplication"  :: String) #-}+{-# ANN module ("HLint: ignore Redundant do"        :: String) #-}++runCapabilities :: () -> IO ()+runCapabilities opts = do+  IO.putStrLn "Capabalities:"+  IO.putStrLn $ "  standard indexing: " <> show enabledMakeStandardJsonIbBps+  IO.putStrLn $ "  simple indexing: "   <> show enabledMakeSimpleJsonIbBps++optsCapabilities :: Parser ()+optsCapabilities = pure ()++cmdCapabilities :: Mod CommandFields (IO ())+cmdCapabilities = command "capabilities" $ flip info idm $ runCapabilities <$> optsCapabilities
+ app/App/Commands/CreateIndex.hs view
@@ -0,0 +1,86 @@+{-# LANGUAGE ScopedTypeVariables #-}++module App.Commands.CreateIndex+  ( cmdCreateIndex+  ) where++import App.Commands.Types+import Control.Lens+import Control.Monad+import Data.Maybe+import Data.Semigroup                             ((<>))+import HaskellWorks.Data.Json.Simd.Index.Simple+import HaskellWorks.Data.Json.Simd.Index.Standard+import Options.Applicative                        hiding (columns)++import qualified App.Lens                          as L+import qualified Data.ByteString                   as BS+import qualified Data.ByteString.Lazy              as LBS+import qualified HaskellWorks.Data.ByteString.Lazy as LBS+import qualified System.Exit                       as IO+import qualified System.IO                         as IO++{-# ANN module ("HLint: ignore Reduce duplication"  :: String) #-}+{-# ANN module ("HLint: ignore Redundant do"        :: String) #-}++runCreateIndex :: CreateIndexOptions -> IO ()+runCreateIndex opts = do+  let filePath      = opts ^. L.filePath+  let outputIbFile  = opts ^. L.outputIbFile & fromMaybe (filePath <> ".ib.idx")+  let outputBpFile  = opts ^. L.outputBpFile & fromMaybe (filePath <> ".bp.idx")+  let method        = opts ^. L.method++  case method of+    "simple" -> do+      IO.withFile filePath IO.ReadMode $ \hIn -> do+        contents <- LBS.resegmentPadded 512 <$> LBS.hGetContents hIn+        let chunks = makeSimpleJsonIbBpsUnsafe contents+        IO.withFile outputIbFile IO.WriteMode $ \hIb -> do+          IO.withFile outputBpFile IO.WriteMode $ \hBp -> do+            forM_ chunks $ \(ibBs, bpBs) -> do+              BS.hPut hIb ibBs+              BS.hPut hBp bpBs+    "standard" -> do+      IO.withFile filePath IO.ReadMode $ \hIn -> do+        contents <- LBS.resegmentPadded 512 <$> LBS.hGetContents hIn+        let chunks = makeStandardJsonIbBpsUnsafe contents+        IO.withFile outputIbFile IO.WriteMode $ \hIb -> do+          IO.withFile outputBpFile IO.WriteMode $ \hBp -> do+            forM_ chunks $ \(ibBs, bpBs) -> do+              BS.hPut hIb ibBs+              BS.hPut hBp bpBs+    _ -> do+      IO.hPutStrLn IO.stderr $ "Unrecognised method: " <> show method+      IO.exitFailure++optsCreateIndex :: Parser CreateIndexOptions+optsCreateIndex = CreateIndexOptions+  <$> strOption+        (   long "input"+        <>  short 'i'+        <>  help "Input JSON file"+        <>  metavar "STRING"+        )+  <*> optional+        ( strOption+          (   long "output-ib-file"+          <>  help "Filename for output ib index"+          <>  metavar "STRING"+          )+        )+  <*> optional+        ( strOption+          (   long "output-bp-file"+          <>  help "Filename for output bp index"+          <>  metavar "STRING"+          )+        )+  <*> strOption+        (   long "method"+        <>  help "Method"+        <>  value "simple"+        <>  metavar "STRING"+        )++cmdCreateIndex :: Mod CommandFields (IO ())+cmdCreateIndex = command "create-index"  $ flip info idm $ runCreateIndex <$> optsCreateIndex
+ app/App/Commands/Types.hs view
@@ -0,0 +1,10 @@+module App.Commands.Types+  ( CreateIndexOptions(..)+  ) where++data CreateIndexOptions = CreateIndexOptions+  { _createIndexOptionsFilePath     :: FilePath+  , _createIndexOptionsOutputIbFile :: Maybe FilePath+  , _createIndexOptionsOutputBpFile :: Maybe FilePath+  , _createIndexOptionsMethod       :: String+  } deriving (Eq, Show)
+ app/App/Lens.hs view
@@ -0,0 +1,13 @@+{-# LANGUAGE FlexibleInstances      #-}+{-# LANGUAGE FunctionalDependencies #-}+{-# LANGUAGE MultiParamTypeClasses  #-}+{-# LANGUAGE TemplateHaskell        #-}+{-# LANGUAGE TypeFamilies           #-}+{-# LANGUAGE TypeSynonymInstances   #-}++module App.Lens where++import App.Commands.Types+import Control.Lens++makeFields ''CreateIndexOptions
+ app/Main.hs view
@@ -0,0 +1,11 @@+module Main where++import App.Commands+import Control.Monad+import Data.Semigroup      ((<>))+import Options.Applicative++main :: IO ()+main = join $ customExecParser+  (prefs $ showHelpOnEmpty <> showHelpOnError)+  (info (commands <**> helper) idm)
+ cbits/debug.c view
@@ -0,0 +1,1 @@+#include "debug.h"
+ cbits/debug.h view
@@ -0,0 +1,103 @@+#include <immintrin.h>+#include <mmintrin.h>+#include <stdint.h>+#include <stdio.h>++#if defined __AVX2__+inline void hw_simd_json_fprint256_num(FILE *file, __m256i var) {+  uint8_t *val = (uint8_t*)&var;+  fprintf(file,+    "%02x %02x %02x %02x %02x %02x %02x %02x  %02x %02x %02x %02x %02x %02x %02x %02x  "+    "%02x %02x %02x %02x %02x %02x %02x %02x  %02x %02x %02x %02x %02x %02x %02x %02x"+    , val[ 0], val[ 1], val[ 2], val[ 3], val[ 4], val[ 5], val[ 6], val[ 7]+    , val[ 8], val[ 9], val[10], val[11], val[12], val[13], val[14], val[15]+    , val[16], val[17], val[18], val[19], val[20], val[21], val[22], val[23]+    , val[24], val[25], val[26], val[27], val[28], val[29], val[30], val[31]);+}+#endif//__AVX2__++#if defined __AVX2__+inline void hw_simd_json_fprint128_num(FILE *file, __m128i var) {+  uint8_t *val = (uint8_t*)&var;+  fprintf(file,+    "%02x %02x %02x %02x %02x %02x %02x %02x  %02x %02x %02x %02x %02x %02x %02x %02x"+    , val[ 0], val[ 1], val[ 2], val[ 3], val[ 4], val[ 5], val[ 6], val[ 7]+    , val[ 8], val[ 9], val[10], val[11], val[12], val[13], val[14], val[15]);+}+#endif//__AVX2__++#if defined __AVX2__+inline void hw_simd_json_print256_num(__m256i var) {+  hw_simd_json_fprint256_num(stdout, var);+}+#endif//__AVX2__++#if defined __AVX2__+inline void hw_simd_json_print128_num(__m128i var) {+  hw_simd_json_fprint128_num(stdout, var);+}+#endif//__AVX2__++inline void hw_simd_json_print_bits_8(uint8_t v) {+  char *digits = "01";+  int i = 0;++  for (i = 0; i < 8; ++i) {+    printf("%c", digits[(v >> i) & 1]);+  }+}++inline void hw_simd_json_print_bits_16(uint16_t v) {+  char *digits = "01";+  int i = 0;++  for (i = 0; i < 16; ++i) {+    printf("%c", digits[(v >> i) & 1]);+  }+}++inline void hw_simd_json_print_bits_32(uint32_t v) {+  char *digits = "01";+  int i = 0;++  for (i = 0; i < 32; ++i) {+    printf("%c", digits[(v >> i) & 1]);+  }+}++inline void hw_simd_json_print_bits_64(uint64_t v) {+  char *digits = "01";+  int i = 0;++  for (i = 0; i < 64; ++i) {+    printf("%c", digits[(v >> i) & 1]);+  }+}++#if defined __AVX2__+inline void hw_simd_json_print_bits_128(__m128i v) {+  int i = 0;++  for (i = 0; i < 2; ++i) {+    if (i > 0) {+      printf("-");+    }++    hw_simd_json_print_bits_64(_mm_extract_epi64(v, i));+  }+}+#endif//__AVX2__++#if defined __AVX2__+inline void hw_simd_json_print_bits_256(__m256i v) {+  int i = 0;++  for (i = 0; i < 4; ++i) {+    if (i > 0) {+      printf("-");+    }++    hw_simd_json_print_bits_64(_mm256_extract_epi64(v, i));+  }+}+#endif//__AVX2__
+ cbits/simd-phi-table-32.c view
@@ -0,0 +1,37 @@+#include <stdint.h>+#include <immintrin.h>++uint32_t hw_json_simd_phi_table_32[] =+  { 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000007, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000007, 0x00000000, 0x00000007, 0x00000007, 0x00000000+  , 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007+  , 0x00000007, 0x00000007, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007+  , 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007+  , 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007+  , 0x00000007, 0x00000007, 0x00000007, 0x06000006, 0x00000000, 0x01000001, 0x00000000, 0x00000000+  , 0x00000000, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007+  , 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007+  , 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007, 0x00000007+  , 0x00000007, 0x00000007, 0x00000007, 0x06000006, 0x00000000, 0x01000001, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  , 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000+  };
+ cbits/simd-spliced.c view
@@ -0,0 +1,434 @@+#include <stdlib.h>+#include <string.h>+#include <stdio.h>+#include <immintrin.h>+#include <mmintrin.h>++#include "simd.h"++#define W8_BUFFER_SIZE    (1024 * 32)+#define W32_BUFFER_SIZE   (W8_BUFFER_SIZE / 4)+#define W64_BUFFER_SIZE   (W8_BUFFER_SIZE / 8)++typedef struct hw_json_simd_bp_state {+  uint64_t  remainder_bits_d;+  uint64_t  remainder_bits_a;+  uint64_t  remainder_bits_z;+  size_t    remainder_len;+} hw_json_simd_bp_state_t;++int hw_json_simd_main_spliced(+    int argc,+    char **argv) {+  if (argc != 4) {+    fprintf(stderr, "./a.out <input-file> <output-ib-file> <output-bp-file>\n");+    exit(1);+  }++  char *in_filename     = argv[1];+  char *ib_out_filename = argv[2];+  char *bp_out_filename = argv[3];++  FILE *in = fopen(in_filename, "r");++  if (!in) {+    fprintf(stderr, "Failed to open input file %s\n", in_filename);+    exit(1);+  }++  FILE *ib_out = fopen(ib_out_filename, "w");+  +  if (!ib_out) {+    fprintf(stderr, "Failed to open ib output file %s\n", ib_out_filename);+    exit(1);+  }++  FILE *bp_out = fopen(bp_out_filename, "w");+  +  if (!bp_out) {+    fprintf(stderr, "Failed to open bp output file %s\n", bp_out_filename);+    exit(1);+  }++  uint8_t buffer[W8_BUFFER_SIZE];++  uint8_t *bits_of_d = malloc(W32_BUFFER_SIZE); memset(bits_of_d, 0, W32_BUFFER_SIZE);+  uint8_t *bits_of_a = malloc(W32_BUFFER_SIZE); memset(bits_of_a, 0, W32_BUFFER_SIZE);+  uint8_t *bits_of_z = malloc(W32_BUFFER_SIZE); memset(bits_of_z, 0, W32_BUFFER_SIZE);+  uint8_t *bits_of_b = malloc(W32_BUFFER_SIZE); memset(bits_of_b, 0, W32_BUFFER_SIZE);+  uint8_t *bits_of_e = malloc(W32_BUFFER_SIZE); memset(bits_of_e, 0, W32_BUFFER_SIZE);+  uint8_t *bits_of_q = malloc(W32_BUFFER_SIZE); memset(bits_of_q, 0, W32_BUFFER_SIZE);++  uint8_t result_ib[W8_BUFFER_SIZE / 8];+  uint8_t result_a [W8_BUFFER_SIZE / 8];+  uint8_t result_z [W8_BUFFER_SIZE / 8];+  hw_json_simd_bp_state_t bp_state;++  uint64_t accum = 0;++  size_t last_trailing_ones = 0;+  size_t total_bytes_read   = 0;+  uint64_t quote_mask_carry = 0;+  size_t quote_odds_carry   = 0;+  size_t quote_evens_carry  = 1;++  uint8_t out_bp_buffer[W32_BUFFER_SIZE * 2];++  while (1) {+    size_t bytes_read = fread(buffer, 1, W8_BUFFER_SIZE, in);++    total_bytes_read += bytes_read;++    if (bytes_read < W8_BUFFER_SIZE) {+      if (ferror(in)) {+        fprintf(stderr, "Error reading file\n");+        exit(1);+      }++      if (bytes_read == 0) {+        if (feof(in)) {+          break;+        }+      }++      size_t next_alignment = ((bytes_read + 63) / 64) * 64;++      memset(buffer + bytes_read, 0, next_alignment - bytes_read);++      bytes_read = next_alignment;+    }++    accum += hw_json_simd_process_chunk(buffer, bytes_read,+      bits_of_d,+      bits_of_a,+      bits_of_z,+      bits_of_q,+      bits_of_b,+      bits_of_e,+      &last_trailing_ones,+      &quote_odds_carry,+      &quote_evens_carry,+      &quote_mask_carry,+      result_ib,+      result_a,+      result_z);++    size_t ib_bytes = (bytes_read + 7) / 8;++    fwrite(result_ib, 1, ib_bytes, ib_out);++    size_t out_bp_bytes = hw_json_simd_write_bp_chunk(+      result_ib,+      result_a,+      result_z,+      ib_bytes,+      &bp_state,+      out_bp_buffer);++    fwrite(out_bp_buffer, out_bp_bytes, sizeof(uint64_t), bp_out);++    fflush(ib_out);+    fflush(bp_out);+  }++  hw_json_simd_write_bp_chunk_final(&bp_state, out_bp_buffer);++  fwrite(out_bp_buffer, 2, sizeof(uint64_t), bp_out);++  fclose(in);+  fclose(ib_out);++  return 0;+}++void hw_json_simd_init_bp_state(+    hw_json_simd_bp_state_t *bp_state) {+  memset(bp_state, 0, sizeof(*bp_state));+}++size_t hw_json_simd_write_bp_chunk(+    uint8_t *result_ib,+    uint8_t *result_a,+    uint8_t *result_z,+    size_t ib_bytes,+    hw_json_simd_bp_state_t *bp_state,+    uint8_t *out_buffer) {+  uint64_t *w64_result_ib = (uint64_t *)result_ib;+  uint64_t *w64_result_a  = (uint64_t *)result_a;+  uint64_t *w64_result_z  = (uint64_t *)result_z;+  uint64_t *w64_work_bp   = (uint64_t *)out_buffer;++  uint64_t  w64_len           = ib_bytes / 8;+  uint64_t  remainder_bits_d  = (*bp_state).remainder_bits_d;+  uint64_t  remainder_bits_a  = (*bp_state).remainder_bits_a;+  uint64_t  remainder_bits_z  = (*bp_state).remainder_bits_z;+  size_t    remainder_len     = (*bp_state).remainder_len;+  size_t    w64s_ready        = 0;++  for (size_t i = 0; i < w64_len; ++i) {+    uint64_t w64_ib = w64_result_ib[i];+    uint64_t w64_a  = w64_result_a[i];+    uint64_t w64_z  = w64_result_z[i];++    size_t pc_ib = __builtin_popcountll(w64_ib);++    uint64_t ext_d = _pext_u64(~(w64_a | w64_z) , w64_ib);+    uint64_t ext_a = _pext_u64(w64_a            , w64_ib);+    uint64_t ext_z = _pext_u64(w64_z            , w64_ib);++    remainder_bits_d |= (ext_d << remainder_len);+    remainder_bits_a |= (ext_a << remainder_len);+    remainder_bits_z |= (ext_z << remainder_len);++    if (remainder_len + pc_ib >= 64) {+      // Write full word+      w64_work_bp[w64s_ready] =+        _pdep_u64(remainder_bits_a, 0x5555555555555555) |+        _pdep_u64(remainder_bits_a, 0xaaaaaaaaaaaaaaaa) |+        _pdep_u64(remainder_bits_d, 0xaaaaaaaaaaaaaaaa);++      w64s_ready += 1;++      remainder_bits_a = remainder_bits_a >> 32;+      remainder_bits_z = remainder_bits_z >> 32;+      remainder_bits_d = remainder_bits_d >> 32;++      w64_work_bp[w64s_ready] =+        _pdep_u64(remainder_bits_a, 0x5555555555555555) |+        _pdep_u64(remainder_bits_a, 0xaaaaaaaaaaaaaaaa) |+        _pdep_u64(remainder_bits_d, 0xaaaaaaaaaaaaaaaa);++      w64s_ready += 1;++      // Set up for next iteration+      remainder_bits_d = ext_d >> (64 - remainder_len);+      remainder_bits_a = ext_a >> (64 - remainder_len);+      remainder_bits_z = ext_z >> (64 - remainder_len);++      remainder_len = remainder_len + pc_ib - 64;+    } else {+      remainder_len += pc_ib;+    }+  }++  (*bp_state).remainder_bits_d  = remainder_bits_d;+  (*bp_state).remainder_bits_a  = remainder_bits_a;+  (*bp_state).remainder_bits_z  = remainder_bits_z;+  (*bp_state).remainder_len     = remainder_len;++  return w64s_ready;+}++size_t hw_json_simd_write_bp_chunk_final(+    hw_json_simd_bp_state_t *bp_state,+    uint8_t *out_buffer) {+  uint64_t *w64_work_bp   = (uint64_t *)out_buffer;++  uint64_t  remainder_bits_d  = (*bp_state).remainder_bits_d;+  uint64_t  remainder_bits_a  = (*bp_state).remainder_bits_a;+  uint64_t  remainder_bits_z  = (*bp_state).remainder_bits_z;+  size_t    w64s_ready        = 0;++  // Write full word+  w64_work_bp[w64s_ready] =+    _pdep_u64(remainder_bits_a, 0x5555555555555555) |+    _pdep_u64(remainder_bits_a, 0xaaaaaaaaaaaaaaaa) |+    _pdep_u64(remainder_bits_d, 0xaaaaaaaaaaaaaaaa);++  w64s_ready += 1;++  remainder_bits_a = remainder_bits_a >> 32;+  remainder_bits_z = remainder_bits_z >> 32;+  remainder_bits_d = remainder_bits_d >> 32;++  w64_work_bp[w64s_ready] =+    _pdep_u64(remainder_bits_a, 0x5555555555555555) |+    _pdep_u64(remainder_bits_a, 0xaaaaaaaaaaaaaaaa) |+    _pdep_u64(remainder_bits_d, 0xaaaaaaaaaaaaaaaa);++  w64s_ready += 1;++  return w64s_ready;+}++uint8_t hw_json_simd_escape_mask[2][256] =+  { { 0xff, 0xfd, 0xfb, 0xff, 0xf7, 0xf5, 0xff, 0xf7, 0xef, 0xed, 0xeb, 0xef, 0xff, 0xfd, 0xef, 0xff+    , 0xdf, 0xdd, 0xdb, 0xdf, 0xd7, 0xd5, 0xdf, 0xd7, 0xff, 0xfd, 0xfb, 0xff, 0xdf, 0xdd, 0xff, 0xdf+    , 0xbf, 0xbd, 0xbb, 0xbf, 0xb7, 0xb5, 0xbf, 0xb7, 0xaf, 0xad, 0xab, 0xaf, 0xbf, 0xbd, 0xaf, 0xbf+    , 0xff, 0xfd, 0xfb, 0xff, 0xf7, 0xf5, 0xff, 0xf7, 0xbf, 0xbd, 0xbb, 0xbf, 0xff, 0xfd, 0xbf, 0xff+    , 0x7f, 0x7d, 0x7b, 0x7f, 0x77, 0x75, 0x7f, 0x77, 0x6f, 0x6d, 0x6b, 0x6f, 0x7f, 0x7d, 0x6f, 0x7f+    , 0x5f, 0x5d, 0x5b, 0x5f, 0x57, 0x55, 0x5f, 0x57, 0x7f, 0x7d, 0x7b, 0x7f, 0x5f, 0x5d, 0x7f, 0x5f+    , 0xff, 0xfd, 0xfb, 0xff, 0xf7, 0xf5, 0xff, 0xf7, 0xef, 0xed, 0xeb, 0xef, 0xff, 0xfd, 0xef, 0xff+    , 0x7f, 0x7d, 0x7b, 0x7f, 0x77, 0x75, 0x7f, 0x77, 0xff, 0xfd, 0xfb, 0xff, 0x7f, 0x7d, 0xff, 0x7f+    , 0xff, 0xfd, 0xfb, 0xff, 0xf7, 0xf5, 0xff, 0xf7, 0xef, 0xed, 0xeb, 0xef, 0xff, 0xfd, 0xef, 0xff+    , 0xdf, 0xdd, 0xdb, 0xdf, 0xd7, 0xd5, 0xdf, 0xd7, 0xff, 0xfd, 0xfb, 0xff, 0xdf, 0xdd, 0xff, 0xdf+    , 0xbf, 0xbd, 0xbb, 0xbf, 0xb7, 0xb5, 0xbf, 0xb7, 0xaf, 0xad, 0xab, 0xaf, 0xbf, 0xbd, 0xaf, 0xbf+    , 0xff, 0xfd, 0xfb, 0xff, 0xf7, 0xf5, 0xff, 0xf7, 0xbf, 0xbd, 0xbb, 0xbf, 0xff, 0xfd, 0xbf, 0xff+    , 0xff, 0xfd, 0xfb, 0xff, 0xf7, 0xf5, 0xff, 0xf7, 0xef, 0xed, 0xeb, 0xef, 0xff, 0xfd, 0xef, 0xff+    , 0xdf, 0xdd, 0xdb, 0xdf, 0xd7, 0xd5, 0xdf, 0xd7, 0xff, 0xfd, 0xfb, 0xff, 0xdf, 0xdd, 0xff, 0xdf+    , 0xff, 0xfd, 0xfb, 0xff, 0xf7, 0xf5, 0xff, 0xf7, 0xef, 0xed, 0xeb, 0xef, 0xff, 0xfd, 0xef, 0xff+    , 0xff, 0xfd, 0xfb, 0xff, 0xf7, 0xf5, 0xff, 0xf7, 0xff, 0xfd, 0xfb, 0xff, 0xff, 0xfd, 0xff, 0xff+    }+  , { 0xfe, 0xff, 0xfa, 0xfb, 0xf6, 0xf7, 0xfe, 0xff, 0xee, 0xef, 0xea, 0xeb, 0xfe, 0xff, 0xee, 0xef+    , 0xde, 0xdf, 0xda, 0xdb, 0xd6, 0xd7, 0xde, 0xdf, 0xfe, 0xff, 0xfa, 0xfb, 0xde, 0xdf, 0xfe, 0xff+    , 0xbe, 0xbf, 0xba, 0xbb, 0xb6, 0xb7, 0xbe, 0xbf, 0xae, 0xaf, 0xaa, 0xab, 0xbe, 0xbf, 0xae, 0xaf+    , 0xfe, 0xff, 0xfa, 0xfb, 0xf6, 0xf7, 0xfe, 0xff, 0xbe, 0xbf, 0xba, 0xbb, 0xfe, 0xff, 0xbe, 0xbf+    , 0x7e, 0x7f, 0x7a, 0x7b, 0x76, 0x77, 0x7e, 0x7f, 0x6e, 0x6f, 0x6a, 0x6b, 0x7e, 0x7f, 0x6e, 0x6f+    , 0x5e, 0x5f, 0x5a, 0x5b, 0x56, 0x57, 0x5e, 0x5f, 0x7e, 0x7f, 0x7a, 0x7b, 0x5e, 0x5f, 0x7e, 0x7f+    , 0xfe, 0xff, 0xfa, 0xfb, 0xf6, 0xf7, 0xfe, 0xff, 0xee, 0xef, 0xea, 0xeb, 0xfe, 0xff, 0xee, 0xef+    , 0x7e, 0x7f, 0x7a, 0x7b, 0x76, 0x77, 0x7e, 0x7f, 0xfe, 0xff, 0xfa, 0xfb, 0x7e, 0x7f, 0xfe, 0xff+    , 0xfe, 0xff, 0xfa, 0xfb, 0xf6, 0xf7, 0xfe, 0xff, 0xee, 0xef, 0xea, 0xeb, 0xfe, 0xff, 0xee, 0xef+    , 0xde, 0xdf, 0xda, 0xdb, 0xd6, 0xd7, 0xde, 0xdf, 0xfe, 0xff, 0xfa, 0xfb, 0xde, 0xdf, 0xfe, 0xff+    , 0xbe, 0xbf, 0xba, 0xbb, 0xb6, 0xb7, 0xbe, 0xbf, 0xae, 0xaf, 0xaa, 0xab, 0xbe, 0xbf, 0xae, 0xaf+    , 0xfe, 0xff, 0xfa, 0xfb, 0xf6, 0xf7, 0xfe, 0xff, 0xbe, 0xbf, 0xba, 0xbb, 0xfe, 0xff, 0xbe, 0xbf+    , 0xfe, 0xff, 0xfa, 0xfb, 0xf6, 0xf7, 0xfe, 0xff, 0xee, 0xef, 0xea, 0xeb, 0xfe, 0xff, 0xee, 0xef+    , 0xde, 0xdf, 0xda, 0xdb, 0xd6, 0xd7, 0xde, 0xdf, 0xfe, 0xff, 0xfa, 0xfb, 0xde, 0xdf, 0xfe, 0xff+    , 0xfe, 0xff, 0xfa, 0xfb, 0xf6, 0xf7, 0xfe, 0xff, 0xee, 0xef, 0xea, 0xeb, 0xfe, 0xff, 0xee, 0xef+    , 0xfe, 0xff, 0xfa, 0xfb, 0xf6, 0xf7, 0xfe, 0xff, 0xfe, 0xff, 0xfa, 0xfb, 0xfe, 0xff, 0xfe, 0xff+    }+  };++void hw_json_simd_summarise(+    uint8_t *buffer,+    uint32_t *out_mask_d,+    uint32_t *out_mask_a,+    uint32_t *out_mask_z,+    uint32_t *out_mask_q,+    uint32_t *out_mask_b) {+#ifdef __AVX2__+  __m256i v_in_data = *(__m256i *)buffer;+  __m256i v_bytes_of_comma      = _mm256_cmpeq_epi8(v_in_data, _mm256_set1_epi8(','));+  __m256i v_bytes_of_colon      = _mm256_cmpeq_epi8(v_in_data, _mm256_set1_epi8(':'));+  __m256i v_bytes_of_brace_a    = _mm256_cmpeq_epi8(v_in_data, _mm256_set1_epi8('{'));+  __m256i v_bytes_of_brace_z    = _mm256_cmpeq_epi8(v_in_data, _mm256_set1_epi8('}'));+  __m256i v_bytes_of_bracket_a  = _mm256_cmpeq_epi8(v_in_data, _mm256_set1_epi8('['));+  __m256i v_bytes_of_bracket_z  = _mm256_cmpeq_epi8(v_in_data, _mm256_set1_epi8(']'));+  __m256i v_bytes_of_quote      = _mm256_cmpeq_epi8(v_in_data, _mm256_set1_epi8('"'));+  __m256i v_bytes_of_backslash  = _mm256_cmpeq_epi8(v_in_data, _mm256_set1_epi8('\\'));++  uint32_t mask_comma     = (uint32_t)_mm256_movemask_epi8(v_bytes_of_comma     );+  uint32_t mask_colon     = (uint32_t)_mm256_movemask_epi8(v_bytes_of_colon     );+  uint32_t mask_brace_a   = (uint32_t)_mm256_movemask_epi8(v_bytes_of_brace_a   );+  uint32_t mask_brace_z   = (uint32_t)_mm256_movemask_epi8(v_bytes_of_brace_z   );+  uint32_t mask_bracket_a = (uint32_t)_mm256_movemask_epi8(v_bytes_of_bracket_a );+  uint32_t mask_bracket_z = (uint32_t)_mm256_movemask_epi8(v_bytes_of_bracket_z );++  *out_mask_d = mask_comma    | mask_colon;+  *out_mask_a = mask_brace_a  | mask_bracket_a;+  *out_mask_z = mask_brace_z  | mask_bracket_z;+  *out_mask_q = (uint32_t)_mm256_movemask_epi8(v_bytes_of_quote    );+  *out_mask_b = (uint32_t)_mm256_movemask_epi8(v_bytes_of_backslash);+#elif defined __SSE4_2__+  __m128i v_in_data_0 = *((__m128i *)buffer    );+  __m128i v_in_data_1 = *((__m128i *)buffer + 1);+  uint16_t *out_w32_mask_d = (uint16_t *)out_mask_d;+  uint16_t *out_w32_mask_a = (uint16_t *)out_mask_a;+  uint16_t *out_w32_mask_z = (uint16_t *)out_mask_z;+  uint16_t *out_w32_mask_q = (uint16_t *)out_mask_q;+  uint16_t *out_w32_mask_b = (uint16_t *)out_mask_b;+  out_w32_mask_d[0] = _mm_extract_epi16(_mm_cmpestrm(*(__m128i*)":,", 2, v_in_data_0, 16, _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK), 0);+  out_w32_mask_d[1] = _mm_extract_epi16(_mm_cmpestrm(*(__m128i*)":,", 2, v_in_data_1, 16, _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK), 0);+  out_w32_mask_a[0] = _mm_extract_epi16(_mm_cmpestrm(*(__m128i*)"{[", 2, v_in_data_0, 16, _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK), 0);+  out_w32_mask_a[1] = _mm_extract_epi16(_mm_cmpestrm(*(__m128i*)"{[", 2, v_in_data_1, 16, _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK), 0);+  out_w32_mask_z[0] = _mm_extract_epi16(_mm_cmpestrm(*(__m128i*)"]}", 2, v_in_data_0, 16, _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK), 0);+  out_w32_mask_z[1] = _mm_extract_epi16(_mm_cmpestrm(*(__m128i*)"]}", 2, v_in_data_1, 16, _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK), 0);+  out_w32_mask_q[0] = _mm_extract_epi16(_mm_cmpestrm(*(__m128i*)"\"", 1, v_in_data_0, 16, _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK), 0);+  out_w32_mask_q[1] = _mm_extract_epi16(_mm_cmpestrm(*(__m128i*)"\"", 1, v_in_data_1, 16, _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK), 0);+  out_w32_mask_b[0] = _mm_extract_epi16(_mm_cmpestrm(*(__m128i*)"\\", 1, v_in_data_0, 16, _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK), 0);+  out_w32_mask_b[1] = _mm_extract_epi16(_mm_cmpestrm(*(__m128i*)"\\", 1, v_in_data_1, 16, _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK), 0);+#else+#error "Require -mavx2 or -msse42 flags to be defined"+#endif+}++uint64_t hw_json_simd_bitwise_add(uint64_t a, uint64_t b, uint64_t *c) {+  uint64_t d = a + b + *c;++  *c = (d <= a) & 1;++  return d;+}++uint64_t hw_json_simd_process_chunk(+    uint8_t *in_buffer,+    size_t in_length,+    uint8_t *work_bits_of_d,       // Working buffer of minimum length ((in_length + 63) / 64)+    uint8_t *work_bits_of_a,       // Working buffer of minimum length ((in_length + 63) / 64)+    uint8_t *work_bits_of_z,       // Working buffer of minimum length ((in_length + 63) / 64)+    uint8_t *work_bits_of_q,       // Working buffer of minimum length ((in_length + 63) / 64)+    uint8_t *work_bits_of_b,       // Working buffer of minimum length ((in_length + 63) / 64)+    uint8_t *work_bits_of_e,       // Working buffer of minimum length ((in_length + 63) / 64)+    size_t *last_trailing_ones,+    size_t *quote_odds_carry,+    size_t *quote_evens_carry,+    uint64_t *quote_mask_carry,+    uint8_t *result_ib,+    uint8_t *result_a,+    uint8_t *result_z) {+  size_t m256_in_len = in_length / 32;+  size_t w64_out_len = in_length / 64;+  size_t w8_out_len  = in_length / 8;++  uint8_t  *w8_bits_of_b  = (uint8_t  *)work_bits_of_b;++  uint32_t *w32_bits_of_d = (uint32_t *)work_bits_of_d;+  uint32_t *w32_bits_of_a = (uint32_t *)work_bits_of_a;+  uint32_t *w32_bits_of_z = (uint32_t *)work_bits_of_z;+  uint32_t *w32_bits_of_q = (uint32_t *)work_bits_of_q;+  uint32_t *w32_bits_of_b = (uint32_t *)work_bits_of_b;++  uint64_t *w64_bits_of_d = (uint64_t *)work_bits_of_d;+  uint64_t *w64_bits_of_a = (uint64_t *)work_bits_of_a;+  uint64_t *w64_bits_of_z = (uint64_t *)work_bits_of_z;+  uint64_t *w64_bits_of_q = (uint64_t *)work_bits_of_q;+  uint64_t *w64_bits_of_e = (uint64_t *)work_bits_of_e;++  uint64_t *w64_result_ib = (uint64_t *)result_ib;+  uint64_t *w64_result_a  = (uint64_t *)result_a;+  uint64_t *w64_result_z  = (uint64_t *)result_z;++  uint64_t accum = 0;++  for (size_t i = 0; i < m256_in_len; ++i) {+    hw_json_simd_summarise(in_buffer + (i * 32),+      w32_bits_of_d + i,+      w32_bits_of_a + i,+      w32_bits_of_z + i,+      w32_bits_of_q + i,+      w32_bits_of_b + i);+  }++  for (size_t i = 0; i < w8_out_len; ++i) {+    char w8 = w8_bits_of_b[i];+    size_t j = (*last_trailing_ones) % 2;+    size_t k = (size_t)(uint8_t)w8;+    char w8e = hw_json_simd_escape_mask[j][k];+    work_bits_of_e[i] = w8e;+    *last_trailing_ones = _lzcnt_u64(~(int64_t)w8);+  }++  for (size_t i = 0; i < w64_out_len; ++i) {+    w64_bits_of_q[i] = w64_bits_of_e[i] & w64_bits_of_q[i];++    uint64_t w64_bits_of_q_word = w64_bits_of_q[i];++    uint64_t qas = _pdep_u64(0x5555555555555555 << ((*quote_odds_carry ) & 1), w64_bits_of_q_word);+    uint64_t qzs = _pdep_u64(0x5555555555555555 << ((*quote_evens_carry) & 1), w64_bits_of_q_word);++    uint64_t quote_mask = hw_json_simd_bitwise_add(qas, ~qzs, quote_mask_carry);++    uint64_t w64_d = quote_mask & w64_bits_of_d[i];+    uint64_t w64_a = quote_mask & w64_bits_of_a[i];+    uint64_t w64_z = quote_mask & w64_bits_of_z[i];++    w64_result_ib[i]  = w64_d | w64_a | w64_z;+    w64_result_a[i]   = w64_a;+    w64_result_z[i]   = w64_z;++    size_t pc = __builtin_popcountll(w64_bits_of_q[i]);+    *quote_odds_carry  += pc;+    *quote_evens_carry += pc;+  }++  return accum;+}
+ cbits/simd-state.c view
@@ -0,0 +1,151 @@+#include <stdint.h>+#include <stdio.h>+#include <stdlib.h>+#include <string.h>+#include <immintrin.h>++#include "debug.h"++#include "simd.h"++void+hw_json_simd_sm_process_chunk(+    uint8_t *in_buffer,+    size_t in_length,+    uint32_t *inout_state,+    uint32_t *out_phi_buffer) {+  __m128i s = _mm_set_epi64x(0, *inout_state);++  for (size_t i = 0; i < in_length; i += 1) {+    uint8_t w = in_buffer[i];+    __m128i p = _mm_shuffle_epi8(_mm_set1_epi32(hw_json_simd_phi_table_32[w]), s);+    out_phi_buffer[i] = _mm_extract_epi32(p, 0);+    s = _mm_shuffle_epi8(_mm_set1_epi32(hw_json_simd_transition_table_32[w]), s);+  }++  *inout_state = (uint32_t)_mm_extract_epi32(s, 0);+}++void+hw_json_simd_sm_make_ib_op_cl_chunks(+    uint8_t state,+    uint32_t *in_phis,+    size_t phi_length,+    uint8_t *out_ibs,+    uint8_t *out_ops,+    uint8_t *out_cls) {+  uint32_t state_offset = state * 8;++  uint32_t ib_offset = 5;+  uint32_t op_offset = 6;+  uint32_t cl_offset = 7;++  for (size_t i = 0; i < phi_length; i += 8) {+    __m256i v_8 = *(__m256i *)&in_phis[i];+    __m256i v_ib_8 = _mm256_slli_epi64(_mm256_srli_epi64(v_8, state_offset), ib_offset);+    __m256i v_op_8 = _mm256_slli_epi64(_mm256_srli_epi64(v_8, state_offset), op_offset);+    __m256i v_cl_8 = _mm256_slli_epi64(_mm256_srli_epi64(v_8, state_offset), cl_offset);+    uint8_t all_ibs = (uint8_t)_pext_u32(_mm256_movemask_epi8(v_ib_8), 0x11111111);+    uint8_t all_ops = (uint8_t)_pext_u32(_mm256_movemask_epi8(v_op_8), 0x11111111);+    uint8_t all_cls = (uint8_t)_pext_u32(_mm256_movemask_epi8(v_cl_8), 0x11111111);++    size_t j = i / 8;+    out_ibs[j] = all_ibs;+    out_ops[j] = all_ops;+    out_cls[j] = all_cls;+  }+}++size_t+hw_json_simd_sm_write_bits(+    uint64_t bits,+    size_t bits_len,+    uint64_t *remaining_bits,+    size_t *remaning_bits_len,+    uint64_t *out_buffer);++size_t+hw_json_simd_sm_write_bp_chunk(+    uint8_t *result_op,+    uint8_t *result_cl,+    size_t ib_bytes,+    uint64_t *remaining_bits,+    size_t *remaning_bits_len,+    uint64_t *out_buffer) {+  uint64_t *w64_result_op = (uint64_t *)result_op;+  uint64_t *w64_result_cl = (uint64_t *)result_cl;+  uint64_t *w64_work_bp   = (uint64_t *)out_buffer;++  uint64_t  w64_len           = ib_bytes / 8;+  size_t    w64s_ready        = 0;++  for (size_t i = 0; i < w64_len; ++i) {+    uint64_t w64_op = w64_result_op[i];+    uint64_t w64_cl = w64_result_cl[i];++    uint64_t w64_op_lo = w64_op;+    uint64_t w64_op_hi = w64_op >> 32;++    uint64_t w64_cl_lo = w64_cl;+    uint64_t w64_cl_hi = w64_cl >> 32;++    uint64_t op_lo = _pdep_u64(w64_op_lo, 0x5555555555555555);+    uint64_t cl_lo = _pdep_u64(w64_cl_lo, 0xaaaaaaaaaaaaaaaa);+    uint64_t ib_lo = op_lo | cl_lo;++    uint64_t op_hi = _pdep_u64(w64_op_hi, 0x5555555555555555);+    uint64_t cl_hi = _pdep_u64(w64_cl_hi, 0xaaaaaaaaaaaaaaaa);+    uint64_t ib_hi = op_hi | cl_hi;++    size_t pc_ib_lo = __builtin_popcountll(ib_lo);+    size_t pc_ib_hi = __builtin_popcountll(ib_hi);++    uint64_t ext_lo = _pext_u64(op_lo, ib_lo);+    uint64_t ext_hi = _pext_u64(op_hi, ib_hi);++    w64s_ready += hw_json_simd_sm_write_bits(ext_lo, pc_ib_lo, remaining_bits, remaning_bits_len, w64_work_bp + w64s_ready);+    w64s_ready += hw_json_simd_sm_write_bits(ext_hi, pc_ib_hi, remaining_bits, remaning_bits_len, w64_work_bp + w64s_ready);+  }++  return w64s_ready;+}++size_t+hw_json_simd_sm_write_bits(+    uint64_t bits,+    size_t bits_len,+    uint64_t *remaining_bits,+    size_t *remaining_bits_len,+    uint64_t *out_buffer) {+  *remaining_bits |= (bits << *remaining_bits_len);++  if (*remaining_bits_len + bits_len >= 64) {+    *out_buffer = *remaining_bits;++    *remaining_bits = bits >> (64 - *remaining_bits_len);++    *remaining_bits_len = *remaining_bits_len + bits_len - 64;++    return 1;+  } else {+    *remaining_bits_len += bits_len;++    return 0;+  }+}++size_t+hw_json_simd_sm_write_bp_chunk_final(+    uint64_t remaining_bits,+    size_t remaining_bits_len,+    uint64_t *out_buffer) {+  if (remaining_bits_len > 0) {+    size_t zero_len = 64 - remaining_bits_len;++    *out_buffer = (remaining_bits << zero_len) >> zero_len;++    return 1;+  } else {+    return 0;+  }+}
+ cbits/simd-transition-table-32.c view
@@ -0,0 +1,37 @@+#include <stdint.h>+#include <immintrin.h>++uint32_t hw_json_simd_transition_table_32[] =+  { 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010001, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x03010103, 0x00010100, 0x03010103, 0x03010103, 0x00010100+  , 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103+  , 0x03010103, 0x03010103, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103+  , 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103+  , 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103+  , 0x03010103, 0x03010103, 0x03010103, 0x00010100, 0x00010200, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103+  , 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103+  , 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103, 0x03010103+  , 0x03010103, 0x03010103, 0x03010103, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  , 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100, 0x00010100+  };
+ cbits/simd.c view
@@ -0,0 +1,25 @@+#include "simd.h"++int hw_json_simd_avx2_enabled() {+#ifdef __AVX2__+  return 1;+#else+  return 0;+#endif+}++int hw_json_simd_bmi2_enabled() {+#ifdef __BMI2__+  return 1;+#else+  return 0;+#endif+}++int hw_json_simd_sse4_2_enabled() {+#ifdef __BMI2__+  return 1;+#else+  return 0;+#endif+}
+ cbits/simd.h view
@@ -0,0 +1,88 @@+#include <immintrin.h>+#include <mmintrin.h>+#include <stdint.h>+#include <stdio.h>++#define W8_BUFFER_SIZE    (1024 * 32)+#define W32_BUFFER_SIZE   (W8_BUFFER_SIZE / 4)+#define W64_BUFFER_SIZE   (W8_BUFFER_SIZE / 8)++typedef struct hw_json_simd_bp_state hw_json_simd_bp_state_t;++int hw_json_simd_avx2_enabled();++int hw_json_simd_bmi2_enabled();++int hw_json_simd_sse4_2_enabled();++extern uint32_t hw_json_simd_transition_table_32[256];+extern uint32_t hw_json_simd_phi_table_32       [256];++int hw_json_simd_main_spliced(+    int argc,+    char **argv);++uint64_t hw_json_simd_process_chunk(+    uint8_t *in_buffer,+    size_t in_length,+    uint8_t *work_bits_of_d,       // Working buffer of minimum length ((in_length + 63) / 64)+    uint8_t *work_bits_of_a,       // Working buffer of minimum length ((in_length + 63) / 64)+    uint8_t *work_bits_of_z,       // Working buffer of minimum length ((in_length + 63) / 64)+    uint8_t *work_bits_of_q,       // Working buffer of minimum length ((in_length + 63) / 64)+    uint8_t *work_bits_of_b,       // Working buffer of minimum length ((in_length + 63) / 64)+    uint8_t *work_bits_of_e,       // Working buffer of minimum length ((in_length + 63) / 64)+    size_t *last_trailing_ones,+    size_t *quote_odds_carry,+    size_t *quote_evens_carry,+    uint64_t *quote_mask_carry,+    uint8_t *result_ibs,+    uint8_t *result_a,+    uint8_t *result_z);++void hw_json_simd_init_bp_state(+    hw_json_simd_bp_state_t *bp_state);++size_t hw_json_simd_write_bp_chunk(+    uint8_t *result_ib,+    uint8_t *result_a,+    uint8_t *result_z,+    size_t ib_bytes,+    hw_json_simd_bp_state_t *bp_state,+    uint8_t *out_buffer);++size_t hw_json_simd_write_bp_chunk_final(+    hw_json_simd_bp_state_t *bp_state,+    uint8_t *out_buffer);++// ---++size_t+hw_json_simd_sm_write_bp_chunk(+    uint8_t *result_op,+    uint8_t *result_cl,+    size_t ib_bytes,+    uint64_t *remaining_bp_bits,+    size_t *remaning_bp_bits_len,+    uint64_t *out_buffer);++size_t+hw_json_simd_sm_write_bp_chunk_final(+    uint64_t remaining_bits,+    size_t remaining_bits_len,+    uint64_t *out_buffer);++void+hw_json_simd_sm_process_chunk(+    uint8_t *in_buffer,+    size_t in_length,+    uint32_t *inout_state,+    uint32_t *out_phi_buffer);++void+hw_json_simd_sm_make_ib_op_cl_chunks(+    uint8_t state,+    uint32_t *in_phis,+    size_t phi_length,+    uint8_t *out_ibs,+    uint8_t *out_ops,+    uint8_t *out_cls);
+ hw-json-simd.cabal view
@@ -0,0 +1,168 @@+cabal-version:  2.2++name:           hw-json-simd+version:        0.1.0.0+synopsis:       SIMD-based JSON semi-indexer+description:    Please see the README on GitHub at <https://github.com/haskell-works/hw-json-simd#readme>+category:       Data+homepage:       https://github.com/haskell-works/hw-json-simd#readme+bug-reports:    https://github.com/haskell-works/hw-json-simd/issues+author:         John Ky+maintainer:     newhoggy@gmail.com+copyright:      2018 - 2019 John Ky+license:        BSD-3-Clause+license-file:   LICENSE+build-type:     Simple+tested-with:    GHC == 8.6.1, GHC == 8.4.3, GHC == 8.2.2+extra-source-files:+    cbits/debug.h+    cbits/simd.h+    cbits/simd.c+    cbits/simd-spliced.c+    cbits/simd-state.c+    cbits/simd-phi-table-32.c+    cbits/simd-transition-table-32.c+    README.md+    ChangeLog.md++source-repository head+  type: git+  location: https://github.com/haskell-works/hw-json-simd++flag avx2+  description: Enable avx2 instruction set+  manual: False+  default: False++flag bmi2+  description: Enable bmi2 instruction set+  manual: False+  default: False++flag sse42+  description: Enable SSE 4.2 optimisations.+  manual: False+  default: True++common base                   { build-depends: base                 >= 4          && < 5      }+common bytestring             { build-depends: bytestring           >= 0.10.6     && < 0.11   }+common hw-prim                { build-depends: hw-prim              >= 0.6.2.21   && < 0.7    }+common lens                   { build-depends: lens                 >= 4          && < 5      }+common optparse-applicative   { build-depends: optparse-applicative >= 0.14       && < 0.15   }+common vector                 { build-depends: vector               >= 0.12       && < 0.13   }++common semigroups     { if (!impl(ghc >=8.0.1)) { build-depends: { semigroups   >= 0.8.4  && < 0.19 } } }+common transformers   { if (!impl(ghc >=8.0.1)) { build-depends: { transformers >= 0.4    && < 0.6  } } }++library+  import:   base+          , bytestring+          , hw-prim+          , lens+          , vector+  exposed-modules:+      HaskellWorks.Data.Json.Simd.Capabilities+      HaskellWorks.Data.Json.Simd.Index.Simple+      HaskellWorks.Data.Json.Simd.Index.Standard+      HaskellWorks.Data.Json.Simd.Internal.Foreign+      HaskellWorks.Data.Json.Simd.Internal.Index.Simple+      HaskellWorks.Data.Json.Simd.Internal.Index.Standard+      HaskellWorks.Data.Json.Simd.Internal.List+  autogen-modules:  Paths_hw_json_simd+  other-modules:    Paths_hw_json_simd+  hs-source-dirs:+      src+  ghc-options: -Wall+  cc-options: -mssse3 -mlzcnt -mbmi2 -mavx2+  include-dirs:+      cbits+  c-sources:+      cbits/debug.c+      cbits/simd.c+      cbits/simd-spliced.c+      cbits/simd-state.c+      cbits/simd-phi-table-32.c+      cbits/simd-transition-table-32.c+  build-tools:+      c2hs+  if flag(sse42)+    ghc-options: -msse4.2+    cc-options: -msse4.2+  if flag(bmi2)+    cc-options: -mbmi2+  if (flag(bmi2)) && (impl(ghc >=8.4.1))+    ghc-options: -mbmi2 -msse4.2+  if flag(avx2)+    cc-options: -mavx2+  if (flag(avx2)) && (impl(ghc >=8.4.1))+    ghc-options: -mbmi2 -msse4.2+  if (impl(ghc >=8.0.1))+    ghc-options: -Wcompat -Wincomplete-record-updates -Wincomplete-uni-patterns -Wredundant-constraints+  default-language: Haskell2010++executable hw-json-simd+  import:   base+          , bytestring+          , hw-prim+          , lens+          , optparse-applicative+          , semigroups+          , vector+  main-is: Main.hs+  autogen-modules:  Paths_hw_json_simd+  other-modules:+      App.Commands+      App.Commands.Capabilities+      App.Commands.CreateIndex+      App.Commands.Types+      App.Lens+      Paths_hw_json_simd+  hs-source-dirs:   app+  ghc-options: -Wall -threaded -rtsopts -with-rtsopts=-N+  build-depends: hw-json-simd+  if flag(sse42)+    ghc-options: -msse4.2+    cc-options: -msse4.2+  if flag(bmi2)+    cc-options: -mbmi2+  if (flag(bmi2)) && (impl(ghc >=8.4.1))+    ghc-options: -mbmi2 -msse4.2+  if flag(avx2)+    cc-options: -mavx2+  if (flag(avx2)) && (impl(ghc >=8.4.1))+    ghc-options: -mbmi2 -msse4.2+  if (impl(ghc >=8.0.1))+    ghc-options: -Wcompat -Wincomplete-record-updates -Wincomplete-uni-patterns -Wredundant-constraints+  default-language: Haskell2010++test-suite hw-json-simd-test+  import:   base+          , bytestring+          , hw-prim+          , lens+          , vector+  type: exitcode-stdio-1.0+  main-is: Spec.hs+  autogen-modules:  Paths_hw_json_simd+  other-modules:    Paths_hw_json_simd+  hs-source-dirs:   test+  ghc-options: -Wall -threaded -rtsopts -with-rtsopts=-N+  build-depends: hw-json-simd+  if flag(sse42)+    ghc-options: -msse4.2+    cc-options: -msse4.2+  if flag(bmi2)+    cc-options: -mbmi2+  if (flag(bmi2)) && (impl(ghc >=8.4.1))+    ghc-options: -mbmi2 -msse4.2+  if flag(avx2)+    cc-options: -mavx2+  if (flag(avx2)) && (impl(ghc >=8.4.1))+    ghc-options: -mbmi2 -msse4.2+  if (impl(ghc >=8.0.1))+    ghc-options: -Wcompat -Wincomplete-record-updates -Wincomplete-uni-patterns -Wredundant-constraints+  if (!impl(ghc >=8.0.1))+    build-depends:+        semigroups >=0.8.4 && <0.19+      , transformers >=0.4 && <0.6+  default-language: Haskell2010
+ src/HaskellWorks/Data/Json/Simd/Capabilities.hs view
@@ -0,0 +1,16 @@+module HaskellWorks.Data.Json.Simd.Capabilities where++import qualified HaskellWorks.Data.Json.Simd.Internal.Foreign as F+import qualified System.IO.Unsafe                             as U++avx_2 :: Bool+avx_2 = U.unsafePerformIO F.enabled_avx_2 /= 0+{-# NOINLINE avx_2 #-}++sse_4_2 :: Bool+sse_4_2 = U.unsafePerformIO F.enabled_sse_4_2 /= 0+{-# NOINLINE sse_4_2 #-}++bmi_2 :: Bool+bmi_2 = U.unsafePerformIO F.enabled_bmi_2 /= 0+{-# NOINLINE bmi_2 #-}
+ src/HaskellWorks/Data/Json/Simd/Index/Simple.hs view
@@ -0,0 +1,148 @@+{-# LANGUAGE GADTs      #-}+{-# LANGUAGE RankNTypes #-}++module HaskellWorks.Data.Json.Simd.Index.Simple+  ( makeSimpleJsonIbBps+  , makeSimpleJsonIbBpsUnsafe+  , enabledMakeSimpleJsonIbBps+  ) where++import Control.Monad.ST+import Data.Word+import HaskellWorks.Data.Json.Simd.Internal.Index.Simple++import qualified Control.Monad.ST.Unsafe                      as ST+import qualified Data.ByteString                              as BS+import qualified Data.ByteString.Internal                     as BSI+import qualified Data.ByteString.Lazy                         as LBS+import qualified Data.Vector.Storable.Mutable                 as DVSM+import qualified Foreign.ForeignPtr                           as F+import qualified Foreign.ForeignPtr.Unsafe                    as F+import qualified Foreign.Marshal.Unsafe                       as F+import qualified Foreign.Ptr                                  as F+import qualified HaskellWorks.Data.Json.Simd.Capabilities     as C+import qualified HaskellWorks.Data.Json.Simd.Internal.Foreign as F+import qualified HaskellWorks.Data.Json.Simd.Internal.List    as L+import qualified System.IO.Unsafe                             as IO++{-# ANN module ("HLint: ignore Reduce duplication"  :: String) #-}+{-# ANN module ("HLint: ignore Redundant do"        :: String) #-}++makeSimpleJsonIbBps :: LBS.ByteString -> Either String [(BS.ByteString, BS.ByteString)]+makeSimpleJsonIbBps lbs = if enabledMakeSimpleJsonIbBps+  then Right (makeSimpleJsonIbBpsUnsafe lbs)+  else Left "makeSimpleJsonIbBps function is disabled"++makeSimpleJsonIbBpsUnsafe :: LBS.ByteString -> [(BS.ByteString, BS.ByteString)]+makeSimpleJsonIbBpsUnsafe lbs = L.zipPadded BS.empty BS.empty ibs bps+  where chunks  = makeIbs lbs+        ibs     = fmap (\(a, _, _) -> a) chunks+        bps     = ibsToIndexByteStrings chunks++makeIbs :: LBS.ByteString -> [(BS.ByteString, BS.ByteString, BS.ByteString)]+makeIbs lbs = F.unsafeLocalState $ do+  wb <- allocWorkBuffers (32 * 1024 * 1204)+  ws <- allocWorkState+  IO.unsafeInterleaveIO $ go wb ws (LBS.toChunks lbs)+  where go :: WorkBuffers -> WorkState -> [BS.ByteString] -> IO [(BS.ByteString, BS.ByteString, BS.ByteString)]+        go _  _  []       = return []+        go wb ws (bs:bss) = do+          let resLen = BS.length bs `div` 8+          resIbFptr  <- F.mallocForeignPtrBytes resLen+          resAFptr   <- F.mallocForeignPtrBytes resLen+          resBFptr   <- F.mallocForeignPtrBytes resLen+          let resIbPtr  = F.castPtr (F.unsafeForeignPtrToPtr resIbFptr)+          let resAPtr   = F.castPtr (F.unsafeForeignPtrToPtr resAFptr )+          let resBPtr   = F.castPtr (F.unsafeForeignPtrToPtr resBFptr )+          let (bsFptr, bsOff, bsLen) = BSI.toForeignPtr bs+          let bsPtr = F.castPtr (F.unsafeForeignPtrToPtr bsFptr)+          _ <- F.processChunk+            (F.plusPtr bsPtr bsOff) -- in_buffer:           Ptr UInt8+            (fromIntegral bsLen)    -- in_length:           Size+            (workBuffersD wb)       -- work_bits_of_d:      Ptr UInt8+            (workBuffersA wb)       -- work_bits_of_a:      Ptr UInt8+            (workBuffersZ wb)       -- work_bits_of_z:      Ptr UInt8+            (workBuffersQ wb)       -- work_bits_of_q:      Ptr UInt8+            (workBuffersB wb)       -- work_bits_of_b:      Ptr UInt8+            (workBuffersE wb)       -- work_bits_of_e:      Ptr UInt8+            (workStateZ ws)         -- last_trailing_ones:  Ptr Size+            (workStateO ws)         -- quote_odds_carry:    Ptr Size+            (workStateE ws)         -- quote_evens_carry:   Ptr Size+            (workStateM ws)         -- quote_mask_carry:    Ptr UInt64+            resIbPtr                -- result_ibs:          Ptr UInt8+            resAPtr                 -- result_a:            Ptr UInt8+            resBPtr                 -- result_z:            Ptr UInt8+          let r =+                ( BSI.fromForeignPtr resIbFptr 0 resLen+                , BSI.fromForeignPtr resAFptr  0 resLen+                , BSI.fromForeignPtr resBFptr  0 resLen+                )+          rs <- IO.unsafeInterleaveIO $ go wb ws bss+          return (r:rs)++ibsToIndexByteStrings :: ()+  => [(BS.ByteString, BS.ByteString, BS.ByteString)]+  -> [BS.ByteString]+ibsToIndexByteStrings bits = F.unsafeLocalState $ do+  bpState <- emptyBpState+  IO.unsafeInterleaveIO $ go bpState (fmap (\(a, b, c) -> mkIndexStep a b c) bits)+  where go :: ()+          => BpState+          -> [Step]+          -> IO [BS.ByteString]+        go s (step:steps) = do+          let bp = stepToByteString s step+          bps <- IO.unsafeInterleaveIO $ go s steps+          return $ bp:bps+        go s [] = return [stepToByteString s indexStepFinal]++mkIndexStep :: BS.ByteString -> BS.ByteString -> BS.ByteString -> Step+mkIndexStep is as zs | isLen == asLen && asLen == zsLen = Step go isLen+  where isLen = BS.length is+        asLen = BS.length as+        zsLen = BS.length zs+        (isFptr, _, _) = BSI.toForeignPtr is+        (asFptr, _, _) = BSI.toForeignPtr as+        (zsFptr, _, _) = BSI.toForeignPtr zs+        go  :: BpState+            -> DVSM.MVector s Word64+            -> ST s Int+        go bpState bpvm = fmap fromIntegral . ST.unsafeIOToST $ do+          let (outFptr, _, _) = DVSM.unsafeToForeignPtr bpvm++          F.withForeignPtr outFptr $ \outPtr ->+            F.withForeignPtr isFptr $ \isPtr ->+              F.withForeignPtr asFptr $ \asPtr ->+                F.withForeignPtr zsFptr $ \zsPtr ->+                  F.withForeignPtr (bpStateP bpState) $ \bpStatePtr -> do+                    F.writeBpChunk+                      (F.castPtr isPtr)+                      (F.castPtr asPtr)+                      (F.castPtr zsPtr)+                      (fromIntegral (BS.length is))+                      (F.castPtr bpStatePtr)+                      (F.castPtr outPtr)+mkIndexStep _ _ _ = error "Mismatched input size"++indexStepFinal :: Step+indexStepFinal = Step go 2+  where go  :: BpState+            -> DVSM.MVector s Word64+            -> ST s Int+        go bpState bpvm = fmap fromIntegral . ST.unsafeIOToST $ do+          let (outFptr, _, _) = DVSM.unsafeToForeignPtr bpvm++          F.withForeignPtr outFptr $ \outPtr ->+            F.withForeignPtr (bpStateP bpState) $ \bpStatePtr -> do+              F.writeBpChunkFinal (F.castPtr bpStatePtr) (F.castPtr outPtr)++stepToByteString :: BpState -> Step -> BS.ByteString+stepToByteString state (Step step size) = F.unsafeLocalState $ do+  let bsSize = size * 8+  bpFptr <- BSI.mallocByteString bsSize+  let bpVm = DVSM.unsafeFromForeignPtr (F.castForeignPtr bpFptr) 0 size+  w64Size <- stToIO $ step state bpVm+  return (BSI.PS bpFptr 0 (w64Size * 8))++enabledMakeSimpleJsonIbBps :: Bool+enabledMakeSimpleJsonIbBps = C.avx_2 && C.sse_4_2 && C.bmi_2
+ src/HaskellWorks/Data/Json/Simd/Index/Standard.hs view
@@ -0,0 +1,112 @@+{-# LANGUAGE BangPatterns        #-}+{-# LANGUAGE GADTs               #-}+{-# LANGUAGE RankNTypes          #-}+{-# LANGUAGE ScopedTypeVariables #-}++module HaskellWorks.Data.Json.Simd.Index.Standard+  ( makeStandardJsonIbBps+  , makeStandardJsonIbBpsUnsafe+  , enabledMakeStandardJsonIbBps+  ) where++import Control.Monad+import Data.Word+import HaskellWorks.Data.Json.Simd.Internal.Index.Standard++import qualified Data.ByteString                              as BS+import qualified Data.ByteString.Internal                     as BSI+import qualified Data.ByteString.Lazy                         as LBS+import qualified Foreign.ForeignPtr                           as F+import qualified Foreign.ForeignPtr.Unsafe                    as F+import qualified Foreign.Marshal.Unsafe                       as F+import qualified Foreign.Ptr                                  as F+import qualified Foreign.Storable                             as F+import qualified HaskellWorks.Data.Json.Simd.Capabilities     as C+import qualified HaskellWorks.Data.Json.Simd.Internal.Foreign as F+import qualified System.IO.Unsafe                             as IO++{-# ANN module ("HLint: ignore Reduce duplication"  :: String) #-}+{-# ANN module ("HLint: ignore Redundant do"        :: String) #-}++makeStandardJsonIbBps :: LBS.ByteString -> Either String [(BS.ByteString, BS.ByteString)]+makeStandardJsonIbBps lbs = if enabledMakeStandardJsonIbBps+  then Right (makeStandardJsonIbBpsUnsafe lbs)+  else Left "makeStandardJsonIbBps function is disabled"++makeStandardJsonIbBpsUnsafe :: LBS.ByteString -> [(BS.ByteString, BS.ByteString)]+makeStandardJsonIbBpsUnsafe lbs = F.unsafeLocalState $ do+  wb <- allocWorkBuffers (32 * 1024 * 1204)+  ws <- newWorkState 0+  fptrState       :: F.ForeignPtr F.UInt32  <- F.mallocForeignPtr+  fptrRemBits     :: F.ForeignPtr F.UInt64  <- F.mallocForeignPtr+  fptrRemBitsLen  :: F.ForeignPtr F.Size    <- F.mallocForeignPtr+  let ptrState      = F.unsafeForeignPtrToPtr fptrState+  let ptrRemBits    = F.unsafeForeignPtrToPtr fptrRemBits+  let ptrRemBitsLen = F.unsafeForeignPtrToPtr fptrRemBitsLen+  F.poke ptrState       0+  F.poke ptrRemBits     0+  F.poke ptrRemBitsLen  0+  IO.unsafeInterleaveIO $ go wb ws fptrState fptrRemBits fptrRemBitsLen (LBS.toChunks lbs)+  where go :: ()+          => WorkBuffers+          -> WorkState+          -> F.ForeignPtr F.UInt32+          -> F.ForeignPtr F.UInt64+          -> F.ForeignPtr F.Size+          -> [BS.ByteString]+          -> IO [(BS.ByteString, BS.ByteString)]+        go _ _ _ fptrRemBits fptrRemBitsLen  []       = do+          resBpFptr  <- F.mallocForeignPtrBytes 8+          let resBpPtr      = F.castPtr (F.unsafeForeignPtrToPtr resBpFptr  )+          let ptrRemBits    = F.unsafeForeignPtrToPtr fptrRemBits+          let ptrRemBitsLen = F.unsafeForeignPtrToPtr fptrRemBitsLen+          remBits     <- F.peek ptrRemBits+          remBitsLen  <- F.peek ptrRemBitsLen+          bpByteLen <- F.smWriteBpChunkFinal+            remBits     -- remaining_bp_bits+            remBitsLen  -- remaning_bp_bits_len+            resBpPtr    -- out_buffer+          return  [ ( BS.empty+                    , BSI.fromForeignPtr resBpFptr 0 (fromIntegral bpByteLen * 8)+                    )+                  ]+        go wb ws fptrState fptrRemBits fptrRemBitsLen (bs:bss) = do+          let (!bsFptr, !bsOff, !bsLen) = BSI.toForeignPtr bs+          let !idxByteLen = (bsLen + 7) `div` 8+          resIbFptr  <- F.mallocForeignPtrBytes idxByteLen+          resBpFptr  <- F.mallocForeignPtrBytes idxByteLen+          let resIbPtr      = F.castPtr (F.unsafeForeignPtrToPtr resIbFptr  )+          let resBpPtr      = F.castPtr (F.unsafeForeignPtrToPtr resBpFptr  )+          let bsPtr         = F.castPtr (F.unsafeForeignPtrToPtr bsFptr)+          let ptrState      = F.unsafeForeignPtrToPtr fptrState+          let ptrRemBits    = F.unsafeForeignPtrToPtr fptrRemBits+          let ptrRemBitsLen = F.unsafeForeignPtrToPtr fptrRemBitsLen+          s :: Word8 <- fromIntegral <$> F.peek ptrState+          void $ F.smProcessChunk+            (F.plusPtr bsPtr bsOff) -- in_buffer:   Ptr UInt8+            (fromIntegral bsLen)    -- in_length:   Size+            ptrState                -- work state:  Ptr UInt32+            (workBuffersP wb)       -- result_phi:  Ptr UInt8+          void $ F.smMakeIbOpClChunks+            (fromIntegral s)          -- state+            (workBuffersP wb)         -- in_phis+            (fromIntegral bsLen)      -- phi_length+            resIbPtr                  -- out_ibs+            (workBuffersO wb)         -- out_ops+            (workBuffersC wb)         -- out_cls+          bpByteLen <- F.smWriteBpChunk+            (workBuffersO wb)         -- result_op+            (workBuffersC wb)         -- result_cl+            (fromIntegral idxByteLen) -- ib_bytes+            ptrRemBits                -- remaining_bp_bits+            ptrRemBitsLen             -- remaning_bp_bits_len+            resBpPtr                  -- out_buffer+          let !r =+                ( BSI.fromForeignPtr resIbFptr 0 idxByteLen+                , BSI.fromForeignPtr resBpFptr 0 (fromIntegral bpByteLen * 8)+                )+          rs <- IO.unsafeInterleaveIO $ go wb ws fptrState fptrRemBits fptrRemBitsLen bss+          return (r:rs)++enabledMakeStandardJsonIbBps :: Bool+enabledMakeStandardJsonIbBps = C.avx_2 && C.sse_4_2 && C.bmi_2
+ src/HaskellWorks/Data/Json/Simd/Internal/Foreign.chs view
@@ -0,0 +1,109 @@+{-# LANGUAGE CPP #-}+{-# LANGUAGE ForeignFunctionInterface #-}++module HaskellWorks.Data.Json.Simd.Internal.Foreign where++import Foreign+import System.IO.Unsafe++#include "../cbits/simd.h"++type UInt8  = {#type uint8_t #}+type UInt32 = {#type uint32_t#}+type UInt64 = {#type uint64_t#}+type Size   = {#type size_t  #}++enabled_avx_2 :: IO Int+enabled_avx_2 = fromIntegral <$> do+  {#call unsafe hw_json_simd_avx2_enabled as c_hw_json_simd_avx2_enabled#}+{-# NOINLINE enabled_avx_2 #-}++enabled_sse_4_2 :: IO Int+enabled_sse_4_2 = fromIntegral <$> do+  {#call unsafe hw_json_simd_sse4_2_enabled as c_hw_json_simd_sse4_2_enabled#}+{-# NOINLINE enabled_sse_4_2 #-}++enabled_bmi_2 :: IO Int+enabled_bmi_2 = fromIntegral <$> do+  {#call unsafe hw_json_simd_bmi2_enabled as c_hw_json_simd_bmi2_enabled#}+{-# NOINLINE enabled_bmi_2 #-}++processChunk :: ()+  => Ptr UInt8    -- in_buffer+  -> Size         -- in_length+  -> Ptr UInt8    -- work_bits_of_d+  -> Ptr UInt8    -- work_bits_of_a+  -> Ptr UInt8    -- work_bits_of_z+  -> Ptr UInt8    -- work_bits_of_q+  -> Ptr UInt8    -- work_bits_of_b+  -> Ptr UInt8    -- work_bits_of_e+  -> Ptr Size     -- last_trailing_ones+  -> Ptr Size     -- quote_odds_carry+  -> Ptr Size     -- quote_evens_carry+  -> Ptr UInt64   -- quote_mask_carry+  -> Ptr UInt8    -- result_ibs+  -> Ptr UInt8    -- result_a+  -> Ptr UInt8    -- result_z+  -> IO UInt64+processChunk = do+  {#call unsafe hw_json_simd_process_chunk as c_hw_json_simd_process_chunk#}+{-# INLINE processChunk #-}++initBpState :: ()+  => Ptr ()+  -> IO ()+initBpState = {#call unsafe hw_json_simd_init_bp_state as c_hw_json_simd_init_bp_state#}+{-# INLINE initBpState #-}++writeBpChunk :: ()+  => Ptr UInt8  -- result_ib+  -> Ptr UInt8  -- result_a+  -> Ptr UInt8  -- result_z+  -> Size       -- ib_bytes+  -> Ptr ()     -- bp_state+  -> Ptr UInt8  -- out_buffer+  -> IO Size+writeBpChunk = {#call unsafe hw_json_simd_write_bp_chunk as c_hw_json_simd_write_bp_chunk#}+{-# INLINE writeBpChunk #-}++writeBpChunkFinal :: ()+  => Ptr ()     -- bp_state+  -> Ptr UInt8  -- out_buffer+  -> IO Size+writeBpChunkFinal = {#call unsafe hw_json_simd_write_bp_chunk_final as c_hw_json_simd_write_bp_chunk_final#}+{-# INLINE writeBpChunkFinal #-}++smProcessChunk :: ()+  => Ptr UInt8    -- in_buffer+  -> Size         -- in_length+  -> Ptr UInt32   -- inout_state+  -> Ptr UInt32   -- out_phi_buffer+  -> IO ()+smProcessChunk = {#call unsafe hw_json_simd_sm_process_chunk as c_hw_json_simd_sm_process_chunk#}++smMakeIbOpClChunks :: ()+  => UInt8        -- state+  -> Ptr UInt32   -- in_phis+  -> Size         -- phi_length+  -> Ptr UInt8    -- out_ibs+  -> Ptr UInt8    -- out_ops+  -> Ptr UInt8    -- out_cls+  -> IO ()+smMakeIbOpClChunks = {#call unsafe hw_json_simd_sm_make_ib_op_cl_chunks as c_hw_json_simd_sm_make_ib_op_cl_chunks#}++smWriteBpChunk :: ()+  => Ptr UInt8    -- result_op+  -> Ptr UInt8    -- result_cl+  -> Size         -- ib_bytes+  -> Ptr UInt64   -- remaining_bp_bits+  -> Ptr Size     -- remaning_bp_bits_len+  -> Ptr UInt64   -- out_buffer+  -> IO Size+smWriteBpChunk = {#call unsafe hw_json_simd_sm_write_bp_chunk as c_hw_json_simd_sm_write_bp_chunk#}++smWriteBpChunkFinal :: ()+  => UInt64       -- remaining_bits+  -> Size         -- remaining_bits_len+  -> Ptr UInt64   -- out_buffer+  -> IO Size+smWriteBpChunkFinal = {#call unsafe hw_json_simd_sm_write_bp_chunk_final as c_hw_json_simd_sm_write_bp_chunk_final#}
+ src/HaskellWorks/Data/Json/Simd/Internal/Index/Simple.hs view
@@ -0,0 +1,82 @@+{-# LANGUAGE GADTs      #-}+{-# LANGUAGE RankNTypes #-}++module HaskellWorks.Data.Json.Simd.Internal.Index.Simple where++import Control.Monad.ST+import Data.Word+import Foreign++import qualified Data.Vector.Storable.Mutable                 as DVSM+import qualified Foreign                                      as F+import qualified Foreign.ForeignPtr.Unsafe                    as F+import qualified HaskellWorks.Data.Json.Simd.Internal.Foreign as F++{-# ANN module ("HLint: ignore Reduce duplication"  :: String) #-}+{-# ANN module ("HLint: ignore Redundant do"        :: String) #-}++data WorkBuffers = WorkBuffers+  { workBuffersP :: !(ForeignPtr F.UInt8)+  , workBuffersD :: !(Ptr F.UInt8)+  , workBuffersA :: !(Ptr F.UInt8)+  , workBuffersZ :: !(Ptr F.UInt8)+  , workBuffersQ :: !(Ptr F.UInt8)+  , workBuffersB :: !(Ptr F.UInt8)+  , workBuffersE :: !(Ptr F.UInt8)+  }++data WorkState = WorkState+  { workStateZ :: !(Ptr F.Size)+  , workStateO :: !(Ptr F.Size)+  , workStateE :: !(Ptr F.Size)+  , workStateM :: !(Ptr F.UInt64)+  , workStateP :: !(ForeignPtr Word8)+  }++newtype BpState = BpState+  { bpStateP :: ForeignPtr Word8+  }++data Step where+  Step :: ( forall s+            .   BpState+            ->  DVSM.MVector s Word64+            ->  ST s Int)+          -> Int+          -> Step++emptyBpState :: IO BpState+emptyBpState = do+  fptr <- F.mallocForeignPtrBytes 32+  return (BpState (F.castForeignPtr fptr))++allocWorkBuffers :: Int -> IO WorkBuffers+allocWorkBuffers n = do+  fptr <- F.mallocForeignPtrBytes (6 * n)+  let ptr = F.unsafeForeignPtrToPtr fptr+  return WorkBuffers+    { workBuffersP = fptr+    , workBuffersD = ptr `F.plusPtr`  0+    , workBuffersA = ptr `F.plusPtr`  n+    , workBuffersZ = ptr `F.plusPtr` (n * 2)+    , workBuffersQ = ptr `F.plusPtr` (n * 3)+    , workBuffersB = ptr `F.plusPtr` (n * 4)+    , workBuffersE = ptr `F.plusPtr` (n * 5)+    }++allocWorkState :: IO WorkState+allocWorkState = do+  fptr <- F.mallocForeignPtrBytes 256+  let ptr = F.unsafeForeignPtrToPtr fptr+  let ws = WorkState+        { workStateZ = ptr `F.plusPtr`  0+        , workStateO = ptr `F.plusPtr`  8+        , workStateE = ptr `F.plusPtr` (8 * 2)+        , workStateM = ptr `F.plusPtr` (8 * 3)+        , workStateP = fptr+        }+  F.poke (workStateZ ws) 0+  F.poke (workStateO ws) 0+  F.poke (workStateE ws) 1+  F.poke (workStateM ws) 0+  return ws
+ src/HaskellWorks/Data/Json/Simd/Internal/Index/Standard.hs view
@@ -0,0 +1,54 @@+{-# LANGUAGE GADTs      #-}+{-# LANGUAGE RankNTypes #-}++module HaskellWorks.Data.Json.Simd.Internal.Index.Standard where++import Data.Word+import Foreign++import qualified Foreign                                      as F+import qualified Foreign.ForeignPtr.Unsafe                    as F+import qualified HaskellWorks.Data.Json.Simd.Internal.Foreign as F++{-# ANN module ("HLint: ignore Reduce duplication"  :: String) #-}+{-# ANN module ("HLint: ignore Redundant do"        :: String) #-}++data WorkBuffers = WorkBuffers+  { workBuffersF :: !(ForeignPtr F.UInt8)+  , workBuffersP :: !(Ptr F.UInt32)+  , workBuffersO :: !(Ptr F.UInt8)+  , workBuffersC :: !(Ptr F.UInt8)+  }++data WorkState = WorkState+  { workStateFptr       :: !(ForeignPtr Word8)+  , workStateRemBits    :: !(Ptr F.UInt64)+  , workStateRemBitsLen :: !(Ptr F.Size)+  , workStateState      :: !(Ptr F.UInt32)+  }++allocWorkBuffers :: Int -> IO WorkBuffers+allocWorkBuffers n = do+  fptr <- F.mallocForeignPtrBytes (3 * n)+  let ptr = F.unsafeForeignPtrToPtr fptr+  return WorkBuffers+    { workBuffersF = fptr+    , workBuffersP = ptr `F.plusPtr`  0+    , workBuffersO = ptr `F.plusPtr`  n+    , workBuffersC = ptr `F.plusPtr` (n * 2)+    }++newWorkState :: Word32 -> IO WorkState+newWorkState initialValue = do+  fptr <- F.mallocForeignPtrBytes 256+  let ptr = F.unsafeForeignPtrToPtr fptr+  let ws = WorkState+        { workStateState      = ptr `F.plusPtr`  0+        , workStateRemBits    = ptr `F.plusPtr`  8+        , workStateRemBitsLen = ptr `F.plusPtr`  16+        , workStateFptr       = fptr+        }+  F.poke (workStateState      ws) (fromIntegral initialValue)+  F.poke (workStateRemBits    ws) 0+  F.poke (workStateRemBitsLen ws) 0+  return ws
+ src/HaskellWorks/Data/Json/Simd/Internal/List.hs view
@@ -0,0 +1,9 @@+module HaskellWorks.Data.Json.Simd.Internal.List+  ( zipPadded+  ) where++zipPadded :: a -> b -> [a] -> [b] -> [(a, b)]+zipPadded a b (c:cs) (d:ds) = (c, d):zipPadded a b cs ds+zipPadded a b []     (d:ds) = (a, d):zipPadded a b [] ds+zipPadded a b (c:cs) []     = (c, b):zipPadded a b cs []+zipPadded _ _ []     []     = []
+ test/Spec.hs view
@@ -0,0 +1,2 @@+main :: IO ()+main = putStrLn "Test suite not yet implemented"