packages feed

kenshou-measure-0.1.0.0: src/Kenshou/Measure/Histogram/Codec.hs

module Kenshou.Measure.Histogram.Codec
  ( encodeHistogram,
    decodeHistogram,
  )
where

import Data.Bits
import Data.ByteString (ByteString)
import Data.ByteString qualified as ByteString
import Data.ByteString.Builder
import Data.ByteString.Lazy qualified as LazyByteString
import Data.Int (Int64)
import Data.Text (Text)
import Data.Word (Word16, Word32, Word64, Word8)
import Kenshou.Measure.Histogram

encodeHistogram :: Histogram -> ByteString
encodeHistogram histogram =
  LazyByteString.toStrict . toLazyByteString $
    byteString "KHST"
      <> word16LE 1
      <> word16LE 0
      <> word64LE config.lowestDiscernible
      <> word64LE config.highestTrackable
      <> word8 (fromIntegral config.significantDigits)
      <> word64LE (totalCount histogram)
      <> word64LE (minValue histogram)
      <> word64LE (maxValue histogram)
      <> word64LE (histogramSum histogram)
      <> word64LE (overflowCount histogram)
      <> word32LE (fromIntegral (length tokens))
      <> foldMap (putVarWord . zigZag) tokens
  where
    config = histogramConfig histogram
    tokens = runLengthEncode (histogramCounts histogram)

decodeHistogram :: ByteString -> Either Text Histogram
decodeHistogram bytes = do
  ensure (ByteString.take 4 bytes == "KHST") "invalid histogram magic"
  version <- word16At bytes 4
  ensure (version == 1) "unsupported histogram version"
  flags <- word16At bytes 6
  ensure (flags == 0) "unsupported histogram flags"
  lowest <- word64At bytes 8
  highest <- word64At bytes 16
  digits <- word8At bytes 24
  count <- word64At bytes 25
  observedMinimum <- word64At bytes 33
  observedMaximum <- word64At bytes 41
  total <- word64At bytes 49
  overflow <- word64At bytes 57
  tokenCount <- word32At bytes 65
  (tokens, _) <- readTokens bytes 69 (fromIntegral tokenCount)
  let config = HistogramConfig lowest highest (fromIntegral digits)
  expectedLength <- histogramLength config
  values <- expandTokens expectedLength tokens
  histogramFromCounts config values count observedMinimum observedMaximum total overflow

histogramLength :: HistogramConfig -> Either Text Int
histogramLength = histogramArrayLength

runLengthEncode :: [Word64] -> [Int64]
runLengthEncode [] = []
runLengthEncode values = go values
  where
    go [] = []
    go (0 : rest) = let (zeros, remaining) = span (== 0) rest in negate (fromIntegral (1 + length zeros)) : go remaining
    go (value : rest) = fromIntegral value : go rest

expandTokens :: Int -> [Int64] -> Either Text [Word64]
expandTokens expected tokens = do
  values <- fmap concat $ traverse expand tokens
  ensure (length values <= expected) "histogram token stream exceeds the configured layout"
  pure (values <> replicate (expected - length values) 0)
  where
    expand value | value < 0 = Right (replicate (fromIntegral (negate value)) 0)
    expand value = Right [fromIntegral value]

readTokens :: ByteString -> Int -> Int -> Either Text ([Int64], Int)
readTokens bytes = go []
  where
    go acc offset 0 = Right (reverse acc, offset)
    go acc offset remaining = do
      (encoded, next) <- readVarWord bytes offset
      go (unZigZag encoded : acc) next (remaining - 1)

putVarWord :: Word64 -> Builder
putVarWord value
  | value < 0x80 = word8 (fromIntegral value)
  | otherwise = word8 (fromIntegral (value .&. 0x7f) .|. 0x80) <> putVarWord (value `shiftR` 7)

readVarWord :: ByteString -> Int -> Either Text (Word64, Int)
readVarWord bytes = go 0 0
  where
    go bitOffset accumulator offset
      | bitOffset >= 64 = Left "varint is too long"
      | offset >= ByteString.length bytes = Left "truncated varint"
      | otherwise =
          let byte = ByteString.index bytes offset
              value = accumulator .|. (fromIntegral (byte .&. 0x7f) `shiftL` bitOffset)
           in if byte .&. 0x80 == 0 then Right (value, offset + 1) else go (bitOffset + 7) value (offset + 1)

zigZag :: Int64 -> Word64
zigZag value = fromIntegral ((value `shiftL` 1) `xor` (value `shiftR` 63))

unZigZag :: Word64 -> Int64
unZigZag value = fromIntegral (value `shiftR` 1) `xor` negate (fromIntegral (value .&. 1))

word8At :: ByteString -> Int -> Either Text Word8
word8At bytes offset
  | offset < ByteString.length bytes = Right (ByteString.index bytes offset)
  | otherwise = Left "truncated histogram header"

word16At :: ByteString -> Int -> Either Text Word16
word16At bytes offset = fromIntegral <$> littleEndianAt bytes offset 2

word32At :: ByteString -> Int -> Either Text Word32
word32At bytes offset = fromIntegral <$> littleEndianAt bytes offset 4

word64At :: ByteString -> Int -> Either Text Word64
word64At bytes offset = littleEndianAt bytes offset 8

littleEndianAt :: ByteString -> Int -> Int -> Either Text Word64
littleEndianAt bytes offset width
  | offset + width > ByteString.length bytes = Left "truncated histogram header"
  | otherwise = Right $ foldr (.|.) 0 [fromIntegral (ByteString.index bytes (offset + index)) `shiftL` (8 * index) | index <- [0 .. width - 1]]

ensure :: Bool -> Text -> Either Text ()
ensure condition message = if condition then Right () else Left message