Add crc32 function to libiberty

Add crc32 function to libiberty

[Ian Lance Taylor]

[-- Attachment #1: Type: text/plain, Size: 823 bytes --]

Some upcoming work in gold (by Sriraman Tallam) requires a CRC function.
I could add a CRC function to gold, but I think it makes sense to add it
to libiberty instead.  This CRC function is a copy of the one in gdb,
except that the table of constants is precomputed.  The gdb maintainers
may want to consider switching to this version--I don't think 1K of
read-only data space is all that much these days.

I am running a bootstrap on x86_64-unknown-linux-gnu and plan to commit
this shortly.

Ian


include/ChangeLog:

2009-07-24  Ian Lance Taylor  <iant@google.com>

	* libiberty.h (crc32): Declare.

libiberty/ChangeLog:

2009-07-24  Ian Lance Taylor  <iant@google.com>

	* crc32.c: New file.
	* Makefile.in: Rebuild dependencies.
	(CFILES): Add crc32.c.
	(REQUIRED_OFILES): Add ./crc32.o.
	* functions.texi: Rebuild.



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Add crc32 function --]
[-- Type: text/x-patch, Size: 9135 bytes --]

Index: include/libiberty.h
===================================================================
--- include/libiberty.h	(revision 150064)
+++ include/libiberty.h	(working copy)
@@ -1,6 +1,7 @@
 /* Function declarations for libiberty.
 
-   Copyright 2001, 2002, 2005, 2007 Free Software Foundation, Inc.
+   Copyright 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
+   2006, 2007, 2008, 2009 Free Software Foundation, Inc.
    
    Note - certain prototypes declared in this header file are for
    functions whoes implementation copyright does not belong to the
@@ -311,6 +312,8 @@ extern void *xmemdup (const void *, size
 extern double physmem_total (void);
 extern double physmem_available (void);
 
+/* Compute the 32-bit CRC of a block of memory.  */
+extern unsigned int crc32 (const unsigned char *, int, unsigned int);
 
 /* These macros provide a K&R/C89/C++-friendly way of allocating structures
    with nice encapsulation.  The XDELETE*() macros are technically
Index: libiberty/Makefile.in
===================================================================
--- libiberty/Makefile.in	(revision 150064)
+++ libiberty/Makefile.in	(working copy)
@@ -124,7 +124,7 @@ COMPILE.c = $(CC) -c @DEFS@ $(CFLAGS) $(
 CFILES = alloca.c argv.c asprintf.c atexit.c				\
 	basename.c bcmp.c bcopy.c bsearch.c bzero.c			\
 	calloc.c choose-temp.c clock.c concat.c cp-demangle.c		\
-	 cp-demint.c cplus-dem.c					\
+	 cp-demint.c cplus-dem.c crc32.c				\
 	dyn-string.c							\
 	fdmatch.c ffs.c fibheap.c filename_cmp.c floatformat.c		\
 	fnmatch.c fopen_unlocked.c					\
@@ -160,7 +160,7 @@ CFILES = alloca.c argv.c asprintf.c atex
 REQUIRED_OFILES =							\
 	./regex.o ./cplus-dem.o ./cp-demangle.o ./md5.o ./sha1.o	\
 	./alloca.o ./argv.o						\
-	./choose-temp.o ./concat.o ./cp-demint.o			\
+	./choose-temp.o ./concat.o ./cp-demint.o ./crc32.o		\
 	./dyn-string.o							\
 	./fdmatch.o ./fibheap.o ./filename_cmp.o ./floatformat.o	\
 	./fnmatch.o ./fopen_unlocked.o					\
@@ -603,6 +603,12 @@ $(CONFIGURED_OFILES): stamp-picdir
 	else true; fi
 	$(COMPILE.c) $(srcdir)/cplus-dem.c $(OUTPUT_OPTION)
 
+./crc32.o: $(srcdir)/crc32.c config.h $(INCDIR)/ansidecl.h $(INCDIR)/libiberty.h
+	if [ x"$(PICFLAG)" != x ]; then \
+	  $(COMPILE.c) $(PICFLAG) $(srcdir)/crc32.c -o pic/$@; \
+	else true; fi
+	$(COMPILE.c) $(srcdir)/crc32.c $(OUTPUT_OPTION)
+
 ./dyn-string.o: $(srcdir)/dyn-string.c config.h $(INCDIR)/ansidecl.h \
 	$(INCDIR)/dyn-string.h $(INCDIR)/libiberty.h
 	if [ x"$(PICFLAG)" != x ]; then \
Index: libiberty/crc32.c
===================================================================
--- libiberty/crc32.c	(revision 0)
+++ libiberty/crc32.c	(revision 0)
@@ -0,0 +1,167 @@
+/* crc32.c
+   Copyright (C) 2009 Free Software Foundation, Inc.
+
+   This file is part of the libiberty library.
+
+   This file is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+
+   In addition to the permissions in the GNU General Public License, the
+   Free Software Foundation gives you unlimited permission to link the
+   compiled version of this file into combinations with other programs,
+   and to distribute those combinations without any restriction coming
+   from the use of this file.  (The General Public License restrictions
+   do apply in other respects; for example, they cover modification of
+   the file, and distribution when not linked into a combined
+   executable.)
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA.
+*/
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include "libiberty.h"
+
+/* This table was generated by the following program.  This matches
+   what gdb does.
+
+   #include <stdio.h>
+
+   int
+   main ()
+   {
+     int i, j;
+     unsigned int c;
+     int table[256];
+
+     for (i = 0; i < 256; i++)
+       {
+	 for (c = i << 24, j = 8; j > 0; --j)
+	   c = c & 0x80000000 ? (c << 1) ^ 0x04c11db7 : (c << 1);
+	 table[i] = c;
+       }
+
+     printf ("static const unsigned int crc32_table[] =\n{\n");
+     for (i = 0; i < 256; i += 4)
+       {
+	 printf ("  0x%08x, 0x%08x, 0x%08x, 0x%08x",
+		 table[i + 0], table[i + 1], table[i + 2], table[i + 3]);
+	 if (i + 4 < 256)
+	   putchar (',');
+	 putchar ('\n');
+       }
+     printf ("};\n");
+     return 0;
+   }
+
+   For more information on CRC, see, e.g.,
+   http://www.ross.net/crc/download/crc_v3.txt.  */
+
+static const unsigned int crc32_table[] =
+{
+  0x00000000, 0x04c11db7, 0x09823b6e, 0x0d4326d9,
+  0x130476dc, 0x17c56b6b, 0x1a864db2, 0x1e475005,
+  0x2608edb8, 0x22c9f00f, 0x2f8ad6d6, 0x2b4bcb61,
+  0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd,
+  0x4c11db70, 0x48d0c6c7, 0x4593e01e, 0x4152fda9,
+  0x5f15adac, 0x5bd4b01b, 0x569796c2, 0x52568b75,
+  0x6a1936c8, 0x6ed82b7f, 0x639b0da6, 0x675a1011,
+  0x791d4014, 0x7ddc5da3, 0x709f7b7a, 0x745e66cd,
+  0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039,
+  0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5,
+  0xbe2b5b58, 0xbaea46ef, 0xb7a96036, 0xb3687d81,
+  0xad2f2d84, 0xa9ee3033, 0xa4ad16ea, 0xa06c0b5d,
+  0xd4326d90, 0xd0f37027, 0xddb056fe, 0xd9714b49,
+  0xc7361b4c, 0xc3f706fb, 0xceb42022, 0xca753d95,
+  0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1,
+  0xe13ef6f4, 0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d,
+  0x34867077, 0x30476dc0, 0x3d044b19, 0x39c556ae,
+  0x278206ab, 0x23431b1c, 0x2e003dc5, 0x2ac12072,
+  0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16,
+  0x018aeb13, 0x054bf6a4, 0x0808d07d, 0x0cc9cdca,
+  0x7897ab07, 0x7c56b6b0, 0x71159069, 0x75d48dde,
+  0x6b93dddb, 0x6f52c06c, 0x6211e6b5, 0x66d0fb02,
+  0x5e9f46bf, 0x5a5e5b08, 0x571d7dd1, 0x53dc6066,
+  0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba,
+  0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e,
+  0xbfa1b04b, 0xbb60adfc, 0xb6238b25, 0xb2e29692,
+  0x8aad2b2f, 0x8e6c3698, 0x832f1041, 0x87ee0df6,
+  0x99a95df3, 0x9d684044, 0x902b669d, 0x94ea7b2a,
+  0xe0b41de7, 0xe4750050, 0xe9362689, 0xedf73b3e,
+  0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2,
+  0xc6bcf05f, 0xc27dede8, 0xcf3ecb31, 0xcbffd686,
+  0xd5b88683, 0xd1799b34, 0xdc3abded, 0xd8fba05a,
+  0x690ce0ee, 0x6dcdfd59, 0x608edb80, 0x644fc637,
+  0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb,
+  0x4f040d56, 0x4bc510e1, 0x46863638, 0x42472b8f,
+  0x5c007b8a, 0x58c1663d, 0x558240e4, 0x51435d53,
+  0x251d3b9e, 0x21dc2629, 0x2c9f00f0, 0x285e1d47,
+  0x36194d42, 0x32d850f5, 0x3f9b762c, 0x3b5a6b9b,
+  0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff,
+  0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623,
+  0xf12f560e, 0xf5ee4bb9, 0xf8ad6d60, 0xfc6c70d7,
+  0xe22b20d2, 0xe6ea3d65, 0xeba91bbc, 0xef68060b,
+  0xd727bbb6, 0xd3e6a601, 0xdea580d8, 0xda649d6f,
+  0xc423cd6a, 0xc0e2d0dd, 0xcda1f604, 0xc960ebb3,
+  0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7,
+  0xae3afba2, 0xaafbe615, 0xa7b8c0cc, 0xa379dd7b,
+  0x9b3660c6, 0x9ff77d71, 0x92b45ba8, 0x9675461f,
+  0x8832161a, 0x8cf30bad, 0x81b02d74, 0x857130c3,
+  0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640,
+  0x4e8ee645, 0x4a4ffbf2, 0x470cdd2b, 0x43cdc09c,
+  0x7b827d21, 0x7f436096, 0x7200464f, 0x76c15bf8,
+  0x68860bfd, 0x6c47164a, 0x61043093, 0x65c52d24,
+  0x119b4be9, 0x155a565e, 0x18197087, 0x1cd86d30,
+  0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec,
+  0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088,
+  0x2497d08d, 0x2056cd3a, 0x2d15ebe3, 0x29d4f654,
+  0xc5a92679, 0xc1683bce, 0xcc2b1d17, 0xc8ea00a0,
+  0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb, 0xdbee767c,
+  0xe3a1cbc1, 0xe760d676, 0xea23f0af, 0xeee2ed18,
+  0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4,
+  0x89b8fd09, 0x8d79e0be, 0x803ac667, 0x84fbdbd0,
+  0x9abc8bd5, 0x9e7d9662, 0x933eb0bb, 0x97ffad0c,
+  0xafb010b1, 0xab710d06, 0xa6322bdf, 0xa2f33668,
+  0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4
+};
+
+/*
+
+@deftypefn Extension unsigned int crc32 (const unsigned char *@var{buf}, int @var{len}, unsigned int @var{init})
+
+Compute the 32-bit CRC of @var{buf} which has length @var{len}.  The
+starting value is @var{init}; this may be used to compute the CRC of
+data split across multiple buffers by passing the return value of each
+call as the @var{init} parameter of the next.
+
+This is intended to match the CRC used by the @command{gdb} remote
+protocol for the @samp{qCRC} command.  In order to get the same
+results as gdb for a block of data, you must pass the first CRC
+parameter as @code{0xffffffff}.
+
+@end deftypefn
+
+*/
+
+unsigned int
+crc32 (const unsigned char *buf, int len, unsigned int init)
+{
+  unsigned int crc = init;
+  while (len--)
+    {
+      crc = (crc << 8) ^ crc32_table[((crc >> 24) ^ *buf) & 255];
+      buf++;
+    }
+  return crc;
+}

