base64

Fast Haskell base64 encoding/decoding (docs.ppad.tech/base64).
git clone git://git.ppad.tech/base64.git
Log | Files | Refs | README | LICENSE

Main.hs (8164B)


      1 {-# OPTIONS_GHC -fno-warn-missing-signatures #-}
      2 {-# LANGUAGE OverloadedStrings #-}
      3 {-# LANGUAGE PackageImports #-}
      4 
      5 module Main where
      6 
      7 import Control.Monad (forM_, when)
      8 import qualified Data.ByteString as BS
      9 import qualified Data.ByteString.Char8 as B8
     10 import qualified "ppad-base64" Data.ByteString.Base64 as B64
     11 import qualified "ppad-base64" Data.ByteString.Base64.Pure as Pure
     12 import qualified "base64-bytestring" Data.ByteString.Base64 as R0
     13 import Data.Word (Word8)
     14 import Test.Tasty
     15 import qualified Test.Tasty.QuickCheck as Q
     16 import qualified Test.Tasty.HUnit as H
     17 
     18 -- generators -----------------------------------------------------------------
     19 
     20 -- random bytes, as a slice at a random offset into a larger buffer, so
     21 -- that inputs with a non-zero 'ByteString' offset are exercised
     22 bytes :: Int -> Q.Gen BS.ByteString
     23 bytes k = do
     24   l <- Q.chooseInt (0, k)
     25   o <- Q.chooseInt (0, 32)
     26   v <- Q.vectorOf (o + l) Q.arbitrary
     27   pure (BS.drop o (BS.pack v))
     28 
     29 newtype BS = BS BS.ByteString
     30   deriving (Eq, Show)
     31 
     32 instance Q.Arbitrary BS where
     33   arbitrary = do
     34     b <- bytes 1024
     35     pure (BS b)
     36 
     37 alphabet :: BS.ByteString
     38 alphabet =
     39   "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
     40 
     41 -- valid encodings subjected to a few random mutations: substitution
     42 -- (by an alphabet char, '=', or an arbitrary byte), deletion, or
     43 -- insertion, with positions biased toward the final quartet
     44 newtype Base64ish = Base64ish BS.ByteString
     45   deriving (Eq, Show)
     46 
     47 instance Q.Arbitrary Base64ish where
     48   arbitrary = do
     49     b <- Q.frequency [(3, bytes 64), (1, bytes 384)]
     50     k <- Q.chooseInt (0, 3)
     51     s <- go k (B64.encode b)
     52     o <- Q.chooseInt (0, 32)
     53     p <- Q.vectorOf o (Q.elements (BS.unpack alphabet))
     54     pure (Base64ish (BS.drop o (BS.pack p <> s)))
     55     where
     56       go :: Int -> BS.ByteString -> Q.Gen BS.ByteString
     57       go 0 s = pure s
     58       go j s = mutate s >>= go (j - 1)
     59 
     60       mutate s = do
     61         let l = BS.length s
     62         i <- Q.oneof [
     63             Q.chooseInt (0, l)
     64           , Q.chooseInt (max 0 (l - 4), l)
     65           ]
     66         c <- Q.frequency [
     67             (6, Q.elements (BS.unpack alphabet))
     68           , (2, pure 0x3d)
     69           , (1, Q.arbitrary)
     70           ]
     71         Q.elements [
     72             BS.take i s <> BS.singleton c <> BS.drop (i + 1) s
     73           , BS.take i s <> BS.drop (i + 1) s
     74           , BS.take i s <> BS.singleton c <> BS.drop i s
     75           ]
     76 
     77 -- decoders under test --------------------------------------------------------
     78 
     79 decoders :: [(String, BS.ByteString -> Maybe BS.ByteString)]
     80 decoders = [("public", B64.decode), ("pure", Pure.decode)]
     81 
     82 ref_decode :: BS.ByteString -> Maybe BS.ByteString
     83 ref_decode bs = case R0.decode bs of
     84   Left _  -> Nothing
     85   Right d -> Just d
     86 
     87 -- properties -----------------------------------------------------------------
     88 
     89 encode_matches_reference :: BS -> Bool
     90 encode_matches_reference (BS bs) =
     91   let r0 = R0.encode bs
     92   in  B64.encode bs == r0 && Pure.encode bs == r0
     93 
     94 decode_inverts_encode :: BS -> Bool
     95 decode_inverts_encode (BS bs) =
     96   let enc = B64.encode bs
     97   in  all (\(_, dec) -> dec enc == Just bs) decoders
     98 
     99 -- base64-bytestring's 'decode' is likewise strict (RFC 4648): it
    100 -- rejects missing or misplaced padding and non-canonical final quartets
    101 decode_matches_reference :: Base64ish -> Bool
    102 decode_matches_reference (Base64ish bs) =
    103   let r0 = ref_decode bs
    104   in  B64.decode bs == r0 && Pure.decode bs == r0
    105 
    106 -- unit tests -----------------------------------------------------------------
    107 
    108 case_rfc_vectors :: TestTree
    109 case_rfc_vectors = H.testCase "RFC 4648 \167 10 vectors" $ do
    110   let vectors = [
    111           ("",       "")
    112         , ("f",      "Zg==")
    113         , ("fo",     "Zm8=")
    114         , ("foo",    "Zm9v")
    115         , ("foob",   "Zm9vYg==")
    116         , ("fooba",  "Zm9vYmE=")
    117         , ("foobar", "Zm9vYmFy")
    118         ]
    119       check (input, expected) = do
    120         H.assertEqual ("encode " <> show input)
    121           expected (B64.encode input)
    122         H.assertEqual ("pure encode " <> show input)
    123           expected (Pure.encode input)
    124         forM_ decoders $ \(nam, dec) ->
    125           H.assertEqual (nam <> " decode " <> show expected)
    126             (Just input) (dec expected)
    127   mapM_ check vectors
    128 
    129 -- malformed final quartets, alone and after a body long enough to
    130 -- take the NEON path
    131 malformed :: TestTree
    132 malformed = H.testCase "malformed padding and non-canonical tails" $ do
    133   let bad = [
    134           "Zh=="     -- non-canonical: nonzero trailing bits
    135         , "Zm9="     -- non-canonical: nonzero trailing bits
    136         , "Zm=v"     -- '=' before a data char
    137         , "===="
    138         , "Z==="
    139         , "=Zg="
    140         , "Zg=a"
    141         , "Zg=", "Zg", "Z"
    142         , "Zm9vY"
    143         , "Zm=vYmFy" -- '=' in the body
    144         , "Zg==Zg==" -- padding mid-stream
    145         , "Zm9v\n"
    146         ]
    147       good = [("Zg==", "f"), ("Zm8=", "fo"), ("Zm9v", "foo")]
    148       body = B64.encode (BS.replicate 72 0xa5)
    149   forM_ decoders $ \(nam, dec) -> do
    150     forM_ bad $ \s -> do
    151       H.assertEqual (nam <> " " <> show s) Nothing (dec s)
    152       H.assertEqual (nam <> " body <> " <> show s) Nothing (dec (body <> s))
    153     forM_ good $ \(s, d) ->
    154       H.assertEqual (nam <> " body <> " <> show s)
    155         (Just (BS.replicate 72 0xa5 <> d)) (dec (body <> s))
    156 
    157 -- every byte value, at every position of encodings that span the NEON
    158 -- body loop, the scalar body tail, and each kind of final quartet,
    159 -- decodes exactly as the reference does; in the body, a byte is
    160 -- accepted iff it is an alphabet char
    161 every_byte_every_position :: TestTree
    162 every_byte_every_position =
    163   H.testCase "every byte at every position" $
    164     forM_ [28, 29, 30 :: Int] $ \n -> do
    165       let base = B64.encode (BS.replicate n 0x00)
    166           l    = BS.length base
    167       forM_ [0 .. 255 :: Int] $ \c ->
    168         forM_ [0 .. l - 1] $ \i -> do
    169           let w   = fromIntegral c :: Word8
    170               inp = BS.take i base <> BS.singleton w <> BS.drop (i + 1) base
    171               pec = ref_decode inp
    172               msg = "n = " <> show n <> ", byte " <> show c
    173                     <> ", position " <> show i
    174           when (i < l - 4) $
    175             H.assertEqual ("reference, " <> msg)
    176               (BS.elem w alphabet) (pec /= Nothing)
    177           forM_ decoders $ \(nam, dec) ->
    178             H.assertEqual (nam <> ", " <> msg) pec (dec inp)
    179 
    180 -- for every length spanning several NEON iterations and each final
    181 -- quartet shape, a single invalid byte at any position (or '=' anywhere
    182 -- in the body) causes decoding to fail
    183 single_corruption :: TestTree
    184 single_corruption = H.testCase "single invalid byte anywhere" $ do
    185   let bad = BS.pack [0x00, 0x20, 0x7f, 0x80, 0xff] <> "-_.:@[`{"
    186   forM_ [1 .. 100 :: Int] $ \n -> do
    187     let raw = BS.pack (fmap fromIntegral [7 * j + 3 | j <- [1 .. n]])
    188         enc = B64.encode raw
    189         l   = BS.length enc
    190         put i w = BS.take i enc <> BS.singleton w <> BS.drop (i + 1) enc
    191     forM_ decoders $ \(nam, dec) ->
    192       H.assertEqual (nam <> ", intact, n = " <> show n) (Just raw) (dec enc)
    193     forM_ [0 .. l - 1] $ \i -> do
    194       let ws = BS.unpack bad <> (if i < l - 4 then [0x3d] else [])
    195       forM_ ws $ \w -> do
    196         let msg = "n = " <> show n <> ", position " <> show i
    197                   <> ", byte " <> show w
    198         forM_ decoders $ \(nam, dec) ->
    199           H.assertEqual (nam <> ", " <> msg) Nothing (dec (put i w))
    200 
    201 bad_lengths :: TestTree
    202 bad_lengths = H.testCase "lengths not a multiple of 4" $
    203   forM_ (filter (\l -> l `rem` 4 /= 0) [1 .. 99 :: Int]) $ \l ->
    204     forM_ decoders $ \(nam, dec) ->
    205       H.assertEqual (nam <> ", length " <> show l) Nothing
    206         (dec (B8.replicate l 'A'))
    207 
    208 main :: IO ()
    209 main = defaultMain $
    210   testGroup "ppad-base64" [
    211     testGroup "property tests" [
    212       Q.testProperty "encode matches reference" $
    213         Q.withMaxSuccess 5000 encode_matches_reference
    214     , Q.testProperty "decode . encode ~ id" $
    215         Q.withMaxSuccess 5000 decode_inverts_encode
    216     , Q.testProperty "decode matches reference" $
    217         Q.withMaxSuccess 10000 decode_matches_reference
    218     ]
    219   , testGroup "unit tests" [
    220       case_rfc_vectors
    221     , malformed
    222     , every_byte_every_position
    223     , single_corruption
    224     , bad_lengths
    225     ]
    226   ]