CRC32C with seed value

[Akira Hayakawa]

Hi,

I am at loss how I can compute crc32c hash value with given seed.

Some C libraries including Linux kernel's libcrc32c has API that takes three arguments: seed(uint32), data(void *) and the length(int). So the same design in Go's crc32 library helps users import their C programs to Go. Actually, I need the API.

I tried crc32.Update(seed, Castagnoli table, data) but the computed value differs from what I compute with Linux's libcrc32c.

I am not expertise in crc32c algorithm but I am just a user. So I think I should ask you how to make the same thing as libcrc32c using Go's crc32 library.

[Joseph Poirier]

crc32c uses polynomial 0x1EDC6F1 (reversed 0x82F63B78). So from src/hash/example_test.go (replace 0xD5828281 with 0x82F63B78):

package crc32_test

import (
    "fmt"
    "hash/crc32"
)

func ExampleMakeTable() {
    // In this package, the CRC polynomial is represented in reversed notation,
    // or LSB-first representation.
    //
    // LSB-first representation is a hexadecimal number with n bits, in which the
    // most significant bit represents the coefficient of x⁰ and the least significant
    // bit represents the coefficient of xⁿ⁻¹ (the coefficient for xⁿ is implicit).
    //
    // For example, CRC32-Q, as defined by the following polynomial,
    //    x³²+ x³¹+ x²⁴+ x²²+ x¹⁶+ x¹⁴+ x⁸+ x⁷+ x⁵+ x³+ x¹+ x⁰
    // has the reversed notation 0b11010101100000101000001010000001, so the value
    // that should be passed to MakeTable is 0xD5828281.
    crc32q := crc32.MakeTable(0xD5828281)
    fmt.Printf("%08x\n", crc32.Checksum([]byte("Hello world"), crc32q))
    // Output:
    // 2964d064
}

See more test examples in src/hash/crc32_test.go

*Note, 0x82F63B78 is exported from src/hash/crc32.go as a constant via crc32.Castagnoli

[Joseph Poirier]

On Sat, Jul 11, 2015 at 10:25 AM, Akira Hayakawa <ruby...@gmail.com> wrote:

Also, try reflecting the bits of Linux's libcrc32c output to see if the crc matches the Go implementation output.

[Akira Hayakawa]

Hi Joe,

Using Update function to specify a seed is correct?

The wrapper below doesn't work for me

func checkSum(data []byte) uint32 {
        table := crc32.MakeTable(crc32.Castagnoli)
        return crc32.Update(0xffffffff, table, data)
}

What I am doing is C code (using libcrc32c) is the code below where WB_CKSUM_SEED is 0xffffffff. From this project https://github.com/akiradeveloper/dm-writeboost

u32 calc_checksum(void *rambuffer, u8 length)
{
        unsigned int len = (4096 - 512) + 4096 * length;
        return crc32c(WB_CKSUM_SEED, rambuffer + 512, len);
}

I am creating a userland tool for the kernel project.

In there, I need to recompute the checksum value in the userland.

The byte sequences given are identical but the computed values are different.

Both CRC implementation is trustable so I should be doing wrong.

Sorry, I don't know how to match the table bits since

the kernel's library is too complicated.

- Akira

[Joseph Poirier]

Hi Akira,

Not sure what the problem is but Go is generating the correct table,
you can compare the a libcrc32c.c file I hacked at
"https://gist.github.com/jpoirier/f644cce4d2d0f17298c3"  to what Go
generates "http://play.golang.org/p/AXWzgEsn8d"

Let me dig a bit depper...

-joe

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Akira Hayakawa]

Hi Joe,

So the tables are the same but the output values are different?

Go version emits 279b567f but the C version emits 0x8d4ae087 right?

I bit modified your C code a bit to run on Wantbox. http://melpon.org/wandbox/permlink/PpVW7qiihOHexp1h

"unsigned char const" are rejected by the compiler so I removed unsigned specifier.

- Akira

[Joseph Poirier]

On Sun, Jul 12, 2015 at 12:38 AM, Akira Hayakawa <ruby...@gmail.com> wrote:

Hi Joe,

So the tables are the same but the output values are different?

Go version emits 279b567f but the C version emits 0x8d4ae087 right?

Yes, that's correct.

I made my own little function that uses the generated table  and it outputs
exactly what I get from the hacked libcrc32c.c file I made, when using
the same input: "https://play.golang.org/p/OBnxANhmqU"

The function assumes an le machine, if it's not you'd need to do the cpu_to_le32

and le32_to_cpu byte swapping same as the libcrc32c.c file does.

-joe

[Akira Hayakawa]

Hi Joe,

Sorry I don't get it.

I am using Intel CPU that's LE.

So the endian isn't relevant to this problem.

In the first place, how do you create 0xeac7d932 from c1a76c6f by byte swap?

- Akira

[Joseph Poirier]