Re: Add crc32 function to libiberty

[DJ Delorie]

Please make sure any CRC routines added to libiberty document the
polynomial they use.  Referencing a web site that may vanish at any
time is too risky, despite how standard this polynomial happens to be
at the moment.

Re: Add crc32 function to libiberty

[H.J. Lu]

On Fri, Jul 24, 2009 at 3:49 PM, Ian Lance Taylor<iant@google.com> wrote:
> Some upcoming work in gold (by Sriraman Tallam) requires a CRC function.
> I could add a CRC function to gold, but I think it makes sense to add it
> to libiberty instead.  This CRC function is a copy of the one in gdb,
> except that the table of constants is precomputed.  The gdb maintainers
> may want to consider switching to this version--I don't think 1K of
> read-only data space is all that much these days.
>
> I am running a bootstrap on x86_64-unknown-linux-gnu and plan to commit
> this shortly.
>
> Ian
>
>
> include/ChangeLog:
>
> 2009-07-24  Ian Lance Taylor  <iant@google.com>
>
>        * libiberty.h (crc32): Declare.
>
> libiberty/ChangeLog:
>
> 2009-07-24  Ian Lance Taylor  <iant@google.com>
>
>        * crc32.c: New file.
>        * Makefile.in: Rebuild dependencies.
>        (CFILES): Add crc32.c.
>        (REQUIRED_OFILES): Add ./crc32.o.
>        * functions.texi: Rebuild.

