[RFA] leb128.h: New file.

[RFA] leb128.h: New file.

[Doug Evans]

Hi.

This patch creates leb128.h which contains a few functions for
reading leb128 values.
They're in a header as static inlines because they can be speed critical.
I've only included what I need in GDB.

Ok to check in?

2012-05-14  Doug Evans  <dje@google.com>

	* leb128.h: New file.

Index: leb128.h
===================================================================
RCS file: leb128.h
diff -N leb128.h
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ leb128.h	15 May 2012 04:56:33 -0000
@@ -0,0 +1,116 @@
+/* Utilities for reading leb128 values.
+   Copyright (C) 2012 Free Software Foundation, Inc.
+
+This file is part of the libiberty library.
+Libiberty is free software; you can redistribute it and/or
+modify it under the terms of the GNU Library General Public
+License as published by the Free Software Foundation; either
+version 2 of the License, or (at your option) any later version.
+
+Libiberty is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+Library General Public License for more details.
+
+You should have received a copy of the GNU Library General Public
+License along with libiberty; see the file COPYING.LIB.  If not, write
+to the Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor,
+Boston, MA 02110-1301, USA.  */
+
+/* The functions defined here can be speed critical.
+   Since they are all pretty small we keep things simple and just define
+   them all as "static inline".  */
+
+#ifndef LEB128_H
+#define LEB128_H
+
+#include "ansidecl.h"
+
+/* Get a definition for NULL.  */
+#include <stdio.h>
+
+#ifdef HAVE_STDINT_H
+#include <stdint.h>
+#endif
+#ifdef HAVE_INTTYPES_H
+#include <inttypes.h>
+#endif
+
+/* Decode the unsigned LEB128 constant at BUF into the variable pointed to
+   by R, and return the new value of BUF.
+   If we read off the end of the buffer, NULL is returned.  */
+
+static inline const unsigned char *
+read_uleb128 (const unsigned char *buf, const unsigned char *buf_end,
+	      uint64_t *r)
+{
+  unsigned int shift = 0;
+  uint64_t result = 0;
+  unsigned char byte;
+
+  while (1)
+    {
+      if (buf >= buf_end)
+	return NULL;
+
+      byte = *buf++;
+      result |= ((uint64_t) (byte & 0x7f)) << shift;
+      if ((byte & 0x80) == 0)
+	break;
+      shift += 7;
+    }
+
+  *r = result;
+  return buf;
+}
+
+/* Decode the signed LEB128 constant at BUF into the variable pointed to
+   by R, and return the new value of BUF.
+   If we read off the end of the buffer, NULL is returned.  */
+
+static inline const unsigned char *
+read_sleb128 (const unsigned char *buf, const unsigned char *buf_end,
+	      int64_t *r)
+{
+  unsigned int shift = 0;
+  int64_t result = 0;
+  unsigned char byte;
+
+  while (1)
+    {
+      if (buf >= buf_end)
+	return NULL;
+
+      byte = *buf++;
+      result |= ((uint64_t) (byte & 0x7f)) << shift;
+      shift += 7;
+      if ((byte & 0x80) == 0)
+	break;
+    }
+  if (shift < (sizeof (*r) * 8) && (byte & 0x40) != 0)
+    result |= -(((uint64_t) 1) << shift);
+
+  *r = result;
+  return buf;
+}
+
+/* Return a pointer to just past the end of an LEB128 number in BUF.
+   If the end isn't found before reaching BUF_END, return NULL.  */
+
+static inline const unsigned char *
+skip_leb128 (const unsigned char *buf, const unsigned char *buf_end)
+{
+  unsigned char byte;
+
+  while (1)
+    {
+      if (buf == buf_end)
+	return NULL;
+
+      byte = *buf++;
+      if ((byte & 128) == 0)
+	return buf;
+    }
+}
+
+#endif /* LEB128_H */

Re: [RFA] leb128.h: New file.

[Doug Evans]

Hi.

This is a slightly modified version of my previous patch.

ref: http://gcc.gnu.org/ml/gcc-patches/2012-05/msg00962.html

The only change is to make the result of the functions an int
instead of a const pointer.
This lets them be used in places where the code is using
non-const pointers without having to apply ugly casts.