On Sun, Jul 12, 2015 at 1:00 AM, Akira Hayakawa <ruby...@gmail.com> wrote:

Hi Joe,

Sorry I don't get it.

I am using Intel CPU that's LE.

So the endian isn't relevant to this problem.

In the first place, how do you create 0xeac7d932 from c1a76c6f by byte swap?

- Akira

Okay, forget the byte swap stuff.

Here's a new gist that uses the "Hello world" input:
"https://play.golang.org/p/mDtf5peqjb"

The first crc value was generated using the native Go CRC func and the

second crc value is generated via the crc32c_le function I created, which is

using the table generated from crc32.MakeTable(0x82F63B78).

Note that the second output crc matches that from the hacked libcrc32c.c
file here "https://gist.github.com/jpoirier/f644cce4d2d0f17298c3"

[Akira Hayakawa]

So you are saying that you successfully reproduce the problem in pure Go code?

These values are unmatched because the either of the two crc implementation is wrong?

Below is the Go implementation.

func update(crc uint32, tab *Table, p []byte) uint32 {
	crc = ^crc
	for _, v := range p {
		crc = tab[byte(crc)^v] ^ (crc >> 8)
	}
	return ^crc
}

As I see it,

1) Go version first complement the passed crc and returns the complemented value.

2) Go version casts the 32bit crc to byte type while the C version masks the least 1byte after xor.

I think the 2) isn't the problem (the codes are equal I think) but the difference in 1) is.

So I need to pass the complemented value to Go version and

complement the return value again? I don't know why though

crc = ^crc32.Update(0, tab, data)

[Akira Hayakawa]

The two crc values are the same now.

But I am not sure the reason is.

https://play.golang.org/p/gR83QYQnDD

- Akira

[Joseph Poirier]

It's working because you're nullifying the complementing that's (incorrectly?) being done by the algo in the update function.

The libcrc32c.c file doesn't appear to complement the crc so I'm guessing it shouldn't be done for that use case.

-joe

[Joseph Poirier]

You can also just seed with 0x00000000 to start and just complement the

return value from Update

"https://play.golang.org/p/ne2m6RssCf" 

[Akira Hayakawa]

Rosetta code tells us that complementing is correct.

http://rosettacode.org/wiki/CRC-32

I searched a bit within Linux kernel about xor and found this comment

in crc32c_generic.c

/*

 * Setting the seed allows arbitrary accumulators and flexible XOR policy

 * If your algorithm starts with ~0, then XOR with ~0 before you set

 * the seed.

 */

static int chksum_setkey(struct crypto_shash *tfm, const u8 *key,

                         unsigned int keylen) 

Perhaps, Linux's crc32c library has decided not to complement

the input and the output for performance reason.

- Akira

[Joseph Poirier]

A plethora of variations... Glad you figured it out.

[Akira Hayakawa]

Thanks for your help.

ftp://ftp.naist.jp/pub/Linux/kernel.org/scm/linux/kernel/git/jejb/storage-tree/lib/crc32.c

describes as follows. Linux kernel's crc32 design appears to allow users to choose

whether to complement or not. Very confusing but I finally understand. Thanks again.

* Same crc32 function was used in 5 other places in the kernel.
* I made one version, and deleted the others.
* There are various incantations of crc32(). Some use a seed of 0 or ~0.
* Some xor at the end with ~0. The generic crc32() function takes
* seed as an argument, and doesn't xor at the end. Then individual
* users can do whatever they need.
* drivers/net/smc9194.c uses seed ~0, doesn't xor with ~0.
* fs/jffs2 uses seed 0, doesn't xor with ~0.
* fs/partitions/efi.c uses seed ~0, xor's with ~0.

[Joseph Poirier]

On Sun, Jul 12, 2015 at 3:20 AM, Akira Hayakawa <ruby...@gmail.com> wrote:

Thanks for your help.

ftp://ftp.naist.jp/pub/Linux/kernel.org/scm/linux/kernel/git/jejb/storage-tree/lib/crc32.c

describes as follows. Linux kernel's crc32 design appears to allow users to choose

whether to complement or not. Very confusing but I finally understand. Thanks again.

* Same crc32 function was used in 5 other places in the kernel.
* I made one version, and deleted the others.
* There are various incantations of crc32(). Some use a seed of 0 or ~0.
* Some xor at the end with ~0. The generic crc32() function takes
* seed as an argument, and doesn't xor at the end. Then individual
* users can do whatever they need.
* drivers/net/smc9194.c uses seed ~0, doesn't xor with ~0.
* fs/jffs2 uses seed 0, doesn't xor with ~0.
* fs/partitions/efi.c uses seed ~0, xor's with ~0.

lmao  it's nice when eveyone's on the same page  :/

take care

[Mike Campin]

Shouldn't the polynomial be 0x1EDC6F41 instead of 0x1EDC6F1