Is that possible to use a compatible polynomia so that hardware
crc32 in SSE4.2 can be used if available?

Thanks.


-- 
H.J.

Re: Add crc32 function to libiberty

[Ian Lance Taylor]

DJ Delorie <dj@redhat.com> writes:

> Please make sure any CRC routines added to libiberty document the
> polynomial they use.  Referencing a web site that may vanish at any
> time is too risky, despite how standard this polynomial happens to be
> at the moment.

I didn't reference the web site for the polynomial, just for background.
To be honest, I'm not sure what the polynomial is.  As the comments
explain, the algorithm I used is precisely taken from gdb, in remote.c,
and is intended to produce the same result.  Does anybody on the gdb
side know the polynomial or any other information?

Ian

Re: Add crc32 function to libiberty

[Ian Lance Taylor]

"H.J. Lu" <hjl.tools@gmail.com> writes:

> On Fri, Jul 24, 2009 at 3:49 PM, Ian Lance Taylor<iant@google.com> wrote:
>> Some upcoming work in gold (by Sriraman Tallam) requires a CRC function.
>> I could add a CRC function to gold, but I think it makes sense to add it
>> to libiberty instead.  This CRC function is a copy of the one in gdb,
>> except that the table of constants is precomputed.  The gdb maintainers
>> may want to consider switching to this version--I don't think 1K of
>> read-only data space is all that much these days.
>
> Is that possible to use a compatible polynomia so that hardware
> crc32 in SSE4.2 can be used if available?

As the comments in the file explain, the algorithm is intended to
compute the precise CRC that gdb computes.  That CRC could be hard to
change, as it is used in the remote protocol between gdb and stubs
running on remote targets.

I have no objection to having libiberty also provide an SSE 4.2
compatible polynomial if anybody wants to work on that.

Ian

Re: Add crc32 function to libiberty

[Eli Zaretskii]

> Cc: gdb-patches@sourceware.org, dj@redhat.com
> From: Ian Lance Taylor <iant@google.com>
> Date: Fri, 24 Jul 2009 15:49:00 -0700

I have a couple of comments about the documentation:

> +@deftypefn Extension unsigned int crc32 (const unsigned char *@var{buf}, int @var{len}, unsigned int @var{init})
> +
> +Compute the 32-bit CRC of @var{buf} which has length @var{len}.  The
                                       ^^^^^^^^^^^^^^^^^^^^^^^^^^
A minor stylistic comment: perhaps "whose length is @var{len}" is better.

> +protocol for the @samp{qCRC} command.  In order to get the same
> +results as gdb for a block of data, you must pass the first CRC
> +parameter as @code{0xffffffff}.

By "first CRC parameter", do you mean @var{init}?  If so, I suggest to
say that explicitly.

Finally, perhaps tell what the "CRC" acronym stands for, first time
you use it in the text.

Thanks.

Re: Add crc32 function to libiberty