Ok to check in?

2012-05-17  Doug Evans  <dje@google.com>

	* leb128.h: New file.

Index: leb128.h
===================================================================
RCS file: leb128.h
diff -N leb128.h
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ leb128.h	17 May 2012 18:23:29 -0000
@@ -0,0 +1,130 @@
+/* Utilities for reading leb128 values.
+   Copyright (C) 2012 Free Software Foundation, Inc.
+
+This file is part of the libiberty library.
+Libiberty is free software; you can redistribute it and/or
+modify it under the terms of the GNU Library General Public
+License as published by the Free Software Foundation; either
+version 2 of the License, or (at your option) any later version.
+
+Libiberty is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+Library General Public License for more details.
+
+You should have received a copy of the GNU Library General Public
+License along with libiberty; see the file COPYING.LIB.  If not, write
+to the Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor,
+Boston, MA 02110-1301, USA.  */
+
+/* The functions defined here can be speed critical.
+   Since they are all pretty small we keep things simple and just define
+   them all as "static inline".  */
+
+#ifndef LEB128_H
+#define LEB128_H
+
+#include "ansidecl.h"
+
+/* Get a definition for NULL.  */
+#include <stdio.h>
+
+#ifdef HAVE_STDINT_H
+#include <stdint.h>
+#endif
+#ifdef HAVE_INTTYPES_H
+#include <inttypes.h>
+#endif
+
+/* Decode the unsigned LEB128 constant at BUF into the variable pointed to
+   by R, and return the number of bytes read.
+   If we read off the end of the buffer, zero is returned,
+   and nothing is stored in R.
+
+   Note: The result is an int instead of a pointer to the next byte to be
+   read to avoid const-vs-non-const problems.  */
+
+static inline int
+read_uleb128 (const unsigned char *buf, const unsigned char *buf_end,
+	      uint64_t *r)
+{
+  const unsigned char *p = buf;
+  unsigned int shift = 0;
+  uint64_t result = 0;
+  unsigned char byte;
+
+  while (1)
+    {
+      if (p >= buf_end)
+	return 0;
+
+      byte = *p++;
+      result |= ((uint64_t) (byte & 0x7f)) << shift;
+      if ((byte & 0x80) == 0)
+	break;
+      shift += 7;
+    }
+
+  *r = result;
+  return p - buf;
+}
+
+/* Decode the signed LEB128 constant at BUF into the variable pointed to
+   by R, and return the number of bytes read.
+   If we read off the end of the buffer, zero is returned,
+   and nothing is stored in R.
+
+   Note: The result is an int instead of a pointer to the next byte to be
+   read to avoid const-vs-non-const problems.  */
+
+static inline int
+read_sleb128 (const unsigned char *buf, const unsigned char *buf_end,
+	      int64_t *r)
+{
+  const unsigned char *p = buf;
+  unsigned int shift = 0;
+  int64_t result = 0;
+  unsigned char byte;
+
+  while (1)
+    {
+      if (p >= buf_end)
+	return 0;
+
+      byte = *p++;
+      result |= ((uint64_t) (byte & 0x7f)) << shift;
+      shift += 7;
+      if ((byte & 0x80) == 0)
+	break;
+    }
+  if (shift < (sizeof (*r) * 8) && (byte & 0x40) != 0)
+    result |= -(((uint64_t) 1) << shift);
+
+  *r = result;
+  return p - buf;
+}
+
+/* Return the number of bytes to read to skip past an LEB128 number in BUF.
+   If the end isn't found before reaching BUF_END, return zero.
+
+   Note: The result is an int instead of a pointer to the next byte to be
+   read to avoid const-vs-non-const problems.  */
+
+static inline int
+skip_leb128 (const unsigned char *buf, const unsigned char *buf_end)
+{
+  const unsigned char *p = buf;
+  unsigned char byte;
+
+  while (1)
+    {
+      if (p == buf_end)
+	return 0;
+
+      byte = *p++;
+      if ((byte & 128) == 0)
+	return p - buf;
+    }
+}
+
+#endif /* LEB128_H */

Re: [RFA] leb128.h: New file.

[Doug Evans]

Ping.

