Re: Add crc32 function to libiberty

[Jeremy Bennett <jeremy dot bennett at embecosm dot com>]

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}