[Eli Zaretskii]

> Cc: gcc-patches@gcc.gnu.org, gdb-patches@sourceware.org
> From: Ian Lance Taylor <iant@google.com>
> Date: Fri, 24 Jul 2009 17:40:09 -0700
> 
> Does anybody on the gdb side know the polynomial or any other
> information?

AFAICS, this was introduced by Jim Blandy.  Jim, are can you help us
here?

Re: Add crc32 function to libiberty

[Michael Snyder]

Eli Zaretskii wrote:
>> Cc: gcc-patches@gcc.gnu.org, gdb-patches@sourceware.org
>> From: Ian Lance Taylor <iant@google.com>
>> Date: Fri, 24 Jul 2009 17:40:09 -0700
>>
>> Does anybody on the gdb side know the polynomial or any other
>> information?
> 
> AFAICS, this was introduced by Jim Blandy.  Jim, are can you help us
> here?

There may be some confusion here.  At least I'm confused.

Jim added gnu_debuglink_crc32() to utils.c in 2003 (to be used
by symfile.c), but I added static ulong crc32() to remote.c some
time around 1997-1998 (argh, there's no changelog entry) while
working on tracepoints.

Ian's new function bears a closer resemblance to the one in
remote.c than to the one in utils.c, other than the fact that
it uses a pre-computed table.  I'm not familiar with Jim's
version, and don't know whether they compute the same result.

I'm not seeking credit here -- in fact, I'd prefer to avoid it,
since I frankly don't remember where I came up with the algorithm.
;-(

Michael

Re: Add crc32 function to libiberty

[Michael Snyder]

Michael Snyder wrote:
> Eli Zaretskii wrote:
>>> Cc: gcc-patches@gcc.gnu.org, gdb-patches@sourceware.org
>>> From: Ian Lance Taylor <iant@google.com>
>>> Date: Fri, 24 Jul 2009 17:40:09 -0700
>>>
>>> Does anybody on the gdb side know the polynomial or any other
>>> information?
>> AFAICS, this was introduced by Jim Blandy.  Jim, are can you help us
>> here?
> 
> There may be some confusion here.  At least I'm confused.
> 
> Jim added gnu_debuglink_crc32() to utils.c in 2003 (to be used
> by symfile.c), but I added static ulong crc32() to remote.c some
> time around 1997-1998 (argh, there's no changelog entry) while
> working on tracepoints.
> 
> Ian's new function bears a closer resemblance to the one in
> remote.c than to the one in utils.c, other than the fact that
> it uses a pre-computed table.  I'm not familiar with Jim's
> version, and don't know whether they compute the same result.
> 
> I'm not seeking credit here -- in fact, I'd prefer to avoid it,
> since I frankly don't remember where I came up with the algorithm.
> ;-(
> 
> Michael

OK, google gives millions of hits for the crc const 0x04c11db7
used by Ian's and my (remote.c) algorithm.  I can't find my way
to an original source, but apparently the algorithm was published
as a part if IEEE 802.3 (ethernet), and is in very wide use
(mpeg, png, v.42, posix cksum...)

If you want to know the actual polynomial, this MIGHT be it
(I guarantee nothing):
x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 
+ x^4 + x^2 + x + 1

Happy googling!

Re: Add crc32 function to libiberty

[Dave Korn]

Michael Snyder wrote:

> OK, google gives millions of hits for the crc const 0x04c11db7
> used by Ian's and my (remote.c) algorithm.  I can't find my way
> to an original source, but apparently the algorithm was published
> as a part if IEEE 802.3 (ethernet), and is in very wide use
> (mpeg, png, v.42, posix cksum...)
> 
> If you want to know the actual polynomial, this MIGHT be it
> (I guarantee nothing):

  Take a read through the document at the URL that Ian quoted in the patch.
It is the most thoroughly comprehensive explanation you could ask for of the
nomenclature and variations of the crc algorithm.

    cheers,
      DaveK

Re: Add crc32 function to libiberty

[Frank Ch. Eigler]

Ian Lance Taylor <iant@google.com> writes:

> As the comments in the file explain, the algorithm is intended to
> compute the precise CRC that gdb computes.  [...]

Then how about renaming it gdb_crc32 ?

- FChE

Re: Add crc32 function to libiberty

[Jeremy Bennett]

On Sat, 2009-07-25 at 12:24 -0700, Michael Snyder wrote:

> There may be some confusion here.  At least I'm confused.
> 
> Jim added gnu_debuglink_crc32() to utils.c in 2003 (to be used
> by symfile.c), but I added static ulong crc32() to remote.c some
> time around 1997-1998 (argh, there's no changelog entry) while
> working on tracepoints.
> 
> Ian's new function bears a closer resemblance to the one in
> remote.c than to the one in utils.c, other than the fact that
> it uses a pre-computed table.  I'm not familiar with Jim's
> version, and don't know whether they compute the same result.
> 
> I'm not seeking credit here -- in fact, I'd prefer to avoid it,
> since I frankly don't remember where I came up with the algorithm.
> ;-(

The algorithm used in both cases is the CRC-32 defined in IEEE 802.3
using the polynomial x^32 + x^26 + x^23 + x^22 + x^16 + x^12 +x^11 +
x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + +1.

However it is used in slightly different ways in each case, and will
give different results for the same input.

In utils.c, the CRC is computed byte at a time from a starting value of
0xffffffff, taking the *least* significant bit of each byte first, and
inverting the final result.

In remote.c, the CRC is computed byte at a time from a starting value of
0xffffffff, taking the *most* significant bit of each byte first. The
final result is not inverted.

Wikipedia has good articles on CRC, its mathematics, and the algorithms
to compute it.

The attached patch (which is independent of Ian Lance Taylor's proposed
CRC patch) updates the GDB manual to make explicit the CRC used in each
case. Suggested entry for the doc directory ChangeLog:

2009-07-26  Jeremy Bennett  <jeremy.bennett@embecosm.com>

	* gdb.texinfo (Separate Debug Files, Remote Protocol): Clarified
	CRC definitions.

Comments welcome

HTH,


Jeremy

-- 
Tel:      +44 (1590) 610184
Cell:     +44 (7970) 676050
SkypeID: jeremybennett
Email:   jeremy.bennett@embecosm.com
Web:     www.embecosm.com

diff -Naurp --exclude ChangeLog --exclude Entries --exclude Entries.Log
--exclude Repository --exclude Root --exclude gdb.texinfo.bak
src/gdb/doc/gdb.texinfo src-modified/gdb/doc/gdb.texinfo
--- src/gdb/doc/gdb.texinfo	2009-07-26 11:12:22.000000000 +0100
+++ src-modified/gdb/doc/gdb.texinfo	2009-07-26 15:24:38.000000000 +0100
@@ -13640,13 +13640,13 @@ file:
 @itemize @bullet
 @item
 The executable contains a @dfn{debug link} that specifies the name of
-the separate debug info file.  The separate debug file's name is
-usually @file{@var{executable}.debug}, where @var{executable} is the
-name of the corresponding executable file without leading directories
-(e.g., @file{ls.debug} for @file{/usr/bin/ls}).  In addition, the
-debug link specifies a CRC32 checksum for the debug file, which
-@value{GDBN} uses to validate that the executable and the debug file
-came from the same build.
+the separate debug info file.  The separate debug file's name is
usually
+@file{@var{executable}.debug}, where @var{executable} is the name of
the
+corresponding executable file without leading directories (e.g.,
+@file{ls.debug} for @file{/usr/bin/ls}).  In addition, the debug link
+specifies a 32-bit @dfn{Cyclic Redundancy Check} (CRC) checksum for the
+debug file, which @value{GDBN} uses to validate that the executable and
+the debug file came from the same build.
 
 @item
 The executable contains a @dfn{build ID}, a unique bit string that is
@@ -13796,10 +13796,27 @@ utilities (Binutils) package since versi
 
 @noindent
 
-Since there are many different ways to compute CRC's for the debug
-link (different polynomials, reversals, byte ordering, etc.), the
-simplest way to describe the CRC used in @code{.gnu_debuglink}
-sections is to give the complete code for a function that computes it:
+@cindex CRC algorithm definition
+The CRC used in @code{.gnu_debuglink} is the CRC-32 defined in
+IEEE 802.3 using the polynomial @math{x^{32} + x^{26} + x^{23} + x^{22}
++ x^{16} + x^{12} +x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x +
+1}. The function is computed byte at a time, taking the least
+significant bit of each byte first. The initial pattern
+@code{0xffffffff} is used, to ensure leading zeros affect the CRC and
+the final result is inverted to ensure trailing zeros also affect the
+CRC.
+
+@emph{Note:} This is the same CRC polynomial as used in handling the
+@dfn{Remote Serial Protocol} @code{qCRC} packet (@pxref{Remote
Protocol,
+, @value{GDBN} Remote Serial Protocol}). However in the
+case of the Remote Serial Protocol, the CRC is computed @emph{most}
+significant bit first, and the result is not inverted, so trailing
+zeros have no effect on the CRC value.
+
+For a complete explanation the code for the function used in
+@code{.gnu_debuglink} is given here. Inverting the initially supplied
+@code{crc} argument means that an initial call to this function
+passing in zero will start computing the CRC using @code{0xffffffff}.
 
 @kindex gnu_debuglink_crc32
 @smallexample
@@ -28035,7 +28052,18 @@ Any other reply implies the old thread I
 @item qCRC:@var{addr},@var{length}
 @cindex CRC of memory block, remote request
 @cindex @samp{qCRC} packet
-Compute the CRC checksum of a block of memory.
+Compute the CRC checksum of a block of memory using CRC-32 defined in
+IEEE 802.3. The CRC is computed byte at a time, taking the most
+significant bit of each byte first. The initial pattern code
+@code{0xffffffff} is used to ensure leading zeros affect the CRC.
+
+@emph{Note:} This is the same CRC used in validating separate debug
+files (@pxref{Separate Debug Files, , Debugging Information in Separate
+Files}). However the algorithm is slightly different. When validating
+separate debug files, the CRC is computed taking the @emph{least}
+significant bit of each byte first, and the final result is inverted to
+detect trailing zeros.
+
 Reply:
 @table @samp
 @item E @var{NN}

Ping: CRC32 documentation patch

[Jeremy Bennett]

This patch clarifies how CRC is calculated in the GDB manual. I think it
probably got lost in the rest of the discussion of CRC.

Any comments?

Suggested entry for the doc directory ChangeLog:

2009-07-26  Jeremy Bennett  <jeremy.bennett@embecosm.com>

	* gdb.texinfo (Separate Debug Files, Remote Protocol): Clarified
	CRC definitions.


Jeremy

-- 
Tel:      +44 (1590) 610184
Cell:     +44 (7970) 676050
SkypeID: jeremybennett
Email:   jeremy.bennett@embecosm.com
Web:     www.embecosm.com

diff -Naurp --exclude ChangeLog --exclude Entries --exclude Entries.Log
--exclude Repository --exclude Root --exclude gdb.texinfo.bak
src/gdb/doc/gdb.texinfo src-modified/gdb/doc/gdb.texinfo
--- src/gdb/doc/gdb.texinfo	2009-07-26 11:12:22.000000000 +0100
+++ src-modified/gdb/doc/gdb.texinfo	2009-07-26 15:24:38.000000000 +0100
@@ -13640,13 +13640,13 @@ file:
 @itemize @bullet
 @item
 The executable contains a @dfn{debug link} that specifies the name of
-the separate debug info file.  The separate debug file's name is
-usually @file{@var{executable}.debug}, where @var{executable} is the
-name of the corresponding executable file without leading directories
-(e.g., @file{ls.debug} for @file{/usr/bin/ls}).  In addition, the
-debug link specifies a CRC32 checksum for the debug file, which
-@value{GDBN} uses to validate that the executable and the debug file
-came from the same build.
+the separate debug info file.  The separate debug file's name is
usually
+@file{@var{executable}.debug}, where @var{executable} is the name of
the
+corresponding executable file without leading directories (e.g.,
+@file{ls.debug} for @file{/usr/bin/ls}).  In addition, the debug link
+specifies a 32-bit @dfn{Cyclic Redundancy Check} (CRC) checksum for the
+debug file, which @value{GDBN} uses to validate that the executable and
+the debug file came from the same build.
 
 @item
 The executable contains a @dfn{build ID}, a unique bit string that is
@@ -13796,10 +13796,27 @@ utilities (Binutils) package since versi
 
 @noindent
 
-Since there are many different ways to compute CRC's for the debug
-link (different polynomials, reversals, byte ordering, etc.), the
-simplest way to describe the CRC used in @code{.gnu_debuglink}
-sections is to give the complete code for a function that computes it:
+@cindex CRC algorithm definition
+The CRC used in @code{.gnu_debuglink} is the CRC-32 defined in
+IEEE 802.3 using the polynomial @math{x^{32} + x^{26} + x^{23} + x^{22}
++ x^{16} + x^{12} +x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x +
+1}. The function is computed byte at a time, taking the least
+significant bit of each byte first. The initial pattern
+@code{0xffffffff} is used, to ensure leading zeros affect the CRC and
+the final result is inverted to ensure trailing zeros also affect the
+CRC.
+
+@emph{Note:} This is the same CRC polynomial as used in handling the
+@dfn{Remote Serial Protocol} @code{qCRC} packet (@pxref{Remote
Protocol,
+, @value{GDBN} Remote Serial Protocol}). However in the
+case of the Remote Serial Protocol, the CRC is computed @emph{most}
+significant bit first, and the result is not inverted, so trailing
+zeros have no effect on the CRC value.
+
+For a complete explanation the code for the function used in
+@code{.gnu_debuglink} is given here. Inverting the initially supplied
+@code{crc} argument means that an initial call to this function
+passing in zero will start computing the CRC using @code{0xffffffff}.
 
 @kindex gnu_debuglink_crc32
 @smallexample
@@ -28035,7 +28052,18 @@ Any other reply implies the old thread I
 @item qCRC:@var{addr},@var{length}
 @cindex CRC of memory block, remote request
 @cindex @samp{qCRC} packet
-Compute the CRC checksum of a block of memory.
+Compute the CRC checksum of a block of memory using CRC-32 defined in
+IEEE 802.3. The CRC is computed byte at a time, taking the most
+significant bit of each byte first. The initial pattern code
+@code{0xffffffff} is used to ensure leading zeros affect the CRC.
+
+@emph{Note:} This is the same CRC used in validating separate debug
+files (@pxref{Separate Debug Files, , Debugging Information in Separate
+Files}). However the algorithm is slightly different. When validating
+separate debug files, the CRC is computed taking the @emph{least}
+significant bit of each byte first, and the final result is inverted to
+detect trailing zeros.
+
 Reply:
 @table @samp
 @item E @var{NN}

Re: Ping: CRC32 documentation patch

[Eli Zaretskii]

> From: Jeremy Bennett <jeremy.bennett@embecosm.com>
> Date: Tue, 04 Aug 2009 18:36:07 +0100
> 
> This patch clarifies how CRC is calculated in the GDB manual. I think it
> probably got lost in the rest of the discussion of CRC.

Yes, sorry.

> Any comments?

Some.

> +The CRC used in @code{.gnu_debuglink} is the CRC-32 defined in
> +IEEE 802.3 using the polynomial @math{x^{32} + x^{26} + x^{23} + x^{22}
> ++ x^{16} + x^{12} +x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x +
> +1}. The function is computed byte at a time, taking the least

Would the polynomial look better, both in print and in on-line
versions of the manual, if you put it into a @quotation or a @display,
and break it into separate lines manually?  I fear that leaving the
line-breaking job to makeinfo or even TeX could produce ugly results
beyond our control.

> +significant bit of each byte first. The initial pattern
> +@code{0xffffffff} is used, to ensure leading zeros affect the CRC and
> +the final result is inverted to ensure trailing zeros also affect the
> +CRC.

Please leave two spaces between sentences, not one (here and elsewhere
in the patch).

> +For a complete explanation the code for the function used in
> +@code{.gnu_debuglink} is given here.

I suggest to reword like this (avoiding passive tense):

   To complete the description, we show below the code of the function
   which produces the CRC used in @code{.gnu_debuglink}.

Okay with these corrections.

Thanks.

Re: Ping: CRC32 documentation patch

[Jeremy Bennett]

On Tue, 2009-08-04 at 21:20 +0300, Eli Zaretskii wrote:

> > +The CRC used in @code{.gnu_debuglink} is the CRC-32 defined in
> > +IEEE 802.3 using the polynomial @math{x^{32} + x^{26} + x^{23} + x^{22}
> > ++ x^{16} + x^{12} +x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x +
> > +1}. The function is computed byte at a time, taking the least
> 
> Would the polynomial look better, both in print and in on-line
> versions of the manual, if you put it into a @quotation or a @display,
> and break it into separate lines manually?  I fear that leaving the
> line-breaking job to makeinfo or even TeX could produce ugly results
> beyond our control.
> 
> > +significant bit of each byte first. The initial pattern
> > +@code{0xffffffff} is used, to ensure leading zeros affect the CRC and
> > +the final result is inverted to ensure trailing zeros also affect the
> > +CRC.
> 
> Please leave two spaces between sentences, not one (here and elsewhere
> in the patch).
> 
> > +For a complete explanation the code for the function used in
> > +@code{.gnu_debuglink} is given here.
> 
> I suggest to reword like this (avoiding passive tense):
> 
>    To complete the description, we show below the code of the function
>    which produces the CRC used in @code{.gnu_debuglink}.

Hi Eli,

Thanks for the feedback. Revised patch at the end of this message.

I've split the polynomial over two lines in a display. makehtml barfs on
the naked braces needed for multi-digit exponents, so I've set that
explicitly in HTML. Now looks OK in PDF, HTML and info.

I've fixed the double spaces between sentences. I found a handful of
other places where these were needed, so I've taken the opportunity to
fix them at the same time.

I've adopted your suggested wording - much clearer.

If you're happy with this, would you commit it for me - I don't have
write access. Suggested ChangeLog entry is:

2009-08-05  Jeremy Bennett  <jeremy.bennett@embecosm.com>

        * gdb.texinfo (Separate Debug Files, Remote Protocol): Clarified
        CRC definitions.

Thanks,


Jeremy

-- 
Tel:      +44 (1590) 610184
Cell:     +44 (7970) 676050
SkypeID: jeremybennett
Email:   jeremy.bennett@embecosm.com
Web:     www.embecosm.com

diff -Naurp --exclude ChangeLog --exclude Entries --exclude Entries.Log --exclude Repository --exclude Root --exclude gdb.texinfo.bak src/gdb/doc/gdb.texinfo src-modified/gdb/doc/gdb.texinfo
--- src/gdb/doc/gdb.texinfo	2009-08-05 10:52:23.000000000 +0100
+++ src-modified/gdb/doc/gdb.texinfo	2009-08-05 11:11:00.000000000 +0100
@@ -1649,7 +1649,7 @@ short paragraph on how to use that comma
 @item apropos @var{args}
 The @code{apropos} command searches through all of the @value{GDBN}
 commands, and their documentation, for the regular expression specified in
-@var{args}. It prints out all matches found. For example:
+@var{args}.  It prints out all matches found.  For example:
 
 @smallexample
 apropos reload
@@ -3887,7 +3887,7 @@ one.
 Break conditions can have side effects, and may even call functions in
 your program.  This can be useful, for example, to activate functions
 that log program progress, or to use your own print functions to
-format special data structures. The effects are completely predictable
+format special data structures.  The effects are completely predictable
 unless there is another enabled breakpoint at the same address.  (In
 that case, @value{GDBN} might see the other breakpoint first and stop your
 program without checking the condition of this one.)  Note that
@@ -10834,7 +10834,7 @@ specified by the extension to support de
 
 There are two encodings in use, depending on the architecture: BID (Binary
 Integer Decimal) for x86 and x86-64, and DPD (Densely Packed Decimal) for
-PowerPC. @value{GDBN} will use the appropriate encoding for the configured
+PowerPC.  @value{GDBN} will use the appropriate encoding for the configured
 target.
 
 Because of a limitation in @file{libdecnumber}, the library used by @value{GDBN}
@@ -10846,8 +10846,8 @@ point computations, error checking in de
 underflow, overflow and divide by zero exceptions.
 
 In the PowerPC architecture, @value{GDBN} provides a set of pseudo-registers
-to inspect @code{_Decimal128} values stored in floating point registers. See
-@ref{PowerPC,,PowerPC} for more details.
+to inspect @code{_Decimal128} values stored in floating point registers.
+See @ref{PowerPC,,PowerPC} for more details.
 
 @node Objective-C
 @subsection Objective-C
@@ -10982,7 +10982,7 @@ arithmetic types.  Operators are often d
 
 @table @code
 @item **
-The exponentiation operator. It raises the first operand to the power
+The exponentiation operator.  It raises the first operand to the power
 of the second one.
 
 @item :
@@ -11154,7 +11154,7 @@ Integer division and remainder.  Defined
 precedence as @code{*}.
 
 @item -
-Negative. Defined on @code{INTEGER} and @code{REAL} data.
+Negative.  Defined on @code{INTEGER} and @code{REAL} data.
 
 @item ^
 Pointer dereferencing.  Defined on pointer types.
@@ -13644,9 +13644,9 @@ the separate debug info file.  The separ
 usually @file{@var{executable}.debug}, where @var{executable} is the
 name of the corresponding executable file without leading directories
 (e.g., @file{ls.debug} for @file{/usr/bin/ls}).  In addition, the
-debug link specifies a CRC32 checksum for the debug file, which
-@value{GDBN} uses to validate that the executable and the debug file
-came from the same build.
+debug link specifies a 32-bit @dfn{Cyclic Redundancy Check} (CRC)
+checksum for the debug file, which @value{GDBN} uses to validate that
+the executable and the debug file came from the same build.
 
 @item
 The executable contains a @dfn{build ID}, a unique bit string that is
@@ -13796,10 +13796,47 @@ utilities (Binutils) package since versi
 
 @noindent
 
-Since there are many different ways to compute CRC's for the debug
-link (different polynomials, reversals, byte ordering, etc.), the
-simplest way to describe the CRC used in @code{.gnu_debuglink}
-sections is to give the complete code for a function that computes it:
+@cindex CRC algorithm definition
+The CRC used in @code{.gnu_debuglink} is the CRC-32 defined in
+IEEE 802.3 using the polynomial:
+
+@c TexInfo requires naked braces for multi-digit exponents for Tex
+@c output, but this causes HTML output to barf. HTML has to be set using
+@c raw commands. So we end up having to specify this equation in 2
+@c different ways!
+@ifhtml
+@display
+@html
+ <em>x</em><sup>32</sup> + <em>x</em><sup>26</sup> + <em>x</em><sup>23</sup> + <em>x</em><sup>22</sup> + <em>x</em><sup>16</sup> + <em>x</em><sup>12</sup> + <em>x</em><sup>11</sup>
+ + <em>x</em><sup>10</sup> + <em>x</em><sup>8</sup> + <em>x</em><sup>7</sup> + <em>x</em><sup>5</sup> + <em>x</em><sup>4</sup> + <em>x</em><sup>2</sup> + <em>x</em> + 1
+@end html
+@end display
+@end ifhtml
+@ifnothtml
+@display
+ @math{x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11}}
+ @math{+ x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1}
+@end display
+@end ifnothtml
+
+The function is computed byte at a time, taking the least
+significant bit of each byte first.  The initial pattern
+@code{0xffffffff} is used, to ensure leading zeros affect the CRC and
+the final result is inverted to ensure trailing zeros also affect the
+CRC.
+
+@emph{Note:} This is the same CRC polynomial as used in handling the
+@dfn{Remote Serial Protocol} @code{qCRC} packet (@pxref{Remote Protocol,
+, @value{GDBN} Remote Serial Protocol}).  However in the
+case of the Remote Serial Protocol, the CRC is computed @emph{most}
+significant bit first, and the result is not inverted, so trailing
+zeros have no effect on the CRC value.
+
+To complete the description, we show below the code of the function
+which produces the CRC used in @code{.gnu_debuglink}.  Inverting the
+initially supplied @code{crc} argument means that an initial call to
+this function passing in zero will start computing the CRC using
+@code{0xffffffff}.
 
 @kindex gnu_debuglink_crc32
 @smallexample
@@ -15835,14 +15872,14 @@ In keeping with the naming conventions u
 tools, DLL export symbols are made available with a prefix based on the
 DLL name, for instance @code{KERNEL32!CreateFileA}.  The plain name is
 also entered into the symbol table, so @code{CreateFileA} is often
-sufficient. In some cases there will be name clashes within a program
+sufficient.  In some cases there will be name clashes within a program
 (particularly if the executable itself includes full debugging symbols)
 necessitating the use of the fully qualified name when referring to the
-contents of the DLL. Use single-quotes around the name to avoid the
+contents of the DLL.  Use single-quotes around the name to avoid the
 exclamation mark (``!'')  being interpreted as a language operator.
 
 Note that the internal name of the DLL may be all upper-case, even
-though the file name of the DLL is lower-case, or vice-versa. Since
+though the file name of the DLL is lower-case, or vice-versa.  Since
 symbols within @value{GDBN} are @emph{case-sensitive} this may cause
 some confusion. If in doubt, try the @code{info functions} and
 @code{info variables} commands or even @code{maint print msymbols}
@@ -28092,7 +28129,18 @@ Any other reply implies the old thread I
 @item qCRC:@var{addr},@var{length}
 @cindex CRC of memory block, remote request
 @cindex @samp{qCRC} packet
-Compute the CRC checksum of a block of memory.
+Compute the CRC checksum of a block of memory using CRC-32 defined in
+IEEE 802.3.  The CRC is computed byte at a time, taking the most
+significant bit of each byte first.  The initial pattern code
+@code{0xffffffff} is used to ensure leading zeros affect the CRC.
+
+@emph{Note:} This is the same CRC used in validating separate debug
+files (@pxref{Separate Debug Files, , Debugging Information in Separate
+Files}).  However the algorithm is slightly different.  When validating
+separate debug files, the CRC is computed taking the @emph{least}
+significant bit of each byte first, and the final result is inverted to
+detect trailing zeros.
+
 Reply:
 @table @samp
 @item E @var{NN}

Re: Ping: CRC32 documentation patch

[Eli Zaretskii]

> From: Jeremy Bennett <jeremy.bennett@embecosm.com>
> Cc: gdb-patches@sourceware.org
> Date: Wed, 05 Aug 2009 11:24:04 +0100
> 
> I've split the polynomial over two lines in a display. makehtml barfs on
> the naked braces needed for multi-digit exponents, so I've set that
> explicitly in HTML. Now looks OK in PDF, HTML and info.
> 
> I've fixed the double spaces between sentences. I found a handful of
> other places where these were needed, so I've taken the opportunity to
> fix them at the same time.
> 
> I've adopted your suggested wording - much clearer.

Thanks.  This version is fine.  I committed it.