On Thu, May 17, 2012 at 11:29 AM, Doug Evans <dje@google.com> wrote:
> Hi.
>
> This is a slightly modified version of my previous patch.
>
> ref: http://gcc.gnu.org/ml/gcc-patches/2012-05/msg00962.html
>
> The only change is to make the result of the functions an int
> instead of a const pointer.
> This lets them be used in places where the code is using
> non-const pointers without having to apply ugly casts.
>
> Ok to check in?
>
> 2012-05-17  Doug Evans  <dje@google.com>
>
>        * leb128.h: New file.
>
> Index: leb128.h
> ===================================================================
> RCS file: leb128.h
> diff -N leb128.h
> --- /dev/null   1 Jan 1970 00:00:00 -0000
> +++ leb128.h    17 May 2012 18:23:29 -0000
> @@ -0,0 +1,130 @@
> +/* Utilities for reading leb128 values.
> +   Copyright (C) 2012 Free Software Foundation, Inc.
> +
> +This file is part of the libiberty library.
> +Libiberty is free software; you can redistribute it and/or
> +modify it under the terms of the GNU Library General Public
> +License as published by the Free Software Foundation; either
> +version 2 of the License, or (at your option) any later version.
> +
> +Libiberty is distributed in the hope that it will be useful,
> +but WITHOUT ANY WARRANTY; without even the implied warranty of
> +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> +Library General Public License for more details.
> +
> +You should have received a copy of the GNU Library General Public
> +License along with libiberty; see the file COPYING.LIB.  If not, write
> +to the Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor,
> +Boston, MA 02110-1301, USA.  */
> +
> +/* The functions defined here can be speed critical.
> +   Since they are all pretty small we keep things simple and just define
> +   them all as "static inline".  */
> +
> +#ifndef LEB128_H
> +#define LEB128_H
> +
> +#include "ansidecl.h"
> +
> +/* Get a definition for NULL.  */
> +#include <stdio.h>
> +
> +#ifdef HAVE_STDINT_H
> +#include <stdint.h>
> +#endif
> +#ifdef HAVE_INTTYPES_H
> +#include <inttypes.h>
> +#endif
> +
> +/* Decode the unsigned LEB128 constant at BUF into the variable pointed to
> +   by R, and return the number of bytes read.
> +   If we read off the end of the buffer, zero is returned,
> +   and nothing is stored in R.
> +
> +   Note: The result is an int instead of a pointer to the next byte to be
> +   read to avoid const-vs-non-const problems.  */
> +
> +static inline int
> +read_uleb128 (const unsigned char *buf, const unsigned char *buf_end,
> +             uint64_t *r)
> +{
> +  const unsigned char *p = buf;
> +  unsigned int shift = 0;
> +  uint64_t result = 0;
> +  unsigned char byte;
> +
> +  while (1)
> +    {
> +      if (p >= buf_end)
> +       return 0;
> +
> +      byte = *p++;
> +      result |= ((uint64_t) (byte & 0x7f)) << shift;
> +      if ((byte & 0x80) == 0)
> +       break;
> +      shift += 7;
> +    }
> +
> +  *r = result;
> +  return p - buf;
> +}
> +
> +/* Decode the signed LEB128 constant at BUF into the variable pointed to
> +   by R, and return the number of bytes read.
> +   If we read off the end of the buffer, zero is returned,
> +   and nothing is stored in R.
> +
> +   Note: The result is an int instead of a pointer to the next byte to be
> +   read to avoid const-vs-non-const problems.  */
> +
> +static inline int
> +read_sleb128 (const unsigned char *buf, const unsigned char *buf_end,
> +             int64_t *r)
> +{
> +  const unsigned char *p = buf;
> +  unsigned int shift = 0;
> +  int64_t result = 0;
> +  unsigned char byte;
> +
> +  while (1)
> +    {
> +      if (p >= buf_end)
> +       return 0;
> +
> +      byte = *p++;
> +      result |= ((uint64_t) (byte & 0x7f)) << shift;
> +      shift += 7;
> +      if ((byte & 0x80) == 0)
> +       break;
> +    }
> +  if (shift < (sizeof (*r) * 8) && (byte & 0x40) != 0)
> +    result |= -(((uint64_t) 1) << shift);
> +
> +  *r = result;
> +  return p - buf;
> +}
> +
> +/* Return the number of bytes to read to skip past an LEB128 number in BUF.
> +   If the end isn't found before reaching BUF_END, return zero.
> +
> +   Note: The result is an int instead of a pointer to the next byte to be
> +   read to avoid const-vs-non-const problems.  */
> +
> +static inline int
> +skip_leb128 (const unsigned char *buf, const unsigned char *buf_end)
> +{
> +  const unsigned char *p = buf;
> +  unsigned char byte;
> +
> +  while (1)
> +    {
> +      if (p == buf_end)
> +       return 0;
> +
> +      byte = *p++;
> +      if ((byte & 128) == 0)
> +       return p - buf;
> +    }
> +}
> +
> +#endif /* LEB128_H */

