[ovs-dev] [PATCH] util: Use lookup table to optimize hexit_value().

[Ben Pfaff]

On Mon, Feb 05, 2018 at 05:03:13PM +0100, Jakub Sitnicki wrote:
> Hi Ben,
> 
> On Fri, Feb 02, 2018 at 11:16 PM GMT, Ben Pfaff wrote:
> > Daniel Alvarez Sanchez reported a significant overall speedup in ovn-northd
> > due to a similar patch.
> >
> > Reported-by: Daniel Alvarez Sanchez <dalvarez at redhat.com>
> > Reported-at: https://mail.openvswitch.org/pipermail/ovs-discuss/2018-February/046120.html
> > Signed-off-by: Ben Pfaff <blp at ovn.org>
> > ---
> >  lib/util.c | 39 +++++++++++++--------------------------
> >  1 file changed, 13 insertions(+), 26 deletions(-)
> >
> > diff --git a/lib/util.c b/lib/util.c
> > index a4d22df0c359..2e7765e41f03 100644
> > --- a/lib/util.c
> > +++ b/lib/util.c
> > @@ -843,32 +843,19 @@ str_to_double(const char *s, double *d)
> >  int
> >  hexit_value(int c)
> >  {
> > -    switch (c) {
> > -    case '0': case '1': case '2': case '3': case '4':
> > -    case '5': case '6': case '7': case '8': case '9':
> > -        return c - '0';
> > -
> > -    case 'a': case 'A':
> > -        return 0xa;
> > -
> > -    case 'b': case 'B':
> > -        return 0xb;
> > -
> > -    case 'c': case 'C':
> > -        return 0xc;
> > -
> > -    case 'd': case 'D':
> > -        return 0xd;
> > -
> > -    case 'e': case 'E':
> > -        return 0xe;
> > -
> > -    case 'f': case 'F':
> > -        return 0xf;
> > -
> > -    default:
> > -        return -1;
> > -    }
> > +    static const signed char tbl[UCHAR_MAX + 1] = {
> > +#define TBL(x)                                  \
> > +        (  x >= '0' && x <= '9' ? x - '0'       \
> > +         : x >= 'a' && x <= 'f' ? x - 'a' + 0xa \
> > +         : x >= 'A' && x <= 'F' ? x - 'A' + 0xa \
> > +         : -1)
> > +#define TBL0(x)  TBL(x),  TBL((x) + 1),   TBL((x) + 2),   TBL((x) + 3)
> > +#define TBL1(x) TBL0(x), TBL0((x) + 4),  TBL0((x) + 8),  TBL0((x) + 12)
> > +#define TBL2(x) TBL1(x), TBL1((x) + 16), TBL1((x) + 32), TBL1((x) + 48)
> > +        TBL2(0), TBL2(64), TBL2(128), TBL2(192)
> > +    };
> > +
> > +    return tbl[c];
> >  }
> >
> >  /* Returns the integer value of the 'n' hexadecimal digits starting at 's', or
> 
> It caught my attention that the contract with hexit_value() callers has
> changed.  Previously we had a catch-all clause for out-of-range values.
> Now there will be an out-of-bounds read.
> 
> Perhaps a check if input is in range would be in place?
> Or some kind of input sanitization like in the original patch?

I don't think any current caller passes an out-of-range value.

What if I just change the parameter type to "unsigned char"?