[Haskell-cafe] Correct parsers for bounded integral values

[Brandon Allbery]

I would like to point out that if you want correctness, you should use
`Integer`. If you are using a bounded `Integral` it is expected that you
are doing so because you value speed over correctness. They are _not_
`Z/n`, they are hardware values that have little to do with formal
mathematics.

On Sun, Jul 20, 2025 at 12:23 PM Viktor Dukhovni <ietf-dane at dukhovni.org>
wrote:

> On Sun, Jul 20, 2025 at 07:08:54AM -0800, Daniil Iaitskov wrote:
>
> > one divMod and double cmp per digit can be replaced with left shift and
> > single cmp per digit which is faster
>
> But, sadly, at first blush not correct as written.  And the multiply is
> not needed, instead, as in the ByteString code, one can take the fast
> path when the old value is at most than 1/10th of the upper bound, fail
> when strictly larger, and take a bit more care when exactly equal.
>
> > CPU is optimized to work with word size values. Assuming word size is
> 64bit
> > then majority of fixed types (Word8 - Word64) fits a register.
> >
> >     {-# SPECIALIZE parse @Int #-}
> >
> > parse :: forall a. Num a => Parsec Word64 -> Word64 -> a
> >
> >    parse nextDigit s old =
> >       nextDigit >>= \case
> >          Nothing -> pure $ fromIntegral s
> >          Just d -> do
> >           let s' = 10 * s + d
> >               new = s' `shiftL` (finiteBitSize s' - finiteBitSize
> (undefined @a))
> >           if old > new then fail "overflow"
> >           else parse nextDigit s' new
>
> It looks like it might not always detect overflow.  Counter-example:
>
>     30 * 10 + 1 = 301
>
> which is 45 mod 256, which happens be larger than 30.  So the above
> would presumably accept "301" returning 45 as a Word8.  Overflow in
> addition of two positive numbers will produce an answer smaller than
> either, but this is not the case with multiplication by 10.
>
> See:
>
>
> https://hackage-content.haskell.org/package/bytestring-0.12.2.0/docs/src/Data.ByteString.Lazy.ReadInt.html#_readDecimal
>
> https://hackage-content.haskell.org/package/bytestring-0.12.2.0/docs/src/Data.ByteString.Lazy.ReadInt.html#_digits
>
> --
>     Viktor.  🇺🇦 Слава Україні!
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.



-- 
brandon s allbery kf8nh
allbery.b at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20250720/103e7c36/attachment.html>