Re: [RFA] leb128.h: New file.

[Jan Kratochvil]

On Mon, 21 May 2012 02:30:58 +0200, Doug Evans wrote:
> Ping.
> On Thu, May 17, 2012 at 11:29 AM, Doug Evans <dje@google.com> wrote:
[...]
> > --- /dev/null   1 Jan 1970 00:00:00 -0000
> > +++ leb128.h    17 May 2012 18:23:29 -0000
[...]
> > +/* Get a definition for NULL.  */
> > +#include <stdio.h>

I think <stddef.h> for NULL.


[...]
> > +static inline int

Return type should be size_t or ptrdiff_t.  Likewise for other functions.

> > +read_uleb128 (const unsigned char *buf, const unsigned char *buf_end,
> > +             uint64_t *r)
> > +{
> > +  const unsigned char *p = buf;
> > +  unsigned int shift = 0;
> > +  uint64_t result = 0;
> > +  unsigned char byte;
> > +
> > +  while (1)
> > +    {
> > +      if (p >= buf_end)
> > +       return 0;
> > +
> > +      byte = *p++;
> > +      result |= ((uint64_t) (byte & 0x7f)) << shift;
> > +      if ((byte & 0x80) == 0)
> > +       break;
> > +      shift += 7;
> > +    }
> > +
> > +  *r = result;
> > +  return p - buf;
> > +}
[...]


Regards,
Jan

Re: [RFA] leb128.h: New file.

[Ian Lance Taylor]

dje@google.com (Doug Evans) writes:

> 2012-05-17  Doug Evans  <dje@google.com>
>
> 	* leb128.h: New file.

I'm not entirely sure about the use of int64_t to hold the result.  Do
we want to let this interface support larger types some day?  E.g.,
should the result be long long?

I'll approve this patch, but think about it.

The patch is not as portable as possible, but it will probably be OK in
practice.  You should deal with any issues that arise.

Thanks.

Ian

Re: [RFA] leb128.h: New file.

[Doug Evans]

On Mon, May 21, 2012 at 10:08 AM, Ian Lance Taylor <iant@google.com> wrote:
> dje@google.com (Doug Evans) writes:
>
>> 2012-05-17  Doug Evans  <dje@google.com>
>>
>>       * leb128.h: New file.
>
> I'm not entirely sure about the use of int64_t to hold the result.  Do
> we want to let this interface support larger types some day?  E.g.,
> should the result be long long?
>
> I'll approve this patch, but think about it.
>
> The patch is not as portable as possible, but it will probably be OK in
> practice.  You should deal with any issues that arise.

I'll change the result to size_t per Jan's request.
I'm kinda worried about putting people to extra effort when they
compile with -Wconversion which is why I went with int (thinking
people would rather just use an int).  But ok.

long long (+ unsigned long long) is ok by me.
I could also rename the functions to read_uleb128_to_ull (unsigned
long long) to allow for a day if/when someone wants
read_uleb128_to_uint64.  Ok?

Re: [RFA] leb128.h: New file.

[Ian Lance Taylor]

Doug Evans <dje@google.com> writes:

> long long (+ unsigned long long) is ok by me.
> I could also rename the functions to read_uleb128_to_ull (unsigned
> long long) to allow for a day if/when someone wants
> read_uleb128_to_uint64.  Ok?

Sounds good to me.

Thanks.

Ian